Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Slide 74Slide 75Slide 76Slide 77Slide 78Slide 79Slide 80Slide 81Slide 82Slide 83Slide 84Slide 85Slide 86Understanding AvailabilityRanjita Bhagwan, Stefan Savage and Geoffrey M. VoelkerIPTPS 2003Presented by: Ramsés MoralesChurn in widely deployed P2P systems●Hosts at any time can●Join●Leave●Fail●Re-join●Leaving/failing can be●Temporal●PermanentChurn in widely deployed P2P systems●Traditional distributed systems●No churn●Designed to hide failures of core components●Designed for fast recovery of failed core components●P2P systems●Hosts are symmetric – no core system components●Availability can be intermittentAvailability in P2P●Measurement and modeling is required●Systems design depends on it, e.g.,●optimal P2P algorithms●file-sharing systems●distributed file systemsOvernet●Built with Kademlia (DHT)●Client IDs●Randomly generated●Same ID through all sessionsOvernet's advantages●It is widely-deployed●ID instead of IP address●No DHCP issues●No NAT issuesMeasurement Infrastructure●Crawler●Finds member hosts●Prober●Tracks individual hostsCrawler●Exploits Kademlia's routing●Search for 50 random IDs●New nodes will be discovered (closer to the IDs)–Use those nodes to search the IDs●continue recursion...●Runs every 4 hoursProber●Runs every 20 minutes●Good enough to capture all sessions?●Lookup random subset of hosts●(The subset is the same each time)●Experimental flaw. Why?Experiment●Crawler ran for 15 days●First day crawl: 84,000 IDs●2,400 chosen at random for probing●Prober ran for 7 days●Enough to characterize?●Only 1,468 hosts answered probes●Shows the disadvantage of tracking a subset●AVAILABILITY = probes_answered / probes_sentAliasing effects●5,867 unique IPs●from 1,468 unique hosts●ID:IP == 1:4●Due to●DHCP●NAT●Multiple clients in a single host●32% hosts used > 5 IPsAliasing effectsAliasing gets worst with time.Aliasing effectsAvailability looks lower due to aliasing(Design implications of thisunderestimation?)Host availabilityAvailability aloneis not enoughTime-of-day effects●Diurnal pattern●6.4 join and leave per host per day●decay of 32 host per day●what about the rest of Overnet?Host availability interdependence80% fall in [-0.2, 0.2](hosts areindependent)Arrivals and departures●15 day crawl●85,000 hosts active per day●20% arrivals per day●20% departures per dayConclusion●IP aliasing is significant●Availability is combination of two, time-varying, distributions●short-term joins and leaves●long-term arrivals and departures●Considerable turnoverSome more discussion●Other availability-related metrics●session length●inter-arrival time●host downtime●host uptime distribution●What about measuring data availability?●AVMONAVMON: Consistent and Scalable Availability Monitoring OverlayRamsés Morales and Indranil GuptaDept. of Computer ScienceUniversity of Illinois at Urbana-Champaign21Motivation●Large scale distributed applications must deal with churn.●Difficult to predict availability variations across nodes and time cause churn.●Availability: fraction of time a node is online.22Motivation (cont.)av(a) = 0.45av(b) = 0.95av(c) = 0.99xxaaccbbgossip multicast m:✗ f ( availability(a) )✔ f ( availability(b) )✔ f ( availability(c) )<m><m>●Multicast reception reliability availability [Pongthawornkamol 2006]<m>23Motivation (cont.)AvailabilitypredictionAv. basedreplicationAvailability MonitoringAvailability MonitoringAvailabilityprediction...Generic availabilitymonitoring (overlay)problemhas not beenaddressed.(Long-term availability(Long-term availabilityfor each host)for each host)●[Bhagwan 2004][Chun 2006][Godfrey 2006][Mickens 2006][Pongthawornkamol 2006][Schwarz 2004]...Av. basedreplicationAvailability MonitoringAvailabilityprediction...Av. basedreplicationAvailability MonitoringAvailabilityprediction...Av. basedreplication24Motivation (cont.)Generic availabilitymonitoring (overlay)problemhas not beenaddressed.SelfishMy availabilityis 1.025Motivation (cont.)Generic availabilitymonitoring (overlay)problemhas not beenaddressed.My availabilityis 1.0Its availabilityis 1.0SelfishColluding26Availability Monitoring ProblemI. Availability Monitoring Overlay [our focus]II. Availability History Maintenance●[Bhagwan 2004][Mickens 2006]27Availability Monitoring Overlay Problem●For each node xx, select and discover a small subset of nodes to monitor xx.xx28Availability Monitoring Overlay Problem●For each node xx, select and discover a small subset of nodes to monitor xx....( ( mmii monitorsmonitors x x ))PS(x)PS(x)xxmm11mmkkx's Pinging Set29Availability Monitoring Overlay Problem●For each node xx, select and discover a small subset of nodes to monitor xx....( ( mmii monitorsmonitors x x ))PS(x)PS(x)...( ( xx monitorsmonitors tti i ))TS(x)TS(x)xxtt11ttk'k'mm11mmkkx's Pinging Setx's Target SetPS = TS-130OutlineMotivationAvailability Monitoring ProblemSystem ModelDesign GoalsAVMON SystemExperimental Results31System ModelMy availabilityis 1.0Its availabilityis 1.0SelfishColluding32System Model (cont.)JoinsLeavesCrashes33System Model (cont.)●Stable system size, NN. ●The number of online nodes in the system varies within a constant factor of NN.–Valid for:● P2P systems [Bhagwan 2003]●PlanetLab based overlays●Grid systems34OutlineMotivationAvailability Monitoring ProblemSystem ModelDesign GoalsAVMON SystemExperimental Results35Design Goal: ConsistencyPS(x)PS(x)xxaayyx's Pinging Setmm●y y PS(x) PS(x), must be consistent, i.e.,●won't change regardless of system changes.●Consistency, ________, ________, ________, ________, ________.Consistency, ________, ________, ________, ________, ________.36Design Goal: Consistency (cont.)PS(x)PS(x)xxaayyx's Pinging Setmm●y y PS(x) PS(x) must be consistent.●Useful for●long term
View Full Document
Unlocking...