JP6438375B2 - Communication system, communication apparatus, control apparatus, traffic observation method, and program - Google Patents

Description

  The present invention relates to a technology for observing traffic flowing in a communication network.

  In the conventional observation technique, traffic is classified and evaluated for each pair of a transmission source and a reception destination (hereinafter referred to as a flow) (for example, see Non-Patent Document 1). Here, for the sake of simplicity, a case where the flow is a pair of transmission and reception “devices” will be described. An actual flow is often defined with a “logical connection termination point pair” determined by a pair of an address and a port number, such as 5-tuple. Each network device classifies the passing traffic for each transmission / reception pair, and counts the number of packets and bytes. Although the present invention is not limited to a particular type of network device, for simplicity, the network device is referred to herein as a switch.

The example of FIG. 1 will be described. Terminals A to F are connected by switches SW _{R to} SW _T. Each switch counts the number of packets for each flow. Here, when a packet from the terminal A to the terminal C passes through the switch SW _R and SW _S, the switch SW _R and SW _S increases with the counter flow A → C from 16 to 17. This counter value is used for failure analysis of a communication network. For example, when the counters of the switch SW _R and the switch SW _T are compared, the number of packets of the flow C → F is greatly different, and it can be estimated that there is a cause of failure between the two.

  As the number of terminals has increased in recent years, the number of flows has become enormous, making it difficult to observe all of them. For example, if the memory required for measuring each flow is 100 bytes and the number of flows reaches 10 million, 1 GB is required to manage all the flows. On the other hand, the high-speed memory used for the CPU cache is tens of MB, which is not enough. For this reason, “sampling” in which packets are thinned out and observed is performed, but there is a risk of missing an important failure.

Next, consider the possibility of reducing the number of rows in the counter table by combining multiple flows. There are only six routes in the communication network 81 of FIG. 1 regardless of the number of terminals. More specifically, a _{SW R → SW S, SW S} → SW R, SW R → SW T, SW T → SW R, SW S → SW R → SW T, SW T → SW R → SW S. Since traffic passing through the same route is processed in the same way by each switch, it is not necessary to distinguish in the cause analysis of the failure. When different processes are performed in flows that pass through the same physical route due to QoS or the like, each may be considered as a separate logical route. If the number of routes is less than the number of flows, the number of rows in the counter table can be greatly reduced by counting the number of packets for each route.

For example, if the communication with all terminal pairs in FIG 1 is performed, flow through the SW _R is present 24 (A → C, A → D, A → E, A → F, B → C, B → D, ..., F → C, a F → D), the counter table of the switch SW _R becomes 24 rows. However, path through the switch SW _R is only six. Therefore, as shown in FIG. 2, a flow determined by a pair of a transmission source and a reception destination is collectively counted as a route in the communication network 81. For example, C → E and C → F counted as separate flows in FIG. 1 are collectively counted as the same route SW _S → SW _R → SW _T in the communication network 81 in FIG. Then, the number of row counter table in the switch SW _R is suppressed to 6.

Japanese Patent Application No. 2014-132603

Y. Gu, L .; Breslau, N.M. Dufffield, and S.D. Sen, “On passive one-way loss measurements using sampled flow statistics”, In IEEE INFOCOM, pp. 197 2946-2950, April 2009. T.A. Inoue, T .; Mano, K .; Mizutani, S.M. Minato, and O.M. Akashi, “Rethinking packet classification for global network view of software-defined networking”, In IEEE ICNP, pp. 199 296-307, 2014. H. Yang and S.J. Lam, “Real-time verification of network properties, using atomic predicates”, in IEEE ICNP, pp. 11-28. 1-11, 2013. A. Srinivasan, T .; Kam, S.M. Malik, and R.M. Brayton, “Algorithms for discretion function manipulation”, in IEEE ICCAD, pp. 92-95, 1990.

  At first glance, this idea of reducing the number of rows in the counter table seems promising. However, since it is a very difficult problem to classify packets for each route in the communication network, there is no high-speed classification technique that can be applied to the current high-speed communication network (see Non-Patent Document 2, for example). ). For this reason, the counter cannot be managed for each route in the communication network, and is managed for each flow as in Non-Patent Document 1.

  An object of the present invention is to make it possible to count traffic without thinning out even if the number of flows is enormous.

  The inventors have discovered that if a data structure called MDD (Multi-valued Decision Diagram) is used, 10 million packets per second can be classified for each route in the communication network (see, for example, Patent Document 1). The present invention uses a data structure called MDD (Multi-valued Decision Diagram) that can classify packets for each route in the communication network, and compares the counter value for each route in the communication network between the switches. To detect.

