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

• US 7,697,452 B2
• Filed: 03/01/2007
• Issued: 04/13/2010
• Est. Priority Date: 03/07/2006
• Status: Expired due to Fees

• 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
• Primary Examiner(s): Nguyen; Brian D
• Application Number:
  US11/712,426
• Publication Number:
  US 20070211645A1
• Time in Patent Office: 1,139 Days
• Field of Search: 370/252, 370/242, 370/244, 370/253, 370/254, 370/255, 370/235, 370/236, 370/237
• 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 and a management apparatus for classifying congestion paths based on packet delay in a plurality of paths between measurement nodes. The method and the apparatus specify the short-time congestions based on packet delay in Internet Protocol network.

Claims

1. A method in a management apparatus for classifying congestion paths among a plurality of paths between measurement nodes, the method comprising:

receiving measurement data units each indicating an origin node, a destination node, and a sent time and a received time in received packets from the measurement nodes,

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

extracting at least one pair of measurement data units which are temporally adjacent and which have an interval time between the sent times of the adjacent measurement data units, the interval time being shorter than a threshold time,

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

extracting at least one pair of measurement data units which are temporally adjacent and which have an interval time between the received times of the adjacent measurement data units, the interval time being shorter than the threshold time,

calculating a plurality of packet delay values based on differences between the sent times and the received times for the extracted measurement data units, and

classifying the congestion paths based on the packet delay values.

2. The method according to claim 1, wherein the classifying comprises:

calculating a minimum value of the packet delay values for each path,

calculating a square sum of differences between the packet delay values and the minimum value for each of a plurality of path pairs, each path pair being made of two different paths selected from this plurality of paths,

calculating a mean of square sum as non-similarity for each path pair, and

selecting at least one path pair of low non-similarity, from the plurality of path pairs.

3. The method according to claim 2, wherein the classifying further comprises:

generating a dendrogram by application of a Ward system to the plurality of path pairs in ascending order of the non-similarity, and

classifying the congestion paths depending on the non-similarity of the dendrogram.

4. A management apparatus for classifying congestion paths among a plurality of paths between measurement nodes, the management apparatus comprising:

means for receiving measurement data units each indicating an origin node, a destination node, and a sent time and a received time in received packets from the measurement nodes,

means for arranging the measurement data units of the same origin node in order of sent time, extracting at least one pair of measurement data units which are temporally adjacent and which have an interval time between the sent times of the adjacent measurement data units, the interval time being shorter than a threshold time, arranging the measurement data units of the same destination node in order of the received time, and extracting at least one pair of measurement data units which are temporally adjacent and which have an interval time between the received times of the adjacent measurement data units, the interval time being shorter than the threshold time,

means for calculating packet delay values based on differences between the sent times and the received times for the extracted measurement data units, and

means for classifying the congestion paths based on the packet delay values.

5. The apparatus according to claim 4, wherein the classifying means comprises:

means for calculating a minimum value of the packet delay for values for each path,

means for calculating a square sum of differences between the packet delay values and the minimum value for each of a plurality of path pairs, each path pair being made of two different paths selected from the plurality of paths, calculating a mean of the square sum as non-similarity for each path pair, and selecting at least one path pair of low non-similarity, from the plurality of path pairs.

6. The apparatus according to claim 5, wherein the classifying means further comprises:

means for generating a dendrogram by application of a Ward system to the plurality of path pairs, in ascending order of the non-similarity, and

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

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 in said management apparatus comprising:

receiving measurement data units each indicating an origin node, a destination node, and a sent time and a received time in received packets from the measurement nodes,

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

extracting at least one pair of measurement data units which are temporally adjacent and which have an interval time between the sent times of the adjacent measurement data units, the interval time being shorter than a threshold time,

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

extracting at least one pair of measurement data units which are temporally adjacent and which have an interval time between the received times of the adjacent measurement data units, the interval time being shorter than the threshold time,

calculating a plurality of packet delay values based on differences between the sent times and the received times for the extracted measurement data units, and

classifying the congestion paths based on the packet delay values.

8. The method according to claim 7, wherein the classifying comprises:

calculating a minimum value of the packet delay values for each path,

calculating a square sum of differences between the packet delay values and the minimum value for each of a plurality of path pairs, each path pair being made of two different paths selected from the plurality of paths,

calculating a mean of the square sum as non-similarity for each path pair, and

selecting at least one path pair of low non-similarity, from the plurality of path pairs.

9. The method according to claim 8, wherein the classifying further comprises:

generating a dendrogram by application of a Ward system to the plurality of path pairs in ascending order of the non-similarity, and

classifying the congestion paths depending on the non-similarity of the dendrogram.

10. A method in a management apparatus for classifying congested paths among a plurality of paths between a plurality of nodes, the method comprising:

receiving from the nodes a plurality of packets each of which indicates an origin node, a destination node, and a transmit time and a receive time of each packet;

extracting from the received packets at least one first packet pair each of which is made of two packets, wherein the two packets share a same origin node, the two packets are temporally adjacent to each other, the two packets have an interval time between the transmit times of the adjacent packets, the interval time being shorter than a threshold time, and the two packets are related to two different paths;

extracting from the received packets at least one second packet pair each of which is made of two packets, wherein the two packets share a same destination node, the two packets are temporally adjacent to each other, the two packets have an interval time between the receive times of the adjacent packets, the interval time being shorter than the threshold time, and the two packets are related to two different paths; and

classifying the congested paths into a plurality of clusters, by performing cluster analysis for a plurality of path pairs using the extracted packet pairs, each path pair being made of two different paths selected from the plurality of paths.

11. The method according to claim 10, further comprising calculating a plurality of packet delay values for a plurality of packets which belong to the extracted packet pairs,

wherein the classifying comprises performing the cluster analysis for the path pairs, based on the calculated packet delay values.

12. The method according to claim 11, wherein the classifying comprises:

per each path pair, calculating a degree of non-similarity between two paths which belong to each path pair, based on differences in packet delay between two packets that belong to one of the extracted packet pairs which corresponds to each path pair; and

performing the cluster analysis for the path pairs, based on a plurality of degrees of non-similarity calculated for the respective path pairs.