Packet cache system and method

Patent metadata

Field	Value
Publication number	US-12216587-B2
Application number	US-202418583341-A
Country	US
Kind code	B2
Filing date	Feb 21, 2024
Priority date	Jun 7, 2022
Publication date	Feb 4, 2025
Grant date	Feb 4, 2025

Abstract

A packet cache system includes a cache memory allocator for receiving a memory address corresponding to a non-cache memory and allocated to a packet, and associating the memory address with a cache memory address; a hash table for storing the memory address and the cache memory address, with the memory address as a key and the cache memory address as a value; a cache memory for storing the packet at a location indicated by the cache memory address; and an eviction engine for determining one or more cached packets to remove from the cache memory and place in the non-cache memory when occupancy of the cache memory is high.

First claim

The invention claimed is:

1. A packet cache system comprising:
a cache memory allocator for receiving a memory address corresponding to a non-cache memory and allocated to a packet, and associating the memory address with a cache memory address;
a hash table for storing the memory address and the cache memory address, with the memory address as a key and the cache memory address as a value;
a cache memory for storing the packet at a location indicated by the cache memory address;
an eviction engine for determining one or more cached packets to remove from the cache memory and place in the non-cache memory when occupancy of the cache memory is high; and
a reorder engine for receiving a read request comprising a read address corresponding to the non-cache memory and allocated to a desired packet to be read from either the cache memory or the non-cache memory, and for storing the desired packet, upon reading from either the cache memory or the non-cache memory, into a reorder buffer such that the desired packet is supplied in response to the read request at a timing proper relative to a timing of other read requests.

2. The system according to claim 1 , wherein the reorder engine is operable, upon receiving the read request, to assign a continuous space in the reorder buffer for accommodating the desired packet.

3. The system according to claim 1 , further comprising a memory allocator for assigning the memory address to the packet.

4. The system according to claim 3 , wherein the memory allocator is operable to form the packet into one or more cells, the one or more cells comprising a control cell when the packet is formed into one cell, and comprising a control cell and one or more data cells when the packet is formed into more than one cell, wherein the memory allocator assigns the memory address to the control cell, and respectively assigns one or more additional memory addresses to the one or more data cells.

5. The system according to claim 4 , wherein when the packet is formed as more than one cell the control cell comprises one or more pointers to respective ones of the additional memory addresses.

6. The system according to claim 4 , wherein when the packet is formed as more than one cell the cache memory allocator is operable to receive the one or more additional memory addresses and associate the one or more additional memory addresses with respective one or more additional cache memory addresses.

7. The system according to claim 6 , wherein the hash table is operable to store the additional memory addresses and the additional cache memory addresses, with the additional memory addresses as keys and the additional cache memory addresses as respective values.

8. The system according to claim 6 , wherein the cache memory is operable to store a portion of the packet at the location indicated by the cache memory address, and to store respective other portions of the packet at respective locations indicated by the additional cache memory addresses.

9. The system according to claim 1 , wherein the eviction engine comprises a memory for storing a priority for each packet stored in the cache memory.

10. The system according to claim 1 , wherein the system is an integral part of an integrated circuit.

11. The system according to claim 10 , wherein the integrated circuit is an application-specific integrated circuit (ASIC).

12. The system according to claim 10 , wherein the cache memory is an integral part of the integrated circuit, and the non-cache memory is external to the integrated circuit.

13. The system according to claim 12 , wherein the cache memory is a static random-access memory (SRAM), and the non-cache memory is a dynamic random-access memory (DRAM).

14. A method for storing packets in memory and reading the packets from memory, comprising:
allocating a memory address, corresponding to a non-cache memory, to a packet;
associating the memory address with a cache memory address;
storing the memory address and the cache memory address in a hash table, with the memory address as a key and the cache memory address as a value;
storing the packet in cache memory at a location indicated by the cache memory address;
when occupancy of the cache memory is high, determining one or more cached packets to remove from the cache memory and place in the non-cache memory;
receiving a read request comprising a read address corresponding to the non-cache memory and allocated to a desired packet to be read from either the cache memory or the non-cache memory; and
storing the desired packet, upon reading from either the cache memory or the non-cache memory, into a reorder buffer such that the desired packet is supplied in response to the read request at a timing proper relative to a timing of other read requests.

15. The method according to claim 14 , further comprising, upon receiving the read request, assigning a continuous space in the reorder buffer for accommodating the desired packet.

16. The method according to claim 14 , wherein the step of allocating the memory address comprises:
forming the packet into one or more cells, the one or more cells comprising a control cell when the packet is formed into one cell, and comprising a control cell and one or more data cells when the packet is formed into more than one cell; and
allocating the memory address to the control cell, and respectively allocating one or more additional memory addresses to the one or more data cells.

17. The method according to claim 16 wherein when the packet is formed as more than one cell the control cell comprises one or more pointers to respective ones of the additional memory addresses.

18. The method according to claim 16 , wherein when the packet is formed as more than one cell the method further comprises associating the one or more additional memory addresses with respective one or more additional cache memory addresses.

19. The method according to claim 18 , wherein the step of storing the memory address and the cache memory address in the hash table further comprises storing the additional memory addresses and the additional cache memory addresses in the hash table, with the additional memory addresses as keys and the additional cache memory addresses as respective values.

20. The method according to claim 19 , wherein the step of storing the packet in cache memory at a location comprises storing a portion of the packet at the location indicated by the cache memory address, and storing respective other portions of the packet at respective locations indicated by the additional cache memory addresses.

Assignees

• Google Llc

Inventors

• Zheng Jiazhen
• Vaduvatha Srinivas
• Walsh Hugh Mcevoy
• Chandra Prashant R
• Agarwal Abhishek
• Wang Weihuang
• Jiang Weiwei

Classifications

• G06F12/121

  using replacement algorithms · CPC title

• G06F12/0864 Primary

  using pseudo-associative means, e.g. set-associative or hashing · CPC title

• G06F12/123

  with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list · CPC title

• G06F2212/154

  Networked environment · CPC title

• G06F2212/1016

  Performance improvement · CPC title