Fairness-related challenges in mobile opportunistic networking

The fundamental challenge in opportunistic networking, regardless of the application, is when and how to forward a message. Rank-based forwarding techniques currently represent one of the most promising methods for addressing this message forwarding challenge. While these techniques have demonstrated great efficiency in performance, they do not address the rising concern of fairness amongst various nodes in the network. Higher ranked nodes typically carry the largest burden in delivering messages, which creates a high potential of dissatisfaction amongst them. In this paper, we adopt a real-trace driven approach to study and analyze the trade-offs between efficiency, cost, and fairness of rank-based forwarding techniques in mobile opportunistic networks.Our work comprises three major contributions. First, we quantitatively analyze the trade-off between fair and efficient environments. Second, we demonstrate how fairness coupled with efficiency can be achieved based on real mobility traces. Third, we propose FOG, a real-time distributed framework to ensure efficiency–fairness trade-off using local information. Our framework, FOG, enables state-of-the-art rank-based opportunistic forwarding algorithms to ensure a better fairness–efficiency trade-off while maintaining a low overhead. Within FOG, we implement two real-time distributed fairness algorithms; Proximity Fairness Algorithm (PFA), and Message Context Fairness Algorithm (MCFA). Our data-driven experiments and analysis show that mobile opportunistic communication between users may fail with the absence of fairness in participating high-ranked nodes, and an absolute fair treatment of all users yields inefficient communication performance. Finally our analysis shows that FOG-based algorithms ensure relative equality in the distribution of resource usage among neighbor nodes while keeping the success rate and cost performance near optimal.     

RMP: fault-tolerant group communication

Based on a logical token ring, this communication protocol ensures total message ordering and atomic delivery, so all group members maintain an identical view of ordered events. RMP (Reliable Multicast Protocol) is an efficient multicast protocol for general distributed applications based on the logical token ring approach. The novelty of RMP is that it simultaneously multicasts an ordered message and implicitly rotates the token position on the ring. There is no token transfer message in the normal multicast. For message atomicity, our protocol minimizes control messages and communication costs while incurring a relatively short delay. In contrast to other token algorithms, RMP does not risk losing the token when the token site fails. Without requiring extra overhead, our approach guarantees total ordering of messages and message atomicity-either every member receives a message, or none do     

An Adaptive Causal Ordering Algorithm Suited to Mobile Computing Environments

Causal message ordering is required for several distributed applications. In order to preserve causal ordering, only direct dependency information between messages, with respect to the destination process(es), need be sent with each message. By eliminating other kinds of control information from the messages, the communication overheads can be significantly reduced. In this paper we present an algorithm that uses this knowledge to efficiently enforce causal ordering of messages. The proposed algorithm does not require any prior knowledge of the network topology or communication pattern. As computation proceeds, it acquires knowledge of the communication pattern and is capable of handling dynamically changing multicast communication groups, and minimizing the communication overheads. With regard to communication overheads, the algorithm is optimal for the broadcast communication case. Extensive simulation experiments demonstrate that the algorithm imposes lower communication overheads than previous causal ordering algorithms. The algorithm can be employed in a variety of distributed computing environments. Its energy efficiency and low bandwidth requirement make it especially suitable for mobile computing systems. We show how to employ the algorithm for causally ordered multicasting of messages in mobile computing environments.     

Decoupled speed scaling: Analysis and evaluation

In this paper, we introduce the notion of decoupled speed scaling, wherein the speed scaling function is completely decoupled from the scheduling policy used in a simple single-server computer system. As an initial result, we first demonstrate that the Fair Sojourn Protocol (FSP) scheduling policy does not work properly with coupled (native) speed scaling, but that it can and does work well with decoupled speed scaling. We then compare the performance of PS, SRPT, and FSP scheduling policies under decoupled speed scaling, and demonstrate significant advantages for FSP. Our simulation results suggest that it might be possible to simultaneously achieve fairness, robustness, and near optimality with decoupled speed scaling.     

结合通信重排和消息合并的通信调度方法研究

