Packet flow control apparatus and a method for controlling the same

• US 6,965,566 B2
• Filed: 02/06/2001
• Issued: 11/15/2005
• Est. Priority Date: 02/16/2000
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Nakamichi, Koji, Kawasaki, Takeshi, Soumiya, Toshio
• Primary Examiner(s): NGUYEN, HANH N
• Application Number:
  US09/777,340
• Publication Number:
  US 20010014081A1
• Time in Patent Office: 1,743 Days
• Field of Search: 370/389, 370/410, 370/412, 370/395, 370/236, 370/473, 370229-235, 370/235.1, 370/392, 370/395.1, 370/395.21, 370/395.52, 370/395.4, 370/395.42, 370/413, 370/428, 370/468, 709/223, 709/238
• US Class Current: 370/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control

Abstract

A packet flow control apparatus performing flow control of packets each having variable length, includes: a buffer memory for temporarily accumulating arrived packets until a sending time of each packet; a counter updated based on a rate determined in accordance with a packet length calculated by a counter value of the counter and limited flow of packets; a sending time determining section for determining the sending time of each packet based on the counter value and a present time; and a sending order control section for managing a sending order of each packet accumulated in the buffer memory, and for sending a read instruction of each packet to the buffer memory, based on the sending time determined by the sending time determining section.

Claims

1. A packet flow control apparatus performing flow control of packets each having variable length, comprising:

a buffer memory for temporarily accumulating arrived packets until a sending time for each packet;

a counter updated based on the length of an input packet and a rate determined by a limited flow of packets;

a sending time determining means for determining the sending time of each packet based on the counter value and a present time; and

a sending order control means for managing a sending order of each packet accumulated in the buffer memory, and for sending a read instruction of each packet to the buffer memory, based on the sending time determined by the sending time determining means;

wherein the sending time determining means includes a memory means storing parameters for each of a plurality of control units to independently control packet flow, the parameters determining a state of change of the counter;

when an input packet is written into the buffer memory, the sending time determining means obtains the sending time of the input packet based on the parameters read out from the memory means, the parameters corresponding to the control unit controlling the input packet; and

the sending time determining means updates the parameters based on a newly obtained sending time of the input packet, and transfers the newly obtained sending time of the input packet to the sending order control means.

10. A packet flow control apparatus performing flow control of packets each having variable length, as claimed in any one of claims 1 to 9, wherein the parameters in the memory means are normalized based on a limited flow value, so as to set an update rate of the counter means to “

1”

.

11. A packet flow control apparatus performing flow control of packets each having variable length, as claimed in any one of claims 1 to 9, wherein the sending order control means previously sorts the sending order of the packets accumulated in the buffer memory, based on the sending time information of the packets received from the sending time determining means, into a sorting memory, and performs the read instruction to the buffer memory by searching the packets to be sent at the next time.

12. A packet flow control apparatus performing flow control of packets each having variable length, as claimed in any one of claims 1 to 9, wherein the sending order control means previously sorts the sending order of the packets accumulated in the buffer memory by dividing a plurality of time zones, based on the sending time information of the packets received from the sending time determining means for each divided time zone, into the sorting memory, and performs the read instruction to the buffer memory by searching the packets to be sent at the next time.

13. A packet flow control apparatus performing flow control of packets each having variable length, as claimed in any one of claims 1 to 9, wherein, when the sending time determined by the sending order determining means is large, the sending order control means temporarily stores the sending time to another memory different from the sorting memory, and sorts the sending time into the sorting memory before the sending time.

14. A packet flow control apparatus performing flow control of packets each having variable length, as claimed in any one of claims 1 to 9, wherein a priority order of each packet is added to each sorted information accumulated in the sorting memory of the sending order control means, and, when there are a plurality of packets to be sent at the same sending time zone, the packet having a high priority order is preferentially sent from the sorting memory.

15. A packet flow control apparatus performing flow control of packets each having variable length, as claimed in any one of claims 1 to 9, wherein a packet length of each packet is added to each sorted information accumulated in the sorting memory of the sending order control means, and, when there are a plurality of packets to be sent at the same sending time zone, the packet having a shorter packet length is preferentially sent from the sorting memory.

2. A packet flow control apparatus performing flow control of packets each having variable length comprising:

a buffer memory for temporarily accumulating arrived packets until a sending time for each packet;

a counter updated based on the length of an input packet and a rate determined by a limited flow of packets;

a sending time determining means for determining the sending time of each packet based on the counter value and a present time; and

a sending order control means for managing a sending order of each packet accumulated in the buffer memory, and for sending a read instruction of each packet to the buffer memory, based on the sending time determined by the sending time determining means;

wherein the sending time determining means includes a memory means storing parameters for each of a plurality of control units to independently control the packet flow, the parameters determining a state of change of the counter and including a sending time of a pre-packet belonging to the control unit and a counter value at the sending time;

when an input packet is written into the buffer memory, the sending time determining means obtains the sending time of the input packet and the counter value at the sending time, based on the parameters having the same control unit as the input packet read out from the memory means; and

the sending time determining means updates the parameters having the same control unit in the memory means based on a newly obtained sending time of the input packet and the counter value at the sending time, and transfers the newly obtained sending time of the input packet to the sending order control means.

3. A packet flow control apparatus performing flow control of packets each having variable length, comprising:

a buffer memory for temporarily accumulating arrived packets until a sending time for each packet;

