CN1177437C - A method for implementing fast forwarding and supporting load sharing - Google Patents

Abstract

The present invention relates to a method for quick retransmission and load share support. Firstly, a circling chain table is set, a pointer pointing to the next output interface is additionally arranged in the data structure of each buffer information unit of a quick retransmission routing buffer table, buffered output interface information is composed of a plurality of output interface information nodes supporting holding load share, each output interface information node is generated dynamically, and the tail pointers of the output interface information nodes are connected to form a loop so as to form a circle chain table structure; firstly, a circling chain table is set, a pointer pointing to the next output interface is additionally arranged in the data structure of each buffer information unit of a quick retransmission routing buffer table, buffered output interface information is composed of a plurality of output interface information nodes supporting holding load share, each output interface information node is generated dynamically, and the tail pointers of the output interface information nodes are connected to form a loop so as to form a circling chain table structure; afterwards, the output interface information is stored in the circling chain table, and data messages are directly forwarded from corresponding output interfaces according to the output interface information of the circling chain table so as to support the load share.

Description

A method for implementing fast forwarding and supporting load sharing

technical field

The invention relates to a method for realizing fast forwarding and supporting load sharing, and belongs to the technical field of IP network communication.

Background technique

Referring to Figure 1 and Figure 2, the positions of the fast forwarding module (Fast Switch) and the load balancing module (LoadBalance) in the router are shown in the figure. The features of these two modules are independent of each other. The basic processing procedures of the fast forwarding module and the load sharing module in the existing equipment are respectively introduced below.

When the router does not enable the fast forwarding function, the received message will be directly sent to the IP layer for forwarding processing through the link layer: the message searches the routing table at the IP layer, and selects the corresponding interface to send according to the corresponding routing information . After the message is output to the link layer through the IP layer, the new link layer frame header information will be replaced, and then sent from the physical layer. After the router enables the fast forwarding function, the packets received by it will be processed as follows at the link layer: Firstly, the routing cache table (also known as: fast forwarding table) is searched. If no matching entry is found, the packet will be sent to the IP layer for the above forwarding processing. The difference is that when the message is output to the link layer through the IP layer and is about to be handed over to the physical layer, its link layer frame header and other information will be added to the routing cache table item, and then sent from the physical layer the message. In this way, when the link layer receives a message with the same characteristics as the message again (such as a message with the same destination address), it will find a matching entry when searching the routing cache table. At this point, the new message will no longer be processed at the IP layer, and its frame header information will be replaced directly according to the information stored in the routing cache table, and sent out from the corresponding output interface.

After the router enables the load sharing function, the routing table of the router will undergo the following changes: the original routing table has only one routing item to a certain address; There will be multiple routing items (refer to Figure 2, for the convenience of description, take setting three routing entries as an example, respectively named: shared route 1, shared route 2, shared route 3; they correspond to different output interfaces). When a group of IP packets with the same destination address (referred to as an IP data stream) are sequentially processed by the IP layer search route, the three sharing routes will be selected in turn, and sent out from three different output interfaces in turn, thus realizing the sharing of traffic function of

In Figure 2, the dotted line describes the general processing flow of IP packets when the fast forwarding and load sharing functions are not enabled; the middle and lower solid lines in Figure 2 describe the IP packet processing flow when the fast forwarding function is enabled The processing flow is characterized by improving the efficiency of router forwarding packets by simplifying the packet processing flow; the solid line at the top of Figure 2 describes the processing flow of IP packets when the load sharing function is enabled, which is characterized by configuring multiple Routing enables service traffic to be load-balanced by multiple links.

The router products currently on the market, including the routers developed by the applicant and the routers of most companies in the industry, do not support the load sharing feature in their fast forwarding. For example, the fast forwarding of Cisco (cisco), an industry authority, also does not support the load sharing function. Although Cisco's unique CEF forwarding (CiscoExpress Forwarding) feature can support both high-speed data forwarding and load sharing; it uses routing hierarchical indexes to speed up routing lookups. At the same time, in routers on the same platform, CEF The forwarding performance is much lower than that of fast forwarding, that is to say, the load sharing supported by CEF is not as efficient as the load sharing supported by fast forwarding.

