WO2012075813A1 - Method for detecting path maximum transmission unit and router - Google Patents

Abstract

A method for detecting path maximum transmission unit (PMTU), the method comprises: determining a detection space according to the number of times cited of an empirical value in an empirical reference table; and determining the PMTU value according to the detection space. Also disclosed is a router thereof. The present invention improves the precision in locating empirical reference values, reduces the iteration steps for approaching the optimal PMTU, thus achieving the effect of fast convergence.

Description

 Method and router for realizing path maximum transmission unit detection

Technical field

 The present invention relates to computer technology, and more particularly to a method and router for implementing path maximum transmission unit detection. Background technique

 A disadvantage of the current Internet Protocol family is the lack of a standard mechanism for the Path MTU (PMTU) of a path to find any path. In the current network, not all router devices support the Path MTU Discovery (PMTUD) function. To replace these devices will be a costly project, so the PMTU detection algorithm has attracted more attention and research.

 The technical background and solution of the problem are analyzed in detail in Equest For Comments (RFC) 1191. The detection algorithms mentioned include decrement method, incremental method, and empirical reference table method. Nick Christenson proposed a layered detection algorithm that further improves the detection accuracy. Later, there is also a layered detection algorithm improved by the empirical reference table, but there is no in-depth consideration of how to improve the accurate positioning of the empirical reference values. Summary of the invention

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

 The present invention provides a method for implementing path maximum transmission unit detection, the method comprising: determining a detection space according to a reference number of empirical reference values in an empirical reference table;

 The PMTU value is determined based on the above detection space.

Preferably, the method for implementing path maximum transmission unit detection may have the following features: determining the detection space according to the reference number of empirical reference values in the empirical reference table includes: selecting an empirical reference value with the largest reference count as the initial PMTU in the empirical reference table. Value, and Transmitting the text with the initial PMTU value as the text length;

 If the packet is sent successfully, the packet with the highest reference value is incremented to send the packet until the packet fails to be sent. If the packet fails to be sent, the packet with the highest reference number of the reference count is sent down until the packet is sent. Success

 The foregoing determining the PMTU value according to the foregoing detection space includes:

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

 Preferably, the method for implementing the path maximum transmission unit detection may have the following characteristics: selecting the empirical reference value with the largest reference count in the empirical reference table as the PMTU initial selection empirical reference value MO, Ml, ..., Mn from the empirical reference table. Forming an array of empirical reference values, sorting the above empirical reference values, and initializing the threshold value Min=M0, Max=Mn; selecting the empirical reference value Mi with the largest reference count from the above empirical reference value array as the initial value of the PMTU, with the above initial The PMTU value encapsulates the packet as the upper limit of the packet length, and sends the encapsulated packet.

 If the packet is sent successfully, the packet with the highest reference value is incremented to send the packet until the packet fails to be sent. If the packet fails to be sent, the packet with the highest reference value is sent down until the packet is sent. Successful delivery includes:

 If the message fails to be sent, and the maximum transmission unit (MTU) value of the next hop of the gateway carried in the received Internet Control Message Protocol (ICMP) message from the gateway is Mu, then an empirical reference larger than Mu is sought. The minimum empirical reference value Mj in the value is taken as the new Max, and an empirical reference value Mi with the largest count is selected between [MO, Mj] as the new PMTU value;

 If the packet fails to be sent, and the received ICMP message from the gateway does not carry the MTU value of the next hop of the gateway, directly assign Max=Mi and select a bow between [MO, Mi]. Counting the largest empirical reference value Mi as the new PMTU value;

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

 After selecting the new PMTU value, send the message again and change the values of Min and MAX again until the two values are adjacent in the empirical reference array.

