US5982771A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Controlling bandwidth allocation using a pace counter
Assignee: Ascom Intermediate AG
•
Filing: 1996-07-18
•
Granted: 1999-11-09
•
Expires: 2016-07-18
Abstract
Abstract A method and apparatus is disclosed for allocating bandwidth within a network switch having a plurality of input ports coupled to a plurality of output ports through a switch fabric to assure that a minimum bandwidth is allocated for predetermined scheduling lists. A switch allocation table is provided for each of a plurality of input ports. Each switch allocation table is organized as a circular table which is sequentially indexed via an associated index counter. Respective entries in the switch allocation table comprise scheduling list numbers which serve to identify cells requiring switch bandwidth. The respective index counters are synchronized such that all switch allocation tables have a corresponding entry selected. The amount of bandwidth and delay through the network switch is controlled for each of the scheduling lists based upon the number and spacing of entries in the respective switch allocation table. Latency through the network switch is significantly reduced via the use of a pace counter and a pace limit which, in cooperation with the switch allocation table, determine whether a cell associated with a particular scheduling list may be dispatched through the switch fabric for transmittal onto a network link by at least one of the output ports.
Inventors
- 👤 Stephen A. Caldara
- 👤 Stephen A. Hauser
- 👤 Thomas A. Manning
- 👤 Raymond L. Strouble
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 14:54
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L47/18; G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368; G06F15/17375; H04L12/00; H04L12/28; H04L12/46; H04L12/4604; H04L12/4608; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04L12/64; H04L12/6402; H04L41/00; H04L41/08; H04L41/0896; H04L47/11; H04L47/15; H04L47/16; H04L47/26; H04L47/266; H04L47/29; H04L47/30; H04L47/50; H04L47/52; H04L47/521; H04L47/522; H04L47/525; H04L47/56; H04L47/62; H04L47/621; H04L47/6215; H04L47/622; H04L47/6225; H04L47/625; H04L47/627; H04L47/70; H04L47/72; H04L47/722; H04L47/74; H04L47/743; H04L47/745; H04L47/76; H04L47/762; H04L47/78; H04L47/782; H04L47/80; H04L47/805; H04L47/82; H04L47/822; H04L49/00; H04L49/10; H04L49/101; H04L49/103; H04L49/104; H04L49/105; H04L49/106; H04L49/107; H04L49/108; H04L49/15; H04L49/1515; H04L49/153; H04L49/1553; H04L49/1576; H04L49/20; H04L49/201; H04L49/203; H04L49/205; H04L49/25; H04L49/253; H04L49/254; H04L49/255; H04L49/256; H04L49/30; H04L49/3009; H04L49/3081; H04L49/309; H04L49/45; H04L49/455; H04L49/50; H04L49/501; H04L49/503; H04L49/505; H04L49/506; H04L49/55; H04L49/552; H04L49/90; H04L49/901; H04L49/9047; H04L49/9063; H04L49/9078; H04L69/00; H04L69/30; H04L69/32; H04L69/322; H04L69/324; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04W; H04W28/00; H04W28/02; H04W28/10; H04W28/14; H04J; H04J3/00; H04J3/02; H04J3/06; H04J3/0635; H04J3/0682; H04J3/0685; H04L2012/5614; H04L2012/5616; H04L2012/5625; H04L2012/5627; H04L2012/5628; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5634; H04L2012/5635; H04L2012/5638; H04L2012/564; H04L2012/5642; H04L2012/5643; H04L2012/5646; H04L2012/5647; H04L2012/5648; H04L2012/5649; H04L2012/565; H04L2012/5651; H04L2012/5652; H04L2012/5672; H04L2012/5678; H04L2012/5679; H04L2012/5681; H04L2012/5682; H04L2012/5683; H04L2012/5684; H04L2012/5685; H04L41/0897; H04L41/40; H04L49/508; H04L49/555; H04L7/00; H04L7/04; H04L7/041; H04L7/046; Y; Y10; Y10S; Y10S370/00; Y10S370/901; Y10S370/902; Y10S370/903; Y10S370/905
Claims Analysis
Total Claims: 41
Claim 1
Independent Claim
195 words
A method for allocating bandwidth in a network switch having a plurality of input ports, a plurality of output ports and a switch fabric for selectively forwarding cells queued for transmission in a queue at one of said plurality of input ports to at least one of said plurality of output ports comprising the steps of: repeatedly retrieving from a table in a memory, in a predetermined sequence, a plurality of table entries, at least one of said plurality of table entries having a first predetermined value; in a first dispatching step, dispatching a first cell associated with said first predetermined value and queued for transmission to said switch fabric upon retrieval of one of said table entries having said first predetermined value; in a second dispatching step, dispatching a second cell associated with said first predetermined value to said switch fabric following queuing of said second cell on a queue associated with said first predetermined value and upon retrieval of a predetermined plurality of table entries having said first predetermined value if said second cell is queued for dispatch prior to retrieval of said predetermined plurality of table entries having said first predetermined value.
Claim 2
Independent Claim
195 words
A method for allocating bandwidth in a network switch having a plurality of input ports, a plurality of output ports and a switch fabric for selectively forwarding cells queued for transmission in a queue at one of said plurality of input ports to at least one of said plurality of output ports comprising the steps of: repeatedly retrieving from a table in a memory, in a predetermined sequence, a plurality of table entries, at least one of said plurality of table entries having a first predetermined value; in a first dispatching step, dispatching a first cell associated with said first predetermined value and queued for transmission to said switch fabric upon retrieval of one of said table entries having said first predetermined value; in a second dispatching step, dispatching a second cell associated with said first predetermined value to said switch fabric following queuing of said second cell on a queue associated with said first predetermined value and upon retrieval of a predetermined plurality of table entries having said first predetermined value if said second cell is queued for dispatch prior to retrieval of said predetermined plurality of table entries having said first predetermined value.
Claim 3
Dependent Claim
79 words
The method of claim 1 wherein said second dispatching step further includes the step of dispatching a second cell associated with said first predetermined value to said switch fabric following queuing of said second cell on a queue associated with said first predetermined value and upon retrieval of the next table entry having said first predetermined value if said second cell is queued for dispatch following retrieval of said predetermined plurality of table entries having said first predetermined value.
Claim 4
Dependent Claim
55 words
The method of claim 1 wherein said repeatedly retrieving step further comprises the steps of: storing within said memory said plurality of table entries, wherein each of said table entries within said memory has a predetermined address; repeatedly generating a sequence of addresses; and accessing said table entries in accordance with said sequence of addresses.
Claim 5
Dependent Claim
47 words
The method of claim 1 wherein said queue comprises a plurality of queues at at least some of the time and said step of dispatching a cell associated with said first predetermined value comprises the step of dispatching said cell from one of said plurality of queues.
Claim 6
Dependent Claim
55 words
The method of claim 4 wherein said method further comprises the step of selecting each queue of said plurality of queues in a predetermined sequence and wherein said step of dispatching said cell associated with said first predetermined value comprises the step of dispatching said cell from the selected queue of said plurality of queues.
Claim 7
Dependent Claim
39 words
The method of claim 5 wherein said step of selecting each queue of said plurality of queues in a predetermined sequence comprises the step of selecting the respective queue of said plurality of queues in a round robin sequence.
Claim 8
Dependent Claim
58 words
The method of claim 5 wherein said step of dispatching said cell from the selected queue of said plurality of queues in said predetermined sequence further comprises the step of dispatching said cell from the selected queue of said plurality of queues on a first in first out (FIFO) basis within each queue of said plurality of queues.
Claim 9
Dependent Claim
60 words
The method of claim 1 wherein said method further includes the steps of: receiving said first cell at said one of said plurality of input ports and storing said first cell in said queue; subsequent to receipt of said first cell, receiving a second cell at said one of said input ports and storing said second cell in said queue.
Claim 10
Dependent Claim
34 words
The method of claim 1 wherein said table entries having said first predetermined value are selectively stored within said table such that said table entries having said first predetermined value are retrieved substantially periodically.
Claim 11
Dependent Claim
20 words
The method of claim 1 wherein at least two of said plurality of table entries contain said first predetermined value.
Claim 12
Dependent Claim
57 words
The method of claim 10 wherein said dispatching step further comprises the step of: dispatching a cell associated with said first predetermined value and queued for transmission to said switch fabric following retrieval of said predetermined plurality of table entries having said first predetermined value, upon retrieval of the next table entry having said first predetermined value.
Claim 13
Independent Claim
204 words
A method for allocating bandwidth in a network switch having a plurality of input ports, a plurality of output ports and a data switch for selectively forwarding cells from one of said plurality of input ports to one of said plurality of output ports comprising the steps of: repeatedly retrieving from a table stored in memory, in a predetermined sequence, a plurality of table entries, at least one of said plurality of table entries having a first predetermined value, said first predetermined value being associated with a queue of said input port; upon retrieval of each of said table entries having said first predetermined value, testing a counter value to determine if said counter value is equal to a second predetermined value; if said counter value is equal to said second predetermined value and a cell is queued for transmission in a queue associated with said predetermined value; forwarding said queued cell from said queue associated with said first predetermined value to said data switch for delivery to at least a selected one of said output ports; and setting said counter value to a third predetermined value; and if said counter value is not equal to said second predetermined value, updating said counter value.
Claim 14
Independent Claim
204 words
A method for allocating bandwidth in a network switch having a plurality of input ports, a plurality of output ports and a data switch for selectively forwarding cells from one of said plurality of input ports to one of said plurality of output ports comprising the steps of: repeatedly retrieving from a table stored in memory, in a predetermined sequence, a plurality of table entries, at least one of said plurality of table entries having a first predetermined value, said first predetermined value being associated with a queue of said input port; upon retrieval of each of said table entries having said first predetermined value, testing a counter value to determine if said counter value is equal to a second predetermined value; if said counter value is equal to said second predetermined value and a cell is queued for transmission in a queue associated with said predetermined value; forwarding said queued cell from said queue associated with said first predetermined value to said data switch for delivery to at least a selected one of said output ports; and setting said counter value to a third predetermined value; and if said counter value is not equal to said second predetermined value, updating said counter value.
Claim 15
Dependent Claim
33 words
The method of claim 12 wherein said step of updating said counter value comprises the step of modifying said counter value such that said counter value approaches or equals said second predetermined value.
Claim 16
Dependent Claim
24 words
The method of claim 12 wherein said second predetermined value equals 0 and said modifying step comprises the step of decrementing said counter value.
Claim 17
Dependent Claim
59 words
The method of claim 12 wherein said network switch includes a table for each of said plurality of input ports and said method includes the step of repeating each of the steps recited in claim 12 for each of said tables and wherein said first predetermined value for each of said tables may comprise a different first predetermined value.
Claim 18
Dependent Claim
32 words
The method of claim 12 wherein said at least one table entry is selectively stored within said table such that said table entries having said first predetermined value are retrieved substantially periodically.
Claim 19
Dependent Claim
20 words
The method of claim 12 wherein at least two of said plurality of table entries contain said first predetermined value.
Claim 20
Dependent Claim
57 words
The method of claim 13 wherein said dispatching step further comprises the step of: dispatching a cell associated with said first predetermined value and queued for transmission to said switch fabric following retrieval of said predetermined plurality of table entries having said first predetermined value upon retrieval of the next table entry having said first predetermined value.
Claim 21
Dependent Claim
181 words
A network switch having a plurality of input ports, a plurality of output ports, a switch fabric in electrical communication with said pluralities of input and output ports, wherein said switch fabric is operative to dispatch a cell received from one of said input ports to at least one of said output ports, said network switch comprising: a queue having a queue identifier of a first predetermined value, said queue being associated with said one of said input ports; a queue identifier generator operative to repetitively output a sequence of queue identifiers, said sequence containing at least one queue identifier having said first predetermined value; a cell dispatch controller operative to dispatch a cell from said queue within said one of said input ports to said switch fabric following the output by said queue identifier generator of a predetermined plurality of queue identifiers having said first predetermined value after dispatch of a prior cell from said queue if said cell is queued on said queue prior to the output of said predetermined plurality of queue identifiers having said first predetermined value.
Claim 22
Dependent Claim
181 words
A network switch having a plurality of input ports, a plurality of output ports, a switch fabric in electrical communication with said pluralities of input and output ports, wherein said switch fabric is operative to dispatch a cell received from one of said input ports to at least one of said output ports, said network switch comprising: a queue having a queue identifier of a first predetermined value, said queue being associated with said one of said input ports; a queue identifier generator operative to repetitively output a sequence of queue identifiers, said sequence containing at least one queue identifier having said first predetermined value; a cell dispatch controller operative to dispatch a cell from said queue within said one of said input ports to said switch fabric following the output by said queue identifier generator of a predetermined plurality of queue identifiers having said first predetermined value after dispatch of a prior cell from said queue if said cell is queued on said queue prior to the output of said predetermined plurality of queue identifiers having said first predetermined value.
Claim 23
Dependent Claim
91 words
The network switch of claim 19 wherein said cell dispatch controller is further operative to dispatch a cell from said queue within said one of said input ports to said switch fabric following queuing of a cell on said queue and upon the output by said queue identifier generator of the next queue identifier having said first predetermined value if at least said predetermined plurality of queue identifiers having said first predetermined value have been output by said queue identifier generator since the dispatch of a prior cell from said queue.
Claim 24
Dependent Claim
86 words
The network switch of claim 19 wherein said queue identifier generator comprises: an address generator operative to repeatedly generate a series of addresses in a first predetermined sequence; and a memory containing a table having a plurality of table entries, wherein selected ones of said table entries comprise said queue identifiers, said memory being responsive to said address generator to output one of said table entries in response to each of said addresses, said table containing at least two queue identifiers having said first predetermined value.
Claim 25
Dependent Claim
27 words
The network switch of claim 20 wherein said address generator further comprises a counter which is operative to output sequential addresses in response to a clock input.
Claim 26
Dependent Claim
21 words
The network switch of claim 19 wherein said queue comprises a plurality of queues at at least some of the time.
Claim 27
Dependent Claim
29 words
The network switch of claim 23 further comprising a cell dispatch controller operative to dispatch a cell from each queue of said plurality of queues in a predetermined sequence.
Claim 28
Dependent Claim
30 words
The network switch of claim 24 wherein said cell dispatch controller is operative to dispatch a cell from each queue of said plurality of queues in a round robin sequence.
Claim 29
Dependent Claim
24 words
The network switch of claim 19 wherein said queue identifier generator is operative to output queue identifiers having said first predetermined value substantially periodically.
Claim 30
Dependent Claim
19 words
The network switch of claim 19 wherein at least two of said queue identifiers have said first predetermined value.
Claim 31
Dependent Claim
58 words
The network switch of claim 27 wherein said dispatching step further comprises the step of: dispatching a cell associated with said first predetermined value and queued for transmission to said switch fabric following retrieval of said predetermined plurality of queue identifiers having said first predetermined value upon retrieval of the next queue identifier having said first predetermined value.
Claim 32
Dependent Claim
243 words
A network switch for forwarding a cell received from one of a plurality of input ports of said network switch to one of a plurality of output ports of said network switch via a switch fabric comprising: an address generator operative to repeatedly generate a series of addresses in a first predetermined sequence; a memory containing a table comprising a plurality of table entries and operative in response to said address generator to output one of said table entries in response to an address input, said table containing at least one table entry having a first predetermined value; a counter containing a counter value; a storage register containing a second predetermined value; a queue associated with said first predetermined value for storing at least one cell for transmission to at least one of said output ports; a bandwidth controller operative in response to the output of each of said plurality of entries of said first predetermined value from said table to determine if said counter value equals a third predetermined value; said bandwidth controller being further operative, if said counter value is equal to said third predetermined value and a cell is queued for transmission in said queue to: dispatch said cell from said queue to said switch fabric; and set said counter value to said second predetermined value; and said bandwidth controller being further operative, if said counter value is not equal to said third predetermined value, to update said counter value.
Claim 33
Dependent Claim
243 words
A network switch for forwarding a cell received from one of a plurality of input ports of said network switch to one of a plurality of output ports of said network switch via a switch fabric comprising: an address generator operative to repeatedly generate a series of addresses in a first predetermined sequence; a memory containing a table comprising a plurality of table entries and operative in response to said address generator to output one of said table entries in response to an address input, said table containing at least one table entry having a first predetermined value; a counter containing a counter value; a storage register containing a second predetermined value; a queue associated with said first predetermined value for storing at least one cell for transmission to at least one of said output ports; a bandwidth controller operative in response to the output of each of said plurality of entries of said first predetermined value from said table to determine if said counter value equals a third predetermined value; said bandwidth controller being further operative, if said counter value is equal to said third predetermined value and a cell is queued for transmission in said queue to: dispatch said cell from said queue to said switch fabric; and set said counter value to said second predetermined value; and said bandwidth controller being further operative, if said counter value is not equal to said third predetermined value, to update said counter value.
Claim 34
Dependent Claim
33 words
The network switch of claim 29 wherein said third predetermined value equals 0 and said bandwidth controller is operative to decrement said counter value if said counter value is not equal to 0.
Claim 35
Dependent Claim
15 words
The network switch of claim 29 wherein said second predetermined value is greater than one.
Claim 36
Dependent Claim
28 words
The network switch of claim 29 wherein said memory is operative to output table entries having said first predetermined value substantially periodically in response to said address generator.
Claim 37
Dependent Claim
21 words
The network switch of claim 29 wherein at least two of said plurality of table entries contain said first predetermined value.
Claim 38
Dependent Claim
58 words
The network switch of claim 33 wherein said dispatching step further comprises the step of: dispatching a cell associated with said first predetermined value and queued for transmission to said switch fabric following retrieval of said predetermined plurality of table entries having said first predetermined value upon retrieval of the next table entry having said first predetermined value.
Claim 39
Independent Claim
149 words
A method for allocating bandwidth in a network switch having a plurality of input ports, a plurality of output ports and a switch fabric for selectively forwarding cells queued for transmission in at least one queue associated with one of said plurality of input ports to at least one of said plurality of output ports comprising the steps of: generating a continuous sequence of scheduling list identifiers, wherein at least one scheduling list identifier of said sequence has a first predetermined value which is associated with said at least one queue; detecting said scheduling list identifiers; dispatching to said switch fabric a cell available for dispatch from one of said at least one queue and associated with said first predetermined value upon detection of a predetermined plurality of scheduling list identifiers having said first predetermined value following the dispatch of a prior cell from said at least one queue.
Claim 40
Independent Claim
149 words
A method for allocating bandwidth in a network switch having a plurality of input ports, a plurality of output ports and a switch fabric for selectively forwarding cells queued for transmission in at least one queue associated with one of said plurality of input ports to at least one of said plurality of output ports comprising the steps of: generating a continuous sequence of scheduling list identifiers, wherein at least one scheduling list identifier of said sequence has a first predetermined value which is associated with said at least one queue; detecting said scheduling list identifiers; dispatching to said switch fabric a cell available for dispatch from one of said at least one queue and associated with said first predetermined value upon detection of a predetermined plurality of scheduling list identifiers having said first predetermined value following the dispatch of a prior cell from said at least one queue.
Claim 41
Dependent Claim
63 words
The method of claim 35 wherein said dispatching step further comprises the step of dispatching a cell which becomes available for dispatch from said at least one queue after detection of said predetermined plurality of scheduling list identifiers having said first predetermined value since the dispatch of said prior cell, upon detection of the next scheduling list identifier having said first predetermined value.
References Cited (Backward Citations)
US3804991A
Cited
US3974343A
Cited
US4069399A
Cited
US4603382A
Cited
US4849968A
Cited
US4727537A
Cited
US4737953A
Cited
US4715030A
Cited
US4821034A
Cited
US4993018A
Cited
US4920531A
Cited
US4878216A
Cited
US4797881A
Cited
US4837761A
Cited
US5084871A
Cited
US5282201A
Cited
US5335325A
Cited
US4893307A
Cited
US5021949A
Cited
US4870641A
Cited
US4872159A
Cited
US4899333A
Cited
US4872160A
Cited
US4958341A
Cited
US4894824A
Cited
US4893302A
Cited
US4979100A
Cited
US5377327A
Cited
US5146560A
Cited
US4956839A
Cited
US4888765A
Cited
US5198808A
Cited
US4922503A
Cited
US5060228A
Cited
US5157657A
Cited
US5090011A
Cited
US5083269A
Cited
US4897841A
Cited
US5199027A
Cited
US4933938A
Cited
US4947390A
Cited
US5132966A
Cited
US4953157A
Cited
US5119372A
Cited
US5179558A
Cited
US5093912A
Cited
US5422879A
Cited
US5130982A
Cited
US5067123A
Cited
US5119369A
Cited
US5070498A
Cited
US5090024A
Cited
US5193151A
Cited
US5197067A
Cited
US5084867A
Cited
US5191652A
Cited
US5163046A
Cited
US5130975A
Cited
US5185743A
Cited
US5272697A
Cited
US5379418A
Cited
US5544170A
Cited
US5553068A
Cited
US5309431A
Cited
US5151897A
Cited
US5258979A
Cited
US5239539A
Cited
US5146474A
Cited
US5029164A
Cited
US5303232A
Cited
US5253248A
Cited
US5341376A
Cited
US5115429A
Cited
US5301190A
Cited
US5335222A
Cited
US5333131A
Cited
US5274641A
Cited
US5253247A
Cited
US5150358A
Cited
US5128932A
Cited
US5267232A
Cited
US5420988A
Cited
US5283788A
Cited
US5163045A
Cited
US5414703A
Cited
US5394396A
Cited
US5271010A
Cited
US5255266A
Cited
US5497369A
Cited
US5268897A
Cited
US5301193A
Cited
US5280470A
Cited
US5285446A
Cited
US5375117A
Cited
US5333134A
Cited
US5287349A
Cited
US5590132A
Cited
US5341373A
Cited
US5479402A
Cited
US5339310A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-08 | 2003-05-10 | 2003-11-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-08 | 2007-05-10 | 2007-11-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-08 | 2011-05-10 | 2011-11-09 | $7700.00 | Window Closed / Lapsed |