Abstract:
Techniques are described for sharing content among peers. Locality domains are treated as first order network units. Content is located at the level of a locality domain using a hierarchical DHT in which nodes correspond to locality domains. A peer searches for a given piece of content in a proximity guided manner and terminates at the earliest locality domain (in the hierarchy) which has the content. Locality domains are organized into hierarchical clusters based on their proximity.

Description:
BACKGROUND 
       [0001]    Computers often need to obtain, via a network, resources such as web pages, software packages, binary media, documents, etc. Client computers, for example, may obtain such resources directly from servers. In a complex network such as a global enterprise with disperse subnets or campuses communicating via relatively slow WAN links, transmitting resources from distant servers to clients separated by a WAN link can tax the bandwidth of a WAN link. Peer-to-peer resource sharing has been used to reduce inter-subnet traffic by allowing peers to exchange resources directly. In a peer-to-peer resource sharing network, peer computers that acquire a resource may share the resource with other peer computers; a computer needing a resource may determine that a copy of the resource is available at a computer (peer) other than the server where the resource is generally available. In such a case, the computer may obtain the resource from the peer computer. 
         [0002]    While many peer-to-peer resource sharing schemes have been used, there is a need for a peer-to-peer resource sharing scheme that may be maintained with little overhead and may allow peers to search for resources first from nearby or proximate peers before searching more distant or less proximate peers. Techniques related to proximity-guided peer resource discovery are described below. 
       SUMMARY 
       [0003]    The following summary is included only to introduce some concepts discussed in the Detailed Description below. This summary is not comprehensive and is not intended to delineate the scope of the claimed subject matter, which is set forth by the claims presented at the end. 
         [0004]    Techniques are described for sharing content among peers. Locality domains or subnets are treated as first order network units. Content is located at the level of a locality domain using a hierarchical distributed hash table (DHT) in which nodes correspond to locality domains. A peer searches for a given piece of content in a proximity guided manner and terminates at the earliest locality domain (in the hierarchy) which has the content. Locality domains are organized into hierarchical clusters based on their proximity. 
         [0005]    Many of the attendant features will be explained below with reference to the following detailed description considered in connection with the accompanying drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0006]    The present description will be better understood from the following detailed description read in light of the accompanying drawings, wherein like reference numerals are used to designate like parts in the accompanying description. 
           [0007]      FIG. 1  shows a portion of a typical enterprise network. 
           [0008]      FIG. 2  shows an example of a peer-to-peer resource sharing framework. 
           [0009]      FIG. 3  shows an example of how a peer-to-peer resource sharing network may be integrated with higher-level applications. 
           [0010]      FIG. 4  shows a scheme for structuring a peer-to-peer network. 
           [0011]      FIG. 5  shows how a physical network may be represented as a hierarchical data structure. 
           [0012]      FIG. 6  shows a hierarchical representation where subnets are represented as first-order elements. 
           [0013]      FIG. 7  shows a peer configured for proximity-guided resource discovery. 
           [0014]      FIG. 8  shows an example of a proximity-guided search of a hierarchy of subnets. 
           [0015]      FIG. 9  shows various processes that may be performed by a peer. 
           [0016]      FIG. 10  shows an example computing device. 
       
    
    
     DETAILED DESCRIPTION 
     Overview  
       [0017]    Embodiments discussed below relate to proximity guided resource discovery in which subnets of a network are represented as first-order entities having identifiers in a same identifier space as identifiers (keys) of resources and identifiers of peers that connect to the network via the subnets. A context for peer-to-peer resource discovery and acquisition will be described first. Hierarchies for guiding a peer&#39;s search for a resource will be described next, followed by explanation of components and processes of peers that may provide and search for resources in such hierarchies. 
       A Peer-To-Peer Resource Sharing Framework  
       [0018]      FIG. 1  shows a portion of a typical enterprise network. Such a network may include a number of branch offices, or branches  100 , which might correspond to a physical campus, building, logical divisions of the network, etc. Distant branches  100  may be connected with links  102 , sometimes referred to as WAN links, which in some cases are lines or satellite channels leased from a telecommunication company. Such links  102  often carry network traffic using special point-to-point frame-relay protocols. A branch  100  (or high level subnet) may connect to a link  100  via router  104 , which may also provide connections to a number of subnets  106  of the branch  100 . Computing devices such as servers, clients, etc., may connect to the network via a subnet  106 . 
         [0019]    Generally, a computer on a network communicates with other computers on its own subnet at relatively high speeds and at relatively low cost. A computer communicates with computers on other subnets in its network branch (or higher level subnet, autonomous system, etc.) at a slower speed and at relatively high cost. A computer communicates with a computer of a remote branch via a link  100  relatively slowly; the link  100  having the effect of bottlenecking communications between opposing branches  100 . Note that an enterprise-like network may have one or more gateways to external networks such as the Internet, which might be another bottleneck. As an example, intra-subnet communications might have latencies of a few milliseconds, inter-subnet communications (same branch office) might have latencies of 30 milliseconds, and inter-subnet communications (different branches via a link) might have latencies of 100 milliseconds. Moreover, there may be abundant bandwidth available in the intra-subnet and in the same branch office. However, the link across different branch offices may be leased, and may be more costly. 
         [0020]    It should be understood that the network described above is a simple example. Although actual networks vary greatly in complexity and architecture, most have some form of logical and physical hierarchy and computers therein experience measurably increasing latency as their communications require increasing numbers of hops to reach remote endpoints, and typically there are jumps in latency at routers, WAN links, and other network boundaries or features. 
         [0021]    As will be discussed in detail later, a computer can discern network topology by probing its network (e.g., using a route tracing utility) and analyzing latencies to identify structural boundaries and proximity of subnets in the network. For example, network structure may be identified by abrupt changes in latencies of respective routers providing a network path between two computers. A computer may also determine network structure by obtaining router update messages or other network configuration data, or simply by being provided with information directly describing the topology of its network. 
         [0022]      FIG. 2  shows an example of a peer-to-peer resource sharing framework. The example of  FIG. 2  illustrates generally how resources may be identified and found by a peer. In the example, a peer computing device  130  has an identifier  132  (e.g., URL, network address plus file path, etc.) of a binary archive resource that the peer  130  is seeking, perhaps as instructed by a user. The peer may transmit the resource identifier  132  to a server, for example a web server or file server (not shown). The web server may determine the scope that the resource may be shared with, and return a scoped resource ID that corresponds to the resource in the appropriate scope. The peer can then use the scoped resource ID to discover the resource in the hierarchy. The peer may consult a centralized server in the appropriate scope, which can consequently either return a list  134  of network or IP addresses  134  of peers where the resource is available. Alternatively, the peer  130  may consult a data source or resource discovery service from which the peer  134  obtains the list  134 . The peer  130  then obtains the resource from the one or more addresses or peers identified in the list  134 . As used herein, the term “resource” (or alternatively, “object”) refers both to a complete unit of data such as a file, web page, or any discrete unit of data, as well as portions or pieces of same. In practice, there is little difference between a client obtaining a discrete resource and a client obtaining pieces of the resource; in both cases the processes of locating and copying a whole resource or its pieces are similar. Therefore, the term “resource” as used herein refers to discrete resources as well as pieces thereof. 
         [0023]      FIG. 3  shows an example of how a peer-to-peer resource sharing network may be integrated with higher-level applications. A client  150  on a subnet  151  may have a web browser  152 . When the browser  152  needs a URL, it sends an open-URL request to a web module  154  (e.g., an HTTP implementation). The web module  154  sends the URL to a server&#39;s  156  HTTP module  158 , along with an indication that the client is capable of peer-to-peer resource sharing. The HTTP module  158  responds to the notice of peer-to-peer capability by attempting to find the resource on a peer-to-peer network. Accordingly, the HTTP module  158  notifies a peer-to-peer module  160  of the data or URL that is being sought. The peer-to-peer module  160 , using any of a wide range of new or existing search techniques, queries a peer-to-peer network which the client  150  is participating in, including peers  161  storing resources  163 . If a copy of the resource named by the URL is available on the peer-to-peer network then the peer-to-peer network sends to the peer-to-peer module  160  identifier(s) of the URL/resource. In the example of  FIG. 3 , the identifiers are in the form of a hashlist  162 , which are hashes of one or more pieces of the URL/resource. If a copy of the URL/resource is not available from the peer-to-peer network, then the HTTP module  158 , when so informed by the peer-to-peer module  160 , transparently proceeds with normal resource acquisition via a web server  164  or the like. 
         [0024]    In the scenario described above, a prior approach has been for the peer-to-peer module  160  to simply broadcast a request for the URL/resource to a local subnet (e.g., broadcast on subnet  151 ) and receive locations of the resource on such subnet. Another approach has been to use more sophisticated large-scale structured overlays such as distributed hash tables (DHTs) which may include peers beyond the local subnet. The first approach is limited in scope, and the second approach may be sensitive to churn (frequent additions or losses of peers) or may involve computational and bandwidth overhead to handle the complexities of maintaining a reliable DHT. The peer-to-peer resource sharing application discussed above is only an example. There are an unlimited number of applications that can use a peer-to-peer network. Embodiments of a peer-to-peer resource sharing scheme will be described next. 
       Peer-To-Peer Resource Discovery Schemes  
       [0025]      FIG. 4  shows a scheme for structuring a peer-to-peer network. In general, the scheme involves representing subnets of a network, such as subnet  200 , as first-order entities in an overlay or peer-to-peer network. That is, subnets, peers  202 , and objects (resources) are assigned identifiers in the same number space. For example, a same hash function may be used to obtain identifiers for the subnets, peers, and resources thereon. While in an ordinary peer-to-peer network peers maintain only mappings of object identifiers (object IDs) to peer addresses, in the present embodiment, globally, peers maintain mappings of subnet IDs to object IDs, and locally peers may maintain mappings of object IDs to local peers. 
         [0026]    While embodiments described below are described with reference to “subnets”, it should be understood that any organizational unit of peers may be used. As with other overlay type networks, the peer-to-peer schemes described herein are implemented above the network layer; at the application layer. While subnets are a convenient unit of organization, any arbitrary unit may be used. To reflect this, the term “locality domain” may be substituted wherever “subnet” is used herein. A locality domain is a unit of organization which may reflect some common locality but does not require it. Locality may refer to topological locality (low hop distances), latency, physical locality, and so forth. A locality domain may even be a random sample of peers. The point is that the embodiments described herein function with groupings of peers regardless of how the peers are grouped. A locality domain may be a unit of peers that mutually operate an autonomous peer-to-peer resource sharing mechanism such as a DHT overlay. In an embodiment operated on the global Internet, a locality domain might be, for example, peers in a given class C network, peers in a subnet of a class B network, peers in a plurality of networks/subnets of various classes, and so on. 
         [0027]    As will be described below, the peers use their respective object ID mappings to search for requested objects and to inform other peers about the locations of objects. When a peer&#39;s mapping of subnet IDs is appropriately prioritized, for instance, by network proximity or least latency, a peer searching for a given object ID will search closest subnets first, and then slower or more distant subnets later. The mappings of the peers together implicitly form a hierarchical overlay structure of subnets and groupings of subnets, as explained next with reference to  FIGS. 5 and 6 . 
         [0028]      FIG. 5  shows how a physical network  250  may be represented as a hierarchical data structure. As explained above, the physical network  250  may be comprised of numerous subnets  252  to which peer devices  202  are connected. Subnets  252  may be part of an encompassing AS or subnet or branch  254 ,  256 , which may be connected by one or more links  258 . An inter-subnet hierarchy representation  262  represents the structure and relative latencies (or distances, or other network metrics) of the physical network  250 . Each subnet  252 ,  254 ,  256  has a unique subnet ID. The various peers  202  among the subnets  252 ,  254 ,  256  store information including IDs of peers and IDs of subnets where such peers reside. In one embodiment, any given peer does not by itself maintain complete knowledge of the physical network  250 . Rather different peers maintain different, perhaps overlapping, mappings between subnet IDs and object IDs. Collectively, the peers of a given subnet may know IDs of peers on sibling or parent subnets. 
         [0029]    Referring again to  FIG. 5 , the inter-subnet hierarchy representation  262  is comprised of the subnet IDs of the subnets/branches of the physical network  250 . For example, the subnet IDs of subnet 1 , subnet 2 , and subnet 3  may be grouped to form a ring  264 , where the nodes or members  266  of the ring  264  are the subnet identifiers of sibling subnets. Another ring  268  may correspond to subnet  256 . The IDs of subnets  254  and  256  may belong to ring  268 . It should be noted that in some embodiments the representation  262  is not a particular data structure residing on a single device but rather is the collection of subnet information stored on the various peers  202 , as will be further explained with reference to  FIGS. 7 and 8 . 
         [0030]      FIG. 6  shows a hierarchical representation  280  where subnets are represented as first-order elements. At the lowest level, subnets are organized in level 2  rings. Each level 2  ring is comprised of a group of sibling subnets, that is, subnets close to each other (in terms of latency or other measures of network distance) or subnets on a common network or branch office. For example, the ring  282  has four member subnets (triangles). Each level 2  ring has its own identifier in the same identifier space as the other subnets. Each level 1  ring  284  includes the subnets of all the subnets within it. In the example of  FIG. 6 . The level 0  ring  286  contains all subnets. One way the DHT representation may be implemented will described next with reference to  FIG. 7 . The number of levels, distribution of subnets, and so forth, will depend on the particular network. 
         [0031]      FIG. 7  shows a peer  202  configured for proximity-guided resource discovery. The peer  202  includes mapping information  302 . The mapping information  302  is used primarily for maintaining contact points in the various subnets. For example, a search may be communicated to a subnet by transmitting the search to one of the peers in the subnet. Toward this end, the mapping information  302 , whose content will differ from peer to peer, associates known subnets (by unique subnetID) with known addresses of peers therein. For example, IP address 196.0.0.1 is a peer in subnet having subnetID of “subnetID-a”. When a peer joins, the mapping information  302  may be bootstrapped in a number of ways. Another peer in the subnet may supply a copy of its own mapping table. In another embodiment, a new peer may first discover the network&#39;s subnet structure and then transmit a broadcast to each discovered subnet to obtain one or more addresses of peers on a subnet. In yet another embodiment, the local DHT of each subnet may implement a maintenance protocol; when an incoming request is received from a remote new peer, a random sampling (for example) of addresses of local peers is returned to the remote new peer. 
         [0032]    The mapping information  302  may be maintained in a number of ways. Subnet turnover (“churn”) may be expected to be relatively infrequent. Rather than tracking which peers have which objects, peers keep an up-to-date set of peer IP addresses for a subnet. One technique is to use a simple caching technique where the IP addresses of a subnet are given a lifetime and are periodically refreshed if not used. When an address proves to be stale when a request is sent to it, the address is removed from the mapping information  302  and one or more new addresses are obtained, for example, from other peers in the new peer&#39;s subnet, or, from a neighboring subnet. Another technique is to randomly select one or more random addresses from a subnet. 
         [0033]    In sum, the mapping information  302  stored collectively by the peers of a given subnet allows those peers to search for resources by transmitting requests in order from a most proximal subnet to, going up the global hierarchy (e.g., level 1  rings, then level 0  ring). A request is transmitted to a subnet by transmitting the request to a known address of a peer in the subnet (an address from mapping information  302 ), and the receiving peer&#39;s local DHT (or other form of local resource sharing) knows a subnet where the requested resource is available, the receiving peer&#39;s subnet/DHT returns the subnetID of any such subnets. It is not important which peers&#39; network addresses of a given subnet are stored in the mapping information. The network addresses are simply communication points for communications directed to the corresponding subnet. If all of a peer&#39;s known network addresses for a subnet prove to be stale or unreachable, the peer may ask another peer, preferably on the local subnet, for new addresses of the subnet. 
         [0034]    Peer  202  may also have a subnet-data mapping table  303  that maps subnets to objects. The mapping table  303  may be initialized by using a copy from another peer in the local subnet, or it may start in an empty state. The mapping table  303  may be maintained in various ways. As the peer  202  performs lookups and locates objects, or perhaps as it receives updates from other subnets (see, e.g., STAGE IVB in  FIG. 8 ) it may store known subnet-object mappings in mapping table  303 . Peer  202  may receive direct subnetID-objectID updates from local peers or from other subnets. Similarly, a peer may receive updates indicating that a subnet no longer has a given object, in which case any such entries would be deleted from mapping table  303 . 
         [0035]    The mapping table  303  and mapping information  302  are used by a peer-to-peer content sharing module  308 . The peer-to-peer content sharing module uses the mapping table  303  and mapping information  302  to perform searches. The information is also maintained by the peer-to-peer content sharing module, which may receive and transmit maintenance updates to/from other peers. The module  308  also answers the searches of other peers. For example, a local or remote peer may request the location for objID-y. The module  308  would consult mapping table  303 , determine that object-IDy is available at subnetID-b, and return the subnetID “subnetID-b” to the requesting peer. Note that the requesting peer may be another peer in the local subnet that is querying the local subnet in response to a request from a peer in another subnet, in which case the requesting peer would then forward the answer (e.g., “subnetID-b”) to such peer. Note that in DHT terminology, objects and objectIDs are sometimes referred to as values and keys, respectively. 
         [0036]    In one embodiment, the peers of a given subnet mutually implement their own peer-to-peer resource sharing mechanism, for example, a local DHT, a simple broadcast mechanism (similar to Vortex, available from Microsoft Corporation), etc. The maintenance of a local DHT is local; peers outside the local DHT may access the DHT but are not members. It is even possible that different subnets may use different types of DHTs or other resource-sharing schemes. Nonetheless, for search efficiency and other reasons, each local DHT (or other form of peer-to-peer sharing) uses keys and identifiers in a same global identifier space. Thus, peers in different subnets will still use the same subnetID for a given subnet and the same objectID for a given object, regardless of which subnet(s) are storing the object. 
         [0037]    In one embodiment, the local resource sharing may be performed by a separate module, for example, a local DHT module  310 . The local DHT module handles the functions involved with participating in the local DHT, and may use and maintain a cache of content  312  having objects (i.e., values) and corresponding identifiers (i.e., keys) as well as a list of local peers  314  (addresses) that have various objects. The local DHT module  310  may perform basic functions such as responding to object queries (queries for the location of an object), issuing such queries to the local DHT  316 , sending and receiving maintenance updates, and so on. When the peer  202  is to search for an object, peer-to-peer content sharing module may first use the local DHT module  310  to determine if a requested object is available locally at a peer  318  in the peer  202 &#39;s local DHT. Also, after receiving a location of a requested objectID and downloading the object, peer-to-peer content sharing module  308  may inform the local DHT module  310  of the newly obtained content, in response to which the local DHT module  310  will update its local cache of content  312 . 
         [0038]      FIG. 8  shows an example of a proximity-guided search of a hierarchy of subnets  330 . The hierarchy of subnets  330  is similar to the example hierarchical representation  280  in  FIG. 6 . Initially, at STAGE  0 , a peer at subnet  332  is searching for an objectID, and a remote subnet  334  knows a location of the objectID. At STAGE I, assuming that the requesting peer was unable to find the objectID on itself or its local subnet (e.g., on local DHT), the requesting peer searches other subnets based on proximity (e.g., subnets less than 5 ms distance). In other words, the requesting peer on subnet  332  will search other subnets on its level 2  ring  336 , preferably in order of increasing subnetID. As the subnetIDs and objectIDs are in the same key/ID space, the search of a given level need only proceed until a subnetID is reached that is greater than the sought objectID, at which time it is known that the object is not available on the current ring level. In the example of  FIG. 8 , the requesting peer contacts two other subnets, neither of which responds with a location of the target objectID. If subnet  338  is queried without success, and the next subnet  340  has a subnetID greater than the requested objectID, then the requesting peer on subnet  332  will start to search less proximate subnets, i.e., subnets higher up the hierarchy. 
         [0039]    At stage  11 , the requesting peer begins searching the next most proximate subnets—the level 1  ring  342  (e.g., subnets less than 30 ms distant). This part of the search may start with the subnet whose subnetID is next in sequence after the last searched subnet  338 —subnet  344 . The level 1  subnets whose subnetID is less than the sought objectID do not have a location of the object, and the search proceeds up another level to the level 0  ring  336 . The next subnet at level 0  whose subnetID is closest to the last searched subnet (subnet  344 ) is subnet  334 , and the requesting peer queries subnet  334 . One or more peers on subnet  334  have in their mapping table information  303  the sought objectID and corresponding subnetIDs subnetIDm and subnetIDn. AT STAGE IVA, SubnetIDm and subnetIDn are returned to the requesting peer on subnet  346 , which may then use the subnetIDs to request a peer address from which to obtain the object. At an optional STAGE IVB, the responding subnet  334  may correctly conclude that no subnets with subnetID of subnet  332  up to and including the subnetID of subnet  344  know the location of the sought objectID (otherwise, the search would not have proceed to the level 0  ring). Therefore, the responding subnet  334  may also transmit the objectID and corresponding known subnetIDs to one or more such subnets. In one embodiment, only one subnet at each intervening level receives the update; the subnet whose subnetID is closest (at its level) to the objectID. 
         [0040]    When a requesting peer has obtained a subnetID of a subnet (e.g., subnetIDm) that is storing the sought object, the requesting peer then looks in its mapping information  302  to find an address of subnetIDm and sends a request to the local DHT of that subnet. The peer may use the found address as a point for communicating with the target subnet (subnetIDm), receiving from the address the address of a peer (on subnetIDm) having the object. The requesting peer then uses the obtained address to transfer the object from the corresponding remote peer. 
         [0041]      FIG. 9  shows various processes that may be performed by a peer  202 . A peer  202  may join  360  by probing the network to discover subnet boundaries (jumps in latency, hop-count thresholds, etc.) or other information that indicate proximity, and then may transmit “join” messages to local peers and optionally other subnets. A peer  202  may service  362  subnet queries. When a requested objectID directed to the peer&#39;s subnet is received, the peer may search itself and/or its local subnet for a subnetID that has the objectID, and return same if found. The peer  202  may also maintain  364  routing information, which may entail receiving updates from other subnets and distributing them to other local peers, and conversely, storing such updates from other local peers. Peer  202  may also have a search process to find  366  a subnet that has a needed objectID. This may involve searching the local subnet, then searching subnets in order of proximity and subnetID until a subnet returns a subnetID of a subnet that has the needed object. The peer  202  may also have a process to query and download. Namely, after receiving the subnetID of a subnet that has a needed object, the peer may query the subnet and receive the address of a peer (on that subnet) that has the object. The object (and/or parts thereof) is then downloaded from that peer. The preceding processes may be implemented using the peer configuration shown in  FIG. 7 , or using any other arbitrary peer design. 
       CONCLUSION 
       [0042]    Embodiments and features discussed above can be realized in the form of information stored in volatile or non-volatile computer or device readable media. This is deemed to include at least media such as optical storage (e.g., CD-ROM), magnetic media, flash ROM, or any current or future means of storing digital information. The stored information can be in the form of machine executable instructions (e.g., compiled executable binary code), source code, bytecode, or any other information that can be used to enable or configure computing devices to perform the various embodiments discussed above. This is also deemed to include at least volatile memory such as RAM and/or virtual memory storing information such as CPU instructions during execution of a program carrying out an embodiment, as well as non-volatile media storing information that allows a program or executable to be loaded and executed. The embodiments and features can be performed on any type of computing device, including portable devices, workstations, servers, mobile wireless devices, and so on. 
         [0043]      FIG. 10  shows an example computing device  380  which may run software implementing any of the techniques or features described herein. The computing device may have known elements such as a processor  382  cooperating with memory  384  and possibly local storage  386  and/or peripheral storage  388 , which may serve as the aforementioned device readable media.