Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
2006-05-30
2006-05-30
Nguyen, Chau (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
C370S414000, C370S417000
Reexamination Certificate
active
07054267
ABSTRACT:
Packets are scheduled for transmission over a communication link in a network, using a Largest Weighted Delay First (LWDF) scheduling policy. A delay measure Wi, i=1, 2, . . . N, is computed for each of N packets, each associated with a corresponding one of N data flows and located in a head position in a corresponding one of N data flow queues. The computed delay measures are then weighted using a set of positive weights α1, α2, . . . , αN. The packet having the largest weighted delay Wi/αiassociated therewith is then selected for transmission. In an embodiment configured to meet a quality of service (QoS) requirement specified in terms of a deadline Tiand an allowed deadline violation probability δi, e.g., a requirement specified by P(Wi>Ti)≦δi, the weights αiin the set of positive weights α1, α2, . . . , αNmay be given by αi=−Ti/log δi. The invention can also be used to meet other types of QoS requirements, including, e.g., requirements based on packet loss probabilities. For example, the QoS guarantee may be defined for a delay measure in the form of queue length Qi, i=1, 2, . . . N, and an allowed queue length violation probability δi. In such an embodiment, the QoS requirement is specified by P(Qi>Hi)≦δi, and the weights αiin the set of positive weights α1, α2, . . . , αNmay be given by αi=−Hi/log δi, where Hirepresents an upper bound on the length of the queue.
REFERENCES:
patent: 5796719 (1998-08-01), Peris et al.
patent: 5886980 (1999-03-01), Zheng
patent: 5917822 (1999-06-01), Lyles et al.
patent: 6009077 (1999-12-01), Firoiu et al.
patent: 6091709 (2000-07-01), Harrison et al.
patent: 6092115 (2000-07-01), Choudhury et al.
patent: 6104700 (2000-08-01), Haddock et al.
patent: 6108307 (2000-08-01), McConnell et al.
patent: 6201793 (2001-03-01), Chen et al.
patent: 6226266 (2001-05-01), Galand et al.
patent: 6317416 (2001-11-01), Giroux et al.
patent: 6359861 (2002-03-01), Sui et al.
patent: 6408006 (2002-06-01), Wolff
patent: 6452933 (2002-09-01), Duffield et al.
patent: 6490248 (2002-12-01), Shimojo
patent: 6532213 (2003-03-01), Chiussi et al.
patent: WO 97/14240 (1997-04-01), None
L. Georgiadis, R. Guerin and A. Parekh, “Optimal multiplexing on a single link: delay and buffer requirements,” IEEE Transactions on Information Theory, 43(5): 1518-1535, 1997.
J. Liebeherr, D. Wrege, and D. Ferrari, “Exact admission control for networks with a bounded delay service,” IEEE/ACM Transactions on Networking, 4(6):885-901, 1996.
M. Andrews, L. Zhang, “Minimizing End-to-End Delay in High-Speed Networks with a Simple Coordinated Schedule,” IEEE INFOCOM'99, pp. 380-388, 1999.
A. Birman et al., “An Optimal Service Policy for Buffer Systems,” Journal of the Association Computing Machinery (JACM), vol. 42, No. 3, pp. 641-657, 1995.
H.R. Gail et al., “Buffer Size Requirements Under Longest Queue First,” Performance Evaluation, vol. 18, pp. 133-140, 1993.
T. Marosits et al., “Performance Evaluation of a General Traffic Control Framework in ATM Networks,” 18th IEEE International Performance, Computing, and Communications Conference (IPCCC'99), Scottsdale, Arizona, pp. 240-249, Feb. 1999.
T-G. Kwon et al., “Scheduling Algorithm for Real-Time Burst Traffic Using Dynamic Weighted Round Robin,” Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS '98),Monterey, California, pp. VI-506-VI-509, May 1998.
Ramanan Kavita
Stoylar Aleksandr
Hyun Soon D.
Lucent Technologies - Inc.
Nguyen Chau
LandOfFree
Method and apparatus for scheduling traffic to meet quality... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for scheduling traffic to meet quality..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for scheduling traffic to meet quality... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3605809