Link state identifier collision handling

• US 8,855,113 B2
• Filed: 09/12/2012
• Issued: 10/07/2014
• Est. Priority Date: 08/20/2009
• Status: Expired due to Fees

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Lu, Wenhu, Lindem, Alfred C. III, Chunduri, Uma S.
• Primary Examiner(s): Zhao, Wei
• Application Number:
  US13/611,981
• Publication Number:
  US 20130003731A1
• Time in Patent Office: 755 Days
• Field of Search: 370/389, 709/235
• US Class Current: 370/389
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols

Abstract

Methods and apparatus for a network element to handle LSID collisions to prevent different LSAs associated with different routes from sharing the same LSID. According to one embodiment, responsive to determining that a tentative LSID that is generated for a first route that is being added collides with an LSID that is assigned to an LSA for a second route, and that one of the first and second routes is a host route, the host route is suppressed. If the first route is the host route, suppressing includes not originating an LSA for the first route. If the second route is the host route, suppressing includes purging the LSA for the second route and not originating an LSA for the second route. Although the host route is suppressed, network reachability of the range subsuming the host route is provided through the route that is not the host route.

Claims

1. A method performed in a network element implementing an Open Shortest Path First (OSPF) protocol for avoiding Link State Identifier (LSID) collisions when assigning LSIDs to identify link state advertisements (LSAs) originated by the network element, the method comprising:

originating a first LSA for a first route, wherein the first LSA includes a first LSID, and wherein the first route is a first host route having at first route mask that is a host mask;

determining to originate a second LSA for a second route;

generating a tentative second LSID for the second route; and

responsive to the tentative second LSID being the same as the first LSID and the first route being the first host route,

suppressing the first LSA of the first route to avoid a LSID collision, and

originating the second LSA for the second route, wherein the second LSA includes the tentative LSID.

2. The method of claim 1, further comprising:

responsive to a withdrawal of the second route, originating the first LSA of the first route.

3. The method of 1, further comprising:

originating a third LSA for a third route, wherein the third LSA includes a third LSID;

determining to originate a fourth LSA for a fourth route, wherein the fourth route is a second host route having a second route mask that is the host mask;

generating a tentative fourth LSID for the fourth route; and

responsive to the tentative fourth LSID being the same as the third LSID and the fourth route being the second host route, suppressing the fourth LSA of the fourth route to avoid a LSID collision.

4. The method of 3, further comprising:

responsive to a withdrawal of the third route, originating the fourth LSA of the fourth route.

5. The method of 1, wherein said suppressing of the first LSA comprises not originating the first LSA.

6. The method of 5, wherein said suppressing of the first LSA further comprises purging a record for the first route from a link state database (LSDB).

7. The method of 5, wherein said suppressing of the first LSA further comprises modifying a record of a routing information base (RIB) to indicate that the first route is being suppressed.

8. The method of 1, wherein said tentative second LSID is based upon a network address of the second route and a route mask of the second route.

9. A method performed in a network element implementing an Open Shortest Path First (OSPF) protocol for avoiding Link State Identifier (LSID) collisions when assigning LSIDs to identify link state advertisements (LSAs) originated by the network element, the method comprising:

originating a first LSA for a first route, wherein the first LSA includes a first LSID;

determining to originate a second LSA for a second route, wherein the second route is a first host route having a first route mask that is a host mask;

generating a tentative second LSID for the second route; and

responsive to the tentative second LSID being the same as the first LSID and the second route being the first host route, suppressing the second LSA of the second route to avoid a LSID collision.

10. The method of claim 9, further comprising:

responsive to a withdrawal of the first route, originating the second LSA of the second route.

11. The method of claim 9, further comprising:

originating a third LSA for a third route, wherein the third LSA includes a third LSID, and wherein the third route is a second host route having a second route mask that is the host mask;

determining to originate a fourth LSA for a fourth route;

generating a tentative fourth LSID for the fourth route; and

responsive to the tentative fourth LSID being the same as the third LSID and the third route being the second host route,

suppressing the third LSA of the third route to avoid a LSID collision, and

originating the fourth LSA for the fourth route, wherein the fourth LSA includes the tentative LSID.

12. The method of claim 11, further comprising:

responsive to a withdrawal of the fourth route, originating the third LSA of the third route.

13. The method of 9, wherein said suppressing of the second LSA comprises not originating the second LSA.

14. The method of 13, wherein said suppressing of the second LSA further comprises purging a record for the second route from a link state database (LSDB).

