# A Multi-constraint Resource Search Algorithm for P2P-SIP Conference Services

Hui-Kai Su, Wen-Hsu Hsiao, Jian-Ting Pan, Chen-Hung Liao, Kim-Joan Chen, Chien-Min Wu

► To cite this version:

Hui-Kai Su, Wen-Hsu Hsiao, Jian-Ting Pan, Chen-Hung Liao, Kim-Joan Chen, et al.. A Multi-constraint Resource Search Algorithm for P2P-SIP Conference Services. 9th International Conference on Network and Parallel Computing (NPC), Sep 2012, Gwangju, South Korea. pp.360-372, 10.1007/978-3-642-35606-3_42. hal-01551334

HAL Id: hal-01551334

https://inria.hal.science/hal-01551334

Submitted on 30 Jun 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Multi-Constraint Resource Search Algorithm for P2P-SIP Conference Services

Hui-Kai Su¹*, Wen-Hsu Hsiao², Jian-Ting Pan³, Chen-Hung Liao⁴, Kim-Joan Chen³, Chien-Min Wu⁵

¹Dept. of Electrical Engineering, National Formosa University, Yun-Lin 632, Taiwan

²Dept. of Computer Science and Information Technology, WuFeng University, Chia-Yi 621, Taiwan

³Dept. of Electrical Engineering, National Chung-Cheng University, Chia-Yi 621, Taiwan

⁴Telecommunications Laboratories, Chunghwa Telecom Co. Ltd., Taoyuan, Taiwan

⁵Dept. of Computer Science and Information Engineering, Nan-Hua University, Chia-Yi 622, Taiwan
hksu@nfu.edu.tw

**Abstract.** Peer-to-peer conference is an interactive multi-users conferencing application that improves the issues of concentrated loading, single-point failure and expensive infrastructure cost for the traditional centralized conference model, according to the conference resource shared by each other. The benefit of non-centralized system can be achieved by using P2P-SIP. However, unlike the traditional centralized architecture, the conference resource is provided by each peer user. How to search the heterogeneous resource efficiently is a key point in the dynamic and distributed environment. Thus, we proposed a multi-constraint resource search algorithm for P2P-SIP conferencing services. In the full distributed environment, users can search a usable resource to reduce the call-setup time and save the conferencing cost according to the conferencing scale and the quality requirements.

**Keywords:** Peer-to-Peer; Session Initiation Protocol; Resource Search Algorithm

## 1 Introduction

In the centralized architecture of the traditional multimedia conferencing model, several high-performance equipment has to be purchased by the conferencing service provider. With the user increasing, the loading of the conference server becomes heavy. More conference high-end servers should be deployed to support a highly-scale conferencing service and keep the conference quality. Thus, the

<footnote>* Corresponding author.</footnote>
conferencing service provider has to invest more money in the conferencing-service infrastructure.

According to the Peer-to-Peer (P2P) concept, users share their resource to each other. Consequently, the infrastructure cost of conference servers can be reduced. Additionally, the P2P conference system is unlike the centralized conference system. Due to no centralized conference server to handle conferences, the conference resource have to be looked up by using a P2P resource discovery mechanism, e.g., participants' address, available P2P focus and available P2P mixer, etc. Based on the P2P resource discovery mechanism, the available conference resource can be searched out by cooperating with other peers. However, although P2P conference service can be achieved by P2P-SIP related works[오큐! 참조 원본을 찾을 수 없습니다., 오큐! 참조 원본을 찾을 수 없습니다., 오큐! 참조 원본을 찾을 수 없습니다.], the present scheme cannot support constraint-based conference resource discovery. In a heterogeneous P2P conference environment, the capacity of each peer is different. How to search out an available and feasible resource efficiently to satisfy the conference requirements is very significant in a real environment.

This paper proposed a multi-constraint resource search algorithm for P2P-SIP conferencing services in a heterogeneous overlay network. According to the peer capacity, peers are classified and managed with an abstract and logical tree structure. The specified tree structure can provide a conference resource discovery functionality with multiple constraints. Thus, the resource requirements of a conference can be satisfied and supported by other peers, such P2P focus and P2P mixer.

