Search

(The final version of the chapter does not involve an abstract. Introduction is provided below.) Wireless access has been increasingly popular recently due to portability and low cost of wireless terminals and equipment. The emerging technologies for wireless local area networks (WLANs) are defined by the IEEE 802.11n standard, where physical layer data rates exceeding 200 Mbps are provisioned with multiple input multiple output antenna techniques. However, actual throughput to be experienced by WLAN users is considerably lower than the provided physical layer data rates, despite the link efficiency is enhanced via the frame aggregation concept of 802.11n. In a multi user communication system, scheduling is the mechanism that determines which user should transmit/receive data in a given time interval. Opportunistic scheduling algorithms maximize system throughput by making use of the channel variations and multi user diversity. The main idea is favouring users that are experiencing the most desirable channel conditions at each scheduling instant, i.e. riding the peaks. While maximizing capacity, such greedy algorithms may cause some users to experience unacceptable delays and unfairness, unless the users are highly mobile. In order to remedy this problem, we combine aggregation and opportunistic scheduling approaches to further enhance the throughput of next generation WLANs. We argue that aggregation can dramatically change the scheduling scenario: A user with a good channel and a long queue may offer a higher throughput than a user with better channel conditions but shorter queue. Hence, the statement that always selecting the user with the best channel maximizes throughput is not valid anymore. In this work, we first present our queue aware scheduling scheme that take into account the instantaneous channel capacities and queue sizes simultaneously, named as Aggregate Opportunistic Scheduling (AOS). Detailed simulations results indicate that our proposed algorithm offers significant gains in total system throughput, by up to 53%, as compared to opportunistic schedulers while permitting relatively fair access. We also improve AOS with the principle of relayed transmissions and show the improvements of opportunistic relaying. Later on, we propose another scheduler, which aims to maximize the network throughput over a long time scale. For this purpose, we estimate the statistical evolution of queue states and model the 802.11n MAC transmissions using queuing theory by extending the bulk service model. Utilizing the outcomes of the queuing model, we design Predictive Scheduling with time-domain Waterfilling (P-WF) algorithm. P-WF further improves the performance of our queue aware schedulers, as the throughput is maximized by applying the water filling solution to time allocations. This chapter includes an overview of existing literature on opportunistic scheduling for wireless networks in general and presents our proposed algorithms with comparative detailed performance analysis as they are applied into the next generation WLANs.

In the bounded delay buffer management problem unit size packets arrive online to be sent over a network link. The objective is to maximize the total weight of packets sent before their deadline. In this paper we are interested in the two-valued variant of the problem, where every packet has either low (1) or high priority weight ( α > 1 ). We show that the optimal randomized competitive ratio against an oblivious adversary is 1 + ( α − 1 ) ∕ ( α 2 + α ) .

Efficiently scheduling various service classes while fulfilling performance targets is one of the main challenges in 3GPP Long-Term Evolution (LTE) communication systems. However, Quality of Service (QoS) and fairness provisioning for all different service classes are generally unstable due to insufficient radio resources, especially in heavily loaded states of the network, which leads to the deterioration of overall system performance. In this paper, we address these challenging issues by proposing a two-level downlink scheduling algorithm to deliver all traffic types while attempting to provide a compromise for the LTE performance targets. For the higher level of the algorithm, a coherent resource distribution approach is developed by applying a game theory model in a nested manner to provide per-class fairness. At the lower level, the greedy-knapsack algorithm is properly tailored to optimally allocate resources to the best potential bearers for QoS and throughput enhancement. The performance of the proposed algorithm was evaluated for normal and overload states of the network. The simulation results clearly demonstrate that the proposed scheduling algorithm, compared with the reference scheduling algorithms, provides the best tradeoff for fairness, throughput, and QoS performance in terms of packet loss rate and packet latency for different service classes.

This paper focuses on the design of provably efficient online link scheduling algorithms for multi-hop wireless networks. We consider single-hop traffic and the one-hop interference model. The objective is twofold: 1) maximizing the throughput when the flow sources continuously inject packets into the network, and 2) minimizing the evacuation time when there are no future packet arrivals. The prior work mostly employs the link-based approach, which leads to throughput-efficient algorithms but often does not guarantee satisfactory evacuation time performance. In this paper, we propose a novel Node-based Service-Balanced (NSB) online scheduling algorithm. NSB aims to give scheduling opportunities to heavily congested nodes in a balanced manner, by maximizing the total weight of the scheduled nodes in each scheduling cycle, where the weight of a node is determined by its workload and whether the node was scheduled in the previous scheduling cycle(s). We rigorously prove that NSB guarantees to achieve an efficiency ratio no worse (or no smaller) than 2/3 for the throughput and an approximation ratio no worse (or no greater) than 3/2 for the evacuation time. It is remarkable that NSB is both throughput-optimal and evacuation-time-optimal if the underlying network graph is bipartite. Further, we develop a lower-complexity NSB algorithm, called LC-NSB, which provides the same performance guarantees as NSB. Finally, we conduct numerical experiments to elucidate our theoretical results., Comment: This paper was accepted for publication in IEEE Transactions on Mobile Computing. A preliminary version of the paper was presented at IEEE INFOCOM 2016

