CN100450037C - A method and device for implementing IP packet load sharing - Google Patents

Abstract

This invention relates to a method and a device for realizing sharing of IP message load, in which, the method includes: utilizing the IP address of a message source, target IP address and an exclusive identified field identifying a part of a message as the key of the load sharing hash algorithm based on the data flow to get the result of digit corresponding to the load sharing path number, taking the result as an index to look for the corresponding load sharing path to transmit the IP message, which integrates the advantages of the load sharing algorithms based on data flow and messages to share messages to all of the sharing paths both multiple data flows and a single data flow.

Description

A method and device for implementing IP packet load sharing

technical field

The present invention relates to the field of communication technology, in particular to a method and device for implementing IP message load sharing.

Background technique

With the increasing popularity of network applications and the increasing scale of the network, the amount of information that needs to be transmitted on the Internet has greatly increased. For routers, they need to provide routing and forwarding functions for a large number of packets. At this time, the load capacity and performance of routers become a practical problem that must be faced: in the case of increased network traffic, or even interface failures How can the router still provide reliable and high-quality services? One of the feasible methods is load sharing. The so-called load sharing is a technology that allows the use of multiple paths to a given destination address. These paths may come from static routes or dynamic routing protocols. A load sharing network is shown in Figure 1.

As shown in Figure 1, the user needs to access the remote server. After the data flow queries the routing table of router A, it finds two paths: A-B-D and A-C-D. At this time, the data traffic is evenly distributed to the two paths through load sharing processing, so the traffic on a single path is reduced to half for the case of no load sharing, which greatly eases the bearing capacity of routers B and C.

In addition, load sharing is also used on the trunk. Trunk is a technology that aggregates multiple physical ports together to form an aggregation group, realizes the sharing of outgoing and incoming loads among member ports, and provides higher connection reliability at the same time. Each trunk port can be configured with the same IP address, that is, it can be used as an actual port logically, and the data flow is evenly distributed to different physical ports in the trunk group through load sharing, so as to reduce the port load capacity. A typical networking is shown in Figure 2.

It is not difficult to find that, regardless of the load sharing of multiple routes or the load sharing of trunks, in order to maximize the load capacity and performance of shared links and make full use of network resources, it is necessary to evenly share data traffic as much as possible to each link, so the choice of a good load sharing algorithm becomes the key.

There are generally two basic algorithms for load sharing: data flow-based load sharing and packet-based load sharing. Load sharing based on data flow is to use the specific information contained in the data flow to distribute packets. The most common way is for routers to distribute packets based on source address & destination address pairs: assuming that there are N paths to the same host, the destination address Under the same circumstances, all packets whose source address is the address of visitor 1 go through the first path, all packets whose source address is the address of visitor 2 go through the second path..., and so on, the source address is visitor All packets of address N go through the Nth path.

For IP messages, the source IP address & destination IP address of the message are used as the key for hash processing. The simplest hash algorithm is to use the source IP and destination IP to perform XOR operation, and then perform multiple times on the result of 32bit length In the halved XOR operation, the length of the result is halved after each halved XOR operation. The number of halved XOR operations is related to the bit length of the final hash result to be obtained. For example, if you need to obtain a 4-bit hash result, you need to halve the XOR 3 times. Finally, the hash result is used as the sharing link identifier to select the corresponding load sharing link to forward the message.

The above sharing algorithm is briefly described as follows:

key1 = source IP address,

key2=destination IP address,

key1 XOR key2=key',

key'_H16 XOR key'_L16=key",

key”_H8 XOR key”_L8=key”’,

key"'_H4 XOR key"'_L4=key"",

The lower 4 bits of key"" are used as the final result of the hash

The detailed flow of the above operations is shown in FIG. 3 . For a given source address and destination address pair, only one path can be selected even if there are multiple available paths. If there is only one flow, only one sharing link will go, and load sharing cannot be performed at all. In an actual environment, the traffic to each destination address may vary greatly, and packets to a certain destination address always use the same path. This working method may lead to unbalanced load sharing.

