Efficiently determining if the identifier of a message received at a network node could be equivalent to one of a set of predetermined identifiers is useful in numerous networking applications. One such application is verifying that the sender of a message received at a peer on the network is authorized to receive a service requested in the message. For example, a first peer that is a proxy server receives a message from a user over a first network. The message requests service from a second peer, a resource that provides the requested service, on a second network. The first peer (the proxy server) sends the message to the second peer (the resource), and the resource provides the requested service to the user. This simple scenario is most likely to occur when the service provided by the resource is freely available to all users.
However, when the service is not freely available, the user request must be checked to determine if the resource is authorized to provide service in response to the request. For example, a service is sold by subscription. When a request is received, it must be determined if the request correspond to a valid subscription. If it does, then the resource provides the service. If it does not so correspond, then the resource denies the service.
One known method for checking if a resource is authorized to provide service based upon a request is to receive all requests for service at the resource, and determine the authorization of each request before responding. This can disadvantageously overburden the resource, particularly when a large number of requests are received and have to be checked. Another known method is to check the requests at an intermediate point between the requesting user (the requester) and the resource, such as the proxy server. A request is only forwarded to a resource if the proxy server determines that the request is authorized, thereby mitigating the burden on the resource by appropriately routing each message based upon its authorization. This, however, introduces the problems of distributing and maintaining the accuracy of authorization data (such as subscriber lists) to several proxy servers, which can disadvantageously generate a substantial amount of network traffic. Further, having to check every request for authorization against a list can be time consuming and burdensome. These problems are especially severe for services with large, dynamic (rapidly changing) subscriber bases. These problems are further exacerbated if a proxy server is configured to receive requests for many different services, each with its own subscriber list. When there are several proxy servers in a large network that are so configured, maintaining the accuracy of authorization criteria (such as subscriber lists) for all services across all proxy servers can be impractical.
In certain known systems, a user sends a request to a peer, which forwards the request to a proxy server, which in turn forwards the request to a resource. Such a system is shown in FIG. 1. Users U1 101, U2 102 and U3 103 send messages through network alpha 104 to peer A 105 requesting service from a resource B 106 on network beta 107. Only U2 102 and U3 103 are subscribers to resource B 106. Proxy server C 108 is connected to both network alpha 104 and network beta 107, and processes requests for service directed to resource B from users on network alpha 104. One known method provides authorization criteria (e.g., subscriber lists) to Peer A 105, which carries out the authorization routing function rather than the proxy server C 108.
Peer A first registers (or logs on) to resource B 106 through peer C 108. Resource B provides peer A 105 with a sorted list of subscriber entries that comprise network addresses of subscribing users U2 and U3. A request for service from resource B is sent from a user to peer A. The request includes a user identifier, such as the user's network address. The user's address is checked against the list of subscriber addresses at Peer A. If the user's network address matches a subscriber address, the user's request is forwarded to proxy server C 108 as an authorized request for service. Proxy server C 108 then forwards the request to resource B 106. If no match is found, the message is not forwarded to proxy server B, and a return message sent to the user indicating a denial of service. Devolving the authorization routing function to the peer advantageously reduces the burden on the proxy server, and can be more efficient when the peer serves a homogeneous and relatively small community of user subscribers. In other words, this method can be efficient when the number of users from which the peer receives requests for service is relatively small, and the number of different services the peer must authorize is also small. However, this known method does not scale well as the number of peers and users increases. The sizes of subscriber table in peer A 105 grows with the number of subscribers to resource B 106. Maintaining the accuracy of such subscriber tables for a large number of peers can be impractical, especially when the subscriber base is dynamic. A substantial amount of message traffic is disadvantageously generated between proxy server B and peer A as the subscriber table in Peer A is sent and/or updated frequently to reflect changes in the authorizations of various users. Larger subscriber tables are also more computationally expensive to search, burdening the peer and taking up resources needed for other tasks.
Another known system uses specialized authorization servers known as "membership servers" to carry out the authorization function, as shown in FIG. 2. Membership server 201 stores subscriber lists 208 and is connected to network alpha 202. When peer A 203 receives a request from a user 204 for service from resource B 205 connected to network beta 206, peer A 203 queries the membership server 201. Membership sever 201 consults the appropriate subscriber list 208 stored in computer readable memory to determine if the requesting user 204 is authorized to access resource B 205 for the requested service. Membership server 201 sends a message to peer A 203 indicating whether the requesting user 204 is authorized. Peer A 203 then caches the user's identifier and authorization for future reference. If the user is authorized, peer A 203 forwards the user request to resource B 205 through proxy server C 207. This method can be more efficient than maintaining current subscriber lists on each peer that receives requests from users. However, this known system also disadvantageously fails to scale well in large networks. A substantial amount of network traffic is disadvantageously generated between peer and membership server in determining authorization, and in maintaining the accuracy of subscriber lists when more than one membership server is needed.
Another disadvantage of known systems is that extensive memory resources are required to maintain subscriber lists, especially in large systems with many users. In certain known systems, users are identified by their user identifiers. For example, an Internet Protocol (IP) network address is represented by a string of 32 bits. A bit string of this length may be necessary for a network to distinguish users, but is unnecessarily long for the purpose of determining if a user is authorized to access a resource. On the other hand, a resource needs only enough information to distinguish the predefined, limited number of authorized users from the rest of all users. Relying upon an unnecessarily long bit string (such as a IP network address) to distinguish authorized users is expensive both in memory usage and in the processing time needed to search lists of such bit strings. This problem is particularly severe when a relatively large number of users subscribe to a given resource. A better system would be able to distinguish authorized users from unauthorized users while using substantially fewer bits per user that are easier to search than long lists of long bit strings.
A known partial solution to this is to represent a user identifier with an integer by using a hash function. A hash function maps a string (such as a network address) to an integer. Although hash functions realize some savings in memory resources and processor search time, they still impose a substantial overhead for large systems with many users.
Thus, known systems that distinguish authorized users from unauthorized users disadvantageously require substantial memory resources and processor time to establish, maintain and search subscriber lists. Further, they can generate substantial amounts of network traffic to distribute and maintain the coherence and/or accuracy of authorization databases.
A better system would distinguish authorized users from unauthorized users while requiring less memory and processor search time. Further, such a system when implemented for a large network would not concentrate the authorization function at the resource. At least part of the authorization function would be distributed over the network. In spite of being distributed, the accuracy of authorization criteria such as subscriber lists would be easy to maintain because such lists would be represented in a compact form, rather than as searchable lists of authorized users. A better system would also be tolerant of authorization errors. By relaxing the requirement of making a completely accurate authorization decision at a single point, less accuracy could be tolerated in the distributed authorization criteria, thereby advantageously decreasing the network traffic needed to keep it sufficiently accurate. The better system would scale well as the network size increased, and provide a more efficient way to handle requests for service based upon their authorization.