Cisco Technology, Inc.

Thomas Dejanovic

John Joseph Williams, Jr

Gregg Anthony Westbrook

Jonathan E Michelson

Bruce Alexander Wilford

Zubin D Dittia

Jonathan S Turner

John Andrew Fingerhut

Anurag Singh Maunder

Methods and apparatus are disclosed using a random indication to map items to paths and to recirculate or delay the sending of a particular item when a destination over its mapped path is unreachable, including, but not limited to the context of sending of packets across multiple paths in a packet switching system. In one implementation, a set of items is buffered, with the set of items including a first and second sets of items. The items in the first set of items are forwarded over a set of paths in a first configuration. The set of paths is reconfigured into a second configuration, and the items in the second set of items are forwarded over the set of paths in the second configuration. In one implementation, a recirculation buffer is used to hold items not immediately sent. In one implementation, the paths are reconfigured in a random fashion.

Method and apparatus using a random indication to map items to paths and to recirculate or delay the sending of a particular item when a destination over its mapped path is unreachable

Methods and apparatus are disclosed for an adaptive rate control mechanism reactive to flow control messages in a packet switching system and other communications and computer systems. Typically, a multiplicative increase and exponential decrease technique is used to throttle traffic. Backpressure feedback is used to calculate the initial rate at which to allow traffic after backpressure is deasserted. This reduces the probability of underrun of buffers (e.g., too little traffic being carried). The adjustment to the initial rate is made by measuring the time between the XON and XOFF in factor periods. Then a target XON time is subtracted. If the result is positive (i.e., the measured XON time was too long), the rate is multiplicatively increased (e.g., by a factor of two to the difference). If the result is negative (i.e., the measured XON time was too short), the rate is exponentially decreased (e.g., by the square root).

Method and apparatus for an adaptive rate control mechanism reactive to flow control messages in a packet switching system

Methods and apparatus are disclosed for distributed reassembly of large packets split into smaller packets. Larger packets are split into several smaller packets, which are marked with a sequence number, timestamp, or other ordering and reassembly indications, and sent through a system or network. These smaller packets are received at the destination location by multiple reassembly components, which distribute information as to received packets and coordinate the sending of packets from themselves so as to produce the reassembled larger packets. In one implementation, each of the multiple reassembly components maintains one or more data structures indicating packets stored locally and those packets stored anywhere or elsewhere within the multiple reassembly components. When all smaller packets comprising a larger packet are received by one of the distributed resequencing components, the reassembly components transmit their smaller packets in a coordinated fashion as to produce the original larger packet.

Method and apparatus for distributed reassembly of subdivided packets using multiple reassembly components

Methods and apparatus are disclosed for communicating time and latency sensitive information in a system, such as, but not limited to a computer or communications system. A first block of data is identified and transmitted. A check code is partially determined based on this first data. While the first data is being transmitted, the time-sensitive data (e.g., flow control, other control information, etc.) is identified. This identified time-sensitive data is then contiguously transmitted after the first data. The determination of the check code is completed based on the time-sensitive data, and the check code is contiguously transmitted after the time-sensitive data. One implementation receives the first data, the time-sensitive data, and the check code. If error correction is being used and is needed, the time-sensitive data is first corrected based on the check code, and then subsequently, the first data is corrected. In this manner, the latency of the availability of this time-sensitive data may be reduced.

Methods and apparatus for communicating time and latency sensitive information

Traffic information is accumulated and flow control information distributed in a packet switching system. Traffic information is collected in multiple elements, which forward in a coordinated fashion to collecting elements indications of congestion and other types of information. The collecting elements manipulate the received indications and generate flow control messages which are sent to individual sending components of the packet switching system. In one implementation, a switching element maintains for each destination a count of packets within itself which are addressed to the particular destination. An indication of a portion of this collected information is included in a packet header forwarded from each of the elements each packet time. Each of the elements are assigned a different offset, such that they send an indication of a different portion of their collected information, so a view of the traffic conditions and/or buffer occupancies within a packet switching system is efficiently produced.

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

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.

Methods and apparatus are disclosed for distributing flow control information in a packet switching system. In one packet switching system, flow control information is collected in a data structure in the first stage switching elements. Each of these switching elements transmit data from the flow control data structure as small messages or in fields included in packets being sent across multiple statically allocated paths. Flow control information is received by next stage elements, which are programmed to forward only flow control information received from a limited number of components or over a limited number of paths. The first stage switching elements may also periodically or occasionally delay sending flow control information or send a dummy message or information to accommodate bandwidth transmission differences between components of the packet switching system, including to accommodate bandwidth variations caused by plesiochronous timing across the network.

Method and apparatus for distributing information within a packet switching system

