TECHNICAL FIELD

The disclosure relates to computer networking.

BACKGROUND

A computer network is a collection of interconnected computing devices that exchange data and share resources. In a packet-based network, such as the Internet, the computing devices communicate data by dividing the data into small blocks called packets. The packets are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.

A private network may include a number of devices, such as computers, owned or administered by a single enterprise. These devices may be grouped into a number of site networks, which in turn may be geographically distributed over a wide area. Each site network may include one or more local area networks (LANs). With the advent of Virtual Private Network (VPN) technology, enterprises can now securely share data between site networks over a public network, such as the Internet. In a typical implementation, one or more “network tunnels” are engineered through a backbone network to transport data and other network communications between the geographically distributed sites.

One form of a VPN is generally referred to as “MPLS VPN” in which Multi-Protocol Label Switching (MPLS) tunnels are used as a transport mechanism. MPLS is a mechanism used to engineer traffic patterns within Internet Protocol (IP) networks. By utilizing MPLS, a source device can request a path through a network to a destination device, i.e., a Label Switched Path (LSP), to carry MPLS packets from the source device to a destination device. Each router along an LSP assigns a label and propagates the label to the closest upstream router along the path for use in forwarding MPLS packets along the path. Routers along the path cooperatively perform MPLS operations to forward the MPLS packets along the established path.

A BGP/MPLS VPN combines the tunneling features of MPLS with virtual routing and forwarding (VRF) and features of border gateway protocol (BGP) to create a VPN. When a VPN is established within a network, devices for the VPN each include VPN-specific VRF tables that are identifiable by a service label known as a VPN route label, which is distinct from transport or infrastructure labels for LSP tunneling. Both service labels and infrastructure labels may be types of MPLS labels. When BGP distributes a VPN route, it also distributes a MPLS label for that route, which for BGP/MPLS VPNs is also known as a VPN route label. Before a data packet for a VPN travels across the backbone, it is encapsulated with the VPN route label that corresponds, in the VPN, to the route that is the best match to the packet's destination address. This labeled packet is further encapsulated (e.g., with another MPLS label or with an IP or Generic Routing Encapsulation (GRE) tunnel header for tunneling across the backbone to the proper PE router). Thus, the backbone core routers do not need to know the VPN routes.

Further details regarding VPNs, specifically VPNs implemented using BGP and MPLS are discussed in E. Rosen and Y. Rekhter, “BGP/MPLS IP Virtual Private Networks (VPNs),” RFC 4364, February 2006, the entire contents of which being incorporated by reference in its entirety. Other network protocols that rely on BGP-advertised labels include BGP Labeled Unicast (BGP-LU), Ethernet VPN (EVPN), and some other forms of Layer 3 VPNs (L3VPNs).

SUMMARY

In general, the disclosure describes techniques performed by a network device for distributed label assignment for labeled routes. A network device may execute multiple threads on one or more processing cores to prepare labeled routes for advertising in route advertisements, such as Border Gateway Protocol (BGP) UPDATE messages. Preparation of a labeled route includes allocating a label from the label space. To accomplish such label allocation, the threads implement a concurrency model in which the performance of the label allocation approaches that of a centralized label allocation.

In one example, labels (e.g., service labels or infrastructure labels) are assigned among the threads such that each thread manages a local label pool that is a unique subset of the labels. That is, none of the labels in the local label pool for a thread overlaps with labels of a local label pool managed by a different thread. Each thread uses its local label pool for label assignments, and labels released by a thread are released to its local label pool. In addition, a thread pre-fetches batches of labels from the global label pool to its local label pool to avoid initial fetching latency and releases batches of labels to the global label pool in accordance with thresholds (or “watermarks”) to reduce, and in some cases minimize, inter-thread communications regarding label allocation and release. Each thread may then assign labels from its local label pool to include with routes for advertising, by the network device, labeled routes using a routing protocol, e.g., BGP. Network devices that received labeled routes may subsequently direct network packets labeled with the label to the network device, which the network device uses to identify a service with which to process the network packets. Such services may include MPLS VPNs, such as MPLS/BGP VPNs, BGP-LU services, or EVPNs, for example.

The techniques may provide one or more technical improvements or benefits that provide at least one practical application. In general, slow label allocation can cause delays in generating and outputting route advertisements and attendant deleterious effects to network packet forwarding. Previous attempts to avoid label conflicts among multiple threads rely heavily upon exchanging messages with inter-thread/inter-process communications to avoid label conflicts, often in a request/response mode between worker threads and a central thread responsible for managing label allocation, which is performed on a per-label basis. Because inter-thread messages involve latencies and processor (e.g., CPU) costs, centrally-managed per-label allocation may become very expensive and cause significant performance penalties. In other systems, mutex locks can be used to allocated labels from a central thread.

Threads operating according to techniques described herein implement a concurrency model in which coordination among the threads is relatively infrequent and batchwise, and each thread has a separate local label pool from which to draw for low-latency label assignment. Moreover, the threads can pre-fetch batches of labels according to the thresholds. This reduces inter-thread messaging and may cause the label assignment failure rate (i.e., a thread being unable to assign a label from its local label pool) to approach zero. The efficiencies may reduce the average overall latency for labeled route generation and advertising by network devices and may result in attendant improvements in network packet forwarding.

In one example, a method includes obtaining, by a first thread of a plurality of execution threads for at least one routing protocol process executing on processing circuitry of a network device, an allocation of first labels drawn from a label space for a network service; adding, by the first thread, the first labels to a first local label pool for the first thread; generating, by the first thread, after obtaining the allocation of the first labels, a labeled route comprising a route for the network service and a label assigned by the first thread from the first local label pool; and outputting, by the network device, the labeled route.

In another example, a network device includes at least one hardware-based processor for executing a first thread of a plurality of execution threads for at least one routing protocol process executing on processing circuitry of the network device, the at least one hardware-based processor configured to: obtain, by the first thread of a plurality of execution threads for at least one routing protocol process executing on processing circuitry of the network device, an allocation of first labels drawn from a label space for a network service; add, by the first thread, the first labels to a first local label pool for the first thread; generate, by the first thread, after obtaining the allocation of the first labels, a labeled route comprising a route for the network service and a label assigned by the first thread from the first local label pool; and output, by the network device, the labeled route

In another example, a computer-readable medium comprising instructions for causing one or more programmable processors of a network device to: obtain, by the first thread of a plurality of execution threads for at least one routing protocol process executing on processing circuitry of the network device, an allocation of first labels drawn from a label space for a network service; add, by the first thread, the first labels to a first local label pool for the first thread; generate, by the first thread, after obtaining the allocation of the first labels, a labeled route comprising a route for the network service and a label assigned by the first thread from the first local label pool; and output, by the network device, the labeled route.

The details of one or more examples are set forth in the accompanying drawings and the description below. Other features, objects, and advantages will be apparent from the description and drawings, and from the claims.

