基于拓撲分割與聚類分析的虛擬軟件定義網絡映射算法

陳 港，孟相如，康巧燕，陽勇

（空軍工程大學信息與導航學院，西安 710077）

0 引言

網絡虛擬化技術通過將網絡服務和網絡基礎設施在邏輯上進行解耦，降低了網絡服務的局限性，增強了部署靈活性，實現了網絡資源的可靠管控，加速了網絡架構和技術上的創新［1］。由于基于傳統網絡的網絡虛擬化存在諸多問題和限制，專家學者將軟件定義網絡（Software Defined Network，SDN）引入網絡虛擬化，形成虛擬軟件定義網絡（virtual SDN，vSDN）［2-4］，其中的一個關鍵技術問題是虛擬網絡映射。作為vSDN 中的映射，相較于一般的虛擬網絡映射［5］，它的映射約束、優化目標、網絡復雜度都具有更高的要求［6-7］。

Tan 等［8］考慮網絡時延和控制器與轉發設備之間的不相交路徑數，提高vSDN的生存性并降低網絡時延；Kuang等［9］考慮了交換機的流量和內存約束，節點映射策略為將節點根據其重要度指標進行樹形拓撲的降序排列后使用貪婪算法進行匹配映射，鏈路映射策略為選擇帶寬富裕度高、跳數少的鏈路優先映射；冉金鵬等［10］采用優化的果蠅算法進行映射方案的求解，在負載均衡、請求接受率和控制延遲等指標上取得較好效果；王健等［11］基于蟻群混合遺傳算法映射節點，利用K-最短路徑算法映射鏈路，提高了接受率，并較好地改善了節點和鏈路的平均利用率以及映射的收益開銷比。文獻［8-11］中將節點和鏈路映射分開考慮，沒有注意到節點與鏈路之間的關聯性。Li等［12］提出了一種拓撲感知的虛擬軟件定義網絡映射方法：節點映射時，采用貪婪算法優先映射虛擬網絡和物理網絡中資源度高的節點；鏈路映射時，分別采用K-最短路徑算法和多商品流算法映射控制鏈路和數據鏈路，采用節點重映射提高映射成功率。該方案有效提升了映射效率和收益開銷比，通過在鏈路映射失敗時采用節點重映射的方式較為粗略地考慮了節點與鏈路之間的拓撲與資源關聯性，但其算法開銷較大，同時未考慮vSDN 中交換機以及控制器內存約束。Yan 等［13］提出了一種基于虛擬軟件定義網絡的啟發式要素感知的資源高效利用算法，該方案基于K-Means 聚類進行節點的匹配映射，采用K-最短路徑算法完成鏈路映射。該方案提升了請求接受率，降低了通信延遲，但其僅根據節點的計算能力、內存以及總的連接帶寬這三個要素進行聚類匹配，忽略了節點與鏈路之間的關聯性，未考慮網絡的拓撲特征。

總結發現，大部分基于vSDN的映射算法沒有充分考慮節點與鏈路之間的相關性。虛擬網絡和物理網絡中的節點與鏈路之間存在著一定的拓撲結構以及對應的計算資源和帶寬資源，分開考慮節點映射和鏈路映射時相當于割裂了兩者之間在拓撲結構和資源數值之間的關聯性。為在vSDN 映射過程中更全面地考慮節點與鏈路約束，以及節點與鏈路之間的相關性，本文提出了一種基于網絡拓撲分割與聚類分析的虛擬軟件定義網絡映射算法（Topology Segmentation and Clustering Analysis-vSDN mapping algorithm，TSCA-vSDN）。本文算法的主要思路如下：1）通過將物理網絡和虛擬請求網絡按照交換機到控制器的最短跳數值展開為樹狀拓撲圖，實現對網絡拓撲的感知和分割，并依據節點的拓撲屬性區分出關鍵節點和鏈路，避免出現關鍵節點或鏈路過早高負荷映射，以提高整體的請求接受率；2）通過定義節點資源度和網絡資源度以及節點緊密度，使用聚類算法依據節點的多項屬性值進行聚類分析，實現對底層物理網絡資源的動態感知；3）通過將鏈路約束分散到節點帶寬資源以及節點的度約束考量，對不符合鏈路要求的節點進行重映射，充分考慮節點與鏈路之間的資源與拓撲相關性。仿真結果表明，該算法有效地提升了基于SDN架構的虛擬網絡映射在較低連通概率物理網絡下的請求接受率。

1 網絡模型與評價指標

1.1 網絡模型

