网络虚拟化服务之软件定义网络新机制 A New Mechanism for SDN Network Virtualization Service_thiran公式是什么公式

A New Mechanism for SDN Network Virtualization Service

ChangchengHuang

Departmentof Systems and Computer Engineering

CarletonUniversity

Ottawa,Canada

huang@sce.carleton.ca

JiafengZhu, Min Luo, Wu Chou

HuaweiTechnologies Inc.

SantaClara, US

{jiafeng.zhu,min.ch.luo, wu.chou}@huawei.com

Abstract— Software Defined Network (SDN) is becoming anew paradigm for both WAN and enterprise networks. By separating control anddata planes, SDN allows network providers to sell new services without changingtheir physical switches. One of the key services SDN can enable is networkvirtualization which allows a service provider to have a virtual slice of anetwork provider’s physical network. While this feature empowers serviceproviders to have dynamic networks, it is becoming more difficult for a networkprovider to statistically share its resource usage across multiple serviceproviders due to the fact that service providers are reluctant to share theiruser information. This paper presents a new scheme that empowers networkprovider to maximize statistical resource sharing with service guarantee whileminimizing information shared.

Keywords—Software Defined Network, Virtual Topology,OpenFlow, OFC

 

I.             INTRODUCTION

Research on SDN startednearly ten years ago. The motivation at that time was to design a new networkarchitecture that allows network managers to have more flexible control oftheir networks. Ethane [1], for example, was proposed in 2007 for enterprisenetworks. Ethane deployed simple flow-based Ethernet switches with acentralized controller that manages the admittance and routing of flows. Ethanewas implemented both in hardware and software with more than 300 wired orwireless hosts.

Most of earlier SDN networkswere designed for datacenter infrastructure [2] where flexibility andscalability are critical. With tens of thousands commodity switches andservers, datacenter presents a serious challenge to network management. SDNsolves the problem by separating control plan from data plane. With relativelyan independent control plane, SDN does not need to be run on proprietaryequipment. Instead, the control plane can be implemented with a large number ofregular servers. By using a centralized structure, these servers can beefficiently supported by datacenter with on-demand service capacity.

In recent years,SDN has found applications in other areas.Google, for example, built a large scale SDN-based WAN network [3] that hasattracted attentions worldwide. Large carriers are looking at the possibilityof upgrading their network infrastructures with SDN architecture. One issue tobeaddressed first is scalability. Some recent study has investigated thescalability issue related to SDN architecture. Early benchmarks on NOX [4] (thefirst SDN controller) showed it could only handle 30,000 flow initiations persecond while maintaining a sub-10 ms flow install time. Recent works have shownthat SDN scalability can be extended by using multicore systems [5] ordeploying multiple OpenFlow controllers (OFCs) [6].

With a separated controlplane, SDN has the potential to enable new services. One of the primary newservices that have been envisioned is the virtual topology service, whichallows network provider to sell different virtual topologies to differentservice providers. Each service provider can use its virtual topology just likethe way it uses its own private network while sharing underlying physicalnetwork resources with other service providers. The network provider, on theother hand, can enjoy new revenue growth through selling virtual topologieswith different granularities. This benefit, however, does not come without achallenge. One of the key issues is the division of ownership, which makesstatistical resource sharing more difficult. This issue has not been fullyaddressed yet. This paper is targeted at this issue in specific. Our goal is toprovide statistical guarantee to service providers while allowing networkprovider to enjoy multiplexing gain.

The paper is organized asfollows. In Section II, we will discuss more detail about the issue to beresolved. In Section III, we will propose a new and practical scheme thatallows each entity to exercise its own authority while achieving gain inresource saving. This will be followed by more description about how parameterswill be calculated in Section IV. Numerical results will be presented inSection V. We will finish the paper with some concluding remarks in Section VI.

II.                                 TOPOLOGY ABSTRACTION AS A SERVICE

The initial SDN adopters, both vendors and networkproviders, have focused on some fundamental issues related to separatingcontrol and data planes. The benefits of network virtualization have not beenfully explored. A good example is the Google SDN WAN project mentioned earlier[3]. It should be noted that Google’s WAN is a special case where Google is theuser, service provider, as well as network provider, i.e., Google providesservice to itself on its own network. This nature allows Google to do globaloptimization easily. Forexample, because Google can control the traffic carriedby the WAN, operators can decide when and how long the elastic traffic will bebuffered. Also because Google owns both service network and underlying WANnetwork, operators can have a global view of the network and therefore optimizenetwork usage globally.

In a real world, it is quitecommon that users, service providers, and network providers are separateentities. They may all have their own objectives which may conflict with eachother. Take the example of enterprise network. With the fast growth ofdatacenters, enterprises are becoming increasingly interested in outsourcingtheir enterprise networks to datacenters. Under this scenario, the owner of thenetwork now is the owner of the datacenter, such as Amazon. The serviceproviders are the enterprises who outsource their enterprise networks to thedatacenters. Therefore a service provider is independent from the networkprovider as well as independent from other service providers who share the samephysical network. Recognizing this need, the pioneers of SDN advocate a layercalled FlowVisor [7] which plays the same role as the hypervisor for virtualmachines. FlowVisor allows a network provider to partition its physical networkinto slices for various service providers. Each service provider can virtuallyown one slice which has its own virtual network topology and related resources generatedthrough a topology abstraction process. The service provider can then optimizeits usage of the slice which it owns. A network provider can sell virtualtopology service to service providers with different granularities selling atdifferent prices [8]. This will change the situation that network providerstoday can only sell pipes and equip network providers a new venue for revenuegrowth. The SDN architecture for topology abstraction service is shown inFigure 1. As shown in the figure, each entity has its own OpenFlow Controller(OFC). The OFC of a service provider is in charge of routing user flows andoptimizing resource usage within its own virtual topology. The OFC of thenetwork provider will execute the topology abstraction process through a topologyvirtualizer based on a global topology map of the underlying physical network.

