JPH0496546A - Queue buffer configuration system - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION [Summary] This invention relates to a queue buffer configuration method in a FIFO for writing and reading data of a predetermined length.

The purpose is to provide a queue buffer configuration method that can change the read order according to the processing priority of each cell while using a single queue.The buffer queue is configured in a single chain format using address inheritance and input. Add class information indicating processing priority to data, provide a write pointer table for each class indicating the buffer position where data is written, write input data to a free buffer, and chain the free buffer according to the data class. The configuration is configured so that it is inserted at a position within and reconnected.

[Industrial Application Field] The present invention is directed to an F that writes and reads data of a predetermined length.
This invention relates to a queue buffer configuration scheme within an IFO.

In recent years, future BISDN (Broadban)
dIntegrated 5 services Digi
AT as an elemental technology for constructing tal network)
M (85ynchronous TransferM
ode) is attracting attention.

An ATM switch generally consists of a queue buffer (hereinafter referred to as a queue) that stores fixed-length information packets called cells, a circuit that controls writing/reading of the buffer, and a line that connects multiple queues. F I FQ (First InFirst 0ut
), but the method of handling cell delivery delay time and cell discard rate within the switch is important.

“Conventional technology” FIG. 8 shows an example of the configuration of a conventional ATM switch.

This configuration uses Multi-5tage Self-Routing.
:MSSR) type switch is used.

To explain the outline of the operation in Fig. 8, the input highway (I
Each successive cell input from nput Iligbway is set to Hirch cell channel number
It consists of a header and information including lChannel Number (hereinafter referred to as VCN), and multiple cells
When input to N converter (referred to as VCC) 80, VC
C refers to a table (not shown) and converts the VCN into a tag (TAG) which is control information used for switching. The cell body and tag enter an initial self-routing module (SRM) 82 within the MSSR network 81 .

A switching unit 821 in this unit controls switching of input cells using tags generated by the vCC 80, and inputs the cells to a queue buffer 822 provided for each designated route. Cells written in a plurality of queue buffers 822 connected to a plurality of the same routes (links (LINKs) to the next stage module in this case) are sequentially read out, multiplexed by a multiplexer 823, and output to the next stage. , and so on for each S
Sequential switching is performed in RM82 and the final stage SRM
82 to the output highway.

Note that the call processing unit (Call Processing)
84 is a signal processing unit.
g) Receive signal information from 83 and control the tags of each CC.

As mentioned above, a conventional ATM switch uses a queue buffer that stores a fixed length information packet called one cell, and is generally configured using F, TPO.

Media stored in ATMlil include images,
There are various types such as voice and data, and the cell loss rate and allowable delay time for delivery differ depending on the required call quality. For example, in the case of audio and moving images, real-time performance is important, and delay time must be maintained within a certain period of time, but even if cells are discarded, there is little impact. On the other hand, in the case of data, if two cells are discarded, it becomes meaningless.
It has relatively little effect on delay time.

Therefore, the CCITT and others are considering a concept of guaranteeing the communication quality required for various media by defining a plurality of one communication class and adjusting the permissible values in the switch based on these definitions. The idea is that the communication class is expressed by a bit string displayed in the header of a cell by the sender, and the network recognizes this bit string and performs switching according to the above-mentioned allowable value.

[Problems to be Solved by the Invention] In conventional ATV switches, it is common to install one queue per input line and process multiple types of cells, that is, cells with different communication classes. This method has the problem that the required conditions cannot be met by improving the throughput of the switch or the performance of the entire switch by increasing the queue length, and the burden on the hardware increases dramatically. .

In contrast, the queues are divided and set up for each communication class,
One possible method is to equivalently change the allowable value by adding priority to read access to these queues. However, this method also does not solve the above problem because the amount of hardware in the queue increases depending on the communication class, and it is difficult to respond flexibly to traffic imbalance.

There is also a method of inserting a cell of a communication class with a high priority into the middle of a queue, but this is difficult to realize with a conventional simple FTFO that outputs cells in the order in which they are input.

SUMMARY OF THE INVENTION An object of the present invention is to provide a queue buffer configuration method that can change the read order according to the processing priority of each cell while using a single queue.

[Means to solve the problem] FIG. 1 is a diagram showing the principle configuration of the present invention.

In FIG. 1, 10 is a fixed-length information cell consisting of a header and information, and the header includes processing priority (communication type);
12 is a write pointer table storing write pointers for each class; 12 is a read pointer storage means; 13 is a write pointer table storing write pointers for each class;
14 is a free buffer pointer storage means, 14 is a write buffer that forms a queue for write buffers in the FIFO, and 15 is an empty buffer that forms a queue for free buffers in the FIFO.

