resiliency

Information about resiliency

Published on January 9, 2008

Author: Ulisse

Source: authorstream.com

Content

Slide1:  Shetal Shah, IITB Dissemination of Dynamic Data: Semantics, Algorithms, and Performance More and more of the information we consume is dynamically constructed…:  More and more of the information we consume is dynamically constructed… Buying a camera? Track auctions…:  Buying a camera? Track auctions… Dynamic Data :  Dynamic Data Data gathered by (wireless sensor) networks Sensors that monitor light, humidity, pressure, and heat Network traffic passing via switches Sports Scores Score changes by 5 points Financials Rice price changes by Rs. 10 compared to previous day Total value of stock portfolio exceeds $ 10,000 Continual Queries:  Continual Queries A CQ is a standing query coupled with a trigger/select condition CQ stock_monitor SELECT stock_price FROM quotes ; WHEN stock_price – prev_stock_price > $0.5 CQ RFP_tracker: SELECT project_name, contact_info FROM RFP_DB; WHERE skill_set_required ⋐ available_skills Not every change at a source leads to a change in the result of the query Generic Architecture:  Generic Architecture Data sources Proxies /caches /Data aggreators End-hosts servers sensors wired host mobile host Network Network Where should the queries execute ?:  Where should the queries execute ? At clients can’t optimize across clients, links At source (where changes take place) Advantages Minimum number of refresh messages, high fidelity Main challenge Scalability Multiple sources hard to handle At Data Aggregators -- DAs/proxies -- placed at edge of network Advantages Allows scalability through consolidation, Multiple data sources Main challenge Need mechanisms for maintaining data consistency at DAs Coherency of Dynamic Data:  Coherency of Dynamic Data Strong coherency The client and source always in sync with each other Strong coherency is expensive! Relax strong coherency:  - coherency Time domain: t - coherency The client is never out of sync with the source by more than t time units eg: Traffic data not stale by more than a minute Value domain: v - coherency The difference in the data values at the client and the source bounded by v at all times eg: Only interested in temperature changes larger than 1 degree Coherency Requirement (c ):  Coherency Requirement (c ) temperature, max incoherency = 1 degree Slide10:  T at Server Data/Query Value at client Violation Bounds Source pushes interesting changes:  Source pushes interesting changes + Achieves v - coherency + Keeps network overhead minimum -- poor scalability (has to maintain state and keep connections open) Source DA User push push Pull – interesting changes:  Pull – interesting changes Pull after Time to Live (TTL) Time To Next Refresh (TTR / TNR) + Can be implemented using the HTTP protocol + Stateless and hence is generally scalable with respect to state space and computation Need to estimate when a change of interest will happen Heavy polling for stringent coherence requirement or highly dynamic data Network overheads higher than for Push Server Repository User Pull Complementary Properties:  Complementary Properties Dynamic Content Distribution Networks:  Dynamic Content Distribution Networks To create a scalable content dissemination network (CDN) for streaming/dynamic data. Dissemination Network: Example:  Dissemination Network: Example Data Set: p, q, r Max Clients : 2 A B D C Challenges – I:  Challenges – I Given the data and coherency needs of repositories, how should repositories cooperate to satisfy these needs? How should repositories refresh the data such that coherency requirements of dependents are satisfied? How to make repository network resilient to failures? [VLDB02, VLDB03, IEEE TKDE] Challenges - II:  Challenges - II Given the data and the coherency available at repositories in the network, how to assign clients to repositories? Given the data and coherency needs of clients in the network, what data should reside in each repository and at what coherency? If the client requirements keep changing, how and when should the repositories be reorganized ? [RTSS 2004, VLDB 2005] Dynamics along three axes :  Dynamics along three axes Data is dynamic, i.e., data changes rapidly and unpredictably Data items that a client is interested in also change dynamically Network is dynamic, nodes come and go Slide19:  Data Dissemination Data Dissemination:  Data Dissemination Different users have different coherency req for the same data item. Coherency requirement at a repository should be at least as stringent as that of the dependents. Repositories disseminate only changes of interest. A B D C Client Slide21:  Data dissemination -- must be done with care should prevent missed updates! 1.2 1.5 1 1.4 1.7 1.4 1 1 1 Source Based Dissemination Algorithm:  Source Based Dissemination Algorithm For each data item, source maintains unique coherency requirements of repositories the last update sent for that coherency For every change, source finds the maximum coherency for which it must be disseminated tags the change with that coherency disseminates (changed data, tag) Slide23:  Source Based Dissemination Algorithm 1.2 1.5 1 1.4 1.7 1 1.5 1 1.5 Repository Based Dissemination Algorithm :  Repository Based Dissemination Algorithm A repository P sends changes of interest to the dependent Q if Slide25:  Repository Based Dissemination Algorithm 1.2 1.5 1 1.4 1.7 1.4 1 1 1 1 1.4 Building the content distribution network:  Building the content distribution network Choose parents for repositories such that overall fidelity observed by the repositories is high ---reduce communication and computational delays.. If parents are not chosen judiciously:  If parents are not chosen judiciously It may result in Uneven distribution of load on repositories. Increase in the number of messages in the system. Increase in loss in fidelity! A B D C DiTA:  DiTA Repository N needs data item x If the source has available push connections, or the source is the only node in the dissemination tree for x N is made the child of the source Else repository is inserted in most suitable subtree where N’’s ancestors have more stringent coherency requirements N is closest to the root Most Suitable Subtree?:  Most Suitable Subtree? l: smallest level in the subtree with coherency requirement less stringent than N’’s. d: communication delay from the root of the subtree to N. smallest (l x d ): most suitable subtree. Essentially, minimize communication and computational delays! Slide30:  Example Initially the network consists of the source. Slide31:  Example D requests service of q with coherency requirement 0.2 Slide32:  Example D requests service of q with coherency requirement 0.2 Slide33:  Resiliency Handling Failures in the Network:  Handling Failures in the Network Need to detect permanent/transient failures in the network and to recover from them Resiliency is obtained by adding redundancy Without redundancy, failures  loss in fidelity Adding redundancy can increase cost  possible loss of fidelity! Handle failures such that cost of adding resiliency is low! Passive/Active Failure Handling:  Passive/Active Failure Handling Passive failure detection: Parent sends I’m alive messages at the end of every time interval. what should the time interval be? Active failure handling: Always be prepared for failures. For example: 2 repositories can serve the same data item at the same coherency to a child. This means lots of work  greater loss in fidelity. Middle Path :  Middle Path A backup parent B is found for each data item that the repository needs Let repository R want data item x with coherency c. P R c At what coherency should B serve R ? If a parent fails:  If a parent fails Detection: Child gets two consecutive updates from the backup parent with no updates from the parent B R k x c c Recovery: Backup parent is asked to serve at coherency c till we get an update from the parent Adding Resiliency to DiTA:  Adding Resiliency to DiTA A sibling of P is chosen as the backup parent of R. If P fails, A serves B with coherency c  change is local. If P has no siblings, a sibling of nearest ancestor is chosen. Else the source is made the backup parent. B R k x c c A Markov Analysis for k:  Markov Analysis for k Assumptions Data changes as a random walk along the line The probability of an increase is the same as that of a decrease No assumptions made about the unit of change or time taken for a change Expected # misses for any k <= 2 k2 – 2 for k = 2, expected # misses <= 6 Experimental Methodology:  Experimental Methodology Physical network: 4 servers, 600 routers, 100 repositories Communication delay: 20-30 ms Computation delay: 3-5 ms Real stock traces: 100-1000 Time duration of observations: 10,000 s Tight coherency range: 0.01 to 0.05 loose coherency range: 0.5 to 0.99 Failure and Recovery Modelling:  Failure and Recovery Modelling Failures and recovery modeled based on trends observed in practice Analysis of link failures in an IP backbone by G. Iannaccone et al Internet Measurement Workshop 2002 Recovery:10% > 20 min 40% > 1 min & < 20 min 50% < 1 min Trend for time between failure: In the Presence of Failures, Varying Recovery Times:  In the Presence of Failures, Varying Recovery Times Addition of resiliency does improve fidelity. In the Presence of Failures, Varying Data Items:  In the Presence of Failures, Varying Data Items Increasing Load Fidelity improves with addition of resiliency even for large number of data items. In the Absence of Failures:  In the Absence of Failures Increasing Load Often, fidelity improves with addition of resiliency, even in the absence of failures! Beyond Resiliency:  Beyond Resiliency Scheduling Assigning clients to repositories Balancing load in the network Handling queries Acknowledgements:  Acknowledgements Allister Bernard & Vivek Sharma S. Dharmarajan Shweta Agarwal T. Siva Prof. C. Ravishankar Prof. Sohoni and Prof. Rangaraj Prof. S. Sudarshan Prof. Krithi Ramamritham

