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

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

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

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

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