A communication system according to the present invention includes:
A communication system comprising the switch provided in a communication network to which a plurality of switches are connected and a control device connected to the switches,
The plurality of switches are
A transmission unit that transmits an operation setting table defining an output route for each region in the header space of the packet to the control device;
A path identifying unit that identifies a path in the communication network defined by an area in a header space of a packet by using a maybe decision tree generated by the control device;
A counter table for increasing the counter value of the route specified by the route specifying unit,
The control device is
Obtaining the operation setting table from the plurality of switches, using the operation setting table of the plurality of switches, a bit string defining an area in a header space of a packet as a non-terminal node and a path in the communication network as a terminal node A path derivation unit that generates a decision tree,
A counter evaluation unit that obtains the counter table from the plurality of switches, creates a counter aggregation table, and determines whether or not the counter value for each path in the communication network matches between the switches.

In the communication system according to the present invention,
The route deriving unit
A bit string defining an area in the header space is converted into a binary decision tree, and a path from a root node to each terminal node is common to each path in the communication network assigned to each terminal node of the binary decision tree A binary decision tree generator for generating a binary decision tree that can reach a terminal node of the binary decision tree;
A common decision tree constructing unit for sharing a common non-terminal node of bit sequences among the binary decision trees having different paths and constructing a maybe decision tree from a root node to each terminal node;
A bit aggregating unit for aggregating a plurality of non-terminal nodes adjacent in a path direction of a terminal node from a root node of the maybe-decided tree constructed by the maybe-decision tree building unit into one non-terminal node;
May be provided.

The communication device according to the present invention is
A communication device functioning as the switch provided in a communication network to which a plurality of switches are connected,
An operation setting table that defines an output route for each region in the packet header space;
A path identifying unit that identifies a path in the communication network defined by an area in a header space of a packet by using a maybe decision tree generated by a control device connected to the plurality of switches;
A counter table for increasing the counter value of the route specified by the route specifying unit;
With
The maybe decision tree is configured by using an operation setting table provided in the plurality of switches, and a maybe decision tree having a bit string defining an area in a header space of a packet as a non-terminal node and a path in the communication network as a termination node It is.

The control device according to the present invention includes:
A control device connected to the switch provided in a communication network to which a plurality of switches are connected,
A receiver that obtains an operation setting table that defines an output route for each region in the header space of the packet from the plurality of switches;
Using the operation setting table of the plurality of switches, a path derivation unit that generates a maybe decision tree having a bit string defining an area in a header space of a packet as a non-terminal node and a path in the communication network as a terminal node;
A transmitter for transmitting the maybe decision tree to the plurality of switches;
A counter table in which a counter value is described for each route in the communication network is acquired from the plurality of switches to create a counter aggregation table, and whether the counter value for each route in the communication network matches between the switches. A counter evaluation unit for determining whether or not
Is provided.

The traffic observation method according to the present invention includes:
A traffic observation method executed by the switch provided in a communication network to which a plurality of switches are connected,
The route in the communication network defined by the area in the header space of the packet is specified using a maybe decision tree generated by the control device connected to the plurality of switches, and the counter value of the specified route is indicated in the counter table. A counting procedure to increase,
A transmission procedure for transmitting the counter table to the control device;
In order,
The maybe decision tree is configured by using an operation setting table provided in the plurality of switches, and a maybe decision tree having a bit string defining an area in a header space of a packet as a non-terminal node and a path in the communication network as a termination node It is.

The traffic observation method according to the present invention includes:
A traffic observation method executed by a control device connected to the switch provided in a communication network to which a plurality of switches are connected,
An operation setting table that defines an output route for each region in the header space of the packet is obtained from the plurality of switches, and a bit string that defines a region in the header space of the packet is non-terminated using the operation setting table of the plurality of switches A route derivation procedure for generating a possibly decision tree as a node and having a route in the communication network as a termination node, and transmitting the decision tree to the plurality of switches;
A counter table including a counter value of a path specified by using the decision tree is acquired from the plurality of switches to create a counter aggregation table, and the counter value for each path in the communication network matches between the switches. A determination procedure for determining whether or not,
In order.

  The program according to the present invention is a program for causing a computer to function as each functional unit included in the communication device according to the present invention.

  The program according to the present invention is a program for causing a computer to function as each functional unit provided in the control device according to the present invention.

  According to the present invention, even if the number of flows becomes enormous, traffic can be counted without being thinned out, and a cause location such as a failure can be estimated. In particular, the number of rows in the counter table managed by each switch does not depend on the number of flows.

