Packet relay device and queue scheduling method

Each of the plurality of queues stores packet data of a received packet. The read concession assignor assigns one of the plurality of queues with a read concession for a predefined time period. The overdraft storage stores an overdraft amount in connection with each of the plurality of queues. The read adequacy determiner determines, in accordance with an overdraft amount stored in connection with one queue out of the plurality of queues, whether to read packet data from the one queue. The overdraft updater updates at least one of a first overdraft amount stored in connection with a first queue and a second overdraft amount stored in connection with a second queue different from the first queue upon reading packet data from the first queue during a time period while the second queue is assigned with the read concession.

FIELD

The embodiments discussed herein are related to a packet relay device and, more particularly, to a queue scheduling method employed in the packet relay device.

BACKGROUND

A packet relay device includes a plurality of communication ports therein. A packet is received via one of the plurality of communication ports, and stored in a queue. The stored packet is read from the queue in a first-in first-out manner. One or more communication ports via which the packet is to be transmitted are determined and the packet is transferred to the determined output ports. When the packet relay device includes a plurality of queues, a queue scheduling for handling these plurality of queues becomes a problem. The deficit round robin (DRR) scheme has been proposed as a queue scheduling method which allows a plurality of queues to be fairly handled, and this DRR scheme is also employed in packet relay devices (for example, see Japanese Laid-open Patent Publication No. 11-252097).

In the DRR scheme, a quantum value, which is a quota of an amount of data read from each queue in one read process, is determined in advance. That is, data of an amount of the quantum value has been read from one queue, the read process on the queue terminates to shift to the read process on another queue. When an amount of data stored in a queue is less than the quantum value, the read process on the queue terminates upon completion of reading entire data stored in the queue. A read process on each queue is performed on a packet-by-packet basis, and thus, practically, the read process may not terminate upon completion of reading an amount of data exactly corresponding to the quantum value. Instead, the read process on the queue may be prolonged until completion of reading a packet which has being read at a time when the amount of data corresponding to the quantum value has been read. An amount of data read beyond the quantum value is referred to as a deficit value. A quota of an amount of data for the next read process on the queue is calculated by subtracting the deficit value from the quantum value. By repeating this operation, an average amount of data obtained by one read process on each queue becomes close to the quantum value. Thus, the DRR scheme is considered as a fair queue scheduling method.

SUMMARY

According to an aspect of the present invention, provided is a packet relay device for relaying a packet. The packet relay device includes a plurality of queues, a read concession assignor, an overdraft storage, a read adequacy determiner, and an overdraft updater.

Each of the plurality of queues stores packet data of a received packet.

The read concession assignor assigns one of the plurality of queues with a read concession for a predefined time period. The read concession allows the packet relay device to read packet data stored in a queue assigned with the read concession.

The overdraft storage stores an overdraft amount in connection with each of the plurality of queues. The overdraft amount indicates an amount of packet data read from a queue during a time period while another queue is assigned with the read concession.

The read adequacy determiner determines, in accordance with an overdraft amount stored in connection with one queue out of the plurality of queues, whether to read packet data from the one queue.

The overdraft updater updates at least one of a first overdraft amount stored in connection with a first queue and a second overdraft amount stored in connection with a second queue different from the first queue upon reading packet data from the first queue during a time period while the second queue is assigned with the read concession.

DESCRIPTION OF EMBODIMENTS

In the DRR scheme, a weight may be allocated to each queue, and a quantum value in proportion to the weight may be applied to each queue. In this case, the size of each queue may be in consistent with the weight allocated thereto against the size of a queue to which a minimum weight is allocated. Therefore, when a maximum weight allowed to be allocated is large, in proportion thereto, the sizes of individual queues to be provided are increased, thereby causing resources inside the packet relay device to be consumed to a great degree.

Accordingly, for a queue scheduling in a packet relay device, it is preferable to provide a queue scheduling method which makes it unnecessary to particularly increase the sizes of queues, even when weights allocated to the queues are large.

