Memory organization in a switching device

• US 7,903,659 B2
• Filed: 05/04/2009
• Issued: 03/08/2011
• Est. Priority Date: 12/16/1996
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Ferguson, Dennis C., Lim, Raymond Marcelino Manese, Sindhu, Pradeep S., Agarwal, Nalini, Liencres, Bjorn O., Oskouy, Rasoul Mirzazadeh, Veeragandham, Sreeram, Ju, Hann-Hwan
• Primary Examiner(s): Moe; Aung S
• Assistant Examiner(s): RIYAMI, ABDULLA A
• Application Number:
  US12/435,162
• Publication Number:
  US 20090268740A1
• Time in Patent Office: 673 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/397, 370/401, 370/412, 370/413, 370/414, 370/415, 370/416, 370/417, 370/418, 370/428, 370/429, 370/442, 370/392, 711/100, 711/144, 711/200, 711/207, 711/203, 711/209, 711/212, 711/220, 711/208, 711/211, 709/213, 709/121, 709/214, 709/223, 709/224, 709/226
• 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 network device switches variable length data units from a source to a destination in a network. An input port receives the variable length data unit and a divider divides the variable length data unit into uniform length data units for temporary storage in the network device. A distributed memory includes a plurality of physically separated memory banks addressable using a single virtual address space and an input switch streams the uniform length data units across the memory banks based on the virtual address space. The network device further includes an output switch for extracting the uniform length data units from the distributed memory by using addresses of the uniform length data units within the virtual address space. The output switch reassembles the uniform length data units to reconstruct the variable length data unit. An output port receives the variable length data unit and transfers the variable length data unit to the destination.

Claims

1. A network device, comprising:

a plurality of input ports to receive variable length data units;

a memory to temporarily store the variable length data units;

a buffer;

a data handler to;

receive a first variable length data unit of the variable length data units,

identify a key for the first variable length data unit,

store the key in an entry in the buffer, the entry being associated with the first variable length data unit,

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

store the starting address in the entry in the buffer associated with the first variable length data unit,

store the first portion in the memory,

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

store the offset in the entry in the buffer associated with the first variable length data unit;

a route lookup engine to

perform a lookup based on the key, and

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

an indirect cell processor, where when the first 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 first 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 header of the first variable length data unit.

3. The network device of claim 2, where the buffer includes a plurality of entries and each entry in the buffer is associated with one of a plurality of variable length data units, each entry comprising a starting address and at least one offset.

4. The network device of claim 3, where at least some of the 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 units 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 1, where the uniform length data 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 first variable length data unit is to be stored;

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

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

store the offset in the entry in the buffer associated with the first variable length data unit.

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

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

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

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

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

receiving, at a plurality of ports of the network device, variable length data units;

temporarily storing, at a memory of the network device, the variable length data units;

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

identifying, by the data handler, a key for the first variable length data unit;

storing, by the data handler, the key in an entry in a buffer, the entry being associated with the first variable length data unit;

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

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

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

storing, by the data handler, the offset in the entry in the buffer associated with the first variable length data unit;

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

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 first 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 first variable length data unit, exceeding more than a particular number of portions of the first variable length data unit.

11. The method of claim 10, further comprising:

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

12. The method of claim 11, where the buffer includes a plurality of entries and each entry in the buffer is associated with one of a plurality of variable length data units, each entry comprising a starting address and at least one offset.

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

14. The method claim 10, further comprising:

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

15. The method of claim 10, where the uniform length cells are 80 bytes in length.

16. The method of claim 10, where the data handler comprises a linking engine, where

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

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

determining the offset identifying where the next portion of the first variable length data unit is to be stored, and

storing the offset in the entry in the buffer associated with the first variable length data unit, are performed by the linking engine.

17. The method of claim 10, where the first variable length data unit comprises a packet.

18. The method of claim 10, further comprising:

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