HK1175622A - Packet transfer system, control apparatus, transfer apparatus, method of creating processing rules, and program - Google Patents

Description

Packet forwarding system, control device, forwarding device, and program and method for preparing processing rule

Reference to related applications

This application is based on and claims priority from japanese patent application No.2010-068902, filed 3/24/2010. The disclosure of which is incorporated herein by reference.

Technical Field

The invention relates to a packet forwarding system, a control device, a forwarding device, a method for preparing a processing rule, and a program. More particularly, the present invention relates to a packet forwarding system having a control plane that manages flows according to policy management and a data plane that performs signal processing. The invention also relates to a corresponding control device, a corresponding forwarding device, and a method and program for preparing processing rules.

Background

Patent document 1 discloses a packet forwarding apparatus with which a plurality of flows can be collected into one flow bundle and then the flow bundle can be processed or processed. Specifically, the packet forwarding device of this patent document includes a flow detection device and a control device. The flow detection apparatus distinguishes a flow to which an input packet belongs from header information of the input packet, and outputs a flow bundle identification which is inherent to the distinguished flow or common to at least one other flow. The control device has an information table that includes a plurality of information entries corresponding to the flow bundle identification. The control device reads out a single information entry from the information table based on the flow bundle identification received from the flow detection device to perform a preset operation.

In non-patent documents 1, 2, an open flow (OpenFlow) is proposed, which similarly understands communication as an end-to-end flow (see non-patent documents 1 and 2). The open flow optimizes routing control, fault recovery, load balancing and optimization on a flow-by-flow basis. An openflow switch operating as a forwarding node includes a secure channel for communicating with an openflow controller, which may be considered a controller. The open flow switch operates according to a flow table whose entries are added or rewritten from time to time.

Relevant documents

Patent document

[ patent document 1]

JP patent publication No. JP-P2003-18204A

Non-patent document

[ non-patent document 1]

Nick McKeown et al.，“OpenFlow：Enabling Innovation in CampusNetworks”，[online]，[retrieved on February 15，2010]，Internet<URL：http://www.openflowswitch.org/documents/openfIow-spec-vO.9.0.pdf>

[ non-patent document 2]

“OpenFlow Switch Specification”Version 0.9.0(Wire Protocol 0×98)[retrieved February 15，2010]Internet<URL：http://www.openflowswitch.org/documents/openfIow-spec-vO.9.0.pdf>

Disclosure of Invention

Technical problem to be solved

The entire disclosures of patent document 1 and non-patent documents 1 and 2 are incorporated herein by reference.

The present inventors made the following analysis.

As noted in patent document 1, if the number of information entries used by a forwarding node (i.e., a switch or a router) increases, the following problem occurs. That is, the number or capacity of memories for holding these information entries increases, while the process for retrieving these information entries becomes time-consuming, thus reducing the packet forwarding capability.

On the other hand, if the flow entry is increased, the following problem occurs: in the case where a network failure or maintenance causes a change in the network topology, the management burden involved in its rewriting increases.

In this respect, in the packet forwarding apparatus of patent document 1, band checking or gathering of statistical information is performed using flow bundle identification, but the number of information entries for packet processing is not reduced (see paragraph 23 "routing table" of patent document 1 and fig. 7).

In view of the prior art described above, the object of the present invention is to: provided are a packet forwarding system, a control device, a forwarding device, a method for preparing a processing rule, and a program, wherein the number of entries for packet processing maintained by a forwarding node can be reduced.

Means for solving the problems

The packet forwarding system in the first aspect of the present invention includes: a policy store holding policies that specify processing content and matching keys that identify packets to which the processing content is to be applied. The packet forwarding system further comprises: a policy management unit that determines the processing content and a tentative (temporary) matching key that identifies a packet to which the processing content is to be applied, with reference to a policy associated with the received packet. The packet forwarding system further comprises: an aggregation tree having a depth corresponding to a length of information to be the matching key. A plurality of nodes branching from a root of the aggregation tree and levels of the nodes represent values of the matching key and the mask length, respectively. The processing rules or the policies can be registered in each individual node. The packet forwarding system further comprises: a processing rule aggregation unit to register the policy in the node of the aggregation tree corresponding to the matching key of the policy of the aggregation tree. The processing rule aggregating unit traces back the aggregation tree from the root of the aggregation tree downward based on the tentative matching key determined by the policy management unit to search for and find a node beyond which no policy is registered downward along the depth of the tree. The processing rule aggregation unit forms the processing rule with the thus found node of the aggregation tree as the matching key. The processing rule aggregating unit registers the processing rule in the node of the aggregation tree thus found. The packet forwarding system further comprises: and a processing rule memory that holds the processing rule formed by the processing rule aggregating unit. The packet forwarding system further comprises: a packet processor that performs registration of the processing rule in the processing rule memory according to registration of the processing rule aggregation unit in the aggregation tree for the processing rule. The packet processor performs packet processing by referring to the processing rule stored in the processing rule memory.

