CN1192307A

CN1192307A - 消息包路由选择

Info

Publication number: CN1192307A
Application number: CN96195908A
Authority: CN
Inventors: 戴维·科特; 马丁·克里斯托弗·泰瑟姆
Original assignee: British Telecommunications PLC
Current assignee: British Telecommunications PLC
Priority date: 1995-07-28
Filing date: 1996-07-26
Publication date: 1998-09-02
Anticipated expiration: 2016-07-26
Also published as: EP0872087A1; DE69624591D1; CA2228219A1; WO1997005725A1; AU6623496A; KR19990036054A; NO980366D0; MX9800791A; JPH11510335A; DE69624591T2; NO980366L; US6272548B1; NZ313707A; AU712810B2; EP0872087B1; CA2228219C; CN1094008C

Abstract

在具有通常的规则的柘扑结构的网络上携带的消息包的路由选择的一种方法中,该消息包在做出本地路由判决的节点(N)处接收。该消息包以根据路由判断而选出的方法输出。该消息包除携带目的地址外还携带一清楚地表明前进优选方向的方向标志,且路由判决利用此标志做出。可用几个标志,对应于网络的不同维。

Description

消息包路由选择

本发明的背景

本发明涉及在网络上消息包路由选择的方法，同时涉及适于进行此方法的网络和节点。

消息包路由选择网络可被使用于，例如，互连多处理器计算机的不同处理器，或作为互连许多不同计算机LAN的基础。将来，可预见，该种网络可被用于分布式处理应用中，如共享虚拟现实环境-“虚拟会议地点”的准备，或用于数据的快速综合可视化，如在财政金融机构。该种网络也可被用于，例如，在远程通信网络中使用的丁的内部结构。

上述所有实例将从能够以超高速，例如10GBit/s或更高速度运行的网络中受益。为获得这样的速率，就必需有高效的消息包路由选择，以使自源到目的地的传送时间最小，而无需本身就造成瓶颈的路由判定过程。前已提出使用一类被称作“自路由选择”的技术，在本申请人的共有未决的国际申请PCT/GB95/01176中所述。

自路由选择是一种通过分组交换网络中的导航方法，在该网络中，每一节点的前进路由在本地确定，而不查询集中式或分布式网络数据库(自路由选择的正式定义，参考Baransel et al的论文，以下引用参考[14])。路由判决基于取自消息包头的信息(通常为目的地址)。在此种网络中，进行路由判决所需的时间一定不长于单个消息包的传送时间。若此条件不满足，系统不稳定，因为在一节点消息包的到达速率与服务速率之比大于1，结果队列长无限增长。对于高传输速度，或对于短消息包长度，这一稳定准则更难以满足。在以多个Gbit/s传输速率运行的超高速网络情况下，该准则成为一非常严格的限制，尤其当传输格式使用几十个字节长的固定长度消息包或信元。

假定，例如，53字节长的ATM信元且峰值比特率为100Gbit/s[1]，一节点只有几纳秒用于对每一到达的信元完成如下的任务：选择信元被发送的适当的输出线路；并解决竞争。此情况可通过将这些任务分成以管线模式进行的许多独立过程而得以缓解。然而，对于超高速网络，必需令用于进行路由选择和解决竞争的过程尽可能简单，以使处理时间最短。

简化超高速网络中路由选择和解决竞争过程的另一动机是光子装置的技术限制。近期的实验证明了光子网络以单一波长，接近100Gbit/s和更高[2]的单信道速率传输数据的潜力。在这些网络中，传输比特率比电子装置的速度高。然而，路由选择过程包括两个不同量级处理过程的组合-位级和消息包级[1]。对于超高速网络，位级的处理要求响应时间至少为比特周期(皮秒级)的光子装置，而消息包级的处理可用消息包速率(纳秒级)的高速电子装置来完成。光子逻辑装置比电子装置开发得少，它们具有初级功能且相对集成化较差，功耗大且昂贵，而且不可能在未消息包的许多年中取得可与电子装置相比拟的发展水平。因此，超高速自路由选择网络的进一步要求是位级处理的数量和复杂程度应减少到绝对最小。

美国专利5105424揭示了一路由选择方案的例子。它试图用于庞大的集成电子并行处理器。该方案包括在消息包的源确定该消息包从源至目的地所应经过的整个路径，该路径被定义为相对地址的序列，并以头的形式加到消息包中。通过与不同计算节点相关的路由选择自动化装置进行路由选择。消息包输出的方向在超高速网络通过参考头的相对地址来确定，且头的更新是通过删除与本路径前一部分相关部分而得以完成。该法的不足是：必须在每一节点读取地址、处理并改动。这样带来了复杂位级处理的显著的额外开支。同时，由于此方法不允许偏离预定的路径，偏离路由判决不能被使用。这使得对于节点有必要包含一大缓冲器在交通负荷过大的情况下解决竞争。

TY Chung的发表于Phoenix conference on Computers and Communications，Marcl 1989，USA，PP.214-218的论文揭示了一个路由选择方案，该方案，类似上述美国专利，在源完全确定消息包的路径，并将该路径编程在消息包的头上。然而，其不同点在于：路由选择的确定是使用数值算法，而不是来自源的查寻表。但在上述方案中，中间路由选择节点，在该论文中称作“级联节点”，只读取路由选择信息并作用于其上，而不进行自动路由判决。在论文中所采用的方法还要求所有编码到消息包头的路由选择信息必须一位一位地读取、更新，消息包头必须用更新的路由选择信息重写。再者，在试图以高比特率运行的系统中，位级处理量是一显著的不足。尽管该论文涉及偏离路由选择的可能性，路由选择方案，由于其确实性，而不能很好地适合这种方法。在此方案中，若出现偏离，则偏离节点必须重新计算到消息包目的地的整个前进路径的路由选择信息，就象影响偏离的偏离节点本身是消息包的源。因为这些方法使用消息包头上编码的预定路线，没有一种是自路由选择方法。

本发明的简要说明

根据本发明的第一方面，提供一在具有通常拓扑结构网络上传输的消息包进行路由选择的方法，该方法包括：

(a)在一节点接收一消息包：

(b)读取一目的地址和方向标志，两者均与消息包一起传输，方向标志清楚指示消息包的向前传输的优选方向；

(c)根据方向标志值进行本地路由判决；

(d)自该节点根据路由判决优选方向输出消息包。

此处所用“方向标志”一词代表数据的简单单位，它指示一消息包自源到目的地优选的传输方向，而不整个确定路径，即自消息包源到目的地消息包所经过的具体的链路和路由节点列。对于网络一维它可能只包含一个比特。

相应地，此处所用“本地路由判决”一词表示在本地路由选择节点处所作的且当消息包离开源时还未确定的输出路径的选择。

本发明提供一带有最小处理量，但能提供可与最先进路由选择机制相媲美的路由选择有效性和网络性能的自路由选择协议。它利用基于推测航行法(不使航标的自导航)方法。此方法大大减少网络节点处的整个处理，并简化和使位级处理最小。象随机路由选择，另一初级协议，推测航行法是强状的，能承受网络的不规则性和错误，易于实施和管理，易于扩展。然而，不象随机路由选择那样典型的低效，推测航行法能提供很好的路由选择效率和网络性能。

最好，消息包是光网络上的光消息包。

尽管该方法提供了光网络的特有优势，尤其在使用光子装置时，然而它绝不仅限于在这样的网络中使用。例如，它在与高速电子网络或使用电子开关逻辑的光网络一起使用时同样具有优势。

最好，该网络至少是两维，且消息包携带至少两个方向标志，网络的每一维一个方向标志。

