在具有保证决定论的帧交换网络中的虚链路的路由选择方法

摘要

本发明涉及一种在帧交换网络中对虚链路进行路由选择的方法，该网络包括所述帧的多个源终端和/或目的终端、通过物理连接而彼此连接的帧交换机，对于点对点类型，每条虚链路由在一个源终端和一个目的终端之间通过所述网络的路径来限定，对于多点类型，每条虚链路由在一边的一个源终端和另一边的多个目的终端之间通过网路的多条路径来限定。对于属于所述定向环的连续交换机的三元组，在遵守分隔约束的同时，所述方法执行虚链路的路由选择，以允许网络的决定论验证。

说明书

技术领域

本发明涉及帧交换网络中的路由选择的领域，更具体地，涉及在AFDX网路中的路由选择的领域。

背景技术

以太网是最众所周知的局域网。以太网可以在相互兼容的两种不同的模式下运行：一种模式是所谓的共享模式，其中，通过帧之间的随机存取和冲突检测，在终端之间共享同一物理介质；另一种模式是所谓的交换模式，其中，终端通过虚链路来交换帧，从而确保不存在冲突。

在交换以太网中，每个终端(源终端或目的终端)分别连接到帧交换机，并且所述交换机通过物理连接来彼此连接。更具体地，每个交换机具有多个端口，所述端口连接至其他交换机的端口或者终端耦合器。在源终端和目的终端之间的虚链路被定义为经由网络而通过将帧从源终端发送到目的终端来定向的路径。同样地，虚链路由这些帧经过的交换机的有序列表定义。对于每个被经过的交换机，通过预定的交换表，根据目的地址来实现帧交换。该交换表非常简单，因为根据交换机的输入端口和帧的目的地址，它表示对应的输出端口。接下来，对其中交换表被预定义的帧交换网络感兴趣，并且随后将这种网络中的第2级的端到端连接表示为“虚链路”，例如在交换以太网中的虚链路。

对于虚链路，可以获得服务保证。然而，在交换机只能支持给定最大吞吐量的情况下，该服务保证对链路的路由选择施加了限制。被发展用于航空工程需求的AFDX网络(航空电子全双工交换式以太网)是一个交换以太网的实例，其中，可以通过虚链路来分配带宽。更具体地，帧之间的最小间隔以及最大帧长都与每个虚链路相关联。此外，对于每个虚链路，转发帧的最大时间、或者等待时间限制(borne de latence)被保证。

在网站www.condoreng.com上可自由使用的标题为“AFDX协议手册”的文件中以及在以申请人的名义提交的专利申请FR-A-2832011中，将会找到对AFDX网络的详细描述。下面将会简单地描述该网络的主要特点。

如已经提及的，AFDX网络基于交换以太网。另外，AFDX网络是全双工类型的，每个终端都能够经由不同的虚链路同时发送和接收帧。由于虚链路具有保证有限制的等待时间的特性，因此AFDX网络也确定流量、带宽和吞吐量的物理分离。因此，每个虚链路具有所保留的端到端路径、分成被称为BAG(带宽分配间隙)的传送间隔的短暂中断和最大帧长。在每个具有预定跑动公差的传送间隔的开始处发送帧。最后，AFDX网络是冗余的，出于可用性的原因，下层的以太网被建成双工通信。数据以封装在以太网帧中的IP包的形式被传送。与传统的以太网交换(利用接收设备的以太网地址)不同，在AFDX网络上的帧交换使用包括在帧头中的虚链路标识符。当交换机在其输入端口上接收帧时，该交换机辨识虚链路标识符并且根据其交换表确定必须经由其发送帧的一个或一些输出端口。交换机快速地验证所发送的帧的完整性，但如果帧是错误的，则不要求重新发送：删除被检测为错误的帧。经由虚链路传输的帧被顺序地编号。在接收时，目的终端验证帧的顺序的完整性。

