Cost propagation switch protocols

• US 6,493,318 B1
• Filed: 01/11/1999
• Issued: 12/10/2002
• 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 Company (HP Inc.)
• Inventors: Bare, Ballard C.
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US09/228,890
• Time in Patent Office: 1,429 Days
• Field of Search: 370/248, 370/252, 370/256, 370/237, 370/238, 370/238.1, 370/242, 370/351, 370/389, 370/395, 370/32, 370/400-402
• US Class Current: 370/238
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/026 Details of "hello" or keep-alive messages
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's
• 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 switch to switch protocol for network load balancing which exchanges cost information among all switches in a load balance domain. As compared to prior techniques, the protocol of the present invention updates all switches in the load balance domain periodically. All switches in the load balance domain are thereby assured of having consistent cost information regarding all switches in the load balance domain. Further, the protocol of the present invention reduces the volume of cost messaging traffic as exemplified by techniques which generate updates to the information any time a cost parameter of a switch changed. The preferred embodiment of he protocol of the present invention exchanges messages describing the switch latency for each switch in the load balance domain. A bit mask field in the transmitted cost packets indicates which switches have already received the cost information. Receipt of the same packet a second time by a switch which already received the cost packet is indicative of a loop in the network and the propagation of that packet is terminated.

Claims

1. A method operable within a plurality of network switches for exchanging cost information among said plurality of network switches, said method comprising the steps of:

propagating cost information packets between a first switch of said plurality of network switches and other switches of said plurality of network switches so as to propagate cost information among said plurality of network switches; and

periodically repeating the propagation of said cost information packets based upon expiration of a pre-determined period of time so as to periodically update the cost information among said plurality of network switches instead of updating the cost information directly in response to any cost parameter change.

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

transmitting a cost information packet from a first switch of said plurality of network switches to other switches of said plurality of network switches;

receiving, in said first switch, a cost propagation packet transmitted from another switch of said plurality of network switches;

recording information derived from the received cost information packet in a memory associated with said first switch; and

forwarding the received cost propagation packet from said first switch to said other switches.

3. The method of claim 2 wherein said cost information packets include a hop count field and wherein the method further comprises the step of:

incrementing said hop count field in association with the step of transmitting and in association with the step of forwarding.

4. The method of claim 3 further comprising the steps of:

comparing the value of said hop count field to a predetermined maximum value; and

bypassing the step of forwarding in response to a determination that said value of said hop count field exceeds said predetermined maximum value.

5. The method of claim 2 further comprising the steps of:

awaiting receipt of a cost information response packet from each of said other switches in response to transmission of said cost information packet; and

retransmitting said cost information packet in response expiration of a timeout period without receipt of said cost information response packet.

6. The method of claim 5 wherein said cost information packets include a transmission retry count field and

wherein the step of transmitting includes the steps of:

incrementing said retry count field in response to sensing a failure of a previous transmission of said cost information packet; and

resending said cost information packet in response to sensing a failure of a previous transmission of said cost information packet, and

wherein the step of retransmitting includes the steps of;

incrementing said retry count field in response to sensing a failure of a previous retransmission of said cost information packet; and

resending said cost information packet in response to sensing a failure of a previous retransmission of said cost information packet.

7. The method of claim 6 further comprising the step of:

comparing the value of said transmission retry count field to a predetermined maximum value; and

bypassing the steps of resending in response to a determination that said value of said transmission retry count field exceeds said predetermined maximum value.

8. The method of claim 2

wherein said cost information packet includes a loop bit offset value associated with the transmitting switch of said cost information packet and

wherein the step of transmitting includes the step of:

storing the loop bit offset value associated with said first switch in said cost information packet prior to transmission thereof, and

wherein the step of forwarding includes the step of;

storing the loop bit offset value associated with said first switch in said cost information packet prior to forwarding thereof.

9. The method of claim 8

wherein said cost information packet includes a bit mask field having a bit corresponding to each possible loop bit offset value and

wherein the step of transmitting includes the step of:

setting the bit in said bit mask field corresponding to said loop bit offset value associated with said first switch in said cost information packet prior to transmission thereof, and

wherein the step of forwarding includes the step of;

setting the bit in said bit mask field corresponding to said loop bit offset value associated with said first switch in said cost information packet prior to forwarding thereof.

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

