CN112088521A - Memory device for high-bandwidth and high-capacity switch - Google Patents

Abstract

The present invention provides a shared memory device for a high bandwidth, high capacity switch. The memory device includes a plurality of memory blocks. The memory device also includes a plurality of ingress pipes, where each ingress pipe is to request a data packet to be written to the memory chunk. The memory device also includes a plurality of egress pipes, wherein each egress pipe is configured to request a data packet to be read from the memory block. Such that each outlet pipe is associated with (soft-allocates to) the set of memory chunks.

Description

A memory device for high-bandwidth, high-capacity switches

technical field

The present invention relates to the use of high capacity, high bandwidth switches in network systems. In particular, the present invention relates to memory devices for such switches, and switches including such memory devices. The memory device provides the realization of a new memory block allocation scheme for the inlet pipe and the outlet pipe, respectively. The new allocation scheme is particularly suitable for providing shared memory architectures with multiple memory blocks. The invention also relates to a corresponding control method for a memory device.

Background technique

Traditional switches typically contain multiple bidirectional ports. Incoming traffic (usually Ethernet packets) from an input port is directed to an output port based on decisions made within the switch.

A port is usually identified by its speed, and the speed is usually the same for input and output. For example, a 100Gbps port (100 gigabits per second) can receive traffic at 100Gbps and send traffic at 100Gbps.

The conventional switch also includes memory for temporarily holding incoming traffic before sending it to an egress port. There are many reasons to control traffic inside the switch, such as:

1. Multiple input ports can receive traffic directed to a single output port (many-to-one). If the output port cannot carry all the traffic received, some traffic received by the output port must be temporarily saved.

2. The back pressure applied to the output port from outside the switch can prevent further output traffic to the output port. Therefore, all incoming traffic directed to this port must be temporarily saved.

3. The scheduling rate of the output port is a parameter inside the switch, which can be used to limit the output rate of a certain port. Therefore, incoming traffic directed to the port must be temporarily saved.

Memory in high-capacity, high-bandwidth switches is typically built as shared memory. That is, the memory is shared by all output ports. The main advantage of shareability is less memory than having dedicated memory for each output port.

A simplified architecture diagram of a traditional switch is shown in Figure 7. Incoming traffic from different input ports passes through a classification engine that selects output ports and corresponding queues for storing the received traffic. The classification engine also determines any edits that may be required for the incoming traffic. After classification, the traffic is stored in memory to temporarily cache the received traffic. The memory is virtually queued and managed as a queue. Queues, buffer management, and scheduling to output ports are managed by the control logic. The queue can be in any form, such as input queue, output queue, virtual output queue (VOQ), etc.

In traditional high-capacity, high-bandwidth switches, the memory fabric is typically shared by all output ports. This means that incoming traffic from any input port and directed to any output port can be written to this shared memory. Algorithms exist for managing memory for each output port. The switch is typically constructed from a single piece of silicon, ie, it is a single device such that all high-speed access to the shared memory is confined to the device, with no external interface. External interfaces may result in the switch being impractically constructed as a single device.

Disadvantageously, the shared memory architecture of the conventional switch has limitations when dedicated to high capacity, high bandwidth switches.

First, in the worst case, i.e. when the switch is fully utilized, i.e. 100% loaded, a single switch with N ports must support N*B write bandwidth and N* from the shared memory Read bandwidth of B, where each port supports B bandwidth (ie, 10Gbps, 100Gbps, etc.). For example, in the worst case, a 64-port switch must support 6.4Tbps read bandwidth and 6.4Tbps write bandwidth from the shared memory, where each port supports 100Gbps.

Second, since network traffic is composed of packets of variable size (for example, Ethernet packets can be 64 bytes in size, but cannot exceed 9KB at most), since the shared memory in the switch is of fixed width (each memory location contains C bytes), therefore, each arriving packet must be written to the shared memory in chunks of size C bytes. The size of the last data block can be 1 byte, up to C bytes. In the worst case, if the incoming traffic contains a stream of packets of size (C+1) bytes, each packet must be written to two locations in said shared memory and sent to The output port is read from two locations in the memory. In this scenario, the bandwidth requirement of the memory is doubled to a maximum of 2*N*B for reading and 2*N*B for writing.