网络通信对于高性能计算机应用至关重要。当前,随着数值模拟应用的复杂化和并行规模的不断提升,应用软件对于缓解拥塞和减少通信协议开销的需求愈发迫切。传统的消息合并方法只以减少通信协议开销和延迟为目标,所以针对小消息进行合并。与之不同的是,从调度算法的角度提出了一种通过消息重排以减缓大消息网络拥塞,并基于优先级合并消息来提高网络有效利用率的算法。实验表明,该算法针对真实应用的通信性能最大可以提升41%,平均对每个应用提升了10%。     

A delay-optimal quorum-based mutual exclusion algorithm fordistributed systems

The performance of a mutual exclusion algorithm is measured by the number of messages exchanged per critical section execution and the delay between successive executions of the critical section. There is a message complexity and synchronization delay trade-off in mutual exclusion algorithms. The Lamport algorithm (1978) and the Ricart-Agrawal algorithm (1981) both have a synchronization delay of T (T is the average message delay), but their message complexity is O(N). Maekawa's algorithm reduces the message complexity to O(√N); however, it increases the synchronization delay to 2T. After Maekawa's algorithm (1985), many quorum-based mutual exclusion algorithms have been proposed to reduce the message complexity or the increase the resiliency to site and communication link failures. Since these algorithms are Maekawa-type algorithms, they also suffer from the long synchronization delay. We propose a delay-optimal quorum-based mutual exclusion algorithm which reduces the synchronization delay to T and still has a low message complexity of O(K) (K is the size of the quorum which can be as low as log N). A correctness proof and a detailed performance analysis are provided     

基于直径仲裁集的网格网络分布式互斥算法

分布式互斥是网格分布式系统的重要问题。根据网格系统的特点,提出了新型的分布式互斥算法。该算法基于网格网络的直径生成分布式互斥仲裁集;采用Lamport逻辑时戳保证消息的时序性;算法采用“探测”消息进行系统的容错处理。分析与仿真证明,该算法具有较低的消息复杂度、较短的响应延迟以及较好的容错性能。     

负载均衡Birkhoff-von Neumann交换中的公平调度

负载均衡Birkhoff-vonNeumann交换在设计高性能并保证时延的交换机时具有重要的参考价值,但目前缺少对算法公平性的研究。对基于帧的方案[6](FrameBasedScheme,简称FBS)进行了公平性分析,指出公平性欠缺的主要原因是没有区分流。依据全帧优先(FullFrameFirst,简称FFF)算法[5],提出加权全帧优先算法(简称W-FFF),证明它可提供比FFF算法小的平均时延,支持保证率型服务,并可实现带宽的公平分配。     

主从结构交换式以太网中实时消息调度研究

为使交换式以太网能满足实时通信的要求,针对FTT SE网络调度模型,提出了一种同时适用于周期性和非周期性实时消息的链路可调度性判定方法。在证明了消息链路调度优化问题MLSOP为NP complete的同时,针对周期性实时消息的链路调度优化给出了启发式算法LSHA。最后,对于周期性和非周期性实时消息分别设计了基于EDF的调度算法。仿真实验表明,在提高网络链路带宽利用率和减小消息平均延时方面,该算法均较FTT SE有明显的优势。     

一种间歇性连接移动网络自适应路由协议

为提高间歇性连接移动网络的消息发送效率,提出一种基于移动自组网OLSR协议的自适应路由协议ARPBO。ARPBO在网络连通时通过OLSR协议快速转发消息;在网络中断时对OLSR协议进行扩展,从消息发送节点的局部连通网络中有效选择下一跳节点,然后通过延迟容忍网络的"存储-携带-转发"机制转发消息。实验结果表明,该路由协议能够在网络存在间歇性连接时获得较高的传递成功率和较低的传递时延。     

电力通信网络中高效的OSPF流量负载均衡协议

针对基于开放式最短路径优先（OSPF）协议的电力通信网络中的流量负载不均衡问题,提出两级优化的OSPF（TSO-OSPF）算法,分别对OSPF区域内和区域间进行流量均衡。算法采用带宽利用率和时延作为链路权重,根据路由器的进出总流量,将流量过大的分支分解到多个路由器,实现最大流最小化,从而解决电力通信网区域内部和边界路由器的流量不均衡问题。仿真实验表明：与OSPF算法相比,TSO-OSPF算法有效均衡了网络的流量,并且降低了10%左右的丢包率。     