a counter updated based on the length of an input packet and a rate determined by a limited flow of packets;

a sending time determining means for determining the sending time of each packet based on the counter value and a present time; and

a sending order control means for managing a sending order of each packet accumulated in the buffer memory, and for sending a read instruction of each packet to the buffer memory, based on the sending time determined by the sending time determining means;

wherein the sending time determining means includes a memory means storing parameters for each of a plurality of control units to independently control the packet flow, the parameters determining a state of change of the counter and including a recovery time to return the counter value at the sending time of a pre-packet belonging to the control unit, to a limit value;

when an input packet is written into the buffer memory, the sending time determining means obtains the sending time of the input packet and the recovery time to return the counter value at the sending time to the limit value, based on the parameters read out from the memory means; and

the sending time determining means updates the parameters having the same control unit in the memory means based on a newly obtained recovery time of the input packet, and transfers the newly obtained recovery time of the input packet to the sending order control means.

4. A packet flow control apparatus performing flow control of packets each having variable length, comprising:

a buffer memory for temporarily accumulating arrived packets until a sending time for each packet;

a counter updated based on the length of an input packet and a rate determined by a limited flow of packets;

a sending time determining means for determining the sending time of each packet based on the counter value and a present time; and

a sending order control means for managing a sending order of each packet accumulated in the buffer memory, and for sending a read instruction of each packet to the buffer memory, based on the sending time determined by the sending time determining means;

wherein the sending time determining means includes a memory means storing parameters which can determine a state of change of the counter value of the counter means for each of a plurality of control units to independently control packet flow, the parameters determining a state of change of the counter;

when a packet to be sent is read out from the buffer memory, the sending time determining means obtains the sending time of a next packet to be sent after next time within packets belonging to the control unit of the sending packets in the buffer memory, based on the parameter having the same control unit as the sending packet read out from the memory means; and

the sending time determining means updates the parameters having the same control unit in the memory means based on a newly obtained sending time of a next packet, and transfers the newly obtained sending time of the next packet to the sending order control means.

5. A packet flow control apparatus performing flow control of packets each having variable length, as claimed in claim 4, wherein, when there are no packets belonging to the control unit in the buffer memory for the control unit of the input packets, the sending time determining means determines the sending time of the input packet when the input packet is written into the buffer memory, and transfers the sending time to the sending order control means, and updates the parameters in the memory means based on the sending time.

6. A packet flow control apparatus performing flow control of packets each having variable length, comprising:

a buffer memory for temporarily accumulating arrived packets until a sending time for each packet;

a counter updated based on the length of an input packet and a rate determined by a limited flow of packets;

a sending time determining means for determining the sending time of each packet based on the counter value and a present time; and

a sending order control means for managing a sending order of each packet accumulated in the buffer memory, and for sending a read instruction of each packet to the buffer memory, based on the sending time determined by the sending time determining means;

wherein the sending time determining means includes a memory means storing parameters for each of a plurality of control units to independently control the packet flow, the parameters determining a state of change of the counter and including a sending time of a packet belonging to the control unit and a counter value at the sending time;

when a packet to be sent is read out from the buffer memory, the sending time determining means obtains the sending time of a next packet to be sent after next time within packets belonging to the control unit of the sending packets in the buffer memory and a counter value at the sending time, based on the parameter having the same control unit as the sending packet read out from the memory means; and

the sending time determining means updates the parameters having the same control unit in the memory means based on a newly obtained sending time of a next packet and the counter value at the sending time, and transfers the newly obtained sending time of the next packet to the sending order control means.

7. A packet flow control apparatus performing flow control of packets each having variable length, as claimed in claim 6, wherein, when there are no packets belonging to the control unit in the buffer memory for the control unit of the input packets, the sending time determining means determines the sending time of the input packet when the input packet is written into the buffer memory, and transfers the sending time to the sending order control means, and updates the parameters in the memory means based on the sending time.

8. A packet flow control apparatus performing flow control of packets each having variable length, comprising:

a buffer memory for temporarily accumulating arrived packets until a sending time for each packet;

a counter updated based on the length of an input packet and a rate determined by a limited flow of packets;

a sending time determining means for determining the sending time of each packet based on the counter value and a present time; and

a sending order control means for managing a sending order of each packet accumulated in the buffer memory, and for sending a read instruction of each packet to the buffer memory, based on the sending time determined by the sending time determining means;

wherein the sending time determining means includes a memory means storing parameters for each of a plurality of control units to independently control the packet flow, the parameters determining a state of change of the counter and including a recovery time to return the counter value at the sending time of a packet belonging to the control unit to a limit value;

when a packet to be sent is read out from the buffer memory, the sending time determining means obtains the sending time of a next packet to be sent after next time within packets belonging to the control unit of the sending packets in the buffer memory and the recovery time to return a limit value to a counter value at the sending time, based on the parameter having the same control unit as the sending packet read out from the memory means; and

the sending time determining means updates the parameters having the same control unit in the memory means based on a newly obtained recovery time of a next packet, and transfers the newly obtained recovery time of the next packet to the sending order control means.

9. A packet flow control apparatus performing flow control of packets each having variable length, as claimed in claim 8, wherein, when there are no packets belonging to the control unit in the buffer memory for the control unit of the input packets, the sending time determining means determines the sending time of the input packet when the input packet is written into the buffer memory, and transfers the sending time to the sending order control means, and updates the parameters in the memory means based on the sending time.