JP4449665B2 - Method, program, server, and system for estimating congestion interval in network - Google Patents

Description

  The present invention relates to a method, program, server, and system for estimating a congestion interval in a network. In particular, it relates to networks in which the path topology changes dynamically or is unknown.

  In order to estimate the congestion interval in a network where the path topology changes dynamically or is unknown, it is necessary to measure quality data such as packet loss rate or delay by active measurement for a plurality of paths. A “path” refers to a path between terminals communicating via a measurement target network. There are a plurality of relay nodes such as routers on the path. “Active measurement” means that a test packet is transmitted from one terminal to the other terminal via the network, and the path quality is measured from the packet loss rate and / or delay of the test packet. Normally, in active measurement, a terminal that transmits a test packet is referred to as a source, and a terminal that receives a test packet is referred to as a destination.

  As a conventional congestion interval estimation method, there is a method of measuring a packet loss rate from a single terminal to a plurality of terminals, that is, a single source / multi-destination measurement method (see, for example, Non-Patent Document 1). This method is estimated for a path topology having a tree structure.

  There is also a method of measuring a packet loss rate from an arbitrary terminal to an arbitrary terminal, that is, a multi-source / multi-destination measurement method (see Non-Patent Document 2, for example). This method can be applied to any path topology.

  Further, there is a method of measuring a RTT (Round Trip Time) to each router in a single path and estimating a link that becomes a bottleneck based on the difference (for example, see Non-Patent Document 3).

Nick Duffield, “Simple Network Performance Tomography” Proc. ACM SIGCOM Internet Measurement Conference, October 2003 M. Tsuru, T. Takine, Y. Oie “Inferring Link Characteristics from End-to-End Path Measurements”, Proc. Of IEEICC 2001, July 2001 A. Akella, S. Seshan, A. Shaikh, “An Empirical Evaluation of Wide-Area Internet Bottlenecks” Proc. Of ACM Internet Measurement Conference 2003 (IMC 2003), October 2003

  However, the single-source / multi-destination measurement method has a problem that when the source terminal is close to the congestion interval, the quality of a large number of paths deteriorates at the same time, and a large number of congestion intervals are estimated. In contrast, the multi-source / multi-destination measurement method does not cause such a problem, but it assumes that the path topology is already known and is difficult to apply when the path topology changes dynamically. . In addition, the RTT measurement method has a problem that a test packet of several Mbps is transmitted for several tens of seconds to several minutes in one measurement, and a large load is applied to the network. In particular, when some of a plurality of paths go through the same relay node, there is also a problem that it cannot be measured simultaneously. Furthermore, according to the conventional measurement method, the quality correlation between paths is not taken into consideration, and all of the poor quality sections are estimated as the congestion sections.

  Therefore, an object of the present invention is to provide a method, a program, a server, and a system for estimating a congestion interval of a network whose path topology changes dynamically or is not known without imposing a great load on the network. And

According to the method of the present invention,
A first step of collecting quality data of the path that is actively measured between terminals and a list of one or more relay nodes on the path for the entire network;
Configure a table having a first axis in which paths for each terminal are arranged and a second axis in which sections divided by one or more relay nodes on the path are arranged, and sections on the path A second step of inputting quality data into an element corresponding to
A third step of designating any one of the paths arranged on the first axis of the table as a target path;
A fourth step of designating, as a target section, one or more sections that are inferior quality with respect to the target path and all of the paths including the section exhibit inferior quality;
A fifth step of designating one or more paths other than the target path and including one or more target sections including deterioration quality data as test paths;
A sixth step of deriving a degree of correlation with respect to the target path from the difference between the quality data of the test path and the quality data of the target path for each test path;
A seventh step of selecting a highly correlated test path determined to have a high degree of correlation according to a predetermined condition;
An eighth step of calculating the number of highly correlated test paths for each target section and determining that there is congestion in the section having the largest number;
A path other than the already specified target path and highly correlated test path is specified as a target path, and the fourth to eighth steps are repeated.

  According to another embodiment of the method of the present invention, for the seventh step, the predetermined condition is that a difference between the past quality data of the target path and the past quality data of the test path is within a predetermined threshold. In addition, when the difference between the latest quality data of the target path and the latest quality data of the test path is within a predetermined threshold, it is preferable that the degree of correlation is determined to be high.

  Furthermore, according to another embodiment of the method of the present invention, it is also preferable that the quality data is a packet loss rate, and it is determined that the quality data indicates a degraded quality when the packet loss rate is a predetermined value or more.

  Furthermore, according to another embodiment of the method of the present invention, it is also preferred that the table elements are input with quality points determined by one or more predetermined quality judgment thresholds for the quality data.

