An on‐demand data broadcasting scheduling algorithm based on dynamic index strategy

On‐demand data broadcasting scheduling is an effective wireless data dissemination technique. Existing scheduling algorithms usually have two problems: (1) with the explosive growth of mobile users and real‐time individual requirements, broadcasting systems present a shortage of scalability, dynamics and timeliness (request drop ratio); (2) with the growth of intelligent and entertained application, energy consumption of mobile client cannot be persistent (tuning time). This paper proposes an effective scheduling algorithm LxRxW. It takes into account the number of lost requests during next item broadcasting time, the number of requests and the waiting time. LxRxW can reduce the request drop ratio. At the same time, the algorithm employs a dynamic index strategy to put forward a dynamic adjusting method on the index cycle length (DAIL) to determine the proper index cycle. Extensive experimental results show that the LxRxW algorithm has better performance than other state‐of‐the‐art scheduling algorithms and can significantly reduce the drop ratio of user requests by 40%–50%. The request drop ratio and accessing time of LxRxW with index increase by 1%–2% than LxRxW algorithm without index, but the tuning time decreases by 70%. The index strategy shows that when the index cycle length is less than 20units, it can significantly reduce the average tuning time but when the index cycle length continues increasing, the average tuning time will increase contrarily. DAIL can dynamically determine the length of index cycle. Moreover, it can reach optimal integrated performance of the request drop ratio, the average accessing time and the average tuning time. Copyright © 2013 John Wiley & Sons, Ltd.     

服务感知的移动P2P流媒体系统视频片调度算法

与有线网络相比,目前移动互联网的带宽普遍较低.这种情况下,如果移动P2P流媒体系统中用户节点上行带宽的利用率不高,将会极大地加重视频源服务器的负载,增加播放延时.为了充分地利用移动节点的上行带宽,缩短播放延时,文中提出了服务感知的视频片调度算法,它由请求算法和服务算法两部分组成.请求节点会根据最近的服务状况动态地调整请求的片数,减少服务拥塞的发生.服务节点会根据请求的优先级合理地安排上传顺序,提高服务的效率.仿真结果表明,该算法很好地适应了移动网络带宽低的情况,能够提高上行带宽的利用率,缩短播放延时.     

LTE基于QoS业务的比例公平调度算法研究

首先介绍目前无线通信中常用的3种调度算法。为了提高频谱利用率,通过仿真比较了3种常用调度算法对系统性能的影响,提出基于QoS(服务质量)业务的比例公平调度算法。该调度算法兼容了其他调度算法的优点。实验中对用户配置不同的QoS参数,从吞吐量的角度来验证不同配置的用户有不同的吞吐量,而且系统会优先保障最优用户的需求。该调度算法提高了系统的最大吞吐量,满足了用户调度的公平性,给用户提供了不同的业务服务,保障了用户的不同需求。     

Real-Time Data Delivery Using Prediction Mechanism in Mobile Environments

Mobile data delivery is a critical issue in the mobile computing area. One of the most important problems is the efficient access to data. A proposed solution to this problem is the prefetching technique which consists in putting in reserving the information before the users need it. Low bandwidth, unreliable wireless links, and frequent disconnections of mobile environments make it difficult to satisfy the timing requirements of traditional strategies. This paper investigates broadcast scheduling strategies for push-based broadcast with timing constraints in the form of deadlines ,and proposes a prediction algorithm based on Kalman filter theory for this study. The proposed dissemination policy and adaptive bandwidth allocation scheme obtain sufficient conditions such that all the time-bounded traffic sources satisfy their timing constraints to provide various quality of service guarantees in the broadcast period. Our goal is to identify scheduling algorithms for broadcast systems that ensure requests meeting their deadlines. Our approach examines the performance of traditional real-time strategies and mobile broadcasting strategies, and demonstrates that traditional real-time algorithms do not always perform the best in mobile environments. The proposed design indeed achieves good performance in mobile environments.     

A Cost-Efficient Scheduling Algorithm of On-Demand Broadcasts

In mobile wireless systems data on air can be accessed by a large number of mobile users. Many of these applications including wireless internets and traffic information systems are pull-based, that is, they respond to on-demand user requests. In this paper, we study the scheduling problems of on-demand broadcast environments. Traditionally, the response time of the requests has been used as a performance measure. In this paper we consider the performance as the average cost of request composed of three kinds of costs – access time cost, tuning time cost, and cost of handling failure request. Our main contribution is a self-adaptive scheduling algorithm named LDFC, which computes the delay cost of data item as the priority of broadcast. It costs less compared with some previous algorithms in this context, and shows good adaptability as well even in pure push-based broadcasts.     

Adaptive low‐priority transfer for high bandwidth and delay product networks

