Method and apparatus for determining approximate network distances using reference locations

• US 6,724,733 B1
• Filed: 11/02/1999
• Issued: 04/20/2004
• Est. Priority Date: 11/02/1999
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Cidon, Israel, Schuba, Christoph, Gupta, Amit, Rom, Raphael
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): Pizarro, Ricardo M.
• Application Number:
  US09/432,506
• Time in Patent Office: 1,631 Days
• Field of Search: 370/252, 370/235, 370/237, 370/238, 370/432, 370/254, 370/255, 370/351, 370/400, 370/401, 370/229, 709/220, 709/224, 709/228, 709/241, 709/105, 709/226
• US Class Current: 370/252
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/45 Network directories; Name-to-address mapping
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1021 based on client or server locations

Abstract

The invention is a method and apparatus for determining an approximate network distance using one or more reference points. In accordance with an embodiment of the invention, the method comprises the steps of selecting at least one reference point positioned along a path between first and second points of a network, generating first distance metric information associated with at least one path associating a first point and the at least one reference point, generating second distance metric information associated with at least one path associating a second point and the at least one reference point, and determining a total approximate distance between the first point and the second point along one or more paths based on the first and second distance metric information. In one or more embodiments, the second distance metric information is published to one or more servers providing domain name server mapping information and the second distance metric information is provided to the first point along with requested mapping information. In one or more embodiments, total approximate distance information between a client and multiple servers providing a desired service is determined and a server associated with a shortest total approximate distance is selected from which to obtain the service.

Claims

1. A method of determining an approximate network distance between a first point and a second point of a network having one or more nodes, comprising:

selecting at least one reference point from said nodes of said network;

obtaining first distance metric information associated with at least one path associating a first point and said at least one reference point;

obtaining second distance metric information associated with at least one path associating a second point and said at least one reference point; and

determining a total approximate distance associated with at least one path associating said first point and said second point based on said first and second distance metric information

said network further comprising;

at least one third point of said network; and

obtaining a third distance metric information associated with said at least one path associating said at least one third point and said at least one reference point network distance and determining a second total approximate distance associated with a path associating said first point and said third point.

2. The method in accordance with claim 1 wherein said second and said at least one third point comprises a server and said first point comprises a client.

3. The method in accordance with claim 1 including the step of transmitting said second distance metric information to said first point.

4. A method of determining an approximate network distance between a first point and a second point of a network having one or more nodes, comprising:

selecting at least one reference point from said nodes of said network;

obtaining first distance metric information associated with at least one path associating a first point and said at least one reference point;

obtaining second distance metric information associated with at least one path associating a second point and said at least one reference point; and

determining a total approximate distance associated with at least one path associating said first point and said second point based on said first and second distance metric information,

wherein there are at least two second points, said method further comprising;

obtaining second distance metric information associated with said at least one path associating each second point and said at least one reference point, determining a total approximate distance associated with said at least one path associating said first point and each second point based on said first and second distance metric information, and including selecting a closest second point by selecting a path to a second point having a shortest total approximate distance.

5. The method in accordance with claim 4 wherein said shortest total approximate distance is selected from a group consisting of one or more of:

a total approximate distance having a shortest number of hops, a shortest delay, a maximum bandwidth and a maximum reliability.

6. The method in accordance with claim 4 wherein said network comprises the Internet.

7. The method in accordance with claim 4 wherein said providing said second distance metric information comprises transmitting said second distance metric information with mapping information.

8. The method in accordance with claim 7 further comprising publishing said second distance metric information to a server providing DNS mapping information.

9. A method of determining an approximate network distance between a first point and a second point of a network having one or more nodes, comprising:

selecting at least one reference point from said nodes of said network;

obtaining first distance metric information associated with at least one path associating a first point and said at least one reference point;

obtaining second distance metric information associated with at least one path associating a second point and said at least one reference point; and

determining a total approximate distance associated with at least one path associating said first point and said second point based on said first and second distance metric information;

wherein said first distance metric information comprises at least one first and at least one second metric, and including the step of obtaining a first distance from said at least one first and second metric information.

10. The method in accordance with claim 9 wherein said obtaining said first distance comprises manipulating said at least one first and second metric information with a composite metric function in which one or more of said metrics are given greater weight than another.

11. A method of determining an approximate network distance between a first point and a second point of a network having one or more nodes, comprising:

selecting at least one reference point from said nodes of said network;

obtaining first distance metric information associated with at least one path associating a first point and said at least one reference point;

obtaining second distance metric information associated with at least one path associating a second point and said at least one reference point; and

determining a total approximate distance associated with at least one path associating said first point and said second point based on said first and second distance metric information;

wherein said second distance metric information comprises at least one first and at least one second metric, and including obtaining a second distance from said at least one first and second metric information.

12. The method in accordance with claim 11 wherein said obtaining said second distance comprises manipulating said at least one first and second metric information with a composite metric function in which one or more of said metrics are given greater weight than another.

13. A computer program product comprising:

a computer usable medium having computer readable program code embodied therein for determining an approximate distance between two points on a network, said medium comprising;

computer readable program code configured to cause a computer to select at least one reference point of said network;

computer readable program code configured to cause a computer to obtain first distance metric information associated with said at least one path associating said first point and said at least one reference point;

computer readable program code configured to cause a computer to obtain second distance metric information associated with at least one path associating said second point and said at least one reference point; and

computer readable program code configured to cause a computer to determine a first set of total approximate distance information for paths associating said first point and said second point based on said first and second distance metric information.

14. The computer program product in accordance with claim 13 wherein said computer readable program code is configured to obtain third distance metric information associated with at least one path associating said at least one third point and said at least one reference point.

15. The computer program product in accordance with claim 14 wherein said computer readable program code is further configured to determine second total approximate distance information for paths associating said first point and said at least one third point based on said first and third distance metric information.

16. The computer program product in accordance with claim 15 wherein said computer readable program code is further configured to select a point from a group of said second and at least one third point, said selected point associated with a shortest total approximate distance from said first and second total distance information.

17. The computer program product in accordance with claim 15 wherein said computer readable program code is configured to cause a computer to obtain first distance metric information with a composite function using at least two different distance information metrics.

18. The computer program product in accordance with claim 15 wherein said computer readable program code is configured to cause a computer to obtain said second distance metric information with a composite function using at least two different distance information metrics.