# Fault-Aware Resource Allocation for Heterogeneous Data Sources with Multipath Routing

Authors: Xiaomei Zhang; Qiang Chen; Zhicai Shi; Jianru Liang
Journal: Scientific Programming
 (2017)

---

## Abstract

With the rapid development of cloud computing and big data, diverse types of traffic generated from heterogeneous data sources are delivered throughout communication networks, which consist of various node kinds such as digital sensors and smart actuators, and different applications. Due to the shared medium, communication networks are vulnerable to misbehaving nodes, and it is a crucial aspect to maintain an acceptable level of service degradation. This paper studies the fault-aware resource allocation problem by exploiting multipath routing and dynamic rate assignment for heterogeneous sources. We estimate the impacts of faults and formulate the resource allocation as a lossy network flow optimization problem based on these estimates. The traditional flow optimization solutions focus on homogeneous traffic. In our work, we model the performance of heterogeneous applications as a relaxed utility function and develop an effective utility framework of rate control for heterogeneous sources with multipath routing in presence of misbehaving nodes. We design a distributed algorithm to decide the routing strategy and obtain the rate assignments on the available paths in a lossy utility fair manner. Extensive performance evaluations corroborate the significant performance of our algorithm in effective utility and utility fairness in the presence of misbehaving nodes.


---

## Body

## 1. Introduction

With the rapid development of cloud computing and big data, communication networks where a wide variety of devices can be connected are increasingly used in data-intensive applications, such as video surveillance, robots, industrial process control, and mobile entities [1]. Various types of traffic generated from heterogeneous data sources have increasing growth in demand for efficient transmission services, for example, traditional data, audio, video, and multimedia delivery through the network [2]. Different quality-of-service (QoS) requirements of these services are specified in the form of application performance metrics, which are not easy to be guaranteed in the homogeneous network service architecture. Therefore, communication networks are expected to support heterogeneous data sources with diverse QoS requirements supporting.Most existing designs of communication networks are based on the assumption that each node is well behaved and cooperative; and packet loss that does occur is mainly due to contention or congestion. Built upon open transmission mediums, communication networks are vulnerable to channel impairments, failure, interference and fading, and so on [3, 4]. Misbehaving nodes always exist along the available paths between sources and destinations. All of these can cause unreliable data transmission, lower effective data rate received successfully at the destination node, and unfairness between different sources [5]. The network performance is significantly degraded by misbehaving nodes particularly for data sources with tight quality-of-service requirements such as real-time provision in city-wide wireless network [6]. How to maintain an acceptable level of network performance degradation for heterogeneous data sources still remains an open problem in the design of a communication network with the presence of misbehaving nodes.The majority of antifault approaches make use of network redundancy. For example, reliable protocols may introduce multiple routing paths, different spectrums, or multiple wireless channels to curb the effects of malicious attacks or failures. In addition, multipath routing, which can be useful in enhancing the network performance, was actively studied in communication networks [7]. In this paper, we guarantee the QoS requirements based on the use of multiple routing paths. For various applications, higher effective throughput and better fairness offer better QoS. To make efficient utilization of this routing diversity, however, heterogeneous data sources must be able to perform an intelligent traffic allocation along the available paths while considering the potential impact of faults on the effective throughput.In order to characterize the effect of misbehaving nodes on throughput, each source must rely on direct knowledge of the impact of faulty nodes in various parts of the network. Unfortunately, it is not an easy job to collect information on misbehaving nodes directly, in a realistic environment. Few current works consider uncertainties and dynamics in the adversarial environment. Most of them assume that the misbehavior is fixed with time. In fact, the extent of misbehaviors at each network node depends on many unknown parameters, including malicious nodes’ actions, schemes used by attackers, mobility patterns, and other unknown external/internal faults [8–10]. Hence, the impact of faulty nodes is probabilistic from the perspective of the network. We estimate the impact of jamming and characterize the effect of faults as a random process. Each source performs traffic allocation based on statistical information at probabilistic faulty nodes.To provide better traffic management on multiple paths, Optimal Flow Control (OFC) approach [11], which is regarded as the most successful result in the area of traffic allocation, optimizes the sum utility of homogeneous traffic. Wang et al. [12] have shown that if various applications are run over a network, the OFC approach usually leads to an unfair traffic allocation according to the utility performance for heterogeneous traffic. The objective of heterogeneous applications is no longer to solely maximize the sum utility of the sources. Instead, it is supposed to meet different QoS requirements related to heterogeneous applications. In order to support different traffic types, we model application performance as a generic utility function by relaxing the utility function conditions. Explicitly taking account of misbehaviors’ effect, we generalize the OFC approach to obtain new problem formulations, namely, fault-aware utility flow control (FUFC), which can optimize relaxed utilities of lossy flows on multiple routing paths, having the ability to handle a number of heterogeneous traffic.In this article, we investigate the problem of resource allocation in multiple-path routing strategies for heterogeneous data sources in the event of faulty behaviors. We first model the effect of misbehaviors at each node as a random process due to the misbehavior dynamic and mobility. Owing to traversing over the probabilistic faulty paths, the flow at the destination node must be studied using a stochastic framework and smaller than that from the source node. We formulate this rate allocation as a lossy flow optimization problem for multipath routing while considering the thinning feature of data flows across faulty paths. In order to support heterogeneous traffic, we relax the utility function conditions in our lossy optimization problem. Then we design a distributed rate control algorithm that allocates source rate so that the performance of heterogeneous data sources is guaranteed. Each source has the ability to compensate for misbehaviors in network performance degradation across multiple routing paths in terms of utilities, rather than performance degradation in terms of rates. In this way, our algorithm improves the utility performance of heterogeneous sources according to different QoS requirements resulting in overall improvement in system performance.The main contributions of this paper are outlined as follows:(i)
We formulate the problem of allocating traffic across multiple routing paths in the presence of faulty nodes as a network lossy flow optimization problem which can optimize relaxed utilities, having the ability to handle heterogeneous traffic.(ii)
We propose an approach which allows network nodes to locally characterize the impact of the nondeterministic and dynamic faulty behaviors and aggregate this information for the heterogeneous source nodes. Each source can introduce bias into rate allocation and routing decisions, leading to compensating for misbehaviors in network performance degradation in terms of utility return.(iii)
We provide a novel distributed algorithm, FUFC, to be friendly with heterogeneous applications and allocate the effective rate in lossy utility fair manner.(iv)
Through comprehensive performance comparisons, we demonstrate the considerable gains in network performance including higher effective throughput and better fairness among heterogeneous sources that can be achieved by our algorithm.The rest of the paper is organized as follows. We depict our system model in Section2. We propose methods that allow nodes to estimate the impact of misbehaviors and model the leaky-path flow in Section 3. In Section 4, we present the fault-aware utility flow control approach with multipath routing. The performance of our algorithm is evaluated in Section 5. Finally, we describe the related work in Section 6 and conclude the paper in Section 7.


## 2. System Model and Assumptions

### 2.1. Network Model