Related presentations


Other presentations created by Ulisse

wtoprimitivo
08. 05. 2008
0 views

wtoprimitivo

M Naoi IPES2007
07. 05. 2008
0 views

M Naoi IPES2007

atos maxwell jamescfh
02. 05. 2008
0 views

atos maxwell jamescfh

06ESADE
30. 04. 2008
0 views

06ESADE

1 4 Eiropas Kopienas programmas
22. 04. 2008
0 views

1 4 Eiropas Kopienas programmas

5 11
21. 04. 2008
0 views

5 11

phan
18. 04. 2008
0 views

phan

Brown Velocity
17. 04. 2008
0 views

Brown Velocity

SME in Pakistan
10. 01. 2008
0 views

SME in Pakistan

visual perception 1
14. 01. 2008
0 views

visual perception 1

Ross Thompson Presentation
15. 01. 2008
0 views

Ross Thompson Presentation

ArmorofGod ShieldofFaithNew
17. 01. 2008
0 views

ArmorofGod ShieldofFaithNew

Hospital Employee Immunization 1
17. 01. 2008
0 views

Hospital Employee Immunization 1

EnhancingCoreWeb
10. 01. 2008
0 views

EnhancingCoreWeb

A C 8 US CHAPTER
10. 01. 2008
0 views