Despite extensive studies on optimal power allocation, how to design an efficient joint user scheduling and power allocation scheme for uplink multiuser networks remains largely unexplored. This study investigates joint opportunistic user scheduling and power allocation in uplink multiuser networks to maximise user throughput subject to the power and resource sharing constraints . By exploiting the cumulative distribution function-based scheduling method, the authors first characterise the optimal power allocation subject to both long-term and short-term power constraints. Instead of calculating the transmit power in an iterative and central manner, users can independently decide their instantaneous transmit power in the proposed scheme, which facilitates the algorithm implementation for each user in uplink networks. The closed-form throughput of the proposed scheme is also derived, which can provide an efficient way to estimate and evaluate user performance. Numerical results reveal that compared with several benchmark schemes, the proposed scheme improves throughput performance significantly.

Many big-data computing applications have been deployed in cloud platforms. These applications normally demand concurrent data transfers among computing nodes for parallel processing. It is important to find the best transfer scheduling leading to the least data retrieval time—the maximum throughput in other words. However, the existing methods cannot achieve this, because they ignore link bandwidths and the diversity of data replicas and paths. In this paper, we aim to develop a max-throughput data transfer scheduling to minimize the data retrieval time of applications. Specifically, the problem is formulated into mixed integer programming, and an approximation algorithm is proposed, with its approximation ratio analyzed. The extensive simulations demonstrate that our algorithm can obtain near optimal solutions.

Network navigation is a promising paradigm for providing location awareness in wireless environments, where nodes estimate their locations based on sensor measurements and prior knowledge. In the presence of limited wireless resources, only a subset rather than all of the node pairs can perform inter-node measurements. The procedure of selecting node pairs at different times for inter-node measurements, referred to as network scheduling, affects the evolution of the localization errors. Thus, it is crucial to design efficient scheduling strategies for network navigation. This paper introduces situation-aware scheduling that exploits network states to select measurement pairs, and develops a framework to characterize the effects of scheduling strategies and of network settings on the error evolution. In particular, both sufficient and necessary conditions for the boundedness of the error evolution are provided. Furthermore, opportunistic and random situation-aware scheduling strategies are proposed, and bounds on the corresponding time-averaged network localization errors are derived. These strategies are shown to be optimal in terms of the error scaling with the number of agents. Finally, the reduction of the error scaling by increasing the number of simultaneous measurement pairs is quantified.

This paper presents a framework for balancing fairness and efficiency in the collaborative networks (CNs) of enterprises. In any CN, the collaboration process often leads to a dilemma: the need to choose between fairness and efficiency. The objective of this research is to propose an algorithm that attempts to increase optimal weights of fairness while maintaining efficiency. In this research, two concepts are utilized to distinguish the balance between fairness and efficiency in CNs: 1) the generalized α-fair concept; and 2) Jain's fairness index. The performance of the proposed algorithm has been tested with conceptual heterogeneous and homogeneous CNs (HeCNs and HoCNs, respectively) based on the enterprise capacity. The experimental results indicate that a balance between efficiency and fairness in CNs is possible while forming a network and obtaining mutual benefits fairly among the enterprises. In addition, the proposed algorithm can minimize the deviation between most and least beneficial enterprises in CN in terms of total profit, lost sale cost, and inventory cost.

Device-to-device (D2D) communication can improve coverage, spectrum efficiency, and energy efficiency based on the current cellular network architecture. The fair scheduling for D2D communication in the orthogonal frequency division multiple access-based cellular network is studied in this paper. Based on the proportional fairness criteria, the optimization objective is formulated to maximize the sum of the relative achievable rate of both cellular users (CUs) and D2D pairs. It is a hybrid optimization problem since it involves in both the resource reuse and the transmit power control. A practical proportional fairness scheduling (PFS) algorithm is proposed. Firstly, the admissible area is decided according to the transmit power limitation of terminals and the quality of service (QoS) requirement. Next, we seek the optimal transmit power combination for the CU and D2D pair in the admissible area and it is demonstrated that the optimal value can be selected from several points on the border of the admissible area. Lastly, when multiple subchannels can be employed for scheduling, based on the generated bipartite graph, Hungarian algorithm is adopted to realize maximum matching, i.e., select reusable CUs and D2D pairs to maximize the sum of the relative achievable rates. The simulation results show that PFS algorithm can guarantee the excellent performance of both throughput and fairness.

© 1967-2012 IEEE. Multicasting is emerging as an efficient method to deliver the same data to a group of users, thereby saving network resources. The fairness between different multicast groups is an important quality-of-service (QoS) indication, but it has not been given significant attention. In this paper, we propose a normalized signal-To-noise ratio (SNR)-based fair scheduling for multiple multicast groups in multicast systems. The system fairness and capacity are then analyzed and compared for both fair scheduling and greedy scheduling over independent but non-identically distributed (i.n.d.) fading channels. Closed-form expressions in terms of the system spectral efficiency, outage probability, system fairness, and average bit error rate (BER) are derived in an uncoded/coded M-Ary quadrature amplitude modulation based adaptive transmission multicast system over i.n.d. Rayleigh fading channels. Numerical results show that compared with greedy scheduling, fair scheduling achieves considerably high fairness at the cost of slight system capacity loss, regardless of the number of multicast groups. Our focus is on the physical layer without rate loss, but we also briefly discuss applications of the proposed scheduling in a cross-layer design subject to the loss rate QoS constraint.

Potential benefits of cooperation in wireless networks include improved throughput and reliability, reduced energy consumption and data transfer delay, and extended network coverage and lifetime. The existing works on using cooperative communication at the MAC layer focus on using it either for improving network performance in terms of throughput, delay, spectral efficiency, etc.; or for improving network lifetime and energy efficiency of the nodes. In this paper, we consider enhancing both the network lifetime and throughput by using cooperative communication at the MAC layer. We formulate optimization problems with this objective for both single hop and multi hop networks. The solutions show that network lifetime and throughput can be significantly improved by using cooperative communications to forward packets at the MAC layer. We then propose a distributed cross-layer cooperative MAC protocol for a multi-hop network environment that can improve the network lifetime and energy efficiency while not degrading the network throughput and end-to-end delay. The analytical and simulation results show that the proposed protocol can improve the performance of the network in terms of network lifetime, throughput, end-to-end delay, and energy efficiency.

