为了正常的体验网站,请在浏览器设置里面开启Javascript功能!

基于静态优先级的ATM网延迟算法

2017-12-21 6页 doc 41KB 17阅读

用户头像

is_321635

暂无简介

举报
基于静态优先级的ATM网延迟算法基于静态优先级的ATM网延迟算法 基于静态优先级的 ATM 网延迟算法 1 2 2 3柳 文,过 莉,张立臣,李曙平 (11 广东工业大学建设学院计算中心 ,广东 广州 510643 ; ) 21 广东工业大学计算机学院 ,广东 广州 510643 ; 31 湘潭船舶厂 ,湖南 湘潭 411100 摘要 : 利用到达和服务与时间的反函数 ,获得了一种计算与 ATM 交换连接的最坏情况延迟的直接算法. 在借鉴经 典的强实时系统静态优先级调度理论的基础上 ,通过引入分区算法来计算 ATM 交换的延迟 ,在指定的时限内传送 ...
基于静态优先级的ATM网延迟算法
基于静态优先级的ATM网延迟算法 基于静态优先级的 ATM 网延迟算法 1 2 2 3柳 文,过 莉,张立臣,李曙平 (11 广东工业大学建设学院计算中心 ,广东 广州 510643 ; ) 21 广东工业大学计算机学院 ,广东 广州 510643 ; 31 湘潭船舶厂 ,湖南 湘潭 411100 摘要 : 利用到达和服务与时间的反函数 ,获得了一种计算与 ATM 交换连接的最坏情况延迟的直接算法. 在借鉴经 典的强实时系统静态优先级调度理论的基础上 ,通过引入分区算法来计算 ATM 交换的延迟 ,在指定的时限内传送 完所有的信息 . 仿真实验结果表明 ,基于静态优先级的分区算法明显优于直接算法 ,ATM 交换网连接的允许可能性 平均提高 10 %. 关键词 : 延迟 ; 分区算法 ; 静态优先级 () 中图分类号 : TP397 文献标识码 : A 文章编号 : 100529792 20020320322203 ( ) 实时系统是能够在确定的时间内执行计算或处达网络入口的最大信元数 A I为 : i ( ) ( βλ) A I= min I ,+ I= 理事物并对外部异步事件作出响应的计算机系统 ,i i i 实时系统的正确性不仅依赖于计算结果的正确性 , I , 0 ?I ?I;i ( )1 23 1 而且依赖于计算结果产生的时间. 根据时限的严 β λ + I , I ?I. i i i 格程度和超过限制时间后果的严重性 ,通常将实时 其中 : 系统分为两类 : 强实时和弱实时系 统 . ATM 网 越 来 β iI= ;i 越多地普及于支持强实时系统的应用 . ATM 是一种 λ 1 - i 面向连接的包交换技术 ,也就是说 ,当 2 台计算机通 βλ 为最大令牌数 ;为令牌在漏桶中的自动流动速 讯时必须首先建立连接 . 一个新的连接要求具有一 率 . () 定的服务质量 QOS,而且只有当网络能够保证所 在 1 个 ATM 网中 ,主机连接到 ATM 交换 ,ATM要求的服务质量没有违犯当前已激活连接的保证书 交换被连接至每个其他可用物理链接 . 1 个 ATM 交 时才许可连接 . 为了保证每次特定的连接信息时限 , 换由输入端 、交换结构和输出端组成. 信元在输入端 必须得到对应一次 ATM 交换的一次连接中所有传 口控制和交换结构中的延迟是常数 ,但在输出端口 送信元的最坏情况信元延迟. 在此 ,作者分析和讨论 控制的延迟是不同的 ,从不同连接来的信元在此被 了最坏情况信元延迟的算法和连接允许控制 . 多路复用 ,信元延迟取决于输出端口队列长度和调 4 ,5. 采用输出端口控制配置漏桶 规 则 和 应度技术 1 模型建立 用优先级驱动的调度策略 ,其模型如图 1 所示. 设 M = { M, M,, M} 表 示 N 个 连 接 的 集 1 2 N ( ) 合 , 认为网络已经允许一系列 i - 1个连接 , 并且都 满足其时限约束. 一个新的强实时连接 M到达 , 令 i D是属于连接 M的信元的相对时限. 时限是一个i i 固定的性能要求. 同时 , 令 d表示属于连接 M的最 i i 坏情况信元延迟. 这个延迟随网络中负荷变化而变 化 . 对连接 M, 假定在任一经历时间长度 I 后 , 其到 i 图 1 优先级驱动调度策略的数学模型 收稿日期 :2001 - 09 - 21 () 基金项目 :国家自然科学基金资助项目 69874024 () 作者简介 :柳 文 1967 - ,女 ,湖南长沙人 ,硕士 ,从事实时系统研究. 为 2 延迟计算和分区算法 - 1 - 1 ( ) ( ) d= max[ S c- A c. ( )5 i c ?0 - 1 - 1 ( ( ) ( ) ( ) ) 其中 : S c和 A c分别是 S I 和 A I 的反 i i 为了方便 ,将控制传输信元的实体称为服务器 , 函数.因此 ,输出端口控制也是一个由优先级驱动和漏桶 ( ) ( ) 将式 4代入式 5, 则得 :校准组合的服务器. 一个连接的信元通过服务器时 i - 1 被延迟 ,是因为服务器没有用全速率服务这个连接 ,λk6 ββ+′ k = 1 i i 这可能是服务器共享了其他连接 .(θθ) ()d= max I+,+. 6 i - 1 i i i i λ i λ( ) 1 - 定义 S I是连接 M的最小有价值服务函数 ,ki i 6 k = 1 即分区算法步骤如下 : ( ) ( ) ()S I= min[ S t , I. 2 i i a1 将所有连接初始化在同一子集中 . 对所有元 如果 1 个优先级调度服务器服务 2 个连接 , 其 素指定一优先级 P. ( ) 最大到达函数如式 1所示 , 假定 M的优先级高于1 () b1 用式 6计算子集中每个连接的延迟 ,如果所 M,那么给予 M是连接的最高优先级 , 对 I ?0 , 有2 1 有连接通过时限测试 ,结束计算 . ( ) S I= I . 而 M的情况与此不同 , 对于一个时间经 1 2 c1 为没有通过时限测试的连接增加一个子集 ,历长度 I , 对 2 个连接的总的有价值服务数是 I 信 对子集中所有连接指定一优先级 P - 1 .( ) 元 . 给出连接 M 到达的最大信元数是 AI , M的 1 2 () d1 用式 6计算每个连接的延迟 ,若所有连接通 ( ) () () 有价值服务数就是 I - AI, 将 1式代入 2, 则有 1 过时限测试或 P - 1 = 0 ,则结束计算 . β e1 否则 ,返回步骤 c1.10 , 0 ?I ? ; λ1 - 1( ) ()3 S I= 2 β 1(λ) β1 - I - , I > .3 仿真实验及性能评估 11 λ 1 - 1 假定优先级指定跟连接的索引顺序相同 , 即 M 17 用离散事件仿真模型仿真 ATM 交换 ,仿真程 拥有最高优先级 , 而 M 是最低优先级 , 连接 M 的 n i 序用 MATLAB 5 . 0 编写. 系统选用 4 个参数 : I 是每 最小有价值服务函数用分段线性函数表示为 : λβ个连接的呼叫保持时间 ,从指数分布中选择 ;,和 D θ0 , 0 ? I?; i i - 1 从均匀分布中选择. 3 (λ) ( θ) θ1 - I - ,( ) S I= < I < I ; Ki ii 6 ( 对每次仿真运行 ,计算其允许可能性 AP Admis2K = 1 ) sion probability, 用 以 反 映 系 统 的 性 能 , 计 算 公 式 如 3 3 3 λ( )( ) I - I + S I , I . I > i i 下 : ()4 i - 1 N 受( ) 7 βA P = ×100 %.K 6 N β 达 ′ K = 1 i3 θθ其中 := , I = + .i - 1 i i 式中 , N 是被接受连接的数量 ; N 是所有到达的 受 达 λλ1 - 1 - KK 6 6 K = 1 K = 1 连接数. β是输出端口的令牌数 , 取值为 仿真实验中 , 一次产生超过 5000 次连接 , 参数 i - 1 λ域依 据 一 视 频 文 件 系 统 参 数 选 取 , 总 信 元 数 为 k6 k = 1 ββλβ′= - I?. i - 1 ii i ii 174 056 ,最大数据率为 10 896 信元/ s ,平均数据率为λ1 - k6 768 信元/ s ,平均相关时限为 40 ,时限偏差范围 k = 1 为 ?30 . 图 2 显示根据直接算法和分区算法使用优 实时连接通信和有价值服务函数都可用分段线 [3 , 6 ] 先级驱动服务器的允许可能性的实验结果 ,利用率 性函数来描述. 假定一个顺序和常态的服务器服 性平均高出 10 %.分区算法来进行连接允许控制 ,该算法明显优于直 接算法 ,ATM 交换连接的允许可能性平均提高 10 %. 参考文献 : 2chen , Alceu H A , Wolfgang A H. Real time programing ZHANG Li1 M. Shantou : Shantou University , 1998 . Li C Z , Bettati R , Zhao W. Static priority scheduling for ATM net2 2 worksA . The IEEE REAL TIME SYSTEMS SYMPOSIUM 1052 28725 C. San Francisco , 1997 : 264 2273 . 3 Ng J , Song S , Zhao W. Integrated delay analysis on regulated ATM switchA . The IEEE Real Time Systems Symposium 1052 28725 C . —分区算法数据 ; 2 —直接算法数据 1 San Francisco , 1997 : 2852297 . 仿真实验曲线图图 2 4 盛友招. 排队论及其在计算机通信中的应用 M . 北京 : 北京邮 电大学出版社 ,1998 . Ermedahl A , Hansson H , Sjodin M. Response2time guarantees in ATM 5 networks A . The IEEE Real Time Systems Symposium 1052 28725 C. San Francisco , 1997 : 274 2284 . 6 Song S , Ng J , Tang B. Efficient delay computation methods for an ATM 4 结论 network with real2time video traffic A . The IEEE REAL TIME SYS 2 TEMS SYMPOSIUM 105228725 C. Phoenix AZ : IEEE Computer So 2 ciety Press , 1999 : 1902199 . 利用到达和服务函数的反函数来计算信元的最 7 林 闯. 计算机网络和计算机系统的性能评价 M . 北京 : 清华 坏情况延迟 ,基于静态优先级调度理论 ,提出了一种大学出版社 ,2001 . Algo rit hm fo r dela y o n ATM la n s ba s e d o n t he st atic p rio rity sc he duling′s 1 2 2 3L IU Wen, GUO Li,ZHANG Li2chen,L I Shu2ping (11Computer Center of Architecture Institute , Guangdong University of Technology , Guangzhou 510643 , China ; 21Computer Institute , Guangdong University of Technology , Guangzhou 510643 , China ; )31Xiangtan Shipyard , Xiantan 411100 , China Ab stract : Using the inverse of the arrival and service functions , the authors obtain a direct algorithm to compute the worst case delay , and based on the classical static priority scheduling theory for hard real2time system , propose a delay computation method with partition algorithm. A firmer commitment is needed from the network , that is , it will always de2 liver all message completely and within specified deadline . The simulation experiments show that the partition algorithm is better than the direct algorithm , and the connections admission probabilities are raised by 10 %. Key wo rd s : delay ; partition algorithm ; static priority
/
本文档为【基于静态优先级的ATM网延迟算法】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索