In this work, we study the problem of efficient resource selection in real-time distributed systems. Specifically, we study how a client in the presence of measurement uncertainty can rapidly select a resource (target) that exhibits good network connectivity. The problem has many applications, including peer selection in P2P systems, server/gateway selection in IP telephony, and overlay routing. A probing-based search strategy is complicated by the potentially large number of targets and the inherent uncertainty in measurement results due to, for instance, small measurement sample sizes and other forms of "noise." We parameterize the problem based on the number of available targets, the number of "good" targets, and various network characteristics. We introduce a framework called spatial slow start (SSS) for searching the target space. SSS can be considered as a parameterized tree search with an interesting twist: apart from the target search space, the rate of probing per target is also manipulated at each step. A detailed simulation study provides insight on what SSS choices are significant under different network conditions. The simulation study also establishes that previously proposed techniques, namely, a random selection (RAND) algorithm that does not do any probing, and a "quick probe and select the best" (QPS) technique work well, but only in some situations. Based on these insights, we present an adaptive SSS algorithm that not only guides the search process according to its measurements of various system parameters, but also changes its search parameters in response to the quality of the measurements themselves. This new adaptive SSS algorithm performs as well as RAND and QPS in situations where RAND and QPS are efficient, and outperforms them in other cases.

Network topology information has many uses for networked applications including the design of reliability and performance enhancing schemes. This information is often acquired by network discovery techniques that rely on ICMP and/or SNMP support from the infrastructure. Unfortunately, network infrastructure may support such services at varying levels. In cases where such support is limited, techniques based on strictly end-to-end measurements have been proposed in the literature to infer a logical topology. In this paper, we propose an end-to-end measurement technique that is complimentary to the earlier techniques and relies on multiple-source multiple-destination probing to collect network wide measurements faster. Our technique relies on the interaction between streams of packets at various nodes in the network. Specifically, we aim to measure the reaction of end-to-end probes to a short burst of concentrated traffic (signal) injected to the network. The key assumption is that probes traversing paths that physically intersect with the path of the bursty traffic (signal path) will exhibit extra jitter. The occurrence of extra jitter in the probe packet inter-arrival times matching the signal bursts indicates that the paths of the probe and signal intersect. We conducted an empirical study on an actual production network to evaluate the ability of the technique to detect end-to-end path intersections. Our empirical results indicate that in the network we considered the technique successfully detected path intersections.

Application-layer path switching systems ensure the performance and reliability of real-time applications (such as IP Telephony) by exploiting inherent redundancies in the underlying IP network. These systems monitor quality throughout an IP Telephony call, rapidly detect performance problems and, if necessary, re-direct calls around problems and congestion in the network. Under normal network load conditions, these systems can easily find a feasible alternate path and restore call quality within sub-second timeframes. However, at high network load, finding alternate paths is challenging due to inherent inaccuracies in the techniques that attempt to measure an end-to-end path’s ability to accommodate additional calls. These inaccuracies may adversely impact established calls on the path and some of the calls may even oscillate back and forth between various alternate paths. In this paper, we propose some novel techniques that address these problems and ensure system stability and performance at high network load. We introduce the concept of Spatial Slow Start, which allows rapid selection of a feasible path from a large possible set. In addition, we help protect a path’s established calls from other switching calls by using intelligent back-off and probationary admission control techniques. We conducted extensive simulation studies to evaluate the performance of the proposed techniques. The results indicate that our techniques significantly reduce the number of oscillations and the amount of time that calls experience poor quality.

