Path recovery on failure in load balancing switch protocols

• US 20030016624A1
• Filed: 08/14/2002
• Published: 01/23/2003
• Est. Priority Date: 05/04/1998
• Status: Active Grant

• 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.
• Granted Patent: US 7,430,164 B2
• Time in Patent Office: Days
• US Class Current: 370/217
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/247 using M:N active or standby paths
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/10 of different types
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers

Abstract

A method for managing multiple active paths among a plurality of network switches to identify and select an alternate path in response to failure of a path from a switch to a device. Load balancing protocols of the present invention enable the simultaneous use of multiple paths between network devices through a mesh of compliant network switches. When a port of a network switch fails (or the link connected to a port fails), a switch in accordance with the present invention selects an alternate port which may be used for forwarding packets to devices normally reached through the failed port. Networks switches operable in accordance with the structures and protocols of the present invention exchange messages to identify potential alternate paths. A potential alternate path is used to send a query message to a neighboring network switch to determine if a path to the identified devices is available through the neighboring network switch. Such query messages are propagated through all intermediate network switches between the switch sensing the failed port up to the identified network device. Acknowledgment messages are returned to verify potential availability of an alternate path. Where an intermediate network switch determines that the complete path is not available through it to the identified device, or where a potentially better path exists, a regenerated query message so indicating is returned along the path that initiated the query message.

Claims

1. A method operable within a network switch for managing alternate paths comprising the steps of:

determining that a port of said network switch is unusable;

identifying at least one MAC address which relies on said port for forwarding of packets through said network switch to at least one device corresponding to said at least one MAC address;

selecting another port of said network switch usable for forwarding packets to said at least one device; and

redirecting packets addressed to said at least one MAC address through said another port to said at least one device.

2. The method of claim 1 wherein the step of selecting includes the steps of:

sending a query message out a potential alternate port of said network switch requesting acknowledgment of usability of said potential alternate port for forwarding packets addressed to said at least one MAC address;

receiving an acknowledgment message on said potential alternate port indicating that said potential alternate port may be used for forwarding of packets addressed to said at least one MAC address; and

assigning said potential alternate port as said another port for forwarding of packets addressed to said at least one MAC address in response to receipt of said acknowledgment message.

3. The method of claim 2 wherein the step of selecting further includes the step of:

receiving a negative acknowledgment message indicating that said potential alternate port may not be used for forwarding of said packets; and

repeating the step of sending a query message for each other potential alternate port of said network switch in response to receipt of said negative acknowledgment message.

4. The method of claim 3 wherein the step of assigning includes the step of:

updating addressing tables in said network switch to indicate the use of said potential alternate port as said another port for forwarding of packets addressed to said MAC address.

5. The method of claim 3

wherein said at least one MAC address is a plurality of MAC addresses,

wherein said query message requests acknowledgment of usability of said potential alternate port for forwarding of said packets for all of said plurality of MAC addresses,

wherein said acknowledgment message includes indicia of which of said plurality of MAC addresses may have packets forwarded through said potential alternate port,

wherein said negative acknowledgment message includes indicia of which of said plurality of MAC addresses may not have packets forwarded through said potential alternate port, and

wherein the step of repeating repeats the step of sending for those MAC addresses indicated in said negative acknowledgment message.

6. The method of claim 5 wherein the step of assigning includes the step of:

updating addressing tables in said network switch to indicate the use of said potential alternate port as said another port for forwarding of packets addressed to MAC addresses indicated in said acknowledgment message.

7. The method of claim 1 wherein the step of selecting includes the step of:

selecting among a plurality of potential alternate ports in a sequence according to a port load factor value associated with each port of said plurality of potential alternate ports.

8. A method operable within a plurality of network switches for managing alternate path selection comprising the steps of:

determining, in a first network switch of said plurality of network switches, that a port of said first network switch is unusable;

identifying at least one MAC address which relies on said port for forwarding of packets through said first network switch to at least one device corresponding to said at least one MAC address;

exchanging messages with at least one intermediate network switch of said plurality of network switches to identify another port of said first network switch usable for forwarding packets to said at least one device; and

redirecting packets addressed to said at least one MAC address through said another port to said at least one device.

9. The method of claim 8 wherein the step of exchanging messages includes the steps of:

propagating a query message out a potential alternate port of said first network switch to said at least one intermediate network switch requesting acknowledgment of usability of said potential alternate port for forwarding packets addressed to said at least one MAC address;

receiving an acknowledgment message from said at least one intermediate network switch on said another port of said first network switch indicating that said potential alternate port may be used for forwarding of packets addressed to said at least one MAC address; and

assigning said potential alternate port as said another port for forwarding of packets addressed to said at least one MAC address in response to receipt of said acknowledgment message.

10. The method of claim 9 wherein the step of propagating a query message includes the steps of:

receiving said query message on a port of said at least one intermediate network switch;

verifying, within said at least one intermediate network switch in response to receipt of said query message, that another path to said at least one MAC address exists through another port of said at least one intermediate network switch other than said port of said at least one intermediate network switch on which said query message was received; and

sending said acknowledgment message back to said first network switch indicating that said potential alternate port of said first network switch may be used to forward said packets.

11. The method of claim 10 further comprising the steps of:

determining, within said at least one intermediate network switch, that said another path is indirectly connected to said at least one device through said another port and another intermediate switch of said at least one intermediate network switch; and

propagating said query message from said at least one intermediate network switch to said another intermediate network switch.

12. The method of claim 11 further comprising the step of:

determining that no port of one of said at least one intermediate network switch is usable for forwarding of said packets addressed to said at least one MAC address;

creating a second query message from said query message; and

propagating said second query message back on the path from which said query message was received.

13. The method of claim 12 further comprising the step of:

repeating the step of exchanging messages in response to receipt of second query message in said first network switches.

15. The system of claim 14 wherein the method step of selecting includes the steps of:

sending a query message out a potential alternate port of said network switch requesting acknowledgment of usability of said potential alternate port for forwarding packets addressed to said at least one MAC address;

receiving an acknowledgment message on said another port indicating that said potential alternate port may be used for forwarding of packets addressed to said at least one MAC address; and

assigning said potential alternate port as said another port for forwarding of packets addressed to said at least one MAC address in response to receipt of said acknowledgment message.

16. The system of claim 15 wherein the method step of selecting further includes the step of:

receiving a negative acknowledgment message indicating that said potential alternate port may not be used for forwarding of said packets; and

repeating the step of sending a query message for each other potential alternate port of said network switch in response to receipt of said negative acknowledgment message.

17. The system of claim 16 wherein the method step of assigning includes the step of:

updating addressing tables in said network switch to indicate the use of said potential alternate port as said another port for forwarding of packets addressed to said MAC address.

18. The system of claim 16

wherein said at least one MAC address is a plurality of MAC addresses,

wherein said query message requests acknowledgment of usability of said potential alternate port for forwarding of said packets for all of said plurality of MAC addresses,

wherein said acknowledgment message includes indicia of which of said plurality of MAC addresses may have packets forwarded through said potential alternate port,

wherein said negative acknowledgment message includes indicia of which of said plurality of MAC addresses may not have packets forwarded through said potential alternate port, and

wherein the method step of repeating repeats the step of sending for those MAC addresses indicated in said negative acknowledgment message.

19. The system of claim 18 wherein the method step of assigning includes the step of:

updating addressing tables in said network switch to indicate the use of said potential alternate port as said another port for forwarding of packets addressed to MAC addresses indicated in said acknowledgment message.

20. The system of claim 14 wherein the method step of selecting includes the step of:

selecting among a plurality of potential alternate ports in a sequence according to a port load factor value associated with each port of said plurality of potential alternate ports.

14. A network switch including a computer readable storage medium tangibly embodying a method operable within said network switch for managing alternate paths comprising the steps of:

determining that a port of said network switch is unusable;

identifying at least one MAC address which relies on said port for forwarding of packets through said network switch to at least one device corresponding to said at least one MAC address;

selecting another port of said network switch usable for forwarding packets to said at least one device; and

redirecting packets addressed to said at least one MAC address through said another port to said at least one device.

21. A system having a plurality of network switches each including a computer readable storage medium tangibly embodying a method operable within said plurality of network switches for managing alternate path selection comprising the steps of:

determining, in a first network switch of said plurality of network switches, that a port of said first network switch is unusable;

identifying at least one MAC address which relies on said port for forwarding of packets through said first network switch to at least one device corresponding to said at least one MAC address;

exchanging messages with at least one intermediate network switch of said plurality of network switches to identify another port of said first network switch usable for forwarding packets to said at least one device; and

redirecting packets addressed to said at least one MAC address through said another port to said at least one device.

22. The system of claim 21 wherein the method step of exchanging messages includes the steps of:

propagating a query message out a potential alternate port of said first network switch to said at least one intermediate network switch requesting acknowledgment of usability of said potential alternate port for forwarding packets addressed to said at least one MAC address;

receiving an acknowledgment message from said at least one intermediate network switch on said another port of said first network switch indicating that said potential alternate port may be used for forwarding of packets addressed to said at least one MAC address; and

assigning said potential alternate port as said another port for forwarding of packets addressed to said at least one MAC address in response to receipt of said acknowledgment message.

23. The system of claim 22 wherein the method step of propagating a query message includes the steps of:

receiving said query message on a port of said at least one intermediate network switch;

verifying, within said at least one intermediate network switch in response to receipt of said query message, that another path to said at least one MAC address exists through another port of said at least one intermediate network switch other than said port of said at least one intermediate network switch on which said query message was received; and

sending said acknowledgment message back to said first network switch indicating that said potential alternate port of said first network switch may be used to forward said packets.

24. The system of claim 23 wherein the method further comprises the steps of:

determining, within said at least one intermediate network switch, that said another path is indirectly connected to said at least one device through said another port and another intermediate switch of said at least one intermediate network switch; and

propagating said query message from said at least one intermediate network switch to said another intermediate network switch.

25. The system of claim 24 wherein the method further comprises the step of:

determining that no port of one of said at least one intermediate network switch is usable for forwarding of said packets addressed to said at least one MAC address;

creating a regenerated query message from said query message with indicia that no path is available through said one of said at least one intermediate network switch to forward said packets addressed to said at least one MAC address; and

propagating the regenerated query message back on the path from which said query message was received.

26. The system of claim 25 wherein the method further comprises the step of:

repeating the step of exchanging messages in response to receipt of the regenerated query message in said first network switches.