The burstiness of a video source can be characterized by its burstiness curve. The burstiness curve is useful in the optimal allocation of resources to satisfy a desired quality of service for the video stream in a packet network. In this paper, we present deterministic algorithms for exact computation of the burstiness curve of a video source, for both elementary video streams and MPEG-2 Transport Streams. The algorithms exploit the piecewise linearity of the burstiness curve and compute only the points at which the slope of the burstiness curve changes. We also present approximate versions of these algorithms, which save computational effort by considering only a small number of candidate points at which the slope of the burstiness curve may change. The approximate algorithm was able to compute the burstiness curve of a 2-h long elementary video stream in approximately 10 s, as compared to over 6 h for the exact algorithm, with virtually no loss of accuracy in the computation. The efficiency of the proposed algorithms makes them suitable for quality-of-service (QoS) provisioning not only in off-line environments such as in video-on-demand (VoD) servers, but also in real-time applications such as in live TV distribution systems.

The loss curve of a video source characterizes the loss rate of the video stream generated by the source as a function of the allocated buffer size for a given transmission rate. The loss curve is useful in the optimal allocation of resources when the video stream is transmitted over a packet network, so that the desired tradeoff can be reached among the loss rate, bandwidth and the buffer space to be allocated in the network. We present an algorithm for computation of the entire loss curve of an elementary video stream. In contrast to earlier algorithms which employ statistical approaches, our algorithm is deterministic and computes the exact loss curve of the video stream. The algorithm exploits the piecewise linearity of the loss curve and computes only the points at which the slope of the loss curve changes. We also present an extension of the algorithm to MPEG-2 transport streams. The efficiency of the algorithm is demonstrated by results from several example video streams. For example, the algorithm was able to compute the entire loss curve of a 2-h elementary video stream in approximately 11 s on a Sun Ultra-2 workstation.

