Asynchronous transfer mode cell processing system with scoreboard scheduling

• US 6,128,303 A
• Filed: 05/09/1996
• Issued: 10/03/2000
• Est. Priority Date: 05/09/1996
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Maker Communications, Inc. (Synaptics Incorporated)
• Inventors: Bergantino, Paul V., Lussier, Daniel J.
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): YAO, KWANG BIN
• Application Number:
  US08/647,374
• Time in Patent Office: 1,608 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
• 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 method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of:

generating a first group of information elements with each element in the first group representing a cell time slot, wherein the value of a given element in the first group indicates whether or not the corresponding cell time slot is available for transmission;

generating a second group of information elements, each element in the second group of information elements corresponding to a block of information elements in the first group and indicative of whether the corresponding block of information elements includes at least one information element indicative of an available cell time slot,

searching the first group of information elements, in response to a cell scheduling request of a given virtual connection in the ATM system, beginning at an element corresponding to a target time slot and proceeding through the first group of elements until an element corresponding to an available time slot is identified; and

scheduling the available time slot for use by the virtual connection by altering the identified element to indicate that the available time slot has been scheduled.

2. The method of claim 1 wherein the information elements are bits, with each bit in the first group representing a cell time slot and each bit in the second group indicating whether at least one time slot is available in a block of bits in the first group.

3. A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method of comprising the steps of:

generating a first group of information elements, with each element in the first group representing a time slot, wherein the value of a given element in the first group indicates whether or not the corresponding cell time slot is available for transmission;

reserving at least one cell time slot in a transmission link for a virtual path connection;

setting an information element in the first group of information elements corresponding to the cell time slot reserved for the virtual path connection, such that said information elements indicate the reserved cell time slot is unavailable; and

generating a tunnel control group of information elements, with each information element in the tunnel control group corresponding to a cell time slot in the transmission link, each of the tunnel control group information elements corresponding to a slot or slots reserved for the virtual path connection, the information elements set in a first manner indicating an available time slot, and all other tunnel control group information elements set in a second, opposite manner indicating unavailable time slots.

4. The method of claim 3 wherein the information elements are bits and further including the steps of:

receiving a servicing request corresponding to the virtual path connection;

searching the tunnel control group of bits for the virtual path connection to determine if a cell time slot has been scheduled for the corresponding location;

directing transmission of a cell in a scheduled cell time slot if the time slot has been scheduled for the corresponding location;

resetting the corresponding bit of the tunnel control group of bits to indicate that the corresponding cell time slot is again available for scheduling; and

setting a bit in the first group of bits corresponding to the cell time slot reserved for the virtual path connection, such that said bit indicates the reserved cell time slot is unavailable.

5. A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of:

generating a first group of bits, with each bit in the first group representing a cell time slot, wherein the value of a given bit in the first group of bits indicates whether or not the corresponding cell time slot is available for transmission;

generating a second group of bits, with each bit in the second group of bits corresponding to a block of bits in the first group of bits and indicative of whether the corresponding block of bits includes at least one bit indicative of an available cell time slot; and

utilizing the second group of bits to determine a block of the first group of bits to be searched in response to a cell scheduling request of a given virtual connection in the ATM system.

6. An apparatus for use in allocating cells in an asynchronous transfer mode (ATM) communication system, the apparatus comprising:

a first group of memory locations for storing a first group of information elements with each element in the first group representing a cell time slot, wherein the value of a given element in the first group of bits indicates whether or not the corresponding cell time slot is available for transmission;

a second group of memory locations for storing a second group of information elements, each element in the second group of information elements corresponding to a block of information elements in the first group of elements and indicative of whether the corresponding block of elements includes at least one bit indicative of an available cell time slot; and

a processor operative to search the first group of information elements, in response to a cell scheduling request of a given virtual connection in the ATM system, beginning at an element corresponding to a target time slot and proceeding through the first group of elements until an element corresponding to an available time slot is identified, and to schedule the available time slot for use by the virtual connection by altering the identified element to indicate that the available time slot has been scheduled.

7. The apparatus of claim 6 wherein the first group of information elements is configured as first group of bits with each bit representing a cell time slot.

8. The apparatus of claim 7 further including a memory for storing the first group of bits and a connection identifier table, wherein the connection identifier is stored in a memory location corresponding to the identified bit.

