Method for determining the delay and jitter in communication between objects in a connected network

• US 7,123,589 B1
• Filed: 06/23/2000
• Issued: 10/17/2006
• Est. Priority Date: 11/18/1999
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Peregrine Systems Incorporated (HP Inc.)
• Inventors: Ramaswamy, Arvind, Dawes, Nicholas W., Slavitch, Michael
• Primary Examiner(s): LEE, CHI HO A
• Application Number:
  US09/599,963
• Time in Patent Office: 2,307 Days
• Field of Search: 370/229, 370/230, 370/235, 370/242, 370/248, 370/250, 370/252, 370/389, 370/392, 370/400
• US Class Current: 370/248
• CPC Class Codes: H04L 2012/5628 Testing
• CPC Class Codes: H04L 2012/5649 Cell delay or jitter
• CPC Class Codes: H04L 41/0681 Configuration of triggering conditions
• CPC Class Codes: H04L 41/5009 Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]
• CPC Class Codes: H04L 43/087 Jitter
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/46 Cluster building

Abstract

Methods which determine network performance by determining not only the transit delay between nodes in a network but also the variance, or jitter, of such transit delays. A common node, usually a network management computer (NMC), sends out a signal to a first node of interest and measures the time before it receives an acknowledgment from the first node. The NMC then sends out a similar signal to a second node of interest and similarly measures the time required to receive an acknowledgment. Based on these two measurements, the transit delay between the first and second nodes can be calculated if the first node lies on the path between the NMC and the second node or vice versa. For a multiple node communications path, the total transit delay between any two nodes is the sum total of the transit delays between adjacent nodes lying on the path. In the case of meshed networks, where a path to a node may be ambiguous, additional measurement nodes strategically positioned in the network can be used such a way that the transit delay between any adjacent pair of nodes can be calculated unambiguously from at least one of these measurement nodes, i.e., the portion of the network being measured will be reduced to a hierarchical one with respect to at least one of the measurement nodes.

Claims

1. A method of determining a total processing overhead delay between a first node and a second node in a network connected to both the first node and the second node, the method comprising:

a) determining interim transit delays processing overhead delays between adjacent nodes in a communications path between the start node and the end node including the following steps;

a1) sending a first signal from a common node to the first node;

a2) receiving a first response signal at the common node from the first node in response to the first signal;

a3) determining a first round trip time, the first round trip time being a time elapsed between steps a) and b);

a4) sending a second signal from the common node to the second node;

a5) receiving a second response signal at the common node from the second node in response to the second signal;

a6) determining a second round trip time, the second round trip time being a time elapsed between steps d) and e); and

a7) calculating the transit delay between the first node and the second node according to the formula

D(X,Y)=|R(NMC,X)−

R(NMC,Y)|/2

where

D(X,Y) is the transit delay between first node X and second node Y;

R(NMC,X) is the first round trip time;

R(NMC,Y) is the second round trip time; and

NMC is the common node;

a8) subtracting a previously determined minimum transit delay between the first node and the second node with the transit delay between the first node and the second node; and

b) calculating the total transit overhead processing delay between the start node and the end node by adding up the interim transit processing overhead delays.

2. A method as in claim 1 wherein at least one of the first and second nodes are directly connected to the common node.

3. A method as in claim 1 wherein at least one of the first and second nodes are indirectly connected to the common node.

4. A method of determining the quality of communications between two nodes in a network, the method comprising:

a) measuring a transit delay between the two nodes at different times resulting in a plurality of transit delay measurements;

b) calculating a jitter among the plurality of time delay measurements based on measuring a variance of the plurality of transit delay measurements; and

c) determining if the jitter exceeds a predetermined threshold value.

5. A method as in claim 4 wherein the network is a hierarchical network and the transit delay is measured between a first node and a second node using the following method:

a) sending a first signal from a common node to the first node;

b) receiving a first response signal at the common node from the first node in response to the first signal;

c) determining a first round trip time, the first round trip time being a time elapsed between steps a) and b);

d) sending a second signal from the common node to the second node in response to the second signal;

e) receiving a second response signal at the common node from the second node in response to the second signal;

f) determining a second round trip time, the second round trip time being a time elapsed between steps d) and e); and

g) calculating the transit delay between the first node and the second node according to the formula

D(X,Y)=|R(NMC,X)−

R(NMC,Y)|/2

where

D(X,Y) is the transit delay between first node X and second node Y;

R(NMC,X) is the first round trip time;

R(NMC,Y) is the second round trip time; and

NMC is the common node.

6. A method as in claim 4 wherein the transit delay is measured between a start node and an end node in a hierarchical network using the following method:

a) determining interim transit delays between adjacent nodes in a communications path between the start node and the end node; and

b) calculating the total transit delay between the start node and the end node by adding up the interim transit delays.

7. A method as in claim 5 wherein the hierarchical network is a portion of a mesh network.

8. A method as in claim 7 wherein the hierarchical network is a portion of a mesh network.

9. A method as in claim 4 wherein step c) includes determining if at least one of the transit delay measurements exceeds a predetermined threshold value.

10. A method of determining a jitter between two transit delay measurements between two nodes, the method comprising:

calculating the jitter based on

J(A,D,t)=D(A,D,t2)−

D(A,D,t1))

where

J(A,D,t) is the jitter between the two transit delay measurements based on measuring a variance of the two transit delay measurements;

D(A,D,t1) is one of the two transit delay measurements taken at time t1;

D(A,D,t2) is the other of the two transit delay measurements taken at time t2; and

A and D are the two nodes between which the transit delay is measured.

11. A method as in claim 10 wherein the two nodes are directly connected to each other.

12. A method as in claim 10 wherein the two nodes are indirectly connected to each other.

13. A method of determining a jitter between a plurality of transit delay measurements between two nodes, the method comprising:

calculating the jitter based on

$J<br><br>\left(A,B\right)=\frac{\sqrt{\underset{i=1}{\overset{M}{\sum <br><br>}}<br><br>{D<br><br>\left(A,B,i\right)}^2}}{\underset{i=1}{\overset{M}{\sum <br><br>}}<br><br>D<br><br>\left(A,B,i\right)}$

 

where

J(A,B) is the jitter between the plurality of transit delay measurements;

D(A,B,i) is the i^th transit delay measurement among the plurality of transit delay measurements; and

M is the number of transit delay measurements.

14. A method as in claim 13 wherein the two nodes are directly connected to each other.

15. A method as in claim 13 wherein the two nodes are indirectly connected to each other.

16. A method of determining a signal processing time in a node, the method comprising:

a) determining at least one round trip delay time of a transmission between a node A and a node K;

b) determining a round trip delay time of a transmission between a node B and a node K;

c) determining a lowest recorded value for the round trip delay time between node A and node K;

d) calculating the signal processing time through node A according to;

P(A)=R(K,B)−

minimum (R(K,A))

 

where

P(A) is the signal processing time through node A;

R(K,B) is a round trip delay time between node B and node K; and

(minimum (R(K,A)) is the lowest recorded value for the round trip delay time between node A and node K.