VIRTUAL ROUTING AND FORWARDING USING IDENTICAL ANYCAST IDENTIFIERS ON EDGE DEVICES

Virtual routing and forwarding techniques in a Virtual Routing and Forwarding (VRF) systems using a common base label and a common index are provided herein. An advertisement is received from a device external to the VRF system, the advertisement including an address of the device. Egress edge devices of the VRF system communicate to determine the common base label and the common index to be associated with the address. A data packet is received from a network device in the VRF system. A match is determined between an overlay label of the data packet and a label value corresponding to a combination of the common base label and the common index. A set of operations are performed modifying the overlay label based on the match. The modified data packet is sent to the device external to the VRF system.

BACKGROUND

The present application relates to computer network technology and, more particularly, to virtual routing and forwarding.

In computer networks, virtual routing and forwarding (VRF) enables a plurality of network routes to be established between a pair of devices that are remotely located to each other. Network devices providing the network routes may maintain a plurality of routing tables that are used to route network communications between different pairs of devices. In some instances, multiple network routes between a pair of devices may be established for redundancy and load balancing purposes. When a network device or a connection in a network route is disrupted, a new set of routes may be determined, which may involve recalculating load balancing between devices, relabeling devices, and/or reconfiguring routes. As the size of a network grows, so too does the amount of computing resources involved in responding to and correcting for disruptions in VRF networks. In sufficiently large networks, the computing resources allocated to such corrections can become enormous.

DETAILED DESCRIPTION

Overview

The present disclosure describes techniques and technology for allocating resources in VRF network topologies to provide node level redundancy. In the following description, for purposes of explanation, numerous examples and specific details are set forth to provide a thorough understanding of the present disclosure. It will be evident, however, to one skilled in the art that the present disclosure as expressed in the claims may include some or all of the features in these examples, alone or in combination with other features described below, and may further include modifications and equivalents of the features and concepts described herein.

Network virtualization is the ability to decouple the physical topology from a virtual topology using tunneling, for example. The physical topology or underlay network is the physical infrastructure that transports data packets across the network. The virtual topology or overlay network is built on top of the underlay network and is a virtual transport network of nodes and logical links where multiple layers of network abstraction can be created. The transport network is adapted to control the sequence of overlay nodes a data packet traverses before reaching its destination. By decoupling the underlay network from applications, network-wide virtualization can optimize computing and storage resources. Network virtualization has become a central part of network design for some organizations.

Virtual routing and forwarding (VRF) is a technology implemented in a computer networking environment that allows multiple instances of a routing table to exist simultaneously on the same network device. VRF is an extension of internet protocol routing and enables configuration of multiple routing table instances to simultaneously coexist within the same router. VRFs may provide network isolation/virtualization at Layer 3 of the Open Systems Interconnection (OSI) model as Virtual Local Area Networks (VLANs) serve at Layer 2. VRF techniques may involve the creation of Virtual Private Network (VPN) tunnels to be dedicated to a single network or client.

The VRF system disclosed herein involves determination, by edge devices of a VRF system, of a base label common among the edge devices, a unique index value specific to the VRF system, and an anycast next-hop address common among the edge devices. The base label and the index, together forming the anycast label for a VRF, and the anycast next-hop address help to provide redundancy among edge devices of the VRF system.

A plurality of egress provider edge (EPE) devices may be provided for redundancy in a routing instance of a VRF system connecting a pair of edge devices external to the VRF system. In some implementations, an ingress provider edge (IPE) device calculates a plurality of redundant paths through the VRF system that each include a different EPE. As a result of disruption associated with one of the EPEs, the IPE may need to recalculate the paths through the VRF system. As the size of VRF systems and the number of devices serviced grows, such recalculations may impose a significant hardware and computational burden on the IPE to determine equal-cost multi-path routes. Moreover, data packets can be lost due to the network disruptions despite recalculation of the network paths. The foregoing problem applies equally to gateway devices that connect two separate and independent VRF systems, such as those provided by two different entities.

The present disclosure provides synchronization of the base label, the index, and the anycast next-hop address for the edge devices of the VRF system. In connection with establishing a routing instance through the VRF system between a pair of external edge devices, a group of the EPEs communicate with each other to determine the common base value. The EPEs also communicate with each other to determine a unique index value to be combined with the common base label value to generate a unique label associated with an individual route but with their own unique next-hops. The EPEs may advertise the common base label, the index, and the common next-hop address to network devices in the VRF system, such as routers. The common base label, the index, and the common next-hop address are propagated to some nodes of the VRF system. As a result, the IPE encapsulates network traffic received from a first external edge device (e.g., a customer edge device) using a combination of the common base label and the index as a first overlay label.

A routing device receives the encapsulated packet and determines an EPE of the plurality of EPEs to send the data packet based on the first underlay label. The routing device removes the first underlay label and sends the data packet with the first overlay label to the EPE determined. If the routing device determines that a network connection between the routing device and the EPE is disrupted, the routing device sends the encapsulated data packet to another one of the EPEs. The EPE receives the encapsulated data packet from the router and determines that the data packet should be sent to the external edge device based on the overlay label. The EPE may modify the overlay label and may send the unencapsulated data packet over a network connection to the external edge device. If the network connection between the EPE and the external edge device is disrupted, the EPE may send the encapsulated data packet to a different EPE in the same group of EPEs. The different EPE may effectuate transmission of the data packet based on the first underlay label.

The foregoing techniques may be applied to gateway devices, which may receive an encapsulated data packet from a routing device. The gateway device(s) may encapsulate the data packet with a label provided by a gateway device of another VRF system and send the encapsulated data packet to the other gateway device. As a result, the gateway device of the different VRF system may receive and repackage the data packet with a different underlay label and/or a different overlay label. The gateway device may then route the re-encapsulated data packet through the other VRF system to an EPE device of the different VRF system, which then decapsulates the data packet and sends the data packet to the external edge device.

The terms “route” or “routing instance,” as used herein, refer to a collection of network segments through a VRF system between a pair of customer edge devices. Routes or routing instances may include a plurality of paths through the VRF system. The term “path,” as used herein, refers to a collection of network segments that includes a single EPE. A route, by contrast, may comprise a plurality of different paths through the VRF system. A route may include a set of equal cost multipaths (ECMPs) through the VRF system, the ECMPs each accruing the same “cost” to transfer a data packet from an ingress edge of the VRF system to an egress edge of the VRF system.

System Architecture

FIG.1illustrates an example network topology100in which a VRF system mediates communications according to one or more embodiments. The network topology100includes a VRF system102that mediates communications between a customer edge device104and a customer edge device106over one or more networks. The edge device104may be remotely located to the edge device106such that the edge devices104and106may be in different buildings, different regions, or different continents.

The VRF system102implements Multiprotocol Label Switching (MPLS) techniques in which network devices provide an underlay network for directing communications that include overlay data packets between the remotely located edge devices104and106. The VRF system102may establish a routing instance in which labels are assigned to data packets and the labels are used as a basis for conveying the data packets through a plurality of network segments. Each network segment comprises a pair of network devices linked by a network connection established in an initiation session, e.g., using a Transmission Control Protocol.

The VRF system102may be provisioned by a third-party service provider (e.g., an internet service provider) external to the edge devices104and106. The VRF system102may be provisioned using Border Gateway Protocol (BGP), an Open Shortest Path First (OSPF) protocol, Intermediate System to Intermediate System (IS-IS), an Enhanced Interior Gateway Routing Protocol (EIGRP), ISIS-SR, label Distribution Protocol (LDP), or another such routing protocol known to those skilled in the art. A processor-based device108(e.g., a controller) may instantiate the VRF system102as a result of a request provided by one or both of the edge devices104and/or106. The processor-based device108may control various parameters associated with the VRF system102, as described herein. The VRF system102includes multiple connections (e.g., VPN tunnels) for a given edge device to provide redundancy and load-balancing between devices of the VRF system102.

The VRF system102includes a Label Switched Path (LSP) comprising an ingress provider edge (“IPE”) device110, a router112, and a set of egress provider edge (“EPE”) devices114-1,114-2, and114-3(collectively “egress provider edges114” or “EPEs114”). The IPE110is communicatively connected with the edge device104along a first edge of the VRF system102. The IPE110, for example, may be connected with the edge device104via a VPN tunnel. In some embodiments, the IPE110may be directly connected with the edge device104without intervening devices therebetween. The EPEs114are communicatively connected (e.g., via a VPN tunnel or may be directly connected) with the edge device106along a second edge of the VRF system102. In connection with establishing the VRF system102, a data structure is generated for each node in the VRF system102indicating routing or forwarding information. For instance, the IPE110, the router112, and the set of EPEs may store routing tables that provide information for routing and/or forwarding data packets in the VRF system102. Non-limiting examples of such routing tables include routing information bases, forwarding information bases, and label forwarding information bases.

Communications between devices or nodes of the VRF system102and the edge devices104or106are according to a first communication protocol, such as Transmission Control Protocol/Internet Protocol (TCP/IP). By contrast, communications among the devices or nodes within the VRF system102are according to a second communication protocol, such as Border Gateway Protocol (BGP), Interior Gateway Protocol (IGP), or Label Distribution Protocol (LDP).

The ingress provider edge110is a network device (e.g., a router, network switch) that receives a data packet from the edge device104. The IPE110compares IP header information in the data packet with information in a data structure (e.g., Routing table, FIB). The IPE110determines a label for the data packet based on the comparison. The IPE110adds an MPLS header to the data packet that includes the label determined. The IPE110transmits the data packet with the MPLS header to the router112.

