Method and apparatus for probabilistic allocation in a switch packet buffer
View Patent ↗Systems and methods of writing data to a buffer during a buffer cycle are described. The buffer has a plurality of buffer banks having various fill levels. The buffer determines a first portion of banks from the plurality of buffer banks. The first portion of banks unfilled banks. A rank can be assigned to each of the first portion of banks and a candidate set of banks chosen from the first portion of banks. A target bank is then chosen from the candidate set and the data is written to that bank. The ranking may be random. Furthermore, the target bank can be chosen based on ranking, fill level, or both.
1. A method of writing, during a read/write cycle, data to a buffer having a plurality of banks, the method comprising:
identifying unfilled banks of the plurality of banks to define a first subset of banks of the plurality of banks, each bank in the first subset of banks having a corresponding fill level value;
assigning, independently of the corresponding fill level value, an ordered rank to the unfilled banks in the first subset of banks;
selecting a pre-determined number of banks of the first subset of banks having the lowest fill level values to form a candidate set of banks;
choosing a first bank from the candidate set based on the corresponding fill level value and the ordered rank of the banks in the candidate set; and
writing at least a portion of the data to the first bank.
2. The method of claim 1 , wherein selecting the candidate set includes excluding any banks that have a read access during the read/write cycle from the candidate set.
3. The method of claim 1 , wherein the pre-determined number of banks in the first subset is greater than or equal to the number of read/write commands that are processed during a read/write cycle of the buffer.
4. The method of claim 1 , wherein the ordered rank is randomly assigned to the first subset of banks.
5. The method of claim 1 , wherein choosing the first bank comprises:
determining that two banks have the same fill level value; and
choosing from among the two banks the bank having the highest ordered rank.
6. The method of claim 1 , further comprising masking a least significant portion of the fill level value for the banks in the first subset of banks so as to create a modified fill level value for each bank in the first subset of banks.
7. The method of claim 6 , wherein selecting the pre-determined number of banks of the first subset of banks is based on the modified fill level values of the corresponding banks in the first subset of banks.
8. The method of claim 7 , wherein choosing the first bank from the candidate set is based on at least one of the respective modified fill level value and the ordered rank of the banks in the candidate set.
9. The method of claim 1 , further comprising determining that the data is multicast data.
10. The method of claim 9 , wherein choosing the first bank comprises randomly selecting a bank from the candidate set without considering fill values.
11. A system configured to write data to a buffer during a read/write cycle, the system comprising:
a hardware-based buffer comprising a plurality of banks configured to store data packets; and
a hardware-based controller configured to:
identify unfilled banks of the plurality of banks to define a first subset of banks of the plurality of banks, each bank in the first subset of banks having a corresponding fill level value;
assign, independently of the corresponding fill level value, an ordered rank to unfilled banks in the first subset of banks;
select a predetermined number of banks of the first subset of banks having the lowest fill level values to form a candidate set of banks from the first subset of banks;
choose a first bank from the candidate set of banks based on the corresponding fill level value and the ordered rank of the banks in the candidate set; and
write at least a portion of the data to the first bank.
12. The system of claim 11 therein the controller is further configured to exclude any banks that have a read access during the read/write cycle from the candidate set.
13. The system of claim 11 , wherein the pre-determined number of banks in the first subset is greater than or equal to the number of read/write commands that are processed during a read/write cycle of the buffer.
14. The system of claim 11 , wherein the ordered rank is randomly assigned to the first subset of banks.
15. The system of clam 11 , wherein the controller is configured to choose the bank having a highest ordered rank when two banks have the same fill level value.
16. A method of writing, during a read/write cycle, data to a buffer having a plurality of banks, the method comprising:
identifying unfilled banks of the plurality of banks to define a first subset of banks of the plurality of banks, each bank in the first subset of banks having a corresponding fill level value;
randomly assigning a rank to the unfilled banks in the first subset of banks;
masking a least significant portion of the fill level value for the banks in the first subset of banks so as to create a modified fill level value for each bank in the first subset of banks;
selecting a pre-determined number of banks of the first subset of banks having the lowest modified fill level values to form a candidate set of banks;
choosing a first bank from the candidate set having the lowest respective modified fill level value, including choosing the bank with the highest rank if two or more banks have the lowest respective modified fill level value; and
writing at least a portion of the data to the first bank.
17. The method of claim 16 , wherein selecting the candidate set includes excluding any banks that have a read access during the read/write cycle from the candidate set.
18. The method of claim 16 , wherein the pre-determined number of banks in the first portion is greater than or equal to the number of read/write commands that are processed during a read/write cycle of the buffer.
19. The method of claim 16 , further comprising:
choosing a second bank from the candidate set having the second lowest respective modified fill level value, including choosing the second hank with the highest remaining rank if two or more banks have the second lowest respective modified fill level value; and
writing at least a portion of the data to the second bank.