用于分组网络中有效的、防止故障的通信业务分配的分配格子

摘要

本发明涉及在一个分组网络中确定分配格子的方法。按照该网络的输出节点进行网络节点分类，其中按照在网络节点和输出节点之间的最小跳跃数确定节点的类型。在构建的分类之上这样确定用于流的分配格子，使得给出回路自由和能够对于故障情况灵活反应。

说明书

本发明涉及一种方法，用于确定在为具有同一输出节点的包通信业务的分组网络中在有效的、防止故障的通信业务分配的意义上的一个分配格子。

当前，分组网络继续发展的一个中心目标是能够提供通过分组网络的实时服务。该发展任务包括交换技术、网络技术和因特网技术的方面。

传统上分组网络首先用于传输时间非关键的数据例如文件传输或者电子邮件。新发展的目标是，也传输具有实时需求的服务例如传统上经由线路交换网络进行的电话、和视频信息。

服务范围这种有目的的扩展涉及对传输质量的相应的需求。对于具有实时传输的服务必须遵守规定的质量参数，例如对于延迟和数据包的丢失的界限。在专业文献中在这一方面人们经常说到服务质量(简称为QoS)参数或者需求。

扩展最宽的分组网络技术基于IP(Internet Protocol)协议，它在传统上在传输包时只提供最佳努力路由选择(Best-effort-Routing)。包从点到点或者路由器到路由器传输，其中各路由器仅局部决定关于向下一路由器继续传输包的决定。在因特网术语中人们说是单个的跳跃(Hop)。在这一最佳努力方法的框架内不能保证任何服务质量参数。不提供延迟时间或者包丢失率的任何相应的控制。这两个参数可以取众多值，例如当在单一路由器或者单一链路上发生瓶颈时。

一个在为保证为服务质量水平传输所必需的控制的分组网络场合的优选方式是预留从端到端或者从主机到主机的路径。使用路径预定的方法例如是ATM(异步传输模式：Asynchronous Transfer Mode)方法或者对于IP网络的MPLS(多协议标记交换：Multi Protocol Label Switching)方法。全路径预留具有较高复杂性、较低灵活性和较差的资源利用性的缺点。因此对于IP网络开发了另外的方法，这种方法至少部分地保持具有最佳努力的原来的IP概念的灵活性。一种这样的开端是DIFE服务概念(Differentiated Services Konzept)，在该方法中包在进入一个子网络时被赋予优先级，并在该子网络内相应于它的优先级处理。但是这一开端最后未引向真正的服务质量保证，而只导入了服务分级类别。

本发明的任务是要能够经由一个分组网络实现具有服务质量保证的数据传输，其中避免传统方法的缺点。

该任务通过根据权利要求1的方法解决。

本发明方法的出发点是下面为具有服务质量数据传输的网络的构思。尊重为服务质量传输所需的、为延迟时间和丢失率的界限的数据包的有效传输能够通过在一个网络内严格控制通信业务发生结合在该网络内灵活分配通信业务而实现。在下面的实施例的中心存在在一个分组网络内为能够通过允许性检验把全体通信业务发生限制在网络边缘而有效分配数据包。

假设一个包网路用节点(例如通过路由器构造)给出。再假设所述节点借助物理连接(下面称为连接段)组网。根据本发明规定，能够怎样在网络内分配包通信业务，使得尽可能避免由传输线段的故障引起的瓶颈或者损害。

为说明本发明下面引入或者定义一些概念。在为保证在借助允许性控制和通信业务分配经由一个分组网络传输数据包时的质量准则的概念的范围内，包括具有同一输入和输出节点的数据包。下面，这种包的全体作为流表示，也就是说，一个流通过在网络的同一输入和输出点之间通过在该网络内的任意路径传输的数据包给出。这一定义与传统上流的定义不同，在传统的流的定义中考虑端点到端点的传输，亦即例如从主机到主机或者从终端设备到终端设备。每一个流定义了分配格子，并且该被定义的分配格子包括一个流的数据包的全体可能路径。对于一个流的包尽可能允许不同路径的一个序列是有意义的，以便保证灵活性。此外可以以分段方式加权，以便在进行通信业务分配时给规定的路径或者连接段给予大的权重，例如因为在那里可提供高的传输容量。为更详细地表征分配格子，使用概念“链路”。于是一个分配格子由多个(逻辑)链路组成。一个(逻辑)链路表示一个(物理)连接段，通过该连接段该链路所属的分配格子可以传输数据包。与(物理)连接段相对，给(逻辑)链路分配一个方向，它规定在什么方向上该链路的分配格子能够通过连接段传输数据包。

