Virtual clock: a new traffic control algorithm for packet switching networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Virtual clock: a new traffic control algorithm for packet switching networks

Full text

Pdf (1.19 MB)

Source

Applications, Technologies, Architectures, and Protocols for Computer Communication archive
Proceedings of the ACM symposium on Communications architectures & protocols table of contents

Philadelphia, Pennsylvania, United States

Pages: 19 - 29

Year of Publication: 1990

ISBN:0-89791-405-8

Also published in ...

Author

L. Zhang

XEROX Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, CA

Sponsor

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 24, Downloads (12 Months): 241, Citation Count: 75

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/99508.99525 What is a DOI?

ABSTRACT

A challenging research issue in high speed networking is how to control the transmission rate of statistical data flows. This paper describes a new algorithm, VirtualClock, for data traffic control in high-speed networks. VirtualClock maintains the statistical multiplexing flexibility of pocket switching while ensuring each data flow its reserved average throughput rate at the same time. The algorithm has been tested through simulation.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
	2	A. Deselous, Contention Probabilities in Packet Switching Networks with Strung lnput Processes, Teletraffc Congress 1988
	3	Ellen L. Hahne. Round Robin Scheduling for Fair Flow Control in Data Communication Networks. PhD thesis, Massachusetts Institute of Technology, December 1986.
	4	R. J ain and S. Routhier. Packet Trains- Measurements and a New Model for Computer Network Traffic. IEEE Journal on Selected Areas in Communicalions, SAC-4(6):986-995, September 1986.
	5	TCP-IP mailing list. TCP-IP mailing list is a special-interest-group mailing list moderated by the Network Information Center (NIC) located at SRI. In TCP-IP mail discussion, there have been numerous observations of malfunctioning hosts in the ARPA Internet.
	6	Utpal Mukherji. A Schedule-Based Approach for Flow-Control in Data Communication Networks. PhD thesis, Massachusetts Institute of Technology, February 1986.
	7	John Nagle, Congestion control in IP/TCP internetworks, ACM SIGCOMM Computer Communication Review, v.14 n.4, p.11-17, October 1984 [doi>10.1145/1024908.1024910]
	8	E. P. Rathgeb. Comparison of Policing Mechanisms for ATM Networks. Submitted to IEEE INFO- COM'90, June 1990.
	9	Jonathan S. Turner. New Directions in Communications (or Which Way to the Information Age?). IEEE Communications Magazine, 24(10):8-15, October 1986.
	10	Lixia Zhang. A New Architecture for Packet Switching Network Protocols. PhD thesis, Massachusetts Institute of Technology, July 1989.

