Source: http://www.google.com/patents/US7552233?dq=U.S.+Patent+%23+5,723,324
Timestamp: 2014-07-25 10:46:10
Document Index: 358411399

Matched Legal Cases: ['Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60']

Patent US7552233 - System and method for information object routing in computer networks - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign in<nobr>Advanced Patent Search</nobr>PatentsAn address of a server that should supply an information object or service to a requester is returned in response to a request therefor. The address of the server that is returned is an optimal server selected according to specified performance metrics. The specified performance metrics may include one...http://www.google.com/patents/US7552233?utm_source=gb-gplus-sharePatent US7552233 - System and method for information object routing in computer networksAdvanced Patent SearchPublication numberUS7552233 B2Publication typeGrantApplication numberUS 10/241,767Publication dateJun 23, 2009Filing dateSep 10, 2002Priority dateMar 16, 2000Fee statusPaidAlso published asUS20030200307Publication number10241767, 241767, US 7552233 B2, US 7552233B2, US-B2-7552233, US7552233 B2, US7552233B2InventorsJyoti Raju, J. J. Garcia-Luna-Aceves, Bradley R. SmithOriginal AssigneeAdara Networks, Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (63), Non-Patent Citations (44), Referenced by (20), Classifications (26), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetSystem and method for information object routing in computer networksUS 7552233 B2Abstract An address of a server that should supply an information object or service to a requester is returned in response to a request therefor. The address of the server that is returned is an optimal server selected according to specified performance metrics. The specified performance metrics may include one or more of an average delay from the server to another, average processing delays at the server, reliability of a path from the server to another, available bandwidth in said path, and loads on the server.
returning, in response to a request from a client, an address of a first server that should service a second server's request for an information object based on the second server receiving the client's request of the information object that is not located at the second server, the address of the first server being selected according to specified performance metrics, wherein the specified performance metrics comprise average processing delays at the first server, average delay from the first server to the second server, reliability of a path from the first server to the second server, and available bandwidth in said path from the first server to the second server;
referring the second server's request for the information object to a first Web router; and
configuring the first Web router to create a map that associates an identifier of the information object with the address of the first server according to other mappings generated by other Web routers and forwarded to the first Web router, wherein the other mappings generated by the other Web routers are forwarded to the first Web router as inter-Web router communication messages passed between the Web routers using a Web Information Locator by Distance (WILD) protocol.
2. The method of claim 1 wherein the specified performance metrics comprises average delay from the first server to the second server, average processing delays at the first server, reliability of a path from the first server to the second server, available bandwidth in said path, and loads on the first server.
8. The method of claim 1 wherein the map is generated by the first Web router according to the specified performance metrics, which comprise one or more of average delay from the first server to the second server, average processing delays at the first server, reliability of a path from the first server to the second server, available bandwidth in said path, and loads on the first server.
9. The method of claim 1 wherein one or more the communication messages passed between the Web routers further report an associated address of one of the other Web routers co-located with an information object repository that contains the information object.
10. The method of claim 1 wherein the other mappings specify optional associations of information object identifiers to information object repository addresses.
11. The method of claim 1 wherein the map is based on distance information obtained using a routing protocol that provides accurate distances from one Web router to another, the distance information being based on one or more of the specified performance metrics.
12. The method of claim 11 wherein the routing protocol is at least one of: a diffusing update algorithm (DUAL); a loop-free path-finding algorithm (LPA); a link-vector algorithm (LVA); a bandwidth efficient source tree (BEST) protocol; a dynamic source tree (DST) routing protocol; a diffusing algorithm for shortest multipaths (DASM); a multipath distance vector algorithm (MDVA); a routing on-demand acyclic multipath (ROAM) protocol; a multiple-path partial-topology dissemination algorithm (MPDA); a multipath loop-free routing algorithm (MPATH); an adaptive link-state protocol (ALP); a topology broadcast protocol; a path vector algorithm used as part of the Border Gateway Protocol (BGP); or a static table in the first Web router specifying the next hops or paths to one or more other active Web routers.
13. The method of claim 1 wherein the first Web router executes a communication protocol with which it determines: addresses of other Web routers participating in a virtual overlay network with the first Web router; and optimum distances to each Web router in the virtual overlay network.
14. The method of claim 13 wherein the first Web router further determines neighbor Web routers that offer the optimum distances to each Web router in the virtual overlay network.
15. The method of claim 13 wherein the first Web router updates the map according to messages received from other Web routers in the virtual overlay network.
16. The method of claim 15 wherein the map is implemented as one or more tables stored in a computer readable medium.
one or more messages passed between Web routers over a Web information locator by distance (WILD) protocol, used for inter-Web router communication, said messages including information which allows said web routers to dynamically update mappings of information objects to server addresses including an address of a first server that should service a second server's request for an information object in response to the second server receiving a client requestor's request for an information object that is not located at the second server based on specified performance metrics, wherein the specified performance metrics comprise an average processing delay at the first server, average delay from the first server to the second server, reliability of a path from the first server to the second server, and available bandwidth in said path from the first server to the second server; and
a first web router, comprising a general purpose computer, for receiving the second server's request for the information object, wherein the first web router is configured to create a map that associates an identifier of the information object with the address of the first server according to other mappings generated by other web routers and forwarded to the first web router, wherein the other mappings generated by the other Web routers are forwarded to the first Web router as inter web router communication messages passed between the web routers using a Web information locator by distance (WILD) protocol.
18. The communication system of claim 17 wherein the mappings are optimal mappings of the information objects to the server addresses.
19. The communication system of claim 18 wherein the specified performance metrics comprises average delay from a server to another, an average processing delay at a server, reliability of a path from a server to another, available bandwidth in such a path, and loads on a server.
20. The communication system of claim 18 wherein said messages report updated distances from said server addresses to another information object, said distances being based on said specified performance metrics.
21. The communication system of claim 20 wherein said messages further report, for each updated distance, an associated server.
22. The communication system of claim 21 wherein said messages further report, for each updated distance, an associated address of a first Web router co-located with a first server that is a subject of the message.
23. The communication system of claim 17. wherein Web routers dynamically update mappings in response to one or more of the following inputs: addition/deletion messages from an associated information object repository, changes in load messages from the associated information object repository, changes in information object repository connectivity information, URL updates from neighbor Web routers, changes in Web router neighbor connectivity information, changes in distances to other Web Routers, and URL lookup queries.
24. The communication system of claim 23 wherein in response to one or more of the inputs, Web routers take one or more of the following actions; if an input offers a better distance to a URL than is currently maintained, change a corresponding routing table entry accordingly and transmit an add message; if an input offers a worse distance than a present routing table entry, ignore that input; if an input causes a loss of a last path, transmit a delete message; and if an input causes a distance increase, change a corresponding routing table entry accordingly and transmit a query.
mapping an address of a requesting server seeking an information object to an address of an information object repository that has a best distance to the requesting server based on the requesting server receiving a requestor' s request of the information object that is not located at the requesting server according to specified performance metrics, wherein the specified performance metrics comprise average processing delays at the requesting server, average delay from one information object repository to another within a network, reliability of a path from one information object repository to another, and available bandwidth in said path; and
referring the requesting server's request for the information object to a first Web router; and
configuring the first Web router to create a map that associates an identifier of the information object with the address of the information object repository according to other mappings generated by other Web routers and forwarded to the first Web router, wherein the other mappings generated by the other Web routers are forwarded to the first Web router as inter-Web router communication messages passed between the Web routers using a Web Information Locator by Distance (WILD) protocol.
26. The method of claim 25 wherein distance information between information object repositories is computed according to a shortest-path first algorithm.
27. The method of claim 25, further comprising verifying mapping information between the information object and the requesting server by only trusting a neighbor node of a communication network that offers a shortest path to the requesting server.
28. The method of claim 27 wherein in the case of two or more equal distances, that mapping information which is received is adopted.
RELATED APPLICATIONS The present application is related to and hereby claims the priority benefit of the following commonly-owned and co-pending U.S. Provisional Patent Applications:
(1) Application No. 60/323,126, entitled �SYSTEM AND METHOD FOR DIRECTING CLIENTS TO OPTIMAL SERVERS IN COMPUTER NETWORKS� filed Sep. 10, 2001, by J. J. Garcia-Luna-Aceves and Srinivas Vutukury; and (2) Application No. 60/322,899, entitled �SYSTEM AND METHOD FOR INFORMATION OBJECT ROUTING IN COMPUTER NETWORKS�, filed Sep. 10, 2001, by Jyoti Raju, J. J. Garcia-Luna-Aceves and Bradley R. Smith; and the present application is also a continuation in part of commonly owned and co-pending U.S. patent application Ser. No. 09/810,148, entitled �SYSTEM AND METHOD FOR DISCOVERING INFORMATION OBJECTS AND INFORMATION OBJECT REPOSITORIES IN COMPUTER NETWORKS�, filed Mar. 15, 2001, by J. J. Garcia-Luna-Aceves, which claims priority from U.S. Provisional Patent Application No. 60/190,331, filed Mar. 16, 2000 and from U.S. Provisional Patent Application No. 60/200,401, filed Apr. 28, 2000, and which issued as U.S. Pat. No. 7,162,539 B2 on Jan. 9, 2007. FIELD OF THE INVENTION The present invention relates to a system and method for directing a client (i.e., an information requesting application such as a Web browser) to an optimal content source such as a cache or server (i.e., information object repository) among many available content repositories for servicing of a request for one or more information objects or services.
�Information Management: A Proposal,� CERN Document, March 1989). The Web consists of a vast collection of information objects organized as pages, and each page may contain links to other pages or, more generally, information objects with which content is rendered as audio, video, images, text or data. Pages are viewed by an end user with a program called a browser (e.g., Netscape NavigatorTm). The Web browser runs in an end system at the user premises. The client (Web browser) obtains the required information objects from a server (Web server) using a request-response dialogue as part of the Hypertext Transfer Protocol (HTTP). Information objects are identified by means of names that are unique throughout the Internet; these names are called Uniform Resource Locators or URLs. A URL consists of three components:
File allocation methods for distributed databases (e.g., W. W. Chu, �Optimal File Allocation in a Multiple Computer System,� IEEE Transactions on Computers, October 1969; S. Mahmoud and J. S. Riordon, �Optimal Allocation of Resources in Distributed Information Networks,� ACM Transactions on Data Base Systems, Vol. 1, No. 1,
March 1976; H. L. Morgan and K. D. Levin, �Optimal Program and Data Locations in Computer Networks,� Communications of the ACM, Vol. 20, No. 5, May 1977) and directory systems (e.g., W. W. Chu, �Performance of File Directory Systems for Data Bases in Star and Distributed Networks,� Proc. National Computer Conference, 1976, pp. 577-587; D. Small and W. W. Chu, �A Distributed Data Base Architecture for Data Processing in a Dynamic Environment,� Proc. COMPCON 79 Spring) constitute some of the earliest embodiments of methods used to select a delivery site for accessing a file or information object that can be replicated at a number of sites.
Hash routing protocols (K. W. Ross, �Hash Routing for Collections of Shared Web Caches,� IEEE Network, Vol. 11, No. 6, November 1997, pp 37-44) constitute another approach to support object discovery in shared caches. Hash routing protocols are based on a deterministic hashing approach for mapping an information object to a unique cache (D. G. Thaler and C. V. Ravishankar, �Using Name-Based Mappings To Increase Hit,� EEE/ACM Trans. Networking, 1998; V. Valloppillil and J. Cohen, �Hierarchical HTTP Routing Protocol,� Internet Draft, http://www.nlanr.net/Cache/ICP/draft-vinod-icp-traffic-dist-OO.txt) to distribute the information objects (universal resource locator or URL in the case of the Web) among a number of caches; the end result is the creation of a single logical cache distributed over many physical caches. An important characteristics of this scheme is that information objects are not replicated among the cache sites. The hash function can be stored at the clients or the cache sites. The hash space is partitioned among the N cache sites. when a client requires access to an information object o, the value of the hash function for o, h(o), is calculated at the client or at a cache site (in the latter case the cache would be configured at the client, for example). The value of h(o) is the address of the cache site to contact in order to access the information object o.
This DNS-based approach, without the use of hierarchies of Web caches, is advocated in the Akamai CDN solution (F. T. Leighton and D. M. Lewin, �Global Hosting System,� U.S. Pat. No. 6,108,703, Aug. 22, 2000). The �global hosting system� advocated by Akamai assumes that a content provider services an HTML document in which special URLs specifying a domain name specific to Akamai. When the client needs to obtain the WP address of the Web cache hosting the content specified in the special URL, the client first contacts its local DNS. The local DNS is pointed to a �top-level� DNS server that points the local DNS to a regional DNS server that appears close to the local DNS. The regional DNS server uses a hashing function to resolve the domain name in the special URL into the address of a Web cache (hosting server) in its region, which is referred to as the target Web cache in the present application, in a way that the load among Web caches in the region is balanced. The local DNS passes the address of that Web cache to the client, which in turn sends its request for the information object to that Web cache. If the object resides in the target Web cache, the cache sends the object to the client; otherwise, the object is retrieved from the original content site.
A number of proposals exist to expedite the dissemination of information objects using what is called �push distribution� and exemplified by Backweb, Marimba and Pointcast (�BackWeb: http://www.backweb.com/�; �Marimba: http:www.marimba.comn �; �Pointcast: http://www.pointcast.com/�). According to this approach, a Web server pushes the most recent version of a document or information object to a group of subscribers. The popular Internet browsers, Netscape Navigator and Internet Explorer�, use a unicast approach in which the client receives the requested object directly from the originating source or a cache. As the number of subscribers of a document or information object increases, the unicast approach becomes inefficient because of processing overhead at servers and proxies and traffic overhead in the network. The obvious approach to make push distribution scale with the number of subscribers consists of using multicast technology. According to this approach (P. Rodriguez and E. W. Biersack, �Continuous Multicast Push of Web Documents over The Internet,� EEE Network Magazine, Vol. 12, No. 2, pp. 18-31, 1998), a document is multicasted continuously and reliably within a multicast group. A multicast group is defined for a given Web document and subscribers join the multicast group of the Web document they need to start receiving the updates to the document. A multicast group consists of the set of group members that should receive information sent to the group by one or multiple sources of the multicast group. The main shortcoming of this particular approach to push distribution are:
The portion of the Internet where subscribers are located must support multicast routing distribution. A multicast address and group must be used for each Web document that is to be pushed to subscribers, which becomes difficult to manage as the number of documents to be pushed increases. Furthermore, Rodriguez, Biersack, and Ross (P. Rodriguez, E. W. Biersack, and K. W. Ross, �Improving The WWW: Caching or Multicast?,� Institut EURECOM 2229, Route Comptuer Network and ISDN Systems, pp. 1-17 (Mar. 30, 1998) have shown that multicasting Web documents is an attractive alternative to hierachical web caching only when the documents to be pushed are very popular, caching distribution incurs less latency.
Another approach to helping select servers in a computer network (Z. Fei, S. Bhattacharjee, E. W. Zegura, and M. H. Ammar, �A Novel Server Selection Technique for Improving The Response Time of a Replicated Service� Proc. EEE Infocom 98, March 1998, pp. 783-791) consists of broadcasting server loading information after a certain load threshold or time period is exceeded. The limitation of this approach is that, just as with topology-broadcast protocols used for routing in computer networks, the scheme incurs substantial overhead as the number of servers increases.
Another recent approach to directing clients to hosting sites with requested information objects or services is the enhanced network services method by Phillips, Li, and Katz (S.G. Phillips, A. J. Li, and D. M. Katz, �Enhanced Network Services Using a Subnetwork of Communicating Processors,� U.S. Pat. No. 6,182,224, Jan. 30, 2001.). Insofar as directing clients to servers, the enhanced network services method is very similar to the gathering of location data with router support advocated by Guyton and Schwartz described previously. As in the Guyton and Schwartz's approach, routers using the enhanced network services approach gather network topological data and also include as part of their normal routing exchanges information about the hosts that can provide content and services to clients; routers can then rank the hosts according to their relative distance in the network. In addition to data regarding hosts that can provide services, routers in the enhanced network services approach can include in their normal routing exchanges host information regarding logged-in users and willingness to pay for performing a designated service. In contrast to the proposal by Guyton and Schwartz, the enhanced network services approach does not attempt to limit the amount of network topological information that routers need to exchange in order to direct clients to best qualified servers. This approach has, therefore, similar performance and scaling limitations as the prior approaches summarized above based on flooding of information among caches or servers, and forwarding of requests over multiple hops.
SUMMARY OF THE INVENTION The present invention address shortcomings of the above-described schemes.
FIG. 1 illustrates an internetwork in which the methods and systems of the present invention may operate.
FIG. 2 illustrates a virtual overlay network of Web routers configured in accordance with an embodiment of the present invention.
FIG. 3 illustrates a hosting site configured with multiple information object repositories and a Web router that operates in accordance with an embodiment of the present invention.
FIG. 4 illustrates functional componets of a Web router in accordance with an embodiment of the present invention.
The address of the information object repository returned in response to the request is the one that maintains a local copy of the originally requested information object or service and is the �best� information object repository selected according to specified performance metrics. It is assumed in this discussion, therefore, that the information object repositories are connected using a virtual (or physical) network and can reach each other. The specified performance metrics may include one or more of an average delay from one information object repository to another along the network(s) (i.e., network delays), average processing delays at an information object repository, reliability of a path from one information object repository to another, available bandwidth in said path, and loads on the various information object repositories.
In order to produce the above-mentioned mappings, distances (e.g., measured in terms of link costs and the like) need to be measured. Thus, the present invention makes use of a routing protocol that provides accurate distances from one Web router to another, these distances being based on one or more of the specified performance metrics. In one particular embodiment, a routing protocol known as ALP is used for this purpose (for further information on the Adaptive Link-State Protocol or ALP see, J. J. Garcia-Luna-Aceves and M. Spohn, �Scalable Link-State Internet Routing,� Proc. IEEE International Conference on Network Protocols (ICNP 98), Austin Tex., Oct. 14-16, 1998, pp. 52-61, incorporated herein by reference), though this is merely for convenience and many other suitable protocols exist and may be used equally as well. In addition, an interfacing protocol between an information object repository and an associated Web router co-located at the site is useful in conjunction with the present invention. In one particular embodiment, the Web Router Communication Protocol (WRCP) is used, however this is merely for convenience and other protocols may be used equally as well, to inform a Web router of the information objects and services added and deleted from its local information object repository.
FIG. 1 illustrates an internetwork 100 and the methods and systems described herein enable the direction of clients and/or servers, etc. to either information objects or the caches and servers storing information objects distributed over computer networks such as internetwork 100. One example of an internetwork 100 is the Internet. Other examples include enterprise networks, local area networks, wide area networks, metropolitan area networks and networks of such networks. In the case where internetwork 100 is the Internet, clients 110 will generally access content located at remote servers 170 through a series of networks operated by different providers. For example, clients 110 may have accounts with local ISPs 120 that enable the clients to connect to the Internet using conventional dial-up connections or one of a variety of high-speed connections (e.g., DSL connections, cable connections, hybrids involving satellite and dial-up connections, etc.). ISPs 120, in turn, may provide direct connections to the Internet or, as shown, may rely on other service providers 130, 140, 150 to provide connections through to a set of high-speed connections between computer resources known as a backbone 160. Connecting to a host (e.g., server 170) may thus involve connecting through networks operated by a variety of service providers.
FIG. 2 illustrates a VON 200 of Web routers 202 a-202 h defined on top of the physical topology of an internetwork, such as the Internet, consisting of routers interconnected via point-to-point links or networks. The virtual network of Web routers includes point-to-point links 204 configured between the Web routers, and the links 206 configured between a Web router 202 and one or more Web caches 208 and content servers 210. Such links 204, 206 can be implemented using tunnels (e.g., Internet protocol (IP) tunnels) between Web routers 202 and between Web routers 202 and Web caches 208. As discussed above, messages can be exchanged between the Web routers 202 via the tunnels. As shown in the figure, a client 110 is not necessarily part of the virtual network of Web routers.
A Web router preferably communicates with its neighbor Web routers using the Web Information Locator by Distance (WILD) protocol. The WILD protocol is disclosed in commonly owned U.S. Provisional Application No. 60/200,401, entitled �System and Method for Discovering Optimum Information Object Repositories in Computer Networks (WILD Protocol), filed Apr. 28, 2000 by J. J. Garcia-Luna-Aceves and Bradley R. Smith, now replaced by commonly owned and co-pending U.S. patent application Ser. No. 09/810,148, entitled �System and Method for Discovering Information Objects and Information Object Repositories in Computer Networks�, filed Mar. 15, 2001, by J. J. Garcia-Luna-Aceves, the complete disclosures of which are hereby incorporated by reference. The WILD communication protocol provides for the exchange of one or more inter-Web router messages via the tunnels. These messages carry the mappings specifying the association between optimal information object repositories and information objects according to the specified metrics. When these mappings change due to changes in the topology of the Internet, the messages carry updated distance information (e.g., as computed according to the performance metrics) in the maps. Thus, using WILD each Web router implements a distributed algorithm and executes a communication protocol with which it determines:
(1) the address of all the other Web routers participating in the same virtual overlay network; and (2) the optimum distance to each Web router (i.e., the associated information object repository) in the VON and the neighbor Web router that offers such a distance. The Web routers employ special rules when updating their local maps in response to received messages. The WILD protocol (or simply WILD) running at each Web router then constructs tables (which are stored locally in memory or other computer-readable media) containing the optimal mapping information. Each Web router uses the tables computed by WILD for directing a requestor to an optimal information object repository. Further details regarding the manner in which the maps and tables are generated and shared among Web routers ma be found in co-pending Application No. 60/323,126, entitled �System and Method for Directing Clients to Optimal Servers in Computer Networks� filed Sep. 10, 2001, the complete disclosure of which is hereby incorporated by reference. Briefly, however, one or more tables are constructed at each Web router and these tables contain client-to-server distance information. The tables are stored in a computer-readable medium accessible by the corresponding Web router and are updated in response to revised client-to-Web router distance information. Such revised client-to-Web router distance information may be included in the inter-Web router communication messages and is preferably determined, at least in part, from internetwork connectivity information received through an exchange of messages according to an inter-domain routing protocol. Furthermore, the tables may be updated in response to revised server load information and the updated table information transmitted to one or more of the Web routers using one or more inter-Web router communication messages.
FIG. 4 illustrates the interaction between various functional components that make up a Web router 400. The method implemented in Web routers to determine an optimum server for a given information object or service is referred to as �URL Routing� and an information object identifier or service identifier is referred to as a �URL�. The Web router maps each URL provided by a requestor to the address of an information object repository that can optimally provide the associated information object. This mapping of URLs to addresses is accomplished by the collaboration among Web routers through WELD. Accordingly, the Web router contacted by the requestor can return the required addresses immediately after processing the request.
Knowing which information object repository is �optimal� for a given URL requires that the Web routers be provided with distance information concerning those URLs. The specific algorithm that a Web router executes to compute the distance to the nearest server storing a copy of an information object or service depends on the routing information that the Web routers use to compute distances to other Web routers, which are co-located with the servers storing information objects and services. Recall that a Web router is informed by its local server(s) of the load in the server(s) and the information objects and services stored in the servers. Hence, a Web router knows that its distance to information objects and services stored in local server(s) is the latency incurred in obtaining those objects or services from the local servers, which is a direct function of the load in those servers.
(1) Diffusing update algorithm (DUAL), which is the basis for Cisco's EIGRP; (2) Loop-Free path-finding algorithm (LPA); (3) Link-vector algorithm (LVA); (4) Bandwidth efficient source tree (BEST) protocol; (5) Dynamic source tree (DST) routing protocol; (6) Diffusing algorithm for shortest multipaths (DASM); (7) Multipath distance vector algorithm (MDVA); (8) Routing on-demand acyclic multipath (ROAM) protocol; (9) Multiple-path partial-topology dissemination algorithm (MPDA); (10) Multipath loop-free routing algorithm (MPATH); (11) Adaptive link-state protocol (ALP); (12) A topology broadcast protocol, such as the one implemented in the Open Shortest Path First protocol (OSPF); (13) The path vector algorithm used as part of the Border Gateway Protocol (BGP); or (14) A static table in a Web router specifying the next hops or paths to every other active Web router in the system. To provide for the reporting of object-server matches to requesters, each Web router maintains a routing database consisting of a routing table, a server table, and a neighbor table. These tables do not need to be exported to the kernel and therefore their size is only constrained by the limits of the available system memory. The routing tables have sizes proportional to the number of URLs they contain, whereas the server table has a size proportional to the number of information object repositories known by the URL routing protocol. The neighbor table size will be proportional to the number of neighbors (both Web router neighbors and local information object repositories). In order to provide for a constant lookup time, a hash table data structure may be used for all three data structures.
URL Cache Local name IP URL name is the name assigned to the information object. CacheIP corresponds to the IP address of the optimum information object repository from which to get the associated information object. Local is a bit mask corresponding to the neighbor table. If a cache neighbor has reported a URL, then its bit is set in the bit mask.
Cache Cache Cache� Web Neighbor Alp_dist Counter IP Load SN Router Address Cache IP Address is the 32-bit IP address of the information object repository. Cache Load is the value corresponding to the load on that information object repository. This may be measured by a computer process resident at the information object repository and reported to the associated Web router using WRCP. Cache_SN is the sequence number associated with the last update regarding the information object repository (used for verification). The Web Router is the Web router that is responsible for sending updates about the associated information object repository. Neighbor stands for the neighbor Web router that offers the best path to the information object repository. Alp_dist is the distance to the Web Router obtained by a routing protocol running in the virtual overlay network. Counter is a count of the number of URLs using the identified information object repository.
Neighbor Link Address cost Neighbor address is the IP address of the neighbor (Web router or local information object repository). Link cost is the cost of the link in the case of Web router neighbors and load in case of information object repository neighbors.
Version Number Cloud ID Type Count Neighbor Link Cost Version number indicates the version of the routing protocol running on the Web router originating the message. The version number needs to be checked by the receiving Web router before processing a packet. If the version number indicates that the originating Web router is using a different version of the routing protocol than the receiving Web router, the packet is simply dropped.
Alp distance Cache Ip Address Load Web Router to WR URL Count URL 1 ADQ Flag URL 2 ADQ Flag Cache IP Address, Load, Web Router and ALP distance have the same meaning as in the server table. URL Count is the number of URL entries corresponding to the subject information object repository. The ADQ flag specifies whether an update message corresponds to an add message (i.e., a message indicating a URL has been added to the local cache), a delete message (i.e., a message indicating a URL has been removed from the local cache) or a query. A Web router that receives a query must return its latest routing table entry to the neighbor that sent the query. In the pseudocode described below, the command to consolidate updates ends up arranging each update in this fashion.
(1) Adds/deletions from an associated information object repository transmitted using WRCP. (2) Changes in load from an associated information object repository transmitted using WRCP. (3) Changes in information object repository connectivity received through the neighbor protocol. (4) URL updates from other neighbor Web routers (e.g., received via WILD). (5) Changes in Web router neighbor connectivity reported by the routing protocol used to compute distances to other Web routers (e.g., ALP). (6) Changes in distances to other Web Routers. (7) URL lookup queries from WRCP. Also using URL routing, a Web router sends the following outputs:
(1) Response to a query sent by WRCP. (2) URL updates to Web router neighbors. When a Web Router receives any of the above inputs, it takes the following actions:
(1) If the input offers a better distance to the URL, change the routing table to use the new input and send out an add update. (2) If the input offers a worse distance than the present one, ignore it. (3) If the input causes the loss of the last path, send out a delete. (4) If the input causes a distance increase or causes the Web router to pick a different path, change the routing table accordingly and send out a query. The various functional modules described above, along with the interfaces between the modules, are best presented in the following pseudocode. This includes the inter-process communications (calls) as well as the main procedures themselves. For convenience, the routing protocol used to compute distances between Web routers is assumed to be ALP; however, other routing protocols could be used instead. Furthermore, the information object repositories used to store information objects or services are referred to as caches, though this term should be understood to include all forms of information object repositories. In the pseudocode, the following variables and data structures are used:
i: The Web router in which the algorithm is running. Ni: The current set of neighbors reported by ALP and Neighbor Protocol. URT: Shared memory URL routing table with all known URLs. Each entry has the following fields:
url: The first 32 bits of the MD5 hash of the URL. p_cache: The preferred cache. p_port: The port used by the preferred cache. local: bit mask corresponding to the local caches that have the URL. NT: Neighbor Table with entries for each neighbor in Ni. Each entry has the following fields:
nbr_ip: IP address of the neighbor nbr_port: Port for a cache neighbor l_cost: Cost of the link to the neighbor CT: Cache table for all the caches currently known by URL Routing. Each entry has the following fields:
cache: IP address of the cache port: Port of the cache load: Load on the cache web_rtr: Web router associated with that cache nbr: Neighbor that offers the shortest path to web_rtr alp_dist: Alp distance to web_rtr counter: Number of NURT entries that point to this cache entry Each packet has the following header fields:
version: Version number of the protocol cloud: Cloud in which the protocol is running l_cost: Link cost to neighbor to whom the packet is being sent UE1: update entry of type 1 in a packet. Each entry has the following fields:
cache: IP address of the cache load: Load on the cache cache_sn: Sequence number associated with the last update about the cache web_rtr: Web router associated with the cache alp_dist: ALP distance to above web router UE2: update entry of type 2 in a packet. Each entry has the following fields:
url: First 32 bits of the MD5 hash of the URL flag: Can be set to add or delete or query depending on the update UE3: update entry of type 3 in a packet. Each entry has the following fields:
web_rtr: Web router to which distance has decreased The first set of inter-process calls to be presented are those made by ALP module 404 to the URL roulting process 416. For each procedure, a description is provided to orient the reader.
void alpUrllnit (u_int32 name); PARAMETERS: DESCRIPTION: This procedure is called by ALP when the routing protocol starts up. Used for initialization of data structures, in one embodiment hash table structures for the routing table and the neighbor tables are intialized. void alpUrlCleanup (void); PARAMETERS: DESCRIPTION: This procedure is called by ALP when the routing protocol goes down. This procedure will free up memory and any other resources. void urlAlpRecvUpdate(u_int32 nbrAdr, u_int8*msg, u_int32 msgLen); PARAMETERS: nbrAdr
Address of neighbor that sent the message
URL message (opaque format for ALP)
Number of bytes in msg
web_rtr_changes
Array of records with the following fields:
web_rtr
Address of neighbor/web router
Cost of link of neighbor/distance to web router
The next hop neighbor
Set to 1 if the link to the neighbor came up, set to 0 if
the link to the neighbor was taken down
void urlAlpGetNewSeqNumber(AlpSeqNum * seqNum); PARAMETERS: seqNum
Sequence number to be returned
Address of a router running ALP
Buffer with opaque data
Neighbor Web router to which the message needs to be sent
void updateURL(array tuple[ ]); PARAMETERS: tuple is an array where each entry has the following fields cache
IP Address of the cache from which the add/delete
Port of the cache from which the add/delete inidcation
upper32
First 32 bits of the Md5 hash of the URL
TTL (time to live) value associated with the URL
Pointer to the cache which is closest
Pointer to cache's port
cacheAdr
Address of the cache from which the load inidcation originates
Port of cache from which the load inidcation originates
Present load of the cache
Although not discussed in detail above, there are some �house keeping� routines that run on a Web server. For example, a time to live (TTL) clearing daemon is responsible for deleting table entries after expiration of an associated TTL. In this way, stale entries are not kept so that only �live� information is returned to requesting clients and servers. The call from the TTL clearing daemon to the URL routing module 416 is as folls:
void delUrITTL(u_int32 url) PARAMETERS: url
void addUrlTTL(u_int32 url, u_int32 ttl) PARAMETERS: url
Time to live value for the url
void changeCacheNeighborState (u_int32 cacheAdr, u_int16 port, u_int18 upDown, u_int16 load); PARAMETERS: cacheAdr
Address of the cache for which the change has taken place
Port being used by the cache
Set to 1 if the link to the neighbor came up, set to 0 if the
Load of cache when it comes up
cache_entry2.counter □□□cache_entry2.counter − 1
cache_entry □ entry for (cache, port) in CT
URT[url].p_cache □□□address of □□local
tcache_entry □□□entry in CT□□corresponding to
nbr_entry □□□entry corresponding to web_rtr_changes[0].
web_rtr in NT
nbr_entry.l_cost □□□web_rtr_changes[0].distance
cache� entry.load
to closest� local_cache in CT
cache_entry.web� rtr, cache_entry
senderDistance □□update_entry.alp� dist + update_entry.load
2.web_rtr, cache� entry2.alp_dist )
cache_entry2 □ entry in CT corresponding to
currentDistance □□□cache_entry.alp_dist +
url □□update_entry.url
entry_distance □□cache_entry.alp_dist+ cache_entry.load
cache_entry2 □□□entry corresponding to URT[url].p_cache,
current_distance □□□cache_entry2.alp_dist + cache_entry2.load
closest_local_cache □□□local cache that offers smallest
current_distance □□□INFINITY
local_distance □□INFINITY
URT[url].p_cache □□□update_entry.cache
□□closet_local� cache.cache
URT[url].p_port □
closest� local_cache
cache_entry 2.port, cache� entry2.load, cache_entry2.web_rtr,
Thus a scheme for enabling the discovery of the caches and servers storing information objects distributed over computer networks, which can be implemented in hardware and/or software, has been described. It should be appreciated that some embodiments of the present invention make use of so-called network-layer URL (NURL) routing. This routing technique involves mapping requested URLs to unicast addresses, which are then used as an anycast IP address (i.e., a unicast address advertised by multiple, physically distinct points in an internet). See, e.g., Craig Partridge, Trevor Mendez, and Walter Milliken, �Host any casting service�, RFC 1546, November 1993. A system and method for using uniform resource locators (URLs) to map application layer content names to network layer anycast addresses, the aforementioned mapping, is disclosed in commonly-owned U.S. Provisional Application No. 60/200,511, entitled �System and Method for Using URLs to Map Application Layer Content Names to Network Layer Anycast Addresses�, filed Apr. 28, 2000 by J. J. Garcia-Luna-Aceves and Bradley R. Smith, now replaced by co-pending and commonly-owned U.S. patent application Ser. No. 09/844,857, entitled �System and Method for Using Uniform Resource Locators to Map Application Layer Content Names to Network Layer Anycast Addresses�, filed Apr. 26, 2001 by J. J. Garcia-Luna-Aceves and Bradley R. Smith, the complete disclosures of which is hereby incorporated by reference. Furthermore, a system and method for using network layer URL routing to locate the closest server carrying specific content (network-level routing of URLs) is disclosed in commonly-owned U.S. Provisional Application No. 60/200,402, entitled �System and Method for Using Network Layer URL Routing to Locate the Closest Server Carrying Specific Content (NURL Routing)�, filed Apr. 28, 2000 by J. J. Garcia-Luna-Aceves and Bradley R. Smith, now replaced by co-pending and commonly-owned U.S. patent application Ser. No. 09/844,856, entitled �System and Method for Using Network Layer Uniform Resource Locator Routing to Locate the Closest Server Carrying Specific Content�, filed Apr. 26, 2001 by J. J. Garcia-Luna-Aceves and Bradley R. Smith, the complete disclosures of which is hereby incorporated by reference.
With the route to the anycast cache server existing in the network infrastructure, a cache server processing a cache miss would like to transfer the content from the URL IP address. In an exemplary embodiment, in such a situation, the present invention resolves the anycast address to the server's real unicast address (which, by definition, uniquely identifies that server in the internet) before starting the download. In an exemplary embodiment, this is done by using an anycast address resolution protocol (AARP), which is disclosed in commonly-owned U.S. Provisional Application No. 60/200,403, entitled �System and Method for Resolving Network Layer Anycast Addresses to Network Layer Unicast Addresses (AARP)�, filed Apr. 28, 2000 by J. J. Garcia-Luna-Aceves and Bradley R. Smith, now replaced by co-pending and commonly-owned U.S. patent application Ser. No. 09/844,759, entitled �System and Method for Resolving Network Layer Anycast Addresses to Network Layer Unicast Addresses�, filed Apr. 26, 2001 by J. J. Garcia-Luna-Aceves and Bradley R. Smith, the complete disclosures of which is hereby incorporated by reference.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5088032Jan 29, 1988Feb 11, 1992Cisco Systems, Inc.Method and apparatus for routing communications among computer networksUS5115495Oct 18, 1988May 19, 1992The Mitre CorporationCommunications network system using full-juncture and partial-juncture station status information for alternate-path distance-vector routingUS5774668Jun 7, 1995Jun 30, 1998Microsoft CorporationSystem for on-line service in which gateway computer uses service map which includes loading condition of servers broadcasted by application servers for load balancingUS5822320Nov 18, 1996Oct 13, 1998Nec CorporationAddress resolution method and asynchronous transfer mode network systemUS6003030Oct 18, 1996Dec 14, 1999Intervu, Inc.System and method for optimized storage and retrieval of data on a distributed computer networkUS6006264 *Mar 30, 1998Dec 21, 1999Arrowpoint Communications, Inc.Method and system for directing a flow between a client and a serverUS6012067Mar 2, 1998Jan 4, 2000Sarkar; Shyam SundarMethod and apparatus for storing and manipulating objects in a plurality of relational data managers on the webUS6012068Jun 30, 1997Jan 4, 2000International Business Machines CorporationMedia manager for access to multiple media typesUS6052718Jan 7, 1997Apr 18, 2000Sightpath, IncReplica routingUS6092178Sep 3, 1998Jul 18, 2000Sun Microsystems, Inc.System for responding to a resource requestUS6097718Jan 2, 1996Aug 1, 2000Cisco Technology, Inc.Snapshot routing with route agingUS6108703May 19, 1999Aug 22, 2000Massachusetts Institute Of TechnologyGlobal hosting systemUS6115742 *Dec 11, 1996Sep 5, 2000At&T CorporationMethod and apparatus for secure and auditable metering over a communications networkUS6115752May 21, 1998Sep 5, 2000Sun Microsystems, Inc.System and method for server selection for mirrored sitesUS6130881Apr 20, 1998Oct 10, 2000Sarnoff CorporationTraffic routing in small wireless data networksUS6138162Feb 11, 1997Oct 24, 2000Pointcast, Inc.Method and apparatus for configuring a client to redirect requests to a caching proxy server based on a category ID with the requestUS6154777Jul 1, 1996Nov 28, 2000Sun Microsystems, Inc.System for context-dependent name resolutionUS6175869 *Apr 8, 1998Jan 16, 2001Lucent Technologies Inc.Client-side techniques for web server allocationUS6182224Jan 2, 1996Jan 30, 2001Cisco Systems, Inc.Enhanced network services using a subnetwork of communicating processorsUS6185619 *Nov 7, 1997Feb 6, 2001Genuity Inc.Method and apparatus for balancing the process load on network servers according to network and serve based policiesUS6201794Aug 21, 1997Mar 13, 2001Advanced Micro Devices, Inc.Network with efficient message routingUS6205477Oct 20, 1998Mar 20, 2001Cisco Technology, Inc.Apparatus and method for performing traffic redirection in a distributed system using a portion metricUS6205481Mar 17, 1998Mar 20, 2001Infolibria, Inc.Protocol for distributing fresh content among networked cache serversUS6249801Jul 15, 1998Jun 19, 2001Radware Ltd.Load balancingUS6256675May 6, 1998Jul 3, 2001At&T Corp.System and method for allocating requests for objects and managing replicas of objects on a networkUS6266706Apr 17, 1998Jul 24, 2001Effnet Group AbFast routing lookup system using complete prefix tree, bit vector, and pointers in a routing table for determining where to route IP datagramsUS6298381 *Oct 20, 1998Oct 2, 2001Cisco Technology, Inc.System and method for information retrieval regarding servicesUS6304913Nov 9, 1998Oct 16, 2001Telefonaktiebolaget L M Ericsson (Publ)Internet system and method for selecting a closest server from a plurality of alternative serversUS6314088Sep 19, 1997Nov 6, 2001Nec CorporationNode configuration setup system with servers hunting through connection-oriented network for client's dataUS6314465Mar 11, 1999Nov 6, 2001Lucent Technologies Inc.Method and apparatus for load sharing on a wide area networkUS6317778Nov 23, 1998Nov 13, 2001International Business Machines CorporationSystem and method for replacement and duplication of objects in a cacheUS6327252Oct 5, 1998Dec 4, 2001Alcatel Canada Inc.Automatic link establishment between distributed servers through an NBMA networkUS6327622 *Sep 3, 1998Dec 4, 2001Sun Microsystems, Inc.Load balancing in a network environmentUS6377551Aug 17, 1998Apr 23, 2002Nortel Networks LimitedQoS based route determination method for communications networksUS6397246Nov 13, 1998May 28, 2002International Business Machines CorporationMethod and system for processing document requests in a network systemUS6405252Aug 23, 2000Jun 11, 2002Speedera Networks, Inc.Integrated point of presence server networkUS6415323 *Dec 9, 1999Jul 2, 2002Fastforward NetworksProximity-based redirection system for robust and scalable service-node location in an internetworkUS6438652Oct 9, 1998Aug 20, 2002International Business Machines CorporationLoad balancing cooperating cache servers by shifting forwarded requestUS6449647Sep 21, 1999Sep 10, 2002Cisco Systems, Inc.Content-aware switching of network packetsUS6553376Nov 16, 1999Apr 22, 2003Infolibria, Inc.Efficient content server using request redirectionUS6574663 *Aug 31, 1999Jun 3, 2003Intel CorporationActive topology discovery in active networksUS6578066Sep 17, 1999Jun 10, 2003Alteon WebsystemsDistributed load-balancing internet serversUS6601098Jun 7, 1999Jul 29, 2003International Business Machines CorporationTechnique for measuring round-trip latency to computing devices requiring no client-side proxy presenceUS6687731Jun 8, 1998Feb 3, 2004Telia AbArrangement for load sharing in computer networksUS6785704Jul 3, 2000Aug 31, 2004Fastforward NetworksContent distribution system for operation over an internetwork including content peering arrangementsUS6917985Mar 9, 2001Jul 12, 2005The Regents Of The University Of CaliforniaCore assisted mesh protocol for multicast routing in ad-hoc NetworksUS6965938Sep 7, 2000Nov 15, 2005International Business Machines CorporationSystem and method for clustering servers for performance and load balancingUS7020083Oct 29, 2001Mar 28, 2006The Regents Of The University Of CaliforniaMethod for improving TCP performance over wireless linksUS7162539Mar 15, 2001Jan 9, 2007Adara Networks, Inc.System and method for discovering information objects and information object repositories in computer networksUS7200111Aug 30, 2001Apr 3, 2007The Regents Of The University Of CaliforniaMethod for improving TCP performance over wireless linksUS20010056416Mar 15, 2001Dec 27, 2001J.J. Garcia-Luna-AcevesSystem and method for discovering information objects and information object repositories in computer networksUS20020004846Apr 26, 2001Jan 10, 2002Garcia-Luna-Aceves J. J.System and method for using network layer uniform resource locator routing to locate the closest server carrying specific contentUS20020007413Apr 26, 2001Jan 17, 2002Garcia-Luna-Aceves JjSystem and method for using a mapping between client addresses and addresses of caches to support content deliveryUS20020010737Apr 26, 2001Jan 24, 2002Garcia-Luna-Aceves J. J.System and method for using uniform resource locators to map application layer content names to network layer anycast addressesUS20020016860Apr 26, 2001Feb 7, 2002Garcia-Luna-Aceves J. J.System and method for resolving network layer anycast addresses to network layer unicast addressesUS20020026511Apr 26, 2001Feb 28, 2002Garcia-Luna-Aceves JjSystem and method for controlling access to content carried in a caching architectureUS20020133537 *Mar 12, 2001Sep 19, 2002Whizz Technology Ltd.Server cluster and server-side cooperative caching method for use with sameUS20030101278Sep 10, 2002May 29, 2003J.J. Garcia-Luna-AcevesSystem and method for directing clients to optimal servers in computer networksEP0817444A2Jun 30, 1997Jan 7, 1998Sun Microsystems, Inc.System for context-dependent name resolutionEP0959601A1May 12, 1999Nov 24, 1999Sun Microsystems, Inc.A system and method for server selection for mirrored sitesWO1998057275A2Jun 8, 1998Dec 17, 1998Telia AbArrangement for load sharing in computer networksWO1999040514A1Feb 9, 1999Aug 12, 1999Sandpiper Networks IncOptimized network resource locationWO2001018641A1Sep 1, 2000Mar 15, 2001Fastforward Networks IncA proximity-based redirection system for robust and scalable service-node location in an internetwork* Cited by examinerNon-Patent CitationsReference1A. Chankhunthod, P. Danzing, C. Neerdaels, M. Schwartz, and K. Worrell, "A Hierarchical Internet Object Cache," Proc. USENIX Technical Conference 96, San Diego, California, Jan. 1996.2A. Duda and M.A. Sheldon, "Content Routing in Networks of WAIS Servers," Proc. IEEE 14th International Conference on Distributed Computing Systems, Jun. 1994.3A. Heddaya and S. Mirdad, "WebWave: Globally Load Balanced Fully Distributed Caching of Hot Published Documents," Proc. IEEE 17th International Conference on Distributed Computing Systems, Baltimore, Maryland, May 1997.4A. Heddaya and S. Mirdad, "WebWave: Globally Load Balanced Fully Distributed Caching of Hot Published Documents," Technical Report BU-CS-96-024, Boston University, Computer Science Department, Oct. 1996.5Ari Luotonen, Henrik Frystyk Nielsen, and Tim Berbers-Lee. Cern httpd. http://www.w3.org/Daemon, Jul. 1996.6B.S. Michel, K. Nikoloudakis, P. Reiher, and L. Zhang, "URL Forwarding and Compression in Adaptive Web Caching," Proc. IEEE Infocom 2000, Tel Aviv, Israel, Apr. 2000.7Bruce Schneier, "Applied Cryptography: Protocols, Algorithms, and Source Code in C," Second Edition, Table of Contents, pp. 30-31, 34-44, 466-474, 483-502, and 10 page errata sheet (1996).8Craig Partridge, Trevor Mendez, and Walter Milliken, "Host Anycasting Service," Network Working Group, RFC 1546 (Nov. 1993).9D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin, and R. Panigrahy, "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web," Proc. 29th ACM Symposium on Theory of Computing (STOC 97), El Paso, Texas, 1997.10D. Karger, Sherman, A. Berkheimer, B. Bogstad, R. Dhanidina, K. Iwamoto, B. Kim, L. Matkins, and Y. Yerushalmi, "Web Caching with Consistent Hashing," Proc. 8th International World Wide Web Conference, Toronto, Canada, May 1999.11D. Small and W.W. Chu, "A Distributed Data Base Architecture for Data Processing in a Dynamic Environment," Proc. COMPCON 79 Spring.12D. Wessels and K. Claffy, "Internet Cache Protocol (ICP), Version 2," RFC 2186, Sep. 1997.13D. Wessels, "Squid Internet Object Cache," http://www.squid-cache.org/, Aug. 1998.14D.G. Thaler and C.V. Ravishankar, "Using Name-Based Mappings To Increase Hit Rates," IEEE/ACM Transaction on Networking, vol. 6, No. 1 (Feb. 1998).15Dykes, Sandra G., et al., "An Empirical Evaluation of Client-side Server Selection Algorithms," IEEE Infocom. vol. 3, Mar. 2000, pp. 1361-1370.16G. Chiu, C.S. Rahgavendra, and S.M. Ng, "Resource Allocation with Load Balancing Consideration in Distributed Computing Systems," Proc. IEEE Infocom 89, Ottawa, Ontario, Canada, Apr. 1989, pp. 758-765.17Garcia-Luna-Aceves, J. J., et al. "The Core-Assisted Mesh Protocol," IEEE Journal on Selected Areas in Communications, vol. 17, No. 8, Sep. 8, 1999, 15 pages.18H.L. Morgan and K.D. Levin, "Optimal Program and Data Locations in Computer Networks," Communications of the ACM, vol. 20, No. 5, May 1977.19http://www.cache.ja.net/workshop./papers.html (Oct. 3, 2001), 6 pages.20J. Garcia-Luna-Aceves and M. Spohn, "Scalable Link-State Internet Routing," ICNP, Sixth International Conference on Network Protocols (ICNP'98), Austin, Texas, pp. 52-61 (Oct. 14-16, 1998).21J.D. Guyton and M.F. Schwartz, "Locating Nearby Copies of Replicated Internet Servers," Proc. ACM SIGCOMM 95 Conference, Cambridge, Massachusetts, pp. 288-298 (Aug. 1995).22J.D. Guyton and M.F. Schwartz, "Locating Nearby Copies of Replicated Internet Servers," Technical Report CU-CS-762-95, Department of Computer Science, University of Colorado-Boulder, Feb. 1995.23Jueneman, Robert R., "Novell Certificate Extension Attributes," Tutorial and Detailed Design, Version 0.998 (Aug. 7, 1998), 98 pages.24K.W. Ross, "Hash Routing for Collections of Shared Web Caches," IEEE Network, vol. 11, No. 6, Nov. 1997, pp. 37-44.25Levine, Brian Niel, et al., "Improving Internet Multicast with Routing Labels," 10 pages.26Levine, Brian Niel, et al., "New Routing Services for Internet Multicast," Apr. 30, 1998, 17 pages.27M.A. Sheldon, A. Duda, R. Weiss, J.W. O'Toole, Jr., and D.K. Gifford, "A Content Routing System for Distributed Information Servers," Proc. Fourth International Conference on Extending Database Technology, Mar. 1994.28P. Rodriguez and E.W. Briesack, "Continuous Multicast Push of Web Documents over The Internet," IEEE Network Magazine, vol. 12, No. 2, pp. 18-31, 1998.29Pablo Rodriguez, Ernst W. Biersack, and Keith W. Ross, "Improving the WWW: Caching or Multicast?," Institut Eurecom 2229, Route Computer Networks and ISDN Systems, pp. 1-17 (Mar. 30, 1998).30PCT International Search Report, PCT/US02/28961, mailed Dec. 10, 2002, 4 Pages.31R. Tewari, "Architectures and Algorithms for Scalable Wide-area Information Systems," Ph.D. Dissertation, Chapter 5, Computer Science Department, University of Texas at Austin, Aug. 1998.32R. Tewari, M. Dahlin, H.M. Vin, and J.S. Kay, "Design Considerations for Distributed Caching on the Internet," Proc. IEEE 19th International Conference on Distributed Computing Systems, May 1999.33Renu Tewari, Michael Dahlin, Harrick M. Vin, and Jonathan S. Kay, "Design considerations for distributed caching on the internet," Technical report, Department of Computer Sciences, University of Texas Austin, http://www.cs.utexas.edu/users /UTCS/techreports/ (Oct. 1998).34Robert L. Carter, et al., "On the network impact of dynamic server selection," Computer Networks 31, pp. 2529-2558 (1999).35S. Gadde, M. Rabinovich, and J. Chase, "Reduce, reuse, recycle: An approach to building large Internet caches," in Proc. 6th Workshop Hot Topics in Operating Systems (HotOS-VI), Cape Cod, MA, May 1997, pp. 93-98.36S. Mahmoud and J.S. Riordon, "Optimal Allocation of Resources in Distributed Information Networks," ACM Transactions on Data Base Systems, vol. 1, No. 1, pp. 60-7S (Mar. 1976).37Sandra G. Dykes, et al., "An Empirical Evaluation of Client-side Server Selection Algorithms," IEEE Infocom, vol. 3, pp. 1361-1370 (Mar. 2000).38Smith, Bradley R., et al, "Federated Networks Bootstrap Services," Nov. 8, 1998, 2 pages.39T. Berners-Lee, "Information Management: A Proposal," CERN Document, (Mar. 1989, May 1990).40V. Valloppillil and J. Cohen, "Hierarchical HTTP Routing Protocol," Internet Draft, http://www.nlanr.net/Cache/ICP/draft-vinod-icp-traffic-dist-00.txt (Apr. 21, 1997).41W.W. Chu, "Optimal File Allocation in a Multiple Computer System," IEEE Transactions on Computers, Oct. 1969.42W.W. Chu, "Performance of File Directory Systems for Data Bases in Star and Distributed Networks," Proc. National Computer Conference, 1976, pp. 577-587.43 *Y. Rekhter and T. Li, A border gateway protocol 4 (BGP-4). RFC 1771. Mar. 1995.44Z. Fei, S. Bhattacharjee, E.W. Zegura, and M.H. Ammar, "A Novel Server Selection Technique for Improving The Response Time of a Replicated Service," Proc. IEEE Infocom 98, Mar. 1998, pp. 783-791.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS7664876Sep 10, 2002Feb 16, 2010Adara Networks, Inc.System and method for directing clients to optimal servers in computer networksUS8166197 *Oct 25, 2005Apr 24, 2012Oracle International CorporationMultipath routing processUS8219706 *Nov 14, 2008Jul 10, 2012At&T Intellectual Property I, LpInterdomain network aware peer-to-peer protocolUS8423666Dec 22, 2009Apr 16, 2013Adara Networks, Inc.System and method for directing clients to optimal servers in computer networksUS8433787Dec 22, 2009Apr 30, 2013Adara Networks, Inc.System and method for directing clients to optimal servers in computer networksUS8495359 *Jun 2, 2010Jul 23, 2013NetAuthoritySystem and method for securing an electronic communicationUS8533359Jun 7, 2012Sep 10, 2013At&T Intellectual Property I, L.P.Interdomain network aware peer-to-peer protocolUS8572214Aug 3, 2006Oct 29, 2013Adara Networks, Inc.System and method for discovering information objects and information object repositories in computer networksUS8619600 *May 31, 2007Dec 31, 2013Centurylink Intellectual Property LlcSystem and method for establishing calls over a call path having best path metricsUS8626925 *Dec 16, 2005Jan 7, 2014Panasonic CorporationSystems and methods for providing a selective multicast proxy on a computer networkUS8671134 *Nov 29, 2010Mar 11, 2014International Business Machines CorporationMethod and system for data distribution in high performance computing clusterUS8706906Mar 8, 2012Apr 22, 2014Oracle International CorporationMultipath routing processUS8756340 *Dec 20, 2007Jun 17, 2014Yahoo! Inc.DNS wildcard beaconing to determine client location and resolver load for global traffic load balancingUS20070094361 *Oct 25, 2005Apr 26, 2007Oracle International CorporationMultipath routing processUS20070143458 *Dec 16, 2005Jun 21, 2007Thomas MilliganSystems and methods for providing a selective multicast proxy on a computer networkUS20090164614 *Dec 20, 2007Jun 25, 2009Christian Michael FDns wildcard beaconing to determine client location and resolver load for global traffic load balancingUS20100125643 *Nov 14, 2008May 20, 2010At&T Corp.Interdomain Network Aware Peer-to-Peer ProtocolUS20100325423 *Jun 2, 2010Dec 23, 2010Craig Stephen EtchegoyenSystem and Method for Securing an Electronic CommunicationUS20110138396 *Nov 29, 2010Jun 9, 2011International Business Machines CorporationMethod and system for data distribution in high performance computing clusterUS20120102220 *Oct 20, 2010Apr 26, 2012Microsoft CorporationRouting traffic in an online service with high availability* Cited by examinerClassifications U.S. Classification709/238, 709/242International ClassificationG06F15/173, G06F15/16Cooperative ClassificationH04L67/1002, H04L67/1014, H04L67/1006, H04L67/1023, H04L67/1008, H04L67/101, G06F17/30902, G06F12/1483, H04L61/1582, H04L12/18, H04L29/12009European ClassificationH04L29/12A, H04L12/18, H04L29/08N9A, H04L29/08N9A1J, G06F12/14D2, G06F17/30W9C, H04L29/08N9A1A, H04L29/08N9A1E, H04L29/08N9A1C, H04L29/08N9A1B, H04L61/15JLegal EventsDateCodeEventDescriptionDec 26, 2012FPAYFee paymentYear of fee payment: 4Mar 26, 2009ASAssignmentOwner name: ADARA NETWORKS, INC., (A FLORIDA CORPORATION), CALFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:RAJU, JYOTI;SMITH, BRADLEY R.;REEL/FRAME:022459/0887;SIGNING DATES FROM 20060520 TO 20061108Owner name: ADARA NETWORKS, INC., CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:GARCIA-LUNA-ACEVES, J.J.;REEL/FRAME:022459/0921Effective date: 20090323Free format text: CHANGE OF ADDRESS;ASSIGNOR:ADARA NETWORKS, INC.;REEL/FRAME:022459/0885RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google