Due to the changed economic environment, the rush to implementing packet switches with switching capacities above 1 Tb/s, which had proceeded at a frantic pace for some years, has slowed down considerably. Most service providers do not foresee the deployment of switches and routers with gigantic capacities in the near future. The immediate interest does now rarely go beyond the subterabit range, with a sweet spot between 120-640 Gb/s, where the emphasis is on feature-rich systems that enable the convergence of legacy services with new emerging data services. Although the current focus is on smaller switches, it is still relevant to understand their evolution path to multiterabit capacities. The scalability issues are also critical to reduce complexity and simplify implementation, in order to push the limits of what can be achieved in the switches within current economic and market constraints. We analyze the current state of the art of practical large packet switches and routers, and discuss the issues affecting their scalability. Our approach is pragmatic, with most of our attention devoted to three major scalability aspects: implementation, support of quality of service, and multicasting. After a general discussion of these issues, we show their impact on the most popular switch architectures.

In small cell-based Internet protocol routers, multicast traffic is generally handled by appending to each cell a local multicast label (LML) containing a bitmap with as many bits as switch ports, so as to identify the ports to which a copy of the cell has to be transferred. This approach is not feasible for switches having 128 ports or more, because the LML length would rise above 16 bytes, thus representing an intolerable overhead, given the small size of cells (typically 64 bytes). We discuss both static and adaptive lossy compression algorithms to reduce the size of LMLs to be attached to multicast cells, at the price of the delivery of cells to a larger set of outputs than necessary, and we compare the compression algorithms performance in terms of switch bandwidth waste, using both analytical and simulation models.

We present the Distributed Frame-Definition Algorithm (DFDA), a novel scheduling policy for input-queued switches with virtual output queueing at the input line cards. The DFDA effectively supports the integration of traffic classes with diverse Quality-of-Service (QoS) requirements (as compelled by emerging QoS frameworks such as Differentiated Services), and scales well with the aggregate capacity of the switch because of the limited complexity of its distributed implementation. The input and output tine cards exchange a minimal amount of control information to define the periodic service schedule that regulates transit through the switch fabric. The composition of the service schedule dynamically adapts to the tight bandwidth requirements of real-time traffic and to the load fluctuations of best-effort traffic. We assess the performance of the DFDA through simulation, and compare it with the most popular scheduling algorithms for input-queued switches. Our experiments show that the DFDA generally sustains higher throughput than the schemes of the prior art.

We investigate techniques for the support of multicast traffic in IP routers that have a large number of switch fabric ports (from 128 to 1024) and internally operate on relatively small fixed-size data units (cells of 64 bytes each). In small packet switches, multicast traffic is typically handled by prepending a local multicast label (LML) to each cell. The LML consists of a bitmap with as many bits as switch ports. The bitmap identifies the set of ports to which copies of the cell must be transferred. The bitmap approach is no longer feasible in switches with 128 ports or more, where the LML length cannot be smaller than 16 bytes, an intolerable overhead when the internal cell payload is only 64 bytes. We devise several compression algorithms, both static and adaptive, to reduce the size of the LML's to be attached to multicast cells. The algorithms define compressed representations of the distribution sets of the multicast cells, trading the additional bandwidth needed to transfer redundant cell copies (i.e., copies directed to outputs that do not belong to the actual distribution sets) for the cell header overhead otherwise needed to deliver the cells only to the proper outputs. We use simulation experiments to compare the performance of the compression algorithms.

Although the current focus is on smaller switches, it is still relevant to understand their evolution path to multi-terabit capacities. In particular, it is interesting to see how their QoS and multicasting features can scale as their size increases, and at which point performance compromises may be necessary for the sake of size. In this talk, we review existing switch architectures and their commercial embodiments, and extrapolate their evolution to larger sizes. A pressing issue in going beyond the terabit barrier is the physical arrangement of the system, and specifically the interconnection of line cards residing in multiple chassis. In this respect, we look for the limits of pure electronic-based solutions, and discuss the relevance of hybrid electro-optical switching systems.

