TWO-PART METRIC FOR LINK STATE ROUTING PROTOCOLS

• US 20150092594A1
• Filed: 09/30/2013
• Published: 04/02/2015
• Est. Priority Date: 09/30/2013
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Zhang, Zhaohui, Wang, Lili
• Granted Patent: US 9,444,721 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• 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 link state protocol, link state advertisements between a plurality of routers coupled to a 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 shared access network for each of the plurality of routers and a set of inbound cost metrics representative of respective inbound costs to receive network traffic for each of the plurality routers from the shared access network; and

performing path selection based on the set of outbound cost metrics and the set of inbound cost metrics to select paths through the routers of the shared access network.

2. The method of claim 1, wherein each of the plurality of 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, wherein performing path selection comprises:

computing, with at least a first one of the plurality of routers, a total cost metric from the first one of the plurality of routers through a second one of the plurality of routers based on one of the outbound cost metrics for the first one of the plurality of routers and one of the inbound cost metrics for the second one of the plurality of routers; and

selecting, with the first one of the plurality of routers, a path from the first one of the plurality of routers through the second one of the plurality of routers based on the computed total cost metric.

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

5. The method of claim 1, wherein the single field of the one of the link state advertisements stores a first one of the outbound cost metrics but not a corresponding first one of the inbound cost metric, wherein the outbound cost metric specifies both the first one of the outbound cost metrics and the corresponding first one of the inbound cost metrics.

6. The method of claim 1, wherein communicating the link state advertisements comprises transmitting, with a first one of the plurality of routers, one of the link state advertisements that specifies one of the outbound cost metrics representative of one of the outbound costs from the first one of the plurality of 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 representative of one of the inbound costs from the first one of the plurality of routers to 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 a first one of the plurality of routers, one of the link state advertisements that specifies one of the outbound cost metrics representative of one of the outbound costs from a second one of the plurality of 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 representative of one of the inbound costs from the second one of the plurality of routers to 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 shared access network operates by advertising the first cost metric and the second cost metric or that the shared access network operates by advertising the total cost metric.

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

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

11. A system comprising:

a plurality of routers that each include one or more processors configured to communicate, in accordance with a link state protocol, link state advertisements between the plurality of routers,

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

wherein the routers are configured to perform path selection based on the set of outbound cost metrics and the set of inbound cost metrics to select paths through the routers of the shared access network.

12. The system of claim 11, wherein each of the plurality of 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, at least one of the plurality of routers are further configured to, when performing path selection, compute a total cost metric from the first one of the plurality of routers through a second one of the plurality of routers based on one of the outbound cost metrics for the first one of the plurality of routers and one of the inbound cost metrics for the second one of the plurality of routers and select a path from the first one of the plurality of routers through the second one of the plurality of routers based on the computed total cost metric.

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

15. The system of claim 11, wherein the single field of the one of the link state advertisements stores a first one of the outbound cost metrics but not a corresponding first one of the inbound cost metric, wherein the outbound cost metric specifies both the first one of the outbound cost metrics and the corresponding first one of the inbound cost metrics.

16. The system of claim 11, at least one of the plurality of routers are further configured to, when communicating the link state advertisements, transmit one of the link state advertisements that specifies one of the outbound cost metrics representative of one of the outbound costs from the first one of the plurality of 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 representative of one of the inbound costs from the first one of the plurality of routers to 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, at least one of the plurality of routers are further configured to, when communicating the link state advertisements, receive one of the link state advertisements that specifies one of the outbound cost metrics representative of one of the outbound costs from a second one of the plurality of 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 representative of one of the inbound costs from the second one of the plurality of routers to 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 at least one of the plurality of routers are further configured to advertise that the shared access network operates by advertising the first cost metric and the second cost metric or that the shared access network operates by advertising the total cost metric.

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

20. The system of claim 11, wherein the link state routing protocol comprises either the Open Shortest Path First (OSPF) routing protocol or the 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 routers to:

communicate, in accordance with a link state protocol, link state advertisements between the plurality of routers coupled to a 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 shared access network for each of the plurality of routers and a set of inbound cost metrics representative of respective inbound costs to receive network traffic for each of the plurality routers from the shared access network; and

perform path selection based on the set of outbound cost metrics and the set of inbound cost metrics to select paths between the routers of the sub-network.