US5440546A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Packet switch
Assignee: Carnegie Mellon University
•
Filing: 1993-10-22
•
Granted: 1995-08-08
•
Expires: 2013-10-22
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-29 09:36
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: 23
Claim 1
Independent Claim
169 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, the shared memory queue in communication with the presentation network for receiving the packets; a distribution network having J output ports, for receiving packets from the shared memory queue and providing them to the desired output ports, the 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 shared memory queue; and feedback means having F≧0 feedback channels in communication with the shared memory and the presentation network for restoring packets blocked from the distribution network.
Claim 2
Dependent Claim
169 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, the shared memory queue in communication with the presentation network for receiving the packets; a distribution network having J output ports, for receiving packets from the shared memory queue and providing them to the desired output ports, the 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 shared memory queue; and feedback means having F≧0 feedback channels in communication with the shared memory and the presentation network for restoring packets blocked from the distribution network.
Claim 3
Dependent Claim
9 words
A switch as described in claim 1 whereby M=N.
Claim 4
Dependent Claim
9 words
A switch as described in claim 2 wherein M=N=J.
Claim 5
Dependent Claim
105 words
A packet switch comprising: an N input port x N output port switching network, where N>3 and is an integer; 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 device; 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 6
Dependent Claim
105 words
A packet switch comprising: an N input port x N output port switching network, where N>3 and is an integer; 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 device; 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 7
Dependent Claim
117 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 shared memory queue, where N≧3 and is an integer, the shared memory 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 shared memory queue.
Claim 8
Dependent Claim
117 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 shared memory queue, where N≧3 and is an integer, the shared memory 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 shared memory queue.
Claim 9
Dependent Claim
200 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 the received packets, iii. a shared memory having K interleaved banks for consecutively storing addressed packets, iv. a switching network for connecting the input ports to the 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 the shared memory to the output ports, iii. means for directing a packet from the shared memory to its proper output port; and C. a feedback network for restoring at sequential addresses in the shared memory of the input queue packets blocked from the output switching network, comprising: i. F>0 feedback channels, ii. a switching network for connecting the output of the 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 10
Dependent Claim
200 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 the received packets, iii. a shared memory having K interleaved banks for consecutively storing addressed packets, iv. a switching network for connecting the input ports to the 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 the shared memory to the output ports, iii. means for directing a packet from the shared memory to its proper output port; and C. a feedback network for restoring at sequential addresses in the shared memory of the input queue packets blocked from the output switching network, comprising: i. F>0 feedback channels, ii. a switching network for connecting the output of the 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 11
Dependent Claim
10 words
The architecture as set forth in claim 6 wherein K≧N.
Claim 12
Dependent Claim
10 words
The architecture as set forth in claim 6 wherein M≧N.
Claim 13
Dependent Claim
10 words
The architecture as set forth in claim 6 wherein F≦N.
Claim 14
Dependent Claim
51 words
The N port memory of claim 5 further comprising a distribution Network having N input ports for receiving packets from consecutively ordered addresses in the shared memory queue, and providing the packets to desired output ports, the shared memory queue being in communication with the distribution network for receiving the packets.
Claim 15
Dependent Claim
250 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 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: 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 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, said switching network for connecting said output of said shared memory and said input being an omega network, iii. means for 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
250 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 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: 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 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, said switching network for connecting said output of said shared memory and said input being an omega network, iii. means for 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 17
Dependent Claim
209 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 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 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 18
Dependent Claim
209 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 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 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 19
Dependent Claim
216 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 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 packets, such that no null spaces exist between consecutively stored packets, where N, K, M, and F are integers.
Claim 20
Dependent Claim
216 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 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 packets, such that no null spaces exist between consecutively stored packets, where N, K, M, and F are integers.
Claim 21
Dependent Claim
127 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, wherein M≧3 and is an integer, and wherein the shared memory queue is a first-in, first-out queue; 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>3 and is an integer, the shared memory queue in communication with the presentation network for receiving the packets; and means for 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 shared memory queue.
Claim 22
Dependent Claim
127 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, wherein M≧3 and is an integer, and wherein the shared memory queue is a first-in, first-out queue; 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>3 and is an integer, the shared memory queue in communication with the presentation network for receiving the packets; and means for 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 shared memory queue.
Claim 23
Dependent Claim
18 words
The N port memory of claim 5 wherein the global shared memory queue is a first-in, first-out queue.
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) | 1998-08-07 | 1999-02-06 | 1999-08-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-08-07 | 2003-02-06 | 2003-08-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-08-07 | 2007-02-06 | 2007-08-08 | $7700.00 | Window Closed / Lapsed |