Juniper Networks, Inc.

International Business Machines Corporation

Telefonaktiebolaget Lm Ericsson (publ)

Sanjay Khanna

Jaihari V Loganathan

Kevin F Wang

Ashutosh K Grewal

Jeffrey M Haas

Venugopalan Ullanatt

Stephen Nadas

Srinivas Ramprasad

Lori Ann Napoli

In general, various aspects of the techniques are described in this disclosure for distributed label assignment for labeled routes. 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.

Distributed label assignment for labeled routing protocol routes

A network device, associated with peer network devices, may receive policy information for a protocol; and compute a first update message based on information regarding a route associated with the policy information. The network device may determine that an upper utilization threshold for one or more of peer queues, associated with the peer network devices, is not satisfied; and write the first update message to the peer queues based on determining that the upper utilization threshold is not satisfied. The network device may compute a second update message based on the information regarding the route; determine that the upper utilization threshold for one or more of the peer queues is satisfied; and pause writing the second update message to the peer queues based on the upper utilization threshold being satisfied. The network device may permit the peer network devices to obtain data from corresponding ones of the peer queues.

Regulating enqueueing and dequeuing border gateway protocol (BGP) update messages

In some examples, a main thread of a plurality of execution threads executing on a plurality of processing cores of at least one hardware-based processor of a network device may receive a request for information associated with network routes that meet one or more criteria. Each of the plurality of execution threads may process a respective routing information partition to generate respective displayable information associated with a respective subset of the network routes that meets the one or more criteria. The main thread may generate consolidated displayable information associated with the network routes that meet the one or more criteria based on the respective displayable information generated by each of the plurality of execution threads. The main thread may output the consolidated displayable information associated with the network routes that meet the one or more criteria for display at a display device.

Multithreaded route processing for routing information display

In general, the disclosure describes techniques for lockless management of immutable objects by multi-threaded processes. A device comprising a processor may implement the techniques, where the processor execute a multi-threaded process including a producer thread and a consumer thread. The producer thread may instantiate an immutable object, and provide, to the consumer thread, a reference to the immutable object. The producer thread may also increment a reference counter to indicate that the reference has been provided to the consumer thread, where the reference counter is local to the producer thread and inaccessible to the at least two consumer threads. The producer thread may receive, from the consumer thread, a notification that the consumer thread has finished processing the immutable object, and decrement, responsive to receiving the notification, the reference counter. The producer thread may then delete, based on the reference counter, the immutable object.

Lockless management of immutable objects by multi-threaded processes using multiple counters

In general, the disclosure describes techniques for distributing processing of routes among multiple execution threads of a network device. In some examples, a method includes partitioning a routing information base (RIB) into a plurality of RIB partitions, assigning a route processing thread to each RIB partition, processing BGP routing protocol messages at each of the route processing threads, and receiving, at a BGP update thread serving a BGP peer group, from two or more of the route processing threads, route update information for routes to be advertised. The route update information includes a BGP route tuple having a network prefix value and a pointer to an outgoing attribute. The method further includes collecting, based on the BGP route tuples, route update information for routes having the same outgoing attribute and constructing a BGP update message from the collected route update information.

Border gateway protocol update packing for a distributed routing information base

A system for resolving next hops in a distributed manner includes a plurality of next hop resolution subsystems, each of the plurality of next hop resolution subsystems including (1) a next hop registry, (2) a partial-view tree storing a local instance of next hop resolution information, and (3) a full-view tree storing a local instance of next hop resolution information. The system (1) receives a request to resolve a next hop; (2) obtains a plurality of partial results using the partial-view trees of the next hop resolution subsystems; (3) select a best one of the plurality of partial results; and 4) replies to the request using the selected best one of the plurality of partial results. The full-view trees are updated such that their contents tend to converge.

Distributed next hop resolution

In general, the disclosure describes techniques for distributing processing of routes among multiple execution threads of a network device. In some examples, a method includes identifying, with a thread of a plurality of execution threads, a first route processing thread of the execution threads to process a first route of a routing protocol, the first route received by the network device; identifying, with the thread, a second route processing thread of the execution threads to process a second route of a routing protocol, the second route received by the network device; processing, by the first route processing thread executing on a first core of the plurality of processing cores, the first route; and processing, by the second route processing thread executing on a second core at least partially concurrently with the first route processing thread executing on the first core of the plurality of processing cores, the second route.

Multi-threaded route processing

A method and system are disclosed for distributing load in a network. A set of routers are configured for providing IP gateway services to a set of hosts where each router in the set of routers all back up all the other routers in the same set. Each router in the set utilizes identical load distribution policies, load distribution properties and load distribution arrangement. A Load Distribution Function (LDF) master router is determined for the set of routers, wherein each one of the set of routers is a backup for the LDF master router. Every router in the set of routers utilize the same algorithm to compute load distribution and the LDF master router provides balancing information to all the other routers by including that information in VRRP advertisement messages to all the routers.

System and method for balancing IP gateway services

The present invention provides a method, system, and computer program product for fast and efficient IP (Internet Protocol) address lookup. IP address values are interpreted using a separate array for each 8-bit component of the address. This technique is therefore exploitable in a multi-processing environment. The IP address look-up time when using the present invention is nearly constant, regardless of the particular address value. Minimal, if any, locking is required. This technique can be used equally well with class-specific IP version32-bit addresses and with Classless Inter-Domain Routing (CIDR), and easily extends to use with IP version128-bit addresses.

Technique for fast and efficient internet protocol (IP) address lookup

The present invention provides a method, system, and computer program product for reliably and efficiently serializing access to data structures (i.e. updates and retrievals) without requiring searchers to use locks. The disclosed technique ensures that the contents of the data structure remain valid during access operations, yet does not require searchers to perform compute-intensive comparison operations to determine validity. Two trees are used at all times. Searches proceed against a first tree, while the second tree is used for performing updates. The steps required to carry out a particular update operation are stored as a queued transaction. When the update to the second tree completes, the trees are switched. The queued transaction is applied to the now-out-of-date tree, such that the nodes of this tree do not need to be searched or otherwise evaluated in order to perform the update, thereby optimizing the process of bringing this tree into synchronization with the tree that is now being used by the searchers. The two trees are repeatedly switched as additional update operations are performed. Atomic operations are used to ensure proper synchronization between the search and update processing on the trees.

Technique for serializing data structure updates and retrievals without requiring searchers to use locks

Systems, methods, and computer program products facilitate establishing a TCP connection between a client and a server utilizing a control block associated with a previous connection between the client and the server wherein the previous connection is in TIME-WAIT state.

Growing community of inventors

Cary, NC, United States of America

Sanjay Khanna