Systems and methods for providing replicated data from memories to processing clients

Systems and methods are provided for a network device. A device includes a plurality of packet processing clients. The device further includes a plurality of memories, where a quantity of the memories is greater than a quantity of the packet processing clients, each of the memories storing a replica of data, the packet processing clients being configured to selectively read the control data from any of the memories. An arbiter is configured to select in a first clock cycle for the plurality of packet processing clients a first subset of memories from among the plurality of memories from which to read the control data, and in a second clock cycle, subsequent to the first clock cycle, to select for the plurality of packet processing clients a second subset of memories from among the plurality of memories from which to read the control data.

FIELD

The technology described herein relates generally to multi-device access to a shared resource and more particularly to multi-device memory access M a network communication system.

BACKGROUND

Multi-device access to a shared resource often results in access bandwidth complications that in certain configurations slow an entire system. This is especially the case in high speed communication systems, such as a network switch, where multiple packet processing clients seek to access control data stored in a memory.

SUMMARY

Examples of systems and methods are provided for a network device that receives packet data from a network. A device includes a plurality of packet processing clients for processing packet data received from a network. The device further includes a plurality of memories, where a quantity of the memories is greater than a quantity of the packet processing clients, each of the memories storing a replica of control data to be used by the packet processing clients, and the packet processing clients being configured to selectively read the control data from any of the memories. An arbiter is coupled to the packet processing clients and to the memories, the arbiter being configured to select in a first clock cycle for the plurality of packet processing clients a first subset of memories from among the plurality of memories from which to read the control data, and in a second clock cycle, subsequent to the first clock cycle, to select for the plurality of packet processing clients a second subset of memories from among the plurality of memories from which to read the control data, the second subset of memories including at least some memories that are not included in the first subset of memories.

As another example, a method of providing control data to a plurality of packet processing clients configured to process packet data received by a network includes updating a plurality of M memories with replicated control data to be used by a plurality of N packet processing clients, where M is greater than N. One of the memories from among the M memories is assigned to each of the packet processing clients for accessing the control data during a first clock cycle, each packet processing client being assigned a different one of the memories from among the M memories, and where at least one of the memories among the M memories is a first unassigned memory that is not assigned to a packet processing client during the first clock cycle. A different memory from among the M memories is assigning to each of the processing clients for accessing the control data during a second clock cycle, where at least one of the memories among the M memories is a second unassigned memory that is not assigned to a packet processing client during the second clock cycle, the second unassigned memory being different from the first unassigned memory.

DETAILED DESCRIPTION

FIG. 1is a block diagram depicting a network device that receives packet data from a network. The network device includes a plurality of N packet processing clients102for processing packet data received from a network. The device also includes a plurality of M memories104. The quantity of memories (M)104is greater than a quantity of packet processing clients (N)102. For example, in one embodiment of the disclosure, M=5 memories provide data to N=3 processing clients. Each of the memories104stores a replica of control data to be used by the packet processing clients102. The packet processing clients102are configured to read the control data from any of the memories104. The device further includes an arbiter106that is coupled to the packet processing clients102and to the memories104. In an embodiment, the arbiter106is configured to select in a first clock cycle for the plurality of packet processing clients102a first subset of memories, subset A for example, from among the plurality of memories104from which to read the control data. The arbiter106is further configured to select, in a second clock cycle, for the plurality of packet processing clients102a second subset of memories, subset B for example, from among the plurality of memories104from which to read the control data. The second subset of memories includes at least some of the memories that are not included in the first subset of memories. Further, the arbiter106is configured to select the subsets of memories such that the second subset of memories does not include at least one memory that is in the first subset of memories. It is noted that in actual devices, there may be a greater or lesser number of processing clients102as well as a greater or lesser number of memories106. Moreover, as will be described in greater detail below, in actual devices there may be a different variance among selected subsets between respective cycles than seen inFIG. 1.