Optimized cooperative scheduling (OCS) increases the network capacity of the wireless ad hoc network by optimizing relay node selection. This increases the capacity by dividing the long link into too many hops locally and avoids the node failure. OCS decides the best node for the transfer of the file by evaluating its objective function and forming the interference set of the relay node. Random scheduling generalizes the randomization framework to the Signal to Interference plus noise ratio rate-based interference model by dealing with the power allocation problem. It develops a distributed gossip comparison mechanism with the power allocation to maximize the throughput. The comparison of wireless scheduling schemes is done in terms of transmission rate, throughput, jitter, time to schedule packets, latency, end-to-end delay and bandwidth. The performance analysis proves that OCS has high transmission rate, low latency and uses less bandwidth. Random scheduling has high throughput, less time for scheduling of packets, low jitter and smaller at the end to end delay.

Wireless mud-logging systems have been employed in petroleum exploration to guarantee efficiency and safety in well-drilling. For the wireless networks in well-drillings, the tradeoff between throughput and fairness has great relation to the type of wells. The throughput is of the most importance to deep wells, while fairness is of primary concern for shallow wells. In this study, this challenge is addressed by using 2-SIC (successive interference cancellation) techniques. The throughput maximization and the fairness maximization problems are further formulated based on an imperfect 2-SIC model, which differentiates our work from existing ones. In view of the hardness of these problems, a low-complexity approximation algorithm for maximizing throughput and a low-complexity heuristic algorithm for maximizing fairness are proposed. To evaluate the proposed schemes, extensive simulations are performed. According to simulation results, the throughput performance could be improved by 23% using our approximation algorithm of throughput maximization, while the Jain’s fairness index could reach 0.975 using our algorithm of fairness optimization.

Recent results have made a promising case for offering oversubscribed wired data center networks (DCN) with extreme costs. Inter-rack wireless networks are drawing intensive attention to augment such wired DCNs with a few wireless links. Inspired by the promise of easy deployment and plug-and-play, we present VLCcube, a novel inter-rack wireless solution that extends the design of wireless DCN into three further dimensions: (1) all inter-rack links are wireless; (2) there is no imposition of any infrastructure-level alteration on wired production data centers; and (3) it should be plug-and-play, without any need of additional mechanical or electronic control operations. This vision, if realized, will lead to increased flexibility, reduced reconstructing cost, simplified configuration and usage, and outstanding compatibility with existing wired DCNs. Previous proposals, however, are opposed to the last two design rationales. To achieve this vision, the proposed VLCcube augments Fat-Tree, a representative DCN in production data centers, by organizing all racks into a wireless Torus structure via the emerging visible light links. We further present the topology design, hybrid routing, and flow scheduling schemes for VLCcube. Extensive evaluations indicate that VLCcube outperforms Fat-Tree significantly under the existing ECMP flow scheduling scheme, irrespective of the undergoing traffic pattern. Moreover, the performance of VLCcube can be significantly promoted by our congestion-aware flow scheduling scheme. More precisely, compared to ECMP, our flow scheduling scheme makes VLCcube achieve $\times 1.50$ throughput under batched flows, $\mathrm{\times}2.21$ and $\times 2.59$ throughput under two different kinds of online flows.

Due to the rapid development in the transmission of Wireless Network technologies, the need for rate evaluation using network coding demands urgent attention. This is solely dependent on how to improve on high performance communication channels for user’s interest. In this paper, an approach of using queuing theory in a wireless network is presented. The idea of network coding in a wireless environment address the transmission of packets not only in unicast form but also address the conflict in packet movement across a channel. Network coding also contributes greatly in computer communication system and other computer based electronic appliances. This means that a source is transmitting packets to a particular destination according to the user’s needs in a communication system. Packet transmission is enhanced within the wireless network using queuing theory. In this approach, the first routers are set to be the user access router and another directly connected router is set to be the source router. The user access router is set to connect 11 number of other routers where mainly the network coding is conducted. The results show an improvement in transmission rate by applying network coding as compared to other scenarios where networks coding are not utilized or the conventional routing either.

We consider the impact of delayed state information on the performance of centralized wireless scheduling algorithms. Since state updates must be collected from throughout the network, they are inevitably delayed, and this delay is proportional to the distance of each respective node to the controller. In this paper, we analyze the optimal controller placement resulting from this delayed state information. We propose a dynamic controller placement framework, in which the controller is relocated using delayed queue length information at each node, and transmissions are scheduled based on channel and queue length information. We characterize the throughput region under such policies, and find a policy that stabilizes the system for all arrival rates within the throughput region.

In this letter, we consider a cognitive wireless powered communication network (CWPCN), with a secondary wireless powered communication network (WPCN) that has cognitive ability to coexist with a primary communication network. To tackle the unfairness resource allocation issue in CWPCN, we extend proportional fair scheduler to this category of network. By utilizing the time division-based “harvest-then-transmit” protocol, we establish an optimization problem for optimal time slot allocation, which maximizes the bandwidth utility function for proportional fairness, under the constraints of time and interference. To solve this problem, an algorithm is proposed to find a tradeoff between fairness and throughput. Simulation results confirm the positive effect on the promotion of fairness metric.

