CN106411729A

CN106411729A - Method and apparatus for processing link-state advertisement

Info

Publication number: CN106411729A
Application number: CN201510466664.1A
Authority: CN
Inventors: 何建军
Original assignee: ZTE Corp
Current assignee: ZTE Corp
Priority date: 2015-07-31
Filing date: 2015-07-31
Publication date: 2017-02-15
Anticipated expiration: 2035-07-31
Also published as: CN106411729B; WO2016177136A1

Abstract

The invention discloses a method and apparatus for processing a link-state advertisement (LSA). The method comprises: generating an LSA to which a distinguishing identifier is added when a router fails to store the LSA; flooding the LSA to which the distinguishing identifier is added to other routers in a network so that the other routers do not add the neighbor router to a SPF (shortest path first) candidate list when adding the router generating the LSA to which the distinguishing identifier is added to the SPF tree by operating SPF to calculate an optimal path. When the method fails to store the LSA, LSA to which the distinguishing identifier is added is generated. The other routers do not add the neighbor router to a SPF (shortest path first) candidate list when adding the router generating the LSA to which the distinguishing identifier is added to the SPF tree by operating SPF to calculate an optimal path, thereby avoiding routing loops caused by storage LSA failure, and ensuring normal transmission of data packets.

Description

Method and device for realizing link state notification processing

Technical Field

The present invention relates to dynamic routing technologies, and in particular, to a method and an apparatus for implementing link state advertisement processing.

Background

The dynamic routing protocol is mainly divided into a distance vector routing algorithm and a link state routing algorithm. The distance vector Routing algorithm comprises a Routing Information Protocol (RIP) and a Border Gateway Protocol (BGP); link state routing algorithms include Open Shortest Path First (OSPF) and Intermediate System-to-Intermediate System (ISIS).

In the distance vector routing algorithm, each router maintains a table listing the currently known best paths to each destination, the tables are continuously updated by exchanging information between neighbors, and finally each router has the best path to each destination. The distance vector routing algorithm has certain disadvantages, for example, the distance vector routing algorithm takes too long to converge to a stable state after the network topology changes, and thus the link state routing algorithm gradually appears. In the Link State routing algorithm, neighbors are discovered by sending and receiving call-out (HELLO) messages, Link State Databases (LSDB) are synchronized among the neighbors, a local router constructs a Shortest Path First (SPF) tree by using the LSDB which is completed synchronously, and finally a loop-free optimal Path reaching each destination address is calculated. After the link state databases are synchronized, the link state databases of the routers at the two ends are consistent, and the running of the SPF ensures that the calculated optimal path cannot form a routing loop.

In the process of calculating the optimal path, the problem of asynchronous link state databases may occur, for example, because the memory usage of the router at one end reaches the maximum value, no additional memory stores the newly received link state advertisement, and the link state databases of the routers at the two ends are asynchronous; at this time, a routing loop is formed in the process of running the optimal path calculated by the SPF, and data packet transmission cannot be completed. Fig. 1 is a networking environment formed by four routers, and as shown in fig. 1, the cost value of the link interface of the router 2 connected to the router 4 is 10, and the cost values of the rest of the link interfaces are all 1. When the router 4 notifies the destination D and the link state databases are identical, the router 1 performs the SPF calculation to reach the destination D through the router 3 to reach the router 4, and the router 2 performs the SPF calculation to reach the destination D through the router 1 and the router 3 to reach the router 4. Assuming that the memory usage in the router 1 reaches the maximum value, no redundant storage space is available to store the router link state advertisement advertised by the router 3 into its own database; at this time, the router 1 runs the SPF to calculate that the optimal path to reach D is the path 1 passing through the router 2, while the router 2 runs the SPF to calculate that the optimal path to reach D is the path 2 passing through the routers 1 and 3 to reach the router 4, the data packet sent to the destination D by the router 1 will be sent to the router 2, the data packet with the destination D will be sent to the router 1 by the router 2, and the data packet sent to the destination D will be transmitted back and forth between the router 1 and the router until the lifetime is 0, that is, a routing loop appears. The routing loop causes that the data message cannot be transmitted to a destination route, and normal transmission of the data message is influenced.

Disclosure of Invention

In order to solve the above technical problem, the present invention provides a method and an apparatus for implementing link status notification processing. Routing loops in SPF calculation caused by LSA storage failure can be avoided.

In order to achieve the object of the present invention, the present invention provides a method for implementing link state advertisement processing, including:

when the router fails to store the Link State Advertisement (LSA), generating the LSA added with the distinguishing identifier;

