CN101309201A - Route processing method, route processor and router - Google Patents

Abstract

The embodiment of the present invention discloses a routing processing method, including: establishing connections between nodes in the network, and scheduling tasks for each node; each node runs a link state routing protocol according to the scheduled tasks, and performs routing calculations to obtain Routing calculation results: obtaining the routing calculation results of each node and performing routing summary. The embodiment of the present invention also provides a routing processor, including: a task scheduling module, used for task scheduling; a protocol running module, used for running the link state routing protocol according to the scheduled task, and performing routing calculation to obtain the routing calculation result ; The route summarization module is used for route summarization of the route calculation results. The embodiment of the present invention also provides a router with a multi-route processor architecture. The technical solution provided by the embodiment of the present invention can realize the scalability of the link state routing protocol.

Description

Route processing method, route processor and router

technical field

The invention relates to computer network technology, in particular to a routing processing method of a link state routing protocol, a routing processor and a router.

Background technique

In the Internet, routers usually implement the forwarding of Internet packets. What guides routers in making forwarding decisions is the forwarding information base. This forwarding information base comes from routing information provided by different routing protocols. Routing protocols run by routers can be divided into border gateway protocols between autonomous systems and interior gateway protocols within autonomous systems according to application scenarios. Among them, an autonomous system refers to an Internet network in which management policies are implemented by a single management organization. Link-state routing protocols are currently the most widely used interior gateway protocols, mainly including Open Shortest Path First Protocol OSPF (Open Shortest Path First Protocol) and Intermediate System to Intermediate System Protocol ISIS (Intermediate System to Intermediate System Routing Protocol). The link state routing protocol is based on the shortest path first algorithm. Its operation process is: through a specific neighbor discovery and maintenance protocol, discover each neighbor around the router, and use its reliable flooding mechanism to diffuse and collect autonomous system information. The local link information of each router in the router forms the so-called link-state database in link-state routing protocols. In this way, each router running a link-state routing protocol will quickly obtain panoramic information about the entire network topology and reach a consensus. By applying the shortest path first algorithm to this database, all the network reachability information of the autonomous system can be obtained, and the routing table of the link state routing protocol can be formed, and these routes are loop-free. Then, the routing table of the link state routing protocol is sent to the global routing table of the router, and the routing information obtained from different routing protocols is synthesized by the global routing table, and the optimal route is selected according to certain rules to form a data plane guidance report. The forwarding information base for document forwarding.

The operation mode of traditional link-state routing protocols is usually that one or more routing protocols (including link-state routing protocols) run on the routing processor of the router control plane as an operating system task, that is to say, protocol operation processing, Functions such as routing calculation and management control are concentrated on a single routing processor. In this mode of operation, the total number of neighbors and routing capacity that the link state routing protocol can support depends on the computing power of the routing processor and the capacity of the physical memory it is equipped with. With the expansion of network scale and flat network design, users usually hope that the total number of neighbors and routing capacity supported by the link state routing protocol can be increased with the increase of hardware resources such as routing processors to realize link state routing. The expansion of the protocol, the operation mode of the traditional link state routing protocol cannot realize the expansion of the link state routing protocol because it is concentrated on a single routing processor.

Contents of the invention

The technical problem to be solved by the embodiment of the present invention is to provide a routing processing method, a routing processor and a router, which can realize the extension of the link state routing protocol.

An embodiment of the present invention provides a routing processing method, including: establishing connections between nodes in the network, and scheduling tasks for each node; each node runs a link state routing protocol according to the scheduled tasks, and performs routing calculations to obtain Routing calculation results: obtaining the routing calculation results of each node and performing routing summary.

An embodiment of the present invention provides a routing processor, including: a task scheduling module, used for task scheduling; a protocol running module, used for running a link state routing protocol according to a scheduled task, and performing routing calculation to obtain a routing calculation result; The routing summarization module is used for routing calculation results for routing summarization.

An embodiment of the present invention provides a router, including a plurality of routing processors, and the routing processors include: a task scheduling module, used for scheduling tasks among routing processors; a protocol running module, used for running chains according to scheduled tasks The route state routing protocol is used to perform route calculation to obtain the route calculation result; the route summary module is used for route summary of the route calculation result.

As can be seen from the above technical solutions, the link-state routing protocol operation mode in the prior art is concentrated on a single routing processor, and is limited by the processing capability of the routing processor itself, so the expansion of the link-state routing protocol cannot be realized. The scheme of the embodiment of the present invention is: establish the connection between each node in the network, and perform task scheduling for each node; each node runs the link state routing protocol according to the scheduled task, and performs routing calculation to obtain the routing calculation result; obtain each The route calculation result of the node is summarized. Because under the operating mode of the embodiment of the present invention, the task scheduling, protocol execution and routing summary operations of the link state routing protocol can be dynamically distributed to each node, that is, each routing processor, so the resources of each node can be fully utilized, thereby realizing It improves the scalability of link-state routing protocols.

Description of drawings

Fig. 1 is a distributed model diagram of a link state routing protocol according to an embodiment of the present invention;

FIG. 2 is a flow chart of a routing processing method according to an embodiment of the present invention;

