System and method for assigning time slots in communication system and network-side apparatus used therefor

The present invention comprises a plurality of terminal-side apparatuses each having a buffer, a queue length notification module, and an output control module, and a network-side apparatus having a fairness guarantee/high efficiency hybrid time slot assignment control module (FG/HE HTSAC module). The FG/HE HTSAC module assigns time slots to all or a part of the terminal-side apparatuses in accordance with a fairness criteria. If the number of the time slots assigned exceeds a queue length for one or more terminal-side apparatuses, leftover time slots are reassigned among the terminal-side apparatus(es) where the number of the time slots assigned thereto does not exceed a queue length. The result of reassignment is notified to an output control circuit that controls output of cells from the buffer.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a network-side apparatus in a communication system as well as a system and a method for assigning time slots by such a network-side apparatus. More specifically, the present invention relates to a method for dynamically assigning, by a network-side apparatus, time slots to terminal-side apparatuses through a shared media over a point to multipoint communication system on the basis of fluctuating traffic.

2. Description of the Related Art

Point to multipoint shared media communication systems comprise a single network-side apparatus connected to a plurality of terminal-side apparatuses. The terminal-side apparatuses share one or more physical media (channels) . In other words, the shared physical medium is passively split among multiple terminal-side apparatuses that share the capacity of that medium. Such systems are expected to provide access networks at low costs. Asynchronous Transfer Mode-Passive Optical Networks (ATM-PONs) are an example of the point to multipoint shared media communication system.

FIG. 1shows an ATM-PON system comprising four terminal-side apparatuses100to130and a single network-side apparatus140. The network-side apparatus140in this system is connected to the terminal-side apparatuses100to130through two kinds of transmission lines in order to allow transmission of upstream signals from the terminal-side apparatuses100to130to the network-side apparatus140. More specifically, each of the terminal-side apparatuses100to130is connected to an optical splitter/combiner160through individual transmission lines150to153, respectively. The optical splitter/combiner160is connected in turn to the network-side apparatus140through a common transmission line (hereinafter, referred to as a “shared transmission line”)170. In order to avoid a collision of data (hereinafter, referred to as “cells”) on the shared transmission line, the terminal-side apparatuses100to130each uses time slots assigned thereto by the network-side apparatus140, while the terminal-side apparatuses100to130shares one frequency band and the network-side apparatus140uses a different frequency band.

There are many possibilities in the choice of bandwidth allocation strategy. Of these, assignment of time slots to the terminal-side apparatuses100to130on a fixed assigned basis is simple to achieve but it prevents efficient use of the bandwidths for the shared transmission line170when the terminal-side apparatuses generate bursty traffic of cells. This is because a fixed number of time slots are equally assigned to all terminal-side apparatuses regardless of fluctuation of traffic demands. Such inefficiency stands out more in systems with highly bursty traffic where each terminal-side apparatus makes communications over a best-effort service such as the Internet.

In order to make efficient use of the shared transmission line170, the network-side apparatus140must assign the time slots dynamically on the basis of traffic conditions to the terminal-side apparatuses100to130. In addition, since the channel capacity of the shared transmission line170is shared by a plurality of terminal-side apparatuses100to130, it is also necessary to achieve fair bandwidth assignment to the terminal-side apparatuses100to130.

A method for controlling assignment of time slots over a point to multipoint shared media communication system will be described in conjunction withFIG. 1. The terminal-side apparatus100comprises a buffer101, a queue length notification module102, and an output control module103. The buffer101is connected to the queue length notification module102and the output control module103. The buffer101is also connected to terminals180and181to store the incoming cells from the terminals. The queue length notification module102monitors a queue length (i.e., the number of cells stored in the buffer101) and supplies information indicative of the queue length to the network-side apparatus140. The output control module103controls transmission of cells from the buffer101. While not being described individually, it is understood that the terminal-side apparatuses110,120, and130each comprises a similar configuration to that of the apparatus100.

