[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN108696329B - 基于二维Torus架构的大规模光网络拓扑设计方法 - Google Patents

基于二维Torus架构的大规模光网络拓扑设计方法 Download PDF

Info

Publication number
CN108696329B
CN108696329B CN201810982237.2A CN201810982237A CN108696329B CN 108696329 B CN108696329 B CN 108696329B CN 201810982237 A CN201810982237 A CN 201810982237A CN 108696329 B CN108696329 B CN 108696329B
Authority
CN
China
Prior art keywords
node
network
intermediate node
longitudinal
hop
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
CN201810982237.2A
Other languages
English (en)
Other versions
CN108696329A (zh
Inventor
蔡怡
许渤
邱昆
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
University of Electronic Science and Technology of China
Original Assignee
University of Electronic Science and Technology of China
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by University of Electronic Science and Technology of China filed Critical University of Electronic Science and Technology of China
Priority to CN201810982237.2A priority Critical patent/CN108696329B/zh
Publication of CN108696329A publication Critical patent/CN108696329A/zh
Application granted granted Critical
Publication of CN108696329B publication Critical patent/CN108696329B/zh
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04J—MULTIPLEX COMMUNICATION
    • H04J14/00—Optical multiplex systems
    • H04J14/02—Wavelength-division multiplex systems
    • H04J14/0201—Add-and-drop multiplexing
    • H04J14/0202—Arrangements therefor
    • H04J14/021—Reconfigurable arrangements, e.g. reconfigurable optical add/drop multiplexers [ROADM] or tunable optical add/drop multiplexers [TOADM]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04B—TRANSMISSION
    • H04B10/00—Transmission systems employing electromagnetic waves other than radio-waves, e.g. infrared, visible or ultraviolet light, or employing corpuscular radiation, e.g. quantum communication
    • H04B10/27—Arrangements for networking
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04J—MULTIPLEX COMMUNICATION
    • H04J14/00—Optical multiplex systems
    • H04J14/02—Wavelength-division multiplex systems
    • H04J14/0227—Operation, administration, maintenance or provisioning [OAMP] of WDM networks, e.g. media access, routing or wavelength allocation
    • H04J14/0254—Optical medium access
    • H04J14/0272—Transmission of OAMP information
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04J—MULTIPLEX COMMUNICATION
    • H04J14/00—Optical multiplex systems
    • H04J14/02—Wavelength-division multiplex systems
    • H04J14/0278—WDM optical network architectures

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Computing Systems (AREA)
  • Physics & Mathematics (AREA)
  • Electromagnetism (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

本发明公开了一种基于二维Torus架构的大规模光网络拓扑设计方法，首先根据ROADM的出入端口数和节点数量N确定二维Torus网络的行列数，出入端口数存在3×3、4×4和5×5三种配置，然后根据出入端口数对应的生成方法生成二维Torus网络，作为光网络拓扑，根据用户选择对光网络进行路由分配或路由波长分配。本发明在不同节点数目下均可以生成结构相似、性能优良的二维Torus网络作为光网络拓扑，可以良好适应于大规模光网络的需要。

Description

基于二维Torus架构的大规模光网络拓扑设计方法
技术领域
本发明属于光网络技术领域，更为具体地讲，涉及一种基于二维Torus架构的大规模光网络拓扑设计方法。
背景技术
光网络(Optical Network)一般指使用光纤作为主要传输介质的广域网、城域网或者新建的大范围的局域网，具有传输速度高、传输距离长等特点。在上个世纪70年代光纤技术被提出并得到发展之后，光纤不仅被应用于大范围的电信通信网络中，还被用来建设并行机中的互连网络。光互连技术采用波导方式传输数据，具有损耗低、速度快和延迟小的优点，采用WDM(Wavelength-Division-Multiplexing,波分复用)技术还可以大幅提升互连的带宽密度，可有效解决上述瓶颈问题.是未来片上互连的应用趋势。
随着人们对信息量需求的增加，光网络规模不断扩大，因此对大规模光网络拓扑的研究也是关注的重点。针对大规模固定节点数目的网络，现有研究的拓扑结构很多，线性、环、mesh和torus是互连结构中最常用的网络拓扑结构。Torus网络，也叫k元n立方网络，是一类非常重要的互联网络，在所有的应用领域中占据主导地位。Mesh结构也是人们较早研究的一种直连网络,它结构规则、简单易于实现，但是mesh结构不对称,会极大地影响网络性能；而Torus以网络直径较小、节点的出入端口数相同、拓扑结构较简单、路由路径多和具有可扩展潜能等很多优点成为互连网络的研究热点。Torus网络实际上可以理解成带有环绕通道的mesh网络，它是一种拓扑结构完全对称的网络，因此torus网络的拓扑设计具有十分重要的意义，目前研究中尚没有一种方法可以用来设计大规模二维torus拓扑。
在Torus网络中，所有节点的相邻节点数目相同。Torus网络与Mesh网络的定义有所区别，它所有的节点度数相同，并且X和Y两个节点相邻的充要条件是：存在j，使得Yj＝(Xj±1)mod K，而对于任意i≠j且0≤i≤n-1，有Yi＝Xi。定义中使用了模运算mod，这就给k元n立方增加了环绕通道，使之规整且对称。所以，Torus网络可以看作是带有环绕通道的Mesh网络。图1是Torus网络的结构示意图。
WDM技术是在一条光纤里传输了多种波长的光信号，每种波长的光信号代表一个信道，每个波长的信道都承载独立的一个业务流，多个信道在一条光纤里同时传送数据，即为对一条光纤的复用。ROADM(Reconfigurable Optical Add-Drop Multiplexer，可重构光分插复用器)是一种使用在密集波分复用(DWDM)系统中的器件或设备。图2是ROADM信号传输示意图。如图2所示，ROADM的作用是通过远程的重新配置，可以动态配置上路或下路波长。也就是说，在线路中间，可以根据需要任意地指配上下业务的波长，实现业务的灵活调度。分插在这里的解释是上路和下路的意思。上路的意思就是在进入到ROADM的光信号中，新增加一种波长的信道，和其他的信道一起复用到光纤中；下路的意思就是在进入到ROADM的光信号中，去掉一种波长的信道，其他无关的信道直接通过ROADM，下路的信道直接转到设备中进行业务处理。
发明内容
本发明的目的在于克服现有技术的不足，提供一种基于二维Torus架构的大规模光网络拓扑设计方法，在不同节点数目下均可以生成结构相似、性能优良的二维Torus网络作为光网络拓扑，可以良好适应于大规模光网络的需要。
为了实现以上发明目的，本发明基于二维Torus架构的大规模光网络拓扑设计方法包括以下步骤：
S1：根据ROADM的出入端口数和节点数量N确定二维Torus网络的行列数，具体方法如下：
当ROADM的出入端口数为3×3或5×5时，记其中表示向上取整，表示向下取整；如果N+×N-≥N，则令二维Torus网络的行数H＝N-，列数L＝N+，否则令二维Torus网络的行数H＝N+，列数L＝N+；
当ROADM的出入端口数为4×4时，令二维Torus的行数[]表示四舍五入取整，令二维Torus的列数
S2：按照步骤S1中确定的行数H和列数L生成初始二维Torus网络，为初始二维Torus网络中每个节点配置一个ROADM，当ROADM的出入端口数为3×3时，二维Torus网络横向为单向光纤通道，纵向为单向光纤通道；当ROADM的出入端口数为4×4时，二维Torus网络横向为双向光纤通道，纵向为单向光纤通道；当ROADM的出入端口数为5×5时，二维Torus网络横向为双向光纤通道，纵向为双向光纤通道；
然后计算C＝H×L-N，如果C≠0，则从初始二维Torus网络中删除C个节点，否则不作任何操作，从而得到二维Torus网络，作为光网络拓扑；
S3：判断当前用户是否选择路由波长分配，如果不是，则进入步骤S4进行普通的路由分配，否则进入步骤S5进行路由波长分配；
S4：当需要对光网络进行路由分配时，采用以下方法分配路由：
S4.1：记源节点坐标为(Xs,Ys)、目的节点坐标为(Xd,Yd)，其中X表示节点的行序号，Y表示节点的列序号，判定源节点和目的节点是否存在，如果不存在，则结束路由分配，否则进入步骤S4.2；
S4.2：初始化中间节点(Xm,Ym)中Xm＝Xs，Ym＝Ys；
S4.3：判断是否中间节点的行序号Xm＝Xd，如果是进入步骤S4.4，否则进入步骤S4.7；
S4.4：判断是否中间节点的列序号Ym＝Yd，如果是进入步骤S4.5，否则进入步骤S4.6；
S4.5：将中间节点的历史坐标依次连接，得到源节点至目的节点的路由；
S4.6：当横向为单向光纤通道时，横向移动直接令Ym＝(Ym+1)％L，％表示求余数，返回步骤S4.3；
当横向为双向光纤通道时，需要先采用横向双向比较判断方法进行双向比较判断，确定移动方向并移动1个节点，返回步骤S4.3；其中横向双向比较判断的具体步骤包括：
S4.6.1：判断是否中间节点的列序号Ym＜Yd，如果是，进入步骤S4.6.2，否则进入步骤S4.6.3；
S4.6.2：计算DR＝Yd-Ym，DL＝L+Ym-Yd，进入步骤S4.6.4；
S4.6.3：计算DL＝Ym-Yd，DR＝L+Yd-Ym，进入步骤S4.6.4；
S4.6.4：判断是否DR＝DL，如果是，进入步骤S4.6.5，否则进入步骤S4.6.6；
S4.6.5：在Ym＝Ym+1和Ym＝Ym-1任意选择一个执行；
S4.6.6：进一步判断是否DR＞DL，如果是，进入步骤S4.6.7，否则进入步骤S4.6.8；
S4.6.7：令Ym＝Ym-1；
S4.6.8：令Ym＝Ym+1；
S4.7：判断是否中间节点的列序号Ym＝Yd，如果不是则进入步骤S4.8，否则进入步骤S4.9；
S4.8：当横向为单向光纤通道时，横向移动直接令Ym＝(Ym+1)％L，进入步骤S4.9；
当横向为双向光纤通道时，先采用横向双向比较判断方法进行双向比较判断，确定移动方向并移动1个节点，进入步骤S4.9；
S4.9：当纵向为单向光纤通道时，纵向移动直接令Xm＝(Xm+1)％H，返回步骤S4.3；
当纵向为双向光纤通道时，先采用纵向双向比较判断方法进行双向比较判断，确定移动方向并移动1个节点，返回步骤S4.3；其中纵向双向比较判断的具体步骤包括：
S4.9.1：判断是否中间节点的列序号Xm＜Xd，如果是，进入步骤S4.9.2，否则进入步骤S4.9.3；
S4.9.2：计算DD＝Xd-Xm，DU＝H+Xm-Xd，进入步骤S4.9.4；
S4.9.3：计算DU＝Xm-Xd，DD＝H+Xd-Xm，进入步骤S4.9.4；
S4.9.4：判断是否DD＝DU，如果是，进入步骤S4.9.5，否则进入步骤S4.9.6；
S4.9.5：在Xm＝Xm+1和Xm＝Xm-1任意选择一个执行；
S4.9.6：进一步判断是否DD＞DU，如果是，进入步骤S4.9.7，否则进入步骤S4.9.8；
S4.9.7：令Xm＝Xm-1；
S4.9.8：令Xm＝Xm+1；
S5：当需要对光网络进行路由波长分配时，采用以下方法分配路由波长：
S5.1：判定源节点和目的节点是否存在，如果不存在，则路由波长分配失败，否则进入步骤S5.2；
S5.2：初始化中间节点(Xm,Ym)，即令Xm＝Xs，Ym＝Ys；
S5.3：判断是否中间节点的行序号Xm＝Xd，如果是进入步骤S5.4，否则进入步骤S5.10；
S5.4：判断是否中间节点的列序号Ym＝Yd，如果是进入步骤S5.5，否则进入步骤S5.6；
S5.5：将中间节点的历史坐标依次连接，得到源节点至目的节点的路由，将本次路由波长分配的波长作为源节点与目的节点的通信波长；
S5.6：判断横向下一跳是否满足条件，如果满足则进入步骤S5.7，否则进入步骤S5.8，横向下一跳所需满足的条件有三个，分别为：存在横向下一跳节点，且当前中间节点至该横向下一跳节点链路上本次路由波长分配的波长存在空闲，并且横向下一跳节点与当前中间节点相比更靠近目标节点；
S5.7：将横向下一跳节点作为新的中间节点，返回步骤S5.3；
S5.8：执行回跳操作，回跳操作的具体步骤包括：
S5.8.1：判断当前中间节点是否为源节点，如果是，则回跳操作失败，否则进入步骤S5.8.2；
S5.8.2：令中间节点为当前中间节点的上一个历史中间节点；
S5.8.3：判断纵向下一跳是否满足条件，如果满足则进入步骤S5.8.4，否则返回步骤S5.8.1，纵向下一跳所需满足的条件有三个，分别为：存在纵向下一跳节点，且当前中间节点至该纵向下一跳节点链路上本次路由波长分配的波长存在空闲，并且纵向下一跳节点与当前中间节点相比更靠近目标节点；
S5.8.4：将纵向下一跳节点作为新的中间节点，回跳操作成功；
S5.9：判断回跳操作是否成功，如果是，返回步骤S5.3，否则路由波长分配失败；
S5.10：判断纵向下一跳是否满足条件，如果满足则进入步骤S5.11，否则进入步骤S5.6；
S5.11：将纵向下一跳节点作为新的中间节点，返回步骤S5.3。
本发明基于二维Torus架构的大规模光网络拓扑设计方法，首先根据ROADM的出入端口数和节点数量N确定二维Torus网络的行列数，出入端口数存在3×3、4×4和5×5三种配置，然后根据出入端口数对应的生成方法生成二维Torus网络，作为光网络拓扑，根据用户选择对光网络进行路由分配或路由波长分配。
本发明中提出了一种根据ROADM的出入端口数和节点数量确定二维Torus网络行列数的方法，对于任意节点数目均可以确定对应的行列数和光纤通道和方向，生成对应的二维Torus网络作为光网络拓扑，从而克服了传统方法在拓扑节点数目灵活的情况下生成的拓扑结构存在不确定性的问题，同时为大规模节点数目的光网络互连实现提供了基础。
附图说明
图1是Torus网络的结构示意图；
图2是ROADM信号传输示意图；
图3是本发明基于二维Torus架构的大规模光网络拓扑设计方法的具体实施方式流程图；
图4是本实施例中N＝7时基于3×3ROADM的二维Torus网络结构图；
图5是本实施例中N＝19时基于4×4ROADM的二维Torus网络结构图；
图6是本实施例中N＝7时基于5×5ROADM的二维Torus网络结构图；
图7是本发明中路由分配的流程图；
图8是横向双向比较判断方法的流程图；
图9是纵向双向比较判断方法的流程图；
图10是本发明中路由波长分配的流程图；
图11是图10中回跳操作流程图。
具体实施方式
下面结合附图对本发明的具体实施方式进行描述，以便本领域的技术人员更好地理解本发明。需要特别提醒注意的是，在以下的描述中，当已知功能和设计的详细描述也许会淡化本发明的主要内容时，这些描述在这里将被忽略。
就光网络拓扑的设计而言，主要包括光网络拓扑构建、路由分配和波长分配等。本发明针对端口数分别为3×3、4×4和5×5ROADM，分别对光网络拓扑设计的各个环节进行设计，提高光网络性能。图3是本发明基于二维Torus架构的大规模光网络拓扑设计方法的具体实施方式流程图。如图3所示，本发明基于二维Torus架构的大规模光网络拓扑设计方法的具体步骤包括：
S301：确定二维Torus网络的行列数：
首先需要根据ROADM的出入端口数和节点数量N确定二维Torus网络的行列数。本发明中ROADM的可选出入端口数分别为3×3、4×4和5×5，端口数不同时二维Torus网络的行列数的配置原则也有所不同，对于出入端口数分别为3×3和5×5的ROADM，二维Torus网络的行列数的配置原则为行数与列数之差越小越好，而对于出入端口数为4×4的ROADM，二维Torus网络的行列数的设配置原则为行数小于列数，这是由于本发明设置基于4×4ROADM的二维Torus网络的横向上为双向光纤通道，纵向上为单向光纤通道，因此为了节省网络的跳数，充分利用双向的优点，行数小于列数(H≤L)，这样可以保证横向上的节点个数尽可能的多。行列数配置的具体方法如下：
当ROADM的出入端口数为3×3或5×5时，对节点数量N进行开方，记其中表示向上取整，表示向下取整。如果N+×N-≥N，则令二维Torus网络的行数H＝N-，列数L＝N+，否则令二维Torus网络的行数H＝N+，列数L＝N+。
当ROADM的出入端口数为4×4时，令二维Torus的行数[]表示四舍五入取整，令二维Torus的列数
S302：生成二维Torus网络：
按照步骤S301中确定的行数H和列数L生成初始二维Torus网络，为初始二维Torus网络中每个节点配置一个ROADM。对于不同出入端口数的ROADM，二维Torus网络中的光纤通道配置也不相同。
由于ROADM可以实现光信号在本地节点的上路和下路，所以出入端口数3×3的ROADM除去本地节点的上下路，在整个光网络中可使用的出入端口数为2×2，因此当ROADM的出入端口数为3×3时，二维Torus横向(即行方向)上为单向光纤通道，纵向(即列方向)上也为单向光纤通道。
出入端口数4×4的ROADM除去本地节点的上下路，在整个光网络中可使用的出入端口数为3×3，因此当ROADM的出入端口数为4×4时，二维Torus横向上为双向光纤通道，纵向上为单向光纤通道。
出入端口数5×5的ROADM除去本地节点的上下路，在整个光网络中可使用的出入端口数为4×4，因此当ROADM的出入端口数为5×5时，二维Torus横向上为双向光纤通道，纵向上也为双向光纤通道。
然后计算C＝H×L-N，如果C≠0，则从初始二维Torus网络中删除C个节点，否则不作任何操作，从而得到二维Torus网络，作为光网络拓扑。
接下来分别对三种ROADM出入端口数的二维Torus网络的生成过程进行举例说明。
对于出入端口数为3×3的ROADM，假设节点数量N＝7，则 由于N+×N-＜N，因此二维Torus网络行数H＝3，列数L＝3。而C＝H×L-N＝2，因此需要从初始的3×3的二维Torus网络中删除2个节点，得到二维Torus网络。经研究发现，在删除节点时采用对角线优先原则进行删除，所得到的二维Torus网络性能较好，本实施例中采用从右下角开始依次在对角线上删除C个节点，根据本发明中二维Torus网络的行列数设置方法可知，删除节点个数C小于行数，在对角线上进行节点删除不会造成二维Torus网络实质性改变。
图4是本实施例中N＝7时基于3×3ROADM的二维Torus网络结构图。图4中白色圆点为保留节点，灰色圆点为删除节点。
对于出入端口数为4×4的ROADM，假设节点数量N＝19，则二维Torus网络行数列数而C＝H×L-N＝2，因此需要从初始的3×7的二维Torus网络中删除2个节点。同样地，本实施例中在删除节点时采用对角线优先原则进行删除。图5是本实施例中N＝19时基于4×4ROADM的二维Torus网络结构图。图5中白色圆点为保留节点，灰色圆点为删除节点。
对于出入端口数为5×5的ROADM，假设节点数量N＝7，则 由于N+×N-＜N，因此二维Torus网络行数H＝3，列数L＝3。而C＝H×L-N＝2，因此需要从初始的3×3的二维Torus网络中删除2个节点。同样地，本实施例中在删除节点时采用对角线优先原则进行删除。图6是本实施例中N＝7时基于5×5ROADM的二维Torus网络结构图。图6中白色圆点为保留节点，灰色圆点为删除节点。
对于以上得到的二维Torus网络的光网络，还需要设计路由分配和波长分配方法。
S303：判断当前用户是否选择路由波长分配，如果不是，则进入步骤S304进行普通的路由分配，否则进入步骤S305进行路由波长分配。
S304：路由分配：
图7是本发明中路由分配的流程图。如图7所示，当需要对光网络进行路由分配时，采用以下方法分配路由：
S701：记源节点坐标为(Xs,Ys)、目的节点坐标为(Xd,Yd)，其中X表示节点的行序号，Y表示节点的列序号，判定源节点和目的节点是否存在，如果不存在，则结束路由分配，否则进入步骤S702。
S702：初始化中间节点(Xm,Ym)，即令Xm＝Xs，Ym＝Ys。
S703：判断是否中间节点的行序号Xm＝Xd，如果是进入步骤S704，否则进入步骤S707；
S704：判断是否中间节点的列序号Ym＝Yd，如果是进入步骤S705，否则进入步骤S706；
S705：获取路由：
将中间节点的历史坐标依次连接，得到源节点至目的节点的路由。
S706：横向移动：
由于本发明中ROADM有三种出入端口数，构成的二维Torus网络也不尽相同，即横向上有单向光纤通道和双向光纤通道两种情况，在横向移动时需要根据实际情况选择不同的方法。
当横向为单向光纤通道时，横向移动直接令Ym＝(Ym+1)％L，％表示求余数，返回步骤S703。
当横向为双向光纤通道时，需要先采用横向双向比较判断方法进行双向比较判断，确定移动方向并移动1个节点，返回步骤S703。图8是横向双向比较判断方法的流程图。如图8所示，横向双向比较判断的具体步骤包括：
S801：判断是否中间节点的列序号Ym＜Yd，如果是，进入步骤S802，否则进入步骤S803；
S802：计算DR＝Yd-Ym，DL＝L+Ym-Yd，进入步骤S804；
S803：计算DL＝Ym-Yd，DR＝L+Yd-Ym，进入步骤S804；
S804：判断是否DR＝DL，如果是，进入步骤S805，否则进入步骤S806。
S805：在Ym＝Ym+1和Ym＝Ym-1任意选择一个执行，即横向选择向右、向左均可。
S806：进一步判断是否DR＞DL，如果是，进入步骤S807，否则进入步骤S808。
S807：令Ym＝Ym-1，即横向选择向左。
S808：令Ym＝Ym+1，即横向选择向右。
S707：判断是否中间节点的列序号Ym＝Yd，如果不是则进入步骤S708，否则进入步骤S709。
S708：横向移动：
与步骤S706相同，当横向为单向光纤通道时，横向移动直接令Ym＝(Ym+1)％L，进入步骤S709。
当横向为双向光纤通道时，先采用横向双向比较判断方法进行双向比较判断，确定移动方向并移动1个节点，进入步骤S709。
S709：纵向移动：
同样地，由于纵向上有单向光纤通道和双向光纤通道两种情况，在纵向移动时需要根据实际情况选择不同的方法。
当纵向为单向光纤通道时，纵向移动直接令Xm＝(Xm+1)％H，返回步骤S703。
当纵向为双向光纤通道时，先采用纵向双向比较判断方法进行双向比较判断，确定移动方向并移动1个节点，返回步骤S703。图9是纵向双向比较判断方法的流程图。如图9所示，纵向双向比较判断的具体步骤包括：
S901：判断是否中间节点的列序号Xm＜Xd，如果是，进入步骤S902，否则进入步骤S903；
S902：计算DD＝Xd-Xm，DU＝H+Xm-Xd，进入步骤S904；
S903：计算DU＝Xm-Xd，DD＝H+Xd-Xm，进入步骤S904；
S904：判断是否DD＝DU，如果是，进入步骤S905，否则进入步骤S906。
S905：在Xm＝Xm+1和Xm＝Xm-1任意选择一个执行，即纵向选择向下、向上均可。
S906：进一步判断是否DD＞DU，如果是，进入步骤S907，否则进入步骤S908。
S907：令Xm＝Xm-1，即纵向选择向上。
S908：令Xm＝Xm+1，即纵向选择向下。
S305：路由波长分配：
依次选取待选波长中每个波长进行路由波长分配，如果某个波长路由波长分配成功，即使用该波长和所分配的路由，如果所有波长均未成功分配路由，则路由波长分配失败。图10是本发明中路由波长分配的流程图。如图10所示，当需要对光网络进行路由波长分配时，采用以下方法分配路由波长：
S1001：判定源节点和目的节点是否存在，如果不存在，则路由波长分配失败，否则进入步骤S1002。
S1002：初始化中间节点(Xm,Ym)，即令Xm＝Xs，Ym＝Ys。
S1003：判断是否中间节点的行序号Xm＝Xd，如果是进入步骤S1004，否则进入步骤S1010；
S1004：判断是否中间节点的列序号Ym＝Yd，如果是进入步骤S1005，否则进入步骤S1006；
S1005：获取路由：
将中间节点的历史坐标依次连接，得到源节点至目的节点的路由，将本次路由波长分配的波长作为源节点与目的节点的通信波长。
S1006：判断横向下一跳是否满足条件，如果满足则进入步骤S1007，否则进入步骤S1008，横向下一跳所需满足的条件有三个，分别为：存在横向下一跳节点，且当前中间节点至该横向下一跳节点链路上本次路由波长分配的波长存在空闲，并且横向下一跳节点与当前中间节点相比更靠近目标节点。以上三个条件需要同时满足，方能进行横向下一跳更新。
S1007：横向下一跳更新：
将横向下一跳节点作为新的中间节点，返回步骤S1003。
S1008：执行回跳操作：
图11是图10中回跳操作流程图。如图11所示，回跳操作的具体步骤包括：
S1101：判断当前中间节点是否为源节点，如果是，则回跳操作失败，否则进入步骤S1102。
S1102：中间节点回跳：
令中间节点为当前中间节点的上一个历史中间节点。
S1103：判断纵向下一跳是否满足条件，如果满足则进入步骤S1104，否则返回步骤S1101，纵向下一跳所需满足的条件有三个，分别为：存在纵向下一跳节点，且当前中间节点至该纵向下一跳节点链路上本次路由波长分配的波长存在空闲，并且纵向下一跳节点与当前中间节点相比更靠近目标节点。同样地，以上三个条件需要同时满足，方能进行纵向下一跳更新。
S1104：纵向下一跳更新：
将纵向下一跳节点作为新的中间节点，回跳操作成功。
S1009：判断回跳操作是否成功，如果是，返回步骤S1003，否则路由波长分配失败。
S1010：判断纵向下一跳是否满足条件，如果满足则进入步骤S1011，否则进入步骤S1006。
S1011：纵向下一跳更新：
将纵向下一跳节点作为新的中间节点，返回步骤S1003。
为了更好地说明本发明的技术方案，对本发明中基于不同出入端口数的二维Torus网络的有效性进行验证。本次验证中采用最大跳数和平均跳数和来比较相同节点数量不同网络拓扑的性能，其中最大跳数表示一个网络拓扑里面任意节点对之间最小跳数的最大值，平均跳数和表示一个网络拓扑里面所有节点对之间最小跳数的平均值。以下每个表格中加粗所标识的方案(即第1个方案)为采用本发明获取的二维Torus网络。
1)基于3×3ROADM的二维Torus网络
表1 是节点数量N＝15时不同网络拓扑的最大跳数和平均跳数和。
H/L C 最大跳数 平均跳数和
H＝4,L＝4 1 6 46.3
H＝3,L＝5 0 6 48.2
H＝3,L＝6 3 7 49.3
表1
如表1所示，在节点数量N＝15时，二维Torus网络为4×4-1时可以取得最佳的性能。
表2 是节点数量N＝50时不同网络拓扑的最大跳数和平均跳数和。
H/L C 最大跳数 平均跳数和
H＝7,L＝8 6 13 210.0
H＝2,L＝25 0 25 637.8
H＝5,L＝10 0 13 331.6
H＝10,L＝5 0 13 331.6
H＝25,L＝2 0 25 637.8
表2
如表2所示，在节点数量N＝50时，二维Torus网络为7×8-6时可以取得最佳的性能。
表3 是节点数量N＝120时不同网络拓扑的最大跳数和平均跳数和。
H/L C 最大跳数 平均跳数和
H＝11,L＝11 1 20 1201.7
H＝2,L＝60 0 60 3630.3
H＝3,L＝40 0 41 2480.7
H＝4,L＝30 0 32 1936.1
H＝5,L＝24 0 27 1633.6
H＝6,L＝20 0 24 1452.1
H＝8,L＝15 0 21 1270.6
H＝10,L＝12 0 20 1210.1
表3
如表3所示，在节点数量N＝120时，二维Torus网络为11×11-1时可以取得最佳的性能。
2)基于4×4ROADM的二维Torus网络
表4 是节点数量N＝17时不同网络拓扑的最大跳数和平均跳数和。
H/L C 最大跳数 平均跳数和
H＝3,L＝6 1 5 43.5
H＝1,L＝17 0 8 76.5
H＝2,L＝9 1 5 47.5
H＝4,L＝5 3 6 46.3
表4
如表4所示，在节点数量N＝17时，二维Torus网络为3×6-1时可以取得最佳的性能。
表5 是节点数量N＝50时不同网络拓扑的最大跳数和平均跳数和。
H/L C 最大跳数 平均跳数和
H＝5,L＝10 0 9 229.6
H＝1,L＝50 0 25 637.8
H＝2,L＝25 0 13 343.9
H＝4,L＝13 2 14 237.1
H＝5,L＝11 5 14 233.7
H＝6,L＝9 4 13 233.3
H＝7,L＝8 6 13 239.9
表5
如表5所示，在节点数量N＝50时，二维Torus网络为5×10时可以取得最佳的性能。
表6 是节点数量N＝120时不同网络拓扑的最大跳数和平均跳数和。
H/L C 最大跳数 平均跳数和
H＝8,L＝15 0 14 875.3
H＝1,L＝120 0 60 3630.3
H＝2,L＝60 0 31 1875.6
H＝3,L＝40 0 22 1331.1
H＝4,L＝30 0 18 1089.1
H＝5,L＝24 0 16 968.1
H＝6,L＝20 0 15 907.6
H＝6,L＝21 6 25 921.0
H＝7,L＝18 6 23 888.2
H＝8,L＝16 8 22 880.9
H＝9,L＝14 6 21 884.4
H＝10,L＝12 0 15 907.6
H＝11,L＝11 1 15 929.0
表6
如表6所示，在节点数量N＝120时，二维Torus网络为8×15时可以取得最佳的性能。
3)基于5×5ROADM的二维Torus网络
表7 是节点数量N＝18时不同网络拓扑的最大跳数和平均跳数和。
H/L C 最大跳数 平均跳数和
H＝4,L＝5 2 4 40.9
H＝1,L＝18 0 9 85.8
H＝2,L＝9 0 5 51.9
H＝3,L＝6 0 4 41.3
H＝3,L＝7 3 8 45.5
表7
如表7所示，在节点数量N＝18时，二维Torus网络为4×5-2时可以取得最佳的性能。
表8 是节点数量N＝60时不同网络拓扑的最大跳数和平均跳数和。
H/L C 最大跳数 平均跳数和
H＝8,L＝8 4 8 237.3
H＝1,L＝60 0 30 915.3
H＝2,L＝30 0 16 488.1
H＝3,L＝20 0 11 345.8
H＝4,L＝15 0 9 288.8
H＝5,L＝12 0 8 256.3
H＝6,L＝10 0 8 244.1
H＝7,L＝9 3 9 237.8
表8
如表8所示，在节点数量N＝60时，二维Torus网络为8×8-4时可以取得最佳的性能。
表9 是节点数量N＝150时不同网络拓扑的最大跳数和平均跳数和。
表9
如表9所示，在节点数量N＝120时，二维Torus网络为12×13-6时可以取得最佳的性能。
根据以上仿真可知，采用本发明所生成的二维Torus网络是性能最优的二维Torus网络，且在节点数量较大的时候具有明显技术优势。
尽管上面对本发明说明性的具体实施方式进行了描述，以便于本技术领域的技术人员理解本发明，但应该清楚，本发明不限于具体实施方式的范围，对本技术领域的普通技术人员来讲，只要各种变化在所附的权利要求限定和确定的本发明的精神和范围内，这些变化是显而易见的，一切利用本发明构思的发明创造均在保护之列。

