Washington University

Cisco Technology, Inc.

At&t Bell Laboratories

Jonathan S Turner

Zubin D Dittia

William Norman Eatherton

Daniel E Lenoski

John Andrew Fingerhut

Michael Brian Galles

Jerome R Cox, Jr

Thomas Dejanovic

George Varghese

Marcel Waldvogel

Vinod Gerard John Peris

Leonard F Wyatt

Methods and apparatuses are disclosed for pacing the rate at which packets of one or more information streams are sent from a device, such as, for example, a workstation, computer, communications mechanism, or component thereof. Typically, multiple timing wheels each having a different timing granularity are used to schedule the transmission of packets of information corresponding the to the information streams. Using multiple timing wheels in this manner allows scheduling of a larger range of rates while typically using a significantly smaller amount of memory than a single timing wheel covering the same range of rates. An entry, corresponding to a next portion of an information stream to be sent from the device, is inserted into the timing wheels at a target time for sending the information. At the target time, the entry is removed and placed in a transmit list of items to be sent from the device. In one implementation a single transmit list is used for all timing wheels. In another implementation, multiple transmit lists are used, typically one for each timing wheel. Entries corresponding to portions of the information streams to be sent from the device are removed in a queued or target transmission time order from a transmit list. A packet of information corresponding to a removed entry is sent, and the entry itself is re-inserted in a timing wheel for the determined next transmission target time.

Method and apparatus for pacing the flow of information sent from a device

Methods and apparatus are disclosed for accumulating traffic information and distributing flow control information in a packet switching system. Traffic information is collected in multiple elements and indications of congestion and/or other types of information useful in determining traffic conditions are forwarded to collecting elements. The collecting elements manipulate the received indications and generate flow control messages which are sent to individual sending components. In one implementation, a switching element maintains for each destination a count of packets within itself which are addressed to the particular destination. Indications of this collected information are sent to collecting switching elements. These collecting elements accumulate the information received from multiple sources. The accumulated information is evaluated, and when a congestion condition is located or anticipated, then flow control messages are distributed to all, or a subset of, the packet sources.

Method and apparatus for accumulating and distributing traffic and flow control information in a packet switching system

Methods and apparatuses are disclosed for controlling the rate at which packets are sent from a first to a second component of a packet switching system. In one implementation, the first component represents an input line card to a packet switch, and the second component represents an output of the packet switch. In such a system, a state is maintained for each output at each line card. For example, these states may include an unconstrained state during which traffic is sent at a full rate to the output, an off state during which no traffic is sent to the output, and a constrained state during which traffic is sent at a reduced rate to the output. Typically, this reduced rate is proportional to the arrival rate of packets at the input line card which are destined for the output. The state of the output is changed based on received flow control information about the output and whether traffic remains queued for the output at the input line card.

Method and apparatus for controlling input rates within a packet switching system

Methods and apparatus are disclosed for distributing fault indications and maintaining and using a data structure indicating faults to route traffic in a packet switching system. In one embodiment, a packet switching system detects faults and propagates indications of these faults to the input interfaces of a packet switch, so the packet switch can adapt the selection of a route over which to send a particular packet. Faults are identified by various components of the packet switching system and relayed to one or more switching components to generate a broadcast packet destined for all input ports (i.e., to each I/O interface in a packet switch having folded input and output interfaces). Other embodiments, generate one or more multicast or unicast packets. The I/O interface maintains one or more data structures indicating the state of various portions of the packet switching system. In one embodiment, an output availability table is maintained indicating over which path a particular destination may be reached, as well as a link availability vector indicating which output likes of the input interface may be currently used. Using these as masks against possible routes in a fully functional system, the packet switching component (e.g., I/O interface) can identify which routes are currently available for reaching the destination of the received packet. These routes can then be selected between using one of numerous deterministic and non-deterministic methods.

Distributing fault indications and maintaining and using a data structure indicating faults to route traffic in a packet switching system

