Electrical computers and digital processing systems: multicomput – Computer network managing – Computer network monitoring
Reexamination Certificate
1998-05-14
2001-02-20
Maung, Zarni (Department: 2758)
Electrical computers and digital processing systems: multicomput
Computer network managing
Computer network monitoring
C709S223000, C709S227000, C709S228000, C709S238000, C709S242000, C370S238000
Reexamination Certificate
active
06192404
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer networks and, in particular, to a particularly effective mechanism for determining distances between nodes of a computer network when time-to-live (TTL) parameters of the headers of messages are not accessible.
BACKGROUND OF THE INVENTION
Networks of computer systems are ubiquitous in our society and such networks range in size from two-computer local area networks to wide area networks which include thousands of computers and which span the entire world. It is frequently desirable to send a message to many other computers of a computer network.
Multicasting is a mechanism by which a relatively low number of messages can be used to convey a message to many computers of a computer network. Consider, for example, computer network
100
shown in FIG.
1
. Suppose computer
102
A has a message to send to all computers
102
B-Y of computer network
100
. Through multicast, computer
102
A forms a single copy of the message and sends the message to computers
102
B-D to which computer
102
A is directly coupled through computer network
100
as shown. Computer
102
D recognizes the message as multicast and forms additional copies to send to computers
102
E-H, to which computer
102
D is directly coupled through computer network
102
D as shown. Similarly, computer
102
H forwards copies of the message to computers
102
J-L, and the message is propagated through computer network
100
to all of computers
102
B-Y.
Unicast is a messaging protocol in which each message has an intended recipient. Using unicast to send a message from computer
102
A to computers
102
B-Y involves twenty-two separate messages transmitted through the portion of computer network
100
between computers
102
A and
102
D. By comparison, multicast transmits a single message through that portion of computer network
100
. The efficiency of multicast relative to unicast is relatively modest in this illustrative example in comparison to multicast messages through wide-area networks which include thousands of computers.
It is frequently desirable to send messages to a local portion of a wide-area network. Messages therefore include a time-to-live (TTL) parameter which establishes a condition for expiration of a multicast message. The TL parameter of a multicast message is initialized by the sending computer and is decreased by each computer which forwards the multicast message. In some networks, the TTL parameter of a multicast message is decremented, i.e., decreased by one, by each computer which forwards the message such that the TTL parameter specifies an expiration condition in terms of network hops. In other networks, each computer which forwards a message decreases the TTL parameter of the message by an amount of time required to transfer the message to the computer such that the TTL parameter specifies an expiration condition in terms of an amount of time the message is permitted to travel. Some of the latter networks require that each computer decrease the TTL parameter by at least one second such that the TTL parameter specifies an expiration condition in terms of a combination of a maximum number of network hops and a maximum amount of time. When the TTL parameter of a multicast message is decreased below a predetermined threshold, which is typically zero, the multicast message is destroyed. The following example is illustrative.
Suppose computer
102
A wishes to send a multicast message to computers
102
B-G. Computer
102
A can form a multicast message with a TTL parameter whose value is two. The message reaches computers
102
B-D since computers
102
B-D are coupled directly to computer
102
A, through computer network
100
. Computer
102
D decrements the TTL parameter of the message to have a value of one and forwards the multicast message to computers
102
E-H. Thus, computers
102
B-G receive the multicast message. In addition, computer
102
H receives the multicast message. Computer
102
H decrements the TTL parameter of the multicast message to have a value of zero. Accordingly, computer
102
H destroys the multicast message. As a result, the multicast message does not pass beyond computer
102
H and does not unnecessarily burden the remainder of computer network
100
.
To determine what value to which to set the TTL parameter of a particular multicast message, each computer of a computer network generally includes a database in which the distance to each other computer of the computer network in terms of TTL parameter values are stored. Such a distance is referred to as a TTL distance. To populate such a database, a computer of a computer network must generally be capable of determining such TTL distances. In computer networks in which header information of messages can be directly examined, such determination is a matter of comparing the difference between the initial and current values of the TTL parameter of messages from specific computers. However, initial TTL parameters of received messages are generally not stored in the header of such messages and, in a number of computer network environments, current TTL parameter values are not accessible.
One mechanism for determining TTL distances between computers of a computer network when current TTL parameter values cannot be directly examined is called an expanding ring search. In general, a multicast message with a TTL parameter whose value is one is sent through the computer network. All computers which respond are determined to have a TTL distance of one. Next, a multicast message with a TTL parameter whose value is two is sent through the computer network. All computers which respond are determined to have a TTL distance of two. Multicast messages with ever increasing TTL parameter values are sent and responses from such multicast messages are gathered to determine the TTL distances of all computers of the computer network.
Expanding ring search suffers from some disadvantages. First, expanding ring search is slow. In general, each computer of the computer network must respond to each multicast message before the next multicast message can be sent. In addition, the computer which sent the original multicast message determines that all computers have responded by waiting a predetermined amount of time. Such a predetermined amount of time can be several seconds in duration, and a complete expanding ring search can include several hundred multicast messages. As a result, determination of TTL distances using expanding ring search can take several minutes.
The second disadvantage of expanding ring searches is that such places a substantial burden on the computer network in terms of message traffic. Specifically, each computer of the computer network responds to each and every multicast message received. In a computer network which includes thousands of computers, each of several hundred multicast messages can elicit thousands of responding messages. Accordingly, expanding ring search can burden a large computer network with hundreds of thousands of messages. If each computer of such a computer network uses an expanding ring search to determine TTL distances to other computers of the computer network, the burden upon the computer network in terms of message traffic is enormous.
What is needed is a mechanism by which computers of a computer network can determine TTL distances to other computers of the computer network without requiring excessive amounts of time or of computer network bandwidth.
SUMMARY OF THE INVENTION
In accordance with the present invention, a base node of a computer network sends TTL query messages using multicast to other receiving nodes of the computer network. The base node is the node of the computer network from which TTL distances are to be measured. Each of the TTL query messages has a different 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 me
Chiu Dah Ming
Hanna Stephen R.
Hurst Stephen A.
Pearlman Radia J.
Barot Bharat
Ivey, Esq. James D.
Maung Zarni
Sun Microsystems Inc.
LandOfFree
Determination of distance between nodes in a computer network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Determination of distance between nodes in a computer network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determination of distance between nodes in a computer network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2572933