FIG. 3 is a flow chart of task scheduling in the routing processing method according to an embodiment of the present invention;

FIG. 4 is a schematic diagram of a scheduling state machine according to an embodiment of the present invention;

FIG. 5 is a schematic diagram of a routing table state machine according to an embodiment of the present invention;

6 is a schematic diagram of establishing a connection relationship between nodes according to an embodiment of the present invention;

7 is a flow chart of actively assigning tasks in the routing processing method according to the embodiment of the present invention;

FIG. 8 is a flow chart of passively assigning tasks in a routing processing method according to an embodiment of the present invention;

FIG. 9 is a schematic diagram of an application network of a routing processing method according to an embodiment of the present invention;

10 is a schematic diagram of related information in the application network of the routing processing method according to the embodiment of the present invention;

11 is a schematic diagram of related information 2 in the application network of the routing processing method according to the embodiment of the present invention;

12 is a schematic diagram of related information three in the application network of the routing processing method according to the embodiment of the present invention;

FIG. 13 is a schematic structural diagram of a routing processor according to an embodiment of the present invention;

14 is a schematic structural diagram of a routing processor task scheduling module according to an embodiment of the present invention;

FIG. 15 is a schematic structural diagram of a router according to an embodiment of the present invention.

Detailed ways

The operation mode of the traditional link-state routing protocol is concentrated on a single routing processor, which is limited by the processing capability of the routing processor itself, and cannot realize the expansion of the link-state routing protocol. A routing processing method provided by the embodiment of the present invention, By dynamically distributing the functions contained in the link-state routing protocol to multiple routing processors, the scalability of the link-state routing protocol can be realized.

The router's multi-routing processor operating architecture generally consists of two parts: several nodes and the internal communication network between them. These nodes are usually organized into a distributed master-slave relationship, that is, a certain node is the master node, and other nodes are distributed slave nodes. Among them, each node includes: routing processor, used to run router control plane tasks such as routing protocols; external interface, used to receive and send routing control packets through the external switching network connected to the forwarding plane; internal interface, used to pass The internal switching network receives and sends messages to complete internal communication between nodes.

For the convenience of description, the routing processor is referred to as a node for short in the following.

The distributed model of the link state routing protocol in the embodiment of the present invention includes a task scheduling module, a protocol running module and a routing table summarizing module. Among them, the task scheduling module is used to discover and maintain the connection relationship between each node, and assign tasks according to the node processing capabilities; the protocol operation module is used to run the basic link state routing protocol according to the assigned tasks; the routing The table summarization module is used to collect the local routing tables of each node.

The task scheduling algorithm of the embodiment of the present invention includes a scheduling state machine and a routing table state machine. Among them, the scheduling state machine divides the states of each node into the main scheduling state, the backup scheduling state, and the secondary scheduling state according to the decision-making power of task assignment. The functions of the scheduling state machine include: establishing and maintaining the relationship between nodes in the distributed system; electing the master scheduling node, backup scheduling node and slave scheduling node; and performing task assignment, etc. The routing table state machine divides the state of each node into the main summary state, the backup summary state and the secondary summary state according to the execution right of the routing table summary task, and completes the summary operation of each local routing table.

The technical solutions of the embodiments of the present invention will be described in detail below in conjunction with the accompanying drawings.

Under the scheduling of the scheduling state machine, the distributed implementation model can be mapped to a specific running model according to the specific scheduling strategy. Figure 1 shows an example of a distributed model of a link-state routing protocol. The mark 22 represents a router, the mark 33 represents a node, and the three circles from top to bottom in the node are three components under the distributed model: task scheduling module, protocol operation module and routing table summary module. Through the scheduling of the scheduling state machine, several allocation modes can be made. A distribution mode is shown in A. Under the control of the scheduling state machine, the task distribution of protocol operation and routing table summary work on multiple nodes is completed. Each node executes protocol operation and routing table summary. At this time, each node The routing table summary module on the router will only complete the summary of local routing information and send it to the global routing table of the router, which is stored in other memory of the router. Another allocation mode is shown in B. Let the main scheduling node perform routing table summary, then the main scheduling node is also the main summary node. At this time, the main summary node needs to summarize the routing information of each node before sending it to the router. Global routing table. There is another distribution mode, as shown in C, which further distributes the routing table summary operation to non-main scheduling nodes under the scheduling of the routing table state machine. The embodiment of the present invention will mainly be introduced in the mode shown in B but is not limited thereto.

Please refer to FIG. 2, which is a flow chart of the routing processing method according to the embodiment of the present invention, including:

A1. Perform task scheduling;

Before introducing the content of this step in detail, first introduce the process of scheduling the state machine.

Figure 4 shows the scheduling state machine. It divides each node into: "inactive" state, in this state, the node does not run the link state routing protocol; in the "waiting" state, the node can run the link state routing protocol but has not entered the working mode; working mode, and The decision rights assigned by tasks are divided into "master scheduling", "backup scheduling" and "slave scheduling" states. Driven by triggering events, the scheduling state machine completes the following functions: establish and maintain the relationship between nodes in the distributed system; elect the master scheduling node, backup scheduling node and slave scheduling node; perform task assignment, etc.

