A Comparison of Multicast Pull Models

We consider the setting of a web server that receives requests for documents from clients, and returns the requested documents over a multicast/broadcast channel. We compare the quality of service (QoS) obtainable by optimal schedules under various models of the capabilities of the server and the clients to send and receive segments of a document out of order. We show that allowing the server to send segments out of order does not improve any reasonable QoS measure. However, the ability of the clients to receive data out of order can drastically improve the achievable QoS under some, but not all, reasonable/common QoS measures.     

Multicast Pull Scheduling: When Fairness Is Fine

We investigate server scheduling policies to minimize average user perceived latency in pull-based client-server systems (systems where multiple clients request data from a server) where the server answers requests on a multicast/ broadcast channel. We first show that there is no O(1) -competitive algorithm for this problem. We then give a method to convert any nonclairvoyant unicast scheduling algorithm A to nonclairvoyant multicast scheduling algorithm B . We show that if A works well, when jobs can have parallel and sequential phases, then B works well if it is given twice the resources. More formally, if A is an s -speed c -approximation unicast algorithm, then its counterpart algorithm B is a 2s -speed c -approximation multicast algorithm. It is already known [5] that Equi-partition, which devotes an equal amount of processing power to each job, is a (2 + ε) -speed O(1 + 1/ε) -approximation algorithm for unicast scheduling of such jobs. Hence, it follows that the algorithm {BEQUI}, which broadcasts all requested files at a rate proportional to the number of outstanding requests for that file, is a (4 + ε) -speed O(1 + 1/ε) -approximation algorithm. We give another algorithm BEQUI-EDF and show that BEQUI-EDF is also a (4 + ε) -speed O(1 + 1/ε) -approximation algorithm. However, BEQUI-EDF has the advantage that the maximum number of preemptions is linear in the number of requests, and the advantage that no preemptions occur if the data items have unit size.     

各类组播路由协议的对比

组播技术对于视频信号在网络中的高质量传播,提供一种很好的解决方案,但由于当初缺乏同一的标准,在经过几十年的发展与研究后,出现不同思路不同方法的网络组播协议,众多的组播路由协议,也使得网络组播显得日益复杂。选择理想的组播协议,是网络设计人员的首要工作。合适的组播协议,能够极大地提高视频传输质量。     

C#中利用UDP协议实现信息的广播和组播

在进行协作开发的项目中,开发工作组的规模比较大而相对互连网又较小时,开发工作组需在不同的地点协作并经常交换情况。此时点对点交换信息不管对网络还是对信息发送者,不仅增加了网络传输负担,而且同时资源消耗较高,代价昂贵。提出使用C#利用UDP协议实现信息的广播和组播。可以让规模较大而相对互联网又较小的工作组能相互方便、快捷地传递信息。     

Scheduling algorithms for multicast traffic in TDM/WDM networks with arbitrary tuning latencies

We consider all-optical Time Division Multiplexing (TDM)/Wavelength Division Multiplexing (WDM) broadcast and select networks with slotted operation. Each network access node is equipped with one fixed transmitter and one tunable receiver; tuning times are not negligible with respect to the fixed size slot time. We discuss efficient scheduling algorithms to assign TDM/WDM slots to multicast traffic in such networks. The problem is shown to be NP-hard; thus, heuristic algorithms based on the Tabu Search meta-heuristic are proposed, and their performance are assessed using randomly created request matrices based on two types of multicast traffic patterns. We show that significant advantages can be obtained by using these novel algorithms with respect to simpler greedy algorithms, even when restricting CPU times to realistic values to make the algorithms of practical use.     

IP组播技术在局域网视频直播系统中的应用

叙述了在局域网环境下,为有效地减轻网络负担,避免资源浪费,设计了基于IP组播技术的视频直播系统设计方案。简要介绍了IP组播技术的概念、原理及体系结构,描述PIM、IGMP协议在视频直播系统中的应用。     

Non-Clairvoyant Scheduling for Minimizing Mean Slowdown

