Weighted equal cost multipath routing
In some implementations, network traffic can be routed along equal cost paths based on weights assigned to each path. For example, weighted equal cost multipath routing can be implemented by assigning weights to each equal cost path (e.g., uplink, next hop node) to a destination device. When the network device receives a packet, the network device can generate a key (e.g., a random value, a hash value based on packet data, a value between 0 and n, etc.). The key can be used to select an uplink or path upon which to forward the packet. A key can be generated for a packet flow or flowlet. Each flow can be associated with the same key so that each packet in a flow will be forwarded along the same path. Each flowlet can be forwarded along a different uplink.
1. A method comprising:
receiving user-specified weights for each equal cost uplink from a first network device to a destination device;
obtaining, at a first network device, a weighted forwarding table comprising the user-specified weights, each of the user-specified weights representing a respective proportion of network traffic to transmit on each equal cost uplink from the first network device to the destination device;
receiving, by the first network device, a network packet;
generating, for each equal cost uplink, a respective portion of a key value range, the respective portion of the key value range corresponding to the user-specified weights, and wherein the weighted forwarding table maps the respective portion of the key value range to each equal cost uplink to the destination device;
storing information identifying the respective portion of the key value range corresponding to each equal cost uplink in the weighted forwarding table; and
forwarding the network packet on an uplink identified in the weighted forwarding table based on the respective portion of the key value range of the uplink.
2. The method of claim 1 , wherein the network packet is associated with a flow, and wherein a key value is randomly generated for each flowlet received by the first network device.
3. The method of claim 1 , wherein generating the respective portion of the key value range comprises dividing the key value range into a plurality of portions of the key value range, wherein each of the plurality of portions is proportional to a respective one of the user-specified weights.
4. The method of claim 1 , wherein the respective portion comprises a respective key value, the method further comprising comparing the respectively key value to the weighted forwarding table and determining that the respective key value falls within the respective portion of the key value range corresponding to an identified uplink.
5. A non-transitory computer-readable medium including one or more instructions which, when executed by one or more processors, cause the one or more processors to perform operations comprising:
obtaining, at a first network device, a weighted forwarding table that specifies proportions of network traffic to transmit on each equal cost uplink from the first network device to a destination device, the proportions comprising user-specified weights for each equal cost uplink from the first network device to the destination device;
converting the user-specified weights for each equal cost uplink into portions of a key value range proportionate to the user-specified weights;
storing information identifying a respective portion of the key value range corresponding to each equal cost uplink in the weighted forwarding table;
receiving, by the first network device, a network packet;
generating a key value within the key value range;
comparing the key value to the weighted forwarding table; and
forwarding the network packet on an uplink identified in the weighted forwarding table based on the comparison.
6. The non-transitory computer-readable medium of claim 5 , wherein the network packet is associated with a flow, wherein a respective key value is randomly generated for each flowlet received by the first network device.
7. The non-transitory computer-readable medium of claim 5 , wherein comparing the key value to the weighted forwarding table comprises determining which of the portions of the key value range includes the key value.
8. The non-transitory computer-readable medium of claim 5 , wherein comparing the key value to the weighted forwarding table comprises determining that the key value is within a respective one of the portions of the key value range.
9. A system comprising:
one or more processors; and
a computer-readable storage device including instructions which, when executed by one or more processors, cause the one or more processor to perform operations comprising:
receiving user-specified weights for each equal cost uplink from a first network device to a destination device;
obtaining, at a first network device, a weighted forwarding table comprising the user-specified weights, each of the user-specified weights representing a respective proportion of network traffic to transmit on each equal cost uplink from the first network device to the destination device;
receiving, by the first network device, a network packet;
generating, for each equal cost uplink, a respective portion of a key value range, the respective portion of the key value range corresponding to the user-specified weights, and wherein the weighted forwarding table maps the respective portion of the key value range to each equal cost uplink to the destination device;
storing information identifying the respective portion of the key value range corresponding to each equal cost uplink in the weighted forwarding table; and
forwarding the network packet on an uplink identified in the weighted forwarding table based on the respective portion of the key value range of the uplink.
10. The system of claim 9 , the operations further comprising generating a key value randomly for each flowlet received by the first network device.
11. The system of claim 9 , the operations further comprising generating a key value for one or more flows received by the first network device, the key value comprising a hash value generated based on source and destination information for each of the one or more flows received by the first network device.
12. The system of claim 9 , the operations further comprising comparing one or more respective values associated with the respective portion with the weighted forwarding table and determining that the one or more respective values fall within a portion of a respective key value range corresponding to the uplink.