CN100396020C - A network tight link location method based on dual-rate periodic flow technology - Google Patents

Abstract

The invention provides a method for locating network tight links based on dual-rate periodic flow technology. This method needs to set the sending end and receiving end of the detection data packet sequence at both ends of the network path to be tested respectively: first, determine the minimum upper bound and the maximum lower bound of the available bandwidth of the network path to be tested by periodic flow technology, so as to determine the detection rate of the sending end. The sending rate of the data packet column; then send a group of detection data packet series based on the double-rate periodic flow characteristics to the receiving end, and the receiving end calculates and analyzes the trend of the one-way delay of the data packet in the received detection data packet series to accurately and quickly The location of the tight link in the network path can be accurately judged, which is beneficial to the development and implementation of various congestion control strategies and scheduling strategies based on network bandwidth.

Description

A network tight link location method based on dual-rate periodic flow technology

technical field

The invention relates to an end-to-end active test method for locating tight links in a network path, which is oriented to the performance test field of computer networks.

Background technique

A network path is composed of several network links. For the end-to-end active test method, the available bandwidth of a network link refers to the maximum rate at which a set of probe packets can pass through the link without congestion, and the available bandwidth of a network path refers to the maximum rate at which a set of probe packets can pass through the link without congestion. The maximum rate that can pass through this path without congestion. A tight link in a network path is one in which the available bandwidth of the network link is equal to the available bandwidth of the network path.

With the rapid development of computer network technology, the corresponding network performance testing technology has also undergone great innovations. At present, there are mainly two methods for locating tight links in the test path. Both methods have advantages and disadvantages.

1. Passive positioning method based on SNMP

The method is to use the simple network management protocol (simple network management protocol, SNMP) to read the relevant information in the MIB of all routers in the path to be tested, so as to obtain the distribution of the available bandwidth of the links along the path to be tested. Through quantitative judgment, the application program can easily obtain the location information of tight links. The advantage of this method is that it is simple, practical, operable, and easy to manage. However, the disadvantages of this method are also obvious. First of all, the MIB of the router does not necessarily have read permission. However, the usual situation is that the router information owned by different ISPs is private. Therefore, the applicable environment based on this segment-by-segment positioning method has inherent limitations. This limitation makes this method impractical. Secondly, the method of constructing available bandwidth distribution by reading router MIB information is a passive monitoring method. The accuracy of the information provided by the router is subject to confirmation, and this method does not provide a confirmation scheme for this. Therefore, this method also suffers from the localization accuracy problem of tight links. Software that uses this method includes MRTG, etc.

2. End-to-end active localization method

This method uses the end-to-end active measurement technology to locate the tight link of the path to be tested. Probe streams are actively sent from one end of the path to be tested to the other. The tight link information in the path to be tested is determined by the properties of the probe flow in the link. The advantage of this method is that it is simple, practical, has nothing to do with intermediate devices (such as routers in the path), and is easy to manage. The Bfind tool developed by Carnegie Mellon University in the United States is the first tool that uses an end-to-end active location method to measure available bandwidth bottlenecks in network paths. At the sending end of the test, Bfind continuously sends loads to the receiving end, and at the same time obtains the ring delay of each link in the network path through the traceroute method, and uses this to determine the location of the bottleneck of the available network bandwidth. However, the early end-to-end active positioning method has a relatively large negative impact on the network. Due to the large sending load, it will affect other applications in the network path, and the accuracy of the link ring delay obtained by the traceroute method is low.

Contents of the invention

The purpose of the present invention is: aiming at the deficiency of network path bandwidth bottleneck positioning method, propose an active test method for locating tight links in a network path spanning multiple routers, which helps application programs or network managers to accurately understand the network The location of the available bandwidth bottleneck in the path is helpful to develop and implement various new congestion control strategies and scheduling strategies based on network bandwidth.

For achieving this purpose, technical scheme of the present invention is as follows:

The present invention is made up of following three test steps:

(1) Determine the minimum upper bound and the maximum lower bound of the available bandwidth of the network path to be tested;

(2) The sending end sends a group of detection data packets based on the characteristics of the double-rate periodic flow to the receiving end;

(3) The receiving end receives the group of probe data packets, calculates the one-way transmission delay of each data packet in the packet train, and analyzes the trend of data packet delay in the probe data packet train.

In particular, according to the trend of data packet delay, it can be obtained: trend 1, data packet delay is increasing (only consider the first case of increasing trend in the k groups of detection data packet columns), it indicates that the link is Tight links in network paths. The second trend is that the packet delay does not show an increasing trend, which indicates that the specific link is not a tight link in the network path.

