JP2008042879A - Congestion path classification method to classify congestion path based on packet delay fluctuation, management apparatus and program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a congestion path classification method or the like which, in order to detect congestion caused in a short period of time due to packet delay, classifies paths experiencing such congestion in common on the basis of the packet delay. <P>SOLUTION: Measurement information including a transmission time and a reception time is received for each packet received by a measurement terminal. With respect to two paths, a group of packet pairs is extracted in which at least a part of transfer times between the transmission time and the reception time overlaps with each other. Packet delay is calculated based on the transmission and reception times for the extracted packet pairs. Then, a minimum packet delay is derived for every path from the packet delays of the multiple measurement information within a predetermined period. A difference between the packet delay and the minimum delay time for every measurement information is calculated as a delay fluctuation time. A minimum warping path with a minimum warping cost is derived from the group of the extracted packet pairs. Finally, non-similarity between the two paths on the minimum warping path is calculated. <P>COPYRIGHT: (C)2008,JPO&INPIT

Description

  The present invention relates to a congestion path classification method, a management apparatus, and a program for classifying a congestion path based on a delay variation time of a packet. In particular, the present invention relates to a method for classifying paths in order to identify short-time congestion based on packet delay in an IP (Internet Protocol) network.

  Since the Internet is a best-effort type communication, it is difficult to ensure accurate communication quality. On the other hand, an ISP (Internet Service Provider) company specifies a quality degradation section and avoids quality degradation by operation control such as route change or line speedup. However, since the Internet is constituted by a large number of independent networks, there are cases where the state inside the network cannot be directly measured.

  2. Description of the Related Art Conventionally, there is a technology for actively measuring characteristics of a plurality of paths (for example, packet loss rate, packet delay, etc., hereinafter referred to as “path state”) between measurement terminals to identify a network quality degradation period (for example, non-patent document). 1). A section means a part of a path divided by a branching / merging point. In this technique, the measurement result is compared with a predetermined threshold value, and the quality of the path is determined in stages (good / bad / medium). Then, a quality degradation section in the network is specified based on a combination of paths determined to be quality degradation and route information of those paths.

  In addition, there is a technique in which a plurality of test packets are simultaneously transmitted to a plurality of paths at short time intervals, and the quality of a shared section is estimated by correlation of received packets (see, for example, Non-Patent Document 2).

  There is also a network tomography technology that indirectly estimates network internal characteristics (delay variation and loss rate distribution) that are difficult to measure directly for the purpose of quality control and management of large-scale networks ( For example, refer nonpatent literature 2, 3 and 4.).

A. Tachibana, S. Ano, T. Hasegawa, M. Tsuru, Y. Oie, “Locating Congested Segments over the Internet Based on Multiple End-to-End Path Measurements”, IEICE Transactions on Communications Internet Technology VI, April 2006 M. Tsuru, T. Takine and Y. Oie., "Inferringlink characteristics from end-to-end path measurements", In Proc. IEEE ICC, Helsinki (2001), 1534-1538 R. Caceres, N. Duffield, J. Horowitz, D. Towsley, `` Multicast-based inference of network-internal loss characteristics '', IEEE Trans. Info. Theory, 45 (7): 2462--2480, 1999. N. Duffield, F. L. Presti, V. Paxson, D. Towsley, "Inferring link loss using striped unicast probes", Proc. IEEE infocom, Anchorage, Apr. 2001.

  However, as in Non-Patent Document 1, when a total value (for example, an average value or a maximum value in a certain period) is compared with a predetermined threshold value, if the difference between the total value and the threshold value is small, extremely normal / abnormal is determined. It will be judged. Therefore, there is a possibility that the classification result varies greatly depending on the threshold value. Further, according to Non-Patent Document 2, in order to determine the correlation between packets for all test packets, very high-precision measurement and complicated calculation are required. It is often difficult to send very close test packets.

  In the prior art, for each path, the deterioration state is determined based on a total value obtained by calculating an average value or a maximum value of the path state. Actually, when quality degradation occurs in one section, the quality degradation occurs simultaneously in a plurality of paths passing through the section. Nevertheless, it is determined that each path has a single deterioration state, and an attempt is made to detect the correlation of the paths from the total values.

  In addition, according to the prior art, it is not possible to specify congestion that occurs for a short time (for example, about 20 ms) such as packet delay in order to specify a quality degradation section from the aggregated value of the path state for each path. . However, when a backbone network is constructed with optical fibers, even a short-time congestion has a great influence on the entire network. Therefore, it is necessary to avoid a route that sometimes causes short-term congestion.

  Furthermore, in recent years, applications such as VoIP (Voice over IP) whose quality deteriorates due to packet delay variation are increasing.

  Furthermore, according to the network tomography technique, since the statistical characteristic (distribution) is used, it is difficult to apply to the real-time estimation of the quality degradation section. In addition, a large amount of measurement packets (test packets and probe packets) are required. In order to estimate with high accuracy, it is necessary to transmit / receive a multicast packet or a continuous packet with a small packet interval as a measurement packet, so that there is also a problem that it can be applied only to a tree topology.

  Therefore, in order to detect congestion that occurs in a short time for an IP network, the present invention periodically compares the time series of delay variation of a plurality of packets, so that a path that experiences the congestion in common can be obtained. An object of the present invention is to provide a congestion path classification method, a management apparatus, and a program that can be classified in real time.