该网络可包含诸如下面将详细描述的曼哈顿街网络(ManhattanStreet Network)的节点网络连接阵列。推测航行法法利用网络具有规则或主体规则结构这一事实。例如，在行和列与罗盘主轴相关的规则方形网格网络中，一消息包可能知道其目的地处于北和东。消息包经网络通过选择大致朝向目的地的可能前进的方向来实现自动导航，当消息包遇到一路由节点，它简单地通知节点所选的前进方向：该节点不计算最优方向，该节点的主要任务只是检查消息包的目的地址是否与节点地址全部或部分匹配，并解决竞争。

根据本发明的第二个方面，提供一对在基本规则网络上传输的消息包进行路由选择的节点，该节点包括：

a)一用于接收消息包的输入；

b)一用于利用消息包所携带的信息进行本地路由判决的路由判决单元，该路由判决单元包括响应消息包所携带方向标志的装置，并清楚指示优选的前进方向；

c)许多用于将消息包引导到网络不同方向上的输出；及

d)用于根据路由判决单元输出将消息包引导到各个不同的输出的装置。

根据本发明的第三方面，提供一具有大体规则拓扑结构且依据本发明的第二方面包含许多节点的网络。

根据本发明的第四方面，提供一依据本发明的第三方面包含许多由网络互连的处理器的计算机系统。

附图的描述

在不同方面体现本发明系统将参考附图仅以举例形式进一步详述，并与前述技术对比。其中：

图1是描述实施本发明的自路由选择协议逻辑的流程图；

图2示出16节点的曼哈顿街网络(Manhattan StreetNetwork)；

图3是一表明利用nxn尺寸的MS-Net推测航行法的路由选择效率对网络维数n的路由判决线图；

图4是表明图2中一节点结构的示意图；

图5是表明利用对于在空闲时隙0.003至0.99的消息包插入概率值无缓冲器的8×8MS-Net推测航行法协议的路由选择跳变概率分布图。

图6是一表明本发明8×8MS Net消息包偏离部分作为空闲时隙消息包插入概率的函数的图；

图7是一表明本发明8×8MS Net相对流量作为空闲时隙消息包插入概率的函数的图；

图8是一表明利用最短路径路由选择的8×8MS-Net相对流量作为空闲时隙消息包插入概率的函数的图；

图9是一表明本发明8×8MS-Net消息包跳变平均数作为空闲时隙消息包插入概率的函数的图；

图10示出一本发明中用作互联许多计算机的LAN的网络；

图11示出了本发明用作为WAN以互连许多LAN的网络；

图12是一表明本发明用作多处理器计算机系统主干的网络；

图13示出缓冲的N×N消息包开关；

图14示出本发明用作丁内部结构的超高速消息包网络；

图15示出用于本发明一系统的另一网络拓扑结构；

图16是一节点中处理步骤详细图；

图17示出一节点的光布局；

图18描述一交叉点开关相对行和通常方向的取向；

图19示出一路由选择逻辑处理器；

图20示出了解决竞争逻辑处理器；

图21示出了网络时隙结构；

图22示出了开关带的子区；

图23示出了地址开关的输入的电路结构；及

图24示出向离开节点的消息包中插入信号的电路；及实例的描述

如图2所示，一光网络1包含以规则网格形式互连的多个节点N。在图2所示例中，使用了曼哈顿街网络(MS-Net)拓扑结构。这是一两端连通的带有单向链路的规则网络。有偶数个行和例，每一节点N有两路到达，两路离开。逻辑上，链路在圆形环面上形成栅格，相邻行或列的链路向相反方向传输，图2示出了16节点(4×4)MS-Net。

图4示出了单个节点N的结构，它包括开关2，该开关被设置将输入消息包确定路由至节点行输出Or，至列输出Oc或至节点本地的宿主。该宿主可能，例如，是许多与各节点相连且共同形成一多处理器并行处理计算机系统，开关2也具有来自宿主的输入，以便在适宜的情况下，该节点能将来自本地宿主的消息包插入到网络上。该开关用图1所示新的路由选择方案来设置，且被本发明入称作“推测航行法”。这种操作节点的方法将在下面详细描述。采用此法的电路也参考图16到20在下面详述，并且适当组件的实例在下面题为“实施技术”的章节中确定。推测航行法

在传统自路由选择方法中，每一消息包在其头携带其目的地址。在消息包沿其路线所遇到的每一网络节点处，目的地址被读取，且该信息被用于计算向前传输的最优路径。一般地，通过使用反映网络拓扑结构规律性的顺序计算地址的方案使得路由选择算法可控。

此处所引用的推测航行法算法也依赖于具有规则(或大体规则)结构的网络。在逻辑互连的布局中，连接节点的链路与拓扑结构的主轴取向平行。这样，除目的地址外，每一消息包携带一些关于其目的地总方向的基本信息。例如，在一行和列与罗盘主轴相关的二维方形栅格网络中，消息包可能知道其目的地在“北和东”的某个地方。消息包通过选择(可能的情况下)大致指向目的地的方向传输以实现自导航经过网络。当消息包遇到一路由节点，它只通知该节点优选的向前传输方向；节点不计算最优方向。如上所述，节点的主要任务只是检查消息包的目的地址是否与该节点的地址部分或全部匹配，并解决竞争。

一用推测航行法的路由节点的逻辑功能总结见图1。检查消息包目的地址的相应域与节点地址之间匹配的位级处理可采用超高速光子装置[3-5]的基本单步操作而高效地进行，无需读取和对全部目的地址逐位处理。

当一消息包第一次被置于网络上时，查寻表或最短路径算法被用于确定朝向目的节点的方向，且该信息连同目的地址被编码到消息包头。该算法或查寻过程只能以本地宿主相对较慢的速率进行。消息包起始位置是网络中消息包可寻址此路由信息的唯一点，每一消息包必须携带的方向信息量可以很小：对于网络拓扑的主轴仅一比特。例如，如下文中所述，在使用曼哈顿街网络(MS-Net)情况下，方向信息仅2比特。方向信息由消息包携过网络到达其目的地，在行程中仅偶尔被改变。当消息包遇到一其地址包含与消息包目的地址(例如，在一MS-Net中，当路由节点位于与消息包目的地相同行或列)相应域匹配域的路由节点时，该信息可被改动。当两地址完全匹配时，目的地被找到。曼哈顿街网络(Manhattan Street Network)

根据上文众所周知的MS-Net[6-8]，现就推测航行法方法进行详细描述。MS-Net，如前所述，是一两端连通，单方向链路的规则网络。该网络的吸引人的特色来自其很好的连通性。MS-Net适合解决竞争的简单偏离策略。它在高负载无缓冲器(“棘手”路由选择)或少量缓冲器[8，9]情况下运行良好。对于超高速光子网络，这是一特别有用的特征，其中，技术限制制约实际缓冲深度为小值[10]。极好的连通性同时构造了强状的网络，使其能容许多个链路错误。

在MS-Net中，路由判决必须在消息包所遇到的每一节点处进行。Maxemchuk[7]描述了以高效操作的各种确定路由规则。

这些规则利用网络的规则结构，且依赖以单调算数序列命名行和列的地址方案。这些路由规则的不足之处在于：需要读取整个目的地址，并在每一路由节点处对每一消息包进行各种复杂程度的计算。

推测航行法路由选择规则

在推测航行法方法中，每一消息包通过跟踪朝向目的地的方向寻找经网络路径。目的地处于网络网格“目的行”和“目的列”的交叉点。在消息包第一次被插入网络的位置，它被给定两个相对于网络布局主轴的初始方向，以指示朝向目的地的最短路径。这些“目的地方向”可由一个2bit字代表，一bit对应一主轴。一简捷的方法是指定MS-Net中列的逻辑取向为“南北”向，行为“东西”。(注意在MS-Net的环形拓扑中，南北向规则且连续，不象地球的南北经线，在两极有奇异值)因此，一消息包的目的地方向的可选集可为“北和东”。目的地方向由消息包经网络在其途中携带，且在要求进行路由判决的网络每一节点处，路由选择优先级根据此简单原则被选定：

