缓冲区有限流量整形器性能参数的最小加代数表示.pdf

第 39 卷 第 10 期 2005 年 10 月 西 安 交 通 大 学 学 报 JOURNAL OF XI AN JIAOTONG UNIVERSITY Vol 39 10 Oct 2005 缓 冲 区 有 限 流 量 整 形 器 性 能 参 数 的 最 小 加 代 数 表 示 高 岭 1 2 李增智 1 王 峥 2 高 鹏 2 胡青山 2 1 西安交通大学电子与信息工程学院 710049 西安 2 西北大学计算机科学系 710069 西安 摘要 针对目前在流量整形器建模中将整形器视为无限缓存设备的缺陷 基于网络演算 使用最小加代数建 立了有限缓冲区的流量整形器 FSS 模型 获得了 FSS 的分组时延和分组丢失与预留缓存空间的关系 给 出了 FSS 性能参数的最小加代数表示 研究结果表明 当贪心整形器的服务曲线大于业务流的到达曲线时 整形器的引入不会额外增加业务流丢失的分组数 而整形器的缓冲特性能够减少网络中业务流丢失的分组 数 在给定目标服务质量参数的前提下 相关结论可用于确定资源预留的上界 以改进网络的规划与设计 关键词 流量整形器 最小加代数 网络演算 中图分类号 TP393 文献标识码 A 文章编号 0253 987X 2005 10 1068 04 Min Plus Algebra Representation for Performance Parameters with Finite Flow Shaper in Buffer Gao Ling 1 2 Li Zengzhi 1 Wang Zheng 2 Gao Peng 2 Hu Qingshan 2 1 School of Electronics and Information Engineering Xi an Jiaotong University Xi an 710049 China 2 Department of Computer Science Northwest University Xi an 710069 China Abstract Aiming at the flaw that the shaper is regarded as an unlimited storage device when modelling the flow shaper a finite storage shaper FSS model was built by min plus algebra based on network calculus The relation between the packet delay and packet loss of FSS and the reserved buffer space was obtained and the FSS performance parameters were represented by min plus algebra Research results show that the shaper will not extra increase the packet number of flow loss when the greedy service curve of shaper is lar ger than the arrival curve of the flow and the buffering characteristic of the shaper can decrease the packet number of the flow loss in the network The results can be applied to determining the upper bound of re source reservation so as to improve the design of network when the target parameters of quality of service are given Keywords f low shaper min plus algebra network calculus 为了实施拥塞控制 保证服务质量 QoS 带宽 利用的公平性 需要通过整形器对进入网络节点的 业务流进行监督和调节 使其符合预先设定的流量 规约 1 近年来 以 整形器为基础的网络演算技 术研究取得了一定的进展 2 5 它基于最小 加代数 Min Plus Algebra MPA 是通过定义一系列的 到达曲线 服务曲线等演算工具 使得网络服务性能 的界限描述得更加简洁 网络演算被广泛应用于网络 QoS 研究的建模 和理论分析中 如利用网络演算建立的确保速率服 务和延迟速率服务的关系模型 4 基于网络演算的 参数区分网络服务的接纳控制模型 6 将网络演算 作为数学工具 研究漏桶模型下的接纳控制模型 7 本文研究了有限缓冲区的流量整形器 FSS 及 其特性 给出了缓冲区有限的有损整形器的时延和 收稿日期 2005 02 04 作者简介 高 岭 1972 男 博士生 李增智 联系人 男 教授 博士生导师 基金项目 国家高技术研究发展计划资助项目 863 511 946 008 分组丢失数等性能参数的 MPA 表示 讨论了贪心 整形器的引入对分组时延和分组丢失等网络性能的 影响 1 网络演算 网络演算 2 4 8 10 可以看作 MPA 在流问题上的 应用 包括了到达曲线 服务曲线 MPA 卷积 反 卷积等内容 定义 1 广义增函数集 G f t f 0 0 s t f s f t t 0 1 F f t f t G f 0 0 2 式中 f 为左连续函数 网络演算的代数结构为 R 其中 R 为实数域 为最小运算 满足 f g t min f t g t 为加运算 满足 f g t f t g t 定义 2 MPA 卷积运算式为 f g t inf 0 s t f t s g s 3 定义 3 MAP 反卷积运算式为 f g t sup s 0 f t s g s 4 推论 1 运算满足交换律 结合律 运算满足分 配律 定义 4 F R t 为一累积函数 表征在 t 时刻进 入系统的流量总和 如果 R 满足 R t R t inf 0 s t F s t s 5 称 为到达曲线 或称 R是 平滑的 定义 5 对于输入函数为 R 输出函数为 R 的系统 S 当且仅当 R R 则称系统 S 提供了服务曲 线 F 定义 6 对于 f F 若 f t1 t2 f t1 f t2 则称 f 满足次可加性 定义 7 对于 f F 其次可加闭包 f 满足 珚 f f 0 f ff inf n 0 f n 6 定理 1 对于 f F 其次可加闭包 f 满足珚 f f 珚 f F 且 f 满足次可加性 定义 8 对于 F x t F 则线性等分运算子 h x t inf 0 s t t s x s 7 定理 2 线性运算子的子加闭包操作 珚 LH满足 珨 H t s inf n N infun u2 u1 H t u 1 H u1 u2 H un s 8 且有 珚 LH LH 推论 2 令 L1表示 F F 的一个线性等分运算子 F 则有 L1 h h L1 h 成立 2 缓冲区有限的有损整形器 定义 9 整形器以对输入业务流进行缓冲的方式 依据定义的服务曲线输出业务流 整形器的基本功能是 调节业务流的流量 使之 符合流量规范的要求 7 定义 10 FSS 是一种缓冲区有限且不能保证输入 业务流无损失 但输出为最大允许值的整形器 为使结论一般化 本文对网络业务流的类型未 另作假设 但考虑了缓冲区大小对分组丢失的影响 合适的缓冲区对于整形器的设计而言是相当重要 的 如果缓冲空间设置得过小 会导致整形器频繁的 丢弃到达的分组 从而影响网络性能 令 D t 表示在 t 时刻 FSS 所丢弃的业务流总 数 其中 D 0 0 引理 1 令 x t 表示在 t 时刻进入 FSS 的业务流总 量 t 为 FSS 的到达曲线 则 FSS 丢弃分组的总 数为 D t x t t t 0 9 定理 3 若整形器 FSS 的服务曲线为 缓冲区长度 为 B 到达曲线为 则整形器累积丢弃的分组总数 D t sup sup n i 0 s2 i 1 s2 i s2i 1 s2 i nB 10 其中 s1 s2 s2 n n N 0 s1 s2 s2 n t 证明 由定义 8 知 对于 0 s t 在 t 时 刻进入 FSS 的业务流总量 x t inf 0 s t t s x s h x t 又由 x t t h x t t B 有 x h B h h B 由定理 2 及推论 2 有 D t t x t t h B t t inf h B n t sup t inf t n i 1 s2i 1 s2i s2 i 1 s2i B sup sup n i 0 s2 i 1 s2i s2 i 1 s2i nB 9601 第 10 期 高 岭 等 缓 冲区 有限流 量整 形器性 能参 数的最 小加代 数表 示 定理 4 给定 FSS 所允许的丢弃最大业务流总量为 P 服务曲线为 到达曲线为 则 FSS 所需的缓冲 区 BL 1 n sup t n i 1 s2i s2i 1 P s2 i P s2 i 1 11 其中 s1 s2 s2 n 0 s1 s2 s2 n t 证明 由 FSS 的定义可知 P t t t BL 则有 P t t t BL 由此得 P t t inf t BL n 这样 nBL t inf t P t nBL t inf n i 1 s2 i s2 i 1 P s2 i P s2i 1 因此 所需缓冲区大小的上界满足 BL 1 n sup t n i 1 s2i s2i 1 P s2 i P s2 i 1 定理 5 若整形器 FSS 缓冲区长度为 B 流 i 的到 达曲线为 i FSS 为该流提供的服务曲线为 i 则 流 i 的时延 d i sup 0 i t n k 1 i nB 0 t 0 12 其中 n 为离散时间序列集 tk t0 0 t1 t2 tn 1 tn t 的长度 证明 在 t 时刻 流 i 所 在队 列 的长 度 为 O i t 且 O i 0 0 由推论 2 知 O i t 满 足 O i i i B i i B 对于分组时延 d i 有 di inf 0 O i s i s 考虑一极小值 0 则 d i sup 0 O i s i s 0 sup 0 i s i s BL i s 0 sup 0 i s i s B n s n 0 sup 0 i s n k 1 i nB 0 进而得 d i lim 0 sup 0 i s n k 1 i nB 0 sup 0 i s n k 1 i nB 0 定理 5 是单个排队队列的时延结果 关于整形 器 FSS 的最大时延和平均时延 有如下推论 推论 3 若整形器 FSS 缓冲区长度为 B 调度队列 总数为 m 流 i 的到达曲线为 i FSS 为该流提供 的服务曲线为 i 则整形器的最大时延为 dmax sup i N 1 i m sup 0 i s n k 1 i nB 0 13 平均时延为 davg 1 m m i 1 sup 0 i s n k 1 i nB 0 14 定义 11 如果整形器能尽可能地发送数据 则称这 个整形器是贪心整形器 贪心整形器是一种常见的整形器 如果其服务 曲线 t 贪心整形器可以作为漏桶控制器 2 定理 6 8 9 假定一个受限于到达曲线 的业务流 依次经过网络节点 S1 S2 当一个具有服务曲线 的贪心整形器置于 S1与 S2之间时 若 F 且满 足次可加性质 则整形器的引入不会改变业务流的 时延上界 定理 7 假定一个受限于到达曲线 的业务流 依 次经过网络节点 S1 S2 当一个具有服务曲线 的贪心整形器置于 S1与 S2之间时 若 F 且满 足次可加性质 则整形器的引入不会额外增加分组 丢失数目 证明 受限于到达曲线 的业务流同样受限于珔 由次可加的闭包的保持性知 珔 F 由定理 1 知 珔 因此业务流的到达曲线可视 为珔 当网络中没有整形器时 网络的服务区曲线为 1 2 1 2分别为 S1 S2为该业务流提供的服务 曲线 则丢失的分组数 D1 珔 1 2 将整形器 放入 S1与 S2之间时 因为 F 所提供的服务曲 线为 1 2 1 2 则丢失的分组数 D2 珔 1 2 若 1 2 珔 有 D1 珔 1 2 0 又因 珔 有 1 2 1 2 故有 D2 D1 0701西 安 交 通 大 学 学 报 第 39 卷 若 1 2 珔 则 D1 珔 1 2 0 又因 珔 有 1 2 珔 故有 D2 D1 0 由此知 整形器的引入不会额外增加业务流丢 失的分组数 以 1 2 珔 的情况可知 整形器的缓 冲特性能够减少网络中业务流丢失的分组数 若 显然整形器的引入会额外增加分组丢 失数 若网络中所有的整形器均为同一贪心整形器 时 第一个整形器会引入额外的分组丢失数目 定理 6 定理 7 的结果表明 当贪心整形器的服 务曲线大于业务流的到达曲线时 整形器的引入能 够改善网络的服务质量 3 结 论 本文基于网络演算 利用 MPA 给出了有限缓 冲区的流量整形器的一般模型 通过研究 得到了流 量整形器的分组丢失数 分组时延与预留缓冲空间 的关系 给 出了 这些 关系 的 MPA 表 示 同 时 用 MPA 方法 证明了在一定条件下引入贪心整形器 能够改善网络的服务质量 相关结果也可用于网络 设备的性能参数的定性分析 从而使得网络性能界 限的表述更加简洁 参考文献 1 FC2475 1998 An architecture for differentiated serv ices S 2 Chang C S Stability queue length and delay part I deterministic queuing networks R IBM Technical Report RC 17708 New York IBM 1992 3 Cruz R L A calculus for network delay part I net work elements in isolation J IEEE Transactions on Information Theory 1991 37 1 114 131 4 Cruz R L A calculus for network delay part II net work analysis J IEEE Transactions on Information Theory 1991 37 1 132 141 5 Yuming J Relationship between guaranteed rate serv er and latency rate server J Computer Networks 2003 43 3 307 315 6 Markus F Volker S A parameter based admission control for differentiated services networks J Com puter Networks 2004 44 4 463 479 7 Urvoy G Dallery Y H buterne G CAC procedure for leaky bucket constrained sources J Performance Evaluation 2000 41 2 117 132 8 Boudec J Y L Thiran P Lecture notes in computer science network calculus M Berlin Springer Ver lag 2001 9 张信明 陈国良 顾 钧 基于网络演算的流量整形模 型 J 软件学报 2002 13 12 2 225 2 230 10 Boudec J Y L Thiran P Lecture notes in computer science application of network calculus to the Internet M Berlin Springer Verlag 2001 编辑 苗 凌 上接第 1067 页 3 aswani N Garcia Molina H Yang B Open prob lems in data sharing peer to peer systems A The 9th International Conference on Database Theory Sie na Italy 2003 4 Stoica I