RESEARCH ARTICLE Adv. Sci. Lett. 4, [605118]

RESEARCH ARTICLE Adv. Sci. Lett. 4,

1 Adv. Sci. Lett. V ol. ?, No. ?, ? 1936-6612/2011/4/400/ 008 doi:10.1166/asl.2011.1261 Copyright © 2011 American Scientific Publishers Advanced Science Letters
All rights reserved Vol. ? , ?–?, ?
Printed in the United States of America

ALM Based Services on HPM P2P Architecture
Mourad Amad1,2,*, Abdelmalek Boudries3 Lyes Badis1,2
1LaMOS Research Unit of Bejaia University, Algeria
2LIMPAF Laboratory, Bouira Univesity, Algeria
3LMA Laboratory, Bejaia University, Algeria

Application Layer Multicast (ALM) is considered as an attractive and promoting approach for implementing large scale
multicast services. In ALM, multicast functio nalities are implemented at the edge inst ead of the core network. As opposed to
IP multicast, ALM requires no infrastructure support and can be easily deployed in th e Internet. In this paper, we propose a
new efficient and scalable m odel for optimizing application layer multicast using HPM as underlying architecture. This
approach benefits from P2P properties and ch aracteristics. In this contribution, we consider a new optimized algorithm for
tree construction simultaneously for each ring of HPM. The gl obal tree construction algorithm is composed of two steps. In
the first step, we construct a s ub-tree for each ring; the second step is to build a global tree using sub sets of adjacent rin gs in
HPM architecture. The proposed solution inherits from main P2P attributes such as: scalabi lity and fault tolerance that
characterize HPM. Preliminarily performance evaluations show that results are globally satisfactory, the depth of the
resulting multicast tree is controlled and optimized.
Keywords: P2P, Group Communication, Media Streaming, ALM.

1. INTRODUCTION
Considering multimedia applications such as video on
demand (V oD), media streaming or media conferencing, efficient and optimized distribution of media content to a
large group of receivers constitutes a key requirement. In
response to such requirement, the efficient support of multicasting by network layer components ( ie. routers ) is
proposed in the form of "network" IP multicasting.
However, the ubiquitous deployment of IP multicasting have been challenged by sever al commercial issues such
as technical challenges rela ted to scalability, quality of
service support, security access or multicast sessions management. Given the advances and performance of
P2P networks and architecture, the need of multicast
capability for applications such as media conferencing,
leads us to propose a scalable and efficient solution that
optimizes ALM and also accelerates the tree construction time.

The rest of this paper is organized as follows: In section 2,
we give a brief related works on Peer to Peer networks ( a
special consideration is given for HPM [1] architecture on which this contribution is based ) and in another hand
the application layer multicast. The section 3 describes
and analysis the proposed model. Section 4 gives some preliminary results of performance evaluations. Finally,
we conclude and give some future works.

*Email Address: [anonimizat]

Adv. Sci. Lett. 4, 400–407, 2011 RESEARCH ARTICLE

2 2. RELATED WORKS: P2P AND ALM

Peer to Peer architecture is an alternative to
client/server model. The application layer multicast is
also an alternative to IP multicast. Combining the two above alternative approaches for new applications ( ex.
Multimedia diffusion in social networking ) is a new
challenge. The two sub-sec tions bellows introduce
separately the P2P and the ALM.

2.1. PEER TO PEER NETWORKS
There are several definitions of Peer to Peer systems
that are being used by the P2P community. As defined in [11]. "P2P allows file sharing or computer resources and
services by direct exchange between systems ". Also as
defined in [4]: "P2P is a class of applications that takes
advantages of resources-storage, cycle, content human
presence-availability at the edge of Internet ". There are
three main generations of P2P networks:

-The first generation: The main benefit of this class is
the organization of network architecture, where machines are not considered as client and server; but rather as
machines that offer and consume resources. Napster [6] is
an example of such system. It is composed of two services: the first service is decentralized and used for
files storing with centralized directory service for lookup
and retrieval. Figure 1.(a) shows Napster architecture.

-The second generation: The second generation systems
solved the problem of the centralized coordination in the first generation. However, the problem of scalability
becomes more critical due to the high rate of network
traffic generated by the flooding algorithm for service lookup. Gnutella [5] is an example of such systems.
Figure 1.(b) shows Gnutella architecture.
-The Third generation: The third generation of P2P
networks ( eg. HPM [1], Chord [10], P2P based CAN [8]
and Agregation based routing protocol [13]) is generally
based on the DHT ( Distributed hash table ) to generate
key for both nodes and data. Nodes identifier and keys value pairs are both hashed to one identifier space. The
nodes are then connected to each other’s in a certain
predefined topology ( ring as in Chord, multi-dimensional
coordinate space as in CAN and hierarchical rings as in
HPM ). The figure 1 shows representative examples of
each generation of P2P networks.