According to the embodiments, the weights allocated to the queues are reflected to time allocation on a queue scheduling in a packet relay device. Thus, it is possible to provide a queue scheduling method which makes it unnecessary to particularly increase the sizes of queues, even when the weights allocated to the queues are large.

Hereinafter, an embodiment of the present invention will be discussed with reference to drawings.

FIG. 1is a diagram illustrating an example of a system configuration of a packet relay device according to an embodiment of the present invention. A packet relay device1illustrated in the example ofFIG. 1includes a plurality of line cards2and a switch card4. One of the line cards2receives a packet and transfers the packet to the switch card4. The switch card4transfers the packet to one of the line cards2. The line card2received the packet from the switch card4transmits the packet.

Each of the line cards2includes a communication port (denoted by “COM-PORT” in the drawings)6, a queue8, an MC address list storage10, an output port table storage12, a packet divider14, a queue16, a packet restorer18, and a port controller20.

The communication port6receives and transmits a packet.

The queue8temporarily stores an input packet.

The MC address list storage10stores an MC address list containing a destination address of a multicast packet.

The output port table storage12stores an output port table containing an output port identifier (ID) capable of identifying an output port for a unicast packet.

The packet divider14divides a packet into segments.

The queue16temporarily stores a segment transferred from the switch card4.

The packet restorer18combines segments to restore the packet.

The port controller20controls the entire line card2.

In the discussion of the embodiment, it is assumed that each communication port6is included in a different line card2. However, it is not necessary for each communication port6to be included in a different line card2. In the discussion of the embodiment, the MC address list storage10and the output port table storage12are provided for each communication port6, respectively. However, they may be provided for a plurality of communication ports6, respectively. Further, the entire packet relay device1may include only one MC address list storage10and only one output port table storage12, respectively.

The communication port6receives an input packet and transfers the input packet to the queue8. Further, the communication port6transmits an output packet transferred from the packet restorer18.

The queue8stores the input packet transferred from the communication port6, and transfers the stored packet to the packet divider14in a first-in first-out manner.

The MC address list storage10stores an MC address list containing a destination address of a multicast packet.

The output port table storage12stores the output port table containing an output port ID corresponding to a destination address of a unicast packet. The content of the output port table is stored as a result of a source address learning process. The source address learning process is irrelevant to the intent of the present embodiment and is a technology well-known to those skilled in the art, thus, is omitted from this discussion.

The packet divider14divides the input packet transferred from the queue8into blocks of data having a predefined size, adds a segment header to each block of data to form a segment, and transfers the segments to the switch card4. The packet divider14performs this process with reference to the MC address list stored in the MC address list storage10and/or the output port table stored in the output port table storage12.

The queue16temporarily stores segments transferred from the switch card4, and then, transfers the stored segments to the packet restorer18.

The packet restorer18removes the segment header from each of the segments transferred from the queue16and combines resultant blocks of data to restore a packet.

The port controller20controls the entire line card2. It is assumed that all of the functions, which is not performed by the above-discussed each processing unit, among the functions performed by the line card2may be processed by the port controller20.

The switch card4includes a UC queue22, an MC queue24, a segment sorter26, a segment read unit28, an MC port table storage30, an MC port searcher32, an MC copier34, a segment sender36, and a switch controller38.

The UC queue22temporarily stores segments, which have been derived from a unicast packet, transferred from a line card2.

The MC queue24temporarily stores segments, which have been derived from a multicast packet, transferred from a line card2.

The segment sorter26sorts segments into the UC queue22or the MC queue24.

The segment read unit28reads segments from the UC queue22or the MC queue24.

The MC port table storage30stores an MC port table containing data on an output port associated with a multicast packet.

The MC port searcher32searches for an output port associated with a multicast packet.

The MC copier34copies the segments derived from a multicast packet and rewrites a segment header of each copied segment for a respective output port.

The segment sender36transfers segments to a line card2.

The switch controller38controls the entire switch card4.

