# Chuyển đổi lý thuyết P8

Chia sẻ: Tien Van Van | Ngày: | Loại File: PDF | Số trang:55

0
53
lượt xem
4

## Chuyển đổi lý thuyết P8

Mô tả tài liệu

ATM Switching with Non-Blocking Multiple-Queueing Networks We have seen in the previous chapter how a non-blocking switch based on a single queueing strategy (input, output, or shared queueing) can be implemented and what trafﬁc performance can be expected. Here we would like to investigate how two of the three different queueing strategies can be combined in the design of a non-blocking ATM switch. The general structure of a non-blocking switch with size N × M is represented in Figure 8.1. Each input port controller (IPC) and output port controller (OPC) are provided with a FIFO buffer of size B i and...

Chủ đề:

Bình luận(0)

Lưu

## Nội dung Text: Chuyển đổi lý thuyết P8

1. Switching Theory: Architecture and Performance in Broadband ATM Networks Achille Pattavina Copyright © 1998 John Wiley & Sons Ltd ISBNs: 0-471-96338-0 (Hardback); 0-470-84191-5 (Electronic) Chapter 8 ATM Switching with Non-Blocking Multiple-Queueing Networks We have seen in the previous chapter how a non-blocking switch based on a single queueing strategy (input, output, or shared queueing) can be implemented and what trafﬁc performance can be expected. Here we would like to investigate how two of the three different queueing strategies can be combined in the design of a non-blocking ATM switch. The general structure of a non-blocking switch with size N × M is represented in Figure 8.1. Each input port controller (IPC) and output port controller (OPC) are provided with a FIFO buffer of size B i and B o cells, respectively. A FIFO shared buffer with capacity NB s cells is also associated with the non-blocking interconnection network (IN). Therefore B i , B o and B s represent the input, output and shared capacity per input–output port in a squared switch. Apparently having B x = 0 for x = i, o, s corresponds to absence of input, output and shared queueing, respectively. Usually, unless required by other considerations, IPC and OPC with the same index are implemented as a single port controller (PC) interfacing an input and an output channel, so that the switch becomes squared. Unless stated otherwise, a N × N squared switch is consid- ered in the following and its size N is a power of 2. Output queueing is adopted when the interconnection network is able to transfer more than one cell to each OPC, since only one cell per slot can leave the OPC. Then the switch is said to have an (output) speed-up K meaning that up to K packets per slot can be received by each OPC. Note that the condition K ≤ min [ B o, N ] always applies. While the second bound is determined by obvious physical considerations, the former bound is readily explained con- sidering that it would make no sense to feed the output queue in a slot with a number of packets larger than the queue capacity. Therefore even the minimum speed-up K = 2 requires an output queueing capability B o ≥ 2 . The switch can also be engineered to accom- plish an input speed-up K i in that up to K i packets per slot can be transmitted by each IPC. When an input speed-up is performed ( K i ≥ 2 ) , the output speed-up factor K will be indi- cated by K o . Accordingly in the general scheme of Figure 8.1 the interconnection network is
2. 282 ATM Switching with Non-Blocking Multiple-Queueing Networks IPC IN OPC 0 0 Bi 1 Ki Ko Bo 1 NBs 1 N-1 M-1 Ko-non-blocking Ki Ko Bi 1 network Bo 1 Figure 8.1. Model of Ko-non-blocking ATM switch labelled as a K o -non-blocking network. Nevertheless, to be more precise, the network needs only be K o -rearrangeable due to the ATM switching environment. In fact, all the I/O con- nections through the interconnection network are set up and cleared down at the same time (the slot boundaries). In general if the switch operates an input speed-up K i , then the output speed-up must take a value K o ≥ K i . In fact it would make no sense for the OPCs to be able to accept a num- ber of packets NK o smaller than the NK i packets that can be transmitted by the IPCs in a slot. Therefore, output speed-up is in general much cheaper to implement than input speed- up, since the former does not set any constraint on K i which can be set equal to one (no input speed-up). For this reason most of this section will be devoted to networks adopting output speed-up only. The availability of different queueing capabilities makes it possible to engineer the switch in such a way that packets are transferred from an upstream queue to a downstream queue, e.g. from an input queue to an output queue, only when the downstream queue does not overﬂow. Therefore we will study two different internal operations in the switch: • Backpressure (BP): signals are exchanged between upstream and downstream queues so that the former queues transmit downstream packets only within the queueing capability of the latter queues. • Queue loss (QL): there is no exchange of signalling information within the network, so that packets are always transmitted by an upstream queue independent of the current buffer sta- tus of the destination downstream queue. Packet storage in any downstream queue takes place as long as there are enough idle buffer positions, whereas packets are lost when the buffer is full. Thus, owing to the non-blocking feature of the interconnection network, packets can be lost for overﬂow at the upstream queues only in the BP mode and also at the downstream queues in the QL mode. In the analytical models we will assume that the selection of packets to be
3. 283 backpressured in the upstream queues (BP) or to be lost (QL) in case of buffer saturation is always random among all the packets competing for the access to the same buffer. Our aim here is to investigate non-blocking ATM switching architectures combining dif- ferent queueing strategies, that is: • combined input–output queueing (IOQ), in which cells received by the switch are ﬁrst stored in an input queue; after their switching in a non-blocking network provided with an out- put speed-up, cells enter an output queue; • combined shared-output queueing (SOQ), in which cells are not stored at the switch inlets and are directly switched to the output queues; an additional shared storage capability is avail- able to hold those cells addressing the same switch outlet in excess of the output speed-up or not acceptable in the output queues due to queue saturation when backpressure is applied; • combined input-shared queueing (ISQ), in which cells received by the switch are ﬁrst stored in an input queue; an additional queueing capability shared by all switch inputs and outputs is available for all the cells that cannot be switched immediately to the desired switch outlet. If a self-routing multistage interconnection network is adopted, which will occur in the case of IOQ and SOQ structures, the general model of Figure 8.1 becomes the structure shown in Figure 8.2 where only output speed-up, with a factor K, is accomplished. Following one of the approaches described in Section 3.2.3, the K-non-blocking interconnection network is imple- mented as a two-block network: an N × N sorting network followed by K banyan networks, each with size N × N . The way of interconnecting the two blocks is represented as a set of N splitters 1 × N in Figure 8.2, so that the overall structure is K-non-blocking. The other imple- mentations of the non-blocking network described in Section 3.2.3 could be used as well. IPC0 1 OPC0 2 Shared 0 queue 0 0 K Bi 1 Bo 1 Sorting network NBs 1 Routing IPCN-1 network OPCN-1 N-1 N-1 N-1 Bi 1 Bo 1 Figure 8.2. Model of K-non-blocking self-routing multistage ATM switch In the following, Section 8.1 describes architectures and performance of ATM switches with combined input–output queueing. Section 8.2 and Section 8.3 do the same with com- bined shared-output and input-shared, respectively. The switch capacities of different non-
4. 284 ATM Switching with Non-Blocking Multiple-Queueing Networks blocking switches, either with single queueing or with multiple queueing, are summarized and compared with each other in Section 8.4. Some additional remarks concerning the class of ATM switches with multiple queueing are given in Section 8.5. 8.1. Combined Input–Output Queueing By referring to the general switch model of Figure 8.1, an ATM switch with combined input– output queueing (IOQ) is characterized by B i ≥ 1 , B o ≥ 1 and B s = 0 . However, since the switch accomplishes an output speed-up K o ≥ 2 , the minimum value of the output queues is B o = 2 (see the above discussion on the relation between K o and B o ). A rather detailed description will be ﬁrst given of basic IOQ architectures without input speed-up operating with both the internal protocols BP and QL. These architectures adopt the K-non-blocking self-routing multistage structure of Figure 8.2 where the shared queue is removed. A thorough performance analysis will be developed and the results discussed for this structure by preliminarily studying the case of a switch with minimum output queue size B o = K . Then a mention will be given to those architectures adopting a set of parallel non- blocking switch planes with and without input speed-up. 8.1.1. Basic architectures The basic switch implementations that we are going to describe are based on the self-routing multistage implementation of a K-non-blocking network described in Section 3.2.3, under the name of K-rearrangeable network. Therefore the interconnection network is built of a sorting Batcher network and a banyan routing network with output multiplexers, which are implemented as output queues located in the OPCs in this ATM packet switching environ- ment. As with the interconnection network with pure input queueing, the IPC must run a contention resolution algorithm to guarantee now that at most K of them transmit a packet to each OPC. Additionally here the algorithm must also avoid the overﬂow of the output queues when backpressure is adopted. The switch architectures with the queue loss (QL) internal protocol and without input speed-up ( K i = 1 ) will be described ﬁrst, by upgrading the structures already described with pure input queueing (Section 7.1.1). Then a possible implementation of one of these architec- tures with internal backpressure between input and output queueing will be studied. 8.1.1.1. Internal queue loss The two basic architectures described with pure input queueing, that is the Three-Phase switch and the Ring-Reservation switch can be adapted to operate with an output speed-up K. In both cases no input speed-up is assumed ( K i = 1 ) . The architecture of the Three-Phase switch with combined input–output queueing is shown in Figure 8.3: it includes a K-non-blocking network, composed of a sorting network (SN), a routing banyan network (RN), and an allocation network (AN). Such structure differs
7. Combined Input–Output Queueing 287 implementing output multiplexing described in Section 3.2.3, the example in Figure 8.5 shows the data phase for the two solutions b and c'. The routing network is implemented as an 8 × 16 banyan network in the former case, thus requiring the use of a one-bit field RI follow- ing ﬁeld DA, and as a set of two 8 × 8 banyan networks in the latter case with EGS interconnection from the sorting network (no field RI is here required). In the example the PCs issue six requests, of which one is not granted owing to a number of requests for outlet 5 larger than the output speed-up K = 2 . RI AC AC activity DA DA destination address PC PC 0 0 5 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 2 0 1 1 0 0 0 2 3 1 5 1 Network 0 1 1 Network 3 4 0 0 0 SN 1 1 1 RN 4 0 5 1 5 0 0 0 0 5 1 5 1 5 1 6 0 7 1 1 5 1 6 7 1 1 1 0 7 1 0 7 1 7 III Data (b) AC DA PC PC 0 5 1 0 0 0 1 1 1 0 0 0 0 1 1 1 2 1 1 0 0 2 3 5 1 Network 1 1 Network Network 3 4 0 0 SN 1 1 RN 1 RN 4 5 1 5 0 0 5 1 5 5 1 6 7 1 5 1 6 7 1 1 7 1 7 1 7 III Data (c') Figure 8.5. Example of packet switching (Phase III) in the QL IOQ Three-Phase switch About the hardware required by this IOQ Three-Phase switch N × N with QL protocol, the K-non-blocking network is assumed as the minimum-cost implementation described in Section 3.2.3 with a Batcher sorting network N × N cascaded through an EGS pattern to K N × N banyan networks. The allocation network is implemented basically as the running sum
8. 288 ATM Switching with Non-Blocking Multiple-Queueing Networks adder network of Figure 7.14, which now includes k' = log 2K stages of adders. Some minor changes have to be applied to take into account that now an activity bit distinguishes idle packets from true request packets so that the running sum in network AN is started in cor- respondence of the ﬁrst non-idle packet. With such a structure different values for the ﬁeld GR in the range [ 0, 2 k' – 1 ] will be associated with the ﬁrst 2 k' requests for the same switch out- let, received on adjacent inputs. The Ring-Reservation switch with pure input queueing can more easily be adapted to operate an output speed-up K. In this case the interconnection network is a K-non-blocking network, the same above adopted in the IOQ Three-Phase switch. The reservation process for the NK outlets of the routing network (K per switch outlet) simply requires that a reservation frame of NK ﬁelds makes a round along the ring crossing all the PCs. As in the case of pure input queueing, each PC reserves the ﬁrst idle ﬁeld of the K associated to the desired switch outlet. If all the K ﬁelds are already reserved (they have been booked by upstream PCs), the PC will attempt a new reservation in the following slot. Unlike an IQ ring reservation switch, the use of the routing network cannot be avoided here, since now a total of NK lines enter the OPCs but at most N packets are transmitted by the IPCs. By implicitly assuming the same hypotheses and following the same procedure as for the IQ multichannel Three-Phase switch described in Section 7.1.3.1 (MULTIPAC switch), the switching overhead η = T I – II ⁄ T III required to perform the three-phase algorithm in the IOQ QL switch is now computed. The duration of Phase I is given by the latency n ( n + 1 ) ⁄ 2 in the Batcher network and the transmission time 1 + n of the ﬁrst two ﬁelds in packet REQ (the transmission time of the other field in packet REQ is summed up in Phase II). The duration of Phase II includes the latency n ( n + 1 ) ⁄ 2 in the Batcher network and the transmission time n + 1 + k' of packet ACK since the time to cross network AN need not be summed (see the analogous discussion for the multichannel IQ switch in Section 7.1.3.1). Hence, the duration of the ﬁrst two phases for an IOQ switch is given by T I – II = n ( n + 3 ) + k' + 2 = log N ( log 2N + 3 ) + log 2K + 2 2 whereas T I – II = log N ( log 2N + 4 ) + 1 in the basic IQ Three-Phase switch. Therefore 2 adding the output speed-up to the basic IQ architecture does not increase the channel internal channel rate C ( 1 + η ) , owing to the use of idle request packets that make it useless for pack- ets ACK to cross network RN. In the ring reservation IOQ switch the minimum bit rate on the ring is clearly K times the bit rate computed for the basic IQ switch, since now the reser- vation frame is K times longer. Therefore, the minimum bit rate is equal to KNC ⁄ ( 53 ⋅ 8 ) . 8.1.1.2. Internal backpressure Basic architecture. An architecture of IOQ switch with internal backpressure (BP) that pre- vents packet loss in the output queues [Pat91] is obtained starting from the IOQ Three-Phase switch with QL protocol described in the previous section. The architecture of an N × N BP IOQ switch is represented in Figure 8.6: it includes an N × N sorting network (SN), an N × NK routing network (RN), and three networks with size N × 2N , that is a merge net- work (MN), an allocation network (AN) and a concentration network (CN).
9. I0 O0 a0 c0 d0 e0 Combined Input–Output Queueing f0 K PC0 j0 k0 b0 Sorting Routing Network network SN RN IN-1 ON-1 fN-1 aN-1 Merge cN-1 Allocation dN-1 Concentr. eN-1 K network PCN-1 network network jN-1 MN AN CN kN-1 bN-1 aN cN dN eN with internal backpressure a2N-1 c2N-1 d2N-1 e2N-1 Figure 8.6. Architecture of the K-non-blocking Three-Phase switch 289