In the prior art, when the user enables the fast forwarding module and configures multiple routes to share the load at the same time, since the data structure of the existing fast forwarding cache table only saves one piece of output interface information (see Figure 3), the router is processing The message that needs to be forwarded is carried out in the following way: when the link layer receives the first IP message of an IP flow, it will first find out that it does not save the fast forwarding cache information, and then send the message to the IP Process forwarding processing. Then, when the first load sharing route is detected, it will be forwarded according to the routing information, and at the same time, generate and add the corresponding fast forwarding route cache item (including the output interface corresponding to the IP message, the frame header information of the output interface, frame header length information, etc.). When the link layer receives the second IP message of the IP flow, since they have the same index, it will directly find the corresponding forwarding route cache information. Therefore, starting from the second packet, all packets of the IP flow will be directly pasted with the frame header information of the corresponding output interface, and sent out from the same output interface. That is to say, due to the fast forwarding, these IP packets will be forwarded from the same output interface according to the first load sharing route, resulting in the failure of routing load sharing, and the data traffic cannot be obtained according to the load sharing requirements set by users. shunt.

Figure 3 shows the data structure of the existing fast forwarding routing cache table, wherein each group of cache items corresponds to an IP flow, and each group of cache items is composed of an index item and a corresponding output interface information unit, and its characteristics The information of only one output interface is statically stored in the output interface information unit.

Contents of the invention

The purpose of the present invention is to provide a method for implementing fast forwarding and supporting load sharing, which can realize the functions of fast forwarding and load sharing at the same time by simply modifying the data structure of the existing fast forwarding routing cache table, and utilize fast Forwarding mechanism to improve the processing efficiency of load sharing.

The purpose of the present invention is achieved in that a method for realizing fast forwarding and supporting load sharing is characterized in that:

(1) Ring linked list is set: in the data structure of each cache information unit in the fast forwarding routing cache table composed of multiple cache entries, set the cache with "output interface information" and "pointing to the next output interface" Pointer"; the data structure of the "output interface information" is composed of several "output interface information nodes" that support the load sharing of the IP data flow, and each "output interface information node" is dynamically generated, and uses the "output interface information node" The tail pointers in the "Information Node" are connected to form a ring to form a circular linked list structure, and each node of the linked list corresponds to an "Output Interface Information Node";

(2) storing the output interface information in the circular linked list;

(3) The data message is directly forwarded from the corresponding output interface according to the output interface information stored in the ring list.

Each cache entry in the plurality of cache entries corresponds to an IP data flow, and each cache entry includes an index entry and a corresponding cache information unit.

The cache information unit in each cache item stores: "pointer to the next output interface" and "output interface information" composed of several "output interface information nodes".

Each of the "output interface information nodes" stores: the frame header information of the IP flow, the corresponding output interface and the tail pointer.

The processing flow in which the data message is directly forwarded from the corresponding output interface according to the output interface information stored in the ring list further includes the following steps:

(A) When initializing the system, the first "output interface information" and its "pointer to the next output interface" in the routing cache table are initially initialized as "empty";

(B) When the link layer receives the first message of a certain IP flow, it first checks its output interface information and finds that it is "empty", then transfers the message to the IP layer for processing, and selects the first message of the IP flow. A load-sharing route is forwarded; and before the interface sends a message, save the output interface information in the first node of the routing cache table, and at the same time point the node's tail pointer to itself, and "point to the next output interface's pointer" is still "null";

(C) When the link layer receives the second and subsequent packets of an IP flow, it first checks the output interface information, if it is not "null", then immediately checks the "pointing to the next output interface" If it is found to be "empty", the message will be forwarded to the IP layer for processing, and a load sharing route of the IP flow will be sequentially selected each time for forwarding; and before the corresponding interface sends the message, compare the output Whether the interface information is different from the interface information already saved in the routing cache table. If there is no identical interface information, a new node is created in the doubly linked list of the output interface information each time, and then output through the head and tail pointers of each node. Each node in the interface information is sequentially connected to form a ring; the "pointer to the next output interface" is "empty" every time when the different routes of each load sharing are not all cached in the output interface information;