本文假設處理的物理網絡和虛擬請求網絡拓撲圖中任意兩點間直連邊的條數最多為1 條，物理網絡和虛擬網絡請求拓撲都為非平凡的簡單連通圖。本文假設控制器為帶內部署，且控制器不參與交換機之間的數據轉發，只負責控制信令的分發。

1.1.1 物理網絡

1.1.3 網絡特征分析

為了對不同的網絡作出區分，以更好地選擇適配的映射策略，本文針對物理網絡和虛擬網絡給出以下一系列定量的評價指標。

定義節點資源度為p(ni)，為減小各節點因三項資源屬性值存在的偏差所導致的節點資源度誤差，設立系數α、β、γ，有：

參考文獻［12］，定義網絡Gi中節點ni的緊密度為CL(ni)，該名詞表征節點在拓撲圖中的中心程度。令緊密度CL(ni)為節點到其余各節點最短跳數倒數的和，計算式如下：

式（7）表明，到其余各節點最短跳數倒數的和越大的節點，其緊密度就越高，反之就越低。

定義節點控制中心度為CC(ni)，表征拓撲網絡中接近控制器的節點中心程度，以方便后續虛擬網絡根節點的映射。令節點控制中心度CC(ni)為節點緊密度和交換機節點到最近控制器節點最短跳數之間的比值，即：

式（8）表明，緊密度相同的節點中，到最近控制器節點最短跳數越小的節點，其節點控制中心度就越高，反之則越低。

定義節點關鍵度為節點控制中心度與節點的度之間的比值，記第i個節點的關鍵度為CR(ni)。為加快算法收斂，將關鍵度高于節點關鍵度平均值20%的節點視為關鍵節點。關鍵鏈路的篩選標準為：關鍵節點直連的鏈路。節點關鍵度計算式為：

式（9）表明，節點控制中心度相同的節點中，度越小的節點，其節點關鍵度就越高，反之則越低。

1.2 虛擬網絡映射模型

虛擬網絡映射模型可抽象為帶權重的無向圖Gv到Gs子集的映射Gv(i)→Gs(i)∈Gs。該映射定義為將虛擬請求網絡中的虛擬節點和鏈路對應映射到物理網絡中的物理節點和路徑，在映射過程中，需要滿足節點的CPU 約束，流表空間TCAM 約束，以及鏈路的帶寬（BW）約束。本文采用兩階段映射法，先映射節點后映射鏈路，如圖1所示。

圖1 虛擬SDN映射模型Fig.1 Virtual SDN mapping model

1.2.1 節點映射

對于同一個虛擬網絡請求，每一個虛擬節點必須映射到不同的物理節點上，但同一個物理節點上可以存在多個不同虛擬網絡請求的虛擬節點。由于物理SDN 控制器節點采用帶內部署，所以在映射虛擬交換機節點和虛擬SDN 控制器節點時可以將其統一考慮為虛擬節點映射。假設每一個虛擬網絡請求有且只有一個虛擬SDN 控制器負責該網絡的數據轉發和流量控制。如果虛擬節點映射到物理節點則為Xij=1；否則Xij=0。虛擬節點nv映射到物理節點ns的過程表示為MN，即：

約束條件如下：

其中：式（11）表示待映射虛擬節點CPU 資源需求不能大于被映射物理節點的剩余CPU 資源；式（12）表示待映射虛擬節點TCAM 資源需求不能大于被映射物理節點的剩余TCAM 資源；式（13）表示同一虛擬網絡中每一個虛擬節點只能映射到一個物理節點，任意物理節點至多承載同一個虛擬網絡中一個虛擬節點。

1.2.2 鏈路映射

對于虛擬網絡請求中的某一條鏈路而言，它可以對應映射到物理網絡中的一條具體的鏈路，也可以映射到物理網絡中由多條鏈路組成的一條具體的路徑。為了在避免歧義的同時更準確地描述鏈路的映射，將虛擬鏈路的映射過程定義為虛擬鏈路與該虛擬鏈路兩端節點映射后對應物理節點間鏈路或路徑的映射。定義底層物理網絡兩點間任一條非閉環的路徑為。將虛擬鏈路ev映射到物理鏈路es的過程記為ME，即：

約束條件如下：

式（15）表示待映射的虛擬鏈路帶寬需求不能大于被映射物理節點的剩余帶寬資源。

1.3 評價指標

定義1虛擬網絡請求接受率。

參考文獻［10］，定義為長期的時間段T中成功映射的虛擬網絡請求數量與收到的虛擬網絡請求數量的比值，表示為AR，如式（16）所示：

