Packet forwarding apparatus with a flow detection table

• US 6,768,738 B1
• Filed: 09/10/1999
• Issued: 07/27/2004
• Est. Priority Date: 10/05/1998
• Status: Expired due to Term

• Current Assignee: Alaxala Networks Corporation (Fortinet Inc.)
• Original Assignee: Hitachi Information Technology Co. Ltd. (Hitachi, Ltd.), Hitachi, Ltd.
• Inventors: Matsuyama, Nobuhito, Aimoto, Takeshi, Yazaki, Takeki, Sugai, Kazuo
• Primary Examiner(s): Duong, Frank
• Assistant Examiner(s): Jagannathan, Melanie
• Application Number:
  US09/393,326
• Time in Patent Office: 1,782 Days
• Field of Search: 370/230.1, 370/230, 370/233, 370/400, 370/395.42, 370/392, 370/389, 370/401, 370/420, 370/421, 370/395.21, 370/231, 370/235, 455/445
• US Class Current: 370/392
• CPC Class Codes: H04L 12/46 Interconnection of networks
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions
• 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/54 Organization of routing tables
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9036 Common buffer combined with individual queues
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04L 69/12 Protocol engines
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A packet forwarding apparatus provided with a plurality of line interface units, comprises a routing processing unit for referring to a routing table, based on header information of received packet to specify one of output lines to output the received packet, a flow detection unit for referring to an entry table, in which a plurality of entries with flow conditions and control information are registered, to retrieve control information defined by the entry with a flow condition which coincides with that of the header information of the received packet, and a packet forwarding unit for transferring the received packet to one of the line interface units connected to the output line specified by the routing processing unit. The entry table id divided into a plurality of subtables corresponding to the values of flow attributes associated with the received packets and the flow detection unit retrieves the control information from one of said subtables specified by the value of the flow attribute corresponding to the received packet.

Claims

1. A packet forwarding apparatus provided with a plurality of line interface units each connected to an input line and an output line, comprising:

a routing processing unit for referring to a routing table, based on header information of each of packets received from the input lines by said line interface units, and specifying one of said output lines from which the packet should be output;

an entry table for storing therein a plurality of entries each including parameter values for defining a flow condition and packet control information,

a flow detection unit for retrieving, by referring to the entry table, packet transfer control information defined by one of said entries of which the flow condition is satisfied with parameter values extracted from the header information of the received packet; and

a packet forwarding unit for transferring said received packet to one of said line interface units connected to the output line specified by said routing processing unit; and

wherein said entry table is divided into a plurality of subtables corresponding to the values of a specific flow attribute to be associated with each of the received packets,

said flow detection unit specifies one of said subtables for each of said received packets in accordance with the value of the specific flow attribute associated with the packet, and retrieves the packet control information from among entries in the specified subtable, and

said packet forwarding unit controls the transfer of each of said received packets to one of said line interface units in accordance with the packet control information notified from said flow detection unit.

2. The packet forwarding apparatus according to claim 1, wherein said entry table comprises a common table for storing said plurality of entries therein and a list table for storing therein pointer addresses for accessing the entries lying within said common table, said list table being divided into a plurality of sub-list tables corresponding to the values of the specific flow attribute, and

said flow detection unit refers to one of said sub-list tables specified by the value of the specific flow attribute associated with each of said received packets to retrieve the entry having a flow condition satisfied with the header information of said received packet, based on pointer addresses stored in the specified sub-list table.

3. The packet forwarding apparatus according to claim 1, wherein said specific flow attribute is a line number indicative of the input line of said received packet.

4. The packet forwarding apparatus according to claim 1, wherein said specific flow attribute is a line number indicative of the output line to output said received packet.

5. The packet forwarding apparatus according to claim 1, wherein said specific flow attribute is a MAC identifier produced from a source MAC address included in the header information of said received packet.

6. The packet forwarding apparatus according to claim 1, wherein said specific flow attribute is a MAC identifier produced from a destination MAC address included in the header information of said received packet.

7. The packet forwarding apparatus according to claim 1, wherein said specific flow attribute is a source subnet identifier for identifying a subnet to which a source IP address included in the header information of said received packet belongs.

8. The packet forwarding apparatus according to claim 1, wherein said specific flow attribute is a destination subnet identifier for identifying a subnet to which a destination IP address included in the header information of said received packet belongs.

9. The packet forwarding apparatus according to claim 1, wherein each of said entries stored in the entry table defines said flow condition with at least one type of information value selected from among a line number indicative of the input line of said received packet, a line number indicative of the output line for said received packet, and address information, application identification information and identification information on service priority to be included in the header of each of said received packets.

10. The packet forwarding apparatus according to claim 1, wherein each of said entries stored in the entry table includes, as said packet control information, at least one type of information selected from priority information indicative of priority for the transmission of said received packet to said output line and forwarding control information indicative of whether the transfer of said received packet to one of said output lines is required, and

said packet forwarding unit performs at least one of filtering control of said received packet and priority control for the transfer of said received packet to one of said output lines in accordance with the packet control information notified from said flow detection unit.

11. The packet forwarding apparatus according to claim 1, wherein each of said entries stored in the entry table includes, as the packet control information, priority information indicative of priority for the transmission of said received packet to said output line, and forwarding control information indicative of whether the transfer of said received packet to one of output lines is required, and

said packet forwarding unit performs both filtering for said received packet and priority control for the transfer of said received packet to the output line in accordance with the priority information and forwarding control information notified from said flow detection unit as the packet control information.

12. The packet forwarding apparatus according to claim 1, wherein each of said entries stored in the entry table includes, as the packet control information, priority information indicative of priority for the transmission of said received packet to said output line, and TOS (Type of Service) information, and

said packet forwarding unit rewrites TOS information included in the header information of each of said received packets in accordance with the TOS information notified from said flow detection unit as the packet control information and thereafter performs priority control for the transfer of said received packet to the output line in accordance with the priority information notified from said flow detection unit as o the packet control information.

13. The packet forwarding apparatus according to claim 2, wherein said list table comprises a first list table for use in filtering of said received packets and a second list table for use in forwarding control of said received packets, and both of said first and second list tables are divided into a plurality of subtables corresponding to the values of said specific flow attribute, respectively, and

said flow detection unit selectively refers to said first and second list tables for each of said received packets to retrieve filtering control information and forwarding control information related to each of said received packets.

14. The packet forwarding apparatus according to claim 2, wherein a memory region for forming said common table and said flow detection unit are integrated onto the same semiconductor substrate.

15. The packet forwarding apparatus according to claim 2, wherein the memory region for forming said common table, said flow detection unit, and said routing processing unit are integrated onto the same semiconductor substrate.

16. The packet forwarding apparatus according to claim 1, wherein each of said entries stored in the entry table includes priority information and connection identification information as said packet control information,

said packet forwarding unit adds the connection identification information notified form said flow detection unit as the packet control information to said received packet, and thereafter performs priority control for the transfer of the received packet to the output line in accordance with the priority information notified from said flow detection unit as the packet control information, and

each of said line interface units outputs the packet received from said packet forwarding unit to one of connections, corresponding to the connection identification information, formed over the output line connected thereto.