Software defined networking is an emerging network paradigm which is considered to be the future evolution trend of network, the network efficiency is determined by the controller. A modeling approach is proposed to evaluate the throughput and time delay of the control plane based on queuing theory. The influence of the number of switches and threads on throughput and latency is analyzed. The accuracy of the model is verified by simulation and the results show that the throughput and time delay increase as the number of switches and threads increase. The throughput and latency can be calculated and evaluated effectively by the proposed model.

Single-ISA asymmetric multicore processors (AMPs), which combine high-performance big cores with low-power small cores, were shown to deliver higher performance per watt than symmetric CMPs (Chip Multi-Processors). Previous work has highlighted that this potential of AMP systems can be realizable via OS scheduling. To date, most existing scheduling schemes for AMPs have been designed to optimize the system throughput, but they are inherently unfair. Although fairness-aware schedulers have been also proposed, they fail to effectively deal with user priorities and do not always ensure that equal-priority applications experience a similar slowdown. To overcome these limitations, we propose ACFS, an asymmetry-aware completely fair scheduler that seeks to optimize fairness while ensuring acceptable throughput. Our evaluation on real AMP hardware and using scheduler implementations in the Linux kernel demonstrates that ACFS achieves an average 23% fairness improvement over two state-of-the-art schemes, while providing higher system throughput. Throughput and fairness are largely conflicting optimization goals on AMPs.Previous asymmetry-aware schedulers fail to effectively deal with user priorities.ACFS achieves an average 23% fairness improvement over state-of-the-art schemes.Predicting cross-core performance on current AMPs is one of the major challenges.

Broadband Wireless Networks is growing rapidly due to the increased number of mobile users. The greatest challenge is to achieve maximum throughput with minimal or no interference while performing concurrent transmission. To reduce the interference problem, this paper proposes a cooperative scheduling and channel assignment algorithm for multi-channel wireless mesh networks. In scheduling algorithm, to avoid the primary interference, the proper time slot is assigned through centralized scheduling for the packet and link in a network. The objective of using the scheduling algorithm is to reduce the transmission delay for uplink/downlink networks. Channel assignment algorithm helps to avoid secondary interference and to perform concurrent transmission with an optimal number of channels. In scheduling, the priority of packets contributes to preventing the accumulation of packets and transmission delay in a multi-hop network. Simulation analysis shows that our channel assignment algorithm avoids both interferences with an optimal number of channels.

In this paper, we link the throughput gains, due to transceiver adaptation, in a point-to-point transmission link to the expected gains in a mesh network. We calculate the maximum network throughput for a given topology as we vary the length scale. We show that the expected gain in the network throughput due to transceiver adaptation is equivalent to the gain in a point-to-point link with a length equal to the mean length of the optical paths across the minimum network cut. We also consider upper and lower bounds on the variation of the gain in the network throughput due to transceiver adaptation, where integer-constrained channel bandwidth assignment and quantized adaptations are considered. This bounds the variability of results that can be expected and indicates why some networks can give apparently optimistic or pessimistic results. We confirm the results of previous authors that show finer quantization steps in the adaptive control lead to an increase in the throughput since the mean loss of throughput per transceiver is reduced. Finally, we consider the likely network advantage of digital nonlinear mitigation and show that a significant tradeoff occurs between the increase in the signal-to-noise ratio for larger mitigation bandwidths and the loss of throughput when routing fewer large-bandwidth superchannels.

The recent wireless sensor network applications are resource greedy in terms of throughput and network reliability. However, the wireless shared medium leads to links interferences in addition to wireless losses due to the harsh environment. The effect of these two points translates on differences in links bandwidth capacities, lack of reliability and throughput degradation. In this study, we tackle the problem of throughput maximization by proposing an efficient congestion control-based schedule algorithm, dubbed REFIACC (Reliable, Efficient, Fair and Interference-Aware Congestion Control) protocol. REFIACC prevents the interferences and ensures a high fairness of bandwidth utilization among sensor nodes by scheduling the communications. The congestion and the interference in inter and intra paths hot spots are mitigated through tacking into account the dissimilarity between links’ capacities at the scheduling process. Linear programming is used to reach optimum utilization efficiency of the maximum available bandwidth. REFIACC has been evaluated by simulation and compared with two pertinent works. The results show that the proposed solution outperforms the others in terms of throughput and reception ratio (more than 80%) and can scale for large networks.

This paper presents the sum rate analysis of a saturated $M$ -group multi-rate carrier sense multiple access network, where nodes in different groups have distinct packet transmission rates. An explicit expression of the network sum rate is derived, based on which the maximum sum rate is obtained by optimizing the transmission probabilities of nodes. It is found that to achieve the maximum sum rate, only the group of nodes with the largest transmission rate is allowed to access the channel, which leads to severe unfairness. To ensure certain fairness, two constraints, namely, throughput fairness (TF) and data-rate fairness (DF), are proposed, with which each node acquires a target proportion of the network throughput and the network sum rate, respectively. Explicit expressions of the network maximum sum rate with TF and DF are derived, which show that by including the fairness constraints, the network maximum sum rate becomes inferior to that without fairness constraints as long as there is difference in the transmission rates of nodes. The analysis is further applied to IEEE 802.11 networks, where the optimal initial backoff window sizes of nodes to achieve the network maximum sum rates with both fairness constraints are derived.

