Methods and systems for unnumbered network link discovery

• US 7,292,541 B1
• Filed: 01/28/2004
• Issued: 11/06/2007
• Est. Priority Date: 01/28/2004
• Status: Expired due to Fees

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: C S, Raja Shekar
• Primary Examiner(s): Kizou; Hassan
• Assistant Examiner(s): Lee; Betty E.
• Application Number:
  US10/766,715
• Time in Patent Office: 1,378 Days
• Field of Search: 370/254, 370/255, 370/256, 370/257, 370/258, 709/223, 709/224
• US Class Current: 370/254
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery

Abstract

Embodiments of the present invention relate to methods and systems for automatically determining the network topology of a computer network containing unnumbered or unaddressed links between network devices, such as routers. The method according to one embodiment uses the network management information data available with each router. From the information, the embodiment can determine all routers connected to a given unnumbered interface. The embodiment can also automatically determine which of these routers is the immediate neighbor by comparing how they connect (via interface number) to the unnumbered interface and how they connect to each other. If the immediate neighbor is found to have a route back to the examined router or a default route, a link between the immediate neighbor and the unnumbered interface can then be stored and identified in the network topology. The method can be repeated in cycles to determine topology changes.

Claims

1. A method for discovery of network topology in networks having network routers with unnumbered interfaces connecting to next-hop routers having an assigned unknown destination network number, the method comprising:

obtaining a configuration of every routers in a network;

for a particular router of the every router in the network identifying an unnumbered interface;

for the unnumbered interface of the particular router, identifying all connected routers reachable through the unnumbered interface including the next-hop routers and routers connected beyond the next-hop routers and adding said all connected routers to a connected router list for the unnumbered interface, wherein at least one of the next-hop routers and one of the routers connected beyond the next-hop routers has the assigned unknown destination network number;

for the all connected routers in the connected router list, determining which of the all connected routers is an immediate neighbor to the particular router having the unnumbered interface;

determining a connected interface of the immediate neighbor which connects to the unnumbered interface of the particular router;

identifying an unnumbered link between the unnumbered interface and the connected interface; and

repeating the identifying an unnumbered interface and identifying all connected routers for each of the every router in the network.

2. The method as recited in claim 1, wherein the determining which of the all connected routers is the immediate neighbor further includes checking for an intermediate router in the connected router list between the particular router and the immediate neighbor.

3. The method as recited in claim 2, wherein the checking further includes determining whether the immediate neighbor connects to the unnumbered interface and to the routers connected beyond the next-hop routers over different interfaces.

4. The method as recited in claim 2, wherein the checking further includes utilizing values in a route table having an interface index and a route destination.

5. The method as recited in claim 1, further comprising:

confirming that the immediate neighbor connects to the unnumbered interface via a network route or a default route over an unnumbered interface.

6. The method as recited in claim 1, further comprising:

storing the unnumbered link in a connectivity list; and

periodically updating the connectivity list.

7. The method as recited in claim 6, wherein the connectivity list is periodically updated by repeating determining whether the unnumbered link is identified in a current or a previous cycle.

8. A method for automated discovery of network topology in networks having network routing devices with unnumbered interfaces connecting to next-hop routers with an assigned unknown destination network number, the method comprising:

for a routing device in a network, identifying an unnumbered interface of the routing device;

identifying connected routing devices connected to the unnumbered interface including the next-hop routers and routers connected beyond the next-hop routers, at least one of the next-hop routers and one of the routers connected beyond the next-hop routers having the assigned unknown destination network number;

determining which of the connected routing devices is an immediate neighbor to the routing device having the unnumbered interface;

identifying an unnumbered link between the unnumbered interface and a corresponding interface of the immediate neighbor; and

indicating the unnumbered link in network topology data.

9. The method as recited in claim 8, wherein the operation of deter g the immediate neighbor is conducted by determining which connected routing device connects to the unnumbered interface and to all other connected routing devices over different interfaces.

10. The method as recited in claim 9, wherein the determining operation utilizes values in a route table for each connected router, the values comprising an interface index and a route destination.

11. The method as recited in claim 8, further comprising:

confirming that the immediate neighbor connects to the unnumbered interface via a network route or a default route.

12. A method for automated discovery of network topology in networks having network routing devices with unnumbered links, the method comprising:

identifying an unnumbered interface of a routing device in a network;

using route data of a connected router list to identify connected routing devices connected to the unnumbered interface including identifying next-hop routers and routers connected beyond the next-hop routers, wherein at least one of the next-hop routers and one of the routers connected beyond the next-hop routers has an assigned unknown destination network number;

for the next-hop routers and the routers connected beyond the next-hop routers identifying all connected routing devices and adding the all connected routing devices to the connected router list;

for every of the connected routing devices and the all connected routing devices of the connected router list, comparing interface connections; and

using the compared interface connections to identify an unnumbered link between the unnumbered interface and a corresponding interface of one of the connected routing devices, the one of the connected routing devices being an immediate neighbor listed on the connected router list as one of the next-hop routers.

13. The method as recited in claim 12, wherein the comparing utilizes route destination and corresponding interface data.

14. A computer network, comprising:

at least two network devices connected to one another in a next-hop configuration, one device having an unnumbered interface connected to an unnumbered interface of the other device thereby defining a link that is unnumbered, wherein the one device and the other device each has an assigned unknown destination network number corresponding to the other device and the one device, respectively;

network management information data on a connected router list indicating interface assignments of the two network devices; and

a network management system configured to access the network management information data on the connected router list, to confirm that the network devices are immediate neighbors and connect to one another via unnumbered interfaces, to assign an identifier of the unnumbered link, and to present that identifier in network topology data, wherein the confirmation that the network devices are said immediate neighbors and connect to one another further includes configuration of the network management system to examine the connected router list and compare each said interface assignment of the two network devices and determine whether the other device connects to the one device over a different interface assignment or the other device connects to still another network device having the assigned unknown destination network number.

15. The network as recited in claim 14, wherein the two network devices comprise routing devices.

16. The network as recited in claim 15, wherein the routing devices comprise routers.