每条虚链路接都是单向的。该虚链路每次只能来自一个源终端，但是可以同时终于多个目的终端。将虚链路区分为只能服务单个接收设备的在点对点(或单播)模式下的虚链路和服务多个接收设备的在多点(多播)模式下的虚链路。

图1示意性地示出了AFDX网络，该网络包括终端T₁至T₆和帧交换机SW₁、SW₂。可以看到，将终端T₃连接到T₂的虚链路VL₃是点对点类型，而通向T₂和T₃的虚链路VL₂以及通向T₃至T₅的虚链路VL₁是多点类型。

图2示意性地示出了AFDX网络中的交换机。该交换机包括多个FIFO类型的输入缓冲器210、帧滤波装置220、多路复用装置230和多个FIFO类型的输出缓冲器240。输入的帧被存储在不同的输入缓冲器中，每个缓冲器都连接至一个输入端口e_i。滤波装置220去除对应于未被识别的虚链路的帧、错误的帧和导致破坏链路特性的帧。多路复用装置230根据交换表和帧所包括的虚链路标识符将帧引向不同的输出缓冲器240。输出缓冲器通过物理连接传送帧，每个缓冲器都连接至一个输出端口p_i。

在AFDX网络中的虚链路的路由选择包括网络的不同交换机的定义交换表。选择路由以遵守不同链路的带宽限制。对于给出的路由选择的解，验证该网络是实际确定的，即，在不同链路上的转发时间远小于所保证的等待时间界限。为此，通常使用被命名为“网络演算”的计算算法，可以Rene L.Cruz于1991年1月发表在Information Theory上的IEEE.Transactions中的题为《A calculus fornetwork delay，Part I：network elements in isolation》和《Calculus fornetwork delay，Part II：network analysis》的文章中找到对于该算法的描述，第37册第一章的114-141页。对于网络的每个元件，该算法以概率统计的方式评估了在相关元件的输出端处的最大瞬时数据吞吐量。通过最大通信量速率函数来模拟由源终端经由虚链路L_i传送的通信量，另外，通信量包络函数R_i(t)取决于帧的最大长度和链路的两个帧相隔的最小时间间隔，该通信量包络函数为：

$R_i\left(t\right)=s_{\max }+\frac{s_{\max }.t}{\mathrm{BAG}}---\left(1\right)$

其中，S_max是帧的最大长度，BAG是被称为链路带宽分配间隙的量，即，BAG是该链路的两个帧相隔的最小时间间隔。因此，在时间间隔[t₀，t₁]期间经由链路产生的数据量被简单地表示为：

对于网络的每个元件，根据输入端的流量包络和该元件的传送函数(也称为服务曲线)，在该元件的输出端确定流量包络。根据在输入端和输出端处的流量包络，通过上方值来限制元件的队列长度(元件的工作积压)和由通过该元件的包经历的延迟。因此，从源终端开始一直到目的终端，逐步地计算在网络的每个点处的流量包络。根据由该链接经过的元件经历的延迟来估计关于虚链路的等待时间，如有必要，根据这些元件之间的传播时间来估计。然后，对于网络的不同链路，验证估计出的等待时间实际上是否符合保证的期望值。

将会在J.Grieu于2004年9月24日发表的题为《Analyse etevaluation de techniques de commutation Ehternet pourl’interconnexion des systémes avioniques》(用于使航空电子系统相互连接的以太网交换技术分析和评价)的论文中找到等待时间的计算算法(网络演算)的应用的描述。

只要网络没有包括物理循环，上述的验证方法就能良好运转。相反地，如果网络中存在这种循环，则在所述循环之后的虚链路的等待时间不能被确定。

