JP2007060611A - Instrumentation terminal and network congestion interval estimation system - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To permit the estimation of the place of congestion efficiently, regardless of the scale of a network. <P>SOLUTION: The instrumentation terminal is provided with a storing range, having n-bit length hash value of own identification value as an node ID (identity) and within a range that does not overlap another instrumentation terminal, under a state of not less than 0 and not more than 2<SP>n</SP>-1, while having a neighboring terminal of the instrumentation terminal provided with the node ID of a value nearest to and higher than the value obtained, by adding a predetermined number to the node ID of own terminal as the module of 2<SP>n</SP>and the list of relay node on a path to the neighbored terminal and the quality of path is measured; then the path, whose quality measurement has been conducted, is partitioned into more than one partitions specified by the relay node neighbored on the path and the n-bit length hash value of an identification value for respective partitions is calculated; and when the n-bit length hash value is within the storage range, the value is stored in the own terminal, but when the same lies out of the storage range, the result of measurement is transmitted to the n-bit length hash value as the address of the same. <P>COPYRIGHT: (C)2007,JPO&INPIT

Description

  The present invention relates to estimation of a congestion period of a network in which it is difficult to directly measure traffic.

  In order to estimate network congestion points in an environment where it is difficult to directly measure network traffic, the path quality such as delay or loss is measured by active measurement for multiple paths. A method is needed to estimate the congestion location inside the network from the results. Here, the path means a route through which the packet passes when a packet is transmitted from a terminal connected to the network to another terminal, and a plurality of relay nodes such as routers exist on the route. . Also. Active measurement means that a test packet is sent from a terminal connected to the network to another terminal, and the path quality is measured from the delay and / or loss of the test packet received by the other terminal. Say the method. A terminal that transmits a test packet in active measurement is called a source, and a terminal that receives a test packet is called a destination.

  As an estimation method of the congestion section, for example, active measurement is performed on a path between a plurality of measurement terminals connected to the network, quality is measured, and a relay node existing on the path is searched, A method for estimating a congestion interval has been proposed (see, for example, Non-Patent Document 1).

  On the other hand, Non-Patent Document 2 describes a lookup protocol using a distributed hash table that can be applied to a peer-to-peer (P2P) type file sharing system or the like.

FIG. 6 is a diagram illustrating the configuration described in Non-Patent Document 2. In FIG. 6, a solid circle represents an actual communication node and its node ID. Here, the node ID is an n-bit hash value (n is a natural number of 2 or more) obtained by converting the IP address of the communication node by a hash function such as SHA-1, and n = 6 in FIG. In addition, it is assumed that there is no communication node having a node ID other than a circle indicated by a solid line. Also, all of the operations described below, modulo ^{2 n,} i.e., performed on mod ^{2 n.}

  When the protocol of Non-Patent Document 2 is applied to a file sharing system, for example, the file is larger than the n-bit hash value by the hash function of the file name, and the value closest to the n-bit hash value of the file name Is stored in a communication node having a node ID as a node ID. In FIG. 6, a file whose file name has an n-bit length hash value of 25 to 34 is stored in a communication node having a node ID = 35.

Each communication node is equal to or more than the value obtained by adding 2 ^m (m = 0, 1,..., N−1) to its own node ID, and the value closest to the value is set as the node ID. The communication node to be used is an adjacent node, and holds information necessary for communicating with the adjacent node, for example, an IP address. A table of adjacent nodes held by each communication node is referred to as a Finger Table. As shown in FIG. 6, the adjacent nodes of the communication node with the node ID = 35 are a total of five communication nodes with node IDs = 37, 42, 48, 56 and 8. In general, when the actual number of communication nodes is N, the expected value of the size of the Finger Table is log2N.

  When acquiring a desired file, the communication node obtains a hash value from the file name, and uses the obtained hash value as a destination, and the file is stored in an adjacent node having a node ID that is equal to or less than the obtained hash value. Send an acquisition request. The communication node that has received the file acquisition request determines whether or not the storage destination communication node of the requested file is itself. If it is not, the communication node of the transfer destination is determined and determined in the same manner. The file acquisition request is transferred to the communication node, and finally, the file acquisition request is transferred to the communication node that stores the requested file.

