Routing inter-AS LSPs with centralized controller

Techniques are described for routing inter-AS LSPs with a centralized controller taking inter-AS TE metric values for inter-AS links into account. The inter-AS TE metric values, e.g., local preference values, MED values, or EROS, indicate route preferences for routes between ASes. The disclosed techniques enable network devices within either or both of a first AS and a second AS to store inter-AS TE metric values for inter-AS links in TEDs of the network devices. The network devices then send the contents of their TEDs, including the inter-AS TE metric values, to a centralized controller of the first AS and the second AS. The centralized controller computes an inter-AS LSP across the first AS and the second AS based at least in part on the inter-AS TE metric values such that the inter-AS LSP includes a preferred one of the inter-AS links as indicated by the inter-AS TE metric values.

TECHNICAL FIELD

The disclosure relates to communication networks.

BACKGROUND

A wide variety of customer devices connect to service provider networks to access resources and services provided by packet-based data networks, such as the Internet, enterprise intranets, content providers, and virtual private networks (VPNs). Each service provider network typically provides an extensive network infrastructure to provide packet-based data services to the customer devices. The service provider networks may comprise a wide area network (WAN). In some examples, each service provider network may comprise a single autonomous system (AS) within a WAN that includes multiple ASes. In other examples, each service provider network may comprise two or more ASes within the WAN.

The network infrastructure of a service provider network typically includes a vast collection of access nodes, aggregation nodes and high-speed edge routers interconnected by communication links. These network devices typically execute various protocols and exchange signaling messages to anchor and manage subscriber sessions and communication flows associated with customer devices. A software defined network (SDN) controller may be included in the network architecture to provide centralized control of the subscriber sessions and communication flows within the service provider network. In some cases, a SDN controller may provide centralized control over an entire WAN including multiple ASes. In this case, the SDN controller may be referred to as a SDN WAN controller or a SD-WAN controller.

SUMMARY

In general, this disclosure describes techniques for routing inter-autonomous system (AS) label switched paths (LSPs) with a centralized controller taking into account inter-AS traffic engineering (TE) metric values for inter-AS links. The inter-AS TE metric values indicate route preferences for routes between ASes, e.g., between a first AS and a second AS. The inter-AS TE metric values may include, e.g., local preference values for the inter-AS links that indicate a preferred outgoing route for a given AS, multiple exit discriminator (MED) values for the one or more inter-AS links that indicate a preferred incoming route for a given AS, or an explicit route object (ERO) that indicates a specific route between ASes.

The disclosed techniques enable network devices within either or both of a first AS and a second AS to store inter-AS TE metric values for one or more inter-AS links in traffic engineering databases (TEDs) of the network devices. The network devices then send the contents of their TEDs, including the inter-AS TE metric values, to a centralized controller coupled to the first AS and the second AS. According to the disclosed techniques, the centralized controller computes an inter-AS LSP across the first AS and the second AS based at least in part on the inter-AS TE metric values such that the inter-AS LSP includes a preferred one of the inter-AS links as indicated by the inter-AS TE metric values. In this way, the centralized controller computes the inter-AS LSP by taking the route preferences for the inter-AS links into account, instead of treating the inter-AS links simply as passive links.

In one example, this disclosure is directed to a method comprising receiving, by a network device within a first AS, inter-AS TE metric values for one or more inter-AS links that indicate route preferences for routes between the first AS and a second AS; storing the inter-AS TE metric values in a TED of the network device; sending, by the network device and to a centralized controller device coupled to the first AS and the second AS, contents of the TED including the inter-AS TE metric values; receiving, by the network device and from the centralized controller device, path information for an inter-AS LSP across the first AS and the second AS computed by the centralized controller device based on the contents of the TED, wherein the inter-AS LSP includes a preferred one of the one or more inter-AS links as indicated by the inter-AS TE metric values; and establishing, by the network device, at least a portion of the inter-AS LSP according to the path information.

In another example, this disclosure is directed to a network device comprising a memory, and one or more processors in communication with the memory. The one or more processors are configured to receive inter-AS TE metric values for one or more inter-AS links that indicate route preferences for routes between a first AS and a second AS, wherein the network device is within the first AS, store the inter-AS TE metric values in a TED of the network device, send contents of the TED including the inter-AS TE metric values to a centralized controller device coupled to the first AS and the second AS, receive, from the centralized controller device, path information for an inter-AS LSP across the first AS and the second AS computed by the centralized controller device based on the contents of the TED, wherein the inter-AS LSP includes a preferred one of the one or more inter-AS links as indicated by the inter-AS TE metric values, and establish at least a portion of the inter-AS LSP.

In a further example, this disclosure is directed to a method comprising receiving, by a centralized controller device coupled to a first AS and a second AS, contents of a TED of a network device within the first AS, wherein the contents of the TED include inter-AS TE metric values for one or more inter-AS links that indicate route preferences for routes between the first AS and the second AS; storing the contents of the TED received from the network device within the first AS in one or more routing tables of the centralized controller device, wherein the one or more routing tables include contents of TEDs of a plurality of network devices within both the first AS and the second AS; computing, by the centralized controller device, an inter-AS LSP across the first AS and the second AS based on the one or more routing tables including the inter-AS TE metric values, wherein the inter-AS LSP includes a preferred one of the one or more inter-AS links as indicated by the inter-AS TE metric values; and sending, by the centralized controller device and to the network device within the first AS, path information for the inter-AS LSP in order to instruct the network device to establish at least a portion of the inter-AS LSP.

