CN1941681B - 网络带宽分配方法 - Google Patents

Abstract

本发明公开了一种网络带宽分配方法，根据网络的负载程度而调整预测带宽的分配比例，并由此估算要求带宽，进而有效地降低平均传输延迟，并避免带宽浪费的发生；另外，根据终端的最大带宽和带宽补偿值来获取可分配的网络的剩余带宽量，由此分配超额带宽，以提高带宽分配公平性，并减少传输延迟抖动的发生；以及根据终端的要求带宽来调整其上传顺序，以有效地降低平均传输延迟。

Description

网络带宽分配方法

技术领域

本发明涉及一种网络的数据上传技术，特别是一种网络带宽分配方法。

背景技术

一直以来，带宽分配是设计一网络系统时经常被注意的项目之一；以被动光网络(passive optical network；PON)为例，将多个光网络单元(OpticalNetwork Unit；ONU)设置在对应数量的办公室或家庭中，并且利用被动装置耦接至单一光线路终端(Optical Line Terminal；OLT)。也就是说，光线路终端位于局端，通过光纤连接到终端(即客户端)附近的光耦合器，然后再通过光纤接到光网络单元。至此，数据可从光线路终端利用广播(broadcast)方式传送给光网络单元，即下传；以及从光网络单元利用时分多路复用(timedivision multiplexing；TDM)方式将数据传送给光线路终端，即上传，如图1所示。由于，在数据上传时，上传带宽由所有的光网络单元共享，因此带宽分配好坏会直接影响上传数据的传输延迟、带宽使用率以及带宽分配公平性等特性。然而，现有的带宽分配方法并无法有效提供低传输延迟、高带宽使用率及带宽分配公平性等需求。

传统上，将每一光网络单元分配在整个带宽的一个相同部份(即一时分多路复用通道中)，并且对这些光网络单元的传输加以同步，以避免可能的碰撞(例如：两个或多个光网络单元的传输发生部分重迭的情况)。举例来说，在公知技术中，为N个光网络单元分别指配一时隙(time slot)，并且在分配的与其适配的时隙中，各个光网络单元可传输任何数量的数据封包，如图2所示。因此，若某个封包无法在当前时隙内完成传输，则必须将此封包保留，以在下一时隙中再进行传输。虽然此方式并不会发生碰撞且不会发生封包分段，但这种固定循环的时隙分配方式无法处理丛发网络流量的情况。

因此，有人进一步提出一种动态带宽分配方式，可在无数据封包传送时，降低对应时隙的大小，并且可将剩余的带宽给其它光网络单元所利用。然而，在此方式下，光线路终端为了得到精确的时隙分配，因此在指派前，光线路终端需知道每一光网络单元中共有多少字节的数据封包在等待。为此，每一光网络单元在传送数据前，将会传送一特别信息，以通知光线路终端其将传送多少字节的数据封包，而后，光线路终端即计算并分配带宽给欲传送数据封包的光网络单元，并且通知光网络单元可传送带宽以开始传送数据封包。在上传过程中，光线路终端会监控光网络单元的传输，以安排下一光网络单元的传输时间，从而在前一光网络单元传输后接续接收下一光网络单元传输的数据封包。

其中，在动态带宽分配架构中，针对动态带宽分配已提出了许多算法。举例来说，在美国公开的第20030048805 A1号中，提出了一种动态带宽分配算法，如图3所示。参照图3，这种方法先设定每一光网络单元具有一保障带宽B_min_j，其中，j表示要求带宽的服务路径终端的数量，也即要求带宽的光网络单元的数量；换句话说，若在第n个周期中的可用带宽为B_ref，则根据保障带宽B_min_j的比例分配各个光网络单元(其有要求带宽)在第n个周期内的可用带宽。随后，再将分配到的可用带宽扣除补偿值B_add_j，n-1，即可得到在第n个周期内，要求带宽的每一光网络单元可用地理想带宽B_ideal_j，n。接着，进行带宽分配，在这里当光网络单元的理想带宽B_ideal_j，n大于0时，则分配给此光网络单元可传送带宽B_temp_j，n即为其所要求的带宽Q_j，n，否则分配的可传送带宽B_temp_j，n即为0。并且带宽分配完成后，重新计算补偿值B_add_j，n，即可完成光网络单元的上传带宽分配。

其中，补偿值为每一光网络单元在此周期之前所累积的超支带宽总和，其中，补偿值大于0代表在此周期之前有超支带宽存在；反之，补偿值小于0则代表在此周期之前有剩余带宽存在。

在其架构下，虽然已可达到带宽分配的公平性，然而仍存在问题，即当光网络单元长时间使用少量带宽时，将会累积大量的剩余带宽，而当此光网络单元突然有大量带宽需求时，短时间内会用掉大量带宽，如此一来将导致其它光网络单元的传输延迟变长。相反地，若光网络单元长时间维持大量带宽需求时，将使可用的理想带宽时有时无，而导致传输延迟抖动(jitter)的范围变大。

另外，在相关文献中也提出了另一种动态带宽分配算法(请参照Chadi M.Assi，Yinghua Ye，Sudhir Dixit，and Mohamed A.Ali，″Dynamic BandwidthAllocation for Quality-of-Service Over Ethernet PONs，″IEEE Journal on SelectedAreas in Communications，Vol.21，No.9，November 2003，pp.1467-1477)，主要是先根据保障带宽和要求带宽将此周期的可用带宽分配给各个光网络单元(其有要求带宽)，接着再根据要求带宽分配超额带宽(即剩余的可用带宽)，如下列公式。

$B\_{\min }_j=\frac{(T_{\mathrm{cycle}}-N\×T_g)\×r}{8}\×w_j---\left(2\right)$

$B\_{\mathrm{excess}}_j=\frac{B\_\mathrm{left}\×R_j}{{\mathrm{\Σ}}_{k\∈K}{R}_k}---\left(3\right)$

