US 5,872,769 AGranted

Linked list structures for multiple levels of control in an ATM switch

AssigneesFujitsu Network Communications, Inc., Fujitsu Limited

InventorsStephen A. Caldara, Stephen A. Hauser, Thomas A. Manning, Raymond L. Strouble

Life of this patent

Estimating the term…

Loading patent…

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.

Claims17

Dependent claims

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.

2 more elements

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.

3 more elements

Dependencies are inferred from the claim text.