Patent Description:
The present teachings relate to computer networks and, for example, distribution of information, such as topology and/or routing algorithm information, using a routing protocol.

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 controller, e.g., 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 controller may provide centralized control over an entire WAN including multiple ASes.

"<NPL>, discusses extensions to BGPLS address-family to advertise a Flexible Algorithm Definition as a part of topology information from a network.

<CIT> discusses methods and apparatus to communicatively couple virtual private networks to virtual machines within distributive computing networks.

Particular aspects are set out in the independent claims, with various optional embodiments being set out in the dependent claims.

In general, techniques are described by which a routing protocol, border gateway protocol (BGP), is extended to control propagation and importation of information using route targets (RTs) specified as bitmasks that encode link administrative group information. A network control device (referred to herein as "controller"), e.g., SDN controller, that manages the subscriber sessions and communication flows within a service provider network is configured to allocate one or more subset of resources (e.g., nodes and links) of an underlay network to each of one or more virtual networks established over the underlay network. The subset of resources can be used to direct traffic of a given network slice, virtual private network (VPN), or set of VPNs to best deliver end-to-end services. The controller outputs a routing protocol message, border gateway protocol - link state (BGP-LS), to advertise the subset of resources. In accordance with the disclosed techniques, the controller generates a bitmask encoded with link administrative group information (e.g., colors or other link affinities) associated with the links and attaches, to the BGP-LS advertisement, a route target specified as the bitmask to control the importation of the advertisement. Each bit of the bitmask corresponds to a different administrative group assigned to a link or set of links within a network. The route target specified as a bitmask is referred to herein as "bitmask route target.

Based on the advertisements (e.g., routing protocol message), each of the PE routers determines whether to import the advertisements based on the bitmask route target specified within the advertisements. For example, each router that is to import the advertisement is configured with one or more corresponding bitmask route targets. In response to receiving an advertisement, the router performs, for example, a logical 'AND' operation with the bitmask route target attached to the advertisement and the one or more bitmask route target(s) configured on the router. In response to determining that the result of the logical 'AND' operation is a non-zero value, the router imports the information carried by the routing protocol advertisement, such as topology information and/or algorithm information. In response to determining that the result of the logical 'AND' operation is zero, the router does not import the advertisement.

The techniques described in this disclosure may provide one or more technical advantages that realize a practical application. For example, instead of the controller having to send a respective advertisement carrying topology or algorithm information for each link administrative group defined within the network, the controller may send an advertisement having topology / algorithm information for a plurality of the link administrative groups (e.g., a subset or even all of the link administrative groups) with each of the administrative link groups to which the advertisement is directed being represented by a different one of the bits in the bitmask route target. In this way, the bitmask route target can be used to selectively identify any of the administrative link groups to control route propagation and importation by the individual routers, which reduces the number of advertisements required to be sent to the routers.

In one example, this disclosure is directed to a network control device comprising a network interface, and a control unit comprising at least one processor. The control unit of the controller device is configured to allocate one or more subset of resources of an underlay network to each of one or more virtual networks established over the underlay network, wherein the one or more subset of resources allocated to a respective virtual network includes one or more nodes and one or more links of the underlay network to be used by the respective virtual network; generate a bitmask encoded with link administrative group information associated with the one or more links, wherein each bit of the bitmask corresponds to a different one of a plurality of link administrative groups defined on the network control device, and wherein each of the link administrative groups define a different grouping of the one or more subset of resources of the underlay network; and output, to a plurality of provider edge (PE) routers that are participating in a respective virtual network, a routing protocol message to advertise the one or more subset of resources, wherein the routing protocol message includes a route target specified as the bitmask.

In another example, this disclosure is directed to a router comprising a plurality of network interfaces, and a control unit comprising at least one processor. The control unit of the router is configured to receive a routing protocol message that has an attached route target specified as a bitmask; and determine, based on the bitmask, whether to import the information carried by the routing protocol message.

In a further example, this disclosure is directed to a method comprising allocating, by a network control device, one or more subset of resources of an underlay network to each of one or more virtual networks established over the underlay network, wherein the one or more subset of resources allocated to a respective virtual network includes one or more nodes and one or more links of the underlay network to be used by the respective virtual network; generating, by the network control device, a bitmask encoded with link administrative group information of the one or more links, wherein each bit of the bitmask corresponds to a different one of a plurality of link administrative groups defined on the network control device, and wherein each of the link administrative groups define a different grouping of the one or more subset of resources of the underlay network; and outputting, by the controller and to a plurality of provider edge (PE) routers that are participating in a respective virtual network, a routing protocol message to advertise the one or more subset of resources, wherein the routing protocol message includes a route target specified as the bitmask.