The segment sorter26sorts segments transferred from a line card2to the UC queue22or the MC queue24.

The UC queue22temporarily stores segments, which have been derived from a unicast packet, transferred from the segment sorter26, and transfers the stored segments to the segment read unit28in a first-in first-out manner.

The MC queue24temporarily stores segments, which have been derived from a multicast packet, transferred from the segment sorter26, and, transfers the stored segments to the segment read unit28in a first-in first-out manner.

The segment read unit28reads segments from the UC queue22to transfer the read segments to the segment sender36, and reads segments from the MC queue24to transfer the read segments to the MC copier34.

The MC port table storage30stores an MC port table containing data on an output port corresponding to a destination address of a multicast packet.

The MC port searcher32searches the MC port table storage30for an output port ID in accordance with a destination address contained in each segment, and then, outputs the found output port ID to the MC copier34.

The MC copier34copies, when the transferred segment is a segment derived from a multicast packet, the transferred segment for the output port identified with the output port ID found by the MC port searcher32, writes the output port ID into the segment header of the copied segment, and transfers the resultant segment to the segment sender36.

The segment sender36sends the transferred segment to the corresponding line card2in accordance with the output port ID contained in the segment header of the transferred segment.

The switch controller38controls the entire switch card4. It is assumed that all of the functions, which is not performed by the above-discussed each processing unit, among the performed by the switch card4may be processed by the switch controller38.

Hereinafter, operations performed by the packet relay device1will be discussed.

FIG. 2is a flowchart illustrating an example of an operation flow of a process performed by the packet relay device according to an embodiment of the present invention. Hereinafter, an operation flow of a process performed by the packet relay device1according to the embodiment of the present invention will be discussed in the order of operation S102to operation S114illustrated inFIG. 2.

In operation S102, the communication port6receives an input packet and stores the input packet in the queue8.

In operation S104, the packet divider14divides the input packet stored in the queue8into blocks of data having a predefined size, adds a segment header to each block of data to form a segment. When a destination address contained in the input packet corresponds to one of addresses stored in the MC address list storage10, the packet divider14sets an MC flag, which is capable of indicating that this segment is derived from a multicast packet, contained in a segment header of each segment. When the destination address contained in the input packet corresponds to none of addresses stored in the MC address list storage10, the packet divider14searches the output port table storage12for an output port ID in accordance with the destination address contained in the input packet, and writes the found output port ID into a segment header of each segment. When the packet divider14fails to find an output port ID in the output port table storage12, the packet divider14sets a BC flag, which is capable of indicating that this segment is derived from a broadcast packet, contained in the segment header of each segment. The packet divider14transfers the segments to the switch card4.

In operation S106, when the MC flag or the BC flag is set in the segment header of the transferred segment, that is, when the transferred segment is derived from a multicast packet or a broadcast packet, the segment sorter26stores the segment in the MC queue24. When neither the MC flag nor the BC flag is set in the segment header of the transferred segment, that is, when the transferred segment is derived from a unicast packet, the segment sorter26stores the segment in the UC queue22.

In operation S108, the segment read unit28reads the segment from the UC queue22or the MC queue24. The details of a segment read process will be discussed later.

In operation S110, the segment sender36transfers the segment to the corresponding line card2in accordance with the output port ID contained in the segment header of the segment.

In operation S112, the packet restorer18removes the segment header from the transferred segment, and combines segments without the segment header to restore a packet.

In operation S114, the communication port6transmits the restored packet.

In the embodiment, it is assumed that the packet relay device1controls the segment read process for reading segments from the queues in accordance with a read concession.

FIG. 3is a diagram illustrating an example of a read concession according to an embodiment of the present invention.FIG. 3illustrates a UCF graph104, an MCF graph106, and a read concession indication102. A horizontal axis is a time axis.

The UCF graph104represents a time variation of a flag value which indicates a condition as to whether the UC queue22is empty or not.

The MCF graph106represents a time variation of a flag value which indicates a condition as to whether the MC queue24is empty or not.