Current mobile networks provide link-layer mobility as a mobile host changes its point of attachment within the scope of an access node, and provide wide-area mobility through global mobility protocols such as mobile IP. Several proposals have been made for an intermediate level of mobility support, called micro-mobility which addresses the issues of handover latency, signaling overhead and packet loss that are inherent in wide-area mobility protocols. We propose a new multi-protocol label switching (MPLS) based network architecture that implements intra-domain micro-mobility using label switched path (LSP) re-direction in a traffic engineered network. We introduce an enhanced label edge router (LER), called the label edge mobility agent (LEMA) and describe the operations of the network nodes in our architecture. The advantages of our approach, as compared with the existing proposals, are its distributed and scalable nature, the ability to provision for quality of service (QoS) through traffic engineering, its ease of gradual deployment, and its efficient design and handover performance.

Multistage packet switches that feature a limited amount of buffers in the switching fabric and distribute most of their buffering capacity over the port cards have recently gained popularity due to their scalability properties and flexibility in supporting quality-of-service (QoS) guarantees. In such switches, the replication of multicast packets typically occurs in-the fabric. This approach minimizes the amount of resources needed to sustain the internal expansion in traffic volume due to multicasting, but also exposes multicast flows to head-of-line (HOL) blocking in the ingress port cards. The distributed scheduler that arbitrates the transfer of packets through the switch and the flow-control scheme that restricts access to the fabric buffers have the most critical role in safeguarding the QoS guarantees of multicast flows against HOL blocking. We add minimal overhead to a well-known QoS framework for multistage packet switches to define the generalized distributed multilayered scheduler (G-DMS), which achieves full support of QoS guarantees for both unicast and multicast flows. The main novelty of the G-DMS is in the mechanism that regulates access to the fabric buffers, which combines selective backpressure with the capability of dropping copies of multicast packets that violate the negotiated profiles of the corresponding flows.

Weighted fair queueing (WFQ) schedulers and shapers have gained wide popularity in current routers and switches because of their advanced quality-of-service features and very low implementation cost. A well-known, intrinsic limitation of WFQ schedulers is the coupling between the bandwidth and delay guarantees that they can provide. Because of this coupling, the support of traffic with low bandwidth and stringent delay requirements, most notably voice, is always problematic with WFQ schedulers. We present the decoupled fair queueing (DFQ) server, which is specifically designed for the support of voice traffic in packet-switched networks. The DFQ server maintains the very low implementation complexity of WFQ schedulers, yet it guarantees low delay to flows requesting relatively low bandwidth. This is achieved by judiciously over-allocating the scheduling rates, and by combining the scheduler with a policer, so as to guarantee that the voice flows only receive the desired bandwidth and do not damage one another, nor the other types of flows that are handled by the server.

Generalized processor sharing (GPS) has gained much popularity as a simple and effective scheduling mechanism for the provisioning of quality of service (QoS) in emerging high-speed networks. For supporting deterministic end-to-end delay guarantees, GPS is known to be sub-optimal in comparison to the earliest deadline first (EDF) scheduling discipline; nevertheless it is often prefered over EDF due to its simplicity. In this paper, using analytical frameworks developed in the literature, we reassess the merits of GPS as compared to EDF in the setting of statistical delay service. Our contributions are threefold. The statistical frameworks in the literature enable the aggregate losses (i.e., delay bound violations) at an EDF scheduler to be estimated-our first contribution, therefore, is to develop a mechanism that allows the aggregate losses to translate to per-flow guarantees. This is achieved by means of a simple packet discard scheme that drops packets fairly then delay violations are imminent at the EDF scheduler. The discard mechanism has a constant complexity and is feasible for implementation in current packet switches. The ability to derive the per-flow guarantees from the aggregate allows a direct comparison between EDF and GPS-our next contribution, therefore, is to show for various traffic mixes with given per-flow loss constraints that EDF offers consistently larger schedulable regions than GPS, both in the single-hop and multi-hop setting. As our final contribution, we argue that the use of GPS for statistical delay support is inherently problematic. We demonstrate that achieving the maximal schedulable regions under GPS could necessitate dynamic resynchronization of the GPS weights, an operation considered infeasible for practical implementation.

