[go: up one dir, main page]

CN111800339B - 混合sdn场景下带有路径数目约束的路由优化方法 - Google Patents

混合sdn场景下带有路径数目约束的路由优化方法 Download PDF

Info

Publication number
CN111800339B
CN111800339B CN202010633665.1A CN202010633665A CN111800339B CN 111800339 B CN111800339 B CN 111800339B CN 202010633665 A CN202010633665 A CN 202010633665A CN 111800339 B CN111800339 B CN 111800339B
Authority
CN
China
Prior art keywords
path
paths
node
traffic
sdn
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.)
Active
Application number
CN202010633665.1A
Other languages
English (en)
Other versions
CN111800339A (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.)
Fuzhou University
Original Assignee
Fuzhou University
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 Fuzhou University filed Critical Fuzhou University
Priority to CN202010633665.1A priority Critical patent/CN111800339B/zh
Publication of CN111800339A publication Critical patent/CN111800339A/zh
Application granted granted Critical
Publication of CN111800339B publication Critical patent/CN111800339B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H04L45/123—Evaluation of link metrics
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/38—Flow based routing

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

本发明涉及一种混合SDN场景下带有路径数目约束的路由优化方法，包括以下步骤：步骤S1:采用贪心算法确定SDN节点的部署位置；步骤S2:根据SDN节点的部署位置，找到所有源目的节点对之间流量需求的可行路径;步骤S3:计算没有路径约束情况下流量在所有可行路径上的分配情况；步骤S4:设置路径数目的约束为h,使用随机取整从每个流量需求的所有可行路径中选出满足路径数目约束的最优路径，得到最优路径集；步骤S5:根据最优路径集，考虑多商品流问题，计算流量在路径上的最优分流。本发明能够实现在有路径数目约束的情况下，有效降低网络的最大链路利用率，进一步提高网络性能。

Description