The control apparatus in the second aspect of the present invention includes: a policy store holding policies that specify processing content and matching keys that identify packets to which the processing content is to be applied. The control apparatus further includes: a policy management unit that determines the processing content and a tentative matching key that identifies a packet to which the processing content is to be applied, with reference to a policy associated with the received packet. The control apparatus further includes: an aggregation tree having a depth corresponding to a length of information to be the matching key. A plurality of nodes branching from a root of the aggregation tree and levels of the nodes represent values of the matching key and the mask length, respectively. The processing rules or the policies can be registered in each individual node. The control apparatus further includes: a processing rule aggregation unit that registers the policy in the node of the aggregation tree corresponding to the matching key of the policy. The processing rule aggregating unit traces back the aggregation tree from the root of the aggregation tree downward based on the tentative matching key determined by the policy management unit to search for and find a node beyond which no policy is registered downward along the depth of the tree. The processing rule aggregation unit forms the processing rule with the thus found node of the aggregation tree as the matching key. The processing rule aggregating unit registers the processing rule in the node of the aggregation tree thus found. The control apparatus further includes: a processing rule storage that registers the processing rule formed by the processing rule aggregation unit. The control apparatus further includes: a packet processor that performs registration of the processing rule in the processing rule memory according to registration of the processing rule aggregation unit in the aggregation tree for the processing rule. The packet processor performs packet processing by referring to the processing rule stored in the processing rule memory.

A forwarding device in a third aspect of the present invention includes: and the strategy memory is connected to the control device and stores the processing rules formed by the control device. The forwarding device further includes: a packet processor that performs registration of the processing rule in the processing rule memory according to registration of the processing rule aggregation unit in the aggregation tree for the processing rule. The packet processor further performs packet processing with reference to the processing rule stored in the processing rule memory.

The method in the fourth aspect of the present invention is a method for forming a processing rule in a packet forwarding system. The packet forwarding system includes: and a memory for storing an aggregation tree having a depth corresponding to a length of information to be a matching key of a policy that specifies processing contents, and the matching key. The matching key identifies the packet to which the processing content is to be applied. A plurality of nodes branching from a root of the aggregation tree and levels of the nodes represent values of the matching key and the mask length, respectively. The processing rules or the policies can be registered in each individual node. The method comprises the following steps: registering the policy in the node of the aggregation tree corresponding to the matching key of the policy; deciding, with reference to the policy associated with the received packet, processing contents and a tentative matching key for identifying the packet to which the processing contents are to be applied; and tracing back the aggregation tree from the root of the aggregation tree downwards based on a tentative matching key to search for and find a node beyond which no registration policy exists downwards along the depth of the tree, thereby forming the processing rule with the node thus found as the matching key. The method of the present invention is closely related to the designated machine (i.e., the packet forwarding system that processes incoming packets according to processing rules that match the incoming packets).

A program in a fifth aspect of the present invention is a program to be run on a computer included in a packet forwarding system including: and a memory for storing an aggregation tree having a depth corresponding to a length of information to be a matching key of a policy that specifies processing contents, and the matching key. The matching key identifies the packet to which the processing content is to be applied. A plurality of nodes branching from a root of the aggregation tree and levels of the nodes represent values of the matching key and the mask length, respectively. The processing rules or the policies can be registered in each individual node. The program causes a computer included in the packet forwarding system to execute: registering the policy in the node of the aggregation tree corresponding to the matching key of the policy; deciding, with reference to the policy associated with the received packet, a processing content and a tentative matching key, the tentative matching key identifying the packet to which the processing content is to be applied; and tracing back the aggregation tree from the root of the aggregation tree downwards based on the tentative matching key to search for and find a node beyond which no registration policy exists downwards along the depth of the tree, thereby forming the processing rule with the node thus found as the matching key. Note that the program may be recorded on a computer-readable recording medium. That is, the present invention can be realized as a computer program. The invention has the advantages of

According to the present invention, the number of processing rules (flow entries) maintained by the forwarding node can be reduced. The reason for this is that: the aggregation tree may be used to prepare processing rules with shorter matching keys without including matching keys of pre-existing policies. Under this condition, the processing rule may be prepared subsequently.

Drawings

Fig. 1 is a schematic block diagram showing an outline of the present invention.

Fig. 2 is a schematic diagram showing an aggregation tree used in the present invention.

Fig. 3 is a schematic block diagram showing the configuration of example embodiment 1 of the present invention.

Fig. 4 is a diagram showing a configuration of a simplified aggregation tree for explaining the operation of exemplary embodiment 1 of the present invention.

Fig. 5 is a flowchart showing a process flow of policy registration of the aggregation tree of fig. 4 in exemplary embodiment 1 of the present invention.

Fig. 6 is a flowchart showing a flow of processing for registering a new flow entry to the aggregation tree of fig. 4 in exemplary embodiment 1 of the present invention.

Fig. 7 is a schematic diagram for illustrating the operation of example embodiment 1 of the present invention step by step.

Fig. 8 is a view similar to fig. 7 and following fig. 7.

Fig. 9 is a schematic view similar to fig. 8 and following fig. 8.

Fig. 10 is a schematic view similar to fig. 9 and following fig. 9.

Fig. 11 is a schematic view similar to fig. 10 and following fig. 10.