In this paper, we propose an ALM based on HPM architecture. The HPM protocol [1] is based on structured
and hierarchical rings. Each ring has 256 nodes ( in case
of 4 levels ). The first level ring contains nodes for which
IP addresses are different in the first part, with no restriction in the other parts. Each node in HPM is
identified by a unique identifier n which is the i
th part of its IP address ( 1 ≤ i ≤ 4), with i: the level on which the
node belongs to. Like nodes and using the distributed
hash tables, the resources are also identified by a unique
identifier. Each resource key is composed of four parts ( ex.
a.b.c.d ) too. Each node maintains a routing table
containing the IP address and port numbers of the
"neighboring" nodes. In each ring, nodes are ordered increasingly based on their identifiers.

Figure 1: Examples of P2P architectures: (a) Napster, (b)
Gnutella and (c) Chord

Let m be the number of bits in the space of node
identifiers on one level ( m = 8 for 256 nodes ). Each node
n maintains a routing table of at most m entries called the
finger table. The ith entry in the finger table of node n
contains the identifier of the first node p that succeeds n
by at least 2i-1 on the identifiers circle, where 1 ≤ i ≤ m. p
is called the ith finger of node n. A finger table entry
includes both the HPM" identifier and the IP address and
port number of the relevant node. In HPM, there are only
one ring in the first level, 256 rings in the second level,
2562 rings in the third level and 2563 rings in the fourth
level ( 255i-1 rings in the ith level ). Figure 2 shows the
HPM architecture where the finger table of one node
belonging to two levels is illustrated. The concerned node
has two identifiers, for example: N50 on level 1 and N52 on level 2.
The keys of resources are used in the context of lookup
services, the most executed operation in P2P networks. However, in ALM,
we don’t consider the key of resources.
We consider only the keys of nodes.

RESEARCH ARTICLE Adv. Sci. Lett. 4,

3 Adv. Sci. Lett. V ol. ?, No. ?, ? 1936-6612/2011/4/400/ 008 doi:10.1166/asl.2011.1261

Figure 2: HPM Architecture

2.2. APPLICATION LAYER MULTICAST

Many different mechanisms of ALM have been proposed.
Three important approaches for implementing multicast
exist: Any Source Multicast (ASM), Single Source Multicast (SSM) and Application Layer Multicast (ALM).
ALM aims to improve the scalability issues of unicast by
distributing data replication process among the different group members, but in an adaptative and efficient way.
However, ALM is not very efficient as IP multicast in
term of data duplication [2]. In ALM, the nodes are self-
organized based on mesh or tree structures.
In Narada [12], the overlay network is built according two
steps process. The first step tr ies to establish an optimized
well-connected and controlled mesh topology. The second
one is for building a source tree from each potential sender to every receiver, using a subset of existing mesh
links. As opposed to Narada, ALMI [7] relies on a central
session controller node to calculate a bi-directional and minimal spanning tree data distribution overlay between
the registered nodes. The session controller can be
implemented on one of the participant nodes or on a well-known external node.
For building an overlay tree, NICE [9] uses hierarchical
clustering techniques, whereby group members arrange themselves into clusters with the neighboring nodes.

The main objective of our proposed approach is to build
an efficient and optimized multicast tree from any node
(root or sender ) to all other nodes ( receivers ) using HPM
architecture. The next section describes our proposed
approach.

3. OUR APROACH

In this paper, we propose a new efficient and optimized
ALM. We use HPM as underlying architecture for our proposed approach. 3.1. MOTIV ATION

In a large scale P2P system, any node can be the source of
a data flow ( eg. real time applications, media distribution
over social networks ) that potentially concerns a large
number of receiving nodes. Also collaboration oriented applications such as media-conferencing need somehow
multicast mechanisms [2]. The media flow ( eg. audio,
video or data ) should be distributed between multiple and
independent participants and conference groups, with
efficiency and optimization. Our contribution based HPM
architecture, aims to contribute to this efficiency and optimization by minimizing the overhead and network
traffic, but also the depth of the constructed multicast tree,
which has an impact on delay, one of the most important
impairments of QoS.

3.2. FUNCTIONAL PRINCIPAL

