Tradeoffs in Delay Guarantees and Computation Complexity for Packet Switches NN
C.E. Rohrs, Michael J. Neely, Eytan Modiano · 2002
We consider the tradeoffs between packet delay guar- antees and per-timeslot computation complexity in an packet switch operating under the crossbar constraint. It is well known that scheduling packets every timeslot according to a Maxi- mum Weight Matching (MWM) achieves 100% throughput. This algorithm ensures average packet delay is within O(n) timeslots (where n is the number of input ports of the switch) but is quite complex to implement, requiring O(n 3 ) computations every slot to compute the schedule. Here we develop a modified version of MWM which reduces computation complexity while still ensuring 100% throughput and offering polynomial delay bounds. Specifi- cally, we develop a class of scheduling policies (parameterized by ) which achieve a per-timeslot computation complexity of O(n α ) and ensure O(n 4-α ) bounds on average delay. In particu- lar, linear per-timeslot computation complexity is achievable with an O(n 3 ) delay guarantee (case α =1). Furthermore, as , complexity can be made as low as desired while delay is held within O(n 4 ). These results for the first time illustrate an explicit tradeoff between performance and scheduling complexity.