As shown in Figure 4, if the node stops the routing protocol in any state, it will transition to the "inactive" state. When the routing protocol is started, it will transition from the "inactive" state to the "waiting" state, start the timer, and start Broadcast heartbeat messages on the internal communication network. After the timer expires, the master scheduling node election is carried out. The rule is to elect the master scheduling node with the largest "processing capacity", followed by the backup scheduling node, and the rest are slave scheduling nodes. When the "processing capacity" value is the same, then Comparing the internal network address values, the rule is generally to elect the one with the largest network address value as the master scheduling node, followed by the backup scheduling node, and the rest as the slave scheduling nodes. The tasks of the backup scheduling node and the slave scheduling node are assigned by the main scheduling node.

Step A1 can be specifically divided into the following steps, please refer to Figure 3, including:

B1. Establish and maintain the relationship between nodes, elect the master scheduling node, backup scheduling node and slave scheduling node;

When the network system is just started, each node knows the existence of each other by periodically broadcasting heartbeat messages, and elects a master scheduling node and a backup scheduling node according to its processing capabilities, and the rest are slave scheduling nodes. Information about processing capabilities is carried in heartbeat messages. After that, the slave scheduling node only sends heartbeat messages to the master scheduling node, and the master scheduling node broadcasts heartbeat messages on the internal network.

For example, the five nodes A, B, C, D, and E shown in Figure 6, after receiving the configuration command to run OSPF, transition from the "inactive" state to the "waiting" state, start the timer, and start the internal Heartbeat messages are broadcast on the communication network. In the format of the heartbeat message, bits 0-1 represent the type field, bits 2-3 represent the state field, bits 4-7 represent the address field, and bits 8-9 represent the processing capability field. Since the current status of each node is "waiting", the value of the state field of the heartbeat message is "waiting", and the "processing capacity" field is the remaining processing capacity of the current node of the node. By broadcasting heartbeat messages, each node obtains neighbor information, which constitutes the following neighbor list.

node state processing capacity A wait 8 B wait 6 C wait 3 D wait 2 E wait 3

The state of nodes A, B, C, D and E in the table is waiting, and the processing capability values are 8, 6, 3, 2 and 3 respectively. After the timer expires, each node starts to elect the master scheduling node. The rule is to find the master scheduling node with the largest "processing capability" value from the obtained neighbor set, followed by the backup scheduling node, and the rest are slave scheduling nodes. When the "processing capacity" values are the same, compare their internal network address values. Generally, the rule is to select the one with the largest network address value as the master scheduling node, followed by the backup scheduling node, and the rest as slave scheduling nodes. Therefore, node A is elected as the master scheduling node, B is elected as the backup scheduling node, and C, D, and E are the slave scheduling nodes. Therefore, nodes A and B transition to the "master scheduling" state and "backup scheduling" state respectively, and nodes C, D, and E all transition to the "slave scheduling" state. After that, A regularly broadcasts heartbeat messages to the internal network, and its state field is "main scheduling", while B, C, D, and E only send heartbeat messages to A, and the state field of B is "backup scheduling", and C, D, and E The E state field is "slave scheduling".

When a new node F joins, the state of node F is "waiting", it starts a timer, and starts broadcasting heartbeat messages to the internal network. Since B, C, D, and E are in non-"main-scheduling" state at this time, they will ignore the heartbeat message from F with a state of "waiting", and A is in "main-scheduling" state at this time, and it will join F to the neighbor list. On the other hand, since A periodically broadcasts a heartbeat message whose status field is "Main Scheduling", the periodic time is less than the timeout time of the timer. After receiving the heartbeat message from A, F finds that there is already a master scheduling node in the internal network. Then the event of "discovering master scheduling" occurs, node F changes the state from "waiting" to "slave scheduling", and only sends heartbeat messages to A from then on.

B2. The main scheduling node assigns tasks;

After the main scheduling node is elected, the main scheduling node starts the initial allocation of tasks. In this step, task assignment is performed by the scheduling state machine.

According to the usual application scenarios of the link state routing protocol in the network, the scheduling state machine can use different split units to perform task assignment. Said different split units refer to multiple virtual private network VPN (Virtual private network) instances of link state routing protocols, multi-protocol processes and multiple areas connected by area border routers in link state routing protocols, etc.

Link-state routing protocol multi-VPN instances refer to routing protocol instances running under each VPN. Each instance only completes the routing function within the VPN and has nothing to do with routing instances under other VPNs. The multi-protocol process of the link state routing protocol refers to a part of the network in which each protocol process runs independently of each other under the same autonomous system, that is, the so-called protocol routing domain. The routing function is completed in this independent sub-routing domain, and they are not related to each other. . An area border router is the link-state routing protocol's definition of a router that is simultaneously connected to multiple areas within an autonomous system. Link state routing protocol divides the entire autonomous system into multiple areas in order to expand the support for a large number of large-scale autonomous systems. These areas are also divided into backbone areas and non-backbone areas. The backbone area must be physically or logically connected, and each non-backbone area must be connected to the backbone area. Area-to-area junctures are area border routers, and other routers are called intra-area routers. The routers in the area complete the routing function in the area by running the shortest path algorithm, while the border routers in the area are responsible for flooding all the routing information in the area to other areas in the form of summaries, so as to assist the routers in the area to complete the inter-area routing function. The method of implementing inter-area routing in the road state routing protocol borrows the split horizon method in the distance vector routing protocol. Therefore, the area border router actually runs the shortest path algorithm on each connected area, and different areas are relatively independent networks.