CITED BY 75

	Mark W. Garrett , Martin Vetterli, Joint source/channel coding of statistically multiplexed real-time services on packet networks, IEEE/ACM Transactions on Networking (TON), v.1 n.1, p.71-80, Feb. 1993
	Norival R. Figueira , Joseph Pasquale, Leave-in-Time: a new service discipline for real-time communications in a packet-switching network, ACM SIGCOMM Computer Communication Review, v.25 n.4, p.207-218, Oct. 1995
	Geoffrey G. Xie , Simon S. Lam, Real-time block transfer under a link-sharing hierarchy, IEEE/ACM Transactions on Networking (TON), v.6 n.1, p.30-41, Feb. 1998
	Timothy H. Harrison , David L. Levine , Douglas C. Schmidt, The design and performance of a real-time CORBA event service, ACM SIGPLAN Notices, v.32 n.10, p.184-200, Oct. 1997
	Debanjan Saha , Sarit Mukherjee , Satish K. Tripathi, Carry-over round robin: a simple cell scheduling mechanism for ATM networks, IEEE/ACM Transactions on Networking (TON), v.6 n.6, p.779-796, Dec. 1998
	Ken Chen , Laurent Decreusefond, An approximate analysis of waiting time in multi-class M/G/1/./EDF queues, ACM SIGMETRICS Performance Evaluation Review, v.24 n.1, p.190-199, May 1996
	Micah Adler , Ramesh K. Sitaraman , Arnold L. Rosenberg , Walter Unger, Scheduling time-constrained communication in linear networks, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.269-278, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Zheng Wang , Jon Crowcroft, Analysis of burstiness and jitter in real-time communications, ACM SIGCOMM Computer Communication Review, v.23 n.4, p.13-19, Oct. 1993
	Jörg Liebeherr , Dallas E. Wrege , Domenico Ferrari, Exact admission control for networks with a bounded delay service, IEEE/ACM Transactions on Networking (TON), v.4 n.6, p.885-901, Dec. 1996
	Partho P. Mishra , Hemant Kanakia, A hop by hop rate-based congestion control scheme, ACM SIGCOMM Computer Communication Review, v.22 n.4, p.112-123, Oct. 1992
	Kay Connelly , Andrew A. Chien, FM-QoS: real-time communication using self-synchronizing schedules, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-18, November 15-21, 1997, San Jose, CA
	Approximate sorting of packet-scheduling in high-speed networks, Journal of Computer Science and Technology, v.16 n.4, p.315-328, 7/1/2001
	H. Jonathan Chao , Necdet Uzun, An ATM queue manager handling multiple delay and loss priorities, IEEE/ACM Transactions on Networking (TON), v.3 n.6, p.652-659, Dec. 1995
	Pawan Goyal , Harrick M. Vin , Haichen Chen, Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks, ACM SIGCOMM Computer Communication Review, v.26 n.4, p.157-168, Oct. 1996
	Pawan Goyal , Harrick M. Vin, Generalized guaranteed rate scheduling algorithms: a framework, IEEE/ACM Transactions on Networking (TON), v.5 n.4, p.561-571, Aug. 1997
	D.-I. Kang , R. Gerber , L. Golubchik , J. K. Hollingsworth , M. Saksena, A software synthesis tool for distributed embedded system design, ACM SIGPLAN Notices, v.34 n.7, p.87-95, July 1999
	Micah Adler , Sanjeev Khanna , Rajmohan Rajaraman , Adi Rosén, Time-constrained scheduling of weighted packets on trees and meshes, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.1-12, June 27-30, 1999, Saint Malo, France
	Ramón Cáceres , Peter B. Danzig , Sugih Jamin , Danny J. Mitzel, Characteristics of wide-area TCP/IP conversations, ACM SIGCOMM Computer Communication Review, v.21 n.4, p.101-112, Sept. 1991
	H. Jonathan Chao, Architecture design for regulating and scheduling user's traffic in ATM networks, ACM SIGCOMM Computer Communication Review, v.22 n.4, p.77-87, Oct. 1992
	Theodore Faber , Lawrence H. Landweber , Amarnath Mukherjee, Dynamic Time Windows: packet admission control with feedback, ACM SIGCOMM Computer Communication Review, v.22 n.4, p.124-135, Oct. 1992
	Steve Iatrou , Ioannis Stavrakakis, A dynamic regulation and scheduling scheme for real-time traffic management, IEEE/ACM Transactions on Networking (TON), v.8 n.1, p.60-70, Feb. 2000
	Jae H. Kim , Andrew A. Chien, Rotating combined queueing (RCQ): bandwidth and latency guarantees in low-cost, high-performance networks, ACM SIGARCH Computer Architecture News, v.24 n.2, p.226-236, May 1996
	Rajeev Agrawal , Rene L. Cruz , Clayton Okino , Rajendran Rajan, Performance bonds for flow control protocols, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.310-323, June 1999
	Simon S. Lam , Geoffrey G. Xie, Group priority scheduling, IEEE/ACM Transactions on Networking (TON), v.5 n.2, p.205-218, April 1997
	Ron Cocchi , Deborah Estrin , Scott Shenker , Lixia Zhang, A study of priority pricing in multiple service class networks, ACM SIGCOMM Computer Communication Review, v.21 n.4, p.123-130, Sept. 1991
	Carey L. Williamson , David R. Cheriton, Loss-load curves: support for rate-based congestion control in high-speed datagram networks, ACM SIGCOMM Computer Communication Review, v.21 n.4, p.17-28, Sept. 1991
	Michael A. Bender , Soumen Chakrabarti , S. Muthukrishnan, Flow and stretch metrics for scheduling continuous job streams, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.270-279, January 25-27, 1998, San Francisco, California, United States
	Geoffrey G. Xie , Simon S. Lam, Delay guarantee of virtual clock server, IEEE/ACM Transactions on Networking (TON), v.3 n.6, p.683-689, Dec. 1995
	John Bruno , Eran Gabber , Banu Özden , Abraham Silberschatz, Move-to-rear list scheduling: a new scheduling algorithm for providing QoS guarantees, Proceedings of the fifth ACM international conference on Multimedia, p.63-73, November 09-13, 1997, Seattle, Washington, United States
	Yuming Jiang, Relationship between guaranteed rate server and latency rate server, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.43 n.3, p.307-315, 22 October 2003
	Zoe Antoniou , Ioannis Stavrakakis, An efficient deadline-credit-based transport scheme for prerecorded semisoft continuous media applications, IEEE/ACM Transactions on Networking (TON), v.10 n.5, p.630-643, October 2002
	Ion Stoica , Hui Zhang, Providing guaranteed services without per flow management, ACM SIGCOMM Computer Communication Review, v.29 n.4, p.81-94, Oct. 1999
	Sandeep Sibal , Antonio DeSimone, Controlling alternate routing in general-mesh packet flow networks, ACM SIGCOMM Computer Communication Review, v.24 n.4, p.168-179, Oct. 1994
	Ron Cocchi , Scott Shenker , Deborah Estrin , Lixia Zhang, Pricing in computer networks: motivation, formulation, and example, IEEE/ACM Transactions on Networking (TON), v.1 n.6, p.614-627, Dec. 1993
	Rauf Izmailov , Duan-Shin Lee , Bhaskar Sengupta, Design and analysis of a congestion-free overlay on a high-speed network, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.970-980, Dec. 1997
	Gianluca Rizzo , Jean-Yves Le Boudec, "Pay bursts only once" does not hold for non-FIFO guaranteed rate nodes, Performance Evaluation, v.62 n.1-4, p.366-381, October 2005
	Kyung D. Ryu , Jeffrey K. Hollingsworth , Peter J. Keleher, Efficient network and I/O throttling for fine-grain cycle stealing, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.3-3, November 10-16, 2001, Denver, Colorado
	Seok-Kyu Kweon , Kang G. Shin, Real-Time Transport of MPEG Video with a Statistically Guaranteed Loss Ratio in ATM Networks, IEEE Transactions on Parallel and Distributed Systems, v.12 n.4, p.387-403, April 2001
	Mansour J. Karam , Fouad A. Tobagi, Analysis of delay and delay jitter of voice traffic in the internet, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.40 n.6, p.711-726, 20 December 2002
	Chia-Tai Chan , Pi-Chung Wang , Yaw-Chung Chen, An efficient traffic control scheme for TCP over ATM GFR services, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.5, p.645-662, 5 April 2002
	Zhenhai Duan , Zhi-Li Zhang , Yiwei Thomas Hou , Lixin Gao, A Core Stateless Bandwidth Broker Architecture for Scalable Support of Guaranteed Services, IEEE Transactions on Parallel and Distributed Systems, v.15 n.2, p.167-182, February 2004
	Steve Muir , Jonathan Smith, An operating system architecture for network processors, Proceedings of the 2005 symposium on Architecture for networking and communications systems, October 26-28, 2005, Princeton, NJ, USA
	Amitava Raha , Sanjay Kamat , Xiaohua Jia , Wei Zhao, Using Traffic Regulation to Meet End-to-End Deadlines in ATM Networks, IEEE Transactions on Computers, v.48 n.9, p.917-935, September 1999
	Sriram Ramabhadran , Joseph Pasquale, Stratified round Robin: a low complexity packet scheduler with bandwidth fairness and bounded delay, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany
	Prasanna Chaporkar , Joy Kuri, A network architecture for providing per-flow delay guarantees with scalable core, Journal of High Speed Networks, v.12 n.3,4, p.87-109, 01/01/2002
	Albert M. K. Cheng , Sudhir M. Rao, Real-Time Traffic Scheduling and Routing in Packet-Switched Networks Using a Least-Laxity-First Strategy, Journal of VLSI Signal Processing Systems, v.34 n.1-2, p.139-148, May-June 2003
	Timothy Sherwood , George Varghese , Brad Calder, A pipelined memory architecture for high throughput network processors, ACM SIGARCH Computer Architecture News, v.31 n.2, May 2003
	Pawan Goyal , Harrick M. Vin , Haichen Cheng, Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.690-704, Oct. 1997
	Pawan Goyal , Simon S. Lam , Harrick M. Vin, Determining end-to-end delay bounds in heterogeneous networks, Multimedia Systems, v.5 n.3, p.157-163, May 1997
	Qin Zheng , Kang G. Shin, Synchronous Bandwidth Allocation in FDDI Networks, IEEE Transactions on Parallel and Distributed Systems, v.6 n.12, p.1332-1338, December 1995
	Wei Jin , Jeffrey S. Chase , Jasleen Kaur, Interposed proportional sharing for a storage service utility, ACM SIGMETRICS Performance Evaluation Review, v.32 n.1, June 2004
	Song Wang , Yu-Chung Wang , Kwei-Jay Lin, Integrating Priority with Share in the Priority-Based Weighted Fair Queuing Scheduler for Real-Time Networks, Real-Time Systems, v.22 n.1-2, p.119-149, Jan.-March 2002
	Wei Liu , Xiang Chen , Yuguang Fang , John M. Shea, Courtesy Piggybacking: Supporting Differentiated Services in Multihop Mobile Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.3 n.4, p.380-393, October 2004
	Dong-In Kang , Richard Gerber , Manas Saksena, Parametric Design Synthesis of Distributed Embedded Systems, IEEE Transactions on Computers, v.49 n.11, p.1155-1169, November 2000
	Chih-Min Chao , Yu-Chee Tseng , Li-Chun Wang, Dynamic Bandwidth Allocation for Multimedia Traffic with Rate Guarantee and Fair Access in WCDMA Systems, IEEE Transactions on Mobile Computing, v.4 n.5, p.420-429, September 2005
	Ajay Gulati , Peter Varman, Lexicographic QoS scheduling for parallel I/O, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Yuming Jiang, Delay bounds for a network of guaranteed rate servers with FIFO aggregation, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.40 n.6, p.683-694, 20 December 2002
	Chengzhi Li , Edward W. Knightly, Schedulability criterion and performance analysis of coordinated schedulers, IEEE/ACM Transactions on Networking (TON), v.13 n.2, p.276-287, April 2005
	F. Németh , P. Barta , R. Szabó , J. Bíró, Network internal traffic characterization and end-to-end delay bound calculus for generalized processor sharing scheduling discipline, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.48 n.6, p.910-940, 19 August 2005
	Hyo Jung Song , Andrew A. Chien, Feedback-Based Synchronization in System Area Networks for Cluster Computing, IEEE Transactions on Parallel and Distributed Systems, v.16 n.10, p.908-920, October 2005
	Fei Long , Gang Feng , Chee Kheong Siew, Channel states dependent fair service: a new packet scheduling algorithm for CDMA, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.49 n.2, p.201-216, 5 October 2005
	Josep M. Blanquer , Banu Özden, Fair queuing for aggregated multiple links, ACM SIGCOMM Computer Communication Review, v.31 n.4, p.189-197, October 2001
	S. De Vuyst , S. Wittevrongel , D. Fiems , H. Bruneel, Controlling the delay trade-off between packet flows using multiple reserved places, Performance Evaluation, v.65 n.6-7, p.484-511, June, 2008
	Rick Wilder , K. K. Ramakrishnan , Allison Mankin, Dynamics of congestion control and avoidance of two-way traffic in an OSI testbed, ACM SIGCOMM Computer Communication Review, v.21 n.2, p.43-58, April 1991
	Hazem Hamed , Ehab Al-Shaer, Dynamic rule-ordering optimization for high-speed firewall filtering, Proceedings of the 2006 ACM Symposium on Information, computer and communications security, March 21-24, 2006, Taipei, Taiwan
	Yong Cui , Jianping Wu , Ke Xu, Precomputation for intra-domain QoS routing, Computer Networks and ISDN Systems, v.47 n.6, p.923-937, 22 April 2005
	Sriram Ramabhadran , Joseph Pasquale, The Stratified Round Robin scheduler: design, analysis and implementation, IEEE/ACM Transactions on Networking (TON), v.14 n.6, p.1362-1373, December 2006
	Antonio DeSimone, Generating burstiness in networks: a simulation study of correlation effects in networks of queues, ACM SIGCOMM Computer Communication Review, v.21 n.1, p.24-31, Jan. 1991
	Greg M. Berstein, Reserved bandwidth and reservationless traffic in rate allocating servers, ACM SIGCOMM Computer Communication Review, v.23 n.3, p.6-25, July 1993
	Daojun Xue , Yang Qin , Chee Kheong Siew, Performance analysis of a novel traffic scheduling algorithm in slotted optical networks, Computer Communications, v.30 n.18, p.3559-3571, December, 2007
	S. De Vuyst , S. Wittevrongel , H. Bruneel, Place reservation: Delay analysis of a novel scheduling mechanism, Computers and Operations Research, v.35 n.8, p.2447-2462, August, 2008
	Reu-Ching Chen , Chen-Sung Chang, Energy Cost Optimization by Adequate Transmission Rate Dividing in Wireless Communication System, Informatica, v.19 n.2, p.191-200, April 2008
	Jae W. Lee , Man Cheuk Ng , Krste Asanovic, Globally-Synchronized Frames for Guaranteed Quality-of-Service in On-Chip Networks, ACM SIGARCH Computer Architecture News, v.36 n.3, p.89-100, June 2008
	Spiridon Bakiras , Feng Wang , Dimitris Papadias , Mounir Hamdi, Vertical dimensioning: A novel DRR implementation for efficient fair queueing, Computer Communications, v.31 n.14, p.3476-3484, September, 2008
	Maxim Podlesny , Sergey Gorinsky, Rd network services: differentiation through performance incentives, ACM SIGCOMM Computer Communication Review, v.38 n.4, October 2008