Churn handling strategies for structured overlay networks: A survey

2.1 Churn

OPEN IN VIEWER

The churn can be defined as the participation dynamics of autonomic overlay network participants. Each participating node may join or leave the overlay at any time. This continuous join and leave operations in a structured overlay network result in content unavailability and outdated routing tables. Because of this dynamics, the routing topology and content availability need to be maintained in order to guarantee overlay network performance. Autonomic computing principles are an attractive solution to tackle the problem of self organization of dynamic network, mainly due to node heterogeneity and high churn. There are mainly two definitions of churn available in the literature:

Definition (Global Churn): Churn can be defined as a measure of the total number of nodes joining or leaving the overlay network over a given time, also known as node turnover.

Definition (Local Churn): Churn is defined as several online (participating in overlay) and offline sessions in a node’s lifetime (starts with initial creation and ends with permanent departure) as shown in Fig. 1.

Churn is a constant problem often offsetting the advantages of structured overlay networks. The literature on the structured overlay networks addresses churn as a legitimate failure scenario to be handled by the inbuilt fault tolerance or self management capabilities of structured overlay networks. Researchers have conducted different studies [24, 25, 26, 27, 28, 29, 30] to understand the churn behaviour of participating nodes. These studies have reported the daily or weekly periodic uptime pattern in different file sharing applications [24, 25, 27, 28], instant messaging [30] and distributed computing applications [29]. Douceur studies the churn behaviour of Microsoft machines and observed that, some of the participating hosts have always on characteristic, while others have cyclic on/off patterns. This cyclic behaviour pattern of overlay nodes is exploited to propose a predictive stabilization strategy to schedule the stabilization operation appropriately.

Churn can be exploited as a tool to attack, the availability of overlay network by generating peers, joining and leaving the network quickly in order to corrupt the functionality of the overlay network. Churn attack is a peer to peer version of Denial of services (DoS) attacks in which malicious peers frequently join and leave the overlay network to induce a large amount of communication and processing overhead to make it incapable to serve legitimate overlay participants. These efforts of malicious attackers can be categorized into two main categories based on attacker’s capability: Random churn attack and Strategic churn attack.

In random intentional churn attack, an attacker can exploit the churn effect by triggering the fast join/ leave of a number of slave nodes to destabilize the routing infrastructure. This attack is a type of DDoS (Distributed Denial of services) attack on overlay networks and its impact can be amplified by Sybil nodes.

In strategic churn attack, an intelligent adversary can plan a strategic attack against a structured overlay network by continuously attacking its weakest part or pinpointing the attack to specified targets only. Such an attacker learns the topology of the overlay by inserting a crawler and then plans its attack accordingly to partition the overlay network.

Churn attacks are an artificially induced churn with potentially high rates to cause bandwidth consumption due to overlay maintenance. This leads to the worst case to denial of service or service degradation. Cooperative web caching [31] is an attractive application of structured overlay networks to eliminate the use of proxy servers by storing meta-information in the overlay nodes. However, this application is vulnerable to churn attack as an attacker can easily mount a distributed denial of service attack by crippling the sharing mechanism. For this, attackers can pose extreme stress in the form of maintenance overhead generated by a large number of concurrent nodes join/leave procedures, which otherwise considered non-malicious.

2.3 Churn patterns

The recent years have witnessed a lot of research from the overlay networks community to make them more robust in the churn periods. But, most of the researchers have presumed that the overlay nodes will join and leave the overlay networks unpredictably and their churn behaviour has no specific patterns. Thus; most of the research efforts focus on the development of the different ways to recover, maintain connectivity or to ensure availability of services in the face of churn.

However, several studies [25, 32, 33] have shown that the churn behaviour usually obeys a particular pattern and the state of the overlay node can be predicted from their online time history [29]. These works clearly show the recurrence in the online and offline behaviour of overlay nodes. The dynamic behaviour of overlay nodes depends on many factors such as underlying user’s online behaviour, geographical position, time of the day, day of the week etc. as reported in many overlay applications. Based on this observation, overlay nodes will have daily and weekly behaviour patterns based on the working habits of their underlying users. Different users will have different behaviour patterns.

