Packet forwarding device with packet filter

To provide a packet forwarding device which minimizes degradation in packet forwarding performance at the time of execution of filtering there is provided a technique in which a destination decision processing unit of a destination decision and filtering unit decides whether to execute filtering on the basis of at least one of an input interface, an input port number, an output interface, and an output port number of an input packet and a plurality of pieces of information constituting the header of the packet. A filtering unit executes filtering only for a packet for which execution of filtering is decided. The packet forwarding device with the destination decision and filtering unit need not execute filtering for all packets and can minimize degradation in packet forwarding performance caused by filtering.

INCORPORATION BY REFERENCE

The present application claims priority from Japanese application JP2005-245236 filed on Aug. 26, 2005, the content of which is hereby incorporated by reference into this application.

BACKGROUND OF THE INVENTION

The technical field of the present invention relates to a packet forwarding device with high-speed filtering means.

Distributed Denial of Service (DDOS) attacks which transmit invalid packets to cause waste of the bandwidth resources of a network and overloading of a public server are becoming a serious problem. Since an attacker often transmits a packet whose source address is spoofed to prevent traceback to the source, detection and discarding of such a spoofed packet by a packet forwarding device is effective in preventing a Distributed Denial of Service attack.

As a technique for detecting and discarding a spoofed packet, there is available filtering in a packet forwarding device. As an example of filtering, there is known filtering in loose mode described in IETF RFC 2827: “Network Ingress Filtering: Defeating Denial of Service Attacks which employ IP Source Address Spoofing.” IETF RFC 2827 describes that packets passing through a packet forwarding device are limited to ones with a known advertised prefix. A prefix here refers to the high-order bits of an address and is information indicating a network.

Other examples of filtering include filtering in strict mode described in IETF RFC 1812: “Requirements for IP Version 4 Routers.” The document describes that if an interface of a packet forwarding device from which a packet is input (to be referred to as an input interface) is different from an interface to which data is to be output in order for the data to reach the source address of the packet, the packet needs to be discarded.

In many cases, a spoofed packet contains an unknown unadvertised prefix or an interface to which data is to be output in order for the data to reach the source address is different from the input interface. Accordingly, execution of filtering described above by a packet forwarding device makes it possible to greatly reduce the number of spoofed packets.

SUMMARY OF THE INVENTION

Filtering processing in loose mode can be implemented by extending destination decision means for deciding an interface to which a packet is to be output. Destination decision means stores an advertised prefix and an interface corresponding to the prefix. When a packet is input, the destination decision means searches for a prefix matching the destination IP address in the header of the packet and decides that an interface corresponding to the matching prefix is an interface to which the packet is to be transmitted. To implement filtering in loose mode, it suffices that the destination decision means is so extended as to compare prefixes with not the destination address but the source address of a packet to retrieve a matching one and discard the packet if there is no matching one.

Filtering in strict mode is also implemented by extending destination decision means. To implement this filtering, it suffices that destination decision means is so extended as to decide an interface corresponding to a prefix matching the source address of a packet and discard the packet if the interface is different from the input interface.

As described above, a packet forwarding device with filtering to which the techniques of IETF RFC 2827 and IETF RFC 1812 are applied needs not only to compare prefixes with a destination IP address to retrieve a matching one but also to compare prefixes with a source IP address for filtering. Since two types of prefix/IP address comparisons need to be made, the extended destination decision means of the packet forwarding device can process only half as many packets as those processed without filtering. For this reason, execution of filtering makes the packet forwarding performance of a router with the means lower than that without filtering.

Under the circumstances, there has been considered a packet forwarding device which minimizes degradation in packet forwarding performance and performs processing at higher speed than a router to which the techniques of IETF RFC 2827 and IETF RFC 1812 are applied.

As at least one means for solving the above-described problem, there is provided a packet forwarding device which comprises a plurality of input ports and a plurality of output ports and a destination decision and filtering unit that manages address conditions indicating network address conditions and interfaces corresponding to the address conditions and executes a destination decision process of deciding that an interface corresponding to a first address condition matching a destination address in an input packet is an output interface and a filtering process of deciding that the packet is intended for “forwarding” if a second address condition matching a source address of the packet exists and executes the filtering process only for some of input packets.