Fig. 12 is a schematic block diagram showing the configuration of example embodiment 2 of the present invention.

Fig. 13 is a schematic block diagram showing the configuration of example embodiment 3 of the present invention.

Detailed Description

First, an outline of the present invention is shown. It should be noted that: the numerals used to refer to the figures appearing in the summary are used only to aid understanding and are not intended to limit the invention to the manner shown in the figures. The present invention may be applied to a packet forwarding system including a data plane 100B and a control plane 100A, as shown in fig. 1. The data plane 100B includes a packet processor 22, and the packet processor 22 refers to a processing rule including a matching key matching the received packet among the plurality of processing rules stored in the processing rule memory 21, thereby performing packet processing. The control plane 100A sets processing rules to control the data plane 100B.

More specifically, the control plane 100A includes a policy storage 11 designed to store a plurality of policies, each policy of the plurality of policies specifying processing contents and a matching key for identifying a packet to which the processing contents are to be applied. The control plane 100A further includes a policy management unit 12, and the policy management unit 12 determines the processing contents to be applied to the received packet and a tentative or temporary matching key for identifying the packet to which the processing contents are applied, with reference to the policy stored in the policy storage 11. The control plane 100A further includes an aggregation tree memory 13 designed to store an aggregation tree having a tree structure at the nodes of which policies stored in the policy memory 11 or processing rules determined by the policy management unit 12 can be registered. The control plane 100A further includes a processing rule aggregation unit 14, and the processing rule aggregation unit 14 traces the aggregation tree down from its root node along the depth of the tree to search for a node beyond which there is no node of the registration policy, thereby preparing a processing rule having the node as a matching key.

Fig. 2 schematically shows an aggregation tree for aggregating IP addresses of IPv4 (internet protocol version 4) into matching keys. In this case, the aggregation tree is constructed as a binary tree having a depth equal to the length of the IP address (i.e., a tree divided into 2 branches at each branch point). The number of levels of nodes traced back down from the root of the binary tree represents the mask length of the IP address used as the matching key. Each node represents the value of the matching key. For management, a processing rule or policy is associated with each node of such an aggregation tree.

Using the aggregation tree described above, the high significance bitmask may aggregate IP addresses included in the processing rules to reduce the number of flow entries. Specifically, arbitration may occur as follows as to whether a pre-existing policy satisfies the "include" relationship:

at this time, it is assumed that an IP routing table having the following entry (policy) is stored in the policy storage 11, and the entry (policy) requires the longest prefix match.

Transmitted policy ID network address/mask destination

11.1.1.0/24 Port 0

2.1.1.0.0/16 Port 1

It is also assumed that: in this case, an unknown packet with a destination IP address of 1.1.2.1 is received. Based on the longest prefix match, the unknown packet matches an entry of policy ID 2. Therefore, the preparation processing contents are the processing rule that the packet is to be sent to port 1.

If a network address/mask of "1.1.0.0/16" is used in order to reduce the length of the matching key of the processing rule, packets of the flow that should inherently match the policy ID1 will not be sent to the appropriate destination. For example, a packet of 1.1.1.1 would be sent to port 1.

In the present invention, for example, the following is assumed at this time: in the above-described aggregation tree of FIG. 2, a policy (with the high order of the matching key being 0) is stored in node 1-1, and another policy (with the high order of the vertical row of the matching key being 000) is stored in node 3-1. In this case, when a newly received packet of the matching key "0011111...." is received, the processing rule aggregating unit 14 performs tracing back in the order of nodes 1-1, 2-1, 3-2, and so on, from the root of the aggregation tree according to the value of the tentative matching key issued from the policy management unit 12. The processing rule aggregation unit sets the matching key corresponding to the node 3-2 as the matching key of the processing rule under consideration. It should be noted that node 3-2 is such a node: down the depth of the tree, beyond this node, there are no nodes that have registered a policy. That is, the processing rule aggregation unit does not drop to a lower node. Thus, after registering a pre-existing policy in a node in the aggregation tree corresponding to the IP address, the following nodes are searched: down the depth of the tree, beyond this node, there is no node that registers a policy, i.e., the node does not "include" the matching key of a pre-existing policy. Thus, as described above, a processing rule of a matching key having a necessary minimum length can be prepared.

[ example embodiment 1]

Hereinafter, exemplary embodiment 1 of the present invention will be described in detail with reference to the drawings. Fig. 3 shows a block diagram of a configuration according to an exemplary embodiment 1 of the present invention.

Referring to fig. 3, a packet forwarding system 100 according to example embodiment 1 of the present invention includes a control plane 100A that manages flows and a data plane 100B that forwards packets. The packet forwarding system forwards a packet transmitted from the transmission source device 200 to the transmission destination device 300. Such a packet forwarding system may be implemented by a flow-based switch that forwards packets, e.g., on a flow-by-flow basis.

The data plane 100B includes a flow entry table 21A, a packet processor 22A, a packet input unit 23A, and a packet output unit 24A.