混合SDN场景下带有路径数目约束的路由优化方法
技术领域
本发明属于路由优化领域，具体涉及一种混合SDN场景下带有路径数目约束的路由优化方法。
背景技术
软件定义网络(SDN)是新型的网络体系架构，其中实现了数据平面和控制平面在SDN交换机和SDN控制器上的解耦。具体而言，SDN交换机是可编程的，根据控制器下发的流表项进行网络流量的转发。SDN控制器是逻辑上集中的设备，通过从SDN收集网络信息来获取网络状态，从而得到全局视图。控制器通过将流条目分派给SDN交换机，来实现网络流量的细粒度转发控制。和传统分布式网络中基于最短路径转发不同，SDN可以实现更加灵活，便捷和智能的网络管理和控制。因此，相关SDN的研究已引起全世界的关注。
尽管SDN具有许多优势，但实际上，一步实现传统网络到SDN网络的完全迁移是非常困难的，特别是对于大规模传统网络。原因主要有两个方面：经济因素和技术因素。一方面，购买和部署SDN设备以升级整个传统网络的基础架构将不可避免地给互联网服务提供商(Internet Service Provider,ISP)带来巨大的资本支出和运营负担。目前，ISP可能不愿意一步实现从传统网络到SDN网络的更新。同时，考虑部署的收益，许多研究表明无需将网络中的所有旧设备更新为SDN设备。另一方面，新兴的与SDN相关的硬件和软件相对不成熟，缺乏大规模的适当评估，SDN设备的可靠性和稳定性无法保证。这意味着使用专用SDN设备更新整个传统网络的基础架构设备可能会导致潜在的安全和不稳定风险。
发明内容
有鉴于此，本发明的目的在于提供一种混合SDN场景下带有路径数目约束的路由优化方法，能够实现在有路径数目约束的情况下，有效降低网络的最大链路利用率，进一步提高网络性能。
为实现上述目的，本发明采用如下技术方案：
一种混合SDN场景下带有路径数目约束的路由优化方法，包括以下步骤：
步骤S1:采用贪心算法确定SDN节点的部署位置；
步骤S2:根据SDN节点的部署位置，找到所有源目的节点对之间流量需求的可行路径；
步骤S3:计算没有路径约束情况下流量在所有可行路径上的分配情况；
步骤S4:设置路径数目的约束为h,使用随机取整从每个流量需求的所有可行路径中选出满足路径数目约束的最优路径，得到最优路径集；
步骤S5:根据最优路径集，考虑多商品流问题，计算流量在路径上的最优分流。
进一步的，所述步骤S1具体为：
步骤S1.1:计算流量按照源目的节点之间最短路径路由得到的网络流量分配情况，得到每条链路上的链路利用率；
步骤S1.2:按照链路利用率从大到小排序，优先部署出链路利用率大的节点为SDN节点。
进一步的，所述步骤S2具体为：
步骤S2.1:针对混合SDN网络拓扑中的节点a，选择使用迪杰斯特拉算法构造从a出发到其他每一个节点的最短路径树，将找到的图转置得到以a为目的节点的最短路径树；
步骤S2.2:在最短路径树上，依次加入各个SDN节点流量可路由的相邻边，使用拓扑排序算法检查看是否会构成回路；如果加入SDN节点的相邻某条边不会构成回路，那么就将该边加入；否则，移除该边；得到一个基于该混合网络拓扑的流量可路由图PPG；
步骤S2.3:重复步骤S2.1-S2.2，找到网络拓扑中的每一个节点的可路由图PPG；
步骤S2.4:在得到的所有流量的可路由图PPG上，采用Yen’s算法找到每一个流量需求源目的节点对之间的所有路径。
进一步的，所述步骤S3具体为：
步骤S3.1:根据多商品流问题模型中的流量需求满足约束，链路容量约束，流守恒的约束，列出相关线性约束，优化目标是最小化最大链路利用率，具体如下所示：
Figure BDA0002566913080000031
Figure BDA0002566913080000032
Figure BDA0002566913080000033
其中，U是网络最大链路利用率，x(p)表示路径p上的流量分配；c(e)是链路e的链路容量
步骤S3.2:使用线性规划求解工具，CPLEX或者Gurobi完成线性规划问题的求解，将满足x(p)＞0的所有路径加入到集合
Figure BDA0002566913080000045
进一步的，所述步骤S4具体为：
步骤S4.1:对于每一个流量需求，按照概率
Figure BDA0002566913080000041
随机选取路径
Figure BDA0002566913080000042
加入到最终的路径集合
Figure BDA0002566913080000043
并将路径p从
Figure BDA0002566913080000044
中移除；
步骤S4.2:当前选取路径数目加1.重复步骤3.1，直到对于该流量需求选取h条路径；
步骤S4.3:：重复步骤S3.1-S3.2，对每一个流量需求都找到路径数目约束h下的最优路径集合。
本发明与现有技术相比具有以下有益效果：
本发明能够实现在有路径数目约束的情况下，有效降低网络的最大链路利用率，进一步提高网络性能。
附图说明
图1是本发明一实施例中的方法流程图。
具体实施方式
下面结合附图及实施例对本发明做进一步说明。
请参照图1，本发明提供一种混合SDN场景下带有路径数目约束的路由优化方法，包括以下步骤：
步骤S1：使用贪心算法确定SDN节点的部署位置；
步骤S1.1：先计算流量按照源目的节点之间最短路径路由得到的网络流量分配情况，得到每条链路上的链路利用率，即链路负载和链路带宽的比值；
步骤S1.2：按照链路利用率从大到小排序，优先部署出链路利用率率较大的节点为SDN节点。
步骤S2：确定SDN节点部署位置后，找到所有源目的节点对之间流量需求的可行路径；
步骤S2.1：针对混合SDN网络拓扑中的节点a，选择使用迪杰斯特拉算法构造从a出发到其他每一个节点的最短路径树，将找到的图转置得到以a为目的节点的最短路径树；
步骤S2.2：在最短路径树上，依次加入各个SDN节点流量可路由的相邻边，使用拓扑排序算法检查看是否会构成回路。具体地，如果加入SDN节点的相邻某条边不会构成回路，那么就将该边加入；否则，移除该边。这样就得到了一个基于该混合网络拓扑的流量可路由图(Permissible Paths Graph,PPG)。也就是包含流量可以进行分流路由的所有路径的图。
步骤S2.3：重复步骤S1.1-S1.2，遍历网络拓扑中的每一个节点，找到以该节点为目的节点的可路由图。
步骤S2.4：在得到的所有流量的可路由图PPG上，使用Yen’s算法找到每一个流量需求源目的节点对之间的所有路径。
步骤S3：计算没有路径约束情况下流量在所有可行路径上的分配情况。具体地，根据多商品流问题模型中的流量需求满足约束，链路容量约束，流守恒的约束，列出相关线性约束。如下所示：
Figure BDA0002566913080000061
Figure BDA0002566913080000062
Figure BDA0002566913080000063
其中(1)为流守恒和流量需求满足约束。(2)是链路容量约束限制。(3)是非负性限制约束。U是网络最大链路利用率。优化目标是最小化最大链路利用率。x(p)表示路径p上的流量分配。c(e)是链路e的链路容量。使用线性规划求解工具，CPLEX或者Gurobi进行可以完成该线性规划问题的求解。把满足x(p)＞0的所有路径加入到集合
Figure BDA0002566913080000064
步骤S4：设置路径数目的限制为h。根据路径数目的约束，使用随机取整从每个流量需求的所有可行路径中选出满足路径数目约束的路径。
步骤S4.1:对于每一个流量需求，按照概率
Figure BDA0002566913080000065
随机选取路径
Figure BDA0002566913080000066
加入到最终的路径集合
Figure BDA0002566913080000067
并将路径p从
Figure BDA0002566913080000068
中移除。
步骤S4.2：当前选取路径数目加1.重复步骤3.1，直到对于该流量需求选取h条路径。
步骤S4.3：重复步骤3.1-3.2，对每一个流量需求都找到路径数目约束h下的最优路径集合
Figure BDA0002566913080000069
步骤S5:根据多商品流问题，计算流量在路径
Figure BDA0002566913080000071
上的最优分流,完成路由优化。
以上所述仅为本发明的较佳实施例，凡依本发明申请专利范围所做的均等变化与修饰，皆应属本发明的涵盖范围。