Methods and apparatus for forwarding packets in a multistage interconnection network are provided which timestamp packets using a substantially system-wide timing reference and a merge sorting variant to restore packets to the proper order, using the timestamp information carried in the packets. One implementation determines when packets passing along different paths in the network can be safely forwarded, even when no packets have recently been received on some of the paths, by forwarding status messages along otherwise idle paths. The status messages provide information that can be used by downstream components to allow them to determine when packets passing over other paths can safely be forwarded. One implementation simultaneously resequences packets being delivered to all n outputs of the multistage interconnection network. The resequencing operations are distributed among a plurality of switching elements making up the interconnection network.

Communications interconnection network with distributed resequencing

Methods and apparatus are disclosed for propagating timestamp floors throughout a packet switching system and using the timestamp floors received at a first component of the packet switching system to determine when a packet may be sent from a packet switching system. Each input of a first stage of a packet switching system maintains a floor register which is updated by copying the timestamp from each arriving packet. In some systems, if a packet is not received during a packet time, the timestamp is automatically updated, typically by adding a fixed time value. Periodically, the first stage switching element forwards a timestamp floor to the next stage switching elements. In one implementation, this distributed timestamp floor is the lesser of the earliest timestamp in one of the floor registers in the input queues, and the earliest timestamp in an output queue for the particular next stage switching element. In a buffering component, typically an output interface or possibly a final stage switching element, each output queue maintains a floor register for that output. When a packet in the particular output queue has a timestamp less than or equal to the timestamp floor maintained in the output queue, the packet is allowed to be sent.

Resequencing packets at output ports without errors using packet timestamps and timestamp floors

Connection distributors are used to route packets corresponding to multiple streams of packets through a packet switching system. During each time slot, one packet is typically sent from each packet stream. During the configuration of a packet stream, a time slot and primary route is determined for the packet stream. The primary route is a route through the packet switch which is non-blocking with other packet streams during the assigned time slot. During a common frame, a packet of each packet stream is sent out of a line card or packet interface to be routed through the packet switch over the designated primary route. During subsequent frames, packets are sent over different routes through the network (until all routes are used and then the cycle repeats). These routes are selected based on a deterministic method so as to maintain the non-blocking characteristic of the primary route selection.

Route scheduling of packet streams to achieve bounded delay in a packet switching system

Methods and apparatus are disclosed for accumulating and distributing information in a packet switching system. For example, it is desirable in certain packet switching systems to communicate the status of internal queues and other port status information from an individual port to all other ports (or at least those which are communicating with the individual port). The amount of information being sent from the individual port is typically very small, such as on the order of a few bits or bytes. By accumulating the information and then broadcasting the collected flow control information, a vast amount of switch fabric resources (e.g., bandwidth) can be saved. In one implementation, flow control information is sent to a destination (e.g., a &ldquo;mailbox&rdquo;) within a packet switching fabric which includes a memory in which flow control information is accumulated. After a period of time or based on the occurrence of some event, the accumulated flow control information is distributed. This same mechanism may be used to distribute most any type of information (e.g., flow control information, signaling information, and data internal or external to a packet switch or packet switching system).

Method and apparatus for accumulating and distributing data items within a packet switching system

Methods and apparatus are also disclosed for responding to received flow control messages indicating a previously congested port is now in a non-congested state. Many different components that have packets to send to a particular output will receive an indication that they are now allowed to send these packets at roughly the same time as the other components. If all components start sending at the same time, then the packet switch might become congested, possibly very quickly. If the packet switch cannot respond and transmit flow control messages to all of these sources fast enough, certain internal buffers could overflow and thus packets might be lost. On implementation causes components to start sending to the destination at varying times to gradually increase the traffic being sent to the destination. In this manner, the traffic in the packet switch gradually rises which allows buffers within the packet switch to drain while new traffic is arriving, and allows the packet switch time to react and throttle-back the traffic in a reasonable manner should paths leading to the output become congested.

Method and apparatus for delaying packets being sent from a component of a packet switching system

