in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 222, Apr. 1997.Anup K. Talukdar, B. R. Badrinath and Arup Acharya, "On accomodating mobile hosts in Integrated Services Packet Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: This paper considers the support of real-time applications to mobile hosts in an integrated services packet network. We have proposed a service model for mobile hosts that can support adaptive applications which can withstand a range of available bandwidth, as well as applications which require mobility independent service guarantees. We describe an admission control scheme and a reservation protocol for implementing this service model. Our admission control scheme achieves high utilization of network resources.
Keywords: RSVP; mobile users; resource reservation
Y.-D. Lin, C.-J. Wu and W.-M. Yin, "PCUP: Pipelined Cyclic Upstream Protocol over Hybrid Fiber Coax," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: In order to span NII (National Information Infrastructure) into the homes, the community cable TV networks have to be re-engineered to support two-way interactive services. In this work, we propose PCUP (Pipelined Cyclic Upstream Protocol) as the upstream MAC (Medium Access Control) protocol for HFC (Hybrid Fiber Coax) community access network. PCUP is designed with the intention of pipelining the upstream channel. This is achieved by proper station positioning, which measures the station propagation offset from the headend, and transmission scheduling, which assigns each station the transmission starting time and duration in a cycle. By taking into account the propagation offsets and the transmission times, transmitted cells can appear back-to-back, i.e. pipelined, at the headend. Since only the active stations are scheduled to transmit in a cycle, a membership control mechanism, which runs a contention-based tree walk algorithm, is executed periodically to allow the stations to join or leave. We also compare PCUP with various schemes proposed to IEEE 802.14 committee.
A. K. Talukdar, B. R. Badrinath and A. Acharya, "On Accommodating Mobile Hosts in an Integrated Services Packet Network," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1046, Apr. 1997.
Abstract: This paper considers the support of real-time applications to mobile hosts in an Integrated Services Packet Network. We have proposed a service model for mobile hosts that can support adaptive applications which can withstand wide range of available bandwidth, as well as applications which require mobility independent service guarantees. We describe an admission control scheme and a reservation protocol for implementing this service model. Our admission control scheme achieves high utilization of network resources.
A. K. Talukdar, B. R. Badrinath and A. Acharya, "On Accommodating Mobile Hosts in an Integrated Services Packet Network," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1046, Apr. 1997.
Abstract: This paper considers the support of real-time applications to mobile hosts in an Integrated Services Packet Network. We have proposed a service model for mobile hosts that can support adaptive applications which can withstand wide range of available bandwidth, as well as applications which require mobility independent service guarantees. We describe an admission control scheme and a reservation protocol for implementing this service model. Our admission control scheme achieves high utilization of network resources.
E. Aharoni and R. Cohen, "Restricted Dynamic Steiner Trees for Scalable Multicast in Datagram Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 876, Apr. 1997.
Abstract: The paper addresses the issue of minimizing the number of nodes involved in the routing over a muhicast tree and in the maintenance of such a tree in a datagram network. It presents a scheme where the tree routing and maintenance burden is laid only upon the source node and the destination nodes associated wtth the multicast tree. The main concepts behind this scheme is to view each multicast tree as a collection of unicast paths and to locate only the multicast source and destination nodes on the junctions of their multicast tree. The paper shows that despite of this restriction, the cost of the created multicast trees is not necessarily higher than the cost of the trees created by other algorithms that do not impose the restriction and therefore require all the nodes along the data path of a tree to participate in the routing over the tree and in the maintenance of the tree.
M. Ajmon Marsan, A. Bianco, E. Leonardi, F. Neri and S. Toniolo, "MetaRing Fairness Control Schemes in All-Optical WDM Rings," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 752, Apr. 1997.
Abstract: WDM rings are receiving significant attention in the field of all-optical networks because their implementation appears to be feasible with state-of-the-art components. Several MAC protocols were recently proposed in order to resolve contentions among nodes sharing the available wavelengths in WDM rings. These MAC protocols achieve high efficiency but unsatisfactory fairness, due to the asymmetric position of sources with respect to destinations. Thus, in order to improve fairness, it is necessary to adopt a fairness control scheme. In this paper we discuss the adaptation of the MetaRing fairness control scheme to the context of WDM multi-channel rings. Several alternatives are considered and compared via simulation.
M. Ajmone Marsan, A. Bianco, E. Leonardi, A. Morabito and F. Neri, "SR^3: A Bandwidth-Reservation MAC Protocol for Multimedia Applications Over All-Optical WDM Multi-Rings," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 761, Apr. 1997.
Abstract: The paper descrabes SR^3 (Synchronous Round Robin with Reservations), a collision-free medium access control protocol for all-optical slotted packet networks based on WDM multi-channel ring topologies where nodes are equipped with one fixed-wavelength receiver and one wavelength-tunable transmitter. SR^3 is derived from the SRR and MMR protocols previously proposed by the same authors for the same class of all-optical networks. SRR and MMR already achieve an eficient exploitation of the available bandwidth, while guaranteeing a throughput-fair access to each node. SR^3, in addition, allows nodes to reserve slots, thereby achieving a stronger control on access delays; it is thus well suited to meet tight delay requirements, as it is the case for multimedia applications. Simulation results show that SR3 provides very good performance to guaranteed quality traffic, but also brings significant performance improvements for best-effort traffic.
I. F. Akyildiz, W. Yen and B. Yener, "A New Hierarchical Routing Protocol for Dynamic Multihop Wireless Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1422, Apr. 1997.
Abstract: The routing techniques used in conventional packet radio networks are not suitable for dynamic multihop wireless networks because of their unique architecture. In this paper, a new hierarchical multihop routing algorithm is introduced which balances the cost of location-update and path-finding operations by partitioning the terminals and mobile base stations to produce a virtual topology. Based on the virtual topology, each network entity stores a fraction of the network topology information and maintains the routing eficiency. Finally, the performance of the hierarchical multihop routing algorithm is investigated through simulations.
K. C. Almeroth, A. Dan, D. Sitaram and W. H. Tetzlaff, "Long Term Resource Allocation in Video Delivery Systems," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1333, Apr. 1997.
Abstract: In typical video delivery systems offering programs on-demand, service should be be nearly immediate and continuous. A video server can provide this type of service by reserving suficient network and server resources for the duration of playout. Scalability and reduced cost can be achieved using a single channel to serve multiple customers waiting for the same program (referred to as batching). Batching is especially useful during high load periods typically occuring during evening prime time hours. Typical channel allocation algorithms use a greedy, allocate-as-needed policy. Variations in system load can cause these algorithms to suffer poor and unpredictable short-term performance, and non-optimal long term performance. In this paper, we develop a set of realistic workloads, identify the limitations of greedy allocation algorithms, and propose a set of rate-based allocation schemes to solve these limitations. The performance of various video delivery systems are simulated and compared. The rate-based policies are shown to be robust for the workloads examined, and are easy to implement.
A. T. Andersen and B. F. Nielsen, "An Application of Superpositions of Two-State Markovian Sources to the Modelling of Self-Similar Behaviour," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 196, Apr. 1997.
Abstract: We present a modelling framework and a fitting method for modelling second order self-similar behaviour with the Markouian Arrival Process (MAP). The fitting method is based on fitting to the autocorrelation function of counts for a second order self-similar process. It is shown that with this fitting algorithm it is possible closely to match the autocorrelation function of counts for a second order self-similar process over 3-5 time-scales with 8-16 state MAPs with a very simple structure i.e. a superposition of 3 respectively 4 Interrupted Poisson Processes (IPP) and a Poisson process. The fitting method seems to work well over the entire range of the Hurst parameter.
J. Armitage, O. Crochat and J. Y. Le Boudec, "Design of a Survivable WDM Photonic Network," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 244, Apr. 1997.
Abstract: We consider schemes for protecting a network using a Wavelength Division Multiplexing (WDM) infrastructure against component or link failures. First, we explain how protection can be achieved by hardware redundancy. Then, we consider that with WDM networks, the failure of a single link or component may cause the simultaneous failure of several optical channels, potentially making impossible the restoration by rerouting in higher layers (SDH, ATM, 1P). To address this, we introduce the concept of Design Protection, which aims at making such failure propagations impossible. We present the Disjoint Alternate Path (DAP) algorithm which places optical channels in order to maximise design protection. We show the result on the example of the ARPA-2 network.
S. Subramaniam, A. K. Somani, M. Azizoglu and R. A. Barry, "," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 499, Apr. 1997.
Abstract: This paper makes the first known attempt to study wavelength-routing networks and the effects of wavelength conversion under dynamic non-Poisson traffic. An approximation that characterizes any non-Poisson traffic by its first two moments is utilized. The arrival occupancy distribution of busy wavelengths for this approximate process is derived and is used to analyze the effects of wavelength conversion. The model predicts that traffic peakedness plays an important role in determining the blocking performance, and also that wavelength conversion gain is insensitive to traffic peakedness over a large range.
A. K. Somani and M. Azizoglu, "All-Optical LAN Interconnection with a Wavelength Selective Router," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1278, Apr. 1997.
Abstract: This paper formulates the wavelength assignment issues in interconnecting optical broadcast-star Local Area Networks (LANs) through a wavelength routing bridge. Static and dynamic approaches to partitioning of wavelengths for local and global traffic are compared using analysis and simulations. It is found that static wavelength assignment, the easiest algorithm to implement, is significantly outperformed by dynamic algorithms. Several dynamic assignment algorithms are developed, and architectural issues in interconnecting optical networks are discussed. The dependence of the call blocking performance on system parameters, such as the traffic rate, the local and global traffic statistics, and the number of available wavelengths is examined in detail. A simple, yet accurate approximation is also developed to predict the blocking performance with an arbitrary number of LANs.
H. Choi, H. A. Choi and M. Azizoglu, "On the All-to-All Broadcast Problem in Optical Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1286, Apr. 1997.
Abstract: This paper considers the transmission of uniform deterministic traffic in an optical broadcast-star network using Wavelength Division Multiplexing. Lower bounds are established on the minimum time to exchange information between every node pair in such a network with tunable transmitters and fixed-tuned receivers. Three different scheduling algorithms are developed that are strictly optimal in three regimes of system parameters. The results are applicable to arbitrary tuning delays and arbitrary numbers of wavelength channels, and indicate the existence of a well-defined transition regime from tuning-limited operation to bandwidth-limited operation.
M. Baldi, Y. Ofek and B. Yener, "Adaptive Real-Time Group Multicast," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 683, Apr. 1997.
Abstract: This paper shows how to provide an adaptive real-time group multicast (many-to-many) communication service. Such a service can be used by applications, like audio/video tele-conferencing, that require low loss, and bounded delay and jitter. In order to meet deterministic quality of service (QoS) requirements of a real-time group multicast, some communication resources are reserved. In this work we show (i) how bandwidth is reserved for each group, and (ii) how an active user in a multicast group can dynamically share, in an efficient and fair manner, the bandwidth allocated to its group. Quality of service support for a real-time multicast group is based on time driven priority [3]. In this scheme the time is divided into time frames of fixed duration and all the time frames are aligned by using a global time reference which can be obtained from GPS (global positioning system). Bandwidth is allocated to a multicast group as a whole, rather than individually to each user. The allocation is done by reserving time intervals within time frames in some periodic fashion. This sort of allocation raises two problems that are studied in this paper: (1) Scheduling: how time intervals are reserved to each multicast group, and (2) Adaptive sharing: how the participants dynamically share the time intervals that have been reserved for their multicast group. The proposed approach is based on embedding multiple virtual rings, one for each multicast group. By using the virtual rings it is simple to route messages to all the participants, while minimizing the bound on the buffer sizes and queuing delays.
J. M. Rulnick and N. Bambos, "Power Control and Time Division: The CDMA versus TDMA Question," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 634, Apr. 1997.
Abstract: For wireless networks, time division multiple access (TDMA) offers certain well-known advantages over methods such as spread spectrum code division (CDMA). Foremost among them is the guarantee that other users will not interfere during a node’s dedicated time slots. For this desirable isolation, the cost is synchronization. Viewing arbitrary time intervals as potential TDMA time slots, we ask whether it is possible to obtain some of the benefit of time division without incurring the synchronization cost. In particular, we address the question of whether a TDMA-like state can be induced on asynchronous channels in such a way as to reduce interference and energy consumption. Through analysis and simulation we find conditions under which it is desirable to use time division. We then show how autonomous power management may be used as a mechanism to induce a form of time division. In this context a backlog-sensitive power management system is presented.
D. Banerjee and B. Mukherjee, "Wavelength-Routed Optical Networks: Linear Formulation, Resource Budgeting Tradeoffs, and a Reconfiguration Study," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 269, Apr. 1997.
Abstract: We consider a wavelength-routed optical network operated as a lightpath-based virtual topology. We present an exact linear programming formulation for the complete virtual topology design, including choice of constituent Iightpaths, routes for these lightpaths, and intensity of packet flows through these lightpaths. By making a shift in the objective function to minimal hop distance and by relaxing the wavelength-continuity constraints (i.e,, assuming wavelength converters at all nodes), we demonstrate that the entire optical network design problem can be linearized and hence solved optimally. The linear formulation can be used to design a balanced network, such that the utilizations of both transceivers and wavelengths are high, i.e., neither of these expensive resources are underutilized. We also use the linear formulation to provide a reconfiguration methodology in order to adapt the virtual topology to changing traffic conditions.
R. Kannan, R. Bartos, K. Y. Lee and H. F. Jordan, "STWnet: A High Bandwidth Space-Time-Wavelength Multiplexed Optical Switching Network," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 777, Apr. 1997.
Abstract: We propose STWnet, a self-routing high bandwidth optical network architecture for interconnecting users, grouped together as g groups with w users per group. STWnet uses the three dimensions of space, time, and wavelength by combining the advantages of space and temporal switching with the benefits of wavelength parallel data transmissions. Technologically difficult switching of individual wavelengths is avoided by prearranging transmissions in a way that they can be switched in a wavelength insensitive manner. Wavelengths are reused within the network thus allowing for a larger switching fabric. The proposed architecture can be internally expanded either in the spatial or temporal dimension to allow for multiple packets to be delivered to the same destination group. The expansion factor is determined based on the Group Knockout Principle and given typical trafic patterns is a small number. STWnet allows easy group to group multicasting and broadcasting while system-wide multi casts and broadcasts can be achieved through repetitive group-to-group transmissions. The network uses readily available components such as opto-electronic directional couplers, fixed wavelength transmitters, and diffraction based parallel receivers while avoiding the use of relatively slow and expensive tunable components.
S. Gorinsky, S. Baruah, T. J. Marlowe and A. D. Stoyenko, "Exact and Efficient Analysis of Schedulability in Fixed-Packet Networks: A Generic Approach," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 584, Apr. 1997.
Abstract: A general model for traffic flows on packet-switched, virtual-circuit based, fixed-packet networks is introduced, and an exact schedulability test is obtained for systems of such flows. Rules are derived that make the evaluation of this schedulability test feasible and efficient under certain circumstances. The practical relevance of this approach is demonstrated by applying it to a number of standard traffic models.
C. E. Rohrs and R. A. Berry, "A Linear Control Approach to Explicit Rate Feedback in ATM Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 277, Apr. 1997.
Abstract: Rate-based feedback congestion control has been proposed as a form of traffic management for available bit rate traffic in ATM networks. This paper discusses applying linear control theory to these algorithms. A congestion control scheme for simple networks is designed and analyzed using the tools of classical control theory. This allows insight into the trade-offs in such schemes and suggests approaches to larger networks.
A. Bestavros and G. Kim, "TCP BOSTON: A Fragmentation-Tolerant TCP Protocol for ATM Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1210, Apr. 1997.
Abstract: We propose a new transport protocol, TCP Boston, that turns ATM's 53-byte cell-oriented switching architecture into an advantage for TCP/IP. At the core of TCP Boston is the Adaptive Information Dispersal Algorithm (AIDA), an efficient encoding technique that allows for dynamic redundancy control. AIDA makes TCP/IP's performance less sensitive to cell losses, thus ensuring a graceful degradation of TCP/IP's performance when faced with congested resources. In this paper, we introduce AIDA and overview the main features of TCP Boston. We present detailed simulation results that show the superiority of our protocol when compared to other adaptations of TCP/IP over ATMs.
M. P. Maher and S. K. Bhogavilli, "Implementation and Analysis of IP Multicast over ATM," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 858, Apr. 1997.
Abstract: Today it is evident that ATM technology will have its role in the future of Internetworking. Two major Internet backbone service providers, Sprint and MCI, have marketed their investments in ATM as a way to push more bandwidth into their Internet infrastructures. Regardless of whether ATM technology will thrive in the WAN or LAN, it is also evident that the Internet Protocol (IP), which has been the glue of the Internet allowing it to endure exponential growth, must be well supported over ATM. IP multicast (protocol extensions to IP that allow IP packets from one source to be distributed to multiple destinations) is an essential part of IP which has allowed multimedia applications, for example, to more efficiently use Internet resources. In this paper we describe an implementation of one model of supporting IP multicast over ATM, the Multicast over ATM model [1] developed by the IETF. We discuss empirical measurements gathered in a testbed with both a WAN and a LAN component that give insights into the behavior of this model. We detail some of the shortcomings of this model and discuss potential modifications to improve it. Ideas for other approaches to IP multicast over ATM are also described.
G. Bianchi and R. Melen, "Non Stationary Request Distribution in Video on Demand Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 711, Apr. 1997.
Abstract: Several works have recently appeared in the literature on the design, performance and dimensioning of networks supporting Video on Demand and Multimedia services. It has been shown that performance is strongly dependent on the model adopted to describe the user’s behaviour in terms of requests for programs. In this paper we provide a detailed investigation of a non stationary model for the user’s request distribution. Numerical results are provided for a network scenario proposed in the literature to investigate the error achieved when the non stationary distribution is approximated with a stationary exponential one.
J. Nonnenmacher and E. W. Biersack, "Performance Modelling of Reliable Multicast Transmission," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 471, Apr. 1997.
Abstract: Our aim is to investigate reliable transmission for multicast communication and explore its relationship to multicast routing. We derive two characterizations that enable the comparison of routing algorithms and error recovery mechanisms with respect to the multicast tree topology, namely the probability mass function of successful receptions and the expected number of retransmisstons needed to deliver a packet from the source to all receivers. We also give a tight approximation of the computationally expensive expected number of retransmissions. These expressions allow to explore the relationship between routing and error recovery for multicast communication. We finally evaluate the impact of routing algorithms on the performance of reliable multicast transmission and give a realistic generic model for a multicast tree.
S. K. Biswas and B. Sengupta, "Call Admissibility for Multirate Traffic in Wireless ATM Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 649, Apr. 1997.
Abstract: For multirate wireless ATM traffic, the first part of the call admission process is to determine whether to admit calls as long as bandwidth is available or to deny admission to a call of a particular class even if there is enough bandwidth available, in the hope of admitting calls of some other class later. A second part of the process is to determine if the quality of service requested by the call can be met. A scenario in which the first part is particularly important is when the blocking probability requirements for different classes is different. In this paper, we consider four policies to determine the circumstances under which calls of different types are admissible. For each of these policies, we show how to compute the blocking probabilities. For three of these policies, the blocking probabilities can be found by using results from product form networks. For the fourth, we provide an approximation which works extremely well in practice. We also formulate a non-linear programming problem which attempts to determine the parameters of the admissibility policies in such a way to maximize the call arrival rates while keeping the blocking probabilities under specified bounds. We provide an algorithm for solving the non-linear programming problem and use this as a basis for comparing the policies. We show that under some circumstances, it is possible to improve the system throughput by as much as 35% by a suitable use of the admissibility policies. This improvement in throughput is particularly important in wireless ATM networks, supporting high rate multimedia traffic because of the inherent limitations in bandwidth availability.
S. Böcking, "Object-Oriented Network Protocols," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1247, Apr. 1997.
Abstract: A wide-range of various network communication services and protocols is required to efficiently support the diverse networks and their applications. It is usual to design a protocol for each new service which is required. An attractive alternative is to use a modular and object-oriented architecture for the design and implementation of network protocols. With it, protocols for individual service provision can be created by simply combining generic protocol functions blocks. The first part of this paper presents a new reference model which gives a foundation for the object-oriented design and implementation of modular network protocols. The second part discusses a case study of an existing object-oriented network communication system.
Jennifer Rexford, Albert Greenberg, Flavio Bonomi and Albert Wong, "A Scalable Architecture for Fair Leaky-Bucket Shaping," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1054, Apr. 1997.
Abstract: This paper presents a shaper architecture that scales to a large number of connections with diverse burstiness and bandwidth parameters. The architecture arbitrates fairly between connections with conforming cells by carefully integrating leaky-bucket traffic shaping with rate-based scheduling algorithms. Through a careful combination of per-connection queueing and approximate sorting, the shaper performs a small, bounded number of operations in response to each arrival and departure, independent of the number of connections and cells. To handle a wider range of rate parameters, a hierarchical arbitration scheme can reduce the implementation overheads and the interference between competing connections. Simulation experiments demonstrate that the architecture limits shaping delay and trafic distortions, even under heavy congestion.
Alexander Schill, Sabine Kühn and Frank Breiter, "Resource Reservation in Advance in Heterogeneous Networks with Partial ATM Infrastructures," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 611, Apr. 1997.
Abstract: Resource reservation in advance (ReRA) enables scheduling and allocation of resources at an early stage in time. This way, the availability of resources can actually be guaranteed for the point in time when the resources are needed. As opposed to that, current reservation protocols such as RSVP perform an ''immediate'' reservation without advance scheduling. They can therefore suffer shortage of resources with subsequent rejection of applications. This paper describes our new approach for providing resource reservation in advance in ATM networks. As a foundation, we first present experiences of IPng and RSVP over ATM. Based on this work, we then discuss major design issues of an appropriate ReRA solution. Important aspects are the signalling model for ReRA, the admission control strategy, the duration of connections, and various other time-related parameters. We also discuss our ongoing implementation of ReRA as an extension of RSVP and outline directions for future research in this area.
José Carlos Brustoloni and Peter Steenkiste, "Copy Emulation in Checksummed, Multiple-Packet Communication," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1122, Apr. 1997.
Abstract: Data copying can be a bottleneck in end-to-end communication over high-speed networks. Emulated copy is an alternative I/O data passing scheme that preserves the API and integrity guarantees of copying but avoids the latter using VM manipulations - transient output copy-on-write (TCOW), input alignment, and page swapping . We characterize and evaluate the support necessary in network adapters for emulated copy in checksummed, multiple-packet communication. Our experiments on an ATM network show that: (1) Emulated copy gives performance better than that of copying even without hardware checksumming support; (2) TCOW improves multiple-packet output performance without any hardware support or changes in applications; (3) Page swapping provides additional similar improvements on multiple-packet input if there is input alignment, which requires either hardware support (early-demultiplexed/ system-aligned buffering) or changes in applications (pooled/application-aligned buffering) ; and (4) The performance of application-aligned buffering is largely unaffected by header/data splitting, a common optimization. We propose a new optimization, buffer snap-off , that extends system-aligned buffering to the general case of arbitrary, unmatched data transfer and application input buffer lengths.
Robert L. Carter and Mark E. Crovella, "Server Selection Using Dynamic Path Characterization in Wide-Area Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1014, Apr. 1997.
Abstract: Replication is a commonly proposed solution to problems of scale associated with distributed services. However, when a service is replicated, each client must be assigned a server. Prior work has generally assumed that assignment to be static. In contrast, we propose dynamic server selection, and show that enables application-level congestion avoidance. Using tools to measure available bandwidth and round trip latency (RTT), we demonstrate dynamic server selection and compare it to previous static approaches. We show that because of the variability of paths in the Internet, dynamic server selection consistently outperforms static policies, reducing response times by as much as 50%. However, we also must adopt a systems perspective and consider the impact of the measurement method on the network. Therefore, we look at alternative low-cost approximations and find that the careful measurements provided by our tools can be closely approximated by much lighter-weight measurements. We propose a protocol using this method which is limited to at most a 1% increase in network traffic but which often costs much less in practice.
Eric W. M. Wong, Andy K. M. Chan and Tak-Shing Peter Yum, "Re-routing in Circuit Switched Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1373, Apr. 1997.
Abstract: Dynamic routing has been adopted in many circuit switched networks in many parts of the world. A number of dynamic routing schemes have been designed and studied with the aim of maximizing the network throughput. The Least Loaded Routtng (LLR) is simple and efficient, while other more elaborate routing schemes can only provide marginal throughput gain over that of LLR. Re-routing is the practice of routing calls on alternate paths to direct paths or other less congested alternate paths. It allows the continuous re-distribution of network loads so that the congestion on direct paths can be relieved. In this paper, we study a re-routing scheme based on LLR. An original analysis of re-routing is performed and numerical examples confirm the significant throughput gain over LLR routing.
C. W. Chan and S. C. Liew, "Performance of Multicasting Closed Interconnection Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 525, Apr. 1997.
Abstract: This paper examines the application of a simple yet general packet replication scheme to achieve multicasting in closed interconnection networks. The performance of these networks is studied and a general throughput equation is obtained to express the overall network throughput in terms of the average routing delay of the corresponding point-to-point network. The multicast performance results are thus built on top of the previously-established, and often simpler, point-to-point results. Making use of this formula, we investigate the multicast closed shuffle-exchange network in detail. Analytical results are compared with simulation results to obtain further insights into the network operation and ways to improve the network performance.
P. Chandra, A. Fisher, C. Kosak and P. Steenkiste, "Experimental Evaluation of ATM Congestion Control Mechanisms," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1324, Apr. 1997.
Abstract: A critical issue in the design of fast packet-switch- based networks is the avoidance of data loss due to congestion. In the context of ATM networks, many link-level congestion control mechanisms for ABR traffic have been proposed and simulated, and a few have been implemented. This paper presents, for the first time, an experimental comparison of several such mechanisms. To drive this comparison, we have developed a set of benchmarks that provide a quantitative characterization of congestion control performance. We also describe a simple but novel technique, the ''virtual port card'', for implementing both non-native switch behavior and long link delays in ATM networks. This technique allows us to compare a wide range of mechanisms on a single flexible hardware platform. Our measurements show that while several of the ATM flow control mechanisms can eliminate cell loss, there are still several unresolved problems. First, for some traffic scenarios we see very poor application-level performance, especially in the presence of bursty traffic. Second, performance is very sensitive to the flow control parameters and identifying an appropriate set of parameters is difficult since it depends heavily on the traffic conditions.
S. Suri, G. Varghese and G. Chandranmenon, "Leap Forward Virtual Clock: A New Fair Queuing Scheme with Guaranteed Delays and Throughput Fairness," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 557, Apr. 1997.
Abstract: We describe an efficient fair queuing scheme, Leap Forward Virtual Clock, that provides end-to-end delay bounds similar to WFQ, along with throughput fairness. Our scheme can be implemented with a worst-case time O (log log N) per packet (inclusive of sorting costs), which improves upon all previously known schemes that guarantee delay and throughput fairness similar to WFQ. Interestingly, both the classical virtual clock and the Self-Clocked Fair Queuing schemes can be thought of as special cases of our scheme, by setting the leap forward parameter appropriately.
T. Chaney, J. A. Fingerhut, M. Flucke and J. S. Turner, "Design of a Gigabit ATM Switch," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 2, Apr. 1997.
Abstract: This paper describes the design and implementation of a gigabit ATM switching system supporting link rates from 150 Mb/s to 2.4 Gb/s, with a uniquely efficient multicast switch architecture that enables the construction of systems with essentially constant per port costs for configurations ranging from 8 to 4096 ports and system capacities approaching 10 Tb/s. The system design supports many-to-one and many-to- many forms of multicast, in addition to the usual one-to-many. It also provides multi cast virtual paths, constant time configuration of multicast connections and an efficient packet-level discard method, that can achieve 100% link efficiencies, without large buffers.
Chung-Ju Chang, Song-Yaor Lin, Ray-Guang Cheng and Yow-Ren Shiue, "PSD-Based Neural-Net Connection Admission Control," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 955, Apr. 1997.
Abstract: ATM (asynchronous transfer mode) systems can support services with bursty trafic. An ATM system needs a sophisticated and real-time connection admission controller not only to guarantee the required quality-of-service (QoS) for existing calls but also to raise the system efficiency. Input process has a power-spectral- density (PSD) which explicitly contains the correlation behavior of input traffic and has a great impact on the system performance. Also, a neural network has been widely applied to deal wtth traffic control related problems in ATM systems because of its self-learning capability. In this paper, we propose a PSD-based neural-net connection admission control (PNCAC) method for an ATM system. Under the QoS constraint, we construct a decision hyperplane of the connection admisston control according to parameters of the power spectrum. We further adopt the learning/adapting capabilities of the neural network to adjust the optimum location of the boundary between these two decision spaces. Simulation results show that the PNCAC method provides a superior system utilization over the conventional CAC schemes by an amount of 18%, while keeping the QoS contract.
Z. D. Dittia, G. M. Parulkar and J. R. Cox Jr., "The APIC Approach to High Performance Network Interface Design: Protected DMA and Other Techniques," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 823, Apr. 1997.
Abstract: We are building a high performance 1.2 Gb/s ATM network interface chip called the APIC (ATM Port Interconnect Controller). In addition to borrowing useful ideas from a number of research and commercial prototypes, the APIC design embraces several innovative features, and integrates all of these pieces into a coherent whole. Some of the novel ideas incorporated in the APIC design include: Protected DMA and Protected I/O, which allow applications to queue data for transmission or reception directly from user-space, effectively bypassing the kernel. This argues for moving the entire protocol stack including the interface device driver into user-space, thereby yielding better latency and throughput performance than kernel-resident implementations. Pool DMA when used with Packet Splitting, is a technique that can be used to build true zero-copy kernel-resident protocol stack implementations, using a page-remapping technique. Finally, Orchestrated Interrupts and Interrupt Demultiplexing are mechanisms used to reduce the frequency of interrupts issued by the APIC. Although many of these ideas have been developed in the context of an ATM network interface, we believe they are also applicable in other contexts. In particular, protected DMA and I/O are promising techniques for improving the performance of several different types of I/O devices.
B. P. Crow, I. Widjaja, J. G. Kim and P. Sakai, "Investigation of the IEEE 802.11 Medium Access Control (MAC) Sublayer Functions," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 126, Apr. 1997.
Abstract: Analysis of the draft IEEE 802.11 wireless local area network (WLAN) standard is needed to characterize the expected performance of the standard’s ad hoc and infrastructure networks. The performance of the medium access control (MAC) sublayer, which consists of Distributed Coordination Function (DCF) and Point Coordination Function (PCF), is determined by simulating asynchronous data traffic in a 1 Mbps ad hoc network, and asynchronous data and packetized voice traffic in a 1 Mbps infrastructure network. The simulation models incorporate the effect of burst errors, packet size, RTS threshold and fragmentation threshold on network throughput and delay. The results show that the IEEE 802.11 WLAN can achieve a reasonably high eficaency when the medium is almost error-free, but may degrade appreciably under harsh fading. The results also show that time-sensitive traffic such as packet voice can be supported together with other intensive traffic such as packet data. However, an echo canceler is required for packet voice systems.
S. Jamin, S. J. Shenker and P. B. Danzig, "Comparison of Measurement-Based Admission Control Algorithms for Controlled-Load Service," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 973, Apr. 1997.
Abstract: We compare the performance of four admission control algorithms--one parameter-based and three measurement-based--for controlled-load service. The parameter-based admission control ensures that the sum of reserved resources is bounded by capacity. The three measurement-based algorithms are based on measured bandwidth, acceptance region [9], and equivalent bandwidth [7]. We use simulation on several network scenarios to evaluate the link utilization and adherence to service commitment achieved by these four algorithms.
A. Kantawala, G. Parulkar, J. DeHart and T. Marz, "Supporting DIS Applications Using ATM Multipoint Connection Caching," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 213, Apr. 1997.
Abstract: This report describes an ATM Multipoint Connection Caching strategy (AMCC) to control the explosive growth of traffic within the network and at an endpoint in a large Distributed Interactive Simulation (DIS) application such as a battlefield simulation. For very large DIS applications with 100,000 entities, the current method of broadcasting information among entities will no longer be feasible due to computational and network bandwidth limitations. Our scheme divides the simulation space into grids and each grid square or a set of grid squares forms a multicast group. Entities join the groups within their perception range and thus, they receive state updates only from entities within their perception range. AMCC utilizes the unique capabilities of our dynamic multipoint ATM signaling protocol, CMAP. We have implemented AMCC and have successfully demonstrated a small DIS battlefield simulation application running over our ATM testbed.
Dante DeLucia and Katia Obraczka, "Multicast Feedback Suppression Using Representatives," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 463, Apr. 1997.
Abstract: For a reliable, feedback dependent multicast transport protocol to scale, it must avoid the feedback implosion problem [3], particularly if the protocol targets arbitrarily large multicast groups communicating over lossy networks. Most existing suppression based feedback control mechanisms address the implosion problem using timers based on round-trip time (RTT) estimates between each receiver and the source. The algorithm presented in this paper has three major benefits: it does not need to compute RTT from all receivers to the source, does not require knowledge of group membership, and provides prompt feedback. A small set of representative receivers and probabilistic suppression are used to limit feedback. We believe that this approach will perform well in real networks. Simulations show that for various multicast group sizes, a few representatives can keep the amount of feedback low while not degrading feedback timeliness.
X. Dong and T. H. Lai, "An Efficient Priority-Based Dynamic Channel Allocation Strategy for Mobile Cellular Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 892, Apr. 1997.
Abstract: Priority-based dynamic carrier allocation strategies can be classified into three categories: static-priority, dynamic-priority, and hybrid-priority strategies. Strategies based on static priorities do not consider the local carrier reuse conditions, while dynamic-priority strategies do take these conditions into consideration. Intuitively, one would expect dynamic-priority strategies to perform better than static- and hybrid-priority strategies, but in the literature it is the other way around -- existing dynamic-priority strategies are out-performed by some static- and hybrid-priority strategies. In this paper, we propose a dynamic-priority strategy that significantly improves over all existing strategies. Under various traffic conditions, our simulation results indicated that the proposed strategy could reduce call blocking/failure rate by a margin ranging from 15% to 95%.
H. Duan, J. W. Lockwood, S. M. Kang and J. D. Will, "A High-Performance OC-12/OC-48 Queue Design Prototype for Input-Buffered ATM Switches," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 20, Apr. 1997.
Abstract: This paper presents the design and prototype of an intelligent, 3-Dimensional-Queue (3DQ) for high-performance, scalable, input buffered ATM switches. 3DQ uses pointers and linked lists to organize ATM cells into multiple virtual queues according to priority, destination, and virtual connection, It enforces per virtual connection Quality-of-Service (QoS) and eliminates Head-of-Line (HOL blocking. Using Field-Programmable-Gate-Array FPGA devices, our prototype hardware can process ATM cells at 622 Mb/s (OC-12). Using more aggressive technology (Multi-Chip-Module (MCM) and fast GaAs logic), the same 3DQ design can process cells at 2.5 Gb/s (OC-48). Using 3DQ and Matrix-Unit-Cell-Scheduler (MUCS) as essential components, an input-buffered ATM switch system has been designed, which can achieve near-100% link bandwidth utilization.
I. Chlamtac, V. Elek, A. Fumagallic and C. Szabó, "Scalable WDM Network Architecture Based on Photonic Slot Routing and Switched Delay Lines," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 769, Apr. 1997.
Abstract: Photonic Slot Routing (PSR) is a promising approach to solving the fundamental scalability problem of all-optical packet switched WDM networks. In this approach adjacent subnetworks can exchange wavelength sensitive traffic through bridges using wavelength non-selective devices which can be constructed using proven technologies. With photonic slot routing, packets sharing a common subnetwork destination are aggregated to form a photonic slot which is individually routed in order to reach the destination subnetwork. Photonic slots from different subnetworks can originate contentions at the bridge, leading to potential penalties of slot loss and retransmission. This paper shows how slot contention penalties can be reduced through the use of Switched Delay Lines (SDL) at the bridges. The combination of these two innovative techniques, the photonic slot routing and the switched delay lines, leads to a unique solution that is shown to nearly achieve throughput and delay performance obtainable in absence of slot contentions.
A. Elwalid and D. Mitra, "Traffic Shaping at a Network Node: Theory, Optimum Design, Admission Control," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 444, Apr. 1997.
Abstract: This paper develops a framework of traffic shaping which has the goal of increasing the nodal connection-carrying capacity. The shaping filters are designed to interwork with statistical multiplexer which use FIFO buffers. Differences in delay tolerances between traffic classes are exploited to shape and smooth the less delay sensitive traffic. The source model used in the analysis is asynchronous, worst-case subject to Dual Leaky Bucket regulation, where the asynchrony is due to the assumption of independent sources. This, together with the allowance of small loss probabilities, makes statistical multiplexing feasible. We require the shapers to be lossless so that losses, if any, occur only at the multiplexer. We obtain the optimal design of the shaper such that a given delay tolerance for the connection is satisfied. For purposes of admission control we obtain the admissible region of combinations of sources of various types such that the QoS requirements in loss and delay are satisfied. By examining the regions obtained with and without shaping we quantify the capacity gain from shaping. Our numerical results show that the gain can be substantial.
A. Feldmann and W. Whitt, "Fitting Mixtures of Exponentials to Long-Tail Distributions to Analyze Network Performance Models," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1096, Apr. 1997.
Abstract: Traffic measurements from communication networks have shown that many quantities characterizing network performance have long-tail probability distributions, i.e., with tails that decays more slowly than exponentially. Long-tail distributions can have a dramatic effect upon performance, but it is often difficult to describe this effect in detail, because performance models with component long-tail distributions tend to be difficult to analyze. We address this problem by developing an algorithm for approximating a long-tail distribution by a finite mixture of exponential. The fitting algorithm is recursive over time scales. At each stage, an exponential component is fit in the largest remaining time scale and then the fitted exponential component is subtracted from the distribution. Even though a mixture of exponential has an exponential tail, it can match a long-tail distribution in the regions of primary interest when there are enough exponential components.
W. C. Feng and J. Rexford, "A Comparison of Bandwidth Smoothing Techniques for the Transmission of Prerecorded Compressed Video," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 58, Apr. 1997.
Abstract: The transfer of prerecorded, compressed video requires multimedia services to support large fluctuations in bandwidth requirements on multiple time scales. Bandwidth smoothing techniques can reduce the burstiness of a variable- bit-rate stream by prefetching data at a series of fixed rates, simplifying the allocation of resources in video servers and the communication network. Given a fixed client-side prefetch buffer, several bandwidth smoothing algorithms have been introduced that are provably optimal under certain constraints. This paper presents a collection of metrics for comparing these smoothing algorithms and evaluating their cost-performance tradeoffs. Due to the scarcity of available trace data, we have constructed a video capture testbed and generated a collection of twenty full-length, motion-JPEG encoded video clips. Using these video traces and a range of client buffer sizes, we investigate the interplay between the performance metrics through simulation experiments. The results highlight the unique strengths and weaknesses of each algorithm.
N. R. Figueira and J. Pasquale, "Rate-Function Scheduling," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1063, Apr. 1997.
Abstract: Rate-Function Scheduling (RFS) is a new deadline-based packet-scheduling service discipline that supports quality-of- service guarantees for applications with real-time communication requirements. RFS is distinguished from other service disciplines in that it achieves all of the following goals: analytically-derived performance bounds, performance isolation among sessions, flexible and efficient allocation of bandwidth, implementation simplicity, work-conserving operation, and bandwidth-fair operation (defined in the paper). Through the specification of rate functions, sessions can control their bandwidth usage and their upper bounds on delay. For a class of rate functions, which we show is sufficient for providing sessions with delay bounds, RFS is as simple to implement and to calculate service bounds such as Zhang’s VirtualClock service discipline. We also show that the Non-Preemptive Earliest Deadline First Policy is a simple degeneration of RFS.
V. Firoiu, J. Kurose and D. Towsley, "Efficient Admission Control for EDF Schedulers," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 310, Apr. 1997.
Abstract: In this paper we present algorithms for flow admission control at an EDF link scheduler when the flows are characterized by peak rate, average rate and burst size. We show that the algorithms have very low computational complexity and are easily applicable in practice. The complexity can be further decreased by introducing the notion of flex classes. We evaluate the penalty in efficiency that the classes incur to the EDF scheduler. We find that this efficiency degradation can be made arbitrarily small and is acceptable even for a small number of classes.
C. Fulton, S. Q. Li and C. S. Lim, "An ABR Feedback Control Scheme with Tracking," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 805, Apr. 1997.
Abstract: We propose an explicit-rate ABR feedback control scheme, UT (Uniform Tracking). The distinct feature of UT is that it achieves max-min fairness by tracking an effective number of sources; specific constraint information is not required. As a result, its implementation is much simpler than that of other fair control schemes; indeed, its complexity is similar to that of unfair explicit-rate controls. In the thorough simulation study, UT demonstrates its ability to scale with speed, distance, number of users (both persistent and bursty), and number of switches while remaining robust, efficient, and fair under stressing conditions with MPEG background traffic and multiple propagation delay loops.
S. Shioda and H. Saito, "Real-Time Cell Loss Ratio Estimation and its Applications to ATM TRaffic Controls," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1072, Apr. 1997.
Abstract: The asymptotics of cell-loss ratio (CLR) in the regime of large buffers are characterized by two parameters, the asymptotic constant and asymptotic decay rate. Both parameters can be expanded in powers of one minus the link utilization (heavy traffic expansion). Thus, once the coefficients in this expansion are obtained, the CLR can be very easdy estimated from the measured link utilization by using CLR asymptotic. This paper proposes an algorithm for estimating these coefficients in real time. For this purpose, the notion of state-space representation for a single-server queue is introduced: the elements of the state vector are the coefficients in the expansion of the asymptotic constant and asymptotic decay rate. Bayesian regression analysts is applied to estimate the state vector based on the buffer measurement. Our approach does not require any models describing the statistics of the traffic other than the asymptotic behavior of the CLR in the regime of large buffers. In addition, it allows us to estimate the effective bandwidth of the aggregated process easily, so it is applicable to a wide range of ATM trafic control methods, such as connection admission control and VP bandwidth control. We describe how this method of CLR estimation will be applied to connection admission controi and VP bandwidth control by using results from simulation experiments.
Y. Y. Kim and S. Q. Li, "Performance Evaluation of Packet Data Services over Cellular Voice Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1022, Apr. 1997.
Abstract: In this paper we develop a Markov chain modeling framework for throughput/delay analysis of data services over cellular voice networks, using dynamic channel stealing method. Some effective approximation techniques are also proposed and verified for simplification of modeling analysis: Our study identifies the average voice call holding time as the dominant factor to affect data delay performance. Especially in heavy load conditions, namely when the number of free voice channels becomes momentarily less, the data users will experience large network access delay in the range of several minutes or longer on average. We also examine the data performance improvement by using priority data access scheme and speech silence detection technique.
F. Ishizaki and T. Takine, "Bounds for the Tail Distribution in a Queue with the Superposition of General Periodic Markov Sources," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1088, Apr. 1997.
Abstract: In this paper, we derive the bounds formulas for the asymptotic tail distribution in a queue whose arrival process is a superposition of general periodic Markov sources. Note that we make no assumption for the structure of the general periodic Markov sources except that the underlying Markov chains are irreducible. The periodic source model in this paper is thus rather general. Taking initial state conditions of the periodic sources into account, we construct a superposed arrival process. Contrary to the previous works, this implies that the periodic sources are not independent. We also provide examples to investigate the efficiency and the accuracy of our bound formulas.
Y. Yamada, N. Miyoshi and T. Hasegawa, "Sensitivity Analysis of the Loss Probability in a Stationary Gradual Queue for High-Speed Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 1114, Apr. 1997.
Abstract: In ATM networks, each node has its own buffer to store some cells. The buffer size represents a tradeoff between cell loss and transmission delay, and therefore, it is a significant concern to evaluate the performance with respect to the buffer size. In this paper, we investigate the sensitivity of the loss probability with respect to the buffer size by considering a gradual input queue with a finite buffer. Gradual inputs are considered as those representing a bursty traffic of cells. Applying the perturbation analysis technique to this model, we derive the strongly consistent sensitivity estimates, and combining with the likelihood ratio method, we confirm that our estimates lead to the reasonable simulation results.
S. Murthy and J. J. Garcia-Luna-Aceves, "Loop-Free Internet Routing Using Hierarchical Routing Trees," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 101, Apr. 1997.
Abstract: We present a new hierarchical routing algorithm that combines the loop-free path-finding algorithm (LPA) with the area-based hierarchical routing scheme first proposed by McQuillan for distance-vector algorithms. The new algorithm, which we call the Hierarchical Information Path-based Routing (HIPR) algorithm, accommodates an arbitrary number of aggregation levels and can be viewed as a distributed version of Dijkstra’s algorithm running over a hierarchical graph. HIPR is verified to be loop-free and correct. Simulations are used to show that HIPR is much more efficient than OSPF in terms of speed, communication and processing overhead required to converge to correct routing tables. HIPR constitutes the basis for future Internet routing protocols that are as simple as RIPv2, but with no looping and better performance than protocols based on link-states.
Puneet Sharma, Deborah Estrin, Sally Floyd, Van Jacobson, P. Sharma, D. Estrin, S. Floyd and V. Jacobson, "Scalable Timers for Soft State Protocols," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 222, Apr. 1997.
Abstract: Soft state protocols use periodic refresh messages to keep network state alive while adapting to changing network conditions; this has raised concerns regarding the scalability of protocols that use the soft-state approach. In existing soft state protocols, the values of the timers that control the sending of these messages, and the timers for aging out state, are chosen by matching empirical observations with desired recovery and response times. These fixed timer-values fail because they use time as a metric for bandwidth; they adapt neither to (1) the wide range of link speeds that exist in most wide-area internets, nor to (2) fluctuations in the amount of network state over time. We propose and evaluate a new approach in which timer-values adapt dynamically to the volume of control traffic and available bandwidth on the link. The essential mechanisms required to realize this scalable timers approach are: (1) dynamic adjustment of the senders’ refresh rate so that the bandwidth allocated for control traffic is not exceeded, and (2) estimation of the senders’ refresh rate at the receiver in order to determine when the state can be timed-out and deleted. The refresh messages are sent in a round robin manner not exceeding the bandwidth allocated to control traffic, and taking into account message priorities. We evaluate two receiver estimation methods for dynamically adjusting network state timeout values: (1) counting of the rounds and (2) exponential weighted moving average.
Keywords: RSVP; PIM; timer management
P. Y. Yan, K. S. Kim, M. V. Hegde and P. S. Min, "Multi-Channel Deflection Crossbar (MCDC): A VLSI Optimized Architecture for Multi-Channel ATM Switching," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 12-19, Apr. 1997.
Abstract: We propose the Multi-Channel Deflection Crossbar (MCDC) as a promising architecture for broadband ATM switching under the realistic constraints imposed by VLSI technology. MCDC is an internally non-blocking, buffer efficient, crossbar based architecture. MCDC is also capable of multi-channel switching with cell sequence integrity preserved. Through a comparative study against a well-known ATM switch architecture, we show that the proposed MCDC architecture is able to incorporate a greater number of input channels and buffers for a given IC die size and requires a lower clocking rate.
M. R. Hashemi and A. Leon-Garcia, "A General Purpose Cell Sequencer/Scheduler for ATM Switches," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 29-37, Apr. 1997.
Abstract: Groups of cells, such as cells belonging to different priority levels, that are all placed in one queue, can be identified by using labels or tags to distinguish them from each other. In this paper we describe a buffering device called sequencer, which can distinguish logical queues within the same physical queue, and at the same time can successfully schedule the service among these logical queues. Scheduling the service among cells, VC’S, or groups of cells in ATM switches is necessary to provide guaranteed QoS for each connection which is a major goal of ATM networks. The proposed sequencer is quite flexible and can realize different scheduling algorithms in different levels, including per VC scheduling. The sequencer can operate in real time and at very high speeds. It has a simple and modular architecture and can be implemented in a single chip. The size of the buffer can be increased simply by cascading several sequencers. The sequencer can be used as traffic shaper, input buffer, output buffer, or queue controller of RAM-based switches.
R. Hao and J. Wu, "Toward Formal TTCN-Based Test Execution," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 230-235, Apr. 1997.
Abstract: Formal test execution method is an important research field in formal protocol conformance testing. In this paper, we propose a formal test execution approach that is based on test notation TTCN’s operational semantics, and describe its executing process by using Input-Output Transition System (IOTS). We also give out a practical design of this formal approach. This formal TTCN-based test execution method is very suitable for the construction of general protocol test system, and also an effective means of automatic test suite verification.
D.-C. Twu and K.-C. Chen, "Adaptive Control Strategy for the Multi-Layer Collision Resolution Protocol," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 236-243, Apr. 1997.
Abstract: The Randomly Addressed Polling (RAP) protocol together with the generalized Multi-Layer Collision Resolution (MCR) protocol have been proposed and demonstrated as efficient, flexible and robust MAC protocols over the wireless network [1]-[3]. In this paper, we present a comprehensive study on the adaptive control schemes and the stability issues of this family of protocols over some centralized controlled network topologies, such as wireless, CATV (Cable Television), HFC (Hybrid Fiber/Coaxial), and even satellite networks. Under the assumption of infinite number of stations, we show that the proposed adaptive algorithm actually helps in stabilizing this family of protocols, and we also show that each packet only experiences finite delay when the adaptive control scheme is employed.
R. Kannan, "A Pipelined Single-Bit Controlled Sorting Network with O(N log^2 N) Bit Complexity," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 253-260, Apr. 1997.
Abstract: We propose a pipelined optical sorting network to sort N w-bit inputs using O(wN log N) single bit-controlled 2 x 2 switching elements. The network is compared to the standard Batcher sorter which requires (O{N log^2 N}) two-input comparators for sorting N log N-bit words. However each comparator in the Batcher sorter has to perform a word comparison between two log N bit inputs, as opposed to single-bit controlled switching elements in the proposed scheme. An alternative implementation of the proposed network maintains the same hardware complexity while showing an O(log log N) improvement in latency over the Batcher sorter. The proposed network is based on binary radix sort and utilizes a pair of self-routing reverse banyan networks to implement each step of the radix-sort algorithm. A distributed single-bit control scheme due to a particular non-blocking property of the reverse banyan network is used to route packets through each reverse banyan. Given the high cost of optical switches, the low hardware and control complexity of the network makes it easy to replace electronic switching elements with 2 x 2 Lithium Niobate directional couplers, thus making the network attractive for high-speed optical applications.
Y. Zhao, S. Q. Li and S. Sigarto, "A Linear Dynamic Model for Design of Stable Explicit-Rate ABR Control Schemes," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 283-292, Apr. 1997.
Abstract: This paper focuses on the important stability issue of ABR traffic control with explicit-rate schemes. We develop a novel design approach with three advantages. First, the ABR rate is only adapted to the low-frequency variation of the underlying VBR traffic, which effectively prevents network congestion with much improved control stability. Second, a linear dynamic model is presented which matces the optimal control theory readily applied to the design of ABR control. Third, the control of different ABR loops is uncoupled, which significantly simplifies the control scheme. With this approach, stability analysts for the controlled network becomes feasible with the knowledge of VBR traffic characteristics. We propose a new explicit-rate ABR control scheme, called H2 scheme, which has the same level of design complexity as the existing schemes but with rigorously proved stability. The stability problem of the existing explicit rate schemes is also considered.
A. Kolarov and G. Ramamurthy, "A Control Theoretic Approach to the Design of Closed Loop Rate Based Flow Control for High Speed ATM Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 293-301, Apr. 1997.
Abstract: In this paper we present a control theoretic approach to the design of closed loop rate based flow control in high speed networks. The proposed control uses a dual proportional derivative controller, where the control parameters can be designed to ensure the stability of the control loop in a control theoretic sense, over a wide range of traffic patterns and propagation delays. We show how the control mechanism can be used to design a controller to support ABR service based on feedback of explicit rates. We demonstrate the excellent transient and steady state performance of the controller through a number of examples.
H. Zhang, O. W. Yang and H. Mouftah, "Design of Robust Congestion Controllers for ATM Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 302-309, Apr. 1997.
Abstract: We propose an approach to design a rate-based proportional traffic controller in order to flow-regulate the best-effort servtce (e.g., ABR traffic) and guaranteed service traffic through an ATM switch. The controller is distributed and it has a very simple structure. Its local controller at each source node is open-loop stable and only requires the knowledge of the buffer occupancy at the bottleneck switch. We show that this controller is fair and is not sensitive to the change of VCS over time. It does not have oscillation and can achieve a high utilization.
D.-S. Lee, "Generalized Longest Queue First: An Adaptive Scheduling Discipline for ATM Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 318-325, Apr. 1997.
Abstract: In this paper, we propose a generalized longest queue first (GLQF) service discipline for ATM networks. We classify sources so that sources in one class have the same cell loss probability requirement. Assume that there are N classes of traffic. Under this discipline, buffer i is assigned a positive number w_i for the weight of buffer i. The scheduler transmits a cell from the buffer that has the maximal weighted queue length. The advantage of this discipline is that it can adapt to temporary overload quickly. We approximate the queue length distribution by decomposing the system into N single server queues with probabilistic service discipline. Our method is an iterative one, which we prove to be convergent by using stochastic dominance arguments and the coupling technique. For high utilization, we present a heavy traffic limit theorem.
D. Stiliadis and A. Varma, "A General Methodology for Designing Efficient Traffic Scheduling and Shaping Algorithms," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 326-335, Apr. 1997.
Abstract: We introduce a general methodology for designing int-grated shaping and scheduling algorithms for packet networks that provide fairness, low end-to-end delay, and low burstiness. The methodology is based on integrating a shaping mechanism with a scheduler from the class of Rate-Proportional Servers (RPS) defined in [10]. The resulting algorithms provide an end-to-end delay bound identical to that of Weighted Fair Queueing. Their worst-case fairness, in terms of minimizing the worst-case delay to empty the session backlog, is much superior to that of Weighted Fair Queueing, and equal to the best known for any scheduling algorithm. In addition, the algorithms achieve a level of fairness in the distribution of free bandwidth among competing sessions better than that of Weighted Fair Queueing. We show that, under this framework, even an unfair scheduling algorithm belonging to the RPS class, such as VirtualClock, can yield worst-case fairness identical to that obtained with Weighted Fair Queueing. We also develop an integrated shaper-scheduler that provides optimal output burstiness and is attractive for use in both network adapters and in switches that support traffic reshaping. We describe an efficient implementation of this integrated shaping and scheduling algorithm with log_2 (V) complexity, where V is the number of sessions sharing the outgoing link.
C.-S. Wu, J.-C. Jiau and K.-J. Chen, "Characterizing Traffic Behavior and Prowiding End-to-end Service Guarantees Within ATM Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 336-344, Apr. 1997.
Abstract: In this paper, we propose a rate-controlled service discipline for supporting B-ISDN services. According to our approach, traffic streams from different connections can be well regulated at the output of each node based on their rate requirements. Moreover, traffic envelope of a connection inside the network can be effectively characterized. By assuming a leaky-bucket constrained input source, we further prove that the proposed scheme can provide end-to-end delay and jitter bounds for each connection passing through a multi-hop network, Finally, we make a comparison of related works and show the effectiveness of our algorithm.
K. Murakami and H. S. Kim, "Comparative Study on Restoration Schemes of Survivable ATM Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 345-352, Apr. 1997.
Abstract: In self-healing networks, end-to-end restoration schemes have been considered more advantageous than line restoration schemes because of a possible cost reduction of the total capacity to construct a fully restorable network. This paper clarifies the benefit of end-to-end restoration schemes quantitatively through a comparative analysis of the minimum link capacity installation cost. A jointly optimal capacity and flow assignment algorithm is developed for the self-healing ATM networks based on end-to-end and line restoration. Several networks with diverse topological characteristics as well as multiple projected traffic demand patterns are employed in the experiments to see the effect of various network parameters. The results indicate that the network topology has a significant impact on the required resource installation cost for each restoration scheme. Contrary to a wide belief in the economic advantage of the end-to-end restoration scheme, this study reveals that the attainable gain could be marginal for a well-connected and/or unbalanced network.
Y. Xiong and L. Mason, "Restoration Strategies and Spare Self-Healing ATM Capacity Requirements in Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 353-360, Apr. 1997.
Abstract: This paper studies the capacity and flow assignment problem arising in the design of self-healing ATM networks using virtual path (VP) concept. The problem is formulated here as a linear programming problem which is solved using standard methods. The objective is to minimize the spare capacity cost for the given restoration requirement. The spare cost depends on restoration strategies used in the network. In the paper we will compare several restoration strategies, not ably, global versus failure-oriented reconfiguration, path versus link based restoration and state-dependent versus state-independent restoration, quantitatively in terms of spare cost. The advantages and disadvantages of various restoration strategies are also highlighted. Such comparisons provide useful guidance for real network design. Further, a new heuristic algorithm is developed in this paper for the design of large self-healing ATM networks using path based restoration. Numerical results illustrate that the heuristic algorithm is efficient and can give near-optimal solutions for the spare capacity allocation and flow assignment.
C.-J. Hou, "Design of a Fast Restoration Mechanism ATM Networks for Virtual Path-Based ATM Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 361-369, Apr. 1997.
Abstract: ln this paper, we propose a fast restoration mechanism for virtual path-based ATM networks. Given an ATM network topology, the capacity of each physical link, and the primary virtual path (VP) layout at system initialization, the proposed mechanism pre-assigns to each primary VP one backup VP such that (PI) the failure of a single node/link does not lead to the failure of both the primary and backup VPs, (P2) the alternate backup VP is routed on a path with the shortest hop count among all possible paths with sufficient bandwidth between the two VP terminators, and (P3) the maximum link load is minimized. During system operation, if a physical node/link fails, the proposed mechanism restores the VPs that traverse the failed node/link simply by redirecting cells on the failed VPs to their corresponding backup VPs. Moreover, the proposed mechanism also locates (i) new VPs for injured backup VPs that traverse the failed node/link, and (ii) second-generation backup VPs for newly-activated backup VPs that replace their corresponding failed primary VPs, both in a decentralized manner, We elaborate on all the component algorithms, and discuss how to configure the functionalities as software daemons that reside at each network node. The proposed mechanism is shown via event-driven simulation to be practically feasible in fast restoring failed VPs in a cost effective manner.
T. V. Lakshman, P. P. Mishra and K. K. Ramakrishnan, "Transporting Compressed Video over ATM Networks with Explicit Rate Feedback Control," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 38-47, Apr. 1997.
Abstract: We propose a scheme for transmission of variable-bit- rate compressed video over ATM networks using the Explicit-Rate congestion control mechanisms proposed for the Available Bit Rate (ABR) service. Compressed video is inherently bursty with rate fluctuations over both short and long time scales. We feel that this source behavior can naturally take advantage of the ABR service, since the ABR explicit-rate schemes allow sources to request varying amounts of bandwidth over time, while reserving a minimum for the entire duration of the connection. Moreover, when the bandwidth demand cannot be met, the network provides feedback indicating the bandwidth currently available to a connection. This information can be used to match the video source rate to the available bandwidth by modifying the quantization level used during compression. We use trace driven simulations to examine how effective the enhanced explicit rate scheme is in ``rate matching'' between the network and the source and the effect on end-end delay. We also look at the sensitivity of the proposed scheme to the estimates of the network round-trip times and to inaccuracies in the rate requests made by sources.
M. Graf, "VBR Video over ATM: Reducing Network Resource Requirements through Endsystem Traffic Shaping," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 48-57, Apr. 1997.
Abstract: Transmission of variable-bitrate (VBR) video over ATM is a challenge because it combines the requirement for on-time data delivery with a bursty traffic characteristic. We focus on the role of ATM endsystems in the transmission of VBR video and examine how traffic shaping in the sender reduces the burstiness of the video stream and therefore the network resource requirements, both for video encoded in real-time and stored video. Shapers based on multiple leaky buckets are popular because they are particularly simple to implement. We present basic results on their buffer requirements and provide new, tighter bounds for their output traffic, enabling efficient resource allocation as well as a significant reduction in the number of leaky buckets required. We extend the basic shaping mechanism to provide efficient shaping for stored video. Finally we compare empirically the performance of multiple leaky bucket shaping with an optimal algorithm for MPEG-1 encoded video and find under realistic conditions near-optimal performance with very few leaky buckets.
M. Krunz and S. K. Tripathi, "Exploiting the Temporal Structure of MPEG Video for the Reduction of Bandwidth Requirements," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 67-74, Apr. 1997.
Abstract: We present a novel bandwidth allocation scheme for transporting variable-bit-rate MPEG trafic from a video server. Using time-varying envelopes to characterize the traffic, this scheme achieves significant bandwidth gain, via statistical multiplexing, while supporting stringent, deterministic QoS guarantees. The gain can be maximized by allowing the server to appropriately schedule the starting times of video sources, at the expense of some negligible startup delay. For homogeneous streams, we give the optimal schedule that results an the mintmum allocated bandwidth. A sub-optimal schedule is given in the heterogeneous case, which is shown to be asymptotically optimal. Efficient online procedures for bandwidth computation are provided. Numerical examples based on traces of MPEG-coded movies are used to demonstrate the benefits of our allocation strategy.
I. Cidon, R. Rom and Y. Shavitt, "Multi-Path Routing Combined with Resource Reservation," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 92-100, Apr. 1997.
Abstract: In high-speed networks it is desirable to interleave routing and resource (such as bandwidth) reservation. The PNNI standard for private ATM networks is a recent example for an algorithm that does this using a sequential crank-back mechanism. In this work, we suggest to do resource reservation along several routes in parallel. We present an analytical model that demonstrates that when there are several routes to the destination it pays to attempt reservation along more than a single route. Following this analytic observation, we present a family of algorithms that route and reserve resources along parallel subroutes. The algorithms of the family represent different tradeoffs between the speed and the quality of the established route. The presented algorithms are simulated against several legacy algorithm, Including PNNI crank-back, and exhibit higher network utilization and faster connection set-up time.
Roch Guerin and Ariel Orda, "QoS-based Routing in Networks with Inaccurate Information: Theory and Algorithms," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 75-83, Apr. 1997.
Abstract: We investigate the problem of routing connections with QoS requirements across one or more networks, when the information available for making routing decisions is inaccurate and expressed in some probabilistic manner. This uncertainty about the actual state of a node or network arises naturally in a number of different environments, that are reviewed in the paper. The main focus is to determine the impact of such inaccuracies on the path selection process, whose goal is then to identify the path that is most likely to satisfy the QoS requirements.
H. F. Salama, D. S. Reeves and Y. Viniotis, "A Distributed Algorithm for Delay-Constrained Unicast Routing," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 84-91, Apr. 1997.
Abstract: In this paper, we study the NP-hard delay-constrained least-cost path problem, and propose a simple, distributed heuristic solution: the delay-constrained unicast routing (DCUR) algorithm. DCUR requires limited network state information to be kept at each node: a cost vector and a delay vector. We prove DCUR’s correctness by showing that it is always capable of constructing a loop-free delay-constrained path within finite time, if such a path exists. The worst case message complexity of DCUR is O(V|3) messages, where V| is the number of nodes. However, simulation results show that, on the average, DCUR requires much fewer messages. Therefore, DCUR scales well to large networks. We also use simulation to compare DCUR to the optimal algorithm, and to the least-delay path algorithm. Our results show that DCUR’s path costs are within 10% from those of the optimal solution.
C.-J. Su and L. Tassiulas, "Broadcast Scheduling for Information Distribution," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 109-117, Apr. 1997.
Abstract: Broadcast data delivery is encountered in many applications where there is a need to disseminate information to a large user community in a wireless asymmetric communication environment. In this paper, we consider the problem of scheduling the data broadcast such that the access latency experienced by the users is low. In a push-based system, where the users cannot place requests directly to the server and the broadcast schedule should be determined based solely on the access probabilities, we formulate a deterministic dynamic optimization problem, the solution of which provides the optimal broadcast schedule. Properties of the optimal solution are obtained and then we propose a suboptimal dynamic policy which achieves mean access latency close to the lower bound. The policy has low complexity, it is adaptive to changing access statistics, and is easily generalizable to multiple broadcast channels. In a pull-based system where the users may place requests about information items directly to the server, the scheduling can be based on the number of pending requests for each item. Suboptimal policies with good performance are obtained in this case as well. Finally, it is demonstrated by a numerical study that as the request generation rate increases, the achievable performance of the pull- and push-based systems becomes almost identical.
C. R. Lin and M. Gerla, "Asynchronous and Multimedia Multihop Wireless Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 118-125, Apr. 1997.
Abstract: Personal communications and mobile computing will require a wireless network infrastructure which is fast deployable, possibly multihop, and capable of multimedia service support. The first infrastructure of this type was the Packet Radio Network (PRNET), developed in the 70’s to address the battlefield and disaster recovery communication requirements. PRNET was totally asynchronous and was based on a completely distributed architecture. It handled datagram traffic reasonably well, but did not offer efficient multimedia support. Recently, under the WAMIS and Glomo ARPA programs several mobile, multimedia, multihop (M^3) wireless network architectures have been developed, which assume some form of synchronous, time division infrastructure. The synchronous time frame leads to efficient multimedia support implementations. However, it introduces more complexity and is less robust in the face of mobility and channel fading. In this paper, we examine the impact of synchronization on wireless M^3 network performance. First, we introduce MACA/PR, an asynchronous network based on the collision avoidance MAC scheme employed in the IEEE 802.11 standard. Then, we evaluate and compare several wireless packet networks ranging from the total asynchronous PRNET to the synchronized cluster TDMA network. We examine the tradeoffs between time synchronization and performance in various traffic and mobility environments.
M. Peyravian and A. D. Kshemkalyani, "Connection Preemption: Issues, Algorithms, and a Simulation Study," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 143-151, Apr. 1997.
Abstract: Connection preemption can be a means to provide available and reliable services to high-priority connections when a network is heavily loaded and connection request arrival patterns are unknown, or when the network experiences link or node failures. We present a simulation study of preemption in a general connection-oriented network setting. Based on the observations made in this study, we have developed two optimal connection preemption selection algorithms that operate in a decentralized/distributed network where individual link managers run the algorithm for connection preemption selection on their outgoing links. The first algorithm optimizes the criteria of (i) the number of connections to be preempted, (ii) the bandwidth to be preempted, and (iii) the priority of connections to be preempted, in that order, and has polynomial complexity. The second algorithm optimizes the criteria of (i) the bandwidth to be preempted, (ii) the priority of connections to be preempted, and (iii) the number of connections to be preempted, in that order, and has exponential complexity. We conclude that the polynomial algorithm is almost as good as the exponential algorithm in terms of overall network performance.
R. Garcés and J. J. Garcia-Luna-Aceves, "Collision Avoidance and Resolution Multiple Access with Transmission Groups," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 134-142, Apr. 1997.
Abstract: The CARMA-NTG protocol is presented and analyzed. CARMA-NTG dynamically divides the channel into cycles of variable length; each cycle consists of a contention period and a group-transmission period. During the contention period, a station with one or more packets to send competes for the right to be added to the group of stations allowed to transmit data without collisions; this is done using a collision resolution splitting algorithm based on a request-to-send/clear-to-send (RTS/CTS) message exchange with non-persistent carrier sensing. CARMA-NTG ensures that one station is added to the group transmission period if one or more stations send requests to be added in the previous contention period. The group-transmission period is a variable-length train of packets, which are transmitted by stations that have been added to the group by successfully completing an RTS/CTS message exchange in previous contention periods. As long as a station maintains its position in the group, it is able to transmit data packets without collision. An upper bound is derived for the average costs of obtaining the first success in the splitting algorithm. This bound is then applied to the computation of the average channel utilization in a fully connected network with a large number of stations. These results indicate that collision resolution is a powerful mechanismin combination with floor acquisition and group allocation multiple access.
M. Schuba, "A Performance Evaluation of Connectionless Overlay Networks for ATM," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 152-159, Apr. 1997.
Abstract: Introducing the Asynchronous Transfer Mode (ATM) causes a backwards compatibility problem, because ATM is connection-oriented whereas most of today’s LANs are connectionless. Interconnection can be achieved by the use of connectionless servers (CLS). These servers together with a number of preestablished virtual circuits form a connectionless overlay network on top of ATM. In this paper we evaluate overlay networks that differ in number, location and interconnection of CLSs by computation of mean cell delay and link load.
C. Li, A. Raha and W. Zhao, "Stability in ATM Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 160-167, Apr. 1997.
Abstract: In this paper, we address the issues of stability in ATM networks. A network is stable if and only if all the packets have a bounded delay. We first consider ATM networks with FCFS scheduling policy. We then study networks with priority driven scheduling poLicy. For each network, we develop criteria for testing the stability of an ATM network and methods of deriving delay bounds in a stable network. In previous work, the Cruz-Gallager-Parekh ring has been a ``benchmark'' architecture to study the stability problem. For example, Gallager and Parekh claimed that the ring with size no more than four switches is stable when the total utilization of the links is less than 100% [9]. We validated this result. Furthermore, we find that a ring with large number of switches is stable if the utilization of each link is less than or equal to 73%.
S. Giordano, J.-Y. Le Boudec, P. Oechslin and S. Robert, "VBR over VBR: The Homogeneous, Loss-Free Case," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 168-176, Apr. 1997.
Abstract: We consider the multiplexing of several variable bit rate (VBR) connections over one variable bit rate connection where the multiplexing uses a multiplexing buffer of size B. The VBR trunk is itself a connection and has a multidimensional connection descriptor, reflecting peak and sustainable rates. Given a cost function for the VBR trunk and a connection admission control (CAC) method for the input connections, we focus on the problem of finding the VBR trunk connection descriptor that minimizes the cost function and is able to accept a given set of VBR input connections. First, we show that, under reasonable assumptions on the cost function, the optimization problem can be reduced to a simpler one. Then we consider the homogeneous, loss-free case, for which we give an explicit CAC method. In that case, we find that, for all reasonable cost functions, the optimal VBR trunk is either of the CBR tgpe, or is truly VBR, with a burst duration equal to the burst duration of the input connections. We motivate this study by showing that the optimal peak cell rate is fixed for a given B (thus for a CBR trunk), and a VBR choice can onlg be an improvement. Lastly, we take as example of cost function the equivalent capacity of the VBR trunk. Those results are expected to form the basis for a general method for a connection manager at a multiplexing node in an integrated services packet network.
H. Che and S.-Q. Li, "Fast Algorithms for Measurement-Based Traffic Modeling," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 177-186, Apr. 1997.
Abstract: This paper develops fast algorithms for construction of circulant modulated rate process to match with two primary traffic statistical functions: distribution f(x) and autocorrelation R(r) of the rate process. Using existing modeling techniques, f(x) has to be limited to certain forms such as Gaussian or binomial; R(r) can only consist of one or two exponential terms which are often real exponential rather than complex. In reality, these two functions are collective from real traffic traces and generally expressed in much complicated form. Our emphasis here is placed on the algorithmic design for matching complicated R(r) in traffic modeling. The typical CPU time for the traffic modeling with R(r) consisting of five or six complex exponential terms is found in the range of a few minutes by the proposed algorithms. Our study further shows an excellent agreement between original traffic traces and sequences generated by the matched analytical model.
G. Mayor and J. Silvester, "Time Scale Analysis of an ATM Queueing System With Long-Range Dependent Traffic," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 205-212, Apr. 1997.
Abstract: Several types of network traffic have been shown to exhibit long-range dependence (LRD). In this work, we show that the busy period of an ATM system driven by a long-range dependent process can be very large. We introduce a new traffic model based on a fractional Brownian motion envelope process. We show that this characterization can be used to predict queueing dynamics. Furthermore, we derive a new framework for computing delay bounds in ATM networks based on this traffic model. We show that it agrees with results given by large deviation theory with less computational complexity.
S. D. Nikolopoulos, A. Pitsillides and D. Tipper, "Addressing Network Survivability Issues by Finding the K-Best Paths through a Trellis Graph," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 370-377, Apr. 1997.
Abstract: Due to the increasing reliance of our society on the timely and reliable transfer of large quantities of information (such as voice, data, and video) across high speed communication networks, it is becoming important for a network to offer survivability, or at least graceful degradation, in the event of network failure. In this paper we aim to offer a solution in the selection of the K-best disjoint paths through a network by using graph theoretic techniques. The basic approach is to map an arbitrary network graph into a trellis graph which allows the application of computationally efficient methods to find disjoint paths. Use of the knowledge of the K-best disjoint paths for improving the survivability of ATM networks at the virtual path and virtual circuit level is discussed.
G. G. Xie and S. S. Lam, "Real-Time Block Transfer Under a Link Sharing Hierarchy," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 388-397, Apr. 1997.
Abstract: Most application-level data units are too large to be carried in a single packet (or cell) and must be segmented for network delivery. To an application, the end-to-end delays and loss rate of its data units are much more relevant performance measures than ones specified for individual packets (or cells). The concept of a burst (or block) was introduced to represent a sequence of packets (or cells) that carry an application data unit. In this paper, we describe how a real-time VBR service, with QoS parameters for block transfer delay and block loss rate, can be provided by integrating concepts and delay guarantee results from our previous work on burst scheduling, together with ideas from ATM block transfer. Two new contributions are presented herein. First, we design an admission control algorithm to provide the following classes of service: bounded-delay block transfer with no loss, and bounded-delay block transfer at specified block loss rate. Second, we show how to extend existing end-to-end delay bounds to networks with hierarchical link sharing.
D. Lin, "Constant-Time Dynamic ATM Bandwidth Scheduling for Guaranteed and Best Effort Services with Overbooking," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 398-405, Apr. 1997.
Abstract: In this paper, we present an analysis of an existing rate-based ABR scheduling algorithm described in [1], and propose an enhanced rate-based round robin (RBR) scheduling algorithm for ATM switches and end systems. One of the novel aspects of RBR is that the scheduler supports available bit rate (ABR) traffic as well as guaranteed bandwidth reservations. In addition, bandwidth overbooking is allowed by the scheduler for ABR services to improve link efficiency as recommended by most flow control schemes. Under competition, the scheduler distributes the bandwidth in a max-min fair way. Any unused reservations for guaranteed services are reallocated to ABR services. Finally, the operations performed during each scheduling cycle are constant, independent of the number of connections. Simulation results are also presented and analyzed.
F. M. Chiussi, Y. Xia and V. P. Kumar, "Virtual Queueing Techniques for ABR Service: Improving ABR/VBR Interaction," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 406-418, Apr. 1997.
Abstract: Several algorithms have been proposed for the switch behavior for congestion control of Available Bit Rate (ABR) services. Schemes such as the Enhanced Proportional Rate Control Algorithm (EPRCA) and the Dynamic Max Rate Control Algorithm (DMRCA), which use the queue length as congestion indicator to make a simple approximation of the fair share converge to the actual fair share, have become popular, because they offer good performance and are simple to implement. In particular, with no VBR traffic in the network, DMRCA has been shown to achieve fairness in all situations, good buffer control, and robust performance. In this paper, first we show that the performance of these schemes may degrade when ABR traffic interacts with highly-bursty VBR traffic. If VBR traffic induces congestion in the network, the length of the ABR queue cannot serve as a reliable indicator of congestion caused by ABR traffic, and the schemes perform poorly, introducing considerable unfairness. Then, we propose a simple technique to solve these problems. The switch constructs the length of a virtual queue which is not affected by the instantaneous behavior of VBR traffic, and does not depend on how the two types of traffic are served in order to share the common link capacity; thus, it can serve as a reliable indicator of congestion. We use this technique in DMRCA with Virtual Queueing (DMRCA_VQ), and show that the new scheme achieves fair rate allocation to the ABR connections also in presence of highly-bursty VBR traffic. DMRCA_VQ maintains the low hardware complexity of DMRCA. The virtual queueing technique is a solution for the more general problem of separating rate allocation based on the queue length from scheduling of multiple queues for sharing a common resource.
M. Parulekar and A. M. Makowski, "M/G/Infinity Input Processes: A Versatile Class of Models for Network Traffic," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 419-426, Apr. 1997.
Abstract: We suggest the M/G/Infinity input process as a viable model for network traffic due to its versatility and tractability. We characterize the process as short or long-range dependent by means of a simple test. To gauge its performance, we study the large buffer asymptotic of a multiplexer driven by an M/G/Infinity input process. The decay rate of the tail probabilities for the buffer content (in steady-state) is investigated using large deviations techniques suggested by Duffield and O'Connell. We show that the selection of the appropriate large deviations scaling is related to the forward recurrence time of the service time distribution, and a closed-form expression is derived for the corresponding generalized limiting log-moment generating function associated with the input process. We apply our results to cases where the service time distribution in the MIGIco input model is (i) Rayleigh (ii) Gamma (iii) Geometric (iv) Weibull (v) Log-normal and (vi) Pareto - cases (v) and (vi) have recently been found adequate for modeling packet traffic streams in certain networking applications. Finally, we comment on the insufficiency of the short- vs. long-range dependence characterization of an input process as a means to accurately describe the corresponding buffer dynamics.
B. L. Mark, D. L. Jagerman and G. Ramamurthy, "Peakedness Measures for Traffic Characterization in High-Speed Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 427-435, Apr. 1997.
Abstract: In high-speed networks based on Asynchronous Transfer Mode ATM, variable bit rate (VBR) sources generate bursty cell streams which share link bandwidth wherever multiplexing occurs. In theory, the bandwidth requirement per stream to support a given quality-of-service at a multiplexer should generally decrease as the number of streams increases. In practice, high statistical multiplexing gain is difficult to achieve because good traffic characterizations are usually not available. This paper proposes the use of peakedness-based measures to capture the statistical information from traffic streams needed to determine bandwidth allocations. The standard definition of peakedness applies only to point process models of traffic. Yet fluid models of traffic have certain advantages in terms of tractability. Hence, we introduce a new measure called modified peakedness, which encompasses point process and fluid models under a common framework. We develop some of its properties and specialize it to several common traffic models. Finally, we study the effectiveness of the peakedness/modified peakedness as burstiness measures for real-time traffic.
C.-S. Chang, "A Filtering Theory for Deterministic Traffic Regulation," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 436-443, Apr. 1997.
Abstract: In this paper, we develop a filtering theory for deterministic traffic regulators that generate f-constrained outputs. We show that such regulators can be implemented by a linear time invariant filter with the impulse response f under the (rein,+)-algebra if the function f is increasing and subadditive. The filtering approach not only yields easier proofs for more general results than those in the literature, but also allows us to design traffic regulators via systematic methods such as concatenation, filter bank summation, linear system realization, and FIR-IIR realization. The theory has many applications, including leaky buckets, traffic regulation for periodic constraint functions, and service curves. In particular, we find a new linear system realization and a new FIR-IIR realization for a concatenation of leaky buckets. Moreover, we find a FIR-IIR realization for traffic regulators with periodic constraint functions. We also show that such regulators, in conjunction with maximum delay guarantee, guarantee shifted-subadditive service curves. Based on this, we provide a couple of rules for service curve allocation among a concatenation of servers.
R. Morris, "Bulk Multicast Transport Protocol," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 455-462, Apr. 1997.
Abstract: BMTP offers rate controlled multicast with reliability, high throughput, and support for large numbers of receivers. A multicast sender needs feedback from receivers to recover from errors and to choose an appropriate send rate, but must avoid being overwhelmed as the number of receivers grows. BMTP does this by keeping the rate at which each receiver sends feedback inversely proportional to a running estimate of the number of receivers. BMTP bases its send rate on the minimum of the receive rates observed by the receivers, causing the sender to slow down in the face of packet loss or competing traffic, and to speed up when there is spare network capacity. BMTP’s NAK-based retransmission rarely sends any data more than twice, a substantial improvement over iterated unicast. Rabin’s Information Dispersal Algorithm can reduce this re-send rate as close as desired to the underlying loss rate of the network. Simulations with 1000 receivers substantiate these claims.
M. Yamamoto, J. F. Kurose, D. F. Towsley and H. Ikeda, "A Delay Analysis of Sender-Initiated and Receiver-Initiated Realiable Multicast Protocols," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 480-488, Apr. 1997.
Abstract: A growing number of network applications require the use of a reliable multicast protocol to disseminate data from a source to a potentially large number of receivers. This paper presents an analytic performance analysis of the packet delay incurred under three generic sender- and receiver-initiated approaches towards reliable multicast. We focus on the host processing requirements of these protocols and derive expressions for average time between the initial arrival of a packet at a sender and its correct reception at a randomly chosen receiver. Our numerical results indicate that a NAK-based protocol that limits NAK generation by intentionally and randomly delaying NAK packets can achieve substantially higher throughput than the other two protocols examined, and can do so without suffering an appreciable higher delay over a range of system parameters.
R. Ramaswami and G. H. Sasaki, "Multiwavelength Optical Networks with Limited Wavelength Conversion," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 489-498, Apr. 1997.
Abstract: This paper proposes optical wavelength division multiplexed (WDM) networks with limited wavelength conversion that can efficiently support lightpaths (connections) between nodes. Each lightpath follows a route in the network and must be assigned a channel along each link in its route. The load $\lambda$_max of a set of lightpath requests is the maximum over all links of the number of lightpaths that use the link. At least Amax wavelengths will be needed to assign channels to the lightpaths. If the network has full wavelength conversion capabilities then $\lambda$_max wavelengths are sufficient to perform the channel assignment. We propose ring networks with fixed wavelength conversion capability within the nodes that can support all lightpath request sets with load $\lambda$_max at most W-1, where W is the number of wavelengths in each link. We also propose ring networks with selective pairwise wavelength conversion capability within the nodes that can support all lightpath request sets with load $\lambda$_max at most W. We also propose a star network with jzed wavelength conversion capability at its hub node that can support all lightpath request sets with load Amax at most W. We extend this result to tree networks and networks with arbitrary topologies. These results show that significant improvements in traffic-carrying capacity can be obtained in WDM networks by providing very limited wavelength conversion capability within the network.
O. Gerstel, R. Ramaswami and G. H. Sasaki, "Fault Tolerant Multiwavelength Optical Rings with Limited Wavelength Conversion," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 507-515, Apr. 1997.
Abstract: This paper pvesents methods for recovering from channel failures, link failures, and node failures in wavelength-division multiplexed (WDM) point-to-point links and ring networks, with limited wavelength conversion/switching capabilities at the nodes. Different recovery schemes are presented to handle each type of failure. Each scheme is evaluated based on the network hardware configuration required to support it, and the performance and management overheads associated with fault-recovery.
H. Harai, M. Murata and H. Miyahara, "Performance of Alternate Routing Methods in All-Optical Switching Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 516-524, Apr. 1997.
Abstract: We study routing methods in all-optical switching networks. In all-optical switching networks, the connection with more hops encounters more call blocking, and it is especially true in optical networks with no wavelength conversions. We therefore consider an alternate routing method with limited trunk reservation in which connections with more hops are prepared more alternate routes. Through developing an approximate analytic approach, we show that our method keeps good performance when compared with the existing alternate routing methods, and also that the fairness among connections can be improved. Further performance improvement is investigated by introducing a wavelength assignment policy and a dynamic routing method. An effectiveness of the proposed method is investigated through simulation.
M. R. Hashemi and A. Leon-Garcia, "The Single Queue Switch," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 533-540, Apr. 1997.
Abstract: In this paper we introduce a new approach to ATM switching. We propose an ATM switch architecture which: uses only a single shift-register-type buffering element to store and queue the cells; and within the same physical queue switches the cells by organizing them in logical queues destined to different output lines. The buffer is also a sequencer which allows flexible ordering the cells in each logical queue to achieve any appropriate scheduling algorithm. This switch is proposed for use as the building block of large-scale multi-stage ATM switches and as the scheduler/controller for the RAM-based switches. The single queue switch implements output queueing and performs full buffer sharing. The hardware complexity is low. The number of input and output lines can vary independently without affecting the switch core. The size of the buffering space can be increased by simply cascading the buffering elements to each other.
I. Cidon, A. Khamisy and M. Sidi, "Analysis of Queueing Displacement Using Switch Port Speedup," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 541-548, Apr. 1997.
Abstract: Current high-speed packet switching systems, ATM in particular, have large port buffering requirements. The use of highly integrated ASIC technology for implementing high-degree and high-speed switch fabrics is facing a technology mismatch in the sense that today's chip technology does not allow to integrate on-chip the high-speed switching fabric with the large buffering requirements. Consequently, many designs are based on the principles of queueing displacement, i.e., they attempt to move the queueing point on-chip. This is usually done by considerably speeding-up the on-chip switch output ports and placing a second external stage of buffering between the switch fabric and the outgoing link circuitry. Such designs are very popular and are used by many current ATM switch vendors. While such schemes are widely used, no rigorous analysis has so far been offered to evaluate the design trade-offs and to quantify the design points. The model we use to analyze the performance of the above system is a two-node tandem queueing system. The first node in the tandem corresponds to the internal buffer while the second node in the tandem corresponds to the external buffer. It is assumed that the internal buffer is capable to transfer c1 cells per time unit to the external buffer, while the external buffer is served at a lower rate of c2 cells per time unit.
J. Choe and N. B. Shroff, "A New Method to Determine the Queue Length Distribution at an ATM Multiplexer," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 549-556, Apr. 1997.
Abstract: In this paper, we develop a simple analytical technique to determine P({Q>q}), the tail of the queue length distribution, at an ATM multiplexer. The ATM multiplexer is modeled as a fluid queue serving a large number of independent sources. Our method is based on the central limit theorem and the maximum variance approximation, and enables us to avoid the state explosion problem. The approach is quite general and not limited by a Markovian framework. We apply our analytical method to study the buffer behavior for various traffic sources such as multiplexed homogeneous and heterogeneous Markov modulated sources, sources that are correlated at multiple time scales, sources whose autocorrelation function exhibits heavy (sub-exponential) tail behavior, and sources generated from real MPEG-encoded video sequences.
Y. Ohba, "QLWFQ: A Queue Length Based Weighted Fair Queueing Algorithm in ATM Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 566-575, Apr. 1997.
Abstract: A work conserving O(1) per-VC queueing algorithm named QLWFQ (Queue Length Based Weighted Fair Queueing) for high-speed ATM networks is proposed. The basic process in QLWFQ is the comparison of the current queue length with the weight when a cell arrival or departure occurs. QLWFQ has upward compatibility with Fair Queueing and FIFO, and can be considered to be a simplified version of Weighted Round Robin. A delay bound and a fairness index are derived analytically for the QLWFQ algorithm. The simulation results for heavily and lightly loaded conditions are also presented. The analytical and simulation results show that QLWFQ achieves a better balance between traffic isolation and traffic sharing than timestamp based algorithms.
B. A. Mah, "An Empirical Model of HTTP Network Traffic," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 592-600, Apr. 1997.
Abstract: The workload of the global Internet is dominated by the Hypertext Transfer Protocol (HTTP), an application protocol used by World Wide Web clients and servers. Simulation studies of IP networks will require a model of the traffic patterns of the World Wide Web, in order to investigate the effects of this increasingly popular application. We have developed an empirical model of network traffic produced by HTTP. Instead of relying on server or client logs, our approach is based on packet traces of HTTP conversations. Through traffic analysis, we have determined statistics and distributions for higher-level quantities such as the size of HTTP files, the number of files per ``Web page'', and user browsing behavior. These quantities form a model can then be used by simulations to mimic World Wide Web network applications.
D. E. Wrege and J. Liebeherr, "A Near-Optimal Packet Scheduler for QoS Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 576-583, Apr. 1997.
Abstract: A packet scheduler in a quality-of-service (QoS) network should be sophisticated enough to support stringent QoS constraints at high loads, but it must also have a simple implementation so that packets can be processed at the speed of the transmission link. The Earliest-Deadline-First (EDF) scheduler is the optimal scheduler for bounded-delay services in the sense that it provides the tightest delay guarantees of any scheduler, but an implementation of EDF requires the sorting of packets, a complex operation that is not practical for high-speed networks. In this study we present the design, implementation and analysis of the novel Rotating-Priority-Queues (RPQ+) scheduler that is near-optimal in the sense that it can approximate EDF with arbitrary precision. The RPQ+ scheduler uses a set of prioritized FIFO queues whose priorities are rearranged (rotated) periodically to increase the priority of waiting packets. We derive admission control tests for RPQ+ and show that it has the following desirable properties: its implementation requires operations independent of the number of queued packets, at can provide worst-case delay guarantees, and its efficiency is ``between'' that of EDF and Static-Priority (SP) schedulers. We use numerical examples, including examples based on MPEG video, to show that in realistic scenarios RPQ+ can closely approximate EDF even for infrequent queue rotations.
G. Hjálmtysson and A. G. Konheim, "Analyzing a Two-Stage Entry Monitor for High-Speed Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 601-610, Apr. 1997.
Abstract: Several researchers have suggested employing two-stage entry monitors for high-speed networks - the first stage enforcing a long term rate, the second stage enforcing a peak rate over a shorter time scale. In spite of this interest, little work on analyzing such systems has appeared. Not only is the analysis hard because of the correlation between the stages, but for the most popular policing scheme, the leaky bucket, prior work is not easily generalized to two stages. This paper presents a performance analysis of a two-stage entry monitor, by analyzing the combined queue length of a two-stage system. Our analysis is for a two-stage buffered moving window. Analyzing such a conservative scheme enables us to bound the penalty of more optimistic schemes, in particular a two stage leaky bucket based system. We obtain a closed form analytical result, and show how to evaluate it for a wide range of parameters of interest. Our results show that the performance penalty of having the second stage is minimal under reasonable rate assumptions.
K. Chang, R. Morris and H. T. Kung, "NFS Dynamics Over Flow-Controlled Wide Area Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 619-625, Apr. 1997.
Abstract: The Network File System protocol (NFS) has been the leading distributed file system for workstations since it was first introduced by Sun Microsystems in 1986. The geographical scale of NFS has been limited to the local area due to its relatively low performance on the wide area Internet. However, with the advent of high bandwidth wide area networks such as ATM, NFS over WANs may become more promising. In this paper, the performance of NFS over various sizes of WAN is studied. The effects of ATM flow-control and queuing strategies on NFS are discussed, as are the performance of TCP and UDP as NFS transport protocols. The primary conclusion is that standard NFS over UDP works well over ATM WANs as long as ATM-level flow control keeps the cell loss rate under one percent. In some cases, NFS over TCP works badly with small packets due to unfortunate interactions with TCP’s congestion window.
J.-S. Wu, M.-T. Sze and J.-K. Chung, "Uplink and Downlink Capacity Analysis for Two-Tier CDMA Cellular Systems," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 626-633, Apr. 1997.
Abstract: The combination of macrocell and microcell in a two-tier cellular system is attractive because it provides a balance between maximizing the number of users per unit area and minimizing the network control associated with handoff. In this paper, we study system capacity of a two-tier cellular architecture employing 3 TDMA/CDMA strategies. Both the uplink and downlink are evaluated via mathematical analysis. It shows that system performance degrades for larger macrocell or microcell and the capacities are poor for users near the macrocells’ boundary. It also shows that huge discrepancy between the results obtained for the center cell versus those obtained for the boundary cell.
X. H. Chen, T. Lang and J. Oksman, "On Algorithms Searching For Quasi-Optimal Subfamilies Suitable For CDMA Applications Of GMW Sequences," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 642-648, Apr. 1997.
Abstract: This paper studies several algorithms for constructing quasi-optimal GMW sub-families in terms of minimized bit error rate under co-channel interference. The results show that performance of resultant sub-families is very sensitive to the algorithms applied and sub-family sizes. A new criterion based on combinational (even plus odd) maximum cross-correlation is introduced for code selection and the resultant highest-peak-deleting and most-peak- deleting algorithms are effective to construct the GMW quasi-optimal sub-families.
A. Orda and N. Shimkin, "Incentive Pricing in Multi-Class Communication Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 659-666, Apr. 1997.
Abstract: We consider a communication network that offers multi-class services to multiple types of traffic. Users choose service classes so as to optimize their own performance. The network associates with each traffic type a nominal service class. Optimal prices should provide incentives for the users to assign each traffic type to its nominal service class. We establish necessary and sufficient conditions for the existence of optimal prices and provide an algorithm for their computation. We indicate that optimal prices can tolerate fluctuations in the various parameters. We then devise a distributed algorithm, with which the network can compute optimal prices even when it does not have sufficient knowledge on the traffic characteristics. Next, we consider an extended model which explicitly includes congestion effects. A key factor which emerges here is the amount of traffic at the disposal of each user. We consider the typical cases of individual, social and type optimization, for which we generalize our results.
J. Misic and S. T. Chanson, "Charging Schemes for ATM Networks Based on Virtual Effective Bandwidths," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 667-674, Apr. 1997.
Abstract: In this paper, we propose charging schemes for ATM networks based on the concept of virtual effective bandwidths (VEB). VEBs were initially developed by the authors to support real-time Connection Admission Control (CAC) in a framework where traffic sources with different quality of service (QoS) requirements are multiplexed into the same finite length queue [6]. VEBs allow different QoS requirements to be related which is important for charging purposes. We propose three charging schemes which can be included in real-time CAC: the first one depends solely on the resource requirements of the call; the second is dependent on resource as well as QoS requirements of the call; the third is dependent on the current traffic intensity of the other connections also.
F. Lo Presti, Z.-L. Zhang, J. Kurose and D. Towsley, "Source Time Scale and Optimal Buffer/Bandwidth Trade-Off for Regulated Traffic in an ATM Node," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 675-682, Apr. 1997.
Abstract: In this paper, we study the problem of resource allocation and control for an ATM node with regulated traffic. Both guaranteed lossless service and statistical service with small loss probability are considered. We investigate the relationship between source characteristics and the buffer/bandwidth trade-off under both services. Our contributions are the following. For guaranteed lossless service, we find that the optimal resource allocation scheme suggests a time scale separation of sources sharing an ATM node with finite bandwidth and buffer space, with the optimal buffer/bandwidth trade-off is determined by the sources’ time scale. For statistical service with a small loss probability, we present a new approach for estimating the loss probability in a shared buffer multiplexor with the so called ``extremal'' on-off, periodic sources. Under this approach, the optimal resource allocation for statistical service is achieved by maximizing both the benefits of buffering sharing and bandwidth sharing. The optimal buffer/bandwidth trade-off is again determined by time scale separation.
Y. Ishibashi, A. Tsuji and S. Tasaka, "A Group Synchronization Mechanism for Stored Media in Multicast Communications," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 692-700, Apr. 1997.
Abstract: This paper proposes a group synchronization mechanism, which synchronizes slave destinations with the master destination, for stored media in multicast communications. At the master and slave destinations, intra-stream and inter-stream synchronization mechanisms which were proposed by the authors are employed to output the master media stream and slave media streams synchronously. We achieve group synchronization by adjusting the output timing of the master media stream at each slave destination to that at the master destination. We also deal with traffic control by media scaling and control of joining an in-progress multicast group. Furthermore, the paper presents experimental results using an ATM network. It shows the validity of the mechanism and illustrates the influence of parameters on the system performance.
M. Sudan and N. Shacham, "Gateway Based Approach for Conducting Multiparty Multimedia Sessions over Heterogeneous Signaling Domains," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 701-710, Apr. 1997.
Abstract: Emerging networking technologies are being introduced with their own management protocols for routing, resource reservation and signaling. This diversity restricts the interoperability among QOS-aware multimedia applications written for different networks. We present an approach for managing multiparty, multimedia sessions in a heterogeneous intern etwork spanning multiple signaling domains. Participants utilize the native signaling on their respective domains and interact with participants on other domains through signaling gateways that bridge the domains and provide translation of signaling procedures and QOS semantics. Data streams are transmitted using a hierarchical representation, which allows participants to independently adjust the reception quality of each stream according to their resources and interests. We present a particular design and implementation details for connecting ATM and IP signaling domains and conclude with its extension to an arbitrary number of interconnected domains.
H.-M. Sun and S.-P. Shieh, "Secret Sharing in Graph-Based Prohibited Structures," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 718-724, Apr. 1997.
Abstract: A secret sharing scheme for the prohibited structure is a method of sharing a master key among a finite set of participants in such a way that only certain pre-specified subsets of participants cannot recover the master key. A secret sharing scheme is called perfect if any subset of participants who cannot recover the master key obtains no information regarding the master key. In this paper, we propose an efficient construction of perfect secret sharing schemes for graph-based prohibited structures where a vertex denotes a participant and an edge does a pair of participants who cannot recover the master key. The information rate of our scheme is 2/n, where n is the number of participants.
P. Janson, G. Tsudik and M. Yung, "Scalability and Flexibility in Authentication Services: The KryptoKnight Approach," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 725-736, Apr. 1997.
Abstract: This paper studies the issues of flexibility and scalability in the context of network security. In particular, it concentrates on authentication and key distribution services suited for a variety of communication paradigms, network environments, and end-devices. We present the design criteria, specification, and step-by-step construction of authentication and key distribution services based on experience in the KryptoKnight project. The central goal of the KryptoKnight project was the construction of basic network security functions in a minimal, flexible (thus, versatile) and scalable manner. Protocol minimality (in terms of resource usage) and flexibility are not merely theoretical goals; they have clear advantages in environments where computational resources are limited and connectivity is restricted, KryptoKnight was aimed at such environments: small and anemic wireless devices, simple network and data-link entities, embedded micro-devices and other special-purpose communication equipment and configurations. Furthermore, scalability of protocols makes their deployment possible in the presence of rapid network growth and inter-domain communication.
T. Kwon, M. Kang and J. Song, "An Adaptable and Reliable Authentication Protocol for Communication Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 737-744, Apr. 1997.
Abstract: In this paper, we propose a new authentication and key distribution protocol which is adaptable and reliable for communication networks. The secrets for authentication, which are chosen from a relatively small space by common users, are easy to guess. Our protocol gives a solution to protect the weak secrets from guessing attacks. Compared with other related work, our protocol is more reliable because it is resistant to various kinds of attacks including guessing attacks, and mom adaptable because it reduces several overheads which make the existing protocols more expensive. We show how to apply our protocol to the Q.931 calling sequences and to the World Wide Web model.
S. H. Low and N. F. Maxemchuk, "An Algorithm to Compute Collusion Paths," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), pp. 745-751, Apr. 1997.
Abstract: In earlier work we have formulated a collusion problem that determines whether it is possible for a set of colluders to collectively discover a target set of information, starting from their initial knowledge, and have presented a complete solution for a special case of the problem. In this paper we present an algorithm that solves the general case. Given a collusion problem the algorithm determines whether it has a solution, and if it does, computes one. A solution to the collusion problem is a method with which the colluders can uncover the hidden information. Communications protocols that employ cryptographic techniques are increasingly used to protect privacy as well as to communicate. A cryptographic protocol defines a process by which information is transferred among some users while hidden from others. The algorithm presented here can be used to determine whether a subset of protocol users can discover, during or after the protocol’s execution, the information that is designed to be hidden from them.
D. Lee, K. K. Ramakrishnan, W. M. Moh and A. U. Shankar, "Performance and Correctness of the ATM ABR Rate Control Scheme," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: We study both correctness and performance of the source/destination protocol of the Available Bit Rate (ABR) service in Asynchronous Transfer Mode (ATM) networks. Although the basic source/destination protocol for congestion management is relatively simple, the protocol specification has to cope with several ``real-world'' cases such as failures and delayed/lost feedback which may introduce complexity. Rigorous proofs of the correct functioning of the protocol based on a formal specification is necessary. We use a formal Extended Finite State Machine (EFSM) model to show that the ABR source/destination protocol is free of live-locks, so that under all conditions both Resource Management (RM) and data cells will be transmitted. We also show that the network options of Explicit Forward Congestion Indication (EFCI) and Explicit Rate (ER) interoperate correctly. While ensuring the correct functioning of the protocol, it is essential that pathological situations do not result in abysmal performance, which is another form of incorrect operation. We use the understanding of the informal English description of the source/destination behavior and of our EFSM model to derive conditions that ensure that the source transmission rate is stable in the presence of delayed or lost feedback RM cells, especially under the operation of a source rule that requires the reduction of the source rate under these conditions. We arrive at bounds on the number of consecutive RM cell losses tolerated while the rate remains stable. It is also of vital importance that the delay for feedback of network state is well understood. There are two components of this delay contributed by the source/destination protocol: the source delay for sending out the probe Forward RM cells and the destination delay to turn-around the Backward RM cell. We provide a worst-case analysis of the delay in turning around RM cells at the destination station and the worst-case interdeparture time of Forward RM cells from the source.
L. A. Kulkarni and S.-Q. Li, "Performance Analysis of Rate Based Feedback Control for ATM Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: Closed-loop input rate regulation schemes have come to play an important role in the transport of the Available Bit Rate (ABR) trafic service category for ATM. In this paper, we present a numerical approach to the performance study of a delayed feedback system with one congested node and multiple connections. This approach consists in modeling the feedback system us a finite Quasi-Birth-Death (QBD) process. Due to the peculiar block tri-diagonol nature of its generator, efficient techniques exist for its steady-state and transient solutions. Using these techniques, we examine a simple parsimonious feedback system for issues such as throughput/loss performance, fairness and stability. Our approach has the flexibility to study the effect of several additional factors such as asynchronous feedback, two-level control and explicit rate notification in the presence of underlying high-priority traffic. This study brings to light the trade-offs between system performance and the complexity of the feedback scheme. Our study shows that the time scales of correlation of the feedback system have a dominant effect on its performance. These time scales are associated with the feedback delay, the durations of active/idle periods of traffic sources and the time scales of the underlying high-priority traffic. We also examine the effect of the time scales on the convergence time for the transient queueing system.
M. Ritter, "The Effect of Bottleneck Service Rate Variations on the Performance of the ABR Flow Control," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: One of the main features of ABR services is the employment of a rate-based flow control mechanism. Feedback from the network switches to the end systems gives users the information necessary to adjust their transmission rates appropriately according to the current network load. This type of control has been investigated to some extent, assuming a constant transmission capacity on a bottleneck link. In this paper we develop a discrete-time analysis to study the effect of bottleneck service rate variations on the performance of the ABR flow control mechanism. Looking at real systems, such variations occur on the one hand due to the establishment and release of ATM connections and on the other hand due to the varying bandwidth demand of VBR connections. To model the rate variations, the bottleneck service rate is assumed to follow a general probability density function
M. Veeraraghavan, G. L. Choudhury and M. Kshirsagar, "Implementation and Analysis of PCC (Parallel Connection Control)," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: In earlier papers, we proposed the PCC (Parallel Connection Control) algorithm for the setup and release of on-demand ATM (Asynchronous Transfer Mode) connections. This paper describes an implementation and analysis of PCC. The PCC algorithm is implemented on a testbed of three types of ATM switches from which service time measurements (software execution times) are obtained. These measured service times are used as input data for an analytical queueing network model to characterize the PCC end-to-end setup delay and maximum throughputs. Assuming all connections pass through ten switches, for this measured data, PCC has a theoretical maximum throughput of 343 calls/sec/switch, and at about 90% of this maximum limit (i.e., at 310 calls/sec/switch), the mean end-to-end connection setup delay is only 43ms. We also compare PCC performance against an equivalent sequential connection setup/release approach. We observe that PCC end-to-end setup delay is much smaller than the sequential setup delay (34% at low load and even smaller at higher load). Also, the per-switch maximum throughput of the PCC approach is 80% more compared to the sequential approach.
C.-L. Ng, S.-W. Seo and H. Kobayashi, "Performance Analysis of Generalized Multihop Shuffle Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: This paper describes the performance analysis of a class of two-connected multihop shufflenets, known as generalized shuffle networks. The topology of such networks is described mathematically by the equation N = kn, where N is the total number of nodes in the network, k the number of stages in the network and n the number of nodes in each stage. Compared to classical shufflenets, the definition of generalized shuffle networks allows a larger number of feasible network structures that are realizable for a given network size N. In attempting to find an optimum network structure, network characteristics are discussed and system performance is evaluated. Important relationships and interdependencies among the various network parameters are developed to facilitate cross-structural comparison.
R. Govindan and A. Reddy, "An Analysis of Internet Inter-Domain Topology and Route Stability," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: The Internet routing fabric is partitioned into several domains. Each domain represents a region of the fabric administered by a single commercial entity. Over the past two years, the routing fabric has experienced significant growth. From more than a year’s worth of inter-domain routing traces, we analyze the Internet inter-domain topology, its route stability behavior, and the effect of growth on these characteristics. Our analysis reveals several interesting results. Despite growth, the degree distribution and the diameter of the inter-domain topology have remained relatively unchanged. Furthermore, there exists a four-level hierarchy of Internet domains classified by degree. However, connectivity between domains is significantly non-hierarchical. Despite increased connectivity at higher levels in the topology, the distribution of paths to prefixes from the backbone remained relatively unchanged. There is evidence that both route availability and the mean reachability duration have degraded with Internet growth.
M. Grossglauser and K. K. Ramakrishnan, "SEAM: Scalable and Efficient ATM Multicast," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: This paper proposes a multipoint-to-multipoint multicast architecture for ATM networks. The necessity for such an architecture stems from the scalability requirements, both in terms of state to be maintained in the network and in terms of the group population dynamics, of a wide range of networking applications. We argue that approaches of using multicast servers or meshes of point-to-multipoint Virtual Circuits (VCS) may be inadequate solutions to this problem. We propose a true multipoint-to-multipoint architecture called SEAM, which uses a single VC for a multicast group consisting of multiple senders and receivers. We achieve this without changes to ATM’s AAL5. SEAM relies on an additional switching feature we call cut-through forwarding, which enables the mapping of several incoming VCS into outgoing VCS. We believe that SEAM is both an important and necessary step in the evolution of ATM. It will enable applications relying on group multicast to benefit directly from ATM’s quality of service support and scalable bandwidth and the resulting performance advantages. Also, it considerably simplifies the problem of supporting IP multicast over large ATM networks.
C. Shields and J. J. Garcia-Luna-Aceves, "The Ordered Core Based Tree Protocol," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: This paper presents a new protocol, the Ordered Core Based Tree (OCBT) protocol, which remedies several shortcomings of the Core Based Tree (CBT) multicast protocol. We show that the CBT protocol can form loops during periods of routing instability, and that it can consistently fail to build a connected multicast tree, even when the underlying routing is stable. The OCBT protocol provably eliminates these deficiencies and reduces the latency of tree repair following a link or core failure. OCBT also improves scalability by allowing flexible placement of the cores that serve as points of connection to a multicast tree. Simulation results show that the amount of control traffic in OCBT is comparable to that in CBT.
R. Ramanathan, "A Unified Framework and Algorithm for (T/F/C)DMA Channel Assignment in Wireless Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: Channel assignment problems in the time, frequency and code domains have thus far been studied separately. Exploiting the similarity of ``constraints'' that characterize assignments within and across these domains, we introduce the first unified framework for the study of assignment problems. Our framework identifies eleven atomic constraints underlying most current and potential assignment problems, and characterizes a problem as a combination of these constraints. Based on this framework, we present a unified algorithm for efficient (T/F/C)DMA channel assignments to nodes or to inter-nodal links in a (multihop) wireless network. The algorithm is parametrized to allow for tradeoff-selectable use as three different variants called RAND, MNF, and PMNF. Using theoretical analysis, we show that the worst-case performance guarantee of PMNF is an order of magnitude better than that of the traditional RAND and MNF for most networks. We also experimentally study the relative performance for one node and one link assignment problem. We observe that PMNF performs the best, and that a larger fraction of unidirectional links degrades the performance in general.
J. Li, N. B. Shroff and E. K. P. Chong, "Channel Carrying: A Novel Handoff Scheme for Mobile Cellular Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: We present a new scheme that addresses the call handoff problem in mobile cellular networks. Efficiently solving the handoff problem is important for guaranteeing Quality of Service (QoS) to already admitted calls in the network. Our scheme is based on a new concept called channel carrying: when a mobile user moves from one cell to another, under certain mobility conditions, the user is allowed to carry its current channel. We propose a new channel assignment scheme to ensure that this movement of channels will not lead to any extra co-channel interference or channel locking. In our scheme, the mobility of channels relies entirely on localized information, and no global coordination is required. Therefore, the scheme is simple and easy to implement. We further develop a hybrid channel carrying scheme that allows us to maximize performance under various constraints. We provide numerical results comparing our scheme with the traditional channel reservation types of techniques. We find that our scheme outperforms the reservation scheme over a broad range of traffic parameters.
Y.-B. Lin and I. Chlamtac, "Effects of Erlang Call Holding Times on PCS Call Completion," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: Previous performance studies of PCS channel allocation assumed that call holding times have an exponential distribution. The exponential call holding time assumption is justified for existing cellular systems, where wireless calls are charged based on the length of the call holding time. Future PCS systems may exercise flat rate billing, and consequently a more general distribution is desirable to model the call holding times. This paper models the call holding times by the Erlang distribution (a generalization of the exponential distribution) to investigate the effect of the variance of the call holding times on the call completion probability. Our analysis indicates that the call completion probability decreases as the variance of the call holding times decreases. This effect becomes more pronounced as the variance of the cell residence times decreases.
Y. Xiong and L. Mason, "Multicast ATM Switches Using Buffered MIN Structure: A Performance Study," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: A (large) multicast ATM switch with external structure of output queueing and internal structure of buffered MINs (multistage interconnection networks) M considered, where the buffered MIN (also called switching network) is composed of switching elements with shared buffer output queueing. Cell replication while routing scheme is used in the switch to implement multicast function. In this paper, we study the performance of the switch with multicast traffic, mainly via computer simulations. The multicast traffic can be random and bursty. From our study we found that for multicast traffic with truncated geometric distribution of cell fanouts it has only a slightly worse impact on the performance of switchzng elements in isolation or in the last stage of the switching network, The multicast traffic has no worse effect on the switch output buffer behavior and cell delay in the switching network. Moreover, traffic splitting can substantially improve the switching network performance for highly bursty traffic. Some analytical approximations are given which could be useful in the dimensioning of switching networks.
K., "Design and Performance Analysis of a Growable Multicast ATM Switch," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: In this paper, we design and analyze a growable multicast ATM switch. It can grow to a large size since both cell routing and contention resolution are designed to distribute over switch elements, and the switch structure is modular. The output ports are partitioned into groups to permit sharing of routing paths. The concept of group routing helps reduce an order of magnitude of switch elements. A two-stage switch architecture is described to illustrate our design principle. The switch can be eastly expanded to a larger size by using more stages. The performance analysis of the switch in terms of cell loss rate, cell delay, mean queue length, mean waiting time, and throughput is conducted using the M/Geom/l model. Experimental results show that the proposed ATM switch not only meets the ATM performance requirements either for unicasting or multicasting but also uses fewer switch elements and has less delay than other comparable switches.
J. Park, L. Jacob and H. Yoon, "Performance Analysis of a Multicast Switch Based on Multistage Interconnection Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: In this paper, we study multicasting in the self-routing multistage interconnection networks (MINs) for asynchronous transfer mode (ATM) switch architectures. Many B-ISDN applications require multicast connections in addition to conventional point-to-point connections. This paper presents a novel approach to support multicast connection, on the basis of a restricted address encoding scheme which constructs a short fixed-size multicast header and a recursive scheme that recycles a multicast packet one or more times through the network to send it to the desired destinations. The proposed two-phase multicast algorithm provides deadlock-free multiple multicast connections in MIN-based ATM switches. The emphasis is on analyzing the performance of an unbuffered MIN-based switch using the multicast algorithm in terms of network throughput. The proposed algorithm can be easily applied to buffered MIN-based ATM switches.
R. H. Lin, C. H. Lam and T. T. Lee, "Performance and Complexity of Multicast Cross-Path ATM Switches," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: A newly proposed large-scale ATM switch called cross-path switch has been shown to be capable of handling multirate traffic efficiently. In this paper, we will study two replication approaches to enhance the switch to support multicasting. The first approach replicates multicast cells at both input and output stages, while the second one replicates cells at the input stage only. A feasible configuration for each scheme is considered and the effect of multicast traffic on the switch performance in terms of throughput and cell loss probability is studied. We observed that, to achieve the same throughput and loss requirement, the second architecture may require fewer switching elements than the first one.
G. Ramamurthy and Q. Ren, "Multi-Class Connection Admission Control Policy for High Speed ATM Switches," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: Broadband networks based on ATM have to support multiple classes of services with widely different traffic characteristics and quality of services. In this paper, we propose and develop a multi-class connection admission control (CAC) policy that supports cell loss and delay requirements. In this mode-based CAC, the source traffic is described in terms of the usage parameter control (UPC) parameters. Through careful analysis and approximations, we derive simple closed-form formulas to calculate the bandwidth required to meet guarantees on quality of service (QoS). While being robust, the CAC achieves a high level of resource utilization and can be easily implemented for real-time admission control.
D. Tse and M. Grossglauser, "Measurement-Based Call Admission Control: Analysis and Simulation," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: We consider the problem of admission control for variable-rate traffic sources sharing a bufferless link, in order to provide a qualitv-of-service in terms of overload probability. Through analysis and simulations, we study the performance of a scheme which has no prior knowledge of the traffic statistics and makes admission decision based on the current network state only. We analyze the dynamics of the system under this control, and show that in the regime of large link capacity and separation of call and burst time-scales, this scheme performs as well as the optimal scheme which has full knowledge of the statistics. We evaluate the performance of the scheme on real traffic sources.
K. A. Hua, S. Sheu and J. Z. Wang, "Earthworm: A Network Memory Management Technique for Large-Scale Distributed Multimedia Applications," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: The two main operating constraints of today’s multimedia servers are the 1/0 bandwidth and communication bandwidth limitations. Both of these problems are addressed in this paper using a novel technique called Earthworm. In this scheme, the network memory is used as a huge cache for buffering multimedia data. Dramatic reduction in the demand on the 1/0 bandwidth, therefore, can be achieved. This scheme also chains display stations to allow them to forward video streams. This strategy eliminates the congestion at the communication port of the server. Removing this bottleneck allows our technique to operate on the vast aggregate bandwidth of the WAN, rather than being constrained by the very limited local bandwidth available to the server. A unique feature of the Earthworm approach is that every display station using the server attempts to make some contribution to the caching space and communication bandwidth. The arrival of a new request, therefore, can be seen as a contributor, rather than just a burden to the server. This characteristic ensures the scalability of our design to support very large multimedia applications.
H. Higaki, K. Shima, T. Tachikawa and M. Takizawa, "Checkpoint and Rollback in Asynchronous Distributed Systems," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: This paper proposes a novel algorithm for taking checkpoints and rolling back the processes for recovery in asynchronous distributed systems. The algorithm has the following properties: (1) Multiple processes can simultaneously initiate the checkpointing. (2) No additional message is transmitted for taking checkpoints. (3) A set of local checkpoints taken by multiple processes denotes a consistent global state. (4) Multiple processes can initiate simultaneously the rollback recovery. (5) The minimum number of processes are rolled back. (6) Each process is rolled back asynchronously. The number of messages for rolling back the processes is O(1) where 1 is the number of channels. Therefore, the system is kept highly available by the algorithm presented in this paper.
L. Libman and A. Orda, "Atomic Resources Sharing in Noncooperative Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: In noncooperative networks, resources are shared among selfish users, which optimize their individual performance measure. We consider the generic and practically important case of atomic resource sharing, in which traffic bifurcation is not implemented, hence each user allocates its whole traffic to one of the network resources. We analyze topologies of parallel resources within a game-theoretic framework and establish several fundamental properties. We prove the existence of and convergence to a Nash equilibrium. For a broad class of residual capacity performance functions, an upper bound on the number of iterations till convergence is derived. An algorithm is presented for testing the uniqueness of the equilibrium. Sufficient conditions for achieving a feasible equilibrium are obtained. We consider extensions to general network topologies. In particular, we show that, for a class of throughput-oriented cost functions, existence of and convergence to a Nash equilibrium is guaranteed in all topologies. With these structural results at hand, we establish the foundations of a design and management methodology, that enables to operate such networks efficiently, in spite of the lack of cooperation among users and the restrictions imposed by atomic resource sharing.
S. Choi and K. G. Shin, "A Cellular Wireless Local Area Network with QoS Guarantees for Heterogeneous Traffic," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: A wireless local area network (WLAN) or a cell with quality-of-service (QoS) guarantees for various types of traffic is considered. A centralized (i.e., star) network topology is adopted as the topology of a cell which consists of a base station and a number of mobile clients. Dynamic Time Division Duplexed (TDD) transmission is used, and hence, the same frequency channel is time-shared for downlink and uplink transmissions under the dynamic control of the base station. We divide traffic into two classes: class I (real-time) and II (non-real-time). Whenever there is no eligible class-I traffic, class-II traffic is transmitted, while uplink transmissions are controlled with a reservation scheme. Class-I traffic is handled with the framing strategy [1] combined with the admmision test for adding new class-I connections. Finally, we present the performance (average delay and throughput) evaluation of the reservation scheme for class-II traffic using both analytical calculations and simulations.
A. H. Wang and M. Schwartz, "Performance Analysis of Multicast Flow Control Algorithms over Combined Wired/Wireless Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: A multipoint flow control framework for data traffic traversing both a wired and wireless network is proposed. A Markov modulated fluid model is used for the receiver to capture the dynamics of the wireless links. We discover that the phase difference of the instantaneous throughput of the receivers is a distinctive feature of muiticast connections. The objectives of the multicast flow control algorithms are to cope with the receiver phase difference cost-effectively in addition to the general goals such as maximizing throughput and minimizing delay. Three ad hoc algorithms have been studied: Listen to Slowest Request (LSQ), Source Estimation (SE), and Open Loop Control. A fluid analysis technique is applied to study the effect of receiver phase difference assuming zero delay. The effect of propagation delay is then discussed. Simulation results are presented to verify the analysis for the zero delay case and to compare the performance of the algorithms under non-negligible delay.
Y. Huang and P. K. McKinley, "Switch-Aided Flooding Operations in ATM Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: In this paper, we propose a flooding method, called Switch-Aided Flooding (SAF), for use in ATM networks. SAF-based protocols take advantage of hardware-supported cell relay and cell duplication, characteristic of such networks, in order to reduce the time needed to disseminate changes in network topology and resource availability. SAF protocols use a spanning multipoint connection (SMC), which is a hardware-switched network spanning tree, but revert to conventional link-by-link flooding when the spanning MC is unavailable or under construction. The results of a simulation study reveal that the proposed flooding protocols deliver network updates several times faster than conventional approaches, while using significantly less bandwidth.
S. Keshav and S. P. Morgan, "SMART Retransmission: Performance with Overload and Random Losses," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: Feedback flow control, in conjunction with limited buffering in the network, inevitably leads to packet loss. Effective congestion control requires not only effective flow control but also a good retransmission strategy. We present a new retransmission strategy called SMART that combines the best features of the traditional go-back-n and selective-retransmit strategies. We show, first, that go-back-n retransmission with static window flow control leads to congestion collapse when the nominal load exceeds the link capacity. Second, we can avert congestion collapse by replacing go-back-n with SMART retransmission, even with static window flow control. Third, SMART retransmission, when combined with Packet-Pair rate-based flow control, performs extremely well, both when losses are due to buffer overflows and when losses are random.
S. Yagyu and H. Takagi, "Performance Characteristics of the D Channel Access Control Scheme," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: In the basic user/network interface of N-ISDN (ITU-T Recommendation I.430), the D-channel is shared by up to 8 terminals for signal and data packets. An analytical model is proposed to reveal the performance characteristics of the access control scheme for the D-channel. Numerical and simulation results are shown to demonstrate the performance differentiation of the terminals with different priorities. It is observed that the mean signal delay at low load may become large because of long service time for packets, and that the priority mechanism may not work properly when the loads at terminals are very asymmetric.
C. S. Hood and C. Ji, "Proactive Network Fault Detection," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: The increasing role of communication networks in today’s society results in a demand for higher levels of network availability and reliability. At the same time, fault management is becoming more difficult due to the dynamic nature and heterogeneity of networks. We propose an intelligent monitoring system using adaptive statistical techniques. The system continually learns the normal behavior of the network and detects deviations from the norm. Within the monitoring system, the measurements are segmented, and features extracted from the segments are used to describe the normal behavior of the measurement variables. This information is combined in the structure of a Bayesian network. The proposed system is thereby able to detect unknown or unseen faults. Experimental results on real network data demonstrate that the proposed system can detect abnormal behavior before a fault actually occurs.
C.-S. Wu, G.-K. Ma and P.-N. Chen, "Architecture for Two-Way Data Services Over Residential Area CATV Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: An architectural design for high speed residential data access using the traditional IEEE 802.3 medium access protocol over the existing CATV network is proposed. The described architecture is attractive in using the existing infrastructure combined with the existing access scheme in the residential area and thus it is cost effective and well suited for home internet access. However, the traditional CSMA/CD protocol is not suitable for the cable TV network due to its long propagation delay. Thus, we propose to combine the existing IEEE 802.3 CSMA/CD MAC with the segmented cable subnetworks so that a home user can get access to the internet as if he is using the Ethernet at 10Mbps,or Fast-Ethernet at 100Mbps. Only three subcarriers in the passband cable is used and therefore it will not interfere with the traditional broadcasting channels and the future digital video channels. The segmented cable are interconnected by the defined Cable Bridge (CB) and a simple flow control mechanism is proposed among the CBs. Functional components and operations of each CB will also be described. For a fair performance among the subnetworks, a prioritized queueing scheme is also proposed on each CB.
Liao J.-W, J.-Y. Wang, W.-T. Lee and L.-Y. Kung, "Multiple Priority CSMA-type Multichannel Local Area Network," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: In this paper, we will introduce a new network access protocol for CSMA-type multichannel local area network (MLAN). This new protocol has the capability of providing different network access priority among the various applications. From the earlier research, it has been shown that the CSMA-type MLAN is superior to a single channel on the equal network bandwidth. On the basis of the developed MLAN architecture, we construct a new network access protocol to provide multiple transmission priorities for various applications, e.q., text, voice, video, image, etc. This protocol is called Multiple-Priority Multichannel Local Area Network (MP-MLAN). The data transmission of MP-MLAN is collision-free, and we can find the throughput characteristics of MP-MLAN are higher and more stable than the conventional CSMA/CD or Multichannel CSMA/CD network from the analysis results. A queueing analysis model for representing the MP-MLAN protocol is established, and simulation results are also provided to evaluate the performance of this network.
A. Muir and J. J. Garcia-Luna-Aceves, "Group Allocation Multiple Access with Collision Detection," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: The Group Allocation Multiple Access with Collision Detection (GAMA/CD) protocol for scheduling variable-length packet transmissions in a local area net work is specified and analyzed. GAMA/CD provides the advantages of both TDMA and CSMA/CD by maintaining a dynamically-sized cycle that varies in length depending on the network load; each cycle is composed of a contention period and a group-transmission period. During the contention period, a station with one or more packets to send competes for membership m the transmission group. Once a member of the transmission group, a station is able to send data without collision during each cycle; as long as a station has data to send, it maintains its position in the group. This can be viewed as either allowing stations to ``share the floor'' in an organized manner, or as establishing frames that are not synchronized on a slot-basis and vary their length dynamically based on demand. Both the throughput and the delay of GAMA/CD are presented and analyzed. To validate our analysis, the results of both models are compared to the throughput and delay produced by a simulation of GAMA/CD.
Y. Lapid, R. Rom and M. Sidi, "Analysis of Packet Discarding Policies in High-Speed Networks," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: In this work, selective discarding policies, as a means for congestion avoidance, are studied and compared to non-discarding policies. The Partial Message Discard policy discards packets of tails of corrupted messages. An improvement to this policy is the Early Message Discard that drops entire messages and not just message-tails. A common performance measure of network elements is the elective throughput which measures the utilization of the network links but which neglects the application altogether. We adopt a new performance measure, goodput, which reflects the utilization of the network from the application's point of view and thus better describes network behavior. We develop and analyze a model for systems which employ discarding policies. The analysis shows a remarkable performance improvement when any message-based discarding policy is applied, and that the Early Message Discard policy performs better, especially under high loads. We compute the optimal parameter setting for maximum goodput at different input loads and investigate the performance sensitivity to these parameters.
T. V. Lakshman, U. Madhow and B. Suter, "Window-Based Error Recovery and Flow Control with a Slow Acknowledgement Channel: A Study of TCP/IP Performance," in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Kobe, Japan), Apr. 1997.
Abstract: With the envisaged growth in Internet access services over networks with asymmetric links such as Asymmetric Digital Subscriber Line (ADSL) and Hybrid Fiber Coax (HFC), it becomes crucial to evaluate the performance of window-based protocols over systems in which the reverse link is considerably slower than the forward link. Even if the actual bandwidth asymmetry is moderate, high effective asymmetries can result because of bidirectional traffic. Our objective is to determine, whether TCP/IP performs reasonably in a setting in which the reverse link is the primary bottleneck. Our main results are: (1) For both the prevalent Tahoe version with Fast Retransmit and the Reno version of TCP, we determine the throughput as a function of buffering, round-trip times and normalized asymmetry (taken to be the ratio of the transmission time of ACKs in the reverse path to that of data packets in the forward path). We identify three modes of operation which are dependent on the forward buffer sizes and the normalized asymmetry. (2) Asymmetry increases TCP’s already high sensitivity to random packet losses that might be caused by transient bursts in real-time traffic. Specifically, random loss leads to significant throughput deterioration when the product of the loss probability, the asymmetry and the square of the bandwidth delay product is large. (3) Congestion in the reverse path adds considerably to TCP’s unfairness when multiple connections share the reverse link. Link bandwidth sharing is unfair even for connections with identical round-trip times and hence use of per connection buffer allocation on the reverse path appears essential.
netbib software created by H. Schulzrinne. Report problems to schulzrinne@cs.columbia.edu. Sun Dec 05 16:59:53 EST 1999