近年來線上社交網路(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.