<FIG> is a block diagram illustrating an example network for providing propagation and importation of border gateway protocol (BGP) routing information (e.g., routes, link/node information, routing algorithm information, and the like) using route targets (RTs) specified as bitmasks encoded with link administrative group information, in accordance with the techniques of this disclosure.

As illustrated in <FIG>, network system <NUM> includes a wide area network (WAN) <NUM> having underlay network topology <NUM> ("underlay topology <NUM>") and a plurality of remote sites 20A-20E ("sites <NUM>") connected to WAN <NUM>. In some examples, WAN <NUM> may support one or more virtual networks on top of underlay topology <NUM> in order to connect one or more of sites <NUM> across WAN <NUM>. For example, virtual networks may enable sites <NUM> to securely share data over WAN <NUM>. Virtual networks may comprise virtual private network (VPNs) or network slices configured with different performance and scaling properties.

WAN <NUM> may comprise the Internet or another public network. In some cases, WAN <NUM> may comprise a multi-protocol label switching (MPLS) network. In some cases, WAN <NUM> may comprise a mobile communication network, such as a <NUM> mobile network. WAN <NUM> has underlay topology <NUM>, which may comprise an Internet Protocol (IP) fabric of nodes and links. Although illustrated in <FIG> as a single topology, in one example underlay topology <NUM> of WAN <NUM> may comprise two or more autonomous systems (ASes). In this example, WAN <NUM> and the disclosed techniques support inter-AS connectivity. Each AS may comprise a collection of network devices under the control of a network service provider that offers services to customers at sites <NUM> that access WAN <NUM>. Services offered may include, for example, traditional Internet access, VoIP, video and multimedia services, and security services. Further example details of inter-AS connectivity in a WAN are described in <CIT>.

Each of sites <NUM> may include a local area network (LAN) or a wide area network (WAN) that comprises a plurality of subscriber devices, such as desktop computers, laptops, workstations, PDAs, wireless devices, network-ready appliances, file servers, print servers or other devices. In some examples, at least one of sites <NUM> may comprise a data center site having specialized facilities that provide storage, management, and dissemination of data to subscribers and other entities. A data center site may include, for example, a plurality of servers and storage area networks (SANs) that provide computing environments for subscribers / customers. Subscriber devices may connect to the data center site to request and receive services and data provided by the data center site.

In the illustrated example of <FIG>, WAN <NUM> includes a controller device <NUM>, provider edge (PE) routers 16A-16E ("PE routers <NUM>"), and transit routers, e.g., provider (P) routers 17A-17D. Controller <NUM> of WAN <NUM> may comprise a software defined network (SDN) controller that provides centralized control of customer sessions and communication flows within WAN <NUM>. In some examples, controller <NUM> is configured to allocate one or more subset of resources of underlay topology <NUM> to a respective virtual network. The subset of resources allocated to a virtual network includes, for example, one or more nodes and one or more links of underlay network <NUM> to be used by the virtual network. The subset of resources can be used to direct traffic of a given virtual network (e.g., network slice, VPN, or set of VPNs) to best deliver end-to-end services. In some examples, the subset of resources allocated to the virtual network may be a dedicated subset of resources that are only used to forward traffic of the virtual network. In other examples, the subset of resources allocated to the virtual network may be at least partially shared and used to forward traffic of multiple virtual networks. Controller <NUM>, therefore, may configure and manage the routing and switching infrastructure within WAN <NUM> (e.g., including PE routers <NUM> and P routers <NUM>). Further example details of an SDN controller are described in <CIT>, and <CIT>.

Each of PE routers <NUM> couples to one or more of remote sites <NUM> via customer edge (CE) routers 18A-18E ("CE routers <NUM>"), respectively. For example, PE router 16A is coupled to site 20A via CE router 18A, PE router 16B is coupled to site 20B via CE router 18B, PE router 16C is coupled to site 20C via CE router 18C, PE router 16D is coupled to site 20D via CE router 18D, and PE router 16E is coupled to site 20E via CE router 18E. PE devices <NUM> are connected to P routers <NUM> via links 15A-15J (collectively, "links <NUM>"), e.g., Ethernet links.

PE routers <NUM> may compute one or more paths for virtual networks established over underlay topology <NUM>. As one example, PE routers <NUM> may use segment routing techniques, e.g., a Source Packet and Routing Networking (SPRING) paradigm, to advertise network segments between nodes using interior gateway protocols (IGPs) or to controller <NUM> using border gateway protocol - link state (BGP-LS) and build single or multi-hop tunnels within an IGP domain, e.g., WAN <NUM>. In segment routing, the "path" information for segments is disseminated between the routers within an IGP domain (or between the routers and controller <NUM> using BGP-LS) as part of the IGP link state information for the respective domain. An ingress router is able to steer a packet through an ordered list of instructions or segments by prepending one or more segment identifiers (SIDs) to the packet. In other words, an ingress router can steer a packet through a desired set of nodes and links by prepending the packet with an appropriate combination (stack) of SIDs. Segment routing allows routers to enforce a flow through any topological path and service chain while maintaining per-flow state only at the ingress node to each domain.