In particular, when the minimum upper bound and the maximum lower bound of the available bandwidth of the network path to be tested are determined in the present invention, a periodical flow technique that periodically sends data packets from the sending end to the receiving end at a constant rate is adopted. The steps of this technology are: under a specific resolution accuracy (analysis accuracy λ, λ<=minimum upper bound-maximum lower bound of the available bandwidth of the network path to be tested), the sending end sends a set of detection data packets to the receiving end at a relatively high rate List. The receiving end receives this group of probe data packets, calculates the one-way transmission delay (one-way delay, OWD) of each data packet in the packet train, and analyzes the trend of data packet delay in the probe data packet train. Trend 1, the packet delay is increasing, indicating that the sending rate selected by the sender is higher than the available bandwidth of the network path to be tested, and this rate is the upper bound of the available bandwidth of the network path to be tested. The receiving end sends control parameters to the sending end, and adjusts the sending rate of the next group of probe data packets at the sending end to half of the original rate. The second trend is that the packet delay does not show an increasing trend, indicating that the sending rate selected by the sender is lower than or equal to the available bandwidth of the network path to be tested, and this rate is the lower bound of the available bandwidth of the network path to be tested. The receiving end sends control parameters to the sending end, and adjusts the sending rate of the next group of probe data packets at the sending end to the minimum value of twice the original rate and the maximum rate of the probe data packet trains that the sending end can generate. Through this iteration, the smallest upper bound and the largest lower bound of the available bandwidth of the network path to be tested are finally obtained.

In particular, in this method, the dual-rate periodic stream sent by the sender uses half of the sum of the minimum upper bound and the maximum lower bound of the available bandwidth as the sending rate, and the construction process of the detection data packet sequence is as follows: a part of the packet sequence The TTL (time to live) domain value in the IP header of the data packet is set to a specific value (the specific value can indicate the position of the specific link in the entire network path to be tested). The sender sends such data packets with specific TTL values alternately with normal probe data data packets. Since the router that the data packet passes through before reaching the destination end will automatically decrement the TTL field value in the IP header of the data packet by 1, therefore, when the detection packet arrives at a specific link position, those data packets with a specific TTL value set IP The TTL field value in the header is reset to zero, and the data packet is discarded by the router. At this time, the number of data packets in the detection packet column is halved, and the transmission rate of the detection packet column is reduced to half of the rate reaching the router, which is the non-congestion rate. (Because the transmission rate of the detection packet is less than or equal to the sending rate when it passes through the network path from the sending end to the receiving end, the sending rate is half of the sum of the minimum upper bound and the maximum lower bound, and half of the sending rate is less than the maximum lower bound of the sending rate, so , the transmission rate of the detection packet column can pass through the entire path to be tested without congestion after it becomes the congestion-free rate.) If the network path is composed of k links, the detection packet column is divided by each link in the network path it passes through Set the corresponding TTL field value (from 1 to k) in the sequence of the path, and the sender will generate a total of k groups of probe data packet sequences with different TTL field values.

The beneficial effect of the invention is that the load can be effectively reduced, and the position of the tight link in the network path can be located more quickly and accurately.

Description of drawings

Figure 1 and Figure 2 show the construction process and path behavior of the dual-rate periodic flow in the present invention.

Fig. 3 is a schematic diagram of the simulation experiment environment of the present invention.

Figure 4 shows the one-way delay measured by the simulation experiment under the CBR background load.

Figure 5 shows the one-way delay measured by the simulation experiment under the Pareto background load.

Detailed ways

The present invention will be further described below in conjunction with the embodiments and the accompanying drawings.

Figure 1 and Figure 2 show the construction process and path behavior of the dual-rate periodic flow in the present invention. In order to ensure the validity of the dual-rate periodic flow detection data packet sequence, the embodiment is established in an adjustable and repeatable environment, as shown in FIG. 3 , and the link and load can be adjusted. The link length is 7 (H=7), and the network topology is shown in Figure 3. The two ends of the network path are provided with a sending end and a receiving end, and the sending end alternately sends ordinary CBR1 data packet trains and CBR2 data packet trains with a specific TTL value set. tl1 is link 1 and tl2 is link 2.

wide bottleneck.

Example 1: Implementation under constant bit rate background streaming

The capacity of l ₄ is set to 2 Mbps, and the capacity of other links is 10 Mbps. By injecting background traffic, the utilization rate of each link reaches 60%. Therefore, the bottleneck link is l ₄ .

