US5872769A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Linked list structures for multiple levels of control in an ATM switch
Assignee: Ascom Intermediate AG
•
Filing: 1996-07-18
•
Granted: 1999-02-16
•
Expires: 2016-07-18
Abstract
Abstract A linked-list structure and method for use in an ATM network switch capable of adaptively providing highly efficient, and thus low cost, integrated services therein. The linked-list structure involves the creation of a list having pointers to a subsequent linked list as list entries. Within the subsequent linked list, each entry can be a pointer to a further linked list. The structure can be expanded to further levels of linked lists as required. Bandwidth distribution is thus achieved among list members at each level. The linked-list structure is employed in the present switch, which includes an input port processor, a bandwidth arbiter, and an output port processor, for switch bandwidth scheduling for both point-to-point, multipoint-to-point and point-to-multipoint cell transfers from the input port processor, and for output link scheduling at the output port processor.
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-11-01 19:13
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: 19
Claim 1
Independent Claim
177 words
A switch structure for use in a communications network, said switch structure comprising a processing element and associated memory for implementing the arbitration between plural queues, each belonging to a respective one of plural scheduling lists addressed by one of plural entries in a master list, said structure comprising: a control element; a linked list of one or more of said plural queues, each queue having a common first characteristic, said linked list of queues organized by said control element and addressed by a respective scheduling list; and a linked list of one or more of said plural scheduling lists, each scheduling list having a common second characteristic, said linked list of scheduling lists organized by said control element and addressed by said master list, wherein said control element is for recognizing the selection of a first entry in said master list and for addressing a first scheduling list of said linked list of scheduling lists in response thereto, and for addressing a first queue of said linked list of queues using said addressed, first scheduling list.
Claim 2
Dependent Claim
177 words
A switch structure for use in a communications network, said switch structure comprising a processing element and associated memory for implementing the arbitration between plural queues, each belonging to a respective one of plural scheduling lists addressed by one of plural entries in a master list, said structure comprising: a control element; a linked list of one or more of said plural queues, each queue having a common first characteristic, said linked list of queues organized by said control element and addressed by a respective scheduling list; and a linked list of one or more of said plural scheduling lists, each scheduling list having a common second characteristic, said linked list of scheduling lists organized by said control element and addressed by said master list, wherein said control element is for recognizing the selection of a first entry in said master list and for addressing a first scheduling list of said linked list of scheduling lists in response thereto, and for addressing a first queue of said linked list of queues using said addressed, first scheduling list.
Claim 3
Independent Claim
160 words
A method of arbitrating, by a control element, between plural queues, each belonging to a respective one of plural scheduling lists addressed by one of plural entries in a master list, said method comprising: organizing, by said control element, one or more of said queues having a common first characteristic as a linked-list of queues addressed by said respective scheduling list; organizing, by said control element, one or more of said scheduling lists having a common second characteristic as a linked-list list of scheduling lists addressed by a first of said plural entries in said master list; recognizing, by said control element, the selection of said first entry in said master list; addressing a first scheduling list of said linked-list of scheduling lists having said common second characteristic by said control element using said first entry; and addressing a first queue of said linked-list of queues having said common first characteristic by said control element using said first scheduling list.
Claim 4
Independent Claim
160 words
A method of arbitrating, by a control element, between plural queues, each belonging to a respective one of plural scheduling lists addressed by one of plural entries in a master list, said method comprising: organizing, by said control element, one or more of said queues having a common first characteristic as a linked-list of queues addressed by said respective scheduling list; organizing, by said control element, one or more of said scheduling lists having a common second characteristic as a linked-list list of scheduling lists addressed by a first of said plural entries in said master list; recognizing, by said control element, the selection of said first entry in said master list; addressing a first scheduling list of said linked-list of scheduling lists having said common second characteristic by said control element using said first entry; and addressing a first queue of said linked-list of queues having said common first characteristic by said control element using said first scheduling list.
Claim 5
Dependent Claim
24 words
The structure of claim 1, wherein each of said plural entries of said master list is comprised of a head and tail pointer pair.
Claim 6
Dependent Claim
25 words
The structure of claim 3, wherein said linked list of scheduling lists is addressed by a respective one of said head and tail pointer pairs.
Claim 7
Dependent Claim
29 words
The structure of claim 1, wherein each scheduling list of said linked list of scheduling lists is comprised of at least one set of head, tail and next pointers.
Claim 8
Dependent Claim
26 words
The structure of claim 5, wherein said linked list of queues is addressed by a respective one of said sets of head, tail and next pointers.
Claim 9
Dependent Claim
27 words
The structure of claim 1, wherein each queue of said linked list of queues is comprised of at least one set of head, tail and next pointers.
Claim 10
Dependent Claim
82 words
The structure of claim 7, further comprising plural linked lists of at least one data cell pointer each, wherein each of said queue head pointers addresses a first data cell pointer in a respective data cell pointer linked list, wherein each of said queue tail pointers addresses a last data cell pointer in a respective data cell pointer linked list, and wherein each of said queue next pointers addresses a next consecutive linked queue, if any, in said linked list of queues.
Claim 11
Dependent Claim
46 words
The structure of claim 8, wherein each of said at least one data cell pointers further comprises: an address pointer to a stored data cell; and a next pointer to a next consecutive data cell pointer, if any, in a respective data cell pointer linked list.
Claim 12
Dependent Claim
51 words
The method of claim 2, wherein said step of organizing said linked-list of queues further comprises: initializing a next pointer for each queue in said linked-list of queues to point to a next sequential queue in said linked-list of queues, or if no next sequential queue exists, to a null value.
Claim 13
Dependent Claim
56 words
The method of claim 2, wherein said step of organizing said linked-list of scheduling lists further comprises: initializing a next pointer for each scheduling list in said linked-list of scheduling lists to point to a next sequential scheduling list in said linked-list of scheduling lists, or if no next scheduling list exists, to a null value.
Claim 14
Dependent Claim
64 words
The method of claim 2, wherein said step of addressing said first scheduling list of said linked-list of scheduling lists further comprises: setting a first master list entry head pointer to point to said first scheduling list in said linked-list of scheduling lists; setting a first master list entry tail pointer to point to a last scheduling list in said linked-list of scheduling lists.
Claim 15
Dependent Claim
56 words
The method of claim 2, wherein said step of addressing said first queue of said linked-list of queues further comprises: setting a first scheduling list head pointer to point to said first queue in said linked-list of queues; setting a first scheduling list tail pointer to point to a last queue in said linked-list of queues.
Claim 16
Dependent Claim
59 words
The method of claim 2 further comprising the steps of: rearranging said linked-list of queues after a prescribed event wherein said first queue of said linked-list of queues is made a last queue of said linked-list of queues, and a next sequential queue in said linked-list of queues is made a new first queue in said linked-list of queues.
Claim 17
Dependent Claim
57 words
The method of claim 14 wherein said step of rearranging said linked-list of queues further comprises the steps of: adjusting a first scheduling list tail pointer to point to said first queue of said linked-list of queues; and adjusting a first scheduling list head pointer to point to said next sequential queue in said linked-list of queues.
Claim 18
Dependent Claim
68 words
The method of claim 2 further comprising the steps of: rearranging said linked-list of scheduling lists after a prescribed event wherein said first scheduling list of said linked-list of scheduling lists is made a last scheduling list of said linked-list of scheduling lists, and a next sequential scheduling list in said linked-list of scheduling lists is made a new first scheduling list in said linked-list of scheduling lists.
Claim 19
Dependent Claim
64 words
The method of claim 16 wherein said step of rearranging said linked-list of scheduling lists further comprises the steps of: adjusting a first master list entry tail pointer to point to said first scheduling list of said linked-list of scheduling lists; and adjusting a first master list entry head pointer to point to said next sequential scheduling list in said linked-list of scheduling lists.
References Cited (Backward Citations)
US3974343A
Cited
US4603382A
Cited
US4584640A
Cited
US4993018A
Cited
US4821034A
Cited
US4920531A
Cited
US4878216A
Cited
US4837761A
Cited
US4870641A
Cited
US5198808A
Cited
US5083269A
Cited
US4953157A
Cited
US5093912A
Cited
US5422879A
Cited
US5130982A
Cited
US5119369A
Cited
US5197067A
Cited
US5084867A
Cited
US5163046A
Cited
US5185743A
Cited
US5379418A
Cited
US5544170A
Cited
US5553068A
Cited
US5309431A
Cited
US5151897A
Cited
US5146474A
Cited
US5303232A
Cited
US5341376A
Cited
US5301190A
Cited
US5335222A
Cited
US5420988A
Cited
US5283788A
Cited
US5414703A
Cited
US5394396A
Cited
US5271010A
Cited
US5497369A
Cited
US5268897A
Cited
US5301193A
Cited
US5375117A
Cited
US5590132A
Cited
US5287349A
Cited
US5479402A
Cited
US5339310A
Cited
US5295134A
Cited
US5487063A
Cited
US5361251A
Cited
US5257311A
Cited
US5321695A
Cited
US5287535A
Cited
US5363433A
Cited
US5513180A
Cited
US5313458A
Cited
US5265088A
Cited
US5280469A
Cited
US5432908A
Cited
US5319778A
Cited
US5623405A
Cited
US5179556A
Cited
US5544168A
Cited
US5459743A
Cited
US5535197A
Cited
US5301055A
Cited
US5291481A
Cited
US5509001A
Cited
US5535196A
Cited
US5301184A
Cited
US5398235A
Cited
US5523999A
Cited
US5432713A
Cited
US5361372A
Cited
US5509007A
Cited
US5570361A
Cited
US5357510A
Cited
US5544169A
Cited
US5546392A
Cited
US5394397A
Cited
US5400337A
Cited
US5379297A
Cited
US5305311A
Cited
US5390174A
Cited
US5479401A
Cited
US5323389A
Cited
US5355372A
Cited
US5577032A
Cited
US5530854A
Cited
US5504742A
Cited
US5432785A
Cited
US5463620A
Cited
US5452296A
Cited
US5436893A
Cited
US5289470A
Cited
US5625846A
Cited
US5465331A
Cited
US5425026A
Cited
US5425021A
Cited
US5521915A
Cited
US5485453A
Cited
US5504741A
Cited
US5546391A
Cited
US5446733A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-02-15 | 2002-08-17 | 2003-02-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-02-15 | 2006-08-17 | 2007-02-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-02-15 | 2010-08-17 | 2011-02-16 | $7700.00 | Window Closed / Lapsed |