哈尔滨工业大学计算机科学与技术学院
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院
第 6章系统的互联和千兆位网络
??1 互连网络基础
??2 静态连接网络
??3 动态连接网络
??4 消息传递机制
??5 千兆位网络技术
??6 ATM交换器和网络
哈尔滨工业大学计算机科学与技术学院
?4 消息传递机制
? 主要研究,
? 存储转发；
? 虫蚀寻径方法；
? 它们的通信时延问题；
? 针对无死锁的消息寻径确定的寻
径算法和自适应两种寻径算法。
哈尔滨工业大学计算机科学与技术学院
? 一,消息寻径方式
? 1.消息的格式
（ 1）消息 (message)
? 是结点间通信的逻辑单位，它常常由任意数
目的长度固定的包组成，因此它的长度是可
变的。
? 在消息传递网络中通信的信息单位是：消
息、包和片的格式。
? 消息寻径中的信息单位如下图所示。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
（ 2）包 (packet)
? 是含寻径目的地址的基本单位；
? 每个包需要一个序号；
? 不同的包可能异步地到达目的结点，
以便把传送的消息重新装配起来。
? 在采用 存储转发寻径方式 的多计算
机系统中，包是信息传送的最小单
位。
哈尔滨工业大学计算机科学与技术学院
? 包的长度取决于寻径方式和网络的实
现方法。
? 典型的包长度为 64--512位。序号可
能占用 1--2个片，取决于消息的长度。
? 包和片的大小还与通道频宽、寻径器
设计以及网络流量密度等有关。
哈尔滨工业大学计算机科学与技术学院
?（ 3）片,
?包可分成一些固定长度的数据片。
寻径信息 (目的地址 )和序号形成头
片，其余的片是数据。
?在采用虫蚀寻径网络的多计算机中，
包可进一步分成片。
?片的长度往往受网络大小的影响，
256个结点的网络需要片长为 8位。
哈尔滨工业大学计算机科学与技术学院
?2.存储转发寻径
? 定义：下图说明了这一概念。
? 在存储转发网络中包是信息流的基
本单位。
? 存储转发网络的时延与源和目的之
间的距离 (段数 )成正比。
? 第一代多计算机系统采用这种寻径
方式。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?3.虫蚀寻径
? 新型的计算机系统都采用虫蚀寻径
方式，把包进一步分成更小的片；
? 与结点相连的硬件寻径器中有片缓
冲区。消息从源结点传送到目的结
点要经过一系列寻径器。
? 同一个包中所有的片，象 不可分离
的同伴一样以流水方式顺序地传送。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 特点,
? 所有数据片必须跟着头片。不同的包
可交替地传送，但不同包的片不能交
叉。否则它们可能被送到错误的目的
地。
? 虫蚀寻径的时延几乎与源和目的之间
的距离无关。
哈尔滨工业大学计算机科学与技术学院
? 4.异步流水
? 采用如下图所示的握手协议，可以实现一
个包内相继片的异步流水运行。
? 异步流水的效率很高，所用的时钟比同步
流水的时钟快，如果路径中的片、缓冲片
或后继通道在某个周期不能使用的话，则
流水线将出现阻塞。
? 如果出现这种情况，则包可能要缓冲、阻
塞、延缓或绕道通过。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?5,时延分析
?下图是包通过存储转发网络和虫
蚀网络的时间比较情况
?其中,
?L是包的长度 (位 )
?W是通道频宽 (位／秒 )
?D是距离 (经过的结点数 -1)
?F是片的长度 (位 )
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 存储寻径网络的通信时延 TSF可表示
为,
?TSF＝ L／ W × (D+1)
? 虫蚀寻径 TWH,
TWH ＝ L／ W+F／ W× D
? 显然,
?TSF与 D成正比；
?如果 L,F，那么 TWH= L／ W，距离 D
对寻径延时的影响可忽略不计。
哈尔滨工业大学计算机科学与技术学院
? 典型的 TSF值约在 2000至 6000?s之间，
而典型的 TWH值只有 5?s或者更小。
? 存储转发寻径往往由软件控制，而
虫蚀寻径则完全用硬件寻径器以流
水方式工作 。
哈尔滨工业大学计算机科学与技术学院
? 二、死锁和虚拟通道
?1.虚拟通道
? 虚拟通道是两个结点间的逻辑链，
它由源结点的片缓冲区、结点间的
物理通道以及接收结点的片缓冲区
组成。
? 下图说明了四条虚拟通道共享一条
物理通道的概念。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?通道的特点,
? 两个端点增加了缓冲区和用来控制虚拟通
道状态的 R／ A线。实现虚拟通道需要用交
叉开关控制、多路选择器和多路分配器。
? 物理通道由所有的虚拟通道分时地共享。
以片传递为基础的分时方法可使一组虚拟
通道共享一条物理通道。
? 用某些通道状态 (如 R／ A信号 )来表示不同
的虚拟通道，控制源缓冲区存放等待使用
通道片。
? 通道 (电缆或光纤 )是它们之间的通信媒介
哈尔滨工业大学计算机科学与技术学院
? 例题 通道上的循环等待引起的死锁
? 如下图所示，有两类死锁是由缓冲
区或通道上的循环等待引起的。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 如下图采用虫蚀寻径的网格形网络中，
四条消息沿四个通道同时传送也会产
生通道死锁 (channel dead lock)
? 4个消息的 4个片同时占用了 4个通道。
如果循环中没有一个通道被释放，死
锁状态将持续下去
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?2.死锁的避免
? 通过增加两条虚拟通道 V3和 V4，可以
打破死锁循环。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 双向通道与单项通道的实现比较
? 虚拟通道可以用单向通道或者双向通道实现。
把两条单向通道组合可以构成一条双向通道；
? 双向通道中的仲裁要复杂一点。
? 单向通道相比较，双向通道由于要做方向仲裁，
因而增加了延迟，又由于控制复杂，因而还增
加了成本。
? 网络的流量不大时，双向通道效率比较高。
? 确定虚拟通道数目时，需要对网络吞吐量和通
信时延折衷考虑。实现数目很大的虚拟通道需
要用高速的多路选择开关。
哈尔滨工业大学计算机科学与技术学院
? 三、流控制策略
?1.问题的提出,
? 当两个或更多的包在某个结点为竞争
缓冲区或通道资源而发生冲突时，必
须确定如何解决冲突的策略。
?针对一对一通信寻径算法和自适应
寻径算法进行讨论。
哈尔滨工业大学计算机科学与技术学院
?2.包冲突的解决
?必须具备三个条件,
?(1)源缓冲区已存有该片；
?(2)通道已分配好；
?(3)接收缓冲区准备接收该片
哈尔滨工业大学计算机科学与技术学院
? 另外还存在,
? 当两个包到达同一个结点时，它们可
能会请求用同一个接收缓冲区或者要
用同一个输出通道，因此必须对两个
问题做出仲裁,
?(1)把通道分配给哪个包?
?(2)没有分配到通道的包做什么事?
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?3.两个包争用的解决方法,
? 提出了一种虚拟直通寻径缓冲方法。
? 虚拟直通方法是存储转发和虫蚀两种寻径方法
的折衷。当不发生冲突时，就如同虫蚀寻径方
法一样工作。
? 最坏情况下，效果与存储转发寻径方法相同。
? 虫蚀寻径在出现冲突时就采用阻塞策略。
? 第 2个包被阻塞不再前进，但并没有被扬弃。
? 某些多计算机网络综合了以上某些流控制策略
的优点，采用混合策略。
哈尔滨工业大学计算机科学与技术学院
?4,维序寻径
? 包寻径可以归结为确定和自适应两类。
? 确定寻径
? 通信路径完全由源和目的地址确定。
? 维序寻径
? 需要一种按照多维网络维序的特定顺序来选
择后继通道。在二维网格网络中称为 X— Y寻
径，首先沿着 X维方向确定路径，然后沿着 Y
维方向选择路径。
? 代表是 E立方体寻径 (E— cube routing)方
法
哈尔滨工业大学计算机科学与技术学院
? 超立方体网络的 E立方体寻径
? 假设有一 N＝ 2n个结点的 n方体。每个
结点的二进制编码为,
?b＝ bn-1bn-2… b1b0。
?源结点为 s＝ sn-1ssn-2… s1s0
?目的结点 d＝ d n-1s d n-2… d1 d0
?要确定一条从 s到 d的步数最小的路
径。
哈尔滨工业大学计算机科学与技术学院
? 将 n维表示成 i＝ 1,2,… n，其中第 i
维对应于结点地址中的第 i-1位。设
v=vn-1vn-2… v1v0是路径中的任一结点。
路径可以根据以下方法唯一地确定。
? ① 计算方向位 ri＝ si-1?di-1,
? 其中 i＝ 1,2,…, n。使 i＝ 1,
?v＝ s，开始以下步骤。
哈尔滨工业大学计算机科学与技术学院
? ② 如果 ri=1，则从当前结点 v寻径到下
一结点,v?2i-1。如果 ri=0则跳过这步；
? ③ i?i+1。如果 i≤n,则转第 2步，否
则退出。
哈尔滨工业大学计算机科学与技术学院
? 例题 4维超立方体网络的正方体寻径
? n＝ 4,s＝ 0110,d＝ 1101,
? 因而 r＝ r4r3r2r1＝ 1011。
? 由于 r1＝ 0?1＝ 1，因此 s就寻径到 s ? 20＝
0111。
? 由于 r2＝ 1?0＝ 1，因此 v＝ 0111就寻径到 v
? 21＝ 0101。
? 由于 r3＝ 1 ? 1＝ 0，因此就可以跳过维 i＝ 3
这一步。
? 由于 r4＝ 1，因此 v＝ 0101就寻径到 v?23＝
1101＝ d。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 5.二维网格网络的 X-Y寻径
? X-Y寻径共有四种模式。
? 东 — 北、东 — 南、西 — 北和西 — 南的路
径方向
? 假定从任意源结点 s＝ (x1,y1)到任意目
的结点 d＝ (x2,y2);
? 寻径从 s开始，首先沿 x方向前进一直
到 d所在的第 y2列为止，然后沿 y方向
前进直到 d。
哈尔滨工业大学计算机科学与技术学院
? 例题：二维网格连接多计算机的 X— Y寻径
? 下图中有 4个 (源，目的 )对，可用以说明二
维网格的 4种寻径模式。
? 从结点 (2,1)到结点 (7,6)需要一条东 —
北路径。
? 从结点 (0,7)到结点 (4,2)要建立一条
东 — 南路径。
? 从结点 (5,4)到结点 (2,0)需要一条西 —
南路径。
? 从结点 (6,3)到结点 (1,5)需要一条西 —
北方向路径。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?6.自适应寻径
?采用自适应寻径的主要目的是避
免死锁。虚拟通道的概念使实现
自适应寻径更经济和更灵活。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 例题 使用虚拟通道的自适应 X-Y寻径
? 这是一个用 X— Y寻径的网格网络示例，
在 Y维上用了 2对虚拟通道。
哈尔滨工业大学计算机科学与技术学院
? 四、选播寻径算法
?1.通信模式
? 多计算机网络中可能会出现四类通
信模式
? 一个源结点和一个目的结点的一对
一的单播 (Unicast)模式
哈尔滨工业大学计算机科学与技术学院
? 选播 (Multicast)模式,
? 对应于一到多的通信情况，即一个源结
点发送同一个消息到多个目的结点。
? 广播 (Broadcast)模式,
? 对应于一到全体的通信情况。
? 会议 (Conference)模式
? 是多到多的通信。
? 实现这些多目的模式必须使用特殊的
硬件或寻径方法。
哈尔滨工业大学计算机科学与技术学院
? 2.寻径效率
? 常用的两个参数是通道流量和通信时延。
? 通道流量：任何时刻的传输有关消息所使
用的通道数来表示。
? 通信时延：包的最长传输时间来表示。
? 优化的寻径网络应能以最小流量和最小时
延实现有关通信模式。
? 在存储转发网络中时延是最重要的问题；
? 在虫蚀寻径网络中流量对效率的影响更大。
哈尔滨工业大学计算机科学与技术学院
? 例题 网格连接计算机中的选播和广
播
? 下图是在 3X3网格上实现的选播寻径。
? 源结点用 S表示，传送一个包到标号为 n的
s个目的结点。这里,i＝ 1,2,…, 5。
? 目的为 5个的选播可以用 5次单播来实现，
如下图所示。
? X-Y寻径的流量需要用 1+3+4+3+2=13条通
道，到 D3的路径最长，所以时延是 4。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?例题 超立方体计算机上选播和
广播
?为在 n方体上实现广播，可用类
似的生成树时延不超过 n就能到
达所有结点。
?下图是一个根结点为 0000的 4-立
方体。超立方体广播树的流量最
小。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 可以得到一棵贪婪选播树，可从结点
0101发送包到 7个目的结点。这个贪
婪选播算法的基本思想是向那些可达
最多剩余目的结点的维方向发送包。
? 从源结点 S＝ 0101开始，由维 2方向可
以到达 2个目的结点，由维 4方向可以
到达 5个目的结点。
哈尔滨工业大学计算机科学与技术学院
? 第一层所用的通道是 0101?0111和 0101
? 1101。从结点 1101，由维 2方向可以
到达 3个目的结点，由维 1方向可以到达 4
个目的结点。
? 第二层所用的通道是 1101 ? 1111，
1101 ? 1100和 0111 ? 0110。
? 第三层所用的通道是 1111 ? 1110，
1111 ? 1011,1100-1000和 0110-0010。
? 第四层所用的通道是 1110 ? 1010。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 所生成的树不是唯一的
? 在扩充选播树时，首先应该比较所有各维方向的可
达性 (reachability)，然后选择某些维使剩余目的
结点的集合最小。
? 两维之间有连线，那么选择其中任何一维都可以。
? 已经证明贪婪选播算法所需的通道数与多次单
播或广播树相比要少。在虫蚀寻径网络中，实
现选播操作时，每个结点的寻径器应有复制片
缓冲区中数据的能力。
? 为了与选播树或广播树的增长同步，树中同一
层的所有输出通道必须在传输向前推进一层之
前处于就绪状态，否则中间结点需要增加缓冲
区。
哈尔滨工业大学计算机科学与技术学院
?3,虚拟通道
? 如图所示。
? 这些虚拟通道可以用来生成 4个虚拟
网络。
? 西 — 北方向通信应该使用图所示的虚
拟网络。
? 类似地，其它方向的通信可以构造另
外三个虚拟网络。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 网络划分
? 虚拟网络概念可将某一给定的物理网络划
分成几个逻辑子网供选播通信使用。
? 例如,
? 假设源结点 (4,2)要传送消息给 6X8网格
中的一个子网。这个 6X8网格已划分成 4个
逻辑子网。所有向东和向北方向的通信都
使用右上角子网。同样，在网格的剩余几
个部位可以构造其它三个子网。
哈尔滨工业大学计算机科学与技术学院
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院
第 6章系统的互联和千兆位网络
??1 互连网络基础
??2 静态连接网络
??3 动态连接网络
??4 消息传递机制
??5 千兆位网络技术
??6 ATM交换器和网络
哈尔滨工业大学计算机科学与技术学院
?4 消息传递机制
? 主要研究,
? 存储转发；
? 虫蚀寻径方法；
? 它们的通信时延问题；
? 针对无死锁的消息寻径确定的寻
径算法和自适应两种寻径算法。
哈尔滨工业大学计算机科学与技术学院
? 一,消息寻径方式
? 1.消息的格式
（ 1）消息 (message)
? 是结点间通信的逻辑单位，它常常由任意数
目的长度固定的包组成，因此它的长度是可
变的。
? 在消息传递网络中通信的信息单位是：消
息、包和片的格式。
? 消息寻径中的信息单位如下图所示。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
（ 2）包 (packet)
? 是含寻径目的地址的基本单位；
? 每个包需要一个序号；
? 不同的包可能异步地到达目的结点，
以便把传送的消息重新装配起来。
? 在采用 存储转发寻径方式 的多计算
机系统中，包是信息传送的最小单
位。
哈尔滨工业大学计算机科学与技术学院
? 包的长度取决于寻径方式和网络的实
现方法。
? 典型的包长度为 64--512位。序号可
能占用 1--2个片，取决于消息的长度。
? 包和片的大小还与通道频宽、寻径器
设计以及网络流量密度等有关。
哈尔滨工业大学计算机科学与技术学院
?（ 3）片,
?包可分成一些固定长度的数据片。
寻径信息 (目的地址 )和序号形成头
片，其余的片是数据。
?在采用虫蚀寻径网络的多计算机中，
包可进一步分成片。
?片的长度往往受网络大小的影响，
256个结点的网络需要片长为 8位。
哈尔滨工业大学计算机科学与技术学院
?2.存储转发寻径
? 定义：下图说明了这一概念。
? 在存储转发网络中包是信息流的基
本单位。
? 存储转发网络的时延与源和目的之
间的距离 (段数 )成正比。
? 第一代多计算机系统采用这种寻径
方式。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?3.虫蚀寻径
? 新型的计算机系统都采用虫蚀寻径
方式，把包进一步分成更小的片；
? 与结点相连的硬件寻径器中有片缓
冲区。消息从源结点传送到目的结
点要经过一系列寻径器。
? 同一个包中所有的片，象 不可分离
的同伴一样以流水方式顺序地传送。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 特点,
? 所有数据片必须跟着头片。不同的包
可交替地传送，但不同包的片不能交
叉。否则它们可能被送到错误的目的
地。
? 虫蚀寻径的时延几乎与源和目的之间
的距离无关。
哈尔滨工业大学计算机科学与技术学院
? 4.异步流水
? 采用如下图所示的握手协议，可以实现一
个包内相继片的异步流水运行。
? 异步流水的效率很高，所用的时钟比同步
流水的时钟快，如果路径中的片、缓冲片
或后继通道在某个周期不能使用的话，则
流水线将出现阻塞。
? 如果出现这种情况，则包可能要缓冲、阻
塞、延缓或绕道通过。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?5,时延分析
?下图是包通过存储转发网络和虫
蚀网络的时间比较情况
?其中,
?L是包的长度 (位 )
?W是通道频宽 (位／秒 )
?D是距离 (经过的结点数 -1)
?F是片的长度 (位 )
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 存储寻径网络的通信时延 TSF可表示
为,
?TSF＝ L／ W × (D+1)
? 虫蚀寻径 TWH,
TWH ＝ L／ W+F／ W× D
? 显然,
?TSF与 D成正比；
?如果 L,F，那么 TWH= L／ W，距离 D
对寻径延时的影响可忽略不计。
哈尔滨工业大学计算机科学与技术学院
? 典型的 TSF值约在 2000至 6000?s之间，
而典型的 TWH值只有 5?s或者更小。
? 存储转发寻径往往由软件控制，而
虫蚀寻径则完全用硬件寻径器以流
水方式工作 。
哈尔滨工业大学计算机科学与技术学院
? 二、死锁和虚拟通道
?1.虚拟通道
? 虚拟通道是两个结点间的逻辑链，
它由源结点的片缓冲区、结点间的
物理通道以及接收结点的片缓冲区
组成。
? 下图说明了四条虚拟通道共享一条
物理通道的概念。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?通道的特点,
? 两个端点增加了缓冲区和用来控制虚拟通
道状态的 R／ A线。实现虚拟通道需要用交
叉开关控制、多路选择器和多路分配器。
? 物理通道由所有的虚拟通道分时地共享。
以片传递为基础的分时方法可使一组虚拟
通道共享一条物理通道。
? 用某些通道状态 (如 R／ A信号 )来表示不同
的虚拟通道，控制源缓冲区存放等待使用
通道片。
? 通道 (电缆或光纤 )是它们之间的通信媒介
哈尔滨工业大学计算机科学与技术学院
? 例题 通道上的循环等待引起的死锁
? 如下图所示，有两类死锁是由缓冲
区或通道上的循环等待引起的。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 如下图采用虫蚀寻径的网格形网络中，
四条消息沿四个通道同时传送也会产
生通道死锁 (channel dead lock)
? 4个消息的 4个片同时占用了 4个通道。
如果循环中没有一个通道被释放，死
锁状态将持续下去
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?2.死锁的避免
? 通过增加两条虚拟通道 V3和 V4，可以
打破死锁循环。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 双向通道与单项通道的实现比较
? 虚拟通道可以用单向通道或者双向通道实现。
把两条单向通道组合可以构成一条双向通道；
? 双向通道中的仲裁要复杂一点。
? 单向通道相比较，双向通道由于要做方向仲裁，
因而增加了延迟，又由于控制复杂，因而还增
加了成本。
? 网络的流量不大时，双向通道效率比较高。
? 确定虚拟通道数目时，需要对网络吞吐量和通
信时延折衷考虑。实现数目很大的虚拟通道需
要用高速的多路选择开关。
哈尔滨工业大学计算机科学与技术学院
? 三、流控制策略
?1.问题的提出,
? 当两个或更多的包在某个结点为竞争
缓冲区或通道资源而发生冲突时，必
须确定如何解决冲突的策略。
?针对一对一通信寻径算法和自适应
寻径算法进行讨论。
哈尔滨工业大学计算机科学与技术学院
?2.包冲突的解决
?必须具备三个条件,
?(1)源缓冲区已存有该片；
?(2)通道已分配好；
?(3)接收缓冲区准备接收该片
哈尔滨工业大学计算机科学与技术学院
? 另外还存在,
? 当两个包到达同一个结点时，它们可
能会请求用同一个接收缓冲区或者要
用同一个输出通道，因此必须对两个
问题做出仲裁,
?(1)把通道分配给哪个包?
?(2)没有分配到通道的包做什么事?
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?3.两个包争用的解决方法,
? 提出了一种虚拟直通寻径缓冲方法。
? 虚拟直通方法是存储转发和虫蚀两种寻径方法
的折衷。当不发生冲突时，就如同虫蚀寻径方
法一样工作。
? 最坏情况下，效果与存储转发寻径方法相同。
? 虫蚀寻径在出现冲突时就采用阻塞策略。
? 第 2个包被阻塞不再前进，但并没有被扬弃。
? 某些多计算机网络综合了以上某些流控制策略
的优点，采用混合策略。
哈尔滨工业大学计算机科学与技术学院
?4,维序寻径
? 包寻径可以归结为确定和自适应两类。
? 确定寻径
? 通信路径完全由源和目的地址确定。
? 维序寻径
? 需要一种按照多维网络维序的特定顺序来选
择后继通道。在二维网格网络中称为 X— Y寻
径，首先沿着 X维方向确定路径，然后沿着 Y
维方向选择路径。
? 代表是 E立方体寻径 (E— cube routing)方
法
哈尔滨工业大学计算机科学与技术学院
? 超立方体网络的 E立方体寻径
? 假设有一 N＝ 2n个结点的 n方体。每个
结点的二进制编码为,
?b＝ bn-1bn-2… b1b0。
?源结点为 s＝ sn-1ssn-2… s1s0
?目的结点 d＝ d n-1s d n-2… d1 d0
?要确定一条从 s到 d的步数最小的路
径。
哈尔滨工业大学计算机科学与技术学院
? 将 n维表示成 i＝ 1,2,… n，其中第 i
维对应于结点地址中的第 i-1位。设
v=vn-1vn-2… v1v0是路径中的任一结点。
路径可以根据以下方法唯一地确定。
? ① 计算方向位 ri＝ si-1?di-1,
? 其中 i＝ 1,2,…, n。使 i＝ 1,
?v＝ s，开始以下步骤。
哈尔滨工业大学计算机科学与技术学院
? ② 如果 ri=1，则从当前结点 v寻径到下
一结点,v?2i-1。如果 ri=0则跳过这步；
? ③ i?i+1。如果 i≤n,则转第 2步，否
则退出。
哈尔滨工业大学计算机科学与技术学院
? 例题 4维超立方体网络的正方体寻径
? n＝ 4,s＝ 0110,d＝ 1101,
? 因而 r＝ r4r3r2r1＝ 1011。
? 由于 r1＝ 0?1＝ 1，因此 s就寻径到 s ? 20＝
0111。
? 由于 r2＝ 1?0＝ 1，因此 v＝ 0111就寻径到 v
? 21＝ 0101。
? 由于 r3＝ 1 ? 1＝ 0，因此就可以跳过维 i＝ 3
这一步。
? 由于 r4＝ 1，因此 v＝ 0101就寻径到 v?23＝
1101＝ d。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 5.二维网格网络的 X-Y寻径
? X-Y寻径共有四种模式。
? 东 — 北、东 — 南、西 — 北和西 — 南的路
径方向
? 假定从任意源结点 s＝ (x1,y1)到任意目
的结点 d＝ (x2,y2);
? 寻径从 s开始，首先沿 x方向前进一直
到 d所在的第 y2列为止，然后沿 y方向
前进直到 d。
哈尔滨工业大学计算机科学与技术学院
? 例题：二维网格连接多计算机的 X— Y寻径
? 下图中有 4个 (源，目的 )对，可用以说明二
维网格的 4种寻径模式。
? 从结点 (2,1)到结点 (7,6)需要一条东 —
北路径。
? 从结点 (0,7)到结点 (4,2)要建立一条
东 — 南路径。
? 从结点 (5,4)到结点 (2,0)需要一条西 —
南路径。
? 从结点 (6,3)到结点 (1,5)需要一条西 —
北方向路径。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?6.自适应寻径
?采用自适应寻径的主要目的是避
免死锁。虚拟通道的概念使实现
自适应寻径更经济和更灵活。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 例题 使用虚拟通道的自适应 X-Y寻径
? 这是一个用 X— Y寻径的网格网络示例，
在 Y维上用了 2对虚拟通道。
哈尔滨工业大学计算机科学与技术学院
? 四、选播寻径算法
?1.通信模式
? 多计算机网络中可能会出现四类通
信模式
? 一个源结点和一个目的结点的一对
一的单播 (Unicast)模式
哈尔滨工业大学计算机科学与技术学院
? 选播 (Multicast)模式,
? 对应于一到多的通信情况，即一个源结
点发送同一个消息到多个目的结点。
? 广播 (Broadcast)模式,
? 对应于一到全体的通信情况。
? 会议 (Conference)模式
? 是多到多的通信。
? 实现这些多目的模式必须使用特殊的
硬件或寻径方法。
哈尔滨工业大学计算机科学与技术学院
? 2.寻径效率
? 常用的两个参数是通道流量和通信时延。
? 通道流量：任何时刻的传输有关消息所使
用的通道数来表示。
? 通信时延：包的最长传输时间来表示。
? 优化的寻径网络应能以最小流量和最小时
延实现有关通信模式。
? 在存储转发网络中时延是最重要的问题；
? 在虫蚀寻径网络中流量对效率的影响更大。
哈尔滨工业大学计算机科学与技术学院
? 例题 网格连接计算机中的选播和广
播
? 下图是在 3X3网格上实现的选播寻径。
? 源结点用 S表示，传送一个包到标号为 n的
s个目的结点。这里,i＝ 1,2,…, 5。
? 目的为 5个的选播可以用 5次单播来实现，
如下图所示。
? X-Y寻径的流量需要用 1+3+4+3+2=13条通
道，到 D3的路径最长，所以时延是 4。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?例题 超立方体计算机上选播和
广播
?为在 n方体上实现广播，可用类
似的生成树时延不超过 n就能到
达所有结点。
?下图是一个根结点为 0000的 4-立
方体。超立方体广播树的流量最
小。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 可以得到一棵贪婪选播树，可从结点
0101发送包到 7个目的结点。这个贪
婪选播算法的基本思想是向那些可达
最多剩余目的结点的维方向发送包。
? 从源结点 S＝ 0101开始，由维 2方向可
以到达 2个目的结点，由维 4方向可以
到达 5个目的结点。
哈尔滨工业大学计算机科学与技术学院
? 第一层所用的通道是 0101?0111和 0101
? 1101。从结点 1101，由维 2方向可以
到达 3个目的结点，由维 1方向可以到达 4
个目的结点。
? 第二层所用的通道是 1101 ? 1111，
1101 ? 1100和 0111 ? 0110。
? 第三层所用的通道是 1111 ? 1110，
1111 ? 1011,1100-1000和 0110-0010。
? 第四层所用的通道是 1110 ? 1010。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 所生成的树不是唯一的
? 在扩充选播树时，首先应该比较所有各维方向的可
达性 (reachability)，然后选择某些维使剩余目的
结点的集合最小。
? 两维之间有连线，那么选择其中任何一维都可以。
? 已经证明贪婪选播算法所需的通道数与多次单
播或广播树相比要少。在虫蚀寻径网络中，实
现选播操作时，每个结点的寻径器应有复制片
缓冲区中数据的能力。
? 为了与选播树或广播树的增长同步，树中同一
层的所有输出通道必须在传输向前推进一层之
前处于就绪状态，否则中间结点需要增加缓冲
区。
哈尔滨工业大学计算机科学与技术学院
?3,虚拟通道
? 如图所示。
? 这些虚拟通道可以用来生成 4个虚拟
网络。
? 西 — 北方向通信应该使用图所示的虚
拟网络。
? 类似地，其它方向的通信可以构造另
外三个虚拟网络。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 网络划分
? 虚拟网络概念可将某一给定的物理网络划
分成几个逻辑子网供选播通信使用。
? 例如,
? 假设源结点 (4,2)要传送消息给 6X8网格
中的一个子网。这个 6X8网格已划分成 4个
逻辑子网。所有向东和向北方向的通信都
使用右上角子网。同样，在网格的剩余几
个部位可以构造其它三个子网。
哈尔滨工业大学计算机科学与技术学院
