Topology discovery by partitioning multiple discovery techniques

• US 7,069,343 B2
• Filed: 04/22/2002
• Issued: 06/27/2006
• Est. Priority Date: 09/06/2001
• Status: Active Grant

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Incorporated
• Inventors: Krumm-Heller, Alex M., Schreuder, James D., Minhazuddin, Muneyb, Goringe, Christopher M.
• Primary Examiner(s): Etienne, Ario
• Assistant Examiner(s): NANO, SARGON N
• Application Number:
  US10/127,888
• Publication Number:
  US 20030046427A1
• Time in Patent Office: 1,527 Days
• Field of Search: 709/224, 709/238, 709/239, 709/240, 709/241, 709/242, 709/217, 709/218, 709/220, 709/228, 709/249, 370/285, 370/401
• US Class Current: 709/249
• CPC Class Codes: H04L 41/046 comprising network management agents or mobile agents therefor
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/42 Centralised routing

Abstract

A system for discovering a topology of a distributed processing network that includes a first topology discovery agent 308 configured to contact a first set of routers to obtain a first type of information stored in each router in the first set of routers; a second topology discovery agent 312 and/or 316 configured to contact a second set of routers to obtain a second type of information stored in each router in the second set of routers, and a phase controller 304 configured to select between the first and second topology discovery agents. The first and second sets of routers are different, and the first and second types of information are different. In one configuration, the first type of information is defined by a network management protocol, and the second type of information is defined by a routing protocol.

Claims

1. A topology discovery method, comprising:

(a) contacting each router in a first set of routers, the first set of routers being part of a common autonomous system;

(b) for each contacted router in the first set of routers, accessing a first set of managed objects and/or variables defined by a network management protocol, the first set of managed objects and/or variables comprising a listing of interface addresses corresponding to the contacted router, how each interface address is connected to a next hop interface of another router, and an interior gateway routing protocol identifier identifying an interior gateway routing protocol present on each link between an interface of the contacted router and the corresponding next hop interface;

(c) for each contacted router in the first set of routers, processing the first set of managed objects and/or variables to identify each next hop interface and, for each next hop interface, how the corresponding interface of the contacted router is connected to the selected next hop interface and an interior gateway routing protocol identifier identifying an interior gateway routing protocol present on each link between the corresponding interface of the contacted router and the selected next hop interface;

(d) based on the first set of managed objects and/or variables, determining a second set of routers using a first interior gateway routing protocol, the second set of routers being in the autonomous system;

(e) contacting each router in the second set of routers;

(f) for each contacted router in the second set of routers, accessing a second set of objects and/or variables defined by the first interior gateway routing protocol, the second set of managed objects and/or variables comprising a listing of interface, link, and/or network addresses corresponding to the members of the second set of routers; and

(g) processing the first and second sets of objects and/or variables to provide a network topology model.

2. The method of claim 1, further comprising:

(h) based on the first set of managed objects and/or variables, determining a third set of routers using a second interior gateway routing protocol different from the first interior gateway routing protocol, the third set of routers being in the autonomous system;

(i) contacting each router in the third set of routers; and

(j) for each contacted router in the third set of routers, accessing a third set of objects and/or variables defined by the second interior gateway routing protocol, the third set of managed objects and/or variables comprising a listing of interface, link, and/or network addresses corresponding to the members of the third set of routers, wherein in step (g) the first, second, and third sets of objects and/or variables are processed to provide the network topology model.

3. The method of claim 1, wherein the memberships of the first and second routers are different.

4. The method of claim 1, wherein the network management protocol is one of the Simple Network Management Protocol, CDP, and the Common Management Information Protocol and the first interior gateway routing protocol is one of Open Shortest Path First protocol, RIP, RIP-2, IS-IS of OSI, EIGRP, and Netware'"'"'s Link Service'"'"'s Protocol.

5. The method of claim 2, wherein the first and second interior gateway protocols are selected from the group consisting of Open Shortest Path First protocol, RIP, RIP-2, IS-IS of OSI, EIGRP, and Netware'"'"'s Link Service'"'"'s Protocol.

6. The method of claim 2, wherein the second set of routers is in a first protocol area, wherein the first protocol area uses the first interior gateway routing protocol, wherein the third set of routers are in a second protocol area, and wherein the second protocol area uses the second interior gateway routing protocol.

13. The method of claim 1, wherein the accessing step (b) comprises:

