TY - JOUR
T1 - Integration of unicast and multicast scheduling in input-queued packet switches
AU - Zhu, Weiying
AU - Song, Min
PY - 2006/4/6
Y1 - 2006/4/6
N2 - Packet queuing and scheduling, two of the critical components in an input-queued packet switch, have been extensively studied in the context of either pure unicast traffic or pure multicast traffic. Unfortunately, the results from a study in one context are not applicable to the other context. The design of integrated scheduling for both types of traffic remains an open issue. This paper deals with the problem of integrating unicast and multicast scheduling in an N × N input-queued packet switch with first in first out buffers. Instead of using isolated switching fabrics for unicast and multicast traffic respectively, we efficiently utilize one switching fabric for both unicast and multicast traffic by a careful design. In our design, each input port maintains a set of unicast queues based on virtual output queuing technique and a set of multicast queues based on a load-balance policy. By employing the research advances that have already been gained for unicast and multicast scheduling, we propose two practical slot-coupled integration algorithms, lSCIA (a loosely slot-coupled integration algorithm) and fSCIA (a fully slot-coupled integration algorithm). In each time slot, unicast scheduling and multicast scheduling cooperate together and the scheduling priority is allocated to either unicast traffic or multicast traffic according to a certain service ratio. The working interval of service ratio is defined as a set such that the saturation throughput is not less than the output load if the service ratio falls into this set. The upper bound and lower bound for the working interval of service ratio are deduced. A 100% throughput can be achieved with strong theoretical guarantees as long as the service ratio lies in the upper bound of the working interval. Both theoretical analysis and simulation studies suggest that the proposed integrated scheduling algorithms exhibit a promising performance in terms of throughput, delay and packet loss ratio, at different traffic compositions under Bernoulli traffic and bursty traffic.
AB - Packet queuing and scheduling, two of the critical components in an input-queued packet switch, have been extensively studied in the context of either pure unicast traffic or pure multicast traffic. Unfortunately, the results from a study in one context are not applicable to the other context. The design of integrated scheduling for both types of traffic remains an open issue. This paper deals with the problem of integrating unicast and multicast scheduling in an N × N input-queued packet switch with first in first out buffers. Instead of using isolated switching fabrics for unicast and multicast traffic respectively, we efficiently utilize one switching fabric for both unicast and multicast traffic by a careful design. In our design, each input port maintains a set of unicast queues based on virtual output queuing technique and a set of multicast queues based on a load-balance policy. By employing the research advances that have already been gained for unicast and multicast scheduling, we propose two practical slot-coupled integration algorithms, lSCIA (a loosely slot-coupled integration algorithm) and fSCIA (a fully slot-coupled integration algorithm). In each time slot, unicast scheduling and multicast scheduling cooperate together and the scheduling priority is allocated to either unicast traffic or multicast traffic according to a certain service ratio. The working interval of service ratio is defined as a set such that the saturation throughput is not less than the output load if the service ratio falls into this set. The upper bound and lower bound for the working interval of service ratio are deduced. A 100% throughput can be achieved with strong theoretical guarantees as long as the service ratio lies in the upper bound of the working interval. Both theoretical analysis and simulation studies suggest that the proposed integrated scheduling algorithms exhibit a promising performance in terms of throughput, delay and packet loss ratio, at different traffic compositions under Bernoulli traffic and bursty traffic.
KW - Input-queued
KW - Integration
KW - Multicast
KW - Packet switches
KW - Queuing
KW - Scheduling
UR - http://www.scopus.com/inward/record.url?scp=31044448423&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=31044448423&partnerID=8YFLogxK
U2 - 10.1016/j.comnet.2005.06.004
DO - 10.1016/j.comnet.2005.06.004
M3 - Article
AN - SCOPUS:31044448423
SN - 1389-1286
VL - 50
SP - 667
EP - 687
JO - Computer Networks
JF - Computer Networks
IS - 5
ER -