The packet input unit 23A is a port connected to the transmission source device 200, and represents a stream entry point of the system. The packet output unit 24A is a port connected to the transmission source device 200, and represents an egress point of the system. It should be noted that, in fig. 3, only one packet input unit 23A and one packet output unit 24A are shown. However, it is assumed that a plurality of packet ingress units and a plurality of packet egress units are provided, and that these packet ingress and egress units are connected to respective different transmission sources and transmission destination devices.

The flow entry table 21A is equivalent to the above-described processing rule memory 21, and is a table in which a flow entry (processing rule) is stored. In each of these flow entry, a matching key for identifying a flow and packet processing contents are stored in association with each other. In each flow entry, a valid time (lifetime) is set. If a packet matching the flow entry is not received during the valid time, packet processor 22A considers: the considered flow is to be terminated (timeout). The packet processor then deletes the flow entry in question. For such an arrangement, the same scheme as that used in the openflow switches of non-patent documents 1, 2 can be used.

The packet processor 22A refers to the flow entry table 21A to find a flow entry matching the received packet, thereby executing the processing determined as the packet processing content in the thus found flow entry. For example, the processing may be forwarding a packet from a packet output unit specified in the plurality of packet output units, discarding the packet, or rewriting a packet header. If there is no flow entry matching the received packet in the flow entry table 21A, the packet processor 22A requests the policy management unit 12A to prepare a flow entry matching the received packet. In response to an instruction from the control plane 100A, the packet processor 22A registers a new flow table entry in the flow table entry table 21A. If a packet matching the flow entry is not received during the time specified by the validity time, packet processor 22A deletes the flow entry, and notifies flow aggregation unit 14A of the thus-deleted flow entry.

By notifying the policy management unit 12A of the start packet (packet having no matching entry) in each flow, and by preparing and registering the packet in the flow entry table 21A, the packet and subsequent packets following the start packet in the same flow can be forwarded at this time.

The control plane 100A includes a policy management layer, which in turn includes a policy table 11A equivalent to the policy storage 11 of fig. 1 and a policy management unit 12A. The control plane 100A further comprises a flow aggregation layer, which in turn comprises a flow aggregation tree 13A equivalent to the aggregation tree memory 13 of fig. 1 and a flow aggregation unit 14A equivalent to the processing rule aggregation unit 14 of fig. 1.

The policy table 11A is a table in which information for determining processing contents (e.g., packet forwarding destination) based on the contents of a packet whose flow entry has been requested to be prepared by the packet processor 22A is set. For example, a routing table maintained by a router or switch is a typical policy table 11A.

The policy management unit 12A has a function of managing policies registered in the policy table 11A, and a function of notifying the content of a change to the flow aggregation layer if the policy table 11A is changed. Further, if the packet processor 22A requests preparation of a flow entry for an unknown packet, the policy management unit 12A refers to the policy table 11A to notify the flow aggregation unit 14A of the processing contents (e.g., packet forwarding destination) and a tentative matching key of the unknown packet.

The flow aggregation tree 13A is a binary tree whose depth corresponds to information to be a matching key of the packet. The tree can register the policies registered in the policy table 11A and the flow entry registered in the flow entry table 21A in association with the respective nodes of the tree.

In the present exemplary embodiment, for simplicity of explanation, such a stream aggregation tree having a depth equal to 4, each layer of the tree representing a mask length, is used, as shown in fig. 4. Assume that the flow aggregation tree branches with "0" or "1" in order from the upper level of the vertical row to the lower level of the vertical row. The sequence of performing the branch operation to the lower level is repeated. The management of the policies and flow entries performed with the aid of the flow aggregation tree will be described in detail later with reference to fig. 5 to 11.

The flow aggregation unit 14A registers the policy, which is notified from the policy management unit 12A of the flow aggregation tree 13A, at a position corresponding to the matching key of the policy. Further, the flow aggregation unit 14A decides in which node of the flow aggregation tree 13A to register the flow entry whose tentative matching key has been decided by the policy management unit 12A. Thus, the flow aggregation unit decides that the flow entry is to be registered in the flow entry table 21A, and instructs the packet processor 22A to register in the flow entry table 21A accordingly. Further, if notified by the packet processor 22A that the flow entry is not already in the flow entry table 21A, the flow aggregation unit 14A deletes the corresponding flow entry from the flow aggregation tree 13A. That is, in the flow aggregation tree 13A, the flow entry is registered or deleted in the same manner as the flow entry registered in the flow entry table 21A.

The various components (processing means) of the packet forwarding system 100 shown in fig. 1 can be realized by a computer program that allows a computer constituting the packet forwarding system 100 to perform the above-described processing operations using the hardware of the computer.

The operation of the present exemplary embodiment will be described in detail below with reference to the accompanying drawings. The following description will be made in the order of the "policy registration" section and the "flow entry registration" section.

[ policy registration ]

Fig. 5 depicts a flow chart showing the flow of registering a policy in the flow aggregation unit 14A. As described previously, the policy management unit 12A notifies the flow aggregation unit 14A of the contents of the policies registered in the policy table 11A (step S001). With the root of the flow aggregation tree 13A as a starting point, the flow aggregation unit 14A advances to a node corresponding to the matching key of the policy. The flow aggregation unit registers the policy at the node (step S002). Regarding the policy, the matching key and the entire used information are notified. For example, if the content is an IP address, information down to the mask length is notified. Next, the relevant content is registered at the relevant position in the flow aggregation tree 13A.