As the exponential growth of the Internet, there is an increasing need to provide different types of services for numerous applications. Among these services, low‐priority data transfer across wide area network has attracted much attention and has been used in a number of applications, such as data backup and system updating. Although the design of low‐priority data transfer has been investigated adequately in low speed networks at transport layer, it becomes more challenging for the design of low‐priority data transfer with the adaptation to high bandwidth delay product networks than the previous ones. This paper proposes an adaptive low‐priority protocol to achieve high utilization and fair sharing of links in high bandwidth delay product networks, which is implemented at transport layer with an end‐to‐end approach. The designed protocol implements an adaptive congestion control mechanism to adjust the congestion window size by appropriate amount of spare bandwidth. The improved congestion mechanism is intent to make as much use of the available bandwidth without disturbing the regular transfer as possible. Experiments demonstrate that the adaptive low‐priority protocol achieve efficient and fair bandwidth utilization, and remain non‐intrusive to high priority traffic. Copyright © 2016 John Wiley & Sons, Ltd.     

Adaptive Realtime Bandwidth Allocation for Wireless Data Delivery

The combination of broadcast and on-demand data delivery services is an economic way to build a highly scalable wireless information system with limited bandwidth. The use of data broadcasting should be adaptive so that the system response time can always be minimized. A traditional approach requires the development of a system response time equation in order to find the optimal solution. However, obtaining such an equation is not always possible. We observe that by maintaining a certain level of on-demand request arrival rate, a close approximation to the optimal solution can be obtained. Using this approach, a real-time adaptive data delivery algorithm is developed. Our algorithm does not require the access information of the data items to be known exactly, which is needed normally for this kind of optimization problems. A simple and low overhead bit vector mechanism is able to capture the relative popularities of the data items. With this information, our algorithm can give a performance comparable to the ideal case in which the access information for each data item is known exactly.     

基于HSDPA的信道相关分组调度算法研究

针对HSDPA(高速下行分组接入)系统中几种支持非实时业务的经典分组调度算法Max C/I(最大载干比)和PF(正比公平)算法缺乏系统公平性的问题,提出一种基于HSDPA的快速公平分组调度算法。此算法在保证信道瞬时条件和系统吞吐量的前提下,旨在为那些平均吞吐量低于某一阈值的用户提供优先被服务的机会。仿真结果表明,此算法较之Max C/I和PF算法能够保证用户间的长期公平性。     

E-UTRA中一种多业务两步比率公平调度算法

符合3GPP多业务处理原则的子信道调度方案是影响E-UTRA系统性能的关键技术。为减少填充和提高多用户分集效应,提出了一种多业务两步比率公平调度算法。在不区分用户业务优先级的情况下,先采用实际缓存量替代传统比率公平算法中的传输速率来分配子信道;业务优先级高的未分配用户再按比率公平算法确认的优先权重从低到高来挤占业务优先级低的用户所分配的子信道,从而确保符合3GPP提出的服务完高优先级业务后再服务低优先级业务的多业务处理原则。仿真结果表明,该算法能在保证用户公平的基础上提高系统吞吐量。     

On-demand data broadcast scheduling based on AHP and GRA methods in wireless broadcast/UMTS integrated systems

The increasing demand for interactive mobile multimedia service is causing the integration of 3rd generation (3G) cellular systems and wireless broadcast systems. The key challenge is to support data dissemination with low response time, request drop rate, and the unfairness of request drop. This article proposes a novel scheduling algorithm called DAG (on-demand scheduling utilizing analytic hierarchy process (AHP) and grey relational analysis (GRA)), which takes multiple factors-waiting time, number of active requests, deadline-into consideration, and models the data scheduling process as a multiple factors' decision-making and best option-selecting process. The proposed approach comprises two parts. The first part applies AHP to decide the relative weights of multiple decision factors according to user requests, while the second adopts GRA to rank the data item alternatives through the similarity between each option and the ideal option. Simulation results are presented to demonstrate that DAG performs well in the multiple criterions mentioned above.     

基于粒子群优化算法的数据中心网络流量调度策略

为解决当前数据中心网络存在链路负载不均衡及带宽资源浪费问题,提出了一种基于粒子群优化算法的流量调度策略.该策略结合软件定义网络控制器可获取全局网络拓扑信息的特性,依据当前链路带宽资源状况及网络流量的带宽需求建立目标函数.首先,根据流的源地址和目的地址找出最短路径集,通过定义粒子聚合度判断算法是否有陷入局部最优的趋势;然后,结合约束条件与目标函数,利用优化的粒子群算法从最短路径集中找出网络流量的最佳调度路径.实验结果表明,相比于其他算法,该算法有效地提高了网络平均吞吐量,获取了较低的丢包率,从而减轻了带宽资源的浪费,更好地实现了网络的负载均衡.     