Step 1: Use periodic flow technology to measure the minimum upper bound and maximum lower bound of the available bandwidth of the path to be tested.

Step 2: Construct a dual-rate periodic flow based on the measured path available bandwidth. That is, at the sending end, two CBR (constant bit rate) sending sources are used to alternately send two sets of data packet sequences S1 and S2. According to the construction characteristics of the dual-rate periodic flow detection packet train, the two sets of data packet trains are sent alternately, that is, in the same time interval, S1 sends a data packet, and then S2 sends another data packet, and so on.

Step 3: Use the sending source to generate a constant bit rate network load (as shown in Figure 4). Experimental results show that when TTL=4, OWD shows an increasing trend, but when TTL=3 there is no increasing trend. Thus the link bottleneck is found to be l ₄ .

Example 2: Implementation of Pareto Background Streaming

The capacity of l ₄ is set to 2 Mbps, and the capacity of other links is 10 Mbps. By injecting background traffic, the utilization rate of each link reaches 60%. Therefore, the bottleneck link is l ₄ .

Step 1: Use periodic flow technology to measure the minimum upper bound and maximum lower bound of the available bandwidth of the path to be tested.

Step 2: Construct a dual-rate periodic flow based on the measured path available bandwidth. That is, at the sending end, two CBR (constant bit rate) sending sources are used to alternately send two sets of data packet sequences S1 and S2. According to the construction characteristics of the dual-rate periodic flow detection packet train, the two sets of data packet trains are sent alternately, that is, in the same time interval, S1 sends a data packet, and then S2 sends another data packet, and so on.

Step 3: Use the sending source to generate Pareto network load (as shown in FIG. 5 ). When TTL=4, OWD shows an increasing trend, but when TTL=3, there is no increasing trend. Thus the link bottleneck is found to be l ₄ .

Claims (1)

1. A method for locating network tight links, using end-to-end active testing technology, which consists of the following three steps: 1), determine the smallest upper bound and the largest lower bound of the available bandwidth of the network path to be tested; 2), the sending end sends a group of detection data packets based on the characteristics of the double-rate periodic flow to the receiving end; wherein, the double-rate periodic flow refers to a periodic flow composed of a data packet group with a specific TTL domain value and a common data packet group; 3), the receiving end receives this group of detection data packet column, calculates the one-way transmission delay of each data packet in the packet column, and analyzes the trend of data packet delay in the detection data packet column, and the data packet column passes through the network path When , the target measurement link whose delay of the first data packet does not show an increasing trend is a tight link, where the tight link refers to the link whose available bandwidth of the network link is equal to the available bandwidth of the network path; Among them, when determining the minimum upper bound of the available bandwidth of the network path to be tested, the following method is used: (1) Under any specific bandwidth analysis accuracy between the minimum upper bound and the maximum lower bound of the available bandwidth of the network path to be tested, use the periodic flow technology, wherein the periodic flow technology is periodically sent from the sender to the receiver at a constant rate packet column; (2), the receiving end receives this group of probing data packet column, calculates the one-way transmission delay of each data packet in the packet column, and analyzes the trend of data packet delay in the probing data packet column; (3) The data packet delay is increasing. The receiving end sends control parameters to the sending end, and adjusts the sending rate of the next group of detection data packets at the sending end to half of the original rate, and iterates to determine the available bandwidth. least upper bound; Among them, when determining the maximum lower bound of the available bandwidth of the network path to be tested, the following method is adopted: (1) Under any specific bandwidth analysis accuracy between the minimum upper bound and the maximum lower bound of the available bandwidth of the network path to be tested, use the periodic flow technology, wherein the periodic flow technology is periodically sent from the sender to the receiver at a constant rate packet column; (2), the receiving end receives this group of probing data packet column, calculates the one-way transmission delay of each data packet in the packet column, and analyzes the trend of data packet delay in the probing data packet column; (3) The data packet delay does not show an increasing trend, the receiving end sends control parameters to the sending end, and adjusts the sending rate of the next set of detection data packets at the sending end to twice the original rate and the detection that the sending end can generate The minimum value between the maximum rates of the data packet column is iterated to determine the maximum lower bound of the available bandwidth; Among them, the sender uses half of the sum of the minimum upper bound and the maximum lower bound of the available bandwidth as the transmission rate of the dual-rate periodic flow; Among them, the method of forming a dual-rate stream is that the sending end sets the TTL field value in the IP packet header of a part of the data packets in the probing data packet column to a specific value, and then combines the data packets with the specific TTL value with the common probing data packets sent alternately.

Images