PPT《高级操作系统Advanced Operating System》

高级操作系统Advanced Operating System 陈香兰(代)xlanchen@ustc.

edu.cn0551_3606864-83中国科学技术大学计算机系

第四章 分布式路由算法 分布式路由算法导论一般类型网络的最短路径路由算法 特殊类型网络的单播算法特殊类型网络中的多播算法虚信道和虚网络 完全自适应和无死锁路由算法几个自适应和无死锁路由算法 容错单播的一般方法 网格和圆环中的容错单播算法超立方中的容错单播算法容错组播算法 上次课主要内容(4小节) 4.1 分布式路由算法导论进程间通信类型通信延迟及其原因路由算法分类路由函数定义4.2 一般类型网络的最短路径路由算法Dijkstra集中式算法Ford分布式算法ARPAnet的路由算法 4.3 特殊类型网络的单播算法双向环上的单播算法及其一般化网格和圆环上的单播算法2维网格的XY路由、适应性路由、折线路由等超立方基于海明距离的一种简单的路由算法4.4 特殊类型网络中的多播算法基于(哈密尔顿)路径基于树的多播应用于超立方的Lan的贪婪多播算法U-网格算法 4.5 虚信道和虚网络 网络资源在存储转发交换中,资源是缓冲区;

在虫孔路由中,资源是信道.网络通信中,若消息在占有资源的前提下可以申请资源,就有可能发生死锁通过控制路由的自适应性可以预防和避免死锁,同时也保证一定的容错性. 虚信道和虚网络经常用于实现无死锁、自适应和(或)容错的路由. 4.5 虚信道和虚网络通过网络分区避免死锁 通过网络分区可以避免死锁给定的网络可以分成几个子网.根据源和目标的位置,消息被路由到不同的子网举例说明:3X3网格的适应性双Y信道路由如图:在Y方向有两个物理信道(双向) (a)一个3X3网格的 双Y信道网 4.5 虚信道和虚网络通过网络分区避免死锁(cont'

d) 上述网格被分成正、负两个子网(如下图)如果目标位于源的右侧,则使用正网;

否则将使用负网.当源和目标同列时,两个子网都不用.由于两个子网中都没有回路,所以可避免死锁. (b)正网络 (c)负网络 4.5虚信道和虚网络虚信道 若网络没有双Y信道,则可用几个虚信道复用一个物理信道每个虚信道都有自己的缓冲区.当物理信道被其它虚信道使用时,就用这个缓冲区保存消息若虚信道间没有循环等待,就可避免死锁.假设上例改为单Y信道网,那么原来的正、负子网中所有的Y信道都是虚信道. 4.5虚信道和虚网络虚信道(cont'

d) 当两个虚信道共享一个物理信道时,信道利用率大幅提高.虽然虚信道提供了一个具有多重信道的网络,但仍需仔细设计路由算法.例如,可以按照信道标记的升序使用虚信道,以便避免虚信道间循环依赖. 4.5虚信道和虚网络虚网络 比虚信道更高一级的虚拟化是虚网络一个给定的物理网络被分成几个虚网络,每个虚网络包括一系列的虚信道.虚网络中相邻的节点被映射到物理网络中时也要相邻一般地,一个虚网络中的虚信道设置应避免信道间的回路.虽然仍有可能存在互相交叉的虚网络回路,但可以通过使虚网络遵循全序或偏序来避回路前面那个例子中,若使用单Y信道,则前面的正、负子网可认为是两个虚网络.显然每个网络中都没有回路.因每个路由过程最多只使用一个虚网络,所以不会产生互相交叉的虚网络回路. 4.5虚信道和虚网络 虽然虚网络包含虚信道,二者是完全不同的概念.一般地,虚信道的使用是与路由过程紧密相连的,包括源和目标的位置.必须合理安排虚信道,以避免死锁.虚网络通常设计为没有回路,因而路由算法可以不必考虑死锁,除非存在交叉虚网络的依赖性 4.5虚信道和虚网络虚信道举例 考虑一个有四个节点的单向环.如果同时有几个路由进程启动,就会发生死锁. 4.5虚信道和虚网络虚信道举例(cont'