Centralized and distributed architectures of scalable video conferencing services

Tien Anh Le, Hang Nguyen

Abstract-The Multipoint Control Unit-based centralized architecture and Application Layer Multicast-based distributed architecture are mainly used for data distribution in video conferencing services. With the contribution of Scalable Video Coding, the latest extension of Advanced Video Coding, video conferencing services are being further researched to support terminals' scalability. The main contribution of this research is to answer a fundamental question before a video conferencing service can actually been designed: which service architecture is more suitable for a SVC-based video conferencing service and in which condition? In order to do that, a framework for evaluating SVC-based video conferencing service has been built; intensive simulation results have been also obtained from simulation scenarios which have been designed from the analysis models of the two scalable video conferencing service architectures. The obtained results show that, with a much higher capacity of the MCU, the MCU-based architecture can only guarantee an almost similar video quality with the ALM-based architecture at a trade-off of at least three times higher end-to-end delay.

Index Terms-Scalable video coding; video evaluation platform; video conference; service architecture;

I. Introduction

Nowadays, multimedia conferencing services are becoming an essential part in both our business and everyday activities. They can save us a lot of time and resource in comparison with the traditional face-to-face meetings. However, in order to fully replace the conventional end-to-end meeting methods, multimedia conferencing services have to provide their users the highest possible quality of experience and a very flexible connectivity to the conferencing service platform. Among the multimedia flows that build up a multimedia conferencing service, video is the most important as well as the most difficult medium that the multimedia conferencing service has to distribute to its participating users (e.g. multimedia conferencing services are usually called video conference). The video medium is apparently very important because it contributes the most to the users' quality of experience and transfers most of the conference information to participants. It is difficult to be distributed because the video stream is always the most heavy stream in the multimedia flow, so it is very difficult to transport the video stream to all users without a serious quality decrement and a heavy network congestion. People are using different kinds of terminals to access to the multimedia conferencing service. These terminals are different in their computational capacities, screen resolutions, and communication bandwidths. However, many service providers are still providing their multimedia services based on single layer video coding (such as JPEG2000, Advance Video Coding (AVC)...). A fatal limitation of the single layer video coding is that it is not scalable enough for multimedia services. Once a source video stream has been encoded with AVC, that encoded bit-stream will remain the same throughout the communication process. Encoding parameters of the encoded bit-stream (such as bit-rate, frame-rate, screen size, SNR...) will be determined at the beginning of the communication session by senders and receivers (mostly by receivers), so it is impossible to change the encoding parameters without using a trans-coder and/or a trans-rater. A much more flexible solution is to use Scalable Video Coding (SVC). SVC has been standardized as an extension of the AVC standard since 2007 [START_REF] Schwarz | Overview of the scalable video coding extension of the H. 264/AVC standard[END_REF]. The main idea of this extension is to apply multi-layer coding into the AVC codec. SVC encodes an input video stream into a multi-layer output bit-stream comprising of a base layer and several enhancement layers. Within those layers, the base-layer is encoded with a basic quality to guarantee that it can be consumed by the weakest receiver of the entire communication group. For the purpose of backward compatibility, the base-layer must be recognized by all conventional H.264 decoders. Enhancement layers, when received at the receivers together with the base-layer, can enhance the overall-quality of the bit-stream. Especially, when all enhancement layers are received in-order at the receiver together with the base layer, the bit-stream will achieve its original encoded quality. However, when real conditions (such as bandwidths, delays, or displaying screen sizes) do not allow, upper layers can be discarded along the transmission link or at any middle box (relaying entities) for the bit-stream to be fit-in with those conditions without corrupting the video communication session. Another issue for multimedia conferencing services is how we can effectively distribute the video bit-stream from its source to many other participants. Most commercial video conferencing services are now using Multipoint Control Unit (MCU) for mixing and distributing video bit-streams to all participants in the conferencing session. When a MCU is used, this middle-box collects video streams from all participating users of the conferencing session. It then mixes all of these incoming streams, making necessary trans-codings or trans-ratings before sending back the mixed streams to all participating users. This process may cause delays, a single point of failure and bottleneck for the entire communication session. Regarding multicast mechanisms, IP-Multicast [START_REF] Deering | Multicast routing in datagram internetworks and extended LANs[END_REF] is the first attempt to address this problem. However, many deploying problems are still preventing IP-Multicast from being supported worldwide [START_REF] Diot | Deployment issues for the IP multicast service and architecture[END_REF]. An alternative solution is Application Level Multicast(ALM). The key concept of ALM is the implementation of multicasting functionality as an application service instead of a network service. It has excellent advantages over IP-Multicast: easier and possibly immediate deployment over the Internet without any modification of the current infrastructure and adaptable to a specific application. In order to evaluate the video conferencing services, designers and researchers are really in-need of an evaluation tool for video transmission which is specially tailored for the evaluation of SVC-based video conferencing service. Since most of the current video conferencing systems are now using the MCU-based centralized architecture or ALM-based distributed architecture to provide their conferencing service, an evaluation platform for these two scalable video conferencing services is required. In [START_REF] Detti | SVEF: an opensource experimental evaluation framework[END_REF], an early attempt was made to evaluate the SVC transmission. However, it used an all-in-one solution which is incompatible to H.264/AVC evaluation platforms. It has not fully supported the extended NALUs. As a result, it couldn't support Sub-sequence Parameter Set (NALU 15). This NALU is very important since it contains decoding information for a sequence of NALUs. If this NALU is dropped along the transmission, many SVC frames will be effected and though cannot be decoded. Last but not least, it cannot provide any interface to popular simulation platforms (NS-2 or OverSim), so that it can only be used in field tests but not in theoretical analysis. So far, the research community depends on EvalSVC [START_REF] Le | EvalSVC -an evaluation platform for scalable video coding transmission[END_REF] for measuring the objective QoS-related parameters of the underlay networks (such as loss-rate, delays, jitters...), as well as evaluating both the subjective (using Mean Opinion Score -MOS) and objective (Peak Signal to Noise Ratio -PSNR) video quality metrics. EvalSVC has supported up to latest extensions of the SVC codec. The main contribution of this research is to form a many-tomany simulation platform for video conferencing service architectures using the NS-2 interface of EvalSVC. Then, both the centralized MCU-based and ALM-based service architectures of the SVC-based video conferencing service will be measured and evaluated for the SNR scalability by using the EvalSVC platform. Analysis will be made on the obtained results.

II. Evaluation of Scalable Video Coding transmissions

In [START_REF] Le | EvalSVC -an evaluation platform for scalable video coding transmission[END_REF], the evaluating problems of Scalable Video Coding transmissions was first addressed and solved by using the EvalSVC platform. The most difficult problem is that the full SVC's Network Abstraction Layer Unit (NALU) extensions haven't been fully defined and standardized. However, it should be noticed that, the basic NALU extension types (e.g., types 14, 15, 20) have been spared for SVC extensions from the AVC NALU types. [START_REF] Wenger | RTP payload format for SVC video[END_REF], are out of EvalSVC's scope. Among the three basic NALU extension types, NAL unit type 14 is used as a prefix NAL unit, NAL unit type 15 is used for subset sequence parameter set, and NAL unit type 20 is used for coded slice in scalable extension. NAL unit types 14 and 20 indicate the presence of three additional octets in the NAL unit header. NALU types 15 contents header information which is not necessary to be repeatedly transmitted for each sequence of of picture [START_REF] Wang | System and transport interface of SVC[END_REF]. This subsequence parameter set can be transmitted on an "out-ofband" transmission for error resilience. We will need this information about the NALU types when we reconstruct the possibly corrupted SVC bit-stream at the receiver side. PRID (priority ID) specifies a priority identifier for the NALU. A lower PRID indicates a higher priority. DID (dependence ID) indicates the inter-layer coding level of a layer representation. QID (quality ID) indicates the quality level of an MGS layer representation. TID (temporal ID) indicates the temporal level of a layer representation. Based on these IDs, we can choose to drop all packets of the same enhancement layer(s) according to a chosen scalability (whether it is quality, temporal, spatial or combined scalability). Fig. 1 illustrates main components of our EvalSVC platform.

Basically there are three available metrics which can be used to evaluate the performance of the scalable video coding bit-stream. These three metrics can be further divided into subjective and objective quality measures. The most popular objective metric is peak signal-to-noise ratio (PSNR). PSNR can be used to assess the resulting video quality by calculating the Mean-square Error between the original raw video bit-stream before the encoding process at the input and the possibly corrupted received video bitstream at the output, frame-by-frame. Normally, the luminance component of the video is used in PSNR comparison since it is the most important component of a video frame.

Y -P SN R(s, d) = 20 log 10 V peak M SE(s, d) [dB] M SE(s, d) = 1 N col N row N col i=0 Nrow j=0 [Y S (n, i, j) -Y D (n, i, j)] 2
In which:

• V peak = 2 k
-1 • k=number of bits per pixel (luminance component) SSIM is another objective metric for measuring the similarity between two images [START_REF] Wang | Image quality assessment: From error visibility to structural similarity[END_REF]. It was designed to improve on traditional methods like peak signal-to-noise ratio (PSNR) and mean squared error (MSE), which have proved to be inconsistent with human eye perception. The SSIM metric is calculated on various windows of an image. The measure between two windows x and y of common size MxN is:

SSIM (x, y) = (2µ x µ x + c 1 )(2σ xy + c 2 ) (µ 2 x + µ 2 y + c 1 )(σ 2 x + σ 2 y + c 2 ) (1)
In which:

• µ x , µ y are the mean values of x and y,

• σ 2 x , σ 2 y are the variance values of x and y, • σ xy is the covariance of x and y, • c 1 , c 2 are two variables to stabilize the division with weak denominator; For subjective measurement, Mean Opinion Score (MOS) is used, which scales the human quality impression on the video from bad (0) to excellent [START_REF] Le | EvalSVC -an evaluation platform for scalable video coding transmission[END_REF]. There is also a convert table between PSNR and MOS values [START_REF] Rec | Methods for subjective determination of transmission quality[END_REF].

All of the three metrics are used in EvalSVC as the main measures to evaluate the SVC transmissions. OverSim [START_REF] Baumgart | OverSim: A flexible overlay network simulation framework[END_REF] is an simulation platform for overlay networks. In comparison to NS-2, it can provide better peer-to-peer and overlay simulation features. We can easily simulate application layer multicast algorithms (such as NICE, Narada...) with an almost unlimited number of peers within a multicasting group. In [START_REF] Le | Scalable video transmission on overlay networks[END_REF], an interface between the EvalSVC platform and the multicast simulations using OverSim has been developed. Together with the NS-2 interface which has been already integrated, the entire EvalSVC platform can provide necessary simulation evaluations for the comparison between SVC-based video conferencing service architectures.

III. Video conferencing service architectures

The multimedia conferencing services are mainly composed of a media distribution plan and a signaling plan [START_REF] Firestone | Voice and video conferencing fundamentals[END_REF]. In this research, we concentrate on the media distribution plan of the conferencing service in which the evaluation of video distribution architecture is in focus.

In Fig. 2, a centralized video conferencing service architecture using MCU is demonstrated. MCU is a central device which has a larger bandwidth connection and more powerful computation capacity than others. The MCU collects video bit-streams from all participants, mix them into a common video frame (the active speaker's video occupies a big part of that common frame, other participants' videos can be displayed as small thumbnails around that big video) and send back to all participants. In a SVCbased video conference service architecture, participants can encode their video using Scalable Video Coding before sending them to the MCU. In order to support those incoming SVC bit-streams, a Scalable Video Conferencing Server (SVCS) was proposed to replace the conventional MCU in [START_REF] Eleftheriadis Alexandros | Multipoint videoconferencing with scalable video coding[END_REF]. The SVCS collects SVC bit-streams from all participants. It can choose to discard enhancement layers to save its bandwidth and computational capacity. Then, the received bit-streams will be decoded and then mixed together to form a common video frame. That video frame will be encoded again using a SVC encoder. The output SVC bit-stream, comprising of a base layer and enhancement layer(s), is then sent to all other participants. The distributed video conferencing service architecture is shown in Fig. 3. In this architecture, each participant is also armed with a SVC encoder. All participants form an application layer multicast (ALM) tree to distribute their SVC bit-stream to the rest of the conference. The ALM algorithm has considered various conditions of the participants' terminals (such as bandwidth, delay, capacity, etc.) before building the multicast tree. As a result, the participant having a higher capacity will more likely become a forwarder who is capable of relaying the SVC bit-streams to another participant, dropping enhancement layers when necessary in order to meet the overall requirements of the conference session. The main difference between the centralized and distributed architectures from the user's point of view is that instead of receiving only one video stream, each terminal will receive video streams from all other participants. It then has the full control whether it wants to receive a video bit-stream from a particular participant or not. Since the video bit-streams are SVC-based, participants also have the right to discard enhancement layers if they find that they are not capable of receiving all layers. So basically, the participants will have the full control on how many video bit-streams and how many layers they want to receive depending on their preferences and capacities. Each conferencing service architecture has its own advantages and disadvantages. The MCU-based centralized architecture may provide a lower network load but with a higher delay and a decrease in video quality. The ALMbased distributed architecture can provide more flexible receiving options with possibly higher video quality. However, the ALM may cause delay and more traffic load on the network. We compare the performance and quality of SVC-based video conference service architectures using simulations and our EvalSVC platform.

We set up a simulation plan of a video conferencing service serving 16 participants simultaneously over the Internet. Two simulation scenarios are built reflecting the centralized and distributed architectures.

A. MCU-based centralized video conferencing service architecture

The NS-2 interface of EvalSVC is used to build and evaluate the first simulation scenario. In this scenario, the participating users connect to the MCU server using a simulated network topology generated by GT-ITM. The topology generated by GT-ITM emulate the real network environment on the Internet using a hierarchical transitstub configuration of 1250 nodes and about 6000 physical links [START_REF] Zegura | How to model an internetwork[END_REF]. Each physical link will have random values of delay, bandwidth, and Packet Error Rate (PER). Each participating user connects to the network using a DSL access interface. The MCU uses a higher bandwidth and lower delay interface to connect to the network. Each participating user sends the same sample video of 1065 frames to the MCU. At the MCU, we prepare in advance a composite SVC video of 1065 frames as if it is mixed and encoded by the MCU after receiving 16 video streams from all 16 participating users. As soon as the MCU receives packages from all participating users, it will send the corresponding video frame of the prepared composite video back to all participants. The MCU uses a 10 Mbps access connection to receive and transmit video bit-streams. By using this two-step scenario, we can emulate the MCU's operations.

The performance evaluation is also two-fold. In Fig. 4a, 16 SVC bit-streams are sent from participants to the MCU via different channels. The MCU will receive 16 possibly corrupted SVC bit-streams. The mixer composes all corrupted SVC bit-streams to make a composite SVC bitstream and send back to all participants. Each participant will receive a composite SVC bit-stream. Of course this composite SVC bit-stream may be double-corrupted due to the quality of the channel. Since the evaluation metrics such as PSNR and SSIM are frame-based (e.g. the source and corrupted bit-streams must be identical in order for the evaluator to give out a reasonable result), an analysis simulation model is shown in Fig. 4b. We assume that the video composition process is loss-less, so we can replace the transmission of 16 separated SVC bit-streams to the MCU by the transmission of a single loss-less composite SVC bit-stream. Afterward, the simulation and analysis models use an identical process to transmit the corrupted SVC bit-stream from the MCU back to the participants. The overall simulation scenario for the MCU-based centralized video conferencing service architecture is as follow. Firstly, 16 raw videos from 16 participants compose a lossless composite raw video. Next, 16 raw videos are encoded by a SVC encoder at each participant and then separately sent over the channel to the MCU. The MCU will decode 16 possibly corrupted SVC bit-streams, and then form the corrupted raw composite video. That raw video will then be encoded again using a SVC encoder and then sent back to participants. Each participant will receive a doublecorrupted SVC bit-stream, and then decode it to obtain a double-corrupted raw video. This video is compared to the loss-less raw video composed at the beginning of the process to evaluate its PSNR and SSIM. In this scenario, we use the NS-2 interface of the EvalSVC framework to build our simulation.

B. ALM-based distributed video conferencing service architecture

The simulation scenario for the ALM-based distributed video conferencing service architecture is in fact quite straight forward. We use NICE [START_REF] Banerjee | Scalable application layer multicast[END_REF], a popular ALM algorithm to multicast the SVC bit-streams from each participant to all others. NICE only uses a delay-type cost function to build and to maintain its ALM tree (with a clustering, layering structure). By sending and receiving periodic heartbeat messages containing delays between nodes within a cluster, peers will decide whether it should elect a new cluster-leader. Changing cluster-leaders provokes changing and rebuilding the entire NICE tree. The underlay network topology is identical with the one used in the MCU-based centralized scenario. In this scenario, all peers will join together to form an overlay. By comparing distances among peers, a media distributing tree is built to multicast the SVC bit-stream. In this case, the bitstream will not be sent directly, it may be relayed by forwarder(s) along the media distributing tree before reaching its final destination. According to the network conditions, enhancement layers can be dropped at the forwarder(s) in order to maintain the continuity of the video communication session. Participating nodes use a 1 Mbps connection to transmit, forward and receive video bit-streams. Afterward, each participant will receive SVC bit-streams from all members of the conference session. Since evaluation metrics such as PSNR and SSIM are only comparing identical bit-streams, in order to evaluate the performance between the distributed and centralized video conferencing service architectures, an analysis model as the one shown in Fig. 5 is used. Video bit-streams are composed at senders before transmitting to the ALM network to prepare a lossless composite video for later evaluation. At each receiving node, all bit-streams are decoded and then composed to make a possibly corrupted composite video. The corrupted bit-stream will be compared with the original composite bit-stream for PSNR and SSIM. In this scenario, we use the Oversim interface of the EvalSVC framework to build our simulation.