The router112is a hardware device constituting a network node that reflects routes or forwards data packets between network devices of the VRF system102. Non-limiting examples of the term “router,” as used herein, include label switching routers, route reflectors, or other similar devices operating as intermediary nodes between ingress provider edge devices and egress provider edge devices (e.g., between IPE110and the EPEs114). The router112exchanges routing information for other internal peers in the VRF system102. The router112, for instance, advertises information regarding routes associated with the EPEs114to the IPE110. The router112also advertises information regarding routes associated with the IPE110to the EPEs114. The router112stores, in memory, a data structure (e.g., a Label Information Base) in which individual labels of a first set of MPLS labels are associated with individual labels of a second set of MPLS labels for the VRF system102. It is understood that there may be more than one router between the IPE110and the EPEs114.

The router112receives, from the IPE110, the data packet with the label and determines a new label associated with the label received based on an association referenced in the data structure. The router112replaces the label on the data packet with the new label determined. The router112sends the data packet with the new label to an EPE114-1of the set of EPEs114corresponding to the new label. Those of skill in the art will appreciate that a LSP may include more than one router112between the IPE110and the EPEs114. The EPE114-1receives the data packet with the new MPLS label and removes the MPLS label from the data packet. The EPE114-1sends the data packet to the edge device106according to the first communication protocol (e.g., IPv4, IPv6).

Several issues may arise that affect operation of the VRF system102. A tunnel between the router112and the EPE114-1may be disrupted or discontinued, for instance. Another potential issue is that operation of the EPE114-2may experience a disruption (e.g., outage). A further potential issue is that a connection118between the EPE114-3and the edge device106may be disrupted or discontinued. Such issues may prevent or inhibit a data packet from the edge device104to reach the edge device106via an intended LSP for a given data packet.

As a result of detecting the occurrence of a disruption in the VRF system102, such as the aforementioned issues, the IPE110may determine and establish a different set of LSPs through the VRF102for load-balancing or redundancy purposes. Significant computational resources may be involved in determining a different set of paths, which may impact performance of the VRF system102, e.g., in mediating communications between other edge devices external to the VRF system102. As the size and complexity of the VRF system102grows to provide routing and forwarding services to external edge devices, so too do the computational resources involved in determining the new set of paths to address issues disrupting operation of the VRF system102.

FIG.2illustrates a network topology200that includes a portion of a VRF system102that mediates communications according to one or more embodiments. The VRF system102includes a set of egress provider edge devices (EPEs)114-1,114-2,114-3(collectively “egress provider edges114” or “EPEs114”) that send communications to customer edge devices external to the VRF system102, as described inFIG.1and elsewhere herein. The EPEs114determine reachability information206to be advertised to other nodes of the VRF system102for the one or more paths. Although three egress provider edges114are shown and described with respect toFIG.2, it is understood that the number of EPEs114may be more or less than three in some embodiments.

The EPEs114-1,114-2,114-3may respectively establish border gateway protocol (BGP) communication sessions205-1,205-2, and205-3(collectively “BGP communication sessions205” or thru any static or dynamic routing protocols) with external edge device106according to one or more communication protocols. The external edge device106may be a device of a customer of a service provider that owns, operates, or otherwise exercises control over the VRF system102. The EPEs114may establish the BGP communication sessions205, e.g., based on a neighbor statement. The IP network/subnet214(10.0.0.0/24) is a network advertised over BGP or any other communicating protocol such as OSPF/ISIS, etc., by the external edge device106in this non-limiting example. The EPEs114may determine at least some of the reachability information206as a result of establishing the BGP communication sessions205. The BGP communication sessions205are, in some embodiments, external BGP (EBGP) sessions established according to an EBGP communication protocol.

The reachability information206determined by the EPEs114includes the prefix, a common anycast next-hop address208, a common base label210(applies for the device), and an index212. The anycast next-hop address208(reachable within VRF system102) may be formatted according to a Layer 2 or a Layer 3 communication protocol, such as IPv4, IPV6, or VXLAN, by way of non-limiting example. The common base label210is a label formatted according to a Layer 3 communication protocol, such as those associated with MPLS (e.g., BGP, IGP). The index212is an offset value to be combined with the common base label210. The index212is specific to the VRF instance associated with the external edge device106. The group of EPEs114may determine a different index212for a VRF instance associated with a different customer; however, the base label210is specific to the group of EPEs114in some embodiments.

The EPEs114may exchange communications with RR/IPE (e.g., via the control plane) to determine the anycast next-hop address208, the common base label210, and the index212. The EPEs need to be provisioned with the same next-hop address, base label and the same unique index for a VRF. In some embodiments, the anycast next-hop address208may be formatted according to an IPV4 or IPv6 communication protocol.

The EPEs114synchronize or coordinate the anycast next-hop address208, the base label210, and the index212using one or more communication protocols, such as Border Gateway Protocol Segment Routing (BGP-SR). In the network topology200shown, the value of the anycast next-hop address208is 33.34.35.0, the value of the base label210is 116000, and the value of the index212is 384. As a result of establishing the anycast next-hop address208, the common base label210, and the index212, the EPEs114store the reachability information206in local memory (e.g., read-only memory) to be used for communications in a specific path through the VRF202. The anycast next-hop address208, the common base label210, and the index212may be stored by the EPEs114in association with an identifier of the specific route established or to be implemented. The EPEs114each store the same address208and the same common base label210for the specific route. The EPEs114each have a unique next-hop address209that is specific or unique to the egress provider edge. EPE114-1, for example, has a next-hop address209-1with a value of 1.1.1.1; EPE114-2has a next-hop address209-2with a value of 2.2.2.2; and EPE114-3has a next-hop address209-3with a value of 3.3.3.3. In an embodiment, unique NHs would be advertised by the EPEs with other members of the EPE group with the IBGP mesh created between the EPEs to handle the network disruptions but with the same base label210and index212. This path will become active depending on the BGP best path algorithm (or when used as backup path).

FIG.3illustrates routing and reachability information an example network topology300in which a VRF system mediates communications according to one or more embodiments. The network topology300includes a VRF system102that mediates communications between a customer edge device104and a customer edge device106over one or more networks as described above. The VRF system102includes egress provider edge devices114-1,114-2,114-3(collectively “EPEs114”) provided on an edge of the VRF system102. The EPEs114advertise reachability information206to one or more peers in the VRF system102, such as a router112. The reachability information206may be advertised as a Layer 3 communication, such as a communication provided over a control plane of a network of the VRF system102. The EPEs114implement a VRF instance that is specific to a customer (e.g., edge device106ofFIG.2).

The reachability information206advertised includes an anycast next-hop address208, a base label210, and an index212, which are determined as described with respect toFIG.2. The reachability information206may include an identifier of a route with which the reachability information206is associated. The anycast next-hop address208, in some embodiments, may have a format according to a Layer 2 or a Layer 3 communication protocol, such as IPv4, IPv6, or VXLAN. In some embodiments, the anycast next-hop address208is provided as a remote-next hop address in a specified path. The base label210and the index212may be formatted according to an MPLS protocol, such as BGP or IGP. The reachability information206includes information that is specific to the VRF's customer (external edge device106), such as the anycast next-hop address208and/or the index212.

The reachability information206advertised to the router112by each of the EPEs114includes the same next-hop address208, the same base label210, and the same index212. Reachability information206-1is advertised by the EPE114-1in connection with a routing instance between a pair of customer edge devices (e.g., edge devices104and106). Reachability information206-2is advertised by the EPE114-2in connection with a routing instance between the pair of customer edge devices. Reachability information206-3is advertised by the EPE114-3in connection with a routing instance between the pair of customer edge devices. The reachability information206-1,206-2,206-3includes the anycast next-hop address208, the base label210, and the index212. In some embodiments, the reachability information206may be provided to the router112by the EPEs114in response to a request from the router112for such reachability information.

In some embodiments, the EPEs114may provide next-hop addresses specific to the EPEs to the router112and/or the IPE110. For instance, with reference toFIG.2, EPE114-1may provide the next-hop address209-1, EPE114-2may provide the next-hop address209-2, and EPE114-3may provide the next-hop address209-3. In some embodiments, the EPEs114may provide the EPE specific next-hop addresses to the router112and/or the IPE110as part of or in connection with the reachability information206. In some embodiments, the EPEs114provide the EPE specific next-hop addresses prior to provisioning the reachability information206or in a process separate from generating and provisioning the reachability information206. The router112and/or the IPE110may use the EPE-specific next-hop addresses, at least in part, to distinguish between the EPEs114.

The router112receives the reachability information206-1,206-2,206-3provided by the EPEs114and updates routing information318regarding the path to be implemented between the edge devices104and106. In some embodiments, the routing information318updated is routing information included in a data structure, such as a routing table, a forwarding information base (FIB), a label forwarding information base (LFIB), a routing information base (RIB), or other similar data structure. Updating the routing information318, in some implementations, may include generating a data structure and including the reachability information206-1,206-2,206-3as routing information318in the data structure. Updating the routing information318may include storing information specific to the EPEs114in association with the reachability information206-1,206-2,206-3, such as information of the EPE114-1,114-2,114-3.