Next, the flow aggregation unit 14A checks whether or not there is any flow entry in the traversed node (step S003). If the view result indicates that no flow entry exists in the traversed node, the processing of policy registration ends.

If there is any flow entry in the traversed node, the flow aggregation unit 14A deletes the flow entry from the flow aggregation tree 13A (step S004), while also requesting the packet processor 22A to also delete the flow entry from the flow entry table 21A (step S005). By prioritizing the policy in this manner, it is possible to eliminate the situation of competing (colliding) with the flow entries to be prepared and registered later. It should be noted that, with respect to the flow entry deleted from the flow entry table 21A, upon receiving the next packet, the policy management unit 12A is requested to prepare the flow entry with respect to the unknown packet.

[ registration of flow entry ]

Fig. 6 depicts a flowchart showing a flow of registering a flow entry in the flow aggregation unit 14A. As described previously, the policy management unit 12A prepares a flow entry by referring to the policy table 11A in response to a request to prepare a flow entry. The policy management unit notifies the flow aggregation unit 14A of the contents of the flow entries thus prepared (step S101). Next, with the root of the flow aggregation tree 13A as a starting point, the flow aggregation unit 14A starts searching for a node matching the information serving as the matching key (step S102).

First, the flow aggregation unit 14A checks whether or not a policy exists in a layer lower than that of the current position (step S103). If a policy exists in a layer lower than that of the current position, the situation of competing with the policy must be eliminated. Therefore, the flow aggregation unit 14A checks a bit of the matching key that is one position lower than the current bit, and descends toward the relevant node side along the flow aggregation tree 13A. The operation of checking and descending is repeatedly performed (step S106).

Suppose that: as a result of tracing the flow aggregation tree 13A down to the lower level side, a decision is given that there is no policy on the layer side lower than the current position (no at step S103). Next, the flow aggregation unit 14A registers a new flow entry notified from the policy management unit 12A at the current position (the node at the above-described decision time) (step S104). Meanwhile, the flow aggregation unit 14A requests the packet processor 22A to register a new flow entry whose matching key is the above-described node position in the flow entry table 21A (step S105). By stepping down along the aggregation tree 13A from its root until it is confirmed that no policy exists in a layer lower than the current position level, a matching key having the shortest length without conflicting with other pre-existing policies can be obtained.

Fig. 7 to 11 show a process of registering a new policy and a new flow entry in the flow aggregation tree 13A shown in fig. 4. In the following description, a 4-bit destination address having a net mask (x.x.x.x/Y, Y is a net mask length) is used as a matching key of a policy registered in the policy table and a matching key of a flow entry registered in the flow entry table. It should be noted that: matching keys may be associated with branches of each level; however, the matching key is not associated with the highest branch representing the root of the flow aggregation tree.

At this time, it is assumed that the initial state is a state in which a flow entry has not been registered in the flow aggregation tree 13A shown in fig. 4; and similarly, no flow entry has been registered in the flow entry table 21A.

It is also assumed that: from the above state, the following two policies have been registered in the policy table 11A: (a) destination address 0.0.0.0/1, processing content a (forwarding from port a) (B) destination address 1.1.0.0/3, processing content B (forwarding from port B)

When a policy is to be registered in the policy table 11A, a notification is issued to the flow aggregation unit 14A in a case where an address down to the net mask is specified. The flow aggregation unit 14A descends from the highest level of the flow aggregation tree 13A to the layer of the specified network mask to search for a policy registration location where the policy is to be registered.

Fig. 7 shows a state where policies (a), (b) have been registered. Policy (a) is registered in node 1-1 and policy (b) is registered in node 3-7.

Assume that packet processor 22A receives the following packets:

destination address 0.1.1.0.

At this time, the corresponding flow entry is not registered in the flow entry table 21A. Thus, the packet processor 22A requests the policy management unit 12A to prepare a flow entry corresponding to the unknown packet.

The policy management unit 12A having received the request to prepare the flow entry refers to the policy table 11A to search for a policy corresponding to the destination address of 0.1.1.0. Since the policy (a) satisfies the condition, the policy management unit 12A notifies: a flow table entry having processing contents of a (forwarded from port a) and a tentative matching key of destination address 0.1.1.0 is prepared for a packet having destination address 0.1.1.0.

The stream aggregation unit 14A steps down the stream aggregation tree of fig. 7 from the highest level according to the flowchart of fig. 6. At node location 1-1, the flow aggregation unit gives a decision that no policy has been registered at a lower level than this current location, as shown in fig. 8.

At this time, the flow aggregation unit 14A causes the matching key of the flow entry registered by the packet processor 22A in the flow entry table 21A to have (c) the destination address of 0.0.0.0/1. This destination address is combined with the process content a (forwarded from port a) to form a set which is then registered in the flow entry table 21A.