Our proposed model is specific to HPM architecture for
global tree construction. The algorithm is composed of two steps. Building a sub-tree in each ring of HPM in the
first step, and the second step is for relaying each two
adjacent sub-trees corresponding to neighboring rings.

3.3. MULTICAST TREE CONSTRUCTION

To build an optimized multicast tree, we define a specific
data structure ( adjacency matrix ), and propose an
algorithm for multicast tree construction ( calculation )
based on this matrix. The algorithm is applied with the
same manner in each ring of HPM. The Adjacency Matrix
We define the adjacency matrix in our proposed model
(denoted Adj_Mat ) as follow: Adj_Mat[i,j] = 1 : if there is
a link between node N
i and Nj (not bijective link ), else it
is equal to zero. Table 1 represents the adjacency matrix of node N50 in ring R1 of level 1 for the network
topology illustrated in figure 2.

N0 N1 N2 N3 N4 N5 N6 N7
N0 – 1 1 0 1 0 0 0
N1 0 – 1 1 0 1 0 0
N2 0 0 – 1 1 0 1 0
N3 0 0 0 – 1 1 0 1
N4 1 0 0 0 – 1 1 0
N5 0 1 0 0 0 – 1 1
N6 1 0 1 0 0 0 – 1
N7 1 1 0 1 0 0 0 –
Table 1: Adjacency matrix

Based on the adjacency matrix defined on table 1, we
give an optimized ALM ( algorithm 1 ) for multicast tree
construction process. This algorithm is applied with the
same manner in each ring composed HPM.

Adv. Sci. Lett. 4, 400–407, 2011 RESEARCH ARTICLE