Application-layer solutions to improve the reliability of realtime applications such as IP telephony exploit the inherent redundancy in networks. Earlier work has shown that the ISP networks provide sufficient redundancy that can be used by such overlay solutions. Enterprise networks, on the other hand, are designed differently from ISP networks, and implementing an overlay on enterprise networks introduces additional constraints. In this paper, we explore the level of redundancy in enterprise networks that would justify an application-layer reliability solution, while taking into account the unique characteristics of enterprise deployments. We report the findings of an empirical study we conducted on nine real enterprise networks of varying sizes. Specifically, we quantify the amount of redundancy in enterprise networks and the protection level that can be achieved by single-hop versus multi-hop overlays. Our results indicate that, among the networks we considered, on average 30% and up to 86% of the nodes on end-to-end paths can be protected. Furthermore, in these networks going from a single-hop overlay to a multiple-hop overlay provided only marginal benefits.

Maintaining good quality of service for real-time applications like IP Telephony requires quick detection and reaction to network impairments. In this paper, we propose and study novel measurement techniques in ORBIT, which is a simple, easily deployable architecture that uses single-hop overlays implemented with intelligent endpoints and independent relays. The measurement techniques provide rapid detection and recovery of IP Telephony during periods of network trouble. We study our techniques via detailed simulations of several multi-site enterprise topologies of varying sizes and three typical fault models. We show that our proposed techniques can detect network impairments rapidly and rescue IP Telephony calls in sub-second intervals. We observed that all impacted calls were rescued with only a few relays in the network and the run-time overhead was low. Furthermore, the relay sites needed to be provisioned with minimal additional bandwidth to support the redirected calls.

Short, low-bandwidth keep-alive packets can be injected into VoIP packet streams to rapidly detect faults and deteriorating network conditions (e.g., increasing delay, jitter, or loss). The keep-alive packets can be duplicated and also used to continuously monitor and compare the delay and loss characteristics of primary and alternate network paths, and thereby help control the rapid switchover of calls (in-progress and future) to alternate routing paths (or the circuit-switched PSTN) when faults or deteriorating QoS conditions are detected. By simultaneously transmitting copies of keep-alive packets over multiple paths to make the differential delay measurements and comparisons, the proposed techniques avoid many common synchronization and timing errors. We examine various performance tradeoffs and describe several ways to implement the proposed architectures and techniques.

A lot of ongoing work is geared towards improving the reliability, performance and QoS characteristics of service provider IP networks. In contrast, we propose novel enterprise-based techniques that exploit the fact that many enterprises are multi/dual-homed. Certain (e.g., VoIP) packets are duplicated and sent over multiple service providers. After traversing the service provider networks, only the first-to-arrive packets are kept and the later-arriving copies are discarded. In so doing, the result is not only better protection against node and link failures, and packet losses and errors, but also better QoS performance under normal (fault-free) operation. The packet-duplication process can be policy-based and take into account costs, bandwidth, and priority issues, permitting the system to behave like a simple "smart router" that automatically and continually makes use of the best (lowest-delay) service provider.

The impact of network failures can be minimized if users are promptly notified by appropriately designed applications. Specifically, for voice-over-IP (VoIP) networks, an RTP/RTCP-based detection method can be used to rapidly distinguish between network congestion and network failures. Users and network managers can exploit this information in various ways, such as rapid network recovery or seeking alternatives at the application layer. In this paper, we present the main ideas behind these proposals, some analytical/simulation results, insights from a Linux-based implementation and experimental results.

No packets will be dropped inside a packet network, even when congestion builds up, if congested nodes send backpressure feedback to neighboring nodes, informing them of unavailability of buffering capacity-stopping them from forwarding more packets until enough buffer becomes available. While there are potential advantages in backpressured networks that do not allow packet dropping, such networks are susceptible to a condition known as deadlock in which throughput of the network or part of the network goes to zero (i.e., no packets are transmitted). In this paper, we describe a simple, lossless method of preventing deadlocks and livelocks in backpressured packet networks. In contrast with prior approaches, our proposed technique does not introduce any packet losses, does not corrupt packet sequence, and does not require any changes to packet headers. It represents a new networking paradigm in which internal network losses are avoided (thereby simplifying the design of other network protocols) and internal network delays are bounded.