According to the present invention, there is a congestion path specifying method in a management device that classifies congestion paths based on delay variation times in paths between a plurality of measurement terminals,
A first step of receiving measurement information including a transmission source address, a reception terminal address, a transmission time, and a reception time from the measurement terminal based on the measurement packet received by the measurement terminal;
A second step of extracting, for the two paths, a set of packet pairs in which at least part of the transfer time between the transmission time and the reception time overlaps;
A third step of calculating a delay time of each packet from the transmission time and the reception time of the measurement information for the extracted packet pair;
A fourth step of calculating a delay variation time from a plurality of delay times in a predetermined period for each path;
A fifth step of deriving a minimum warping path that minimizes the warping cost from the set of extracted packet pairs;
A sixth step of calculating dissimilarity between two paths in the minimum warping path;
And a seventh step of identifying a set of non-congested paths and a set of congested paths by clustering dissimilarities.

According to another embodiment of the congestion path identifying method of the present invention, for the fourth step,
It is also preferable to derive a minimum delay time among packet delays of a plurality of measurement information in a predetermined period for each path, and to calculate a difference between the delay time and the minimum delay time as a delay variation time for each measurement information.

  According to another embodiment of the congestion path identifying method of the present invention, in the fourth step, when the maximum value of the difference between the delay time and the minimum delay time is equal to or less than a predetermined threshold, the path is considered to be non-congested. Identifies as a path.

  According to another embodiment of the congestion path identifying method of the present invention, with respect to the seventh step, for each packet pair of two paths, a ratio of the average value to the square of the difference in delay variation time is calculated. It is also preferable to derive a pair of two paths having a low dissimilarity calculated by the sum of these ratios.

According to another embodiment of the congestion path identifying method of the present invention,
Create a dendrogram by applying the Ward method in order from the pair with the lowest dissimilarity between the two paths.
It is also preferable to classify the paths according to the dendrogram dissimilarity.

According to the present invention, in a management device that classifies congestion paths based on delay variation times in paths between a plurality of measurement terminals,
Measurement information collection means for receiving measurement information including a transmission source address, a reception terminal address, a transmission time and a reception time from the measurement terminal based on the measurement packet received by the measurement terminal;
Measurement information extraction means for extracting a set of packet pairs in which at least part of the transfer time between the transmission time and the reception time overlaps for the two paths;
Delay time calculation means for calculating the delay time of each packet from the transmission time and reception time of the measurement information for the extracted packet pair;
A delay variation calculating means for calculating a delay variation time from a plurality of delay times in a predetermined period for each path;
A minimum warping path deriving means for deriving a minimum warping path that minimizes the warping cost from the set of extracted packet pairs;
Dissimilarity calculating means for calculating dissimilarity between two paths in the minimum warping path;
Congestion path specifying means for specifying a set of non-congested paths and a set of congested paths by clustering is provided.

According to another embodiment of the management device of the present invention,
For each path, it further comprises a minimum delay time deriving means for deriving a minimum delay time among packet delays of a plurality of measurement information in a predetermined period,
It is also preferable that the delay variation calculating means calculates, for each measurement information, a difference between the delay time and the minimum delay time as the delay variation time.

  According to another embodiment of the management device of the present invention, if the maximum value of the difference between the delay time output from the delay variation calculation means and the minimum delay time is equal to or less than a predetermined threshold, the path is not congested. Non-congested path filter means for specifying the path is further included.

  According to another embodiment of the management device of the present invention, the congestion path specifying means calculates, for each packet pair of two paths, a ratio of their average value to the square of the difference in delay variation time, It is also preferable to derive a pair of two paths having a low dissimilarity calculated by the sum of the ratios.

According to another embodiment of the management device of the present invention, the congestion path specifying means includes:
A dendrogram creating means for creating a dendrogram by applying the Ward method in order from a pair of low dissimilarities of two paths;
It is also preferable to further include path classification means for classifying paths according to the dendrogram dissimilarity.