Packet-based load balancing means that the router sends a packet with the destination address A through the first path, and sends a second packet with the destination address A (the same destination address) through the second path.

The realization idea of the message-based load sharing algorithm is to allocate a counter for each route or trunk interface that needs to be load-sharing. Every time a message is received, the corresponding counter is incremented by 1, and each corresponding load sharing is polled according to the counter value. Paths forward packets from corresponding sharing paths in order to achieve load sharing.

The disadvantage of this method is that a counter needs to be allocated for each route or trunk interface that needs to be load-balanced, and there are often a large number of routes on the router, which will lead to the allocation and management of a large number of counters, resulting in a serious waste of storage resources. In addition, frequent operations on the counter will also occupy a large amount of memory access bandwidth and affect forwarding performance.

Contents of the invention

The purpose of the present invention is to provide a method and device for implementing IP message load sharing, which solves the unbalanced sharing problem of the load sharing algorithm based on data flow and the serious waste of storage resources of the message-based load sharing algorithm and affects the forwarding performance question.

The purpose of the present invention is achieved through the following technical solutions:

A method for implementing IP packet load sharing, comprising:

Use the source IP address of the message, the destination IP address and the identification field that uniquely identifies a message as the key in the hash calculation of the load sharing based on the data flow, perform the hash calculation operation, and obtain the result of the number of digits related to the number of load sharing paths;

Using the result as an index, look up the corresponding load sharing path in the sharing link table corresponding to the route;

Use the found load balancing path to forward IP packets.

The identification field only performs the corresponding hash operation with the hash calculation result of the same number of digits.

The value of the identification field is increased by 1 each time a message is sent.

The identification field is identification information in the packet header.

A device for implementing IP message load sharing, comprising:

An identification field acquisition module, configured to acquire an identification field that uniquely identifies a message in the message;

The load sharing calculation module is used to carry out the hash calculation operation using the message source IP address, the destination IP address and the identification field as the key in the hash calculation to obtain the load sharing path; it further includes: a load sharing hash calculation sub-module for The source IP address of the message, the destination IP address and the identification field are used as the key to carry out the hash calculation operation, and the result of the number of digits related to the number of load sharing paths is obtained; the load sharing path search sub-module is used to use the result obtained by the hash algorithm operation as The index looks up the corresponding load sharing path in the sharing link table corresponding to the route;

The packet forwarding module is configured to forward the IP packet according to the load sharing path obtained by the load sharing calculation module.

The device is set in the router.

As can be seen from the technical solution provided by the present invention above, the present invention introduces the unique identifier of the IP message in the sharing hash algorithm based on the data flow, which is equivalent to introducing the characteristics of the load sharing algorithm based on the message, that is, when the same For a data stream, when the source address and destination address of the message are unchanged, the hash result will also change continuously according to the 16-bit identifier carried by the message, so that the messages of the same data stream can be evenly shared to all on the link. At the same time, because the identifier carried by the packet itself is used, there is no need to allocate counters for each route or trunk interface that needs to be load-balanced, which greatly reduces the waste of storage resources and does not affect the forwarding performance due to frequent memory access.

Therefore, the present invention realizes the advantages of both the load sharing algorithm based on the data stream and the load sharing algorithm based on the message, and the message can be evenly shared on all sharing links for the situation of multiple data streams and a single data stream. Moreover, the algorithm is simple to implement, does not occupy and access a large amount of storage space, and has no impact on forwarding performance.

Description of drawings

FIG. 1 is a schematic diagram of a load sharing network in the prior art;

FIG. 2 is a schematic diagram of trunk networking in the prior art;

Fig. 3 is the implementation flow diagram of prior art flow-by-flow hash algorithm;

Fig. 4 is each field in IP datagram format and header;

Fig. 5 is a flow chart of the operation of an embodiment of the method of the present invention;

Fig. 6 is a schematic diagram of a module of an embodiment of the device of the present invention.

Detailed ways