The read concession indication102indicates which of the UC queue22and the MC queue has the read concession.

The UCF graph104takes a value “0” when the UC queue22is empty and a value “1” when the UC queue22is not empty. The MCF graph106takes a value “0” when the MC queue24is empty, and a value “1” when the MC queue24is not empty. With respect to the read concession indication102, for a time period while the UC queue has the read concession, a box122appended with a letter “U” is illustrated, and for a time period while the MC queue has the read concession, a box124appended with a letter “M” is illustrated. During a time period while neither of the boxes are illustrated, neither of the queues has the read concession. The length of each box in the time-axis direction represents a predefined time period for reading a segment, that is, one segment is read during a time period represented by one box.

During a time period112, only the UC queue22is not empty, and thus, the read concession is assigned to the UC queue22. During time periods114and118, only the MC queue is not empty, and thus, the read concession is assigned to the MC queue24. During a time period116, neither the UC queue22nor the MC queue24is empty, and thus, the read concession is allocated in time in accordance with the weight predefined for each queue. In an example illustrated inFIG. 3, it is assumed that the weights are allocated in accordance with the following expression, UC:MC=1:2. Therefore, during the time period116, the read concession is allocated in accordance with a proportion of two boxes each appended with a letter “M” in contrast to one box appended with a letter “U”. In the embodiment, the segment read unit28manages this read concession.

FIG. 4is a diagram illustrating an example of a configuration of a segment read unit in a packet relay device according to an embodiment of the present invention. The segment read unit28includes a segment reader42, a queue switch controller44, a weight storage46, a read concession assignor48, an overdraft storage50, an overdraft updater52, and a read adequacy determiner54.

The segment reader42reads a segment from either of the UC queue22and the MC queue24.

The queue switch controller44controls from which of the UC queue22and the MC queue24the segment reader42reads the segment.

The weight storage46stores each weight assigned to the UC queue22and the MC queue24, respectively.

The read concession assignor48assigns the UC queue22or the MC queue24with the read concession for each predefined time period.

The overdraft storage50stores two overdraft amounts corresponding to the UC queue and the MC queue, respectively. Each of the overdraft amounts represents an amount of segments which were read from the corresponding queue during time periods while the read concession was not assigned to the corresponding queue.

The overdraft updater52updates the overdraft amounts.

The read adequacy determiner54determines, with respect to the UC queue22or the MC queue24, whether to perform the segment read process.

The segment reader42reads a segment from the UC queue22or the MC queue24in accordance with the control by the queue switch controller44, and then, transfers the read segment to the segment sender36or the MC copier34.

The queue switch controller44controls from which of the UC queue22and the MC queue24the segment reader42reads the segments in accordance with a determination result notified from the read adequacy determiner54. The queue switch controller44also notifies the overdraft updater52of data on a queue from which the segment reader42has read the segments, and the number of read segments.

The weight storage46stores each weight assigned to the UC queue22and the MC queue24, respectively, in advance.

The read concession assignor48assigns the UC queue22or the MC queue24with the read concession for each predefined time period in accordance with weights assigned to the UC queue22and the MC queue24, respectively.

In the overdraft storage50stores a UC overdraft amount corresponding to the UC queue22and an MC overdraft amount corresponding to the MC queue24.

The overdraft updater52updates values of overdraft amounts stored in the overdraft storage50in accordance with data on a queue from which the segment reader42has read the segments and the number of read segments, which are notified from the queue switch controller44, and data on the read concession assigned by the read concession assignor48.

The read adequacy determiner54determines, with respect to the UC queue22or the MC queue24, whether to read segments, in accordance with values of overdraft amounts stored in the overdraft storage50, and notifies the queue switch controller44of the determination result.

FIG. 5is a flowchart illustrating an example of an operation flow of a segment read process according to an embodiment of the present invention. Hereinafter, an operation flow of a segment read process according to the embodiment of the present invention will be discussed in the order of operation S202to operation S222illustrated inFIG. 5. It is assumed that the segment read process is performed every predefined time period for reading a segment.

