Patent US6567382B1 successfully refreshed from Google Patents.
US6567382B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Maximal flow data routing
Assignee: Alcatel Lucent SAS
•
Filing: 1999-08-10
•
Granted: 2003-05-20
•
Expires: 2019-08-10
Abstract
Abstract In a network consisting of a plurality of nodes interconnected by links, a communication from one terminal to a second terminal is transmitted using a maximal flow algorithm, in which the communication is divided among all the possible paths from the first terminal to the second terminal. Accordingly, greater use is made of lightly loaded links and the demand on heavily loaded links is reduced as the traffic is more evenly distributed across the network, resulting in an overall improvement in network performance.
Inventors
- 👤 Michael Cox
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 18:46
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/24; H04L47/00; H04L47/10; H04L47/11; H04L47/12; H04L47/122; H04L47/125
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
92 words
A method of transmitting a data message across a network comprising a plurality of routers, wherein the method comprises: providing each router with a topology map of the network, wherein the transmitting host router identifies all useable paths between a transmitting terminal and at least one destination terminal, dividing the data message into a plurality of packets having at least a minimum size, and distributing the plurality of packets among the useable paths, wherein the number of paths chosen by the transmitting host router is not greater than the number of packets.
Claim 2
Independent Claim
92 words
A method of transmitting a data message across a network comprising a plurality of routers, wherein the method comprises: providing each router with a topology map of the network, wherein the transmitting host router identifies all useable paths between a transmitting terminal and at least one destination terminal, dividing the data message into a plurality of packets having at least a minimum size, and distributing the plurality of packets among the useable paths, wherein the number of paths chosen by the transmitting host router is not greater than the number of packets.
Claim 3
Dependent Claim
39 words
A method as claimed in claim 1 , wherein the transmitting host receives information on the load distribution across the network and dynamically allocates the plurality of packets to the paths according to the available capacity of the paths.
Claim 4
Dependent Claim
31 words
The method as claimed in claim 1 , wherein paths having an element which is loaded above a predetermined threshold are only chosen if more lightly loaded paths are not available.
Claim 5
Dependent Claim
14 words
The method as claimed in claim 3 , wherein the element is a node.
Claim 6
Dependent Claim
14 words
The method as claimed in claim 3 , wherein the element is a link.
Claim 7
Dependent Claim
15 words
The method as claimed in claim 3 , wherein the predetermined threshold is 70 percent.
Claim 8
Dependent Claim
30 words
The method of transmitting data as claimed in claim 1 , wherein each router broadcasts a load status message indicating the load status of the router and its associated links.
Claim 9
Dependent Claim
20 words
A method as claimed in claim 7 wherein the load status message indicates a range in which the load falls.
Claim 10
Dependent Claim
21 words
A method as claimed in claim 8 wherein a load status message is broadcast when the range of a load changes.
Claim 11
Dependent Claim
99 words
A router comprising: first means for receiving and storing network topology data; second means for receiving and storing network load status data; processor means to divide an outgoing message into packets having at least a minimum size and to allocate the packets to paths using a routing algorithm on the basis of the network topology data and the load status data, wherein the number of paths chosen by the routing algorithm is not greater than the number of packets; and packet header means to add a header to each packet including source and destination information and packet sequence information.
Claim 12
Dependent Claim
99 words
A router comprising: first means for receiving and storing network topology data; second means for receiving and storing network load status data; processor means to divide an outgoing message into packets having at least a minimum size and to allocate the packets to paths using a routing algorithm on the basis of the network topology data and the load status data, wherein the number of paths chosen by the routing algorithm is not greater than the number of packets; and packet header means to add a header to each packet including source and destination information and packet sequence information.
Claim 13
Dependent Claim
37 words
The router as claimed in claim 10 , wherein the routing algorithm receives information on the load distribution across the network and dynamically allocates the packets to the paths according to the available capacity of the paths.
Claim 14
Dependent Claim
33 words
The router as claimed in claim 10 , wherein the routing algorithm chooses paths having an element which is loaded above a predetermined threshold only if more lightly loaded paths are not available.
Claim 15
Dependent Claim
15 words
The method as claimed in claim 12 , wherein the predetermined threshold is 70 percent.
Claim 16
Dependent Claim
107 words
A router comprising: a network map storage device for receiving and storing network topology data; a network status storage device for receiving and storing network load status data; a processor to divide an outgoing message into packets having at least a minimum size and to allocate the packets to paths using a routing algorithm on the basis of the network topology data and the load status data, wherein a number of paths chosen by the routing algorithm is not greater than a number of packets; and a packet header insertion device to add a header to each packet including source and destination information and packet sequence information.
Claim 17
Dependent Claim
107 words
A router comprising: a network map storage device for receiving and storing network topology data; a network status storage device for receiving and storing network load status data; a processor to divide an outgoing message into packets having at least a minimum size and to allocate the packets to paths using a routing algorithm on the basis of the network topology data and the load status data, wherein a number of paths chosen by the routing algorithm is not greater than a number of packets; and a packet header insertion device to add a header to each packet including source and destination information and packet sequence information.
Claim 18
Dependent Claim
38 words
The router as claimed in claim 14 , wherein the routing algorithm receives information on the load distribution across a network topology and dynamically allocates the packets to the paths according to the available capacity of the paths.
Claim 19
Dependent Claim
33 words
The router as claimed in claim 14 , wherein the routing algorithm chooses paths having an element which is loaded above a predetermined threshold only if more lightly loaded paths are not available.
Claim 20
Dependent Claim
15 words
The method as claimed in claim 16 , wherein the predetermined threshold is 70 percent.
References Cited (Backward Citations)
US5495426A
Cited
US5596722A
Cited
US6081511A
Cited
US6178448B1
Cited
US6347078B1
Cited
US6256295B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-05-19 | 2006-11-18 | 2007-05-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-05-19 | 2010-11-18 | 2011-05-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-05-19 | 2014-11-18 | 2015-05-20 | $7700.00 | Window Closed / Lapsed |