determining that the bit in said bit mask field corresponding to said loop bit offset value associated with said first switch in the received cost information packet is set; and

bypassing the step of forwarding in response to a determination that said bit in said bitmask corresponding to said loop bit offset value associated with said first switch in the received cost information packet is set.

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

recording loop information derived from said bit mask field of said received cost information packet in a memory associated with said first switch.

12. The method of claim 2 wherein the step of recording includes the step of:

storing path information derived from said cost information packet and corresponding cost information derived from said cost information packet in a first location of a memory associated with said first switch in response to receipt of said cost information packets.

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

awaiting convergence of the step of propagating said cost information; and

copying said path information and said corresponding cost information to a second location of said memory in response to said convergence.

14. The method of claim 13 wherein the step of awaiting convergence includes the step of:

waiting for a predetermined period of time after initiation of the periodic propagation.

15. The method of claim 14 further comprising the step of:

discarding said cost information packets received from said another switch after said convergence.

16. The method of claim 13 wherein each said cost information packet includes a sequence number indicative of the convergence period for which it was propagated and wherein the step of awaiting convergence includes the step of:

using said sequence number to determine when convergence has occurred for said convergence period.

39. The method of claim 1, wherein propagating of cost information packets is performed at Layer 2.

41. The method of claim 1, wherein the cost information is dynamic.

17. A system including a plurality of network switches, each of said switches including a computer readable storage medium tangibly embodying a method operable within said plurality of network switches for exchanging cost information among said plurality of network switches, said method comprising the steps of:

propagating cost information packets between a first switch of said plurality of network switches and other switches of said plurality of network switches so as to propagate cost information among said plurality of network switches; and

periodically repeating the propagation of said cost information packets based upon expiration of a pre-determined period of time so as to periodically update the cost information among said plurality of network switches instead of updating the cost information directly in response to any cost parameter change.

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

transmitting a cost information packet from a first switch of said plurality of network switches to other switches of said plurality of network switches;

receiving, in said first switch, a cost propagation packet transmitted from another switch of said plurality of network switches;

recording information derived from the received cost information packet in a memory associated with said first switch; and

forwarding the received cost propagation packet from said first switch to said other switches.

19. The system of claim 18 wherein said cost information packets include a hop count field and wherein the method further comprises the step of:

incrementing said hop count field in association with the step of transmitting and in association with the step of forwarding.

20. The system of claim 19 wherein the method further comprises the steps of:

comparing the value of said hop count field to a predetermined maximum value; and

bypassing the step of forwarding in response to a determination that said value of said hop count field exceeds said predetermined maximum value.

21. The system of claim 18 wherein the method further comprises the steps of:

awaiting receipt of a cost information response packet from each of said other switches in response to transmission of said cost information packet; and

retransmitting said cost information packet in response expiration of a timeout period without receipt of said cost information response packet.

22. The system of claim 21 wherein said cost information packets include a transmission retry count field and

wherein the method step of transmitting includes the steps of:

incrementing said retry count field in response to sensing a failure of a previous transmission of said cost information packet; and

resending said cost information packet in response to sensing a failure of a previous transmission of said cost information packet, and

wherein the method step of retransmitting includes the steps of;

incrementing said retry count field in response to sensing a failure of a previous retransmission of said cost information packet; and

resending said cost information packet in response to sensing a failure of a previous retransmission of said cost information packet.

23. The system of claim 22 wherein the method further comprises the step of:

comparing the value of said transmission retry count field to a predetermined maximum value; and

bypassing the steps of resending in response to a determination that said value of said transmission retry count field exceeds said predetermined maximum value.

24. The system of claim 18

wherein said cost information packet includes a loop bit offset value associated with the transmitting switch of said cost information packet and

wherein the method step of transmitting includes the step of:

storing the loop bit offset value associated with said first switch in said cost information packet prior to transmission thereof, and

wherein the method step of forwarding includes the step of;

storing the loop bit offset value associated with said first switch in said cost information packet prior to forwarding thereof.

25. The system of claim 24

wherein said cost information packet includes a bit mask field having a bit corresponding to each possible loop bit offset value and

wherein the method step of transmitting includes the step of:

setting the bit in said bit mask field corresponding to said loop bit offset value associated with said first switch in said cost information packet prior to transmission thereof, and

