Eligibility-Based Round Robin for Fair and Efficient Packet Scheduling in Interconnection Networks

Interconnection networks of parallel systems are used for servicing traffic generated by different applications, often belonging to different users. When multiple users contend for channel bandwidth, fairness in bandwidth sharing becomes a key requirement. In fact, enforcing a fair sharing of channel bandwidth improves flow isolation, thus preventing misbehaving flows from affecting the performance of other flows. We present a novel packet scheduling algorithm, called eligibility-based round robin (EBRR), devised to provide fair queueing in interconnection networks. In fact, EBRR meets the constraints imposed by wormhole switching, which is the most popular switching technique in interconnection networks of parallel systems. It can also be applied to packet switching wide area networks (WANs), such as IP and ATM. We show that EBRR has O(1) complexity and better delay and fairness properties than existing algorithms of comparable complexity. Here, we also investigate the means for assessing the fairness of a scheduler: we show that using the relative fairness bound as a fairness measure may lead to erroneous results. We then propose an alternative measure, called the generalized relative fairness bound, that allows fairness to be assessed more precisely.