The router112may advertise, to an ingress provider edge device110of the VRF system102, the routing information318that includes at least some of the reachability information206. The ingress provider edge device110may update routing information322based on the routing information318provided. Updating the routing information322may include updating a data structure to include at least the prefix, base label210, and index212(base label+index forms the anycast label) provided by the router112. The router112may advertise at least some of the reachability information206to the ingress provider edge110or other routers according to an appropriate communication protocol, such as Label Distribution Protocol (LDP) or BGP. The VRF system102may synchronize routing information, such as a common MPLS label of the EPEs114or BGP Prefix Segment Identifiers, among the IPE110, the router112, and/or the EPEs114using techniques documented by the Internet Engineering Task Force. Non-limiting examples of such techniques include RFC 8669 (last updated Sep. 9, 2021), RFC 4760 (last updated Jan. 21, 2020), and RFC 8277 (last updated Oct. 19, 2017).

FIG.4illustrates routing a packet using an example network topology400in which a VRF system mediates communications according to one or more embodiments. A VRF system102establishes a route through which a customer edge device104and a customer edge device106can communicate as described above. The route includes a set of LSPs through which the VRF102can route encapsulated data packets using MPLS routing information, as described herein. The VRF system102implements Multiprotocol Label Switching techniques in which VPNs provide Internet Protocol (e.g., IPv4, IPv6) services to the remotely located edge devices104and106.

The route established by the VRF system102includes an ingress provider edge device110, a router112, and egress provider edge devices114-1,114-2,114-3(collectively “EPEs114”). The ingress provider edge110stores routing information322in a data structure, such as a routing table or a Routing Information Base (RIB). The routing information322includes information associated with the set of paths of the routing instance, such as a plurality of MPLS labels that correspond to a routing instance associated with the EPEs114. The routing information322further includes one or more common anycast next-hop addresses208provided by the EPEs114.

The router112also stores routing information318in a data structure, such as a routing table or a Label Forwarding Information Base (LFIB). The routing information318may also include information associated with the set of paths of the routing instance, such as labels advertised by the EPEs114. In some embodiments, the routing information318may include a common anycast next-hop address208provided by the EPEs114, the common anycast next-hop addresses208corresponding to a group of EPEs providing redundancy. The router112may advertise the common anycast next-hop address208to the IPE110in connection with the labels advertised by the EPEs114.

FIG.5Aillustrates example network information502that may be stored by an ingress provider edge device110according to one or more embodiments. The network information502may include reachability information and/or routing information, as described herein. The network information502includes one or more sets of path information504-1,504-2,504-3. . .504-N regarding LSPs established by the VRF system102. The sets of path information504may include a route506, an LDP label508, a base label210, an index212, an anycast next-hop address208, and/or information indicating an operation516to be performed involving a received data packet. The route information504-1,504-2,504-3. . .504-N may include additional information or exclude some of the information in the network information502in some embodiments. In some embodiments, entries in the network information502may include a plurality of routing tables for distribution of VRF/VPN routing information. Each routing table may include an IP-formatted address prefix (e.g., IPv4 address, IPv6 address) and a subnet mask—for instance, a BGP routing table may be associated with an IPV4/mask of 10.0.0.0/24. Some of the path information shown in504-1may be stored in different tables or arrays in some embodiments.

The route506identifies a route established to facilitate communications between customer edge devices, such as the edge devices104and106. The route506may have a format that includes an IP/IPV6 address. The LDP label508is an MPLS label generated according to the Label Distribution Protocol. The LDP label508is an identifier specific to the EPEs114. For instance, the LDP label508has a value of 132768 and may correspond to the anycast next-hop address208(33.34.35.0) of the EPE114-1inFIG.2.FIG.5Aillustrates FIB information502that combines the label information1500ofFIG.5Dand the routing information518ofFIG.5B. For example, inFIG.5BRoute ID would include the route distinguisher and target identifier may be as follows:

The base label210and the index212together make up an MPLS label advertised to the IPE110by the router112, as described with respect toFIG.3. In some embodiments, the base label210and the index212are stored as different entries in a routing table. In some embodiments, the base label210and the index212are combined into a single value (e.g., 116384) and stored in a routing table.

Different routes through the VRF system102may have different sets of path information. A single instance of path information associated with a single route, however, may include information associated with a plurality of paths through the VRF system102. For instance, an overlay label generated based on the path information504-1inFIG.5A, for instance, has a value of 116384 that corresponds to a routing instance comprising a plurality of paths that each include one of the EPEs114inFIG.5B. The overlay label generated based on the path information504-1may correspond to a combination of the common base label210and the index212. More specifically, an overlay label116384generated based on the path information504-1may correspond to the value384of the index212added to the value116000of the common base label210(seeFIG.2), as included in the reachability information206discussed with respect toFIG.3.

The path information520-1further includes the next-hop address208advertised by the EPEs114to the router112in connection with advertisement of the base label210and the index212, as also described with respect toFIG.3. The anycast next hop address208has an VPN-IPV4/V6 NH address format, such as “RD+33.34.35.0”, but only “33.34.35.0” is considered for brevity as shown inFIG.5B. The operation information516in the path information504-1indicates an MPLS operation to be performed for data packets received from the edge device104that matches route506in FIB.504-1is derived from path information520-1,520-2,520-3of5B along withFIG.5D. Thus, path information504-1is not an equal cost multi-path (ECMP) in the forwarding information base (FIB).

The IPE110routes encapsulated data packets through established paths in the VRF system102based on the network information502. In previous implementations, an IPE may perform load-balancing operations, such as a set of hashing operations, to select a path through the VRF system102to route a data packet received. In such implementations, in response to a network disruption associated with one of the EPEs, the IPE would recompute or recalculate the ECMPs through the VRF system. Additionally, the IPE would store a different MPLS label generated according to BGP for each EPE.

By contrast, the VRF system102reduces the computational resources involved in obviating or responding to a network disruption associated with one or more of the EPEs412. If operation of one of the EPEs114or a network connection in the VRF system102to the EPEs114is disrupted, though IPE110recomputes the path, as long as even one path is available, the FIB will remain the same on the IPE in the VRF system102. Therefore, an encapsulated packet sent by the IPE110to one of the EPEs114will still reach the edge device106. Moreover, the network information502maintained by the IPE110includes the same overlay/service/VRF label116384for all of the EPEs114associated with the route506in the path information504-1. As described herein, the router112performs load-balancing operations for the route including the paths through the EPEs114instead of the IPE110.

FIG.5Billustrates example network information518that may be stored by an IPE or RR according to one or more embodiments. The network information518may include reachability information and/or routing information, as described herein. The network information518includes one or more sets of path information520-1,520-2,520-3,520-4, . . .520-N regarding LSPs established by the VRF system. The sets of path information520-1,520-2,520-3,520-4, . . .520-N may each include a route identifier522, an LDP label524, a base label210, an index212, an anycast next-hop address208, and/or a BGP endpoint identifier532.

In some embodiments, the base label210and the index212may be combined into a single entry in each path information520-1,520-2,520-3,520-4, . . .520-N. For instance, the path information520-1,520-2,520-3,520-4, . . .520-N may each include a single entry in which the base label210is combined with the index212, resulting in a value of 116384. The router112in the data path, in some implementations, performs load-balancing or forwards the data packet(s) received from the IPE110using the LDP label508or420-A of Label information1500.

In some embodiments, each instance of the path information520may include an identifier of one of the EPEs114. An example of such an identifier is the BGP endpoint532, tied with the unique next-hop addresses209discussed with respect toFIG.2. The EPE identifier is useable by the router112to identify with which of the EPEs114the particular instance of the path information520is associated. For instance, the path information520-1may include an identifier associated with the EPE114-1, the path information520-2may include an identifier associated with the EPE114-2, and the path information520-3may include an identifier associated with the EPE114-3. In some embodiments, the EPE identifier includes information specific to the individual EPE, such as a MAC address or a network segment identifier. The router112may use the EPE identifier to differentiate between the EPEs114.

In some embodiments, entries in the network information502may include a plurality of routing tables for distribution of VRF/VPN routing information. Each routing table may include an VPN IPV4/V6-formatted address prefix (e.g., IPv4 address, IPv6 address) and a subnet mask—for instance, a BGP routing table may be associated with an IPV4/mask of 10.0.0.0/24. Some of the path information shown in path information504-1may be stored in different tables or arrays in some embodiments.

The route identifier522identifies a route established to facilitate communications between customer edge devices, such as the edge devices104and106. The route identifier522may have a format that includes a VPN IPv4/IPV6 address and a route target identifier as per RFC 4364 (e.g., 8100=RDe1:10.0.0.0/24+RT1, 8101=RDe2:10.0.0.0/24+RT1, 8102=RDe3:10.0.0.0/24+RT1). A route wherever referred is the actual IPV4/IPV6 prefix derived from route ID by stripping of the RD and RT.

FIG.5Cillustrates example VFR label information560that may be stored by an egress provider edge device114according to one or more embodiments. The VFR label information560may include overlay label420-B. Overlay label420-B may be created by a combination of the base label210and the index212. Based on the information in the overlay label420-B, the EPE114will perform an operation550, such as IPv4/IPv6 routing in VRF system102.

FIG.5Dindicates the Label Information Base that gets populated by label distribution protocols like LDP or ISIS-SR. The label to reach the anycast NH208(33.34.35.0) would be underlay420-A (132768).

Referring back toFIG.4, the VRF system102establishes a routing instance for communications between the edge device104and the edge device106. The routing instance has network segments that include the IPE110, the router112, and the EPEs114. The IPE110and the router112(acting as LSR) respectively utilize the routing information322and318described with respect toFIGS.5A and5Dto route data packets through the routing instance.