According to the present invention, in a program for causing a computer mounted on a management device that classifies a congestion path to function based on a delay variation time in a path between a plurality of measurement terminals,
Measurement information collection means for receiving measurement information including a transmission source address, a reception terminal address, a transmission time and a reception time from the measurement terminal based on the measurement packet received by the measurement terminal;
Measurement information extraction means for extracting a set of packet pairs in which at least part of the transfer time between the transmission time and the reception time overlaps for the two paths;
Delay time calculation means for calculating the delay time of each packet from the transmission time and reception time of the measurement information for the extracted packet pair;
A delay variation calculating means for calculating a delay variation time from a plurality of delay times in a predetermined period for each path;
A minimum warping path deriving means for deriving a minimum warping path that minimizes the warping cost from the set of extracted packet pairs;
Dissimilarity calculating means for calculating dissimilarity between two paths in the minimum warping path;
The computer is caused to function as a congestion path specifying means for specifying a set of non-congested paths and a set of congested paths by clustering.

According to another embodiment of the program for the management device of the present invention,
For each path, it further comprises a minimum delay time deriving means for deriving a minimum delay time among packet delays of a plurality of measurement information in a predetermined period,
The delay variation calculation means preferably causes the computer to function so as to calculate the difference between the delay time and the minimum delay time as the delay variation time for each measurement information.

  According to another embodiment of the program for the management apparatus of the present invention, if the maximum value of the difference between the delay time output from the delay variation calculation means and the minimum delay time is equal to or less than a predetermined threshold, the path Is further included as a non-congested path filter means for identifying a non-congested path.

  According to another embodiment of the program for the management apparatus of the present invention, the congestion path specifying means calculates the ratio of the difference between the squares of the delay variation times to the average value for each packet pair of the two paths. It is also preferable to cause the computer to function so as to derive a pair of two paths with low dissimilarity calculated by the sum of these ratios.

According to another embodiment of the management device program of the present invention, the congestion path specifying means
A dendrogram creating means for creating a dendrogram by applying the Ward method in order from a pair of low dissimilarities of two paths;
It is also preferable to cause the computer to function as path classification means for classifying paths in accordance with the dendrogram dissimilarity.

  According to the congestion path classification method, management device, and program of the present invention, in order to detect congestion occurring in a short time for an IP network, by periodically comparing the time series of delay variation of a plurality of packets, Paths that commonly experience the congestion can be classified in real time. In the measurement of the delay variation time, probe packets having a random packet interval are used, so that it can be applied to a large-scale IP network. Furthermore, the amount of calculation can be reduced by reducing the measurement information necessary for specifying the congestion path as much as possible.

  Hereinafter, the best mode for carrying out the present invention will be described in detail with reference to the drawings.

  The present invention transfers measurement packets (test packets, prolobe packets) at random intervals along a plurality of paths. Thereby, the delay variation time is measured. The collected delay variation times are periodically compared, and a group of paths experiencing common quality degradation is extracted based on the similarity of time series. Compare the route information of the path group and estimate the quality degradation section inside the network.

  FIG. 1 is a network configuration diagram.

  According to FIG. 1, four measuring terminals A to D are connected via a network having sections 1 to 5. A plurality of measurement packets are continuously transmitted and received between the measurement terminals. Further, the management device 2 is also connected to the network, and all the measurement terminals A to D transmit measurement information to the management device 2. Here, “path” refers to a route for each measurement terminal. The “section” means a part of a path divided by a branch / merge point.

  FIG. 1 also shows a network topology configuration table. For example, the path 1 represents a route between the measuring terminal A and the measuring terminal B, and is connected via the section 1, the section 2, and the section 3.

  FIG. 2 is an explanatory diagram showing packet reception in the present invention.

  According to FIG. 2, the measurement terminal B is focused. The measuring terminal B is connected to the measuring terminal A via the path 1 (section 1 to section 2 to section 3), and is connected to the measuring terminal C through the path 4 (section 5 to section 2 to section 3). And is connected to the measuring terminal D via the path 5 (section 4 to section 3).

  As is clear from the network topology shown in FIG. 2, for example, when congestion occurs in the section 2, the congestion is experienced by a plurality of packets via the paths 1 and 4. Further, congestion occurring in the section 3 is experienced by a plurality of packets passing through the paths 1, 4, and 5.

(S201) The measurement terminal B receives measurement packets from the measurement terminals A, C, and D. The measurement terminal B stamps the reception time for each received measurement packet. The measurement packet includes “source address”, “sequence number”, and “transmission time”.

  The measurement packet transmission interval does not have to be constant, and may be random. Note that the time is assumed to be synchronized in all measurement terminals A to D. Further, the measurement packet may be a measurement test packet (probe packet) or a normal data packet. For example, according to RTP (Realtime Transfer Protocol), a time stamp is included in the header.

