Spanning tree recovery in computer networks

• US 6,628,661 B1
• Filed: 07/22/1999
• Issued: 09/30/2003
• Est. Priority Date: 08/27/1998
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Tondering, Claus, Goldman, Tomasz J., Dyrga, Ryszard W.
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): NGUYEN, BRIAN D
• Application Number:
  US09/359,199
• Time in Patent Office: 1,531 Days
• Field of Search: 370/408, 370/216, 370/217, 370/256, 370/255, 370/218, 370/409, 370/400, 370/401, 370/225, 370/229, 370/230, 370/242, 370/389, 370/390, 370/432, 709/221, 709/252, 709/239, 709/223, 709/224
• US Class Current: 370/408
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

In a spanning tree-based computer network having a plurality of switches, a spanning tree can be generated and/or recovered by identifying a network core, determining a distance to the network core for each switch in the network, and generating and/or recovering a spanning tree for the network based on the switches'"'"' relative distances to the network core.

Claims

1. A method performed in a spanning tree-based computer network comprising a plurality of switches, the method comprising:

determining a distance to a network core for each switch in the network; and

managing a spanning tree for the network based on the switches'"'"' relative distances to the network core, wherein the network core represents a high bandwidth portion of the network and comprises multiple core switches, each of the core switches having a distance to network core of zero, and said managing the spanning tree for the network based on the switches'"'"' relative distances to the network core comprises;

constraining an initial formation of the spanning tree such that the spanning tree is centered at the network core, and

after the spanning tree is formed, periodically propagating network core distance information downstream from the network core to downstream switches and updating the downstream switches with the network core distance information.

2. The method of claim 1 in which constraining the initial formation of the spanning tree comprises choosing one of the core switches as a spanning tree root.

3. The method of claim 1 in which periodically propagating the network core distance information downstream comprises broadcasting frames periodically, each frame identifying the broadcasting switch and a distance to network core value, and updating the downstream switches with the network core information comprises storing at each of the downstream switches information identifying one or more switch ports that are operational and one or more directly-connected upstream switches.

4. The method of claim 1 in which managing the spanning tree further comprises recovering the spanning tree in response to a communication failure in the computer network based on the periodically propagated network core distance information.

5. The method of claim 4 in which recovery of the spanning tree comprises reconfiguring a port in a first switch to communicate with another switch closer to the network core.

6. The method of claim 5 in which reconfiguration of the switch'"'"'s port comprises changing the port from blocking to forwarding.

7. The method of claim 4 in which recovery of the spanning tree comprises:

determining whether a first switch has an operational port for communicating with another switch closer to the network core;

if an operational port is available, reconfiguring the port to communicate with the other switch closer; and

if no operational port is available, executing a spanning tree generation algorithm.

8. An article comprising a machine-readable medium embodying information indicative of instructions that when performed by one or more machines result in operations comprising:

determining a distance to a network core for each of a plurality of switches of a spanning tree-based machine network; and

managing a spanning tree for the network based on the switches'"'"' relative distances to the network core, wherein the network core represents a high bandwidth portion of the network and comprises multiple core switches, each of the core switches having a distance to network core of zero, and said managing the spanning tree for the network based on the switches'"'"' relative distances to the network core comprises;

constraining an initial formation of the spanning tree such that the spanning tree is centered at the network core, and

after the spanning tree is formed, periodically propagating network core distance information downstream from the network core to downstream switches and updating the downstream switches with the network core distance information.

9. The article of claim 8, wherein constraining the initial formation of the spanning tree comprises choosing one of the core switches as a spanning tree root.

10. The article of claim 8, wherein periodically propagating the network core distance information downstream comprises broadcasting frames periodically, each frame identifying the broadcasting switch and a distance to network core value, and updating the downstream switches with the network core information comprises storing at each of the downstream switches information identifying one or more switch ports that are operational and one or more directly-connected upstream switches.

11. The article of claim 8, wherein managing the spanning tree further comprises recovering the spanning tree in response to a communication failure in the machine network based on the periodically propagated network core distance information.

12. The article of claim 11, wherein recovery of the spanning tree comprises reconfiguring a port in a first switch to communicate with another switch closer to the network core.

13. The article of claim 12, wherein reconfiguration of the switch'"'"'s port comprises changing the port from blocking to forwarding.

14. The article of claim 11, wherein recovery of the spanning tree comprises:

determining whether a first switch has an operational port for communicating with another switch closer to the network core;

if an operational port is available, reconfiguring the port to communicate with the other switch closer; and

if no operational port is available, executing a spanning tree generation algorithm.