The present invention adds class information representing processing priority to fixed length information, uses a single queue to store fixed length information, and stores information according to the priority order of each class. This is to rearrange the write buffer to a new location.

"Operation" Each buffer I4 forming the write buffer has a cell (header and information) written to it. At the beginning, the buffer address of the buffer following the own buffer is stored, and after that, the cell is stored. The buffer queue forms a chain in the form of address inheritance sequentially from the head to the last buffer.

The first buffer represents the buffer with the highest priority among the buffers that have not been read until now after the cell was written, and its buffer address is stored in the read pointer storage means 2. In addition, these queue buffers are ordered in order from the highest priority to the lowest priority for each class to form a chain.

Among cells of the same class, the cell that arrives first is placed in the earlier position (the position where it can be read earlier).

The buffer address of the last buffer to which cells of each class were written in the write buffer queue is stored for each class in the write pointer table 11 for each class, and the write buffer of that class is stored in correspondence with each class. A write flag (indicated by WF) is also set to indicate whether or not there is a write flag (“l l II” if written, “O” if not written). Class 2 indicates that the <latest> data is stored after itt of cell 1, and class 2 indicates that the last data is stored at buffer address C.

Additionally, a queue for free buffers 15 is provided.

The buffer address of the first empty buffer is stored in the empty buffer pointer storage means 13.

When a cell arrives, the free buffer pointer storage means 13
The first buffer 15 (
In the example shown in the figure, E) is acquired, and at the same time the free buffer pointer is updated to the next free buffer address (F in the figure).

The next cell that arrives is written to the acquired free buffer address.

On the other hand, the class of the cell is identified, the write pointer of the corresponding class is searched in the write pointer table 11, the storage address of the cell that arrived immediately before is known, and the buffer address at the beginning of the buffer to which the cell is to be taken over is set to the buffer address obtained above. Change to (E). Next, the address of the takeover destination before the change (original) of the buffer in which the cell that arrived immediately before was stored is set to the buffer address obtained above (
E) is stored as the takeover destination address at the beginning.

This allows a new buffer to be connected to the end buffer of each class, and maintains the continuity of the entire chain. Further, the pointer of the corresponding class in the class-by-class write pointer table 11 is updated to the pointer to which the new cell has been written.

In the read operation, each time a read request occurs, the read is read from the beginning of the written queue buffer indicated in the read pointer storage means 12, and at the same time, the contents of the read pointer are updated to the primary buffer address. Buffers after being read are chained to an empty buffer column.

An end mark is always inserted in the takeover destination address field of the buffer located at the end of the chain. During write and read operations, if an end mark (indicated by EM) is detected as the takeover destination address of an empty Harafah or read buffer, All operations stop. When forming a new chain, load the start address of a new buffer instead of the BM.

[Example] Figure 2 is a hardware configuration diagram of the example, Figure 3 is the initial setting operation sequence, Figures 4(a) and 4(b) are the write operation sequence, and Figure 5 is the read operation. In the sequence, FIG. 6 shows an example of the configuration of a loaded buffer column, and FIG. 7 shows an example of the configuration of an empty buffer column.

The hardware configuration diagram in FIG. 2 shows two main configurations necessary to implement the present invention.

20 is free buffer pointer memory (displayed in EPM)
, 2] is the write pointer memory (indicated by WPM),
22 is a read pointer register (indicated by RPR), 2
3. 24 is a selector (indicated by SEL), 25 is a memory where a free buffer queue and a write buffer queue are formed, 26 is a memory control circuit that controls reading and writing to the memory, and 27 is initializing the memory. Reset circuit, 28 is empty buffer address latch, 29 is loading method buffer address latch, 30 is takeover buffer address latch, 31-1 to 31-3 are comparison circuits (C
OMP), 32 is a control section that controls the operation of each section.

The empty buffer pointer memory (EMP) 20 stores an empty buffer pointer (ERP), which is the first address of the empty buffer string, and an empty buffer loading pointer (EWP), which is the last address of the empty buffer string. In the memory (WPM) 21, a class-specific put pointer (WP) and a loading flag are written for each class. Further, the read pointer register 22 stores the buffer address of the head of the written queue buffer (buffer address with the highest read priority at the present time).

Using the configuration shown in FIG. 2, each operation sequence controlled by the control section 32 will be explained with reference to FIGS. 3 to 5.

FIG. 3 shows the initial setting operation sequence.