Other problems, means, and effects will become apparent from an embodiment to be described later.

According to the solving means, filtering only for some of input packets minimizes degradation in performance at the time of execution of filtering and implements an improvement in performance.

DESCRIPTION OF THE EMBODIMENTS

An embodiment suitable for implementing the present invention will be explained below with reference toFIGS. 1 to 16. Note that the present invention is not limited to this embodiment.

(1) Overview of Network and Router

An example of a network to be considered in this embodiment will be explained with reference toFIG. 1. InFIG. 1, networks of ISPs ISP-A and ISP-B are connected through an IX. Note that ISP is an abbreviation for Internet Service Provider. The network of the ISP ISP-A is divided into six networks N1to N6using four routers R0to R3while the network of the ISP ISP-B is divided into a plurality of networks including a network N7. The IP addresses of the networks N1to N7are 12.13.0.0/16, 13.14.0.0/16, 14.15.0.0/16, 15.16.17.0/24, 16.17.0.0/16, 18.19.20.0/24, and 19.20.0.0/16, respectively. Characters (including numeric characters) before “/” of each address represent an IP address, and numeric characters after “/” represent the bit length (prefix length) of the IP address. For example, the prefix of the IP address of 12.13.0.0/16 is “12.13.” Note that although the network of the ISP ISP-B has one or more networks in addition to the network N7, the networks are omitted for the sake of illustrative simplicity.

A port of the router R1leading to the network N1, a port of the router R2leading to the network N2, a port of the router R3leading to the network N2, and a port of a router R4leading to the IX are assigned, as IP addresses, 12.13.1.1, 13.14.1.1, 13.14.1.2, and 11.12.1.1, respectively. The networks N3to N7accommodate respective terminals T1to T5. The router R0executes filtering for a packet originating from any of the terminals T1to T4and destined for the network of the ISP ISP-B. The router R0has a plurality of ports and manages networks (the networks N1and N2and the IX) directly connected to the ports, whose port numbers are1,2, and3, respectively, using the numbers of interfaces (to be referred to as interface numbers),1,2, and3. The router R0discards a packet input from the network N1if the packet contains a source IP address which does not belong to any of the networks N1, N3, and N4and discards a packet input from the network N2if the packet contains a source IP address which does not belong to any of the networks N2, N5, and N6.

The overview of the configuration and operation of a router200used as the router R0will be explained next with reference toFIGS. 2,3,4, and5.

FIG. 2shows a block diagram of the router200. The router200is composed of N interface units210, any of which is denoted by210-i(i=1 to N), 2N input ports201, any of which is denoted by201-ij(i=1 to N, j=1 or 2) accommodated by a corresponding one of the interface units210, 2N output ports202, any of which is denoted by202-ij, one packet forwarding unit250which couples the interface units210together, and one processor280. Each interface unit210-iis composed of a packet transmitting/receiving circuit230which executes the process of transmitting and receiving packets, a destination decision and filtering unit100characteristic of this embodiment, and an ARP table search unit220. In the following description, the input ports201and output ports202and lines connecting the packet transmitting/receiving circuits230and the packet forwarding unit250will be distinguished from each other by generically referring to the former ones as extra-device ports and the latter ones as intra-device lines. Units include hardware (a semiconductor circuit or the like) which executes a program.

FIG. 3shows an example of the format of a packet input from each of the input ports201or output to each of the output ports202inFIG. 2. The format is composed of a header unit310and a data unit320. The data unit320is composed of user data321. The header unit310is composed of a Source MAC Address311(to be referred to as a SMAC hereinafter) which is a source address at the data link layer, a Destination MAC Address312(to be referred to as a DMAC hereinafter) which is a destination address, a Source IP Address313(to be referred to as a SIP hereinafter) which is a source address (the address of a transmitting terminal) at the network layer, and a Destination IP Address314(to be referred to as a DIP hereinafter) which is a destination address (the address of a receiving terminal).

