Memory organization in a switching device

• US 8,477,784 B2
• Filed: 01/07/2011
• Issued: 07/02/2013
• Est. Priority Date: 12/16/1996
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Sindhu, Pradeep S., Ferguson, Dennis C., Liencres, Bjorn O., Agarwal, Nalini, Ju, Hann-Hwan, Lim, Raymond Marcelino Manese, Oskouy, Rasoul Mirzazadeh, Veeragandham, Sreeram
• Primary Examiner(s): RIYAMI, ABDULLAH A
• Application Number:
  US12/986,745
• Publication Number:
  US 20110164618A1
• Time in Patent Office: 907 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, 711/100, 711/144, 711/200, 711/207, 711/203, 711/209, 711/212, 711/220, 711/208, 711/211
• 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:

a data handler to;

receive a variable length data unit,

identify a key for the variable length data unit,

determine a starting address in a memory, where a first portion of the variable length data unit is to be stored,

store the first portion in the memory,

store a second portion of the variable length data unit in the memory, a location, in the memory, of the second portion being identified by an offset;

a route lookup engine to;

perform a lookup based on the key, and

identify, based on the lookup, an output port, of the network device, for the variable length data unit; and

an indirect cell processor, where when the variable length data unit comprises more than a particular number of portions, the indirect cell processor is to identify at least one offset associated with at least one portion, of the variable length data unit, exceeding the particular number of portions.

2. The network device of claim 1, where the data handler is to identify the key based on information included in a data block of the variable length data unit.

3. The network device of claim 2, further comprising:

a buffer to store the key, the buffer including a plurality of entries associated with one of a plurality of variable length data units, each entry, of the plurality of entries, comprising a starting address and at least one offset associated with the starting address.

4. The network device of claim 3, where at least some of the plurality of entries in the buffer include a plurality of offsets and an indirect cell address of an indirect cell.

5. The network device of claim 1, further comprising:

a divider to divide the variable length data unit into uniform length portions for storage in the memory, where the uniform length portions include the first portion and the second portion.

6. The network device of claim 5, where the uniform length portions units are 80 bytes in length.

7. The network device of claim 1, where the data handler comprises a linking engine, the linking engine to:

determine the starting address in the memory where the first portion of the variable length data unit is to be stored;

store the starting address in an entry in a buffer associated with the variable length data unit;

determine the offset identifying where the second portion of the variable length data unit is to be stored; and

store the offset identifying where the second portion of the variable length data unit is to be stored in the entry in the buffer associated with the variable length data unit.

8. The network device of claim 1, where the variable length data unit comprises a packet.

9. The network device of claim 1, further comprising:

the output port for forwarding the variable length data unit.

10. The network device of claim 1, where the offset identifying the second portion includes an offset address that is based on a location, in the memory, of a last portion of the variable length data unit and a value of a pointer associated with a current location that is to be written to in the memory.

11. A method of routing a variable length data unit through a network device located on a network, the method comprising:

receiving, at a data handler, a variable length data unit of a plurality of variable length data units;

identifying, by the data handler, a key for the variable length data unit of the plurality of variable length data units;

determining, by the data handler, a starting address in a memory, where a first portion of the variable length data unit is to be stored;

storing, by the data handler, the starting address in an entry in a buffer associated with the variable length data unit;

storing the first portion in the memory at the starting address;

storing, by the data handler, a second portion of the variable length data unit in the memory, a location, in the memory, of the second portion being identified by an offset;

performing, by a route lookup engine, a lookup based on the key;

identifying, by the route lookup engine, an output port of the network device for the variable length data unit based on the lookup; and

identifying, by an indirect cell processor, at least one offset associated with at least one portion, of the variable length data unit, exceeding more than a particular number of portions of the variable length data unit.

12. The method of claim 11, further comprising:

identifying, by the data handler, the key based on information included in a data block of the variable length data unit.

13. The method of claim 12, further comprising:

storing the key in the buffer, the buffer including a plurality of entries associated with one of the plurality of variable length data units, each entry, of the plurality of entries comprising a starting address and at least one offset associated with the starting address.

14. The method of claim 13, where at least some of the plurality of entries in the buffer include a plurality of offsets and an indirect cell address of an indirect cell.

15. The method claim 11, further comprising:

dividing, by a divider, the variable length data unit into uniform length portions for storage in the memory, where the uniform length portions include the first portion and the second portion.

16. The method of claim 11, where the uniform length portions are 80 bytes in length.

17. The method of claim 11, further comprising:

determining, by the data handler, the starting address, in the memory, where the first portion of the variable length data unit is to be stored,

storing, using the data handler, the starting address in the entry in the buffer associated with the variable length data unit,

determining, by the data handler, the offset identifying where the second portion of the variable length data unit is to be stored, and

storing, using the data handler, the offset identifying where the second portion of the variable length data unit is to be stored in the entry in the buffer associated with the variable length data unit.

18. The method of claim 11, where the variable length data unit comprises a packet.

19. The method of claim 11, further comprising:

forwarding, by a plurality of output ports, the plurality of variable length data units.

20. The method of claim 11, where the offset identifying the second portion includes an offset address that is based on a location, in the memory, of a last portion of the variable length data unit and a value of a pointer associated with a current memory location that is to be written to in the memory.