Often one would like to allocate shared resources in a fair way. A common and well-studied notion of fairness is Max-Min Fairness , where we first maximize the smallest allocation, and subject to that the second smallest, and so on. We consider a networking application where multiple commodities compete over the capacity of a network. In our setting, each commodity has multiple possible paths to route its demand (for example, a network using Multiprotocol Label Switching (MPLS) tunneling). In this setting, the only known way of finding a max-min fair allocation requires an iterative solution of multiple linear programs. Such an approach, although polynomial time, scales badly with the size of the network, the number of demands, and the number of paths, and is hard to implement in a distributed environment. More importantly, a network operator has limited control and understanding of the inner working of the algorithm. In this article we introduce Upward Max-Min Fairness, a novel relaxation of Max-Min Fairness, and present a family of simple dynamics that converge to it. These dynamics can be implemented in a distributed manner. Moreover, we present an efficient combinatorial algorithm for finding an upward max-min fair allocation. This algorithm is a natural extension of the well-known Water Filling Algorithm for a multiple path setting. We test the expected behavior of this new algorithm and show that on realistic networks upward max-min fair allocations are comparable to the max-min fair allocations both in fairness and in network utilization.

In this paper, we investigate the problem of bandwidth allocation in wireless sensor network (WSN) under signal to noise plus interference ratio interference model, which aims at finding a tradeoff between fairness and network throughput. Specifically, we propose an approximate algorithm to solve this problem since it has been proved to be NP-hard. Different from similar algorithms proposed in previous issues, we maximize two utility functions, which are the newly defined bandwidth utility function for fairness and network throughput, by jointly considering sensor nodes association and resource allocation in WSN. In addition, we formulate a new utility function with respect to bandwidth allocation, with the method of weighted sum of two objectives as one objective function, which will find a tradeoff between fairness and throughput. Consequently, the problem is decomposed into two sub-problems and solved in two stages, which are cluster formation stage and scheduling stage. In the first stage, we let sensor nodes join to cluster head nodes, which can determine the association of sensor nodes; in the second stage, the total utility function is maximized by allocating time slots for tradeoff between fairness and throughput. Finally, simulation results demonstrate that our algorithm can achieve better performance than compared algorithms.

There have been some rapid advances on the design of full duplex (FD) transceivers in recent years. Although the benefits of FD have been studied for single-hop wireless communications, its potential on throughput performance in a multi-hop wireless network remains unclear. As for multi-hop networks, a fundamental problem is to compute the achievable end-to-end throughput for one or multiple communication sessions. The goal of this paper is to offer some fundamental understanding on end-to-end throughput performance limits of FD in a multi-hop wireless network. We show that through a rigorous mathematical formulation, we can cast the multi-hop throughput performance problem into a formal optimization problem. Through numerical results, we show that in many cases, the end-to-end session throughput in a FD network can exceed $2 \times$ of that in a half duplex (HD) network. Our finding can be explained by the much larger design space for scheduling that is offered by removing HD constraints in throughput maximization problem. The results in this paper offer some new understandings on the potential benefits of FD for end-to-end session throughput in a multi-hop wireless network.

In Long-Term Evolution (LTE) and beyond systems, radio resource scheduling mechanism plays one of the main roles in system performance maximization. From this perspective, due to the conflicting quality requirements of different traffic types, providing a compromise among all performance targets for heterogeneous traffic is difficult. Moreover, the centralized scheduling mechanism for the ever growing number of users along with the massive variety of services, especially in overload states, is infeasible due to the extensive cost of information acquisition and computations. In this paper, we design resource scheduling policies for supporting the efficient delivery of heterogeneous traffic in overload states of a cell. To this end, we cast the class-based bearer-level resource distribution problem as a Proportional Fractional Knapsack model. The objective of the formulated problem is to meet Quality of Service (QoS) requirements and provide fairness for all standardized service classes. Since the solution of this problem is computationally expensive, due to the uncertainty and limited information on network and user operation, we develop a Gaussian-based analytical model and drive a formula for simplified computation of the weight of service bearers. Then, we propose Proportional Fractional Knapsack algorithm for guaranteeing effective utilization of resources for heterogeneous traffic. Finally, performance evaluation results are provided and demonstrate that the proposed scheduling approach can provide a significant level of fairness, in balance with the QoS and throughput performance targets, comparable with optimal ones.

Nanotechnology is enabling the development of miniature devices able to perform simple tasks at the nanoscale. The interconnection of such nano-devices with traditional wireless networks and ultimately the Internet enables a new networking paradigm known as the Internet of Nano-Things (IoNT). Despite their promising applications, nano-devices have constrained power, energy, and computation capabilities along with very limited memory on board, which may only be able to hold one packet at once and, thus, requires packets to be delivered before certain hard deadlines. Toward this goal, a fully-distributed computation-light provably-correct scheduling/MAC protocol is introduced for bufferless nano-devices, which can maximize the network throughput, while achieving perpetual operation. More specifically, the proposed scheduling algorithm allows every nano-device to make optimal transmission decisions locally based on its incoming traffic rate, virtual debts, and channel sensing results. It is proven that the proposed algorithm is timely throughput optimal in the sense that it can guarantee reliable data delivery before deadlines as long as the incoming traffic rates are within the derived maximum network capacity region. This feature not only can lead to high network throughput for the IoNT, but also guarantees that the memory of each device is empty before the next packet arrives, thus addressing the fundamental challenge imposed by the extremely limited memory of nano-devices. In addition, the optimal deadline is derived, which guarantees that all the nano-devices can achieve perpetual communications by jointly considering the energy consumption of communications over the terahertz channel and energy harvesting based on piezoelectric nano-generators.

