Route/service processor scalability via flow-based distribution of traffic

• US 6,853,638 B2
• Filed: 04/01/1998
• Issued: 02/08/2005
• Est. Priority Date: 04/01/1998
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Cohen, Earl
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Elallam, Ahmed
• Application Number:
  US09/053,237
• Publication Number:
  US 20020097736A1
• Time in Patent Office: 2,505 Days
• Field of Search: 370/235, 370/351, 370/352, 370/355, 370/359, 370/386, 370/389, 370/392, 370/411, 711/216, 370/401, 370/477, 713/153, 713/160
• US Class Current: 370/389
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]

Abstract

The invention provides a router architecture that is scalable, that is, as more processing power is desired, more individual processors can be added. The data flow from each line can be distributed among all of the processors in the system. As desired services are added, increasing the amount of “touch” or processing performed on the packets in the system, more processors can be added to carry the increased load. The router architecture is also able to distribute the high interface rate of an uplink connection in the same manner. Packets are allocated to processors in a manner that allows the original order of data packets within the same flow to be maintained. The system uses a hash function to distribute the flows, making sure that packets within the same flow are sent to the same processor so that the original packet order in each flow is maintained. Different flows may be sent to different processors.

Claims

1. A routing system for distributing packets in a network, wherein the packets originate at a source and are returned to a destination, both source and destination external with respect to the routing system, comprising:

a plurality of network interfaces that transfer packets to a destination and from a source;

a plurality of route processing engines;

a hash mechanism that performs a hashing function on at least a portion of net-work layer information packet, in the packets transferred to the routing system, to determine a distribution of the packets to the route processing engines for processing by the engines;

a processing mechanism that determines packets belonging to a same flow and their original order from the network layer information of the packets, the network layer information including at least the same source/destination and protocol; and

a data transferer that sends each ordered packet flow to a single route processing engine, thereby preserving the original ordered packet flows.

2. A router, comprising:

a plurality of processing engines for processing packets;

an interface for receiving a received packet from a network;

a data compiler to perform a hash function on said received packet to generate a hash result, and to select a selected processing engine from said plurality of processing engines in response to said hash result; and

,

a switch to distribute said packet to said selected processing engine; and

said data compiler determines an IP source address having source bytes and an IP destination address having destination bytes and a protocol byte, and performs said hash function by performing an exclusive OR (XOR) to said source byter and said destination byter and protocol byter to generate said hash result as at least one output byte, said at least one output byte to designate a flow to which said received packet belongs, and routing all packets having the same flow to a selected processing engine.

9. The router as in claim 2, or claim 3, further comprising:

said data compiler selection of said processing engine is partly table driven.

10. The router as in claim 2, or claim 3, further comprising:

said data compiler distributes the packets among said plurality of processing engines.

11. The router as in claim 2, or claim 3, or claim 4, further comprising:

said hash function uses a destination address information.

12. The router as in claim 2, or claim 3, or claim 4, further comprising:

said hash function uses a protocol information.

13. The router as in claim 2, or claim 3, or claim 4, further comprising:

said hash function uses a source port information.

14. The router as in claim 2, or claim 3, further comprising:

said data compiler puts packets received from said network into packet digest from before transferring them to said switch.

15. The router as in claim 2, or claim 3, further comprising:

said switch receiving said packet after said processing engine finishes processing said packet, and then

said switch routing said packet to an interface to transmit said packet out to said network.

16. The router as in claim 2, or claim 3, further comprising:

said processing engine performs routing of said packet.

17. The router as in claim 2, or claim 3, further comprising:

said processing engine performs filtering on said packet.

18. The router as in claim 2, or claim 3, further comprising:

said data compiler allocating said processing of packets to remaining processing engines in the event that a processor fails.

19. The router as in claim 2, or claim 3, further comprising:

said processing engine performs encryption on said packet.

20. The router as in claim 2, or claim 3, further comprising:

said processing engine performs decryption on said packet.

