Two-part metric for link state routing protocols

• US 9,444,721 B2
• Filed: 09/30/2013
• Issued: 09/13/2016
• Est. Priority Date: 09/30/2013
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Zhang, Zhaohui, Wang, Lili
• Primary Examiner(s): Crompton, Christopher R
• Application Number:
  US14/042,644
• Publication Number:
  US 20150092594A1
• Time in Patent Office: 1,079 Days
• Field of Search: 370/254
• US Class Current: 1/1
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/248 Connectivity information update

Abstract

Techniques are described for utilizing two-part metrics with link state routing protocols of computer networks. For example, link state advertisements communicated by a router convey outbound cost metrics representative of outbound costs for the router to send network traffic to a network, and inbound cost metrics representative of inbound costs to receive network traffic from the network. The techniques may be particularly useful with respect to shared access networks, including broadcast or non-broadcast multi-access networks.

Claims

1. A method comprising:

communicating, in accordance with a layer three link state protocol, link state advertisements (LSAs) between a plurality of layer three routers coupled to an intermediate layer two shared access network, wherein the link state advertisements specify a set of outbound cost metrics representative of respective outbound costs to send network traffic to the intermediate layer two shared access network for each of the plurality of layer three routers and a set of inbound cost metrics representative of respective inbound costs to receive network traffic for each of the plurality layer three routers from the intermediate layer two shared access network;

computing, with a first one of the plurality of layer three routers, a total cost metric for each link through the intermediate layer two shared access network that originates at the first one of the plurality of layer three routers and terminates at each remaining one of the plurality of layer three routers based on one of the outbound cost metrics for the first one of the plurality of layer three routers and the corresponding inbound cost metrics for each of the remaining ones of the plurality of layer three routers;

performing path selection based on the total cost metrics; and

forwarding network traffic based on the path selection.

2. The method of claim 1, wherein each of the plurality of layer three routers communicates its respective one of the set of outbound cost metrics and its respective one of the set of inbound cost metrics in a single LSA.

3. The method of claim 1, further comprising generating a representation of a topology graph of the plurality of layer three routers in which a communication path from the first one of the plurality of layer three routers to a second one of the remaining plurality of layer three routers through the shared access network is represented as a single edge connecting a first node to a second node in the topology graph,

wherein computing the total cost metric comprises computing one of the total cost metrics for the single edge as a summation of the one of the outbound cost metrics for the first one of the plurality of layer three routers and one of the inbound cost metrics for the second one of the plurality of layer three routers,

wherein the method further comprises assigning the one of the total cost metrics to the single edge in the topology graph, and

wherein performing the path selection comprises performing the path selection based on the one of the total cost metrics assigned to the single edge of the topology graph.

4. The method of claim 1, wherein communicating the link state advertisements comprises transmitting, with the first one of the plurality of layer three routers, one of the link state advertisements that specifies both the one of the outbound cost metrics for the first one of the plurality of layer three routers representative of one of the outbound costs from the first one of the plurality of layer three routers to the shared access network and one of the inbound cost metrics for the first one of the plurality of layer three routers representative of one of the inbound costs to the first one of the plurality of layer three routers from the shared access network using a single field of the one of the link state advertisements.

5. The method of claim 4, wherein the single field of the one of the link state advertisements stores the one of the outbound cost metrics for the first one of the plurality of layer three routers but not a corresponding one of the inbound cost metrics for the first one of the plurality of layer three routers, wherein the one of the outbound cost metrics for the first one of the plurality of layer three routers specifies both the one of the outbound cost metrics for the first one of the plurality of layer three routers and the corresponding one of the inbound cost metrics for the first one of the plurality of layer three routers.

6. The method of claim 1, wherein communicating the link state advertisements comprises transmitting, with the first one of the plurality of layer three routers, one of the link state advertisements that specifies the one of the outbound cost metrics for the first one of the plurality of layer three routers representative of one of the outbound costs from the first one of the plurality of layer three routers to the shared access network in a first field of the one of the link state advertisements and one of the inbound cost metrics for the first one of the plurality of layer three routers representative of one of the inbound costs to the first one of the plurality of layer three routers from the shared access network in a second field of the one of the link state advertisements different than the first field.

7. The method of claim 1, wherein communicating the link state advertisements comprises receiving, with the first one of the plurality of layer three routers, one of the link state advertisements that specifies one of the outbound cost metrics for a second one of the plurality of layer three routers representative of one of the outbound costs from the second one of the plurality of layer three routers to the shared access network in a first field of the one of the link state advertisements and one of the inbound cost metrics for the second one of the plurality of layer three routers representative of one of the inbound costs to the second one of the plurality of layer three routers from the shared access network in a second field of the one of the link state advertisements different than the first field.

8. The method of claim 1, further comprising advertising that the intermediate layer two shared access network operates by advertising inbound cost metrics and the outbound cost metrics or that the intermediate layer two shared access network operates by advertising the total cost metrics.

9. The method of claim 1, wherein the intermediate layer two shared access network comprises either a broadcast network or a non-broadcast multi-access network.

10. The method of claim 1, wherein the layer three link state routing protocol comprises either an Open Shortest Path First (OSPF) routing protocol or an Intermediate system to intermediate system (IS-IS) routing protocol.

11. A system comprising:

a plurality of layer three routers coupled to an intermediate layer two shared access network and that each include one or more processors configured to communicate, in accordance with a layer three link state protocol, link state advertisements (LSAs) between the plurality of layer three routers,

wherein the link state advertisements specify a set of outbound cost metrics representative of respective outbound costs to send network traffic to the intermediate layer two shared access network for each of the plurality of layer three routers and a set of inbound cost metrics representative of respective inbound costs to receive network traffic for each of the plurality layer three routers from the intermediate layer two shared access network, and

wherein a first one of the plurality of layer three routers is configured to compute a total cost metric for each link through the intermediate layer two shared access network that originates at the first one of the plurality of layer three routers and terminates at each remaining one of the plurality of layer three routers based on one of the outbound cost metrics for the first one of the plurality of layer three routers and the corresponding inbound cost metrics for each of the remaining ones of the plurality of layer three routers, perform path selection based on the total cost metric, forward network traffic based on the path selection.

12. The system of claim 11, wherein each of the plurality of layer three routers communicates its respective one of the set of outbound cost metrics and its respective one of the set of inbound cost metrics in a single LSA.

13. The system of claim 11, wherein the first one of the plurality of layer three routers is further configured to generate a representation of a topology graph of the plurality of layer three routers in which a communication path from the first one of the plurality of layer three routers to a second one of the remaining plurality of layer three routers through the shared access network is represented as a single edge connecting a first node to a second node in the topology graph, compute one of the total cost metrics for the single edge as a summation of the one of the outbound cost metrics for the first one of the plurality of layer three routers and one of the inbound cost metrics for the second one of the plurality of layer three routers, assign the one of the total cost metrics to the single edge in the topology graph, and perform the path selection based on the one of the total cost metrics assigned to the single edge of the topology graph.

14. The system of claim 11, wherein the first one of the plurality of layer three routers is further configured to, when communicating the link state advertisements, transmit one of the link state advertisements that specifies both the one of the outbound cost metrics for the first one of the plurality of layer three routers representative of one of the outbound costs from the first one of the plurality of layer three routers to the shared access network and one of the inbound cost metrics for the first one of the plurality of layer three routers representative of one of the inbound costs to the first one of the plurality of layer three routers from the shared access network using a single field of the one of the link state advertisements.

15. The system of claim 14, wherein the single field of the one of the link state advertisements stores the one of the outbound cost metrics for the first one of the plurality of layer three routers but not a corresponding one of the inbound cost metrics for the first one of the plurality of layer three routers, wherein the one of the outbound cost metrics for the first one of the plurality of layer three routers specifies both the one of the outbound cost metrics for the first one of the plurality of layer three routers and the corresponding one of the inbound cost metrics for the first one of the plurality of layer three routers.

16. The system of claim 11, wherein the first one of the plurality of layer three routers is further configured to transmit one of the link state advertisements that specifies the one of the outbound cost metrics for the first one of the plurality of layer three routers representative of one of the outbound costs from the first one of the plurality of layer three routers to the shared access network in a first field of the one of the link state advertisements and one of the inbound cost metrics for the first one of the plurality of layer three routers representative of one of the inbound costs to the first one of the plurality of layer three routers from the shared access network in a second field of the one of the link state advertisements different than the first field.

17. The system of claim 11, wherein the first one of the plurality of layer three routers are further configured to receive one of the link state advertisements that specifies one of the outbound cost metrics for a second one of the plurality of layer three routers representative of one of the outbound costs from the second one of the plurality of layer three routers to the shared access network in a first field of the one of the link state advertisements and one of the inbound cost metrics for the second one of the plurality of layer three routers representative of one of the inbound costs to the second one of the plurality of layer three routers from the shared access network in a second field of the one of the link state advertisements different than the first field.

18. The system of claim 11, wherein the first one of the plurality of layer three routers is further configured to advertise that the intermediate layer two shared access network operates by advertising the inbound cost metrics and the outbound cost metrics or that the intermediate layer two shared access network operates by advertising the total cost metrics.

19. The system of claim 11, wherein the intermediate layer two shared access network comprises either a broadcast network or a non-broadcast multi-access network.

20. The system of claim 11, wherein the layer three link state routing protocol comprises either an Open Shortest Path First (OSPF) routing protocol or an Intermediate system to intermediate system (IS-IS) routing protocol.

21. A non-transitory computer-readable storage medium having stored thereon instructions that, when executed, cause one or more processors of a plurality of layer three routers to:

communicate, in accordance with a layer three link state protocol, link state advertisements between the plurality of layer three routers coupled to an intermediate layer two shared access network, wherein the link state advertisements specify a set of outbound cost metrics representative of respective outbound costs to send network traffic to the intermediate layer two shared access network for each of the plurality of layer three routers and a set of inbound cost metrics representative of respective inbound costs to receive network traffic for each of the plurality layer three routers from the intermediate layer two shared access network;

compute a total cost metric for each link through the intermediate layer two shared access network that originates at the first one of the plurality of layer three routers and terminates at each remaining one of the plurality of layer three routers based on one of the outbound cost metrics for the first one of the plurality of layer three routers and the corresponding inbound cost metrics for each of the remaining ones of the plurality of layer three routers;

perform path selection based on the total cost metrics; and

forward network traffic based on the path selection.