基于光網(wǎng)絡(luò)的分布式計(jì)算系統(tǒng)中任務(wù)與通信的聯(lián)合調(diào)度研究.pdf

1、分布式計(jì)算將分散在不同地方的計(jì)算、存儲(chǔ)等資源集結(jié)起來(lái),協(xié)同合作,從而獲得可觀的計(jì)算能力,以便用于實(shí)現(xiàn)復(fù)雜的科學(xué)計(jì)算任務(wù)。很多高級(jí)應(yīng)用不但是計(jì)算密集型,更體現(xiàn)出數(shù)據(jù)密集型,即計(jì)算任務(wù)執(zhí)行期間將會(huì)產(chǎn)生大量數(shù)據(jù)(從GB到TB甚至PB級(jí)),并在多個(gè)計(jì)算資源間進(jìn)行大塊數(shù)據(jù)傳輸。這就要求網(wǎng)絡(luò)能夠提供大帶寬、低延遲的數(shù)據(jù)傳輸能力。傳統(tǒng)的IP網(wǎng)絡(luò)顯然無(wú)法滿足這種較高的OoS要求,因此研究人員將目光轉(zhuǎn)向光網(wǎng)絡(luò),期望能夠直接在光網(wǎng)絡(luò)上構(gòu)筑分布式計(jì)算系統(tǒng)以滿

2、足數(shù)據(jù)密集型的分布式科學(xué)計(jì)算應(yīng)用。
　　 為了實(shí)現(xiàn)分布式計(jì)算,需要將復(fù)雜的、大型的計(jì)算任務(wù)分解為若干小任務(wù),并將其調(diào)度到可用計(jì)算資源上,同時(shí)實(shí)現(xiàn)某種優(yōu)化目標(biāo)。分布式環(huán)境下的任務(wù)調(diào)度已有大量研究,但大都基于分組交換網(wǎng)絡(luò)(如IP網(wǎng)絡(luò))。在數(shù)據(jù)量交換不多的情況下,很多研究直接將底層網(wǎng)絡(luò)假設(shè)為任意節(jié)點(diǎn)對(duì)間可隨時(shí)通信的全互聯(lián)理想網(wǎng)絡(luò)模型。當(dāng)網(wǎng)絡(luò)系統(tǒng)替換為光網(wǎng)絡(luò)時(shí),通信機(jī)制變?yōu)榫€路交換。由于傳輸數(shù)據(jù)之前需要事先建立固定帶寬的光路連接,并且接

3、入端口只具有單可達(dá)性,這就會(huì)使通信建立存在一定的阻塞概率。傳統(tǒng)的任務(wù)調(diào)度模型無(wú)法直接應(yīng)用于光網(wǎng)絡(luò)互聯(lián)場(chǎng)景,因此在將任務(wù)分配到計(jì)算資源上的同時(shí),需要協(xié)同考慮資源間的光路建立。
　　 本論文研究任務(wù)分配與光路建立的聯(lián)合調(diào)度問題,該問題之前鮮有研究。我們首先研究了在專有光網(wǎng)絡(luò)下的聯(lián)合調(diào)度模型和算法以及減少通信競(jìng)爭(zhēng)沖突的優(yōu)化策略,然后研究了在公共光網(wǎng)絡(luò)下基于動(dòng)態(tài)共享光虛擬專用網(wǎng)(OVPN,OpticalVirtual Private N

4、etwork)的聯(lián)合調(diào)度問題,最后設(shè)計(jì)并實(shí)現(xiàn)了面向分布式計(jì)算應(yīng)用的跨域OVPN服務(wù)接口體系。
　　 第一章緒論首先介紹了基于光網(wǎng)絡(luò)互聯(lián)的分布式計(jì)算的發(fā)展背景,然后分別綜述了分布式計(jì)算中的任務(wù)調(diào)度和光網(wǎng)絡(luò)中的光路調(diào)度的研究現(xiàn)狀,并分析了研究聯(lián)合調(diào)度的必要性。
　　 第二章研究了聯(lián)合調(diào)度模型和算法。大規(guī)模的分布式科學(xué)計(jì)算應(yīng)用大都由一系列具有相互依存關(guān)系的任務(wù)組成,并按照某種工作流方式實(shí)現(xiàn)最終計(jì)算任務(wù)。這種工作流一般采用有向無(wú)