## 2 Background

Recently, multimedia conferencing service is more and more popular. The IETF has organized some related working groups that develop standards for multimedia conferencing and discuss related issues. Many RFC documents were proposed, such as RFC 4353[오큐! 참조 원본을 찾을 수 없습니다.], RFC 4579[오큐! 참조 원본을 찾을 수 없습니다.] and RFC 5850[오큐! 참조 원본을 찾을 수 없습니다.]. The architecture models, components and protocols of SIP conference were discussed.

P2P SIP composes of the characteristics of P2P distributed architecture and centralized client-server model. The resource locating and message transmission services for full distributed environment is provided by using an P2P overlay network. The advantages of decentralization, low cost, high robustness and high scalability are included. The problems of single-point failure and loading concentration can be reduced. Nowadays, P2PSIP is based on the SIP-over-P2P framework. A P2P protocol, e.g., Chord, provides resource store and discovery for SIP. The registration and addressing of SIP users are achieved. Other applications can also be applied.

P2PSIP working group was organized in 2007, and several related drafts were proposed. The working group make efforts in the development of P2PSIP standards. The reference [오큐! 참조 원본을 찾을 수 없습니다.] proposed a resource discovery mechanism with P2PSIP. The mechanism can store the resource
information into the distributed P2P network dynamically. However, the peer heterogeneity is not considered. An unsuitable resource may be searched out to support a large multimedia conference. Consequently, its quality would be unstable and the conference may be crashed.

## 3 A Multi-Constraint Resource Search Algorithm for P2P-SIP VoIP Services

In this section, the design of multi-constraint resource search algorithm over the P2P network is proposed. The resource discovery in DHT can be divided into two methods usually. The first method is random walk[오휴! 참조 원본을 찾을 수 없습니다.]. The nodes would randomly probe their neighbors to ask if they are resource providers. This method brings a huge network overhead and inefficient search. The second one is putting resource information and corresponding index into the overlay, then getting resource information by retrieving the index from the overlay, such as [오휴! 참조 원본을 찾을 수 없습니다.].

In addition, no service discovery usage standard for RELOAD was proposed. In order to find a suitable resource for P2P-SIP in the distributed network, P2P-SIP Working Group also proposed the related draft for service discovery, i.e., Recursive Distributed Rendezvous (ReDiR)[오휴! 참조 원본을 찾을 수 없습니다.].

In [오휴! 참조 원본을 찾을 수 없습니다.], it discovers the nearest resource with Node-ID because the resource is distributed and discovered based on Node-ID. Furthermore, ReDiR requires O(log n) messages (or discovery hops) to find resource. In the situation, the searched resource could not support the conference sometimes, such as limiting in its mixing capacity or transport capacity. The resource discovery procedure may be re-performed until the suitable resource is found. For conferencing, it means the call setup time increases with the messages (or discovery hops) and peer capacity. Thus, we propose a multi-constraint resource search algorithm to reduce the call setup time.

On the other hand, the heterogeneity and availability of resource is a important subject for dynamic peer-to-peer network. As an improvement, we also develop a dynamic resource registration method to achieve distributed loading and efficient discovery.

### 3.1 System Environment

The P2P-SIP multimedia conference network is formed by peers, and the logical conferencing overlay network is constructed. Each peer connects to other peer in the overlay and maintains the overlay routing information by the DHT. Some peers also have to provide the storage space to storage the index information which is assigned by the DHT.

Peers can share the resource to other peer in the overlay. It can be a role such as a P2P Focus or P2P Mixer in the multimedia conference network.
* Focus deals with the session initialization, management, and coordination of conferences. It does not require complex computing, but need to handle all of conference sessions.

* Mixer provides the functionalities of video and audio mixing for conferences. Moreover, it also handles the receiving and delivering of video and audio streams for all conference participants.