The network-side apparatus140comprises a dynamic time slot assignment control module141for use in determining assignment of the time slots to the terminal-side apparatuses100to130. The system comprises a downstream transmission line190in order to allow transmission of downstream control signals, especially information indicative of assignment of the time slots, from the network-side apparatus140to the terminal-side apparatuses100to130. While the downstream transmission line190illustrated inFIG. 1connects the network-side apparatus140only with the terminal-side apparatus100, it is apparent that the downstream transmission line190also connects the remaining terminal-side apparatuses110to130with the network-side apparatus140.

There may be another system without the downstream transmission line190. In this system, the information indicative of the time slot assignment is transmitted through the shared transmission line170and the individual transmission lines150to153, from the network-side apparatus140to the terminal-side apparatuses100to130.

With the above-mentioned configurations, cells are transmitted from the terminal-side apparatuses100to130to the network-side apparatus140in the manner described below.

Cells supplied from the terminals180and181to the buffer101are stored in the buffer101. The queue length notification module102monitors the queue length and periodically supplies information indicative of the queue length to the network-side apparatus140. The information indicative of the queue length is herein referred to as “queue length information”. The dynamic time slot assignment control module141in the network-side apparatus140determines, in accordance with the queue length information, the number and position of the time slots to be assigned each terminal-side apparatus. The dynamic time slot assignment control module141supplies the information indicative of the number and position of the time slots to the output control modules103in the terminal-side apparatuses100to130through the downstream transmission line190. The information indicative of the number and position of the time slots is herein referred to as “timeslot assignment information” for short.

The output control module103in the terminal-side apparatus transmits the cells in the buffer101to the network-side apparatus140in response to the timeslot assignment information. The cells from the terminal-side apparatuses100to130are transferred to a station (not shown) through the individual transmission lines150to153, the optical splitter/combiner160, the shared transmission line170, the network-side apparatus140, and the transmission line191.

The dynamic time slot assignment control module141in the network-side apparatus140determines whether there is any terminal-side apparatus in which the queue length exceeds the threshold value. If any, the network-side apparatus140divides the time slots into N number of slot groups and assigns the time slots on an equal basis to the N number of terminal-side apparatuses (wherein N represents the number of the terminal-side apparatuses in which the queue length exceeds the threshold value) to provide fair distribution of the time slots among the terminal-side apparatuses. The network-side terminal140then supplies information indicative of the assigned number of the time slots for each terminal-side apparatus through the downstream transmission line190. The above-mentioned procedure to assign the time slots dynamically and fairly by the network-side apparatus to the terminal-side apparatuses is disclosed in, for example, Japanese Patent Laid-Open No. 10-242981.

Next, an example of this dynamic assignment will be described referring toFIG. 2. InFIG. 2, the queues in the buffers in the terminal-side apparatuses100,110,120, and130have the lengths of 10, 50, 40, and 0, respectively. It is assumed that the threshold value is zero and the total number of the time slots available for the terminal-side apparatuses is 60. As mentioned above, the time slots are assigned only to the terminal-side apparatus(es) where the queue length exceeds the threshold value. Therefore, assignment is made to the terminal-side apparatuses100,110, and120in the illustrated example. The dynamic time slot assignment control module141divides the sixty time slots into three slot groups, twenty for each. Subsequently, dynamic time slot assignment control module141assigns the time slots equally to the terminal-side apparatuses100,110, and120. As a result, the terminal-side apparatuses100,110,120, and130are assigned with 20, 20, 20, and 0 numbers of the time slots. The hatched bar inFIG. 2corresponds to the slot group containing equally assigned time slots.

As apparent from the above, the N number of terminal-side apparatuses where the queue length exceeds the threshold value are subject to equal assignment of the available time slots. This allows fair assignment of the time slots. However, it would lead to low bandwidth utilization levels when there is one or more terminal-side apparatuses to which time slots are assigned over their queue length. For example, the terminal-side apparatus100is assigned with the twenty time slots while the queue length therein corresponds to ten cells. Such “over-assignment” may deteriorate bandwidth utilization levels on the shared transmission line.