其中：vSDNRe(t)表示在時刻t成功映射的虛擬網絡個數；vSDNGe(t)表示在時刻t收到的虛擬網絡個數。

2 虛擬SDN請求映射算法

本章首先介紹拓撲分割物理網絡，并計算物理網絡和虛擬網絡的拓撲和資源指標，然后對物理網絡節點基于拓撲和資源指標進行聚類分析，將虛擬網絡的節點根據物理節點聚類分析結果進行匹配映射，并在節點映射前進行相關的鏈路約束判斷，節點映射成功后再映射鏈路，最后對算法的時間復雜度進行計算說明。

2.1 物理網絡拓撲分割和資源指標計算

物理網絡拓撲分割和資源指標計算步驟如下：

圖2 物理網絡拓撲分割示例Fig.2 Example of physical network topology segmentation

圖3 樹形拓撲網絡示例Fig.3 Example of tree topology network

圖4 延展后的樹形拓撲圖Fig.4 Extended tree topology diagram

4）計算物理網絡和虛擬網絡的節點度d(ni)、緊密度CL(ni)、控制中心度CC(ni)。將虛擬網絡中緊密度最高的節點作為根節點，其余節點按照到該根節點的最短跳數作為層數轉化為樹形拓撲網絡。

5）計算物理樹形拓撲網絡的關鍵節點和關鍵鏈路，在映射時只有當關鍵節點的剩余節點資源度與物理子拓撲網絡中平均節點資源度的比值大于一定值時才可以被映射，具體比值記為ratio，通過后續實驗得出。但關鍵鏈路不受影響，即當關鍵節點不被映射時依舊可以充當其余節點的數據轉發節點，與其直連的關鍵鏈路可以被虛擬鏈路映射。為避免出現關鍵鏈路過早耗盡帶寬的情況，在鏈路映射時設置鏈路權重隨鏈路剩余可用帶寬降低而提高。

2.2 節點聚類分析和鏈路映射

為了充分利用物理網絡和虛擬網絡的拓撲信息以及資源信息，首先針對物理網絡節點的拓撲指標進行聚類分析，分割為k個節點拓撲屬性相近的集合；接著，計算虛擬節點到各聚類中心的歐氏距離，選取歐氏距離值最小的集合作為虛擬節點待映射的物理節點集合；然后，按照虛擬網絡的樹形拓撲網絡，從根節點開始依據廣度搜索順序映射虛擬節點，并計算虛擬節點和選取集合中所有節點的資源指標的歐氏距離，選取歐氏距離值最小的物理節點作為虛擬節點的映射節點；最后，除映射虛擬網絡根節點外，對每一個虛擬網絡節點進行鏈路約束初步判斷，當所有節點鏈路約束符合后開始鏈路映射，若仍出現矛盾則進行節點重映射，直至映射成功或遍歷后映射失敗。

映射算法流程如圖5 所示，圖中否1、否2、否3、否4 代表不同的轉折條件，分別為該節點不滿足約束但集合ki未遍歷、集合ki已遍歷但k個聚類集合未遍歷、k個集合已遍歷但拓撲網絡未遍歷、都已遍歷未找到合適節點。節點映射時，首先選擇合適的物理拓撲網絡并映射虛擬網絡的控制器，然后映射虛擬網絡交換機節點。

圖5 映射算法流程Fig.5 Flow chart of mapping algorithm

映射控制器時，首先計算物理子拓撲網絡與虛擬網絡的優先級pr，然后計算優先級變量pr()（簡記為prs）和pr()（簡記為prv）的歐氏距離d0，優先考量歐氏距離值最小的物理拓撲網絡映射虛擬網絡。

其中各變量計算式如下：

若該物理拓撲網絡控制器節點滿足虛擬網絡控制器節點的資源約束，則確認虛擬網絡控制器映射到該網絡的物理控制器，若不滿足則順序考量下一個物理子拓撲網絡，直至遍歷完全都不滿足約束時則映射失敗。

首先選取d1值最小的節點集合cluster(j)(j∈k)作為該虛擬節點的待映射物理節點集合，然后根據物理節點和虛擬節點的C(ni)、TC(ni)、Bw(ni)指標，在集合cluster(j)中計算虛擬節點和物理節點三個資源指標的歐氏距離d2，將集合中的節點按照歐氏距離d2升序排列。

其中各變量計算式如下：

