Parallel Matching Algorithms for CIOQ Switches with Multiple Traffic Classes
| Autor: | Ying-Che Kuo, 郭英哲 |
|---|---|
| Rok vydání: | 2005 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 93 Packet switching is the core technology of the Internet. Internet link speeds are increasing to beyond tens of gigabits per second to satisfy a continuing growth in traffic. This increase in link speed and the need for quality of service (QoS) for diverse applications such as voice, audio, and video drive research into new switch architectures. It has recently been shown that a combined input and output queued (CIOQ) switch with a speed-up factor of 2 can exactly emulate an output-queued (OQ) switch. The main benefit of using a CIOQ switch is to reduce memory bandwidth requirement while providing QoS guarantees since memory bandwidth sets a limit in building a large-capacity switch. The key component for exact emulation is a matching algorithm for bipartite graphs. For example, a CIOQ switch with a speedup factor of 2, which adopts the least cushion first/most urgent first (LCF/MUF) matching algorithm, can exactly emulate an OQ switch with any arbitrary service discipline. However, the complexities of cushion calculation and packet reordering required at output ports make the algorithm very difficult to be realized in a high-speed switch. In the first part of this thesis, we propose an approximate LCF/MUF algorithm and evaluate its performance for the weighted round robin (WRR) service discipline. For ease of implementation, the proposed algorithm calculates approximate cushions and does not perform reordering at the output ports. The trade-off is that it loses the property of exact emulation. It was found, via computer simulations, that the performance of a CIOQ switch with the proposed single-iteration matching algorithm is close to that of an OQ switch under uniform, non-uniform, and correlated input traffic models for offered load up to 0.9. In addition, the packet departure order can be maintained under the single-iteration algorithm. On the other hand, to exact emulate an OQ switch, the buffer size at each input and output port is assumed to be of infinite size. This assumption is obviously unrealistic in practice. The performance of the LCF/MUF algorithm with finite input and output buffers is also presented. In current Internet environment, packets are transported with different lengths. Most of previous scheduling algorithms found in open literature were designed for fixed-length packets (or cells) scheduling. Hence, segmenting packets of variable-lengths into cells and re-assembling the cells into original packets are needed before and after packets transmissions across the switching fabric because cells belonging to various packets may interleave with one another. In the second part of this thesis, we present the packet-based LCF/MUF (PB-LCF/MUF) algorithm for CIOQ switches and evaluate its performance via computer simulations. The PB-LCF/MUF algorithm delivers each packet as a whole and thus no cell interleaving of packets happened at output ports. Therefore, no re-assembly buffer is needed. Numerical results show that the performance of a CIOQ switch with a speedup factor of 5 which adopts the single-iteration PB-LCF/MUF algorithm is close to that of an OQ switch under the WRR service discipline. In order to provide QoS guarantee, a switch may have to maintain a large number of queues. However, when considering the cost of hardware implementation, the number of queues is a decisive factor. In the last part of this thesis, we propose a novel output initiated parallel matching (OIPM) algorithm for large-scale input-buffered switches. In our proposed architecture, packets are buffered at input ports while queues are maintained at output ports. The number of queues maintained at each output port is K queues for an N×N switch with K priority classes of traffic which is much smaller than N×K virtual output queues (VOQ) maintained in an input-queued switch. In addition to reducing the number of queues, our proposal guarantees starvation free, in-order delivery, and achieves weighted fairness among traffic classes. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|