Towards simple, high-performance schedulers for high-aggregate bandwidth switches
Proceedings - IEEE INFOCOM - Tập 3 - Trang 1160-1169 vol.3
Tóm tắt
High-aggregate bandwidth switches are those whose port count multiplied by the operating line rate is very high; for example, a 30 port switch operating at 40 Gbps or a 1000 port switch operating at 1 Gbps. Designing high-performance schedulers for such switches is challenging for the following reasons: (i) high performance requires finding good matchings; (ii) good matchings take time to find; (iii) in high-aggregate bandwidth switches there is either too little time (due to high line rates) or there is too much work to do (due to a high port count). We exploit the following features of the switching problem to devise simple-to-implement, high-performance schedulers: (a) the state of the switch (carried in the lengths of its queues) changes slowly with time, implying that heavy matchings will likely stay heavy over a period of time; (b) observing arriving packets conveys useful information about the state of the switch. These features are exploited using hardware parallelism and randomization to yield three scheduling algorithms for IQ (input-queued) switches - APSARA, LAURA and SERENA. These algorithms are shown to achieve 100% throughput and simulations show that their delay performance is quite competitive with respect to the maximum weight matching. The stability proof involves a derandomization procedure and uses methods which may have wider applicability.
Từ khóa
#Bandwidth #Switches #Packet switching #Scheduling algorithm #Bipartite graph #Fabrics #Throughput #Delay #Traffic control #AggregatesTài liệu tham khảo
nijenhuis, 1978, Combinatorial algorithms: For computers and calculators, 2nd Edition Academic Press Chap 7, 56
10.1109/40.988685
10.1109/71.963420
10.1109/71.205650
10.1145/211542.606546
10.1109/INFCOM.1998.665071
10.1109/90.769767
10.1109/INFCOM.1998.665102
mckeown, 1996, Achieving 100% throughput in an input-queued switch, IEEE INFOCOM'96, 1, 296, 10.1109/INFCOM.1996.497906
mckeown, 1995, Scheduling algorithms for input-queued cell switches
10.1109/49.772435
10.1109/INFCOM.2001.916303
prabhakar, 1999, On the speedup required for combined input and output queued switching, Automatica, 35, 1090, 10.1016/S0005-1098(99)00129-6
10.1145/507553.507563
10.1109/INFCOM.2001.916636
10.1145/161541.161736
10.1109/26.809713
10.1109/35.668285
10.1109/HIS.2001.946687
10.1109/INFCOM.1997.635110
10.1109/INFCOM.2000.832229
10.1109/49.772430
10.1109/INFCOM.2001.916665
10.1109/INFCOM.2000.832562