具體映射虛擬網絡節點時，首先映射虛擬網絡的根節點，然后依照對樹形拓撲網絡的廣度搜索順序依次進行虛擬節點的映射。具體過程為：排除掉物理控制器節點，然后針對關鍵節點判斷關鍵節點的節點資源度Rp()是否小于該物理子拓撲網絡節點資源度平均值的一半，若小于則跳過該關鍵節點；否則繼續考察物理節點的資源是否滿足虛擬節點的資源約束。若考察的物理節點滿足虛擬節點的資源約束則對節點進行鏈路約束初步判斷，如果符合判斷則將該物理節點作為該虛擬節點的映射節點；若不滿足則順序考察下一個物理節點。若遍歷該集合cluster(j)都無法找到符合約束的節點則更換物理拓撲網絡。若遍歷所有物理拓撲網絡仍無法找到符合約束的物理節點，則表明無法成功映射該虛擬網絡所有節點，即映射失敗。其中，鏈路約束初步判斷的資源需求方為待映射虛擬節點與上層虛擬節點間的鏈路帶寬需求，資源供給方為待被映射物理節點與虛擬網絡根節點已映射物理節點間的鏈路帶寬資源。

3）鏈路映射時，采用K-最短路徑算法，在計算兩節點間最短路徑時，將鏈路權重設置為物理網絡鏈路帶寬最大值與鏈路剩余帶寬的差值加一，以規避關鍵鏈路被提前過度映射而降低請求接受率。如果沒有找到滿足需求的鏈路，在物理拓撲未遍歷完時采用下一個物理子拓撲網絡進行節點重映射，若已遍歷所有物理子拓撲網絡，則進行一次節點重映射，并盡量規避之前已被選擇的物理節點，若仍失敗則丟棄該虛擬網絡請求。如果映射成功則反饋成功。

4）本文提出的TSCA-vSDN 算法，輸入為物理拓撲網絡和虛擬拓撲網絡，輸出為節點映射表單和鏈路映射表單。具體內容如算法1（TSCA-vSDN）所示，其中第1）～4）行計算物理網絡中交換機到控制器的最短跳數，并進行拓撲分割；第5）～8）行計算各子拓撲網絡的優先度；第9）～12）行進行聚類分析；第13）～27）行根據聚類結果和節點資源屬性進行節點匹配映射，輸出節點映射表單；第28）～34）行采用K-最短路徑算法進行鏈路映射，輸出鏈路映射表單。

算法1 TSCA-vSDN。

2.3 算法時間復雜度計算

3 算法評估

在相同的底層物理網絡環境下，面對不同的虛擬網絡請求，針對算法TSCA-vSDN 的請求接受率指標進行仿真實驗分析，并與算法KCL-vSDN和To-vSDN進行對比。三種算法的簡要描述如下。

1）算法TSCA-vSDN。節點映射時，首先基于K-means 聚類方法對與虛擬節點拓撲參數比例相似的候選物理節點進行聚類，然后根據節點的計算資源選取比例最接近的進行映射；鏈路映射時，選用K-最短路徑算法，在鏈路映射受阻時采用節點重映射提高映射成功率；算法映射單個虛擬網絡的時間復雜度為

2）算法KCL-vSDN。節點映射時，首先基于K-means 聚類方法對與虛擬節點資源比例相似的候選物理節點進行聚類，然后根據網絡演算得到的控制要素從集群中選擇出最優的物理節點進行匹配映射；鏈路映射時選用K-最短路徑算法［13］；算法映射單個虛擬網絡的時間復雜度為

3）算法To-vSDN。節點映射時，采用貪婪算法優先映射虛擬網絡和物理網絡中資源度高的節點；鏈路映射時，先采用K-最短路徑算法映射控制器到交換機的虛擬控制鏈路，然后采用多商品流算法映射其余虛擬數據鏈路，在鏈路映射受阻時采用節點重映射增加映射成功率［12］；算法映射單個虛擬網絡的時間復雜度為

3.1 仿真環境設置

通過文獻［14-16］及本文仿真實驗發現不同的底層物理網絡以及不同的虛擬網絡請求，對同一算法的性能有著較大的影響。參考數據中心常用拓撲，采用facebook 數據中心網絡拓撲（簡記為topo-facebook）和fat-tree 網絡拓撲（簡記為topo-fat-tree）等兩類常見底層物理拓撲結構，以及依靠網絡節點和節點連通概率（KP）隨機生成的拓撲網絡（簡記為topomesh），分別作為仿真環境的底層物理網絡。