While virtual topology allowsa network provider to sell topology abstraction service to service providers,it also makes the network provider partially lose the control of its resourceallocation capability. After selling a virtual topology to a service provider,the network provider has no control of how user traffic will be routed withinthe virtual topology owned now by the service provider. This makes the network providerdifficult to optimize its resource usage across multiple service providers.There are several situations that make the issue particularly thorny:

     I.         A service provider may not be legally allowed to discloseinformation about the traffic of its individual users (also called micro-flowinformation) to the network provider although service providers can provideaggregate information such as mean and peak rates of a virtual link. A virtuallink typically carries large number of micro-flows.

     II.         Aservice provider may be a competitor of the network provider. For example, RIMuses Amazon cloud servicewhile it is also a competitor with Amazon in tablet devices.

The network provider may not want to disclose its networkusage information to a service provider in afraid of the service provider usingthe information to bargain.

Fig. 1.SDN architecture forvirtual network service.

 

In general, each entity tendsto disclose as little information as possible due to various legal andcommercial reasons. Therefore the topology abstraction process is also aninformation-filtering process that tries to minimize the information exchangedbetween different entities.

The reality that there aremultiple authorities with limited shared information has made resource sharingextremely difficult. This issue has not been addressed in literature as well asin practice. Existing mapping solutions [9-11] for virtual topology servicesare typically based on the assumption that service providers will provide abandwidth requirement for each virtual link to their network provider. Thenetwork provider then generates the virtual topologies with requiredbandwidths. No statistical sharing among the reserved bandwidths for differentvirtual links sharing a physical link is allowed. On the other hand, it is alsodifficult for a service provider to know exactly how much traffic it can put ona virtual link without suffering performance degradation because the serviceprovider has no information about the characteristics of other virtual networkssharing the same physical network. This leaves a service provider no choice butto conservatively engineer the peak rate on each virtual link to be below theguaranteed fixed bandwidth. While this makes the formulation of the virtualnetwork mapping problem easier, it is a loss of network utilization for thenetwork provider because it cannot take advantage of the dynamic nature of thetraffic carried by each virtual link. In this paper, we call this kind ofservice as wired virtual topology service.

In the following section, wewill propose a new service and a practical and effective mechanism that willhelp a network provider maximize its network utilization while providingstatistical guarantee to service providers.

III.             VIRTUAL TOPOLOGY WITH STATISTICAL GUARANTEE

We consider the case thatnetwork provider and service providers are separate entities. Service providersbuy their virtual topologies from a network provider. Different virtualtopologies share a physical network owned by the network provider. The OFC ofeach entity is trying to maximize its own profit through maximizing itsvirtual/physical network utilization. We propose a new service called elasticvirtual topology service that allows a network provider to utilize itsresources more efficient while minimizing the information to be shared betweenthe network provider and its clients, service providers.

With the elastic virtualtopology service, a service provider receives a statistical guarantee thatpromises a) the service provider can send its traffic on each virtual link asit is with a negotiated low congestion probability； b) the service provider canstill have a negotiated minimum bandwidth when congestion happens. In return,the service provider needs to provide some basic characteristics of its trafficcarried by each virtual link. It should be noted that each virtual link maycarry numerous micro-flows. The information to be shared is the aggregatedtraffic characteristics of the virtual link rather than individual micro-flows.In this way, the service provider can still hide information about its usersfrom network provider while the latter can achieve scalability through handlingaggregate traffic instead of individual micro flows.

In specific, wepropose the following Virtual Topology with Statistical Guarantee (VTSG)scheme. To start with, a service provider sends a request to network providerwith a description of the requested virtual topology and associated mean andpeak rate for each virtual link instead of sending topology request withassociated bandwidths. Different from bandwidths, the mean and peak rates of avirtual link are decided by the user traffic and routing algorithm used by theservice provider, which are under the control of the service provider.Therefore it is possible for the service provider to estimate these statisticsbased on its user profile. On the other hand, the bandwidth received by avirtual link will be dynamic and depend on traffic characteristics of othervirtual links sharing the same physical link for statistical multiplexing gainand can only be decided by the network provider who has information abouttraffic characteristics of all virtual links sharing the physical link.

The network provider will usethe mean and peak rates to calculate a minimum bandwidth that is higher thanthe mean rate of the virtual link but smaller than its peak rate with a highpercentage (say 99.9%) guarantee that the virtual link will be able to send itstraffic as it is without congestion. When congestion does happen, the virtuallink will be guaranteed with the minimum bandwidth. When a virtual linktraverses multiple physical links, the minimum bandwidth the virtual link canget will be the smallest of the minimum bandwidths supported by all theinvolved physical links.

Equipped with a way to calculate the minimum bandwidthrequired for each virtual link, the network provider will then map the virtualtopology by formulating it as an optimization problem with the minimumbandwidths as the demands. To this end, there are various existing approachessuch as those in[9-11] can be applied. So our focus inthis paper will be on thecalculation of the minimum bandwidth rather than on theformulation of the mapping problem. It is important to note that the complexityof calculating the minimum bandwidth has a significant impact on the complexityof the mapping algorithms. That is why existing approaches [9-11] assume thebandwidth requirement for each virtual link is simply a constant which does notdepend on other virtual links sharing the same physical link. Our goal is tofind a way that existing approaches such as those in [9-11] can be directlyapplied without any changes.

After mapping is done, thenetwork provider will then notify the service provider of the minimum bandwidthfor each virtual link and the guaranteed performance. Without congestion,service providers are allowed to send their natural traffic as it is. Whencongestion happens at a physical link, the network provider will send alerts tothe service providers sharing the physical link and shape those virtual linkswith elastic virtual topology service to their minimum bandwidths.

Upon receiving alerts, thoseservice providers will decide how to route their user traffic within theirvirtual networks to avoid their congested virtual links and minimize the impacton their virtual networks. For example, if a service provider is using OSPFrouting protocol, the service provider can simply increase the costs of thosecongested links. Traffic will then be diverted to other uncongested links.Certainly, other more sophisticated optimization approaches can be used withSDN centralized control architecture. It is important to note that our VTSGapproach allows network provider and service provider to make their separateresource usage decisions while sharing minimum amount of information.

Our objective in the nextsection is to develop a method for calculating the minimum bandwidth for eachvirtual link so that a) it allows statistical multiplexing across differentvirtual links sharing the same physical link； b) all existing topology mapping algorithms such as thosein [9-11] can still be applied using the minimum bandwidths as virtual linkdemands.

IV.                            MINIMUM BANDWIDTH CALCULATION