In an additional example, this disclosure is directed to a centralized controller device comprising a memory, and one or more processors in communication with the memory. The one or more processors are configured to receive contents of a TED of a network device within a first AS, wherein the contents of the TED include inter-AS TE metric values for one or more inter-AS links that indicate route preferences for routes between the first AS and a second AS, wherein the centralized controller device is coupled to the first AS and the second AS, store the contents of the TED received from the network device within the first AS in one or more routing tables of the centralized controller device, wherein the one or more routing tables include contents of TEDs of a plurality of network devices within both the first AS and the second AS, compute an inter-AS LSP across the first AS and the second AS based on the one or more routing tables including the inter-AS TE metric values, wherein the inter-AS LSP includes a preferred one of the one or more inter-AS links as indicated by the inter-AS TE metric values, and send, to the network device within the first AS, path information for the inter-AS LSP in order to instruct the network device to establish at least a portion of the inter-AS LSP.

DETAILED DESCRIPTION

FIG. 1is a block diagram illustrating an example network system10including a software defined network (SDN) controller12configured to route inter-autonomous system (AS) label switched paths (LSPs), in accordance with techniques described herein. The example network system10ofFIG. 1includes SDN controller12and a wide area network (WAN) having a first AS (AS1)14and a second AS (AS2)16. SDN controller12of network system10operates as a high-level controller for the WAN. More specifically, SDN controller12provides centralized control of customer sessions and communication flows within the WAN by configuring and managing the routing and switching infrastructure within and between first AS114and second AS216. In this case, SDN controller12may be referred to as a SDN WAN controller or a SD-WAN controller.

In one example, network system10may comprise a service provider network system that provides packet-based data services to customer devices26A and26B (“customer devices26”). In this example, each of AS114and AS216comprises a collection of network devices under the control of one or more network service providers that presents a common, clearly defined routing policy. Customer device26A may connect to AS114and customer device26B may connect to AS216to access resources provided by packet-based data networks, such as the Internet, enterprise intranets, content providers, and virtual private networks (VPNs). A network service provider that administers one or both of AS114and AS216typically offers services to customer devices26that access the WAN of network system10. Services offered may include, for example, traditional Internet access, VoIP, video and multimedia services, and security services.

In some cases, AS114and AS216may be administered by the same network service provider, and SDN controller12may be operated by that network service provider. In other cases, AS114may be administered by a first network service provider and AS216may be administered by a second, different network service provider. In those cases, SDN controller12may be operated by, for example, the first network service provider with cooperation from the second network service provider.

As illustrated inFIG. 1, customer device26A connects to AS114via customer edge (CE) device24A and customer device26B connects to AS216via CE device24B. In general, CE devices24A and24B (“CE devices24”) may be routers or switches controlled by customer networks. Customer devices26may be, for example, personal computers, laptop computers or other types of computing devices associated with customers. In addition, customer devices26may comprise mobile devices that access the data services provided by the WAN of network system10via a radio access network (RAN) (not shown). Example mobile subscriber devices include mobile telephones, laptop or desktop computers having, e.g., a 3G wireless card, wireless-capable netbooks, video game devices, pagers, smart phones, personal data assistants (PDAs) or the like.

Each of customer devices26may run a variety of software applications, such as word processing and other office support software, web browsing software, software to support voice calls, video games, video conferencing, and email, among others. Customer devices26connect to the WAN of network system10via wired and/or wireless communication links. The term “communication link,” as used herein, comprises any form of transport medium, wired or wireless, and can include intermediate nodes such as network devices. Communication links may comprise, for instance, aspects of an asymmetric digital subscriber line (DSL) network, a Worldwide Interoperability for Microwave Access (WiMAX) network, a T-1 line, an Integrated Service Digital Network (ISDN), wired Ethernet, or a cellular radio link.

Each of PE devices20within AS114and each of PE devices22within AS216maintain a link state database (LSDB) and/or a traffic engineering database (TED) associated with a link state routing protocol of an interior gateway protocol (IGP), such as open shortest path first (OSPF) and intermediate system-to-intermediate system (IS-IS). The contents of the LSDB and/or TED of a given PE device, e.g., PE device20A, describe links and nodes only within the respective AS of the given PE device, e.g., AS114of PE device20A.

Within AS114, PE devices20may communicate over intra-AS links21to exchange link state and traffic engineering (TE) information stored in the PE devices' LSDBs or TEDs using a border gateway protocol (BGP). In this way, each of PE devices20learns the topology and any TE constraints within AS114in order to accurately route traffic through AS114. Within AS216, PE devices22operate in a similar manner and communicate over intra-AS links23to learn the topology and any TE constraints within AS216in order to accurately route traffic through AS216.

As mentioned above, SDN controller12provides centralized control of customer sessions and communication flows within the WAN of network system10. SDN controller12, therefore, may configure and manage the routing and switching infrastructure within and between first AS114and second AS216(e.g., including PE devices20, PE devices22, and additional transit routers and switches not shown inFIG. 1). Further example details of an SDN controller are described in PCT International Patent Application PCT/US13/44378, filed Jun. 5, 2013, and U.S. patent application Ser. No. 41/500,736, filed Sep. 29, 2014, the entire contents of which are incorporated herein by reference.