交通信号的实时公平调度及其仿真

交通信号的实时调度是改善交通拥堵的重要途径之一,其公平性研究同样至关重要。针对通信网络和交通网络的共同特点,借鉴其最大最小公平和比例公平的思想,分别提出最小最大公平、比例公平交通信号实时调度算法;并与优化队列长度的实时调度、固定周期调度算法进行仿真对比。实验结果表明,优化队列长度的实时调度和固定周期调度会使得部分车辆等待时间过长而表现出不公平;最小最大公平调度表现出最好的公平性,但在网络高密度下平均时延表现较差;比例公平调度则在各种交通密度下同时表现出较低的平均时延和较好的公平性。研究结果为实时交通信号的公平调度提供了解决方案,具有较好的应用价值。     

Shortest hop multipath algorithm for wireless sensor networks

Shortest hop or distance path is one of the most common methods used for relaying messages in a wide variety of networks. It provides an efficient message relaying to destination in terms of energy and time. There are many algorithms for constructing shortest hop or distance path. However, according to our knowledge, no algorithm for constructing a shortest hop multipath for wireless sensor networks (WSNs) has yet been proposed in the literature. In this paper, we propose a novel distributed shortest hop multipath algorithm for WSNs in order to generate energy efficient paths for data dissemination or routing. The proposed algorithm generates shortest hop braided multipath to be used for fault-tolerance or load-balancing. It guarantees the BFS tree and generates near optimal paths in O(V.D+V) message complexity and O(D²) time complexity regarding the communication costs towards the sink after termination of algorithm.     

Hierarchical Scheduling for Symmetric Multiprocessors

Hierarchical scheduling has been proposed as a scheduling technique to achieve aggregate resource partitioning among related groups of threads and applications in uniprocessor and packet scheduling environments. Existing hierarchical schedulers are not easily extensible to multiprocessor environments because 1) they do not incorporate the inherent parallelism of a multiprocessor system while resource partitioning and 2) they can result in unbounded unfairness or starvation if applied to a multiprocessor system in a naive manner. In this paper, we present hierarchical multiprocessor scheduling (H-SMP), a novel hierarchical CPU scheduling algorithm designed for a symmetric multiprocessor (SMP) platform. The novelty of this algorithm lies in its combination of space and time multiplexing to achieve the desired bandwidth partition among the nodes of the hierarchical scheduling tree. This algorithm is also characterized by its ability to incorporate existing proportional-share algorithms as auxiliary schedulers to achieve efficient hierarchical CPU partitioning. In addition, we present a generalized weight feasibility constraint that specifies the limit on the achievable CPU bandwidth partitioning in a multiprocessor hierarchical framework and propose a hierarchical weight readjustment algorithm designed to transparently satisfy this feasibility constraint. We evaluate the properties of H-SMP using hierarchical surplus fair scheduling (H-SFS), an instantiation of H-SMP that employs surplus fair scheduling (SFS) as an auxiliary algorithm. This evaluation is carried out through a simulation study that shows that H-SFS provides better fairness properties in multiprocessor environments as compared to existing algorithms and their naive extensions.     

无人机中继通信系统中信息传输调度算法研究

研究了将无人机作为通信中继平台对战区实施无线通信覆盖时的信息传输调度算法.首先介绍了几种基于信息特征(如优先级、长度、信息在系统总的占用时间等)的调度算法.为了克服传统调度算法的缺点,提出了一种改进的动态优先权调度(DPS,Dynamic Priority Scheduling)算法,将信息的优先级与接受系统服务的时间联系起来,动态调整信息的优先权,从而获得较小的系统平均时延,而且对不同信息又不失“公平性“.最后给出了几种调度算法的仿真结果,并对结果进行了分析.分析表明,动态优先权调度算法是一种比较适合无人机通信中继的实用调度算法.     

FC仲裁环实现实时传输的带宽分配方法

