IP Library › Granted Patent US 10,404,573
Granted Patent B2
US 10,404,573 · App. 16/089,112 · Granted Sep 3, 2019

Efficient method to aggregate changes and to produce border gateway protocol link-state (BGP-LS) content from intermediate system to intermediate system (IS-IS) link-state database

Inventors: Amarnath Ammireddy (San Jose, CA); Uma S. Chunduri (Fremont, CA); Vasant S. Patil (San Jose, CA)
Assignee: Telefonaktiebolaget LM Ericsson (publ)
H04L45/021H04L45/02H04L45/04H04L45/54
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 10,404,573
App. No.
16/089,112
Granted
Sep 3, 2019
Kind
B2
Abstract

A method is implemented by a network device functioning as a Border Gateway Protocol (BGP) speaker to transmit aggregated link-state information pertaining to a network in which the network device operates to a peer BGP speaker. The method includes storing, in a link-state database, node entries representing nodes in the network, fragment entries representing fragments received from nodes in the network, and link/prefix entries representing links/prefixes in the network. Each link/prefix entry is assigned a state from a possible set of states, where the possible set of states include a new entry state, a modified entry state, a deleted entry state, and an unmodified entry state. The method further includes determining link-state information to transmit to the peer BGP speaker based on a state assigned to a link/prefix entry, and transmitting the determined link-state information to the peer BGP speaker.

Claims (92)

1. A method implemented by a network device functioning as a Border Gateway Protocol (BGP) speaker to transmit aggregated link-state information pertaining to a network in which the network device operates to a peer BGP speaker, the method comprising:

storing, in a link-state database, node entries representing nodes in the network, fragment entries representing fragments received from nodes in the network, and link/prefix entries representing links/prefixes in the network, wherein each node entry is associated with a set of fragment entries and each fragment entry is associated with a set of link/prefix entries, and wherein each fragment entry and link/prefix entry is assigned a version number and each link/prefix entry is assigned a state from a possible set of states, wherein the possible set of states include a new entry state, a modified entry state, a deleted entry state, and an unmodified entry state;

determining link-state information to transmit to the peer BGP speaker based on a state assigned to a link/prefix entry; and

transmitting the determined link-state information to the peer BGP speaker.

2. The method of claim 1 , wherein determining link-state information to transmit to the peer BGP speaker includes determining that link-state information for a link/prefix should be transmitted to the peer BGP speaker in response to a determination that a link/prefix entry representing that link/prefix is assigned the new entry state or the modified entry state.

3. The method of claim 1 , wherein determining link-state information to transmit to the peer BGP speaker includes determining that link-state information for deletion of a link/prefix should be transmitted to the peer BGP speaker in response to a determination that a link/prefix entry representing that link/prefix is assigned the deleted entry state.

4. The method of claim 1 , wherein determining link-state information to transmit to the peer BGP speaker includes determining that link-state information for a link/prefix should not be transmitted to the peer BGP speaker in response to a determination that a link/prefix entry representing that link/prefix is assigned the unmodified entry state.

5. The method of claim 1 , further comprising:

receiving a fragment from a node in the network, wherein the fragment advertises link-state information for a link/prefix;

creating, in the link-state database, a new link/prefix entry representing the link/prefix in response to a determination that a link/prefix entry representing that link/prefix does not exist in the link-state database;

associating the new link/prefix entry representing the link/prefix with a fragment entry representing the received fragment;

assigning an updated version number to the fragment entry representing the received fragment;

assigning the updated version number to the new link/prefix entry representing the link/prefix; and

assigning the new entry state to the new link/prefix entry representing the link/prefix.

6. The method of claim 1 , further comprising:

receiving a fragment from a node in the network, wherein the fragment advertises link-state information for a link/prefix;

assigning an updated version number to a fragment entry representing the received fragment;

assigning the updated version number to a link/prefix entry representing the link/prefix;

updating a content of the link/prefix entry representing the link/prefix with a content of the link-state information for the link/prefix included in the received fragment in response to a determination that the content of the link/prefix entry representing the link/prefix is different from the content of the link-state information for the link/prefix included in the received fragment and that the link/prefix entry representing the link/prefix is assigned the unmodified entry state; and

assigning the modified entry state to the link/prefix entry representing the link/prefix.

7. The method of claim 1 , further comprising:

receiving a fragment from a node in the network, wherein the fragment advertises link-state information for a link/prefix;

assigning an updated version number to a fragment entry representing the received fragment;

assigning the updated version number to a link/prefix entry representing the link/prefix; and

updating a content of the link/prefix entry representing the link/prefix with a content of the link-state information for the link/prefix included in the received fragment without assigning a new state to the link/prefix entry representing the link/prefix in response to a determination that the link/prefix entry representing the link/prefix is assigned the new entry state or the modified entry state.

8. The method of claim 1 , further comprising:

assigning the deleted entry state to a link/prefix entry representing a link/prefix in response to a determination that a version number assigned to the link/prefix entry representing the link/prefix lags behind a version number assigned to a fragment entry associated with the link/prefix entry representing the link/prefix.

9. The method of claim 8 , further comprising:

receiving a fragment from a node in the network, wherein the fragment advertises link-state information for the link/prefix;

assigning an updated version number to a fragment entry representing the received fragment;

assigning the updated version number to the link/prefix entry representing the link/prefix; and

assigning the unmodified entry state to the link/prefix entry representing the link/prefix in response to a determination that a content of the link/prefix entry representing the link/prefix matches a content of the link-state information for the link/prefix included in the received fragment and that the link/prefix entry representing the link/prefix is assigned the deleted entry state.

10. The method of claim 8 , further comprising:

receiving a fragment from a node in the network, wherein the fragment advertises link-state information for the link/prefix;

assigning an updated version number to a fragment entry representing the received fragment;

assigning the updated version number to the link/prefix entry representing the link/prefix;

updating a content of the link/prefix entry representing the link/prefix with a content of the link-state information for the link/prefix included in the received fragment in response to a determination that a content of the link/prefix entry representing the link/prefix is different from a content of the link-state information for the link/prefix included in the received fragment and that the link/prefix entry representing the link/prefix is assigned the deleted entry state; and

assigning the modified entry state to the link/prefix entry representing the link/prefix.

11. The method of claim 1 , wherein the determined link-state information is transmitted to the peer BGP speaker via Border Gateway Protocol Link-State (BGP-LS).

12. The method of claim 1 , further comprising:

storing global link/prefix entries representing links/prefixes advertised in the network in the link-state database, wherein each global link/prefix entry is assigned a fragment number.

13. The method of claim 12 , further comprising:

receiving a fragment from a node in the network, wherein the fragment advertises link-state information for a link/prefix;

creating, in the link-state database, a new global link/prefix entry representing the link/prefix in response to a determination that a global link/prefix entry representing that link/prefix does not exist in the link-state database; and

assigning a fragment number of the received fragment to the new global link/prefix entry representing the link/prefix.

14. The method of claim 12 , further comprising:

receiving a fragment from a node in the network, wherein the fragment advertises link-state information for a link/prefix; and

assigning a fragment number of the received fragment to a global link/prefix entry representing the link/prefix.

15. The method of claim 12 , further comprising:

receiving a fragment from a node in the network, wherein the fragment advertises link-state information that indicates that a link/prefix should be deleted; and

deleting a global link/prefix entry representing the link/prefix from the link-state database in response to a determination that a fragment number of the received fragment matches a fragment number assigned to the global link/prefix entry representing the link/prefix.

16. The method of claim 12 , wherein link-state information for a link/prefix is transmitted to the peer BGP speaker if a global link/prefix entry representing that link/prefix exists in the link-state database.

17. A network device configured to act as a Border Gateway Protocol (BGP) speaker, the network device to transmit aggregated link-state information pertaining to a network in which the network device operates to a peer BGP speaker, the network device comprising:

a link-state database to store link-state information pertaining to a network in which the network device operates;

a set of one or more processors; and

a non-transitory machine-readable storage medium having stored therein a link-state module, which when executed by the set of one or more processors, causes the network device to store, in the link-state database, node entries representing nodes in the network, fragment entries representing fragments received from nodes in the network, and link/prefix entries representing links/prefixes in the network, wherein each node entry is associated with a set of fragment entries and each fragment entry is associated with a set of link/prefix entries, and wherein each fragment entry and link/prefix entry is assigned a version number and each link/prefix entry is assigned a state from a possible set of states, wherein the possible set of states include a new entry state, a modified entry state, a deleted entry state, and an unmodified entry state, wherein the link-state module, when executed by the set of one or more processors, further causes the network device to determine link-state information to transmit to the peer BGP speaker based on a state assigned to a link/prefix entry and transmit the determined link-state information to the peer BGP speaker.

18. The network device of claim 17 , wherein the link-state module, when executed by the set of one or more processors, further causes the network device to receive a fragment from a node in the network, wherein the fragment advertises link-state information for a link/prefix, create, in the link-state database, a new link/prefix entry representing the link/prefix in response to a determination that a link/prefix entry representing that link/prefix does not exist in the link-state database, associate the new link/prefix entry representing the link/prefix with a fragment entry representing the received fragment, assign an updated version number to the fragment entry representing the received fragment, assign the updated version number to the new link/prefix entry representing the link/prefix, and assign the new entry state to the new link/prefix entry representing the link/prefix.

19. A non-transitory machine-readable medium having computer code stored therein, which when executed by a set of one or more processors of a network device acting as a Border Gateway Protocol (BGP) speaker, causes the network device to perform operations for transmitting aggregated link-state information pertaining to a network in which the network device operates to a peer BGP speaker, the operations comprising:

storing, in a link-state database, node entries representing nodes in the network, fragment entries representing fragments received from nodes in the network, and link/prefix entries representing links/prefixes in the network, wherein each node entry is associated with a set of fragment entries and each fragment entry is associated with a set of link/prefix entries, and wherein each fragment entry and link/prefix entry is assigned a version number and each link/prefix entry is assigned a state from a possible set of states, wherein the possible set of states include a new entry state, a modified entry state, a deleted entry state, and an unmodified entry state;

determining link-state information to transmit to the peer BGP speaker based on a state assigned to a link/prefix entry; and

transmitting the determined link-state information to the peer BGP speaker.

20. The non-transitory machine-readable medium of claim 19 , wherein the computer code, when executed by the set of one or more processors of the network device, causes the network device to perform further operations comprising:

receiving a fragment from a node in the network, wherein the fragment advertises link-state information for a link/prefix;

creating, in the link-state database, a new link/prefix entry representing the link/prefix in response to a determination that a link/prefix entry representing that link/prefix does not exist in the link-state database;

associating the new link/prefix entry representing the link/prefix with a fragment entry representing the received fragment;

assigning an updated version number to the fragment entry representing the received fragment;

assigning the updated version number to the new link/prefix entry representing the link/prefix; and

assigning the new entry state to the new link/prefix entry representing the link/prefix.

21. The non-transitory machine-readable medium of claim 19 , wherein the computer code, when executed by the set of one or more processors of the network device, causes the network device to perform further operations comprising:

receiving a fragment from a node in the network, wherein the fragment advertises link-state information for a link/prefix;

assigning an updated version number to a fragment entry representing the received fragment;

assigning the updated version number to a link/prefix entry representing the link/prefix;

updating a content of the link/prefix entry representing the link/prefix with a content of the link-state information for the link/prefix included in the received fragment in response to a determination that the content of the link/prefix entry representing the link/prefix is different from the content of the link-state information for the link/prefix included in the received fragment and that the link/prefix entry representing the link/prefix is assigned the unmodified entry state; and

assigning the modified entry state to the link/prefix entry representing the link/prefix.

22. The non-transitory machine-readable medium of claim 19 , wherein the computer code, when executed by the set of one or more processors of the network device, causes the network device to perform further operations comprising:

receiving a fragment from a node in the network, wherein the fragment advertises link-state information for a link/prefix;

assigning an updated version number to a fragment entry representing the received fragment;

assigning the updated version number to a link/prefix entry representing the link/prefix; and

updating a content of the link/prefix entry representing the link/prefix with a content of the link-state information for the link/prefix included in the received fragment without assigning a new state to the link/prefix entry representing the link/prefix in response to a determination that the link/prefix entry representing the link/prefix is assigned the new entry state or the modified entry state.

23. The non-transitory machine-readable medium of claim 19 , wherein the computer code, when executed by the set of one or more processors of the network device, causes the network device to perform further operations comprising:

assigning the deleted entry state to a link/prefix entry representing a link/prefix in response to a determination that a version number assigned to the link/prefix entry representing the link/prefix lags behind a version number assigned to a fragment entry associated with the link/prefix entry representing the link/prefix.

24. The non-transitory machine-readable medium of claim 23 , wherein the computer code, when executed by the set of one or more processors of the network device, causes the network device to perform further operations comprising:

receiving a fragment from a node in the network, wherein the fragment advertises link-state information for the link/prefix;

assigning an updated version number to a fragment entry representing the received fragment;

assigning the updated version number to the link/prefix entry representing the link/prefix; and

assigning the unmodified entry state to the link/prefix entry representing the link/prefix in response to a determination that a content of the link/prefix entry representing the link/prefix matches a content of the link-state information for the link/prefix included in the received fragment and that the link/prefix entry representing the link/prefix is assigned the deleted entry state.

25. The non-transitory machine-readable medium of claim 23 , wherein the computer code, when executed by the set of one or more processors of the network device, causes the network device to perform further operations comprising:

receiving a fragment from a node in the network, wherein the fragment advertises link-state information for the link/prefix;

assigning an updated version number to a fragment entry representing the received fragment;

assigning the updated version number to the link/prefix entry representing the link/prefix;

updating a content of the link/prefix entry representing the link/prefix with a content of the link-state information for the link/prefix included in the received fragment in response to a determination that a content of the link/prefix entry representing the link/prefix is different from a content of the link-state information for the link/prefix included in the received fragment and that the link/prefix entry representing the link/prefix is assigned the deleted entry state; and

assigning the modified entry state to the link/prefix entry representing the link/prefix.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Sep 27, 2018
From: AMMIREDDY, AMARNATH; CHUNDURI, UMA S.; PATIL, VASANT S.
To: TELEFONAKTIEBOLAGET LM ERICSSON (PUBL)
Reel/Frame 047000/0305 →
Continuity (3)
Provisional Application 62314293 · Mar 28, 2016
Provisional Application 62314284 · Mar 28, 2016
Related Publication 20190132232A1 · May 2, 2019
Cited By (1)
US 12,348,406