a)一消息包应，如果可能的情况下，向其目标方向之一的某个方向传输。若有两个或无可用方向，该消息包不顾及选择哪个路径(除非在下列b或c的情况下)。

目的方向仅在即将描述的特定环境被改变。在每一节点，目的地址与节点地址的行和列名相比较，以便检查是否目的行或目的列已被找到(且很明显若行和列地址匹配，则目的地被找到)。当一消息包已找到其目的行或列时，可采用附加路由选择规则：

b)当一消息包遇到其目的行(列)，且若该行(列)沿目的方向之一取向，则该消息包应在可能情况下转向它，否则按主要规则a)进行。

c)若一消息包在其目的方位某一方向沿目的行或列运行时，它应在可能的情况下继续沿该方向运行，否则按主要规则(a)进行。

d)若一消息包穿过其目的行(列)，则该消息包的南北(东西)目的方位必须被检查，并在必要的情况下复位。

e)若一消息包沿其目的行(列)运行，不论是否在目的方向上，而后转弯，则南北(东西)目的方位必须被检查，并在必要的情况下复位。

这些简单的路由选择规则提供了一消息包在每一交叉点以高效率选择前进路径的基础。一具有完成这些规则任务的路由选择逻辑处理器只需每一消息包的4位信息：i)目的方向(2位)；ii)目的行(列)是否与节点行(列)是否相匹配(每一1bit)。用这4个输入位时，路由选择逻辑足够简单使这些规则可用有少量基本布尔逻辑门的硬布线电子线路执行，无需算术、寄存器或查寻表。此逻辑电路可用几个并行线股设计，任一线的最大长度约4个门。路由选择逻辑处理器可在高速下运行，允许以适用于多个Gbit/s网络中进行自路由选择的速率确定最优路径。

因为该网络是各向同性的，路由选择指令对于网络中的每一交叉点是一样的。推测航行法与现存路由选择方案间一个重要的差别在于推测航行法不要求网络的行和列以有组织的方式命名；它们可以完全任意的方式命名，因为路由选择不依赖以特定序列安排的节点地址。路由选择效率

表1给出对于各种尺寸的MS-Net使用推测航行法，随机路由选择和更复杂的路由选择方案所得到的路由选择效率的对比。此处假定无拥塞(解决竞争在下节中考虑)，且消息包严格遵守路由选择规则。规则表明两个自一节点出去的链路间无优先级，其一路径以0.5的概率被选择。对于每一路由选择方案节点间的平均距离(根据跳变数)通过确定网络中每一源和目的地间的平均距离而被算出。路由选择方案的效率是节点间平均最短路径用该路由选择方案的节点间平均距离除。在推测航行法路由选择方案情况下，最短路径算法(基于Maxemchuk的确定规则1[7])被使用一次，只用于从源选择第一输出链路并确定初始目的方位。

图3示出了在尺寸为N×N，其中N＝4到64(16到4096个节点)的MS-Net中，用推测航行法的路由选择效率变化。对于比8×8大的网络，该效率随网络尺寸缓慢变化，且总大于87％。

表1示出了在每一节点用推测航行法的效率值可与用先进最短路径路由选择算法所得的效率相比拟。然而，推测航行法方法更简单：它避免需读取整个消息包目的地址和计算诸如一节点的相对地址，其象限和自节点发出的链路的方向。这对于超高速网络具有显著优势。节点结构

网络传输固定长度消息包，且被开缝以使任一给定链路在每一时隙可传输至多一个消息包。本网络的一节点的结构示于图4[7]。到达两个输入链路的消息包(一个来自行，一个来自列)被给定适当的相对延迟以便时隙与路由开关[11]一致。在每一时隙，节点将从网络接受至多两个消息包以向前传输。若一消息包被确认为已到达其目的地，则它被从网络上取下并转向本地宿主。同时，或者如果在输入链路上检查到空时隙，一消息包可从本地宿主接收到并插入网络。所有进入路由开关的消息包(无论是从网络得到或自本地宿主插入)根据推测航行法方案规则，在可能情况下按照由“目的方位”所指示的优先级，被确定路由至输出链路之一。

节点在两个端口具有输出缓冲器，能暂存少量消息包(K＝0至64)。根据缓冲器尺寸，节点可采用一“棘手”策略(K＝0)或偏离路由选择策略(K)0)以解决若在同一链路上两消息包提示向外传输的优先级所产生的竞争[6]。在出现竞争时，假定至少有一个缓冲器时隙可用，两消息包以优选消息包的随机顺序被引导至所选择的缓冲器。然而，若没有缓冲空间，则两消息包之一(随机选择)可偏离到另一输出口。当在路由选择开关处有两个消息包，且其中之一无特别的向外路由选择优先级，则该消息包将作为偏离的候选。当一消息包无特别的向外路由选择优先级，且无其它限制，该消息包将被分配到随机选取的“输出口”。

有两种可用以处理宿主打算插入网络的新消息包的策略。一个策略是将消息包暂存到源缓冲器中直到其优选输出口可用；另一是任一输出链路或缓冲器可用，即将消息包插入网络。此处我们选择后者，因此假定若有f个可用时隙，其中f＝0.1或2(即，2-f个消息包由网上接收用于向前传输)，则f个新消息包可被自宿主插入，无论其优选输出口是否可用(即，消息包在其源节点可能遭致偏离)。为达到此目的，源端的最小路径算法或查寻表应为每一新消息包提供两套目的方法：一套在该消息包被向前传输至源节点的优选输出口时使用，而另一套在该消息包被偏离到其它口时使用。选取目的方位以便该新消息包找到自源节点给定输出口到目的地的最短路径，假定无进一步偏离。此策辂具有的优点是：平均，一新消息包在到达队列中花费较少的时间，但不足是：若消息包在源节点被偏离，自非优选输出口的最短可用路径可能包含更多的跳变。我们采用基于Maxemchuk的确定规则1[7]以从源选择最优输出链路，同时确定在源节点处有偏离和无偏离的初始目的方位。网络性能

可以预料，自路由选择的推测航行法方案在网络超负荷时将造成降级，因为一消息包可被偏离至其所携带的目的方位不再通过最短路径将其引导至目的地的位置。为探讨此问题，我们已模拟了64节点(8×8)MS-Net性能作为业务负载的函数。在每一节点生成新消息包是无存贮的，在每一节点处消息包生成平均速率相同。选择目的节点遵循均匀分布，新消息包的插入和路由选择独立于网络节点输出缓冲器的状态。

图5示出对提供的不同负荷值，棘手偏离(K＝0)情况下，源与目的之间所用跳变数量的概率分布。提出的负荷用P_A代表，它是源向空闲时隙插入新消息包的概率。跳变概率对应跳变数量的指数降低，甚至P_A高达0.99，证明了推测航行法路由选择协议的可靠性；我们还未检测到消息包被陷掉或无限循环。这一点证明尽管偏离的结果是增加跳变数量，偏离并不危及推测航行法方法的整体性。方案的整体性通过MS-Net网络的规则，循环的拓扑结构而得以保证。图6示出了对各种尺寸的缓冲器，消息包偏离部分对P_A的函数。由于大量进入节点并不关心选择哪一输出链路的消息包，偏离的最大部分，即使无缓冲器，也只有12.2％。