(S202) The measurement terminal B generates measurement information for the received measurement packet. The measurement information includes “transmission source address”, “reception terminal address”, “transmission time”, and “reception time”. The “receiving terminal address” identifies the measuring terminal B. “Reception time” is the time at which the measurement terminal B receives the broadcast packet. Then, the measurement terminal B transmits the measurement information to the management device 2.

  Here, the measurement terminal 1 may be configured to transmit the measurement information to the management device 2 periodically (for example, every 10 seconds).

(S203) The management apparatus 2 not only receives measurement information from the measurement terminal B, but also receives measurement information from all measurement terminals. The received measurement information is recorded for each receiving terminal.

  FIG. 3 is a flowchart in the present invention.

(S201) The transmission side measurement terminal transmits a plurality of measurement packets to the counterparty measurement terminal. The same processing as S201 of FIG. 2 described above is performed.

(S202) The reception-side measuring terminal that has received the measurement packet transmits measurement information to the management apparatus 2. The same processing as S202 of FIG. 2 described above is performed.

(S203) The management device 2 constantly receives a plurality of pieces of measurement information from a plurality of measurement terminals. These pieces of measurement information are collected and stored more than a certain amount. The same process as S203 of FIG. 2 described above is performed.

(S204) The management apparatus 2 extracts, for each receiving terminal, a set of packet pairs in which at least part of the transfer time between the transmission time and the reception time overlaps for two paths having different transmission source addresses.

  For example, suppose that the i-th packet Pi in the path P is compared with the j-th packet Qj in the path Q. The path P is a route from the transmission terminal A to the reception terminal B. The path Q is a route from the transmission terminal C to the reception terminal B. Here, the transfer time of the packet Pi and the transfer time of the packet Qj are compared, and it is determined whether or not at least a part of them overlaps. The packet Pi transfer time is the time from the transmission time of the transmission terminal A to the reception time of the reception terminal B. The packet Qj transfer time is the time from the transmission time of the transmission terminal C to the reception time of the reception terminal B.

  Furthermore, it is also preferable to extract only the packet pairs whose time interval (packet pair gap) between the reception times is within the threshold time for the packets Pi and Qi determined to overlap at least part of the transfer time. The threshold time may be about several tens of milliseconds, for example, 20 ms. As a result, when congestion occurs due to a delay of about 20 ms or more in one section, a common influence is detected on different paths through the section.

  As a result, it is possible to extract only packets that may experience short-term congestion between paths at the same time and measure the delay variation time (difference between the delay time and the minimum delay time) for only those packets.

(S205) The management apparatus 2 calculates a delay time (= reception time−transmission time) from the transmission time and the reception time for each piece of measurement information in the extracted packet pair set.

(S206) For each path, a minimum delay time is derived among packet delays of a plurality of measurement information in a certain period. The minimum delay time is a reference value for the delay variation time. Therefore, the delay variation time is calculated with respect to the minimum delay time.

(S207) For each measurement information, the difference between the delay time and the minimum delay time is calculated as the delay variation time. That is, the delay variation time is defined by a change from the minimum delay time.

(S208) Here, a path whose maximum difference between the delay time and the minimum delay time is equal to or less than a predetermined threshold is specified as a non-congested path. The path specified as the non-congested path is notified to S212 as it is. Thereby, the process (S209-S211) which clusters a dissimilarity about a non-congested path can be omitted. Measurement information for a path that is unlikely to have passed through the quality degradation section is not introduced into the calculation. That is, only measurement information for a path that has a high possibility of passing through the quality degradation section can be introduced into the calculation. As the predetermined threshold value, for example, an average value of standard deviation values of delay variation of each path calculated from past measurement data is used as a range of normal values.

(S209) The minimum warping path that minimizes the warping cost is derived from each piece of measurement information in the extracted set of packet pairs. The warping path represents correspondence between two time series data. Here, the time warping distance is an element for deriving the degree of similarity between two time-series data by giving flexibility to displacement (expansion / contraction) in the time axis direction. For example, there are the following references.
Satoshi Oomo, Han Han Chen, Kazutaka Furuse, Nobuo Obo, “Similar search of time-series data based on time warping: Efficiency improvement by dimensional reduction”, Database Society of Japan Letters Vo.4, N0.1, [online], [Search July 5, 2006], Internet <URL: http://www.dbsj.org/Japanese/DBSJLetters/vol4/no1/papers/oomomo.pdf>

  FIG. 4 is an explanatory diagram of a warping path with respect to a packet delay variation time.

  In the N × M matrix of FIG. 4, the horizontal axis is a packet Pi (i = 1 to N) on the path P, and the vertical axis is a packet Qj (j = 1 to M) on the path Q. The delay variation times of the packets on the path P are represented by p1, p2,..., PN, and the delay variation times of the packets on the path Q are represented by q1, q2,.