Claims (1)

1.一种基于二维Torus架构的大规模光网络拓扑设计方法，其特征在于，包括以下步骤：
S1：根据ROADM的出入端口数和节点数量N确定二维Torus网络的行列数，具体方法如下：
当ROADM的出入端口数为3×3或5×5时，记其中表示向上取整，表示向下取整；如果N+×N-≥N，则令二维Torus网络的行数H＝N-，列数L＝N+，否则令二维Torus网络的行数H＝N+，列数L＝N+；
当ROADM的出入端口数为4×4时，令二维Torus的行数[]表示四舍五入取整，令二维Torus的列数
S2：按照步骤S1中确定的行数H和列数L生成初始二维Torus网络，为初始二维Torus网络中每个节点配置一个ROADM，当ROADM的出入端口数为3×3时，二维Torus网络横向为单向光纤通道，纵向为单向光纤通道；当ROADM的出入端口数为4×4时，二维Torus网络横向为双向光纤通道，纵向为单向光纤通道；当ROADM的出入端口数为5×5时，二维Torus网络横向为双向光纤通道，纵向为双向光纤通道；
然后计算C＝H×L-N，如果C≠0，则在初始二维Torus网络中从右下角开始依次在对角线上删除C个节点，否则不作任何操作，从而得到二维Torus网络，作为光网络拓扑；
S3：判断当前用户是否选择路由波长分配，如果不是，则进入步骤S4进行普通的路由分配，否则进入步骤S5进行路由波长分配；
S4：当需要对光网络进行路由分配时，采用以下方法分配路由：
S4.1：记源节点坐标为(Xs,Ys)、目的节点坐标为(Xd,Yd)，其中X表示节点的行序号，Y表示节点的列序号，判定源节点和目的节点是否存在，如果不存在，则结束路由分配，否则进入步骤S4.2；
S4.2：初始化中间节点(Xm,Ym)中Xm＝Xs，Ym＝Ys；
S4.3：判断是否中间节点的行序号Xm＝Xd，如果是进入步骤S4.4，否则进入步骤S4.7；
S4.4：判断是否中间节点的列序号Ym＝Yd，如果是进入步骤S4.5，否则进入步骤S4.6；
S4.5：将中间节点的历史坐标依次连接，得到源节点至目的节点的路由；
S4.6：当横向为单向光纤通道时，横向移动直接令Ym＝(Ym+1)％L，％表示求余数，返回步骤S4.3；
当横向为双向光纤通道时，需要先采用横向双向比较判断方法进行双向比较判断，确定移动方向并移动1个节点，返回步骤S4.3；其中横向双向比较判断的具体步骤包括：
S4.6.1：判断是否中间节点的列序号Ym＜Yd，如果是，进入步骤S4.6.2，否则进入步骤S4.6.3；
S4.6.2：计算DR＝Yd-Ym，DL＝L+Ym-Yd，进入步骤S4.6.4；
S4.6.3：计算DL＝Ym-Yd，DR＝L+Yd-Ym，进入步骤S4.6.4；
S4.6.4：判断是否DR＝DL，如果是，进入步骤S4.6.5，否则进入步骤S4.6.6；
S4.6.5：在Ym＝Ym+1和Ym＝Ym-1任意选择一个执行；
S4.6.6：进一步判断是否DR＞DL，如果是，进入步骤S4.6.7，否则进入步骤S4.6.8；
S4.6.7：令Ym＝Ym-1；
S4.6.8：令Ym＝Ym+1；
S4.7：判断是否中间节点的列序号Ym＝Yd，如果不是则进入步骤S4.8，否则进入步骤S4.9；
S4.8：当横向为单向光纤通道时，横向移动直接令Ym＝(Ym+1)％L，进入步骤S4.9；
当横向为双向光纤通道时，先采用横向双向比较判断方法进行双向比较判断，确定移动方向并移动1个节点，进入步骤S4.9；
S4.9：当纵向为单向光纤通道时，纵向移动直接令Xm＝(Xm+1)％H，返回步骤S4.3；
当纵向为双向光纤通道时，先采用纵向双向比较判断方法进行双向比较判断，确定移动方向并移动1个节点，返回步骤S4.3；其中纵向双向比较判断的具体步骤包括：
S4.9.1：判断是否中间节点的列序号Xm＜Xd，如果是，进入步骤S4.9.2，否则进入步骤S4.9.3；
S4.9.2：计算DD＝Xd-Xm，DU＝H+Xm-Xd，进入步骤S4.9.4；
S4.9.3：计算DU＝Xm-Xd，DD＝H+Xd-Xm，进入步骤S4.9.4；
S4.9.4：判断是否DD＝DU，如果是，进入步骤S4.9.5，否则进入步骤S4.9.6；
S4.9.5：在Xm＝Xm+1和Xm＝Xm-1任意选择一个执行；
S4.9.6：进一步判断是否DD＞DU，如果是，进入步骤S4.9.7，否则进入步骤S4.9.8；
S4.9.7：令Xm＝Xm-1；
S4.9.8：令Xm＝Xm+1；
S5：当需要对光网络进行路由波长分配时，采用以下方法分配路由波长：
S5.1：判定源节点和目的节点是否存在，如果不存在，则路由波长分配失败，否则进入步骤S5.2；
S5.2：初始化中间节点(Xm,Ym)，即令Xm＝Xs，Ym＝Ys；
S5.3：判断是否中间节点的行序号Xm＝Xd，如果是进入步骤S5.4，否则进入步骤S5.10；
S5.4：判断是否中间节点的列序号Ym＝Yd，如果是进入步骤S5.5，否则进入步骤S5.6；
S5.5：将中间节点的历史坐标依次连接，得到源节点至目的节点的路由，将本次路由波长分配的波长作为源节点与目的节点的通信波长；
S5.6：判断横向下一跳是否满足条件，如果满足则进入步骤S5.7，否则进入步骤S5.8，横向下一跳所需满足的条件有三个，分别为：存在横向下一跳节点，且当前中间节点至该横向下一跳节点链路上本次路由波长分配的波长存在空闲，并且横向下一跳节点与当前中间节点相比更靠近目标节点；
S5.7：将横向下一跳节点作为新的中间节点，返回步骤S5.3；
S5.8：执行回跳操作，回跳操作的具体步骤包括：
S5.8.1：判断当前中间节点是否为源节点，如果是，则回跳操作失败，否则进入步骤S5.8.2；
S5.8.2：令中间节点为当前中间节点的上一个历史中间节点；
S5.8.3：判断纵向下一跳是否满足条件，如果满足则进入步骤S5.8.4，否则返回步骤S5.8.1，纵向下一跳所需满足的条件有三个，分别为：存在纵向下一跳节点，且当前中间节点至该纵向下一跳节点链路上本次路由波长分配的波长存在空闲，并且纵向下一跳节点与当前中间节点相比更靠近目标节点；
S5.8.4：将纵向下一跳节点作为新的中间节点，回跳操作成功；
S5.9：判断回跳操作是否成功，如果是，返回步骤S5.3，否则路由波长分配失败；
S5.10：判断纵向下一跳是否满足条件，如果满足则进入步骤S5.11，否则进入步骤S5.6；
S5.11：将纵向下一跳节点作为新的中间节点，返回步骤S5.3。
CN201810982237.2A 2018-08-27 2018-08-27 基于二维Torus架构的大规模光网络拓扑设计方法 Expired - Fee Related CN108696329B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201810982237.2A CN108696329B (zh) 2018-08-27 2018-08-27 基于二维Torus架构的大规模光网络拓扑设计方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201810982237.2A CN108696329B (zh) 2018-08-27 2018-08-27 基于二维Torus架构的大规模光网络拓扑设计方法