1 shows an example of a system configuration for managing a counter for each flow. 1 shows an example of a system configuration for managing a counter for each route. An example of the counter totalization table with which a controller is equipped is shown. An example of the traffic monitoring sequence which concerns on Embodiment 1 is shown. An example of the structure of the communication network which concerns on embodiment is shown. An example of the operation | movement setting table | surface with which switch SW _A is provided is shown. An example of the operation of the switch SW _A when the packet header space is expressed in two-dimensional coordinates is shown. An example of the operation | movement setting table | surface with which switch SW _B is provided is shown. An example of the operation of the switch SW _B when the packet header space is expressed in two-dimensional coordinates is shown. It shows an example of the operation setting table provided in the switch SW _C. Shows an example of the operation of the switch SW _C when expressed in two-dimensional coordinate the header space of the packet. An example of a combination of routes in the communication network 83 is shown. It is explanatory drawing of each path | route shown in FIG. It is a block diagram which shows an example of a switch. It is a flowchart which shows an example of operation | movement of a switch. It is a block diagram which shows an example of a controller. It is a flowchart which shows an example of operation | movement of a controller. An example of a route deriving unit is shown. An example of the flowchart which converts a BDD set into one MDD is shown. An example of the BDD structure which concerns on embodiment is shown. An example of the MDD structure which concerns on embodiment is shown. An example at the time of replacing BDD which concerns on embodiment with MDD is shown. An example at the time of combining MDD which shows each path concerning an embodiment into one MDD is shown. An example of the algorithm in the case of combining MDD which shows each path | route which concerns on embodiment of this invention in one MDD is shown. The other example of the algorithm in the case of combining MDD which shows each path | route which concerns on embodiment of this invention in one MDD is shown. An example of the algorithm in the case of performing bit aggregation in MDD which concerns on embodiment of this invention is shown. An example of the algorithm in the case of performing MDD update in MDD which concerns on embodiment of this invention is shown. An example of an algorithm in the case of searching for a route corresponding to a given packet header by tracing the MDD in the MDD according to the embodiment of the present invention will be described. In MDD which concerns on embodiment of this invention, an example in the case of handling a 6-bit packet header by the arrangement | sequence for every 2 bits is shown.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings. In addition, this invention is not limited to embodiment shown below. These embodiments are merely examples, and the present invention can be implemented in various modifications and improvements based on the knowledge of those skilled in the art. In the present specification and drawings, the same reference numerals denote the same components.

(Embodiment 1)
As shown in FIG. 2, the communication system according to the present embodiment includes switches that configure a communication network 81 and a controller 82 that manages each switch. The switch functions as a communication device, and the controller 82 functions as a control device. The controller 82 includes a counter tabulation table as shown in FIG. The apparatus of the present embodiment can be realized by a computer and a program, and can be recorded on a recording medium or provided through a communication network.

  FIG. 4 shows an example of a traffic monitoring sequence according to the present embodiment. The traffic monitoring sequence according to this embodiment includes a route derivation procedure (S301 to S303), a count procedure (S304), and a determination procedure (S305 to S306) in this order.

In the route derivation procedure, the controller 82 acquires an operation setting table from each switch (S301), and generates an MDD and a route list using the operation setting table (S302). The MDD here is probably a decision tree in which a bit string defining an area in the header space of a packet is a non-terminal node and a route in the communication network 81 is a terminal node. Thereby, each switch acquires MDD and a path | route list from the controller 82 (S303).
In the counting procedure, each switch specifies a packet path using MDD, and counts packets for each specified path (S304).
In the determination procedure, the controller 82 acquires a counter table from each switch and creates a counter tabulation table as shown in FIG. 3 (S305), compares the counter value for each path between the switches, It is determined whether or not the counter value for each path matches between the switches (S306).

  In the communication system according to the embodiment, each switch specifies a route in the communication network 81 using MDD. If a data structure called MDD is used, 10 million packets per second can be classified for each route in the communication network (see, for example, Patent Document 1). For this reason, the communication system according to the embodiment can count traffic without thinning out even if the number of flows is enormous.

  First, MDD will be briefly described. This will be described using the example of the communication network 83 shown in FIG. In the present embodiment, “packet behavior” described in Patent Document 1 is expressed as “route” so as to be intuitively easy to understand. “Behavior” is a concept that includes a situation in which routes of packets sent from different switches join in the middle or a packet is discarded. In the present embodiment, “behavior” is referred to as “route” in accordance with the purpose of traffic observation.

The communication network 83 according to the present embodiment is configured by switches SW _A , SW _B, and SW _C. Consider a communication network consisting of three switches A to C each having three interfaces (such as P _A1 ). In FIG. 5, the terminal is omitted. For simplicity, it is assumed that a packet flow can be identified by two 3-bit areas. In other words, it can be considered that a 3-bit transmission address and a reception address are distinguished.

