The topology update mechanism is a key element in a link-state routing algorithm, providing information on which all routing decisions are based. Topology update schemes are essential for coping with link/node failures and recoveries, increasing load levels, and the addition and deletion of links/nodes. The effectiveness of topology update mechanisms for ATM networks for connection oriented services is studied through simulation. We concentrate on link failures, and the rerouting that takes place after a failure. The proposed topology update scheme informs all network nodes of the status of the links/nodes and the flow levels on each link for each connection priority. We define a performance metric that measures the level of control message activity in the network. We compare the proposed scheme with one that does not provide flow level information, but only informs the routing entity at which link an establishing connection was blocked or preempted. The efficiency of the proposed scheme is shown to be much better than the alternative as measured by the defined performance metric.

Buffer allocation for frame reassembly and queueing in the destination node of an ATM subnetwork supporting multiple frame relay connections is examined. The finite peak rate of a frame relay connection is explicitly modeled and shown to be an important factor in buffer sizing. Specifically, the average number of buffers required is shown to be large when many low-peak-rate frame relay connections are multiplexed for delivery to a single high-speed frame relay interface port, but the tail of the distribution is determined only by aggregate traffic statistics.>

Conventional allocation of network resources for connection management is by and large static. For each performance parameter that is negotiated during a call setup, its agreed value must be maintained throughout the duration of the call. Due to a dynamic networking environment, the result of quality of service (QOS) negotiation during call establishment may not remain ideal throughout the duration of a call. The authors propose a method for managing connections, in a connection-oriented integrated communication network, to maintain acceptable QOS for the entire duration of each connection, to make QOS improvements whenever possible, to recover from connection failures and call preemption, as well as to partially retrieve allocated resources to relieve network overload.>

A closed-loop, rate-based congestion control mechanism for ATM cell relay networks is presented. The goal of the congestion control mechanism is to guarantee the negotiated quality of service during overload conditions, and to allow a connection to exceed its negotiated throughput when there is unused capacity along its path through the network. With this control mechanism, the rate of an end system is adjusted based on both the network congestion state and whether its rate is within the negotiated parameters. The performance of this control mechanism for file transfer traffic is illustrated by results from simulations, Using a simple analytical model, the worst case buffer requirement and file transfer delay are analysed. From the analysis, conditions are derived for the rate increment, rate decrease factor and initial rate that minimize the buffer requirement and file transfer delay. From the analytical results, an adaptive rate reduction scheme is suggested to improve performance.>

The leaky bucket algorithm, which has been proposed as a monitor/enforcer in the rate-based management of bandwidth in high-performance, integrated packet communication networks, is considered. The effectiveness of the unbuffered leaky bucket algorithm in protecting the quality of service (QOS) experienced by connections passing through a common internodal link queue is studied. It is shown that excess traffic generated by a source can pass through the leaky bucket without marked or discarded and cause unacceptable packet delay/loss to other connections sharing the queue. It is also shown that average bursts that are larger, or average rate that is higher, than that assumed at connection establishment can deteriorate the queue performance even with the leaky bucket enforcing the agreed throughput QOS by discarding packets. On the basis of this analysis, a strategy for alleviating these problems is devised, namely, allocating network bandwidth above the leaky bucket permit rate and configuring the leaky bucket with a loss/mark probability greater than 10/sup -2/.>

Routing subject to multiple quality-of-service (QOS) constraints is considered. Such a problem arises in both private corporate backbone networks and public switched networks, and will become even more prevalent in the future with the emergence of asynchronous transfer mode (ATM) networks. A rule-based call-by-call source routing strategy that makes use of routing fallbacks to accommodate users with diverse QOS requirements is proposed.>

