# US 2003/0067931 A1 · Buffer management policy for shared memory switches

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2003/0067931 A1
- Document ID: US20030067931A1
- Status: Published application
- Kind: A1
- Application number: 09/918,347
- Filed: 2001-07-30
- Published: 2003-04-10
- Earliest claimed: 2001-07-30
- Inventors: Yishay Mansour; Alexander Kesselman
- Web page: https://patentgrep.com/patent/US20030067931A1

## CPC

- H04L 49/254: {Centralised controller, i.e. arbitration or scheduling}
- H04L 49/90: Buffering arrangements
- H04L 49/103: using a shared central buffer; using a shared memory
- H04L 49/3027: {Output queuing}
- H04L 49/503: {Policing}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A method for allocating space among a plurality of queues in a buffer includes sorting all the queues of the buffer according to size, thereby to establish a sorted order of the queues. At least one group of the queues is selected, consisting of a given number of the queues in accordance with the sorted order. A portion of the space in the buffer is allocated to the group, responsive to the number of the queues in the group. A data packet is accepted into one of the queues in the group responsive to whether the data packet will cause the space occupied in the buffer by the queues in the group to exceed the allocated portion of the space.

## Claims

### Claim 1

A method for allocating space among a plurality of queues in a buffer, comprising:
sorting all the queues of the buffer according to size, thereby to establish a sorted order of the queues;
selecting at least one group of the queues consisting of a given number of the queues in accordance with said sorted order;
allocating a portion of the space in the buffer to said at least one group, responsive to the number of the queues in said at least one group; and
accepting a data packet into one of the queues in said at least one group responsive to whether the data packet will cause the space occupied in the buffer by the queues in the group to exceed the allocated portion of the space.

### Claim 2 (depends on 1)

A method according to claim 1, wherein selecting said at least one group comprises selecting for inclusion in said at least one group the queues that are largest among said plurality of queues.

### Claim 3 (depends on 2)

A method according to claim 2, wherein allocating the portion of the space comprises setting a size of the space proportional to a sum of a harmonic series.

### Claim 4 (depends on 3)

A method according to claim 3, wherein setting the size of the space comprises establishing a total maximum buffer size Bk for the k largest output queues, wherein Bk is substantially given by
25 B k = M ( ln ⁢ ⁢ N + 1 ) ⁢ ∑ i = 1 k ⁢ 1 i
wherein M is the total buffer space available to all queues, N is the number of output queues, and i is an integer index.

### Claim 5 (depends on 4)

A method according to claim 4, wherein selecting the number k of the queues comprises selecting a fixed number of the queues.

### Claim 6 (depends on 4)

A method according to claim 4, wherein k has a variable value.

### Claim 7 (depends on 6)

A method according to claim 6, wherein k and Bn are set in accordance with the equation:
26 B k = ( n + m c n + 1 ) · M log c ⁢ N
wherein n, c and m are parameters such that 1<c<N, and n is the largest integer such that m and k satisfy the conditions
0≦m≦cn+1 and 27 k = ∑ i = 1 n ⁢ c i + m .

### Claim 8 (depends on 2)

A method according to claim 2, wherein buffer space is allocated within said at least one group of queues in accordance with a set of conditions which functionally define a known buffer management policy.

### Claim 9 (depends on 8)

A method according to claim 8, wherein said known buffer management policy is chosen from a group consisting of complete partitioning (CP), sharing with maximum queue lengths (SMXQ), sharing with minimum allocation (SMA), sharing with maximum queue length and minimum allocation (SMQMA), and dynamic threshold (DT).

### Claim 10 (depends on 2)

A method according to claim 2, wherein said given number is fixed.

### Claim 11 (depends on 2)

A buffer management policy according to claim 2, wherein said given number and said portion of the space in the buffer are variable.

### Claim 12

A method for allocating space among N output queues in a buffer of size M, which comprises:
sorting all the queues of the buffer according to size, thereby to establish a sorted order of the queues;
selecting a number k of said N output queues in accordance with said sorted order;
establishing a total maximum buffer space of Bk for said number k of said N output queues, wherein Bk<M;
ascertaining whether acceptance of an arriving packet destined for one of said number k of said N output queues will cause the space in the buffer used by said k queues together to exceed Bk; and
if the acceptance of an arriving packet destined for one of said k queues will cause the space used by said k queues together to exceed Bk, rejecting said packet.