在这里，公式(1)为主要带宽分配的基本方法，其中，R_j代表各个光网络单元所要求的带宽，B_min_j代表各个光网络单元的保障带宽，B_excess_j代表将剩余带宽再分配给光网络单元的超额带宽，以及B_gran_j则是代表光网络单元实际分配到的带宽(即可传送带宽)。由公式(1)可知，当所要求的带宽小于或等于保障带宽时，光网络单元可分配到其所要求的带宽；反之，光网络单元则可分配到保障带宽外加超额带宽。在这里，保障带宽的算法如公式(2)所示，其中，T_cycle代表此周期的时间，N代表光网络单元的个数，T_g代表光网络单元的切换时间，r代表传输速率，以及w_j代表光网络单元的保障带宽权重(其依据用户条约而决定)。另外，超额带宽的算法如公式(3)所示，其中，B_left代表此周期的可用带宽在分配保障带宽后所剩的剩余带宽，而K为大负载(即所要求的带宽大于保障带宽)的光网络单元的集合，即K＝{R_j＞B_min_j}。

在此架构下，虽然可实现有效利用剩余带宽，然而在剩余带宽的分配上其依据光网络单元的要求带宽所占的比例分配，就这点来说，并不符合公平原则，因此可能导致购买少量带宽的用户却会因为要求较大的带宽，而可分配到大量的可传送带宽。

因此，对此有人更提出了利用流量预测的方式来事先分配多余带宽，以降低高优先权数据的等待时间，主要通过下列公式实现。

R_j＝(H_j+E_wait_j(n))+M_j+L_j    (4)

E_wait_j(n)＝A_wait_j(n-1)     (5)

从公式(4)中，可知光网络单元的要求带宽由高(H_j)、中(M_j)和低(L_j)三种优先权的带宽需求所组成，其中在高优先权的部份加入流量预测值(E_wait_j(n))，而n代表周期数。在公式(5)中，A_wait_j(n-1)代表在第n-1个周期的等待期间内到达的高优先权的实际数据量，由此可知流量预测值(E_wait_j(n))即为前一周期等待期间所到达的高优先权的带宽需求。

然而，通过这种方式虽然可降低高优先权数据的平均传输延迟，但其会导致其它优先权数据的平均传输延迟增加，并且流量预测误差会降低带宽的使用率。

所以，对于如何有效提供低传输延迟、高带宽使用率及带宽分配公平性，于是成为目前带宽分配方法极重要的研究方向。

发明内容

因此为了实现以上目的，本发明公开了一种网络带宽分配方法，其中所述网络包含一局端和连接至局端的多个终端，所述网络带宽分配方法包括下列步骤：取得终端的待传送带宽和预测带宽；根据一权值调整预测带宽；以及将待传送带宽与调整后的预测带宽相加，以得到每一终端的要求带宽，其中该要求带宽用作该局端允许该终端经由该网络上传的数据量的依据。在此，权值可随着网络的负载程度递增而递减。

本发明还公开一种网络带宽分配方法，其中此网络包含一局端和连接至局端的多个终端，此网络带宽分配方法包括下列步骤：取得至少一个终端的要求带宽；根据每一终端的要求带宽和保障带宽分配传送带宽；根据分配的传送带宽确认要求带宽；当存在未满足的要求带宽时，根据此网络的剩余带宽再分配至少一超额带宽给与未满足的要求带宽相对应的终端，以此调整分配的传送带宽；及根据终端最后的传送带宽调整每一终端的带宽补偿值。

其中，再分配超额带宽的步骤包括下列步骤：根据此网络在个一传送周期中的可用带宽和已分配的传送带宽来计算剩余带宽；根据剩余带宽以及每一该终端的最大带宽和带宽补偿值计算每一终端可分配的额外带宽；以及根据终端的未满足的要求带宽和额外带宽再分配超额带宽，以此调整终端的传送带宽。

此外，为了防止传输延迟抖动过大，预先针对每一终端而设置一最大传送带宽限制；因此，在执行根据要求带宽和保障带宽给相对应的终端分配传送带宽的步骤之前或之后，可先根据每一终端的最大传送带宽限制而调整每一终端的要求带宽。也就是当要求带宽大于最大传送带宽限制时，以最大传送带宽限制取代要求带宽，以作为进行后续步骤的要求带宽；反之，则维持原要求带宽。其中，最大传送带宽限制可设定为介于最大带宽和最大带宽的两倍之间的带宽。

在这里，通过比较每一终端的要求带宽和保障带宽，再根据比较结果而给相应的终端分配与要求带宽或与保障带宽相符合的传送带宽，其中，当要求带宽小于或等于保障带宽时，给终端分配与要求带宽相符合的传送带宽；反之，当要求带宽大于保障带宽时，则给终端分配与保障带宽相符合的传送带宽。在这里，当要求带宽大于保障带宽时，除了给相应的终端分配与保障带宽相符合的传送带宽之外，需再给此终端分配一超额带宽。

在超额带宽的分配上，先计算网络的剩余带宽，如下式所示：

$B\_{\mathrm{left}}_n=B\_{\mathrm{total}}_n-\underset{j=1}{\overset{N}{\mathrm{\Σ}}}B\_{\min }_j.$

其中，B_min_j为已分配给终端的传送带宽(即保障带宽)、B_tatal为在第n个传送周期(Cycle)中网络的可用带宽(其中n为正整数)，以及B_left为此网络到至目前为止剩余的可用带宽(即在此传送周期中网络的可用带宽在带宽初步分配后所剩的剩余带宽)；由此公式可知，剩余带宽即为网络的可用带宽扣除已分配给每一终端的传送带宽总合。

接着，根据下列公式计算未满足的每一终端可分配的额外带宽：

$B\_{\mathrm{extra}}_k=\frac{B\_{\max }_k-B\_{\mathrm{add}}_k}{\mathrm{\Σ}(B\_{\max }_k-B\_{\mathrm{add}}_k)}\×B\_{\mathrm{left}}_n,$ 且k∈K。

其中，B_max_k为终端可传送的最大带宽、B_add_k为每一终端在此传送周期之前所累积的超支带宽总和(即终端的带宽补偿值)、B_extra_k为目前可分配给终端的额外带宽，而K为相应未满足的要求带宽(即要求带宽R_j大于保障带宽B_min_j)的终端的集合，即K＝{R_j＞B_min_j}；在这里，先根据每一终端的最大带宽B_max_j和带宽补偿值B_add_k而得到每一终端可分配剩余带宽的比例，再根据得到的比例和剩余带宽B_left_n计算可分配给终端的额外带宽B_extra_k。其中，K和k均为正整数。