Segment routing is further described in<NPL>, while Segment Routing use cases are described in <NPL>. Further details regarding SPRING are found in (<NUM>) "<NPL>; (<NUM>)<NPL>; and (<NUM>)"<NPL>.

In some examples, PE routers <NUM> may implement flexible algorithm techniques to compute constraint-based paths based on different algorithms. The algorithms may define, for example, calculation types, metric types, and/or constraints used to compute paths. For example, calculation types may include IGP algorithms defined under "Interior Gateway Protocol (IGP) Parameters" IANA registries or other calculation mechanisms. Metric types may include the type of metrics used to compute the best paths along a constrained topology, such as an IGP metric, minimum unidirectional link delay, traffic engineering default metric, etc. The constraints may, for example, restrict paths to links with specific affinities or avoid links with specific affinities. A type of constraint may be to compute a path along a subset links associated with a particular color. Color is a generic notion which may represent any characteristic or property of the network, such as virtual topology, network slice, path computation algorithm, traffic engineering constraint (e.g., latency, bandwidth, etc.), administrative profile, etc. In the example of <FIG>, links 15A, 15B, and 15C may be associated with a first color (e.g., "red") that represents links with a first link attribute (e.g., low latency) and may be used to compute constraint-based path 22A from PE router 16A to PE router 16D. Similarly, links 15A, 15D, and <NUM> may be associated with a second color (e.g., "blue" color) that represents links with a second link attribute (e.g., high bandwidth) and may be used to compute constraint-based path 22B from PE router 16A to PE router 16D. Additional examples of color constraints are described in <NPL>. Further examples of flexible-algorithm are described in<NPL>.

In some current example solutions, an administrator may assign one or more administrative groups (e.g., colors) to links of each router (e.g., via a command-line interface of the router). After the links have been configured, routers typically use IGP to flood the IGP domain with a flexible-algorithm definition that includes the combination of (a) calculation-type, (b) metric-type, and (c) constraints, and may be identified by a flexible-algorithm identifier. The flexible-algorithm definition may include the link administrative group information that identifies the link attribute (e.g., color). However, in these examples, each of the routers send and receive flexible algorithm definitions and link administrative group information throughout an IGP domain and every router may compute a path for each algorithm, which is inherently unscalable (e.g., when there is a larger number of algorithms).

To address scalability issues, a network may, in some examples, include a controller to allocate one or more subset of resources of underlay topology <NUM> to PE routers <NUM> participating in a respective virtual network. For example, the controller may use BGP-LS to advertise the subset of resources (e.g., as a BGP-LS attribute attached to a link network layer reachability information (NLRI)) for the virtual network to PE routers participating in the virtual network. However, if a link belongs to different link administrative groups, then the controller typically advertises a respective BGP-LS advertisement for each link administrative group the link belongs to, which is also inherently unscalable (e.g., when a link has a larger number of assigned colors). Moreover, without the presently taught techniques, BGP-LS does not support the advertisement of flexible-algorithm definitions.

In accordance with the techniques described in this disclosure, controller <NUM> and PE routers <NUM> provide propagation and importation of BGP-LS routes using route targets specified as bitmasks encoded with link administrative group information, in accordance with the techniques of this disclosure.

In the example of <FIG>, controller <NUM> may configure link administrative groups for links of each router in WAN <NUM>. As described above, links 15A, 15B, and 15C may be associated with a first color (e.g., "red") that represents links with a first link attribute (e.g., low latency) and may be used to compute constraint-based path 22A from PE router 16A to PE router 16D. Similarly, links 15A, 15D, and <NUM> may be associated with a second color (e.g., "blue" color) that represents links with a second link attribute (e.g., high bandwidth) and may be used to compute constraint-based path 22B from PE router 16A to PE router 16D. After allocating the links for the one or more virtual networks, controller <NUM> may generate a bitmask encoded with link administrative group information associated with the links. Each bit of the bitmask may correspond to a different administrative group assigned to a link or set of links within the network. In this example, controller <NUM> may set a first bit, e.g., the least significant bit, of the bitmask with a value of '<NUM>' which represents link 15A is assigned with a red color. Controller <NUM> may also set a second bit, e.g., the next bit from the least significant bit, of the bitmask with a value of '<NUM>' which represents link 15A is assigned with a blue color. The bitmask, in this example, is therefore set as '<NUM>'. The example bitmask is merely an example and may be any variable length.