FIG. 4shows an example of the format of a packet used internally in the router200inFIG. 2. The format is obtained by adding an internal header unit330to the above-described format. The internal header unit330is composed of an input port number331which is the number of a port from which a packet is input, an output port number332which is the number of a port to which the packet is to be output, a Next Hop IP Address333(to be referred to as an NHIP hereinafter) which is the IP address of the next router or terminal that is to receive the packet, and an input IF334which is the number of an interface from which the packet is input (to be referred to as an input interface number). The output port number332, the Next Hop IP Address333, the number of an interface (not shown) to which the packet is to be output (output interface number), and the like are generically referred to as output destination information.

FIG. 5shows the details of the packet transmitting/receiving circuit230shown inFIG. 2. The packet transmitting/receiving circuit230will also be considered as a combination of a packet transmitting unit and a packet receiving unit. When the packet transmitting/receiving circuit230receives a packet in the format inFIG. 3from one of the input ports201, an internal header adding unit910adds the internal header unit330inFIG. 4, stores, in the field for the input port number331, the number of a port from which the packet is input, and writes the packet into a packet buffer920. An interface number decision unit940decides, from information contained in the stored packet, the number of an interface from which the packet is input (to be referred to as an input interface number) and writes the input interface number in the field for the input IF334of the internal header unit330. A packet header transmission unit950transmits information of the header unit310and internal header unit330of the packet in the packet buffer920to the destination decision and filtering unit100as packet header information21. Note that at this time, the output port number332and the NHIP333each have a nonsensical value. The input port number331, input IF334, and the like are generically referred to as input information or input source information for the packet receiving unit.

An interface here refers to a network directly connected to a router. The router200assigns networks respective unique interface numbers and manages them using the numbers. In this embodiment, the networks N1and N2and the IX are connected to input ports of the router200serving as the router R0, and interface numbers of1,2, and3are assigned to the networks, respectively. Since port numbers and interface numbers correspond one to one, each packet transmitting/receiving circuit230can decide an input interface number using a corresponding input port number. For example, if the router200serving as the router R0receives a packet originating from the terminal T1through the input port connected to the network N1, the packet transmitting/receiving circuit230can decide from the input port number of1that the input interface number is1. If the input port is an ATM port or Ethernet (registered trademark) port, and a network connected to the input port is divided into a plurality of networks with different VPI/VCI values or VLAN ID values, the interface number decision unit940only needs to decide the interface number on the basis of a VPI/VCI pair in an ATM header, a VLAN ID in an Ethernet header, or the like, in addition to the input port number.

The destination decision and filtering unit100inFIG. 2receives the packet header information21from the packet transmitting/receiving circuit230and executes filtering on the input side (to be referred to input-side filtering). The destination decision and filtering unit100manages prefixes and interfaces corresponding to the prefixes and executes destination decision processing and filtering. In the destination decision processing, the destination decision and filtering unit100compares the prefixes with the DIP314in the packet header information21to retrieve a matching one, decides the number of an interface to which the input packet is to be output (to be referred to as an output interface number), a next hop IP address, and an output port number, and transmits the pieces of information to the packet transmitting/receiving circuit230as packet output port information22. For example, if a packet originating from the terminal T1and destined for the network of the ISP ISP-B is received, the output interface number, the next hop IP address, and the output port number of the packet are3, 11.12.1.1, and3, respectively.

As will be explained in detail later, the destination decision and filtering unit100characteristically includes an execution decision unit115(FIG. 6) which stores whether to turn on or off filtering for each output interface. To execute filtering only for a packet destined for the IX, the execution decision unit of the router R0stores pieces of On/Off information of Off, Off, and On, respectively, for the output interfaces (interfaces Nos.1,2, and3) and decides “execution” of filtering only for a packet to be output to interface No.3as the output interface. Decision of turn-on or execution of filtering will also be referred to as decision of “Filtering,” and decision of turn-off or non-execution will also be referred to as decision of “No Filtering.”

In the filtering, the destination decision and filtering unit100first decides a second input interface number that is the number of an interface from which the packet with the SIP313should have been input. The destination decision and filtering unit100then compares the input interface number in the packet header information21with the second input interface number. If the numbers match each other, the destination decision and filtering unit100decides that the packet in the packet transmitting/receiving circuit230is intended for “forwarding.” Otherwise, it decides that the packet is intended for “discard.” The destination decision and filtering unit100transmits filtering information23indicating “forwarding” or “discard” to the packet transmitting/receiving circuit230. If filtering is not executed, the destination decision and filtering unit100transmits the filtering information23indicating “forwarding” to the packet transmitting/receiving circuit230.

