一种多协议标签交换网络中的流量分配方法及装置

摘要

本发明公开多协议标签交换网络中的流量分配方法及装置，方法包括：从IP包的包头中提取流标识；进行散列运算得出散列值作为容器分配表的表项地址；根据表项地址和容器分配表查找出适合的路径编号，并将IP包从适合的路径输出；判断容器分配表的容器分配是否合理，如果不合理就调整容器分配表。装置包括：流标识提取单元：用于从IP包的包头中提取流标识；散列运算单元：用于进行散列运算得出散列值作为容器分配表的表项地址；容器分配单元：用于根据表项地址和容器分配表查找出适合的路径编号；分组交换单元：将IP包从适合的路径输出；均衡单元：用于判断容器分配表的容器分配是否合理，如果不合理就调整容器分配表。本发明提高流量均衡性能。

说明书

技术领域

本发明涉及一种对网络流量进行分配的方法和装置，具体涉及一种多协议标签交换网络中的流量分配方法和装置。

背景技术

当前，IP网络应用日益普及，用户数和网络规模不断扩大，网络流量持续增长。为了提高IP网络的服务质量和资源使用效率，迫切需要增强IP网络的流量管理能力。多协议标签交换(MPLS)网络融合了面向连接的包转发技术和IP动态路由，是下一代互联网的关键技术。与现有IP网络中的最短路径路由相比，基于MPLS网络的多路径路由提供了简便、高效的流量管理能力，具有很大的应用潜力，也是当前研究的热点领域。流量分配方法是多路径路由的关键技术之一。流量分配是将一个聚集流按照需要的速率比例分割成若干个流，分配给多条路径，实现各条路径流量的平衡增长，达到网络流量均衡分布的目标。

近年来，报道了许多关于流量分配方法的研究，但是这些方法仍存在不足。

轮转方法(round-robin)以包为最小单位分配流量，依次轮流从一组路径中选择一条路径，经由此条路径把包发送出去。轮转方法能够达到最优的流量分配，给转发操作增加的开销较小。其不利一面在于包的顺序严重错乱，这是因为同一对(源节点，目的节点)(source-destination pair)之间的不同路径有不同的延迟，会造成属于同一TCP流的包顺序错乱，而TCP协议把错序到达的包作为网络拥塞的一个信号，据此减少发送速率.

为保持包的顺序，提出了直接散列(Hash)方法。直接散列法以流为最小单位分配流量，使用散列函数选择路径，实现了包的有序传递。散列函数的输入是流标识，对属于同一流的包，流标识保持不变，由此散列函数总是选择同一条路径，于是属于同一个流的包始终分配到同一条路径上。流标识通常取自五元组(源IP地址，目的IP地址，传输层协议号，源端口，目的端口)(source IP address，destination IP address，transport protocol，sourceport，and destination port)的一部分或全部。直接散列方法的不足之处在于，流量均衡效果与包级别的相差较大，这是因为处于活跃状态的流的速率可能差别较大，所以流标识不一定服从均匀分布。

为了直接散列的性能，提出了表散列方法(参见2000-Inforcom，Performance of Hashing-Based Schemes for Internet Load Banlancing)。表散列方法在直接散列方法中加入了一个间接分配结构，首先通过散列函数把聚集流按流标识平均分成多组(假设为均匀散列)，每个组包含若干个流，一个组也称为一个容器(bin)；然后把这些容器按照路径容量比例分配给输出路径。因为容器的数量至少大于输出路径的数量，所以表散列方法把聚集流划分的更细，因此分配容器的方法比直接散列的方法均衡性能更好.

为进一步提高表散列方法的性能，提出了可重分配的表散列方法(参见2005-Computer Networks，Traffic distribution over equal-cost-multi-paths)。该方法记录各个容器及输出路径的流量，每隔一个固定的时间，把容器重新分配一次。为了减少因重新分配容器而引起包错序，该方法只选择由占用率最高的路径所属的容量最大的容器，把这个容器重新分配给占用率最低的路径。

但是，该方法尚存在以下不足：

