Method and apparatus for reordering packet data units in storage queues for reading and writing memory

• US 6,757,791 B1
• Filed: 03/30/1999
• Issued: 06/29/2004
• Est. Priority Date: 03/30/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: OʼGrady, Robert, Tran, Sonny N., Dan, Yie-Fong, Wilford, Bruce
• Primary Examiner(s): Gossage, Glenn
• Application Number:
  US09/282,080
• Time in Patent Office: 1,918 Days
• Field of Search: 711/5, 711/157, 711/158, 711/153, 711/154, 711/167, 710/39, 710/54, 710/52, 370/386, 370/412, 370/413, 370/414, 370/419
• US Class Current: 711/154
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9094 Arrangements for simultaneous transmit and receive, e.g. simultaneous reading/writing from/to the storage element

Abstract

A method and system for reordering data units that are to be written to, or read from, selected locations in a memory are described herein. The data units are reordered so that an order of accessing memory is optimal for speed of reading or writing memory, not necessarily an order in which data units were received or requested. Packets that are received at input interfaces are divided into cells, with cells being allocated to independent memory banks. Many such memory banks are kept busy concurrently, so cells (and thus the packets) are read into the memory as rapidly as possible. The system may include an input queue for receiving data units in a first sequence and a set of storage queues coupled to the input queue for receiving data units from the input queue. The data units may be written from the storage queues to the memory in an order other than the first sequence. The system may also include a disassembly element for generating data units from a packet and a reassembling element for reassembling a packet from the data units.

Claims

1. A method including steps for

receiving data units for writing to a memory, said data units being received in a first sequence;

storing said data units in a set of storage queues, wherein storing includes advancing a number of said data units out of said first sequence; and

writing data units from said set of storage queues to a plurality of regions of said memory, in an order other than the order of said first sequence.

2. A method as in claim 1, wherein writing said data units in an order other than the order of said first sequence enables concurrent access to a plurality of independent memory banks comprising said memory.

3. A method as in claim 1, wherein the size of said data units is uniform.

4. A method as in claim 1, wherein

said memory has a busy time for each of said regions;

said memory has a latency time for each of said regions, said latency time being greater than said busy time for each region;

whereby the writing of data units occurs with less latency than writing said data units in said first sequence.

5. A method as in claim 1, wherein said plurality of regions are located in memory elements capable of operating in parallel.

6. A method as in claim 1, wherein said step for storing is performed in an order of said first sequence.

7. A method as in claim 1, wherein the writing of data units occurs in an order that is optimal for writing said data units into said memory with respect to at least one of the following parameters:

(1) latency and (2) speed.

8. A method as in claim 1, further including steps for

reading data units from said memory in a sequence;

storing said sequence of data units in a set of reassembly queues; and

reordering said data units as they are output from said reassembly queues to a set of output queues.

9. A method as in claim 1, wherein said plurality of regions are located in a plurality of independent memory banks comprising said memory.

10. A method as in claim 9, wherein said plurality of independent memory banks operate concurrently.

11. A method as in claim 1, wherein said first sequence of data units comprises a sequence in which said data units are present in a packet, said method further including steps for

receiving said packet;

and

disassembling said packet into said data units.

12. A method as in claim 11, further including steps for

reading data units from said memory;

and

reassembling said packet from said data units read from said memory.

13. A memory controller apparatus coupled to a memory, said apparatus including

an input queue capable of receiving data units in a first sequence;

a set of storage queues coupled to said input queue and receiving said data units from said input queue such that adjacent data units in said sequence are stored in differing storage queues, wherein a number of said data units are advanced out of said first sequence; and

dequeuing element coupled to said storage queues, wherein said dequeuing element controls the writing of said data units from said storage queues to said memory in an order other than said first sequence.

14. Apparatus as in claim 13, wherein the size of said data units is uniform.

15. Apparatus as in claim 13, wherein said dequeuing element is disposed for reordering said data units stored in said storage queues so as to maintain busy a plurality of memory banks that operate independently in said memory.

16. Apparatus as in claim 13, wherein said dequeuing element operates to write said data units in an order that is optimal for writing into said memory with respect to at least of one of the following parameters:

(1) latency and (2) speed.

17. Apparatus as in claim 13, wherein

said memory has a busy time for each of said regions;

said memory has a latency time for each of said regions, said latency time being greater than said busy time for each said region; and

said dequeuing element operates to write to said memory with less latency than writing said data units in said first sequence.

18. Apparatus as in claim 13, wherein said memory includes a plurality of memory elements capable of operating in parallel.

19. Apparatus as in claim 13, wherein said first sequence of data units comprises a sequence in which said data units are present in a packet, and wherein said apparatus further includes a disassembly element capable of generating one or more of said data units from said packet.

20. Apparatus as in claim 19, wherein said memory controller is disposed for

reading said data units from said memory;

and

reassembling said packet from said data units read from said memory.

21. Apparatus as in claim 13, wherein said memory includes a plurality of independent memory banks.

22. Apparatus as in claim 21, wherein a plurality of said memory banks operate concurrently.

23. A method of rapidly storing packets in a memory of a packet-switching router, comprising the computer-implemented steps of:

receiving a plurality of packets in a set of input queues for writing to a memory;

disassembling said packets into data units in a first sequence;

storing said data units in a set of storage queues, wherein said step of storing includes

advancing a number of said data units out of said first sequence;

dequeuing said data units from said storage queues; and

writing said data units from said set of storage queues to a plurality of regions of said memory in an order other than the order of said first sequence.

24. A method as recited in claim 23, further comprising the steps of:

reading data units from said memory in a sequence;

storing said sequence of data units in a set of reassembly queues; and

reordering said data units as they are output from said reassembly queues to a set of output queues.

25. A memory controller apparatus coupled to a memory, said apparatus including

a set of input queues capable of receiving packets;

a disassembly element coupled to said set of input queues, said disassembly element disassembling said packets into data units in a first sequence;

a set of storage queues coupled to said disassembly element and receiving said data units from said disassembly element such that adjacent data units in said first sequence are stored in differing storage queues, wherein a number of data units are advanced out of said first sequence; and

a dequeuing element coupled to said storage queues, wherein said dequeuing element controls the writing of said data units from said storage queues to said memory in an order other than said first sequence, said dequeuing element further dequeuing said data units from said storage queues.

26. Apparatus as in claim 25, wherein said apparatus further includes

a reading element capable of reading data units from a memory in a first sequence;

a set of reassembly queues coupled to said reading element and capable of storing said data units; and

a reassembly element coupled to said reassembly queues, said reassembly element reordering and outputting said data units to a set of output queues.