When congestion builds up in a packet network, two general approaches are possible to cope with the shortage of buffer space. One approach is to drop incoming packets for the buffer that is not available and to rely on the end-to-end protocols for the recovery of lost packets. The alternative approach is to insist that no packets should be dropped inside a packet network, even when congestion builds up. One way to accomplish this goal is to have the congested nodes send backpressure feedback to neighboring nodes, informing them of unavailability of buffering capacity and in effect stopping them from forwarding packets until enough buffer becomes available. While there are potential advantages in backpressured networks that do not allow packet dropping, such networks are susceptible to a condition known as deadlock in which throughput of the network or part of the network goes to zero (i.e., no packets are transmitted). In this paper, we describe a simple, lossless method of preventing deadlocks and livelocks in backpressured packet networks. In contrast with prior approaches, our proposed technique does not introduce any packet losses, does not corrupt the packet sequence, and does not require any changes to packet headers. In addition to presenting the new congestion control protocol in a general context, we describe an important application of the technique to Gigabit Ethernet (IEEE 802.3z).

This paper proposes algorithms for handoff, location, and connection management in a wireless asynchronous transfer mode (ATM) local-area network (LAN). Fast handoffs while maintaining cell sequence and quality-of-service (QoS) guarantees are achieved by distributing switching functionality to base stations, and using a networking scheme based on provisioned virtual trees. A new distributed location management scheme using a minimal registration procedure and broadcasts on wired links is proposed for this LAN. The detailed signaling procedures that support the algorithms for mobility and connection management are described. Finally, an implementation of these procedures and an analysis of the measured data is presented. Measurements of service times obtained from this implementation indicate that over 100 calls/s. can be handled by each node in 50-node network with a high-percentage of mobiles (75%) relative to fixed endpoints. This is comparable to current wired ATM switch call handling throughputs, in spite of the fact that these nodes perform additional handoff and location management functions. The data also indicates handoff latency times of 1.3 ms. This validates our proposal for maintaining cell sequence while performing handoffs.

In a wireless packet (e.g., ATM) network that supports an integrated mix of multimedia traffic, a large variety of mobiles with different service rates will need to be accommodated efficiently in a bandwidth-on-demand fair-sharing manner. We propose and study multi-code CDMA (MC-CDMA) with distributed-queueing request update multiple access (DQRUMA) for multi-rate wireless packet networks. The network incorporates MC-CDMA (a flexible multiplexing scheme for providing multi-rate packet transmissions) and DQRUMA (an efficient demand-assignment multiple access protocol for wireless access and scheduling) to form a unified bandwidth-on-demand fair-sharing platform for multi-rate wireless services. A slot-by-slot packet transmit scheduling policy provides the possibility of slot-by-slot allocation of pseudo-noise (PN) codes (primary codes) and optimal power levels to the mobiles involved in packet transmissions. Also, a maximum capacity power allocation (MCPA) criterion is derived to exploit the subcode concatenation property of the MC-CDMA transmission. Simulation results show that the system provides close to ideal-access performance for multi-rate mobiles, both with homogeneous traffic characteristics and with a mix of heterogeneous traffic characteristics.

Multi-code direct-sequence code division multiple access (MC-CDMA) has been proposed as a flexible multiple access scheme for wireless packet networks that support a large variety of mobiles with different and even time-varying rates. However, the interference model typically used with conventional DS-CDMA cellular systems - a large number of low-power mobiles uniformly distributed in cells - may not hold. In MC-CDMA cellular systems, it is possible for a high-rate mobile, perhaps near the boundary of a cell, to have all the codes for high-rate transmission - therefore transmitting at high power and causing significant interference to the neighboring cell. In this study, we analyze the effects of MC-CDMA intercell interference on the reverse link (i.e., mobile to cell site) and investigate a maximum capacity power allocation (MCPA) criterion that exploits the sub-code concatenation property of MC-CDMA transmission. When the transmission rate is high, power control with MCPA criterion can significantly reduce reverse-link MC-CDMA intercell interference. However, with only four codes per mobile (e.g., as in IS-95), the reduction in intercell interference is less than 1 dB.

