Patent US4813038A successfully refreshed from Google Patents.
US4813038A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Non-blocking copy network for multicast packet switching
Assignee: Iconectiv LLC
•
Filing: 1987-06-29
•
Granted: 1989-03-14
•
Expires: 2007-06-29
Abstract
Abstract A copy network capable of packet replication is disclosed. An encoding process transforms the set of copy numbers, specified in the headers of incoming packets, into a set of monotone address intervals which form new packet headers. This process is carried out by a running adder network and a set of dummy address encoders. A broadcast banyan network performs the packet replication according to a Boolean Interval Splitting Algorithm. Finally, trunk number translators determine the destinations of individual copies. The copy network is self-routing, non-blocking and has a constant packet latency.
Inventors
- 👤 Tony T. Lee
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 15:29
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/02; H04L12/16; H04L12/18; H04L12/1886; H04L49/00; H04L49/30; H04L49/3009; H04L49/10; H04L49/101; H04L49/15; H04L49/1507; H04L49/20; H04L49/201; H04L49/25
Claims Analysis
Total Claims: 50
Claim 1
Independent Claim
41 words
A copy network for copying data packets comprising: encoding means for converting copy numbers in the headers of incoming packets into address intervals, and decoding means for replicating said packets by routing said packets to the addresses contained in the intervals.
Claim 2
Dependent Claim
41 words
A copy network for copying data packets comprising: encoding means for converting copy numbers in the headers of incoming packets into address intervals, and decoding means for replicating said packets by routing said packets to the addresses contained in the intervals.
Claim 3
Dependent Claim
18 words
The network of claim 1 wherein said encoding means comprises a running adder network and dummy address encoders.
Claim 4
Dependent Claim
20 words
The network of claim 2 wherein said decoding means comprises a banyan network whose nodes are capable of packet replication.
Claim 5
Dependent Claim
65 words
A copy network for copying data packets comprising: means for providing running sums of copy numbers contained in the headers of data packets arriving at said copy network, means for utilizing said running sums to provide the header of each packet with an address interval, and means for replicating said packets including a network for routing said packets to the addresses contained in said intervals.
Claim 6
Dependent Claim
65 words
A copy network for copying data packets comprising: means for providing running sums of copy numbers contained in the headers of data packets arriving at said copy network, means for utilizing said running sums to provide the header of each packet with an address interval, and means for replicating said packets including a network for routing said packets to the addresses contained in said intervals.
Claim 7
Dependent Claim
17 words
The network of claim 4 wherein said means for providing said sums is a top-down adder network.
Claim 8
Dependent Claim
17 words
The network of claim 4 wherein said means for providing said sums is as bottom-up adder network.
Claim 9
Dependent Claim
25 words
The copy network of claim 4 wherein said means for providing said sums comprises a top-down running adder network and a bottom-up running adder network.
Claim 10
Dependent Claim
18 words
The copy network of claim 4 wherein said means for utilizing said sums comprises a set of encoders.
Claim 11
Dependent Claim
20 words
The copy network of claim 4 wherein said replicating means includes a network having the topology of a banyan network.
Claim 12
Dependent Claim
21 words
The copy network of claim 4 wherein said replicating means includes a banyan network whose nodes are capable of packet replication.
Claim 13
Dependent Claim
24 words
The copy network of claim 9 wherein said replicating means comprises a plurality of binary tree networks and a plurality of square banyan networks.
Claim 14
Dependent Claim
66 words
A copy network for simultaneously providing copies of a plurality of data packets comprising means for transforming a set of copy numbers specified in the headers of said data packets into a set of monotone address intervals which form new packet headers, and packet replication means including an array of interconnected identical nodes capable of replicating packets in accordance with information contained in said address interval.
Claim 15
Dependent Claim
66 words
A copy network for simultaneously providing copies of a plurality of data packets comprising means for transforming a set of copy numbers specified in the headers of said data packets into a set of monotone address intervals which form new packet headers, and packet replication means including an array of interconnected identical nodes capable of replicating packets in accordance with information contained in said address interval.
Claim 16
Dependent Claim
23 words
The copy network of claim 12 wherein said network further includes trunk number translators located at the output of said packet replication means.
Claim 17
Dependent Claim
101 words
A copy network for copying data packets comprising a running adder network for providing running sums of copy numbers specified in the headers of incoming packets, a set of dummy address encoders for utilizing said sums to provide each of said packets with an address interval, each of said address intervals containing a number of addresses equal to the original copy number, a broadcast network for replicating said packets by routing said packets to the addresses contained in said intervals, and translator means located at the outputs of said broadcast network for providing packets leaving said broadcast network with destination addresses.
Claim 18
Dependent Claim
101 words
A copy network for copying data packets comprising a running adder network for providing running sums of copy numbers specified in the headers of incoming packets, a set of dummy address encoders for utilizing said sums to provide each of said packets with an address interval, each of said address intervals containing a number of addresses equal to the original copy number, a broadcast network for replicating said packets by routing said packets to the addresses contained in said intervals, and translator means located at the outputs of said broadcast network for providing packets leaving said broadcast network with destination addresses.
Claim 19
Dependent Claim
14 words
The copy network of claim 14 wherein said broadcast network is a banyan network.
Claim 20
Dependent Claim
24 words
The copy network of claim 14 wherein said broadcast network comprises a plurality of binary tree networks and a plurality of square banyan networks.
Claim 21
Dependent Claim
24 words
The copy network of claim 14 wherein said copy network includes a Batcher sorting network located at the inputs to said running adder network.
Claim 22
Dependent Claim
27 words
The copy network of claim 14 further including a concentrator network for insuring that there are no inactive inputs between two active inputs of said broadcast network.
Claim 23
Dependent Claim
19 words
The copy network of claim 18 wherein said concentrator network is located at the inputs of said broadcast network.
Claim 24
Dependent Claim
65 words
A copy network for providing copies of data packets comprising: means for transforming a set of copy numbers specified in the headers of said data packets into a set of monotone broadcast network output address intervals which form new data packet headers, and a broadcast network for replicating said packets by routing each packet to the broadcast network output addresses contained in its associated interval.
Claim 25
Dependent Claim
65 words
A copy network for providing copies of data packets comprising: means for transforming a set of copy numbers specified in the headers of said data packets into a set of monotone broadcast network output address intervals which form new data packet headers, and a broadcast network for replicating said packets by routing each packet to the broadcast network output addresses contained in its associated interval.
Claim 26
Dependent Claim
15 words
The copy network of claim 20 wherein said broadcast network is a broadcast banyan network.
Claim 27
Dependent Claim
37 words
A copy network for copying data packets comprising, means for providing data packets whose headers include address intervals, and a network for replicating said packets by routing each packet to the addresses contained in its associated interval.
Claim 28
Dependent Claim
37 words
A copy network for copying data packets comprising, means for providing data packets whose headers include address intervals, and a network for replicating said packets by routing each packet to the addresses contained in its associated interval.
Claim 29
Dependent Claim
45 words
The copy network of claim 22 wherein said replicating network comprises: 2 M inputs, 2 N outputs, 2 M binary tree networks, each of said binary tree networks having N-M stages, and 2 N-M square banyan networks, each of said banyan networks having M stages.
Claim 30
Dependent Claim
40 words
A copy network for copying data packets comprising: means for providing data packets whose headers include address intervals, and packet replication means including an array of interconnected nodes capable of replicating packets by utilizing information provided by said address intervals.
Claim 31
Dependent Claim
40 words
A copy network for copying data packets comprising: means for providing data packets whose headers include address intervals, and packet replication means including an array of interconnected nodes capable of replicating packets by utilizing information provided by said address intervals.
Claim 32
Independent Claim
47 words
A method for copying data packets comprising the steps of: converting copy numbers in the headers of incoming packets into address intervals, and replicating said packets by routing said packets through a network whose nodes are capable of packet replication to the addresses contained in said intervals.
Claim 33
Independent Claim
47 words
A method for copying data packets comprising the steps of: converting copy numbers in the headers of incoming packets into address intervals, and replicating said packets by routing said packets through a network whose nodes are capable of packet replication to the addresses contained in said intervals.
Claim 34
Independent Claim
63 words
A method for copying data packets comprising the steps of: providing running sums of copy numbers contained in the headers of arriving packets, utilizing said running sums to provide the header of each packet with an address interval, and replicating said packets by routing said packets through a network whose nodes are capable of packet replication to the addresses contained in said intervals.
Claim 35
Independent Claim
63 words
A method for copying data packets comprising the steps of: providing running sums of copy numbers contained in the headers of arriving packets, utilizing said running sums to provide the header of each packet with an address interval, and replicating said packets by routing said packets through a network whose nodes are capable of packet replication to the addresses contained in said intervals.
Claim 36
Dependent Claim
17 words
The method of claim 26 wherein said replicating step comprises routing said packets through a banyan network.
Claim 37
Independent Claim
59 words
A method for simultaneously copying a plurality of data packets comprising the steps of: transforming a set of copy numbers specified in the headers of said data packets into a set of monotone address intervals which form new packet headers, and replicating said packets in an array of interconnected nodes by utilizing the information provided by said address intervals.
Claim 38
Independent Claim
59 words
A method for simultaneously copying a plurality of data packets comprising the steps of: transforming a set of copy numbers specified in the headers of said data packets into a set of monotone address intervals which form new packet headers, and replicating said packets in an array of interconnected nodes by utilizing the information provided by said address intervals.
Claim 39
Dependent Claim
28 words
The method of claim 28 wherein said method further comprises the step of: providing each packet resulting from said replicating step with a trunk number or destination address.
Claim 40
Independent Claim
80 words
A method for copying data packets comprising: providing running sums of copy numbers specified in the headers of incoming packets, utilizing said running sums to provide each packet with an address interval, each address interval containing a number of addresses equal to the original copy number, replicating said packets by routing said packets through a network whose nodes are capable of packet replication to the addresses specified in the intervals, and providing packets leaving said replication network with destination addresses.
Claim 41
Independent Claim
80 words
A method for copying data packets comprising: providing running sums of copy numbers specified in the headers of incoming packets, utilizing said running sums to provide each packet with an address interval, each address interval containing a number of addresses equal to the original copy number, replicating said packets by routing said packets through a network whose nodes are capable of packet replication to the addresses specified in the intervals, and providing packets leaving said replication network with destination addresses.
Claim 42
Independent Claim
64 words
A method for copying data packets comprising the steps of: transforming a set of copy numbers specified in the headers of said data packets into a set of monotone broadcast network output address intervals which form new packet headers, and routing said packets through a broadcast network capable of replicating said packets to the broadcast network output addresses contained in the new packet headers.
Claim 43
Independent Claim
64 words
A method for copying data packets comprising the steps of: transforming a set of copy numbers specified in the headers of said data packets into a set of monotone broadcast network output address intervals which form new packet headers, and routing said packets through a broadcast network capable of replicating said packets to the broadcast network output addresses contained in the new packet headers.
Claim 44
Independent Claim
41 words
A method for copying data packets comprising the steps of: providing data packets whose headers include address intervals, and routing said packets through a network having nodes capable of utilizing the information provided by the address intervals to replicate said packets.
Claim 45
Independent Claim
41 words
A method for copying data packets comprising the steps of: providing data packets whose headers include address intervals, and routing said packets through a network having nodes capable of utilizing the information provided by the address intervals to replicate said packets.
Claim 46
Independent Claim
177 words
A method for routing a data packet through a node in the k th stage of a network comprising an array of interconnected nodes organized into N stages, said nodes having logic "0" and logic "1" outputs, said packet having a header including a minimum binary number m 1 . . . m N and a maximum binary number M 1 . . . M N which together define an interval, said method comprising the steps of: if m k =M k , transmitting said packet out said logic "0" or said logic "1" output and if m k =M k , transmitting a first copy of said packet out said logic "0" output with a header including the interval [m 1 . . . M N ,M 1 . . . M k-1 011 . . . 1] and transmitting a second copy of said packet out said logic "1" output with a header including the interval [m 1 . . . m k-1 10 . . . 0,M 1 . . . M N ].
Claim 47
Independent Claim
177 words
A method for routing a data packet through a node in the k th stage of a network comprising an array of interconnected nodes organized into N stages, said nodes having logic "0" and logic "1" outputs, said packet having a header including a minimum binary number m 1 . . . m N and a maximum binary number M 1 . . . M N which together define an interval, said method comprising the steps of: if m k =M k , transmitting said packet out said logic "0" or said logic "1" output and if m k =M k , transmitting a first copy of said packet out said logic "0" output with a header including the interval [m 1 . . . M N ,M 1 . . . M k-1 011 . . . 1] and transmitting a second copy of said packet out said logic "1" output with a header including the interval [m 1 . . . m k-1 10 . . . 0,M 1 . . . M N ].
Claim 48
Dependent Claim
14 words
The method of claim 33 wherein said intervals contain output addresses of said network.
Claim 49
Independent Claim
160 words
A method for selectively replicating a data packet comprising the steps of receiving a packet whose header includes an address interval defined by a minimum address and a maximum address, said packet being received at a node in the k th stage of a network comprising a plurality of interconnected nodes organized into N stages, if the k th bit in the minimum address is equal to the k th bit in the maximum address, transmitting said received packet out from said node via a first or second output of said node, and if the k th bit in the minimum address is not equal to the k th bit in the maximum address, transmitting the packet out via the first and second output of said node and modifying the headers of the transmitted packets so that the header of each transmitted packet includes a portion only of said address interval defined by said minimum address and said maximum address.
Claim 50
Independent Claim
160 words
A method for selectively replicating a data packet comprising the steps of receiving a packet whose header includes an address interval defined by a minimum address and a maximum address, said packet being received at a node in the k th stage of a network comprising a plurality of interconnected nodes organized into N stages, if the k th bit in the minimum address is equal to the k th bit in the maximum address, transmitting said received packet out from said node via a first or second output of said node, and if the k th bit in the minimum address is not equal to the k th bit in the maximum address, transmitting the packet out via the first and second output of said node and modifying the headers of the transmitted packets so that the header of each transmitted packet includes a portion only of said address interval defined by said minimum address and said maximum address.
References Cited (Backward Citations)
US4317195A
Cited
US4354263A
Cited
WO1984004015A1
Cited
US4542497A
Cited
US4617657A
Cited
US4734907A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-03-13 | 1992-09-12 | 1993-03-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-03-13 | 1996-09-12 | 1997-03-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-03-13 | 2000-09-12 | 2001-03-14 | $7700.00 | Window Closed / Lapsed |