面向子流的低延迟数据调度算法

J4 ›› 2012, Vol. 34 ›› Issue (5): 7-12.

面向子流的低延迟数据调度算法

吴国福，窦强，吴吉庆，窦文华

（国防科学技术大学计算机学院，湖南长沙 410073）

收稿日期:2010-03-11 修回日期:2010-05-23 出版日期:2012-05-25 发布日期:2012-05-25

A Novel SubStreamOriented LowDelay Scheduling Algorithm

WU Guofu,DOU Qiang,WU Jiqing,DOU Wenhua

(School of Computer Science,National University of Defense Technology,Changsha 410073,China)

Received:2010-03-11 Revised:2010-05-23 Online:2012-05-25 Published:2012-05-25

摘要/Abstract

摘要：

P2P流媒体是分发流媒体数据的高效方式，而数据传输延迟是决定P2P流媒体系统性能的重要参数。在分析“拉”模式数据调度模式传输延迟的基础上，本文在“推”、“拉”混合的调度模式下提出一种新的面向子流的低延迟数据调度算法。首先子流的调度问题被转换成等价的带权二部图匹配问题，其次针对转换后的二部图改进匈牙利算法，提出最小延迟、最大匹配的启发式匹配算法。该算法在保证最大匹配的同时使得每条子流的延迟尽可能地低。模拟实验表明本文的算法能够极大降低数据传输延迟。

关键词: P2P流媒体, 数据调度, 子流, 带权二部图, 匹配

Abstract:

Peer-to-Peer streaming is an effectual and promising way to distribute media content. In this paper, we present a novel substreamoriented lowdelay scheduling strategy under the pushpull hybrid framework. First the substream scheduling problem is transformed into the matching problem of the weighted bipartite graph. Then the wellknown Hungarian Algorithm is ameliorated, and a minimum delay, maximum matching algorithm is presented. Not only maximum matching is reserved by the new improved algorithm, but also the transmitting delay of each substream is as low as possible. The simulation results show that our method can greatly reduce the transmission delay.

Key words: P2P streaming;scheduling;substream;weighted bipartite graph;matching

吴国福，窦强，吴吉庆，窦文华. 面向子流的低延迟数据调度算法[J]. J4, 2012, 34(5): 7-12.

WU Guofu,DOU Qiang,WU Jiqing,DOU Wenhua. A Novel SubStreamOriented LowDelay Scheduling Algorithm[J]. J4, 2012, 34(5): 7-12.

[1]	田永红, 章钧津, 宋哲煜. 结合噪声数据增强的蒙汉伪平行语料库的构造[J]. 计算机工程与科学, 2025, 47(04): 751-760.
[2]	吉陈果, 贾海蓉, 裴意静, 段淑斐. 基于失匹配负波潜伏期优化的语音增强研究[J]. 计算机工程与科学, 2025, 47(03): 524-533.
[3]	王钦晨, 段利国, 王君山, 张昊妍, 郜浩. 基于BERT字句向量与差异注意力的短文本语义匹配策略[J]. 计算机工程与科学, 2024, 46(07): 1321-1330.
[4]	刘汝霖, 杨惠, 李韬, 吕高锋, 孙志刚. 面向装备平台的敏捷交换芯片设计与实现[J]. 计算机工程与科学, 2024, 46(02): 200-208.
[5]	贾康, 李晓楠, 李冠宇. 一种基于自适应结构感知池化图匹配的图相似度计算模型[J]. 计算机工程与科学, 2023, 45(11): 1999-2007.
[6]	周聪, 陶静, 赵宝康, 李安艺. 基于双重检索修正域名系统的最长匹配规则[J]. 计算机工程与科学, 2023, 45(09): 1572-1577.
[7]	杨茂恒, 章辉, 周超. 基于匹配理论的LoRa参数双重匹配优化[J]. 计算机工程与科学, 2023, 45(06): 995-1002.
[8]	许晓阳, 王斯棋. 基于粒子分解的SPH并行算法研究与应用[J]. 计算机工程与科学, 2022, 44(06): 964-970.
[9]	郭嘉宇, 付晓东, 岳昆, 刘骊, 冯勇, 刘利军. 偏好匹配满意度最大化的众包任务分配[J]. 计算机工程与科学, 2022, 44(01): 16-26.
[10]	谢聪, 郑洪清. 一种新型的樽海鞘群算法及其应用[J]. 计算机工程与科学, 2022, 44(01): 184-190.
[11]	张露文, 薛晓军, 李恒, 王海瑞, 张国银, 赵磊. 基于改进NLM的PCB图像去噪算法[J]. 计算机工程与科学, 2021, 43(09): 1608-1615.
[12]	范小康, 夏泽宇, 龙思凡, 杨灿群. 基于ARM SVE的光滑粒子流体动力学SIMD加速方法[J]. 计算机工程与科学, 2021, 43(06): 989-996.
[13]	陈雪松, 雷嫚, 毕波, 唐锦萍. 一种改进的OSID的图像匹配算法[J]. 计算机工程与科学, 2021, 43(06): 1032-1040.
[14]	王吴松, 方欢, 郑雪文. 基于Petri网的流程变体合并方法[J]. 计算机工程与科学, 2021, 43(06): 1095-1103.
[15]	黄浩淼, 张江, 张晶, 保峻嵘. 融合TLD框架的DSST实时目标跟踪改进算法[J]. 计算机工程与科学, 2020, 42(09): 1587-1598.