Network routing of endpoints to content based on content swarms

• US 9,407,693 B2
• Filed: 10/03/2007
• Issued: 08/02/2016
• Est. Priority Date: 10/03/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Singhal, Sandeep Kishan, Key, Peter Bernard, Zhang, Ming, Shen, Guobin, Karagiannis, Thomas, Ganesh, Ayalvadi Jagannathan
• Primary Examiner(s): SISON, JUNE Y
• Application Number:
  US11/866,811
• Publication Number:
  US 20090092124A1
• Time in Patent Office: 3,226 Days
• Field of Search: 709/226
• US Class Current: 1/1
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053
• CPC Class Codes: H04L 67/1072 Discovery involving ranked list compilation of candidate peers
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

Using location-independent names to identify content, a service for mapping endpoint requests to requested content. Content requested by an endpoint of the network is mapped to a dynamic “swarm” of server, peer, or other endpoints capable of supporting the content download. Content names are mapped to a dynamically generated content swarm, presenting a current set of hosts, which can provide the requested content. Optionally, varying degrees of explicit visibility into routing paths and the performance tradeoffs between those routing paths is supported. Based on a set of class of service parameters for a given request for content, a host can initiate route selection based on class of service parameters, predicated on routing metrics maintained by the network by cooperating endpoints and/or network routers.

Claims

1. A system comprising:

one or more processors;

memory communicably coupled to the one or more processors, the memory comprises;

substantially up to date content mapping information, independent of a type of content, which maps each unique content identifier corresponding to a content item of a plurality of unique content identifiers corresponding to a plurality of content items to a set of nodes of a network that each includes the content item;

substantially up to date end-to-end routing information for routes between node pairs of the nodes of the network, the end-to-end routing information comprising one or more routing characteristics; and

a lookup service module which, when executed by the one or more processors and in response to a request specifying a particular content item and one or more classes of service parameters;

determines a plurality of nodes of the network that satisfy the request based on the content mapping information, a determination of the plurality of nodes of the network being independent of a location of each node of the plurality of nodes of the network; and

selects at least one route associated with the plurality of nodes based at least on the end-to-end routing information and the one or more class of service parameters.

2. The system according to claim 1, wherein the substantially up to date content mapping information is stored on a distributed data store.

3. The system according to claim 2, wherein the substantially up to date content mapping information is stored on a data store and implemented with distributed hash tables (DHTs).

4. The system according to claim 1, wherein the plurality of nodes of the network include any one or more of source hosts for the content item, active clients including the content item or intermediate hosts that have cached the content item.

5. The system according to claim 1, wherein the one or more routing characteristics comprise any one or more of bandwidth, loss rate and latency of routes between node pairs of the nodes of the network.

6. The system according to claim 1, wherein the substantially up to date end-to-end routing information is stored on a data store and implemented with distributed hash tables (DHTs).

19. The system according to claim 1, wherein the determination of the plurality of nodes comprises computing routes between node pairs based at least in part on the one or more class of service parameters and a maximum number of routes computed between each of the node pairs.

7. A method for proactively determining optimal service endpoints for providing content in a network, comprising:

based on a request for a content stream of interest including a unique content identifier that is independent of location of the content stream, receiving, by a requesting endpoint, information representing a set of candidate endpoints from a network service that each includes the content stream of interest, wherein the set of candidate endpoints is provided to the requesting endpoint independent of respective candidate endpoint locations;

based on at least one predetermined criterion associated with the request and information retrieved from a data store comprising substantially up to date end-to-end routing information for routes between the requesting endpoint and the endpoints of the candidate endpoints of the network service, selecting, by the requesting endpoint, at least one candidate endpoint of the set of candidate endpoints for provision of a service relating to the content stream of interest, the end-to-end routing information comprising one or more routing characteristics, the one or more routing characteristics of the selected at least one candidate endpoint comprises a latency value, wherein the at least one predetermined criterion comprises a latency performance parameter; and

based on an increase in the latency value associated with the selected at least one candidate endpoint that results in failing to meet the latency performance parameter, switching to at least a second candidate endpoint of the set of candidate endpoints for provision of the service relating to the content stream of interest in response to determining that a latency value associated with the at least the second candidate endpoint satisfies the latency performance parameter.

8. The method according to claim 7, further comprising:

receiving routing quality information that facilitates the selecting of the at least one candidate endpoint based on measurements of the quality of routes to the at least one candidate endpoint.

9. The method according to claim 8, wherein the one or more routing characteristics further comprise one or more of bandwidth, network distance, cost or loss rate metrics, further comprising:

selecting one or more optimal routes to the at least one candidate endpoint from the requesting endpoint based on one or more of bandwidth, the latency value, network distance, cost or loss rate metrics received with respect to one or more routes between the requesting endpoint and the at least one candidate endpoint.

10. The method of claim 8, further comprising:

determining, based on the quality of routes to the at least one candidate endpoint, whether a quality of service requirement is met for an application or service associated with the request.

11. The method of claim 7, wherein the provision of the service relating to the content stream of interest includes enabling a downloading or streaming operation by the requesting endpoint.

12. The method of claim 7, wherein the provision of the service relating to the content stream of interest includes enabling a real-time rendering operation by the requesting endpoint.

13. A method for determining optimal routes to optimal service endpoints for providing service with respect to one or more specified items of content in a network, comprising:

receiving, in response to a content stream of interest request by a requesting endpoint of a network, first information including unique endpoint identifier information representing a set of candidate endpoints from a network service, the unique endpoint identifier information being independent of a location of each of the candidate endpoints, each of the candidate endpoints capable of providing a service with respect to the content stream of interest, each unique endpoint identifier assigned to each candidate endpoint at the time the candidate endpoint joined the network;

receiving, by the requesting endpoint, second information representing route quality information concerning at least one characteristic of at least one endpoint to endpoint route between the requesting endpoint and the set of candidate endpoints, the second information retrieved from a data store comprising substantially up to date end-to-end routing information for routes between endpoints of the endpoints of the network, the end-to-end routing information comprising at least bandwidth information; and

based on an analysis of the second information representing route quality information and a class of service parameter associated with the content stream of interest, connecting to a subset of the set of candidate endpoints via a specific one or more of the at least one endpoint to endpoint route.

14. The method of claim 13, wherein the receiving of the second information includes receiving information about the at least one endpoint to endpoint route from a plurality of network routers tracking network state.

15. The method of claim 13, wherein the end-to-end routing information further comprises latency, jitter, or reliability of the at least one endpoint to endpoint route.

16. The method of claim 15, wherein the class of service parameter comprises a latency class of service need, wherein the connecting to the subset of the set of candidate endpoints is further based on the latency associated with the end-to-end routing information of the subset of the set of candidate endpoints and the latency class of service need.

17. The method of claim 13, further comprising:

monitoring the specific one or more of the at least one endpoint to endpoint route to determine actual quality of service information associated with the at least one endpoint to endpoint route.

18. The method of claim 13, wherein the content stream of interest comprises content where a unique content identifier identifying content independent of location is unknown prior to a request for the content, wherein the unique content identifier is determined based at least in part on part of the content, a property associated with the content, or both.