Cisco Technology, Inc.

Stratacom, Inc.

Other

Cisco Systems Inc.

Daniel E Klausmeier

David Anthony Hughes

Kevin C Wong

Charles Matthew Corbalis

Quang Nguyen

Ross Heitkamp

Rafael Gomez

Cherng-Ren Sue

Kambiz Hooshmand

Satish P Sathe

A method of managing oversubscription of a common buffer resource shared by a number of traffic flows in a cell switching network in response to the utilization of the common buffer resource. A buffer utilization threshold is established for each of the traffic flows. As new cells arrive, the global usage of the buffer resource is monitored. As the buffer utilization increases, the thresholds for each of the traffic flows are dynamically adjusted based upon the global usage of the buffer. Aggressive buffer allocations are scaled back when necessary, thereby leaving space for traffic flows which are relatively empty. In one embodiment, the thresholds are coded in mantissa and exponent form so that the scaling is accomplished by adjusting the exponent value.

Method and apparatus for per traffic flow buffer management

A method of executing a sequence of multiple dependent operations, each operation including a memory read and a memory write involves overlapping memory accesses of the operations by grouping together memory reads and memory writes of multiple operations and preserving a desired sequence of the operations using a circuit external to a memory through which the memory accesses are performed. The operations may be updates to one or more linked lists. In one embodiment, the step of overlapping memory accesses may be performed by grouping together memory accesses according to ATM cell arrivals or departures. In this embodiment, the operations are associated with ATM cell arrivals or departures and may be gets or puts. Each get and put operation may be characterized by a number of atomic memory operations to update one or more linked lists. To perform the operations a circuit a having an address processor, a data processor coupled to the address processor and to the external memory, and a prefetch buffer coupled to the external memory, the address processor and to the data processor is provided. The address processor generates memory addresses for the operations according to the step of overlapping memory accesses. The atomic memory operations are grouped so that all of the memory read operations associated with the dependent operations are performed before all of the memory write operations associated with the dependent operations are performed.

Method and apparatus for maximizing memory throughput

A plurality of cells are received from a digital network and stored in a logical queue. The cells contain data information and logical connection information and the logical queue corresponds to the logical connection identified by the logical connection information. The cells are combined into a frame by extracting the cells from the logical queue and storing the cells to a local memory so that the data information is preserved. Extraction may be accomplished by notifying a local processor that the frame's worth of data is ready and then transferring the data information of the cells to a local memory at the direction of the local processor. During the transfer, error detection operations may be performed. Information may be transmitted into the digital network by segmenting a frame of data into a plurality of cells and injecting each of the cells into a logical queue. The logical queue may be constructed with a series of linked list pointers associated with the memory locations. The cells may then be transmitted into the digital network in an order consistent with the linked list pointers.

Method and apparatus for using ATM queues for segmentation and reassembly of data frames

In a digital switch, incoming cells are placed into a queue in a cell memory. The switch maintains various cell queues, including VC queues that correspond to individual connections and QBin queues that correspond to various classes of service. Cells may arrive to a VC queue or a QBin queue but will depart from a QBin queue. Accordingly, cells may be moved from VC queues to QBin queues. Cells are serviced according to the use of QBin Groups. A QBin Group (QBG) includes a number of logical queues (QBins) of cells to be transported in the digital network. After a QBG is selected, one of its logical queues is selected for servicing. The QBG may be selected by examining all of the QBGs to find an eligible QBG which is most overdue for service. A QBin of the selected QBG may then be selected by examining each of the QBins comprising the selected QBG to find the most overdue for service. The QBGs may correspond to virtual interfaces.

Multi-stage queuing discipline

