返回Google圖書搜尋

On-line Call Admission for High-speed Networks

出版	School of Computer Science, Carnegie Mellon University, 1995
URL	http://books.google.com.hk/books?id=mi_VpwAACAAJ&hl=&source=gbs_api

註釋Abstract: "New networking technologies such as asynchronous transfer mode (ATM) can carry a wide variety of traffic -- voice, video, and data -- over a single digital network. Since some of these services depend on bandwidth guarantees, the network should employ some mechanism for preventing network links from becoming overly congested. This includes making intelligent decisions about whether to accept a call, and if so, when to schedule it, and how to route it. Such strategies are called call admission algorithms. Challenges in the design of such algorithms include high bandwidth requirements and the on-line nature of the problem: when a call comes in, the algorithm has to make an immediate decision about scheduling the call. A call's duration can only be determined by observing how long it takes to complete. A necessary first step in designing call admission algorithms is to understand the nature of traffic. In this thesis we develop traffic models for the connection behavior of traffic currently observed on the Internet. We characterice [sic] the interarrival times, the bandwidth requirements, and the durations of TCP connections. Heavy-tailed distributions, especially the Weibull distribution, yield statistically better models than traditional models such as exponential distributions. We also find evidence of the self- similar nature of connection interarrival times. This implies that the burstiness of current TCP traffic, and most likely future multi-media traffic, differs substantially from conventional traffic models. To cope with bursty traffic, high bandwidth demands, and unknown call durations we suggest algorithms that may delay calls. We use competitive analysis and simulations to evaluate our algorithms. Our results include an analysis of the most basic greedy call admission algorithm. We show, among other results, that GREEDY is [theta](log n)-competitive with respect to network utilization on n-node trees for arbitrary unknown durations and arbitrary bandwidth, and that no alogorithm can be better than [omega](log log n / log log log n)-competitive. Our simulations show that call admission algorithms with delay are robust; even when subjected to very bursty traffic and high bandwidth calls, and achieve better network utilization without affecting many more calls than algorithms without delay. We observe that given a certain achieved network utilization the percentages of calls rejected by a greedy algorithm without delay is about the same as that of a greedy algorithm with delay. Therefore delay may offer the right compromise between the network service provider and the users. We show both in theory via competitive analysis and in practice via simulations that greedy call admission algorithms that may delay calls are superior to those that do not."