Method and apparatus for estimating relative network proximity in the presence of a network filter

• US 7,444,428 B1
• Filed: 08/26/2002
• Issued: 10/28/2008
• Est. Priority Date: 08/26/2002
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Kuo, Szu-Wen, Mowat, J Eric, Shah, Mehul S.
• Primary Examiner(s): Jareonchonwanit; Bunjob
• Assistant Examiner(s): Chea; Philip J
• Application Number:
  US10/228,638
• Time in Patent Office: 2,255 Days
• Field of Search: 370/351, 370/241, 370/249, 709223-224, 709238-242
• US Class Current: 709/242
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 61/4541 Directories for service discovery
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

A method and apparatus for estimating relative network proximity between request routing agents and client agents are described herein. In one embodiment, the method includes a proximity estimation unit to send a first number of probe messages to a client agent without waiting to receive a reply message, wherein the proximity estimation unit is to receive a first set of reply messages. The apparatus also including a proximity verification unit coupled with the proximity estimation unit, to send a second number of probe messages to the client agent, and to receive a second set of reply messages.

Claims

1. An apparatus comprising:

a processor to execute instructions that implement;

a proximity estimation unit to send a first number of probe messages to a client agent without waiting to receive a reply message, the proximity estimation unit to receive a first set of reply messages including a largest expired time to live (TTL) value of the first set, and to determine a proximity estimate from the largest expired TTL value of the first set; and

a proximity verification unit coupled with the proximity estimation unit, to use the proximity estimate to set a TTL value in each of a second number of probe messages, to send the second number of probe messages including the largest expired TTL value of the first set, to the client agent, to receive a second set of reply messages including a largest expired TTL value of the second set, and to verify that the largest expired TTL value of the first set equals the largest expired TTL value of the second set, wherein the second number is smaller than the first number, so that the proximity estimate can be verified by sending a smaller number of probe messages than the number of probe messages that was sent to determine the proximity estimate.

2. The apparatus of claim 1, wherein the proximity estimation unit estimates a proximity between a client agent and a request routing agent.

3. The apparatus of claim 2, wherein the proximity is published to a request routing server.

4. The apparatus of claim 1, wherein the first number is a predefined value, and the second number is based on a information included in the second set of reply messages.

5. A method comprising:

estimating a proximity, the estimating including

sending a first number of probe messages to a client agent without waiting to receive a reply message,

receiving a first set of reply messages including a largest expired time-to-live (TTL) value of the first set, and

determining a proximity estimate from the largest expired TTL value of the first set;

verifying the proximity, the verifying including

using the proximity estimate to set a TTL value in each of a second number of probe messages,

sending the second number of probe messages, including a largest expired TTL value of the first set, to the client agent, wherein the second number is less than the first number,

receiving a second set of reply messages, including a largest expired TTL value of the second set, and

verifying that the largest expired TTL value of the first set equals the largest expired TTL value of the second set,

so that the proximity estimate can be verified by sending a number of probe messages that is less than the number of probe messages that was sent to determine the proximity estimate.

6. The method of claim 5, wherein the proximity is between a request routing agent and a firewall.

7. The method of claim 5 wherein the proximity is between a request routing agent and the client agent.

8. The method of claim 5, wherein each of the first number of probe messages is assigned a different time to live (TTL) value ranging from 1—

to a predefined value.

9. The method of claim 5 further comprising:

publishing the proximity in a table.

10. An apparatus comprising:

a processor to execute instructions that implement;

a proximity estimation unit to send a first number of probe messages and to receive a first set of reply messages including a largest expired time-to-live (TTL) value of the first set, the proximity estimation unit to determine a proximity estimate between a request routing agent and a client agent from the largest expired TTL value of the first set;

a probe message optimization unit coupled with the proximity estimation unit, to determine an optimized sequence of TTL values to be sent in an optimized number of probe messages, the optimized number being smaller than the first number, the optimized sequence of TTL values including the largest expired TTL value of the first set as a center value of the sequence; and

a proximity verification unit coupled with the proximity estimation unit and the probe message optimization unit, to use the proximity estimate to set a time to live (TTL) value in each of the optimized number of probe messages, to send the optimized number of messages to the client agent, to receive a second set of reply messages including a largest expired TTL value of the second set, and to verify that the largest expired TTL value of the first set equals the largest expired TTL value of the second set, so that the proximity estimate can be verified by sending a smaller number of probe messages than the number of probe messages that was sent to determine the proximity estimate.

11. The apparatus of claim 10, wherein the proximity estimation unit sends the probe messages to the client agent without waiting to receive any of the first set of reply messages, each of the probe messages having a different time to live (TTL).

12. The apparatus of claim 11, wherein the probe message optimization unit determines the optimized number of probe messages based on a highest expired TTL value of probe messages received by the proximity estimation unit.

13. The apparatus of claim 10, wherein the first number is a predefined value and the optimized number is based on information included in the second set of reply messages.

14. A network comprising:

a request routing agent serving network content, the request routing agent including a processor to execute instructions that implement;

a proximity estimation unit to send a number of probe messages to a client agent, to receive a first set of reply messages including a largest expired TTL value of the first set, and to determine a proximity estimate from the first set of reply messages from the largest expired TTL value of the first set;

