Transmit scheduler for an asynchronous transfer mode network and method of operation

• US 5,991,867 A
• Filed: 09/12/1996
• Issued: 11/23/1999
• Est. Priority Date: 09/12/1996
• Status: Expired due to Term

• Current Assignee: Sagemcom Broadband SAS (Sagemcom Holding SAS)
• Original Assignee: Efficient Networks, Inc. (Siemens AG)
• Inventors: Fosmark, Klaus S.
• Primary Examiner(s): An, Meng-Ai T.
• Assistant Examiner(s): Nguyen, Dzung C.
• Application Number:
  US08/713,211
• Time in Patent Office: 1,167 Days
• Field of Search: 395/200.76, 395/200.56, 395/800.16, 395/800.42, 370/390, 370/382, 370/397, 370/395, 370/230, 370/232, 370/414, 370/413, 370/16, 370/18, 712/32, 712/33, 712/39, 712/225, 712/229, 709/230, 709/234
• US Class Current: 712/16
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A transmit scheduler and method of operation are provided for an asynchronous transfer mode network. The transmit scheduler is operable to write data to and read data from a scheduler table and a virtual channel identifier ("VCI") table in order to schedule cells for virtual channels. The transmit scheduler calculates a location in the scheduler table in which to schedule a cell for a current virtual channel and determines whether a cell for a prior virtual channel is scheduled in the calculated location in the scheduler table. The transmit scheduler then schedules the cell for the current virtual channel at the calculated location in the scheduler table. If a cell for a prior virtual channel was scheduled in the calculated location in the scheduler table, the transmit scheduler writes a pointer into a next pointer field of a record for the current virtual channel in the VCI table, where the pointer provides a link to a record for the prior virtual channel in the VCI table. The transmit scheduler is thereby operable to build linked lists beginning at each location in the scheduler table in which cells for more than one virtual channel are calculated to be scheduled.

Claims

1. A transmit scheduler for an asynchronous transfer mode network:

the transmit scheduler operable to write data to and read data from a scheduler table and a virtual channel identifier (VCI) table in order to schedule cells for virtual channels by;

using a first pointer and a second pointer to maintain position within the scheduler table, the first pointer indicating a current location and the second pointer indicating a virtual location;

determining from the scheduler table which virtual channel is currently scheduled for processing by a segmenter;

calculating a location in the scheduler table in which to schedule a cell for the current virtual channel;

determining whether a cell for a prior virtual channel is scheduled in the calculated location in the scheduler table;

scheduling the cell for the current virtual channel at the calculated location in the scheduler table; and

writing a pointer into a next pointer field of a record for the current virtual channel in the VCI table if a cell for a prior virtual channel was scheduled in the calculated location in the scheduler table, the pointer providing a link to a record for the prior virtual channel in the VCI table;

such that the transmit scheduler is operable to build linked lists beginning at each location in the scheduler table in which cells for more than one virtual channel are calculated to be scheduled.

2. The transmit scheduler of claim 1, wherein the transmit scheduler increments the second pointer when a cell is placed into a FIFO queue by the segmenter.

3. The transmit scheduler of claim 1, wherein the transmit scheduler increments the second pointer when a cell is placed into a FIFO queue by the segmenter, but does not increment the second pointer when a cell is placed into the FIFO queue if the second pointer is more than a defined distance ahead of the first pointer.

4. The transmit scheduler of claim 1, wherein the transmit scheduler increments the second pointer when a cell is placed into a FIFO queue by the segmenter and increments the first pointer to skip locations holding a value of zero until a location holding a scheduled virtual channel is reached in order to catch the second pointer when the second pointer is ahead.

5. An adapter for an asynchronous transfer mode network, comprising:

a memory operable to hold a scheduler table, a virtual channel identifier (VCI) table, and a FIFO queue, the scheduler table having a plurality of locations for scheduling cells for virtual channels, the VCI table having a record for each of a plurality of active virtual channels, and the FIFO queue having cells for transmission across an asynchronous transfer mode network; and