6 to 11 show an example of operation setting in each switch. Each switch receives the packet, identifies the packet by two 3-bit areas, determines an operation corresponding to the packet based on the operation setting table shown in FIG. 6, FIG. 8, and FIG. 10, and executes it. 7, 9 and 11 show the operation of each switch when the header space defined by two 3-bit areas is expressed in two-dimensional coordinates. 6-11, _PA1 etc. show an output route.

  Each switch determines an operation for each region in the header space of the packet. Thereby, an operation setting table for each switch is created. Unlike determining a route that passes through the entire communication network 83, it is easy to determine the operation of each switch. Since the route in the communication network 83 is a combination of operations performed by all switches, it is more complicated than individual operations. In the example of FIGS. 6 to 11, as shown in FIGS. 12 and 13, the packet in the communication network 83 is classified into one of 12 types of routes from I to XII. Combining the operation of each switch, it can be seen that there are 12 types of routes from I to XII in this communication network 83. More precisely, there are more than 12 routes in the graph, but routes where packets cannot flow from the settings of each switch were ignored.

  The role of the MDD is to return a route in the communication network corresponding to the packet flow, given the packet. Thereby, each switch can classify the route of the received packet at high speed, and a counter table based on the route as shown in FIG. 3 can be realized. The input for constructing the MDD is an operation setting table for all the switches shown in FIGS. As output, an MDD and a route list as shown in FIG.

  Subsequently, a traffic observation technique using MDD will be described. A device that manages the entire network 81 shown in FIG. It is assumed that the controller 82 can communicate with all the switches.

  FIG. 14 is a configuration diagram of the switch (the operation setting table is omitted). The switch according to the present embodiment includes a packet transmitting / receiving unit 21, a route specifying unit 22, and a counter table 23.

  The packet transmitting / receiving unit 21 receives the MDD and the route list from the controller 82. The route specifying unit 22 holds an MDD and a route list.

  The operation of each switch in the counting procedure is shown in the flowchart of FIG. When the packet transmitting / receiving unit 21 receives the packet (S201), the route specifying unit 22 classifies the route into the route corresponding to the packet (S202), and the counter table 23 increases the counter value of the corresponding route (S203). The counter table 23 may count the number of packets, but may count the number of bytes. The counter table 23 transmits the updated counter table to the controller 82 via the packet transmission / reception unit 21.

  FIG. 16 is a configuration diagram of the controller 82. The controller 82 includes a packet transmission / reception unit 11, a route derivation unit 12, a counter tabulation table 14, a counter evaluation unit 15, and an alarm generation unit 16.

  The route deriving unit 12 collects information on the operation setting table of each switch from the packet transmitting / receiving unit 11. The route deriving unit 12 constructs the MDD of the communication network 81 using the flow included in the operation setting table of each switch, and sets it in each switch via the packet transmitting / receiving unit 11. Thereby, each switch can specify a route from the header space of the packet in the counting procedure.

  In addition, the controller 82 totals the counter table of each switch to create the counter total table 14, and performs monitoring using this. The operation of the controller 82 in the determination procedure is shown in the flowchart of FIG. The counter tabulation table 14 periodically tabulates the counter table of all switches as in the table of FIG. The counter evaluation unit 15 evaluates the validity of the counter value for each route in the communication network (S102). For example, an evaluation method based on counter value contradiction is considered as follows. If a contradiction is found, the alarm generation unit 16 issues an alarm (S103) and performs a more detailed analysis as necessary.

The counter evaluation unit 15 confirms that the counter of the switch not included in the route is zero. For example, referring to the route R → S in FIG. 3, the counter of the switch SW _{T from} which the packet should not pass is “3” and is not zero. This indicates that the packet is passing through the wrong path, and it is considered that some failure has occurred around the switch SW _T.

The counter evaluation unit 15 confirms that the counters of all the switches on the path match (almost). Looking at the route S → R → T in FIG. 3, the counter value of the switches SW _R and SW _S is “49823”, but the counter value of the switch SW _T is “38294”, and the switch SW _T is the switch SW _R. And SW _S is much smaller. This indicates that many packets are discarded along the route R → T.

The counter evaluation unit 15 confirms that the counter value downstream of the path does not exceed the upstream. Looking at the path T → R of FIG. 3, the larger of the counter value of the downstream of the switch SW _R than the counter value of the upstream of the switch SW _T. This indicates that the packet is illegally generated in the communication network 81.

  Note that because of transmission delays and queuing delays, the counter values do not always match completely between switches. Actually, evaluation is performed in consideration of these delays.

  As described above, according to the present embodiment, the network operator who operates the controller 82 can continuously monitor the traffic using the counter tabulation table 14 and evaluate the validity. In particular, the cause of a failure can be estimated by traffic observation. Thereby, the network operator can confirm that the communication network is functioning correctly.