In this paper, we describe an enhancement to OSPF, called the IBB (I'll Be Back) capability, that enables other routers to use a router whose OSPF process is inactive for forwarding traffic for a certain period of time. The IBB capability can be used for avoiding route flaps that occur when the OSPF process is brought down in a router to facilitate protocol software upgrade, operating system upgrade, router ID change, AS and interface renumbering, etc. When the OSPF process in an IBB-capable router is inactive, it cannot adapt its forwarding table to reflect changes in network topology. This can lead to routing loops and/or black holes. We provide a detailed analysis of how and when loops or black holes are formed and propose solutions to prevent them. Using the GateD platform, we have developed an IBB extension to OSPF incorporating these solutions. Using this system in an experimental setup, we demonstrate that the overhead of the IBB extension is modest compared to the benefit it offers, and has good scaling behavior in terms of network size and the number of routers with inactive OSPF processes.

We study the performance of TCP in an internetwork consisting of both rate-controlled and nonrate-controlled segments. A common example of such an environment occurs when the end systems are part of IP datagram networks interconnected by a rate-controlled segment, such as an ATM network using the available bit rate (ABR) service. In the absence of congestive losses in either segment, TCP keeps increasing its window to its maximum size. Mismatch between the TCP window and the bandwidth-delay product of the network results in accumulation of large queues and possibly buffer overflows in the devices at the edges of the rate-controlled segment, causing degraded throughput and unfairness. We develop an explicit feedback scheme, called explicit window adaptation, based on modifying the receiver's advertised window in TCP acknowledgments returning to the source. The window size indicated to TCP is a function of the free buffer in the edge device. Results from simulations with a wide range of traffic scenarios show that this explicit window adaptation scheme can control the buffer occupancy efficiently at the edge device, and results in significant improvements in packet loss rate, fairness, and throughput over a packet discard policy such as random early detection (RED).

We discuss a hardware implementation of an explicit rate allocation algorithm for support of available bit rate (ABR) service in ATM switches. We then demonstrate the effectiveness of the algorithm at the network-level through measurements on the actual implementation in a network testbed. The rate allocation algorithm has several desirable properties, such as exact computation of the max-min rates, O(1) computations per resource management (RM) cell received, and the ability to provide minimum cell rate (MCR) guarantees. We show that the algorithm can be implemented with a modest amount of hardware (64,000 gates in an Altera 10K100 programmable logic device and 16 bytes of SRAM storage per VC), and that even a slow FPGA-based implementation with a 20 MHz internal clock rate can process RM cells within one cell time at an OC-3 port. We also outline the design for supporting OC-12 and OC-48 links. We present results from measurements of ABR traffic in network configurations with up to four bottlenecks and 100 connections. The results show that the algorithm is able to converge to the exact max-min fair allocations with no oscillations after convergence, maintains minimum rate guarantees, and is also able to maintain high link utilization in the presence of on-off traffic.

Loss of the routing protocol messages due to network congestion can cause peering session failures in routers, leading to route flaps and routing instabilities. We study the effects of traffic overload on routing protocols by quantifying the stability and robustness properties of two common Internet routing protocols, OSPF and BGP, when the routing control traffic is not isolated from data traffic. We develop analytical models to quantify the effect of congestion on the robustness of OSPF and BGP as a function of the traffic overload factor, queueing delays, and packet sizes. We perform extensive measurements in an experimental network of routers to validate the analytical results. Subsequently we use the analytical framework to investigate the effect of factors that are difficult to incorporate into an experimental setup, such as a wide range of link propagation delays and packet dropping policies. Our results show that increased queueing and propagation delays adversely affect BGP's resilience to congestion, in spite of its use of a reliable transport protocol. Our findings demonstrate the importance of selective treatment of routing protocol messages from other traffic, by using scheduling and utilizing buffer management policies in the routers, to achieve stable and robust network operation.

This paper addresses the clock recovery problem while transporting MPEG-2 systems layer streams over packet-switched networks. The packet delay variation (jitter) introduced by the network affects the stability and thus the quality of the recovered clock. A decoder design methodology is described in which a jitter estimator that performs restamping on all the incoming packets containing clock values is used in conjunction with a standard phase-locked loop (PLL). A simple implementation of this methodology is described, where a new heuristic has been added to the standard PLL to eliminate the effects of the jitter. The methodology is evaluated by both analysis and extensive simulation experiments in a multi-hop ATM network using constant bit-rate MPEG-2 transport streams produced by hardware encoders with varying levels of cross traffic. The results show that the restamping approach outperforms standard dejittering methods, especially under heavy load conditions.

We propose and analyze several strategies for performing timestamping of an MPEG-2 Transport Stream transmitted over a packet-switched network using the PCR-unaware encapsulation scheme, and analyze their effect on the quality of the recovered clock at the MPEG-2 Systems decoder. When the timestamping scheme is based on a timer with a fixed period, the PCR values in the packet stream may switch polarity deterministically, at a frequency determined by the timer period and the transport rate of the MPEG signal. This, in turn, can degrade the duality of the recovered clock at the receiver beyond acceptable limits. We consider three timestamping schemes for solving this problem: (1) selecting a deterministic timer period to avoid the phase difference in PCR values altogether, (2) fine-tuning the deterministic timer period to maximize the frequency of PCR polarity changes, and (3) selecting the timer period randomly to eliminate the deterministic PCR polarity changes. For the case of deterministic timer period, we derive the frequency of the PCR polarity changes as a function of the timer period and the transport rate, and use it to find ranges of the timer period for acceptable quality of the recovered clock. We also analyze a random timestamping procedure based on a random telegraph process and obtain lower bounds on the rate of PCR polarity changes such that the recovered clock does not violate the PAL/NTSC clock specifications. The analytical results are verified by simulations with both synthetic and actual MPEG-2 Transport Streams sent to a simulation model of an MPEG-2 Systems decoder.

We study the performance of the TCP in an internetwork consisting of both rate-controlled and non-rate-controlled segments. A common example of such an environment occurs when the end systems are part of IP datagram networks interconnected by a rate-controlled segment, such as an ATM network using the ABR service. In the absence of congestive losses in either segment, the TCP keeps increasing its window to its maximum size. Mismatch between the TCP window and the bandwidth-delay product of the network will result in an accumulation of large queues and possibly buffer overflows in the devices at the edges of the rate-controlled segment, causing degraded throughput and unfairness. We develop an explicit feedback scheme, called explicit window adaptation based on modifying the receiver's advertised window in the TCP acknowledgments returning to the source. The window size indicated to the TCP is a function of the free buffer in the edge device. Results from simulations with a wide range of traffic scenarios show that this explicit window adaptation scheme can control the buffer occupancy efficiently at the edge device, and results in significant improvements in packet loss rate, fairness, and throughput over a packet discard policy such as drop-from-front or random early detection.

The sharing of a common buffer by TCP data segments and acknowledgments in a network or internet has been known to produce the effect of ack compression, often causing dramatic reductions in throughput. We study several schemes for improving the performance of two-way TCP traffic over asymmetric links where the bandwidths in the two directions may differ substantially, possibly by many orders of magnitude. These approaches reduce the effect of ack compression by carefully controlling the flow of data packets and acknowledgments. We first examine a scheme where acknowledgments are transmitted at a higher priority than data. By analysis and simulation, we show that prioritizing acks can lead to starvation of the low-bandwidth connection. Next, we introduce and analyze a connection-level backpressure mechanism designed to limit the maximum amount of data buffered in the outgoing IP queue of the source of the low-bandwidth connection. We show that this approach, while minimizing the queueing delay for acks, results in unfair bandwidth allocation on the slow link. Finally, our preferred solution separates the acks from data packets in the outgoing queue, and makes use of a connection-level bandwidth allocation mechanism to control their bandwidth shares. We show that this scheme overcomes the limitations of the previous approaches, provides isolation, and enables precise control of the connection throughputs. We present analytical models of the dynamic behavior of each of these approaches, derive closed-form expressions for the expected connection efficiencies in each case, and validate them with simulation results.

In a disk array with a nonvolatile write cache, destages from the cache to the disk are performed in the background asynchronously while read requests from the host system are serviced in the foreground. We study a number of algorithms for scheduling destages in a RAID-5 system. We introduce a scheduling algorithm, called linear threshold scheduling, that adaptively varies the rate of destages to disks based on the instantaneous occupancy of the write cache. The performance of the algorithm is compared with that of a number of alternative scheduling approaches, such as least cost scheduling and high/low mark. The algorithms are evaluated in terms of their effectiveness in making destages transparent to the servicing of read requests from the host, disk utilization, and their ability to tolerate bursts in the workload without causing an overflow of the write cache. Our results show that linear threshold scheduling provides the best read performance of all the algorithms compared, while still maintaining a high degree of burst tolerance. An approximate implementation of the linear threshold scheduling algorithm is also described. The approximate algorithm can be implemented with much lower overhead, yet its performance is virtually identical to that of the ideal algorithm.

This paper provides an analysis of the source policy in the rate-based congestion control scheme developed by the Asynchronous Transfer Mode (ATM) Forum for available bit rate service and derives approximate analytical closed-form expressions to describe the rate increase process. These approximations are used to analyze the impact of the source algorithm on the TCP slow-start process operating over a rate-controlled ATM network. The results show that the increase in TCP congestion window ramp-up time is noticeable when the round-trip delay is small. The results are verified by simulation.

We study the performance of bidirectional TCP/IP connections over a network that uses rate-based flow and congestion control. An example of such a network is an asynchronous transfer mode (ATM) network using the available bit rate (ABR) service. The sharing of a common buffer by TCP packets and acknowledgment (acks) has been known to result in an effect called ack compression, where acks of a connection arrive at the source bunched together, resulting in unfairness and degraded throughput. It has been the expectation that maintaining a smooth flow of data using rate-based flow control would mitigate, if not eliminate, the various forms of burstiness experienced with the TCP window flow control. However, we show that the problem of TCP ack compression appears even while operating over a rate-controlled channel. The degradation in throughput due to bidirectional traffic can be significant. For example, even in the simple case of symmetrical connections with adequate window sizes, the throughput of each connection is only 66.67% of that under one-way traffic. By analyzing the periodic bursty behavior of the source IP queue, we derive estimates for the maximum queue size and arrive at a simple predictor for the degraded throughput, for relatively general situations. We validate our analysis using simulation on an ATM network using the explicit rate option of the ABR service. The analysis predicts the behavior of the queue and the throughput degradation in simple configurations and in more general situations.

Generalized processor sharing (GPS) has been considered as an ideal scheduling discipline based on its end-to-end delay bounds and fairness properties. Until recently, emulation of GPS in a packet server has been regarded as the ideal means of designing a packet-level scheduling algorithm to obtain low delay bounds and bounded unfairness. Strict emulation of GPS, as required in the weighted fair queueing (WFQ) scheduler, however, incurs a time-complexity of O(N) where N is the number of sessions sharing the link. Efforts in the past to simplify the implementation of WFQ, such as self-clocked fair queueing (SCFQ), have resulted in degrading its isolation properties, thus affecting the delay bound. We present a methodology for the design of scheduling algorithms that provide the same end-to-end delay bound as that of WFQ and bounded unfairness without the complexity of GPS emulation. The resulting class of algorithms, called rate-proportional servers (RPSs), are based on isolating scheduler properties that give rise to ideal delay and fairness behavior. Network designers can use this methodology to construct efficient fair-queueing algorithms, balancing their fairness with implementation complexity.

Although weighted fair queueing (WFQ) has been regarded as an ideal scheduling algorithm in terms of its combined delay bound and proportional fairness properties, its asymptotic time complexity increases linearly with the number of sessions serviced by the scheduler, thus limiting its use in high-speed networks. An algorithm that combines the delay and fairness bounds of WFQ with O(1) timestamp computations had remained elusive so far. In this paper we present two novel scheduling algorithms that have O(1) complexity for timestamp computations and provide the same bounds on end-to-end delay and buffer requirements as those of WFQ. The first algorithm, frame-based fair queueing (FFQ), uses a framing mechanism to periodically recalibrate a global variable tracking the progress of work in the system, limiting any short-term unfairness to within a frame period. The second algorithm, starting potential based fair queueing (SPFQ), performs the recalibration at packet boundaries, resulting in improved fairness while still maintaining the O(1) timestamp computations. Both algorithms are based on the general framework of rate-proportional servers (RPSs) introduced by Stiliadis and Varma (see ibid., vol.6, no.2, p.164-74, 1998). The algorithms may be used in both general packet networks with variable packet sizes and in asynchronous transfer mode (ATM) networks.

We develop a general model, called latency-rate servers (/spl Lscr//spl Rscr/ servers), for the analysis of traffic scheduling algorithms in broadband packet networks. The behavior of an /spl Lscr//spl Rscr/ server is determined by two parameters-the latency and the allocated rate. Several well-known scheduling algorithms, such as weighted fair queueing, virtualclock, self-clocked fair queueing, weighted round robin, and deficit round robin, belong to the class of /spl Lscr//spl Rscr/ servers. We derive tight upper bounds on the end-to-end delay, internal burstiness, and buffer requirements of individual sessions in an arbitrary network of /spl Lscr//spl Rscr/ servers in terms of the latencies of the individual schedulers in the network, when the session traffic is shaped by a token bucket. The theory of /spl Lscr//spl Rscr/ servers enables computation of tight upper bounds on end-to-end delay and buffer requirements in a heterogeneous network, where individual servers may support different scheduling architectures and under different traffic models.

We examine the performance of bidirectional TCP/IP connections over asynchronous transfer mode (ATM) networks using the available bit rate (ABR) service. The problem of "ack-compression" re-appears, although the queues are primarily at the end-systems. We further the understanding of the problem by quantitatively analyzing the periodic bursty behavior of the source IP queue. We are able to predict the peak values for the queue and arrive at a simple robust predictor for the degraded throughput, applicable for relatively general situations. The degradation in throughput due to bidirectional traffic can be significant. For example, even in the simple case of symmetrical connections with adequate window sizes, the throughput of each connection is only 66.67% of that under one-way traffic. We validate our analysis using simulation, where the ATM network uses the explicit rate option. We show that the analysis predicts the behavior of the queue and the throughput degradation. We observe the need to separate the flow of acknowledgments and data for the bidirectional TCP connection and for inter-leaving their processing at the end-systems to overcome the problem of ack compression.

We introduce a general methodology for designing integrated 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 by Stiliadis and Varma (see Proceedings of ACM SIGMETRICS '96, p.104-15, 1996). 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 re-shaping. We describe an efficient implementation of this integrated shaping and scheduling algorithm with log/sub 2/(V) complexity, where V is the number of sessions sharing the outgoing link.

Many future applications of computer networks such as distance education, remote collaboration, and teleconferencing will rely on the ability of the network to provide multicast services. We propose and evaluate ARIES, a heuristic for updating multicast trees dynamically in large point-to-point networks. The algorithm is based on monitoring the accumulated damage to the multicast tree within local regions or the tree as nodes are added and deleted and triggering a rearrangement when the number of changes within a connected subtree crosses a set threshold. We derive an analytical upper bound on the competitiveness of the algorithm. We also present simulation results to compare the average-case performance of the algorithm with two other known algorithms for the dynamic multicast problem, GREEDY, and edge-bounded algorithm (EBA). Our results show that ARIES provides the best balance among competitiveness, computational effort, and changes in the multicast tree after each update.

Although direct-mapped caches suffer from higher miss ratios as compared to set-associative caches, they are attractive for today's high-speed pipelined processors that require very low access times. Victim caching was proposed by Jouppi (1990) as an approach to improve the miss rate of direct-mapped caches without affecting their access time. This approach augments the direct-mapped main cache with a small fully associate cache, called victim cache, that stores cache blocks evicted from the main cache as a result of replacements. We propose and evaluate an improvement of this scheme, called selective victim caching. In this scheme, incoming blocks into the first-level cache are placed selectively in the main cache or a small victim cache by the use of a prediction scheme based on their past history of use. In addition, interchanges of blocks between the main cache and the victim cache are also performed selectively. We show that the scheme results in significant improvements in miss rate as well as the average memory access time, for both small and large caches (4 Kbytes-128 Kbytes). For example, simulations with ten instruction traces from the SPEC '92 benchmark suite showed an average improvement of approximately 21 percent in miss rate over simple victim caching for a 16-Kbyte cache with a block size of 32 bytes; the number of blocks interchanged between the main and victim caches reduced by approximately 70 percent. Implementation alternatives for the scheme in an on-chip processor cache are also described.

In this paper, we propose and evaluate ARIES, a heuristic for updating multicast trees dynamically in large point-to-point networks. The algorithm is based on monitoring the accumulated damage to the multicast tree within local regions of the tree as nodes are added and deleted, and triggering a rearrangement when the number of changes within a connected subtree crosses a set threshold. We derive an analytical upper-bound on the competitiveness of the algorithm. We also present simulation results to compare the average-case performance of the algorithm with two other known algorithms for the dynamic multicast problem, GREEDY and EBA (edge-bounded algorithm). Our results show that ARIES provides the best balance among competitiveness, computational effort, and changes in the multicast tree after each update.

In this paper, we develop a general model, called latency-rate servers (LR-servers), for the analysis of traffic scheduling algorithms in broadband packet networks. The behavior of an LR scheduler is determined by two parameters-the latency and the allocated rate. We show that several well-known scheduling algorithms, such as weighted fair queueing, virtualclock, self-clocked fair queueing, weighted round robin, and deficit round robin, belong to the class of LR-servers. We derive tight upper bounds on the end-to-end delay, internal burstiness, and buffer requirements of individual sessions in an arbitrary network of LR-servers in terms of the latencies of the individual schedulers in the network, when the session traffic is shaped by a leaky bucket. Thus, the theory of LR-servers enables computation of tight upper-bounds on end-to-end delay and buffer requirements in a network of servers in which the servers on a path may not all use the same scheduling algorithm. We also define a self-contained approach to evaluate the fairness of LR-servers and use it to compare the fairness of many well-known scheduling algorithms.

In this paper we introduce and analyze frame-based fair queueing, a novel traffic scheduling algorithm for packet-switched networks. The algorithm provides end-to-end delay bounds identical to those of PGPS (packet-level generalized processor sharing), without the complexity of simulating the fluid-model system in the background as required in PGPS. The algorithm is therefore ideally suited for implementation in packet switches supporting a large number of sessions. We present a simple implementation of the algorithm for a general packet switch. In addition, we prove that the algorithm is fair in the sense that sessions are not penalized for excess bandwidth they received while other sessions were idle. Frame-based fair queueing belongs to a general class of scheduling algorithms, which we call Rate-Proportional Servers. This class of algorithms provides the same end-to-end delay and burstiness bounds as PGPS, but allows more flexibility in the design and implementation of the algorithm. We provide a systematic analysis of this class of schedulers and obtain bounds on their fairness.

Establishing a multicast tree in a point-to-point network of switch nodes, such as a wide-area asynchronous transfer mode (ATM) network, can be modeled as the NP-complete Steiner problem in networks. In this paper, we introduce and evaluate two distributed algorithms for finding multicast trees in point-to-point data networks. These algorithms are based on the centralized Steiner heuristics, the shortest path heuristic (SPH) and the Kruskal-based shortest path heuristic (K-SPH), and have the advantage that only the multicast members and nodes in the neighborhood of the multicast tree need to participate in the execution of the algorithm. We compare our algorithms by simulation against a baseline algorithm, the pruned minimum spanning-tree heuristic that is the basis of many previously published algorithms for finding multicast trees. Our results show that the competitiveness (the ratio of the sum of the heuristic tree's edge weights to that of the best solution found) of both of our algorithms was, on the average, 25% better in comparison to that of the pruned spanning-tree approach. In addition, the competitiveness of our algorithms was, in almost all cases, within 10% of the best solution found by any of the Steiner heuristics considered, including both centralized and distributed algorithms. Limiting the execution of the algorithm to a subset of the nodes in the network results in an increase in convergence time over the pruned spanning-tree approach, but this overhead can be reduced by careful implementation.

Establishing a multicast tree in a point-to-point network of switch nodes, such as a wide-area ATM network, is often modeled as the NP-complete Steiner problem in networks. In this paper, we study algorithms for finding efficient multicast trees in the presence of constraints on the copying ability of the individual switch nodes in the network. We refer to this problem as the degree-constrained multicast tree problem and model it as the degree-constrained Steiner problem in networks. Steiner heuristics for the degree-constrained case are proposed and their simulation results for sparse, point-to-point networks are presented. The results are compared with respect to their quality of solution, cost (running time), and the number of test cases for which no solution could be found. The results of our research indicate that efficient multicast frees can be found in large, sparse networks with small multicast groups even with limited multicast capability in the individual switches. Some of the Steiner heuristics tested yielded degree-constrained multicast trees within 5% of the best heuristic solution found in most of the cases. Even when the fanout of each switch node was restricted to 2, the heuristics we used were able to generate efficient multicast trees in almost all our test networks. Surprisingly few test networks were unsolvable. In those cases where no solution was found by a heuristic, backtracking solved many of the remaining cases. Among the heuristics we used, degree-constrained versions of simple path-distance heuristics such as SPH and SPH-R provided the best tradeoffs between quality of solution and cost.

In a disk array with a nonvolatile write cache, destages from the cache to the disk are performed in the background asynchronously while read requests from the host system are serviced in the foreground. In this paper, we study a number of algorithms for scheduling destages in a RAID-5 system. We introduce a new scheduling algorithm, called linear threshold scheduling, that adaptively varies the rate of destages to disks based on the instantaneous occupancy of the write cache. The performance of the algorithm is compared with that of a number of alternative scheduling approaches such as least-cost scheduling and high/low mark. The algorithms are evaluated in terms of their effectiveness in making destages transparent to the servicing of read requests from the host, disk utilization, and their ability to tolerate bursts in the workload without causing an overflow of the write cache. Our results show that linear threshold scheduling provides the best read performance of all the algorithms compared, while still maintaining a high degree of burst tolerance. An approximate implementation of the linear-threshold scheduling algorithm is also described. The approximate algorithm can be implemented with much lower overhead, yet its performance is virtually identical to that of the ideal algorithm.

In this paper, we present efficient sequential and parallel algorithms for computation of time-slot assignments in SS/TDMA (satellite-switched/time-division multiple-access) systems with variable-bandwidth beams. These algorithms are based on modeling the time-slot assignment (TSA) problem as a network-flow problem. Our sequential algorithm, in general, has a better time-complexity than a previous algorithm due to Gopal, et al. (1982) and generates fewer switching matrices. If M (N) is the number of uplink (downlink) beams, L is the length of any optimal TSA, and /spl alpha/ is the maximum bandwidth of an uplink or downlink beam, our sequential algorithm takes O((M+N)/sup 3/min(MN/spl alpha/,L)) time to compute an optimal TSA when the traffic-handling capacity of the satellite is of the same order as the total bandwidth of the links. Our parallel algorithm uses L/2 processors and has a time-complexity of O((M+N)/sup 3/logL) on a PRAM model of parallel computation. We then generalize this algorithm to P/spl les/L/2 processors and describe an efficient implementation of the algorithm on a hypercube multiprocessor with P processors. A massively-parallel version of the algorithm runs in O((M+N)/sup 2/log(M+N)logL) time on (M+N)L/2 processors.>

In a large nonblocking crossbar switch, the controller often becomes a bottleneck in terms of both performance and reliability. We present a number of schemes for distributing the setup function among multiple controllers, thus improving both the performance and the reliability of the switch. The controllers are symmetric and operate in parallel. We present four distributed control schemes that provide a range of tradeoffs in controller complexity, speed, and hardware overhead for nonblocking operation. We derive a lower bound of N(1/spl minus/1/K) for the number of buses required for nonblocking operation of a crossbar switch with N ports and K controllers under certain constraints. We then describe a scheme that actually achieves this lower bound. Results from simulation indicate that the hardware overhead in terms of the extra buses needed is small for all the schemes if a small probability of blocking is acceptable.>

The authors present a performance study of a switching system being designed for use in the high-performance switching system (HPSS) project at the Lawrence Livermore National Laboratory. The HPSS is a distributed switching system designed to operate with the protocols of the proposed ANSI fibre channel standard (FCS). The system is based on a folded version of the Clos three-stage network and its largest configuration has 4096 ports, each operating at 1.0625 Gbit/s. A detailed simulation model is used to evaluate the throughput, setup time, and blocking at various stages in an HPSS configuration with 512 ports. The results indicate that the system can sustain a throughput that is within 70 to 80 percent of the maximum theoretical limit for the authors choice of operational parameters.>

A method is presented to improve the performance of the High-Performance Switching System (HPSS), a distributed switching system being designed for use in the campus-wide high-speed network prototype at the Lawrence Livermore National Laboratory. The HPSS uses protocols of the proposed ANSI Fibre Channel Standard (FCS). The system is based on a folded version of the Clos three-stage network, and its largest configuration has 4096 ports, each operating at 1.0625 Gb/s. The authors' approach improves the connection-setup time in the HPSS by queuing connection requests at destination ports, thus reducing the overhead associated with retries due to port-busy conditions. Results from a detailed simulation of the HPSS are presented to show the performance improvement for different traffic distributions and operating parameters.

Abstract In this paper, we study routing problems in a general class of asymmetrical three‐stage Clos networks. This class covers many asymmetrical three‐stage networks considered by earlier researchers. We derive necessary and sufficient conditions under which this class of networks is rearrangeable with respect to a set ofmulticonnections, i.e., connections between subsets of input and output terminals. We first model the routing problem in these networks as a network‐flow problem. If the number of switching elements in the first and last stages of the network isO(f)and the number of switching elements in the middle stage ism, then the network‐flow model yields a routing algorithm with running timeO(mf3). We then show that the problem of routing a set of multiconnections in an asymmetrical Clos network can be transformed into the well‐studied problem of routing a set of pairwise connections in a more symmetric form of the network. This approach results in a routing algorithm with complexityO(mK2), whereKis the aggregate capacity of the interstage links in the network. ©1993 by John Wiley & Sons, Inc.

It is shown that any hierarchical switching system can be modeled by a special class of flow networks called unit networks. Using the results available for finding maximum flow through a unit network, a time-slot assignment (TSA) algorithm that runs in O(min(L,M/sup 2/)*min(N, square root M)*M/sup 2/) time is presented. This is an O(max(M/N, square root M)) improvement over the TSA algorithm proposed by M.A. Bonucelli (1989).>

Presents parallel algorithms for computation of time-slot assignments in time-division multiplex (TDM) switching systems. The algorithms apply to a general class of TDM switching systems called hierarchical switching systems (HSS), which have a three-stage switching structure. The algorithms are based on modeling the time-slot assignment problem as a network-flow problem. Previous algorithms for finding an optimal time-slot assignment in these switching systems are inherently sequential and no parallel algorithms are known for this problem. If M is the number of users of the switching system, N is the switch-size, and L is the length of an optimal time-slot assignment, the best-known sequential TSA algorithm runs in O(M/sup 2/.min(N, square root M).min(L, M/sup 2/)) time. The authors first describe an algorithm using L/2 processors with running time O(M/sup 3/ log L) on a PRAM model of computation. They then generalize it to P>

We introduce and evaluate a class of prefetch schemes for on-chip data caches in high-performance RISC processors. These schemes are conservative, initiating a prefetch only when a sequential pattern of references have been observed. Performance results based on traces of five programs in the SPEC suite on an IBM RS/6000 show that these schemes result in a significant reduction in miss ratio without the large increase in memory traffic associated with earlier schemes.

The authors present an incremental algorithm for scheduling traffic in a general class of time-division multiplexed (TDM) switching systems used in satellite and terrestrial communication networks. Instead of recomputing the time slot assignment (TSA) for each frame of traffic, this algorithm computes a TSA for a new frame by modifying the known TSA of the previous frame. The algorithm takes O(M/sup 2/+cM) time for finding an optimal TSA in a hierarchical switching system, where M is the number of users and c is the number of changes between the traffic demands of two consecutive frames. The algorithm uses a two-step process. The first step transforms the TSA problem in the hierarchical switching system (HSS) into an equivalent TSA problem in a simple TDM switching system. The second step uses an incremental algorithm to find a TSA for the latter. The second step exploits the correspondence between the TSA problem and the rearrangement problem in a Clos three-stage network. When the traffic demands in consecutive frames overlap to a significant extent, the incremental algorithm provides considerable speedup over previous algorithms.>

The fault-tolerance capability of one-sided crosspoint networks is analyzed with respect to crosspoint faults. Because of the correspondence between one-sided crosspoint networks and multiple-bus interconnection networks, the analysis also applies to multiple-bus configurations, where M buses are used to interconnect N processors. Upper bounds are established on the size of a fault set to sustain a given level of connectivity. Two modes of operation are considered, namely, nonblocking and rearrangeable. A complete nonblocking switch matrix with N ports has N/sup 2//2 crosspoints. It is shown that at most N/2-1 faulty crosspoints can be tolerated in the case of nonblocking operation.>

The effect of nonuniform traffic patterns is studied based on simulation and analysis when two multistage networks are used in parallel to interconnect processors and memory modules in a shared-memory system. The networks considered are identical copies of buffered multi stage networks. The authors consider the following two strategies to distribute the total traffic between the two networks: distribute the traffic randomly among the networks, and route the nonuniform component of the traffic to one network and the uniform component to the other. To facilitate the implementation of these strategies in a system, a technique to detect nonuniformities in the network traffic at run-time and change the routing strategy dynamically is discussed. The authors compare this technique to an ideal scheme by means of analysis and simulation. The results show that the run-time detection scheme performs very close to the ideal case. The effectiveness of dual networks in tolerating short bursts of nonuniform traffic is also demonstrated.>

The authors present efficient sequential and parallel algorithms for computation of time-slot assignments in SS/TDMA (satellite-switched/time-division multiple-access) systems with variable-bandwidth beams. These algorithms are based on modeling the time-slot assignment (TSA) problem as a network-flow problem. If M(N) is the number of uplink (downlink) beams, L is the length of any optimal TSA, and alpha is the maximum bandwidth of an uplink or downlink beam, the sequential algorithm takes O((M+N)/sup 3/ min (M N alpha , L)) time to compute an optimal TSA, when the traffic-handling capacity of the satellite is of the same order as the total bandwidth of the links. The parallel algorithm uses L/2 processors and has a time-complexity of O((M+N)/sup 3/ log L) on a probabilistic random access machine (PRAM) model of parallel computation. The authors then generalize this algorithm to P>

A major problem in the design of VLSI crossbar networks is the simultaneous-switching noise (also known as Delta-I noise), caused by the simultaneous activation of a large number of line-drivers at the output leads of the VLSI package. In a nonblocking configuration, one can reduce the maximum number of active line-drivers in a chip by using extra columns of chips. Tight upper and lower bounds are derived for the number of additional columns required for a one-sided nonblocking crossbar network when a Delta-I constraint is imposed. By using algorithms that allocate paths intelligently, a substantial reduction in the Delta-I constraint is imposed. A substantial reduction in the Delta-I noise can be achieved with a modest hardware overhead, if a small blocking probability is acceptable. The first-fit and the best-fit case bus-allocation policies are introduced.>

The authors study methods for routing data in supercomputers that use multistage interconnection networks (MINs) in the presence of faulty components in the network. These methods are applicable to existing multiprocessors such as the IBM GF11 and RP3. These methods are based on the concept of dynamic full-access (DFA) which refers to the ability of the network to route data from any processor in the system to any other processor in a finite number of passes through the network. The authors introduce a graph-model called the DFA graph of a MIN and show how it can be used to determine the DFA capability of the MIN under a given set of network faults. When the faults in the network satisfy certain special properties, algorithms for routing any arbitrary permutation in a faulty Benes network and any Omega permutation in a faulty Omega network are presented.>

A major impediment to building large crosspoint chips for configuring crosspoint switching networks is the simultaneous switching (Delta-I) noise problem that is caused by the switching of a large number of line drivers driving the output pins of the package. This limits the size of the largest crosspoint chips that can be operated reliably. An architectural solution to this problem is presented for networks constructed from one-sided crosspoint switching chips. The approach seeks to minimize the maximum number of active drivers in the individual chips by distributing the active drivers in the network uniformly among the chips by allowing rearrangements of existing connections when a new connection is made. A graph model is used to determine the number and location of rearrangements. An allocation scheme based on a simplified graph model that achieves a 50% reduction in the maximum number of active drivers per chip as compared to a random allocation strategy is presented. A maximum of three rearrangements is sufficient to obtain this reduction.>

The authors establish upper and lower bounds for the number of crosspoints required in a one-sided crosspoint switching network to provide a given level of connectivity. Two modes of operation are considered, namely, nonblocking and rearrangeable. A complete nonblocking switch matrix with N ports has N/sup 2//2 crosspoints. The authors show that this number can be reduced by at most N/2-1 crosspoints for nonblocking operation. If rearrangeable operation is allowed, however, as many as 25% of the crosspoints can be removed. An analysis is made of the relationship between the number of crosspoints removed and the maximum number of rearrangements of connections needed. Also introduced are algorithms for rearrangement of connections in both single-chip and partitioned implementations with reduced numbers of crosspoints.>

The fault tolerance of multiprocessor systems with multistage interconnection networks under multiple faults in the network is studied. The fault tolerance is analyzed with respect to the criterion of dynamic full access (DFA) property of the processors in the system. A characterization of multiple faults in the Omega network is introduced and used to develop simple tests for the DFA capability under a given set of faults. It is shown that the DFA capability is maintained under a large number of faults. A maximum of three passes is shown to be sufficient for communication between any two processors in the system when the faults satisfy certain conditions which can be checked easily. For cases in which these conditions do not hold, at most log/sub 2/N-2 passes through the network are shown to be sufficient if a set of weaker conditions is satisfied. Techniques for routing data between processing elements through the faulty network are described. Extension of the results to general k-stage shuffle/exchange networks with k>

Although a theoretical lower bound of (2 log/sub 2/N-1) stages for rearrangeability of a network with N=2/sup n/ inputs and outputs has been known, the sufficiency of (2 log/sub 2/N-1) stages has neither been proved nor disproved. The best known upper bound for rearrangeability is (3 log/sub 2/N-3) stages. It is proved that if (2 log/sub 2/R-1) shuffle/exchange stages are sufficient for rearrangeability of a network with R=2/sup r/ inputs and outputs, then for any N>R, (3 log/sub 2/N-(r+1)) stages are sufficient for a network with N inputs and outputs. This result is established by setting some of the middle stages of the network to realize a fixed permutation and showing the reduced network to be topologically equivalent to a member of the Benes class of rearrangeable networks. From the known result that five stages are sufficient for rearrangeability when N>or=8, an upper bound of (3 log/sub 2/N-4) is obtained. Any increase in the network size R for which the rearrangeability of (2 log/sub 2/R-1) stages can be shown results in corresponding improvements in the upper bound for all N>or=R. As a result of the one-to-one correspondence that exists between the switches in the reduced shuffle/exchange network and those in the Benes network, the former network can be controlled by the well-known looping algorithm.>

In this paper we study the rearrangeability of multistage shuffle/exchange networks. Although a theoretical lower bound of (2 log2N - 1) stages for rearrangeability of a network with N = 2n inputs and outputs has been known, the sufficiency of (2 log2N - 1) stages has neither been proved nor disproved. The best known upper bound for rearrangeability is (3 log2N - 3) stages. We prove that, if (2 log2R - 1) shuffle/exchange stages are sufficient for rearrangeability of a network with R = 2' inputs and outputs, then, for any N > R, 3 log2N - (r + 1) stages are sufficient for a network with N inputs and outputs. This result is established by setting some of the middle stages of the network to realize a fixed permutation and showing the reduced network to be topologically equivalent to a member of the Benes class of rearrangeable networks. We first characterize equivalence to Benes networks in set-theoretic terms and use this to prove equivalence of the reduced shuffle/exchange network to the Benes network. From the known result that 5 stages are sufficient for rearrangeability when N = 8, we obtain an upper bound of (3 log2N - 4) stages for rearrangeability when N ≥ 8. Further, any increase in the network size R for which the rearrangeability of (2 log2R - 1) stages could be shown, results in a corresponding improvement in the upper bound for all N ≥ R.

In this paper we prove the rearrangeubility of a multistage shuffle/exchange network with eight inputs and outputs consisting of five stages. A lower bound of (2 log_{2} N - 1) stages for rearrangeability of a Shuffle/exchange network withN = 2^{n}inputs and outputs is known; we show its sufficiency forN = 8. We not only prove the rearrangeability, but also describe an algorithm for routing arbitrary permutations on the network and prove its correctness. In contrast to previous efforts to prove rearrangeability, which rely on topological equivalence to the Benes class of rearrangeable networks, our approach is based on first principles. We also show that two switches in the network are redundant. The results in this paper are useful for establishing an upper bound of (3 log_{2} N - 4) stages for rearrangeability of a multistage shuffle/exchange network withN \geq 8, as demonstrated in [12].

In this paper, we study fault-tolerant multiprocessor systems employing redundant-path multistage interconnection networks. Such systems permit interprocessor communication in the presence of faulty components in the network. The interconnection network considered is a delta network augmented with an extra switching stage in front. When the first and last stages are fault-free, the extra-stage delta networks continue to provide full access in the presence of all single and many multiple faults in switching elements of the intermediate stages. In this paper, we use graph-theoretic techniques to study the problem of routing permutations in extra-stage delta networks when faults are present in the network. We first formulate the problem of performing an arbitrary permutation on the fault-free network as a vertex-coloring problem and later extend this to networks with noncritical faults. Although the general problem of realizing a permutation in the minimum number of passes is intractable, classes of permutations with some regularity can be routed optimally. To illustrate the idea, we consider the class of BPC (bit permute-complement) permutations: algorithms for performing arbitrary permutations in this class on the extra-stage delta network are given, both for the fault-free network and for a network with noncritical faults.