The three kinds of irrelevance described above can all become the task allocation algorithm of the scheduling state machine. When multiple areas of area border routers are used as the division unit, each processing node runs a specific area, maintains the neighbor relationship in the area, and synchronizes the link state information of the area. When multi-VPN instances or multi-protocol processes are used as distributed task allocation units, each node can run several link-state routing protocol processes, and each process is an independent link-state routing protocol. In a specific implementation, a configuration option can be provided, so that users can make a final choice according to the specific application scenarios of the protocol.

The following content of the embodiment of the present invention is described by taking the OSPF protocol of the link state routing protocol as an example, and using multiple area allocation units of the area border router to perform task allocation.

After determining the relationship between the processing nodes and electing the main scheduling node, the main scheduling node in the “main scheduling” state will trigger the “active task allocation” event when receiving the routing control message, and execute the active task allocation shown in Figure 7 Operation process; when the backup scheduling node under "backup scheduling" or the slave scheduling node under the "slave scheduling" state receives the routing control message, it triggers the "passive task allocation" event and performs the passive task allocation operation shown in Figure 8 process.

Please refer to Figure 7, the shown active task allocation operation process includes:

C1, receiving the routing control message;

C2. Determine whether the message processing task is in charge of the node, if yes, go to step C3, if not, go to step C4;

The main scheduling node can determine whether the message processing task is in charge of the node by looking up relevant information in the local interface list.

C3, will process the routing control message;

C4, whether the message processing task has been assigned, if yes, go to step C6, if not, go to step C5;

The main scheduling node can determine whether the message processing task has been allocated by looking up relevant information in the area list of the task allocation mapping table.

C5. Designate a node to be responsible for the message processing task, and enter step C6;

C6. Send interface information to the corresponding node to notify it to join the task;

C7. Modify the interface mapping table information.

Please refer to Figure 8, the shown passive task allocation operation process includes:

D1. Receive routing control message;

D2. Determine whether the message processing task is in charge of the node, if yes, go to step D3, if not, go to step D4.

The backup scheduling node or the slave scheduling node can determine whether the message processing task is in charge of the node by looking up relevant information in the local interface list.

D3. Processing the routing control message;

D4. Discard the routing control message.

A specific description will be given below in conjunction with an example of an application network shown in FIG. 9 . Fig. 9 includes routers RT1, RT2 in area0, router RT4 in area1, area border router RT3, and networks n1 to n6. The area border router RT3 is connected to two areas, namely area0 and area1, through three interfaces, namely if0, if1, and if2. RT3 consists of three nodes, namely A, B, and C. The current status is "main scheduling", "backup scheduling" and "slave scheduling", that is, A, B, and C are the main scheduling node, backup scheduling node, and from the scheduling node.

A possible task allocation result is: C is responsible for the task of area0, and B is responsible for the task of area1. The specific operation is as follows: Initially, the data of each node and the forwarding plane are shown in Figure 10 . The forwarding plane receives the OSPF message from the interface if0, and it selects the default mode to broadcast the message to the entire distributed system according to the interface mapping table (currently empty), so A, B, and C all receive the message from the interface if0 OSPF packet, which carries area0 information. B and C did not find the if0 information in their local interface lists, and judged that they were not responsible for the task, so they discarded the OSPF packets. A first also does not find if0 information in its local interface list, and judges that the task is not responsible for itself. Then, A checks whether the task has been allocated, and it looks for area0 in the area list of the task allocation mapping table (empty at this time). , but not found, so it is judged that the task has not been allocated, then add area0 to the area list of the task allocation mapping table, and launch the node C with the largest remaining processing capacity in the node queue arranged in the order of "processing capacity", In this way, the assignment result is that C is assigned to be responsible for the area0 task. A will perform the following operations: fill in C in the node corresponding to area0 in the area list of the task assignment mapping table, set the port corresponding to the interface if0 in the interface mapping table as C, and send a message to C to notify it to join the new task if0. Then the result shown in Fig. 11 is obtained.

During this process, A is also responsible for periodically delivering the interface mapping table to the forwarding plane. As shown in Figure 11. When the forwarding plane receives an OSPF message, it will send the message to the corresponding node in unicast mode according to the interface from which the message comes and the contents of the interface mapping table. Therefore, when the forwarding plane sends the message from the interface if0 to the control plane again, it will directly send the message to C, thereby reducing the processing overhead on A and B.

Similarly, when A receives an OSPF packet from interface if2, it carries area1 information. B and C still do the same processing as before. A also does a similar process, adding area1 to the area list of the task allocation mapping table, and pushes out the node B with the largest remaining processing capacity in the node queue, and the assignment result is that B is assigned to be responsible for the area1 task. For this purpose, A performs the following operations: fill in B in the node corresponding to area1 in the area list of the task assignment mapping table, set the port corresponding to interface if2 in the interface mapping table as B, and send a message to B to notify it to join the new task if2.