Therefore, an object of the present invention is to provide a system and a method for assigning time slots with which a network-side apparatus can assign time slots dynamically and fairly to terminal-side apparatuses by efficiently using bandwidths of a shared transmission line.

Another object of the present invention is to provide a network-side apparatus applicable to the above-mentioned system and method.

SUMMARY OF THE INVENTION

In the present invention, a plurality of terminal-side apparatuses are connected to a network-side apparatus through a shared transmission lines. The network-side apparatus is adapted to assign time slots to the terminal-side apparatuses. The terminal-side apparatus is adapted to transfer packets or cells to a transmission medium by using the time slots assigned to it.

Each terminal-side apparatus comprises buffering means for use in storing a packet to be transferred, and notification means for notifying the network-side apparatus of the number of packets stored in the buffering means.

The network-side apparatus receives, from the terminal-side apparatuses, information indicative of the number of packets stored in the buffering means in the terminal-side apparatuses. In response to this information, the network-side apparatus assigns time slots to the terminal-side apparatuses in accordance with a predetermined fairness criteria. Subsequently, the network-side apparatus determines whether there is a terminal-side apparatus with a time slot or slots excessively assigned. If it does, the network-side apparatus makes the excessive time slots be a subject of reassignment. The network-side apparatus further comprises control means for use in reassigning the time slots to one or more terminal-side apparatuses (herein referred to as an “available terminal-side apparatus for reassignment”) except for those with the excessive time slots (herein referred to as a “non-available terminal-side apparatus for reassignment”).

As apparent from the above, according to the present invention, the control means in the network-side apparatus first assigns the time-slots to the terminal-side apparatuses in accordance with the fairness criteria. If this results in over-assignment of the time slots, the network-side apparatus reassigns the leftover time slots to the terminal-side apparatus(es) . The assignment and reassignment guarantees fairness among the terminal-side apparatuses and allows efficient assignment of the time slots.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

A first embodiment of the present invention will be described with reference to the drawings.FIG. 3shows a point to multipoint shared media communication system for use in implementing time slot assignment according to the present invention. This point to multipoint shared media communication system comprises a fairness guarantee/high efficiency hybrid time slot assignment control module (hereinafter, referred to as “FG/HE HTSAC module”)341in place of the dynamic time slot assignment control module141shown inFIG. 1. InFIG. 3, similar components and parts to those described in conjunction withFIG. 1are represented by the same reference numerals and description of such components is omitted.

Now, operations of the communication system configured as illustrated inFIG. 3will be described. The terminal-side apparatuses100to130receive incoming cells from the terminals180and181and transfer them to FG/HE HTSAC module341in the network-side apparatus140. This transfer is similar to that achieved by the conventional communication system described above. The FG/HE HTSAC module341in the network-side apparatus140receives the queue length information from the queue length notification modules in the terminal-side apparatuses100to130. In response to the queue length information, the FG/HE HTSAC module341in the network-side apparatus140computes, according to the following procedures, the number of the time slots to be assigned to the terminal-side apparatuses100to130. The network-side apparatus140then produces information indicative of the number of the time slots to be assigned to each of the terminal-side apparatuses100to130. The assignment information is supplied to the terminal-side apparatuses100to130through the downstream transmission line190.

FIG. 4is a flow chart used by the FG/HE HTSAC module341in the network-side apparatus140to assign the time slots to the terminal-side apparatuses. At step400, the FG/HE HTSAC module341assigns the time slots to the terminal-side apparatuses100to130on the basis of the fairness criteria. The fairness criteria as used herein means criteria for fairness applied to distribute the time slots to the terminal-side apparatuses with fairness.