The different overlay network applications will have different online patterns of overlay nodes, depending on their use. The news and communication applications may have their nodes online during the working hours of the region they belong, whereas media streaming applications and social network users may be online during non-working hours, weekends or during their breaks. The main aspect of this observation is that, these patterns are recurrent as users will have the same routine every day, every week or other repeating period. So, we can easily predict the future state of the overlay node based on the past observations. We can exploit these characteristics for efficient maintenance of structured overlay networks by implementing an intelligent prediction framework based on this human factor based workload for setting stabilization parameters appropriately. Researchers [34, 35, 36] have utilized this recurrent behaviour patterns for availability prediction and intelligent replica placement algorithm.

Most of the state of the art structured overlay networks [3, 4, 5, 6, 11] does nothing in order to ensure the connectivity of the overlay nodes ahead of time, rather they only react to the disconnection caused by the churn behaviour of the participant nodes. Some of the researchers [37] have proposed a statically resilient structured overlay network, but at the cost of larger routing table overhead.

Churn is an inherent dynamic characteristic of the overlay networks. Thus; it is a good idea to prepare for it ahead of time. Intelligent prediction of neighbouring node dynamism is helpful to improve the resilience and can reduce the overhead associated with topology maintenance of structured overlay networks. The short-term availability prediction of neighbouring nodes can serve as an important basis for scheduling maintenance operation on a particular structured overlay network node. This review paper proposes the use of a sophisticated predictive stabilization approach to schedule the next stabilization action by assessing the risk of failure of the neighbouring node for some time in the future.

2.4 Need of churn handling

The overlay networks are fundamentally open networks, where nodes may join or leave the overlay network at any time. The joining of a new node have a necessary condition to contact an existing node, whereas existing nodes may leave the overlay network ungracefully (without informing other nodes). This dynamicity raises the need of monitoring and maintenance of network connections to keep the routing table and the overlay structure up to date. The main idea is to enable the self organization of the overlay nodes in an autonomic manner.

Without employing a maintenance mechanism, the routing table entries may get stale and results in performance degradation as new nodes join or existing nodes leave the overlay network. The stabilization mechanism comprises of two parts: failure detection and node replacement. The failure detection mechanism periodically pings the neighbours to discover ungraceful leaves. After the detection of the failed routing table entry, it will be replaced by another appropriate alive node in the network. The method of detection and replacement of the failed node to ensure the structural integrity of the overlay network is known as stabilization mechanism.

A stabilization strategy is required to maintain the structural integrity by keeping the routing table entries (finger tables and successor pointers in case of chord) up to date in case of peer failure. The stabilization algorithm ensures the timely detection of node failures and keeps the routing table full with up-to-date entries. Thus, the stabilization mechanism is defined as the process of maintaining geometric and routing properties of an overlay network experiencing churn.

2.5 Design issues of a churn handling mechanism

The structured overlay networks are self organizing networks capable to handle high node dynamism. This self organization property ensures the legitimate configuration of overlay network in dynamic situation to maintain acceptable performance to its participants. But, to achieve this self organization, practical churn handling techniques are needed, which provide guaranteed overlay services without compromising the openness of overlay networks. Here, we highlight the issues and requirements of practical churn handling mechanism for the structured overlay network. The main issues while designing a practical churn handling mechanism are:

Overlay networks are practically open networks in which any new node can join or leave the network at any time. Thus a practical churn handling mechanism is needed that provide resilient overlay network structure in dynamic scenarios without compromising the openness of the system.

The majority of the internet devices connected to the internet is mobile devices with wireless links. So, most of the overlay network participants are mobile. Thus, an effective churn handling mechanism should be able to handle churn in mobile environment.