We propose a time-frequency-code-slicing technique that allows multiple users with different speed requirements access to a communications resource in a manner that is cost effective over a wide range of access speeds. Conventional systems require low-speed users to either pay a cost premium (e.g., high-speed burst modems for TDMA) or end up wasting some of the spectrum (e.g., universal time slots). The advantages of our proposed scheme can be demonstrated with any two combinations (or all three) of time slicing, frequency slicing, and code slicing. For instance, with a time-frequency-slicing approach, users can be assigned different portions of the spectrum (e.g., on a slot-by-slot basis), allowing them access to only the needed fraction of the shared resource. With time-code slicing, users are dynamically granted portions of the code space, during specified time periods. Finally, in frequency-code slicing, a user may be assigned a number of codes in different frequency bands. These codes can be of constant or variable chip rates.

We propose a distributed reservation protocol for high-speed, star-based, local-communication systems with heterogeneous users. The users have different delay, throughput, and priority requirements, and each user has knowledge of only its own traffic mix. At light loads, the usual delay overhead of reserveration schemes can be eliminated. Also, the probability of correct reservation reception is improved: it is only necessary to detect the presence or absence of a signal since reservation signals do not carry address information or the desired amount of channel time. Users know the value of a global reservation counter, which specifies the amount of transmission time acquired by a reservation. The protocol can support both circuit- and packet-switched traffic (e.g., integrated voice and data).

The use of two resource-sharing techniques for congestion control in a backbone asynchronous transfer mode (ATM) network consisting of ATM cross-connects interconnected with high-speed optical links such as 2.4-Gb/s OC-48c fibers is studied. Memory sharing allows an optimal shared use of buffer space in an ATM switch fabric. Channel (or line) sharing, on the other hand, takes advantage of spare line capacity in the system to permit temporary increases in the output rates of the congested output ports. Fundamental bounds on delay-throughput performance and buffer requirements for specific cell loss rates are presented, and two practical application scenarios, representing line protection arrangements with and without service access capabilities, are introduced.>

The authors propose a single way to dramatically improve the performance of input-queued ATM packet switches beyond the 82% saturation point obtained in previous work. The method is an extension of the independent output-port schedulers technique and is based on the notion of recycled time slots, i.e. reusing time slots normally wasted due to scheduling conflicts. In contrast to previous results, the technique yields a throughput improvement from 65% to 92% without speedup, trunking, or complicated hardware. If input grouping with a group size of four is also employed, then the method can yield up to 95% throughput.>

The problem of designing a large high-performance, broadband packet of ATM (asynchronous transfer mode) switch is discussed. Ways to construct arbitrarily large switches out of modest-size packet switches without sacrificing overall delay/throughput performance are presented. A growable switch architecture is presented that is based on three key principles: a generalized knockout principle exploits the statistical behaviour of packet arrivals and thereby reduces the interconnect complexity, output queuing yields the best possible delay/throughput performance, and distributed intelligence in routing packets through the interconnect fabric eliminates internal path conflicts. Features of the architecture include the guarantee of first-in-first-out packet sequence, broadcast and multicast capabilities, and compatibility with variable-length packets, which avoids the need for packet-size standardization. As a broadband ISDN example, a 2048*2048 configuration with building blocks of 42*16 packet switch modules and 128*128 interconnect modules, both of which fall within existing hardware capabilities, is presented.>

The performance of a growable architecture for broadband asynchronous transfer mode (ATM) switching consisting of a memoryless self-routing interconnect fabric and modest-size packet switch modules is examined. The cell loss probability is the focus because the architecture attains the best possible delay-throughput performance if the packet switch modules use output queuing. There are two sources of cell loss in the switch. First, cells are dropped if too many simultaneous arrivals are destined to a group of output ports. Second, because a simple, distributed path-assignment controller is used for speed and efficiency, cells are dropped when the controller cannot schedule a path through the switch. The authors compute an upper bound on arrivals, possibly including isochronous circuit connections, and show that both sources of cell loss can be made negligibly small.>