In one embodiment of the disclosure, the arbiter106is configured to assign memories104to packet processing clients102in a pseudo random fashion as a mechanism for load balancing and ensuring fairness in access to the memories104, for example. Because, in some embodiments, a packet processing client takes more than one clock cycle to perform a read operation on a particular memory, such as accessing a lookup data table stored on the particular memory, or because the particular memory is unable to perform certain types of accesses in a back-to-pack fashion (e.g., certain DDR3 protocols do not support reading data from the same page on consecutive cycles), a packet processing client that is assigned the particular memory in the next clock cycle is not able to perform its read operation due to that particular memory being busy or unable to perform. A particular packet processing client that is always assigned a memory immediately after that memory has been assigned to another busy packet processing client would regularly be blocked from performing read operations, slowing total processing of the particular packet processing client. In contrast, a particular packet processing clients that is assigned a memory after that memory was unassigned for a previous clock cycle is much more likely to be able to perform its desired read operations because that previously unassigned memory has had more than one clock cycle to complete any previous requests in its job queue that were not yet completed. For example, in one embodiment of the disclosure where a network device operates in a system that is oversubscribed, the bandwidth of the M memories is not sufficient to serve all client requests. In such an embodiment, a network device attempts to provide each processing client the same portion of memory accesses, such as using certain algorithms described herein.

To combat such unfairness, in one embodiment, a network device performs operations to assign memories to packet processing clients in a pseudo random fashion that ensures that because certain memories are not assigned to a packet processing client during each clock cycle, during a set of processing cycles, each of the packet processing clients is assigned a memory that was not assigned to another packet processing client during a previous clock cycle at least once. Having more copies of control data than processors, and rotating access to the memories containing those control data copies, a network device, in one embodiment, supports increased bandwidth by reducing blockage resulting from reading data at a given memory on two consecutive cycles.

FIG. 1discloses additional network device elements that, in one embodiment of the disclosure, are used to facilitate this pseudo random memory assignment in accordance with an embodiment. InFIG. 1, the arbiter106includes shift logic108in the form of one or both of a first shift register110that operates as a processing client shift register and a second shift register112that operates as a memory shift register112. These shift registers include an array of entries that are shifted X positions (e.g., one or more positions) left or right each clock period in a wrap around fashion. Example functionality of the processing client shift register110is described in further detail with respect toFIG. 2, and example functionality of the memory shift register112is described with respect toFIG. 4. The arbiter106further includes assignment logic114that matches packet processing clients with memories.

FIG. 2depicts an example assignment mechanism for assigning memories to processing clients for access to data that is replicated at each of the memories. The example ofFIG. 2includes N=3 processing clients and M=5 memories. Thus, in each clock cycle, two memories will not be assigned to a processing client, while three of the memories will be assigned to a processing client. A processing client shift register is depicted at202. The client shift register202includes an entry for each of the processing clients, which are numbered sequentially 0, 1, 2. The client shift register202identifies an order in which the packet processing clients are assigned memories for a particular clock cycle. In the example ofFIG. 2, for cycle0, the processing clients are assigned memories such that Processing Client0is assigned a memory first, Processing Client1is assigned a memory second, and Processing Client2is assigned a memory third. For cycle1, the client shift register is shifted one position left, as indicated at204, such that Processing Client1is assigned a memory first, Processing Client2is assigned a memory second, and Processing Client0is assigned a memory third. For cycle2, the client shift register is shifted another position left, as indicated at206, such that Processing Client2is assigned a memory first, Processing Client0is assigned a memory second, and Processing Client1is assigned a memory third. Such memory to processing client assignments are performed sufficiently quickly, in an embodiment, such that each of the processing clients are able to perform read operations in each cycle, barring an assigned memory being busy or otherwise unable to perform.