Controller <NUM> may then advertise the subset of resources (e.g., colored links) to PE routers <NUM> using a route target specified as the bitmask. For example, controller <NUM> may attach the route target specified as the bitmask to a BGP-LS advertisement (e.g., BGP update message). The route target specified as the bitmask may be referred to herein as "bitmask route target.

Each of PE routers <NUM> may then import or discard the advertisement (e.g., routing protocol messages) based on whether the respective PE router is participating in the virtual network, as indicated by the bitmask route target included in the advertisement. For example, PE router 16A, as an example, receives a routing protocol message that advertises the subset of resources of underlay network <NUM> allocated to the virtual network in which PE router 16A is participating. In order to import the advertisement for the virtual network, PE router 16A may perform a logical 'AND' operation with the bitmask route target attached to the routing protocol message and a bitmask route target configured on PE router 16A. Routers that need to learn the information are configured with one or more bitmask route targets, with the bits set for the link administrative groups that the routers want to import. The bitmask route target may be stored in an import route target list. As one example, PE router 16A may be configured with a route target specified as a bitmask of <NUM>, which may represent PE router 16A is to import routes for links associated with the colors red (e.g., first bit) and blue (e.g., second bit).

When PE router 16A receives a BGP-LS advertisement, PE router 16A may perform a logical 'AND' operation with the bitmask route target attached to the BGP-LS advertisement and the bitmask route target configured on PE router 16A, and if the result of the logical 'AND' operation is a non-zero value, PE router 16A imports the information carried by the routing protocol message, such as topology information and/or algorithm information. Alternatively, or additionally, if the result of the logical 'AND' operation is zero, PE router 16A does not import the information carried by the routing protocol message. As one example, controller <NUM> may send a bitmask route target as <NUM> attached to a BGP-LS advertisement. In response to receiving the BGP-LS advertisement, PE router 16A performs a logical 'AND' operation with the bitmask route target attached to the BGP-LS advertisement (e.g., <NUM>) and the bitmask route target in its route target import list (e.g., <NUM>). In this example, PE router 16A determines that the result of the logical 'AND' operation results in a non-zero value and imports the information carried by the routing protocol message, such as topology information and/or algorithm information. Alternatively, or additionally, PE router 16A may import a BGP-LS advertisement with a bitmask route target of <NUM> or a bitmask route target of <NUM>.

In some examples, controller <NUM> may also advertise a BGP-LS advertisement including a flexible algorithm definition (e.g., calculation type, metric type, included/excluded administrative group) defining the topology used for the algorithm. For example, BGP-LS comprises a new BGP Network Layer Reachability Information (NLRI) encoding format to specify the flexible algorithm definition. In this way, controller <NUM> may advertise a BGP-LS advertisement including NLRI specifying the flexible algorithm definition and is attached to a bitmask route target encoded with the link administrative group associated with the flexible algorithm definition.

In some examples, a bitmask route target may also be used for route target constraint mechanisms. Routers may use route target constraints to indicate interest in receiving only routes including particular route targets. Additional examples of route target constraint mechanisms are described in<NPL>. In accordance with the techniques of this disclosure, routers may send, for example, a BGP advertisement (e.g., BGP update message) including route target membership information identifying a respective bitmask route target that it is interested in receiving. For example, BGP peers (e.g., PE routers <NUM>) may each send BGP advertisements including route target membership NLRI identifying a bitmask route target that it is interested in receiving. A BGP peer that receives the route target membership information may use the route target membership NLRI to control propagation of subsequent advertisements to each of the other PE routers <NUM> depending on whether the advertisements include a bitmask route target the other PE router is interested in. In this way, routers that implement bitmask route target for route target constraint mechanisms may restrict propagation of advertisements to only routers that have advertised interest in receiving advertisements including a particular bitmask route target, which may reduce the number of advertisements in the network.

<FIG> is a block diagram illustrating an example router configured to provide importation of border gateway protocol routing information using route targets specified as bitmasks encoded with link administrative group information, in accordance with the techniques of this disclosure.

In general, router <NUM> may operate substantially similar to any of PE routers <NUM> of <FIG>. In the illustrated example of <FIG>, router <NUM> includes interface cards 88A-88N ("IFCs <NUM>") that receive packets via incoming links 90A-90N ("incoming links <NUM>") and send packets via outbound links 92A-92N ("outbound links <NUM>"). IFCs <NUM> are typically coupled to links <NUM>, <NUM> via a number of interface ports (not shown in <FIG>). Router <NUM> also includes a control unit <NUM> that determines routes of received packets and forwards the packets accordingly via IFCs <NUM>.

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

