skip to main content
article

On achieving fairness in the joint allocation of processing and bandwidth resources: principles and algorithms

Published: 01 October 2005 Publication History

Abstract

The problem of achieving fairness in the allocation of the bandwidth resource on a link shared by multiple flows of traffic has been extensively researched over the last decade. However, with the increasing pervasiveness of optical networking and the occasional trend toward using over-provisioning as the solution to bandwidth congestion, a router's processor also becomes a critical resource to which, ideally speaking, all competing flows should have fair access. For example, achieving fairness in the allocation of processing resources can be part of an overall strategy of countering certain kinds of denial of service attacks (such as those based on an excessive use of the router processor by using unnecessary optional headers). In this paper, we investigate the issue of achieving fairness in the joint allocation of the processing and bandwidth resources. We first present a simple but powerful general principle for defining fairness in such systems based on any of the classic notions of fairness such as max-min fairness, proportional fairness, and utility max-min fairness defined for a single resource. We apply our principle to a system with a shared processor and a shared link with max-min fairness as the desired goal. We then propose a practical and provably fair packet-by-packet algorithm for the joint allocation of processing and bandwidth resources. We demonstrate the fairness achieved by our algorithm through simulation results using both synthetic and real gateway traffic traces. The principles and the algorithm detailed in this paper may also be applied in the allocation of other kinds of resources such as power, which is a critical resource in mobile systems.

References

[1]
{1} D. Cohen and K. Narayanaswamy. A Fair Service Approach to Defending Against Packet Flooding Attacks. {Online}. Available: http://www.cs3-inc.com/ddos.html.
[2]
{2} J. Xu and W. Lee, "Sustaining availability of web services under distributed denial of service attacks," IEEE Trans. Comput., vol. 52, no. 2, pp. 195-208, Feb. 2003.
[3]
{3} D. K. Y. Yau, J. C. S. Lui, and F. Liang, "Defending against distributed denial-of-service attacks with max-min fair server-centric router throttles," in Proc. Int. Workshop on Quality of Service (IWQoS), Stanford, CA, May 2002, pp. 35-44.
[4]
{4} D. P. Bertsekas and R. Gallager, Data Networks, 2nd ed. Upper Saddle River, NJ: Prentice-Hall, 1991.
[5]
{5} A. Demers, S. Keshav, and S. Shenker, "Analysis and simulation of a fair queueing algorithm," in Proc. ACM SIGCOMM, Austin, TX, Sep. 1989, pp. 1-12.
[6]
{6} A. K. Parekh and R. G. Gallager, "A generalized processor sharing approach to flow control in integrated service networks--the single node case," in Proc. IEEE INFOCOM, Florence, Italy, May 1992, pp. 915-924.
[7]
{7} S. Keshav, An Engineering Approach to Computer Networking: ATM Network, the Internet, and the Telephone Network. Reading, MA: Addison-Wesley, 1997.
[8]
{8} F. Kelly, "Charging and rate control for elastic traffic," Eur. Trans. Telecommun., vol. 8, no. 1, pp. 33-37, Jan. 1997.
[9]
{9} Z. Cao and E. W. Zegura, "Utility max-min: An application-oriented bandwidth allocation scheme," in Proc. IEEE INFOCOM, New York, Mar. 1999, pp. 793-801.
[10]
{10} L. Kleinrock, Queueing Systems. New York: Wiley, 1976, vol. 2. Computer Applications.
[11]
{11} S. J. Golestani, "A self-clocked fair queueing scheme for broadband applications," in Proc. IEEE INFOCOM, Toronto, ON, Canada, Jun. 1994, pp. 636-646.
[12]
{12} M. Shreedhar and G. Varghese, "Efficient fair queuing using deficit round-robin," IEEE/ACM Trans. Netw., vol. 4, no. 3, pp. 375-385, Jun. 1996.
[13]
{13} J. C. R. Bennett and H. Zhang, "WF2Q: Worst-case fair weighted fair queueing," in Proc. IEEE INFOCOM, San Francisco, CA, Mar. 1996, pp. 120-128.
[14]
{14} S. S. Kanhere, H. Sethu, and A. B. Parekh, "Fair and efficient packet scheduling using elastic round robin," IEEE Trans. Parall. Distr. Syst., vol. 13, no. 3, pp. 324-336, Mar. 2002.
[15]
{15} J. M. Blanquer and B. Özden, "Fair queuing for aggregated multiple links," in Proc. ACM SIGCOMM, San Diego, CA, Aug. 2001, pp. 189-197.
[16]
{16} K. Mochalski, J. Micheel, and S. Donnelly, "Packet delay and loss at the Auckland internet access path," in Proc. Passive Active Measure. Workshop, Fort Collins, CO, Mar. 2002, pp. 46-55.
[17]
{17} V. Raghunathan, S. Ganeriwal, C. Schurgers, and M. Srivastava, "E2WFQ: An energy efficient fair scheduling policy for wireless systems," in Proc. Int. Symp. Low Power Electr. Design, Monterey, CA, Aug. 2002, pp. 30-35.
[18]
{18} Y. Zhou and H. Sethu, "Toward end-to-end fairness: A framework for the allocation of multiple prioritized resources," in Proc. IEEE Int. Perf. Comput. Commun. Conf., Phoenix, AZ, Apr. 2003, pp. 495-504.
[19]
{19} S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss. (1998, Dec.) An Architecture for Differentiated Services. {Online}. Available: http://www.ietf.org/rfc/rfc2475.txt.
[20]
{20} L. Lenzini, E. Mingozzi, and G. Stea, "Trade-offs between low complexity, low latency, and fairness with deficit round-robin schedulers," IEEE/ACM Trans. Netw., vol. 12, no. 4, pp. 681-693, Aug. 2004.
[21]
{21} S. Lu, V. Bhargavan, and R. Srikant, "Fair scheduling in wireless packet networks," IEEE/ACM Trans. Netw., vol. 7, no. 4, pp. 473-489, Aug. 1999.
[22]
{22} Auckland-VI Trace Data {Online}. Available: http://pma.nlanr.net/ Traces/long.
[23]
{23} S. Floyd and V. Jacobson, "Link-sharing and resource management models for packet networks," IEEE/ACM Trans. Netw., vol. 3, no. 4, pp. 365-386, Aug. 1995.
[24]
{24} S. Lu, V. Bharghavan, and R. Srikant, "Fair scheduling in wireless packet networks," in Proc. ACM SIGCOMM, Cannes, France, Sep. 1997, pp. 63-74.