When an initialization request is generated for the first time, an initialization signal is generated from the control unit 32, and a class-specific placement pointer WP (second
21 WPM in the figure) are all set to 0, all loading flags are turned off, and then the read pointer (2nd
Write EM (end mark) in RP22 (inside the figure),
Free buffer pointer (EPR in EPM20 in Figure 2)
) is written as ``00°'', and the initial value of the address of the next empty buffer is written into the empty buffer address ``oo'' (300 to 303 in FIG. 3).

Next, it is determined whether the takeover address (write address) written to the free buffer has reached the specified value (the last address assigned to the free buffer) (step 304), and if it has not reached it, step 305 ~3
In step 07, empty buffer chains are sequentially formed. At that time, the takeover address + fixed value is written as write data (takeover destination address).

In this way, when the write address (the beginning of the free buffer) reaches the specified value, data "EM" is written to the write address, and the free buffer loading pointer (EP in Figure 2) is written to the write address.
Write the specified value to the register EWP (not shown) that constitutes M20 and return (308, 3).
09,310).

FIG. 7 shows an example of the structure of the empty buffer row formed in this manner. As shown in the figure, the free buffer loading pointer (EWP) holds the last buffer address of free buffers, and the free buffer pointer (ERP) holds the buffer address of the beginning of the free buffer string (initial value is 00). do.

Next, the write operation sequence when a cell is input will be explained using FIGS. 4(a) and 4(b) and with reference to FIGS. 6 and 7.

When a cell arrives, the free buffer pointer (ERP) is read (402 in FIG. 4(a)). At this time, in the example of FIG. 7, "C" (buffer address) is read out as data. It is determined whether the acquired free buffer is valid (whether the read data is not "'B M") (403). In the case of "'EM", the processes from step 404 to be described later are performed, but if valid (in the case of "C"), the contents of the address "'C°" are read (step 41o). In this example, "D'" is obtained as the data (takeover address) of the buffer at address "C" (this is the empty buffer address latch 28 in FIG. 2).
).

Next, the data ladder "D" is written to the empty buffer pointer ERP (inside 20 in FIG. 2) (411 in FIG. 2).

This 'D' is used as the write destination for subsequent cells.

Next, extract the class information of the input cell.

Using the class, the class-by-class put pointer and the load flag are taken out from the write pointer memory (WPM 21 in FIG. 2) (412). In the example shown in FIG. 6, when the class is "M", the data whose write pointer is "A'' and whose loading flag is on (°"1'') is retrieved.

Next, it is determined whether the loading flag is on (413) to see if there is a write buffer for the class. If it is on, it is known that the cell of this class has been previously written (before being read). If it is off, although not shown, the write pointer WP whose upper class flag is on is read out, the takeover destination address of the buffer at that address is taken out, and written as the takeover destination address of the buffer at address 〛C'' obtained above. , ■ to proceed to step 416, which will be described later.

If the loading flag is on in step 413, the contents of the buffer address "A°" (read in step 412) written at the end of the cell of this class (assumed "M") are read out (step 414).

As a result, in the example shown in FIG. 6, "B" is read as the takeover destination address. This transfer destination address “B”
゛ is the address ゛C° which is the free buffer acquired earlier
It is written as the takeover destination address in the buffer of "'" (415). In this way, the buffer of address "B" is connected after the buffer of address "'C".

Thereafter, the process moves to FIG. 4(b) according to (2), and the arrived cell information (fixed length) is written into the empty buffer (address "C") that has already been acquired (416).

Furthermore, data ``'C''° is written to the corresponding class of the write pointer memory (WPM) (417).If the loading flag was off before, 1 is set to on, and the data ``' is set as the destination address of address ``A''.
Write C゛ (418). This allows the address “
The buffer at address "Coo" is connected after the buffer at 'A', and the write pointer is updated.

Next, the read pointer RP (FIG. 2, 22) is read, and it is determined whether the contents match the EM (end mark). If they match, "'C" is written to the read pointer (steps 419 and 420). ).This is to read from address C as the first address when the read pointer stops after reading to the last buffer.

In the above step 403, if there is no free buffer (ERI-EM), the class-specific put pointer (WP) corresponding to the class displayed by the arriving cell is read out (404), and the read buffer address ( "A'"
``), the transfer destination address of the corresponding buffer is read (405). In this example, it is assumed that the address address B'' is obtained. It is determined whether or not this "B" is an EM (406). If it is an EM, the arrived cell is discarded as there is no buffer to write the arriving cell (409). If it is not EM, the arrived cell information is written twice into the hunted buffer (address "B") and the previous information is erased (407). Next, write data ''B' to the write pointer memory WPM, and at the same time turn on the loading flag of the corresponding class (408)
. The operations in steps 404 to 409 above are executed in class M displayed by the cell.

