一种提高光突发交换网络公平性的波长调度方法转让专利
申请号 : CN200410080250.7
文献号 : CN100586224C
文献日 : 2010-01-27
发明人 : 纪越峰 , 胡轶群
申请人 : 北京邮电大学
摘要 :
本发明公开了一种提高光突发交换网络公平性的波长调度方法。在JET协议下，随着突发包经过的节点数增多，偏置时间不断减小，丢包的概率也加大。这种情况将极大的影响网络的公平性和信道利用率。本发明的波长调度方法，把突发包所预留的网络资源总量作为它的权重，权重大的突发包可以抢占权重较小的包预留的波长资源，这样有效地解决了公平性问题。在负荷为0.6时，采用该调度方法后，最长路由和最短路由的两种突发包的全网丢包率之间的比值从原来的1700下降到2。另外，由于选择了合适的权重方法，还降低了考虑突发包长度的加权全网丢包率。
权利要求 :
1、一种提高光突发交换网络公平性的波长调度方法，包括下列步骤：
A.接收到新来的突发包，使用LAUC-VF方案，为其调度波长资源；
B.如果找到了空闲的波长，那么调度成功，方法终止；否则，转到步骤C；
C.计算每个波长的权重Mi，i代表第i个波长，并计算最小值Mmin＝min(Mi)，i＝1，2，...， K，K为波长数目；
D.计算新来的突发包的权重值Marrival；
E.比较Mmin和Marrival；如果Marrival＜Mmin，那么调度失败，丢弃该突发包，方法终止； 否则，转到步骤F；
F.相应波长上的冲突的突发包预留的波长资源将会被新来的突发包抢占，并向下游节点 发送拆链消息。
在步骤C和步骤D中，突发包的权重值计算方法如下：对于一个在OBS网络中传播的突 发包，假设它已经经过的跳数为h，突发包长度为l，如果它在当前节点预留波长资源成 功的话，那么它所预留的网络资源总量表示为(h+1)×l，即该突发包的权重。
2、根据权利要求1所述的提高光突发交换网络公平性的波长调度方法，其特征在于：如果某 个波长上存在多个冲突包时，用多个冲突包的权重之和来表示该波长上的权重。
3、根据权利要求1所述的提高光突发交换网络公平性的波长调度方法，其特征在于：当下游 节点收到拆链包时，如果找到相应的预留波长资源的话，清除相应的预留波长资源，并且 向该下游节点的下游节点继续发送拆链包；如果没有找到相应的预留记录的话，这说明突 发包已经被丢弃或者拆除，此时销毁拆链包即可。
说明书 :
技术领域
本发明涉及光通信网络，尤其涉及光突发交换网络的波长调度方法。
背景技术
随着IP数据业务的快速增长，IP over WDM(波分复用)作为未来IP 网络的核心技术日趋明显。当前以WDM为基础的光突发交换(OBS)技术是 最有前途的技术之一。光突发交换中，使用的带宽粒度介于光电路交换和 光分组交换之间，比光线路交换灵活，带宽利用率高，又比光分组交换更 贴近实用。可以说，它结合了两者的优点且克服了两者的部分缺点，是两 者之间的平衡选择，因而逐渐引起了众多学者的重视。
在OBS中，OBS边缘路由器把来自传统路由器的IP包组装成被称为突 发(Burst)的超长IP包，对应于每一个突发，形成一个突发控制分组(BCP)， 以携带该突发的交换控制信息，如目的地址等。形成数据突发的目的是为 了增大交换的颗粒。
在标准的恰量时间协议(简称JET协议：Just Enough Time)方案下， 带宽申请过程是单向的。信源发出预留资源的控制包，信源在等待了一个 初始偏置时间后，不等应答信息到来就可发送数据。数据突发与控制分组 在不同的物理信道上传输，数据突发以直通的方式通过OBS交换网络，控 制分组在每个节点经过光/电(O/E)转换、处理和电/光(E/O)转换，完 成对数据突发的控制处理。因此在每个中间节点上，都要将偏置时间减小， 即去除控制包的处理和等待时间。
在标准JET协议中，突发包的偏置时间越大，该突发包丢包的概率越 小。随着突发包在多跳网络中经过的跳数不断增加，它们的剩余偏置时间 将不断减小。这样相当于降低了这些包的优先级，使得它们相对于刚开始 传送的包，更容易被阻塞。因此长路由的包的丢包率将大于短路由的包， 影响了整个网络的公平性。而且，由于那些经过了多跳的包没能到达终点， 它们已经预留的那些网络资源也就浪费。
在OBS中，OBS边缘路由器把来自传统路由器的IP包组装成被称为突 发(Burst)的超长IP包，对应于每一个突发，形成一个突发控制分组(BCP)， 以携带该突发的交换控制信息，如目的地址等。形成数据突发的目的是为 了增大交换的颗粒。
在标准的恰量时间协议(简称JET协议：Just Enough Time)方案下， 带宽申请过程是单向的。信源发出预留资源的控制包，信源在等待了一个 初始偏置时间后，不等应答信息到来就可发送数据。数据突发与控制分组 在不同的物理信道上传输，数据突发以直通的方式通过OBS交换网络，控 制分组在每个节点经过光/电(O/E)转换、处理和电/光(E/O)转换，完 成对数据突发的控制处理。因此在每个中间节点上，都要将偏置时间减小， 即去除控制包的处理和等待时间。
在标准JET协议中，突发包的偏置时间越大，该突发包丢包的概率越 小。随着突发包在多跳网络中经过的跳数不断增加，它们的剩余偏置时间 将不断减小。这样相当于降低了这些包的优先级，使得它们相对于刚开始 传送的包，更容易被阻塞。因此长路由的包的丢包率将大于短路由的包， 影响了整个网络的公平性。而且，由于那些经过了多跳的包没能到达终点， 它们已经预留的那些网络资源也就浪费。
发明内容
本发明的目的在于避免上述不足，提供一种全新的波长调度方法，通 过给经过多跳的包增加适当的权重，使得它可以抢占权重较小的包预留的 波长资源，这样有效地解决了公平性问题。另外，由于选择了合适的权重 方法，还降低了考虑突发包长度的加权全网端到端丢包率。
本发明的目的采用以下技术方案来实现：
在本发明中，计算的是考虑突发包长度的全网端到端丢包率。全网端 到端丢包率描述的是网络中的全部丢包与网络中全部发出的包之间的关 系。另外，在OBS中，每个突发包都是由大量的IP包组成的。因为最终关 心的还是IP包的丢包率，而且在本发明中不涉及OBS网络中的汇聚过程， 因此本方法用考虑突发包长度的加权全网丢包率来尽可能反映IP包的丢包 率。这里，用整个网络中所有丢包的包长之和与所有发出的包的包长之和 的比值来计算考虑突发包长度的加权全网端到端丢包率。
本发明方法包括以下步骤：
A.接收到新来的突发包，使用可插空最迟可用未占用信道(简称 LAUC-VF：latest available unused channel with void filling) 方法，为其调度波长资源。
B.如果找到了空闲的波长，那么调度成功，方法终止。否则，转到步 骤C。
C.计算每个波长的权重Mi，i代表第i个波长，并计算最小值 Mmin＝min(Mi)，i＝1，2，...，K，K为波长数目。
D.计算新来的突发包的权重值Marrival。
E.比较Mmin和Marrival。如果Marrival＜Mmin，那么调度失败，丢弃该突发包， 方法终止。否则，转到步骤F。
F.相应波长上的冲突的突发包预留的资源将会被新来的突发包抢占， 并向下游节点发送拆链消息。
本方法用突发包已经预留的网络资源总量来作为突发包的权重。对于 一个在OBS网络中传播的突发包，假设它已经经过的跳数为h，突发包长 度为l。如果它在当前节点预留波长资源成功的话，那么它所预留的网络资 源总量可以表示为(h+1)×l。本方法把它作为该突发包的权重。这样，突发 包越长，经过的跳数越多，它的权重就越大，越容易抢占别的突发包的资 源，也就越不容易丢包。
由于采用了上述技术方案，本发明具有以下优点和效果：
本发明的权重计算方法可以精确的反映丢弃一个突发包所要付出的代 价。巧妙的把经过的条数和突发包长度结合在一起，可以同时改善网络的 公平性和信道利用率。原因如下：
由于权重方法中考虑了经过的跳数，可以有效的缩小路由长度不同 的突发包之间的丢包率差异，从而改善网络公平性。
普通的JET协议下，如果那些经过了多跳的包发生丢包，这些突发 包已经预留的那些网络资源也就浪费。采用突发包所预留的网络资 源总量作为权重的方法，可以有效的降低这种情况发生的概率，从 而进一步降低了全网端到端丢包率。
另外，这种权重方法考虑了包长。这相当于给大的突发包更高一些 的优先级，从而使得这些大突发包不容易丢包。大的突发包中包含 的IP包的数目也更多，这样就可以有效地降低基于IP包的丢包率。
另外，在计算波长的权重时，如果在某个波长上存在多个冲突包，用 多个包的权重之和来表示该波长上的权重。之所以采用求和的方法，是因 为本权重方法是用预留的网络资源总量来衡量的，这样必然要用各个包预 留的网络资源总量之和来表示多个包的权重。这种权重计算方法可以精确 的反映丢弃多个突发包所要付出的代价。
下面通过仿真一个7×7网孔型mesh-torus网络，来比较本发明的方 法和标准JET的性能：
每条链路包含两根光纤，分别用于两个方向上。每根光纤上有8个波 长，波长上的速率是10Gbps。每个节点有一个本地源，负责产生突发包。 突发包的生成服从泊松过程。突发包长度为负指数分布，平均长度为50, 000字节(在10G链路上，相当于40μs)。每个节点上的突发包的目的地 址随机分布于网络中的其他节点上。采用最短路径方法计算网络中两点之 间的静态路由。控制包的处理时间是100μs。偏置时间为1000μs。
参照图2，给出了在两种不同调度方法下，加权全网丢包率和负荷之 间的关系。从图中可以看出本调度方法所取得的性能要比标准JET的好。
参照图3，给出了标准JET协议下，全网中不同的路由长度的突发包 的加权丢包率和负荷之间的关系。H为突发包的路由长度。H＝i(i＝1，2， 3，4，5，6)表示该突发包的路由长度为i。从图中可以看出对于标准JET 协议，路由长度越长，丢包率就越高。这与前面的理论分析相符合。在负 荷为0.6时，路由长度为6的突发包与路由长度为1的突发包的丢包率之 间的比值为1700。随着负荷增加，该比值不断减小。负荷为0.9时，该比 值下降为240。该结果表明在不加任何改进措施的标准JET协议下，OBS网 络的公平性是很差的。
参照图4，给出了在改进的调度方法下，全网中不同的路由长度的突 发包的加权丢包率和负荷之间的关系。从图中可以看出路由长度为2，3， 4，5，6的突发包的加权丢包率基本上相等，路由长度为1的突发包的丢 包率要比前面三者略低，但差别不大。在负荷为0.3时，路由长度为6的 突发包与路由长度为1的突发包的丢包率之间的比值为2.6。负荷为0.6 和0.9时，该比值分别为2和1.6。结合图3和图4的仿真结果，可以看 出，采用改进的调度方法后，OBS网络的公平性有了很大的提高。
本发明的目的采用以下技术方案来实现：
在本发明中，计算的是考虑突发包长度的全网端到端丢包率。全网端 到端丢包率描述的是网络中的全部丢包与网络中全部发出的包之间的关 系。另外，在OBS中，每个突发包都是由大量的IP包组成的。因为最终关 心的还是IP包的丢包率，而且在本发明中不涉及OBS网络中的汇聚过程， 因此本方法用考虑突发包长度的加权全网丢包率来尽可能反映IP包的丢包 率。这里，用整个网络中所有丢包的包长之和与所有发出的包的包长之和 的比值来计算考虑突发包长度的加权全网端到端丢包率。
本发明方法包括以下步骤：
A.接收到新来的突发包，使用可插空最迟可用未占用信道(简称 LAUC-VF：latest available unused channel with void filling) 方法，为其调度波长资源。
B.如果找到了空闲的波长，那么调度成功，方法终止。否则，转到步 骤C。
C.计算每个波长的权重Mi，i代表第i个波长，并计算最小值 Mmin＝min(Mi)，i＝1，2，...，K，K为波长数目。
D.计算新来的突发包的权重值Marrival。
E.比较Mmin和Marrival。如果Marrival＜Mmin，那么调度失败，丢弃该突发包， 方法终止。否则，转到步骤F。
F.相应波长上的冲突的突发包预留的资源将会被新来的突发包抢占， 并向下游节点发送拆链消息。
本方法用突发包已经预留的网络资源总量来作为突发包的权重。对于 一个在OBS网络中传播的突发包，假设它已经经过的跳数为h，突发包长 度为l。如果它在当前节点预留波长资源成功的话，那么它所预留的网络资 源总量可以表示为(h+1)×l。本方法把它作为该突发包的权重。这样，突发 包越长，经过的跳数越多，它的权重就越大，越容易抢占别的突发包的资 源，也就越不容易丢包。
由于采用了上述技术方案，本发明具有以下优点和效果：
本发明的权重计算方法可以精确的反映丢弃一个突发包所要付出的代 价。巧妙的把经过的条数和突发包长度结合在一起，可以同时改善网络的 公平性和信道利用率。原因如下：
由于权重方法中考虑了经过的跳数，可以有效的缩小路由长度不同 的突发包之间的丢包率差异，从而改善网络公平性。
普通的JET协议下，如果那些经过了多跳的包发生丢包，这些突发 包已经预留的那些网络资源也就浪费。采用突发包所预留的网络资 源总量作为权重的方法，可以有效的降低这种情况发生的概率，从 而进一步降低了全网端到端丢包率。
另外，这种权重方法考虑了包长。这相当于给大的突发包更高一些 的优先级，从而使得这些大突发包不容易丢包。大的突发包中包含 的IP包的数目也更多，这样就可以有效地降低基于IP包的丢包率。
另外，在计算波长的权重时，如果在某个波长上存在多个冲突包，用 多个包的权重之和来表示该波长上的权重。之所以采用求和的方法，是因 为本权重方法是用预留的网络资源总量来衡量的，这样必然要用各个包预 留的网络资源总量之和来表示多个包的权重。这种权重计算方法可以精确 的反映丢弃多个突发包所要付出的代价。
下面通过仿真一个7×7网孔型mesh-torus网络，来比较本发明的方 法和标准JET的性能：
每条链路包含两根光纤，分别用于两个方向上。每根光纤上有8个波 长，波长上的速率是10Gbps。每个节点有一个本地源，负责产生突发包。 突发包的生成服从泊松过程。突发包长度为负指数分布，平均长度为50, 000字节(在10G链路上，相当于40μs)。每个节点上的突发包的目的地 址随机分布于网络中的其他节点上。采用最短路径方法计算网络中两点之 间的静态路由。控制包的处理时间是100μs。偏置时间为1000μs。
参照图2，给出了在两种不同调度方法下，加权全网丢包率和负荷之 间的关系。从图中可以看出本调度方法所取得的性能要比标准JET的好。
参照图3，给出了标准JET协议下，全网中不同的路由长度的突发包 的加权丢包率和负荷之间的关系。H为突发包的路由长度。H＝i(i＝1，2， 3，4，5，6)表示该突发包的路由长度为i。从图中可以看出对于标准JET 协议，路由长度越长，丢包率就越高。这与前面的理论分析相符合。在负 荷为0.6时，路由长度为6的突发包与路由长度为1的突发包的丢包率之 间的比值为1700。随着负荷增加，该比值不断减小。负荷为0.9时，该比 值下降为240。该结果表明在不加任何改进措施的标准JET协议下，OBS网 络的公平性是很差的。
参照图4，给出了在改进的调度方法下，全网中不同的路由长度的突 发包的加权丢包率和负荷之间的关系。从图中可以看出路由长度为2，3， 4，5，6的突发包的加权丢包率基本上相等，路由长度为1的突发包的丢 包率要比前面三者略低，但差别不大。在负荷为0.3时，路由长度为6的 突发包与路由长度为1的突发包的丢包率之间的比值为2.6。负荷为0.6 和0.9时，该比值分别为2和1.6。结合图3和图4的仿真结果，可以看 出，采用改进的调度方法后，OBS网络的公平性有了很大的提高。
附图说明
图1是本发明的方法流程图；
图2是两种不同调度方法下，加权全网丢包率和负荷之间的关系图；
图3是标准JET下，全网中不同路由长度的包的加权丢包率和负荷之 间的关系图；
图4是改进JET协议下，全网中不同路由长度的包的加权丢包率和负 荷之间的关系图。
图2是两种不同调度方法下，加权全网丢包率和负荷之间的关系图；
图3是标准JET下，全网中不同路由长度的包的加权丢包率和负荷之 间的关系图；
图4是改进JET协议下，全网中不同路由长度的包的加权丢包率和负 荷之间的关系图。
具体实施方式
参照图1，给出了本发明方法的流程图。
在本发明的方法中，当一个新的突发包到来时，首先通过LAUC-VF(中 文？)方法来寻找一个空闲的波长。如果找到了空闲的波长，那么方法终 止。如果LAUC-VF方法失败，说明在每个波长上都存在一个或多个包所预 留的资源与新来的突发包冲突。此时，计算每个波长上冲突的包的权重Mi， i代表第i个波长。
如果存在多个冲突包时，用多个包的权重之和来表示该波长上的权重。 之所以采用求和的方法，而不是采用求最大值的方法，是因为本权重方法 是用预留的网络资源总量来衡量的，这样必然要用各个包预留的网络资源 总量之和来表示多个包的权重。
其中，Mi，j表示第i个波长上第j个冲突的突发包的权重值。Ni表示第 i个波长上冲突的突发包个数。
然后，求出所有波长中最小的权重值。
Mmin＝min(Mi)，i＝1，2，...，K， (2)
其中，K为波长数目。
将Mmin与新来的包的权重值Marrival相比较。如果新来的包的权重Marrival 大于最小的冲突包权重Mmin，则该波长上的冲突包预留的资源将会被新来 的包抢占。否则，丢弃新来的包。
一旦波长上已经预留的资源被新来的包抢占，必须向下游节点发送拆 链消息，释放下游节点相应的预留资源。拆链包的个数与被强占的突发包 的个数相对应。拆链包的路由也与相应的被抢占包的路由相同。
当下游节点收到拆链包时，如果找到相应的预留资源的话，清除它， 并且向它的下游节点继续发送拆链包。如果没有找到相应的预留记录的话， 这说明突发包已经被丢弃或者拆除，此时销毁拆链包即可。
在本发明的方法中，当一个新的突发包到来时，首先通过LAUC-VF(中 文？)方法来寻找一个空闲的波长。如果找到了空闲的波长，那么方法终 止。如果LAUC-VF方法失败，说明在每个波长上都存在一个或多个包所预 留的资源与新来的突发包冲突。此时，计算每个波长上冲突的包的权重Mi， i代表第i个波长。
如果存在多个冲突包时，用多个包的权重之和来表示该波长上的权重。 之所以采用求和的方法，而不是采用求最大值的方法，是因为本权重方法 是用预留的网络资源总量来衡量的，这样必然要用各个包预留的网络资源 总量之和来表示多个包的权重。
其中，Mi，j表示第i个波长上第j个冲突的突发包的权重值。Ni表示第 i个波长上冲突的突发包个数。
然后，求出所有波长中最小的权重值。
Mmin＝min(Mi)，i＝1，2，...，K， (2)
其中，K为波长数目。
将Mmin与新来的包的权重值Marrival相比较。如果新来的包的权重Marrival 大于最小的冲突包权重Mmin，则该波长上的冲突包预留的资源将会被新来 的包抢占。否则，丢弃新来的包。
一旦波长上已经预留的资源被新来的包抢占，必须向下游节点发送拆 链消息，释放下游节点相应的预留资源。拆链包的个数与被强占的突发包 的个数相对应。拆链包的路由也与相应的被抢占包的路由相同。
当下游节点收到拆链包时，如果找到相应的预留资源的话，清除它， 并且向它的下游节点继续发送拆链包。如果没有找到相应的预留记录的话， 这说明突发包已经被丢弃或者拆除，此时销毁拆链包即可。