Tachibana, Ano, Hasegawa, Tsuru, Oie, “Congestion segment estimation method based on active measurement on multiple paths”, IEICE Tech. 104 no. 309 CQ2004-76, pp. 43-48, September 2004 I. Stocia, R.A. Morris, D.M. Karger, M.M. F. Kaashhoek, H.C. Balakrishnan, “Cord: A Scalable Peer-to-peer Lookup Service for Internet Applications”, ACM SIGCOMM 2001, 2001.

  Consider a case in which the method described in Non-Patent Document 1 is executed by a large number of measurement terminals, for example, 10,000 measurement terminals, in order to measure or estimate a congestion point of a large-scale network. In order to make it possible to measure or estimate a congestion point in a large-scale network, it is necessary to determine measurement partners dispersed on the network as much as possible. Furthermore, although Non-Patent Document 1 does not describe how to collect measurement results and which apparatus performs estimation processing, for example, measurement results measured by a large number of measurement terminals are stored in one server. When it is configured to accumulate and perform estimation processing, as the number of measurement terminals increases, the amount of accumulated data becomes enormous, making it difficult to instantly refer to measurement results necessary to identify congestion points. The problem arises.

  Therefore, the present invention does not require a server device that collectively stores and processes measurement results measured by each measurement terminal, regardless of the scale of the network, and makes it possible to efficiently estimate a congestion location. An object is to provide a terminal and a system.

According to the measuring terminal according to the present invention,
The n-bit-length hash value of the value which can identify the terminal and the node ID, with 0 or 2 ⁿ -1 or less, and the other measurement terminal a measurement terminal having a storage range in the range of distinct values, 2 ⁿ , The measurement terminal having a node ID of a value that is equal to or more than a value obtained by adding a predetermined number to the node ID of the terminal and that is closest to the value obtained by adding the predetermined number is defined as an adjacent terminal. A determining unit that determines one or more adjacent terminals based on a predetermined number; an acquiring unit that acquires a list of relay nodes on a path with the adjacent terminal; a measuring unit that measures the quality of a path with the adjacent terminal; Path dividing means for dividing a path for which quality measurement has been performed with a terminal into one or more sections identified by adjacent relay nodes on the path and calculating an n-bit length hash value of a value for identifying each section; , Storage means for storing measurement results and quality For each section of the measured path, the n-bit length hash value calculated by the path dividing unit is stored in the storage unit if it is within the storage range, and the measurement result is stored if it is outside the storage range. And transmitting means for transmitting the n-bit hash value as a destination.

According to another embodiment of the measuring terminal according to the present invention,
When the measurement result is transmitted, the transmission unit transmits the measurement result to an adjacent terminal determined from the n-bit hash value as the destination, and the measurement result transfer unit transmits the destination of the received measurement result. When the value is within the storage range of the terminal itself, the received measurement result is stored in the storage unit, and when the value is outside the storage range, it is also preferably transferred to the adjacent terminal determined from the destination value.

According to another embodiment of the measurement terminal according to the present invention,
When the path for which congestion estimation is performed is divided into sections, and the n-bit length hash value of the value for identifying the section is outside the storage range of the own terminal, the measurement result request is sent to the n-bit length hash value. As a destination, it is transmitted to the adjacent terminal determined from the n-bit length hash value, and when it is within the storage range, a result acquisition means for reading the measurement result from the storage means of the own terminal, and the destination of the received measurement result request If the value is within the storage range of the terminal itself, the measurement result stored in the storage means is transmitted to the measurement terminal that is the source of the measurement result request, and if it is outside the storage range, it is determined from the destination value. Measurement result request transfer means for transferring to the adjacent terminal, and congestion interval estimation means for estimating the congestion interval based on the measurement results of other paths including at least one interval among the intervals of the path for which the congestion estimation is performed And having And it is also preferred.

Furthermore, according to another embodiment of the measuring terminal according to the present invention,
It is also preferable that the measuring unit performs quality measurement with the adjacent terminal based on a measurement result transmitted from the transmitting unit to the adjacent terminal.