We consider a network with a setL=1,2,…,L of links of capacity cl, l∈L, and a set V=1,2,…,V of nodes. We denote a link as a pair of nodes i,j, where i∈V is the transmitter of the link and j∈V is the receiver. The network is shared by a set S=1,2,…,S of sources, and S⊆V. Each source s∈S has ks available paths or routes from the source to destination. Denote L×1 vector Rs,n the set of links used by source s∈S on its path n∈1,2,…,ks, whose lth element is equal to 1 if and only if the path passes through link l and 0 otherwise. Then the set of all the available paths of source s is defined by (1)Rs=Rs,1,Rs,2,…,Rs,ks,and the whole set of paths in the network is defined by a L×K routing matrix R(2)R=R1,R2,…,RS,where K=k1+k2+⋯+kS is the total number of paths.Denote theks×1 vector As,l as the set flow s’ paths pass through link l, whose nth element is equal to 1 if the path Rs,n of flow s contains link l, and 0 otherwise. For each source s, define xs,n be the rate of source s on the path Rs,n, and obviously the total source rate xs=∑n=1ksxs,n‍, where xs∈ms,Ms, where ms≥0 and Ms<∞ are the required minimum and maximum source rate, respectively. Let(3)X=x1,1,…,x1,k1,x2,1,…,x2,k2,…,xk,1,…,xk,kSTbe the corresponding vector of all path rates of all sources and let the ks×1 vector Fs=xs,1,…,xs,ksT denote the set of all path rates of source s.Figure1 illustrates an example network of the sources s1,s2,s3,s4. Each source consists of multiple routing paths: (4)Rs1,1=A,B,B,C,C,F,Rs1,2=D,E,E,F,Rs2,1=D,E,E,F,F,I,Rs2,2=G,H,H,I,Rs3,1=A,B,B,C,C,F,Rs3,2=G,H,H,F.Figure 1
An example network with heterogeneous sources.For communication networks, usually, users focus on source rate and throughput at the destination node. However, since networks consist of various node types or modalities, as shown in Figure1, there may exist different applications with diverse utility behaviors. Each application uses its utility as a measure of the QoS performance in terms of provided services. Regardless of the types of sources, we assume that utility Usxs is achieved by the traffic as a function of its rate xs. More generally, utilities of multiple applications can be categorized as follows in terms of performance goal perspectives [12]:(i)
Elastic utility for traditional data services such as file transfer, mail, and ftp;(ii)
Real-time utility for delay-sensitive services such as video surveillance, real-time monitoring, and teleconferencing;(iii)
Rate-adaptive utility for real-time rate-adaptive services which are able to adjust their rates dynamically;(iv)
Stepwise utility for other types of services such as audio and video delivery services via a layered encoding and transmission model.


### 2.2. Misbehaving Node Model

In this article, we assume that the source nodes have no prior knowledge of the abnormal behaviors of nodes: failures of internal components, or some external attacks/interferences in the adversarial environment. That is, we make no assumption about the strategy used by malicious nodes, mobility patterns, or misbehaviors’ goals. Instead of basing on direct of knowledge of the misbehaviors, we suppose that the network nodes characterize the impact of faulty behaviors in terms of their direct impact on throughput. We assume that packet loss occurs not due to contention or congestion but misbehaving nodes, since the former can be managed by the provision of the underlying network protocols. With the existence of misbehaving nodes, the increased packet loss ratio of each node usually occurs, which is caused by the increased probability of collisions for the transmission mechanism. Network nodes can then incorporate the information to the decision of source nodes’ optimal rate allocation and routing.


## 2.1. Network Model

We consider a network with a setL=1,2,…,L of links of capacity cl, l∈L, and a set V=1,2,…,V of nodes. We denote a link as a pair of nodes i,j, where i∈V is the transmitter of the link and j∈V is the receiver. The network is shared by a set S=1,2,…,S of sources, and S⊆V. Each source s∈S has ks available paths or routes from the source to destination. Denote L×1 vector Rs,n the set of links used by source s∈S on its path n∈1,2,…,ks, whose lth element is equal to 1 if and only if the path passes through link l and 0 otherwise. Then the set of all the available paths of source s is defined by (1)Rs=Rs,1,Rs,2,…,Rs,ks,and the whole set of paths in the network is defined by a L×K routing matrix R(2)R=R1,R2,…,RS,where K=k1+k2+⋯+kS is the total number of paths.Denote theks×1 vector As,l as the set flow s’ paths pass through link l, whose nth element is equal to 1 if the path Rs,n of flow s contains link l, and 0 otherwise. For each source s, define xs,n be the rate of source s on the path Rs,n, and obviously the total source rate xs=∑n=1ksxs,n‍, where xs∈ms,Ms, where ms≥0 and Ms<∞ are the required minimum and maximum source rate, respectively. Let(3)X=x1,1,…,x1,k1,x2,1,…,x2,k2,…,xk,1,…,xk,kSTbe the corresponding vector of all path rates of all sources and let the ks×1 vector Fs=xs,1,…,xs,ksT denote the set of all path rates of source s.Figure1 illustrates an example network of the sources s1,s2,s3,s4. Each source consists of multiple routing paths: (4)Rs1,1=A,B,B,C,C,F,Rs1,2=D,E,E,F,Rs2,1=D,E,E,F,F,I,Rs2,2=G,H,H,I,Rs3,1=A,B,B,C,C,F,Rs3,2=G,H,H,F.Figure 1
An example network with heterogeneous sources.For communication networks, usually, users focus on source rate and throughput at the destination node. However, since networks consist of various node types or modalities, as shown in Figure1, there may exist different applications with diverse utility behaviors. Each application uses its utility as a measure of the QoS performance in terms of provided services. Regardless of the types of sources, we assume that utility Usxs is achieved by the traffic as a function of its rate xs. More generally, utilities of multiple applications can be categorized as follows in terms of performance goal perspectives [12]:(i)
Elastic utility for traditional data services such as file transfer, mail, and ftp;(ii)
Real-time utility for delay-sensitive services such as video surveillance, real-time monitoring, and teleconferencing;(iii)
Rate-adaptive utility for real-time rate-adaptive services which are able to adjust their rates dynamically;(iv)
Stepwise utility for other types of services such as audio and video delivery services via a layered encoding and transmission model.


## 2.2. Misbehaving Node Model

In this article, we assume that the source nodes have no prior knowledge of the abnormal behaviors of nodes: failures of internal components, or some external attacks/interferences in the adversarial environment. That is, we make no assumption about the strategy used by malicious nodes, mobility patterns, or misbehaviors’ goals. Instead of basing on direct of knowledge of the misbehaviors, we suppose that the network nodes characterize the impact of faulty behaviors in terms of their direct impact on throughput. We assume that packet loss occurs not due to contention or congestion but misbehaving nodes, since the former can be managed by the provision of the underlying network protocols. With the existence of misbehaving nodes, the increased packet loss ratio of each node usually occurs, which is caused by the increased probability of collisions for the transmission mechanism. Network nodes can then incorporate the information to the decision of source nodes’ optimal rate allocation and routing.


## 3. Estimating the Impact of Misbehaviors and Models for Leaky-Path Flows

In this section, we provide methods for the network node to estimate and characterize the impact of misbehaviors and for a source node to obtain misbehavior information. Before incorporating the impact into traffic allocation and routing, each nodej must estimate the effect of misbehaviors on transmissions over link v,j and relay it to source s. In the presence of misbehaving nodes, the increased probability of collisions usually leads to the increased packet loss ratio of each link for the transmission mechanism. Due to the impact of misbehaviors, network links are lossy in nature. Consequently, the flow rate turns into lower and lower across its routing path called leaky-path, and the effective data rate received successfully at the destination node is lower than the transmission rate at the source. To study this, we present the models for lossy links and leaky-path flows in the following.


### 3.1. Estimating the Impact of Misbehaviors