Scheduling tasks close to their data and optimising resources utilisation are both crucial for the efficiency of MapReduce system. On the other hand, there is a conflict between fairness and efficiency. In this study, an efficient and dominant resource held time fairness (EHTF) scheduler is presented, in which the efficient utilisation of resources, data locality and fairness are addressed simultaneously. In EHTF scheduler, the authors introduce the concept of ‘coarse-grained fairness’ to improve the efficiency of MapReduce system. For each scheduling, several tasks from different jobs can be assigned to the free slot without violating the coarse-grained fairness doctrine. To determine the best task from these several tasks in each scheduling step, a score model is proposed by taking into consideration both resources utilisation and data locality. The authors describe the design and implementation of EHTF scheduler. The authors’ experimental results show that EHTF achieves more fairness and better throughput than Fair and Quincy schedulers.

In multihop wireless ad hoc networks, it is important to maintain the outcome fairness of throughput and to maximize the throughput. In this paper, we propose a novel opportunistic scheduling framework by considering outcome fairness and throughput simultaneously. Since the data rate fluctuates intensively due to channel errors, we first devise a data rate estimation method with an adaptive sliding window to accurately and adaptively estimate the data rate. Then, we present a framework together with two mechanisms. The first proposed mechanism is ROSA-WOM, with the weighted objective function method to configure the data rate. The other one is ROSA-MGCF, and it is a maximum total goodput method under a constrained fairness index. The proposed mechanisms are able to schedule the flows fairly even when the data rate of all flows is more than the channel capacity. We establish a testbed to evaluate these two mechanisms. The experiment results show that our proposed mechanisms can not only trade off with different fairness and throughput requirements, but also effectively provide robust service isolation, outcome fairness, and high throughput in the presence of channel errors.

Throughput-optimal scheduling has been heavily investigated given its ability to fully utilize network resources and maintain network stability. Most of the existing throughput-optimal algorithms, including the classic queue-length based MaxWeight algorithm and flow-delay-based MaxWeight algorithm, however, may bring a severe unfairness problem when scheduling transmission control protocol (TCP) controlled flows. As TCP is the dominant transport layer protocol in the Internet and it controls the majority of Internet traffic, we study how to design the scheduling algorithm that can ensure both throughput optimality and be compatible to TCP flows. In this paper, we analyze the reason behind the incompatibility between the existing scheduling algorithms and TCP, and then investigate the properties of the head-of-line access delay-based scheduling algorithm (HOLD) we proposed. We prove that the proposed HOLD can fairly schedule TCP flows in wireless networks with time-varying channel conditions and achieve throughput optimality with flow-level dynamics. Simulations using OMNeT++ 4 have been conducted to validate our analytical results, and compare the performance of different scheduling algorithms comprehensively.

To efficiently trade off system sum rate and link fairness, power allocation in wireless spectrum-sharing networks often concentrates upon proportional fairness. The corresponding problem has been proved to be convex for a single tone but NP-hard for more than two tones. However, in the two-tone case, the complexity of the problem for achieving proportional fairness has not been addressed yet. In this paper, we prove that the issue of proportional-fairness optimization for the two-tone situation is NP-hard by reducing the problem of finding the maximum independent set in an undirected graph to it. Moreover, a computationally efficient algorithm is proposed to provide an efficient suboptimal solution. Simulation results are presented to illustrate the effectiveness of our proposal.

As systems scale toward exascale, many resources will become increasingly constrained. While some of these resources have historically been explicitly allocated, many—such as network bandwidth, I/O bandwidth, or power—have not. As systems continue to evolve, we expect many such resources to become explicitly managed. This change will pose critical challenges to resource management and job scheduling. In this paper, we explore the potential of relaxing network allocation constraints for Blue Gene systems. Our objective is to improve the batch scheduling performance, where the partition-based interconnect architecture provides a unique opportunity to explicitly allocate network resources to jobs. This paper makes three major contributions. The first is substantial benchmarking of parallel applications, focusing on assessing application sensitivity to communication bandwidth at large scale. The second is three new scheduling schemes using relaxed network allocation and targeted at balancing individual job performance with overall system performance. The third is a comparative study of our scheduling schemes versus the existing scheduler on Mira, a 48-rack Blue Gene/Q system at Argonne National Laboratory. Specifically, we use job traces collected from this production system.

Packets that traverse more hops to the destination will get lower throughput and result in the inter-flow fairness issue.We propose a virtual queue management scheme that does not require the modification of any communication protocol.According to the number of flows, our scheme adjusts the parameters to achieve each flow's fair sharing of channel resource.Our proposed scheme can mitigate the inter-flow fairness problem and effectively improves the quality of video transmission. Due to intra-flow and inter-flow interference problems, the throughput performance decreases dramatically in a multi-hop wireless network. These two kinds of bandwidth unfair sharing problems could cause serious collisions and congestion, hence affecting the performance of multi-hop wireless networks. That is to say, data packets that need to traverse more hops to arrive at the destination will get lower throughput and result in the inter-flow fairness problem. Furthermore, the quality of video transmission is especially poor in traditional multi-hop wireless network environments. Therefore, in this paper, we propose a virtual queue management scheme that does not require the modification of any communication protocol. According to the number of flows, it adjusts the queue management scheme to achieve each flow's fair sharing of channel resource. It also improves the quality of video transmission. Through NS2 simulations, the results show that our proposed scheme can mitigate the inter-flow fairness problem and effectively improves the quality of video transmission. Display Omitted