A crucial problem facing the designers and deployers of future high-speed networks is providing applications with quality of service (QOS) guarantees. For soft real-time applications, which are delay sensitive but loss tolerant, delay distribution is an important QOS measure of interest. In this paper we study (through simulation) the end-to-end delay distribution seen by individual sessions under simple first-come first-served (FCFS) multiplexing in a network model with two significant features: (1) all traffic is connection-oriented, (2) cross traffic along routes is representative of that seen by calls in a moderately sized wide area network (i.e., less than 100 switches). We compare these delay distributions with the worst case point-valued analytic delay bounds predicted by three different techniques for providing such bounds (two of which require a more sophisticated link-level scheduling policy). We also consider the per-hop delay distributions seen as a session progresses deeper into the network and determine the sensitivity of these delay distributions to the manner in which the interfering traffic is modeled. Finally, we use our delay distribution results to examine the tradeoff between the QOS requested by a call, the manner in which the QOS guarantee is provided, and the number of calls that are admitted at the requested QOS.

When congestion occurs in a packet queuing system, packets can be dropped from the rear or the front of the queue. It is demonstrated that the probability of a packet being dropped is the same in systems with rear and front packet dropping. It is shown that the probability of a packet being delayed longer than a given value in a system with front dropping is less than or equal to that in a system with rear dropping. It is further illustrated that front dropping not only improves the delay performance on an internodal link, but also provides the overall loss performance for time constrained traffic such as packet voice.>

The problem of transporting constant-bit-rate (CBR) traffic through a packet network is analyzed. In the system considered, CBR traffic is packetized and packets from several similar sources are multiplexed on a transmission link. The bit streams are recreated at the receiving end by demultiplexing the packets and then playing out the packets of each CBR stream. Traffic fluctuations may cause gaps to appear in the playout process. Their frequency can be reduced by adding a smoothing delay to each stream. The queueing system analyzed has periodic arrivals and deterministic service times. A method of analysis, based on the ballot theorems of Takacs (1967), is presented to provide steady-state delay distributions as well as a transient analysis of the system to predict the statistics of the time for a gap to develop in the CBR stream as a function of the smoothing delay.>

To achieve better statistical gain for voice and video traffic and to relieve congestion in integrated networks, a dynamic rate control mechanism is proposed. This mechanism, using a variable rate coder, adjusts the source coding rate based on network feedback information. An analytical model is developed to evaluate the performance of the mechanism for voice traffic. The feedback delay for the source node to obtain the network congestion information is presented in the model. Significant improvement in statistical gain can be realized for smaller capacity links (e.g., links that can accommodate less than 24 calls) with a reasonable feedback time (about 100 ms); but this increase causes a temporary degradation in voice quality to a lower rate. The authors show that whether the feedback delay is exponentially distributed or constant does not significantly affect performance in terms of fractional packet loss and average received coding rate. Using the number of calls in talkspurt or the packet queue length as measures of congestion provides comparable performance.>

To achieve better statistical gain for voice and video traffic and to relieve congestion in fast packet networks, a dynamic rate control mechanism is proposed. An analytical model is developed to evaluate the performance of this control mechanism for voice traffic. The feedback delay for the source node to obtain the network congestion information is represented in the model. The study indicates that significant improvement in statistical gain can be realized for smaller capacity links (e.g., links that can accommodate less than 24 voice calls) with a reasonable feedback time (about 100 ms). The tradeoff for increasing the statistical gain is temporary degradation of voice quality to a lower rate. It is shown that whether the feedback delay is exponentially distributed or constant does not significantly affect performance in terms of fractional packet loss and average received coding rate. It is also shown that using the number of calls in talkspurt or the packet queue length as measures of congestion provides comparable performance.>

