Internet route deaggregation and route selection preferencing

• US 20050201302A1
• Filed: 03/18/2005
• Published: 09/15/2005
• Est. Priority Date: 06/14/2000
• Status: Active Grant

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: Wiltel Communications Group, Inc. (Lumen Technologies, Inc.)
• Inventors: Gaddis, Michael E., Hicks, Peter N., Barmann, David, Nunes, Steven T.
• Granted Patent: US 7,554,930 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/06 Deflection routing, e.g. hot-potato routing
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

A method and system for managing the routing of traffic within a network develops a topological address space map of the network to enable a “best route” selection process. The network is comprised of a backbone connected to a plurality of peering partners. Points on the network monitor traffic flows. A central facility analyzes the traffic flows and routes within the network and performs intelligent routing management. Intelligent routing management ensures that traffic is properly routed through preferred routes on the network, and avoids inefficient routing. Intelligent routing management also selects new routes to be injected into the network in order to further improve the accuracy of the address space map of the network. Intelligent routing management ensures that bandwidth is requested and delivered topologically closely to peering partner networks, and that traffic is carried by the backbone for long haul data distribution in both directions.

Claims

1. A method for modifying routing using a topological address space map of a system having a plurality of networks connected to a backbone via a plurality of entry points, the method comprising:

monitoring the entry points of a plurality of messages arriving from the plurality of networks;

correlating the plurality of message entry points with their associated message source address ranges to develop the topological address space map of the system; and

using the topological address space map to implement modified routing.

2. The method of claim 1, wherein using the topological address space map to implement modified routing further comprises:

subject to a determination that the amount of messages from a first source address range arriving from a first path exceeds a first threshold amount, preferencing all messages to a destination address within the first source address range to travel via the first path.

3. The method of claim 2, wherein using the topological address space map to implement modified routing further comprises:

subject to a determination that the first path has not been preferenced, and further subject to a determination that the amount of messages from the first source address range arriving from the first path exceeds a second threshold amount, deaggregating a published route associated with the first source address range.

4. The method of claim 3, wherein the first source address range is a group of addresses corresponding to the same Internet Protocol address and mask;

the first threshold is a preset percentage of the total amount of messages from a first source address range; and

wherein the second threshold is a preset percentage of the total amount of messages from a first source address range.

5. A method for performing traffic routing management in a network, the method comprising:

monitoring source address ranges for a plurality of signals;

monitoring arrival network connection points for the plurality of signals; and

developing a topological address space map of the network.

6. The method of claim 5, further comprising:

using the topological address space map to route a signal to a network connection point closest to a destination address range of the signal; and

reconciling differences between the topological address space map and existing routes in the network.

7. The method of claim 6, in which using the topological address space map further comprises:

preferencing a route table route that is not selected naturally according to a network routing protocol and is not prohibited according to a network configuration parameter, subject to a determination that the route exceeds a signal quantity threshold, wherein the network routing protocol is the Border Gateway Protocol, and wherein preferencing a route table route includes modifying the local preferences for the route and is preformed automatically, and further wherein the signal quantity threshold is a predetermined number of the total number of signals from the source address range corresponding to the route.

8. The method of claim 6, wherein using the topological address space map further comprises injecting automatically a new route within the source address range of a signal into the network by using a Border Gateway Protocol session from an external system.

9. The method of claim 5, wherein developing the topological address space map of the network further comprises:

collecting route entries from a route table on a router in the network;

compiling automatically signal traffic statistics entries on the monitored plurality of signals passing through the router in the network; and

correlating each signal traffic statistics entry with a route entry, wherein each signal traffic statistics entry comprises;

a measure of the quantity of signals corresponding to a source address range;

an Internet Protocol address;

a prefix length for the Internet Protocol address range; and

an associated route entry.

10. The method of claim 6, wherein the plurality of signals monitored includes:

a predetermined portion of set of signals sent within the network; and

a set of signals generated to fill in portions of the topological address space map of the network to provide substantially equal signal coverage of the network, wherein monitoring is performed automatically and automatically used to develop the topological address space map; and

wherein the process of using the topological address space map is performed automatically.

11. A computer program product for managing the routing of signals in a network, the computer program product comprising:

a computer readable medium that stores program code including;

program code that receives route entries from a route table in the network;

program code that receives Internet Protocol statistics data entries on signals flowing through one or more routers on the network, wherein each Internet Protocol statistics data entry includes a measure of the quantity of signals corresponding to a signal source address range;

program code that monitors source address ranges for a plurality of signals;

program code that monitors arrival network connection points for the plurality of signals;

program code that develops a topological address space map of the network using the route entries and Internet Protocol statistics data entries; and

program code that implements the topological address space map.

12. The computer program product of claim 11, further comprising:

program code that uses the topological address space map to route a signal to a network connection point topologically closest to a destination address range of the signal.

13. The computer program product of claim 12, wherein program code that uses the topological address space map further comprises:

program code that preferences a route table route that is not selected naturally according to a network routing protocol and is not prohibited according to a network configuration parameter, subject to a determination that the route exceeds a signal quantity threshold.

14. The computer program product of claim 12, wherein program code that uses the topological address space map further comprises:

program code that injects a new route within the source address range of a signal into the network.

15. The computer program product of claim 12, wherein program code that uses the topological address space map further comprises program code that reconciles differences between the topological address map and existing routes in the network.

16. The computer program product of claim 11, wherein program code that develops the topological address space map of the network further comprises:

program code that collects route entries from a route table on a router in the network; and

program code that compiles signal traffic statistics entries on the monitored plurality of signals passing through the router in the network, wherein each signal traffic statistics entry includes a measure of the quantity of signals corresponding to a source address range.

17. The computer program product of claim 16, further including program code that correlates each signal traffic statistics entry with a route entry.

18. The computer program product of claim 11, wherein program code that implements the topological address space map comprises program code that selects a preferred route.

19. The computer program product of claim 18, wherein the program code that selects the preferred route comprises:

program code that selects as the preferred route a route entry that is not selected naturally according to a network routing protocol and is not prohibited according to a network configuration parameter, subject to a determination that the route exceeds a signal quantity threshold.

20. The computer program product of claim 18, wherein program code that implements the topological address space map further comprises program code that selects a deaggregation route, wherein the program code that selects the deaggregation route comprises:

program code that selects as the deaggregation route a route corresponding to an Internet Protocol statistics data entry, wherein the route is more specific than the route table route currently announced to the network.