For example, if the router R0receives a packet originating from the terminal T1and destined for the network of the ISP ISP-B, a corresponding one of the destination decision and filtering units100first decides that the output interface number of the packet is3and decides “execution” of filtering. If the source IP address of the packet having been transmitted by the terminal T1belongs to the network N3or N4, a second input interface number and an input interface number decided by the interface number decision unit940both become 1, and thus, the destination decision and filtering unit100decides that the packet is intended for “forwarding.” On the other hand, assume that the terminal T1is an attacker and that the source address of the packet to be transmitted belongs to any one other than the networks N1, N3, and N4. In this case, if the source address belong to, e.g., the network N2, the second input interface number becomes2, and the destination decision and filtering unit100decides that the packet is intended for “discard.” If the router R0receives a packet originating from the terminal T1to be forwarded to the terminal T4through the router R0, the destination decision and filtering unit100decides that the output interface number of the packet is2and decides “non-execution” of filtering.

A packet read unit960and a header write unit970of the packet transmitting/receiving circuit230inFIG. 5receive the filtering information23from the destination decision and filtering unit100. If the filtering information23indicates “forwarding,” the header write unit970writes the output port number and next hop IP address in the packet output port information22in the fields for the output port number332and NHIP333inFIG. 4, respectively. The packet read unit960reads out the stored packet from the packet buffer920and transmits it to the packet forwarding unit250. On the other hand, if the filtering information23indicates “discard,” the packet read unit960does not transmit the packet to the packet forwarding unit250. Accordingly, the stored packet is overwritten with a packet arriving next and finally discarded. Note that instructions for “discard” include not only positive ones to execute discarding but also negative ones to disallow forwarding.

Upon receipt of the packet from the packet transmitting/receiving circuit230, the packet forwarding unit250inFIG. 2transmits the packet to the packet transmitting/receiving circuit230of one of the interface units210corresponding to the output port number332contained in the packet. The packet transmitting/receiving circuit230having received the packet from the packet forwarding unit250stores the packet in the packet buffer930inFIG. 5. The packet header transmission unit950transmits information in the internal header unit330and header unit310of the packet stored in the packet buffer930to the destination decision and filtering unit100as the packet header information21.

Upon receipt of the packet header information21from the packet transmitting/receiving circuit230, the destination decision and filtering unit100inFIG. 2executes filtering on the output side (to be referred to as output-side filtering). The destination decision and filtering unit100has a piece of filtering On/Off information for each input interface used in output-side filtering in addition to pieces of filtering On/Off information for respective output interfaces used in input-side filtering. The destination decision and filtering unit100executes filtering on the basis of a piece of On/Off information corresponding to the input interface and transmits the filtering information23indicating “forwarding” or “discard” to the packet transmitting/receiving circuit230.

This example assumes that each execution decision unit115(FIG. 6) of the router R0stores pieces of On/Off information, all of which are Off, for the input interfaces (interfaces Nos.1,2, and3). Accordingly, filtering is not executed, and the destination decision and filtering unit100transmits the filtering information23indicating “forwarding” to the packet transmitting/receiving circuit230. By executing filtering for a packet only if a piece of On/Off information corresponding to the input interface number of the packet is On, as described above, the efforts in searching for a prefix matching the source IP address in the packet is minimized, and an increase in speed is implemented as compared with IETF RFC 2827. When filtering is to be executed only for a packet input from a specific input interface, a piece of On/Off information corresponding to the input interface is set to On. This case will be described later. If the filtering information23indicates “discard,” the packet read unit960of the packet transmitting/receiving circuit230inFIG. 5does not transmit the packet in the packet buffer930to the corresponding one of the output ports202, and thus, the packet is overwritten with the next one and discarded.