The overlay networks are composed of a large number of geographically distributed peers. Heterogeneous internet connectivity patterns and underlying user behaviour results in the variation of node behaviour. Whereas, most of the churn handling mechanisms either be designed by considering the capabilities of the weakest component (negative in mind) or by strongest component (positive in mind).

The overlay network is a set of independent nodes with no central administration. This decentralized nature of peer to peer networks offers many advantages, but it makes the monitoring and resilience to failure a complex task. Thus, while designing a churn handling mechanism; we need to keep in mind this decentralization and lack of global knowledge about the arrival/departure of nodes into account.

Due to the open nature of structured overlay networks, malicious nodes can easily become the part of the legitimate overlay network and can perform various malicious activities such as a DDoS attack, network partitioning and churn attack. Thus, along with the inherent churn feature of participants an effective maintenance strategy should be robust to this malicious behaviour.

2.6 Requirements of a practical churn handling mechanism

The churn handling mechanism requires efficient methods to find and replace stale routing table entries to retain the desired structure of the overlay network. The main requirements of a practical churn handling mechanism are as follows:

A practical and effective churn handling strategy must not induce high maintenance overhead for maintaining the structure of the overlay network. The excessive bandwidth requirements for the maintenance traffic will make the system impractical. Thus, a practical churn handling strategy has to maintain a balance between the maintenance traffic imposed, and desired performance level of the network.

A good churn handling strategy should be able to detect and correct the stale routing table entries timely to ensure the acceptable level of performance in terms of average number of successful query lookups.

Some researchers advocate the fact that an effective maintenance strategy should react to the changes in the environment, e.g. the churn handling strategy should behave according to the varying levels of churn. But, this feature could be exploited by the attackers to perform an attack on the availability of the overlay network by engaging its maximum bandwidth for maintenance action only. So, a good maintenance strategy should maintain a balance between reactivity to changes and performance of a structured overlay network.

The churn handling strategy should be efficient enough to maintain the desired performance level of structured overlay network without constraining their ever evolving nature. That is, a good churn handling strategy should not bind the arbitrary behaviour of overlay network participants.

A good churn handling strategy should be able to differentiate between malicious user induced churn and a legitimate churn. The inability to make this differentiation result in an inefficient maintenance mechanism that itself collapses the whole network.

A practical churn handling strategy should be decentralized that is, it should be able to maintain the structure of overlay network without requiring any centralized stabilization agent.

OPEN IN VIEWER

4.1 Resilience to legitimate node failures

The resilience to node failures approaches will maintain the system performance under the legitimate node dynamics. These approaches can be classified into two main categories based on their underlying strategy to maintain the functional structured overlay network in the face of churn: static resilience and dynamic resilience approaches. The static resilience approach is based on the idea to maintain an acceptable level of performance in the churn scenario. That is, although the system is not fully repaired in churn scenario, but it should be fully functional. Whereas dynamic resilience approaches concentrate on improving the overlay network resilience dynamically by providing flexibility in the selection of certain design parameters such as routing table size and neighbour selection.

Churn is an attractive tool for an adversary to destabilize the structured overlay network [31]. In this attack, a large number of malicious users will join and leave the network frequently in order to increase the bandwidth consumption due to overlay maintenance. The state of the art structured overlay network architectures [4, 5, 9, 50, 51, 52] consider churn as a legitimate node behaviour and provide simple maintenance mechanisms with significant recovery time to handle a set of node failures [44, 48, 53]. Researchers have been aware of this attack for quite a while [18, 54, 55, 56, 57] and various solutions have been presented to thwart this attack [3, 51, 58, 59, 60] but until recently no solution can provably cope with this attack without compromising the openness of the overlay network. Moreover, most of the proposed solutions [58, 59] are static as they can handle only bounded number of node failures. Kuhn et al. [58] have proposed an efficient but a complex architecture to counter an intelligent adversary by continuously shifting newly joined nodes to less sparse areas. In contrast, our proposed technique is simpler and addresses more realistic random intentional churn attack by allowing the new nodes to join as a leaf node and thereby isolating the effect of leave of malicious nodes without affecting the rest of the overlay.

