最短响应时间优先请求分配算法的研究

分析了在分布式高性能防火墙中两种常用的请求分配算法,在此基础上提出了最短响应时间优先调度算法。仿真表明,该算法具有很好的调度效果和很高的稳定性。     

基于图匹配的多处理机调度算法

本文对具有高通讯延迟的多处理机系统（机群系统）上的任务调度算法进行了研究，与以往算法主要考虑任务图的关键路径不同，本文给出了任务图的调度与其偶图匹配的对应关系，并由此提出了一种新的启发式算法，通过模拟试验显示本算法具有较好的调度效果。     

光网络环境中最先开始路径优先的自适应路由算法

为了优化光网络环境下分布式计算系统的资源调度性能,提出了一种最先开始路径优先的自适应路由算法。该算法基于Dijkstra最短路径优先算法,通过引入一个时间标记变量来估计从源节点到当前目标节点的最先可用时间,绕过调度过程中产生拥堵的链路,选择能够最先开始通信的路由,从而减小通信竞争冲突,缩短了调度长度。仿真结果表明,该算法能够使用较少的网络链路资源来获得最短的调度长度。     

Advance Reservations and Scheduling for Bulk Transfers in Research Networks

Data-intensive e-science collaborations often require the transfer of large files with predictable performance. To meet this need, we design novel admission control (AC) and scheduling algorithms for bulk data transfer in research networks for e-science. Due to their small sizes, the research networks can afford a centralized resource management platform. In our design, each bulk transfer job request, which can be made in advance to the central network controller, specifies a start time and an end time. If admitted, the network guarantees to complete the transfer before the end time. However, there is flexibility in how the actual transfer is carried out, that is, in the bandwidth assignment on each allowed path of the job on each time interval, and it is up to the scheduling algorithm to decide this. To improve the network resource utilization or lower the job rejection ratio, the network controller solves optimization problems in making AC and scheduling decisions. Our design combines the following elements into a cohesive optimization-based framework: advance reservations, multipath routing, and bandwidth reassignment via periodic reoptimization. We evaluate our algorithm in terms of both network efficiency and the performance level of individual transfer. We also evaluate the feasibility of our scheme by studying the algorithm execution time.     

Optimal scheduling algorithms in WDM optical interconnects with limited range wavelength conversion capability

Optical communication is a promising candidate for many emerging networking and parallel/distributed computing applications because of its huge bandwidth. Wavelength division multiplexing (WDM) is a technique that can better utilize the optical bandwidth by dividing the bandwidth of a fiber into multiple wavelength channels. In this paper, we study optimal scheduling algorithms to resolve output contentions in bufferless time slotted WDM optical interconnects with wavelength conversion ability. We consider the general case of limited range wavelength conversion with arbitrary conversion capability, as limited range wavelength conversion is easier to implement and more cost effective than full range wavelength conversion, and it also includes full range wavelength conversion as a special case. We first consider the conversion scheme in which each wavelength can be converted to multiple wavelengths in an interval of wavelengths and the intervals for different wavelengths are "ordered". We show that the problem of maximizing network throughput can be formalized as finding a maximum matching in a bipartite graph. We then give an optimal scheduling algorithm called the first available algorithm that runs in O(k) time, where k is the number of wavelengths per fiber. We also study the case where the connection requests have different priorities. We formalize the problem as finding an optimal matching in a weighted bipartite graph and give a scheduling algorithm called the downwards expanding algorithm that runs in O(kD + Nklog(Nk)) time where N is the number of input fibers of the interconnect and D is the conversion degree. Finally, we consider the circular symmetrical wavelength conversion scheme and give optimal scheduling algorithms for nonprioritized scheduling in O(Dk) time and prioritized scheduling in O(k/sup 2/+Nklog(Nk)) time.     

Optimizing the Throughput of Data-Driven Peer-to-Peer Streaming

During recent years, the Internet has witnessed a rapid growth in deployment of data-driven (or swarming based) peer-to-peer (P2P) media streaming. In these applications, each node independently selects some other nodes as its neighbors (i.e. gossip-style overlay construction), and exchanges streaming data with the neighbors (i.e. data scheduling). To improve the performance of such protocol, many existing works focus on the gossip-style overlay construction issue. However, few of them concentrate on optimizing the streaming data scheduling to maximize the throughput of a constructed overlay. In this paper, we analytically study the scheduling problem in data-driven streaming system and model it as a classical min-cost network flow problem. We then propose both the global optimal scheduling scheme and distributed heuristic algorithm to optimize the system throughput. Furthermore, we introduce layered video coding into data-driven protocol and extend our algorithm to deal with the end-host heterogeneity. The results of simulation with the real world traces indicate that our distributed algorithm significantly outperforms conventional ad hoc scheduling strategies especially in stringent buffer and bandwidth constraints.     

On approximation of the bulk synchronous task scheduling problem

The bulk synchronous task scheduling problem (BSSPO) is known as an effective task scheduling problem for distributed memory machines. We present a proof of NP-completeness of the decision counterpart of BSSPO, even in the case of makespan of at most five. This implies nonapproximability of BSSPO, meaning that there is no approximation algorithm with performance guarantee smaller than 6/5 unless P = NP. We also give an approximation algorithm with a performance guarantee of two for BSSPO in several restricted cases.     

基于输入排队的高速交换调度算法研究

高速交换网络一般采用基于定长信元的交换结构,其性能决定于排队策略和信元调度算法.输入排队策略只有和一个有效的调度算法相结合,才能保证交换结构具有良好的吞吐率和时延等性能.主要阐述了基于VOQ的最大数量匹配算法,最大权重匹配算法,稳定结合算法,神经网络算法等输入排队调度算法,分别从技术特点,性能指标和实现复杂度等多个方面进行比较和分析.分析了分布式和集中式两大类调度算法的工作方式,并根据各类算法的特点提出,神经网络算法可以通过定义其优先级函数实现其余各类算法.     

Connectivity and coverage maintenance in wireless sensor networks

One of the main design challenges for wireless sensor networks (WSNs) is to obtain long system lifetime without sacrificing system original performance such as communication connectivity and sensing coverage. A large number of sensor nodes are deployed in redundant fashion in dense sensor networks, which lead to higher energy consumption. We propose a distributed framework for energy efficient connectivity and coverage maintenance in WSNs. In our framework, each sensor makes self-scheduling to separately control the states of RF and sensing unit based on dynamic coordinated reconstruction mechanism. A novel energy-balanced distributed connected dominating set algorithm is presented to make connectivity maintenance; and also a distributed node sensing scheduling is brought forward to maintain the network coverage according to the surveillance requirements. We implemented our framework by C++ programming, and the simulation results show that our framework outperforms several related work by considerably improving the energy performance of sensor networks to effectively extend network lifetime.     

Fast primal-dual distributed algorithms for scheduling and matching problems

In this paper we give efficient distributed algorithms computing approximate solutions to general scheduling and matching problems. All approximation guarantees are within a constant factor of the optimum. By “efficient”, we mean that the number of communication rounds is poly-logarithmic in the size of the input. In the scheduling problem, we have a bipartite graph with computing agents on one side and resources on the other. Agents that share a resource can communicate in one time step. Each agent has a list of jobs, each with its own length and profit, to be executed on a neighbouring resource within a given time-window. Each job is also associated with a rational number in the range between zero and one (width), specifying the amount of resource required by the job. Resources can execute non preemptively multiple jobs whose total width at any given time is at most one. The goal is to maximize the profit of the jobs that are scheduled. We then adapt our algorithm for scheduling, to solve the weighted b-matching problem, which is the generalization of the weighted matching problem where for each vertex v, at most b(v) edges incident to v, can be included in the matching. For this problem we obtain a randomized distributed algorithm with approximation guarantee of \frac16+e{\frac{1}{6+\epsilon}}, for any ${\epsilon >0 }${\epsilon >0 }. For weighted matching, we devise a deterministic distributed algorithm with the same approximation ratio. To our knowledge, we give the first distributed algorithm for the aforementioned scheduling problem as well as the first deterministic distributed algorithm for weighted matching with poly-logaritmic running time. A very interesting feature of our algorithms is that they are all derived in a systematic manner from primal-dual algorithms.     

Agent scheduling model for adaptive dynamic load balancing in agent-based distributed simulations