In a conventional network system, a SDN controller learns intra-AS link state and TE metric values from TEDs of PE devices in the network system, but does not learn inter-AS TE metric values for inter-AS links. In general, the SDN controller does not learn the inter-AS TE metric values for the inter-AS links because the values are based on user configured preferences that are not stored in the LSDBs and/or TEDs of the PE devices. The inter-AS links are instead represented in the TEDs of the PE devices as passive links that include some link attributes but do not include traffic engineering information. The SDN controller may take the inter-AS links into consideration as passive links when computing inter-AS paths, but does not have the knowledge or control to select a preferred inter-AS route. The SDN controller may instead select inter-AS routes for the inter-AS paths based on a randomized or round-robin selection technique.

One example of an inter-AS TE metric value is a local preference value for a given inter-AS link that may be used to identify a preferred outgoing route of a given AS. For example, an administrator of AS114may assign each of inter-AS links18a local preference value, and the one of inter-AS links18having the highest local preference value may be identified as the preferred outgoing route of AS114. Another example of an inter-AS TE metric value is a multiple exit discriminator (MED) value for a given inter-AS link that may be used to identify a preferred incoming route of a given AS. For example, the administrator of AS114may assign each of inter-AS links18a MED value, and the one of inter-AS links18having the lowest MED value may be identified as the preferred incoming route of AS114. In some examples, an administrator of AS216may assign the same or different local preference and MED values to inter-AS links18. A further example of an inter-AS TE metric value is an explicit route object (ERO) that indicates a specific route between AS114and AS216.

The inter-AS TE metric values may be configured by a user or an administrator of each of AS114and AS216. The inter-AS TE metric values may then be flooded to PE devices20within AS114or PE devices22within AS216per IGP link state flooding procedures. In the case where AS114and AS216are administered by the same network service provider, the administrator of that network service provider may configure the inter-AS TE metric values for each of AS114and AS216to reflect the same inter-AS route preferences. In the case where AS114is administered by a first network service provider and AS216is administered by a second, different network service provider, the administrators for the first and second network service providers may need to work together to configure the inter-AS TE metric values for AS114and AS216to reflect the same inter-AS route preferences.

This disclosure describes techniques to enable SDN controller12to route inter-AS label switched paths (LSPs) while taking into account inter-AS TE metric values for inter-AS links18. In order to compute an inter-AS LSPs between AS114and AS216with end-to-end TE, SDN controller12needs to learn the intra-AS link state and TE metric values as well as the inter-AS TE metric values from PE devices20,22within each of AS114and AS216.

The disclosed techniques enable PE devices20, such as PE device20A, for example, within AS114to store the inter-AS TE metric values for inter-AS links18in a TED of PE device20A. The TED of PE device20A may also store the intra-AS TE metric values for intra-AS links21within AS114. In one example, PE device20A may receive the configured inter-AS TE metric values directly from a user or administrator of AS114. In another example, PE device20A may receive the configured inter-AS TE metric values in link state messages of an IGP, e.g., an Opaque link state advertisement (LSA) of OSPF or a link state packet (LSP) of IS-IS, from one of neighboring PE devices20B-20D within AS114. In either example, upon receiving the configured inter-AS TE metric values, PE device20A may advertise the inter-AS TE metric values to any of PE devices20B-20D within AS114in link state messages of IGP.

The disclosed techniques further enable PE device20A, for example, to send the contents of its TED, including the inter-AS TE metric values, to SDN controller12using an extended version of the BGP routing protocol used to send or report link state and TE information to SDN controller12. The extended version of BGP may be referred to as a link state attribute of BGP (BGP-LS). In some instances, the extended version of BGP may alternatively be referred to as BGP with link state extensions (BGP-LS). New type-length-values (TLVs) for BGP-LS are defined herein to carry each of the inter-AS TE metric values.

InFIG. 1, the BGP-LS communication carrying the TED contents of PE device20A, including the inter-AS TE metric values associated with AS114, is illustrated as a dotted arrow from PE device20A to SDN controller12. A similar dotted arrow is illustrated from PE device22A to SDN controller12to illustrate a BGP-LS communication carrying TED contents of PE device20B, including inter-AS TE metric values associated with AS216. In this way, SDN controller12receives TED contents, including inter-AS TE metric values, from PE devices in both AS114and AS216. Although described and illustrated with respect to PE device20A within AS114and PE device22A within AS216, any of PE devices20within AS114and PE devices22within AS216may be configured to store inter-AS TE metric values in their TEDs and send the contents of their TEDs, including the inter-AS TE metric values, to SDN controller12using BGP-LS.

In accordance with the disclosed techniques, SDN controller12computes an inter-AS LSP across AS114and AS216based at least in part on the inter-AS TE metric values received from the PE devices20,22. In this way, SDN controller12computes the inter-AS LSP by taking the route preferences for inter-AS links18into account, instead of treating inter-AS links18simply as passive links. The computed inter-AS LSP, therefore, includes a preferred one of inter-AS links18as indicated by the inter-AS TE metric values. SDN controller12may then send path information for the computed inter-AS LSP to one or more of PE devices20,22in order to instruct the PE devices to establish at least a portion of the inter-AS LSP. For example, PE device20A within AS114may receive the path information for the computed inter-AS LSP, and signal or establish at least a portion of the inter-AS LSP, e.g., by signaling the inter-AS path using the preferred one of inter-AS links18.

