http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/159 2026-04-17T17:04:57Z 2026-04-17T17:04:57Z Yen-Peng Sung 宋彥朋 http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43767 2021-06-15T02:28:04Z 2009-01-01T00:00:00Z

標題: 點棒可視圖的厚度最佳漸近上界; Asymptotically Optimal Thickness Bounds of Generalized Bar Visibility Graphs 作者: Yen-Peng Sung; 宋彥朋 摘要: Given a set of disjoint horizontal line segments (call bars), d(b1, b2) of two bars b1 and b2 is the minimum number of the other bars that the vertical line segments whose endpoints are at b1 and b2 passing through. A graph G is a bar k-visibility graph if G can be represented as a set of disjoint bars such that any two vertices are adjacent in G if and only if d(u, v) ≤ k, where u and v are the associated bars with those vertices. A graph G is a semi bar k-visibility graph if G can be represented as a set of disjoint bars whose left endpoints have the same x-coordinates such that any two vertices are adjacent in G if and only if d(u, v) ≤ k, where u and v are the associated bars with those vertices. The thickness of G is the minimum number of planar subgraphs whose union is G. Dean et al. gave the best previously known upper bound 3k(6k + 1) on the thickness of bar k-visibility graphs. Hartke et al. proved that the largest complete graph in bar k-visibility graphs is K_4k+4, so the upper bound on the thickness of bar kvisibility graphs is at least ⌈(2k +3)/3⌉. Felsner and Massow gave an upper bound on the thickness of semi bar 1-visibility graphs. Felsner and Massow proved that K_2k+3 is the largest complete graph in semi bar k visibility graphs, so the upper bound on the thickness of semi bar k visibility graphs is at least ⌈(2k + 5)/6⌉. We reduce the upper bound to 3k + 3 on the thickness of bar k-visibility graphs, and give an upper bound 2k for semi bar k-visibility graphs.

2009-01-01T00:00:00Z Chin-Hua Sun 孫錦驊 http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/33582 2021-06-13T04:48:39Z 2006-01-01T00:00:00Z

標題: 點對點網路的多人虛擬世界負載平衡機制; Load-balancing for Peer-to-peer Networked Virtual Environment 作者: Chin-Hua Sun; 孫錦驊 摘要: 點對點網路允許每一台電腦直接連結到其他電腦做溝通。現在最常見的應用是檔案分享。不過，分散式運算才是點對點網路的主要功能。 網路遊戲是現在最流行的趨勢，而目前市面上看得到的多人角色扮演遊戲(MMORPG, Massive Multi-user Online Role Playing Game) 都是採用傳統的主從式架構。這樣的架構有下列幾個壞處：伺服器的建置成本高；伺服器一旦出問題就會導致整個遊戲無法進行；提供遊戲的廠商需提供數個伺服器以容納更多的使用者。但是，連接到不同伺服器的玩家其實並不在相同的環境中。 本論文是針對MMORPG，提出一個點對點的架構，並且加入動態狀態資訊分配 (DSID, Dynamic Status Information Distribution) 來解決上述主從式架構下所產生的問題，以期能做出一個建置成本低並且富有彈性的遊戲架構，同時也允許所有的使用者都能夠在同樣的一個環境中進行互動。; The peer-to-peer network allows each computer to connect to other computers directly. Its most popular application today is file sharing, but distributed computing is the main function of peer-to-peer network. The trend of games is online games. Most MMORPGs (Massive Multi-user Online Role Playing Games) we can see today are based on client-server architecture. This causes some disadvantages as follows: the server is very expensive and the failure of the server fails the whole game. Besides, the vendor of a game need to provide several servers to allow more players playing at the same time, but players connect to different servers are in the different virtual environments. This thesis provides a peer-to-peer architecture with dynamic status information distribution (DSID) mechanism for MMORPG to address the issues occurred in the client-server architecture. We hope to construct a low-cost and flexible architecture that allows all players to interact to each other in the same virtual environment.

2006-01-01T00:00:00Z Ying-Chieh Huang 黃盈傑 http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/23870 2021-06-08T05:11:55Z 2006-01-01T00:00:00Z

標題: 點對點網路檔案分享之可靠聲譽系統的設計與實作; Design and Implementation of a Reliable Reputation System for File Sharing in Peer-to-Peer Networks 作者: Ying-Chieh Huang; 黃盈傑 摘要: 在現今的網路上點對點網路的應用程式扮演了一個重要的角色。很多應用程式經由點對點協定都獲得極大的成功，例如檔案分享、分散式處理和即時通訊。 由於點對點網路的匿名性，在檔案分享的系統裡就有個潛藏的嚴重問題，那就是檔案提供者有可能提供竄改過的檔案，例如：內容和檔名不符的檔案，或者是損壞的檔案，甚至是含有病毒和特洛依木馬的檔案。 目前在點對點檔案分享系統上建立聲譽系統已有許多相關的研究，但對於某些攻擊行為的抵抗力仍然有限。我們在我們的聲譽系統裡加入一個伺服器，以便記錄所有使用者的行為，包含上載、下載、評價以及取得評價等動作。經由我們設計的行為監控程式，來判斷是否有的惡意行為，並進一步處罰惡意的使用者，讓我們的聲譽系統更可靠。; Nowadays, peer-to-peer (P2P) applications have played an important role in the network. Many applications have a great success by using P2P protocol, such as file sharing, distributed processing, and instant messaging, etc. In file-sharing applications, because of the anonymity of P2P, there is a problem that some of file providers may misuse by providing tampered files – wrong files, bad files, even viruses and Trojan Horses. There are already many existing researches on reputation system for P2P file-sharing, but they still limited to the resistance of some attacks. We add a server into our reputation system, in order to record all users’ actions, include uploading, downloading, judging and getting judgment. To make our reputation system more reliable, we have the monitor component that monitors these records to determine whether there is any malicious behavior, and punish the malicious users if some wrong behaviors are detected.

2006-01-01T00:00:00Z Ching-Pang Lin 林靖邦 http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/27153 2021-06-12T17:56:36Z 2008-01-01T00:00:00Z

標題: 點對點網路多媒體串流之服務品質保證; Multimedia QoS Control for P2P Community Streaming 作者: Ching-Pang Lin; 林靖邦 摘要: With the growth of multimedia devices and applications, we have more and more available media data distributed in computers in a house or even a building, so we need an efcient way to access and integrate those data. In this thesis, we propose to use a P2P network architecture for multimedia streaming. In the P2P network, every- one can contribute his own resources such as bandwidth and storage capacity. Thus, we can integrate the multimedia data among a community. However, the resources in a P2P network are time-varying. To guarantee the streaming quality, we design a mechanism, Rate Adaption Bandwidth Allocation, to manage resources among the nodes in the system. Rate Adaption Bandwidth Allocation performs three main func- tions: (1) selecting reliable nodes for incoming multimedia streaming; (2) scheduling the chunk requests to meet timing constraints of video playback; (3) generating the bandwidth allocation for nodes to reserve bandwidths. We implement Rate Adaption Bandwidth Allocation in a real-world P2P system. We evaluate the performance of Rate Adaption Bandwidth Allocation and, and discuss lessons learned from our expe- rience with respect to the practicality and further optimization of our system.

2008-01-01T00:00:00Z