Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
1999-12-10
2003-11-18
Cangialosi, Salvatore (Department: 2661)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
Reexamination Certificate
active
06650626
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to communication systems, and more particulary to propagating link state advertisements in a communication network.
BACKGROUND OF THE INVENTION
In today's information age, it is typical for computers to be internetworked over a communication network. A common networking model uses a number of interconnecteds routers to route protocol messages (referred to hereinafter as packets) within the communication network. A router acts as a gateway between two or more network segments, and processes packets according to addressing information contained in the packets.
When a router receives a packet from a particular network segment, the router determines whether to drop the packet, process the packet, or forward the packet. Specifically, the router may drop the packet if the packet is destined for the same network segment from which it was received. The router may forward the packet if the packet is destined for a different network segment. The router may process the packet if the packet is destined for the router itself. For convenience, the router logic that forwards packets is referred to as the “fast path” of the router, while the router logic that processes packets is
1
referred to as the “control plane” of the router.
In order for the fast path to forward packets, the router uses a routing protocol to determine network routes, and uses the network routes to build and maintain a forwarding table. The forwarding table includes forwarding entries mapping each destination address to a corresponding router interface based upon the network routes.
There are many different routing protocols in common use. One type of routing protocol, known as a “link state” routing protocol, an example of which is the Open Shortest Path First (OSPF) routing protocol, requires each router in the communication network to maintain a topology database describing the topology of the communication network. The topology database identifies each router in the communication network and the status of each router's links to other routers. Each router uses the topology information from its topology database to determine the network routes, typically using a shortest-path first technique for determining the network routes. The topology information, and therefore the forwarding table, is updated as network routes change.
In order for each router to maintain a topology database, each router must receive link state information from each of the other routers in the communication network.
Therefore, each router sends link state advertisement (LSA) protocol messages to the other routers in the communication network indicating the status of each communication link maintained by the router. Typically, each router sends a LSA protocol message whenever the status of a communication link changes, and also sends a LSA. protocol message periodically so that new routers receive the link state information in a timely manner. The LSA protocol messages are propagated to each of the other routers in the communication network.
When a router receives a LSA protocol message, the LSA protocol message is processed by the control plane of the router. The control plane updates the topology database according to the link state information in the LSA protocol message, and updates the forwarding table accordingly. The control plane may also forward the LSA protocol message to its neighboring routers.
Unfortunately, this control plane processing by each router can cause significant delay in propagating the LSA protocol messages to all routers in the communication network, especially in large communication networks having many routers. Consequently, there can be significant delay in recovering from network routing changes and outages, resulting in mis-routed packets, dropped packets, and overall performance degradation.
Thus, an improved technique for propagating LSA protocol messages is needed.
SUMMARY OF THE INVENTION
In accordance with one aspect of the invention, LSA protocol messages are forwarded over the fast path using a minimum spanning tree. Specifically, a minimum spanning tree is built using topology information learned from a routing protocol. Upon receiving a LSA protocol message from an originating device over an inbound interface, the LSA protocol is forwarded according to the minimum spanning tree. Also, the LSA protocol message is preferably routed to the control plane, which processes and forwards the LSA protocol message as usual for robustness.
REFERENCES:
patent: 5535195 (1996-07-01), Lee
patent: 5917820 (1999-06-01), Rekhter
patent: 6016306 (2000-01-01), Le Boudec et al.
patent: 6105018 (2000-08-01), Demers et al.
Cangialosi Salvatore
Nortel Networks Limited
Steubing McGuinness & Manaras LLP
LandOfFree
Fast path forwarding of link state advertisements using a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast path forwarding of link state advertisements using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast path forwarding of link state advertisements using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3176238