Agent-based distributed simulations are confronted with load imbalance problem, which significantly affects simulation performance. Dynamic load balancing can be effective in decreasing simulation execution time and improving simulation performance. The characteristics of multi-agent systems and time synchronization mechanisms make the traditional dynamic load balancing approaches not suitable for dynamic load balancing in agent-based distributed simulations. In this paper, an adaptive dynamic load balancing model in agent-based distributed simulations is proposed. Due to the complexity and huge time consuming for solving the model, a distributed approximate optimized scheduling algorithm with partial information (DAOSAPI) is proposed. It integrates the distributed mode, approximate optimization and agent set scheduling approach. Finally, experiments are conducted to verify the efficiency of the proposed algorithm and the simulation performance under dynamic agent scheduling. The experiments indicate that DAOSPI has the advantage of short execution time in large-scale agent scheduling, and the distributed simulation performance under this dynamic agent scheduling outperforms that under static random agent distribution.     

Priority scheduling for networked virtual environments

When simulating large virtual environments (VEs), contention for limited resources such as the CPU, rendering pipeline, or network bandwidth frequently degrades the system's performance. Whenever such a competition occurs and not all elements that require the resource can be serviced, an approximation must be made to avoid compromising interactive performance. We propose an enhancement to the round-robin approach called Priority Round Robin scheduling (PRR). This algorithm enforces priorities, while retaining the output sensitivity and starvation-free performance of round-robin scheduling. Priorities are set by a user-defined error metric (such as visual error), which the algorithm attempts to minimize. This permits not only scheduling the entities competing for a resource such as updates competing for the network, but also filling the gap between filtering and scheduling techniques. We evaluate our algorithm in a client-server system     

Workflow performance improvement using model-based scheduling over multiple clusters and clouds

In recent years, a variety of computational sites and resources have emerged, and users often have access to multiple resources that are distributed. These sites are heterogeneous in nature and performance of different tasks in a workflow varies from one site to another. Additionally, users typically have a limited resource allocation at each site capped by administrative policies. In such cases, judicious scheduling strategy is required in order to map tasks in the workflow to resources so that the workload is balanced among sites and the overhead is minimized in data transfer. Most existing systems either run the entire workflow in a single site or use naïve approaches to distribute the tasks across sites or leave it to the user to optimize the allocation of tasks to distributed resources. This results in a significant loss in productivity. We propose a multi-site workflow scheduling technique that uses performance models to predict the execution time on resources and dynamic probes to identify the achievable network throughput between sites. We evaluate our approach using real world applications using the Swift parallel and distributed execution framework. We use two distinct computational environments-geographically distributed multiple clusters and multiple clouds. We show that our approach improves the resource utilization and reduces execution time when compared to the default schedule.     

Network and data location aware approach for simultaneous job scheduling and data replication in large-scale data grid environments

Data Grid integrates graphically distributed resources for solving data intensive scientific applications. Effective scheduling in Grid can reduce the amount of data transferred among nodes by submitting a job to a node, where most of the requested data files are available. Scheduling is a traditional problem in parallel and distributed system. However, due to special issues and goals of Grid, traditional approach is not effective in this environment any more. Therefore, it is necessary to propose methods specialized for this kind of parallel and distributed system. Another solution is to use a data replication strategy to create multiple copies of files and store them in convenient locations to shorten file access times. To utilize the above two concepts, in this paper we develop a job scheduling policy, called hierarchical job scheduling strategy (HJSS), and a dynamic data replication strategy, called advanced dynamic hierarchical replication strategy (ADHRS), to improve the data access efficiencies in a hierarchical Data Grid. HJSS uses hierarchical scheduling to reduce the search time for an appropriate computing node. It considers network characteristics, number of jobs waiting in queue, file locations, and disk read speed of storage drive at data sources. Moreover, due to the limited storage capacity, a good replica replacement algorithm is needed. We present a novel replacement strategy which deletes files in two steps when free space is not enough for the new replica: first, it deletes those files with minimum time for transferring. Second, if space is still insufficient then it considers the last time the replica was requested, number of access, size of replica and file transfer time. The simulation results show that our proposed algorithm has better performance in comparison with other algorithms in terms of job execution time, number of intercommunications, number of replications, hit ratio, computing resource usage and storage usage.     

GA-Sim:一种基于分类和实例学习相结合的作业运行时间预测算法