In this paper, we assume that packet loss or corruption occurs only due to faulty nodes since contention or congestion can be controlled by the provision of the underlying network protocols. Although a faulty node may perform various malicious behaviors, any good node exhibits the same behavior: delivering packets correctly. During the updated period represented by the time intervalt-T,t, each node j can record the number of packets received over link and the number of valid packets which pass an error detection check. As the network has no knowledge of the misbehaving nodes actions, the impact of fault is uncertain and probabilistic from the perspective of the network. The behavior of node v is formulated as a random variable Hv. The outcomes of Hv are defined as follows: (5)Hv=1ifvreceivesthepacketsuccessfully,0otherwise.The packet delivery ratio over each link v,j can be formulated as a random variable using statistics from node v. Due to the packet loss in faulty links, the data rate of a flow becomes thinner and thinner along its routing path. For a routing path, the behavior of a path p=v1,v2,…,vp can also be formulated as a random variable Tp. The outcomes of Tp are defined as follows: (6)Tp=1ifpdeliversthepacketsuccessfully,0otherwise.Then, the packet delivery ratio over nodej can itself be characterized as hj=Pr⁡Hj=1, a random variable using statistics from past network communication, due to the network’s uncertainty in the faulty node’s action. During the time interval t-T,t, each node j records the number nt-T,t of packets received over links, and the number mt-T,t of valid packets. The packet delivery probability over link (i,j) for the update period ([t-T],t) is thus equal to the ratio(7)hjt-T,t=mt-T,tnt-T,t. In order to reduce significant variation, and to include memory of misbehaviors history, we update the estimation through the previous estimate h^jt-T as(8)h^jt=αh^jt-T+1-αhjt-T,t, where α∈0,1 is a constant weight representing the relative preference between recent and historic samples. The constant time interval T influences the quality of the estimate process. If the interval is too large, the estimate result will be outdated and cost more time. Otherwise, the dynamics of misbehaviors can not be captured, and the result of h^j is not accurate enough. Hence, the choice of T depends on the application scenarios. We use a similar estimation procedure to update the variance νl2:(9)νj2t=βνj2t-Ts+1-βμjt-Ts,t, where β∈0,1 is a constant weight and μj is the sample variance of packet delivery ratios computed using (7) during the time interval t-Ts,t. The node collects sample values during time interval t-Ts,t. Hence, the time interval Ts should be larger than the time interval T.Given the packet delivery ratio estimatesh^jt for the links i,j in the routing path Rs,n, the source s needs to estimate the effective end-to-end packet delivery probability. The end-to-end packet success ratio Rs,n for the path can be formulated as(10)gs,n=∏i,j∈Rs,nhj, which is also a random variable due to the randomness in variable hj. We let g^s,n denote as the mean of random variable gs,n which is equal to the product of estimations h^l:(11)g^s,n=∏i,j∈Rs,nh^j.LetRs,ni denote the subpath of Rs,n from source S to the intermediate node i and R¯s,ni denote the subpath of Rs,n from the intermediate node i to the destination node of Rs,n. The estimated packet delivery ratio of subpath Rs,ni can be computed using (10):(12)g^s,ni=∏i,j∈Rs,nih^j.The covarianceϕs,ni is similar given by(13)ϕs,ni=∏i,j∈Rs,niνj2+h^j2-g^s,ni2.


### 3.2. Leaky-Path Flow Model

Due to misbehaviors at nodes along the path, the effective rate is potentially reduced at each intermediate receiving node since data packets are lost. At a linki,j in the routing path Rs,n with transmission source rate xs,n, data is only received correctly on g^s,nixs,n. We define the goodput xs,n′ of a flow as the effective data rate received successfully at its destination node [13]. For a flow from source s traversing multiple hops, the goodput received at the destination node is given by(14)xs,n′=g^s,nxs,n, where xs,n is the transmission rate at the source and Rs,n is the set of links along the route. It can be seen that the data rate of a flow declines every hop along its routing path, and it is in this sense that we call it a leaky-path flow.To define a set of constraints for the multipath rate allocation problem, we must consider the resource constraints and the reduction of data flow due to misbehaviors at intermediate nodes. The resource constraint in necessary conditions of network utility maximization was that the average data rate should be no more than average capacity of each link. We next generate the stochastic constraint through incorporating the fault statistics into the link capacity constraint. For a communication network under probabilistic misbehaviors, the data flow rate is reduced along each path with increased the hops from sources. Hence, if the data flow rate at the source s is chosen without considering the packet loss by misbehaviors, the actual aggregate rate ∑Qsxs,n‍ may not be tightly bounded by the average capacity, where Qs=s∈Si,j∧Rs,n∈Rs∧i,j∈Rs,n. Thus at the node i of path Rs,ni, the goodput is given by gs,nixs,n. The stochastic constraint is thus imposed by the capacity constraint on the total traffic traversing a link i,j which can be given as follows:(15)∑Qsgs,nixs,n≤ci,j.In order to compensate for the randomness in (15), we use the expected value and variance to replace the packet delivery ratio gs,ni. The mean g^s,ni and variance ϕs,ni of gs,ni can be computed using (12) and (13), respectively. We replace gs,ni with the statistic value g^s,ni+δϕs,ni, where constant δ≥0. The link constraint can be expresses by(16)∑Qsg^s,ni+δϕs,nixs,n≤ci,j.A principal objective in optimal flow control problem formulation is to maximize the overall effective network utility of all flows from different sources:(17)max∑s∈SUs∑n=1ksg^s,nxs,nor(18)max∑s∈SUs∑n=1ksxs,n′,where Usxs is the associated utility as a measure of performance (or equivalently QoS).


## 3.1. Estimating the Impact of Misbehaviors

In this paper, we assume that packet loss or corruption occurs only due to faulty nodes since contention or congestion can be controlled by the provision of the underlying network protocols. Although a faulty node may perform various malicious behaviors, any good node exhibits the same behavior: delivering packets correctly. During the updated period represented by the time intervalt-T,t, each node j can record the number of packets received over link and the number of valid packets which pass an error detection check. As the network has no knowledge of the misbehaving nodes actions, the impact of fault is uncertain and probabilistic from the perspective of the network. The behavior of node v is formulated as a random variable Hv. The outcomes of Hv are defined as follows: (5)Hv=1ifvreceivesthepacketsuccessfully,0otherwise.The packet delivery ratio over each link v,j can be formulated as a random variable using statistics from node v. Due to the packet loss in faulty links, the data rate of a flow becomes thinner and thinner along its routing path. For a routing path, the behavior of a path p=v1,v2,…,vp can also be formulated as a random variable Tp. The outcomes of Tp are defined as follows: (6)Tp=1ifpdeliversthepacketsuccessfully,0otherwise.Then, the packet delivery ratio over nodej can itself be characterized as hj=Pr⁡Hj=1, a random variable using statistics from past network communication, due to the network’s uncertainty in the faulty node’s action. During the time interval t-T,t, each node j records the number nt-T,t of packets received over links, and the number mt-T,t of valid packets. The packet delivery probability over link (i,j) for the update period ([t-T],t) is thus equal to the ratio(7)hjt-T,t=mt-T,tnt-T,t. In order to reduce significant variation, and to include memory of misbehaviors history, we update the estimation through the previous estimate h^jt-T as(8)h^jt=αh^jt-T+1-αhjt-T,t, where α∈0,1 is a constant weight representing the relative preference between recent and historic samples. The constant time interval T influences the quality of the estimate process. If the interval is too large, the estimate result will be outdated and cost more time. Otherwise, the dynamics of misbehaviors can not be captured, and the result of h^j is not accurate enough. Hence, the choice of T depends on the application scenarios. We use a similar estimation procedure to update the variance νl2:(9)νj2t=βνj2t-Ts+1-βμjt-Ts,t, where β∈0,1 is a constant weight and μj is the sample variance of packet delivery ratios computed using (7) during the time interval t-Ts,t. The node collects sample values during time interval t-Ts,t. Hence, the time interval Ts should be larger than the time interval T.Given the packet delivery ratio estimatesh^jt for the links i,j in the routing path Rs,n, the source s needs to estimate the effective end-to-end packet delivery probability. The end-to-end packet success ratio Rs,n for the path can be formulated as(10)gs,n=∏i,j∈Rs,nhj, which is also a random variable due to the randomness in variable hj. We let g^s,n denote as the mean of random variable gs,n which is equal to the product of estimations h^l:(11)g^s,n=∏i,j∈Rs,nh^j.LetRs,ni denote the subpath of Rs,n from source S to the intermediate node i and R¯s,ni denote the subpath of Rs,n from the intermediate node i to the destination node of Rs,n. The estimated packet delivery ratio of subpath Rs,ni can be computed using (10):(12)g^s,ni=∏i,j∈Rs,nih^j.The covarianceϕs,ni is similar given by(13)ϕs,ni=∏i,j∈Rs,niνj2+h^j2-g^s,ni2.