21. The router as in claim 2, or claim 3, or claim 4, further comprising:

said switch is a crossbar switch.

3. A router, comprising:

a plurality of processing engines located within said router for processing packets;

an interface for receiving a received packet from a network;

a data compiler to perform a hash function on a destination address of said received packet to generate a hash result, and to select a selected processing engine from said plurality of processing engines located within said router in response to said hash result;

a switch to distribute said packet to said selected processing engine; and

each processing engine of said plurality of processing engines having a plurality of queues, said packed has classification information in a header, and said processing engine selects a queue of said plurality of queues in response to said classification information.

22. The router as in claim 3, further comprising:

said classification information indicates a priority of said packet.

4. A router, comprising:

a plurality of processing engines for processing packets;

an interface for receiving a received packet from a network;

a data compiler to perform a hash function on said received packet to generate a hash result, and to select a selected processing engine from said plurality of processing engines in response to said hash result;

a switch to distribute said packet to said selected processing engine;

said data compiler detecting that a particular packet requires specialized processing; and

said switch distributing said particular packet to specialized processing engine to perform said specialized processing.

23. The router as in claim 4, further comprising:

said specialized processing is compression.

24. The router as in claim 4, further comprising:

said specialized processing is decompression.

25. The router as in claim 4, further comprising:

said specialized processing is routing.

26. The router as in claim 4, further comprising:

said specialized processing is routing.

5. A method of processing packet in a router, comprising:

receiving a packet from a network;

performing a hash function calculation on said packet to produce a hash result;

switching, in response to said hash result, said packet to a processing engine of a plurality of processing engines in said router, for further processing of said packet; and

performing an exclusive OR (XOR) in response to a source address and a destination address and a protocol byte to generate said hash result as a least one output byte, said at least one output byte to designate a flow to which said received packet belongs, and routing all packets having the same flow to a selected processing engine.

27. The method as in claim 5, or claim 6, further comprising:

selecting a processing engine by using said hash result and a table.

28. The method as in claim 5, or claim 6, further comprising:

distributing the packet among said plurality of processing engines.

29. The method as in claim 5, or claim 6, or claim 7, or claim 8, further comprising:

using a source address information in said hash function calculation.

30. The method as in claim 5, or claim 6, or claim 7, or claim 8, further comprising:

using a destination address information in said hash function calculation.

31. The method as in claim 5, or claim 6, or claim 7, or claim 8, further comprising:

using a protocol information in said hash function calculation.

32. The method as in claim 5, or claim 6, or claim 7, or claim 8, further comprising:

using a source port information in said hash function calculation.

6. A method of processing packet in a router, comprising:

receiving a packet from a network;

performing a hash function calculation on a destination address of said packet to produce a hash result;

switching, in response to said hash result, said packet to a processing engine of a plurality of processing engines in said router, for further processing of said packet; and

allocating said packets to remaining processing engines in the event that a processing engine fails.

7. A method of processing packet in a router, comprising:

receiving a packet from a network;

performing a hash function calculation on said packet to produce a hash result;

switching, in response to said hash result, said packet to a processing engine of a plurality of processing engines in said router, for further processing of said packet;

detecting that a particular packet requires specialized processing; and

distributing said particular packet to a specialized processing engine to perform said specialized processing.

33. The method as in claim 7, further comprising:

processing decompression as said specialized processing.

34. The method as in claim 7, further comprising:

processing decompression as said specialized processing.

35. The method as in claim 7, further comprising:

processing encryption as said specialized processing.

36. The method as in claim 7, further comprising:

processing routing as said specialized processing.

8. A router, comprising:

a plurality of processing engines located within said router for processing packets;

an interface for receiving a packet from a network, said packet referred to as a received packet;

a hashing function to perform a hash calculation on a destination address of said packet, said hash calculation producing a hash result;

a data compiler to determine a type of service required by said received packet; and

;

a switch, responsive to said type of service and responsive to said hash result, to distribute said packet to a selected processing engine of said plurality of processing engines located within said router, said selected processing engine providing said type of service.

37. The router as in claim 8, further comprising:

said type of service is comprising.

38. The router as in claim 8, further comprising:

said type of service is decompression.

39. The router as in claim 8, further comprising:

said type of service is encryption.

40. The router as in claim 8, further comprising:

said type of service is routing.

41. A router for distributing packets in a network, the packets originate at a source and are routed to a destination, comprising:

a plurality of route processing engines located within said router;

a mechanism that performs a hashing function on at least a portion of network layer information in said packets, said information indicating said destination, said hashing function producing an indica of a flow;

a classification engine to switch packets with a same indica of a flow to a single route processing engine of said plurality of route processing engines; and

said packets are a plurality of packets, individual packets of said plurality of packets arrive in substantially random order to produce different values of said information in random order, and said classification engine carries out a hashing function to produce said indica of flow, and different values of said indica of flow are in substantially random order in response to said plurality of packets arriving in random order, and a particular flow always produces a same indica of flow, and said particular flow is assigned to a particular route processing engine in the order that a first packet of said particular flow first arrives at said router.

42. The router of claim 41, further comprising:

said random order of arrival of said first packet of said particular flow leads to a distribution of packets being assigned to said route processing engine.

43. The route of claim 41, further comprising:

said information indicating said destination includes a destination address of said destination.

44. A method of operating a router, comprising:

receiving a packet by said router, said packet addressed to a destination, said router having a plurality of route processing engines;

hashing a portion of a network layer information of said packet, said information indicating said destination, to determine an indication of a flow;

selecting, in response to said indication of a flow, one processing engine of said plurality of processing engines to process the flow indicated;

said receiving step receives a plurality of packets, individual packets of said plurality of packets arrive in substantially random order to produce different values of said information in random order;

said hashing step produces different values of said indication of a flow in substantially random order in response to said plurality of packets arriving in random order;

producing by a particular flow a same indica of flow; and

assigning said particular flow to a particular route processing engine in the order that a first packet of said particular flow first arrives at said router.

45. The method of claim 44, further comprising:

assigning, in response to said random order of arrival of said first packet of said particular flow, a distribution of packets to said route processing engines.

46. The method of claim 44, further comprising:

including in said information a destination address of said destination.

47. A router, comprising:

a port adapter to receive a packet by said router, said packet addressed to a destination, said router having a plurality of route processing engines;

means for hashing a portion of a network layer information of said packet, said information indicating said destination, to determine an indication of a flow;

means for selecting, in response to said indication of a flow, one processing engine of said plurality of processing engines to process the flow indicated;

means for receiving a plurality of packets, individual packets of said plurality of packets arrive in substantially random order to produce different values of said information in random order;

means for producing different values of said indication of a flow in substantially random order in response to said plurality of packets arriving in random order;

means for producing by a particular flow a same indica of flow; and

means for assigning said particular flow to a particular route processing engine in the order that a first packet of said particular flow first arrives at said router.

48. The router of claim 47, further comprising:

means for assigning, in response to said random order of arrival of said first packet of said particular flow, a distribution of packets to said route processing engines.

49. The router of claim 47, further comprising:

said information includes a destination address of said destination.

50. A computer readable media, comprising:

said computer readable media having instructions written thereon for execution on a processor for the practice of the method of,

receiving a packet by said router, said packet addressed to a destination, said router having a plurality of route processing engines;

hashing a portion of a network layer information of said packet, said information indicating said destination, to determine an indication of a flow;

selecting, in response to said indication of a flow, one processing engine of said plurality of processing engine to process the flow indicated;

said receiving step receives a plurality of packets, individual packets of said plurality of packets arrive in substantially random order to produce different values of said information in random order;

said hashing step produces different values of said indication of a flow in substantially random order in response to said plurality of packets arriving in random order;

producing by a particular flow a same indica of flow; and

assigning said particular flow to a particular route processing engine in the order that a first packet of said particular flow first arrives at said router.