wherein the method step of forwarding includes the step of;

setting the bit in said bit mask field corresponding to said loop bit offset value associated with said first switch in said cost information packet prior to forwarding thereof.

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

determining that the bit in said bit mask field corresponding to said loop bit offset value associated with said first switch in the received cost information packet is set; and

bypassing the step of forwarding in response to a determination that said bit in said bitmask corresponding to said loop bit offset value associated with said first switch in the received cost information packet is set.

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

recording loop information derived from said bit mask field of said received cost information packet in a memory associated with said first switch.

28. The system of claim 18 wherein the method step of recording includes the step of:

storing path information derived from said cost information packet and corresponding cost information derived from said cost information packet in a first location of a memory associated with said first switch in response to receipt of said cost information packets.

29. The system of claim 28 wherein the method further comprises the step of:

awaiting convergence of the step of propagating said cost information; and

copying said path information and said corresponding cost information to a second location of said memory in response to said convergence.

30. The system of claim 29 wherein the method step of awaiting convergence includes the step of:

waiting for a predetermined period of time after initiation of the periodic propagation.

31. The system of claim 30 wherein the method further comprises the step of:

discarding said cost information packets received from said another switch after said convergence.

32. The system of claim 29 wherein each said cost information packet includes a sequence number indicative of the convergence period for which it was propagated and wherein the method step of awaiting convergence includes the step of:

using said sequence number to determine when convergence has occurred for said convergence period.

40. The system of claim 17, wherein propagating of cost information packets is performed at Layer 2.

42. The system of claim 17, wherein the cost information is dynamic.

33. A method operable within a plurality of network switches for exchanging cost information among said plurality of network switches, said method comprising the steps of:

propagating cost information packets between a first switch of said plurality of network switches and other switches of said plurality of network switches;

periodically repeating the propagation of said cost information packets based upon expiration of a pre-determined period of time;

awaiting receipt of a cost information response packet from each of said other switches in response to transmission of said cost information packet; and

retransmitting said cost information packet in response to expiration of a timeout period without receipt of said cost information response packet;

wherein the step of propagating includes the steps of;

transmitting a cost information packet from a first switch of said plurality of network switches to other switches of said plurality of network switches;

receiving, in said first switch, a cost propagation packet transmitted from another switch of said plurality of network switches;

recording information derived from the received cost information packet in a memory associated with said first switch; and

forwarding the received cost propagation packet from said first switch to said other switches;

wherein said cost information packets include a transmission retry count field and,

wherein the step of transmitting includes the steps of;

incrementing said retry count field in response to sensing a failure of a previous transmission of said cost information packet; and

resending said cost information packet in response to sensing a failure of a previous transmission of said cost information packet; and

wherein the step of retransmitting includes the steps of;

incrementing said retry count field in response to sensing a failure of a previous retransmission of said cost information packet; and

resending said cost information packet in response to sensing a failure of a previous transmission of said cost information packet.

34. A method operable within a plurality of network switches for exchanging cost information among said plurality of network switches, said method comprising the steps of:

propagating cost information packets between a first switch of said plurality of network switches and other switches of said plurality of network switches;

periodically repeating the propagation of said cost information packets based upon expiration of a pre-determined period of time;

wherein the step of propagating includes the steps of;

transmitting a cost information packet from a first switch of said plurality of network switches to other switches of said plurality of network switches;

receiving, in said first switch, a cost propagation packet transmitted from another switch of said plurality of network switches;

recording information derived from the received cost information packet in a memory associated with said first switch; and

forwarding the received cost propagation packet from said first switch to said other switches;

wherein said cost information packet includes a loop bit offset value associated with the transmitting switch of said cost information packet and

wherein the step of transmitting includes the step of storing the loop bit offset value associated with said first switch in said cost information packet prior to transmission thereof, and

wherein the step of forwarding includes the step of storing the loop bit offset value associated with said first switch in said cost information packet prior to forwarding thereof.

35. A method operable within a plurality of network switches for exchanging cost information among said plurality of network switches, said method comprising the steps of:

propagating cost information packets between a first switch of said plurality of network switches and other switches of said plurality of network switches;

periodically repeating the propagation of said cost information packets based upon expiration of a pre-determined period of time;

awaiting convergence of the step of propagating said cost information; and