In face of the explosive surge of mobile data services, spectrum aggregation or carrier aggregation technology has been proposed to improve system throughput and spectrum efficiency (SE) by aggregating licensed and unlicensed spectrum bands. However, the system performances would be severely deteriorated by the channel access collision if the channel access and resource scheduling approaches are not coordinated among different networks in the same spectrum band. Therefore, in order to improve the system throughput and the SE, a fairness-based license-assisted access and resource scheduling scheme are designed for the coexisting systems, incorporating long term evolution-advanced and WiFi systems in the unlicensed band. The optimal sizes of the contention window in the proposed fairness-based channel access approach are obtained in terms of various density ratios between these two systems. Furthermore, a novel resource scheduling approach employing linear programming is proposed to maximize the utility function with the goal of improving the service experience of users and the SE with various spectrum qualities. The theoretical proofs and simulation results verify the enhanced performances of the proposed approaches in terms of key metrics, such as throughput, SE, delay, and packet loss ratio.

Energy consumption has become a main problem of sustainable development in communication networks and how to communicate with high energy efficiency is a significant topic that re- searchers and network operators commonly concern. In this paper, an energy-efficient multicast algorithm in multi-hop wireless networks is proposed aiming at new generation wireless communications. Traditional multi-hop wireless network design only considers either network efficiency or minimum energy consumption of networks, but rarely the maximum energy efficiency of networks. Different from previous methods, the paper targets maximizing energy efficiency of networks. In order to get optimal energy efficiency to build network multicast, our proposed method tries to maximize network throughput and minimize networks' energy consumption by exploiting network coding and sleeping scheme. Simulation results show that the proposed algorithm has better energy efficiency and performance improvements compared with existing methods.

A packet scheduling algorithm used for wireless sensor network meeting the proportional fairness principle is proposed. Based on the weighted round robin (WRR) strategy, the proposed scheduling algorithm allocates different service quota to different traffics according to their average packet arrival rates to guarantee the proportion fairness on the average packet delivery delay and the average packet loss ratio. Since the scheduling algorithm does not perform the high-load operations such as adding time stamps, sorting and so on, it can be implemented easily and is suitable for resource-limited WSN. The proposed algorithm is tested in a wireless sensor network. The performance shows that the scheduling algorithm can guarantee the average packet delivery delay proportional fairness when the average packet delivery delay is used as the performance metric and the average packet loss ratio proportional fairness is realized when all the queues are overflowing and the average packet loss ratio is used as the performance metric.

This paper designs a down-link resource scheduling algorithm for wireless cellular networks to achieve throughput-delay trade-off. The available bandwidth of the down-link is divided into some parallel sub-channels, and each sub-channel can be allocated to one potential user in every time-slot. This problem is modeled as a multi-user multi-server discrete-time queuing system with a time-varying connectivity. For this system, it is well-known that the classical MaxWeight algorithm has the optimal throughput, but its delay performance is very poor. To overcome this issue, we use the Lyapunov Optimization technique to design a throughput-utility maximizing algorithm that provides a good trade-off between the throughput and delay performance. Our approach is verified by both theoretical analysis and simulation evaluations.

Network coding has been shown to offer significant throughput benefits over certain wireless network topologies. However, the application of network coding may not always improve the network performance. In this paper, we first provide an analytical study, which helps in assessing when network coding is preferable to a traditional store-and-forward approach. Interestingly, our study reveals that in many topological scenarios, network coding can in fact hurt the throughput performance; in such scenarios, applying the store-and-forward approach leads to higher network throughput. We validate our analytical findings via extensive testbed experiments. Guided by our findings as our primary contribution, we design and implement PACE, a Policy-Aware Coding Enforcement logic that enables network coding only when it is expected to offer performance benefits. Specifically, PACE leverages a minimal set of periodic link quality measurements in order to make per-flow online decisions with regards to when network coding should be activated, and when store-and-forward is preferable. It can be easily embedded into network-coding-aware routers as a user-level or kernel-level software utility. We evaluate the efficacy of PACE via: 1) ns-3 simulations, and 2) experiments on a wireless testbed. We observe that our scheme wisely activates network coding only when appropriate, thereby improving the total network throughput by as much as 350% in some scenarios.

Research on the smart grid is being given enormous supports worldwide due to its great significance in solving environmental and energy crises. Electric vehicles (EVs), which are powered by clean energy, are adopted increasingly year by year. It is predictable that the huge charge load caused by high EV penetration will have a considerable impact on the reliability of the smart grid. Therefore, fair energy scheduling for EV charge and discharge is proposed in this paper. By using the vehicle-to-grid technology, the scheduler controls the electricity loads of EVs considering fairness in the residential distribution network. We propose contribution-based fairness, in which EVs with high contributions have high priorities to obtain charge energy. The contribution value is defined by both the charge/discharge energy and the timing of the action. EVs can achieve higher contribution values when discharging during the load peak hours. However, charging during this time will decrease the contribution values seriously. We formulate the fair energy scheduling problem as an infinite-horizon Markov decision process. The methodology of adaptive dynamic programming is employed to maximize the long-term fairness by processing online network training. The numerical results illustrate that the proposed EV energy scheduling is able to mitigate and flatten the peak load in the distribution network. Furthermore, contribution-based fairness achieves a fast recovery of EV batteries that have deeply discharged and guarantee fairness in the full charge time of all EVs.

We propose a new fair queueing scheme which we call Channel-Independent Throughput-based Fair Queueing (CITFQ) without using virtual time system. In our CITFQ scheme, each flow is equipped with a counter that measures the weighted throughput achievement if it has a backlog of packets. Our CITFQ scheme achieves fairness guarantees, short term fairness for error-free flows, long term fairness for error flows, and graceful degradation for flows which have received extra service.