网络效率的更准确的量度是流量。在稳定状态，消息包自源被网络接受的速率应等于网络向目的地发送消息包的速率。因此稳态流量是每一节点每一时隙发送消息包的平均个数。MS-Net的理论最大流量(利用最短路径路由选择的最大存贮和发送流量)是2被以跳变数[8]表示的平均最短路径除。对于8×8MS-Net，其最大流量是2/5.02＝0.399。将相对流量定义为实际流量被理论最大值归格化是有用的。归格化弥补了实际流量对网络大小的依赖，并提供最大可能流量有多少被取得的指示[8]。图7示出了对于各种尺寸的缓冲器相对流量对应P_A的路由判决线。在棘手偏离(K＝0)的情况下，43％的相对流量在最大网络负荷被获取，在缓冲器深度K＝4情况下，该值增加到79％。如图8所示[8，9]，利用初级推测航行法方法所获得的性能完全可以与在每一节点利用最短路径算法给每一消息包路由选择的同样8×8MS-Net的性能相比拟。在该情况下，棘手偏离条件下最大网络负荷点可获取55％的相对流量，缓冲器深度K＝4时，该值增至91％。结论是利推测航行法简洁性的代价是相对流量的稍有降低。而且，由于对于推测航行法在节点处所需进行的处理量最小化了，网络可通过使用足以高得多的速度运行(例如，以100Gbit/s线速度进行消息包头地址匹配已在最近被证实[5])。因此，尽管相对流量稍有降低，但可获取以每秒发送信息记的绝对网络流量的大幅度增长。

另一重要的度量性能指标是延迟，整个延迟包括两部分：消息包在插入网络前必须在宿主缓冲器中等待的时间，和网络本身的延迟(消息包自源到目的地通过网络的时间)。此处我们只考虑后者。由每一跳变引入的网络延迟由三部分组成：传播延迟，在每一节点故意引入的延迟以便与时隙找齐的(图4)，和在输出缓冲器的排队延迟。发明者发现在超高速光子网络，主要是传播延迟。这是因为用于传输一个消息包的时间很短。例如，在前言中所提及，容纳100Gbit/s53字节ATM信元连同保护带和其它头所需时隙约6.5ns[1]，或等于仅1.3m长光纤。因此，对于平均大于几十消息包长的链路，且假定实际光子缓冲器限于几个时隙深[10]，传播时间远超过其它延迟分量。从而，假定链路长类似，将来自源到目的地所必须进行的跳变数最小化是很重要的。图9示出对于大小不同的缓冲器，在采用推测航行法协议的8×8MS-Net中跳变数目的平均值对应P_A的函数关系。同时，示于右手尺度是“相对等待”，被定义为归格化到平均最短路径的跳跃数均值(在这种情况下5.02跳变)。这表明缓冲器深度为4足以将传播延迟减小到理论最小值的30％以内。

如已提及的，MS-Net结构具有来自其良好联通性的有吸引力的特征。它在高负荷下运行良好，并能经受多个链路故障。然而，它在许多方面受到批评：它不支持立体声双声道调频广播；据说它不支持保证服务；且网络允许消息包被改组12。这些是在超过高速光子网络情况下不太显著的批评。首先，在MS-Net中的立体声双声道调频广播必须采用更高级协议来执行(正在开发有效方案[13]，但有效载荷的有效复制在光领域采用无源分裂装置很简便。其次，的确确定的交通模式将产生许多偏离，造成MS-Net通过许多附加跳变来发送一些消息包。然而，因为网络等待很短(由传播延迟支配)，这对于非连接数据可能不是一个重要考虑方向，或者甚至对于传统的延迟敏感的面连接的应用如声音和视频。再次，至于消息包的改组是否为一个显著的不足是一个有争议点。已有建议提出，对于许多可预见应用，消息包改组或在实时中不要求，或采用再装适当大小的缓冲器而可在实时中获得[14]。

在将皮秒级光脉冲用于传输的超高速光子网络中，最实用的方法是允许消息包(包括目的地址和其它头数据)经网络传播，而在传输中不改变且不进行光电再生。它避免了光电瓶颈，同时也避免需要在网络中嵌入超过短激光光源和皮秒级精确度的时钟恢复机构[1]。然而，推测航行法技术依赖于每一消息包携带一些关于其目的地总方向的辅助基本信息，且该信息在消息包自源到目的地的途中可能偶尔被改变。每一消息包所携带的必要的信息可以很小：在我们已详细描述的MS-Net情况下，仅为2比特。此信息的速率(每一消息包时隙2比特)可足够慢以便于对消息包的其余部分利用带外信道能很容易地在链路对链路基础上通信。对于此信令信息没有必要与消息包头的其它部分和有效载荷一样用同样超高速格式传输。它可被在一独立波长，独立时段，或物理上分隔的并行信道中传输，始终假定消息包级的同步穿过每一链路时被保持。

推测航行法方案的几个辅助优点也已被确认。网络中行与列的命名可为任意的；没有必要对分配地址遵循有组织的顺序方案。甚至对于节点没有必要知道网络的维数。这意味着，附加的行和列可在任何时间任意位置被引入网络，无需对现有网络进行改动或调整(除更新在源所使用的查寻表或最短路径算法)。用于引入行和列的特殊方案(如部分寻址[7])，不被要求。因为基本路由选择原则可在硬线路电子逻辑电路中执行以求速度，这是一个很大的优势。这也大大简化了网络归化发展和管理过程。

推测航行法方案可以承受网络的不规则性。若节点或链路以反常的方式被添加或出现故障，则在本地该网络可能几乎不会象规则结构那样受到影响。鉴于基于规则确定性的路由选择规则，顺序算术寻址在此情形下可能出现故障，推测航行法方案看起来具有良好的安全性，尽管路由选择效率降低。正如所描述的，我们对MS-Net的模拟已表明推测航行法方案对偏离很棒，甚至在很大的载荷下。我们同时注意到该方案对由消息包所携带的“目的方向”数据的意外破损也很有效。这些有效性在诸如具有规则循环拓扑的MS-Net网络中可被保证。换句话说，若该消息包被远远偏离其最优路径，或者若目的方位在途中丢失或损坏，该消息包将继续在其非最优选方向传输由此加长了其路途。但是因为网络是循环的，该消息包最终将遇到其目的行和列，且该协议保证其正确方位此后可自动重建。尽管效率较低，推测航行法也可在带有边界的非循环网络中实施。在此情况下，边界的节点将消息包从边界“反射”，同时，如果必要，反向一个或多个目的方位。

能够以多个Gbit/s的速度互连处理器和工作站的超高速网络正在成为现实[1，3，15，16]。以100Gbit/s的峰值速度生成光子消息包[1]，地址识别[5，17]和位级自同步技术[18]为第一证据，最近超高速网络已取得显著进步。此处所述的推测航行法方法容许这些电子学中最近的技术进步被应用于采用光自路由选择的大流量.高速度的超高速网络网格中。超高速消息包互连网络的应用

这些应用仅通过实施描述。本发明的路由选择方法、节点、网络的许多其它应用是可能的。此描述假定此网络是曼哈顿街类型，它已在上述实施例中详述。因此，假定节点是两端连接(每个节点处有2个输入线和2个输出线)。

网络的应用只取决于其所连接宿主的类型和网络的物理延伸。

1.计算机和工作站的直接互联(图10)

例如，超级计算机/“高端”用户的办公室/校园LAN；

例如，分布式处理应用(例如：高质量模拟环境-“虚拟会议室”，财政金融部门数据的快速复合可视化)。

2.LAN的高速互联(图11)

在这种情况下超高速消息包网络节点的宿主是提供与常规较低速网络的路由器。

3.1与2的混合。

4.在大型计算机内部结构中用作“主干”的超高速消息包网络(图12)。

在此情况下，超高速网络节点的宿主是计算机的子系统(处理器，存贮器，I/O装置等)；

5.用作消息包开关(例如，对于极大容量的ATM)内部结构的超高速消息包网络。

在此情况下，节点为消息包开关的输入和输出口服务。图13示出带缓冲器M*N消息包开关(N个输入口，N个输出口)，其中，输入信号被缓冲。

在将超高速消息包网络用作开关的开关设计中，输入口的深输入缓冲器被保留。若网络采用偏离路由选择(如曼哈顿街网络实例所述)，在路由节点可能有小的输出缓冲器。在该情况下，消息包开关可被描述为既有输入缓冲器又有“内部”缓冲器(即，交换网给节点的输出缓冲器一起用作消息包开关整体内部的缓冲器)若使用“棘手”路由选择(即，交换节点无输出缓冲器)，则消息包开关整体上只有输入缓冲器。

图14示出了消息包开关的结构。

另外的拓扑结构

尽管联系MS-Net已作描述，本发明可应用于各种不同网络拓扑结构。例如，此方法可用于被称作“三角连接网络”(ATC)的拓扑结构中，该结构第一次由GE Myers和ME Zarki(“Routing inTAC：Triangularly Arranged Connection Networks”，Proc.INFOCOM’90，pp.481-486(1991)描述。TAC是一其中节点处于等边三角形顶点的三连通网络结构。图15示出了一个16节点的4×4TAC网络的例子。节点数需是4的倍数以使链路正确取向。Myers和Zarki描述了类似Maxemchuk的MS-Net方案的自路由选择方案，其中，每一节点利用消息包目的地址数据(必须整个读取)和当前节点数据计算每一到来消息包的最优向外离开的链路。

另外的方法是如下推测航行法方案：网络的主轴如图所示，并将以x，y和z标记。每一链路形成与主轴之一平行的部分链路线(称作一行) (类似MS-Net的街道)。每一节点的地址有3个域(每个域对应与主轴平行链路行的名称)。消息包的目的地处于链路三个已命名行的交叉点，具有地址(D_X，D_Y，D_Z)。每一消息包携带一套相对于主轴的地址方向。地址方向由3-bit字表示。TAC中推测航行法的路由选择规则如下。当前路由节点具有地址(N_X，N_Y，N_Z)。

a)消息包应该，如果可能，向其目的地址之一的方向传输。若有两个可选用的方向，消息包不关心选择两个中的哪一个(除下面b或c情况之外)。若有三个或没有可选方向，消息包不关心选择哪一个路径(除下面b或c情况之外)。

仅在当前所述特定情况下，目的方位被改变。在每一节点处，目的地址与节点地址相比较以便检查是否指示消息包已找到目的地所处链路行的D_X＝D_x，D_Y＝N_y，或D_Z＝N_z(显然，若所有三个匹配条件均为翰，则目的地已被找到)。

当匹配条件之中一个或两个为真，采用附加路由选择规则。

b)若消息包遇到目的地所处链路行，且若该链路行朝向目的地，则消息包应在可能的情况下转向它，否则按主规则进行。