copying said path information and said corresponding cost information to a second location of said memory in response to said convergence;

wherein the step of propagating includes the steps of;

transmitting a cost information packet from a first switch of said plurality of network switches to other switches of said plurality of network switches;

receiving, in said first switch, a cost propagation packet transmitted from another switch of said plurality of network switches;

recording information derived from the received cost information packet in a memory associated with said first switch; and

forwarding the received cost propagation packet from said first switch to said other switches;

wherein the step of recording includes the step of;

storing path information derived from said cost information packet and corresponding cost information derived from said cost information packet in a first location of a memory associated with said first switch in response to receipt of said cost information packets;

wherein each of said cost information packet includes a sequence number indicative of the convergence period for which it was propagated and wherein the step of awaiting convergence includes the step of using said sequence number to determine when convergence has occurred for said convergence period.

36. A system including a plurality of network switches, each of said switches including a computer readable storage medium tangibly embodying a method operable within said plurality of network switches for exchanging cost information among said plurality of network switches, said method comprising the steps of:

propagating cost information packets between a first switch of said plurality of network switches and other switches of said plurality of network switches; and

periodically repeating the propagation of said cost information packets based upon expiration of a pre-determined period of time;

awaiting receipt of a cost information response packet from each of said other switches in response to transmission of said cost information packet; and

retransmitting said cost information packet in response to expiration of a timeout period without receipt of said cost information response packet;

wherein the method step of propagating includes the steps of;

transmitting a cost information packet from a first switch of said plurality of network switches to other switches of said plurality of network switches;

receiving, in said first switch, a cost propagation packet transmitted from another switch of said plurality of network switches;

recording information derived from the received cost information packet in a memory associated with said first switch; and

forwarding the received cost propagation packet from said first switch to said other switches;

wherein said cost information packets include a transmission retry count field and,

wherein the method step of transmitting includes the steps of;

incrementing said retry count field in response to sensing a failure of a previous transmission of said cost information packet; and

resending said cost information packet in response to sensing a failure of a previous transmission of said cost information packet; and

wherein the method step of retransmitting includes the steps of;

incrementing said retry count field in response to sensing a failure of a previous retransmission of said cost information packet; and

resending said cost information packet in response to sensing a failure of a previous transmission of said cost information packet.

37. A system including a plurality of network switches, each of said switches including a computer readable storage medium tangibly embodying a method operable within said plurality of network switches for exchanging cost information among said plurality of network switches, said method comprising the steps of:

propagating cost information packets between a first switch of said plurality of network switches and other switches of said plurality of network switches; and

periodically repeating the propagation of said cost information packets based upon expiration of a pre-determined period of time;

wherein the method step of propagating includes the steps of;

transmitting a cost information packet from a first switch of said plurality of network switches to other switches of said plurality of network switches;

receiving, in said first switch, a cost propagation packet transmitted from another switch of said plurality of network switches;

recording information derived from the received cost information packet in a memory associated with said first switch; and

forwarding the received cost propagation packet from said first switch to said other switches;

wherein said cost information packet includes a loop bit offset value associated with the transmitting switch of said cost information packet and

wherein the method step of transmitting includes the step of storing the loop bit offset value associated with said first switch in said cost information packet prior to transmission thereof, and

wherein the step of forwarding includes the step of storing the loop bit offset value associated with said first switch in said cost information packet prior to forwarding thereof.

38. A system including a plurality of network switches, each of said switches including a computer readable storage medium tangibly embodying a method operable within said plurality of network switches for exchanging cost information among said plurality of network switches, said method comprising the steps of:

propagating cost information packets between a first switch of said plurality of network switches and other switches of said plurality of network switches; and

periodically repeating the propagation of said cost information packets based upon expiration of a pre-determined period of time;

wherein the method step of propagating includes the steps of;

transmitting a cost information packet from a first switch of said plurality of network switches to other switches of said plurality of network switches;

receiving, in said first switch, a cost propagation packet transmitted from another switch of said plurality of network switches;

recording information derived from the received cost information packet in a memory associated with said first switch; and

forwarding the received cost propagation packet from said first switch to said other switches;

wherein the method step of recording includes the step of storing path information derived from said cost information packet and corresponding cost information derived from said cost information packet in a first location of a memory associated with said first switch in response to receipt of said cost information packets.