On the throughput achievable by isolated and interconnected input-queueing switches under multiclass traffic
Proceedings - IEEE INFOCOM - Tập 3 - Trang 1605-1614 vol.3
Tóm tắt
Many studies provide an extended investigation of the maximum throughput achievable in input-queueing (IQ) or combined-input-and-output-queueing (CIOQ) packet switches. Some scheduling policies, among which are maximum weight matching algorithms, were identified as optimal, in the sense that they were proved to achieve 100% throughput under any admissible single-class traffic pattern. Most of the results in the literature, however, consider just one switch in isolation, operating on packets belonging to a single traffic class. In this paper we first generalize known results, showing that a wide class of IQ schedulers operating on multiple traffic classes can achieve 100% throughput. In addition, we address the problem of the maximum throughput achievable in a network of interconnected IQ switches loaded by multiclass traffic, and we devise some simple scheduling policies that guarantee 100% throughput when switches are interconnected in a network. Both the Lyapunov function methodology and the fluid models approach are used to obtain our results.
Từ khóa
#Throughput #Switches #Scheduling algorithm #Packet switching #Traffic control #Fabrics #Telecommunication traffic #Algorithm design and analysis #Pattern matching #Lyapunov methodTài liệu tham khảo
10.1109/INFCOM.2001.916664
10.1109/49.772432
10.1109/GLOCOM.1999.830047
10.1109/INFCOM.2000.832561
10.1109/49.772435
hung, 0, ATM input-buffered switches with the guaranteed-rate property, ISCC '98 Athens Greece June 1998, 331
10.1109/INFCOM.2000.832560
10.1109/INFCOM.2000.832229
10.1109/26.809713
10.1145/321879.321887
10.1109/INFCOM.2002.1019413
10.1137/1.9781611970265
10.1109/INFCOM.1998.665071
10.1109/INFCOM.2000.832561
10.1109/90.336324
kushner, 1967, Stochastic Stability and Control
10.1109/5.469298
mckeown, 1995, Scheduling algorithms for input-queued cell switches
10.1214/aoap/1177004828
10.1145/143365.143495
10.1109/90.909028
10.1109/26.780463
10.1109/49.772430
10.1109/INFCOM.1995.515971
dai, 1999, Stability of fluid and stochastic processing networks
mckeown, 0, A practical scheduling algorithm to achieve 100% throughput in input-queued switches, IEEE INFOCOM 98 San Francisco CA USA Apr 1998, 792