Preferably, the foregoing method for implementing path maximum transmission unit detection may have the following characteristics: After determining the PMTU value according to the foregoing detection space, the method further includes: if the PMTU value is an empirical reference value in the experience reference table, adding a reference count of the empirical reference value, otherwise, adding the PMTU value to the foregoing Experience reference table.

 Preferably, the method for implementing the path maximum transmission unit detection may have the following features: The foregoing method further includes:

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

 The present invention provides a router, and the foregoing router includes:

 a space determination module, configured to: determine a detection space according to a reference number of empirical reference values in an empirical reference table;

 A Path Maximum Transmission Unit (PMTU) determination module is configured to: determine a PMTU value based on the above detection space.

 Preferably, the above router may have the following characteristics:

 The space determination module described above includes:

 The initial determining unit is set to: in the empirical reference table, select the empirical reference value with the largest reference count as the initial value of the PMTU, and send the initial value of the PMTU as the length of the 4 艮 text; and the iterative determining unit, set to: If the packet is sent successfully, the packet with the highest reference value is incremented to send the packet until the packet fails to be sent. If the packet fails to be sent, the packet with the highest reference number of the reference count is sent down until the packet is successfully sent. ;

 The above path maximum transmission unit (PMTU) determining module is further configured to: select an empirical reference value having the largest reference count in the above detection space as the above PMTU value.

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

The above initial determining unit is further configured to: select an empirical reference value M0, Ml, ..·, Mn from the empirical reference table to form an array of empirical reference values, sort the above empirical reference values, and initialize the critical value Min=M0, Max= Mn; selecting the empirical reference value Mi with the largest reference count from the above-mentioned empirical reference value array as the initial value of the PMTU, and using the initial value of the PMTU as the upper limit of the packet length to encapsulate the packet, and sending the encapsulated packet; The above-mentioned iterative determining unit is further configured to: if the packet transmission fails, and the received maximum transmission unit (MTU) value of the next hop of the gateway carried in the Internet Control Message Protocol (ICMP) packet from the gateway is Mu, Then find the minimum empirical reference value Mj among the empirical reference values larger than Mu as the new Max, and select an empirical reference value Mi with the largest reference count between [MO, Mj] as the new PMTU value; if the message is sent If the received MTU packet from the gateway does not carry the MTU value of the next hop of the gateway, the value of Max=Mi is directly assigned, and an empirical reference value with the largest reference count is selected between [MO, Mi]. Mi as the new PMTU value; if the message is sent successfully, select the empirical reference value with the largest reference count between [Mi, Mn] as the PMTU value, and assign Min=Mi; and select the new PMTU value again. Send the message and change the values of Min and MAX again until the two are adjacent to each other in the empirical reference array.

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

 The above routers also include:

 The update module is configured to: after determining the PMTU value according to the foregoing detection space, if the PMTU value is an empirical reference value in the experience reference table, the reference count of the empirical reference value is incremented by one, otherwise, the PMTU value is added to The above experience is referenced in the table.

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

 The above iterative determining unit is further configured to: when selecting an empirical reference value with the largest reference count, if the reference count of the empirical reference values of the selected interval is the same, the largest empirical reference value is selected as the PMTU value.

 The technical solution of the embodiment of the invention improves the accuracy of the positioning of the empirical reference value, saves the iterative step approaching the optimal PMTU, and achieves the effect of fast convergence. BRIEF abstract

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

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

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

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

FIG. 5 is a schematic diagram of a fourth process for determining a detection space according to the present invention; FIG. FIG. 6 is a schematic structural diagram of a router according to the present invention. Preferred embodiment of the invention

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

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

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

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

 Step 101: Determine a detection space according to the number of times of reference of the empirical reference value in the empirical reference table. Currently, only some empirical reference values suggested in the respective RFCs in the experience reference table do not refer to the concept of counting; and the present invention is for each empirical reference. The value sets a reference count for counting the number of uses of each empirical reference value; and can use the reference count to dynamically update the empirical reference value in the empirical reference table; wherein, the empirical reference table can be seen in Table 1:

 Experience reference table

 MTU value

 65535 RFC791

 65535 RFC 1044

 17914 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

 544 DEC standard

 512 RFC1088

 508 RFC 1042

 508 RFC1051

 296 RFC1144

 68 RFC791 only some specific empirical reference values are recommended in the RFC. For some specific environments, if some empirical reference values are used in addition to these empirical reference values, these common empirical reference values can be added to the experience reference table. , and count its reference count;

 Step 102: Determine a PMTU value according to the foregoing detection space.

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

 Wherein, at initialization, the reference count value may 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 one.

 Using the above method, the accuracy of the empirical reference value is improved, and the iterative steps approaching the optimal PMTU are saved, and the fast convergence effect is achieved.

 The present invention combines a hierarchical detection algorithm based on an empirical reference table to analyze the use of reference counting, in which no network packet loss is considered; an initial iteration point is selected at the beginning of the detection, and a reference count is selected in the empirical reference table. The maximum empirical reference value is used as the initial value of the PMTU; then the message is sent as the message length, if the transmission is successful, the selection is made) the message is sent with the highest empirical reference value until the transmission fails; if the transmission fails, the selection reference count is decremented. The largest empirical reference sends a message until the transmission is successful. The path MTU value can be obtained faster by the above method.

