System and method for network topology discovery

• US 7,567,523 B2
• Filed: 01/29/2004
• Issued: 07/28/2009
• Est. Priority Date: 01/29/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Black, Richard, Donnelly, Austin, Fournet, Cedric
• Primary Examiner(s): Cho; Hong
• Application Number:
  US10/768,582
• Publication Number:
  US 20050169193A1
• Time in Patent Office: 2,007 Days
• Field of Search: 370252-256, 370/351, 370/389, 370/392, 370/400, 370/401, 709/208, 709/209, 709220-224
• US Class Current: 370/255
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• 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 43/0829 Packet loss
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/26 Route discovery packet

Abstract

A system and method for discovering network topology by various switch training and probing methods. Segments are discovered by having computers enter a promiscuous mode and determining from packets sent to a selected computer which computers see which other computers in the network. From the segments, various switch interconnections are determined, by having different computers train switches as to a training address and seeing which computers receive probe packets sent to that training address from another computer. Various training and probing methods are described that locate intermediate segments, deep switches, switch interconnections, and edge and singleton cases. In one implementation, a master computer coordinates the other computers (and devices) in the network to send the training and probing packets, and report on received packets, in order to determine the network topology.

Claims

1. In a computer network, a method for discovering information about a topology of the network, comprising:

training a switch with a training message sent from a first computer so that the switch knows a training address, the training address comprising an address that is known by the switch, such that the switch can use the training address as a base in determining which other computers have access to the training address;

probing with a probe message sent from a second computer to the training address;

determining which other computer or computers in the network see the probe message;

detecting at least one segment in the network, the detecting including placing a plurality of computers in the network into a promiscuous mode, selecting a master computer, and, at each computer other than the master computer;

a) sending a packet to the master computer;

b) recording any packet observed from another computer sent to the master computer; and

c) reporting the source address of each packet observed; and

collecting the source addresses of the packets observed in order to determine which computers see which other computer or computers in the network.

2. The method of claim 1 wherein detecting the at least one segment further comprises, constructing a matrix indicative of whether each computer sees each other computer in the network, and analyzing the matrix, a given computer being in a segment with another computer when the given computer can see the other computer and the other computer can see the given computer.

3. The method of claim 1 further comprising sending a packet from the master computer to an address distinct from those belonging to any computer on the network, such that any computer on the segment of the master computer will see the packet to the distinct address.

4. The method of claim 1 further comprising sending a packet from the master computer such that any computer on the segment of the master computer will see the packet to the distinct address, and no computer on any other segment will see the packet.

5. The method of claim 4 wherein sending the packet from the master computer comprises the master computer first sending a packet from a distinct address to another address, and further comprising, sending a packet from the master computer'"'"'s address to the distinct address.

6. The method of claim 1 further comprising, determining a segment leader for each segment, and wherein training the switch with the training message sent from the first computer comprises training the switch with the training message sent from a first segment leader, and wherein probing with the probe message sent from the second computer comprises probing the switch with the probe message sent from a second segment leader.

7. The method of claim 1 wherein training a switch comprises, for a first segment leader of a first segment, training any switches attached to the first segment by sending a training message from a training address, and further comprising, for a second segment leader of a second segment, training any switches attached to the second segment by sending a message from the training address.

8. The method of claim 7 wherein probing with a probe message comprises sending a packet from the first segment leader to the training address to determine how each switch attached to the first segment was trained.

9. A computer-readable medium encoded with computer-executable instructions for performing the method of claim 1.

10. In a computer network, a method of detecting at least one segment in the network comprising:

placing a plurality of computers in the network into a promiscuous mode;

selecting a collector computer;

at each computer other than the collector computer

a) sending a packet to the collector computer;

b) recording any packet observed from another computer sent to the collector computer; and

c) reporting the source address of each packet observed;

collecting the source addresses of the packets observed; and

determining which computers see which other computer or computers in the network based on the source addresses collected.

11. The method of claim 10 further comprising, constructing a matrix indicative of whether each computer sees each other computer in the network, and analyzing the matrix such that a first computer is in a segment with a second computer when the first computer can see the second computer and the second computer can see the first computer.

12. The method of claim 10 wherein a master computer collects the source addresses and determines which computers see which other computer or computers in the network.

13. The method of claim 10 wherein the collector computer sends a packet to a distinct address such that any computer on the segment of the collector computer will see the packet sent to the distinct address.

14. The method of claim 10 further comprising, determining a segment leader for each segment.

15. The method of claim 14 further comprising, determining whether there is an intermediate segment between switches, including, selecting a segment leader as a distinguished computer that is of a different segment than the collector computer, at each segment leader other than the distinguished computer:

a) sending a packet to distinguished computer;

b) recording any packet observed from another segment leader sent to the distinguished computer; and

c) reporting the source address of each packet observed;