Fairness is an important property of computer networks and systems. In a wide range of these systems such as distributed multi-hop wireless networks, multihomed networks, and cloud computing, each user may be allocated a number of system resources; this resembles a many-to-many relationship between the sets of users and resources, which raises the problem of system-wide fair resource allocation. In this paper, we assume that each user/node can be allocated a number of resources, which could be either in its neighborhood or far from it. As a key difference with previous works and through incorporating the concept of “flow”, we model near/far resources allocated to nodes. To attain fair flow control in such systems, first we model this situation by introducing a new multi-server system called multi-ring , in which a server that represents a resource, can serve only a subset of either neighboring or far nodes in the system. Then, we define a centralized optimization problem to attain weighted proportional fairness among all nodes meaning that the sum of allocated capacities from all servers to each node (while considering its flow) is fair. We evaluate fairness properties of multi-ring networks and provide conditions on system parameters under which a system can have a fair resource allocation. Moreover, we present a distributed method to attain fairness in distributed environments, and its stability/convergence is evaluated by non-linear discrete dynamical systems. We present conditions under which the system is stable, and through numerical analysis, we show how to obtain stable system parameters for large systems. The effectiveness of the presented method is studied through extensive numerical evaluation. Results show the success of our method in attaining fairness for various topologies and system parameters, and confirm our stability analysis. A number of systems with fairness issues are also studied as potential applications of our model.

Wireless link scheduling is one of the major challenging issues in multi-hop wireless networks when they need to be designed in distributed fashion. This paper improves the general randomized scheduling method by using learning automata based framework that allows throughput optimal scheduling algorithms to be developed in a distributed fashion. A distributed scheduling algorithm that operates on more realistic conflict graph was proposed based on the physical interference model. This model uses a combination of a distributed learning automata based on the pick algorithm and an algorithm that compares successive scheduling solutions. Comparison was made by creating spanning tree on the conflict graph of the two consecutive schedules. Briefly, a distributed scheduling schemes was proposed, that: (i) is throughput optimal, (ii) intelligently choose links for new schedule, and (iii) message and time complexity is in O(n3).

We propose a flow-oriented global path and bandwidth scheduling scheme for inter-data-center IP/optical network. To improve the throughput of network and reduce the mutual impact between flows, we allow each flow to be carried by a multi-path optical channel data unit (ODU) channel. In addition bandwidth is allocated to flows fairly according to weight. Simulation results reveal that compared to high-priority-first mechanism, the method proposed improves average bandwidth allocation ratio by about 15% and allocation fairness between flows by 30%. Furthermore, compared to pure IP network, router ports are significantly saved and network cost can be reduced by up to 40% with scheme proposed in unified controlled IP/optical network.

Delay-tolerant networks are sparse mobile ad hoc networks in which there is typically no complete path between the source and destination. Although many routing schemes for delay-tolerant networks have been proposed, they do not address fairness issues in terms of the workload/traffic handled at each node and the share of throughput among different destination nodes. In this paper, we propose a socially aware routing strategy that optimizes both fairness and throughput. A relay node is selected based on the multi-hop delivery probability and its queue length. The effect of queue length control is to divert traffic away from highly connected nodes and allows nodes to explore less-congested paths to the destination. This helps balance the network loads, thus achieving workload fairness. Furthermore, to achieve throughput fairness, we sort arriving messages into different destination-based queues. Messages are then scheduled following a two-level forwarding strategy that optimizes throughput fairness using round-robin and delivery ratio using priority scheduling. Extensive real-trace-driven simulation results show that our scheme outperforms existing algorithms in terms of the delivery ratio. Furthermore, our scheme achieves a high throughput fairness, while distributing the network loads more evenly, with the top 10% of network nodes handling only 22% of the forwardings. Copyright © 2016 John Wiley & Sons, Ltd.

We study an one-hop device-to-device (D2D) assisted wireless caching network, where popular files are randomly and independently cached in the memory of end-users. Each user may obtain the requested files from its own memory without any transmission, or from a helper through an one-hop D2D transmission, or from the base station (BS). We formulate a joint D2D link scheduling and power allocation problem to maximize the system throughput. However, the problem is non-convex and obtaining an optimal solution is computationally hard. Alternatively, we decompose the problem into a D2D link scheduling problem and an optimal power allocation problem. To solve the two subproblems, we first develop a D2D link scheduling algorithm to select the largest number of D2D links satisfying both the signal to interference plus noise ratio (SINR) and the transmit power constraints. Then, we develop an optimal power allocation algorithm to maximize the minimum transmission rate of the scheduled D2D links. Numerical results indicate that both the number of the scheduled D2D links and the system throughput can be improved simultaneously with the Zipf-distribution caching scheme, the proposed D2D link scheduling algorithm, and the proposed optimal power allocation algorithm compared with the state of arts., Comment: This manuscript has been submitted to TCOM

Network transport is an important aspect of geographical information science, transportation, complex networks, etc. Previous studies have shown that the transport capacity of street networks can be enhanced by improving routing algorithms. However, the upper throughput limit of street networks is unknown in detail. This article studies the transport process of networks and finds that any connected network has a maximum throughput depending on the topological and structural properties of the network. Based on this, the maximum throughput of street networks is obtained. Experiments show that when the street network remains unchanged, the maximum throughput of the street network is limited and is dependent on road capacity and average path length, regardless of adopted routing algorithms. Our findings suggest that the throughput of networks can be improved by increasing node capacity or decreasing average path length, but the maximum transport capacity of the network cannot be greater than the ratio of the sum of all the nodes' capacities to the average path length of the network, no matter what routing strategies are adopted. This study is expected to be a starting point for more sophisticated research in network transport, such as evaluating the inherent throughput of an urban street network.