CN100417138C - A method of load sharing - Google Patents

Abstract

The invention discloses a method for load sharing. When the next-hop path of the message received by the communication device is more than one, the number of required flows is obtained according to the maximum number of next-hop supported paths supported by the communication device, and is Each stream is assigned a stream ID. And each flow identifier value uniquely corresponds to a determined next-hop path, so that the route can directly select the path identifier without reading the threshold value to determine the corresponding path identifier, thereby avoiding the access to the same block caused by reading the threshold value Performance bottlenecks caused by memory. Therefore, the load sharing method of the present invention is suitable for high-speed equipment. At the same time, when the next-hop path increases or decreases due to the change of the route, the corresponding relationship between the flow identifier and the path can be changed by changing the corresponding relationship between the flow identifier and the path according to the principle of changing the least number of paths according to the flow identifier. , a large number of streams caused by the out-of-sequence problem, in addition, the present invention can also solve the non-equal load sharing problem.

Description

A method of load sharing

technical field

The invention relates to the communication field, in particular to a load sharing method.

Background technique

In an actual network, due to the complex topological relationship between nodes, there are often multiple paths to a destination. Multiple paths may be reachable, and they are equal to each other, that is, they all form routes. In this way, there will be multiple equal-cost routes to a destination.

As shown in Figure 1, there may be three paths from node R1 to R8. If the routing calculation treats these three paths as equal-cost routes, then at node R1, a packet faces three choices.

The first road: R1-》R2-》R3-》R4-》R8

The second road: R1-"R5-"R8

The third road: R1-》R6-》R7-》R8

For online traffic, sometimes in order to achieve link backup or expand traffic, a sharing method is also adopted, that is, there will be multiple paths to the same place, and traffic exists on multiple paths, and traffic is shared between each other , that is, load sharing. The first goal of load sharing is to balance the traffic as much as possible, so that multiple links can fully play their roles.

Load sharing occurs in many places. For example, on our most common IP router, or on the switching device of the label switching path (LSP).

In the next-generation network, the solution of multi-network integration is adopted, that is, multiple services are transmitted on one network. There may be one or more paths for the same next-hop router. If the same flow is allocated to different On the path, the concept of the same flow is a collection of data packets that come from the same source and go to the same destination, and have some common characteristics, because the number of nodes passed by different paths is different, and the distance of the transmission link passed Different nodes have different congestion levels and buffer sizes, which will cause different delays on different paths. At this time, the arrival time of the same flow at the destination may be different, and may be out of order.

For traffic transmitted using the Transmission Control Protocol (TCP), out-of-sequence will be considered as packet loss at the destination node, and retransmission will occur, resulting in increased network traffic, and in severe cases, TCP disconnection will occur. At the same time, if it is a real-time service transmitted, such as Internet voice communication (Voice Over IP; VOIP), for end users, the voice quality will be unbearable, and there will be intermittent or unclear phenomena.

Therefore, in the next generation network, when routers forward, it is a very important feature to use the same path to forward the same flow. Therefore, the second requirement of load sharing is that the same stream cannot be out of order.

At present, the existing technology is a method of realizing load sharing according to flows, which utilizes the hash threshold algorithm proposed by D. Thaler. The hash threshold algorithm is to hash the field in the packet header, and the obtained hash value is used as the identifier of the flow. For IP packets, the source IP address and destination IP address are generally used for hashing. During load sharing, the Hash algorithm can use the CRC16 algorithm.

When load sharing, set multiple thresholds for the Hash value. For example, if there are 8 equal-cost routes, and the Hash value is 0 to 65535, then divide 0 to 65535 into eight equal parts. In the first way, if the Hash value falls within the nth interval, take the nth way.

When it is necessary to add paths due to routing changes, modify the threshold at the same time, for example, from 3 paths to 4 paths, then divide 65535 by 4, and then multiply by n to get the interval of the nth path. described as follows:

Suppose there are 3 equal-cost routes (3 next hops), and the threshold is set as follows:

Now add a next hop to change to 4 next hops. At this time, the changes in the allocation relationship are as follows:

In this way, load balancing according to flows is realized.

