High speed weighted fair queuing system for ATM switches

Details High speed weighted fair queuing system for ATM switches High speed weighted fair queuing system for ATM switches

1998-09-15

2004-12-07

Hsu, Alpus H. (Department: 2665)

Multiplex communications

Data flow congestion prevention or control

Control of data admission to the network

C370S395210

Reexamination Certificate

active

06829218

ABSTRACT:

FIELD OF THE INVENTION
The invention relates generally to asynchronous transfer mode (ATM) networks and, more particularly, to high speed weighted queuing systems for ATM switches.
BACKGROUND
Weighted fair queuing, (also known as packetized general processor sharing (PGPS), may be come important in the next generation of ATM switching system and routers in order to fairly share bandwidth while allowing for a guaranteed minimum delay to individual connections sharing a particular transmission facility. However, to date, the implementation of weighted fair queuing algorithms have been problematic and difficult to scale to a large number of connections. For example, in conventional weighted fair queuing, the complexity of an ideal implementation is 0(N)+0(logN) where N is the number of circuits, 0(N) represents the recalculation for all head-of-line packets for all circuits, and 0(logN) is the amount of calculations involved in resorting all of the reference finishing times. The next generation of ATM switches is expected to include tens of thousands of connections and operate at multi-gigabit rates. Accordingly, a scalable, highly efficient implementation of a weighted fair queuing algorithm is necessary.
SUMMARY OF THE INVENTION
The present invention provides improved algorithms for performing queuing in an ATM switch. In particular, the invention provides a highly efficient implementation of a weighted fair queuing algorithm in an ATM switch where the packets are of a fixed size. Although some important approximations are made in the proposed implementation, all of the properties of an ideal weighted fair queuing algorithm are preserved. The sorting algorithms in accordance with the present invention are advantageous in that it is possible to maintain appropriate servicing of connections without sorting all of the individual connections. This may be accomplished by presorting each of the individual virtual circuit connections into a finite number of predetermined bins according to a weight associated with the connection. Thereafter, only the bins need be sorted without having to sort each of the individual connections. Accordingly, the invention is suitable for implementations having transmission speeds of multiple gigabits-per-second.


REFERENCES:
patent: 4616359 (1986-10-01), Fontenot
patent: 5179556 (1993-01-01), Turner
patent: 5280470 (1994-01-01), Buhrke et al.
patent: 5457687 (1995-10-01), Newman
patent: 5535201 (1996-07-01), Zheng
patent: 5541926 (1996-07-01), Saito et al.
patent: 5577035 (1996-11-01), Hayter et al.
patent: 5583861 (1996-12-01), Holden
patent: 5675576 (1997-10-01), Kalampoukas et al.
patent: 5689508 (1997-11-01), Lyles
patent: 5694554 (1997-12-01), Kawabata et al.
patent: 5737313 (1998-04-01), Kolarov et al.
patent: 5737314 (1998-04-01), Hatono et al.
patent: 5748614 (1998-05-01), Wallmeier
patent: 5754530 (1998-05-01), Awdeh et al.
patent: 5802040 (1998-09-01), Park et al.
patent: 5805577 (1998-09-01), Jain et al.
patent: 5805599 (1998-09-01), Mishra et al.
patent: 5812527 (1998-09-01), Kline et al.
patent: 5864540 (1999-01-01), Bonomi et al.
patent: 5901147 (1999-05-01), Joffe
patent: 5933425 (1999-08-01), Iwata
patent: 5949789 (1999-09-01), Davis et al.
patent: 5956340 (1999-09-01), Afek et al.
patent: 5959993 (1999-09-01), Varma et al.
patent: 6038217 (2000-03-01), Lyles
patent: 6064651 (2000-05-01), Rogers et al.
patent: 6064677 (2000-05-01), Kappler et al.
patent: 6069872 (2000-05-01), Bonomi et al.
patent: 6072775 (2000-06-01), Ikeda
patent: 6091730 (2000-07-01), Biegaj et al.
patent: 6198723 (2001-03-01), Parruck et al.
patent: 6408005 (2002-06-01), Fan et al.
U.S. patent application Ser. No. 08/299,472, Wong, filed Aug. 31, 1994.
U.S. patent application Ser. No. 09/033,030, He et al., filed Mar. 2, 1998.
Slobodan S. Petrovic, “ABR Service in ATM Networks: Performance Comparison between Adaptive Stochastice and ERICA Flow Control Schemes with Guaranteed Minimum Cell Rate,” Proceedings 23rdAnnual Conference on Local Networks, IEEE, 1998.
W. Melody Moh and Madhavi Hegde, “Evaluation of ABR Congestion Control Protocols for ATM LAN and WAN,” Proceedings of the 1996 International Conference on Network Protocol, IEEE, 1996.
Chen-Khong Tham and Wee-Seng Soh, “Multi-service Connection Admission Control using Modular Neural Networks,” Proceedings of the 1998 17thAnnual IEEE Conference on Computer Communication, INFOCOM, IEEE, 1998.
European Search Report dated Nov. 18, 2002.
Fabio M. Chiussi and Andrea Francini,Implementing Fair Queuing in ATM Switches: The Discrete Rate Approach, Proceedings of the IEEE INFOCOM '98, Mar. 29, 1998.
Jon C.R. Bennett, and Hui Zhang,Hierarchical Packet Fair Queuing Algorithms, IEEE/ACM Transactions on Networking, vol. 5. No. 5, Oct. 1997.
Hideyuki Shimonishi, and Hiroshi Suzuki,Performance Analysis of Weighted Round Robin Cell Scheduling and Its Improvement in ATM Networks, IEICE Trans. Commun. vol. E81-B No. 5, May 1998.
Fabio M. Chiussi, Andrea Francini, and Joseph G. Kneuer,Implementing Fair Queueing in ATM Switches—Part 2: Logarithmic Calendar Queue, Global Telecommunications Conference, Nov., 1997.
Andreas Ermedahl, Hans Hansson, Mikael Sjödin,Response-Time Guarantees in ATM Networks, 1997 IEEE.
Mei-Hwey Hou and Chienhua Chen,Service Disciplines for Guaranteed Performance Service, IEEE, 1997.

Affiliated with

Also associated with

Rating

High speed weighted fair queuing system for ATM switches does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with High speed weighted fair queuing system for ATM switches, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High speed weighted fair queuing system for ATM switches will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3325845