Browse Prior Art Database

Weighted Queueing Algorithm for Efficient Asynchronous Transfer Mode Traffic Shaping

IP.com Disclosure Number: IPCOM000117620D
Original Publication Date: 1996-Apr-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 4 page(s) / 130K

Publishing Venue

IBM

Related People

Barton, DF: AUTHOR [+2]

Abstract

The Asynchronous Transfer Mode (ATM) User Network Interface (UNI) supports up to 16,777,216 Virtual Connections (VCs). Each virtual connection has its own peak transmission rate. The problem introduced by ATM at the UNI is that, as the number of active virtual channels and number of distinct peak rates increase, it becomes increasingly more difficult to fairly multiplex the ATM cell streams for all of the virtual connections while maintaining high utilization of the transmission media bandwidth and keeping cell delay variation to a minimum. This disclosure introduces a weighted queue servicing algorithm based on queue priority and peak transmission rate as an efficient solution to this problem.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Weighted Queueing Algorithm for Efficient Asynchronous Transfer Mode
Traffic Shaping

      The Asynchronous Transfer Mode (ATM) User Network Interface
(UNI) supports up to 16,777,216 Virtual Connections (VCs).  Each
virtual connection has its own peak transmission rate.  The problem
introduced by ATM at the UNI is that, as the number of active virtual
channels and number of distinct peak rates increase, it becomes
increasingly more difficult to fairly multiplex the ATM cell streams
for all of the virtual connections while maintaining high utilization
of the transmission media bandwidth and keeping cell delay variation
to a minimum.  This disclosure introduces a weighted queue servicing
algorithm based on queue priority and peak transmission rate as an
efficient solution to this problem.

      By defining multiple traffic queues of virtual connections and
assigning peak cell transmission rates and priorities to each queue
such that all virtual connections in a given traffic queue have the
same peak rate and priority, then a simple and efficient queue
servicing algorithm can be implemented by transferring one ATM cell
to the ATM link from the next virtual connection in the traffic queue
that has the lowest service weight, W, as defined below:
                 W = S|P|T
  where W is the concatenation of the bitwise logical not of S, the
bitwise logical not of P, and T.  S, P, and T are the unsigned binary
vectors defined below:
  S - the service request indicator of width 1, which takes the value
       "1" when the traffic queue is requesting service, "0"
otherwise
  P - the traffic queue priority (higher P means higher priority)
  T - the peak rate time interval, reciprocal of a traffic queue's
       peak cell transmission rate

      According to this algorithm, the next ATM cell to be
transferred to the ATM link will come from the next virtual
connection in the traffic queue that is requesting service, has the
highest priority, and has the fastest peak rate of all traffic queues
with the same priority that are also currently requesting service.  A
traffic queue asserts its service request once each peak rate time
interval, and its service request remains asserted until one ATM cell
from each virtual connection in the traffic queue has been
transferred to the ATM link.

      Consider an example (Figure) where there are three traffic
queues, each with different peak rates and different numbers of
active virtual connections...