图3示出了AFDX网络的情况，该网络包括一个具有三个交换机的环：SW₁，SW₂，SW₃。每个交换机都具有三个物理端口，每个端口由一个输入端口和一个输出端口组成。交换机SW₁的输出端口p₁连接至交换机SW₃的输入端口e₃。交换机SW₃的输出端口p₃连接至交换机SW₂的输入端口e₂。交换机SW₂的输出端口p₂连接至交换机SW₁的输入端口e₁。在网络中，通过端口p₁、e₃、p₃、e₂、p₂、e₁的路径C形成定向环。在输出端口p₁上的流量包络取决于在输入端口e₁上(即p₂上)的流量包络，并且取决于链路VL₁(在SW₁的输入端)的流量包络。类似地，在p₂处的流量包络依次取决于在p₃处的流量包络和链路VL₃的流量包络。最后，在p₃处的流量包络依次取决于在p₁处的流量包络和链路VL₂的流量包络。可以看出，存在循环的依赖关系，这使得估计流量包络和等待时间是不可能的。

图4示出了AFDX网络的情况，该网络包括一个具有四个交换机的环：SW₁，SW₂，SW₃，SW₄。每个交换机具有四个物理端口，每个端口由一个输入端口和一个输出端口组成。应注意到，在网络中已对四条虚链路VL₁至VL₄进行了路由选择。

SW₁的输出端口23的流量包络取决于SW₃的输出端口5的流量包络和链路VL₁的流量包络。SW₃的输出端口5的流量包络取决于SW₄的输出端口23的流量包络和链路VL₃的流量包络。SW₄的输出端口23的流量包络取决于SW₂的输出端口24的流量包络和链路VL₄的流量包络。最后，SW₂的输出端口24的流量包络取决于SW₁的输出端口23的流量包络和VL₂的流量包络。

同样，由于循环的依赖关系，不能估计通量包络和等待时间。

为了避免循环依赖，已知改变网络的拓扑的方法，例如，在环中未连接的交换机之间增加物理连接，或者甚至增加用于连接至环中的多个或所有交换机的中央交换机。在这两种情况下，拓扑的改变局部地增大了虚链路的可能路由选择路径数量，从而可以改变初始的路由选择并破坏循环依赖。然而，为此不创建新的环或者新链路的路由选择不会引起新的循环依赖是不确定的。因此，将会回到之前的情况并且没有验证网络的决定论的能力将导致新的网络拓扑的复杂化。

本发明的目的在于提供一种在帧交换网络中对虚链路进行路由选择的方法，在无需改变拓扑的情况下，该方法允许网络决定论的肯定验证。

发明内容

本发明由帧交换网络中的虚链路的路由选择方法来限定，该帧交换网络包括所述帧的多个源终端和/或目的终端，帧交换机通过物理连接彼此连接，对于点对点类型，每条虚链路由穿过一个源终端和一个目的终端之间的所述网络的路径限定，对于多点类型，每条虚链路由穿过一侧一个源终端和另一侧多个目的终端之间的所述网络的多条路径限定。所述方法包括以下步骤：

(a)在所述网络中搜索多个所述定向环，其中，多个所述定向环包所述交换机有关的循环置换；

(b)选择在每个定向环中的连续交换机的三元组，每个三元组限定一条禁用的路由选择路径；

(c)确定虚链路的路由选择的解，所述虚链路不经过所述禁用路径；

(d)基于由此所路由选择的虚链路来验证所述网络的决定论(déterminisme)。

如果该网络的决定论被确认，则可以将对应于所述路由选择的解的交换表存储在交换机中。

优选地，该网络的决定论的验证包括计算由所述虚链路越过的交换机的输出端处的流量包络，以及计算关于这些链路的等待时间，然后，将由此获得的等待时间与设置的等待时间界限进行比较。

根据一个优选实施例，在所述步骤(b)中，选择尽可能最大数量的定向环所共有的三元组。

同样可以在所述步骤(b)中，优先选择属于由拓扑约束禁用的路由选择路径的三元组。对于被划分为由独立电源供电的不同区域的网络，所述拓扑约束可以包括：

-当分别连接至所述虚链路的所述源终端和所述目的终端的所述交换机属于同一区域时，禁用任何越过两个区域之间的边界的路由选择路径；

