Determination of distance between nodes in a computer network

• US 6,192,404 B1
• Filed: 05/14/1998
• Issued: 02/20/2001
• Est. Priority Date: 05/14/1998
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Pearlman, Radia J., Chiu, Dah Ming, Hanna, Stephen R., Hurst, Stephen A.
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): Barot, Bharat
• Application Number:
  US09/079,504
• Time in Patent Office: 1,013 Days
• Field of Search: 709/212, 709/216-218, 709/223-224, 709/227-228, 709/238-242, 709/300, 709/302-304, 370/235-238, 370/248, 370/351, 370/400-402
• US Class Current: 709/224
• 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 45/16 Multipoint routing
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/26 Route discovery packet

Abstract

A base node of a computer network sends concurrent TTL query messages using multicast to other receiving nodes of the computer network. Each of the TTL query messages has a different time-to-live (TTL) parameter value and records the TTL parameter of the TTL query message into a message body. The receiving nodes receive one or more of the TTL query messages, namely, those TTL query messages whose TTL parameter values are sufficient to allow the TTL query message to reach the receiving node. Each receiving node can determine the TTL distance to the receiving node from the base node by determining the lowest TTL parameter value of all TTL query messages which reached the receiving node. Each receiving node communicates the TTL distance by sending to the base node a TTL query response message which indicates, in the message body, the least TTL parameter value of all TTL query messages received by the receiving node. Accordingly, the base node can determine TTL distances to other nodes of the computer network very quickly.

Claims

1. A method for determining relative distances between a base node and at least one other node of a computer network, the method comprising:

sending through the computer network at least two query messages, each of which includes;

an expiration parameter which specifies an expiration condition for the query message; and

a data body which includes data specifying the expiration condition of the query message as specified in the expiration parameter of the query message;

receiving, from a recipient one of the other nodes, a query response message which includes data specifying a quickest expiration of at least one received one of the query messages which is received by the recipient node, wherein the quickest expiration is determined according to the respective expiration conditions of the received query messages as specified in the data body of the received query message;

wherein the quickest expiration relates to the relative distance.

2. The method of claim 1 wherein the expiration parameter is a time-to-live parameter.

4. The method of claim 1 wherein the expiration condition of each of the query messages specifies a number of hops through the computer network such that the query message expires after completing the number of hops.

5. The method of claim 1 wherein the quickest expiration specified by the query response message indicates a range of possible distances between the base node and the recipient node, the method further comprising:

sending through the computer network at least two additional query messages, each of which includes;

an expiration parameter which specifies an expiration condition for the additional query message wherein the expiration condition corresponds to a distance within the range of possible distances; and

a data body which includes data specifying the expiration condition of the additional query message as specified in the expiration parameter of the additional query message; and

receiving, from the recipient node, a subsequent query response message which includes data specifying a new quickest expiration of at least one received one of the additional query messages which is received by the recipient node, wherein the new quickest expiration is determined according to the respective expiration conditions of the received additional query messages as specified in the data body of the received additional query message.

3. The method of claim I wherein the expiration condition of each of the query messages specifies an amount of time from the sending of the query message at which the query message expires.

6. A method for determining relative distances between a base node and at least one other nodes of a computer network, the method comprising:

receiving, from the base node through the computer network, at least one query message, each of which includes;

an expiration parameter which specifies an expiration condition for the query message; and

a data body which includes data specifying the expiration condition of the query message as specified in the expiration parameter of the query message; and

determining a quickest expiration of the at least one query message, wherein the quickest expiration is determined according to the respective expiration conditions of the query messages as specified in the data body of the query message;

wherein the quickest expiration relates to the relative distance.

7. The method of claim 6 further comprising:

sending, to the base node, a query response message which includes data specifying the quickest expiration.

8. The method of claim 6 wherein the expiration parameter is a time-to-live parameter.

9. The method of claim 6 wherein the expiration condition of each of the query messages specifies an amount of time from the sending of the query message at which the query message expires.

10. The method of claim 6 wherein the expiration condition of each of the query messages specifies a number of hops through the computer network such that the query message expires after completing the number of hops.

11. A computer readable medium useful in association with a computer which includes a processor and a memory, the computer readable medium including computer instructions which are configured to cause the computer to determine relative distances between a base node and at least one other nodes of a computer network, the computer instructions comprising:

a sending module which is configured to send through the computer network at least two query messages, each of which includes;

an expiration parameter which specifies an expiration condition for the query message; and

a data body which includes data specifying the expiration condition of the query message as specified in the expiration parameter of the query message; and

a receiving module which is operatively coupled to the sending module and which is configured to receive, from a recipient one of the other nodes, a query response message which includes data specifying a quickest expiration of at least one received one of the query messages which are received by the recipient node, wherein the quickest expiration is determined according to the respective expiration conditions of the received query messages as specified in the data body of the received query messages;

wherein the quickest expiration relates to the relative distance.

12. The computer readable medium of claim 11 wherein the expiration parameter is a time-to-live parameter.

13. The computer readable medium of claim 11 wherein the expiration condition of each of the query messages specifies an amount of time from the sending of the query message at which the query message expires.

14. The computer readable medium of claim 11 wherein the expiration condition of each of the query messages specifies a number of hops through the computer network such that the query message expires after completing the number of hops.

15. The computer readable medium of claim 11 wherein the quickest expiration specified by the query response message indicates a range of possible distances between the base node and the recipient node, further wherein the computer instructions further comprise:

a second sending module which is operatively coupled to the receiving module and which is configured to send through the computer network at least two additional query messages, each of which includes;

an expiration parameter which specifies an expiration condition for the additional query message wherein the expiration condition corresponds to a distance within the range of possible distances; and

a data body which includes data specifying the expiration condition of the additional query message as specified in the expiration parameter of the additional query message; and

a second receiving module which is operatively coupled to the second sending module and which is configured to receive, from the recipient node, a subsequent query response message which includes data specifying a new quickest expiration of at least one received one of the additional query messages which are received by the recipient node, wherein the new quickest expiration is determined according to the respective expiration conditions of the received additional query messages as specified in the data body of the received additional query messages.

16. A computer readable medium useful in association with a computer which includes a processor and a memory, the computer readable medium including computer instructions which are configured to cause the computer to determine relative distances between a base node and one or more other nodes of a computer network, the computer instructions comprising:

a receiving module which is configured to receive, from the base node through the computer network, at least one query message, each of which includes;

an expiration parameter which specifies an expiration condition for the query message; and

a data body which includes data specifying the expiration condition of the query message as specified in the expiration parameter of the query message; and

a comparison module which is operatively coupled to the receiving module and which is configured to determine a quickest expiration of the at least one query message, wherein the quickest expiration is determined according to the respective expiration conditions of the query messages as specified in the data body of the query messages;

wherein the quickest expiration relates to the relative distance.

17. The computer readable medium of claim 16 wherein the computer instructions further comprise:

a sending module which is operatively coupled to the comparison module and which is configured to send, to the base node, a query response message which includes data specifying the quickest expiration.

18. The computer readable medium of claim 16 wherein the expiration parameter is a time-to-live parameter.

19. The computer readable medium of claim 16 wherein the expiration condition of each of the query messages specifies an amount of time from the sending of the query message at which the query message expires.

20. The computer readable medium of claim 16 wherein the expiration condition of each of the query messages specifies a number of hops through the computer network such that the query message expires after completing the number of hops.

21. A computer system comprising:

a processor;

a memory operatively coupled to the processor; and

distance determining logic which executes in the processor from the memory and which, when executed by the processor, causes the computer to determine relative distances between the computer system and at least one other node through a computer network, the distance determining logic comprising;

a sending module which is configured to send through the computer network at least two query messages, each of which includes;

an expiration parameter which specifies an expiration condition for the query message; and

a data body which includes data specifying the expiration condition of the query message as specified in the expiration parameter of the query message; and

a receiving module which is operatively coupled to the sending module and which is configured to receive, from a recipient one of the other nodes, a query response message which includes data specifying a quickest expiration of at least one received ones of the query messages which are received by the recipient node, wherein the quickest expiration is determined according to the respective expiration conditions of the received query messages as specified in the data body of the received query messages;

wherein the quickest expiration relates to the relative distance.

22. The computer system of claim 21 wherein the expiration parameter is a time-to-live parameter.

23. The computer system of claim 21 wherein the expiration condition of each of the query messages specifies an amount of time from the sending of the query message at which the query message expires.