(D) After all the different routes of load sharing have transmitted the packet of the IP flow once, the first packet of the second cycle of the IP flow is found before the packet is forwarded by the corresponding link layer interface. If the output interface information has been saved before, no new node will be generated; instead, the value corresponding to the tail pointer of the "output interface information" will be assigned to the "pointer to the next output interface";

(E) When the follow-up message of this IP flow arrives again, it is checked that the "pointer to the next output interface" is not "empty", that is, the current message is found directly from the output interface information corresponding to the node it points to. The output interface of the text, and replace the frame header according to the output interface information, and forward it directly from the corresponding output interface; at the same time, modify the content of "pointer to the next output interface" to the value in the node tail pointer.

The innovation key of the present invention is to modify the data structure of the cache information unit stored in the fast forwarding cache, add a "pointer to the next output interface", and modify the data structure of the "output interface information" to be supported by The IP data flow load sharing is composed of several "output interface information nodes", each of which is dynamically generated, and is sequentially connected with the tail pointers in the "output interface information nodes" to form a ring Type linked list structure; different from the previous static storage, and only one output interface information is stored; supplemented by corresponding processing methods, it can realize the characteristics of fast forwarding and support load sharing.

The invention has the advantage that while ensuring high-speed forwarding efficiency, it can make full use of network bandwidth resources to balance service flow. The method is very simple to modify the existing fast forwarding process and is easy to implement; and because the fast forwarding is executed in an interruption, the present invention has little influence on the processing efficiency of the existing fast forwarding process, and the result of theoretical analysis is: Compared with Cisco's CEF feature, the forwarding processing efficiency is higher in the case of supporting load sharing.

Description of drawings

FIG. 1 is a schematic diagram of locations of load sharing and fast forwarding features in an existing router system.

FIG. 2 is a schematic diagram of an existing processing flow of fast forwarding and load sharing of IP packets.

FIG. 3 is a schematic diagram of a data structure of an existing fast forwarding routing cache table.

Fig. 4 is a flow chart of the method for implementing fast forwarding and supporting load sharing in the present invention.

Fig. 5 is a schematic diagram of the data structure of the routing cache item in the fast forwarding routing cache table in the present invention.

Detailed ways

Referring to Fig. 4, the present invention is a kind of method that realizes fast forwarding and supports load sharing, and it comprises the following steps: (1) ring linked list is set;

(2) storing the output interface information in the circular linked list;

(3) The data message is directly forwarded from the corresponding output interface according to the output interface information stored in the ring list.

The present invention is a method for implementing fast forwarding and supporting load sharing by adopting a circular linked list. The data structure of the fast forwarding routing cache table is composed of a plurality of cache entries, wherein each group of cache entries corresponds to an IP data flow. Each group of cache items includes an index item and a corresponding cache information unit; the innovation of the present invention is that in the data structure of each cache information unit in the fast forwarding routing cache table, in addition to the cached "output interface information" , also set a "pointer to the next output interface"; and the data structure of the "output interface information" in the routing cache table is also modified to be composed of several "output interface information nodes" that support the load sharing of the IP data flow , wherein each "output interface information node" is dynamically generated, and is connected with the tail pointer in the "output interface information node" to form a circular linked list structure, and each linked list node corresponds to an "output interface information node"; It is realized with the help of corresponding message processing flow.

The data message of the present invention further includes the following steps according to the output interface information stored in the ring list and forwarded directly from the corresponding output interface:

(A) When initializing the system, the first "output interface information" and its "pointer to the next output interface" in the routing cache table are initially initialized as "empty";

(B) When the link layer receives the first message of a certain IP flow, it first checks its output interface information and finds that it is "empty", then transfers the message to the IP layer for processing, and selects the first message of the IP flow. A load-sharing route is forwarded; and before the interface sends a message, save the output interface information in the first node of the routing cache table, and at the same time point the node's tail pointer to itself, and "point to the next output interface's pointer" is still "null";