-当分别连接至所述虚链路的所述源终端和所述目的终端的交换机属于不同区域时，禁用任何越过两个区域之间的边界多于一次的路由选择路径。

在优选的应用中，帧交换网络是AFDX网络。

最后，本发明还涉及一种计算机程序，所述计算机程序包括软件工具，当在计算机上运行所述计算机程序时，所述软件工具适于实现上述方法的步骤。

附图说明

图1示意性地示出了示例性的AFDX网络；

图2示意性地示出了在AFDX网络中的交换机的结构；

图3示出了包括一个具有三个交换机的环的AFDX网络的情况；

图4示出了包括一个具有四个交换机的环的AFDX网络的情况；

图5A和5B示出了本发明的工作原理；

图6示出了根据本发明的路由选择方法的流程图；

图7示出了用于应用根据本发明的路由选择方法的AFDX网络的简化实例。

具体实施方式

基于本发明的构思是通过在可能的路径中选择与具有网络的定向环部分的隔离约束来执行虚链路的路由选择。

接下来，将网络的节点或交换机的任何有序序列l作为定向环称为，l＝SW₁，SW₂，...，SW_N，其中N≥3，以使对于i＝1，...，N-1以及SW₁∈G(SW_N)，S_i+1∈G(S_i)，其中，G是建立每个交换机SW与一组其后继者(即，直接连接至SW的输出端口的一组交换机)的对应关系的应用。在全双工网络中，每个物理端口包括一个输入端口和一个输出端口，应理解，如果在网络中存在定向环SW₁，SW₂，...，SW_N，那么SW_N，SW_N-1，...，SW₁同样是定向环，但方向相反。

在实现虚链路的路由选择之前，根据本发明的方法统计网络的定向环。为此，可以将网络示为有向图，该有向图的顶点是交换机和终端，以及输出端口到输入端口的连接是弧。在网络中搜索定向环相当于在图中搜索线路。为此，将图的每个顶点都用标记标注。每个顶点向它的后继站传送其标记，然后这些后继站中的每一个将接收到的标记和它自己的标记并置并且将由此并置的标记传送给其自身的后继站。逐步地继续传送标签。当顶点接收到包括其自身的标记的标记列表时，线路被识别并且停止该列表的传送。然后，将线路按等效类别进行分组：相同类别的定向线路/环相当于邻近的循环置换。为了描述它，按照每一等效类别任意选择一个定向环。

定向环已被识别，通过经过的交换机的数量来对定向环进行分类。如图5A所示，考虑一个这样的定向环。此处，该定向环对应于一个具有六个交换机SW₁至SW₆的物理环。进入到环中的一个交换机SW_i并且出来以后再连接至下一个交换机SW_i+1的虚链路VL不能引起在环中的循环依赖关系，而与在环上已路由选择的虚链路的数量和共享该环的交换机的数量无关。事实上，由于相关链路VL不经过连续交换机的两个输出端口，所以不会引起在这些交换机的输出端处的流量包络之间的任何关系。

因此，应该理解，只有当虚链路共享至少三个连续的交换机(即，具有定向环的至少两个共有的输出端口)时，才能引起循环依赖。如果考虑实际共享具有图5A中的定向环的三个交换机的虚链路，应注意，为了覆盖环并因此获得循环依赖关系，需要至少六个链路VL₁，...，VL₆。通常，对于具有N个交换机的定向环，可以通过正好具有与环共有的三个交换机的最少N个链路获得依赖，优选地对于具有与环共有的多于三个的交换机的N条链路可以获得依赖。对于正好与定向环共有M>2个交换机的链路，应该具有至少条这样的链路，以获得循环依赖关系，其中，E(.)表示整数值。