In the prior art, when there are many next hops for load sharing, because the Hash threshold must be read every time, there will be access competition for a certain fast storage area in the high-speed device, resulting in a bottleneck, so the high-speed device It is difficult to achieve high performance. At the same time, due to routing changes, when the next hop needs to add and delete paths, a large number of flows will change paths, resulting in potentially unnecessary large amounts of disorder. This problem is detailed below.

The flow identification (ID) range of changing the next hop is as follows, and the gray part in the figure is the part of changing the path.

The total fraction of streams that change paths is:

((65535-49151)+(43690-32767)+21845-16383))/65536＝50%

But when we add a path (next hop), at most 25% of the traffic only needs to change the path to this path, that is to say, 50%-25%=25% of the traffic does not need to change the path.

Changing the path means that during the switching period, these streams may appear out of order. We can see from the above examples that, using this method, in addition to the traffic that needs to be switched, a large proportion of traffic is switched by mistake, resulting in unnecessary disorder. Out-of-order will lead to retransmission for TCP traffic, and for voice, etc., it means quality degradation. This problem also exists when reducing the path (next hop).

Contents of the invention

In view of this, the main purpose of the present invention is to provide a method of load sharing, so that while realizing load sharing, the processing performance of high-speed devices can be optimized, and at the same time, the problem of large-scale error and out-of-sequence caused by path changes can be solved .

The present invention provides a method for load sharing, which specifically includes the following steps,

A. When the next hop path of the message received by the communication device is more than one, the number of required flows is obtained according to the maximum number of supported next hop paths supported by the communication device, and a flow identifier is assigned to each flow, so The value of the number of flows mentioned above is greater than or equal to the number of the maximum number of paths supported by the next hop.

B. The communication device makes each flow uniquely correspond to a determined next-hop path according to the destination address of the message and the flow identifier;

C. The communication device performs load sharing and forwarding of the message according to the next-hop path. The value of the number of streams in step A is a common multiple of the maximum number of supported paths from 1 to the next hop.

The quantity value of the flow in the step A, according to the error requirement of the traffic distribution ratio, takes a value close to the integer power of 2 that is the common multiple of the maximum supported path number of the next hop.

The flow identifier is obtained through a hash algorithm according to the content of the field of the message header.

The fields of the message header include source address, destination address, message lifetime, source port number, destination port number, protocol type, or any combination thereof.

Described step B specifically comprises,

B1. A load sharing table is set in the routing table of the route, and the load sharing table includes a flow identifier and a next hop identifier;

B2. The communication device searches for a next-hop path in the load sharing table according to the destination address of the message and the flow identifier.

In the correspondence between the flow identifier and the next-hop path in step B, the next-hop path corresponds to one or more flow identifiers according to the proportion of traffic that needs to be shared by different paths.

When a path needs to be deleted or added, the corresponding relationship between the flow identifier and the path is modified according to the ratio.

It also includes changing the corresponding relationship between the flow identifier and the path by changing the number of paths to be the least according to the flow identifier.

When the maximum number of paths supported by the next hop changes, the number of flows must be recalculated to obtain the flow ID, and the load sharing table corresponding to the load sharing flow ID and the path must be initialized.

It can be seen from the above-mentioned technical solution provided by the present invention that limited flow identifiers are obtained by performing Hash on the data message, and each flow identifier value uniquely corresponds to a certain next-hop path, so that the route can directly select the path identifier, The corresponding path identifier is determined without reading the threshold value. In this way, the performance bottleneck of high-speed devices caused by accessing the same block of memory caused by the read threshold is avoided. Therefore, the load sharing method of the present invention is suitable for high-speed equipment. At the same time, when the next hop path increases or decreases due to the change of the route, the path of the flow identifier can be changed by changing the path of the flow identifier according to the principle of changing the least number of paths. The problem of out-of-sequence occurs in a large number of streams, and at the same time, the present invention can also solve the problem of non-equal load sharing.

Description of drawings

Fig. 1 is the topological schematic diagram of the router in the existing network;

Fig. 2 is method flowchart of the present invention;

Fig. 3 is a schematic diagram of a method according to an embodiment of the present invention.

Detailed ways

