Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus interface architecture
Reexamination Certificate
2000-09-19
2004-11-16
Dang, Khanh (Department: 2111)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus interface architecture
C370S412000
Reexamination Certificate
active
06820162
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
This application is based upon and claims the benefit of priority from the prior Japanese Patent Application No. 11-273219, filed Sep. 27, 1999, the entire contents of which are incorporated herein by reference.
BACKGROUND OF THE INVENTION
This invention relates to a queue control device and a queue control method which are applied to, for example, ATM (Asynchronous Transfer Mode) communications and computers.
FIG. 7
shows a conventional queue management method. The queue management method includes a pointer table
101
having an n number of addresses and a storage area
102
that stores the head address and tail address for the queue in the pointer table
101
. When a queue is constructed for an n number of elements, address A0 to address An are allocated to the individual elements in the pointer table
101
. In each address in the pointer table
101
, pointer information indicating the next element for constituting the queue is stored. The storage area
102
stores the head address and tail address. The head address indicates the head element in the queue in the pointer table
101
and the tail address indicates the tail element. Using these addresses, the queue is managed.
For example, in the example of
FIG. 7
, address A0 in the pointer table has been stored in the head address in the storage area
102
and address A7 has been stored in the tail address. In address A0 in the pointer table
101
indicated by the head address, pointer information A2 indicating the address for the next element has been stored. Furthermore, pointer information A8 indicating the address for the next element has been stored in address A2 in the pointer table
101
and pointer information A7 indicating the tail address is stored in address A8 in the pointer table
101
. Since address A7 in the pointer table
101
is the tail address, it has not next pointer information and have 0 indicating the end of the queue stored in it. In this way, a queue consisting of addresses A0→A2→A8→A7 is constructed.
The queue is accessed sequentially, starting at address A0. After the process corresponding to address A0 has been completed, the pointer information corresponding to address A0 is deleted from the queue and the head address is updated from A0 to A2.
There are two methods of adding new elements to the queue as follows. When element Ai is added to an FIFO (First In First Out) queue, pointer information indicating Ai is stored in the tail address A7 of the pointer table
101
and the tail address of the storage area
102
is updated from A7 to Ai. On the other hand, when element Ai is added to an LIFO (Last In First Out) queue, pointer information indicating the head address A0 is stored in Ai of the table
101
and the head address of the storage area
102
is updated from A0 to Ai.
FIG. 8
shows a queue management method for managing two types of queues. To manage a first and a second queue, two storage areas
111
,
112
are provided. The storage area
111
holds the head address
1
and tail address
1
in the first queue. The first queue is managed using the head address
1
and tail address
1
. The storage area
112
holds the head address
2
and tail address
2
in the second queue. The second queue is managed using the head address
2
and tail address
2
.
Now, consider a case where queues are managed in a communication control system with, for example, an n number of communication channels. For example, in ATM communications, virtual channels are shared on one physical line, and packet is changed into ATM cell and transmits in the virtual channel. A bandwidth used by each virtual channel is classified into some groups corresponding to the application of each virtual channel, and each group is controlled according to a priority. That is, channels of each group are managed by the queue and each group is controlled according to the priority.
FIG. 9
shows the queue management method. In
FIG. 9
, a time table is provided in a storage area
121
. The time table has an m number of time entries T0 to Tm. Each channel is serviced in this order of T0 to Tm of the m number of entries. In each of the time entries T0 to Tm, the head address and tail address of a queue for a virtual channel serviceable at each time have been stored. For example, at time entry T0, Ah1-0 (=A0) has been stored in the head address and At1-0 (=A2) has been stored in the tail address. Moreover, at time entry T1, Ah1-1 (=A3) has been stored in the head address and At1-1 (=A3) has been stored in the tail address.
On the other hand, according to the head address and tail address at each of the entries, the pointer indicating the next element and information indicating the end have been stored in the pointer table
122
.
Each channel is served in order from time entry T0 in the time table. After service has been given at time entry Tm, service is given, starting at time entry T0 again. After the virtual channel registered in a certain entry has been given service, the virtual channel is registered in another time entry. If another virtual channel has been registered in that time entry, the virtual entry will constitute a queue at that time entry.
Consider a case where two types of virtual channels differing in priority are controlled in such a communication control device. As shown in
FIG. 9
, when there is only one queue at time entries T0 to Tm, control can be performed only by FIFO or LIFO. This causes a problem: the two types of virtual channels cannot be controlled independently on the basis of their priority.
To overcome this problem, as shown in
FIG. 10
, a queue control method having two sets of head addresses and tail addresses for each of the time entries T0 to Tm is needed. The method is based on the method shown in FIG.
8
. In the example shown in
FIG. 10
, there are a first queue and a second queue for each of the time entries T0 to Tm. With the first queue and second queue, two types of virtual channels differing in priority can be controlled as shown in the pointer table
122
. Specifically, for example, at time entry T0, the first queue specified by the head address Ah1-0 (=A0) and tail address At1-0 (=A2) is processed. Then, the second queue specified by the head address Ah2-0 (=A1) and tail address At2-0 (=A5) is processed.
As shown in
FIG. 10
, however, when two types of queues composed of the first queue and second queue are managed using the m number of time entries T0 to Tm, the storage area
123
requires an area for storing
4
×m head addresses and tail addresses. This leads to a problem: the storage capacity of the storage area
123
increases.
BRIEF SUMMARY OF THE INVENTION
It is, accordingly, an object of the present invention to overcome the above problem by providing a queue control device and a queue control method which are capable of preventing the storage capacity from increasing by controlling a plurality of queues as a single queue.
The foregoing object is accomplished by providing a queue control device comprising: a first storage area for storing a first and a second queue, the first queue including a plurality of elements, each of the elements having an address specifying the next element, and the second queue including a plurality of elements, each of the elements having an address specifying the next element; a second storage area for storing first pointer information and second pointer information, the first pointer information being a head address specifying the head element in the first queue, and the second pointer information being a tail address specifying the tail element in the second queue; and a controller which controls the first and second storage areas and which sets not only an address specifying the head element in the second queue in the tail element in the first queue stored in the first storage area but also an address specifying the tail address in the first queue in the tail element in the second queue and controls the first and second queues accordin
LandOfFree
Queue control device for and queue control method of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Queue control device for and queue control method of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Queue control device for and queue control method of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3285005