In the centralized system, powerful conference servers would be deployed. On the contrary, the capacity of each P2P-SIP peer is weak and heterogeneous. In P2P-SIP, a peer which has enough capability to be a Focus or Mixer has to register information to the overlay. When a User Agent want to make a conference, the resource discovery mechanism is used to find suitable resource and establish this session. Figure 1 illustrates an example that a caller makes a conference. (1) P2P conference servers, i.e., P2P Focus and P2P Mixer, register their information to the P2P overlay network. (2) When the caller wants to create a conference, he will discover the conference resource that provides the functionality of Focus and Mixer. (3) Based on the resource discovery mechanism, the suitable P2P Focus and P2P Mixer are selected. (4) Finally, the selected P2P Focus and P2P mixer handle the conference operations, such as conference initialization, release, media processing, etc.

<figure><img src="image_2.png" /><figcaption>Fig. 1. A P2P-SIP conference system.</figcaption></figure>

## 3.2 Resource Indexing

The capability of resources which are provided by peers change dynamically with the resource assignment or reconfiguration. If resource provider registers the index of current capability to the overlay, the caller might find the older resource index since the overlay information has not been updated rapidly. In order to avoid this problem,
the resource registration has to find and delete the last record. Therefore, it may involve high network overhead and long resource search time due to the dynamical available resource information.

Unlike the previous method, we define two class for resource capability, fixed attribute and dynamic attribute. Fixed attribute is the maximal capability of resource, and the dynamic attribute is available capability of resource. The all attributes show in Table 1.

<table><caption>**Table 1.** The attributes of service resource.</caption><thead><tr><th></th><th>P2P Focus</th><th>P2P Mixer</th></tr></thead><tbody><tr><th>Fixed attributes</th><td>Maximal connection capacity</td><td>1) Maximal mixing capacity, 2) maximal transport capacity, and 3) highest SVC-layer supporting</td></tr><tr><th>Dynamic attributes</th><td>Available connection capacity</td><td>1) Available mixing capacity, and 2) available transport capacity</td></tr></tbody></table>

Table 1 shows the attributes of P2P Focus and P2P Mixer. In our P2P-SIP conference service, each service has its service index, and builds a Constraint Tree by the fixed attribute. The Constraint Tree adopts the concept of range search. Using a tree-based data structure which called data partitioning tree, can divide the resource attribute into different segment. For example, the P2P Focus supposes that the system can provide maximal connection capacity to 12 connections, at least is 3 connections, and it can build a Constraint Tree as Fig. 2. In the Constraint Tree, each node is a index, called Node-Index. By the same way, Figure 3 is a Constraint Tree of P2P Mixer, it has three fixed attributes.

<figure><img src="image_3.png" /></figure>
<figure><img src="image_4.png" /><figcaption>Fig. 3. A Constraint Tree for P2P mixer.</figcaption></figure>

## 3.3 Resource Registration

If the peer in the overlay shares the resource to others, it has to register the index which includes service name, resource attributes, and the location information to the overlay network. In our system, we use DHT to maintain a structured overlay. Keys, correspondingly, play the role of indices of this database. We use "Hash(Service Name; Node Index)" as a key. Node Index, the fixed attribute which is provided by peer belong to leaf node in the Constraint Tree. For example, Hash(P2P Focus; 9) indicates that a P2P Focus can provide 9-connections resource to support conferences.

Unlike the traditional segment tree, when a peer receive the information belongs to it. If the peer is not the root of Constraint Tree, then it duplicates the information to its parent node. In this way, each node keeps the information of its children just as Fig. 4.
<figure><img src="image_5.png" /><figcaption>Fig. 4. The resource duplications of P2P Focus.</figcaption></figure>

## 3.4 Resource Search

In traditional P2P-SIP system, users create a conference through resource discovery because users are unaware of where the available conference resources are. Resource discovery in our approach can find the feasible conference resource to support the conference according to the Constraint Tree information.

First, each resource requester establishes a Constraint Tree according to the service type, P2P Focus or P2P Mixer. Second, resource requester finds the tree node on the constraints of resource requirements. For example, a caller want to make a conference with five participants, he has to look up a P2P Focus which can handle five connections at least. In the Constraint Tree, many tree nodes may satisfy the requirement, but the minimal tree nodes will be selected in order to minimize query messages. Third, the index of each selected tree node is converted into Resource-ID (key) by DHT. Resource requester stores the keys of the selected tree nodes to its register.

