Method for detecting path maximum transmission unit and router

0001Method and router for detecting path maximum transmission unit

0002Technical field

0003The present invention relates to computer technology, and in particular, to a method and router for detecting a path maximum transmission unit. Background technique

0004One disadvantage of the current Internet protocol family is that for a host, there is no standard mechanism for finding the path maximum transmission unit (Path MTU, PMTU) of any path. In the current network, not all router devices support the PMTU detection (Path MTU Discovery, PMTUD) function. It will be a costly project to replace these devices, so the PMTU detection algorithm has increasingly attracted people's attention and research.

0005In Equest For Comments (RFC) 1191, the technical background and solution of the problem are analyzed in detail. The detection algorithms mentioned include decreasing method, increasing method, and empirical reference table method. Nick Christenson proposed the layered detection algorithm, which further improved the detection accuracy. Later, there are also layered detection algorithms improved using the empirical reference table , but there is no in-depth consideration on how to improve the precise positioning of the empirical reference value. Summary of the invention

0006In order to solve this technical problem, the present invention provides a method and a router for realizing the detection of the maximum transmission unit of a path to improve the accurate positioning of the empirical reference value.

0007The present invention provides a method for detecting a maximum transmission unit of a path. The method includes: determining a detection space according to the number of times of empirical reference values in an empirical reference table; and

0008The PMTU value is determined according to the above detection space.

0009Preferably, the above method for detecting the maximum transmission unit of the path may have the following characteristics: The foregoing determining the detection space according to the number of citations of the empirical reference values in the empirical reference table includes: selecting the empirical reference value with the largest reference count as the PMTU initial in the empirical reference table Value, and send the message with the above PMTU initial value as the message length; and

0010If the message is sent successfully, increment the empirical reference value with the largest reference count to send the message until the message fails to send; if the message fails to send, decrement the empirical reference value with the largest reference count to send the message until the message is sent success;

0011The above determination of the PMTU value according to the above detection space includes:

0012The empirical reference value with the largest reference count in the above detection space is selected as the above PMTU value.

0013Preferably, the above method for realizing the detection of the maximum transmission unit of the path may have the following characteristics: The above-mentioned selection of the empirical reference value with the largest reference count in the empirical reference table as the PMTU initial selection of the empirical reference values MO, Ml, ..., Mn Form an empirical reference value array, sort the above empirical reference values, and initialize the critical values Min=M0, Max=Mn; select the empirical reference value Mi with the largest reference count from the above empirical reference value array as the initial value of PMTU. The PMTU value is used as the upper limit of the packet length to encapsulate the packet, and send the encapsulated packet;

0014If the message is sent successfully, the experience reference value with the largest reference count is incremented to send the message until the message fails to be sent; if the message fails to be sent, the experience reference value with the largest reference count is decremented to be sent to the message Successful delivery includes:

0015If the message fails to be sent, and the received Internet Control Message Protocol (ICMP) message from the gateway carries the maximum transmission unit (MTU) value of the next hop of the gateway as Mu, look for an experience reference larger than Mu The minimum empirical reference value Mj in the value is the new Max, and select a bow between [MO, Mj] I to use the empirical reference value Mi with the largest count as the new PMTU value;

0016If the message fails to be sent, and the received ICMP message from the gateway does not carry the MTU value of the next hop of the above gateway, then directly assign Max=Mi and choose a bow between [MO, Mi] The largest experience reference value Mi is counted as the new PMTU value;

0017If the message is sent successfully, choose an empirical reference value with the largest reference count between [Mi, Mn] as the PMTU value, and assign Min=Mi; and

0018After selecting the new PMTU value, the Gen text is sent again, and the values of Min and MAX are changed again until the two are adjacent two values in the empirical reference value array.

0019Preferably, the above method for detecting the maximum transmission unit of the path may have the following characteristics: After the PMTU value is determined according to the detection space, the method further includes: If the PMTU value is an empirical reference value in an empirical reference table, the empirical experience The reference count of the reference value is incremented by one, otherwise, the PMTU value is added to the above empirical reference table.

0020Preferably, the above method for detecting the maximum transmission unit of a path may have the following characteristics: The above method further includes:

0021When selecting an empirical reference value with the largest reference count, if the reference counts of the empirical reference values in the selected interval are the same, then the largest empirical reference value is selected as the PMTU value.

0022The present invention provides a router. The router includes:

0023The space determination module is set to: determine the detection space according to the number of times of the reference value of the empirical reference value in the empirical reference table; and

0024The path maximum transmission unit (PMTU) determination module is set to: determine the PMTU value according to the above detection space.

