JP3422952B2 - Packet switched network section free band measurement method and apparatus - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a technique for managing a packet switching network such as the Internet, and more specifically, a technique for measuring the state of the network and a quality of service provided on the network. It is about technology.

[0002]

2. Description of the Related Art In packet switching networks, a conventional method for measuring an available bandwidth has been to actually transfer data and to divide the amount of data that can be transferred by the time required for the transfer. This method has a problem in that, in order to transfer data, another device, which is a partner device for transfer, is required in addition to the measuring device. The free bandwidth that can be measured by this method is the value of the interval with the minimum free bandwidth in the route between the measuring device and the partner device, and it is difficult to specify that interval, and any interval can be measured. There were problems such as not being able to do it. Furthermore, with this method, it is necessary to perform data transfer for the minimum free bandwidth in the route between the measurement device and the partner device so that the free bandwidth is used up, so the load on the packet switching network is reduced. There is a problem that other traffic that shares the section is adversely affected, such as causing packet loss.

[0003]

SUMMARY OF THE INVENTION An object of the present invention is to provide a section free band measuring method and apparatus for a packet switching network, which has a light load on the packet switching network and can measure a free band in a desired section. Especially.

[0004]

A packet switching network section free band measuring method according to the present invention comprises a plurality of nodes,
A measuring device, wherein the measuring device sends a plurality of test packets to two nodes to be transmissions located at both ends of the measurement target section by a single route, and packets to the two transmission target nodes The transfer delay time is measured, the minimum value is determined for each of the two transmission target nodes from the measured value of the packet transfer delay time, and the minimum value is determined for each of the two transmission target nodes from the measured value of the packet transfer delay time. An average value is obtained, and from the minimum value and the average value of the packet transfer delay time for each of the two transmission target nodes, the sum of the average waiting time in the queue of each node through which the packet passes from the measuring device to the transmission target node is calculated. From the difference of the sum of the average waiting time calculated for each of the two transmission target nodes, In a method of measuring a section free bandwidth of a packet switching network for calculating a section average waiting time in a queue, a measuring device forms a queue model of a section to be measured, and the section average waiting time, the link speed of the section, and the section Calculating the queuing model based on the average burst length when the generation process of each burst can be described by the Poisson distribution when the traffic flowing through is considered as a unit of burst, and calculate the free bandwidth of the measurement target section Is characterized by.

Further, the packet switching network section idle band measuring apparatus of the present invention comprises a plurality of nodes and a plurality of test packets respectively provided to two nodes to be transmitted located at both ends of the section to be measured by one route. Means for transmitting the packet transfer delay time to the two transmission target nodes, means for determining the minimum value for each of the two transmission target nodes from the measured value of the packet transfer delay time, the packet A means for obtaining an average value for each of the two transmission target nodes from the measured value of the transfer delay time, and a packet for transmission from the measurement device based on the minimum value and the average value of the packet transfer delay time for each of the two transmission target nodes. A method of calculating the sum of the average waiting time in the queue of each node that passes up to the node , And from the difference of the sum of the average waiting time obtained for each of the two transmission nodes,
In a packet switching network including a measuring device having means for calculating a section average waiting time in a queue to a measurement target section, the measurement target section is modeled as a queue, the section average waiting time and the link speed of the section And the average burst length when the generation process of each burst can be described by Poisson distribution when the traffic flowing in the section is regarded as a unit of burst, and the queuing model calculation is performed based on It is characterized by having a means for calculating. In a preferred embodiment of the present invention, the free bandwidth of the measurement target section j is B _j , the link speed of the section j is R _j , the section average waiting time in the section _j is Q _j , and the section j is If the average burst length when the generation process of each burst can be described by the Poisson distribution when the traffic flowing through is regarded as a unit of burst, and the average burst length is M, then the equation: B _j = M · R _j / (M + R _j Q _j ), The free band of the measurement target section j is calculated.

[0006]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, embodiments of the present invention will be described with reference to the drawings. FIG. 1 is a diagram for explaining a network configuration and a measurement target section to which the present invention is applied, and here,
IP network as an example of packet switching network
Indicates 10. In this IP network 10, links 1,2, ..., j-1, j, ... from the measuring device 1 according to the present invention along the route.
And IP routers 1,2, ..., j-1, j, ... are connected in a line. Here, the measurement target section is the j-th link j,
The IP routers at both ends are IP router j-1 and IP router j. Further, it is assumed that the IP router has a function of immediately returning a response packet in response to a packet response request. All existing IP routers have this function. Further, it is assumed that the method of the present invention is mounted on the measuring device 1.