A method and apparatus for buffering information in a digital network are provided. Each data element arrives on a particular logical connection. The apparatus stores the data element in the tail of a queue that corresponds to the connection on which the data element arrived. The apparatus maintains one queue for each connection. The apparatus tracks the state of the queues using linked lists. Each entry in the linked list corresponds to a block in the memory used to store the data. The entries that correspond to blocks that contain data for a particular connection are linked together to reflect the order of arrival of the data stored in the corresponding blocks. Information that is generated about a particular data element after the data element has been stored is placed in the linked list entry that corresponds to the block in which the data was stored, rather than in the block with the data. A connection indicator is stored with each data element to indicate the connection on which the data element is to be sent. Prior to sending a data element over a specified connection, the apparatus compares the stored connection indicator with the specified connection. If it is different from the connection indicated by the connection indicator, then an error signal is generated.

System for buffering data in the network having a linked list for each

A method and apparatus are provided for scheduling when each of a plurality of virtual connections supported by a transmit device will be serviced by the transmit device. The transmit device includes a transmission control unit that uses a plurality of calendars to schedule when each of the plurality of virtual connections will be serviced. Virtual connections with faster transfer rates are scheduled using higher granularity calendars, while virtual connections with slower transfer rates are scheduled using lower granularity calendars. Each entry in the calendars is associated with a time interval ('cell slot') during which the transmit device is able to service one virtual connection. During a given cell slot, linked lists associated with the calendar entries that correspond to the cell slot are added to a service queue, and the virtual connection at the head of the service queue is serviced. After a virtual connection is serviced, the next service time for the virtual connection is scheduled by attaching the virtual connection to the head of a linked list associated with the appropriate entry of the appropriate calendar. The appropriate entry is determined by incrementing a fixed-point 'desired service time' value that represents the cell slot for which the virtual connection was last scheduled, by a fixed-point inter-gap value that represents the how many cell slots ideally elapse between sequential service times of the virtual connection.

Multi-level rate scheduler

A frame based traffic policing system that determines if incoming data cells are conforming or non-conforming according to the a traffic contract. The frame based traffic policing system first detects a cell at the beginning or end of a frame and determines if the frame conforms with a traffic contract. If the cell does not exceed the parameters of the traffic contract, then the frame based traffic policing system deems the cell as conforming. If the cell was the first cell of a frame, then frame based traffic policing system treats all the remaining cells in the frame as conforming or non-conforming depending upon if the first data cell was conforming or non-conforming. If the cell was the last cell of a frame, then frame based traffic policing system treats all the cells of the following frame as conforming or non-conforming depending upon if the last cell of a previous frame was conforming or non-conforming. In this manner, all the data cells are from the same frame receive the same treatment by the network. The frame based traffic policing system improves the throughout of the network since the network will be less likely to waste resources transmitting cells from a corrupted frame.

Frame based traffic policing for a digital switch

To simplify the service decision made in a queue based digital switch, a method and apparatus is introduced that makes service decisions based upon the history of incoming cells. The apparatus includes a minimum service rate circuit that monitors the rate of arriving cells. The minimum service rate circuit tests the arriving cells to determine if they are in conformance with the minimum service rate of a service contract. The minimum service rate circuit may use a continuous state leaky bucket algorithm as specified in the CCITT Recommendation I.371 document, dated 1992, to determine if a cell is in conformance with the minimum service rate of the service contract. When a cell arrives that conforms to the minimum service rate, the minimum service rate circuit notifies the server and the server serves the queue associated with the connection.

Method and apparatus for implementing communication service contract

A method for performing rate control for digital communication systems. A server serves N connection queues where each connection queue has accumulation rate a.sub.i. Each credit accumulation rate a.sub.i is divided into a set of binary coefficients. The connections are then divided into connection groups wherein each connection group has group accumulation rate created using the binary coefficients. The connection group accumulation rate is used to maintain a group credit balance c.sub.j. To select a connection to be served, the server examines the group credit balances and selects the group with the greatest credit balance. A connection within the selected group is chosen using a round-robin system. Thus the server selects a connection to serve without performing a linear scan over all the connections.

Growing community of inventors

Sunnyvale, CA, United States of America

Daniel E Klausmeier