Scalable high speed router apparatus

• US 7,466,703 B1
• Filed: 04/30/1999
• Issued: 12/16/2008
• Est. Priority Date: 05/01/1998
• Status: Expired due to Fees

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Stiliadis, Dimitrios, Arunachalam, Raman, Tzeng, Hong-Yi, Rathnavelu, Sunder R, Kumar, Vijay P
• Primary Examiner(s): NGUYEN, HANH N
• Application Number:
  US09/303,718
• Time in Patent Office: 3,518 Days
• Field of Search: 370/389, 370/392, 370/399, 370/409, 370/359, 370/229, 370/231, 370/419, 370/428, 370/412, 370/413, 370/400, 370/351, 370/395.3
• US Class Current: 370/392
• 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/60 Router architectures
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags

Abstract

A scalable, high-speed router for routing packets of information through an interconnected network comprises an interface for receiving a packet containing header and data information; a device for extracting routing information from the header of an arrived packet and generating a corresponding header packet for the arrived packet; a memory device for storing the data information of the arrived packet at predetermined memory locations; a device for processing the corresponding header packet to determine a route for the arrived packet and assigning packet forwarding information to the header packet; and, a device for retrieving the data information from the predetermined memory locations and forwarding both the data and header packet containing the packet forwarding information to the interface for routing the packet to a further destination in accordance with the packet forwarding information. The processing device includes devices performing filtering, route-table lookup and flow identification functions and which devices are organized in a pipelined fashion for successive, high-speed operations on the header packet. The router ensures that the arrived packet is forwarded in accordance with any quality of service requirements and flow specifications.

Claims

1. A scalable, high-speed router for routing packets of information through an interconnected network, said router comprising:

a) an interface means for receiving a packet including a header and data information;

b) means for extracting routing information from said header of said arrived packet and generating a header packet for said arrived packet, wherein said header packet includes said routing information extracted from said header of said arrived packet;

c) memory means for storing said data information of said arrived packet at predetermined memory locations;

d) means for processing said header packet to determine a route for said arrived packet, said processing means assigning packet forwarding information to said header packet; and

e) means for retrieving said data information from said predetermined memory locations and forwarding said data information and said header packet including said packet forwarding information to said interface means for routing said arrived packet to a further destination in accordance with said packet forwarding information.

2. A scalable, high-speed router for routing packets as claimed in claim 1, wherein said interface means includes scheduler means for forwarding said processed packet;

wherein, if said packet forwarding information includes a quality of service requirement, said scheduler means forwards said arrived packet in accordance with said quality of service requirement;

wherein, if said packet forwarding information includes a flow specification, said scheduler means forwards said arrived packet in accordance with said flow specification.

3. A scalable, high-speed router for routing packets as claimed in claim 2, wherein said scheduler means includes means for implementing a weighted fair-queuing scheduling scheme.

4. A scalable, high-speed router for routing packets as claimed in claim 1, wherein said routing information included in said header packet includes source and destination addresses and other routing parameters, said processing means further including filter means for determining propriety of said arrived packet to be routed based on one or more of said source addresses, destination addresses and other routing parameters.

5. A scalable, high-speed router for routing packets as claimed in claim 1, wherein said processing means further includes route look-up table means for determining a destination address to which said arrived packet is to be forwarded, wherein said destination address is determined from said header packet.

6. A scalable, high-speed router for routing packets as claimed in claim 5, wherein said processing means further includes flow identification means for receiving said arrived packet and assigning said arrived packet to a specific flow.

7. A scalable, high-speed router for routing packets as claimed in claim 6, wherein said flow identification means forwards said header packet including said packet forwarding information to said interface means for use in routing said arrived packet.

8. A scalable, high-speed router for routing packets as claimed in claim 1, wherein said memory means is a high speed buffer memory.

9. A scalable, high-speed router for routing packets as claimed in claim 1, wherein said data information of said arrived packet is stored as successive pages in said predetermined memory locations, said router further including link list manager means for tracking address locations for said successive pages containing said data information of said arrived packet.

10. A scalable, high-speed router for routing packets as claimed in claim 7, wherein said filtering means, route-table look-up means, and flow identification means are organized in a pipelined fashion that successively operate on said header packet and assign said packet forwarding information to said header packet.

11. A method for routing packets of information in an interconnected network, said method comprising the steps of:

a) receiving a packet including a header and data information;

b) extracting routing information from said header of said arrived packet and generating a header packet for said arrived packet, wherein said header packet includes said routing information extracted from said header of said arrived packet;

c) storing said data information of said arrived packet at predetermined memory locations;

d) processing said header packet to determine a route for said arrived packet and assigning packet forwarding information to said header packet; and

e) retrieving said data information from said predetermined memory locations and forwarding said data information and said header packet including said packet forwarding information for routing said arrived packet to a further destination in accordance with said packet forwarding information.

12. A method for routing packets of information as claimed in claim 11, wherein said routing information included in said header packet includes source and destination addresses and other routing parameters, said processing step d) further including the step f) of determining the propriety of said arrived packet to be routed based on one or more of said source addresses, destination addresses and other routing parameters.

13. A method for routing packets of information as claimed in claim 12, wherein said processing step d) further includes the step g) of determining a destination address to which said arrived packet is to be forwarded, wherein said destination address is determined from said header packet.

14. A method for routing packets of information as claimed in claim 13, wherein said processing step d) further includes the step h) of assigning said arrived packet to a specific flow.

15. A method for routing packets of information as claimed in claim 14, wherein said processing steps f), g), and h) are successively performed in a pipe-lined fashion.

16. A network router comprising:

a) an interface for receiving and transmitting packets, each packet containing comprising a header and data information;

b) means for extracting routing information from an arrived packet and generating a packet record corresponding to the arrived packet, the packet record corresponding to the arrived packet comprising routing and processing information included in the arrived packet;

c) memory for storing data information of the arrived packet at predetermined memory locations;

d) a processor for processing the packet record corresponding to the arrived packet and determining a route and resource assignments for the arrived packet, the processor assigning packet forwarding information to the packet record corresponding to the arrived packet;

e) means for retrieving the data information of the arrived packet from the predetermined memory locations and assembling an outgoing packet corresponding to the arrived packet from the data information of the arrived packet, the packet record corresponding to the arrived packet, and the packet forwarding information assigned to the packet record corresponding to the arrived packet;

f) means for queuing and scheduling for transmission the outgoing packet corresponding to the arrived packet, the queuing and scheduling being based on quality-of-service requirements of the arrived packet; and

g) means for forwarding the outgoing packet corresponding to the arrived packet to the interface for transmitting the outgoing packet to a further destination in accordance with the forwarding information assigned to the packet record corresponding to the arrived packet.