US6505254B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods and apparatus for routing requests in a network
Assignee: Cisco Technology Inc
•
Filing: 1999-04-19
•
Granted: 2003-01-07
•
Expires: 2019-04-19
Abstract
Abstract A system and method of routing requests received from client computers. The client computer processor is redirected to a router for which the address is within the preferred coverage zone. If a router is not identified for which the address is within a preferred coverage zone, but a router other than the router that received the request is identified for which the address is within a regular coverage zone, the processor is redirected to the router for which the address is within the regular coverage zone. If a message is transmitted from a router behind a firewall to a router outside the firewall, and then a request for data is received from a processor behind the firewall, the processor is redirected to the address of the router. Routers register themselves dynamically into a hierarchy. In another alternative embodiment, a service request from a particular client computer is serviced immediately by the root router rather than redirected to another router. The root router then attempts to find the best source server for the client computer. The next service request from the client computer is dispatched directly by the root router to this best router.
Inventors
- 👤 Kirk L. Johnson
- 👤 M. Franz Kaashoek
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 16:47
CPC Classifications
H; H04; H04L; H04L63/00; H04L63/02; H04L63/0209; H04L45/00; H04L45/02; H04L45/04
Claims Analysis
Total Claims: 46
Claim 1
Independent Claim
302 words
A replica routing system, comprising: a processor; and a plurality of routers; the processor being programmed to transmit a request to one of the routers; the router being programmed to perform steps of: A) to receive the request; B) to compare an address from which the request purports to originate with coverage zone information for the router that received the request and a hierarchy of a plurality of routers that are its progeny, the coverage zone information being stored in a database associated with the router that received the request, the coverage zone information for the router that received the request including a preferred coverage zone and a regular coverage zone, the preferred coverage zone being a restrictive set of addresses for which the router believes that it would be at least as good as any other router at serving a request from addresses in the restrictive set of addresses, the regular coverage zone is a larger set of addresses than the preferred coverage zone for which the router will be willing to serve if the request came from one of the larger set addresses, but for which the router does not know whether it is an optimal router; C) if the router that received the request is not within a preferred coverage zone as identified in step B, to redirect the processor to a router for which the address is within the preferred coverage zone; and D) if a router is not identified in step C for which the address is within a preferred coverage zone, but a router other than the router that received the request is identified in step B for which the which the address is within a regular coverage zone, to redirect the processor to the router for which the address is within the regular coverage zone.
Claim 2
Dependent Claim
302 words
A replica routing system, comprising: a processor; and a plurality of routers; the processor being programmed to transmit a request to one of the routers; the router being programmed to perform steps of: A) to receive the request; B) to compare an address from which the request purports to originate with coverage zone information for the router that received the request and a hierarchy of a plurality of routers that are its progeny, the coverage zone information being stored in a database associated with the router that received the request, the coverage zone information for the router that received the request including a preferred coverage zone and a regular coverage zone, the preferred coverage zone being a restrictive set of addresses for which the router believes that it would be at least as good as any other router at serving a request from addresses in the restrictive set of addresses, the regular coverage zone is a larger set of addresses than the preferred coverage zone for which the router will be willing to serve if the request came from one of the larger set addresses, but for which the router does not know whether it is an optimal router; C) if the router that received the request is not within a preferred coverage zone as identified in step B, to redirect the processor to a router for which the address is within the preferred coverage zone; and D) if a router is not identified in step C for which the address is within a preferred coverage zone, but a router other than the router that received the request is identified in step B for which the which the address is within a regular coverage zone, to redirect the processor to the router for which the address is within the regular coverage zone.
Claim 3
Dependent Claim
17 words
The replica routing system of claim 1 , wherein the router receives the request using HTTP protocol.
Claim 4
Dependent Claim
99 words
The replica routing system of 1 , wherein replica routers in the plurality of routers are programmed to perform steps A through D and are further programmed to perform the steps of: E) transmitting a redirect request to a processor, the redirect request indicating the router to which the processor has been redirected; F) repeating steps A through E within each router to which the request is redirected, until steps C and D cannot be performed; and G) routing the data to the processor from the router that has most recently received a request for data from the processor.
Claim 5
Dependent Claim
99 words
The replica routing system of 1 , wherein replica routers in the plurality of routers are programmed to perform steps A through D and are further programmed to perform the steps of: E) transmitting a redirect request to a processor, the redirect request indicating the router to which the processor has been redirected; F) repeating steps A through E within each router to which the request is redirected, until steps C and D cannot be performed; and G) routing the data to the processor from the router that has most recently received a request for data from the processor.
Claim 6
Dependent Claim
35 words
The replica routing system of claim 1 , wherein if more than one router is identified in step C or D, the processor is redirected toward an identified router that is lowest in the hierarchy.
Claim 7
Dependent Claim
48 words
The replica routing system of claim 1 wherein the preferred coverage zone and the regular coverage zone are sets of addresses associated with the router and are independent of where the router is located in the hierarchy of the plurality of routers at a particular point in time.
Claim 8
Dependent Claim
72 words
The replica routing system of claim 1 , wherein the replica router is programmed such that step C comprises selecting the router for which the address is within the preferred coverage zone from a plurality of routers having addresses within the preferred coverage zone based on load information for each of the plurality of routers that indicates a loading based on handling of service requests for each of the plurality of routers.
Claim 9
Dependent Claim
67 words
The replica routing system of claim 1 , wherein the replica router is programmed such that step C comprises selecting the router for which the address is within the preferred coverage zone from a plurality of routers having addresses within the preferred coverage zone based on content information for each of the plurality of routers that indicates whether each router stores the data requested by the request.
Claim 10
Dependent Claim
52 words
The replica routing system of claim 1 , wherein the coverage zone information is based on propagated coverage zone information received from child routers in the hierarchy of routers that propagate child coverage zone information for each child router upward through the hierarchy of routers to form the propagated coverage zone information.
Claim 11
Independent Claim
284 words
A method of routing requests received from processors, comprising the steps of: A) receiving, at a router, a request from a processor for data; B) comparing an address from which the request purports to originate with coverage zone information for the router that received the request and a hierarchy of routers that are its progeny, the coverage zone information being stored in a database associated with the router that received the request, the coverage zone information for the router that received the request including a preferred coverage zone and a regular coverage zone, the preferred coverage zone being a restrictive set of addresses for which the router believes that it would be at least as good as any other router at serving a request from addresses in the restrictive set of addresses, the regular coverage zone is a larger set of addresses than the preferred coverage zone for which the router will be willing to serve if the request came from one of the larger set addresses, but for which the router does not know whether it is an optimal router; C) if the router that received the request is not within a preferred coverage zone as identified in step B, to redirect the processor to a router for which the address is within the preferred coverage zone; and D) if a router is not identified in step C for which the address is within a preferred coverage zone, but a router other than the router that received the request is identified in step B for which the which the address is within a regular coverage zone, to redirect the processor to the router for which the address is within the regular coverage zone.
Claim 12
Independent Claim
284 words
A method of routing requests received from processors, comprising the steps of: A) receiving, at a router, a request from a processor for data; B) comparing an address from which the request purports to originate with coverage zone information for the router that received the request and a hierarchy of routers that are its progeny, the coverage zone information being stored in a database associated with the router that received the request, the coverage zone information for the router that received the request including a preferred coverage zone and a regular coverage zone, the preferred coverage zone being a restrictive set of addresses for which the router believes that it would be at least as good as any other router at serving a request from addresses in the restrictive set of addresses, the regular coverage zone is a larger set of addresses than the preferred coverage zone for which the router will be willing to serve if the request came from one of the larger set addresses, but for which the router does not know whether it is an optimal router; C) if the router that received the request is not within a preferred coverage zone as identified in step B, to redirect the processor to a router for which the address is within the preferred coverage zone; and D) if a router is not identified in step C for which the address is within a preferred coverage zone, but a router other than the router that received the request is identified in step B for which the which the address is within a regular coverage zone, to redirect the processor to the router for which the address is within the regular coverage zone.
Claim 13
Dependent Claim
17 words
The method of claim 9 , wherein the processor transmits the request for data using HTTP protocol.
Claim 14
Dependent Claim
74 words
The method of claim 9 , further comprising: E) transmitting a request for data from the processor to the router to which the processor has been redirected; F) repeating steps A through E within each router to which the request is redirected, until steps C and D cannot be performed; and then G) routing the data to the processor from the router that has most recently received a request for data from the processor.
Claim 15
Dependent Claim
33 words
The method of claim 9 , wherein if more than one router is identified in step C or D, the processor is redirected toward an identified router that is lowest in the hierarchy.
Claim 16
Dependent Claim
46 words
The method of claim 9 wherein the preferred coverage zone and the regular coverage zone are sets of addresses associated with the router and are independent of where the router is located in the hierarchy of the plurality of routers at a particular point in time.
Claim 17
Dependent Claim
46 words
The method of claim 9 wherein the preferred coverage zone is a restrictive set of addresses for which the router believes that it would be at least as good as any other router at serving a request from an addresses in the restrictive set of addresses.
Claim 18
Dependent Claim
53 words
The method of claim 9 wherein the regular coverage zone is a larger set of addresses than the preferred coverage zone for which the router will be willing to serve if the request came from one of the addresses, but for which the router does not know whether it is an optimal router.
Claim 19
Dependent Claim
63 words
The method of claim 9 , wherein step C comprises selecting the router for which the address is within the preferred coverage zone from a plurality of routers having addresses within the preferred coverage zone based on load information for each of the plurality of routers that indicates a loading based on handling of service requests for each of the plurality of routers.
Claim 20
Dependent Claim
58 words
The method of claim 9 , wherein step C comprises selecting the router for which the address is within the preferred coverage zone from a plurality of routers having addresses within the preferred coverage zone based on content information for each of the plurality of routers that indicates whether each router stores the data requested by the request.
Claim 21
Dependent Claim
50 words
The method of claim 9 , wherein the coverage zone information is based on propagated coverage zone information received from child routers in the hierarchy of routers that propagate child coverage zone information for each child router upward through the hierarchy of routers to form the propagated coverage zone information.
Claim 22
Dependent Claim
265 words
A replica routing system, comprising: a processor; and a plurality of routers; the processor being programmed to transmit a first request for data and a subsequent request for data to one of the routers; the router being programmed: A) to receive the first request from the processor for data; B) to serve the first request; C) to compare an address from which the request purports to originate with coverage zone information for the router that received the request and a hierarchy of routers that are its progeny, the coverage zone information being stored in a database associated with the router that received the request, in order to identify one of the routers as a preferred router for serving the processor, the coverage zone information for the router that received the request including a preferred coverage zone and a regular coverage zone, the preferred coverage zone being a restrictive set of addresses for which the router believes that it would be at least as good as any other router at serving a request from addresses in the restrictive set of addresses, the regular coverage zone is a larger set of addresses than the preferred coverage zone for which the router will be willing to serve if the request came from one of the larger set addresses, but for which the router does not know whether it is an optimal router; D) to receive a subsequent request from the processor for data at the router that received and served the first request; and E) to redirect the processor to the preferred router for serving the subsequent request.
Claim 23
Dependent Claim
265 words
A replica routing system, comprising: a processor; and a plurality of routers; the processor being programmed to transmit a first request for data and a subsequent request for data to one of the routers; the router being programmed: A) to receive the first request from the processor for data; B) to serve the first request; C) to compare an address from which the request purports to originate with coverage zone information for the router that received the request and a hierarchy of routers that are its progeny, the coverage zone information being stored in a database associated with the router that received the request, in order to identify one of the routers as a preferred router for serving the processor, the coverage zone information for the router that received the request including a preferred coverage zone and a regular coverage zone, the preferred coverage zone being a restrictive set of addresses for which the router believes that it would be at least as good as any other router at serving a request from addresses in the restrictive set of addresses, the regular coverage zone is a larger set of addresses than the preferred coverage zone for which the router will be willing to serve if the request came from one of the larger set addresses, but for which the router does not know whether it is an optimal router; D) to receive a subsequent request from the processor for data at the router that received and served the first request; and E) to redirect the processor to the preferred router for serving the subsequent request.
Claim 24
Dependent Claim
63 words
The replica routing system of claim 19 wherein the coverage zone information includes a preferred coverage zone and a regular coverage zone, and wherein the preferred coverage zone and regular coverage zone are sets of addresses associated with the router and are independent of where the router is located in the hierarchy of the plurality of routers at a particular point in time.
Claim 25
Dependent Claim
48 words
The replica routing system of claim 20 wherein the preferred coverage zone is a restrictive set of addresses for which the router believes that it would be at least as good as any other router at serving a request from an addresses in the restrictive set of addresses.
Claim 26
Dependent Claim
55 words
The replica routing system of claim 20 wherein the regular coverage zone is a larger set of addresses than the preferred coverage zone for which the router will be willing to serve if the request came from one of the addresses, but for which the router does not know whether it is an optimal router.
Claim 27
Dependent Claim
64 words
The replica routing system of claim 20 wherein step C comprises selecting the router for which the address is within the preferred coverage zone from a plurality of routers having addresses within the preferred coverage zone based on load information for each of the plurality of routers that indicates a loading based on handling of service requests for each of the plurality of routers.
Claim 28
Dependent Claim
59 words
The replica routing system of claim 20 wherein step C comprises selecting the router for which the address is within the preferred coverage zone from a plurality of routers having addresses within the preferred coverage zone based on content information for each of the plurality of routers that indicates whether each router stores the data requested by the request.
Claim 29
Dependent Claim
51 words
The replica routing system of claim 19 wherein the coverage zone information is based on propagated coverage zone information received from child routers in the hierarchy of routers that propagate child coverage zone information for each child router upward through the hierarchy of routers to form the propagated coverage zone information.
Claim 30
Independent Claim
240 words
A method of routing requests received from processors, comprising the steps of: A) receiving, at a router, a first request form the processor for data; B) serving the first request at the router; C) comparing an address from which the request purports to originate with coverage zone information for the router that received the request and a hierarchy of routers that are its progeny, the coverage zone information being stored in a database associated with the router that received the request, in order to identify one of the routers as a preferred router for serving the processor, the coverage zone information for the router that received the request including a preferred coverage zone and a regular coverage zone, the preferred coverage zone being a restrictive set of addresses for which the router believes that it would be at least as good as any other router at serving a request from addresses in the restrictive set of addresses, the regular coverage zone is a larger set of addresses than the preferred coverage zone for which the router will be willing to serve if the request came from one of the larger set addresses, but for which the router does not know whether it is an optimal router; D) receiving a subsequent request from the processor for data at the router that received and served the first request; and E) redirecting the processor to the preferred router for serving the subsequent request.
Claim 31
Independent Claim
240 words
A method of routing requests received from processors, comprising the steps of: A) receiving, at a router, a first request form the processor for data; B) serving the first request at the router; C) comparing an address from which the request purports to originate with coverage zone information for the router that received the request and a hierarchy of routers that are its progeny, the coverage zone information being stored in a database associated with the router that received the request, in order to identify one of the routers as a preferred router for serving the processor, the coverage zone information for the router that received the request including a preferred coverage zone and a regular coverage zone, the preferred coverage zone being a restrictive set of addresses for which the router believes that it would be at least as good as any other router at serving a request from addresses in the restrictive set of addresses, the regular coverage zone is a larger set of addresses than the preferred coverage zone for which the router will be willing to serve if the request came from one of the larger set addresses, but for which the router does not know whether it is an optimal router; D) receiving a subsequent request from the processor for data at the router that received and served the first request; and E) redirecting the processor to the preferred router for serving the subsequent request.
Claim 32
Dependent Claim
61 words
The method of claim 26 wherein the coverage zone information includes a preferred coverage zone and a regular coverage zone, and wherein the preferred coverage zone and regular coverage zone are sets of addresses associated with the router and are independent of where the router is located in the hierarchy of the plurality of routers at a particular point in time.
Claim 33
Dependent Claim
46 words
The method of claim 27 wherein the preferred coverage zone is a restrictive set of addresses for which the router believes that it would be at least as good as any other router at serving a request from an addresses in the restrictive set of addresses.
Claim 34
Dependent Claim
53 words
The method of claim 27 wherein the regular coverage zone is a larger set of addresses than the preferred coverage zone for which the router will be willing to serve if the request came from one of the addresses, but for which the router does not know whether it is an optimal router.
Claim 35
Dependent Claim
62 words
The method of claim 27 wherein step C comprises selecting the router for which the address is within the preferred coverage zone from a plurality of routers having addresses within the preferred coverage zone based on load information for each of the plurality of routers that indicates a loading based on handling of service requests for each of the plurality of routers.
Claim 36
Dependent Claim
57 words
The method of claim 27 wherein step C comprises selecting the router for which the address is within the preferred coverage zone from a plurality of routers having addresses within the preferred coverage zone based on content information for each of the plurality of routers that indicates whether each router stores the data requested by the request.
Claim 37
Dependent Claim
49 words
The method of claim 26 wherein the coverage zone information is based on propagated coverage zone information received from child routers in the hierarchy of routers that propagate child coverage zone information for each child router upward through the hierarchy of routers to form the propagated coverage zone information.
Claim 38
Dependent Claim
281 words
A router being programmed to perform the steps of: A: to receive a request from a processor; B: to compare an address from which the request purports to originate with coverage zone information for the router that received the request and a hierarchy of a plurality of routers that are its progeny, the coverage zone information being stored in a database associated with the router that received the request, the coverage zone information for the router that received the request including a preferred coverage zone and a regular coverage zone, the preferred coverage zone being a restrictive set of addresses for which the router believes that it would be at least as good as any other router at serving a request from addresses in the restrictive set of addresses, the regular coverage zone is a larger set of addresses than the preferred coverage zone for which the router will be willing to serve if the request came from one of the larger set addresses, but for which the router does not know whether it is an optimal router; C) if the router that received the request is not within a preferred coverage zone as identified in step B, to redirect the processor to a router for which the address is within the preferred coverage zone; and D) if a router is not identified in step C for which the address is within a preferred coverage zone, but a router other than the router that received the request is identified in step B for which the which the address is within a regular coverage zone, to redirect the processor to the router for which the address is within the regular coverage zone.
Claim 39
Dependent Claim
281 words
A router being programmed to perform the steps of: A: to receive a request from a processor; B: to compare an address from which the request purports to originate with coverage zone information for the router that received the request and a hierarchy of a plurality of routers that are its progeny, the coverage zone information being stored in a database associated with the router that received the request, the coverage zone information for the router that received the request including a preferred coverage zone and a regular coverage zone, the preferred coverage zone being a restrictive set of addresses for which the router believes that it would be at least as good as any other router at serving a request from addresses in the restrictive set of addresses, the regular coverage zone is a larger set of addresses than the preferred coverage zone for which the router will be willing to serve if the request came from one of the larger set addresses, but for which the router does not know whether it is an optimal router; C) if the router that received the request is not within a preferred coverage zone as identified in step B, to redirect the processor to a router for which the address is within the preferred coverage zone; and D) if a router is not identified in step C for which the address is within a preferred coverage zone, but a router other than the router that received the request is identified in step B for which the which the address is within a regular coverage zone, to redirect the processor to the router for which the address is within the regular coverage zone.
Claim 40
Dependent Claim
36 words
The router of claim 33 wherein if more than one router is identified in step C or D, the router is programmed to redirect the processor toward an identified router that is lowest in the hierarchy.
Claim 41
Dependent Claim
46 words
The router of claim 33 wherein the preferred coverage zone and the regular coverage zone are sets of addresses associated with the router and are independent of where the router is located in the hierarchy of the plurality of routers at a particular point in time.
Claim 42
Dependent Claim
69 words
The router of claim 33 wherein the replica router is programmed such that step C comprises selecting the router for which the address is within the preferred coverage zone from a plurality of routers having addresses within the preferred coverage zone based on load information for each of the plurality of routers that indicates a loading based on handling of service requests for each of the plurality of routers.
Claim 43
Dependent Claim
64 words
The router of claim 33 wherein the replica router is programmed such that step C comprises selecting the router for which the address is within the preferred coverage zone from a plurality of routers having addresses within the preferred coverage zone based on content information for each of the plurality of routers that indicates whether each router stores the data requested by the request.
Claim 44
Dependent Claim
49 words
The router of claim 33 wherein the coverage zone information is based on propagated coverage zone information received from child routers in the hierarchy of routers that propagate child coverage zone information for each child router upward through the hierarchy of routers to form the propagated coverage zone information.
Claim 45
Dependent Claim
282 words
A router comprising: means for receiving a request from a processor; means for comparing an address from which the request purports to originate with coverage zone information for the router that received the request and a hierarchy of a plurality of routers that are its progeny, the coverage zone information being stored in a database associated with the router that received the request, the coverage zone information for the router that received the request including a preferred coverage zone and a regular coverage zone, the preferred coverage zone being a restrictive set of addresses for which the router believes that it would be at least as good as any other router at serving a request from addresses in the restrictive set of addresses, the regular coverage zone is a larger set of addresses than the preferred coverage zone for which the router will be willing to serve if the request came from one of the larger set addresses, but for which the router does not know whether it is an optimal router; based on the means for comparing, means for determining if the router that received the request is not within a preferred coverage zone as identified by the means for comparing an address, redirecting the processor to a router for which the address is within the preferred coverage zone; and means, if a router is not identified by means for comparing an address for which the address is within a preferred coverage zone, but a router other than the router that received the request is identified in step B for which the address is within a regular coverage zone, redirecting the processor to the router for which the regular coverage zone.
Claim 46
Dependent Claim
282 words
A router comprising: means for receiving a request from a processor; means for comparing an address from which the request purports to originate with coverage zone information for the router that received the request and a hierarchy of a plurality of routers that are its progeny, the coverage zone information being stored in a database associated with the router that received the request, the coverage zone information for the router that received the request including a preferred coverage zone and a regular coverage zone, the preferred coverage zone being a restrictive set of addresses for which the router believes that it would be at least as good as any other router at serving a request from addresses in the restrictive set of addresses, the regular coverage zone is a larger set of addresses than the preferred coverage zone for which the router will be willing to serve if the request came from one of the larger set addresses, but for which the router does not know whether it is an optimal router; based on the means for comparing, means for determining if the router that received the request is not within a preferred coverage zone as identified by the means for comparing an address, redirecting the processor to a router for which the address is within the preferred coverage zone; and means, if a router is not identified by means for comparing an address for which the address is within a preferred coverage zone, but a router other than the router that received the request is identified in step B for which the address is within a regular coverage zone, redirecting the processor to the router for which the regular coverage zone.
References Cited (Backward Citations)
US5088032A
Cited
US4987587A
Cited
US5463735A
Cited
US5282270A
Cited
US5345586A
Cited
US5664107A
Cited
US5914953A
Cited
US5425090A
Cited
US5430729A
Cited
US5930249A
Cited
WO1996041285A1
Cited
US5956716A
Cited
US5740549A
Cited
US5600794A
Cited
US5812769A
Cited
US5845087A
Cited
US5828847A
Cited
US5774660A
Cited
WO1998018076A1
Cited
WO1998031107A2
Cited
US6052718A
Cited
WO1998037699A1
Cited
WO1998040831A1
Cited
US6351775B1
Cited
US6195703B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-01-06 | 2006-07-08 | 2007-01-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-01-06 | 2010-07-08 | 2011-01-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-01-06 | 2014-07-08 | 2015-01-07 | $7700.00 | Window Closed / Lapsed |