再根据终端的未满足的要求带宽和额外带宽再分配超额带宽，如下式所示：

且k∈K。

其中，R_eft_j为要求带宽R_j扣除已分配得的传送带宽(即保障带宽B_min_j)后所剩下的超额要求带宽，也就是，R_left_j＝R_j-B_min_j；由此公式可知，当超额要求带宽R_left_j小于或等于额外带宽B_extra_j时，给相应的终端再分配与超额要求带宽R_left_j相符合的超额带宽B_excess_j；反之，则再分配与额外带宽B_extra_j相符合的超额带宽B_excess_j。在这里，每一终端的最大带宽B_max_j和保障带宽B_min_j均可根据用户条约而决定。

最后，根据分配完成后的传送带宽的带宽超支情形来更新每一终端的带宽补偿值，也就是，将超额使用的带宽加入带宽补偿值中，并在下一传送周期中将应给而未给的带宽从带宽补偿值中扣除。其中，当传送带宽大于其最大带宽时，将超额使用的部份，即传送带宽扣除最大带宽后的超额使用带宽，加入带宽补偿值中；反之，即分配的传送带宽小于最大带宽时，则将没被分配到的部份(即最大带宽扣除传送带宽后的未使用带宽)，或者将分配完后的超额要求带宽(即要求带宽扣除传送带宽后的未使用带宽)，从带宽补偿值中扣除，根据这种方式更新每一终端的带宽补偿值。

在这里，可反复执行超额带宽的再分配，以满足大部分的要求带宽，因此在分配后会再次确认是否有未满足的要求带宽，当确认到存在有未满足的要求带宽时，则再一次进行超额带宽的再分配。此外，为了避免重复分配超额带宽的次数过多，在每次再分配超额带宽之后，可累计分配次数，并且在确认是否有未满足的要求带宽存在时，同时确认再分配次数是否达预定值；其中当确认到有未满足的要求带宽存在且再分配次数未达到预定值时，才再次进行超额带宽的再分配。

本发明还公开了一种网络带宽分配方法，其中此网络包含一局端和连接至局端的多个终端，此网络带宽分配方法包括下列步骤：从终端发出的上传信息中取得所有的要求带宽；排列发出上传信息的终端的上传顺序，以此得到一传送次序；以及根据要求带宽的大小来依序调整传送次序中每一终端的上传顺序，以得到调整后的传送次序，其中以调整后的该传送次序作为该局端依序允许该终端带宽上传的依据。

其中根据要求带宽的大小来依序调整传送次序中每一终端的上传顺序，以此得到调整后的传送次序的步骤，包括下列步骤：依序比较上传顺序相邻的两个终端的要求带宽，其中当上传顺序在后面的终端的要求带宽小于在前面的时，对两个终端的上传顺序对调，以此得到调整后的传送次序。

在这里，可通过反复执行根据要求带宽的大小来依序调整传送次序中每一终端的上传顺序，以此得到调整后的传送次序的步骤，以使每一终端的上传顺序可根据其欲上传的资料量而排列成较佳的次序。然而，为避免每一终端的上传顺序的调动距离过大，可事先设定一预定值。并且，在每次得到调整后的传送次序之后，确认调整后的传送次序与原始的传送次序是否相同；当不同时，则累计改变次数，并确认累计后的改变次数是否达预定值；当累计后的改变次数未达预定值时，再返回调整步骤，以再次依据要求带宽调整传送次序；反之，当累计后的改变次数达到预定值时，则停止传送次序的调整，随后局端会以最后获得的调整后的传送次序来依序允许各个终端上传数据

下面，结合附图和本发明的具体实施方式对本发明特征和应用做进一步的详细说明。

附图说明

图1为网络基本架构的示意图；

图2为图1所示的网络中数据上传方式的示意图；

图3为公知的传送带宽分配的示意图；

图4为根据本发明的网络带宽分配方法的一个实施方式的流程图；

图5为说明图4中权值与网络负载程度间关系的一个实施例；

图6为说明图4中权值与网络负载程度间关系的另一实施例；

图7为说明图4中权值与网络负载程度间关系的再一实施例；

图8A为根据本发明网络带宽分配方法的一个实施方式的流程图；

图8B为根据本发明网络带宽分配方法的一个实施方式的流程图；

图9A为根据本发明的网络带宽分配计算方法实施方式的流程图；

图9B为根据本发明的网络带宽分配方法的一个实施方式的流程图；

图10为根据本发明的网络带宽分配方法的一个实施方式的流程图；

图11为图10中步骤220的一个实施方式的详细流程图；

图12A为图10中步骤240的一个实施方式的详细流程图；

图12B为图10中步骤240的另一实施方式的详细流程图；

图12C为图10中步骤240的再一实施方式的详细流程图；

图13为图12A至图12C中步骤245的一个实施方式的详细流程图；

图14为图10中步骤250的一个实施方式的详细流程图；

图15A为根据本发明的网络带宽分配方法的一个实施例的流程图；

图15B为根据本发明的网络带宽分配方法的一个实施例的流程图；

图16A为图15A中步骤260的一个实施方式的详细流程图；

图16B为图15B中步骤260的一个实施方式的详细流程图；

图17为根据本发明的网络带宽分配方法的一个实施方式的流程图；

图18A为图17中步骤330的一个实施方式的详细流程图；

图18B为图17中步骤330的一个实施方式的详细流程图；

图18C为图17中步骤330的一个实施方式的详细流程图；以及

图19为根据本发明的网络带宽分配方法的一个实施方式的流程图。

具体实施方式

下面详细说明本发明的内容，并通过附图作为辅助说明。说明中提及的标号参照附图中的标号。

在例举的实施方式中，本发明可应用于一网络，并且此被动光网络包含一局端和连接到此局端的多个终端；而且这些终端和局端终分别分配有在公知技术中已知类型的硬件，以实现此网络。

