Apparatus and method for managing memory in a network switch

• US 6,912,637 B1
• Filed: 06/23/2000
• Issued: 06/28/2005
• Est. Priority Date: 07/08/1998
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Herbst, Joseph
• Primary Examiner(s): Anderson, Matthew
• Assistant Examiner(s): LI, ZHUO H
• Application Number:
  US09/602,474
• Time in Patent Office: 1,831 Days
• Field of Search: 711 3- 4, 711167-168, 711170-173, 711/202, 713/178, 713/500, 713/502, 713/600, 709/102, 709/200, 709/215, 709/229, 707/206, 707/202
• US Class Current: 711/167
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 12/46 Interconnection of networks
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/2458 Modification of priorities while in transit
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/623 Weighted service order
• CPC Class Codes: H04L 47/745 Reaction in network
• CPC Class Codes: H04L 47/827 : Aggregation of resource allocation or reservation requests
• CPC Class Codes: H04L 49/102 : using shared medium, e.g. bus or ring
• CPC Class Codes: H04L 49/103 : using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/109 : Integrated on microchip, e.g. switch-on-chip
• CPC Class Codes: H04L 49/25 : Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/3072 : Packet splitting
• CPC Class Codes: H04L 49/3081 : ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/309 : Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/351 : for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/352 : Gigabit ethernet switching [GBPS]
• CPC Class Codes: H04L 49/45 : Arrangements for providing or supporting expansion
• CPC Class Codes: H04L 49/555 : Error detection
• CPC Class Codes: H04L 49/606 : Hybrid ATM switches, e.g. ATM&STM, ATM&Frame Relay or ATM&IP
• 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/9063 : Intermediate storage in different physical parts of a node or terminal
• CPC Class Codes: H04L 49/9073 : Early interruption upon arrival of a fraction of a packet
• CPC Class Codes: H04L 49/9094 : Arrangements for simultaneous transmit and receive, e.g. simultaneous reading/writing from/to the storage element
• CPC Class Codes: H04L 67/10 : in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 69/14 : Multichannel or multilink protocols
• CPC Class Codes: H04L 69/16 : Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 : Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/323 : in the physical layer [OSI layer 1]
• CPC Class Codes: H04L 69/329 : in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 : Network security protocols
• CPC Class Codes: H04Q 11/0478 : Provisions for broadband connections

Abstract

The present invention is related to a method and apparatus for managing memory in a network switch, wherein the memory includes the steps of providing a memory, wherein the memory includes a plurality of memory locations configured to store data therein and providing a memory address pool having a plurality of available memory addresses arranged therein, wherein each of the plurality of memory addresses corresponds to a specific memory location. The method further includes the steps of providing a memory address pointer, wherein the memory address pointer indicates a next available memory address in the memory address pool, and reading available memory addresses from the memory address pool using a last in first out operation. The method also includes writing released memory addresses into the memory address pool, adjusting a position of the memory address pointer upon a read or a write operation from the memory address pool.

Claims

1. A method for managing memory in a network switch, said method comprising the steps of:

providing a memory, wherein the memory includes a plurality of memory locations configured to store data therein;

providing a memory address pool having a plurality of available memory addresses arranged therein, wherein each of the plurality of memory addresses corresponds to a specific memory location; and

providing a memory address pointer, wherein the memory address pointer indicates a next available memory address in the memory address pool;

wherein when a release of a released memory address does not occur in a same clock cycle as a request for an available address, the method further comprises;

reading available memory addresses from the memory address pool using a last in first out operation;

writing released memory addresses into the memory address pool; and

adjusting a position of the memory address pointer upon a read or a write operation from the memory address pool; and

wherein when the release of the released memory address occurs in the same clock cycle as the request for the available address, the method further comprises;

passing off the released memory addresses in place of the available memory addresses.

2. A method for managing memory in a network switch as recited in claim 1, wherein the steps of reading available memory addresses and writing released memory addresses are initiated during a second clock cycle when the reading step and the writing step are requested in a first clock cycle.

3. A method for managing memory in a network switch, said method comprising the steps of:

receiving a request from a module for a next available memory address in a first clock cycle, comprising providing an address pointer for indicating the next available memory address in a memory address pool, wherein the address pointer releases and address in a last-in first-out operation;

receiving a released memory address in the first clock cycle; and

passing off the released memory address to the module requesting the next available memory address in place of the next available memory addresses in a second clock cycle, which is a next clock cycle after the first clock cycle.

4. A method for managing memory in a network switch as recited in claim 3, wherein the passing off step operates without incrementing or decrementing a next available memory address pointer associated with the memory in the network switch.

5. A method for managing memory, said method comprising the steps of:

providing a memory having a predetermined number of memory storage locations therein;

providing a predetermined number of address in a stack, each of the predetermined number of addresses corresponding to a unique memory storage location; and

providing an address pointer for indicating a next available address to be used from the predetermined number of addresses in the stack, wherein the address pointer releases and address in a last-in first-out operation;

wherein the method further comprises a step of passing off an address released back to the stack to a request for an available address in place of a next available memory address when a release of an address back to the stack occurs in the same clock cycle as the request for an available address.

6. A method for managing memory as recited in claim 5, wherein the method further comprises passing off the address released without incrementing or decrementing the address pointer.

7. An apparatus for managing memory in a network switch, said apparatus comprising:

a memory address pool having a plurality of memory addresses, each of said plurality of memory addresses corresponding to an individual memory location in a memory; and

a memory controller in connection with said memory and said memory address pool,

wherein said memory controller manages an address pointer for indicating a next available memory address in said memory address pool and is configured to pass off the released memory address in place of the available memory address upon a request for the available memory address in the same clock cycle.

8. An apparatus for managing memory in a network switch as recited in claim 7, wherein said memory address pool further comprises a cell free address pool.

9. An apparatus for managing memory in a network switch as recited in claim 7, wherein said memory address pool further comprises a slot free address pool.

10. An apparatus for managing memory in a network switch as recited in claim 7, wherein said memory controller is further configured to read an available memory address from said memory address pool and to write a released memory address to said address pool.

11. An apparatus for managing memory in a network switch as recited in claim 10, wherein said memory controller is further configured to pass off the released memory address upon a request for the available memory address in the same clock cycle without adjusting said address pointer.

12. An apparatus for managing memory in a network switch, said apparatus comprising:

a memory address pool in connection with said memory, said memory address pool having a predetermined number of memory addresses therein, each of said predetermined number of memory addresses corresponding to an individual memory location in the memory; and

a memory controller in connection with said memory and said memory address pool,

wherein said memory controller passes off a released memory address to a request for an available memory address in place of the available memory address when the request for said available memory address is received during the same clock cycle as said released memory address is released.

13. An apparatus for managing memory in a network switch as recited in claim 12, wherein said memory further comprises SDRAM.

14. An apparatus for managing memory in a network switch as recited in claim 12, wherein said memory further comprises SRAM.

15. An apparatus for managing memory in a network switch as recited in claim 12, wherein said memory address pool further comprises a cell free address pool.

16. An apparatus for managing memory in a network switch as recited in claim 12, wherein said memory address pool further comprises a slot free address pool.

17. An apparatus for managing memory in a network switch as recited in claim 12, wherein said memory controller further comprises a common buffer pool controller.

18. An apparatus for managing memory in a network switch as recited in claim 12, wherein said memory controller further comprises a SDRAM controller.

19. An apparatus for managing memory in a network switch, said apparatus comprising:

a memory, wherein the memory includes a plurality of memory locations configured to store data therein;

a memory address pool having a plurality of available memory addresses arranged therein, wherein each of the plurality of memory addresses corresponds to a specific memory location;

means for managing a memory address pointer, wherein the memory address pointer indicates a next available memory address in the memory address pool;

means for reading available memory addresses from the memory address pool using a last in first out operation;

means for writing released memory addresses into the memory address pool; and

means for adjusting a position of the memory address pointer upon a read or a write operation from the memory address pool,

wherein said means for reading and said means for writing are configured to pass off an available memory address in place of a next available memory address when a request to read an address is received during the same clock cycle as a request to write an address.