For example,FIG. 5gives different fairness criteria:The FG/HE HTSAC module341assigns time slots equally to the terminal-side apparatuses100to130;The FG/HE HTSAC module341assigns time slots in proportion to the sum of guaranteed minimum bandwidths for the connections in the terminal-side apparatuses100to130;The FG/HE HTSAC module341assigns time slots in proportion to the sum of maximum band widths for the connections in the terminal-side apparatuses100to130;The FG/HE HTSAC module341assigns time slots in proportion to the difference between the sum of maximum bandwidths and the sum of guaranteed minimum bandwidths for the connections in the terminal-side apparatuses100to130;The FG/HE HTSAC module341assigns time slots in proportion to the number of connections in the terminal-side apparatuses100to130; andThe FG/HE HTSAC module341assigns a part of total time slots equally to the terminal-side apparatuses100to130and then assigns the remaining time slots in proportion to the sum of guaranteed minimum bandwidths, the sum of maximum bandwidths, the difference between the sum of maximum bandwidths and the sum of guaranteed minimum bandwidths for the connections in the terminal-side apparatuses100to130, or in proportion to the number of connections.

The assignment performed at the step400on the basis of the fairness criteria is hereinafter referred to as the “primary assignment”. The time slots assigned per terminal-side apparatus during the primary assignment is hereinafter referred to as the “primarily assigned time slots”. At step401, the FG/HE HTSAC module341determines whether or not reassignment should be performed for efficiency improvement. More specifically, the FG/HE HTSAC module341compares, for each terminal-side apparatus, the number of the primarily assigned time slots with the queue length. If there is any terminal-side apparatus where the number of the primarily assigned time slots exceeds the queue length, the difference between them is designated as a primary leftover time slot or slots. The FG/HE HTSAC module341performs reassignment of the primary leftover time slot(s) for efficiency improvement in order to avoid deterioration of bandwidth utilization levels. This operation is herein referred to as the “primary reassignment” for the purpose of clarity.

On the contrary, if the number of the primarily assigned time slots is smaller than the queue length for all terminal-side apparatuses100to130, then process goes to the operation at step405without reassignment. This is because fairness is assured among the terminal-side apparatuses100to130and there is no over-assignment of the time slots, indicating that the available bandwidth is fully utilized.

If the step401is positive, the FG/HE HTSAC module341determines, at step402, to which terminal-side apparatus or apparatuses the primary leftover time slot(s) should be reassigned. The primary leftover time slot(s) can be assigned to the terminal-side apparatus with the primarily assigned times lots smaller than the queue length. Such a terminal-side apparatus is herein referred to as the “available terminal-side apparatus for reassignment”. The remaining terminal-side apparatus is herein referred to as the “non-available terminal-side apparatus for reassignment”.

At step403, the FG/HE HTSAC module341determines the number of the primary leftover time slots. If there are two or more non-available terminal-side apparatuses for reassignment, the number of the time slots to be reassigned is the sum of the primary leftover time slots in these apparatuses. After the determination of the primary leftover time slots, the queue length is used as the number of the time slots assigned to the non-available terminal-side apparatus for reassignment.

At step404, the FG/HE HTSAC module341carries out the primary reassignment for efficiency improvement. More specifically, the FG/HE HTSAC module341assigns the primary leftover time slots to the available terminal-side apparatus (es) for reassignment. The reassignment may be made using various algorithms, and some of which are indicated inFIG. 6. The algorithms shown inFIG. 6are:assignment based on the fairness criteria used in the primary assignment (see,FIG. 5) for reassignment (Fairness algorithm);queue length averaging assignment such that the value obtained by subtracting the number of the primarily assigned time slots from the queue length becomes equal or similar to each other in the available terminal-side apparatuses for reassignment (Distributed Minimum algorithm); andassignment of the time slots in proportion to the queue length in the available terminal-side apparatuses for reassignment (Packet Ratio algorithm).