When A receives an OSPF packet from interface if1, it carries area0 information. B and C still do the same processing as before. A finds area0 in the area list of the task allocation mapping table, and knows that the area0 task has been assigned to C, so directly sets the port corresponding to interface if1 in the interface mapping table as C, and sends a message to C, informing it to join the new task if1 . Then the result in Figure 12 is obtained.

In this way, C and B are assigned to tasks area0 and area1 respectively, and the interfaces they contain are if0, if1 and if2 respectively. Messages from interfaces if0 and if1 will be sent directly to node C, and messages from interface if2 will be sent directly to node B.

In a nutshell, the above content describes the method for task allocation in the embodiment of the present invention. It uses nodes to perform active task allocation in the "master scheduling" state, and perform passive task allocation in the "backup scheduling" or "slave scheduling" state. Centralize the task allocation algorithm to the main scheduling node to complete, and ensure that the corresponding tasks will be sent directly from the forwarding plane to the corresponding processing nodes, so that each node will only receive the routing information in the area it is responsible for, and then perform routing independently calculate.

B3. Elect and broadcast the primary summary node of the routing table.

The main scheduling node selects the main summary node, the backup summary node and the secondary summary node according to the processing capabilities of each node collected by receiving the heartbeat message, and sends them to each node through an internal message.

Here, the routing table state machine is used for scheduling. The scheduling algorithm of the routing table state machine depends on the algorithm of the scheduling state machine. The routing table state machine, as shown in Figure 5, is similar to the scheduling state machine, and divides each node into a "waiting" state. The node has not entered the working mode, that is, no related operations of routing table summary are required. In the working mode, the status of each node is divided into "master summary", "backup summary" and "slave summary" according to the decision-making power assigned by the task. If the node stops the routing protocol in any state, it will transition to the "inactive" state. When the routing protocol is started, it will transition from the "inactive" state to the "waiting" state, start the timer, and start broadcasting on the internal communication network Heartbeat message. After the timer expires, the routing summary relationship is determined.

The process of determining the routing summary relationship refers to the transition of the routing state of each node from the "waiting" state to one of the three states in the working mode, that is, the initialization process of the routing table state machine, which is generally synchronized with the initialization process of the scheduling state machine. During the election process of the main scheduling node of the scheduling state machine, each node transitions from the "waiting" state to one of the three scheduling states, as the "timer timeout" event and "discovering the main scheduling" of the scheduling state machine triggering the operation Events are also triggering events for the routing table state machine. Correspondingly, the routing table state machine of a node that transitions from the "waiting" state to the "main scheduling" state in the scheduling state machine will also transition from the "waiting" state to the "main summary" state. That is to say, the initialization of the routing table state machine is the same as that of the scheduling state machine. By default, the node that performs the main scheduling is also responsible for the routing table summary, that is, the main scheduling node is also the main summary node.

A2. Each node runs the link state routing protocol, performs routing calculations, and obtains a local routing table;

Each node will run the link state routing protocol locally according to the assigned tasks, discover and maintain neighbor relationships, synchronize link state information with each neighbor, apply the shortest path first algorithm for routing calculations, and obtain local routing tables.

A3. Carry out route summarization.

Each node performs route summary according to the route summary relationship determined by the routing table state machine.

Generally, each slave summary node sends the local routing table to the main summary node, and the main summary node summarizes the routing table, obtains the summary result, and sends a copy to the backup summary node.

When the scheduling state machine is implemented in the multi-area or link-state routing protocol multi-process mode of the link-state routing protocol area border router, since the routing tables of each process are valid within the same range, it is necessary to transfer each local routing table to Summarized to form the global routing table of a complete routing protocol. Each slave summary node sends a local routing table to the main summary node, and the main summary node collects all routing calculation results to form a global routing table of the routing protocol, and sends it to the global routing table of the router.

Although the main scheduling node is generally the main summary node by default, it is responsible for the summary of the routing table, but under the scheduling of the routing table state machine, the main summary node may not be the same node as the main scheduling node, that is, task scheduling can be performed on one node. Routing table summarization can run on a different node.

It should also be noted that if multiple instances of link-state routing protocols are used as the scheduling unit, since each protocol instance is valid within the scope of its own VPN, each node can independently complete its own routing table summary, which is equivalent to Each node is the main summary state.

The summary of the routing table may also consider some specific requirements of the routing protocol. For example, when the OSPF area is used as the distributed execution unit, the support for OSPF virtual links needs to be considered. For an OSPF relay area configured with a virtual link, its Type 3 and Type 4 Link State Advertisement LSAs (Link State Advertisement) need to update the routing calculation results of the backbone area. Therefore, these two types of LSAs can be calculated locally first and become local A part of the routing table is sent to the main aggregation node for aggregation according to the protocol rules, and the specific process depends on the implementation of the routing protocol.

The summary of each local routing table will form the global routing table of the routing protocol. At this time, the link state routing protocol needs to send it to the global routing table of the router. The global routing table of the router synthesizes the routing information obtained from different routing protocols. , select the optimal route according to certain rules, form a forwarding information base for the data plane to guide packet forwarding, and send it to the forwarding plane.