Upon receipt of the filtering information23indicating “forwarding” from the destination decision and filtering unit100, the packet transmitting/receiving circuit230inFIG. 5transmits the NHIP333of the internal header unit330inFIG. 4to the ARP table search unit220inFIG. 2as next hop IP address information24. The ARP table search unit220has a next hop MAC address corresponding to the next hop IP address information24. Upon receipt of the information24, the ARP table search unit220transmits the corresponding MAC address to the packet transmitting/receiving circuit230as next hop MAC address information25. As for the header unit310inFIG. 4, the packet transmitting/receiving circuit230writes the MAC address in the next hop MAC address information25in the field for the DMAC312and a MAC address assigned to the one of the output ports corresponding to the output port number332of the internal header unit330in the field for the SMAC311. The packet transmitting/receiving circuit230deletes the internal header unit330and transmits the stored packet to the one of the output ports202corresponding to the output port number332.

(2) Details of Destination Decision and Filtering Unit of Router

A detailed example of operation at the time of input-side filtering of the destination decision and filtering unit100shown inFIG. 2will be explained with reference to the block diagram inFIG. 6and the flowchart inFIG. 7.

As shown inFIG. 6, the destination decision and filtering unit100is composed of a destination decision processing unit120which executes destination decision processing, a filtering unit110which executes filtering, and a routing table search unit130which has a routing table500storing prefixes and interfaces corresponding to the prefixes and compares the prefixes with an input IP address to retrieve a matching one.

Upon receipt of the packet header information21, the destination decision and filtering unit100stores the SIP313, DIP314, and input interface information in a SIP store unit111, a DIP store unit121, and an input interface store unit114, respectively, and stores all pieces of information in the packet header information21in a header information store unit116(step701).

Next, a routing table search starting unit B denoted by reference numeral122instructs the routing table search unit130to make a search in the routing table and transmits the DIP314in the DIP store unit as search key information (step702).FIG. 8shows the details of the routing table search unit130; andFIG. 9, an example of the routing table500of the routing table search unit130. The routing table500stores N routing entries501, any of which is denoted by501-i(i=1 to N) and stores an IP address condition, an interface number corresponding to the IP address condition, a next hop IP address, and a port number, in descending order of the prefix length of the IP address conditions.

Upon receipt of an instruction to make a search in the routing table and the DIP314from the routing table search starting unit B (122), a routing table control unit510of the routing table search unit130sequentially reads out the routing entries501from the routing table500in order from one with the smallest address. The routing table control unit510compares the prefix of each read-out IP address condition with a part of the DIP314of length equal to the prefix length. The routing table control unit510transmits an interface number, next hop IP address, and port number corresponding to a matching IP address condition retrieved first to a destination decision unit123(step703). The destination decision unit123decides that the received pieces of information are the output interface number, next hop IP address, and output port number, respectively, of a packet in the packet transmitting/receiving circuit230and transmits them to the packet transmitting/receiving circuit230and a routing table search starting unit A denoted by reference numeral112as the packet output port information22(step704).

If a packet destined for the terminal T5connected to the network of the ISP ISP-B is received from any of the terminals T1to T4, the destination IP address of the packet matches only the IP address condition of a routing entry501-5. Accordingly, the destination decision unit123decides that the output interface number, next hop IP address, and output port number of the packet are3, 11.12.1.1, and3, respectively. The destination decision unit123decides upon receipt of a packet destined for the terminal T1or T2that the output interface number, next hop IP address, and output port number of the packet are1, 12.13.1.1, and1, respectively, decides upon receipt of a packet destined for the terminal T3that the output interface number, next hop IP address, and output port number of the packet are2, 13.14.1.1, and2, respectively, and decides upon receipt of a packet destined for the terminal T4that the output interface number, next hop IP address, and output port number of the packet are2, 13.14.1.2, and2, respectively.

Upon receipt of the output interface number from the destination decision unit123, the routing table search starting unit A (112) transmits the information to the execution decision unit115(step713). The execution decision unit115transmits a piece of On/Off information for the output interface to the routing table search starting unit A (112) (step714).

More specifically, for example, if the router R0receives a packet destined for the terminal T5, the output interface number of the packet is3, and thus, the execution decision unit115transmits a piece of On/Off information of On to the routing table search starting unit A (112). On the other hand, if the router R0receives a packet destined for any of the terminals T1to T4, the output interface number of the packet is1or2, and thus, the execution decision unit115transmits a piece of On/Off information of Off to the routing table search starting unit A (112).