Routing engine <NUM> operates as the control plane for router <NUM> and includes an operating system that provides a multi-tasking operating environment for execution of a number of concurrent processes. Routing engine <NUM> may implement one or more protocols <NUM> to execute routing processes. For example, protocols <NUM> may include BGP-LS <NUM>, OSPF <NUM>, and IS-IS <NUM> for exchanging link state information with other routing devices in the computer network. Routing engine <NUM> uses the Interior Gateway Protocol (IGP) link state routing protocols, OSPF <NUM> and/or IS-IS <NUM>, to exchange /routing information with other routing devices in the same IGP area or autonomous system (AS) in order to discover the topology of the IGP area or AS and update link state database (LSDB) <NUM>. Although not illustrated in <FIG>, routing engine <NUM> may also include a segment routing component to implement segment routing techniques, such as SPRING. Routing engine <NUM> maintains LSDB <NUM> configured to store link state information about nodes and links within the computer network in which router <NUM> resides, e.g., underlay topology <NUM> of WAN <NUM> from <FIG>. For example, LSDB <NUM> may include one or more of local/remote internet protocol (IP) addresses, local/remote interface identifiers, link metrics and traffic engineering (TE) metrics, link bandwidth, reservable bandwidth, class of service (CoS) reservation state, preemption, or shared risk link groups (SRLG).

Routing engine <NUM> may use BGP-LS <NUM> to share link state information collected by the IGP link state routing protocols with external components, such as controller <NUM> (which may represent an example implementation of controller <NUM> of <FIG>). BGP-LS is further described in <NPL>. In accordance with the techniques described in this disclosure, routing engine <NUM> may also use BGP-LS <NUM> to receive, from controller <NUM>, one or more subset of resources allocated to a given virtual network in which router <NUM> is participating. BGP-LS <NUM> comprises a new BGP Network Layer Reachability Information (NLRI) encoding format. In BGP-LS <NUM>, the MP_Reach_NLRI and MP_UNREACH_NLRI attributes are used to carry opaque information, including the subset of resources allocated to the given virtual network. For example, each link state NLRI describes either a node, a link, or a prefix. In some examples, the MP_Reach_NLRI and MP UNREACH NLRI attributes may also be used to carry route target membership NLRI information for route target constraint mechanisms.

Routing information <NUM> may describe various routes within the network and the appropriate next hops for each route, i.e., the neighboring routing devices along each of the routes. Routing engine <NUM> analyzes LSDB <NUM> to generate routing information <NUM> and install forwarding data structures into forwarding information <NUM> of forwarding engine <NUM>. In accordance with the disclosed techniques, routing engine <NUM> may generate a separate one of routing information <NUM> and forwarding information <NUM> for each of the virtual networks in which router <NUM> participates. The separate routing and forwarding tables created for each of the virtual networks in which router <NUM> participates are called Virtual Routing and Forwarding (VRF) tables. In general, one of routing information <NUM> comprises a global routing table for the entire computer network in which router <NUM> resides, e.g., underlay topology <NUM> of WAN <NUM> from <FIG>.

In accordance with the disclosed techniques, routing engine <NUM> include a route importation unit <NUM> that controls importation of BGP routes using route targets specified as bitmasks encoding link administrative group information. In this example, routing engine <NUM> is configured with a bitmask route target <NUM> stored in routing information <NUM>. For example, an administrator may configure bitmask route target <NUM> via an interface (not shown in <FIG>) of router <NUM> and store the bitmask route target <NUM> in an import route target list in routing information <NUM>. As described in this disclosure, bitmask route target <NUM> may represent a bitmask encoded with link administrative group information, where each bit of the bitmask corresponds to a different administrative group assigned to a link or set of links within the network.

Route importation unit <NUM> is configured to determine whether to import an incoming advertisement (e.g., BGP-LS update message) based on the bitmask route target attached to the incoming advertisement. For example, when router <NUM> receives a BGP-LS advertisement from controller <NUM>, route importation unit <NUM> may perform a logical 'AND' operation on the bitmask route target attached to the received BGP-LS update message and bitmask route target <NUM> configured on router <NUM>. If the result of the logical 'AND' operation is a non-zero value, route importation unit <NUM> imports the information carried by the routing protocol advertisement, such as topology information and/or algorithm information, e.g., by storing the route into routing information <NUM>. If the result of the logical 'AND' operation is zero, route importation unit <NUM> does not import the incoming route.

In some examples, the incoming BGP-LS advertisement includes a flexible algorithm definition. For example, BGP-LS <NUM> comprises a new BGP Network Layer Reachability Information (NLRI) encoding format to specify a flexible algorithm definition. For example, router <NUM> may in some instances receive, from controller <NUM>, a BGP-LS advertisement including NLRI specifying the flexible algorithm definition and is attached to a bitmask route target encoded with the link administrative group associated with the flexible algorithm definition.