c)若消息包沿目的地所在链路行上传输，且沿朝向目的地的方向传输，它应在可能的情况下继续沿该方向传输，否则按主规则进行。网络的例子。

d)若消息包穿过目的地所在链路的一行，则在可能的情况下，消息包的目的方位必须被检查并在需要时复位。

e)若消息包沿目的地所在链路的一行传输，无论是否朝向目的地方位，且此后转向，则在可能的情况下消息包的目的方位必须被检查并在需要时复位。

实施技术

1.节点的逻辑操作

图解表示i)采用推测航行法自路由选择协议的路由节点的逻辑功能，和ii)节点结构如上述图1和4所示。表明节点内处理步骤的更详细的图示于图16中，关于各步骤操作的细节在下文给出。

2.节点的光连接

节点的光布局在图17中给出。若将其与图4比较，总开关符号被三个2×2光开关(两个“寻址开关”和一个“交叉点路由选择开关)取代。适合的路由选择开关可为铌酸锂装置，如由GEC Advanced Components提供的Y-35-8772-02型。示于图17的延迟单元可以是，例如，由PR Prucnal(IEEE J Quantum Electronics.vol29，no2，pp.600-612，1993)描述的可调光延迟系统。光缓冲器可以是由DK Hunter和I Andonovic(Electronics letters，vol29，no3，pp280-281，1993)描述的类型，其中2×2开关可以是上述铌酸锂装置，并且延迟线可以是适当切割的光纤。

3.路由选择逻辑处理器

路由选择逻辑处理器基于前述路由选择规则确定信元的最优前向路由选择。路由请求被解决竞争处理器从每一代表信元到来的路由选择逻辑解决竞争处理器接收到。若一到来路线上的时隙是空的，则相应的路由选择逻辑解决竞争处理器不发出路由请求。信元的路由请求包括下列信息：ii)所请求的离开路径(行，列或不计较)；ii)如果所请求的交叉点开关设置得到许可，信元向前携带的目的方位；iii)如果所请求的交叉点开关设置未得到许可(即，信元被偏离)，信元向前携带的目的方位。通常不论信元是否被偏离，特定信元所携带的目的方位在其经过网络节点时不变。然而，路由规则定义目的方位必须被调整的情况，在下文详细路由选择逻辑表中指出。

路由选择逻辑的输入只包含4位：信元的目的行地址是否与节点行地址相匹配？(1bit)；信元的列地址是否与节点列地址相匹配？(1bit)：东西目的方位取向(1bit)；南北目的方位取向(1bit)。

自本地宿主插入到网络中的新信元被置于先进先出(FIFO)缓冲器并等待空网络时隙。当在到来信号中有一空位或当到来信元已被确认到达其目的地并切换至本地宿主时就出现空时隙，路由选择查寻表为每一开始穿过网络的新信元提供一适当的路由请求。查寻表的项目可通过，例如，最短路径算法而被确定。注意到，只有新信元查询该查寻表：对于传输经过节点的信元不要求使用该表，它代表信息量。同时，查寻过程需仅在相对较慢的本地宿主存取速度下进行。来自查寻表的路由选择请求格式取决于是否直到时隙空闲存在于缓冲器中的新信元在最优输出路径上(假定两个输出路径之一是最优的)可得到。如果在该情况下，路由请求只包括所请求的离开路径(行或列)和离开“目的方位”。然而，如果一空闲时隙在路由选择开关输入口上可获得，该新信元就发射到网络上，查寻表必须提供前面描述的整个3项路由请求。换句话说，在此情况下，如果它发现自身不能经最优路径退出，则必须为新信元提供适当的离开目的方位。

下表示出对于不同行与列配置网络节点的详细路由选择逻辑。实际上，这些表基于前述路由选择规则，示出由4位输入数据输出路由选择请求的映射图。为了表格揭示详细路由选择逻辑的目的，假定网络交叉点处的2×2十字路由开关被配置成“横号”状态是信元沿行和列方向的直通方向，“叉号”开关状态引起方向改变。例如，图18示出一行方向由西向东，列方向由南向北的交叉点。

基于表1(i)图19示出对于在取向为西到东，南到北的交叉点中的路由选择逻辑处理器的电路图，此图进一步证实推测航行法的路由选择逻辑，利用前已提及的4个输入位，是足够简单的，路由规则可采用少量基本布尔逻辑门(反，与和非)，无需算术，寄存器或查寻表即可用硬线路电子电路执行。如图所示，逻辑电路可用几个并行股构成，且任一股的最大长度是约4个门。因此，采用具有极短的上升和下降时间(＜0.2ns)和短的传播延迟(＜0.6ns)的超高速射极耦合逻辑装置，路由选择逻辑自理器可在高速运行，产生少数个纳秒以内的路由请求，适合的装置是由NTT电子技术公司制造的SST ECL逻辑IC系列(SELIC)。零件号码是NLB6201(四2输入或/或非门)；NLB6203(四3输入与/与非门)；NLB6200(五2输入或/或非门)。其后者可被配置成图19和20所示电路的反相器。

4.解决竞争处理器