The resource requester selects s Resource-IDs (keys) from its register and send the Fetch messages to the s destinations in parallel. s is a parameter which is assigned by system or users. For example, it sends one Fetch message when s=1. If s is larger than the size of its register, all of the keys in the register will be selected, and then send to the s destinations with the Fetch messages in parallel. If the peer which receives the Fetch message has the enough available resource, it will reply a response message to the resource requester. The response message contains the k resources, such as the suitable k P2P Focuses.

Based on [0류! 참조 원본을 찾을 수 없습니다.], we propose a range query algorithm for conference resource discovery with Constraint Tree. According to [0류! 참조 원본을 찾을 수 없습니다.], the node [5,7] and node [8,12] can be
converted into Resource-IDs(keys), and then stored to the register. Figure 2 illustrates the Constraint Tree of a P2P Focus resource. If the requester wants to make a five-people conference, it sends Fetch messages to the selected tree nodes in the P2P Focus Constraint Tree. The selected tree nodes which are [5,7] and [8,12] in Fig. 2 can guarantee the P2P Focus of the responded keys can support the conference.

Figure 5 illustrates the data flow of resource discovery. The requester wants find a P2P Focus that can support five to seven connections. (1) The key is calculated with a Hash function. (2) Based on DHT mechanism which is Chord in our system, the Fetch message can be delivered to P2P Focus whose capacity is between five and seven. (3) The peer (tree node [5,7]) replies a response message include service (resource) description to the requester, i.e., the service descriptions of k P2P Focuses.

<figure><img src="image_6.png" /><figcaption>Fig. 5. The data flow of service discovery with P2P focus.</figcaption></figure>

The requester receives the response, and then contacts with the resource candidate immediately according to the result, or waits until all response messages are received. From the response results, if no peer can support the conference, the next s Resource-IDs (keys) from its register would be selected again. By the same way, the suitable peer would be looked up, finally. However, if the register is empty and no
suitable peer can be selected, it means that no peer can support the exacting
conference requirement.

4 System Operation

In this section, the flow diagram of a P2P-SIP conference setup is explained. Figure 6 illustrates the process of the call setup.

1. The caller has to set the conference profile before call setup.

2. Using our multi-constraint resource search algorithm, caller can find the available P2P Focus from the overlay network.

3. And then the caller sends a SIP-invite message which is a request for create a P2P-SIP conference to the Focus. At the meanwhile, the caller send a list which contains all the conference member by SDP [오휠! 참조 원본을 찾을 수 없습니다.] through the SIP-invite message according to RFC 5366 [오휠! 참조 원본을 찾을 수 없습니다.].

4. If Focus receives the request, it has to find members in the overlay according to the list in the SIP-invite message. And then it find the IP address of all members through the overlay which is create by DHT.

5. In addition, Focus has to search a suitable P2P Mixer using our mechanism from the overlay according to the conference profile.

6. When Focus finds a suitable Mixer, it send a SIP-invite message as the request to the Mixer.

7. If Mixer accepts the SIP-invite request, it response a 200 OK message to the Focus which contains the Media Mixing Level information by SDP.

8. After the above process, Focus send SIP-invite messages to all members. The messages include the information about Mixer.

9. All callees join the conference and establish the media streaming connection with Mixer according to the above information.
<figure><img src="image_7.png" /><figcaption>Fig. 6. The message sequence chart of a P2P-SIP conference setup.</figcaption></figure>
# 5 Simulation and Results

## 5.1 Simulation Environment

Our multi-constraint resource search algorithm based on RELOAD was implemented on Oversim [오류! 참조 원본을 찾을 수 없습니다., 오류! 참조 원본을 찾을 수 없습니다.]. Oversim is a P2P simulation framework which is based on OMNet++ [오류! 참조 원본을 찾을 수 없습니다.].