Multiple-module, multistage packet switching systems are gaining popularity as a scalable solution to the ever increasing demand for the aggregate switching capacity. Due to additional contention points between the stages, such systems differ in their behavior from single module output buffered switches, which serve as a model for most of the advanced quality of service (QoS) scheduling algorithms. Recently, a distributed scheduling reference architecture has been proposed to extend the QoS provisioning framework to the practical multistage switches. While keeping all the per-flow state information in the port card, it aggregates the individual traffic flows into a few QoS based fabric channels and relies on the intelligent selective feedback to ensure that the QoS guarantees of the individual flows are met. In this paper we discuss a novel credit-based feedback mechanism that allows to aggregate multiple traffic components with diverse QoS requirements into the same downstream FIFO queue. We specifically apply it to merge the guaranteed-bandwidth (GB) and best-effort (BE) QoS channels of the distributed scheduling architecture into a single non-guaranteed-delay queue in the switch fabric. The mechanism allows to satisfy the bandwidth requirements of the GB traffic while maximizing the throughput of the BE traffic and distributes the available excess bandwidth between different types of traffic fairly. The presentation is supported by fluid stationary analysis and packet-level simulations.

This paper develops a framework for statistically guaranteeing end-to-end delay bounds to leaky-bucket-constrained flows transporting real-time traffic in a network of switches using earliest deadline first (EDF) packet scheduling and per-hop traffic shaping. We first analyze the delay-bound violation probabilities at an isolated EDF scheduler fed by fluid source processes generating extremal dual-leaky-bucket-regulated traffic. We compute a close upper bound by applying the Benes approach to an equivalent hypothetical system derived from the real one. We then extend the analysis to the end-to-end scenario in the presence of traffic re-shaping at each node in the network. We compare the analytical results with simulations, and show that the match is very close. We also investigate the advantages of smoothing the traffic at the ingress to the network, and propose a simple choice of smoothing parameters, which perform very well. Using realistic traffic parameters, we compare the schedulable region of our statistical framework with that of the corresponding deterministic framework, and demonstrate that the statistical framework allows tremendous improvements in network utilization, even for very low delay-violation probabilities. The framework developed in this paper is therefore highly useful in practical packet networks to provide quality of service to real-time applications in the form of statistical, rather than deterministic, end-to-end delay bounds.

The continuous growth in the demand for diversified quality-of-service (QoS) guarantees in broadband networks introduces new challenges in the design of packet switches that scale to large switching capacities. Packet scheduling is the most critical function involved in the provision of individual bandwidth and delay guarantees to the switched flows. Most of the scheduling techniques proposed so far assume the presence in the switch of a single contention point, residing in front of the outgoing links. Such an assumption is not consistent with the highly distributed nature of many popular architectures for scalable switches, which typically have multiple contention points, located in both ingress and egress port cards, as well as in the switching fabric. We define a distributed multilayered scheduler (DMS) to provide differentiated QoS guarantees to individual end-to-end flows in packet switches with multiple contention points. Our scheduling architecture is simple to implement, since it keeps per-flow scheduling confined within the port cards, and is suitable to support guaranteed and best-effort traffic in a wide range of QoS frameworks in both IP and ATM networks.

We propose a novel buffer management scheme in order to regulate the individual queue lengths in a shared-memory switch. The primary motivations of our scheme are: (i) provide differentiated allocations to the queues sharing the memory, where the allocations are directly derived from the call admission control (CAC) parameters; (ii) allow for the co-existence of regulated and best-effort traffic achieving high buffer utilization without violating the guaranteed buffer allocations of the regulated connections; (iii) protect well-behaving connections that conform to their allocations from any misbehaviour in other traffic; and (iv) handle deviations in incoming traffic patterns, from the ones assumed by CAC, by distributing unavoidable losses in an equitable manner. The new scheme, which we call dynamic partitioning, achieves all these objectives, and constitutes a first example of a scheme that is highly efficient, derives its parameters directly from CAC, and is also very robust against misbehaviour. The scheme is simple to implement, and therefore amenable for deployment in current high-speed switches. We present the scheme in the context of ATM switches, together with cell level simulations for its validation.

