University of Science and Technology of China A dissertation for master s degree Design and Analysis on Storage Scheduling of Clustered Video-On-Deman

中 国 科 学 技 术 大 学 硕 士 学 位 论 文 集 群 式 视 频 点 播 系 统 的 存 储 调 度 分 析 与 设 计 作 者 姓 名 : 学 科 专 业 : 导 师 姓 名 : 完 成 时 间 : 王 飞 控 制 科 学 与 工 程 奚 宏 生 教 授 二 八 年 五 月 六 日

University of Science and Technology of China A dissertation for master s degree Design and Analysis on Storage Scheduling of Clustered Video-On-Demand System Author s Name: Speciality: Supervisor: Wang Fei Control Sciences and Engineering Prof. Xi Hongsheng Finished time: May 6, 2008

论 文 原 创 性 和 授 权 使 用 声 明 本 人 声 明 所 呈 交 的 学 位 论 文, 是 本 人 在 导 师 指 导 下 进 行 研 究 工 作 所 取 得 的 成 果 除 已 特 别 加 以 标 注 和 致 谢 的 地 方 外, 论 文 中 不 包 含 任 何 他 人 已 经 发 表 或 撰 写 过 的 研 究 成 果 与 我 一 同 工 作 的 同 志 对 本 研 究 所 做 的 贡 献 均 已 在 论 文 中 作 了 明 确 的 说 明 本 人 授 权 中 国 科 学 技 术 大 学 拥 有 学 位 论 文 的 部 分 使 用 权, 即 : 学 校 有 权 按 有 关 规 定 向 国 家 有 关 部 门 或 机 构 送 交 论 文 的 复 印 件 和 电 子 版, 允 许 论 文 被 查 阅 和 借 阅, 可 以 将 学 位 论 文 编 入 有 关 数 据 库 进 行 检 索, 可 以 采 用 影 印 缩 印 或 扫 描 等 复 制 手 段 保 存 汇 编 学 位 论 文 保 密 的 学 位 论 文 在 解 密 后 也 遵 守 此 规 定 作 者 签 名 : 年 月 日

摘 要 摘 要 计 算 机 和 网 络 技 术 的 进 步 使 得 视 频 点 播 (Video-On-Demand,VOD) 服 务 成 为 可 能 由 于 其 能 够 使 用 户 按 照 自 己 的 需 求 选 择 自 己 感 兴 趣 的 视 频 信 息, 近 年 来 在 娱 乐 教 育 广 告 等 领 域 得 到 了 广 泛 的 应 用 随 着 应 用 的 增 多 和 用 户 群 的 不 断 扩 大, 视 频 服 务 器 和 网 络 的 压 力 不 断 增 加 为 了 提 高 并 发 处 理 能 力 和 有 效 利 用 网 络 带 宽, 目 前 大 部 分 视 频 服 务 器 都 采 用 集 群 式 结 构 在 集 群 式 VOD 系 统 中, 多 个 并 行 工 作 的 存 储 节 点 构 成 整 个 服 务 系 统, 不 同 的 影 片 存 储 到 系 统 的 节 点 上, 当 用 户 请 求 到 达 时, 系 统 根 据 相 关 策 略 选 择 一 服 务 器 对 用 户 进 行 服 务, 只 有 当 所 有 的 服 务 器 都 超 过 最 高 负 载 时 才 拒 绝 用 户 请 求 由 于 不 同 影 片 的 热 度 不 同, 如 果 不 采 取 合 适 的 存 储 策 略, 将 会 使 各 服 务 器 的 负 载 不 均 衡, 造 成 存 储 了 热 门 影 片 的 节 点 过 载 而 同 时 其 它 节 点 还 有 大 量 带 宽 剩 余 的 现 象, 从 而 大 大 降 低 系 统 的 效 率, 浪 费 系 统 带 宽 解 决 影 片 热 度 不 均 的 方 法 通 常 有 复 制 和 分 条 分 条 技 术 通 过 将 影 片 分 割 成 小 块 分 别 存 储 到 集 群 中 各 服 务 器 上 的 方 式 让 各 服 务 器 分 担 影 片 的 服 务 压 力, 很 好 地 解 决 了 影 片 热 度 不 均 的 问 题 但 是, 传 统 的 分 条 策 略 仅 仅 考 虑 了 影 片 之 间 的 热 度, 而 忽 视 了 热 度 同 时 也 存 在 于 影 片 内 部, 因 此, 通 过 分 条 解 决 了 影 片 间 热 度 不 均 问 题 的 同 时, 又 因 为 影 片 内 部 的 热 度 不 均 匀 带 来 了 新 的 问 题 本 文 首 先 概 述 了 研 究 的 相 关 背 景 和 研 究 的 意 义, 介 绍 了 视 频 点 播 技 术 的 发 展 历 史 和 当 前 研 究 热 点 问 题, 讨 论 了 视 频 点 播 中 的 相 关 技 术, 介 绍 了 计 算 机 集 群 技 术, 视 频 文 件 的 存 储 调 度 算 法 和 磁 盘 调 度 算 法, 视 频 流 的 服 务 策 略 以 及 流 媒 体 传 输 协 议 接 着, 介 绍 了 传 统 分 条 算 法 的 优 点, 并 且 针 对 传 统 分 条 算 法 的 局 限 性, 提 出 了 改 进 的 存 储 调 度 算 法, 详 细 讨 论 了 其 设 计 思 想 和 所 基 于 的 用 户 行 为 模 式 模 型, 根 据 改 进 的 算 法 设 计 了 仿 真 模 拟 实 验, 通 过 服 务 器 负 载 不 均 衡 度 和 用 户 请 求 接 受 率 分 析 了 改 进 策 略 对 系 统 性 能 的 影 响 本 文 的 最 后 讨 论 了 存 储 调 度 系 统 工 程 实 现 的 相 关 问 题, 分 析 了 各 模 块 的 功 能 作 用, 并 且 对 未 来 可 以 进 行 的 工 作 作 了 展 望 关 键 词 : 视 频 点 播, 集 群 系 统, 流 媒 体, 数 据 存 储, 负 载 均 衡