5、圈圖(DAG:Directed Acyclic Graph)來(lái)統(tǒng)一描述。因此我們研究的聯(lián)合調(diào)度可抽象為光網(wǎng)絡(luò)感知的DAG調(diào)度問題。列表調(diào)度算法是DAG調(diào)度中最常用的啟發(fā)式算法,為此我們根據(jù)聯(lián)合調(diào)度模型對(duì)列表調(diào)度算法進(jìn)行了擴(kuò)展,在將DAG中的任務(wù)節(jié)點(diǎn)調(diào)度到計(jì)算資源上的同時(shí),協(xié)同考慮將DAG邊調(diào)度到網(wǎng)絡(luò)的鏈路上,從而實(shí)現(xiàn)了任務(wù)與光路的聯(lián)合調(diào)度。
　　 第三章基于擴(kuò)展列表調(diào)度算法分別從路由策略和計(jì)算資源選擇策略兩個(gè)方面研究了如何減少網(wǎng)

6、絡(luò)資源沖突的優(yōu)化措施。對(duì)于路由策略,我們提出了一個(gè)自適應(yīng)路由算法,在調(diào)度某條光路時(shí)能夠繞過擁塞鏈路并選取一條最先開始的最短路由；對(duì)于計(jì)算資源選擇策略,我們的做法是盡量讓后繼任務(wù)節(jié)點(diǎn)調(diào)度到離前繼任務(wù)節(jié)點(diǎn)所在資源較近的計(jì)算資源上,其思想是盡量減少光路的建立跳數(shù),從而減少光路對(duì)資源的占用和產(chǎn)生沖突的可能性。仿真結(jié)果表明兩種策略各有優(yōu)勢(shì):自適應(yīng)路由策略對(duì)于減小調(diào)度長(zhǎng)度效果明顯,而資源選擇策略有利于提高任務(wù)調(diào)度對(duì)網(wǎng)絡(luò)資源的使用使用效率。當(dāng)二者結(jié)合

7、使用時(shí),優(yōu)勢(shì)互補(bǔ),可獲得最佳調(diào)度結(jié)果。
　　 第四章研究了在公共光網(wǎng)絡(luò)上如何實(shí)現(xiàn)聯(lián)合調(diào)度的問題。由于在公共光網(wǎng)絡(luò)場(chǎng)景下運(yùn)營(yíng)商考慮到商業(yè)利益,不會(huì)向計(jì)算用戶提供全網(wǎng)的資源信息,因此無(wú)法實(shí)現(xiàn)基于全網(wǎng)拓?fù)湫畔⒌穆?lián)合調(diào)度,為此我們提出采用光虛擬專用網(wǎng)(OVPN)方式解決這一問題。OVPN資源可以是專有的或是共享的。對(duì)于專有OVPN可以直接使用之前提到的靜態(tài)調(diào)度算法,但是會(huì)占用過多的網(wǎng)絡(luò)資源。動(dòng)態(tài)共享OVPN可以提高網(wǎng)絡(luò)資源使用效率,但引

8、入了網(wǎng)絡(luò)資源的動(dòng)態(tài)變化,為此我們提出了一種低開銷的基于靜態(tài)調(diào)度的動(dòng)態(tài)重調(diào)度機(jī)制。仿真實(shí)驗(yàn)顯示,在中等網(wǎng)絡(luò)負(fù)載以下,基于動(dòng)態(tài)共享OVPN的重調(diào)度機(jī)制可以獲得接近于基于全網(wǎng)的靜態(tài)聯(lián)合調(diào)度的調(diào)度效果,并具有現(xiàn)實(shí)可行性。
　　 第五章研究了在多域光網(wǎng)絡(luò)環(huán)境下如何為分布式計(jì)算應(yīng)用實(shí)現(xiàn)跨域OVPN服務(wù)的接口體系。通過提供跨域OVPN服務(wù),可以為計(jì)算用戶屏蔽底層多域環(huán)境和復(fù)雜的域間操作,使之感覺仍然為單域環(huán)境。我們分析了面向分布式計(jì)算的跨域O

9、VPN服務(wù)新的應(yīng)用需求,并提出了一個(gè)層級(jí)式跨域OVPN服務(wù)平面體系構(gòu)架。與其他OVPN服務(wù)平面實(shí)現(xiàn)方式不同,我們基于控制平面中的流量工程數(shù)據(jù)庫(kù)(TrafficEngineering Database,TED)實(shí)現(xiàn)OVPN資源的分割和虛擬化；通過對(duì)OVPN資源及其操作封裝并實(shí)例化為對(duì)象實(shí)現(xiàn)OVPN管理控制的劃分和隔離。我們基于webservice實(shí)現(xiàn)了跨域OVPN服務(wù)的調(diào)用接口,調(diào)度器可以直接編程實(shí)現(xiàn)OVPN資源的創(chuàng)建、信息獲取,光路拆建