A large number of researchers are currently working on structuring the overlay networks in a hierarchical manner [61, 62, 63, 64, 65, 66, 67, 68, 69, 70] in order to achieve better efficiency, performance, maintenance cost and load balancing. Mariela et al. [69] have evaluated the hierarchical DHTs in the churn scenario of mobile nodes and clearly state the effectiveness of hierarchical DHTs as compared to flat DHTs. However, they have not considered the effect of malicious adversary, who maliciously triggers a large number of join requests for limited lifetime to bring the entire system down.

Table 4 summarizes the comparison of performance of different state of the art flat and hierarchical structured overlay networks in terms of lookup hop count and cost of join and leave in the form of messages sent per join/leave event.

The proactive repair [3, 4, 5] strategies maintain the overlay network structure by running a stabilization routine periodically. Periodic maintenance is employed by using scheduled probing to check the health of neighbouring nodes, even when it is not needed. The main purpose of the periodic stabilization is to incorporate the new nodes and remove the failed nodes from the overlay network. But, this joining and leaving of node may occur at any time and do not have any fixed interval. So, the performance of the periodic stabilization depends on the period (stabilization interval chosen). The choice of stabilization interval further classifies the proactive repair in two categories: Fixed interval and Adaptive Stabilization.

In contrast to proactive repair, the reactive repair strategies [7, 10, 11] are based on the concept of triggered stabilization in view of sporadic churn behaviour of overlay participants. Thus; maintenance routine will be called only after the detection of node failure. The Table 6 provides the comparison of the proactive and reactive repair strategies. The reactive repair strategies involve two phases: failure detection phase and failure recovery phase. In the recovery phase, the missing entry in the routing table of the peer is replaced by sending a contact request to a new peer. The reactive repair strategies can be classified into two categories based on the execution time of recovery phase: Eager and Lazy maintenance. The eager techniques execute the recovery action as soon as a change is detected. Whereas, the lazy repair strategies delay the implementation of recovery action either up to the failure to deliver a data packet or until all the routing table entries of a node become stale. In this sub-section, we will discuss different reactive maintenance strategies in detail.

5.3 Proactive vs. reactive repair

A good maintenance strategy should be adaptable to the varying levels of churn with minimum overhead. Performing periodic maintenance, when it is not needed leads to increased overhead and reactive maintenance occurs only after causing routing inconsistencies. Although, reactive maintenance has minimum overhead and triggered immediately after the detection of the failure, but this reactive maintenance strategy can bring down the network instead of repairing it by congesting the network with maintenance traffic or can easily be exploited by a malicious attacker.

The main driving factor behind the implementation of the predictive stabilization is to provide affordable, preventive maintenance for the structured overlay networks. For predictive maintenance, researchers [75, 76] have proposed two main data driven approaches for prediction: Hidden Markov Model (HMM) and Neuro-Fuzzy, and compare their performance to forecast the failure of neighbouring nodes in order to schedule the next stabilization routine. The HMM is a statistical model, which finds the relationship between different variables to predict the failure of nodes. Whereas, Neuro-Fuzzy is an artificial intelligence based models that learns from the data instead of using explicitly programmed instructions.

The Table 6 concludes that, both periodic and reactive maintenance approaches have drawbacks that make them unsuitable in certain situations. Performing periodic maintenance, when it is not needed leads to increased overhead and reactive maintenance occurs only after causing routing inconsistencies. Thus, recently researchers have [75, 76] have proposed a new class of maintenance mechanism: Predictive Maintenance. The predictive maintenance strategy comes into play after predicting the failure of neighbouring nodes and before causing any routing inconsistency unlike reactive stabilization. The ability to predict or estimate the node failure enables to perform preventive maintenance on abnormal nodes instead of all nodes and results in affordable system operation by providing triggered maintenance.