Network node for sharing a common buffer among multiple connections while ensuring minimum bandwidth for each connection

• US 6,173,331 B1
• Filed: 10/05/1998
• Issued: 01/09/2001
• Est. Priority Date: 10/03/1997
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Shimonishi, Hideyuki
• Primary Examiner(s): VU, VIET DUY
• Application Number:
  US09/166,377
• Time in Patent Office: 827 Days
• Field of Search: 709/213, 709/223, 709/226, 709/230, 709/231, 709/232, 709/235, 709/238, 709/234, 709/250, 710/29, 710/52, 710/56, 370/229, 370/230, 370/235
• US Class Current: 709/232
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5681 Buffer or queue management

Abstract

A network node includes a single buffer connected to a transmission medium. Detection circuitry receives an incoming packet and detects the virtual connection of the received packet Control circuitry calculates a value of delivery instant for the received packet according to a minimum bandwidth assigned co the detected virtual connection so that vacancy of the transmission medium is reduced to a minimum if the received packet were delivered from the buffer onto the transmission medium at the instant of the calculated value. The calculated value is compared with a decision threshold assigned to the detected virtual connection. The received packet is stored into the buffer if the calculated value is smaller than the decision threshold or discarded if the calculated value is greater than the decision threshold.

Claims

1. A network node comprising:

a first-in-first-out buffer connected to a transmission medium;

detection circuitry for receiving an incoming packet and detecting a virtual connection of the received packet; and

control circuitry for calculating a value of delivery instant according to a minimum bandwidth assigned to the detected virtual connection so that vacancy of said transmission medium is reduced to a minimum if the received packet were delivered from said buffer onto said transmission medium at the instant of the calculated value, comparing the calculated value with a decision threshold assigned to the detected virtual connection, storing the received packet into said buffer if the calculated value is smaller than the decision threshold, and discarding the received packet if the calculated value is greater than the decision threshold.

2. The network node of claim 1, wherein said control circuitry is arranged to calculate said value according to a data length of the received packet.

3. The network node of claim 1, wherein said control circuitry is arranged to calculate said value according to a weight coefficient assigned to the detected virtual connection.

4. The network node of claim 1, wherein said control circuitry is arranged to:

monitor a queue length of packets stored in said buffer; and

decrease said assigned minimum bandwidth if the queue length is greater than a predetermined length.

5. The network node of claim 1, wherein said control circuitry is arranged to:

monitor a queue length of packets stored in said buffer; and

decrease said decision threshold if the queue length is greater than a predetermined length.

6. A network node comprising:

first and second first-in-first-out buffers connected to a transmission medium;

detection circuitry for receiving an incoming packet and detecting a virtual connection and a class of the received packet; and

control circuitry for calculating a value of delivery instant according to a minimum bandwidth assigned to the detected virtual connection so that vacancy of said transmission medium is reduced to a minimum if the received packet were delivered from either of said buffers onto said transmission medium at the instant of the calculated value, comparing the calculated value with a decision threshold assigned to the detected virtual connection, storing the received packet into one of said buffers depending on the detected class of the packet if the calculated value is smaller than the decision threshold, discarding the received packet if the calculated value is greater than the decision threshold, monitoring storage level of said first buffer and delivering packets from the second buffer onto the transmission medium if the first buffer is vacant and packets from the first buffer onto the transmission medium if the first buffer is not vacant.

7. The network node of claim 6, wherein said control circuitry is arranged to calculate said value according to a data length of the received packet.

8. The network node of claim 6, wherein said control circuitry is arranged to calculate said value according to a weight coefficient assigned to the detected virtual connection.

9. A network node comprising:

a first-in-first-out buffer connected to a transmission medium;

a memory; and

an LSI (large scale integration) chip including;

detection circuitry for receiving an incoming packet and detecting a virtual connection of the received packet, and

control circuitry for reading a calculated value of delivery instant from said memory, recalculating a value of delivery instant using the value read from said memory according to a minimum bandwidth assigned to the detected virtual connection so that vacancy of said transmission medium is reduced to a minimum if the received packet were delivered from said buffer onto said transmission medium at the instant of the recalculated value, comparing the recalculated value with a decision threshold assigned to the detected virtual connection, storing the received packet into said buffer if the recalculated value is smaller than the decision threshold, discarding the received packet and resetting the recalculated value to the read value if the recalculated value is greater than the decision threshold, and storing both of the recalculated and reset values of delivery instant into said memory.

10. The network node of claim 9, wherein said control circuitry is arranged to calculate said value according to a data length of the received packet.

11. The network node of claim 9, wherein said control circuitry is arranged to calculate said value according to a weight coefficient assigned to the detected virtual connection.

12. The network node of claim 9, wherein said control circuitry is arranged to:

monitor a queue length of packets in said buffer; and

decrease said assigned minimum bandwidth if the queue length is greater than a predetermined length.

13. The network node of claim 9, wherein said control circuitry is arranged to:

monitor a queue length of packets in said buffer; and

decrease said decision threshold if the queue length is greater than a predetermined length.

14. A method of controlling packets to be discarded or stored into a first-in-first-out buffer connected to a transmission medium, comprising the steps of:

a) receiving an incoming packet and detecting a virtual connection of the received packet;