Based on the imported route, routing engine <NUM> is configured to annotate LSDB <NUM> to indicate which resources (e.g., colored links) of the underlay topology of the computer network are allocated for a given virtual network. As one example routing engine <NUM> may add flags or other indicators to LSDB <NUM> to mark the advertised subset of resources as usable for the given virtual network. Routing engine <NUM> in essence masks-off or ignores the remaining resources of the underlay topology of the computer network included in LSDB <NUM> when performing routing services for the given virtual network. In this way, routing engine <NUM> has a restricted view of the full underlay topology of the computer network and, thus, only uses the subset of resources in the restricted view to generate one of routing tables <NUM> and one of forwarding tables <NUM> for the given virtual network.

Forwarding engine <NUM> operates as the data plane for router <NUM> for forwarding network traffic. In some examples, forwarding engine <NUM> may comprise one or more packet forwarding engines (PFEs) (not shown) that may each comprise a central processing unit (CPU), memory and one or more programmable packet-forwarding application-specific integrated circuits (ASICs). Forwarding information <NUM> may associate, for example, network destinations with specific next hops and corresponding interface ports of IFCs <NUM>. Forwarding information <NUM> may be a radix tree programmed into dedicated forwarding chips, a series of tables, a complex database, a link list, a radix tree, a database, a flat file, or various other data structures.

The architecture of router <NUM> illustrated in <FIG> is shown for by way of example only. The techniques of this disclosure are not limited to this architecture. In other examples, router <NUM> may be configured in a variety of ways. In one example, some of the functionally of control unit <NUM> may be distributed within IFCs <NUM> or a plurality of packet forwarding engines (PFEs) (not shown). Control unit <NUM> may be implemented solely in software, or hardware, or may be implemented as a combination of software, hardware, or firmware. For example, control unit <NUM> may include one or more processors which execute software instructions. In that case, the various software modules of control unit <NUM> may comprise executable instructions stored on a computer-readable medium, such as computer memory or hard disk.

<FIG> is a block diagram illustrating an example controller configured to provide propagation of border gateway protocol routing information using route targets specified as bitmasks encoded with link administrative group information, in accordance with the techniques of this disclosure. For purposes of illustration, controller device <NUM> may be described herein within the context of network system <NUM> of <FIG>, and may represent controller <NUM>. The architecture of controller device <NUM> illustrated in <FIG> is shown for example purposes only and should not be limited to this architecture. In other examples, controller device <NUM> may be configured in a variety of ways.

Controller device <NUM> includes a control unit <NUM> coupled to a network interface <NUM> to exchange packets with other network devices by inbound link <NUM> and outbound link <NUM>. Control unit <NUM> may 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). Alternatively, or additionally, control unit <NUM> may comprise dedicated hardware for performing the techniques described herein.

Control unit <NUM> provides an operating environment for path computation element (PCE) <NUM>, network topology abstractor daemon (NTAD) <NUM>, resource allocation unit <NUM>, and route propagation unit <NUM>. 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 controller device <NUM>, aspects of these units may be delegated to other computing devices. Control unit <NUM> also provides an operating environment for several protocols <NUM>, including BGP-LS <NUM>.

Control unit <NUM> may use BGP-LS <NUM> to receive link state information from PE routers within a computer network, e.g., underlay topology <NUM> of WAN <NUM> from <FIG>. Control unit <NUM> may also forward the received link state information to NTAD <NUM>. NTAD <NUM> may generate a network topology (e.g., underlay topology <NUM> of WAN <NUM> from <FIG>) based on the received link state information.

As illustrated in <FIG>, PCE <NUM> includes a path computation unit <NUM>, a topology unit <NUM>, and a path provisioning unit <NUM>. NTAD <NUM> may forward the topology data to topology unit <NUM> of PCE <NUM>. Topology unit <NUM> may receive the topology data describing available resources of the computer network, including access, aggregation, and edge nodes, interfaces thereof, and interconnecting communication links. Path computation unit <NUM> of PCE <NUM> may use the topology data received by topology unit <NUM> to compute paths across the computer network. Upon computing the paths, path computation unit <NUM> may schedule the paths for provisioning by path provisioning unit <NUM>. A computed path includes path information usable by path provisioning unit <NUM> to establish the path in the network. For example, path provisioning unit <NUM> may send the path information to network devices to instruct the network devices to establish at least a portion of the path in the network. Provisioning a path may require path validation prior to committing the path to provide for packet transport.

Control unit <NUM> includes resource allocation unit <NUM> configured to allocate one or more subset of the resources (e.g., nodes and/or links) included in the topology data of the computer network to a respective virtual network established over the computer network. For example, NTAD <NUM> may also forward the topology data to resource allocation unit <NUM>. Resource allocation unit <NUM> may be configured to allocate the subset of resources to the respective virtual network based on source information, destination information, and classification information for traffic of the respective virtual network. The classification information may comprise link administrative group information, e.g., color or other link attribute, for the traffic.