根据本发明取决于针对流的一个输出节点的网络节点分类。类型从在各节点和输出节点之间的最小跳跃数或者最小连接段数确定。最小跳跃数的确定例如对于IP网络可以借助通过路由协议如SPF或者OSPF交换的拓扑信息进行。在到输出节点最小跳跃数的意义上具有同一距离的网络节点属于同一类型。下面为简便起见称类型N的网络节点，其中N是自然数，表示对该输出节点的最小跳跃数。现在可以从类型N的节点引出到类型N-1的节点即在输出节点的方向上的链路。为具有尽可能多的多种路径，对于类型N＞1的节点到类型N-1的节点的所有连接段引入逻辑链路是有意义的。如此引入的逻辑链路总是从具有一个较大的最小跳跃数的类型(类型N)的节点引向一个具有小1的最小跳跃数的类型(类型N-1)的节点。因此这样定义的链路不包含任何回路。此外还可以在一个类型中引入逻辑链路，此时要注意回路自由(Schleifenfreiheit)。除回路自由外在一个类型内引入逻辑链路时还要考虑下面的两个方面：所有节点应该尽可能具有多的出发链路，以便在故障情况下可以有另外可选择的方案。因此对于一个类型的出发链路数的下限应该尽可能大。另一个方面是，在一个类型中应该确定尽可能多的链路，以便优化另外可以选择的路径的数目，此时要注意在该类型内的回路自由。

通过类型的引入和从每一较高类型的节点向较低类型的节点链路的定义，确定对于关于流的分配格子的轮廓，其可以通过在单一类型内的链路补足。重要的优点是效率和回路自由。根据本发明的通信业务分配集中在类型之间的链路。在使用跳跃数作为度量标准从较高到较低类型的路由选择使数据包的路径最小化。路由选择或者在类型内的分配可以被限制在最小值。由此保证尽可能短的路径并因此一种有效的路由选择。从节点的较高类型到较低类型的路由选择是单向的。包括多于一类的节点的回路在这一路由选择时被排除。在全网络中确立回路自由的问题归结为在节点类型内的链路确定，其中必须避免在该类型中建立回路。由此把原来的问题描绘为一个具有极小复杂程度的问题。

在一个类型内无回路地确定链路可以如下进行：

-把类型的节点相应于出发链路数或者在具有同样出发链路数的节点的场合相应于进入链路的容量纳入一个序列中。

-至少对于一部分节点相应于该序列为每一节点执行下面的步骤：

--从各节点识别到类型小1的节点群的最短路径，其中不考虑通过它出发链路直接导向类型N-1的节点的路径。通过识别最短路径使在该类型内的通信业务的分配最小，亦即，关心有效的路由选择。在具有到次低类型最小困难的多个路径的场合，针对回路自由上尝试所有的路径。

--当一个被识别的路径未导向该类型的节点内的一个回路时，则把经由被识别的路径的第一连接段的链路作为链路纳入该分配格子中。在具有多个被识别的路径的场合，可以在回路自由的场合选择一个，或者还对所考虑的节点确定多于一个链路。

根据本发明对分配格子的确定具有大灵活性和小故障性的优点。根据本发明确定的分配格子首先仅涉及一个输出节点(egress node)。从该分配格子可以导出为通过该输出节点传输的所有流的一个通信业务分配，由此执行分配格子的链路的选择。例如对于一个流把输入节点(ingress node)在分类中一并包括在内。从该流的输入节点到通过分配格子的链路引导的输出节点的路径的全部定义分配格子的链路的一个子集，该子集再次为所考虑的流确定一个分配格子。分组网络的路由器的路由选择表现在可以根据为流的分配格子建立。在分组网络中的路由选择或者数据包的继续中继于是根据为所属流的分配格子进行。一个流可以通过所属分配格子的多个路径分配，以便保证平衡的通信业务分配。这一分配例如可以按照包的连接所属性或者相应于包的目的地和源地址进行。通过限制网络的总通信业务发生可实现具有QoS的水平的数据传输，并通过根据本发明的通信业务分配

-通过集中在从较高类型向较低类型的路由选择避免延迟和

-通过通信业务分配和备选路径避免通信业务高峰(从而瓶颈)。

通信业务分配可以根据当前通信业务值动态进行，此时分配格子这样构想，使得每一单个节点尽可能具有为续传一个流的数据包的备选方案。

根据一个输出节点的上述分类可以为在该输出节点离开该分组网络的所有流用于链路故障反应。因为在输出节点的周围关于路径的多样性出现一个瓶颈，因此至少为在输出节点周围的节点进行分类是有意义的。对于在任意涉及所考虑的流的链路故障时的一个应用，所有通过其向具有所考虑的输出节点引导所属通信业务的节点的分类或者该数据网的所有节点的分类是有效的。可以为所有输出节点从而为所有可能的流执行该方法或者分类。

在一个根据本发明分类的节点的一个出发链路故障时可以以下述方式反应：对于具有两个或者更多出发链路的节点的场合，可以把正常时通过故障链路引导的通信业务通过该节点的一个或者多个其他的链路分配。当一个节点的唯一的出发链路故障时，可以反转在该节点上前行的链路的方向，所述链路在同一类型的节点具有它们的输出点。在一个不具有从同一类型的节点来的在其上前行的链路的节点的唯一的出发链路故障时，可以反转其他类型所有在其上前行的链路，亦即对于类型N的一个链路通常是向类型N+1的节点的链路。

