Method and apparatus for discovering network topology

• US 20020143905A1
• Filed: 03/30/2001
• Published: 10/03/2002
• Est. Priority Date: 03/30/2001
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Durham, David M., Govindarajan, Priya
• Granted Patent: US 7,263,552 B2
• Time in Patent Office: Days
• US Class Current: 709/220
• 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:

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;

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

2. The method of claim 1, wherein identifying the second network device comprises receiving an address of the second network device from a third network device.

3. 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.

4. The method of claim 3, 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.

5. 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.

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

7. The method of claim 1, further comprising:

identifying a third network device at the first network device;

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.

8. The method of claim 1, further comprising sending a packet to a third network device to provoke the third 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.

9. The method of claim 1, further comprising sending a packet to a third network device addressed to a port that does not exist on the third 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.

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

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;

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

11. The medium of claim 10, wherein the instructions for identifying the second network device further comprise instructions which, when executed by the machine, cause the machine to perform further operations comprising receiving an address of the second network device from a third network device.

12. The medium of claim 10, 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 10, 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 greater time to live until a message reaches the second network device.

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

identifying a third network device at the first network device;

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.

15. The medium of claim 10, further comprising instructions which, when executed by the machine, cause the machine to perform further operations comprising sending a packet to a third network device to provoke the third 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.

17. The method of claim 16, wherein identifying the second network device comprises receiving an identification of the second network device, including its address from a policy server.

18. 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 selecting an interface that corresponds to any reply received to the PING message from the second network device.

19. The method of claim 16, wherein the Traceroute message 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.

20. The method of claim 16, further comprising sending a packet to a third network device addressed to a port that does not exist on the third 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.

16. A method comprising:

identifying a second network device at a first network device;

sending a Traceroute message 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;

compiling the addresses to determine the topology of the network.