解决竞争处理器检查各种路由请求并确定是否两信元表示同时向交叉点路由开关的同一输出口的优先。适合的解决竞争过程已在上面描述。在此情况下，解决竞争过程简洁且可由采用少量电子逻辑门的硬线路实现。例如，图20示出了执行解决竞争逻辑处理器主要任务的电路图，逻辑处理器将向十字路由开关发出命令(且假定此处使用“棘手”路由选择-即无输出缓冲器)。对于高速运行，所使用的电子逻辑装置可与上述路由选择逻辑处理器相同(由NTT电子技术公司生产的SST ECL逻辑IC系列(SELIC))。若带有输出缓冲器的偏离路由选择被采用，则逻辑电路稍微复杂一些：将有两个附加数据输入端，每一指示是否缓冲器之一为满。除设置存取和交叉点开关，解决竞争处理器有为前向传输发出适当目的方位的任务。完成此任务的逻辑电路未在图20中示出，但极为简单。对于正选择路由的两消息包中每一个，目的方位从路由选择逻辑处理器G，H或J，K输出端直接取出(图19)，取决于是否每一消息包的路由请求被许可或拒绝。

若要求，优先级方案可被引入。有许多这类方案可供选择，大多数要求附加网络信令以代表单个信元的状态，例如：延迟灵敏度；衰老和存活时间标记； “目的地在望”标志；服务等级；等。这些优先级方案值必须对照组合，传输和处理时间，(它们限制整个网络流量)的额外开支来判断。不要求任务附加网络信令的方案包括对在存取缓冲器内等待的新信元的优先级(优先级许可或拒绝)。

5、头地址匹配

检查是否消息包目的地址中的一个域与路由节点地址中的相应域之间相匹配的任务可采用国际专利申请PCT/GB94/00397中所描述的二进制字识别技术而得以超高速进行，该技术的进一步技术细节在PCT/GB95/01116第15页第22行--第17页第2行中得以揭示。这些先前申请在此处作为参考。此技术的实验证实由D Cotter，JK Lucek，M Shabeer，Ksmith，DC Rogers，D Nesset和P Gunning(“Self-routing of 100Gbit/s packets using 6-bitaddress recognition”，Electronics Letters，在发表中)描述。

6、传递目的方位的方案

如上所述，可能有各种传递目的方位的方法且由每一消息包携带的必要信息量可以很小：对于MS-Net只有2bit。

采用独立时段进行目的方位传递的方法现描述如下。

图2 1示出一网络时隙的例子。在此时隙中，我们将在消息包到消息包基础上本地细粒(位级)时间抽取与全局粗粒(消息包级)时间结合起消息包。此图描述位级和消息包级时间参考之间的关系。网络时钟仅在消息包级提供粗网络同步。网络以时钟频率，最大每个时隙一个信元，由此在时间和空间上被开槽。在图21所示实例中，时隙内的时间分割被作成适应标准ATM信元。网络时钟已被选为标准SDH速率之一。信元包含一瞬时速率为100Gbit/s代表大约440bit(53字节ATM信元加上大约10-20附加头位以保证信元在超高速光消息包网上路由选择)串。注意到，信元在其时隙内位置未以位级精度给出；相反，有一等于几个位周期(在此例在大约100皮秒或10个位周期)的时间容差。网络时隙同时包含一开关带，可供进行路由开关的再配置，和时间保护带，需要此开关带等于多个位周期。例如，一般路由开关(如由GEC Advanced Components提供的Y-35-8772-02型铌酸锂装置，或G Sherlock et al在ElectronicsLetters 30，137-138，1994中所描述的2×2集成Inp半导体型)能够在-1ns级完成开关配置。因此，对于瞬时速率为100Gbit/s的信元，1ns的开关带相当于100个位周期。1ns宽“开关带”可供路由开关再配置的时间。然而，此时隙可被再用于以逐链路为基础由一个节点到另一节点目的方位的传输。图22示出开关带怎样被分成进一步的子带以用于传输目的方位信号：二个100ps宽监视带和一包含2bit2.5Gbit/s信号(代表用于MS-Net推测航行法的2位“目的方位”)800ps宽带。图23示出在一路由节点处接收输入链路上信号的方案。所要求的附加元件位于图17中延迟单元之后。2.5Gbit/s接收器可以是BT&D型PDC2201-2.4-FP。解码电路读取信号位码，将其作为C和D位输出至路由选择逻辑处理器(图19)。如图23所示光调制器完成在到达存取开关或地址域匹配装置之前从消息包中除去2.5Gbit/s的信号。光调制器必须能在100ps的时窗正确地与网络时钟同步开关，且提供20dB光对比度。一个适合的装置是D.G.Moodie，A.D.Ellis和C.W.Ford(在“Generation of 6.3ps optical pulses at a10GHz repetition rateusing a packaged electro-absorption modulator and dispersion compensating fibre，”Electron.lett.vol.30.no.20.pp.1700-1701，1994)中描述的多量子阱半导体电吸收调制器。

图24示出为一离开节点的消息包将2.5Gbit/s的信号插入适当时间带的方案。图24所示的组件将插入到图17所示输出缓冲器之后。2.5Gbit/s的光发射器是带有整体光隔离器的DFB激光型，如Lasertron Inc提供的装置QLM5S710。编码器从解决竞争处理器中取出适当的目的方位bit，并将合适的信号(如上所述2bit 2.5Gbit/s字)提供给与网络时钟正确同步的发射器。

下表TF19和TF20分别是图19和22逻辑电路的输入和输出数据的检索表。References[1] D Cotter，M Shabeer，K Smith，J Lucek and D Rogers，＂UltrafastSelf-Routing Networks＂，Proc. EFOC&N＇95，vol. 2，pp.210-213，Brighton，Engiand(June 1995)[2] S Kawanishi，H Takara，O Kamatani and T Morioka，＂100Gbit/s，500kmOptical Transmission Experiment＂，Opt.Soc.Am.Tech.Dig.OFC＇95，vol.8，pp.287-288，San Diego(February 1995)[3] J R Sauer，M N Islam and S P Dijaili，＂A Soliton Ring Network＂，J.Lightwave Technol.，vol.11，pp.2182-2190(1993)[4] D Cotter and S C Cotter，＂Algorithm for Binary Word Recognition Suitedto Ultrafast Nonlinear Optics＂，Elect.Lett.，vol.29，pp.945-946(1993)[5] D Cotter，J K Lucek，M Shabeer，K Smith，D C Rogers，D Nesset and PGunning，＂Self-Routing of 100Gbit/s Packets Using 6-bit＇Keyword＇ AddressRecognition＂，Elect.Lett.(in press)[6] N F Maxemchuk，＂Regular Mesh Topologies in Local and Metropolitan AreaNetworks＂，AT&T Tech.J.，vol.64，pp.1659-1685(1985)[7] N F Maxemchuk，＂Routing in the Manhattan Street Network＂，IEEE Trans.on Commun.，vol.35，pp.503-512(1987)[8] N F Maxemchuk，＂Comparison of Deflection and Store-and-ForwardTechniques in the Manhattan Street and Shuffle-Exchange Networks＂，Proc.INFOCOM＇89，pp.800-809(1989)[9] A K Choudhury and V O K Li.＂Performance Analysis of DeflectionRouting in the Manhattan Street Network＂，Proc.ICC＇91，pp.1659-1664(1991)[1O] D K Hunter and I Andonovic，＂Optical Contention Resolution and BufferingModule for ATM Networks＂，Elect.Latt.，vol.29，pp.280-281(1993)[11] P R Prucnal，＂Optically-Processed Self-Routing，Synchronisation andContention Resolution for 1D and 2D Photonic Switch Architectures＂，IEEE J.Quant.Electr.，vol.29，pp.60O-612(1993)[12) C Partridge，Gigabit Networking，Addison Wesley，pp.143-147(1994)[13] S C Liew，＂A General Packet Replication Scheme for Multicasting inInterconnection Networks＂，Proc.INFOCOM＇95，pp.394-400(1995)[14] C Baransel， W Dobosiewicz and P Gburzynski，＂Routing in Multihop PacketSwitching Networks：Gigabit-per-second Challenge＂，IEEE Network，vol.9，pp.38-61(May/June 1995)[15] A Bononi，F Forghieri and P R Prucnai，＂Soliton Ultrafast All-Optical MeshNetworks＂，IEE Proc.J.，vol.140，pp.285-290(1993)[16] A G Nowatzyk and P R Prucnal，＂Are Crossbars Really Dead？The Casefor Optical Multiprocessor Interconnect Systems＂，ISCA＇95 Intern.Conf.on Comp.Architecture， Margherita Ligure，Italy(June 1995)[17] I Glesk， J P Sokoloff and P R Prucnal，＂All-Optical Address Recognitionand Self-Routing in a 250Gbit/s Packet-Switched Network＂，Elect.Lett.，vol.30，pp.1322-1323(1994)[18] M Shabeer，J K Lucek，K Smith，D Cotter and D C Rogers，＂Self-Synchronisation Scheme for High-Speed Photonic Networks＂，Elect.Lett.(inpress) 1.交叉点取向西→东和南→北ii)自西到来信元的路由选择逻辑表

