Cisco Technology, Inc.

Dalit Sagi

William Norman Eatherton

Vijay Rangarajan

Doron Shoham

Garry Paul Epps

Eyal Oren

Danny Levy

Methods and apparatus are disclosed for generating and using an enhanced tree bitmap data structure in determining a longest prefix match, such as in a router, packet switching system. One implementation organizes the tree bitmap to minimize the number of internal nodes that must be accessed during a lookup operation. A pointer is included in each of the trie or search nodes to the best match so far entry in the leaf or results array which allows direct access to this result without having to parse a corresponding internal node. Moreover, one implementation stores the internal node for a particular level as a first element in its child array. Additionally, one implementation uses a general purpose lookup engine that can traverse multiple tree bitmaps or other data structures simultaneously, and perform complete searches, partial searches, and resume partial searches such as after receiving additional data on which to search.

Method and apparatus for generating and using enhanced tree bitmap data structures in determining a longest prefix match

A method for communication includes allocating target bandwidths to two or more packet sources and defining one or more of the packet sources as preferred sources. Quantum values defining maximum amounts of data to be sent during a single scheduling round are defined for the respective packet sources. Repetitive scheduling rounds are performed in order to determine a schedule for processing pending data packets produced by the packet sources. In each scheduling round, all pending packets that are produced by the preferred sources and are within the target bandwidths allocated to the preferred sources are scheduled. Pending packets produced by packet sources other than the preferred sources are scheduled in accordance with the quantum values, within the target bandwidths allocated to the packet sources other than the preferred sources. The pending packets are processed responsively to the schedule. The target bandwidths may comprise, for example, guaranteed bandwidths or excess bandwidths.

Oversubscription of guaranteed bandwidth

Methods and apparatus are disclosed for scheduling entities in a system, such as, but not limited to a computer or communications system. Typically, calendar scheduling is used as a primary scheduling mechanism, with spare time allocated to a secondary scheduling mechanism. The secondary scheduling mechanism can use a round robin technique or variant thereof, or any other scheduling methodology. A calendar entry is examined to determine whether to process a calendar scheduled entity corresponding to the calendar entry or to process a secondary scheduled entity. Which scheduling entity to process is typically determined based on an eligibility of an entity corresponding to the primary scheduled event, a scheduling mechanism indicator, and/or an entity indicator. These combinations of scheduling mechanisms can be used to identify which packets to send, queues or ports to access, processes or threads to execute, or for any other purpose.

Methods and apparatus for scheduling entities using a primary scheduling mechanism such as calendar scheduling filled in with entities from a secondary scheduling mechanism

A pipelined linecard architecture for receiving, modifying, switching, buffering, queuing and dequeuing packets for transmission in a communications network. The linecard has two paths: the receive path, which carries packets into the switch device from the network, and the transmit path, which carries packets from the switch to the network. In the receive path, received packets are processed and switched in a multi-stage pipeline utilizing programmable data structures for fast table lookup and linked list traversal. The pipelined switch operates on several packets in parallel while determining each packet's routing destination. Once that determination is made, each packet is modified to contain new routing information as well as additional header data to help speed it through the switch. Using bandwidth management techniques, each packet is then buffered and enqueued for transmission over the switching fabric to the linecard attached to the proper destination port. The destination linecard may be the same physical linecard as that receiving the inbound packet or a different physical linecard. The transmit path includes a buffer/queuing circuit similar to that used in the receive path and can include another pipelined switch. Both enqueuing and dequeuing of packets is accomplished using CoS-based decision making apparatus, congestion avoidance, and bandwidth management hardware.

Pipelined packet switching and queuing architecture

Methods and apparatus are disclosed for determining a next round robin element requesting service using a cascaded approach. The cascaded approach could be implemented in numerous ways, including, inter alia, a circuit or in software, and be used, inter alia, in a network or computer system. In one implementation, a first stage of the cascaded implementation is divided into multiple groups, each of the multiple groups receives an indication of elements requesting service. Based on a last round robin result and its address, each of the multiple groups determines a candidate for the next result. In the situation where the last result was in a group and the group has a requesting element subsequent in the round robin sequence, that next requesting element is selected and forced to be the selected next result. Otherwise, this processing is repeated by subsequent stages to determine the round robin result. One implementation selects a next result from 4096 requesting inputs within a single clock period using three sixteen input cascaded stages.

Growing community of inventors

Ramat Hagolan, Israel

Dalit Sagi