Heavy load packet-switched routing

• US 7,706,280 B2
• Filed: 08/01/2005
• Issued: 04/27/2010
• Est. Priority Date: 08/01/2005
• Status: Expired due to Fees

• Current Assignee: Limelight Networks, Inc.
• Original Assignee: Limelight Networks, Inc.
• Inventors: Raciborski, Nathan F., Gordon, Michael M.
• Primary Examiner(s): Ton; Dang T
• Assistant Examiner(s): Morlan; Robert M
• Application Number:
  US11/195,247
• Publication Number:
  US 20070025327A1
• Time in Patent Office: 1,730 Days
• Field of Search: 370/351, 370/230, 370/230.1, 370/232, 370/233, 370/234, 370/237, 370/238, 370/238.1, 370/392, 370/395.21, 370/411
• US Class Current: 370/237
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1012 based on compliance of requirements or conditions with available server resources
• CPC Class Codes: H04L 67/1017 based on a round robin mechanism
• CPC Class Codes: H04L 67/1019 Random or heuristic server selection
• CPC Class Codes: H04L 67/1021 based on client or server locations
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements

Abstract

According to the invention, a content delivery network (CDN) for delivering content objects over the Internet is disclosed. The CDN includes a point of presence (POP), a content object request interface, and a routing function. At least one POP is coupled to a plurality of full-route networks. The content object request interface receives requests for content objects for delivery to a number of end users using a plurality of terminal networks. The routing function that routes content objects in at least two modes, where a first mode routes content objects based upon a first route path chosen based upon delivery efficiency, and a second mode routes at least some content objects using a second route path when at least of a portion of the first route path reaches a level of use. The first and second route paths egress to different full-route networks.

Claims

1. A content delivery network (CDN) for delivering content objects over the Internet, the CDN comprising:

a point of presence (POP), wherein;

the POP is coupled to a plurality of full-route networks,

each of the plurality of full-route networks delivering content objects to a plurality of terminal networks,

the plurality of terminal networks comprise a first terminal network, and

the plurality of terminal networks are coupled to a plurality of end users;

a content object request interface that receives requests for content objects for delivery to the plurality of end users using the plurality of terminal networks; and

a routing function that routes content objects in at least two modes, wherein;

a first mode routes content objects based upon a first route path from the POP to the first terminal network,

the first route path is chosen based upon efficiency based upon an efficiency algorithm,

a second mode routes at least some content objects using a second route path when at least a portion of the first route path reaches a level of use,

the second mode and the first mode are both simultaneously used to route content objects after the portion of the first route path exceeds the level of use,

the second route path is chosen without considering delivery efficiency as defined by the efficiency algorithm,

use of the second route path in the second mode is less efficient than use the first route path in the second mode according to the efficiency algorithm, and

the first and second route paths egress to different full-route networks.

2. The CDN for delivering content objects over the Internet as recited in claim 1, wherein egress from the POP for the second route path starts with a full-route network that is not directly coupled to the first terminal network, whereby another full-route network is used to reach the first terminal network.

3. The CDN for delivering content objects over the Internet as recited in claim 1, wherein the POP is one of a plurality of POPs, the CDN further comprising a backbone coupled to at least two of the plurality of POPs.

4. The CDN for delivering content objects over the Internet as recited in claim 1, wherein the second route path and the first route path pass through the same full-route network on the way to the first terminal network.

5. The CDN for delivering content objects over the Internet as recited in claim 1, wherein the CDN is a captive CDN integral to a content originator.

6. The CDN for delivering content objects over the Internet as recited in claim 1, wherein a full-route network does not pass traffic to another full-route network when the full-route network is directly coupled to the first terminal network.

7. The CDN for delivering content objects over the Internet as recited in claim 1, wherein the POP is one of a plurality of POPs, which are geographically distributed.

8. The CDN for delivering content objects over the Internet as recited in claim 1, wherein the POP stores at least one of the content objects.

9. A method for delivering content objects over the Internet with a distribution system, the method comprising steps of:

receiving a first request to deliver a first content object to a first end user, wherein;

the distribution system comprises a point of presence (POP),

the POP is coupled to a plurality of full-route networks,

the plurality of full-route networks comprise a first full-route network and a second full-route network,

each of the plurality of full-route networks delivering content objects to a plurality of terminal networks,

the plurality of terminal networks comprise a first terminal network,

the first terminal network is coupled to a plurality of end users,

the plurality of end users comprise the first end user and a second end user,

the first end user and the second end user subscribe to the terminal network for Internet service,

the POP is coupled to the first terminal network, and

the first full-route network and the second full-route network are coupled to the first terminal network;

determining that the first end user is associated with the first terminal network;

determining that a first egress point between the POP and the first full-route network is more efficient a route than using the second full-route network;

