US6128303A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Asynchronous transfer mode cell processing system with scoreboard scheduling
Assignee: RPX Corp
•
Filing: 1996-05-09
•
Granted: 2000-10-03
•
Expires: 2016-05-09
Abstract
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.
Inventors
- 👤 Paul V. Bergantino
- 👤 Daniel J. Lussier
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 06:56
CPC Classifications
H; H04; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5614; H04L2012/5616; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5672; H04L2012/5678; H04L2012/5679; H04L2012/5681
Claims Analysis
Total Claims: 63
Claim 1
Independent Claim
191 words
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.
Claim 2
Independent Claim
191 words
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.
Claim 3
Dependent Claim
48 words
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.
Claim 4
Independent Claim
193 words
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.
Claim 5
Independent Claim
193 words
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.
Claim 6
Dependent Claim
133 words
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.
Claim 7
Independent Claim
147 words
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.
Claim 8
Independent Claim
147 words
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.
Claim 9
Independent Claim
212 words
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.
Claim 10
Independent Claim
212 words
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.
Claim 11
Dependent Claim
27 words
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.
Claim 12
Dependent Claim
36 words
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.
Claim 13
Independent Claim
213 words
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.
Claim 14
Independent Claim
213 words
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.
Claim 15
Dependent Claim
25 words
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.
Claim 16
Independent Claim
169 words
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.
Claim 17
Independent Claim
169 words
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.
Claim 18
Dependent Claim
38 words
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.
Claim 19
Dependent Claim
40 words
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.
Claim 20
Independent Claim
257 words
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.
Claim 21
Independent Claim
257 words
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.
Claim 22
Dependent Claim
60 words
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.
Claim 23
Dependent Claim
143 words
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.
Claim 24
Independent Claim
171 words
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.
Claim 25
Independent Claim
171 words
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.
Claim 26
Independent Claim
228 words
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.
Claim 27
Independent Claim
228 words
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.
Claim 28
Independent Claim
186 words
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.
Claim 29
Independent Claim
186 words
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.
Claim 30
Dependent Claim
27 words
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.
Claim 31
Dependent Claim
29 words
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.
Claim 32
Independent Claim
274 words
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.
Claim 33
Independent Claim
274 words
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.
Claim 34
Dependent Claim
62 words
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.
Claim 35
Dependent Claim
149 words
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.
Claim 36
Independent Claim
158 words
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.
Claim 37
Independent Claim
158 words
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.
Claim 38
Independent Claim
159 words
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.
Claim 39
Independent Claim
159 words
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.
Claim 40
Independent Claim
231 words
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.
Claim 41
Independent Claim
231 words
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.
Claim 42
Independent Claim
196 words
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.
Claim 43
Independent Claim
196 words
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.
Claim 44
Independent Claim
194 words
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.
Claim 45
Independent Claim
194 words
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.
Claim 46
Independent Claim
195 words
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.
Claim 47
Independent Claim
195 words
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.
Claim 48
Independent Claim
176 words
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.
Claim 49
Independent Claim
176 words
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.
Claim 50
Dependent Claim
49 words
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.
Claim 51
Dependent Claim
25 words
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.
Claim 52
Dependent Claim
58 words
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.
Claim 53
Dependent Claim
132 words
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.
Claim 54
Dependent Claim
21 words
The method of claim 31, wherein said each said unit being a respective register and said resource being a memory device.
Claim 55
Dependent Claim
22 words
The method of claim 31, wherein each said unit being a respective cell time slot and said resource being a transmission link.
Claim 56
Independent Claim
199 words
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.
Claim 57
Independent Claim
199 words
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.
Claim 58
Dependent Claim
26 words
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.
Claim 59
Dependent Claim
36 words
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.
Claim 60
Dependent Claim
60 words
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.
Claim 61
Dependent Claim
144 words
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.
Claim 62
Dependent Claim
19 words
The apparatus claim 38, wherein each said unit being a respective register and said resource being a memory device.
Claim 63
Dependent Claim
22 words
The apparatus of claim 38, wherein each said unit being a respective cell time slot and said resource being a transmission link.
References Cited (Backward Citations)
US4589087A
Cited
US5008807A
Cited
US5247627A
Cited
US4947388A
Cited
US4926374A
Cited
US5130975A
Cited
US5463622A
Cited
US5136584A
Cited
US5249178A
Cited
US5379295A
Cited
US5271005A
Cited
US5280475A
Cited
US5420859A
Cited
US5253247A
Cited
US5274641A
Cited
US5265091A
Cited
US5365519A
Cited
US5241536A
Cited
US5394397A
Cited
US5381407A
Cited
US5440552A
Cited
US5412655A
Cited
US5521915A
Cited
US5467347A
Cited
US5544172A
Cited
US5526352A
Cited
US5450400A
Cited
US5448567A
Cited
US5500851A
Cited
US5390184A
Cited
US5446726A
Cited
US5528592A
Cited
US5577035A
Cited
US5610914A
Cited
US5455826A
Cited
EP0690596A1
Cited
US5633867A
Cited
EP0702473A1
Cited
EP0705007A2
Cited
US5598541A
Cited
US5533020A
Cited
US5602853A
Cited
US5530806A
Cited
US5598410A
Cited
US5541918A
Cited
US5548588A
Cited
US5563884A
Cited
US5535201A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-10-03 | 2004-04-03 | 2004-10-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-10-03 | 2008-04-03 | 2008-10-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-10-03 | 2012-04-03 | 2012-10-03 | $7700.00 | Window Closed / Lapsed |