Posted by Mr. Friday
分散式網路中的Power Law現象
前面談到了網路流量的80/20法則，網路上有80%左右的流量都貢獻給了P2P，而事實上，在P2P的世界裡頭，也到處有著Power Law的影子。
大家先別只想到BT跟eMule。其實這個世界上到處充斥著分散式的系統，而其中許多的網路結構都是以Power Law的模樣呈現：從通訊網路、社交網路、到生物網路都有，譬如著名的AT&T的電話網路紀錄。在這篇2000年研究文獻裡 面提到，他們統計過AT&T的電話通聯紀錄，結果發現群眾的通聯模式也符合Power Law的關係。如果說每個人都是平面上的一個點，而每播一通電話就是一條線、連接著播/接電話的兩個人，那麼將可觀察到大多數的點只有幾條連線，但有極少 數的點，可連線通往大多數的點──換言之，大多數人可能一天當中只會打給固定幾個人，但有少數人士可能一次打個幾十通上百通。〈當然啦，這些人也有可能是 出於電話行銷、業務員、或是電話詐騙才會打那麼多電話，但有這些樣本才算是反映了真實世界。〉
電話網路如此，電腦網路也是如此。大家現在在用的WWW超連結也有著這樣的關係。先前Mr。Saturday寫過Web上的人際網路 - 網路長什麼樣子？描述的就是這個現象。前面不是把打電話類比成圖案嗎？現在請你想像一個網站是一個點，點跟點之間的連線代表超連結，那麼這張圖會長什麼樣呢？
這個網站把它弄成3D的圖案，看起來很漂亮，其實仍然不脫是一個Power Law Graph！網路當中有極少數的網站，可以通往這世界上大部分的其他網站。
再回到我們所熟悉的P2P軟體下載軟體，根據前面的兩個先例，各位要不要猜猜P2P分享網路當中又有哪裡是符合Power Law特性的呢？
應該有的人已經猜出來了！如果我們把使用P2P軟體的人當成平面上的一個點，我向別人下載一個檔案就算是我跟他之間的一條連線，那麼…沒錯，得到的也會是一個Power Law Graph，透過少數節點把整個網路連結起來。畫成圖案的話大概是像這樣：
出處一樣是前述的網站，這是利用早期P2P分享軟體Gnutella的一個支派，叫Gnucleus，蒐集得到的資料。〈雖然醜了點…〉
P2P搜尋機制的契機：利用Power User
有的人應該忍不住要問了：知道這個又怎樣？對我的影響又不大。其實…對於現在大家用到的P2P分享軟體而言，影響還蠻大的！當初我的這篇文章透視BT（四）──為什麼BT沒有內建搜尋功能?裡面，曾經提過：
如 同前面的例子，搜尋的方法也分成兩種，一種是主從式架構型的，一種是純P2P式的。很不幸的，純P2P式的搜尋到目前為止，可說都是非常沒有效率的(只有 極少極少的例外)。純P2P型搜尋方式的代表為Anthill。顧名思義，搜尋的過程就像螞蟻找食物, 使用者發出很多小小隻的螞蟻，挨家挨戶的去敲門，看看有沒有好心人願意提供使用者想要的食物。有的話就傳送回來。沒有的話? 只好認栽. 事實上因為網路使用者眾多，小螞蟻們根本不可能爬完所有門戶，所以這種搜尋方式也不能保證找到應該要有的檔案. 這種略帶殘缺的搜尋方式被應用在早期的Gnutella，FreeNet，以及現在日本的winny。
主 從式的搜尋方法就比較有效率。一開始由一個人負責匯整班上所有同學手上的清單，然後再讓同學根據清單來找尋他想要的玩具。不會出現”明明網路上有人有檔， 為啥程式告訴我找不到”的現象。早期大紅的Knapster就是這類的代表。不過就如同我前面所說主從式的缺點；雖然有效率，可是遇到人多的時候就會塞 車，伺服器端的資源耗得又凶又快。
其實當時我沒有特別提到如果把Power Law這個因素考慮進去會怎麼樣。我們現在來假想一種狀況：如果，在P2P分想網路裡的每一個人，都記載著他的朋友擁有什麼檔案，以及他朋友的朋友擁有什 麼檔案〈就是第二層朋友啦〉，這樣的話能夠有什麼改善？嘿嘿，你有沒有發現，這樣一來「擁有最多朋友的那些人，他們手上的檔案清單將會相當詳盡」！記不記 得我們常說什麼根據社會學家統計，這世界上隨便兩個人的朋友關係不超過六個人〈可以說這世上的任何一個人都是我的朋友的朋友的朋友的朋友的朋友的朋友〉， 到底跟這是一模一樣的，因為P2P網路關係與人際關係一樣都符合Power Law。所以對於擁有最多朋友的那些人來說，手中若握有兩層朋友檔案清單，幾乎可以說是擁有整個P2P網路資源清單的大半。透過這些人來進行搜尋，豈不甚 好？
這就是Search in Power Law Networks這 篇經典研究文章的概念。每一個人要找檔案時，會先詢問網路中擁有最多朋友的人：「嘿，你知不知道誰有這個檔案？」若他不知道，再詢問網路上朋友第二多的 人：「嘿，你知不知道誰有這個檔案？」根據這篇文章的模擬實驗，它建立了一個七百人的小型網路，並且假設每個檔案只會存在一台機器裡面，結果顯示，50% 的檔案只需要8步以內就可以找到。
覺得還是不夠快嗎？可別忘了這是P2P式的搜尋，因此不需要建立伺服器來 幫忙搜尋，有這樣的效能，已經很不錯了。當然，這套方式還是有不少實作上的缺陷，例如對朋友多的人來說，手上的檔案清單將會長得非常大、查詢的流量將會相 當可觀，而且一旦網路連結方式不是Power Law Graph就沒用了。但無論如何這篇發表自2000年的文章總是給了P2P軟體設計者一些指引的方向。從使用情境推測，Winny/Share的 Cluster word機制，似乎也利用了Power Law的特性。
利用Power User建構P2P式的MMOG！
接下來這一段或許有點難以想像，不過真的有人在進行這樣的研究，那就是 P2P式的線上遊戲。事實上一個大型的線上遊戲，是非常耗費伺服器系統資源與頻寬的，所以遊戲公司不得不建立多個伺服器，以應付多個網友的需求。但也因為 這樣，導致連上不同伺服器的人，無法與另一個伺服器的玩家溝通，一個遊戲世界事實上被切割成多個平行世界，對玩家來說，多少有所缺憾。
也因此，學術界有一些研究，就是試圖透過P2P的機制，分享伺服器的負載，甚至終極目標是有一天能不透過伺服器就能進行遊戲。如果成功的話整個遊戲世界通通是連結在一起的，多好啊！
怎麼作呢？雖然P2P的線上遊戲還不成熟，但概念大致上差不多：把一個虛 擬的世界，切分成數個分離的區域。每個區域的活動就由網路世界裡面的部分玩家代管。請注意，不一定是要由身在該區域的玩家才能管理喔。每位學者可能有不同 的設計，譬如WOW裡面整個奧格瑪區域可能是由幾位散落在雷霆崖、幽暗城的玩家所管理，也可能是由奧格瑪當地的遊戲成員自己管理，端看系統怎麼設計。
當然，這其中，有一派的學者就是透過遊戲裡面的Power User來協助建構P2P的線上世界。忘了是在哪一篇paper看到，玩家在P2P下載軟體中停留的時間，也呈現80/20的分布，如果這項趨勢在線上遊 戲中也一樣的話，那麼系統業者利用這些人分擔一些系統運算與頻寬似乎也是十分理所當然的事。〈不過這些人很有可能是代練功的，但反正這些人吃飽閒閒沒事也 不會下線…〉
不過P2P的MMOG距離成熟還有一大段距離，首先第一個問題：「作弊」就很難遏止。畢竟這種模式把伺服器的全部或一部分權限交到不認識的玩家手 中，這些玩家會不會濫用權力？答案幾乎是肯定的。再者，遊戲反應時間掌握在部分玩家手中，如果這些玩家時常上上下下離開遊戲，對於其他玩家一定會造成影 響；而且系統能夠容納多少人、演算法架構是否夠完整…都還需要經過完整的測試。畢竟線上遊戲是真的要收費的，任何一個環節有問題，不但客服電話會接到手 軟，可能還會有黑道玩家找上門來要幹架喔！〈可參考PTT八卦版相關討論文章：有沒有線上遊戲收益的八卦！〉
結語
前幾篇說過，Power Law的現象幾乎無所不在，而在不同的研究領域裡，它可能會有完全不同的解讀。這幾篇下來我們陸續談過了長尾理論、社交與書籤網站，以及本篇的P2P網路。至於其他領域嘛…一時之間還想不到，有機會的話再更新囉！
發表文章
沒有留言:
張貼留言