MEMORY ORGANIZATION IN A SWITCHING DEVICE

• US 20010010692A1
• Filed: 07/24/1997
• Published: 08/02/2001
• Est. Priority Date: 12/16/1996
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: AGARWAL, NALINI, LIENCRES, BJORN O., LIM, RAYMOND MARCELINO MANESE, VEERAGANDHAM, SREERAM, JU, HANN-HWAN, FERGUSON, DENNIS C., SINDHU, PRADEEP S., OSKOUY, RASOUL MIRZAZADEH
• Granted Patent: US 6,493,347 B2
• Time in Patent Office: Days
• US Class Current: 370/395.7
• 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 router for switching data packets from a source to a destination in a network, the router comprising:

an input port for receiving a data packet;

a physically distributed memory including two or more banks, each memory bank including a global data area for storing portions of the data packet;

an input switch for streaming across the memory banks uniform portions of the data packet;

a controller for determining packet routing through the router;

an output switch for extracting in order the portions of packet data stored in the global data area of each memory bank and forwarding the packet data to an appropriate output port; and

an output port for transferring the data packet to the destination.

2. A router for switching data packets from a source to a destination in a network, the router comprising:

a distributed memory comprising two or more memory banks, each memory bank 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.

3. The apparatus of

claim 2

wherein the distributed memory includes an output queue for storing a notification indicative of the routing of the data packet through the router.

4. The apparatus of

claim 3

wherein the notification includes linking information for retrieving at least a first cell of the data packet from the distributed memory.

5. The apparatus of

claim 4

wherein the notification includes linking information for the first 5 cells of the data packet.

6. The apparatus of

claim 3

wherein the notification includes an address for an indirect cell, the indirect cell stored in the distributed memory and including linking information for extracting cells in order from the distributed memory.

7. The apparatus of

claim 3

wherein each memory bank includes a global data area for storing portions of data packets and a notification area for storing notifications.

8. The apparatus of

claim 7

wherein the notification area is sized to be ⅕

of a size of the global data area for a given memory bank.

9. The apparatus of

claim 8

further including a plurality of multi-function multiports, each multi-function multiport including one or more input ports and output ports for receiving and transmitting data packets through the router.

10. The apparatus of

claim 9

wherein a portion of the distributed memory is located within each multi-function multiport such that each multi-function multiport includes a memory bank having a global data area and a notification area.

11. The apparatus of

claim 10

wherein the notification area of a given multi-function multiport stores notifications for data packets to be routed through an output port of the given multi-function multiport.

12. The apparatus of

claim 2

wherein memory reads and writes to and from the distributed memory are sized to be 64 bytes.

13. The apparatus of

claim 2

further including mapping means for mapping from a virtual address space to a physical address space associated with the distributed memory, the mapping means for detecting aged packets in memory and allowing for easy overwriting thereof such that garbage collection of aged packets is not required.

14. A method of routing a data packet through a router in a system transmitting data packets between a source and a destination over a network including the router, the method comprising:

receiving the data packet;

dividing the data packet into a cells of a fixed size;

storing the cells in a distributed memory, the distributed memory including two or more memory banks where consecutive cells from the data packet are stored in consecutive banks of the distributed memory; and

storing linking information in one bank of the memory for linking cells of the data packet that are stored throughout the distributed memory, the linking information used for extracting the cells in order for transmission from the router to the destination.

15. A method of storing a data packet in a router while a look-up engine determines the proper path through the router for the data packet in a system transmitting data packets between a source and a destination over a network including the router, the method comprising:

dividing the data packet into fixed length cells;

storing the cells and linking information for reconstructing the data packet across a global data buffer, the global data buffer including two or more memory banks where the data packet is divided among the memory banks.

16. A method for determining which data packets stored in a router are to be passed through the router in a system transmitting data packets between a source and a destination over a network including the router, the method comprising:

determining a route through the router for a data packet, the route including a notification indicating a starting address in memory where the data packet is stored;

processing the notification including queuing the notification with other notifications to be output on the same output port of the router in a stream queue;

determining the fullness of the stream queue;

determining a drop criterion based in part on fullness of the stream queue;

generating a random number;

comparing the random number and the drop criterion and dropping the notification based upon results of the comparison.

17. The method of

claim 16

wherein the fullness test is performed when the data packet reaches a head of the stream queue.

18. The method of

claim 16

wherein the fullness is a percentage and the random number generated is between zero and one.