Towards Fog Network Utility Maximization(FoNUM) for Managing Fog Computing ResourcesVladimir MarbukhNational Institute of Standards & Technology100 Bureau Drive, Stop 8910Gaithersburg, MD 20899-8910[email protected]Abstract—Fog computing is an emerging architecture, whichextends the Cloud computing paradigm to the edge of the network,enabling new applications and services, including Internet ofThings (IoT). End users have certain computation tasks, whichcan be completed either locally on the end device or remotely onan accessible Fog node via computation offloading. Due tomobility and highly dynamic nature of end users, the access iswireless with severe physical limitations on the access networkcapacity to sustain stringent latency requirements for streamingand real-time applications for large number of end users overwide-spread geographical area. Also, computationally and storageintensive tasks can be offloaded to centralized cloud over IP corenetwork at the cost of higher communication delay. Efficiency ofoffloading critically depends not only on the wireless access to Fognodes, but also on availability of the computing, storage, control,and networking resources at the Fog nodes. This position paperproposes Fog Network Utility Maximization (FoNUM) forbalancing end user preferences for various Fog services withmobile end user preferences for conserving battery energy toprolong battery lives. We suggest that approximate, pricingbased, distributed solution to FoNUM can be obtained byemploying soft handoff, which allows peripheral devices to connectto several “close” Fog nodes and then customize the offloadingdepending on the specific task resource requirements and resourceavailability at the Fog nodes. Keywords-Fog network;utility maximization;resourcemanagement; pricing; approximation, soft handoff.I.INTRODUCTION Fog computing is an emerging architecture that movescomputation, communication, and storage closer to the endusers [1]-[2]. The emergence of Fog computing is driven byadvent of the Internet of Things (IoT) and enabled by a varietyof powerful end-user, network edge, and access devices withembedded artificial intelligence and 5G communicationcapabilities. These devices include smartphones, tablets, smarthome appliances, small cellular base stations, edge routers,traffic control devices, connected vehicles, smart meters, andenergy controllers in a smart power grid, smart buildingcontrollers, industrial control systems, drones, industrial andconsumer robots, etc.While “Cloud paradigm” assumes moving computing,control, and data storage into the centralized cloud, “Fogparadigm” relies on balancing centralized and local computing,storage, and network management. However, finding the “rightbalance” is a challenging problem due to “very large scale,”highly dynamic nature of IoT, and strong externalities, i.e., sideeffects of local resource management decisions. Recentlydeveloped Network Utility Maximization (NUM) [3]demonstrated feasibility of distributed cross-layer networkoptimization by pricing externalities for balancing userdemands for communication bandwidth.This position paper proposes Fog Network UtilityMaximization (FoNUM) as an extension of NUM [3]. FoNUMbalances end user preferences for various services with mobileuser preferences for conserving battery energy to prolongbattery lives. We argue that approximate, pricing-based,distributed solution to FoNUM can be obtained by employingsoft handoff, which allows peripheral devices to connect toseveral “close” Fog nodes and then customize the joboffloading depending on the job resource requirements andresource availability at the Fog nodes.Figure 1 shows a “bird view” architecture of Fog computingarchitecture [1]-[2].Figure 1. Fog computing architecture.Each mobile device has certain computation tasks, which canbe completed either locally on the mobile device or remotely onthe cloud via computation offloading. Due to mobility andhighly dynamic nature of end users, the access is wireless withsevere physical limitations on the access network capacity tosustain stringent latency requirements for streaming and realtime applications for large number of mobile nodes over widespread geographical area.Assuming wireless access network to be interference limited,we quantify system performance by the aggregate user utility.Optimization of the system computing and communicationresources requires accounting for externalities due toU.S. Government work not protected by U.S. copyright*&&&*OUFSOBUJPOBM$POGFSFODFPO’PH$PNQVUJOH *$’$¥*&&&%0**$’$Authorized licensed use limited to: Macquarie University. Downloaded on October 06,2021 at 00:53:40 UTC from IEEE Xplore. Restrictions apply.interference created by the individual offloading transmissions.While each Fog node can account for the intracell externalities,exact accounting for the intercell externalities in a large-scalenetwork is not feasible due to prohibitive exchange of the“microscopic” information on the intercell interference by endusers. We suggest that approximate, pricing-based, distributedsolution to FoNUM can be obtained by employing soft handoff,which allows peripheral devices to connect to several “close”Fog nodes and then customize the offloading depending on thespecific task resource requirements and resource availability atthe Fog nodes.The paper is organized as follows. Section II describesinterference limited wireless access network to the Fog networkand service model at the Fog nodes, which extends model [4].Given upper limits on the interference at the Fog nodes, the Fogcapacity region is the intersection of the communicationcapacity region of the access network to the Fog nodes andcapacity regions for computing services at the Fog nodes.Extending results [5], Section III shows that the communicationcapacity region of the access network to the Fog nodes can beeffectively evaluated using Perron-Frobenius theory. SectionIV describes Fog Network Utility Maximization (FoNUM)framework as argues that efficient resource allocation in Fognetwork can be achieved with distributed, pricing-basedsolution to FoNUM. Finally, conclusion briefly summarizesand outlines directions of future research.II. COMMUNICATION AND COMPUTING MODELSSubsection A describes interference limited wireless accessto Fog nodes, used by end users for offloading. Subsection Bdescribes computing service model at Fog nodes. Given upperlimits on the interference at the Fog nodes, these models yieldthe feasible region for the offloading rates.A. Access Communication Network to Fog NodesConsider Fog network with S peripheral users and N Fognodes. User i M 1,.., Signal to Interference plus noise Ratioat Fog node n N 1,.., isSINR = p I in in in in n ( ) 2 , (1)wherepin is user i transmission power to node n , in ispropagation gain from user i to Fog node n , n2 is exogenousinterference at node n , and interference experienced by user iat node n from other users j i is1NI = p in jk jn j i k . (2)Expression (2) assumes that each user coordinates hertransmissions to different nodes, thus these transmissions do notinterfere with each other. However, different nodes do notcoordinate transmissions with each other.We assume that user i transmission rate is an increasingfunction of the Signal to Interference plus noise Ratio (1): 2inin nI in in inpr = , (3)where in(0) 0 . Two examples of rate function (3) areShannon capacity:r =W SINR in in log (1 ) 2 , (4)where W is the wireless bandwidth, and threshold capacity:* *0in in ininr if SINR SINRr =otherwise . (5)Threshold-based capacity (5) is an extreme case of a realisticsigmoid rate function of a wireless channel.Given the interference level at the Fog nodes1 1M NI = p n ik in i k , (6)equations (2)-(3) yield end user i transmission power neededfor offloading rate to Fog node n :121( )( )[1 ( )]in inin n nin in inrp Ir , (7)where in 1(.) is inverse of increasing function in(.) . Thus,given interference levels at the Fog nodes (6), the feasibleregion for the offloading rates is as follows:1211 1( )( )[1 ( )]I Nik ikk k ni k ik ik inrI Ir . (8)Note that despite region (8) is not necessarily convex, it can beshown [6] that convexification can be achieved with timesharing between different transmission power vectors.B. Computing Services at Fog NodesWe assume that each Fog node has up to J types ofresources in addition to the communication resources, whichcan be requested by an offloaded task. These additionalresources may include computing resources, memory, networkmanagement resources, etc. Let Bnj be amount of resourcej J 1,.., at Fog node n N 1,.., . We assume that each enduser i M 1,.., can offload up to S classes of tasks. Taskoffloading to a Fog node consumes task class specific mixtureof resources at this node. We model the amount of consumedresources by assuming that offloading of a type s S 1,.., taskat rate r 0 consumes amount src j of type j resource at aFog node.Assuming that system can direct the offloading to differentfog nodes, let rins be user i transmission rate to node n requiredto sustain class s jobs generated by this peripheral. The totaloffloading rate by peripheral i to node n issin insr r . (9)Assuming that resource j capacity at node n is C jn , node ncan sustain demand for this resource if and only ifs s s i c r B j in jn . (10)Authorized licensed use limited to: Macquarie University. Downloaded on October 06,2021 at 00:53:40 UTC from IEEE Xplore. Restrictions apply.In Figure 2, region 0, , ,0 R R in jn s s represents convexifiedfeasible region due to communication constrains (8), region0, , , ,0 A AB B represents capacity region due to limitedresources at the Fog nodes (10). Intersection of these tworegions F B b R 0, , , ,0 sjn represents the feasible region forthe Fog network, given interference levels at the Fog nodes.Figure 2. Feasible and capacity regions for offloading ratesIII. CAPACITY REGIONWhile inequalities (8) determine feasible user offloadingrates for given interference levels at the Fog nodes, this sectionderives communication capacity of a Fog network, i.e., regionof sustainable offloading rates. Subsection A demonstrates thatsolution to “microscopic” system (6)-(7) can be exactlyrecovered from “macroscopic” linear system for interferencesat the Fog nodes. Dimension of this system, equal to thenumber of Fog nodes N , is typically much lower than numberof the end users M : N M . Subsection B gives concisecharacterization of achievable transmission rates in terms ofPerron-Frobenius eigenvalue to the non-negative matrix of themacroscopic system.A. Dimension ReductionMultiplying both sides of (7) by ik , then summing over( , ) i n , and taking into account (6), we obtain the followingequations for interference at base stations Ik , k N 1,.., :121( )( )1 ( )in in ikk n nn i in in inrI Ir . (11)Moving term containing Ik from the right-hand to the left-handside and renaming indices, we obtain the following closedsystem of N linear equations for interferences at base stationsI n , n 1,..,N :1 21in inn k ik k ikn ik ik k n i k iI = I , (12)where11( )( )1 ( )ik ikik ikik ikrrr , (13) k ik ik ( ) ( ) r r i , (14)and r r ( ) ik is vector of transmission rates. After solvinglinear system (10)-(12) for interferences In , user transmissionpowers pns can be recovered with explicit expressions (8).In a case of a single cell, (12)-(13) yield explicit expressionfor interference at the base station21 ( )( )rrI, (15)and end user transmission powers 21( )i srp 11 ( ) [1 ( )]i i ir r i , (16)where11( )i 1 ( ) i ir Ir . (17)B. Perron-Frobenius CharacterizationAccording to (16)-(17), capacity region of a single-cellsystem is given by111i 1 ( ) i iM r . (18)In a case of Shannon capacity (4),ni 1( ) 2 1 r r W ni , (19)and thus sustainability condition (18) takes the following form:1 2 r W siM . (20)In a case of threshold-based capacity (5), *in*in1( )inr 0 0SINR if r rif r, (21)and thus, sustainability condition (18) takes the following form:*11i 1 iMSINR . (22)For a multi-cell system, n(r) 1, n 1,..,N , (23)where n(r) are given by (13)-(14), is generally a necessarybut not sufficient condition for sustainability of rates r r ( ) in .Assuming conditions (23) are satisfied, in the rest of thissubsection we concisely define the Fog communicationcapacity region in a general case of multiple Fog nodes: 2n( , ) ( , )nm s n k ms msnknk : 0:r p r =p $ nnk nk p # ! ” . (24)Our analysis is based on observation that equations (12) form0 sriFAabˆ Fˆ FbjnBAB srABˆ s R jnsRinsR jnˆ sRinAuthorized licensed use limited to: Macquarie University. Downloaded on October 06,2021 at 00:53:40 UTC from IEEE Xplore. Restrictions apply.a linear system:I A(r)I b(r) , (25)where matrixA r A r ( ) [ ( )] nk n k N, 1 has non-negativecomponents1( ) ( )1 ( )innk ik ikn ik iA r = rr , (26)if n k , and 0Ann , and column vector b (bn)nN1 haspositive components1 2( ) ( )1 ( )inn k ik ikn ik k ib r = rr . (27)According to (7), transmission rates r r ( ) in can berealized with finite transmission powers if and only if system(25)-(27) has non-negative solution In ” 0 , n 1,..,N , i.e.,R r I I A r I b r ˆ ! ” { : 0: ( ) ( )}. (28)It is known [6] that capacity region (28) can be characterized interms of Perron-Frobenius eigenvalue of matrix A(r) withcomponents (26), % %(r):% & ‘ s rins 1 (29)complemented with conditions (23). Conditions (23), (29)provide a concise Perron-Frobenius characterization of systemcommunication capacity region (24), which is open andgenerally non-convex. Convexification of the capacity region(23), (29) can be achieved with time sharing between different transmission power vectors [6].0, , , , ,0 s sIn Figure 2 regionR a b R in jnrepresents this convexified communication capacity region. Intersection of the convexified communicationcapacity region and resource capacity region at the Fog nodes0, , , ,0 A AB B represents the overall Fog capacity region Fˆ .We conclude this subsection by noting that approximationsand bounds on the Perron-Frobenius eigenvalue %(r)immediately lead to the corresponding approximations andbounds on the Fog communication capacity region (24). Forexample, it is known [6] that( ) max ( ) k n nknr A r% , (30)and thus, condition1 max1 ( )r inik iknn ik k n ir (31)supplemented with (23) guarantee (29), and thus determine lowbound on the Fog communication capacity region (24). Alsonote that in a case of a single cell N 1, conditions (23) and(31) the Fog communication capacity region (24).IV. FOG NETWORK UTILITY MAXIMIZATION (FONUM)System operation inside capacity region close to its boundaryresults in high level of interference and thus requires high levelof transmission powers. Since for mobile end users,transmission power is inversely related to battery lifeexpectancy, mobile users should balance their preferences forthe offloading rate on the one hand and prolonging the batterylife on the other hand. Subsection A introduces user utilityfunctions which quantify this tradeoff. Assuming that overallFog performance is characterized by the aggregate utility,subsection B demonstrates inefficiency of selfish user utilitymaximization. This inefficiency is due to strong negativeexternalities of the offloading decisions by individual end users.Subsection C discusses possible distributed implementation ofFog Network Utility Maximization (FoNUM), which is basedon approximate pricing of these externalities.A. User and System Performance CriteriaWe assume that end user i preference for class s service canbe quantified by increasing utility function v r is i ( ) s , wherevis(0) 0 . Specific form of end user utility as a function oftransmission rate in a case of computation offloading have beendiscussed in literature, e.g., see [8]. Here we only note that in acase of services which do not require minimum bandwidth, e.g.,file transfer, this function is concave: v v r 1( ) , as shown inFigure 3. In a case of real-time, e.g., streaming, services, whichrequire minimum bandwidth, this function has a sigmoid shape:v v r 2( ) , as shown in Figure 3.Figure 3. User utility of offloadingWe assume that the aggregate utility of user i offloadingservices s S 1,.., at rates r r s S i is s : ( , 1,.., ) is additive:1i i i i ( ) ( ) s s s Ssv r r( . (32)Mobile end user i balances preference for high offloading ratewith incentive for prolonging the battery life which translates tolower transmission power pi . We model this balance byincluding penalty f p i i ( ) in user i utility as follows:i i i is i i i ( , ) ( ) ( ) s ssu r p v r f p , (33)where f p i i ( ) is an increasing and convex function, fi (0) 0and f p i i ( ) ) * as pi ) *. Penalty function f p i i ( ) issketched in Figure 4.0rv r 1( )v r 2( )v r ( )Authorized licensed use limited to: Macquarie University. Downloaded on October 06,2021 at 00:53:40 UTC from IEEE Xplore. Restrictions apply.Figure 4. Penalty due to battery depletingFunctionf p 1( ) describes mobile user with less remainingbattery energy than function f p 2( ) describes.B. Inefficiency of Selfish OptimizationIn selfish optimization, each peripheral user i I + selfishlymakes offloading decisions in an attempt to maximize hersindividual utility (33), given interference levels at the Fog nodesnI . Substituting expression (3) for the offloading rate rin inuser i utility (33), we obtain the following expression for theuser utility i as a function of the transmission power, giveninterference levels at the Fog nodes In : ( )U p I v 2p ss in ini in n is in ss n n in in nsi inn sI pf p (34)Thus, user i selfish optimization takes form of utility (34)maximization over transmission powers pin s , s S 1,.., ,n N 1,.., 
)max ( )sinsi in npU p I . (35)subject to resource capacity constraints (10).Optimization (35) in a case of inactive capacity constraints(10) is shown in Figure 5 in a typical case of sigmoid ratefunction (3).Figure 5. Utility: offloading vs. battery depleting, I I I 1 2 3 Increase in the user transmission power benefits user utility forsufficiently small transmission power due to increase in theoffloading rate. However, for large transmission power,detrimental effect due to high battery energy expendituredominates. Given interference level I , the optimaltransmission power p I *( ) is a decreasing function of I .Since interference levels at the Fog nodes In depend ontransmission powers by all interfering end users:1 1 1I p = p n in in ( ) i k s M N S s , (36)selfish user optimization can be naturally interpreted withingame-theoretic framework. If fixed-point equations (6), (35)converge, the corresponding selfish equilibrium is a pureequilibrium of the corresponding game. Since U p I ( ) 0 , asp ) 0 , system avoids “power warfare,” i.e., unlimited increasein the transmission powers by end users competing for wirelessbandwidth. Still, selfish equilibrium may be highly inefficientsince “more transmission power challenged” end users withpenalty function f p 1( ) in Figure 4 may be completely starvedfrom offloading by “less transmission power challenged” endusers with penalty function f p 2( ) in Figure 4.Assuming that overall performance of Fog network ischaracterized by the aggregate utilityU p I p U p I p ([ ( )] [ ( )] i i in n s , (37)a natural goal for Fog resource allocation is maximization ofthis aggregate utility:max0max [ ( )]pU U p I p ( (“(38)subject to resource capacity constraints (10).We call optimization problem (38)-(10) a Fog NetworkUtility Maximization (FoNUM) and quantify inefficiency ofselfish optimization by the corresponding Price of Anarchy(PoA):PoA U U * max * 1” ( ( , (39)where U *( is the aggregate utility (37) at the selfishequilibrium. The inefficiency of selfish optimization is due tonot accounting for externalities due to interference at the Fognodes, which may eliminate some users from offloading. Sinceexact accounting for the externalities in a large-scale Fognetwork is not feasible, in the next subsection we propose someapproximations.C. FoNUM: Towards Distributed Solution through PricingFollowing NUM framework, FoNUM accounts forexternalities by imposing social costs on the users for thecreated externalities. The corresponding user i net utility is:, ,i in in i in i in nj j n in ( , ) ( , ) s s s s s sn s j n sw r p u r p r g c q p , (40)wheregnj is the marginal social cost of using of an unit ofresource j capacity at Fog node n , and qn is the marginal0p* 1p* 2p* 3pU p I ( ) 1U p I ( ) 2U p I ( ) 3U p I ( )U I U p I I * * ( ) ( ( ) )Authorized licensed use limited to: Macquarie University. Downloaded on October 06,2021 at 00:53:40 UTC from IEEE Xplore. Restrictions apply.social cost of a unit of interference at Fog node n .User i I + maximization of its net utility (40): 2,pmaxswp( 0)inI p sin in si in in spn in in n” (41)yield solution, which depends on the costs gnj and qi . Theproblem is finding the socially optimal costs, such thatindividual user net utility maximization (41) yields solution toFoNUM (37)-(38). In the rest of this subsection, we suggestthat these socially optimal costs can be determined adaptivelyas an implementation of the demand/supply principle: costincreases (decreases) as resource supply decreases (increases).Following [10], we consider algorithm which proceeds indiscrete time t 0,1,2,.. . We assume that each Fog noden N 1,.., measures the aggregate demand on the typej J 1,.., resource at this node at time tR t c r t jn j in ( ) ( ) s i s s (42)and evaluates the excess over available capacity Bjn :R t B jn jn ( ) . Following demand/supply law for resource j atnode n , the marginal social cost of using of an unit of resourcej capacity at Fog node n evolves as follows:g t g t h R t B nj nj t jn jn ( 1) ( ) ( ( ) ) , (43)where – . x x max( ,0) and some sufficiently small ht 0 .We also assume that each Fog node n N 1,.., estimatesinterference at this node at time t , I t n( ) , and evaluates theexcessive interference over predetermined ermined target levelnI, I t I n n ( ) . Following demand/supply law for the wirelessbandwidth at node n , the marginal cost of a unit of interferenceat Fog node n evolves as follows:q t q t h I t I n n t n n ( 1) ( ) ( ( ) ) . (44)After costs (43)-(44) are communicated to users, these usersdetermine Fog nodes to connect to and the transmission powersby solving their individual optimization problems (40)-(41).The first issue with this algorithm is convergence for ht , 0as t /* . The convergence can be expected based onconvergence of similar algorithms in simpler situations [10].However, for a Fog network, relevance of convergence isquestionable due to arrivals/departures and mobility of endusers. More relevant is an adequate ability to combine nearoptimal performance under steady scenario with adaptabilityunder reasonable dynamic scenarios for sufficiently small butfixed 0h h t . The second issue is selection of upper limitsof interference levels at the Fog nodes In , n N 1,.., in (44).In accordance with FoNUM framework, this selection shouldbe able to approximate solution to optimization problem (37)-(38). The third major issue is practically implementable strategyof updating end users on the costs (43)-(44) since only usersexpected to initiate soft handoff should be updated on the realtime costs (43)-(44) of the resources and interference at the“neighboring” Fog nodes. We outline possible ways to addressthese issues in the next section.V. CONCLUSION AND FUTURE RESEARCHEfficient balancing of the centralized and local computing,storage, and network management in emerging Fog computinginfrastructure requires accounting for the externalities createdby offloading decisions made by individual end users. Thisposition paper suggests Fog Network Utility Maximization(FoNUM) for balancing various tradeoffs in Fog networks foreach end user as well as across different users. FoNUM extendsconventional Network Utility Maximization (NUM), whichsolves this problem in a case of communication resources.We plan give recommendations on parameter ht in (43)-(44)under realistic simulation scenarios. Selecting “near-optimal”target interference levels at the Fog nodes In , n N 1,.., aswell as updating end users on the costs (43)-(44) requiresevaluation of the long-range intracell externalities in near realtime. Physical limitations on the wireless bandwidth createinherent tradeoffs between accuracy of the Fog managementinformation and Fog ability to handle payload. One mayenvision a scheme which adapts frequency of updates of theimplied costs according to the importance and rate of change.We plan investigation of such scheme by employingmethodology of learning algorithms for soft handoff withrecently emerged concept of the Age of Information (AoI) [11].REFERENCES[1] F. Bonomi, R. Milito, P. Natarajan, J. Zhu, “Fog computing: A platformfor Internet of Things and analytics” in Big Data and Internet of Things:A Roadmap for Smart Environments, Cham, Springer, pp. 169-186, 2014.[2] M. Chiang and T. Zhang, “Fog and IoT: an overview of researchopportunities,” IEEE Internet of Things Journal, Vol. 3, No. 6, 2016.[3] M. Chiang, S. H. Low, A. R. Calderbank, J. C. Doyle, “Layering asoptimization decomposition: A mathematical theory of networkarchitectures”, Proc. IEEE, vol. 95, no. 1, pp. 255-312, Jan. 2007.[4] V. Marbukh, “Towards Efficient Offloading in Fog/Edge Computing byApproximating Effect of Externalities,” 2nd Workshop on IntegratingEdge Computing, Caching, and Offloading in Next Generation Network,IEEE Infocom, San Francisco, 2018.[5] S.V. Hanly, “Congestion measures in DS-CDMA networks,” IEEE Trans.on Communications, Vol.: 47, Issue: 3, Mar 1999.[6] W. Yu and J. Yuan, “Joint source coding, routing and resource allocationfor wireless sensor networks,” IEEE ICC 2005.[7] Meyer, Matrix Analysis and Applied Linear Algebra, SIAM, 2000.[8] X. Chen, “Decentralized computation offloading game for mobile cloudcomputing,” IEEE Trans. on Parallel and Distributed Systems, 2014.[9] X. Lin, N.B. Shroff, and R. Srikant, A Tutorial on Cross-LayerOptimization in Wireless Networks, IEEE Journal on Selected Areas inCommunications, Vol. 24, No. 8, August 2006.[10] M. Costa, M. Codreanu, and A. Ephremides, “On the age of informationin status update systems with packet management,” IEEE Trans. Inf.Theory, vol. 62, no. 4, April 2016, 1897–1910.Authorized licensed use limited to: Macquarie University. Downloaded on October 06,2021 at 00:53:40 UTC from IEEE Xplore. Restrictions apply.