The specific implementation process is as follows: Assume that the initial empirical reference value array is MO, Ml, M2, Mn; MO, Ml, M2, ..., Mn are generally the empirical reference values listed in Table 1; experience in the array Reference values from small to large Sorting sequentially, and initializing the threshold value Min=M0, Max=Mn; Selecting the Mi with the largest reference count from the array as the initial value of the PMTU, see Figure 2, as the upper limit of the packet length, encapsulating the message, will not fragment The (Don't Fragment, DF) flag is set and sent.

 If you receive an Internet Control Message Protocol (ICMP) message from the gateway that requires "segmentation but DF is not set", the next MTU value of the gateway is smaller than the current PMTU value. Assume that the MTU value of the next hop of the gateway carried in the returned ICMP message is Mu, and the minimum empirical reference value Mj in the empirical reference value larger than Mu is found as the new Max, then between [MO, Max] Select a bow | use the highest empirical reference value Mi as the new PMTU value, see Figure 3. If there is no MTU value of the next hop of the gateway in the reply (some gateways do not support it), then directly assign Max=Mi, see Figure 4.

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

 In this way, after finding the new PMTU value, send the message again, and change the values of Min and Max again, until the two are adjacent values in the empirical reference value array, that is, there is no other empirical reference between the two. The value is up; and the length of the message is sent successfully, and the Max length packet is sent.

 Wherein, when selecting an empirical reference value with the largest reference count, if the reference count of the empirical reference values in the selected area of the array is the same, the empirical reference value is selected to be the largest.

 Hierarchical 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 the layered detection, which is not described in detail in the present invention.

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

 Because the MTU value of the router is generally not changed frequently in real life, even if it is changed, the scope of the change is not large, and it usually changes between some certain values. Therefore, the more times the PMTUD is performed, the faster the convergence of the algorithm using the reference count is; Generally, the decrement method and the increment method are used, and the time complexity is 0 ( η ), even if the dichotomy method is used to find the time complexity is 0 (logN); and the time complexity after using the reference count is less than 0 (logN).

Suppose the empirical reference value array is MO, Ml, ..., M99; the reference count of each empirical reference value They are 0, 1 , 0, ..., 0, 7, 9, 0, ..., 0, 2; where Ml has a reference count of 1, M59 has a reference count of 7, and M60 has a reference count of 9. , M99 has a reference count of 2, and other empirical reference values have a reference count of 0. The final initial detection space is [M59, M60], and the results of the number of packets sent 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 unnecessary detection packets and improves the convergence speed.

 Number of times of sending unwanted probe packets under different algorithms

如图 6所示， 为本发明路由器的结构示意图， 上述路由器包括空间确定 模块 61和 PMTU确定模块 62; 其中， 空间确定模块用于根据经验参考表中 经验参考值的引用次数确定探测空间； 路径最大传输单元（PMTU )确定模 块用于根据上述探测空间确定 PMTU值。

As shown in FIG. 6 , which is a schematic structural diagram of a router according to the present invention, the router includes a space determining module 61 and a PMTU determining module 62. The space determining module is configured to determine a detecting space according to a reference number of empirical reference values in an empirical reference table; A Maximum Transmission Unit (PMTU) determination module is operative to determine a PMTU value based on the detection space described above.

 The space determining module may include an initial determining unit and an iterative determining unit. The initial determining unit is configured to select, in the empirical reference table, an empirical reference value with the largest count as the initial value of the PMTU, and use the initial value of the PMTU as the text length. Sending the text; the iterative determining unit is configured to: if the message is successfully sent, incrementally select the empirical reference value with the largest reference count to send the message until the message fails to be sent; if the message fails to be sent, the empirical reference with the largest selection reference count is decremented. The value is sent until the packet is sent successfully. The path maximum transmission unit (PMTU) determining module is further configured to select an empirical reference value having the largest reference count in the foregoing detection space as the foregoing PMTU value.