15. The method of 13, wherein said suppressing of the second LSA further comprises modifying a record of a routing information base (RIB) to indicate that the second route is being suppressed.

16. The method of 9, wherein said tentative second LSID is based upon a network address of the second route and a route mask of the second route.

17. A system that avoids Open Shortest Path First (OSPF) Link State Identifier (LSID) collisions by preventing origination of link state advertisements (LSAs) for different routes having a same LSID, the system comprising:

a first router that learns OSPF routes from a second router; and

the second router that distributes the OSPF routes to the first router, the second router comprising;

an OSPF module that implements the OSPF protocol, generates LSAs, and assigns LSIDs to the LSAs, wherein during said LSID assignment the OSPF module;

suppresses those of the OSPF routes that are host routes and would have LSIDs that collide with other LSIDs of LSAs that are not for host routes; and

upon a withdrawal of an OSPF route having an LSID that would have collided with an LSID of one of the suppressed OSPF routes, originates the one of the suppressed OSPF routes.

18. The system of claim 17, wherein the OSPF module further:

for each suppressed OSPF route of the suppressed OSPF routes, associates the suppressed OSPF route with an OSPF route having an LSA already originated by the second router having a LSID that would have collided with the LSID of the suppressed OSPF route.

20. The system of claim 17, wherein the second router further includes the following:

a local OSPF routing information base (RIB) that stores the OSPF routes;

a link state database (LSDB);

wherein the OSPF module further maintains the suppressed host routes in the local OSPF RIB; and

wherein the OSPF module further adds LSAs for those of the OSPF routes that are not suppressed into the LSDB.

19. The system of 17, wherein the OSPF module further:

purges entries of a link state database (LSDB) corresponding to those suppressed OSPF routes; and

maintains entries of a local OSPF routing information base (RIB) for those suppressed OSPF routes.

21. A network element that avoids Open Shortest Path First (OSPF) Link State Identifier (LSID) collisions by preventing origination of link state advertisements (LSAs) for different routes having a same LSID, the network element comprising:

a non-transitory computer-readable storage medium to store code; and

a set of one or more processors coupled to the non-transitory computer-readable storage medium, operative to execute the code, the code including;

an OSPF module to originate a plurality of LSAs for a plurality of routes, wherein the OSPF module is configured to;

originate a first LSA for a first route, wherein the first LSA includes a first LSID, and wherein the first route is a host route having a route mask that is a host mask;

determine to originate a second LSA for a second route;

generate a tentative second LSID for the second route;

responsive to the tentative second LSID being the same as the first LSID and the first route being the host route,

suppress the first LSA of the first route to avoid a LSID collision, and

originate the second LSA for the second route, wherein the second LSA includes the tentative LSID; and

responsive to a withdrawal of the second route, originate the first LSA of the first route.

22. A network element that avoids Open Shortest Path First (OSPF) Link State Identifier (LSID) collisions by preventing origination of link state advertisements (LSAs) for different routes having a same LSID, the network element comprising:

a non-transitory computer-readable storage medium to store code; and

a set of one or more processors coupled to the non-transitory computer-readable storage medium, operative to execute the code, the code including;

an OSPF module to originate a plurality of LSAs for a plurality of routes, wherein the OSPF module is configured to;

originate a first LSA for a first route, wherein the first LSA includes a first LSID;

determine to originate a second LSA for a second route, wherein the second route is a host route having a route mask that is a host mask;

generate a tentative second LSID for the second route;

responsive to the tentative second LSID being the same as the first LSID and the second route being the host route, suppress the second LSA of the second route to avoid a LSID collision; and

responsive to a withdrawal of the first route, originate the second LSA of the second route.

23. A network element that avoids Open Shortest Path First (OSPF) Link State Identifier (LSID) collisions by preventing origination of link state advertisements (LSAs) for different routes having a same LSID, the network element comprising:

a non-transitory computer-readable storage medium to store code; and

a set of or more processors coupled to the non-transitory computer-readable storage medium, operative to execute the code, the code including;

an OSPF module to implement the OSPF protocol, originate LSAs for OSPF routes, and assign LSIDs to the LSAs, wherein during said LSID assignment the OSPF module is configured to;

suppress those of the OSPF routes that are host routes and would have LSIDs that collide with other LSIDs of LSAs that are not for host routes; and

upon a withdrawal of an OSPF route having an LSID that would have collided with an LSID of one of the suppressed OSPF routes, originate the one of the suppressed OSPF routes.