考虑实时消息的优先级顺序,对光纤通道仲裁环结构下研究实时性问题的“最差情形”做了补充和完善。重新定义保证数据传输实时性的2个限制条件,提出最差情形公平负载率的概念,从而将上述2个限制条件归结为一条,即要保证所有消息的实时性,必须使每个消息的最差情形公平负载率小于等于1,揭示数据传输的实时性与网络负载率之间的本质联系。考虑对实时消息进行拆分后增加的协议开销和物理层延时等影响因素,基于网络总负载率最小化原则给出一种简洁的带宽分配方法。通过实例仿真研究了仲裁环下假想消息集中的各个实时消息在“最差情形”下的带宽分配情况,证明该算法的正确性。     

一种用于无线网络中实时业务的跨层调度算法

就同时包含了有线链路和无线链路的异构网络上的实时应用,提出了一种满足其端到端服务质量(QoS)需求的无线网络MAC(media access control)层调度算法(real-time cross-layer scheduling algorithm for real-time application,简称RTCLA).该算法采用跨层的思想,结合了自适应调制编码(adaptive modulation and coding,简称AMC)技术和选择性自动请求重传(selective repeat-automatic repeat request,简称SR-ARQ)技术,在满足应用的系统误包率(packet error rate,简称PER)要求、尽可能减少基站中等待超时分组数目的前提下,提高系统吞吐性能和频谱利用率.通过仿真来验证算法分组超时率、平均系统有效吞吐率和公平性3个方面的性能,并与改进的比例公平算法(modifiedpro portional fair,简称MPF)、最早到期优先(earliest deadline first,简称EDF)和改进的最大加权延时优先(modified largest weighted delay first,简称M-LWDF)等3种广泛使用的算法进行了比较.仿真结果还表明,综合考虑实时应用的严格时延要求和无线网络资源稀缺以及信道的时变特性,RTCLA更适合于对时延敏感的实时应用,尤其是分组超时率性能方面表现突出.此外,仿真结果还表明,RTCLA在稳定性方面的表现与其他3种算法基本相同.     

Fundamentals of Scheduling and Performance of Video Tape Libraries

Robotic tape libraries are popular for applications with very high storage requirements, such as video servers. Here, we study the throughput of a tape library system, we design a new scheduling algorithm, the so-called Relief, and compare it against some older/straightforward ones, like FCFS, Maximum Queue Length (MQL) and an unfair one (Bypass), roughly equivalent to Shortest Job First. The proposed algorithm incorporates an aging mechanism in order to attain fairness and we prove that, under certain assumptions, it minimizes the average start-up latency. Extensive simulation experiments show that Relief outperforms its competitors (fair and unfair alike), with up to 203% improvement in throughput, for the same rejection ratio.     

Lifetime maximizing dynamic energy efficient routing protocol for multi hop wireless networks

Energy efficiency is recognized as a critical problem in wireless networks. Many routing schemes have been proposed for finding energy efficient routing paths with a view to extend lifetime of the networks – however it has been observed that the energy efficient path depletes quickly. Further, an unbalanced distribution of energy among the nodes may cause early death of nodes as well as network. Hence, balancing the energy distribution is a challenging area of research in wireless networks. In this paper we propose an energy efficient scheme that considers the node cost of nodes for relaying the data packets to the sink. The node cost considers both the remaining energy of the node as well as energy efficiency. Using this parameter, an energy efficient routing algorithm is proposed which balances the data traffic among the nodes and also prolongs the network lifetime. Simulation shows that proposed routing scheme improves energy efficiency and network lifetime than widely used methods viz., Shortest Path Tree (SPT) and Minimum Spanning Tree (MST) based PEDAP, Distributed Energy Balanced Routing (DEBR) and Shortest Path Aggregation Tree Based Routing Protocol.     

小无线网络中基于BLUF的包调度算法

在无线网络的多用户资源分配中,一个重要的问题就是设计高效的调度算法来保证用户的公平性,并充分利用有限资源和保证用户服务质量要求。提出一种基于缓冲区长度效用函数的多用户包调度（BLUF）算法,该算法充分考虑无线信道的时变特性,用缓冲区长度的效用函数来表示调度的服务质量需求的紧急程度,用户当前信道速率与其获得的平均信道速率的比值表示用户公平性和系统效率的权衡程度。仿真结果表明,与存在的比例公平性无线包调度（PFS）算法相比,BLUF算法能够保证实时任务的时延需求的前提下,获得更好的公平性、系统吞吐量等性能。