Claims (1)

1.一种混合SDN场景下带有路径数目约束的路由优化方法，其特征在于，包括以下步骤：
步骤S1：采用贪心算法确定SDN节点的部署位置；
所述步骤S1具体为：
步骤S1.1：计算流量按照源目的节点之间最短路径路由得到的网络流量分配情况，得到每条链路上的链路利用率；
步骤S1.2：按照链路利用率从大到小排序，优先部署出链路利用率大的节点为SDN节点；
步骤S2：根据SDN节点的部署位置，找到所有源目的节点对之间流量需求的可行路径；
所述步骤S2具体为：
步骤S2.1：针对混合SDN网络拓扑中的节点a，选择使用迪杰斯特拉算法构造从a出发到其他每一个节点的最短路径树，将找到的图转置得到以a为目的节点的最短路径树；
步骤S2.2：在最短路径树上，依次加入各个SDN节点流量可路由的相邻边，使用拓扑排序算法检查看是否会构成回路；如果加入SDN节点的相邻某条边不会构成回路，那么就将该边加入；否则，移除该边；得到一个基于该混合网络拓扑的流量可路由图PPG；
步骤S2.3：重复步骤S2.1-S2.2，找到网络拓扑中的每一个节点的可路由图PPG；
步骤S2.4：在得到的所有流量的可路由图PPG上，采用Yen’s算法找到每一个流量需求源目的节点对之间的所有路径；
步骤S3：计算没有路径约束情况下流量在所有可行路径上的分配情况；
所述步骤S3具体为：
步骤S3.1：根据多商品流问题模型中的流量需求满足约束，链路容量约束，流守恒的约束，列出相关线性约束，优化目标是最小化最大链路利用率，具体如下所示：
minimize U
Figure FDA0002994339590000021
Figure FDA0002994339590000022
Figure FDA0002994339590000023
其中，U是网络最大链路利用率，x(p)表示路径p上的流量分配；c(e)是链路e的链路容量；
步骤S3.2：使用线性规划求解工具，CPLEX或者Gurobi完成线性规划问题的求解，将满足x(p)＞0的所有路径加入到集合
Figure FDA0002994339590000028
；
步骤S4：设置路径数目的约束为h，使用随机取整从每个流量需求的所有可行路径中选出满足路径数目约束的最优路径，得到最优路径集；所述步骤S4具体为：
步骤S4.1：对于每一个流量需求，按照概率
Figure FDA0002994339590000024
随机选取路径
Figure FDA0002994339590000025
加入到最终的路径集合
Figure FDA0002994339590000026
并将路径p从
Figure FDA0002994339590000027
中移除；
步骤S4.2：当前选取路径数目加1，重复步骤4.1，直到对于该流量需求选取h条路径；
步骤S4.3：重复步骤S4.1-S4.2，对每一个流量需求都找到路径数目约束h下的最优路径集合；
步骤S5：根据最优路径集，考虑多商品流问题，计算流量在路径上的最优分流。
CN202010633665.1A 2020-07-02 2020-07-02 混合sdn场景下带有路径数目约束的路由优化方法 Active CN111800339B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202010633665.1A CN111800339B (zh) 2020-07-02 2020-07-02 混合sdn场景下带有路径数目约束的路由优化方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202010633665.1A CN111800339B (zh) 2020-07-02 2020-07-02 混合sdn场景下带有路径数目约束的路由优化方法

