Linked list based least recently used arbiter

Details Linked list based least recently used arbiter Linked list based least recently used arbiter

1998-05-27

2002-09-03

Nguyen, Chau (Department: 2663)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S416000

Reexamination Certificate

active

06445680

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to data communication networks and more particularly relates to a least recently used (LRU) arbiter based on a linked list mechanism.
BACKGROUND OF THE INVENTION
Currently, there is a growing trend to make Asynchronous Transfer Mode (ATM) networking technology the base of future global communications. ATM has already been adopted as a standard for broadband communications by the International Telecommunications Union (ITU) and by the ATM Forum, a networking industry consortium.
Asynchronous Transfer Mode
ATM originated as a telecommunication concept defined by the Comite Consulatif International Telegraphique et Telephonique (CCITT), now known as the ITU, and the American National Standards Institute (ANSI) for carrying user traffic on any User to Network Interface (UNI) and to facilitate multimedia networking between high speed devices at multi-megabit data rates. ATM is a method for transferring network traffic, including voice, video and data, at high speed. Using this connection oriented switched networking technology centered around a switch, a great number of virtual connections can be supported by multiple applications through the same physical connection. The switching technology enables bandwidth to be dedicated for each application, overcoming the problems that exist in a shared media networking technology, like Ethernet, Token Ring and Fiber Distributed Data Interface (FDDI). ATM allows different types of physical layer technology to share the same higher layer—the ATM layer.
More information on ATM networks can be found in the book “ATM: The New Paradigm for Internet, Intranet and Residential Broadband Services and Applications,” Timothy Kwok, Prentice Hall, 1998.
ATM uses very short, fixed length packets called cells. The first five bytes, called the header, of each cell contain the information necessary to deliver the cell to its destination. The cell header also provides the network with the ability to implement congestion control and traffic management mechanisms. The fixed length cells offer smaller and more predictable switching delays as cell switching is less complex than variable length packet switching and can be accomplished in hardware for many cells in parallel. The cell format also allows for multi-protocol transmissions. Since ATM is protocol transparent, the various protocols can be transported at the same time. With ATM, phone, fax, video, data and other information can be transported simultaneously.
ATM is a connection oriented transport service. To access the ATM network, a station requests a virtual circuit between itself and other end stations, using the signaling protocol to the ATM switch. ATM provides the User Network Interface (UNI) which is typically used to interconnect an ATM user with an ATM switch that is managed as part of the same network.
Prior Art Source Queue Arbitration
The environment of the present invention is a data communications network. In a data communications network, data is transferred from end to end, i.e., from source to destination, in data units. Different types of networks give their data units different names. For example, the data units in Ethernet networks are called frames, in ATM networks the data units are called cells and in TCP/IP networks the data units are called packets. A packet (or frame, cell, etc.) is defined as a part of a message that the higher level software application desires to send from a source to a destination or several destinations. In addition, messages can be sent from multiple sources to the same destination.
Each network equipment device has means by which several sources of input data may be destined to the same destination. To manage the flow of data, each destination output has associated with it a queue and some form of control means which functions to manage to flow of data from each of the data sources into the queue. The control means that is utilized in many devices is called an arbiter. It is preferable that the arbiter decide the order in which the data sources load data into the destination queue in a manner that is fair. The decision as to which source should transmit data to the destination queue should preferably also be made as quick as possible in light of (1) the potentially large number of sources vying for the same destination queue and (2) the high data rate of the traffic being carried over the network.
A block diagram illustrating the data flow between multiple sources of data and a destination queue whereby the flow of data to the queue is controlled by an arbiter is shown in FIG.
1
. The arbiter portion, generally referenced
10
, of the network device comprises a plurality of input data sources labeled input source #
1
through input source #N, a plurality of source queues
12
labeled source queue #
1
through source queue #N, an arbiter
14
, backpressure information source
16
and a destination queue
18
.
Each input source transmits data to its corresponding source queue. Each source queue sends both data
20
and an empty flag
22
indicating that the particular source queue is empty. The arbiter receives the data and empty flags from all the source queues and outputs data to the destination queue in accordance with its arbitration scheme. The destination queue transmits data to one or more output ports. The backpressure information source
16
provides backpressure information from downstream processing elements, such as the switching fabric or output ports, to the arbiter.
The explosive growth in networks and the pressing drive for faster data rates is resulting in a larger number of data sources vying to send data to any one destination port. Thus, designers of network equipment are searching for solutions that enable the management of source queues in an intelligent manner such that selection decisions are made at high speed and in a manner fair to the plurality of input data sources. Previous to the recent growth in network use with the high demand for higher speeds and larger bandwidths, the management of input source queues did not create a bottleneck in the flow of network traffic. Thus, a relatively simple and straightforward technique was used.
A description of a prior art implementation of a fair arbitration scheme among several input data sources will now be presented. Diagrams illustrating a prior art source index queue used to determine the order of access to a destination queue by multiple data sources is shown in
FIGS. 2A
,
2
B and
2
C. In this type of prior art arbiter implementation, a source index queue
30
is created which includes a plurality of index numbers
32
with each index number corresponding to an input source queue. In addition, the queue includes an indication
34
of the status of each input source queue.
When the arbiter wants to retrieve data from one of the input queues, it cycles through the entries in the source index queue
30
, beginning from the top of the queue, searching for the first input source entry that has data, i.e., a packet, available for transmission to the output destination queue. An input source queue that has data ready to transmit has its data ready indication
34
set to a ‘1’. Once a source is selected, its corresponding index number is placed at the end of the source index queue
30
and the other index numbers above it are pushed up one position.
With reference to
FIGS. 2A and 2B
, it is assumed that there are N sources and one destination. Initially, the order of the contents of the index queue corresponds to the order of the N input source queues, i.e., source #
1
, #
2
. . . #N. An additional bit
34
indicates whether the source has a packet available to transmit to the destination. Note that this bit can be set to ‘0’, i.e., unavailable, due to an empty source queue or due to backpressure from the destination, indicating that this particular source queue is not permitted to send packets.
Now assume, for example, that source #
5
is the first source in the index queue with its data ready

Affiliated with

Also associated with

Rating

Linked list based least recently used arbiter does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Linked list based least recently used arbiter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linked list based least recently used arbiter will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2837722