Those skilled in the art will appreciate that the techniques described herein may be implemented without a router, a route reflector, and/or or a label switching router. For instance, the VRF system102may be implemented without the router112. In such implementations, the data packet422having the overlay420-B may be sent from the IPE110to the EPE114-1without the underlay420-A. Substantially similar modifications may apply to the VRF systems102,702,902, and/or908, as described with respect toFIGS.6,7, and9infra.

Subsequent to establishing a routing instance, the ingress provider edge110receives, over the routing instance, a data packet418from the edge device104. The data packet418includes a header and a payload. The header includes a destination address advertised by the edge device106and may be formatted according to one or more protocols, such as IPv4, IPV6, or VXLAN, such as 10.0.0.0/24.

The IPE110determines, based on the routing information322, that the destination address is associated with a next hop of the routing instance, such as the anycast next hop address208advertised by the EPEs114, as discussed with respectFIG.3. The IPE110determines an MPLS label to apply based on the anycast next hop address208. More particularly, the IPE110determines that the path information504-1includes route506matching the address provided in the header of the data packet418.

Based on the match between the address in the header and the IPV4/IPV6 address of route506in the path information504-1in the FIB, the IPE110generates an encapsulated data packet420that includes the data packet418and an MPLS Layer 2 frame. Generating the encapsulated data packet420includes encapsulating the data packet418with an underlay label420-A and an overlay label420-B based on the path information504-1. The underlay label420-A is an MPLS label generated according to LDP. To generate the overlay label420-B, the IPE110combines or adds the base label210and the index212of the path information504-1. As described herein, the base label210and the index212are reflected to the IPE110by the router112.

The router112receives the encapsulated data packet420and performs a set of operations to select an EPE of the EPEs114to which to send a data packet422. The router112, more particularly, refers to the routing information318to determine a label switching operation to be performed on the data packet420and a destination for a data packet422resulting from the label switching operation. In some implementations, the label switching operation may include a POP operation in which the underlay420-A is removed to reveal the overlay420-B. In some implementations, the label switching operation includes a SWAP operation in which the underlay420-A is exchanged with a different underlay label in the routing information318.

In the VRF instance implemented in the VRF system102for communications between the edge devices104and106, the router112performs a POP operation to remove the underlay420-A. The router112performs a load-balancing technique to select an EPE among the EPEs114to which the encapsulated packet420will be sent based on LFIB (based on label information1500), which is outside the scope of this document. Non-limiting examples of such load-balancing techniques include hash-based ECMP techniques, round robin ECMP techniques, and weighted ECMP techniques. In connection with performing a hash based ECMP technique, the router112may select a hashing key of a plurality of hashing keys stored in memory of the router112to use in a given hashing operation.

The encapsulated packet422includes an overlay420-B, which in this particular non-limiting example, has a value of 116384. The data packet422includes the data packet418encapsulated in an MPLS frame. The router112forwards the data packet422to the EPE114-1.

The EPE114-1receives the encapsulated packet422from the router112. The EPE114-1determines one or more operations to be performed and a destination for the data packet422based on the overlay label420-B. In some embodiments, the EPE114-1determines a destination address of a data packet based on a comparison between the overlay420-B and routing information424stored in memory of the EPE114-1, as seen inFIG.5C. The EPE114-1may, for instance, remove the overlay label420-B and send the data packet418to the edge device106according to a defined communication protocol, such as IPv4 or IPv6 based on the FIB (Not depicted in any of the diagrams which is pure IPV4/V6 routing/forwarding).

The VRF systems described herein are more robust to mitigate network disruptions associated with the EPEs.FIG.6illustrates an example network topology600in which a VRF system102mediates communications according to one or more embodiments with respect to routing during network disruptions. The features described with respect to the network topology600are substantially similar to those described with respect to the network topology400, so further description thereof is omitted for brevity.

A router112sends an encapsulated data packet422to an EPE114-1. In the network topology600, a network connection624between the EPE114-1and an edge device106is disrupted (e.g., experiences an outage). In previous implementations, an IPE would recalculate routes and/or paths (e.g., ECMPs) through a VRF system in response to a network disruption associated with the EPEs114. However, the VRF system102is adapted to operate despite such disruptions without imposing computational burdens on hardware of an IPE110of the VRF system102.

In the VRF system102, the EPEs114-1,114-2,114-3are configured to communicate with each other through IBGP mesh, which advertises the prefixes with their own nexthop address, to transmit data packets to the edge device106as a result of detecting a disruption in a network connection with the edge device106. For instance, the router112receives an encapsulated data packet420and selects EPE114-1as a recipient for a data packet422, as described with respect toFIG.4. The EPE114-1receives the data packet422from the router112having an overlay label or service label corresponding to the overlay label420-B. The EPE114-1may decapsulate the data packet422in some embodiments by removing the overlay label of the data packet422(e.g., overlay420-B ofFIG.4). The EPE114-1determines the data packet422should be sent to the edge device106based on routing information424-1stored in memory/FIB of the EPE114-1. The routing information424includes the reachability information206described with respect toFIG.3.

The EPE114-1determines that a network connection624between the EPE114-1and the edge device106is unavailable (e.g., due to a network disruption). In response to the determination that the network connection624is unavailable, the EPE114-1may reference the routing information424-1and determine that the EPE114-2and the EPE114-3are also associated with a same VRF instance for the data packet422. As a result of detecting the match, the EPE114-1sends the data packet422to the EPE114-2over a network connection626between the EPEs114-1and114-2or it could go through the router112again. Before sending the data packet422to the EPE114-2, the EPE114-1may re-encapsulate the data packet422with the overlay label the EPE114-1previously removed. For instance, with reference again toFIG.4, the EPE114-1may encapsulate the data packet422with the overlay label420-B. The EPE414-2determines, based on the routing information424-2, to send a decapsulated data packet418to the edge device106. In some embodiments, each of the EPEs114may have a network connection with a plurality of other EPEs114—for instance, the EPE114-1may also be communicatively coupled with the EPE114-3for sending data packets.

The VRF102is also configured to handle disruptions between the router112and the EPEs114. For instance, the edge device104may send a data packet418addressed to the edge device106via the VRF system102. The router112receives an encapsulated data packet420from the IPE110and selects EPE114-3as the next recipient of the data packet420. However, the router112may detect that a network connection630(e.g., LDP/VPN tunnel) with the EPE114-3is disrupted or that the EPE114-3is unable to receive or process data packets—for instance, the EPE114-3may be powered off or may be offline for updates. The router112may detect a network disruption associated with the EPE114-3as a result of receiving a notification message from one of the EPEs114indicating the network disruption in the EPE114-3or in the network connection630.

In previously implemented VRF systems, the ingress provider edge (or other entity of the VRF system) would recalculate MPLS routes through a VRF system as a result of detecting that the EPE114-3or the network connection630is unavailable. In the VRF system102, by contrast, the router112uses the routing information318(corresponding to the label information1500ofFIG.5D) to select a different one of the EPEs114to send the data packet. The router112may select the EPE114-2having the same underlay label508as the EPE114-3based on the path information504-1as encapsulated by IPE by looking intoFIG.5D. In some embodiments, the router112forwards the data packet based on the LDP label508to one of the EPEs114available—in this particular example, the router112may forward the data packet to the EPE114-2based on the LDP label508. The router112sends an encapsulated data packet632to the EPE114-2, which decapsulates the data packet632and sends the data packet418to the edge device106.

FIG.7illustrates an example network topology700in which a VRF system702mediates communications between multiple external edge devices according to one or more embodiments. The VRF system702maintains routing information for mediating communications from edge devices704,705to one or more of a plurality of edge devices706-1,706-2,706-3, and706-4(collectively “edge devices706”). The VRF system702implements a plurality of routing instances wherein individual routing instances are between the edge device704and one of the edge devices706. The VRF system702includes IPEs708-1and708-2; routers710-1and710-2; and EPEs712-1,712-2, and712-3.

With reference toFIG.8C, in the VRF system702, groups or subsets of the EPEs712may be formed based on one or more routing strategies, such as ECMP techniques discussed herein. For instance, a first group of EPEs for communications with the edge devices706-1and706-2includes the EPEs712-1and712-2corresponding to customer A/VRF_A. A second group of EPEs for communications with the edge devices706-3and706-4includes the EPEs712-2and712-3corresponding to customer B/VRF_B.

The EPEs712communicate with each other to determine reachability information713to be advertised to peers in the VRF system702for communications to the edge devices706. The routers710-1and710-2respectively generate routing information714-1and714-2based on the reachability information713-1,713-2,713-3advertised by the EPEs712. The IPEs708-1and708-2respectively generate and store routing information709-1and709-2according to routing information provided by the routers710-1and710-2, as described with respect toFIGS.4,5A,5B, and elsewhere herein.

FIG.8Cillustrates reachability information generated by sets of the EPEs712based on communications between the EPEs712. The EPEs712-1and712-2store, in memory, network information802-1regarding routes between the EPEs712-1,712-2and the edge devices706-1and706-2. The EPEs712-2and712-3store, in memory, network information802-2regarding routes between the EPEs712-2,712-3and the edge devices706-3and706-4.