Publications (2)

Publication Number Publication Date
CN108696329A CN108696329A (zh) 2018-10-23
CN108696329B true CN108696329B (zh) 2019-07-12

Family

ID=63841372

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201810982237.2A Expired - Fee Related CN108696329B (zh) 2018-08-27 2018-08-27 基于二维Torus架构的大规模光网络拓扑设计方法

Country Status (1)

Country Link
CN (1) CN108696329B (zh)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN115499271B (zh) * 2022-08-30 2023-10-13 西北工业大学 一种混合网络拓扑结构及其路由方法

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2007096852A1 (en) * 2006-02-21 2007-08-30 University College Cork - National University Of Ireland, Cork An optical communication network
CN102780936B (zh) * 2012-07-17 2014-11-12 西安电子科技大学 无阻塞通信的光片上网络系统及其通信方法
CN103124420B (zh) * 2013-01-21 2015-06-24 电子科技大学 一种无线片上网络架构方法
CN104320341B (zh) * 2014-10-23 2017-05-24 东北大学 路由自适应异步2D‑Torus片上网络系统及其设计方法

Also Published As

Publication number Publication date
CN108696329A (zh) 2018-10-23

Similar Documents

Publication Publication Date Title
JP5523578B2 (ja) 周波数割当方法および装置
Dutta et al. A survey of virtual topology design algorithms for wavelength routed optical networks
US8515280B1 (en) Physically-diverse routing in heterogeneous optical networks
JP2012109928A (ja) 波長パス再配置方法及び上位レイヤパス再配置方法
CN108111411B (zh) 骨干网络及其动态路径规划系统和规划方法
JP2010199891A (ja) ネットワーク設計管理方法及び装置及び光ネットワークシステム
CN109429117A (zh) 路由选择方法和设备
CN108696329B (zh) 基于二维Torus架构的大规模光网络拓扑设计方法
Farahmand et al. Efficient online traffic grooming algorithms in WDM mesh networks with drop-and-continue node architecture
KR101541534B1 (ko) 광학 네트워크 온 칩의 광 라우터 설계 장치 및 방법
Agrawal et al. Core arrangement based spectrum-efficient path selection in core-continuity constrained SS-FONs
US7925163B2 (en) Assignment of channel colors in optical networks
US9325446B2 (en) Method of configuring an optical path, a path computation engine and an optical communications network node
Le et al. Multicast routing in WDM networks without splitters
CN101330344A (zh) 一种波分复用网中单链路故障的子通路保护方法
Beauquier et al. All-to-all routing and coloring in weighted trees of rings
Jinno et al. Minimal virtualized-elastic-regenerator placement and least congestion resources assignment for translucent elastic optical networks
CN106060682A (zh) 基于串联结构分层光交叉连接的波带路由方法
Zhao et al. Multi-core virtual concatenation scheme considering inter-core crosstalk in spatial division multiplexing enabled elastic optical networks
JP3811147B2 (ja) 波長分割多重方式を利用する環状通信ネットワークの波長割当方法
JP5898112B2 (ja) ネットワーク設計装置およびネットワーク設計プログラム
JP2013062628A (ja) パス再配置方法及び装置
JP4155894B2 (ja) 波長ルーティング装置及び波長ルーティングネットワーク
JP6048252B2 (ja) ネットワーク設計方法およびネットワーク設計装置
Lai et al. Resource Optimization for Link Failure Recovery of Software-Defined Optical Network

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant
CF01 Termination of patent right due to non-payment of annual fee
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20190712