After the step404, operation of the FG/HE HTSAC module341returns to the step401inFIG. 4. It is noted that the number of the total time slots assigned to the available terminal-side apparatus(es) may exceed the queue length therein after the primary reassignment. In such a case, the FG/HE HTSAC module341designates an excessive time slot or slots as a secondary leftover time slot or slots and repeats the procedures from the step402to reassign the secondary leftover time slots to the terminal-side apparatus(es). This operation is herein referred to as the “secondary reassignment”. More specifically, the FG/HE HTSAC module341determines whether there is any terminal-side apparatus with the number of time slots exceeding the queue length (step401). If the step401is positive, the FG/HE HTSAC module341designates the corresponding terminal-side apparatus as the non-available terminal-side apparatus for reassignment. The FG/HE HTSAC module341designates the queue length in that non-available terminal-side apparatus for reassignment as the number of the time slots assigned thereto. Subsequently, the FG/HE HTSAC module341determines the number of the second leftover time slots, that is, the difference between the queue length and the number of the time slots already assigned during the primary assignment and the primary reassignment (step403) Thereafter, the FG/HE HTSAC module341performs the secondary reassignment (step404) In this way, the FG/HE HTSAC module341repeats the above-mentioned procedures until the number of the total time slots assigned becomes equal to or smaller than the queue length for all terminal-side apparatuses.

Finally, at the step405, the FG/HE HTSAC module341determines the final number of the time slots assigned to each terminal-side apparatus. If the primary (secondary) reassignment has been performed for efficiency improvement, the FG/HE HTSAC module341sums up, as the final number of the time slots assigned for a terminal-side apparatus, the primarily assigned time slots and the portion of the leftover time slots assigned to that apparatus during the primary and secondary reassignments. On the other hand, if reassignment is not performed, the number of the primarily assigned time slots obtained at the step401is determined as the final number of the time slots.

It is noted that no terminal-side apparatus may become available for reassignment before completion of the operation even though one or more time slots still remain without being assigned. In such a case, the FG/HE HTSAC module341assigns all of the remaining time slots to all terminal-side apparatuses according to the fairness criteria used at the step400.

FIG. 7shows an example of assignment achieved using the above-mentioned procedure. InFIG. 7A, the queues in the buffer101in the terminal-side apparatuses100,110,120, and130have the lengths of 10, 50, 40, and 0, respectively. InFIG. 7C, the queues in the buffer101in the terminal-side apparatuses100,110,120, and130have the lengths of 30, 50, 40, and 0, respectively. It is assumed that the total number of the time slots available for the terminal-side apparatuses is 60. Under such circumstances, the time slots are to be assigned to the terminal-side apparatuses100,110, and120. The terminal-side apparatus130is not subjected to assignment because the queue length does not exceed the threshold value. Therefore, the numbers of the time slots assigned to the terminal-side apparatuses100,110,120, and130in accordance with the fairness criteria are 20, 20, 20, and 0, respectively.

InFIG. 7C, the number of the time slots assigned in accordance with the fairness criteria is smaller than the queue length for all terminal-side apparatuses100to130. The FG/HE HTSAC module341determines at the step401not to perform reassignment for efficiency improvement accordingly.

InFIG. 7A, on the contrary, the FG/HE HTSAC module341assigns, at the step400inFIG. 4, the time slots equally to the terminal-side apparatuses100,110, and120where the queue length exceeds the threshold value of zero (that is, the queue length is not equal to zero). As a result, twenty time slots are assigned as the primarily assigned time slots to each of the terminal-side apparatuses100to120in accordance with the fairness criteria. As apparent from the figure, the number (i.e., 20) of the primarily assigned time slots exceeds the queue length (i.e., 10) for the terminal-side apparatus100. Therefore, the FG/HE HTSAC module341determines at the step401inFIG. 4that the reassignment should be performed for efficiency improvement.

In the example shown inFIG. 7A, the number of the primarily assigned time slots is smaller than the queue length for the terminal-side apparatuses110and120, so that the FG/HE HTSAC module341determines, at the step402, these terminal-side apparatuses to be “available terminal-side apparatus for reassignment”.

At the step403, the FG/HE HTSAC module341calculates the difference between the number of the primarily assigned time slots (i.e., 20 in this case) and the queue length (i.e., 10) for the terminal-side apparatus100. The FG/HE HTSAC module341designates the difference (i.e., 10) as the primary leftover time slots. The FG/HE HTSAC module341then determines the queue length (i.e., 10) in the terminal-side apparatus100as the number of the time slots assigned thereto.