(1)理论上，如果流标识服从均匀分布，那么已有的散列函数能够以流标识作为关键字，均匀划分流。这时如果流的速率比较接近，那么流就可以均匀分布到各个容器上。但是，由于活跃状态的流的速率差别较大，流标识也不一定服从均匀分布，造成各容器的流量差别较大。发生这种情况时，只能通过重新分配容器才能提高流量均衡的性能。

(2)已有的散列函数是静态的，其依赖的参数一经确定就不改变，所以容器的初始分配也采用静态方法，亦即事先指定容器的数量，并按这个数量和输出路径容量比例把容器分配给路径。因此，当流顺次到达时，各容器的流量差别较大。

发明内容

本发明所要解决的技术问题就是为了克服以上的不足，提出了一种多协议标签交换网络中的流量分配方法及装置，能改善流量分配性能。

本发明的技术问题通过以下的技术方案予以解决：

一种多协议标签交换网络中的流量分配方法，包括如下步骤：

A、从IP包的包头中提取流标识；B、根据流标识进行散列运算得出散列值作为容器分配表的表项地址；C、根据所述表项地址和容器分配表查找出适合的路径编号，并将IP包从所述适合的路径输出；D、判断容器分配表的容器分配是否合理，如果不合理就调整所述容器分配表。

所述步骤D中调整所述容器分配表包括：通过计算各路径的分配偏移，查找出最空闲路径和最忙路径；判断最忙路径上是否存在部分容器，所述部分容器容量最接近于所述最空闲路径的剩余容量、且将所述部分容器从最忙路径重新分配给最空闲路径可使得所有路径的分配偏移更小；如果有，则将所述部分容器从最忙路径重新分配给最空闲路径。

如果最忙路径上不存在所述部分容器，则判断最忙路径上容量最大的容器是否位于容器分配表的表项地址长度表达范围的上界，如果是就将当前表项地址的长度加1，并把首个未扩展表项的地址p置0，如果否就只将首个未扩展表项的地址p置成j-1，其中j是所述最忙路径上容量最大的容器的表项地址；然后增加一新的容器，与所述容量最大的容器组成伙伴容器，接着初始化新增容器的输出路径编号，使之与所述容量最大的容器使用相同的路径。

所述步骤D中调整所述容器分配表还包括：判断所述伙伴容器是否有相同的输出路径，如果是就进行容器合并操作，如果否，判断所述伙伴容器的输出路径的分配偏移是否都大于0，且两者的分配偏移之和小于最空闲路径的分配偏移，如果是就进行容器合并操作，并将合并后的容器的路径设置成最空闲路径；所述容器合并操作包括：判断伙伴容器中的新增的容器是否位于当前表项地址长度表达范围的上界，如果是就将当前表项地址的长度减1，并把首个未扩展表项的地址p置2d-1，如果否就只将当前首个未扩展表项的地址减1；然后释放伙伴容器中的新增的容器。

所述步骤B具体包括：由流标识产生一个足够长的随机比特序列；从所述随机比特序列中，取一定长度的比特即得出所述散列值。

所述步骤D每隔25秒-35秒进行一次。

一种多协议标签交换网络中的流量分配装置，包括：流标识提取单元：用于从IP包的包头中提取流标识；散列运算单元：用于进行散列运算得出散列值作为容器分配表的表项地址；容器分配单元：用于根据所述表项地址和容器分配表查找出适合的路径编号；分组交换单元：将IP包从所述适合的路径输出；均衡单元：用于判断容器分配表的容器分配是否合理，如果不合理就调整所述容器分配表。

所述调整所述容器分配表包括：通过计算各路径的分配偏移，查找出最空闲路径和最忙路径；判断最忙路径上是否存在部分容器，所述部分容器容量最接近于所述最空闲路径的剩余容量、且将所述部分容器从最忙路径重新分配给最空闲路径可使得所有路径的分配偏移更小；如果有，则将所述部分容器从最忙路径重新分配给最空闲路径。

如果最忙路径上不存在所述部分容器，则判断最忙路径上容量最大的容器是否位于容器分配表的表项地址长度表达范围的上界，如果是就将当前表项地址的长度加1，并把首个未扩展表项的地址p置0，如果否就只将首个未扩展表项的地址p置成j-1，其中j是所述最忙路径上容量最大的容器的表项地址；然后增加一新的容器，与所述容量最大的容器组成伙伴容器，接着初始化新增容器的输出路径编号，使之与所述容量最大的容器使用相同的路径。