and flooding the LSA added with the distinguishing identifier to other routers in the network, so that when the routers generating the LSA added with the distinguishing identifier are added to the SPF tree by running the Shortest Path First (SPF) calculation optimal path, the other routers do not add the neighbor routers to the SPF candidate list.

Further, when generating an LSA added with a distinguishing identifier, the method further includes:

setting the router with the LSA failure storage to enter a wait state, setting corresponding waiting time according to the LSA failure storage frequency, and storing the LSA with the failure storage again when the waiting time is up;

the waiting time is less than a preset maximum time threshold.

Further, setting the corresponding waiting time according to the number of times of LSA storage failure specifically includes:

presetting unit waiting time length, and setting corresponding waiting time length according to the failure times of storing the LSA;

the waiting time is equal to the product of the failure times of storing LSA failure and the preset unit waiting time.

Further, when the number of times of LSA storage failure is greater than 1, the waiting time is set through an exponential backoff mechanism.

Further, the step of restoring the LSA with failed storage specifically includes:

when the waiting time length is up, the router which fails to store the LSA exits the waiting wait state;

when the LSA failed to be stored comes from other routers, receiving and storing the LSA failed to be stored retransmitted by other routers;

and when the LSA failed in storage is the LSA generated by the router, the router regenerates and stores the LSA failed in storage.

In another aspect, the present application further provides an apparatus for implementing link state advertisement processing, including: a generation unit and a flooding unit; wherein,

the generating unit is used for generating the LSA added with the distinguishing identifier when the router fails to store the LSA;

and the flooding unit is used for flooding the LSA added with the distinguishing identifier to other routers in the network so that when the routers which generate the LSA added with the distinguishing identifier are added to the SPF tree in the operation of the SPF calculation optimal path, the other routers do not add the neighbor routers to the SPF candidate list.

Further, the device also comprises a waiting setting unit and a re-storing unit,

the waiting setting unit is used for setting the router with the LSA failure to enter a wait waiting state when the generation unit generates the LSA added with the distinguishing identifier, and setting corresponding waiting duration according to the frequency of LSA failure;

the storing unit is used for storing the LSA which fails to be stored again when the waiting time length is up;

the waiting time is less than a preset maximum time threshold.

Further, the waiting time is equal to the product of the failure times of storing the LSA failure and the preset unit waiting time.

Further, the waiting setting unit is specifically configured to, when the generation unit generates the LSA to which the distinguishment flag is added, set the router in which the LSA storage failure occurs to enter a wait waiting state,

when the number of times of storing LSA failure is 1, setting a product of preset unit waiting time length as the waiting time length;

and when the failure times of storing the LSA are more than 1, setting the waiting time length through an exponential backoff mechanism.

Further, the re-storing unit is specifically adapted to,

when the waiting time length is up, the router which fails to store the LSA exits the wait state;

Compared with the prior art, the technical scheme of the application comprises the following steps: when the router fails to store the LSA, generating the LSA added with the distinguishing identifier; flooding the LSA added with the distinguishing identifier to other routers in the network, so that the other routers do not add the neighbor routers to the SPF candidate list when the router generating the LSA added with the distinguishing identifier is added to the SPF tree by running the SPF calculation optimal path. The method generates the LSA added with the distinguishing identifier when the LSA is failed to be stored, so that other routers do not add neighbor routers to an SPF candidate list when the router which generates the LSA added with the distinguishing identifier is added to an SPF tree when the router which runs an SPF calculation optimal path and the LSA added with the distinguishing identifier is added to the SPF tree, thereby avoiding routing loops caused by the failure of storing the LSA and ensuring the normal transmission of data messages.

Drawings

The accompanying drawings, which are included to provide a further understanding of the invention and are incorporated in and constitute a part of this application, illustrate embodiment(s) of the invention and together with the description serve to explain the invention without limiting the invention. In the drawings:

FIG. 1 is a networking environment formed by four routers;

FIG. 2 is a flow chart of a method of implementing a link state advertisement process in accordance with the present invention;

FIG. 3 is a block diagram of an apparatus for implementing the link state advertisement process according to the present invention;

FIG. 4 is a flowchart illustrating a processing method for failure to store an LSA according to a first embodiment of the present invention;

FIG. 5 is a flow chart of a method for a router to exit from a wait state;

FIG. 6 is a flowchart of a method according to a third embodiment of the present invention.

Detailed Description

In order to make the objects, technical solutions and advantages of the present invention more apparent, embodiments of the present invention will be described in detail below with reference to the accompanying drawings. It should be noted that the embodiments and features of the embodiments in the present application may be arbitrarily combined with each other without conflict.

