欒明君,羅 翔,曹孝元
中國電子科技集團公司第十五研究所 智能協(xié)同計算技術(shù)實驗室,北京 100083
隨著聯(lián)合軍事行動場景的出現(xiàn),需要大量特定應(yīng)用軟件來完成相關(guān)任務(wù)。由于單個指揮中心的服務(wù)器容量有限,需要在各個指揮中心之間進行網(wǎng)絡(luò)和計算資源共享。而這將面臨軟件分發(fā)效率和部署策略的穩(wěn)定性與資源利用率的問題,具體表現(xiàn)在:一方面,某些軟件需要頻繁在多個相關(guān)指揮中心臨時分發(fā);另一方面,一個指揮中心有限的服務(wù)器資源需要被頻繁地部署大量軟件[1]。本文針對頻繁的軟件分發(fā)和部署需求,對部隊內(nèi)主要依靠傳統(tǒng)的直發(fā)和貪婪或?qū)<医?jīng)驗的方式提出相關(guān)的計算方法和模型,致力于提升軟件分發(fā)和部署的效率。
軟件分發(fā)包括廣泛分布的數(shù)據(jù)中心網(wǎng)絡(luò)中的單播和多播傳輸場景,其中每個指揮中心被抽象為網(wǎng)絡(luò)中的一個節(jié)點[2]。隨著指揮中心數(shù)量的增加和軟件交換頻率的提高,必須靈活利用全局網(wǎng)絡(luò)資源,以避免交通爭用和資源搶占,從而在動態(tài)環(huán)境中實現(xiàn)快速和可靠的數(shù)據(jù)傳輸。
軟件部署是在指揮中心的不同服務(wù)器上為多個不同大小的軟件組分配任務(wù)。依靠專家經(jīng)驗或者簡單的貪婪策略部署將導(dǎo)致嚴(yán)重的性能惡化和計算資源耗盡[3-5]。因此,需要一種根據(jù)其資源占用將每個軟件分配到一個或多個特定服務(wù)器上的更優(yōu)策略,以提高服務(wù)器資源利用率和系統(tǒng)穩(wěn)定性。在本文中,不僅考慮傳統(tǒng)一對一場景,還考慮了單個軟件多次部署的復(fù)雜情況的一對多場景,而這將極大地增加分配的復(fù)雜性,導(dǎo)致專家經(jīng)驗和貪婪規(guī)則的失敗或資源更容易浪費。
本文提出了從軟件分發(fā)到軟件部署的完整解決方案。軟件分發(fā)策略基于一個改進的極小化極大整數(shù)線性規(guī)劃公式,將應(yīng)用軟件數(shù)據(jù)劃分成多個片段,并根據(jù)網(wǎng)絡(luò)能力沿不同路徑同時傳輸優(yōu)化了數(shù)據(jù)劃分和調(diào)度,提高了全局資源利用率和流量平衡,實現(xiàn)了數(shù)據(jù)分發(fā)的高效分發(fā)。對于軟件部署策略,采用改進的整數(shù)多重背包模型,統(tǒng)一地處理每個軟件分配在一個服務(wù)器(一對一)和多個服務(wù)器(一對多)的兩種不同情形,創(chuàng)新地以負載平衡的方式利用服務(wù)器資源,從而大大提高了系統(tǒng)的穩(wěn)定性和資源利用率,適用部隊系統(tǒng)部署場景。仿真結(jié)果表明,軟件分發(fā)模型在25 節(jié)點網(wǎng)絡(luò)相比傳統(tǒng)直傳方式減少了90%分發(fā)時間,軟件部署規(guī)模在300個軟件和15個服務(wù)器場景下最高可提升30%的資源利用率。
本文研究基于軟件劃分的協(xié)同分發(fā)和基于改進多背包模型的軟件部署問題,以優(yōu)化目標(biāo)函數(shù)建立數(shù)學(xué)模型。
針對復(fù)雜化、大規(guī)模和動態(tài)化的信息分發(fā)交互需求,面向多中心分布式網(wǎng)絡(luò)環(huán)境[6-7],提出基于分布式協(xié)同的多向優(yōu)選數(shù)據(jù)并發(fā)技術(shù)[8-9],即針對分布式多中心的域間數(shù)據(jù)分發(fā)問題,綜合利用全網(wǎng)節(jié)點域作為網(wǎng)內(nèi)緩存中繼,并基于網(wǎng)絡(luò)環(huán)境的狀態(tài)感知結(jié)果[8]和基于MiniMax ILP[10-12]的最優(yōu)化流量調(diào)度算法,并行選擇多條信道進行數(shù)據(jù)分片的協(xié)同轉(zhuǎn)發(fā),最大化利用網(wǎng)絡(luò)中的有限資源。同時依靠多節(jié)點域的緩存中繼能力,有效應(yīng)對戰(zhàn)術(shù)環(huán)境下網(wǎng)絡(luò)抖動和中斷情況,提升信息分發(fā)的可靠性。另外,對于重復(fù)發(fā)送的數(shù)據(jù)內(nèi)容,接收方可直接從中繼節(jié)點拉取緩存數(shù)據(jù),而無需從源端重新獲取,從而進一步降低流量開銷。支持基于網(wǎng)絡(luò)資源感知的流量動態(tài)規(guī)劃、彈性調(diào)度和優(yōu)化編排,從而極大增強復(fù)雜異構(gòu)環(huán)境下大規(guī)模通信傳輸適應(yīng)能力、提高基礎(chǔ)信息網(wǎng)絡(luò)資源利用率、提升網(wǎng)絡(luò)管理自動化水平、全面推動網(wǎng)絡(luò)智能化改造進程。
下面以多播分發(fā)方式為例說明分發(fā)機制,其中單播是指只有一個目的節(jié)點,而多播指的是有多個目的節(jié)點。如圖1 所示為多播分布式優(yōu)選數(shù)據(jù)并發(fā)策略的典型示意圖。考慮一個三節(jié)點的多中心互聯(lián)網(wǎng)絡(luò),源節(jié)點A需要同時向三個目的節(jié)點B、C、D發(fā)送同一份數(shù)據(jù),傳統(tǒng)分發(fā)模式采用并行的一發(fā)三模式從A 分別向三個方向發(fā)送三份完整數(shù)據(jù),這種方式將在網(wǎng)絡(luò)中形成三倍的數(shù)據(jù)流量,且最終的任務(wù)完成時間取決于A-B、A-C 和A-D 三條路徑中最差的一條傳輸路徑。而優(yōu)選數(shù)據(jù)并發(fā)策略則有效統(tǒng)籌利用全網(wǎng)的節(jié)點和帶寬資源,從源端最少可以僅發(fā)送一份完整數(shù)據(jù),并利用B、C、D 節(jié)點作為緩存中繼互相為其他目的節(jié)點轉(zhuǎn)發(fā),從而最大化優(yōu)化網(wǎng)絡(luò)資源消耗,且最終的任務(wù)完成時間最大可節(jié)約50%以上。以圖1為例,具體的策略執(zhí)行過程如下:
圖1 分布式優(yōu)選數(shù)據(jù)并發(fā)策略Fig.1 Illustration of collaborated parallel data distribution
(1)在發(fā)送端將原始數(shù)據(jù)分成固定大小的分片,并為每一個分片添加唯一的分片序列號。
(2)獲取從源節(jié)點到目的節(jié)點的路徑狀態(tài)(包括帶寬、丟包率、延時),基于MiniMax ILP 的流量調(diào)度算法將分片分配至不同的路徑并行傳輸。通常來說,具有更多資源的路徑會被分配更多的數(shù)據(jù)分片。
(3)當(dāng)B、C、D 各自分別收到來自A 的部分?jǐn)?shù)據(jù)分片后緩存至本地,并作為中繼節(jié)點將副本轉(zhuǎn)發(fā)至其他兩個目的節(jié)點。
(4)B、C、D同時接收到來自A和其他中繼節(jié)點的數(shù)據(jù)分片并重新整合為完整的數(shù)據(jù)。
基于如上策略,圖1示例網(wǎng)絡(luò)中最終的數(shù)據(jù)分發(fā)結(jié)果如下:
(1)A-B方向,分片1和2傳輸路徑為A-C-D,分片3傳輸路徑為A-B,分片4傳輸路徑為A-D-B;
(2)A-C方向,分片1和2傳輸路徑為A-C,分片3傳輸路徑為A-B-C,分片4傳輸路徑為A-D-C;
(3)A-D方向,分片1和2傳輸路徑為A-C-D,分片3傳輸路徑為A-B-D,分片4傳輸路徑為A-D。
基于軟件分發(fā)策略,提出了一個適應(yīng)擁塞控制的最小最大整數(shù)線性規(guī)劃(ILP)的流量調(diào)度模型。該模型的參數(shù)、輸出變量和約束條件如下詳述。在此基礎(chǔ)上,進一步探討了該模型的實際應(yīng)用。
流量調(diào)度優(yōu)化算法依據(jù)網(wǎng)絡(luò)鏈路的狀態(tài)(可用帶寬、丟包率、延時)分配各方向的數(shù)據(jù)分片數(shù)量,以達到網(wǎng)絡(luò)資源的最大化利用和分發(fā)效率的最大化提升。算法涉及的參數(shù)如下所示:
1.1.1 單播模型
目標(biāo)函數(shù)(1)最優(yōu)化從源節(jié)點到單個目的節(jié)點的分發(fā)效率,即最小化將數(shù)據(jù)分發(fā)到所有目的節(jié)點的最終任務(wù)完成時間。
1.1.2 多播模型
目標(biāo)函數(shù)(4)最優(yōu)化從源節(jié)點到多個目的節(jié)點的分發(fā)效率,即最小化將數(shù)據(jù)分發(fā)到所有目的節(jié)點的最終任務(wù)完成時間。
對于軟件分配策略,采用了一種改進的整數(shù)多重背包模型[4,13-14],相比于文獻[15]使用遺傳算法提高軟件部署中的參數(shù)配置效率而沒有處理軟件部署的系統(tǒng)穩(wěn)定性與資源利用效率問題,本文通過將軟件組分配到不同的服務(wù)器上,以實現(xiàn)服務(wù)器資源的負載均衡,從而極大地提高了系統(tǒng)的穩(wěn)定性。
本文考慮兩種情況。在一對一的軟件分配情況下,每個軟件只分配一次,分配所有軟件后,每個服務(wù)器上的資源占用最平衡。相比之下,在一對多的軟件分配情況下,每個軟件可以在不同的服務(wù)器上被多次分配,這引入了更大的數(shù)學(xué)復(fù)雜性。具體的,考慮一對多的一個例子,將七個軟件分配到四個服務(wù)器上,根據(jù)軟件資源占用和服務(wù)器容量,本文的軟件分配策略提供了最負載平衡和最優(yōu)資源利用的分配方案。如圖2所示,分配結(jié)果是a-A,d-A;b-B,c-B;f-C;e-d,g-D,所有服務(wù)器資源利用率均為0.2%,實現(xiàn)負載均衡的資源利用。
圖2 負載均衡的軟件部署策略Fig.2 Software deployment strategies for load balancing
基于軟件部署規(guī)模的可擴展性、軟件系統(tǒng)的穩(wěn)定性和資源利用效率三方面考慮,構(gòu)建軟件部署的改進多背包模型。給定的參數(shù)和輸出變量如下所示:
給定參數(shù):
k:表示所需安裝的軟件,總數(shù)為K;
m:表示每個服務(wù)器,總數(shù)為M;
sdk:表示安裝第k個軟件所需硬盤大?。?/p>
sgk:表示安裝第k個軟件所需安裝的個數(shù);
sdm:表示第m個服務(wù)器硬盤大??;
輸出參數(shù):
:表示第k個軟件是否安裝在第m個服務(wù)器,取值為0 或者1,其中1 表示安裝,0 表示不安裝。
基于可擴展性、系統(tǒng)整體穩(wěn)定性和整體資源利用率構(gòu)建改進的多背包模型,得到目標(biāo)函數(shù):
服從下述的約束條件:
約束條件(1)表示部署在m臺服務(wù)器上的軟件總的所占硬盤大小不能超過該臺服務(wù)器本身的硬盤大??;約束條件(2)表示部署在所有服務(wù)器上的第k個軟件總和不能超過需要部署的個數(shù);約束條件(3)表示變量取值為0 或者1。約束條件(2)的sgk可以取值1 也可以是其他任意符合要求的正整數(shù),從而該模型將單個軟件只能部署一次和單個軟件可以部署多次兩種情形都涵蓋了,實際上也正是因為該約束條件使得模型最糟糕復(fù)雜度從(2K)M增加至(2K+M)M,由于M一般是遠大于K的,復(fù)雜度的增加導(dǎo)致依靠人工專家經(jīng)驗的部署策略效率遠差于依靠改進背包模型的部署策略。
為了評估軟件分發(fā)和分配策略,本文使用LP 求解器Gekko 和OR-Tools 進行了基于模擬的實驗。為了比較,還實現(xiàn)了傳統(tǒng)的和貪婪的軟件分發(fā)和分配模型。具體而言,對于傳統(tǒng)的軟件分發(fā),源節(jié)點將軟件數(shù)據(jù)文件分發(fā)到目標(biāo)節(jié)點,而不使用其他節(jié)點作為緩存節(jié)點。對于貪婪的軟件分發(fā)模型,軟件數(shù)據(jù)被分割并平均分配到每條路徑上以進行并行傳輸。對于貪婪的軟件分配模型,每個軟件都分配給資源最空閑的服務(wù)器。
對于軟件分發(fā)策略,在10、15、20、25 個節(jié)點的網(wǎng)絡(luò)中進行了100 次迭代的隨機生成網(wǎng)絡(luò)條件的模擬。其中,隨機生成的每條鏈路可用帶寬在100 Mbit/s 到1 000 Mbit/s之間,丟包率在0到10%之間,延時在50 ms到1 s 之間。數(shù)據(jù)文件大小為1 000 MB,并從每個節(jié)點往所有其他節(jié)點分發(fā)。進一步為了直觀地量化表示策略的優(yōu)勢程度,將最優(yōu)策略對比傳統(tǒng)策略的數(shù)據(jù)分發(fā)效率提升定義為:
將貪婪策略對比傳統(tǒng)策略的數(shù)據(jù)分發(fā)效率提升定義為:
2.1.1 單播軟件分發(fā)
圖3 所示為一個25 節(jié)點網(wǎng)絡(luò)的單播分發(fā)結(jié)果對比。由圖中可見,提出的最優(yōu)策略由于采用了最優(yōu)流量調(diào)度算法,在所有100 次仿真中對比其他兩種策略,在分發(fā)時間上均表現(xiàn)出極大的優(yōu)勢。貪婪策略由于采用均分的流量分配模式,得出的分配結(jié)果遠不如最優(yōu)解。而傳統(tǒng)策略則具有最差的分發(fā)效率。
圖3 單播數(shù)據(jù)分發(fā)時間對比Fig.3 Comparison of data distribution time for unicast case
圖4 所示為在不同規(guī)模網(wǎng)絡(luò)下采用不同分發(fā)策略的效率提升對比。其中,在25 節(jié)點網(wǎng)絡(luò)中采用最優(yōu)策略對比傳統(tǒng)策略可實現(xiàn)85%以上的效率提升,且隨著網(wǎng)絡(luò)規(guī)模擴大,提升效果也更明顯。相比之下,貪婪策略對比傳統(tǒng)策略也有60%~80%的效率提升,但仍不及提出的最優(yōu)策略。其原因在于最優(yōu)策略實際在值域空間中選取了最優(yōu)的流量分配解,而貪婪策略則只選取了平均解。
圖4 單播數(shù)據(jù)分發(fā)效率提升Fig.4 Improvement ratio of data distribution efficiency for unicast case
2.1.2 多播軟件分發(fā)
圖5 展示了在一個25 個節(jié)點的網(wǎng)絡(luò)中多播軟件分發(fā)策略效果。在所有的100個樣本中,全局網(wǎng)絡(luò)資源進行并行傳輸?shù)淖顑?yōu)方式明顯優(yōu)于貪心和傳統(tǒng)的軟件分發(fā)模型。
圖5 多播數(shù)據(jù)分發(fā)時間對比Fig.5 Comparison of data distribution time for multicast case
圖6可以看出,最優(yōu)分發(fā)模型相比傳統(tǒng)直傳方式可以減少85%左右的分發(fā)時間而貪婪模型只能減少75%左右,顯示出最優(yōu)模型的優(yōu)勢。
圖6 多播數(shù)據(jù)分發(fā)效率提升Fig.6 Improvement ratio of data distribution efficiency for multicast case
實際上,極小化最大整數(shù)線性規(guī)劃(ILP)方法試圖在廣闊的搜索空間中尋找最優(yōu)解,傳統(tǒng)的投遞算法和貪心的投遞算法的結(jié)果可以被視為整個搜索空間中的兩個特殊解決方案,對于傳統(tǒng)的投遞算法,被安排到緩存節(jié)點的數(shù)據(jù)切片設(shè)置為0,而對于貪心投遞算法,被安排到所有緩存節(jié)點的數(shù)據(jù)切片是相等的。因此,合理地說這兩個解決方案的性能應(yīng)該比最優(yōu)解決方案差,這與仿真結(jié)果是相符的。
對于軟件分配策略,運行了一對一和一對多兩種情況的模擬。對于每種情況,隨機生成了100個軟件和服務(wù)器條件。模擬參數(shù)隨機生成如下:軟件大小在300 MB和10 000 MB之間隨機生成,服務(wù)器存儲大小在200 GB和600 GB 之間隨機生成。對于一對多的情況,每個軟件的數(shù)量在1 到2 之間隨機生成,總軟件數(shù)量為300 和200兩種場景,服務(wù)器數(shù)量為10和15兩種。
2.2.1 1對1軟件部署仿真
圖7 展示了在300 個軟件和15 個服務(wù)器的一對一場景,從仿真圖可看出最優(yōu)部署策略資源利用效率遠高于貪婪策略,這是因為最優(yōu)策略能夠以最優(yōu)且負載平衡的方式充分利用全局服務(wù)器資源。
圖7 一對一軟件部署效率對比Fig.7 One-to-one software deployment efficiency comparison
2.2.2 1對多軟件部署仿真
圖8 展示了在300 個軟件和15 個服務(wù)器的一對多場景,從仿真圖可看出最優(yōu)部署策略資源利用效率仍然遠高于貪婪策略。
圖8 一對多軟件部署效率對比Fig.8 One-to-many software deployment efficiency comparison
表1 列出了一對一和一對多在各種場景下平均資源利用情況。對于一對一情況,最優(yōu)策略相對貪婪模型提高了接近30%的資源利用率,對于一對多情況,最優(yōu)策略相對貪婪模型最高實現(xiàn)了接近20%的資源利用率提升,最后一列給出了最優(yōu)部署策略相比貪婪策略資源利用率具體的提升比率。最優(yōu)軟件分配策略在廣泛的搜索空間中尋找最優(yōu)且負載平衡的解決方案。事實上,貪婪模型的解決方案可以被視為整個搜索空間中的特殊解決方案。因此,貪心模型的性能比最優(yōu)解決方案差是可以理解的,這與模擬結(jié)果相符。
表1 最優(yōu)策略與貪婪策略部署資源利用率對比Table 1 Comparison of resource utilization between optimal strategy and greedy strategy deployment
為了進一步驗證分發(fā)和部署策略技術(shù)的可行性,分別進行了多播分發(fā)和軟件部署的實驗場景驗證。
為進一步驗證提出的技術(shù)可行性,搭建了一個四節(jié)點網(wǎng)絡(luò),并基于可靠UDP傳輸協(xié)議實現(xiàn)數(shù)據(jù)分發(fā)策略,實驗拓撲參考圖1,測試從A往B、C、D三個節(jié)點分發(fā)數(shù)據(jù)的場景。首先測試對比最優(yōu)策略與傳統(tǒng)策略。數(shù)據(jù)文件大小為1 GB,設(shè)置每條鏈路具有相同的帶寬、丟包率和延時,其中帶寬固定為1 Gbit/s,丟包率和延時變化。對比測試的數(shù)據(jù)分發(fā)時間結(jié)果如表2所示(鏈路狀態(tài)為鏈路丟包率和延時)。在相同網(wǎng)絡(luò)條件和數(shù)據(jù)樣本下,采用最優(yōu)策略比采用傳統(tǒng)策略用時平均減少50%以上,最后一行給出了具體的提升效率。
表2 最優(yōu)策略與傳統(tǒng)策略數(shù)據(jù)分發(fā)時間對比Table 2 Comparison of data distribution time for optimal strategy and conventional strategy
其次測試對比最優(yōu)策略與貪婪策略。鏈路狀態(tài)設(shè)置為:A-B,帶寬1 Gbit/s,丟包率0%,延時0 ms;A-C,帶寬800 Mbit/s,丟包率2%,延時50 ms;A-D,帶寬500 Mbit/s,丟包率4%,延時100 ms;其他鏈路,帶寬1 Gbit/s,丟包率0%,延時0 ms。表3 所示為采用兩種策略的數(shù)據(jù)分發(fā)時間對比(運行10 次實驗測試)。結(jié)果顯示,采用最優(yōu)策略與貪婪策略相比,數(shù)據(jù)分發(fā)用時平均減少57%,具體提升為表3最后一列。
表3 最優(yōu)策略與貪婪策略數(shù)據(jù)分發(fā)時間對比Table 3 Comparison of data distribution time for optimal strategy and greedy strategy
為了驗證軟件部署策略的有效性,考慮五臺服務(wù)器的實際部署場景。其中,五臺服務(wù)器的配置相同,內(nèi)存均為16 GB,存儲空間分別是512 GB、512 GB、1 TB、256 GB、1 TB,待部署軟件有160 個,這些軟件包括Tomcat-9.027、人大金倉數(shù)據(jù)-12.1.0.2、Python-3.5.2、neo4j-3.5.9、py2neo-4.3.0、Flask-1.1.2、curl-7.71.1 等相關(guān)軟件應(yīng)用,軟件大小從35 MB 到2.1 GB 不等。下面針對一對多部署場景隨機從160個軟件中抽取100個軟件測試10組部署數(shù)據(jù),對比貪婪和目標(biāo)部署策略。表4實驗數(shù)據(jù)表明,對于有多種大小服務(wù)器部署的場景,貪婪策略對資源利用率更低,本文所提出的部署策略具有更好的平均資源利用率,利用率提高了大約17%,具體提升比率為表4最后一列。
表4 最優(yōu)策略與貪婪策略軟件部署資源利用率對比Table 4 Comparison of resource utilization between optimal strategy and greedy strategy deployment
由于需要使用大量種類繁多的應(yīng)用軟件來完成相關(guān)任務(wù),而單個指揮中心的服務(wù)器容量有限,因此需要在各個指揮中心之間進行網(wǎng)絡(luò)和計算資源共享。針對目前軟件分發(fā)和部署所存在的效率與穩(wěn)定性和資源利用率等問題,提出了軟件分發(fā)和部署模型提高分發(fā)效率和部署的穩(wěn)定性與資源利用率。具體而言,對于軟件分發(fā),將軟件數(shù)據(jù)分成多個片段,并沿不同路徑傳輸,通過不同路徑并行傳輸,實現(xiàn)數(shù)據(jù)的協(xié)同傳輸。對于軟件部署,通過考慮負載均衡,利用改進的整數(shù)多背包模型構(gòu)建了部署策略,實現(xiàn)部署的穩(wěn)定性和資源利用率的提升。仿真結(jié)果表明,在一個25節(jié)點網(wǎng)絡(luò)中,軟件分發(fā)策略減少了最高85%以上的傳輸時間;對于300個軟件和15個服務(wù)器的軟件部署場景,軟件部署策略提高了最高30%的資源利用率。更進一步,通過實驗環(huán)境驗證,軟件分發(fā)最優(yōu)策略相比于傳統(tǒng)的直發(fā)和貪婪的均發(fā)方式都能減少50%以上的傳輸時間,軟件部署資源利用率相比貪婪的方式可提高20%左右資源利用率。表明本文所提出的軟件分發(fā)和部署策略的有效性。
更進一步,某些特殊情形下會遇到網(wǎng)絡(luò)抖動的軟件分發(fā)和帶依賴關(guān)系的復(fù)雜軟件部署問題,而目前分發(fā)模型是無法處理網(wǎng)絡(luò)抖動的情形,部署模型也需要改進才可以處理帶依賴關(guān)系的部署問題。后續(xù)將改進本文相關(guān)的方法去解決上述問題。