The heterogeneous P2P conference overlay network was simulated. There are 1000 nodes in our simulated overlay. We carried out the simulations on heterogeneous capacity scenarios. The resource density of P2P Focus is 20% in the overlay, and the P2P Mixer is same. But the two conditions are independent. For instance, a peer could be a P2P Focus and P2P Mixer simultaneously. And the DHT is the Chord using 160-bits SHA-1 to hash the key. Table 2 shows the distribution of resources which include the range and the attributes in the overlay. Assume each peer in the overlay creates h calls one hour, and then the conference arrival rate is 1000h.

<table><caption>Table 2. The resources of conference service.</caption><thead><tr><th>Node class</th><th>Attribute</th><th>Value</th><th>Random Distribution</th></tr></thead><tbody><tr><td>P2P focus</td><td>Maximal connection capacity</td><td>[3 50]</td><td>Uniform</td></tr><tr><td rowspan="3">P2P mixer</td><td>Maximal mixing capacity</td><td>[2 200]</td><td>Uniform</td></tr><tr><td>Maximal transport capacity</td><td>[1 50]</td><td>Uniform</td></tr><tr><td>highest SVC-layer supporting</td><td>[1 3]</td><td>Uniform</td></tr><tr><td>Peer</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>

<table><caption>Table 3. The conference profile.</caption><thead><tr><th>Attribute</th><th>Value</th></tr></thead><tbody><tr><td>Conference member</td><td>3 40 participants</td></tr><tr><td>Frame quality</td><td>1 3 layers</td></tr><tr><td>Session time</td><td>60 180 minutes</td></tr></tbody></table>

<table><caption>Table 4. The resource profile of P2P mixer.</caption><thead><tr><th>Resolution</th><th>Frame rate (frames/sec)</th><th>Quality</th><th>Bitrate (Mbps)</th><th>Occupied mixing resource</th></tr></thead><tbody><tr><td rowspan="3">352x240</td><td rowspan="3">6.25</td><td>1</td><td>0.4</td><td>1</td></tr><tr><td>2</td><td>0.75</td><td>2</td></tr><tr><td>3</td><td>1.2</td><td>4</td></tr></tbody></table>
We randomly generate a Conference Profile as a call. The different Conference Profile maps to the different value of resource. Table 3 and Table 4 show Conference Profile and Resource Profile Mapping, respectively. In Table 4, Bitrate is the requirement of transport capacity and Mixing is the requirement of Mixing capacity. The levels of Quality are defined from Bitrate and Mixing. It can provide more higher quality frame when the resources in overlay achieve the requirement. We discover the resources in the Resource Profile to setup the conference using our mechanism.

We simulate 12 hours and there are three phases in our simulation. It builds the overlay network topology in the initial phase. The transition phase begins to simulate the behavior of P2P-SIP conference. Finally, the measurement phase simulates the behavior of the call and measures the simulation data simultaneously.

## 5.2 Simulation Results and Comparison

We implement the multi-constrain search algorithm by the P2P simulator and compare with other designs. One is ReDiR-based mechanism, which is described in section 3. We preserve the original design of [오류! 참조 원본을 찾을 수 없습니다.], and then we add the capacity of service information due to [오류! 참조 원본을 찾을 수 없습니다.] has not the issue about capacity. It can discover the resource using its Node-ID, and then filter the resource that cannot achieve the requirement of the call. Another one is Fixed-Partition that distributes all the resources to fixed nodes. The fixed node is similar to index server in client/server architecture. The two designs also use Table 3 and Table 4 as its conference profile.

The caller finds the suitable resources with search algorithm. If the peer has enough capacity to satisfy the caller, it responds its IP address and port number to the caller. The caller will pick the most satisfied one to send SIP-invite message. Figure 7 illustrates the related performance. The definition of *s* is described in section 3.4. The split means how many index nodes the method of Fixed Partition has. Furthermore, the data structure tree is a binary tree when branch=2.

In Fig. 7, we can see that our algorithm have high probability with one hit. Especially the method with *s*=parallel which means the caller can get many resource responses than *s*=1. As increasing the utilization of resource, the hit rate will be lower because there is no accurately way to find available resource in the distributed system. On the contrary, we use the Constraint Tree to prior capacity as a classification. Although the available resource decreases, we still can find the resource we need quickly unless there are no resources in the overlay.
<figure><img src="image_8.png" /><figcaption>**Fig. 7.** The hit ratio in one step.</figcaption></figure>