Cited By

View all
  • (2009)A framework for providing hard delay guarantees and user fairness in Grid computingFuture Generation Computer Systems10.1016/j.future.2009.01.00325:6(674-686)Online publication date: 1-Jun-2009
  • (2006)Dynamic adjustment of virtual paths in ATM networksProceedings of the 10th WSEAS international conference on Communications10.5555/1981726.1981806(407-412)Online publication date: 13-Jul-2006

Index Terms

  1. On achieving fairness in the joint allocation of processing and bandwidth resources: principles and algorithms

                        Recommendations

                        Reviews

                        Wei Yen

                        Fairness in the network is an interesting topic from both the theoretical and practical perspectives. In a realistic setting, it is usually hard to define and measure fairness and find the means to achieve it. The authors are ambitious, and look at a static network environment with heterogeneous essential resources. The results are the proposed principle of fair essential resource allocation (FERA) and the packet-by-packet processor and link sharing (PPLS) algorithm. I found the paper inspiring and thought provoking, which is not to say that I agree with each and every statement in it. In fact, the authors make some counterintuitive assumptions and points. For instance, it is debatable that the essential resource should exclude buffer because its allocation is dependent on other types of resources. The authors make a good contribution by creating the framework that will become the foundation for further advances in this area of research. In addition, this paper is well written and self-contained. Although I wish the authors had given more elaborate simulation results, I believe graduate students will be able to get the gist of this paper with some effort. I strongly recommend the paper to telecom operators and scholars in this area. It is quite a rewarding read. Online Computing Reviews Service

                        Access critical reviews of Computing literature here

                        Become a reviewer for Computing Reviews.

                        Comments

                        Information & Contributors

                        Information

                        Published In

                        cover image IEEE/ACM Transactions on Networking
                        IEEE/ACM Transactions on Networking  Volume 13, Issue 5
                        October 2005
                        269 pages

                        Publisher

                        IEEE Press

                        Publication History

                        Published: 01 October 2005
                        Published in TON Volume 13, Issue 5

                        Author Tags

                        1. fairness
                        2. max-min
                        3. processor sharing
                        4. resource allocation

                        Qualifiers

                        • Article

                        Contributors

                        Other Metrics

                        Bibliometrics & Citations

                        Bibliometrics

                        Article Metrics

                        • Downloads (Last 12 months)1
                        • Downloads (Last 6 weeks)0
                        Reflects downloads up to 14 Feb 2025

                        Other Metrics

                        Citations

                        Cited By

                        View all
                        • (2009)A framework for providing hard delay guarantees and user fairness in Grid computingFuture Generation Computer Systems10.1016/j.future.2009.01.00325:6(674-686)Online publication date: 1-Jun-2009
                        • (2006)Dynamic adjustment of virtual paths in ATM networksProceedings of the 10th WSEAS international conference on Communications10.5555/1981726.1981806(407-412)Online publication date: 13-Jul-2006

                        View Options

                        Login options

                        Full Access

                        View options

                        PDF

                        View or Download as a PDF file.

                        PDF

                        eReader

                        View online with eReader.

                        eReader

                        Figures

                        Tables

                        Media

                        Share

                        Share

                        Share this Publication link

                        Share on social media