Weighted-cost multi-pathing using range lookups

Abstract

A method of forwarding packets by a physical network switch is provided. The method assigns egress ports that connect the network switch to each particular next hop to a weighted-cost multipathing (WCMP) group associated with the particular next hop. The method assigns weights to each egress port in each WCMP group according to the capacity of each path that connects the egress port to the next hop associated with the WCMP group and normalizes the weights over a range of values. For each packet received at the network switch, the method identifies the WCMP group associated with a next hop destination of the packet. The method calculates a hash value of a set of fields in the packet header and uses the hash value to perform a range lookup in the identified WCMP group to select an egress port for forwarding the packet to the next hop.

What is claimed is: 
     
       1. A method of forwarding packets by a physical network switch, the method comprising:
 identifying a weighted-cost multipathing (WCMP) group associated with a next hop of a received packet, wherein the identified WCMP group is associated with at least one egress port; and 
 applying WCMP in selecting an egress port to use to send the received packet to the next hop based on one or more fields in a header of the received packet, wherein:
 an egress port is associated with a weight, 
 the weight indicates a capacity of a path that connects the egress port to the next hop, 
 the weight is normalized over a range of values, 
 the range of values is based on a range associated with one or more fields in received packet headers, and 
 WCMP distributes network packet traffic among next hops in proportion to available capacity of links between the physical network switch and next hops whereby paths are assigned weights based on their capacity and are selected to forward packets with a probability proportional to weight of each path. 
 
 
     
     
       2. The method of  claim 1 , further comprising calculating a value based on a hash of one or more fields in a header of the received packet. 
     
     
       3. The method of  claim 2 , wherein calculating the value comprises calculating a hash value using one or more of: a source Internet protocol (IP) address, a destination IP address, a source port number, a destination port number, and a protocol used in communicating the received packet. 
     
     
       4. The method of  claim 1 , wherein identifying a WCMP group associated with a next hop of a received packet comprises identifying a WCMP group based on a destination Internet Protocol (IP) address in the received packet. 
     
     
       5. The method of  claim 1 , wherein selecting an egress port to use to send the received packet to the next hop based on one or more fields in a header of the received packet comprises:
 calculating a value based on a hash of one or more fields in a header of the received packet and 
 selecting an egress port of the identified WCMP group based on the calculated value being within a range of values associated with the selected egress port. 
 
     
     
       6. The method of  claim 1 , comprising:
 determining a range of potential hash values from a hash of one or more fields in a header of the received packet; 
 normalizing the weight over the range of potential hash values; and 
 assigning a subset of the range of values to an egress port associated with a WCMP group, wherein the range of values comprises the range of hash potential values. 
 
     
     
       7. The method of  claim 1 , wherein members of a WCMP group are not replicated within the WCMP group. 
     
     
       8. The method of  claim 1 , wherein one or more match action units perform the identifying and using a value to select an egress port. 
     
     
       9. The method of  claim 1 , wherein the next hop comprises a next network switch or router in a path of the received packet to the received packet's final destination. 
     
     
       10. The method of  claim 1 , further comprising:
 assigning egress ports that connect the physical network switch to a particular next hop destination to a second WCMP group associated with the particular next hop destination; 
 assigning weights to at least one egress port in the second WCMP group according to a capacity of a path that connects an egress port to a next hop associated with the second WCMP group; and 
 normalizing the weights over a range of values. 
 
     
     
       11. The method of  claim 1 , comprising:
 based on failure of an egress port, removing the failed egress port from the WCMP group and adjusting weights for remaining egress ports. 
 
     
     
       12. A hardware network switch, the hardware network switch comprising: a processor; a memory; and a set of ingress pipelines, at least one ingress pipeline configured to:
 identify a weighted-cost multipathing (WCMP) group associated with a next hop of a received packet, wherein the identified WCMP group is associated with at least one egress port; and 
 apply WCMP to select an egress port to use to send the received packet to the next hop based on one or more fields in a header of the received packet, wherein:
 an egress port is associated with a weight, 
 the weight indicates a capacity of a path that connects the egress port to the next hop, 
 the weight is normalized over a range of values, 
 the range of values is based on a range associated with one or more fields in received packet headers, and 
 WCMP distributes network packet traffic among next hops in proportion to available capacity of links between the hardware network switch and next hops whereby paths are assigned weights based on their capacity and are selected to forward packets with a probability proportional to a weight of each path. 
 
 
     
     
       13. The switch of  claim 12 , wherein the at least one ingress pipeline is configured to:
 calculate a value based on a hash of one or more fields in a header of the received packet. 
 
     
     
       14. The switch of  claim 13 , wherein to calculate the value, the at least one ingress pipeline is to calculate a hash value using one or more of: a source Internet protocol (IP) address, a destination IP address, a source port number, a destination port number, and a protocol used in communicating the received packet. 
     
     
       15. The switch of  claim 12 , wherein apply WCMP to select an egress port to use to send the received packet to the next hop based on one or more fields in a header of the received packet comprises:
 calculate a value based on a hash of one or more fields in a header of the received packet and 
 select an egress port of the identified WCMP group based on the calculated value being within a range of values associated with the selected egress port. 
 
     
     
       16. The switch of  claim 12 , wherein members of a WCMP group are not replicated within the WCMP group. 
     
     
       17. The switch of  claim 12 , comprising one or more match action units to identify a WCMP group and select an egress port to use. 
     
     
       18. The switch of  claim 12 , wherein the next hop comprises a next network switch or router in a path of the received packet to the received packet's final destination. 
     
     
       19. The switch of  claim 12 , further comprising a traffic manager and a set of egress pipelines.