Abstract Abstract Recent advances of Computer & Networks technology have made Video-On-Demand possible. As VOD allows users to select the video information according to their own interest, it has been applied in many fields such as entertainment, education, advertisement, and etc. As the scale of application and the number of users increase, the video servers and the network are bearing more and more burden. In order to enhance the concurrent processing ability and to effectively utilize the network bandwidth, most video servers adopt the clustered structure. In the clustered VOD system, the whole serving system consists of a series of concurrent storing nodes and different videos are stored on different nodes. When a user request arrives, the system selects an available server node to serve the user using a certain strategy; a user request is rejected only when all the possible servers are unavailable. As different videos have different demand probability, if no suitable storing strategy is adopted, the loads of the servers would be unbalanced causing the nodes storing hot videos overload while other nodes starving, resulting in low effectiveness of the whole system and waste of network bandwidth. There are two traditional methods in solving the demanding skewness of the videos: replication and striping. Striping splits the serving tasks to different servers by striping a video into smaller segments and stores them onto different server nodes, thus solves the skewness between videos. However, the traditional striping strategy fails to consider the skewness within a single video; it brings new problems to the matter as it solves an old one. This paper introduced the history and recent advances in VOD related research, discussed the storage & scheduling algorithm and disk scheduling algorithm, as well as the serving strategy and the transport protocol of the stream media. In the purpose of fixing the defect of the traditional striping algorithm, the author proposed a revised storage scheduling algorithm and illustrated its design and the user behavior pattern the algorithm is based on. A simulation was carried out to determine the new algorithm s actual effects on the system s performance by the means of calculating the load balance status and the accept ratio of user requests. The last few chapters of this paper discussed the implementation issues of

Abstract storage scheduling system, the author analyzed the function of the modules in the system and provided an outlook on how future work could be oriented. Key Words: Video On Demand (VOD), clustered system, streaming media, storage & scheduling, load balance

目 录 目 录 第 1 章 绪 论...1 1.1 研 究 的 背 景 和 意 义... 1 1.1.1 视 频 点 播 基 本 概 念... 1 1.1.2 流 媒 体 系 统... 3 1.1.3 存 储 调 度 研 究 的 意 义... 4 1.2 研 究 现 状... 5 1.2.1 VOD 系 统 分 类... 5 1.2.2 视 频 流 的 存 储... 6 1.2.3 服 务 器 间 的 负 载 均 衡... 7 1.2.4 动 态 内 容 更 新 策 略... 7 1.3 本 文 研 究 的 工 作... 7 1.4 本 文 内 容 安 排... 8 第 2 章 视 频 点 播 技 术 概 述...10 2.1 流 媒 体 服 务 系 统... 10 2.1.1 计 算 机 集 群 技 术... 10 2.1.2 VOD 系 统 架 构... 11 2.1.3 视 频 文 件 的 存 储 调 度 算 法... 12 2.1.4 磁 盘 调 度 算 法... 15 2.1.5 请 求 分 配 与 迁 移... 17 2.2 视 频 流 服 务 策 略... 18 2.2.1 客 户 拉... 18 2.2.2 服 务 器 推... 21 2.3 交 互 式 VOD... 23 2.4 流 媒 体 传 输 协 议... 24 2.4.1 RTP 协 议... 24 2.4.2 时 传 输 控 制 协 议 RTCP 协 议... 25 2.4.3 实 时 流 协 议 RTSP 协 议... 30 2.4.4 资 源 预 留 协 议 RSVP... 32 2.5 本 章 小 结... 33 第 3 章 流 媒 体 服 务 系 统 存 储 调 度...34 3.1 用 户 行 为 模 式 分 析... 34 3.1.1 影 片 间 热 度... 34 3.1.2 影 片 内 热 度... 35 3.2 文 件 分 割 与 服 务 拒 绝 率 的 关 系... 36 3.2.1 单 服 务 器 单 影 片 情 况... 36

目 录 3.2.2 单 服 务 器 多 影 片 情 况... 37 3.2.3 多 服 务 器 单 影 片 情 况... 37 3.2.4 多 服 务 器 多 影 片 情 况... 37 3.3 分 割 存 储... 38 3.4 视 频 文 件 的 分 配... 38 3.4.1 复 制... 38 3.4.2 分 条... 39 3.5 改 进 的 磁 盘 调 度 策 略... 43 3.5.1 点 播 中 断 概 率 模 型 分 析... 44 3.5.2 改 进 的 分 块 策 略... 45 3.6 仿 真 实 验... 46 3.6.1 仿 真 实 验 设 计 思 路... 46 3.6.2 仿 真 结 果 与 分 析... 49 3.7 本 章 小 结... 51 第 4 章 流 媒 体 服 务 系 统 存 储 调 度 的 工 程 实 现...52 4.1 存 储 调 度 系 统 设 计... 52 4.2 功 能 模 块 划 分... 54 4.2.1 信 息 采 集 模 块... 54 4.2.2 热 度 估 计 模 块... 55 4.2.3 存 储 调 度 决 策 模 块... 57 4.3 本 章 小 结... 57 第 5 章 总 结 和 展 望...59 5.1 总 结... 59 5.2 展 望... 60 参 考 文 献...61 攻 读 硕 士 学 位 期 间 参 与 的 科 研 项 目...66 攻 读 硕 士 学 位 期 间 撰 写 的 论 文...66 致 谢...67