collecting the source addresses of the packets observed; and

determining whether the collector computer'"'"'s segment is asymmetric, and if so, determining that the collector computer'"'"'s segment is an intermediate segment.

16. The method of claim 14 further comprising, for a first segment leader of a first segment, training any switches attached to the first segment by sending a training message from the training address, and further comprising, for a second segment leader of a second segment, training any switches attached to the second segment by sending a message from the training address.

17. The method of claim 16 further comprising, probing with a probe message from the first segment leader to the training address to determine how each switch attached to the first segment was trained.

18. The method of claim 14 further comprising, having each segment leader, in turn, train any switches attached to its segment with a particular address which is the same for each segment leader, having each segment leader, in turn, send a probe packet to the particular address such that each switch adjacent a segment leader will deliver the probe packet to the segment attached to that switch which most recently had its segment leader send the train message, collecting the results from each segment leader as to whether the probe packet was received, and unifying the results to determine which segments share a switch and which segments are attached to a switch to which no other segment is attached.

19. The method of claim 18 wherein the segment leaders send the train messages in an order comprising a tree ordering on the segments in the network.

20. The method of claim 19 further comprising, constructing a matrix indicative of whether each computer sees each other computer in the network, and wherein the tree order comprises the tree order rooted at the collector computer and generated from the matrix.

21. The method of claim 14 further comprising, having each segment leader train its local switch with a training address that is different from the training address of another segment leader, probing the training address of each other segment leader, collecting information as to each probe packet received at each segment leader, and processing the information to determine an interconnection of switches in the network.

22. The method of claim 10 further comprising, selecting as a switch leader a representative computer from among each segment attached to a switch.

23. The method of claim 22 wherein a plurality of switch leaders are selected corresponding to a plurality of switches, and further comprising, allocating different training addresses, each different address corresponding to a different switch leader;

having each switch leader train its local switch with the training addresses of the other switch leaders, having each switch leader probe its corresponding switch with the training address corresponding to that switch leader, collecting information as to each probe packet received at each segment leader, and processing the information to determine an interconnection of switches in the network.

24. The method of claim 22 wherein a plurality of switch leaders are selected corresponding to a plurality of switches, and further comprising, selecting a first switch leader from among the switch leaders, selecting a second switch leader from among the switch leaders, the second switch leader being different from the first switch leader, and grouping remaining switch leaders into at least one equivalence class, in which any switch leaders that exchange packets without those packets traveling through a switch in the network on the path from the first switch leader to the second switch leader are grouped in the same equivalence class.

25. The method of claim 24 wherein at least a first and second equivalence class are present, and further comprising, selecting a first class leader from the first equivalence class and a second class leader from the second equivalence class, sending a training packet corresponding to a training address from the first class leader to the first switch leader from the training address, sending a training packet from the second switch leader corresponding to the training address to the second class leader, sending a probe packet from the first switch leader to the training address, and ordering the class based on where the probe packets are received.

26. The method of claim 25 wherein the ordering is not determined, and further comprising, sending a training packet corresponding to a training address from the second class leader to the second switch leader from the training address, sending a training packet from the first switch leader corresponding to the training address to the first class leader, and sending a probe packet from the second switch leader to the training address, and ordering the class based on where the probe packets are received.

27. A computer-readable medium encoded with computer-executable instructions for performing the method of claim 10.

28. In a computer network, a system for determining the topology of the network, comprising:

a master computer, the master computer directing other computers in the network to send training packets, to send probe packets, and to report which probe packets were received at the other computers, wherein the master computers optimizes the directions to the other computers by performing operations including, remembering the topology of the network from one instance of discovering network topology to the next, and, when there is a freedom in the order of giving directions to the other computers, selecting an order which would be most efficient if the network topology were alike to the previous instance of discovering network topology;

a collector for collecting information from the other computers including data corresponding to each probe packet received at each other computer; and

an analysis mechanism, the analysis mechanism determining the topology of the network based on the information from the other computers.

29. The system of claim 28 wherein the collector constructs a sees matrix indicative of which computers see which other computers in the network, and the analysis mechanism processes the sees matrix.

30. The system of claim 28 wherein some of the computers in the network may be directed to send probe packets but may not be directed to send training packets or to report which probe packets were received at the computer.

31. The system of claim 30 wherein a direction of those computers comprises the use of remote transmission elicitation.

32. The system of claim 28 wherein some of the computers in the network may not be directed to send training packets, but may be directed to send probe packets or to report which probe packets were received at the computer.

33. The system of claim 28, wherein the master computer on the wireless side of a wireless half bridge instructs another computer on the wired side of a wireless half-bridge, comprising:

the master computer places an additional copy of the address of the computer to be instructed inside the packet containing the instruction

the master computer broadcasts the instruction packet to the entire network

