flow-based conflict detection

1、Flow-based Conflict Detection in OpenFlow Networks Using First-Order LogicBruno Lopes Alcantara Batista Universidade Estadual Cear(UECE) Fortaleza, Cear, Brazil brunolarces.uece.brGustavo Augusto Lima de Campos Universidade Estadual Cear(UECE) Fortaleza, Cear, Brazil gustavolarces.uece.brMarcial P F

2、ernandezUniversidade Estadual Cear (UECE) Fortaleza, Cear, Brazil marciallarces.uece.brII.RELATED WORKNatarajam et al. 2, identified the hidden conflict problem in an OpenFlow network using FlowVisor. They showed many methodologies to identify and resolve these conflicts. FlowVi- sor is a special-pu

3、rpose OpenFlow controller that acts as a transparent proxy between OpenFlow switches and multiple OpenFlow controllers 3. The methodologies proposed by Natarajam et al. 2 are: Hash-Trie based Conflict Detection (HTCD) and Ontology based Conflict Detection (OCD).Al-Shaer and Al-Haj 4 proposes a tool

4、to find Flow Table misconfigurations using a Binary Decision Diagrams (BDD) technique, called FlowChecker. This approach creates a Flow Table representation in different switches and controllers across distinct OpenFlow federated infrastructures.Dunlop, Indulska and Raymond 5, worked with conflict r

5、esolution for policy-based management system. They showed a brief description of policy model and methods employed conflict detection.Our proposal focus on representing flow conflict using first- order logic and apply this rules in a logical agent that will run in a Prolog engine. It can detect conf

6、licts at Controller in runtime, saving switch resources and minimizing configuration errors in OpenFlow Network. It is different from Natarajam et al. 2, that represents OpenFlow conflicts using a hash table (the HTCD) and a knowledge representation of OpenFlow con- flicts (the OCD) using ontology a

7、nd Web Ontology Language (OWL). The proposal is also different from Al-Shaer and Al- Haj 4, that represent the OpenFlow conflict using a BDD, a compressed description of sets or relations about the OpenFlow rules conflicts.AbstractThe OpenFlow architecture is a proposal from the Clean Slate initiati

8、ve to define a new Internet architecture where the network devices are simple, and the control and management plane is performed by a centralized controller. The simplicity and centralization architecture makes it reliable and inexpensive. However, this architecture does not provide mechanisms to de

9、tect conflicting in flows, allowing that unreachable flows can be configured in the network elements, and the network may not behave as expected. This paper proposes an approach to conflict detection using first-order logic to define possible antagonisms and employ an inference engine to detect conf

10、licting flows before the OpenFlow controller implement in the network elements.I.INTRODUCTIONThe OpenFlow architecture is a proposal of the Clean Slate initiative to define an open protocol that configures the flow tables in OpenFlow switches 1. The OpenFlow creates a basic abstract layer that simpl

11、ifies the network management beyond to achieve better performance over traditional protocols.The network control is performed by the OpenFlow Con- troller, which allows to keep the switches simple, only with the packet forwarding function. In an OpenFlow network, as the number of switches and hosts

12、increases, becomes more complex to manage the flows and facilitates the occurrence of conflicting rules.These inconsistent rules continue to use the switch Ternary Content-Addressable Memory (TCAM), spending an expensive switch resource with a flow that will never be matched. The traditional OpenFlo

13、w architecture does not offer a mechanism of conflict detection in the OpenFlow controller or in the OpenFlow switch.This paper presents a flow-based approach to conflict detection in OpenFlow networks using first-order logic. The first-order logic is used to represent these conflicts. The flows wil

14、l be evaluated by a Prolog inference engine before being applied by OpenFlow controller in the network switches.The rest of the paper is structured as follows. In Section II, we present some related work about policy conflict detection. Section III introduces the OpenFlow architecture. Section IV pr