topo-facebook 和topo-fat-tree 都有其較為固定的結構，在給定節點數量的前提下，其鏈路數量是固定的，為方便對照，本文設置三類物理網絡節點總數都為200。實驗中鏈路帶寬、交換機計算資源、存儲資源等數據參考文獻［17］進行設置，具體見表1。

表1 底層物理網絡分類及參數設置Tab.1 Classification and parameter setting of underlying physical network

鏈路帶寬設為40 Gb/s，交換機節點計算資源CPU 為12×103，存儲資源TCAM 為250 × 103，控制器節點計算資源為交換機的4 倍。本文將其節點總數設為200，控制器個數為4。topo-mesh 為隨機網絡，為考察物理網絡節點總數以及連通概率對算法映射性能的影響，設定節點總數分別為200，控制器數量為4；KP為0.02 和0.03；數據鏈路帶寬以及計算資源CPU 和存儲資源TCAM 服從均勻分布，即，單位103］；控制鏈路帶寬為40 × 103，控制器計算資源為交換機計算資源的4倍。底層物理網絡分類見表1。

虛擬網絡采用topo-mesh 隨機網絡，考慮到虛擬網絡的大小不確定性以及持續時長不確定性，將其節點總數N設為N～U［2，20］的均勻分布，KP為0.5，將其持續時長T設為T～P(λ)，λ=120，240，360，480 的泊松分布（單位為s）。數據鏈路帶寬、節點計算資源CPU 和存儲資源TCAM 服從均勻分布，，單位為Mb/s，～U[5× 103，20 × 103]；控制鏈路帶寬為10 Mb/s，控制器計算資源和存儲資源為交換機的2倍。

3.2 結果分析

本文采用控制變量法共進行了三組實驗。實驗一在固定物理環境和虛擬網絡請求生存時長的條件下，改變關鍵節點的剩余節點資源度與物理子拓撲網絡中平均節點資源度的比值ratio，探究使得算法TSCA-vSDN 的請求接受率最高的ratio值；實驗二與實驗三在固定物理網絡節點總數和相同連通概率（KP）的條件下，改變物理網絡類型和虛擬網絡請求生存時長，探究物理網絡類型和虛擬網絡請求生存時長對三種算法請求接受率的影響；同時實驗三在實驗二的基礎上，更換了一種物理網絡類型以及KP，探究不同網絡類型、不同物理網絡KP對三種算法請求接受率的影響。

3.2.1 實驗一

基于topo-mesh（KP=0.026）網絡拓撲，在當關鍵節點的剩余節點資源度與物理子拓撲網絡中平均節點資源度的比值ratio分別取0.1、0.3、0.5、0.7、0.9，且生存時長為480 時，對算法TSCA-vSDN的請求接受率進行分析。

由實驗一的圖6 可以看出，當關鍵節點的剩余節點資源度與物理子拓撲網絡中平均節點資源度的比值取0.5 時，算法TSCA-vSDN 的請求接受率較高。后續實驗中該比值ratio都取0.5。

圖6 不同比值時算法TSCA-vSDN的請求接受率對比Fig.6 Comparison of request acceptance rate of TSCA-vSDN algorithm with different ratios

3.2.2 實驗二

基 于topo-facebook（KP≈0.018）網絡拓撲和topomesh(KP=0.018)網絡拓撲，將三種算法在不同的生存時長條件下進行映射性能對比。

實驗二分別以topo-facebook 和對應KP的隨機拓撲為底層物理網絡，分析了算法TSCA、KCL 以及To 在面對虛擬請求時長T～P(λ)，λ=120，240，360，480的映射性能對比情況。

從圖7～8 中可以看出，當虛擬請求時長在120、240、360、480附近服從泊松分布波動時，算法TSCA 的請求接受率（AR）絕大多數情況下為最高。當虛擬網絡請求個數接近1000時，所有指標都趨于平滑、穩定，表明此時已基本消除虛擬網絡節點總數以及生存時長的隨機波動影響，其數值具備一定的說服力。

圖7 基于topo-facebook（KP ≈0.018）物理網絡的算法請求接受率對比Fig.7 Comparison of algorithm request acceptance rate based on topo-facebook（KP ≈0.018）physical network

從圖7 分析得出，算法TSCA 穩定時的AR隨著生存時長的增加出現明顯的降低，說明AR穩定時，資源利用率基本已到達該算法利用極限，AR的數值受到了因生存時長增加導致的剩余可用資源的約束。著重分析圖7（d）可知，當請求個數為50時，算法TSCA的AR值從1開始陡然下降，說明此時已到達該算法資源利用率極限，隨后的大部分虛擬請求映射失敗；但當請求個數接近120 時，算法TSCA 的AR值開始回升，因為此時剛開始映射的虛擬請求生存周期已結束，剩余可用資源增加，接下來的部分虛擬請求成功映射，隨后AR在一定范圍內波動。

