Memory organization in a switching device

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.

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.

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.