According to the program of the present invention,
A first step of collecting quality data of the path that is actively measured between terminals and a list of one or more relay nodes on the path for the entire network;
Configure a table having a first axis in which paths for each terminal are arranged, and a second axis in which sections divided by one or more relay nodes on the path are arranged, and sections on the path A second step of inputting quality data into an element corresponding to
A third step of designating any one of the paths arranged on the first axis of the table as a target path;
A fourth step of designating, as a target section, one or more sections that are inferior quality with respect to the target path and all of the paths including the section exhibit inferior quality;
A fifth step of designating one or more paths other than the target path and including one or more target sections including deterioration quality data as test paths;
A sixth step of deriving a degree of correlation with respect to the target path from the difference between the quality data of the test path and the quality data of the target path for each test path;
A seventh step of selecting a highly correlated test path determined to have a high degree of correlation according to a predetermined condition;
An eighth step of calculating the number of highly correlated test paths for each target section and determining that there is congestion in the section having the largest number;
A path other than the already specified target path and highly correlated test path is specified as a target path, and the computer is executed to repeat the fourth to eighth steps.

  According to another embodiment of the program of the present invention, for the seventh step, the predetermined condition is that the difference between the past quality data of the target path and the past quality data of the test path is within a predetermined threshold. In addition, it is also preferable to execute so that the degree of correlation is determined to be high when the difference between the latest quality data of the target path and the latest quality data of the test path is within a predetermined threshold.

  Further, according to another embodiment of the program of the present invention, the quality data is a packet loss rate, and is executed so as to be judged to indicate a degraded quality when the packet loss rate is a predetermined value or more. Is also preferable.

  Furthermore, according to another embodiment of the program of the present invention, the table elements are executed so that the quality points determined by one or more predetermined quality judgment thresholds are input to the quality data. It is also preferable.

According to the measurement server of the present invention,
Data collection means for receiving quality data in a path between terminals and a list of relay nodes on the path from the terminal;
Storage means for storing quality data and a relay node list;
A congestion interval estimation means for estimating a congestion interval in the network based on the quality data and the relay node list,
The congestion interval estimation means is:
For the entire network, collect quality data of the path that is actively measured between terminals and a list of one or more relay nodes on the path,
Configure a table having a first axis in which paths for each terminal are arranged and a second axis in which sections divided by one or more relay nodes on the path are arranged, and sections on the path Enter quality data in the element corresponding to
Specify one of the paths arranged on the first axis of the table as the target path,
One or more sections that are inferior quality with respect to the target path and all of the paths including the section exhibit inferior quality are designated as target sections,
One or more paths that are other than the target path and that include deterioration quality data in one or more target sections are designated as test paths,
For each test path, the degree of correlation with the target path is derived from the difference between the quality data of the test path and the quality data of the target path.
Select a highly correlated test path that has been determined to have a high degree of correlation by a given condition,
Calculate the number of highly correlated test paths for each target section, determine that there is congestion in the section with the largest number,
A path other than the already specified target path and highly correlated test path is specified as a target path, and the fourth to eighth steps are repeated.

  According to another embodiment of the measurement server of the present invention, the predetermined condition is that the difference between the past quality data of the target path and the past quality data of the test path is within a predetermined threshold and the latest of the target path It is also preferable to determine that the degree of correlation is high when the difference between the quality data of the test and the latest quality data of the test path is within a predetermined threshold.

  According to another embodiment of the measurement server of the present invention, it is also preferable that the quality data is a packet loss rate, and it is determined that the degradation data is indicated when the packet loss rate is a predetermined value or more.

  Furthermore, according to another embodiment of the measurement server of the present invention, it is also preferable that a quality point determined by one or more predetermined quality determination thresholds for quality data is input to the table element.

