線上社交網路頻寬及延遲感知同儕式好友群播

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：24

、訪客IP：3.145.155.149

姓名

洪兆緯(Chao-wei Hung) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

線上社交網路頻寬及延遲感知同儕式好友群播
(Bandwidth- and Latency-Aware Peer-to-Peer FriendCast for Online Social Network)

相關論文

★ 以IEEE 802.11為基礎行動隨意無線網路之混合式省電通訊協定	★ 以范諾圖為基礎的對等式網路虛擬環境相鄰節點一致性研究
★ 行動隨意網路可調適及可延展之位置服務協定	★ 同儕式網路虛擬環境高效率互動範圍群播
★ 巨量多人線上遊戲之同儕網路互動範圍語音交談	★ 基於范諾圖之同儕式網路虛擬環境狀態管理
★ 利用多變量分析之多人線上遊戲信任使用者選擇	★ 無位置資訊無線感測網路之覆蓋及連通維持
★ 同儕網路虛擬環境3D串流同儕選擇策略	★ 一個使用802.11與RFID技術的無所不在導覽系統U-Guide之設計與實作
★ 同儕式三維資料串流	★ IM Finder: 透過即時通訊網路線上使用者找尋解答
★ 無位置資訊無線感測網路自走車有向天線導航與協調演算法	★ 多匯點無線感測網路省能及流量分散事件輪廓追蹤
★ 頻寬感知同儕式3D串流	★ 無線感測網路旋轉指向天線定位法

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

近年來線上社交網路(Online Social Network, OSN)越來越熱門，朋友之間藉由此類型平台進行互動交流也越趨頻繁。主從式架構下的線上社交網路不僅帶來伺服器頻寬和計算有限的瓶頸，也帶來了擴充性的疑慮。本論文預期設計一個同儕式頻寬及延遲感知好友群播(FriendCast, FC)的方法，可以讓線上社交網路中的每個使用者利用同儕式的方法對所有的好友進行即時訊息的發佈。方法中每個使用者對所有的朋友建立好友群播樹(FriendCast Tree, FCT)，首先系統仍會存在一個伺服器用來提供註冊和登入功能以及輔助好友群播樹快速的建立。而新的使用者加入系統時會先向伺服器註冊並擁有自己的網路座標(Network Coordinate, NC)，由於任兩個使用者間的資料傳送延遲和彼此的網路座標距離成比例關係，所以我們可以藉由他們的座標點來預估任兩點間的延遲時間，並作為建立好友群播樹的依據。我們在論文中提出Degree-Adapted Greedy Tree Algorithm(DATGA)，以可用外分支度預估(available out-degree estimation)方法來估計每個好友在好友群播樹中合理的外分支度，並利用網路座標系統上座標點距離的關係，配合貪婪法則(greedy method)建立好友群播樹，達成資料發佈至所有朋友能有較小的網路延遲總和。藉著好友群播樹，使用者只需對合理數量的鄰居以較低的延遲時間轉送訊息，因此具有高擴充性、頻寬及延遲感知的特點。

摘要(英)

The Online Social Network (OSN) is more and more popular recently; it is common that people use it to interact with each other for the purpose of social intercourse. The Client/Server-based OSN architecture brings about the bottleneck of bandwidth and computation limitation, leading to the scalability problem. This paper proposes designing a bandwidth- and latency-aware peer-to-peer friendcast scheme for a peer (i.e., user) in an OSN to simultaneously send instant messages to all of its friends. In this scheme, every user builds a friendcast tree including all friends. A server is responsible for only light-weight tasks, like registering, logining, and storing some information of peers to speed up the tree construction. Peers register to the server and obtain network coordinates on entering the system. Since the data delivery latency between two peers is proportional to the distance of their coordinates, the two peers can estimate the latency between them by the coordinates. We also propose an Available Out-Degree Estimation (AODE) method to estimate the rational out-degree for a tree node in the friendcast tree on the basis of the peer’s available bandwidth. According to the out-degree estimation and network coordinates, we design a greedy algorithm called Degree-Adapted Greedy Tree Algorithm (DATGA) to construct a friendcast tree with consideration of decreasing the message transmission latency. By the friendcast tree, a peer just needs to forward messages to a rational number of peers with short latency. The friendcast scheme is thus scalable and has the bandwidth- and latency-awareness properties.