We consider the problem of scheduling dynamically arriving jobs in a non-clairvoyant setting, that is, when the size of a job in remains unknown until the job finishes execution. Our focus is on minimizing the mean slowdown, where the slowdown (also known as stretch) of a job is defined as the ratio of the flow time to the size of the job. We use resource augmentation in terms of allowing a faster processor to the online algorithm to make up for its lack of knowledge of job sizes. Our main result is that the Shortest Elapsed Time First (SETF) algorithm, a close variant of which is used in the Windows NT and Unix operating system scheduling policies, is a $(1+\epsilon)$-speed, $O((1/\epsilon)^5 \log^2 B)$-competitive algorithm for minimizing mean slowdown non-clairvoyantly, when $B$ is the ratio between the largest and smallest job sizes. In a sense, this provides a theoretical justification of the effectiveness of an algorithm widely used in practice. On the other hand, we also show that any $O(1)$-speed algorithm, deterministic or randomized, is $\Omega(\min(n,\log B))$-competitive. The motivation for resource augmentation is supported by an $\Omega(\min(n,B))$ lower bound on the competitive ratio without any speedup. For the static case, i.e., when all jobs arrive at time 0, we show that SETF is $O(\log{B})$ competitive without any resource augmentation and also give a matching $\Omega(\log{B})$ lower bound on the competitiveness.     

Scheduling time-constrained multicast messages in circuit-switched tree networks

In this paper, we consider a kind of multicast scheduling problem in a tree network. Each multicast message is transmitted through a directed subtree within the tree network. The transmission time of each multicast message is assumed to be one unit. Two messages can be transmitted at the same time if their subtrees are edge-disjoint. Each message is constrained by a ready time and a deadline, and has a weight we can gain if it is scheduled within its deadline. The optimality criterion is the total weight we gain. We assume that the degree of each subtree is bounded by a constant d and present an approximation algorithm of which the approximation ratio is at most 4d+15.     

视频流调度策略的研究

视频流调度策略是视频点播系统中有效使用存储资源和网络资源的关键技术。该文研究了已有的多种流调度技术并分析了各种调度方法的优劣,在此基础上以补丁算法为基础提出了一种支持零延迟交互式操作的调度方法,并实验正明了这种方法在用户延迟、带宽消耗等方面的优越性。     

网格环境中资源管理与调度的研究

网格在解决分散式资源共享方面具有广阔的应用前景,使得它成为下一代互联网瞩目的焦点。本文首先对网格中资源管理和调度的现状展开讨论,分析比较当前的几种调度方案,为进一步提出高效完备的资源调度算法作准备。     

基于遗传算法的网格计算资源调度策略

如何将网格这个复杂环境中的计算资源进行有效调度,是一个NP问题。遗传算法被证明是解决这类问题的有效算法,同时遗传算法有“早熟”和慢速收敛等缺点。为了克服其缺点,提出一种新的并行遗传算法,采取避免近亲繁殖的交叉策略和保护优秀个体的方法,提高算法搜索能力和收敛速度。仿真结果表明该算法能有效地解决网格计算资源分配问题。     

基于网格工作流的决策资源协同调度模型

基于网格的开放式决策支持系统越来越受到学术界的重视。在研究网格环境中的决策资源和网格工作流的基础上,提出了一种基于网格工作流的决策资源协同调度模型,并给出了该模型的协同调度机制与调度过程。     

Pinwheel Scheduling: Achievable Densities