输入数据			路由请求
输入数据			路由请求			目的行？	目的列？	到来目的方位	交叉点开关设置	离开目的方位(请求的路由选择)	离开的目的方位(偏离的路由选择)
否	否	E，NE，SW，NW，S	不考虑横号叉号不考虑	E，N		目的行？	目的列？	到来目的方位	交叉点开关设置	离开目的方位(请求的路由选择)	离开的目的方位(偏离的路由选择)
				E，N		E，SW，N	E，SW，N
				W，S		E，SW，N	E，SW，N
				W，S		是	E，NE，SW，NW，S	叉号横号叉号不考虑	E，NW，S+W，N	W，N+E，SW，N
	W，S								E，NW，S+W，N	W，N+E，SW，N
	W，S		是	否	E，NE，SW，NW，S				横号横号叉号不考虑	E，NE，SW，S+	E，S+E，SW，N
W，S										E，NE，SW，S+	E，S+E，SW，N
W，S		是				任意	不考虑(到达目的地)

ii)自南到来信元的路由选择逻辑表

输入数据			路由请求
输入数据			路由请求			目的行？	目的列？	到来目的方位	交叉点开关设置	离开目的方位(请求的路由选择)	离开的目的方位(偏离的路由选择)
否	否	E，NE，SW，NW，S	不考虑叉号横号不考虑	E，N		目的行？	目的列？	到来目的方位	交叉点开关设置	离开目的方位(请求的路由选择)	离开的目的方位(偏离的路由选择)
				E，N		E，SW，N	E，SW，N
				W，S		E，SW，N	E，SW，N
				W，S		是	E，NE，SW，NW，S	横号叉号横号不考虑	E，NW，S+W，N	W，N+E，SW，N
	W，S								E，NW，S+W，N	W，N+E，SW，N
	W，S		是	否	E，NE，SW，NW，S				叉号叉号横号不考虑	E，NE，SW，S+	E，S+E，SW，N
W，S										E，NE，SW，S+	E，S+E，SW，N
W，S		是				任意	不考虑(到达目的地)

+到来和离开目的方位不同 2.交叉点取向东→西和南→北i)自东到来信元的路由选择逻辑表

输入数据			路由请求
输入数据			路由请求			目的行？	目的列？	到来目的方位	交叉点开关设置	离开目的方位(请求的路由选择)	离开的目的方位(偏离的路由选择)
否	否	E，NE，SW，NW，S	叉号不考虑不考虑横号	E，N	E，N	目的行？	目的列？	到来目的方位	交叉点开关设置	离开目的方位(请求的路由选择)	离开的目的方位(偏离的路由选择)
				E，N	E，N	E，S
				W，N		E，S
				W，N		W，S	W，S
				是	E，NE，SW，NW，S	W，S	W，S	叉号不考虑叉号横号	E，N	E，N
	E，S								E，N	E，N
	E，S		W，NE，S+			E，N+W，S
	是	否	W，NE，S+			E，N+W，S	E，NE，SW，NW，S		叉号不考虑横号横号	E，S+	E，N
E，S										E，S+	E，N
E，S			W，NW，S	W，S+W，S
是	任意		W，NW，S	W，S+W，S	不考虑(到达目的地)

ii)自南到来信元的路由选择逻辑表

输入数据			路由请求
输入数据			路由请求			目的行？	目的列？	到来目的方位	交叉点开关设置	离开目的方位(请求的路由选择)	离开的目的方位(偏离的路由选择)
否	否	E，NE，SW，NW，S	横号不考虑不考虑叉号	E，N E，W		目的行？	目的列？	到来目的方位	交叉点开关设置	离开目的方位(请求的路由选择)	离开的目的方位(偏离的路由选择)
				E，N E，W		E，S
				W，N		E，S
				W，N		W，S	W，S
				是	E，NE，SW，NW，S	W，S	W，S	横号不考虑横号叉号	E，N	E，N
	E，S								E，N	E，N
	E，S		W，NE，S+			E，N+W，S
	是	否	W，NE，S+			E，N+W，S	E，NE，SW，NW，S		横号不考虑叉号叉号	E，S+	E，N
E，S										E，S+	E，N
E，S			W，NW，S	W，S+W，S
是	任意		W，NW，S	W，S+W，S	不考虑(到达目的地)

+到来和离开目的方位不同 3.交叉点取向西→东和南→北i)自西到来信元的路由选择逻辑表

输入数据			路由请求
输入数据			路由请求			目的行？	目的列？	到来目的方位	交叉点开关设置	离开目的方位(请求的路由选择)	离开的目的方位(偏离的路由选择)
否	否	E，NE，SW，NW，S	横号不考虑不考虑叉号	E，N	E，N	目的行？	目的列？	到来目的方位	交叉点开关设置	离开目的方位(请求的路由选择)	离开的目的方位(偏离的路由选择)
				E，N	E，N	E，S
				W，N		E，S
				W，N		W，S	W，S
				是	E，NE，SW，NW，S	W，S	W，S	横号叉号不考虑叉号	W，N+E，S	E，NW，S+
	W，N								W，N+E，S	E，NW，S+
	W，N		E，N			E，N
	是	否	E，N			E，N	E，NE，SW，NW，S		横号横号不考虑叉号	W，SE，S	W，SE，N+
W，N										W，SE，S	W，SE，N+
W，N			W，N+	W，S
是	任意		W，N+	W，S	不考虑(到达目的地)

ii)自北到来信元的路由选择逻辑表

输入数据			路由请求
输入数据			路由请求			目的行？	目的列？	到来目的方位	交叉点开关设置	离开目的方位(请求的路由选择)	离开的目的方位(偏离的路由选择)
否	否	E，NE，SW，NW，S	叉号不考虑不考虑横号	E，N	E，N	目的行？	目的列？	到来目的方位	交叉点开关设置	离开目的方位(请求的路由选择)	离开的目的方位(偏离的路由选择)
				E，N	E，N	E，S
				W，N		E，S
				W，N		W，S	W，S
				是	E，NE，SW，NW，S	W，S	W，S	叉号横号不考虑横号	W，N+E，S	E，NW，S+
	W，N								W，N+E，S	E，NW，S+
	W，N		W，S			W，S
	是	否	W，S			W，S	E，NE，SW，NW，S		叉号叉号不考虑横号	E，NE，S	E，NE，N+
W，N										E，NE，S	E，NE，N+
W，N			W，N+	W，S
是	任意		W，N+	W，S	不考虑(到达目的地)

+到来和离开目的方位不同ii)自北到来信元的路由选择逻辑表

输入数据			路由请求
输入数据			路由请求			目的行？	目的列？	到来目的方位	交叉点开关设置	离开目的方位(请求的路由选择)	离开的目的方位(偏离的路由选择)
否	否	E，NE，SW，NW，S	不考虑横号叉号不考虑	E，N		目的行？	目的列？	到来目的方位	交叉点开关设置	离开目的方位(请求的路由选择)	离开的目的方位(偏离的路由选择)
				E，N		E，SW，N	E，SW，N
				W，S		E，SW，N	E，SW，N
				W，S		是	E，NE，SW，NW，S	不考虑横号叉号横号	E，N
	E，SE，N+W，S	E，SW，NE，S+							E，N
	E，SE，N+W，S	E，SW，NE，S+	是	否	E，NE，SW，NW，S				不考虑横号叉号叉号	E，N
