1、Toward Systematic Detection and Resolution of Network Control ConflictsDennis VolpanoDepartment of Computer Science Naval Postgraduate School Geoffrey G. XieDepartment of Computer Science Naval Postgraduate SXin Sun School of Computing & Information SciencesFlorida Inter

2、national UABSTRACTThe problem of detecting and resolving control conflicts has started to receive attention from the networking commu- nity. Corybantic 16 is an example of recent work in this area. We argue that it is too coarse grain in that it does not model the combined o

3、perational objectives of multiple controller functions. This paper proposes a finer grain ap- proach where a network control function is represented as a deterministic finite-state transducer. The machine runs on inputs provided by an SDN controller and outputs instruc- tions that update the network

4、 as needed to meet objectives. Standard proof techniques and algorithms can be leveraged to analyze properties of these machines. Specifically, their intersection describes precisely the stable operating region of a network when the machines operate in parallel. The stable region comprises condition

5、s under which no control function is in the process of updating the network.of operational objectives, such as power manager 9, load balancer 1, bandwidth allocator 2,17, application control manager 5, and virtual machine (VM) migrator 7, 15.The proliferation of single-objective controller functions

6、 is both encouraging and daunting. On the one hand, it has successfully elevated the level of abstractions for network operation from device-level configuration to service-level re- quirements. On the other hand, it fosters independent devel- opment of functions that can interact in unpredictable wa

7、ys and de-stabilize a network. For example, consider the net- work in Figure 1. Suppose the operator runs two controller functions: one aims to balance load per destination across links v and w, and the other aims to turn off E if its un- der utilized (assuming that E consumes more power than F). Th

8、e power-save function is at odds with the load-balancing function. The latters objective is to balance load even if traffic is light at each router. So both routers must remain on. The power-save function will see this as an opportunity to shift flows to F and turn off E, which can trigger load bala

9、ncing to turn it back on. So even under constant op- erating conditions, power to E can flipflop indefinitely with these two functions. This is an example of oscillation caused by multiple functions. Oscillation can also occur within a single function under constant conditions. This may be due to po

10、or design or be intentional. For instance, the function may be implementing a circular scheduling algorithm for access to a shared medium like a software-defined wireless access network. We consider here oscillation caused by mul- tiple functions. This kind of oscillation is also a challenge for net

11、work functions virtualization (see pg. 11 of 4).The problem of detecting and resolving control conflicts has started to receive attention from the networking com- munity. Corybantic 16 is an example of recent work in this area. However, Corybantics approach is too coarse grain in that it avoids mode

12、ling combined operational objectives of competing controller modules. For example, when mul- tiple modules propose actions in response to an event suchCategories and Subject DescriptorsC.2.3 Computer-Communication Networks: Network Operationsnetwork management; D.2.4 Software Engi- neering: Software

13、/Program Verificationformal methods, correctness proofsKeywordstransducers, SDN, controller function interaction1.INTRODUCTIONBy making the control plane programmable and centraliz- ing it, software defined networking (SDN) builds upon well- established software development principles such as modula

14、r design and open APIs in an attempt to contain the growing complexity and cost of network management. In the last five years, a number of network controller functions have been conceptualized, each of which targets a single or narrow setApproved for public release; distribution is unlimited.Fw(c) 2

15、014 Association for Computing Machinery. ACM acknowledges that this con- tribution was authored or co-authored by an employee, contractor or affiliate of the United States government. As such, the Government retains a nonexclusive, royalty- free right to publish or reproduce this article, or to allo

16、w others to do so, for Govern- ment purposes only.HotSDN14, August 22, 2014, Chicago, IL, USA. Copyright 2014 ACM 978-1-4503-2989-7/14/08.$15.00./10.1145/2620728.2620745.vEFigure 1: Unequal cost (power) load balancing67des)na)onas a significant load increase over a link, Corybantic u

17、sesa policy-based approach to select only one of the proposals to implement. This approach is suboptimal from the per- spective of meeting operational requirements because a) it discards possible solutions where multiple proposals with- out conflicts may be implemented at the same time; and b) it re

18、quires each controller module to determine the accept- ability of the winning proposal (from another module) with an abstract currency that does not accurately measure how well the module will be able to meet its own objective.A finer grain approach to detecting and resolving control conflicts is ne

19、eded. There are two important requirements. First, a uniform representation of the operational objectives is needed in order to reason about the joint effect of multiple controller functions (Corybantic introduces an abstract cur- rency for this purpose). Second, a controller function should be repr

20、esented in a way that facilitates formal reasoning and makes key problems decidable. To this end, we propose a new programming model for SDN controllers that is quite different from current practice. The controller executes only code that is produced algorithmically from operational ob- jectives exp

21、ressed independently of one another. The code continuously observes the network and adjusts it in real time as needed to satisfy the requirements. Properties of the code are proved under the assumption that only the code can change the network. For instance, we might be able to show that there will