The network information802may include reachability information and/or routing information, as described herein. The network information802will be exchanged between the group of associated EPEs operating in cooperation to route data packets to external edge devices corresponding to customers. The network information802includes a base label806common to the associated EPEs. The base label806useable to label data packets for forwarding to the associated EPEs in the VRF system702. The network information802may include a unique but common index808associated with a particular VRF instance of the VRF system702to an external edge device. The unique index808is unique to the VRF instance or to a particular external edge device706but is common among a defined group of egress provider edge devices indicated in the group information804, but804itself will not be part of802and used here just for the purpose of understanding. The same is applicable henceforth wherever mentioned. As a specific non-limiting example, the unique index808having a value of 384 is particular to the customer A/VFR A having one of the external edge devices706-1but is common among the group of EPE712-1and EPE712-2indicated in the group information804. EPE712-1and EPE712-2use the unique index808in connection with network traffic in the VRF system702between the customer A/VRF_A having external edge devices704and one of the external edge devices706-1. The network information802may include an overlay label810corresponding to a combination of the base label806and the unique index808.

The network information802using the IBGP mesh is used to handle the network disruptions apart from advertising network information518, and further includes a unique next-hop IP address812that the EPEs collectively determine in connection with the unique index808. The network information802may include destination addresses814of one of the external edge devices706. The network information802may include or indicate an action830inFIG.8Bto be performed on a data packet having an overlay or service label matching one of labels810. Some of the network information802may be stored in different tables or arrays in some embodiments. The network information may include route ID813and EPE ID815.

By way of example, the group information804in the network information802-1identifies the EPEs712-1and712-2as belonging to a group that coordinates to route data packets to customer A/VRF_A having external edge devices706-1and706-2. The base label806of the network information802-1is advertised by the EPEs712-1and712-2for routing data packets to the customer A/VRF_A having edge devices706-1and706-2. The network information802-1includes a unique index808with a value of 384 that is designated for data packets to be routed to customer A/VRF_A having the edge device706-1/706-2.

The group information804in the network information802-2identifies the EPEs712-2and712-3as belonging to a group that coordinates to route data packets to customer B/VRF_B having external edge devices706-3and706-4. The base label806of the network information802-2is advertised by the EPEs712-2and712-3for routing data packets to the customer B/VRF_B having edge devices706-3and706-4. The network information802-2includes a unique index808with a value of 419 that is designated for data packets to be routed to the customer B/VRF_B having edge device706-3/706-4.FIG.8Dfurther illustrates example label information1510that may be stored by an egress provider edge device712-1,712-2,712-3according to one or more embodiments. As shown inFIG.8D, an overlay label810may be created by a combination of the base label806and the index808. Based on the information in the overlay label810, the EPE712-1,712-2,712-3will perform an operation816, such as POP or IPv4/IPv6 routing in VRF system702(Customer A/VRF_A or Customer B/VRF_B).

FIG.8Bshows example network information818stored by EPEs of the VRF system702according to one or more embodiments.8B is derived from8C and8G. The network information818may include reachability information and/or routing information, as described herein. The network information818may be stored in one or more routing tables or forwarding tables, each routing or forwarding table storing information for sending encapsulated data packets through a particular routing instance. The network information818includes a plurality of sets of path information820-1,820-2, . . .820-N each associated with a particular path through one of the EPEs712to one of the edge devices706. The path information820-1is associated with a path through EPE712-1to edge device706-1of customer A/VRF_A, the path information820-2is associated with a path through EPE712-2to edge device706-1of customer A/VRF_A, the path information820-3is associated with the path through EPE712-2to edge device706-3of customer B/VRF_B, and the path information820-4is associated with the path through EPE712-3to edge device706-3of customer B/VRF_B.

Each set of path information820includes a route822, an LDP label823, a base label824, an index826, a next-hop address828, and an operation830. The path information820-1and820-2shown inFIG.8Bincludes some information that is substantially similar. The path information820-3and820-4shown inFIG.8Bincludes some information that is substantially similar. The base labels824, the index826, and the next-hop address828respectively correspond to the base labels806, the indexes808, and the next-hop IP addresses812advertised by the EPEs712. Each of the LDP labels823is specific to next-hop address828.

FIG.8Eillustrates example network information892that may be stored by an IPE or RR/router according to one or more embodiments. The network information892may include reachability information and/or routing information, as described herein. The network information892includes one or more sets of path information820-1,820-2,820-3,820-4, . . .820-N regarding LSPs established by the VRF system. The sets of path information820-1,820-2,820-3,820-4, . . .820-N may each include a route identifier822, a base label824, an index826, an anycast next-hop address855, and/or a BGP endpoint identifier860. The route identifier822is similar to522.FIG.8Fillustrates LFIB label information1502, similar to that shown inFIG.5D.FIG.8Gillustrates label information1504, including unique anycast NH address812.

In some embodiments, the base label824and the index826may be combined into a single entry in each path information820-1,820-2,820-3,820-4, . . .820-N. For instance, the path information820-1,820-2,820-3,820-4, . . .820-N may each include a single entry in which the base label824is combined with the index826, resulting in a value of 116384. The router710in the data path, in some implementations, performs load-balancing or forwards the data packet(s) received from the IPE708using the LDP label838. In some embodiments, each instance of the path information820may include an identifier of one of the EPEs712. An example of such an identifier is the BGP endpoint860, which is tied with the unique next-hop addresses209discussed with respect toFIG.2. The EPE identifier is useable by the router710to identify with which of the EPEs712the particular instance of the path information820is associated. For instance, the path information820-1may include an identifier associated with the EPE712-1, the path information820-2may include an identifier associated with the EPE712-2, and the path information820-4may include an identifier associated with the EPE712-3. In some embodiments, the EPE identifier includes information specific to the individual EPE, such as a MAC address or a network segment identifier. The router710may use the EPE identifier to differentiate between the EPEs712.

FIG.8Ashows example network information832stored by an ingress provider edge (e.g., IPEs708) of a VRF system according to one or more embodiments.8A is derived from8E and8F. The network information832may include reachability information and/or routing information, as described herein. The network information832may be stored in one or more routing tables or forwarding tables, each routing or forwarding table storing information for sending encapsulated data packets through a particular routing instance. The network information832includes a plurality of sets of path information834-1,834-2,834-3,834-4. . .834-N each associated with a particular VRF instance or path through one of the IPEs708to one of the edge devices706.

Each set of the path information834includes a route836, an LDP label838, a base label840, an index842, and an anycast NH address855, and an operation816. In the network information832, a single set of the path information834may correspond to a plurality of sets of the path information820stored by the routers710. The LDP labels838are generated according to the Label Distribution Protocol, as described herein. Each LDP label838corresponds to one of the anycast next-hop addresses855of an EPE712. The value of the LDP label distributed is outside the scope of this document but herein for brevity, on IPE anycast next-hop address855is chosen to be equidistant from the EPEs and will have the same value on the IPE. But depending on the deployment and protocols used, LDP label/LFIB could be same or different for the same anycast next-hop.

The IPEs708have a limited amount of storage locations for storing path information. For instance, in some implementations of a VRF system, an IPE would perform load-balancing operations to select a path among a plurality of paths of a route through the VRF system. The IPE, which may have sufficient memory space to store information for ˜N sets of ECMPs information, would store an instance of path information in memory for each path that includes an EPE. As a result, the amount of occupied memory of the IPE is proportional to the number of EPEs/VRFs of the VRF system if the EPEs are advertising a label per routing-instance/VRF.

By way of contrast, the IPE708stores a set of path information for each ECMP route through the VRF system702. As shown in the network information832ofFIG.8A, the VRF instance having a route836value of 9100 is associated with two paths—a first path for the path information820-1and a second path for the path information820-2of network information892. However, the IPE708stores a single set of path information820-1for the routing instance having the route836value of 9100. Advantageously, the amount of memory of the IPE708occupied to store routing information is significantly reduced relative to other VRF solutions in which IPEs may store an instance of path information for each path through an EPE. Hence ECMP resources will not be consumed for the overlay routes on the peer IPEs.

Operation of the VRF system702will now be described with reference toFIGS.8A-8G. The edge device704sends, to the VRF system702, a first data packet718addressed to the edge device706-1. The IPE708-1receives the first data packet718and determines, based on the destination address in the first data packet718and the routing information709-1, that the first data packet718should be encapsulated using the path information834-1. More specifically, the IPE708-1encapsulates the first data packet718with an MPLS frame that includes an overlay label having a value116384corresponding to the base label840and index842in the path information834-1. The IPE708-1also encapsulates the first data packet718with an underlay label having a value132768(corresponding to the LDP label838in the path information834-1).

The IPE708-1sends an encapsulated data packet722having the MPLS frame, which is received by the router710-1. The router710-1identifies the EPEs712-1and712-2as candidates for receiving the data packet722based on a match between the underlay label value132768of the data packet722and an LDP label420-B of Label information1502. Selection of one of the EPE712-1and the EPE712-2involves performance of an ECMP load-balancing technique, which is outside the scope of this document. For instance, the router710-1may select a hash key from among a plurality of stored hash keys and perform a hash function using the selected hash key to obtain a hash value. In this particular example, the router710-1selects the EPE712-1based on the resulting hash value. The router710-1removes the underlay of the data packet722based on the routing information714-1and forwards an encapsulated data packet726to the EPE712-1. The data packet726has an overlay label value of 116384 corresponding to the overlay label value of the data packet722.

The EPE712-1receives the data packet726and references routing information stored in the memory of the EPE712-1to determine how to process the data packet726. The routing information stored by the EPE712-1includes at least some of the information in the network information804of VRF Label Information1510. EPE712-1will route the packets as per816of VRF Label Information1510based on overlay label810. The group information804and hence network information818will be used in the event that there is a disruption in a connection which would bring the BGP/IGP down, such as between EPE712and edge device106.

