Science & Technology

2 pages
6 views

Distributed Selfish Replication under Node Churn

of 2
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Distributed Selfish Replication under Node Churn
Transcript
  Distributed Selfish Replication under Node Churn Eva Jaho, Ina Jaho and Ioannis StavrakakisDepartment of Informatics and TelecommunicationsNational & Kapodistrian University of Athens, GreeceE-mail:  { grad0836@di.uoa.gr } ,  { grad0839@di.uoa.gr } ,  { ioannis@di.uoa.gr }  Abstract —In this paper the impact of node churn on the effec-tiveness of a distributed selfish replication group is investigated.In such a group, nodes cooperate in deciding which objects tostore, so that the cost of providing content to their clientele bedecreased, compared to that induce when operating in isolation.In order for a cooperation scheme to be sustainable, nodesshould not be mistreated; i.e., their performance should never belower than that in isolation. In this paper it is shown that nodechurn can introduce mistreatment to otherwise mistreatment-free cooperation schemes. Finally, by properly modifying apreviously described scheme that looses its mistreatment-freeproperty under node churn, a scheme is developed that maintainsthe mistreatment-free property in a distributed selfish replicationgroup in the presence of node churn. I. I NTRODUCTION We consider a group of nodes that collectively replicatecontent as shown in Figure 1. A network node caches orreplicates content in its storage in order to provide it tolocal or remote nodes effectively and economically. Network nodes can decide on their own on the content they will storeor they can cooperate with other nodes that are in closedistance, form a group, and collectively decide which contentto store. A user’s request is first received by the local node.If the requested object is stored locally, it is returned tothe requesting user immediately, thereby incurring a minimalaccess cost. Otherwise, the requested object is searched for,and fetched from other nodes of the group, at a potentiallyslightly (due to the proximity) higher access cost. If the objectcan not be located anywhere in the group, it is retrieved froman srcin server, which is assumed to be outside the group,thus incurring a maximal access cost [2].A key design issue in this distributed replication group is toensure that the object replication strategy employed does notmistreat any of the participating nodes. If a node is mistreated(i.e., the average access cost for objects requested by itsclientele (users having this node as the first place to look forcontent) is higher than the cost incurred if it were not part of the group), then the node will leave the group. In Laoutariset al. [1] a mistreatment-free policy (referred to as TSLS) hasbeen devised based on a game-theoretic formulation. A key This work has been supported in part by the following projects fundedby the IST FET Program of the European Commission: CASCADAS(Component-ware for Autonomic Situation-aware Communications, andDynamically Adaptable Services) under contract FP6-027807, BIONETS(BIOlogically-inspired autonomic NETworks and Services) under contractFP6-027748, and NoE CONTENT (IST-384239).Fig. 1. A distributed replication group assumption in developing the TSLS policy has been that nodesare always available and that there is no node churn in thegroup.In the present work we first calculate the access cost underthe TSLS policy and then under the greedy local (GL) policy(i.e. when each node decides on the content to store in isolationand not as part of a group) and we verify that TSLS cannever induce an access cost higher than the GL policy. Inthe sequel, we assume that each of the cooperating nodesis not always available but node churn occurs with someprobability. The resulting costs are derived and it is shown thatthe TSLS policy looses its mistreatment-free property. Finally,the original TSLS strategy is modified and a new strategyis developed that is shown to maintain the mistreatment-freeproperty in the presence of node churn.II. D ISTRIBUTED  S ELFISH  R EPLICATION UNDER  N ODE C ERTAINTY When a user requests an object, its local node returns it, if the object is stored locally incurring a cost  t l . Otherwise, if the object is not stored locally, then the object is searched inthe storage of the other nodes of the group and is returned if at least one of them has it incurring a cost  t r . Finally, if theobject is not found in any of the nodes of the group or in thelocal node, then the object is received from the srcin serverwith a cost  t s , where  t l  ≤  t r  ≤  t s . The total cost  C  j ( P  ) of a node  v j  for accessing all the objects (under the globalplacement referred to as  P  ), is given by:  C  j ( P  ) =  o i ∈ P  j r ij  · t l  +  o i / ∈ P  j ,o i ∈ P  − j r ij  · t r  +  o i / ∈ P  r ij  · t s  , where  r ij  denotes the rate at which node  v j  requests object o i ,  P  j  is the placement of node  v j , which is the set of objectsreplicated at this node and  P  − j  is the set of objects collectivelyheld by nodes in the group other than  v j .As shown in [1], TSLS achieves a pure Nash equilib-rium [4], and the resulting local utility of each node is at leastas good as that under a GL placement strategy and possiblybetter ( C  TSLS j  ( P  ) ≤ C  GLj  ( P  ‘) ).These conclusions hold good for distributed systems whereparticipating nodes are always available (ON). Very frequentlythough node churn is present, due to the autonomicity of thenodes or simply temporary unavailability of various reasons(resource constraints or faults), which can increase costs ordecrease service quality [3]. The first question asked here isthe following:  Would TSLS under the cooperative replicatingof objects still be more effective than GL and mistreatment be still avoided  ? The answer is no, as shown in the nextsection, where in addition a modified strategy is introducedthat maintains the mistreatment-free property under nodechurn.III. D ISTRIBUTED  S ELFISH  R EPLICATION UNDER  N ODE U NCERTAINTY When a user requests an object, its local node returns it atthe (low) cost  t l  as long as the object is stored locally and thenode is ON (with a probability  π ). Otherwise, if the objectcannot be provided by the local node (i.e., if the object isnot stored locally, or if it is but the node that has it is OFF),then the object is searched in the storage of other nodes of the group and is returned if at least one of them has it andis ON, at the (higher) cost  t r . Finally, if the object cannot beprovided by the local node or any of the nodes of the groupthen the object is received from the server with a maximalcost  t s . In this case, the average total cost  C  j ( P  )  of a node v j  for accessing all the objects, is given by: C  j ( P  ) =  o i ∈ P  j r ij  · t l · π j  +  o i / ∈ P  r ij  · t s +  o i / ∈ P  j ,o i ∈ P  k  r ij  · t r · [1 − n  k =1 ,k  = j,k : oi ∈ P k (1 − π k )]  +  o i ∈ P  j ,o i ∈ P  k  r ij  · t r · (1 − π j ) · [1 − n  k =1 ,k  = j,k : oi ∈ P k (1 − π k )]  +  o i ∈ P   r ij  · t s · n  k =1 ,k : o i ∈ P  k (1 − π k )   . Under node uncertainty, we develop a modified TSLSstrategy (referred to as a mistreatment-free object placement(MfOP) strategy) that is shown to be mistreatment-free undernode churn (see upcoming report in [5]).The original TSLS policy requires each node to knowonly its local demand pattern and the objects selected forreplication by remote nodes, whereas the MfOP policy requiresadditionally that each node knows its probability and theprobabilities of the other remote nodes to be available. 0,05,010,015,020,025,030,035,040,045,050,00,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 π  j       C      j      (      P      ) GL access costMFOP access costTSLS access cost Fig. 2. Access cost under MfOP, TSLS and GL IV. R ESULTS This work has analytically evaluated the access cost underboth cases: when nodes are always available and when theyare available with some probability  π . The results shown inFigure 2 illustrate the loss of the mistreatment-free property byTSLS under node churn and the preservation of this propertyby the proposed MfOP policy. Notice that the average totalcost under the GL policy is always higher than that the MfOPpolicy, while it can be lower than that under the TSLS policyunder high node churn rates.R EFERENCES[1] Nikolaos Laoutaris, Orestis Telelis, Vassilios Zissimopoulos and IoannisStavrakakis, ”Distributed Selfish Replication”.[2] Avraham Leff, Joel L. Wolf, and Philip S. Yu, ”Replication algorithmsin a remote caching architecture,” IEEE Transactions on Parallel andDistributed Systems, vol. 4, no. 11, pp. 1185-1204, Nov.1993.[3] Philip Brighten Godfrey, Scott Shenker, and Ion Stoica, ”MinimizingChurn in Distributed Systems”. March 17, 2006.[4] Martin J. Osborne and Ariel Rubinstein, A Course in Game Theory, MITPress, 1994.[5] http://cgi.di.uoa.gr/ istavrak/publications.html.
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x