FIG. 2is a block diagram illustrating an example network device50configured to send inter-AS TE metric values, e.g., local preference and MED values, to a centralized controller device, in accordance with the techniques of this disclosure. For purposes of illustration, network device50may be described herein within the context of network system10ofFIG. 1, and may represent any of PE devices20within AS114or PE devices22within AS216, for example.

In the example ofFIG. 2, network device50includes control unit54in which routing engine56provides control plane functionality for network device50and forwarding engine58provides data plane functionality for network device50. Network device50also includes interface cards60A-60N (“IFCs60”) that receive control and data packets via incoming links and send packets via outbound links. IFCs60are typically coupled to the incoming links and the outbound links via a number of interface ports. In general, control unit54determines routes of received packets and forwards the packets accordingly via IFCs60.

Control unit54provides an operating environment for routing engine56and may be implemented solely in software, or hardware, or may be implemented as a combination of software, hardware or firmware. For example, control unit54may include one or more processors (not shown) which execute software instructions. In that example, routing engine56may include various software modules or daemons (e.g., one or more routing protocol processes, user interfaces and the like), and control unit54may include a computer-readable storage medium, such as computer memory or hard disk, for storing executable instructions.

Routing engine56operates as the control plane for network device50and includes an operating system (not shown) that may provide a multi-tasking operating environment for execution of a number of concurrent processes. For example, routing engine56provides an operating environment for various protocols68that perform routing functions for network device50. As described in further detail below, protocols68provide control plane functions for storing network topology in the form of routing tables or other structures, executing routing protocols to communicate with peer routing devices and maintain and update the routing tables, and providing management interface(s) to allow user access and configuration of network device50.

In the illustrated example ofFIG. 2, routing engine56includes BGP70and IGP link state routing protocols OSPF74and IS-IS75as routing protocols used to exchange routing information with other network devices in the same AS in order to discover the topology of the AS and update routing information64. Routing information64defines routes and the appropriate next hops for each route, i.e., the neighboring network devices along each of the routes, through the AS to destinations/prefixes within the AS learned via BGP70. Routing information64also defines the network topology of the AS with interconnected links learned using OSPF74or IS-IS75.

Routing engine56may maintain a link state database (LSDB)65configured to store link state information about nodes and links within the AS in which network device50resides. For example, LSDB65may include one or more of local/remote internet protocol (IP) addresses, local/remote interface identifiers, link metrics and TE metrics, link bandwidth, reservable bandwidth, class of service (CoS) reservation state, preemption, or shared risk link groups (SRLG). In addition, routing engine56may maintain a traffic engineering database (TED)66configured to store traffic engineering information. In accordance with the techniques of this disclosure, TED66is configured to store both intra-AS TE metric values and inter-AS TE metric values. The intra-AS TE metric values may include some or all of the metrics stored in LSDB65for nodes and links within the AS of network device50. The inter-AS TE metric values may include one or more of local preference values that indicate a preferred outgoing route for the AS of network device50, MED values that indicate a preferred incoming route for the AS of network device50, or an ERO that indicates a specific route between the AS of network device50and a remote AS.

User interface62of routing engine56provides an interface by which an administrator52or other management entity may modify the configuration of network device50. Using user interface62, one or more management entities may enable/disable and configure services, install routes, enable/disable and configure rate limiters and configure interfaces, for example. In accordance with the techniques of this disclosure, routing engine56may receive inter-AS TE metric values for inter-AS links configured by administrator52via user interface62. Routing engine56may then store the inter-AS TE metric values in TED66. In other examples, routing engine56may receive the configured inter-AS TE metric values in Opaque LSAs of OSPF74or LSPs of IS-IS75from neighboring network devices.

Conventionally, inter-AS links are configured as passive links that include some link attributes but do not include traffic engineering information. The inter-AS links, therefore, are conventionally advertised in link state messages as passive links and included in TEDs of network devices as passive links.

As discussed above, the inter-AS TE metric values may include local preference values and MED values that are assigned to each of the inter-AS links. Local preference values are conventionally only carried in internal BGP (iBGP) messages within the AS of network device50, and are not carried in external BGP (eBGP) messages. When the AS of network device50has more than one outgoing route to another AS, the local preference value for a given inter-AS link indicates the preference of one route over the other routes. For example, administrator52may assign each of the inter-AS links a local preference value where the highest local preference value indicates the preferred outgoing route from the AS. MED values are conventionally carried in both iBGP and eBGP messages. The MED values are used to influence how a neighbor AS enters the AS of network device50to reach a certain destination. For example, administrator52may assign each of the inter-AS links a MED value where the lowest MED value indicates the preferred incoming route to the AS.

According to the disclosed techniques, network device50may advertise the configured inter-AS TE metric values for the inter-AS links to neighboring network devices in the AS of network device50using an Opaque LSA of OSPF74or a LSP of IS-IS75. Upon receiving the Opaque LSA or IS-IS LSP, the neighboring network devices may update their LSDBs and/or TEDs with the inter-AS TE metric values included in the link state messages.

