復(fù)雜網(wǎng)絡(luò)中的計(jì)算遷移問題.pdf

1、Internet作為迄今為止最復(fù)雜的人工系統(tǒng),在其雜亂無章的表象下卻隱藏著令人吃驚的大范圍模式的秩序與結(jié)構(gòu).為此,本文通過分析研究CAIDA的Skitter項(xiàng)目提供的Internet監(jiān)測(cè)數(shù)據(jù)中蘊(yùn)藏的某些復(fù)雜網(wǎng)絡(luò)的特征和規(guī)律,來研究復(fù)雜網(wǎng)絡(luò)上的計(jì)算遷移問題.提出了"計(jì)算遷移"的思想.由于處在不同地域的用戶對(duì)計(jì)算需求的不平衡性,導(dǎo)致了Internet上的資源呈現(xiàn)出不均勻分布,即在一些小生境中,資源豐富,而在另外一些小生境中,卻資源匱乏.另外

2、,Internet上各種網(wǎng)絡(luò)設(shè)備的移動(dòng)性和鏈路的多變性,使資源不再固定或穩(wěn)定,而是動(dòng)態(tài)變化的.在這種資源動(dòng)態(tài)變化以及分布不均勻的環(huán)境中,為了實(shí)現(xiàn)有限資源的最大化利用,當(dāng)本地的資源有限,或剩余資源已不能滿足用戶計(jì)算任務(wù)的需求時(shí),將計(jì)算任務(wù)遷移到資源豐富,運(yùn)行環(huán)境良好的節(jié)點(diǎn)上繼續(xù)運(yùn)行,將能得到更好的性能表現(xiàn).即計(jì)算任務(wù)隨資源的變化而進(jìn)行遷移,實(shí)現(xiàn)"資源在哪里,就到哪里計(jì)算".由于Internet上資源分布的動(dòng)態(tài)性,為了能有效利用其上的資源,

3、資源發(fā)現(xiàn)也是本文要解決的一個(gè)問題.針對(duì)Internet網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中節(jié)點(diǎn)的度分布存在"冪律"分布,以及Internet網(wǎng)絡(luò)中存在"小世界"的特征,引入TCP/IP中動(dòng)態(tài)路由的思想,提出一種新的資源發(fā)現(xiàn)算法—連接度優(yōu)先路由查找(CFR)算法.該算法能有效降低網(wǎng)絡(luò)節(jié)點(diǎn)之間的通信開銷和減少對(duì)每個(gè)查詢進(jìn)行處理的節(jié)點(diǎn)數(shù)量,解決了傳統(tǒng)的"廣播擴(kuò)散"方式來搜索網(wǎng)絡(luò)上共享資源而造成網(wǎng)絡(luò)流量急劇增加的問題.基于CFR算法和"計(jì)算遷移"思想,提出了資源可用