Transcript 投影片
Introduction to Laboratory of DIS, NTUIM Andy Cheng, C. H. Kang, C. T. Fang DIS Lab, Dept. of Information Management, NTU Mar. 14, 2003 Outline • Introduction • Director & Members • Research Topics • • • • • • • Wireless Ad Hoc Network & Topology Formation (2000 ~ 2002) Personal Data Licensing (2000 ~ ) Peer-to-Peer Networks (2000 ~ ) Grid Computing (2002 ~ ) Agent (2002 ~ ) Recommendation (2002 ~ ) Reputation (2002 ~ ) • Publications • Awards & Honors • References 2003/03/14 Introduction to Laboratory of DIS, NTUIM 2 Introduction • Research: • Distributed computing • Visions: • Before 1Q 2006, 20 conference papers accepted by first-class ACM conference/journals. • Before 1Q 2004, a sound training course include distributed systems/algorithms and software engineering for undergraduate students. • Slogans: • “格物致知”, • “跟我們聯誼吧!” • Style & Culture • 老實, 勤奮, 努力, 向上... 你相信了 喔!! 真的嗎?! 2003/03/14 Introduction to Laboratory of DIS, NTUIM 3 Director & Members • Director: Dr. Yuh-Jzer Joung • http://joung.im.ntu.edu.tw/joung/ • Members: • PHD Students: • • • • CSC, Shi-Cho Cha http://mba.ntu.edu.tw/~csc/ Eric, Yu-En Lue http://www.yuenlue.com/ • 2nd Year Graduate Students: • Andy Cheng • C. H. Kang • C. T. Fang 2003/03/14 Introduction to Laboratory of DIS, NTUIM 4 Members (con’d) • 1st Year Graduate Students: •王教昌, 宋華偉, 李柏奇, 林宜均, 林章汶, •林盟凱, 陳彥瀚, 黃翊展, 黃鈞塘, 嚴正. • Current Undergraduate Students: •李金諺, 邱建樺, 陳宇翔, 陳宏典, 陳玠均, •楊伶琪, 詹子儀, 簡伯翰. 2003/03/14 Introduction to Laboratory of DIS, NTUIM 5 Wireless Ad Hoc Network & Topology Formation (2000 ~ 2002) C. J. Hsu Alan Chen S. H. Liu Gary Chung G. D. Haung 2003/03/14 Introduction to Laboratory of DIS, NTUIM 6 Wireless Ad Hoc Network & Topology Formation (2000 ~ 2002) •可任意建置與擴展之隨到即連在地性服務--系 統建構與實作 by S. H. Liu • 藍芽模擬環境的建構 by C. J. Hsu • 網路建構與路由演算法於MANET中效能比較 by Alan Chen • 建立藍芽拓樸之分散式演算法 by G. D. Haung 2003/03/14 Introduction to Laboratory of DIS, NTUIM 7 可任意建置與擴展之隨到即連 在地性服務--系統建構與實作 • 以無線區域網路 (Wireless LAN) 和無線 行動隨建即連網路(Mobile Ad Hoc Network MANET) 為基底 (pic) • 目前所開發的系統程式是用 於個人數位助理 (PDA)之 上 2003/03/14 Introduction to Laboratory of DIS, NTUIM 8 藍芽模擬環境的建構 • BuleHoc不足之功能：裝置行為單一固定、 行動模型支援從缺、模擬結果尚未整合、藍芽 微網(Piconet)數目受限 • 建構在IBM BlueHoc之上，提供一個更有彈 性、更為完善的藍芽模擬平台 • 實際執行相關演算法，證明可以改善原有的缺 點 Ex:模擬結果整合(pic) 2003/03/14 Introduction to Laboratory of DIS, NTUIM 9 網路建構與路由演算法於 MANET中效能比較 • 研究MANET上Hierarchical Routing演算 法或協定的效能 • 在模擬環境下進行實作，根據不同的節點移動 模式針對整體網路的構建與相關路由的效能做 一綜合性的比較 • 結論：沒有演算法是最佳的，所有的演算法都 具備各自的優點及缺點，針對不同的環境，建 議使用不同的路由演算法 2003/03/14 Introduction to Laboratory of DIS, NTUIM 10 建立藍芽拓樸之 分散式演算法 • 藍芽裝置在溝通前，必須先建立點對點的連線， 形成一個藍芽拓譜 (pic) • 發展一個演算法可以快速地建構拓撲、確保拓 撲的連通性、拓撲利於快速地路由 • 使用模擬器驗證演算法能夠正確的運作，並且 擁有上述的優點 2003/03/14 Introduction to Laboratory of DIS, NTUIM 11 Gossip-based Resource Discovery Algorithms • 發現資源問題：在分散式環境中，如何讓每個 節點都能知道其他節點的存在 • 在認識其他節點的過程中，可以保有下面的性 質：距離越近的節點，越容易被認識 • 用ns2模擬器驗證演算法的正確性 2003/03/14 Introduction to Laboratory of DIS, NTUIM 12 Personal Data Lisencing (2000 ~ ) S. C. Cha 2003/03/14 Introduction to Laboratory of DIS, NTUIM 13 Personal Data Licensing (2000 ~ ) • Personal Data Backbone (PDB) is a Universal Profile System (UPS) over P2P network. • A UPS is developed to allow a user to access different information services with only a single action of authentication and authorization. E.g., Microsoft Passport • PDB can tolerate “a certain degree of failures” and to offer accountability of personal data access. 2003/03/14 Introduction to Laboratory of DIS, NTUIM 14 Peer-to-Peer Networks (2000 ~ ) J. W. Lin 2003/03/14 Juicy Wang C. T. Fang C. H. Gang Eriko Lue Andy Lin Introduction to Laboratory of DIS, NTUIM 15 Peer-to-Peer Networks (2000 ~ ) • A P2P network by definition is a fully distributed, non-hierarchical network and each participating node is symmetric. • Topics we are working on: • • • • • • Distributed naming and routing. Surrogate routing. Meta search on P2P networks. P2P file sharing system. CDN over P2P networks. Power computation networks. 2003/03/14 Introduction to Laboratory of DIS, NTUIM 16 Distributed Naming & Routing • The problems is how to name a node/object and to resolve a name of a node/object on a large scale and totally decentralized environment. • There are three usual ways to achieve this: • Centralized indexing, e.g., Napster. • Query flooding, e.g., Gnutella. • Hash and heuristic-based routing, e.g., Chord, CAN, Tapestry, Pastry, P-Grid. • Others, e.g., PlanetP. 2003/03/14 Introduction to Laboratory of DIS, NTUIM 17 Napster’s Approach Napster’s Server Cluster Dr. [email protected] 140.112.107.79 2003/03/14 Introduction to Laboratory of DIS, NTUIM 18 Gnutella’s Approach I am Dr. Evil! I have it! I have it! Who has “Dr. Evil.avi”? 2003/03/14 Introduction to Laboratory of DIS, NTUIM 19 Distributed Hash Table • A hash function maps a node/object onto a NodeID/ObjectID space. • Nodes are organized as a hypercube, or a skip list. • Objects are inserted into a distributed hash table (DHT). • To resolve a name of a node/object, request is routed along a hypercube/skip list path. A 4D hypercube 2003/03/14 Introduction to Laboratory of DIS, NTUIM 20 2003/03/14 Introduction to Laboratory of DIS, NTUIM 21 Hash ( [cyndi]舞澤圓.avi ) = 5581357 IP: 203.23.91.178 5678 AA57 舞澤圓 6610 [cyndi]舞澤圓.avi @ 140.112.107.68 7557 5F88 D357 1357 4567 舞澤圓 3F88 IP: 140.112.107.68 2003/03/14 8310 1234 8887 Introduction to Laboratory of DIS, NTUIM 22 Distributed Naming & Routing (con’d) • Mystry – a Plaxton mesh based scheme designed by Eric, Yu-En Lue. • Terrorists Win – a skip list based topology with dynamic load balancing mechanism – by OB, C. H. Kang. • MagicCube – a hypercube based routing with surrogate selection algorithm – by J. C. (Juicy) Wang, J. W. Lin. 2003/03/14 Introduction to Laboratory of DIS, NTUIM 23 MagicCube 2003/03/14 Introduction to Laboratory of DIS, NTUIM 24 Surrogate Routing • In practical implementation, the number of nodes is often greatly less than the NodeID space. • A deterministic surrogate routing scheme guarantees all nodes choose the same surrogate for a failure/inexistent node. 2003/03/14 Introduction to Laboratory of DIS, NTUIM 25 Keyword Search on DHT-based P2P Network • Google’s service is an example of keyword search, while it is a centralized approach. • Current DHT-based P2P network only support search with exact object name. • Distributed inverted index supports keyword search on DHT-based P2P networks while problem of unbalanced load arises. • We’re now working on the improvement of distributed inverted index and a directed search using Bloom-filter ObjectIDs. 2003/03/14 Introduction to Laboratory of DIS, NTUIM 26 Keyword Search on DHT-based P2P Network (con’d) Java P2P Java Ryoko Azumi P2P Azumi cyndi cyndi Azumi Split based on Keywords 2003/03/14 Azumi cyndi P2P Split based on Documents Introduction to Laboratory of DIS, NTUIM 27 Probabilistic Resource Location • Andy Cheng finds that randomized replication on a P2P network guarantees certain level of hit rate. • His research is currently on how to develop a gossip-based approach achieving randomized replication. • In his thesis, a simulation will help to identify the performance. 2003/03/14 Introduction to Laboratory of DIS, NTUIM 28 P2P File Sharing System • MyP2P file sharing system is built on Mystry base layer. Application Services Application Services Agent Agent Compositor Compositor Agent Dock 4 Personal Data Personal Data Management Agent Management Agent Access Control Personal Privacy Management Personal Identity & Profile Agent Dock 2 Agent Dock 1 System System Services Services Base Base Security Guard Power Power Computing Computing Network Network Agent Agent Resource Allocation Service Replication & Immigration Topology Configuration Instant Instant Messaging Messaging Agent Agent Agent Dock 5 P2P P2P Messaging Messaging & File & File System System Agent Dock 2 Agent/Service Discovery Name Resolution Message Routing Platform Security Logical Identity MyP2P Platform Service Platform Common Service MyP2P Common 2003/03/14 Introduction to Laboratory of DIS, NTUIM 29 CDN over P2P Networks • Content Delivery Network (CDN) delivers digital content to consumers with better scalability, better availability, and more efficient capacity utilization. CNN web server CRASH Users in Europe Akamai CDN Service Users in Asia 2003/03/14 Introduction to Laboratory of DIS, NTUIM BOOM BANG Users in U.S. 30 CDN over P2P Networks (con’d) • Content Sources join the network as MyP2P nodes and the whole network will be servicing as a content delivery network (CDN). • When a file requested is transferred back along the path of request routing, each node along the path will dynamically decide to cache the file or not. • Randomized hierarchical paging intelligently determines where to place replicas. 2003/03/14 Introduction to Laboratory of DIS, NTUIM 31 Power Computation Networks • Many difficult problems e.g., protein folding require enormous computation powers. • We combine agent technology and randomized job assignment to provide computation power of a P2P network. • Problems are implemented by inheriting our PCN APIs. • Mobile Agents which carry problems will travel around MyP2P network to find hosts with redundant computing power. • Jobs carried by MAs will split and be dispatched dynamically. • Randomly picking nodes balances load all over the network. 2003/03/14 Introduction to Laboratory of DIS, NTUIM 32 Randomized Job Assignment 2003/03/14 Introduction to Laboratory of DIS, NTUIM 33 Our MEDIC! System 2003/03/14 Introduction to Laboratory of DIS, NTUIM 34 2003 New Topics 2003/03/14 Introduction to Laboratory of DIS, NTUIM 35 Grid Computing (2002 ~ ) • Grid computing • Large-scale resource sharing • Innovative applications • High-performance orientation • Grid problem • Flexible, secure, coordinated resource sharing among virtual organization • Globus (www.globus.org) • • • • • 2003/03/14 Resource management Data management and access Application development environments Information service security Introduction to Laboratory of DIS, NTUIM 36 Grid Computing (2002 ~ ) • Grid & P2P architectures • Missions on grids involve large proportion of members while tasks on P2P are small and related only to few members • Grids organize resources on different machines into huge computational powers • P2P communities facilitate participants to operate respectively 2003/03/14 Introduction to Laboratory of DIS, NTUIM 37 Agent (2002 ~ ) Design Objectives flexible, autonomous action Environment Agent Encapsulated Computer System 2003/03/14 Introduction to Laboratory of DIS, NTUIM 38 Agent (2002 ~ ) Well-defined boundaries and interfaces problem-solving entities Agent Autonomous Flexible 2003/03/14 Introduction to Laboratory of DIS, NTUIM 39 Collaborative filtering (2002 ~ ) • Collaborative filters help people make choices based on the opinions of other people • GroupLens : a system for collaborative filtering of netnews (cs.umn.edu) • EachMovie : a system that recommends users with (research.compaq.com/SRC/eachmovie/) 2003/03/14 Introduction to Laboratory of DIS, NTUIM 40 Collaborative filtering (2002 ~ ) Centralized models • www.amazon.com • Cons & pros + easy to implement , global view - scale weakly , single point of failure - centralized resource consumption Distributed models ‧ Gnutella ‧ Cons & pros + scalable , fault tolerance - expensive global view ‧ Research topics in distributed environment 2003/03/14 Introduction to Laboratory of DIS, NTUIM 41 Collaborative filtering (2002 ~ ) 2003/03/14 Introduction to Laboratory of DIS, NTUIM 42 Reputation & trust(2002 ~ ) • The reputation of an entity is an expectation of its behavior based on other entities • The trust of an entity A about another entity B is that A believes that B will act as A expects within a specific context at a given time • Applications • eBay ( we have a funny example here • Web service ) • Research • A simulation platform for different reputation models • Reputation models in distributed environments • Problems (such as collusions) 2003/03/14 Introduction to Laboratory of DIS, NTUIM 43 Publications • WWW 2003 (Poster), S. C. Cha and Y. J. Joung, On Derived Data Service in the Cyberspace. • AAS 2003, C. J. Hsu and Y. J. Joung, An NS- based Bluetooth Topology Construction Simulation Environment. • PET 2003, S. C. Cha and Y. J. Joung, From P3P to OPDL. • LawTech 2002, S. C. Cha and Y. J. Joung, Online Personal Data Lisencing. 2003/03/14 Introduction to Laboratory of DIS, NTUIM 44 Awards & Honors • NCHC高速計算獎 • 劉宗原:國科會九十一年度碩士論文獎 • Tic100科技創新比 賽冬令營活動分組 第二名 2003/03/14 Introduction to Laboratory of DIS, NTUIM 45 References • … 2003/03/14 Introduction to Laboratory of DIS, NTUIM 46 ~~Q & A~~ Thank You! We will graduate, yeah, baby, yeah… Ad Hoc network Broadcast with (1) client2’s identity (MAC address) (2) destination LAS’s IP address (3) request message Client1 LAS Client2 Ad hoc mode (a) Client2 requests TCP connection with the request message LAS Reply desired data Client2 Client1 Infrastructure mode (b) Client1 relays the request Ad hoc mode LAS Client1 Client2 Reply desired data back using client2’s identity 2003/03/14 Introduction to Laboratory of DIS, NTUIM Back 48 模擬結果整合 Back 2003/03/14 Introduction to Laboratory of DIS, NTUIM 49 藍芽拓撲 (a) a piconet, (b) a scatternet Back 2003/03/14 Introduction to Laboratory of DIS, NTUIM 50