Method and apparatus for overflowing data packets to a software-controlled memory when they do not fit into a hardware-controlled memory

• US 7,155,516 B2
• Filed: 09/25/2001
• Issued: 12/26/2006
• Est. Priority Date: 02/08/2000
• Status: Expired due to Term

• Current Assignee: ARM Finance Overseas Limited (SoftBank Group Corp.)
• Original Assignee: MIPS Technologies Incorporated (Wave Computing, Inc.)
• Inventors: Musoll, Enrique, Melvin, Stephen, Nemirovsky, Mario
• Primary Examiner(s): Wiley, David
• Assistant Examiner(s): SHIN, KYUNG H
• Application Number:
  US09/964,827
• Publication Number:
  US 20060036705A1
• Time in Patent Office: 1,918 Days
• Field of Search: 709/226, 709/210, 370/392, 707/205
• US Class Current: 709/226
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9047 including multiple buffers, e.g. buffer pools
• CPC Class Codes: H04L 49/9073 Early interruption upon arrival of a fraction of a packet
• CPC Class Codes: H04L 49/9078 using an external memory or storage device
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A system for managing packets incoming to a data router has a local packet memory (LPM) mapped into pre-configured memory units, to store packets for processing, an external packet memory (EPM), a first storage system to store packets in the LPM, and a second storage system to store packets in the EPM. The system is characterized in that the first storage system attempts to store all incoming packets in the LPM, and for those packets that are not compatible with the LPM, relinquishes control to the second system, which stores the LPM-incompatible packets in the EPM.

Claims

1. A system for managing packets incoming to a data router comprising:

a local packet memory (LPM) mapped into pre-configured memory units, to store packets for processing;

an external packet memory (EPM) for storing overflow data which is not storable by said LPM;

a first storage system coupled to said LPM, to determine a size of said packets to be stored in said LPM, and for determining whether said packets can be stored in said LPM, wherein in determining whether said packets can be stored in said LPM, the first storage system is configured to consider unallocated portions of the local packet memory in increments of one or more fixed sizes; and

a second storage system coupled to said first storage system, for receiving an indication from said first storage system when it cannot store said packets in said LPM, and for storing said packets in said LPM;

wherein said first storage system attempts to store all said packets in said LPM, and for those packets that are not storable within said LPM, relinquishes control to said second system, which stores said packets in said LPM; and

wherein said system is configured to adjust said one or more fixed sizes to include more or fewer fixed size increments which may be considered by the first storage system when the first storage system considers whether said packets can be stored in the LPM.

2. The system of claim 1 wherein said first storage system is hardware controlled and said second storage system is software-controlled.

3. The system of claim 1 wherein the data router is connected to and operates on the Internet network.

4. The system of claim 1 wherein the data router is connected to and operates on a corporate wide-area-network (WAN).

5. The system of claim 2 wherein the first storage system is implemented as an integrated circuit (IC) or IC chip set.

6. The system of claim 1 wherein said first storage system provides a memory address to said second storage system if said packets cannot be stored in said EPM.

16. The system of claim 1, wherein said system is configured to adjust said one or more fixed sizes based at least in part on a size of said packets.

17. The system as recited in claim 1, wherein the first storage system is configured to consider unallocated portions of the local packet memory in increments of two or more fixed sizes in parallel.

7. A data packet router comprising:

external ports to receive and send data packets from and to neighboring connected routers; and

a system coupled to said external ports, for managing said packets incoming to a data router, the system comprising;

a local packet memory (LPM) mapped into pre-configured memory units, to store packets for processing, each of said pre-configured memory units being resizable by said system;

an external packet memory (EPM) for storing overflow data which is not storable by said LPM;

a first storage system coupled to said LPM, to determine the size of said packets to be stored in said LPM, for determining whether said packets can be stored in said LPM, and to store packets in said LPM, wherein in determining whether said packets can be stored in said LPM, the first storage system is configured to consider unallocated portions of the local packet memory in increments of one or more fixed sizes; and

a second storage system coupled to said first storage system, for receiving an indication from said first storage system when it cannot store said packets in said LPM and for storing said packets in said LPM;

wherein said first storage system attempts to store all said packets in said LPM, and for those packets that are not storable within said LPM, relinquishes control to said second system, which stores said packets in said LPM; and

wherein said router is configured to adjust said one or more fixed sizes to include more or fewer fixed size increments which may be considered by the first storage system when the first storage system considers whether said packets can be stored in the LPM.

8. The router of claim 7 wherein said first storage system is hardware-controlled and said second storage system is software-controlled.

9. The router of claim 7 wherein the data router is connected to and operates on the Internet network.

10. The router of claim 7 wherein the data router operates on a corporate wide-area-network.

18. The router of claim 7, wherein said router is configured to adjust said one or more fixed sizes based at least in part on a size of said packets.

19. The router as recited in claim 7, wherein said router is configured to consider unallocated portions of the local packet memory in increments of two or more fixed sizes in parallel.

11. A method for managing packets incoming to a data router, comprising the steps of:

storing incoming packets, by a first storage system, into a local packet memory (LPM) that is mapped into preconfigured but resizable memory units;

determining whether incoming packets are storable within the LPM, wherein said determining comprises considering unallocated portions of the local packet memory in increments of one or more fixed sizes;

relinquishing packets not storable within the LPM to a second storage system;

storing the packets not storable within the LPM in an external packet memory by a second storage system, and

adjusting said one or more fixed sizes to include more or fewer fixed size increments which may be considered by the first storage system when the first storage system considers whether said packets can be stored in the LPM.

12. The method of claim 11 wherein the first storage system is hardware controlled and the second storage system is software controlled.

13. The method of claim 11 wherein in the data router is connected to and operates on a corporate wide-area-network (WAN).

14. The method of claim 11 wherein the first and second storage systems are implemented as an integrated circuit (IC) or IC chip set.

15. The method of claim 14 wherein in step (c) the second storage system is software-controlled.

20. The method of claim 11, wherein adjusting said one or more fixed sizes is based at least in part on a size of said packets.

21. The method of claim 11, further comprising considering unallocated portions of the local packet memory in increments of two or more fixed sizes in parallel.