CU-Boulder ECEN 5032 - Queueing in High-Performance Packet Switching

Unformatted text preview:

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 6, NO. 9, DECEMBER 1988 1587 Queueing in High-Performance Packet Switching Abstract-Because of the unscheduled nature of arrivals to a packet switch, two or more packets may arrive on different inputs destined for the same output. The switch architecture may allow one of these packets to pass through to the output, but the others must be queued for later transmission. We study the performance of four different ap- proaches for providing the queueing necessary to smooth fluctuations in packet arrivals to a high-performance packet switch. They are 1) input queueing 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 N input lines to the switch and simultaneously launched into a switch fabric of size Nb x Nb; 3) output queueing where packets are queued in a separate Erst-in first-out (FIFO) buffer located at each output of the switch; and 4) completely shared buffering where all queueing 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. At the expense of an increase in the switch fabric size and latency, the lost packet rate for input smoothing can be made small by increasing the frame size b. Output queueing and completely shared buffering both achieve the op- timal throughput-delay performance for any packet switch. However, compared to output queueing, completely shared buffering requires less buffer memory at the expense of an increase in switch fabric size. 1. INTRODUCTION N the move toward high-performance packet switching I for integrated service networks [ 11 and multiprocessor interconnects [2], attention is focusing on packet-switch- ing architectures that provide many simultaneous input/ output paths through the switch fabric and allow the in- ternal paths to be time-multiplexed in a statistical rather than deterministic fashion. Such architectures provide the capability for high-speed transmission ( 1-200 Mbits/s ) on each input/output with a total switch capacity of 1-200 Gbits/s. Because of the high-speed operation of the switch, the processing of packets is largely hardware- based, with packet headers containing address informa- tion that is used by the switch fabric to route packets from inputs to outputs on the switch. Depending on its design, the switch fabric may be blocking. That is, the switch fabric may be unable to provide simultaneous, indepen- dent paths between arbitrary pairs of inputs and outputs. However, even if the switch fabric is nonblocking, congestion in the switch will still arise because, unlike a circuit switch, arrivals to a packet switch are unsched- Manuscript received November 2, 1987; revised June 11, 1988. This paper was presented at INFOCOM ’88, New Orleans, LA, March 1988. This work was performed while M. G. Hluchyj was with AT&T Bell Lab- oratories. M. G. Hluchyj is with Codex Corporation, Mansfield, MA 02048. M. J. Karol is with AT&T Bell Laboratories, Holmdel, NJ 07733. IEEE Log Number 8824400. uled: two or more packets may arrive simultaneously on different inputs destined for the same output. One of these contending packets for an output may be allowed to pass through the switch, but the others must be queued for later transmission on the output. This form of congestion is unavoidable in a packet switch and dealing with it often represents the greatest source of complexity in the switch architecture. In this paper, we examine the performance of four dif- ferent approaches for providing the queueing necessary to smooth the statistical fluctuations in packet arrivals to the switch. The switch fabric in all cases is assumed to be nonblocking and, as illustrated in Fig. 1, operates syn- chronously with fixed-length packets arriving on the N in- puts in a time-slotted fashion. The four different ap- proaches to packet queueing in the switch are described in Section 11, and the performance of each is analyzed in Section 111. 11. PACKET QUEUEING ARCHITECTURES Fig. 2 illustrates four approaches to providing the queueing for a high-performance packet switch. In this section, we describe how each functions to smooth (in time) the packet arrivals destined to a common output. A. Input Queueing With input queueing, illustrated in Fig. 2(a), a separate buffer is placed on each input to the switch. Each arriving packet enters, at least momentarily, the buffer on its input where it awaits access to the switch fabric. Initially, we assume the buffers are served first-in first-out (FIFO), so that at the beginning of each time slot only the packets at the heads of the FIFO’s contend for access to the switch outputs. If every packet is addressed to a different output, the nonblocking switch fabric allows each to pass through to its respective output. If k packets at the heads of the input FIFO’s are addressed to a particular output, one is allowed to pass through the switch fabric, while the other k - 1 must wait until the next time slot, when a new selection is made among the packets that are then waiting. Note that while a packet is waiting its turn for access to an output, other packets may be queued behind it in the FIFO and, consequently, blocked from reaching possibly idle outputs on the switch. As we shall see in Section III-A, this results in a maximum throughput, for large N, of (2 - h) = 0.586 for input queueing with FIFO buff- ers. The throughput can be increased by relaxing the strict first-in first-out queueing discipline of the input buffers. 0733-8716/88/1200-1587$01.00 O 1988 IEEE1588 1114121 I N- IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 6, NO. 9, DECEMBER 1988 SWITCH IN1 ININ] +N TIME SLOT AI I- [NI 13111 1 I 12121 I‘ NONELOCKING .2 TIME- SLOTTED PACKET (a) INPUT OUEUEING (b) INPUT SMOOTHING -lbk (C) OUTPUT QUEUEING (d) COMPLETELY SHARED BUFFERING Fig. 2. Four approaches to providing the queueing for a high-performance packet switch. Each input still sends, at most, one packet into the switch fabric per time slot, but not necessarily the first packet in its queue, and no more than one packet is allowed to pass through the switch fabric to each output


View Full Document

CU-Boulder ECEN 5032 - Queueing in High-Performance Packet Switching

Documents in this Course
Load more
Download Queueing in High-Performance Packet Switching
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Queueing in High-Performance Packet Switching and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Queueing in High-Performance Packet Switching 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?