举例来说，所应用的网络可为一被动光网络(passive optical network；PON)，因此在局端具有光线路终端(Optical Line Terminal；OLT)；而在每一终端则具有一光网络单元(Optical Network Unit；ONU)。在光网络单元和光线路终端中可分别设置一中央处理器(Central Processing Unit；CPU)，以控制一媒体存取控制(Media Access Control；MAC)逻辑电路的工作。其中，每一媒体存取控制逻辑电路可包含在一单一集成电路(Integrated Circuit；IC)中，例如：摩托罗拉(Motorola)公司的MPC860TZP50、RS232接口以及10BaseT接口。此外，在光网络单元和光线路终端中也可包括一网络处理器芯片，例如：英特尔(Intel)公司的IXP1200、Maker通讯公司(科胜讯(Conexant)公司)的MXT-4000系列和MXT-5000系列、Sitera公司的Prism、MMC公司的nP3400，以进行以太网络封包的处理。在这里，网络处理器芯片也可具有一媒体存取控制芯片，例如：特殊应用IC(Application Specific Integrated Circuit；ASIC)或现场可编程门阵列(Field Programmable Gate Array；FPGA)，以提供此网络的存取。并且，这些光网络单元以及此光线路终端还具有内存(例如，只读存储器(Read-Only Memory；ROM)或随机存取内存(Random-AccessMemory；RAM))以及可利用单一光纤进行双向使用的一光学收发器。虽然在这里所提的网络可使用任何类型的光学收发器，但实现方法之一可利用在一集成电路中，以波长1.3μm和波长1.55μm分别进行传送及接收的一收发器(其应用一平面光波电路(PlanarLightwave Circuit；PLC))，以及利用一向前回授电路(其应用一只读存储器)，而与一丛发的第一位非实时地工作，进而可工作在一1.25Gbps的传输速度下。然而，可在一光网络单元或一光线路终端中所使用的特定硬件并非是本发明的关键特征，也就是说，本发明可使用公知技术中的任何已知硬件。

以下所述的各种方法通常在上述媒体存取控制芯片中实现，以提供此网络的存取，此外，其也可在软件中实现，再通过中央处理器而加载并及执行，其中，此中央处理器为分离，但耦接于此网络的媒体存取控制芯片。

为达到低传输延迟、高带宽使用率以及符合带宽分配公平性的网络传送带宽分配，因此针对网络带宽分配方法提出了三个实施方式，分别为可依据上传数据量调整传送次序、可依据网络负载情况调整预测带宽分配比例，以及符合带宽分配公平性的传送带宽分配方法。

在一例举的实施方式中，其根据预测带宽的估算来改善网络传送带宽分配；在这里，可根据下述公式进行预测带宽的估算。

R_j＝Q_j+E_j×W(L)    (6)

其中，R_j代表估算的终端的要求带宽、Q_j代表终端等待传送的数据量、E_j代表预期在等待时间内到达终端的数据量(即预测带宽)、L代表在此传送周期中的网络负载程度，以及W(L)则代表根据网络负载情况而改变的权值。因此，由公式(6)可知，预测带宽的分配比例会依据当时的网络负载情况而调整。

其中，j表示要求带宽的服务路径终端的数量，也就是说要求带宽的终端数量。因此，在网络中，局端通过公式(6)而逐一估算终端的要求带宽，进而可根据估算的要求带宽，允许对应的发出上传信息的终端可经由网络上传的数据量(即传送带宽)。

换句话说，参照图4，在一传送周期中，首先取得终端的待传送带宽和预测带宽(步骤110)，接着根据一权值调整预测带宽(步骤120)，再根据公式(6)估算终端的要求带宽，也就是将待传送带宽与调整后的预测带宽相加，以得到终端的要求带宽(步骤130)。

在这里，为了减少预测带宽E_j的预测误差所造成的带宽浪费，在网络负载较轻时，可使用较大的权值W(L)；反之，在网络负载较重时，则可使用较小的权值W(L)；也就是说，权值W(L)随着网络负载程度L的递增而递减。其中，权值W(L)与网络负载程度L之间的关系可如图5、图6和图7所示，在网络负载较重时，不会发生带宽的浪费，而在网络负载较轻时，又可得到预测带宽所产生的缩短平均传输延迟的优点。另外，在这里预测带宽可以为每一终端在前一传送周期中的传送带宽，即在前一传送周期中上传的数据量

换句话说，在步骤120中的权值，可用于计算网络的负载程度(步骤140)，再根据计算出的负载程度获得权值(步骤150)；其中，此权值可在步骤110之前先行取得，也可在步骤120之前再取得，分别如图8A和图8B所示。

在这里，为了方便说明，仅以一次估算进行说明，然而事实上，可根据此实施方式通过反复执行上述步骤，来估算出发出上传信息的每一终端的要求带宽，如图9A所示；或者也可先获取发出上传信息的每一终端的待传送带宽和预测带宽，再通过反复执行步骤120至步骤130，以估算出发出上传信息的每一终端的要求带宽，如图9B所示。

另外，是根据传送带宽分配来改善网络传送带宽分配，参照图10，先获取发出上传信息的终端中至少一个终端的要求带宽(步骤210)，获取后，根据所获取的要求带宽计算分配给与要求带宽相对应的终端的传送带宽，在这里，传送带宽为允许对应的终端经由网络上传的数据量。在这里，每一终端具有一可用带宽范围，此可用带宽范围介于一保障带宽和一最大带宽之间。

在获得要求带宽之后，先进行初步的带宽分配，即根据每一终端的要求带宽和保障带宽将此周期的可用带宽分配给各个终端，即逐一分配各个终端的传送带宽(步骤220)。在这里，通过比较每一终端的要求带宽和保障带宽(步骤221)，再根据比较结果给相应的终端分配与要求带宽或保障带宽相符合的传送带宽，其中，当要求带宽小于或等于保障带宽时，分配给此终端的传送带宽即为此终端的要求带宽(步骤223)，反之，当要求带宽大于保障带宽时，分配给此终端的传送带宽则为此终端的保障带宽(步骤225)，如图11所示。并且，可通过反复执行上述步骤(即步骤221以及步骤223或步骤225)而实现发出上传信息的每一终端的传送带宽的初步分配。