The thus prepared flow entry is also registered in the corresponding node of the flow aggregation tree (see fig. 8).

It is assumed that, from the above state, the following policies have been registered in the policy table 11A:

(d) destination address 0.1.0.0/3, process content a (forwarded from port a).

The flow aggregation unit 14A descends from the highest position of the flow aggregation tree 13A to the level of the specified network mask according to the flowchart of fig. 4 in the same manner as when policies (a) and (b) are processed, to search for and find a policy registration position. Then, the flow aggregation unit registers the policy at the thus found registration location.

A route registration policy (d) via node 1-1, node 2-2, and node 3-3. In the node 1-1, the flow entry (c) has been registered. Therefore, in step S004 of fig. 5, the flow aggregation unit 14A deletes the flow (c) from the flow aggregation tree, while requesting the packet processor 22A to delete the flow entry (c) from the flow entry table 21A. Since the matching key of policy (d) conflicts with the matching key of flow entry (c), i.e., the matching key of policy (d) is "included" in the matching key of flow entry (c). Therefore, if the flow entry (c) continues to be registered in the flow entry table 21A, the packet processor will then be unable to distinguish between the flow entry prepared based on the policy (d) and the flow entry (c).

As a result, policy (d) is registered in node 3-3 and flow entry (c) is deleted from its parent node 1-1.

If a packet having the destination address 0.1.1.0 that should have matched the flow entry (c) is received at this time, the packet processor 22A again requests the policy management unit 12A to prepare a flow entry. Therefore, the flow entry is prepared by the same processing as that performed when the flow entry (c) is registered.

At this time, however, policy (d) has been registered, as described above. Thus, the flow aggregation unit drops to the position of the node 3-4 without stopping at the node 1-1, as shown in fig. 10. At this location, the flow aggregation unit gives a decision that no policy has been registered beyond this location down the depth of the flow aggregation tree.

