TRILL shortest path first implementation

• US 8,902,759 B2
• Filed: 10/08/2012
• Issued: 12/02/2014
• Est. Priority Date: 10/08/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bond, David M., Kaushik, Meenakshi R.
• Primary Examiner(s): ROSE, KERRI M
• Application Number:
  US13/647,311
• Publication Number:
  US 20140098703A1
• Time in Patent Office: 785 Days
• Field of Search: 370/235, 370/238, 370/252, 370/254
• US Class Current: 370/238
• CPC Class Codes: H04L 45/028 Dynamic adaptation of the update intervals, e.g. event-triggered updates
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's

Abstract

A shortest path first (SPF) computation in a distributed network may be performed efficiently by performing the SPF computation in stages. Rather than perform a new SPF computation every time a change occurs affecting a link state within the distributed network, a routing protocol may identify the change and determine if the impact to the link state necessarily needs the new SPF computation. For example, a predetermined list of events may identify changes that may not necessarily impact the SPF value(s) currently associated with the distributed network. Embodiments disclosed may avoid computation of the new SPF for changes to the link state thus managing network system resources more efficiently.

Claims

1. A computer program product for performing a Shortest Path First (SPF) computation in a network, the computer program product comprising a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code being configured to:

identify a plurality of network elements connected together as a distributed network, operating under a link state protocol (LSP);

identify a change in network topology in the LSP occurring in the distributed network;

determine whether the change in network topology in the LSP impacts an SPF value on the distributed network; and

perform the SPF computation in the distributed network only when the change in the LSP impacts the SPF value.

2. The computer program product of claim 1, wherein the distributed network operates under a Transparent Interconnect of Lots of Links (TRILL) standard.

3. The computer program product of claim 1, wherein the distributed network operates under an Intermediate System to Intermediate System (IS-IS) routing protocol.

4. The computer program product of claim 1, wherein the change in network topology in the LSP includes a neighbor identification change.

5. The computer program product of claim 1, wherein the change in network topology in the LSP includes a change in a distribution tree.

6. The computer program product of claim 5, the computer-readable program code being configured to compute the SPF computation only for a multicast distribution.

7. The computer program product of claim 1, wherein the change in network topology in the LSP includes a name change among the network elements.

8. A network system, comprising:

a plurality of network elements connected together in a distributed network; and

a server connected to the distributed network, the server being configured to;

identify a change in status of one of the network elements in the distributed network,

reference a list of predetermined events,

determine whether the change in status of one of the network elements corresponds to one of the predetermined events, and

compute a shortest path first (SPF) value for the distributed network if the change in status of one of the network elements is not one of the predetermined events.

9. The network system of claim 8, wherein the change in status of one of the network elements is a change to a link state protocol (LSP).

10. The network system of claim 9, wherein the change to the LSP triggers computation of the SPF value according to a series of determinations.

11. The network system of claim 8, wherein the distributed network operates under a Transparent Interconnect of Lots of Links (TRILL) standard.

12. The network system of claim 8, wherein the distributed network operates under an Intermediate System to Intermediate System (IS-IS) routing protocol.

13. The network system of claim 8, wherein the list of predetermined events includes events in which the SPF value is computed for either a unicast distribution tree or a multicast distribution tree.