accessing the first set of managed objects and/or variables contained in the ipAddr table, ipAddrTable table, ipRouteTable table, and ipRouteEntry table.

14. The method of claim 1, wherein in processing step (c) when a packet can pass directly from the contacted router interface to the network, the network is assumed to be a stub network and when a packet must pass from the contacted interface through a network to reach another network, the intermediate network is assumed to be a transport network.

15. The method of claim 1, wherein step (c) produces, for each router in the first set of routers a first set of interface addresses, wherein step (f) produces, for each in the second set of routers, a second set of interface addresses, wherein a plurality of routers are in both the first and second sets of routers, and further comprising:

comparing the first and second lists of interface addresses to identify, for each router in the first and second sets of routers, duplicative and conflicting addresses;

removing duplicative addresses from a composite list of interface addresses; and

for conflicting addresses, use the corresponding addresses in the first list of addresses.

7. A topology discovery system, comprising:

(a) a first topology discovery agent operable to;

(i) contact each router in a first set of routers, the first set of routers being part of an autonomous system;

(ii) for each contacted router in the first set of routers, access a first set of managed objects and/or variables defined by a network management protocol, the first set of managed objects and/or variables comprising a listing of interface addresses corresponding to the contacted router, how each interface address is connected to a next hop interface of another router, and an interior gateway routing protocol identifier identifying an interior gateway routing protocol present on each link between an interface of the contacted router and the corresponding next hop interface;

(iii) for each contacted router in the first set of routers, process the first set of managed objects and/or variables to identify each next hop interface and, for each next hop interface, how the corresponding interface of the contacted router is connected to the selected next hop interface and an interior gateway routing protocol identifier identifying an interior gateway routing protocol present on each link between the corresponding interface of the contacted router and the selected next hop interface;

(b) a second topology discovery agent operable to;

(i) determine a second set of routers using a first interior gateway routing protocol, the second set of routers being part of the autonomous system;

(ii) contact each router in a second set of routers;

(iii) for each contacted router in the second set of routers, accessing a second set of objects and/or variables defined by the first interior gateway routing protocol, the second set of managed objects and/or variables comprising a listing of interface, link, and/or network addresses corresponding to the members of the second set of routers; and

(b) a phase controller operable to;

(i) based on the first set of managed objects and/or variables, select between the first and topology discovery agents to effect topology discovery; and

(ii) process the first and second sets of objects and/or variables to provide a network topology model.

8. The system of claim 7, further comprising:

(c) a third topology discovery agent operable to;

(i) based on the first set of managed objects and/or variables, determine a third set of routers using a second interior gateway routing protocol different from the first interior gateway routing protocol, the third set of routers being part of the autonomous system;

(ii) contact each router in the third set of routers; and

(iii) for each contacted router in the third set of routers, access a third set of objects and/or variables defined by the second interior gateway routing protocol, the third set of managed objects and/or variables comprising a listing of interface, link, and/or network addresses corresponding to the members of the third set of routers and wherein the phase controller is operable to process the first, second, and third sets of objects and/or variables are processed to provide the network topology model.

9. The system of claim 7, wherein the memberships of the first and second routers are different.

10. The system of claim 7, wherein the network management protocol is one of the Simple Network Management Protocol, CDP, and the Common Management Information Protocol and the first routing protocol is one of Open Shortest Path First protocol, RIP, RIP-2, IS-IS of OSI, EIGRP, and Netware'"'"'s Link Service'"'"'s Protocol.

11. The system of claim 8, wherein the first and second interior gateway protocols are selected from the group consisting of Open Shortest Path First protocol, RIP, RIP-2, IS-IS of OSI, EIGRP, and Netware'"'"'s Link Service'"'"'s Protocol.

12. The method of claim 8, wherein the second set of routers is in a first protocol area, wherein the first protocol area uses the first interior gateway routing protocol, wherein the third set of routers are in a second protocol area, and wherein the second protocol area uses the second interior gateway routing protocol.

16. The system of claim 7, wherein the accessing operation (ii) comprises:

accessing the first set of managed objects and/or variables contained in the ipAddr table, ipAddrTable table, ipRouteTable table, and ipRouteEntry table.

17. The system of claim 7, wherein in processing operation (iii) when a packet can pass directly from the contacted router interface to the network, the network is assumed to be a stub network and when a packet must pass from the contacted interface through a network to reach another network, the intermediate network is assumed to be a transport network.