IV. Simulation result

The results are shown in Fig. 6 and Fig. 7. These results compare the average quality of the received video bitstreams in two architectures using PSNR and SSIM. SNR scalability is used to encode the video bit-streams since it is the best error-resistance SVC type [START_REF] Le | EvalSVC -an evaluation platform for scalable video coding transmission[END_REF]. We can see that, with a much higher capacity MCU, the centralized architecture can provide an almost similar video quality with the distributed architecture. More specifically, the direction from nodes to the MCU (uplink) has a small end-to-end delay but the direction from the MCU to nodes (downlink) has a very high delay leading to its very high end-to-end delay. In this result, a very big delay created by the mixing, encoding/decoding processes at the MCU has not been considered. Therefore, the real end-to-end delay of the MCU-based architecture should be much higher. In this case, a very high price is required if we want to keep the end-to-end delay of the MCU-based scalable video conferencing service architecture below a recommended threshold of 200 ms [START_REF] Itu-T | [END_REF]. Even though a 10 times higher bandwidth and about 16 times higher computational capacity have been applied at the MCU (when all participating peers is having a similar bandwidth and computational capacity with the ALMbased scenario), it can only guarantee a slightly higher quality of the received videos with the trade-off of a very high end-to-end delay in comparison with the ALM-based architecture.

V. Conclusion and future work

In this paper, we have succeeded in comparing the performance and quality of the centralized, MCU-based and distributed, ALM-based scalable video conferencing architectures. Intensive simulation scenarios have been built based on the EvalSVC, a scalable video coding evaluation framework and its interfaces to NS-2 and OverSim simulation tools. The obtained results have shown that, when 10 times higher bandwidth, approximately 16 times higher computational capacity, and similar participants' capacities are applied, the MCU-based architecture may obtain a slightly higher average video quality at participants. However, a very high queuing with a high packet dropping rate at the MCU show a highly potential single point of failure in the network. Especially when the number of participants increases into hundreds or even thousands, the ALMbased architecture is foreseen to out-perform the MCUbased architecture. A very serious problem of the MCUbased architecture is that its end-to-end delay is about 3 times higher than the ALM-based architecture even without considering the very high delay of the mixing, encoding/decoding process at the MCU. Based on the result and simulation scenario obtained from this research, theoretical analysis can be built to provide a more solid background on the performance of the centralized MCU-based scalable video conferencing services.

Fig. 1 .

 1 Fig. 1. EvalSVC's diagram[5].

Fig. 2 .

 2 Fig. 2. Centralized video conferencing architecture.

Fig. 3 .

 3 Fig. 3. Distributed video conferencing architecture.

Fig. 4 .

 4 Fig. 4. MCU-based centralized video conferencing simulation scenario.

Fig. 5 .

 5 Fig. 5. ALM-based distributed analysis scenario.

Fig. 6 .

 6 Fig. 6. Y-PSNR comparison of MCU-based and ALM-based scalable video conferencing service with SNR SVC encoding method.

Fig. 7 .

 7 Fig. 7. SSIM comparison of MCU-based and ALM-based scalable video conferencing service with SNR SVC encoding method.

TABLE I

 I Average end-to-end delay [s].TableIshows the average end-to-end delay comparison between the MCU-based and ALM-based service architectures. It is clear that, from both packet level and frame level, the MCU-based architecture has almost three times the end-to-end delay than the ALM-based architecture.

	Types	Uplink	Downlink MCU e2e ALM e2e
	Packet 0.0327191 0.232448	0.265167	0.09171
	Frame 0.0328203 0.256979	0.289799 0.108484


Tien Anh Le

Hang Nguyen

Hongguang Zhang

Multi-variable cost function for Application Layer Multicast routing

Keywords: application layer multicast routing, cost function, resource allocation, traffic control, end-to-end QoS routing

Cost function is an essential part in Application Layer Multicast (ALM) routing algorithms. It is from a cost function that we can calculate links' costs and then build the data delivery tree for multicasting. Unfortunately, cost function remains an almost untouched research area in ALM routing. In this research, we propose a new multi-variable cost function considering various end-to-end QoS parameters simultaneously. The mathematical derivation process is also described in details so that one can apply it to obtain other multi-variable cost functions according to their specific requirements. The newly proposed multi-variable cost function can avoid congestion before it happens, preventing the data delivery tree from being frequently or unnecessarily changed while still be adaptable to the dynamic requirements of different applications. With theoretical analysis, we have proved that the new cost function can provide better performance for ALM routing algorithms compared to conventional cost functions.

I. Introduction

The Internet was originally built for unicast or one-toone applications. Nowadays, it has to serve a large number of multimedia services such as multimedia conference. These types of multicast services put a big load on the unicast infrastructure of the Internet. IP-Multicast [START_REF] Deering | Multicast routing in datagram internetworks and extended LANs[END_REF] is the first attempt to solve this problem. It is so far the most efficient multicast mechanism to deliver the data over each link of the network only once. However, many deploying problems are still preventing IP-Multicast from being supported worldwide [START_REF] Diot | Deployment issues for the IP multicast service and architecture[END_REF]. An alternative solution is Application Level Multicast(ALM). The key concept of ALM is the implementation of multicasting functionality as an application service instead of a network service. It has excellent advantages over IP-Multicast: easier and possibly immediate deployment over the Internet without any modification of the current infrastructure and adaptable to a specific application. In a tree-push ALM, a data distribution tree is built first, then the data is actively distributed from the source node to intermediate peers until reaching all peers in the multicast tree [START_REF] Hosseini | A survey of application-layer multicast protocols[END_REF]. In order to build an ALM distribution tree, we must have costs of all available endto-end links. Those costs can only be calculated by using a cost function. The main contribution of this research is to design a new multi-variable cost function of the end-to-end delay and bandwidth taking into account advantages of application layer links. We also propose in details the mathematical derivation process of the new multi-variable cost function and analyze its performance. This analysis and derivation process can be further applied to find other forms of cost functions with other QoS parameters. A theoretical anal-ysis will also be performed to compare the newly found cost function with conventional ones. The new cost function is capable of preventing congestion on each link before it occurs by assigning higher costs to nearly-overloaded end-to-end links. The new cost function also considers the dynamic characteristics of end-to-end links of the overlay environment. The rest of the paper is organized as follows. Section II provides a survey on the state-of-the-art cost functions and analyzes their limitations. The proposed multi-variable cost function will be described and derived in section III. By theoretical analysis, we will compare the new multivariable cost function with conventional ones to show its advantages in section IV. Finally, we conclude and give out some possible future works in Section V.

II. Conventional cost functions

Conventional cost functions are either empirical or heuristic. Among all available cost functions for ALM routing that we have found, none of them has a mathematical derivation nor a clear citation. In most of the ALM routing algorithms, the state of the network, on which the routing algorithm is presented, readily associates some costs with each link. Thus they do not address how the link cost function should be defined so as to efficiently distribute allocated resources over the network [START_REF] Matta | On routing real-time multicast connections[END_REF]. Also in [START_REF] Matta | On routing real-time multicast connections[END_REF], several kinds of cost functions have been investigated.

LinkCost = RsvBw + ReqBw LinkCap (1)
In which:

• RsvBw: The amount of bandwidth currently in use by existing connections,

• ReqBw: The amount of bandwidth requested by the newly arriving group,

• LinkCap: Total bandwidth of the link. The main idea of using the cost function ( 1) is to choose a tree that is least-loaded and at the same time, to minimize the total amount of bandwidth to be consumed by the new connection.

LinkCost = 1 + RsvBw LinkCap (2)
The main idea of using the cost function of (2) (a variation of (1)) is that hop count, a static link metric, plays a dominant role in the link cost.

LinkCost = 1 LinkCap -(RsvBw + ReqBw) (3)
In (3), the cost increases exponentially with the utilization of the link. According to [START_REF] Matta | On routing real-time multicast connections[END_REF], (3) appears more attractive than (1) and (2) because it can better distribute the load over the network by avoiding the use of highly loaded links, and thus links don't likely become saturated for future connections. Furthermore, it gives preference to shorter paths (with less number of link) as long as links are not heavily loaded.

In [START_REF] Lorenz | Optimal partition of QoS requirements for many-to-many connections[END_REF], the cost function ( 4) was used because it has many desirable practical characteristics. It decreases with the delay, it is convex, it assigns infinitely high cost when the required delay guarantee approaches zero, and a fixed minimal link usage cost C l , even if no guarantee is required. The constant θ determines how fast the cost grows for low delays and the constant A l is used as a scaling constant.

