互连网络714008295.ppt

2.两种确定寻径算法（维序寻径） （1）二维网格中的X-Y寻径： 首先沿着X维方向确定路径，然后沿着Y维方向选择路径。 假定从任意源结点s = ( X1 Y1 )到任意目的结点 d = ( X2 Y2 )。寻径从s开始，首先沿着X方向前进一直到d所在的第X2列为止，然后沿Y方向前进直到d。 四种模式： 东—北，东—南，西—北，西—南。 下面是一个例子： 0,7 1,7 2,7 3,7 4,7 4,6 7,6 1,5 4,5 7,5 1,4 2,4 3,4 4,4 5,4 7,4 1,3 2,3 3,3 4,3 5,3 6,3 7,3 2,2 4,2 7,2 2,1 3,1 4,1 5,1 6,1 7,1 2,0 Y X 东—北：( 2 , 1 ) ? ( 7 , 6 ) 西—南：( 5 , 4 ) ? ( 2 , 0 ) 东—南：( 0 , 7 ) ? ( 4 , 2 ) 西—北：( 6 , 3 ) ? ( 1 , 5 ) 特点： 总是先沿X维方向寻径，然后再沿Y维方向寻径，寻径不会出现死锁或循环等待现象。 可以扩充到n维网络，如X-Y-Z等等。 可用于存储转发或Wormhole寻径网络，在源和目的结点之间形成一条距离最短的路径。 （2）立方体网络中的E立方体寻径： 假设有一个N = 2n个结点的n方体。每个结点的二进制编码为： b = bn-1 bn-2 …b1 b0 s = sn-1 sn-2 … s1 s0 d = dn-1 dn-2 … d1 d0 如何确定一条从s到d的步数最小的路径？ 将n维表示成i = 1, 2, … n，其中第i维对应结点地址中的第i-1位。设 v = vn-1 vn-2 …v1 v0 是路径中的任一结点。 方法： （1）计算方向位。 使 i = 1 , v = s， 开始下面的步骤。 （2）如果ri = 1，则从当前结点v寻径到下一结点 ； 如果ri = 0，则跳过这一步。 （3）i = i + 1，如果 i ? n，则转第（2）步，否则退出。 如下面的例子： 0110 0010 0000 0100 0111 0001 0011 0101 1110 1010 1000 1100 1111 1001 1011 1101 4维立方体网络 n = 4，s = 0110，d = 1101 寻径： （1）计算方向位。i = 1，v = s ? 0 1 1 r4 1 1 0 r3 1 0 1 r2 0 1 1 r1 （ R= ） （2）r1= 1， （3）r2= 1， （4）r3= 0， （5）r4= 1， 路径为：0110 ?0111?0101?1101 0110 0010 0000 0100 0111 0001 0011 0101 1110 1010 1000 1100 1111 1001 1011 1101 特点： 寻径按照从维1到维4的顺序进行。 如果s和d的第i位相同，则沿维i的方向不需要寻径，否则从当前结点沿着这一维方向走向下一结点（立方体中，每维包括两个结点）。重复这一过程直到到达目的结点。 3.自适应寻径 目的：避免死锁 虚拟通道：使实现自适应寻径更经济和更灵活。 方法：网格网络中，同一维的所有连接都使用虚拟通道。 如下图所示： 02 12 22 01 11 21 00 10 20 （a）没有虚拟通道的原型网络 02 12 22 01 11 21 00 10 20 （b）Y维方向有两对虚拟通道 02 12 22 01 11 21 00 10 20 （c）向西方向传递消息 （d）向东方向传递消息 02 12 22 01 11 21 00 10 20 4.6通信模式 1.通信模式 单播模式（Unicast）：一个源结点——一个目的结点。 选播模式（Multicast）：一个源结点——多个目的结点。（多播、组播） 广播模式（Broadcast）：一个源结点——全体结点。 会议模式（Conference）：多个源结点——多个目的结点。 2.寻径效率 通信流量（Channel traffic）：用传输有关消息所使用的通道数来表示。 通信时延（Communication latency）：用包的最长传输时间来表示。 在Wormhole寻径方式下，网络流量这个参数比较重要。 在存储转发网络中，时延是最重要的问题。 例：网格连接