在这里，当要求带宽大于保障带宽时，除了给相应的终端分配与保障带宽相符合的传送带宽，需要给此终端再分配一超额带宽；因此，在进行初步的带宽分配(即步骤220)之后，会逐一确认是否有未满足的要求带宽(步骤230)，当确认到存在未满足的要求带宽时，则将剩余带宽再分配给与未满足的要求带宽相对应的各个终端，即给与未满足的要求带宽相对应的各个终端再分配一超额带宽，以得到每一终端再分配后的传送带宽(步骤240)，如图10所示。换句话说，在步骤230比较分配的传送带宽和要求带宽，当要求带宽大于分配之传送带宽时，则存在未满足的要求带宽。其中，此剩余带宽为初步的带宽分配后，此周期的可用带宽扣除分配的传送带宽后所剩余的部分(即剩余的带宽量)。

也就是说，先依据保障带宽和要求带宽将此周期的可用带宽分配给各个终端，如下述公式所示。

公式(7)为传送带宽分配的基本方法，其中，R_j为要求带宽，B_min_j表示保障带宽，B_excess_j代表将剩余带宽再分配的超额带宽，以及B_grant_j代表实际分配给到终端的带宽(即传送带宽)。在公式(7)中，当要求带宽R_j小或等于保障带宽B_min_j时，此终端即可分配到其所要求的带宽(即要求带宽R_j)；反之，则可分配到保障带宽B_min_j外加超额带宽B_excess_j。

与公知技术相比，在超额带宽的计算上，根据本发明的一种实施方式，为根据与未满足的要求带宽相对应的各个终端的最大带宽和带宽补偿值而计算。因此，在步骤240中，先根据在此传送周期中网络的可用带宽和已分配的传送带宽来进行剩余带宽的计算(步骤241)，接着，根据剩余带宽以及每一终端(未满足其要求带宽的)的最大带宽和带宽补偿值逐一计算每一终端可分配的额外带宽(步骤243)，最后逐一根据每一终端的未满足的要求带宽和额外带宽再分配超额带宽，以调整与未满足的要求带宽相对应的这些终端的传送带宽(步骤245)，如图12A所示。

在这里，为了方便说明，仅以超额带宽的一次分配进行说明，然而事实上，根据本发明的实施方式，在分配后会再次逐一确认是否有未满足的要求带宽(步骤246)，当确认到存在有未满足的要求带宽时，可通过执行上述步骤(即步骤241、步骤243和步骤245)而再一次分配超额带宽，如图12B所示；此外，为了避免重复分配超额带宽的次数过多，在每次分配超额带宽(步骤245)之后，可累计分配次数(步骤247)，并且在确认是否有未满足的要求带宽时，同时确认再分配次数是否达预定值(步骤249)，当确认到存在有未满足的要求带宽且再分配次数未达到预定值时，再重复进行步骤241、步骤243和步骤245，以再次进行超额带宽的分配，如图12C所示。

简单来说，这里的超额带宽的分配方法如下列公式所示。

$B\_{\mathrm{left}}_n=B\_{\mathrm{total}}_n-\underset{j=1}{\overset{N}{\mathrm{\Σ}}}B\_{\min }_j---\left(8\right)$

$B\_{\mathrm{extra}}_k=\frac{B\_{\max }_k-B\_{\mathrm{add}}_k}{\mathrm{\Σ}(B\_{\max }_k-B\_{\mathrm{add}}_k)}\×B\_{\mathrm{left}}_n,$ 且k∈K    (9)

且k∈K    (10)

在这里，公式(8)为计算剩余带宽的方法，其中，B_min_j为已分配给终端的传送带宽(即保障带宽)、B_tatal为在第n个传送周期(Cycle)中网络的可用带宽(其中n为正整数)，以及B_left为此网络至目前为止剩余之可用带宽(即在此传送周期中网络的可用带宽在带宽初步分配后所剩下的剩余带宽)；由公式(8)可知，剩余带宽即为网络的可用带宽扣除已分配给每一终端的传送带宽总合。

公式(9)为计算额外带宽的方法，其中，B_max_k为终端可传送的最大带宽、B_add_k为每一终端在此传送周期之前所累积的超支带宽总和(即终端的带宽补偿值)、B_extra_k为目前可分配给终端的额外带宽，而K为与未满足的要求带宽(即要求带宽R_j大于保障带宽B_min_j)相对应的终端的集合，即K＝{R_j＞B_min_j}；在公式(9)中，先根据每一终端的最大带宽B_max_j和带宽补偿值B_add_k而得到每一终端可分配剩余带宽的比例，再根据得到的比例和剩余带宽B_left_n计算可分配给终端的额外带宽B_extra_k。这里的剩余带宽即通过公式(8)得到。其中K和k均为正整数。

公式(10)为分配超额带宽的方法，其中，R_lefi_j为要求带宽R_j扣除已分配的传送带宽(即保障带宽B_min_j)后所剩下的超额要求带宽，也就是，R_left_j＝R_j-B_min_j；由公式(10)可知，当超额要求带宽R_left_j小于或等于通过公式(9)得到的额外带宽B_extra_j时，给相应的终端再分配与超额要求带宽R_left_j相符和的超额带宽B_excess_j；反之，则再分配与额外带宽B_extra_j相符和的超额带宽B_excess_j。在这里，每一终端的最大带宽B_max_j和保障带宽B_min_j均可根据用户合约而决定。

换句话说，在步骤245中，先根据要求带宽和已分配的传送带宽计算超额要求带宽(步骤2451)，接着比较超额要求带宽和额外带宽(步骤2453)，其中当超额要求带宽小于或等于额外带宽时，给此终端再分配与超额要求带宽相符和的超额带宽(步骤2455)；反之，则给此终端再分配与额外带宽相符和的超额带宽(步骤2457)，如图13所示。并且，可通过反复执行上述步骤(即步骤2451、步骤2453以及步骤2455或步骤2457)而逐一给所有相应的未满足的终端再分配超额带宽。

在调整与未满足的要求带宽相对应的终端的传送带宽之后，再根据传送带宽和最大带宽调整每一终端的带宽补偿值(步骤250)，如图10所示。