FIG. 2 is a block diagram showing a configuration example of the packet switching network section free band measuring device 1 of the present invention. In the figure, 2 is a packet generating device, 3 is a packet transmitting device, 4 is a packet receiving device, 5 is a device for determining a minimum value of packet transfer delay time, 6 is a device for calculating an average value of packet transfer delay time, 7 Is an apparatus for calculating the average waiting time to the target node, 8 is an apparatus for calculating the average waiting time to the free bandwidth measurement target section, and 9 is an apparatus for applying the queuing theory to calculate the free bandwidth.

A test packet is generated by the packet generator 2 according to parameters such as the target node, the packet size, the number of transmissions, and the transmission interval, which are input to the measuring device 1,
The generated test packet is transmitted from the packet transmission device 3. The returned test packet is received by the packet reception device 4, and data such as the target node and the transfer delay time is stored. Based on the data stored in the packet receiving device 4, the device 5 determines the minimum value of the packet transfer delay time, and the device 6 calculates the average value of the packet transfer delay time. From the minimum value and the average value of these packet transfer delay times, the device 7 calculates the sum of the average waiting times to the target node. The device 8 calculates the section average waiting time to the free bandwidth measurement target section from the difference in the sum of the average waiting times to the adjacent target nodes, and from the calculation result, the link speed of the measurement target section, the queue parameter, and the like. The device 9 applies the queuing theory to calculate the free bandwidth, and outputs the result.

FIG. 3 is a diagram showing a flow of an embodiment of the present invention. First, the packet transfer delay time D _{j, i} to the IP router j at one end of the measurement target section is measured a plurality of times (1 to i) using a test packet of a fixed size (step 1).
1). Similarly, the packet transfer delay time D _{j-1, i} to the IP router j-1 at the other end of the measurement target section is repeated a plurality of times (1 to i).
Measure (step 12). In this case, the order of measurement is arbitrary. Next, from the obtained packet transfer delay times D _{j, i} and D _{j-1, i} , the minimum value min _i (D _{j, i) is} set for each IP router.
) And min _i (D _{j-1, i} ) are respectively determined (steps 13 and 15). Similarly, from the obtained packet transfer delay times D _{j, i} and D _{j-1, i} , the average value ave
_i (D _{j, i} ) and ave _i (D _{j-1, i} ) are calculated respectively (steps 14 and 16). As this average value, a value indicating another average such as an intermediate value may be used depending on the state of the network.

The average packet transfer delay time ave _i (D _{x, i} ) to the x-th IP router x on the route is an average that varies depending on the transfer delay time L _x peculiar to the route and the congestion state of the route. It can be represented by the sum of the waiting time W _x . L _x is the sum of the time required for a signal to propagate through each section on the route and the time required for each IP router passing through to process the packet.

W _x is the sum ΣQ _k (k = 1,2, ..., x) of the section average waiting time to each passing link. Minimum value min _i of the packet transfer delay (D _{x, i)} is sufficiently if the measurement data according to a number of test packets, likely to be transferred without waiting for all routers on the path, L _x
Can be considered. Therefore, the average waiting time W _x to the IP router _x is calculated by W _x = ave _i (D _{x, i} ) −L _x = ave _i (D _{x, i} ) −min _i (D _{x, i} ). You can Using this equation, for the IP routers j and j-1 at both ends of the measurement target section, W _j and W respectively
_j-1 is calculated (steps 17 and 18).

[0012] The term average waiting time Q _j in the measurement target section j, the average latency and IP routers to IP router j
can be calculated by the difference _{Q j = W j -W j-} 1 and the average waiting time until j-1.

From the above, the section average waiting time in the section to be measured is obtained (step 19). The traffic flowing through the target section is captured in bursts corresponding to the content size such as WWW. At this time, assuming that the generation process of each burst can be described by Poisson distribution (random arrival) and the service time is proportional to the burst length expressed by exponential distribution with mean M, B _j = M · R _j from the queue calculation. The empty band B _j of the measurement target section j can be calculated from / (M + R _j Q _j ) (step 20). Here, R _j is the link speed of the measurement target section. This R _j may be known,
Even if it is not known, applying a method such as described in Japanese Patent Application No. 10-275673 to obtain the link speed of an arbitrary section to the IP routers at both ends of the section to be measured will put a heavy load on the network. You can ask without paying.

[0014]

As described above, in the conventional method, it was necessary to exchange data with the partner terminal, but according to the packet switching network section free band measuring method of the present invention, a test packet is sent from the measuring device. Since the data is transmitted to the node, there is an advantage that the other terminal is unnecessary. Also,
In the conventional method, only the value of the section with the smallest free band in the path between the measuring apparatus and the partner terminal can be measured, but according to the method of the present invention, the test packet is sent from the measuring apparatus to both nodes of the section to be measured. Is transmitted, there is an advantage that an empty band in an arbitrary section can be measured. Further, in the conventional method, it is necessary to perform data transfer for the section with the smallest free band on the path between the measuring device and the partner terminal so that the empty band is used up, and other sections that share that section are shared. There was a problem that the traffic was adversely affected,
According to the method of the present invention, since a test packet having a small capacity is used, there is an advantage that the load on the packet switching network can be significantly reduced and other traffic sharing the section is not affected.

