Method and apparatus for discovering network topology

• US 7,263,552 B2
• Filed: 03/30/2001
• Issued: 08/28/2007
• Est. Priority Date: 03/30/2001
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Durham, David M., Govindarajan, Priya
• Primary Examiner(s): Huynh; Kim
• Assistant Examiner(s): SORRELL, ERON J
• Application Number:
  US09/822,539
• Publication Number:
  US 20020143905A1
• Time in Patent Office: 2,342 Days
• Field of Search: 709/220, 709/223, 709/238, 709/242, 709/250, 709/224, 370254-258
• US Class Current: 709/224
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]

Abstract

A method and apparatus are provided that allow the automatic discovery of the topology of a network. In one embodiment, the invention includes identifying a second network device at a first network device, sending a message from the first network device to the second network device, the message establishing the identity of any network device between the first network device and the second network device, and compiling the established identities to determine the topology of the network. The invention can use PING and Traceroute utilities to find nodes and identify network devices.

Claims

1. A method comprising:

registering a first network device and a second network device to a policy server;

receiving network discovery policies from the policy server at the first and second network devices;

identifying the second network device at the first network device in accordance with the received policies by receiving an address of the second network device from a third network device, the third network device being different from the policy server;

sending a message from the first network device to the second network device, the message establishing the identity of any network device between the first network device and the second network device in accordance with the received policies; and

compiling the established identities to determine the topology of the network.

2. The method of claim 1, wherein the first network device comprises a plurality of network interfaces, the method further comprising selecting an interface to the second device by sending a packet from each of the plurality of network interfaces to an address of the second network device and selecting an interface that corresponds to any reply received from the second network device.

3. The method of claim 2, wherein sending a packet from each of the plurality of network interfaces comprises sending a PING packet from each of the plurality of network interfaces.

4. The method of claim 1, wherein sending the message comprises sending a plurality of messages to the second network device, each message having an incrementally greater time to live until a message reaches the second network device.

5. The method of claim 1, wherein sending the message comprises executing a route tracing utility at the first network device to determine the route of a packet between the first and second network device.

6. The method of claim 1, further comprising:

identifying a fourth network device at the first network device; and

sending a message from the first network device to the third network device, the message establishing the identity of any network device between the first network device and the third network device.

7. The method of claim 1, further comprising sending a packet to a fourth network device to provoke the fourth network device to identify an address corresponding to a port at which the packet was received and wherein compiling further comprises compiling the identified address.

8. The method of claim 1, further comprising sending a packet to a fourth network device addressed to a port that does not exist on the fourth network device in order to provoke the third network device to send an error message to the first network device that identifies an address of the third network device corresponding to the port at which the packet was received and wherein compiling further comprises compiling the identified address.

9. The method of claim 1, further comprising sending the established identities to the policies server in accordance with the received policy.

10. The method of claim 9 wherein compiling comprises compiling the established identities at the policy server to determine the topology of the network.

11. A machine-readable storage medium having stored thereon data representing sequences of instructions which, when executed by a machine, cause the machine to perform operations comprising:

registering a first network device and a second network device to a policy server;

receiving network discovery policies from the policy server at the first and second network devices;

identifying the second network device at the first network device in accordance with the received policies by receiving an address of the second network device from a third network device, the third network device being different from the policy server;

sending a message from the first network device to the second network device, the message establishing the identity of any network device between the first network device and the second network device in accordance with the received policies; and

compiling the established identities to determine the topology of the network.

12. The medium of claim 11, wherein the first network device comprises a plurality of network interfaces, the instructions further comprising instructions which, when executed by the machine, cause the machine to perform further operations comprising selecting an interface to the second device by sending a packet from each of the plurality of network interfaces to an address of the second network device and selecting an interface that corresponds to any reply received from the second network device.

13. The medium of claim 11, wherein the instructions for sending the message further comprise instructions which, when executed by the machine, cause the machine to perform further operations comprising sending a plurality of messages to the second network device, each message having an incrementally &

eater time to live until a message reaches the second network device.

14. The medium of claim 11, further comprising instructions, when executed by the machine, cause the machine to perform further operations comprising:

identifying a fourth network device at the first network device; and

sending a message from the first network device to the third network device, the message establishing the identity of any network device between the first network device and the fourth network device.

15. The medium of claim 11, further comprising instructions which, when executed by the machine, cause the machine to perform further operations comprising sending a packet to a fourth network device to provoke the fourth network device to identify an address corresponding to a port at which the packet was received and wherein the instructions for compiling comprise further instructions which, when executed by the machine, cause the machine to perform further operations comprising compiling the identified address.

16. A method comprising:

registering a first network device and a second network device to a policy server;

receiving network discovery policies from the policy server at the first and second network devices;

identifying the second network device at the first network device in accordance with the received policies by receiving an address of the second network device from a third network device, the third network device being different from the policy server;

sending a route tracing packet from the first network device to the second network device, to determine addresses of any network device between the first network device and the second network device in accordance with the received policies; and

compiling the addresses to determine the topology of the network.

17. The method of claim 16, wherein the first network device comprises a plurality of network interfaces, the method further comprising selecting an interface to the second device by sending a PING message from each of the plurality of network interfaces to an address of the second network device and selective an interface that corresponds to any reply received to the PING message from flue second network device.

18. The method of claim 16, wherein the route tracing packet comprises a plurality of messages to the second network device, each message having an incrementally greater time to live until a message reaches the second network device.

19. The method of claim 16, further comprising sending a packet to a fourth network device addressed to a port that does not exist on the fourth network device in order to provoke the third network device to send an error message to the first network device that identifies an address of the third network device corresponding to the port at which the packet was received and wherein compiling further comprises compiling the identified address.