Under the Quality of Serviceresearch area, numerous ways have been developed to calculate congestionprobability and bandwidth requirement (e.g. [12]). Most of these approachesrequire detail traffic characteristics of underlined micro-flows and complexanalytical manipulations. Under our context, micro-flow information ofindividual users is not available and complex analytical manipulations willmake the topology mapping becoming more complex and intractable. Our objectiveis to find a practical approach that allows a SDN controller of a network providerto calculate the minimum bandwidth for each virtual link under the VTSG servicewith limited information while achieving multiplexing gain. To meet thesechallenges, we propose the following approach.

Weconsider the scenario that a physical network has received R virtual network requests. The virtual links of the R virtual network requests constitute aset L. We assume that each serviceprovider will inform the network provider of its requested virtual networktopology and mean and peak rates of the traffic associated with each virtuallink. The informationshared is aggregate because each virtual link carrieslarge number of micro-flows. This kind of information sharing is the minimumrequired for virtual topology service.

A simple example is shown in Figure2 where a physical network includes four nodes (Nodes A, B, C, D) and fivelinks (Links (A, B), (B, C), (C, D), (D, A) (A, C) as shown in solid lines).Two virtual topologies are generated out of the physical network. One virtualtopology includes virtual nodes A, B, C and virtual links (A, B)₁,(B, C)₁, (A, C)₁ as shown in dashed lines. The otherincludes virtual nodes A, C, D and virtual links (A, C)₂, (C, D)₂and (D, A)₂ as shown in dash-dotted lines. Here we assume virtualnodes happen to overlap with physical nodes to simplify our notations. It iseasy to see that physical link (A, C) carries two virtual links (A, C)₁and (A, C)₂.

Due tothe fact that we do not have information about the characteristics ofindividual micro-flows within a virtual link, we need to capture the nature ofthe aggregate traffic with a virtual link directly. To this end, we assume thatthe traffic carried by each virtual link can be modeled by a Gaussian process.This is a valid assumption in most cases because a virtual link typicallycarries a large number of micro-flows which lead to Gaussian process based onCentral Limit Theorem. Many measurements have confirmed that aggregate Internettraffic indeed follows Gaussian processes [13].

 

In general, we assume each virtual link l, where ∈ , carriesGaussian traffic with mean rate ml and peak rate pl as announced by thecorresponding tenant. After receiving mean rate ml and peak rate pl for all ∈ ,the network provider needs to calculate a minimum bandwidth bl for each virtuallink.

Wedenote the standard deviation of the Gaussian trafficwith each virtual link asWe set qlas the -quantile of the Gaussian distribution where will bedecided by the network provider and can be kept constant for all virtual links.When αis very small, the quantile value qlwill happen rarely. Therefore qlcan be roughly treated as the peakrate, i.e.

whereerf ( ) is the error function of Gaussian distribution. The actual value for αwill be decided by the service provider. We denote

Thisleads us to

                   

Wefirst focus on the case that a virtual link will be mapped to a single physicallink. We willdiscuss more general cases in the latter part of this section.Suppose there are Lsvirtual links sharing a substrate physical link s. Withoutloss of generality, we assume these virtual links areindexed 1, 2,…, Ls. It iseasy to see that the aggregate traffic on the physical link is still a Gaussianprocess

                       

Fig. 2.  A sample physicalnetwork with two virtual topologies generated.

with amean  and standard deviationSimilarly let qbe the β-quantile ofthe aggregate traffic. Then we have

If we provision the bandwidth capacity ofthe physical link as b≥q,congestion will happen with a probability less than β. Therefore by controllingb, we can achieve any guaranteed congestion probability β.

The next issue is how to assign thiscapacity to individual virtual links so that a virtual link can have a minimumbandwidth guarantee when congestion does happen. We adopt a simple approachwhere the minimum bandwidth assigned to each virtual link is calculated as thefollowing:

                    

Therefore b≥q issatisfied. The reason for this simple approach is that the physical network hasvery little knowledge of the individual traffic flow routed in each virtualtopology. This makes it very hard to apply other fairness approaches such asMax-min [5]. However while being simple as it is, it is still more complex thana constant bandwidth as existing algorithms have typically assumed.

Combining Eqs. (1) to (4), we can seethat bldepends on ml’s and pl’s ofall the virtual links sharing the physical link as well as Ls, and furthermorethe relationship is nonlinear. This nonlinear relationship will make allexisting topology mapping algorithms such as those in [9-12] not applicable.The dependency on Lswill also make it infeasible because a network provider canonly know Lsafter optimization and mapping have been done, i.e., Ls is themapping result rather than mapping input. Therefore we need to further simplifyEq. (4) so that it forms a linear relationship and it does not depend on Ls.

We consider the scenarios where thetraffic carried by each virtual link is relatively small compared to thecapacity of the physical link. In specific, we assume that the variance of the trafficwithin each virtual link is upper bounded, i.e.

for , where Σis the upper bound. When veryfew virtual links are mapped to a physical link, the physical link is typicallyunderutilized. The physical link will not get congested no matter how muchminimum bandwidth is committed to each virtual link. So we will focus on those physicallinks hosting many virtual links, i.e. we assume the number of virtual linksmapped to a physical link is lower bounded, which means for all physical links, where Λis thelower bound. Then we have

Eq. (4) will be satisfied. This means thatthe congestion probability for the virtual link lwill be smaller than β. AlthoughEq. (5) is looser than Eq. (4), we can see that, when Λgoesto infinity, the allocated bandwidth for each virtual link with Eq. (5)converges to its mean rate which is clearly the minimum bandwidth any approachcan assign with guaranteed performance. This is in clear contrast to peak rateallocation with the wired virtual topology service.

It is important to note that Eq. (5) isdifferent from Eq. (4) in the sense that blis only dependent on mlwhile allother parameters will be constant across all virtual links and all physicallinks. And furthermore, it does not depend on With this result, all existingtopology mapping algorithms will be valid without anychanges. So our objectivehas been achieved.

Now we will investigate the performanceof our proposed VTSG scheme in comparison with the wired virtual topology service.Because the mean rate mland peak rate plvary from virtual link to virtual link,in order to study the average performance, we consider ml’sand  pl’s asi.i.d. random variables respectively withBecause virtual networks are typicallyindependent, this assumption is roughly true in practice.

                       