0025Preferably, the above router may have the following characteristics:

0026The above space determination module includes:

0027The initial determination unit is set to: select the empirical reference value with the largest reference count in the empirical reference table as the initial value of the PMTU, and send the original text using the initial value of the PMTU as the original length; and the iterative determination unit, set to: If the message is sent successfully, the experience reference value with the largest reference count is incremented to send the message until the message fails to be sent; if the message fails to be sent, the experience reference value with the largest reference count is decremented to be sent until the message is successfully sent ;

0028The path maximum transmission unit (PMTU) determination module is further configured to: select the empirical reference value with the largest reference count in the detection space as the PMTU value.

0029Preferably, the above router may also have the following characteristics:

0030The above-mentioned initial determination unit is also set to: select empirical reference values M0, Ml,..., Mn from the empirical reference table to form an empirical reference value array, sort the empirical reference values, and initialize the critical values Min=M0, Max= Mn; Select the empirical reference value Mi with the largest reference count from the above empirical reference value array as the initial PMTU value, encapsulate the message using the above initial PMTU value as the upper limit of the message length, and send the encapsulated message; the iterative determination unit is also set to : If the message fails to be sent, and the received Internet Control Message Protocol (ICMP) message from the gateway carries the maximum transmission unit (MTU) value of the next hop of the gateway as Mu, then look for a larger experience than Mu The minimum empirical reference value Mj among the reference values is taken as the new Max, and an empirical reference value Mi with the largest reference count is selected as the new PMTU value between [MO, Mj]; if the message fails to be sent, and the received The ICMP message of the gateway does not carry the MTU value of the next hop of the above gateway, then directly assign Max=Mi, and choose an empirical reference value Mi with the largest reference count between [MO, Mi] as the new PMTU value; If the message is sent successfully, choose an empirical reference value with the largest reference count between [Mi, Mn] as the PMTU value, and assign Min=Mi; and after selecting a new PMTU value, send the message again and change the Min again And MAX until the two are adjacent two values in the empirical reference value array.

0031Preferably, the above router may also have the following characteristics:

0032The above routers also include:

0033The update module is set to: After the above-mentioned determination of the PMTU value according to the above detection space, if the above-mentioned PMTU value is an empirical reference value in the empirical reference table, the reference count of the above empirical reference value is incremented by one; otherwise, the PMTU value is added to The above experience reference table.

0034Preferably, the above router may also have the following characteristics:

0035The above iterative determination unit is also set to: when selecting an empirical reference value with the largest reference count, if the reference counts of the empirical reference values in the selected interval are the same, then select the largest empirical reference value as the PMTU value.

0036The technical solution of the embodiment of the present invention improves the accuracy of positioning the empirical reference value, saves the iterative steps approaching the optimal PMTU, and achieves the effect of rapid convergence. Brief description of the drawings

0037FIG. 1 is a flowchart of a method for detecting a path maximum transmission unit according to the present invention;

00382 is a schematic diagram of a first process of determining a detection space according to the present invention;

00393 is a schematic diagram of a second process of determining a detection space according to the present invention;

00404 is a schematic diagram of a third process of determining a detection space according to the present invention;

0041FIG. 5 is a schematic diagram of the fourth process of determining the detection space of the present invention; FIG. 6 is a schematic structural diagram of the router of the present invention. Preferred embodiments of the invention

0042The implementation of the technical solution will be described in further detail below with reference to the drawings.

0043In order to improve the precise positioning of the empirical reference value, the present invention proposes a method for detecting the maximum transmission unit of the path, and applies the method to the detection algorithm. This method proposes the concept of reference counting of empirical reference values. This method can be used not only in hierarchical detection algorithms, but also in decrement methods, increment methods, or other algorithms based on empirical reference values.

0044In various algorithms based on empirical reference values, there is bound to be the problem of choosing an empirical reference value, which empirical reference value to choose, there is currently no standard requirement. After introducing the reference count of empirical reference values, there is a basis for selecting empirical reference values.

0045As shown in FIG. 1, it is a flowchart of a method for detecting a path maximum transmission unit according to the present invention. The method includes:

0046Step 101: Determine the detection space according to the number of times of reference values of experience reference values in the experience reference table; the current experience reference table only has some experience reference values suggested in each RFC, and does not have the concept of reference counting; and the present invention is for each experience reference The value sets a reference count for counting the number of times each experience reference value is used; and the reference count can be used to dynamically update the experience reference value in the experience reference table; where the experience reference table can be found in Table 1:

0047Experience Reference Table

0048MTU value reference

65535 RFC791