The edge device705also sends, to the VRF system702, a second data packet720addressed to the edge device706-3. The IPE708-2receives the second data packet720and determines, based on the destination address in the second data packet720and the routing information709-2, a data structure (e.g., a Forwarding Equivalence Class table), that the data packet should be encapsulated using the path information834-2. The IPE708-2encapsulates the second data packet720with an MPLS frame that includes an overlay label having a value116419corresponding to the base label840and index842in the path information834-3. The IPE708-2also encapsulates the second data packet720with an underlay label having a value144902(corresponding to the LDP label838in the path information834-3).

The IPE708-2sends an encapsulated data packet724having the MPLS frame, which is received by the router710-2. The router710-2identifies the EPEs712-2and712-3as candidates for receiving the data packet724based on a match between the underlay label value144902of the data packet and the LDP labels420-B of label information1502. The router710-2selects the EPE712-2based on a result of an ECMP load-balancing technique, as described herein. The router710-2removes the underlay of the data packet724and forwards an encapsulated data packet728to the EPE712-2. The data packet728has an overlay label value of 116419.

The EPE712-2receives the data packet728and references routing information stored in the memory of the EPE712-2to determine how to process the data packet728. The routing information stored by the EPE712-2includes at least some of the information in the network information similar to VRF label information1510but with a different anycast label 116419 associated with routing instance VFR_B described above with reference to the routing information stored by the EPE712-1.

In this example, however, the EPE712-2may detect a network disruption in a connection between the EPE712-2and the edge device706-3. As a result of detecting the disruption, the EPE712-2references the routing information to identify another EPE in the group associated with the underlay label value of 116419 or the unique next-hop address 33.34.36.2. For instance, as shown in the network information802-2, and hence820-4, the EPE712-2determines that the EPE712-3is included in a group associated with the label having the value116419. The EPE712-2sends the data packet728to the EPE712-3, which references routing information stored in its memory. With reference toFIG.8D, based on a match between the label value116419, followed by using820-4the network information818and route it towards706-3in routing instance VRF_B. EPE712-3removes the overlay or service label and sends an unencapsulated data packet732to the edge device706-3based on overlay label 116419 as per overlay label810of VRF Label information1510. The data packet732includes a header and a payload that matches the second data packet720sent by the edge device704.

The foregoing techniques involve generating, by a collection of EPEs, an anycast next hop identifier and an anycast MPLS identifier. The EPEs advertise the next hop identifier and the MPLS identifier to other network devices of a VRF system to facilitate a set of routing instances of a VRF system. The IPEs and routers of the VRF system use the anycast next hop identifier and the anycast MPLS identifier to implement a set of routing instances that comprise a plurality of MPLS network segments. Along with this, unique NHs with an anycast label would be advertised by the EPEs with other members of the EPE group with the IBGP mesh created between the group of EPEs to handle the network disruptions but with the same base label210/806, and the index212/808. This path will become active depending on the BGP best path algorithm (or when used as backup path) during link or node disruptions which would bring down BGP/IGP between EPE and an edge device. As a result of the features described herein, a VRF system may handle disruptions involving egress provider edges with improved efficiency. More particularly, VRF system entities (e.g., ingress provider edges, routers) do not incur a significant increase in ECMP software and/or hardware computing resources and packet losses are substantially reduced as a result of experiencing a disruption involving network segments that include the EPEs.

FIG.9illustrates a network topology900that includes a plurality of VRF systems according to one or more embodiments. The network topology900includes a VRF system902configured to provision a routing instance for mediating communications between external edge devices904and906, as described herein. The network topology900also includes a VRF system908configured to mediate communications between the VRF system902and an external edge device910. The external edge devices904,906and910belong to the same customer. Various features of the network topology900are substantially similar to other network topologies described herein, so further description of such features is omitted for brevity including the IBGP mesh formed between EPEs with unique next-hops to handle various network and device disruptions. In this case IBGP mesh would be formed between ASBRs belong to the same AS to handle such network and device disruptions.

The VRF system902is separate from the VRF system908. The VRF system902may be operated a first entity different from a second entity operating the VRF system908. The first and second entities are separate entities that may provide one or more services, such as network services, internet service, and cloud or web-based services, by way of non-limiting example. The VRF system902operates on a different set of hardware and/or software than the VRF system908and may be located in a different building, campus, region, or country than the VRF system908. In some embodiments, the hardware and/or software of the VRF systems902and908are isolated from each other except to convey communications between the edge device910and the edge device904and/or the edge device906. For instance, the VRF system902may operate using a first set of administrative servers whereas the VRF system908operates using a second set of administrative servers different from the first set of administrative servers.

The VRF system902comprises an ingress provider edge912, a router914, and egress provider edges916-1,916-2, and916-3, as described herein. The VRF system902also includes gateway devices918-1and918-2for interfacing with gateway devices of other VRF systems, such as the VRF system908. The VRF system908comprises gateway devices920-1and920-2, a router922, and an egress provider edge device924. Non-limiting examples of the router914and the router922include label switching routers, route reflectors, or other similar devices operating as intermediary nodes between edge devices (e.g., between IPE912and EPEs916) or between gateway devices and provider edge devices (e.g., between IPE912and gateway devices918, between gateway devices920and EPE924). Non-limiting examples of the gateway devices include asynchronous system border routers (ASBRs) and/or area border routers (ABRs). In some embodiments, the VRF system908may include a plurality of EPEs924that operate as described with respect toFIGS.2,3,4, and elsewhere herein.

Network connections926-1,926-2,926-3, and926-4are established between the VRF systems902and908. A network connection926-1is established between the gateway918-1and the gateway920-1, a network connection926-2is established between the gateway918-2and the gateway920-2, a network connection926-3is established between the gateway918-1and the gateway920-2, and a network connection926-4is established between the gateway918-2and the gateway920-1. The network connections926-1,926-2,926-3, and926-4are, in some embodiments, network tunnels established using MPLS techniques, such as a Resource Reservation Protocol for Traffic Engineering (RSVP-TE) protocol or a Multiprotocol External BGP (MP-EBGP) protocol. As a particular non-limiting example, one or both of the network connections926-1,926-2,926-3and/or926-4may be VPN tunnels. The gateway devices918and/or920are network devices, such as border routers (e.g., area boundary routers, autonomous system border routers). In some embodiments, the VRF system902and/or908may include more than two gateway devices for communications with other VRF systems. In an embodiment, a solution is provided to solve Inter-AS Option-B. As explained above, an Inter-AS Option-A and Option-C can be addressed with the embodiments discussed above. ASBRs will have a base label and a range per unique NH address present in the vpn-ipv4/v6 BGP advertisement. Only range needs to be provisioned thru cli or any means on ASBRs. So ASBRs will just swap the base labels from EPEs to ASBRs and vice-versa based on the NH. Index will remain the same. ASBRs will receive BGP VPN-ipv4/v6 network information from EPEs and peer AS ASBRs similar to as discussed with respect toFIG.5B. From this ASBRs, will generate a table such as shown inFIG.10AorFIG.10Band advertise the BGP VPN-ipv4/v6 prefixes to peer AS ASBRs by swapping the vpn-ipv4/v6 labels (from the base label allocated based on the peer AS along with the index) and changing the NH. In an embodiment, ASBRs will install the locally allocated MPLS label in the LFIB ASBRs.

The gateway devices918-1and918-2communicate with the router914to facilitate communications with the edge device910communicatively coupled with the VRF system908. The router914advertises the routing information provided by the gateway devices918-1and918-2to the IPE912. For instance, the router914may advertise the IPE912, a common anycast next hop address, and anycast Overlay/VRF/Service Label provided by ASBRs918-1and918-2which will forward the packets to ASBRs920-1and920-2which will eventually forward the packets to the edge device910.

In the VRF system908, the EPE924generates reachability information928for communications with the edge device910. The reachability information928may include an anycast next-hop address928-1corresponding to an anycast IP address of a group of EPEs associated to mediate communications to the external edge device910, as described with respect to the EPEs204ofFIG.2and elsewhere herein. The reachability information928also includes a base label928-2having a value of 220000 and an index928-3having a value of 551. The next-hop address928-1, the base label928-2, and the index928-3correspond to those described with respect toFIG.3and elsewhere herein. The next-hop address928-1, the base label928-2, and the index928-3may be specific to and cooperatively determined among one or more other EPEs of the VRF system908and generates network information928similar to shown inFIG.5Band advertises the same to router922.

The EPE924advertises the reachability information928to the router922. The router922advertises at least some of the reachability information928to the gateways920-1and920-2. The gateways920-1and920-2generate the routing information930.

In some embodiments, the label 260551 is a combination of a base label common to the gateways920-1and920-2and an index value specific to a peer VRF instance neighbor of the peer VRF system902, as described with respect to the index212ofFIG.2and elsewhere herein. For instance, the routing information930may include, for instance, an anycast next-hop address930-1, a base label930-2specific to the group of gateways920, and an index930-3corresponding to the NH928-1advertised by EPE-924. The reachability information stored and advertised by the gateways920may include an address of the930-1associated with itself (920), the base label930-2, and the index930-3. The actual label (260551) stored in LFIB as shown inFIG.10Dwill be930-2(Allocated Base Label)+930-3(Index).