在步骤250中主要根据分配完成后传送带宽的带宽超支情况而更新带宽补偿值，也就是，将超额使用的带宽加入带宽补偿值中，并在下一传送周期将应给而未给的带宽从带宽补偿值中扣除。参照图14，在步骤250，可通过比较每一终端最后的传送带宽和最大带宽(步骤251)，并当此传送带宽大于其最大带宽时，将超额使用的部份，即传送带宽扣除最大带宽后的超额使用带宽，加入带宽补偿值(步骤253)，以此更新带宽补偿值(步骤257)；反之，即要求带宽小于最大带宽(也可以是分配的传送带宽小于最大带宽)时，则将没被分配到的部份(即最大带宽扣除传送带宽后的未使用带宽)，或者将分配完后的超额要求带宽(即要求带宽扣除传送带宽后的未使用带宽)，从带宽补偿值中扣除(步骤255)，以此更新带宽补偿值(步骤257)。同样地，可通过反复执行上述步骤(即步骤251、步骤253/步骤255以及步骤257)而逐一更新每一终端的带宽补偿值。

此外，为了防止传输延迟抖动过大，预先针对每一终端设置一最大传送带宽限制，即每一终端在一个传送周期中具有一最大传送带宽限制；因此，在进行初步的带宽分配(即步骤220)之前或之后，可先根据每一终端的最大传送带宽限制调整每一终端的要求带宽(步骤260)，如图15A、图15B所示。

参照图16A、图16B，这里(即步骤260)的调整方式为逐一比较每一终端的最大传送带宽限制和要求带宽(步骤261)，并且在要求带宽大于最大传送带宽限制时，以最大传送带宽限制取代要求带宽，作为进行后续步骤的要求带宽(步骤263)；反之，则维持原要求带宽(即不以最大传送带宽限制取代要求带宽)(步骤265)，如下列公式所示。

在公式(11)中，R_j′为调整后的要求带宽、R_j为原要求带宽，以及B_bound_j为终端的最大传送带宽限制。在这里，最大传送带宽限制可设定为介于最大带宽和最大带宽的两倍之间的带宽。

由上述可知，根据本发明的传送带宽分配方法，当终端所要求的带宽(即上述要求带宽)小于或等于保障带宽时，直接配给其要求带宽，反之如果所要求带宽大于保障带宽，则等所有终端分配完保障带宽(或要求带宽)后，计算网络的剩余带宽，并将此剩余带宽根据由所有未完成分配的终端的最大带宽扣除历来超支带宽(即带宽补偿值)后的值所占的比重来分配。也就是，终端最大带宽愈大，可分配到的带宽愈多，并且终端超支情形愈严重可分配到的带宽愈少，由于最大带宽大多根据用户合约而设定，因此此分配方式可实现根据用户重要性及带宽超额使用情况来决定剩余带宽的分配，以使网络的可用带宽可较公平地分配到各个终端。其中，通过最大传送带宽限制的设定，可使超支带宽(即带宽补偿值)被限制在最大带宽以内，因此当最大带宽扣除历来超支带宽(即带宽补偿值)后为零时，此终端无法参与剩余带宽的分配，如此一来即可有效限制用户可用的传送带宽，进而符合带宽分配的公平性。

另外，是针对上传次序来改善网络传送带宽分配，主要依据终端的上传数据量调整传送次序，而此传送次序为局端以此允许发出上传信息的终端上传数据的顺序。在这里，每一终端在经由网络上传数据到局端之前，会先发出一上传信息来通知局端，其中此上传信息具有一要求带宽，以告知局端其欲上传的数据量。而后，参照图17，局端会先从上传信息中获取所有发出上传信息的终端的要求带宽(步骤310)，接着，排列发出上传信息的终端的上传顺序，由此得到一传送次序(步骤320)，然后根据要求带宽的大小来依序调整传送次序中每一终端的上传顺序，由此得到调整后的传送次序(步骤330)，因此局端即可根据调整后的传送次序依序允许各个终端上传数据。

步骤330中的调整方式，为比较上传顺序相邻的两个终端的要求带宽(步骤331)，并且当上传顺序靠后的终端的要求带宽小于上传顺序靠前的终端的要求带宽时，将两终端的上传顺序对调(步骤333)，反之，则维持原上传顺序(步骤335)，以此得到调整后的传送次序，如图18A所示。其中，可通过反复执行上述步骤，而依序调整每一终端的上传顺序，直至完成所有终端的上传顺序的调整。

举例来说，在一个实施方式中，参照图18B，假设共有j个终端发出上传信息(即最终的上传顺序为j)，并且当步骤331执行第N-2上传顺序与第N-1上传顺序的终端的要求带宽的相比较(步骤431)(其中，N≤j)时，若第N-1上传顺序的终端的要求带宽小于第N-2上传顺序的终端的要求带宽，那么两终端的上传顺序将会对调(步骤333)，也就是原第N-2上传顺序的终端的上传顺序会改变成第N-1上传顺序，而原第N-1上传顺序的终端的上传顺序会改变成第N-2上传顺序；反之，若第N-1上传顺序的终端的要求带宽不小于第N-2上传顺序的终端的要求带宽，那么两终端的上传顺序则不会对调(步骤335)。接着，在执行对调时，确认第N+1上传顺序是否为最终的上传顺序(即确认N+1是否等于j)(步骤437)，若不是最终的上传顺序(即N+1≠j)时，则接续比较第N上传顺序和第N+1上传顺序的终端的要求带宽；反之(即N+1＝j)(步骤441)，则不继续比较。此外，当无执行对调时，则确认第N上传顺序是否为最终的上传顺序(即确认N是否等于j)(步骤439)，若不是最终的上传顺序(即N＝-j)时，则接续比较第N-1上传顺序和第N上传顺序的终端的要求带宽(步骤443)；反之(即N＝j)，则不继续比较。

此外，也可在步骤333或步骤335之后，均进行第N+1上传顺序是否为最终上传顺序的确认(即确认N+1是否等于j)(步骤437)，若不是最终上传顺序(即N+1≠j)时，则接续比较第N上传顺序和第N+1上传顺序的终端的要求带宽(步骤439)；反之(即N+1＝j)，则不接续比较，如图18C所示。