In addition to varying the order in which the processing clients are assigned memories, memories are assigned in a numeric order where the memory assignment starting point is also varied based on assignment logic. This assignment logic for each of cycles0,1, and2is indicated inFIG. 2at207,209,211, respectively. In the example ofFIG. 2, the first memory to be assigned to a processing client is determined according to the formula:
Starting Memory=(cycle*N)%M,(eq. 1)
where cycle is a clock cycle number, N is the number of packet processing clients, % represents a modulo operation, and M is the number of memories. Thus, for clock cycle0, Memory0is the first memory to be assigned (i.e., Starting Memory=(0*3)% 5=0). Memory0is assigned to the first processing client according to the order shown in the client shift register at202, Processing Client0, as depicted at208. Memory1is the next memory to be assigned and is assigned to the second memory in the client shift register202order, Processing Client1. Further, Memory2is the third memory to be assigned, and Memory2is assigned to the third memory in the client shift register202order, Processing Client2. As indicated at208, Memory3and Memory4are not assigned a processing client for clock cycle0because each of Processing Clients0,1,2have already been assigned memories.

For clock cycle1, the client shift register is shifted one position to the left, as indicated at204, and the assignment logic determines that Memory3is the first memory to be assigned to a processing client Starting Memory=(1*3)% 5=3). Thus, for clock cycle1, Memory3is assigned to the first processing client according to the order shown in the client shift register at204, Processing Client1, as depicted at210. Memory4is the next memory to be assigned and is assigned to the second memory in the client shift register204order, Processing Client2. Memories are assigned in a wraparound fashion. Thus, Memory0is the third memory to be assigned, and Memory0is assigned to the third memory in the client shift register204order, Processing Client0. As indicated at210, Memory1and Memory2are not assigned a processing client for clock cycle1.

For clock cycle2, the client shift register is shifted one position to the left, as indicated at206, and the lent determines that Memory1is the first memory to be assigned to a processing client (i.e., Starting Memory=(2*3)% 5=1). Thus, for clock cycle2, Memory1is assigned to the first processing client according to the order shown in the client shift register at206, Processing Client2, as depicted at212. Because, in one embodiment of the disclosure, memories are assigned in a sequential order, Memory2is the next memory to be assigned and is assigned to the second memory in the client shift register206order, Processing Client0. Further, Memory3is the third memory to be assigned, and Memory3is assigned to the third memory in the client shift register206order, Processing Client1. As indicated at212, Memory0and Memory4are not assigned a processing client for clock cycle2.

FIG. 3is a mapping of the memory-processing client assignments for clock cycles0-2as well as clock cycles3-5, in accordance with an embodiment. Clock cycle0-2assignments were determined using the process depicted inFIG. 2, while cycle3-5assignments were determined via continued iterations of that same algorithm. As described above, a processing client is more likely to be able to perform a desired read operation when the memory assigned to that processing unit was free in one or more immediately preceding clock cycles. Over the six cycles depicted, each of Processing Clients0,1,2is assigned a memory that was free in an immediately preceding clock cycle at least three times. Thus, in one embodiment of the disclosure, a network device attempts to serve high quality memory allocation slots evenly across the set of processing clients over time.

FIG. 4depicts another example algorithm for assignment of memories to processing clients for access to data that is replicated at each of the memories, in accordance with an alternative embodiment of the disclosure. The algorithm ofFIG. 4produces an identical assignment result as the algorithm ofFIG. 2while using a memory shift register in place of a client shift register and a variant of the assignment logic used inFIG. 2. The algorithm ofFIG. 2identifies which processing clients are served (or free) by each of the memories during each clock cycle. Such a mapping is useful for connecting memories to the correct processing clients when returning results via the arbiter. The algorithm ofFIG. 4identifies which memory is serving each of the processing clients. Such a mapping is useful for sending processing client requests to the proper memories via the arbiter. Thus, in embodiments of the disclosure, an arbiter performs one or both of the algorithms inFIG. 2andFIG. 4to aid in transmitting read requests and returning read request results. In other embodiments, an arbiter performs one of theFIG. 2andFIG. 4algorithms and translates to the other assignment representation, as described in further detail with reference toFIG. 5.