A hierarchical fair service curve algorithm for link-sharing,real-time, and priority services

We study hierarchical resource management models and algorithms that support both link-sharing and guaranteed real-time services with priority (decoupled delay and bandwidth allocation). We extend the service curve based quality of service (QoS) model, which defines both delay and bandwidth requirements of a class in a hierarchy, to include fairness, which is important for the integration of real-time and hierarchical link-sharing services. The resulting fair service curve (FSC) link-sharing model formalizes the goals of link-sharing, real-time and priority services and exposes the fundamental trade-offs between these goals. In particular, with decoupled delay and bandwidth allocation, it is impossible to simultaneously provide guaranteed real-time service and achieve perfect link-sharing. We propose a novel scheduling algorithm called hierarchical fair service curve (H-FSC) that approximates the model closely and efficiently. The algorithm always guarantees the service curves of leaf classes, thus ensures real-time and priority services, while trying to minimize the discrepancy between the actual services provided to and the services defined by the FSC link-sharing model for the interior classes. We have implemented the H-FSC scheduler in NetBSD. By performing analyzes, simulations and measurement experiments, we evaluate the link-sharing and real-time performances of H-FSC, and determine the computation overhead     

基于实时数据转发系统的资源参数优化

为了应对实际的业务应用需求,在一定程度上提高网络带宽利用率,在一般实时数据转发系统（RTDFS）的基础上．针对该类系统,提出了优化TCP链路和转发缓冲区取值的方法。主要根据转发系统的网络链路状况,以及实时数据到达转发系统的特征,利用排队论的相关理论建立相应的数学模型,并利用影响TCP传输吞吐量的主要参数,计算出系统运行服务器中最佳的转发缓冲区大小和并行的线程数量。实际系统的实现结果表明,标称带宽为2M,实时数据记录端到实时数据转发端的往返时延约为2ms。实时数据转发端到集控中心服务器的往返时延约为154ms的情况下,转发端的缓冲区无限大、多线程个数为4时,系统运行带宽利用率能达到90％以上,并且验证了该数学模型的理论计算。     

A flexible downlink scheduling scheme in cellular packet data systems

Fast downlink scheduling algorithms play a central role in determining the overall performance of high-speed cellular data systems, characterized by high throughput and fair resource allocation among multiple users. We propose a flexible channel-dependent downlink scheduling scheme, named the (weighted) alpha-rule, based on the system utility maximization that arises from the Internet economy of long-term bandwidth sharing among elastic-service users. We show that the utility as a function of per-user mean throughput naturally derives the alpha-rule scheme and a whole set of channel-dependent instantaneous scheduling schemes following different fairness criteria. We evaluate the alpha-rule in a multiuser CDMA high data rate (HDR) system with space-time block coding (STBC) or Bell Labs layered space-time (BLAST) multiple-input multiple-output (MIMO) channel. Our evaluation shows that it works efficiently by enabling flexible tradeoff between aggregate throughput, per-user throughput, and per-user resource allocation through a single control parameter. In other words the Alpha-rule effectively fills the performance gap between existing scheduling schemes, such as max-C/I and proportional fairness (PF), and provides an important control knob at the media-access-control (MAC) layer to balance between multiuser diversity gain and location-specific per-user performance.     

Scheduling data broadcast in asymmetric communication environments

With the increasing popularity of portable wireless computers, mechanisms to efficiently transmit information to wireless clients are of significant interest. The environment under consideration is asymmetric in that the information server has much more bandwidth available, as compared to the clients. In such environments, often it is not possible (or not desirable) for the clients to send explicit requests to the server. It has been proposed that in such systems the server should broadcast the data periodically. One challenge in implementing this solution is to determine the schedule for broadcasting the data, such that the wait encountered by the clients is minimized. A broadcast schedule determines what is broadcast by the server and when. In this paper, we present algorithms for determining broadcast schedules that minimize the wait time. Broadcast scheduling algorithms for environments subject to errors, and systems where different clients may listen to different number of broadcast channels are also considered. Performance evaluation results are presented to demonstrate that our algorithms perform well.     

软件定义时分波分复用无源光网络中基于带宽预测的资源分配策略

针对时分波分复用无源光网络(TWDM-PON)多个光线路终端(OLT)间资源缺乏协同集中调度问题,该文提出一种带有软件定义的基于带宽预测的资源分配策略(RABP)。在光线路终端间,设计粒子群优化的BP神经网络模型预测各光线路终端所需带宽,避免了控制器与光线路终端信息交互时延对资源分配实时性的影响;其次,在光线路终端内,动态设定滑动周期并基于光网络单元授权信息实时统计资源池共享带宽,同时,设计负载均衡的波长调度机制实现多波长的高效利用。仿真结果表明,该策略提高了信道资源利用率,降低了平均包时延。     

