高级操作系统 Advanced Operating System

Slides:



Advertisements
Similar presentations
社区矫正与和谐社区的建设 —— 以社会工作为切入点 珠勒花 内蒙古农业大学 2014 年 6 月 27 日.
Advertisements

为什么爸爸妈 妈是双眼皮, 我是单眼皮? 为什么为什么? 555…. 1 、举例说出相对性状和基因的关系。 3 、理解近亲结婚的危害。 2 、 能够描述控制相对性状的一对基因的 传递特点。
人的性别遗传 合肥市第四十九中学 丁 艳. 男女成对染色体排序图 1 、男性和女性各 23 对染色体有何异同 ? 哪 一对被称为性染色体 ? 2 、这两幅图中,哪幅 图显示的是男性的染色 体?哪幅图显示的是女 性染色体? 3 、图中哪条染色体是 Y 染色体?它与 X 染色体 在形态上的主要区别是.
融合遗传: 两个亲本杂交后,子代 会表现出介于双亲之间 的性状。 生物体的形态结构和 生理特征叫做性状。 同一种生物的同一种性状的 不同表现类型 。 相对性状:
第 5 章 基因突变及其他变异 第 3 节 人类遗传病 【思考】 感冒是不是遗传病? 先天性疾病、地方性疾病和遗传 病有什么关系?
精彩人生.
第八章 土地行政管理.
抗菌药物合理用药指标 2011年11月24日.
企业会计学(三) 人大版本 吕 昌.
中考冲刺之 ——现代文阅读技巧2.
「鬧鐘媽媽」vs.「教育媽媽」 談管教兒女的方法
1、一般地说,在生物的体细胞中, 和 都是成对存在的。
辨性别 A B. 辨性别 A B 第三节人类染色体与性别决定 昌邑市龙池初中 杨伟红 学习目标 1.理解人的染色体组成和传递规律。 2.解释人类性别决定的原理。 3.通过探究活动,解读数据了解生男生女的比例。
青岛国金财富投资管理股份有限公司 (青岛蓝海股权交易中心推荐机构会员、交易商会员,会员号:1063)
據點考核與評鑑 報告人:臺南市政府 照顧服務管理中心.
特殊族群運動健康訓練(I).
依据教材 全国高等教育自学考试指定教材 《西方行政学说史》, 竺乾威主编,高等教育出版社。
一、平面点集 定义: x、y ---自变量,u ---因变量. 点集 E ---定义域, --- 值域.
學生申訴管道 學生受教權的維護.
抗菌药物临床应用管理规定.
正 信 讀 書 會 主 持 群 : 姚 永 錩 、 鄭 健 、 陳 淑 珍 佛法的生活應用 2008/07/23.
非法集资典型案例评析 南京师范大学法学院 蔡道通 2016年1月.
专题(二) 交往沟通 掌握技能 命 题 解 读 背 景 材 料 新 题 演 练 考 点 链 接 1.
松竹梅岁寒三友 步入建交 桃李杏村暖一家 迈进职教 活出精彩.
职业理想近距离 班级:13302班 14302班 主持人:指定同学主持 时间:12月12日 19日.
第八单元第二课第一课时 严守法律 温州四中 蒋莉青.
初中语文总复习 说明文 阅读专题 西安市第六十七中学 潘敏.
初中语文总复习 说明文 阅读专题.
管理学基本知识.
行政作用法 行政命令.
植物之繁殖方法.
高级财务会计.
默写基础知识: 1、家庭是由 关系、 关系或 关系而结合成的亲属生活组织。家里有 ,家中有 。
钞坑安置区项目简介.
滁州学院首届微课程教学设计竞赛 课程名称:高等数学 主讲人:胡贝贝 数学与金融学院.
什么是颈椎病? 颈椎病是指颈椎间盘退行性变,及其继发性椎间关节退行性变所致脊髓、神经、血管损害而表现的相应症状和体征。
创建广东省现代教育技术 实验学校自查报告 斗门区乾务镇五山中心小学 2012年5月22日.
1.1.2 四 种 命 题.
北京中兴荣投资顾问有限公司简介.
第3节 建筑内部热水供应系统 3.1 分类、组成、供水方式 3.2 加热设备和器材 3.3 热水管道的布置与敷设
色 弱 與 色 盲.
荆门市农业水价综合改革 工作情况汇报 湖北省荆门市水务局 二0一六年九月.
宠物之家 我的宠物性别? 雌(♀) or 雄(♂) 第一阶段:我的宠物我做主 第二阶段:宠物“相亲记” 第三阶段:家族诞生
紧抓PPP项目为招标代理机构 带来的转型发展机遇
孟德尔的豌豆杂交实验(一) 豌豆杂交实验为什么这么成功? 豌豆是自花传粉、闭花受粉植物; 人工异花传粉 有易于区分的性状。
遗传的基本规律 (一)基因的分离规律.
拾貳、 教育行政 一、教育行政的意義 教育行政,可視為國家對教育事務的管理 ,以增進教育效果。 教育行政,乃是一利用有限資源在教育參
92-90數學課程綱要比較 -- 不含數與計算 台北市立師範學院 數學資訊教育系副教授 李源順.
課程銜接 九年一貫暫行綱要( )  九年一貫課程綱要( ) 國立台南大學數學教育系 謝 堅.
2.4 二元一次方程组的应用(1).
運輸與空間的交互作用 運輸發展的階段 一、分散的港口 二、侵入路線 三、發展支線 四、初步相互連結 五、完全相互連結 六、高度優越的幹線
  第七章 压电式传感器.
