Asynchronous transfer mode cell processing system with scoreboard scheduling

• US 6,359,891 B1
• Filed: 06/13/2000
• Issued: 03/19/2002
• Est. Priority Date: 05/09/1996
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Conexant Systems Incorporated (Synaptics Incorporated)
• Inventors: Lussier, Daniel J., Bergantino, Paul V.
• Primary Examiner(s): YAO, KWANG BIN
• Application Number:
  US09/592,341
• Time in Patent Office: 644 Days
• Field of Search: 370/395, 370/396, 370/397, 370/398, 370/399, 370/409, 370/410, 370/412, 370/415, 370/428, 370/429, 370/442, 370/443, 370/444, 370/458, 370/459, 370/460
• US Class Current: 370/398
• CPC Class Codes: H04L 2012/5616 Terminal equipment, e.g. codecs, synch.
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5672 Multiplexing, e.g. coding, scrambling
• 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

Methods and apparatus for processing cells in an asynchronous transfer mode (ATM) communication system. A group of bits comprises a primary scoreboard indicative of the scheduling status for cell time slots in a periodic container of cells, with each bit indicating the availability of a corresponding cell time slot. A connection identifier (ID) table is maintained with each location in the table corresponding to one of the cell time slots and thus a single primary scoreboard bit. A cell scheduling instruction specifies a connection ID for a virtual connection on an ATM transmission link. A processor searches the primary scoreboard until a bit corresponding to an available cell time slot is located, reserves the located cell slot by setting the corresponding bit, and stores the connection ID in the corresponding location in the connection ID table. A cell servicing instruction specifies an address in the connection ID table. The processor receives the servicing instruction, retrieves the corresponding primary scoreboard bit, constructs or retrieves a cell for transmission in the slot if the bit was set, and then clears the bit so the slot is available for subsequent scheduling requests. A secondary scoreboard may be used to bound the primary scoreboard search time. The secondary scoreboard includes a bit for each block of primary scoreboard bits. The bit indicates whether the primary scoreboard block includes an available time slot. Portions of the primary scoreboard with no available slots thus need not be searched. Separate tunnel control primary scoreboards may be used in conjunction with a master primary scoreboard to support virtual path tunneling.

Claims

1. A communication scheduling system comprising:

a memory configured to store primary information elements that correspond to communication time slots and that correspond to memory locations; and

processing circuitry configured to select one of the primary information elements having a corresponding one of the communication time slots and a corresponding one of the memory locations, modify the selected one of the primary information elements to reserve the corresponding one of the communication time slots, and initiate a communication during the corresponding one of the communication time slots for a communication channel indicated in the corresponding one of the memory locations.

2. The communication scheduling system of claim 1 wherein the primary information elements are each a single bit.

3. The communication scheduling system of claim 1 wherein:

the memory is configured to store secondary information elements that correspond to blocks of the primary information elements; and

the processing circuitry is configured to modify the secondary information elements to indicate the blocks that have at least one of the information elements that have an available one of the communication time slots, and to process the secondary information elements to select the selected one of the primary information elements.

4. The communication scheduling system of claim 3 wherein the secondary information elements are each a single bit.

5. The communication scheduling system of claim 3 wherein:

the memory is configured to store channel information elements that correspond to the communication channel and that correspond to the communication time slots; and

the processing circuitry is configured to select one of the channel information elements having the corresponding one of the communication time slots, modify the selected one of the channel information elements to reserve the corresponding one of the communication time slots, and initiate the communication during the corresponding one of the communication time slots for a sub-channel in the communication channel.

6. The communication scheduling system of claim 5 wherein the selected one of the channel information elements corresponds to an additional one of the memory locations that indicates the sub-channel.

7. The communication scheduling system of claim 5 wherein the sub-channel comprises a constant bit rate channel.

8. The communication scheduling system of claim 5 wherein the sub-channel comprises an available bit rate channel.

9. The communication scheduling system of claim 5 wherein the channel information elements are each a single bit.

10. The communication scheduling system of claim 1 wherein the communication channel comprises an asynchronous transfer mode connection and the communication time slots comprise asynchronous transfer mode cell time slots.

11. A method of operating a communication scheduling system comprising:

storing primary information elements that correspond to communication time slots and that correspond to memory locations;

selecting one of the primary information elements having a corresponding one of the communication time slots and a corresponding one of the memory locations;

modifying the selected one of the primary information elements to reserve the corresponding one of the communication time slots; and

initiating a communication during the corresponding one of the communication time slots for a communication channel indicated in the corresponding one of the memory locations.

12. The method of claim 11 wherein the primary information elements are each a single bit.

13. The method of claim 11 further comprising:

storing secondary information elements that correspond to blocks of the primary information elements;

modifying the secondary information elements to indicate the blocks that have at least one of the information elements that have an available one of the communication time slots; and

processing the secondary information elements to select the selected one of the primary information elements.

14. The method of claim 13 wherein the secondary information elements are each a single bit.

15. The method of claim 11 further comprising:

storing channel information elements that correspond to the communication channel and that correspond to the communication time slots;

selecting one of the channel information elements having the corresponding one of the communication time slots;

modifying the selected one of the channel information elements to reserve the corresponding one of the communication time slots; and

wherein initiating the communication comprises initiating the communication during the corresponding one of the communication time slots for a sub-channel in the communication channel.

16. The method of claim 15 wherein the selected one of the channel information elements corresponds to an additional one of the memory locations that indicates the sub-channel.

17. The method of claim 15 wherein the sub-channel comprises a constant bit rate channel.

18. The method of claim 15 wherein the sub-channel comprises an available bit rate channel.

19. The method of claim 15 wherein the channel information elements are each a single bit.

20. The method of claim 11 wherein the communication channel comprises an asynchronous transfer mode connection and the communication time slots comprise asynchronous transfer mode cell time slots.