In Fig.8, the average search steps for finding a suitable resource is lower than other designs. It is related with the call setup time. This is because, our algorithm can avoid unnecessary search by the Constraint Tree. Even though the resources are serious shortage, we can use the range search to increase our efficiency.

<figure><img src="image_9.png" /><figcaption>**Fig. 8.** The average search steps for looking a suitable resource up.</figcaption></figure>
# 6 Conclusion

In this paper, we proposed a multi-constraint resource search algorithm for P2P-SIP conference. According to the multi-constraint resource search algorithm, not only the hit ratio of P2P usable resource would be improved, but also the overall conference setup time would be reduced. The simulation shows that our proposed method has high efficiency for resource search. Comparing with other algorithms, the efficiency of P2P-conference resource search can be improved. Even if the conference arrival rate is increasing, it can also find the suitable resource efficiently. Additionally, our mechanism also has good flexibility; it can be extended to other structured peer-to-peer systems, such as Pastry, CAN, etc.

# Acknowledgment

We would like to thank the National Science Council (NSC) in Taiwan. This research was supported in part by the NSC under the grant number NSC100-2221-E-150-077.

# References

1. Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., Schulzrinne, H.: REsource LOcation And Discovery (RELOAD) Base Protocol. draft-ietf-p2psip-base-08.txt (2010)

2. Oredope, A., Liotta, A., Roper, I., Morphett, J.: Peer-to-peer session initiation protocol in highly volatile environments. In: Next Generation Mobile Applications, Services and Technologies, 2008 (NGMAST '08). (16-19 2008) 76–82

3. Baumgart, I.: P2pns: A secure distributed name service for p2psip. In: Pervasive Computing and Communications, 2008. PerCom 2008. Sixth Annual IEEE International Conference on. (march 2008) 480–485

4. J. Rosenberg: A framework for conferencing with the session initiation protocol (SIP). RFC 4353 (2006)

5. Johnston, A., Levin, O.: Session Initiation Protocol (SIP) Call Control - Conferencing for User Agents. RFC 4579 (2006)

6. Mahy, R., Sparks, R., Rosenberg, J., Petrie, D., Johnston, A.: A Call Control and Multi-Party Usage Framework for the Session Initiation Protocol (SIP). RFC 5850 (May 2010)

7. Maenpaa, J., Camarillo, G.: Service Discovery Usage for REsource LOcation and Discovery (RELOAD). draft-ietf-p2psip-service-discovery-05.txt (2012)

8. Lv, Q., Cao, P., Cohen, E., Li, K., Shenker, S.: Search and replication in unstructured peer-to-peer networks. In: Proceedings of the 16th international conference on Supercomputing. ICS '02, New York, NY, USA, ACM (2002) 84–95

9. Buford, J., Wang, A., Hei, X., Liu, Y., Ross, K.: Discovery of in-band streaming services in peer-to-peer overlays. In: Global Telecommunications Conference, 2007. GLOBECOM '07. IEEE. (nov. 2007) 242–247

10. Zheng, C., Shen, G., Li, S., Shenker, S.: Distributed segment tree: Support range query and cover query over dht. In: Proceedings of the Fifth International Workshop on Peer-to-Peer Systems (IPTPS). (2 2006)
11. Handley, M., Jacobson, V., Perkins, C.: SDP: Session Description Protocol. RFC 4566 (2006)

12. Camarillo, G., Johnston, A.: Conference Establishment Using Request-Contained Lists in the Session Initiation Protocol (SIP). RFC 5366 (2008)

13. The OverSim P2P Simulator: http://www.oversim.org/

14. Baumgart, I., Heep, B., Krause, S.: Oversim: A flexible overlay network simulation framework. In: 2007 IEEE Global Internet Symposium. (11-11 2007) 79–84

15. The OMNeT++ Network Simulation Framework: http://www.omnetpp.org/