TY - GEN
T1 - Packet delay-aware scheduling in input queued switches
AU - Li, Yihan
AU - Panwar, Shivendra
AU - Chao, H. Jonathan
AU - Lee, Jong Ha
PY - 2006
Y1 - 2006
N2 - Virtual Output Queuing is widely used by high-speed packet switches to overcome head-of-line blocking. This is done by means of matching algorithms. In fixed-length VOQ switches, variable-length IP packets are segmented into fixedlength cells at the inputs. When a cell is transferred to its destination output, it will stay in the reassembly buffer and wait for the other cells of the same packet before the entire packet can depart the system. The delay a packet suffers in the system includes the waiting time in the VOQ, the widely studied cell delay, and the waiting time at the output reassembly buffer, the reassembly delay often ignored in many papers. Among all existing matching algorithms, Maximum Weight Matching (MWM) has the lowest average cell delay. In this paper, we investigate the average packet delay, one of the key performance measure for an input buffered packet switch. A new class of matching algorithms, PDA-MWM, is defined and proved to be stable under all admissible traffic. Three PDA-MWM matching algorithms are studied by simulation. We show that, in order to achieve low packet delay, there is a tradeoff between the cell delay performance and the reassembly delay performance. If both of them are carefully considered, a matching scheme can greatly reduce the packet delay as compared to MWM.
AB - Virtual Output Queuing is widely used by high-speed packet switches to overcome head-of-line blocking. This is done by means of matching algorithms. In fixed-length VOQ switches, variable-length IP packets are segmented into fixedlength cells at the inputs. When a cell is transferred to its destination output, it will stay in the reassembly buffer and wait for the other cells of the same packet before the entire packet can depart the system. The delay a packet suffers in the system includes the waiting time in the VOQ, the widely studied cell delay, and the waiting time at the output reassembly buffer, the reassembly delay often ignored in many papers. Among all existing matching algorithms, Maximum Weight Matching (MWM) has the lowest average cell delay. In this paper, we investigate the average packet delay, one of the key performance measure for an input buffered packet switch. A new class of matching algorithms, PDA-MWM, is defined and proved to be stable under all admissible traffic. Three PDA-MWM matching algorithms are studied by simulation. We show that, in order to achieve low packet delay, there is a tradeoff between the cell delay performance and the reassembly delay performance. If both of them are carefully considered, a matching scheme can greatly reduce the packet delay as compared to MWM.
KW - Delay performance
KW - Scheduling
KW - Stability
KW - Switching
KW - Virtual Output Queueing
UR - http://www.scopus.com/inward/record.url?scp=50949089248&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=50949089248&partnerID=8YFLogxK
U2 - 10.1109/GLOCOM.2006.351
DO - 10.1109/GLOCOM.2006.351
M3 - Conference contribution
AN - SCOPUS:50949089248
SN - 142440357X
SN - 9781424403578
T3 - GLOBECOM - IEEE Global Telecommunications Conference
BT - IEEE GLOBECOM 2006 - 2006 Global Telecommunications Conference
T2 - IEEE GLOBECOM 2006 - 2006 Global Telecommunications Conference
Y2 - 27 November 2006 through 1 December 2006
ER -