第 1 章 绪 论 第 1 章 绪 论 1.1 研 究 的 背 景 和 意 义 1.1.1 视 频 点 播 基 本 概 念 Internet 发 展 至 今, 互 联 网 已 经 深 入 到 了 生 活 的 每 个 角 落 互 联 网 的 传 统 服 务 诸 如 收 发 邮 件 观 看 新 闻 在 线 聊 天 等 已 经 为 绝 大 多 数 人 所 熟 知, 同 时, 新 技 术 新 应 用 层 出 不 穷, 视 频 点 播 网 络 游 戏 远 程 教 育 网 上 购 物 等 一 系 列 的 新 兴 服 务 已 经 兴 起 1969 年, 为 了 能 在 爆 发 核 战 争 时 保 障 通 信 联 络, 美 国 国 防 部 高 级 研 究 计 划 署 ARPA 资 助 建 立 了 世 界 上 第 一 个 分 组 交 换 试 验 网 ARPANET, 连 接 美 国 四 个 大 学 ARPANET 的 建 成 和 不 断 发 展 标 志 着 计 算 机 网 络 发 展 的 新 纪 元 70 年 代 末 到 80 年 代 初, 计 算 机 网 络 蓬 勃 发 展, 各 种 各 样 的 计 算 机 网 络 应 运 而 生, 如 MILNET USENET BITNET CSNET 等, 在 网 络 的 规 模 和 数 量 上 都 得 到 了 很 大 的 发 展 一 系 列 网 络 的 建 设, 产 生 了 不 同 网 络 之 间 互 联 的 需 求, 并 最 终 导 致 了 TCP/IP 协 议 的 诞 生 1980 年,TCP/IP 协 议 研 制 成 功 1982 年,ARPANET 开 始 采 用 IP 协 议 1986 年, 美 国 国 家 科 学 基 金 会 NSF 资 助 建 成 了 基 于 TCP/IP 技 术 的 主 干 网 NSFNET, 连 接 美 国 的 若 干 超 级 计 算 中 心 主 要 大 学 和 研 究 机 构, 世 界 上 第 一 个 互 联 网 产 生, 迅 速 连 接 到 世 界 各 地 90 年 代, 随 着 Web 技 术 和 相 应 的 浏 览 器 的 出 现, 互 联 网 的 发 展 和 应 用 出 现 了 新 的 飞 跃 1995 年,NSFNET 开 始 商 业 化 运 行 针 对 不 断 高 速 扩 展 的 计 算 机 互 联 网 络, 各 国 政 府 纷 纷 提 出 各 自 的 互 联 网 发 展 计 划, 美 国 的 信 息 高 速 公 路 计 划 是 其 中 的 典 型 代 表 1993 年 9 月, 克 林 顿 政 府 正 式 制 定 了 名 为 国 家 信 息 基 础 设 施 行 动 日 程 表 ( 即 NII 计 划 ) 的 计 划 书 从 而 使 建 设 信 息 高 速 公 路 进 入 到 有 目 标 有 计 划 有 行 动 的 新 阶 段 信 息 高 速 公 路 的 主 要 内 容 是 利 用 先 进 的 计 算 机 网 络 作 为 传 输 通 道, 传 送 接 收 和 处 理 文 字 图 像 语 音 等 信 号, 从 而 将 从 商 业 应 用 到 家 庭 中 使 用 的 电 脑 电 视 传 真 电 话 等 各 类 信 息 处 理 设 备 纳 入 一 个 全 球 的 高 速 化 的 多 媒 体 的 信 息 传 输 接 收 处 理 的 体 系 为 了 开 启 Internet 的 新 时 代, 美 国 34 所 大 学 自 1996 年 10 月 起, 发 起 了 轰 轰 烈 烈 的 Internet 2 计 划, 它 的 重 要 任 务 之 一 就 是 要 把 网 络 传 输 与 电 视 合 二 为 一, 实 现 实 时 动 态 图 像 传 送 目 前, 参 加 Internet 2 计 划 的 大 学 己 达 163 所, 并 且 有 众 多 商 第 1 页

第 1 章 绪 论 家 给 予 资 金 上 的 帮 助 Internet 2 首 先 致 力 于 扩 容, 也 就 是 增 加 带 宽, 扩 充 网 络 负 载 能 力 Internet 2 不 是 目 前 的 Internet 的 简 单 升 级, 它 要 创 造 一 个 全 新 的 程 序 系 统, 从 根 本 上 改 变 互 联 网 的 承 受 能 力 新 的 信 息 高 速 公 路 将 建 立 在 Internet 2 的 基 础 上, 它 将 彻 底 改 变 现 阶 段 网 上 交 通 堵 塞 的 状 况, 在 真 正 意 义 上 实 现 电 子 商 务 在 西 雅 图 群 英 会 上,Internet 2 的 模 式 己 经 基 本 确 定, 远 程 教 学 终 生 受 教 等 方 面 甚 至 已 经 变 成 现 实 微 软 3COM, CISCO 等 公 司 都 积 极 地 参 与 到 Internet 2 的 研 究 与 开 发 中 视 频 点 播 (VOD Video on demand) 系 统 是 计 算 机 网 络 技 术, 通 信 技 术, 多 媒 体 信 息 处 理 技 术 分 布 计 算 技 术 数 据 压 缩 技 术 等 众 多 技 术 相 结 合 的 产 物 它 将 远 程 视 频 服 务 器 上 的 媒 体 信 息, 通 过 计 算 机 网 络 或 其 他 通 信 设 施 传 送 到 本 地 的 媒 体 处 理 器 或 终 端 上, 用 户 可 以 在 电 视 机 或 PC 上 随 意 点 播 自 己 喜 爱 的 视 频 节 目, 并 可 以 控 制 节 目 的 暂 停 快 进 倒 退, 循 环 等, 就 像 控 制 自 己 家 庭 的 VCD 或 者 DVD 播 放 器 一 样 VOD 的 实 质 是 信 息 使 用 者 根 据 自 己 的 需 要 主 动 获 得 多 媒 体 信 息, 他 和 信 息 发 布 和 广 播 的 区 别 在 于 主 动 性 和 交 互 性 这 种 信 息 服 务 方 式 符 合 人 们 对 信 息 资 源 更 深 层 次 的 需 要, 他 改 变 了 广 播 式 的 被 动 灌 输 方 式 由 于 它 打 破 了 以 往 传 统 的 影 音 服 务 的 局 限, 提 供 给 用 户 更 多 地 主 动 性, 因 此, 近 年 来 得 到 了 非 常 广 泛 的 应 用 视 频 点 播 技 术 是 在 电 脑 多 媒 体 技 术 通 信 的 分 组 交 换 技 术 数 字 和 光 纤 传 输 技 术 日 益 成 熟 的 条 件 下 发 展 起 来 的 电 脑 技 术 的 进 步, 尤 其 是 Web 技 术 的 发 展, 改 变 了 信 息 基 础 设 施 的 结 构, 包 括 信 息 的 生 成 存 储 传 送 和 表 现 形 式 等 方 面 现 在, 文 本 图 像 连 同 窄 带 视 频 信 号 已 数 字 化, 并 通 过 网 络 存 储 传 送 和 再 现 ; 但 是, 这 些 传 统 手 段 不 能 充 分 满 足 当 今 社 会 对 高 质 量 连 续 多 媒 体 ( 如 高 保 真 音 频 和 电 视 质 量 视 频 ) 的 应 用 需 要 校 园 多 媒 体 网 络 教 室 : 课 堂 上 的 教 师 可 以 根 据 需 要, 随 时 随 地 在 教 学 中 点 播 与 课 程 有 关 的 视 频 课 件 以 增 强 教 学 直 观 感, 丰 富 教 学 内 容 在 课 余 时 间 学 生 可 以 自 由 选 取 视 频 课 程 节 目 进 行 预 复 习, 以 增 强 学 习 兴 趣, 提 高 教 学 效 率 多 媒 体 图 书 馆 : 将 视 频 资 料 分 类, 提 供 视 频 资 料 自 由 选 取 预 览 索 引 查 询 分 类 管 理 等 功 能 企 业 内 部 培 训 : 提 供 教 材 管 理 线 上 随 选 阅 览 完 成 自 我 训 练 目 的, 提 高 员 工 技 能, 增 强 公 司 的 员 工 素 质 优 势. 多 功 能 网 吧 : 在 原 有 网 络 结 构 上 增 加 电 影 广 告 MTV 等 影 片 视 频 节 目 服 务, 可 拓 宽 营 业 项 目 KTV 点 歌 : 实 现 无 人 DJ 室, 降 低 人 工 管 理 成 本 统 一 存 储, 没 有 重 复 歌 曲 点 歌 迅 速, 热 门 歌 曲 不 用 等 候 第 2 页