According to the measurement system of the present invention, the measurement system includes a network to be measured, a plurality of terminals connected to the network, and the measurement server described above.
The terminal
An active measuring means for actively measuring quality data in a path with a partner terminal at predetermined intervals;
Relay node list acquisition means for acquiring a relay node list on the path for each predetermined period;
Data transmission means for transmitting the quality data and the relay node list to the measurement server.

  According to the present invention, it is possible to estimate a congestion interval of a network whose path topology changes dynamically or is not known without imposing a great load on the network. In particular, according to the present invention, since the correlation of the quality between paths based on time variation is taken into account, the congestion interval estimated as a result is reduced, and the accuracy for congestion interval estimation is improved.

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

  FIG. 1 is a system configuration diagram according to the present invention.

  According to FIG. 1, a plurality of terminals 1 and a measurement server 5 are connected to a network 2 to be measured. The network 2 includes a plurality of relay nodes 3 for packet path control. In a network, there is a path merging or branching such that a plurality of paths between a plurality of terminals go through the same relay node for a certain section, and a part of the path delimited by the merging or branching of these paths Is referred to as a “section”.

  FIG. 2 is an explanatory diagram showing that the path is divided into sections.

According to FIG. 2, the path 41 from the source terminal 11 to the destination terminal 12 is configured via the relay nodes 31 to 35. Similarly, the path 42 from the terminal 13 to the terminal 14 is configured via the relay nodes 36, 32, 33 and 37. Here, when viewed from the path 41, since the path 42 joins at the relay node 32 and branches at the relay node 33, the section is divided as follows.
(Section 1) From the terminal 11 to the relay node 31 (Section 2) From the relay node 32 to the relay node 33 (Section 3) From the relay node 34 to the measuring terminal 12 Similarly, the path 42 is also in the sections 4, 2 and 5 It is divided into

  The terminal 1 includes a storage unit 101, an active measurement unit 102, a relay node list acquisition unit 103, and a data transmission unit 104.

  The active measurement unit 102 performs active measurement with the counterpart terminal at predetermined intervals, and acquires quality data. The active measurement data includes a transmission / reception set representing a set of the IP address of the source terminal and the IP address of the destination terminal, a measurement time (tm_o), and quality data such as a packet loss rate. Here, only the packet loss rate is used as the quality data, but other quality data such as a delay may be included.

Table 1 shows the measured active measurement data.

  The relay node list acquisition unit 103 collects relay node identification information such as an address along with the arrangement order in all relay nodes existing on the path to the partner terminal at predetermined intervals. The data includes a transmission / reception group, a time (tr_o) when the relay node list is acquired, and a relay node list in which relay nodes on the path are arranged in order. This relay node list data is stored in the storage unit 101 and transmitted to the measurement server 5 using the data transmission unit 104. For example, the relay node list data is acquired using a “traceroute” command or the like using a TTL (Time to Live) field of the IP packet.

Table 2 is a measured relay node list.

  The storage unit 101 stores an address of a measurement partner terminal, a period for performing active measurement, a period for performing relay node list acquisition, relay node list data, and active measurement data.

  The data transmission unit 104 transmits the active measurement data and the relay node list to the measurement server 5.

  Next, the measurement server 5 includes a data collection unit 501, a congestion interval estimation unit 502, and a storage unit 503.

  The data collection unit 501 receives active measurement data and relay node list data from each measurement terminal. A method based on polling from the measurement server 5 may be used, or a method in which each measurement terminal transmits autonomously may be used.

  The storage unit 503 holds various tables to be described later in addition to the address of the measurement terminal 1 that is a data collection target. Information such as a quality judgment threshold, a mapping table update cycle, and the previous mapping table update time is also held. The mapping table update cycle is desirably set to be the same as the measurement cycle at each measurement terminal in order to reflect the measurement result of each measurement terminal in the mapping table as soon as possible.

  The congestion interval estimation unit 502 estimates the congestion interval in the measurement target network using the table of the storage unit 503.

  FIG. 3 is a flowchart of the congestion interval estimation unit 502 in the present invention. Below, it demonstrates based on the sequence number of a flowchart.

(S301) First, for the entire network, the quality data of the path that is actively measured between terminals and a list of one or more relay nodes on the path are collected.

Table 3 is an active measurement table received from each terminal.

Table 4 is a relay node list table received from each terminal.