C l (d) = A l d θ (4)
In [START_REF] Lorenz | Optimal partition of QoS requirements on unicast paths and multicast trees[END_REF], the cost function on each link is calculated by ( 5)

c i (x) = κ i x -κ i , if x > κ i ∞ , if x ≤ κ i (5)
In which:

• κ i : Minimal delay that can be guaranteed on link i when utilizing all of its available resources,

• x i : Requested delay of the new connection. Although delay is used as a sample, any other QoS parameter such as bandwidth, jitter, packet loss can be used. However, the heuristics function ( 5) is only single-variable, therefore it cannot consider other parameters simultaneously. Another cost function [START_REF] Lorenz | Optimal partition of QoS requirements on unicast paths and multicast trees[END_REF] considering several QoS parameters has been used in [START_REF] Widyono | The design and evaluation of routing algorithms for real-time channels[END_REF], again, without any mathematical proof.

C(β, δ, ψ) = δ + K 1 β + K 2 .e K 3 ψ (6)
In which:

• β: Residual bandwidth,

• δ: Residual buffer space,

• ψ: Estimated delay bound. The scaling factor K i allows us to modulate the relationship between β, δ, ψ even further, although it is still unclear how bandwidth, buffer, and delay units could be added exactly together [START_REF] Widyono | The design and evaluation of routing algorithms for real-time channels[END_REF], [START_REF] Bueno | Multicast extension of unicast charging for qos services[END_REF]. In [START_REF] Tien | Toward building an efficient application layer multicast tree[END_REF], a single-variable cost function has been derived and its performance has been simulated under real conditions. The results have shown that, the single-variable cost function can only build a good multicast tree in certain conditions. A multi-variable cost function is highly demanded to build a more reliable multicast tree. From the best of our knowledge, conventional cost functions are mainly applied in network-layer routing. Our work has been one of the pioneers who have made full investigations on application layer multicast routing considering both network conditions and application's requirements.

III. Proposed multi-variable cost function

QoS parameters can be either bandwidth-type (meaning that the requested bandwidth is always smaller than or equal to the maximum available bandwidth) or delay-type (meaning that the requested delay is always greater than or equal to the minimum available delay).

A. Problem formation

Problem: Find a multi-variable cost function which can simultaneously consider varied bandwidth and delay requests from the application and maximum guaranteed resources from the underlay network. The cost function must be able to assign increasingly higher costs for nearlysaturated end-to-end links to prevent congestion.

B. Lemma 1: Bandwidth-type cost function

Assume we have on the end-to-end link i : A total available bandwidth of κ w , and a requested bandwidth of x w , we must find the bandwidth-type cost function: f (x w ). Since κ w is the maximum available bandwidth when using all available resources on link i, so 0 ≤ x w ≤ κ w . With time, according to the application's requirements, x w may be varied by an amount of ∆x w causing the cost to have the current value of f (x w + ∆x w ), so this current value of the cost function depends on:

• The previous cost: f (x w ),

• The increment of cost which is proportional to: -The previous cost: f (x w ), -The ratio between the increment of requested bandwidth and the total requested bandwidth: ∆xw xw+∆xw , • The decrement of cost which is proportional to: -The ratio between the decrement of the remaining available bandwidth and the maximum available bandwidth (κw-xw-∆xw) κw . Finally, we have:

f (x w + ∆x w ) = f (x w ).     1 + ∆x w x w + ∆x w (κ w -x w -∆x w ) κ w     (7)
From [START_REF] Widyono | The design and evaluation of routing algorithms for real-time channels[END_REF] we have:

lim ∆xw→0 f (x w + ∆x w ) -f (x w ) ∆x w = lim ∆xw→0 f (x w ) κ w (x w + ∆x w ) . 1 (κ w -x w -∆x w ) ⇔ f ′ (x w ) = f (x w ). κ w x w (κ w -x w ) (8)
Replacing f (x w ) by y and f ′ (x w ) by dy dxw ; from [START_REF] Bueno | Multicast extension of unicast charging for qos services[END_REF] we have an ordinary differential equation:

dy dx w = y κ w x w (κ w -x w ) (9)
Solve the ordinary differential equation ( 9), we find the bandwidth-type cost function:

dy y = κ w x w (κ w -x w ) dx w ⇔ dy y = κ w x w (κ w -x w ) dx w x w + (κ w -x w ) x w (κ w -x w ) dx w = - d(κ w -x w ) κ w -x w + dx w x w ⇔ ln(y) = ln(x w ) -ln(κ w -x w ) + c ⇔ y = Φ.x w (κ w -x w ) (10)

C. Lemma 2: Delay-type cost function

We can see that, the required delay parameter (x d ) has a reversed characteristic against the required bandwidth parameter (x w ). So by replacing ẋd = 1

x d , κd = 1 κ d , and

d ẋd = d( 1 x d ) = -dx d
x d 2 into (9) we have:

dy d ẋd = y κd ẋd ( κd -ẋd ) ⇔ - dy dx d x d 2 = y 1 κ d 1 x d ( 1 κ d - 1 x d ) ⇔ dy dx d = y 1 κ d -x d (11)
Equation ( 11) is the ordinary differential equation to derive the delay-type cost function. From (11), we have:

dy y = dx d κ d -x d ⇔ dy y = - d(x d -κ d ) x d -κ d ln(y) = -ln(x d -κ d ) + ln(c) ⇔ y = c x d -κ d ⇔ y = Ψ.κ d x d -κ d (12)

D. Derivation of the multi-variable cost function

We now try to derive the bandwidth-delay cost function u(x w , x d ) considering two independent QoS parameters: bandwidth (x w ) and delay (x d ) at the same time. From ( 9) and (11), we have:

x w (κ w -x w ) κ w u xw + (κ d -x d )u x d = u (13)
In which u xw = ∂u ∂xw , and

u x d = ∂u ∂x d .
Equation ( 13) is a quasi linear first order partial differential equation, we will solve it to obtain our bandwidth-delay cost function.

Let

x w = x w (s), x d = x d (s), u = u(x w (s), x d (s)), then: ∂x w ∂s .u xw + ∂x d ∂s .u x d = ∂u ∂s (14)
Compare ( 13) and ( 14), we have:

           ∂x w ∂s = x w (κ w -x w ) κ w ∂x d ∂s = κ d -x d ∂u ∂s = u (15)
A constant of integration is obtained by eliminating s from two or more equations and integrating out. Such integration generates an arbitrary integration constant, which may be viewed as a function of all the variables, but it is constant with respect to s. Let φ(x w , x d , u) be a constant of integration, since it is constant with respect to s, we can write: 16) is the orthogonality property of the vector (x w , x d ), we can use it to check whether φ has been obtained correctly.

dφ ds = 0 ⇔ ∂φ
In order to solve (13) we have to find two constants of integration from (15).

D.1 Finding the first constant of integration:

From (15), we have:

dx w ds du ds = x w (κ w -x w ) κ w u ⇔ du u = κ w .dx w x w (κ w -x w ) (17)
Since ( 17) and ( 9) have an identical form, we can use Lemma 1 to achieve the first constant of integration (18) :

u = Φ.x w (κ w -x w ) ⇔ Φ = (κ w -x w )u x w (18)
We now check the orthogonality property of the first constant of integration (18) by confirming (16):

∂Φ ∂x w . x w (κ w -x w ) κ w + ∂Φ ∂x d .(κ d -x d ) + ∂Φ ∂u u = ∂( (κ w -x w )u x w ) ∂x w . x w (κ w -x w ) κ w + ... ... + ∂( (κ w -x w )u x w ) ∂x d (κ d -x d ) + ∂( (κ w -x w )u x w ) ∂u u = -κ w .u x 2 w . x w (κ w -x w ) κ w + 0.(κ d -x d ) + ... ... + (κ w -x w ) x w .u = 0 (19)
By ( 19) and ( 16), we can confirm that the first constant of integration has been correctly found.

D.2 Finding the second constant of integration:

Similarly, using (15) and ( 12), we can find the second constant of integration having the form of:

Ψ = (x d -κ d )u κ d ( 20
)
We now check the orthogonality property of the first constant of integration (20) by confirming (16):

∂Ψ ∂x w . x w (κ w -x w ) κ w + ∂Ψ ∂x d .(κ d -x d ) + ∂Ψ ∂u u = ∂( (x d -κ d )u κ d ) ∂x w . x w (κ w -x w ) κ w + ... ... + ∂( (x d -κ d )u κ d ) ∂x d (κ d -x d ) + ∂( (x d -κ d )u κ d ) ∂u u = 0. x w (κ w -x w ) κ w + u κ d .(κ d -x d ) + ... ... + (x d -κ d ) κ d .u = 0 (21)
By ( 21) and ( 16), we can confirm that the second constant of integration has been correctly found.

D.3 The general solution:

The equation Φ(x w , x d , u) = constant, describes a relationship among x w , x d , u such as shown in (15). Notice that if Φ(x w , x d , u) is a constant, then G(Φ) is also a constant (G(.) is any arbitrary function). Similarly, if Ψ(x w , x d , u) is a constant, then H(Ψ) is also a constant (H(.) is any arbitrary function). We can set these two constants equal so that:

G(Φ) = H(Ψ) (22)
This provides a more general expression in x w , x d , u that solves the partial differential equation ( 13). The two arbitrary functions in ( 22) may be merged into one by letting F(.) = G 1 (H(.)), then:

Φ = F(Ψ) (23)
(23) is the general solution of the partial differential equation (13).

D.4 Checking the general solution:

From ( 18), ( 20), (23), we have:

(κ w -x w )u x w = F (x d -κ d )u κ d (24)
We will now check whether ( 24) is indeed a solution, and that the function F can be completely general. Let u be expressed as a function of x w and x d , where x w and x d are still independent. We take the total derivative of (24) to x w and solve for

u xw . Denoting F (x d -κ d )u κ d = F(x d , u
), we have:

κ w -x w x w .u xw - κ w x w 2 .u = x d -κ d κ d .u xw .F ′ (x d , u) ⇔ u xw = κ w .κ d .u x w [(κ w -x w )κ d -x w (x d -κ d )F ′ (x d , u)] (25)
Similarly, taking the total derivative of (24) to x d and solve for u x d , we have:

(κ w -x w )u x d x w = F ′ (x d , u). u + (x d -κ d )u x d κ d ⇔ u x d = F ′ (x d , u).u.x w (κ w -x w )κ d -F ′ (x d , u).(x d -κ d ).x w (26)
Replacing ( 25) and ( 26) into the left-hand side of (13) we have:

x w (κ w -x w ) κ w . κ w .κ d .u x w . [(κ w -x w )κ d -x w (x d -κ d ).F ′ (x d , u)] + ... + (κ d -x d ). F ′ (x d , u).u.x w (κ w -x w )κ d -F ′ (x d , u)(x d -κ d ).x w = (κ w -x w ).κ d -(x d -κ d ).F ′ (x d , u).x w (κ w -x w )κ d -x w (x d -κ d ).F ′ (x d , u) .u = u
We can obtain the right-hand side of (13), so (24) is exactly the general solution of the partial differential equation (13).

D.5 Fitting boundary conditions to the general solution:

Equation (24) provides us a general solution comprising of a family of arbitrary functions. We need to fix to a certain bandwidth-delay cost function by assigning boundary conditions to this general solution. From the natural characteristics of two independent QoS parameters: requested bandwidth (x w ) and requested delay (x d ), and their partial cost functions (10) and ( 12), we have these boundary conditions:

       x w κ w -x w = t 3 κ d x d -κ d = t u = t 2 (27)
Replacing ( 27) into (24) we have:

F( t 2 t ) = t 2 t 3 ⇔ F(t) = 1 t (28)
From ( 28) and (24), we have:

F (x d -κ d ).u κ d = κ d (x d -κ d ).u = (κ w -x w )u x w (29)
The specific solution of (13) is therefore:

u(x w , x d ) = x w κ w -x w . κ d x d -κ d (30)
Recursively, we can see that, the specific multi-variable cost function equals to the average multiplication of all partial cost functions f i (x i ):

u(x 1 , x 2 , ..., x n ) = n n i=1 f i (x i ) (31)
In general, we can build a cost function for as many variables as possible. However, while a multi-variable cost function can consider many QoS parameters at the same time, it should be noted that the multi-variable cost function does not always give a better result than the singlevariable cost function. For example, the cost function with bandwidth, delay, and packet-loss can build a better multicast tree if many peers are using wireless access network with a high packet loss rate to join the multicast tree but when most of the peers are using a wired access network with a low packet loss rate, then that three-variable cost function may build a worse multicast tree than the twovariable cost function of only bandwidth and delay.

IV. Theoretical analysis of the new multi-variable cost function

Conventional cost functions can be divided into two groups. The first group comprises of single-variable cost functions such as (1), ( 2), ( 3), (4), and (5). The other group comprises of multi-variable cost functions such as [START_REF] Lorenz | Optimal partition of QoS requirements on unicast paths and multicast trees[END_REF].

Fig. 1(a) shows the value of a bandwidth-type singlevariable cost function versus the requested bandwidth. Since x w < κ w , we only consider the left domain of the graph. We can see that, when the requested bandwidth approaches κ w , the link cost increases rapidly to infinity. Fig. 1(b) shows the value of a delay-type single-variable cost function versus the requested delay. Since x d > κ d , we only consider the right domain of the graph. We can see that, when the requested delay approaches κ d , the link cost increases rapidly to infinity. Nevertheless, two single-variable functions failed to consider other important QoS parameters simultaneously. Fig. 2 shows the value of the newly proposed multi-variable cost function. In this graph, only two QoS parameters (requested bandwidth and delay) are shown for demonstrative purposes. We only use the right part of the graph where x w < κ w and x d > κ d . The main difference is that, the link cost will only increase rapidly when both requested bandwidth x w and delay x d excess the maximum resources κ w and κ d . When only a single parameter excesses its limited resource, a high cost will be assigned, however, it should not be high enough to block the entire link since we still have resources to assign for the other parameter. For example, when x d excesses κ d , the cost increases to a high value, however, if we still have much bandwidth to assign, then the increased link cost will not be sufficient to block the entire link. The link cost will only increase rapidly if both the requested bandwidth and delay simultaneously excess their available resources (which are the total resources that the link can provide). Compared to the heuristic multi-variable cost function [START_REF] Lorenz | Optimal partition of QoS requirements on unicast paths and multicast trees[END_REF], our new multi-variable cost function has many advantages. Firstly, it has considered the requested QoS parameters from the application instead of only the residual resource from the underlay network. This is a major advantage since application's requirements are usually varied. Secondly, although the scaling factors K i allows us to assign different weights for different parameters, it is not clear how to assign values for these factors in practice, therefore, there will be implementation problems. Thirdly, it is really unclear how we can add all bandwidth, buffer and delay together without any unit impairment. From the above analysis, we can conclude that our new multi-variable cost function owns better characteristics than conventional cost functions.

V. Conclusion and future works

In this research, a new multi-variable cost function has been proposed. The mathematical derivation process has also been described in details so that one can apply it to obtain other multi-variable cost functions according to their specific requirements. The newly found cost function has considered dynamic requirements of the application and the underlay network. For future works, intensive simulations will be performed to show the advantages of the newly proposed multi-variable cost function. A new ALM can be designed based on simulation and analysis results. The result can be further applied to improve the performance of any ALM algorithms who are using conventional cost functions to build their data delivery tree.

Fig. 1 .

 1 Fig. 1. Bandwidth-type (a) and delay-type (b) cost functions according to (10) and (12).

Fig. 2 .

 2 Fig. 2. Multi-variable cost function according to (30).


Toward building an efficient Application Layer Multicast tree

Tien Anh Le, Hang Nguyen, Quang Hoang Nguyen

Abstract-Link cost is very important in media distribution trees. A good cost function can provide information for media routing algorithms to find the best way to distribute the media on overlay networks. In this research, a bandwidth-type cost function is proposed. The proposed cost function can calculate links' costs based on both network resources and application's requirements. It can help Application Layer Multicast (ALM) routing algorithms to avoid congestion before building media distributing trees. The derivation process has also been explained in details so that it can be further applied in other conditions to build other cost functions suitable for different requirements. The newly proposed cost function will then be applied in a popular Application Layer Multicast (NICE) to replace its old cost function. Possible modifications to NICE's algorithm will be discussed. Intensive simulation scenarios have also been carried out to validate the advanced performance of the newly proposed cost function in comparison with conventional functions. The simulation scenario has also been developed to show the adaptation of the cost function under real conditions when some peers use the WiMax access network to join the multicast group.

Index Terms-application layer multicast routing; cost function; resource allocation; traffic control; end-to-end QoS routing;

I. Introduction