An element of the N × M matrix represents a distance (dissimilarity) d (i, j) based on the following equation. The following equation expresses the ratio of the difference between the squares of the delay variation times of packets and their average value as a distance.
d (i, j) = (pi−qj) ² / average (pi, qi)
avarage (pi, qi): Average delay variation time of packets

  Two measurement packets are transmitted at random intervals (for example, a uniform distribution of about 50 ms). Since the two measurement packets are not synchronized, even if they experience the same quality degradation, the packet delay variation times do not match exactly. Therefore, if the delay variation time is long, the difference (pi−qj) between pi and qj becomes large.

  According to the present invention, the time warping distance for comparing the time series by expanding and contracting in the time axis direction is applied to the dissimilarity d.

  According to FIG. 4, for the packet Pi and the packet Qj, the elements in which the transfer times between the transmission time and the reception time overlap at least partially are shown in gray. For a set U of packet pairs represented in gray, warping paths W = w1, w2,..., WK, wk = (i, j), max (M, N) ≦ K <M + N− Derive 1

The warping path satisfies the following conditions.
(Condition 1) w1 = (min (i), min (j)) and wK = (max (i), max (j)). However, (i, j) εU.
(Condition 2) When wk = (a, b), wk + 1 = (a ′, b ′), 0 ≦ a−a ′ and 0 ≦ b−b ′. According to FIG. 4, the warping path always extends in the lateral direction and / or the upward direction.
(Condition 3) When wk = (a, b), wk + 1 = (a ′, b ′), a−a ′ ≦ 1 and b−b ′ ≦ 1. According to FIG. 4, when the warping path is extended, it always extends by one element. However, if the set U is divided into a plurality of partial data and (a ′, b ′) satisfying this condition does not exist, wk + 1 = (min (i), min (j)), (i > a, j> b)). As a result, the next warping path is found.

(S211) The dissimilarity between two paths in the minimum warping path is calculated. In the set U, since there are a plurality of warping paths that satisfy the conditions 1 to 3, the warping cost is calculated for each warping path. The warping cost is defined by the sum of d (wk) = d (i, j) (wk = (i, j)) in the warping path.
C = 1 / K · √ (Σ _{k = 1} ^K d (w _k ))

  The warping path that minimizes the warping cost is adopted as the minimum warping path. The warping cost is defined as the dissimilarity d between the two paths (d = min (C)).

Further, the degree of dissimilarity with a path whose delay variation time is virtually zero (referred to as “best path”) is calculated. The distance between the path P and the best path 0 is as follows.
d (P, 0) = d (w _k ) = pi

  FIG. 5 is a graph showing the similar relationship between the delay variation times of two paths.

  According to FIG. 5, a thin line is drawn between two delay variation times. This connects two packets with overlapping transfer times. By using the time warping distance, it is possible to derive the degree of similarity between two time-series data by giving flexibility to the shift (expansion / contraction) in the time axis direction.

(S210) For each pair of paths, a dendrogram (dendrogram) is created by applying the Ward method in cluster analysis (numerical classification method) in order from the pair with the lowest dissimilarity d.

  Cluster analysis refers to a method of creating a cluster by classifying objects that are similar to each other from a group in which different properties are intermingled and classifying objects. First, it is classified into clusters having each path as an element. When N paths are clustered, they are classified into N clusters. Then, two paths with the smallest dissimilarity d are extracted and combined into one cluster. As a result, the total number of clusters decreases by 1 to N-1.

  Next, the dissimilarity between the combined cluster and the remaining clusters is recalculated. Various algorithms have been proposed for the recalculation method, but a typical Ward method is applied.

  The Ward method is one of the hierarchical cluster analysis methods, and when classifying similar ones, the deviation sum of squares from the cluster centroid for all individuals in the cluster is obtained, and the cluster The inner sum of squares is merged so that the increment is as small as possible.

  Euclidean square distance is often used as a criterion for determining whether or not they are similar to each other. The merging of pairs of paths that are similar to each other is repeated until combined into one cluster to create a dendrogram. The dendrogram represents the dissimilarity relationship between the clusters.