(S302) Next, mapping table creation update processing is performed. Here, it is necessary to create various tables in advance.

Table 5 is a section table. The section table represents a section ID associated with a section including one or more relay nodes on the path by branching or joining of the paths in the measurement target network, and a relay node list on the section.

Table 6 is a path table.

  The path table includes, as columns, a path ID, a relay node list, a transmission / reception group, a stability, a time (tr_d), a section list, a past loss rate, a latest loss rate, a quality point, a time ( tm_d). The path ID is associated with each transmission / reception set composed of the IP address of the transmission side terminal and the IP address of the reception side terminal, and is specified every time a new transmission / reception set is added. The time (tr_d) is referenced from the active measurement table. The degree of stability is “0” for a newly created path or a path whose transit node has been changed within a predetermined period, and “1” for a path that has not changed since the predetermined period. ”And is given to estimate the section only for paths where the relay node is stable.

The section list represents one or more section IDs existing on the path, and is associated with the section ID of the section table. The past loss rate and the latest loss rate are packet loss rates with time variations, and are used to derive the degree of path correlation. The quality point is a value obtained by determining the latest loss rate based on a quality determination threshold stored in advance. According to Table 6, the packet loss rate is 1% as the first quality determination threshold, and the packet loss rate is 2% as the second quality determination threshold. The time (tm_d) is referenced from the relay node list table.
Quality point 0: When the latest loss rate is less than 1% Quality point 1: When the latest loss rate is 1% or more and less than 2% Quality point 2: When the latest loss rate is 2% or more

The mapping table creation / updating process constitutes a mapping table as shown in Table 7.

  The mapping table includes a vertical axis in which paths for each terminal are arranged and a horizontal axis in which sections in the measurement target network are arranged. Quality data is input to the elements of the table. Here, a quality point using a quality determination threshold is input. The specific operation of the mapping table creation / update process will be described later.

(S303) One of the paths arranged on the vertical axis of the mapping table is designated as the target path.

Table 8 is a mapping table corresponding to S303. According to Table 8, it is assumed that the path ID 1 is first designated as the target path.

(S304) One or more sections indicating inferior quality points are selected for the target path (path ID 1). According to Table 8, sections 1, 2, 3, 4, 5, 15, 16, and 17 indicating poor quality points 2 are selected for the target path (path ID 1). Next, in a section showing poor quality points for the target path (path ID 1), a section in which all of the paths including the section show bad quality points is designated as the target section.

Table 9 is a mapping table corresponding to S304.

  According to Table 9, in the sections 1, 2, 3, 4, 5, 15, 16, and 17 indicating the poor quality point 2 for the target path (path ID 1), all of the paths including the section indicate the poor quality points. Sections 1, 2, 5, 15, and 16 are designated as target sections.

(S305) One or more paths other than the target path and including a degraded quality point in the target section are designated as a test path. According to Table 9, for the path IDs 2 to 9 other than the target path, path IDs 2, 5, 6 and 9 including degradation quality data in the target section are sequentially specified.

(S306) For each test path (path ID = 2, 5, 6, 9), the degree of correlation with the target path is derived from the difference between the quality data of the test path and the quality data of the target path. For example, the quality data is a packet loss rate, and the degree of correlation can be derived by comparing past and current packet loss rates.

  For example, as a predetermined condition, the difference between the past degradation quality data of the target path and the past degradation quality data of the test path is within a predetermined threshold, and the latest degradation quality data of the target path and the latest degradation quality of the test path When the difference from the data is within a predetermined threshold, it can be determined that the degree of correlation is high.

(S307) A highly correlated test path determined to have a high degree of correlation according to a predetermined condition is selected. In Table 9, for example, it is assumed that path IDs 2 and 5 are derived as highly correlated test paths as paths having a high degree of correlation with the target path among path IDs 2, 5, 6, and 9 that are test paths.

  FIG. 4 is a graph for explaining the degree of correlation.

  The graph of FIG. 4 is configured with the packet loss rate on the vertical axis and the time on the horizontal axis, and represents the packet loss rate associated with the time variation between the target path and the test path. Here, the latest loss rate is represented by P (tm) with respect to the latest time tm, and the past loss rate is represented with P (tm−ΔTm) with respect to the past time tm−ΔTm. For the target path and the test path, the latest loss rate difference is represented by ΔP (tm), and the past loss rate difference is represented by ΔP (tm−ΔTm). Here, if the latest loss rate difference ΔP (tm) is a predetermined threshold value Dp (for example, 0.5%) or less and the past loss rate difference ΔP (tm−ΔTm) is a predetermined threshold value Dp or less, It is judged that the correlation is high.

  FIG. 5 is a graph in which a plurality of paths are arranged as in the graph of FIG. According to FIG. 5, the correlation between paths at a predetermined time can be clearly understood.