Fig. 2 is a flowchart of a method for implementing a link state advertisement process according to the present invention, as shown in fig. 2, including:

step 200, when the router fails to store the Link State Advertisement (LSA), generating the LSA added with the distinguishing identifier;

it should be noted that the failure to store the LSA may be determined by parameter information fed back by the router; adding a distinguishing identifier on the generated LSA, adding a distinguishing identifier on a data frame which is not used by the LSA, for example, adding OVER as the distinguishing identifier on the data frame which is not used after the LSA length frame, or expanding a new data frame on the generated LSA for adding the distinguishing identifier, wherein the method for adding the distinguishing identifier is a conventional technical means of a person skilled in the art;

step 201, flooding the LSA added with the distinguishing identifier to other routers in the network, so that when the other routers operate the Shortest Path First (SPF) to calculate the optimal path and add the router generating the LSA added with the distinguishing identifier to the SPF tree, the neighbor routers are not added to the SPF candidate list.

When generating the LSA added with the distinguishing identifier, the method of the invention further comprises the following steps:

setting the router with the LSA failure to enter a wait state, and setting corresponding wait duration according to the number of LSA failure times;

when the waiting time length is up, the LSA which fails to be stored is stored again;

the waiting time is less than the preset maximum time threshold.

Preferably, the waiting time period is equal to the product of the failure times of storing the LSA failure and the preset unit waiting time period.

It should be noted that the unit waiting time is an empirical value of those skilled in the art, and is generally considered to be 200 milliseconds by default. The maximum duration threshold is also set based on empirical values by those skilled in the art. Modifying the wait duration may be accomplished by a back-off algorithm.

Preferably, when the number of times of LSA storage failure is greater than 1, the waiting duration is set by an exponential backoff mechanism.

Preferably, the step of restoring the LSA with failed storage specifically includes:

when the waiting time length is reached, the router which stores LSA failure exits the wait waiting state;

and when the LSA failed to be stored is the LSA generated by the router, the router regenerates and stores the LSA failed to be stored.

After the LSA that fails to be stored is stored, according to the conventional method, the router feeds back the information that the storage is completed to other routers in the network, so that when the other routers perform SPF calculation, the router that newly stores the LSA is added to the SPF tree, and the optimal path is calculated.

The method generates the LSA added with the distinguishing identifier when the LSA is failed to be stored, so that other routers do not add neighbor routers to an SPF candidate list when the router which generates the LSA added with the distinguishing identifier is added to an SPF tree when the router which runs an SPF calculation optimal path and the LSA added with the distinguishing identifier is added to the SPF tree, thereby avoiding routing loops caused by the failure of storing the LSA and ensuring the normal transmission of data messages. Fig. 3 is a structural diagram of an apparatus for implementing a link status advertisement process according to the present invention, as shown in fig. 3, including: a generation unit and a flooding unit; wherein,

The apparatus of the present invention further comprises a wait setting unit and a re-storing unit,

and the waiting setting unit is used for setting the router with the LSA failure in storing the LSA to enter a wait waiting state when the generation unit generates the LSA added with the distinguishing identifier, and setting corresponding waiting time according to the failure times of storing the LSA.

The waiting setting unit is specifically configured to, when the generation unit generates the LSA with the added distinguishment flag, set the router with the LSA failure to enter wait waiting state,

the waiting time is less than the preset maximum time threshold.

The re-storage unit is used in particular for,

when the LSA failed to be stored comes from other routers, receiving and storing the LSA failed to be stored retransmitted by the other routers;

The process of the present invention is illustrated in clear detail below by means of specific examples, which are provided only for illustrating the present invention and are not intended to limit the scope of the process of the present invention.

Example 1

In this embodiment, the method of the present invention is clearly and specifically described by taking the LSA storage failure as an example, the LSA storage failure in this embodiment may be a received LSA from another router in the network, or may be an LSA generated by the router itself. The reason for the storage failure may be that the memory of the router reaches a maximum value.

Fig. 4 is a flowchart of a processing method when storing an LSA fails according to a first embodiment of the present invention, as shown in fig. 4, including:

step 400, when storing LSA fails, judging whether the router is in wait state, if not, executing step 4010; otherwise, step 4020 is performed.

Step 4010, generating an LSA added with a distinguishing identifier and flooding the LSA to other routers in the network, and setting the wait duration of the wait state as a unit wait duration;

after other routers receive the LSAs with the distinguishing identifications, constructing an SPF tree, and adding the router which generates the LSAs added with the distinguishing identifications into the SPF tree, the neighbor routers are not added into an SPF candidate list, namely, the other routers do not take the router with storage failure as a router for forwarding a next hop.