现在假设对于给出的定向环，消除了对应于环的三个连续顶点的一个路由选择路径。该情况如图5B所示，其中，以折线表示的路径SW₁，SW₂，SW₃被禁止用于路由选择。由于这个约束，不再可能通过导致循环依赖的虚链路来获得环的覆盖。事实上，虚链路VL₁不再被允许并且响应于规定约束的所有虚链路最多包括路径SW₁，SW₂或路径SW₂，SW₃。没有一条虚链路(尤其是VL₆和VL₂)能够引起交换机SW₁和SW₃的流量包络之间的关系。

可以看到，通过禁止通过定向环的给出的三个连续交换机的任何路由选择路径，消除了任何循环依赖的风险。此外，虚链路的路由选择的可能数量受到该禁止(对于具有三个交换机的环，最多减少三分之一)的影响较小。

对于每个定向环，以上述方式来进行。有利地，禁止多个环所共有的路由选择路径以便减少路径数量。

图6示出了根据本发明的路由选择方法的流程图。从描述网络的拓扑步骤610开始，在步骤620中，通过附近的循环置换，统计网络的所有定向环。在步骤630中，按照经过的交换机的数量来对定向环进行分类。对于每个由此获得的定向环，随后在步骤640中识别环中的连续交换机的所有三元组。在步骤650中，搜索多个环所共有的三元组。在步骤660中，选择每个环的一个三元组。有利地，将通过按照优先级的顺序来选择三元组，该三元组由可能的最大数量的环所共有。所选的三元组限定禁用的路由选择路径；通过禁止经由路径的路由选择，对于该路径所属的一个环或多个环，可以破坏循环依赖关系。

在步骤670中，在遵守在步骤660中建立的约束，确定用于对虚链路进行路由选择的解。

在步骤680中，对于在步骤670中得到的路由选择的解，通过估计在由链路经过的交换机的输出端处的流量包络以及用于不同链路的等待时间，来检查网络实际上是否是确定性的。然后，将所获得的等待时间与对所述链路设置的等待时间界限进行比较。

如果决定论被确认，则对应于路由选择的解的交换表被建立并被存储在交换机中。如果决定论未被确认，则在步骤670中尝试一个新的路由选择的解，或者默认地，在步骤660中尝试重新选择禁用的路由选择路径，如虚线所表示的。

图7示出了简化的AFDX网络的实例，该实例用于说明根据本发明的路由选择方法。

网络包括：每一个都可以是源终端或目的终端的五个终端T₁至T₅、以及四个交换机SW₁至SW₄。该网络的定向环通过循环置换来识别：

-对于具有三个交换机的环：

$l_1^{\mathrm{cw}}={\mathrm{SW}}_1,{\mathrm{SW}}_2,{\mathrm{SW}}_4;$$l_1^{\mathrm{ccw}}={\mathrm{SW}}_4,{\mathrm{SW}}_2,{\mathrm{SW}}_1$

$l_2^{\mathrm{cw}}={\mathrm{SW}}_1,{\mathrm{SW}}_4,{\mathrm{SW}}_3;$$l_2^{\mathrm{ccw}}={\mathrm{SW}}_3,{\mathrm{SW}}_4,{\mathrm{SW}}_1$

-对于具有四个交换机的环：

$l_3^{\mathrm{cw}}={\mathrm{SW}}_1,{\mathrm{SW}}_2,{\mathrm{SW}}_4{\mathrm{SW}}_3;$$l_3^{\mathrm{ccw}}={\mathrm{SW}}_3,{\mathrm{SW}}_4,{\mathrm{SW}}_2{\mathrm{SW}}_1;$

对于每个环，列出对于禁用的路由选择路径的候选的三元组：

环$l_1^{\mathrm{cw}}:\{{\mathrm{SW}}_1,{\mathrm{SW}}_2,{\mathrm{SW}}_4\};\{{\mathrm{SW}}_2,{\mathrm{SW}}_4,{\mathrm{SW}}_1\};\{{\mathrm{SW}}_4,{\mathrm{SW}}_1,{\mathrm{SW}}_2\}$