In the embodiment ofFIG. 4a memory shift register402includes an entry for each of the memories, which are numbered sequentially 0, 1, 2, 3, 4. The memory register402identifies an order in which the memories are assigned to processing clients for a particular clock cycle. In the example ofFIG. 4, during cycle0, the processing clients are assigned memories such that Memory0is assigned to a processing client first, Memory1is assigned to a processing client second, Memory2is assigned to a processing client third, Memory3is assigned to a processing client fourth, and Memory4is assigned to a processing client fifth, as depicted at402. At404, for cycle1, the memory shift register is shifted one position left such that Memory1is assigned to a processing client first, Memory2is assigned to a processing client second, Memory3is assigned to a processing client third, Memory4is assigned to a processing client fourth, and Memory0is assigned to a processing client fifth. At406, for cycle2, the memory shift register is shifted one position left such that Memory2is assigned to a processing client first, Memory3is assigned to a processing client second, Memory4is assigned to a processing client third, Memory0is assigned to a processing client fourth, and Memory1is assigned to a processing client fifth.

Because there are fewer processing clients than memories, in each cycle, the assignment logic determines which of the memories will not be assigned to a processing client. In each cycle, M-N memories are cut from the subset of memories that are selected for assignment, leaving N memories in the subset of memories for assignment to N processing clients. In the example ofFIG. 4, two memories are cut, because M=5 and N=3. The assignment logic begins cutting memories from the subset of memories to be assigned at the memory identified by the formula:
Starting Memory=(cycle*(N−1))%M−(cycle*(N−1)+N)%M,(eq. 2)
where cycle is a clock cycle number, N is the number of packet processing clients, % represents a modulo operation, and M is the number of memories. Thus for cycle0, memories are cut starting at position3of the memory shift register, resulting in Memory3and Memory4being cut, leaving Memory0, Memory1, and Memory2for assignment, as indicated at408(i.e., Starting Memory=(0*(3−1))% 5−(0*(3−1)+3)% 5=3). For cycle1, memories are cut starting at position0of the memory shift register, resulting in Memory1and Memory2being cut, leaving Memory3, Memory4, and Memory0for assignment, as indicated at410. For cycle2, memories are cut starting at position3of the memory shift register, resulting in Memory4and Memory0being cut, leaving Memory1, Memory2, and Memory3for assignment, as indicated at412.

In an embodiment, the remaining memories (e.g., the memories at408) are then assigned to processing clients starting at the processing client identified by:
Starting Client=cycle %N,(eq. 3)
where cycle is a clock cycle number, % represents a modulo operation, and N is the number of packet processing clients. Thus, for cycle0, Processor Client0is assigned the first memory remaining at408, Memory0; Client1is assigned the second memory at408, Memory1; and Client2is assigned the third memory at408, Memory2, as depicted at414. For cycle1, Processor Client1is assigned the first memory remaining at408, Memory3; Client2is assigned the second memory at408, Memory4; and Client0is assigned the third memory at408, Memory0, as depicted at416. For cycle2, Processor Client2is assigned the first memory remaining at408, Memory1; Client0is assigned the second memory at408, Memory2; and Client1is assigned the third memory at408, Memory3, as depicted at418.

FIG. 5is a chart depicting the memory-processing client assignments for clock cycles0-2as well as clock cycles3-5using the algorithms described with respect toFIGS. 2 and 4, in an embodiment. At502,FIG. 5depicts a client napping per memory, illustrating the memory assignments according to the algorithm ofFIG. 2, while at504,FIG. 5depicts a memory mapping per client, illustrating the memory assignments according to the algorithm ofFIG. 4, in an embodiment. These mappings are analogous. For example, for cycle2, Memory1is mapped to Processing Client2, Memory2is mapped to Processing Client0, and Memory3is mapped to Processing Client1for both of theFIG. 2andFIG. 4algorithm determined mappings. Thus, in different embodiments of the disclosure, different algorithms are utilized, and variations of algorithms are used toward a common result of implementing a pseudo random assignment of memories to processing clients that results in fair load balancing among the memories.

Additionally, results produced using one of theFIG. 2,FIG. 4algorithms can be translated to the other. For example, where for clock cycle1using theFIG. 2algorithm, Memory0is assigned to Processing Unit0, Memory3is assigned to Processing Unit1, and Memory4is assigned to Processing Unit2, as indicated at506, the memory mapping per client equivalent, which can be determined using theFIG. 4algorithm, can also be determined by identifying which memory is assigned to Processing Client0(Memory0), which memory is assigned to Processing Client1(Memory3), and which memory is assigned to Processing Client2(Memory4), as indicated at508. Additionally, to translate from theFIG. 4memory mapping client of theFIG. 4algorithm at508to theFIG. 4representation, an arbiter iterates through each of the Memories0-5, identifying which have been assigned to which processing client, where some memories are not assigned and are thus marked free in the representation at506.

