Multi-level rate scheduler

Patent 5835494 Issued on November 10, 1998. Estimated Expiration Date:

March 27, 2017. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

Bandwidth management and congestion control scheme for multicast ATM networks
Patent #: 5179556
Issued on: 01/12/1993
Inventor: Turner

Broadband input buffered ATM switch
Patent #: 5241536
Issued on: 08/31/1993
Inventor: Grimble, et al.

Bandwidth allocation, transmission scheduling, and congestion avoidance in broadband asynchronous transfer mode networks
Patent #: 5463620
Issued on: 10/31/1995
Inventor: Sriram

Asynchronous transfer mode (ATM) multiplexing process device and method of the broadband integrated service digital network subscriber access apparatus
Patent #: 5499238
Issued on: 03/12/1996
Inventor: Shon

Traffic shaping system with transmit latency feedback for asynchronous transfer mode networks
Patent #: 5515363
Issued on: 05/07/1996
Inventor: Ben-Nun, et al.

ATM cell scheduler
Patent #: 5533020
Issued on: 07/02/1996
Inventor: Byrn, et al.

Apparatus and method of processing bandwidth requirements in an ATM switch Patent #: 5577035
Issued on: 11/19/1996
Inventor: Hayter, et al.

Inventors

Application

No. 825409 filed on 03/27/1997

US Classes:

370/397, Employing logical addressing for routing (e.g., VP or VC)370/232, Based on data flow rate measurement370/399Employing logical addressing for routing (e.g., VP or VC)

Examiners

Primary: Kizou, Hassan

Attorney, Agent or Firm

Blakely, Sokoloff, Taylor & Zafman LLP

Foreign Patent References

2288097 GB. 10/12/1995

International Class

H04L 012/56

Abstract

A method and apparatus are provided for scheduling when each of a plurality of virtual connections supported by a transmit device will be serviced by the transmit device. The transmit device includes a transmission control unit that uses a plurality of calendars to schedule when each of the plurality of virtual connections will be serviced. Virtual connections with faster transfer rates are scheduled using higher granularity calendars, while virtual connections with slower transfer rates are scheduled using lower granularity calendars. Each entry in the calendars is associated with a time interval ("cell slot") during which the transmit device is able to service one virtual connection. During a given cell slot, linked lists associated with the calendar entries that correspond to the cell slot are added to a service queue, and the virtual connection at the head of the service queue is serviced. After a virtual connection is serviced, the next service time for the virtual connection is scheduled by attaching the virtual connection to the head of a linked list associated with the appropriate entry of the appropriate calendar. The appropriate entry is determined by incrementing a fixed-point "desired service time" value that represents the cell slot for which the virtual connection was last scheduled, by a fixed-point inter-gap value that represents the how many cell slots ideally elapse between sequential service times of the virtual connection.

Other References

G. Mercankosk et al, "Multiplexing Spacer Outputs On Cell Emissions," Proceedings of INFOCOM '95 - Conference on Computer Communications, Fourteenth Annual Joint Conference. of the IEEE Computer and Communications Societies, Institute of Electrical and Electronics Engineers, Boston Apr. 2-6, 1995, vol. 3, pp. 49-55 (Apr. 2, 1995)
E. Wallmeier et al., "The Spacing Policer, An Algorithm for Efficient Peak Bit Rate Control in ATM Networks," Proceedings of the International Switching Symposium, vol. 2, pp. 22-26 (Oct. 25, 1992)
PCT Search Report mailed Apr. 14, 1997 for Counterpart PCT Appliction No.PCT US96/19947
"An Event Driven EPRCA", ATM Forum Technical Committee Traffic Management Sub-working Group, Sep. 10, 1994, pp. 1-13
Soung C. Liew, Kevin W. Lu, "Comparison of Buffering Strategies for Asymmetric Packet Switch Modules", IEEE Journal, 1991, vol. 9, No. 3, pp. 428-43