With the wired virtual topology service,the bandwidth required by each virtual link denoted by will be its peak rate. We have

Nowwe can calculate how much bandwidth we can save in terms of percentage denotedby as

From Eq. (9), we can see that, whenΛincreases, i.e., the minimum number of virtual links sharing a physical link increases,the gain will also increase. When the number of virtual links sharing aphysical link is very small, the physical link becomes extremely unlikely toget congested. So it does not matter anymore in terms of how much bandwidth isassigned to each virtual link. Therefore, Eq. (5) can still be used.

When a virtual link is mapped to a paththat traverses multiple physical links, we can calculate the minimumbandwidthrequired for each physical link using similar approach and then take theirminimum as the minimum bandwidth for the virtual link. We will show somenumerical examples in the next section. If the traffic of a virtual link issplittable, we can model each portion of the splitted virtual link as aproportional amount of the whole virtual link traffic. This is typically the caseif ECMP protocol is applied. The above approach can then be applied to eachportion.

V.             NUMERICAL RESULTS

We now examine some numerical results. Wefirst want to see how the minimumbandwidtfor each virtual link changes withincreasing number of virtual links sharing thesame physical link. We assumeeach virtual link generates 1Gbps traffic in average and 1.3Gbps at peak. We set  ==0.1%. This means that the congestionprobability for each physical link is set as low as 0.1%. The result is shownin Figure 3. It is easy to see that the minimum bandwidth goes down withincreasing number of virtual links. More specifically, when there is only onevirtual link using the physical link, the minimum bandwidth is its peak rate,i.e., no multiplexing gain. However this is typically the case that thephysical link is underutilized due to the fact that the number of virtual linksis too small. Therefore no congestion issue exists for this case.

When the number of virtual links startsincreasing, the minimum bandwidth drops extremely fast at the beginning and flatsout later. This shows that it is quite effective to multiplex a small number ofvirtual links. We now compare the two types of services. In order to simplifythe parameter setting, we assume =and =Σ, both are roughly true in real situation.We rewrite Eq. (8) as follows:

             

Fig.3.Average minimum bandwidth for each virtual link vs. minimum number of virtuallinkssharing the same physical link. All virtual links have similar statisticalcharacteristics. Eachvirtual link carries traffic with average mean rate of1Gbps with average peak rate at 1.3 Gbps.

We defineas the coefficient of variation forthe traffic with each virtual link. We have

The results are shown in Figure 4, wherethe x-axis indicates Λand y-axis indicates . We can see that the saving increaseswith increasing numberof virtual links. The increase is more dramatic when thenumber of virtual links is small. Furthermore it also increases with increasingvariability of the traffic. The more variable the traffic, the more gain we canhave. When =0.3, i.e., the peak rate is about 90% more than the mean rate, thesaving is more than 30% with ten virtual links. This saving is significant.

VI.             CONCLUSION

By separating control plane from dataplane, SDN has the potential to allow network and service providers to create avariety of new services. Virtual topology is one of the most promising servicesSDN can provide. Through topology abstraction process, a network provider cansell virtual slices of its physical network to different service providers.Different service providers as tenants have full control of the virtual topologieswithin their own slices while the network provider has the control of its physicalnetwork. However lack of information about the micro-flows of each user makeseach owner difficult to explore statistical multiplexing gain.

This paper proposed VTSG as a new andpractical mechanism that allows a network provider to maximize statisticalmultiplexing gain while still provides certain guarantee to each tenant. Inaddition, our VTSG approach enables network provider and service provider tomake their separate resource usage decisions while sharing minimum aggregatevirtual link information.

Numerical results have shown thatsignificant gain can be achieved with relatively small number of tenants. Thisis veryencouraging because the number of tenants a network provider will hostmay be variable in a very wide range.

While achieving this multiplexing gain,we have made our method for minimum bandwidthcalculation to be independent fromother virtual links sharing the same physical link. This feature allows allexisting topology mapping algorithms applicable with our minimum bandwidthcalculation method.

          

Fig.4.  Average bandwidth saved vs. minimumnumber of virtual links.

REFERENCES

[1]  M. Casado, M. J.Freedman, J. Pettit, J. Luo, N.McKeownm S. Shenker, “Ethane:Taking Control of the Enterprise,” ACM SIGCOMM 2007, August 27-31, 2007, Kyoto.

[2]  M. Banikazemi, D.Olshefski, A. Shaikh, J. Tracey, and G Wang, “Meridian:An SDN Platform for Cloud Network Services,” IEEE Communications Magazine, Feb.2013

[3]  S. Jain, et al., “B4:Experience with a Globally-Deployed Software Defined WAN,” ACM SIGCOMM 2013,August 12-16, 2013, Hong Kong

[4]  A. Tavakkoli et al.,“Applying NOX to the Datacenter,” ACM Workshop on Hot Topics in Networks (HotNets-VIII),October 22-23, 2009, New York

[5]  A. Tootoonchina etal., “On Controller Performance in SoftwareDefined Networks,” 2^ndUSENIXHot-ICE’12, April 24, 2012, San Jose.

[6]  A. Tootoochian and Y.Ganjali, “Hyperflow: A Distributed Control Plane for OpenFlow,” USENIX NSDIINM/WREN, April 2010, San Jose

[7]  R. Sherwood, et al.,“FlowVisor: A Network Virtualization Layer,” OPENFLOW-TR-2009-1,OpenFlowConsortium, October 2009

[8]  D. Drutskoy, E.Keller, and J. Rexford, “Scalable Network Virtualization in Software DefinedNetworks,” IEEE Internet Computing, Vol. 17, Iss. 2, March, 2013.

[9]  N.M.M.K. Chowdhury,M.R. Rahman, and R. Boutaba, “Virtual Network Embedding with Coordinated Nodeand Link Mapping,” IEEE INFOCOM 2009, April 2009, Rio de Janeiro.

[10]  X. Cheng, et al.,“Virtual Network Embedding Through TopologyAware Node Ranking,” ACM SIGCOMMComputer Communication Review, Vol. 41, No. 2, April 2011.

[11]  J. He, et al.,“DaVinci: Dynamically Adaptive Virtual Networks for a Customized Internet,” ACMCoNEXT2008, Madrid, December 2008.