關鍵字(中)

★ 朋友群播
★ 朋友清單
★ 異質網路環境
★ 網路座標
★ 擴展性
★ 社交網路
★ 同儕式

關鍵字(英)

★ online social network
★ peer-to-peer
★ FriendCast
★ network coordinate
★ heterogeneous
★ friend list

論文目次

中文摘要 .................................................................................................................................... I
Abstract ...................................................................................................................................... II
目錄 ............................................................................................................................... III
表目錄 ....................................................................................................................... IV
圖目錄 ........................................................................................................................ V
一、緒論 ............................................................................................................................ 1
二、相關研究 .................................................................................................................... 6
2-1 同儕式社交網路 .................................................................................................... 6
2-2 網路座標系統 ........................................................................................................ 8
2-3 群播樹繞徑演算法 .............................................................................................. 10
三、頻寬及延遲感知好友群播系統設計 ...................................................................... 15
3-1 系統架構 .............................................................................................................. 15
3-2 好友群播樹建立 .................................................................................................. 15
3-3 系統設計 .............................................................................................................. 19
3-3-1 初始化 ...................................................................................................... 20
3-3-2 登入/登出 ................................................................................................. 21
3-3-3 系統維護 .................................................................................................. 22
3-3-4 資料的發佈 .............................................................................................. 23
3-4 系統正確性 .......................................................................................................... 24
3-4-1 好友狀態正確性 ...................................................................................... 24
3-4-2 檔案資料及狀態正確性 .......................................................................... 24
四、實驗模擬 .................................................................................................................. 26
4-1 環境設定 .............................................................................................................. 26
4-2 群播樹演算法 ...................................................................................................... 28
4-3 模擬度量 .............................................................................................................. 29
4-4 效能評估 .............................................................................................................. 29
五、結論 .......................................................................................................................... 38
參考文獻 ................................................................................................................................. 39

參考文獻