The authors describe a simple adaptive routing scheme for datagram (connectionless) and virtual circuit (connection-oriented) transmission that relieves congestion resulting from nonuniform traffic patterns and network failures. The authors describe a fixed-routing algorithm for dedicated channel ShuffleNets. Based on the fixed routing algorithm, an adaptive routing scheme for datagram transmission is presented followed by performance results for uniform and nonuniform traffic patterns and fault tolerance. The adaptive routing of datagrams uses only the local queue size information available at the network interface units (NIUs) and redistributes the load as congestion develops. Since datagrams are individually routed through the network, they may not arrive at their destination in the order they were generated and may need to be resequenced. The authors compute an upper estimate on the resequencing buffer size for stream traffic. A virtual circuit version of the adaptive routing algorithm eliminates the need for resequencing buffers.>

A multiconnected ring is a ring-structured network in which each node is also connected by chords to other nodes of the ring. The span of a chord is the number of nodes counted between the endpoints of the chord (only one endpoint is included). A multiconnected ring is defined as being nested if it is rotationally symmetric and if the span of each chord is an integral multiple of the spans of each of the shorter chords. For local and metropolitan area networks, a nested multiconnected ring (NMCR) can be implemented as a multifiber ring network in which each node receives and transmits on a subset of the fibers in a bundle or cable. Because of the rotational symmetry, NMCRs permit an identical connector to be used at each node. A NMCR is one of several intermediary networks between a ring and a fully connected network. Under a performance criterion that takes throughput, equipment cost, and complexity into account, an optimized NMCR outperforms both its extreme counterparts. Although ShuffleNet multiconnected rings can provide higher throughput per node than NMCRs, the rotational symmetry and identical connectors of NMCRs make them preferable for applications with many nodes and lower throughput-per-node requirements.>

The fiber distributed data interface (FDDI) and the IEEE 802.6 distributed queueing dual bus (DQDB) are emerging standards for high-speed (45-150-Mb/s) local and metropolitan area networks. The authors describe several ways to build on these emerging standards to significantly increase the achievable throughput and lower th e end-to-end delay. Without increasing the number of transceivers or their rate, substantial throughput increases are obtained by a highly concurrent logical interconnection pattern of user modes, and the end-to-end delay is decreased by the use of more efficient media-access techniques. The most promising architecture is a multiconnected ring having only two transmitters and two receivers per node, where each node needs to handle or process only a small fraction of the network traffic. In one example, the authors describe a 24-node, distributed, packet-switched network, with only two 100-Mb/s transmitters and two 100-Mb/s receivers per node; it has a maximum throughput of 1.5 Gb/s-15 times the 100/Mb/s throughput of FDDI. Such a system has the potential to be a follow-on standard to FDDI (or IEEE 802.6) or to provide a high-performance LAN/MAN that can interwork with standard systems.>

Consideration is given to the effects of time-multiplexed stream traffic on the performance of a store-and-forward packet switch. Substantially reducing the amount of buffering in the switch results in only a small probability that an existing circuit will be disrupted during the length of its connection. For example, with a circuit-switched frame of length 1000 and 100% loading, reducing the buffer size from 999 packets to 83 results in only a 10/sup -6/ circuit-disruption probability.>

The authors study the performance of four different approaches for providing the queuing necessary to smooth fluctuations in packet arrivals to a space-division packet switch. They are (1) input queueing, where a separate first-in, first-out (FIFO) buffer is provided at each input to switch; (2) input smoothing, where a frame of b packets is stored at each of the N input lines to the switch and simultaneously launched into a switch fabric of size Nb*Nb; (3) output queuing, where packets are queued in a separate FIFO buffer located at each output of the switch; and (4) completely shared buffering, where all queuing is done at the outputs and all buffers are completely shared among all the output lines.>