In operation S202, the queue switch controller44determines whether the UC queue22is empty.

In operation S204, when the UC queue22is empty (“Yes” in operation S202), the overdraft updater52subtracts one from the value of the UC overdraft amount. In the embodiment, it is assumed that the value of the UC overdraft amount is not updated when the value of the UC overdraft amount is not a positive value. Further, it is assumed that the amount of packet data read from the queues is counted by the number of the read segments.

In operation S206, the queue switch controller44determines whether the MC queue24is empty.

In operation S208, when the MC queue24is empty (“Yes” in operation S206), the overdraft updater52subtracts one from the value of the MC overdraft amount. In the embodiment, it is assumed that the value of the MC overdraft amount is not updated when the value of the MC overdraft amount is not a positive value.

In operation S210, when the MC queue24is not empty (“No” in operation S206), the segment reader42reads a segment from the MC queue24.

In operation S212, when the UC queue is not empty (“No” in operation S202), the queue switch controller44determines whether the MC queue24is empty.

In operation S214, when the MC queue24is empty (“Yes” in operation S212), the overdraft updater52subtracts one from the value of the MC overdraft amount. In the embodiment, it is assumed that the value of the MC overdraft amount is not updated when the value of the MC overdraft amount is not a positive value.

In operation S216, the segment reader42reads a segment from the UC queue22.

In operation S218, when the MC queue24is not empty (“No” in operation S212), the queue switch controller44determines whether the next segment is a segment included in a new packet. In the embodiment, it is assumed that a segment header of a segment contains data capable of indicating a type of the segment. The types of a segment includes, for example, a beginning segment of a packet, an ending segment of a packet, an intermediate segment of a packet, a segment included in a packet consisting of a single segment, or the like. The queue switch controller44records a type of a segment which was read during a previous segment read process. Thus, it may be determined that the next segment is a segment included in a new packet when a segment which was read during a previous segment read process is an ending segment of a packet or a segment included in a packet consisting of a single segment.

In operation S220, when the next segment is a segment included in a new packet (“Yes” in operation S218), the segment read unit28performs a “new reading” process. The details of the “new reading” process will be discussed later.

In operation S222, when the next segment is not a segment included in a new packet (“No” in operation S218), the segment read unit28performs a “continued reading” process. The details of the “continued reading” process will be discussed later.

FIG. 6is a flowchart illustrating an example of an operation flow of a “new reading” process according to an embodiment of the present invention. Hereinafter, an operation flow of the “new reading” process according to the embodiment will be discussed in the order of operation S302to operation S318illustrated inFIG. 6.

In operation S302, the read concession assignor48determines which of the UC queue22and the MC queue24is assigned with the read concession.

In operation S304, when the UC queue22is assigned with the read concession (“UC” in operation S302), the read adequacy determiner54determines whether the value of the UC overdraft amount is a positive value.

In operation S306, when the value of the UC overdraft amount is not a positive value (“No” in operation S304), the segment reader42reads a segment from the UC queue22.

In operation S308, when the value of the UC overdraft amount is a positive value (“Yes” in operation S304), the segment reader42reads a segment from the MC queue24.

In operation S310, the overdraft updater52subtracts one from the value of the UC overdraft amount.

In operation S312, when the MC queue24is assigned with the read concession (“MC” in operation S302), the read adequacy determiner54determines whether the value of the MC overdraft amount is a positive value.

In operation S314, when the value of the MC overdraft amount is not a positive value (“No” in operation S312), the segment reader42reads a segment from the MC queue24.

In operation S316, when the value of the MC overdraft amount is a positive value (“Yes” in operation S312), the segment reader42reads a segment from the UC queue22.

In operation S318, the overdraft updater52subtracts one from the value of the MC overdraft amount.

As discussed above, when the value of an overdraft amount corresponding to one queue assigned with the read concession is a positive value, the segment read process is performed on the other queue.