(S308) The number of highly correlated test paths is calculated for the target section, and it is determined that there is congestion in the section with the largest number of paths. According to Table 9, the number of highly correlated test paths for the target section is as follows.
Number of highly correlated test paths for section ID1: 2
Number of highly correlated test paths for section ID2: 0
Number of highly correlated test passes for section ID 5: 1
Number of highly correlated test passes for section ID 15: 1
Number of highly correlated test paths for section ID 5: 0
Then, the section with the largest number of highly correlated test paths is the section ID1, and it is determined that the section ID1 has congestion.

  (S309) The process is repeated using a path other than the already specified target path and highly correlated test path as a target path. According to Table 9, the path ID 1 that is the target path and the path IDs 2 and 5 that are the highly correlated test paths are not designated as the next target paths.

Table 10 is a mapping table in further S304.

  According to Table 10, it is assumed that a path ID 1 that is a path other than the path ID 1 that is the target path and the path IDs 2 and 5 that are the highly correlated test paths is designated as the target path.

(S304) One or more sections indicating inferior quality points are selected for the target path (path ID 3). According to Table 10, sections 7, 10, 11, 12, 14, and 18 indicating poor quality points 2 are selected for the target path (path ID 3). Next, in the section showing the poor quality point for the target path (path ID 3), the section where all the paths including the section show the bad quality point is designated as the target section.

Table 11 is a mapping table in further S304.

  According to Table 11, in the sections 7, 10, 11, 12, 14, and 18 indicating the poor quality point 2 for the target path (path ID 3), the sections 10 and 11 in which all of the paths including the section indicate the poor quality points. And 12 are designated as target intervals.

(S305) One or more paths other than the target path and including a degraded quality point in the target section are designated as a test path. According to Table 9, for the path IDs 1, 2, 4 to 9 other than the path ID 3 that is the target path, path IDs 6 and 9 including degradation quality data in the target section are sequentially specified.
(S306) For each test path (path ID = 6, 9), the degree of correlation with the target path is derived from the difference between the quality data of the test path and the quality data of the target path.
(S307) As described above, a highly correlated test path determined to have a high degree of correlation according to a predetermined condition is selected. In Table 11, for example, it is assumed that both path IDs 6 and 9 serving as test paths are derived as highly correlated test paths having a high degree of correlation with the target path.

(S308) The number of highly correlated test paths is calculated for the target section, and it is determined that there is congestion in the section with the largest number of paths. According to Table 11, the number of highly correlated test paths for the target section is as follows.
Number of highly correlated test paths for section ID 10: 1
Number of highly correlated test paths for section ID 11: 2
Number of highly correlated test paths for section ID 12: 2
Then, the sections with the largest number of highly correlated test paths are the section IDs 11 and 12, and it is determined that the section IDs 11 and 12 have congestion.

Table 12 is a mapping table in S308.

(S309) Further, the process is repeated using a path other than the already specified target path and highly correlated test path as a target path. According to Table 12, the path IDs 1 and 3 that are target paths and the path IDs 2, 5, 6, and 9 that are highly correlated test paths are not designated as the next target paths. For example, path IDs 4, 7, and 8 are selected as candidates for the next target path. However, since the quality points indicating the degradation quality data are not input to the path IDs 4, 7, and 8, the processing for detecting the congestion section is ended.

  Finally, the mapping table creation / update process will be described. This process is exactly the same as the method described in Japanese Patent Application No. 2004-088888 by the same applicant.

  FIG. 6 is a flowchart showing the mapping table creation update process (S302) of FIG. Hereinafter, each row of the table is referred to as a record, and each column is referred to as a field.

