Cost calculation in load balancing switch protocols
First Claim
1. A method operable within a network switch for determining costs associated with communication to other network switches and device through ports of said network switch, said method comprising the steps of:
- computing periodically, within said network switch, a port latency value associated with operation of a port of said network switch, the port latency value equal to a queue depth of data stored in at least one queue associated with said port divided by a data transfer speed associated with a port of the network switch; and
computing periodically, within said network switch, a port load factor cost value as a ratio of said port latency value and the available throughput of said port.
3 Assignments
0 Petitions
Accused Products
Abstract
A method for computing cost information associated with a port of a switch in a network of switches. Cost information is computed as a port load factor: a ratio of port latency over available throughput. Port latency is determined as the depth of a queue associated with the port divided by the speed of the port. Available throughput is determined as the speed of the slowest port on a given path associated with the port in question. Preferably, the queue depth is measured in bits and the port speed and available throughput are measured in bits per second. Further, in the preferred embodiment, port latency is computed as a weighted average as ((15×previous latency)+current latency)/16. A higher value for the port load factor indicates a port which is more heavily loaded. The load factor is therefore useful in load balancing among the ports of switches and paths associated therewith.
165 Citations
34 Claims
-
1. A method operable within a network switch for determining costs associated with communication to other network switches and device through ports of said network switch, said method comprising the steps of:
-
computing periodically, within said network switch, a port latency value associated with operation of a port of said network switch, the port latency value equal to a queue depth of data stored in at least one queue associated with said port divided by a data transfer speed associated with a port of the network switch; and
computing periodically, within said network switch, a port load factor cost value as a ratio of said port latency value and the available throughput of said port. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
computing a weighted average of a present port latency value and prior port latency values associated with operation of a port of said network switch.
-
-
3. The method of claim 2 wherein the step of computing said weighted average comprises the step of:
computing said weighted average as;
-
4. The method of claim 1 wherein the step of computing a port load factor value comprises the step of:
computing a weighted average of a present port load factor value and at least one previously computed port load factor value.
-
5. The method of claim 4 wherein the step of computing said weighted average comprises the step of:
computing said weighted average as;
-
6. The method of claim 1 wherein said available throughput is determined as the port speed of the slowest port on a path associated with said port of said network switch.
-
7. The method of claim 1 wherein the step of computing a port latency value comprises the steps of:
-
determining a queue depth as the amount of data stored in at least one queue associated with said port; and
dividing said queue depth by a data transfer speed associated with a port of said network switch to generate the port latency value.
-
-
8. The method of claim 7 the step of determining a queue depth comprises the step of determining the depth of an outbound queue associated with said port and wherein said data transfer speed is the speed of outbound transfers on said port.
-
9. The method of claim 1 wherein the method further comprises the steps of:
-
receiving a cost packet from a first other network switch via a first port of said network wherein the steps of computing a port latency value and computing a port load factor are responsive to receipt of said cost packet;
updating information in said cost packet as a function of said port latency value; and
forwarding said cost packet to a second other network switch via a second port of said network switch.
-
-
10. The method of claim 9 wherein the step of computing said port latency value comprises the steps of:
-
determining an outbound port latency value associated with said first port;
determining an inbound port latency value associated with said second port; and
combining said inbound port latency value and said outbound port latency value to generate said port latency value.
-
-
11. The method of claim 10
wherein the step of determining said outbound port latency value comprises the steps of: -
determining an outbound queue depth as the amount of data stored in an outbound queue associated with said first port; and
dividing said outbound queue depth by a data transfer speed associated with said first port to generate said outbound port latency value.
-
-
12. The method of claim 11
wherein the step of determining said inbound port latency comprises the steps of: -
determining an inbound queue depth as the amount of data stored in an inbound queue associated with said second port; and
dividing said inbound queue depth by a data transfer speed associated with said first port of said network switch to generate said inbound port latency value.
-
-
13. The method of claim 11
wherein the step of determining said inbound port latency comprises the steps of: -
determining an inbound queue depth as the amount of data stored in an inbound queue associated with said second port;
selecting another port having the fastest speed of all ports of said network switch known to be usable to forward packets to said first other network switch dividing said inbound queue depth by the data transfer speed associated with said another port of said network switch to generate said inbound port latency value.
-
-
14. The method of claim 1 further comprising the steps of:
-
determining a quantity of dropped data as a quantity of data dropped by said network switch from queues associated therewith; and
increasing said port latency value in accordance with said quantity of dropped data.
-
-
15. The method of claim 14
wherein the step of determining a quantity of dropped data includes the step of: -
determining a drop rate as a percentage of said quantity of dropped data as compared to a quantity of data transmitted from said network switch, and wherein the step of modifying said port latency value includes the step of;
multiplying said port latency value by the quantity (2(said drop rate/10)).
-
-
16. The method of claim 1 wherein said network switch includes a plurality of ports logically grouped as a trunked port and wherein the method further comprises the step of:
distributing packets to said plurality of ports in said trunked port in accordance with said port load factor of each port of said trunked port.
-
17. The method of claim 16 wherein the step of distributing comprises the step of:
distributing said packets to said plurality of ports in said trunked port in inverse proportion to said port load factor of said each port.
-
18. A network switch including a computer readable storage medium tangibly embodying a method operable within said network switch for determining costs associated with communication to other network switches and device through ports of said network switch, said method comprising the steps of:
-
computing periodically, within said network switch, a port latency value associated with operation of a port of said network switch, the port latency value equal to a queue depth of data stored in at least one queue associated with said port divided by a data transfer speed associated with a port of the network switch; and
computing periodically, within said network switch, a port load factor cost value as a ratio of said port latency value and the available throughput of said port. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
computing a weighted average of a present port latency value and prior port latency values associated with operation of a port of said network switch.
-
-
20. The system of claim 19 wherein the method step of computing said weighted average comprises the step of:
computing said weighted average as;
-
21. The system of claim 18 wherein the method step of computing a port load factor value comprises the step of:
computing a weighted average of a present port load factor value and at least one previously computed port load factor value.
-
22. The system of claim 21 wherein the method step of computing said weighted average comprises the step of:
computing said weighted average as;
-
23. The system of claim 18 wherein said available throughput is determined as the port speed of the slowest port on a path associated with said port of said network switch.
-
24. The system of claim 18 wherein the method step of computing a port latency value comprises the steps of:
-
determining a queue depth as the amount of data stored in at least one queue associated with said port; and
dividing said queue depth by a data transfer speed associated with a port of said network switch to generate the port latency value.
-
-
25. The system of claim 24 the step of determining a queue depth comprises the step of determining the depth of an outbound queue associated with said port and wherein said data transfer speed is the speed of outbound transfers on said port.
-
26. The system of claim 18 wherein the method further comprises the steps of:
-
receiving a cost packet from a first other network switch via a first port of said network wherein the steps of computing a port latency value and computing a port load factor are responsive to receipt of said cost packet;
updating information in said cost packet as a function of said port latency value; and
forwarding said cost packet to a second other network switch via a second port of said network switch.
-
-
27. The system of claim 26 wherein the method step of computing said port latency value comprises the steps of:
-
determining an outbound port latency value associated with said first port;
determining an inbound port latency value associated with said second port; and
combining said inbound port latency value and said outbound port latency value to generate said port latency value.
-
-
28. The system of claim 27
wherein the method step of determining said outbound port latency value comprises the steps of: -
determining an outbound queue depth as the amount of data stored in an outbound queue associated with said first port; and
dividing said outbound queue depth by a data transfer speed associated with said first port to generate said outbound port latency value.
-
-
29. The system of claim 28
wherein the method step of determining said inbound port latency comprises the steps of: -
determining an inbound queue depth as the amount of data stored in an inbound queue associated with said second port; and
dividing said inbound queue depth by a data transfer speed associated with said first port of said network switch to generate said inbound port latency value.
-
-
30. The system of claim 28
wherein the method step of determining said inbound port latency comprises the steps of: -
determining an inbound queue depth as the amount of data stored in an inbound queue associated with said second port;
selecting another port having the fastest speed of all ports of said network switch known to be usable to forward packets to said first other network switch dividing said inbound queue depth by the data transfer speed associated with said another port of said network switch to generate said inbound port latency value.
-
-
31. The system of claim 18 wherein the method further comprises the steps of:
-
determining a quantity of dropped data as a quantity of data dropped by said network switch from queues associated therewith; and
increasing said port latency value in accordance with said quantity of dropped data.
-
-
32. The system of claim 31
wherein the method step of determining a quantity of dropped data includes the step of: -
determining a drop rate as a percentage of said quantity of dropped data as compared to a quantity of data transmitted from said network switch, and wherein the method step of modifying said port latency value includes the step of;
multiplying said port latency value by the quantity (2(said drop rate/10)).
-
-
33. The system of claim 18 wherein said network switch includes a plurality of ports logically grouped as a trunked port and wherein the method further comprises the step of:
distributing packets to said plurality of ports in said trunked port in accordance with said port load factor of each port of said trunked port.
-
34. The system of claim 33 wherein the method step of distributing comprises the step of:
distributing said packets to said plurality of ports in said trunked port in inverse proportion to said port load factor of said each port.
Specification