At this time, the flow aggregation unit 14A makes the matching key of the flow entry registered in the flow entry table 21A by the packet processor 22A correspond to the position of the node 3-4 having the destination address (c') of 0.1.1.0/3. Therefore, a flow entry whose destination address is 0.1.1.0/3 and whose processing content is a (forwarded from port a) is registered in the flow entry table 21A.

Assume that packet processor 22A then further receives the following packets:

(e) destination address 0.0.1.1.

In this case, as in the case of the flow entry (c) or (c'), the node 2-1 is searched to the lower layer side based on the policy (a), and a node in which a policy is registered does not exist beyond the node 2-1 down the depth of the tree. For this case, the matching key of the flow entry corresponds to the position of the above-described node 2-1, and is (e) the destination address of 0.0.0.0/2. Therefore, a flow entry whose destination address is 0.0.0.0/2 and whose processing content is a (forwarded from port a) is registered in the flow entry table 21A.

As a result, as shown in FIG. 11, the flow entry (e) is registered in the node 2-1.

Therefore, it is possible to reduce the mask length of the mask key of the flow entry to be registered and suppress an increase in the number of registered flow entries. The reason for this is that: the flow aggregation tree is traced down to search for and find a node beyond which no policy exists down the depth of the tree. Next, a flow entry having the node as a matching key is registered. As such, the entire flow table entry may be logically aggregated in the form that there is no "include" relationship with respect to the policy.

Further, in the present exemplary embodiment, when a new policy is registered, a flow entry registered in a node corresponding to a parent node on the flow aggregation tree is deleted. That is, the flow entry having the mask length shorter than the necessary length is deleted and then set again.

Further, in the present exemplary embodiment, the number of flow entries registered in the flow entry table is reduced to the necessary minimum number. This is due to the deletion of flow entries from time to time.

[ example embodiment 2]

An exemplary embodiment 2 will be described below, in which the present invention is applied to an openflow switch and an openflow controller in non-patent documents 1 and 2. Fig. 12 shows the configuration of example embodiment 2 of the present invention.

The present exemplary embodiment differs from the above exemplary embodiment 1 in that: the control plane 100A of example embodiment 1 becomes the control device 101 having the path forming unit 15A, and the data plane 100B of example embodiment 1 becomes the forwarding device 102. Although a single forwarding device 102 is shown in fig. 12, multiple forwarding devices prepare and distribute flow entries under the control of the controller 101 to process respective received packets. Otherwise, the configuration of the various components is similar to that of example embodiment 1.

In the present exemplary embodiment, the path forming unit 15A forms a forwarding path for a packet received from the open flow switch based on a preliminarily provided network topology or based on configuration information of each forwarding device (not shown), for example, thereby forming a flow entry implementing the path. The flow entry thus formed is registered as a policy in the policy table 11B, while corresponding information is notified to the flow aggregation unit 14A. The following operation is similar to that of the above-described exemplary embodiment 1. That is, the flow entry registered in the node that becomes the parent node, which is the parent node of the node in which the new policy (new flow entry) is registered, is deleted by the process of fig. 5 using the flow aggregation tree 13A. Forwarding device 102 is also instructed to perform a corresponding deletion. Similarly, the new policy (new flow entry) is issued to forwarding device 102 as a flow entry with the appropriate wildcards by the process of fig. 5 using flow aggregation tree 13A. As can be seen from the foregoing, the present invention can be applied to a configuration in which a control device such as an openflow switch and an openflow controller of non-patent documents 1 and 2 controls a large number of forwarding devices to control a packet forwarding path.

While the preferred exemplary embodiments of the present invention have been described, such exemplary embodiments have been presented by way of illustration only, and are not intended to limit the scope of the invention. That is, further modifications, substitutions and adaptations may be made without departing from the basic technical concept of the present invention.

For example, the control apparatus 101A may have: the service information collecting unit 16A is configured to collect the service information recorded by the forwarding device 102 with the aid of the flow entry. In this case, the path forming unit 15A can form: the path of the traffic state collected from the traffic information collection unit 16A is considered regardless of the shortest hop calculated from the network topology.

In the above-described exemplary embodiment, the destination address is used as the matching key. However, it is also possible to use the transport source address or both the destination address and the transport source address as a matching key. Naturally, the present invention can be applied not only to IPv4 addresses but also to IPv6 addresses.

In the above description of the exemplary embodiment, it is assumed that a packet is transmitted from the transmission source device 200 to the transmission destination device 300. The invention is also applicable to reverse flows, in which case the processing rules (flow entries) for reverse flows may be similarly aggregated.

The present invention can also be applied to a system constituted by a control plane that performs policy management and prepares a processing rule exemplified by a flow entry, and a data plane that processes a received packet according to the processing rule thus prepared. The system can aggregate matching keys of a processing rule with either a high significance bit mask or a low significance bit mask. For example, the present invention may be applied to reduce entries on a routing table maintained by a forwarding device that forwards packets with the aid of the routing table.

The disclosures of the above non-patent documents are incorporated herein by reference. The specific example embodiments or examples may be modified or adjusted based on the basic technical concept of the present invention within the scope of the entire disclosure of the present invention (including the claims). Furthermore, various combinations and selections of elements disclosed herein may be made within the context of the claims. That is, the present invention may cover various modifications or adaptations of the present invention that may occur to those skilled in the art from the entire disclosure of the present invention including the claims and the technical idea of the present invention.

Description of the reference numerals

11 policy store

11A, 11B policy Table

12. 12A policy management unit

13 aggregation tree memory

13A flow aggregation tree

14 processing rule aggregation unit

14A stream polymerization Unit

15A path forming unit

16A service information acquisition unit

21 processing rules memory

21A flow entry table

22. 22A packet processor

23A packet input unit

24A packet output unit

100 packet forwarding system

100A control plane

100B data plane

101 control device

102 forwarding device

200 transmission source device

300 transfer destination device

Claims (12)

1. A packet forwarding system, comprising:

a policy store holding policies that specify processing content and matching keys that identify packets to which the processing content is to be applied;

a policy management unit that determines the processing content and a tentative matching key that identifies a packet to which the processing content is to be applied, with reference to a policy associated with the received packet;

an aggregation tree having a depth corresponding to a length of information to be the matching key; a plurality of nodes branching from a root of the aggregation tree and levels of the nodes represent values of the matching key and mask length, respectively;

the processing rules or the policies can be registered in each individual node;

a processing rule aggregating unit that registers the policy in the node of the aggregation tree corresponding to the matching key of the policy; the processing rule aggregating unit traces back the aggregation tree from the root of the aggregation tree downward based on the tentative matching key determined by the policy management unit to search for and find a node beyond which no policy is registered downward along the depth of the tree; the processing rule aggregating unit forms the processing rule with the found node of the aggregation tree as the matching key; the processing rule aggregating unit registers the processing rule in the found node of the aggregation tree;

A processing rule memory that holds processing rules formed by the processing rule aggregating unit; and

a packet processor that performs registration of the processing rule in the processing rule memory according to registration of the processing rule in the aggregation tree by the processing rule aggregation unit; the packet processor performs packet processing by referring to the processing rule stored in the processing rule memory.

2. The packet forwarding system of claim 1,

the processing rule aggregating unit deletes a processing rule registered in a node as a parent node of a node in an aggregation tree in which a policy is newly registered; the processing rule aggregation unit causes the packet processor to delete the processing rule deleted from the aggregation tree from the processing rule memory.

3. The packet forwarding system of claim 1 or 2, wherein,

if the processing rule is deleted from the processing rule storage due to timeout, the packet processor notifies the processing rule aggregation unit that the processing rule has been deleted;

the processing rule aggregating unit deletes the notified processing rule from the aggregation tree.

4. The packet forwarding system of any of claims 1-3,

the control device includes the policy memory, a policy management unit, an aggregation tree, and the processing rule aggregation unit, forms the processing rule, and distributes the formed processing rule to each of a plurality of forwarding devices, each having the processing rule memory and the packet processor.

5. The packet forwarding system of claim 4,

the control device does not include a policy management unit, but includes: a forwarding path forming unit that forms a packet forwarding path based on configuration information of a forwarding device and a network topology including the forwarding device;

the control device causes the processing rule aggregating unit to input a matching key that implements the packet forwarding path formed by the forwarding path forming unit; the control device distributes the processing rules to each of the forwarding devices.

6. The packet forwarding system of claim 5, wherein,

the control apparatus includes: a service information acquisition unit that acquires service information recorded using the processing rule from the forwarding device;

The forwarding path forming unit forms the packet forwarding path based on the collected traffic information.

7. The packet forwarding system of any of claims 1-6,

the matching key is one of a destination IP address and a transmission source IP address.

8. A control device, comprising:

a policy store holding policies that specify processing content and matching keys that identify packets to which the processing content is to be applied;

a policy management unit that determines the processing content and a tentative matching key that identifies a packet to which the processing content is to be applied, with reference to a policy associated with the received packet;

an aggregation tree having a depth corresponding to a length of information to be the matching key; a plurality of nodes branching from a root of the aggregation tree and levels of the nodes represent values of the matching key and the mask length, respectively; the processing rules or the policies can be registered in each individual node;

a processing rule aggregating unit that registers the policy in the node of the aggregation tree corresponding to the matching key of the policy; the processing rule aggregating unit traces back the aggregation tree from the root of the aggregation tree downward based on the tentative matching key determined by the policy management unit to search for and find a node beyond which no policy is registered downward along the depth of the tree; the processing rule aggregating unit forms the processing rule with the found node of the aggregation tree as the matching key; the processing rule aggregating unit registers the processing rule in the found node of the aggregation tree;

A processing rule storage that registers the processing rule formed by the processing rule aggregating unit; and

a packet processor that performs registration of the processing rule in the processing rule memory according to registration of the processing rule in the aggregation tree by the processing rule aggregation unit; the packet processor performs packet processing by referring to the processing rule stored in the processing rule memory.

9. The control apparatus according to claim 8,

the processing rule aggregating unit deletes a processing rule registered in a node corresponding to a parent node, the parent node being a parent node of a node in an aggregation tree in which a policy is registered; the processing rule aggregation unit causes the packet processor to delete the processing rule deleted from the aggregation tree from the processing rule memory.

10. A forwarding device connected to a control device; the control apparatus includes:

a policy store holding policies that specify processing content and matching keys that identify packets to which the processing content is to be applied;

a policy management unit that determines the processing content and a tentative matching key that identifies a packet to which the processing content is to be applied, with reference to a policy associated with the received packet;

An aggregation tree having a depth corresponding to a length of information to be the matching key; a plurality of nodes branching from a root of the aggregation tree and levels of the nodes represent values of the matching key and the mask length, respectively; the processing rules or the policies can be registered in each individual node; and

a processing rule aggregating unit that registers the policy in the node of the aggregation tree corresponding to the matching key of the policy; the processing rule aggregating unit traces back the aggregation tree from the root of the aggregation tree downward based on the tentative matching key determined by the policy management unit to search for and find a node beyond which no policy is registered downward along the depth of the tree; the processing rule aggregating unit forms the processing rule with the found node as the matching key; the processing rule aggregating unit registers the processing rule in the found node of the aggregation tree;

wherein the forwarding device comprises:

a processing rule storage that registers the processing rule formed by the processing rule aggregating unit; and

a packet processor that performs registration of the processing rule in the processing rule memory according to registration of the processing rule in the aggregation tree by the processing rule aggregation unit; the packet processor performs packet processing by referring to the processing rule stored in the processing rule memory.

11. A method of forming processing rules in a packet forwarding system, the packet forwarding system comprising:

a memory that stores an aggregation tree having a depth corresponding to a length of information to be a matching key of a policy that specifies processing contents, and the matching key;

the matching key identifying the packet to which the processing content is to be applied; a plurality of nodes branching from a root of the aggregation tree and levels of the nodes represent values of the matching key and mask length, respectively; the processing rules or the policies can be registered in each individual node;

the method comprises the following steps:

registering the policy in the node of the aggregation tree corresponding to the matching key of the policy;

deciding, with reference to the policy associated with the received packet, processing contents and a tentative matching key for identifying the packet to which the processing contents are to be applied; and

based on a tentative matching key, the aggregation tree is traced back down from the root of the aggregation tree to search for and find a node beyond which no registration policy exists down the depth of the tree, thereby forming the processing rule with the found node as the matching key.

12. A program to be run on a computer included in a packet forwarding system, the packet forwarding system comprising:

a memory that stores an aggregation tree having a depth corresponding to a length of information to be a matching key of a policy that specifies processing contents, and the matching key;

the matching key identifying the packet to which the processing content is to be applied; a plurality of nodes branching from a root of the aggregation tree and levels of the nodes represent values of the matching key and mask length, respectively; the processing rules or the policies can be registered in each individual node;

the program causes the computer to execute:

registering the policy in the node of the aggregation tree corresponding to the matching key of the policy;

deciding, with reference to the policy associated with the received packet, processing contents and a tentative matching key for identifying the packet to which the processing contents are to be applied; and

based on the tentative matching key, the aggregation tree is traced back down from the root of the aggregation tree to search for and find a node beyond which there is no registration policy down the depth of the tree, thereby forming the processing rule with the found node as the matching key.