Publications (2)

Publication Number Publication Date
CN111800339A CN111800339A (zh) 2020-10-20
CN111800339B true CN111800339B (zh) 2021-06-01

Family

ID=72810079

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202010633665.1A Active CN111800339B (zh) 2020-07-02 2020-07-02 混合sdn场景下带有路径数目约束的路由优化方法

Country Status (1)

Country Link
CN (1) CN111800339B (zh)

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN113347514B (zh) * 2021-06-22 2023-05-02 重庆邮电大学 基于多路径生存性保护的软件定义光网络控制器部署方法
CN115297048B (zh) * 2022-07-07 2023-04-07 北京瑞祺皓迪技术股份有限公司 一种基于光纤网络的路由路径生成方法及装置

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1756233A (zh) * 2004-09-30 2006-04-05 富士通株式会社 电信网络中的路由选择方法和装置
CN101990135A (zh) * 2009-07-30 2011-03-23 中兴通讯股份有限公司 一种基于最大带宽约束的路径查询方法和装置
CN106230737A (zh) * 2016-07-19 2016-12-14 国网辽宁省电力有限公司鞍山供电公司 一种状态感知的软件定义组网方法
US10321409B2 (en) * 2013-10-28 2019-06-11 Huawei Technologies Co., Ltd. System and method for joint power allocation and routing for software defined networks

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9634867B2 (en) * 2014-05-02 2017-04-25 Futurewei Technologies, Inc. Computing service chain-aware paths
CN107317697B (zh) * 2017-05-25 2020-01-07 清华大学 一种ospf与sdn混合网络的路由配置方法
CN110971521B (zh) * 2018-09-29 2022-09-13 中兴通讯股份有限公司 路由路径计算方法、系统、设备及计算机可读存储介质
CN109194577B (zh) * 2018-10-23 2020-04-10 清华大学 一种基于部分部署的分段路由网络的流量工程方法及装置
CN109617819B (zh) * 2019-01-29 2021-06-08 南京邮电大学 基于流量分类的软件定义回程网络路由方法

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1756233A (zh) * 2004-09-30 2006-04-05 富士通株式会社 电信网络中的路由选择方法和装置
CN101990135A (zh) * 2009-07-30 2011-03-23 中兴通讯股份有限公司 一种基于最大带宽约束的路径查询方法和装置
US10321409B2 (en) * 2013-10-28 2019-06-11 Huawei Technologies Co., Ltd. System and method for joint power allocation and routing for software defined networks
CN106230737A (zh) * 2016-07-19 2016-12-14 国网辽宁省电力有限公司鞍山供电公司 一种状态感知的软件定义组网方法