Abstract. A pinwheel schedule for a vector v= (v ₁ , v ₂ , . . ., v _n ) of positive integers 2 ≤ v ₁ ≤ v ₂ ≤ ⋅s ≤ v _n is an infinite symbol sequence {S _j : j ∈ Z } with each symbol drawn from [n] = {1,2, . . ., n } such that each i ∈ [n] occurs at least once in every v _i consecutive terms (S _j+1 , S _j+2 , . ., S _j+vi ) . The density of v is d(v) = 1/v ₁ + 1/v ₂ + ⋅s + 1/v _n . If v has a pinwheel schedule, it is schedulable . It is known that v(2,3,m) with m ≥ 6 and density d(v) = 5/6 + 1/m is unschedulable, and Chan and Chin [2] conjecture that every v with d(v) ≤ 5/6 is schedulable. They prove also that every v with d(v) ≤ 7/10 is schedulable. We show that every v with d(v) ≤ 3/4 is schedulable, and that every v with v ₁ =2 and d(v) ≤ 5/6 is schedulable. The paper also considers the m -pinwheel scheduling problem for v , where each i ∈ [n] is to occur at least m times in every mv _i consecutive terms (S _j+1 , . ., S _j+mvi ) , and shows that there are unschedulable vectors with d(v) =1- 1/[(m+1)(m+2)] + ɛ for any ɛ > 0 .     

资源约束平行处理机调度的MILP模型

本文针对考虑资源约束的平行处理机的调度问题,以选择操作链来划分时间段,并建立了数学模型。这一方式将对处理机和资源的关注转化到操作的变化上来,极大地降低了该类问题的计算复杂性。     

Optimal On-Line Algorithms to Minimize Makespan on Two Machines with Resource Augmentation

We study the problem of on-line scheduling on two uniformly related machines where the on-line algorithm has resources different from those of the off-line algorithm. We consider three versions of this problem, preemptive semi-online, non-preemptive on-line and preemptive on-line scheduling. For all these cases we design algorithms with best possible competitive ratios as functions of the machine speeds. This work was submitted as a part of the M.Sc. thesis of the second author. A preliminary version of this paper appeared in the proceedings of The First Workshop on Approximation and Online Algorithms (WAOA’03), pages 109–122.     

无人机平台非对称广播链路的动态优先权调度算法

战场数据分发系统需要传输不同长度的信息和数据,数据容量相差很大,采用动态优先权调度算法在系统平均延时、长短信息传输的公平性两个方面可以同时达到很好的性能。该调度算法适合于有优先级控制的广播链路。     

Scheduling Independent Multiprocessor Tasks

Abstract. We study the problem of scheduling a set of n independent multiprocessor tasks with prespecified processor allocations on a fixed number of processors. We propose a linear time algorithm that finds a schedule of minimum makespan in the preemptive model, and a linear time approximation algorithm that finds a schedule of makespan within a factor of (1+\eps) of optimal in the non-preemptive model. We extend our results by obtaining a polynomial time approximation scheme for the parallel processors variant of the multiprocessor task model.     

网格环境下一种新的动态任务调度算法

现有的任务调度算法大多没有考虑网格环境的特点,因此性能还有待提高。针对这个问题,将任务完成时间和网格资源置信度结合起来,给出了一个可调节的局部目标函数,提出了一种新的启发式动态任务调度算法TSAMRC。模拟实验表明,该算法对于网格环境具有更好的调度性能。     

基于数据接收质量的P2P流媒体自适应推拉调度算法

针对现有基于推、拉以及推拉混合模式调度算法不能高效分发数据的同时保证节点数据接收质量,导致服务器负载重的问题,提出一种基于数据接收质量的自适应推拉调度算法。该算法根据节点缓存区数据被及时正确填充的情况动态调节推拉获取数据比例,当数据接收质量好时主要采用推方式获取数据,数据接收质量变差时则过渡到拉方式获取数据。仿真实验表明所提算法可以充分利用推拉方式各自优点加速数据在网络中传播的同时保证节点数据接收质量,降低服务器负载,提高系统可扩展性。     

Modeling and Supporting Grid Scheduling

Grid resource management systems and schedulers are important components for building Grids. They are responsible for the selection and allocation of Grid resources to current and future applications. Thus, they are important building blocks for making Grids available to user communities. In this paper we briefly analyze the requirements of Grid resource management and provide a classification of schedulers. Then, we define an extensible formal model for Grid scheduling activities, and characterize the general Grid scheduling problem. Finally, we provide a reference architecture for the support of our model and discuss different aspects of architectural implementations.