In one example, a local preference value of an inter-AS link may conventionally be configured for advertisement using OSPF as follows:set protocols ospf area 0.0.0.0 interface ge-2/1/0.0 passive traffic-engineering remote-node-id 201.202.65.65set protocols ospf area 0.0.0.0 interface ge-2/1/0.0 passive traffic-engineering remote-node-router-id 65.0.0.201set protocols ospf area 0.0.0.0 interface ge-2/1/0.0 te-metric 999

According to the disclosed techniques, a local preference value of an inter-AS link may be configured for advertisement using OSPF74as follows: set protocols ospf area 0.0.0.0.0 interface ge-2/1/0.1 local preference100. The variable name “local preference” and the local preference value of 100 are used herein for example purposes only. In other examples, a differently named variable may be used to represent the local preference value, and the local preference value may be set to any value capable of indicating a preferred outgoing inter-AS link within a plurality of inter-AS links.

In another example, a local preference value of an inter-AS link may conventionally be configured for advertisement using IS-IS as follows:set protocols isis interface xe-1/1/1.0 passive remote-node-iso 0100.0000.0202set protocols isis interface xe-1/1/1.0 passive remote-node-id 202.202.1.1set protocols isis interface xe-1/1/1.0 level 2 te-metric 999

According to the disclosed techniques, a local preference value of an inter-AS link may be configured for advertisement using IS-IS75as follows: set protocols isis interface xe-1/1/1.0 level 2 local preference100. Again, the variable name “local_preference” and the local preference value of 100 are used herein for example purposes only. In other examples, a differently named variable may be used to represent the local preference value, and the local preference value may be set to any value capable of indicating a preferred outgoing inter-AS link within a plurality of inter-AS links.

In a further example, a MED value of an inter-AS link may conventionally be configured for advertisement using OSPF as follows:set protocols ospf area 0.0.0.0 interface xe-1/1/0.0 interface-type p2pset protocols ospf area 0.0.0.0 interface xe-1/1/0.0 passive traffic-engineering remote-node-id 202.202.1.2set protocols ospf area 0.0.0.0 interface xe-1/1/0.0 passive traffic-engineering remote-node-router-id 65.0.0.202set protocols ospf area 0.0.0.0 interface xe-1/1/0.0 metric 999

According to the disclosed techniques, a MED value of an inter-AS link may be configured for advertisement using OSPF74as follows: set protocols ospf area 0.0.0.0.0 interface ge-2/1/0.1 metric-out30. The variable name “metric-out” and the MED value of 30 are used herein for example purposes only. In other examples, a differently named variable may be used to represent the MED value, and the MED value may be set to any value capable of indicating a preferred incoming inter-AS link within a plurality of inter-AS links.

In an additional example, a MED value of an inter-AS link may conventionally be configured for advertisement using IS-IS as follows:set protocols isis interface ge-2/0/0.0 passive remote-node-iso 0100.0000.0201set protocols isis interface ge-2/0/0.0 passive remote-node-id 201.202.1.1set protocols isis interface ge-2/0/0.0 level 2 te-metric 999

According to the disclosed techniques, a MED value of an inter-AS link may be configured for advertisement using IS-IS75as follows: set protocols isis interface ge-2/0/0.0 level 2 metric-out30. Again, the variable name “metric-out” and the MED value of 30 are used herein for example purposes only. In other examples, a differently named variable may be used to represent the MED value, and the MED value may be set to any value capable of indicating a preferred incoming inter-AS link within a plurality of inter-AS links. In the example of OSPF74, network device50may advertise the configured inter-AS TE metric values to neighboring network devices in an Opaque LSA. When the neighboring network devices receive the Opaque LSA, the inter-AS TE metric values included in the Opaque LSA will be updated and stored in LSDBs and/or TEDs of the neighboring network devices. The Opaque LSA of OSPF is described in more detail in R. Coltun, “The OSPF Opaque LSA Option,” Network Working Group, IETF RFC 2370, July 1998, the entire contents of which are incorporated by reference herein. Moreover, the inclusion of intra-AS TE metric values in the Opaque LSA of OSPF is described in more detail in D. Katz, et al., “Traffic Engineering (TE) Extensions to OSPF Version 2,” Network Working Group, IETF RFC 3630, September 2003, the entire contents of which are incorporated by reference herein.

An example of an OSPF LSDB, e.g., LSDB65of network device50for OSPF74, is as follows.

An example of an OSPF TED, e.g., TED66of network device50for OSPF74, that includes inter-AS TE metric values is as follows.

Returning toFIG. 2, routing engine56of network device50further includes BGP-LS72as an extended version of the BGP routing protocol used to send or report link state and TE information to a centralized controller device, e.g., SDN controller12fromFIG. 1. According to the disclosed techniques, BGP-LS72may be used to send the contents of TED66to the centralized controller, including the inter-AS TE metric values. In BGP-LS72, the MP_REACH_NLRI and MP_UNREACH_NLRI attributes are used to carry opaque information, including the inter-AS TE metric values. Examples of the newly defined TLVs used to carry local preference values and MED values are described in detail below with respect toFIGS. 4 and 5. The BGP-LS protocol by which BGP-LS72operates is described in additional detail in H. Gredler, et al., “North-Bound Distribution of Link-State and TE information using BGP: draft-ietf-idr-ls-distribution-13,” Inter-Domain Routing Working Group, Internet Engineering Task Force (IETF) Internet-Draft, Oct. 16, 2015, the entire contents of which are incorporated herein by reference.