还包括：判断所述伙伴容器是否有相同的输出路径，如果是就进行容器合并操作，如果否，判断所述伙伴容器的输出路径的分配偏移是否都大于0，且两者的分配偏移之和小于最空闲路径的分配偏移，如果是就进行容器合并操作，并将合并后的容器的路径设置成最空闲路径；所述容器合并操作包括：判断伙伴容器中的新增的容器是否位于当前表项地址长度表达范围的上界，如果是就将当前表项地址的长度减1，并把首个未扩展表项的地址p置2d-1，如果否就只将当前首个未扩展表项的地址减1；然后释放伙伴容器中的新增的容器。

本发明与现有技术对比的有益效果是：本发明提高了流量均衡性能，避免了由于个别容器流量过大而造成重新分配不能取得理想的均衡性能。本发明减少了重分配容器的次数，避免了由于容器在若干条路径之间多次重分配而引起的包的错序，进而影响了网络传递效率。

附图说明

图1是本发明具体实施方式的多协议标签交换网络中的流量分配方法的流程示意图；

图2是本发明具体实施方式的散列运算的原理示意图；

图3是本发明具体实施方式的没有扩展的容器分配表的结构示意图；

图4是本发明具体实施方式的扩展后的容器分配表的结构示意图；

图5是本发明具体实施方式的多协议标签交换网络中的流量分配装置的结构示意图。

具体实施方式

下面通过具体的实施方式并结合附图对本发明做进一步详细说明。

在进行本发明的多协议标签交换网络中的流量分配方法之前，可以先生成容器分配表。容器分配表表项的数目由输出路径的数量决定，取大于路径数的2的幂。

如图1上述，一种多协议标签交换网络中的流量分配方法，包括如下步骤：

第一步：从IP包的包头中提取流标识。

第二步：根据流标识进行散列运算得出散列值作为容器分配表的表项地址。具体可采用如下方法进行：由流标识产生一个足够长的随机比特序列；从所述随机比特序列中，取一定长度的比特即得出所述散列值。如图2所示，在本发明的一个实施例中，流标识经过32位循环冗余校验(CRC32)、16位循环冗余校验(CRC16)和12位循环冗余校验(CRC12)三个运算单元，分别输出32位、16位和12位的随机比特序列。动态散列函数以这三串比特序列作为输入，输出d个比特作为容器分配表表项地址。

第三步：根据所述表项地址和容器分配表查找出适合的路径编号，并将IP包从该路径输出。

第四步：判断容器分配表的容器分配是否合理，如果不合理就调整所述容器分配表。此步骤每隔一固定时间进行一次，所述固定时间越小，流量分配性能越好，但是花费的处理时间越大，而且频繁地调整容器的分配，会有更多包错序的现象。经多次试验后发现，所述固定时间优选为25秒-35秒，进一步优选为30秒。

图3是没有扩展的容器分配表，由b个表项组成，地址从0到b-1，p是容器分配表的参数，代表首个未扩展表项的地址。C是容器的容量，L是容器统计的时间，I是输出路径的编号。图4是扩展后的容器分配表，其中(0，b)，(1，b+1)，(2，b+2)分别是三对伙伴容器。

判断容器分配表的容器分配是否合理的方法是：判断所有路径的分配偏移D都是0，如果是则容器分配表的容器分配合理。路径j的分配偏移是：$D_j=\frac{X_j}{\underset{k=0}{\overset{n-1}{\Sigma }}{X}_k}-\frac{C_j}{\underset{k=0}{\overset{n-1}{\Sigma }}{C}_k},$其中X_j是路径j的流量，$X_j=\underset{i}{\Sigma }(a_{i,j}·F_i),$C_j是路径j的容量。

通过调整散列函数的参数、改变容器分配表的大小以及更新容器分配表的内容，使得容器上的流量分布更为合理。