The authors propose a multihop wavelength-division-multiplexing (WDM) approach, referred to as ShuffleNet, for achieving concurrency in distributed lightwave networks. ShuffleNet can be configured with each user having as few as one fixed-wavelength transmitter and one fixed-wavelength receiver, avoiding both wavelength agility and pretransmission coordination problems. Still, the network can achieve at least 40% of the maximum efficiency possible with wavelength-agile transmitters and receivers. To transmit a packet from one user to another, however, may require routing the packet through intermediate users, each repeating the packet on a new wavelength, until the packet is finally transmitted on a wavelength that the destination user receives. For such a multihop lightwave network, the transmit and receive wavelengths must be assigned to users to provide both a path between all users and the efficient utilization of all wavelength channels. A class of assignment schemes is proposed which is based on a generalization of the perfect shuffle and achieves high efficiency for uniform traffic loads. Physically, the network may take on a variety of topologies, including a bus, tree, or star.>

In many applications, such as metropolitan area, campus, and local area networks, multicomputer interconnection networks, and the interconnection of cabinets, shelves, and boards, optical interconnection is increasingly favored over electrical. Recently, ShuffleNet multihop lightwave networks were proposed as a way to tap the vast bandwidth potential of optical fiber for multiuser packet communications. We consider the use of ShuffleNet multihop networks for optical interconnection, and study their implementation in ring topologies with each node connected to several other nodes of the ring (i.e., multi-connected ring topologies). To minimize fiber cabling congestion, the design procedure uses a new representation of the ShuffleNet connectivity graph and a generalization of Gray code patterns. As an example, only six fibers (without wavelength-division multiplexing) are required to interconnect 24 Network Interface Units (NIUs), providing a total network throughput of 1.47 Gb/s for an optical transmission rate of 100 Mb/s. The design also provides for easy, modular growth of multi-connected rings.

The authors study the performance of four different approaches for providing the queuing necessary to smooth fluctuations in packet arrivals to a high-performance packet switch. They are (1) input queuing, where a separate buffer is provided at each input to the switch; (2) input smoothing, where a frame of b packets is stored at each of the input line to the switch and simultaneously launched into a switch fabric of size Nb*Nb; (3) output queuing, where packets are queued in a separate first-in first-out (FIFO) buffer located at each output of the switch; and (4) completely shared buffering, where all queuing is done at the outputs and all buffers are completely shared among all the output lines. Input queues saturate at an offered load that depends on the service policy and the number of inputs N, but is approximately 0.586 with FIFO buffers when N is large. Output queuing and completely shared buffering both achieve the optimal throughput-delay performance for any packet switch. However, compared to output queuing, completely shared buffering requires less buffer memory at the expense of an increase in switch fabric size.>

Two simple models of queueing on anN \times Nspace-division packet switch are examined. The switch operates synchronously with fixed-length packets; during each time slot, packets may arrive on any inputs addressed to any outputs. Because packet arrivals to the switch are unscheduled, more than one packet may arrive for the same output during the same time slot, making queueing unavoidable. Mean queue lengths are always greater for queueing on inputs than for queueing on outputs, and the output queues saturate only as the utilization approaches unity. Input queues, on the other hand, saturate at a utilization that depends onN, but is approximately(2 -\sqrt{2}) = 0.586whenNis large. If output trunk utilization is the primary consideration, it is possible to slightly increase utilization of the output trunks-upto(1 - e^{-1}) = 0.632asN \rightarrow \infty-by dropping interfering packets at the end of each time slot, rather than storing them in the input queues. This improvement is possible, however, only when the utilization of the input trunks exceeds a second critical threshold-approximatelyln (1 +\sqrt{2}) = 0.881for largeN.