第 1 章 绪 论 互 动 式 导 览 展 示 系 统 : 适 用 于 百 货 公 司 机 场 火 车 站 剧 院 和 博 物 院 等 公 共 场 所, 作 为 产 品 讲 解 说 明 服 务 内 容 介 绍 环 境 导 览 操 作 演 示 等 目 的 宾 馆 饭 店 : 可 以 将 一 些 经 典 影 片 卡 拉 OK, 菜 单 等 节 目 加 入 到 视 频 节 目 库 中, 使 入 住 客 人 在 自 己 客 房 中 根 据 兴 趣 和 时 间, 任 意 点 播 喜 欢 的 内 容 甚 至 可 以 将 客 人 关 心 的 当 天 时 事 新 闻 财 经 报 道 等 电 视 节 目 加 入 到 视 频 库, 使 客 人 在 错 过 节 目 播 放 时 间 的 情 况 下 仍 可 收 看 到 想 看 的 节 目 住 宅 小 区 : 为 小 区 提 供 新 的 服 务 内 容, 住 户 在 家 中 可 以 点 播 电 视 节 目 精 选 影 片 或 卡 拉 OK 伴 唱 等 可 以 丰 富 家 庭 文 化 娱 乐 生 活, 完 善 小 区 的 服 务 VOD 系 统 覆 盖 广 泛 的 领 域, 如 影 视 点 播 卡 拉 OK 远 程 教 学 公 司 培 训 广 告 亭 智 能 小 区 等 同 时, 将 这 样 的 媒 体 引 入 信 息 基 础 建 设 对 电 脑 研 发 带 来 了 新 的 挑 战, 因 为 他 们 自 身 的 固 有 属 性, 包 括 对 流 量 数 据 存 储 和 连 续 播 放 的 需 要 他 们 需 要 大 容 量 存 储 设 备, 需 要 宽 带 网 络 环 境, 最 主 要 的 是 必 须 确 保 实 时 传 输 传 统 的 技 术 不 能 满 足 严 格 的 实 时 性 和 大 容 量 需 要, 其 技 术 瓶 颈 特 别 反 映 在 网 络 带 宽 文 档 系 统 和 存 储 设 备 I/O 性 能 这 3 个 方 面 为 此, 许 多 解 决 方 案 应 运 而 生, 其 中 一 些 方 案 使 用 专 用 硬 件 平 台 或 终 极 电 脑 作 为 多 媒 体 服 务 器 然 而, 依 赖 硬 件 解 决 方 案 不 但 代 价 昂 贵, 而 且 会 给 今 后 的 扩 展 升 级 和 维 护 带 来 问 题 另 一 些 方 案 则 以 低 带 宽 连 接 为 目 标, 用 于 传 送 低 质 量 小 屏 幕 的 视 频 内 容, 例 如, 我 们 通 过 拔 号 上 网 收 看 的 一 些 节 目, 这 些 方 法 只 能 局 限 于 某 些 应 用, 无 法 确 保 高 质 量 视 频 点 播 的 需 要 1.1.2 流 媒 体 系 统 目 前 在 网 络 上 传 输 音 / 视 频 (A/V) 等 多 媒 体 信 息 主 要 有 两 种 方 案 : 下 载 和 流 式 传 输, 由 于 网 络 带 宽 的 限 制 A/V 文 件 所 需 的 存 储 容 量 大, 采 用 下 载 方 式 需 要 的 时 间 很 长 流 式 传 输 则 把 声 音 影 像 或 动 画 等 到 信 息 由 音 视 频 服 务 器 向 用 户 计 算 机 连 续 实 时 传 送, 用 户 不 必 等 到 整 个 文 件 全 部 下 载 完 毕, 而 只 需 经 过 几 秒 的 启 动 延 时 即 可 进 行 播 放, 当 音 频 视 频 等 媒 体 文 件 在 客 户 机 上 播 放 时, 文 件 的 剩 余 部 分 将 在 后 台 从 服 务 器 内 继 续 下 载 流 式 传 输 不 仅 使 启 动 延 时 成 十 倍 百 倍 地 缩 短, 而 且 不 需 要 太 大 的 缓 存 容 量 流 媒 体 指 在 Internet/Intranet 中 严 格 按 时 间 先 后 次 序 传 输 和 播 放 的 连 续 音 / 视 数 据 流 流 媒 体 具 有 三 个 特 点 : 连 续 性 (continuous) 实 时 性 (real-time) 时 序 性 (time-ordered), 即 有 严 格 的 前 后 时 序 关 系 与 传 统 的 多 媒 体 文 件 下 载 后 播 放 的 方 式 不 同, 流 媒 体 在 播 放 前 并 不 下 载 整 个 文 件, 只 将 部 分 内 容 缓 存 后, 流 媒 体 数 据 流 随 时 传 送 随 时 播 放 流 媒 体 技 术 所 提 供 的 播 放 功 能 交 互 性 能 和 缓 冲 区 功 能, 以 及 其 在 传 输 声 像 第 3 页

