【作者】 李毅超；

【导师】 章小宁；

【作者基本信息】 电子科技大学 ， 工程硕士（专业学位）， 2018， 硕士

【摘要】 在互联网高速发展的今天,网络已经深入到人们生活的每个方面,网络的韧性技术研究也越来越受到人们的重视。软件定义网络(Software-Defined Networking,SDN)作为一种在交换机中配置流表项来转发流量的新型网络架构,具有结构灵活、集中配置、网络业务快速部署的特点,可以很好地来研究网络韧性问题。本文主要研究在软件定义网络架构下在单链路失效场景中的流表项压缩问题。文章提出流表项共享和流表项复用两种机制,在保证网络快速应对单链路失效的同时,最小化网络中所使用的流表项总数。在流表项共享机制中,本文实现了两种情景下的共享。第一种是备份流表项之间的共享,第二种是备份流表项和工作流表项的共享。采用这样的方法,流表项数目得到了极大地减少。因此,在考虑三态内容寻址存储器(Ternary Content Addressable Memory,TCAM)大小的限制下,本文将流表项共享机制引入SDN保护中,并为这个问题建立了整数线性规划(Integer Linear Programming,ILP)模型。因为这个问题是NP-hard的,为了更有效地去解决这个问题,本文提出了流表项共享保护(Flow Entry Sharing Protection,FESP)的启发式算法。通过仿真结果可以看出,该算法明显减少了网络中所需要配置的流表项总数。在流表项复用机制中,首先定义了复用段的概念。本文将经过同一复用段的多条业务流聚合成一条流,并使用VLAN ID作为这条聚合流的标签。采用这样的方法,所需的流表项数目得以大大减少。本文将流表项复用机制引入SDN保护中,以达到保证网络生存性和最小化流表项总数的目的。文中在资源受限的SDN网络中为这个问题建立了ILP模型,并证明了这是一个NP-hard问题。随后,本文使用马尔可夫近似技术设计了一个近似最优算法来解决这个问题。理论分析表明本文设计的算法能够生成近似最优解。大量的仿真结果表明,与其他类似算法相比,本文的算法能够明显减少网络中需要配置的流表项总数。更多还原

【Abstract】 With the rapid development of the Internet,the network has penetrated into every aspect of people’s life.The research of network resilience technology has also received increasing attention.The Software-Defined Networking(SDN)paradigm supports deploying traffic flows dynamically by a centralized controller to SDN switches.In particular,the controller configures forwarding rules in SDN switches to route traffic flows.With the characteristics of flexible structure,centralized configuration,and rapid deployment of network services,it is possible to study the network resilience technology well.This thesis mainly studies the flow entry compressing problem in a single link failure scenario in SDN.Flow entry sharing and flow entry multiplexing are proposed.These two methods are considered to minimize the total number of flow entries while guaranteeing traffic survivability against a single link failure.In the method of flow entry sharing,we introduce two cases of flow entry sharing:(1)sharing between backup flow entries;(2)sharing between working flow entry and backup flow entry.In this way,the number of flow entries is greatly reduced.In this way,the total number of flow entries can be reduced greatly.To this end,we consider the limited size of Ternary Content Addressable Memory(TCAM)in SDN switches,and employ flow entry sharing in SDN protection.We first present the problem as an Integer Linear Programming(ILP)model,and then design a greedy based heuristic algorithm named Flow Entry Sharing Protection(FESP).Extensive simulation results show that compared with the previous SDN protection algorithms,FESP significantly reduces the total number of flow entries.In the method of flow entry multiplexing,we first give the definition of multiplexing segment.We multiplex traffic flows traversing through the same multiplexing segment into an aggregated flow with the label of VLAN ID.Thus,multiple flow entries are merged into one multiplexed flow entry.In this way,the total number of flow entries can be reduced greatly.We also extend the method to SDN protection,and reduce the number of backup flow entries.We formulate this problem as an ILP model.Since this problem is NP-hard,we design a polynomial algorithm using the Markov approximation technique.Theoretical analysis indicates that the polynomial algorithm generates near-optimal solution.The extensive emulation results show that compared with the benchmark algorithms,the proposed Markov approximation based algorithm reduces the total number of flow entries significantly.更多还原