DCell網絡上的路徑覆蓋和限制連通性研究.pdf

1、隨著社會信息化的發(fā)展，計算機應用深入到了各個行業(yè)，網絡資源和數據規(guī)模不斷擴大。在這樣的背景下，云計算(Cloud Computing)迅速興起。近年來，云計算的發(fā)展已經上升到包含美國在內的多個國家的國家戰(zhàn)略層面。云計算本質上是一種資源按需分配的模式。它的一個核心理念就是通過不斷提高“云”端的處理能力，進而減輕終端用戶的處理負擔，而將絕大部分計算放在“云”端，由大型數據中心網絡來完成。作為云計算的基礎設施和下一代網絡技術的創(chuàng)新平臺，數據中

2、心網絡的研究已經成為近年來學術界和工業(yè)界關注的熱點。
　　數據中心網絡可以表示為一個簡單圖G=(V(G)，E(G))，我們用V(G)和E(G)分別表示圖G中的頂點集合和邊集合，頂點和邊分別表示數據中心網絡中的服務器和連接服務器的鏈路，而交換機可被認為是透明的網絡設備。數據中心網絡拓撲結構的性質對于數據中心網絡的性能至關重要。
　　網絡中的哈密頓性質在信息通信中具有重要的應用。如果在數據中心網絡的多播路由算法中使用哈密頓路徑或

3、哈密頓圈，則能夠有效地減少或避免死鎖和擁塞。哈密頓性質可以被看作是不交路徑覆蓋性質的一個特例，例如，一對一、一對多、多對多1-不交路徑覆蓋問題即哈密頓連通性問題，而一對一2-不交路徑覆蓋問題即哈密頓圖問題。
　　網絡的不交路徑覆蓋已經被廣泛應用于數據庫設計，VLSI設計，代碼優(yōu)化，無線傳感器網絡的拓撲控制，以及軟件測試。在數據中心網絡中，不交路徑覆蓋能夠有效地提高數據收集或數據分發(fā)效率。例如，在數據中心網絡中使用不交路徑覆蓋進行數

4、據收集（從所有服務器中收集數據）或數據分發(fā)（分發(fā)數據到所有服務器上），我們僅需訪問數據中心網絡中每臺服務器一次。
　　隨著數據中心網絡的規(guī)模不斷擴大，服務器發(fā)生故障的情形是不可避免的，使用限制連通度能夠更加精確地度量數據中心網絡的容錯性。因此研究數據中心網絡的限制連通度是一個重要的課題。
　　DCell網絡是一種重要的數據中心網絡，它具有較好的路由性能和高擴展性，且能很好地支持一對多和多對多等網絡通信服務，并能夠支持超大規(guī)模

5、的數據中心網絡。
　　本文研究DCell網絡（Dk，n，其中k≥0且n≥2）的哈密頓性質，不交路徑覆蓋問題，以及限制連通性，具體研究成果如下:
　　1.證明了DCell網絡具有很好的哈密頓性質:
　　(1)證明了Dk,n是哈密頓連通的（D1,2除外）和哈密頓的（D0,2除外）。
　　(2)給出了構造Dk,n上任意兩個不同頂點間一條哈密頓路徑的O(tk，n)算法，其中tk，n為Dk,n的頂點數。
　　(3)證

6、明了Dk,n是(n+k-4)-哈密頓連通的和(n+k-3)-哈密頓的。
　　2.研究了DCell網絡的不交路徑覆蓋問題:
　　(1)對于任意的整數1≤r≤n+k-1，證明了Dk,n是一對一r-不交路徑覆蓋的（D1,2除外）。
　　(2)對于任意的整數1≤r≤n+k-1，給出了構造Dk,n上一個一對一r-不交路徑覆蓋的O(tk，n)算法，并分析了這些不交路徑中最長路徑長度的上界。
　　(3)證明了Dk,n是一對多(

7、n+k-2)-不交路徑覆蓋的（D1,2除外）。
　　(4)對于任意的整數1≤r≤(「)(n+k-1）/2」，證明了Dk,n是多對多r-不交路徑覆蓋的（D1,2除外）。
　　3.研究了DCell網絡的限制連通性:
　　若Dk,n上每個無故障頂點存在至少h個無故障鄰居，則基于該條件下的Dk,n的連通度可定義為限制h-連通度(用kh(Dk,n)表示）。
　　(1)對于任意的整數k≥1以及0≤h≤n-1，證明了kh(Dk