Multiplex communications – Network configuration determination
Reexamination Certificate
1997-12-03
2001-06-26
Nguyen, Chau (Department: 2663)
Multiplex communications
Network configuration determination
C370S408000
Reexamination Certificate
active
06252856
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to systems for routing data through one or more networks. More specifically, the invention provides a system for minimizing unnecessary routing calculations in a network environment and thereby improves the utilization of computational resources.
2. Background
Data communication networks may include various nodes, routers, switches, hubs, and other network devices coupled to and communicating with one another. Data is communicated between network devices by utilizing links between the devices. A particular data packet (or data cell) may be handled by multiple network devices and cross multiple links as it travels between a source and a destination. Additionally, multiple networks may be coupled to one another by common network devices or common links.
Various protocols can be used to communicate routing information through a network. One type of protocol is referred to as a link state protocol, in which each node in the network knows the network topology such that the node can calculate routes through the network using the known topology. The link state information is distributed to network nodes using a series of Link State Advertisements (LSAs) originated by routers and other nodes in the network. For example, a router may advertise LSAs into the network area in which the router resides. These advertised LSAs may indicate that the router has connections to one or more nodes. These LSAs are received by other routers and nodes in the network. Thus, the other routers and nodes learn of the connections described in the advertised LSAs. All routers in the network may generate and advertise similar LSAs.
Since each router “learns” the network topology by receiving various LSAs, each router is capable of independently calculating routes through the network.
An example of a link state routing protocol is the Open Shortest Path First (OSPF) routing protocol. Each router running the OSPF protocol maintains an identical database describing the network topology. Using this topology database, each router is able to generate a routing table by constructing a shortest-path tree with the router at the root of the tree. OSPF is a dynamic routing protocol; i.e., OSPF detects changes in network topology and recalculates paths based on the new topology. Typically, all routers in an autonomous network run the OSPF protocol simultaneously.
OSPF allows multiple networks and routers to be grouped together. These groupings are commonly referred to as areas. The specific topology of a particular area is not broadcast to other areas. Instead, a summary of the area topology is transmitted to other areas, thereby reducing the amount of link state information that must be transmitted through the network. Since a router may be connected to more than one area, each router that borders multiple areas maintains a separate topology database for each area. A separate copy of OSPF's basic routing algorithm is executed in each area. Additionally, routing within a particular area is determined only by the topology of the particular area. Each area may use a different authentication scheme, such that some areas use stricter authentication schemes than other areas.
Mutlticast Open Shortest Path First (MOSPF) is a multicasting extension to OSPF. Multicasting is the distribution of data from a source to multiple destinations. The multiple destinations may be members of a multicast group such that each member of a multicast group receives data addressed to the group. By adding a new type of LSA, the group membership LSA, MOSPF is able to determine the location of all multicast group members in the network.
In standard MOSPF, a multicast tree for a source-group flow is calculated (or constructed) in each area to reach all possible routers and networks (and hence all group members) in that area. During the construction of the multicast tree, group member information is checked when a vertex (a router or a network) is moved from the candidate list to the Shortest Path First (SPF) tree. The SPF tree contains multiple vertices and various information related to each vertex in the tree. The information related to each vertex may include the type of vertex (e.g., a router or a network), the vertex ID, and information regarding the link(s) associated with the vertex. Each vertex in the SPF tree includes a pointer to the parent of the vertex.
If a vertex is downstream from the calculating router and has associated group members, then the calculating router's interface that leads to the vertex becomes a downstream interface for the source-group flow. In this situation, an entire tree is constructed even if there is no group member in the area, thereby inefficiently utilizing computational resources.
When new router LSAs or network LSAs are received or originated, all multicast forwarding entries are deleted and the new forwarding entries are recalculated on demand (i.e., new multicast trees are constructed on demand in all areas). When a new group membership LSA is received or originated, all the multicast forwarding entries related to the group are also deleted and then recalculated on demand in all the areas. This complete reconstruction of multicast trees inefficiently utilizes computational resources in a multi-area situation because it is likely that only a small portion of the forwarding entries need to be reconstructed in some areas.
It is therefore desirable to provide a system that minimizes unnecessary calculations of multicast trees and thereby improves the efficient utilization of computational resources.
SUMMARY OF THE INVENTION
The present invention provides a system that minimizes unnecessary calculations of multicast trees and thereby improves the utilization of computational resources.
An embodiment of the invention provides a system for recalculating multicast trees by identifying a change associated with a network area. In response to the change in the network area, forwarding entries are recalculated in the network area. If the change results in the change of summary LSAs advertised into other areas, forwarding entries affected by the changed summary LSAs are also recalculated in those areas.
An alternate embodiment of the invention recalculates multicast trees in response to receiving a new group membership LSA. The system then determines whether the originator of the LSA is reachable from a calculating router. If the originator of the LSA is reachable from the calculating router, then the forwarding entries associated with the group are recalculated. If the originator of the LSA is not reachable from the calculating router, then the forwarding entries associated with the group are maintained, but not recalculated.
Another embodiment of the invention provides a system for terminating the construction of a multicast tree. Multicast tree construction may be terminated when all of the calculating router's interfaces that have adjacent neighbors have been added to the forwarding table for the tree.
Other embodiments of the invention terminate construction of the multicast tree when all of the calculating router's downstream vertices have been moved to the tree.
REFERENCES:
patent: 4740954 (1988-04-01), Cotton et al.
patent: 4742511 (1988-05-01), Johnson
patent: 4864559 (1989-09-01), Perlman
patent: 4873517 (1989-10-01), Baratz et al.
patent: 5088032 (1992-02-01), Bosack
patent: 5289460 (1994-02-01), Drake, Jr. et al.
patent: 5291477 (1994-03-01), Liew
patent: 5309433 (1994-05-01), Cidon et al.
patent: 5331637 (1994-07-01), Francis et al.
patent: 5355371 (1994-10-01), Auerbach et al.
patent: 5471467 (1995-11-01), Johann
patent: 5491690 (1996-02-01), Alfonsi et al.
patent: 5600638 (1997-02-01), Bertin et al.
patent: 5600794 (1997-02-01), Callon
patent: 5737526 (1998-04-01), Periasamy et al.
patent: 5754790 (1998-05-01), France et al.
patent: 5854899 (1998-12-01), Callon et al.
patent: 5881246 (1999-03-01), Crawley et al.
patent: 5943317 (1999-08-01), Brabson et al.
patent: 5953312 (1999-09-01), Crawley et al
Blakely , Sokoloff, Taylor & Zafman LLP
Lee Chiho Andrew
Nguyen Chau
Nortel Networks Limited
LandOfFree
Method and apparatus for minimizing calculations required to... 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 and apparatus for minimizing calculations required to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for minimizing calculations required to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2546862