Multiple path routing

Details Multiple path routing Multiple path routing

1998-08-11

2002-02-12

Kizou, Hassan (Department: 2662)

Multiplex communications

Data flow congestion prevention or control

Control of data admission to the network

C370S238000, C370S406000, C709S241000, C709S241000

Reexamination Certificate

active

06347078

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to routing data packets to a destination node within a packet switching network. In particular the invention relate to a multiple path routing scheme using a novel data structure.
BACKGROUND OF THE INVENTION
In packet switching networks such as the Internet, a packet from a source traverses intermediate network routers before reaching its destination. Before a packet arrives at a router, a routing protocol is used to determine the existence and status of all routers and links therebetween on the network. This information is used by the router to determine an appropriate next hop for an arriving packet with a given destination. The next hop includes the next router along the path to the destination and the outgoing port of the present router linking the next router. A widely used link-state routing protocol, is Open Shortest Path First (“OSPF”)
Given the current link states in the network, (e.g. reduced bandwidth, increased bandwidth, disconnected, reconnected) each router S keeps track of a shortest path tree “SPT” from S to every other router in the network. Since the router retains only one shortest path from S for each destination router, the first hop from S along this path will be used as the next hop to forward any packets with the same given destination.
Although a router using OSPF has global information about the regional network topology, it determines only the local route of a packet, i.e., the next hop. When each router computes such next-hop information based on an SPT, each packet is guaranteed to be forwarded along a loop-free path to its destination. A loop-free path is a path that doesn't include the same router more than once. Multiple SPTs rooted at router S can co-exist in a network. In such a case there are multiple choices of next hops from S to forward a packet, each of which will lead to a different path of the same shortest distance. The packet can be forwarded to any of these next hops.
Routing protocols allowing for only a single shortest path suffer from several inefficiencies. For example, if immediately before dispatching a packet along its next hop, a router learns that a link along the path is down, the router must first recompute a new single shortest path and only then send the packet along the new next hop.
The single shortest path method also ignores network load considerations. Thus, even if a path has a lot of traffic the packet will be forwarded along that path if it is the shortest to its destination. Furthermore, it is known that finding an optimal path that satisfies certain QoS constraints is in general computationally difficult (NP-complete). Since some QoS parameters that need to be optimized may depend on the network traffic load and thus can change dynamically over a short period of time, finding an optimal path can become infeasible even for a moderate-size network. Even for QoS parameters that do not change frequently, determining the optimal path from a router may require global knowledge of these parameters in the network, and a local change in these parameters would therefore need to be disseminated to every node in the network. Hence in most cases only suboptimal paths can be computed.
SUMMARY OF THE INVENTION
The present invention uses a multiple path algorithm (referred to herein as “MPA”) to enable a router to forward packets to multiple viable next hops that are not strictly constrained to be a part of a shortest path from the router to the packet's destination. The method of the present invention still guarantees, however, that all packets will be routed to their destination on loop-free paths. In general each path traversing a different next hop is guaranteed to be loop free if it satisfies the constraint that the shortest distance from the implementing router to the destination decreases at each next hop.
In a preferred embodiment of the invention, the MPA uses a novel data structure which stores information relating to each router (node) in the network that is a potential destination node. In particular, the data structure maintains at least the following attributes: the shortest distance from the implementing router to the destination node; the cost of each link from the implementing router to each potential next hop; and for each potential next hop, the shortest distance from the implementing router to the destination node along a path traversing that particular next hop.
Using this data structure, multiple viable next hops are computed by selecting next hops from the potential next hops whose shortest distance attribute traversing that next hop, minus the cost of the link from the implementing router to the next hop, is less than the shortest path from the implementing router to the destination node.
The method and data structure of the present invention can be efficiently implemented as an add-on component to existing routing protocols such as OSPF. Each MPA implementing router uses the topology information exchanged by the router protocols to compute multiple paths between a given source and a given destination. Moreover, conventional routers based on shortest path routing can co-exist in the same network with MPA implementing routers to guarantee loop-free routing for each packet. In general, an MPA implementing router can interoperate with any router whose routing protocol uses the loop-free policy.
By maintaining multiple viable next hops in a router for each destination, recovery from link failure is much faster than heretofore possible, since the recovery mechanism using alternate paths can be implemented locally by the router, and there is almost no delay incurred by the link failure. On the other hand, without MPA, after detecting a link failure, the router would need to broadcast throughout the network the link failure, then recompute the shortest path tree to determine a new alternative path.


REFERENCES:
patent: 5142531 (1992-08-01), Kirby
patent: 5317566 (1994-05-01), Joshi
patent: 5537392 (1996-07-01), Willie et al.
patent: 5825772 (1998-10-01), Dobbins et al.
patent: 5881243 (1999-03-01), Zaumen et al.
patent: 0465090A (1992-01-01), None
Richard G. Ogier & Vlad Rutenberg, “Efficient Algorithms for Optimal Alternate Routing in Communication Networks” 676-680 (May 23, 1993) XP000371172.

Affiliated with

Also associated with

Rating

Multiple path 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 Multiple path routing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple path routing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2969848