E，N+W，NW，S	E，SW，NW，N+									E，N
E，N+W，NW，S	E，SW，NW，N+	是				任意	不考虑(到达目的地)

+到来和离开目的方位不同 4交叉点取向东→西和北→南i)自东到来信元的路由选择逻辑表

输入数据			路由请求
输入数据			路由请求			目的行？	目的列？	到来目的方位	交叉点开关设置	离开目的方位(请求的路由选择)	离开的目的方位(偏离的路由选择)
否	否	E，NE，SW，NW，S	不考虑叉号横号不考虑	E，N		目的行？	目的列？	到来目的方位	交叉点开关设置	离开目的方位(请求的路由选择)	离开的目的方位(偏离的路由选择)
				E，N		E，SW，N	E，SW，N
				W，S		E，SW，N	E，SW，N
				W，S		是	E，NE，SW，NW，S	不考虑叉号横号叉号	E，NE，N+W，NW，S	E，SW，NW，N+
	是	否	E，NE，SW，NW，S	不考虑叉号横号横号	E，N		E，NE，SW，NW，S	不考虑叉号横号叉号	E，NE，N+W，NW，S	E，SW，NW，N+
E，N+W，NW，S					E，N		E，SW，NW，N+
E，N+W，NW，S					是	任意	E，SW，NW，N+	不考虑(到达目的地)

表1

m×n维MS-Net各种路由选定方案的效率，相对于最短路径算法

MS，NetM×n	平均最短路径	推测航行法			Maxemchuk′s确定路由方案(7)		随机路由(7)
		推测航行法			Maxemchuk′s确定路由方案(7)		随机路由(7)		平均距离	95％置位区间	路由效率	规则1路由效率	规则2，3路由效率	规则A路由效率	规则B路由效率
		4×44×66×66×86×108×88×1010×1010×1212×1212×1414×1416×1618×1822×2224×2426×2632×3248×4850×5062×6264×64	2.933333.304353.714294.340434.779665.015875.417725.838386.420177.020987.449107.887189.019619.9133011.929613.015713.940717.012725.009125.969631.975533.0071	2.934253.569134.114854.830345.452085.539936.114416.648617.287887.913748.469808.9999610.1961411.324013.597314.762815.857819.248128.128329.223335.852436.9633	±0.0010±0.0018±0.0021±0.0022±0.0022±0.0015±0.0026±0.0028±0.0032±0.0030±0.0046±0.0043±0.0030±0.0037±0.0038±0.0066±0.0061±0.0085±0.0088±0.0107±0.0138±0.0116	1.0000.9260.9030.8990.8770.9050.8860.8780.8810.8870.8790.8760.8850.8760.8770.8820.8790.8840..8890.8890.8920.893	1.001.001.001.001.001.001.001.001.001.001.00	1.000.970.970.981.000.990.990.991.001.000.99	平均距离	95％置位区间	路由效率	规则1路由效率	规则2，3路由效率	规则A路由效率	规则B路由效率	0.210.140.100.090.070.060.050.050.040.040.03	0.790.300.210.170.140.110.090.080.070.060.06

TF19

解决竞争的逻辑处理器的电路图

(标为A和B的粮个输入消息包的棘手路由选择〕输入数据M，N：消息包A的路由选择请求

M：交叉点开关设置：0＝横号，1＝叉号

N：交叉点开关设置考虑/不考虑：0＝考虑，1＝不考虑P，Q：消息包B的路由选择请求

P：交叉点开关设置：0＝横号，1＝叉号

Q：交叉点开关设置考虑/不考虑：0＝考虑，1＝不考虑输出数据(至交叉横号路由选择开关〕R：交叉点开关设置：0＝横号，1＝交叉

TF20

路由选择逻辑处理器的电路图

(交叉点取向西→东和南→北，位元由西来〕输入数据A：节点行＝目的行？0＝否，1＝是B：节点列＝目的列？0＝否，1＝是C：东-西目的方位： 0＝东，1＝西D：北-南目的方位： 0＝北，1＝南输出数据(路由选择请求〕E：交叉点开关设置：0＝横号，1＝叉号F：交叉点开关设置考虑/不考虑：0＝考虑，1＝不考虑G，H：输出目的方位(受监视的请求的路由选择〕

G：0＝东，1＝西

H：0＝北，1＝南J，K：输出目的方位(不受监视的请求的路由选择〕

J：0＝东，1＝西

K：0＝北，1＝南L：节点是目的节点？0＝否，1＝是

Claims

1、一种用于一具有一般规则拓扑结构的网络上传输的消息包路由选择的方法，包括：

(a)在一节点处接收一消息包；

(b)读取目的地址和方向标志，两者均由消息包携带，方向标志清楚指示消息包前向传输的优选方向；

(c)根据方向标志值进行本地路由判决；及

(d)根据路由判决优选的方向将消息包自节点输出。

2、根据权利要求1的方法，其中消息包是载于光网络的光消息包。

3、根据权利要求2的方法，包括对消息包所载信息在光时域上进行逻辑操作并将逻辑操作结果用于步骤(c)的路由判决。

4、根据前述任一权利要求的方法，其中网络至少有两维，且消息包至少携带两个方向标志，每一标志对应网络的一维。

5、根据权利要求4的方法，还包括将目的地址与节点地址相比较，且当目的地址不是节点地址，但至少目的地址的一个域与节点地址相对应，则为消息包所载的一个或多个方向标志写一新值。

6、根据前述任一权利要求的方法，其中节点，当其同时接收到具有相同的优选前向传输方向的两个或多个消息包时，将其中一个消息包输出到非优选方向上去。

7、根据前述任一权利要求的方法，其中消息包首先在初始节点被放到网络上，初始节点由目的地址确定通常对应自初始节点到目的地址最短路径的传输方向，并相应设置该或每方向标志。

8、根据前述权利要求之一的方法，其中该网络具有环形拓扑结构。

9、根据前述任一权利要求的方法，其中，网络具有非规则寻址方案。

10、一将传输于通常规则网络的消息包做路由选择的节点，该节点包括：

a)一为接收消息包的输入；

b)一用于利用消息包所载信息进行本地路由判决的路由判决单元，路由判决单元包括响应由消息包所载并清楚提示前向传输优选方向的方向标志的装置；

c)用于将消息包以各自不同的方向引导到网络上的多个输出；及

d)用于根据路由判决单元的一个输出将消息包引导到许多各自不同的输出的装置。

11、根据权利要求10的节点，布置以在节点输入接收光消息包。

12、根据权利要求11的节点，包括用于在光域对消息包所载信息进行逻辑操作的一个或多个光逻辑门。

13、根据权利要求12的节点，其中该或每一逻辑门的输出连至路由判决单元；

14、根据权利要求10到13之一的节点，其中，节点被布置在至少两维的网络中连接，且路由判决单元被布置基于至少两个方向标志值进行路由判决，应用中消息包为网络每一维携带一个标志。

15、一具有一般规则拓扑结构并具有根据权利要求10到14任一个的许多节点的网络。

16、根据权利要求15的网络，其中该网络是一光网络。

17、根据权利要求15或16的网络，其中网络有环形拓扑结构。

18、根据权利要求17的网络，具有曼哈顿街网络(MS-Net)拓扑。

19、一包含多个由根据权利要求15至18之一的网络互连的处理器的计算机系统。

20、局域网(LAN)包含根据权利要求15至18之一的网络。

21、用于远程通信网的开关，包括根据权利要求15到18之一的网络。

22、根据权利要求15至18之一的网络，具有不规则寻址方案。