Abstract:
A method of administering a plurality of routers in a computer network, comprising initializing a router in the plurality; receiving initial database description packets from at least first and second neighboring routers; processing the data description packet received from the first neighboring router; generating a request for link state advertisements from the first neighboring router; processing the database description packet received from the second neighboring router; if requesting link state advertisements from the second neighboring router that were not requested from the first neighboring router.

Description:
FIELD 
     The present invention relates broadly to computer networks employing routers that communicate link-state requests to each other. Specifically, the present invention relates to elimination of unnecessary traffic in the form of link-state requests between routers. 
     BACKGROUND 
     Open shortest path first (OSPF) is an Internal gateway protocol that was designed to be used internally in a single, autonomous system. OSPF uses link state or shortest path first-based technology (as compared to the distance-vector or Bellman-Ford technology found in routing protocols such as routing information protocol (RIP). Individual link state advertisements (LSAs) describe pieces of the OSPF routing domain (autonomous system). These LSAs are flooded throughout the routing domain, forming the link state database. Each router has an identical link state database; synchronization of link state databases is maintained via a reliable flooding algorithm. From this link state database, each router builds a routing table by calculating a shortest-path tree, with the root of the tree being the calculating router itself. This calculation is commonly referred to as the Dijkstra procedure. 
     LSAs are small. Each advertisement describes a small piece of the OSPF routing domain, such as the neighborhood of a single router, the neighborhood of a single transit network, a single inter-area route or a single external route. 
     This type of routing protocol requires each router to maintain at least a partial map of the network. When a network link changes state (up to down, or vice versa), an LSA is flooded throughout the network. All the routers note the change, and recompute their routes accordingly. This method is more reliable, easier to debug and less bandwidth-intensive than distance-vector methods. It is also more complex and more computationally- and memory-intensive. OSPF and OSI&#39;s IS-IS are link state routing protocols. 
     Adjacency, as referred to herein, is a relationship formed between selected neighboring OSPF routers for the purpose of exchanging routing information. When the link state databases of two neighboring routers are synchronized, the routers are said to be adjacent. Not every pair of neighboring routers becomes adjacent. The fact that routers are neighbors is not sufficient to guarantee an exchange of link state updates; they must form adjacencies to exchange link state updates. Adjacency is an advanced form of neighborship formed by routers that are willing to exchange routing information after negotiating parameters of such an exchange. Routers reach a FULL state of adjacency when they have synchronized views on a link state database. 
     Interface type plays a major role in how the adjacencies are formed. For example, neighbors on point-to-point links always try to become adjacent, while routers attached to broadcast media such as Ethernet may choose to become adjacent only with a subset of neighboring routers on the interface. 
     Once a router decides to form an adjacency with a neighbor, it starts by exchanging a full copy of its link state database. The neighbor, in turn, exchanges a full copy of its link state database with the router. After passing through several neighbor states, the routers become fully adjacent. 
     As stated above, OSPF is a link state protocol. When an OSPF-compliant router starts to speak with another router, it brings up an adjacency via a database exchange process. The database exchange is an attempt to synchronize the link state database of the two routers. Any missing information is requested from the neighbor. This does not scale, if a routers starts to speak with many other routers. It could potentially request the same information from all the adjacent routers. Each such request results in an LSA update, which must be reliably acknowledged. This results in unnecessary control packet transmissions. 
     When a router receives from a neighbor a database description (DBD) packet containing LSA descriptions that are not present in its local link state database, the router sends out a link state request (LSREQ) directed towards the neighbor. In the case of multiple adjacencies coming up at the same time, the link state database synchronization process could request the same LSA from multiple peers. 
     The neighbor replies to these requests in one or more link state update (LSUPD) packets. Each such duplicate request results in a duplicate update from the peer. Each such LSUPD further results in the sending of an acknowledgement (ACK). 
     The protocol described above becomes expensive in wireless environments, such as mobile, ad hoc networks where not only are unnecessary OSPF packets sent, but these packets can be retransmitted many times due to packet loss. This results in higher control traffic overhead and poor routing convergence. Thus, there is a heartfelt need for reduction and load balancing of link state requests in an OSPF-compliant system of network routers. 
     SUMMARY 
     The present invention reduces the link state requests, thus reducing duplicate updates and ACKs sent in such circumstances. The present invention suppresses LSREQs for LSAs that have already been requested from at least one neighboring router. This moves the LSREQ scope from a neighbor to the LSAs&#39; flooding scope. In an embodiment, the present invention also provides failsafe mechanisms that try to send a LSREQ to other possible neighbors in case the current neighbor does not respond. 
     In one aspect, the present invention provides a method of administering a plurality of routers in a computer network, comprising initializing a router in the plurality; receiving initial database description packets from at least first and second neighboring routers; processing the data description packet received from the first neighboring router; generating a request for link state advertisements from the first neighboring router; processing the database description packet received from the second neighboring router; if requesting link state advertisements from the second neighboring router that were not requested from the first neighboring router. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates a network of routers in accordance with the present invention; 
         FIG. 2  illustrates in block diagram form the major components of a router in accordance with the present invention; and 
         FIG. 3  illustrates in flow chart form a sequence of acts performed in accordance in an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     Directing attention to  FIG. 1 , there is shown an exemplary network of routers in accordance with the present invention. Routers  10 - 70  function to pass traffic in the form of packetized data between points  100 ,  200 . Points  100 ,  200  can be individual, end user computer systems, local area networks, wider area networks, and may even be separate computer networks containing additional routers, but in each case data packets are sent through at least some of the routers  10 - 70  between points  100 ,  200 . While  FIG. 1  illustrates a network having a specific number of routers  10 - 70 , it is to be understood that various configurations of routers can be implemented in accordance with the present invention. Such variations include the number of routers included, as well as the communication medium employed between the routers. Routers  10 - 70  can communicate with each other over wireless media as well as wired media, as can points  100 ,  200 . 
       FIG. 2  illustrates an exemplary embodiment of routers  10 - 70 . Router  200  includes communication connection  210 , processor  212 , memory  214 , link state database  216 , routing table  218 , timer  220 , and retransmit list  222 . Other components, commonly found in routers known to those skilled in the art, are included in router  200 , but are not illustrated. 
     Operation of the present invention is described with reference to the sequence of acts illustrated in  FIG. 3 . In an embodiment, when router  10  is coming up (act  300 ), it needs to bring up neighborship with two routers  20  and  30 . It&#39;s assumed that router  20  and router  30  are already synchronized and have identical databases. In this case, router  10  receives an initial DBD packet from both router  20  and router  30  (act  302 ). In the case where the DBD packet received from router  20  gets processed first (act  304 ), router  10  will generate one LSREQ packet (act  306 ), requesting all of the LSAs it does not have from router  20 . Processing a DBD packet allows router  10  to inspect all headers in the list of headers of LSAs included in the DBD packet. 
     When router  10  processes the initial DBD packet received from router  30  (act  308 ), router  10  determines whether the initial DBD packet received from router  30  contains headers for LSAs that were not included in the initial DBD packet from router  20  (decision act  310 ). Router  10  only generates a request for LSAs that it has not already requested from router  20  (act  312 ). In cases where the DBD packet is formed in a predictable fashion, both initial DBD packets from router  20  and router  30  are almost identical. In this case, router  10  doesn&#39;t generate a request after processing this initial DBD packet from router  30 . Even though router  10  doesn&#39;t request anything from router  30 , it still behaves as if it requested the LSAs from router  30  by putting this LSA on its LSREQ retransmit list (act  314 ). 
     If router  20  does not respond within a retransmit interval (decision act  316 ), a request is now sent to both router  20  and router  30  (act  318 ). While act  318  is illustrated as looping back to decision act  316 , in an alternative embodiment, sending the request to multiple routers is performed only once. An update received from either router  20  or router  30  satisfies the LSREQ retransmit entry for both router  20  and router  30 . When the LSUPD arrives (either from router  20  or another router) (act  320 ), router  10  services any pending request (act  322 ) for the same LSA from all the neighbors (router  20  and router  30  in this example). The LSA is then removed from the LSA retransmit list (act  324 ). 
     The present invention is particularly useful in cases where a router has to bring up adjacency with tens or hundreds of peers at the same time such as due to mobility. But in case of lossy environments, it&#39;s possible that the first request doesn&#39;t generate a LSUPD response, thus triggering retransmits from all of the pending neighbors. 
     An embodiment of the present invention implements a round robin scheme that tries sending LSREQ to all eligible neighbors before retransmitting an LSREQ to the same neighbor. This is simply done by using a shorter (perhaps one half of the interval period) retransmit interval timer for the neighbors to which router  10  has pretended to have sent LSREQ. Every LSREQ sent results in an addition of one half of the retransmit interval to currently waiting timers. 
     To further explain this feature, assume there is a need to request a certain LSA from neighboring routers  20 ,  30  and  40 . Also assume the worst case, where neighbors are not able to reply with an LSUPD packet. In accordance with the present invention, the request is first sent to router  20 . After one half of the retransmit interval passes, the timer for router  30  expires, and a request is sent to router  30 . The retransmit timers for router  40  and router  20  are pushed by another retransmit interval. After time equal to one half of the retransmit interval passes, the timer for router  40  expires. 
     While a method and apparatus for reducing and load balancing link state requests in a network of routers have been illustrated and described in detail, it is to be understood that numerous modifications can be made to embodiments of the present invention without departing from the spirit thereof.