Cisco Technology, Inc.

John H W Bettink

Clarence Filsfils

David Delano Ward

Pradosh Mohapatra

Ijsbrand Wijnands

Sami Boutros

Mohammed Ismael Tatar

William Norman Eatherton

Yuri Tsier

Paul Mattes

Jianyu Chen

Norbert Brotz

Muthurajah Sivabalan

Rami Zemach

Samir D Thoria

Luca Martini

Vitaly Sukonik

Stefano Benedetto Previdi

Rajiv Asati

Gregory J Shepherd

Pawan Uberoy

Akash Renukadas Deshpande

Michael E Lipman

David J Tsiang

Moshe Voloshin

Kannan Devarajan

Anbu Chezhian Gunalan

Rajagopalan M Ammanur

Prabhakara R Yellai

David R Oran

Stewart Frederick Bryant

George Swallow

Ian Michael Charles Shand

Michael Brian Galles

Donald Edward Steiss

Doron Shoham

Garry Paul Epps

John C Carney

Michael Laor

Christian J Martin

Shyamsundar Nandkishor Maniyar

Marvin Wayne Martinez, Jr

Christian Schmutzer

Palani Chinnakannan

Mark Warden Hervin

Shimon Listman

Pranav Dharwadkar

Dheerendra Talur

Parag Kumar Jain

David John Smith

Christopher Yates Satterlee

Ljsbrand Wijnands

Disclosed is the generation of a bit-indexed forwarding table (BIFT) that can include a plurality of entries, each such entry corresponding to a bit position of a plurality of bit positions, where each such bit position represents an egress network node of a plurality of egress network nodes, and the generating configures the BIFT to be used in forwarding a packet to one or more of the plurality of egress network nodes, based at least in part on a bit string in the packet. The generating includes selecting a bit position of the plurality of bit positions as a selected bit position, creating an entry of the plurality of entries (where the entry corresponds to the selected bit position), identifying a neighbor node associated with the selected bit position, and updating one or more fields of the entry with neighbor information regarding the neighbor node.

Bit indexed explicit forwarding optimization

Disclosed are systems and methods for generating a bit-indexed forwarding table (BIFT) that includes a plurality of entries, each of which corresponds to a bit position of a number of bit positions. Each such bit position represents an egress network node of a plurality of egress network nodes. The BIFT is generated from an existing BIFT that includes a number of existing BIFT entries. Further, the generating configures the BIFT to be used in forwarding a packet to one or more of the egress nodes, based at least in part on a bit string in the packet. In one embodiment, the generating includes selecting a bit position of the plurality of bit positions as a selected bit position, creating an entry of the plurality of entries, and converting an existing BIFT entry of the plurality of existing BIFT entries to the entry of the plurality of entries.

Various systems and methods for performing bit indexed explicit replication (BIER). For example, one method involves receiving a packet at a node. The packet includes a bit string. The node traverses the bit string and selects an entry in a bit indexed forwarding table (BIFT). The entry includes a forwarding bit mask. Based on the forwarding bit mask and the bit string, the node forwards the packet.

Bit indexed explicit replication forwarding optimization

In one embodiment, configurable policy-based processing of packets is performed, including, but not limited to, using user-configurable parameters to adjust control-plane allocation of resources used in processing of packets. In one embodiment, these resources include, but are not limited to, processing by fast path or slow path forwarding of packets; forwarding information base (FIB) entries, databases, and hardware processing elements; instantiation of sub-FIB databases; and/or selection of sub-FIB data plane entries for population of sub-FIB databases, a group of FIB entries is label switched traffic, fully expanded Internet Protocol routes, loopback addresses of packet switching devices in the network, label-switched to label-switched traffic, Internet Protocol (IP) to label-switched traffic, IP to IP traffic, and/or label to IP traffic. In one embodiment, a group of the plurality of different groups of FIB entries is defined upon how a route or label corresponding to a FIB entry was learned.

Adjusting control-plane allocation of packet processing resources

In one embodiment, an access component of a local network edge device receives traffic, and generates a frame for the traffic that includes a remote context label that identifies an access component of the remote network edge device to which the traffic is to be forwarded upon arrival at the remote network edge device, and a virtual circuit label corresponding to a particular virtual service of the traffic. The local network edge device forwards the frame towards the remote network edge device. In another embodiment, the frame may be received at a core component of the remote network edge device, an in response to the remote context label identifying an access component of the remote network edge device, forwarded to the access component, which determines the particular virtual service, and forwards the traffic from the frame out the access component towards an endpoint for the traffic.

