Fault-tolerant non-flooding routing

Details Fault-tolerant non-flooding routing Fault-tolerant non-flooding routing

2000-01-12

2004-04-13

Iqbal, Nadeem (Department: 2184)

Error detection/correction and fault detection/recovery

Data processing system error or fault handling

Reliability and availability

C370S218000

Reexamination Certificate

active

06721899

ABSTRACT:

TECHNICAL FIELD
This invention relates to communication network link-state routing protocols.
BACKGROUND OF THE INVENTION
Link-state routing protocols, such as the Open Shortest Path First (OSPF) or the ISO Intermediate System to Intermediate System routing protocol (IS—IS), are becoming the dominant Internet technology for routing packets within Autonomous Systems. An Autonomous System (“AS” or area) is a group of routers operating a common routing protocol and exchanging routing information.
Under link-state protocols, each router maintains a database describing the Autonomous System's topology. In steady state, every router has an identical database. The information stored in this database includes the routers' local states, e.g., their usable interfaces (links), reachable neighbors, and the links parameters (metrics). The routers distribute their local states throughout the Autonomous System by flooding, i.e., sending the local states to all the routers. Each router then makes its forwarding decisions based on the complete description of the topology of the routing area. All routers operate under the same protocol.
From the topological database, each router constructs a tree of shortest paths (the “shortest path tree” or “SPT”) with itself as the root. The routing information obtained from other routers appears on the tree as leaves. The tree provides routes to all destinations within the Autonomous System. Dimensionless metrics describe the costs of the separate links and complete routes.
Thus, in link-state protocol networks, the process of collecting topological information from the network is separated from the process of computing the correct routes. The former is performed distributively by all the routers in an area who share state information with each other. The latter is performed locally by each router. This is the main advantage of link-state protocols, because the computation can be performed quickly and without relying on other routers.
When a cost metric of some link changes, the information need be sent once to every router in the area; the recipients then immediately update their own routing tables under the common protocol. This is in sharp contrast to distance-vector protocols, such as RIP, where multiple routing packets may have to be sent many times between the same routers in order for their routing tables to converge to a steady-state correct value.
Even though the amount of information exchanged by routers operating under link-state protocols is less than the amount of information exchanged under distance-vector protocols, it may still be large when the cost metrics of the links vary quickly, or when the number of links in an area is large. In principle, every router in the area should have at all times the latest topological information. If the topology information is not identical in all routers, routing loops may result. This means that every time that there is a cost metric change in any one of the links, all the routers in the routing area must be notified.
Flooding an entire area after a single link-state change is inefficient in terms of bandwidth and computational overhead required. Furthermore, flooding a large routing area may take a long time. During that time, different routers will have different link-state information, and transient routing loops are possible. Many of the Internet's problems with routing instability are associated with the long delays required to propagate routing information.
One way to reduce the total amount of routing information being transmitted is to have the router responsible for a given link ignore changes in that link's metric. The new information will simply not be propagated and routing will continue along the old paths in a sub-optimal manner. After several metric changes, the router can broadcast a cumulative update packet summarizing all the topological changes that have taken place since last update. By limiting the frequency of such updates, the amount of network information traffic can be limited at the cost of some sub-optimal routing.
This approach does not work when the link change that takes place is a link failure or extreme congestion of the link; in this case, the rest of the network must be notified immediately—withholding link failure information will cause routing failures and loss of packets. Therefore, in order to restore the paths that previously traversed the failed link, information regarding failure of a link must be propagated at least to some routers in the network immediately.
We now discuss three basic ideas regarding routing restoration with limited local updates. Although these ideas are either inefficient or do not work in all cases, they will illustrate the problem and provide the reader with a better insight into our local route restoration scheme.
Tunneling
As illustrated in
FIG. 1
, when the link between routers A and B goes down, a new path is constructed between these routers through routers N
1
, N
2
, and N
3
. All the traffic that should have traveled through the broken link is now diverted into this new path, which acts as a virtual link.
A tunneling scheme can be implemented as follows. After the link between A and B fails, router A detects the failure, but does not broadcast this information to the rest of the network. Instead, it uses its shortest path first (SPF) engine to compute the new shortest path to router B and records the new next hop for B. Router A then sends a special packet containing the information regarding the failed link through that next hop. When the next hop router, N
1
in our example, receives the special packet, it in turn re-computes the new shortest path to B, determines and records the new next hop to B, and forwards the special packet along that next hop. This operation is repeated until router B receives the special packet, i.e., router B is the computed next hop router.
In this manner, router A and all of the routers in the restoration path—routers N
1
, N
2
, and N
3
in our example—are informed of the link failure and are capable of forwarding packets to B along the new path. When a regular data packet that needs to traverse the failed link arrives at A, the packet is encapsulated in another packet with destination B and forwarded along the newly computed shortest path until it reaches B. Upon arrival at B, the original packet is decapsulated and forwarded according to the established routing table.
This scheme limits the update information that needs to be broadcast after a link failure. Only the routers that are part of the new path from A to B are informed of the changes in the topology. Even though the rest of the network does not know about the failure, global routing continues to function correctly, though possibly sub-optimally.
A major drawback of the tunneling scheme is that every single data packet that goes through the new path has to be encapsulated at router A. This requires A to be able to generate a new packet for every data packet that must be diverted, increasing the load on A and greatly limiting the efficiency of its packet forwarding function.
Local Routing Table Adjustment with Simple Updates
According to this approach, only the routers of the restoration path are informed of the link's failure. These routers modify their routing tables and let their forwarding engines function as usual. In other words, along some restoration path, the new topological information is broadcast and the routing tables are re-computed, whereas the other routers continue using old routing tables. In our previous example (see FIG.
1
), if routers A, N
1
, N
2
, and N
3
simply re-computed their routing tables using the new information about the link failure, global routing might still function correctly. Even though router S continues to use an old routing table, a packet from S to D might still be routed correctly, although possibly sub-optimally.
We say might because this partial update scheme is not restrictive enough to guarantee proper forwarding. Because the actual path that a packet takes is determine

Affiliated with

Also associated with

Rating

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3231468