Dynamic routing through a content distribution network

• US 7,603,481 B2
• Filed: 07/15/2003
• Issued: 10/13/2009
• Est. Priority Date: 10/31/2002
• Status: Expired due to Fees

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Carter, Stephen R
• Primary Examiner(s): Lin; Kenny S
• Assistant Examiner(s): DOAN, DUYEN MY
• Application Number:
  US10/619,886
• Publication Number:
  US 20040088431A1
• Time in Patent Office: 2,282 Days
• Field of Search: 709239-240, 709/243, 370230-2301, 370/231
• US Class Current: 709/240
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/308 Route determination based on user's profile, e.g. premium users
• CPC Class Codes: H04L 47/20 Traffic policing

Abstract

Methods, systems, and data structures are provided for dynamically routing a data packet through a Content Distribution Network (CDN). A routing table includes a desired path for a data packet and one or more alternative paths. Each path includes links and each link connects pairs of an entry node, intermediate nodes, and a destination node together. Each link also includes policies that are processed by the entry node and the intermediate nodes. If conditions of currently available nodes (local nodes) trigger one or more of the policies, then any processing node dynamically reorders a number of the currently available nodes within the routing table. After the processing, the data packet is routed to a next or preferred currently available node within the routing table.

Claims

1. A method for dynamically routing a data packet through a Content Distribution Network (CDN), comprising:

receiving a routing table for a CDN and a data packet, wherein the routing table represents a desired path and alternative paths through the CDN, and wherein each path represents links between an entry node, intermediate nodes, and a destination node;

evaluating policies associated with currently available links for currently available paths at the entry node and at each of the intermediate nodes, when the data packet is received on the entry node and when the data packet is received on each of the intermediate nodes, wherein the policies are executable statements processed at each of the intermediate nodes, the policies are executed by each of the intermediate nodes when the data packet is received at each of those intermediate nodes, and the policies are embedded in the routing table;

reordering currently available intermediate nodes within the routing table for the currently available links, when the policies are triggered by current conditions of the currently available intermediate nodes; and

routing the data packet to a next available intermediate node of the routing table, wherein the next available intermediate node is one of the currently available intermediate nodes, and wherein at least one intermediate node selects the next available intermediate node that is associated with one of the alternative paths;

wherein the evaluating further comprises comparing policy priority metrics to the currently available intermediate nodes'"'"' data traffic for determining whether to trigger actions associated with the policy priority metrics;

wherein processing one of the actions for suspending existing traffic associated with one of the currently available nodes in order to accommodate the routing of the data packet based on the policy priority metrics associated with the data packet.

2. The method of claim 1 further comprising iterating the processing for evaluating, reordering, and routing at each intermediate node that receives the data packet until the data packet reaches the destination node.

3. The method of claim 1 wherein the evaluating further comprises comparing policy threshold metrics to the currently available intermediate nodes'"'"' processing load levels for determining whether to trigger actions associated with the policy threshold metrics.

4. The method of claim 3 further comprising, processing one of the actions to promote or demote one or more of the currently available intermediate nodes within the routing table.

5. The method of claim 1 wherein the evaluating further includes comparing policy bandwidth utilization metrics against existing bandwidth utilization levels associated with the currently available intermediate nodes for determining whether to trigger bandwidth utilization actions in order to load balance bandwidth use within the CDN.

6. A method for dynamically a data packet routing through a Content Distribution Network (CDN), comprising:

associating policies with a routing table, wherein the routing table includes a desired path and one or more alternative paths, and wherein each path includes links between an entry node, intermediate nodes, and a destination node;

evaluating, at a receiving node identified in the routing table, the policies when the receiving node acquires a data packet, and wherein the receiving node is one of the intermediate nodes, and wherein the policies are executable statements processed at of the receiving node, the policies are executed by each of the intermediate nodes when the data packet is received at each of those intermediate nodes, and the policies are embedded in the routing table; and

reordering, at the receiving node, next available intermediate nodes within the routing table when the policies are triggered to change routing from the desired path to one of the alternative path;

routing the data packet to a next available intermediate node of the routing table, wherein the next available intermediate node is one of the currently available intermediate nodes, and wherein at least one intermediate node selects the next available intermediate node that is associated with one of the alternative paths;

wherein the evaluating further comprises comparing policy priority metrics to the currently available intermediate nodes'"'"' data traffic for determining whether to trigger actions associated with the policy priority metrics;

wherein processing one of the actions for suspending existing traffic associated with one of the currently available nodes in order to accommodate the routing of the data packet based on the policy priority metrics associated with the data packet.

7. The method of claim 6 further comprising, identifying the entry node as an initial receiving node.

8. The method of claim 7 further comprising, notifying, by the initial receiving node, remaining intermediate nodes within the routing table for any reordering of the routing table that occurs.

9. The method of claim 6 wherein the evaluating further comprises using policies associated with at least one of next intermediate node bandwidth utilization levels, next intermediate node utilization levels, and next intermediate node traffic priority assignments.

10. The method of claim 6 wherein the associating further comprises assigning the policies to the links established between the nodes and forming the desired path and the one or more alternative paths.

11. The method of claim 6 further comprising preventing previously demoted intermediate nodes from being promoted at the receiving node when reordering of the routing table occurs.

12. The method of claim 11 further comprising, using a formal notation to update the routing table or the policies in order to identify the previously demoted intermediate nodes.