SYSTEM AND METHOD FOR NETWORK TOPOLOGY DISCOVERY

• US 20090285127A1
• Filed: 06/04/2009
• Published: 11/19/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
• Granted Patent: US 8,724,512 B2
• Time in Patent Office: Days
• 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 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.

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

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

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

5. A computer system comprising the following:

one or more processors;

system memory;

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

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

a remembering component configured to remember the most recently used value; and

a generating component configured to generate the least recently used value by the application of the successor function to the most recently used value.

6. The computer system of claim 5, where the most recently used value is remembered by storing the most recently used value in a memory.

7. The computer system of claim 5, wherein the remembering component remembers the most recently used value, and wherein each computer in the network stores the most recently used value in volatile and/or non-volatile memory.

8. The computer system of claim 7, further comprising a master computer, the master computer being configured to query the memory of each other computer, decide amongst the values of each computer, and select the least recently used value for the network, wherein each computer updates its most recently used value when the master computer begins to use it.

9. A computer system comprising the following:

one or more processors;

system memory;

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

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

a remembering means for remembering the most recently used value; and

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

10. The computer system of claim 9, where the most recently used value is remembered by storing the most recently used value in a memory.

11. The computer system of claim 9, wherein the remembering means remembers the most recently used value, and wherein each computer in the network stores the most recently used value in volatile and/or non-volatile memory.

12. The computer system of claim 9, further comprising a master computing means, the master computing means being configured to query the memory of each other computer, decide amongst the values of each computer, and select the least recently used value for the network, wherein each computer updates its most recently used value when the master computing means begins to use it.