[Brief description of drawings]

FIG. 1 is a diagram illustrating a network configuration and a measurement target section to which the present invention is applied.

FIG. 2 is a block diagram showing a configuration example of a packet switching network section free band measuring device of the present invention.

FIG. 3 is a diagram showing a flow of an embodiment of the present invention.

[Explanation of symbols]

1 measuring device 2 packet generating device 3 packet transmitting device 4 packet receiving device 5 device for determining the minimum value of packet transfer delay time 6 device for calculating the average value of packet transfer delay time 7 calculating the average waiting time to the target node Device 8 Device for calculating average waiting time to free bandwidth measurement target device 9 Device for applying queuing theory to calculate free bandwidth 10 IP network

Front page continuation (72) Inventor Takayuki Furuya 2-3-1, Otemachi, Chiyoda-ku, Tokyo Inside Nippon Telegraph and Telephone Corporation (56) References Takayuki Furuya, Takumi Kimura, measurement quantity for hop condition monitoring of the Internet , The Institute of Electronics, Information and Communication Engineers, 1998 Communication Society Conference Proceedings 2, Japan, The Institute of Electronics, Information and Communication Engineers, September 7, 1998, B-11-15 (58) Fields investigated (Int.Cl. ⁷ , DB name) H04L 12/56 400 H04L 12/56 200

Claims (4)

(57) [Claims] 1. A plurality of nodes and a measurement device are provided, and the measurement device transmits a plurality of test packets to two nodes to be transmissions located at both ends of a measurement target section by one route, respectively. , Measuring the packet transfer delay time to each of the two transmission target nodes, determining the minimum value for each of the two transmission target nodes from the measured value of the packet transfer delay time, and measuring the packet transfer delay time From the above, the average value is obtained for each of the two transmission target nodes, and from the minimum value and the average value of the packet transfer delay time for each of the two transmission target nodes, each node through which the packet passes from the measuring device to the transmission target node The average waiting time in each of the two waiting nodes is calculated, and the average waiting time obtained for each of the two transmission target nodes is calculated. In the method of measuring the section free bandwidth of the packet switching network, which calculates the section average waiting time in the queue to the section to be measured from the difference in the time sum,
When the measuring device forms a queuing model for the section to be measured, and when the section average waiting time, the link speed of the section, and the traffic flowing through the section are regarded as a unit of burst, the generation process of each burst can be described by Poisson distribution. A packet switching network section free band measuring method, characterized in that a queuing model calculation is performed based on the average burst length at that time and a free band in the measurement target section is calculated. 2. The packet switching network section free band measuring method according to claim 1, wherein the measuring device sets a free band of the measurement target section j as B _j , sets a link speed of the section j as R _j, and sets the section Let Q _{j be the} section average waiting time in _j, and let M be the average burst length when the generation process of each burst can be described by Poisson distribution when the traffic flowing in the section j is regarded as a unit of burst. A packet-switched network section free band measuring method, characterized in that the free band of the measurement target section j is calculated based on B _j = M · R _j / (M + R _j Q _j ). 3. A means for transmitting a plurality of test packets by a single route to a plurality of nodes and two transmission target nodes located at both ends of a measurement target section, respectively.
Means for measuring the packet transfer delay time to the two transmission target nodes, means for determining the minimum value for each of the two transmission target nodes from the measured values of the packet transfer delay time, and measurement of the packet transfer delay time From the value, means for obtaining an average value for each of the two transmission target nodes, and from the minimum value and the average value of the packet transfer delay time for each of the two transmission target nodes, a packet passes from the measuring device to the transmission target node. Means for calculating the sum of average waiting times in the queue of each node, and the section average waiting time in the queue to the measurement target section from the difference in the sum of the average waiting times obtained for each of the two transmission target nodes In a packet-switched network equipped with a measuring device having means for calculating A matrix model of waiting for the target interval,
A queuing model based on the section average waiting time, the link speed of the section, and the average burst length when the generation process of each burst can be described by Poisson distribution when the traffic flowing through the section is regarded as a unit of burst A packet switching network section free band measuring device comprising means for performing calculation and calculating a free band in a measurement target section. 4. The packet switching network section free band measuring device according to claim 3, wherein the free band of the measurement target section j is B _j , the link speed of the section j is R _j, and the section average in the section j. Let the waiting time be Q _j ,
When the average burst length when the generation process of each burst can be described by a Poisson distribution when the traffic flowing through the section j is regarded as a unit of burst, and the average burst length is M, the equation: B _j = M · R _j / (M + R A packet-switched network section free band measuring device having means for calculating a free band of a measurement target section j based on _j Q _j ).