Non-Patent Citations (4)

* Cited by examiner, † Cited by third party
Title
Incremental deployment for traffic engineering in hybrid SDN network;Yingya Guo; Zhiliang Wang; Xia Yin; Xingang Shi; Jianping Wu; Ha;《2015 IEEE 34th International Performance Computing and Communications Conference (IPCCC)》;20160218;全文 *
Optimize Routing in Hybrid SDN Network with Changing Traffic;Yingya Guo; Zhiliang Wang; Xia Yin; Xingang Shi; Jianping Wu;《2017 26th International Conference on Computer Communication and Networks (ICCCN)》;20170918;全文 *
Traffic Engineering in SDN/OSPF Hybrid Network;Yingya Guo; Zhiliang Wang; Xia Yin;《2014 IEEE 22nd International Conference on Network Protocols》;20141211;全文 *
面向流量工程的互联网域内路由优化研究;郭迎亚;《CNKI博士论文全文数据库》;20190601;全文 *

Also Published As

Publication number Publication date
CN111800339A (zh) 2020-10-20

Similar Documents

Publication Publication Date Title
CN101965715B (zh) 最短路径确定中的打破平局
Narvaez et al. New dynamic SPT algorithm based on a ball-and-string model
TWI493926B (zh) 複雜型樹狀網路之自動化訊務工程
CN103379032B (zh) 跨域端到端路由的获取方法及装置、子路由计算实体
CN107666412B (zh) 服务功能链的虚拟网络功能部署方法
CA2882535C (en) Control device discovery in networks having separate control and forwarding devices
Garcia-Luna-Aceves et al. Distributed, scalable routing based on vectors of link states
CN109194577A (zh) 一种基于部分部署的分段路由网络的流量工程方法及装置
CN103873363B (zh) 一种电力光纤通信网业务的双路由配置方法
CN107888496A (zh) 用于标签交换路径的多个路径计算
CN101483610B (zh) 链路状态路由协议的路由更新方法
WO2016086709A1 (zh) 实现容量规划的方法和装置
CN107317697B (zh) 一种ospf与sdn混合网络的路由配置方法
CN108718246B (zh) 一种面向网络功能虚拟化的资源调度方法和系统
CN108965141A (zh) 一种多路径路由树的计算方法及装置
CN111800339B (zh) 混合sdn场景下带有路径数目约束的路由优化方法
CN113242179B (zh) 一种基于sdn的sr路径计算和标签栈生成的方法及sdn控制器
CN109768924A (zh) 一种面向多流共存的sdn网络多链路故障恢复方法及系统
WO2014180448A1 (zh) 一种对ptn网络业务进行保护的方法及装置
CN112887202A (zh) 一种基于子拓扑网络的sdn链路故障网络收敛方法
CN113328950B (zh) 一种基于树状结构的sdn路由系统构建方法
CN108243123A (zh) 广播报文的处理方法、装置、控制器和交换机
CN109246013A (zh) 一种fc-ae-1553交换型网络中的路由方法
CN104270313A (zh) 一种网络链路利用率调节方法
CN108966053A (zh) 一种多域网络动态域序列跨域路由计算方法及装置

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