改善非結(jié)構(gòu)化對(duì)等式網(wǎng)

1、1 改善非結(jié)構(gòu)化對(duì)等式網(wǎng)之訊息傳遞策改善非結(jié)構(gòu)化對(duì)等式網(wǎng)之訊息傳遞策 作者：許志貴作者：許志貴 中華民國(guó) 九十七 二 月2簡(jiǎn)介簡(jiǎn)介lGnutella：以氾式詢問(Query Flooding)的方式搜尋附近的所有結(jié)的節(jié)點(diǎn)，將查詢到的訊息資按照原詢問多條徑隨機(jī)選擇一條回傳，達(dá)到搜尋資和回覆訊息的效果。l研究顯示使用氾式詢問(Query Flooding) 10,14這方法的系統(tǒng)，如Gnutella，通常在網(wǎng)搜尋時(shí)，可以在TTL (Time-to-Live) 於七時(shí)，將百分之九十五的節(jié)點(diǎn)尋訪完畢。3簡(jiǎn)介簡(jiǎn)介l氾式詢問的優(yōu)點(diǎn)：受節(jié)點(diǎn)頻繁加入和退出環(huán)境的影響很小容錯(cuò)能l氾式詢問的缺點(diǎn)：產(chǎn)生多餘的尋訪程

2、(overlay network)將相同的詢問資訊發(fā)送給對(duì)方多餘的查詢?cè)斐深l寬的消耗4目標(biāo)目標(biāo)l是否可以詢問到最多的節(jié)點(diǎn)，並且減少詢問時(shí)所產(chǎn)生的多餘訊息。5方法方法lMax Neighbor BroadcastlMax-Min TraversallMulti-Max-Min TraversallHybrid Max-Min Traversal6方法方法7方法方法1：Max Neighbor Broadcastl把廣播隔開的方式減少詢問訊息，間隔one-hop再做廣播。l間隔動(dòng)作部分，我們會(huì)選擇出這一個(gè)節(jié)點(diǎn)的鄰居中，其鄰居節(jié)點(diǎn)最多的那一個(gè)節(jié)點(diǎn)當(dāng)我們選擇的徑。8方法方法1：Max Neighbor

3、 Broadcast9方法方法2：Max-Min Traversall拿掉廣播這個(gè)動(dòng)作，針對(duì)鄰居最大跟最小的這種節(jié)點(diǎn)做徑選擇。10方法方法2：Max-Min Traversal11方法方法3：Multi-Max-Min Traversall由於Max-Min Traversal很容易miss掉節(jié)點(diǎn)，所以嘗試增加詢問的路徑。12方法方法3：Multi-Max-Min TraversalN：設(shè)定發(fā)送給N個(gè)倍數(shù)之Max-Min Neighbor Degree的節(jié)點(diǎn)EX：N = 213方法方法4：Hybrid Max-Min TraversallMax-Min Traversal下增加廣播的方法，每隔

4、數(shù)個(gè)hops做一次廣播。14方法方法4：Hybrid Max-Min TraversalM：廣播積分。這個(gè)積分會(huì)依照每一個(gè)節(jié)點(diǎn)的鄰居大小下去扣除，當(dāng)廣播積分M被扣到以下時(shí)，這個(gè)扣到的節(jié)點(diǎn)就會(huì)直接進(jìn)廣播的動(dòng)作。EX：M = 5M = 1M = 3M = 1M = 5M = 0M = 0M = 515效能評(píng)估效能評(píng)估l實(shí)驗(yàn)環(huán)境與架構(gòu) Borland C+ Builder撰寫模擬的程式節(jié)點(diǎn)數(shù)：200 2000N = 2M = 20節(jié)點(diǎn)平均degree = 8query停止條件：尋問訊息之前已經(jīng)接收過就會(huì)轉(zhuǎn)發(fā)。16效能評(píng)估效能評(píng)估l實(shí)驗(yàn)結(jié)果 17效能評(píng)估效能評(píng)估l實(shí)驗(yàn)結(jié)果 18效能評(píng)估效能評(píng)估l實(shí)驗(yàn)結(jié)果 Multi-Max-Min Traversal19效能評(píng)估效能評(píng)估l實(shí)驗(yàn)結(jié)果 Multi-Max-Min Traversal20效能評(píng)估效能評(píng)估21結(jié)論結(jié)論l在這篇文中，提出同的方法改善在分散式非結(jié)構(gòu)化P2P overlay network系統(tǒng)中的訊息詢問方式。針對(duì)較為簡(jiǎn)的氾式詢問(Query Flooding)方法做同的衍生，