(C) When the link layer receives the second and subsequent packets of an IP flow, it first checks the output interface information, if it is not "null", then immediately checks the "pointing to the next output interface" If it is found to be "empty", the message will be forwarded to the IP layer for processing, and a load sharing route of the IP flow will be sequentially selected each time for forwarding; and before the corresponding interface sends the message, compare the output Whether the interface information is different from the interface information already saved in the routing cache table. If there is no identical interface information, a new node is created in the doubly linked list of the output interface information each time, and then output through the head and tail pointers of each node. Each node in the interface information is sequentially connected to form a ring; the "pointer to the next output interface" is "empty" every time when the different routes of each load sharing are not all cached in the output interface information;

(D) After all the different routes of load sharing have transmitted the packet of the IP flow once, the first packet of the second cycle of the IP flow is found before the packet is forwarded by the corresponding link layer interface. If the output interface information has been saved before, no new node will be generated; instead, the value corresponding to the tail pointer of the "output interface information" will be assigned to the "pointer to the next output interface", that is to say, at this time "pointer to The pointer to the next output interface" is no longer "null", but points to the second "output interface information" of load sharing;

(E) When the follow-up message of this IP flow arrives again, it is checked that the "pointer to the next output interface" is not "empty", that is, the current message is found directly from the output interface information corresponding to the node it points to. The output interface of the text, and replace the frame header according to the output interface information, and forward it directly from the corresponding output interface; at the same time, modify the content of the "pointer to the next output interface" to the value in the node's tail pointer; in this way, the subsequent The packets can be forwarded sequentially and in turn from each configured load sharing interface at high speed, realizing the function of fast forwarding supporting load sharing.

An embodiment of the present invention is introduced below in conjunction with Fig. 5 (it is configured three load sharing routes):

First start the router, the system is initialized, the first item "Output Interface Information" and its "pointer to the next output interface" in the routing cache table are initially turned into "empty"; at this time, the "Output Interface Information" in the " The output interface information node 1", and the subsequent "output interface information node 2" and "output interface information node 3" have not been generated yet.

When the link layer receives the first message of a certain IP flow, it checks that the "output interface information" is "null", then forwards the message to the IP process for forwarding, and finds the first message when performing routing search Load sharing routing, that is, "output interface information node 1"; before the link layer is about to send the message, save the information data of its corresponding output interface (including the frame header information, output interface and tail pointer of the IP flow) In the node of "output interface information node 1" corresponding to the index item of the routing cache table, point the tail pointer of this node to itself; at this time, its "pointer to the next output interface" is still "empty";

When the second message of the IP flow arrives, first check that the "output interface information" is not "null", then immediately check the "pointer to the next output interface", and find that it is still "null"; The message is forwarded to the IP layer for processing. At this time, the enabled load sharing software function module will forward the message from the output interface of the second load sharing route; before the link layer sends the message, compare the output When the interface information and the information already saved in the routing cache are found that the current output interface information has not been saved, a new node "output interface information node 2" is created, and at the same time, the tail pointer of "output interface information node 1" is modified to point to "output interface information node 1". Information node 2", and the tail pointer of "output interface information node 2" points to "output interface information node 1", and the two nodes are connected to form a ring; while the "pointer to the next output interface" is still "null".

When the third packet of the IP flow arrives, it is processed as the second packet. That is, it is handed over to the IP layer for processing, and the third load sharing route is found. Before the corresponding link layer interface sends a message, it is found that the output interface information has not been saved before, so a new node "output interface information node 3" is added in the routing cache. At the same time, modify the tail pointer of "output interface information node 2" to point to "output interface information node 3", and the tail pointer of "output interface information node 3" to point to "output interface information node 1", and connect to form a ring. The "pointer to next output interface" is still "null".

When the fourth packet of this flow arrives, it is also processed in the same way as the second packet. That is, it is handed over to the IP layer for processing. At this time, the load sharing software function module will send the message to the first sharing route for forwarding. Before the corresponding link layer interface sends a message, it is found that the interface information has been saved before, so no new node is generated; instead, the value corresponding to the tail pointer of "output interface information node 1" is assigned to the "point to the next output interface Pointer to ", that is to say, "pointer to the next output interface" is no longer "null" at this time, and points to "output interface information node 2".

