Socially aware microcloud service overlay optimization in community networks

Received: 00 Month 0000 Revised: 00 Month 0000 Accepted: 00 Month 0000 DOI: xxx/xxxx PAPER SUBMISSION Socially Aware Micro-Cloud Service Overlay Optimization in Community Networks Nuno Apolónia1,2,3 | Felix Freitag1,3 | Leandro Navarro1,3 | Sarunas Girdzijauskas2,4 1Universitat Politècnica de Catalunya. Barcelona, Spain 2KTH Royal Institute of Technology. Stockholm, Sweden 3[apolonia,felix,leandro]@ac.upc.edu 4sar[email protected] Correspondence *Nuno Apolónia, Edifici C6-E208 C.Jordi Girona, 1-3 08034 Barcelona, Spain. Email: [email protected] Summary Community networks are a growing network cooperation effort by citizens to build and maintain Internet infrastructure in regions that are not available. Adding that, to bring cloud services to community networks (CNs), micro-clouds were started as an edge cloud computing model where members cooperate using resources. Therefore, enhancing routing for services in CNs is an attractive paradigm that benefits the infrastructure. The problem is the growing consumption of resources for disseminating messages in the CN environment. This is because the services that build their overlay networks are oblivious to the underlying workload patterns that arise from social cooperation in CNs. In this paper, we propose SELECTinCN (Select in Community Networks), which enhances the overlay creation for pub/sub systems over peer-to-peer (P2P) networks. SELECTinCN includes social information based on cooperation within CNs by exploiting the social aspects of the community of practice (CoP). Our work organizes the peers in a ring topology and provides an adaptive P2P connection establishment algorithm, where each peer identifies the number of connections needed based on the social structure and user availability. This allows us to propagate messages using a reduced number of hops, thus providing an efficient heuristic to an NP-hard problem that maps the workload graph to the structured P2P overlays resulting in a number of messages close to the theoretical minimum. Experiments show that, by using social network information, SELECT- inCN reduces the number of relay nodes by up to 89% using the CoP information versus the state-of-the-art pub/sub notification systems given as baseline. KEYWORDS: Community networks, P2P overlay networks, Community of Practice, Social Networks, Micro-Clouds 1 INTRODUCTION Community networks (CNs) are a growing infrastructure for users to access the Internet and micro-cloud services. The CNs were created to fill a void where Internet providers considered areas too remote and not sufficiently profitable. Users in such areas have gathered together in social collaborations to provide free and open Internet to all members in such locations. Furthermore, CNs can be viewed as a community of practice (CoP), where users collaborate to fulfill common goals. In large networks with more than 35,000 nodes, such as Guifi.net1, collaboration is done mostly within areas or groups of people instead of the entire 1http://guifi.net This is the peer reviewed version of the following article: Silvestre, N. [et al.]. Socially aware microcloud service overlay optimization in community networks. "Software. Practice and experience", 11 Setembre 2019, p. 1-14, which has been published in final form at https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.2750. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Self-Archiving. 2Nuno Apolónia ET AL network. In addition, these networks present challenges to the members. Members contribute toward collaborative goals, such as adding new devices (antennas and routers) to increase network capacity or adding new services to the network (Internet proxies, FTPs, cameras, and videos). 2 A CoP is a common group of people who gather and complete tasks to achieve a common goal1. Collaboration is a key step in developing ideas or infrastructures that support their goals. In this respect, CNs are viewed as CoP applications when it comes to setting up network devices, augmenting network abilities, or even supporting new cloud services at micro-cloud levels. The CoP can also provide social interaction between members of the network, which can help optimize the network routing and infrastructure built by the members. Edge cloud computing is an emerging environment in which services are deployed at the edges of the network by taking advantage of edge devices to perform computational tasks without the need to go to the Internet or data centers. Therefore, edge cloud computing is an attempt to minimize the effect of long-distance communication. Edge cloud computing does not aim to replace traditional clouds but to complement them, where immediate and common computing is done at the edge while the most intensive work is still done in the traditional cloud. The idea of edge cloud computing is to introduce micro-clouds into CNs so that each area of the network collaborates to minimize the service requirements for outside resources. To further attempt to optimize such solutions, we review an adaptation for service deployment according to network properties2. To complement micro-clouds in CNs, we need to consider the social behavior of the members to understand how people behave in the network where the CoP plays a role as an environment and to understand the expected behavior of the services with respect to the provided social properties. The level of interaction and collaboration between people must be respected and transposed toward the service behavior to have a fair system and motivate further interest in the services. We find that building micro-clouds can be a solution to minimize the dependency on the outside network (Internet) within CNs. In fact, with the broader use of micro-clouds, such networks can minimize Internet interaction, favoring services that are already available on the CN and diminishing the traffic on the Internet. However, issues also arise as micro-cloud services come into play, such as their performance with constrained devices, the communication latency in both networks, and the motivation to use newly created services rather than well-established Internet services. We can also establish that service routing is a key step toward optimizing services while making them attractive to members. However, such routing is only performed by assessing the network itself, which may not lead to collaboratively using devices on the network, disregarding social interactions. Our work aids in the optimization of overlays within micro-clouds on CNs by using CoP information to build and optimize relay nodes when information is disseminated. Services within the CN micro-clouds focus on peer-to-peer (P2P) dissemination and run with constrained devices3,4. Therefore, with CoP information for social support, we aim to build network overlays that prioritize information according to how users contribute to the network. Nevertheless, all nodes should be guaranteed to receive their fair share of the services. The resulting overlay created through SELECTinCN (Select in Community Networks) disseminates the data through nodes that contribute more without losing those that contribute less. When applying SELECTinCN on services in micro-clouds, we need to consider that each node (or user) contributes to the community in various ways, such as contributing network links, devices, or capital to construct area antennas or faster links. However, we see that each user may not be concerned about using all the services available in the micro-clouds in the same way. Therefore, we can establish a contribution as a component of disseminating data for each service. In summary, we define our contributions as follows: •Using the CoP information as the main source for relationships between users, we propose optimizing service overlays within micro-clouds in CNs that exploit both social graphs and cooperation between members. •We describe and evaluate a reassignment process that projects the social graph onto the P2P overlay network, minimizing the distance of the overlay networks’ ID space. •The SELECTinCN algorithm defines the connections that allow for message propagation with a minimum number of hops when using CoP information instead of friendship graphs. It is adaptive to dynamic environments with the use of novel recovery mechanisms, applying re-routing when required. •To understand the value and viability of using CoP information to enhance service overlays in micro-clouds, we evaluate and analyze this using a simulation environment. 2http://guifi.net/node/3671/view/services Nuno Apolónia ET AL 3 To prove the viability and scalability of our proposed system, we conducted simulations on large-scale datasets with thousands to millions of users collected through Facebook and Twitter. We experimentally show that this social graph exploitation reduces the number of hops required for dissemination by over 64% and reduces the number of relay nodes by over 89% against the state-of-the-art approaches. Moreover, we compare our previous results with experiments with CoP information gathered from CNs. The results are in the same range as the social network information, thus demonstrating its viability for use within the micro-clouds in CNs. The rest of the paper is organized as follows. In Section 2, we provide an information on the CoP and micro-clouds and the background of the structured P2P topology construction protocol. The design of SELECTinCN, our proposed solution for optimizing overlays in micro-clouds, is presented in Section 3. In Section 4, we present an extensive evaluation of our proposed approach against the state-of-the-art approaches and discuss the results in Section 5. In Section 6, we conduct a review of the related work. The last section concludes and specifies the direction for future work. 2 BACKGROUND 2.1 Community of Practice Communities of practice (CoPs) are a group of people socially involved in a given domain or goal. Community networks (CNs) can be perceived as CoPs because each individual person in the network aims to make their network sustainable for Internet or other services. In fact, in Guifi.net, one of the largest CNs, we observe several groups through the forum and mailing lists used for communication between members. Such groups are formed to tackle issues that are relevant within the same geographic zones. Each group is considered a CoP group that aims to gather information or even devices that can augment their capacity or performance with respect to the location. In addition, the CoP can be viewed as a social network with the same properties as small-world networks. The activity in CNs can be considered a collaboration of individuals to guarantee that the network is stable, free, and open to anyone that wishes to join. Moreover, a CoP system within CNs is naturally established with goals, such as building main antennas, joining highly connected localities with fiber optics to increase Internet usability, or even making edge cloud devices available to be shared within the community for their own services. The fact that CoPs can be considered social networks regarding the collaboration of individuals can be used to augment the knowledge of the network to improve cloud services. However, such an approach has not been addressed in the literature. Instead, social networks, such as Facebook, Twitter, and others, have been assumed to be the main point for social interactions. 2.2 Micro-Clouds Edge cloud computing is a case of cloud computing by moving computations to the resources at the network edge, thus fully using the edge resources and relying less on Internet cloud resources. In this way, edge cloud computing works to share its own services and resources without going outside of the local network (i.e., to the Internet) to use cloud services. There are significant differences between classic cloud environments and edge clouds. An important characteristic is the use of distributed low-capacity devices instead of centralized data centers with powerful computing devices. Moreover, the network between devices has a higher variance in latency and bandwidth between devices than traditional data centers. Our case study of edge cloud computing in CNs includes micro-clouds built with Cloudy3. Cloudy is a distribution based on Debian GNU/Linux, which is intended to be used by common users. Therefore, Cloudy’s development was driven by important aspects, such as the ease of use, deployment in low-capacity devices, automated service discovery, and service pre-configuration. Furthermore, community services are included in the distribution to facilitate the process for edge cloud computing (e.g., PeerStreamer for peer-to-peer based live streaming, Tahoe-LAFS for decentralized storage service, and Syncthing4for data synchronization between various storage nodes, among others). In addition, the shared services within Cloudy are expected to be automatically announced to the network (published/unpublished) when initiated by the users. In Cloudy, services can use an overlay network created through existing technologies, such as Serf5, which specifically clusters nodes and manages service availability in the CN micro-clouds. 3http://cloudy.community 4https://www.syncthing.net/ 5https://serf.io/ 4Nuno Apolónia ET AL 2.3 Peer-to-Peer Networks A P2P overlay network consists of a set of 𝑁peers (||=𝑁). The identifiers of the peers are assigned from an ID space  on the unit interval ∈ [0 … 1) using a uniform mapping function (SHA-1). A distance function 𝑑(𝑢, 𝑣)indicates the distance between peer 𝑢∈and peer 𝑣∈in the ID space . Each peer 𝑝∈maintains short-range links 𝑠 𝑝⊂that are peers with the minimum distance 𝑑(𝑢, 𝑣)in the ID space and long-range links 𝑙 𝑝⊂established with a probability that is inversely proportional to the distance between the peers. The short-range links 𝑠 𝑝and long-range links 𝑙 𝑝of each peer 𝑝form the routing table 𝑝=𝑠 𝑝+𝑙 𝑝, where |𝑝|≪ 𝑁, usually |𝑝|=𝑙𝑜𝑔𝑁. This is the case in the latest P2P models5. To reach all peers within a minimum time, the optimization minimizes connections instead of establishing connections to all peers. The lookup query from peer 𝑝for peer 𝑢is routed in a greedy fashion (i.e., peer 𝑝selects the neighbor 𝑤∈𝑝that minimizes the distance 𝑑(𝑤,𝑢)in the ID space to forward the query). The lookup process forms an ℎ-hop path 𝑝→+𝑢with ℎ=|𝑝→+𝑢|≥1. Based on the selection process of the links 𝑝, the P2P overlay networks can guarantee that the ℎ-hop path is bounded in 𝑂(𝑙𝑜𝑔𝑁). Moreover, peers are heterogeneous in terms of their connectivity characteristics. Different peers present different bandwidth capabilities 𝑏𝑤𝑝, which affects the rate at which a peer can send and receive packets. Therefore, the time data take to reach peer 𝑢from peer 𝑝can be given by 𝑙(𝑝, 𝑢) = ∑ℎ 𝑖=1 𝑏𝑤𝑖. The propagation of messages from peer 𝑝to peer 𝑢is calculated based on the bandwidth capability that each peer 𝑤∈ℎmaintains in the ℎ-hop path between peers 𝑝and 𝑢. A routing tree 𝑅𝑇𝑏is constructed to disseminate the message to all members 𝑏. Thus, the edges of the routing tree connect social peers that receive and forward the message until all members receive it (in a publisher/subscriber fashion). The relay nodes 𝑟∈𝑅𝑇𝑏are viewed as the edges of the routing tree 𝑅𝑇𝑏in the path between a publisher and its subscribers, thus allowing relay nodes to be subscribers themselves, depending on the social graph. The focus of our work is to minimize the number of relay nodes used to disseminate a message on the P2P system within micro-clouds and to reduce the dissemination latency, even when including node churn. In addition, we aim to optimize the current overlay network that exists in micro-clouds by adding social information with the network status. Although the routing tree 𝑅𝑇 guarantees the dissemination of the message to all required members, it suffers from a high number of relay nodes. This happens because social users that are connected in the routing tree 𝑅𝑇 are not necessarily directly connected in the P2P overlay network. Hence, each edge in the routing tree consists of 𝑂(𝑙𝑜𝑔𝑁)relay nodes. We must ensure that all social users will receive propagated messages regardless of the structure of the social network or CoP. Therefore, a P2P substrate that minimizes the number of relay nodes in the routing tree 𝑅𝑇 is required. We define the problem of minimizing the relay nodes as follows: Given a publisher 𝑏and a set of subscribers 𝑆𝑏, each peer 𝑝∈aims to establish links in the routing table 𝑝such that the routing tree for publisher 𝑏and subscriber 𝑠∈𝑏contains the minimum number of relay nodes 𝑏= {𝑠∈|𝑓(𝑠, 𝑏) = 𝑓𝑎𝑙𝑠𝑒}, granting a near theoretical optima minimal solution. 3 SELECTINCN SYSTEM SELECTinCN aims to construct a global P2P overlay network that establishes connections between peers that host social connections. Moreover, SELECTinCN seeks to organize close socially connected peers in the overlay network to reduce the number of hops required for the routing process. The intuition behind this is to provide a P2P substrate that reduces the number of hops between two socially connected peers and to maintain the minimum number of relay nodes of the routing tree 𝑅𝑇𝑏for each publisher 𝑏∈. Finally, the goal of SELECTinCN is to optimize service overlays within micro-clouds in CNs while having a low latency influence. 3.1 Applying the Community of Practice The information gathered from the CoP differs from the usual social networks. Instead of relationships between users, such as friends and friends of friends, it uses the concept of interactions between people (cooperation between members). We exploit the mailing lists (as an alternative to social networks) to establish interactions between people and understand how people cooperate. Therefore, by establishing the relations as the cooperation between the users, it is an easier process to identify the main users who cooperate with others. Nuno Apolónia ET AL 5 TABLE 1 Local state of peer 𝑝and listing of local variables for a given peer. 𝐷𝑝the identifier for peer 𝑝 𝑝a set of peer identifiers to which peer 𝑝is connected 𝑝a set of peer identifiers that host the user relations of peer 𝑝 𝑝a set of connections that peer 𝑣∈𝑝maintains The mailing list information was gathered from the Guifi.net mailing lists.6We assume that the mailing lists are used exclusively for cooperation within the network and for network enhancement. Thus, users interact with each other in a variety of cooperation projects. For example, topics on the mailing lists include the installation of new routers/devices and services to be used by the community. From such lists, we identified the users (by email) and cross-referenced all the posts to establish common links between users. Therefore, we established the strength of cooperation for each user when they appear in different threads. In addition, the lists are primarily separate for geographically separate locations. Thus, we can add users that collaborate between different locations and those that only cooperate within the same region. Other types of CoPs should be usable as long as relations can be established between members, such as in the case of real-life meetings in which members come together to discuss and even deploy devices in the field. The number of mailing list users is a small percentage of the total users of the network because only some of the people cooperate with others using mailing lists. We find that most people tend to install their devices without much guidance and let the network itself automatically configure routing and cooperation with other devices. Some of the network users also use real-life meetings for cooperation. However, the CoP over CNs follows small-world properties, where the clustering coefficient is not small and the distance between nodes grows logarithmically. Our system model consists of a set of peers and a set of social users , where the social users are members of mailing lists. Each social user 𝑢∈is mapped onto only one peer 𝑝∈. We assume that peers communicate with each other over reliable channels (e.g., TCP connections) that bound the number of connections each peer maintains. Each peer maintains a set of four local variables listed in Table 1 . The first variable, 𝐷𝑝, is the identifier of the peer 𝑝and defines the position of peer 𝑝in the ID space ∈ [0 … 1). SELECTinCN organizes the socially connected peers within a close distance in the overlay network. Thus, each peer 𝑝modifies its identifier 𝐷𝑝to minimize the distance 𝑑(𝑝,𝑢)to its most important peer 𝑢. We measure the importance between two peers using the strength of cooperation between two users in the social graph. Using the mailing lists, we determine where each pair of members communicates with each other, strengthening their relationship in multiple threads 𝑡. Therefore, we define the social strength between two peers 𝑝and 𝑢as follows: 𝑠(𝑝, 𝑢) = |𝑝∩𝑢|∗𝑡 𝑝 , 𝑝, 𝑢 ∈(1) 3.2 System Overview The SELECTinCN system is built with three main processes: –Projection: SELECTinCN associates the position of each peer that hosts a social user in the overlay network. The position of each peer is used to define the distance between two socially connected peers in the ID space . When a peer joins the overlay network, the local variables of Table 1 are initialized. –Identifier Reassignment: SELECTinCN evaluates the peer positions in the ID space and reassigns the identifiers on a round-based basis. Specifically, each peer leverages the social information and modifies its identifier to reduce its distance in the overlay network with users that have higher collaboration relations. –Peer Connection Establishment and Reassignment: While SELECTinCN organizes the socially connected peers in the same area in the ID space , each peer establishes direct 6https://llistes.guifi.net/sympa 6Nuno Apolónia ET AL connections to peers that are part of the CoP. A link reassignment process is performed to ensure that each social peer communicates with the maximum number of CoP members in the minimum required hops with the minimum dissemination latency. Both the peer identifier and connection reassignment processes use a gossip-based peer-sampling methodology to evaluate the defined topology. 3.3 Projection and Identifier Reassignment The projection process determines the initial position of the peer that is perceived by the underlying overlay network. As shown in Algorithm 1, the projection of the social user in the overlay network is specified based on the relations of the user (line 1). Thus, the assigned identifier 𝐷𝑝is reduced in terms of the distance (line 3) between peer 𝑢and peer 𝑣when user 𝑣has a relationship with other users. Otherwise, a random identifier is assigned to peer 𝑣using a uniform hash function (line 5). As the CoP grows, social users interact more often, and the social strength in Equation 1 between two users is modified. The goal is to reduce the distance in the ID space between social users. Each peer modifies its identifier and moves closer to the peer that hosts a collaboration (social peer) with higher social strength. The new position choice is the centroid of all its social relations. To address the problem using only the highest connected users, we use the centroid between the two social peers that maintain the highest social strength value, as presented in Algorithm 2, to avoid congestion and to avoid centering the network on only the most active members. Complexity Analysis: For each peer 𝑝∈, the initial position in the overlay network is calculated in 𝑂(1) because the identifier is assigned either uniformly or based on a user connection. Thus, the initial projection of the social graph in the P2P topology requires 𝑂(𝑁)complexity. The reassignment of the peer identifiers based on the peer-sampling protocol requires 𝑂(|𝑝|)complexity for each peer, where |𝑝|≪ 𝑁. In modern social networks, |𝑝|is usually in the range of hundreds of social friends, while the size of the network 𝑁is billions of users6. For CNs, the numbers are smaller in comparison; however, they have grown over the last few years. Thus, 𝑁is around 30,000, whereas the social interactions on a local level may be less than a hundred. Summarizing, the total complexity of the projection and identifier reassignment algorithm is as follows: 𝑂(𝑁⋅|𝑝|)(2) Procedure 1 Peer Identifier Assignment Input: 𝑣∈newly registered social users Output: 𝐷𝑝peer identifier 1: if 𝑣≠∅then 2: u←the peer of the social user that invited 𝑣 3: 𝐷𝑝←𝑚𝑖𝑛𝐷𝑑(𝑢, 𝑣) 4: else 5: 𝐷𝑝←UNIFORMHASH(𝑣) 6: end if 7: Return 𝐷𝑝 Procedure 2 Peer Identifier Reassignment 1: Procedure EVALUATEPOSITION() 2: 𝑢←the peer with the highest social strength in 𝑝; 3: 𝑣←the peer with the second highest social strength in 𝑝; 4: 𝐷𝑝←|𝑑(𝑢,𝑣)| 2; 5: end Procedure Nuno Apolónia ET AL 7 Procedure 3 Peer-sampling - Active Thread 1: Procedure EXCHANGERT() 2: socialFriend ←getRandomSocialFriendPeer(); 3: Send <𝑝,𝑝>to socialFriend; 4: Receive < 𝑛𝑀𝑢𝑡𝑢𝑎𝑙, 𝑀 > from socialFriend; 5: 𝑠𝑜𝑐𝑖𝑎𝑙𝐹 𝑟𝑖𝑒𝑛𝑑.nMutual = nMutual; 6: 𝑠𝑜𝑐𝑖𝑎𝑙𝐹 𝑟𝑖𝑒𝑛𝑑.M = M; 7: 𝐷𝑝←evaluatePosition(); 8: 𝑝←createLinks(); 9: end Procedure Procedure 4 Peer-sampling - Passive Thread 1: Procedure RESPONSEEXCHANGERT() 2: Receive <𝑢,𝑢>from socialFriend; 3: nMutual ←|𝑢.merge(𝑝)|; 4: 𝑠𝑜𝑐𝑖𝑎𝑙𝐹 𝑟𝑖𝑒𝑛𝑑.nMutual ←nMutual; 5: 𝑀←𝑢.constructFriendshipBitmap(𝑝); 6: Send < 𝑛𝑀𝑢𝑡𝑢𝑎𝑙, 𝑀 > to socialFriend; 7: 𝑀′←𝑝.constructFriendshipBitmap(𝑢); 8: 𝑠𝑜𝑐𝑖𝑎𝑙𝐹 𝑟𝑖𝑒𝑛𝑑.bitMap = 𝑀′; 9: 𝐷𝑝←evaluatePosition(); 10: 𝑝←createLinks(); 11: end Procedure 3.4 Peer Connection Establishment and Reassignment SELECTinCN uses a gossip-based peer-sampling service to construct the topology in the overlay network. Each peer periodically acquires its social neighbor’s connections in the overlay network and evaluates its current established connections. Specifically, each peer 𝑝seeks to establish direct connections with the maximum number of peers in its social neighborhood 𝑝. To create a ring topology, each peer is allowed to accept only 𝐾incoming links while maintaining two short-range outgoing links 𝑠 𝑝with its successor and predecessor in the overlay network and 𝐾long-range outgoing links 𝑙 𝑝with its social peers. The intuition behind the 𝐾incoming links is to avoid having peers that have too many connections because other peers seek to connect to them, creating more traffic than others. When the 𝐾incoming links are established, the peer accepts a new incoming connection if the new connection has a better bandwidth capacity than the already-existing connections. The 𝐾outgoing longrange links are selected by applying the locality sensitive hashing (LSH) technique to the social neighbor’s connections retrieved from the peer-sampling service (lines 3-6 and 2-8 in Algorithms 3 and 4, respectively). The LSH technique is used to identify the peers that maintain different connections and to avoid any link overlap in the overlay network. The connection establishment mechanism is shown in Algorithm 5. We begin by indexing the bitmaps of the social neighborhood in buckets in the LSH index (lines 2-4). In our algorithm, we consider the number of buckets to be equal to the number of defined long-range links (||=𝐾). The reason for selecting ||=𝐾buckets in the LSH index is to simplify the selection process of the direct connections. Peers whose connections are similar will be indexed in the same bucket. This results in selecting only one peer of each bucket to establish at most 𝐾long-range links. The bitmap of 𝑢∈𝑝is an array of size |𝑝|, the values of which define the link existence in 𝑢between two socially connected peers 𝑢∈𝑝and 𝑣∈𝑝, where 𝑢≠𝑣, as follows: 𝑏𝑖𝑡𝑚𝑎𝑝(𝑢, 𝑣) = {1if (𝑢, 𝑣) ∈ 𝑢 0if (𝑢, 𝑣) ∉ 𝑢 8Nuno Apolónia ET AL The bitmaps are indexed in the buckets of LSH in lines 5-18, and we aim to select one peer from each bucket ℎ∈to establish a connection. To establish connections with the maximum number of peers 𝑝in the social neighborhood 𝑝with the minimum dissemination latency, we select the peer that presents the maximum value in the bitmap (line 8). In doing so, we ensure that each peer achieves the maximum number of social connections with the minimum number of peer connections (not all 𝐾connections are used). Moreover, we drop an already-established connection (𝑝, 𝑢) ∈ 𝑝with a peer 𝑢that presents similar connections with the newly established connection (𝑝, 𝑣) ∈ 𝑝(lines 12-16) in Algorithm 5. Procedure 5 Peer Link Reassignment 1: Procedure CREATELINKS() 2: for 𝑢∈𝐶𝑝do 3: LSHIndex(𝑢.𝑏𝑖𝑡𝑀𝑎𝑝); 4: end for 5: for ℎ∈do 6: ℎ←peers assigned in the same bucket ℎ; 7: if ℎ≠∅then 8: 𝑢←picker(ℎ); 9: if (𝑝, 𝑢) ∉ 𝑝then 10: 𝑝←(𝑝, 𝑢) 11: end if 12: for 𝑣∈ℎ, 𝑣 ≠𝑢do 13: if (𝑣, 𝑝) ∈ 𝑝then 14: 𝑝, remove(v); 15: end if 16: end for 17: end if 18: end for 19: end Procedure Procedure 6 Picker Peer Connection 1: Procedure PICKER(ℎ) 2: ℎ←sort peers(ℎ) 3: if (|ℎ|>0)&& (ℎ(0).𝑏𝑤 < ℎ(1).𝑏𝑤)then 4: return ℎ(1) 5: end if 6: return ℎ(0) 7: end Procedure Complexity Analysis: The complexity analysis of the connection establishment and reassignment algorithm is analogous to the number of social peers |𝑝|that each user maintains and the number of buckets ||assigned on the LSH index. The peer-sampling protocol aggregates the bitmaps with 𝑂(|𝑝|)complexity. The index of the bitmaps in ||=𝐾buckets requires 𝑂(|𝑝|⋅𝑙𝑜𝑔(|𝑝|)⋅𝐾)complexity. The 𝐾long-range links are selected using the LSH index at 𝑂(𝐾)cost. Summarizing, the total complexity of the connection establishment and reassignment algorithm for each peer 𝑝∈is 𝑂(|𝑝|2⋅𝑙𝑜𝑔(|𝑝|)⋅𝐾2)(3) Nuno Apolónia ET AL 9 TABLE 2 Three real-world datasets of social networks that include user information, such as social connections and the average degree of social connection. Dataset Users/Peers Connections/Links Average Degree Facebook 63,731 817,090 25.642 Twitter 3,990,418 294,865,207 73.89 CoP-Guifi 3,016 16,471 10.9 4 EVALUATION For our evaluation, we consider previous experiments done with SELECTinCN and social networks, such as Facebook and Twitter, as the baseline7and the experiments with Guifi.net mailing lists as the CoP information. Therefore we show that our proposed solution can be applicable to other community networks, which exhibit the underlying user interaction patterns similar to that of Guifi.net (e.g., in collaboration networks such as FunkFeuer, AWMN or Freifunk). The simulation experiments were performed using the Gelly Graph API7running over the Apache Flink8distributed data processing framework. The experiments were run on a Flink cluster with 20 virtual machines to provide a distributed discrete event simulator suitable for conducting large-scale experiments. For each experimental round, we used all the users/peers from each dataset. The implementation of SELECTinCN is performed using the vertex-centric iterative model8. Specifically, in synchronized iteration steps, each peer produces messages to other peers and updates their identifiers and connections in the overlay network using the SELECTinCN algorithms. Experiments are performed in evolving networks, where users join the overlay network at different phases. We initiate our experiments by selecting a social peer 𝑢∈from the dataset at random. Thereafter, we insert a portion of the relationships of user 𝑢into the social network, following the model by9. Therefore, at each iteration step, we select a registered social user and insert a number of the userâĂŹs social peers into the social graph, which preserves the exponentially decreasing rate of the model. The same process as in the social networks is performed with the CoP graph in which relationships are added to the users with each iteration. In the experiments, we use all the users as peers from each dataset to create the overlay. 4.1 Datasets Our evaluation is performed with three real-world datasets listed in Table 2 . These datasets cover a wide range of social graph features from less connected graphs, such as Facebook10, to highly connected graphs, such as Twitter6, which enhances the evaluation of our proposed approach for several graph types. Moreover, we conduct experiments on the CoP-Guifi dataset, based on the gathered mailing list information. The number of nodes in the simulations corresponds to the number of users in the datasets, and the links correspond to the number of connections. 4.2 Metrics To measure the efficiency of SELECTinCN, we used the following metrics: •Number of hops: The average number of overlay hops within the path between two peers. •Number of relay nodes: The average number of relay nodes in the pub/sub routing tree. To validate our analysis, for each metric, we report the average result out of 100 independent trials to decrease the risk of statistical error. We consider these metrics to be important for understanding the behavior of SELECTinCN when different social information is used and for comparing the results with other work while also providing feedback on using SELECTinCN for the domain of CNs. 7https://ci.apache.org/projects/flink/flink-docs-master/libs/gelly_guide.html 8http://flink.apache.org/