The total implementation cost of schedulers which approximate the generalized processor sharing (GPS) policy is dominated by the complexity of maintaining and sorting the time-stamps for all connections. Several approaches have been proposed which reduce the cost of the sorting operation and only introduce a small degradation in the delay bounds of the scheduler; they include logarithmic calendar queues and schedulers supporting a discrete set of guaranteed rates. All these techniques still require computing and storing one time-stamp per connection, thus maintaining the cost of GPS-related algorithms clearly higher than that of less sophisticated schedulers. Furthermore, in the case of the discrete-rate approach, the complexity increases linearly with the number of supported rates, thus making it attractive only for relatively small numbers of rates. In this paper, we introduce a discrete-rate GPS-related scheduler which does not require the computation and storage of one time-stamp per connection, and only maintains a single time-stamp per rate. The elimination of the per-connection time-stamps has no negative effect on the delay bounds. Then, we present a generalized discrete-rate approach, which uses a given number of FIFO queues to support a larger number of guaranteed rates, and only introduces a modest degradation in delay bounds for certain rates. The technique can be applied to our no-per-connection-time-stamp scheduler, as well as to any discrete-rate scheduler.

The minimum-delay self-clocked fair queueing (MD-SCFQ) algorithm that we present in this paper is the first algorithm that achieves the same delay bounds as the packet by packet version of generalized processor sharing (P-GPS), has fairness properties similar to P-GPS, and uses a system-potential function of 0(1) complexity. To prove that MD-SCFQ achieves the same delay bounds of P-GPS, we have shown that the fluid version of MD-SCFQ belongs to the class of rate proportional server (RPS) schedulers; thus, its packet-by-packet version inherits all the well-known single-node and multiple-node delay properties of P-RPS schedulers. We have also computed the fairness index of MD-SCFQ, and show that is very close to that of P-GPS. Because of the properties of its system potential, MD-SCFQ, when combined with a shaper which declares packets eligible for scheduling according to their virtual starting times, is a work-conserving worst-case fair scheduler.

A central issue in congestion control for available bit rate (ABR) services is the computation of the fair share for every connection at each switching node in the network. An important class of algorithms for the switch behavior computes the fair share according to the exact definition of max-min fairness, and uses it as the explicit rate conveyed to the sources. These algorithms may encounter difficulties due to the complex task of keeping track of active connections. In addition, since these schemes treat all connections equally, they lead to under-utilization of the link capacity when on-off sources are present in the network. To obviate these shortcomings, it has been proposed to use the traffic load to correct the computed fair share when setting the explicit rate. In this paper, first we show that using the traffic load as suggested in literature inherently perturbs rate allocation, and makes the schemes sensitive to the round-trip delay of the connections, leading to unfairness. Then, we introduce a scheme called the enhanced fast max-min rate allocation (E-FMMRA) algorithm, which solves the problem by keeping track of the maximum explicit rate over all backward RM cells. The same technique used in E-FMMRA can also be applied to the popular explicit rate indication for congestion avoidance (ERICA) scheme to solve similar problems associated with the use of the traffic load.

Several algorithms have been proposed for the switch behavior for congestion control of available bit rate (ABR) services. Schemes such as the enhanced proportional rate control algorithm (EPRCA) and the dynamic max rate control algorithm (DMRCA), which use the queue length as the congestion indicator to make a simple approximation of the fair share converge to the actual fair share, have become popular, because they offer a good performance and are simple to implement. In particular, with no VBR traffic in the network, DMRCA has been shown to achieve fairness in all situations, good buffer control, and robust performance. First we show that the performance of these schemes may degrade when ABR traffic interacts with highly-bursty VBR traffic. If VBR traffic induces congestion in the network, the length of the ABR queue cannot serve as a reliable indicator of congestion caused by ABR traffic, and the schemes perform poorly, introducing considerable unfairness. Then, we propose a simple technique to solve these problems. The switch constructs the length of a virtual queue which is not affected by the instantaneous behavior of VBR traffic, and does not depend on how the two types of traffic are served in order to share the common link capacity; thus, it can serve as a reliable indicator of congestion. We use this technique in DMRCA with virtual queueing (DMRCA-VQ), and show that the new scheme achieves fair rate allocation to the ABR connections also in the presence of highly-bursty VBR traffic. The DMRCA-VQ maintains the low hardware complexity of DMRCA. The virtual queueing technique is a solution for the more general problem of separating rate allocation based on the queue length from scheduling of multiple queues for sharing a common resource.