The gateways918-1and918-2determine a set of network information for mediating communications between the VRF system902and the VRF system908. The gateway devices918-1and918-2generate reachability information, as described with respect toFIGS.2,3, and elsewhere herein. At least some of the reachability information may be stored in routing information932in memory of the gateways918. The routing information932may include, for instance, an anycast next-hop address932-1, a base label932-2specific to the group of gateways918, and an index932-3corresponding to the NH advertised by neighbor associated with the VRF system908. The reachability information stored and advertised by the gateways918may include an address of the932-1associated with itself (918), the base label932-2, and the index932-3. The actual label (240551) stored in LFIB as shown inFIG.10Ewill be932-2(Allocated Base Label)+932-3(Index). The routing information930and/or the routing information932may include features and/or a format described with respect to the reachability information206and/or802respectively described with respect toFIGS.2and8.

The router914generates and stores routing information as described with respect to the network information518and/or818respectively described with respect toFIG.5B or8B. The router914advertises at least some of the information included in the routing information932to the IPE912. The IPE912generates and stores routing information as described with respect to the network information502and/or832respectively described with respect toFIG.5A or8Abased onFIG.5B or8Eit received.

Similarly, EPEs916or IPE912(which in this case will act as another EPE) would advertise prefixes to918thru router914which will reach920and then router922followed by EPE924. All the operations described above will happen in the reverse direction as well if bi-directional communication is desired.

In operation of the network topology900, the external edge device904may send a data packet934to the VRF system902. The data packet934may be addressed to the external edge device910and received by the IPE912. The IPE912references its routing information and encapsulates the data packet934to generate an encapsulated data packet936. The encapsulated data packet936includes a first overlay corresponding to a combination of the base label932-2and the index932-3and includes a first underlay corresponding to an LDP label, as described with respect toFIGS.4through5Band elsewhere herein. The IPE912sends the data packet936to the router914. The router914removes the first underlay of the data packet936to reveal the first overlay and performs an ECMP load-balancing technique to select one of the gateways918-1and918-2to which to send the data packet.

An issue that may arise with respect to the network topology900is that network traffic through one of the gateways918may be disrupted. Consider, for example, a situation in which the router914determines that a network connection938with the gateway918-2is unavailable. In previous implementations, it would be difficult for the router914to effectuate delivery of the data packet to the VRF system908under such conditions. However, in the network topology900, the router914would determine that another path is available to the VRF system908via the gateway918-1. The router914would direct an encapsulated data packet940having the first overlay label.

A further potential issue that may arise with respect to the network topology900is that one of the network connections926-1,926-2,926-3, and926-4between gateways918and920may be disrupted. For instance, the gateway918-1may receive the data packet940and determine, based on the first overlay label, that the data packet940should be processed and sent to the gateway920-1. The gateway918-1, however, may detect that the network connection926-1with the gateway920-1is unavailable or otherwise disrupted. In response to detecting the disruption of the network connection926-1, the gateway918-1references routing information to determine how to proceed. In some embodiments, the gateway918-1then sends packet940from gateway to gateway920-2as described below.

FIG.10Aillustrates example network information1002stored in memory of a gateway device, such as the gateway devices918-1and918-2, according to one or more embodiments. This is advertised to IPE912. The network information1002may include reachability information and/or routing information, as described herein. More particularly, the network information1002includes one or more sets of path information1004-1,1004-2, . . .1004-N regarding paths through the VRF system902. The sets of path information1004may include group information1006identifying a group of associated gateways918of the VRF system902operating in cooperation to route data packets to gateway devices of other VRF systems. Group information1006is similar to group information804described earlier.

The network information1002includes a base label1008, an index1010, and an anycast next-hop IP address1012collectively generated by the gateways918. The base label1008, the index1010, and the next-hop address1012may be generated in response to receiving network information1050from the gateways920. The network information1002includes the Route ID and an MPLS label240551(Derived from1008+1010) that's allocated locally on gateways918after receiving network information1050from the gateways920in connection with the Route ID. The network information1002may further include or indicate an operation1018to be performed for data packets received having an overlay label corresponding to a combination of the base label1008and the index1010as it generates label information1070.

Referring back toFIG.9, the gateway918-2compares the overlay or service label (240551) of the data packet940to the sets of label information1021-1of the label information1070ofFIG.10Ederived from network information1002ofFIG.10Aand network information1020ofFIG.10C. The gateway918-2identifies a match between the overlay label of the data packet940and the label information1021-1of the label information1070. Based on the match, the gateway918-2determines that the data packet940should be processed and sent to the gateway920-2. The gateway device918-2performs a SWAP operation based on the operation1034indicated to swap the overlay of the data packet940with the label (260551) in the label information1070. The gateway device918-2sends a resulting encapsulated data packet942to the gateway device920-2of the VRF system908.

The gateway920-2receives the data packet942and compares the overlay label of the data packet942to routing information stored in memory of the gateway920-2.FIG.10Billustrates example network information1020stored in memory of a gateway device, such as the gateway devices920-1and920-2, according to one or more embodiments. The network information1020may include reachability information and/or routing information, as described herein. The network information1020, more particularly, includes one or more sets of path information1021-1,1021-2, . . .1021-N regarding paths through the VRF system908.

The sets of path information1021may include group information1022identifying a group of associated gateways920of the VRF system908operating in cooperation to receive data packets from gateway devices of other VRF systems and route the data packets received through an appropriate path of the VRF system908. The path information1021includes a base label1024, an index1026, and an anycast next-hop IP address1028advertised by the EPE924for routing data packets through the VRF system908to the edge device910. The path information1021of network information1050may include an MPLS label 260000 (Derived from1025+1026) advertised by the gateways920to gateways of other VRF systems, such as the gateways918. Gateways920after receiving10B from EPE924, generates10C and10D.10C is advertised to gateways918and labels as per10D is installed locally on gateways920with the operation/action of swapping the overlay label from260551to220551and add an LDP label to reach the EPE924based on anycast NH address 10.10.10.1 as required. The same is mentioned in1034of10D.

Referring back toFIG.9, the gateway920-2compares the overlay or service label of the data packet942to the sets of label information1021-1of the label information1060ofFIG.10Dwhich is generated after receiving1021-1ofFIG.10Bfrom EPE-924. The gateway920-2identifies a match between the overlay label (260551) of the data packet942and the value (260551) of the label1035in the set of path information1021-1as inFIG.10D. Based on the match, the gateway920-2that the data packet942should be sent to the router922. More particularly, the gateway device920-2performs a SWAP operation specified in1034, which involves swapping the overlay label with a label corresponding to a combination of the base label1024and the index1026(e.g., a label having a value of 220551 as per10D which is derived fromFIG.10B). The gateway device920-1also performs a PUSH operation specified in1034, which involves applying the LDP label1032in the path information1021-1as an underlay label of the data packet946(e.g., a label having a value of 230195). The gateway920-1sends the encapsulated data packet946to the router922.