(S212) The path is divided into a plurality of clusters by cutting at an appropriate height (for example, ½) in the dendrogram dissimilarity. When cutting at least at the highest position, it is classified into two clusters.

  Thereafter, the path information of each path is compared, and a section that is shared by paths experiencing common congestion and that does not pass through other paths is identified as a congestion section.

  As described above, when quality degradation occurs in a specific path, the influence also occurs on other paths that experience the same quality degradation. By classifying a set of packet pairs by clustering according to the delay variation time of the packets, it is possible to specify paths that experience the same quality degradation.

  FIG. 6 is a graph showing the delay variation of 30 paths in a certain 5 seconds, calculated by the traffic measurement experiment result on the Internet.

  The graph of FIG. 6 is calculated in S207. A network connected to three ISP (Internet Service Provider) networks via optical access lines at two sites was used. The active measurement experiment was performed for 24 hours through 30 paths by a combination of transmission and reception ISPs. In each path, 64-byte UDP test packets were transmitted at intervals according to a uniform distribution of 10 to 90 ms.

  The 99% value of the delay variation of each path packet was counted in a cycle of 5 seconds, and clustering of 30 paths was performed (704 times) for 5 seconds with a threshold time of 20 ms or more in at least one path.

  FIG. 7 is the dendrogram of FIG.

  The graph of FIG. 7 is created by S210. According to the graph of FIG. 7, the vertical axis represents the dissimilarity between clusters, and 30 paths are classified in order from the path with the lowest dissimilarity.

  When classified by the height of 1/2 of the maximum value of dissimilarity, according to the graph of FIG. 7, cluster A (paths 13, 24, 29, 3, 8) and cluster B (25 paths other than A) ) And 2). Here, the five paths included in the cluster A correspond to the five paths in which the packet delay variation is increased in synchronization in FIG. On the other hand, in the 25 paths included in the cluster B, the packet delay variation does not increase. In this way, the five paths that experience common congestion and the other 25 paths can be classified with high accuracy.

  For classification, first, 99% values of packet delay variation of paths classified into each cluster are totaled. For example, for 5 seconds in which one path has a threshold time of 20 ms or longer, the cluster to which the path belongs is determined to be a set of paths that have experienced common quality degradation. That is, according to FIGS. 6 and 7, since any of the five paths (paths 13, 24, 29, 3, 8) classified into cluster A has a threshold time of 20 ms or more, these 5 paths The book paths are classified as five paths that experience common congestion. On the other hand, in the 25 paths classified into the cluster B, since the 99% value of the packet delay variation does not become the threshold time of 20 ms or more, it is not determined that the common congestion has been experienced and is identified as a non-congested path. .

  In the above description, classification is performed with a height that is ½ of the maximum value of dissimilarity. Instead, it is also preferable to classify at a height such that the dissimilarity between two paths classified into the same cluster is always greater than the dissimilarity between two paths classified into different clusters.

  FIG. 8 is a functional configuration diagram of the measurement terminal and the management device according to the present invention.

  According to FIG. 8, the measurement terminal 1 includes a packet transmission unit 10, a packet reception unit 11, a measurement information generation unit 12, and a measurement information transmission unit 13. These functional units can also be realized by a program executed by a computer mounted on the measurement terminal 1.

  The packet transmission unit 10 transmits a plurality of packets including the transmission time to the counterparty measuring terminal. The operation of S201 described above is performed.

  The packet receiving unit 11 receives a plurality of packets including transmission times from a plurality of counterpart measurement terminals. The operation of S202 described above is performed.

  The measurement information generation unit 12 generates measurement information including the address of the transmission source terminal, the address of the destination terminal, the transmission time, and the reception time for each received packet. The operation of S203 described above is performed.

  The measurement information transmission unit 13 transmits the generated measurement information to the management device. The operation of S204 described above is performed.

  According to FIG. 8, the management device 2 includes a measurement information collection unit 21, a measurement information extraction unit 22, a delay time calculation unit 23, a minimum delay time derivation unit 24, a delay variation calculation unit 25, a non-congested path. The filter unit 26, the minimum warping path derivation unit 27, the dissimilarity calculation unit 28, and the congestion path classification unit 29 are included. The congestion path classification unit 29 includes a dendrogram creation unit 291 and a path classification unit 292. These functional units can also be realized by a program executed by a computer mounted on the management apparatus 2.

  The measurement information collection unit 21 receives and accumulates measurement information from a plurality of measurement terminals. The operation of S203 in FIG. 3 described above is performed.

  The measurement information extraction unit 22 extracts a packet pair to be measured. For the two paths, a set of packet pairs in which at least part of the transfer time between the transmission time and the reception time overlap is extracted. The operation of S204 in FIG. 3 described above is performed.

  The delay time calculation unit 23 calculates a packet delay from the transmission time and the reception time for the extracted packet pair. The operation of S205 in FIG. 3 described above is performed.

  The minimum delay time deriving unit 24 derives the minimum delay time among the packet delays of a plurality of measurement information in a predetermined period for each path. The operation of S206 in FIG. 3 described above is performed.

  The delay variation calculation unit 25 calculates the difference between the delay time and the minimum delay time as the delay variation time for each measurement information. The operation of S207 in FIG. 3 described above is performed.

  The non-congested path filter unit 26 specifies the path as a non-congested path when the maximum value of the difference between the delay time and the minimum delay time is equal to or less than a predetermined threshold. The path specified as the non-congested path is notified to the path classification unit 292 as it is. Thereby, it is possible to omit the process of clustering dissimilarities for non-congested paths. That is, the processes of the minimum warping path deriving unit 27, the dissimilarity calculating unit 28, and the dendrogram creating unit 291 can be omitted. As the predetermined threshold value, for example, an average value of standard deviation values of delay variation of each path calculated from past measurement data is used as a range of normal values. The non-congested path filter unit 26 performs the operation of S208 in FIG.

  The minimum warping path deriving unit 27 derives a minimum warping path that minimizes the warping cost from the set of extracted packet pairs. The operation of S209 in FIG. 3 described above is performed.

  The dissimilarity calculation unit 28 calculates dissimilarity between two paths in the minimum warping path. The dissimilarity calculation unit 28 calculates, for each packet pair of two paths, the ratio of the difference between the squares of the delay variation times and the average value thereof, and the dissimilarity calculated by the sum of the ratios is low. A pair of two paths is derived. The operation of S210 described above is performed. The operation of S210 in FIG. 3 described above is performed.

  The dendrogram creation unit 291 creates a dendrogram by applying the Ward method in order from the pair with the lowest dissimilarity for each pair of paths. The operation of S211 in FIG. 3 described above is performed.

  The path classification unit 292 classifies paths according to the dendrogram dissimilarity. The operation of S212 in FIG. 3 described above is performed.

  As described above in detail, according to the congestion path classification method, management apparatus, and program of the present invention, in order to detect congestion occurring in a short time for an IP network, a path that commonly experiences the congestion is detected. It is possible to classify from the packet delay variation time. Therefore, it is possible to classify paths even for degradation at a layer 2 node that cannot be detected by “traceroute”. The present invention can compare delay variation times of packets for each path in units of packets, and classify the quality of each path based on the similarity of the variation.

  According to the various embodiments of the present invention described above, those skilled in the art can easily make various changes, modifications and omissions within the scope of the technical idea and the viewpoint of the present invention. The above description is merely an example, and is not intended to be restrictive. The invention is limited only as defined in the following claims and the equivalents thereto.