An analytical method is derived to estimate the protocol data unit (PDU) frame loss probability as a function of buffer size when identical sources are multiplexed on a fast packet link. The generation of PDUs from each source is governed by an on-off source model, and upper and lower bounds on the frame loss probability are derived. The analysis takes into account the correlated nature of fast packet losses within a PDU due to buffer overflows. The required buffer size for a given frame loss probability is directly proportional to the expected PDU frame length, and the loss probability decreases exponentially with increasing buffer size.>

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 knockout switch is a packet-switch architecture recently proposed for high-performance packet networks. In addition to providing point-to-point connections among user pairs, a packet network must often support multicast and broadcast capabilities. Multicast connections differ from point-to-point connections in that each packet is addressed to a number of destinations. Two specific approaches using the knockout switch to provide a practical and efficient means for multicast services under both light and heavy traffic conditions are proposed. The first involves packet duplication and is more suitable for light traffic loads. The second uses a fast address comparison technique and is capable of handling larger loads. In both cases, the knockout principle is utilized to yield the best delay-throughput performance, guarantee the first-in first-out packet sequence, and provide for a simple, modular implementation.>

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.>

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.>

The Knockout Switch is a new packet switch architecture recently proposed for high-speed local and metropolitan area networks, multiprocessor interconnects, and local or toll switches for integrated traffic loads. We describe an approach to extend the original Knockout Switch to work with variable-length packets. This new architecture employs an input broadcast bus arrangement to achieve complete interconnection of the inputs and outputs. Consequently, there is no congestion in the switch fabric other than the unavoidable conflict of multiple simultaneous packets destined for the same output. It is with this output contention that the Knockout principle is fully utilized to efficiently concentrate and store contending packets while maintaining the first-in first-out discipline of the packet sequence; and yet the fabric speed required is no more than the input/output line speeds, Under these design goals, no switch can yield better delay/ throughout performance. These are the most important attributes that have been preserved in the current proposal from the original Knockout Switch. For anN \times Nswitch configuration, the variable-length packet Knockout Switch consists ofNinput broadcast buses, and anN:Lconcentrator (L \ll N) and a shared buffer for each output. The design of each subsystem is discussed with emphasis on possible VLSI realization. Using today's technology, we should be able to implement the proposed switch with both input/output lines and internal hardware operating at 50 Mbits/s. The dimension of the switch (N \times N) can grow modularly from say 32 × 32 to 1024 × 1024, rendering a total throughput in the range of tens of gigabits per second. Future upgrading of the line interfaces to much higher speed without modification to the internal switch hardware is also possible with a modest restriction on the minimum length of new packets.

A new, high-performance packet-switching architecture, called the Knockout Switch, is proposed. The Knockout Switch uses a fully interconnected switch fabric topology (i.e., each input has a direct path to every output) so that no switch blocking occurs where packets destined for one output interfere with (i.e., block or delay) packets going to different Outputs. It is only at each output of the switch that one encounters the unavoidable congestion caused by multiple packets simultaneously arriving on different inputs all destined for the same output. Taking advantage of the inevitability of lost packets in a packet-switching network, the Knockout Switch uses a novel concentrator design at each output to reduce the number of separate buffers needed to receive simultaneously arriving packets. Following the concentrator, a shared buffer architecture provides complete sharing of all buffer memory at each output and ensures that all packets are placed on the output line on a first-in first-out basis. The Knockout Switch architecture has low latency, and is self-routing and nonblocking. Moreover, its Simple interconnection topology allows for easy modular growth along with minimal disruption and easy repair for any fault. Possible applications include interconnects for multiprocessing systems, high-speed local and metropolitan area networks, and local or toll switches for integrated traffic loads.

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.

In a time-multiplex switching system, the incoming traffic must be scheduled to avoid conflict at the switch output (two or more users converging simultaneously upon a single output). Two scheduling algorithms, random scheduling and optimal scheduling, are explored in this paper. Random scheduling is computationally simple, whereas optimal scheduling is currently very difficult. We have found, using a traffic model appropriate for circuit switched traffic that increases of typically 10 to 15 percent in offered load can be obtained through optimal scheduling (as compared to the much simpler random scheduling algorithm). The improvement is a function of the number of time slots (or circuits) per time-multiplexed frame, and falls to zero for both very small and very large frame sizes. Thus, in many circuit switching applications, providing a computationally expensive optimal schedule may not be warranted. This conclusion has important ramifications for both electronic and emerging photonic switching systems since it reduces the importance of the costly design feature of optimal scheduling.