US5689506A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multicast routing in multistage networks
Assignee: Nokia of America Corp
•
Filing: 1996-01-16
•
Granted: 1997-11-18
•
Expires: 2016-01-16
Abstract
Abstract Multicasting of an ingress cell received at one of a plurality of input ports is provided through a multistage switching network to one or more of a plurality of output ports. An ingress cell including a data payload and information identifying output ports of the network is received at one of the input ports of a first stage of the network. A determination is made of the minimum number of first output ports of the first stage of the network to which a single copy of the ingress cell is to be outputted to enable the ingress cell to reach all of the identified output ports. The single copy of the ingress cell is then routed to the minimum number of first output ports of the first stage of the network.
Inventors
- 👤 Fabio Massimo Chiussi
- 👤 Joseph George Kneuer
- 👤 Vijay Pochampalli Kumar
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 09:25
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L49/00; H04L49/15; H04L49/1553; H04L49/1576; H04L49/20; H04L49/201; H04L49/203; H04L49/30; H04L49/3081; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5635; H04L2012/5638; H04L2012/5646; H04L2012/5651; H04L2012/5652; H04L2012/5678; H04L2012/5681
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
203 words
Apparatus for multicasting an ingress cell received at one of a plurality of input ports connectable through a self-routing multistage network to one or more of a plurality of output ports, comprising: means for receiving, at one of the input ports of a first stage of the network, an ingress cell including a data payload and information identifying output ports of said network to which the ingress cell is to be outputted; means for determining a minimum number of next stage buffered switching elements of said network to which a copy of the ingress cell is to be outputted to enable the ingress cell to reach all of the identified output ports; and means for routing each copy of the ingress cell to exactly one output port of the multistage network associated with said next stage switching element; the routing means optionally including one or more memoryless switching elements, located between buffered switch elements of different stages of the multistage network, through which one or more ingress cells are concurrently routed using means for assuring a sequentially ordered delivery of ingress cells to the respective output port and any other one or more ports of the multistage network identified in the multicast connection.
Claim 2
Dependent Claim
203 words
Apparatus for multicasting an ingress cell received at one of a plurality of input ports connectable through a self-routing multistage network to one or more of a plurality of output ports, comprising: means for receiving, at one of the input ports of a first stage of the network, an ingress cell including a data payload and information identifying output ports of said network to which the ingress cell is to be outputted; means for determining a minimum number of next stage buffered switching elements of said network to which a copy of the ingress cell is to be outputted to enable the ingress cell to reach all of the identified output ports; and means for routing each copy of the ingress cell to exactly one output port of the multistage network associated with said next stage switching element; the routing means optionally including one or more memoryless switching elements, located between buffered switch elements of different stages of the multistage network, through which one or more ingress cells are concurrently routed using means for assuring a sequentially ordered delivery of ingress cells to the respective output port and any other one or more ports of the multistage network identified in the multicast connection.
Claim 3
Dependent Claim
33 words
The apparatus of claim 1 including a second stage of said network connected to the first output ports of said first stage, said second stage being implemented the same as the first stage.
Claim 4
Dependent Claim
19 words
The apparatus of claim 1 wherein the identifying information includes a bit map segment to identify the output ports.
Claim 5
Dependent Claim
73 words
The apparatus of claim 3 wherein said network includes at least two cascaded stages, each stage implemented the same as the first stage, the bit map segment is used by the first stage to identify the minimum number of first output ports, and a portion of the bit map segment is used by a second stage to identify any one or more output ports of the second stage to receive the ingress cell.
Claim 6
Dependent Claim
78 words
The apparatus of claim 3 wherein said network includes at least two cascaded stages, each stage implemented the same as the first stage, a first subset of the bit map segment is used by the first stage to identify the minimum number of first output ports, and a second subset of the bit map segment is used by a second stage to identify any one or more output ports of the second stage to receive the ingress cell.
Claim 7
Dependent Claim
84 words
The apparatus of claim 1 wherein the identifying information includes a bit map segment to identify the output ports and a control segment, wherein said network includes at least two stages, and wherein the bit map segment is used by the first stage to identify the minimum number of first output ports, and wherein a second bit map segment is generated using the control segment, the second bit map segment being used by the second stage to identify output ports of the second stage.
Claim 8
Dependent Claim
33 words
The apparatus of claim 6 wherein the second stage includes multiple sections, wherein the control segment is a connection tag which uniquely identifies the output ports of each section of the second stage.
Claim 9
Dependent Claim
20 words
The apparatus of claim 2 wherein either one or both of the first and second stages is a multistage network.
Claim 10
Dependent Claim
43 words
The apparatus of claim 1 further including means for storing the data payload in an available cell buffer located in one or more stages of said network, and a plurality of linked list output queues, at least one for each the output ports.
Claim 11
Dependent Claim
178 words
The apparatus of claim 1 wherein one or more of the stages of the network includes means for storing the data payload in an available cell buffer; a plurality of linked list output queues, at least one for each of the output ports; a reference counter, associated with each cell buffer, for storing a number equal to the number of ports to which that ingress cell is to be outputted; means for interpreting the bitmap segment to identify output ports to which the data payload is to be delivered and for making an entry into one or more linked list output queues; means for transmitting, to each of the identified output ports, one copy of the data payload according to a sequence determined by the entries in the corresponding linked list output queue; and means for deleting, at each of the linked list output queues, an entry therefrom when the payload is outputted to an identified output port and decrementing the reference counter by one, and for making available the cell buffer when the reference counter equals zero.
Claim 12
Dependent Claim
21 words
The apparatus of claim 1 wherein the cell buffer and the linked list output queue are located in the same memory.
Claim 13
Dependent Claim
23 words
The apparatus of claim 1 wherein the linked list output queues of each of the output ports are located in the same memory.
Claim 14
Dependent Claim
27 words
The apparatus of claim 1 wherein a separate memory is dedicated to each output port and wherein entries into the linked list output queues are done concurrently.
Claim 15
Dependent Claim
35 words
The apparatus of claim 1 wherein the bitmap segment is put into a separate queue and the entries are made at a rate that is equal to or faster than an ingress cell receive rate.
Claim 16
Dependent Claim
31 words
The apparatus of claim 1 wherein entries into the linked list output queues occur at a rate equal to the ingress cell receive rate multiplied by the number of output ports.
Claim 17
Dependent Claim
41 words
The apparatus of claim 1 wherein at least one output port includes a plurality of linked list output queues and wherein the processing of each of the singly linked list output queues for said at least one output port is independent.
Claim 18
Dependent Claim
22 words
The apparatus of claim 1 wherein the processing is based on priority as determined by header data included in the ingress cell.
Claim 19
Dependent Claim
32 words
The apparatus of claim 1 further including a separate linked list output queue for a received unicast ingress cell and a separate linked list output queue for a received multicast ingress cell.
Claim 20
Independent Claim
211 words
A method of multicasting an ingress cell received at one of a plurality of input ports connectable through a multistage network to one or more of a plurality of output ports, said method comprising the steps of (a) receiving, at one of the input ports of a first stage of the network, an ingress cell including a data payload and information identifying output ports of said network to which the ingress cell is to be outputted; (b) determining a minimum number of next stage buffered switching elements of said network to which a copy of the ingress cell is to be outputted to enable the ingress cell to reach all of the identified output ports; and (c) routing each copy of the ingress cell to exactly one output port of the multistage network associated with said next stage switching element; the routing step optionally including randomly routing the ingress cell through one or more memoryless switching elements, located between buffered switch elements of different stages of the multistage network, through which one or more ingress cells are concurrently routed using means for assuring a sequentially ordered delivery of ingress cells to the respective output port and any other one or more ports of the multistage network identified in the multicast connection.
Claim 21
Independent Claim
211 words
A method of multicasting an ingress cell received at one of a plurality of input ports connectable through a multistage network to one or more of a plurality of output ports, said method comprising the steps of (a) receiving, at one of the input ports of a first stage of the network, an ingress cell including a data payload and information identifying output ports of said network to which the ingress cell is to be outputted; (b) determining a minimum number of next stage buffered switching elements of said network to which a copy of the ingress cell is to be outputted to enable the ingress cell to reach all of the identified output ports; and (c) routing each copy of the ingress cell to exactly one output port of the multistage network associated with said next stage switching element; the routing step optionally including randomly routing the ingress cell through one or more memoryless switching elements, located between buffered switch elements of different stages of the multistage network, through which one or more ingress cells are concurrently routed using means for assuring a sequentially ordered delivery of ingress cells to the respective output port and any other one or more ports of the multistage network identified in the multicast connection.
Claim 22
Dependent Claim
21 words
The method of claim 19 including the step of repeating steps (b) and (c) for a second stage of said network.
Claim 23
Dependent Claim
21 words
The method of claim 19 including the step of repeating steps (b) and (c) for all subsequent stages of said network.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-11-17 | 2001-05-19 | 2001-11-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-11-17 | 2005-05-19 | 2005-11-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-11-17 | 2009-05-19 | 2009-11-18 | $7700.00 | Window Closed / Lapsed |