FIG. 7is a flowchart illustrating an example of an operation flow of a “continued reading” process according to an embodiment of the present invention. Hereinafter, an operation flow of the “continued reading” process according to the embodiment will be discussed in the order of operation S402to operation S422illustrated inFIG. 7.

In operation S402, the queue switch controller44determines on which of the UC queue22and the MC queue the previous segment read process was performed. In the embodiment, it is assumed that, on which of the UC queue22and the MC queue24the previous segment read process was performed is recorded by setting or resetting a queue flag which is capable of indicating a queue on which the previous segment read process was performed.

In operation S404, when the previous segment read process was performed on the UC queue22(“UC” in operation S402), the segment reader42reads a segment from the UC queue22.

In operation S406, the queue switch controller44determines which of the UC queue22and the MC queue24has the read concession.

In operation S408, when the MC queue24has the read concession (“MC” in operation S406), the queue switch controller44determines whether the value of the MC overdraft amount is a positive value.

In operation S410, when the value of the MC overdraft amount is not a positive value (“No” in operation S408), the overdraft updater52adds one to the value of the UC overdraft amount.

In operation S412, when the value of the MC overdraft amount is a positive value (“Yes” in operation S408), the overdraft updater52subtracts one from the value of the MC overdraft amount.

In operation S414, when the previous segment read process was performed on the MC queue24(“MC” in operation S402), the segment reader42reads a segment from the MC queue24.

In operation S416, the queue switch controller44determines which of the UC queue22and the MC queue24has the read concession.

In operation S418, when the UC queue22has the read concession (“UC” in operation S416), the queue switch controller44determines whether the value of the UC overdraft amount is a positive value.

In operation S420, when the value of the UC overdraft amount is not a positive value (“No” in operation S418), the overdraft updater52adds one to the value of the MC overdraft amount.

In operation S422, when the value of the UC overdraft amount is a positive value (“Yes” in operation S418), the overdraft updater52subtracts one from the value of the UC overdraft amount.

By providing such a configuration as discussed above, the packet relay device according to the embodiment may reflect, in the queue scheduling, a weight allocated to each queue to time allocation of the segment read process performed on the corresponding queue.

Hereinafter a more specific example will be discussed.

FIG. 8is a diagram illustrating an example of queues according to an embodiment of the present invention.FIG. 8illustrates the UC queue22and the MC queue24. In the UC queue22, unicast packets201to207are stored. The number of segments constituting each unicast packet is illustrated in each box representing a unicast packet, respectively. In the MC queue24, multicast packets211to214are stored. The number of segments constituting each multicast packet M and the number of output ports N are illustrated in the form of M×N in each box representing a multicast packet, respectively.

FIG. 9is a diagram illustrating an example of a queue scheduling according to an embodiment of the present invention.FIG. 9illustrates the read concession indication102, a UCC graph132, a sequence of unicast packets134, an MCC graph136, a sequence of multicast packets138, and a time axis140.

The UCC graph132represents a time variation of a value of the UC overdraft amount.

The sequence of unicast packets134represents time periods when each unicast packet is read from the UC queue22.

The MCC graph136represents a time variation of a value of the MC overdraft amount.

The sequence of multicast packets138represents time periods when each multicast packet is read from the MC queue24.

For the sake of convenience in discussion, a time period number is appended, along the time axis140, to each time period while a segment is read. In this example illustrated inFIG. 9, it is assumed that weights are allocated in accordance with the following expression, UC:MC=2:3. According to the read concession indication102, it may be understood that, during time periods0and1, the read concession is assigned to the UC queue22, and during time periods2to4, the read concession is assigned to the MC queue24.

A time period0is a “new reading” time period. It is assumed that the value of the UC overdraft amount and the value of the MC overdraft amount are 0, respectively, during the time period0.