15、esents the mathematical theory involved and the conflict definitions in first-order logic. In Section V we present an architecture of logical agent written in Prolog. In Section VII we conclude the paper and present some future works.III.OPENFLOW ARCHITECTUREThe OpenFlow architecture has several com

16、ponents: the OpenFlow controller is a centralized entity of OpenFlow network, one or many OpenFlow devices (switch), and the OpenFlow protocol that works as an interface between the controller and the OpenFlow devices setting up the Flow Table.Figure 1 shows the components of an OpenFlow archi- tect

17、ure. This approach considers a centralized controller that configures all devices. Devices should be kept simple in order to reach better forward performance and leaving the network control to the controller.The protocol should use a secure channel based on TLS. The controller updates the Flow Table

18、 by adding and removingconflict and the flow entries with ID 4 and ID 7 is a kind ofdynamic conflict.The static conflicts arise when we create flow entries with erroneous parameters or syntax. For example, the flow entry with ID 5 in Table II is in static conflict because the source and destination

19、MAC address is identical and this simply means that the packet must be treated in the host according to its ARP table.The flows with the ID 4 and ID 7 causes a kind of dynamic conflict. This conflict occurs when two or more well-formed flow entries can simultaneously match a packet. For example, the

20、 host with source IP address sends a packet to destination IP address 0 with the destination port 80 and TCP protocol. What flow entry must be used to match this packet? Is it ID 4 or ID 7 flow entry?Usually, an incoming packet will match with the flow entry with ID 4, because this

21、entry has higher priority than ID 7 flow entry. Now, if the action of ID 4 flow entry is drop the packet, and the ID 7 action is send to port three (output=3), the ID 7 flow entry will never be matched.These conflicts cause the following problems: (1) The network cannot behave as expected due to the

22、 occurrence of the conflicts (Imagine that in case of dynamic conflict, the network administrator wanted the host with IP address can access the host with IP address 0 using the port 80 and TCP protocol); (2) The flow entries are stored in the TCAM flow table inside OpenFlow switche

23、s (TCAM is power hungry, expensive and takes up quite a bit of silicon space);(3) In the Table II we have seven flow entries, four normal flow entries and three conflicting flow entries.We can describe these conflicting flow entries using first- order logic. The Al-Shaer and Al-Haj work 4 introduced

24、 the necessary formalization of OpenFlow flow table. In our proposal, we modify the Al-Shaer and Al-Haj formalization4 to remove the policy abstraction and treat only one flow table, regardless the user/administrator who uses the OpenFlow controller or OpenFlow switch.Definition 1. A Flow Table is a

25、 sequence of flow entries that determine the behavior of OpenFlow switch, as follows:Fig. 1.The OpenFlow architecture. The Controller communicates toSwitch by OpenFlow Protocol over TLS. The OpenFlow Channel receive the OpenFlow message and configure the Flow Table.flow entries using the OpenFlow Pr

26、otocol. The Flow Table is a database that contains flow entries associated with actions to command the switch to apply some actions on a certain flow.A Flow Entry has three parts: header field, counters, and action. The header field is used to define the match condition to a specific flow. Counters

27、are used to count the rule occurrence for management purposes, and action defines the action to be applied to an exact flow.When a packet arrives to the OpenFlow Switch, it is matched against flow entries in the Flow Table, and the action will be triggered if the header field is matched and then upd

28、ate the counter. If the packet does not match any entry in the Flow Table, the packet will be sent to the controller over a secure channel.IV.FIRST-ORDER LOGIC AND OPENFLOW CONFLICT REPRESENTATIONThe tables I and II are representations of a Flow Table. We assume if two or more flow entries have the

29、same priority; the first match will take the precedence.In the Table I, we have four flow entries with no con- flicts. Here, a briefly description of each flow entry, in ID order: (1) Match all packets with destination MAC address FF:FF:FF:FF:FF:FF (broadcast MAC address); (2) Match all packets with