### Claim 13 (depends on 12)

A method according to claim 12, wherein said selecting a number k of said N output queues comprises selecting a number k of said N output queues that are largest among said N output queues.

### Claim 14 (depends on 13)

A method according to claim 13, wherein establishing the total maximum buffer space comprises setting the maximum buffer size such that Bk is substantially given by
28 B k = M ( ln ⁢ ⁢ N + 1 ) ⁢ ∑ i = 1 k ⁢ 1 i
wherein M is the total buffer space available to all queues, and N is the number of output queues, and i is an integer index which refers to an ordinal ranking of the queue size.

### Claim 15 (depends on 13)

A method according to claim 13, wherein the buffer space is allocated within said number k of said N output queues in accordance with a set of conditions which functionally define a known buffer management policy

### Claim at position 16 (depends on 15)

16 A method according to claim 15, wherein said known buffer management policy is chosen from a group consisting of complete partitioning (CP), sharing with maximum queue lengths (SMXQ), sharing with minimum allocation (SMA), sharing with maximum queue length and minimum allocation (SMQMA), and dynamic threshold (DT).

### Claim 17 (depends on 12)

A method according to claim 12, wherein selecting the number k of the queues comprises selecting a fixed number of the queues.

### Claim 18 (depends on 12)

A method according to claim 12, wherein the value of k is variable.

### Claim 19 (depends on 18)

A method according to claim 18, wherein the values of k and Bn are set in accordance with the equation
29 B k = ( n + m c n + 1 ) · M log c ⁢ N
wherein n, c and m are parameters such that 1<c<N, and n is the largest integer such that m and k satisfy the conditions:
0≦m≦cn+1 and 30 k = ∑ i = 1 n ⁢ c i + m .

### Claim 20

A shared memory switch comprising:
a memory providing buffer space of size M, which is adapted to contain a plurality of output queues; and
a controller, coupled to sort all the queues of the buffer according to size, thereby to establish a sorted order of the queues, and to allocate the space in the buffer to the output queues in accordance with said sorted order such that a portion of the space is allocated to a group of the queues consisting of a given number of the queues that are largest among the plurality of the queues responsive to the given number of the queues in the group.

### Claim 21 (depends on 20)

A switch according to claim 20, wherein said portion of the space is allocated by setting a size of the space proportional to a sum of a harmonic series.

### Claim 22 (depends on 21)

A switch according to claim 21, wherein said portion of the space is allocated for the k largest output queues and the total maximum buffer size Bk for said k largest output queues is substantially given by
31 B k = M ( ln ⁢ ⁢ N + 1 ) ⁢ ∑ i = 1 k ⁢ ⁢ 1 i
wherein i is an integer index which refers to an to ordinal ranking of the queue size.

### Claim 23 (depends on 22)

A switch according to claim 22, wherein said portion of the space is allocated for the k largest output queues and the total maximum buffer size Bk for said k largest output queues is substantially given by the equation
32 B k = ( n + m c n + 1 ) · M log c ⁢ N
wherein n, c and m are parameters such that 1<c<N, and n is the largest integer such that m and k satisfy the conditions
0≦m≦cn+1 and 33 k = ∑ i = 1 n ⁢ ⁢ c i + m .

### Claim 24 (depends on 20)

A shared memory switch according to claim 20, wherein said switch has N output lines and N corresponding output queues, wherein said given number is denoted by k and said portion of the space available for the k largest output queues is denoted by Bk, wherein Bk<M.

### Claim 25 (depends on 24)

A shared memory switch according to claim 24, wherein Bk is substantially given by the equation
34 B k = M ( ln ⁢ ⁢ N + 1 ) ⁢ ∑ i = 1 k ⁢ ⁢ 1 i
wherein i is an integer index which refers to the ordinal ranking of the queue in terms of the queue size.
