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.     

各类组播路由协议的对比

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

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.     

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

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

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.     

一种新型的联合单播/组播的两级交换结构*

高速交换结构的设计中一般很难以较低的复杂度实现其对组播业务的支持。提出一种联合单播/组播的两级交换结构TSSIUM,该结构通过对Crossbar结构级联一个组播合路结构实现,因此可以极低的复杂度即可实现对组播业务的支持。理论分析和实测数据均表明,该结构在容许的通信量下可以达到100％的吞吐率。     

网格资源调度研究

在介绍网格资源管理的基础上,针对网格中的资源调度问题,分析和总结常见的三类资源调度策略;并结合应用任务的类型分析了面向应用的资源调度策略,探讨网格对不同类型任务的调度支持,着重分析协作型任务的调度问题。将协作型任务通过BPEL4WS规范描述后,分解为多个可以并发或串行执行的子任务,然后进行调度。基于此,提出了一个新的协作型任务调度方法。     

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.     

视频流调度策略的研究

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

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

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

BC单播与BC多播并存的多用户网络分析

提出一种多用户BC单播与BC多播并存的网络模型以及结合零空间交的迫零干扰消息的新方法,该模型的主网采用“循环模式” 为接收端分配期望消息,以构成多播网络;次网采用“一发多收”为接收端分配期望消息,以构成单播网络。该迫零方法首先根据接收端的干扰消息获取对应的零空间,再取多个零空间的交空间,最后将多个干扰消息同时置于对应的交空间中,即可实现在每个接收端同时迫零多个干扰消息。对于该多用户系统,分析得到了最优天线配置方案及系统复用增益的一般化结果。 采用 Matlab对系统进行仿真分析,结果表明系统复用增益的理论值与仿真结果相一致。     

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

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

组播广播单频网动态域管理研究

针对传统动态单频网多播/广播(MBSFN)不能满足域管理需求的问题,提出一种简单易行的动态域操作算法。介绍增强型多媒体广播组播业务逻辑架构和MBSFN域管理部署选项,建模研究MBSFN域传输特性。根据域传输特性的仿真结果,明确动态MBSFN域管理需求,按照需求提出一种动态域操作算法,对算法中门限值选取进行分析。仿真结果证明了其可行性。     

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

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

基于受限广播搜索的分布式QoS组播路由协议

根据像网络电视这样的宽带多媒体业务的需要,提出了一种简单有效的分布式QoS组播路由协议来支持动态成员组播。分析和仿真表明,本协议和其它同类协议比具有消息开销少、成功率高、路径建立时延短和性能稳定等优点。     

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.