30、 source IP address and destination IP address ; (3) Match all packets with source IP address and destination IP address ; (4) Match all packets with destination IP address 0, protocol is TCP and destination port 80.The Table II was added three more flow entri

31、es. Fol- low a brief description of these new flow entries, in ID order: (5) Match all packets with source MAC ad- dress 78:12:DA:A8:CB:C1 and destination MAC address 78:12:DA:A8:CB:C1; (6) Match all packets with source IP address and destination IP address ; (7) Match all packets w

32、ith source IP address and protocol is TCP.Unused flow entry fields are removed for simplicity. How- ever, these additions to flow entries create some conflicts. In the Table II the flow entries with ID 5 and ID 6 are in static = F1, F2, . . . , FnDefinition 2. A Flow Entry is a set of k-fie

33、lds of filtering F = f1, f2, . . . , fn where n is the length of flow entry fields, that is associated an action ai belonging to the set of possible actions. Thus, a flow entry can be defined in this way:Fi := Ci ai AWhere Ci is the restriction of matching fields that mustbe satisfied to the action

34、ai A can be performed. The Cicondition can be represented as a boolean expression over the value of matching fields fv1, fv2, . . . , fvn, showed in (1):Ci = fv1 fv2 . . . fvn(1)As previously stated, when two or more flow entries has the same priority, the first matching is mandatory, in the other w

35、ords:TABLE I.MATRIX REPRESENTING THE SWITCH FLOW TABLE WITH NO CONFLICTS. ALL THE FOUR FLOW ENTRIES IN FLOW TABLE DOES NOT PRESENTS ANY CONFLICTS IN ITS RULESIDingress-portmac-srcmac-dstether-typevlan-idip-srcip-dstip-protoport-srcport-dst1234*FF:FF:FF:FF:FF:FF*0x08000x08000x08000x0800* 10.0

36、.0.2* 0* TCP* 80TABLE II.MATRIX REPRESENTING THE SWITCH FLOW TABLE WITH CONFLICTS. THE FLOW ENTRIES WITH ID 5 AND ID 6 IS A KIND OF STATIC CONFLICT. THE FLOW ENTRIES WITH ID 4 AND ID 7 IS A KIND OF DYNAMIC CONFLICT.IDingress-portmac-srcmac-dstether-typeip-srcip-dstip-protopor

37、t-srcport-dst1234567* 78:12:DA:A8:CB:C1*FF:FF:FF:FF:FF:FF* 78:12:DA:A8:CB:C1*0x08000x08000x08000x08000x08000x08000x0800* * * 0* * TCP* TCP* 80*In (5), the conflict arises whenthe field matching value_with index 7 (source IP address) is

38、equal to field matchingFa =(C1 C2 . . . Ci) i1value with index 8 (destination IP address) for any flow table entry.iindex(a)_B. Dynamic Conflict NotationThe dynamic conflicts can be expressed as a set of all known conflicts, as follows:Fa =Cj Ciiindex(a) j=1Such that, priority(Ci1) priority(Ci)and i

39、ndex(a) = i | Fi = Ci aThus, the flow table of the switch j can be represented in = 1, 2, . . . , n, n N(6)(2).Suppose that P = p1, p2, . . . , pn is an incoming packet in switch and the pn correspond the current packets header. The dynamic conflict shown in previous section can be defined as follow

40、s:_(j) =Fn(2)nindex(a) =Fi, Fi+1 (j)A. Static Conflict NotationThe static conflicts can be expressed as a set of all known conflicts, as follows:and P is the packet receivediiand fv = then fv = pkkki+1i+1and fv= then fv= pkkkIn (7) the fi is all matching fields values of flow entry with = , n N(3),

41、, . . . , 12kfi+1nindex i andis all matching fields values of flow entrykwith index i + 1. If one of these matching fields values has theEach individual static conflict in (3) can be represented as a boolean statement of field matching restriction. For example, to define the MAC address conflict sho

