Memory organization in a network device

• US 8,761,180 B2
• Filed: 03/20/2013
• Issued: 06/24/2014
• Est. Priority Date: 12/16/1996
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Ferguson, Dennis, Liencres, Bjorn, Agarwal, Nalini, Ju, Hann-Hwan, Lim, Raymond Marcelino Manese, Oskouy, Rasoul Mirzazadeh, Veeragandham, Sreeram, Sindhu, Pradeep
• Primary Examiner(s): RIYAMI, ABDULLAH A
• Application Number:
  US13/847,880
• Publication Number:
  US 20130215886A1
• Time in Patent Office: 461 Days
• Field of Search: 370/351, 370/352, 370/353, 370/354, 370/355, 370/363, 370/368, 370/389, 370/395.1, 370/395.6, 370/395.7, 370/395.31, 370/395.53, 370/395.61, 370/395.64, 370/395.65, 370/395.71, 370/396, 370/392, 370/397, 370/401, 370/412, 370/413, 370/414, 370/415, 370/416, 370/417, 370/418, 370/428, 370/429, 370/442
• US Class Current: 370/392
• CPC Class Codes: G06F 15/167 using a common memory, e.g. mailbox
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5652 Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• 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/72 Routing based on the source address
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 49/103 using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/108 using shared central buffer
• CPC Class Codes: H04L 49/1538 Cell slicing
• CPC Class Codes: H04L 49/203 ATM switching fabrics with multicast or broadcast capabilities
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/252 Store and forward routing
• 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/608 ATM switches adapted to switch variable length packets, e.g. IP packets
• 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/9042 : Separate storage for different parts of the packet, e.g. header and payload
• CPC Class Codes: H04L 49/9047 : including multiple buffers, e.g. buffer pools
• CPC Class Codes: H04L 49/9057 : Arrangements for supporting packet reassembly or resequencing
• CPC Class Codes: H04L 69/22 : Parsing or analysis of headers
• CPC Class Codes: H04L 9/40 : Network security protocols
• CPC Class Codes: H04Q 11/0478 : Provisions for broadband connections

Abstract

A router for switching data packets from a source to a destination in a network in which the router includes a distributed memory. The distributed memory includes two or more memory banks. Each memory bank is used for storing uniform portions of a data packet received from a source and linking information for each data packet to allow for the extraction of the uniform portions of a data packet from distributed locations in memory in proper order after a routing determination has been made by the router.

Claims

1. A network device comprising:

one or more processors to;

identify a key for a data unit having a plurality of portions,

identify an output port for the data unit based on the key,

determine a quantity of the plurality of portions included in the data unit,

determine that the quantity of the plurality of portions is greater than a particular quantity,

identify an offset associated with a portion, of the plurality of portions of the data unit, after determining that the quantity of the plurality of portions is greater than the particular quantity, and

forward the data unit via the output port based on the offset.

2. The network device of claim 1, where, when identifying the key, the one or more processors are to:

identify the key based on information included in a data block of the data unit.

3. The network device of claim 1, where, when identifying the output port, the one or more processors are to:

perform a lookup based on the key, and

identify the output port based on the lookup.

4. The network device of claim 1, where the one or more processors are further to:

divide the data unit into the plurality of portions, and

store the plurality of portions in a memory after dividing the data unit.

5. The network device of claim 4, where the plurality of portions are of uniform length.

6. The network device of claim 1, where the one or more processors are further to:

determine a starting address of a memory where the portion is to be stored, and

store the starting address in an entry, of a buffer, associated with the data unit.

7. The network device of claim 6, where the one or more processors are further to:

determine another offset associated with a location at which another portion, of the plurality of portions, is to be stored, and

store information identifying the other offset in the entry.

8. The network device of claim 1, where the one or more processors are further to:

receive the data unit before identifying the key.

9. The network device of claim 1, where the one or more processors are further to:

store the key in a buffer,

the buffer including a plurality of entries, and

a particular entry, of the plurality of entries, including a starting address, and

store the portion based on the starting address in the particular entry.

10. A method comprising:

identifying, by a network device, a key for a data unit having a plurality of portions;

identifying, by the network device, an output port for the data unit based on the key;

determining, by the network device, a quantity of the plurality of portions included in the data unit;

determining, by the network device, that the quantity of the plurality of portions is greater than a particular quantity;

identifying, by the network device, an offset associated with a portion, of the plurality of portions of the data unit, after determining that the quantity of the plurality of portions is greater than the particular quantity; and

forwarding, by the network device, the data unit via the output port based on the offset.

11. The method of claim 10, further comprising:

determining a starting address of a memory; and

storing the starting address in an entry, of a buffer, associated with the data unit.

12. The method of claim 11, further comprising:

storing the portion, of the plurality of the portions, in the memory at the starting address.

13. The method of claim 10, where identifying the key comprises:

identifying the key based on information included in a data block of the data unit.

14. The method of claim 10, where identifying the output port comprises:

performing a lookup based on the key, and

identifying the output port based on the lookup.

15. The method of claim 10, further comprising:

storing the key in a buffer,

the buffer including a particular entry associated with the portion of the plurality of portions, and

the particular entry including a starting address and an offset associated with the starting address; and

storing the portion in a memory based on the starting address and the offset in the particular entry.

16. The method of claim 10, further comprising:

dividing the data unit into the plurality of portions,

the plurality of portions being of uniform length; and

storing the plurality of portions in a memory after dividing the data unit.

17. A non-transitory computer-readable medium storing instructions, the instructions comprising:

one or more instructions that, when executed by at least one processor, cause the at least one processor to;

identify a key for a data unit having a plurality of portions,

identify an output port for the data unit based on the key,

determine a quantity of the plurality of portions included in the data unit,

determine that the quantity of the plurality of portions satisfies a particular quantity,

identify an offset associated with a portion, of the plurality of portions of the data unit, after determining that the quantity of the plurality of portions satisfies the particular quantity, and

forward the data unit via the output port based on the offset.

18. The non-transitory computer-readable medium of claim 17, where the instructions further comprise:

one or more instructions that, when executed by the at least one processor, cause the at least one processor to;

receive the data unit,

divide the data unit into the plurality of portions, and

store the plurality of portions in a memory.

19. The non-transitory computer-readable medium of claim 17, where the instructions further comprise:

one or more instructions that, when executed by the at least one processor, cause the at least one processor to;

extract the key from the data unit, and

store the key in an entry, of a buffer, associated with the portion.

20. The non-transitory computer-readable medium of claim 17, where the instructions further comprise:

one or more instructions that, when executed by the at least one processor, cause the at least one processor to;

determine a starting address of a memory where the portion is to be stored, and

store the starting address in an entry, of a buffer, associated with the data unit.