When the follow-up message of this stream arrives, it is checked that the "pointer to the next output interface" is not "empty", that is, according to the output interface information corresponding to the node it points to, the frame header is replaced, and the corresponding output interface directly Forward it. At the same time, modify the content of "pointer to the next output interface" to the value in the node tail pointer. For example, in this embodiment, the fifth message is no longer handed over to the IP layer for processing, but directly finds the output interface 2 from the "pointer to the next output interface", and replaces the frame according to the "output interface information node 2" Forward directly after the header. At the same time, modify the "pointer to the next output interface" to point to "output interface information node 3"

In this way, subsequent IP packets can be forwarded at high speed through the configured load-sharing interface in turn, thereby realizing the function of fast forwarding supporting load sharing.

Claims (5)

1. A method for realizing fast forwarding and supporting load sharing, characterized in that: (1) Ring linked list is set: in the data structure of each cache information unit in the fast forwarding routing cache table composed of multiple cache entries, set the cache with "output interface information" and "pointing to the next output interface" Pointer"; the data structure of the "output interface information" is composed of several "output interface information nodes" that support the load sharing of the IP data flow, and each "output interface information node" is dynamically generated, and uses the "output interface information node" The tail pointers in the "Information Node" are connected to form a ring to form a circular linked list structure, and each node of the linked list corresponds to an "Output Interface Information Node"; (2) storing the output interface information in the circular linked list; (3) The data message is directly forwarded from the corresponding output interface according to the output interface information stored in the ring list. 2. A method for realizing fast forwarding and supporting load sharing according to claim 1, characterized in that: each cache entry in the plurality of cache entries corresponds to an IP data stream, and each A cache entry includes an index entry and a corresponding cache information unit. 3. A method for implementing fast forwarding and supporting load sharing according to claim 2, characterized in that: the cache information unit in each cache item stores: "pointer to the next output interface" and "Output Interface Information" composed of several "Output Interface Information Nodes". 4. A method for implementing fast forwarding and supporting load sharing according to claim 3, characterized in that: each of the "output interface information nodes" stores: the frame header information of the IP flow, the corresponding output interface and tail pointer. 5. A method for realizing fast forwarding and supporting load sharing according to claim 1, characterized in that: said data message is directly forwarded from the corresponding output interface according to the output interface information stored in the ring list The processing flow further includes the following steps: (A) When initializing the system, the first "output interface information" and its "pointer to the next output interface" in the routing cache table are initially initialized as "empty"; (B) When the link layer receives the first message of a certain IP flow, it first checks its output interface information and finds that it is "empty", then transfers the message to the IP layer for processing, and selects the first message of the IP flow. A load-sharing route is forwarded; and before the interface sends a message, save the output interface information in the first node of the routing cache table, and at the same time point the node's tail pointer to itself, and "point to the next output interface's pointer" is still "null"; (C) When the link layer receives the second and subsequent packets of an IP flow, it first checks the output interface information, if it is not "null", then immediately checks the "pointing to the next output interface" If it is found to be "empty", the message will be forwarded to the IP layer for processing, and a load sharing route of the IP flow will be sequentially selected each time for forwarding; and before the corresponding interface sends the message, compare the output Whether the interface information is different from the interface information already saved in the routing cache table. If there is no identical interface information, a new node is created in the doubly linked list of the output interface information each time, and then output through the head and tail pointers of each node. Each node in the interface information is sequentially connected to form a ring; the "pointer to the next output interface" is "empty" every time when the different routes of each load sharing are not all cached in the output interface information; (D) After all the different routes of load sharing have transmitted the packet of the IP flow once, the first packet of the second cycle of the IP flow is found before the packet is forwarded by the corresponding link layer interface. If the output interface information has been saved before, no new node will be generated; instead, the value corresponding to the tail pointer of the "output interface information" will be assigned to the "pointer to the next output interface"; (E) When the follow-up message of this IP flow arrives again, it is checked that the "pointer to the next output interface" is not "empty", that is, the current message is found directly from the output interface information corresponding to the node it points to. The output interface of the text, and replace the frame header according to the output interface information, and forward it directly from the corresponding output interface; at the same time, modify the content of "pointer to the next output interface" to the value in the node tail pointer.

Images