Multicast is the essential routing mechanism required by one-to-many and many-to-many services. If unicast can compete or even replace multicast in low data-rate services (e.g. short message service, instance message...), multicast is so far the best choice for multimedia services such as video streaming, IPTV, multi-point video conferencing. IP Multicast [START_REF] Deering | Multicast routing in datagram internetworks and extended LANs[END_REF] is the most efficient multicast mechanism to deliver the data over each link of the network only once, creating copies only when the links to the multiple destinations split. However, IP Multicast can only be deployed within a private network or on a network which can be fully managed by the service provider. The deployment of IP Multicast over the Internet has been facing many technical and business problems [START_REF] Diot | Deployment issues for the IP multicast service and architecture[END_REF] which are preventing it from being used universally. Attempts have been made to overcome these problems. Explicit Multi-Unicast (XCAST) [START_REF] Boivie | Explicit multicast (Xcast) concepts and options[END_REF] is an alternate multicast strategy to IP multicast that provides reception addresses of all destinations within each packet. As such, since the IP packet size is limited in general, XCAST cannot be used for multicast groups of large number of destinations. Tunnels and bridges can be made to connect IP Multicast islands with each other using unicast or Application Layer Multicast (ALM) as proposed in Island Multicast [START_REF] Jin | Island multicast: Combining ip multicast with overlay data distribution[END_REF]). Between them, the method using ALM is more favorable since it can provide a more efficient mechanism connecting IP Multicast islands. Application Layer Multicast can be used as the bridges between IP Multicast islands but it is also well-known for its capability of being deployed as a stand-alone solution for multicasting service over the Internet. The key concept of ALM is the implementation of multicasting functionality as an application service instead of a network service. Although there are some drawbacks such as multiple copies of the same packet on the same link as well as typically constructing non-optimal trees, it has an excellent advantage that IP-Multicast cannot have: easier and possibly immediate deployment over the Internet, ability to adapt to a specific application. Tree-push is a common approach for data delivery in Application Layer Multicast algorithms, especially when the multimedia quality is concerned [START_REF] Hwang | Multimedia Networking: From Theory to Practice[END_REF]. In this approach, before the data distribution can take place, a media distribution tree must be built from all participating peers. The construction algorithm of the media distribution tree is based on the costs among participating peers. These costs are calculated by using a certain cost function. Eventually, the efficiency of the media distribution algorithm will mainly depend on the cost function being used. The main contribution of this research is to propose a cost function considering requirements from both the multimedia service and available resource from the underlay network for building a more efficient ALM media distribution tree. The derivation process will also been explained in details so that it can be further applied in other conditions to build other cost functions suitable for different requirements. The implementation process of the new cost function in NICE, a very popular ALM algorithm, will also be studied to show its feasibility and its advance in performance. Intensive simulation scenarios in which a maximum of more than one thousand peers are served at the same time using conventional distance-type cost function and the newly proposed bandwidth-type cost function. The simulation scenario is also extended to cover the case when some peers are joining the multicast session from the WiMax access network. This scenario will show how well the newly proposed cost function can adapt with the real network conditions.

II. Conventional cost function in NICE

NICE [START_REF] Banerjee | Scalable application layer multicast[END_REF] is a popular ALM protocol, specially designed for large number of receiver sets. The protocol arranges peers into a layering hierarchy. The basic operation of the protocol is to create and maintain that hierarchy. The hierarchy is created by assigning peers into different layers. Peers in each layer are partitioned into a set of clusters whose sizes are from k to 3k-1 (with k is a chosen constant number of peers who have the nearest "distance" to each other). Each peer will have a maximum distance (M d ) to all other peers within that cluster. The leader (or the center) of a cluster will be elected as the one who has the minimum M d . Firstly, all peers will join clusters of the first layer. Then leaders from all clusters of the first layer will form clusters on the second layer. There are at most log k (N ) layers with the highest layer has only single member. The data distribution in NICE is a source-specific tree. If a peer wants to multicast data, it will unicast that data to the leader of its cluster. That leader will then multicast the data to all members of all clusters that it is joining including leaders on upper layers. These leaders will then multicast the data to the rest. NICE is a very popular sample for a tree-pushed multicast algorithm. It depends heavily on "distances" which are actually calculated by a delay-type cost function. The delay is measured by a very simple end-to-end latency which is obtained by using a simple ping between each pair of peers. Other conventional cost functions can also been applied to calculate the distances among peers in NICE. In [START_REF] Matta | On routing real-time multicast connections[END_REF][8] [START_REF] Bueno | Multicast extension of unicast charging for qos services[END_REF], some cost functions have been proposed. However, all of them only consider the network resource when calculating the cost, none of them consider requirements from the multimedia applications which are also varied greatly during the communication session. In [START_REF] Lorenz | Optimal partition of QoS requirements on unicast paths and multicast trees[END_REF] and [START_REF] Raz | Optimal partition of QoS requirements with discrete cost functions[END_REF], conventional cost functions have started to consider application's requirements. However, there was neither mathematical derivation nor theoretical analysis for these cost functions so one may easily get loss when trying to apply this cost function in other conditions.

III. Proposed bandwidth-type cost function

Assuming that we have an overlay with application peers and end-to-end-links, in order to form a tree for data delivery, we need costs of all those end-to-end links. These costs must be calculated by a cost function. On each end-to-end link, we have to consider variable requirements from applications running on the NICE ALM. For example, an application can be a scalable video service with different video coding layers or it can be a multimedia flux comprising of video, audio, text, data sub-streams, each has different bandwidth and delay requirements. Those requirements are changed frequently by the application. We have to also consider the maximum available resources of the underlay. For example, if an end-to-end link is built upon 3 physical links, each has its own available bandwidth. Then the maximum available bandwidth of the end-to-end link equals to the minimum available bandwidth (bottleneck) of all 3 physical links. Assume we have on the end-to-end link i : A total available bandwidth of κ w , and a requested bandwidth of x w , we must find the bandwidth-type cost function: f (x w ). Since κ w is the maximum available bandwidth when using all available resources on link i, so 0 ≤ x w ≤ κ w . With time, according to the application's requirements, x w may be varied by an amount of ∆x w causing the cost to have the current value of f (x w + ∆x w ), so this current value of the cost function depends on:

• The previous cost: f (x w ),

• The increment of cost which is proportional to:

-The previous cost: f (x w ), -The ratio between the increment of requested bandwidth and the total requested bandwidth: ∆xw xw+∆xw , • The decrement of cost which is proportional to: -The ratio between the decrement of the remaining available bandwidth and the maximum available bandwidth (κw-xw-∆xw) κw . Finally, we have:

f (x w + ∆x w ) = f (x w ).     1 + ∆x w x w + ∆x w (κ w -x w -∆x w ) κ w     (1)
From ( 1) we have:

lim ∆xw→0 f (x w + ∆x w ) -f (x w ) ∆x w = lim ∆xw→0 f (x w ) κ w (x w + ∆x w ) . 1 (κ w -x w -∆x w ) ⇔ f ′ (x w ) = f (x w ). κ w x w (κ w -x w ) (2)
Replacing f (x w ) by y and f ′ (x w ) by dy dxw ; from (2) we have an ordinary differential equation:

dy dx w = y κ w x w (κ w -x w ) (3)
Solve the ordinary differential equation ( 3), we find the bandwidth-type cost function:

dy y = κ w x w (κ w -x w ) dx w ⇔ ln(y) = ln(x w ) -ln(κ w -x w ) + c ⇔ y = Φ.x w (κ w -x w ) (4)

IV. Simulation methodology and results

We set up an OverSim [START_REF] Baumgart | OverSim: A flexible overlay network simulation framework[END_REF] simulation scenario based on NICE. The main goal of the simulation is to show the advanced performance of a representative ALM algorithm (e.g. NICE) when applying our new cost function. The simulation may only show the advanced performance for NICE but the simulation methodology (which is protocolindependence) can be generalized to any ALM algorithm using a different cost function other than our new cost function for building the data delivery tree. The simulation plan will build an overlay of a varied number of peers (e.g., varied group sizes of 16, 32, 64, 128, 256, 512, and 1024) running on an underlay network topology generated by GT-ITM [START_REF] Calvert | GT internetwork topology models (GT-ITM)[END_REF]. Each topology was a two-level hierarchical transit-stub topology, containing 1250 nodes and about 6000 physical links [START_REF] Zegura | How to model an internetwork[END_REF]. Each physical link will have random values of delay, bandwidth, and PER (Packet Error Ratio). We will use the simulation plan described in [START_REF] Constantinescu | Overlay multicast networks: elements, architectures and performance[END_REF] for comparison and confirmation purposes. We use similar performance metrics commonly applied by all ALM algorithms to validate the advanced performance of the NICE only uses a delay-type cost function to build and to maintain its ALM tree (with a clustering, layering structure). By sending and receiving periodic heartbeat messages containing delays between nodes within a cluster, peers will decide whether it should elect a new clusterleader. Changing cluster-leaders provokes changing and rebuilding the entire NICE tree. In its original paper [START_REF] Banerjee | Scalable application layer multicast[END_REF], authors of NICE implemented the delay-type cost function simply by using an end-to-end delay parameter. We now want to apply our new bandwidth-type cost function. Costs of all end-to-end links will be calculated and NICE will use them instead of the conventional delay cost to run their algorithm on. We will compare performances of two cases mainly by using two metrics: average link stress, and average link stretch [START_REF] Constantinescu | Implementation of Application Layer Multicast in OverSim[END_REF]. The average link stress metric is defined by the mean value of identical packets sent by a protocol over each underlay link. To calculate the average link stress of the network, instead of standing on each link and counting identical packets, we let the nodes (peers/routers) count the link stress of all their links, and then take a half of the sum. The reason for doing so is because in OverSim, it is easier to control nodes than links, meanwhile any physical link is always formed just by 2 nodes. The average link stretch is the ratio of average path length of the members of a protocol to the average path length of the members in the multi-unicast protocol. In our implementation, we just concentrate on the numerator: the average path length (mean value of actual hops) that a data packet must go through from source to destination. For each packet received at an overlay peer, we will take its Time-To-Live information which is actually the hop-count value that it had to go through. Note that we just need to count the path length of packets routed by the ALM protocol, so we take the calculation at the overlay layer, not at the underlay layer.