## 3.2. Leaky-Path Flow Model

Due to misbehaviors at nodes along the path, the effective rate is potentially reduced at each intermediate receiving node since data packets are lost. At a linki,j in the routing path Rs,n with transmission source rate xs,n, data is only received correctly on g^s,nixs,n. We define the goodput xs,n′ of a flow as the effective data rate received successfully at its destination node [13]. For a flow from source s traversing multiple hops, the goodput received at the destination node is given by(14)xs,n′=g^s,nxs,n, where xs,n is the transmission rate at the source and Rs,n is the set of links along the route. It can be seen that the data rate of a flow declines every hop along its routing path, and it is in this sense that we call it a leaky-path flow.To define a set of constraints for the multipath rate allocation problem, we must consider the resource constraints and the reduction of data flow due to misbehaviors at intermediate nodes. The resource constraint in necessary conditions of network utility maximization was that the average data rate should be no more than average capacity of each link. We next generate the stochastic constraint through incorporating the fault statistics into the link capacity constraint. For a communication network under probabilistic misbehaviors, the data flow rate is reduced along each path with increased the hops from sources. Hence, if the data flow rate at the source s is chosen without considering the packet loss by misbehaviors, the actual aggregate rate ∑Qsxs,n‍ may not be tightly bounded by the average capacity, where Qs=s∈Si,j∧Rs,n∈Rs∧i,j∈Rs,n. Thus at the node i of path Rs,ni, the goodput is given by gs,nixs,n. The stochastic constraint is thus imposed by the capacity constraint on the total traffic traversing a link i,j which can be given as follows:(15)∑Qsgs,nixs,n≤ci,j.In order to compensate for the randomness in (15), we use the expected value and variance to replace the packet delivery ratio gs,ni. The mean g^s,ni and variance ϕs,ni of gs,ni can be computed using (12) and (13), respectively. We replace gs,ni with the statistic value g^s,ni+δϕs,ni, where constant δ≥0. The link constraint can be expresses by(16)∑Qsg^s,ni+δϕs,nixs,n≤ci,j.A principal objective in optimal flow control problem formulation is to maximize the overall effective network utility of all flows from different sources:(17)max∑s∈SUs∑n=1ksg^s,nxs,nor(18)max∑s∈SUs∑n=1ksxs,n′,where Usxs is the associated utility as a measure of performance (or equivalently QoS).


## 4. Fault-Aware Utility Flow Control with Multipath Routing

### 4.1. Utility Framework for Fair Flow Control

Even though the optimal flow control approach has made a success in dealing with resource allocation, it also processes serious limitations when different types of traffic exist in the network. If each source selects different utility functions with different QoS requirements, OFC may cause utility unfairness among contending users for practical use. Since the source with high demand may receive a low resource, this results in applications receiving low utility.In big-data communication networks, sources with different traffic types offer various valuable information regarding the environment. In order to support numerous applications with different utility demands, the flow control strategy should have the ability to allocate traffic rates properly in order to balance the performance for different applications. When considering different QoS requirements of heterogeneous sources, it can not meet the practical demand to allocate source rate simply in terms of conventional fairness criteria. Therefore, we design a utility framework of fair flow control, which allocates source rate according to the different QoS utilities.In this framework, each sources attains a utility Usxs, where xs is the source rate. The utility function Us· is assumed to be continuous, strictly increasing, and bounded in the interval ms,Ms. We define a “pseudo utility” usxs as usxs=∫msxs1/Usydy‍. The goal is to maximize the sum of the pseudo utility(19)Problem:max∑s∈S∫ms∑n=1ks1Usydys.t.:∑Qsxs,n≤ci,jms≤∑n=1ksxs,n≤Ms.We generalize the OFC approach to obtain new problem formulations, namely, utility optimal flow control (UFC), which replace the conventional utility function with pseudo utilityusxs.The demand for different QoS utilities also motivates a new concept of the utility max-min fairness [14].Definition 1.
A source rate allocationX∗=x1∗,x2∗,…,xS∗T is utility max-min fair, if it is feasible and for each source s, the utility Usxs∗ cannot be increased while maintaining feasibility, without decreasing the utility Us′xs′∗ for some source s′ with a lower utility Us′xs′∗≤Usxs∗.The definition shows that we should design rate control protocols that try to achieve fairness in terms of utilities, rather than fairness in terms of rates. For heterogeneous sources, the utilities, rather than source rates, are meaningful metrics of QoS for the applications.To apply the UFC in fault-aware wireless networks, one needs to specify the resource constraints as in (19). Due to the faulty nodes existence on the routing path, the traffic rate is potentially decreased at each receiver as faulty nodes are lossy. Then the UFC operates over faulty links as follows: at each link, the link resource constraint is calculated as in (19), but using the total actual received rate at the link, not the sum of the original rates; and the source node updates the flow rate according to the feedback parameter of resource constraints along its route. This straightforward application of the UFC framework takes account of the faulty links, but only in the way the feedback parameters are computed. The lossy nature of the routing path is not considered in the objective function in the UFC problem itself. In the following section, we will propose the fault-aware utility flow control algorithm, which takes account of the lossy nature of the faulty paths in the objective function and constraints, to achieve lossy utility-based fairness for heterogeneous sources and study the properties in detail.


### 4.2. Fault-Aware Utility Flow Control Algorithm with Multiple Paths