The invention provides a load sharing method, the core idea of which is to eliminate the process of reading the threshold value and improve the processing performance of the high-speed equipment through the design of the data structure. And when the number of paths changes, the control of changing the precise ratio of path routing can completely or within an acceptable range eliminate the problem of misordering.

In order to make the purpose, technical solutions and advantages of the present invention more clearly, the present invention will be described in further detail below in conjunction with the accompanying drawings and specific embodiments:

See Figure 2,

Step 201. When the communication device receives more than one next-hop path for the message, obtain the number of required flows according to the maximum supported number of next-hop paths supported by the communication device, and assign a flow identifier to each flow.

In the present invention, the input value of the Hash calculation is the content of the field in the data message header, the field in the message header can be the content of the field in the message header, and the output value is a flow identifier. The fields of the message header include but are not limited to one or any combination of source address, destination address, message lifetime, source port number, destination port number, protocol type.

Assuming that the data stream is divided into N, the HASH algorithm directly obtains values from 0 to N-1, and each value directly corresponds to a path.

The value of N can be selected in this way: assuming that the next hop in the routing table supports a maximum of L paths, the maximum number of paths supported by the next hop is a pre-set value, which can be set through the command line, or It can be set through the network management; if the maximum number of paths supported by the next hop changes, the maximum number of flow identifiers must be recalculated through HASH, and the load sharing table (LBT) corresponding to the load sharing flow identifier and the path must be initialized;

In order to ensure load balancing, theoretically N should be divisible by 1~L, for example, the next hop supports X effective routes, then data streams 0~N are evenly distributed to X effective routes by integer multiples. Next, let's illustrate the selection of the value of N with the maximum supported path L=3 in the next hop. When L=3, the theoretical minimum value of N should be 6, because in the example, when the next hop is 3 paths, the number of data streams is as follows: To achieve load balancing, the number of data streams should be divisible by 3; since the maximum path supported by the next hop when L is 3, when the next hop is 2 paths, the number of data streams should be divisible by 2 to achieve load balanced. Therefore, in the example, if the transmission of the entire data packet is to achieve load balancing, the value of the data flow N should be divisible by 2 and 3 at the same time, that is, when L=3, the theoretical minimum value of N should be 6. Similarly, when L=16, generally the maximum number of supported paths for the next hop will not exceed this value, that is, under normal circumstances, it is within 8, and the theoretical minimum value of N is 9×5×7×11×13 ×16, wherein 16×9×5×7 includes the cases when N=1, 2, 3, 4, 6, 8, 10, 12 or 14.

When the maximum supported load sharing path is 2 to 8, the minimum value of data flow N is as follows.

L Minimum theoretical N 2 2 3 6 4 12 5 60 6 60 7 420 8 840

From this we can see that when the value of L is larger, the minimum value of the data stream N increases rapidly, so the calculated value of N will be very large. If the computer memory is large enough, it can be designed according to this. But in practice, we can appropriately simplify it to just select a value that is several times of L as N. Because the value obtained by the Hash algorithm in high-speed equipment is generally an integer power of 2, so an integer power of 2 larger than L can be selected as N, for example, it can be approximated as follows:

L N 2 2 3 8 4 16 5 64 6 64 7 64 8 64

Step 202, the communication device makes each flow uniquely correspond to a determined next-hop path according to the destination address of the message and the flow identifier;

The next-hop path corresponding to the flow identifier in the communication device has been uniquely determined before the search. We can initialize a load sharing table in the routing table, and the load sharing table includes at least two fields of the flow identifier and the next hop identifier; the communication device according to the destination address of the message and the value of the flow identifier Determine the next-hop path in the load balancing table. It should be noted that a flow identifier uniquely corresponds to a determined next-hop path, but a determined next-hop path may correspond to one or more flow identifiers.

If it is required to distribute traffic evenly, the flow identifiers shared by each next-hop path are equally divided. If traffic is required to be allocated in different proportions on different paths, the flow identifier shared by each next-hop path is allocated in accordance with the required proportion.

When the next-hop path needs to be deleted or added due to changes in routing, manual addition and deletion of forwarding paths through the command line, or the rapid automatic discovery mechanism from the forwarding layer discovers that some of the paths are unreachable, etc., only need to be based on the above-mentioned The ratio modifies the corresponding relationship between flow identifiers and paths without changing the corresponding relationship between flow identifiers and paths according to the order of flow identifiers. In particular, we can change the corresponding relationship between the flow identifier and the path according to the flow identifier changing the least number of paths, which can effectively reduce the problem of flow disorder caused by a large number of flow changes.

