Methods, apparatuses and systems facilitating deployment, support and configuration of network routing policies

• US 20020141343A1
• Filed: 12/19/2001
• Published: 10/03/2002
• Est. Priority Date: 03/28/2001
• Status: Active Grant

• Current Assignee: Transaction Network Services Incorporated (Trident Private Holdings I LLC)
• Original Assignee: Transaction Network Services Incorporated (Trident Private Holdings I LLC)
• Inventors: Bays, Robert James
• Granted Patent: US 7,139,242 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 41/0895 Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements

Abstract

Methods, apparatuses and systems relating to the control and application of policies for routing data over a computer network, such as the Internet. Some implementations of the invention facilitate the configuration, deployment and/or maintenance of network routing policies. Some implementations of the invention are particularly useful for controlling the routing of data among autonomous systems or organizations. Certain implementations allow for dynamic modification of routing policy based on such factors as current Internet performance, load sharing, user-defined parameters, and time of day.

Claims

1. A method facilitating the distribution of traffic flows across a plurality of routing peers, the traffic flows transmitted from a first computer network to hosts associated with respective destination networks, and wherein there is at least one path from the first computer network to each destination network, the method comprising the steps of

monitoring traffic flows from a first computer network to a plurality of respective destination networks;

generating an ordered list of destination networks based on a traffic flow statistic value associated with each destination network,

for each destination network in the ordered list, associating the routing peer(s) having reachability to the destination network; and

iteratively performing a load balancing cycle until all destination networks have been assigned a routing peer, the load balancing cycle comprising;

for a first routing peer;

selecting the first unassigned destination network to which the first routing peer has reachability and assigning the selected destination network to the first routing peer; and

setting a traffic flow weighting value to the traffic flow statistic value associated with the selected destination network;

for each subsequent routing peer;

selecting the first unassigned destination network to which the routing peer has reachability;

assigning the selected destination network to the routing peer;

repeating the selecting step until the traffic flow statistic values associated with the selected destination network(s) aggregate beyond a threshold level derived from the traffic flow weighting value; and

assigning the selected destination network(s) to the routing peer.

2. The method of claim 1 wherein the selecting step for each subsequent routing peer is repeated until the traffic flow statistic values associated with the selected destination network(s) aggregate to within a threshold range from the traffic flow weighting value.

3. The method of claim 1 or 2 further comprising applying the paths assigned to each destination network to a routing system.

4. The method of claim 1 or 2 further comprising the steps of

monitoring utilization of the plurality of routing peers operably connected to the first computer network;

and

and wherein the load balancing operation is conditioned on utilization of at least one routing peer exceeding a predetermined threshold level.

5. The method of claim 4 wherein the threshold level is a threshold percentage of the utilization capacity associated with each routing peer.

6. The method of claim 1 or 2 further comprising the steps of

monitoring utilization of a selected routing peer operably connected to the first computer network;

and

and wherein the load balancing operation is conditioned on utilization of the selected routing peer exceeding a predetermined threshold level.

7. The method of claim 6 wherein the threshold level is a threshold percentage of the utilization capacity associated with the selected routing peer.

8. The method of claim 1 or 2 further comprising the steps of

before performing the load balancing steps, filtering the ordered destination networks against a predefined list of destination networks.

9. The method of claim 1 or 2 further comprising the steps of

before performing the load balancing steps, filtering the routing peer(s) associated with each destination network.

10. The method of claim 9 wherein the filtering step is performed to filter out invalid routing peers.

11. The method of claim 9 further comprising the step of

identifying a routing peer associated with a destination network during a higher priority process, and,

wherein the filtering step is performed to filter out all other routing peers if a routing peer associated with a higher priority process is identified.

12. The method of claim 9 wherein the filtering step is performed to filter out routing peers associated with paths having a hop count variance greater than a threshold value from the shortest path to the destination network.

13. The method of claim 1 or 2 further comprising the step of

associating at least one routing system to a group;

and