在这里，为了方便说明，仅以传送次序的一次调整进行说明，然而事实上，根据本发明的实施方式，可反复执行步骤330，以使每一终端的上传顺序可依据其欲上传的数据量而排列成较佳的次序。然而为了避免每一终端的上传顺序的调动距离过大，可事先设定一预定值。并且，在得到调整后的传送次序之后(即步骤330)，确认调整后的传送次序与原始的传送次序是否相同(步骤350)；当不同时，累计改变次数(步骤360)，并确认累计后的改变次数是否达到预定值(步骤370)；当累计后的改变次数未达到预定值时，再返回执行步骤330，以再次依据要求带宽调整传送次序；反之，当累计后的改变次数达到预定值时，则停止传送次序的调整，随后局端会以最后得到的调整后的传送次序来依序允许各个终端上传数据，如图19所示。

综合上述，与公知的相关方法相比，本发明提出了一种网络带宽分配方法，可依据终端的上传数据量调整传送次序。此外，本发明还提出一种网络带宽分配方法，可依据网络负载情形调整预测带宽分配比例，进而有效地降低平均传输延迟。另外，根据本发明的网络带宽分配方法，还可提高带宽的使用率。此外，本发明更提出一种网络带宽分配方法，可提高带宽分配公平性及降低的传输延迟抖动情形。

此外，根据本发明所提出的多个实施方式，可在网络中任意搭配使用，也可在网络中单独使用，以提升数据上传的效率。

虽然如上所述公开了本发明的优选实施方式，然而其并非用于限定本发明，对于本领域的普通技术人员，在不脱离本发明的精神和范围的前提下，可以对于本发明做出各种变形和改进，因此本发明的保护范围必须通过本发明所附的权利要求及其等同物所限定。

Claims (12)

1.一种网络带宽分配方法，所述网络包含一局端和连接至所述局端的多个终端，其特征在于，所述方法包括下列步骤：

在一传送周期中，取得至少一所述终端的一待传送带宽和一预测带宽，所述待传送带宽为终端等待传送的数据量，所述预测带宽为预期在等待时间内到达终端的数据量；

根据一权值调整所述预测带宽；以及

将所述待传送带宽与调整后的所述预测带宽相加，以得到所述终端的一要求带宽，其中所述要求带宽用作所述局端允许所述终端经由所述网络上传的数据量的依据，所述要求带宽为估算的终端的要求带宽。

2.根据权利要求1所述的网络带宽分配方法，其特征在于，在取得至少一所述终端的一待传送带宽和一预测带宽的所述步骤之前和之后中之一，还包括下列步骤：

计算在所述传送周期中所述网络的一负载程度；以及

根据所述负载程度取得一权值。

3.根据权利要求2所述的网络带宽分配方法，其特征在于，所述权值随着所述负载程度递增而递减。

4.根据权利要求1所述的网络带宽分配方法，其特征在于，每一所述终端的所述预测带宽为所述终端在前一所述传送周期中上传的所述数据的量。

5.一种网络带宽分配方法，其特征在于，所述网络包含有一局端和连接到所述局端的多个终端，所述网络带宽分配方法包括下列步骤：

取得至少一个所述终端的至少一个要求带宽，所述要求带宽为终端所要求的带宽；

根据每一所述终端的所述要求带宽和一保障带宽分配一传送带宽；

根据分配的所述传送带宽确认所述要求带宽；

当存在未满足的所述要求带宽时，根据所述网络的一剩余带宽再分配至少一超额带宽给与未满足的所述要求带宽相对应的所述终端，以此调整分配的所述传送带宽，包括下列步骤：

根据所述网络在一传送周期中的一可用带宽以及已分配的所述传送带宽来计算所述剩余带宽；

根据所述剩余带宽以及每一所述终端的一最大带宽和一带宽补偿值计算每一所述终端可分配的一额外带宽；以及

根据未满足的所述要求带宽和所述额外带宽再分配所述超额带宽，以此调整所述终端的所述传送带宽；以及

根据所述终端最后的所述传送带宽调整每一所述终端的所述带宽补偿值；

其中，所述根据每一所述终端的所述要求带宽和一保障带宽分配一传送带宽的步骤包括下列步骤：

比较所述终端的所述要求带宽和所述保障带宽；

当所述要求带宽大于所述保障带宽时，分配与所述保障带宽相符合的所述传送带宽；以及

当所述要求带宽不大于所述保障带宽时，分配与所述要求带宽相符合的所述传送带宽；

所述根据分配的所述传送带宽确认所述要求带宽的步骤包括下列步骤：比较所述终端的所述要求带宽和分配的所述传送带宽，其中当所述要求带宽大于分配的所述传送带宽时，所述要求带宽为未满足；

所述剩余带宽的计算为从所述可用带宽中扣除已分配的所述传送带宽；

所述根据未满足的所述要求带宽和所述额外带宽再分配所述超额带宽，据以调整所述终端的所述传送带宽的步骤包括下列步骤：

根据所述要求带宽和分配的所述传送带宽计算所述终端的一超额要求带宽；

比较所述终端的所述超额要求带宽和所述额外带宽；

当所述超额要求带宽大于所述额外带宽时，再给所述终端分配与所述额外带宽相符合的所述超额带宽，由此调整所述终端的所述传送带宽；以及

当所述超额要求带宽不大于所述额外带宽时，给所述终端分配与所述超额要求带宽相符合的所述超额带宽，由此调整所述终端的所述传送带宽；

所述根据所述终端最后的所述传送带宽调整每一所述终端的所述带宽补偿值的步骤包括下列步骤：

比较所述终端最后的所述传送带宽和所述最大带宽；

当最后的所述传送带宽大于所述最大带宽时，将分配的所述传送带宽减去所述最大带宽，以得到一超额使用的部份；

当所述传送带宽小于所述最大带宽时，将所述传送带宽减去所述最大带宽，以得到一未使用带宽；以及

根据所述超额使用的部份和所述未使用带宽中之一更新所述带宽补偿值；