In accordance with the disclosed techniques, control unit <NUM> includes a route propagation unit <NUM> configured to provide propagation of border gateway protocol routes using route targets specified as bitmasks encoded with link administrative group information. For example, NTAD <NUM> may also forward the topology data to route propagation unit <NUM> such that route propagation unit <NUM> may generate a bitmask representing the link administrative group information. For example, controller <NUM> may generate a bitmask with each bit of the bitmask corresponding to a different administrative group assigned to a link or set of links within a network.

As one example, controller <NUM> may receive, e.g., from an administrator, instructions to assign link 15A with a first color (e.g., red) and a second color (e.g., blue). In response, route propagation unit <NUM> generates a bitmask with bits set for each of the colors assigned to link 15A. Control unit <NUM> may then use BGP-LS <NUM> to advertise the subset of resources to one or more network devices that are participating in the respective virtual network (e.g., PE routers 16A and 16D of <FIG>) as a restricted view of the underlay network topology for the respective virtual network. The BGP-LS advertisements may be tagged using route targets to identify the respective virtual network. In accordance with the disclosed techniques, the route targets are specified with the bitmask generated by route propagation unit <NUM>.

<FIG> is a block diagram illustrating an example bitmask route target, in accordance with the techniques described in this disclosure. In the example of <FIG>, bitmask route target <NUM> may represent a transitive BGP community container as described in <NPL>. The BGP community container may include a global administrator (GA) type <NUM>, a global administrator length <NUM>, a global administrator <NUM>, a local administrator <NUM>, a bitmask length <NUM>, and bitmask <NUM>.

Global administrator type <NUM> may include an autonomous system number, an IPv4 address or an IPv6 address. For a global administrator type <NUM> of autonomous system number, the global administrator length <NUM> may include a length of <NUM>-octets. For a global administrator type <NUM> of IPv4 address, the global administrator length <NUM> may include a length of <NUM>-octets. For a global administrator type <NUM> of IPv6 address, the global administrator length <NUM> may include a length of <NUM>-octets.

Bitmask <NUM> may have a variable length defined by bitmask length <NUM> (e.g., <NUM>-octet bitmask length). As described in this disclosure, bitmask <NUM> is encoded with link administrative group information. A controller may attach bitmask route target <NUM> to a BGP-LS advertisement (e.g., BGP update message) and send the BGP-LS advertisement to PE routers participating in a particular virtual network.

<FIG> is a flowchart illustrating an example operation of a controller and a PE router configured to provide importation and propagation of border gateway protocol routing information using route targets specified as bitmasks encoded with link administrative group information, in accordance with the techniques of this disclosure. The operation of <FIG> is described with respect to controller <NUM> and one of PE routers <NUM> of <FIG>. In other examples, the operation of <FIG> may be performed by controller <NUM> of <FIG> and/or router <NUM> of <FIG>.

Controller <NUM> allocates one or more subset of resources of underlay network topology <NUM> to each of one or more virtual networks <NUM> established over underlay network <NUM> (<NUM>). Underlay network <NUM> may comprise an IP fabric of nodes and links. In some examples, underlay network <NUM> comprises a WAN that includes one or more autonomous systems. As described above, virtual networks may comprise one or more VPNs or multiple network slices with different performance and scaling properties on top of underlay network <NUM>. The subset of resources allocated to a respective virtual network includes one or more nodes and one or more links of underlay network <NUM> to be used by the virtual network. In some examples, the subset of resources allocated to the virtual network may be a dedicated subset of resources that are only used to forward traffic of the virtual network. In other examples, the subset of resources allocated to the virtual network may be at least partially shared and used to forward traffic of multiple virtual networks.

Controller <NUM> may allocate the subset of resources to the virtual network based on constraint information to restrict paths to links with specific affinities or avoid links with specific affinities. A type of constraint may be to compute a path along a subset links associated with a particular color. For example, controller <NUM> may allocate certain links of underlay network <NUM> that are used to build routes between pairs of source and destination devices in accordance with a particular color.

After allocating the subset of resources to the virtual network, controller <NUM> generates a bitmask encoded with link administrative group information associated with the one or more links (<NUM>). Each bit of the bitmask may correspond to a different one of a plurality of link administrative groups defined on the network control device. Moreover, each of the link administrative groups may define a different grouping of the subset of resources of the underlay network. For example, link 15A may be associated with a first color (e.g., red) that represents a link with a first link attribute (e.g., low latency). Link 15A may also be associated with a second color (e.g., "blue" color) that represents a link with a second link attribute (e.g., high bandwidth). Controller <NUM> may set a bit for each of the link administrative groups associated with link 15A. For example, controller <NUM> may set a first bit of the bitmask (e.g., <NUM>) to represent the link is associated with the color red and set a second bit of the bitmask (e.g., <NUM>) to represent the link is associated with the color blue, which results in a bitmask of <NUM>.

