DCell網(wǎng)絡上的路徑覆蓋和限制連通性研究.pdf

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

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

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

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

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

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

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