Routing engine56also provides an operating environment of one or more traffic engineering protocols to establish tunnels for forwarding packets through the AS in which network device50resides. For example, routing engine56includes label distribution protocol (LDP)76and resource reservation protocol with traffic engineering (RSVP-TE)77used to signal or establish LSPs within the AS based on routing information64. In some examples, routing engine56may use LDP76or RSVP-TE77to establish at least a portion of an inter-AS LSP as computed by the centralized controller device.

Routing engine56analyzes routing information64to generate forwarding information78installed in forwarding engine58. Forwarding engine58operates as the data plane for network device50. Although not shown inFIG. 2, forwarding engine58may comprise a central processing unit (CPU), memory and one or more programmable packet-forwarding application-specific integrated circuits (ASICs). Forwarding information78is generated based on selection of certain routes within the AS and maps packet key information (e.g., destination information and other select information from a packet header) to one or more specific next hops and ultimately to one or more specific output interface ports of IFCs60.

The architecture of network device50illustrated inFIG. 2is shown for example purposes only and should not be limited to this architecture. In other examples, network device50may be configured in a variety of ways. In one example, some of the functionality of control unit54may be distributed within IFCs60. Control unit54may be implemented solely in software, or hardware, or may be implemented as a combination of software, hardware, or firmware. For example, control unit54may include one or more of a processor, a programmable processor, a general purpose processor, an integrated circuit, an ASIC, a field programmable gate array (FPGA), or any type of hardware unit capable of implementing the techniques described herein. Control unit82may further include one or more processors which execute software instructions stored on a computer readable storage medium, such as random access memory (RAM), read only memory (ROM), programmable read only memory (PROM), erasable programmable read only memory (EPROM), electronically erasable programmable read only memory (EEPROM), non-volatile random access memory (NVRAM), flash memory, a hard disk, a CD-ROM, a floppy disk, a cassette, magnetic media, optical media, or other computer-readable storage media. In some instances, the computer-readable storage medium may include instructions that cause a programmable processor to perform the techniques described herein. For example, the various software modules of control unit54may comprise executable instructions stored on the computer-readable medium.

FIG. 3is a block diagram illustrating an example centralized controller device80configured to route inter-AS LSPs based on inter-AS TE metric values, e.g., local preference and MED values, in accordance with the techniques of this disclosure. For purposes of illustration, centralized controller device80may be described herein within the context of network system10ofFIG. 1, and may represent SDN controller12. The architecture of centralized controller device80illustrated inFIG. 3is shown for example purposes only and should not be limited to this architecture. In other examples, centralized controller device80may be configured in a variety of ways.

Centralized controller device80includes a control unit82coupled to a network interface84to exchange packets with other network devices by inbound link86and outbound link88. Control unit82may include one or more processors (not shown) that execute software instructions, such as those used to define a software or computer program, stored to a computer-readable storage medium (not shown), such as non-transitory computer-readable mediums including a storage device (e.g., a disk drive, or an optical drive) or a memory (such as Flash memory or RAM) or any other type of volatile or non-volatile memory, that stores instructions to cause the one or more processors to perform the techniques described herein. Alternatively or additionally, control unit82may comprise dedicated hardware, such as one or more integrated circuits, one or more ASICs, one or more Application Specific Special Processors (ASSPs), one or more field programmable gate arrays (FPGAs), or any combination of one or more of the foregoing examples of dedicated hardware, for performing the techniques described herein.

Control unit82provides an operating environment for path computation element90and network topology abstractor daemon (NTAD)94. In one example, these units may be implemented as one or more processes executing on one or more virtual machines of one or more servers. That is, while generally illustrated and described as executing on a single centralized controller device80, aspects of these units may be delegated to other computing devices. Control unit82also provides an operating environment for several protocols, including BGP-LS92.

In some examples, centralized controller device80may compute and establish inter-AS LSPs across a first AS and a second AS of a network, such as AS114and AS216of network system10fromFIG. 1. As illustrated inFIG. 3, path computation element90includes a path computation unit96, a topology unit97and a path provisioning unit98. In order to compute the inter-AS LSPs with end-to-end TE, path computation element90needs to learn intra-AS link state and TE metric values for intra-AS links within each AS, and inter-AS TE metric values for inter-AS links. BGP-LS92is an extended version of the BGP routing protocol used to receive link state and TE information from network devices, e.g., PE devices20,22within each of AS114and AS216. According to the disclosed techniques, BGP-LS92may be used to receive the contents of TEDs of the network devices including inter-AS TE metric values that indicate inter-AS route preferences, e.g., local preference values, MED values, and/or EROS.

Control unit82of centralized controller device80stores the received TED contents in routing tables91. Routing tables91may include the contents of TEDs of a plurality of network devices within both the first AS and the second AS. An example of routing tables91is as follows.

Lsdist.0—stores network topology data from TED

Lsdist.1—stores network topology data from IGP database

Control unit82may also forward the received TED contents to NTAD94. NTAD94may generate a network topology of the first AS and second AS based on the TED contents, and forward the topology data to topology unit97of path computation element90. Topology unit97may receive the topology data describing available resources of the network, including access, aggregation, and edge nodes, interfaces thereof, and interconnecting communication links. In this way, the inter-AS TE metric values for the inter-AS links are included in the network topology and routing tables91used by path computation element90to compute inter-AS LSPs.