第 1 章 绪 论 文 件 时 表 现 出 的 占 用 硬 盘 小 速 度 快 高 保 真 等 性 能, 使 得 网 上 收 听 广 播 收 看 实 时 电 视 广 播 进 入 实 用 阶 段 流 媒 体 服 务 系 统 在 强 调 对 数 据 对 象 的 共 享 使 用 和 追 求 最 大 化 的 数 据 吞 吐 率 的 同 时, 更 强 调 对 高 速 稳 定 和 连 续 的 访 问 流 支 持, 强 调 对 同 步 的 支 持, 从 而 确 保 媒 体 数 据 的 按 时 到 达 流 媒 体 技 术 能 够 广 泛 应 用 于 多 媒 体 新 闻 发 布 在 线 直 播 网 络 广 告 电 子 商 务 视 频 点 播 远 程 教 育 远 程 医 疗 网 络 电 台 实 时 视 频 会 议 等, 它 丰 富 了 传 统 互 联 网 内 容 的 表 现 形 式, 赋 予 宽 带 应 用 更 多 的 娱 乐 性 和 互 动 性 流 媒 体 技 术 必 将 成 为 未 来 宽 带 网 络 业 务 的 主 流 技 术 实 时 性 和 质 量 是 流 媒 体 的 关 键 问 题 为 了 保 证 时 延 和 质 量, 网 络 必 须 提 供 足 够 的 带 宽 资 源, 而 资 源 的 保 证 又 依 赖 于 许 多 其 他 的 控 制, 如 流 量 控 制 拥 塞 控 制 等 当 网 络 资 源 变 化 时, 还 必 须 能 够 适 应 这 种 变 化 并 做 出 相 应 的 调 节 1.1.3 存 储 调 度 研 究 的 意 义 VOD 系 统 所 传 输 的 数 据 主 要 是 视 频 和 音 频 数 据, 这 些 数 据 同 传 统 的 文 本 和 数 字 数 据 有 着 很 大 的 不 同 (Gemmell,1995) 首 先, 音 视 频 文 件 通 常 被 称 为 连 续 媒 体, 也 就 是 说 他 们 是 由 连 续 的 数 据 单 元 所 组 成 ( 比 如 视 频 帧 或 者 声 音 采 样 ), 而 且 通 常 也 都 是 按 顺 序 为 用 户 服 务 ( 虽 然 用 户 也 可 能 会 暂 停 快 进 或 者 快 退, 但 是 这 些 操 作 同 传 统 媒 体 相 比, 概 率 要 低 很 多 ) 相 比 之 下, 文 本 和 数 字 数 据 则 会 经 常 出 现 随 机 访 问 其 次, 多 媒 体 数 据 通 常 含 有 非 常 大 的 数 据 量 一 个 普 通 质 量 的 10 分 钟 的 视 频 流 在 没 有 经 过 压 缩 的 情 况 下 需 要 1.5GB 的 存 储 空 间 即 使 是 经 过 压 缩, 他 也 需 要 100-600MB 的 存 储 空 间 下 表 列 出 了 常 见 的 多 媒 体 数 据 所 需 要 的 存 储 空 间 媒 体 类 型 数 据 速 率 语 音 级 别 音 频 单 声 道,8 bit 8kHz 采 样 率 64 Kbps MPEG 编 码 音 频 CD 音 质 音 频 384 Kbps CD 音 质 音 频 双 声 道,16 bit 44.1kHz 采 样 率 1.4 Mbps MPEG-2 编 码 视 频 NTSC 视 频 640*480 分 辨 率,24 位 色 HDTV 视 频 1280*720 分 辨 率,24 位 色 0.42 Mbps 27 MBps 81 MBps 表 1.1 常 见 多 媒 体 数 据 所 需 存 储 空 间 第 4 页