Since the optimization framework of utility flow control is primarily developed for fault-free network environments, it cannot be directly applied to adversarial environments. In order to guarantee the network performance in the presence of misbehaving nodes, we provide the lossy optimization framework of utility flow control based on leaky-path model. The objective in this problem formulation is to maximize the overall pseudo utility of all effective flows, subject to the link capacity including expected packet loss due to misbehaviors. Then we have the following optimization problem:(20)Problem:max∑s∈S∫ms∑n=1ksg^s,nxs,n1Usydys.t.:∑Qsg^s,ni+δϕs,nixs,n≤ci,jms≤∑n=1ksxs,n≤Ms.The Lagrangian function can be defined as(21)LX~,λ,λ_,λ¯=∑s∈S∫ms∑n=1ksg^s,nxs,n1Usydy+λ¯Ms-∑n=1ksxs,n-λ_ms-∑n=1ksxs,n-∑i,jλi,j∑Qsg^s,ni+δϕs,nixs,n-ci,j.Here,λ¯=λ¯1,…,λ¯sT, λ_=λ_1,…,λ_sT, λ=λ1,…,λLT, and u=λ¯,λ_,λ are all nonnegative. The objective function of the dual problem is given by(22)Dλ,λ¯,λ_=maxx~Lx~,λ,λ¯,λ_.In terms of the Arrow-Hurwicz gradient method [15], we can obtain(23)xs,nt+1=xs,nt+γ1Us∑n=1ksg^s,nxs,nt+λ¯st-λ_st-λs,nrt+,where γ is a small step size and λs,nrt is the path price, which is composed of the link prices λi,jt along the particular route. Then the objective function of the dual problem is then(24)minλ,λ¯,λ_Dλ,λ¯,λ_.The Lagrangian multipliers for the dual can be computed by the gradient method, as follows:(25)λi,jt+1=λi,jt+γ∑Qsg^s,ni+δϕs,nixs,nt-ci,j+,(26)λ¯st+1=λ¯st+γMs-∑n=1ksxs,nt+,(27)λ_st+1=λ_st-γms-∑n=1ksxs,nt+.We present our design of distributed algorithm based on proximal optimization steps for solving the utility max-min fair flow control with multiple paths problem. The FUFC algorithm for heterogeneous sources with multiple routing paths can be summarized in Algorithm1.Algorithm 1:Fault-aware utility flow control FUFC algorithm.
(i) Link(i,j)’s algorithm
At each time t = 1,2,…, each link (i,j):
(1) Aggregates flow rates xs,n(t) for all paths Rs,n that contain link (i,j);
(2) Computes a new link price by formula (25);
(3) Communicates the new price λ(i,j)(t+1) to all sources whose paths Rs,n contain link (i,j).
(ii) Sources’s algorithm
At each time t = 1,2,…, each source s:
(1) Receives from the network the path prices
λ
s
,
n
r
(
t
)
=
max
(
i
,
j
)
∈
R
s
,
n
⁡
λ
(
i
,
j
)
(
t
)     (∗)
for all its paths Rs,n,n=1,…,ks;
(2) Updates the path rate xs,n(t+1) using formula (23) and source rate xst+1=∑n=1ks‍xs,nt+1;
(3) Communicates the upper and lower bound price λ¯ and λ_ for the next step, according to (26) and (27);
(4) Communicates the new flow rate xs,n(t+1) to all the links which are contained in path Rs,n.For each sources with multiple paths, the property of updating formulations can easily lead to the oscillations in the Lagrangian algorithm. Since this kind of oscillation is detrimental to network control, we introduce an augmented variable fs,n to solve the oscillation problem. The following modified objective function is used to replace the objective function of formulation (20):(28)max∑s∈S∫ms∑n=1ksg^s,nxs,n1Usydy-∑s∈S∑n=1ks12xs,n-fs,n2.Denotingxs,n∗ as the optimal value of (20), the optimal value of the utility maximization problem with objective function (28) is xs,n=xs,n∗, fs,n=fs,n∗. Therefore, (23) is slightly modified by applying the new objective function:(29)xs,nt+1=1-γxs,nt+γfs,nt+γ1Us∑n=1ksg^s,nxs,nt+λ¯st-λ_st-λs,nrt+,fs,nt+1=1-γfs,nt+γxs,nt.


### 4.3. Lossy Utility Max-Min Fairness

Based on the assumption of nonadversarial environments, each node in the network is well-behaved andhi=1. Our distributed algorithm with hi=1 can allocate rates to achieve the utility max-min fairness among sources. The path rate algorithm of (23) simplifies to(30)xs,nt+1=xs,nt+γ1Us∑n=1ksxs,nt-λs,nrt+.We can obtain that1/Us∑n=1ksxs,nt‍=λs,nrt or xs,nt+1=0 at convergence. In steady state, nodes attain a normal utility Us∗=1/λsr∗. Let Sλ denote the set of nodes which have at least one path rate by the link price λ. Let us first consider the highest link price λ0; all the sources s∈Sλ0 get the smallest utility Us=1/λ0. They are feasible and no source utility can be increased without decreasing another source utility that has the maximum price λ0. So for these flows with price λ0, they are utility max-min fair.Then we consider the second highest link priceλ1. All the sources s∈Sλ1 attain the same utility Us=1/λ1. No source utility can be increased without decreasing another source utility of s′∈Sλ0∪Sλ1 having a lower utility Us<Us′. All other flows traversing this link will be assigned a price of λ1 and equally share the remaining utility, which is also a utility max-min fair allocation.Let us keep selecting all the link prices in the orderλ0,λ1,…,λk-1,λk; it is concluded that the algorithm with hi=0 allocates source rate in utility max-min fair manner and that the global fairness is achieved.Whenh=1, the source rate in our algorithm can achieve utility max-min fairness, while the source rate can achieve lossy utility max-min fairness with h<1. The following corollary establishes that utility max-min fair solutions also have the convergence property as loss ratios tend to zero.Corollary 2.
As the node fault ratio drop to zero:limk→∞⁡mini,j∈Rs,nhjk=1, lossy utility max-min fair solutions converge to the lossless utility max-min fair solution.The continuity of solutions can be proved using standard techniques in convergence analysis of Pompeiu-Hausdorff distance [13]. For the sake of limited space, we omit the proof here.With the rapid process of Internet of Things and smart cities, the nature of the network is gradually evolving heterogeneously. There are various types of nodes, such as camera, robots, and mobile entities, in distributed heterogeneous systems. Our approach caters for a variety of service performance metrics related to heterogeneous sources. The network performance and QoS requirements are guaranteed through providing both effective throughput and fairness among various sources. We show the numerical results of our proposed algorithm in the following section.


## 4.1. Utility Framework for Fair Flow Control

Even though the optimal flow control approach has made a success in dealing with resource allocation, it also processes serious limitations when different types of traffic exist in the network. If each source selects different utility functions with different QoS requirements, OFC may cause utility unfairness among contending users for practical use. Since the source with high demand may receive a low resource, this results in applications receiving low utility.In big-data communication networks, sources with different traffic types offer various valuable information regarding the environment. In order to support numerous applications with different utility demands, the flow control strategy should have the ability to allocate traffic rates properly in order to balance the performance for different applications. When considering different QoS requirements of heterogeneous sources, it can not meet the practical demand to allocate source rate simply in terms of conventional fairness criteria. Therefore, we design a utility framework of fair flow control, which allocates source rate according to the different QoS utilities.In this framework, each sources attains a utility Usxs, where xs is the source rate. The utility function Us· is assumed to be continuous, strictly increasing, and bounded in the interval ms,Ms. We define a “pseudo utility” usxs as usxs=∫msxs1/Usydy‍. The goal is to maximize the sum of the pseudo utility(19)Problem:max∑s∈S∫ms∑n=1ks1Usydys.t.:∑Qsxs,n≤ci,jms≤∑n=1ksxs,n≤Ms.We generalize the OFC approach to obtain new problem formulations, namely, utility optimal flow control (UFC), which replace the conventional utility function with pseudo utilityusxs.The demand for different QoS utilities also motivates a new concept of the utility max-min fairness [14].Definition 1.
A source rate allocationX∗=x1∗,x2∗,…,xS∗T is utility max-min fair, if it is feasible and for each source s, the utility Usxs∗ cannot be increased while maintaining feasibility, without decreasing the utility Us′xs′∗ for some source s′ with a lower utility Us′xs′∗≤Usxs∗.The definition shows that we should design rate control protocols that try to achieve fairness in terms of utilities, rather than fairness in terms of rates. For heterogeneous sources, the utilities, rather than source rates, are meaningful metrics of QoS for the applications.To apply the UFC in fault-aware wireless networks, one needs to specify the resource constraints as in (19). Due to the faulty nodes existence on the routing path, the traffic rate is potentially decreased at each receiver as faulty nodes are lossy. Then the UFC operates over faulty links as follows: at each link, the link resource constraint is calculated as in (19), but using the total actual received rate at the link, not the sum of the original rates; and the source node updates the flow rate according to the feedback parameter of resource constraints along its route. This straightforward application of the UFC framework takes account of the faulty links, but only in the way the feedback parameters are computed. The lossy nature of the routing path is not considered in the objective function in the UFC problem itself. In the following section, we will propose the fault-aware utility flow control algorithm, which takes account of the lossy nature of the faulty paths in the objective function and constraints, to achieve lossy utility-based fairness for heterogeneous sources and study the properties in detail.