22、never be an attempt to shift load to a router that is off. But if other controller code can power down devices then theres no guarantee. Therefore, no manually- written controller code using APIs like POX 12 is allowed, nor is application-level access to network resources like that provided by PANE

23、5.In the next section, we describe a finer grain approach to treating conflicts among operational objectives. Examples are given for controlling power and load balancing. We show how the approach can also be used to control a single device, namely a MAC-learning switch. Then we discuss tradeoffs of

24、the approach in Section 5, followed by related and future work in Sections 6 and 7.ZvLw ZvZwLvLw, LvZwr3; r1; r2; OEHZvHwZvLw ZvZw Hr5; OnEHZvHwr0; r4; HvLw, HvZw, LvHw, HvHwHFigure 2: Link-local power-save transducernetwork in advance to give an operator a sense of how their network can behave. Thi

25、s comes from analyzing the inter- section of DFTs. With proper handling of their output func- tions, they can be intersected through a standard product construction. An operator then gets a picture of what we call the stable operating region of the network under the intersec- tion. This is the set o

26、f conditions under which no controller function is attempting to alter the network. Depending on how narrow the region is, a decision can be made about whether to deploy the functions simultaneously. One can ex- periment with different combinations of controller functions to see the stable regions t

27、hey produce. Resolving conflicts translates into choosing the right mix of machines or even tuning them in order to achieve an acceptable stable region. Moreover, useful properties of an intersection are obtained for “free” from properties of the constituent machines. As we shall see, the invariant

28、for a state (p, q) of an intersec- tion is obtained by merely conjoining the invariants proven separately for states p and q in their respective machines.2.1Modeling a power-save functionConsider the network in Figure 1. Assume each link ex- hibits a utilization rate that can vary over time. This ra

29、te can be sampled on each cycle and is either high (H), low (L) or zero (Z). Suppose a power-save machine tries to power down E when the link utilization of links v and w is low or zero for two consecutive cycles.1 Any new flows are then routed to F. A DFT runs on a sequence of input symbols. Here e

30、ach symbol reflects the utilization rates of both links v and w at the end of a cycle. For instance, HvLw is a symbol that denotes a high and low utilization of v and w respectively. Therefore the input alphabet of the machine is2.A FINER GRAIN STRATEGYWe propose a controller function be modeled as

31、a deter- ministic finite-state transducer (DFT) 8. A DFT is a prim- itive computing machine that runs on inputs, computed by an SDN controller, and outputs a sequence of instructions to change the network as needed to meet the functions ob- jective. The inputs are measurements and other parameters o

32、f a running network suitably discretized for the machine. They include link utilization, end-to-end bandwidth require- ments, flow-to-path assignments, etc. Inputs are supplied once per “cycle” to a machine. The machine transitions ac- cordingly and may produce output that changes network configurat

33、ion in some way. The minimum period of a cycle is determined by the SDN controllers ability to refresh the measurements during that time. With one transition per cycle, the machine has a crude form of clock that is useful for implementing timeouts.The advantage DFTs is that one can analyze propertie

34、s of them and their intersection to understand the scope of interaction between controller functions. Important proper- ties are decidable for these machines such as whether two machines have a nonempty or finite intersection. It is possi- ble to precisely describe the scope of interaction for a giv

35、en = Hv, Lv, Zv Hw, Lw, Zw.The power save transducer for the network in Figure 1 isgiven in Figure 2; in a slight abuse of notation, H stands for all symbols of containing H. The output function produces the empty output for all states except r2 and r5 where it outputs OffE and OnE. The machine wait

36、s for two consec- utive cycles where link w is experiencing heavy load beforerestoring power to E. The final states r0 and r3 represent 1The choice of two cycles is completely arbitrary. It can be whatever an operator wants.68stable operating states for the network where the machine is not in the pr

37、ocess of possibly powering down E. For r3, E is powered down with low use of w, and for r0, both routers are powered up with one or both links experiencing high usage. Precisely, the following invariants can be shown for these states by a straightforward mutual induction on the length of input w:ZvH

38、wq1; LvHwq4; F to EZvHw LvHwBBq5; Bq0; 1. the power-save transducer is in r0 on input w with output y only if w ends with a member of H and y ends with OnE, and2. the power-save transducer is in r3 on input w with output y only if w ends with ZvLw or ZvZw and y ends with OffE.BHvZw HvLwZvHw LvHwBBq3

39、; E to FBHvZw HvLwq6; q2; It may seem curious that transitions are possible out ofr2, r3 and r4 with heavy load over v when E is supposedly powered off in those states. The machine has been designed this way because the attempt to turn E off may have failed or been overridden. Thus it treats OffE (a

40、nd OnE) more as a request than a command. Alternatively, it could be treated as a command and re-tried until it succeeds, a retry maximum is reached, or conditions have changed making it unnecessary. Power status would have to be added to the input stream in this case. So the power-save function can