The router922references routing information stored in its memory, as described with respect toFIGS.4and7, and pops the underlay (having the value 230195, let's say) of the data packet946to reveal the overlay label having the value 220551. The router922sends the data packet948having the overlay label to the EPE924based on the routing information. The EPE924receives the data packet948, references routing information stored in its memory, and pops the overlay label of the data packet948based on the routing information, as described with respect toFIGS.4,7, and elsewhere herein. The EPE924sends a resulting data packet950having a destination address matching an address910-1to the edge device910.

Advantageously, the features described herein improve the robustness of a VRF system against the disruption of network connections, both internal to the VRF system and external to the VRF system. The VRF system also reduces the impact of network disruptions to an ingress provider edge device by providing a common label and a common next hop address for the egress provider edge devices. When an egress provider edge node experiences an outage, for example, the routing instance identified in routing information of an ingress provider edge does not change, which improves convergence. With respect to gateway nodes between VRF systems of different entities, classifications for equal cost multi-path determinations are also reduced on importing border routing information. Furthermore, the label ranges for border devices, such as the gateways918, can be configured by BGP peers, which improves scalability of a VRF system.

It is understood that the various embodiments described herein may be combined with other embodiments to achieve new embodiments. For example, the features of the network topology900may be combined with the features described with respect to the network topology700to realize benefits of both topologies. The network topologies described herein may be expanded to include a greater number of egress provider edges than three. Moreover, a VRF system described herein may include different sets of EPEs for implementing different routing instances. In a rare event wherein an ASBR is completely disconnected from all the devices of its local AS, it can bring down the link with the peer ASBRs which otherwise can blackhole the traffic.

FIG.11illustrates a network device1100that is adapted to operate according to one or more embodiments of the present disclosure. The network device1100may be a switch or a router, for example. As shown, network device1100can include a management module1112, an internal fabric module1104, and a number of I/O modules1106a-1106p. The management module1112may be disposed of in a control plane (also referred to as control layer) of the network device1100and can include one or more management CPUs1108for managing and controlling operation of network device1100in accordance with the present disclosure. Each management CPU1108can be a general-purpose processor, such as an Intel®/AMD® x86-64 or ARM® processor, that operates under the control of software stored in memory, such as a storage subsystem1120and memory subsystem1122, which may include read-only memory1128and/or random-access memory1126, and/or file storage subsystem1127. In some embodiments, the CPU1108may include control circuitry, and may include or be coupled to a non-transitory storage medium storing encoded instructions that cause the CPU1108to perform operations described herein. In some embodiments, the non-transitory storage medium may include encoded logic or hardwired logic for controlling operation of the CPU1108. The control plane refers to all the functions and processes that determine which path to use, such as routing protocols, spanning tree, and the like. Each network device1100can include multiple elements that may be electrically coupled via a bus1130.

Internal fabric module1104and I/O modules1106a-1106pcollectively represent the data plane of network device1100(also referred to as data layer, forwarding plane, etc.). Internal fabric module1104is configured to interconnect the various other modules of network device1100. Each I/O module1106a-1106pincludes one or more input/output ports1110a-1110pthat are used by network device1100to send and receive network packets. Each I/O module1106a-1106pcan also include a packet processor1112a-1112p. Each packet processor1112a-1112pcan comprise a forwarding hardware component configured to make wire speed decisions on how to handle incoming (ingress) and outgoing (egress) network packets. In some embodiments, the forwarding hardware can comprise an application specific integrated circuit (ASIC), a field programmable array (FPGA), a digital processing unit, or other such collection of configured logic.

Further Embodiments

In some aspects, the techniques described herein relate to a method including: receiving, by a first egress edge device of a Virtual Routing and Forwarding (VRF) system, an advertisement that includes a first identifier of a first external device external to the VRF system; communicating with a second egress edge device of the VRF system to determine a first base label value and a first index value, the first base label value being common to the first egress edge device and the second egress edge device, and the first index value being specific to the first external device; advertising, by the first egress edge device, the first identifier and the first base label value to one or more devices in the VRF system; receiving, by the first egress edge device, a first data packet encapsulated according to a Multi-Protocol Label Switching (MPLS) protocol; determining a first match between a first overlay label of the first data packet and a second label value corresponding to a combination of the first base label value and the first index value; performing a first set of operations to modify the first overlay label based on the first match; and sending the first data packet to the first external device.

In some aspects, the techniques described herein relate to a method, further including: communicating with the second egress edge device to determine a first anycast next-hop address common to the first egress edge device and the second egress edge device; and advertising the first anycast next-hop address to the one or more devices in the VRF system.

In some aspects, the techniques described herein relate to a method, further including: receiving, by the first egress edge device, a second data packet encapsulated according to the MPLS protocol; determining that a second overlay label of the second data packet matches the second label value; detecting a network disruption between the first egress edge device and the first external device; and in response to detecting the network disruption, sending the second data packet to the second egress edge device.

In some aspects, the techniques described herein relate to a method, further including: receiving, by the first egress edge device, a second data packet from the second egress edge device, the second data packet including a second overlay label; determining a second match between the second overlay label and the second label value; performing, as a result of determining the second match, the first set of operations further including: modifying the second overlay label based on the second match; and sending the second data packet to the first external device.

In some aspects, the techniques described herein relate to a method, wherein performing the first set of operations further includes removing the first overlay label.

In some aspects, the techniques described herein relate to a method, wherein performing the first set of operations further includes swapping the first overlay label with the first identifier.

In some aspects, the techniques described herein relate to a method, further including: receiving, by the first egress edge device, an advertisement that includes a second identifier of a second external device external to the VRF system; communicating with the second egress edge device to determine a second index value specific to the second external device; advertising the second index value to the one or more devices in the VRF system; receiving, by the first egress edge device, a second data packet encapsulated according to the MPLS protocol; determining a second match between a second overlay label of the second data packet and a third label value corresponding to a combination of the first base label value and the second index value; performing a second set of operations modifying the second overlay label based on the second match; and sending the second data packet to the second external device.

In some aspects, the techniques described herein relate to a first network device including: at least one memory; one or more network interfaces; and one or more processors configured to perform operations causing the first network device to: communicate with a second network device of a first Virtual Routing and Forwarding (VRF) system to determine a first base label value and a first index value, the first base label value being common between the first network device and the second network device, and the first index value being specific to a first external device external to the first VRF system; update routing information stored in the at least one memory to include a first set of path information associating the first base label value and the first index value with a first identifier of the first external device and with a second identifier of the second network device; receive a first data packet having a first overlay label; and send the first data packet to the first external device based on a first match between the first overlay label and a second label value corresponding to a combination of the first base label value and the first index value.

In some aspects, the techniques described herein relate to a first network device, wherein the one or more processors are further configured to perform operations causing the first network device to: communicate with a third network device of the first VRF system to determine a second base label value and a second index value, the second base label value being common between the first network device and the third network device, and the second index value being specific to a second external device external to the first VRF system; update the routing information to include a second set of path information associating the second label value and the second index value with a third identifier of the second external device and a fourth identifier of the third network device; receive a second data packet having a second overlay label; and send the second data packet to the second external device based on a second match between the second overlay label and a third label value corresponding to a combination of the first base label value and the second index value.

In some aspects, the techniques described herein relate to a first network device, wherein the first external device is a gateway device of a second VRF system, the first identifier is a label advertised by the gateway device, and the one or more processors are configured to replace the first overlay label with the first identifier as a result of the first match.

In some aspects, the techniques described herein relate to a first network device, wherein the first external device is a customer edge device, the first identifier is an address of the first external device, and the one or more processors are configured to remove the first overlay label as a result of the first match.

In some aspects, the techniques described herein relate to a first network device, wherein the one or more processors are further configured to store routing information in the at least one memory and to perform operations causing the first network device to: communicate with the second network device to determine a second index value specific to a second external device external to the first VRF system; update the routing information to include a second set of path information associating the first base label value and the second index value with the second identifier and with a third identifier of the second external device; receive a second data packet having a second overlay label; and send the second data packet to the second external device based on a second match between the second overlay label and a third label value corresponding to a combination of the first base label value and the second index value.

In some aspects, the techniques described herein relate to a first network device, wherein the one or more processors are further configured to perform operations causing the first network device to: receive a second data packet from a router of the first VRF system; determine a second match between a second overlay label of the second data packet and a third label value in the first set of path information; detect a disruption in a network connection with the first external device; and in response to detecting the disruption, send the second data packet to the second network device.

In some aspects, the techniques described herein relate to a first network device, wherein the one or more processors are further configured to perform operations causing the first network device to: receive, from the second network device, a second data packet that includes a second overlay label; determine a second match between a second overlay label of the second data packet and the second label value; remove, as a result of the second match, the second overlay label; and send the second data packet to the first external device.

In some aspects, the techniques described herein relate to a method including: receiving, by a first network device of a first Virtual Routing and Forwarding (VRF) system, first reachability information including a first address of a first edge device external to the first VRF system, a first base label associated with a first set of egress edge devices of the first VRF system, and a first index associated with the first set of egress edge devices; broadcasting an advertisement including the first address and a first label value generated according to a defined communication protocol; receiving, from a gateway device of a second VRF system, a first data packet including a first label; generating a modified data packet by at least replacing the first label with a second label corresponding to a combination of the first base label and the first index; and sending the modified data packet to a second network device in the first VRF system based on a match between a value of the first label and the first label value.

In some aspects, the techniques described herein relate to a method, wherein generating the modified data packet includes applying a third label to the first data packet, the defined communication protocol is a Border Gateway Protocol, the third label is generated according to a Label Switching Protocol, and the second network device is a Label Switched Router.

In some aspects, the techniques described herein relate to a method, including: receiving, from the gateway device of the second VRF system, a second data packet including the first label; detecting a network disruption between the first network device and the second network device; and sending the second packet to a third network device of the first VRF system as a result of detecting the network disruption.

In some aspects, the techniques described herein relate to a method, wherein the first network device is a gateway device of the first VRF system and the second network device is a Label Switching Router of the first VRF system.

In some aspects, the techniques described herein relate to a method, including: receiving, by the first network device, an anycast next-hop address corresponding to a set of egress edge devices of the first VRF system.

In some aspects, the techniques described herein relate to a method, including: updating routing information stored in a memory of the first network device to include a set of path information including group information in which the first network device and a third network device of the first VRF system are identified as belonging to a same network device group.

Operations of processes described herein can be performed in any suitable order unless otherwise indicated herein or otherwise clearly contradicted by context. Processes described herein (or variations and/or combinations thereof) may be performed under the control of one or more computer systems configured with executable instructions and may be implemented as code (e.g., executable instructions, one or more computer programs or one or more applications) executing collectively on one or more processors, by hardware or combinations thereof. The code may be stored on a computer-readable storage medium, for example, in the form of a computer program comprising a plurality of instructions executable by one or more processors. The computer-readable storage medium may be non-transitory. In some embodiments, the code is stored on set of one or more non-transitory computer-readable storage media having stored thereon executable instructions that, when executed (i.e., as a result of being executed) by one or more processors of a computer system, cause the computer system to perform operations described herein. The set of non-transitory computer-readable storage media may comprise multiple non-transitory computer-readable storage media and one or more of individual non-transitory storage media of the multiple non-transitory computer-readable storage media may lack all of the code while the multiple non-transitory computer-readable storage media collectively store all of the code. Further, in some examples, the executable instructions are executed such that different instructions are executed by different processors. As an illustrative example, a non-transitory computer-readable storage medium may store instructions. A main CPU may execute some of the instructions and a graphics processor unit may execute other of the instructions. Generally, different components of a computer system may have separate processors and different processors may execute different subsets of the instructions.

Accordingly, in some examples, computer systems are configured to implement one or more services that singly or collectively perform operations of processes described herein. Such computer systems may, for instance, be configured with applicable hardware and/or software that enable the performance of the operations. Further, computer systems that implement various embodiments of the present disclosure may, in some examples, be single devices and, in other examples, be distributed computer systems comprising multiple devices that operate differently such that the distributed computer system performs the operations described herein and such that a single device may not perform all operations.