第 1 章 绪 论 由 于 视 频 对 象 的 巨 大 存 储 要 求 和 有 限 的 存 储 空 间, 每 个 服 务 器 都 只 能 存 储 有 限 数 量 的 视 频 流 而 且, 由 于 I/O 服 务 带 宽 的 限 制, 每 个 服 务 器 可 以 同 时 传 输 的 视 频 流 数 量 也 是 有 限 的 因 此, 视 频 文 件 的 存 储 调 度 涉 及 到 视 频 文 件 在 服 务 器 上 的 合 理 放 置 和 不 同 服 务 器 的 负 载 均 衡, 只 有 进 行 合 理 的 存 储 调 度 才 能 提 高 资 源 的 使 用 率, 提 高 真 个 系 统 的 性 能 1.2 研 究 现 状 1.2.1 VOD 系 统 分 类 VOD 系 统 可 以 分 为 两 大 类 : 单 服 务 器 结 构 和 分 布 式 结 构 单 服 务 器 的 优 点 是 实 现 和 管 理 非 常 简 单, 一 般 小 型 的 VOD 系 统 多 用 此 种 结 构, 其 服 务 器 可 以 采 用 普 通 的 PC 也 可 以 使 用 功 能 稍 强 的 小 型 机 但 是 单 服 务 器 结 构 的 VOD 系 统 存 在 着 很 多 难 以 克 服 的 局 限 性 其 中 最 突 出 的 一 点 便 是 服 务 器 的 服 务 能 力 和 容 错 性 单 服 务 器 的 CPU 处 理 能 力 和 存 储 容 量 等 都 非 常 有 限, 而 影 片 文 件 所 需 要 的 存 储 空 间 是 巨 大 的, 在 这 样 的 情 况 下, 单 服 务 器 系 统 就 的 存 储 影 片 数 量 和 并 行 服 务 用 户 数 都 有 很 大 的 局 限 另 外, 由 于 只 有 一 个 服 务 器, 一 旦 服 务 器 出 现 故 障, 将 会 影 响 整 个 系 统 的 运 行, 导 致 系 统 瘫 痪 分 布 式 结 构 与 单 服 务 器 系 统 的 不 同 之 处, 在 于 视 频 文 件 存 储 于 不 同 的 服 务 器 上, 点 播 压 力 和 存 储 压 力 被 很 多 服 务 器 所 分 担, 同 时 也 避 免 了 服 务 段 的 网 络 带 宽 瓶 颈, 提 高 了 系 统 的 容 错 性 能, 即 使 一 个 服 务 器 出 现 故 障, 也 不 至 于 影 响 到 整 个 系 统 的 运 行 目 前 大 规 模 的 VOD 服 务 系 统 都 采 用 了 分 布 式 结 构 分 布 式 系 统 的 研 究 主 要 需 要 解 决 以 下 几 个 问 题 : 存 储 空 间 的 有 效 利 用 问 题, 影 片 文 件 占 用 的 存 储 空 间 非 常 巨 大, 如 何 合 理 安 排 影 片 在 各 个 服 务 器 上 的 存 储, 才 能 有 效 利 用 各 服 务 器 的 空 间 是 一 个 研 究 问 题 (Burbeck,1996) 当 然, 目 前 存 储 设 备 的 容 量 不 断 增 加, 成 本 不 断 降 低, 这 个 问 题 已 经 不 是 很 突 出 负 载 平 衡 问 题 某 些 新 片 可 能 会 在 一 段 时 间 内 非 常 流 行, 被 用 户 大 量 点 播, 形 成 点 播 高 峰 ; 而 另 外 一 些 相 对 冷 门 的 影 片 的 点 播 率 则 比 较 低, 如 果 不 能 对 点 播 请 求 进 行 合 理 的 调 度, 就 会 造 成 某 些 服 务 器 不 堪 重 负 而 另 外 一 些 服 务 器 却 几 乎 空 载 的 情 况, 造 成 服 务 资 源 的 浪 费 (Serpanos,1996; Wolf,1997; Tsao,1999; Gonzalez,2002; Shu,2005) 容 错 能 力 问 题 VOD 系 统 中 的 某 些 服 务 器 可 能 会 因 为 软 件 或 者 硬 件 的 故 障 而 不 能 正 常 工 作,VOD 系 统 应 该 在 不 影 响 客 户 端 的 情 况 下, 将 故 障 服 务 器 的 工 第 5 页

