在WDM环网中的DRC覆盖问题

1、在WDM环网中的DRC覆盖问题目 录1. 基本概念2. 问题的背景3. 已知结果4. 一些记号5. 本文的结果6. 问题在WDM环网中的DRC覆盖问题1. 基本概念在WDM环网中的DRC覆盖问题* Synchronous Optical Network (同步光纤网)SONET是Bellcore于八十年代中期首先提出的用光导纤维传输的物理层标准。它被ANSI标准化并被CCITT推荐在全世界推广。我们可以用看待Ethernet双绞线局域网作为机构网通信系统的同样观点，来看待SONET作为一个全球性通信系统的物理网。这是一种潜在的全球性网络，在光纤上具有标准的数据传输率，并在世界范围内被广泛接受。

2、SONET使世界各 公司融为一体。在WDM环网中的DRC覆盖问题* Bidirectional (双向通信)传递一个对象，这个对象可以在Server端中回调 (Callback) 把运算结果在Client端显示出来。进行客户端和服务器双向通信的技术. * Unidirectional (单向通信)。 在WDM环网中的DRC覆盖问题* WDM (wavelength-division multiplexed 波分复用)波分复用(WDM)是指在一根光纤上，同时传输波长不同的多个光载波信号，而每一个光载波可以通过频分复用(FDM)或时分复用(TDM)方式，各自载荷多路模拟信号或多路数字信号。* DW

3、DM (dense WDM)密集波分复用系统。在WDM环网中的DRC覆盖问题* ADM （Add-Drop Multiplexer）分插复用器-是 SONET/SDH 网络的主要组成部分,联合, 或多元,一些较低速数据流进入到一个单束光。 * OADM （ Optical Add-Drop Multiplexer） 光分插复用器* WADM（wavelength add-drop multiplexer） 波分插复用器在WDM环网中的DRC覆盖问题* DCS （Digital Cross-connect System）数字交叉连接系统是一个数字信号或它的权利部分提供自动交叉连接的网络元素。*

4、SDH （Synchrounous Digital Hierarchy）同步数字体系-是设备大家族中的一员，在自动配线，路由调度，通信保护/恢复，网络资源优化配置和网络管理等方面发挥着重要的作用，并使网络具有了更高的智能化。 在WDM环网中的DRC覆盖问题WDM与ADM在WDM环网中的DRC覆盖问题WDM ring networks:WDM环网在WDM环网中的DRC覆盖问题* g-设计 （g- 覆盖）设 为正整数， H是一个图，g是一些无孤立点的有限简单图的集合，我们用H表示H的每条边都重复次而得到的多重图.H的g-设计（g-覆盖）是一个有序对 (X,), 这里X为H 的顶点集，是H的子图的集

5、合(称为区组集)，使得其中每一个元素都同构于g中某个图，且H的任意一条边在区组集中恰 (至少) 出现次. H的g-设计和g-覆盖分别记为GD(H, g,)和CD(H, g,).在WDM环网中的DRC覆盖问题例：5-圈系设K5 的点集为 X=0,1,2,3,4，g=C5, 则K5 的 g-设计为（X,B)：其中B: (0,1,2,3,4), (0,2,4,1,3)在WDM环网中的DRC覆盖问题K6的 g-设计设K6 的点集为 X=0,1,2,3,4,5，g=K5,K1,5, 则 K6 的 g-设计为（X,B)：其中B: K5 0,1,2,3,4, K1,5 5;0,1,2,3,4.在WDM环网中

6、的DRC覆盖问题g=G时称为图分解(或覆盖)|g|1时,称为多图分解(或覆盖)已知结果简介1.对图分解2.对图覆盖在WDM环网中的DRC覆盖问题2. 问题的背景在WDM环网中的DRC覆盖问题 随着网络业务量的爆炸性增长以及光网络设备器件(OXC、OADM等) 的快速发展, 波分复用(WDM) 技术成为目前骨干网络的核心技术。由于WDM光网络中每个波长可提供高达吉比特(如OC248、OC2192、OC2768)的传输容量, 而很多业务连接请求的带宽(如OC21, OC23, OC212)都小于一个波长容量。因此, 有必要使用业务疏导(traffic grooming)技术将多个低速度的业务连接请

7、求有效汇聚在一个波长通道传输。 流量疏导研究的是如何将不同速率、不同类型的低速业务打包成高速数据流,复用到一个波长上, 用来实现某种设计目的的过程. 在由SONET/ WDM 构成的网络中,每一波长可通过时分复用( TDM) 方式承载很多低速业务流.在WDM环网中的DRC覆盖问题 在基于WDM技术的光网络中, 一根光纤的失效会导致大量数据的丢失.因此对WDM光网络的抗毁性, 预防阻塞和预防掉线问题进行深入研究具有重要的价值.本文要考虑一个覆盖问题,这个问题是由预防阻塞，保持线路的独立性和抗毁性WDM网络的生存性而引起的,其中通信请求在子网络中分配路径, 这些子网络的保护是相互独立的. 在WDM

8、环网中的DRC覆盖问题物理图: 我们用一个图G来模拟WDM网, 并称此图为物理图, 图的顶点代表光转换器, 边代表连接两个转换器的光纤. 事实上, G为一个有向对称多重图；也就是说每次有一个信号通过光纤从结点 x 传到结点 y, 同时也有一个反向信号从结点 y 传向结点 x. 我们将考虑图G是有向对称图和无向对称图的情形. 在WDM环网中的DRC覆盖问题 通常物理图不需要正则性,为了确保发送失败的需求能够重新分配路径,物理图必须具有连通性. 环形网的重要特点是环路中任何两个节点之间都存在两条经过不同路由的网络连接, 因此比较容易实现对环路的保护.许多光网络设计者考虑将物理图设计成环. 也就是说

