Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Alternate path routing
Reexamination Certificate
1999-09-15
2003-08-26
Dinh, Dung C. (Department: 2153)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Alternate path routing
C709S241000, C709S240000, C709S238000, C370S400000, C370S357000
Reexamination Certificate
active
06611874
ABSTRACT:
FIELD OF THE INVENTION
This invention deals with a method for statistically improving routing within an internet, and more particularly for improving next hop selection between internetwork routers.
BACKGROUND OF THE INVENTION
Modem digital networks operate using different transmission media and interconnect on demand a very large number of users (e.g. hosts) and applications through fairly complex digital communication networks.
Due to the large variety of users'profiles and distributed applications, network traffic is making greater bandwidth demands, exhibits less regular patterns and must be delivered to more uses and more widely separated destinations. This has driven the development fast packet switching techniques in which data from different origins are segmented into fixed or variable length packets (generically referred to as datagrams, with both expressions “packets” and “datagrams” being equally used herein) and then transferred, over high speed digital networks, between data source and target terminal equipments.
Several types of networks have been installed throughout the world, which need to be interconnected (e.g. via so called Routers) to optimize the possibilities of organizing traffic between source host terminal(s) and.target host terminal(s) located anywhere in the world. This is made possible by using so-called internetworking.
Internetwork (also referred to as internet) facilities use a set of networking protocols such as Transmission ControlProtocol/Internet Protocol (TCP/IP) developed to allow cooperating host computers to share resources across the internetwork. TCP/IP is a set of data communication protocols that are referred to as an internet protocol (IP) suite. Because TCP and IP are the best known, it has become common to use the term TCP/IP to refer to the whole protocol family. TCP and IP are two of the protocols in this suite. Other protocols of the suite include User Datagram Protocol (UDP), Address Resolution Protocol (ARP), and Real Time Protocol (RTP).
An internet may be viewed as a collection of heterogeneous and independent networks using TCP/IP and connected together by routers. The administrative responsibilities for an internet (e.g., assignment of IP addresses and domain names) can be within a single network (LAN) or distributed among multiple networks. To enable sending data from any source host to any target host connected to the internet, routing protocols have been defined. They include Routing Information Protocol (RIP) and Open Shortest Path First (OSPF) protocol using personalized so-called Routing Tables to define inter-router paths on a hop-by-hop basis, asynchronously from source to target. To that end, internetwork routers keep exchanging up-to-date network topology information and building up their Routing Tables.
Accordingly, whenever a source host (S) needs to send a data packet through the internet to a target host (T), S contacts its “default” router asking the router to send the packet toward the target (T). Routing within any given router R is based only on target identification. When running OSPF, the system looks for the “best” path toward the destination T. By “best” path one usually means shortest (i.e. involving minimum router “hops”). But for purposes of the invention, a “best” path may also take into account minimum cost and optimized bandwidth occupation. Lleased links costs may need to be taken into consideration when setting the path throughout the internet networks. In case of equivalent paths OSPF usually selects the first path identified within router Table.
Some improvements have been made in OSPF to avoid always using same paths which can lead to overloading some network paths and concurrent underutilization of others. For instance, in case of “equivalent” paths being identified some kind of “round robin” or per packet multipath algorithm may be executed to achieve load balancing. To further illustrate the above, consider an example of operation (see FIG.
1
). Assume source IP Host (
1
) transmits IP traffic to IP destination Host(
9
). All this traffic goes to IP Router
1
(R
1
).Router
1
learns the routes to IP Destination Host (
9
) using the OSPF routing protocol. As schematically illustrated in
FIG. 1
, there are three different routes from IP Router
1
to IP destination host (
9
), one via Router R
2
(path
3
), one via Router R
3
(path
4
) and one via Router R
4
(path
5
). Each route has an associated “cost”. OSPF selects the route with lowest cost and all traffic is sent over that selected route. Where “equivalent” routes are detected, the first route in the Router R
1
Table is selected.
However, when the OSPF Per Packet Multipath option is enabled in IP Router R
1
and when the costs of all three routes are equal, IP Router R
1
keeps the three routes. IP traffic is then transferred equally on all these routes, in round robin operating mode, on a per packet basis. A first IP packet to be transmitted is sent on the first route (Route (
3
)), a second IP packet is sent over the second route (Route (
4
)), a third packet is sent on third route (Route (
5
)), a fourth packet is then assigned the first route (Route (
3
)) again, and so on.
In practice, the system operation is a little more complex. Each network router includes a routing table and a cache storing the actual path(s) to be followed. Then the system may assign a different route to each packet or keep sending packets over the same route until the cache is refreshed, in which case the router switches to next route.
This enables balancing the IP traffic on all available “equivalent” routes, and accordingly, balances the traffic, as much as possible, over equivalent routes across the internet.
However, this function uses a static cost parameter, set at network configuration time. It does not take any congestion on one of the “equivalent” routes into consideration, while congestion may and actually does, occur.
Assume one of the routes shown in
FIG. 1
, e.g. route (
5
), is congested due to the maximum bandwidth being used on the connection between IP Router R
1
and Router R
4
. In this case, the OSPF Per Packet Multipath Function keeps using the route (
5
) because the OSPF cost does not change even though the link (
5
) is congested. IP Router R
1
may still distribute packets over all three routes, but the packets assigned to route (
5
) will be queued in Router R
1
until link
5
exits from congestion. The IP Destination Host (
9
) then receives and acknowledges all the IP packets, except those transmitted over path
5
. The Destination Host must then wait for the IP packets on path (
5
) before it can provide the complete set of data to its application. As a consequence, with the OSPF Per Packet Multipath operating mode, the delay introduced in the connection between Source and Destination (Target) hosts is the highest delay on all the different assigned routes. In addition, if three TCP Connections are established from IP source (
1
) to destination (
9
) for each of the three connections, IP packets are sent over the three different routes. This means that all the three connections will be impacted by the delay introduced on route (
5
).
More precisely, when packets P
1
, P
2
, P
3
. . . are sent by any source host toward a Target host, the target host acknowledges reception of the last received packet.
In fact acknowledgment addresses a number of bytes, but as far as the invention is concerned that does not affect the rationale. Assuming then P
2
misses, the target host shall keep acknowledging P
1
, even if P
3
, . . . are received. The system runs then a Fast Recovery protocol to generate retransmission of P
2
from the source host until P
2
is received.
In any case the overall consequence is that the efficiency of the network is seriously affected. Assuming one path goes through a 200 Kbps link and one or several go through 1 Mbps link(s), the practical result is that the system might be biased by the 200 Kbps rate of operation.
OBJECTS OF THE INVENTION
One object of this invention is to provide a method
Denecheau Lionel
Esteve Denis
Jourdet Christophe
Thubert Pascal
Dinh Dung C.
Johnson Marlon
Munoz-Bustamante Carlos
LandOfFree
Method for improving routing distribution within an internet... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for improving routing distribution within an internet..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for improving routing distribution within an internet... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3108649