Preferably, the initial determining unit may be further configured to select an empirical reference value MO, Ml, .., Mn from the empirical reference table to form an array of empirical reference values, sort the empirical reference values, and initialize the threshold 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 value of PMTU, and use the above initial PMTU value as the message length The upper limit encapsulates the packet and sends the encapsulated packet. The iterative determining unit may be further configured to: if the packet fails to be sent, and the received MTU value of the next hop of the gateway carried in the ICMP packet from the gateway For Mu, find the minimum empirical reference value Mj among the empirical reference values larger than Mu as the new Max, and select an empirical reference value Mi with the largest reference count between [MO, Mj] as the new PMTU value; If the packet fails to be sent, and the received ICMP message from the gateway does not carry the MTU value of the next hop of the gateway, the value of Max=Mi is directly assigned, and a reference count is selected between [MO, Mi]. The empirical reference value Mi is used as the new PMTU value; if the message is sent successfully, an empirical reference value with the largest reference count is selected as the PMTU value between [Mi, Mn], and the value of Min=Mi is assigned; and the new PMTU value is selected. After that, the message is sent again, and the values of Min and MAX are changed again until the two are adjacent to each other in the empirical reference value array.

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

 In addition, the iterative determining unit is further configured to select the largest empirical reference value as the PMTU value if the reference count of the empirical reference values of the selected interval is the same when selecting an empirical reference value with the largest reference count.

 For the process of determining the detection space by the space determining module, refer to FIG. 2 to FIG. 5, and details are not described herein again. The router determines the detection space by the space determination module, and then the PMTU determination module selects the empirical reference value with the largest reference count as the PMTU value; the router uses the reference count to greatly reduce the number of the useless detection packets, and improves the convergence speed, and The ^"determination bit for the empirical reference value has been improved.

One of ordinary skill in the art will appreciate that all or a portion of the above steps may be accomplished by a program that instructs the associated hardware, such as a read-only memory, a magnetic disk, or an optical disk. Alternatively, all or part of the steps of the above embodiments may also be implemented using one or more integrated circuits. Correspondingly, each module/unit in the foregoing embodiment may be implemented in the form of hardware, or may be implemented in the form of a software function module. The invention is not limited to any specific form of combination of hardware and software. The above embodiments are only intended to illustrate the technical solutions of the present invention and are not to be construed as limiting the invention. A person skilled in the art should understand that the technical solutions of the present invention may be modified or equivalent, without departing from the spirit and scope of the present invention, and should be included in the scope of the claims of the present invention.

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

Claims