第 1 章 绪 论 作 交 由 剩 下 的 正 常 服 务 器 分 担 (Anker,1999;Vin,1995;Golubchik,2001) 1.2.2 视 频 流 的 存 储 视 频 流 的 存 储 是 将 系 统 中 的 所 有 视 频 按 照 一 定 的 策 略 放 置 到 系 统 中 的 各 服 务 器 中 去 如 果 有 一 个 良 好 的 放 置 策 略, 就 会 给 系 统 的 负 载 均 衡 带 来 很 大 的 方 便 如 果 我 们 不 考 虑 当 用 户 被 服 务 的 时 候 交 换 对 其 进 行 服 务 的 媒 体 服 务 器, 那 么 我 们 就 应 该 在 分 配 视 频 文 件 的 时 候 使 得 每 个 服 务 器 都 有 相 同 的 被 请 求 的 概 率 通 常 有 两 种 方 法 来 达 到 这 种 平 衡, 也 就 是 复 制 和 分 条, 另 外 也 有 学 者 将 两 者 结 合 起 来 提 出 了 分 组 分 条 的 策 略 复 制 策 略 是 通 过 将 某 些 热 门 影 片 在 不 止 一 个 服 务 器 上 保 存 副 本, 来 实 现 负 载 在 各 个 服 务 器 上 的 均 衡 的 复 制 策 略 的 典 型 代 表 是 Serpanos 等 (1996) 提 出 的 一 种 被 称 为 MMPacking 的 算 法 在 MMPacking 中, 视 频 流 根 据 其 点 播 概 率 以 升 序 排 列, 从 点 播 概 率 最 低 的 影 片 开 始, 以 轮 询 的 方 式 放 置 到 每 一 个 视 频 服 务 器 上 当 一 个 视 频 流 被 分 配 到 多 媒 体 服 务 器 上 的 时 候, 就 计 算 该 服 务 器 的 累 积 的 被 请 求 概 率 如 果 概 率 高 于 平 均 请 求 概 率 ( 也 即 是 1/N, 当 服 务 器 数 为 N 时 ), 就 对 当 前 的 视 频 流 生 成 一 个 副 本 放 置 到 下 一 个 服 务 器 上 复 制 的 缺 点 之 一 在 于 它 的 容 量 整 个 影 片 副 本 都 放 在 一 个 服 务 器 上, 服 务 性 能 就 受 到 了 单 盘 I/O 带 宽 的 限 制 当 需 求 超 过 了 服 务 器 的 服 务 能 力 的 时 候, 就 需 要 将 影 片 复 制 到 其 他 磁 盘 上, 增 加 了 系 统 的 容 量 要 求 也 有 一 些 学 者 提 出 了 减 少 存 储 浪 费 的 算 法, 这 些 算 法 都 是 基 于 存 储 容 量 和 带 宽 相 同 的 服 务 器 的 (Bisdikian,1995; Venkatasubramanian, 1997) 复 制 通 常 用 在 各 视 频 服 务 器 距 离 较 远, 难 以 采 用 分 条 策 略 的 分 布 式 VOD 系 统 中 分 条 策 略 的 最 初 想 法 是 使 用 磁 盘 冗 余 阵 列 (RAID), 将 一 部 视 频 分 成 多 个 块 分 别 存 储 到 所 有 的 服 务 器 中 (Tewari,1995;Tewari,1996;Bolosky,1996) 这 种 架 构 下 的 VOD 系 统 被 称 为 并 行 视 频 服 务 器 (Lee,1998) 分 条 可 以 将 数 据 透 明 地 分 布 到 多 个 磁 盘 中, 而 让 用 户 感 觉 自 己 是 在 使 用 单 一 的 快 速 磁 盘 用 户 请 求 造 成 的 负 载 被 均 匀 分 布 到 整 个 磁 盘 阵 列 中, 很 好 地 消 除 了 影 片 之 间 热 度 不 均 对 负 载 均 衡 造 成 的 不 良 影 响 然 而, 在 不 同 的 分 条 服 务 器 之 间 同 步 确 是 一 个 难 题 由 于 网 络 延 迟 调 度 等 原 因, 不 同 的 服 务 器 可 能 会 在 不 同 的 时 间 开 始 数 据 传 输 第 一 个 分 条 数 据 甚 至 可 能 会 在 其 他 分 条 到 来 之 后 才 姗 姗 来 迟 由 此 造 成 了 客 户 端 必 须 缓 存 一 部 分 乱 序 的 数 据 并 且 等 待 第 一 个 分 条 数 据, 造 成 了 开 始 播 放 的 延 迟 分 组 分 条 将 纯 粹 的 分 条 策 略 和 复 制 策 略 结 合 起 来 每 个 媒 体 服 务 器 都 有 一 部 分 分 条 设 置, 而 同 时 也 根 据 预 测 的 用 户 请 求 概 率 将 某 些 最 热 门 的 影 片 副 本 复 制 到 服 务 器 中 在 这 种 算 法 下, 媒 体 服 务 器 也 被 称 为 分 条 磁 盘 组 (Disk-Striping 第 6 页

第 1 章 绪 论 Group DSG)(Wolf,1997) 一 些 学 者 基 于 这 种 思 想 提 出 了 在 媒 体 服 务 器 之 间 达 到 静 态 负 载 均 衡 的 算 法 (Wolf,1997;Tsao,1999;J.Guo,2003) 1.2.3 服 务 器 间 的 负 载 均 衡 视 频 文 件 在 媒 体 服 务 器 之 间 的 复 制 可 以 实 现 实 时 负 载 迁 移, 达 到 负 载 均 衡 Wolf 等 (1997) 提 出 了 DASD 跳 舞 算 法 来 通 过 负 载 迁 移 平 衡 服 务 负 载 Tsao 等 (1999) 提 出 了 分 布 式 VOD 系 统 动 态 负 载 均 衡 的 连 接 优 化 算 法, 他 们 的 算 法 通 过 使 个 服 务 器 的 被 访 问 概 率 相 等 来 达 到 负 载 均 衡 的 目 的 Y.Guo 等 (2003) 提 出 了 基 于 视 频 复 制 的 组 合 式 负 载 均 衡 (Combination Load Balancing,CLB) 来 降 低 用 户 请 求 的 拒 绝 率 这 些 算 法 都 是 在 服 务 器 负 载 超 过 一 定 的 阀 值 或 者 用 户 请 求 被 拒 绝 的 时 候 来 进 行 请 求 迁 移 但 是, 在 某 些 影 片 热 度 极 度 不 均 的 系 统 中, 某 些 媒 体 服 务 器 可 能 已 经 达 到 负 载 上 限 而 不 能 继 续 接 受 任 何 用 户 请 求 的 迁 入, 这 样 就 可 能 导 致 增 加 用 户 初 始 播 放 延 迟 或 者 用 户 请 求 被 拒 绝 1.2.4 动 态 内 容 更 新 策 略 由 于 分 布 式 VOD 系 统 的 服 务 器 连 接 在 广 域 网 中, 因 此 用 户 请 求 模 式 会 随 着 时 间 推 移 而 发 生 变 化 视 频 在 各 服 务 器 上 的 副 本 需 要 定 期 进 行 动 态 更 新 以 防 止 系 统 过 于 臃 肿 或 者 降 低 效 率 Radoslavov 等 (2001) 提 出 了 一 种 简 单 但 是 有 效 的 基 于 服 务 器 连 接 度 的 初 始 放 置 策 略, 这 种 策 略 仅 考 虑 静 态 放 置 当 用 户 请 求 模 式 随 着 时 间 发 生 改 变, 这 个 系 统 不 可 避 免 地 效 率 降 低 Rabinovich 等 (1999) 研 究 了 动 态 对 象 复 制 技 术, 在 他 们 的 研 究 中, 视 频 对 象 的 大 小 通 常 都 是 几 KB 大 小, 而 服 务 时 间 则 可 以 忽 略 不 计 Y.Guo 等 (2003) 研 究 了 集 中 式 VOD 系 统 的 动 态 内 容 重 分 布 问 题 1.3 本 文 研 究 的 工 作 在 大 规 模 VOD 集 群 系 统 中, 由 于 影 片 的 热 度 不 均 造 成 的 各 服 务 器 之 间 的 负 载 不 均 衡 的 情 况 一 直 是 学 者 们 研 究 的 课 题 对 于 这 个 问 题 一 般 有 两 种 解 决 方 法, 一 种 是 复 制, 另 一 种 是 分 条 由 于 视 频 数 据 的 数 据 量 通 常 十 分 庞 大, 因 此, 复 制 的 策 略 对 存 储 空 间 造 成 的 浪 费 是 显 而 易 见 的 分 条 的 技 术 应 用 在 了 很 多 公 司 的 服 务 器 产 品 中, 但 是 分 条 的 技 术 也 有 其 缺 陷 性 其 中 一 点 即 是 影 片 的 内 热 度 不 均 所 带 来 的 问 题 由 于 用 户 在 点 播 影 片 的 时 候 并 不 总 是 从 头 观 看 到 尾, 很 有 可 能 会 出 现 中 途 中 第 7 页