In addition, the operation of step 408 (writing data 'B') is performed for all write pointers WP of classes M and below and whose loading flags are inactive (off).

However, if there is one whose flag is already on, write pointers WP of this class or lower are excluded. Priorities between classes are preserved by the following operations.

Next, the read operation sequence shown in FIG. 5 will be explained.

When a read request occurs, the read pointer (RP)
(501 in FIG. 5). In the example shown in FIG.
M) or not, and if it is empty, it ends, and if there is data (in the case of address "E"), the cell information (data after the takeover address) is retrieved from the loading (written) buffer at that address. Read out (503). The read data is output from the memory 25 in FIG. 2 as data OUT.

After this, compare the contents of the class-specific put pointer WP with the above data (address 'E'), and if it fails, it is the last write buffer of this class, so the flag is turned off for loading of this class (the same 505, 506).

Next, take over the address (“Eoo)”
F") is written to the read pointer RP to update the read address (507). Then, data ""E M" is written to the address ゛'E"° (50
8).

This is a preparation to incorporate the read buffer at the end of the free buffer, and then reads the contents of the free buffer loading pointer EWP (see Figures 3 and 7), and reads the address data (in the example of Figure 7). “c”) and (
509), writes the address "'E"' of the last buffer to be added as the destination address of the buffer at this address ("G") (510).Finally, write the address to the empty buffer loading pointer EWP. “
Eo'' is written (511) and the last empty buffer position is displayed.

” 1 write in double operation, 1 in read operation,
Both the free pointer and the read pointer stop when they each display an end mark (EM). For this purpose, EM is always inserted into the takeover destination address field of the buffer located at the end of the chain. When forming a new chain.

The starting address of each pointer is loaded.

The communication-specific placement pointer is updated each time a cell arrives; however, once a cell of the class is no longer in the loaded buffer, the next time a cell of the class arrives, the cell in the class higher than the class will be updated. The write pointer of the lowest class which is in the loaded state is used to perform the connection operation of the buffer.

As described above, processing priority for each class is guaranteed, and delay time and discard characteristics are improved for cells with high priority.

[Effects of the Invention] According to the present invention, processing priority (communication type) can be added to each cell by using a single matrix, so that it is possible to add a processing priority (communication type) to each cell using a single matrix. It is possible to satisfy the function using . In addition, since cells with multiple types of communication classes can be processed at once, it is possible to flexibly deal with imbalances in traffic between one communication class, and the loss of buffer division (the burden of dividing and managing buffers) is alleviated. can.

[Brief explanation of the drawing]

Figure 1 is a diagram of the principle configuration of the present invention, Figure 2 is a hardware configuration diagram of an embodiment, Figure 3 is an initial setting operation sequence, and Figures 4(a) and 4(b) are write operation sequences. , FIG. 5 shows the read operation sequence. 6 shows an example of the configuration of a loading buffer line, FIG. 7 shows an example of the configuration of an empty buffer line, and FIG. 8 shows an example of the configuration of a conventional ATM switch. 10 in Figure 1: Fixed length information cell 11: Write pointer table by class 12: Read pointer storage means 13: Free buffer Pointer storage means 14: Write buffer 15: Free buffer

Claims (4)

[Claims] (1) FI that writes and reads data of a predetermined length
In the queue buffer configuration method in FO, the buffer sequence is configured in a single chain format by taking over addresses, and class information indicating processing priority is added to the input data, and class information indicating the buffer position where the data is written is added. A write pointer table (11) is provided, input data is written to an empty buffer (15), and the input data is written to the empty buffer (15).
5) is inserted into a position in the chain according to the class of data and reconnected. (2) In a queue buffer configuration method in a FIFO that stores and reads cells of a predetermined length consisting of a header and information, class information indicating processing priority is added to the header of each cell, and classes with high priority are added to the header of each cell. A queue buffer in which cells are written in a single chain format by taking over addresses sequentially from the beginning, a write pointer table (11) that stores the position of the rear end of the cell write buffer for each class, and an empty buffer pointer storage means that indicates the empty buffer position. (13), and a read pointer storage means (12) updated by taking over the address of the write queue buffer, writes an input cell to an empty buffer (15), and creates a write pointer table corresponding to the class of the cell. A queue buffer configuration method characterized by using a queue buffer and reconnecting it into a queue buffer. (3) The queue buffer configuration method according to claim (2), further comprising empty buffer pointer storage means (13) for holding empty buffers into which input cells are to be written in a chain format. (4) Claims (1) to (3) provide that the class-specific write pointer table (11) stores a loading flag indicating that cells of each class have been written but reading has not yet been completed. Features a queue buffer configuration method.