9、, 图G或者是长为n的无向圈,或者是对称有向圈. 在WDM环网中的DRC覆盖问题4个波长的环型光纤在WDM环网中的DRC覆盖问题10个用户在WDM环网中的DRC覆盖问题逻辑图: 在G中发送业务请求就是指有业务请求的两个节点在G中找到一条路. 所有请求构成的图称为逻辑图 I. 我们考虑的保护问题是指用I的一族子图 Ik 覆盖所有需求.通常情况下, 我们希望 Ik 有简单的结构以及有较少的顶点数.因此一个非常有用的情况是 Ik 为一个短圈. 事实上, 保护是指事先为业务预留备份资源, 当故障发生后, 业务可以被快速地切换到预留的备份资源上进行承载.在WDM环网中的DRC覆盖问题 在此，我们使用圈的

10、一半资源发送请求,一旦发送失败, 我们将重新用另一半资源发送请求.将短圈作为子网络, 容易操作, 同时重新分配路径时花费也少. 事实上, 由于请求必须在物理网络G上发送, 因此还有另一个限制条件: 我们可以认为将每个子网络分配一个波长. 每一个圈由一些请求组成, 这些请求必须是在物理图G上发送且顶点是不交的. 换句话说就是我们要为每个请求找到相应的顶点不交的路. 我们将这个性质叫做不交的路径选择控制性质. 在WDM环网中的DRC覆盖问题逻辑图的边集合01，06，27，47在WDM环网中的DRC覆盖问题我们的目的是降低网络费用： 当G=Cn时,相应问题转化为求覆盖逻辑图的圈数. 此时所用的波长数

11、最少。 本问题是使所用波长数最小。在WDM环网中的DRC覆盖问题需要解决的问题： 1.物理图上任意两个结点间都有业务请求和相互业务请求的问题. 2. 物理图上任意两个结点间都有多个业务请求和相互业务请求的问题. 3.物理图上有多类用户, 同类中的用户彼此没有业务,不同类中的用户任意两个结点间都有业务请求和相互业务请求的问题.在WDM环网中的DRC覆盖问题DRC条件(disjoint routing constraint )指将有业务往来的用户在物理图上直接连接。 即：设物理图G的点集为Zn, DRC条件是指将G的点按如下顺序排列：0, 1, 2,n-1, 使得圈具有不交的布线性质。* 图G的D

12、RC圈分解是指将逻辑图H的边集分解成满足DRC条件的圈的并.*图G的DRC圈覆盖是指将DRC条件的圈覆盖逻辑图H的边集.在WDM环网中的DRC覆盖问题满足和不满足DRC条件4长圈在WDM环网中的DRC覆盖问题K5的DRC-分解 K5被2个C3和1个C4覆盖(0,1,2), (1,A,B), (0,B,2,A)在WDM环网中的DRC覆盖问题K6的DRC-覆盖 K6被2个C3和3个C4覆盖(0,1,4), (0,1,3), (0,2,4,5),(1,2,3,5),(2,3,4,5)在WDM环网中的DRC覆盖问题3. 已知结果在WDM环网中的DRC覆盖问题对于逻辑图为Kn和K*n由Bermond等人

13、在下面的文献中讨论它的最优解.J-C. Bermond, D. Coudert, Min-Li Yu, On DRC-covering of Kn by cycles, Journal of Combinatorial Designs,11(2003), 100 - 112.并提出了两个问题Kn和Kn，n.在WDM环网中的DRC覆盖问题对于逻辑图为Kn和Kn，n韩娜在其硕士学位论文 关于DRC圈覆盖问题，河北师大，2008 中研究了逻辑图为Kn和K*n ，Kn，n和K*n, n 时的DRC圈覆盖.在WDM环网中的DRC覆盖问题对于逻辑图为Kt(n)谢春丽解决了当物理图为Kt(n)（其中n和t都

14、为奇数）时的DRC圈覆盖问题.见文献谢春丽，完全多部图的DRC圈覆盖问题，河北师大硕士学位论文，2009.在WDM环网中的DRC覆盖问题对于环型网逻辑图为KnBermond和Yu将问题延伸到物理图G为圆环型的情形.见文献J-C. Bermond,Min-Li Yu,Vertex disjoint routings of cycles over Tori, NETWORKS, Vol. 49(3)(2007), 217225.在WDM环网中的DRC覆盖问题综述文章Z.Liang and S.Yang, On DRC covering-a survey, Journal of Discrete M

15、athematical Sciences & Cryptography, in press.在WDM环网中的DRC覆盖问题4. 一些记号在WDM环网中的DRC覆盖问题 Kv 表示v阶完全图.Kt(n)表示每个部的点数为n的t-部完全图. Cm表示m长无向圈, 记为(a1,a2,am).H表示图H中每条边重复次.在WDM环网中的DRC覆盖问题 (n,), *(n,)分别表示Kn, K*n 的DRC圈覆盖所需的最小圈数. k(n,), *k(n,)分别表示Kn, K*n 的DRC k长圈覆盖所需的最小圈数.在WDM环网中的DRC覆盖问题(nt,), *(nt,)分别表示Kt(n), K*t(n) 的DRC圈覆盖所需的最小圈数. k(nt,), *k(nt,) 分别表示圈长固定为k时的 Kt(n), K*t(n)的DRC圈覆盖所需的最小圈数.在WDM环网中的DRC覆盖问题Z is a ring of integers.Zm is residue class group modulo m with residue classes 0,1,m-1. a,b =xZ | a x b.a,bk =xZ | ax b, x a (mod k) .Lx=miny | y Z, xy.在WDM