Using context labels to scale MAC tables on computer network edge devices

In one embodiment, a packet switching device creates multiple virtual packet switching devices within the same physical packet switching device using virtual machines and sharing particular physical resources of the packet switching device. One embodiment uses this functionality to change the operating version (e.g., upgrade or downgrade) of the packet switching device by originally operating according to a first operating version, operating according to both a first and second operating version, and then ceasing operating according to the first operating version. Using such a technique, a packet switching device can be upgraded or downgraded while fully operating (e.g., without having to reboot line cards and route processing engines).

Virtual machines in a packet switching device

In one embodiment, individual or groups of heat generating data processing operations are rate-controlled such that a component, a set of components, a board or line card, and/or an entire apparatus or any portion thereof stays within a corresponding heat budget. One or more heat price tags are associated with these data processing operations which are used to determine whether or not a corresponding data processing operation can be currently performed within one or more corresponding heat budgets. If so, the data procession operation proceeds. If not, the data processing operation is delayed. Examples of such data processing operations include, but are not limited to, data retrieval from memory, data storage in memory, lookup operations in memory, lookup operations in a binary or ternary content-addressable memory, regular expression processing, cryptographic processing, or data manipulation.

Rate-controlling of heat generating data processing operations

In one embodiment, a packet switching device provides more than eight behavior aggregates of Quality of Service (QoS) processing based on a service type of a received Multiprotocol Label Switched (MPLS) packet and on a Traffic Class (TC) value extracted from a label of the MPLS packet. The service type is typically determined based on a forwarding equivalence class (FEC) associated with the MPLS packet. This service type may identify a service provided by a service provider and/or the type of packet traffic.

Expanded quality of service processing of multiprotocol label switching (MPLS) packets

In one embodiment, rule-based virtual address translation is performed for accessing data (e.g., reading and/or writing data) typically stored in different manners and/or locations among one or more memories, such as, but not limited to, in packet switching devices. A virtual address is matched against a set of predetermined rules to identify one or more storing description parameters. These storing description parameters determine in which particular memory unit(s) and/or how the data is stored. Thus, different portions of a data structure (e.g., table) can be stored in different memories and/or using different storage techniques. The virtual address is converted to a lookup address based on the identified storing description parameter(s). One or more read or write operations in one or more particular memory units is performed based on the lookup address said converted from the virtual address.

Rule-based virtual address translation for accessing data

In one embodiment, packet streams are reliably transported through a network using packet replication. A packet stream is received at a duplication point in a network, with two or more copies of each of the packet streams being transported, typically over divergent paths in the network, to a merge point from which a single copy of the packet stream is forwarded or consumed. In one embodiment, this merge point is a packet switching device that includes ingress card(s) and egress line card(s), wherein multiple copies of the packet stream are received by ingress line card(s), with only a single copy provided to an egress line card of the packet switching device. In this manner, a switching fabric or other communication mechanism communicatively coupling the ingress line card(s) to the egress line card, nor the egress line card, is taxed with the burden imposed by additional copies of packet stream.

Reliably transporting packet streams using packet replication

In one embodiment, forwarding information bases (FIBs) are selectively populated in a packet switch. A packet switching device determines, based on one or more protocol signaling messages, a subset, which is less than all, on which FIBs a lookup operation may be performed for identifying forwarding information for a received particular packet. The packet switching device populates each of these FIBs, but not all of the FIBs of the packet switching device, with forwarding information corresponding to the particular forwarding value. Thus, FIB resources are consumed for only those FIBs which could actually be used, and not all of the FIBs, for forwarding packets in the data plane of the packet switching device, whether these packets are received on a primary or backup path.

Selectively populating forwarding information bases in a packet switch

In one embodiment, an Internet Protocol (IP) routing information base of a packet switching device is filtered to produce a significantly smaller subset of IP routes that are installed in one or more forwarding information bases for forwarding of IP packets. In one embodiment, these smaller forwarding information bases are located in memory local to a network processor to more quickly perform lookup operations thereon. In one embodiment, one or more of these forwarding information bases is used only for exact matching of addresses (not longest prefix matching). In one embodiment, the IP routes in these smaller forwarding information bases substantially correspond to packet switching devices in a network (e.g., core and edge routers), such as in contrast to including all the IP routes for devices external to the network.

Installing and using a subset of routes for forwarding packets

Growing community of inventors

San Jose, CA, United States of America

John H W Bettink