X-CDNSP-Times	“X-” is to show this is a non standard header
:	Colon & space (separator)
{version}	The version of this protocol - currently 1
{ip}	The IP address of the machine tested
{region}	The region the IP address came from (e.g. the number
	after the y flag)
{time}	The time in milliseconds for the OPTIONS response to
	come back

Preferably, the header is passed out-of-band to an appropriate CDNSP process that is used to generate one or more DNS request routing maps, e.g.,nameserver map312. That process may also receive the DNS SRV response and the requesting IP address of the client player that initiated the query. Such “feedback” provides significant value to users of the system (both SRV-enabled clients and other clients) by enhancing the accuracy of subsequent region or machine assignments when later requests are resolved against the modifiedmap312. In particular, one of ordinary skill in the art will appreciate that the best analysis of a given routing decision with respect to a given client is made by that client, as opposed to some proxy for that client (e.g., the client's local name server). The header illustrated above may include information that describes the specific region/machine that the given client selected as the “best” and the data underlying that decision. This information can then be used to bias the request routing decisions in themap312 for future requests made by this or other clients. As more clients use the system and provide such feedback, the request routing provided by the map becomes more and more accurate as, in effect, subsequent decisions can be based on the additional intelligence about how well the request routing was performed for the earlier requests.

As noted above, typically the fastest responding server to the OPTIONS test will be the best server to stream the requested data to the user. This also gives the system a chance to re-assign the stream, e.g., via a redirect message. If the fastest responding server is indeed the correct server to stream from, then the X-CDNSP-Times header can be ignored by the server. Another function provided by the present invention is the ability of the client player (namely, the code running in that player) to identify a “better” source for a stream being received and to switch to that source “on the fly,” i.e., while the stream is being received and rendered on the client. Thedecision process308 is used to determine whether the player should switch servers mid-stream. Because it is likely there will be some cost to switching (e.g., perhaps a short interruption in service), a client should only switch servers if it is not getting an acceptable stream from the first server. Thedecision process308 makes a decision regarding whether the stream being received is “acceptable,” e.g., a stream that is not currently being thinned by the server, or some other metric. As used herein, “acceptable” does not necessarily mean acceptable quality. It can also mean acceptable from a stream management point of view. For example, the client could be actually told by the server that the stream is unacceptable, e.g., if the server knows it is to be taken down soon (for a software update or other servicing). It could also declare a stream unacceptable if new advertising or newer content (e.g., a fast breaking news story) becomes available. These examples, of course, are merely representative.

If the decision process determines that another server is a better source than a current source, control is passed to thestream switch process310, which is the process that makes the actual switch from one server to another. The particular technique used for switching from a first server to a second server typically is media type-dependent and any convenient technique may be used. Thus, for example, assume a stream being received has a length of 5:00 minutes and the client player is processing the stream from a first server at an offset of 2:35 when a decision is made to change to a second server. Thestream switch process310 may then cause the second server to begin sending the stream at an offset of 2:45 and, at the same time, send appropriate instructions to terminate the stream from the first server. The stream switch process thus has the capability of picking the server it likes “least” and instructing that server to cease transmission at a given point. In another alternative, once thestream switch process310 decides to make a switch, it creates an internal buffer and causes that buffer to be filled with advance portions of the stream (e.g., by instructing the first server to deliver packets faster than those packets can be rendered or by instructing the player to slow down the rendering process). Theswitch process310 then causes the first server to cease transmission and request that the new server begin the stream at a given offset. At this point, the pre-cached data in the buffer is rendered until the given offset is reached and the new data is received. As appropriate, the stream switch process includes the capability to match data packets from first and second servers to enable a substantially seamless switch to the new stream source. Voice streams can be synched before a switch by snipping out and putting in minute bits of silence between words. Of course, the above are merely exemplary as any convenient switching technique may be implemented. (DAVID, you can describe a few others if appropriate)

Thus, as summarized in the flowchart ofFIG. 4, the client player provisioned according to the invention performs a query to a nameserver against a CDNSP network map. This isstep400. The query is made asking for a particular service (e.g., RTSP) via a particular protocol (TCP) in a particular domain. In response, atstep402, the nameserver returns a set of one or more tokens, with each token defining a machine or, in the preferred embodiment, a group of machines, from which the player should seek to obtain the stream. The player may then optionally perform one or more tests to determine which of a set of servers provides a best quality of service for the stream. This isstep404. That server is then used to retrieve the stream, which isstep406. Atstep408, a test is performed to determine whether the client player is still receiving the stream. If not, the routine ends. If, however, the client player is still receiving the stream, the routine continues atstep410 with the client player code repeating the DNS SRV query during playback to determine whether there is a better source for the stream. The “period” over which the query is repeated is variable and is dependent on the bandwidth available between the client and the network. For a live stream, a query/minute may be a desirable frequency. A shorter frequency (e.g., every few seconds) may be desirable for a broadband connection). Atstep412, a test is performed to determine whether the client player is receiving acceptable service from the existing source. If so, the routine returns to step408 and repeats the process at a given frequency. If the outcome of the test atstep412 indicates that the stream source is unacceptable, the routine continues atstep414 to initiate the switch to the “better” stream source. As noted above, preferably this switch is carried out “on the fly” as appropriate to maintain and/or enhance the quality of service. Thereafter, atstep416, the client player continues to obtain the remainder of the stream from the new source. Of course, the “best” source may be changed again if the circumstances warrant. In a preferred embodiment, and as indicated atstep418, the client player publishes data back to the CDNSP identifying the tests it ran to determine the best server. Such data may then be used to augment the network map that is used for subsequent request routing determinations.