社會學(一) 空中大學花蓮中心 鍾燕菁
高级操作系统 Advanced Operating System
主要内容: 1.选址问题的概念 2.单点选址模型 3.多点选址模型 4.其他方法概况
第七讲 二维连续分布独立性与二维函数分布 本次课讲授:第二章的 ; 下次课讲第三章的 。
可降阶的高阶方程 一、 型的微分方程 二、不显含未知函数的方程 三、不显含自变量的方程.
浙江大学医学院公共技术平台 实验仪器预约管理系统系列培训 医学院公共技术平台 丁巧灵
第6章 反比例函数 第二节 反比例函数的图象和性质(一).
高级操作系统 Advanced Operating System
高级操作系统 Advanced Operating System
小学5.
18.1 符號檢定 單一樣本符號檢定 : 樣本中大於 的數以正號(+)表示, 而小於 的數以負號(-)表示,
教師專業與權益相關法令 報告人 劉亞平.
本章學習目的 瞭解彈性的意義與衡量 瞭解需求的價格彈性 瞭解供給的價格彈性 瞭解需求的所得彈性 瞭解需求的交叉彈性 瞭解價格彈性的應用
第四节 微分 函 数 的 微 分 微分的定义 微分的几何意义 基本初等函数的微分公式 基本初等函数 的微分公式与 微分的运算法则
第四章 随机变量的数字特征 关键词: 数学期望 方差 协方差、相关系数 其它数字特征.
高级操作系统 Advanced Operating System
統計網路學習館 線性迴歸.
用加減消去法解一元二次聯立方程式 台北縣立中山國中 第二團隊.
Presentation transcript:

高级操作系统 Advanced Operating System 熊焰 yxiong@ustc.edu.cn 0551_3607394 中国科学技术大学计算机系

第三章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 第三章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 虚信道和虚网络 完全自适应和无死锁路由算法 5/7/2019 Advanced Operating System