Furthermore, according to another embodiment of the measuring terminal according to the present invention,
For a section constituting a path with each adjacent terminal, the number of paths that pass through the section is searched, and a path evaluation value calculating unit that calculates a path evaluation value based on the number of paths that pass through the section is provided. It is also preferable to measure the path only with an adjacent terminal within the upper limit value, having an upper limit value, based on the evaluation value of the path.

Furthermore, according to another embodiment of the measuring terminal according to the present invention,
It is also preferable that the measurement unit has an upper limit value and performs path measurement only with the adjacent terminals within the upper limit value in the descending order of the data amount of the measurement result transmitted from the transmission unit and the measurement result transfer unit to the adjacent terminal.

Furthermore, according to another embodiment of the measuring terminal according to the present invention,
The storage range is modulo 2 ⁿ and is smaller than the node ID of the own terminal among the node IDs of other existing measurement terminals, and is larger than the node ID of the own terminal from the closest node ID, and It is also preferable to be within the range up to the nearest node ID.

Furthermore, according to another embodiment of the measuring terminal according to the present invention,
Wherein the predetermined number, modulo ^{2 n,} it is also preferred 2 m + k is (are m 0 or n-1 an integer) (k is 0 or ² n -1 an integer).

According to the system according to the invention,
It comprises a network and a plurality of the measurement terminals connected to the network.

  A value that can identify a terminal is converted into an n-bit hash value by a hash function to obtain a node ID, and a measurement partner of each measurement terminal is obtained as a value obtained by adding a predetermined number to the node ID. Even in the case where there are measurement partners, it is possible to select the measurement partners dispersed without any bias. In addition, an n-bit length hash value of each section of the path for which quality measurement has been performed is obtained, and the measurement result is distributed to measurement terminals corresponding to the n-bit length hash value of the section, that is, the measurement result is managed by a distributed hash table. Thus, the measurement results can be managed without requiring a server device that collectively stores the measurement results, and the measurement results necessary for estimating the congestion point can be referred to efficiently regardless of the number of measurement terminals.

  The measurement result is transmitted by transmitting and / or transferring to the adjacent terminal, not directly to the measurement terminal of the storage destination. As a result, the measurement terminal stores only information necessary for communication with the adjacent terminal to form a distributed hash table, and further performs quality measurement with the adjacent terminal using transmission of the measurement result to the adjacent terminal. be able to. This can reduce the load on the network for quality measurement.

  By setting the upper limit value of the path to be measured and setting the path to be measured based on the number of paths passing through the sections constituting the path and the data amount of the measurement result transmitted by the transmission means and the measurement result transfer means within the upper limit value, It is possible to reduce the load on the network by measuring and transmitting the measurement result.

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

  FIG. 1 is a configuration diagram of a congestion location estimation system according to the present invention. According to FIG. 1, a plurality of measuring terminals 1 are connected to the network 2. A plurality of relay nodes 21 such as routers exist inside the network 2.