Third, typically in such high bandwidth, high capacity switches, the cache shared memory is implemented in the switch. The shared memory is typically built from single-ported memory blocks to save silicon area, rather than dual-ported memory blocks that are twice the size of single-ported memory blocks. A single-port memory block can only perform 1 read or 1 write per clock, but not both. This means that shared memory built from single-ported memory blocks must again double the bandwidth capacity to support N*B bandwidth for simultaneous reads and writes.

Fourth, it is impossible to support such high bandwidth requirements from a single block of single-port memory due to physical limitations of operating frequency. For example, a 64-port switch and a 100Gbps port must support a read bandwidth of 6.4Tbps and a write bandwidth of 6.4Tbps for shared memory, regardless of the speedup required to split packets into fixed size C. For a split size of 64 bytes, or memory width, a 12.8Tbps single-port memory should run at 25GHz to be able to maintain the required bandwidth. When the required bandwidth is doubled, the frequency is even higher in order to support C+1 sized packet flows. Increasing the C value for wider memory has an impact on memory speed and silicon area (memory speed and silicon area of the memory and logic to support C).

In order to solve the above-mentioned bandwidth problem of the shared memory architecture, multiple memory blocks of a single-port memory are usually used instead of one memory block. Specifically, using the multiple memory blocks is divided into two steps:

1. Bundling a set of ports (bundled into tubes) such that at operating frequency and worst-case traffic scenario (100% load and segmentation), the selected segment size C is sufficient to provide C per clock cycle, without creating arbitrary bottlenecks.

2. M memory blocks are connected in parallel so that each pipe can access the memory block for reading or writing.

Figure 8 shows the architecture. At each clock cycle, each input pipe (also called an entry pipe or pipe) can request a write to the shared memory, and each output pipe (also called an exit pipe or pipe) can request a write from the shared memory to read. For proper operation, for a given number P of pipes, the number M of memory blocks should be at least 2P memory blocks so that P reads and P writes can be performed in the same clock cycle (simultaneously).

The "Queue Engine and Control" block accepts write requests per clock from all ingress pipes, and each clock accepts read requests from all egress pipes. The block then decides which egress pipe performs reads from which memory block, and which ingress pipe performs writes to which memory block.

The order of reads from the egress pipe depends on the scheduling algorithm, independent of the location of the data packet in the memory block, and independent of the scheduling decisions of other egress pipes.

If two or more egress pipes request a read from the same memory block, only one egress pipe is granted read permission, while the rest will wait and will not perform reads for that clock cycle. This scenario is called a conflict. Since reads must be in order, and since the fragments of the data packets must be transmitted in the order of the original packets, in a typical implementation, read operations cannot be out-of-order.

The combined read and write process for the architecture shown in FIG. 8 is described herein. Each clock cycle, the control logic accepts W write requests from entry pipes and R read requests from exit pipes (not all pipes request a read or write every clock cycle). The control logic then selects memory blocks for reading and writing based on the request as follows:

1. Select the memory block for reading.

a. Perform maximum matching of the exit pipes (up to P) requested for reading with the corresponding memory blocks (M).

b. Note that not all read requests can be supported on the same clock cycle due to possible collisions.

c. Set matching pair {exit pipe, memory block}.

2. Select the memory block for writing.