4
Algorithm 1: Multicast tree construction algorithm
–––––––––––––––––––––––––
1: Begin
2: If (Ni is a source node ) then
3: Send message TREE-SUCCESSOR (N i) to all nodes in its finger
table
4: else //Ni is not a source
5: At the reception of the messages TREE-SUCCESSOR (N i)
5.1. If ((Ni has not received the same message ) then
5.1.1. If (Ni belongs to another ring ) then
– Ni becomes a source node and executes the multicast tree
construction algorithm with the same manner
5.1.2. Else
– Forwards this message to all nodes in its finger table
5.2. Else
– Discard this message,
6: End.

Algorithm 1: Multicast tree construction algorithm

3.4. SHARED ADJACENCY MATRIX

The Adjacency matrix represents the neighboring of nodes in each ring of HPM, and then it must be shared
efficiently between them. The algorithm 2 shows how to
share the adjacency matrix in our proposed model.

Algorithm 2: Shared Adjacency Matrix Algorithm
1: Begin
2: For any change in finger table or at reception of a new entry of
adjacency matrix do
3: Update this entry,
4: Send this entry to all successors in the finger table
5. End.

Algorithm 2: Shared Adjacency Matrix Algorithm

3.5. NODES JOIN AND LEA VE PROCESSES

In a dynamic environment, nodes can join or leave the network at any time. Given this, a "Bootstrapping
mechanism" constitutes a required key functionality, and is required for P2P networks. Nodes intending to
participate in such overlay ne twork, initially have to find
at least one node already member of this network. Four types of bootstrapping mechanism exist: Static
Overlay Nodes Bootstrapping Servers, Out-of-band
Address caches, Random Address Probing and Employing Network Layer Mechanism [11]. For
simplification, we choose the static overlay nodes
bootstrapping.
When a new node joins the system, it takes place in the
HPM architecture. When another node p discovers this
new node, it sends the message
TREE-SUCCESSOR (p) to
the new comer. This last accepts and forwards the
message to all its children ( successors ). Consequently,
just a portion of the multicast sub-tree is updated ( in one
ring). When a node leaves the system, a stabilization algorithm
of HPM is invoked. This process should be executed
following a node join or leave ( or failure ), and then a
portion of the multicast sub-tree is updated. The figure 3 shows the static overlay nodes bootstrapping Servers
mechanism, generally used in P2P networks.

Figure 3: The bootstrapping mechanism

4. PERFORMANCE EV ALUATION

Figure 4 shows the cost of adjacency matrix, it is equal to
O(Log 2(ni)), n i ≤ 256 , where each cell contains one bit,
which means that this data structure does not affect the
scalability of our proposed approach.

Figure 4: Adjacency matrix size

Figure 5 shows the average overhead messages generated
when applying the multicast tree construction algorithm simultaneously/sequentially in each ring. The figure
shows that the overhead messages are reduced when
using sequentially multicast tree construction algorithm,
but evidently the simultaneously method reduces the time
taken by the algorithm.

RESEARCH ARTICLE Adv. Sci. Lett. 4,

5 Adv. Sci. Lett. V ol. ?, No. ?, ? 1936-6612/2011/4/400/ 008 doi:10.1166/asl.2011.1261

Figure 5: The average of overhead messages

Figure 6 shows the average depth of resulting multicast tree, which increments in logarithmic way in the
beginning ( when HPM is composed of one ring ) but also,
it is maximized by the value 16. This is has an impact on
delay, one of the most important parameters for real time
applications, like video/audio conferencing based multicast
.

Figure 6: The average depth of multicast tree

5. CONCLUSION AND PERSPECTIVES
Heterogeneity is one of th e main characteristics of
Internet. It is necessary to cr eate efficient, fault-tolerant
and scalable solutions for data delivery especially for group communications. ALM is based on different and
independent mechanisms. Building multicast on top of
decentralized, scalable, and reliable P2P overlay networks offers a promising approach.

In this paper, we have proposed a novel optimized and
scalable model for application layer multicast using HPM
architecture. We provide an efficient algorithm for
multicast tree construction process. It is based on a
particular shared data structure called Adjacency matrix.
Performance evaluation shows that our proposed approach is globally satisfactory. The average depth of
resulting multicast tree is O(log
2(n)), which has an
important impact on delay, one of the most important parameters of QoS for real time application like video/audio conferencing.
In term of perspectives, we envision extending our
proposed model in the context of social networking in
order to make an optimized media streaming over existing social networking architectures such as Routil [3].

REFERENCES

[1]: Mourad Amad, Ahmed Meddahi, Djamil Aïssani,
Zonghua Zhang, HPM: A novel hierarchical Peer-to-Peer
model for lookup acceleration with provision of physical proximity , Journal of Network and Computer Applications,
Elsevier, vol. 35(6), pp. 1818-1830, 2012
[2]:Mourad Amad, Ahmed Meddahi, Gilles Vanwormhoudt,
A Self-Adaptative ALM Architecture for P2P Media Streaming , in 2015 International Conference on Protocol
Engineering (ICPE) and International Conference
on New
Technologies of Distributed Systems (NTDS), Paris, 2015.
[3]:Lyes Badis, Mourad Amad, Djamil Aïssani, Aldja
Benkerrou and Kahina Bedjguelel, ROUTIL: P2P Routing
Protocol based on Interest Links , International Conference on
Advanced Aspects of Software Engineering (ICAASE’16), Constantine, Algeria, October 2016.

[4]: C. Shirky. What is p2p..and what isn’t , O’ Reilly
Network, 2001.
[5]: Gnutella. http://www.gnutella.com .
[6]: Napster. http://www.napster.com
[7]: D. Pendarakis, D. Verma S. Shi and M. Waldvogel,
Almi: an application level multicast infrastructure , in the
3rd USENIX Symposium on Internet Technologies. San
Francisco, CA, USA, Mars 2001.
[8]: Bin Zeng, Rui Wang, A novel lookup and routing
protocol based on CAN for structured P2P network , 2016
IEEE International Conf erence on Computer
Communication and the Internet (ICCCI), Wuhan, China,
December 2016, doi: 10.1109/CCI.2016.7778866
[9]: S. Banerjee, B. Bhattacharjee and C. Kommareddy,
Scalable application layer multicast , in ACM SIGCOMM ,
Aug 2002.
[10]: Ion Stoica, Robert Morris, David Liben-Nowell, David
Karger, M. Frans Kaashoek, Frank Dabek and Haris Balakrishnan, Chord: A scalable peer-to-peer lookup service
for internet application , IEEE/ACM Transactions on
networking, Vol. 11, No. 1, January 2003.
[11]: Peer to Peer Working group, Bidirectional peer-to-
peer communication with interposing firewalls and Nats ,
White Paper , 2001.
[12]: S. Rao Y-H. Chu and H. Zhang, A case for end system
multicast , in ACM IGMETRICS , pp. 1–12. Santa Clare, CA,
USA, June 2002. [13]: Nicolas Hidalgo, Luciana Arantes, Pierre Sens,
Xavier Bonnaire, An Aggregation-Based Routing Protocol
for Structured Peer to Peer Overlay Networks , 2nd
International Conference on Advances in P2P Systems (AP2PS 2010) , Florence, Italy, pp.76-81, 2010.