Buffer associated with multiple data communication channels

Details Buffer associated with multiple data communication channels Buffer associated with multiple data communication channels

1999-12-17

2003-09-16

Gaffin, Jeffrey (Department: 2182)

Electrical computers and digital data processing systems: input/

Input/output data processing

Input/output data buffering

C710S001000, C710S003000, C710S005000, C710S033000, C710S035000, C710S053000, C710S054000, C710S055000, C710S056000, C710S057000

Reexamination Certificate

active

06622186

ABSTRACT:

CROSS-REFERENCE TO RELATED APPLICATIONS
This application is based upon and claims priority from prior French Patent Application No. 98-16156, filed Dec. 17, 1998, the entire disclosure of which is herein incorporated by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to electronic systems, and more specifically to a buffer for adapting the data flows exchanged between multiple communication channels.
2. Description of Related Art
An input channel and one or more output channels forming a communication channel are generally asynchronously processed intermittently, so that the input channel often provides data while the output channel is not ready to receive it, or conversely, the output channel is ready to receive data while the input channel provides none. It is thus necessary to adapt the data flows of these channels, which is generally done by using a buffer. The buffer stores any excess data that the output channel cannot accept at a given time and provides the data to the output channel when the channel becomes available.
FIG. 1
illustrates a buffer for adapting the flows of multiple input channels to multiple respective output channels. It can be, for example, a multi-protocol switch for switching multiple ATM connections on multiple Ethernet links. The buffer includes a DRAM
10
which, in high rate applications, is generally a synchronous DRAM (SDRAM). Memory
10
is managed by a memory controller
12
which processes the data exchanged between the ATM connections and the Ethernet links via adequate interfaces
14
.
One way of adapting the flows of multiple communication channels is to dedicate an area of fixed size in SDRAM
10
to each possible communication channel. This solution is far from being optimal from the point of view of the memory use, since a seldom required dedicated area cannot be used to relieve a very frequently required dedicated area. Thus, dedicated areas must be of maximum size to fulfill possible maximum requirements, although this maximum size will most often not be used. Further, in a switch, the number of open communication channels is variable, and they are practically never all in use at the same time. The areas dedicated to the non-open channels remain empty but are unusable for other channels.
FIG. 2
illustrates another solution for providing a buffer function to each of several possible communication channels. As illustrated, SDRAM
10
is organized in small blocks
16
of fixed size which are dedicated one by one to each communication channel according to needs. More specifically, each communication channel is associated with a chain of linked blocks
16
containing the data waiting for the corresponding output channel, with the chain forming a buffer of variable size. The blocks left free and not assigned to communication channels are listed in a queue of free blocks
18
also contained in memory
10
.
To manage this memory organization, memory controller
12
includes, for each possible communication channel, two pointers wbptr and W for the input channel, and two pointers rbptr and R for the output channel. Pointer wbptr points to the last block of the chain, that is, the block which is being filled. Pointer W points to the current writing location of this last block. Pointer rbptr points to the first block of the chain, that is, the block which is being emptied. Pointer R points to the current reading location of this first block. Further, controller
12
includes registers to enable managing of the queue of free blocks
18
. Queue
18
may be of the LIFO type (as shown), in which case one register containing a pointer “top” to the top of queue
18
is enough.
Initially, free block queue
18
is full, which signifies that all the blocks of SDRAM
10
are free and can be dedicated to communication channels. When a communication channel is opened, the free block found at the top of queue
18
, as indicated by pointer “top”, is dedicated thereto. Pointer “top” is decremented by one unit and the pointers wbptr and rbptr associated with the communication channel are both reset to point to the block just dedicated. At this time, pointers W and R point to the first element to be read from or mitten into the block. After writing a word into the block at the location indicated by pointer W, pointer W is incremented by one unit.
When the last location of the current block is reached by pointer W, a new block taken from the top of queue
18
at the location indicated by pointer “top” is dedicated to the communication channel. Pointer “top” is decremented by one unit, pointer wbptr is updated to point to the new block, pointer W is updated to point to the first location of the new block, and a descriptor of the block just filled is updated to chain to the new block. Thus, if the buffer needs for a communication channel increase, an increasing number of blocks can be used to form a chain, the length of which can increase to occupy the entire SDRAM or at least the entire space left free by the concurrent communication channels, if necessary.
The data to be sent to the output channel is read at the location indicated by pointer R in the block indicated by pointer rbptr. Upon each reading of a word, pointer R is incremented by one unit. When pointer R reaches the last location, pointer rbptr is updated to point to the next block of the chain. Pointer R is updated to point to the first datum to be transmitted in this block. The freed block is inscribed at the top of queue
18
, at location top+1. Pointer “top” is then incremented by one unit. Thus, as blocks are freed in a chain associated with a communication channel, these blocks become immediately available to all communication channels.
A problem which arises with such a memory organization is that a single immediate access to free block queue
18
is required. This is particularly impairing in access time when an SDRAM is used, because a minimal access to an SDRAM costs 8 clock cycles, only a single cycle of which is necessary for reading or writing a word. More specifically, there are three preload cycles, three addressing cycles, a read or write cycle, and a stop cycle. Further, free block queue
18
cannot be integrated in controller
12
as a memory accessible in a single cycle, because this queue is generally of too large a size for such an integration to be reasonable.
SUMMARY OF THE INVENTION
In view of these drawbacks, it is an object of the present invention to overcome the above-mentioned drawbacks and to provide a memory organization for a buffer that optimizes the accesses to a queue of free blocks contained in a DRAM with an access latency.
Another object of the present invention is to provide a method of managing a buffer for adapting the flows of multiple input channels to multiple respective output channels.
One embodiment of the present invention provides a buffer for adapting data flows from input channels to output channels. The buffer includes a DRAM organized in blocks and a memory controller for managing assignment of the blocks to the chains of linked blocks. The DRAM contains, as a chain of linked blocks, data associated with each communication channel formed by a pair of input and output channels, and also contains a main queue of free blocks for listing unoccupied blocks. The memory controller includes a cache memory containing a partial queue of free blocks that the memory controller uses in managing block assignment. According to one embodiment, when a level of the partial queue reaches a predetermined minimum limit the cache memory is at least partially filled by a burst from the main queue, and when a level of the partial queue reaches a predetermined maximum limit the cache memory is at least partially emptied by a burst into the main queue. According to another embodiment, the partial queue stores a local image of a top portion of the main queue, and the memory controller exclusively uses the partial queue in assigning blocks to the chains of linked blocks.
Another embodiment of the present invention provides

Affiliated with

Also associated with

Rating

Buffer associated with multiple data communication channels does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Buffer associated with multiple data communication channels, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Buffer associated with multiple data communication channels will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3026704