调整所述容器分配表包括：通过计算各路径的分配偏移，查找出最空闲路径(分配偏移最小的路径)和最忙路径(分配偏移最大的路径)；判断最忙路径上是否存在部分容器，所述部分容器容量最接近于所述最空闲路径的剩余容量、且将所述部分容器从最忙路径重新分配给最空闲路径可使得所有路径的分配偏移更小；如果有，则将所述部分容器从最忙路径重新分配给最空闲路径。这样做的目的是防止把过多的流分配到最空闲路径上，使得最空闲路径又发生过载，从而在未来的某个时刻又要把部分容器从这条路径上移出。这可防止某个容器在多条路径之间来回切换。

如果最忙路径上不存在所述部分容器，那就进行容器分裂操作，容器分裂操作具体为：判断最忙路径上容量最大的容器是否位于容器分配表的表项地址长度表达范围的上界(表达范围的上界：一个有d个二进制位的二进制数，所表示的最大的无符号整数是2^d-1，也即容器分配表中的最后一行)，如果是就将当前表项地址的长度加1，并把首个未扩展表项的地址p置0，如果否就只将首个未扩展表项的地址p置成j-1，其中j是所述最忙路径上容量最大的容器的表项地址；然后增加一新的容器，与所述容量最大的容器组成伙伴容器，接着初始化新增容器的输出路径编号，使之与所述容量最大的容器使用相同的路径。

随着容器分配表不断扩展，p的值不断增加。扩展后的容器和对应的容器构成一对伙伴容器，对内容相同的伙伴容器可以进行合并操作。

调整所述容器分配表还包括：判断所述伙伴容器是否有相同的输出路径，如果是就进行容器合并操作，如果否，判断所述伙伴容器的输出路径的分配偏移是否都大于0，且两者的分配偏移之和小于最空闲路径的分配偏移，如果是就进行容器合并操作，并将合并后的容器的路径设置成最空闲路径；所述容器合并操作包括：判断伙伴容器中的新增的容器是否位于当前表项地址长度表达范围的上界，如果是就将当前表项地址的长度减1，并把首个未扩展表项的地址p置2d-1，如果否就只将当前首个未扩展表项的地址减1；然后释放伙伴容器中的新增的容器。

上述第四步并不需要一定在第三步之后。

下面以一个实例对本发明做进一步说明：假定MPLS入口路由器到MPLS出口路由器之间有10条路径，容量分别记为C₁，C₂，C₃，...，C₁₀，容器分配表表项地址的长度取12(d＝12)，刚好是CRC12的输出，因此初始状态时分配表表项有2^d＝2¹²个。首个未扩展表项的地址p＝0。

随着输入IP包的不断到达，所采取的流量分配方法如下：

步骤1：IP包进入输入缓冲存储单元，等待被分配。

步骤2：分组交换装置从输入缓冲存储单元读取IP包，分离IP包头，送到流标识提取装置。

步骤3：流标识提取单元从IP包头提取流标识，送给散列运算单元。

本例中使用了(源IP地址，目的IP地址)作为流标识，所以对IPv4网络流标识有2³²⁺³²个，对于IPv6可以使用IP地址作为标识，也可以使用包头的流标识字段。也可使用(源IP地址，目的IP地址，源端口号，目的端口号)四元组和(源IP地址，目的IP地址，源端口号，目的端口号，协议号)五元组流标识，本例中从实际应用的角度考虑，选取IP地址作为流标识，因为端口号常用于传输层协议(TCP，UDP等)，一些IP层协议只有协议号。

步骤4：散列运算单元使用动态散列算法，以流标识作为输入计算出容器的地址。散列运算分为2个步骤：(1)比特序列生成函数H(k)。本例中使用的循环冗余校验函数，包括有：CRC12，CRC16和CRC32。实际中也可以选用CRC8等。(参见循环冗余校验码)。H(k)由流标识生成一串60比特长的比特序列。(2)动态散列运算。动态散列与静态散列的主要区别在于能够动态调整散列函数，而且新散列函数“包含”了旧散列函数。这里的包含是指对于由旧散列函数处理过的已经存储在散列表中的关键字，新散列函数的散列结果维持不变。因此动态散列的主要技巧在于散列函数，通常的方法是把关键字变换成一串比特序列，取其中的一部分作为散列值(散列表项的地址)，当需要扩展时增加所取的位数(包含原来的地址比特)。设hi(k)，(其中i＝0，1，...)是一族动态散列函数，把关键字k映射为i长的比特序列：{0，1，...，2i-1}。那么对这一族函数满足：