At the step404, the FG/HE HTSAC module341reassigns the ten leftover time slots to the terminal-side apparatuses110and120, as shown inFIG. 7B. In this example, the FG/HE HTSAC module341uses the equivalent assignment to reassign the time slots. As a result, the terminal-side apparatuses110and120are reassigned with five primary leftover time slots each. Alternatively, if the FG/HE HTSAC module341uses the queue length averaging assignment algorithm, then the terminal-side apparatuses110and120are reassigned with ten and zero primary leftover time slots, respectively. If the FG/HE HTSAC module341reassigns the primary leftover time slots in proportion to the queue length, then the terminal-side apparatuses110and120are reassigned with six and four primary leftover time slots, respectively.

At the step405, the FG/HE HTSAC module341determines the final numbers of the time slots assigned to the terminal-side apparatuses100to130. For this purpose, the FG/HE HTSAC module341calculates, for each terminal-side apparatus, the sum of the number of the primarily assigned time slots (10, 20, 20, 0) and the number of the primary leftover time slots (0, 5, 5, 0) reassigned at the step404. The FG/HE HTSAC module341designates the sums, that is, 10, 25, 25, and 0, as the final numbers of the time slots assigned to the terminal-side apparatuses100to130.

In the manner described above, the FG/HE HTSAC module341of the present invention assigns the time slots to the terminal-side apparatuses100to130in accordance with the fairness criteria and then reassigns the excessive time slots thereto. This operation ensures fairness among the terminal-side apparatuses100to130and permits efficient assignment of time slots.

Next, a second embodiment of the present invention will be described referring to the drawings. In the second embodiment, time slots are assigned to all terminal-side apparatuses in accordance with the fairness criteria.FIG. 8Ais a view for use in describing assignment of time slots at the step400inFIG. 4on the basis of the fairness criteria. The terminal-side apparatuses100to130in this embodiment have queue lengths of 10, 50, 40, and 0, respectively in their buffers. It is assumed that the total number of the time slots available for the terminal-side apparatuses100to130is 60.

InFIG. 8A, the FG/HE HTSAC module341assigns, at the step400, time slots equally to all terminal-side apparatuses100to130. As a result, the terminal-side apparatuses100,110,120, and130are assigned with fifteen time slots for each. The number of the primarily assigned time slots exceeds the queue length (i.e., 10) in the terminal-side apparatus100. Likewise, number of the primarily assigned time slots exceeds the queue length (i.e., 0) in the terminal-side apparatus130. Therefore, at the step401inFIG. 4, the FG/HE HTSAC module341determines that reassignment should be performed for efficiency improvement.

At the step403inFIG. 4, the FG/HE HTSAC module341calculates the difference between the number of the primarily assigned time slots (i.e., 15) to the terminal-side apparatus100and the queue length (i.e., 10) stored therein. Likewise, the FG/HE HTSAC module341calculates the difference between the number of the primarily assigned time slots (i.e., 15) to the terminal-side apparatus130and the queue length (i.e., 0) stored therein. Next, the FG/HE HTSAC module341calculates the sum of these differences. Furthermore, the FG/HE HTSAC module341determines the sum (i.e., 20) as the number of the primary leftover time slots to be subjected to reassignment.

At the step404inFIG. 4, the FG/HE HTSAC module341performs reassignment for efficiency improvement. In the example shown inFIG. 8A, the FG/HE HTSAC module341reassigns the twenty leftover time slots to the terminal-side apparatuses110and120. More specifically, the terminal-side apparatuses110and120are assigned with ten leftover time slots for each. Finally, at the step405inFIG. 4, the FG/HE HTSAC module341determines that 10, 25, 25, and 0 time slots in total are assigned to the terminal-side apparatuses100,110,120, and130, respectively.

In the second embodiment, the FG/HE HTSAC module341does not restrict the terminal-side apparatus(es) to which the time slots are to be assigned in accordance with the fairness criteria. This embodiment also assures the fairness among the terminal-side apparatuses100to130and permits efficient time slot assignment, as in the first embodiment.

