【摘要】 二维torus网络无死锁的自适应路由方法属于分布式高性能容错计算技术领域，其特征在于，把节点之间的每条物理通道被划分为两条虚拟通道，这两条通道均为两向通道，并分配到二维torus网络的四个虚拟子网中，利用虚拟通道分配策略避免了各子网内以及各子网间可能形成的死锁，同时达到更高的自适应性。本发明与传统的维序路由方法、西向优先和负向优先方法相比，当标准化输入负载和网络中故障节点数提高时，我们的方法明显可以提高网络实际流量，并降低传输延迟，从而提高整个网络的传输性能。 【专利类型】发明授权 【申请人】清华大学 【申请人类型】学校 【申请人地址】100084 北京市100084-82信箱 【申请人地区】中国 【申请人城市】北京市 【申请人区县】海淀区 【申请号】CN200810104406.9 【申请日】2008-04-18 【申请年份】2008 【公开公告号】CN101267398B 【公开公告日】2010-09-01 【公开公告年份】2010 【授权公告号】CN101267398B 【授权公告日】2010-09-01 【授权公告年份】2010.0 【IPC分类号】H04L12/56; H04W40/02; H04W40/12 【发明人】向东; 陈振; 王琦 【主权项内容】二维torus网中的无死锁自适应路由方法，其特征在于，所述方法是在每一维上有k个节点的二维torus网上依次按步骤实现的：步骤(1)：初始化对于二维torus网络，连接两个边界之间的物理通道称为边界通道；把每条物理通道划分为两条虚拟通道：c1和c2，这两条通道均为两向通道，c1通道分为c1+和c1-两个方向的通道，c2通道分为c2+和c2-两个方向的通道，“+”和“-”表示消息传输的正负方向；将二维torus网划分为如下四个虚拟子网：x-y-、x-y+、x+y-、x+y+，x+、x-即表示在x轴上的正、负方向的路由，对于y轴同理；步骤(2)：对于每个消息依次按以下步骤分配到所属虚拟子网：设当前节点为curr，目的节点为dest，当前节点和目的节点在两维上的偏移量为A＝xd-xc，B＝yd-yc，其中下标c、d分别代表当前节点和目的节点，dx表示所述维度上的虚拟子网分配，对于dy同理；当A≥0且B≥0时，如果A≥k/2，B≥k/2，则dx＝-，dy＝-；如果A＜k/2，B≥k/2，则dx＝+，dy＝-；如果A≥k/2，B＜k/2，则dx ＝-，dy＝+；如果A＜k/2，B＜k/2，则dx＝+，dy＝+；当A≥0且B＜0时，如果A≥k/2，B≥-k/2，则dx＝-，dy＝-；如果A＜k/2，B≥-k/2，则dx＝+，dy＝-；如果A≥k/2，B＜-k/2，则dx＝-，dy＝+；如果A＜k/2，B＜-k/2，则dx＝+，dy＝+；当A＜0且B≥0时，如果A≤-k/2，B≥k/2，则dx＝+，dy＝-；如果A≤-k/2，B＜k/2，则dx＝+，dy＝+；如果A＞-k/2，B≥k/2，则dx＝-，dy＝-；如果A＞-k/2，B＜k/2，则dx＝-，dy＝+； 当A＜0且B＜0时，如果A＜-k/2，B＜-k/2，则dx＝+，dy＝+；如果A＜-k/2，B＞-k/2，则dx＝+，dy＝-；如果A≥-k/2，B＜-k/2，则dx＝-，dy＝+；如果A≥-k/2，B≥-k/2，则dx＝-，dy＝-；步骤(3)：二维平面上的消息依次按以下步骤路由：步骤(3.1)：如果消息在x-y-虚拟子网中：如果A≥0，B≥0，则选择通道x(c1-)，y(c1-)；如果A＜0，B≥0，则选择通道x(c2-)，y(c1-)；如果A≥0，B＜0，则选择通道x(c1-)，y(c2-)；如果A＜0，B＜0，则选择通道x(c2-)，y(c2-)；步骤(3.2)：如果消息在x-y+虚拟子网中：如果A≥0，B≥0，则选择通道x(c1-)，y(c1+)；如果A＜0，B≥0，则选择通道x(c2-)，y(c1+)；如果A≥0，B＜0，则选择通道x(c1-)，y(c2+)；如果A＜0，B＜0，则选择通道x(c2-)，y(c2+)；步骤(3.3)：如果消息在x+y-虚拟子网中：如果A≥0，B≥0，则选择通道x(c1+)，y(c1-)；如果A＜0，B≥0，则选择通道x(c2+)，y(c1-)；如果A≥0，B＜0，则选择通道x(c1+)，y(c2-)；如果A＜0，B＜0，则选择通道x(c2+)，y(c2-)；步骤(3.4)：如果消息在x+y+虚拟子网中：如果A≥0，B≥0，则选择通道x(c1+)，y(c1+)；如果A＜0，B≥0，则选择通道x(c2+)，y(c1+)；如果A≥0，B＜0，则选择通道x(c1+)，y(c2+)；如果A＜0，B＜0，则选择通道x(c2+)，y(c2+)。 【当前权利人】清华大学 【当前专利权人地址】北京市100084-82信箱 【专利权人类型】公立 【统一社会信用代码】12100000400000624D 【引证次数】1.0 【他引次数】1.0 【家族引证次数】1.0 【家族被引证次数】8
