Design and simulation of an input queuing packet switch

Journal of Computer Science, July, 2005 by Azeddine Bilami, Mustapha Lalam, Mohamed Benmohammed

Abstract: Many Architectures of Internet routers, ATM and Ethernet switches have been proposed and analysed in literature. Theoretically reliable and valid solutions have been developed to achieve high performances, but a lot of them are not feasible in practice for commercial and technological reasons. Few papers develop the implementation and simulation aspects. The objective of this study is the design of a packet switch with a minimum cost and hardware complexity. We propose an input-queuing architecture using a multistage interconnection network and a simple cell selection policy implemented by hardware. The switch is described and simulated using a VHDL language. Performances in terms of throughput and cell loss are evaluated.

Key words: Routing, Switch, Multistage Interconnection Network (MIN), Benes Network, Self Routing, VHDL

INTRODUCTION

A major challenge concerned to high-speed switching is related today to switch design that requires the best possible compromise between ease of implementation and goodness of performances.

Switch Functionality is Twofold:

* Managing packet buffering while selecting packets to transmit each time to avoid contentions and cell loss.

* Routing packets from their incoming ports to their destination ports.

To avoid contentions and cell loss, the incoming packets are stored in buffers. These buffers can be in inputs, in outputs, in inputs and in outputs or shared by inputs and outputs. So, a choice that a designer may have is where to place the buffers. Although, a lot of existing switches use the shared buffers technique, it has been shown through several publications that the method using input buffers is the only one which can constantly answer to the increasing needs of large switches and to the high rates of present and future communication lines. With such solution, the cost of the switch remains acceptable and the management of the queues in the buffers less complex. Nevertheless, it introduces the well known problem of the HOL (Head Of Line) blocking which is usually solved by means of scheduling algorithms. Appropriate scheduling algorithms are adopted depending on the application environment and some constraints such as line rate, number of ports to connect, cost, expected performances.

To route packets from input ports to output ports, Multistage Interconnection Networks (MINs) are very attractive. They can route in parallel the incoming packets. They have a relatively low cost and are better adapted for VLSI implementation. MINs have been used initially in multiprocessors architectures to connect the processors to memory banks. Recently and regarding to their characteristics, an other interest is granted to these networks: they are used in the Internet routers, in the ATM and Ethernet switches and are appropriate to be used to construct electro-optic switches.

Using Benes network which present the best cost among non blocking MINs and input buffers technique with a simple selection policy of maximum cells to transmit without conflicts in a cycle, we propose in this study a switch with a low cost introducing a minimum hardware complexity. It may be useful to give the meanings of the following terms that are used frequently in this study.

Permutation: is a one-to-one I/O mapping, where all inputs and outputs are active. It is called a partial permutation, if any I/O are not active. Cell: we consider packets of a fixed size. We prefer using in the continuation of this article, the term 'cell' instead of 'packet'.

Throughput: defined as the number of cells arriving to their destinations divided by the total number of departed cells from their sources in a unit time (a cycle).

Interconnection Network

Benes Network: A (NxN) Benes network (Fig. 1) is a network with N inputs and N outputs. Its dimension is r = [log.sub.2]N. It is composed of 2([log.sub.2]N)-1 stage of 2r-1 switching elements (SE for short) and presents with Waksman network, the best cost among all the non blocking multistage networks: [1]

[FIGURE 1 OMITTED]

BENES network is dynamic and rearrangeable. It presents N12 possible paths to establish a link between a free input and a free output. It is for this fact fault tolerant since we can always establish a path even if some switches are out of use. It offers a constant latency for all couples (input, output). The Only drawback that is known about it is the complexity of its routing control algorithms. The solution usually used is centralized: it needs a global controller, which configures the network before the transfers. This solution requires O(N.r) sequential time to position all the SE(s).

Self Routing: One of the features that give to this network a big interest, are the self-routing property: every 2x2 switch can decide to which of its outputs the incoming cell will be transmitted, depending only on the cell destination address. This means that the implementation of a complex routing algorithm, either centralized or distributed, is not needed.

It has been proved that some permutations families representing a subset of all possible permutations (N! for an NxN Benes network), can be routed automatically in only one pass, consuming 0([log.sub.2]N) in parallel time. Lenfant in [2], has defined the FUB (Frequently Used Bijections) family. Nassimi and Sahni have proposed in [3], an algorithm for the BPC (Bit Permute Complement) class. Boppana and Raghavendra [4] have resolved the problem for the LC (Linear Complement) family. These families are regrouped in the same class BPCL (Bit Permute Closure) of self routing permutations.