Controller <NUM> then outputs a routing protocol message to advertise the subset of resources to the plurality of PE routers <NUM> that is participating in the virtual network (e.g., PE routers 16A and 16D), wherein the routing protocol message includes a route target specified as the bitmask (<NUM>). According to the disclosed techniques, controller <NUM> advertises the subset of resources to the plurality of PE routers <NUM> using BGP-LS advertisements including a route target specified as the bitmask.

Each of PE routers <NUM> may then import or discard the advertisement based on whether the respective PE router is participating in the virtual network, as indicated by the bitmask route target included in the advertisement. For example, PE router 16A, as an example, receives the routing protocol message that advertises the subset of resources of underlay network <NUM> allocated to the virtual network in which PE router 16A is participating (<NUM>). As previously discussed, in order to import the advertisement for the virtual network, PE router 16A may perform a logical 'AND' operation with the route target attached to the routing protocol message and a route target configured on PE router 16A (<NUM>). Routers that need to learn the information are configured with one or more bitmask route targets, with the bits set for the link administrative groups that the routers want to import. As one example, PE router 16A may be configured with a route target specified as a bitmask of <NUM>, which may represent PE router 16A is to import routes for links associated with the colors red (e.g., first bit) and blue (e.g., second bit).

In response to determining that the result of the logical 'AND' operation with the route target attached to the advertisement and the route target configured on PE router 16A is a non-zero value ("YES" of step <NUM>), PE router 16A imports the information carried by the routing protocol message, such as topology information and/or algorithm information (<NUM>). Alternatively, in response to determining that the result of the logical 'AND' operation with the route target attached to the advertisement and the route target configured on PE router 16A is zero ("NO" of step <NUM>), PE router 16A does not import the routing protocol message (<NUM>).

If implemented in hardware, this disclosure may be directed to an apparatus such a processor or an integrated circuit device, such as an integrated circuit chip or chipset. Alternatively, or additionally, if implemented in software or firmware, the techniques may be realized at least in part by a computer-readable data storage medium comprising instructions that, when executed, cause a processor to perform one or more of the methods described above. For example, the computer-readable data storage medium may store such instructions for execution by a processor.

A computer-readable medium may form part of a computer program product, which may include packaging materials. A computer-readable medium may comprise a computer data storage medium such as random access memory (RAM), read-only memory (ROM), non-volatile random access memory (NVRAM), electrically erasable programmable read-only memory (EEPROM), Flash memory, magnetic or optical data storage media, and the like. In some examples, an article of manufacture may comprise one or more computer-readable storage media. A computer-readable medium may also or alternatively comprise a transient medium such as a transmission signal or carrier wave. Such transient media may occur between components of a single computer system, and/or between multiple separate computer systems.

In some examples, the computer-readable storage media may comprise non-transitory media. The term "non-transitory" may indicate that the storage medium is not embodied in a carrier wave or a propagated signal. In certain examples, a non-transitory storage medium may store data that can, over time, change (e.g., in RAM or cache).

The code or instructions may be software and/or firmware executed by processing circuitry including one or more processors, such as one or more digital signal processors (DSPs), general purpose microprocessors, application-specific integrated circuits (ASICs), field-programmable gate arrays (FPGAs), or other equivalent integrated or discrete logic circuitry. In addition, in some aspects, functionality described in this disclosure may be provided within software modules or hardware modules.

Claim 1:
A network control device (<NUM>, <NUM>) comprising:
a network interface (<NUM>); and
a control unit (<NUM>) comprising at least one processor configured to:
allocate one or more subset of resources of an underlay network (<NUM>) to each of one or more virtual networks established over the underlay network, wherein the one or more subset of resources allocated to a respective virtual network includes one or more nodes and one or more links of the underlay network to be used by the respective virtual network;
generate a bitmask (<NUM>) encoded with link administrative group information associated with the one or more links, wherein each bit of the bitmask corresponds to a different one of a plurality of link administrative groups defined on the network control device, and wherein each of the link administrative groups define a different grouping of the one or more subset of resources of the underlay network; and
output, to a plurality of provider edge 'PE' routers (<NUM>) that are participating in a respective virtual network, a routing protocol message to advertise, using Border Gateway Protocol-Link State 'BGP-LS' advertisements, the one or more subset of resources, wherein the routing protocol message includes a route target (<NUM>) specified as the bitmask.