System and method for network topology discovery

• US 20050169193A1
• Filed: 01/29/2004
• Published: 08/04/2005
• 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
• Granted Patent: US 7,567,523 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• 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;

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

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

2. The method of claim 1 further comprising, detecting at least one segment in the network.

3. The method of claim 2 wherein detecting the at least one segment in the network comprises, 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;

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.

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

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

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

7. The method of claim 6 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.

8. The method of claim 2 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.

9. The method of claim 2 further comprising, determining a segment leader for each segment.

10. The method of claim 9 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 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.

11. The method of claim 2 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.

12. The method of claim 11 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.

13. A computer-readable medium having computer-executable instructions for performing the method of claim 1.

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

15. The method of claim 14 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.

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

17. The method of claim 14 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.

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

19. The method of claim 18 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.

20. The method of claim 18 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.

21. The method of claim 20 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.

22. The method of claim 18 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.

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

24. The method of claim 23 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.

25. The method of claim 18 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.

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

27. The method of claim 26 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.

28. The method of claim 26 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.

29. The method of claim 28 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.

30. The method of claim 29 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.

31. A computer-readable medium having computer-executable instructions for performing the method of claim 14.

32. 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;

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.

33. The system of claim 32 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.

34. The system of claim 32 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.

35. The system of claim 32 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.

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

37. The system of claim 32 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.

38. The system of claim 32 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.

39. The system of claim 38 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.

40. The system of claim 38, 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.

41. The system of claim 38 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.

42. The system of claim 32, 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.

43. The system of claim 32 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.

44. A computer readable medium having computer-executable components for implementing the system of claim 32.

45. 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;

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

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

46. The method of claim 45 wherein determining the segments in the network comprises detecting shallow segments.

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

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

49. The method of claim 45 further comprising 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.

50. The method of claim 49 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.

51. The method of claim 50 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.

52. The method of claim 49 further comprising, discovering interconnections between each of the islands.

53. The method of claim 45 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.

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

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

56. A computer-readable medium having computer-executable instructions for performing the method of claim 45.

57. In a computer network, a method comprising, discovering information about a topology of the network, including sending and receiving packets using addresses distinct from those belonging to any computer on the network.

58. The method of claim 57, 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.

59. The method of claim 57, where the addresses used in the packets are fresh addresses which have never been used on the network before.

60. The method of claim 59, where the addresses used in the packets are addresses which are not known to the network because they have not been used on the network recently.

61. The method of claim 60, further comprising, 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.

62. A computer-readable medium having computer-executable instructions for performing the method of claim 57.

63. In a computer system, a method for remembering addresses, comprising,

storing a single value corresponding to the least recently used address allocation generation;

selecting a set of values that form a cyclic group, with a mathematical successor function on values;

remembering the most recently used value; and

generating the least recently used value by the application of the successor function to the most recently used value.

64. The method of claim 63, where the most recently used value is remembered by storing the most recently used value in a memory.

65. The method of claim 63 wherein the method is implemented in a system for remembering the most recently used value, the system comprising each computer in the network storing the most recently used value in volatile and/or non-volatile memory, a master computer, the master computer querying the memory of each other computer, deciding amongst the values of each computer, and selecting the least recently used value for the network, and each computer updating its most recently used value when the master begins to use it.

66. A computer readable medium having computer-executable instructions for performing the method of claim 63.

67. In a computer network, a system comprising:

a mechanism for determining whether a path from a first computer to a second computer passes from the wired side of a wireless half-bridge to the wireless side of a wireless half-bridge, the mechanism comprising;

at the first computer, means for sending a packet to the second computer which contains an additional copy of the source address of the first computer, and

at the second computer, means for testing to see whether the source address of the received packet is the same as the additional copy of the original source address of the first computer, or if the source address has been changed.

68. In a computer network, a method, comprising:

determining whether a path from a first computer attached to a wired network to a second computer passes from the wireless side of a wireless half-bridge to the wired side of a wireless half-bridge;

at the first computer sending a packet to an address not in use on the network;

at the second computer checking to see whether the packet sent by the first computer is received.

69. A computer-readable medium having computer-executable instructions for performing the method of claim 68.

70. 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, probing with at least one probe message sent from one or more of the computer in the network, and determining which computer in the network sees which of the probe message or messages.

71. The method of claim 70 further comprising using the discovered topology to evaluate the network.

72. The method of claim 71 wherein using the discovered topology for evaluating the network comprises using the discovered topology for diagnostics.

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

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

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

76. A computer-readable medium having computer-executable instructions for performing the method of claim 70.

77. In a computer system, a method for determining if two paths in the network touch or cross comprising:

selecting a pair of computers representing the first path;

selecting a pair of computers representing the second path;

sending a training packet from one member of the first pair to the other member of the first pair;

sending a training packet from one member of the second pair to the other member of the second pair;

sending a probe packet from the member of the first pair which did not send the training packet to the address used in the training packets;

and determining whether the probe packet is received by the first training computer of the first pair, the training computer of the second pair, or both.

78. The method of claim 77, where the computers of the first pair are the same computer, and the first training packet is sent on the local segment only.

79. The method of claim 77, where the computers of the second pair are the same computer, and the second training packet is sent on the local segment only.

80. The method of claim 77, further comprising where the method consults information already known about other paths that cross or touch in the computer network in order to reduce the number of packets that must be sent.

81. A computer-readable medium having computer-executable instructions for performing the method of claim 77.