delivering the first content object with the first egress point;

receiving a second request to deliver a second content object to the second end user,

determining that the first egress point reaches a level of utilization;

determining that the second end user is associated with the first terminal network; and

delivering the second content object with a second egress point between the POP and the second full-route network, wherein;

delivery with the second egress point is triggered by reaching the level of utilization,

delivering the second content object begins while still delivering the first content object, and

the second egress point is chosen without considering routing efficiency of starting delivery with the second egress point.

10. The method for delivering content objects over the Internet with the distribution system as recited in claim 9, wherein the delivering the second content object step comprises a step of sending the second content object between the first full-route network and the second full-route network to reach the first terminal network.

11. The method for delivering content objects over the Internet with the distribution system as recited in claim 9, wherein the second egress point is chosen in at least one of the following ways:

in round-robin fashion from egress points,

randomly from egress points, or

sequentially from egress points.

12. The method for delivering content objects over the Internet with the distribution system as recited in claim 9, wherein:

the first egress point is in a first geographic location,

the second egress point is in a second geographic location, and

the first geographic location is different from the second geographic location.

13. A method for delivering content objects over the Internet with a distribution system, the method comprising steps of:

receiving a first request to deliver a first content object to a first end user, wherein;

the distribution system comprises a point of presence (POP),

the POP is coupled to a plurality of full-route networks,

the plurality of full-route networks comprise a first full-route network and a second full-route network,

each of the plurality of full-route networks delivering content objects to a plurality of terminal networks,

the plurality of terminal networks comprise a first terminal network,

the first terminal network is coupled to a plurality of end users,

the plurality of end users comprise the first end user, a second end user and a third end user,

the first end user, the second end user and the third end user subscribe to the first terminal network for Internet service,

the POP is coupled to the first terminal network, and

the plurality of full-route networks are coupled to the first terminal network;

determining that the first end user is associated with the first terminal network;

delivering the first content object with a first egress point between the POP and the first terminal network;

receiving a second request to deliver a second content object to the second end user,

determining that the first egress point reaches a first level of utilization;

determining that the second end user is associated with the first terminal network;

determining that a second egress point between the POP and, the first full-route network is more efficient a route than using a second egress point between the POP and the second full-route network;

delivering the second content object with the second egress point, wherein delivery with the second egress point is triggered by reaching the first level of utilization;

receiving a third request to deliver a third content object to the third end user,

determining that the second egress point reaches a second level of utilization determining that the third end user is associated with the first terminal network; and

delivering the third content object with a third egress point between the POP and the second full-route network, wherein;

delivery with the third egress point is triggered by reaching the second level of utilization,

delivering the third content object begins while still delivering the second content object, and

the third egress point is chosen without considering routing efficiency of starting delivery with the third egress point.

14. The method for delivering content objects over the Internet with the distribution system as recited in claim 13, wherein each of the plurality of full-route networks and the plurality of terminal networks are autonomous systems.

15. The method for delivering content objects over the Internet with the distribution system as recited in claim 13, wherein delivery of content objects after reaching the second level of utilization are randomly distributed among the other full-route networks.

16. The method for delivering content objects over the Internet with the distribution system as recited in claim 13, wherein delivery of content objects after reaching the second level of utilization are distributed among the plurality of full-route networks, excluding the first full-route network, according to a sequential algorithm.

17. The method for delivering content objects over the Internet with the distribution system as recited in claim 13, wherein delivery of content objects after reaching the second level of utilization are distributed among the plurality of full-route networks, excluding the first full-route network, according to a weighted algorithm.

18. The method for delivering content objects over the Internet with the distribution system as recited in claim 17, wherein the weighted algorithm is weighted by at least one of bandwidth cost, latency, packet loss, or maximum bandwidth.

19. The method for delivering content objects over the Internet with the distribution system as recited in claim 13, wherein at least one of the first or second level of utilization is a percentage of a capacity of the first or second egress point.

20. The method for delivering content objects over the Internet with the distribution system as recited in claim 13, wherein the second level of utilization is defined by a packet loss rate for the second egress point.

21. The method for delivering content objects over the Internet with the distribution system as recited in claim 13, wherein:

the first egress point has lower latency than the second egress point, and

the second egress point has lower latency than the third egress point.

22. The method for delivering content objects over the Internet with the distribution system as recited in claim 13, wherein:

the first egress point has lower cost to the distribution system than the second egress point, and

the second egress point has lower cost to the distribution system than the third egress point.

23. The method for delivering content objects over the Internet with the distribution system as recited in claim 13, wherein the first, second and third content objects are duplicates of each other.

24. The method for delivering content objects over the Internet with the distribution system as recited in claim 13, wherein the content object is a whole file or a whole stream.