(S601) The record of the active measurement table is the process target record. If there are unprocessed records, the processing up to S607 is repeated for each processing target record.
(S602) Referring to the path table, it is checked whether a record having the same transmission / reception set as the transmission / reception set of the processing target record exists in the path table. If it does not exist, it means that a new path has been created, and the process proceeds to section creation processing (S603). If it exists, a path table record having the same transmission / reception set is extracted, and the process proceeds to S604.
(S604) The time (tm_o) of the processing target record is compared with the time (tr_d) of the extracted path table record. If tm_o is greater than or equal to tr_d, that is, if the processing target record is newer than the path table record, the process proceeds to section creation processing (S603) in order to reflect the data of the relay node list table in the path table.
(S605) The quality field of the path table is updated. The quality field update sets a quality point derived from the packet loss rate of the processing target record. At this time, the time (tm_o) of the processing target record is set to the time (tm_d) of the path table record.
(S606) The previous mapping table update time is compared with the current time, and if the difference is equal to or greater than the mapping table update cycle, the process proceeds to the mapping table update process (S607).
(S609) S602 to S607 are repeated until all unprocessed records are processed.

  FIG. 7 is a flowchart showing the section creation processing (S603) of FIG.

(S701) A record in the relay node list table having the same transmission / reception set as the transmission / reception set of the processing target record in the section creation processing of FIG. It is checked whether or not a record having the same transmission / reception group as the transmission / reception group of the processing target record exists in the path table. If it does not exist, it is a new record, and the process proceeds to S702. When it exists, it transfers to S703.
(S702) The process target record is added as a new record in the path table. A path ID value that does not overlap with other records is assigned to the path ID of the new record. The stability of the new record is 0. Further, the newly assigned path ID value is added to the changed path list.
(S703) A path table record having the same transmission / reception set as the transmission / reception set of the processing target record is extracted. Next, it is checked whether or not the relay node list of the processing target record completely matches the relay node list of the extracted path table record. If they match completely, the existing path is unchanged and the stability of the extracted path table record is set to 1, and the time (tr_o) of the processing target record is set as the time (tr_d). (S705). If they do not match completely, the relay node on the path has been changed, and the process proceeds to S704.
(S704) The path ID of the extracted path table record is added to the changed path list. Next, referring to the relay node table, the path ID passing through each relay node in the relay node list field of the extracted path table record is added to the changed path list. Thereafter, the relay node list and time of the extracted path table record are updated to the corresponding field values of the processing target record. Further, 0 is set to the stability of the extracted path table record.
(S706) The record of the path table added in S702 or the record of the path table changed in S704 is the processing target record. Check whether the relay node in the relay node list field of the record to be processed exists in the relay node table. If it exists, the path ID value passing through the relay node from the relay node table is added to the changed path list. If it does not exist, the relay node is added to the relay node table as a new record. The path ID of the processing target record is set as the path ID of the added relay node table record.

(S707) Each path in the changed path list is a processing target. If there is no unprocessed path, the process ends.
(S708) If there is an unprocessed path, a process target path is selected.
(S709) The relay node list on the processing target path is extracted from the relay node list field of the path table. Next, a path ID passing through each relay node in the relay node list is obtained with reference to the relay node table. The relay nodes in the relay node list are arranged in order, and it is checked whether or not the path IDs passing through the adjacent relay nodes completely match. When they completely match, it means that adjacent relay nodes belong to the same section, and when they do not match completely, it means that there is a branch or merge of paths and they belong to different sections. By these operations, the boundaries of the sections on the path can be recognized, and the path can be divided into sections. It is also possible to extract a relay node list belonging to the same section.

  The process of S709 will be described with reference to FIG. The path 41 is selected as the processing target path. In the relay node list, relay nodes 31 to 35 are extracted. The path ID passing through the relay nodes 31, 34 and 35 is only the path 41. The path IDs passing through the relay node 32 and the relay node 33 are the path 41 and the path 42. Therefore, it is possible to determine that the relay node 31-the relay node 32 and the relay node 33-the relay node 34, in which adjacent path IDs do not completely match with each other, belong to different sections. The other relay nodes are relay nodes that are adjacent to each other and have the same path ID. Therefore, it can be determined that they belong to the same section. Therefore, it can be determined that the path 41 includes three sections 1, 2, and 3, and the relay node list of each section can also be extracted.