a probe message optimization unit coupled with the proximity estimation unit, to determine an optimized sequence of TTL values to be sent in an optimized number of probe messages, the optimized number being smaller than the first number, the optimized sequence of TTL values including the largest expired TTL value of the first set as a center value of the sequence; and

a proximity verifying unit coupled with the proximity estimation unit and the probe message optimization unit, to use the proximity estimate to set a time to live (TTL) value in each of the optimized number of probe messages, to send the optimized number of probe messages, to receive a second set of reply messages including a largest expired TTL value of the second set, and to verify that the largest expired TTL value of the first set equals the largest expired TTL value of the second set, so that the proximity estimate can be verified by sending a smaller number of probe messages than the number of probe messages that was sent to determine the proximity estimate; and

the client agent including a processor to execute instructions that implement processing network content requests.

15. The network of claim 14, further comprising:

a network layer filter dropping probe messages that are destined to the client agent.

16. The network of claim 14, wherein the proximity estimation unit sends the number of probe messages to the client agent without waiting to receive one of the first set of reply messages, wherein each probe message has a different TTL.

17. A method comprising:

sending a first number of messages to a client agent without waiting to receive a reply message;

receiving a first set of reply messages, the first set including a largest expired time to live (TTL) value of the first set;

estimating proximity based on the largest expired TTL value of the first set;

setting a TTL value in each of a second number of probe messages, wherein the second number of probe messages includes an optimized sequence of TTL values having the largest expired TTL value of the first set as a center value of the sequence, the second number being smaller than the first number;

sending the second number of probe messages to the client agent;

receiving a second set of reply messages, the second set including a largest expired TTL value of the second set; and

verifying that the largest expired TTL value of the first set equals the largest expired TTL value of the second set, so that the estimated proximity can be verified by sending a smaller number of probe messages than the number of probe messages that was sent to estimate the proximity.

18. The method of claim 17, wherein the proximity is between the client agent and a request routing agent.

19. The method of claim 17, wherein the proximity is between a firewall and a request routing agent.

20. A method comprising:

sending a first number of probe messages to a client agent, each of the probe messages including a time to live (TTL) value;

receiving a first set of reply messages including a largest expired TTL value for the first set;

using the largest expired TTL value for the first set to set a TTL value in a second number of probe messages, wherein the second number of probe messages includes the largest expired TTL value of the first set, the second number being smaller than the first number;

sending the second number of probe messages;

receiving a second set of reply messages including a largest expired TTL value for the second set;

determining whether the largest expired TTL value for the second set is equal to the largest expired TTL value for the first set;

in response to determining the largest TTL value for the second set is equal to the largest TTL value for the first set, sending a third number of probe messages, each probe message including a TTL value from a second range of TTL values;

receiving a third set of reply messages, the third set of reply messages including a largest expired TTL value for the third set;

determining whether the largest expired TTL value for the third set is equal to the largest expired TTL value for the first set;

in response to determining the largest expired TTL value for the third set is equal to the largest expired TTL value for the first set, indicating a proximity.

21. The method of claim 20, wherein the second number is equal to the third number.

22. The method of claim 20, wherein the range is from one less than to one more than the largest expired TTL for the first set to one.

23. The method of claim 20, wherein the proximity is between the client agent and a request routing agent.

24. The method of claim 20, wherein the proximity is between a firewall and a request routing agent.

25. A machine-readable storage medium that provides instructions, which when executed by a machine, cause said machine to perform operations comprising:

estimating a proximity, the estimating including,

sending a first number of probe messages to a client agent without waiting to receive a reply message,

receiving a first set of reply messages, and

determining a proximity estimate from the first set of reply messages;

verifying the proximity, the verifying including,

using the proximity estimate to set a time to live (TTL) value in a second number of probe messages,

sending the second number of probe messages to the client agent, wherein the second number of probe messages includes the largest expired TTL value of the first set, the second number being less than the first number,

receiving a second set of reply messages including a largest expired TTL value of the second set, and

verifying that the largest expired TTL value of the first set equals the largest expired TTL value of the second set,

so that the proximity estimate can be verified by sending a number of probe messages that is less than the number of probe messages that was sent to determine the proximity estimate.

26. The machine-readable storage medium of claim 25, wherein the proximity is between a request routing agent and a firewall.

27. The machine-readable storage medium of claim 25, wherein the proximity is between a request routing agent and the client agent.

28. The machine-readable storage medium of claim 25, wherein each of the first number of probe messages is assigned a different TTL value ranging from 0 to a predefined value.

29. The machine-readable storage medium of claim 25 that provides instructions, which when executed by a machine, cause said machine to perform operations further comprising:

publishing the proximity in a table.

30. A system for directing a client agent to a nearest request routing agent among a plurality of request routing agents on a network, the system comprising:

a plurality of request routing agents, each including a processor to execute instructions that;

estimate a proximity of the request routing agent to the client agent, by sending a first number of probe messages to the client agent without waiting to receive a reply message;

verify the proximity of the request routing agent to the client agent, by sending a second number of probe messages to the client agent without waiting to receive a reply message, the second number being less than the first number, so that the proximity can be verified by sending a number of probe messages that is less than the number of probe messages that was sent to estimate the proximity; and

report the verified proximity to a request routing server;

a request routing server including a processor to execute instructions that;

receive verified proximities from the plurality of request routing agents,

based on the received proximities, determine which of the plurality of request routing agents is nearest to the client agent, and

direct the client agent to the determined routing agent.