Method and apparatus for the distribution of network traffic
View Patent ↗A packet network system, such as an autonomous system, includes a plurality of packet network devices some of which are edge routers and some of which are core routers. Each of the edge and core routers include 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 traffic distribution function that operates to calculate path bandwidths for all of the paths over which the traffic can be forwarding through the system and to use the volume of traffic ingressing to the system, link utilization information and the calculated path bandwidth to redistribute the traffic in the system such that traffic loss in the system in minimized.
1. A method for distributing traffic ingressing to a packet network system, comprising:
providing a separate instance of an interior gateway protocol (IGP), running on each one of a plurality of routers comprising a packet network system, that calculates all eligible paths for traffic through the packet network system;
providing a separate instance of a traffic distribution function, running on each one of the plurality of routers comprising the packet network system, that receives, from each of the other of the plurality of routers, link volume information representative of the volume of traffic ingressing to each of the routers and link bandwidth information representative of available link bandwidth for all links to each of the plurality of routers in the packet network system, and uses the link bandwidth information to calculate a path bandwidth for each of the calculated eligible paths in the packet network system;
using the calculated eligible path bandwidths and the link volume information to calculate under-utilized links that are each associated with a volume of traffic ingressing to the link that is below an available bandwidth of the link and over-utilized links that are each associated with a volume of traffic ingressing to the link that is above an available bandwidth of the link for at least some of the eligible paths in the packet network system;
programming forwarding table entries in each of the plurality of routers to forward higher priority traffic flows over the eligible paths with under-utilized links before forwarding lower priority traffic flows over the eligible paths with under-utilized links, wherein the programming forwarding table entries 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 determining a priority for the first traffic flow that is based on at least one of: a bandwidth needed to support the first traffic flow, a number of hops from an ingress router to a destination for the first traffic flow, an identity of the router into which the first traffic flow has ingressed, and an identity of the router out of which the first traffic flow has egressed; and
forwarding the first traffic flow over one or more eligible paths in the packet network system using the determined priority and the forwarding tables entries in each of the plurality of the routers in the packet network system.
2. The method of claim 1 wherein the IGP is an Open Shortest Path First or an Intermediate System to Intermediate System network protocol.
3. The method of claim 1 wherein the traffic ingressing to the packet network system is comprised of one or more traffic flows and the calculated eligible paths includes a set of paths of equal cost, as calculated by the IGP running on each of the routers, over which each one of the one or more traffic flows ingressing to the routers is forwarded to reach their destination.
4. The method of claim 1 wherein the traffic distribution function is comprised of a link utilization calculation function, a path bandwidth calculation function and a redistribution algorithm function all of which can access a store of packet network system information.
5. The method of claim 4 wherein the redistribution algorithm function operates to distribute traffic that results in a minimal loss of all traffic ingressing to the packet network system.
6. The method of claim 1 wherein the link volume information representative of the volume of traffic ingressing to each of the routers is comprised of the total traffic volume ingressing to each of the routers.
7. The method of claim 6 wherein the total traffic volume ingressing to each of the routers is comprised of the sum of the volume of one or more traffic flows.
8. A method for distributing traffic ingressing to a packet network system, comprising:
providing a separate instance of an interior gateway protocol (IGP), running on each one of a plurality of routers comprising a packet network system, that calculates all eligible paths over which traffic is forwarded through the packet network system;
providing a separate instance of a traffic distribution function, running on each one of the plurality of routers comprising the packet network system, that receives, from each of the other of the plurality of routers, link volume information representative of the traffic ingressing to the routers and link bandwidth information representative of available link bandwidth for all links to each of the plurality of routers in the packet network system, and using the link bandwidth information to calculate a path bandwidth for each of the calculated eligible paths in the packet network system;
using one or more traffic prioritization criteria that include a bandwidth needed to support a received traffic flow to derive a traffic distribution priority for each of a plurality of traffic flows comprising the traffic ingressing to the packet network system such that the plurality of traffic flows include higher priority traffic flows and lower priority traffic flows;
using the calculated eligible path bandwidths and the link volume information to calculate under-utilized links that are each associated with a volume of traffic ingressing to the link that is a predetermined amount greater than an available bandwidth of the link and over-utilized links that are each associated with a volume of traffic ingressing to the link that is a predetermined amount less than an available bandwidth of the link for at least some of the eligible paths in the packet network system;
programming forwarding table entries in each of the plurality of routers to distribute higher priority traffic flows over the eligible paths with under-utilized links before distributing lower priority traffic flows over the eligible paths with under-utilized links, wherein the programming forwarding table entries 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; and
forwarding the plurality of traffic flows over one or more eligible paths using a priority determined for each of the plurality of traffic flows according to the traffic distribution priority and the forwarding table entries in each of the plurality of the routers in the packet network system.
9. The method of claim 8 wherein the IGP is an Open Shortest Path First or an Intermediate System to Intermediate System network protocol.
10. The method of claim 8 wherein the calculated eligible paths includes a set of paths of equal cost, as calculated by the IGP running on each of the routers, over which each of the plurality of traffic flows ingressing to the routers is forwarded to reach their proper destination.
11. The method of claim 8 wherein the traffic distribution function is comprised of a link utilization calculation function, a path bandwidth calculation function and a redistribution algorithm function, each of which access a store of packet network system information to perform their functions.
12. The method of claim 11 wherein the redistribution algorithm function operates to first distribute traffic of the highest priority.
13. The method of claim 8 wherein the link volume information representative of the volume of traffic ingressing to each of the routers is comprised of the total traffic volume ingressing to each of the routers.
14. The method of claim 13 wherein the total traffic volume ingressing to each of the routers is comprised of the sum of the volume of one or more traffic flows.
15. The method of claim 8 wherein the traffic prioritization criteria also include at least one of a number of hops from an ingress router to a destination for the received traffic flow, an identity of a router into which the received traffic flow has ingressed, and an identity of a router from which the received traffic flow has egressed.