(S710) It is checked whether the relay node list belonging to each section divided in S709 and the record having the same relay node list exist in the section table. If not, a section ID is assigned and registered as a new record in the section table. Next, the section ID on the processing target path is checked in the section table, and the section list of the corresponding path table record is updated.

  FIG. 8 is a flowchart showing the mapping table update process (S607) of FIG.

(S801) A record in the path table is a processing target. If there is an unprocessed record, one record to be processed is selected. If there are no unprocessed records, exit.
(S802) The time (tr_d) and time (tm_d) of the processing target record are checked. When the mapping table update cycle is ΔT, if tm_d−tr_d> ΔT, that is, the collection time of the relay node list of the processing target record is older than the mapping table update cycle than the quality measurement time. In this case, the process target record is not used for updating the mapping table, and the process returns to S801. By not using the record having the old relay node list for updating the mapping table, the reliability for the estimated congestion interval can be improved.
(S803) The stability of the process target record is referred to. If the stability is 0, the process target record is not used for updating the mapping table, and the process returns to S801. A record having a stability level of 0 is recognized as a new path or a changed path in the section creation process, and the reliability of the estimated congestion section can be improved by setting the stable path as a processing target. .
(S804) It is checked whether the path ID of the processing target record already exists in the mapping table record. If it does not exist, add a new record. Next, it is checked whether or not the section ID of the section list of the processing target record exists in the mapping table field. If there is a section ID that does not exist, a new field is added.

  A mapping table record having the same path ID as the path ID of the processing target record is extracted. Among the fields of the extracted mapping table record, the quality field value of the processing target record is set in the field corresponding to the section ID of the section list of the processing target record, and the values of the remaining fields are set to null values.

  According to the above-described various embodiments of the present invention, various changes, modifications, and omissions in the technical idea and scope of the present invention can be easily made by those skilled in the art. 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 system configuration diagram in the present invention. It is explanatory drawing showing that the path | pass is divided | segmented into the area. It is a flowchart in this invention. It is a graph explaining a correlation degree. 5 is a graph in which a plurality of paths are arranged as in the graph of FIG. 4. It is a flowchart showing the mapping table creation update process (S302) of FIG. It is a flowchart showing the area creation process (S603) of FIG. It is a flowchart showing the mapping table update process (S607) of FIG.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1, 11-14 Measurement terminal 101 Storage part 102 Active measurement part 103 Relay node list acquisition part 104 Data transmission part 2 Network to be measured 3, 31-37 Relay node 41, 42 Path 5 Measurement server 501 Data collection part 502 Congestion Section estimation unit 503 storage unit

Claims (13)

A method in which a measurement server identifies a congestion section in a network in which a plurality of terminals can communicate with each other,
A first step of collecting, for the entire network, quality data of the path that is actively measured between the terminals and a list of one or more relay nodes on the path;
Configuring a table having a first axis in which paths for each terminal are arranged and a second axis in which sections divided by one or more relay nodes on the path are arranged, A second step of inputting the quality data into an element corresponding to a section;
A third step of designating any one of the paths arranged on the first axis of the table as a target path;
A fourth step of designating, as a target section, one or more sections that are inferior quality with respect to the target path and all of the paths including the section exhibit inferior quality;
A fifth step of designating, as a test path, one or more paths other than the target path and including degradation quality data in one or more of the target sections;
A sixth step of deriving a degree of correlation for the target path from the difference between the quality data of the test path and the quality data of the target path for each test path;
A seventh step of selecting a highly correlated test path determined to have a high degree of correlation according to a predetermined condition;
Calculating the number of the highly correlated test paths for each target section, and determining that there is congestion in the section having the largest number;
A method, wherein a path other than an already specified target path and a highly correlated test path is specified as the target path, and the fourth to eighth steps are repeated.
  In the seventh step, the predetermined condition is that the difference between the past quality data of the target path and the past quality data of the test path is within a predetermined threshold, and the latest quality data of the target path 2. The method according to claim 1, wherein the degree of correlation is determined to be high when a difference between the first quality data and the latest quality data of the test path is within a predetermined threshold.   3. The method according to claim 1, wherein the quality data is a packet loss rate, and the quality is determined to indicate the deterioration quality when the packet loss rate is a predetermined value or more.   4. The method according to claim 3, wherein a quality point determined by one or more predetermined quality determination thresholds for the quality data is input to an element of the table. A program for identifying a congestion section in a network in which a plurality of terminals can communicate with each other,
