[發明專利]一種計算中心內部物理主機的選擇方法

有效

• 申請號: 201410284277.1
• 申請日: 2014-06-23
• 公開（公告）號: CN104065547B
• 公開（公告）日: 2017-06-20
• 發明（設計）人: 沈玉龍;宗旋;張琪;姜曉鴻;裴慶祺;張華慶
• 申請（專利權）人: 西安電子科技大學昆山創新研究院;西安電子科技大學
• 主分類號: H04L12/44
• 分類號: H04L12/44;H04L29/08;G06F9/455;G06F9/50
• 代理公司: 西安吉盛專利代理有限責任公司61108
• 代理人: 張培勛

1.一種計算中心內部物理主機的選擇方法，其特征在于包括如下步驟：

1)輸入樹及相關參數

給定一個三元組集合G＝(T,r,g)，其中，T代表樹，r代表樹的根節點，g代表計算中心需要提供的虛擬機數目；在樹中有三個變量函數：weight()、height()和path()，其中，weight(r)表示以r為根節點的樹能夠提供的虛擬機數目，height(r)表示以r為根節點的樹的高度，path(r)表示以r為根節點的樹存在的最遠路徑；

樹的子樹的根節點以r_n表示，n為正整數，n的取值范圍為[1,n]，子樹中的變量：weight(r_n)、height(r_n)和path(r_n)，其中，weight(r_n)表示以r_n為根節點的子樹能夠提供的虛擬機數目，height(r_n)表示以r_n為根節點的子樹的高度，path(r_n)表示以r_n為根節點的子樹存在的最遠路徑；

給定變量minHeight、minTree、minPath、longestPath、h1和h2，其中，minHeight表示遍歷過程中局部最優子樹的高度，minTree表示遍歷過程中局部最優的子樹，minPath表示遍歷過程中局部最優子樹的路徑長度，longestPath表示遍歷過程中局部最優子樹的最長路徑長度，h1表示遍歷過程中第一高子樹高度，h2表示遍歷過程中第二高子樹高度；

2)數值初始化

初始化變量，即height(r)＝0，path(r)＝0，height(r_n)＝0，path(r_n)＝0，minHeight初始化為無窮大，minTree初始化為空，longestPath＝0，h1＝0，h2＝0；

3)樹的遍歷

采用后序遍歷的方法，從根節點r開始遍歷樹的所有節點；

4)記錄最小子樹

若minHeight≥height(r_n)，則minHeight＝height(r_n)；若minPath≥path(r_n)，則minPath＝path(r_n)；并記錄最小子樹minTree＝r_n，

判斷weight(r_n)≥g是否成立，若weight(r_n)≥g不成立，則n＝n+1，轉至步驟3)繼續遍歷；若weight(r_n)≥g成立，執行步驟5)；

5)判斷樹的遍歷是否結束

判斷height(r_n)>h1是否成立，若height(r_n)>h1成立，則h2＝h1，h1＝height(r_n)；若height(r_n)>h1不成立，再繼續判斷height(r_n)>h2是否成立，若height(r_n)>h2成立，則h2＝height(r_n)；

若longestPath>path(r_n)，則longestPath＝path(r_n)，即獲取最短的最長路徑長度；

若樹沒有遍歷結束，則n＝n+1，轉至步驟3)繼續遍歷；

判斷h2+h1>longestPath是否成立，若h2+h1>longestPath成立，則path(r_n)＝h2+h1；若h2+h1>longestPath不成立，則path(r_n)＝longestPath；

6)得出最優子樹

判斷minTree是否存在，若minTree存在，weight(r)＝weight(minTree),height(r_n)＝height(minTree)；若minTree不存在，必須判斷樹T的虛擬機數目是否大于g，如果是，minTree＝r,weight(r)＝weight(minTree),height(r)＝height(minTree)，否則沒有最優子樹；

7)選擇最優子樹中的物理主機放置虛擬機

選擇最優子樹中包含的服務器，作為放置虛擬機的物理主機，處理用戶提交的任務或云平臺分配的子任務。