Fig. 1 shows that the newly proposed cost function when applied by NICE can reduce the average link stress that a link has to take to a smaller value than the original NICE's distance function. The result in Fig. 2 means that, in average, a packet has to go over a longer physical route when applying the newly proposed cost function. However, Fig. 3 shows that the average end-to-end delay when applying the new cost function is much smaller than the old distance function especially when the group size increases. Even when the number of participants is 1024, the average endto-end delay of the new cost function is just about 79 ms which is much smaller than the limitation value of 150 ms recommended by ITU-T for real-time communication services [START_REF] Itu-T | [END_REF]. From the results we can see that, the new cost function can avoid multiple replication of packets on access links and so reduce the average link stress. Even though a packet may have to go through more physical hops in order to reach its destination, the new cost function can still guarantee a half-smaller average end-to-end delay than the conventional distance function. It should be noticed from Fig. 3 that, when the group size is smaller than 64, the average end-to-end delays when applying new and conven- tional cost functions are similar since there are not many better options for NICE to choose from. However, when the group size is large, the new cost function can give out more routes for NICE to build its media distribution tree resulting in a much better average end-to-end delay than the conventional cost function.

V. Extended simulation scenario

To see the adaptation of the newly proposed cost function in the real network conditions, we implement a testbed based on both the Oversim-based simulation platform and two real WiMax terminals. The Oversim-based simulation platform is reused from the previous simulation scenarios. The WiMax access network comprises of an Acatel-Lucent base station (9710 C-WBS). The first WiMax terminal is an Alcatel-Lucent 9799 PCMCIA card. The second terminal is a Sequans USB card. IEEE 802.16e-2005 state of the art Scalable OFDMA based Technology is applied. Fig. 4 illustrates the integration between the Oversim-based simulation platform and the WiMax access network.

The results show that, when some peers are using a WiMax access network to participate in the multicast tree, the performance of a single variable cost function is not good enough to give a really better performance since the access network is usually very varied in QoS. More investigations need to be done for this type of access network.

VI. Conclusion and future works

In this research, a new bandwidth-type cost function has been proposed. The mathematical derivation process has also been described in details so that ones can apply it to obtain other cost functions according to their specific requirements. The newly found cost function has considered dynamic requirements of the application and the underlay network. Intensive simulation results show that the new cost function can greatly reduce the average link stress and average end-to-end delay (two very important metrics in multimedia services) for the multicast session. A real testbed has been developed from the simulation scenarios to illustrate the adaptation of the newly proposed cost function in the case when some peers are using the WiMAx access network to connect to the multicast group. Base on this result, multi-variable cost function should be considered. For future works, a new ALM can be designed based on the newly proposed cost function. The result can be further applied to improve the performance of any ALM algorithms who are using conventional cost functions to build their data delivery tree.

Fig. 1 .

 1 Fig. 1. Average link stress comparison for the NICE data-plan using the old and newly proposed bandwidth-type cost functions. Transmitting data is obtained from a real SVC transmission session.

Fig. 2 .

 2 Fig. 2. Average path length (physical router counting) comparison for the NICE data-plan using the old and newly proposed bandwidthtype cost functions. Transmitting data is obtained from a real SVC transmission session..

Fig. 3 .

 3 Fig. 3. Average end-to-end delay performance.

Fig. 4 .

 4 Fig. 4. Extended simulation scenario with 2 real Wimax terminals.


Mengke Hu
email: mengke.hu@telecom-sudparis.eu

Hongguang Zhang
email: hongguang.zhang@it-sudparis.eu

Tien Anh Le

Hang Nguyen
email: hang.nguyen@it-sudparis.eu

Performance Evaluation of Video Streaming over Mobile WiMAX Networks

Keywords: Video Streaming, Scalable Video Coding, WiMAX I

This paper considers the transmission performance of multimedia streams, especially Scalable Video Coding (SVC), over mobile WiMAX networks. SVC supports temporal, spatial, and quality scalabilities at bit-stream level, which enables the easy adaptation of video by selecting the sub-sets of bit-stream. Thus, SVC streams are more suitable than non-scalable bitstreams in the mobile environment where network conditions are dynamic. In this work, we firstly set up a simulation platform, which integrates NS-2 WiMAX module with EvalSVC evaluation tool set. Then, we design scenarios involving multiple Mobile Stations (MS) and handover to evaluate the performance of video streaming. After intensive simulation tests, we compare the throughput and the packet delay in the different connection scenarios, and count the frame loss of the received video. The simulation results indicate that, in terms of frame loss, the number of MSs is critical to the performance of video transmission. Moreover, handover imposes great influence on video stream transmission.

INTRODUCTION

As the wireless multimedia communication services have been booming, the demands for real-time video streaming increase sharply. Recent development in high speed wireless networks has made it possible to provide real-time video streaming. Among those wireless standards, Worldwide Interoperability for Microwave Access (WiMAX) is prominent on the aspects of high-data rate and long-range coverage. The standard for mobile WiMAX networks is IEEE 802.16e that has come out for MBWA (Mobile Broad Band Wireless Access) in 2005. However, the bandwidth variation, handoff, and the transmission error of WiMAX are critical problems that impose a lot of interferences on video streaming. In this regard, Scalable Video Coding (SVC) has emerged as a promising video format. SVC is developed as an extension of H.264/MPEG-4 Advance Video Coding (AVC) [START_REF] Schwarz | Overview of the Scalable Video Coding Extension of the H.264/AVC Standard[END_REF]. SVC offers spatial, temporal and quality scalabilities at bit-stream level, which enables the easy adaptation of video by selecting a sub-set of the bit-stream. As a result, the SVC bit-streams can be easily truncated to meet various constraints of heterogeneous environments [START_REF] Monteiro | Evaluation of the H.264 Scalable Video Coding in Error Prone IP Networks[END_REF]. Thus, SVC streams realize a better allocation and usage of the available resource; and they are more suitable to be transmitted over unpredicted wireless networks [START_REF] Casasempere | Performance Evaluation of H.264/MPEG-4 Scalable Video Coding over IEEE 802[END_REF]. Therefore, for mobile WiMAX transmission, SVC video stream is a good choice to make up the deficiencies of mobile WiMAX networks including handover and bandwidth variation.

In this circumstance, it is necessary to evaluate the transmission performance of SVC streams over mobile WiMAX networks. However, the performance evaluation of real mobile WiMAX is expensive and inconvenient, because of the limited deployment of WiMAX and the proprietary nature of these deployments. In this regard, the computer-based simulation is a feasible solution. Unfortunately, the current simulation platform is neither complete nor comprehensive enough to evaluate SVC over WiMAX. For example, the widely-used evaluation tool set EvalVid [START_REF] Klaue | EvalVid -A Framework for Video Transmission and Quality Evaluation[END_REF] does not support SVC. Moreover, the mobile WiMAX module [START_REF] Rouil | [END_REF] for NS-2 platform has no interface to transmit real video streams.

In this work, we have combined the mobile WiMAX NS-2 with our EvalSVC [START_REF] Le | EvalSVC -an evaluation platform for scalable video coding transmission[END_REF] for real video stream transmission and evaluation. In order to evaluate the performance of SVC stream transmission over mobile WiMAX, we propose four connection scenarios depicted as follows:

 One BS (Base Station) and one MS (Mobile Station) as streaming client.

 One BS and multiple MS as streaming clients,  One BS Multiple MS as streaming servers,  One MS as streaming client handover between two BS These scenarios are implemented by NS-2 scripts including parameter settings, network construction, and video stream transmission. After simulation in each case, we reconstruct the received video stream, and then compare it with the original one, in order to evaluate the effects of different scenarios.

The remainder of this document is organized as follows: in Section II, we will explain our experiment environment, including the platform introduction and parameter settings. The four mobile WiMAX connection scenarios will be presented in Section III, and the correspondent results and analysis lie in Section IV. Finally, a brief conclusion will be drawn and the rest problem for the further research will be outlined in Section V.

This work is partly supported by the Poseidon project.

II. EXPERIMENT ENVIRONMENT

In this section, we firstly present an overview of our experimental tools. Then, we will show the parameter settings in our simulation.

A. Platform Introduction