9. A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of:

generating a first group of bits with each bit in the first group representing a cell time slot, wherein the value of a given bit in the first group indicates whether or not the corresponding cell time slot is available for transmission;

receiving a scheduling instruction specifying a connection identifier for a given virtual connection and an address in a connection identifier table corresponding to a target time slot;

converting the connection identifier table address into an address for a bit in the first group of bits corresponding to the target time slot;

retrieving a portion of the first group of bits, the portion of the first group of bits including the bit corresponding to the target time slot and at least one additional bit corresponding to a subsequent cell time slot;

searching the portion of the first group of bits, in response to the scheduling instruction of the given virtual connection in the ATM system, until a bit corresponding to an available time slot is identified; and

scheduling the available time slot for use by the virtual connection by altering the identified element to indicate that the available time slot has been scheduled.

10. The method of claim 9 further including the step of storing the connection identifier in a connection identifier table location corresponding to the identified bit.

11. A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of:

generating a first group of bits with each bit in the first group representing a cell time slot, wherein the value of a given bit in the first group indicates whether or not the corresponding cell time slot is available for transmission;

receiving a servicing instruction specifying an address in a connection identifier table;

retrieving from the connection identifier table a connection identifier corresponding to the specified address and identifying a virtual connection in the ATM system;

retrieving from a memory storing the first group of bits a bit corresponding to the specified address in the connection identifier table;

directing transmission of a cell for the virtual connection if the retrieved bit indicates that the corresponding cell time slot has been scheduled for the virtual connection; and

altering the corresponding bit to indicate that the cell time slot has been serviced and is therefore again available for subsequent scheduling requests.

12. The method of claim 11 wherein the step of directing transmission of a cell for the virtual connection further includes the step of constructing a cell for the virtual connection for transmission during the scheduled cell time slot.

13. The method of claim 11 wherein the step of directing transmission of a cell for the virtual connection further includes the step of retrieving a previously constructed cell for the virtual connection for transmission during the scheduled cell time slot.

14. A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of:

generating a first group of bits with each bit in the first group representing a cell time slot, wherein the value of a given bit in the first group indicates whether or not the corresponding cell time slot is available for transmission;

retrieving a first block of bits within the first group of bits in response to a scheduling instruction specifying a connection identifier of a virtual connection and a target cell slot, the first block of bits including a bit corresponding to the target cell time slot;

searching through the retrieved first block to locate a bit indicative of an available cell time slot at or after the bit corresponding to the target cell time slot;

if an available cell time slot is located, determining if there are any other bits in the first block of bits indicative of other available cell time slots;

if there are no other bits in the first block indicative of other available cell time slots, altering a bit in a second group of bits to indicate that the first block of the first group includes only bits corresponding to unavailable cell time slots, the second group of bits including a bit for each of a plurality of blocks of bits in the first group of bits, the second group of bits indicative of whether the corresponding block of first group bits includes a bit indicative of an available cell time slot.

15. The method of claim 14 further including the step of, if no available cell time slot is located in the first block of bits in the first group of bits, using the second group of bits to identify a subsequent block of bits in the first group of bits which includes a bit indicative of an available cell time slot.

16. The method of claim 15 further including the steps of:

retrieving the subsequent block of bits in the first group of bits which includes a bit indicative of an available cell time slot;

searching the subsequent block of bits to locate the bit indicative of the available cell time slot;

scheduling the available time slot for use by the virtual connection by altering the bit indicative of the available time slot to indicate that the available time slot has been scheduled;

determining if the subsequent block includes any other bits indicative of other available cell time slots; and

if there are no other bits in the subsequent block indicative of other available cell time slots, altering a bit in a second group of bits to indicate that the subsequent block of the first group includes only bits corresponding to unavailable cell time slots.

17. A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of:

providing multiple groups of bits, with each group of bits indicating a schedule status of a portion of traffic for a transmission link of the ATM system;

utilizing a first group of bits of the multiple groups to reflect schedule status regarding high priority traffic on the transmission link;

generating a second group of bits of the multiple groups to be indicative of the schedule status of lower priority traffic on the transmission link;

searching the first group of bits, in response to a cell scheduling request of a given virtual connection in the ATM system, beginning at a bit corresponding to a target time slot and proceeding through the first group of elements until a bit corresponding to an available time slot is identified; and