65535 RFC 1044

005117914 IBM Standard

8166 RFC 1042

4464 RFC 1042

4352 RFC1188

2048 RFC907

2002 RFC 1042

1536 RFC895

1500 RFC894 1500 RFC1134

1492 RFC 1042

1006 RFC1055

1006 RFC1822

576 RFC877

0063544 DEC standard

512 RFC1088

508 RFC 1042

508 RFC1051

296 RFC1144

006868 RFC791 Only some specific empirical reference values are recommended in the RFC. For certain environments, if some empirical reference values other than these empirical reference values are commonly used, these commonly used empirical reference values can be added to the empirical reference table , And count its reference count;

0069Step 102: Determine the PMTU value according to the above detection space.

0070When an empirical reference value needs to be selected in the empirical reference value in the detection interval, the empirical reference value with the largest reference count is selected as the PMTU value;

0071During initialization, the reference count value can be initialized to 0; whenever the empirical reference value is detected as the optimal PMTU value, the reference count of the empirical reference value is incremented by 1.

0072By adopting the above method, the accuracy of positioning the empirical reference value is improved, the iterative steps approaching the optimal PMTU are saved, and the effect of rapid convergence is achieved.

0073The present invention uses a layered detection algorithm based on an empirical reference table to analyze the use method of reference counting. In this embodiment, network packet loss is not considered; an initial iteration point is selected at the beginning of detection, and a reference count is selected in the empirical reference table. The maximum empirical reference value is taken as the initial value of PMTU; then the message is sent as the message length, and if the transmission is successful, the increment is selected) The message is sent with the largest empirical reference value until the transmission fails; if the transmission fails, the reference count is decremented The largest empirical reference value sends the message until it is successfully sent. Through the above method, the path MTU value can be obtained faster.

0074The specific implementation process is as follows: Assume that the initial experience reference value array is MO, Ml, M2, Mn; MO, Ml, M2, ..., Mn are generally the experience reference values listed in Table 1; the experience in the array The reference values are sorted in ascending order, and the initial critical value Min=M0, Max=Mn; select the Mi with the largest reference count from the array as the initial value of PMTU, see Figure 2, which is used as the upper limit of the packet length, encapsulation The packet is sent after setting the Don't Fragment (DF) flag.

0075If you receive an Internet Control Message Protocol (ICMP) message from a gateway that requires fragmentation but DF is not set, it indicates that the next MTU value of the gateway is less than the current PMTU value. Assuming that the MTU value of the next hop of the gateway carried in the returned ICMP message is Mu, if the minimum empirical reference value Mj among the larger empirical reference values is found as the new Max, then it is between [MO, Max] Choose a bow | Use the largest counted empirical reference value Mi as the new PMTU value, see Figure 3. If there is no MTU value for the next hop of the gateway in the reply message (some gateways do not support it), then assign Max=Mi directly, see Figure 4.

0076If the transmission is successful, select an empirical reference value with the largest reference count between [Mi, Mn] as the PMTU value, and assign Min=Mi, see Figure 5.

0077In this way, after finding the new PMTU value, send the text again, change the values of Min and Max again, until the two are adjacent two values in the empirical reference value array, that is, there is no other empirical reference between the two Valued; and ensure that the Min length message is sent successfully, and the Max length message fails to be sent.

0078When selecting an empirical reference value with the largest reference count, if the reference counts of the empirical reference values in the selected interval in the array are the same, the one with the largest empirical reference value is selected.

0079The layered detection first needs to determine the initial detection space [Min, Max], the above is the process of determining the initial detection space; the following is to do layered detection, the present invention will not be described in detail.

0080If the PMTU result after the layered detection is a known empirical reference value in the array, then the reference count of the empirical reference value is incremented by 1, otherwise, the PMTU value is inserted into the array as a new empirical reference value.

0081In reality, the router MTU value generally does not change frequently, even if it is changed, the change range is not large, and it usually changes between certain values. Therefore, the more the number of PMTUDs, the faster the algorithm convergence after using the reference count; Generally, the decreasing and increasing methods are used, and the time complexity is 0 (η ), even if the dichotomy is used to find the time complexity is 0 (logN ); and the time complexity after using reference counting is less than 0 (logN).

0082Assume that the empirical reference value array is MO, Ml, ..., M99; the reference count of each empirical reference value is 0, 1, 0, ..., 0, 7, 9, 0, ..., 0, 2 ; Among them, the reference count of Ml is 1, the reference count of M59 is 7, the reference count of M60 is 9, the reference count of M99 is 2, and the reference counts of other empirical reference values are all 0. The initial detection space finally determined is [M59, M60], then the results of the number of packet transmissions under the four algorithms are shown in Table 2. It can be clearly seen that the use of reference counting greatly reduces the number of useless detection packets and improves the convergence speed.