(Embodiment 2)
In the present embodiment, details of the route deriving unit 12 will be described. FIG. 18 shows an example of the route deriving unit 12 according to the present embodiment. The route deriving unit 12 according to the present embodiment includes a binary decision tree generation unit 121, a maybe decision tree construction unit 122, and a bit aggregation unit 123. The binary decision tree generation unit 121, the maybe decision tree construction unit 122, and the bit aggregation unit 123 execute a maybe decision tree construction procedure.

  The route deriving unit 12 may be realized by causing a computer to function as the binary decision tree generation unit 121, the maybe decision tree construction unit 122, and the bit aggregation unit 123. In this case, each configuration is realized by a CPU (Central Processing Unit) of the controller 82 executing a computer program stored in a storage unit (not shown).

  The binary decision tree generation unit 121 converts the bit string described in the header space for specifying the packet path into a binary decision tree, and the packet path in the communication network assigned to each terminal node of the binary decision tree Each time, a binary decision tree that can reach the end node of the binary decision tree having a common path is generated. The conversion from the bit string to the binary decision tree is performed by, for example, constructing a BDD corresponding to each path of the packet received by the packet receiving unit 11 using the algorithm 3 of Non-Patent Document 3. Specifically, the binary decision tree generation unit 121 according to the present embodiment converts a bit string described in a header space for specifying a packet path into a BDD, and a packet assigned to each terminal node of the BDD For each path, a BDD that can reach the terminal node of the BDD having a common path is generated.

  This BDD set is an input to the maybe decision tree construction unit 122 of this embodiment. Perhaps the decision tree construction unit 122 converts the BDD set into one MDD. Hereinafter, a method for converting BDD into MDD will be described, and finally an algorithm for tracing MDD will be described. The conversion method will be described according to the flowchart shown in FIG.

(About BDD and MDD)
A compressed data structure called BDD and MDD (multi-valued decision diagram) will be described with reference to FIGS. Here, BDD is a binary decision tree, and MDD is probably a decision tree. The binary decision tree generation unit 121 generates the BDD of FIG. 20 from the bit string of the packet header. FIG. 20 is a BDD representing the region I in FIG. The numerical value written in the non-terminal nodes N _{0 to} N ₈ in the BDD represents the bit number of the packet header (the bit number is counted from 0). If the bit is 0, the dotted line is traced, and if the bit is 1, the solid line is traced.

Finally when it reaches the terminal node NE _1, the bit pattern matches the region I. On the other hand, when it reaches the terminal node NE _2, the bit pattern does not match the region I. For example, a path indicated by a thick line in FIG. 20 represents a bit pattern of 01011 * and matches the path of the region I. The fifth bit * in the area I represents a wild card. If a bit is a wildcard, the value of that bit is arbitrary. In this case, the corresponding BDD node is omitted. Therefore, in FIG. 20, B ₅ nodes connected by a solid line in terminal node NE ₁ is omitted. Thus, the bit pattern of the header is represented by the path from the upper node to the lower node. A path on the BDD corresponds to a rectangle in the header space. By following all paths, you can enumerate rectangle rules that do not overlap.

Since BDD performs “compression” by sharing a common “partial path”, the binary decision tree generation unit 121 can compactly express an enormous number of rectangles. For example, the path “01011 *” and the path “01111 *” indicated by bold lines in FIG. 20 share the head portion of 01 and the tail portion of 1 *. This BDD has 14 paths, but can be expressed by only 9 non-terminal nodes N _{0 to} N ₈ .

  As already mentioned, the BDD is constructed for each path in the communication network. FIG. 20 shows only one BDD, but 12 BDDs are constructed to represent the header space of FIG. FIG. 21 is an MDD representing the entire header space of FIG. The MDD in FIG. 21 is probably constructed by the decision tree construction unit 122 from the BDD generated by the binary decision tree generation unit 121.

In MDD, unlike BDD, the type of terminal node is arbitrary, and this time it is associated with a packet path in the communication network. Since there are 12 types of paths in FIG. 12, the end nodes are 12 types from NT _I to NT _XII . In this MDD, K = 2 consecutive bits are combined into one. For this reason, each node has two bit numbers and 0-3 arrows that can be expressed by two bits. A path indicated by a thick line in FIG. 21 represents a bit pattern of “010111”, and reaches the end node NT _I according to the path of the region I. Similar to BDD, MDD also shares a partial path and performs compression. The “size” of BDD or MDD is defined as the number of non-terminal nodes.

(MDD initial construction)
First, the initial construction of MDD will be described. The maybe decision tree construction unit 122 according to the present embodiment constructs an MDD from the root node to each terminal node. The number of bits of the packet header is L, and the L-bit header space is represented as χ = {0, 1} ^L (FIGS. 5 to 11 are L = 3 + 3). A bit pattern representing a header is assumed to be x∈χ.

であれば合致し、