Path computation unit96of path computation element90may use the topology data received by topology unit97and routing tables91to compute inter-AS LSPs across the first AS and the second AS of the network. As an example, path computation unit96may compute a first portion of an inter-AS LSP through the first AS based on a first set of intra-AS metric values for the first AS. Path computation unit96may then compute a second portion of the inter-AS LSP between the first AS and the second AS that includes a preferred one of the inter-AS links based on the inter-AS metric values. Path computation unit96may also compute a third portion of the inter-AS LSP through the second AS based on a second set of intra-AS metric values for the second AS.

According to the disclosed techniques, when computing an inter-AS LSP, path computation unit96may select a preferred outgoing route for the first AS from a plurality of outgoing routes based on a local preference value as one of the inter-AS metric values. In addition, path computation unit96may select a preferred incoming route for the first AS from a plurality of incoming routes based on a MED value as another one of the inter-AS metric values. In this way, path computation element90computes the inter-AS LSP taking the route preferences for the inter-AS links into account, instead of treating the inter-AS links simply as passive links.

Upon computing the paths, path computation unit96may schedule the paths for provisioning by path provisioning unit98. A computed path includes path information usable by path provisioning unit98to establish the path in the network. For example, path provisioning unit98may send the path information for the inter-AS LSP to network devices to instruct the network devices to establish at least a portion of the inter-AS LSP in the network. Provisioning a path may require path validation prior to committing the path to provide for packet transport.

FIG. 4is a conceptual diagram illustrating an example format of a local preference TLV110carried by BGP-LS. As described above, BGP-LS is an attribute of the BGP routing protocol used to carry link state and traffic engineering information from networks to external components, such as centralized controller device12fromFIG. 1. Information carried in BGP-LS is encoded in Type Length Value (TLV) triplets. As illustrated inFIG. 4, local preference TLV110includes a type field, a length field, and the local preference value. The type field defines a type of the TLV used to identify the TLV. The length field defines the length of the local preference value in octets. The value field defines a local preference value for a given inter-AS link that can be used to identify a preferred outgoing route of a given AS. For example, an inter-AS link having a highest local preference value among a plurality of inter-AS links may be identified as the preferred outgoing route.

According to the techniques of this disclosure, BGP-LS carries the local preference TLV110from PE devices20in AS114and PE devices22in AS216to centralized controller device12. The local preference TLV110carried by BGP-LS enables centralized controller device12to route inter-AS LSPs while taking the local preference value for the inter-AS links into account. In some cases, a similar local preference TLV may be carried in link state messages of an IGP. As one example, the local preference TLV may be carried in the Opaque LSA of the OSPF link state routing protocol as either a stand-alone TLV or as a sub-TLV. As another example, the local preference TLV may be carried in the IS-IS LSA. In some examples, local preference TLV110may be carried by all three protocols, i.e., BGP-LS, OSPF, and IS-IS, in the same network.

FIG. 5is a conceptual diagram illustrating an example format of a MED TLV112carried by BGP-LS. As described above, BGP-LS is an attribute of the BGP routing protocol used to carry link state and traffic engineering information from networks to external components, such as centralized controller device12fromFIG. 1. Information carried in BGP-LS is encoded in Type Length Value (TLV) triplets. As illustrated inFIG. 5, MED TLV112includes a type field, a length field, and the MED value. The type field defines a type of the TLV used to identify the TLV. The length field defines the length of the local preference value in octets. The value field defines a MED value for a given inter-AS link that can be used to identify a preferred incoming route of a given AS. For example, an inter-AS link having a lowest MED value among a plurality of inter-AS links may be identified as the preferred incoming route.

According to the techniques of this disclosure, BGP-LS carries the MED TLV112from PE devices20in AS114and PE devices22in AS216to centralized controller device12. The MED TLV112carried by BGP-LS enables centralized controller device12to route inter-AS LSPs while taking the MED value of a given AS into account. In some cases, a similar MED TLV may be carried in link state messages of an IGP. As one example, the MED TLV may be carried in the Opaque LSA of the OSPF link state routing protocol as either a stand-alone TLV or as a sub-TLV. As another example, the MED TLV may be carried in the IS-IS LSA. In some examples, MED TLV112may be carried by all three protocols, i.e., BGP-LS, OSPF, and IS-IS, in the same network.

FIG. 6is a flowchart illustrating an example operation of a network device sending inter-AS TE metric values to a centralized controller device, in accordance with the techniques of this disclosure. The example operation ofFIG. 6will be described with respect to network device50fromFIG. 2. In other examples, the operation illustrated inFIG. 6may be performed by any of PE devices20within first AS14or PE device22within second AS16fromFIG. 1.

Routing engine56of network device50within a first AS receives inter-AS TE metric values for one or more inter-AS links that indicate route preferences for routes between the first AS and a second AS (120). In one example, routing engine56may receive the inter-AS TE metric values directly from admin52of the first AS via user interface62. In another example, routing engine56of network device50may receive the inter-AS TE metric values in link state messages of an IGP, e.g., an Opaque LSA of OSPF74or a LSP of IS-IS75, from neighboring network devices within the first AS. In this example, admin52configures the inter-AS TE metric values, and the inter-AS TE metric values are then flooded to network devices within the first AS per IGP link state flooding procedures.