The above content introduces the route processing method of the embodiment of the present invention in detail, and accordingly, the embodiment of the present invention provides a route processor.

Please refer to FIG. 13 , which is a schematic structural diagram of a routing processor according to an embodiment of the present invention. The routing processor includes a task scheduling module 100 , a protocol running module 200 and a routing summary module 300 .

Among them, the task scheduling module 100 is responsible for discovering and maintaining connection relationships with other routing processors, and assigning tasks according to the processing capabilities of each routing processor.

The protocol running module 200 is configured to run a basic link state routing protocol according to assigned tasks, perform routing calculations, and obtain a local routing table.

The route summarization module 300 is used for route summarization of the route calculation results, and can gather the local routing tables obtained from the route calculation by each route processor, so as to form a complete global routing table of the routing protocol.

Referring to FIG. 14 , the task scheduling module 100 of the routing processor further includes an information unit 1001 , a scheduling election unit 1002 , a routing summary election unit 1003 and a task allocation unit 1004 .

The information unit 1001 is used to store the routing processor's own processing capability value information and obtain the processing capability value information of other routing processors; each routing processor knows the existence of each other by periodically broadcasting heartbeat messages, and the processing capability value information is in the heartbeat message In carrying, the information unit 1001 obtains the processing capability value information of other routing processors through a heartbeat message.

The scheduling selection unit 1002 is configured to select a routing processor for task allocation according to the processing capability value information of its own routing processor stored in the information unit 1001 and the acquired processing capability value information of other routing processors. The election rule is to find the one with the largest processing capability value from the obtained neighbor set as the main scheduling routing processor for task assignment, followed by the backup scheduling routing processor, and the rest as the slave scheduling routing processor. When the processing capability values are the same, compare the internal network address values. The rule is generally that the one with the largest network address value is selected as the master scheduling routing processor, followed by the backup scheduling routing processor, and the rest are slave scheduling routing processors.

The route summary election unit 1003 is configured to select a route processor for route summary according to its own processing capability value information stored in the information unit 1001 and the acquired processing capability value information of other route processors. The election rule generally takes the one with the largest processing capability value as the main summary route processor for route summarization, followed by the backup summary route processor, and the rest as slave summary route processors. Generally speaking, the main scheduling route processor elected by the scheduling election unit 1002 and the main summary route processor elected by the route summary election unit 1003 are the same route processor, but the main summary route processor elected by the route summary election unit 1003 can also be Not the same route processor as the main dispatch route processor.

The task allocation unit 1004 is used for task allocation when the routing processor serves as the main scheduling routing processor, and can allocate tasks to other routing processors.

The task scheduling module 100 of the routing processor further includes: a first timer unit 1005 and a scheduling state machine unit 1006 .

The first timer unit 1005 is used for setting timing. The scheduling state machine unit 1006 is used to divide the task state of the routing processor and instruct the routing processor to perform different operations. When the routing processor enters the waiting state and starts timing after the first timer unit 1005, the scheduling state machine unit 1006 informs the information unit 1001 to obtain the processing capability value information of other routing processors. When the timing set by the first timer unit 1005 expires, the scheduling state machine unit 1006 triggers the scheduling election unit 1002 to perform an election, and instructs the routing processor to be elected as It enters the master scheduling state when task allocation is performed, and enters the backup scheduling state or slave scheduling state when it is not elected for task allocation.

The task scheduling module 100 of the routing processor further includes: a second timer unit 1007 and a routing table state machine unit 1008 .

The second timer unit 1007 is used for setting timing. The routing table state machine unit 1008 is used to divide the routing summary state of the routing processor and instruct the routing processor to perform different operations. When the routing processor enters the waiting state and after the second timer unit 1007 starts timing, the routing table The state machine unit 1008 notifies the information unit 1001 to obtain the processing capability value information of other routing processors. When the timing set by the second timer unit 1007 expires, the routing table state machine unit 1008 triggers the route summary election unit 1003 to elect and instructs the route When the processor is elected for route summarization, it enters the main summary state, and when it is not elected for route summary, it enters the backup summary state or the slave summary state.

The task allocation unit 1004 in the task scheduling module 100 of the routing processor further includes: a judging unit 10041 and a processing unit 10042 . The judging unit 10041 is used to judge whether the message processing task belongs to the routing processor according to the interface list information after receiving the message; The routing processor responsible for the message processing task, and modify the interface mapping table information.

The embodiment of the present invention also provides a router. Please refer to FIG. 15 , which is a schematic structural diagram of a router according to an embodiment of the present invention.

In FIG. 15 , the router contains three route processors 60 , 70 and 80 as an example to illustrate but not limited thereto, and the router may contain multiple route processors. Each routing processor of the router is the same as the routing processor introduced in FIG. 13 , including a task scheduling module 100 , a protocol running module 200 and a route summarizing module 300 .