第三章 分布式路由算法 主要内容( cont'd ) 几个自适应和无死锁路由算法 容错单播的一般方法 网格和圆环中的容错单播算法 超立方中的容错单播算法 容错组播算法 5/7/2019 Advanced Operating System

第三章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 第三章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 5/7/2019 Advanced Operating System

一、进程间通信类型 二、通信延迟及其原因 四、路由函数 三、路由算法类型 5/7/2019 Advanced Operating System

3.1分布式路由算法导论 一、进程间通信类型 有效的进程间通信对分布式系统的性能很重要 根据目标个数的不同,本章讨论的进程间通信 的类型有: 一对一(单播) 一对多(组播) 一对所有(广播) 5/7/2019 Advanced Operating System

3.1分布式路由算法导论: 二、通信延迟及其原因 在基于消息传递的分布式系统中,消息一般在 到达目标节点之前可能要通过一个或多个中间 节点,故存在通信延迟。 分布式系统中的通信延迟依赖于如下四个因素: 网络拓扑、路由、流量控制、交换 5/7/2019 Advanced Operating System

3.1分布式路由算法导论: 二、通信延迟及其原因(cont'd) 1、网络拓扑,也叫互连网络 通常用图表示,定义处理单 元(PE)之间是如何连接的 分类 特殊类型的网络使用 k元n维立方表示 5/7/2019 Advanced Operating System

3.1分布式路由算法导论: 二、通信延迟及其原因(cont'd) 2、路由 决定如何选择路径以便将消息传递到目的地。 本章主要考虑路由 5/7/2019 Advanced Operating System

3.1分布式路由算法导论: 二、通信延迟及其原因(cont'd) 3、流量控制 流量控制决定在消息沿路径传递时如何分配网络资 源 网络资源包括: 信道 缓冲区 5/7/2019 Advanced Operating System

3.1分布式路由算法导论: 二、通信延迟及其原因(cont'd) 4、交换技术 这是一个实际的机制,它决定消息如何从一个输入信 道转到一个输出信道。 5/7/2019 Advanced Operating System

3.1分布式路由算法导论: 三、路由算法类型 路由算法类型包括: 特殊 vs. 一般 最短 vs. 非最短 确定型 vs. 适应型 5/7/2019 Advanced Operating System

3.1分布式路由算法导论: 1、一般型路由和特殊型路由 一般型路由算法 适合于所有类型的网络 但是对于某种特定网络不是很有效 特殊型路由算法 只对特定的网络类型有效,如超立方、网格等 这些算法由于利用了特定网络的拓扑属性,所以效 率往往较高。 5/7/2019 Advanced Operating System

3.1分布式路由算法导论: 2、最短路由算法和非最短路由算法 最短路径算法 对给定的源-目标对,给出一个代价最小的路径 路径的代价 所有跳步(连接)代价的线性和。 缺点:可能会导致网络某一部分的拥塞 非最短路由算法 可以将消息路由到一个更长的路径从而避免拥塞。 在某些情况下,随机路由可能是有效的。 5/7/2019 Advanced Operating System

3.1分布式路由算法导论: 3、确定型路由和适应型路由 确定型路径算法(静态) 路由路径只在网络的拓扑发生改变时才发生变化 而且不使用任何有关网络状态的消息。 适应型路由算法(动态) 路径根据网络流量而改变。 5/7/2019 Advanced Operating System

3.1分布式路由算法导论: 5、容错型路由和非容错型路由 容错型路由算法 即使出现错误,被路由消息也能保证送到。 非容错型路由算法 假定路由不会出错 路由算法不必动态调整自己的活动。 5/7/2019 Advanced Operating System

3.1分布式路由算法导论: 6、冗余型路由和非冗余路由 冗余型路由算法 用几个边分离(或节点分离)的路径向同一个目标 发送多个拷贝。 只要这些路径中的一个是好的,则至少有一个消息 拷贝能到达目标。 必须保证有且只有一个拷贝被接收 非冗余型路由算法 对每个目标只需转发消息的一个拷贝。 5/7/2019 Advanced Operating System

3.1分布式路由算法导论: 7、死锁避免型路由和非死锁避免型路由 3.1分布式路由算法导论: 7、死锁避免型路由和非死锁避免型路由 死锁避免型路由算法 通过仔细设计的路由算法,保证不发生死锁。 非死锁避免型路由算法 没有特别的设施来预防或避免死锁。 可能发生死锁,也可能不发生死锁。 5/7/2019 Advanced Operating System

3.1分布式路由算法导论: 四、路由函数 路由函数定义一个消息如何从源节点路由到目标节点 有许多不同的路由函数的定义,例如 每个PE在收到一个消息以后,都将决定: 1)把这条消息传送到本地存储器,还是 2)转发到一个邻接的PE 有许多不同的路由函数的定义,例如 依赖于目标的、依赖于输入的、依赖于源的、依赖于路径的 等等 一般而言,路由函数参考的信息越多,效果可能就越好 本章仅使用依赖于目标的路由函数 仅仅依赖于当前和目标节点 依赖于当前、目标节点,以及输入的邻接节点 依赖于目标节点和从源节点到当前节点的路径 依赖于源、当前、目标节点 5/7/2019 Advanced Operating System

第三章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 第三章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 5/7/2019 Advanced Operating System

3.2 一般类型网络的最短路径路由算法 许多分组交换网,如法国的Transpac或美国 的ARPAnet都使用最短路径路由 这里介绍三个一般类型网络的最短路径路由 算法: Dijkstra集中式算法 Ford分布式算法 ARPAnet路由算法 5/7/2019 Advanced Operating System

3.2 一般类型网络的最短路径路由算法: 预备、分布式系统图示 一般地,一个分布式系统可以用图来表示: 节点代表PE(处理单元); 边代表通信链接; 每个链接的数字代表链接代价。 例: 5/7/2019 Advanced Operating System

三个一般类型网络的最短路径路由算法: Dijkstra集中式算法 Ford分布式算法 ARPAnet路由算法 5/7/2019 Advanced Operating System

3.2.1 Dijkstra集中式算法 第一种类型的算法以集中式的风格进行路由 需要了解给定网络的全局拓扑消息,即: 1、网络中所有其它节点的列表; 2、节点之间的所有链接; 3、每个链接的代价。 5/7/2019 Advanced Operating System

3.2.1 Dijkstra集中式算法: 一、算法描述 设 D(v)是从源s到节点v的距离(沿给定路径的链接的代价的和) l(v,w)是节点v和w之间的代价 Dijkstra算法如下: 设N={s}; 对不在N中的每一个节点v,令D(v)=l(s,v)。 对那些没有连接到s的节点赋值为∞。 找到不在N中的一个节点w,使D(w)最小并将w加入N; 然后对所有不在N中的其它节点计算并更新D(v): D(v) := min[D(v), D(w)+l(w,v)] 重复步骤2,直到所有节点都在N中 即与s相邻的节点 N N D(w) w s ? 5/7/2019 Advanced Operating System D(v) v

3.2.1 Dijkstra集中式算法: 二、算法举例 上述算法作用于如图所示的网络: 以P5为源节点 1、集合N只包含源节点P5即N= { P5}。 对不在N中的节点P1,P2,P3,P4计算: D(1)=D(2)=∞; (由于P1和P2不与P5直接相连) D(3)=l(P5,P3) =20 D(4)=l(P5,P4)=2 = ∞  =2 = ∞ 5/7/2019 Advanced Operating System =20

3.2.1 Dijkstra集中式算法: 二、算法举例(cont'd) 2、取D(1),D(2),D(3),D(4)中具最小值的对应节点P4加入 到集合N中, N= { P5,P4}, 对不在N中的其它节点P3,P2,P1更新 D(1)=min{D(1),D(4)+l(4,1)} =min{∞,2+∞}=∞, D(2)=min{D(2),D(4)+l(4,2)} =min{∞,2+1}=3, D(3)=min{D(3),D(4)+l(4,3)} =min{20,2+2}=4。   =∞ =3 =2 =∞ 5/7/2019 Advanced Operating System  =20 =4

3.2.1 Dijkstra集中式算法: 二、算法举例(cont'd) 3、取D(1),D(2),D(3)中具最小值的对应节点P2加入到集合N中, N={P5,P4,P2}, 对不在N中的其它节点P3,P1更新 D(1)=min{D(1),D(2)+l(2,1)} =min{∞,3+4}=7 D(3)=min{D(3),D(2)+l(2,3)} =min{4, 3+3}=4。 =3 =2  =∞ =7 5/7/2019 Advanced Operating System  =4

3.2.1 Dijkstra集中式算法: 二、算法举例(cont‘d) 4、取D(1),D(3)中具最小值的对应节点P3加入到集合N中, N= { P5,P4,P2,P3} 对不在N中的其它节点P1更新 D(1)=min{D(1),D(3)+l(3,1)} =min{7,4+5}=7 =3 =2 =7  5/7/2019 Advanced Operating System =4

3.2.1 Dijkstra集中式算法: 二、算法举例(cont'd) 5、取D(1)中具有最小值的对应节点P1加入到集合N中, N= { P5,P4,P2,P3,P1}, 此时,节点都在N中,算法结束。 5/7/2019 Advanced Operating System

3.2.1 Dijkstra集中式算法: 连续的步骤,如下表: 5/7/2019 Advanced Operating System

3.2.2Ford分布式算法 第二种类型的路由算法采用分散式的方法进行 路由 分布式算法 每个节点和其邻节点交换代价和路由信息,直到这 些节点的路由表到达最短路径的要求为止 5/7/2019 Advanced Operating System

3.2.2Ford分布式算法(cont'd) Ford分布式算法也包括两个部分: 一个初始步骤 一个最短距离计算的步骤 这里,最短距离指一个给定节点和目标节点之间的距离 当所有节点都带有 1)一个表示它们到目标节点距离的标记以及 2)沿着最短路径到达目标节点要经过的下一个节 点的标记 时,算法结束。 5/7/2019 Advanced Operating System

3.2.2Ford分布式算法: 一、算法描述 每个节点v,都有(n,D(v))的标记。 初始步骤: 令D(d)=0,将所有其它节点标记为(.,∞) 5/7/2019 Advanced Operating System

3.2.2Ford分布式算法: 一、算法描述(cont'd) 最短距离计算步骤: 对所有节点的最短路径做标记: 对每个节点v≠d: 考虑v的每个邻节点w,根据当前D(w), 计算D(w)+l(w, v),令 D(v):=min{D(v),D(w)+l(w,v)} 更新v的标记:用使上述表达式取值最小的邻 接节点代替n,并用新值代替D(v)。 对每个节点重复上述操作,直到不再有改变 5/7/2019 Advanced Operating System

3.2.2Ford分布式算法: 二、举例 上述算法作用于如图所示的网络: 以P5为目标节点 初始: 令D(5) = 0,将其他节点P1,P2,P3,P4都标记为(.,∞) 5/7/2019 Advanced Operating System

3.2.2Ford分布式算法: 二、举例:第一轮 对于P1, 同理,P2仍标记为(.,∞) 对于P3, 同理,P4标记为(P5, 2)。 邻节点为P2,P3,由当前标记可知P2,P3距离P5都为∞,则P1 不能通过任何节点到达P5,P1仍标记为(.,∞) 同理,P2仍标记为(.,∞) 对于P3, 邻节点为P1,P2,P4,P5,其中 D(1)= D(2)=D(4)=∞,D(5)=0 由于P3到P5的距离20+D(5)为20 小于当前D(3)= ∞, 表明P3经P5有最短路径可达P5 故P3标记为(P5, 20) 同理,P4标记为(P5, 2)。 5/7/2019 Advanced Operating System

3.2.2Ford分布式算法: 二、举例:第二轮 对于P1, 对于P2, 同理,更新P3和P4的标记为 (P4,4),(P5,2) 邻节点为P2,P3,由当前标记可知P5距离P2为∞,距离P3为 20,则P1通过P3有最短路径到达P5,D(1)为P1到P3的距离 与P3到P5的距离之和为5+20=25,故P1标记为(P3,25); 对于P2, 邻节点为P1,P3,P4,计算P2到 Pi (i = 1,3,4)的距离与当前D(i)之 和,并取最小值,可见计算P2到 P4的距离与当前D(4)之和最小为 3,说明P2经P4有最短路径到达 P5,故P2标记更新为(P4,3); 同理,更新P3和P4的标记为 (P4,4),(P5,2) 5/7/2019 Advanced Operating System

3.2.2Ford分布式算法: 二、举例:第三轮 按同样方法更新P1,P2,P3,P4的标记为: (P2,7),(P4,3),(P4,4),(P5,2); 由于此后再重复以上算法试图更新 每一个节点的标记都不会改变其 标记,算法结束。 5/7/2019 Advanced Operating System

3.2.2Ford分布式算法: 举例小结 (P4,3) (.,∞) (P3,25) (.,∞) (P2,7) (.,0) (P5,2) 5/7/2019 Advanced Operating System (P4,4) (.,∞) (P5,20)

3.2.2Ford分布式算法(cont’d) 上例中,所有节点的行为在经过3轮之后都被 同步了 上述同步方法仅仅是为了便于演示 同步方法是指所有节点在每一轮中都更新一次标记 Ford算法也适用于异步系统, 其中每个节点以随机的速率更新其D(v)值。 5/7/2019 Advanced Operating System

3.2.3 ARPAnet路由算法 ARPAnet的路由算法是一个可靠、实用的分布式路由 算法,也是今天流行的Internet 路由算法的前身。 与Ford算法比较相似 不同的是 算法中的节点都维护一个一般化的路由表,以便记录通过不 同邻接节点的最短路径。 这个路由表包含从这个节点到所有其它节点的最优路径的延 迟。 每隔固定的时间间隔,路由表就被传送到它的所有邻接节点, 直到最小延迟表在某一点达到稳定为止。 5/7/2019 Advanced Operating System

3.2.3 ARPAnet路由算法: 举例 P1 11 P3 7 P4 3 举例说明:用ARPAnet 路由算法时,P1,P2, P3,P4的一般路由表,仍 以P5为目标节点 每个表格都包含通过每个 邻居到达P5的最短距离 假设在时刻0前已经达到 了一个稳定点 即网络延迟表如右图 P2 4 P3 6 P5 2 P2 7 P3 9 P1 12 P2 6 P4 4 P5 20 想一想,从每个节点的路由表上,可以看出最短路由的问题么? 5/7/2019 Advanced Operating System

3.2.3 ARPAnet路由算法: 举例(cont'd) 11 P3 7 P4 3 假设0时刻,P4与P5之 间链接失效,则P4更新 其路由延迟表,并传输 给其所有邻节点,从而 使那些节点的路由延迟 表发生变化,直到产生 一个新的稳定点 想一想,新的稳定点可 能是怎样的? P2 4 P3 6 P5 2∞ P2 7 P3 9  P1 12 P2 6 P4 4 P5 20 5/7/2019 Advanced Operating System

3.2.3 ARPAnet路由算法: 举例(cont'd) 11 P3 7 P4 35 P1 11 P3 79 P4 5 P2 4 P3 6 P5 ∞ P2 46 P3 68 P5 ∞ P2 7 P3 9 P2 79 P3 911   P1 12 P2 6 P4 46 P5 20 P1 12 P2 68 P4 6 P5 20 …… 5/7/2019 Advanced Operating System

3.2.3 ARPAnet路由算法: 举例(cont'd) 上述过程一直持续到达到一个新的稳定点,P1,P2,P3,P4分别 用了20,19,17,20个时间间隔,如下图所示。 5/7/2019 Advanced Operating System

3.2.3 ARPAnet路由算法(cont'd) ARPAnet路由算法中 每个节点对所有邻居都发送相同消息,对接收节点 不做任何标识。 这样,某些节点就会接收无用消息。 在链接节点失效时候,这些消息会导致我们不期望的 循环。 例如 5/7/2019 Advanced Operating System

3.2.3 ARPAnet路由算法: 不期望的循环,举例 11 P3 7 P4 3 例如,P4和P5链接失效时, P4的最短路径为4,但是 这个4来自于P2,而P2到 P5的最短路径原来就依赖 于P4与P5的链接,由于P4 使用P2的信息时,P2的信 息尚未得到更新,导致出 现不期望的循环: P4P2P4 P2 4 P3 6 P5 2∞ P2 7 P3 9  P1 12 P2 6 P4 4 P5 20 5/7/2019 Advanced Operating System

3.2.3 ARPAnet路由算法: 不期望循环的消除 循环的消除是在路由消息中包含路径的所有节点,并 把这些消息发给邻居节点。 然而,它的效率较底,因为它的额外开销太大。 Shin和Chou,提出了一个避免循环算法:只需在路由 消息中存储路径中最近的k个节点,k与相应网络中循 环的最大长度有关 5/7/2019 Advanced Operating System

第三章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 第三章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 5/7/2019 Advanced Operating System

3.3特殊类型网络的单播路由算法 一般类型网络的路由算法适用于所有拓扑类型的网络。 但, 每个节点需要维持路由延迟表,而且 效率太低,不适用于特殊类型的网络。 得益于特殊网络的拓扑特性,可以不使用路由延迟表 而构造最短路径路由算法 本节介绍三种特殊网络的单播路由算法: 1、双向环单播路由算法 2、网格和圆环单播路由算法 3、超立方单播路由算法 5/7/2019 Advanced Operating System

3.3.1 双向环单播路由算法 一、双向环单播路由算法 在双向环上进行决定型单播路由非常简单: 消息沿着一个方向被转发:顺时针或者逆时针 由于消息可以沿两个方向发送,所以由源节点根据 目标节点的位置决定发送方向: 如果目标离顺时针方向近,则用顺时针方向; 否则选择逆时针方向。 一个消息通过几个中间节点按照顺时针或逆时针方 向传递,直到到达目标节点。 5/7/2019 Advanced Operating System

3.3.1 双向环单播路由算法 一、双向环单播路由算法( cont'd ) 双向环上的单播路由算法可以使用两条路径: 一条沿着顺时针, 另一条沿着逆时针。 消息 也可以被复制,然后每个方向发一个拷贝; 也可以分成两半,每半转发到一个方向。 5/7/2019 Advanced Operating System

3.3.1 双向环单播路由算法: 二、算法的一般化 双向环是k元1维立方,即只有一个维度。 若维度大于1,如网格和超立方,就用有序维度 路由 每次将每个消息沿一个维度路由 注意: 圆环:在一个维度中的各点以环的方式连接起来,带 有周边连接 网格:一个维度中的各点以线性排列的形式连接起来, 没有周边连接 (x1,y1,…)(x2,y2,…) 5/7/2019 Advanced Operating System

3.3.1 双向环单播路由算法: 二、算法一般化( cont'd ) 环形路由方法可用于在一个维度中对消息进行 路由。 沿着一个线性排列路由是很简单的。 当消息到达每个维度的对等者时,就使用下一个维度。 通过使经过的各个维度保持一个单调的顺序,就可以 保证不会发生死锁。 但这种方法适应性差。 5/7/2019 Advanced Operating System

3.3.2 网格和圆环单播路由算法 网格和圆环是k元2维立方。 类似地,3维网格和圆环是k元3维立方。 本小节介绍 圆环有周边邻接, 网格没有周边连接。 类似地,3维网格和圆环是k元3维立方。 本小节介绍 1、2维网格的XY路由 2、最短且完全适应路由 3、折线路由 4、最大最短路径路由 5/7/2019 Advanced Operating System

3.3.2 网格和圆环单播路由算法: 1、2维网格的XY路由 特别地,若源和目标分别为 (sx,sy)和(dx,dy),则路由消 息将在X维度上走|dx – sx| 步, 然后在Y维度上走|dy– sy|步 5/7/2019 Advanced Operating System

3.3.2 网格和圆环单播路由算法: 2、最短且完全适应路由 在最短且完全适应路由中, 每个中间节点,包括源节点,都要充分利用所有可 行的最短路径。 在2维网格中, 只要dx–sx≠0且dy–sy≠0,每个节点在选择邻居时 总有两个选择。 一个好的适应性路由算法应该能选择任意-个邻居 并能尽可能地保持dx –sx≠0且dy–sy≠0的情况。 显然,XY路由是最不灵活的一个。 5/7/2019 Advanced Operating System

3.3.2 网格和圆环单播路由算法: 适应性路由图示 只要dx–sx≠0且dy–sy≠0, 每个节点在选择邻居时总有 两个选择:X方向或者Y方向 5/7/2019 Advanced Operating System

3.3.2 网格和圆环单播路由算法: 3、折线路由 Badr和Podar提出了一个2维网格的折线路由方法 首先建立一个包含源和目标的矩形. 源s=(sx,sy)和目标d=(dx,dy)分别位于矩形的两个对角 从端点d=(dx,dy)引出一条线L,这条线将平分经过点d的矩形 的两边所组成的角。 消息将沿着直线L 路由,但仍在矩 形内部。 即所有的中间节点都是依照它们到 L的距离来选择的——在所有合格 的节点中,总是选择距离L 最近的 一个。 直线L 5/7/2019 Advanced Operating System

3.3.2 网格和圆环单播路由算法: 折线路由( cont'd ) 在2维圆环中,折线路由可能不是最优的,因为 一个中间节点可能有多于两个的合格邻居。 5/7/2019 Advanced Operating System

3.3.2 网格和圆环单播路由算法 4、最大最短路径(MP)路由 对于最优解,Wu在k元M维立方的最短路径路 由算法的基础上提出了一个最大最短路径(MP) 路由算法: 路由消息总是被转发到与目标节点存在最大个数的 最短路径(但并不一定是点分离的路径)的那个邻 居节点。 基于最大最短路径的路由算法是一个对2维网 格和M维立方都是最优的路由算法。 然而,关于最大最短路径对2维圆环是不是最 优的仍然是一个未决的问题。 5/7/2019 Advanced Operating System

3.3.2 网格和圆环单播路由算法 关于边(点)分离路经 若源和目标都有四个邻居, 那么很容易在它们之间建立 四个边(或点)分离的路径。 一般地,设k(k≤4)是源和目 标节点所具有的最小的邻居 的数目,那么,在源和目标 之间就存在k个边〔点〕分离 的路径。 5/7/2019 Advanced Operating System

3.3.3 超立方单播路由算法 对超立方的单播路由可采用一种相对简单的 方法,不必在每个节点中存储路由延迟表。 一个n维超立方(n-cube)可定义为: Q0,是一个只有一个节点的退化图 Qn=K2xQn-1,这里: K2是具有两个节点的完全图; x是两个图的笛卡尔乘积。 Qn中的一个节点的地址可以表示为 u=unun-1…u1(ui=0或1,1≤i≤n) 对于两个n-1维立方, 在对应的点之间连线 5/7/2019 Advanced Operating System

3.3.3 超立方单播路由算法: 一、海明距离 两个节点u=unun-1…u1和w=wnwn-1…w1间最短路径长 度就是u和w间的海明距离,表示为H(u,w)。 u和w间的异或操作u⊕w=rn rn-1 …. r1定义为: 如果ui=wi,则ri=0; 如果ui≠wi,则ri=1,1≤i≤n。 显然,H(u,w)等于u⊕w中1的个数。 u(i)表示改变u的第i位(也叫维).例如1101(3)=1001。 u=unun-1…u1 w=wnwn-1…w1 5/7/2019 Advanced Operating System

3.3.3 超立方单播路由算法: 二、超立方路由 在超立方路由中, 当前节点u和目标节点w的相对地址为u⊕w,它和 将要发送到下一个节点(也叫转发节点)的消息一起 传送。 在每个跳步,相对距离都会通过将相对地址中的一 个1替换而进行更新。 5/7/2019 Advanced Operating System

3.3.3 超立方单播路由算法: 二、超立方路由( cont'd ) 在下面的算法中,节点u是当前节点(可以是源节点), 节点w是目标节点。 一个节点,或者开始一次路由, 或者收到一个消息 根据相对地址, 选中存在差异的那一维 将消息发送给这个维度上对等的节点 发送给本节点的? 根据相对地址, 选中存在差异的那一维 将消息发送给这个维度上对等的节点 5/7/2019 Advanced Operating System

3.3.3 超立方单播路由算法: 二、超立方路由( cont'd ) 在上述算法中,i的选择是随机的, 这意味着可能有不止一条最短路径。 实际上,最短边分离的个数等于源节点和目标 节点的海明距离。 如果遵循一个预定的顺序,这种算法就是决定 性的,叫做e立方路由。 例如,维的顺序遵循升序:首先是1维,然后2维, 等等。n维在最后; 5/7/2019 Advanced Operating System

3.3.3 超立方单播路由算法: 三、一个3维立方路由的例子 例中:源节点u=000目标节点w=110。 从点000到点110有下列三个点分离路径: 路径1(红色):000100110 路径2(蓝色):000010110 路径3(绿色):000001011111110 最短 5/7/2019 Advanced Operating System

3.3.3 超立方单播路由算法: 四、超立方多路径路由的性质 超立方多路径路由具有如下性质: 若两个节点u和w在n维立方中的海明距离是k. 则,在u和w之间就有n个点分离路径。 在这n条路径中,有k个路径长度为k, 其余n-k个路径长度为k+2。 例如上一页中, 000和110之间的距离|000⊕110|=2。 因此,上述路径中有两条长度为2,一条长度4 5/7/2019 Advanced Operating System

3.3.3 超立方单播路由算法: 四、超立方多路径路由的性质 类似地.000和100之间的三条点分离路径为: 路径1(红色):000100 路径2(绿色):000001101100 路径3(蓝色):000010110100 000和100之间的海明距离 |000⊕100|=1 5/7/2019 Advanced Operating System

第三章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 第三章 分布式路由算法 主要内容 分布式路由算法导论 一般类型网络的最短路径路由算法 特殊类型网络的单播算法 特殊类型网络中的多播算法 5/7/2019 Advanced Operating System

3.4特殊类型网络的多播路由算法 多播(一到多)是指从一个源向任意多个目标 节点传送同样的消息。 多播在数据并行编程操作中有一些应用,例如 单播和广播都是多播的特例。 多播在数据并行编程操作中有一些应用,例如 复制,障碍同步, 对共享存储器失效以及分布式共享内存系统更新的 支持等。 5/7/2019 Advanced Operating System

3.4.1 一般的多播路由算法 两个主要的多播路由参数是通信量和时间。 通信量是以将消息发送到所有的目标所需的通信链 接的数目来衡量的。 时间就是消息传送的时间。 当两个多播路由算法有相同的时间步数时,应 该选择具有较小的通信量步数的那一个。 通信量可以通过不同的目标共享链接来降低。 5/7/2019 Advanced Operating System

3.4.1 一般的多播路由算法: 一、多播优化问题 通常,多播存在下列四个优化问题: 一个最优的多播路径是一个包括所有目标的 最短路径。 1、多播路径优化问题 一个最优的多播路径是一个包括所有目标的 最短路径。 2、多播回路优化问题 最优多播回路是包含所有目标的最短长度的 回路。 5/7/2019 Advanced Operating System

3.4.1 一般的多播路由算法: 一、多播优化问题( cont'd ) 3、steiner树优化问题 一个包含所有目标节点的给定拓扑的一个子树 最小steiner树具有最小的总长度 注意:不一定每个通向目标的路径长度都是最短的。 4、多播树优化问题 一个包含所有目标的给定拓扑的子树,且树中每个通向 目标的路径的长度对于给定的拓扑是最小的。 一个最优的多播树具有最小的通信量 5/7/2019 Advanced Operating System

3.4.1 一般的多播路由算法: 一、多播优化问题( cont'd) 不幸的是,对网格和超立方的多播优化问题都 是NP完全问题。 一般使用启发式多播算法。 目前已有人给出了在使用分割-通过路由技术(如虫 孔路由)的网络中进行最优化多播通信的充分条件 本节考虑两种算法: 一是基于路径的; 二是基于树的。 5/7/2019 Advanced Operating System

3.4.2基于路径的多播路由算法 一、基本思想: 首先建立一个哈密尔顿回路, 然后根据这个回路把多播集合转发出去。 如果有一个邻居位于目标前面,但距离目标更近, 那么就可以抄近路。 1895年,爱尔兰数学家哈密尔顿首先提出“环球周游”问题。他用一个正十二面体的 20个顶点代表世界上20个城市,要求旅游者能否找到沿着正十二面体的 棱,从某 一个顶点(即城市)出发,经过每一个顶点(即每一座城市)恰好一次,然后回到 出发顶点? 这便是著名的哈密尔顿问题。它的解称为哈密尔顿回路。 5/7/2019 Advanced Operating System

3.4.2基于路径的多播路由算法: 二、主要步骤 在给定的网格或超立方上建立哈密尔顿回路; 将哈密尔顿回路上的节点排序。 对每个中间节点, 这个顺序起始于源节点,并包括所有目标节点。 这样哈密尔顿回路就被分割成了哈密尔顿路径; 对每个中间节点, 若它是一个目标节点, 保留消息的一个拷贝,删除该目标节点的地址。 将消息和目标列表传给一个邻居。 这个邻居必须在当前节点之前(按顺序),离下一个目标最近,且 仍在这个目标之前(或就是这个目标)。 考虑抄近路 5/7/2019 Advanced Operating System

3.4.2基于路径的多播路由算法: 三、哈密尔顿路径 若使用双向链接,则只需一个哈密尔顿路径 (而不是哈密尔顿回路)即可。 哈密尔顿路径为系统(n×n的网格)中的所有 节点定义了一个顺序。 在整个顺序中,每个节点(x,y)都被赋予一个数字r: 自上而下排序 自下而上排序 x代表第x行; y代表第y列 5/7/2019 Advanced Operating System

3.4.2基于路径的多播路由算法: 四、哈密尔顿路径举例 例如,一个4X4的网格上每个节点具有的r值如图 所示: n=4 若y是偶数,r值沿X方向递增 r(x,y)=yn+x 若y是奇数,r值沿X方向递减 r(x,y)=yn+n-x-1 =yn+(n-1)-x 5/7/2019 Advanced Operating System

3.4.2基于路径的多播路由算法: 五、哈密尔顿路径定义 两个节点在路径中相邻当且仅当|r(v)-r(u)|=1 例如: 4X4网格中,使用粗线连接两个相邻节点 5/7/2019 Advanced Operating System

3.4.2基于路径的多播路由算法: 六、低信道网络和高信道网络 使用顺序定义,整个网格可以分成两个子网: 一个包括从低序节点到高序节点的链接; 另一个包括从高序节点到低序节点的链接。 在两个子网中,除了哈密尔顿路径上的链接以外, 其它链接也包含在其中。 向高序走 向低序走 5/7/2019 Advanced Operating System

3.4.2基于路径的多播路由算法: 七、最短路径路由函数 目标依据它们与源的相对位置也分为两个子集。 一个子集将沿着高信道网络传送, 另外一个将沿着低信道网络传送。 为了将消息沿着最短路径传送,定义如下路由函数。 假定使用高信道网络。 v和d(r(v)<r(d))分别是中间节点和目标节点。 若d是v的一个邻居,那么消息将直接转发到d; 否则,选择一个满足下式的v的邻居u: 向高序走 5/7/2019 Advanced Operating System

3.4.2基于路径的多播路由算法: 举例 下图显示了一个在4X4网格中进行多播的例子 哈密尔顿路径连接了那些r值依次递增的节点 假定节点6(地址为(1,1))为源节点,目标节点为0、2、 10、13和14。 紫色:源节点; 蓝色:目标节点 5/7/2019 Advanced Operating System

3.4.2基于路径的多播路由算法: 举例( cont'd ) 显然,转发消息到节点0和2时,应该使用低信道网络。 依据路由函数,可以得到如下路径: 同样,转发消息到节点10,13和14时应使用高信道网络 红色:低信道网络路径和 具有最小r值的邻居 深紫色:高信道网络路径和 具有最大r值的邻居 5/7/2019 Advanced Operating System

3.4.3基于树的多播路由算法 Lan的贪婪多播算法可以应用于超立方。在这 个算法中, 每个节点(包括源节点)在收到包含目标节点地址列 表的消息后,就把自己的地址和目标节点的地址相 比较。 若发现匹配,消息的一个拷贝将被送往本地的处理器 若多播集合非空,当前节点将决定把目标列表中的地址 转发到哪些邻居。 即,本节点是目标节点之一 还剩其他目标节点要发 5/7/2019 Advanced Operating System

3.4.3基于树的多播路由算法: 一、根据维度顺序进行转发 维度顺序由目标节点的相对二进制地址来决定 n位地址的每一位都有一个计数器。 计数器的内容代表相应维度的(差异统计)信息。 具有最大计数值的那一维将被选中。 所有在这位为1的目标将被转发到这一维上的那个邻居 在剩余的目标中,将利用下一个被选中的维度重复上述 步骤。 当剩余的多播集合为空时,这一过程就结束。 5/7/2019 Advanced Operating System

3.4.3基于树的多播路由算法: 二、4维立方中的多播例子 考虑一个4维立方体(目标用蓝色节点代表) 节点0010(紫色)打算向组播集(蓝色) {0000,0001,1001,1100,1110} 中的每个节点发送消息 所有目标节点的实际地址和源节点0010 的实际地址做异或操作,得到 多播集合的相对地址 {0010,0011,1011, 1110,1100}。 每一列的1的数目组成 了一个称为列总和的 向量(3, 2, 4, 2) 5/7/2019 Advanced Operating System

3.4.3基于树的多播路由算法: 二、4维立方中多播例子( cont'd ) 沿着第2维的邻居拥有最受欢迎4的维度。即节点 0000成为下一个转发节点,发往节点0000的消息 包含子集(0000,0001,1001,1100)。 只有节点1110被剩下了,这个节点可以通过第3维 的邻居转发,也可以通过第4维的邻居转发。 上述过程将在每个转发节点重复操作。 每个多播树的分支都将继续到剩余的 多播集合变空为止 5/7/2019 Advanced Operating System

3.4.3基于树的多播路由算法: 三、基于递归倍增的启发式算法 当使用分割-通过网络时,可以使用递归倍增 方法构造启发式算法。 以单端口模型下的2维网格为例来说明 McKinIey等人提出的u-网格算法。 先为2维网格的节点地址定义一个字典序(<t),即 若x1<tx2或者x1=x2,但y1<ty2,则有(x1,y1)<(x2,y2)。 边分离性质: 假定P(n1,n2)是n1和n2间最短路径,易知, 若n1<tn2<tn3<tn4,则P(n1,n2)和P(n3,n4)边分离 5/7/2019 Advanced Operating System

3.4.3基于树的多播路由算法: 三、基于递归倍增的启发式算法 利用边分离性质,可建立下面避免竞争且具有最少步 数的多播算法 假定源节点是(0,0),按照字典顺序重新排列目标节点、 并将源节点放在前面。 将列表分成两个相等的子列表。源节点将多播消息发往第 二个子列表的第一个节点。 重复上述分割步骤直到每个子列表中只有一个节点; 若源节点不是(0,0),可重新定义排列顺序以便源节点成 为第一个节点 5/7/2019 Advanced Operating System

3.4.3基于树的多播路由算法: 四、举例 考虑一个4×4网格,(0,0)是源节点, (1,0),(1,1),(1,2),(1,3),(2,0),(2,1)和(3,2)是目标 节点。 源节点和目标节点的字典顺序是: (0,0),(1,0),(1,1),(1,2),(1,3),(2,0),(2,1)和 (3,2) 5/7/2019 Advanced Operating System

3.4.3基于树的多播路由算法: 四、举例( cont'd ) 第一步,这个列表被分成两个子列表 {(0,0),(1,0),(1,1),(1,2)}和 {(1,3),(2,0),(2,1),(3,2)} 源(0,0)将信息发送到第二个子列表的第一个节点(1,3) 使用XY路由建立(0,0)到(1,3)的路由路径 5/7/2019 Advanced Operating System

3.4.3基于树的多播路由算法: 举例( cont'd ) 在每个子列表上重复上述 过程,有: 5/7/2019 Advanced Operating System

本课小结 本课主要内容(4小节) 分布式路由算法导论 一般类型网络的最短路径路由算法 进程间通信类型 通信延迟及其原因 路由算法分类 路由函数定义 一般类型网络的最短路径路由算法 Dijkstra集中式算法 Ford分布式算法 ARPAnet的路由算法 5/7/2019 Advanced Operating System

特殊类型网络的单播算法 特殊类型网络中的多播算法 双向环上的单播算法及其一般化 网格和圆环上的单播算法 超立方 基于(哈密尔顿)路径 2维网格的XY路由、适应性路由、折线路由等 超立方 基于海明距离的一种简单的路由算法 特殊类型网络中的多播算法 基于(哈密尔顿)路径 基于树的多播 应用于超立方的Lan的贪婪多播算法 U-网格算法 5/7/2019 Advanced Operating System