[1] F. Aurenhammer, “Voronoi Diagrams: A Survey of a Fundamental Geometric Data Structure,” ACM Comp. Surveys, vol. 23, no. 3, 1991, pp. 345–405.
[2] M. Albano, R. Baraglia, M. Mordacchini, L. Ricci, “Efficient Broadcast on Area of Interest in Voronoi Overlays,” Computational Science and Engineering (CSE’09), 2009.
[3] S. Buchegger and A. Datta, “A case for P2P infrastructure for social networks– opportunities and challenges,” In WONS 2009, 6th International Conference on Wireless On-demand Network Systems and Services, Snowbird, Utah, USA, February 2009.
[4] A. R. Bharambe, C. Herley, and V. N. Padmanabhan, “Analyzing and Improving a BitTorrent Networks Performance Mechanisms,” In Proceedings of IEEE INFOCOM, Barcelona, Spain, Apr. 2006.
[5] S. Buchegger, D. Schi‥oberg, L. H. Vu, Anwitaman Datta, “PeerSoN: P2P social networking – early experiences and insights,” In Proc. ACM Workshop on Social Network Systems (2009).
[6] M. Castro, P. Druschel, A. Kermarrec, and A. Rowstron, “SCRIBE: A large-scale and decentralized application-level multicast infrastructure,” IEEE Journal on Selected Areas in Communications, 20(8):100–110, 2002.
[7] Y. H. Chu, A. Ganjam, T. E. Ng, S. G. Rao, K. Sripanidkulchai, J. Zhan, and H. Zhang, “Early Experience with an Internet Broadcast System Based on Overlay Multicast,” In Proceedings of USENIX, June-July, 2004.
[8] K. Chen, K. Nahrstedt, “Effective Location-Guided Tree Construction Algorithms for Small Group Multicast in MANET,” INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE.
[9] Y. Chen, Y. Xiong, X. Shi, J. Zhu, B. Deng, X. Li, ”Pharos: Accurate and Decentralized Network Coordinate System,” The Institution of Engineering and Technology 2009, IET
Comm., Vol. 3, Iss. 4, pp. 539–548.
[10] L. Chen, Z.Y. Yang, and Z.Q. Xu, “A degree-delay-constrained genetic algorithm for multicast routing tree,” in: Proceedings of the Fourth International Conference on Computer and Information Technology, 2004, pp. 1033–1038.
[11] Y. Chen, G. Zhao, A. Li, B. Deng, X. Li, ”Myth: An Accurate and Scalable Network Coordinate System under High Node Churn Rate,” Proc. on ICON2007, 15th IEEE International Conference, page(s): 143-148, 19-21 Nov., 2007.
[12] F. Dabek, R. Cox, F. Kaashoek, and R. Morris, “Vivaldi: A Decentralized Network Coordinate System,” Proc. ACM SIGCOMM, August 2004.
[13] Y. K. Dalal and R. Metcalfe, “Reverse path forwarding of broadcast packets,” Communications of the ACM, vol. 21, no. 12, pp. 1040–1048, Dec. 1978.
[14] Y. Feng, Z. Yu, Y. Pan, “Heuristic Genetic Algorithm for Degree Constrained Multicast Routing Problem,” Proceedings of 2004 International Conference on Machine Learning and Cybernetics, Shanghai, China, 2004, pp. 2448–2452.
[15] K. P. Gummadi, S. Saroiu, and S. D. Gribble. King: Estimating latency between arbitrary Internet end hosts. In Proc. of SIGCOMM IMW 2002, pages 5–18, November 2002.
[16] S. Y. Hu, J. F. Chen and T. H. Chen, "VON: A Scalable Peer-to-Peer Network for Virtual Environments," IEEE Network, vol. 20, no. 4, Jul./Aug. 2006, pp.22-31.
[17] http://www.wireshark.org/
[18] B. A. Julstrom, “Codings and Operators in Two Genetic Algorithms for the Leaf-Constrained Minimum Spanning Tree Problem,” International Journal of Applied Mathematics and Computer Science, 14 (3) (2004), 385–396.
[19] L. Ji, and M.S. Corson, “Differential Destination Multicast– A MANET Multicast Routing Protocol for Small Groups,” Proc. of INFOCOM 2001, April 2001, pp.1192-1201.
[20] J. R. Jiang, Y. L. Huang, and S. Y. Hu, “Scalable AOI-Cast for Peer-to-Peer Networked
Virtual Environments,” in Proc. 28th International Conference on Distributed Computing Systems Workshops (ICDCSW) Cooperative Distributed Systems (CDS), Jun. 2008.
[21] P. Jokela, A. Zahemszky, C. Esteve, S. Arianfar, and P. Nikander, “LIPSIN: Line Speed Publish/Subscribe Inter-Networking,” Proceedings of SIGCOMM 2009, Barcelona, Spain, August 2009.
[22] R. S. Kazemzadeh, H. A. Jacobsen, “Reliable and highly available distributed publish/subscribe service,” In SRDS, 2009.
[23] L. Kou, G. Markowsky, and L. Berman, “A Fast Algorithm for Steiner Trees,” Acta Informatica, 15, pp.141–145,1981.
[24] S. Keshav, S. Paul, “Centralized Multicast,” Computer Science Department, Cornell University, USA, Technical Report TR98-1688, 1998.
[25] E. Kranakis, H. Singh, J. Urrutia, “Compass Routing on Geometric Networks,” Proc. of 11th Canadian Conf. on Comp. Geometry, CCCG-99, pages51-54, Vancou-ver Aug. 15-18 (1999).
[26] J. Ledlie, P. Gardner, and M. Seltzer “Network coordinates in the wild,” Proc. NSDI, April 2007.
[27] Y. Mao, L. K. Saul, J. M. Smith, ”IDES: An Internet Distance Estimation Service for Large Networks,” Proc. IEEE J. Selected Areas Commun., Special Issue on Sampling the Internet, Techniques and Applications, 2006, 24, (12), pp.2273–2284.
[28] T. S. E. Ng, H. Zhang, “Predicting Internet Network Distance with Coordinates-based Approaches,” Proc. INFOCOM, June 2002.
[29] M. Pandey, S. M. Ahmed, B. D. Chaudhary, “2T-DHT: A Two Tier DHT for Implementing Publish/Subscribe,” In Proc. Computational Science and Engineering, 2009.
[30] M. Pias, J. Crowcroft, S. Wilbur, T. Harris, and S. Bhatti, “Lighthouses for Scalable
Distributed Location,” Proc. IPTPS, February 2003.
[31] P. Pietzuch, J. Ledlie, M. Mitzenmacher, M. Seltzer, “Network-aware Overlays with Network Coordinates,” Proc. IWDDS, July 2006
[32] P. Paul and S. V. Raghavan, “Survey of Multicast Routing Algorithms and Protocols,” In Proceedings of the Fifteenth International Conference on Computer Communication (ICCC 2002), pages 902.926, 2002.
[33] S. Rhea, B. Godfrey, B. Karp, J. Kubiatowicz, S. Ratnasamy, S. Shenker, I. Stoica, and H. Yu., “OpenDHT: a Public DHT Service and its Uses,” In SIGCOMM’05, August 2005.
[34] G.R. Raidl, B.A. Julstrom, “Greedy Heuristics and an Evolutionary Algorithm for the Bounded-Diameter Minimum Spanning Tree Problem,” Proceedings of the 2003 ACM Symposium on Applied Computing, Melbourne, FL, USA, 2003, pp. 747–752.
[35] D. Schi‥oberg, “A peer-to-peer infrastructure for social networks,” Diplom thesis, TU Berlin, Berlin, Germany, December 17, 2008.
[36] Y. Shavitt and T. Tankel, “Big-bang Simulation for Embedding Network Distances in Euclidean Space,” Proc. IEEE INFOCOM, April 2003.
[37] S. Tarkoma, M. Ain, and K. Visala, “The Publish/Subscribe Internet Routing Paradigm (PSIRP): Designing the Future Internet Architecture”, Towards the Future, pp. 102-111, 2008.
[38] D. N. Tran, F. Chiang, and J. Li, “Friendstore: cooperative online backup using trusted nodes,” In SocialNets’08: 1st Workshop on Social Network Systems, Glasgow, Scotland, April 2008.
[40] S.Y. Tseng, Y.M. Huang, and C.C. Lin, “Genetic algorithm for delay- and degree-constrained multimedia broadcasting on overlay networks,” Computer Communications 29 (17) (2006) 3625–3632.
[41] A. Tawfig, Z. Taieb, “Delay-Constrained, Low-Cost Multicast Routing in Multimedia Networks,” Journal of Parallel and Distributed Computing, 61 (9) (2001) 1307–1336.
[42] Z. Wang, B. Shi, and E. Zhao, “Bandwidth-Delay-Constrained Least-Cost Multicast Routing based on Heuristic Genetic Algorithm,” Computer Communications, 24 (2001) 685–692.
[43] R. Zhang, Y. C. Hu, X. Lin, and S. Fahmy, “A Hierarchical Approach to Internet Distance Prediction,” Proc. IEEE ICDCS, July 2006.
[44] R. Zimmermann and L. Liu, “ACTIVE: Adaptive Low-Latency Peer-to-Peer Streaming,” Proceedings of SPIE, vol.5680, pp. 26-37, 2005.
[45] R. Zhang, C. Tang, Y. C. Hu, S. Fahmy, and X. Lin, “Impact of the Inaccuracy of Distance Prediction Algorithms on Internet Applications– an Analytical and Comparative Study,” Proc. IEEE INFOCOM, May 2006.

指導教授

江振瑞(Jehn-ruey Jiang)

審核日期

2010-7-26

推文