對比圖7 和圖8 可知，兩者的底層物理網絡topo-facebook和隨機拓撲的KP接近，節點總數、控制器數量相同，節點參數相近。分析后發現，三種算法都在隨機拓撲上的AR穩定數值更高，算法TSCA 的AR仍然高于其余兩者算法，說明算法TSCA 相較于算法TSCA、KCL 更適應topo-facebook 物理網絡，能很好地發揮出算法的映射性能，極大提高虛擬網絡的請求接受率。

圖8 基于topo-mesh（KP=0.018）物理網絡的算法請求接受率對比Fig.8 Comparison of algorithm request acceptance rate based on topo-mesh（KP=0.018）physical network

3.2.3 實驗三

基于topo-fat-tree（KP≈0.026）網絡拓撲和topo-mesh（KP=0.026）網絡拓撲，將三種算法在不同的生存時長條件下進行映射性能對比，結果如圖9～10所示。

圖9 基于topo-fat-tree（KP ≈0.026）物理網絡的算法請求接受率對比Fig.9 Comparison of algorithm request acceptance rate based on topo-fat-tree（KP ≈0.026）physical network

實驗三分別以topo-fat-tree 和對應KP的隨機拓撲為底層物理網絡，分析了算法TSCA、KCL 以及To 在面對虛擬請求時長T～P(λ)，λ=120、240、360、480的映射性能對比情況。

從圖9～10中可以看出，當虛擬請求時長在120、240、360、480附近服從泊松分布波動時，算法TSCA 的請求接受率（AR）絕大多數情況下為最高；當虛擬網絡請求個數接近1000 時，所有指標都趨于平滑、穩定，說明此時已基本消除虛擬網絡節點總數以及生存時長的隨機波動影響，其數值具備一定的說服力。

對比圖9 和圖10 可知，兩者的底層物理網絡topo-fat-tree和隨機拓撲的KP接近，節點總數、控制器數量相同，節點參數相近。分析后發現，三種算法大都在隨機拓撲上的AR穩定數值更高，算法TSCA的AR穩定數值仍然高于其余兩種算法，說明算法TSCA 相較于算法TSCA、KCL 更適應topo-fat-tree 物理網絡，能很好地發揮出算法的映射性能，極大提高虛擬網絡的請求接受率。

圖10 基于topo-mesh（KP=0.026）物理網絡的算法請求接受率對比Fig.10 Comparison of algorithm request acceptance rate based on topo-mesh（KP=0.026）physical network

對比實驗二與實驗三可以看出，當虛擬請求網絡的生存時長不高于360時，算法TSCA 在topo-fat-tree中能取得更好的AR；當虛擬請求網絡的生存時長高于480 時，算法TSCA 在topo-facebook中能取得更高的穩定AR值。

通過實驗二與實驗三可以看出，當虛擬請求網絡的生存時長在120、240、360、480 附近服從泊松分布波動時，針對連通概率較低的底層物理網絡，如topo-facebook 和topo-fat-tree以及隨機分布的物理網絡，算法TSCA 的請求接受率穩定值都高于算法TSCA、KCL，能更好地發揮出算法的映射性能。

4 結語

本文所提出的算法TSCA-vSDN 首先通過拓撲分割縮小節點和鏈路映射搜索范圍；然后通過聚類分析節點的拓撲樹形和資源屬性，優化節點映射匹配過程；最后通過將鏈路約束作為節點約束的一部分，充分利用節點與鏈路相關性，提高映射請求接受率。

通過兩組對比實驗，將算法TSCA-vSDN 與算法KCLvSDN 和To-vSDN 在不同底層物理網絡拓撲（如facebook 物理網絡、fat-tree 物理網絡以及隨機分布的物理網絡）、不同的虛擬網絡請求持續時長條件下的映射性能進行對比，實驗結果表明算法TSCA-vSDN 在提高請求接受率方面性能較優。本文所提出的算法TSCA 雖然對請求接受率有較為明顯的提升，但它的計算開銷也更大，如何在盡量保持較高請求接受率的條件下優化計算流程，進一步降低其計算開銷，同時增加對收益與成本比值和負載均衡等方面的優化研究，將是下一步拓展加深的研究課題。