Implementation and performance measurements of a delay-bounded HPD algorithm in an ALTQ-based router

ABSTRACT

In this paper we show the first working implementation of an adaptive, measurement-based scheduling algorithm called delay-bounded hybrid proportional delay (DBHPD) in a FreeBSD based ALTQ prototype router. We describe how we have implemented DBHPD and discuss what kind of difficulties were encountered in the implementation. We present measurement results of the DBHPD implementation with FTP, HTTP, Video Streaming and VoIP traffic in underload, overload and heavy overload conditions. We show that the algorithm operates well according to the theoretical model and preserves the desired delay-bound as well as the delay ratios between the classes. We also compare DBHPD to an existing Class-Based-Queueing (CBQ) algorithm that is widely used both in research and in the industry. We show that DBHPD is able to achieve at least as good link utilization as CBQ and in addition results in much better and predictable differentiation in terms of delays and more controlled packet losses.

REFERENCES

• 1: J. Antila and M. Luoma. Scheduling and quality differentiation in differentiated services. In Proceedings of MIPS 2003, pages 119--130, November 2003.
• 2: J. Antila and M. Luoma. Adaptive scheduling for improved quality differentiation. In Proceedings of MIPS 2004, November 2004.
• 3: J. Antila and M. Luoma. Robust delay estimation of an adaptive scheduling algorithm. In Proceedings of QoS-IP 2005, February 2005.
• 4: K. Cho. Managing traffic with ALTQ. In Proceedings of USENIX 1999 Annual Technical Conference. USENIX, June 1999.
• 5: K. Cho. Fitting theory into reality in the altq case. In Proceedings of ASIA BSD conference. USENIX, March 2004.
• 6: N. Christin, J. Liebeherr, and T. Abdelzaher. A quantitative assured forwarding service. In Proceedings of IEEE INFOCOM 2002, volume 2, pages 864--873, New York, NY, June 2002.
• 7: Kimberly C. Claffy , George C. Polyzos , Hans-Werner Braun, Application of sampling methodologies to network traffic characterization, Conference proceedings on Communications architectures, protocols and applications, p.194-203, September 13-17, 1993, San Francisco, California, United States
• 8: Constantinos Dovrolis , Dimitrios Stiliadis , Parameswaran Ramanathan, Proportional differentiated services: delay differentiation and packet scheduling, IEEE/ACM Transactions on Networking (TON), v.10 n.1, p.12-26, February 2002 [doi>10.1109/90.986503]
• 9: Sally Floyd , Van Jacobson, Link-sharing and resource management models for packet networks, IEEE/ACM Transactions on Networking (TON), v.3 n.4, p.365-386, Aug. 1995 [doi>10.1109/90.413212]
• 10: M. Luoma and J. Antila. Differentiation of the internet traffic. In Proceedings of ICN 2004, February 2004.
• 11: Abhay K. Parekh , Robert G. Gallagher, A generalized processor sharing approach to flow control in integrated services networks: the multiple node case, IEEE/ACM Transactions on Networking (TON), v.2 n.2, p.137-150, April 1994 [doi>10.1109/90.298432]
• 12: M. Shreedhar , George Varghese, Efficient fair queueing using deficit round robin, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.231-242, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 13: Ion Stoica , Hui Zhang , T. S. Eugene Ng, A hierarchical fair service curve algorithm for link-sharing, real-time and priority services, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.249-262, September 14-18, 1997, Cannes, France

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
adaptive scheduling, implementation, measurements