Analysis of Distributed DDQ for QoS Router

ETRI Journal

关键词: router;    traffic control;    real-time;    packet scheduler;    queuing;    Quality-of-service;   

Others  :  1185465
DOI  :  10.4218/etrij.06.0104.0193

【 摘 要 】

In a packet switching network, congestion is unavoidable and affects the quality of real-time traffic with such problems as delay and packet loss. Packet fair queuing (PFQ) algorithms are well-known solutions for quality-of-service (QoS) guarantee by packet scheduling. Our approach is different from previous algorithms in that it uses hardware time achieved by sampling a counter triggered by a periodic clock signal. This clock signal can be provided to all the modules of a routing system to get synchronization. In this architecture, a variant of the PFQ algorithm, called digitized delay queuing (DDQ), can be distributed on many line interface modules. We derive the delay bounds in a single processor system and in a distributed architecture. The definition of traffic contribution improves the simplicity of the mathematical models. The effect of different time between modules in a distributed architecture is the key idea for understanding the delay behavior of a routing system. The number of bins required for the DDQ algorithm is also derived to make the system configuration clear. The analytical models developed in this paper form the basis of improvement and application to a combined input and output queuing (CIOQ) router architecture for a higher speed QoS network.

   

【 参考文献 】

• [1]John B. Nagle, "On Packet Switches with Infinite Storage," IEEE Trans. on Comm., vol. 35, iss. 4, Apr. 1987, pp. 435-438.
• [2]Bob Branden, David Clark, and Scott Shenker, Integrated Services Architecture, IETF RFC 1633, June 1994.
• [3]Abhay K. Parekh and Robert G. Gallager, "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks : the Single-Node Case," IEEE/ACM Trans. on Networking, vol. 1, no. 3, 1993, pp. 344-357.
• [4]Lixia Zhang, "VirtualClock: A New Traffic Control Algorithm for Packet Switching Network," ACM SIGCOMM ‘90, 1990, pp. 19-29.
• [5]Norival R. Figueira and Joseph Pasquale, "An Upper Bound on Delay for the VirtualClock Service Discipline," IEEE/ACM Trans. on Networking, vol. 3, no. 4, Aug. 1995, pp. 399-408.
• [6]S. Jamaloddin Golestani, "A Self-Clocked Fair Queuing Scheme for Broadband Applications," IEEE INFOCOM ‘94, 1994, pp. 636-646.
• [7]Jon C. R. Bennett and Hui Zhang, "WF2Q : Worst-Case Fair Weighted Fair Queuing," IEEE INFOCOM ’96, Mar. 1996, pp. 120-128.
• [8]Shun Y. Cheung and Corneliu S. Pencea, "BSFQ: Bin Sort Fair Queuing," IEEE INFOCOM ’02, 2002, pp. 1640-1649.
• [9]M. Shreedhar and G. Varghese, "Efficient Fair Queuing Using Deficit Round Robin," ACM SIGCOMM ’95, 1995, pp. 231-242.
• [10]S. Moon, J. Rexford, and K. Shin, "Scalable Hardware Priority Queue Architectures for High-Speed Packet Switches," IEEE Trans. on Computer, vol. 49, no. 11, 2000, pp. 1215-1227.
• [11]P. Kuacharoen, M. Shalan, and V. Mooney, "A Configurable Hardware Scheduler for Real-Time Systems," Int’l Conf. on Engineering of Reconfigurable Systems and Algorithms (ERSA’03), 2003, pp. 96-101.
• [12]Chao and Uzun, "An ATM Queue Manager with Multiple Delay and Loss Priorities," IEEE GLOBECOM ‘92, 1992, pp. 308-313.
• [13]Kicheon Kim, "Flow Aggregation of Rage Controlled Round-Robin Scheduler," ETRI J., vol. 26, no. 4, Aug. 2004, pp. 351-359.
• [14]Kicheon Kim, "Distributed Digitized Delay Queuing (DDQ) for Large Scale QoS Router," Int’l Conf. on Parallel and Distributed Processing Techniques and Applications (PDPTA’04), June 21-24, 2004, pp. 1183-1190.
• [15]Bob Branden, Lixia Zhang, Steve Berson, Shai Herzog, and Sugih Jamin, "Resource ReSerVation Protocol (RSVP) ? Version 1 Functional Specification," IETF RFC 2205, Sept. 1997.
• [16]Kicheon Kim and David Hutchison, "Flowmeter for QoS Provision in Packet Switched Network," IEE Electronics Lett., vol. 34, no. 1, 1998, pp. 21-22.
• [17]Fabio M. Chiussi, Andrea Francini, and Joseph G.. Kneuer, "Implementing Fair Queuing in ATM Switches ? Part 2: The Logarithmic Calendar Queue," IEEE GLOBECOM ’97, 1997, pp. 519-525.
• [18]Anujan Varma and Dimitrios Stiliadis, "Hardware Implementation of Fair Queuing Algorithms for Asynchronous Transfer Mode Networks," IEEE Comm. Magazine, Dec. 1997, pp. 54-68.
• [19]Shang-Tse Chuang, Ashish Goel, Nick McKeown, and Balaji Prabhakar, "Matching Output Queuing with a Combined Input/Output-Queued Switch," IEEE J. on Selected Areas in Comm., June 1999, pp. 1030-1039.