US4870641A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multichannel bandwidth allocation
Assignee: Iconectiv LLC
•
Filing: 1988-03-30
•
Granted: 1989-09-26
•
Expires: 2008-03-30
Abstract
Abstract A method and apparatus for allocating bandwidth in a broadband packet switching network are disclosed. The invention utilizes channel groups (112) which may be defined as a set of parallel packet channels that act as a single data link connection between packet switches (110). In accordance with the invention, bandwidth is allocated in two steps. At virtual circuit setup time, bandwidth is reserved in particular channel groups. At transmission time packets are assigned to individual channels within the groups, illustratively, using a coordination mechanism in communication with the input ports of the appropriate packet switch. The bandwidth allocation technique, known as multichannel bandwidth allocation, leads to increased throughput and reduced packet loss probabilities.
Inventors
- 👤 Achille Pattavina
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 23:40
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04L2012/5619; H04L2012/5629; H04L2012/5631; H04L2012/5632
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
120 words
A method for allocating bandwidth in a packet switching network comprising a plurality of packet switches interconnected by packet channels organized into channel groups, said method comprising setting up virtual circuits in said network by reserving bandwidth in one or more of said channel groups for each virtual circuit, and under the control of centralized coordination means in communication with the input ports of the appropriate one of said packet switches, assigning each packet to be transmitted via a particular channel group to an individual packet channel within the particular channel group and resolving conflicts if the number of packets to be simultaneously transmitted via a particular channel group exceeds the number of individual channels in the particular channel group.
Claim 2
Independent Claim
120 words
A method for allocating bandwidth in a packet switching network comprising a plurality of packet switches interconnected by packet channels organized into channel groups, said method comprising setting up virtual circuits in said network by reserving bandwidth in one or more of said channel groups for each virtual circuit, and under the control of centralized coordination means in communication with the input ports of the appropriate one of said packet switches, assigning each packet to be transmitted via a particular channel group to an individual packet channel within the particular channel group and resolving conflicts if the number of packets to be simultaneously transmitted via a particular channel group exceeds the number of individual channels in the particular channel group.
Claim 3
Dependent Claim
55 words
The method of claim 1 wherein at one of said packet switches said setting up step comprises: selecting an adjacent packet switch, and within a set of channel groups connecting said one packet switch and said adjacent packet switch, selecting a channel group in said set that can accommodate the virtual circuit being set up.
Claim 4
Independent Claim
118 words
A method for allocating bandwidth in a packet switch having output channels organized into channel groups, said method comprising the steps of at the time a virtual circuit passing through said switch is set up, allocating said virtual circuit to one of said output channel groups, and at transmission time, receiving, at a plurality of input ports of said switch, packets to be transmitted via particular ones of said channel groups, assigning through use of centralized coordination means in communication with said plurality of input ports at least some of said packets to individual output channels in the particular channel groups, and routing at least some of said packets through said switch to the assigned individual output channels.
Claim 5
Independent Claim
118 words
A method for allocating bandwidth in a packet switch having output channels organized into channel groups, said method comprising the steps of at the time a virtual circuit passing through said switch is set up, allocating said virtual circuit to one of said output channel groups, and at transmission time, receiving, at a plurality of input ports of said switch, packets to be transmitted via particular ones of said channel groups, assigning through use of centralized coordination means in communication with said plurality of input ports at least some of said packets to individual output channels in the particular channel groups, and routing at least some of said packets through said switch to the assigned individual output channels.
Claim 6
Dependent Claim
22 words
The method of claim 3 wherein said assigning step comprises the step of identifying packets addressed to the same output channel group.
Claim 7
Dependent Claim
29 words
The method of claim 3 wherein said assigning step comprises the step of computing an index corresponding to an individual output channel for at least some of said packets.
Claim 8
Independent Claim
182 words
A method for allocating bandwidth in a packet switch having output channels organized into channel groups, said method comprising the steps of: at the time a virtual circuit passing through said switch is set up, allocating said virtual circuit to one of said output channel groups, and at transmission time, receiving, at a plurality of input ports of said switch, packets to be transmitted via particular ones of said channel groups, assigning at least some of said packets to individual output channels in the particular channel groups, and routing at least some of said packets through said switch to the assigned individual output channels, wherein said assigning step comprises the step of identifying packets addressed to the same output channel group, and wherein each of said output channels has an address, the address of each output channel group is the address of a group leader channel, and said assigning step further comprises assigning offsets to packets addressed to the same channel group, each offset corresponding to the differences between a particular group leader address and the address of an individual output channel.
Claim 9
Independent Claim
182 words
A method for allocating bandwidth in a packet switch having output channels organized into channel groups, said method comprising the steps of: at the time a virtual circuit passing through said switch is set up, allocating said virtual circuit to one of said output channel groups, and at transmission time, receiving, at a plurality of input ports of said switch, packets to be transmitted via particular ones of said channel groups, assigning at least some of said packets to individual output channels in the particular channel groups, and routing at least some of said packets through said switch to the assigned individual output channels, wherein said assigning step comprises the step of identifying packets addressed to the same output channel group, and wherein each of said output channels has an address, the address of each output channel group is the address of a group leader channel, and said assigning step further comprises assigning offsets to packets addressed to the same channel group, each offset corresponding to the differences between a particular group leader address and the address of an individual output channel.
Claim 10
Dependent Claim
28 words
The method of claim 6 wherein said routing step further comprises routing at least some of said packets through a self-routing network to said assigned individual output channels.
Claim 11
Dependent Claim
27 words
The method of claim 6 wherein said routing step further comprises routing at least some of said packets through a Batcher-banyan network to said individual output channels.
Claim 12
Dependent Claim
101 words
A packet switch comprising: a plurality of output channels arranged in groups, a plurality of input ports for receiving packets containing information serving to identify particular output channel groups, centralized output channel assignment means in communication with said plurality of input ports for assigning to said packets individual output channels in said particular output channel groups and for resolving conflicts when the number of said packets simultaneously containing information which serves to identify a particular channel group exceeds the number of channels in said group, and routing means for routing at least some of said packets to said individual output channels.
Claim 13
Dependent Claim
101 words
A packet switch comprising: a plurality of output channels arranged in groups, a plurality of input ports for receiving packets containing information serving to identify particular output channel groups, centralized output channel assignment means in communication with said plurality of input ports for assigning to said packets individual output channels in said particular output channel groups and for resolving conflicts when the number of said packets simultaneously containing information which serves to identify a particular channel group exceeds the number of channels in said group, and routing means for routing at least some of said packets to said individual output channels.
Claim 14
Dependent Claim
19 words
The packet switch of claim 9 wherein said routing means comprises a Batcher network followed by a banyan network.
Claim 15
Dependent Claim
31 words
The packet switch of claim 9 wherein each of said output channels has an address and the address of each output channel group is the address of a group leader channel.
Claim 16
Dependent Claim
29 words
The packet switch of claim 11 wherein said output channel assignment means comprises a first sub-network for identifying packets containing information serving to identify the same output channel group.
Claim 17
Dependent Claim
34 words
The packet switch of claim 9 wherein said channel assignment means comprises means for computing an index for each packet, at least some of said indices corresponding to individual output channels in said groups.
Claim 18
Dependent Claim
113 words
A packet switch comprising: a plurality of output channels arranged in groups, means for receiving packets containing information serving to identify particular output channel groups, output channel assignment means for assigning to said packets individual output channels in said particular output channel groups, and routing means for routing said packets to said individual output channels, wherein each of said output channels has an address and the address of each output channel group is the address of a group leader channel, wherein said output channel assignment means comprises a first sub-network for identifying packets containing information serving to identify the same output channel group, and wherein said first subnetwork comprises a plurality of comparators.
Claim 19
Dependent Claim
113 words
A packet switch comprising: a plurality of output channels arranged in groups, means for receiving packets containing information serving to identify particular output channel groups, output channel assignment means for assigning to said packets individual output channels in said particular output channel groups, and routing means for routing said packets to said individual output channels, wherein each of said output channels has an address and the address of each output channel group is the address of a group leader channel, wherein said output channel assignment means comprises a first sub-network for identifying packets containing information serving to identify the same output channel group, and wherein said first subnetwork comprises a plurality of comparators.
Claim 20
Dependent Claim
147 words
A packet switch comprising: a plurality of output channels arranged in groups, means for receiving packets containing information serving to identify particular output channel groups, output channel assignment means for assigning to said packets individual output channels in said particular output channel groups, and routing means for routing said packets to said individual output channels, wherein each of said output channels has an address and the address of each output channel group is the address of a group leader channel, wherein said output channel assignment means comprises a first sub-network for identifying packets containing information serving to identify the same output channel group, and wherein said output channel assignment means further comprises a second subnetwork for assigning offsets to packets containing information identifying the same channel group, each offset corresponding to the difference between a particular group leader address and the address of an individual output channel.
Claim 21
Dependent Claim
147 words
A packet switch comprising: a plurality of output channels arranged in groups, means for receiving packets containing information serving to identify particular output channel groups, output channel assignment means for assigning to said packets individual output channels in said particular output channel groups, and routing means for routing said packets to said individual output channels, wherein each of said output channels has an address and the address of each output channel group is the address of a group leader channel, wherein said output channel assignment means comprises a first sub-network for identifying packets containing information serving to identify the same output channel group, and wherein said output channel assignment means further comprises a second subnetwork for assigning offsets to packets containing information identifying the same channel group, each offset corresponding to the difference between a particular group leader address and the address of an individual output channel.
Claim 22
Dependent Claim
15 words
The packet switch of claim 15 wherein said second sub-network is a running adder sub-network.
Claim 23
Dependent Claim
113 words
A packet switch comprising: a plurality of output channels arranged in groups, means for receiving packets containing information serving to identify particular output channel groups, output channel assignment means for assigning to said packets individual output channels in said particular output channel groups, and routing means for routing said packets to said individual output channels, wherein each of said output channels has an address and the address of each output channel group is the address of a group leader channel, and wherein said channel assignment means comprises means for assigning offsets to said packets, each offset identifying the difference between a particular group leader address and the address of an individual output channel.
Claim 24
Dependent Claim
113 words
A packet switch comprising: a plurality of output channels arranged in groups, means for receiving packets containing information serving to identify particular output channel groups, output channel assignment means for assigning to said packets individual output channels in said particular output channel groups, and routing means for routing said packets to said individual output channels, wherein each of said output channels has an address and the address of each output channel group is the address of a group leader channel, and wherein said channel assignment means comprises means for assigning offsets to said packets, each offset identifying the difference between a particular group leader address and the address of an individual output channel.
Claim 25
Independent Claim
113 words
A method for switching data packets in a packet switch having a plurality of output channels arranged in groups, said method comprising: receiving at said switch a plurality of data packets each containing information corresponding to the address of a desired output channel group, generating for each data packet a request packet containing the desired output channel group, computing an index for each request packet which can be used to determine whether or not the corresponding data packet can be accommodated in the desired output channel group, and routing those data packets which can be accommodated in the desired output channel groups through said switch to individual output channels in the desired groups.
Claim 26
Independent Claim
113 words
A method for switching data packets in a packet switch having a plurality of output channels arranged in groups, said method comprising: receiving at said switch a plurality of data packets each containing information corresponding to the address of a desired output channel group, generating for each data packet a request packet containing the desired output channel group, computing an index for each request packet which can be used to determine whether or not the corresponding data packet can be accommodated in the desired output channel group, and routing those data packets which can be accommodated in the desired output channel groups through said switch to individual output channels in the desired groups.
Claim 27
Dependent Claim
19 words
The method of claim 18 wherein said packets are transmitted synchronously through said switch to said individual output channels.
Claim 28
Dependent Claim
16 words
The method of claim 18 wherein said indices are utilized to identify said individual output channels.
Claim 29
Independent Claim
158 words
A method for switching data packets in a packet switch having a plurality of output channels arranged in groups, said method comprising: receiving at said switch a plurality of data packets each containing information corresponding to the address of a desired output channel group, generating for each data packet a request packet containing the desired output channel group, computing an index for each request packet which can be used to determine whether or not the corresponding data packet can be accommodated in the desired output channel group, and routing those data packets which can be accommodated in the desired output channel groups through said switch to individual output channels in the desired groups, wherein said computing step further comprises the steps of sorting said request packets according to desired output channel group, identifying request packets having the same desired output channel group and generating signals indicative thereof, and obtaining running sums of said signals to provide said indices.
Claim 30
Independent Claim
158 words
A method for switching data packets in a packet switch having a plurality of output channels arranged in groups, said method comprising: receiving at said switch a plurality of data packets each containing information corresponding to the address of a desired output channel group, generating for each data packet a request packet containing the desired output channel group, computing an index for each request packet which can be used to determine whether or not the corresponding data packet can be accommodated in the desired output channel group, and routing those data packets which can be accommodated in the desired output channel groups through said switch to individual output channels in the desired groups, wherein said computing step further comprises the steps of sorting said request packets according to desired output channel group, identifying request packets having the same desired output channel group and generating signals indicative thereof, and obtaining running sums of said signals to provide said indices.
Claim 31
Independent Claim
113 words
A method for routing data packets through a packet switch having a plurality of output channels organized into groups, each of said data packets containing an address to a desired output channel group, said method comprising generating a request packet for each data packet containing the address of the desired output channel group, computing for each request packet an index for spreading data packets addressed to the same channel group over the individual channels comprising the group and for identifying data packets that cannot be accommodated in the desired channel group, and routing those data packets which can be accommodated in the desired channel group to the individual channels identified by said indices.
Claim 32
Independent Claim
113 words
A method for routing data packets through a packet switch having a plurality of output channels organized into groups, each of said data packets containing an address to a desired output channel group, said method comprising generating a request packet for each data packet containing the address of the desired output channel group, computing for each request packet an index for spreading data packets addressed to the same channel group over the individual channels comprising the group and for identifying data packets that cannot be accommodated in the desired channel group, and routing those data packets which can be accommodated in the desired channel group to the individual channels identified by said indices.
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) | 1992-09-25 | 1993-03-27 | 1993-09-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-09-25 | 1997-03-27 | 1997-09-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-09-25 | 2001-03-27 | 2001-09-26 | $7700.00 | Window Closed / Lapsed |