The following is an illustrative embodiment for an Apple QuickTime media player.


Construction of a SRV Query
A preferred SRV construction method is set forth below.
_a{Serial Number}-{IP address}._tcp.srv.kamai.net.

_a{Serial	This is the serial number field (including the “a”) from a
Number}	CDNSP-specific hostname (a hostname pointing to the
	CDN) with an underscore prepended. A serial number
	identifies a virtual content bucket on a CDN content
	server that may host the content
-	Hyphen (separator)
{IP Address}	The IP address of the player written as a four byte
	unsigned integer in network byte order
.	Dot (separator)
_tcp	Required by RFC 2782 - not applicable here
.	Dot (separator)
Srv	Specifies to the CDNSP DNS system to serve this request
	from a different set of servers
.	Dot (separator)
Kamai.net	Any CDNSP DNS domain name, with this particular
	name being merely representative

Note the use of the underscore (“_”) character in the full SRV name. This is not an improper syntax as underscores are only illegal in hostnames, and an SRV query is not considered a hostname. Although not required, preferably there are several SRV servers associated with the “srv.kamai.net” domain to spread out the load and ensure there is no single point of failure. The passing of the player's IP address is optional but desirable, and this operation may be set as a configuration option in the player. The SRV server must therefore be able to handle responses with and without the IP address supplied, although preferably the address is used. If the IP address is not passed, then the SRV server should treat the address of querying name server as the IP address of the client.

The SRV nameserver that receives this query then has several important pieces of information:

1. The IP address of the player (optional, but desirable);

2. The IP address of the player's nameserver; and

3. The type of media being requested (e.g. “q”=QuickTime).

Based on this information, and in a preferred embodiment, the SRV server then performs the following steps

- 1. Calculates a best CDNSP region to direct the player towards using the three (3) pieces of information given above, in combination with a network map; and
- 2. Returns a reply to the client comprising an identification of this region, as well as several other regions that are possible contenders if the first region does not work out well.

As an example, assume that a user at IP address 17.37.117.209 is requesting a stream from the host a40.q.kamai.net. The SRV query might then be of the following representative format:

_a40-287667665._tcp.srv.kamai.net

Based on the then-current network map, assume that the best region is region5, followed by region3, and then region2 and region7 at equal ability. In such case, the SRV name server will return the following representative data (with the particular references being merely exemplary):


Ranking	Weighting	Port to use	Hostname

1	0	554	a40.y5q.kamai.net.
2	0	554	a40.y3q.kamai.net.
3	0	554	a40.y2q.kamai.net.
3	0	554	a40.y7q.kamai.net.

SRV Field Meanings

- Ranking Ranking order, with low numbers tried before high
- Weighting N/A
- Port The port to which the connection should be mae. For an Apple QuickTime player, for example, this will always be 554. This value may be useful at some point if a different set of servers (on a different port) are set up
- Hostname The fully-qualified domain name of the server to contact. The y{x}q entry in the Hostname field is an instruction to a CDNSP top-level nameserver to return a set of low-level nameservers in the specified region. This will result in a the best server in that specific region being returned when the name is looked up by the player.
  Behavior of the Player after Receiving a SRV Response