scheduling the available time slot for use by the virtual connection by altering the identified bit to indicate that the available time slot has been scheduled.

18. An apparatus for use in allocating cells in an asynchronous transfer mode (ATM) communication system, the apparatus comprising:

a first group of memory locations for storing a first group of bits with each bit in the first group representing a cell time slot, wherein the value of a given bit in the first group of bits indicates whether or not the corresponding cell time slot is available for transmission;

a processor operative to receive a scheduling instruction specifying a connection identifier for a virtual connection and an address in a connection identifier table corresponding to a target time slot, to convert the connection identifier table address into an address for a bit in the first group of bits corresponding to the target time slot, and to retrieve from memory a portion of the first group of bits including the bit corresponding to the target time slot and at least one additional bit corresponding to a subsequent cell time slot;

the processor further being operative to search the first group of bits beginning at a bit corresponding to the target time slot and proceeding through the first group of bits until a bit corresponding to an available time slot is identified, and to schedule the available time slot for use by the virtual connection by altering the identified bit to indicate that the available time slot has been scheduled.

19. An apparatus for use in allocating cells in an asynchronous transfer mode (ATM) communication system, the apparatus comprising:

a first group of memory locations for storing a first group of bits with each bit in the first group representing a cell time slot, wherein the value of a given bit in the first group of bits indicates whether or not the corresponding cell time slot is available for transmission; and

a processor operative to receive a servicing instruction specifying an address in a connection identifier table, to retrieve from the connection identifier table a connection identifier corresponding to the specified address and identifying a virtual connection in the ATM system, to retrieve from a memory storing the first group of bits a bit corresponding to the specified address in the connection identifier table, to direct transmission of a cell for the virtual connection if the retrieved bit indicates that the corresponding cell time slot has been scheduled for the virtual connection, and to alter the corresponding bit to indicate that the cell time slot has been serviced and is therefore again available for subsequent scheduling requests.

20. The apparatus of claim 19 wherein the processor is further operative to construct a cell for the virtual connection for transmission during the scheduled cell time slot.

21. The apparatus of claim 19 wherein the processor is further operative to retrieve a previously constructed cell for the virtual connection for transmission during the scheduled cell time slot.

22. An apparatus for use in allocating cells in an asynchronous transfer mode (ATM) communication system, the apparatus comprising:

a first group of memory locations for storing a first group of bits with each bit in the first group representing a cell time slot, wherein the value of a given bit in the first group of bits indicates whether or not the corresponding cell time slot is available for transmission; and

a processor operative to retrieve a first block of bits within the first group of bits in response to a scheduling instruction specifying a connection identifier of a virtal connection and a target cell slot, the first block of bits including a bit corresponding to a target cell time slot, to search through the retrieved first block to locate a bit indicative of an available cell time slot at or after the bit corresponding to the target cell time slot, if an available cell time slot is located, to determine if there are any other bits in the first block of bits indicative of other available cell time slots, and if there are no other bits in the first block indicative of other available cell time slots, altering a bit in a second group of bits to indicate that the first block of the first group includes only bits corresponding to unavailable cell time slots, the second group of bits including a bit for each of a plurality of blocks of bits in the first group of bits, the second group of bits indicative of whether the corresponding block of first group of bits includes a bit indicative of an available cell time slot.

23. The apparatus of claim 22 wherein the processor is further operative, if no available cell time slot is located in the first block of bits in the first group of bits, to utilize the second group of bits to identify a subsequent block of bits in the first group of bits which includes a bit indicative of an available cell time slot.

24. The apparatus of claim 23 wherein the processor is further operative to retrieve the subsequent block of bits in the first group of bits which includes a bit indicative of an available cell time slot, to search the subsequent block of bits to locate the bit indicative of the available cell time slot, to schedule the available time slot for use by the virtual connection by altering the bit indicative of the available time slot to indicate that the available time slot has been scheduled, to determine if the subsequent block includes any other bits indicative of other available cell time slots, and if there are no other bits in the subsequent block indicative of other available cell time slots, to alter a bit in a second group of bits to indicate that the subsequent block of the first group includes only bits corresponding to unavailable cell time slots.

25. A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of:

generating multiple groups of information elements with each group of information elements indicating a schedule status of a group of virtual connections having a given cell rate;