[12]  J.-Y. Le Boudec andP. Thiran, “Network Calculus: A Theory of Deterministic Queuing Systems for theInternet,” Springer, LNCS, 2001.

[13]  W. E. Leland, M. S.Taqqu, W. Willinger, D. V. Wilson, “On the Selfsimilar Nature of EthernetTraffic ,” IEEE/ACM Trans. Networking, Vol. 2, No.1, Feb. 1994.

 

     网络虚拟化服务之软件定义网络新机制

ChangchengHuang

加拿大渥太华卡尔顿大学

计算机系统工程系

huang@sce.carleton.ca

JiafengZhu, Min Luo, Wu Chou

华为技术有限公司

SantaClara, US

{jiafeng.zhu,min.ch.luo, wu.chou}@huawei.com

 

摘要：软件定义网络（SDN）正成为广域网和企业网络的一种新模式。SDN通过分离控制和数据平面允许网络提供商提供新的服务，而不改变它们的物理开关。SDN则是其中一个关键的服务，可以允许一个服务提供者有一个网络提供商的物理网络的一个虚拟网络。然而这个授权服务为动态网络，这使在多个服务资源共享变得更加困难商，因为运营商都不愿意分享他们的用户信息。本文提出了一种新的方案，它使网络运营商最大限度地利用统计资源共享服务保障，同时尽量减少信息的共享。

关键词：软件定义网络虚拟拓扑OpenFlow OFC（控制器）

 

 

一、引言

SDN近十年前开始研究。当时的动机是设计一个新的网络体系结构，它允许网络管理员能更灵活的控制自己的网络。例如乙烷[1]，2007年提出了企业网络。乙烷部署的简单的以太网交换机和一个集中控制器，管理流动的导纳和路由流程。乙烷在硬件和软件实现了300多个有线或无线主机。

最早期的SDN网络被设计用作数据中心基础设施[2]，灵活性和可扩展性是至关重要的。成千上万商品交换机和服务器、数据中心网络管理提出了严峻的挑战。SDN解决问题通过将控制计划从数据平面流动。相对独立的控制，SDN不需要专用设备上运行。相反，可以实现控制与大量的常规服务器。通过使用一个集中的结构，可以有效地支持这些服务器数据中心和提供服务能力。

近年来，SDN发现应用在其他领域。例如，谷歌建立了一个大规模SDN-基础广域网络[3]，吸引了全世界的关注。大型航空公司正在升级他们的网络基础设施，SDN架构成为了可行性。首先需要解决的一个问题是可伸缩性。最近的一些研究调查了SDN架构相关的可伸缩性问题。早期的基准NOX[4](第一SDN控制器)显示它每秒只能处理30000流量，同时保持sub-10毫秒安装时间。最近的工作表明，SDN可伸缩性可以延长使用多核系统[5]或部署多个OpenFlow控制器(OFCs)[6]。

分离控制平面，SDN有潜力启用新服务。其主要设想的新服务之一是虚拟拓扑服务，它允许网络提供商出售不同的虚拟拓扑给不同的客户。每个客户可以使用其虚拟拓扑就像使用自己的私有网络的方式，共享底层物理网络资源与其他客户。网络供应商，另一方面，通过销售虚拟拓扑可以享受新的收入通过不同的增长度。这个好处，然而也有一个挑战，其关键问题是服务的所有权，这使得统计资源共享更加困难。这个问题尚未完全解决。本文针对这个问题在特定的。我们的目标是提供统计保证服务提供商，同时允许网络提供商享受多路复用增益。

本文的结构如下，在第二节，我们将讨论更多的细节问题有待解决。在第三节，我们将提出一个新的和实用的方案，允许每个实体行使自己的权力，同时实现增益资源节约。这之后，将在第四节更多的描述如何进行参数计算。将在第五节提交数值结果和完成的文件。在第六节作一些总结性发言。

二、     拓扑抽象作为一种服务

最初的SDN采用者，供应商和网络提供商，专注于一些基本的控制和数据分离平面有关的问题。网络虚拟化的好处没有被充分研究。一个很好的例子是前面提到的谷歌SDN广域网项目[3]。应该注意的是，谷歌的广域网是一个特例，谷歌用户，服务提供者，以及网络提供商，即谷歌提供的服务本身的网络。这个特性允许谷歌轻易进行全局优化。例如，因为谷歌可以控制交通由广域网，运营商可以决定什么时候，多长时间弹***通将缓冲。也因为谷歌拥有潜在服务网络和广域网网络，运营商可以有一个全球的网络，因此优化网络在全球范围内使用。

在现实生活中，这是很常见的用户，服务提供商和网络提供商分离的实体。它们全部具有可彼此冲突目标。取企业网络的例子。随着数据中心的快速增长，企业正在成为他们的外包企业网络数据中心越来越感兴趣。在这种情况下，网络的管理者现在是数据中心，如亚马逊的所有者。服务供应商是谁，他们的外包企业网络到数据中心的企业。因此服务提供商独立于网络供应商，以及独立于其他的服务提供商谁共享相同的物理网络上。认识到这方面的需求，SDN的先驱倡导一种叫做FlowVisor层[7]起着作为管理程序与虚拟机相扮演同的角色。 FlowVisor允许网络提供商及其物理网络关于各种服务提供商服务划分。每个服务提供商可以实际上拥有一个片有其自己的虚拟网络拓扑，并通过拓扑抽象过程中产生的相关资源。则服务提供商可以优化其使用它所拥有的子网。网络提供商可以使用不同的速度卖不同价格[8]卖虚拟拓扑服务的服务提供商。这将改变，今天的网络供应商只能销售管道和装备网络供应商的新场地的收入增长的局面。在SDN架构拓扑抽象服务被示于图1。如该图所示，每个实体有它自己的OpenFlow控制器（OFC）。一个服务提供者的OFC是负责路由用户流量和其自己的虚拟拓扑中优化资源使用的。网络提供商的OFC将通过基于基础物理网络的全球拓扑图拓扑虚拟器执行拓扑抽象过程。

尽管虚拟拓扑允许网络提供商拓扑抽象服务卖给服务提供者，这也使得网络提供者部分失去控制的资源配置功能。出售虚拟拓扑服务提供者之后，网络提供商没有控制如何在虚拟拓扑路由用户流量由服务提供者拥有现在。这使得网络提供者很难优化资源使用多个服务提供者。有几种情况下使特别棘手的问题:

（1）             服务提供商可能不会允许合法地披露其个人用户（也称为微流信息）网络提供商的交通信息，虽然服务提供商可以提供综合信息，如均值和峰值速率虚连接的虚拟链路通常携带大量微流。

（2）             一个服务提供者可能是一个网络提供商的竞争对手。例如，RIM使用亚马逊的云服务，同时也是竞争对手与亚马逊的平板电脑。网络提供商可能不希望披露其网络使用信息服务提供者在服务提供者害怕使用信息来讨价还价。

图1.SDN虚拟网络服务体系结构

一般来说，由于各种法律和商业原因，每个实体供应商倾向于披露尽可能少的信息。因此拓扑抽象过程也是一个信息过滤的过程，试图最小化不同实体之间交换的信息。

事实上，有多个部门在有限的共享信息，取得了资源共享非常困难。这个问题一直没有得到解决在文学以及在实践中。现有映射方案[9-11]对虚拟拓扑服务通常基于这样的假定，服务提供商将提供给他们的网络提供商的每个虚拟链路的带宽要求。网络提供商然后生成具有所需频带的虚拟拓扑。保留的带宽不同的虚拟链路共享一个物理链路间无统计学共享是允许的。另一方面，它也难于对一个服务提供商确切地知道多少流量它可以把在虚拟链路而不遭受性能降低，因为服务提供者不具有关于其他虚拟网络共享相同的物理网络的特性的信息。这使得服务供应商别无选择，只能保守工程师每个虚拟链路峰值速率是在保证固定带宽以下。尽管这使得在虚拟网络映射问题的制剂更容易，这是网络利用率为网络提供商的损失，因为它不能利用由每个虚拟链路承载的通信量的动态特性的优势。在本文中，我们称这种服务为有线虚拟拓扑服务。

在下面的章节中，我们将提出一个新的服务和切实有效的机制，这将有助于网络提供商最大限度地发挥其网络使用率，同时提供统计保障服务供应商。

三、     虚拟拓扑统计

我们认为，网络提供商和服务提供商是单独的实体。服务提供商购买他们的虚拟拓扑网络提供商。不同的虚拟拓扑共享一个物理网络由网络供应商。每个实体的OFC试图最大化自己的利润通过最大化其虚拟/物理网络的利用率。我们提出一项新服务，称为弹性虚拟拓扑服务，允许网络提供者利用其资源更有效率的同时最小化之间的信息共享网络供应商和客户，服务提供者。

与弹性虚拟拓扑服务，服务提供商接收承诺：1.服务提供商可以将它的访问流量每个虚拟链路上，因为它是一个协商的低拥堵概率统计的保证；2.服务提供商仍然可以有一个协商的最小带宽拥塞时。作为回报，服务提供商需要提供它的流量通过每个虚拟链路进行的一些基本特征。应当注意的是，每一个虚拟链路可以携带大量的微流。要共享的信息是虚拟链路，而不是个别的微流的聚集的业务量特征。以这种方式，服务供应商仍然可以隐藏有关它的用户从网络供应商的信息，而后者可通过操作合计流量而不是个别的微流实现可扩展性。

具体而言，我们提出以下虚拟拓扑与统计担保（VTSG）方案。首先，服务提供者发送一个请求到网络提供商与所请求的虚拟拓扑中对每个虚拟链路而不是发送具有相关联的带宽拓扑请求的描述和相关联的平均值和峰值速率。从带宽不同，平均值和峰值速率的虚拟链路是通过使用由服务提供者，这是服务提供者的控制下的用户业务和路由算法决定。因此，这是可能的服务提供者来估计这些统计是根据它的用户配置文件。另一方面，由虚拟链路接收到的带宽将是动态的，依赖其他虚拟链路的通信量特征共享相同的物理链路进行统计复用增益，并且只能通过谁拥有关于所有的业务特性信息的网络提供者来决定虚拟链路共享物理链路。

网络提供者将使用平均值和峰值率计算的最小带宽高于虚拟链路的平均速率，但小于峰值速率高的比例(如99.9%)保证虚拟链接将能够发送它没有拥堵的交通。当拥塞发生时，虚拟链接将保证最小带宽。当一个虚拟链接遍历多个物理链接，最小带宽虚拟链接可以将最小的最小带宽支持的所有相关物理链接。

配备所需的最小带宽的方法来计算每个虚拟链接，网络提供商将映射虚拟拓扑通过制定作为一个优化问题与最小带宽的要求。为此，有各种现有方法如(9 - 11)可以应用。所以我们的重点在本文将最小带宽的计算而不是映射问题的配方。重要的是要注意，计算最小带宽的复杂性有重大影响的映射算法的复杂性。这就是为什么现有方法[9 - 11]假设每个虚拟链路的带宽要求只是一个常数，不依赖于其他虚拟链接共享同一物理连接。我们的目标是找到一种方法，现有的方法如(9 - 11)可以直接应用没有任何变化。

映射完成后，网络提供商将通知服务提供者为每个虚拟链接和保证最小带宽性能可以让他们的自然流量没有拥挤堵塞。服务提供者在物理链路拥塞发生时，网络提供商将警报发送到服务提供者分享那些虚拟物理链路和与弹性虚拟拓扑服务最低带宽。

当接到警报，这些服务提供者将决定如何路由用户流量在他们的虚拟网络，以避免拥挤的虚拟链接和虚拟网络对他们的影响最小化。例如，如果一个服务提供者使用OSPF路由协议，服务提供者可以增加那些拥挤的链接的成本。交通就会转向其他拥堵链接。当然，其他更复杂的优化方法可以用于SDN集中控制架构。重要的是要注意，我们VTSG方法允许网络提供者和服务提供者做出各自的资源使用情况决定在分享最低数量的信息。

在下一节中，我们的目标是开发一种方法计算最小带宽为每个虚拟链接以便a)它允许统计复用在不同虚拟链接共享相同的物理链接；b)所有现有的拓扑映射算法例如[9 - 11]仍然可以使用最小带宽应用虚拟链路的要求。

四、     最小带宽计算