FIG. 9is a block diagram illustrating a configuration of the above-mentioned FG/HE HTSAC module341. The FG/HE HTSAC module341inFIG. 9comprises a fairness guarantee assignment circuit900, an assignment information management table901, a reassignment determination circuit902, a reassigned terminal-side apparatus determination circuit903, a reassigned time slots determination circuit904, an efficiency improvement reassignment circuit905, and an assigned time slots transmission circuit906.

The fairness guarantee assignment circuit900computes assignment of the time slots to the terminal-side apparatuses100to130in accordance with the fairness criteria at the timing of changing the time slot assignment. The fairness guarantee assignment circuit900then writes the computation results into the assignment information management table901. Subsequently, the fairness guarantee assignment circuit900notifies the reassignment determination circuit902of the completion of the assignment in accordance with the fairness criteria. In this event, the fairness guarantee assignment circuit900may assign the time slots to the terminal-side apparatus100to130in various ways. Examples include assignment of the time slots to all terminal-side apparatuses100to130, which corresponds to the second embodiment, and assignment of the time slots to only one or more terminal-side apparatuses where the queue length exceeds a predetermined threshold value, which corresponds to the first embodiment.

For the assignment of the time slots in accordance with the fairness criteria, different fairness criteria may be applied such as those described in the first embodiment. As shown inFIG. 10, the assignment information management table901comprises a queue length field911, an assigned time slots field912, and a reassignment flag field913. The queue length field911contains the queue length information in the terminal-side apparatus. The assigned time slots field912contains information indicative of the number of the time slots assigned to the corresponding terminal-side apparatus. The reassignment flag field913contains information indicative of flags associated with reassignment. In response to the queue length information supplied from the terminal-side apparatuses100to130, the queue length field911is updated. When the fairness guarantee assignment circuit900completes the above-mentioned assignment, it writes the result into the assigned time slots field912. Updates of the assigned time slots field912will be described later. The reassignment flag field913will also be described later.

In response to the notice indicative of completion of the primary assignment from the fairness guarantee assignment circuit900, the reassignment determination circuit902obtains, from the assignment information management table901, the information indicative of the number of the primarily assigned time slots as well as the queue length information. The reassignment determination circuit902then determines, based on the information obtained, whether or not the reassignment should be carried out. More specifically, the reassignment determination circuit902compares the number of the primarily assigned time slots with the queue length for each terminal-side apparatus. If the number of the primarily assigned time slots exceeds the queue length in one or more terminal-side apparatuses, then the reassignment determination circuit902determines that the reassignment should be performed. The reassignment determination circuit902supplies a control trigger to the reassigned terminal-side apparatus determination circuit903accordingly.

On the contrary, when the number of the primarily assigned time slots is smaller than the queue length for all terminal-side apparatuses100to130, the reassignment determination circuit902determines not to perform the reassignment. The reassignment determination circuit902supplies the numbers of the primarily assigned time slots to the assignment time slots transmission circuit906.

In response to the control trigger supplied from the reassignment determination circuit902, the reassigned terminal-side apparatus determination circuit903obtains, from the assignment information management table901, the information indicative of the number of the primarily assigned time slots as well as the queue length information. The reassigned terminal-side apparatus determination circuit903determines available terminal-side apparatus(es) for reassignment. More specifically, the reassigned terminal-side apparatus determination circuit903designates, as the available terminal-side apparatus(es) for reassignment, the terminal-side apparatus(es) having the number of the primarily assigned time slots being smaller than the queue length. The reassigned terminal-side apparatus determination circuit903excludes the remaining terminal-side apparatus(es) from the subjects of the reassignment. Then, the reassigned terminal-side apparatus determination circuit903writes “reassigned” or “not reassigned” in the reassignment flags field913for the corresponding terminal-side apparatus in the assignment information management table901. The reassigned terminal-side apparatus determination circuit903supplies a control trigger to the reassignment time slots determination circuit904.

