in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.Sumit Gupta and Narasimha Reddy, "A Client-oriented IP redirection mechanism," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper introduces a new approach for implementing transparent client access to network services. Ever increasing load on the Internet has made it essential to design services that are fast, reliable, easily mangeable, transparent to access, and that can scale gracefully with load. A common way of achieving this has been replicating services across multiple servers and redirecting clients to different servers depending upon various criteria. Existing schemes are either entirely server or network based. This scheme involves the client network layer actively in redirection. The paper describes the redirection protocol in detail and the basic implementation of the testbed. The performance of the mechanism is measured by experiments on the testbed and analyzed. The advantages and disadvatanges of client based network level redirection are discussed and some useful applications that it enables are described.
Keywords: Internet and experimental systems; IPRP
Sriram Ragahvan, G. Manimaran and Siva Ram Murthy, "A Rearrangeable Algorithm for the Construction of Delay-Constrained Dynamic Multicast Trees," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: With the proliferation of multimedia group applications, the construction of multicast trees satisfying Quality of Service (QoS) requirements is becoming a problem of prime importance. Many of the multicast applications (such as video broadcasts and teleconferencing) require the network to support dynamic multicast sessions wherein the membership of the multicast group changes with time. In this paper, we propose and evaluate an algorithm for the on-line update of multicast trees to adjust to changes in group membership. The algorithm is based on a concept called Quality Factor (QF) that represents the usefulness of a portion of the multicast tree to the overall multicast session. When the usefulness of a particular region of the tree drops below a threshold, a reaarangement technique is used to suitably modify the tree. Our algorithm aims to satisy the delay-constraints of all current group members, at the same time minimizing the cost of the constructed tree. We compare the performance of our algorithm, by simulation, with that of an off-line Steiner heuristic; with ARIES [2], a recently published algorithm for on-line update of unconstrained trees; and with the algorithm proposed in [10] for on-line update of delay-constrained trees. The simulation results indicate that our algorithm provides excellent cost-competitiveness that is better than that provided by the algorithm described in [10], minimizes changes in the multicast tree after each update, and performs favorably even when compared with the unconstrained ARIES heuristic.
Keywords: Routing & Multicasting
Jeong Kim and Marwan Krunz, "Quality of Service over Wireless ATM Links," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Several technical issues must be resolved before ATM services can be efficiently extended to the wireless environment. Key issues include incorporating the characteristics of the time-varying wireless channel in the provisioning of the cell-level QoS, and improving the transport performance using error control mechanisms. In this paper, we analyze the cell loss and delay performance over a wireless ATM link. We consider both cases of a single and multiplexed ATM connections. The link capacity fluctuates according to a fluid version of Gilbert-Elliot channel model. Traffic sources are modeled as on-off fluid processes. Our analytical framework incorporates the effects of error control schemes (i.e., ARQ and/or FEC), which are used to improve the transport performance over the wireless link. For the single-stream case, we derive the mean delay and the cell loss rate (CLR) due to buffer overflow at the sender side of the wireless link. We also obtain a closed-form approximation for the corresponding wireless effective bandwidth. In the case of multiplexed streams, we obtain a good approximation for the CLR using the Chernoff-Dominant Eigenvalue (CDE) approach. The expressions for the CLR and effective bandwidth are then used to study the optimal FEC code rate that guarantees the requested QoS while maximizing the utilization of the wireless bandwidth. Numerical results and simulations are used to verify the adequacy of our analysis and to study the impact of error control on the allocation of bandwidth for guaranteed cell loss and delay performance.
Keywords: Wireless ATM
Ravi Jain, Thomas Raleigh, Danny Yang, Li Fung Chang, Charles Graff, Michael Bereschinsky and Mitesh Patel, "Enhancing Survivability of Mobile Internet Access Using Mobile IP with Location Registers," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: The Mobile IP (MIP) protocol for IP version 4 provides continuous Internet connectivity to mobile hosts. However, currently it has some drawbacks in the areas of survivability, performance, interoperability with protocols for providing QoS. We have proposed an alternative protocol, Mobile IP with Location Registers (MIP-LR), which overcomes some of these drawbacks and is closer to the ``service node'' database approach used in the Public Switched Telephone Network (PSTN): before launching a packet to the mobile host, the sender first queries a database, called the Home Location Register (HLR), to obtain the recipient's current location. MIP-LR is designed for operation in enterprise environments or within logical administrative domains. In this paper we focus on showing how MIP-LR enhances the survivability of MIP by eliminating some of the functions which MIP introduces for mobility support, allowing the HLR to be placed outside the mobiles home network in case the latter is particularly vulnerable, and replicating and distributing HLRs. We present two schemes for managing the multiple HLRs and enabling mobile and correspondent hosts to dynamically discover the addresses of the HLRs serving a given mobile host. The first scheme introduces a set of Translation Servkets from the correspondent host to the mobile host must travel via three (sub)networks: the the second uses a form of quorum consensus based on the Triangle Lattice (TL); for the latter we present an enhanced protocol called the Optimistic TL (OTL). For both schemes we present algorithms for mobile host registration and packet delivery, protocols for recovery from HLR failures, and complexity analysis of the overhead involved.
Keywords: Wireless; mobility
Isabella Chang, Robert Engel, Dilip Kandlur, Dimitrios Pendarakis and Debanjan Saha, "Key Management for Secure Internet Multicast using Boolean Function Minimization Techniques," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: The Internet today provides no support for privacy or authentication of multicast data distribution. However, an increasing number of applications will require secure multicast services in order to restrict group membership and enforce accountability of group members. A major problem associated with the deployment of secure multicast delivery services is the scalability of the key distribution protocol. This is particularly true with regard to the handling of group membership changes, such as member departures and/or expulsions, which necessitate the distribution of a new session key to all the remaining group members. In this paper, we present a new multicast key management scheme which uses a set of auxiliary keys in order to improve scalability. In contrast to previous schemes which generate a fixed hierarchy of keys, we dynamically generate the most suitable key hierarchy by composing different keys. However, our work goes one step further by focusing on the problem of cumulative member removal. Using Boolean function minimization techniques, our scheme outperforms all other schemes known to us in terms of message complexity in removing multiple group members. The efficiency of our scheme in aggregating key updates, due to multiple member departures, offers the potential of a significant performance advantage. The proposed scheme has been used within a toolkit for secure Internet multicast services that we have developed.
Keywords: Network Management and security
Dan Rubenstein, Sneha Kasera, Don Towsley and Jim Kurose, "Improving Reliable Multicast Using Active Parity Encoding Services (APES)," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We propose and evaluate novel reliable multicast protocols that combine active repair service (a.k.a. local recovery) and parity encoding (a.k.a. forward error correction or FEC) techniques. We show that, compared to other repair service protocols, our protocols require less buffer inside the network, maintain the low bandwidth requirements of previously proposed repair service / FEC combination protocols, and reduce the amount of FEC processing at repair servers, moving more of this processing to the end-hosts. We also examine repair service / FEC combination protocols in an environment where loss rates differ across domains within the network. We find that repair services are more effective than FEC at reducing bandwidth utilization in such environments. Furthermore, adding FEC to a repair services protocol not only reduces buffer requirements at repair servers, but also reduces bandwidth utilization in domains with high loss, or in domains with large populations of receivers.
Keywords: Routing & Multicasting
Jinwoo Choe and Ness Shroff, "Queueing Analysis of High-Speed Multiplexers including Long-Range Dependent Arrival Processes," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: With the advent of high-speed networks, we expect that a single link will carry hundreds or even thousands of applications. This results in a very natural application of the Central-Limit-Theorem, to model the arrival process to a queue by a Gaussian stochastic process. In this paper we study the tail probability P(Q>x) of a queueing system when the arrival process is assumed to be a very general class of Gaussian processes. Our study is based on Extreme Value Theory and we show that log P(Q>x) + m(x)/2 grows at most (on the order of) log x, where m(x) corresponds to the reciprocal of the maximum (normalized) variance of a Gaussian process directly related to the aggregate arrival process. This result is considerably stronger than the existing results in the literature based on Large Deviation Theory. We further show that this improvement can be quite important in characterizing the asymptotic behavior of P(Q>x). The types of Gaussian processes that our results cover also include a large class of processes that exhibit self-similarity and other types of long-range dependence. Through numerical examples we show that exp(-m(x)/2) provides a very accurate estimate for a variety of long-range and short-range dependent arrival processes over the entire buffer range.
Keywords: Performance analysis and modeling
Qingming Ma and Peter Steenkiste, "Supporting Dynamic Inter-Class Resource Sharing: A Multi-Class QoS Routing Algorithm," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In an integrated services network, resources are shared by multiple traffic classes. Service classes that deliver Quality-of-Service (QoS) to applications have priority over others that do not. In such a multi-service network, routing decisions for high priority QoS traffic will affect what resources are available for lower priority traffic: Poor route selection can result in congestion for, or even starvation of, lower priority traffic. Whereas many studies have focused on routing algorithms that optimize the network throughput for individual service classes, little effort has been devoted to routing algorithms that address inter-class resource sharing. In this paper, we propose a routing algorithm that allows dynamic sharing of link resources among multiple traffic classes. The algorithm is based on the concept of ``virtual residual bandwidth,'' which is derived from the link residual bandwidth by taking the congestion condition of low priority traffic into account. By using the virtual residual bandwidth in the link cost function for QoS sessions, we discourages QoS sessions from using links that are heavily loaded with low priority traffic. Our approach is simple in the sense that besides changing the link cost function, no other changes to the routing algorithms for individual service classes are required. An extensive simulation study shows that when the traffic load is unevenly distributed, significant performance improvements can be achieved for low priority traffic without sacrificing performance for high priority traffic. The result demonstrates that QoS routing is important even when the QoS traffic load is light and call blocking is not an issue.
Keywords: Routing & Multicasting
Xun Huang, Rosen Sharma and S. Keshav, "The Entrapid Protocol Development Environment," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Keywords: Communications protocols and software
Andrea Fumagalli, Isabella Cerutti, Marco Tacca, Francesco Masetti, Rajesh Jagannathan and Sridhar Alagar, "Survivable Networks Based on Optimal Routing and WDM Self-Healing Rings," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: The design of survivable all-optical networks based on self-healing WDM rings (SHR/WDM) to provide 100% protection from any single link failure requires the joint solution of three sub-problems. These are the Ring Cover of the mesh topology (the RC sub-problem), the routing of Working Lightpaths between node pairs to support traffic demands (the WL sub-problem) and the selection of the SHR/WDM Spare Wavelengths for the protection of every link traffic (the SW sub-problem). This paper presents an ILP formulation of the problem of minimizing the total wavelength mileage (lambda-miles) required to support a set of given traffic demands in a given network topology using SHR/WDM employing 1:N line protection mechanism (the WRL problem). This formulation allows to jointly and optimally solve the three sub-problems, and yields up to 15% reduction of the total lambda-miles required by existing solutions that separately resolve the sub-problems. A simplified sub-optimal solution of the WRL problem is also provided, that yields results few percent worse than the optimal solution and that is tractable for networks whose size is on the order of the Pan-European network, i.e., 19 nodes.
Keywords: Optical
Bo Li, Mordecai Golin, Giuseppe Italiano, Xin Deng and Kazem Sohraby, "On The Optimal Placement of Web Proxies in the Internet," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Web caching or web proxy has been considered as the prime vehicle of coping with the ever-increasing demand for information retrieval over the Internet, WWW being a typical example. Existing work on web proxy has primarily focused on content based caching; relatively less attention has been given to the development of proper placement strategies for the potential web proxies in the Internet. In this paper, we argue that the placement of web proxies is critical to the performancem and further investigates the optimal placement policy of web proxies for a target web server in the Internet. The objective is to optimize a given performance measure for the target web server subject to system resources and traffic pattern. Specifically, we are interested in finding the optimal placement of multiple web proxies ($M$) among potential sites ($N$) under a given traffic pattern. We show this can be modeled a Dynamic Programming problem. We further obtain the optimal solution for the tree topology using $O(N^3M^2)$ time.
Keywords: Internet and experimental systems
David Starobinski and Moshe Sidi, "Stochastically Bounded Burstiness for Communication Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We develop a network calculus for processes whose burstiness is stochastically bounded by general decreasing functions. This calculus enables us to prove the stability of feedforward networks and obtain statistical upper bounds on interesting performance measures such as delay, at each buffer in the network. Our bounding methodology is useful for a large class of input processes, including important processes exhibiting ``subexponentially bounded burstiness'' such as fractional Brownian motion. Moreover, it generalizes previous approaches and provides much better bounds for common models of real-time traffic, like Markov modulated processes and other multiple time-scale processes. We expect that this new calculus will be of particular interest in the implementation of services providing statistical guarantees.
Keywords: Performance analysis and modeling
Subir Varma, "Performance and Buffering Requirements of TCP Applications in Asymmetric Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Asymmetric networks are defined to be those in which the forward and reverse link speeds may assume different values. These types of networks are becoming more prevalant due to the growing penetration of HFC and ADSL systems. Consequently it is important to understand and quantify the effest that asymmetry has on the performance of TCP applications. This paper studies the effect of the number of buffers in the reverse bottleneck link on TCP throughput, and provides formulae for computing the minimum number of buffers in the forward bottleneck link in order to achieve optimum performance.
Keywords: Performance analysis and modeling
Dean Lorenz and Ariel Orda, "Optimal Partition of QoS Requirements on Unicast Paths and Multicast Trees," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We investigate the problem of optimal resource allocation for end-to-end QoS requirements on unicast paths and multicast trees. Specifically, we consider a framework in which resource allocation is based on local QoS requirements at each network link, and associated with each link is a cost function that increases with the severity of the QoS requirement. Accordingly, the problem that we address is how to partition an end-to-end QoS requirement into local requirements, such that the overall cost is minimized. We establish efficient (polynomial) solutions for both unicast and multicast connections. These results provide the required foundations for the corresponding QoS routing schemes, which identify either paths or trees that lead to minimal overall cost. In addition, we show that our framework provides better tools for coping with other fundamental multicast problems, such as dynamic tree maintenance.
Keywords: Routing & Multicasting
Sylvain Delas, Ravi Mazumdar and Catherine Rosenberg, "Cell loss asymptotics in priority queues accessed by a large number of independent stationary source," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this paper we derive cell loss asymptotics for finite buffers accessed by a large number of independent stationary sources wich are served according to a strict HOL priority schedule. The techniques are based on sample-path arguments, the Bahadur-Rao theorem and scaling. The results are shown to be valid for a wide class of sources including long-range dependent sources. The theoretical results are numerically validated vs. simulations.
Keywords: Performance analysis and modeling
Ornan Gerstel, Phil Lin and Galen Sasaki, "Combined WDM and SONET Network Design," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper considers grooming of low speed traffic into high speed lightpaths in a WDM based optical ring with a primary goal of reducing the cost of the entire system, which is dominated by the cost of the SONET transmission equipment connected to the optical ring. The paper attempts to enumerate the architectural options provided by SONET to arrive at a cost-effective solution, including UPSR and BLSR rings, use of digital cross-connects and back-to-back connections between SONET ADMs to reduce the overall cost, and use of different ring speeds (OC-48 and OC-12). To demonstrate each of the architectures, a uniform traffic is considered and its grooming and resulting SONET architecture demonstrated. The paper deviates from earlier approaches which break the problem into two steps: traffic grooming and assignment of lightpaths to rings, in that it looks at the problem as a whole and tries to solve it in a single step. The paper also considers the characteristics of SONET UPSR and BLSR rings and how these affect the grooming. The paper derives lower and upper bounds to these problems for uniform traffic and shows how these improve on known results.
Keywords: Optical
Shaogang Chen and Kihong Park, "An Architecture for Noncooperative QoS Provision in Many-Switch Systems," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper presents an architecture for multi-class quality of service (QoS) provision in wide area networks comprising of multiple switches or routers. In previous work, we have given a comprehensive analysis of the noncooperative multi-class QoS provision game with selfish users for single-switch systems showing when Nash equilibria exist and under what conditions they are Pareto and/or system optimal. In this paper, we study a specific network architecture for facilitating noncooperative QoS provision in many-switch systems with emphasis on realizability. We shield the user from having to choose the service classes on the switches along a route while preserving the basic premise of selfishness. The network is equally simple and completely decentralized comprising of a compact decision procedure running at all routers in the system. Our adherence to a simple user/simple network paradigm---a crucial component for scalability---is nonetheless able to produce a computational version of Adam Smith's ``invisible hand'' which self-organizes network resources to deliver stratified QoS commensurate with user needs. The simple, decentralized decision procedure is encapsulated as a QoS agent and installed at all routers. The QoS agent acts on behalf of a user's traffic flow by intercepting packets entering a switch implementing generalized processor sharing (GPS) packet scheduling and determines which service class to assign the packet to to satisfy the user's end-to-end QoS requirements---packet loss, delay, and jitter---at minimum cost. It executes a certain self-optimization procedure which is user optimal in the single-switch case and approximates the NP-hard QoS assignment problem in the many-switch case. The QoS agents solve a distributed control problem using only constant space packet header overhead and zero per-connection state at the routers. We present simulation results which show that our architecture is able to provide stable, stratified QoS and we show that our system performs favourably compared to reservation- and FIFO-based schemes.
Keywords: Communications protocols and software
Xusheng Tian and Chuanyi Ji, "Bounding the Performance of Dynamic Channel Allocation with QoS Provisioning for Distributed Admission Control in wireless Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Title: Bounding the Performance of Dynamic Channel Allocation with QoS Provisioning for Distributed Admission Control in Wireless Networks In this work, we investigate the performance of distributed admission control with QoS provisioning and dynamical channel allocation for mobile/wireless networks. We first provide a QoS metric feasible for admission control with dynamically allocated channels. We then derive analytically a criterion using the QoS measure for distributed call admission control with dynamic channel allocation. As Maximum packing is used as the dynamic channel allocation scheme, the results obtained are independent of any particular algorithm which implements the dynamic channel assignment. Our results thereby provide the optimal performance achievable for the distributed admission control with the QoS provisioning by the best dynamic channel allocation scheme in the given setting.
Keywords: Wireless
Khosrow Sohraby and Reza Jafari, "Performance Analysis of a Priority Based ATM Multiplexer with Correlated Arrivals," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this paper, we consider the performance analysis of an ATM multiplexer supporting both delay sensitive (e.g., silence detected voice) and loss sensitive (e.g., data) traffic flows. The delay sensitive cells are stored in a finite (relatively small) buffer and are given service priority over loss sensitive cells in each slot. In our formulation, we allow both classes to have a general (Markovian) correlation structure. A simple matrix geometric solution for the state probability of the system is provided allowing simple computation of any desired performance metric such as loss probability and buffer requirements of high and low priority classes, respectively. We provide number of numerical results. In particular, we consider the superposition of Bernoulli ON-OFF sources often used to model silence detected packetized voice-like traffic as high priority class. The example for low priority traffic is taken to be i.i.d batches of geometric distribution and two-state correlated batches. Our numerical results show that both the loss behavior and the buffer requirements are quite sensitive to the (average) burst size of high priority traffic. In particular, it is demonstrated that for any level of utilization, the buffer requirements for both classes appear to be almost proportional to the burst size of the high priority class. The performance of low priority traffic is shown to be quite sensitive to its correlation structure. This class suffers most if both low and high priority traffic are very bursty.
Keywords: Performance analysis and modeling
Dapeng Wu and H. Jonathan Chao, "Efficient Bandwidth Allocation and Call Admission Control for VBR Service Using UPC Parameters," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Provision of Quality-of-Service (QoS) guarantees is an important and challenging issue in the design of Asynchrous Transfer Mode (ATM) networks. Call Admission Control (CAC) is an integral part of the challenge and is closely related to other aspects of network designs such as traffic characterization and QoS specification. Since the Usage Parameter Control (UPC) parameters are the only standardized traffic characterization, developing efficient CAC schemes based on UPC parameters is significant for the implementation of CAC on ATM switches. In this paper, we develop a CAC algorithm called TAP (derived from TAgged Probability) as well as two other CAC algorithms using the UPC parameters. These CAC algorithms are based on our observation that the loss-probability-to-overflow-probability ratio tends to decrease as the number of sources increases. By introducing the loss-probability-to-overflow-probability ratio $K$, we find that this ratio sheds light on increasing resource utilization while still guaranteeing QoS. Analysis, simulation, and numerical results have shown that the TAP algorithm is simple and efficient.
Keywords: Traffic management; scheduling
Arnaud Legout, Joerg Nonnenmacher and Ernst Biersack, "Bandwidth Allocation Policies for Unicast and Multicast Flows," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Using multicast delivery to multiple receivers reduces the aggregate bandwidth required from the network compared to using unicast delivery to each receiver. To encourage the use of multicast delivery, a higher amount of bandwidth should be allocated to a multicast flow as compared to a unicast flow that share the same bottleneck, but without starving the unicast flow. We investigate three bandwidth allocation policies for multicast flows and evaluate their impact on the bandwidth received by the individual receivers. The policy that allocates the available bandwidth as a logarithmic function of the number of receivers downstream of the bottleneck achieves the best trade-off between maximizing the receiver satisfaction and keeping fairness high.
Keywords: Congestion control
Eytan Modiano and Richard Barry, "Design and Analysis of an Asynchronous WDM Local Area Network Using a Master/Slave Scheduler," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We describe an architecture and Medium Access Control (MAC) protocol for WDM networks. Our system is based on a broadcast star architecture and uses an unslotted access protocol and a centralized scheduler to efficiently provide bandwidth-on-demand in WDM networks. To overcome the effects of propagation delays the scheduler measures the delays between the terminals and the hub and takes that delay into account when scheduling transmissions. Simple scheduling algorithms, based on a look-ahead capability, are used to overcome the effects of head-of-line blocking. An important application area for this system is in optical access networks, where this novel MAC protocol can be used to access wavelengths in a WDM Passive Optical Network (PON).
Keywords: Optical
John Byers, Michael Luby and Michael Mitzenmacher, "Accessing Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed Up Downloads," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Mirror sites enable client requests to be serviced by any of a number of servers, reducing load at individual servers and dispersing network load. Typically, a client requests service from a single mirror site. We consider enabling a client to access a file from multiple mirror sites in parallel to speed up the download. To eliminate complex client-server negotiations that a straightforward implementation of this approach would require, we develop a feedback-free protocol based on erasure codes. We demonstrate that a protocol using fast Tornado codes can deliver dramatic speedups at the expense of transmitting a moderate number of additional packets into the network. Our scalable solution extends naturally to allow multiple clients to access data from multiple mirror sites simultaneously. Our approach applies naturally to wireless networks and satellite networks as well.
Keywords: Routing & Multicasting
Timur Friedman and Don Towsley, "Multicast Session Membership Size Estimation," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We derive estimators and bounds that drive probabilistic polling algorithms for the estimation of the session size, n, of any potentially large scale multicast session. We base our analysis upon a mapping of polling mechanisms to the problem of estimating the parameter n of the binomial(n,p) distribution. From the binomial model, we derive an interval estimator for n, and we characterize the tradeoff between the estimator's quality and its overhead in a manner readily matched to application requirements. We derive other estimators and bounds that enable applications to treat as a tunable parameter the confidence that they will not exceed their overhead limits. We also suggest revised estimators and other improvements for the mechanisms proposed by Bolot, Turletti, and Wakeman, and Nonnenmacher and Biersack.
Keywords: Routing & Multicasting
Santosh Krishnan, Abhijit Choudhury and Fabio Chiussi, "Dynamic Partitioning: A Mechanism for Shared-Memory Management," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), pp. 144-152, Mar. 1999.
Abstract: In this paper, we propose a novel buffer management scheme in order to regulate the individual queue lengths in a shared-memory switch. The primary motivations of our scheme are: i) provide differentiated allocations to the queues sharing the memory, where the allocations are directly derived from the Call Admission Control (CAC) parameters; ii) allow for the co--existence of regulated and best-effort traffic, achieving high buffer utilization without violating the guaranteed buffer allocations to the regulated connections; iii) protect well-behaving connections that conform to their allocations from any misbehaviors in other traffic; and iv) handle deviations in incoming traffic patterns, from the ones assumed by CAC, by distributing unavoidable losses in an equitable manner. The new scheme, which we call Dynamic Partitioning, achieves all these objectives, and constitutes a first example of a scheme that is highly efficient, derives its parameters directly from CAC, and is also very robust against misbehaviors. The scheme is simple to implement, and therefore amenable for deployment in current high-speed switches. We present the scheme in the context of ATM switches, together with cell-level simulations for its validation.
Keywords: Traffic management; scheduling; shared memory switches; buffer management; call admission control
Jeonghoon Mo, Richard La, Venkat Anantharam and Jean Walrand, "Analysis and Comparison of TCP Reno and Vegas," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We propose some improvements of TCP Vegas and compare its performance characteristics with TCP Reno. We argue through analysis that TCP Vegas, with its better bandwidth estimation scheme, uses the network resources more efficiently and fairly than TCP Reno. Simulation results are given that support the results of the analysis.
Keywords: Congestion control
Matthew Roughan and Darryl Veitch, "Measuring Long-Range Dependence under Changing Traffic Conditions," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Recent measurements of various types of network traffic have shown evidence consistent with long-range dependence and self-similarity. However, an alternative explanation for these measurements is non-stationarity in the data. Standard estimators of LRD parameters such as the Hurst parameter H assume stationarity and are susceptible to bias when this assumption does not hold. Hence LRD may be indicated by these estimators when none is present, or alternatively LRD taken to be non-stationarity. The recently developed Abry-Veitch (AV) joint estimator has much better properties when a time-series is non-stationary. In particular the effect of polynomial trends in data may be intrinsically eliminated from the estimates of LRD parameters. This paper investigates the behavior of the AV estimator when there are non-stationarities in the form of a level shift in the mean and/or the variance of a process. We examine cases where the change occurs both gradually or as a single jump discontinuity, and also examine the effect of the size of the shift. In particular we show that although a jump discontinuity may cause bias in the estimates of the H, the bias is negligible except when the jump is sharp, and large compared with the standard deviation of the process. We explain these effects and suggest how any introduced errors might be minimized. We define a broad class of non-stationary LRD processes so that LRD remains well defined under time varying mean and variance, and show how three subclasses correspond to meaningful models of traffic rate under changing traffic conditions. The results are tested by applying the estimator to a real data set which contains a clear non-stationary event falling within this class.
Keywords: Performance analysis and modeling
Junyi Li, Ness Shroff and Edwin Chong, "A Static Power Control Scheme for Wireless Cellular Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We present a novel static power control scheme to improve system capacity in wireless cellular networks. Our basic idea is to reduce intercellular interference and improve the capture probability by coordinating transmission powers of users in different cells. This coordination is determined beforehand and no real-time intercellular coordination is required. Power control is static and fixed, for simplicity of implementation. We formulate and solve a generic optimal scheduling problem with our coordination scheme. We find that the optimal scheduling policy is in a simple form of bang-bang control. We illustrate our scheduling solution by considering a specific case with the uniform fairness constraint. We evaluate, via numerical analysis and simulation, both throughput and delay of the coordination scheme, and compare them with other schemes. We find that the coordination scheme can achieve significant performance improvement, in terms of both maximum throughput and throughput-delay tradeoff, over a wide range of capture ratio values.
Keywords: Wireless
Peter Parnes, Kåre Synnes and Dick Schefström, "A Framework for Management and Control of Distributed Applications using Agents and IP-multicast," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: As more and more applications on the Internet become network aware the need and possibility to remotely control them becomes larger. This paper presents a framework for control and management of distributed applications and components. This is done using IP-multicast and an agent based application architecture. The target of the framework is to allow for resource discovery of both controllable elements and available control points in the these elements as well as real-time control. All this is done in scalable and secure way based on IP-multicast and asymmetric cryptography. The presented framework is also independent of the underlying transport mechanism to allow for flexibility and easy deployment. The framework bandwidth usage and introduced control delay is presented. Details on the reference implementation of the framework and example usage scenarios where the framework is used to create bandwidth adaptive applications and better group awareness is also presented.
Keywords: Internet and experimental systems
Lachlan Andrew, "Measurement-based Band Allocation in Multiband CDMA," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Multiband (or multi-carrier) CDMA is a promising approach to increasing the capacity of CDMA systems, while maintaining compatibility with existing system. This paper proposes and algorithm for allocating new calls to bands based on measured path gains, or alternatively, on estimates of the mobile stations' positions. By separating strong and weak users into separate bands, this algorithm reduces the other-cell interference on the uplink. It is shown to provide significantly better performance than algorithms such as least load when hard handoff is used. An additional benefit of this algorithm is a reduction in the dynamic range required for uplink power control.
Keywords: Wireless
Cheng-Shang Chang, "Deterministic Traffic Specification via Projections under the Min-plus Algebra," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this paper, we address the parameterization problem for traffic envelopes needed for deterministic traffic regulation and service guarantees. A parameterized function is a good ``substitute'' for a traffic envelope if (i) the substitute is not smaller than the envelope and (ii) no other functions not smaller than the envelope are smaller than the substitute. Analogous to the least square approximation problem in a vector space, we use projections under the (min,+)-algebra to find a substitute for a traffic envelope. To facilitate the computation of operations under the (min,+)-algebra, we develop the concept of ordered orthogonal bases. A substitute for a traffic envelope can be represented by a coordinate vector with respect to an ordered orthogonal basis. Operations under the (min,+)-algebra, including pointwise minimum, convolution, subadditive closure, and pointwise maximum, can then be computed on the domain of coordinate vectors. A substitute and its coordinate vector forms a transform pair, called C-transform in the paper. The C-transform is related to the Legendre (or convex) transform and has many properties such as Parseval's formula.
Keywords: Multimedia
Puqi Perry) Tang and Tsung-Yuan Charles) Tai, "Network Traffic Characterization Using Token Bucket Model," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper investigated the problem of deriving token bucket parameters from the observed traffic patterns of computer network flows in two cases. In the basic case, we identified the set of token bucket parameters for any given flow so that all the packets in the flow will be delivered immediately without incurring any delay or loss. Then, we extended the basic case by adding a queue to the token bucket model to temporarily store packets that cannot be delivered right away until enough tokens get accumulated in the bucket. The queue has the effect of smoothing the traffic so that the resulting token bucket parameters are less demanding. It also makes the derived token bucket parameters less fluctuated over time. Relationship among the queue size and token bucket parameters for a given flow are analyzed rigorously. Queuing delay for each packet in the flow is calculated and used to describe the adjusted post-queuing traffic pattern. Simple and efficient algorithms for the derivation of measurement-based traffic specification (MBTS) are presented, along with empirical results. This MBTS technology alleviates the need for users to explicitly characterize the traffic a priori in order to reserve network resource in an integrated services network.
Keywords: Traffic management; scheduling
Archan Misra and Teunis Ott, "The Window Distribution of Idealized TCP Congestion Avoidance with Variable Packet Loss," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper analyzes the stationary behavior of idealized TCP congestion avoidance when the packet loss probability is not constant, but varies as a function of the window size. By neglecting the detailed window behavior during fast recovery, we are able to derive a Markov process that is then approximated by a continuous-time, continuous state-space process. The stationary distribution of this process is analyzed and derived numerically and then extrapolated to obtain the stationary distribution of the TCP window. This numerical analysis enables us to predict the behavior of the TCP congestion window when interacting with a router port performing Early Random Drop (or Random Early Detection) where the loss probability varies with the queue occupancy.
Keywords: Performance analysis and modeling
Martin May, Jean Bolot, Alain Jean-Marie and Christophe Diot, "Simple Performance Models of Differentiated Services Schemes for the Internet," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Schemes based on the tagging of packets have recently been proposed as a low-cost way, both in terms of implementation and architectural changes, to augment the single class best effort service model of the current Internet and to include some kind of service discrimination. Such schemes have a number of attractive features, however, it is not clear exactly what kind of service they would provide to applications. Yet quantifying such service is very important to understand the benefits and drawbacks of the different tagging schemes and of the mechanisms in each scheme (for example, determing how much RIO contributes in the Assured scheme), and to tackle key issues such as tariffing (the difference in tariff between different service classes would presumably depend on the difference in performance between the classes). In this paper, we tackle such issues, and derive a quantitative description of the service provided by tagging schemes. Specifically, we describe and solve simple analytic models of two recently proposed schemes, namely the Assured Service scheme and the Premium Service scheme. We obtain expressions for performance measures that characterize the service provided to tagged packets, the service provided to non-tagged packets, and the fraction of tagged packets that do not get the better service. We use these expressions, as well as simulations and experiments from actual implementations, to illustrate the benefits and shortcomings of the schemes.
Keywords: Performance analysis and modeling
Yetik Serbest and San-qi Li, "Unified Measurement Functions for Traffic Aggregation and Link Capacity Assessment," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this paper, we present simple and informative new measurement functions. Their applications on real traffic traces provide insightful guidelines for measurement-based network control. We investigate practical scenarios and conclude that robust and insensitive measurement intervals can be found with the consideration of multiplexing and connection/flow dynamics. We find that a considerable precentage of the effective bandwidth is required by low frequency traffic in the context of realistic implementations. For a queuing node with the maximum allowable queuing delay dmax, it is quantitatively shown that peak rate of the input traffic filtered (smoothed) with the averaging period of 200dmax captures more than 80% of the effective bandwidth when traffic aggregation and flow/connection dynamics are considered.
Keywords: Traffic management; scheduling
Paolo Narvaez, Kai-Yeung Siu and Hong-Yi Tzeng, "New Dynamic SPT Algorithm based on a Ball-and-String Model," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: A key functionality in today's widely used interior gateway routing protocols such as OSPF and IS-IS involves the computation of a shortest path tree (SPT). In many existing commercial routers, the computation of an SPT is done from scratch following changes in the link states of the network. As there may coexist multiple SPTs in a network with a set of given link states, such recomputation of an entire SPT not only is inefficient but also causes frequent unnecessary changes in the topology of an existing SPT and creates routing instability. This paper presents a new dynamic SPT algorithm that makes use of the structure of the previously computed SPT. Our algorithm is derived by recasting the SPT problem into an optimization problem in a dual linear programming framework, which can also be interpreted using a ball-and-string model. In this model, the increase (or decrease) of an edge weight in the tree corresponds to the lengthening (or shortening) of a string. By stretching the strings until each node is attached to a tight string, the resulting topology of the model defines an (or multiple) SPT(s). By emulating the dynamics of the ball-and-string model, we can derive an efficient algorithm that propagates changes in distances to all affected nodes in a natural order and in a most economical way. Compared with existing results, our algorithm has the best-known performance in terms of computational complexity as well as minimum changes made to the topology of an SPT. Rigorous proofs for correctness of our algorithm and simulation results illustrating its complexity are also presented.
Keywords: Routing & Multicasting
Rajesh Krishnan, Ram Ramanathan and Martha Steenstrup, "Optimization Algorithms for Large Self-Structuring Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: As networks grow in scale and heterogeneity, hierarchical organization is inevitable. In this paper we present the case for optimal self-organization of network hierarchies. We provide a graph partitioning formulation relevant to networking but different from extant graph partitioning literature. In particular, we require that the resultant partitions be connected, a constraint that changes the character of the problem significantly. We devise a solution that consists of distinct phases for initial partitioning, refinement and post-processing, propose efficient heuristics for each phase, and evaluate them extensively on internetwork-like graphs through simulation. Our results suggest that vertex trading techniques, in vogue for a number of decades in graph partitioning, are highly applicable, but multilevel techniques favored by conventional graph partitioning research may be of limited value for internetwork-like graphs. Our solution can be implemented in practical networks to automatically generate Internet OSPF areas or ATM PNNI clusters.
Keywords: Routing and Multicasting
Murali Kodialam and Steven Low, "Resource Allocation in Multicast Trees," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We consider how to allocate bandwidth in a multicast tree so as to optimize some global measure of performance. In our model each receiver has a budget to be used for bandwidth reservation on links along its path from the source, and each link has a cost function depending on the amount of total bandwidth reserved at the link by all receivers using that link. We formulate and solve a problem of allocating bandwidth in the multicast tree such that the sum of link costs is minimized.
Keywords: Routing & Multicasting
Guohong Cao and Mukesh Singhal, "Distributed Fault-Tolerant Channel Allocation for Mobile Cellular Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Distributed channel allocation algorithms have received considerable attention due to their high reliability and scalability. However, in these algorithms, a borrower needs to consult with its interference neighbors in order to borrow a channel. Thus, a borrower fails to borrow channels when it cannot communicate with anyone of its interference neighbors. In real-life networks, under heavy traffic load, a cell has a large probability to experience an intermittent network congestion or even a communication link failure. In these algorithms, since a cell has to consult with a large number of interference neighbors to borrow a channel, the failure rate will be much higher under heavy traffic load. In this paper, we first propose a fault-tolerant channel acquisition algorithm which tolerates communication link failures and node ($MH$ or $MSS$) failures. Then, we present a channel selection algorithm and integrate it into the distributed acquisition algorithm. Simulation results show that our algorithm significantly reduces the failure rate under network congestion, communication link failures, and node failures compared to non-fault-tolerant channel allocation algorithms.
Keywords: Wireless
Anja Feldmann, Ramon Caceres, Fred Douglis, Gideon Glass and Michael Rabinovich, "Performance of Web Proxy Caching in Heterogeneous Bandwidth Environments," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Much work on the performance of Web proxy caching has focused on high-level metrics such as hit rates, but has ignored low-level details such as cookies, aborted connections, and persistent connections between clients and proxies as well as between proxies and servers. These details have a strong impact on performance, particularly in heterogeneous bandwidth environments where network speeds between clients and proxies are significantly different than speeds between proxies and servers. We evaluate through detailed simulations the latency and bandwidth effects of Web proxy caching in such environments. We drive our simulations with packet traces from two scenarios: clients connected through slow dialup modems to a commercial ISP, and clients on a fast LAN in an industrial research lab. We present three main results. One, caching persistent connections at the proxy can improve latency much more than simply caching Web data. Two, aborted connections can waste more bandwidth than that saved by caching data. Three, ``cookies'' can dramatically reduce hit rates by making many documents effectively uncacheable.
Keywords: Internet and experimental systems
Reiner Ludwig and Bela Rathonyi, "Link Layer Enhancements for TCP/IP over GSM," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper has two main contributions. First the extremely high latency of the GSM link is revealed which through measurements is determined to have a magnitude usually only known from satellite links. This greatly impacts the link configuration time of packet framing protocols for serial links like the Point-to-Point Protocol (PPP). The key idea of the proposed solution - Quickstart-PPP - is to break the strict sequential order of the different signalling phases while ensuring that protocol semantics are not violated and interoperability with existing PPP implementations is preserved. As a result the link configuration delay can be completely eliminated. The second contribution uncovers a fundamental problem which is that the GSM circuit-switched data service is not capable of satisfying different reliability requirements simultaneously. More precisely it is not possible to use applications requiring the GSM link to operate in reliable mode together with loss-tolerant but delay-sensitive applications at the same time. The developed solution - Link Sniffer - suggests a mechanism that can be added to the implementation of GSM
Keywords: Wireless
Johnny Chen, Peter Druschel and Devika Subramanian, "A New Approach to Routing With Dynamic Metrics," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We present a new routing algorithm to compute paths within a network using dynamic link metrics. Dynamic link metrics are cost metrics that depend on a link's dynamic state, e.g., the congestion on the link. Our algorithm is destination-initiated: a destination initiates a global path computation to itself using dynamic link metrics. All other destinations that do not initiate this dynamic metric computation use paths that are calculated and maintained by a traditional routing algorithm using static link metrics. Analysis of Internet packet traces show that a high percentage of network traffic is destined for a small number of networks. Because our algorithm is destination-initiated, it achieves maximum performance at minimum cost when it only computes dynamic metric paths to these selected ``hot'' destination networks. This selective approach to route recomputation reduces many of the problems (principally route oscillations) associated with calculating all routes simultaneously. We compare the routing efficiency and end-to-end performance of our algorithm against those of traditional algorithms using dynamic link metrics. The results of our experiments show that our algorithm can provide higher network performance at a significantly lower routing cost under conditions that arise in real networks. The effectiveness of the algorithm stems from the independent, time-staggered recomputation of important paths using dynamic metrics, allowing for splits in congested traffic that cannot be made by traditional routing algorithms.
Keywords: Routing & Multicasting
Ilia Baldine and George Rouskas, "Dynamic Reconfiguration Policies for WDM Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We study the issues arising when considering the problem of reconfiguring broadcast optical networks in response to changes in the traffic patterns. Although the ability to dynamically optimize the network under changing traffic conditions has been recognized as one of the key features of multiwavelength optical networks, this is the first in-depth study of the tradeoffs involved in carrying out the reconfiguration process. Our contribution is three-fold. First, we identify the degree of load balancing and the number of retunings as two important, albeit conflicting, objectives in the design of reconfiguration policies. Second, we formulate the problem as a Markovian Decision Process and we develop a systematic and flexible framework in which to view and contrast reconfiguration policies. Third, we also show how an appropriate selection of reward and cost functions can be used to achieve the desired balance among various performance criteria of interest. Our work demonstrates that it is practical to apply results from Markov Decision Process theory to obtain optimal reconfiguration policies even for networks of large size. The advantages of optimal policies over a class of threshold-based policies are also illustrated through numerical results.
Keywords: Optical
Joy Kuri and Sneha Kasera, "Reliable Multicast in Multi-access Wireless LANs," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Multicast is an efficient paradigm for transmitting data from a sender to a group of receivers. In this paper we focus on multicast in single channel multi--access wireless local area networks (LAN's) comprising several small cells. In such a system, a receiver cannot correctly receive a packet if two or more packets are sent to it at the same time, because the packets ``collide.'' Therefore, one has to ensure that only one node sends at a time. We look at two important issues. First, we consider the problem of the sender acquiring the multi-access channel for multicast transmission. Second, for reliable multicast in each cell of the wireless LAN, we examine ARQ--based approaches. The second issue is important because the wireless link error rates can be very high. We present a new approach to overcome the problem of feedback collision in single channel multi-access wireless LAN's, both for the purpose of acquiring the channel and for reliability. Our approach involves the election of one of the multicast group members (receivers) as a ``leader'' or representative for the purpose of sending feedback to the sender. For reliable multicast, on erroneous reception of a packet, the leader does not send an acknowledgement, prompting a retransmission. On erroneous reception of the packet at receivers other than the leader, our protocol allows negative acknowledgements from these receivers to collide with the acknowledgement from the leader, thus destroying the acknowledgement and prompting the sender to retransmit the packet. Using analytical models, we demonstrate that our protocol exhibits higher throughput in comparison to two other protocols which use traditional delayed feedback--based probabilistic methods. Last, we present a simple scheme for leader election.
Keywords: Routing & Multicasting
Ahmed Bashandy, Edwin K. P. Chong and Arif Ghafoor, "Network Modeling and Jitter Control for Multimedia Communication Over Broadband Network," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Due to the isochronous nature of multimedia data streams, they require special handling by the underlying data network to provide guaranteed Quality of Service (QoS). For pre-orchestrated multimedia documents, the important QOS parameters are bandwidth, jitter and reliability. A data network may employ a large number of service disciplines that provide guaranteed QoS, such as PGPS, SCFQ, VC, WF$^2$Q. In this paper, we propose a network model, which we call the Jitter Graph, to capture the bandwidth, jitter and reliability of a large number of service disciplines. The model also captures the relation between these QoS parameters and the allocated resources, such as bandwidth and buffer. The significance of this model is that it abstracts the properties of the network, which allows the design of QoS routing protocols, resource allocation policies, and traffic regulation schemes that are independent of the specific properties of each node. Based on this model, we propose a traffic regulation scheme, which we call the Initial Delay Regulator (IDR), which reduces, and possibly eliminates, jitter introduced by any service discipline that can be abstracted by the jitter graph network model. We then present and analyze some of the existing service disciplines to determine the parameters of the jitter graph model and to show the generality of the network model and the proposed jitter control regulator. In the end, we simulate some the existing service disciplines to show the effectiveness of IDR in reducing jitter while operating in conjunction with different service disciplines.
Keywords: Multimedia
Victor Firoiu, Jim Kurose and Don Towsley, "Performance Evaluation of ATM Shortcut Connections in Overlaid IP/ATM Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this paper we present methods to evaluate the benefit of using direct ATM connections (shortcuts) between IP nodes in IP over ATM networks, and we identify the combinations of IP and ATM network topologies where ATM shortcut benefits are likely to be high. We model an IP/ATM network with and without ATM shortcuts as two loss networks. We propose a metric for network performance comparison, the Network Load Ratio, that gives the ratio of the number of flows accepted by two networks at the same network blocking probability. We derive an estimator of this metric, the Asymptotic Load Ratio, that has low computational complexity. This estimator forms the basis of a methodology for network performance comparison. We use this method in simulation experiments using random networks. These experiments indicate that in many cases the utilization of an IP/ATM network increases proportionally to the decrease in the average path length when ATM shortcuts are used. We have also found that there is almost no correlation between the increase in network utilization (when using ATM shortcuts) and the IP to ATM node ratio.
Keywords: Performance analysis and modeling
Ray-I Chang, Meng-Chang Chen, Jan-Ming Ho and Ming-Tat Ko, "An Effective and Efficient Traffic Smoothing Scheme for Delivery of Online VBR Media Streams," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Traffic smoothing for delivery of online VBR media streams is one of the most important problems in designing multimedia systems. Given available client buffer and a window-sliding size, conventional approaches try to reduce bandwidth allocated in each window. However, they can not lead to the minimization of bandwidth allocated for transmitting entire stream. Although a window-sliding approach was introduced to further reduce the bandwidth allocated recently [21], it was computational costly. In this paper, an effective and efficient online traffic-smoothing scheme is proposed. Different from the conventional static window-sliding approaches, our approach dynamically decides the suitable window-sliding size to online smooth the bursty traffic. Then, an aggressive workahead scheme is applied in transmitting entire stream. By examining different media streams, our approach has small bandwidth, high bandwidth utilization and small computation cost. Considering the online transmission of a Star War movie, our approach result is 13% less for the bandwidth and 4% less for the network idle rate than SLWIN(1). Comparing the number of window sliding, our approach is 75% less than SLWIN(1). The relations between the characteristic of input traffic and the behavior of obtained scheduling results are discussed. Finally, an extension of the proposed approach to resolve the latency and quality tolerance applications is also introduced.
Keywords: Multimedia
Matthew Andrews, Sanjeev Khanna and Krishnan Kumaran, "Integrated Scheduling of Unicast and Multicast Traffic in an Input-Queued Switch," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We consider the problem of scheduling packets in an input-queued switch when both unicast and multicast traffic is present. In contrast to current approaches which mostly isolate unicast from multicast, we propose an integrated scheduling procedure that packs unicast cells into idle slots left by the multicast schedule. While the optimal integrated schedule can be shown to be NP-hard to obtain, we propose both off-line and on-line algorithms with strong theoretical guarantees to perform integration efficiently. Simulations suggest substantial improvement in switch throughput using the integrated schedule. To further reinforce the importance of performing integration, we study the multicast scheduling problem with and without fanout splitting. Again, we prove hardness of the problem and several of its variants, and propose competitive algorithms. The hardness of multicast scheduling hence emphasizes the importance of integrated scheduling for switch performance.
Keywords: Switching
Bhargav Bellur and Richard Ogier, "A Reliable, Efficient Topology Broadcast Protocol for Dynamic Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We present, prove correctness for, and evaluate a protocol for the reliable broadcast of topology and link-state information in a multihop communication network with a dynamic topology, such as a wireless network with mobile nodes. The protocol is called Topology Broadcast based on Reverse Path Forwarding (TBRPF), and uses the concept of reverse-path forwarding (RPF) to broadcast link-state updates in the reverse direction along the spanning tree formed by the minimum-hop paths from all nodes to the source of the update. TBRPF uses the topology information received along the broadcast trees to compute the minimum-hop paths that form the trees themselves, and is the first topology broadcast protocol based on RPF with this property. The use of minimum-hop trees instead of shortest-path trees (based on link costs) results in less frequent changes to the broadcast trees and therefore less communication cost to maintain the trees. Simulations show that TBRPF achieves up to a 98\% reduction in communication cost as compared to flooding in a 20-node network.
Keywords: Routing & Multicasting
Jeffrey Gilbert and Robert Brodersen, "Globally Progressive Interactive Web Delivery," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper suggests that since web browsing is an interactive process and downloading a web page can take several seconds to several minutes over slow links, the information presented to the user during this time is important. We present new metrics and visualization techniques to illustrate and quantify web page loading. Given the insight afforded by the metrics, we propose a methodology to improve web access using a new technique, globally progressive interactive web delivery. This technique entails applying progressive coding to the document transmission process in its entirety, as well as allowing the user to explicitly direct link bandwidth to images of interest. This globally progressive interactive framework has been developed without modifying either existing web browsers or servers through the use of a web proxy and browser-side Java applets. The framework allows for both protocol and image compression research in a platform-independent manner. Directions of current work on integrating the architecture into existing web infrastructure for greater performance and scalability are discussed.
Keywords: Communications protocols and software
Francois Baccelli, Daniel Kofman and Jean-Louis Rougier, "Self Organizing Hierarchical Multicast Trees and their Optimization," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Multicast routing protocols suitable for wide-area networks are being developed for the Internet. Protocols based on hierarchical trees appears to be well suited for their superior scalability and flexibility. In this paper we show how to construct a class of hierarchical multicast trees and we analyze their performances. This study gives insight into how the chosen hierarchical structure impacts the tree performances with respect to network resource consumption. Optimal structures which minimize resource consumption are deduced, which allows for simple dimensioning rules, such as how many hierarchical levels should be used. A stochastic geometric approach sorted out to be well adapted for this study. This approach leads to explicit expressions for the average tree cost, as a function of the hierarchical clustering, from which the optimal tree structure can then be easily deduced. Keywords: Multicast Routing, Optimization, Hierarchical Center-Based Trees, Dimensioning, Random Geometry, Poisson-Voronoi Tesselations.
Keywords: Routing & Multicasting
Xiaowei Yang, "A Model for Window Based Flow Control in Packet-Switched Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Recently, networks have increased rapidly both in scale and speed. Problems related to the control and management are of increasing interest. The average throughput and end-to-end delay of a network flow are important design factors. However, there is no satisfactory tool to obtain such parameters. The traditional packet-by-packet event driven simulation is slow when the network speed is high. The time driven simulation faces the difficulty of choosing the right time interval when simulating packet-switched networks. As Transmission Control Protocol (TCP) is the most widely used transport layer protocol, and it uses window based flow control mechanism, classic queuing theories involving Markov Chain assumptions are not applicable. This paper describes a model for window based flow control packet-switched networks. The model attempts to provide a way to obtain the steady state results for large and high speed networks using TCP. In this paper, we discuss in detail the construction, implementation and application of the model. This paper also compares the results obtained from the model with those from the packet by packet event driven simulation. The comparison shows the model is correctly modeling the networks.
Keywords: Performance analysis and modeling
Masoud Sajadieh and Frank Kschischang, "A Reduced Complexity Decoding Scheme for Wireless Applications," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Cellular transmission standards such as GSM and IS-54 produce data streams with varying degrees of significance at the source encoder level. We propose an unequal error protection scheme based on a non-uniform signal set which provides the more important data with a preferential Euclidean distance. The unequal error protection is partly accomplished by the modulator in contrast to the conventional systems where the channel encoder is solely responsible. The coding gain resulting from the asymmetric modulation can be translated into a reduction in the complexity of the channel encoder; specifically a reduction by more than half in the number of encoder states can be expected. We study the interaction between the code complexity and the modulation asymmetry in quantitative terms. For differentially coherent systems, a $\pi/6$-shifted differential embedded QPSK is proposed. Decentralizing the bit protection culminates in an extra degree of freedom which in turn introduces more flexibility into the system design.
Keywords: Wireless
Deborah Estrin, Mark Handley, Ahmed Helmy, Polly Huang and David Thaler, "A Dynamic Bootstrap Mechanism for Rendezvous-based Multicast Routing," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Current multicast routing protocols can be classified into three types according to how the multicast tree is established: broadcast and prune (e.g., DVMRP, PIM-DM), membership advertisement (e.g., MOSPF), and rendezvous-based (e.g., CBT, PIM-SM). Rendezvous-based protocols associate with each logical multicast group address, a physical unicast address, referred to as the `core' or `rendezvous point' (RP). Members first join a multicast tree rooted at this rendezvous point in order to receive data packets sent to the group. Rendezvous mechanisms are well suited to large wide-area networks because they distribute group-specific data and membership information only to those routers that are on the multicast distribution tree. However, rendezvous protocols require a bootstrap mechanism to map each logical multicast address to its current physical rendezvous-point address. The bootstrap mechanism must adapt to network and router failures but should minimize unnecessary changes in the group-to-RP mapping. In addition, the bootstrap mechanism should be transparent to the hosts. This paper describes and analyzes the bootstrap mechanism developed for PIM-SM. The mechanism employs an algorithmic mapping of multicast group to rendezvous point address, based on a set of available RPs distributed throughout a multicast domain. The primary evaluation measures are convergence time, message distribution overhead, balanced assignment of groups to RPs, and host impact. The mechanism as a whole, and the design lessons in particular, are applicable to other rendezvous-based multicast routing protocols as well.
Keywords: Routing & Multicasting
Zhiruo Cao and Ellen Zegura, "Utility Max-Min: An Application-Oriented Bandwidth Allocation Scheme," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: As the diversity of applications using integrated networks has increased, the trend has been towards a wider variety of network services with a richer user interface. However, the types of information that applications can currently provide to network services regarding acceptable service (e.g., cell loss rate) share the characteristic that they are potentially poorly correlated with application-layer performance. In this paper, we consider the use of an application-layer performance measure --- the utility --- in the context of bandwidth allocation for an available bit rate service. Our bandwidth allocation scheme can be viewed as a generalization of traditional available bit rate service; our scheme is equivalent to bandwidth max-min allocation when the utility of all applications are equal. The goal of our allocation scheme is to provide good application-layer service to a wide diversity of applications sharing available bandwidth. We achieve this goal while also supporting changes in utility over time, tolerating some inaccuracy in utility function specification, and addressing the issue of circumvention through pricing.
Keywords: Traffic management; scheduling
Jiher Ju and Victor Li, "TDMA Scheduling Design of Multihop Packet Radio Networks Based on Latin Squares," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Many transmission scheduling algorithms have been proposed to maximize the spatial reuse and minimize the Time Division Multiple Access (TDMA) frame length in multihop packet radio networks. Almost all existing algorithms assume exact network topology information and require recomputations when the network topology changes. In addition, existing work focuses on single channel TDMA systems. In this paper, we propose a multichannel topology-transparent algorithm based on latin squares. Our algorithm has the flexibility to allow the growth of the network, i.e., the network can add more mobile nodes without recomputation of transmission schedules for existing nodes. At the same time, a minimum throughput is guaranteed. We analyze the efficiency of our algorithm, and examine the topology-transparent characteristics and the sensitivity on design parameters by simulation.
Keywords: Wireless
Adam Costello and Steven McCanne, "Search Party: Using Randomcast for Reliable Multicast with Local Recovery," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: IP multicast is an efficient means of sending to a group, but the packets are sent unreliably. Some applications, like distributed whiteboard and news articles, require detection and retransmission of lost packets. In order to scale to large groups, local recovery is necessary to avoid involving the entire group in the repair process for packet losses affecting small regions of the distribution tree. While many current research efforts have attempted to devise local recovery schemes that rely only on the existing service model, we believe that extending the multicast forwarding service could enable viable and highly scalable local recovery mechanisms. To investigate this open issue, we propose a new randomized forwarding service called randomcast, and build upon it a loss recovery protocol called Search Party. Starting with the local recovery structure of the very scalable LMS scheme, we use randomized forwarding to greatly improve robustness at a modest cost in overhead and/or retransmission delay (the trade-off between the two costs is fine-tunable). Analysis predicts that as the group size N increases, overhead will increase by at most log N and retransmission delay will be unaffected. Simulation experiments show that both increase very little as N grows from 8 to 64, and confirm the tunability of the trade-off.
Keywords: Routing & Multicasting
Shlomi Dolev, Ephraim Korach and Dmitry Yukelson, "The Sound of Silence: Guessing Games for Saving Energy in Mobile Environment," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper explores efficient discrete coding techniques that are motivated by the time/energy tradeoff in message transmission between mobile hosts and mobile support stations. Three algorithms are suggested two of which use guessing games in which the mobile support station guesses the message to be transmitted by the mobile host and receives approving signal for successful guess from the mobile host. The first algorithm is designed to achieve the smallest expected amount of energy while obeying a time bound for message transmissions. The second algorithm achieves the shortest expected transmission time while obeying a bound on the energy. This algorithm uses dynamic programming to construct an optimal tree for the guessing game. Our third algorithm uses a different approach, approach that is based on the Lempel-Ziv compression algorithm. The time energy tradeoff is controlled by the choice of the length of the codes used to encode strings in the dictionary. The theoretical results obtained are not tied to mobile computing and are of independent interest.
Keywords: Wireless
Nihal Pekergin, "Stochastic Bounds on Delays of Fair Queueing Algorithms," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this paper, we study the delay characteristics of Fair Queueing algorithms with a stochastic comparison approach. In integrated services networks, Fair Queueing policies have received much attention, because they can guarantee an end-to-end delay bound when the burstiness of the session traffic is bounded, and they ensure the fair allocation of the bandwitdh. A large class of FQ policies attempt to emulate Generalized Processor Sharing policy by assigning timestamps to cells. These GPS-related policies have quite complex dynamic, and their exact analytical analysis are not tractable. The delay characteristics of these algorithms are evaluated by considering the worst-case, when sources have a bounded burstiness. In fact, these are deterministic delay bounds which do not always provide an insight on the underlying policies. We propose a methodology to analyze delay characteristics of a class of GPS-related FQ policies with general source models by providing stochastic bounds on their delay distribution. These stochastic bounds are obtained by analyzing two modified Weighted Round Robin policies. Clearly, since cells are scheduled periodically according to a predefined list under WRR-related policies, their models are simpler than the models of GPS-related policies.
Keywords: Performance analysis and modeling
Predrag Jelenkovic, "Network Multiplexer with Truncated Heavy-Tailed Arrival Streams," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper investigates the asymptotic behavior of a single server queue with truncated heavy- tailed arrival sequences. We have discovered and explicitly asymptotically characterized a unique asymptotic behavior of the queue length distribution. Informally, this distribution on the log scale resembles a stair-wave function that has steep drops at speci c bu er sizes. This has important design implications suggesting that negligible increases of the bu er size in certain bu er regions can decrease the over ow probabilities by order of magnitudes. A problem of this type arises quite frequently in practice when the arrival process distribution has a bounded support and inside that support is nicely matched with a heavy-tailed distribution (e.g. Pareto). However, our primary interest in this scenario is in its possible application to controlling heavy-tailed tra c ows. More precisely, one can imagine a network control procedure in which short network ows are separated from long ones. If the distribution of ows is heavy-tailed this procedure will yield truncated heavy-tailed distribution for the short network ows. Intuitively, it can be expected that with short ows one can obtain much better multiplexing gains than with the original ones (before the separation). Indeed, our analysis con rms this expectation.
Keywords: Performance analysis and modeling
Matthew Andrews and Lisa Zhang, "Minimizing End-to-End Delay in High-Speed Networks with a Simple Coordinated Schedule," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We study the problem of providing end-to-end delay guarantees in connection-oriented networks. In this environment, multiple-hop sessions coexist and interfere with one another. Parekh and Gallager showed that the Weighted Fair Queueing (WFQ) scheduling discipline provides a worst-case delay guarantee comparable to $\{1\over \rho_i\} \times K_i$ for a session with rate $\rho_i$ and $K_i$ hops. Such delays can occur since a session-$i$ packet can wait for time $1\over \rho_i$ at every hop. We describe a work-conserving scheme that guarantees an \{\em additive\} delay bound of approximately $\{1\over \rho_i\}+K_i$. This bound is smaller than the \{\em multiplicative\} bound $\{1\over \rho_i\}\times K_i$ of WFQ, especially when the hop count $K_i$ is large. We call our scheme \{\sc Coordinated-Earliest-Deadline-First\} (CEDF) since it uses an earliest-deadline-first approach in which simple coordination is applied to the deadlines for consecutive hops of a session. The key to the bound is that once a packet has passed through its first server, it can pass through all its subsequent servers quickly. We conduct simulations to compare the delays actually produced by the two scheduling disciplines. In many cases, these actual delays are comparable to their analytical worst-case bounds, implying that CEDF outperforms WFQ.
Keywords: Traffic management; scheduling
Saswati Sarkar and Leandros Tassiulas, "A Framework for Routing and Congestion Control in Multicast Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We propose a new multicast routing and scheduling algorithm called multipurpose multicast routing and scheduling algorithm (MMRS). The routing policy load balances amongst various possible routes between the source and the destinations, basing its decisions on the message queue lengths at the source node. The scheduling amongst various sessions sharing links is devised such that the flow of a session depends on the congestion of the next hop links. MMRS is throughput optimal and computationally simple. It can be implemented in a distributed, asynchronous manners. It has several parameters which can be suitably modified to control the end to end delay, packet loss in a topology specific manner. These parameters can be adjusted to offer limited priorities to some desired sessions. MMRS is expected to play a significant role in end to end congestion control in the multicast scenario.
Keywords: Routing & Multicasting
Paul Francis, Sugih Jamin, Vern Paxson, Lixia Zhang, Daniel Gryniewicz and Yixin Jin, "An Architecture for a Global Internet Host Distance Estimation Service," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: There is an increasing need for Internet hosts to be able to quickly and efficiently learn the distance, in terms of metrics such as latency or bandwidth, between Internet hosts. For example, to select the nearest of multiple equal-content web servers. This paper explores technical issues related to the creation of a public infrastructure service to provide such information. In so doing, we suggests an architecture, called IDMaps, whereby Internet distance information is distributed over the Internet, using IP multicast groups, in the form of a virtual distance map. Systems listening to the groups can estimate the distance between any pair of IP addresses by running a spanning tree algorithm over the received distance map. We also presents the results of experiments that give preliminary evidence supporting the architecture. This work thus lays the initial foundation for future work in this new area.
Keywords: Internet and experimental systems
Mario Baldi and Yoram Ofek, "Ring versus Tree Embedding for Real-time Group Multicast," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In general topology networks, routing from one node to another over a tree embedded in the network is intuitively a good strategy, since it typically results in a route length of O(log n) links, being n the number of nodes in the network. Routing from one node to another over a ring embedded in the network would result in route length of O(n) links. However, in group (many-to-many) multicast, the overall number of links traversed by each packet, i.e. the networks elements on which resources must be possibly reserved, is typically O(N) for both tree and ring embedding, where N is the size of the group. This paper focuses on the tree versus ring embedding for real-time group multicast in which all packets should reach all other nodes in the group with a bounded end-to-end delay. In this work real-time properties are guaranteed by the deployment of time-driven priority in network nodes. In order to have a better understanding of the non-trivial problem of ring versus tree embedding, we consider the following group scenarios: (i) static - fixed subset of active nodes, (ii) dynamic - fixed number of active nodes (i.e. the subset of active nodes is changing over time, but its size remains constant), and (iii) adaptive - the number and identity of active nodes change over time. Tree and ring embedding are compared using the following metrics: (i) end-to-end delay bound, (ii) overall bandwidth allocated to the multicast group, and (iii) signaling overhead for sharing of the resources allocated to the group. The results are interesting and counter-intuitive, since, as it is shown, embedding a tree is not always the best strategy. In particular, dynamic and adaptive multicast on a tree require a protocol for updating state information and coordinate the operation of the group. Such a protocol is not required on the ring where the circular topology, (implicit) token passing mechanisms are sufficient. Moreover, the bandwidth allocation on the ring for the above three multicast scenarios is O(N); while on a general tree it is O(N) for the static multicast scenario and O(N^2) for the dynamic and adaptive. Only if a core based tree is used a bandwidth allocation of O(N) is required for any of the three multicast scenarios.
Keywords: Routing & Multicasting
Xi Zhang, Kang Shin, Debanjan Saha and Dilip Kandlur, "Scalable Flow Control for Multicast ABR Services," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We propose a flow-control scheme for multicast ABR services in ATM networks. At the heart of the proposed scheme is an optimal second-order rate control algorithm, called the $\alpha$-control, designed to deal with the variation in RM-cell round-trip time (RTT) resulting from dynamic ``drift'' of the bottleneck in a multicast tree. Applying two-dimensional rate control, the proposed scheme makes the rate process converge to the available bandwidth of the connection's most congested link. It also confines the buffer occupancy to a target regime bounded by a finite buffer capacity. It works well irrespective of the topology of the multicast tree. Using the fluid approximation, we model the proposed scheme and analyze the system dynamics for multicast ABR traffic. We study the convergence properties and derive the optimal-control conditions for the $\alpha$-control. The analytical results show that the scheme is stable and efficient in the sense that both the source rate and bottleneck queue length rapidly converge to a small neighborhood of the designated operating point. We present simulation results which verify the analytical observations. The simulation experiments also demonstrate the superiority of the proposed scheme to the other schemes in dealing with RM-cell RTT and link-bandwidth variations, achieving fairness in both buffer and bandwidth occupancies, and increasing average throughput.
Keywords: Routing & Multicasting
Subhabrata Sen, Don Towsley, Zhi-Li Zhang and Jayanta Dey, "Optimal Multicast Smoothing of Streaming Video over an Internetwork," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: A number of applications such as internet video broadcasts, corporate telecasts, distance learning etc. require transmission of streaming video to multiple simultaneous users across an internetwork. The high bandwidth requirements coupled with the multi-timescale burstiness of compressed video make it a challenging problem to provision network resources for transmitting streaming multimedia. For such applications to become affordable and ubiquitous, it is necessary to develop scalable techniques which can {\em efficiently} deliver streaming video to multiple heterogeneous clients across a heterogeneous internetwork. In this paper, we propose using {\em multicasting of smoothed video} and {\em differential caching} of the video at intermediate nodes in the distribution tree, as techniques for reducing the network bandwidth requirements of such dissemination. We formulate the multicast smoothing problem, and develop an algorithm for computing the set of {\em optimally} smoothed transmission schedules for the tree (such that the transmission schedule along each link in the tree has the lowest peak rate and rate variability for any feasible transmission schedule for that link) given a buffer allocation to the different nodes in the tree. We also develop an algorithm to compute the minimum total buffer allocation to the entire tree and the corresponding allocation to each node, such that feasible transmission is possible to all the clients, when the tree has heterogeneous rate constraints. MPEG-2 trace-driven performance evaluations indicate that there are substantial benefits from multicast smoothing and differential caching. For example, our optimal multicast smoothing can reduce the total transmission bandwidth requirements in the distribution tree by more than a factor of $3$ as compared to multicasting the unsmoothed stream.
Keywords: Multimedia
Norio Matsufuru and Reiji Aibara, "Efficient Fair Queueing for ATM Networks using Uniform Round Robin," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this paper, we investigate scheduling algorithms that are suitable for ATM networks. In ATM networks, all packets have a fixed small length of 53 bytes and they are transmitted at very high rate. Therefore a time complexity of a scheduling algorithm is quite important. Most scheduling algorithms proposed so far have a complexity of O(log N) per packet, where N denotes the number of connections sharing the link. In contrast, weighted round robin(WRR) has the advantage of having O(1) complexity; however, it is known that its delay property gets worse as N increases. To solve this problem, in this paper we propose two new variants of WRR, uniform round robin (URR) and idling uniform round robin (I-URR). Both disciplines provide end-to-end delay and fairness bounds which are independent of N. Complexity of URR, however, slightly increases as N increases, while I-URR has complexity of O(1) per packet. I-URR also works as a traffic shaper, so that it can significantly alleviate congestion on the network. We also introduce a hierarchical WRR discipline (H-WRR) which consists of different WRR servers using I-URR as the root server. H-WRR efficiently accommodates both guaranteed and best-effort connections, while maintaining O(1) complexity per packet. If several connections are reserving the same bandwidth, their delay bounds achieved by H-WRR are close to those of weighted fair queueing.
Keywords: Atm
Zhenyu Tang and J. J. Garcia-Luna-Aceves, "Hop-Reservation Multiple Access (HRMA) for Ad-Hoc Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: A new multichannel MAC protocol called Hop-Reservation Multiple Access (HRMA) for wireless ad-hoc networks (multi-hop packet radio networks) is introduced, specified and analyzed. HRMA is based on simple half-duplex, very-slow frequency-hopping spread spectrum (FHSS) radios and takes advantage of the time synchronization necessary for frequency hopping. HRMA allows a pair of communicating nodes to reserve a frequency hop using a reservation and handshake mechanism that guarantee collision-free data transmission in the presence of hidden terminals. We analyze the throughput achieved in HRMA for the case of a hypercube network topology assuming variable-length packets, and compare it against the multichannel slotted ALOHA protocol, which represents the current practice of MAC protocols in commercial ad-hoc networks based on spread spectrum radios, such as Metricom's Ricochet system. The numerical results show that HRMA can achieve much higher throughput than multichannel slotted ALOHA within the traffic-load ranges of interest, especially when the average packet length is large compared to the duration of a dwell time in the frequency hopping sequence, in which case the maximum throughput of HRMA is close to the maximum possible value.
Keywords: Wireless
S. Ramamurthy and Biswanath Mukherjee, "Survivable WDM Mesh Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This investigation considers optical networks which employ wavelength cross-connects that enable the establishment of wavelength-division-multiplexed (WDM) channels, between node-pairs. In such and other networks, the failure of network elements (e.g., fiber links, cross-connects, etc.) may cause the failure of several optical channels, thereby leading to large data losses. This study examines different approaches to protect mesh-based WDM optical networks from single-link failures. In particular, it examines 1+1 protection, path restoration, and link restoration. In 1+1 protection, for each connection, a link-disjoint backup path is determined and spare channels are reserved and wavelength cross-connects are configured at the time of connection setup (and prior to any failures). In restoration-based approaches, when a failure occurs, backup paths and wavelengths are discovered dynamically from the available spare capacity in the network. First, we examine the capacity requirements to protect a static set of connections for each of the above schemes. We find that, for two representative network topologies, and for random traffic demands, path restoration provides about 20\% improvement in capacity requirements over 1+1 protection, and about 10\% improvement over link restoration. We propose distributed control algorithms for link- and path-restoration. Numerical results obtained by simulating these protocols indicate that, for a representative network topology, at a certain load, (when the blocking probability of the network is about $10^\{-6\}$), and averaged over all single-link failures, about 69\% of connections are successfully restored with path restoration, and about 54\% are successfully restored with link restoration.
Keywords: Optical
Injong Rhee, Nallathambi Balaguru and Goerge Rouskas, "MTCP: Scalable TCP-like Congestion Control for Reliable Multicast," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We present MTCP, a congestion control scheme for large-scale reliable multicast. Congestion control for reliable multicast is important, because of its wide applications in multimedia and collaborative computing, yet nontrivial, because of the potentially large number of receivers involved. Many schemes have been proposed to handle the recovery of lost packets in a scalable manner, but there is little work on the design and implementation of congestion control schemes for reliable multicast. We propose new techniques that can effectively handle instances of congestion occurring simultaneously at various parts of a multicast tree. Our protocol incorporates several novel features: (1) hierarchical congestion status reports that distribute the load of processing feedback from all receivers across the multicast group, (2) the relative time delay (RTD) concept which overcomes the difficulty of estimating round-trip times in tree-based multicast environments, (3) window-based control that prevents the sender from transmitting faster than packets leave the bottleneck link on the multicast path through which the sender's traffic flows, (4) a retransmission window that regulates the flow of repair packets to prevent local recovery from causing congestion, and (5) a selective acknowledgment scheme that prevents independent (i.e., non-congestion-related) packet loss from reducing the sender's transmission rate. We have implemented MTCP both on UDP in SunOS 5.6 and on the simulator ns, and we have conducted extensive Internet experiments and simulation to test the scalability and inter-fairness properties of the protocol. The encouraging results we have obtained support our confidence that TCP-like congestion control for large-scale reliable multicast is within our grasp.
Keywords: Routing & Multicasting
Gustavo De Veciana, Tae-Jin Lee and Takis Konstantopoulos, "Stability and Performance Analysis of Networks Supporting Services with Rate Control-Could the Internet be Unstable?," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We consider the stability and performance of a model for networks supporting services that adapt their transmission rate to the available bandwidth. Not unlike real networks, in our model connection arrivals are stochastic and have a random amount of data to send, so the number of connections in the system changes over time. In turn the bandwidth allocated to, or throughput achieved by, a given connection, may change during its lifetime due to feedback control mechanisms that react to congestion and thus implicitly to the number of ongoing connections. Ideally, for a fixed number of connections, such mechanisms reach an equilibrium typically characterized in terms of its `fairness' in allocating bandwidth to users, e.g. max-min or proportionally fair. In this paper we prove the stability of such networks when the offered load on each link does not exceed its capacity. We use simulation to investigate the performance, in terms of average connection delays, for various network topologies and fairness criteria. Finally we pose an architectural problem in TCP/IP's decoupling of the transport and network layer from the point of view of guaranteeing connection level stability, which we claim may explain congestion phenomena on the Internet.
Keywords: Performance analysis and modeling
Vincent Fayet, Denis A. Khotimsky and Antoni Przygienda, "Hop-by-Hop Routing with Node-Dependent Topology Information," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper is focused on the problem of hop-by-hop routing in a network where different nodes have different views of the network topology. In particular, each node may be aware of just a subset of the network links, perceiving the rest as if their cost was infinite. We formalize the idea of node's individual view of the network with the concept of \{\em visibility sets\} and introduce a routing approach based on the notion of a \{\em feasible path\}, i.e., such path in the node's visibility set that satisfies certain specified restrictions. It is shown that, in a network with general visibility sets, forwarding the packet along an optimal feasible path is \{\em necessary and sufficient\} to guarantee its eventual delivery to destination without being dropped or routed to the same node twice. Based on the proposed approach, we derive the precise routing policy and formulate an efficient algorithm to search for a family of one-to-all optimal feasible paths in a network with embedded visibility sets. We then proceed to prove the correctness of the algorithm. The new routing method provides for execution of multiple dynamic routing protocols, possibly overlaying each other in the same address space, within a network with common kinds of metrics of arbitrary complexity. It solves the problem of interoperability when new metrics or novel link properties are being introduced and eliminates the necessity to run different protocols and protocol versions within disjoint routing domains.
Keywords: Routing & Multicasting
Guido Appenzeller, Mema Roussopoulos and Mary Baker, "User-Friendly Access Control for Public Network Ports," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We are facing a growing user demand for ubiquitous Internet access. As a result, network ports are becoming common in public spaces within buildings such as lounges, conference rooms and lecture halls. This introduces the problem of protecting these public ports from unauthorized use. In this paper, we study the problem of access control for public network ports. We view this problem as a special case of the more general problem of access control for a service on a network. We present an access control model on which we base our solution. This model has three components: authentication, authorization, and access verification. We describe the design and implementation of a system that allows secure network access through public network ports. Our design requires no special hardware or custom client software, resulting in minimal deployment cost and maintenance overhead. Our system has a user-friendly, web-based interface, offers good security, and scales to a campus-sized community.
Keywords: Network Management and security
Eyal Felstaine, Reuven Cohen and Ofer Hadar, "Crankback Prediction in Hierarchical ATM networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: When an ATM node discovers that it cannot continue the setup of a virtual channel under the requested QoS, it initiates a back-tracking procedure called ``crankback''. We propose a novel scheme, refered to as crankback prediction, that decreases the crankback overhead. Under the proposed scheme, nodes check during the connection admission control procedure whether the establishment of a virtual channel has a good chance to be admitted over the entire designated route. If this is not the case, crankback is initiated even before a certain QoS parameter is exceeded. The main idea behind the proposed scheme is to allocate a ``quota'' to the PGs along the message path, and then to sub-allocate this quota to the son PGs of these PGs. This process continues recursively until reaching the $1$-level PG, that contains only physical nodes. The main advantage of the proposed scheme is that it lowers the setup delay and the processing and communication load imposed by signaling messages that establish unused portions of VCs.
Keywords: Routing & Multicasting
Aniruddha Gokhale and Douglas Schmidt, "Techniques for Optimizing CORBA Middleware for Distributed Embedded Systems," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: The distributed embedded systems industry is poised to leverage emerging real-time operating systems, such as Inferno, Windows CE2.0, and PalmOS, to support mobile communications applications. Advances in off-the-shelf real-time operating systems provides an enabling framework for a wide range of mobile communication applications, such as electronic mail, Internet browsing, and network management. Ideally, these applications can be developed using standard middleware components like CORBA to improve their quality and reduce their cost and cycle time. However, stringent constraints on the available memory in embedded systems imposes a severe limit on the footprint of the middleware. This paper provides three contributions to the study and design of small footprint, real-time CORBA middleware. First, we describe optimizations used to develop the protocol engine and the CORBA IDL compiler provided by TAO, which is our real-time CORBA implementation. TAO's IDL compiler produces stubs and skeletons that can use either compiled and/or interpretive marshaling. Second, we compare the performance and footprint of TAO IDL compiler-generated stubs and skeletons for a wide range of IDL data types. Third, we illustrate the benefits of the small footprint and efficiency of TAO IDL compiler-generated stubs and skeletons for a range of standard CORBA services implemented using TAO. Our results comparing the performance of the compiled and interpretive stubs and skeletons indicate that the interpretive stubs and skeletons perform between 75-100% of the compiled stubs and skeletons for a wide range of data types. On the other hand, the code sizes for the interpreted stubs and skeletons were between 26-45% and 50-80% of the compiled stubs and skeletons, respectively. These results indicate a positive step towards implementing high performance, small footprint middleware for distributed embedded systems.
Keywords: Communications protocols and software
Jean-Chrysostome Bolot, Sacha Fosse-Parisis and Don Towsley, "Adaptive FEC-Based Error Control for Interactive Audio in the
Internet," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Excessive packet loss rates can dramatically decrease the audio quality perceived by users of Internet telephony applications. Recent results suggest that error control schemes using forward error correction (FEC) are good candidates for decreasing the impact of packet loss on audio quality. With FEC schemes, redundant information is transmitted along with the original information so that the lost original data can be recovered at least in part from the redundant information. Clearly, sending additional redundancy increases the probability of recovering lost packets, but it also increases the bandwidth requirements and thus the loss rate of the audio stream. This means that the FEC scheme must be coupled to a rate control scheme. Furthermore, the amount of redundant information used at any given point in time should also depend on the characteristics of the loss process at that time (it would make no sense to send much redundant information when the channel is loss free), on the end to end delay constraints (destination typically have to wait longer to decode the FEC as more FEC information is used), on the quality of the redundant information, etc. However, it is not clear how to choose the ``best'' possible redundant information given all the constraints mentioned above. We address this issue in the paper, and illustrate our approach using a FEC scheme for packet audio recently standardized in the IETF. We find that the problem best redundant information can be expressed mathematically as a constrained optimization problem for which we give explicit solutions. We obtain from these solutions a simple algorithm with very interesting features: i) it optimizes a subjective measure of quality (such as the perceived audio quality at a destination) as opposed to a non subjective measure (such as the packet loss rate at a destination), ii) it incorporates the constraints of rate control and playout delay adjustment schemes, and iii) it adapts to varying (and estimated on line with RTCP) loss conditions in the network. We have been using the algorithm, together with a TCP-friendly rate control scheme, for a few months now and we have found it to provide very good audio quality even with high and varying loss rates. We present simulation and experimental results to illustrate its performance.
Keywords: Internet and experimental systems
Hoon Tong Ngin, Chen Khong Tham and Wee Seng Soh, "Generalised Minimum Queuing Delay: An Adaptive Multi-rate Service Discipline for ATM Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this paper, we propose a generalised minimum queuing delay (GMQD) service discipline for high speed networks, mainly asynchronous transfer mode (ATM) networks. This proposed scheme is similar to service disciplines based on fair queuing, but instead of using only a single service rate for each session for its entire connection lifetime, multiple service rates are used. The service rate of any session at any point in time is computed efficiently based on the number of bits backlogged in the queues of the session and another imaginary reference session at that point in time. The main advantage of this scheme is that the queuing delays suffered by all the sessions connected to a single output node are minimised, leading to a smaller cell delay variation. In addition, this smaller cell delay variation also implies a smaller variance in the maximum queue length, thereby, reducing the possibility of buffer overflow. Keywords: ATM, scheduling, multi-rate service disciplines
Keywords: Traffic management; scheduling
Wei K. Tsai and Yuseok Kim, "Re-Examining Maxmin Protocols: A Fundamental Study on Convergence, Complexity, Variations, and Performance," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Maxmin protocols are an importance class of rate-based flow control for ABR (best-effort connection-oriented) traffic in the integrated service networks. However, most maxmin protocols do not converge to maxmin optimality and global convergence and complexity results are quite difficult to prove. This paper studies maxmin protocols in four aspects: convergence, complexity, variations, and performance. Firstly, the concept of ''pseudo-saturation'' is introduced and it is shown that most protocols do not properly handle the pseudo-saturation cases, and as a result, they do not converge to true maxmin optimality. Secondly, the concept of ''constraint precedence graph (CPG)'' is introduced and is used to define the best possible complexity of any maxmin protocol. The existing complexity estimates do not consider possible concurrent operations and therefore is overly conservative while the CPG analysis shows the benefit of parallelization. Thirdly, the concept of ``constraint'' is generalized and this generalization leads to simple modification of existing protocols to compute maxmin rates when the sources have non-zero minimum cell rate (MCR) requirements. Finally, it is shown using simulations that the complexity analysis is inadequate to gauge protocol performance. A new analysis based on protocol dynamics is called for to understand the performance.
Keywords: Congestion control
Laurent Massoulie and Jim Roberts, "Bandwidth Sharing: Objectives and Algorithms," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper concerns the design of distributed algorithms for sharing network bandwidth resources among contending flows. The classical fairness notion is the so-called max-min fairness; F. Kelly [8] has recently introduced the alternative proportional fairness criterion; we introduce a third criterion, which is naturally interpreted in terms of the delays experienced by ongoing transfers. We prove that fixed size window control can achieve fair bandwidth sharing according to any of these criteria, provided scheduling at each link is performed in an appropriate manner. We next consider a distributed random scheme where each traffic source varies its sending rate randomly, based on binary feedback information from the network. We show how to select the source behaviour so as to achieve an equilibrium distribution concentrated around the considered fair rate allocations. This stochastic analysis is then used to assess the asymptotic behaviour of deterministic rate adaption procedures.
Keywords: Traffic management; scheduling
Richard Draves, Christopher King, Srinivasan Venkatachary and Brian Zill, "Constructing Optimal IP Routing Tables," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: The Border Gateway Protocol (BGP) populates Internet backbone routers with {\it routes} or {\it prefixes}. We present an algorithm to locally compute (without any modification to BGP) equivalent forwarding tables that provably contain the minimal number of prefixes. For large backbone routers, the Optimal Routing Table Constructor (ORTC) algorithm that we present produces routing tables with roughly 60\% of the original number of prefixes. The publicly available MaeEast database with 41315 prefixes reduces to 23007 prefixes when ORTC is applied. We present performance measurements on four publicly available databases and a formal proof that ORTC does produce the optimal set of routes.
Keywords: Routing & Multicasting
Amotz Bar-Noy and Yaron Shilo, "Optimal Broadcasting of Two Files over an Asymmetric Link," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We study the problem of scheduling files over a broadcast channel in an asymmetric environment. The goal is to minimize the mean response time for clients who access the broadcast channel. Asymmetric channels gained a lot of attention since they are used to model wireless communication, Teletext systems, and web caching in satellite systems. This paper addresses the 2-files case. We design a simple algorithm that defines the optimal schedule given the demand probability for each file. Our solution is extended to include other important factors, such as dependencies between files, variable-length files, and different priorities for the clients. Adding dependencies is important in the web caching environment since clients may wish to access more than one file in the broadcast channel. For all the above extensions, we prove the surprising result that there exists a simple optimal schedule. Such a schedule is composed of a repeated pattern of AA...AB where A is the more ``popular'' file and B is the less ``popular'' file.
Keywords: Traffic management; scheduling
Anthony Lauck, Charles Kalmanek and K. K. Ramakrishnan, "SUBMARINE: An Architecture for IP Routing over Large NBMA Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: As communications networks grow in both speed and scale, there is a need to switch packets at higher speeds. One approach is to use fast switches that operate at the datalink layer (layer 2) to build a high-performance ``cloud'' for interconnecting network layer routers. The use of ATM for the layer 2 network provides a number of advantages when the network is shared among multiple services and when additional capabilities that are supported well at layer 2, such as fine-grained per-flow QoS, are needed. This paper describes a robust and efficient solution to the problem of supporting IP over a large non-broadcast multiple-access (NBMA) network, such as ATM. Our solution, known as SUBMARINE, calculates loop-free shortcut routes across the NBMA network. SUBMARINE builds on existing IP routing protocols, is designed to scale to multiple areas within a single Autonomous System, and makes minimal changes to the IP forwarding process.
Keywords: Routing & Multicasting
Shiwen Chen, Bulent Yener and Yoram Ofek, "Performance Trade-offs in Reliable Group Multicast Protocols," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper presents an extensive performance study in order to identify some tradeoffs between tree-based and ring-based reliable group multicast protocols. The motivation for such a study is the following observation. In communications network routing from one node to another over a tree embedded in the network is intuitively a good strategy, since it typically results in route length of O(lg$n$) links, while routing from one node to another over a ring embedded in the network would result in route length of O($n$) links. However, in a group multicast (many-to-many) the overall number of links traversed by each packet for both tree and ring embedding is typically O($n$), so both approaches have similar communication requirements. In reliable group multicast protocols the traffic pattern is complex, since packets are sent from a multicast source to the multiple destinations, and then some control packets are sent back to the source, and this can result in resending of some of the original packets. Consequently, determining under what condition the tree-based approach is better than ring-based approach is not obvious. The key criteria for evaluating the performance of a reliable group multicast protocol is $(i)$ how many successful multicast were achieved per unit time, and $(ii)$ what is the efficiency of the multicast, namely, the ratio between the number of successful transmission and the total number of packets that were transmitted. Under the above criteria it is shown that the ring-based multicast often performs better than the tree-based multicast. One of the main reasons for this result is that ring-based multicast is window-based with simple and effective management of acknowledgments and retransmissions, while the tree-base is rate-based with complex and slow management of acknowledgments and retransmissions.
Keywords: Routing & Multicasting
Anwar Elwalid and Debasis Mitra, "Design of Generalized Processor Sharing Schedulers Which Statistically Multiplex Heterogeneous QoS," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Generalized Processor Sharing (GPS) is the basis for the packet scheduler of choice in IP routers and ATM switches of the future. The currently accepted approach for the design of GPS schedulers is based on deterministic QoS guarantees, which,it is generally accepted, is overly conservative and leads to limitations on capacity. To address this problem we develop a framework for GPS scheduling which is based on statistical QoS guarantees and statistical multiplexing. We give the design of GPS weights which maximize the coverage of operating points,and also the design of the connection admission control (CAC). The general framework is end-to-end, with two heterogeneous QoS classes coexisting with a third, best effort class. Each QoS class has a specified delay bound together with a bound on the probability of its violation. An important objective is to maximize the bandwidth available to best effort traffic while just satisfying the guarantees of the QoS classes. To this end, we consider output regulated GPS scheduling which has the additional feature of limiting each connection's share of the bandwidth to a specified value, a design parameter which is determined by our analysis. The sources are subject to standard dual leaky bucket regulation. For the design of the GPS weights we give procedures based on two key concepts, the realizable set and the critical weights.The realizable set is the union of all admissible sets of connections of both classes over all weights. One of the main contributions is a pragmatic design process by which most of the realizable set is realized by two critical weights. In the benign case, the system is ``Effectively Homogeneous'' and a single GPS weight suffices, while in the complementary ``Effectively Non-Homogeneous'' case it is necessary to switch between the critical weights. The numerical results, which are for a single node with a wide range of traffic and QoS parameters, validate the design procedure and also show that there are substantial capacity gains from statistical multiplexing.
Keywords: Traffic management; scheduling
Alexander Stolyar and K. K. Ramakrishnan, "The Stability of a Flow Merge Point with Non-Interleaving Cut-Through Scheduling Discipline," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Cut-through switching has been used as a way to reduce network latency. With cut-through, if packets are broken up into fixed length subunits (such as cells in ATM), each subunit is forwarded by a switch without waiting for the remaining subunits of the packet. However, when multiple input flows are merged into a single output flow, it is a critical requirement to not interleave the subunits (cells) of a packet with those of another. The process of VC-merging to support multicast (multipoint to multipoint or multipoint to point) in ATM (and more generally with destination-based forwarding in Multi-Protocol Layer Switching) depends on the ability of switches to support such merging. We examine how to maintain cut-through switching at a merge point while satisfying the non-interleaving requirement. We show that a simple round-robin polling discipline may make the merge point unstable. Instability means that the input queues have a tendency to build up infinitely even though the total input data rate is less than the output link capacity. We show that the round-robin discipline is stable if the merge point is symmetric in that packet rates of all input flows are equal (or at least ``almost equal''). We also prove that two simple modifications of the round-robin discipline make the merge point always stable. The latter disciplines are good candidates for the practical implementation of cut-through switching with VC-merging.
Keywords: Switching
Roch Guerin, Liang Li, Steve Nadas, Ping Pan and Vinod Peris, "The Cost of QoS Support in Edge Devices: An Experimental Study," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper investigates the problem of making QoS guarantees available in access devices such as edge routers, that are commonly deployed in today's IP networks. The introduction of new capabilities such as QoS needs to take place, at least initially, within the constraints imposed by the limitations and the architecture of these existing systems. It is, therefore, important to identify possible solutions that can deliver the desired functional enhancements without impacting performance or requiring major upgrades. In this paper, we propose a specific design approach which we explore by carrying out a complete implementation, whose performance we then evaluate in the context of an experimental testbed. The results of our experiments indicate that a reasonable level of service differentiation, i.e., rate and delay guarantees, can be provided with a minimal impact on the raw packet forwarding performance of edge devices. This provides some initial evidences that as the Internet backbone is upgraded to support QoS guarantees, a similar and necessary enhancement can also be implemented rapidly and effectively at the edge of the backbone.
Keywords: Internet and experimental systems
Amit Kulkarni and Gary Minden, "Active Networking Services for Wired/Wireless Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: An active networking architecture provides the infrastructure for applications to inject user programs into the nodes of the network. This enables customization of the network so that application-specific services can be downloaded into the network in the form of new protocols. In this paper, we look at different kinds of services that applications require from the network. We study these services to identify common characteristics so that services can be grouped into classes of protocols. We argue that this study permits us to develop a methodology that helps in rapidly designing and deploying new protocols.
Keywords: Network Management and security
Jing-yu Qiu and Edward Knightly, "Inter-Class Resource Sharing using Statistical Service Envelopes," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Networks that support multiple services through ``link-sharing'' must address the fundamental conflicting requirement between \emph{isolation} among service classes to satisfy each class' quality of service requirements, and statistical \emph{sharing} of resources for efficient network utilization. While a number of service disciplines have been devised which provide mechanisms to both isolate flows and fairly share excess capacity, admission control algorithms are needed which exploit the effects of inter-class resource sharing. In this paper, we develop a framework of using \emph{statistical service envelopes} to study inter-class statistical resource sharing. We show how this service envelope enables a class to over-book resources beyond its deterministically guaranteed capacity by statistically characterizing the excess service available due to fluctuating demands of other service classes. We apply our techniques to several multi-class schedulers, including Generalized Processor Sharing, and design new admission control algorithms for multi-class link-sharing environments. We quantify the utilization gains of our approach with a set of experiments using long traces of compressed video.
Keywords: Traffic management; scheduling
Prasun Sinha, Raghupathy Sivakumar and Vaduvur Bharghavan, "CEDAR: a Core-Extraction Distributed Ad hoc Routing algorithm," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this paper, we present CEDAR, a Core-Extraction Distributed Ad hoc Routing algorithm for QoS routing in ad hoc network environments. CEDAR has three key components: (a) the establishment and maintenance of a self-organizing routing infrastructure called the core for performing route computations, (b) the propagation of the link-state of stable high-bandwidth links in the core through increase/decrease waves, and (c) a QoS route computation algorithm that is executed at the core nodes using only locally available state. Our performance evaluations show that CEDAR is a robust and adaptive QoS routing algorithm that reacts quickly and effectively to the dynamics of the network while still approximating link-state performance for stable networks.
Keywords: Routing & Multicasting
Junyi Li, Ness Shroff and Edwin Chong, "Sharing Scheme in Wireless Cellular Networks including Handoffs," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Enhancing system capacity while maintaining quality of service is an important issue in wireless cellular networks. In this paper, we present a localized channel sharing scheme to address this problem. Our basic idea is to allow channels to be shared between adjacent cells at the expense of a smaller initial allocation of channels per cell. We show that this tradeoff results in a better utilization of network resources. We further propose a fixed channel assignment scheme to maximize channel reuse efficiency while allowing channel sharing. We show that our sharing scheme can also facilitate handoff processing. An important feature of our sharing scheme is that channel management is localized between adjacent cells, and no global coordination or optimization is required, thus making it suitable for implementation. We provide numerical results comparing our scheme with the traditional channel assignment and handoff techniques. We find that our scheme improves system capacity over a wide range of traffic parameters and a variety of quality of service requirements.
Keywords: Wireless
Omar Ait-Hellal and Eitan Altman, "Performance Evaluation of Congestion Phenomenain the Rate Based Flow Control Mechanism for ABR," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this paper we investigate the performances of the EFCI-based (Explicit Forward Congestion Indication) and ER-based (Explicit Rate) algorithms for the rate-based flow control of the ABR (Available Bit Rate) traffic in an ATM network. We consider the case of multiple switches in tandem. We present several definitions of a bottleneck, and provide conditions that determine which queue is the bottleneck. We show that it is not necessarily the queue with the slowest transmission rate that is ``responsible'' for a bottleneck. We derive analytic formulas for the maximum queue length. We compare our results to those obtained by approximating a network by a simpler one, containing only the bottleneck switch. We show that the maximum queue lengths under the approximating approach may largely underestimate the ones obtained in the real network.
Keywords: Congestion control
Shizhao Li and Nirwan Ansari, "Input-Queued Switching with QoS Guarantees," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Input-queued switching architecture is becoming an attractive alternative for de signing very high speed switches owing to its scalability. Tremendous efforts ha ve been made to overcome the throughput problem caused by contentions occurred a t the input and output sides of the switches. However, no QoS guarantees can be provided by the current input-queued switch design. In this paper, a frame based scheduling algorithm, referred to as Store-Sort-and -Forward (SSF), is proposed to provide QoS guarantees for input-queued swi tches without requiring speedup. SSF uses a framing strategy in which the time axis is divided into constant-length frames, each made up of an integer mul tiple of time slots. Cells arrived during a frame are first held in the input b uffers, and are then ``sorted-and-transmitted'' within the next frame. A bandwid th allocation strategy and a cell admission policy are adopted to regulate the t raffic to conform to the (r,T) traffic model. A strict sense 100% throughp ut is proved to be achievable by rearranging the cell transmission orders in eac h input buffer, and a sorting algorithm is proposed to order the cell transmissi on. The SSF algorithm guarantees bounded end-to-end delay and delay jitter. It i s proved that a perfect matching can be achieved within N(ln N +O(1)) effect ive moves.
Keywords: Traffic management; scheduling
Yuhong Zhu, George Rouskas and Harry Perros, "Blocking in Wavelength Routing Networks, Part I: The Single Path Case," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We study a class of circuit-switched wavelength routing networks with and without wavelength converters, and we present the first part of a new analytical framework to accurately and efficiently evaluate the blocking performance of such networks. Our model is fairly general and it allows non-uniform traffic, i.e., call request arrival rates and call holding times can vary with the source-destination pair. It also accounts for the correlation among the loads at all links in a path, and it can be used when the location of converters is fixed but arbitrary. We first construct an exact Markov process that captures the behavior of a path in terms of wavelength use. We also obtain an approximate Markov process which has a closed-form solution that can be efficiently computed for short paths. We then develop an iterative algorithm to analyze approximately arbitrarily long paths. The algorithm decomposes a path into shorter segments which are then studied in isolation using the corresponding approximate Markov process. The individual solutions are appropriately combined to obtain a solution for the original path. Finally, we demonstrate how our analytical techniques can be used to gain insight into the problem of converter placement in wavelength routing networks.
Keywords: Optical
K. R. Venugopal, M. Shiva kumar and P. Sreenivasa Kumar, "A Heuristic for Placement of Limited Range Wavelength Converters in All-Optical Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Wavelength routed optical networks have emerged as a technology that can effectively utilize the enormous bandwidth of the optical fiber.Wavelength converters play an important role in enhancing the fiber utilization and reducing the overall call blocking probability of the network. As the distortion of the optical signal increases with the increase in the range of wavelength conversion in optical wavelength converters, limited range wavelength conversion assumes importance. Placement of wavelength converters is a NP complete problem in an arbitrary mesh network. In this paper, we investigate heuristics for placing limited range wavelength converters in arbitrary mesh wavelength routed optical networks. The objective is to achieve near optimal placement of limited range wavelength converters resulting in reducing blocking probabilities and low distortion of the optical signal. The proposed heuristic is to place limited range wavelength converters at the most congested nodes, nodes which lie on the long lightpaths and nodes where conversion of optical signals is significantly high. We observe that limited range converters at few nodes can provide almost the entire improvement in the blocking probability as the full range wavelength converters placed at all the nodes. Congestion control in the network is brought about by dynamically adjusting the weights of the channels in the link thereby balancing the load and reducing the average delay of the traffic in the entire network. Simulations have been carried out on a 12-node ring network, 14-node NSFNET, 19-node EON, 28-node US long haul network, 30-node INET network and the results agree with the analysis.
Keywords: Optical
Sylvia Ratnasamy and Steven McCanne, "Inference of Multicast Routing Trees and Bottleneck Bandwidths using End-to-end Measurements," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: The efficacy of end-to-end multicast transport protocols depends critically upon their ability to scale efficiently to a large number of receivers. Several research multicast protocols attempt to achieve this high scalability by identifying sets of co-located receivers in order to enhance loss recovery, congestion control and so forth. A number of these schemes could be enhanced and simplified by some level of explicit knowledge of the topology of the multicast distribution tree, the value of the bottleneck bandwidth along the path between the source and each individual receiver and the approximate location of the bottlenecks in the tree. In this paper, we explore the problem of inferring the internal structure of a multicast distribution tree using only observations made at the end hosts. By noting correlations of loss patterns across the receiver set and by measuring how the network perturbs the fine-grained timing structure of the packets sent from the source, we can determine both the underyling multicast tree structure as well as the bottleneck bandwidths. Our simulations show that the algorithm is robust and appears to converge to the correct tree with high probability.
Keywords: Routing & Multicasting
Hiroshi Saito, "Performance Evaluation and Dimensioning for AAL2 CLAD," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: ATM traffic Analysis
Keywords: Atm
Ben Liang and Zygmunt Haas, "Predictive Distance-Based Mobility Management for PCS Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper presents a mobile tracking scheme that exploits the predictability of user mobility patterns in wireless PCS networks. Instead of the constant velocity fluid-flow or the random-walk mobility model, a more realistic Gauss-Markov model is introduced, where a mobile's velocity is correlated in time to a various degree. Based on the Gauss-Markov model, a mobile's future location is predicted by the network based on the information gathered from the mobile's last report of location and velocity. When a call is made, the network pages the destination mobile at and around the predicted location of the mobile and in the order of descending probability until the mobile is found. A mobile shares the same prediction information with the network and reports its new location whenever it reaches some threshold distance away from the predicted location. We describe an analytical framework to evaluate the cost of mobility management for the proposed predictive distance-based scheme. We then compare this cost against that of the regular, non-predictive distance-based scheme, which is obtained through simulations. Performance advantage of the proposed scheme is demonstrated under various mobility and call patterns, update cost, page cost, and frequencies of mobile location inspections.
Keywords: Performance analysis and modeling
Timothy Brown, "Classifying Loss Rates in Broadband Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Tasks such as admission control in ATM and predicting overload conditions in telephone networks require a function that specifies what conditions will result in loss rates exceeding a threshold, p*. This paper considers the formal task of deriving such a classification function based on samples at different conditions. When the size of these samples is small relative to 1/p*, previously proposed methods incorrectly classify conditions that surpass the threshold by orders of magnitude. This paper derives general conditions for consistent and robust classifiers and presents specific methods that meet these conditions. The paper analyzes the methods with respect to asymptotic and finite sample behavior and the results are confirmed using simulated data.
Keywords: Multimedia
Yael Dubinsky and Adrian Segall, "A Flexible Rerouting Protocol in ATM networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: The paper introduces a protocol for rerouting calls in an ATM network, referred to as the Flexible Rerouting Protocol (FRP). Failure of a VP triggers construction of an alternate VP out of VP's that are not in use, named stand-by VP's, by simple operations at the endpoints of the stand-by VP's. VC rerouting from the failed VP to the alternate VP is performed concurrently. FRP is designed to also allow recovery from repeated failures that may occur during the construction and rerouting process.
Keywords: Atm
Debasis Mitra, John A. Morrison and K. G. Ramakrishnan, "Virtual Private Networks: Joint Resource Allocation And Routing Design," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We consider the resource allocation problem in the design of intranets or virtual private networks (VPNs) that is faced by a service provider, which has service level agreements with various customers to carry their multiservice traffic. The design allocates bandwidth on each link to the VPNs such that, when the traffic of a customer is optimally routed over its VPN, a weighted aggregate measure of carried bandwidth over the service provider's infrastructure is maximized, subject to constraints that each VPN carries a specified minimum. Thus, this is a joint resource allocation and traffic routing problem. Multiplexing is across services and routes within each VPN, but not across VPNs, the latter in the interest of QoS protection. The traffic modelling is at the flow or call level, with random arrivals and holding times of calls and each call requiring (effective) bandwidth, which is characteristic of the call's service type, on all links in its route. The network is modelled as a multirate loss network. Scalability of the design process, i.e., the ability to handle OC3 and higher rates, is an important contribution, and this is achieved by the systematic use of asymptotic techniques, specifically a Refined Uniform Asymptotic Approximation. Our software package VPN DESIGNER incorporates these results. We report on numerical results for problems with up to 8 VPNs on a network with 8 nodes, 24 OC3 links, 6 services and up to 640 routes.
Keywords: Traffic management; scheduling
Prashant Chandra, Allan Fisher and Peter Steenkiste, "A Signaling Protocol for Structured Resource Allocation," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: There is an emerging class of multi-party, multimedia, multi-flow applications that have a high-level structure that imposes dependencies between resource allocations for flows within the application. These applications are also capable of making intelligent decisions on how resource allocation should be controlled within the application. The development of such applications places new requirements on signaling protocols. This paper outlines these new requirements, discusses ways in which they can be supported and presents the design and implementation of an experimental signaling protocol that supports these requirements. This paper makes the case that for these structured applications, there is an advantage to allocating the resources in an integrated fashion, i.e computation, storage and communication resources for all the flows are allocated at the same time in a coordinated fashion. The concept of a virtual mesh is introduced as a key abstraction that encapsulates the set of resources that are allocated and managed in an integrated fashion to meet the needs of applications. The paper presents two mesh setup algorithms and a performance evaluation comparing them. Temporal resource sharing within the virtual mesh is discussed in detail and signaling support for temporal sharing at setup and runtime is examined. It is important to characterize temporal sharing since it can significantly reduce the resource requirements for applications. We have implemented the Beagle signaling protocol that supports this integrated resource management model. Beagle representations and mechanisms for mesh setup and temporal sharing are described and a prototype implementation is presented.
Keywords: Communications protocols and software
Israel Ben-Shahar, Ariel Orda and Nahum Shimkin, "Best-Effort Resource Sharing by Users with QoS Requirements," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Communication networks typically provide a basic best-effort service category, in which resources are shared by concurrent users. As no QoS guarantees are provided, a user will accept to get best-effort service only if the {\em expected} QoS meets some minimal, user-specific, requirements. This results in an inherent conflict of interest among users, which we model as a {\em dynamic noncooperative game} and investigate its structure and properties. Specifically, we study the operating points of such systems, i.e., their {\em Nash equilibria}. First, we investigate the optimal user strategies, which involve a prediction of the future system state, and show that they are of the threshold type. We then establish that a Nash equilibrium point exists and is unique. An algorithmic scheme for computing the Nash equilibrium is provided. In practice, rather than making complex predictions, users typically employ simple decision rules, based on what they learn by experience. Interestingly, it can be shown that the Nash equilibrium of our considered system is a stationary point of such learning schemes. Moreover, we demonstrate that users employing such schemes converge to the Nash equilibrium. Finally, we briefly discuss the implications of our study on network design and management.
Keywords: Performance analysis and modeling
Wanjiun Liao, "Mobile Internet Telephony: Mobile Extensions to H.323," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Internet telephony realizes the transmission of two-way and real-time traffic over IP-based networks. The dominant standard for Internet telephony is ITU-T Rec. H.323. With the current version of H.323, Internet telephony allows interoperability with circuit-switched telephone, but IP host mobility is not supported. In this paper, mobile extensions to H.323 that enable Internet mobile phone service are proposed. The proposed approach combines the characteristics of both cellular phone system and mobile IP mechanism with Internet telephony, and therefore realizes the transmission of real-time voice traffic for both stationary and mobile hosts over IP-based networks. The most striking feature of the proposed approach is that the complicated mobility management functions are handled by the procedures for dynamically joining and departing from a conference, functions already defined in H.323. Therefore, our approach allows mobility support without the need for additional new entities, and with minimal modifications to existing H.323 standard. Such mobility extensions can serve as an add-on feature for the existing Internet telephony systems compliant to the H.323 standard.
Keywords: Multimedia
Andreas Terzis, Mani Srivastava and Lixia Zhang, "A Simple QoS Signaling Protocol for Mobile Hosts in the Integrated Services Internet," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: With advances in packet routing technology, and resource reservation protocols, the Internet is expected to provide ubiquitous integrated transport of speech, audio, video, and other real-time multimedia data in addition to the current best effort data traffic. Such integrated transport will also need to be supported for the increasing number of mobile users who access the internet over wireless access networks, using Mobile-IP to retain continual IP connectivity. In this paper we present a simple Quality of Service (QoS) signaling protocol for mobile users in an integrated service Internet. The protocol works by combining pre-provisioned RSVP Tunnels (a proposed mechanism for supporting RSVP signaling over IP-in-IP tunnels) with Mobile IP. Our protocol, even-though simple, captures the essence of QoS provisioning for wireless and mobile networks. The wireless medium provides a completely different medium than wires, and therefore one's expectations from it should be different. Service quality is inherently mobility dependent, and intermittent disconnections are bound to happen. It is not the signaling protocol's task to completely overcome or conceal transient conditions from applications, but rather applications should try to adapt. Our approach is a relatively simple solution that can be easily implemented today with minimal changes to other components of the Internet architecture. We also evaluate the application level performance impact of the QoS provisioning delays associated with our protocol on a prototypical packet speech application with various playout buffering strategies, and compare against the performance of the ordinary RSVP protocol suite with Mobile IP.
Keywords: Wireless
Mun Choon Chan and Thomas Woo, "Cache-based Compaction: A New Technique for Optimizing Web Transfer," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Despite the announcements of many new technologies (e.g., cable modem, ADSL), the speed of the last hop will remain a bottleneck for some time to come. This is especially true for the emerging area of wireless access to the Internet. In this paper, we propose and study a new technique, which we call cache-based compaction for reducing the latency of Web browsing over a slow link. Our compaction technique trades computation for bandwidth. The key observation is that an object can be coded in a highly compact form for transfer if similar objects that have been transferred earlier can be used as references. The contributions of this paper are: (1) an efficient selection algorithm for selecting similar objects as references, and (2)an encoding/decoding algorithm that reduces the size of a Web object by exploiting its similarities with the reference objects. We verify the efficacy of our proposal through detailed experimental evaluations. Our compaction technique significantly generalizes previous work on optimizing Web transfer using compression or differencing, and provides a systematic foundation that ties together caching, compression and prefetching.
Keywords: Internet and experimental systems
Ramon Caceres, Nick Duffield, Joseph Horowitz, Don Towsley and Tian Bu, "Multicast-based Inference of Network-internal Characteristics: Accuracy of Packet Loss Estimation," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We explore the use of end-to-end multicast traffic as measurement probes to infer network-internal characteristics. We develop a Maximum Likelihood Estimator for packet loss rates on individual links based on losses observed by multicast receivers. This technique exploits the inherent correlation between such observations to infer the performance of paths between branch points in the multicast tree spanning the probe source and its receivers. We evaluate through analysis and simulation the accuracy of our estimator under a variety of network conditions. In particular, we report on the error between inferred loss rates and actual loss rates as we vary the network topology, propagation delay, packet drop policy, background traffic mix, and probe traffic type. In all but one case, estimated losses and probe losses agree to within 2 percent on average. We feel this accuracy is enough to reliably identify congested links in a wide-area internetwork.
Keywords: Internet and experimental systems
Gabor Fodor, Andras Racz and Zoltan Turanyi, "Weighted Fair Early Packet Discard at an ATM Switch Output Port," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this paper we consider an output port of an ATM switch, where cell streams belonging to different TCP and UDP sessions arrive. During congestion the switch applies Early Packet Discard in order to reduce bandwidth waste. In order to guarantee fairness in the sense that only misbehaving sources get affected by the packet drop mechanism and to ensure high server utilization, we propose an algorithm which also features simplicity. A salient feature of this algorithm is that it allows a predefined share to be associated with each stream. The algorithm, Weighted Fair Early Packet Discard, WFEPD, attempts to provide this weighted share of the bandwidth for the streams in the long time average. A sliding window implementation of the WFEPD allows us to demonstrate its efficiency in terms of fairness and bandwidth utilization.
Keywords: Traffic management; scheduling
Junshan Zhang and Edwin K. P. Chong, "CDMA Systems With Random Spreading in Fading Channels: Network Capacity and Power Control," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We study single-cell synchronous CDMA systems equipped with matched filter receivers in fading channels, and identify the network capacity for single-class systems and the network capacity region for multiple-class systems. We find the tightest upper bound of the network capacity over all possible distributions of received powers. We also explore the concepts of effective target SIR and effective bandwidth, which play an important role in determining the admissibility.
Keywords: Wireless
Mario Joa-Ng and I-Tai Lu, "Spread Spectrum Medium Access Protocol with Collision Avoidance in Mobile Ad-hoc Wireless Network," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Spread spectrum techniques and collision avoidance multiple access protocols are combined to form a new set of medium access protocols for mobile wireless ad hoc networks. The Request-to-Send and Clear-to-Send message dialogue solves the ``hidden terminal'' and the ``exposed terminal'' problems and speeds up the retransmission. The spreading code assignment avoids disruption of any ongoing transmission by an intruder. Simulation results confirm that a higher channel throughput is achieved by the new protocols even in a dense network.
Keywords: Wireless
Sanket Nesargi and Ravi Prakash, "Distributed Wireless Channel Allocation in Networks with Mobile Base Stations," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In traditional cellular systems with fixed base stations the channel reuse pattern is static and deterministic. When the cell layout is dynamic, due to the mobility of base stations, the cluster of cells within co-channel interference range changes with time. Consequently, the channel reuse pattern is highly dynamic. Moreover, base stations also need wireless channels to communicate amongst themselves. A communication session between a pair of nodes may have to switch channels due to the movement of other nodes into the neighborhood. Hence, there is a need for new wireless channel allocation algorithms for virtual cellular systems with mobile base stations. In this paper, principles of mutual exclusion pertaining to distributed computing systems are employed to develop such an algorithm. The inter-base station wireless links are referred to as backbone links while the base station-mobile node links are referred to as short-hop links. The proposed algorithm is distributed, dynamic and deadlock free. Disjoint sets of channels are used for backbone and short-hop links. The distributed nature of the channel allocation scheme leads to robustness as the responsibility is no longer centralized at the MTSO. Instead, it is shared among all the mobile base stations. This also makes the algorithm scalable.
Keywords: Wireless
AbdulRahman Aljadhai and Taieb Znati, "A Framework for Call Admission Control and QoS Support in Wireless Environments," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: With the proliferation of wireless networks technologies, mobile users are expected to demand the same quality-of-service (QoS) available to fixed users. This paper presents a framework to support predictive timed-QoS guarantees, in wireless environments. The main components of this framework include a service model for QoS guarantees, a path predictability model, and a call admission control scheme. The unique feature of this framework is the ability to combine the path predictability model with the call admission control to determine the level of predictive timed-QoS guarantees that the network can provide over a predetermined interval of time. The performance of the call admission control scheme, in terms of the dropping ratio of hand-off calls and the blocking ratio of new calls, is presented.
Keywords: Wireless
Wu-chang Feng, Dilip Kandlur, Debanjan Saha and Kang Shin, "A Self-Configuring RED Gateway," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: The congestion control mechanisms used in TCP have been the focus of numerous studies and have undergone a number of enhancements. However, even with these enhancements, TCP connections still experience alarmingly high loss rates, especially during times of congestion. The IETF has addressed this problem by advocating the deployment of active queue management mechanisms, such as RED, in the network. While RED can potentially improve packet loss rates, we show that its effectiveness is highly dependent upon its operating parameters. In fact, in cases where these parameters do not match the requirements of the network load, the performance of the RED gateway can approach that of a traditional drop-tail gateway. To alleviate this problem, we propose and experiment with a self-configuring active queue management mechanism which can significantly reduce loss rates across congested links. When used in the network, this mechanism can effectively reduce packet loss while maintaining high link utilizations under the most difficult scenarios.
Keywords: Congestion control
Tim Daniels and Chris Blondia, "Asymptotic Behavior of a Discrete-Time Queue with Long Range Dependent Input," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this paper we derive an expression for the asymptotics of the buffer length distribution of a discrete-time infinite capacity single server queue with deterministic service time and its input belonging to class of long range dependent M/G/inf arrival processes. For these processes bursts arrive acording to a Poisson process and their durations are Pareto distributed. The exact tail probabilities are derived by using a generating function approach in combination with Tauberian theorems.
Keywords: Performance analysis and modeling
Miquel Oliver-Riera and Joan Borràs-Chia, "Performance Evaluation of Variable Reservation Policies for Hand-off Prioritization in Mobile Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this article we propose a variable reservation scheme for cellular networks, based on prioritization of hand-off calls in front of new calls. This problem has been extensively studied in the literature, and several schemes consisting on call-requests queuing, fixed reservation of channels or combinations of both have been proposed. In this paper we take advantage of the information reported by the mobile terminal to adaptively establish the number of channels to be reserved in the target cell. The effect of progressive channel degradation in the overlapping zone between cells is also taken into account. Performance evaluation is done using infinite bidimensional Markov chains. A noticeable improvement in blocking and call-dropping probabilities is achieved using this new mechanism.
Keywords: Wireless
Ran Canetti, Juan Garay, Gene Itkis, Daniele Micciancio, Moni Naor and Benny Pinkas, "Multicast Security: A Taxonomy and Efficient Constructions," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Multicast communication is becoming the basis for a growing number of applications. It is therefore critical to provide founded security mechanisms for multicast communication. Yet, existing security protocols for multicast offer only very partial solutions. We first present a taxonomy of multicast scenarios on the Internet and point out the relevant security concerns. Next we identify two major security problems of multicast communication: \{\em individual authentication\}, and \{\em key revocation\}. Maintaining authenticity in multicast protocols is a much more complex problem than for unicast; in particular, known solutions are prohibitively inefficient in many cases. We present a solution that is reasonable for a range of scenarios. Our approach can be regarded as a `midpoint' between traditional Message Authentication Codes and digital signatures. We also present an improved and very efficient solution to another prevailing problem for multicast protocols, namely the key revocation problem.
Keywords: Network Management and security
Hao Che and San-qi Li, "MPOA Flow Classification Design and Analysis," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this paper, we propose a framework for the performance analysis and flow classification design of Multi-Protocol Over ATM (MPOA) network. The study based on the real Internet/intranet traces shows that even at high cost with long delay for each shortcut setup, MPOA can offer significant performance gain over the traditional routed network in an inter ELAN communication environment. In comparison, the MPOA performance gain in an Internet backbone environment is much less significant, mainly because of the dominant short-lived flows contributed by both $dns$ and $http$ applications. We also propose a flow classification algorithm, which substantially reduces the implementation complexity while achieves the same level of performance as compared to the default flow classification algorithm proposed by MPOA standard. A simple timeout mechanism is also introduced to the flow cache table management for significant performance improvement. We further develop a stable, adaptive flow classification algorithm, which achieves a near-optimal solution to minimize the constrained MPOA resource utilizations.
Keywords: Lan/man
Muriel Medard, Steven Finn and Rick Barry, "WDM Loop-back Recovery in Mesh Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Current means of providing loop-back recovery, which is widely used in SONET, relies on fiber-based recovery, where a fiber is used to back up another fiber. We present WDM-based loop-back recovery for optical networks where wavelengths are used to back up other wavelengths. We present two new algorithms for performing WDM-based loop-back over optical mesh networks. The first algorithm performs recovery for link failures. We compare its operation with known ways of providing loop-back recovery and show that the known methods are not applicable to WDM-based recovery. The second algorithm performs WDM loop-back recovery for node failures. We illustrate the operation of both algorithms and prove their validity. We discuss the advantages of WDM-based loop-back for flexibility in WDM service provisioning.
Keywords: Optical
David Hayes, Michael Rumsewicz and Lachlan Andrew, "Quality of Service Driven Packet Scheduling Disciplines for Real-Time Applications: Looking Beyond Fairness," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this paper we focus on real-time scheduling of soft real-time data services such as multimedia data, MPEG video streaming and IP telephony, which can tolerate a small degree of loss or delay. We argue that network operators and service providers should be able to select from a range of Quality of Service objectives, including maximising the number of customers receiving good service. Further, we argue that scheduling disciplines such as fair queueing are unable to achieve such goals and hence there is a need for alternative approaches. We propose a new scheduling scheme, which we call the Dual Queue discipline. We show that the Dual Queue has the flexibility to satisfy a variety of QoS objectives, ranging from existing notions of fairness through to maximising the number of customers receiving good service. In addition, even the simplest Dual Queue implementation outperforms Fair Queueing, is scalable in the number of active sessions, and can be made fair, if desired, over moderate to long time scales.
Keywords: Traffic management; scheduling
Yuguang Fang and Imrich chlamtac, "A New Mobility Model and Its Application in the Channel Holding Time Characterization in PCS Network," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In order to capture the essence of PCS network behavior, a good mobility model is necessary. This model must be good enough to fit field data and make the resulting queueing model still tractable. In this paper, we propose a new mobility model, called \{\it hyper-Erlang distribution model\}, which satisfies the above two requirements. We use this model to characterize the cell residence time and obtain analytical results for the channel holding time, the distribution of which is of primary importance in teletraffic analysis of PCS networks. These results can be used to facilitate the computation together with the use of the partial fractional expansion technique. It is expected that the mobility model and the analytical results for channel holding time presented in this paper will play an significant role for field data processing in PCS network design and performance evaluation.
Keywords: Performance analysis and modeling
Jj Garcia-Luna-Aceves and Ewerton L. Madruga, "A Multicast Routing Protocol for Ad-Hoc Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: The Core-Assisted Mesh Protocol (CAMP) is introduced for multicast routing in ad-hoc networks. CAMP generalizes the notion of core-based trees introduced for internet multicasting into multicast meshes that have much richer connectivity than trees. A shared multicast mesh is defined for each multicast group; the main goal of using such meshes is to maintain the connectivity of multicast groups even while network routers move frequently. CAMP consists of the maintenance of multicast meshes and loop-free packet forwarding over such meshes. Within the multicast mesh of a group, packets from any source in the group are forwarded along the reverse shortest path to the source, just as in traditional multicast protocols based on source-based trees. CAMP guarantees that, within a finite time, every receiver of a multicast group has a reverse shortest path to each source of the multicast group. Multicast packets for a group are forwarded along the shortest paths from sources to receivers defined within the group's mesh. CAMP uses cores only to limit the traffic needed for a router to join a multicast group; the failure of cores does not stop packet forwarding or the process of maintaining the multicast meshes.
Keywords: Routing & Multicasting
Sashisekaran Thiagarajan and Arun Somani, "An Efficient Algorithm for Optimal Wavelength Converter Placement on Wavelength-Routed Networks with Arbitrary Topologies," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper describes an algorithm for optimally placing a given number of wavelength converters in All-Optical Networks(AONs) with arbitrary topologies. We first introduce the simple network model upon which the algorithm is based. We explain how the blocking performance of the network can be obtained when a given number of converters are placed at the network nodes. We then present our optimal converter placement algorithm and illustrate its working using a simple example. The savings in calculation of the blocking performance offered by our algorithm is analyzed. Finally the benefits of our optimal converter placement algorithm is studied through network examples such as the path, NSFnet and the mesh-torus.
Keywords: Optical
Jose' Brustoloni, "Interoperation of Copy Avoidance in Network and File I/O," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Copy avoidance techniques for network I/O often assume that server buffers are ephemeral (i.e., are deallocated as soon as I/O processing completes). Such techniques cannot be used for file I/O, where buffers may need to be cached long-term. Mapped file I/O, however, can easily provide copy avoidance for cached server buffers. This paper demonstrates experimentally that mapped file I/O interoperates correctly with emulated copy, a recently proposed copy avoidance scheme for ephemeral server buffers. The resulting solution allows data to be passed between networks and file systems without copying and without changing existing interfaces. Greatest benefits are obtained when copying is avoided both in network and file I/O. Two new optimizations are contributed: header patching, for stripping packet headers and restoring page alignment without hardware support; and user-directed page swapping, for passing data between regions without copying. These optimizations are useful also for network I/O with operating system bypass or with non-copy semantics.
Keywords: Communications protocols and software
Go Hasegawa, Masayuki Murata and Hideo Miyahara, "Fairness and Stability of Congestion Control Mechanism of TCP," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this paper, we focus on fairness and stability of the congestion control mechanisms adopted in several versions of TCP by investigating their time--transient behaviors through an analytic approach. In addition to TCP Tahoe and TCP Reno widely used in the current Internet, we also consider TCP Vegas, which adjusts the sending window size by observing the round trip times of the connection, and enhanced TCP Vegas, which is proposed in this paper for fairness enhancements. We consider homogeneous case, where two connections have the equivalent propagation delays, and heterogeneous case, where each connection has different propagation delay. We show that TCP Tahoe and TCP Reno can achieve fairness among connections in homogeneous case, but cannot in heterogeneous case. We also show that TCP Vegas can provide almost fair service among connection, but there is some unfairness caused by the essential nature of TCP Vegas. Finally, we explain the effectiveness of our enhanced TCP Vegas in terms of fairness and throughput.
Keywords: Congestion control
Giannis Marias, Dimitris Skyrianoglou and Lazaros Merakos, "A Centralised Approach to Dynamic Channel Assignment in Wirelles ATM LANs," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: A Centralised approach for Dynamic Channel Assignment (DCA) in wireless ATM LANs is presented. The proposed approach applies to structured wireless ATM LANs, were Base Stations act as hubs offering wireless access to Mobile Units. An IntrAdomain DCA entity (IADCA) is introduced for the dynamic assignment of resources to the requesting Base Stations, taking into account mutual interference constraints and the current resource usage. The IADCA entity is based on two different reservation disciples and multiple assignment policies when candidate carriers are available. Simulation results for a number of scenarios are presented to assess the performance of the proposed approach.
Keywords: Wireless ATM
Thorsten Kurz, Patrick Thiran and Jean-Yves Le Boudec, "Regulation of a CAC Algorithm," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Connection Admission Control (CAC) algorithms are used to decide whether an incoming connection should be accepted or rejected in a node of a network offering reservation based services in order to maintain the guaranteed Quality of Service (QoS) in the network. In this paper, we consider the statistical CAC algorithm proposed by Elwalid et al. . The traffic model is made of ON-OFF sources and the QoS parameter is the loss probability. Based on the traffic descriptors of existing and incoming connections, the algorithm takes its decision by computing an upper bound of this probability and checking whether it is larger than a given tolerance e. Usually this tolerance is a fixed, given parameter. We propose here to adapt e to react to the actual losses experienced at the node using a simple regulation mechanism: if the actual loss ratio is much smaller than the targeted loss ratio, e is increased to make a more aggressive usage of the available resources, and vice versa if the actual loss ratio is too high. We discuss the influence of the regulation parameters and we show that despite its simplicity this regulated CAC improves significantly the performance of its non-tunable counterpart.
Keywords: Traffic management; scheduling
Jun Li, Roy Yates and Dipankar Raychaudhuri, "Performance Analysis on Path Rerouting Algorithms for Handoff Control in Mobile ATM Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper studies the distribution of mobile-generated traffic in mobile ATM networks and evaluates the performance of dynamic path rerouting algorithms for handoff control. In mobile ATM networks, user mobility and handoff path rerouting process may produce extra traffic load over network links, which leads to greater network capacity to support the same QoS. In this paper, we propose a \{\it dynamic flow model\} for mobile ATM networks. The model represents the mobile-generated traffic as a set of stochastic flows over a set of OD (Origin-Destination) pairs. The user mobility is defined as the transfer probability of the flows and the handoff path rerouting algorithm is modeled by a transformation between the routing functions for traffic flows. The analysis shows that user mobility may cause the temporal variations as well as the \{\it smoothing effect\} on the network traffic distribution. Using the dynamic flow model, typical handoff path rerouting algorithms are evaluated through both analytical and experimental approaches. The methodology of evaluation can be used for either redesigning the network topology for given path rerouting algorithm or selecting a path rerouting algorithm for a given network topology under a specific mobile service scenario.
Keywords: Wireless ATM
Norbert Vicari and Robert Schedel, "Performance of the GFR-Service with Constant Available Bandwidth," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Recently the ATM Forum defined the Guaranteed Frame Rate service category to provide a minimum service guarantee to classical best-effort services. The eligibility of frames for this service category is determined with the Frame Based Generic Cell Rate Algorithm and the transmission is guaranteed by a queuing-discipline based on two thresholds. In this paper we present a discrete-time analysis of the GFR-service under the assumption of constant available bandwidth. The presented method can be applied to dimension the thresholds of the queuing discipline used to enforce the guaranteed service.
Keywords: ATM
Craig Labovitz, Gerald Malan and Farnam Jahanian, "Origins of Internet Routing Instability," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper examines the network routing messages exchanged between core Internet backbone routers. Internet routing instability, or the rapid fluctuation of network reachability information, is an important problem currently facing the Internet engineering community. High levels of network instability can lead to packet loss, increased network latency and time to convergence. At the extreme, high levels of routing instability have led to the loss of internal connectivity in wide-area, national networks. In an earlier study of inter-domain routing, we described widespread, significant pathological behaviors in the routing information exchanged between backbone service providers at the major U.S. public Internet exchange points. These pathologies included several orders of magnitude more routing updates in the Internet core than anticipated, large numbers of duplicate routing messages, and unexpected frequency components between routing instability events. The work described in this paper extends our earlier analysis by identifying the origins of several of these observed pathological Internet routing behaviors. We show that as a result of specific router vendor software changes suggested by our earlier analysis, the volume of Internet routing updates has decreased by an order of magnitude. We also describe additional router software changes that can decrease the volume of routing updates exchanged in the Internet core by an additional 30 percent or more. We conclude with a discussion of trends in the evolution of Internet architecture and policy that may lead to a rise in Internet routing instability.
Keywords: Internet and experimental systems
Srinidhi Varadarajan and Tzi-cker Chiueh, "Automatic Fault Detection and Recovery in Real Time Switched Ethernet Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: EtheReal is a real-time Fast Ethernet switch architecture that provides bandwidth guarantees to distributed multimedia applications without OS and hardware modifications on the host machines. It implements true link-layer multicast, and offers a natural match to support network-layer QoS protocols such as RSVP. Because real-time performance guarantees fundamentally require state to be installed inside the network, link/switch failures could lead to significant disruption to the QoS promised to the user applications. This paper describes the fault detection and recovery mechanism supported by the EtheReal architecture, and reports on the performance measurements of the initial prototype implementation. The heart of EtheReal's fault detection and recovery mechanism is a fast spanning tree reconfiguration algorithm to reduce the total fault recovery time, and a delayed link inactivation scheme that allows real-time connections which are not affected by the failed links/switches to continue to exist, even though some of the links are marked as ``blocked'' in the new spanning tree topology. Measurements on the prototype show that the fault detection and recovery time on a network whose diameter is 10 hops are 220ms and 31ms, respectively. This combined delay corresponds to a minor jitter in real-time audio/video communication, and is a significant improvement over the standard IEEE 802.1d implementation, which takes on the order of 30 sec.
Keywords: Routing & Multicasting
Tushar Tripathi and Kumar N. Sivarajan, "Computing Approximate Blocking Probabilities in Wavelength Routed All-Optical Networks with Limited-Range Wavelength Conversion," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this paper, we propose a method to calculate the average blocking probability in all-optical networks using *limited-range* wavelength conversion. Previous works have shown that there is a remarkable improvement in blocking probability while using limited-range wavelength conversion [2], [3] but these analytical models were either for a path [2] or for a mesh-torus network [3]. Using a graph-theoretical approach, we extend Birman's model [4] for no wavelength conversion and derive an analytical expression to compute the blocking probabilities in networks with limited-range wavelength conversion for fixed routing. The proposed analytical model is a generalization of Birman's model and is applicable to *any* network topology. We consider the case where an incoming wavelength can be converted to d adjacent outgoing wavelengths on either side of the input wavelength, in addition to the input wavelength itself, where d is the degree of conversion. Using this model we demonstrate that the performance improvement obtained by full wavelength conversion over no wavelength conversion can almost be achieved by using limited wavelength conversion with the degree of conversion, d, being only 1 or 2. In a few example networks we considered, for blocking probabilities up to a few percent, the carried traffic with limited conversion degree d=2 was almost equal to the carried traffic for full wavelength conversion. The results obtained show that significant improvements in blocking performance can be obtained by providing limited-range wavelength conversion of small degree within the network.
Keywords: Optical
Cheng-Shang Chang and Rene L. Cruz, "A Time Varying Filtering Theory for Constrained Traffic Regulation and Dynamic Service Guarantees," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: By extending the filtering theory under the (min,+)-algebra to the time varying setting, we solve the problem of constrained traffic regulation and develop a calculus for dynamic service guarantees. For a constrained traffic regulation problem with maximum tolerable delay d and maximum buffer size q, the optimal regulator that generates the output traffic conforming to a subadditive envelope f and minimizes the number of discarded packets is a concatenation of the g-clipper with g(t) = min[f(t+d), f(t)+q] and the maximal f-regulator. The g-clipper is a bufferless device which optimally drops packets as necessary in order that its output be conformant to an envelope g. The maximal f-regulator is a buffered device that delays packets as necessary in order that its output be conformant to an envelope f. The f-regulator is a linear time invariant filter with impulse response f, under the (min,+)-algebra. To provide dynamic service guarantees in a network, we develop the concept of a dynamic server as a basic network element. Dynamic servers can be joined by concatenation, ``filter bank summation,'' and feedback to form a composite dynamic server. We also show that dynamic service guarantees for multiple input streams sharing a work conserving link can be achieved by a dynamic SCED (Service Curve Earliest Deadline) scheduling algorithm, if an appropriate admission control is enforced.
Keywords: Traffic management; scheduling
Despina Saparilla, Keith W. Ross and Martin Reisslein, "Periodic Broadcasting with VBR-Encoded Video," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We consider designing near video on demand (VoD) systems that minimize start-up latency while maintaining high image quality. Recently non-uniform segmentation has been used to develop periodic broadcasting techniques for near VoD. These techniques give significant reductions in start-up latency as compared with more conventional uniform segmentation. All of these schemes assume, however, that the videos are CBR-encoded. Since a CBR-encoded video has a larger average rate than an open-loop VBR encoding with the same image quality, there is potential to obtain further performance improvements by using VBR video. In this paper we develop a series of multiplexing schemes for the periodic broadcasting of VBR-encoded video, which are based on smoothing, server buffering and client prefetching. Two key but conflicting performance measures exist when using VBR video: latency and packet loss. By introducing small additional delays in our multiplexing schemes, our traced-based numerical work shows that the schemes can achieve nearly 100% link utilization with negligible packet loss. When the ratio of the CBR rate to the VBR average rate is a modest 1.8, start-up latency can be reduced by a factor of four or more for common scenarios.
Keywords: Traffic management; scheduling
Carlos Pazos, Juan Sanchez-Agrelo and Mario Gerla, "Using Back-Pressure to Improve TCP Performance with Many Flows," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Congestion control of Internet Best Effort traffic relies mostly on TCP window flow control of individual sessions. This paper argues that such approach does not scale well to a very large number of simultaneously active flows, typical of backbones characterized by large delay-bandwidth products. In this scenario, the TCP window sizes tend to be small and dropping or marking packets alone is not effective to reduce the offered traffic. An analysis presented here describes the aggressive TCP dynamics under many flows and suggests that performance can be improved by applying back-pressure flow control to the aggregate traffic in the backbone. To demonstrate this argument, a link-layer, rate-based, back-pressure mechanism for IP-over-ATM backbones using the ABR service is described. A simulation study of a network with this capability demonstrates the improvement of TCP performance under many flows. The study also considers RED and ECN routers to indicate that these techniques alone are not well positioned to address the many flows scenario either. However, the combination of RED and ECN routers with back-pressure has the potential to further improve TCP performance.
Keywords: Internet and experimental systems
Costas Courcoubetis, Antonis Dimakis and George Stamoulis, "Traffic Equivalence and Substitution in a Multiplexer," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: For a multiplexer fed with a large number of sources we derive conditions under which a single source can be substituted for a given subset of the sources while preserving the buffer overflow probability and the dominant time scales of buffer overflows. This equivalence is stronger than simple effective bandwidth equality and takes into account the context in which mutiplexing takes place. This allows a substitution to be made for arbitrarily large proportions of the traffic without changing the operating point of the multiplexer as experienced by the rest of the traffic. It corresponds to defining a single source which is equivalent in a sense ``local'' to a given context, rather than equivalent in a sense which is ``universal'' to all contexts. The proposed methodology does not rely on traffic models and obtains the necessary information from the actual traffic traces. We study the case of fractional Brownian motion as a single source substitute and provide theoretical and experimental results that validate the approach.
Keywords: Performance analysis and modeling
Michael Donahoo, Mostafa Ammar and Ellen Zegura, "Multiple-Channel Multicast Scheduling for Scalable Bulk-data Transport," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: A key technique for allowing a server to handle a large volume of requests for file transfers is to multicast the data to the set of requesting clients. Typically, the paths from the server to the clients will be heterogeneous in bandwidth availability. Multiple-Channel Multicast (MCM) is an approach that can be used to handle this heterogeneity. In this approach the data is multicast over multiple channels, each addressed as a separate multicast group. Each receiver subscribes to a set of channels (i.e., joins the corresponding multicast groups) commensurate with its own rate capabilities. Of particular interest in the design of MCM schemes is the scheduling of data transmission across the multiple channels to accomodate asynchronous requests from clients. In this paper, we present and analyze a new multiple-channel multicast approach called Partition Organization (PO) scheduling. The scheme is designed to result in good reception efficiency when compared to existing proposals while improving on their performance when other measures of interest (which we introduce) are considered.
Keywords: Routing & Multicasting
Indra Widjaja, Haining Wang, Steven Wright and Amalendu Chatterjee, "Scalability Evaluation of Multi-Protocol Over ATM (MPOA)," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Multi-Protocol over ATM (MPOA) is being considered by the industry as an important short-cut technology that provides an efficient transfer of inter-subnet unicast data in a LANE environment. MPOA was initially considered to carry backbone traffic in the enterprise or campus networks. However, congestion in the public Internet provokes many to consider MPOA as a solution for the carrier or service provider networks as well. In this paper, we investigate the scalability issues of MPOA in the wide area network environment. We use a realistic simulation model driven by real Internet traffic traces to study crucial metrics such as the SVC setup rate, the number of VCs required, and the percentage of packets switched. Based on the simulation results, we find that MPC ingress cache size provides a three-way trade-off among the percentage of switched packets, the VC usage and the SVC setup rate requirement. We also find that the SVC setup rate is linearly dependent on the packet arrival rate.
Keywords: Performance analysis and modeling
Yannis Korilis and Ariel Orda, "Incentive Compatible Pricing Strategies for QoS Routing," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: QoS routing mechanisms allow users identify paths that can accommodate their performance requirements and reserve the necessary resources. An important problem is how to conduct such resource allocation efficiently, not only from the single-connection, but also from the network point of view. We propose the use of pricing mechanisms as a means to regulate the users' decisions in a networkwide efficient manner. Focusing on QoS architectures that employ rate-based schedulers, we formulate a congestion-based pricing scheme. We establish the structure of the corresponding user-optimal response, i.e., a path selection algorithm that satisfies the user's requirements at minimal cost. We show that the underlying noncooperative game among users has a unique equilibrium, for any particular choice of price functions. Then, we establish the existence of incentive compatible price functions, which drive the network into an equilibrium point that coincides with the optimum of a social function. Specifically, these price functions are the derivatives of the social function. We then extend our results to the case in which users can identify only sub-optimal paths, as is often the case with multiobjective path optimization.
Keywords: Traffic management; scheduling
Kin Leung, "A Kalman-Filter Method for Power Control in Broadband Wireless Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: A Kalman-filter method for power control is proposed for broadband, packet-switched TDMA wireless networks. By observing the temporal correlation of co-channel interference when transmitters can send data contiguously, the method uses a Kalman fitler to predict interference power in the future. Based on the predicted interference and estimated path gain between the transmission and receiver, transmission power is determined to achieve a desired signal-to-interference-plus-noise ratio (SINR). Performance results reveal that the Kalman-filter method for power control provides a significant performance improvement. Specifically, when a message consists of 10 packets on average, the 90 and 95 percentile of the SINR by the new method are 3.95 and 5.53 dB above those when no power control is in use, and lie just 0.73 and 1.04dB below the upper-bound performance of the optimal power control, respectively, in a system with 4-sector cells and an interleaved frequency assignment of a reuse factor of 2/8 [WL98]. As a by-product, these results show that the cell layout and assignment scheme combined with the new method for power control can be used to support high-speed data services.
Keywords: Wireless
Faber Theodore, Joe Touch and Wei Yue, "The TIME-WAIT state in TCP and Its Effect on Busy Servers," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Hosts providing important network services such as HTTP and FTP incur a per-connection memory load from TCP that can adversely affect their connection rate and throughput. The memory requirement is directly tied to the number of connections; caching and other sharing methods will not alleviate it. We have observed HTTP throughput reductions of as much as 50% under SunOS 4.1.3 due to this loading. This paper advocates off-loading the memory requirements to the growing number of clients. This reduces server memory requirements as connection rate at that server grows due to increases in the number of clients and the bandwidth available on the network. Our approaches control server memory load better with growing client load than per-transaction techniques such as persistent HTTP connections. Our approaches also interoperate with persistent connections to take advantage of their other benefits. This paper describes the causes of the memory loading, called TIME-WAIT loading, and defines three methods of alleviating it that scale with increasing number of clients. We present measurements of the systems and a comparison of their properties.
Keywords: Communications protocols and software
Farooq Anjum and Leandros Tassiulas, "Fair Bandwidth Sharing among Adaptive and Non-Adaptive Flows in the Internet," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: The problem of fair bandwidth sharing among adaptive (TCP) and non-adaptive (i.e. CBR-UDP) flows at an Internet gateway is considered. An algorithm that drops packet preventively, in an attempt to actively penalize the non-adaptive traffic that attempts to ``steal'' buffer space, and therefore bandwidth from the adaptive traffic flows, is presented. The algorithm maintains minimal flow state information and is therefore scalable. The performance of the algorithm is compared with other gateway algorithms and it is shown that, in the presence of non-adaptive traffic, it achieves a more balanced bandwidth allocation among the different flows. The behavior of a flow subjected to the given algorithm has also been analysed in detail.
Keywords: Internet and experimental systems
S. Jamaloddin Golestani and Krishan Sabnani, "Fundamental Observations on Multicast Congestion Control in the Internet," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Multicast congestion Control
Keywords: Congestion control
Izhak Rubin and Jing Ling, "All-optical cross-connect meshed-ring communications networks using a reduced number of wavelengths," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We introduce a meshed ring communications network which employs cross-connect switches. The cross-connect switches can be implemented as wavelength routers resulting in WDM networks, or as ATM Virtual Path (VP) switches leading to ATM compatible network systems. We show in the paper that this network architecture results in a significant increase in throughput performance in comparison with SONET ring networks. For a certain class of meshed rings, under a uniform traffic matrix, we derive the optimal topology which achieves maximum throughput efficiency. For practical implementation reasons, we investigate the performance of networks which employ a reduced number of identifiers (e.g., using fewer wavelengths or fewer VPI's). We demonstrate that by increasing the bandwidth allocated to wavelength subnetworks, the required number of wavelengths is reduced. Furthermore, we show that by modifying the topological layout of the meshed ring network, we can reduce substantially the number of required wavelengths (or identifiers), while incurring just a modest reduction in throughput efficiency!
Keywords: Optical
George Apostolopoulos, Sanjay Kamat and Roch Guerin, "Implementation and Performance Measurements of QoS Routing Extensions to OSPF," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this paper, we report on an implementation of QoS routing extensions to the OSPF protocol, and on various performance measurements made on the basis of this implementation to assess the cost and feasibility of QoS routing in IP networks. The results provide insight into the respective weights of the two major components of QoS routing costs, processing cost and protocol overhead. More important, they establish strong empirical evidence that the cost of QoS routing is well within the limits of modern processors. Furthermore, we also find that although support for QoS routing does increase the amount of protocol traffic, it still remains a minute fraction of the bandwidth of most links. The paper also explores the sensitivity of our findings to variations in network size and topology, by combining the information obtained from the implementation to results generated by means of simulations. This provides a comprehensive investigation of the operational costs of QoS routing.
Keywords: Routing & Multicasting
Laurent Gautier, Christophe Diot and Jim Kurose, "End-to-end Transmission Control Mechanisms for Multiparty Interactive Applications on the Internet," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper reports on the design and the evaluation of transmission control mechanisms specifically designed for multiplayer, distributed (serverless), interactive Internet applications. Distributed synchronization and dead reckoning are the main elements of this transmission control infrastructure. These mechanisms have been implemented in a fully distributed, multiplayer game application, i.e., one in which each entity in a game session computes its own local view of the session. The role of each entity is consequently to periodically send its own state to all other session participants (using RTP/UDP/IP multicast) and to periodically compute its own local view of the global game state using information received from the other participants. A detailed experimental analysis is provided using MBone and LAN experiments. We investigate how the ``quality'' of the game is influenced by the frequency at which players exchange state information, as well as by network impairments such as packet loss and transmission delay.
Keywords: Internet and experimental systems
Shang-Tse Chuang, Ashish Goel, Nick McKeown and Balaji Prabhakar, "Matching Output Queueing with a Combined Input Output Queued Switch," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: The Internet is facing two problems simultaneously: there is a need for a faster switching/routing infrastructure, and a need to introduce guaranteed qualities of service (QoS). Each problem can be solved independently: switches and routers can be made faster by using input-queued crossbars, instead of shared memory systems; and QoS can be provided using WFQ-based packet scheduling. However, until now, the two solutions have been mutually exclusive - all of the work on WFQ-based scheduling algorithms has required that switches/routers use output-queueing, or centralized shared memory. This paper demonstrates that a Combined Input Output Queueing (CIOQ) switch running twice as fast as an input-queued switch can provide precise emulation of a broad class of packet scheduling algorithms, including WFQ and strict priorities. More precisely, we show that a ``speedup'' of 2 is sufficient, and a speedup of 2-1/N is necessary, for this exact emulation. We introduce a variety of algorithms that configure the crossbar so that emulation is achieved with a speedup of two, and consider their running time and implementation complexity. An interesting feature of our work is that the exact emulation holds for all input traffic patterns. We believe that, in the future, these results will make possible the support of QoS in very high bandwidth routers.
Keywords: Switching
Michael Hicks, Jonathan Moore, Scott Alexander, Carl Gunter and Scott Nettles, "PLANet: An Active Internetwork," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Active networking addresses the issue of slow network evolution by making the network programmable, and therefore extensible. We have designed a system based on a special purpose programming language, PLAN (Packet Language for Active Networks), which allows exploration of several key dimensions of the active networking design space; in particular, our system supports both programmable packets and dynamic server extensions. We have used our system to build an active internetwork, PLANet, in which all packets are PLAN programs and new services can be dynamically added to the network using a combination of programmability features. PLANet is implemented in user-space using a byte-code interpreted version of the Caml language running on Linux PCs and currently supports Ethernet and IP as link layers. On 300~MHz Pentium-II's over 100~Mbps Ethernet, PLANet routers can achieve 48~Mbps and can switch over 5000 packets per second. As an illustration of the uses of programmability, we also present several experiments that demonstrate how PLANet can support a variety of strategies for coping with congestion.
Keywords: Internet and experimental systems
Jia-Ru Li, Dane Dwyer and Vaduvur Bharghavan, "A Transport Protocol For Heterogeneous Packet Flows," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: A Transport Protocol For Heterogeneous Packet Flows Jia Ru Li, Dane Dwyer, Vaduvur Bharghavan Coordinated Science Laboratory University of Illinois In this paper, we present a new transport protocol called HPF for effectively supporting heterogeneous packet flows in an Internet environment. The following are the key features of HPF: + HPF supports heterogeneous packet flows with different reliability, priority and timing (delay) requirements in the same transport connection. + HPF decouples the congestion control and reliability mechanisms (that are integrated in TCP) in order to support congestion control for unreliable and heterogeneous packet flows. + HPF supports application-level framing, and provides APIs for applications to specify the priority, reliability and timing requirements of each frame. + HPF enables the use of application-specified priorities as hints for network routers to preferentially drop low-priority packets during congestion. This ensures that `important data' gets through with high priority over unimportant data during congestion. We show through performance measurements in our experimental testbed that our approach can provide effective support for heterogeneous packet flows in the presence of dynamic networking resources.
Keywords: Communications protocols and software
Andras Farago, Imrich Chlamtac and Stefano Basagni, "Virtual Path Network Topology Optimization Using Random Graphs," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: An algorithm is presented for designing the logical topology of the virtual path (VP) network, an important task in ATM network design. We prove that the algorithm provides a VP network topology that is asymptotically optimal with respect to both connectivity and the diameter of the network. These optimality properties are combined with algorithmic simplicity and polynomial running time, thus overcoming the notorious ``optimality vs. scalability'' dilemma. This result is made possible by applying the theory of random graphs to this type of networks. This theory has the methodological advantage of increased accuracy with growing network size, thus turning the ``curse of dimensionality'' into a blessing. Therefore, the paper exemplifies that the theory of random graphs, beyond supporting analysis purposes, may serve as a useful tool in the design of algorithms that overcome the ``scalability bottleneck,'' a problem that prevents current approaches from finding near-optimal solutions as today's networks grow in size and complexity.
Keywords: Traffic management; scheduling
Zohar Naor and Hanoch Levy, "Cell Identification Codes for Tracking Mobile Users," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: area: Location management in wireless networks.
Keywords: Wireless
Rahul Jain and Edward Knightly, "A Framework for Design & Evaluation of Admission Control Algorithms in Multi-Service Mobile Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Supporting Quality of Service (QoS) guarantees in wireless networks requires that admission control algorithms incorporate user mobility, and limit the probability that sufficient resources are unavailable when a user must handoff. In this paper, we develop a framework for designing admission control algorithms in wireless networks that support guaranteed QoS. First, we devise a taxonomy to explore the mathematical structure and practical design tradeoffs encountered in developing admission control algorithms. We next introduce the Perfect Knowledge Admission Control Algorithm, which, while unrealizable in practice, serves as a benchmark for evaluating admission control algorithms by using future knowledge of handoff events to exactly control the admissible region. Finally, we perform an extensive set of simulations (including trace-driven simulations) and, applying the Perfect Knowledge Algorithm, we study several admission control algorithms from the literature, identify a number of key system parameters for algorithm design, and quantify the fundamental tradeoffs in complexity and accuracy as revealed by the taxonomy.
Keywords: Wireless
George Apostolopoulos, Vinod Peris and Debanjan Saha, "Transport Layer Security: How much does it really cost?," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: The last couple of years has seen a growing momentum towards using the Internet for conducting business. One of the key enablers for business applications is the ability to setup secure channels across the internet. The Secure Sockets Layer (SSL) protocol provides this capability and it is the most widely used transport layer security protocol. In this paper we investigate the performance of SSL both from a latency as well as a throughput point of view. Since SSL is primarily used to secure web transactions, we use the SPECWeb96 benchmark suitably modified for use with the SSL protocol. We benchmark two of the more more popular web-servers that are in use today and find that they are a couple of orders of magnitude slower when it comes to serving secure web pages. We investigate the reason for this deficiency by instrumenting the SSL protocol stack with a detailed profiling of the protocol processing components. Based on our findings we suggest two modifications to the protocol that reduce the latency as well as increase the throughput at the server.
Keywords: Network Management and security
Nick Duffield, "Asymptotic Sampling Properties of Effective Bandwidth Estimation for Admission Control.," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In measurement based admission control, measured traffic parameters are used determine the maximum number of connections which can be admitted to a resource within a given quality constraint. It has been pointed out that the certainty equivalent formulation, in which the measured parameters are assumed to be the true ones, can compromise admission control. This is because the measured parameters are themselves random quantities, and so contribute additional variability to the attained quality. This paper analyzes the asymptotic sampling properties of admission controllers that use effective bandwidth estimation in a large deviation setting. This analysis applies to both bufferless and buffered resources; in the many sources asymptotic and in the large buffer asymptotic. It also investigates the impact of correlations between samples, as modeled by Markov processes.
Keywords: Performance analysis and modeling
Tzi-cker Chiueh and Chiueh and Prashant Pradhan, " High Performance IP Routing Table Lookup using CPU Caching", in Proceedings of the Conference on Computer Communications (IEEE Infocom), New York, March 1999.
Abstract: Wire-speed IP (Internet Protocol) routers require very fast routing table lookup for incoming IP packets. The routing table lookup operation is time consuming because the part of an IP address used in the lookup, i.e., the network address portion, is variable in length. This paper describes the routing table lookup algorithm used in a cluster-based parallel IP router project called Suez. The innovative aspect of this algorithm is its ability to use CPU caching hardware to perform routing table caching and lookup directly by carefully mapping IP addresses to virtual addresses. By running a detailed simulation model that incorporates the performance effects of the CPU memory hierarchy against a packet trace collected from a major network router, we show that the overall performance of the proposed algorithm can reach 87.87 million lookups per second for a 500-MHz Alpha processor with a 16-KByte L1 cache and a 1-MByte L2 cache. This result is one to two orders of magnitude faster than previously reported results on software-based routing table lookup implementations. This paper also reports the performance impacts of various architectural parameters in the proposed scheme and its storage costs, together with the measurements of an implementation of the proposed scheme on a Pentium-II machine running Linux.
Keywords: Routing & Multicasting
Nen-Fu Huang, Shi-Ming Zhao, Jen-Yi Pan and Chi-An Su, "A Fast IP Routing Lookup Scheme for Gigabit Switching Routers," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: One of the key design issues for the new generation IP routers is the route lookup mechanism. For each incoming IP packet, the IP routing requires to perform a longest prefix matching on the address lookup in order to determine the packet's next hop. This paper presents a fast route lookup mechanism that only needs tiny SRAM and can be implemented in a pipelined skill in hardware. Based on the proposed scheme, the forwarding table is tiny enough to fit in SRAM with very low cost. For example, a large routing table with 40,000 routing entries can be compacted to a forwarding table of 450-470 Kbytes. In the worst case, the number of memory accesses for a lookup is three. When implemented in a pipeline skill in hardware, the proposed mechanism can achieve one routing lookup every memory access. With current 10ns SRAM, this mechanism furnishes approximately 100 million routing lookups per second. This is much faster than any current commercially available routing lookup schemes.
Keywords: Switching
Lee Breslau, Pei Cao, Li Fan, Graham Phillips and Scott Shenker, "Web Caching and Zipf-like Distributions: Evidence and Implications," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper addresses two unresolved issues about Web caching. The first issue is whether Web requests from a fixed user community are distributed according to Zipf's law~\cite\{zipf29\}. Several early studies have supported this claim~\cite\{glassman94,cunha95,almeida96a\} while other recent studies have suggested otherwise~\cite\{Nishikawa98,almeid98\}. The second issue relates to a number of recent studies on the characteristics of Web proxy traces, which have shown that the hit-ratios and temporal locality of the traces exhibit certain asymptotic properties that are uniform across the different sets of the traces~\cite\{cao97,rizzo98,duska:usits97,gribble97,kroeger:usits97\}. In particular, the second issue is whether these properties are inherent to Web accesses or whether they are simply an artifact of the traces. An answer to these unresolved issues will facilitate both Web cache resource planning and cache hierarchy design. We show that the answers to the two questions are related. We first investigate the page request distribution seen by Web proxy caches using traces from a variety of sources. We find that the distribution does not follow Zipf's law precisely, but instead follows a Zipf-like distribution with the exponent varying from trace to trace. Furthermore, we find that there is (i) a weak correlation between the access frequency of a Web page and its size and (ii) a weak correlation between access frequency and its rate of change. We then consider a simple model where the Web accesses are independent and the reference probability of the documents follows a Zipf-like distribution. We find that the model yields asymptotic behaviors that are consistent with the experimental observations, suggesting that the various observed properties of hit ratios and temporal locality are indeed inherent to Web accesses observed by proxies. Finally, we revisit Web cache replacement algorithms and show that the algorithm that is suggested by this simple model performs best on real trace data. The results indicate that while page requests do indeed reveal short-term correlations and other structures, a simple model for an independent request stream following a Zipf-like distribution is sufficient to capture certain asymptotic properties observed at Web proxies.
Keywords: Communications protocols and software
Jim Challenger, Arun Iyengar and Paul Dantzig, "A Scalable System for Consistently Caching Dynamic Web Data," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper presents a new approach for consistently caching dynamic Web data in order to improve performance. Our algorithm, which we call Data Update Propagation (DUP), maintains data dependence information between cached objects and the underlying data which affect their values in a graph. When the system becomes aware of a change to underlying data, graph traversal algorithms are applied to determine which cached objects are affected by the change. Cached objects which are found to be highly obsolete are then either invalidated or updated. DUP was a critical component at the official Web site for the 1998 Olympic Winter Games. By using DUP, we were able to achieve cache hit rates close to 100% compared with 80% for an earlier version of our system which did not employ DUP. As a result of the high cache hit rates, the Olympic Games Web site was able to serve data quickly even during peak request periods.
Keywords: Internet and experimental systems
Gene Cheung and Steve McCanne, "Optimal Routing Table Design for IP Address Lookups Under Memory Constraints," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: The design of lookup tables for fast IP address lookup algorithms using a general processor is formalized as an optimization problem. A cost model that models the access times and sizes of the hierarchical memory structure of the processor is formulated. Two algorithms, using dynamic programming and Lagrange multipliers, solve the optimization problem optimally and approximately respectively. Experimental results show our techniques has visible improvements over existing techniques in the literature.
Keywords: Routing & Multicasting
Seung Rhee and Takis Konstantopoulos, "A Decentralized Model for Virtual Path Capacity Allocation," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We investigate the problem of Virtual Path (VP) capacity
Keywords: Traffic management; scheduling
Reza Rejaie, Mark Handley and Deborah Estrin, "An End-to-end Rate-based Congestion Control Mechanism for Realtime Streams in the Internet," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: End-to-end congestion control mechanisms have been critical to the robustness and stability of the Internet. The majority of today's Internet traffic is TCP, and we expect this to remain a large proportion of traffic in the future. Thus, having ``TCP-friendly'' behavior is crucial for new applications. However, the emergence of non-congestion-controlled realtime applications threatens unfairness to competing TCP traffic and possible congestion collapse. We present an end-to-end TCP-friendly Rate Adaptation Protocol (RAP), which employs an additive-increase, multiplicative-decrease (AIMD) algorithm. It is well suited for unicast playback of realtime streams and other semi-reliable rate-based applications. Its primary goal is to be fair and in particular \{\em TCP-friendly\} while separating network congestion control from application-level reliability. We evaluate RAP through extensive simulation, and conclude that bandwidth is usually evenly shared between TCP and RAP traffic. Unfairness to TCP traffic is directly determined by how TCP diverges from the AIMD algorithm. Basic RAP behaves in a TCP-friendly fashion in a wide range of likely conditions, but we also devised a fine-grain rate-adaptation mechanism to extend this range further. Finally, we show that deploying RED queue management can result in more ideal fairness between TCP and RAP traffic.
Keywords: Congestion control
Andy Myers, Peter Dinda and Hui Zhang, "Performance Characteristics of Mirror Servers on the Internet," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: As a growing number of web sites introduce mirrors to increase throughput, the challenge for clients becomes determining which mirror will offer the best performance when a document is to be retrieved. In this paper we present findings from measuring 9 clients scattered throughout the United States retrieving over 490,000 documents from 47 production web servers which mirror three different web sites. We have several interesting findings that may aid in the design of protocols for choosing among mirror servers. Though server performance varies widely, we have observed that a server's performance relative to other servers is more stable and is independent of time scale. In addition, a change in an individual server's transfer time is not a strong indicator that its performance relative to other servers has changed. Finally, we have found that clients wishing to achieve near-optimal performance may only need to consider a small number of servers rather than all mirrors of a particular site.
Keywords: Internet and experimental systems
Sue Moon, Paul Skelly and Don Towsley, "Estimation and Removal of Clock Skew from Network Delay Measurements," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Packet delay and loss traces are frequently used by network engineers, as well as network applications, to analyze network performance. The clocks on the end-systems used to measure the delays, however, are not always synchronized, and this lack of synchronization reduces the accuracy of these measurements. Therefore, estimating and removing relative skews and offsets from delay measurements between sender and receiver clocks are critical to the accurate assessment and analysis of network performance. In this paper we introduce a linear programming-based algorithm to estimate the clock skew in network delay measurements and compare it with three other algorithms. We show that our algorithm has time complexity of $O(N)$, leaves the delay after the skew removal positive, and is robust in the sense that the error margin of the skew estimate is independent of the magnitude of the skew. We use traces of real Internet delay measurements to assess the algorithm, and compare its performance to that of three other algorithms. Furthermore, we show through simulation that our algorithm is unbiased, and that the sample variance of the skew estimate is better (smaller) than existing algorithms.
Keywords: Internet and experimental systems
Achille Pattavina and Guido Maier, "Photonic Rearrangeable Networks with Zero Switching-Element Crosstalk," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: The substantial growth expected in the near future in the demand of transmission bandwidth to be used in a dynamic and flexible transport network makes the development of all-optical digital cross-connect architectures very important. We consider here in particular the class of the rearrangeable non-blocking space-division switching fabrics configured as multistage structures built with very simple optical switching elements. Rearrangeable networks look today more attractive than strict-sense non-blocking networks since the former have a lower complexity and are compatible with the data loss rate required in a circuit-switched network even with current technology of optical switching devices. We face one the most important problems which arises in a multiple space-channel optical system such as a photonic switching fabric, that is the build-up of crosstalk noise on a certain channel due to the interference with other signals inside the system. We find here the design rules to configure a minimum-cost rearrangeable photonic switching network where the most serious cause of crosstalk (interference inside the switching elements) is eliminated.
Keywords: Switching
Eric Levy-Abegnoli, Arun Iyengar, Junehwa Song and Daniel Dias, "Design and Performance of a Web Server Accelerator," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We describe the design, implementation and performance of a Web server accelerator which runs on an embedded operating system and improves Web server performance by caching data. The accelerator resides in front of one or more Web servers. Our accelerator can serve up to 5000 pages/second from its cache on a 200 MHz PowerPC. This throughput is an order of magnitude higher than that which would be achieved by a high-performance Web server running on similar hardware under a conventional operating system such as Unix or NT. The superior performance of our system results in part from its highly optimized communications stack. In order to maximize hit rates and maintain updated caches, our accelerator cache provides API's which allow application programs to explicitly add, delete, and update cached data. We analyze the SPECweb96 benchmark, and show that the cache can provide high hit ratios and excellent performance for workloads similar to this benchmark.
Keywords: Internet and experimental systems
Martin Reisslein, Keith Ross and Srini Rajagopal, "Guaranteeing Statistical QoS to Regulated Traffic: The Single Node Case," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Multimedia traffic can tolerate some loss but has rigid delay constraints. A natural QoS requirement for a multimedia connection is a prescribed bound on the the fraction of traffic that exceeds an end--to--end delay limit. We propose and analyze a traffic management schemes which guarantees QoS to multimedia traffic while simultaneously allowing for a large connection-carrying capacity. We study our traffic management scheme in the context of a single node. In order for the node to guarantee QoS, each connection's traffic is regulated. In order to support many connections, the link statistically multiplexes the connections' traffic. The scheme consists of (i) cascaded leaky-buckets for traffic regulation, (ii) smoothers at the ingresses, and (iii) bufferless statistical multiplexing within the node. For this scheme we show that loss probabilities are minimized with simple one--buffer smoothers which operate at specific minimum rates. We also show that the worst--case input traffic is extremal on--off traffic for all connections. These two results lead to a straightforward scheme for guaranteeing QoS to regulated traffic. Using MPEG video traces, we present numerical results which demonstrate the methodology. Finally, we compare the bufferless scheme with buffered statistical multiplexing.
Keywords: Traffic management; scheduling
Chi Wan Sung and Wing Wong, "Power Control for Multirate Multimedia CDMA Systems," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We consider a wireless multimedia CDMA system, in which the terminals transmit at different rates. We formulate the problem as a constrained optimization problem, with the objective of maximizing the total effective rate. An optimal power control strategy is derived. When the scale of the system is large, the optimal solution takes a simple form, which is easy to be applied practically. Furthermore, our basic model can be extended to include delay-sensitive traffic. We have shown that the problem can be decoupled and our results are still valid in the general model.
Keywords: Wireless
Kevin Lai and Mary Baker, "Measuring Bandwidth," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Accurate network bandwidth measurement is important to a variety of network applications. Unfortunately, accurate bandwidth measurement is difficult. We describe some current bandwidth measurement techniques: throughput, pathchar, and Packet Pair. We explain some of the problems with these techniques, including poor accuracy, poor scalability, lack of statistical robustness, poor agility in adapting to bandwidth changes, lack of flexibility in deployment, and inaccuracy when used on a variety of traffic types. Our solutions to these problems include the use of a packet window to adapt quickly to bandwidth changes, the use of Receiver Only Packet Pair to combine accuracy and ease of deployment, and the use of Potential Bandwidth Filtering to increase accuracy more than 37\% over previously used filtering algorithms.
Keywords: Performance analysis and modeling
Supratik Bhattacharyya, Don Towsley and Jim Kurose, "The Loss Path Multiplicity Problem in Multicast Congestion Control," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: An important concern for source-based multicast congestion control algorithms is the loss path multiplicity (LPM) problem that arises because a transmitted packet can be lost on one or more of the many end-to-end paths in a multicast tree. Consequently, if a multicast source's transmission rate is regulated according to loss indications from receivers, the rate may be completely throttled as the number of loss paths increases. In this paper, we analyze a family of additive increase multiplicative decrease congestion control algorithms and show that, unless careful attention is paid to the LPM problem, the average session bandwidth of a multicast session may be reduced drastically as the size of the multicast group increases. This makes it impossible to share bandwidth in a \{\em max-min fair\} manner among unicast and multicast sessions. We show that max-min fairness can be achieved however, if every multicast session regulates its rate according to the most congested end-to-end path in its multicast tree. We present an idealized protocol for tracking the most congested path under changing network conditions, and use simulations to illustrate tnat tracking the most congested path is indeed a promising approach.
Keywords: Congestion control
Matthias Grossglauser and David N. C. Tse, "A Time-Scale Decomposition Approach to Measurement-Based Admission Control," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We propose a time-scale decomposition approach to measurement-based admission control (MBAC). We identify a \{\em critical time-scale\} $\sth$ such that: 1) aggregate traffic fluctuation slower than $\sth$ can be tracked by the admission controller and compensated for by flow admissions; 2) fluctuations faster than $\sth$ have to be absorbed by reserving spare bandwidth on the link. A MBAC design is presented which filters aggregate measurements into low and high frequency components separated at the cutoff frequency $1/\sth$, using the low frequency component to track slow time-scale traffic fluctuations and the high frequency component to estimate the spare bandwidth needed. Our analysis shows that the scheme achieves high utilization and is robust to traffic heterogeneity, multiple time-scale fluctuations and measurement errors. The scheme uses only measurements of aggregate bandwidth and does not need to keep track of per-flow information.
Keywords: Performance analysis and modeling
Suresh Kalyanasundaram, Junyi Li, Edwin Chong and Ness Shroff, "Channel Sharing Scheme For Packet-Switched Cellular Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In this paper, we study an approach for sharing channels to improve network utilization in packet-switched cellular networks. Our scheme exploits unused resources in neighboring cells without the need for global coordIn this paper, we study an approach for sharing channels to improve network utilization in packet-switched cellular networks. Our scheme exploits unused resources in neighboring cells without the need for global coordination. We formulate a minimax approach to optimizing the allocation of channels in this sharing scheme. We develop a distributed algorithm to achieve this objective and study its convergence. We illustrate, via simulation results, that the distributed channel sharing scheme performs better than the fixed channel scheme over a wide variety of traffic conditions. ination. We formulate a minimax approach to optimizing the allocation of channels in this sharing scheme. We develop a distributed algorithm to achieve this objective and study its convergence. We illustrate, via simulation results, that the distributed channel sharing scheme performs better than the fixed channel scheme over a wide variety of traffic conditions.
Keywords: Wireless
Zhi-Li Zhang, Srihari Nelakuditi, Rahul Aggarwal and Rose Tsang, "Efficient Selective Frame Discard Algorithms for Stored Video Delivery across Resource Constrained Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Video delivery from a server to a client across a network is an important component of many multimedia applications. While delivering a video stream across a resource constrained network, loss of frames may be unavoidable. Under such circumstances, it is desirable to find a server transmission schedule that can efficiently utilize the network resources while maximizing the perceived quality-of-service (QoS) at the client. To address this issue, in this paper we introduce the notion of {\em selective frame discard} at the server and formulate the {\em optimal selective frame discard} problem using a QoS-based cost function. Given network bandwidth and client buffer constraints, we develop an $O(N\log N)$ algorithm to find the minimum number of frames that must be discarded in order to meet these constraints. The correctness of the algorithm is also formally established. Since the computational complexity of the optimal algorithm for solving the optimal selective frame discard problem is prohibitively high in general, we also develop several efficient heuristic algorithms for selective frame discard. These algorithms are evaluated using JPEG video traces.
Keywords: Multimedia
Abel Dasylva and R. Srikant, "Bounds on the Performance of Admission Control and Routing Policies for General Topology Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We consider the problem of obtaining non-trivial upper bounds on the the lost revenue under any routing and admission control scheme in a multi-class loss network. First, we use the following simple idea to bound the performance of any coordinate-convex admission policy on a single link: the blocking probability of any call class is lower bounded by considering just this class in isolation and replacing the available bandwidth (a random quantity) by its mean. Then, we use this single-link bound to obtain linear programs which give bounds in the case of sparsely connected networks with multiple bandwidth classes.
Keywords: Performance analysis and modeling
Juerg Bolliger, Thomas Gross and Urs Hengartner, "Bandwidth Modelling for Network-Aware Applications," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Network-aware applications attempt to adjust their resource demands in response to changes in resource availability. E.g., if a node (server) maintains a connection to a client, the server may want to adjust the amount of data sent to the client based on the effective bandwidth realized for the connection. Information about current and future network performance is therefore crucial for an adaptive application. This paper discusses three aspects of the coupling of applications and networks: (1) a network-aware application needs timely information about the status of the network; (2) a simple bandwidth estimation technique performs reasonably well for TCP-Reno connections without timeouts; (3) enhancements proposed to TCP-Reno to reduce the number of timeouts (i.e., SACKs and its variants) increase the bandwidth but also improve the accuracy of bandwidth estimators developed by other researchers. The empirical observations reported in this paper are based on the records of an in-vivo experiment in the Internet. Over a 3-month period, we logged the micro dynamics of random connections between a set of selected hosts. These results are encouraging for the developers of network-aware applications since they provide evidence that indeed a simple widening of the interface between applications and network (protocol) may be able to provide the information that is necessary to allow an application to adapt successfully. keywords: protocol performance modelling, internet experiment, support for adaptive applications
Keywords: Communications protocols and software
Khosrow Sohraby and Alex Privalov, "End-to-End Jitter Analysis in Networks of Periodic Flows," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Constant Bit Rate (CBR) traffic is expected to be an important traffic source in high-speed networks. Such sources usually have stringent delay and loss requirements and in many cases they should be delivered exactly as they were generated. A simple delay priority scheme in the network nodes will bound the delay and delay jitter for CBR traffic so that the CBR flows with stringent QoS will only compete with similar traffic flows within the network. In this paper, we extend the work in \cite{PriSoh1} to a networking environment and provide the end-to-end jitter analysis of feed-forward connection-oriented networks supporting multiplexed CBR connections. The impact of the traffic mix in each node and the number of nodes in the network on the end-to-end jitter of individual flows are examined.
Keywords: Performance analysis and modeling
Chuanyi Ji, Sheng Ma and Xusheng Tian, "Approximation Capability of Independent Wavelet Models to Heterogeneous Network Traffic," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: In our previous work, we showed empirically that independent wavelet models were parsimonious, computationally efficient, and accurate in modeling heterogeneous network traffic measured by both auto-covariance functions and buffer loss rate. In this work, we focus on auto-covariance functions, to establish the theory on independent wavelet models as unified models for heterogeneous network traffic. We have developed theory on approximation capability of independent wavelet models for heterogeneous traffic in terms of the decay rate of auto-covariance functions at large lags. Averaged auto-covariance functions of independent wavelet models have been derived and shown to be linear combinations of basis functions. Through the simple analytical expression, we have shown that the decay rate of the auto-covariance functions of independent wavelet models is determined explicitely through a single quantity called the rate function of variances of wavelet coefficients. By specifying analytical forms of the rate function, independent wavelet models have been shown as unified models to heterogeneous traffic in terms of auto-covariance function. The simplicity of the theory thereby provides both quantitative and qualitative explanations why independent wavelet models are unified models of heterogeneous traffic.
Keywords: Performance analysis and modeling
Teunis J. Ott, T. V. Lakshman and Larry H. Wong, "SRED: Stabilized RED," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper describes a mechanism we call ``SRED'' (Stabilized Random Early Drop). Like RED (Random Early Detection) SRED pre-emptively discards packets with a load-dependent probability whern a buffer in a router in the Internet or an Intranet seems congested. SRED has an additional feature that over a wide range of load levels helps it stabilize its buffer occupation at a level independent of of the number of active connections. SRED does this by estimating the number of active connections or flows. The same mechanism can be used to identify flows that may be misbehaving, i.e. are taking more than their fair share of bandwidth. Since the mechanism is statistical in nature, the next step must be to collect state information of the candidates for ``misbehaving'', and to analyze that information. We show that the candidate flows thus identified have a high posterior probability of taking a larger than average amount of bandwidth.
Keywords: Congestion control
Kang-Won Lee, Sungwon Ha and Vaduvur Bharghavan, "IRMA: A Reliable Multicast Architecture for the Internet," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: IRMA is a reliable multicast architecture that guarantees reliable, sequenced, and loosely synchronized delivery of multicast streams. IRMA provides ACK-based reliability, hybrid local server-initiated and sender-initiated loss recovery, and support for end-to-end flow control and congestion control. Unlike most contemporary work, IRMA supports TCP as the reliable 'multicast' transport protocol at the end host without modifications. IRMA has been instantiated in a laboratory testbed, and its performance has been measured in various scenarios. Preliminary performance results show that IRMA is efficient and adaptive to the dynamics of the network.
Keywords: Routing & Multicasting
John Daigle and Matthew Roughan, "Queue-Length Distributions for Multi-Priority Queueing Systems," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: Many telecommunication systems provide priority service on the basis of either fee for service or perceived relative importance. Lower priority traffic may either be delayed or denied service. In many cases, the bottleneck in such a system can be, and has been, modeled by an M/G/1 queueing system having either non-preemptive or preemptive resume service. The probability generating function for the occupancy distribution of the various traffic classes can be obtained, and from this the moments of the occupancy distributions may be calculated. On the other hand, occupancy distributions themselves have been obtainable in only in a few specific cases. Indeed, the \PGF\ itself is not expressible in closed form for the lower priority traffic. However, the occupancy distribution is of great importance, particularly in those not unrealistic models where the moments are not all finite. In this paper, we consider the problem of obtaining occupancy distributions for the M/G/1 queueing system with HOL priority. Specifically, we develop a method for obtaining the occupancy distributions based on fast Fourier transform technique, using the probability generating function and known properties of the tail probabilities. We demonstrate the validity of our approach by actually obtaining the occupancy distributions for a number of service time distributions -- including cases with regularly varying service time distributions.
Keywords: Performance analysis and modeling
S. Y. Wang and H. T. Kung, "A Simple Methodology for Constructing Extensible and High-Fidelity TCP/IP Network Simulators," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: This paper proposes a simple methodology for constructing extensible and high-fidelity TCP/IP simulators in BSD UNIX environments. A simulator constructed under this methodology will simulate multiple network nodes by re-entering the UNIX kernel of the simulation host multiple times. Generated simulation results are derived from executing the native TCP/IP protocol stack on the simula tion host. They are thus more accurate than those generated from a TCP/IP network simulator that implements only an abstraction of a real-life TCP/IP implementation. By using this methodology, the simulator architecture creates an illusion for the BSD UNIX kernel that the simu lated network is a real network. All existing application programs such as ftp, telnet and http, and all network utili ties such as route, ifconfig and tcpdump are immediately applicable to a simulated network for generating network traffic, configuring networks, gathering statistics, etc. Addi tionally, the network simulator provides the standard UNIX API on every node in a simulated network so that any existing or future application program can run on any node in a simulated network. This allows a network simulator to be easily extended to study high-level network architecture and application issues.
Keywords: Performance analysis and modeling
Parameswaran Ramanathan, Krishna Sivalingam, Prathima Agrawal and Shalinee Kishore, "Resource Allocation During Handoff Through Dynamic Schemes for Mobile Multimedia Wireless Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: User mobility management is one of the important components of mobile multimedia systems. In a cell-based network, a mobile should be able to seamlessly obtain transmission resources after handoff to a new basestation. This is essential for both service continuity and quality of service assurance. In this paper, we present strategies for accommodating continuous service to mobile users through estimating resource requirements of potential handoff connections. A diverse mix of heterogeneous traffic with diverse resource requirements is considered. We investigate static and dynamic resource allocation schemes. The dynamic scheme probabilistically estimates the potential number of connections that will be handed off from neighboring cells, for each class of traffic. The performance of these strategies in terms of connection blocking probabilities for handoff and local new connection requests are evaluated. The performance is also compared to a scheme previously proposed in [1]. The results indicate that using dynamic estimation and allocation, we can significantly reduce the dropping probability for handoff connections.
Keywords: Wireless
Subhabrata Sen, Jennifer Rexford and Don Towsley, "Proxy Prefix Caching for Multimedia Streams," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: High latency and loss rates in the Internet make it difficult to stream audio and video without introducing a large playback delay. To address these problems, we propose a {\em prefix caching\/} technique whereby a proxy stores the initial frames of popular clips. Upon receiving a request for the stream, the proxy initiates transmission to the client and simultaneously requests the remaining frames from the server. In addition to hiding the delay, throughput, and loss effects of a weaker service model between the server and the proxy, this novel yet simple prefix caching technique aids the proxy in performing {\em workahead smoothing\/} into the client playback buffer. By transmitting large frames in advance of each burst, workahead smoothing substantially reduces the peak and variability of the network resource requirements along the path from the proxy to the client. We describe how to construct a smooth transmission schedule, based on the size of the prefix, smoothing, and playback buffers, without increasing client playback delay. Experiments with MPEG traces show how a few megabytes of buffer space at the proxy can substantially reduce the bandwidth requirements of variable-bit-rate video. Drawing on these results, we present guidelines for allocating buffer space for each stream, and how to effectively share buffer and bandwidth resources among multiple clients and streams.
Keywords: Multimedia
George Xylomenos and George Polyzos, "TCP and UDP Performance over a Wireless LAN," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999.
Abstract: We present a comprehensive set of measurements of a 2.4 GHz DSSS wireless LAN and analyze its behavior. We examine issues such as host and interface heterogeneity, bidirectional (TCP) traffic and error modeling, that have not been previously analyzed. We uncover multiple problems with TCP and UDP performance in this system. We investigate the causes of these problems (radio hardware, device drivers, network protocols) and discuss the effectiveness of proposed improvements.
Keywords: Wireless
netbib software created by H. Schulzrinne. Report problems to schulzrinne@cs.columbia.edu. Wed Mar 08 17:33:52 EST 2000