Methods and apparatus are disclosed for using barrier phases to synchronize processes and components in a packet switching system, including, for example, but not limited to the use of barrier phases in the coordinated timing of the sending of information (e.g., flow control information) within a packet switching system, and the use of barrier phases in a packet sequence number windowing protocol. In one implementation, elements are assigned to one of multiple ordered sets of a barrier groups, wherein each element of a barrier group must be set to a common barrier state before any element of a next a barrier group can switch to a next barrier state, and once all elements of a particular barrier group switch to a new barrier state, all the elements of the next barrier group begin to switch to the next barrier state.

Method and apparatus for using barrier phases to synchronize processes and components in a packet switching system

Methods and apparatus are disclosed for using barrier phases to limit the disorder of packets which may be used in a computer or communications system. In one packet switching system, source nodes include an indication of their current barrier state in sent packets. For each barrier state, a predetermined range of sequence numbers may be used or a predetermined number of packets may be sent by a source node. The source, destination, and switching nodes are systematically switched between barrier phases, which is typically performed continuously in response to the flow of barrier request and barrier acknowledgement packets or signals. Each source node broadcasts to all forward connected nodes a barrier request to change to a next barrier state. After a switching node has received a barrier request on all incoming links, the switching node propagates the barrier request. Upon receiving barrier requests over all links, each destination stage relays an acknowledgement message to all connected source elements, which then send a barrier acknowledgement in much the same way, and each source element changes its barrier state causing the sequence number or counting space to be reset, and newly sent packets to indicate the new barrier state. Upon receiving all its barrier acknowledgement messages, each destination stage changes its barrier state, and then the destination can manipulate (e.g., resequence, reassemble, send, place in an output queue, etc.) packets marked with the previous barrier state as it knows that every packet from the previous barrier state has been received. This transition of barrier phases and limiting the number of packets sent per barrier phases may be used to limit the range of the sequence number space and the size of outgoing, resequencing, and reassembling buffers, as well providing a packet time-out mechanism which may be especially useful when non-continuous sequence numbers or time-stamps are included in packets for resequencing and/or reassembly purposes.

Method and apparatus for using barrier phases to limit packet disorder in a packet switching system

Methods and apparatus are disclosed for distributed resequencing of packets belonging to an original stream of packets in a computer or communications system. Typically, packets of the original stream are marked with a sequence number, timestamp, or other ordering indication, and distributed among different paths and arriving at a location possibly out of their original sequence. These packets are received at the location by multiple resequencing components, which distribute information as to received packets and coordinate the sending of packets from themselves so as to produce a stream of resequenced packets. In one implementation, each of the multiple resequencing components maintains one or more data structures indicating packets stored locally and those packets stored anywhere (or elsewhere) within the multiple resequencing components. When a next packet in the original sequence has been received, the packet is sent out.

Method and apparatus for resequencing of packets into an original ordering using multiple resequencing components

Methods and apparatus are disclosed for distributed resequencing and distributed reassembly of large packets split into smaller packets with each packet typically marked with a sequence number, timestamp, or other ordering and reassembly indications, and distributed among different paths and arriving possibly out of their original sequence. Multiple resequencing components communicated information as to received packets and coordinate the sending of packets from themselves, typically to produce a stream of resequenced packets which is then distributed to multiple reassembly components, which communicate information as to received packets and coordinate the sending of packets from themselves so as to produce the reassembled larger packets. When all packets comprising a larger packet are received by one of the distributed resequencing components, the reassembly components transmit their packets typically over a common bus or link in a coordinated fashion as to produce the original larger packet.

Method and apparatus for distributed resequencing and reassembly of subdivided packets

The invention provides a system and method for sharing packet traffic load among a plurality of possible paths. Each packet is associated with a flow, and a hash value is determined for each flow, so as to distribute the sequence of packets into a set of hash buckets. The hash value has a relatively large number of bits, but is divided by the number of possible paths so as to achieve a relatively small modulus value; the modulus value is used to index into a relatively small table associating one selected path with each entry. The modulus value is determined by a relatively small amount of circuitry, simultaneously for a plurality of moduli, and one such modulus value is selected in response to the number of possible paths.

Load sharing across flows

The invention provides a system and system for sharing packet traffic load among a plurality of possible paths. Each packet is associated with a flow, and a hash value is determined for each flow, so as to distribute the sequence of packets into a set of hash buckets. The hash value has a relatively large number of bits, but is divided by the number of possible paths so as to achieve a relatively small modulus value; the modulus value is used to index into a relatively small table associating one selected path with each entry. The modulus value is determined by a relatively small amount of circuitry, simultaneously for a plurality of moduli, and one such modulus value is selected in response to the number of possible paths.

Growing community of inventors

Sunnyvale, CA, United States of America

Thomas Dejanovic