Patent US5229991A successfully refreshed from Google Patents.
US5229991A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Packet switch with broadcasting capability for atm networks
Assignee: Washington University in St. Louis
•
Filing: 1991-01-30
•
Granted: 1993-07-20
•
Expires: 2011-01-30
Abstract
Abstract A packet switch having broadcasting capability for an ATM network includes a copy network stage having an increased number of copy outputs over the number of switch inputs and outputs to improve data throughput under worst case conditions, broadcast translation circuits with inputs connected to a multiple number of copy network outputs for multiplexing the data packets therethrough, partitioned memories for the broadcast translation circuits to reduce their memory requirements, and techniques for aligning broadcast copies of data packets for minimizing the number of copies each BTC must translate and thereby reduce each of their memories. All of these enhancements to a prior art broadcast ATM switch substantially reduce its memory requirements to thereby enable broadcasting in an ATM switch to be practically realized.
Inventors
- 👤 Jonathan S. Turner
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 22:07
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L49/00; H04L49/10; H04L49/104; H04L49/105; H04L49/106; H04L49/20; H04L49/201; H04L49/203
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
137 words
In a packet switch for replicating and routing packets of data between a plurality n of inputs and a plurality n of outputs, n being a positive integer, said packet switch operating in cycles, wherein in each cycle a set of packets is input and a subset of these packets is replicated and the copies output, the improvement comprising means for replicating the packets, said replicating means including a copy network connected between said switch inputs and switch outputs, said copy network having means for replicating said packets in accordance with a specified number of copies f, defined as the fanout of the packet, tagging each packet with a copy number, and transmitting said replicated, tagged copies through a number of copy network outputs, said copy network having at least a number of outputs greater than n.
Claim 2
Dependent Claim
137 words
In a packet switch for replicating and routing packets of data between a plurality n of inputs and a plurality n of outputs, n being a positive integer, said packet switch operating in cycles, wherein in each cycle a set of packets is input and a subset of these packets is replicated and the copies output, the improvement comprising means for replicating the packets, said replicating means including a copy network connected between said switch inputs and switch outputs, said copy network having means for replicating said packets in accordance with a specified number of copies f, defined as the fanout of the packet, tagging each packet with a copy number, and transmitting said replicated, tagged copies through a number of copy network outputs, said copy network having at least a number of outputs greater than n.
Claim 3
Dependent Claim
50 words
The packet switch of claim 1 wherein said replicating means includes a plurality of at least n broadcast translation circuits (BTC) connected between the outputs of said copy network and said switch outputs, said BTCs having means for decoding said copy number tags to thereby determine a packet's ultimate destination.
Claim 4
Dependent Claim
46 words
The packet switch of claim 2 wherein said copy network has N outputs and wherein each of said BTC's is connected to a plurality s of said N copy network outputs, said plurality of BTC's being equal to a number obtained by dividing N by s.
Claim 5
Dependent Claim
34 words
The packet switch of claim 3 wherein each BTC has means for converting the plurality of s data packets for sequentially translating them and means for reconverting the data packets for simultaneous outputs therefrom.
Claim 6
Dependent Claim
19 words
The packet switch of claim 4 wherein each of said BTCs is connected to copy network outputs N/s apart.
Claim 7
Dependent Claim
74 words
The packet switch of claim 2 wherein each BTC has a memory, said memory having two sets of entries, a first set of entries corresponding to those packets of data having a fanout ≦f 1 and a second set of entries corresponding to those packets of data having a fanout of >f 1 , f 1 being a positive integer and thereby defined as a critical fanout for characterizing said two sets of entries.
Claim 8
Dependent Claim
72 words
The packet switch of claim 6 wherein said first set of entries represents a matrix of B×f 1 entries where B is defined as the total number of packet switch connections with fanout greater than one and f 1 equals a pre-selected critical fanout, and said second set of entries represents a matrix of (B/f 1 ) ×n entries, where n is defined as the number of packet switch inputs or outputs.
Claim 9
Dependent Claim
23 words
The packet switch of claim 4 further comprising means for aligning the replicated, tagged copies of data packets with selected copy network outputs.
Claim 10
Dependent Claim
97 words
The packet switch of claim 8 wherein the copy network inputs and outputs are numbered and wherein the alignment means includes means for aligning the first copy of each group of copies produced from a common original packet with the particular numbered copy network output having an umber divisible by the next higher power of 2 greater than or equal to the original packet's fanout f, and wherein the copy network output number is also greater than or equal to 3F, where F is the cumulative fanout of the data packets appearing at lower-numbered copy network inputs.
Claim 11
Independent Claim
179 words
A method for implementing broadcasting in a packet switch which processes a maximum plurality n of incoming data packets along a plurality of numbered data paths in an ATM circuit, n being a positive integer, each of said data packets having a header which contains at least a fanout f, f being a positive integer, said method comprising the steps of: concentrating the data packets along consecutive, lowest numbered data paths, computing, for each data packet, the cumulative fanout F for all data packets being processed along lower numbered data paths and inserting F in each data packet header, determining which data packets can be transmitted through said packet switch without exceeding its capacity and discarding all other data packets in the same cycle, assigning copy network outputs to each data packet, replicating each data packet f times with a copy network, assigning systematically determined copy numbers and copy network outputs to each of said replicated data packets, said copy network outputs exceeding n in number, and sending multiple copies of replicated data packets to a single output buffer.
Claim 12
Independent Claim
179 words
A method for implementing broadcasting in a packet switch which processes a maximum plurality n of incoming data packets along a plurality of numbered data paths in an ATM circuit, n being a positive integer, each of said data packets having a header which contains at least a fanout f, f being a positive integer, said method comprising the steps of: concentrating the data packets along consecutive, lowest numbered data paths, computing, for each data packet, the cumulative fanout F for all data packets being processed along lower numbered data paths and inserting F in each data packet header, determining which data packets can be transmitted through said packet switch without exceeding its capacity and discarding all other data packets in the same cycle, assigning copy network outputs to each data packet, replicating each data packet f times with a copy network, assigning systematically determined copy numbers and copy network outputs to each of said replicated data packets, said copy network outputs exceeding n in number, and sending multiple copies of replicated data packets to a single output buffer.
Claim 13
Dependent Claim
32 words
The method of claim 10 wherein the step of assigning replicated data packets includes the step of aligning the replicated data packets with particular copy network outputs that are not necessarily consecutive.
Claim 14
Dependent Claim
92 words
The method of claim 11 wherein the copy network inputs and outputs are numbered and wherein the step of aligning includes the step of aligning the first copy of each group of packets produced form a common original packet with the numbered copy network output having a number divisible by the next higher power of 2 greater than or equal to the original packet's fanout f, and which is also greater than or equal to 3F, where F is the cumulative fanout of the data packets appearing at lower-numbered copy network inputs.
Claim 15
Dependent Claim
72 words
The method of claim 10 wherein the broadcast packet switch includes a plurality of broadcast translation circuits BTC's, each of said BTC's having a memory for storing translation information, and the step of translating includes the step of first determining whether the fanout f of each data packet is greater than, less than, or equal to a critical fanout f 1 before each of said BTC memories is accessed for translation information.
Claim 16
Dependent Claim
24 words
The method of claim 10 wherein the step of sending includes the step of sending replicated data packets to a single broadcast translator circuit.
Claim 17
Dependent Claim
23 words
The method of claim 14 further comprising the step of translating each data packet by its copy number to determine its virtual address.
Claim 18
Dependent Claim
38 words
The method of claim 15 wherein the step of translating the copy numbers of each data packet comprises the step of translating a plurality s of data packet copy numbers during each cycle, s being a positive integer.
Claim 19
Dependent Claim
111 words
In a packet switch for replicating and routing packets of data between a plurality n of inputs and a plurality n of outputs, n being a positive integer, said packet switch operating in cycles, wherein in each cycle a set of packets is input and a subset of these packets is replicated and the copies output, the improvement comprising means for implementing broadcasting, said broadcasting means including a copy network having at least a plurality n of inputs and a number of outputs greater than n to ensure that the number of copies output is greater than or equal to n, or the total number of copies replicated, whichever is smaller.
Claim 20
Dependent Claim
111 words
In a packet switch for replicating and routing packets of data between a plurality n of inputs and a plurality n of outputs, n being a positive integer, said packet switch operating in cycles, wherein in each cycle a set of packets is input and a subset of these packets is replicated and the copies output, the improvement comprising means for implementing broadcasting, said broadcasting means including a copy network having at least a plurality n of inputs and a number of outputs greater than n to ensure that the number of copies output is greater than or equal to n, or the total number of copies replicated, whichever is smaller.
Claim 21
Dependent Claim
68 words
The packet switch of claim 17 wherein said broadcasting means includes a plurality of broadcast translation circuits BTC's, said BTC's being connected to the copy network outputs and having means for translating information contained in each data packet into a virtual address, each BTC being connected to a plurality s of copy network outputs and having means for processing a plurality s of data packets in one cycle.
Claim 22
Dependent Claim
45 words
The packet switch of claim 18 wherein said data packet processing means includes means for sequencing said plurality s of data packets into a serial data stream and means for realigning said data stream after its translation by each of said BTC's for parallel output.
Claim 23
Dependent Claim
69 words
The packet switch of claim 19 wherein each BTC has a memory, said memory having two sets of entries, a first set of entries corresponding to those packets of data having a fanout ≦ a fanout f 1 and a second set of entries corresponding to those packets of data having a fanout of >f 1 , f 1 being a positive integer and defined as the critical fanout.
Claim 24
Dependent Claim
68 words
The packet switch of claim 20 wherein said first set of entries represents a matrix of B×f 1 where B is defined as the total number of packet switch connections with fanout greater than one and f 1 equals a pre-selected critical fanout, and said second set of entries represents a matrix (B/f 1 )×n, where n is defined as the number of packet switch inputs or outputs.
Claim 25
Dependent Claim
65 words
The packet switch of claim 17 wherein said copy network has means for replicating each data packet in accordance with each data packet's fanout f, f being a positive integer, and tagging each of said data packets with a copy number representative of its ultimate destination, and further comprising means for aligning the replicated data packets with their copy numbers along selected copy network outputs.
Claim 26
Dependent Claim
93 words
The packet switch of claim 22 wherein the copy network inputs and outputs are each numbered and wherein the alignment means includes means for aligning the first copy of each group of packets produced from a common original packet with the numbered copy network output having a number divisible by the next higher power of 2 grater than or equal to the original packet's fanout f, and which is also greater than or equal to 3F, where F is the cumulative fanout of the data packets appearing at lower numbered copy network inputs.
Claim 27
Dependent Claim
83 words
In a packet switch for replicating and routing packets of data between a plurality n of inputs and a plurality n of outputs, n being a positive integer, the improvement comprising means for implementing broadcasting in said packet switch, said broadcasting means including a plurality of copy networks connected between said plurality of inputs and plurality of outputs, said copy networks having means for replicating data packets, said plurality of copy networks having a sum total of copy network outputs greater than n.
Claim 28
Dependent Claim
83 words
In a packet switch for replicating and routing packets of data between a plurality n of inputs and a plurality n of outputs, n being a positive integer, the improvement comprising means for implementing broadcasting in said packet switch, said broadcasting means including a plurality of copy networks connected between said plurality of inputs and plurality of outputs, said copy networks having means for replicating data packets, said plurality of copy networks having a sum total of copy network outputs greater than n.
Claim 29
Dependent Claim
50 words
The packet switch of claim 24 wherein the broadcasting means includes a plurality of parallel switch planes for processing data packets, each of said switch planes having a plurality of stages mirroring the other of said switch planes, and means for dividing incoming data packets amongst said parallel switch planes.
References Cited (Backward Citations)
US4516238A
Cited
US4596010A
Cited
US4849968A
Cited
US4969146A
Cited
US4991168A
Cited
US5007070A
Cited
US5050164A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-07-19 | 1997-01-18 | 1997-07-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-07-19 | 2001-01-18 | 2001-07-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-07-19 | 2005-01-18 | 2005-07-20 | $7700.00 | Window Closed / Lapsed |