b) calculating a value of delivery instant according to a minimum bandwidth assigned to the detected virtual connection so that vacancy of said transmission medium is reduced to a minimum if the received packet were delivered front said buffer onto said transmission medium at the instant of the calculated value;

c) comparing the calculated value with a decision threshold assigned to a connection indicated by said identifier; and

d) storing the received packet into said buffer if the calculated value is smaller than the decision threshold, and discarding the received packet if the calculated value is greater than the decision threshold.

15. The method of claim 14, wherein the step (b) comprises calculating said value of delivery instant according to a weight coefficient assigned to the detected virtual connection.

16. The method of claim 14, wherein the step (b) comprises calculating said value of delivery instant according to a weight coefficient assigned to the detected virtual connection.

17. The method of claim 15, wherein the step (b) further comprises the steps of;

monitoring a queue length of packets in said buffer; and

decreasing said assigned minimum bandwidth if the queue length is greater than a predetermined length.

18. The method of claim 14, wherein the step (b) further comprises the steps of:

monitoring a queue length of packets in said buffer; and

decreasing said decision threshold if the queue length is greater than a predetermined length.

19. A method of controlling packets to be discarded or stored into first and second first-in-first-out buffers connected to a transmission medium, comprising;

the steps of;

a) receiving an incoming packet and detecting a virtual connection and a class of the received packet; and

b) calculating a value of delivery instant according to a minimum bandwidth assigned to the detected virtual connection so that vacancy of said transmission medium is reduced to a minimum if the received packet were delivered from either of said buffers onto said transmission medium at the instant of the calculated value;

c) comparing the calculated value with a decision threshold assigned to the detected virtual connection;

d) storing the received packet into one of said first and second buffers depending on the detected class if the calculated value is smaller than the decision threshold;

e) discarding the received packet if the calculated value is greater than the decision threshold; and

f) monitoring storage level of said first buffer and delivering packets from the second buffer onto the transmission medium if the first buffer is vacant and packets from the first buffer onto the transmission medium if the first buffer is not vacant.

20. A method of controlling packets, comprising the steps of:

a) receiving an incoming packet and detecting a virtual connection of the received packet;

b) reading a calculated value of delivery instant of the received packet from a memory;

c) recalculating a value of delivery instant of the received packet using the value read from said memory according to a minimum bandwidth assigned to the detected virtual connection so that vacancy of said transmission medium is reduced to a minimum if the received packet were delivered from said buffer onto said transmission medium at the instant of the recalculated value;

d) comparing the recalculated value with a decision threshold assigned to the detected virtual connection;

e) storing the received packet into said buffer if the recalculated value is smaller than the decision threshold;

f) discarding the received packet and resetting the recalculated value to the read value if the recalculated value is greater than the decision threshold; and

g) storing both of the recalculated and reset values of delivery instant into said memory.

21. A method of controlling packets, comprising the steps of:

a) receiving a packet of a particular virtual connection or a packet of other virtual connection, detecting a time interval between a previous packet and the received packet, and setting an arrival time value V of every packet to a previous variable plus the detected time interval;

b) setting an arrival time value R of the packet of said particular virtual connection to the arrival time value V;

c) updating the previous variable with a minimum bandwidth value assigned to said particular virtual connection, said arrival time values V and R and a previous delivery time value F of the packet of said particular virtual connection;

d) updating the previous delivery time value F with said minimum bandwidth value and the arrival time value V;

e) comparing the updated delivery time value F with a decision threshold which is equal to the arrival time value V plus a threshold value assigned to said particular virtual connection;

storing the packet of said particular virtual connection into a first-in-first-out buffer if the updated delivery time value F is smaller than the decision threshold and resetting the updated delivery time value F to the previous delivery time value and discarding the packet of said particular virtual connection if the updated delivery time value F is greater than said decision threshold; and

g) repeating the steps (a) to (f).

22. The method of claim 21, wherein the step (c) comprises updating the previous variable with a length of the packet of said particular virtual connection in addition to said minimum bandwidth value.

23. A method of controlling packets, comprising the steps of:

a) setting an arrival time value V equal to a previous variable plus unity and updating the previous variable with a time interval T which is an integral multiple of a minimum interval between successive packets of any virtual connection;

b) receiving a packet of a particular virtual connection or a packet of other virtual connection and comparing the arrival time value V with a previous arrival time value R of the packet of the particular virtual connection;

c) if the arrival time value V is not equal to the previous arrival time value R, updating the previous variable with a previous delivery time value P of the packet of said particular virtual connection, the arrival time value V weighted by a coefficient assigned to said particular virtual connection and the previous arrival time value R weighted by said coefficient, and setting a current arrival time R of the packet of said particular virtual connection to the arrival time value V;

d) updating the previous delivery time value F with the weighted arrival time value V;

e) if the arrival time V is equal to the previous arrival time value R, repeating the step (d);

f) comparing the updated delivery time value F with a decision threshold which is equal to the weighted arrival time value V plus a threshold value assigned to said particular virtual connection;

g) storing the packet of said virtual connection into a first-in-first-out buffer if the updated delivery time value F is smaller than the decision threshold and resetting the updated delivery time value F to the previous delivery time value and discarding the packet of said particular virtual connection if the updated delivery time value F is greater than said decision threshold; and

h) repeating the steps (b) to (g) if a packet arrives; and

i) repeating the step (a) at T-intervals.