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

• US 7,877,481 B2
• Filed: 10/25/2006
• Issued: 01/25/2011
• Est. Priority Date: 02/08/2000
• Status: Expired due to Fees

• 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): SHIN, KYUNG H
• Application Number:
  US11/552,764
• Publication Number:
  US 20070110090A1
• Time in Patent Office: 1,553 Days
• Field of Search: 709/226, 370/392, 370/386, 370/429
• 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) configured 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 the LPM and to a second storage system;

wherein the first storage system is configured to;

determine whether said packets can be stored in the LPM;

if a given packet is determined not to be storable within the LPM;

relinquish packet management to the second storage system;

set a first lock; and

set a second lock corresponding to an originating device of the given packet; and

wherein the second storage system is configured to;

receive an indication from the first storage system that the given packet is not storable in the LPM;

in response to receiving the indication, manage the given packet; and

wherein setting the first lock causes the system to buffer additional incoming packets until the system completes a first action in response to the determination that the given packet is not storable within the LPM and wherein setting the second lock causes the system to prevent packet overflow from initiating for subsequent packets from the same originating device before receiving an acknowledgement.

2. The system of claim 1 wherein to manage the given packet, the second storage system is further configured to drop the given packet.

3. The system of claim 2 wherein the first action comprises sending a control packet to an external device from which the given packet was received indicating that the given packet was dropped.

4. The system of claim 1 wherein to manage the given packet, the second storage system is further configured to store the given packet in the EPM.

5. The system of claim 4 wherein the first storage system provides a memory address to the second storage system if the given packet cannot be stored in the LPM.

6. The system of claim 5 wherein the first action comprises determining a next memory address at which to store a next packet in the EPM.

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

8. The system of claim 1 wherein the LPM is mapped into pre-configured memory units.

9. A data packet router comprising:

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

a system coupled to the external ports and configured to manage packets incoming to the data packet router, the system comprising;

a local packet memory (LPM) configured 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 the LPM and to a second storage system;

wherein the first storage system is configured to;

determine whether said packets can be stored in the LPM;

if a given packet is determined not to be storable within the LPM;

relinquish packet management to the second storage system; and

set a lock; and

wherein the second storage system is configured to;

receive an indication from the first storage system that the given packet is not storable in the LPM;

in response to receiving the indication, manage the given packet; and

wherein setting the lock causes the system to buffer additional incoming packets until the system completes a first action in response to the determination that the given packet is not storable within the LPM.

10. The router of claim 9 wherein to manage the given packet, the second storage system is further configured to drop the given packet.

11. The router of claim 10 wherein the first action comprises sending a control packet to an external device from which the given packet was received indicating that the given packet was dropped.

12. The router of claim 9 wherein to manage the given packet, the second storage system is further configured to store the given packet in the EPM.

13. The router of claim 12 wherein the first storage system provides a memory address to the second storage system if the given packet cannot be stored in the LPM.

14. The router of claim 13 wherein the first action comprises determining a next memory address at which to store a next packet in the EPM.

15. The router of claim 9 wherein the first storage system is hardware controlled and the second storage system is software-controlled.

16. The router of claim 9 wherein the LPM is mapped into pre-configured memory units.

17. A method for managing packets incoming to a data router, the method comprising:

storing incoming packets for processing in a local packet memory (LPM);

determining whether a given packet can be stored in the LPM by a first storage system;

if the given packet is determined not to be storable within the LPM;

sending an indication to a second storage system; and

setting a first lock; and

setting a second lock corresponding to an originating device of the given packet; and

the second storage system;

receiving the indication that the given packet is not storable in the LPM;

in response to receiving the indication, managing the given packet;

wherein setting the first lock causes the system to buffer additional incoming packets until the system completes a first action in response to the determination that the given packet is not storable within the LPM and wherein setting the second lock causes the system to prevent packet overflow from initiating for subsequent packets from the same originating device before receiving an acknowledgement.

18. The method of claim 17 wherein managing the given packet further comprises dropping the given packet.

19. The method of claim 18 wherein the first action comprises sending a control packet to an external device from which the given packet was received indicating that the given packet was dropped.

20. The method of claim 17 wherein managing the given packet further comprises storing the given packet in an external packet memory (EPM).

21. The method of claim 20 further comprising providing a memory address to the second storage system if the given packet cannot be stored in the LPM.

22. The method of claim 21 wherein the first action comprises determining a next memory address at which to store a next packet in the EPM.

23. The method of claim 17 wherein the LPM is mapped into pre-configured memory units.