The measuring terminal uses an n-bit hash value obtained by converting a value uniquely identifying the measuring terminal, such as an IP address or name assigned to itself, using a hash function such as SHA-1 as a node ID, and 2 ⁿ as a modulus. Then, a measurement terminal having a node ID that is equal to or more than a value obtained by adding a predetermined number to its own node ID and having a value closest to the value obtained by adding the predetermined number is determined as a measurement partner. Predetermined number, as one or more, ^{e.g., 2 m 2 (m = 0,1} , ···, n-1) or ^{2 m (m = 0,1, ···} , n-1) to ⁿ - An arbitrary value of 1 or less can be added. Note that n is selected so that 2 ⁿ is equal to or greater than the number of measurement terminals to be arranged. As a result, even when the number of measurement terminals is large, n or less measurement partners can be selected without deviation from the network. Hereinafter, a measurement terminal that is a measurement partner is referred to as an adjacent terminal.

  FIG. 2 is a process flow diagram in each measurement terminal. The measurement terminal selects one path for measurement from the plurality of paths between the adjacent terminals (S21). The investigation of the relay node list existing on the measurement path is not performed every time active measurement is performed because the load on the network is large (S22). When investigating the relay node list, for example, a list of relay nodes existing on the measurement path is acquired by using a “Tracroute” command using a TTL (Time To Live) field of the IP packet (S23). Subsequently, active measurement is performed, and for example, the measurement result shown in FIG. In FIG. 3A, the alphabet of the measurement path represents a relay node existing on the path, that is, a relay node list of the measurement path.

  Subsequently, a measurement terminal as a storage destination of the obtained measurement result is obtained, and the measurement result is transmitted to the obtained measurement terminal (S25). FIG. 3B is a diagram illustrating a measurement destination storage terminal of the measurement result of FIG. Here, it is assumed that measurement terminals having node IDs indicated by solid circles in FIG. 6 are arranged. The measurement terminal divides a measurement path, that is, a relay node A-B-C-D-F, which is a list of relay nodes, into sections. Here, the section refers to a part of a path specified by adjacent relay nodes. Subsequently, a value for specifying the section by a method common to the system is given to the section. For example, when the IP address of the relay node A is 10.0.0.1 and the IP address of the relay node B is 192.168.0.1, as a method of assigning a value that identifies the section, the relay node A The section in the B direction from the relay node B is set to 10.0.0.1.192.168.0.1, and the section in the A direction from the relay node B is set to 192.168.0.1.10.0.0.0.1. There are methods. Subsequently, an n-bit long hash value of a value specifying the section is obtained. In FIG. 3 (b), the n-bit length hash values of the values specifying section A: B, section B: C, section C: D, section D: E, and section E: F are 6, 43, 24, 51 and 18.

Since a measurement terminal that uses the obtained n-bit length hash value as a node ID does not always exist, a measurement terminal that stores a measurement result is obtained based on the obtained n-bit length hash value. In the example of FIG. 3 (b), ²ⁿ is used as a modulus and stored in a measurement terminal having a node ID that is larger than the obtained n-bit length hash value and closest to the obtained n-bit length hash value. ing. That is, corresponding to the n-bit length hash values 6, 43, 24, 51, and 18 that specify the section, the measurement terminals having the node IDs of 8, 48, 25, 56, and 19 are connected to the measurement terminal shown in FIG. The measurement results shown in a) are stored. When measuring a path having k relay nodes, k-1 measurement terminals serve as storage destination measurement terminals, and these k-1 storage destination measurement terminals store the same measurement result.

In addition, the measuring terminal recognizes a measuring terminal having a node ID of the closest value that is smaller than the node ID of the own terminal and modulo 2 ⁿ , and the measuring terminal that should store the measurement result is itself If there is not, the n-bit length hash value of the value specifying the section is sent to the adjacent terminal of the closest value below the destination node ID. The adjacent terminal that has received the measurement result determines whether it is a measurement result that should be stored from the node ID indicated in the destination. Further transfer to the adjacent terminal.

  As described above, the measurement terminal has a range of values in which the device itself should store the result, and if the n-bit length hash value of the path section is within this range, stores the measurement result, If it is outside, it is transmitted or transferred to the adjacent terminal. The range of values for storing the measurement result is the range from the node ID of the nearest existing measurement terminal that is smaller than the range, that is, the node ID of the own terminal, as long as there is no overlapping range at each measurement terminal. It may be outside the range up to a number smaller by 1 than the node ID of the terminal. For example, a range from a value smaller than the node ID of the own terminal and one greater than the node ID of the nearest existing measurement terminal to the node ID of the own terminal, or from the node ID of the own terminal, the node ID of the own terminal It may be a range up to a value that is larger and one smaller than the node ID of the closest existing measurement terminal. However, in order to ensure that there is no overlapping range in each measurement terminal, this range is smaller than the node ID of the own terminal and the node ID of the own terminal from the closest node ID of the actual measurement terminal. It is preferable to determine within a range up to the node ID of the closest actual measurement terminal. Further, the measurement result transmission method is not limited to the above method.

  After sending the measurement results to the destination measurement terminal, determine whether all paths have been measured. If there are unmeasured paths, measure the next path after a certain period of time If measurement is in progress, the system waits until the next measurement (S26).

  Note that the list of relay nodes is acquired by the Traceroute command by the measurement terminal that is the source, and the measurement result of the path quality is acquired by the measurement terminal that is the destination by the active measurement, but the measurement terminal that is the source is the relay node. The list can be sent to the destination measurement terminal, and the measurement terminal that is the destination can send the measurement result to the destination measurement terminal. Conversely, the measurement terminal that is the destination sends the measurement result to the destination measurement terminal. It is also possible to adopt a configuration in which the measurement terminal that is the source transmits the measurement result to the storage destination measurement terminal.