Step 203, the communication device performs load sharing and forwarding of the message according to the next hop path

The following takes load sharing in IPV4 forwarding as an example to illustrate the implementation of the load sharing method of the present invention.

The IPV4 forwarding route selection is obtained by searching the FIB. The FIB is composed of a next-hop path indexed by an IP address with a mask length.

To look up the FIB table, use the destination IP address of the packet as the Key value to search a table or a tree to obtain the longest matching entry (the most accurate match, the optimal entry). For example, the destination address is 1.1.1.1, and there are two items in the routing table, one is 1.1.1.*/24, the other is 1.1.*.*/16, and the mask is marked after the slash, then the destination address will be Matches the route 1.1.1.*/24 because it is more precise than 1.1.*.*/16.

After the entry is matched, a path can be obtained, which is represented by the next hop IP address + outgoing interface, and also represented by an index (for example, using the forwarding model of the adjacency table). In the following, regardless of the above two cases , a next-hop path is uniformly identified by NH.

The logical structure of the FIB entry in the present invention is as follows,

NH Load sharing flag LF Other flag bits and table entry content Load sharing table pointer LP

Among them, the content of NH and other flag bits and entries is the same as that of the general FIB table. When LF is 0, it indicates that there are no multiple paths. The entry is the same as the general FIB, and NH is used for forwarding; when the load sharing flag LF is 1 , indicating that there are multiple paths, and the load sharing table (LBT) needs to be searched through the load sharing table pointer LP to perform load sharing.

When the load sharing flag bit LF is 1, it indicates that there are multiple paths, and load sharing needs to be performed through the load sharing table pointer LP. The load sharing table pointer LP obtains the determined next-hop path by looking up the load sharing table. The load sharing table includes three fields: destination address, flow ID and next hop ID; for example, the load sharing table is shown in the following table,

Let's take the next hop maximum supported path L=4 as an example, and the value of the corresponding data flow N is 16, so each flow identifier corresponds to a certain path. When there are 4 paths for the next hop, replace them with NH1, NH2, NH3, and NH4 respectively. In order to achieve load sharing, the data flow is evenly distributed to these 4 paths, and whether the data flow is distributed to these 4 paths in order The path has nothing to do with load balancing. For example, when there are 4 paths for the next hop, the corresponding relationship between each flow identifier and the next path can be shown in the following table,

Stream ID 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 path NH1 NH1 NH4 NH2 NH2 NH4 NH2 NH4 NH2 NH3 NH1 NH3 NH3 NH1 NH4 NH3

At the same time, we change the path according to the principle of changing the least number of paths according to the flow identifier, which can solve the problem of misordering of a large number of flows when adding or deleting load sharing paths. Let's illustrate it in detail with the above example.

When the path of the next hop in the above example changes from 4 to 3, for example, NH4 is disconnected, there are still 3 paths, namely NH1, NH2 and NH3. Flow IDs 0 to 15 need to be evenly distributed to NH1, NH2, and NH3. According to the principle of changing the least number of flow IDs, the path that needs to be changed should be to distribute the 4 flow IDs of NH4 to NH1, NH2, and NH3 as evenly as possible. That is, we need to add a flow identifier to each path from NH1 to NH3, and at the same time add a flow identifier to a path. We can choose one, for example, add two to NH1. The possible assignments after passing the changes are as follows:

Stream ID 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 path NH1 NH1 NH1 NH2 NH2 NH1 NH2 NH2 NH2 NH3 NH1 NH3 NH3 NH1 NH3 NH3

That is, the flow that originally went through NH4 is now going through NH1 to NH3 respectively, and it is relatively uniform, achieving the effect of load sharing. The ratio of the changed flow is: 4/16=25%, and there is no disorder.