other computers do not obey the instructions in broadcast instruction packets unless a copy of their own address is found within the instruction packet.

34. The system of claim 28 wherein the other computer on the wireless side of a wireless half bridge responds to an instruction from the master computer on the wired side of a wireless half-bridge, wherein the other computer places an additional copy of the address of the master computer inside the packet containing the response, the other computer broadcasts the instruction packet to the entire network, and the other computers ignore responses in broadcast response packets unless they are the master computer whose address is found within the response packet.

35. In a computer network, a method for discovering information about a topology of the network, comprising:

determining the segments in the network which contain at least one computer;

training a portion of the network with at least one training message sent from one or more of the computers in the network so that the switches in the portion of the network know at least some training address, the training address comprising an address that is known by the switch, such that the switch can use the training address as a base in determining which other computers have access to the training address;

probing with at least one probe message sent from one or more of the computers in the network;

determining which computer in the network sees which of the probe message or messages

determining which switches and segments are found together in an island, including;

putting a first segment in a first proposed island;

for each other segment;

determining whether that segment shares a switch with any segment already in a proposed island, and

a) if so, merging the segment into that proposed island, and

b) if not, creating a new proposed island, and

wherein when each segment has been put in a proposed island, maintaining information such that each of the proposed island is an actual island in the network.

36. The method of claim 35 wherein determining the segments in the network comprises detecting shallow segments.

37. The method of claim 36 wherein determining the segments in the network further comprises detecting any shallow intermediate segments.

38. The method of claim 35 wherein training a portion of the network comprises applying three sweep detection to discover which segments are attached to a common switch.

39. The method of claim 35 further comprising, determining whether there is more than one island, and if so, using an island edge detection mechanism to determine any switch at the end of an island and any gap between the islands.

40. The method of claim 39 further comprising, determining whether there is any gaps larger than two islands, and if so, for each such gap, applying at least one gap splitting method to break the gap into smaller gaps.

41. The method of claim 39 further comprising, discovering interconnections between each of the islands.

42. The method of claim 35 further comprising separating computers in the network into a fixed set and a wireless set containing fixed computers and wireless computers, respectively, and wherein the segments are determined from the fixed set.

43. The method of claim 42 further comprising separating the network into regions based on detecting wireless half-bridges.

44. The method of claim 35 further comprising, building a graph to represent the topology of the discovered network.

45. A computer-readable medium encoded with computer-executable instructions for performing the method of claim 35.

46. In a computer network, a method comprising:

discovering information about a topology of the network, including sending and receiving training packets and probe packets using addresses distinct from those belonging to any computer on the network, where the addresses used in the packets are fresh addresses which have never been used on the network before and are not known to the network because they have not been used on the network recently;

reporting which probe packets were received at the computers in the computer network, including remembering the topology of the network from one instance of discovering network topology to the next and selecting an order which would be most efficient if the network topology were alike to the previous instance of discovering network topology; and

choosing addresses from a range apportioned into generations, using the addresses from a portion of the generation which is least recently used, and remembering the generation which is least recently used.

47. The method of claim 46, wherein the addresses used in the packets are distinct from those belonging to any computer by being selected from a range allocated by an address allocating authority for the type of computer network, and not used for constructing any network interface for any computer.

48. A computer-readable medium encoded with computer-executable instructions for performing the method of claim 46.

49. In a computer network, a method comprising:

discovering information about a topology of the network, including training a portion of the network with at least one training message sent from one or more of the computers in the network so that the switches in the portion of the network know at least some training address, the training address comprising an address that is known by the switch, such that the switch can use the training address as a base in determining which other computers have access to the training address;

probing with at least one probe message sent from one or more of the computer in the network;

determining which computer in the network sees which of the probe message or messages;

detecting at least one segment in the network, the detecting including placing a plurality of computers in the network into a promiscuous mode, selecting a master computer, and, at each computer other than the master computer;

a) sending a packet to the master computer;

b) recording any packet observed from another computer sent to the master computer; and

c) reporting the source address of each packet observed; and

collecting the source addresses of the packets observed in order to determine which computers see which other computer or computers in the network.

50. The method of claim 49 further comprising using the discovered topology to evaluate the network.

51. The method of claim 50 wherein using the discovered topology for evaluating the network comprises using the discovered topology for diagnostics.

52. The method of claim 50 wherein using the discovered topology for evaluating the network comprises using the discovered topology for quality of service.

53. The method of claim 50 wherein using the discovered topology for evaluating the network comprises using the discovered topology for performance recommendations.

54. The method of claim 50 wherein using the discovered topology for evaluating the network comprises using the discovered topology for product recommendations.

55. A computer-readable medium encoded with computer-executable instructions for performing the method of claim 49.

56. In a computer network, a method for discovering information about a topology of the network, comprising:

training a switch with a training message sent from a first computer so that the switch knows a training address, the training address comprising an address that is known by the switch, such that the switch can use the training address as a base in determining which other computers have access to the training address;

probing with a probe message sent from a second computer to the training address;

determining which other computer or computers in the network see the probe message;

detecting at least one segment in the network;

determining a segment leader for each segment;

determining whether there is an intermediate segment between switches, including, selecting a segment leader as a distinguished computer that is of a different segment than the master computer, at each segment leader other than the distinguished computer;

a) sending a packet to distinguished computer;

b) recording any packet observed from another segment leader sent to the distinguished computer; and

c) reporting the source address of each packet observed;

collecting the source addresses of the packets observed; and

determining whether the master computer'"'"'s segment is asymmetric, and if so, determining that the master computer'"'"'s segment is an intermediate segment.

57. The method of claim 56, wherein detecting the at least one segment further comprises, constructing a matrix indicative of whether each computer sees each other computer in the network, and analyzing the matrix, a given computer being in a segment with another computer when the given computer can see the other computer and the other computer can see the given computer.

58. The method of claim 56, further comprising sending a packet from the master computer to an address distinct from those belonging to any computer on the network, such that any computer on the segment of the master computer will see the packet to the distinct address.

59. The method of claim 56, further comprising sending a packet from the master computer such that any computer on the segment of the master computer will see the packet to the distinct address, and no computer on any other segment will see the packet.

60. The method of claim 59, wherein sending the packet from the master computer comprises the master computer first sending a packet from a distinct address to another address, and further comprising, sending a packet from the master computer'"'"'s address to the distinct address.

61. The method of claim 56, further comprising determining a segment leader for each segment, and wherein training the switch with the training message sent from the first computer comprises training the switch with the training message sent from a first segment leader, and wherein probing with the probe message sent from the second computer comprises probing the switch with the probe message sent from a second segment leader.

62. The method of claim 56, wherein training a switch comprises, for a first segment leader of a first segment, training any switches attached to the first segment by sending a training message from a training address, and further comprising, for a second segment leader of a second segment, training any switches attached to the second segment by sending a message from the training address.

63. The method of claim 62, wherein probing with a probe message comprises sending a packet from the first segment leader to the training address to determine how each switch attached to the first segment was trained.

64. A computer-readable medium encoded with computer-executable instructions for performing the method of claim 56.

65. In a computer network, a system for determining the topology of the network, comprising:

a master computer, the master computer directing other computers in the network to send training packets, to send probe packets, and to report which probe packets were received at the other computers, wherein the master computer discovers the other computers on the network by sending at least one packet asking other computers to identify themselves to the master, and the other computers sending at least one packet identifying themselves to the master computer and wherein only one master is allowed to be active at a time on the network, wherein one master computer receives a packet from another master computer asking other computers to identify themselves and the one master computer responds with a packet indicating that there is already a master computer present, and wherein any other computer already identified with another master computer may send a packet indicating that it is already identified to another master computer;

a collector for collecting information from the other computers including data corresponding to each probe packet received at each other computer;

an analysis mechanism, the analysis mechanism determining the topology of the network based on the information from the other computers.

66. The system of claim 65 wherein the packet sent by the master computer may contain the identification or others computers which the master computer has already identified, and the other computers need not identify themselves again if they have already been identified.

67. The system of claim 65, wherein the other computers spread their packets over an interval of time in order to avoid overwhelming the master computer, wherein each computer selects a time from some interval, and each computer sends its response at its selected time.

68. The system of claim 65, wherein the collector constructs a sees matrix indicative of which computers see which other computers in the network, and the analysis mechanism processes the sees matrix.

69. The system of claim 65, wherein some of the computers in the network may be directed to send probe packets but may not be directed to send training packets or to report which probe packets were received at the computer.

70. The system of claim 69, wherein a direction of those computers comprises the use of remote transmission elicitation.

71. The system of claim 65, wherein some of the computers in the network are not directed to send training packets, but are directed to send probe packets or to report which probe packets were received at the computer.

72. The system of claim 65, wherein the master computer on the wireless side of a wireless half bridge instructs another computer on the wired side of a wireless half-bridge, comprising:

the master computer placing an additional copy of the address of the computer to be instructed inside the packet containing the instruction;

the master computer broadcasting the instruction packet to the entire network; and

other computers failing to obey the instructions in broadcast instruction packets unless a copy of their own address is found within the instruction packet.

73. The system of claim 65, wherein the other computer on the wireless side of a wireless half bridge responds to an instruction from the master computer on the wired side of a wireless half-bridge, wherein the other computer places an additional copy of the address of the master computer inside the packet containing the response, the other computer broadcasts the instruction packet to the entire network, and the other computers ignore responses in broadcast response packets unless they are the master computer whose address is found within the response packet.