Scalable packet routing and switching device and method

• US 7,710,991 B1
• Filed: 04/14/2003
• Issued: 05/04/2010
• Est. Priority Date: 06/20/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Barnes, Peter M., Lynch, William L., Li, Anthony J.
• Primary Examiner(s): Kumar; Pankaj
• Assistant Examiner(s): Mais; Mark A
• Application Number:
  US10/414,135
• Time in Patent Office: 2,577 Days
• Field of Search: 370/389, 370/392, 370/401, 370412-415, 370/431, 370/432, 370474-476, 370/217, 370/219, 370/221, 370235-238, 370/390, 370/396, 370/395.1, 370/395.21, 370/395.31, 370/411
• US Class Current: 370/414
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 45/58 Association of routers
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 49/15 Interconnection of switching modules

Abstract

Methods of routing and switching a packet from an incoming link to an outgoing link of a router. In one example, the method includes assigning a destination queue to the packet, determining if the router is implemented in a scaled-down configuration, remapping the destination queue to one or more remapped destination queues, and storing the packet in the one or more remapped destination queues. In one embodiment, the method may also include requesting a packet from the destination queue, translating the request to the remapped destination queue, and transmitting the packet from the remapped destination queue.

Claims

1. A method for storing a packet in a memory of a router, comprising:

based on a destination address of the packet, assigning the packet to at least one outgoing link of the router;

assigning to the packet a destination queue associated with the at least one outgoing link of the router, assigning of the destination queue being based on a full-scale configuration in which the router has one or more switchcards, each switchcard having two or more memory control units;

determining if the router is implemented in a scaled-down configuration in which, on at least one of the one or more switchcards, a reduced number of memory control units are available relative to the full-scale configuration, and determining the number of memory control units which are available in the scaled-down configuration; and

storing the packet in at least one remapped destination queue in the memory based in part on the assigned outgoing link and on the determined number of memory control units.

2. The method of claim 1, wherein the destination queue is mapped to the at least one assigned outgoing link prior to storing the packet.

3. The method of claim 1 wherein the determining operation further includes assigning a queue offset number.

4. The method of claim 3, wherein the at least one remapped destination queue includes, as a function of the queue offset number, at least one destination queue additional to the assigned destination queue.

5. The method of claim 4, wherein the storing operation includes dividing the packet into at least two cells.

6. The method of claim 5, further comprising writing the at least two cells from a striper to the remapped destination queues in a parallel arrangement.

7. The method of claim 4, wherein the storing operation writes the at least two cells in the at least one additional destination queue.

8. The method of claim 7, wherein the storing operation writes the at least two cells in the at least one remapped destination queue contiguously in round robin order.

9. The method of claim 1, wherein the determining if the router is implemented in a scaled-down configuration includes determining how many line cards, switch cards, and memory control units are available.

10. The method of claim 1,

further comprising remapping to the packet to the at least one remapped destination queue based on a number of memory control units and line card units available.

11. A method of routing and switching a packet from an incoming link to an outgoing link of a router, the method comprising:

assigning a destination queue to the packet prior to storing the packet for switching, assigning of the destination queue being based on a full-scale configuration in which the router has one or more switchcards, each switchcard having two or more memory control units;

determining if the router is implemented in a scaled-down configuration in which, on at least one of the one or more switchcards, a reduced number of memory control units are available relative to the full-scale configuration, and determining the number of memory control units which are available in the scaled-down configuration

based on the determining, remapping the destination queue to one or more remapped destination queues; and

storing the packet in the one or more remapped destination queues.

12. The method of claim 11, further comprising:

requesting a packet from the destination queue;

translating the request to the one or more remapped destination queues; and

transmitting the packet from the one or more remapped destination queues.

13. A router comprising:

memory including a plurality of memory control units to store packets, the memory having a full-scale configuration comprising one or more switchcards, each switchcard having two or more memory control units; and

at least one processor configured to;

assign the packet to at least one outgoing link of the router based on a destination address of the packet;

assign to the packet a destination queue associated with the at least one outgoing link of the router, assigning of the destination queue being based on the full-scale configuration;

determine if the router is implemented in a scaled-down configuration in which, on at least one of the one or more switchcards, a reduced number of memory control units are available relative to the full-scale configuration, and determine the number of memory control units which are available in the scaled-down configuration; and

store the packet in at least one remapped destination queue in the memory based in part on the assigned outgoing link and on the determined number of memory control units.

14. The router of claim 13, wherein the destination queue is mapped to the assigned outgoing link prior to storage of the packet for switching.

15. The router of claim 13, wherein the at least one remapped destination queue includes, based on an assigned queue offset number, at least one destination queue additional to the assigned destination queue.

16. The router of claim 13, wherein the processor is configured to

remap to the packet to the at least one remapped destination queue based on the determined number of memory control units and line card units available.