であれば合致しない。この論理関数ｆ_ｉをＢＤＤで表す。たとえば、ヘッダｘ＝０１０１１１は図２０の太線のパスに対応し、

となることで領域Ｉに合致することを表す。 A set of paths and P = {I, II, ··· }, header x is a logical function indicating whether matches the region i∈P and _f i (x).

If so,

If it does not match. The logical function _{f i} expressed in BDD. For example, the header x = 0101111 corresponds to the bold path in FIG.

This indicates that it matches the region I.

を図２２のようにＩ、ｎｉｌに置き換えればよい。 As shown in FIG. 20, it is assumed that all paths f _i , _{ｉ i} ∈P in the communication network are expressed in BDD. Maybe decision tree construction unit 122, the BDD f _i, with all paths from the root node to each end node, by simply converting the MDD F _i without changing the meaning of the function, each terminal node from the root node An MDD is constructed (FIG. 22). Here, F _i (x) is a function for associating the header x with the region i. If F _i (x) = i, the header x matches the region i, and if F _i (x) = nil, it matches. No (nil represents an undefined route). This conversion operation is performed by the terminal node of the BDD in FIG.

May be replaced with I and nil as shown in FIG.

演算を統合演算と呼ぶことにし、次の式（１−１）のように定義する。 (MDD integration)
Next, the decision tree construction unit 122 may unify the MDDs representing the respective routes in the communication network 83 by sharing non-terminal nodes having a common bit string to obtain the MDD of FIG. When two MDDs Fi and Fj are given, if the path of the header x is defined by either F _i or F _j (if it is not nil), it may be associated with that path. like this

The operation is called an integrated operation and is defined as the following equation (1-1).

  Here, an algorithm framework called CASE proposed by Non-Patent Document 4 is used. CASE performs arbitrary “calculation” on two MDDs and outputs a new MDD as a calculation result. An algorithm for calculating Expression (1-1) using CASE is shown in Algorithm 1 in FIG.

Algorithm 1 will be described. Algorithm 1, when both Fi and Fj are terminal nodes, according to formula _(1-1), seek to integrate _F i (x) and _{F j (x), F i} (x) and _F j ( Output the integration of x). If both Fi and Fj is not the end node, in a range of from x 'is 0 ² k -1, _{F i} child node _F i of. child node _F j of the child [x '] and _{F j.} calculate the integration of child [x ′] Let it be child [x ′]. After the calculation is completed, F is output. In the algorithm 1, a part between “/ *” and “* /” is a comment.

By performing this integration operation on all routes in the communication network 83, the entire header space χ can be associated with any route. Let such a function be F. The function F is defined as the following formula (1-2).

次に２回戦

３回戦、と繰り返し、決勝戦を終えるとＦが決まる。ここで、ＭＤＤ Ｆのサイズを｜｜Ｆ｜｜と表記し、非終端ノード数と定義する。 By going to apply repeated integration operations on MDD F _i representing each path in the communication network 83, a set of MDD as shown in FIG. 22 are combined into one MDD shown in FIG. 23. This MDD represents the function F. Because this operation is associative and mathematically commutative, it can be computed in any order. For example, it is possible to select two MDDs in the order shown in FIG. 25 and perform an operation, and finally obtain one MDD representing F. Note that the order shown in FIG. 25 is the tournament table.

Second round

F is decided after repeating the third round and finishing the final round. Here, the size of MDD F is expressed as || F || and is defined as the number of non-terminal nodes.

At the bottom of FIG. 25, the size || F || of MDD F _{i associated} with each path is shown. In this way, by performing operations in order from the smallest MDD, the total amount of calculation can be minimized (the proof is made in Theorem 1 of Non-Patent Document 3). Note that the amount of CASE calculation depends on the MDD size, but does not depend on the number of paths (number of rectangles) included in the MDD.

(Bit aggregation)
The route deriving unit 12 according to the present embodiment preferably includes a bit aggregation unit 123. Up to this point, each node of BDD and MDD has been associated with one bit (as shown in FIGS. 22 and 23). Here, the bit aggregating unit 123 according to the present embodiment aggregates a plurality of bits adjacent to each other in the path direction of the terminal node from the root node of the maybe decision tree constructed by the maybe decision tree constructing unit 122. For example, each terminal node is aggregated in association with a plurality of bits, and the MDD in FIG. 23 is converted into the MDD in FIG. As a result, the path from the root node to the terminal node is shortened, and the path in the communication network 83 corresponding to the packet header can be found in a short time.