As described above, the inter-AS TE metric values for the inter-AS links may include one or more of local preference values that indicate a preferred outgoing route for the first AS, MED values that indicate a preferred incoming route for the first AS, or an ERO that indicates a specific route between the first AS and the second AS. Upon receiving the inter-AS metric values, routing engine56stores the inter-AS TE metric values in TED66of network device50(122). According to the disclosed techniques, TED66of network device50may store the inter-AS TE metric values for the inter-AS links and also store intra-AS TE metric values for intra-AS links within the first AS.

Routing engine56may then advertise the inter-AS TE metric values to other network devices within the first AS using a link state routing protocol of the IGP (124). In one example, the inter-AS TE metric values may be carried in an Opaque LSA of OSPF74. In another example, the inter-AS metric values may be carried in a LSP of IS-IS75. Routing engine56may advertise the intra-AS TE metric values in a similar manner.

In accordance with the disclosed techniques, routing engine56of network device50sends the contents of TED66including the inter-AS metric values to centralized controller device12of the first AS and the second AS (126). Routing engine56may send the contents of TED66to centralized controller device12using BGP-LS72. The inter-AS TE metric values may be encoded in newly defined TLVs carried by BGP-LS72, e.g., local preference TLV110fromFIG. 4and MED TLV112fromFIG. 5.

Based on the contents of TED66of network device50, centralized controller device12may compute an inter-AS LSP across the first AS and the second AS that takes the inter-AS TE metric values into account. Routing engine56of network device50then receives path information for the inter-AS LSP computed by centralized controller device12that includes a preferred one of the inter-AS links as indicated by the inter-AS TE metric values (128). The received path information for the inter-AS LSP indicates the route of the inter-AS LSP across the first AS and the second AS. Routing engine56of network device50then establishes at least a portion of the inter-AS LSP according to the path information (130).

FIG. 7is a flowchart illustrating an example operation of a centralized controller device routing inter-AS LSPs based on inter-AS TE metric values, in accordance with the techniques of this disclosure. The example operation ofFIG. 7will be described with respect to centralized controller device80fromFIG. 3. In other examples, the operation illustrated inFIG. 7may be performed by SDN controller12fromFIG. 1.

Centralized controller device80comprises a controller coupled to both a first AS and a second AS. According to the disclosed techniques, control unit82of centralized controller device80receives contents of a TED of a network device within the first AS, including inter-AS TE metric values for one or more inter-AS links that indicate route preferences for routes between the first AS and the second AS (140). Control unit82of centralized controller device80may also receive contents of TEDs of network devices within either or both of the first AS and the second AS.

The TED of the network device within the first AS, for example, may include both the inter-AS TE metric values for the inter-AS links and intra-AS TE metric values for links within the first AS. As described above, the inter-AS TE metric values for the inter-AS links may include one or more of local preference values that indicate a preferred outgoing route for the first AS, MED values that indicate a preferred incoming route for the first AS, or an ERO that indicates a specific route between the first AS and the second AS. Control unit82may receive the contents of the TED of the network device in the first AS using BGP-LS92. The inter-AS TE metric values may be encoded in newly defined TLVs carried by BGP-LS92, e.g., local preference TLV110fromFIG. 4and MED TLV112fromFIG. 5.

Control unit82of centralized controller device80stores the contents of the TED received from the network device within the first AS in routing tables91that include the contents of TEDs of a plurality of network devices within both the first AS and the second AS (142). In some examples, control unit82forwards the received TED contents to NTAD94running on control unit82. NTAD94may generate a topology of the first AS and the second AS based on the TED contents, and forward the topology to topology unit97of path computation element90. In this way, the inter-AS TE metric values for the inter-AS links are included in the network topology used by path computation element90to compute inter-AS LSPs.

Path computation element90of centralized controller device80then computes an inter-AS LSP that includes a preferred one of the inter-AS links based on routing tables91including the inter-AS TE metric values (144). For example, path computation element90may compute a first portion of the inter-AS LSP through the first AS based on a first set of intra-AS metric values for the first AS. Path computation element90may then compute a second portion of the inter-AS LSP between the first AS and the second AS that includes the preferred one of the inter-AS links based on the inter-AS metric values. Path computation element90may also compute a third portion of the inter-AS LSP through the second AS based on a second set of intra-AS metric values for the second AS.

According to the disclosed techniques, when computing the inter-AS LSP, path computation element90may select a preferred outgoing route for the first AS from a plurality of outgoing routes from the first AS to the second AS based on a local preference value as one of the inter-AS metric values. In addition, path computation element90may select a preferred incoming route for the first AS from a plurality of incoming routes to the first AS from the second AS based on a MED value as another one of the inter-AS metric values. In this way, path computation element90computes the inter-AS LSP taking the route preferences for the inter-AS links into account, instead of treating the inter-AS links simply as passive links.

Upon computing the inter-AS LSP, control unit82of centralized controller device80sends path information for the inter-AS LSP to the network device within the first AS in order to instruct the network device to establish at least a portion of the inter-AS LSP (146). The received path information for the inter-AS LSP indicates the route of the inter-AS LSP across the first AS and the second AS.

Various aspects of this disclosure have been described. These and other aspects are within the scope of the following claims.