The pseudo random nature of the arbiter assignment enables predictability that is important in some embodiments of the disclosure. For example, in certain embodiments where memory response time varies significantly across the population of memories, it is important that a processing client possess data identifying from which memory to expect data for a particular clock cycle. When memories take more than one clock cycle to provide control data results, and a processing client makes memory requests over consecutive clock cycles, the processing client needs to possess data identifying from Which Memory to expect data for given clock cycle's request, enabling the processing client to match returned data with the proper read request. By implementing the arbiter algorithm at the processing client, alone or in parallel with an arbiter, the processing clients still function reliably, even with significant variances in memory response times. For example, in an embodiment where Processing Client1requests data from a first position in the replicated lookup table in Memory1at clock cycle1and further requests data from a second position in the replicated lookup table in Memory2at clock cycle2, when Memory2returns its data before Memory1, Processing Client utilizes its per-clock cycle memory assignment data to match the data from Memory1with the first request and the data from Memory2with the second request, despite receiving those responses out of order.

FIG. 6is a block diagram depicting a network device. The network device600includes a first electrical substrate602and a plurality of packet processing clients604for processing packet data606received from a network disposed on the first electrical substrate602. The network device600further includes a plurality of memories608that are external to the electrical circuit substrate602, for example external memories implemented using double data rate 3 (DDR3) technologies. In other embodiments of the disclosure, greater or lesser number of memories are implemented, and in still other embodiments of the disclosure, the memories are implemented in SRAM or on the electrical circuit substrate602itself. The quantity of the memories608is greater than the quantity of the packet processing clients604in an embodiment. Each of the memories608stores a replica of control data to be used by the packet processing clients604. The packet processing clients604are configured to read the control data from any of the memories608. The network device600further includes an arbiter610disposed on the first electrical substrate602that is coupled to the packet processing clients604and to the memories608. The arbiter610is configured to select in a first clock cycle for the plurality of packet processing clients604a first subset of memories, subset A for example, from among the plurality of memories608front which to read the control data, and in a second clock cycle to select for the plurality of packet processing clients604a second subset, subset B for example, of memories from among the plurality of memories608from which to read the control data, where the second subset of memories includes at least some memories that are not included in the first subset of memories.

In one embodiment of the disclosure, each of the memories includes a replica of control data that is used to process packets in a network device. This replicated data is used by the respective packet processing clients. For example, in one embodiment where the packet processing clients are components of a LAN switch, the replicated data includes a switch lookup table. Upon receiving a packet, a processing client reads the MAC address that is in the frame header of a received packet. The processing client accesses one of the replicated switch lookup tables on one of the memories to determine an appropriate output port for the received packet. Upon accessing the port data for the received packet, the processing client forwards the received packet on the appropriate output port.

FIG. 7is a flow diagram depicting a method of providing control data to a plurality of packet processing clients configured to process packet data received by a network. At702, a plurality of M memories are updated with replicated control data to be used by a plurality of N packet processing clients, where M is greater than N. At704, one of the memories from among the M memories are assigned to each of the packet processing clients for accessing the control data during a first clock cycle, each packet processing client being assigned a different one of the memories from among the M memories, wherein at least one of the memories among the M memories is a first unassigned memory that is not assigned to a packet processing client during the first clock cycle. At706, a different memory from among the M memories is assigned to each of the processing clients for accessing the control data during a second clock cycle, wherein at least one of the memories among the M memories is a second unassigned memory that is not assigned to a packet processing client during the second clock cycle, the second unassigned memory being different from the first unassigned memory.

This application uses examples to illustrate the invention. The patentable scope of the invention includes other examples. For example, in embodiments of the disclosure, the processing clients ofFIG. 1are components of a network switch, a router, or other network device.