This bit aggregation operation is performed by algorithm 2 in FIG. This algorithm, given MDD root node F (where F is not a function, but MDD root node) finds 2 ^K child nodes that are K bits ahead, and sets them as new Set as a child node.

  This calculation is performed recursively to reconstruct the entire MDD. The calculated node is cached so that this algorithm is not repeated for the same node. For example, the root node in FIG. 23 will be described. The child node of K = 2 bits ahead is a node indicated by a bold circle (if the node with bit number 2 is omitted, it is the next node). These are set as new child nodes (the four nodes shown by bold circles in FIG. 23). Further, algorithm 2 is recursively applied to each child node.

Algorithm 2 will be described. In Algorithm 2, when F is not a terminal node or when F is not in the cache, bit aggregation is recursively in the range of x ′ from 0 to 2 ^k −1, and the result is stored in the cache F ^{(K )} Is output.

The MDD reconstructed in this way is represented as F ^(K) . The calculation amount of Algorithm 2 depends on the MDD size, but does not depend on the number of paths (rectangle number) included in the MDD. In the present embodiment, whether or not bit aggregation is performed is arbitrary. For example, when the MDD scale is small, bit aggregation may not be performed.

(MDD update)
The MDD F or F ^(K) constructed as described above as shown in FIG. 23 is updated with the MDD F ′ representing the route in the new communication network 83. In the header space in which the route in the new communication network 83 is defined, X ′ = {xεχ: F ′ (x) ≠ nil}, the route in the new communication network 83 is applied, otherwise the original Leave as it is. At this time, the following calculation may be applied using CASE.

An algorithm for calculating Equation (2) using CASE is shown in Algorithm 3 in FIG. A method for acquiring F ′ will be described. First, as in the method to obtain the _{F i} from _{f i,} obtain the 'F is converted from' f. If F ^(K) is K> 1, the algorithm 2 in FIG. 26 is applied to align K of F ′ with F ^(K) .

を求めて出力する。Ｆ’とＦの両方が終端ノードでない場合には、ｘ’が０から２^ｋ−１の範囲で、

を計算し、計算後のＦ’’を出力する。 Algorithm 3 will be described. In algorithm 3, when both F ′ and F are terminal nodes, according to equation (1-1),

Is output. If both F ′ and F are not terminal nodes, x ′ is in the range of 0 to 2 ^k −1,

And F ″ after the calculation is output.

(Embodiment 3)
In the present embodiment, details of the MDD search in the route specifying unit 22 will be described.
The route specifying unit 22 searches the MDD for the route in the communication network of the packet received by the packet receiving unit 21 according to the bit string described in the header space of the packet, and is assigned to the terminal node reached. Set to. For example, the path in the communication network 83 corresponding to the given packet header x is searched by following MDD F ^{(K) (} algorithm 4 shown in FIG. 28). In this algorithm 4, a bit string of an input header is regarded as an “array” packet header pkt divided into K bits. FIG. 29 shows an example in which a 6-bit packet header is handled in an array of every K = 2 bits. If the packet header pkt [0] is obtained, 0, the first 2 bits (01) are obtained, and the packet header pkt [1], the second and third 2 bits (01) are obtained. In general, the packet header pkt [i] represents a bit string in the range of [Ki, K (i + 1) −1].

  F. b represents the smallest value among the bits associated with MDD node F. For example, since the root node of MDD in FIG. b = 0. The algorithm 4 follows a child node at high speed only by array access, reaches a terminal node, and obtains a packet path in the communication network 83.

Algorithm 4 will be described. Algorithm ^4, the period ^{F (k)} is not a terminal node, x '= packet header pkt ^{[F (k).} b / K] and F ^(k) = F ^(k) . A route search is performed by calculating Child [x ′], and a search result F ^(k) is output.

An example of tracing MDD F ^(K) in FIG. 21 using the packet header in FIG. 29 will be described. First, the root node is F ^(K) . Since b = 0, the packet header pkt [0 / K] = 1, and F ^(K) . F ^(K) is updated by child [1].

This update operation is equivalent to advancing the thick path in FIG. In the next node, F ^(K) . b = 2 and the packet header pkt [2 / K] = 1 is obtained, and F ^(K) . Use child [1] to advance one more path. Finally, F ^(K) . b = 4, packet header pkt [4 / K] = 3, and F ^(K) . child [3] = I, and a route in the communication network 83 corresponding to the region I is obtained. The calculation amount of the algorithm 4 depends on the MDD path length, but does not depend on the number of paths (rectangle number) included in the MDD.

The route specifying unit 22 according to the present embodiment sets the route in the communication network 83 of the received packet to the route assigned to the terminal node reached by searching for MDD F ^(K) . Here, the MDD F ^(K) used by the route specifying unit 22 is constructed by the MDD F ^(K) constructed by the maybe decision tree constructing unit 122 or maybe constructed by the decision tree constructing unit 122 and then aggregated by the bit aggregating unit 123. MDD F ^(K) .

  The packet transmitting / receiving unit 21 may transfer the packet based on the operation setting table, but transfers the packet received by the packet transmitting / receiving unit 21 based on the route in the communication network 83 set by the route specifying unit 22. May be.

  The present invention can be applied to the information communication industry.