在高性能计算作业调度系统中,许多调度算法依赖于对作业运行时间的准确估计,尤其是以EASY为代表的回填算法,而使用用户提供的作业运行时间往往会降低调度性能。提出了一种基于分类和实例学习相结合的作业运行时间预测算法--GA-Sim,该算法在考虑预测准确性的同时考虑了低估问题。在两个实际调度日志上的数值实验结果表明,相较于IRPA和TRIP算法,GA-Sim在取得更高预测精度的同时降低了低估率。 对数值实验结果进行了深入分析,并给出了不同情形下选择恰当预测算法的建议。     

时间触发光纤通道调度算法确定性分析

光纤通道以其优良性能,成为下一代航电系统的必然选择。但是基于事件触发的消息调度形式限制了对航电系统性能的分析,为提高消息在网络中传输时间确定性,在时间触发协议的基础上,针对光纤通道提出一种时间触发的消息调度算法。通过对交换式网络建模,采用理论和仿真相结合的方法,对先来先服务调度策略和时间触发调度策略进行分析,结果表明时间触发调度算法可以很好地提高网络消息传输的确定性,满足航电系统安全关键消息的传输要求。     

基于动态预测和任务流整形的网格调度算法

针对网格环境下计算节点的自治性、异构性、分布性等特征,提出一种基于任务响应时间的动态修正预测和任务流整形的网格调度算法,该调度方法依据历史数据和最近访问过计算节点的任务请求提交时间、任务完成时间、网络通信延迟等信息,预测计算节点的将来任务响应时间,将任务提交给预测的轻负载或性能较优的计算节点完成。通过使用动态修正算法和任务流整形算法降低预测误差,提高资源利用率。实验结果表明,该方法在任务响应时间、任务的吞吐率等方面优于随机调度等传统算法,具有较好的综合性能。     

分布式测量系统服务窗口动态调度方法研究

在网络制造环境下, 动态时间性能是测量系统的重要指标. 针对基于 CORBA (Common object request broker architecture) 和尺寸测量接口标准 (Dimensional measurement interface standard, DMIS) 的分布式测量系统 (Distributed measurement system, DMS), 根据多用户非抢占优先排队网络静态性能模型, 提出基于无穷小摄动分析的样本轨道划分方法, 建立测量系统服务窗口的动态调度算法, 实现测量系统的时间性能调优. 通过在一个制造工厂中进行的应用实验, 证明了此方法的有效性.     

Improving scheduling of tasks in a heterogeneous environment

Optimal scheduling of parallel tasks with some precedence relationship, onto a parallel machine is known to be NP-complete. The complexity of the problem increases when task scheduling is to be done in a heterogeneous environment, where the processors in the network may not be identical and take different amounts of time to execute the same task. We introduce a task duplication-based scheduling algorithm for network of heterogeneous systems (TANH), with complexity O(V/sup 2/), which provides optimal results for applications represented by directed acyclic graphs (DAGs), provided a simple set of conditions on task computation and network communication time could be satisfied. The performance of the algorithm is illustrated by comparing the scheduling time with an existing "best imaginary level scheduling (BIL)" scheme for heterogeneous systems. The scalability for a higher or lower number of processors, as per their availability is also discussed. We have shown to provide substantial improvement over existing work on the task duplication-based scheduling algorithm (TDS).     

Routing and scheduling connections in networks that support advance reservations

A key problem in networks that support advance reservations is the routing and time scheduling of connections with flexible starting time and known data transfer size. In this paper we present a multicost routing and scheduling algorithm for selecting the path to be followed by such a connection and the time the data should start and end transmission at each link so as to minimize the reception time at the destination, or optimize some other performance criterion. The utilization profiles of the network links, the link propagation delays, and the parameters of the connection to be scheduled form the inputs to the algorithm. We initially present a scheme of non-polynomial complexity to compute a set of so-called non-dominated candidate paths, from which the optimal path can be found. We then propose two mechanisms to appropriately prune the set of candidate paths in order to find multicost routing and scheduling algorithms of polynomial complexity. We examine the performance of the algorithms in the special case of an Optical Burst Switched network. Our results indicate that the proposed polynomial-time algorithms have performance that is very close to that of the optimal algorithm. We also study the effects network propagation delays and link-state update policies have on performance.