Method and management apparatus for classifying congestion paths based on packet delay

• US 20070211645A1
• Filed: 03/01/2007
• Published: 09/13/2007
• Est. Priority Date: 03/07/2006
• Status: Active Grant

• Current Assignee: KDDI R&D Laboratories Inc. (KDDI Corporation)
• Original Assignee: KDDI R&D Laboratories Inc. (KDDI Corporation)
• Inventors: Ano, Shigehiro, Tachibana, Atsuo, Hasegawa, Toru
• Granted Patent: US 7,697,452 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/16 Threshold monitoring

Abstract

A method for classifying congestion paths based on packet delay in a plurality of paths between measurement nodes, has the following steps. First, it receives a measurement data unit including an origin node, a destination node, and a sent time and a received time in a received packet from the measurement node. Then, it arranges the measurement data units of the same origin node in order of sent time, and extracts a pair of measurement data units of which an interval time between the sent times of adjacent measurement data units is less than the threshold time. Then, it arranges the measurement data units of the same destination node in order of the received time, and extracts a pair of measurement data units of which an interval time between the received times of adjacent measurement data units is less than the threshold time. And it calculates packet delay based on the difference between the sent time and the received time for a plurality of extracted measurement data units, and specifies the congestion path based on the packet delay.

Claims

1. A method for classifying congestion paths based on packet delay in a plurality of paths between measurement nodes, the method comprising the steps of:

receiving a measurement data unit including an origin node, a destination node, and a sent time and a received time in a received packet from the measurement node,

arranging the measurement data units of the same origin node in order of sent time,

extracting a pair of measurement data units of which an interval time between the sent times of adjacent measurement data units is less than the threshold time,

arranging the measurement data units of the same destination node in order of the received time,

extracting a pair of measurement data units of which an interval time between the received times of adjacent measurement data units is less than the threshold time,

calculating packet delay based on the difference between the sent time and the received time for a plurality of extracted measurement data units, and

specifying the congestion path based on the packet delay.

2. The method as claimed in claim 1, wherein the specifying step,

calculates the minimum value of the packet delay for every path,

calculates square sum of difference between the packet delay and the minimum value for every two pair of measurement data units,

calculates the mean of those square sums as non-similarity, and

derives the pair of measurement data units of low non-similarity.

3. The method as claimed in claim 2, wherein the specifying step further,

generates a tendrogram applied by Ward system in order of the pairs of the low non-similarity, and

classifies the paths depending on non-similarity of the tendrogram.

4. A management apparatus for classifying congestion paths based on packet delay in a plurality of paths between measurement nodes, the management apparatus comprising:

means for receiving a measurement data unit including an origin node, a destination node, and a sent time and a received time in a received packet from the measurement node,

means for arranging the measurement data units of the same origin node in order of sent time, extracting a pair of measurement data units of which an interval time between the sent times of adjacent measurement data units is less than the threshold time, arranging the measurement data units of the same destination node in order of the received time, extracting a pair of measurement data units of which an interval time between the received times of adjacent measurement data units is less than the threshold time,

means for calculating packet delay based on the difference between the sent time and the received time for a plurality of extracted measurement data units, and

means for specifying the congestion paths based on the packet delay.

5. The apparatus as claimed in claim 4, wherein the specifying means comprising:

means for calculating the minimum value of the packet delay every path,

means for calculating square sum of difference between the packet delay and the minimum value for every pair of measurement data units, calculating the mean of those square sums as non-similarity, and deriving the pair of measurement data units of low non-similarity.

6. The apparatus as claimed in claim 5, wherein the specifying means further comprising:

means for generating a tendrogram applied by Ward system in order of the pairs of the low non-similarity, and

means for classifying the paths depending on non-similarity of the tendrogram.

7. A method for causing a computer to function as a management apparatus for classifying congestion paths based on packet delay in a plurality of paths between measurement nodes, the method comprising the steps of:

receiving a measurement data unit including an origin node, a destination node, and a sent time and a received time in a received packet from the measurement node,

arranging the measurement data units of the same origin node in order of sent time,

extracting a pair of measurement data units of which an interval time between the sent times of adjacent measurement data units is less than the threshold time,

arranging the measurement data units of the same destination node in order of the received time,

extracting a pair of measurement data units of which an interval time between the received times of adjacent measurement data units is less than the threshold time,

calculating packet delay based on the difference between the sent time and the received time for a plurality of extracted measurement data units, and

specifying the congestion path based on the packet delay.

8. The method as claimed in claim 7, wherein the specifying step,

calculates the minimum value of the packet delay for every path,

calculates square sum of difference between the packet delay and the minimum value for every pair of measurement data units,

calculates the mean of those square sums as non-similarity, and

derives the pair of measurement data units of low non-similarity.

9. The method as claimed in claim 8, wherein the specifying step further,

generates a tendrogram applied by Ward system in order of (the pairs of) the low non-similarity, and

classifies the paths depending on non-similarity of the tendrogram.