Abstract Claims Description Full Text

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