Memory organization in a switching device

• US 6,493,347 B2
• Filed: 07/24/1997
• Issued: 12/10/2002
• Est. Priority Date: 12/16/1996
• Status: Expired due to Term

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Agarwal, Nalini, Ferguson, Dennis C., Lim, Raymond Marcelino Manese, Sindhu, Pradeep S., Liencres, Bjorn O., Oskouy, Rasoul Mirzazadeh, Veeragandham, Sreeram, Ju, Hann-Hwan
• Primary Examiner(s): TON, DANG T
• Application Number:
  US08/901,061
• Publication Number:
  US 20010010692A1
• Time in Patent Office: 1,965 Days
• Field of Search: 370/395, 370/389, 370/396, 370/397, 370/351, 370/352, 370/354, 370/355, 370/428, 370/412, 370/429, 370/413, 370/414-418, 370/442, 370/368, 370/363, 370/353, 370/398, 370/395.1, 370/395.31, 370/395.53, 370/395.6, 370/395.61, 370/395.64, 370/395.65, 370/395.7, 370/395.71, 370/399, 370/401, 370/475, 340/825.01, 340/825.03
• US Class Current: 370/401
• 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 a data packet from a source to a destination in a network, the router comprising:

an input port for receiving the data packet, the data packet formatted in accordance with a first protocol;

a divider for dividing the data packet into uniform length cells for temporary storage in the router, the divider dividing the data packet without changing the formatting of the data packet;

a distributed memory comprising a plurality of physically separated memory banks, each memory bank including a global data area for storing a portion of the data packet;

an input switch for streaming across the memory banks uniform portions of the data packet such that consecutive cells associated with the data packet are stored in consecutive banks of the distributed memory;

a controller for determining packet routing through the router;

an output switch for extracting in order the portions of the data packet stored in the global data area of each memory bank including reassembling the cells in proper order to reconstruct the data packet formatted in accordance with the first protocol and forwarding the data packet to an appropriate output port; and

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

2. An apparatus for use in a router, the router for switching data packets from a source to a destination in a network, the router including one or more input ports for receiving data packets, a divider for dividing the data packets into uniform portions without changing the format of the data packet and one or more output ports operable to forward the data packets to other devices on the network based on routing decisions made by the router, the apparatus comprising:

a distributed memory comprising a plurality of physically separated memory banks;

a switch coupled to the divider operable to stream the uniform portions to the memory banks where consecutive cells associated with a data packet are stored in consecutive memory banks;

each memory bank operable to store uniform portions of a data packet received from the source and linking information to allow for the extraction of the uniform portions of the data packet from the plurality of memory banks in proper order after a routing determination has been made by the rout4er such that the data packet as originally formatted can be routed to another device in the network.

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 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 a 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 without changing the formatting of the data packet;

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 including storing consecutive cells associated with a data packet in consecutive memory banks of the global data buffer; and

a switch for gathering cells associated with the data packet from the global data buffer and reconstructing the data packet prior to forwarding the packet to the destination.

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 step of determining the fullness of the stream queue 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.