Claim  A method for implementing Path Maximum Transmission Unit (PMTU) detection, the method comprising: determining a detection space according to a reference number of empirical reference values in an empirical reference table;  A PMTU value is determined based on the probe space.  2. The method for implementing path maximum transmission unit detection according to claim 1, wherein the determining the detection space according to the reference number of empirical reference values in the empirical reference table comprises: selecting an empirical reference with the largest reference count in the empirical reference table The value is taken as the initial value of the PMTU, and the initial value of the PMTU is used as the length of 4 艮;  If the packet is sent successfully, the packet with the highest reference value is incremented to send the packet until the packet fails to be sent. If the packet fails to be sent, the packet with the highest reference number of the reference count is sent down until the packet is sent. Success  The determining the PMTU value according to the detection space includes:  The empirical reference value with the largest reference count in the detection space is selected as the PMTU value.  The method for implementing path maximum transmission unit detection according to claim 2, wherein the empirical reference value having the largest reference count is selected as the initial value of the PMTU in the empirical reference table, and the initial value of the PMTU is used as the message. The length of the sent message includes:  Selecting the empirical reference values MO, Ml, ..., Mn from the empirical reference table to form an array of empirical reference values, sorting the empirical reference values, and initializing the critical values Min=M0, Max=Mn; The value of the value is selected as the initial value of the PMTU, and the initial PMTU value is used as the upper limit of the packet length to encapsulate the packet, and the encapsulated packet is sent;  If the message is sent successfully, the message is sent with the empirical reference value with the largest reference count, until the message fails to be sent; if the message fails to be sent, the empirical reference value with the largest reference count is sent down, until the message is sent. The successful sending of the text includes: If the message fails to be sent, and the maximum transmission unit (MTU) value of the next hop of the gateway carried in the received Internet Control Message Protocol (ICMP) message from the gateway is Mu, then the experience is greater than that of Mu. The minimum empirical reference value Mj in the reference value is taken as the new Max, and an empirical reference value Mi with the largest count is selected between [MO, Mj] as the new PMTU value; If the packet fails to be sent, and the received ICMP message from the gateway does not carry the MTU value of the next hop of the gateway, directly assign Max=Mi and select a bow between [MO, Mi]. Use the most empirical reference value Mi as the new PMTU value;  If the message is sent successfully, select an empirical reference value with the highest reference count between [Mi, Mn] as the PMTU value, and assign the value Min=Mi;  After selecting the new PMTU value, send the message again and change the values of Min and MAX again until the two values are adjacent in the empirical reference array.  The method for implementing the path maximum transmission unit detection according to claim 3, wherein after the determining the PMTU value according to the detection space, the method further includes:  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.  The method for implementing path maximum transmission unit detection according to claim 3, wherein the method further comprises:  When selecting an empirical reference value with the largest reference count, if the reference count of the empirical reference values of the selected interval is the same, the largest empirical reference value is selected as the PMTU value.  6. A router, the router comprising:  a space determination module, configured to: determine a detection space according to a reference number of empirical reference values in an empirical reference table;  A Path Maximum Transmission Unit (PMTU) determination module is configured to: determine a PMTU value based on the detection space.  7. The router according to claim 6, wherein  The space determining module includes: The initial determining unit is configured to: select an empirical reference value with the largest reference count as the initial value of the PMTU in the experience reference table, and send the initial value of the PMTU as a length of 4 ;; and an iterative determining unit, set to: If the packet is sent successfully, the packet with the highest reference value is incremented to send the packet until the packet fails to be sent. If the packet fails to be sent, the packet with the highest reference number of the reference count is sent down until the packet is sent. success; The path maximum transmission unit (PMTU) determining module is further configured to: select an empirical reference value having the largest reference count in the detection space as the PMTU value.  8. The router according to claim 6, wherein  The initial determining unit is further configured to: select an empirical reference value M0, Ml, .., from the empirical reference table to form an array of empirical reference values, sort the empirical reference values, and initialize the critical value Min=M0, Max = Mn; selecting the empirical reference value Mi with the largest reference count from the empirical reference value array as the initial value of the PMTU, and using the initial value of the PMTU as the upper limit of the packet length to encapsulate the packet, and sending the encapsulated packet;  The iterative determining unit is further configured to: if the message fails to be sent, and the received maximum transmission unit (MTU) value of the next hop of the gateway carried in the Internet Control Message Protocol (ICMP) message from the gateway is Mu, then find the minimum empirical reference value Mj among the empirical reference values larger than Mu as the new Max, and select an empirical reference value Mi with the largest reference count between [MO, Mj] as the new PMTU value; If the transmission fails, and the received ICMP message from the gateway does not carry the MTU value of the next hop of the gateway, directly assign Max=Mi, and select a maximum reference count between [MO, Mi]. The empirical reference value Mi is used as the new PMTU value; if the message is sent successfully, an empirical reference value with the largest reference count is selected as the PMTU value between [Mi, Mn], and the value of Min=Mi is assigned; and the new PMTU value is selected. After that, send the message again and change the values of Min and MAX again until the two are adjacent to each other in the empirical reference array.  9. The router according to claim 8, wherein the router further comprises:  An update module, configured to: after determining the PMTU value according to the detection space, if the PMTU value is an empirical reference value in an experience 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.  10. The router according to claim 8, wherein  The iterative determining unit is further configured to: when selecting an empirical reference value having the largest reference count, if the reference count of the empirical reference values of the selected interval is the same, the largest empirical reference value is selected as the PMTU value.