Multiplex communications – Network configuration determination
Reexamination Certificate
2000-05-04
2004-06-29
Ho, Duc (Department: 2665)
Multiplex communications
Network configuration determination
C370S255000, C370S466000
Reexamination Certificate
active
06757258
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention pertains generally to OSPF (open shortest path first) routing protocols. More particularly, the invention is a method and apparatus for reducing OSPF flooding which provides fast convergence and recovery when there is a change in network topology.
2. The Prior Art
Routing protocols for use on computer networks as well as the global information network (commonly known as the Internet) are known the art. For example, TCP/IP (Transmission Control Protocol/Internet Protocol) is a widely used networking protocol that provides communication across interconnected networks, between computers with diverse hardware architectures and various operating systems.
OSPF (Open Shortest Path First) is another routing protocol used over local area networks (LANs), wide area networks (WANs) and the Internet. OSPF is a link-state routing algorithm that is used to calculate routes based on the number of routers, transmission speeds, delays and route costs. In general, OSPF supports three kinds of connection and networks: point-to-point lines between two routers; multiaccess networks with broadcasting (e.g., most LANs); and multiaccess networks without broadcasting (e.g., most packet-switched WANs).
A multiaccess network is one that can have multiple routers on it, each of which can directly communicate with all the others (i.e., a “mesh” topology). A serial connection between two routers is represented by a pair of arcs, one in each direction. OSPF works by abstracting the collection of actual networks, routers, and lines into a directed graph in which each arc is assigned a cost (distance, delay, etc.) It then computes the shortest path based on the weight on the arcs.
In conventional OSPF, the OSPF router protocol must refresh its Link State Advertisements (LSAs) at periodic intervals (typically every 1800 seconds or 30 minutes), otherwise the LSA data will expire in the other routers of the network. The LSA data includes, for example, information regarding the cost of the connection, the type of connection, and which nodes the router is connected, among other information. The refreshing of LSA data is carried out regardless of whether the information has changed or not. The purpose for refreshing LSA data is to provide a certain level of robustness—at most, the LSA data in routers is outdated by only 30 minutes. On the other hand, even if the network topology is stable and unchanging, the OSPF will still generate traffic in order to refresh LSA data in the other routers. Internet Service Providers and users having large networks have noticed this non-negligible protocol traffic.
Some implementations have tried to improve the flooding caused by LSA traffic by reducing its refresh frequency from 30 minutes to around 50 minutes or more. This solution presents the advantage of reducing the amount of refresh traffic but will require at least one refresh before the LSA expires. Another disadvantage with increasing the refresh times of LSA is that the time period during which potentially incorrect LSA data is resident in the other routers correspondingly increases.
The existing OSPF Demand Circuit (DC) feature utilizes a “Do Not Age” (DNA) LSA implementation. The purpose of OSPF DC is to reduce the cost associated with data line transmissions. For example, where data is communicated over ISDN (integrated services digital line), X.25 or ATM (asynchronous transfer mode) there is a cost associated with the transfer. OSPF DC attempts to reduce refreshing and flooding of already known and unchanged information. To this end, the LSA will now be flooded with the higher bit set thus making them DNA LSA. In addition, several other protocols are disabled to reduce traffic over the communication lines. For example, DC suppresses “hellos” between adjacent neighbors. As a consequence, the suppression of hellos will delay the knowledge that the neighbor has gone down or otherwise terminated communication. While the DC feature generally reduces overhead and therefore reduces the cost of operating the network, there is a lack of convergence and recovery is delayed when there is a change in the network topology. Consequently, packets may be lost and network performance may suffer in DC arrangements.
Accordingly, there is a need for a method and system for reducing OSPF flooding and traffic due to refreshing LSA which provides fast convergence and recovery when there is a change in network topology. The present invention satisfies these needs, as well as others, and generally overcomes the deficiencies found in the background art.
BRIEF DESCRIPTION OF THE INVENTION
The invention is a method and system for reducing OSPF flooding and traffic in a networked system. The invention is generally embodied in software executed by one or more router devices in the system. The flood reduction algorithm may be enabled for one or more ports of the router device. The flood reduction algorithm may further be used in conjunction with conventional OSPF and OSFF DC where flood reduction is not enabled for a particular port. For example, a router may comprise a first and second interface port, the first port configured with flood reduction and the second configured for conventional OSPF.
The invention relates to machine readable media on which are stored embodiments of the present invention. It is contemplated that any media suitable for retrieving instructions is within the scope of the present invention. By way of example, such media may take the form of magnetic, optical, or semiconductor media. The invention also relates to data structures that contain embodiments of the present invention, and to the transmission of data structures containing embodiments of the present invention.
According to a first embodiment of the invention, the method for reducing OSPF protocol flooding comprises enabling the hello protocol for a flood reduction-enabled port and communicating a do not age link state advertisement via the port. When a change in the network topology is subsequently determined, the method further comprises communicating subsequent do not age link state advertisements to communicate the change in network topology when the change in topology is determined.
According to a second embodiment of the invention, the flood reduction apparatus comprises means for enabling hello protocol for a flood reduction-enabled port and means for communicating do not age link state advertisements via the port.
An object of the invention is to provide method and system for reducing OSPF flooding which overcomes the deficiencies of the prior art.
Another object of the invention is to provide a method and system for reducing OSPF flooding which provides fast convergence and recovery when there is a change in network topology
Further objects and advantages of the invention will be brought out in the following portions of the specification, wherein the detailed description is for the purpose of fully disclosing the preferred embodiment of the invention without placing limitations thereon.
REFERENCES:
patent: 5687168 (1997-11-01), Iwata
patent: 6147971 (2000-11-01), Rochberger et al.
patent: 6349091 (2002-02-01), Li
patent: 6418139 (2002-07-01), Akhtar
“Open Shortest Path First”,Internetworking Technologies Handbook, Chapter 46, p. 46-46-6, 1999. (no month).
Cisco Technology Inc.
Ho Duc
Sierra Patent Group Ltd.
LandOfFree
Method and apparatus for reducing OSPF flooding 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 reducing OSPF flooding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reducing OSPF flooding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3308278