During the time period0, the read concession is assigned to the UC queue22, and the value of the UC overdraft amount is not a positive value. Thus, the segment read unit28reads a packet from the UC queue22. The unicast packet201stored at the head of the UC queue22is a packet consisting of four segments. Thus, the segment read unit28reads segments from the UC queue22across four time periods (time periods0to3). During the first two time periods (time periods0and1), the read concession is assigned to the UC queue22, thus, causing no change in values of the UC overdraft amount and the MC overdraft amount. During the following two time periods (time periods2and3), the MC queue24has the read concession, thus, the UC overdraft amount is added by one during each of the two time periods. After the unicast packet201has been read, the unicast packet202becomes a head packet in the UC queue22.

During a time period4, the read concession is assigned to the MC queue24, and the value of the MC overdraft amount is not a positive value. Thus, the segment read unit28reads a packet from the MC queue24. This segment read process is performed with respect to a first copy out of three copies of the multicast packet211stored at the head of the MC queue24. The multicast packet211is a packet consisting of two segments, thus, the segment read unit28reads segments from the MC queue24across two time periods (time periods4and5). During the first time period (time period4), the MC queue24has the read concession, thus, causing no change in the values of the UC overdraft amount and the MC overdraft amount. During the following one time period (time period5), the UC queue22has the read concession, and the value of the UC overdraft amount is a positive value. Thus, the value of the UC overdraft amount is subtracted by one.

During a time period6, the read concession is assigned to the UC queue22, and the value of the UC overdraft amount is a positive value. Thus, the segment read unit28reads a packet from the MC queue24. This segment read process is performed with respect to a second copy out of the three copies of the multicast packet211stored at the head of the MC queue24. The multicast packet211is a packet consisting of two segments, thus, the segment read unit28reads segments from the MC queue24across two time periods (time periods6and7). During the first time period (time period6), the value of the UC overdraft amount is subtracted by one. During the following one time period (time period7), the MC queue24has the read concession, and thus, causing no change in the values of the UC overdraft amount and the MC overdraft amount.

During a time period8, the read concession is assigned to the MC queue24, and the value of the MC overdraft amount is not a positive value. Thus, the segment read unit28reads a packet from the MC queue24. This segment read process is performed with respect to a third copy out of the three copies of the multicast packet211stored at the head of the MC queue24. The multicast packet211is a packet consisting of two segments, thus, the segment read unit28reads segments from the MC queue24across two time periods (time periods8and9). During this two time periods (time periods8and9), the MC queue24has the read concession, thus, causing no change in the values of the UC overdraft amount and the MC overdraft amount. After the multicast packet211has been read, the multicast packet212becomes a head packet in the MC queue24.

During a time period10, the read concession is assigned to the UC queue22, and the value of the UC overdraft amount is not a positive value. Thus, the segment read unit28reads a packet from the UC queue22. The unicast packet202stored at the head of the uc queue22is a packet consisting of three segments, thus, the segment read unit28reads segments from the UC queue22across three time periods (time periods10to12). During the first two time periods (time periods10and11), the read concession is assigned to the UC queue22, thus, causing no change in the values of the UC overdraft amount and the MC overdraft amount. During the following one time period (time period12), the read concession is assigned to the MC queue24, and the value of the MC overdraft amount is not a positive value. Thus, the value of the UC overdraft amount is added by one. After the unicast packet202has been read, the unicast packet203becomes a head packet in the UC queue22.

During a time period13, the read concession is assigned to the MC queue24, and the value of the MC overdraft amount is not a positive value. Thus, the segment read unit28reads a packet from the MC queue24. This segment read process is performed with respect to a first copy out of three copies of a multicast packet212stored at the head of the MC queue24. The multicast packet212is a packet consisting of four segments, thus, the segment read unit28reads segments from the MC queue24across four time periods (time periods13to16). During the first two time periods (time periods13and14), the MC queue24has the read concession, thus, causing no change in the values of the UC overdraft amount and the MC overdraft amount. During the following one time period (time period15), the read concession is assigned to the UC queue22, and the value of the UC overdraft amount is a positive value. Thus, the value of the UC overdraft amount is subtracted by one. During the following one time period (time period16), the UC queue22has the read concession, and the value of the UC overdraft amount is not a positive value. Thus, the value of the MC overdraft amount is added by one.