It is a network block diagram. It is explanatory drawing showing reception of the packet pair in this invention. It is a flowchart in this invention. It is explanatory drawing of the warping path | route with respect to the delay variation time of a packet. It is a graph showing the similar relationship of the delay variation time of two paths. It is a graph showing the delay variation time of 30 paths in a certain 5 seconds calculated by the traffic measurement experiment result on the Internet. It is a dendrogram of FIG. It is a functional block diagram of the measurement terminal and management apparatus in this invention.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Measurement terminal 10 Packet transmission part 11 Packet reception part 12 Measurement information generation part 13 Measurement information transmission part 2 Management apparatus 21 Measurement information collection part 22 Measurement information extraction part 23 Delay time calculation part 24 Minimum delay time derivation part 25 Delay variation calculation part 26 Non-Congestion Path Filter Unit 27 Minimum Warping Path Derivation Unit 28 Dissimilarity Calculation Unit 29 Congestion Path Classification Unit 291 Dendrogram Creation Unit 292 Path Classification Unit

Claims (15)

A congestion path identification method in a management device that classifies congestion paths based on delay variation times in paths between a plurality of measurement terminals,
A first step of receiving measurement information including a transmission source address, a reception terminal address, a transmission time, and a reception time from the measurement terminal based on the measurement packet received by the measurement terminal;
A second step of extracting, for the two paths, a set of packet pairs in which at least part of the transfer time between the transmission time and the reception time overlaps;
A third step of calculating a delay time of each packet from the transmission time and the reception time of the measurement information for the extracted packet pair;
A fourth step of calculating a delay variation time from a plurality of the delay times in a predetermined period for each path;
A fifth step of deriving a minimum warping path that minimizes the warping cost from the extracted set of packet pairs;
A sixth step of calculating a dissimilarity between two paths in the minimum warping path;
A congestion path specifying method comprising: a seventh step of specifying a set of non-congested paths and a set of congestion paths by clustering the dissimilarities. For the fourth step,
For each path, a minimum delay time is derived among packet delays of a plurality of measurement information in a predetermined period.
The congestion path identification method according to claim 1, wherein a difference between the delay time and the minimum delay time is calculated as a delay variation time for each measurement information.   The fourth step according to claim 2, wherein if the maximum value of the difference between the delay time and the minimum delay time is equal to or less than a predetermined threshold, the path is specified as a non-congested path. Congestion path identification method.   For the seventh step, for each packet pair of the two paths, calculate the ratio of the difference between the squares of the delay variation time and the average value thereof, and calculate the two low dissimilarities calculated by the sum of the ratios. The congestion path identification method according to claim 1, wherein a pair of paths is derived. For the seventh step,
The dendrogram is created by applying the Ward method in order from the low-similarity pair of the two paths,
The congestion path identification method according to claim 4, wherein paths are classified according to the degree of dissimilarity of the dendrogram. In a management device that classifies a congestion path based on a delay variation time in a path between a plurality of measurement terminals,
Measurement information collection means for receiving measurement information including a transmission source address, a reception terminal address, a transmission time and a reception time from the measurement terminal based on the measurement packet received by the measurement terminal;
Measurement information extraction means for extracting a set of packet pairs in which at least part of the transfer time between the transmission time and the reception time overlaps for the two paths;
Delay time calculation means for calculating the delay time of each packet from the transmission time and the reception time of the measurement information for the extracted packet pair;
Delay variation calculating means for calculating a delay variation time from a plurality of delay times in a predetermined period for each path;
A minimum warping path derivation means for deriving a minimum warping path that minimizes the warping cost from the set of extracted packet pairs;
Dissimilarity calculating means for calculating dissimilarity between two paths in the minimum warping path;
A management apparatus comprising: a congestion path specifying unit that specifies a set of non-congested paths and a set of congestion paths by clustering. For each path, it further comprises a minimum delay time deriving means for deriving a minimum delay time among packet delays of a plurality of measurement information in a predetermined period,
The management apparatus according to claim 6, wherein the delay variation calculating unit calculates, for each measurement information, a difference between the delay time and the minimum delay time as a delay variation time.   When the maximum value of the difference between the delay time output from the delay variation calculation unit and the minimum delay time is equal to or less than a predetermined threshold, the device further includes a non-congestion path filter unit that identifies the path as a non-congestion path. The management apparatus according to claim 7.   The congestion path specifying means calculates the ratio of the difference between the squares of the delay variation time and the average value for each packet pair of the two paths, and has a low dissimilarity 2 calculated by the sum of the ratios. The management apparatus according to claim 6, wherein a pair of paths is derived. The congestion path specifying means includes:
A dendrogram creating means for creating a dendrogram by applying the Ward method in order from a pair of low dissimilarities of the two paths;
The management apparatus according to claim 9, further comprising: a path classification unit that classifies paths according to the degree of dissimilarity of the dendrogram. Based on the delay variation time in the path between a plurality of measurement terminals, in a program that causes a computer mounted on a management device to classify a congestion path,
Measurement information collection means for receiving measurement information including a transmission source address, a reception terminal address, a transmission time and a reception time from the measurement terminal based on the measurement packet received by the measurement terminal;
Measurement information extraction means for extracting a set of packet pairs in which at least part of the transfer time between the transmission time and the reception time overlaps for the two paths;
Delay time calculation means for calculating the delay time of each packet from the transmission time and the reception time of the measurement information for the extracted packet pair;
Delay variation calculating means for calculating a delay variation time from a plurality of delay times in a predetermined period for each path;
A minimum warping path derivation means for deriving a minimum warping path that minimizes the warping cost from the set of extracted packet pairs;
Dissimilarity calculating means for calculating dissimilarity between two paths in the minimum warping path;
A program for a management apparatus, which causes a computer to function as a congestion path specifying means for specifying a set of non-congested paths and a set of congestion paths by clustering. For each path, it further comprises a minimum delay time deriving means for deriving a minimum delay time among packet delays of a plurality of measurement information in a predetermined period,
The management apparatus according to claim 9, wherein the delay variation calculating unit causes the computer to function as a delay variation time by calculating a difference between the delay time and the minimum delay time for each measurement information. Program.   When the maximum value of the difference between the delay time output from the delay variation calculation unit and the minimum delay time is equal to or less than a predetermined threshold, the device further includes a non-congestion path filter unit that identifies the path as a non-congestion path. The program for the management apparatus according to claim 12, wherein the computer functions as described above.   The congestion path specifying means calculates the ratio of the difference between the squares of the delay variation time and the average value for each packet pair of the two paths, and has a low dissimilarity 2 calculated by the sum of the ratios. The program for a management apparatus according to any one of claims 11 to 13, wherein the computer functions to derive a pair of paths. The congestion path specifying means includes:
A dendrogram creating means for creating a dendrogram by applying the Ward method in order from a pair of low dissimilarities of the two paths;
15. The program for a management apparatus according to claim 14, wherein the computer functions as path classification means for classifying paths in accordance with the degree of dissimilarity of the dendrogram.

Images