第三章作业答案

第三章作业1）修改讲义中的基本路由器模型，使其只使用输入缓冲并且没有虚通道。针对该路由器模型，重写虫孔交换和报文交换的基本延迟表达式。答：假设物理微片与微片大小相等，等于物理通道宽度W;路由头假设为一个微片，消息大小为L+W位;路由延迟为tr秒;两个路由器间物理通道的操作频率为Bhz，则路由器间物理通道的带宽为BW位/秒;假设连线足够短，一个时钟周期能够完成一次传输路由器间传输延迟为tw，路由器内部延迟为ts报文交换延迟时间不变：)*)((⎥⎦⎤⎢⎣⎡+++∗=WWLtttDtwsrpacket虫孔交换延迟时间：⎥⎦⎤⎢⎣⎡++++=WLtttttDtwswsrwormhole*)max()(*2）考虑一个虫孔交换网络，虚电路在被控制信号或特殊消息显示拆除之前一直存在。画出长度为三个微片的消息在长度为三段链路的通路上、在源节点向通路注入控制微片并取消通路之前的传输时空图。答：微片控制头三个微片消息Time取消通路时间3）报文交换相对于消息交换的一个主要优点是，允许几个报文同时沿着从源到目的路径传输。假设所有报文沿同一路径传输，不需要为每个报文添加序列号。画出一个包括4个报文的消息在一个三段链路长的路径上传输的时空图。答：报文报文头Time第一个报文接收时间最后一个报文接收时间4）写出二维网格中最小负向优先算法。答：算法：二维网格中最小负优先输入：当前节点坐标(Xcurrent,Ycurrent)和目的节点(Xdest，Ydest)输出：选择的输出通道Channel过程:（算法大致思想：一正一负先走负，正正负负随便走）Xoffset:=Xdest-Xcurret;Yoffest:=Ydest-Ycurrent;ifXoffset0andYoffset0thenChannel:=Select(X-,Y-);//Select（x，y）选择函数，从通道中选择一个空闲的通道。endif;//(-,-)选空闲ifXoffest0andYoffset0thenChannel:=X-;//(-,+)选X-endif;ifXoffest0andYoffset=0thenChannel:=X-;endif;ifXoffest0andYoffset0thenChannel:=Y-;//(+,-)选Y-endif;ifXoffest0andYoffset0thenChannel:=Select(X+,Y+);//(+,+)选空闲endif;ifXoffest0andYoffset=0thenChannel:=X+;endif;ifXoffest=0andYoffset=0thenChannel:=Intenal;//Intenal连接本地的通道endif;5）采用转弯模型，针对三维网格给出最短路径部分自适应路由算法，使这些算法具有尽可能少的路由限制。答：输入：当前节点坐标（Xcurrent，Ycurrent，Zcurrent），目的节点坐标（Xdest，Ydest，Zdest）输出：选择的输出通道Channel。过程：Xoffset:=Xdest-Xcurrent;Yoffset:=Ydest-Ycurrent;Zoffset:=Zdest-Zcurrent;ifXoffset0andYoffset0andZoffset0thenchannel:=select(X-,Y-,Z-);endififXoffset0andYoffset0andZoffset=0thenchannel:=select(X-,Y-);endififXoffset0andYoffset=0andZoffset0thenchannel:=select(X-,Z-);endififXoffset=0andYoffset0andZoffset0thenchannel:=select(Y-,Z-);endififXoffset=0andYoffset=0andZoffset0thenchannel:=Z-;endififXoffset=0andYoffset0andZoffset=0thenchannel:=Y-;endififXoffset0andYoffset=0andZoffset=0thenchannel:=X-;endififXoffset0andYoffset0andZoffset0thenchannel:=select(X+,Y+,Z+);endififXoffset0andYoffset=0andZoffset=0thenchannel:=X+;endififXoffset=0andYoffset0andZoffset=0thenchannel:=Y+;endififXoffset=0andYoffset=0andZoffset0thenchannel:=Z+;endififXoffset=0andYoffset0andZoffset0thenchannel:=select(Y+,Z+);endififXoffset0andYoffset=0andZoffset0thenchannel:=select(X+,Z+);endififXoffset0andYoffset0andZoffset=0thenchannel:=select(X+,Y+);endififXoffset=0andYoffset=0andZoffset=0thenchannel:=internal;endif6）给出蝶式MIN中可以建立无冲突路径的充要条件。答：蝶式MIN中的地址映射：考虑从Sn-1Sn-2…S1S0到dn-1dn-2…d1d0建立一条电路经过第0级链路：Sn-1Sn-2…S1S0---〉Sn-1Sn-2…S1S0S0Sn-2…S1Sn-1作为第0级开关输入地址,经过第0级开关后：Sn-1Sn-2…S1S0---〉Sn-1Sn-2…S1S0’经过第1级链路：Sn-1Sn-2…S1S0’---〉Sn-1Sn-2…S0’S1S0Sn-1’…S1Sn-2作为第1级开关输入地址，经过第1级开关后：Sn-1Sn-2…S0’S1---〉Sn-1Sn-2…S0’S1’类似的有第i级开关的输出为：Sn-1…Si+1…Si-1'...S1'S0'Si'从而第n-1级开关的输出为：Sn-2’Sn-3’…S1'S0'Sn-1'最后一级连接为恒等排列，所以Sn-2’Sn-3’…S1'S0'Sn-1'=dn-1dn-2…d1d0从而有：Si’=di+1(0≤i≤n-2),Sn-1'=d0所以第i级开关的输出为：Sn-1…Si+1…di-1…d1d0di对于任意两个输入/输出对（S,D)和（R,T)，可以建立无冲突的两条路径的充要条件是：对于任意的i都有:Sn-1…Si+1…Di-1…D1D0Di不等于Rn-1…Ri+1…Ti-1…T1T0Ti7）给出立方体网络中的自路由标记。答：ti=dn-i-1(0=i=n-1)在立方体网络网络中，在第i级开关最低有效位为第n-i-1位，并且最终映射到的目标地址中的对应位为第n-i-1位，所以ti=dn-i-1(0=i=n-1)。8）写出XY多播路由算法。答：输入:目的节点集D,当前节点坐标v=（x,y），源节点坐标u=（x0,y0）过程：ifx=x0then//本地节点是源节点上或下方ify≠y0and(x,y)∈DthenD=D-{(x,y)}；把消息送到本地节点；endifDy0+={(xi,yi)|xi=x0,yy0,(xi,yi)∈D};//源节点上方的目的节点集Dy0-={(xi,yi)|xi=x0,yy0,(xi,yi)∈D};//源节点下方的目的节点集ifDy0+≠φthen把消息和列表Dy0+送到节点(x,y+1);endif//向上发送ifDy0-≠φthen把消息和列表Dy0-送到节点(x,y-1);endif//向下发送D=D-Dy0+-Dy0-;ifD≠φthenDx0+={(xi,yi)|xix0,(xi,yi)∈D};//源节点右方的目的节点集Dx0-={(xi,yi)|xix0,(xi,yi)∈D};//源节点左方的目的节点集ifDx0+≠φthen把消息和列表Dx0+送到节点(x+1,y);endif//向右发送ifDx0-≠φthen把消息和列表Dx0-送到节点(x-1,y);endif//向左发送endifendififxx0then//本地节点在源节点的右边if(x,y)∈DthenD=D-{(x,y)}；把消息送到本地节点；endifDy+={(xi,yi)|xi=x,yiy0,(xi,yi)∈D};//本地节点上方的目的节点集Dy-={(xi,yi)|xi=x,yiy0,(xi,yi)∈D};//本地节点下方的目的节点集ifDy+≠φthen把消息和列表Dy+送到节点(x,y+1);endif//向上发送ifDy-≠φthen把消息和列表Dy-送到节点(x,y-1);endif//向下发送D=D-Dy+-Dy-;ifD≠φthenDx+={(xi,yi)|xx0,(xi,yi)∈D};//源节点右方的目的节点集ifDx+≠φthen把消息和列表Dx+送到节点(x+1,y);endif//向右发送endifendififxx0then//本地节点在源节点的左边if(x,y)∈DthenD=D-{(x,y)}；把消息送到本地节点；endifDy+={(xi,yi)|xi=x,yiy0,(xi,yi)∈D};//本地节点上方的目的节点集Dy-={(xi,yi)|xi=x,yiy0,(xi,yi)∈D};//本地节点下方的目的节点集ifDy+≠φthen把消息和列表Dy+送到节点(x,y+1);endif//向上发送ifDy-≠φthen把消息和列表Dy-送到节点(x,y-1);endif//向下发送D=D-Dy+-Dy-;ifD≠φthenDx+={(xi,yi)|xx0,(xi,yi)∈D};//源节点右方的目的节点集ifDx+≠φthen把消息和列表Dx+送到节点(x-1,y);endif//向左发送endifendif9）给出6X6网格中双路径和多路径多播路由的路径。源节点为（4，3）,目标节点集为（0，0），（4，0），（5，1）（3，2）（0，2）（5，3）（0，3）（3，4）（1，5）（5，5）。答：(1)双路径多播路由：如图9.1所示DH:(4,3)-(3,3)-(2,3)-(1,3)-[(0,3)目的结点]-(0,4)-(1,4)-(2,4)-[(3,4)目的结点]-(4,4)-(5,4)-[(5,5)目的结点]-(4,5)-(3,5)-(2,5)-[(1,5)目的结点]DL:(4,3)-[(5,3)目的结点]-(5,2)-(4,2)-[(3,2)目的结点]-(2,2)-(1,2)-[(0,2)目的结点]-(0,1)-(1,1)-(2,1)-(3,1)-(4,1)-[(5,1)目的结点]-(5,0)-[(4,0)目的结点]-(3,0)-(2,0)-(1,0)-[(0,0)目的结点]节点标记l(v)目的节点源节点图9.16×6双路径多播路由示意图4,044,3194,04(2)多路径多播路由:如图9.2所示DH1：(4,3)-(4,4)-(5,4)-[(5,5)目的结点]DH2：(4,3)-(3,3)-(2,3)-(1,3)-[(0,3)目的结点]-(0,4)-(1,4)-(2,4)-[(3,4)目的结点]-(3,5)-(2,5)-[(1,5)目的结点]DL1：(4,3)-[(5,3)目的结点]-(5,2)-[(5,1)目的结点]DL2：(4,3)-(4,2)-[(3,2)目的结点]-(2,2)-(1,2)-[(0,2)目的结点]-(0,1)-(1,1)-(2,1)-(3,1