A C 8 US CHAPTER

6 SMS
18. 01. 2008
0 views

6 SMS

textiles grad 2006
22. 01. 2008
0 views

textiles grad 2006

SessIIBYeboahEtAl
22. 01. 2008
0 views

SessIIBYeboahEtAl

hfcourse frzn
19. 01. 2008
0 views

hfcourse frzn

Heezen overview of cases
22. 01. 2008
0 views

Heezen overview of cases

2c
23. 01. 2008
0 views

2c

language
14. 01. 2008
0 views

language

10 Cash Control
04. 02. 2008
0 views

10 Cash Control

gsoverview
04. 02. 2008
0 views

gsoverview

Cuisine
22. 01. 2008
0 views

Cuisine

schap011
07. 02. 2008
0 views

schap011

Frontier1
11. 02. 2008
0 views

Frontier1

library orientation
28. 01. 2008
0 views

library orientation

WeddingPlanning
29. 01. 2008
0 views

WeddingPlanning

harpring
21. 01. 2008
0 views

harpring

EnabGrid
07. 02. 2008
0 views

EnabGrid

owen holland
12. 01. 2008
0 views

owen holland

breakout 2ARavishankara
20. 02. 2008
0 views

breakout 2ARavishankara

Michelozzo and Bernardo
10. 01. 2008
0 views

Michelozzo and Bernardo

absent
15. 01. 2008
0 views

absent

p1 calyon de dumast
28. 02. 2008
0 views

p1 calyon de dumast

p548 lecture2v2
03. 03. 2008
0 views

p548 lecture2v2

SB 18 Productive Consultation
08. 03. 2008
0 views

SB 18 Productive Consultation

tortola
20. 01. 2008
0 views

tortola

what
20. 01. 2008
0 views

what

ONEPowerPointPresent ation
19. 03. 2008
0 views

ONEPowerPointPresent ation

hall peter
25. 03. 2008
0 views

hall peter

EID Intro
31. 03. 2008
0 views

EID Intro

cottrell icfa korea may05
03. 04. 2008
0 views

cottrell icfa korea may05

Maps
07. 04. 2008
0 views

Maps

ErgonomicsPresentati on 000
07. 03. 2008
0 views

ErgonomicsPresentati on 000

London2012
14. 04. 2008
0 views

London2012

Samurai Hoedown
07. 02. 2008
0 views

Samurai Hoedown

m2f2
04. 02. 2008
0 views

m2f2

Olympic Mascots
14. 04. 2008
0 views

Olympic Mascots

stdslides2003
12. 03. 2008
0 views

stdslides2003

Packaging ru
14. 01. 2008
0 views

Packaging ru

phpulsefeb
14. 02. 2008
0 views

phpulsefeb

ALADI May2 2005
25. 01. 2008
0 views

ALADI May2 2005

041014 TEAHA
10. 04. 2008
0 views

041014 TEAHA

tds gap
22. 01. 2008
0 views

tds gap

AIDS f06
16. 01. 2008
0 views

AIDS f06

UniversityForumFeb23 2005
16. 01. 2008
0 views

UniversityForumFeb23 2005

Presentation to LGA 23Jan07 V3
24. 01. 2008
0 views

Presentation to LGA 23Jan07 V3

NW web presentation7 03
29. 02. 2008
0 views

NW web presentation7 03

build ssp system
21. 01. 2008
0 views

build ssp system

laighside
29. 01. 2008
0 views

laighside

landis
15. 01. 2008
0 views

landis

Service design for active ageing
21. 11. 2016
0 views

Service design for active ageing