In response to the control trigger from the reassigned terminal-side apparatus determination circuit903, the reassignment time slots determination circuit904obtains, from the assignment information management table901, the information indicative of the number of the primarily assigned time slots to the non-available terminal-side apparatus for reassignment as well as the queue length information therefor. The reassignment time slots determination circuit904determines the number of the primary leftover time slots to be reassigned. More specifically, the reassignment time slots determination circuit904calculates the difference between the number of the primarily assigned time slots and the queue length for each of the non-available terminal-side apparatuses for reassignment. The reassignment time slots determination circuit904determines the sum of the differences as the number of the primary leftover time slots to be reassigned. In addition, the reassignment time slots determination circuit904designates the queue length as the number of the time slots assigned to the corresponding non-available terminal-side apparatus for reassignment. The reassignment time slots determination circuit904writes the determined number of the time slots into the assigned time slots field912for the non-available terminal-side apparatus for reassignment in the assignment information management table901to update this field.

After calculation of the number of the primary leftover time slots to be reassigned, the reassignment time slots determination circuit904notifies the efficiency improvement reassignment circuit905of this number. In response to this notice, the efficiency improvement reassignment circuit905obtains, from the assignment information management table901, the queue length information for the available terminal-side apparatus(es) for reassignment. The efficiency improvement reassignment circuit905reassigns the number of the primary leftover time slots to the available terminal-side apparatus(es). This reassignment may be made in various ways including those described in the first embodiment.

If the total number of the time slots assigned to the available terminal-side apparatus exceeds the queue length as a result of the primary reassignment, the reassigned terminal-side apparatus determination circuit903excludes the corresponding terminal-side apparatus(es) from the subjects of the secondary reassignment. The reassigned terminal-side apparatus determination circuit903designates the queue length in the non-available terminal-side apparatus(es) for reassignment as the number of the time slots assigned thereto.

The reassignment time slots determination circuit904determines the difference between the number of the time slots assigned previously (i.e., the sum of the primarily assigned time slots and the primary leftover time slots) and the queue length as the number of the secondary leftover time slots. Then, the reassignment time slots determination circuit904reassigns the secondary leftover time slots to the available terminal-side apparatus(es) by using any one of the above-mentioned methods. The FG/HE HTSAC module341repeats the same procedures until the number of the time slots assigned becomes equal to or smaller than the queue length for all terminal-side apparatuses. It is noted that no terminal-side apparatus may become available for reassignment before completion of the operation even though one or more time slots still remain without being assigned. In such a case, the FG/HE HTSAC module341assigns all of the remaining time slots to all terminal-side apparatuses according to the fairness criteria used at the step400.

When reassignment is performed, the efficiency improvement reassignment circuit905determines, as the total number of the time slots assigned to the terminal-side apparatuses100to130, the sum of the number of the time slots contained in the assignment time slots field912in the assignment management table901and the number of the leftover time slots reassigned. The efficiency improvement reassignment circuit905notifies the assigned time slots transmission circuit906of the determined number of the time slots.

The assigned time slots transmission circuit906supplies the information indicative of the number of the time slots to be assigned to the terminal-side apparatuses100to130through the downstream transmission line190, in response to reception of this information from the reassignment determination circuit902or the assigned time slots transmission circuit906.

As described above, according to the configuration shown inFIG. 9, the FG/HE HTSAC module can achieve the time slot assignment methods described in conjunction with the first and second embodiments.

The first embodiment of the present invention is advantageous in that the fairness can be assured among the terminal-side apparatuses with efficient use of the transmission bandwidths. This is because the method for assigning the time slots according to the present invention allows the network-side apparatus to assign the time slots to the terminal-side apparatuses in accordance with the fairness criteria, assuring fairness among the terminal-side apparatuses. If there is the terminal-side apparatus having the number of the time slots assigned exceeding the queue length, the network-side apparatus reassigns the excessive time slots. This prevents excessive assignment of the time slots while keeping the fairness, making efficient use of the transmission bandwidths.

Modifications of the invention herein disclosed will occur to person skilled in the art and all such modifications are deemed to be within the scope of the invention as defined by the appended claims.