During a time period17, the read concession is assigned to the MC queue24, and the value of the MC overdraft amount is a positive value. Thus, the segment read unit28read a packet from the UC queue22. The unicast packet203stored at the head of the UC queue22is a packet consisting of only one segment, thus, the segment read unit28reads a segment from the UC queue22during only one time period (time period17). During this time period (time period17), the value of the MC overdraft amount is subtracted by only one. After the unicast packet203has been read, the unicast packet204becomes a head packet in the UC queue22.

During a time period18, the read concession is assigned to the MC queue24, and the value of the MC overdraft amount is not a positive value. Thus, the segment read unit28reads a packet from the MC queue24. This segment read process is performed with respect to a second copy out of the three copies of the multicast packet212stored at the head of the MC queue24. The multicast packet212is a packet consisting of four segments, thus, the segment read unit28reads segments from the MC queue24across four time periods (time periods18to21). During the first two time periods (time periods18and19), the MC queue24has the read concession, thus, causing no change in the values of the UC overdraft amount and the MC overdraft amount. During the following two time periods (time periods20and21), the read concession is assigned to the UC queue22, and the value of the UC overdraft amount is not a positive value. Thus, the value of the MC overdraft amount is added by one during each of the two time periods.

During a time period22, the read concession is assigned to the MC queue24, and the value of the MC overdraft amount is a positive value. Thus, the segment read unit28reads a packet from the UC queue22. The unicast packet204stored at the head of the UC queue22is a packet consisting of four segments, thus, the segment read unit28reads segments from the UC queue22across four time periods (time periods22to25). During the first two time periods (time periods22and23), the read concession is assigned to the MC queue24, and the value of the MC overdraft amount is a positive value, thus, the value of the MC overdraft amount being subtracted by one during each of the two time periods. During the following one time period (time period24), the read concession is assigned to the MC queue24, and the value of the MC overdraft amount is not a positive value. Thus, the value of the UC overdraft amount is added by one. During the following one time period (time period25), the UC queue22has the read concession, and thus, causing no change in the values of the UC overdraft amount and the MC overdraft amount. After the unicast packet204has been read, the unicast packet205becomes a head packet in the UC queue22.

In the embodiment discussed above, it is assumed that the packet relay device includes only two queues, i.e., the UC queue and the MC queue. However, it is not limited to this, but the packet relay device may include three queues or more. In such a case, the values of the overdraft amounts corresponding to a queue on which the segment read process is performed and a different queue which has the read concession may be increased or decreased during the same time period while the segment read process is performed.

In the embodiment discussed above, it is assumed that each queue corresponds to an overdraft amount. However, when the packet relay device includes only two queues, only one overdraft amount may be provided. In such a case, a positive sign and a negative sign thereof may identify two overdraft amounts corresponding to the two queues, respectively.

As discussed above, according to the embodiment, it may be possible to provide a queue scheduling method which may not require to increase the size of the queues even when the weights allocated to individual queues are increased in the queue scheduling in the packet relay device.

Functions included in the packet relay device1according to the above-discussed embodiment of the present invention may be realized not only in the form of hardware, but also in the form of software executed by a computer incorporated in the packet relay device1. For example, by developing a program which allows a computer to execute functions of the segment reader42, the queue switch controller44, the read concession assignor48, the overdraft updater52and the read adequacy determiner54, and allowing the program to be written into memory devices of the computer and be executed by the computer, it is possible to realize the functions of the segment read unit28.

Such a program that enables realization of the packet relay device1according to the embodiment of the present invention may be stored in memory devices, such as ROM devices or RAM devices, both being incorporated in the packet relay device1, or recording media, such as a hard disc, and when executing the program, the program is loaded to a main memory, and is executed thereon.