根据服务质量研究领域，开发了多种方法计算拥塞概率和带宽需求(例如[12])。这些方法需要详细的交通特点，强调微流程和复杂的分析操作。在我们的情况下，个人用户不可用的微流信息和复杂的分析操作将使拓扑映射变得更加复杂和棘手。我们的目标是找到一个实际的方法，允许网络提供商的SDN控制器计算每个虚拟链路的最小带宽下VTSG服务有限的信息而实现多路复用增益。迎接这些挑战，我们提出以下方法。

我们考虑的场景，一个物理网络已经收到了R虚拟网络请求。R虚拟网络请求的虚拟链接构成一组l .我们假设每个服务提供者的网络提供商将通知要求虚拟网络拓扑和平均值和峰值速率的流量与每个虚拟链接。信息共享是聚合，因为每个虚拟链接有大量微流程。这种信息共享是虚拟拓扑服务所需的最低。

一个简单的例子如图2所示，一个物理网络包括四个节点(节点A，B，C，D)和五个链接(链接(A，B)(B，C)(C，D)，(D)(A、C)作为实线所示)。两个虚拟拓扑生成的物理网络。一个虚拟拓扑包含虚拟节点A，B，C和虚拟链接(A，B)₁， (B，C)₁， (A，C)₁如虚线所示。另一个包含虚拟节点、C、D和虚拟链接(A， C)₂，(C， D)₂和(D，A)₂，点线所示。这里我们假设虚拟节点发生重叠与物理节点简化我们的符号。很容易看到，物理链路(A，C)有两个虚拟链接(A，C)₁和 (A，C)₂。

因为我们没有信息个人微流程在虚拟链路的特点，我们需要捕捉骨料的性质交通直接与虚拟链接。为此，我们假设交通由每个虚拟链接可以通过高斯过程建模。这是一个有效的假设在大多数情况下，因为虚拟链接通常有大量微流程导致高斯过程基于中心极限定理。许多测量证实，聚合互联网流量确实遵循高斯过程[13]。

在一般情况下，我们假设每个虚拟链接l，∈，带有高斯交通意味着利率毫升和宣布的pl峰率对应的租户。收到意味着利率毫升和峰值速率pl∈，网络提供商需要计算最小带宽提单为每个虚拟链接。

我们的标准偏差表示高斯交通与每个虚拟链接我们设置分位数的高斯分布将由网络供应商，可以决定对所有虚拟链接保持不变。当其值非常小，分位数的值很少发生。因此大致视为峰值速率，即：

其中ERF（）是高斯分布的误差函数。为α的实际值将由服务提供者来决定。我们表示：

这导致：

我们首先集中在该虚拟链路将被映射到单个物理链路的情况。我们将在这一节的后半部分讨论更一般的情况下。假设有Lsvirtual链路共享一个基底物理链路第不失一般性，我们假设这些虚拟链接建立索引1，2，...，Ls。很容易看出，在物理链路的总流量仍然是一个高斯过程：

图2. 一个物理网络与两个虚拟拓扑示例

求平均和标偏差同样让QBE的β-位数的总流量。然后我们有

如果我们规定作为b≥q物理链路的带宽容量，拥塞会发生的概率小于β。因此，通过控制B，就可以实现任何保证拥堵的概率β。

接下来的问题是如何分配这样一个虚拟链路可以在拥堵确实发生最小带宽保证这方面的能力，以单个虚拟链路。我们采用其中分配给每个虚拟链路的最小带宽被计算为如下一个简单的方法：

如果满足公式(4)，我们有：

因此满足b≥q。这样做的原因简单的方法是，在物理网络具有路由中的每个虚拟拓扑各个业务流的很少知识。这使得它很难应用其他方法公平，如最大最小[5]。然而同时又简单，因为它是，它仍比恒定带宽的现有算法已通常假定更为复杂。

结合方程（1）至（4）中，我们可以看到，上毫升的和PL的所有虚拟链路共享物理链路以及LS的，进而关系bl取决于是非线性的。这种非线性关系将使所有现有的拓扑映射算法，例如在[9-12]不适用。在Lswill的依赖也使其不可行，因为网络提供商可以只知道Lsafter优化和映射已经完成，也就是说，LS是映射的结果，而不是映射输入。因此，我们需要进一步简化等式（4）使得它形成了一个线性关系，它不依赖于LS。

Now we will investigate the performanceof our proposed VTSG scheme in comparison with the wired virtual topology service.Because the mean rate mland peak rate plvary from virtual link to virtual link,in order to study the average performance, we consider ml’sand  pl’s asi.i.d. random variables respectively withBecause virtual networks are typicallyindependent, this assumption is roughly true in practice.

我们考虑以下情况相比，在物理链路的容量由每个虚拟链路承载的通信量相对较小的情况下。在具体，我们假设每个虚拟链路内的通信量的方差上界，也就是说，对于，其中Σis上限。当很少虚拟链路被映射到一个物理链路，物理链路典型地充分利用。物理链路不会得到拥挤没有多大关系最小带宽是如何致力于为每一个虚拟链路。因此，我们将集中于承载多个虚拟链接这些物理链路，即我们假设映射到物理链路的虚拟链路的数量被降低为界，这意味着对所有的物理链路，其中，λ为下界。然后我们有：

   

公式（4）满足。这意味着，对于该虚拟链路的拥塞概率lwill是小于β。虽然公式（5）比方公式（4）较宽松，我们可以看到，当Λ到无穷大，所分配的带宽为等式每个虚拟链路。（5）收敛其平均速率显然是最小带宽的任何方法可以在保证性能的分配。这是鲜明对比的峰值速率分配与有线虚拟拓扑服务。

需要注意的是公式（5）不同于（4），在只依赖于某种意义上的所有其他参数将在所有虚拟链路和所有物理链路不变。并且此外，它不依赖于使用该结果，所有现有的拓扑映射算法将不作任何有效改变。因此，我们的目的已经达到。

现在我们将调查的性能提出VTSG计划与有线相比虚拟拓扑服务。因为平均率mland峰率plvary虚拟链接虚拟链接，为了研究的平均表现，我们认为ml和pli.i.d.随机变量分别，因为虚拟网络通常是独立的，这种假设大约是真正的在实践中得出结论。

从公式（1）我们得到：

从公式（5）我们得到：

有线虚拟拓扑服务，带宽由数字将是其每个虚拟链路所需的峰值速率。我们得到：

