Method and apparatus for the distribution of network traffic
View Patent ↗A packet network device, such as a router or switch, includes functionality that operates to receive network traffic, process the traffic as needed and to forward the traffic to its destination. Additionally, each router includes a weighted equal cost multipath routing function that operates to identify equal cost paths over which to forward the network traffic, to calculate a path weighting that is dependent upon the path bandwidth and to forward the traffic ingressing to it over each of the equal cost paths according to the calculated path weighting.
1. A method of distributing traffic in a packet network system, comprising:
receiving, by a first packet network device of a plurality of packet network devices in a packet network system, information from each of the other packet network devices in the packet network system and using that information to calculate a plurality of paths over which to forward traffic flows;
using, by the first packet network device, the received information to identify two or more equal cost paths over which to forward traffic flows and to calculate a bandwidth available on each of the two or more equal cost paths;
determining, by the first packet network device using the calculated bandwidth available on each of the two or more equal cost paths, that the first equal cost path of the two or more equal cost paths is under-utilized;
programming a forwarding table in the first packet network device to forward higher priority traffic flows over the first equal cost path before forwarding lower priority traffic flows over the first equal cost path, wherein the programming the forwarding table includes, for each traffic flow:
identifying a plurality of equal cost multi-paths (ECMPs) for that traffic flow;
determining a total ECMP bandwidth for that traffic flow;
determining a pre-redistribution percentage of the total ECMP bandwidth attributable to each of the plurality of ECMPs; and
determining a redistribution of that traffic flow across the plurality of ECMPs, wherein each ECMP is provided a redistributed percentage of that traffic flow that is based on the pre-redistribution percentage of the total ECMP bandwidth attributable to that ECMP and the maximum number of ECMPs that the forwarding table can support;
receiving a first traffic flow and prioritizing the first traffic flow higher than at least one second traffic flow based on a first bandwidth needed to support the first traffic flow relative to a second bandwidth needed to support the at least one second traffic flow; and
forwarding the first traffic flow over the first equal cost path before forwarding the at least one second traffic flow over the first equal cost path according to the forwarding table.
2. The method of claim 1 wherein the prioritizing the first traffic flow higher than at least one second traffic flow is also based on a number of hops from an ingress router to a first traffic flow destination for the first traffic flow relative to a number of hops from an ingress router to a second traffic flow destination for each at least one second traffic flow.
3. The method of claim 1 wherein the packet network system is an autonomous system that includes a connected group of one or more Internet Protocol (IP) prefixes and has a single, defined routing policy.
4. The method of claim 1 wherein the information received from each of the other packet network devices in the packet network system includes a link state advertisement from each of the other packet network devices.
5. The method of claim 4 wherein the link state advertisement from each of the other packet network devices is comprised of one or more of a network interface index, an interface bandwidth, an interface type, an interface cost, and path bandwidth determined by that packet network device.
6. The method of claim 5 wherein the interface type is one of a physical link, an aggregation of physical links, and a virtual LAN.
7. The method of claim 5 wherein the interface cost is comprised of one or more cost metrics.
8. The method of claim 7 wherein the one or more cost metrics are a distance to another packet network device in the packet network system, a link bandwidth, a link availability, and a link reliability factor.
9. The method of claim 1 wherein each of the two or more equal cost paths is weighted according to the percentage of a total bandwidth, of the identified two or more equal cost paths, that is apportioned to each of the equal cost paths.
10. A packet network device, comprising:
one or more line cards; and
a control module that includes at least one route processing module, the route processing module including:
means for calculating a bandwidth available for each of two or more identified equal cost paths and determining, using that calculated bandwidth, that a first identified equal cost path of the two or more identified equal cost paths is under-utilized;
means for programming a forwarding information base to forward higher priority traffic flows over the first identified equal cost past before forwarding lower priority traffic flows over the first identified equal cost path, wherein the means for programming the forwarding information base includes, for each traffic flow:
means for identifying a plurality of equal cost multi-paths (ECMPs) for that traffic flow;
means for determining a total ECMP bandwidth for that traffic flow;
means for determining a pre-redistribution percentage of the total ECMP bandwidth attributable to each of the plurality of ECMPs; and
means for determining a redistribution of that traffic flow across the plurality of ECMPs, wherein each ECMP is provided a redistributed percentage of that traffic flow that is based on the pre-redistribution percentage of the total ECMP bandwidth attributable to that ECMP and the maximum number of ECMPs that the forwarding table can support;
means for receiving a first traffic flow and prioritizing the first traffic flow higher than at least one second traffic flow based on a first bandwidth needed to support the first traffic flow relative to a second bandwidth needed to support the at least one second traffic flow; and
means for forwarding the first traffic flow over the first identified equal cost path before forwarding the at least one second traffic flow over the first identified equal cost path according to the forwarding table.
11. The packet network device of claim 10 wherein the route processing module is comprised of a route processor, means for processing link state advertisements, means for storing the packet network system link state information, and means for running an weighted equal cost multipath (WECMP) routing protocol.
12. The packet network device of claim 11 wherein the means for running an WECMP routing protocol operates, using the path bandwidths associated with each of the equal cost paths, to determine the proportions of the traffic that will be forwarded over each one of the two or more identified equal cost paths.