Adaptive buffer partitioning method for shared buffer switch and switch therefor
View Patent ↗A method for adaptively partitioning a buffer in a shared buffer switch is provided. The buffer partitioning method for a shared buffer switch which has a plurality of input ports, a plurality of output ports, and a shared buffer, the method for determining whether or not to store a cell, which is newly received through one of the input ports, in the shared buffer comprises the steps of (a) determining a buffer area of the shared buffer in which the newly received cell is stored; (b) determining a cell discard threshold with respect to the total number of cells stored in the shared buffer and the changing rate, with respect to time, of the total number of the cells; and (c) determining whether or not to store the newly received cell in the shared buffer, by comparing the number of cells stored in the buffer area in which the newly received cell is to be stored, with the cell discard threshold. In the method, using a cell discard threshold which is determined with respect to the total number of cells stored in a shared buffer and the changing rate of the total number of cells, it is determined whether or not to store a newly received cell. Therefore, the shared buffer switch adaptively handles changes in inflowing traffic volume and changes in outflowing cell traffic volume such that cell loss due to cell discard is effectively prevented.
1. A buffer partitioning method for a shared buffer switch which has a plurality of input ports, a plurality of output ports, and a shared buffer, the method for determining whether or not to store a cell, which is newly received through one of the input ports, in the shared buffer comprising the steps of:
(a) determining a buffer area of the shared buffer in which the newly received cell is stored;
(b) determining a cell discard threshold with respect to the total number of cells stored in the shared buffer and the changing rate, with respect to time, of the total number of the cells; and
(c) determining whether or not to store the newly received cell in the shared buffer, by comparing the number of cells stored in the buffer area in which the newly received cell is to be stored, with the cell discard threshold.
2. The method of claim 1 , wherein the shared buffer switch has a table for storing cell discard thresholds with respect to the total number of cells stored in the shared buffer and the changing rate, with respect to time, of the total number of the cells, and in step (b) a cell discard threshold is determined by referring to a cell discard threshold corresponding to the total number of cells stored in the shared buffer and the changing rate, with respect to time, of the total number of the cells in the table.
3. The method of claim 1 , wherein in step (b) interval i in which the total number of cells stored in the shared buffer is determined after dividing the maximum number of cells that can be stored in the shared buffer into a plurality of intervals, and a cell discard threshold is determined with respect to interval i and the changing rate, with respect time, of the total number of the cells.
4. The method of claim 1 , wherein in step (b) interval j in which the changing rate, with respect to time, of the total number of the cells is determined after dividing a range of the changing rate, with respect to time, of the total number of the cells stored in the shared buffer into a plurality of intervals, and a cell discard threshold is determined with respect to the total number of cells stored in the shared buffer and interval j.
5. The method of claim 1 , wherein in step (b) interval i in which the total number of cells stored in the shared buffer is determined after dividing the maximum number of cells that can be stored in the shared buffer into a plurality of intervals; interval j in which the changing rate, with respect to time, of the total number of the cells is determined after dividing a range of the changing rates, with respect to time, of the total number of the cells stored in the shared buffer into a plurality of intervals; and then a cell discard threshold is determined with respect to interval i and interval j.
6. The method of claim 1 , wherein the shard buffer switch is a common node of a plurality of Virtual Circuits (VCs), and in step (a) a buffer area for storing a newly received cell is determined according to a VC in which the newly received cell is included.
7. The method of claim 6 , wherein each VC has a predetermined service rate, and in step (b) a cell discard threshold is determined with respect to the service rate of a VC in which the newly received cell is included, the total number of cells stored in the shared buffer, and the changing rate, with respect to time, of the total number of cells.
8. The method of claim 7 , wherein the shared buffer switch has a table for storing a cell discard threshold corresponding to the service rate of a VC in which each cell is included, the total number of cells stored in the shared buffer, and the changing rate, with respect to time, of the total number of cells, and in step (b) a cell discard threshold is determined by referring to a cell discard threshold corresponding to the service rate of a VC in which the newly received cell is included, the total number of cells stored in the shared buffer, and the changing rate, with respect to time, of the total number of cells.
9. The method of claim 7 , wherein in step (b) interval v in which the service rate of a VC to which the newly received cell belongs is included is determined after dividing a range of the service rates of the VCs; interval i in which the total number of cells stored in the shared buffer is determined after dividing the maximum number of cells that can be stored in the shared buffer into a plurality of intervals; interval j in which the changing rate, with respect to time, of the total number of the cells is determined after dividing a range of the changing rates, with respect to time, of the total number of the cells stored in the shared buffer into a plurality of intervals; and then a cell discard threshold is determined with respect to intervals v, i andj.
10. A buffer partitioning method for a shared buffer switch which has a plurality of input ports, a plurality of output ports, and a shared buffer, and operates as a common node of a plurality of Virtual Circuits (VCs) having different predetermined service rates, the method for determining whether or not to store a cell, which is newly received through one of the input ports, in the shared buffer comprising the steps of:
(a) determining a buffer area of the shared buffer, in which the newly received cell is stored, according to a VC to which the newly received cell belongs;
(b) determining a reference cell discard threshold with respect to the service rate of the VC to which the newly received cell belongs;
(c) determining a cell discard proportionality constant with respect to the total number of cells stored in the shared buffer and the changing rate, with respect to time, of the total number of the cells;
(d) determining a cell discard threshold by multiplying the reference cell discard threshold by the cell discard proportionality constant; and
(e) determining whether or not to store the newly received cell in the shared buffer, by comparing the number of cells stored in the buffer area in which the newly received cell is to be stored, with the cell discard threshold.
11. The method of claim 10 , wherein the shared buffer switch has a table for storing cell discard proportionality constants with respect to the total number of cells stored in the shared buffer and the changing rate, with respect to time, of the total number of the cells, and in step (c) a cell discard proportionality constant is determined by referring to a cell discard proportionality constant corresponding to the total number of cells stored in the shared buffer and the changing rate, with respect to time, of the total number of the cells in the table.
12. The method of claim 10 , wherein in step (c) interval i in which the total number of cells stored in the shared buffer is determined after dividing the maximum number of cells that can be stored in the shared buffer into a plurality of intervals, and a cell discard proportionality constant is determined with respect to interval i and the changing rate, with respect time, of the total number of the cells.
13. The method of claim 10 , wherein in step (c) interval j in which the changing rate, with respect to time, of the total number of the cells is determined after dividing a range of the changing rate, with respect to time, of the total number of the cells stored in the shared buffer into a plurality of intervals, and a cell discard proportionality constant is determined with respect to the total number of cells stored in the shared buffer and interval j.
14. The method of claim 10 , wherein in step (c) interval i in which the total number of cells stored in the shared buffer is determined after dividing the maximum number of cells that can be stored in the shared buffer into a plurality of intervals; interval j in which the changing rate, with respect to time, of the total number of the cells is determined after dividing a range of the changing rates, with respect to time, of the total number of the cells stored in the shared buffer into a plurality of intervals; and then a cell discard proportionality constant is determined with respect to interval i and interval j.
15. A shared buffer switch comprising:
a plurality of input ports for receiving cells from the outside;
a shared buffer for storing the cells received through the plurality of input ports;
a plurality of output ports for transmitting the cells stored in the shared buffer to the outside; and
a partitioner which determines whether or not to store the cells, which are newly received through one of the input ports, in the shared buffer with respect to the total number of cells stored in the shared buffer and the changing rate, with respect to time, of the total number of the cells, and according to the determination, stores the newly received cells in the shared buffer, or discard the newly received cells.
16. The shared buffer switch of claim 1 , further comprising:
a table for storing cell discard thresholds with respect to the total number of cells stored in the shared buffer and the changing rate, with respect to time, of the total number of the cells.
17. The shared buffer switch of claim 15 , wherein the shared buffer switch is a common node of a plurality of Virtual Circuits (VCs) having different predetermined service rates, and has a table for storing cell discard thresholds with respect to the service rate of a VC to which each cell belongs, the total number of cells stored in the shared buffer and the changing rate, with respect to time, of the total number of the cells.
18. The shared buffer switch of claim 15 , wherein the shared buffer switch is a common node of a plurality of Virtual Circuits (VCs) having different predetermined service rates, and has a table for storing cell discard proportionality constants with respect to the total number of cells stored in the shared buffer and the changing rate, with respect to time, of the total number of the cells.