FIG. 4 is a flowchart of the congestion location estimation method according to the present invention.
(S41) First, the measurement terminal connected to the path to be estimated acquires a relay node list of the estimation target path.
(S42) Based on the acquired relay node list of the estimation target path, the estimation target path is divided into sections.
(S43) One section from which the measurement result is acquired is selected from the divided sections.
(S44) An n-bit hash value of a value specifying the selected section is obtained, and a measurement result within a predetermined time is acquired from a measurement terminal in which a measurement result of a path including the selected section is stored. When other measurement terminals store the measurement results, the measurement results are acquired in the same way as the storage of the measurement results, with the n-bit length hash value of the value that identifies the selected section as the destination, below the destination node ID A measurement result acquisition request is transmitted to the adjacent terminal having the closest value. If the neighboring terminal that has received the measurement result acquisition request is a measurement terminal that stores the measurement result, the adjacent terminal transmits the measurement result to the transmission source of the measurement result acquisition request, and stores the measurement result. If it is not a measurement terminal, a transfer destination adjacent terminal is determined by the same method and a measurement result acquisition request is transferred. The reason for acquiring only the measurement results within a predetermined time is that the congestion changes with time.
(S45) If measurement results have not been acquired for all sections of the estimation target path, the processes of S43 to S44 are repeated. Then, the congestion location is estimated based on the acquired measurement result.

  The above process will be specifically described with reference to FIG. The table shown in FIG. 5 shows the measurement results for pass 1 to pass 8. In the table shown in FIG. 5, a section where 0 or alphabet is displayed indicates a section constituting the path. For example, the path 1 is composed of sections 1, 2, 3, and 4, and the path 6 is composed of sections 1, 2, 7, and 10. In addition, 0 in the table indicates that no packet loss has occurred as a result of measurement, and the alphabets a to d indicate the value of the packet loss that has occurred or the rank of the packet loss calculated from the value of the packet loss. . For example, in the measurement of path 1, no packet loss occurs, and in the measurement of path 3, it indicates that a packet loss of a% or a packet loss of rank a has occurred.

  The measurement results of the paths 1 to 8 are distributed and arranged in the distributed hash table as described above. That is, it is stored in the measurement terminal determined from the n-bit length hash value of each section of the path. Accordingly, the measurement terminal determined by the n-bit length hash value of the value specifying the section 1 stores the measurement results of the paths 1, 2, 6 and 8, and the n-bit length hash value of the value specifying the section 3 The measurement results of paths 1 and 4 are stored in the measurement terminal determined in (1).

  Here, it is assumed that the path 10 composed of the sections 7, 8, 9 and 10 is estimated. The measurement terminal 1 first selects the section 7 and acquires the measurement result from the measurement terminal that stores the measurement result of the section 7. In this case, the measurement results of the paths 2, 3, and 6 are acquired.

  Subsequently, the section 8 is selected, and the measurement results of the paths 2 and 5 are acquired. Similarly, the measurement results of paths 2, 5, and 8 are acquired by selecting section 9, and the measurement results of paths 3, 5, and 6 are acquired by selecting section 10.

  The measurement terminal 1 estimates the congestion interval based on the acquired measurement results of each path and the intervals constituting the path. At that time, the measurement time is also taken into consideration. In this illustrative example, the measurement terminal 1 acquires the measurement results of the paths 2, 3, 5, 6, and 8, and estimates, for example, the section 10 in which the measurement result indicating no packet loss is obtained as the congestion section.

  If the path is composed of sections of p on average and the number of measurement terminals is N, the average of measurement results obtained by one measurement terminal in one measurement is plog2N. In addition, the time required for obtaining the measurement result is on the order of O (logN), that is, logN, and data necessary for congestion interval estimation can be referred to immediately.

  Each measurement terminal determines an adjacent terminal based on a node ID that is an n-bit length hash value obtained by converting a value unique to the measurement terminal with a hash function such as SHA-1. Then, the transmission or acquisition of the measurement result is performed by using the n-bit hash value of the section constituting the path of the measurement result or the section where the measurement result is to be acquired as the destination, the destination node ID or less, and the closest value. Active measurement is performed by transmitting a test packet to an adjacent terminal by transmitting a measurement result or an acquisition request to the adjacent terminal having a node ID. Therefore, by including the measurement result in the packet transmitted to the adjacent terminal by active measurement, it is possible to reduce the load on the network for transmission of the measurement result.

  Furthermore, consider reducing the load on the network. First, attention is paid to the fact that since the inside of the network is configured with a certain type of hierarchical structure, the number of paths to be measured that pass through increases in the section configured by the relay nodes located in the upper hierarchy.

  FIG. 7 is a diagram for explaining the increase in the number of paths to be measured that pass through a section composed of relay nodes in an upper hierarchy. In FIG. 7, relay nodes are represented by circles, and reference numerals 22, 23, and 24 are relay nodes located in the highest hierarchy. Further, a section from the relay node 22 to 23 is referred to as section A, and a section from the relay node 23 to 24 is referred to as section B. Note that what is represented by a square is a measurement terminal. Here, when the measurement terminal under the relay node 22 measures the path configured with the measurement terminal under the relay node 23, all of these paths include the section A, and the subordinate of the relay node 22 When the measurement terminal in the node measures the path configured with the measurement terminal under the relay node 24, since these paths all include the sections A and B, the section A and the section B have many measurement paths. Will pass.

  The measurement result is transmitted to an adjacent terminal having the n-bit length hash value of the section as the destination, the destination node ID or less and the closest value as the node ID, for example, the section A or section B in FIG. The amount of measurement results transmitted with the n-bit length hash value as the destination increases, and by excluding a part of the paths passing through these sections A and B from the measurement target path, the measurement accuracy is not affected. The load on the network can be reduced.

  For this reason, instead of targeting all paths with adjacent terminals, an upper limit is set for the number of paths to be measured, and if the number of adjacent terminals exceeds the upper limit, Measurement is not performed. When the number of adjacent terminals exceeds the upper limit, it is necessary to determine the adjacent terminal to be measured, that is, the measurement target path, but the method does not include a section through which many measurement target paths pass. Select the measurement target path. For example, in the measurement terminal, the relay node list between each adjacent terminal is acquired, the section constituting the path with the adjacent terminal is recognized, and the reciprocal of the number of paths passing through each section is set as the value of the section. The evaluation value of each path is calculated as the sum of the values of the sections constituting the path, and only the number of paths defined as the upper limit are measured in order from the path having the largest evaluation value. Further, information on paths passing through each section may be exchanged between measurement terminals, and the above calculation may be performed based on the absolute number of paths passing through each section.

  On the other hand, the fact that there are few measurement results on the packet for active measurement means that the effect of reducing the load by putting the measurement result on the active measurement is small. Therefore, the load on the network can be reduced by obtaining the data amount of the measurement result to be transmitted for each adjacent terminal and performing the measurement only with the number of adjacent terminals defined as the upper limit in descending order of the data amount. Here, it is assumed that the data amount of the measurement result includes not only data generated by the measurement result at the terminal itself but also measurement result data that needs to be received and transferred from another measurement terminal.

  The measurement terminal of the present invention can also be realized by operating a computer program for executing each function described above on the computer.