each element in each group representing a cell time slot, wherein the value of a given element in a group indicates whether or not the corresponding cell time slot is available for transmission;

searching a first group of information elements, in response to a cell scheduling request of a given virtual connection in the ATM system, beginning at an element corresponding to a target time slot and proceeding through the first group of elements until an element corresponding to an available time slot is identified; and

scheduling the available time slot for use by the virtual connection by altering the identified element to indicate that the available time slot has been scheduled.

26. A method of allocating cells in an asynchronous transfer mode (ATM) communication system, the method comprising the steps of:

generating multiple groups of information elements with each group of information elements indicating a schedule status of a separate transmission link in a system supporting multiple transmission lines;

each element in each group representing a cell time slot, wherein the value of a given element in each group indicates whether or not the corresponding cell time slot is available for transmission;

searching a first group of information elements, in response to a cell scheduling request of a given virtual connection in the ATM system, beginning at an element corresponding to a target time slot and proceeding through the first group of elements until an element corresponding to an available time slot is identified; and

scheduling the available time slot for use by the virtual connection by altering the identified element to indicate that the available time slot has been scheduled.

27. An apparatus for use in allocating cells in an asynchronous transfer mode (ATM) communication system, the apparatus comprising:

a first group of memory locations for storing a first group of information elements with each element in the first group representing a cell time slot, wherein the value of a given element in the first group of bits indicates whether or not the corresponding cell time slot is available for transmission;

a second group of memory locations for storing a tunnel control group of information elements, with each element in the tunnel control group corresponding to a cell time slot, with each of the tunnel control information group elements corresponding to a slot reserved for the virtual path connection, information elements set in a first manner indicating an available time slot, and all other tunnel control group bits set in a second manner indicating unavailable time slots; and

a processor operative to search the first group of information elements, in response to a cell scheduling request of a given virtual connection in the ATM system, beginning at an element corresponding to a target time slot and proceeding through the first group of elements until an element corresponding to an available time slot is identified, and to schedule the available time slot for use by the virtual connection by altering the identified element to indicate that the available time slot has been scheduled.

28. An apparatus for use in allocating cells in an asynchronous transfer mode (ATM) communication system, the apparatus comprising:

a first group of memory locations for storing a first group of information elements with each element in the first group representing a cell time slot, wherein the value of a given element in the first group of bits indicates whether or not the corresponding cell time slot is available for transmission;

a plurality of additional groups of memory locations for storing a corresponding plurality of additional groups of information elements, with each group of elements indicating a schedule status of a portion of traffic for the transmission link of the ATM system; and

a processor operative to search the first group of information elements, in response to a cell scheduling request of a given virtual connection in the ATM system, beginning at an element corresponding to a target time slot and proceeding through the first group of elements until an element corresponding to an available time slot is identified, and to schedule the available time slot for use by the virtual connection by altering the identified element to indicate that the available time slot has been scheduled.

29. An apparatus for use in allocating cells in an asynchronous transfer mode (ATM) communication system, the apparatus comprising:

a first group of memory locations for storing a first group of information elements with each element in the first group representing a cell time slot, wherein the value of a given element in the first group of bits indicates whether or not the corresponding cell time slot is available for transmission;

a plurality of additional groups of memory locations for storing a corresponding plurality of additional groups of information elements, with each group of elements indicating a schedule status of a group of virtual connections having a given cell rate; and

a processor operative to search the first group of information elements, in response to a cell scheduling request of a given virtual connection in the ATM system, beginning at an element corresponding to a target time slot and proceeding through the first group of elements until an element corresponding to an available time slot is identified, and to schedule the available time slot for use by the virtual connection by altering the identified element to indicate that the available time slot has been scheduled.

30. An apparatus for use in allocating cells in an asynchronous transfer mode (ATM) communication system, the apparatus comprising:

a first group of memory locations for storing a first group of information elements with each element in the first group representing a cell time slot, wherein the value of a given element in the first group of bits indicates whether or not the corresponding cell time slot is available for transmission;

a plurality of additional groups of memory locations for storing a corresponding plurality of additional groups of information elements, with each group of elements indicating a schedule status of a separate transmission link in a system supporting multiple transmission links; and