11: Packet transmission / reception unit 12: Route derivation unit 121: Binary decision tree generation unit 122: Perhaps decision tree construction unit 123: Bit aggregation unit 14: Counter aggregation table 15: Counter evaluation unit 16: Alarm generation unit 21: Packet transmission / reception unit 22 : Route specifying unit 23: Counter tables 81 and 83: Communication network 82: Controller

Claims (8)

A communication system comprising the switch provided in a communication network to which a plurality of switches are connected and a control device connected to the switches,
The plurality of switches are
A transmission unit that transmits an operation setting table defining an output route for each region in the header space of the packet to the control device;
A path identifying unit that identifies a path in the communication network defined by an area in a header space of a packet by using a maybe decision tree generated by the control device;
A counter table for increasing the counter value of the route specified by the route specifying unit,
The control device is
Obtaining the operation setting table from the plurality of switches, using the operation setting table of the plurality of switches, a bit string defining an area in a header space of a packet as a non-terminal node and a path in the communication network as a terminal node A path derivation unit that generates a decision tree,
A counter evaluation unit that acquires the counter table from the plurality of switches, creates a counter tabulation table, and determines whether or not the counter value for each path in the communication network matches between the switches;
Communications system. The route deriving unit
A bit string defining an area in the header space is converted into a binary decision tree, and a path from a root node to each terminal node is common to each path in the communication network assigned to each terminal node of the binary decision tree A binary decision tree generator for generating a binary decision tree that can reach a terminal node of the binary decision tree;
A common decision tree constructing unit for sharing a common non-terminal node of bit sequences among the binary decision trees having different paths and constructing a maybe decision tree from a root node to each terminal node;
A bit aggregating unit for aggregating a plurality of non-terminal nodes adjacent in a path direction of a terminal node from a root node of the maybe-decided tree constructed by the maybe-decision tree building unit into one non-terminal node;
The communication system according to claim 1. A communication device functioning as the switch provided in a communication network to which a plurality of switches are connected,
An operation setting table that defines an output route for each region in the packet header space;
A path identifying unit that identifies a path in the communication network defined by an area in a header space of a packet by using a maybe decision tree generated by a control device connected to the plurality of switches;
A counter table for increasing the counter value of the route specified by the route specifying unit;
With
The maybe decision tree is configured by using an operation setting table provided in the plurality of switches, and a maybe decision tree having a bit string defining an area in a header space of a packet as a non-terminal node and a path in the communication network as a termination node Is,
Communication device. A control device connected to the switch provided in a communication network to which a plurality of switches are connected,
A receiver that obtains an operation setting table that defines an output route for each region in the header space of the packet from the plurality of switches;
Using the operation setting table of the plurality of switches, a path derivation unit that generates a maybe decision tree having a bit string defining an area in a header space of a packet as a non-terminal node and a path in the communication network as a terminal node;
A transmitter for transmitting the maybe decision tree to the plurality of switches;
A counter table in which a counter value is described for each route in the communication network is acquired from the plurality of switches to create a counter aggregation table, and whether the counter value for each route in the communication network matches between the switches. A counter evaluation unit for determining whether or not
A control device comprising: A traffic observation method executed by the switch provided in a communication network to which a plurality of switches are connected,
The route in the communication network defined by the area in the header space of the packet is specified using a maybe decision tree generated by the control device connected to the plurality of switches, and the counter value of the specified route is indicated in the counter table. A counting procedure to increase,
A transmission procedure for transmitting the counter table to the control device;
In order,
The maybe decision tree is configured by using an operation setting table provided in the plurality of switches, and a maybe decision tree having a bit string defining an area in a header space of a packet as a non-terminal node and a path in the communication network as a termination node Is,
Traffic observation method. A traffic observation method executed by a control device connected to the switch provided in a communication network to which a plurality of switches are connected,
An operation setting table that defines an output route for each region in the header space of the packet is obtained from the plurality of switches, and a bit string that defines a region in the header space of the packet is non-terminated using the operation setting table of the plurality of switches A route derivation procedure for generating a possibly decision tree as a node and having a route in the communication network as a termination node, and transmitting the decision tree to the plurality of switches;
A counter table including a counter value of a path specified by using the decision tree is acquired from the plurality of switches to create a counter aggregation table, and the counter value for each path in the communication network matches between the switches. A determination procedure for determining whether or not,
The traffic observation method which has in order.   The program for functioning a computer as each function part with which the communication apparatus of Claim 3 is equipped.   The program for functioning a computer as each function part with which the control apparatus of Claim 4 is equipped.

Images