It is a block diagram of the congestion location estimation system by this invention. It is a processing flow figure in each measuring terminal. It is a figure which shows the example of a measurement result and the storage destination measurement terminal of a measurement result. It is a flowchart of the estimation method of the congestion location by this invention. It is a figure explaining the estimation method of the congestion location by this invention. It is a figure explaining the lookup protocol by a prior art. It is a figure explaining that the number of the paths of the measurement object which passes through the section constituted by the relay node of the higher hierarchy increases.

Explanation of symbols

1 Measuring terminal 2 Network 21, 22, 23, 24 Relay node

Claims (9)

The n-bit-length hash value of the value which can identify the terminal and the node ID, with 0 or 2 ⁿ -1 or less, and the other measurement terminal a measurement terminal having a storage range in the range of distinct values,
2 Using the ⁿ as a modulo, a measurement terminal that has a node ID that is equal to or greater than a value obtained by adding a predetermined number to the node ID of its own terminal and that is closest to the value obtained by adding the predetermined number is defined as one adjacent terminal. Determining means for determining one or more neighboring terminals based on the predetermined number;
Obtaining means for obtaining a list of relay nodes on a path with an adjacent terminal;
A measuring means for measuring the quality of a path with an adjacent terminal;
A path dividing unit that divides a path whose quality has been measured with an adjacent terminal into one or more sections specified by adjacent relay nodes on the path, and calculates an n-bit length hash value of a value for identifying each section When,
A storage means for storing the measurement results;
For each section of the path for which quality measurement has been performed, if the n-bit length hash value calculated by the path dividing unit is within the storage range, the measurement result is stored in the storage unit, and if it is outside the storage range, the measurement result is stored. Transmitting means for transmitting the n-bit long hash value as a destination;
A measuring terminal characterized by comprising: It has a measurement result transfer means,
When transmitting the measurement result, the transmission means transmits to the adjacent terminal determined from the n-bit length hash value as the destination,
The measurement result transfer unit stores the received measurement result in the storage unit when the destination value of the received measurement result is within the storage range of the own terminal, and from the destination value when the destination is outside the storage range. The measurement terminal according to claim 1, wherein the measurement terminal transfers to the determined adjacent terminal. When the path for which congestion estimation is performed is divided into sections, and the n-bit length hash value of the value for identifying the section is outside the storage range of the own terminal, the measurement result request is sent to the n-bit length hash value. As a destination, a result acquisition unit that transmits to the adjacent terminal determined from the n-bit length hash value and reads the measurement result from the storage unit of the terminal when it is within the storage range;
If the destination value of the received measurement result request is within the storage range of the own terminal, the measurement result stored in the storage means is transmitted to the measurement terminal that is the transmission source of the measurement result request and is outside the storage range The measurement result request transfer means for transferring to the adjacent terminal determined from the value of the destination,
Congestion interval estimation means for estimating a congestion interval based on the measurement results of other paths including at least one interval among the intervals of the path for which congestion estimation is performed;
The measuring terminal according to claim 2, further comprising:   4. The measuring terminal according to claim 2, wherein the measuring unit performs quality measurement with the adjacent terminal based on a measurement result transmitted from the transmitting unit to the adjacent terminal. For a section constituting a path with each adjacent terminal, the number of paths that pass through the section is searched, and path evaluation value calculation means that calculates a path evaluation value based on the number of paths that pass through the section,
The measuring means has an upper limit value, and based on the path evaluation value, measures a path only with an adjacent terminal within the upper limit value,
The measurement terminal according to any one of claims 1 to 4, wherein The measurement means has an upper limit value, and the path is measured only with the adjacent terminal within the upper limit value in order of the data amount of the measurement result transmitted by the transmission means and the measurement result transfer means to the adjacent terminal,
The measurement terminal according to claim 4. The storage range is modulo 2 ⁿ and is smaller than the node ID of the own terminal among the node IDs of other existing measurement terminals, and is larger than the node ID of the own terminal from the closest node ID, and The measuring terminal according to claim 1, wherein the measuring terminal is within a range up to the nearest node ID. Wherein the predetermined number, modulo ^{2 n,} the preceding claims, characterized in that 2 m + k is (are m 0 or n-1 an integer) (k is 0 or ² n -1 an integer) 8. The measuring terminal according to any one of items 7. A system comprising a network and a plurality of measuring terminals connected to the network,
The system according to claim 1, wherein the measurement terminal is the measurement terminal according to claim 1.

Images