## 4.2. Fault-Aware Utility Flow Control Algorithm with Multiple Paths

Since the optimization framework of utility flow control is primarily developed for fault-free network environments, it cannot be directly applied to adversarial environments. In order to guarantee the network performance in the presence of misbehaving nodes, we provide the lossy optimization framework of utility flow control based on leaky-path model. The objective in this problem formulation is to maximize the overall pseudo utility of all effective flows, subject to the link capacity including expected packet loss due to misbehaviors. Then we have the following optimization problem:(20)Problem:max∑s∈S∫ms∑n=1ksg^s,nxs,n1Usydys.t.:∑Qsg^s,ni+δϕs,nixs,n≤ci,jms≤∑n=1ksxs,n≤Ms.The Lagrangian function can be defined as(21)LX~,λ,λ_,λ¯=∑s∈S∫ms∑n=1ksg^s,nxs,n1Usydy+λ¯Ms-∑n=1ksxs,n-λ_ms-∑n=1ksxs,n-∑i,jλi,j∑Qsg^s,ni+δϕs,nixs,n-ci,j.Here,λ¯=λ¯1,…,λ¯sT, λ_=λ_1,…,λ_sT, λ=λ1,…,λLT, and u=λ¯,λ_,λ are all nonnegative. The objective function of the dual problem is given by(22)Dλ,λ¯,λ_=maxx~Lx~,λ,λ¯,λ_.In terms of the Arrow-Hurwicz gradient method [15], we can obtain(23)xs,nt+1=xs,nt+γ1Us∑n=1ksg^s,nxs,nt+λ¯st-λ_st-λs,nrt+,where γ is a small step size and λs,nrt is the path price, which is composed of the link prices λi,jt along the particular route. Then the objective function of the dual problem is then(24)minλ,λ¯,λ_Dλ,λ¯,λ_.The Lagrangian multipliers for the dual can be computed by the gradient method, as follows:(25)λi,jt+1=λi,jt+γ∑Qsg^s,ni+δϕs,nixs,nt-ci,j+,(26)λ¯st+1=λ¯st+γMs-∑n=1ksxs,nt+,(27)λ_st+1=λ_st-γms-∑n=1ksxs,nt+.We present our design of distributed algorithm based on proximal optimization steps for solving the utility max-min fair flow control with multiple paths problem. The FUFC algorithm for heterogeneous sources with multiple routing paths can be summarized in Algorithm1.Algorithm 1:Fault-aware utility flow control FUFC algorithm.
(i) Link(i,j)’s algorithm
At each time t = 1,2,…, each link (i,j):
(1) Aggregates flow rates xs,n(t) for all paths Rs,n that contain link (i,j);
(2) Computes a new link price by formula (25);
(3) Communicates the new price λ(i,j)(t+1) to all sources whose paths Rs,n contain link (i,j).
(ii) Sources’s algorithm
At each time t = 1,2,…, each source s:
(1) Receives from the network the path prices
λ
s
,
n
r
(
t
)
=
max
(
i
,
j
)
∈
R
s
,
n
⁡
λ
(
i
,
j
)
(
t
)     (∗)
for all its paths Rs,n,n=1,…,ks;
(2) Updates the path rate xs,n(t+1) using formula (23) and source rate xst+1=∑n=1ks‍xs,nt+1;
(3) Communicates the upper and lower bound price λ¯ and λ_ for the next step, according to (26) and (27);
(4) Communicates the new flow rate xs,n(t+1) to all the links which are contained in path Rs,n.For each sources with multiple paths, the property of updating formulations can easily lead to the oscillations in the Lagrangian algorithm. Since this kind of oscillation is detrimental to network control, we introduce an augmented variable fs,n to solve the oscillation problem. The following modified objective function is used to replace the objective function of formulation (20):(28)max∑s∈S∫ms∑n=1ksg^s,nxs,n1Usydy-∑s∈S∑n=1ks12xs,n-fs,n2.Denotingxs,n∗ as the optimal value of (20), the optimal value of the utility maximization problem with objective function (28) is xs,n=xs,n∗, fs,n=fs,n∗. Therefore, (23) is slightly modified by applying the new objective function:(29)xs,nt+1=1-γxs,nt+γfs,nt+γ1Us∑n=1ksg^s,nxs,nt+λ¯st-λ_st-λs,nrt+,fs,nt+1=1-γfs,nt+γxs,nt.


## 4.3. Lossy Utility Max-Min Fairness

Based on the assumption of nonadversarial environments, each node in the network is well-behaved andhi=1. Our distributed algorithm with hi=1 can allocate rates to achieve the utility max-min fairness among sources. The path rate algorithm of (23) simplifies to(30)xs,nt+1=xs,nt+γ1Us∑n=1ksxs,nt-λs,nrt+.We can obtain that1/Us∑n=1ksxs,nt‍=λs,nrt or xs,nt+1=0 at convergence. In steady state, nodes attain a normal utility Us∗=1/λsr∗. Let Sλ denote the set of nodes which have at least one path rate by the link price λ. Let us first consider the highest link price λ0; all the sources s∈Sλ0 get the smallest utility Us=1/λ0. They are feasible and no source utility can be increased without decreasing another source utility that has the maximum price λ0. So for these flows with price λ0, they are utility max-min fair.Then we consider the second highest link priceλ1. All the sources s∈Sλ1 attain the same utility Us=1/λ1. No source utility can be increased without decreasing another source utility of s′∈Sλ0∪Sλ1 having a lower utility Us<Us′. All other flows traversing this link will be assigned a price of λ1 and equally share the remaining utility, which is also a utility max-min fair allocation.Let us keep selecting all the link prices in the orderλ0,λ1,…,λk-1,λk; it is concluded that the algorithm with hi=0 allocates source rate in utility max-min fair manner and that the global fairness is achieved.Whenh=1, the source rate in our algorithm can achieve utility max-min fairness, while the source rate can achieve lossy utility max-min fairness with h<1. The following corollary establishes that utility max-min fair solutions also have the convergence property as loss ratios tend to zero.Corollary 2.
As the node fault ratio drop to zero:limk→∞⁡mini,j∈Rs,nhjk=1, lossy utility max-min fair solutions converge to the lossless utility max-min fair solution.The continuity of solutions can be proved using standard techniques in convergence analysis of Pompeiu-Hausdorff distance [13]. For the sake of limited space, we omit the proof here.With the rapid process of Internet of Things and smart cities, the nature of the network is gradually evolving heterogeneously. There are various types of nodes, such as camera, robots, and mobile entities, in distributed heterogeneous systems. Our approach caters for a variety of service performance metrics related to heterogeneous sources. The network performance and QoS requirements are guaranteed through providing both effective throughput and fairness among various sources. We show the numerical results of our proposed algorithm in the following section.