Step 4020, if the router is in the wait state, judging whether the waiting time length is equal to the maximum time length threshold value, and not executing the step 4021; otherwise, 4022 is performed;

step 4021, setting the product of the failure times of storing the LSA and the unit waiting time as the waiting time through an exponential backoff mechanism.

Step 4022, keeping the waiting time length equal to the maximum time length threshold unchanged.

Example 2

Fig. 5 is a flowchart of a method for a router to exit from the wait state, as shown in fig. 5, including:

step 500, the router is in wait state when the waiting time is not reached;

step 501, when the waiting time length is up, the router exits the wait state;

step 502, the router stores the failed LSA again, and generates the LSA without the distinguishing identifier to other routers after the storage is completed, so that the neighbor routers are added to the SPF candidate list when the other routers run the SPF to calculate the optimal path. I.e., other routers may consider neighboring routers as forwarding next hop routers.

Example 3

The router floods and adds the LSA with the distinguishing identifier to other routers in the network, the other routers need to correspondingly modify the flow of running the SPF to calculate the optimal path, and when the router with the LSA with the distinguishing identifier added is added to the SPF tree, the neighbor router is not added to the SPF candidate list, so that the router with the LSA failure in storing the LSA is ensured not to be used as the router for forwarding the next hop, and the possible routing loop is avoided. Fig. 6 is a flowchart of a method according to a third embodiment of the present invention, as shown in fig. 6, including:

step 600, the router running the SPF adds itself to the candidate list of the optimal path with a cost value of 0;

step 601, selecting the router with the minimum expense value from the candidate list, and adding the router into the SPF tree.

Step 602, judging that the LSA of the router has a distinguishing identifier; otherwise, go to step 603; if yes, return to step 601;

step 603, link of the neighbor router is processed.

Step 604, judging that the link check of the router passes; if yes, go to step 6050; otherwise, step 6060 is performed.

Step 6050, calculate the cost value of the root router to reach the next hop router N of the neighbor router. Here, router N is the next hop.

Step 6060, judge whether there is a link of other unprocessed neighbor routers; if yes, return to step 603; otherwise, step 60521 is performed.

Step 6051, judge that the neighbor router is already in the candidate list; instead, 60520 is performed; yes, 60530 is performed;

step 60520, add the neighbor router to the candidate list.

Step 60521, judging whether unprocessed neighbor router links exist; if yes, return to step 603; if not, go to step 60522;

step 60522, judging the candidate list is empty; if yes, go to step 60523; otherwise, return to step 601.

Step 60523, the SPF calculation is finished;

step 60530, determining that the calculated cost value is less than the known cost value; if yes, go to step 605310; otherwise, step 605320 is performed.

And step 605310, modifying the cost value of the neighbor router into the cost value of the next hop for the root router to reach the neighbor router, and determining the next hop to be the router N. Step 60521 is then performed.

Step 605320, determining the cost value is equal to the known cost value; if yes, go to step 605321; otherwise, return to step 6060.

Step 605321, after adding the next hop list known to the neighbor router, proceed to step 6060.

Although the embodiments of the present invention have been described above, the above description is only for the convenience of understanding the present invention, and is not intended to limit the present invention. It will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims.

Claims

1. A method for implementing link state advertisement processing, comprising:

2. The method of claim 1, wherein when generating the LSA with the addition of the distinguishing identifier, the method further comprises:

the waiting time is less than a preset maximum time threshold.

3. The method of claim 2, wherein the setting the corresponding waiting duration according to the number of times of storing the LSA failure specifically comprises:

4. The method of claim 3, wherein setting the wait duration is performed by an exponential backoff mechanism when the number of times the LSA fails to be stored is greater than 1.

5. The method according to any of claims 2 to 4, wherein the re-storing the LSA that failed storage specifically comprises:

6. An apparatus for implementing link state advertisement processing, comprising: a generation unit and a flooding unit; wherein,

7. The apparatus of claim 6, further comprising a wait setting unit and a restore unit,

the waiting time is less than a preset maximum time threshold.

8. The apparatus of claim 7, wherein the wait period is equal to a product of a number of failures to store the LSA and a predetermined unit wait period.

9. The apparatus of claim 8, wherein the waiting setting unit is specifically configured to, when the generation unit generates the LSA with the added distinguishment flag, set the router with the LSA failure to enter wait waiting state,

10. The device according to any one of claims 6 to 9, wherein the re-storage unit is particularly adapted to,