Patent US5287346A successfully refreshed from Google Patents.
US5287346A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Packet switch
Assignee: Carnegie Mellon University
•
Filing: 1991-10-16
•
Granted: 1994-02-15
•
Expires: 2011-10-16
Abstract
Abstract The present invention pertains to a packet switch. The packet switch is comprised of a global shared-memory queue having M storage addresses in which respective packets are stored, where M≧3 and is an integer. The packet switch is also comprised of a presentation network having N input ports for receiving packets and providing the respective packets to desired addresses in the queue, where N≧3 and is an integer. The queue is in communication with the presentation network for receiving the packets. The packet switch is also comprised of a distribution network having J input ports, where J≧1, for receiving packets from the queue and providing them to the desired output ports. The distribution network is in communication with the queue. There is also means for ordering packets received by the presentation network such that packets received sequentially by the presentation network are caused to be provided by the presentation network to consecutive addresses in the queue. In a preferred embodiment, M=N=J, the ordering means includes a fetch-and-add circuit in communication with the queue such that it identifies addresses free for storage of packets being received by the presentation switch, and causes the packets being received by the presentation network to be placed into consecutive addresses free for storage; and the presentation network and the distribution network are each a Ω switch. In an even more preferred embodiment, the packet switch has multicast capability.
Inventors
- 👤 Ronald P. Bianchini, Jr.
- 👤 Hyong S. Kim
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 19:09
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04J; H04J3/00; H04J3/02; H04L49/00; H04L49/10; H04L49/104; H04L49/105; H04L49/106; H04L49/108; H04L49/15; H04L49/1553; H04L49/1561
Claims Analysis
Total Claims: 41
Claim 1
Independent Claim
191 words
A packet switch comprising: a shared memory queue having M interleaved storage banks having addresses at which respective packets are stored, where M is an integer ≧3; a presentation network having N input ports for receiving packets and providing the respective packets to desired addresses in the shared memory queue, where N is an integer, said queue in communication with the presentation network for receiving the packets; a distribution network having J output ports, for receiving packets from the queue and providing them to the desired output ports, wherein M=N=J, said distribution network in communication with the shared memory queue; means for simultaneously generating addresses for packets received by the presentation network such that packets received on ordered input ports by the presentation network are caused to be provided by the presentation network to consecutively ordered addresses in the queue, said means for simultaneously generating addresses including a fetch-and-add circuit in communication with the queue such that it identifies addresses free for storage of packets being received by the presentation network and causes the packets being received by the presentation network to be placed in consecutively ordered addresses free for storage.
Claim 2
Dependent Claim
191 words
A packet switch comprising: a shared memory queue having M interleaved storage banks having addresses at which respective packets are stored, where M is an integer ≧3; a presentation network having N input ports for receiving packets and providing the respective packets to desired addresses in the shared memory queue, where N is an integer, said queue in communication with the presentation network for receiving the packets; a distribution network having J output ports, for receiving packets from the queue and providing them to the desired output ports, wherein M=N=J, said distribution network in communication with the shared memory queue; means for simultaneously generating addresses for packets received by the presentation network such that packets received on ordered input ports by the presentation network are caused to be provided by the presentation network to consecutively ordered addresses in the queue, said means for simultaneously generating addresses including a fetch-and-add circuit in communication with the queue such that it identifies addresses free for storage of packets being received by the presentation network and causes the packets being received by the presentation network to be placed in consecutively ordered addresses free for storage.
Claim 3
Dependent Claim
23 words
A switch as described in claim 1 wherein the presentation network is an Ω switch and the distribution network is an Ω switch.
Claim 4
Dependent Claim
18 words
A switch as described in claim 2 wherein the presentation network is comprised of log 2 N stages.
Claim 5
Dependent Claim
14 words
A switch as described in claim 3 wherein the queue is a FIFO queue.
Claim 6
Dependent Claim
179 words
A packet switch comprising: a shared memory queue having M interleaved storage banks having addresses at which respective packets are stored, where M is an integer ≧3; a presentation network having N input ports for receiving packets and providing the respective packets to desired addresses in the shared memory queue, where N is an integer, said queue in communication with the presentation network for receiving the packets; a distribution network having J output ports, for receiving packets from the queue and providing them to the desired output ports, said distribution network in communication with the shared memory queue; means for simultaneously generating addresses for packets received by the presentation network such that packets received on ordered input ports by the presentation network are caused to be provided by the presentation network to consecutively ordered addresses in the queue; feedback means having F≧0 feedback channels in communication with said shared memory and said presentation network for restoring packets blocked from the distribution network; and means for providing multicast, said providing means in communication with the queue and the distribution network.
Claim 7
Dependent Claim
179 words
A packet switch comprising: a shared memory queue having M interleaved storage banks having addresses at which respective packets are stored, where M is an integer ≧3; a presentation network having N input ports for receiving packets and providing the respective packets to desired addresses in the shared memory queue, where N is an integer, said queue in communication with the presentation network for receiving the packets; a distribution network having J output ports, for receiving packets from the queue and providing them to the desired output ports, said distribution network in communication with the shared memory queue; means for simultaneously generating addresses for packets received by the presentation network such that packets received on ordered input ports by the presentation network are caused to be provided by the presentation network to consecutively ordered addresses in the queue; feedback means having F≧0 feedback channels in communication with said shared memory and said presentation network for restoring packets blocked from the distribution network; and means for providing multicast, said providing means in communication with the queue and the distribution network.
Claim 8
Dependent Claim
53 words
A switch as described in claim 5 wherein the providing means includes an Ω switch in communication with the queue to receive packets therefrom; and a second global shared priority queue in communication with the Ω switch and the distribution network for providing packets from the second priority queue to the distribution network.
Claim 9
Dependent Claim
27 words
A switch as described in claim 6 wherein the queue and second queue are each FIFO queues, and the presentation and distribution networks are each Ω switches.
Claim 10
Dependent Claim
110 words
A packet switch comprising: an N input port×N output port switching network, where N≧3 and is an integer and the network is an Ω network; N I/O devices, with each I/O device connected to a corresponding input port and a corresponding output port; N processors, each processor connected to a correspondence I/O devices; a shared input memory comprising N interleaved memory banks each memory bank connected to a corresponding processor and corresponding I/O device; and a means for simultaneously generating addresses for packets received on the input ports such that packets received on ordered input ports are caused to be provided to consecutively ordered addresses of the shared input memory.
Claim 11
Dependent Claim
110 words
A packet switch comprising: an N input port×N output port switching network, where N≧3 and is an integer and the network is an Ω network; N I/O devices, with each I/O device connected to a corresponding input port and a corresponding output port; N processors, each processor connected to a correspondence I/O devices; a shared input memory comprising N interleaved memory banks each memory bank connected to a corresponding processor and corresponding I/O device; and a means for simultaneously generating addresses for packets received on the input ports such that packets received on ordered input ports are caused to be provided to consecutively ordered addresses of the shared input memory.
Claim 12
Dependent Claim
253 words
An architecture for switching packets comprising: A. an input queue for storing received packets at ordered addresses of a shared memory, comprising: i. N≧3 input ports for receiving packets, ii. means for simultaneously generating unique sequentially ordered addresses for each of said received packets, iii. a shared memory having K interleaved banks for consecutively storing addressed packets, iv. a switching network for connecting said input ports to said shared memory, said switching network for connecting said input ports to said shared memory being an omega network; B. an output switching network for transmitting packets to their specified output port comprising: i. M≧3 output ports for transmitting packets, ii. a switching network for connecting the output of said shared memory to said output ports, said switching network for connecting the output of said shared memory to said output ports being an omega network, iii. means for detecting a packet from said shared memory to its proper output port; and C. a feedback network for restoring at sequential addresses in said shared memory of said input queue packets blocked from said output switching network, comprising: i. F≧0 feedback channels, ii. a switching network for connecting said output of said shared memory and said input, said switching network for connecting said output of said shared memory and said input being an omega network, iii. means for simultaneously generating unique sequentially ordered addresses for each of the feedback packets, such that no null spaces exist between consecutively stored packets, where N, K, M, and F are integers.
Claim 13
Dependent Claim
253 words
An architecture for switching packets comprising: A. an input queue for storing received packets at ordered addresses of a shared memory, comprising: i. N≧3 input ports for receiving packets, ii. means for simultaneously generating unique sequentially ordered addresses for each of said received packets, iii. a shared memory having K interleaved banks for consecutively storing addressed packets, iv. a switching network for connecting said input ports to said shared memory, said switching network for connecting said input ports to said shared memory being an omega network; B. an output switching network for transmitting packets to their specified output port comprising: i. M≧3 output ports for transmitting packets, ii. a switching network for connecting the output of said shared memory to said output ports, said switching network for connecting the output of said shared memory to said output ports being an omega network, iii. means for detecting a packet from said shared memory to its proper output port; and C. a feedback network for restoring at sequential addresses in said shared memory of said input queue packets blocked from said output switching network, comprising: i. F≧0 feedback channels, ii. a switching network for connecting said output of said shared memory and said input, said switching network for connecting said output of said shared memory and said input being an omega network, iii. means for simultaneously generating unique sequentially ordered addresses for each of the feedback packets, such that no null spaces exist between consecutively stored packets, where N, K, M, and F are integers.
Claim 14
Dependent Claim
211 words
An architecture for switching packets comprising: A. an input queue for storing received packets at ordered addresses of a shared memory, said input queue being a first-in, first-out queue, said input queue comprising: i. N≧3 input ports for receiving packets, ii. means for simultaneously generating unique sequentially ordered addresses for each of said received packets, iii. a shared memory having K interleaved banks for consecutively storing addressed packets, iv. a switching network for connecting said input ports to said shared memory; B. an output switching network for transmitting packets to their specified output port comprising: i. M≧3 output ports for transmitting packets, ii. a switching network for connecting the output of said shared memory to said output ports, iii. means for directing a packet from said shared memory to its proper output port; and C. a feedback network for restoring at sequential addresses in said shared memory of said input queue packets blocked from said output switching network, comprising: i. F≧0 feedback channels, ii. a switching network for connecting said output of said shared memory and said input, iii. means for simultaneously generating unique sequentially ordered addresses for each of the feedback packets, such that no null spaces exist between consecutively stored packets, where N, K, M, and F are integers.
Claim 15
Dependent Claim
211 words
An architecture for switching packets comprising: A. an input queue for storing received packets at ordered addresses of a shared memory, said input queue being a first-in, first-out queue, said input queue comprising: i. N≧3 input ports for receiving packets, ii. means for simultaneously generating unique sequentially ordered addresses for each of said received packets, iii. a shared memory having K interleaved banks for consecutively storing addressed packets, iv. a switching network for connecting said input ports to said shared memory; B. an output switching network for transmitting packets to their specified output port comprising: i. M≧3 output ports for transmitting packets, ii. a switching network for connecting the output of said shared memory to said output ports, iii. means for directing a packet from said shared memory to its proper output port; and C. a feedback network for restoring at sequential addresses in said shared memory of said input queue packets blocked from said output switching network, comprising: i. F≧0 feedback channels, ii. a switching network for connecting said output of said shared memory and said input, iii. means for simultaneously generating unique sequentially ordered addresses for each of the feedback packets, such that no null spaces exist between consecutively stored packets, where N, K, M, and F are integers.
Claim 16
Dependent Claim
217 words
An architecture for switching packets comprising: A. an input queue for storing received packets at ordered addresses of a shared memory, comprising: i. N≧3 input ports for receiving packets, ii. means for simultaneously generating unique sequentially ordered addresses for each of said received packets, said means for generating unique sequentially ordered addresses for each received packet comprising a combining fetch-and-add circuit iii. a shared memory having K interleaved banks for consecutively storing addressed packets, iv. a switching network for connecting said input ports to said shared memory; B. an output switching network for transmitting packets to their specified output port comprising: i. M≧3 output ports for transmitting packets, ii. a switching network for connecting the output of said shared memory to said output ports, iii. means for directing a packet from said shared memory to its proper output port; and C. a feedback network for restoring at sequential addresses in said shared memory of said input queue packets blocked from said output switching network, comprising: i. F≧0 feedback channels, ii. a switching network for connecting said output of said shared memory and said input, iii. means for simultaneously generating unique sequentially ordered addresses for each of the feedback packet, such that no null spaces exist between consecutively stored packets, where N, K, M, and F are integers.
Claim 17
Dependent Claim
217 words
An architecture for switching packets comprising: A. an input queue for storing received packets at ordered addresses of a shared memory, comprising: i. N≧3 input ports for receiving packets, ii. means for simultaneously generating unique sequentially ordered addresses for each of said received packets, said means for generating unique sequentially ordered addresses for each received packet comprising a combining fetch-and-add circuit iii. a shared memory having K interleaved banks for consecutively storing addressed packets, iv. a switching network for connecting said input ports to said shared memory; B. an output switching network for transmitting packets to their specified output port comprising: i. M≧3 output ports for transmitting packets, ii. a switching network for connecting the output of said shared memory to said output ports, iii. means for directing a packet from said shared memory to its proper output port; and C. a feedback network for restoring at sequential addresses in said shared memory of said input queue packets blocked from said output switching network, comprising: i. F≧0 feedback channels, ii. a switching network for connecting said output of said shared memory and said input, iii. means for simultaneously generating unique sequentially ordered addresses for each of the feedback packet, such that no null spaces exist between consecutively stored packets, where N, K, M, and F are integers.
Claim 18
Dependent Claim
272 words
An architecture for multicast switching packets comprising: A. an input queue for storing received packets at sequential addresses of a shared memory, comprising: i. N≧3 input ports for receiving packets, ii. means for uniquely addressing sequentially each of said received packets, iii. a shared memory having K interleaved banks for consecutively storing addresses packets, iv. a switching network for connecting said input ports to said shared memory; B. a multicast queue for replicating packets contained in said input queue and storing at sequential addresses of a second shared memory, comprising: i. K input ports for receiving packets, ii. means for uniquely addressing sequentially each of said replicated packets, iii. a shared memory having L interleaved banks for consecutively storing addressed packets, iv. a switching network for connecting the output of said input queue shared memory to said multicast queue shared memory; C. an output switching network for transmitting packets to their specified output port, comprising: i. M≧3 output ports for transmitting packets, ii. a switching network for connecting the output of said multicast queue shared memory to said output ports, iii. means for directing a packet from said multicast queue shared memory to its proper output port; and D. a feedback network, for restoring at sequential addresses in said multicast queue shared memory, packets blocked from said output switching network, comprising: i. F≧0 feedback channels, ii. a switching network for connecting said output of said multicast queue shared memory and said input, iii. means for uniquely addressing sequentially each of the feedback packets, such that no null spaces exist between consecutively stored packets, where N, K, L, M, and F are integers.
Claim 19
Dependent Claim
272 words
An architecture for multicast switching packets comprising: A. an input queue for storing received packets at sequential addresses of a shared memory, comprising: i. N≧3 input ports for receiving packets, ii. means for uniquely addressing sequentially each of said received packets, iii. a shared memory having K interleaved banks for consecutively storing addresses packets, iv. a switching network for connecting said input ports to said shared memory; B. a multicast queue for replicating packets contained in said input queue and storing at sequential addresses of a second shared memory, comprising: i. K input ports for receiving packets, ii. means for uniquely addressing sequentially each of said replicated packets, iii. a shared memory having L interleaved banks for consecutively storing addressed packets, iv. a switching network for connecting the output of said input queue shared memory to said multicast queue shared memory; C. an output switching network for transmitting packets to their specified output port, comprising: i. M≧3 output ports for transmitting packets, ii. a switching network for connecting the output of said multicast queue shared memory to said output ports, iii. means for directing a packet from said multicast queue shared memory to its proper output port; and D. a feedback network, for restoring at sequential addresses in said multicast queue shared memory, packets blocked from said output switching network, comprising: i. F≧0 feedback channels, ii. a switching network for connecting said output of said multicast queue shared memory and said input, iii. means for uniquely addressing sequentially each of the feedback packets, such that no null spaces exist between consecutively stored packets, where N, K, L, M, and F are integers.
Claim 20
Dependent Claim
10 words
An architecture as set forth in claim 12 wherein K≧N.
Claim 21
Dependent Claim
10 words
An architecture as set forth in claim 12 wherein M≧N.
Claim 22
Dependent Claim
10 words
An architecture as set forth in claim 12 wherein F≦N.
Claim 23
Dependent Claim
10 words
An architecture as set forth in claim 12 wherein L≧K.
Claim 24
Dependent Claim
18 words
An implementation of the switching architecture set forth in claim 12 wherein said switching networks are omega networks.
Claim 25
Dependent Claim
20 words
An implementation of the switching architecture set forth in claim 12 wherein said input queue is a first-in, first-out queue.
Claim 26
Dependent Claim
22 words
An implementation of the architecture of claim 12 wherein said means for uniquely addressing each received packet is a combining fetch-and-add circuit.
Claim 27
Dependent Claim
223 words
An architecture for a shared memory multicast copy network comprising: A. an input queue for storing received packets at sequential addresses of a shared memory, comprising: i. N≧3 input ports for receiving packets, ii. means for uniquely addressing sequentially each of said received packets, iii. a shared memory having K interleaved banks for consecutively storing addressed packets, iv. a switching network for connecting said input ports to said shared memory; B. a multicast queue for replicating packets contained in said input queue and storing at sequential addresses of a second shared memory to be considered for output, comprising: i. K input ports for receiving packets, ii. means for uniquely addressing sequentially each of said replicated packets, iii. a shared memory having L interleaved banks for consecutively storing addressed packets, iv. a switching network for connecting the output of said input queue shared memory to said multicast queue shared memory; and C. a feedback network for restoring at sequential addresses in said multicast queue shared memory, packets blocked from said output switching network, comprising: i. F≧0 feedback channels, ii. a switching network for connecting said output of said multicast queue shared memory and said input, iii. means for uniquely addressing sequentially each of the feedback packets, such that no null spaces exist between consecutively stored packets, where N, K, L, and F are integers.
Claim 28
Dependent Claim
223 words
An architecture for a shared memory multicast copy network comprising: A. an input queue for storing received packets at sequential addresses of a shared memory, comprising: i. N≧3 input ports for receiving packets, ii. means for uniquely addressing sequentially each of said received packets, iii. a shared memory having K interleaved banks for consecutively storing addressed packets, iv. a switching network for connecting said input ports to said shared memory; B. a multicast queue for replicating packets contained in said input queue and storing at sequential addresses of a second shared memory to be considered for output, comprising: i. K input ports for receiving packets, ii. means for uniquely addressing sequentially each of said replicated packets, iii. a shared memory having L interleaved banks for consecutively storing addressed packets, iv. a switching network for connecting the output of said input queue shared memory to said multicast queue shared memory; and C. a feedback network for restoring at sequential addresses in said multicast queue shared memory, packets blocked from said output switching network, comprising: i. F≧0 feedback channels, ii. a switching network for connecting said output of said multicast queue shared memory and said input, iii. means for uniquely addressing sequentially each of the feedback packets, such that no null spaces exist between consecutively stored packets, where N, K, L, and F are integers.
Claim 29
Dependent Claim
10 words
An architecture as set forth in claim 20 wherein K≧N.
Claim 30
Dependent Claim
10 words
An architecture as set forth in claim 20 wherein M≧N.
Claim 31
Dependent Claim
10 words
An architecture as set forth in claim 20 wherein F≦N.
Claim 32
Dependent Claim
18 words
An implementation of the switching architecture set forth in claim 20 wherein said switching networks are omega networks.
Claim 33
Dependent Claim
20 words
An implementation of the switching architecture set forth in claim 20 wherein said input queue is a first-in, first-out queue.
Claim 34
Dependent Claim
22 words
An implementation of the architecture of claim 20 wherein said means for uniquely addressing each received packet is a combining fetch-and-add circuit.
Claim 35
Dependent Claim
118 words
An N port memory, where N≧3, comprising: a global shared memory queue having M interleaved storage banks having addresses in which respective packets are stored, where M≧3 and is an integer; a presentation network having N input ports for receiving packets and providing the respective packets to desired addresses in the queue, where N≧3 and is an integer, said presentation network being an omega network, said queue in communication with the presentation network for receiving the packets; and means for simultaneously generating addresses for packets received by the presentation network such that packets received on ordered input ports by the presentation network are caused to be provided by the presentation network to consecutively ordered addresses in the queue.
Claim 36
Dependent Claim
118 words
An N port memory, where N≧3, comprising: a global shared memory queue having M interleaved storage banks having addresses in which respective packets are stored, where M≧3 and is an integer; a presentation network having N input ports for receiving packets and providing the respective packets to desired addresses in the queue, where N≧3 and is an integer, said presentation network being an omega network, said queue in communication with the presentation network for receiving the packets; and means for simultaneously generating addresses for packets received by the presentation network such that packets received on ordered input ports by the presentation network are caused to be provided by the presentation network to consecutively ordered addresses in the queue.
Claim 37
Dependent Claim
18 words
The N port memory of claim 27 wherein the means for simultaneously generating addresses includes a fetch-and-add circuit.
Claim 38
Dependent Claim
156 words
An N port memory, where N≧3, comprising: a global shared memory queue having M interleaved storage banks having addresses in which respective packets are stored, where M≧3 and is an integer; a presentation network having N input ports for receiving packets and providing the respective packets to desired addresses in the queue, where N≧3 and is an integer, said presentation network being an omega network, said queue in communication with the presentation network for receiving the packets; means for simultaneously generating addresses for packets received by the presentation network such that packets received on ordered input ports by the presentation network are caused to be provided by the presentation network to consecutively ordered addresses in the queue; and a distribution network having N input ports for receiving packets from consecutively ordered addresses in the queue, and providing the packets to desired output ports, the queue being in communication with the distribution network for receiving the packets.
Claim 39
Dependent Claim
156 words
An N port memory, where N≧3, comprising: a global shared memory queue having M interleaved storage banks having addresses in which respective packets are stored, where M≧3 and is an integer; a presentation network having N input ports for receiving packets and providing the respective packets to desired addresses in the queue, where N≧3 and is an integer, said presentation network being an omega network, said queue in communication with the presentation network for receiving the packets; means for simultaneously generating addresses for packets received by the presentation network such that packets received on ordered input ports by the presentation network are caused to be provided by the presentation network to consecutively ordered addresses in the queue; and a distribution network having N input ports for receiving packets from consecutively ordered addresses in the queue, and providing the packets to desired output ports, the queue being in communication with the distribution network for receiving the packets.
Claim 40
Dependent Claim
18 words
The N port memory of claim 29 wherein the means for simultaneously generating addresses includes a fetch-and-add circuit.
Claim 41
Dependent Claim
14 words
The N port memory claim 30 wherein the distribution network is an omega network.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-02-14 | 1997-08-16 | 1998-02-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-02-14 | 2001-08-16 | 2002-02-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-02-14 | 2005-08-16 | 2006-02-15 | $7700.00 | Window Closed / Lapsed |