Device for flow classifying and packet forwarding device with flow classify function

• US 7,286,535 B2
• Filed: 08/12/2002
• Issued: 10/23/2007
• Est. Priority Date: 04/08/2002
• Status: Active Grant

• Current Assignee: Alaxala Networks Corporation (Fortinet Inc.)
• Original Assignee: Hitachi, Ltd.
• Inventors: Yazaki, Takeki, Ishikawa, Yuichi
• Primary Examiner(s): NGUYEN, HANH N
• Application Number:
  US10/215,846
• Publication Number:
  US 20030189932A1
• Time in Patent Office: 1,898 Days
• Field of Search: 370/400, 370/389, 370/392, 370/390, 370/428, 370/429, 370/395.31, 370/351, 370/412, 370/410, 370/419
• US Class Current: 370/392
• 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]
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A flow classifier having a flow CAM having plural flow entries, a search key generator for generating a search key of a format which differs by a flow condition, and a table holding a flow search result corresponding to an address of respective flow entry of CAM, in which access is made to CAM by the search key of a variable format including at least one header information item extracted from a packet header and the flow search result is obtained from the table in accordance with the address of the flow entry coinciding with the search key outputted from CAM to thereby constitute high speed formation of flow classifying by a variety of flow conditions.

Claims

1. A packet forwarding device connected to a plurality of input and output ports for forwarding a packet received from one of the input ports to one of the output ports specified by header information of the packet, the packet forwarding device comprising:

a flow classifier for classifying the packet into one of packet flows to which the packet belongs, according to the header information of the packet; and

means for executing on the packet a forward control previously designated for said one packet flow;

wherein the flow classifier includes;

a flow Content Addressable Memory (CAM) having a plurality of flow entries;

a search key generator for generating a search key having a variable format which differs depending on a combination of information items to constitute a flow condition; and

a table for specifying the forward control to be executed on the packet in response to an address of a flow entry outputted from said flow CAM,

wherein said flow CAM includes a plurality of table regions corresponding to the format of the search key, each of said table regions includes a plurality of flow entries each including a plurality of information fields for indicating values of information items to constitute the flow condition and excluding information fields containing information which is not necessary for a respective input logical link,

wherein all of the flow entries in said flow CAM are compared with the search key to output an address of one of the flow entries matched with the search key, and the search key includes at least one header information item extracted from the header of the packet.

2. The packet forwarding device according to claim 1, wherein said search key generator is provided with a search key definition table designating header information items to constitute a flow condition in association with an identifier of said one input port, refers to the search key definition table based on the identifier of the input port which receives said packet, and generates the search key including the header information items designated by the table.

3. The packet forwarding device according to claim 1,

wherein said search key generator is provided with a flow mode table indicating a correspondence between the identifier of said one input port and a flow mode, and a search key definition table designating header information items to constitute a flow condition in association with a flow mode indicated by the flow mode table;

and

wherein the search key generator specifies the flow mode of the packet by referring to the flow mode table and generates the search key based on a flow condition read out from the search key definition table in accordance with the specified flow mode.

4. The packet forwarding device according to claim 1,

wherein the search key generator includes:

a mode condition table indicating a correspondence between an identifier of said one input port and a mode condition;

a detection mode table indicating a correspondence among the identifier of said input port, a mode condition and a flow mode; and

a search key definition table designating header information items to constitute a flow condition in association with a flow mode indicated by the flow mode table, and

wherein the search key generator specifies the flow mode of the packet from the flow mode table in accordance with the identifier of the input port which receives said packet and the mode condition designated by the mode condition table, and generates the search key based on a flow condition read out from the search key definition table in accordance with the specified flow mode.

5. The packet forwarding device according to claim 1, wherein the header information of the packet includes internal header information generated by an input port interface associated with the input port, and the internal header information including an input port identifier and an output port identifier.

6. The packet forwarding device according to claim 1, wherein at least one of information fields of each flow entry in one of said table regions indicating a header information item which is different in kind from a header information item of a corresponding information field of flow entries in another one of the table regions.

7. A packet forwarding device connected to a plurality of input and output ports for forwarding a packet received from each of the input ports to one of the output ports specified by header information of the packet, said packet forwarding device comprising:

a controller for classifying the packet into one of packet flows to which the packet belongs, according to the header information of the packet and determining forward control to be executed on the packet; and

means for executing the forward control determined by the controller on the packet;

wherein the controller includes a flow classifier comprising;

a flow Content Addressable Memory (CAM) having a plurality of flow entries;

a search key generator for generating a search key having a variable format which differs depending on a combination of information items to constitute a flow condition; and

a table for specifying the forward control to be executed on the packet in response to an address of a flow entry outputted from said flow CAM,

wherein said flow CAM includes a plurality of table regions corresponding to the format of the search key, each of said table regions includes a plurality of flow entries each including a plurality of information fields for indicating values of information items to constitute the flow condition and excluding information fields containing information which is not necessary for a respective input logical link,

wherein all of the flow entries in said flow CAM are compared with the search key to output an address of one of the flow entries matched with the search key, and the search key includes at least one header information item extracted from the header of the packet.

8. The packet forwarding device according to claim 7, wherein said controller includes a table controller for reading out information specifying the forward control to be executed on the packet therefrom in response to the address of the flow entry outputted from said flow CAM.

9. The packet forwarding device according to claim 7, wherein at least one of information fields of each flow entry in one of said table regions indicating a header information item which is different in kind from a header information item of a corresponding information field of flow entries in another one of the table regions.

10. A device for flow controlling comprising:

a flow Content Addressable Memory (CAM) having a plurality of flow entries;

a search key generator for generating a search key having a variable format which differs depending on a combination of information items to be a flow condition; and

a table for specifying a flow search result corresponding to an address of a flow definition entry of the flow CAM, said flow search result designating flow control to be executed on a packet,

wherein said flow CAM includes a plurality of table regions corresponding to the format of the search key, each of said table regions includes a plurality of flow entries each including a plurality of information fields for indicating values of information items to constitute the flow condition and excluding information fields containing information which is not necessary for a respective input logical link,

wherein all of the flow entries in said flow CAM are compared with the search key to output an address of one of the flow entries matched with the search key, and the search key includes at least one header information item extracted from the header of the packet, and

wherein the flow search result is read out from the table in accordance with the address of the flow entry outputted from the CAM.

11. The device according to claim 10, wherein at least one of information fields of each flow entry in one of said table regions indicating a header information item which is different in kind from a header information item of a corresponding information field of flow entries in another one of the table regions.