US6853638B2 — Route/service processor scalability via flow-base…

Claim 1

Independent Claim 156 words

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.

Claim 2

Dependent Claim 156 words

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.

Claim 3

Dependent Claim 155 words

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.

Claim 4

Dependent Claim 155 words

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.

Claim 5

Dependent Claim 121 words

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.

Claim 6

Dependent Claim 121 words

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.

Claim 7

Dependent Claim 95 words

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.

Claim 8

Dependent Claim 95 words

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.

Claim 9

Independent Claim 116 words

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.

Claim 10

Independent Claim 116 words

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.

Claim 11

Independent Claim 76 words

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.

Claim 12

Independent Claim 76 words

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.

Claim 13

Independent Claim 79 words

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.

Claim 14

Independent Claim 79 words

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.

Claim 15

Dependent Claim 111 words

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.

Claim 16

Dependent Claim 111 words

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.

Claim 17

Dependent Claim 25 words

The router as in claim 2 , or claim 3 , further comprising: said data compiler selection of said processing engine is partly table driven.

Claim 18

Dependent Claim 25 words

The router as in claim 2 , or claim 3 , further comprising: said data compiler distributes the packets among said plurality of processing engines.

Claim 19

Dependent Claim 25 words

The router as in claim 2 , or claim 3 , or claim 4 , further comprising: said hash function uses a destination address information.

Claim 20

Dependent Claim 24 words

The router as in claim 2 , or claim 3 , or claim 4 , further comprising: said hash function uses a protocol information.

Claim 21

Dependent Claim 25 words

The router as in claim 2 , or claim 3 , or claim 4 , further comprising: said hash function uses a source port information.

Claim 22

Dependent Claim 32 words

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.

Claim 23

Dependent Claim 44 words

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.

Claim 24

Dependent Claim 21 words

The router as in claim 2 , or claim 3 , further comprising: said processing engine performs routing of said packet.

Claim 25

Dependent Claim 21 words

The router as in claim 2 , or claim 3 , further comprising: said processing engine performs filtering on said packet.

Claim 26

Dependent Claim 32 words

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.

Claim 27

Dependent Claim 21 words

The router as in claim 2 , or claim 3 , further comprising: said processing engine performs encryption on said packet.

Claim 28

Dependent Claim 21 words

The router as in claim 2 , or claim 3 , further comprising: said processing engine performs decryption on said packet.

Claim 29

Dependent Claim 23 words

The router as in claim 2 , or claim 3 , or claim 4 , further comprising: said switch is a crossbar switch.

Claim 30

Dependent Claim 18 words

The router as in claim 3 , further comprising: said classification information indicates a priority of said packet.

Claim 31

Dependent Claim 14 words

The router as in claim 4 , further comprising: said specialized processing is compression.

Claim 32

Dependent Claim 14 words

The router as in claim 4 , further comprising: said specialized processing is decompression.

Claim 33

Dependent Claim 14 words

The router as in claim 4 , further comprising: said specialized processing is routing.

Claim 34

Dependent Claim 14 words

The router as in claim 4 , further comprising: said specialized processing is routing.

Claim 35

Dependent Claim 25 words

The method as in claim 5 , or claim 6 , further comprising: selecting a processing engine by using said hash result and a table.

Claim 36

Dependent Claim 22 words

The method as in claim 5 , or claim 6 , further comprising: distributing the packet among said plurality of processing engines.

Claim 37

Dependent Claim 31 words

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.

Claim 38

Dependent Claim 31 words

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.

Claim 39

Dependent Claim 30 words

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.

Claim 40

Dependent Claim 31 words

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.

Claim 41

Dependent Claim 15 words

The method as in claim 7 , further comprising: processing decompression as said specialized processing.

Claim 42

Dependent Claim 15 words

The method as in claim 7 , further comprising: processing decompression as said specialized processing.

Claim 43

Dependent Claim 15 words

The method as in claim 7 , further comprising: processing encryption as said specialized processing.

Claim 44

Dependent Claim 15 words

The method as in claim 7 , further comprising: processing routing as said specialized processing.

Claim 45

Dependent Claim 15 words

The router as in claim 8 , further comprising: said type of service is comprising.

Claim 46

Dependent Claim 15 words

The router as in claim 8 , further comprising: said type of service is decompression.

Claim 47

Dependent Claim 15 words

The router as in claim 8 , further comprising: said type of service is encryption.

Claim 48

Dependent Claim 15 words

The router as in claim 8 , further comprising: said type of service is routing.

Claim 49

Dependent Claim 198 words

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.

Claim 50

Dependent Claim 198 words

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.

Claim 51

Dependent Claim 34 words

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.

Claim 52

Dependent Claim 20 words

The route of claim 41 , further comprising: said information indicating said destination includes a destination address of said destination.

Claim 53

Independent Claim 168 words

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.

Claim 54

Independent Claim 168 words

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.

Claim 55

Dependent Claim 34 words

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.

Claim 56

Dependent Claim 18 words

The method of claim 44 , further comprising: including in said information a destination address of said destination.

Claim 57

Dependent Claim 174 words

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.

Claim 58

Dependent Claim 174 words

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.

Claim 59

Dependent Claim 36 words

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.

Claim 60

Dependent Claim 17 words

The router of claim 47 , further comprising: said information includes a destination address of said destination.

Claim 61

Dependent Claim 186 words

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.

Claim 62

Dependent Claim 186 words

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.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2008-02-08	2008-08-09	2009-02-08	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2012-02-08	2012-08-09	2013-02-08	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2016-02-08	2016-08-09	2017-02-08	$7700.00	Window Closed / Lapsed

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

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag