loading...
Fair Queuing with Round Robin: A New Packet Scheduling Algorithm for Routers
Ramada Hotel, Taormina-Giardini Naxos, Italy July 01-July 04
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISCC.2002.1021794Seventh IEEE Symposium on Computers a ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Arunabha Sen, Arizona State University
Ibraz Mohammed, Arizona State University
Ravikanth Samprathi, CISCO Systems
Subir Bandyopadhyay, University of Windsor
In the last few years several queuing policies have been proposed to ensure fairness between competing requests at a service point. Fair Queuing (FQ) algorithm due to Demers, Keshav and Shenkar is a queuing technique that attains near perfect fairness, where perfect fairness is considered to be the one attained by a fluid flow model. In data network, head of the line processor sharing (PS) is considered to be the most fair algorithm. It has been shown that the difference in throughput at any time, in any queue, for any arrival pattern between the FQ and the PS discipline will never exceed MAX, where MAX is the maximum packet size. This difference in throughput is taken as a metric for fairness measure of a queuing algorithm. The draw-back of the FQ algorithm is its high packet processing overhead (O(log N)), where N is the number of active flows. To alleviate this problem of high computational complexity, Shreedhar and Varghese proposed a fair queuing algorithm based on the idea of deficit round robin (DRR). Although DRR reduces the packet processing overhead to O(1), its fairness measure is considerably worse (3MAX) than that of FQ (MAX). In this paper, we present a new round robin based fair queuing algorithm (FQRR) whose packet processing overhead is O(1) and fairness measure is 2MAX.
Citation:
Arunabha Sen, Ibraz Mohammed, Ravikanth Samprathi, Subir Bandyopadhyay, "Fair Queuing with Round Robin: A New Packet Scheduling Algorithm for Routers," iscc, pp.1001, Seventh IEEE Symposium on Computers and Communications (ISCC'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.