Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
1999-08-10
2003-05-20
Jung, Min (Department: 2663)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
C370S400000, C370S468000
Reexamination Certificate
active
06567382
ABSTRACT:
TECHNICAL FIELD
This invention relates to a technique for improving the routing of data traffic in a network.
BACKGROUND ART
There are a number of techniques for routing data.
A first technique uses a distance vector. In this technique each router maintains a list of destinations which can be reached in one “hop” from the corresponding router. Each router notifies a requesting router in the network of its access to the requested destination so a path to the destination can be established.
A problem with this technique is that loops can be formed.
The BGP4 protocol is a modified distance vector technique which solves the loop problem by deleting duplicate routes.
In the link state protocol (LSP), each router notifies all other routers directly attached to the router. This enables each router to build a graphical topological map of the network so that each router knows the structure of the network.
The Open Shortest Path First (OSPF) protocol looks for the least cost shortest path for the transmission of data from a source to a destination. All the data is transmitted over a single path.
The Equal Cost Multiple Path (ECMP) protocol improves on the transmission speed of OSPF by identifying all paths of equal cost and dividing the traffic equally among these paths. A drawback of this technique is that it does not take account of the load status of each of the paths so equal amounts of the data traffic are distributed to lightly loaded and heavily loaded links. Thus this system does not make optimal use of the network and it can add to congestion on the heavily loaded links.
Optimized Multipath (OMP) improves on ECMP by dynamically adjusting the traffic allocated to links on the basis of the network load distribution.
DISCLOSURE OF THE INVENTION
It is desirable to provide a technique which improves on the utilization of the network made by the prior art.
Accordingly this specification discloses a method of transmitting data across a network which includes a plurality of routers, the method including providing each router with a map of the topology of the network, wherein the transmitting host router identifies all useable paths between a transmitting terminal and at least one destination terminal, and wherein the transmitting host router distributes the data message among the useable paths so the choice of paths is not limited to the shortest paths.
In a preferred embodiment, the transmitting host router identifies at least all the shortest paths and distributes the data amongst a plurality of these paths inversely to their load status.
In a further embodiment, the transmitting host router identifies at least the shortest paths and the next shortest paths and distributes the data amongst a plurality of these paths inversely to their load status.
In these embodiments the transmitting host selects two or more paths, but not necessarily all the paths, to carry the data. Paths with a traffic load exceeding a predetermined threshold are not selected. Thus the system can help to avoid overloading the network by choosing the more lightly loaded links.
In a further embodiment, the transmitting host receives information on the load distribution across the network and dynamically allocates the data message to the paths according to the load of the paths.
In an alternative embodiment each router through which a portion of the data message passes reallocates the portion of the data message on the basis of current network load conditions.
In a further embodiment the host router subdivides the data message according to network specifications.
The different paths may have different different delays. In distributing the data across several links, it is necessary that the individual blocks of data are given a sequence stamp at the time they are split up, to enable them to be reassembled in the correct sequence at the destination.
REFERENCES:
patent: 5495426 (1996-02-01), Waclawsky et al.
patent: 5596722 (1997-01-01), Rahnema
patent: 6081511 (2000-06-01), Carr et al.
patent: 6178448 (2001-01-01), Gray et al.
patent: 6347078 (2002-02-01), Narvaez-Guarnieri et al.
patent: 6256295 (2002-07-01), Calon
Alcatel
Jung Min
LandOfFree
Maximal flow data routing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Maximal flow data routing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximal flow data routing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3074868