a processor operative to search the first group of information elements, in response to a cell scheduling request of a given virtual connection in the ATM system, beginning at an element corresponding to a target time slot and proceeding through the first group of elements until an element corresponding to an available time slot is identified, and to schedule the available time slot for use by the virtual connection by altering the identified element to indicate that the available time slot has been scheduled.

31. A method of allocating units of a resource, the method comprising the steps of:

generating a first group of information elements with each element in the first group representing one of the resource units, wherein the value of a given element in the first group indicates whether or not the corresponding resource unit is available;

generating a second group of information elements, each element in the second group of information elements corresponding to a block of information elements in the first group, each information element of the second group being indicative of whether the corresponding block of information elements of the first group includes at least one information element indicative of an available resource unit,

searching the first group of information elements, in response to request, beginning at an element corresponding to a target resource unit and proceeding through the first group of elements until an element corresponding to an available resource unit is identified; and

scheduling the available resource unit by altering the identified element to indicate that the available resource unit has been scheduled.

32. The method of claim 31 wherein the information elements are bits, with each bit in the first group representing one of said resource units and each bit in the second group indicating whether at least one resource unit is available in a block of bits in the first group.

33. The method of claim 32 further including the step of storing the connection identifier in a connection identifier table location corresponding to the identified bit.

34. The method of claim 33 further including the step of, if no available resource unit is located in the first block of bits in the first group of bits, using the second group of bits to identify a subsequent block of bits in the first group of bits which includes a bit indicative of an available resource unit.

35. The method of claim 34 further including the steps of:

retrieving the subsequent block of bits in the first group of bits which includes a bit indicative of an available resource unit;

searching the subsequent block of bits to locate the bit indicative of the available resource unit;

scheduling the available resource unit by altering the bit indicative of the available resource unit to indicate that the available resource unit has been scheduled;

determining if the subsequent block includes any other bits indicative of other available resource units; and

if there are no other bits in the subsequent block indicative of other available resource units, altering a bit in a second group of bits to indicate that the subsequent block of the first group includes only bits corresponding to unavailable resource units.

36. The method of claim 31, wherein said each said unit being a respective register and said resource being a memory device.

37. The method of claim 31, wherein each said unit being a respective cell time slot and said resource being a transmission link.

38. An apparatus for use in allocating units of a resource, the apparatus comprising:

a first group of memory locations for storing a first group of information elements with each element in the first group representing one of the resource units, wherein the value of a given element in the first group of bits indicates whether or not the corresponding resource unit is available;

a second group of memory locations for storing a second group of information elements, each element in the second group of information elements corresponding to a block of information elements in the first group of elements, and each information element of the second group being indicative of whether the corresponding block of elements of the first group includes at least one bit indicative of an available resource unit; and

a processor operative to search the first group of information elements, in response to a request, beginning at an element corresponding to a target resource unit and proceeding through the first group of elements until an element corresponding to an available resource unit is identified, and to schedule the available resource unit by altering the identified element to indicate that the available resource unit has been scheduled.

39. The apparatus of claim 38 wherein the first group of information elements is configured as first group of bits with each bit representing a resource unit.

40. The apparatus of claim 39 further including a memory for storing the first group of bits and a connection identifier table, wherein the connection identifier is stored in a memory location corresponding to the identified bit.

41. The apparatus of claim 40 wherein the processor is further operative, if no available resource unit is located in the first block of bits in the first group of bits, to utilize the second group of bits to identify a subsequent block of bits in the first group of bits which includes a bit indicative of an available resource unit.

42. The apparatus of claim 41 wherein the processor is further operative to retrieve the subsequent block of bits in the first group of bits which includes a bit indicative of an available resource unit, to search the subsequent block of bits to locate the bit indicative of the available resource unit, to schedule the available resource unit for use by the virtual connection by altering the bit indicative of the available resource unit to indicate that the available resource unit has been scheduled, to determine if the subsequent block includes any other bits indicative of other available resource units, and if there are no other bits in the subsequent block indicative of other available resource units, to alter a bit in a second group of bits to indicate that the subsequent block of the first group includes only bits corresponding to unavailable resource units.

43. The apparatus claim 38, wherein each said unit being a respective register and said resource being a memory device.

44. The apparatus of claim 38, wherein each said unit being a respective cell time slot and said resource being a transmission link.