环$l_1^{\mathrm{ccw}}:\{{\mathrm{SW}}_4,{\mathrm{SW}}_2,{\mathrm{SW}}_1\};\{{\mathrm{SW}}_2,{\mathrm{SW}}_1,{\mathrm{SW}}_4\};\{{\mathrm{SW}}_1,{\mathrm{SW}}_4,{\mathrm{SW}}_2\}$

环$l_2^{\mathrm{cw}}:\{{\mathrm{SW}}_1,{\mathrm{SW}}_4,{\mathrm{SW}}_3\};\{{\mathrm{SW}}_4,{\mathrm{SW}}_3,{\mathrm{SW}}_1\};\{{\mathrm{SW}}_3,{\mathrm{SW}}_1,{\mathrm{SW}}_4\}$

环$l_2^{\mathrm{ccw}}:\{{\mathrm{SW}}_3,{\mathrm{SW}}_4,{\mathrm{SW}}_1\};\{{\mathrm{SW}}_4,{\mathrm{SW}}_1,{\mathrm{SW}}_3\};\{{\mathrm{SW}}_1,{\mathrm{SW}}_3,{\mathrm{SW}}_4\}$

环$l_3^{\mathrm{cw}}:\{{\mathrm{SW}}_1,{\mathrm{SW}}_2,{\mathrm{SW}}_4\};\{{\mathrm{SW}}_2,{\mathrm{SW}}_4,{\mathrm{SW}}_3\};\{{\mathrm{SW}}_4,{\mathrm{SW}}_3,{\mathrm{SW}}_1\};\{{\mathrm{SW}}_3,{\mathrm{SW}}_1,{\mathrm{SW}}_2\}$

环$l_3^{\mathrm{ccw}}:\{{\mathrm{SW}}_3,{\mathrm{SW}}_4,{\mathrm{SW}}_2\};\{{\mathrm{SW}}_4,{\mathrm{SW}}_2,{\mathrm{SW}}_1\};\{{\mathrm{SW}}_2,{\mathrm{SW}}_1,{\mathrm{SW}}_3\};\{{\mathrm{SW}}_1,{\mathrm{SW}}_3,{\mathrm{SW}}_4\}$

为了消除循环依赖的任何风险，为每个环选择一个三元组以及禁止通过相应路径的路由选择是足够的。有利地，如已经提及的，为了减少禁用路径的数量，选择尽可能最大数量的环所共有的三元组。在这种情况下，例如，将会选择：

为和所共有的{SW₁，SW₂，SW₄}；

为和所共有的{SW₄，SW₂，SW₁}，；

的{SW₁，SW₄，SW₃}以及的{SW₃，SW₄，SW₁}。

因此，将会只禁用4条路径，而不是理论上需要的6条路径。

实际上，由于施加了路由选择约束，所以对于虚链路的路线确定，验证网络的决定论不是唯一要考虑的约束。例如，在航空电子应用中，已知将网络划分为由独立电源供电的不同区域。因此，出于安全的原因，设置拓扑约束，在下文被称为划分约束，包括：

-如果分别连接到源终端和目的终端的交换机属于相同区域，则禁用越过区域之间的边界的任何路由选择路径；

-如果分别连接到源终端和目的终端的交换机属于相邻的不同区域，则禁用越过区域之间的边界多于一次的任何路由选择路径。

首先，统计根据划分约束而禁用的路由选择路径的集合S。对于给出的要路由的虚链路，遵守该限制相当于分隔关于S的路径的链接。

通常，根据本发明的实施例，在应用与网络的决定论验证相关联的路由选择约束之前，禁用路径的集合S将是可利用的。当为每个定向环选择一个交换机三元组时，有利地，将会选择属于该集合S的已禁用路径的三元组。当然，如果该环的多个三元组属于S，则将会优先选择在尽可能最大数量的定向环所共有的三元组。因此，对于决定论验证将排除的路径数量将会较少量地增加。