The core idea of the present invention is to provide a method and device for implementing IP message load sharing, which integrates data flow-based and message-based load sharing algorithms, and introduces a data packet uniquely identified in the IP message header when performing hash calculation. The 16-bit identification information, for the case of multiple data streams or a single data stream, can make the message evenly distributed to all sharing links.

The IP datagram format and each field in the header are as shown in Figure 4, and each field is described as follows:

Version: Indicates the version of the IP protocol, usually 4 and 6. Figure 4 is the IPV4 packet format.

Header length: Indicates the number of 32-bit words occupied by the IP header, including possible options.

Service type: including a 3bit priority subfield, 4bit TOS (service type) subfield and 1bit unused bit, but must be set to 0. 4bit TOS respectively represent: minimum delay, maximum throughput, highest reliability and Minimum fee.

Total length: refers to the length of the entire IP datagram, in bytes.

Identification field: uniquely identifies each datagram sent by the host, which is the 16-bit identification field used below.

Fragment Offset: When a packet needs to be fragmented, it identifies the location where the fragment offsets the original datagram.

Time to live: Set the maximum number of routers that a datagram can pass through, and it specifies the time to live for a datagram.

Protocol: identifies the type of high-layer protocol carried by this IP packet.

Header checksum: It is the checksum code calculated according to the IP header. It does not perform calculations on the data following the header.

Source IP address and destination IP address: identify the starting address of the packet and the final destination address of the packet.

Optional: It is a variable-length optional information in the datagram. These options are rarely used, and not all hosts and routers support these options.

The 16-bit identification field uniquely identifies each datagram sent by the host. Usually, the value of this identification field will increase by 1 each time a message is sent. This identifier is originally used to determine the fragment reassembly of the same packet by the same identifier at the destination when the IP packet is fragmented.

Here, the identifier is used to uniquely identify the characteristics of each message, instead of the distribution counter based on the load sharing of the message, and the identifier, the source IP address and the destination IP address of the message are used together as the key of the hash algorithm, and the hash algorithm is improved again , the easiest way can still be an XOR operation, for example:

key1 = source IP address,

key2=destination IP address,

key3 = 16-bit identifier,

key1 XOR key2=key',

key'_H16 XOR key'_L16 XOR key3=key",

key"_H8 XOR key"_L8=key'",

key'"_H4 XOR key'"_L4=key"",

The lower 4 bits of key"" are used as the final result of the hash. Finally, the hash result is used as the sharing link identifier, and the corresponding load sharing link is selected to forward the message.

The operation flow of an embodiment of the method of the present invention is shown in FIG. 5 . Assuming that there are 16 load sharing paths in total, the final result is obtained when the result of 4 bits is obtained. The specific operation steps are as follows:

Step 1: Take the source IP address of the message as HASH_key1, take the destination address of the message as HASH_key2, and take the 16-bit identifier of the message as HASH_key3;

After the router receives the packet, before assigning the route, in order to realize the load sharing, it needs to carry out the load sharing calculation, first obtain the source IP address and the destination address of the packet. Take the source IP address of the message as HASH_key1, take the destination address of the message as HASH_key2, and take the 16-bit identifier uniquely identifying the message in the header of the message as HASH_key3;

Step 2: Perform XOR operation on HASH_key1 and HASH_key2 to get the result of 32-bit length as HASH_key';

Generally, the source IP address and destination IP address of the message are both 32 bits. When performing the hash algorithm, since HASH_key3 is a 16-bit field, the XOR operation performed for the first time is the XOR operation of HASH_key1 and HASH_key2 to obtain a The result of 32-bit length is denoted as HASH_key';

Step 3: Take the high 16-bit data of HASH_key’ and perform XOR operation with the low 16-bit data to get the 16-bit length result, and then perform XOR operation with HASH_key3 again to get the 16-bit length result as HASH_key”;

The 32-bit length result HASH_key' obtained by XORing the above HASH_key1 and HASH_key2 is XORed with the upper 16-bit data and the lower 16-bit data to obtain a 16-bit length result. Since HASH_key3 is a 16-bit field, the above The obtained 16-bit length result is XORed with HASH_key3 again to obtain another 16-bit length result, which is recorded as HASH_key”;