(2-1)FIG. 10shows the details of the execution decision unit115. The execution decision unit115is composed of an execution information table1000-A which stores a piece of On/Off information for each output interface, an execution information table1000-B which stores a piece of On/Off information for each input interface, and an execution information table control unit1010. The execution information tables1000-A and1000-B have the same format. The execution information table1000-A is used at the time of input-side filtering while the execution information table1000-B is used at the time of output-side filtering.FIG. 11shows an implementation example of the execution information table1000-A. A corresponding piece of On/Off information is stored at an address equal to the number of each output interface. As for pieces of On/Off information in each execution information table1000-A of the router R0inFIG. 1, only a piece1001-A3of On/Off information for interface No.3is On, and the other pieces of On/Off information are Off. The execution information table control unit1010reads out a piece of On/Off information corresponding to the output interface number from the execution information table1000-A and transmits the piece to the routing table search starting unit A (112).

The following processing branches depending on the piece of On/Off information received by the routing table search starting unit A (112) (step705). If the piece of On/Off information is On, the routing table search starting unit A (112) instructs the routing table search unit130to make a search in the routing table500and transmits the SIP313in the SIP store unit as search key information (step706). Upon receipt of the information, the routing table search unit130reads out the routing entries501from the routing table500in order from one with the smallest address in the same manner as in the process in step703. The routing table search unit130compares each read-out IP address condition with the SIP313and transmits an interface number corresponding to a matching IP address condition retrieved first to a filtering result decision unit113as a second input interface number. If there is no routing entry501-istoring a matching IP address condition, the routing table search unit130notifies the filtering result decision unit113that there is no matching routing entry501-i(step707).

The routing table search unit130decides upon receipt of a packet which contains an IP address belonging to the network N3or N4inFIG. 1as a source IP address that the input interface number is1, decides upon receipt of a packet with a network IP address belonging to the network N5or N6that the input interface number is2, decides upon receipt of a packet with a network IP address belonging to the network N7that the input interface number is3, and decides upon receipt of a packet with any other IP address that there is no matching entry. If there is any matching routing entry501-i, the process branches depending on whether or not the input interface number matches the second input interface number (step708). If the input interface number is equal to the second input interface number, the filtering result decision unit113decides that the packet is intended for “forwarding” because the packet in the packet transmitting/receiving circuit230is input from a valid input interface (step709). On the other hand, if the interface numbers are not equal to each other, the filtering result decision unit113decides that the packet is intended for “discard” because the packet is input from an invalid input interface (step710). If there is no matching entry501-i, step708is skipped, and the filtering result decision unit113decides that the packet is intended for “discard” (step710).

For example, if the terminal T1transmits a packet with an IP address belonging to the network N3as a source IP address, the source IP address matches the IP address condition of a routing entry501-3, and thus, the destination decision unit123decides that the input interface number of the packet is1. Since this number matches the second input interface number, the filtering result decision unit113decides that the packet is intended for “forwarding.” If the terminal T1transmits a packet with an IP address belonging to any of the networks N5to N7as a source IP address, the destination decision unit123decides that the input interface number of the packet is2or3. Since this number does not match the second interface number, i.e.,1, the filtering result decision unit113decides that the packet is intended for “discard.” If the terminal T1transmits a packet with an IP address belonging to any one other than the networks N1to N7and the IX as a source IP address, there is no routing entry501-iwith an IP address condition matching the source IP address. For this reason, the filtering result decision unit113decides that the packet is intended for “discard.”

On the other hand, if the piece of On/Off information is Off in step705, the filtering result decision unit113decides that the packet in the packet transmitting/receiving circuit230is intended for “forwarding” (step709) and transmits the filtering information23indicating “forwarding” to the packet transmitting/receiving circuit230(step711).

The processing described above is a processing operation in strict mode. A processing operation in loose mode is different only in that it does not include the branch in step708. If an IP address condition matching the source IP address of the packet exists in the routing table500in step707, it is only necessary to execute step709in which the filtering result decision unit113decides that the packet is intended for “forwarding.”