K-PSO: An improved PSO-based container scheduling algorithm for big data applications

In recent years, Docker container technology is being applied in the field of cloud computing at an explosive speed. The scheduling of Docker container resources has gradually become a research hotspot. Existing big data computing and storage platforms apply with traditional virtual machine technology, which often results in low resource utilization, a long time for flexible scaling and expanding clusters. In this paper, we propose an improved container scheduling algorithm for big data applications named Kubernetes-based particle swarm optimization(K-PSO). Experimental results show that the proposed K-PSO algorithm converges faster than the basic PSO algorithm, and the running time of the algorithm is cut in about half. The K-PSO container scheduling algorithm and algorithm experiment for big data applications are implemented in the Kubernetes container cloud system. Our experimental results show that the node resource utilization rate of the improved scheduling strategy based on K-PSO algorithm is about 20% higher than that of the Kube-scheduler default strategy, balanced QoS priority strategy, ESS strategy, and PSO strategy, while the average I/O performance and average computing performance of Hadoop cluster are not degraded.     

Soft QoS provisioning using the token bank fair queuing scheduling algorithm

Future-generation wireless packet networks will support multimedia applications with diverse QoS requirements. Much of the research on scheduling algorithms has been focused on hard QoS provisioning of integrated services. Although these algorithms give hard delay bounds, their stringent requirements sacrifice the potential statistical multiplexing performance and flexibility of the packet-switched network. Furthermore, the complexities of the algorithms often make them impractical for wireless networks. There is a need to develop a packet scheduling scheme for wireless packet-switched networks that provides soft QoS guarantees for heterogeneous traffic, and is also simple to implement and manage. This article proposes token bank fair queuing (TBFQ), a soft scheduling algorithm that possesses these qualities. This algorithm is work-conserving and has a complexity of O(1). We focus on packet scheduling on a reservation-based TDMA/TDD wireless channel to service integrated real-time traffic. The TBFQ scheduling mechanism integrates the policing and servicing functions, and keeps track of the usage of each connection. We address the impact of TBFQ on mean packet delay, violation probability, and bandwidth utilization. We also demonstrate that due to its soft provisioning capabilities, the TBFQ performs rather well even when traffic conditions deviate from the established contracts.     

Efficient scheduling algorithms for mixed services in wireless OFDMA system

Orthogonal Frequency Division Multiple Access (OFDMA) is an attracting system for combating the frequency selective fading. It’s widely considered as a promising candidate modulation and access scheme for next generation mobile communication systems. However, the explosive growth of multimedia applications raises higher performance requirements for Radio Resource Management (RRM) in OFDMA system. In particular, limited bandwidth and fierce resource competition impose a challenging issue on the design of packet scheduler. In this paper, we propose two scheduling algorithms applicable to mixed services (i.e., real-time and non-real-time services), that is QoS-oriented Dynamic Threshold Control (DTC) algorithm and fairness-oriented Fairness Aware and QoS Aware (FAQA) algorithm. These two algorithms are both composed of two stages, i.e., initial subcarrier allocation and subcarrier reallocation. For the DTC algorithm, in the stage of initial subcarrier allocation, based on the different metrics to weigh QoS between both services, we design a unique scheduling strategy for each type of service. A dynamic threshold is adopted to help users quickly recover from starvation, so that any one user in system can escape from severely degraded QoS. In the stage of subcarrier reallocation, we will reallocate the surplus subcarriers from the buffer-empty users to the buffer-nonempty users so as to increase spectrum efficiency. For FAQA algorithm, in the stage of initial subcarrier allocation, for the purpose of achieving Proportional Fairness (PF) with lower complexity, we deduce a simple scheduling strategy satisfying PF criterion by means of Greedy algorithm. In the stage of subcarrier reallocation, in order to increase the number of users satisfying QoS requirements, we’ll reallocate the surplus subcarriers from the QoS-satisfied users to the QoS-unsatisfied users. Simulation results demonstrate that, on one hand, the DTC algorithm not only guarantees the quality of both services, but also increases the spectrum efficiency; on the other hand, the FAQA algorithm well maintains the fairness among users, and increases the QoS satisfaction degree at the same time.     

支持优先级与公平策略的队列规程

首先介绍了队列调度算法在流量控制中的关键地位,然后讨论了现有队列调度算法,如基于优先级的调度算法、轮询调度算法与公平队列调度算法,最后提出了一种新的队列规程,该队列规程融合了优先级调度算法与DRR调度算法。在网络正常情况下,不同业务流公平地共享网络带宽,在网络出现拥塞的情况下,高优先级业务流能够抢占带宽,保证其较低的丢包率,并能够实现两种调度算法的快速切换。