# US 2004/0083289 A1 · Method and apparatus for distributing requests among a plurality of resources

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2004/0083289 A1
- Document ID: US20040083289A1
- Status: Published application
- Kind: A1
- Application number: 10/417,427
- Filed: 2003-04-16
- Published: 2004-04-29
- Earliest claimed: 1998-03-13
- Assignees: Massachusetts Institute of Technology
- Inventors: David Karger; Eric Lehman; F. Thompson Leighton; Matthew Levine; Daniel Lewin; Rina Panograhy
- Web page: https://patentgrep.com/patent/US20040083289A1

## CPC

- G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals}
- H04L 67/10: in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46)
- H04L 67/101: based on network conditions
- H04L 67/1019: Random or heuristic server selection
- H04L 67/1021: based on client or server locations
- H04L 67/1023: based on a hash applied to IP addresses or costs
- H04L 67/568: Storing data temporarily at an intermediate stage, e.g. caching
- H04L 67/1001: for accessing one among a plurality of replicated servers
- H04L 67/10015: {Access to distributed or replicated servers, e.g. using brokers}
- H04L 69/329: in the application layer [OSI layer 7]
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

The invention relates to a method and apparatus for distributing a request to one of a plurality of resources. A request is mapped to a location in mathematical mapping space. Each of the plurality of resources is mapped to a respective location or locations in the mathematical mapping space. The request is allocated to one of the resources based on a mathematical relationship between the request location and the resource location in the mathematical mapping space. An apparatus for distributing a request to one of a plurality of resources includes the plurality of resources and an input receiving a resource request. A mapper in communication with the input maps the request to a request location in a mathematical mapping space and maps each of the plurality of resources to at least one resource locations in the mathematical mapping space. A distributor distributes the request to one of the plurality of resources in response to a mathematical relationship between the locations of the request and resources in the mathematical mapping space. The invention also relates to a method and apparatus for requesting data from one of a plurality of servers. An virtual network of nodes is generated in response to a data request. A first node on the virtual network of nodes is chosen randomly, and a path generated from the first node to the root on the virtual network. At least one node on the path is mapped to a respective one of the plurality of servers and data is requested from a server. The node may be mapped to the server using the method and apparatus for distributing a request to one of a plurality of resources of the present invention.

## Claims

### Claim 1

A method for distributing an information request to a server resource, comprising the steps of:
hashing the request to a request location in a circular mathematical mapping space;
hashing the resource to a location in the circular mathematical mapping space;
matching the request to the resource based on a mathematical relationship between the request location and the resource location in the mathematical mapping space; and allocating the request to the resource.

### Claim 2

A method for querying one of a plurality of servers, comprising the steps of:
generating an interconnected network of nodes in response to a data request;
choosing a first node on the network of nodes;
generating a route from the first node to a last node;
identifying one of the plurality of servers to be the final server;
determining the distance of each of the plurality of servers;
identifying a subset of the plurality of servers to be a distance less than or equal to the final server;
mapping the first node on the route to one of the subset of the plurality of servers and mapping the last node to the final server; and
querying the one of the plurality of servers mapped to the first node on the route.

### Claim 3 (depends on 2)

The method of claim 2 wherein the querying step comprises transmitting the query and a sequence of nodes through which the query should be directed.

### Claim 4 (depends on 3)

The method of claim 3 wherein the querying step further comprises transmitting a route of servers mapped to the nodes on the route from the first node to the last node.

### Claim 5 (depends on 4)

The method of claim 4 wherein the query step further comprises transmitting a request from a client to the server.

### Claim 6 (depends on 5)

The method of claim 5 wherein the mapping step comprises calculating a hash function.

### Claim 7 (depends on 6)

The method of claim 6 wherein the mapping step further comprises:
mapping the first node to a first node location in a mathematical mapping space;
mapping each of the subset of the plurality of servers to a respective at least one server location in the mathematical mapping space;
allocating the first node to one of the subset of the plurality of servers based on a mathematical relationship between the first node location and each of the server locations in the mathematical mapping space.

### Claim 8 (depends on 2)

The method of claim 2 wherein the identifying step comprises identifying a subset of the plurality of servers to be a distance less than or equal to the final server only if the ratio of servers to clients is smaller than a predetermined value.

### Claim 9 (depends on 2)

The method of claim 2 wherein the determining step comprises determining distance based on communications latency.

### Claim 10 (depends on 2)

The method of claim 2 wherein the determining step comprises determining distance based on the number of network hops.

### Claim 11

An apparatus for querying one of a plurality of servers, comprising:
an interface for receiving a query;
a router in communication with the input for choosing a first node on a virtual network and for generating at least one route of nodes in response to the query;
distance logic for determining the distance of each of the plurality of servers and identifying a subset of the plurality of servers to be an acceptable distance from the apparatus;
an allocator in communication with the path generator for allocating nodes on the route to a respective one of the subset of the plurality of servers; and
an output in communication with the allocator for requesting data from the respective one of the plurality of servers to the nodes on the route.

### Claim 12 (depends on 11)

The method of claim 11 wherein the distance logic determines distance based on communications latency.

### Claim 13 (depends on 11)

The method of claim 11 wherein the distance logic determines distance based on the number of network hops.

### Claim 14 (depends on 11)

The method of claim 11 wherein the distance logic identifies a subset of the plurality of servers to be a distance less than or equal to a final server only if the ratio of servers to clients is smaller than a predetermined value.
