EP0785699A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Multicast routing in multistage networks
Assignee: AT&T Inc
•
Filing: 1997-01-07
•
Granted: —
•
Expires: 2017-01-07
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. <IMAGE>
Inventors
- 👤 Fabio Massimo Chiussi
- 👤 Vijay Pochampalli Kumar
- 👤 Joseph George Kneuer
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-31 02:36
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: 21
Claim 1
Independent Claim
141 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 first output ports of the first stage of said 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; and means for routing the single copy of the ingress cell to the minimum number of first output ports of the first stage of said network.
Claim 2
Dependent Claim
32 words
The apparatus of claim 1 including a second stage of said network connected to the first output ports of said first stage and implemented using the same means as the first stage.
Claim 3
Dependent Claim
19 words
The apparatus of claim 1 wherein the identifying information includes a bit map segment to identify the output ports.
Claim 4
Dependent Claim
75 words
The apparatus of claim 3 wherein said network includes at least two cascaded stages, each stage implemented using the same means 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 the one or more output ports of the second stage to receive the ingress cell.
Claim 5
Dependent Claim
80 words
The apparatus of claim 3 wherein said network includes at least two cascaded stages, each stage implemented using the same means 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 the one or more output ports of the second stage to receive the ingress cell.
Claim 6
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 7
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 8
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 9
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 10
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 11
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 12
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 13
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 14
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 15
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 16
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 inked list output queues for said at least one output port is independent.
Claim 17
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 18
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 19
Independent Claim
143 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 first output ports of the first stage of said 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; and (c) routing the single copy of the ingress cell to the minimum number of first output ports of the first stage of said network.
Claim 20
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 21
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
Maintenance schedule is calculated for granted US utility patents.