DocumentCode :
1600279
Title :
Providing guaranteed rate services in the load balanced Birkhoff-von Neumann switches
Author :
Chang, Cheng-Shang ; Lee, Duan-Shin ; Yue, Chi-Yao
Author_Institution :
Inst. of Commun. Eng., Nat. Tsing Hua Univ., Hsinchu, Taiwan
Volume :
3
fYear :
2003
Firstpage :
1622
Abstract :
In this paper, we propose two schemes for the load balanced Birkhoff-von Neumann switches to provide guaranteed rate services. As in [C. S. Chang et al., (2002)], the first scheme is based on an earliest deadline first (EDF) scheduling policy. In such a scheme, we assign every packet of a guaranteed rate flow a targeted departure time that is the departure time from the corresponding work conserving link with capacity equal to the guaranteed rate. By adding a jitter control mechanism in front of the buffer at the second stage and running the EDF policy at the output buffer, we show that the end-to-end delay for every packet of a guaranteed rate flow is bounded by the sum of its targeted departure time and a constant that only depends on the number of flows and the size of the switch. Our second scheme is a frame based scheme as in [I. Keslassy et al., (2002)]. There, time slots are grouped into fix size frames. Packets are placed in appropriate bins (buffers) according to their arrival times and their flows. We show that if the incoming traffic satisfies certain assumptions, then the end-to-end delay for every packet and the size of the central buffers are both bounded by constants that only depend on the size of the switches and the frame size. The second scheme is much simpler than the first one in many aspects: (i) the online complexity is O(1) as there is no need for EDF, (ii) central buffers are finite and thus can be built into a single chip, (iii) connection patterns of the two switch fabrics are changed less frequently, (iv) there is no need for resequencing-and-output buffer after the second stage, and (v) variable length packets may be handled without segmentation and reassembly.
Keywords :
buffer storage; delays; multistage interconnection networks; packet switching; scheduling; Birkhoff-von Neumann switch; EDF; central buffer; connection pattern; earliest deadline first; finite single chip; frame based scheme; multicasting flow; multistage switch; online complexity; resequencing output buffer; targeted departure time; variable length packet; Bandwidth; Communication switching; Delay; Jitter; Optical buffering; Optical packet switching; Optical switches; Packet switching; Round robin; Size control;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies
ISSN :
0743-166X
Print_ISBN :
0-7803-7752-4
Type :
conf
DOI :
10.1109/INFCOM.2003.1209185
Filename :
1209185
Link To Document :
بازگشت