Wherein, the task scheduling module 100 is responsible for discovering and maintaining the connection relationship with other routing processors, and assigning tasks according to the processing capability value of each routing processor. The protocol running module 200 is configured to run a basic link state routing protocol according to assigned tasks, perform routing calculations, and obtain a local routing table. The route summarization module 300 is used for route summarization of the route calculation results, and can gather the local routing tables obtained from the route calculation by each route processor, so as to form a complete global routing table of the routing protocol. The task scheduling module 100 of each routing processor further includes an information unit 1001, a scheduling election unit 1002, a routing summary election unit 1003, a task assignment unit 1004, a first timer unit 1005, a scheduling state machine unit 1006, and a second timer unit 1007 and routing table state machine unit 1008. The task allocation unit 1004 in the task scheduling module 100 further includes a judging unit 10041 and a processing unit 10042 . The functions of these units are the same as those described above and will not be described in detail here.

In summary, the link-state routing protocol operation mode in the prior art is concentrated on a single routing processor, and is limited by the processing capability of the routing processor itself, so the expansion of the link-state routing protocol cannot be realized, and the implementation of the present invention The example solution is: establish the connection between the nodes in the network, and schedule tasks for each node; each node runs the link state routing protocol according to the scheduled tasks, and performs routing calculation to obtain the routing calculation result; Describe the route calculation results and perform route summary. Because under the operating mode of the embodiment of the present invention, the task scheduling, protocol execution and routing summary operations of the link state routing protocol can be dynamically distributed to each node, that is, each routing processor, so the resources of each node can be fully utilized, thereby realizing An extension of the link-state routing protocol.

Furthermore, dynamically distributing the three functions of the link-state routing protocol to each node can have greater fault tolerance. If a node of the distributed system fails, or when a node's protocol is running and its network fluctuates greatly, it can isolate the impact on other nodes.

A routing processing method, a routing processor, and a router provided by the embodiments of the present invention have been described above in detail. In this paper, specific examples are used to illustrate the principles and implementation methods of the embodiments of the present invention. The descriptions of the above embodiments are only It is used to help understand the method and its core idea of the embodiment of the present invention; at the same time, for those of ordinary skill in the art, according to the idea of the embodiment of the present invention, there will be changes in the specific implementation and application scope. In summary As stated above, the content of this specification should not be construed as limiting the present invention.

Claims (17)

1, a kind of route processing method is characterized in that, comprising:

Set up each internodal connection in the network, each node is carried out task scheduling;

Each node is according to the task run link-state routing protocol of described scheduling, and the walking along the street of going forward side by side obtains route result of calculation by calculating;

Obtain the described route result of calculation of each node and go forward side by side walking along the street by gathering.

2, route processing method according to claim 1 is characterized in that, describedly each node is carried out task scheduling is specially:

Determine to carry out the node of Task Distribution and carry out the node that route gathers according to the disposal ability value information of each node;

The task of distributing each node by the described node of determining that carries out Task Distribution.

3, route processing method according to claim 2 is characterized in that:

Described disposal ability value information according to each node is determined to carry out the node of Task Distribution and carries out the node that route gathers to be specially:

Obtain the heartbeat message that carries node processing ability value information of broadcasting in the network, according to described disposal ability value information, the node of election processing ability value maximum is as the node that carries out Task Distribution and carry out the node that route gathers.

4, route processing method according to claim 2 is characterized in that:

The node that described disposal ability value information according to each node is determined to carry out Task Distribution is by the control of dispatch state machine, and control procedure is specially:

Indication enters the node of wait state and broadcast the heartbeat message that carries node status information and disposal ability value information after starting timer, behind timer expiry, triggering determines to carry out the election process of the node of Task Distribution, the node that elects the processing ability value maximum is as the node that carries out Task Distribution, and indicate it to enter the master scheduling state, indicate other nodes to enter backup dispatch state or the node transmission heartbeat message of the node from dispatch state from dispatch state to the master scheduling state according to election results.

5, route processing method according to claim 2 is characterized in that:

The node that the route of determining described disposal ability value information according to each node to carry out gathers is by the control of routing table state machine, and control procedure is specially:

Indication enters the node of wait state and broadcast the heartbeat message that carries node status information and disposal ability value information after starting timer, behind timer expiry, triggering determines to carry out the election process of the node that route gathers, the node that elects the processing ability value maximum is as carrying out the node that route gathers, and indicate it to enter the master scheduling state, indicate other nodes to enter backup summary status or, only send heartbeat message to the node of main summary status from the node of summary status from summary status according to election results.

6, route processing method according to claim 2 is characterized in that, the described node of determining that carries out Task Distribution distributes the task of each node to be specially:

The node that carries out Task Distribution that elects splits the task that unit distributes each node according to difference, the described different a plurality of zones that split multiple virtual private network (VPN) VPN instance, multi-protocols process or Area Border Router connection that unit is a link-state routing protocol.

According to claim 2 or 6 described route processing methods, it is characterized in that 7, the described node of determining that carries out Task Distribution distributes the task of each node to be specially:

After the described node that carries out Task Distribution that elects receives message, according to node under the interface list information judgement message Processing tasks, do not belong to this node and be responsible for if judge, then specify the node of being responsible for this message Processing tasks, and revise interface map list information.

8, route processing method according to claim 2 is characterized in that, describedly obtains the walking along the street of going forward side by side of route result of calculation and is specially by gathering:

Each node will carry out local routing table that route calculates send to described determine carry out the node that route gathers, describedly carry out the node that route gathers and receive the laggard walking along the street of described local routing table by gathering, obtain overall routing table.

9, a kind of route processors is characterized in that, comprising:

Task scheduling modules is used to carry out task scheduling;

Agreement operation module is used for the task run link-state routing protocol by scheduling, and the walking along the street of going forward side by side obtains route result of calculation by calculating;

The route summarizing module is used for that route result of calculation is carried out route and gathers.

10, route processors according to claim 9 is characterized in that, described task scheduling modules further comprises:

Information unit, the disposal ability information that is used to store route processors self disposal ability information He obtains other route processorss;

Scheduling election unit is used for electing the route processors that carries out Task Distribution according to route processors self the disposal ability information of information unit storage and the disposal ability information of other route processorss that obtain;

Route gathers the election unit, is used for carrying out the route processors that route gathers according to the node processing ability information of information unit storage and the disposal ability information election of other route processorss that obtain;

Task allocation unit is used for allocating task.

11, route processors according to claim 10 is characterized in that, described task scheduling modules further comprises:

The first timer unit is used to be provided with regularly;

Dispatch state machine unit, be used for the task status of route processors is divided, and the indication route processors is carried out different operating, when route processors enter wait state and the first timer unit starting regularly after, announcement information unit, dispatch state machine unit obtains the disposal ability information of other route processorss, after the timing of first timer unit setting is overtime, dispatch state machine unit triggers scheduling election unit conducts an election, and the indication route processors is elected as and enters the master scheduling state when carrying out Task Distribution, is not elected as to enter the backup dispatch state when carrying out Task Distribution or from dispatch state.

12, route processors according to claim 10 is characterized in that, described task scheduling modules further comprises:

The second timer unit is used to be provided with regularly;

The routing table state machine unit, be used for the route summary status of route processors is divided, and the indication route processors is carried out different operating, when route processors enter wait state and the second timer unit starting regularly after, routing table state machine unit announcement information unit obtains the disposal ability information of other route processorss, after the timing of second timer unit setting is overtime, routing table state machine unit triggering route gathers the election unit and conducts an election, and the indication route processors is elected as and carries out entering main summary status when route gathers, and is not elected as to carry out entering when route gathers the backup summary status or from summary status.

13, route processors according to claim 10 is characterized in that, described task allocation unit further comprises:

Judging unit after being used to receive message, judges according to interface list information whether the message Processing tasks belongs to this route processors and be responsible for;

Processing unit is used for specifying the route processors of being responsible for this message Processing tasks when judgment unit judges goes out not belong to this route processors and is responsible for, and revises interface map list information.

14, a kind of router is characterized in that, comprising:

A plurality of route processorss, described route processors comprises:

Task scheduling modules is used to carry out the task scheduling between route processors;

Agreement operation module is used for the task run link-state routing protocol by scheduling, and the walking along the street of going forward side by side obtains route result of calculation by calculating;

The route summarizing module is used for that route result of calculation is carried out route and gathers.

15, router according to claim 14 is characterized in that, the task scheduling modules in the described route processors further comprises:

Information unit, the disposal ability information that is used to store route processors self disposal ability information He obtains other route processorss;

Scheduling election unit is used for electing the route processors that carries out Task Distribution according to route processors self the disposal ability information of information unit storage and the disposal ability information of other route processorss that obtain;

Route gathers the election unit, is used for carrying out the route processors that route gathers according to the node processing ability information of information unit storage and the disposal ability information election of other route processorss that obtain;

Task allocation unit is used for allocating task.

16, router according to claim 15 is characterized in that, the task scheduling modules in the described route processors further comprises:

The first timer unit is used to be provided with regularly;

Dispatch state machine unit, be used for the task status of route processors is divided, and the indication route processors is carried out different operating, when route processors enter wait state and the first timer unit starting regularly after, announcement information unit, dispatch state machine unit obtains the disposal ability information of other route processorss, after the timing of first timer unit setting is overtime, dispatch state machine unit triggers scheduling election unit conducts an election, and the indication route processors is elected as and enters the master scheduling state when carrying out Task Distribution, is not elected as to enter the backup dispatch state when carrying out Task Distribution or from dispatch state;

The second timer unit is used to be provided with regularly;

The routing table state machine unit, be used for the route summary status of route processors is divided, and the indication route processors is carried out different operating, when route processors enter wait state and the second timer unit starting regularly after, routing table state machine unit announcement information unit obtains the disposal ability information of other route processorss, after the timing of second timer unit setting is overtime, routing table state machine unit triggering route gathers the election unit and conducts an election, and the indication route processors is elected as and carries out entering main summary status when route gathers, and is not elected as to carry out entering when route gathers the backup summary status or from summary status.

17, router according to claim 15 is characterized in that, the described task allocation unit of task scheduling modules further comprises in the described route processors:

Judging unit after being used to receive message, judges according to interface list information whether the message Processing tasks belongs to this route processors and be responsible for;

Processing unit is used for specifying the route processors of being responsible for this message Processing tasks when judgment unit judges goes out not belong to this route processors and is responsible for, and revises interface map list information.

Images