## 5. Performance Evaluations

In this section, we evaluate through simulations the performance of our proposed rate control algorithm with multiple routing paths in two case studies. In the first case, we apply our flow control algorithm to a specific multipath communication network and demonstrate the dynamics of behaviors. We use numerical examples to illustrate the advantage of the FUFC over the UFC approach without considering the impact of faulty nodes. In the second case, we extend the scale of network topology in order to observe the performance trends and shows the convergence of utility fair flow control solutions established in Section4.We consider two network cases with four heterogeneous sourcesS1, S2, S3, and S4 which support multiple services with different QoS requirements. Therefore, we set utility functions consisting of heterogeneous traffic. The utility function of each source node with source rate xi is given as U1x1=1/1+e-2x1-6, U2x2=log⁡x2+1/log⁡11, U3x3=1/1+e-2x4+4, and U4x4=0.1x3. The linear utility function represents that the satisfaction of an application increases linearly. The logarithmic utility function corresponds to the real-time application which the sigmoidal function approximates.Each fault parameterhj is modeled as an independent beta random variable with parameters (δj,βj) as hj=δj/δj+βj. For example, hC=0.9 has corresponding parameters δC=39.6 and βC=4.4. Other simulation parameters are summarized in Table 1.Table 1
Parameter values in simulations.
Parameter
Value
Link capacity
c
l
,
c
2
,
c
3
,
c
4 = 4, 6, 8, 10 Mbps
Maximum data rate
M
s = 10 Mbps
Minimum data rate
m
s = 0 Mbps
Step size
γ = 0.1
Update time interval
T = 0.05 s
Update relay time interval
T
s = 0.2 s
Simulation steps
1000


### 5.1. Case 1

In this case, we show how our FUFC protocol can provide effective flow control with the existence of misbehaving nodes. The proposed FUFC protocol is benchmarked against the standard utility flow control (UFC) protocol [12]. Figure 2 depicts the topology of the network with 7 links, 6 nodes, and four sources S1, S2, S3, and S4. S1 routes its flow along two paths (A→C→B) with path rate x1,1, and (A→D→B) with path rate x1,2. S2 routes its flow along two paths, (A→D→B→F) with path rate x2,1, and (A→E→B→F) with path rate x2,2. S3 routes its flow along two paths (A→E→B) with path rate x3,1, and (A→C→B) with path rate x3,2. S4 routes its flow along a single path (B→F) with path rate x4,1.Figure 2
The network topology of Case1.We denote thatx is the data rate of one flow at the source node, and x′ as the goodput at the destination node. Note the time scale in all the relevant figures is in terms of number of iterations. In the UFC approach, we use the algorithm in Problem (19) calculated based on the flow rate on each link and link price on each path. Figure 3 shows the utility of flow rates x at four source nodes using the UFC approach. Two utilities U1 of x1 and U3 of x3 converge to 0.9876, while U2 of x2 and U4 of x4 converge to 0.6381. Without considering the effect of faulty links, the algorithm computes U1 and U3 to share the bottleneck resource with an equal utility. The UFC approach provides a utility max-min fair resource allocation in which U1 is equal to U3, and U2 is equal to U4 of their source rates x.Figure 3
The utility of flow rates at four source nodes.In fact, the effective utilities of four flows cannot maintain the utility fairness at their destination node after traveling along the leaky-paths. The effective utilities of goodput for four sources in the UFC approach are depicted in Figure4. The effective utilities decrease to 0.9099, 0.5756, 0.8075, and 0.6023 among four sources. For FUFC, the effective rates in Algorithm 1 are shown in Figure 5. It can be seen that FUFC yields higher effective utilities (0.987, 0.6381, 0.9883, and 0.6381) for four sources than UFC. We take a closer look at utility allocation among flows and effective flows in Figures 4 and 5. In Figure 3, four flows share a max-min fair utility allocation of source rate that U1 of x1 is equal to U3 of x3, and U2 of x2 is equal to U4 of x4. However, the utility fairness is broken due to different faulty effects on four paths by faulty links. U3 of x3′ and U2 of x2′ are lower than U1 of x1′ and U4 of x4′, respectively, in Figure 4. In Figure 5, the effective utilities U1 of x1′ and U3 of x3′ in FUFC are closer to each other than those in the UFC approach. The same situation happens in U2 of x2′ and U4 of x4′. It demonstrates that better utility fairness is attained among effective flow rates by FUFC.Figure 4
The effective utility in UFC.Figure 5
The effective utility in FUFC.Figures6 and 7 report the goodput at the destination node of UFC and FUFC, respectively. It can be seen that FUFC yields higher effective rates (6.185, 3.619, 8.196, and 6.381) for flows than UFC with goodput (5.156, 2.976, 6.717, and 6.023). This is because in our algorithm, multiple source nodes allocate traffic across multiple routing paths adaptively to compensate for faulty nodes, whose effects on throughput are taken into account in utility functions and constraints. Thus the network performance in presence of faulty nodes is improved through higher effective utility, higher effective throughput, and better utility fairness among effective flows by our algorithm FUFC.Figure 6
The goodput in UFC.Figure 7
The goodput in FUFC.


### 5.2. Case 2

We investigate the performance while increasingk faulty links from 1 to 8 between A and C, A and D, A and E, and B and F in the network of Case 1. Consider a wireless network given in Figure 8 where each flow travels multiple hops.Figure 8
The network topology of Case2.With an increasing number of links, the equilibrium utilitiesU2 and U4 of effective flow over the above paths of four sources for both UFC and FUFC are plotted in Figure 9. As the number of links increases, the effective utilities of goodput in both UFC and FUFC decline. Clearly, the effective utility of FUFC can be significantly higher than that of UFC. Meanwhile, the effective utilities of the flows in FUFC are closer to each other than those in the UFC approach, indicating that better fairness among effective utilities is achieved by FUFC. The gain of FUFC over UFC increases as the number of hops increases. Each source increases its flow rate adaptively to compensate for the higher data loss as the number of hops increases.Figure 9
The effective utilitiesU2 and U4 in UFC and FUFC.We can see from Figure10 that, with decreasing the number of faulty links, the rate allocation is convergent to the rate allocation in wireless lossless condition. As discussed in Section 4, the rate region in our algorithm converges to the rate region in the corresponding lossless network while a sequence of link loss rate converges to zero (the number of faulty links converges to zero). The lossy utility max-min fairness can be achieved in our algorithm and converges to the corresponding lossless fairness with a sequence of loss rates converging to 0 in Figure 11. Figures 10 and 11 show the trends of rate region and utility fairness of four sources.Figure 10
The trend of rate allocation.Figure 11
The trend of utility.


## 5.1. Case 1