a segmenter coupled to and operable to access the memory, the segmenter further operable to retrieve data, build cells based upon the retrieved data, and place the cells into the FIFO queue for transmission across the asynchronous transfer mode network; and

the segmenter comprising a transmit scheduler operable to write data to and read data from the scheduler table and the VCI table in order to schedule cells for virtual channels by;

using a first pointer and a second pointer to maintain position within the scheduler table, the first pointer indicating a current location and the second pointer indicating a virtual location;

determining from the scheduler table which virtual channel is currently scheduled for processing by the segmenter;

calculating a location in the scheduler table in which to schedule a cell for the current virtual channel;

determining whether a cell for a prior virtual channel is scheduled in the calculated location in the scheduler table;

scheduling the cell for the current virtual channel at the calculated location in the scheduler table; and

writing a pointer into a next pointer field of a record for the current virtual channel in the VCI table if a cell for a prior virtual channel was scheduled in the calculated location in the scheduler table, the pointer providing a link to a record for the prior virtual channel in the VCI table;

such that the transmit scheduler is operable to build linked lists beginning at each location in the scheduler table in which cells for more than one virtual channel are calculated to be scheduled.

6. The adapter card of claim 5, wherein the transmit scheduler increments the second pointer when a cell is placed into the FIFO queue by the segmenter.

7. The adapter card of claim 5, wherein the transmit scheduler increments the second pointer when a cell is placed into the FIFO queue by the segmenter, but does not increment the second pointer when a cell is placed into the FIFO queue if the second pointer is more than a defined distance ahead of the first pointer.

8. The adapter card of claim 5, wherein the transmit scheduler increments the second pointer when a cell is placed into the FIFO queue by the segmenter and increments the first pointer to skip locations holding a value of zero until a location holding a scheduled virtual channel is reached in order to catch the second pointer when the second pointer is ahead.

9. The adapter card of claim 5, wherein the segmenter is implemented on an application specific integrated circuit, and the memory is a static random access memory device.

10. A method of operation for a transmit scheduler for an asynchronous transfer mode network, comprising:

using a first pointer and a second pointer to maintain position within a scheduler table, the first pointer indicating a current location and the second pointer indicating a virtual location;

determining a virtual channel currently scheduled for processing from the scheduler table;

calculating a location in a scheduler table in which to schedule a cell for the current virtual channel;

determining whether a cell for a prior virtual channel is scheduled in the calculated location in the scheduler table;

scheduling the cell for the current virtual channel at the calculated location in the scheduler table; and

writing a pointer into a next pointer field of a record for the current virtual channel in a virtual channel identifier (VCI) table if a cell for a prior virtual channel was scheduled in the calculated location in the scheduler table, the pointer providing a link to a record for the prior virtual channel in the VCI table;

such that linked lists are built beginning at each location in the scheduler table in which cells for more than one virtual channel are calculated to be scheduled.

11. The method of claim 10, wherein using a first pointer and a second pointer to maintain position comprises incrementing the second pointer when a cell is placed into a FIFO queue for transmission across the asynchronous transfer mode network.

12. The method of claim 10, wherein using a first pointer and a second pointer to maintain position comprises incrementing the second pointer when a cell is placed into a FIFO queue for transmission across the asynchronous transfer mode network, but not incrementing the second pointer when a cell is placed into the FIFO queue if the second pointer is more than a defined distance ahead of the first pointer.

13. The method of claim 10, wherein using a first pointer and a second pointer to maintain position comprises incrementing the second pointer when a cell is placed into a FIFO queue for transmission across the asynchronous transfer mode network and incrementing the first pointer to skip locations holding a value of zero until a location holding a scheduled virtual channel is reached in order to catch the second pointer when the second pointer is ahead.

14. The method of claim 10, wherein the method is implemented by an application specific integrated circuit.