wherein the ordered list of destination networks in the generating step comprises an ordered list of destination networks to which at least one routing system in the group has reachability;

and wherein, for each destination network in the ordered list, associating the routing peer(s), operably connected to at least one routing system in the group, having reachability to the destination network.

14. The method of claim 1 or 2 further comprising the step of

defining at least one subnet of at least one destination network;

wherein the monitoring step comprises monitoring traffic flows from a first computer network to a plurality of respective destination networks and/or defined subnets of the destination networks;

wherein the generating step comprises generating an ordered list of destination networks and/or defined subnets of the destination networks based on a traffic flow statistic value associated with each destination network or subnet of the destination network; and

wherein the load balancing cycle is iteratively performed on all network destinations and/or defined subnets of the network destinations.

17. The method of claim 16 further comprising the step of

assigning a fill priority to a price tier based on the cost of the price tier relative to the respective costs of all price tiers corresponding to all associated routing peers.

18. The method of claim 16 wherein the selecting step for each subsequent routing peer is repeated until the traffic flow statistic values associated with the selected destination network(s) aggregate to within a threshold range from the traffic flow weighting value.

19. The method of claim 16 or 18 further comprising the step of

applying the paths assigned to each destination network to a routing system.

20. The method of claim 16 or 18 further comprising the steps of

monitoring utilization of the plurality of routing peers operably connected to the first computer network;

and

and wherein the load balancing operation is conditioned on utilization of at least one routing peer exceeding a predetermined threshold level.

21. The method of claim 20 wherein the threshold level is a threshold percentage of the utilization capacity associated with each routing peer.

22. The method of claim 16 or 18 further comprising the steps of

monitoring utilization of a selected routing peer operably connected to the first computer network;

and

and wherein the load balancing operation is conditioned on utilization of the selected routing peer exceeding a predetermined threshold level.

23. The method of claim 22 wherein the threshold level is a threshold percentage of the utilization capacity associated with the selected routing peer.

24. The method of claim 16 or 18 further comprising the steps of

before performing the load balancing steps, filtering the ordered destination networks against a predefined list of destination networks.

25. The method of claim 16 or 18 further comprising the steps of

before performing the load balancing steps, filtering the routing peer(s) associated with each destination network.

26. The method of claim 25 wherein the filtering step is performed to filter out invalid routing peers.

27. The method of claim 25 further comprising the step of

identifying a routing peer associated with a destination network during a higher priority process, and,

wherein the filtering step is performed to filter out all other routing peers if a routing peer associated with a higher priority process is identified.

28. The method of claim 25 wherein the filtering step is performed to filter out routing peers associated with paths having a hop count variance greater than a threshold value from the shortest path to the destination network.

29. The method of claim 16 or 18 further comprising the step of

associating at least one routing system to a group;

and

wherein the ordered list of destination networks in the generating step comprises an ordered list of destination networks to which at least one routing system in the group has reachability;

and wherein, for each destination network in the ordered list, associating the routing peer(s), operably connected to at least one routing system in the group, having reachability to the destination network.

30. The method of claim 16 or 18 further comprising the step of

defining at least one subnet of at least one destination network;

wherein the monitoring step comprises monitoring traffic flows from a first computer network to a plurality of respective destination networks and/or defined subnets of the destination networks;

wherein the generating step comprises generating an ordered list of destination networks and/or defined subnets of the destination networks based on a traffic flow statistic value associated with each destination network or subnet of the destination network; and

wherein the load balancing cycle is iteratively performed on all network destinations and/or defined subnets of the network destinations.

15. A method facilitating the distribution of traffic flows across a plurality of routing peers, the traffic flows transmitted from a first computer network to hosts associated with respective destination networks, and wherein there is at least one path from the first computer network to each destination network, the method comprising the steps of

monitoring traffic flows from a first computer network to a plurality of respective destination networks;

generating an ordered list of destination networks based on a traffic flow statistic value associated with each destination network,

for each destination network in the ordered list, associating the routing peer(s) having reachability to the destination network; and