42、wed in previous Section, the expression could be:symbol * (the OpenFlow wildcard) so replace the with the= fvi+1pk value. After all changes, compare the fields fvi77i+1i+1= fv= fvand fviand fviand fvi = fvi+1. If all88991212statements are true, there is a dynamic conflict. = Fi (j), fv2 = fv3(4)i+1i

43、+1i+1ii+1 12(7)iifv12= fvfvi7 = fv7 fv8 = fv8 fv9= fv9In (4), a conflict occurs when field matching value with index 2 (source MAC address) is equal to field matching value with index 3 (destination MAC address) for any flow table entry.V.LOGIC MODEL-BASED REFLEX AGENT TO DETECT OPENFLOW CONFLICTSTh

44、e proposed logic model-based reflex agent detects Open- Flow conflicts, using condition-action rules and using first- order predicate. = Fi (j), fv7 = fv8(5)states in S and certain possible actions in A. The agents de- signer defines these rules looking for the performance measure that will be appli

45、ed to the agent. In this context, it is expected that, in an environment, if the rules are suitable, the agent will achieve its objectives and, consequently, it will be well evaluated.A. The Model-Based Reflex Agent with Codition-Action RulesThe structure of this agent is a simple reflex agent with

46、condition-action rules 6, with the insertion of a next function used to adapt an internal state to deal with partially observable environments. This new information describes environment aspects (called model) that are not currently perceived by the agents sensors. Specifically, the next state funct

47、ion adapts the current internal state considering the actual information perception and the information about the effects of possible actions in the environment and about how the environment evolves independently of the agents actions.The Figure 2 shows a diagram of the model-based reflex agent that

48、 synthesizes the Russell&Norvigs ideas, related to a reactive agent program 6, as well as the abstract architecture point of view proposed by Wooldridge in 7.B. First-Order Predicate Logic Model-Based Reflex AgentThe literature provides various techniques that may be employed to implement model-base

49、d reflex agents. It suggests some ways to represent information about the state of the environment, the agent actions, and the mechanism to select the agent action 6 7.One possibility is the formal system called predicate logic or if there are uncertainties, an extension of this formalism, such as f

50、uzzy logic and probability. Specifically, the logic agent represents all perceptive information through logical formulas. Its internal state is then a set of sentences of classical first order, and it employs a logical deduction to update its internal state to select its actions.In the context of th

51、e logic model-based reflex agent to detect conflicts between flows, the perception subsystem, see function, captures the information about the flows state,p P , and generates a perception, p0 P 0, that is a set ofwell formed formulas written in predicate logic, expressing the flows stored in the tab

52、le at some moment, during an interactionK. In turn, the next function considers these formulas and adapts the agent internal state, s S.In the context of logic agents, the internal state is seen as a Knowledge Base (KB) that, beyond the formulas about flows, generated in the output of the see functi

53、on (p0), contain formulas that are representations of the information about: the effect of the agents actions, the dynamic of the agents envi- ronment and the condition-action rules. Therefore, considering the current information in KB, the action function deduces the actions a A, i.e., the flows in

54、 conflict and the types ofFig. 2. Model-based Reflex Agent schematic diagram.In addition to the functional description realized in 6 to the simple reflex agent, the description of this new structure adds an intermediate step in the following five steps scheme. This new synthesis assumes that for any

55、 interaction K: (1) Through sensors, the agent receives information from the environment (Env), i.e., perceptions defined on a set of n potential perceptions from the environment, P = p1, . . . , pn;conflicts that are logical consequences of the formulas in the knowledge base. Figure 3 shows a skele

56、ton to program these components.The second part of the LAPS function, after the interpre- tation of the environment state, p, and the generation of the corresponding perception, p0, by see function, and after next function has adapted the knowledge base, KB, specifies theagents action function and the information that are involved in the selection of actions.The agent is capable of deals with the types of con- flict described before. It is not necessary to consider other two kinds of information showed in the Figure 2. In this case, the antecedent of the second if decision structure in