其中，在所述根据所述剩余带宽以及每一所述终端的一最大带宽和一带宽补偿值计算每一所述终端可分配的一额外带宽的步骤包括下列步骤：根据下述公式计算与未满足的所述要求带宽相对应的每一所述终端的所述额外带宽：

$B\_{\mathrm{extra}}_k=\frac{B\_{\max }_k-B\_{\mathrm{add}}_k}{\mathrm{\Σ}(B\_{\max }_k-{B\_\mathrm{add}}_k)}\×{B\_\mathrm{left}}_n,$ 且k∈K；

其中，B_extra_k代表所述额外带宽；B_max_k代表所述最大带宽；B_add_k代表所述带宽补偿值；B_left_n代表所述剩余带宽；K为与未满足的所述要求带宽相对应的所述终端的集合；k代表K中的所述终端；以及n代表第n个传送周期，其中K、k和n分别为一正整数；

所述超额要求带宽为所述要求带宽扣除分配的所述传送带宽。

6.根据权利要求5所述的网络带宽分配方法，其特征在于，在所述根据每一所述终端的所述要求带宽和一保障带宽分配一传送带宽的步骤之前和之后中之一，还包括下列步骤：

根据在所述传送周期中每一所述终端的一最大传送带宽限制调整所述终端的所述要求带宽。

7.根据权利要求6所述的网络带宽分配方法，其特征在于，所述根据在所述传送周期中每一所述终端的一最大传送带宽限制调整所述终端的所述要求带宽的步骤包括下列步骤：

比较每一所述终端的所述最大传送带宽限制和所述要求带宽，其中当所述要求带宽大于所述最大传送带宽限制时，利用所述最大传送带宽限制取代所述要求带宽作为所述终端的所述要求带宽。

8.根据权利要求6所述的网络带宽分配方法，其特征在于，所述最大传送带宽限制的范围介于所述最大带宽和所述最大带宽的两倍之间。

9.根据权利要求5所述的网络带宽分配方法，其特征在于，所述根据所述终端最后的所述传送带宽调整每一所述终端的所述带宽补偿值的步骤包括下列步骤：

比较所述终端最后的所述传送带宽、所述最大带宽和所述要求带宽；

当最后的所述传送带宽大于所述最大带宽时，将分配的所述传送带宽减去所述最大带宽，以得到一超额使用的部份；

当所述传送带宽小于所述最大带宽且大于所述要求带宽时，将所述传送带宽减去所述最大带宽，以得到一未使用带宽；

当所述传送带宽小于所述最大带宽且小于所述要求带宽时，将所述要求带宽减去所述传送带宽，以得到一超额要求带宽；以及

根据所述超额使用的部份、所述未使用带宽和所述超额要求带宽中之一更新所述带宽补偿值。

10.一种网络带宽分配方法，其特征在于，所述网络包含一局端和连接到所述局端的多个终端，所述网络带宽分配方法用于在根据所述终端的多个要求带宽分配一传送带宽后，再分配所述被动光网络的一剩余带宽给与一超额要求带宽相对应的所述终端，其中所述超额要求带宽为所述传送带宽未满足所述要求带宽的部分，所述方法包括下列步骤：

分配至少一个传送带宽；

根据所述网络在一个传送周期中的一可用带宽和已分配的所述传送带宽计算所述网络的一剩余带宽；

根据所述剩余带宽以及每一所述终端的一最大带宽和一带宽补偿值计算与所述超额要求带宽相对应的所述终端可分配的至少一个额外带宽；以及

根据所述超额要求带宽和所述额外带宽再分配所述超额带宽，以此调整所述终端的所述传送带宽；

其中，所述要求带宽为终端所要求的带宽；所述剩余带宽的计算为将所述可用带宽减去已分配的所述传送带宽；

所述根据所述剩余带宽以及每一所述终端的一最大带宽和一带宽补偿值计算与所述超额要求带宽相对应的所述终端可分配的至少一额外带宽的步骤包括下列步骤：根据下列公式计算相应所述超额要求带宽的所述终端可分配的所述额外带宽：

$B\_{\mathrm{extra}}_k=\frac{B\_{\max }_k-B\_{\mathrm{add}}_k}{\mathrm{\Σ}(B\_{\max }_k-{B\_\mathrm{add}}_k)}\×{B\_\mathrm{left}}_n,$ 且k∈K；

其中，B_extra_k代表所述额外带宽；B_max_k代表所述最大带宽；B_add_k代表所述带宽补偿值；B_left_n代表所述剩余带宽；K为与未满足的所述要求带宽相对应的所述终端的集合；k代表在K中的所述终端；以及n代表第n个传送周期，并且K、k和n分别为一正整数；

所述根据所述超额要求带宽和所述额外带宽再分配所述超额带宽，以此调整所述终端的所述传送带宽的步骤，包括有下列步骤：

比较所述终端的所述超额要求带宽和所述额外带宽；

当所述超额要求带宽大于所述额外带宽时，给所述终端再分配与所述额外带宽相符合的所述超额带宽，以此调整所述终端的所述传送带宽；以及

当所述超额要求带宽不大于所述额外带宽时，给所述终端分配与所述超额要求带宽相符合的所述超额带宽，以此调整所述终端的所述传送带宽。

11.根据权利要求10所述的网络带宽分配方法，其特征在于，在所述根据所述超额要求带宽和所述额外带宽再分配所述超额带宽，以此调整所述终端的所述传送带宽的步骤之后，还包括下列步骤：

根据分配的所述传送带宽和所述要求带宽确认所述超额要求带宽；以及

当有所述超额要求带宽存在时，返回并继续执行根据所述可用带宽和已分配的所述传送带宽计算所述剩余带宽的步骤。

12.根据权利要求11所述的网络带宽分配方法，其特征在于，在所述根据所述超额要求带宽和所述额外带宽再分配所述超额带宽，以此调整所述终端的所述传送带宽的步骤之后，还包括有下列步骤：

累计一分配次数；

根据分配的所述传送带宽和所述要求带宽确认所述超额要求带宽，并根据一预定值确认一所述累计分配次数；及

当所述超额要求带宽存在且所述分配次数未达所述预定值时，返回并连续执行根据所述可用带宽和已分配的所述传送带宽计算所述剩余带宽的步骤。

Images