hi(k)＝hi-1(k)

或

hi(k)＝hi-1(k)+2i-1

这样的函数有很多种，我们使用的方法是先使用一个H(k)把k转换为一串长的随机比特序列，hi(k)就取此序列的后i位。也就是，

设H(k)＝bm-1...b2b1b0

那么hi(k)＝bi-1...b1b0，其中m>＝i

步骤5：散列运算单元把表项地址和IP包长信息分别输出到容器分配单元、均衡单元；

(1)容器分配表的表项地址输出到容器分配单元，用于查找容器分配表，产生输出路径标号，见步骤6。

(2)IP包长信息输出到均衡单元，用于更新动态散列函数的参数，及调整容器分配表的大小和内容，见步骤7。

步骤6：容器分配单元查找容器分配表；

容器分配单元中保存有容器分配表；本例中把容器的流量统计信息(容器分配表的C字段)和输出路径编号(容器分配表的I字段)放在同一表中。

步骤7：均衡单元统计容器流量，更新动态散列函数的参数，并调整容器分配表的大小和内容。

均衡单元监测容器和输出路径的实时流量，每隔一个固定的时间段，检查当前的容器分配是否合理，如果不够合理，那么通过调整散列函数的参数(d、p)、容器分配、扩展或收缩容器分配表，提高流量均衡性能。

均衡单元周期性地触发容器分配的调整操作。具体调整容器分配表包括如下步骤：

(1)使用重分配方法，调整容器的分配。

首先通过计算各路径的分配偏移，找出最空闲和最忙的路径；然后尝试把最忙路径上的部分容器重新分配给最空闲的路径。当我们找到容量最接近于空闲路径j剩余容量的容器，且使得n条路径的分配偏移更小，那么重新分配这部分容器，否则找出容量最大的容器，对该容器进行分裂操作(即进行下面的(2))。

(2)容器的分裂过程。

如果待分裂容器j位于当前表项地址长度(d)表达范围的上界(j＝2d-1)，那么首先要增加表项地址的长度(d＝d+1)，并把p置0，然后增加一组新的容器，与原有的容器组成若干对伙伴容器，接着初始化新增容器的输出路径编号，使之与伙伴容器使用相同的路径，避免包的错序；否则的话，可以只需更新p的值，增加新的容器。p＝j-1

(3)容器的合并过程

均衡单元周期性检查合并的条件：如果“伙伴”容器有着相同的输出路径，那么进行容器合并操作；如果“伙伴”容器的输出路径都有溢出，且溢出之和小于最空闲路径的分配偏移，那么进行容器合并和调整操作。

如果待合并的容器i位于当前表项地址长度(d)表达范围的上界(i＝2d-1)，那么首先要减小表项地址的长度(d＝d-1)，并把p置2d-1，然后释放容器i(释放容器指：去掉容器分配表中的一行，这样容器分配表就变小了；也称作容器分配表收缩了)；否则，只需更新p的值，p＝p-1释放容器i。

步骤8：容器分配单元把输出路径编号返回到分组交换装置，分组交换装置把当前IP包输出到对应的路径上，完成了流量分配过程。

如图5所示，一种多协议标签交换网络中的流量分配装置，包括：流标识提取单元：用于从IP包的包头中提取流标识；散列运算单元：用于进行散列运算得出散列值作为容器分配表的表项地址；容器分配表保存单元，用于保存容器分配表；分组交换单元：用于根据所述表项地址和容器分配表查找出适合的路径编号，并将IP包从该路径输出；均衡单元：用于判断容器分配表的容器分配是否合理，如果不合理就调整所述容器分配表。

本发明将一个聚集流分配到多个不同容量的输出路径上，按照路径容量的比例分配流量，使得各输出路径的占用率均衡增长。

以上内容是结合具体的优选实施方式对本发明所作的进一步详细说明，不能认定本发明的具体实施只局限于这些说明。对于本发明所属技术领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干简单推演或替换，都应当视为属于本发明的保护范围。