Step 4: Take the high 8-bit data of HASH_key” and perform XOR operation with the low 8-bit data, and get the 8-bit length result as HASH_key’”;

Step 5: Take the high 4-bit data of HASH_key’” and perform XOR operation with the low 4-bit data, and get the 4-bit length result as HASH_key””, which is the final result of hash;

Since there are 16 load sharing paths in total, the 4-bit result obtained is the final result;

Step 6: Use the value of the HASH_key"" as an index, search for the corresponding load sharing path in the sharing link table corresponding to the route, and use the found path to forward the message.

The present invention provides a device for realizing load sharing of IP packets. The device is arranged in a router. The module schematic diagram of an embodiment thereof is shown in FIG. 6 , including: an identification field acquisition module, a load sharing calculation module and a message forwarding module .

The identification field acquiring module is configured to acquire an identification field that uniquely identifies a message in the message.

The load sharing calculation module is used to use the message source IP address, destination IP address and identification field as keys to obtain a load sharing path. This module further includes:

The load sharing hash calculation sub-module is used to use the source IP address, destination IP address and identification field of the message as the key to perform hash calculation operations, and obtain the result of the number of bits related to the number of load sharing paths.

The load sharing path search submodule is used to use the result obtained by the hasn algorithm operation as an index to search for the corresponding load sharing path.

The packet forwarding module is configured to forward packets according to the obtained load sharing path.

In summary, because the method of the present invention introduces the unique identifier of the IP message in the sharing hash algorithm based on the data flow, it is equivalent to introducing the characteristics of the load sharing algorithm based on the message, that is, when the same data flow, When the source address and destination address of the message are unchanged, the hash result will also change according to the 16-bit identifier carried by the message, so that the messages of the same data flow can be evenly distributed to all sharing links. At the same time, because the identifier carried by the packet itself is used, there is no need to allocate counters for each route or trunk interface that needs to be load-balanced, which greatly reduces the waste of storage resources and does not affect the forwarding performance due to frequent memory access.

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 skilled in the art within the technical scope disclosed in the present invention can easily think of changes or Replacement should be covered within the protection scope of the present invention. Therefore, the protection scope of the present invention should be determined by the protection scope of the claims.

Claims (6)

1. A method for implementing IP message load sharing, characterized in that, comprising: Use the source IP address of the message, the destination IP address and the identification field that uniquely identifies a message as the key in the hash calculation of the load sharing based on the data flow, perform the hash calculation operation, and obtain the result of the number of digits related to the number of load sharing paths; Using the result as an index, look up the corresponding load sharing path in the sharing link table corresponding to the route; Use the found load balancing path to forward IP packets. 2. The method for implementing IP packet load sharing according to claim 1, wherein the identification field is only subjected to a corresponding hash operation with the hash calculation result of the same number of digits. 3. The method for implementing IP packet load sharing according to claim 1, wherein the value of the identification field is increased by 1 each time a packet is sent. 4. A method for implementing IP packet load sharing according to any one of claims 1 to 3, wherein the identification field is identification information in the packet header. 5. A device for implementing IP message load sharing, characterized in that, comprising: An identification field acquisition module, configured to acquire an identification field that uniquely identifies a message in the message; The load sharing calculation module is used to carry out the hash calculation operation using the message source IP address, the destination IP address and the identification field as the key in the hash calculation to obtain the load sharing path; it further includes: a load sharing hash calculation sub-module for The source IP address of the message, the destination IP address and the identification field are used as the key to carry out the hash calculation operation, and the result of the number of digits related to the number of load sharing paths is obtained; the load sharing path search sub-module is used to use the result obtained by the hash algorithm operation as The index looks up the corresponding load sharing path in the sharing link table corresponding to the route; A message forwarding module, configured to forward IP messages according to the load sharing path obtained by the load sharing calculation module. 6. The device for implementing IP packet load sharing according to claim 5, characterized in that the device is set in a router.

Images