Special Topics CS 8803
Popular in Course
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 8803 at Georgia Institute of Technology - Main Campus taught by Ling Liu in Fall. Since its upload, it has received 12 views. For similar materials see /class/234076/cs-8803-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.
Reviews for Special Topics
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 11/02/15
PeerCQ A Decentralized and Self O O O configuring P2P Information Monitoring System Bugra Gedik Ling Liu CoC GaTech 2002 Georgia aas mu xe TechLuo ogy OOO Talk Outline I Information Monitoring I PeerCQ Overview I Service Partitioning I Fault Tolerance I Cost Analysis I Experimental Results I Conclusion amp Future Work O O 0 Information Monitoring Why I Everyone today can publish information on the web independently and at any time I Information sources are constantly and rapidly changing I Information sources are heterogeneous and autonomous noncooperating I There is a higher latency between change notification and source changes I Needs techniques for efficient execution of longrunning distributed queries and long standing distributed triggers wTechmg ccgy Georgia ms mu e Continual Queries and Information Monitoring I Continual Queries CQs are primitives used to express information monitoring requests I CQs are standing queries that monitor information updates and return results whenever the updates reach certain speci ed thresholds I There are three main components of a CO query trigger and stop condition Continual Query Q Trigger STOP Weather Q Altemative transport routes Infomlation 39 Trigger heavy Wind or rain STOP three months Monitor the weather in the region of port of Smannah and Atlanta Find all alternate transport routes when the weather Condition is bad hem2 wind or hem2 rain Continu al Query Centralized Information Monitoring COO OpenCQ WebCQ NiagaraCQ I Scaling requires both 0 Powerful servers or clusters 0 I ncreased network bandwidth Single point of failure P2P Alternative processing bottleneck network bottleneck Centralized Serve P2P Approach to Information Monitoring 555525 I P2P Information Monitoring 0 No central point of failure 0 Resources grow with 4 clients Network bandwidth Processing power I No administrative management cost O O O PeerCQ An Overview I The rst decentralized Internet scale P2P continual query system for monitoring information change on the web I PeerCQ o accepts CQs from peers o distributes CQs to appropriate peers o executes CQs at peers O 0 9 A Walkthrough Scenario PeerCQ serventepplicetinn an PeerA Noti cation a ager direct noti cation em all noti cation Internet P2P Protocol co Migration Natl cation Module Manager Manager cQ Replication co Processing Module Manager including co enuine an result cechE a Georgia ms e wTechmg ocgy O O 0 Challenges in PeerCQ I Assignment of CQs to Peers Service Partitioning o Balancing peer loads Peer heterogeneity o Utilizing system resources CQ grouping CQs interested in monitoring same data items can be grouped to decrease overall resource consumption including network bandwidth and repeated computation CQpeer coupling peer loads network proximity of peers to data sources I Providing a reliable system on top of a highly unreliable network of peers I Maintaining decentralization O O 0 Service Partitioning I Service partitioning Distribution of CQs to peers in a way that balances the load and improves system resource utilization Important features of PeerCQ service partitioning o Peerawareness o CQawareness 0 Efficient service lookup Geo ia wTregchmg Service lookup and service partitioning OOO Design choice DHT based Chordlike vs flooding based Gnutellalike o Flooding costly no restriction on where a CO can be executed locating the peer that will execute a CO is costly o DHT based efficient guaranteed lookup restricts where a CO can be executed suitable for replication amp fault tolerance PeerCQ service partitioning extends a Pastrylike DHT based P2P approach The assignments of CQs to peers are based on a matching algorithm defined between CQs and peers derived from a relationship between CQ identifiers and peer identifiers OO 0 Mapping Peers to Identifiers Map each peer to a set of unique mbit identifiers which forms that peer s identifier set I This mapping has to be as uniform as possible I The peers that donate more resources are assigned more peer identifiers virtual peer identifiers O Identifiers of Pa O Identifiers of Pb Geo ia wTregchmg How to define the number of Virtual Identifiers Define a measure called Effective Donation ED and calculate its value for each peer based on 0 amount of resources it wants to donate to the system and o the average amount oftime it stays in the network per session Donated resources are used to calculate the ED value ED is used to calculate the number of peer identifiers ED value is used to differentiate heterogeneous peers however it does not ensure that the system will not consume more than the donated resources O O 0 Mapping 005 to Identifiers I Each CO is assigned to an mbit identifier which is composed of two parts 0 the first part is same for CQs interested in monitoring the sama data item 0 the remaining part is uniquely random I The length of the first part is 3 also called the grouping factor I The identifier space is divided into 25 contiguous regions Based on its trigger a CO is mapped to an identifier in one of these regions Triggers defined on the same data item ldentlfler space O O 0 Matching 005 to Peers Strict Matching Phase 0 A CO is matched to a peer such that the peer has the peer identifier which is the closest one to the CO identifier This is a DHT lookup o The peer is called the CO owner I Relaxed Matching Phase 0 The CO owner carries out a search among peers having identifiers in its identifier neighborhood to nd a better qualified peer to execute the CO using three measures cache af nity factor peer load factor data source distance factor 0 The peer is called the CO executor Formulating the Relaxed Matching O O O Fu n ction Cache affinity factor CAFltvaq 1 cqmon7ifieme prache 0 o termse Peer load factor l d gt h MAX LOAD EL Strict matching PLFp 17 Flow p 0a res 7 W LOAD otherWiSB Source distance factor 1 SDF c p q pingitimecqmon7vrcpIP Relaxed matching function RMFpcq PLFp CAFpcqOzSDFpcq TecIm G Georgiana Formulating the Relaxed Matching Function Cache affinity factor 000 1 cqmon itemepcache CAMPch 0 otherwise re axed mg Peer load factor E Strict matching PLFp 17 glam p load g fresh T MAXiLOAD 5 W7 LOAD harms Source distance factor SDF C p q pingitimecqmon7vrcpIP Relaxed matching function RMFpcq PLFp CAFpcqOzSDFpcq O O 0 Service Lookup Details I Use Plaxton Routing and a Chordlike ring Logarithmic time in hops to insert and update CQs Each node maintains routing tables and neighbor lists one for each identifier they possess O O 0 Node Dynamics Node additions and deletions 0 Routing layer issues Routing table and neighbor list are correctly maintained 0 Service partitioning issues The strict matching and the relaxed matching are preserved for every CQ CQ owners and executors are changed properly to maintain the two matchings details in the paper O O 0 Fault Tolerance I Use replication for fault tolerance I Dynamic Passive replication 0 Backups Replica holders peers in the neighbor list of CO owner 0 Primary CQ executor determined based on relaxed matching Ropllmlinntisllqu stnchnarclwlcqlpl relaxed marrhkqlalptp venllme m O O 0 Cost Model Measures of interest 0 Load on a peers due to CO executions 0 Balance in loads of eers 0 Network load due to CO executions Notations P denote the network consisting of N peers G 91 is the set of groups that peer p has sizeGp n is the number of CO groups that peer has 9 represents a group in p which can be identi ed by its trigger identi er sizeg is the number of CQs group gy contains costg is the cost of processing all CQs in group gy thostg is the cost of executing group g s trigger ngostsizeg is the cost of grouping for group g costGp is the cost of processing all CQs in a peer balance denotes the load balance of the peers netCostp ds is a function that assigns costs to peer data source pairs based on the ping time between the peer and the data source avgNetCost denotes the average network cost O O 0 Cost Model cont loadp ostGp EDp was mm costGp Z costgl Z Costsizegl 11 21 5 may costGp sz39zeGp monCost Z gCostsizegl 11 balance VARload p E load p SIZE G ZFEPZIJ P netCostp gI monisrc avgNetCost N O O 0 Effect of Grouping cont tumva Setting the grouping factor a to higher values will decrease the number of CO groups processed by a peer while Optimized relaxed matching provides better grouping Peers 10000 5 data Srcs 5000 items 0 m Simulation Based o O 0 Experimental Results m quottritium quot mum xlu n quotaw w Effect ol mowing arm of grouping mm Hominich frcmmncy sri 9 t hmm v 39 5 c 7 u a no 9mm w pnrr a 0150 mm pm My Setting the grouping factor a to higher values will ecrease the number of CO groups processed by a peer while but may 39 quot 39 quotquot information monitoring requests Peers 10000 COs 1000000 data srcs 5000 items 0 Georg 1 TechLm m 128m O O 0 System Utilization R2n am my aim quotelm39k CD QDltlml1Dd Relaxm Milth mean load quotmark cost mun rm lumpan 1mm gmupmg factor Increasing the grouping factor helps in 39 quot luau 39 quot quot L 39 by enabling more group processing decreasingthe average network cost since the cost of fetching data items of interest from remote data sources is incurred only once per CQ group Optimized relaxed matching provides better utilization Peers 10000 s 1000000 0 data srcs 500 items 0 m 128rblt O O 0 Load Balance m mm laid an halal 4 s a muv l incth For moderate values ofthe grouping factor a the optimized relaxed matching provides betterload balance since it explicitly considers peer loads in its value 39 For high values ofthe grouping factor a the optimized relaxed matching provides worse load balance due to excessive grouping Higher values ofthe grouping factor a are better for favoring overall system utilization whereas lower values are better for favoring load balance peem 10000 it COS it data Bros 5000 it items 1 O O 0 Conclusions Information monitoring is an interesting and suitable application domain for applying P2P technology Mechanisms used for identi er mapping strict matching by considering resource and runtime factors when assigning CQs to peers relaxed matching is an effective way to provide reasonable system resource utilization and peer load balance PeerCQ home httpdislccgatecheduPeerCQ
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'