24. The computer system of claim 21 wherein the expiration condition of each of the query messages specifies a number of hops through the computer network such that the query message expires after completing the number of hops.

25. The computer system of claim 21 wherein the quickest expiration specified by the query response message indicates a range of possible distances between the base node and the recipient node, further wherein the distance determining logic further comprises:

a second sending module which is operatively coupled to the receiving module and which is configured to send through the computer network at least two additional query messages, each of which includes;

an expiration parameter which specifies an expiration condition for the additional query message wherein the expiration condition corresponds to a distance within the range of possible distances; and

a data body which includes data specifying the expiration condition of the additional query message as specified in the expiration parameter of the additional query message; and

a second receiving module which is operatively coupled to the second sending module and which is configured to receive, from the recipient node, a subsequent query response message which includes data specifying a new quickest expiration of at least one received one of the additional query messages which is received by the recipient node, wherein the new quickest expiration is determined according to the respective expiration conditions of the received additional query messages as specified in the data body of the received additional query messages.

26. A computer system comprising:

a processor;

a memory operatively coupled to the processor; and

distance determining logic which executes in the processor from the memory and which, when executed by the processor, causes the computer to determine relative distances between the computer system and a base node through a computer network, the distance determining logic comprising;

a receiving module which is configured to receive, from the base node through the computer network, at least one query message, each of which includes;

an expiration parameter which specifies an expiration condition for the query message; and

a data body which includes data specifying the expiration condition of the query message as specified in the expiration parameter of the query message; and

a comparison module which is operatively coupled to the receiving module and which is configured to determine a quickest expiration of the at least one query message, wherein the quickest expiration is determined according to the respective expiration conditions of the query messages as specified in the data body of the query messages;

wherein the quickest expiration relates to the relative distance.

27. The computer system of claim 26 wherein the distance determining logic further comprises:

a sending module which is operatively coupled to the comparison module and which is configured to send, to the base node, a query response message which includes data specifying the quickest expiration.

28. The computer system of claim 26 wherein the expiration parameter is a time-to-live parameter.

29. The computer system of claim 26 wherein the expiration condition of each of the query messages specifies an amount of time from the sending of the query message at which the query message expires.

30. The computer system of claim 26 wherein the expiration condition of each of the query messages specifies a number of hops through the computer network such that the query message expires after completing the number of hops.

31. An apparatus for determining relative distances between a base node and at least one other node of a computer network, the apparatus comprising:

means for sending through the computer network at least two query messages, each of which includes;

an expiration parameter which specifies an expiration condition for the query message; and

a data body which includes data specifying the expiration condition of the query message as specified in the expiration parameter of the query message; and

means for receiving, from a recipient one of the other nodes, a query response message which includes data specifying a quickest expiration of at least one received one of the query messages which is received by the recipient node, wherein the quickest expiration is determined according to the respective expiration conditions of the received query messages as specified in the data body of the received query message;

wherein the quickest expiration relates to the relative distance.

32. The apparatus of claim 31 wherein the quickest expiration specified by the query response message indicates a range of possible distances between the base node and the recipient node, the apparatus further comprising:

means for sending through the computer network at least two additional query messages, each of which includes;

an expiration parameter which specifies an expiration condition for the additional query message wherein the expiration condition corresponds to a distance within the range of possible distances; and

a data body which includes data specifying the expiration condition of the additional query message as specified in the expiration parameter of the additional query message; and

means for receiving, from the recipient node, a subsequent query response message which includes data specifying a new quickest expiration of at least one received one of the additional query messages which is received by the recipient node, wherein the new quickest expiration is determined according to the respective expiration conditions of the received additional query messages as specified in the data body of the received additional query message.

33. An apparatus for determining relative distances between a base node and at least one other nodes of a computer network, the apparatus comprising:

means for receiving, from the base node through the computer network, at least one query message, each of which includes;

an expiration parameter which specifies an expiration condition for the query message; and

a data body which includes data specifying the expiration condition of the query message as specified in the expiration parameter of the query message; and

means for determining a quickest expiration of the at least one query message, wherein the quickest expiration is determined according to the respective expiration conditions of the query messages as specified in the data body of the query message;

wherein the quickest expiration relates to the relative distance.

34. The apparatus of claim 33 further comprising:

means for sending, to the base node, a query response message which includes data specifying the quickest expiration.