第 1 章 绪 论 断 点 播 的 情 况 甚 至 有 研 究 表 明 ( 吴 松,2006), 很 多 用 户 会 在 点 播 的 前 5 分 钟 内 中 断 点 播 因 此, 影 片 的 各 个 部 分 被 观 看 的 概 率 实 际 上 有 着 很 大 的 差 距 影 片 开 头 的 部 分 比 影 片 末 尾 的 部 分 有 着 高 得 多 的 被 访 问 概 率 传 统 的 分 条 方 式 将 影 片 各 部 分 均 匀 分 条 存 储 到 各 服 务 器 中, 很 好 地 解 决 了 影 片 间 热 度 给 负 载 均 衡 带 来 的 不 利 影 响, 但 是 却 因 为 影 片 内 热 度 的 原 因 带 来 了 新 的 问 题 本 文 通 过 研 究 用 户 的 访 问 行 为 模 式, 提 出 了 影 片 内 热 度 的 研 究 模 型, 并 根 据 该 模 型 提 出 了 改 进 的 分 条 存 储 策 略 同 时, 通 过 对 系 统 的 仿 真 模 拟, 得 出 了 评 估 系 统 性 能 的 一 系 列 参 数 1.4 本 文 内 容 安 排 本 文 主 要 研 究 了 VOD 系 统 中 的 存 储 调 度 相 关 问 题, 讨 论 了 在 有 限 的 服 务 资 源 条 件 下, 如 何 通 过 对 资 源 的 合 理 分 配 和 调 度 来 达 到 服 务 器 之 间 的 负 载 均 衡, 提 高 系 统 性 能, 以 服 务 更 多 的 用 户 针 对 当 前 存 储 调 度 的 研 究, 讨 论 了 VOD 系 统 中 的 各 相 关 技 术, 集 中 分 析 了 用 户 在 视 频 点 播 时 候 的 行 为 模 式 对 负 载 均 衡 的 影 响, 并 提 出 了 新 的 存 储 调 度 策 略, 以 及 讨 论 了 存 储 调 度 系 统 在 工 程 上 实 现 的 问 题 本 文 的 具 体 内 容 安 排 如 下 : 第 一 章 讨 论 了 本 文 研 究 的 背 景 和 意 义, 概 述 性 地 介 绍 了 视 频 点 播 和 流 媒 体 系 统 的 基 本 概 念 和 主 要 特 点 简 述 了 国 内 外 的 相 关 研 究 情 况, 当 前 视 频 点 播 的 研 究 热 点 问 题 并 且 概 述 了 本 文 作 者 所 研 究 的 工 作 第 二 章 介 绍 了 视 频 点 播 的 相 关 技 术 首 先 概 述 了 流 媒 体 服 务 系 统 的 技 术 问 题, 由 于 基 于 集 群 技 术 的 视 频 点 播 系 统 正 受 到 越 来 越 多 的 关 注, 首 先 介 绍 了 计 算 机 集 群 技 术 的 发 展 和 应 用 ; 接 着 介 绍 了 VOD 系 统 架 构 的 问 题, 形 象 说 明 了 VOD 系 统 的 结 构 组 成 和 各 部 分 关 系 接 着 讨 论 了 视 频 文 件 的 存 储 调 度 算 法 和 磁 盘 调 度 算 法 问 题 以 及 请 求 分 配 与 迁 移 介 绍 了 两 种 视 频 流 服 务 策 略 : 客 户 拉 和 服 务 器 推 的 策 略, 目 前 这 两 种 策 略 都 有 着 广 泛 的 应 用 同 时 简 要 介 绍 了 交 互 式 VOD 的 发 展 和 特 征, 目 前 交 互 式 VOD 是 研 究 的 一 个 重 要 方 向 本 章 最 后 介 绍 了 流 媒 体 传 输 的 协 议,RTP 协 议 是 最 适 合 于 进 行 流 媒 体 传 输 的 协 议, 因 此 对 其 进 行 了 介 绍 第 三 章 讨 论 了 流 媒 体 服 务 系 统 存 储 调 度 的 相 关 问 题 首 先 分 析 了 用 户 行 为 模 式 由 于 用 户 的 行 为 模 式 引 起 的 影 片 间 热 度 不 均 和 影 片 内 热 度 不 均 问 题 接 着 讨 论 了 文 件 的 分 割 与 服 务 拒 绝 率 的 问 题, 通 过 从 特 殊 到 一 般 的 方 法 得 出 了 文 件 分 割 与 服 务 拒 绝 率 之 间 的 量 化 关 系 视 频 文 件 的 复 制 和 分 条 是 常 见 的 两 种 抑 制 文 件 间 热 度 不 均 对 负 载 均 衡 影 响 的 策 略, 本 章 也 对 它 们 进 行 了 介 绍 接 下 来 详 细 介 绍 了 改 进 的 磁 盘 调 度 策 略, 改 进 的 策 略 针 对 影 片 内 热 度 不 均 进 行 了 处 理 和 分 析, 以 最 大 程 度 消 除 影 片 内 热 度 不 均 给 传 统 分 条 技 术 带 来 的 局 限 性 本 章 最 后 讨 论 了 对 应 于 第 8 页