At&t Bell Laboratories

At+t Corp.

Lucent Technologies Inc.

Ellen L Hahne

Abhijit K Choudhury

Nicholas Frank Maxemchuk

Samuel P Morgan

Henning Gunther Schulzrinne

Ping Pan

Charles R Kalmanek

A reservation is created within a network by sending a stateless probe from a source node toward a destination node. The stateless probe determines a reservation path between the source node and the destination node via intermediate routers in the network. A determination is made if the destination node agrees to create the reservation path to the source node. If the destination node agrees to create the reservation path to the source node, the reservation path is established by returning a corresponding response message to the source node. Links included in more than one established reservation path to the same destination node are identified. The multiple reservations on such links are aggregated. This aggregation creates a tree of reservations rooted at the destination node.

Border gateway reservation protocol for tree-based aggregation of inter-domain reservations

A dynamic threshold system and method is disclosed for allocating memory among different output queues in a shared-memory ATM switch. The maximum permissible length for any individual queue at any instant of time is a function of the unused buffering in the switch. The dynamic threshold system and method deliberately reserves a small amount of buffer space, not allocating it to any currently active output queue, but attempts to equally share the remaining buffer space among the currently active output queues. The dynamic threshold system and method improve fairness and switch efficiency by guaranteeing access to the buffer space for all output queues, and by preventing any single output queue from monopolizing the memory at the expense of the others. The dynamic threshold system and method adapt to uncertain or changing load conditions. The packet losses that occur with dynamic thresholds tend to be clustered at a few offending queues, which is desirable in ATM systems, since it results in fewer messages being disturbed at higher protocol layers and, hence, fewer message retransmissions. The dynamic threshold system and method are also extendable to handle traffic with multiple space priorities.

Dynamic queue length thresholds in a shared memory ATM switch

A system for queueing and selective pushout and method are disclosed for a packet communications module such as a shared memory asynchronous transfer mode (ATM) switch. The shared memory stores packets in queues, each packet having a field and at most two pointers. Within each queue, the packets having respective space priorities are stored in subqueues each having the respective space priorities. The packets are stored in these priority subqueues using a first pointer pointing to the next packet of the same space priority in the queue. The second pointer associated with a stored packet points to the previous packet of greater than or equal space priority in the FIFO order in the queue. The field of a packet is used to store the priority value corresponding to the next packet in FIFO order in the queue, and this field is used by a processor to decide priority sub-queues to serve next. The packets are stored in the queues in a FIFO order using the two pointers and the fields of the packets. The processor controls the selective pushout to push out a packet and uses the two pointers and the fields of the packets to restore the FIFO order. A method is also disclosed including the steps of storing packets in a queue, with each of the queued packets associated with the two pointers and a field; serving the queue; pushing out packets from the queue; and maintaining queue-lengths and a state information table.

Implementation of selective pushout for space priorities in a shared

A method of regulating backpressure traffic in a packet switched network made up of a plurality of switching elements each having a local buffer memory identifies at least one switching element which succeeds at least one other switching element in a transmission path. The at least one succeeding switching element has a congested local buffer memory. A backpressure signal is transmitted to the at least one other switching element. Packets destined for the succeeding switching element are queued in the local buffer memory of the at least one other switching element. Next, it is determined when the occupancy of the local buffer memory for the other switching element has exceeded a predetermined threshold. In response to the exceeded predetermined threshold, the other switching element ignores the backpressure signal transmitted from the succeeding switching element and transmits the queued packets to the succeeding switching element.

Method of regulating backpressure traffic in a packet switched network

A method for use in a high-speed virtual circuit digital network for resizing windows of virtual circuits in nodes of the network. The resizing of a virtual circuit's window is initiated by an input router at an edge of the digital network. When the input router determines that resizing is necessary, it sends a first congestion control message to the nodes through which the virtual circuit passes. If the message indicates a larger window, the node receiving the message determines what size window it can provide and sends the message with that window size on to the next node. An output router at the other edge of the digital network receives the message, sets the window size based on the message as altered by the nodes, and returns a second message with the final window size via the nodes. On receipt of the second message, the nodes alter their windows and the input router sends cells as permitted by the new window. Included in the method are novel techniques for determining the ideal window size for a virtual circuit, for determining at the input router when a change in window size is necessary, and for determining the size of the window in the nodes.

Dynamic window sizing in a data network

Bandwidth balancing is accomplished to DQDB networks that handle multi-priority traffic by causing each node to throttle its own rate of transmission in accordance with the priority of the data that the node transmits. In accordance with one approach, each node limits its throughput to the product of a bandwidth balancing factor (which is a fraction that varies according to the priority level of data) and the unused bus capacity. When parcels of different priorities are received within each node, the parcels are processed in priority order. In accordance with another approach, all active parcels within a node are handled concurrently and receive some bandwidth. The throughput of each parcel in a node is limited to the product of the bandwidth balancing factor and the unused bus capacity. In accordance with still another approach, each traffic parcel limits it throughput to the product of the bandwidth balancing and the bus capacity unused by parcels of equal or higher priority. This scheme allocates bandwidth first to the higher-priority parcels, then allocates the leftovers to the lower-priority parcels. Lower-priority parcels have no effect on the steady-state throughputs of higher-priority parcels.

Fair access of multi-priority traffic to distributed-queue dual-bus

A potential transmission-access failing in the IEEE 802.6 protocol is remedied by the use of terminals that sense the activity level on the interconnecting communications lines. In response to conditions that may give rise to such a failing, each terminal throttles its own transmission rate to improve the transmission capacity allocation of the protocol. In one embodiment, the terminal that transmits over more than half of the slots in the round trip delay simply throttles itself to one half the slots when it detects that another terminal is transmitting or is wishing to transmit. In another embodiment, even a terminal that is transmitting over fewer than half the slots in the round trip delay determines the number of unoccupied slots and throttles itself to transmit over not more than half of the number of available slots. In still another embodiment, a terminal wishing to transmit many packets casts a number of reservation bits onto the transmission channel to insure for itself some transmission capacity. The number of reservation bits sent is equal to a fraction of the available slots. In yet another embodiment, each terminal throttles itself to take no more than a specified fraction of the remaining transmission capacity.

Communications system

A method of controlling congestion in a virtual circuit packet network. A initial packet buffer is assigned to each virtual circuit at each node into which incoming packets are stored and later removed for forward routing. If a larger buffer is desired for a virtual circuit to service a larger amount of data, then additional buffer space is dynamically allocated selectively to the virtual circuit on demand if each node has sufficient unallocated buffer space to fill the request. In one embodiment, the criterion for dynamic allocation is based on the amount of data buffered at the data source. In alternative embodiments, the criteria for dynamic allocation may be further based on the amount of data buffered at each node for a virtual circuit and the total amount of free buffer space at each node of a virtual circuit. Signaling protocols are disclosed whereby data sources and virtual circuit nodes maintain consistent information describing the buffer allocations at all times.

Growing community of inventors

Westfield, NJ, United States of America

Ellen L Hahne