Cisco Technology, Inc.

Alcatel Lucent

Alcatel-lucent USA Inc.

Andrew McRae

Jeffrey Kidd

Liang Li

Seenu Banda

Hugh Nhan

Robert Haragan, Jr

Thanh Trung Dao

Parthibhan Parama Guru

Vinodh Kumar

Mohan Sundaram

Sanjeev A Mahajan

David James Stewart

Classifying packets is disclosed. In some embodiments, a packet can be classified once for a plurality of nodes. The classification of a packet can be used at a receiving node to determine the receiving node policy for the packet. In some embodiments, the classification of a packet is specified by a classification index associated with the packet. In some embodiments, the receiving node policy for the packet can be determined by performing a lookup in a data structure associated with the receiving node based at least in part on the classification index of the packet. In some embodiments, the classification of the packet is sufficient to specify not only the receiving node policy but also a plurality of policies of a plurality of nodes.

Classifying packets

Processing management packets is disclosed. In some embodiments, a network device includes a set of line cards. Each line card may include a management processor. In some embodiments, if it is determined that a management packet received by a first management processor of a first line card is associated with a management process that is at least in part associated with a second management processor on a second line card, the management packet may be forwarded from the first management processor to the second management processor. In some embodiments, a set of one or more management processors operate as a cluster of peers to implement the management functionality of a network device and may communicate via a private network.

Processing management packets

Managing processes on a network device is disclosed. A set of processes running on a network device may be monitored and managed by a set of one or more dedicated components. In some embodiments, if a process on a first management processor on a first line card has at least in part failed, the process may be migrated to a second management processor on a second line card. If a request for the migrated process is received, it is directed to the second management processor on the second line card.

Managing processes on a network device

An improvement in the compilation of classification tables from across control lists increases the efficiency of memory utilization by fragments in the lower level tables and using the classification ID's from a pair of higher-level tables as pointers to the fragments and as indicators of the depth of the entries in the fragments. A further improvement makes use of aggregate bit vectors, thereby simplifying construction of the lower-level tables. The bit-vector sections preferably coincide with the cache lines of the processing, thereby maximizing the speed with which the relevant bits in the bit vector can be identified from the aggregate bit vectors.

Compilation of access control lists

A system and method for implementing a CPU/Network Device Interface that reduces the CPU involvement in managing the interface. New data structures in shared memory that are either read-only or write-only by CPU allow the CPU to efficiently utilize techniques such as write-posting and cache prefetching. Additionally, hardware-assisted packet transmission and high-level packet flow control reduce the burden on the CPU. A fair allocation system assures fair access to the receive interface by multiple line cards.

Network device/CPU interface scheme

A software-implemented switching path includes separate control and data planes with the data plane having a graph of feature nodes with each node implementing a feature to be applied to a packet being switched. Each feature node includes private data and code which are utilized to apply the feature to the packet. The packet is switched to a next node based on packet-specific context data.

Flexible software-based packet switching path

In one embodiment, a super class that contains a plurality of matching rules is generated. The matching rules of the super class are converted into a hierarchical arrangement of lookup tables and equivalence sets, the hierarchical arrangement having a plurality of levels including a first level and a final level. A final equivalence set is associated with the final level. The lookup tables and final equivalence set are then used to generate a results table that indicates a network packet is associated with a particular class.

Method for classifying packets using multi-class structures

Incremental compilation of packet classifications using fragmented tables

A technique classifies packets in a manner that is both deterministic and efficient. A hierarchical arrangement of lookup tables is organized into levels to classify the packets. Entries contained in the lookup tables are incrementally built and added to the lookup tables as packets are classified. A packet is divided into a series of fields and a first-level lookup table is built for each of these fields. Successive-level-lookup tables are then allocated and initialized to contain 'missing' entries. When a packet is classified, it is applied to the first-level lookup tables to produce a series of indices. These indices are then applied to the second-level lookup tables to select indices that are the applied to a next-level table and so on until an outcome index is selected from a final-level lookup table. If the entry selected in the second-level lookup table is empty the successive-level entries are built and the classification is retried.

Incremental compilation for classification and filtering rules

A technique for classifying a packet in a deterministic number of lookup operations. The technique builds a single 'super class' that contains the match criteria for all the rules associated with packet classification. The 'super class' is then compiled to produce a series of lookup tables and equivalence sets, including a final lookup table and equivalence set. The final equivalence set is then &#x201c;post-processed&#x201d; to associate the entries in the final lookup table with a particular result.

The present invention allows for processing classification and/or security filtering rules by using bitmaps as representations. In one instance, the packet header involved in the packet classification is divided into sections (fields) such as 16 bit portions. Once, this is performed, a data lookup table is built for each of the packet header fields. In particular, a bitmap is created representing which filter rules match a certain packet header field value. The created data lookup tables, typically one for each packet header field, are merged to form intermediate level data lookup tables. The intermediate level data lookup tables are continuously merged until one final data lookup table is formed. The result of the final data lookup table represents all the possible packets to be classified. Thus, each final data entry has a bitmap representing the filtering rules that matches this entry. The bitmap can be used to selectively provide a desired result of the classification. For instance, a first matching rule is represented by the first bit set in the bitmap; the best matching rule is determined by processing the bitmap and selecting the most appropriate rule; and a complete set of rules that match is represented by the full bits set in the bitmap.

Growing community of inventors

Berowra, Australia

Andrew McRae