For the video evaluation, we use EvalSVC to calculate the QoS measurements. EvalSVC, derived from EvalVid, is our previous work that supports SVC video evaluation. EvalSVC tool set provide trace-based video evaluation. Precisely, it only needs all trace files, original SVC encoded bit-stream and a SVC decoder to generate QoS measurements such as end-toend delay, jitter, loss rate, sender"s and receiver"s bit-rate.

For the simulation of mobile WiMAX networks, NIST has proposed WiMAX module for NS-2. Based on their work, we improve the SVC transmission interfaces in WiMAX NS-2. These interfaces are designed either to read the video trace file or to generate the data required to evaluate the video delivered quality. Besides, they can also inspect the network performance issues, including throughput and packet delay.

B. Parameter Settings 1) SVC Encoding

In our experiment, the video stream is encoded in SVC quality scalability. Precisely, we use MGS (Medium Grained Scalability), which any enhancement layer NAL (Network Abstract Layer) unit can by discarded from a quality scalable bit stream and thus packet based quality scalable coding is provided.

The original source file is "Foreman". After encoding in SNR scalability (MGS mode) by JSVM8.5, the video stream contains twenty layers. The details are showed in TABLE I.

2) WiMAX module for NS-2

We have created several mobile WiMAX connection scenarios. These scenarios will be showed in detail in the next section, but all of them have the same parameter settings:

 OFDM modulation with 64-QAM constellation rate, channel bandwidth 10M Hz.

 TDD (Time Division Duplex).

 Network topology X range: 1100m.

 Network topology Y range: 1100m.

 Diffusion radius: 500m.

 Bit rate of Constant Bit Rate (CBR) traffic: 500 kbps.

III. EXPERIMENT SCENARIOS

In this section, we describe the four connection scenarios in detail. Here, I have to mention that the frame loss, packet delay, throughput are obtained only from video streaming client.

A. One MS as streaming client

The video stream is transmitted from streaming server (wire-linked with one BS) to one MS as a streaming client. In this scenario, the only interference to the video transmission is bandwidth variation due to the mobile WiMAX network condition. Compare with other scenarios in the following parts, the frame loss, and packet delay would be the smallest, while the throughput would be the largest in this case.

B. Multiple MS as streaming clients

The video stream is transmitted from streaming server (wire-linked with one BS) to multiple MS as streaming clients. In this case, only one of these MSs is video streaming client that receives real video traffic and the rest of the MSs are interfering stations that receive Constant Bit Rate (CBR) traffic. In this circumstance, the increasing of MS would cause the shrink of available bandwidth for video streaming client, because the CBR flows would contend the bandwidth for video transmission. Thus, with the increasing of MS the frame loss, and packet delay would increase, while throughput would decrease.

C. Multiple MS as streaming server

The video stream is diffused from streaming server (MS) to one BS, and transmitted to streaming client wire-linked with the BS. In this case, only one of these MSs is video streaming server that sends real video traffic, and the rest of the MSs are interfering stations that send CBR traffic. In this circumstance, the increasing of MS would cause the shrink of available bandwidth for video streaming server, because the CBR flows would contend the bandwidth for video transmission. Thus, with the increasing of MS the frame loss, and packet delay would increase, while throughput would decrease.

D. One MS as a streaming client over two BS

The video stream is transmitted from streaming server (wire-linked with both BSs) to two BS of different coordinate, and diffused to one MS as Streaming Client. In this case, we can only see that a MN is losing connection with its current BS and scans to find another point of attachment. The packet delay and throughput would fluctuate during searching for new attachment. The frame loss would be larger than scenario A.

IV. EXPERIMENT RESULTS ANALYSIS

In this section, we show our experiment results and make correspondent analysis. In the following figures, the "MN" in the legends is referred as Mobile Nodes. It is correspondent to MS. The "Sender" is referred as streaming server, while the "Receiver" is referred as streaming client. Because the WiMAX bandwidth is various, the two curves in Fig. 1 fluctuated. The "Receiver Bitrate" is smaller than "Sender Bit-rate", as the uplink and downlink are asymmetric. However, without the interference of CBR traffic, the transmission performs well, because receiver bit-rate never equals zero.

A. 1 MS as streaming client

B. Multiple MS as streaming clients

In this part, we simulate 1MN, 2 MN, 10 MN, 15 MN, 20 MN, and 30 MN respectively. The results depicted in the following figures compare the performance issues in these 6 cases. The Fig. 2 and Fig. 3 indicate that with the increasing number of MS, in general, the packet delay increases, while the throughput decreases. As for the bit-rate from Fig. 4, it is obviously larger at the sender part than at the receiver part. However, with the interference of CBR traffic, the transmission performs worse than the scenario A.

C. Multiple MS as streaming server

In this part, we simulate 2 MN and 8 MN respectively. The results depicted in the following figures compare the performance issues in these two cases. When the number of MNs is more than 9, the received video totally corrupts. In Fig. 5 and Fig. 6, they tell us the fact that with the increasing number of MS, in general, the packet delay increases, while the throughput decreases. However, compared with Scenario B, the performances are much worse. The reason is that the up-link bandwidth of MS is narrower than the one of wire-linked video server. From Fig. 7, we can see that the bitrate at both sender and receiver decrease sharply because of too much packet loss.

D. One MS handover between two BS

In this part, we simulate handover, as well as one MN as a streaming client. The results depicted in the following figures compare the performance issues in these two cases. From Fig. 8 and Fig. 9, we can see that at the 3sec and the 20 sec, handover happens, because the packet delay and throughput fluctuate severely. From Fig. 10, the bit-rate at both sender and receiver are much smaller than those in scenario A. From the figures in this part, the hand over effect the transmission a lot compared with scenario A.

E. Frame Loss after Reconstruction

In this part, we reconstruct the received video and count the general frame loss in respect to the original one. The TABLE II indicates that the number of MN referred as MS does affect the performance of video transmission. Besides, handover causes great frame loss, which would make the reconstruction failure.

V. CONCLUSION AND FUTURE WORK

In this paper, the transmission performance of SVC video streams over mobile WiMAX is investigated through our simulation platform. The results show that the number of MSs and the number of BSs (handover) does affect the video quality in terms of frame loss. The future work will be towards the SVC layer adaptation algorithm, which could further improve the performance of video streaming over mobile WiMAX.

Figure 1 .

 1 Figure 1. Cumulative Bit-rate at Sender and Receiver

Figure 2

 2 Figure 2. Packet Delay

Figure 4 .

 4 Figure 4. Cumulative Bit-rate at Sender and Receiver

Figure 5

 5 Figure 5. Packet Delay

Figure 7 .

 7 Figure 7. Cumulative Bit-rate at Sender and Receiver

Figure

  Figure 8. Packet Delay

Figure 10 .

 10 Figure 10. Cumulative Bit-rate at Sender and Receiver

TABLE I

 I

						11	352x288	7.5000	330.70	(0,2,1)
						12	352x288	7.5000	400.70	(0,2,2)
						13	352x288	7.5000	494.30	(0,2,3)
						14	352x288	15.0000	430.60	(0,3,1)
						15	352x288	15.0000	517.90	(0,3,2)
						16	352x288	15.0000	637.90	(0,3,3)
						17	352x288	30.0000	537.00	(0,4,1)
						18	352x288	30.0000	639.50	(0,4,2)
						19	352x288	30.0000	782.90	(0,4,3)
		.	CONTAINED LAYERS
	Layer	Resolution	Frame	Bit	Min	D T Q
	ID		Rate	Rate	Bite
					Rate
	0	352x288	1.8750	110.30	110.30	(0,0,0)
	1	352x288	3.7500	147.20	147.20	(0,1,0)
	2	352x288	7.5000	190.30	190.30	(0,2,0)
	3	352x288	15.0000	234.10	234.10	(0,3,0)
	4	352x288	30.0000	280.00	280.00	(0,4,0)
	5	352x288	1.8750	175.80		(0,0,1)
	6	352x288	1.8750	217.90		(0,0,2)
	7	352x288	1.8750	276.20		(0,0,3)
	8	352x288	3.7500	244.70		(0,1,1)
	9	352x288	3.7500	299.50		(0,1,2)
	10	352x288	3.7500	374.20		(0,1,3)

TABLE II

 II

	.	FRAME LOSS
	WiMAX Connection	General Frame Loss After
	Scenarios	Reconstruction
	1 MN receives video stream	4.00%
	1 MN receives video stream,	4.00%
	1 MN receives CBR flow
	1 MN receives video stream,	4.33%
	9 MNs receive CBR flows
	1 MN receives video stream,	8.21%
	14 MNs receive CBR flows
	1 MN receives video stream,	9.77%
	29 MNs receive CBR flows
	1 MN receives video stream,	20.42%
	29 MNs receive CBR flows
	1 MN sends video stream,	52.39%
	1 MN sends CBR flow
	1 MN sends video stream,	54.16%
	7 MNs sends CBR flows
	Handover: 1 MN receives video	30.30 %
	flows over 2 BSs