0083Table of times of sending useless probe packets under different algorithms

0084<img file="WO2012075813A1_D0001.tif" /> As shown in FIG. 6, which is a schematic structural diagram of a router of the present invention, the above router includes a space determination module 61 and a PMTU determination module 62; wherein, the space determination module is used to determine the detection space according to the number of times of reference of empirical reference values in the empirical reference table; path The maximum transmission unit (PMTU) determination module is used to determine the PMTU value according to the above detection space.

0085Wherein, the space determination module may include an initial determination unit and an iterative determination unit; the initial determination unit is used to select 1 in the experience reference table to use the largest counted experience reference value as the initial PMTU value, and the above-mentioned PMTU initial value as the document length Sending the message; the iterative determination unit is used to send the message by incrementing the empirical reference value with the largest reference count if the message is sent successfully until the message fails to be sent; if the message fails to be sent, decrementally selecting the empirical reference with the largest reference count Value to send the message until the message is sent successfully. The path maximum transmission unit (PMTU) determination module is further used to select the empirical reference value with the largest reference count in the detection space as the PMTU value.

0086Preferably, the above initial determination unit may be further used to select empirical reference values MO, Ml,..., Mn from the empirical reference table to form an empirical reference value array, sort the empirical reference values, and initialize the critical value Min=M0 , Max=Mn; select the empirical reference value Mi with the largest reference count from the above empirical reference value array as the initial PMTU value, encapsulate the message using the above PMTU initial value as the upper limit of the message length, and send the encapsulated message; the above iteration The determining unit may be further used to find the smallest experience among the larger experience reference values greater than Mu if the message transmission fails and the MTU value of the next hop of the gateway carried in the received ICMP message from the gateway is Mu The reference value Mj is used as the new Max, and the empirical reference value Mi with the largest reference count is selected as the new PMTU value between [MO, Mj]; if the message fails to be sent, and the received ICMP message from the gateway If the MTU value of the next hop of the above gateway is not carried, Max=Mi is directly assigned, and an empirical reference value Mi with the largest reference count is selected as the new PMTU value between [MO, Mi]; if the message is sent successfully, Then choose an empirical reference value with the largest reference count between [Mi, Mn] as the PMTU value, and assign the value Min=Mi; And after selecting a new PMTU value, the message is sent again, and the values of Min and MAX are changed again until the two are adjacent two values in the empirical reference value array.

0087In order to add some common experience reference values outside the experience reference table to the experience reference table in a specific environment, the router may further include an update module, which is used to determine the PMTU value according to the detection space If the PMTU value is an empirical reference value in the empirical reference table, the reference count of the empirical reference value is incremented by one; otherwise, the PMTU value is added to the empirical reference table.

0088In addition, the above iterative determination unit is also used to select the largest empirical reference value as the PMTU value if the empirical reference value with the largest reference count is selected, and if the reference counts of the empirical reference values in the selected interval are the same.

0089The process of the above-mentioned space determination module determining the detection space can be referred to FIG. 2 to FIG. 5, which will not be repeated here. The router determines the probe space through the space determination module, and then the PMTU determination module selects the empirical reference value with the largest reference count as the PMTU value; after using the reference count, the router greatly reduces the number of useless probe packets sent and improves the convergence speed, and Increased the ^" determination bit for the empirical reference value.

0090A person of ordinary skill in the art may understand that all or part of the steps in the above method may be completed by instructing relevant hardware through a program, and the above program may be stored in a computer-readable storage medium, such as a read-only memory, a magnetic disk, or an optical disk. Optionally, all or part of the steps in the foregoing embodiments may also be implemented using one or more integrated circuits. Correspondingly, each module/unit in the above embodiments may be implemented in the form of hardware, or may also be implemented in the form of software function modules. The invention is not limited to any specific form of combination of hardware and software. The above embodiments are only used to illustrate the technical solutions of the present invention but not to limit them, and the present invention has been described in detail with reference to the preferred embodiments. Those of ordinary skill in the art should understand that the technical solutions of the present invention can be modified or equivalently replaced without departing from the spirit and scope of the technical solutions of the present invention, and should be covered by the scope of the claims of the present invention.

0091Industrial Applicability The technical solution of the embodiment of the present invention improves the accuracy of positioning the empirical reference value, saves the iterative steps approaching the optimal PMTU, and achieves the effect of rapid convergence.