Ethernet topology change notification and nearest neighbor determination

• US 5,793,975 A
• Filed: 03/01/1996
• Issued: 08/11/1998
• Est. Priority Date: 03/01/1996
• Status: Expired due to Term

• Current Assignee: Avaya Holdings Ltd (Avaya Incorporated)
• Original Assignee: Bay Networks Group Inc. (Nortel Networks Corporation)
• Inventors: Zeldin, Paul
• Primary Examiner(s): Geckil, Mehmet B.
• Application Number:
  US08/609,281
• Time in Patent Office: 893 Days
• Field of Search: 395/200.1, 395/200.11, 395/200.53, 395/200.54, 395/200.72, 370/400, 370/401, 370/409, 370/351
• US Class Current: 709/224
• CPC Class Codes: H04L 12/413 with random access, e.g. carrier-sense multiple-access with collision detection [CSMA-CD]
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/26 using dedicated tools for LAN [Local Area Network] management
• CPC Class Codes: H04L 45/02 Topology update or discovery

Abstract

It is desirable to be able to automatically map the topology of a computer network. To automatically map the topology of a computer network, a new method is proposed. First, all the network management modules (NMMs) in the network start off broadcasting multicast packets informing other units of their presence. When a network management module detects that only a single unit is connected to a particular slot-port combination, then that network management module designates the single unit as being a downstream unit in a network topology table. After updating its network topology table, the network management module sends a quench packet to the single unit to silence the downstream unit. These steps are repeated for all occurrences of a single unit connected to a particular slot-port combination in that network. After this occurs, the very bottom layer of the network has been detected and it'"'"'s topology has been mapped. Since this bottom layer has been silenced by the quench packets, the bottom layer units will no longer be sending out the multicast packets. Thus, the next lowest layer can be detected by performing the same set of steps again. Specifically, any slot-pair combination that only has a single unit coupled to it is then marked as being a downstream and a quench message is sent to silence that unit. These steps are performed recursively until the entire network topology is detected.

Claims

1. A computer implemented method of automatically determining the topology of a computer network, said computer network comprising a plurality of network devices coupled together, each of said network devices having at least one port, said method comprising starting with a set of all network devices then repeating the following steps until all network devices downstream from other network devices are detected:

sending packets from each of said network devices in said set to at least all other network devices in said set;

determining an upper network device is directly above a lower network device in said set by detecting within each network device in said set if a packet from only one other network device was received on a particular port; and

in response to said determination, executing the steps of;

marking said lower network device as a downstream network device in a topology table within said upper network device determined to be directly above said lower network device; and

silencing said lower network device by removing said lower network device from said set.

2. The method as claimed in claim 1, said method further comprising the steps of:

determining when no downstream network devices remain; and

ceasing to send multicast packets when no downstream network devices remain.

3. The method as claimed in claim 1 wherein said step of silencing said lower network device comprises sending a quench packet to said downstream network device.

4. The method as claimed in claim 3 further comprising the step of:

receiving a quench packet within said lower network device from said upper network device, after receiving said quench packet from said upper network device performing the substeps of;

marking said upper network device as an upstream device in a topology table within said lower network device; and

ceasing to send packets from said lower network device to all other network devices in said network.

5. The method as claimed in claim 4 wherein said step of receiving a quench packet further comprises the substep of:

sending a response packet to said upstream network device.

6. The method as claimed in claim 1 wherein upstream devices continue to send quench packets to downstream network devices after said computer network topology has been mapped.

7. The method as claimed in claim 1 wherein if a network device sends a multicast packet to all other devices in the network after all network devices downstream from other network devices have been detected, said steps sending, determining, marking, and silencing, are performed again.

8. The method as claimed in claim 1 wherein said step of sending is implemented by a sending thread in said network device and said steps of detecting and handling are implemented by a receiving thread.

9. A network device for automatically determining the topology of a computer network, said computer network comprising a plurality of network devices coupled together, said network device comprising:

a processor;

a memory coupled to said processor;

at least one network port, said network port coupled to another network device;

a sending thread executing on said processor, said sending thread sending packets from said network device to other network devices in said network unless said network device has been silenced; and

a receiving thread executing on said processor, said receiving thread receiving packets from other network devices, if only one other network device is detected on a network port then marking said only one other network device as a downstream network device in a topology table in said network device and silencing said downstream network device.

10. The network device as claimed in claim 9 wherein said sending thread ceases sending packets to all other network devices when no downstream network devices remain.

11. The network device as claimed in claim 9 wherein said receiving thread silences said downstream network device by sending a quench packet to said downstream network device.

12. The network device as claimed in claim 9 wherein said receiving thread receives a quench packet from an upstream network device and in response to said quench packet marks said upstream network device in said topology table.

13. The network device as claimed in claim 12 wherein said sending thread stops sending packets to all other network devices after receiving thread receives a quench packet from said upstream network device.

14. The network device as claimed in claim 13 wherein said sending thread sends a response packet back to said upstream network device.

15. A computer network, said computer network comprising a plurality of network devices, each of said network devices having at least one network port coupled to another network device through a communication line, each of said network devices in said computer network starting in a set of all network devices then repeating the following steps until all network devices downstream from other network devices are detected:

sending packets from network devices in said set to at least all other network devices in said set;

determining an upper network device is directly above a lower network in said set by detecting if a packet from only one other network device was received on a particular network port; and

in response to said determination, executing the steps of;

marking said lower network device as a downstream network device in a topology table within said upper network device determined to be directly above said lower network device;

silencing said lower network device by removing said lower network device from said set.