Dynamic algorithm for determining a shortest path tree...

Details Dynamic algorithm for determining a shortest path tree... Dynamic algorithm for determining a shortest path tree...

1999-03-24

2004-03-09

Pham, Chi (Department: 2667)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C709S239000

Reexamination Certificate

active

06704320

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to routing of information packets in a communications network, and, more particularly, to a router determining shortest paths for communicating packets between nodes based on shortest-path trees.
2. Description of the Related Art
In an interconnected communications network employing packets, such as the Internet, routing protocols are employed by routers of the network to determine how packets are to be forwarded between nodes. Packets received by a node's router are forwarded to other nodes based on a forwarding table of an interior routing protocol. Interior routing protocols exchange network topology and link-state information (“network topology information”) among routers to allow the node's router to construct the corresponding forwarding table. An example of a widely-used interior routing protocol is the Open Shortest Path First (OSPF) protocol, as outlined in J. Moy, “OSPF Version 2,” Internet Draft, Request for Comment (RFC) 2178, July, 1997. In addition, some interior routing protocols associate a link cost, known in the art as a weight, with each link between nodes. The link cost may be associated with, for example, available bandwidth or revenue generated by the link. When link-state information (e.g., status, utilization, connectivity, or bandwidth) is exchanged between routers, each router in a regional network has a complete description of the network's topology.
Each router computes paths between nodes, and uses the weights to calculate a set of preferred paths. Each of the set of preferred paths that is computed has a minimum total weight for the path between the particular router and each other router in the region. This set of preferred paths may be defined with a shortest path tree (SPT). A forwarding table with routing information (e.g., source-destination pair, source ports, and destination ports) is generated from the SPT. The router uses the routing information to forward a received packet along the shortest path of the SPT to its destination. The SPT may be calculated using an algorithm such as Dijkstra's algorithm, described in E. Dijkstra, “A note: two problems in connection with graphs,” Numerical Mathematics, vol. 1, 1959, pp. 269-271.
When the network topology of a regional network changes (e.g., a link fails, recovers, or changes its routing weights), each router in the region detects the change and updates the network topology information stored by the router. After updating its stored network topology information, each router recalculates a new SPT and forwarding table. In routers of the prior art, the recalculation deletes the current SPT and recalculates the new SPT from scratch (this type of recalculation method is known in the art as a statis algorithm).
However, for most changes in network topology, the new SPT does not differ significantly from the old SPT, and in many cases the old and new SPTs are the same. Statis algorithms that recompute the new SPT from scratch are inefficient because they do not take advantage of available information about the prior (outdated) SPT. Another drawback of statis algorithms is that multiple routes of the same shortest distance may coexist from one router to another router. When the SPT is re-computed from scratch, a different one of the coexisting multiple routes may be selected for the SPT than was selected by a prior computation. If a new path of the coexisting multiple routes is selected each time the new SPT is computed, the router may change many entries in its forwarding table frequently and unnecessarily, increasing the risk of routing errors or routing failures associated with implementing the change in routing.
To illustrate,
FIG. 1
shows a regional network
100
of an Internet Service Provider (ISP) comprising four routers
101
,
102
,
103
, and
104
. The routers
101
,
102
, and
104
are commonly known as access routers and provide users a connection to the network
100
. Router
103
connects the network
100
to a backbone packet network
105
that may be, for example, the Internet. Initially, link
106
(shown by a dashed arrow) between
103
and
104
is not in service (i.e., disconnected or not provisioned). The solid arrows indicate links which are preferred paths defined by an SPT calculated and stored in router
101
(commonly termed as an SPT “rooted at” router
101
). The numeral next to each solid arrow in
FIG. 1
is the weight assigned to the corresponding link. The forwarding table in router
101
contains forwarding entries, each forwarding entry corresponding to next-hop information of each user's network connection through router
103
to the backbone packet network
105
. Initially, all packets routed from router
101
to backbone packet network
105
pass through router
102
. However, if the link between routers
103
and
104
is established (i.e., either provisioned or recovered) and has a link weight of 1, the network topology changes and the SPT rooted at router
101
must be recomputed.
When the SPT is recomputed from scratch, the result may indicate that all paths to the backbone packet network
105
from router
101
now pass through router
104
. Router
101
then changes the next-hop information for some or all network connections passing through router
103
to now pass through router
104
. However, the path weight for the previous and new paths are the same and the changes may not be necessary. These changes may correspond to several thousand updates in the forwarding table of router
101
, many of which may be redundant updates. In addition to redundant updates in forwarding tables, unnecessary changes in the SPT may also cause undesirable fluctuation of traffic load on any given route.
SUMMARY OF THE INVENTION
The present invention relates to routing packets in a packet network based on a shortest path tree (SPT) defining paths between nodes in the network. In accordance with the present invention, a temporary list of nodes in the network is generated for a current SPT, the list including nodes affected by a change in the weight of a link between two nodes in the network. The change in weight corresponds to the addition of a new link in the network or an increase or decrease in the weight of an existing link in the network. A selection process selects a node of the list in accordance with a maximum decrement criterion, the maximum decrement criterion identifying the node in the list having a most negative or a least positive associated distance change resulting from the change in the weight of the link. An update process updates one or more paths in current SPT for nodes reachable from the selected node, wherein the selected node is removed from the list and zero, one, or more of the reachable nodes are added to the list. The selection process and update process are repeated until the list is empty to generate an updated SPT. A router, for example, then routes one or more packets in accordance with the updated SPT.


REFERENCES:
patent: 5115495 (1992-05-01), Tsuchiya et al.
patent: 5872773 (1999-02-01), Katzela et al.
patent: 6088333 (2000-07-01), Yang et al.
patent: 6098107 (2000-08-01), Narvaez-Guarnieri et al.
patent: 6122283 (2000-09-01), Lee
patent: 6347078 (2002-02-01), Narvaez-Guarnieri et al.
patent: 6370119 (2002-04-01), Bosso et al.
patent: 6400681 (2002-06-01), Bertin et al.

Affiliated with

Also associated with

Rating

Dynamic algorithm for determining a shortest path tree... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Dynamic algorithm for determining a shortest path tree..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic algorithm for determining a shortest path tree... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3237458