Electrical computers and digital processing systems: multicomput – Computer network managing – Network resource allocating
Reexamination Certificate
1998-06-02
2003-04-22
Maung, Zarni (Department: 2142)
Electrical computers and digital processing systems: multicomput
Computer network managing
Network resource allocating
C709S225000, C709S216000
Reexamination Certificate
active
06553420
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to allocating resource requests to the available resources. More specifically, the invention relates to distributing information requests to servers capable of storing and providing the requested information.
BACKGROUND OF THE INVENTION
In large distributed information systems there are servers that store information and there are clients that request information. The World Wide Web (“Web”) is an example of a distributed information system. There are web sites, which act as servers, and there are clients, which are computers used by people to obtain information from the servers. The users request information from the web sites and the web sites respond to the requests by providing the requested information in the form of data, documents, files, or web pages.
Immense growth of the Web places great demands on the infrastructure of the Internet that provides the physical connections for the Web. Service providers invest vast sums of money in Internet infrastructure in an attempt to provide acceptable performance despite increasing data demand. Acceptable performance generally implies little or no delay in accessing information. Two causes of delay are heavy communication loading a part of a network and a large number of requests loading a particular server. When part of the network becomes congested with too much traffic, communication over that part of the network becomes unreliable and slow. Similarly, when too many requests are directed at a single server, the server becomes overloaded, or “swamped.”
One of these problems can cause the other, in part because network software is typically designed to repeat requests that are not responded to promptly. For example, if a server is overloaded, it will not respond to requests quickly, and requests may be resent, thereby increasing network traffic. If a network is overloaded, a request may not reach a server quickly, and a duplicate request may be sent to the server before the server had a chance to respond to the first request, thereby increasing the load on the server. Both network overload and server overload lead to delays in retrieving information.
A server can become overloaded for various reasons. A server storing a few documents that have very high access rates can become overloaded. An example of this kind of server is a web site that becomes very popular such as a site reporting results of a popular sports event. A server responsible for such a site can become overloaded with a large volume of requests for a one or a small number of documents containing the latest information on the event. Another type of server that can become overloaded is a server storing a large number of documents each of which is accessed at normal or even relatively low access rates. The server becomes overloaded as it attempts to serve a large number of requests for many different documents. An example of this kind of server is a server for a large organization, such as a library, that serves a vast number of documents that are accessed on a regular basis.
A general strategy employed to reduce both network traffic and overloaded servers is replication accomplished by caching. Copies of frequently requested documents can be stored throughout the network, thereby spreading the work of serving the documents across several servers. In one approach, several clients share a cache server in a manner that is transparent to the people using it. Client requests are forwarded through the cache server, which keeps copies of frequently requested documents and attempts to satisfy requests with a cached copy. If the cache server has a copy of the document, then the request can be answered immediately with the requested document. If the cache server does not have a copy, then the cache server can request a copy of the document from the original site. When the cache server receives a copy of the document from another cache server or from the original site for the document, it can then answer the client's request. Subsequent requests for that document can be serviced by the cache because it has a copy of the document. Thus, the load on the original site for the document is reduced because the original site does not need to be involved in every request.
Referring to
FIG. 1A
, three clients, Client One
110
, Client Two
111
, and Client Three
112
, each request documents Doc
1
, Doc
2
, and Doc
3
respectively via Cache Server A
100
. The cache server answers all three of these requests in a manner that is transparent to the users. If Server A
100
does not have the documents requested by Client One
110
, Client Two
111
, and Client Three
112
, it requests the documents from the Original Sites
102
,
104
for the documents. Once it receives the documents it sends the documents to the Clients
110
-
112
.
Caching can reduce network traffic if the cached copy is close, in the network topology sense, to the requester because fewer network links and resources are used to retrieve the information. Caching can also relieve an overloaded server because some of the requests that would normally be routed to the original site can be served by a cache server, and so the number of requests made of the original site is reduced. There is a tradeoff of a greater performance benefit if more clients share the same cache server that is balanced against an increased likelihood that the cache server itself will become overloaded.
One approach to solving this dilemma is to use a group of servers that function together as a cache. Responsibility for answering requests is divided among the group. There are many ways to divide responsibility among the group of servers. One way is to have a client's request for a document be directed to an arbitrary one of the servers of the group of cache servers. If a copy of the document is stored in that server, it is transmitted to the client. If a copy is not stored in that server, the request is forwarded to the original site of the document. This approach divides the load among the servers, thereby preventing overload of any particular server. A client needs to know which servers are available, but the client does not need information about the servers to choose one. One disadvantage of this approach is that each of the servers will request each document from the original site for that document. This could load the original site as the number of cache servers increases.
Alternatively, the server could, if it does not have a copy of the document, first forward the request to the other cache servers. One disadvantage of this technique is that as the number of participating servers grows, the number of messages between the cache servers can become problematic.
Another approach also uses a group of servers but allocates responsibility for documents to particular servers. As part of this approach, the client is informed about the allocation of documents to servers so it can address a request to the server with responsibility for that document. Instead of arbitrarily choosing a cache, a client chooses the cache server allocated to the document requested. For this approach to be successful, it cannot be unduly burdensome on the client to determine which cache server to direct a document request. It is also necessary to balance the load appropriately among the caches. For example, even if all documents are accessed by clients at the same rate, if some caches contain more documents than others, those caches will have more requests to service, and may become overloaded.
In the context of caching, it would be unduly burdensome to maintain a list of all the documents available in the cache servers. Such a list would have to be maintained as documents were added and deleted from the original site. An alternative approach is for clients to use a standard hash function to determine from which server to request a document. In
FIG. 1B
, a standard hash function (h) is used by the clients to choose among three cache servers. Client One
110
requests Doc
1
from Server A
100
since h(Doc
1
)=Serv
Karger David
Lehman Eric
Leighton F. Thomson
Levine Matthew
Lewin Daniel
Cardone Jason D.
Massachusetts Institute of Technology
Maung Zarni
Testa Hurwitz & Thibeault LLP
LandOfFree
Method and apparatus for distributing requests among a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for distributing requests among a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for distributing requests among a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3047777