As described above, the destination decision and filtering unit100of the present invention need not execute routing table search in step707if the piece of On/Off information is Off. For this reason, it is unnecessary to execute routing table search for filtering for all packets. This minimizes degradation in performance caused by filtering and implements an improvement in search performance over IETF RFC 2827.

In the above example, only input-side filtering which is intended for a packet received from one of the input ports201is executed, and output-side filtering which is intended for a packet received from the packet forwarding unit250is not executed. This is because input-side filtering is more effective for speeding up. To show an example of the effects of the present invention, a case will be considered where a packet to be output to one output interface (or output port) is subjected to filtering using the router200including the N interface units210and 2N input ports201. At this time, if the destination decision and filtering unit100of each of the interface units210is to execute input-side filtering, the destination decision and filtering unit100only needs to execute filtering for an average of 1/(2N) of packets. For this reason, the routing table search unit130delivers about (1+1/(2N))^−1 times the performance delivered when only destination decision processing is executed. For example, if N=16, the routing table search unit130delivers about 0.97 times.

On the other hand, if the destination decision and filtering unit100is to execute output-side filtering, the interface unit210of each destination decision and filtering unit100of this embodiment includes two output interfaces, and thus, filtering is executed for an average of ½ of packets output from the interface unit210. For this reason, the routing table search unit130delivers about 0.67 times the performance delivered when only destination decision processing is executed.

As described above, if the execution decision unit115has a piece of On/Off information for each output interface (or output port), degradation in performance caused by filtering can be prevented more effectively by executing input-side filtering by the destination decision and filtering units100in a distributed manner.

Cases have been explained where the execution decision unit115has a piece of On/Off information for each output port number. The execution decision unit115may have a piece of On/Off information for each output port number. At this time, the execution information table1000-A has a piece of On/Off information for each output port number. In step713, upon receipt of an output interface number and an output port number from the destination decision unit123, the routing table search starting unit A (112) transmits the output port number to the execution decision unit115. In step714, it suffices that the execution decision unit115transmits a piece of On/Off information corresponding to the output port number to the routing table search starting unit A (112).

(2-2) Input-side filtering when filtering is turned on or off for each output interface (or output port) has been explained above particularly with reference toFIG. 7or the like. Output-side filtering when filtering is turned on or off for each input interface (or input port) will then be explained. A case will be considered where the same network as that inFIG. 1is used, and the router R0executes filtering only for a packet input from the IX, i.e., the network whose interface number is3. In this case, pieces of execution information in the execution information table1000-A are all Off. The destination decision and filtering unit100decides that all packets input from the corresponding ones of the input ports201are intended for “forwarding.” Each of the packets passes through the packet forwarding unit250and is forwarded to the packet transmitting/receiving circuit230on the output side. The packet transmitting/receiving circuit230stores the packet and at the same time transmits information in the internal header unit330and header unit310to the destination decision and filtering unit100.

The output-side filtering operation of the destination decision and filtering unit100will be explained with reference to the flowchart shown inFIG. 12. The flowchart is different from the flowchart of the processing of the destination decision and filtering unit100for a packet input from one of the input ports201illustrated inFIG. 7and shows a process flow in which the destination decision process (steps702to704) is omitted, and in step714described above, the execution decision unit115reads out a piece of On/Off information corresponding to an input interface (or input port number) from the execution information table1000-B with the same format as that of the execution information table1000-A and transmits it to the routing table search starting unit A (112). The other operations are the same as those of input-side filtering.

(2-3) Cases have been explained above where the execution decision unit115turns on or off a piece of On/Off information for each input interface (input port) or output interface (output port), particularly with reference toFIG. 11or the like. An example will now be explained where a piece of On/Off information is turned on or off for each flow. A flow here refers to a flow sequence for a packet decided from at least one of packet header information, an input interface (or input port), and an output interface (or output port). As examples of a flow, there can be considered one for a pair of an input port and an output port, one for a pair of an input interface and an output interface, and one for a pair of a source address and a destination address which, however, are not limitative. By turning on or off a piece of On/Off information for each flow, an ISP can provide, for a user, an additional communication service which executes filtering for a specific flow. For example, if the ISP ISP-A provides, for a user having the terminal T1(whose IP address is 14.15.1.1), an additional communication service which executes filtering for a packet received from the terminal T5(whose IP address is 19.20.1.1), it suffices that the router R0executes filtering for a packet with an input port number of3, a destination IP address of 14.15.1.1, and a source IP address of 19.20.1.1.