A first step of collecting, for the entire network, quality data of the path that is actively measured between the terminals and a list of one or more relay nodes on the path;
Configuring a table having a first axis in which paths for each terminal are arranged and a second axis in which sections divided by one or more relay nodes on the path are arranged, A second step of inputting the quality data into an element corresponding to a section;
A third step of designating any one of the paths arranged on the first axis of the table as a target path;
A fourth step of designating, as a target section, one or more sections that are inferior quality with respect to the target path and all of the paths including the section exhibit inferior quality;
A fifth step of designating, as a test path, one or more paths other than the target path and including degradation quality data in one or more of the target sections;
A sixth step of deriving a degree of correlation for the target path from the difference between the quality data of the test path and the quality data of the target path for each test path;
A seventh step of selecting a highly correlated test path determined to have a high degree of correlation according to a predetermined condition;
Calculating the number of the highly correlated test paths for each target section, and determining that there is congestion in the section having the largest number;
A program that designates a path other than the already designated target path and the highly correlated test path as the target path, and causes the computer to execute the fourth to eighth steps.   In the seventh step, the predetermined condition is that the difference between the past quality data of the target path and the past quality data of the test path is within a predetermined threshold, and the latest quality data of the target path 6. The program according to claim 5, wherein the program is executed so that the degree of correlation is determined to be high when a difference between the test quality and the latest quality data of the test path is within a predetermined threshold.   The program according to claim 5 or 6, wherein the quality data is a packet loss rate, and is executed so as to be determined to indicate the deterioration quality when the packet loss rate is equal to or greater than a predetermined value. .   8. The program according to claim 7, wherein the program is executed such that a quality point determined by one or more predetermined quality determination thresholds is input to the quality data in the element of the table. A measurement server that identifies a congestion section in a network in which a plurality of terminals can communicate with each other,
Data collection means for receiving quality data in a path between terminals and a list of relay nodes on the path from the terminal;
Storage means for storing the quality data and the relay node list;
Congestion interval estimation means for estimating a congestion interval in the network based on the quality data and the relay node list,
The congestion interval estimation means includes:
For the entire network, collect quality data of the path that is actively measured between the terminals and a list of one or more relay nodes on the path;
Configuring a table having a first axis in which paths for each terminal are arranged and a second axis in which sections divided by one or more relay nodes on the path are arranged, Enter the quality data in the element corresponding to the section,
Specify any one of the paths arranged on the first axis of the table as a target path,
One or more sections showing poor quality with respect to the target path, and all of the paths including the section showing bad quality are designated as target sections,
One or more paths other than the target path and including degradation quality data in one or more target sections are designated as test paths,
For each test path, the degree of correlation with the target path is derived from the difference between the quality data of the test path and the quality data of the target path,
Select a highly correlated test path determined to have a high degree of correlation according to predetermined conditions,
Calculate the number of the highly correlated test paths for each target section, determine that there is congestion in the section with the largest number,
A measurement server that functions to specify a path other than an already specified target path and a highly correlated test path as the target path, and to repeat from the specification as the target section until it is determined that there is congestion .   The predetermined condition is that a difference between past quality data of the target path and past quality data of the test path is within a predetermined threshold, and the latest quality data of the target path and the latest quality of the test path are The measurement server according to claim 9, wherein the degree of correlation is determined to be high when a difference from quality data is within a predetermined threshold.   The measurement server according to claim 9 or 10, wherein the quality data is a packet loss rate, and is determined to indicate the deterioration quality when the packet loss rate is a predetermined value or more.   The measurement server according to claim 11, wherein a quality point determined by one or more predetermined quality determination thresholds with respect to the quality data is input to an element of the table. A measurement system comprising a network to be measured, a plurality of terminals mutually connected to the network, and the measurement server according to any one of claims 9 to 12,
The terminal
An active measuring means for actively measuring quality data in a path with a partner terminal at predetermined intervals;
Relay node list acquisition means for acquiring a relay node list on the path for each predetermined period;
A measurement system comprising: the data transmission means for transmitting the quality data and the relay node list to the measurement server.

Images