In this case, we show how our FUFC protocol can provide effective flow control with the existence of misbehaving nodes. The proposed FUFC protocol is benchmarked against the standard utility flow control (UFC) protocol [12]. Figure 2 depicts the topology of the network with 7 links, 6 nodes, and four sources S1, S2, S3, and S4. S1 routes its flow along two paths (A→C→B) with path rate x1,1, and (A→D→B) with path rate x1,2. S2 routes its flow along two paths, (A→D→B→F) with path rate x2,1, and (A→E→B→F) with path rate x2,2. S3 routes its flow along two paths (A→E→B) with path rate x3,1, and (A→C→B) with path rate x3,2. S4 routes its flow along a single path (B→F) with path rate x4,1.Figure 2
The network topology of Case1.We denote thatx is the data rate of one flow at the source node, and x′ as the goodput at the destination node. Note the time scale in all the relevant figures is in terms of number of iterations. In the UFC approach, we use the algorithm in Problem (19) calculated based on the flow rate on each link and link price on each path. Figure 3 shows the utility of flow rates x at four source nodes using the UFC approach. Two utilities U1 of x1 and U3 of x3 converge to 0.9876, while U2 of x2 and U4 of x4 converge to 0.6381. Without considering the effect of faulty links, the algorithm computes U1 and U3 to share the bottleneck resource with an equal utility. The UFC approach provides a utility max-min fair resource allocation in which U1 is equal to U3, and U2 is equal to U4 of their source rates x.Figure 3
The utility of flow rates at four source nodes.In fact, the effective utilities of four flows cannot maintain the utility fairness at their destination node after traveling along the leaky-paths. The effective utilities of goodput for four sources in the UFC approach are depicted in Figure4. The effective utilities decrease to 0.9099, 0.5756, 0.8075, and 0.6023 among four sources. For FUFC, the effective rates in Algorithm 1 are shown in Figure 5. It can be seen that FUFC yields higher effective utilities (0.987, 0.6381, 0.9883, and 0.6381) for four sources than UFC. We take a closer look at utility allocation among flows and effective flows in Figures 4 and 5. In Figure 3, four flows share a max-min fair utility allocation of source rate that U1 of x1 is equal to U3 of x3, and U2 of x2 is equal to U4 of x4. However, the utility fairness is broken due to different faulty effects on four paths by faulty links. U3 of x3′ and U2 of x2′ are lower than U1 of x1′ and U4 of x4′, respectively, in Figure 4. In Figure 5, the effective utilities U1 of x1′ and U3 of x3′ in FUFC are closer to each other than those in the UFC approach. The same situation happens in U2 of x2′ and U4 of x4′. It demonstrates that better utility fairness is attained among effective flow rates by FUFC.Figure 4
The effective utility in UFC.Figure 5
The effective utility in FUFC.Figures6 and 7 report the goodput at the destination node of UFC and FUFC, respectively. It can be seen that FUFC yields higher effective rates (6.185, 3.619, 8.196, and 6.381) for flows than UFC with goodput (5.156, 2.976, 6.717, and 6.023). This is because in our algorithm, multiple source nodes allocate traffic across multiple routing paths adaptively to compensate for faulty nodes, whose effects on throughput are taken into account in utility functions and constraints. Thus the network performance in presence of faulty nodes is improved through higher effective utility, higher effective throughput, and better utility fairness among effective flows by our algorithm FUFC.Figure 6
The goodput in UFC.Figure 7
The goodput in FUFC.


## 5.2. Case 2

We investigate the performance while increasingk faulty links from 1 to 8 between A and C, A and D, A and E, and B and F in the network of Case 1. Consider a wireless network given in Figure 8 where each flow travels multiple hops.Figure 8
The network topology of Case2.With an increasing number of links, the equilibrium utilitiesU2 and U4 of effective flow over the above paths of four sources for both UFC and FUFC are plotted in Figure 9. As the number of links increases, the effective utilities of goodput in both UFC and FUFC decline. Clearly, the effective utility of FUFC can be significantly higher than that of UFC. Meanwhile, the effective utilities of the flows in FUFC are closer to each other than those in the UFC approach, indicating that better fairness among effective utilities is achieved by FUFC. The gain of FUFC over UFC increases as the number of hops increases. Each source increases its flow rate adaptively to compensate for the higher data loss as the number of hops increases.Figure 9
The effective utilitiesU2 and U4 in UFC and FUFC.We can see from Figure10 that, with decreasing the number of faulty links, the rate allocation is convergent to the rate allocation in wireless lossless condition. As discussed in Section 4, the rate region in our algorithm converges to the rate region in the corresponding lossless network while a sequence of link loss rate converges to zero (the number of faulty links converges to zero). The lossy utility max-min fairness can be achieved in our algorithm and converges to the corresponding lossless fairness with a sequence of loss rates converging to 0 in Figure 11. Figures 10 and 11 show the trends of rate region and utility fairness of four sources.Figure 10
The trend of rate allocation.Figure 11
The trend of utility.


## 6. Related Work

There has been much work on resource allocation approaches for providing reliable transmissions (see, e.g., [16–18]). Some of these approaches are obtained as distributed solutions to an optimization problem first motivated by Kelly et al. in [11], with setting fixed reliability constraints. Saad et al. focus on effective rate allocation by maximizing the network utility with quality-of-service (QoS) constraints [18]. Hosseinabadi and Vaidya allocate data rates using a cross-layer approach with the presence of misbehavior nodes [16]. To ensure secure communication, [17] formulate resource allocation as an optimization problem considering QoS metrics and artificial noises. Their work, however, is unable to adjust the effective rate and fairness adaptively in terms of the actual receive-resource at destination nodes. In our work, we define effective utility function associated with the effective rate at receivers and make the fairness objectives involve in optimization problem. Thus, our flow control approach could maintain an acceptable level of network performance degradation through getting better fairness and more effective utility in the presence of misbehaving nodes.Existing techniques for secure communication under misbehaving nodes provide methods for reaction to misbehaviors by classifying each receiving node as either faulty or regular. For example, the authors of [19] provide a technique to divide the network links into reliable and unreliable ones and route around the region of the network being faulty, and the authors of [20] propose an approach to detect misbehaving nodes and perform coordinated channel-hopping. However, the state of being faulty at each node is uncertain under random attacks, smart attacks, or stochastic software/hardware failures. Our approach incorporates the impact of potential dynamic faults into the traffic allocation and routing protocol and provides sufficient protection from stationary failures, mobile interferences, and the uncertain losses from the various environments.Rate control stack design has been studied for the Internet in the 90s. Recently, rate control mechanisms for wireless networks are studied in [21–23]. The basic idea is that each application attains concave utility function and, thus, is appropriate only for homogeneous traffic. Further, Lee et al. [24] show that instability may be caused by heterogeneous traffic without appropriate rate controllers. Wang et al. [12] have provided a rate control framework that is able to deal with various types of traffic, such that the resulting utility is proportional fair. All these results are based on the assumption of nonadversarial environments where each wireless node is cooperative and well-behaved.


## 7. Conclusion

In this paper, we studied the problem of traffic allocation across multiple routing paths for heterogeneous data sources in the presence of misbehaving nodes whose effects can be characterized statistically. We have presented methods for each network node to estimate the impact of misbehaving nodes and for data sources to these estimates into our traffic allocation and routing algorithm. We formulated multiple-path traffic allocation as a lossy network flow optimization problem based on leaky-path model. In order to handle heterogeneous traffic, we extended the concept of solving the lossy network flow optimization problem which maximizes effective relaxed utility function and proposed a FUFC algorithm to allocate the effective rate in lossy utility fair manner. We showed that considerable gains in effective network utility and utility fairness among heterogeneous sources are achieved by the FUFC approach.



---

*Source: 9749581-2017-09-17.xml*