We study shared-memory switches under multicast bursty traffic and characterize the relation between their performance and the multicast distribution that defines the mix of multicast traffic arriving at the switches. We consider two schemes that have been used in practical realizations of these switches to replicate multicast cells: (1) replication-at-receiving (RAR), where multiple copies of a multicast cell are stored in the buffer and served independently, and (2) replication-at-sending (RAS), where a single instance of a multicast cell is stored in the buffer, and the cell is replicated as it is transmitted to the output ports. For each scheme, we study two configurations: (1) the shared-memory-only (SMO) configuration, where the bandwidth of the replication mechanism is sufficient to accommodate even the worst-case replication requirements, and (2) the shared-memory-with-replication-first-in-first-out (SM+RFIFO) configuration, where the bandwidth of the replication mechanism is lower than that required by the worst case, and thus an additional buffer is used in front of the shared memory to temporarily store cells while they are replicated. For all cases, using simulation, we find upper bounds for the buffer requirements to achieve a desired cell-loss rate. We show that these upper bounds are significantly larger than the buffer requirements under unicast traffic and are approached even for very small volumes of multicast traffic; thus, these upper bounds should be used in practice to size the buffers to achieve the desired performance under traffic with general multicast distributions. We also study shared-memory switches with output demultiplexers and characterize and compare the different multicasting schemes that are used in these switches.

We study a shared-memory center-stage switch with input multiplexers and output demultiplexers, where backpressure is applied from the demultiplexers to the center stage, and from the center stage to the multiplexers. We consider three backpressure schemes: (i) non-selective backpressure (NSB), where a congested center stage or a congested demultiplexer applies backpressure indiscriminately to all the traffic destined to it, regardless of the destination; (ii) per-port selective backpressure (PPSB), where the center stage applies backpressure selectively only to the traffic destined to the center-stage port(s) experiencing congestion, but a demultiplexer applies backpressure indiscriminately to all the traffic destined to it; and (iii) per-subport selective backpressure (PSSB), where both center-stage switch and demultiplexers apply backpressure selectively only to the traffic destined to the output link(s) experiencing congestion. We show that NSB introduces heavy HOL blocking which limits the throughput of the system and causes heavy losses. On the contrary, PPSB and PSSB achieve high throughputs, and allow one to increase buffer utilization in the system while keeping the majority of the buffers physically separate in the input multiplexers. Both these schemes perform very well in the case where only limited sharing of the buffers in the center stage is allowed, as required to guarantee fairness in the switch. With PSSB, small buffer sizes in the demultiplexers can be used. If the buffers in the demultiplexers are large, PPSB and PSSB offer comparable performance.

The authors propose a new space-division fast packet switch architecture based on banyan interconnection networks, called the tandem banyan switching fabric (TBSF). It consists of placing banyan networks in tandem, offering multiple paths from each input to each output, thus overcoming in a very simple way the effect of conflicts among packets (to which banyan networks are prone) and achieving output buffering. From a hardware implementation perspective, this architecture is simple in that it consists of several instances of only two VLSI chips, one implementing the banyan network and the other implementing the output buffer function. The basic structure and operation of the tandem banyan switching fabric are described, and its performance is discussed. The authors propose a modification to the basic structure which decreases the hardware complexity of the switch while maintaining its performance. An implementation of the banyan network using a high-performance BiCMOS sea-of-gates on 0.8- mu m technology is reported.>