41、 be modeled in many different ways. In fact, the decision to disable a router can push downstream link utilization rates higher. So a link-local approach such as the one described here may be unacceptable. A path-based approach is con- sidered in Section 3.Figure 3:Load balancing transducerand w is

42、not experiencing high usage. So the stable region for the network is the disjunction of the conditions for these two states.Note that low utilization of both links can cause oscillation since low, yet nonzero, usage of both links is not part of the stable operating region produced by the product. To

43、 see this, suppose powering off router E causes high utilization of link w. Then starting from the start state r5q0, state r1q0 is revisited on inputLvLw LvLw ZvHw ZvHw ZvHw LvLwAll but the first symbol of this input will repeat indefinitely if both links have low usage whenever both routers are on

44、(see red path in Figure 4). It is a subtle consequence of the machines interacting of which an operator should be aware. Now suppose an operator is later asked to provide redun- dancy in the network by ensuring both routers are always on. On the surface, this certainly appears to be at odds with pow

45、er saving but by how much? Will the network be completely inoperable because of these competing concerns? It may not because the answer depends on how the network normally operates. All we can safely say is that the stable operating region will likely be narrowed. To illustrate, con- sider the redun

46、dancy transducer in Figure 5. Theres only2.2Modeling a load-balancing functionSuppose we also want to balance load per destination across links v and w of the network in Figure 1. The load balancing transducer for this network is given in Figure 3. It has the same input alphabet as the power-save tr

47、ansducer; B stands for symbols representing a load-balanced network:HvHw, ZvLw, LvLw, LvZw, ZvZwThe only stable state is q0 for which it can be shown that the load balancing transducer is in this state on input w with output y only if w ends with a member of B and y is empty or ends with F to E or E

48、 to F; the former means move flows from F to E and the latter from E to F. This machine remains in states q3 and q4 waiting indefinitely for the balance to occur when in practice, a machine would wait until there is a balance or a timeout occurs.1/106 2/20 1/10 !$#3%7 89 )1/.062/.02.3The intersectio

49、n transducer !,#$%-)!*#$%+1/2062/10We want to know the stable operating region for the net- work in Figure 1 under the power-save and load-balancing machines. How narrow is this region? The intersection, or more precisely the product, of the machines is computed for this purpose. A portion of the pr

50、oduct is shown in Figure 4. It has a total of 13 reachable states with two final (stable) states, namely r0q0 and r3q0 (not all transitions from r0q0 and r3q0 are shown). From the invariants above, we know that the product is in state r0q0 on input w only if w ends./.01/102/.0!$#$%+!#$%()!,#,%-)./.0

51、./.02/.02/.02/202/1062/20!5#$%+!3#4%+with a member of H B which is just HvHw. This tells2/10us that the product will be in this stable state only when the utilization rates of both v and w are high. It will be in stable state r3q0 only if w ends with ZvLw or ZvZw, that is, when link v is not being u

52、sed, perhaps because E is off,Figure 4: A portion of the product machine for the power save and load balancing transducers69one stable state, s0, and it requires nonzero load on both links to remain in it. So the product of all three machines has only one stable state, namely r0s0q0, and it requires

53、 high utilization of links v and w to stay there. This condition may be too narrow to be a useful stable region. However, the point here is that we discovered there is a network condition under which all three machines can co-exist without causing any oscillation.P1P2EP33. PATH-BASED POWER SAVINGThe

54、 power-savetransducerintheprecedingsectionworks at the granularity of links. Alternatively, we can use trans- ducers to model controller functions at the granularity of forwarding paths, for instance, if the network deploys an MPLS like traffic engineering solution. We sketch here one approach to a

55、path-based transducer for power saving. Like ElastricTree 9, it treats path capacities and flows in its decision to alter power.Consider the network in Figure 6. There are three possible paths to the destination, P1, P2 and P3. Every flow in the network is assigned to a path and consumes a portion o

56、f the available bandwidth for that path. As long as all flows can be serviced by P1 without forcing any flows consumption below what it expects, router E can go dormant.Inputs to the path-based transducer contain three ele- ments: the current flow-path assignments, the bandwidth each flow is current

57、ly experiencing and the utilization of each path. To represent the latter two, we assume the network is instrumented to produce totally-ordered symbols Z, L andH. In the case of bandwidth, each is a range in which a flows bandwidth lies during a cycle. The ranges may vary across flows because what m

58、ight be a high range for one may be low for another depending on their service-level agreements. There is another set of ranges for utilization which reflect level of path usage in a cycle. For example, below is an input symbol for the network in Figure 6 with two flows:(P3, P1, L, H, Z, Z, L)The first two elements convey flow-path assignments, the next two convey current bandwidths ex