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

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

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

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

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

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

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

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