Distributed FIFO queuing for ATM systems

Details Distributed FIFO queuing for ATM systems Distributed FIFO queuing for ATM systems

1998-08-25

2001-09-18

Chin, Wellington (Department: 2664)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S229000, C370S230000

Reexamination Certificate

active

06292491

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to digital communication systems and in particular to an access node that makes use of distributed queuing such as may be deployed in an Asynchronous Transfer Mode (ATM) network system.
BACKGROUND OF THE INVENTION
Packet switching communication networks such as those based upon Asynchronous Transfer Mode (ATM) technology are increasingly used to transfer digital information over long distances. A typical ATM network can be viewed as including several different types of elements that permit an end node or user node such as a personal computer (PC) to be connected to other digital terminal equipment (DTE) such as host computer or service provider node. ATM networks transfer data in fixed length packets or “cells” on a demand driven basis using virtual paths and virtual channels defined within a physical transmission medium.
With the recent explosive growth in Internet-related data traffic, network service providers (NSPs) have had to find new ways to quickly upgrade their own network facilities to alleviate congestion and bottlenecks. The NSPs have therefore begun to deploy ATM technology in the core or background of their networks as an efficient and flexible means of carrying large amounts of data traffic. ATM is also being deployed towards the edge or access side of the network where it may provide connections to access multiplexers or so-called access nodes that allow residential users to connect to Internet Service Providers (ISPs) through an ATM network.
The elements within an ATM network include devices known as an access node and a switching node. The access node, more formally called a service access multiplexer, allows the combination of a variety of lower speed service connections into a single higher speed connection. The switch nodes may thus use higher speed communication links to move cell traffic to its intended destination. For example, an access node may aggregate traffic on multiple low speed links such as T
1
or xDSL type digital communication links, and provide a connection to a switching node via high speed trunk lines such as T
3
or OC
3
communication links.
In general, it is desired that the trunk lines connected between the access nodes and the switching network only require a traffic capacity which is sufficiently large enough to handle the average expected load but not necessarily a peak expected load. The access nodes therefore preferably also perform some type of statistical multiplexing function. The statistical multiplexing function can, for example, operate on the cells on a first-in and first-out basis. In other words, the next cell to be sent over the trunk line can be selected to be the cell which entered the access node first.
Any mechanism used for selecting the cell priority needs to be fair and nonblocking in order for most applications, such as transaction processing, voice over cell and/or cell aggregation schemes for multiple users, to operate properly. In practice, first-in first-out queuing alone has been unable to provide the characteristics expected of an ATM network. It is, therefore, also often desirable in such networks for some sort of priority access to be granted to certain cells.
One priority scheme has been to try to equalize the bandwidth allocated per user node. Another approach is to prioritize access to the trunk based upon traffic loading. In this scenario, priority is granted on a dynamic basis to the nodes which have the higher amount of traffic.
Implementing any sort of priority scheme in this situation is complicated by the fact that ATM itself is a type of multiplex scheme. In particular, ATM was originally conceived as a flexible and responsive method for supporting multiple forms of digital traffic, including data, voice, image, and video, while providing rapid adaptability to changes in patterns of network traffic. The users of ATM networks generally expect that a mixture of bursty and delay sensitive traffic can be processed simultaneously.
ATM contrasts with more traditional multiplexing methods in the way in which it allocates communication channels. In traditional time division multiplexing, for example, communication channel access is divided into fixed periods of time called “frames.” Frames are then divided into a fixed number of time slots of equal duration. Each user is then assigned a certain time slot within each frame. The time slots are generally implemented in a manner which is synchronous. A user node can therefore access a communication channel only during the time slot that has been allocated to them. If no traffic is ready to send when the designated time slot occurs, then the time slot is unused.
In contrast to this, in an ATM network, access to the communication channel is more flexible. Any user needing to communicate can use the channel whenever it is available. Therefore, ATM imposes no regular pattern on the way users are given access to a communication channel. In order to avoid a situation where any given user would monopolize the channel, every message is divided into small, fixed length cells. Arrangements are then made in the switching fabric such that no single user can monopolize access to the communication channel while other users have messages to send.
Any arbitration scheme for an access node to be used together with an ATM network therefore should exhibit priority allocation properties that are consistent with the overall ATM architectural philosophy. Otherwise, the access node itself may restrict the benefits obtainable by using ATM in the first place.
It is also useful to have a system that can be used to distribute the cell bus control mechanism over multiple cell queues with no central entity making the decision as to which cell is to be transmitted. This would have many advantages, including lower cost, better fault tolerance, improved scalability, and ease of hardware implementation.
SUMMARY OF THE INVENTION
The present invention is a technique for implementing a distributed queuing scheme and in particular a technique for determining priority of transmission among a number of cell queues within a traffic concentrator such as in an Asynchronous Transfer Mode (ATM) access node. In accordance with the invention, the access node permits the oldest queued cell to be asserted on the cell bus in any given time, taking also into consideration priority information as needed.
In order to accomplish this, the technique makes use of a binary count down contention bus that operates on a cyclic basis, with one bus period being allocated for each ATM cell. During each period, any queue having cells to be transmitted asserts the age of its oldest cell on the contention bus. The highest priority queue having the oldest cell is then permitted to assert its cell data on the next period on a separate traffic bus.
In the preferred embodiment, rather than calculating an age for each cell which would need to be reactivated on each bus cycle, a counter is included with each group of queues or line unit. The contents of the counter are saved with each cell in the queue. Therefore, when a cell is made available at the output end of a queue, the age of the cell can be determined by figuring the difference between the present counter value and the copy of the counter that was saved with the cell. There is, therefore, no need for various counters associated with various queues to be synchronized.
The contention bus is preferably a wire- or type inverted logic bus. The queues first assert the priority of their highest priority cell, sending the most significant bit first. The priority is binary encoded and inverted so that higher priorities will cause zeros on the bus and therefore win the contention because of the wire- or attachment. Once a queue sees a bit on the contention bus that is different from the bit that it is trying to assert, then that unit knows that a higher priority queue is contending. In this case, the lower priority queue removes itself from contention and does not try to contend for access again until the next period.
Next,

Affiliated with

Also associated with

Rating

Distributed FIFO queuing for ATM systems does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Distributed FIFO queuing for ATM systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed FIFO queuing for ATM systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2511717