Once the client (and, in particular, the client player) receives this list of servers, it contacts each one and requests an “OPTIONS” from each one. The response from each server is timed, and the “fastest” server may be selected as the “best” server from which to proceed. Once the fastest responding server is selected, the client connects to it and sends the usual DESCRIBE command. In addition to this, the X-CDNSP-Times: header preferably is added containing the timings of the OPTIONS experiment.

After the Connection is Established

At this point, the client is speaking to the best server. As noted above, the client player may selectively switch from one stream to another, either seamlessly or with as minimal of a break as possible. With that ability, if a client does a SRV lookup periodically, it can learn which set of servers is currently best and switch to a server that is better than the one it is currently receiving the stream from.

In combination with the inventive method, a given server itself can elect at any time to send the client to a better place via the RTSP REDIRECT command. This command allows for a redirect to happen at a particular time count, which should allow the player to resume the stream where it left off elsewhere without missing any data.

As noted above, when the client player sends a query to the nameserver, that server performs a lookup against a map of current Internet traffic conditions. The CDNSP generates the map in any convenient manner. The following is a representative technique, which should not be taken by way of limitation. To prepare for generating this map, mapping agents (e.g., one per CDN server region) may collect the following information: (a) IP blocks (a list of IP address blocks currently in use in the Internet), (b) load (per-IP block measurements of the amount of web load currently being handled by the CDN, (c) communication costs (e.g., a table listing the measured communication cost for each {IP block, CDN server region} pair, and (d) capacity (e.g., an aggregate server and network capacity of each CDN server region).

In particular, a combination of different methods may be used to put together the list of IP blocks representing all of the leaf networks (e.g., endpoint LAN's on the global Internet): BGP peering, harvesting information from network registration databases (e.g., RIPE, APNIC and ARIN), and random traceroutes into very large blocks (e.g., UUNET). The load on the CDN generated by each IP block may be determined by gathering and aggregating measurements from the CDN content servers. One or more different communication costs may be used to determine the cost of communication between an IP block and a CDN server region: network health of server region (e.g., a binary metric indicating that the region is up or down), ASPATH length between the block and the server region (e.g., as supplied by BGP), round trip time (RTT) between the region's mapping agent and a given point in the IP block, packet loss rate between the region's mapping agent and the given point in the IP block, geographic distance, and perhaps others. These metrics may be combined into a single cost metric for each IP block, server region pair, with the priority, or weighting, of each individual metric set to be proportional to its position on the list. Two types of capacity measurement are typically made: total server capacity in each region and physical network capacity in each region. The server capacity is determined from the number of servers currently up in a region. Physical network capacity is determined with packet pair measurements. Region capacity may be calculated as a given function (e.g., the minimum) of these two measurements.

The map associates each IP block to an optimal CDN server region. One technique for generating the map involves identifying a number of candidate regions for each IP block (e.g., based on the {IP block, server region} communication costs), generating a bipartite graph using all of the measured and collected network information (e.g., with one side of the graph representing each of the IP blocks and the other side representing CDN server regions), and then running a min-cost flow algorithm on the graph. Each IP block node is labeled with its measured load, which is treated as the “flow” coming from that node. Running the algorithm results in an optimal assignment of IP block load to server regions. This assignment is the map, which is generated periodically by the CDNSP and then delivered to the nameservers that respond to the client player queries.

Many of the functions have been described and illustrated above as discrete programs. One of ordinary skill will appreciate that any given function, alternatively, may comprise part of another program. Thus, any reference herein to a program should be broadly construed to refer to a program, a process, an execution thread, or other such programming construct. Generalizing, each function described above may be implemented as computer code, namely, as a set of computer instructions, for performing the functionality described via execution of that code using conventional means, e.g., a processor, a computer, a machine, a system, or other apparatus.

While the present invention has been described in the context of an RTSP stream-based protocol, one of ordinary skill in the art will appreciate that the functions and features described may also be used for other types of content. A particular example would be HTTP over TCP/IP, wherein the given content of interest is a large HTTP object. In such case, the various processes described above may be modified as appropriate to implement the described functionality. Thus, for example, the stream switch process would be modified to incorporate appropriate routines for handling the file switch. As in the stream-based embodiment, the code may be built into a browser, a plug-in, an applet, or other codebase.