现在，我们可以计算出多少带宽，我们可以节省的百分比表示的作为：

从公式（9），我们可以看到，当Λ增加，即虚拟链路共享物理链路增加的最小数目时，增益也将增加。当虚拟链路共享物理链路的数量是非常小的，该物理链路变得极不可能获得拥塞。因此它不会在多少带宽被分配给每个虚拟链路而言不再重要。因此，方程（5）仍然可以使用。

当一个虚拟链路映射到横穿多个物理链路的路径，就可以计算出所需的使用类似的方法的每个物理链路的最小带宽，然后取它们的最小的最小带宽的虚连接。我们将展示在下一节一些数值例子。如果虚拟链路的流量分割，我们可以分裂虚拟链路的每个部分建模为整个虚拟链路流量的比例量。这是典型的情况下，如果ECMP协议被应用。上面的方法可以被应用到每个部分上。

五、     数值结果

我们现在研究一些数值结果。我们首先要看到的最小带宽用于增加虚拟链路共享同一物理链路的数量每个虚拟链路是如何变化的。我们假设每个虚拟链路产生1Gbps的流量平均1.3Gbps的高峰。我们设置Φ=β=0.1％。这意味着，对于每个物理链路的拥塞概率被设置为低到0.1％。其结果示于图3中很容易看出，最小带宽下降而增加虚拟链路的数目。更具体地说，当存在使用物理链路仅一个虚拟链路，最小带宽是其峰值速率，即，不复用增益。然而，这是通常的物理链路，由于这样的事实，虚拟链路的数目太小未充分利用的情况下。因此，对于这种情况下，不存在拥堵问题。

当虚拟链路的数量开始增加，最小带宽下降极快的开头和公寓出来以后。这表明，它是相当有效的复少量的虚拟链路。现在，我们比较这两个类型的服务。为了简化参数设置，我们假设α=β和=Σ，两者都在实际情况大致如此。我们重写公式（8）如下：

图3. 平均最小带宽为每个虚拟链接与最小数量的虚拟链接共享同一物理连接。所有虚拟链接也有类似的统计特征。每个虚拟链路进行流量平均意味着1 Gbps的速度与平均速度峰值1.3Gbps。

我们定义：作为变异系数为与每个虚拟连接的通信量。我们有：

结果如图4所示，x轴显示Λ和 y轴表示。我们可以看到，储蓄增加而增加数量虚拟链接。更戏剧性的增加当虚拟链接的数量很小。此外它也随着变化的流量的增加而增加。变量的流量越多，收获越多。Φ= 0.3时，即。，峰值率约90%以上的平均速度，节省30%以上的十个虚拟链接。这节约是显著的。

六、     结论

通过分离控制平面和数据平面，SDN有可能允许网络和服务提供者创建各种各样的新服务。虚拟拓扑的一个最有前途的SDN可以提供服务。通过拓扑抽象过程，网络提供者可以出售虚拟切片的物理网络不同的服务提供者。不同的服务提供者为租户有完全控制自己的片内的虚拟拓扑而网络提供商的控制它的物理网络。然而微流程的每个用户的信息的缺乏使得每个所有者很难探索统计复用增益。

提出VTSG作为一种新的网络和实践机制，允许供应商统计复用增益最大化同时还为每个租户提供一定的保证。此外，我们VTSG方法使网络提供者和服务提供者做出各自的资源使用情况决定在分享最低总虚拟链接信息。

数值结果表明，可以实现显著的增益与相对较少的租户。这是非常令人鼓舞的，因为租户网络提供商将主机的数量可能是变量在一个非常广泛。

而实现这一多路复用增益，我们取得了我们的最小带宽计算方法独立于其他虚拟链接共享同一物理连接。这个特性允许所有现有的拓扑映射算法适用与我们的最小带宽计算方法。

图4. 平均带宽存储与最低数量虚拟链路

参考文献：

[1]  M. Casado，M. J. Freedman，J. Pettit，J.Luo，N.McKeownm S. Shenker，“Ethane: Taking Control of the Enterprise，”ACM SIGCOMM 2007，August27-31，2007，Kyoto.

[2]  M. Banikazemi，D. Olshefski，A. Shaikh，J. Tracey，and G Wang，“Meridian:SDN云网络服务平台，”IEEE通信杂志，Feb. 2013

[3]  S. Jain，et al.，“B4: 全球部署软件定义的广域网的经验，”ACM SIGCOMM 2013，August 12-16，2013，Hong Kong

[4]  A. Tavakkoli et al.，“NOX应用数据中心，”ACM Workshop on 网络研讨会热门话题(HotNets-VIII)，October 22-23，2009，New York

[5]  A. Tootoonchina etal.，“软件定义网络控制器的性能，” 2^ndUSENIXHot-ICE’12，April 24，2012，San Jose.

[6]  A. Tootoochian and Y.Ganjali，“Hyperflow: OpenFlow的分布式控制平面” USENIX NSDI INM/WREN，April 2010，San Jose

[7]  R. Sherwood，et al.，“FlowVisor: 网络虚拟化层，”OPENFLOW-TR-2009-1， OpenFlowConsortium，October 2009

[8]  D. Drutskoy，E. Keller，and J. Rexford，“软件定义网络可扩展虚拟化，”IEEE Internet Computing， Vol. 17， Iss. 2，March，2013.

[9]  N.M.M.K. Chowdhury，M.R. Rahman，and R. Boutaba，“虚拟网络嵌入与协调节点和链接映射” IEEE INFOCOM2009，April 2009，Rio de Janeiro.

[10]  X. Cheng，et al.，“通过拓扑感知节点排名的嵌入式虚拟网络，”ACM SIGCOMM计算机通信评审，Vol. 41，No. 2，April 2011.

 [11]  J. He， et al.，“达芬奇：动态自适应虚拟网络定制的互联网，”ACM CoNEXT2008，Madrid，December 2008.

[12]  J.-Y. Le Boudec andP. Thiran，“网络微积分: 确定性网络排队系统理论，”Springer，LNCS，2001.

[13]  W. E. Leland，M. S. Taqqu，W. Willinger，D. V. Wilson，“以太网流量的自相似性，”IEEE/ACM Trans. Networking，Vol. 2， No.1，Feb. 1994.