当故障时间超过一个规定的界限值时，可以执行对具有该故障链路的节点类型的重新确定。

下面根据附图在实施例的范围内详细说明本发明。

图1表示根据本发明的节点分类的网络线段。

图2表示在不同类型节点间的链路的确定。

图3表示在相同类型节点间的链路的确定。

图4表示在一个输出节点附近的瓶颈的图示。

图5表示通过经由备用出发链路换接通信业务对链路故障的反应。

图6表示通过反转同一类型的一个进入链路对链路故障的反应。

图7表示通过反转对另外类型的节点的链路对链路故障的反应。

图8表示通过新分类节点对链路故障的反应。

对于一个输出节点，包括该网络所有节点的一个分配格子以下述方式构造：对于所有节点测量导向该输出节点的最小跳跃数目的距离。于是跳跃数规定类型所属性。于是对于类型N的每一节点，在该节点和类型N-1的节点之间的所有连接段上确定了导向类型N-1的节点的链路。以下面的步骤执行一类内节点的确定。首先根据从节点出发的链路数和进入链路的容量分配一类节点。在这一分配中考虑出发链路数序列中的链路，在该序列中从具有较少出发链路的节点到具有较多出发链路的节点排序。在具有相同出发链路数的节点的场合，首先考虑具有较高进入链路容量的节点。如果不知道进入链路的容量，则另外也可考虑进入链路数。在这一序列中为类型N的节点确定在该类型内的链路。于是步骤为：

1.相应于上面定义的序列选择类型N的一个节点。

2.识别到类型小1的类型的节点群的最短路径，其中该路径不允许经过直接导向类型N-1的节点的出发链路。

3.当这一路径未导向类型N的节点内的一个回路时，则经由被识别的路径的一个第一连接段的链路作为在该分配格子中的链路被接收。

4.之后考虑在上述定义的序列中的类型N的下一节点。

以这种方式可以在一个类型中引入尽可能大数目的链路，它满足回路自由和为最小出发链路数目的一个尽可能小的下限这两个条件。

图1举例表示一个网络的11个节点，对于这些节点执行根据本发明的分类。输出节点通过一个正方形表示。类型1的节点通过单圆圈表示，类型2的节点通过双圆圈表示，类型3的节点通过3圆圈表示。连接节点之间的连接段通过实线表示。

图2表示引入在不同类型的节点之间的链路，从类型1到类型0的链路通过点线表示，其方向通过箭头表示。在类型1和0之间存在下面的链路：

-从节点5到节点4

-从节点1到节点4

-从节点2到节点4

-从节点9到节点4。

从类型2到类型1的链路通过虚线表示，其方向通过箭头表示。在类型2和1之间存在下面的链路：

-从节点8到节点5

-从节点3到节点5

-从节点3到节点1

-从节点6到节点1

-从节点6到节点9

-从节点11到节点9

-从节点10到节点9

-从节点10到节点2。

最后，通过点划线和通过箭头表示从类型3到类型2的链路，它涉及下面的链路：

-从节点7到节点8

-从节点7到节点3

-从节点7到节点10。

图3表示相应于上述方法如何确定类型内的链路。类型1内的链路通过点线箭头表示，类型2内的链路通过虚线箭头表示。类型1内的链路包括：

-从节点5到节点1

-从节点1到节点2

-从节点9到节点2。

类型2内的链路包括：

-从节点10到节点11

-从节点11到节点6

-从节点11到节点8

-从节点3到节点6

-从节点3到节点8

不同类型之间的链路在图3中通过实线箭头表示。

在图4中通过实线箭头表示所有的链路。在输出节点4附近存在拓扑上决定的某一个瓶颈，因为路径格子为所有的路径都引向同一端点，输出节点。于是例如容易看到，对于一个无回路的路径格子存在一个只具有一个出发链路的节点。因为要是类型1的所有节点都有一个到类型1的一个另外的节点的第二出发链路，则产生一个回路。在图4中是节点2，它只具有一个出发链路。

图5到图8表示根据本发明对一个链路的故障提供的反应。

在图5中在节点6和9之间的链路故障。如用一个点箭头所表示的那样，在正常情况下在节点6和9之间传输的通信业务现在通过从节点6到节点1的链路引导。

在图6中从节点2到节点4唯一的出发链路故障。作为反应(这通过点线箭头表示)，朝向同一类型的节点的链路被反转，由此朝向出发链路。从节点1到节点2的链路和从节点9到节点2的链路方向反转。

在图7中节点9和节点2之间的链路和节点9和节点4之间的链路故障。因此节点9不再有任何出发链路，同时也不具有从同一类型节点来的任何链路。作为反应，反转从较高类型的节点来的全部进入的链路。它涉及从节点6到节点9、从节点11到节点9和从节点10到节点9的链路。

图8接着表示和图7同样的故障情况，其中根据故障的持续时间进行节点9的新一次分类。现在节点9代替类型1而作为类型3的一个节点分配。现在点线箭头表示根据节点9的这一新分类其与未故障情况比较改变了的通信业务引导。