iteratively performing a load balancing cycle until all destination networks have been assigned a routing peer, the load balancing cycle comprising;

for a first routing peer;

selecting the first unassigned destination network to which the first routing peer has reachability and assigning the selected destination network to the first routing peer; and

setting a traffic flow weighting value to the traffic flow statistic value associated with the selected destination network;

for each subsequent routing peer;

selecting the first unassigned destination network to which the routing peer has reachability and assigning the selected destination network to the routing peer; and

,

if the traffic flow statistic value associated with the assigned destination network is below a threshold level derived from the traffic flow weighting value, then;

selecting the next unassigned destination network to which the routing peer has reachability, and assigning the selected destination network, if the traffic flow statistic values associated with previously assigned destination networks and the next destination network aggregate below a maximum threshold derived from the traffic flow weighting value; and

repeating the selecting step and conditional assigning step until the traffic flow statistic values associated with the selected destination network(s) aggregate beyond a lower threshold value derived from the traffic flow weighting value.

16. A method facilitating the distribution of traffic flows across a plurality of routing peers, the traffic flows transmitted from a first computer network to respective destination hosts, wherein each destination host is associated with a destination network, and wherein there is at least one path from the first computer network to each destination network, the method comprising the steps of

monitoring traffic flows from a first computer network to a plurality of respective destination networks;

generating an ordered list of destination networks based on a traffic flow statistic value associated with each destination network,

for each destination network in the ordered list, associating the routing peer(s) having reachability to the destination network;

wherein each routing peer has a cost model associated therewith, the cost model comprising at least one price tier including a tier capacity and a fill priority;

selecting all routing peers having a price tier associated with the highest fill priority and, for the selected routing peers, iteratively performing a load balancing cycle until either all destination networks have been assigned a routing peer or all routing peers have been assigned up to their respective tier capacities, the load balancing cycle comprising;

for a first routing peer;

selecting the first unassigned destination network to which the first routing peer has reachability and assigning the selected destination network to the first routing peer; and

setting a traffic flow weighting value to the traffic flow statistic value associated with the selected destination network;

for each subsequent routing peer;

selecting the first unassigned destination network to which the routing peer has reachability;

repeating the selecting step until the traffic flow statistic values associated with the selected destination network(s) aggregate beyond a threshold level derived from the traffic flow weighting value; and

assigning the selected destination network(s) to the routing peer;

selecting all routing peers having a price tier associated with the next highest fill priority and iteratively performing the load balancing cycle until either all destination networks have been assigned a routing peer or all routing peers have been assigned up to their respective tier capacities; and

repeating the above selecting step for all fill priorities.

31. A method facilitating the control of routing policy in a routing system operably connected to a computer network, the method comprising the steps of:

receiving Network Layer Reachability Information (NLRI) associated with a destination network from at least two routing peers, wherein the destination network is defined by a computer network address and a subnet mask;

associating a path including one of said routing peers as the next hop with a subnet of the destination network;

injecting the path to the subnet of the destination network into a routing system; and

removing the injected path from the routing system, if the routing peer in the injected path withdraws the route to the destination network.

32. The method of claim 31 wherein the associating step is conditioned upon the non-existence of a natural NLRI path to the subnet in the routing system.

33. The method of claim 31 wherein the injecting step is conditioned upon the non-existence of a natural NLRI path to the subnet in the routing system.

34. The method of claim 31, 32, or 33 further comprising the steps of

repeating the associating and injecting steps for all subnets included in the destination network.

35. The method of claim 31 further comprising the steps of

testing the performance of each path to a subnet of the destination network;

and wherein the path exhibiting the best performance is associated with the subnet in the associating step.

36. The method of claim 35 wherein the testing step comprises the steps of

testing each path to the subnet of the destination network relative to at least two performance metrics;

and

combining the performance metrics into a weighted aggregate score.

37. The method of claim 36 wherein the performance metrics are selected from the group consisting of:

1) response time,

     2) hop count,

     3) available bandwidth,

     4) jitter,

     5) throughput, and

     6) reliability.