Broadcast tree determination in load balancing switch protocols

• US 6,865,160 B1
• Filed: 01/11/1999
• Issued: 03/08/2005
• Est. Priority Date: 05/04/1998
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Bare, Ballard C.
• Primary Examiner(s): Duong, Frank
• Assistant Examiner(s): Harper, Kevin C.
• Application Number:
  US09/228,087
• Time in Patent Office: 2,248 Days
• Field of Search: 370254-256
• US Class Current: 370/256
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

A method for generating and maintaining a pruned broadcast tree for a network of switches operating multiple simultaneously active paths between devices with a load balancing family of protocols. The pruned broadcast tree is preferably generated as a by product of cost propagation aspects of the load balancing protocols exchanged among cooperating network switches. The load balance protocols operable within the network switches in association with the present invention permit multiple simultaneously active paths to be utilized among the network devices. The pruned broadcast tree is therefore used to reduce the latency of broadcast messages propagated within the network switches to reach all devices in the network. The broadcast tree defines a minimized set of devices to which a broadcast message need be forward to assure transmission to all network devices. The pruned broadcast tree, once established, is updated only in response to failure of a link and recovery of a failed link. A separate protocol of the present invention enables such pruned broadcast tree modifications and restoration.

Claims

1. A method operable within a network switch for managing a broadcast tree, said method comprising the steps of:

constructing a pruned broadcast tree by propagation of dynamic cost information packets from edge switches, wherein a dynamic cost information packet is sent by an edge switch and a receiving switch sends back a first acknowledgement packet to the edge switch in response to a first dynamic cost information packet, and wherein the first acknowledgement packet will have a set broadcast learn flag to inform the edge switch that broadcast packets will be transmitted from a particular port of the edge switch, where the particular port has received the first acknowledgement packet with the set broadcast learn flag, where the first acknowledgment packet is used to establish a broadcast path from the edge switch to the receiving switch;

wherein the first acknowledgement packet is used to establish the broadcast path in order to select the lowest latency path for the broadcast path and any subsequent acknowledgement packets are not used to establish the broadcast path;

wherein each dynamic cost information packet includes a cost information determined by a ratio of a port latency value and an available throughput of a port in the edge switch, where the port latency value is equal to a queue depth of data stored in at least one queue associated with the port divided by a data transfer speed associated with the port of the network switch; and

forwarding received broadcast messages to other network devices in accordance with said pruned broadcast tree.

2. The method of claim 1 wherein the step of constructing is responsive to exchange of load balancing information between said network switch and other cooperating network devices.

3. The method of claim 2 wherein the step of constructing includes the steps of:

receiving a packet on a port within said network switch wherein said packet includes indicia requesting that said pruned broadcast tree include said port for future broadcast messages to an edge switch associated with said port; and

adding said port to said pruned broadcast tree for broadcast of messages to said edge switch in response to receipt of a first said packet.

4. The method of claim 3 wherein the step of constructing further includes the steps of:

receiving a packet on a port within said network switch wherein said packet includes indicia requesting that said pruned broadcast tree exclude said port for future broadcast messages to an edge switch associated with said port; and

deleting said port from said pruned broadcast tree for broadcast of messages to said edge switch in response to receipt of a first said packet.

5. The method of claim 3 wherein said packet is a cost acknowledgement packet.

6. The method of claim 1 wherein said network switch is coupled to at least one cooperating network switch in a common load balance domain,

wherein the step of forwarding includes the steps of:

receiving a broadcast message of said broadcast messages on a port of said network switch in said pruned broadcast tree; and

transmitting said broadcast message out all other ports of said network switch which are said pruned broadcast tree.

7. The method of claim 6 wherein the step of forwarding further includes:

transmitting said broadcast message out other ports of said network switch connected to devices not in said common load balance domain.

8. The method of claim 1 further comprising the steps of:

sensing failure of a path associated with a port of said network switch on said pruned tree; and

updating said pruned broadcast tree in response to sensing said failure.

9. The method of claim 8 wherein the step of updating includes the step of:

determining a second port of said network switch which may be used for forwarding of broadcast messages; and

sending a packet out said second port indicative of devices to which broadcast messages may be forwarded via said second port.

10. The method of claim 9 further comprising the step of:

determining that other network switches depended upon said path of said network switch for broadcast to other devices; and

sending a packet from said network switch to said other switches indicative of said failure of said path.

11. The method of claim 1, wherein the dynamic cost information packet includes cost that is updated periodically.

12. The method of claim 1, wherein the edge switch can receive a second acknowledgment packet subsequently to receiving the first acknowledgment packet, and wherein the second acknowledgement packet will not include a set broadcast learn flag.

13. The method of claim 1, further comprising:

in response to a link failure, constructing a new pruned broadcast tree, including receiving a new dynamic cost information packet, removing all broadcast paths to other switches, and sending a new acknowledgement packet in response to the new dynamic cost information packet in order to establish a new broadcast path.

14. The method of claim 1, further comprising:

after receiving, by the edge switch, the first acknowledgement packet with the broadcast learn flag that is set, placing the particular port, for a MAC (Media Access) address of the edge switch, in the pruned broadcast tree.

15. A method operable within a network switch for managing a broadcast tree, said method comprising the steps of:

constructing a pruned broadcast tree by propagation of dynamic cost information packets from edge switches, wherein a dynamic cost information packet is sent by an edge switch and a receiving switch sends back a first acknowledgement packet to the edge switch in response to a first dynamic cost information packet, and wherein the first acknowledgement packet will have a set broadcast learn flag to inform the edge switch that broadcast packets will be transmitted from a particular port of the edge switch, where the particular port has received the first acknowledgement packet with the set broadcast learn flag, where the first acknowledgment packet is used to establish a broadcast path from the edge switch to the receiving switch; and

wherein each dynamic cost information packet includes a cost information determined by a ratio of a port latency value and an available throughput of a port in the edge switch, where the port latency value is equal to a queue depth of data stored in at least one queue associated with the port divided by a data transfer speed associated with the port of the network switch.

16. The method of claim 15, further comprising:

forwarding received broadcast messages to other network devices in accordance with said pruned broadcast tree.

17. The method of claim 15 wherein the step of constructing is responsive to exchange of load balancing information between said network switch and other cooperating network devices.

18. The method of claim 17 wherein the step of constructing includes the steps of:

receiving a packet on a port within said network switch wherein said packet includes indicia requesting that said pruned broadcast tree include said port for future broadcast messages to an edge switch associated with said port; and

adding said port to said pruned broadcast tree for broadcast of messages to said edge switch in response to receipt of a first said packet.

19. The method of claim 18 wherein the step of constructing further includes the steps of:

receiving a packet on a port within said network switch wherein said packet includes indicia requesting that said pruned broadcast tree exclude said port for future broadcast messages to an edge switch associated with said port; and

deleting said port from said pruned broadcast tree for broadcast of messages to said edge switch in response to receipt of a first said packet.