Methods and apparatus are disclosed for determining the order to send information arriving at the inputs of a packet switching system. A line card maintains its own data structure indicating flow control information and a queue for each destination it is sending data with its memory. Control logic then controls the placing of the incoming data into these queues and for taking the data out of the queues and sending the data, typically in the form of packets, to the packet switch. As information arrives at a line card, priority outgoing packet time slots are allocated for that destination. In this manner, each destination is given the opportunity to send information at its arrival rate. In the remaining bandwidth or packet cycles available on the outgoing link, the destination queues containing information retained due to a congestion condition are serviced.

Method and apparatus for scheduling packets being sent from a component of a packet switching system

Methods and apparatus are disclosed for accumulating and distributing flow control information via update messages and piggybacked flow control information in other messages. One implementation operates using at least two techniques. Using a first technique, for every packet entering the switching system from a line card, the switching system conveys flow control information (typically congestion or both congestion and no-congestion indications) for the packet's destination to the line card. Using a second technique, the switching system will periodically convey congestion and no-congestion indications for all destinations to the line cards. In one implementation, when the first technique is used to provide only congestion indications, the periodic distribution of flow control information using the second technique provides non-congested indications which allows the line cards and their sources to resume or begin sending to the non-congested destinations.

Accumulating and distributing flow control information via update messages and piggybacked flow control information in other messages in a packet switching system

A method and apparatus for an exponentially faster technique than is presently utilized in routers for looking-up destination addresses and matching them to a prefix in order to determine an output data link for routing of the data message to a destination. The basic algorithm includes arranging the prefix and corresponding output data link information in sub-databases arranged by prefix length and then using a multi-step prefix length binary search algorithm to sort through the sub-databases to determine a best matching prefix for routing of the data packet. Various refinements of the basic algorithm are disclosed to further enhance the search time including adding markers representative of sub-database entries having a longer prefix length and also various searching methodologies to minimize the number of searching steps including rope searching in various formats. Thus, methodologies are disclosed for building the sub-databases, as appropriate to implement the corresponding novel search routines and perform the novel search routines themselves, and the router which implements all of the foregoing. Many of the inventive features disclosed herein are applicable to other routing DPJ protocols such as OSI Routing, call routing and telephone DPJ networks, and string matching problems.

Scalable high speed IP routing lookups

Multicasting is implemented in a virtual circuit switch for an ATM network by recycling data cells through the switch fabric a multiple number of times with a copy-by-two network creating an additional data cell upon each recycle to thereby satisfy the number of connection addresses in the multicast connection. Resequencing of the data cells may be implemented at the exit to the switch fabric as well as upon each recycle of data cells through the switch fabric.

Multicast virtual circuit switch using cell recycling

A resequencing buffer and buffer control circuit is disclosed for resequencing data packets into their timed sequence after traversing a switch fabric which can introduce a misordering of data packets because of the varying time intervals required for data packets to traverse the switch fabric in a non-blocking manner. The resequencing buffer controller includes a plurality of hi-directional shift registers for storing each data packet's age and slot number, each bi-directional shift register having an associated slot control circuit for feeding the age and slot number one bit at a time onto a contention bus to thereby determine the oldest data packet eligible for transmission. The contention bus is an exclusive OR wire bus which interconnects the slot control circuits and an output circuit which controls the buffer to output the slot number containing the data packet of oldest age. In the event of ties between data packets having the same age, the slot numbers of the buffer are used to select a data packet for transmission.

Data packet resequencer for a high speed data switch

A resequencing buffer and buffer control circuit is disclosed for resequencing data packets into their timed sequence after traversing a switch fabric which can introduce a misordering of data packets because of the varying time intervals required for data packets to traverse the switch fabric in a non-blocking manner. The resequencing buffer controller includes a plurality of bi-directional shift registers for storing each data packet's age and slot number, each bi-directional shift register having an associated slot control circuit for feeding the age and slot number one bit at a time onto a contention bus to thereby determine the oldest data packet eligible for transmission. The contention bus is an exclusive OR wire bus which interconnects the slot control circuits and an output circuit which controls the buffer to output the slot number containing the data packet of oldest age. In the event of ties between data packets having the same age, the slot numbers of the buffer are used to select a data packet for transmission

Growing community of inventors

St. Louis, MO, United States of America

Jonathan S Turner