a. Set the list of memory blocks (M') available for writing.

i. Any memory block not selected for reading and not full.

b. Out of the list of M' memory blocks, select W memory blocks and attach them to entry pipes with valid write requests respectively.

ii. Select the memory block using one of the following mechanisms:

1. The polling order among all available memory blocks.

2. Create a list of memory blocks according to the occupancy level from small to large, and select W memory blocks with the smallest occupancy level.

c. Set matching pair {entry pipe, memory block}.

In a traditional shared memory architecture using multiple memory blocks, read bandwidth is disadvantageously reduced due to possible conflicts between read requests for the same memory block from different exit pipes.

It is important to note that read requests from an outlet pipe are counted at each outlet pipe, regardless of requests from other outlet pipes. Therefore, two or more exit pipes may request to perform reads from the same memory block at the same time. In fact, for a given number of memory blocks, the probability of arbitrary collisions increases with the number of pipes, and for a given number of pipes, the probability of arbitrary collisions decreases with the number of memory blocks.

The following equation calculates the probability of no conflict at all:

where M is the number of memory blocks and P is the number of exit pipes requested to be read.

Therefore, the probability of any collision is:

E.g:

· For 32 memory blocks and 4 exit pipes: P(collision) = 0.177

· For 32 memory blocks and 8 exit pipes: P(collision) = 0.614

· For 32 memory blocks and 12 exit pipes: P(collision) = 0.857

· For 32 memory blocks and 16 exit pipes: P(collision) = 0.990

Accordingly, in the conventional shared memory architecture, there is a high probability of collusion. Therefore, at maximum possible capacity, in worst-case traffic scenarios, and in worst-case collusion mode (e.g. all reads in the same clock cycle are requested to a particular memory block , so the last pipe reads after waiting P–1 clock cycles), the shared memory bandwidth is too low to support outgoing traffic.

Various mechanisms have been proposed to reduce the amount of latency increase and bandwidth reduction caused by read collision phenomena, such as:

1. Input Queue: Hard-allocate memory blocks for input pipes: This mechanism has good memory utilization and simpler logic. However, it produces a high collision rate on the read side and can lead to head-end jamming.

2. Output Queue: Hard-allocate memory blocks for output pipes: This mechanism has simplified logic and eliminates read conflicts, but memory utilization is low and memory cannot be shared.

3. Increase the number of memory blocks relative to the number of tubes: This mechanism results in increased silicon area for memory blocks and logic (multiplexers and demultiplexers).

4. Reads of segments may be out-of-order and reordered at each exit pipe: With this mechanism, the latency problem is not resolved because reads of sequential segments need to be waited before starting a transfer.

5. Use dual-port memory blocks instead of single-port memory blocks: Under this mechanism, the silicon area of the memory block is doubled for the same total shared memory size.

SUMMARY OF THE INVENTION

In view of the above disadvantages, the present invention aims to improve the traditional shared memory architecture and the proposed mechanism. In particular, the present invention aims to provide a shared memory architecture that improves latency and throughput. Therefore, an object of the present invention is to significantly reduce the collision probability in order to avoid an increase in shared memory bandwidth. Ideally, the possibility of read collusion is even completely eliminated.

The object of the invention is achieved by the solutions provided in the disclosed independent claims. Advantageous implementations of the invention are further defined in the dependent claims.

A first aspect of the present invention provides a memory device for a switch. The memory device includes a plurality of memory blocks, a plurality of ingress pipes, and a plurality of egress pipes, wherein each ingress pipe is used to request data packets to be written into the memory block, and each egress pipe is used to request a read from the memory block Taking packets, each egress pipe is associated with the set of memory blocks.

A "collection" is a group of memory blocks associated with a single outlet pipe. "Associated" means that these memory blocks are the preferred memory blocks for writing packets destined for the associated egress pipe, and are the preferred memory blocks for the associated egress pipe to perform reads. However, if more writes are required at the same time, the remaining writes can also be allocated to other memory blocks, so the exit pipe can also read from the other memory blocks.

By associating the egress pipe with a set of memory blocks, the rights of arriving packets are controlled by the memory device, thus at least significantly reducing the probability of read collusion. Since these drawbacks are often caused by collusion of reads of the same memory block by different exit pipes, the probability of high latency and low throughput is also reduced. Therefore, the memory device of the first aspect supports an improved switch for higher bandwidth and capacity.

In an implementation manner of the first aspect, the sets are disjoint sets.

This minimizes the possibility of collusion, and possibly even no collusion at all, optimally reducing latency and increasing throughput.

In another implementation of the first aspect, each set includes the same number of memory blocks.

This allows the memory device to be efficiently implemented as a shared memory architecture for the switch.

In another implementation of the first aspect, the memory device includes a controller for selecting a memory block for the egress pipe from the set associated with the egress pipe requesting the read packet, for the reading of the data packet.

In another implementation of the first aspect, the controller is further configured to request to write an entry of a data packet destined for the determined egress pipe from a set associated with the determined egress pipe The pipe selects the memory block for the writing of the packet.

The controller may be a processor. The controller specifically enables "soft allocation" (ie, association) of memory blocks and exit pipes to reduce the probability of read collusion.

In another implementation of the first aspect, the controller is further configured to: when selecting the memory block from the set associated with the determined outlet pipe for the data packet When writing, exclude one or more full memory blocks.

The efficiency of memory block allocation is further improved.

In another implementation of the first aspect, if the total number of write requests for data packets destined for the determined egress pipe is less than a write allowed in the set associated with the determined egress pipe The controller is further configured to select a memory block from the write-allowed memory blocks in the set associated with the determined outlet pipe based on the minimum occupancy rate or randomly.

This reduces the number of controller selections, which increases allocation efficiency and reduces the likelihood of collusion.

In another implementation of the first aspect, if the total number of write requests for data packets destined for the determined egress pipe is greater than write allowed in the set associated with the determined egress pipe the number of incoming memory blocks, the controller is also used to create a list of all ingress pipes with outstanding write requests.

This allows the controller to monitor all outstanding write requests in order to process all requests more efficiently.

In another implementation of the first aspect, if the total number of write requests for data packets destined for the determined egress pipe is greater than write allowed in the set associated with the determined egress pipe the number of incoming memory blocks, the controller is further configured to select the memory block from another set not associated with the determined egress pipe to write the data packet, specifically , allocates the remaining block of free memory for each outstanding write request.

This ensures that the possibility of collusion is as low as possible, while all requests are finalized.

In another implementation of the first aspect, the controller is configured to: select from another set not associated with the determined egress pipe for the determined egress pipe requesting a read packet A block of memory for the reading of the data packet.

This ensures that each packet reaches the correct destination.

In another implementation manner of the first aspect, the controller is further configured to select a remaining available memory block for the outstanding write request based on a minimum occupancy rate or randomly.

This implementation can further improve the efficiency of memory block allocation.

In another implementation of the first aspect, the controller is further configured to associate the outlet pipe with the set of memory blocks.

Thus, the controller fully controls the memory device. The controller can also change the association of the set of the memory blocks with the outlet pipe if necessary.

A second aspect of the present invention provides a switch for packet switching. The switch includes the memory device according to the first aspect or any implementation thereof.

In one implementation of the second aspect, the switch includes a plurality of input ports and a plurality of output ports, wherein each of the inlet pipes is associated with a group of the input ports, and each of the outlets A tube is associated with the set of output ports.

A third aspect of the present invention provides a method for controlling a memory device. The memory device includes a plurality of memory blocks, inlet pipes and outlet pipes. The method comprises: selecting a memory block for the egress pipe from a set of memory blocks associated with the egress pipe requesting to read the data packet for the reading of the data packet; and/or from the exit pipe associated with the determined egress In the set of memory blocks associated with the pipe, a memory block is selected for any ingress pipe requesting to write a data packet whose destination is the determined egress pipe, so as to write the data packet.

In an implementation manner of the third aspect, the sets are disjoint sets.

In another implementation of the third aspect, each set includes the same number of memory blocks.

In another implementation of the third aspect, the method includes selecting a memory block for the egress pipe from a set associated with the egress pipe requesting to read the data packet, for the data packet read.

In another implementation of the third aspect, the method further comprises: requesting to write any inlet pipe destined for the determined outlet pipe from the set associated with the determined outlet pipe A block of memory is selected for writing the packet.

In another implementation manner of the third aspect, the method further includes: when selecting the memory block from the set associated with the determined egress pipe for writing the data packet , exclude one or more full memory blocks.

In another implementation of the third aspect, if the total number of write requests for data packets destined for the determined egress pipe is less than a write allowed in the set associated with the determined egress pipe the number of incoming memory blocks, the method comprising: selecting a memory block based on a minimum occupancy rate or randomly from the write-allowed memory blocks in the set associated with the determined egress pipe.

In another implementation of the third aspect, if the total number of write requests for data packets destined for the determined egress pipe is greater than the write allowed in the set associated with the determined egress pipe the number of incoming memory blocks, the method includes creating a list of all ingress pipes with outstanding write requests.

In another implementation of the third aspect, if the total number of write requests for data packets destined for the determined egress pipe is greater than the write allowed in the set associated with the determined egress pipe the number of incoming memory blocks, the method includes: selecting the memory block from another set not associated with the determined egress pipe to write the data packet, specifically, for Each outstanding write request allocates the remaining block of free memory.

In another implementation of the third aspect, the method includes selecting a memory for the determined egress pipe requesting a read packet from another set not associated with the determined egress pipe block for reading of the packet.

In another implementation manner of the third aspect, the method includes: selecting a remaining available memory block for the outstanding write request based on a minimum occupancy rate or randomly.

In another implementation of the third aspect, the method includes associating the outlet pipe with the set of memory blocks.

The method of the third aspect achieves all of the above advantages and effects of the memory device of the first aspect.

A fourth aspect of the present invention provides a computer program product storing program code for controlling a memory device according to the first aspect or any of its implementations and/or according to the second aspect or any of its implementations A switch of an implementation, or when implemented on a computer, for performing a method according to the third aspect or any implementation thereof.

Accordingly, with the computer program product of the fourth aspect, the advantages of the first, second and third aspects, respectively, can be achieved.

It should be noted that all the devices, elements, units and means described in this application can be implemented in software or hardware elements or any kind of combination thereof. All steps performed by the various entities described in this application and the functions described to be performed by the various entities are intended to indicate that the various entities are adapted or used to perform the respective steps and functions. Although in the following description of specific embodiments, specific functions or steps performed by an external entity are not reflected in the description of specific elements of that entity performing the specific steps or functions, it should be clear to those skilled in the art that these methods and functions may be implemented in implemented in respective hardware or software elements or any combination thereof.

Description of drawings

In conjunction with the accompanying drawings, the following description of specific embodiments will illustrate various aspects of the present invention described above and implementations thereof, wherein:

FIG. 1 shows a memory device according to an embodiment of the present invention;

FIG. 2 shows a switch according to an embodiment of the present invention;

Figure 3 shows a method according to an embodiment of the present invention;

FIG. 4 shows the simulation of uniformly distributed random traffic through a memory device according to an embodiment of the present invention;

FIG. 5 shows the simulation of uniformly distributed random traffic through a memory device according to an embodiment of the present invention;

FIG. 6 shows the simulation of uniformly distributed random burst traffic through a memory device according to an embodiment of the present invention;

Figure 7 illustrates a conventional switch shared memory architecture; and

Figure 8 shows a conventional switch shared memory architecture with multiple memory blocks and multiple egress and ingress pipes.

Detailed ways

FIG. 1 shows a memory device 100 according to an embodiment of the present invention. The memory device 100 is particularly suitable for implementation in a switch 200 (shown in FIG. 2 ). In particular, the memory device 100 may serve as a shared memory architecture of the switch 200 .

The memory device 100 includes a plurality of memory blocks 101, a plurality of inlet pipes 102 and a plurality of outlet pipes 103, wherein each memory block 101 may be a conventional memory block. Furthermore, the inlet pipe 102 and the outlet pipe 103 themselves can be implemented like conventional pipes. Each ingress pipe 102 is used to request to write data packets into the memory block 101 . For example, the data packets may be Ethernet data packets. Further, each egress pipe 103 is used for requesting to read data packets from the memory block 101 .

According to the present invention, each outlet pipe 103 and the set 104 of the memory blocks 101 (represented by the dotted line between the memory block 101 and the outlet pipe 103 , but it does not mean that the outlet pipe 103 can only read from these memory blocks 101 take) associated. The set 104 of the memory blocks 101 may be disjoint sets, ie the two sets 100 do not share any memory blocks 101 . Further, each set 104 may include the same number of memory blocks 101 . However, the two sets 104 may include different numbers of memory blocks 101 .

Since the read requests and sequences of different egress pipes 103 from the memory block 101 are certain and cannot be controlled, the memory device 100 in FIG. 1 controls to write the arriving data packets into the memory block 101, thereby significantly reducing the the probability of read collisions. Therefore, the probability of high latency and low throughput due to conflicting reads of the same memory block 101 by different outlet pipes 103 is also reduced.

An example of the memory device 100 of FIG. 1 is described below. In the memory device 100 , M memory blocks 101 are divided into P outlet pipes 103 such that each outlet pipe 103 is associated with M/P memory blocks 103 .

For example, for M=64 and P=16, each outlet pipe 103 can be associated with 4 memory blocks 101 as follows:

– outlet pipe 0: memory blocks 0-3

– Outlet Pipe 1: Memory Blocks 4-7

-…

– Outlet Pipe 16: Memory Blocks 60-63

Typically, if the destination of the data packet to be written is the egress pipe 103, the memory block 101 associated with the egress pipe 103 is selected for any one of the ingress pipes 102 for writing. It is worth noting that if these memory blocks 101 are full, they may not be selected for writing.

Since a certain outlet pipe 103 is associated with M/P memory blocks 103, and it is assumed that there is one memory block for reading, there is M/P-1 memory block 101 dedicated to this outlet pipe 101 and available for writing . It is assumed that none of the M/P-1 memory blocks 101 are full.

Considering the basic rules for selecting memory blocks 101 for writing, if each outlet pipe 103 has M/P - 1 write requests or less in the same clock cycle, the probability of collisions on reads is reduced to zero . The selection algorithm for the memory block for write requests, as described above for the conventional shared memory architecture, is modified accordingly to significantly reduce read conflicts.

Specifically, the writing process of the present invention can be divided into two steps: the first step (step 1): only from the memory blocks 101 of the associated range, that is, from M/P memory blocks 101 , is the request entry Pipes 102 allocate memory blocks 101 for writing to each outlet pipe 103 . Second step (step 2): allocate memory blocks 101 for the remaining write requests (ie, if M/P memory blocks have been allocated for egress pipe 103 for reading, or if no memory blocks are allocated for reading, The number of writes for the outlet pipe 103 is greater than M/P-1). These two steps are described in more detail below:

step 1:

1. Select a memory block 101 for each entry pipe 102 individually from the M/P memory blocks 101 for writing.

a. For example, for M=64, P=16, memory blocks 0-3 may be selected for writes to outlet pipe 0 (unless any of the memory blocks are already selected for reading).

b. If a certain outlet pipe 103 requires less than 4 writes, or if less than 3 writes are required, where the memory block 101 has been selected for reading, it can be accessed from the M/P (or M/P – 1) fewer memory blocks 101 are selected. It is worth noting that the present invention is not limited to the memory block selection process, and the process can be:

i. Select the memory block 101 with the smallest occupancy.

ii. Randomly select memory block 101

iii. etc.

2. Create a list of all ingress pipes 102 with outstanding requests.

a. This can happen if the following conditions are true.

i. have more than M/P-1 write requests for a single outlet pipe 103 for which reads have been allocated; or

ii. There are more than M/P write requests for a single outlet pipe 103 and no reads are allocated for that outlet pipe 103 .

Step 2:

1. The remaining write requests from all ingress pipes 102 are allocated to the remaining available memory blocks 101.

a. Available memory blocks 101 are memory blocks that are not allocated for reading or writing and are not full (ie, can be written).

b. The present invention is not limited to the memory block selection process, and the process can be:

i. Select the memory block 101 with the smallest occupancy.

ii. Randomly select memory block 101

iii. etc.

As defined, the memory block 101 is "soft allocated" to (associated with) the outlet pipe 103 . This means that the M/P memory block for outlet pipe 103 is the memory block that is preferentially used for writing, but if more writes are needed at the same time, the remaining writes are allocated to the remaining memory block 101, making it as A different outlet pipe 103 serves as the end point.

Figure 2 shows a switch 200 according to an embodiment of the present invention. The switch 200 is specifically used for packet switching in a network system, and can be a high-bandwidth, high-capacity switch. The switch 200 includes at least one memory device 100 according to an embodiment of the present invention, especially as shown in FIG. 1 .

As shown in FIG. 2 , the switch 200 may further include multiple input ports 201 and multiple output ports 202 . Each inlet pipe 102 of the memory device 100 is associated with the group 203 of the input ports 201 , and each outlet pipe 103 of the memory device 100 is associated with the group 204 of the output ports 202 .

Figure 3 illustrates a method 300 according to an embodiment of the present invention. The switch 300 is particularly used to control the memory device 100 according to the embodiment of the present invention, especially the memory device shown in FIG. 1 . The method 300 may be performed by the controller of the memory device 100 , or by the controller of the switch 200 (shown in FIG. 2 ), wherein the switch includes the memory device 100 .

The method includes: Step 301 : Selecting the memory block 101 of the memory device 100 for the egress pipe 103 of the memory device 100 from the set of memory blocks 101 associated with the egress pipe 103 requesting to read the data packet , to read the data packet. Additionally or alternatively, the method 300 includes: Step 302 : from the set 104 of memory blocks 101 associated with the determined exit pipe 103 for the request of the memory device 100 to write to the determined exit Any ingress pipe 102 of the data packet of the pipe 103 selects the memory block 101 of the memory device 100 to write the data packet.

The following analyzes the performance improvement of the memory device 100, the switch 200, and the method 300 according to the embodiments of the present invention.

As an example, a memory device 100 containing P=16 outlet pipes 103 and M=32-256 memory blocks 101 is simulated for two memory block allocation schemes:

1. Randomly allocate memory block 101 for write requests (conventional).

2. According to the solution of the present invention, the memory block 101 is softly allocated for the write request (exit pipe 103).

Figure 4 shows a first test simulating a uniformly distributed random flow. A worst-case traffic pattern (small packets) from all input ports was applied, where a uniformly distributed random destination was chosen for each packet.

Figure 5 shows a second test simulating uniformly distributed random traffic. A worst-case traffic pattern (small packets) from all input ports is applied, where a uniformly distributed random destination is chosen for each packet in 9 clock cycles, and in the 10th clock cycle, all arriving The destination of the packet is a randomly chosen uniformly distributed single destination.

Figure 6 shows a third test simulating a uniformly distributed random burst of traffic. A worst-case traffic pattern (small packets) from all input ports is applied, where a uniformly distributed random destination is chosen for all arriving packets at each clock cycle. The destination of all arriving packets is a single, uniformly-distributed destination chosen at random.

In the summaries of Figures 4, 5, and 6, all simulation results show that when using the soft allocation scheme of the present invention (compared to traditional random memory block selection), a lower number of memory blocks 101 has a higher transmission bandwidth. Only when the number of memory blocks 101 is very high, the performance of the two schemes is the same.

Notably, the large number of memory blocks 101 increases the overall silicon area and power consumption. Another advantage of the allocation scheme of the present invention is that delays are reduced. Since the overall shared memory structure of the memory device 100 provides more bandwidth, the latency is reduced. Latency is the time a packet stays in the memory device 100 or switch 200 before being transmitted. The time is counted from the arrival of the first byte of the packet to the departure of the first byte of the packet.

The present invention has been described in connection with various embodiments and embodiments by way of example. However, those skilled in the art can understand and obtain other variations by practicing the claimed invention, studying the drawings, the present disclosure and the independent claims. In the claims and descriptions, the term "comprising" does not exclude other elements or steps, and "a" does not exclude a plural possibility. A single element or other unit may fulfill the functions of several entities or items recited in the claims. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage.

Claims (16)

1. A memory device (100) for a switch (200), wherein the memory device (100) comprises: multiple memory blocks(101); a plurality of ingress pipes (102), wherein each ingress pipe (102) is used to request data packets to be written to the memory block (101); and a plurality of exit pipes (103), wherein each exit pipe (103) is used for requesting to read data packets from the memory block (101), Therein, each outlet pipe (103) is associated with a set (104) of said memory blocks (101). 2. The memory device (100) according to claim 1, characterized in that, The sets (104) are disjoint sets. 3. The memory device (100) according to claim 1 or 2, characterized in that, Each set (104) includes the same number of memory blocks (101). 4. The memory device (100) according to any one of claims 1 to 3, characterized in that, comprising: a controller for selecting a memory block (101) for the egress pipe (103) from the set (104) associated with the egress pipe (103) requesting to read the data packet, for the reading of the data packet Pick. 5. The memory device (100) according to claim 4, characterized in that, The controller is further configured to request to write any ingress pipe ( 102) Select a memory block (101) for writing the data packet. 6. The memory device (100) according to claim 5, characterized in that, The controller is further configured to exclude, when selecting the memory block (101) from the set (104) associated with the determined egress pipe (103) for writing of the data packet One or more full memory blocks (101). 7. The memory device (100) according to claim 5 or 6, characterized in that, if the total number of requests to write packets destined for the determined egress pipe (103) is less than the allowable writes in the set (104) associated with the determined egress pipe (103) the number of memory blocks (101), the controller is also used to: A memory block (101) is selected from the write-enabled memory blocks (101) in the set (104) associated with the determined outlet pipe (103) based on minimum occupancy or randomly. 8. The memory device (100) according to any one of claims 5 to 7, characterized in that, if the total number of requests to write packets destined for the determined egress pipe (103) is greater than the allowable writes in the set (104) associated with the determined egress pipe (103) the number of memory blocks (101), the controller is also used to: A list of all ingress pipes (102) with outstanding write requests is created. 9. The memory device (100) according to any one of claims 5 to 8, characterized in that, if the total number of requests to write packets destined for the determined egress pipe (103) is greater than the allowable writes in the set (104) associated with the determined egress pipe (103) the number of memory blocks (101), the controller is also used to: Said memory block (101) is selected from another set (104) not associated with said determined egress pipe (103) for writing of said data packet, in particular, for each unrelated set (104) A completed write request allocates the remaining available memory blocks (101). 10. The memory device (100) according to claim 9, characterized in that, said controller for selecting a memory block (101) for said determined egress pipe (103) from another set (104) not associated with said determined egress pipe (103) requesting a read packet, for the reading of the data packet. 11. The memory device (100) according to claim 9, characterized in that, The controller is further configured to select remaining available memory blocks for the outstanding write requests based on minimum occupancy or randomly (101). 12. The memory device (100) according to any one of claims 4 to 11, characterized in that, The controller is also configured to associate the outlet pipe (103) with the set (104) of the memory blocks (101). 13. A switch (200) for packet switching, characterized in that the switch (200) comprises: The memory device (100) according to any of claims 1 to 12. 14. The switch (200) of claim 13, comprising: multiple input ports (201) and multiple output ports (202), Therein, each inlet pipe (102) is associated with the group (203) of said input ports (201) and each outlet pipe (103) is associated with the group (204) of said output ports (202). 15. A method (300) for controlling a memory device (100), wherein the memory device (100) comprises a plurality of memory blocks (101), an inlet pipe (102) and an outlet pipe (103), The method includes: (301): Select a memory block (101) for the egress pipe (103) from the set of memory blocks (101) associated with the egress pipe (103) requesting to read the data packet, for the data packet read; and/or (302): From the set (104) of memory blocks (101) associated with the determined egress pipe (103), request to write any ingress pipe of a packet destined for the determined egress pipe (103) (102) Select a memory block (101) for writing the data packet. 16. A computer program product, characterized in that a program code is stored, wherein the program code is used to control a memory device (100) according to any one of claims 1 to 12 and/or according to claim 1 The switch of 13 or 14, or when implemented on a computer, for performing the method (300) of claim 15.

Images