FIG. 13shows an implementation example of the execution decision unit at this time. The execution decision unit115inFIG. 13is composed of an execution information table control unit1310and an execution information table1000-C shown inFIG. 14. The execution information table1000-C inFIG. 14has a format used to decide, on the basis of the source IP address (SIP), destination IP address (DIP), and input port number of a packet, whether to execute filtering for the packet. Each of entries1001-C of the execution information table1000-C, any of which is denoted by1001-Ci (i is an integer equal to or larger than 1) and stores a SIP, a DIP, and an input port number as a SIP condition, a DIP condition, and an input port number condition, respectively.

As operation when a packet is input, it suffices that the following processing is executed in step714described above. More specifically, in step714, the execution information table control unit1310reads out the entries1001-C from the execution information table1000-C in order from one with the smallest address. The execution information table control unit1310compares corresponding pieces of information in the storing units111,114, and116and an output interface store unit115A with the SIP condition, DIP condition, and input port number condition of each read-out entry1001-Ci to retrieve a matching entry1001-Ci. If there is any matching entry1001-Ci, the execution information table control unit1310decides that a corresponding piece of On/Off information is On; otherwise, Off. The execution information table control unit1310transmits the piece of On/Off information to the routing table search starting unit A (112).

In step714, the execution information table control unit1310needs to read out the entries1001-C one by one and compare each read-out entry1001-Ci with the source address. Accordingly, the performance of the execution decision unit115degrades with increasing number of the entries1000-C. To turn on or off filtering for any one of each of input interfaces, each of input ports, each of output interfaces, and each of output ports, it is preferable to use the execution information tables1000-A and1000-B.

Assume a case where a port between the IX and the router R0is physically implemented by a plurality of ports using a technique such as link aggregation (802.3ad). In this case, if the router R0executes filtering for a packet originating from the terminal T1and destined for the terminal T5, filtering needs to be executed for packets input from a plurality of input ports. In such a case, it suffices that a plurality of conditions can be designated as input port number conditions of each entry1001-Ci.

A case has been described where the value of a piece of filtering On/Off information is decided on the basis of the source IP address (SIP), destination IP address (DIP), and input port number of a received packet. The execution decision unit of the present invention can also decide the value of the piece of On/Off information on the basis of other pieces of information such as the destination MAC address and source MAC address.

As described above, if an output interface and an output port number are stored as conditions of each entry1001-Ci, input-side filtering causes less degradation in performance than that caused by output-side filtering. On the other hand, if an input interface number and an input port number are stored as conditions of each entry1001-Ci, it is more preferable to execute output-side filtering.

(3) Setting of Execution Information Table of Execution Decision Unit

The administrator of the ISP ISP-A sets the execution information tables1000-A and1000-B from a control terminal10outside the router200.FIG. 15shows examples of a command input to the control terminal10at the time of setting of the execution information tables1000-A and1000-B. The “out13interface_filter” commands are ones to set pieces of On/Off information for respective output interfaces in entries1001-A1and1001-A2and the entry1001-A3. Reference numeral151denotes an output interface number; and152, a piece of On/Off information. The commands in the first and second lines are intended to set the pieces of On/Off information for interfaces Nos.1and2as the output interfaces to Off, and the command in the third line is intended to set the piece of On/Off information for interface No.3as the output interface to On. To set a piece of On/Off information for each output interface, input port, and output port, an “in_interface_filter” command, an “in_port_filter” command, and an “out_port_filter” command are respectively used instead of an “out_interface_filter” command.

FIG. 16shows an example of a command, a “flow_filter” command which is used to set the execution information table1000-C. The command inFIG. 16is used to set an entry1001-C1. Reference numeral161denotes a SIP condition;162, a DIP condition; and163, an input port number condition.

Upon receipt of a command, the processor280transmits receipt information to the execution decision unit and an instruction to write the information to the execution information table1000-C. The execution information table control unit in the execution decision unit writes the receipt information in the execution information table1000-C.