When the path of the next hop in the above example is changed from 4 to 5, for example, NH5 is added, if load sharing is to be realized at this time, data flow identifiers 0 to 15 should be allocated to NH1, NH2, and NH3 as much as possible , NH4 and NH5. According to the principle of changing the least number of paths with flow identifiers, the path to be changed should be to take out a flow identifier from any three paths of NH1, NH2, NH3, and NH4 and assign them to NH5. The possible assignments after passing the changes are as follows:

Stream ID 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 path NH5 NH1 NH5 NH5 NH2 NH4 NH2 NH4 NH2 NH3 NH1 NH3 NH3 NH1 NH4 NH3

That is, one flow ID is taken from NH1, NH2, and NH4 and assigned to NH5, then the proportion of changed flows is 3/16=18.75%, and there is no out-of-sequence occurrence.

It should be noted that the corresponding relationship between each flow identifier and the next path only needs to satisfy the corresponding relationship in proportion, and does not need to be arranged in order. The proportion refers to the proportion of traffic that needs to be shared by different paths. Because in actual paths, such as TE LSP tunnels, different paths require that the proportion of traffic shared is not equal. For example, there are 3 paths NH1~NH3, which share 20%, 20%, and 60% of the traffic respectively. NH1 and NH2 are allocated 3 flow IDs each, and NH3 is allocated 10 flow IDs, so that the purpose of sharing can be achieved. Therefore, we can allocate flow IDs according to the actual needs, so as to achieve the effect of reasonable load sharing. At the same time, when it is necessary to add and delete paths due to routing changes, it is also carried out according to the above-mentioned ratio, and load sharing is realized according to the principle of changing the path with the least amount of flow identifiers, instead of assigning paths to flow identifiers sequentially, it can solve the problem of increasing the next-hop path. Or the large number of streams brought in to achieve load sharing during deletion may be out of order.

At the same time, in the above example, when the next hop path is changed from 2 to 1, it is necessary to modify all flow identifiers corresponding to the unique path and change the LF flag in the FIB table to 0.

The above is only a preferred embodiment of the present invention, but the scope of protection of the present invention is not limited thereto. Any person familiar with the technology can easily think of changes or replacements within the technical scope disclosed in the present invention. , should be covered within the protection scope of the present invention.

Claims (10)

1. A method for load sharing, characterized in that, A. When the next hop path of the message received by the communication device is more than one, the number of required flows is obtained according to the maximum number of paths supported by the next hop of the communication device, and a flow identifier is assigned to each flow. The value of the number is greater than or equal to the maximum number of paths supported by the next hop; B. The communication device makes each flow uniquely correspond to a determined next-hop path according to the destination address of the message and the flow identifier; C. The communication device performs load sharing and forwarding of the message according to the next-hop path. 2. A method of load sharing according to claim 1, characterized in that the number of flows in the step A is a common multiple of the maximum number of supported paths from 1 to the next hop. 3. A method of load sharing according to claim 1, characterized in that, the quantity value of the flow in the step A, according to the error requirement of the flow distribution ratio, is close to 1 to the maximum supported path of the next hop The value of the integer power of 2 that is the common multiple of the number. 4. The method according to claim 1, wherein the flow identifier is obtained through a hash algorithm according to the content of the header field. 5. The method according to claim 4, wherein the domain of the message header includes one or any combination of source address, destination address, message lifetime, source port number, destination port number, protocol type . 6. method according to claim 1, is characterized in that, described step B specifically comprises, B1. A load sharing table is set in the routing table of the route, and the load sharing table includes a flow identifier and a next hop identifier; B2. The communication device searches for a next-hop path in the load sharing table according to the destination address of the message and the flow identifier. 7. The method according to claim 1, characterized in that, in the corresponding relationship between the flow identifier and the next-hop path in step B, the next-hop path corresponds to the traffic ratio required to be shared by different paths One or more stream IDs. 8. The method according to claim 7, wherein when a path needs to be deleted or added, the corresponding relationship between the flow identifier and the path is modified according to the ratio. 9. The method according to claim 8, further comprising changing the corresponding relationship between the flow identifier and the path according to the principle of changing the flow identifier with the least number of paths. 10. The method according to claim 1, characterized in that when the maximum number of paths supported by the next hop changes, the number of flows must be recalculated to obtain the flow identifier, and the load sharing flow identifier must be initialized and the load balancing table corresponding to the path.

Images