Gertjan Halkes

Johan Pouwelse
email: j.a.pouwelse@tudelft.nl

UDP NAT and Firewall Puncturing in the Wild

Keywords: UDP, NAT, Firewall, Puncturing, Measurements

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In Peer-to-Peer (P2P) systems, computers on the Internet connect with each other in a symmetrical fashion. The computers simultaneously assume both the role of client as well as the role of server. This requires that random computers on the Internet must be able to connect with each other. However, the deployment of firewalls and Network Address Translator (NAT) boxes creates obstacles.

By their very nature, firewalls are meant to regulate what connections are permitted. Moreover, firewalls are frequently configured to allow only outgoing connections, based on the assumption of the client-server model of communication. Of course, in a P2P setting connections may also be incoming, often on non-standard ports, which these firewalls don't allow.

NAT boxes pose a separate but related problem. Although NAT by itself is not meant as a connection filtering technology, it does present an obstacle for setting up connections: the publicly visible communications endpoint (IP and port combination) is not visible for the computer behind the NAT box, and may even be different for each remote endpoint. To make matters worse, NAT technology is often combined with firewalling to create an even bigger obstacle for connection setup.

The techniques for dealing with NATs and firewalls are well known. For example, the STUN [START_REF] Rosenberg | Session Traversal Utilities for NAT (STUN). RFC 5389 (Proposed Standard)[END_REF] protocol details how a computer can determine what kind of NAT and firewall is between itself and the public Internet. Connection setup can be done through connection brokering or rendez-vous [START_REF] Ford | Peer-to-peer communication across network address translators[END_REF]. It should be noted though that the connection setup techniques are most useful for UDP traffic. Setting up a connection for TCP traffic when both computers are behind a NAT/firewall requires unusual or non-standard use of TCP and IP mechanisms, and may rely on specific NAT/firewall behaviour to work [START_REF] Biggadike | NATBLASTER: Establishing TCP connections between hosts behind NATs[END_REF].

In this paper we present the results of a measurement study of UDP NAT and firewall puncturing "in the wild". Using the known techniques, we have implemented a P2P solution for NAT and firewall puncturing which we then used to measure connection setup success. Our results show that using puncturing, connections between many more peers can be set up, which should ultimately increase robustness in the P2P network.

Related Work

The problems related with NATs and firewalls and work-arounds for these problems have been described extensively in previous work. The STUN protocol [START_REF] Rosenberg | Session Traversal Utilities for NAT (STUN). RFC 5389 (Proposed Standard)[END_REF] describes how to detect the type of NAT and firewall between a computer and the public Internet and determine its publicly visible address. To do so, it uses UDP messages (although TCP is also supported) sent to pre-determined STUN servers with public IP addresses. Although the STUN protocol does not provide guarantees about whether the address learnt through it is in fact usable for connection setup, the techniques described are the most well-known method for determining NAT and firewall types.

UDP hole punching was extensively described in [START_REF] Ford | Peer-to-peer communication across network address translators[END_REF] (although earlier descriptions exist). The idea is that to allow packets to come in from a remote endpoint, the computer behind the NAT or firewall needs to send something to the remote endpoint first. By doing so it creates a "hole" in the NAT or firewall through which communications can proceed. This even works when both sides are behind a NAT/firewall, when both sides start by punching a hole in their respective NAT/firewalls.

In this paper we only consider simple hole punching. More elaborate techniques exist to deal with NAT/firewalls with more complex behaviour [START_REF] Roverso | NATCracker: NAT combinations matter[END_REF]. However, these techniques only apply to a small percentage of the NAT/firewalls on the Internet, and are therefore less useful.

Previous studies have shown that a significant portion of the Internet hosts could be usable in P2P networks using the cited techniques [START_REF] Ford | Peer-to-peer communication across network address translators[END_REF][START_REF] Guha | Characterization and measurement of tcp traversal through nats and firewalls[END_REF][START_REF] Noh | Experiences with a large-scale deployment of stanford peer-to-peer multicast[END_REF]. However, none of these studies try to determine to what extent the theoretical ability to connect is actually usable. The study presented in this paper tries to fill that void.

In the rest of this paper we will use the terminology introduced by the BEHAVE working group [START_REF] Audet | Network Address Translation (NAT) Behavioral Requirements for Unicast UDP[END_REF]. Specifically we will use the following terms and their respective abbreviations (see Figure 1 for a graphical explanation of the mapping types):

Endpoint-Independent Mapping (EIM) The NAT reuses the port mapping for subsequent packets from the same IP address and port to any remote IP address and port. So when sending packets to host A and B from the same internal IP address and port, hosts A and B will see the same external IP address and port. Address-Dependent Mapping (ADM) The NAT reuses the port mapping for subsequent packet from the same internal IP address and port to the same remote IP address, regardless of the remote port. This means that host A will always see the same external IP address and port, regardless of the port on host A, but host B will see a different mapping. Address and Port-Dependent Mapping (APDM) The NAT only reuses the port mapping for subsequent packets using the same internal and remote IP addresses and ports, for the duration of the mapping. Even when communicating from the same internal IP address and port, host A will see two different external IP addresses and/or ports when different ports on host A are used. Endpoint-Independent Filtering (EIF) The NAT or firewall allows packets from any remote IP address and port, for a specific endpoint on the NAT or firewall. Address-Dependent Filtering (ADF) The NAT or firewall allows packets destined to a specific endpoint on the NAT or firewall from a specific remote IP, after a computer behind the NAT of firewall has sent a single packet to the remote IP. Address and Port-Dependent Filtering (APDF) The NAT or firewall allows packets destined to a specific endpoint on the NAT or firewall from remote endpoints only after a packet has been sent to that remote endpoint from inside the NAT or firewall.

For the purposes of our experiments there is no difference between ADM and APDM as only single endpoints on the different hosts are used, which we will therefore combine into the abbreviation A(P)DM. Similarly we collapse the definitions of ADF and APDF into A(P)DF if the distinction is irrelevant. In [START_REF] Roverso | NATCracker: NAT combinations matter[END_REF] a more extensive subdivision is made, but again the distinctions made are relevant only when considering multiple ports or port-prediction techniques.

Implementation

We have implemented a UDP NAT/firewall puncturing scheme as part of the Tribler BitTorrent client. Although the Tribler client does not currently use UDP for setting up connections or exchanging data, we use it as a vehicle to deploy our puncturing test software on real users' machines. The puncturing test builds an swarm, much like the BitTorrent software. However, instead of having a separate tracker, we use a peer at a pre-programmed address and port and employ a form of Peer EXchange (PEX) to find new peers to connect with. The PEX messages include a (random) peer ID, the IP address and port at which the peer originating the PEX message communicates with the remote peer, and the NAT/firewall type of the remote peer. The latter is included so the receiving peer can determine whether it is useful to attempt to connect to the remote peer, as certain combinations of mapping and filtering are not able to connect to each other. Our implementation tries to make minimal use of centralised components. Therefore the detection of the NAT and firewall type are not done using STUN. Instead, the peers rely on information reported by other peers and by checking if other peers can connect to it without previous communication in the reverse direction. Furthermore, peers use other peers as rendez-vous servers (see Figure 2). If a peer R is connected to two other peers A and B , it can serve as rendez-vous server for them, even if it is itself behind a NAT box or firewall.

It should be noted that due to the generic audience which participated in our trial we expect these numbers to be reasonably representative for generic Internet users. Because using P2P file-sharing software is typically discouraged in a corporate environment, we do expect a bias towards home users. Home users tend to use less professional equipment that is more prone to misbehaviour, which may negatively impact our connection success rate results.

In the following sections we will describe the tests used by peers to determine their NAT and firewall types.

NAT Type Detection

To allow determination of the NAT type of the NAT box (if any) that a peer is behind, all peers report the remote address and port they see when a connection is set up. So each peer will receive, from its communication partner, his own external address and port. If the reports from all communication partners are the same (or at least a large majority is the same), a peer will determine that there is either no NAT or the NAT has EIM behaviour. Note that the two cases (no NAT or EIM behaviour) are indistinguishable without a reliable local determination of the local address. Furthermore, the difference is mostly irrelevant. If, however, the reported external IP address and/or port are regularly different, then the peer concludes that it is behind a A(P)DM NAT.

Filtering Behaviour Detection

The filtering behaviour of a NAT/firewall is detected by checking whether a direct connection request arrives before a reverse connection request arrives. To enable this to work, when a peer tries to set up a connection using rendezvous, it will always first send a direct connection request to the remote peer. In most cases this direct connection request will arrive at the remote peer before the reverse connection request from the rendez-vous, unless the NAT/firewall behaviour is A(P)DF. So when for a significant fraction of incoming requests the direct connection request arrives before any communication in the reverse direction, the peer concludes that the filtering behaviour is EIF (or there is no firewall, which again is indistinguishable). Otherwise it must conclude that the filtering type is A(P)DF.

In principle it would be possible for the clients to distinguish between ADF and APDF. For example, peers could try to deliberately send a direct connection request to the wrong port. If the filtering is of APDF type, no connection can be setup, and the attempt will always fail. However, if the firewall uses ADF type filtering, the attempt will still succeed (assuming the reverse connection request arrives at the remote peer). Another option is to try to connect to peers behind an A(P)DM type NAT. This should theoretically only succeed for peers behind ADF firewalls. These experiments should be performed several times before concluding one way or the other.

In our implementation however, we have not let peers try to distinguish between APDF and ADF type filtering. We did let A(P)DF peers attempt to connect to A(P)DM peers, such that from the collected logs we can later make the distinction. Because distinguishing between APDF and ADF filtering after the experiments should not provide different results, and the fraction of both EIM-ADF and A(P)DM peers is small (see Section 5), we felt that including this distinction in the client software would provide little benefit.

Results

In this section we present the results for two trials. For the purposes of data collection, the peers in the network logged all interesting send and receive events to a local log file. In the first trial (907 peers), peers would not retry a failed connection attempt immediately. After analysing the results of this first trial, we conducted a second trial (1,531 peers) in which peers would perform up to three retries if connection attempts failed. In the first trial peers regularly sent the collected logs to a central collection server. However, in the second trial we used a less intrusive reporting method which lead to peers with an unfiltered Internet connection being favoured in the results. Therefore we report the market share results from the first test to ensure correct results. Both trials lasted several weeks.

Market Share

Figure 3 shows the detected NAT and firewall types for 646 out of the 907 peers in the first trial, for which were able to draw a conclusion about the NAT/firewall type from the connections they made. The most dominant type of NAT/firewall is EIM-APDF (52%). This includes both simple firewalls and EIM NATs. Theoretically these can connect to each other through a rendez-vous peer. The fraction of peers that are behind A(P)DM NATs is only 11%. These NAT/firewalls are the biggest obstacle, i.e. they can only connect to EIM-EIF and EIM-ADF peers. The fraction of A(P)DM NATs is expected to go down, as more and more vendors start complying with the BEHAVE RFC [START_REF] Audet | Network Address Translation (NAT) Behavioral Requirements for Unicast UDP[END_REF].

Connection Success Rate

Next we look at the success rate in setting up a connection between two peers. For this we only consider those connections for which we have information on both ends of the connection, and for which we were able to determine the NAT/firewall type of both peers. Our results therefore represent 15,545 connections between 841 peers. We have split the results out into the different NAT/firewall types we have distinguished (see Table 1). A first thing to note about the results is that even peers classified as EIM-EIF only show an 85% success rate. Detailed analysis of the results shows that this is caused by a small fraction of peers that consistently show poor connectability (see Figure 4). Perhaps they are experiencing high packet losses due to a saturated link. As the puncturing test is running in the background of a BitTorrent client this is certainly not impossible.

To test our hypothesis, we tried to reproduce the packet dropping behaviour in a local test environment using (new) NAT routers. Using TCP side traffic to saturate the links, we were only able to produce small packet loss rates (≤ 5%). To see whether other methods of stressing the routers would produce different results, we also performed a similar test using UDP side traffic. Using large volumes of UDP packets we could get some routers to drop significant numbers of packets (50% or more), or even crash completely.

We must stress that we used newly acquired NAT routers, which may be more resilient to the BitTorrent-like stress test that we subject these routers to. Unfortunately, we currently do not have older router and modem models, which may be more susceptible to dropping packets under high TCP load. Also, although the consumer-grade NAT/firewalls are the prime suspect for dropping packets, they are by no means the only possible point at which packets may be dropped. Therefore we can not discount packet loss as a cause for reduced connection success rates.

Another possibility is that certain routers stop functioning correctly when their mapping tables are full. This is a well-known problem with some older types of routers, when used in combination with BitTorrent. Note that this does not mean they do not function at all, but new connections can usually not be set up anymore, and existing connections can experience significant throughput reductions. A peer behind such a router may still be reachable over the existing connections, but all new connection attempts will fail, thereby reducing the connection success rate.

The connections between EIM-ADF peers and EIM-A(P)DF peers succeed a little more often than the connections between EIM-EIF peers, but this result is not statistically significant as only 36 peers in our test are behind a EIM-ADF type NAT/firewall.

Connections to and from peers behind EIM-APDF NAT/firewalls succeed a little less frequently than the connections between EIM-EIF peers. This is not entirely unexpected. As already noted in the RFC describing the STUN protocol [START_REF] Rosenberg | Session Traversal Utilities for NAT (STUN). RFC 5389 (Proposed Standard)[END_REF], even though two peers should be able to communicate given the classification determined here, subtleties in the actual implementation may prevent actual connection setup (see also Section 5.2). Conversely, peers which should not be able to connect due to incompatible NAT/firewall types can on occasion setup a connection due to similar implementation subtleties.

Behavioural Subtleties In our analysis of the collected logs, we found several behaviours in NAT boxes that are not well described by the classification we have used so far. For example, we found that several EIM-APDF NATs would occasionally use a different external port (similar to A(P)DM NAT behaviour). This is one reason why these NATs have lower connection success rates.

A second notable behaviour occurs in A(P)DM NATs. The conventional idea is that these NATs will use a different port for each remote endpoint. However, some A(P)DM NATs appear to use a small set of ports repeatedly. So although it is uncertain which of these ports will be used, there is only a small set to choose from. This could explain why sometimes a connection between an A(P)DM NAT and an EIM-APDF NAT/firewall does succeed: because the set is small there is a chance that the EIM-APDF NAT/firewall actually uses the port that is chosen by the A(P)DM NAT, allowing the packet to arrive. This may also explain why sometimes the connections between two A(P)DM NATs succeed.

A(P)DM to EIM-ADF First Attempt Success One very interesting result can be seen in the connections from A(P)DM peers to EIM-ADF peers. If we assume that a packet sent directly between peers A and B will arrive before a packet sent at the same time but via a third peer, then the direct connection request will always arrive before the reverse connection request has punched a hole. This results in the direct connection request being dropped at the NAT/firewall. If we consider the case where an A(P)DM peer is the originating peer, the reverse connection request sent from the EIM-ADF peer will also very likely not arrive at the port that the direct connection request was sent from, causing the packet to be dropped. This means that given the above assumption, we would expect that connection attempts from A(P)DM peers to EIM-ADF peers will always fail the first time. For the second and later attempts, the firewall on the EIM-ADF side will already have been opened for connections from the A(P)DM peer by the reverse connection request of the first attempt, allowing the direct connection request to pass through.

As we can see from the results, the first connection attempt does succeed in approximately 41% of the cases. The reason for this is that the direct connection request is not always faster than the reverse connection request which is sent through the rendez-vous peer. This is known as a Triangle Inequality Violation (TIV). It is well known that TIVs exist in the round-trip time between nodes [START_REF] Savage | Detour: A case for informed internet routing and transport[END_REF][START_REF] Tang | Virtual landmarks for the internet[END_REF][START_REF] Zheng | Internet routing policies and roundtrip-times[END_REF]. Our connection setup is dependent on one-way delay, and not round-trip time, but many of the underlying causes such as routing policies and peering agreements will affect the one-way delay as well. Studies of TIVs in roundtrip time seem to indicate that the occurrence of TIVs can be as high as 40%, although lower numbers are more common.

Another possible explanation for TIVs specific to our situation is that there is network equipment which requires some setup time when a packet needs to be sent to a host (or AS) with which it has not recently communicated. The consumer-grade NAT/firewalls are of course a first suspect for such behaviour, but an exploratory test with a small number of such boxes did not find any significant extra delay. The only source of extra delay in communicating with "new" IP addresses that we were able to find is the ARP protocol used in LANs. However, in our situation it is unlikely that the ARP protocol is the cause of TIVs.

Finally, there are other, albeit unlikely, possibilities for the first attempt to succeed. First, it is possible that some EIM-ADF firewalls have very long mapping/filter timeouts. If, after closing the connection, an A(P)DM peer tries to establish a new connection before the mapping/filter has timed out, the first attempt could succeed. To prevent such situations we did not allow new connections within 5 minutes, but this could be too short. Second, the two peers could simultaneously try to connect to each other. However, similarly to the pre- vious explanation, the chances of such an occurrence are very small. Third, the previously mentioned behavioural subtleties may explain a small fraction of the successful connections as well. If the A(P)DM NAT uses only a small number of ports, this significantly increases the chance that the EIM-ADF peer actually attempts the reverse connection to the port the A(P)DM NAT is expecting, in which case the connection setup will succeed.

Timeout

A final measurement we made was the timeout for the mappings/firewall holes. This parameter is important when setting the keep-alive interval. To measure the timeout, we sent UDP packets to a pre-programmed IP address and port, after which a reply was sent with a delay. If the reply was received, the timeout was determined to be larger than the delay of the reply. The largest timeout for which a message was received was determined to be the approximate timeout for the mapping/firewall hole.

To ensure a rapid measurement, several messages requesting replies at different delays were sent at the same time from different ports. This setup can give wrong results for some EIM-ADF NAT/firewalls which refresh the timeout for incoming traffic as well as for outgoing traffic. Doing so is a security risk, so we expect few firewalls to behave this way. However, we have for this reason excluded the (small number) of EIM-ADF NAT/firewalls from our analysis.

The graph on the left in Figure 5 shows the results of this measurement. These results indicate that many firewalls employ a fairly short timeout (1 minute or less) for the created mappings/firewall holes. However, some NAT/firewalls, particularly those based on the Linux kernel, use a longer timeout if more than two packets have been sent on a particular mapping/firewall hole, and at least one packet has passed in both directions. We therefore also measured the timeout where we include an initial handshake before requesting the delayed reply. The results are shown in the graph on the right in Figure 5. The results are markedly different. Most of the NAT/firewalls that have a 30 second timeout without the handshake now use a much longer timeout. The default value in the Linux kernel is 180 seconds, which may explain the large fraction of peers with that timeout when using an initial handshake. These differences between single packet timeouts and timeouts after an initial handshake are also demonstrated in [START_REF] Hätönen | An experimental study of home gateway characteristics[END_REF].

Discussion

In the previous section we have seen that NAT/firewalls do not always behave as simple as the traditional classifications have suggested. The result of this is that both connections that are expected to succeed do not, and vice versa. Although there seems to be a convergence towards BEHAVE compatible NAT behaviour (as can be seen by the very small number of A(P)DM NAT boxes that are available from stores today), it is unlikely that all behavioural anomalies will fully disappear.

Our results confirm that over three quarters of the peers on the Internet (79%) are not directly connectable. The lack of connectability has long been recognised as a problem in P2P networks [START_REF] Ford | Peer-to-peer communication across network address translators[END_REF][START_REF] Liu | The impact of NAT on BitTorrent-like P2P systems[END_REF], especially in video streaming [START_REF] Mol | The design and deployment of a bittorrent live video streaming solution[END_REF]. However, using a simple rendez-vous mechanism, a further 64% of all peers could potentially set up connections between themselves when using UDP. This would reduce the connectability problem to a mere 15% of peers, practically eliminating the problem for most P2P applications.

Some have suggested that the problem of NATs obstructing connectability will go away with the introduction of IPv6. However, it should be noted that most of the problems today are not so much caused by the NAT behaviour, but rather by the filtering. The vast majority of NAT/firewalls today are of the EIM-A(P)DF type, which means that their externally visible endpoint is constant and therefore not a big obstacle for connectability. The remaining problems are caused by the filtering behaviour, and it is likely that home routers will continue to include firewalling by default, even when the switch to IPv6 is made. As such, the connectability problems will continue to exist and the puncturing techniques studied in this paper will remain an important tool to overcome these problems.

Conclusions

In this paper we have presented the results of a real implementation of UDP NAT and firewall puncturing, running on random Internet users' machines. Our implementation makes minimal use of central components. Most notably, peers detect their NAT and firewall types solely through communication with other peers.

Our results show that connectable (EIM-EIF) peers form a small minority (21%) on the Internet, and that most NATed and firewalled peers (64% of all peers, EIM-A(P)DF) should theoretically be able to set up connections through a simple rendez-vous mechanism when using UDP. Our results also show that connections between these peers can indeed be set up, with a success rate only fractionally lower than for connectable peers. As these hosts are the majority of the peers in Peer-to-Peer networks, we conclude that there is a large opportunity for UDP based Peer-to-Peer protocols to set up many more connections and therefore create a more robust network.

Finally, our measurements of the NAT mapping/firewall hole timeout show that keep-alive message should be sent at least every 55 seconds to ensure that mappings/holes will remain open on almost every NAT/firewall. This assumes that several messages are exchanged within the first 30 seconds, because some NAT/firewalls extend their timeout if there is more traffic than a simple request and reply.

Fig. 1 .

 1 Fig. 1. When a NAT exhibits Endpoint-Independent Mapping (EIM) behaviour, hosts A and B see the same external IP address and port (Y:y) for a particular internal IP and port combination (X:x). If however the NAT type is Address (and Port)-dependent Mapping, hosts A and B see different IP/port combinations (Y:y and Z:z). Note that the IP addresses (Y and Z) can be the same, especially if the NAT has only a single external address.

Fig. 2 .

 2 Fig. 2. Rendez-vous for connection setup.

Fig. 3 .

 3 Fig. 3. NAT/firewall type market share

Fig. 4 .

 4 Fig.[START_REF] Guha | Characterization and measurement of tcp traversal through nats and firewalls[END_REF]. Cumulative distribution of per peer connection success rate, counting only connections attempts between compatible peers. Connections to peers with lower success rates are not counted against peers with a higher connection success rate.

Fig. 5 .

 5 Fig. 5. Mapping/firewall hole timeout without (left) and with (right) handshake.

Table 1 .

 1 Connection success rate per NAT/firewall type. Each bar shows the successful attempts, where retries are shown as increasingly darker shades of green.

	From	To EIM-EIF	EIM-APDF	EIM-ADF	A(P)DM
	EIM-EIF
	EIM-APDF
	EIM-ADF
	A(P)DM

This work was partially supported by the European Community's 7th Framework Programme through the P2P-Next and QLectives projects (grant no. 216217, 231200).


Molazem Farid

Joseph Tabrizi

Mohamed Peters
email: peters@cs.sfu.ca

Hefeeda
email: mhefeeda@cs.sfu.ca

Adaptive Transmission of Variable-Bit-Rate Video Streams to Mobile Devices

Keywords: Mobile Video Streaming, Mobile Broadcast Networks, Energy Saving

We propose a novel algorithm to efficiently transmit multiple variable-bit-rate (VBR) video streams from a base station to mobile receivers in wide-area wireless networks. The algorithm transmits video streams in bursts to save the energy of mobile devices. A key feature of the new algorithm is that it dynamically controls the buffer levels of mobile devices receiving different video streams according to the bit rate of the video stream being received by each device. Our algorithm is adaptive to the changes in the bit rates of video streams and allows the base station to transmit more video data on time to mobile receivers. We have implemented the proposed algorithm as well as two other recent algorithms in a mobile video streaming testbed. Our extensive analysis and results demonstrate that the proposed algorithm outperforms two other algorithms and it results in higher energy saving for mobile devices and fewer dropped video frames.

Introduction

Due to advances in mobile devices such as increased computing power and screen size, the demand for mobile multimedia services has been increasing in recent years [START_REF]Global IPTV market analysis[END_REF]. However, video streaming to mobile devices still has many challenges that need to be addressed. For example, mobile devices are small and can only be equipped with small batteries that have limited lifetimes. Thus, conserving the energy of mobile devices during streaming sessions is needed to prolong the battery lifetime and enable users to watch videos for longer periods. Another challenge for mobile video is the limited wireless bandwidth in wide-area wireless networks. The wireless bandwidth is not only limited, but it is also quite expensive. For instance, Craig Wireless System Ltd. agreed to sell one quarter of its wireless spectrum to a joint venture of Rogers Communication and Bell Canada for $80 million [START_REF]Craig wireless to sell canadian spectrum for $80m[END_REF], and AT&T sold a 2.5 GHz spectrum to Clearwire Corporation in a $300 million transaction [START_REF]AT&T sells wireless spectrum in southeast to Clearwire corporation[END_REF]. Thus, for commercially viable mobile video services, network operators should maximize the utilization of their license-based wireless spectrum bands.

In this paper, we consider the problem of multicasting multiple video streams from a wireless base station to many mobile receivers over a common wireless channel. This problem arises in wide-area wireless networks that offer multimedia content using multicast and broadcast services, such as DVB-H (Digital Video Broadcast-Handheld) [START_REF] Kornfeld | DVB-H and IP Datacast -broadcast to handheld devices[END_REF], ATSC M/H (Advanced Television Systems Committee-Mobile/Handheld) [START_REF]ATSC mobile DTV standard[END_REF], WiMAX [6], and 3G/4G cellular networks that enable the Multimedia Broadcast Multicast Services (MBMS) [START_REF] Parkvall | Evolving 3G mobile systems: Broadband and broadcast services in WCDMA[END_REF]. We propose a new algorithm to efficiently transmit the video streams from the base station to mobile receivers. The transmission of video streams is done in bursts to save the energy of mobile devices. Unlike previous algorithms in the literature, e.g. [START_REF] Hsu | On statistical multiplexing of variable-bit-rate video streams in mobile systems[END_REF][9][START_REF] Yang | Performance analysis of time slicing in DVB-H[END_REF][START_REF] Hsu | Time slicing in mobile TV broadcast networks with arbitrary channel bit rates[END_REF][START_REF] Tabrizi | Optimal scalable video multiplexing in mobile broadcast networks[END_REF], the new algorithm adaptively controls the buffer levels of mobile devices receiving different video streams. The algorithm adjusts the buffer level at each mobile device according to the bit rate of the video stream being received by that device. The algorithm also uses variable-bit-rate (VBR) video streams, which are statistically multiplexed to increase the utilization of the expensive wireless bandwidth. By dynamically adjusting the receivers' buffers, our algorithm enables finer control of the wireless multicast channel and allows the base station to transmit more video data on time to mobile receivers.

We have implemented our new algorithm in an actual mobile video streaming testbed that fully complies with the DVB-H standard. We have also implemented the recent algorithm proposed in [START_REF] Hsu | On statistical multiplexing of variable-bit-rate video streams in mobile systems[END_REF] and an algorithm used in some commercial base stations for broadcasting VBR video streams [13], which we know through private communication [START_REF]Private communication with Nokia's engineers managing mobile TV base stations[END_REF]. Our empirical results demonstrate the practicality of our new algorithm. Our results also show that our algorithm outperforms other algorithms as it delivers more video frames on-time to mobile receivers and it achieves high energy saving for mobile receivers.

The rest of this paper is organized as follows. We review related work in Section 2. In Section 3, we describe the wireless network model that we consider and we state the problem addressed in this paper. We present the proposed algorithm in Section 4. We empirically evaluate our algorithm and compare it against others in Section 5. We conclude the paper in Section 6.

Related work

Energy saving at mobile receivers using burst transmission (aka time slicing) has been studied in [9,[START_REF] Yang | Performance analysis of time slicing in DVB-H[END_REF]. Simulations are used in these studies to show that time slicing can improve energy saving for mobile receivers. However, no burst transmission algorithms are presented. Burst transmission algorithms for constantbit-rate (CBR) video streams are proposed in [START_REF] Hsu | Time slicing in mobile TV broadcast networks with arbitrary channel bit rates[END_REF][START_REF] Hefeeda | On burst transmission scheduling in mobile TV broadcast networks[END_REF]. These algorithms cannot handle VBR video streams with fluctuating bit rates. In this paper, we consider the more general VBR video streams which can achieve better visual quality and bandwidth utilization [16]. In [START_REF] Tabrizi | Optimal scalable video multiplexing in mobile broadcast networks[END_REF], we presented a burst transmission technique designed for scalable video streams. The algorithm in [START_REF] Tabrizi | Optimal scalable video multiplexing in mobile broadcast networks[END_REF] adjusts the number of transmitted quality layers based on the available bandwidth. However, unlike the algorithm presented in this paper, our previous algorithm does not support VBR streams, nor does is dynamically adjusts the receivers' buffers. In addition, the new algorithm in this paper is designed for single-layer VBR video streams, which are currently the most common in practice.

Transmitting VBR video streams over a wireless channel while avoiding buffer overflow and underflow at mobile devices is a difficult problem [START_REF] Rezaei | Video streaming over[END_REF]. Rate smoothing is one approach to reducing the complexity of this problem. The smoothing algorithms in [START_REF] Lai | A monotonic-decreasing rate scheduler for variablebit-rate video streaming[END_REF][START_REF] Lin | FOS: A funnel-based approach for optimal online traffic smoothing of live video[END_REF] reduce the complexity by controlling the transmission rate of a single video stream to produce a constant bitrate stream. The minimum requirements of rate smoothing algorithms in terms of playback delay, lookahead time, and buffer size are discussed in [START_REF] Thiran | Network calculus applied to optimal multimedia smoothing[END_REF]. The on-line smoothing algorithm in [START_REF] Sen | Online smoothing of variablebit-rate streaming video[END_REF] reduces the peak bandwidth requirements for video streams. However, none of these smoothing algorithms is designed for mobile multicast/broadcast networks with limited-energy receivers. A different approach to handling VBR video streams is to employ joint rate control algorithms. For example, Rezaei et al. [START_REF] Rezaei | Joint video coding and statistical multiplexing for broadcasting over DVB-H channels[END_REF] propose an algorithm to assign bandwidth to video streams proportional to their coding complexities. This algorithm, however, requires expensive joint video encoders. A recent algorithm for transmitting VBR video streams to mobile devices without requiring joint video encoders is presented in [START_REF] Hsu | On statistical multiplexing of variable-bit-rate video streams in mobile systems[END_REF]. This algorithm, called SMS, performs statistical multiplexing of video streams. SMS divides the receivers' buffers into two equal parts, one for receiving data, and the other for playing out video. The proposed algorithm in this paper outperforms SMS because it dynamically controls the wireless channel and the buffer levels of the receivers. This allows the base station to exploit the varying nature of VBR streams in order to transmit more video frames on time.

The VBR transmission algorithms deployed in practice are simple heuristics. For example, in the Nokia Mobile Broadcast Solution (MBS) [13,[START_REF]Private communication with Nokia's engineers managing mobile TV base stations[END_REF], the operator determines a bit rate value for each video stream and a time interval based on which bursts are transmitted. The time interval is calculated on the basis of the size of the receiver buffers and the largest bit rate among all video streams, and this time interval is used for all video streams to avoid buffer overflow instances at the receivers. In each time interval, a burst is scheduled for each video stream based on its bit rate. In practice, it is difficult for an operator to assign bit rate values to VBR video streams to achieve good performance while avoiding buffer underflow and overflow instances at the receivers. In this paper, we compare our proposed algorithm to the SMS algorithm [START_REF] Hsu | On statistical multiplexing of variable-bit-rate video streams in mobile systems[END_REF] (which represents the state-ofthe-art in the literature) as well as to the algorithm used in the Nokia Mobile Broadcast Solution (which represents one of the state-of-the-art algorithms in practice).

System Model and Problem Statement

We study the problem of transmitting several video streams from a wireless base station to a large number of mobile receivers. We focus on multicast and broadcast services enabled in many recent wide-area wireless networks such as DVB-H [START_REF] Kornfeld | DVB-H and IP Datacast -broadcast to handheld devices[END_REF], MediaFLO [23], WiMAX [6], and 3G/4G cellular networks that offer Multimedia Broadcast Multicast Services (MBMS) [START_REF] Parkvall | Evolving 3G mobile systems: Broadband and broadcast services in WCDMA[END_REF]. In such networks, a portion of the wireless spectrum can be set aside to concurrently broadcast multiple video streams to many mobile receivers. Since the wireless spectrum in wide-area wireless networks is license-based and expensive, maximizing the utilization of this spectrum is important. To achieve high bandwidth utilization, we employ the variable-bit-rate (VBR) model for encoding video streams. Unlike the constant-bit-rate (CBR) model, the VBR model allows statistical multiplexing of video streams [START_REF] Hsu | On statistical multiplexing of variable-bit-rate video streams in mobile systems[END_REF], and yields better perceived video quality [16]. However, the VBR model makes video transmission much more challenging than the CBR model in mobile video streaming networks [START_REF] Rezaei | Video streaming over[END_REF].

Mobile receivers are typically battery powered. Thus, reducing the energy consumption of mobile receivers is essential. To save energy, we employ the burst transmission model for transmitting video streams, in which the base station transmits the data of each video stream in bursts with a bit rate higher than the encoding bit rate of the video. The burst transmission model allows a mobile device to save energy by turning off its wireless interface between the reception of two bursts [START_REF] Hefeeda | On burst transmission scheduling in mobile TV broadcast networks[END_REF][START_REF] Rezaei | Video streaming over[END_REF]. The arrival time of a burst is included in the header of its preceding burst. Thus, the clocks at mobile receivers do not need to be synchronized. In addition, each receiver is assumed to have a buffer to store the received data. Figure 1 shows a high-level depiction of the system model that we consider.

To achieve the burst transmission of video streams described in Figure 1, we need to create a transmission schedule which specifies for each stream the number of bursts, the size of each burst, and the start time of each burst. Note that only one burst can be transmitted on the broadcast channel at any time. The problem we address in this paper is to design an algorithm to create a transmission schedule for bursts that yields better performance than current algorithms in the literature.

In particular, we study the problem of broadcasting S VBR video streams from a base station to mobile receivers in bursts over a wireless channel of bandwidth R Kbps. The base station runs the transmission scheduling algorithm every Γ sec; we call Γ the scheduling window. The base station receives the video data belonging to video streams from streaming servers and/or reads it from local video databases. The base station aggregates video data for Γ sec. Then, it computes for each stream s the required number of bursts. We denote the size of burst k of video stream s by b s k (Kb), and the transmission start time for it by f s k sec. The end time of the transmission for burst k of stream s is

f s k + b s k /R sec.
After computing the schedule, the base station will start transmitting bursts in the next scheduling window. Each burst may contain multiple video frames. We denote the size of frame i of video stream s by l s i (Kb). Each video frame i has a decoding deadline, which is i/F , where F is the frame rate (fps). The goals of our scheduling algorithm are: (i) maximize the number of frames delivered on time (before their decoding deadlines) for all video streams, and (ii) maximize the average energy saving for all mobile receivers. We define the average energy saving as γ = S s=1 γ s /S, where γ s is the fraction of time the wireless interfaces of the receivers of stream s are turned off.

Proposed Algorithm

Overview

We start by presenting an overview of the proposed algorithm and then we present the details. We have proved that our algorithm produces near-optimal energy saving and that it runs in time O(N S), where S is the number of video streams and N is the total number of control points defined for the video streams, but we have omitted the proofs due to space limitations.

We propose a novel algorithm, which we call the Adaptive Data Transmission (ADT) algorithm, to solve the burst transmission problem for the VBR video streams described in Section 3. The key idea of the algorithm is to adaptively control the buffer levels of mobile devices receiving different video streams using dynamic control points. The buffer level at each mobile device is adjusted as a function of the bit rate of the video stream being received by that device. Since we consider VBR video streams, the bit rate of each video is changing with time according to the visual characteristics of the video. This means that the buffer level at each mobile device is also changing with time. The receiver buffer level is controlled through the sizes and timings of the bursts transmitted by the base station in each scheduling window. The sizes and timings of the transmitted bursts are computed by the proposed ADT algorithm at dynamically defined control points. Dynamic control points provide flexibility to the base station so that the algorithm has more control over the bandwidth when the bit rates of video streams increase. This results in transmitting more video data on time to mobile receivers.

The ADT algorithm defines control points at which it makes decisions about which stream should have access to the wireless medium and for how long it should have access. Control points for each video stream are determined based on a parameter α, where 0 < α < 1. This parameter is the fraction of B, the receiver's buffer, that is played out between two control points of a video stream. The parameter α can change dynamically between scheduling windows but is the same for all video streams. At a given control point, the base station selects a stream and computes the buffer level of the receivers for the selected stream and can transmit data as long as there is no buffer overflow at the receivers. Our algorithm is designed for broadcast networks where there is no feedback channel, so we cannot know the buffer capacity of every receiver. We assume B to be the minimum buffer capacity for the receivers. Therefore, the receivers have a buffer capacity of at least B Kb and our solution still works if some of them have larger buffer capacities.

For small values of α, control points are closer to each other (in time) which results in smaller bursts. This gives the base station more flexibility when deciding which video stream should be transmitted to meet its deadline. That is, the base station has more opportunities to adapt to the changing bit rates of the different VBR video streams being transmitted. For example, the base station can quickly transmit more bursts for a video stream experiencing high bit rate in the current scheduling window and fewer bursts for another stream with low bit rate in the current scheduling window. This dynamic adaptation increases the number of video frames that meet their deadlines from the high-bit rate stream while not harming the low-bit rate stream. However, smaller bursts may result in less energy saving for the mobile receivers.Each time that a wireless interface is turned on, it incurs an energy overhead because it has to wake up shortly before the arrival of the burst to initialize its circuits and lock onto the radio frequency of the wireless channel. We denote this overhead by o , which is on the order of msec depending on the wireless technology.

Details

The proposed ADT algorithm is to be run by the wireless base station to schedule the transmission of S video streams to mobile receivers. The algorithm can be called periodically every scheduling window of length Γ sec, and whenever a change in the number of video streams occurs.

We define several variables that are used in the algorithm. Each video stream s is coded at F fps. We assume that mobile receivers of video streams have a buffer capacity of B Kb. We denote the size of frame i of video stream s by l s i (Kb). We denote the time that the data in the buffer of a receiver of stream s can be played out by d s sec. This means that it takes d s sec until the buffer of a receiver of video stream s is drained. We use the parameter M (Kb) to indicate the maximum size of a burst that could be scheduled for a video stream in our algorithm when there are no other limitations like buffer size. In some wireless network standards, there might be limitations on the value of M . A control point is a time when the scheduling algorithm decides which stream should be assigned a burst. A control point for video stream s is set every time the receiver has played out αB Kb of video data.

Let us assume that the algorithm is currently computing the schedule for the time window t start to t start + Γ sec. The algorithm defines the variable t schedule and sets it equal to t start . Then, the algorithm computes bursts one by one and keeps incrementing t schedule until it reaches the end of the current scheduling window, i.e., t start ≤ t schedule ≤ t start + Γ . For instance, if the algorithm schedules a burst of size 125 Kb on a 1 Mbps bandwidth, then the length of this burst will be 0.125 sec and the algorithm increments t schedule by 0.125 sec. The number of video frames of video stream s that are sent until time t schedule is denoted by m s . The number of frames of stream s that are played out at the receiver side of stream s until time t schedule is p s = min(m s , t schedule × F ). If p s < m s , then frames p s + 1 to m s are still in the receivers' buffers. If p s = m s , then the buffers of the receivers of video stream s are empty. In this case, the receivers of video stream s are waiting for data and if m s < t schedule × F , some video frames were not received on time. We define the playout deadline for stream s as:

d s = (m s -p s )/F. ( 1
)
The next control point h s of stream s after time t schedule will be when the receivers of stream s have played out αB Kb of video data. We compute the number of frames g s corresponding to this amount as follows:

ps+gs i=ps l s i ≤ αB < ps+gs+1 i=ps l s i . (2)
The control point h s is then given by:

h s = t schedule + g s /F. (3)
The high-level pseudo-code of the ADT algorithm is given in Figure 2. The algorithm works as follows. At each control point, the algorithm finds the stream s ′ which has the closest deadline d s ′ . Then it finds the stream s ′′ with the closest control point h s ′′ . Then the algorithm schedules a burst for stream s ′ until the control point h s ′′ if this does not exceed the maximum burst size M or the available buffer space at the receivers of s ′ . Otherwise, the size of the new burst is set to the minimum of M and the available buffer space. The algorithm repeats the above steps until there are no more bursts to be transmitted from the video streams in the current scheduling window, or until t schedule exceeds t start +Γ and there remains data to be transmitted. The latter case means that some frames will not be transmitted. In this case, the algorithm tries to find a better schedule by increasing the number of control points to introduce more flexibility. This is done by dividing α by 2. After decreasing α, the algorithm resets t schedule to be t start and computes a new schedule. The algorithm keeps decreasing α until it reaches a preset minimum value α min or a schedule with all frames transmitted on time is found. If α is reduced in a scheduling window, then it will be gradually increased in the following scheduling windows.

Evaluation

Testbed and Setup

The testbed that we used to evaluate our algorithm consists of a base station, mobile receivers, and data analyzers. The base station includes an RF signal Adaptive Data Transmission (ADT) Algorithm // Input: S VBR video streams // Output: Burst schedule to transmit S video streams 1. compute control points and deadlines for each stream s 2. while there is a video stream to transmit { 3.

create a new scheduling window from t start to t start + Γ 4.

while the current scheduling window is not complete { 5.

pick video stream s having the earliest deadline 6.

schedule a burst until the next control point or until the buffer is full 7.

update t schedule based on the length of scheduled burst 8.

//gradually increase α if it was reduced in previous scheduling windows 9.

if α < α max and α was not reduced in the current scheduling window 10.

update α (increase linearly) 11.

update d s h (control point) for video stream s 12.

if there is a stream s ′ which is late and α > α min 13.

//go back within the scheduling window and reschedule bursts 14.

update t schedule to t start 15.

update α (decrease by a factor of 2) 16. else 17.

move to next control point greater than or equal to t schedule 18. } 19. } Fig. 2. The proposed transmission scheduling algorithm. modulator which produces DVB-H standard-compliant signals. The signals are amplified to around 0 dB before transmission through a low-cost antenna to provide coverage to approximately 20m for cellular phones. The mobile receivers in our testbed are Nokia N96 cell phones that have DVB-H signal receivers and video players. Two DVB-H analyzers are included in the testbed system. The first one, a DiviCatch RF T/H tester [START_REF]Divi Catch RF-T/H transport stream analyzer[END_REF], has a graphical interface for monitoring detailed information about the received signals, including burst schedules and burst jitters. The second analyzer, a dvbSAM [START_REF]dvbSAM DVB-H solution for analysis, monitoring, and measurement[END_REF], is used to access and analyze received data at the byte level to monitor the correctness of the received content.

We implemented our ADT algorithm, the SMS algorithm [START_REF] Hsu | On statistical multiplexing of variable-bit-rate video streams in mobile systems[END_REF], and the Nokia Mobile Broadcast Solution (MBS) [13,[START_REF]Private communication with Nokia's engineers managing mobile TV base stations[END_REF], in the testbed and integrated them with the IP encapsulator of the transmitter. We set the modulator to a QPSK (Quadrature Phase Shift Keying) scheme and a 5 MHz radio channel, and the overhead T o was set to 100 msec. We fixed the maximum receiver buffer size B be 4 Mb (500 KB). We prepared a test set of 17 diverse VBR video streams to evaluate the algorithms. The different content of the streams (TV commercials, sports, action movies, documentaries) provided a wide range of video charac- teristics with average bitrates ranging from 25 kbps to 750 kbps and a ratio of minimum frame size to maximum frame size of nearly 300. Each video stream was played at 30 fps and had length of 566 sec. We transmitted the 17 VBR video streams concurrently to the receivers and we collected detailed statistics from the analyzers. Each experiment was repeated for each of the three algorithms (ADT, SMS, and MBS).

Results for Dropped Video Frames

Dropped frames are frames that are received at the mobile receivers after their decoding deadlines or not received at all. The number of dropped frames is an important quality of service metric as it impacts the visual quality and smoothness of the received videos. Figure 3 shows the cumulative total over all video streams of the numbers of dropped frames for ADT with fixed values of α ranging from 0.10 to 0.50, and for SMS and MBS. The figure clearly shows that our ADT algorithm consistently drops significantly fewer frames than the SMS and MBS algorithms. The figure also shows the effect of decreasing the value of α for our ADT algorithm. The total number of dropped frames decreases from 24,742 with α = 0.50 to 7,571 with α = 0.20. No frames are dropped when α is reduced to 0.10. On the other hand, the SMS algorithm is significantly worse with 58,450 dropped frames. The results for MBS in Figure 3 were obtained by running the algorithm for each video stream with different assigned bit rates ranging from 0.25 times the average bit rate to 4 times the average bit rate of the video stream and then choosing the best result for each video stream. Even in this total of best cases, the number of dropped frames is more than 75,700. In practice, an operator heuristically chooses the assigned bit rates for video streams, so the results in practice likely will be worse.

We counted the number of dropped frames for each video stream to check whether the ADT algorithm improves the quality of some video streams at the expense of others. A sample of our results is shown in Figure 4; others are similar for different values of α. The curve in the figure shows the average over all streams of the percentage of dropped frames; each point on the curve is the average percentage of frames transmitted to that point in time that were dropped. The bars show the ranges over all video streams. As shown in the figure, the difference between the maximum and minimum dropped frame percentages at the end of the transmission period is very small. Therefore, the ADT algorithm does not sacrifice the quality of service for some streams to achieve good aggregate results.

We further analyzed the patterns of dropped video frames for each algorithm by plotting the total number of dropped frames during each 1 sec interval across all video streams. Some samples of our results are shown in Figure 5. For the ADT algorithm, reducing α from 0.50 to 0.20 resulted in finer control over the bandwidth allocation and significantly fewer frames were dropped. Further reducing α to 0.10 eliminated all dropped frames as we have already seen in Figure 3. The SMS algorithm on the other hand dropped up to 72% of the frames during the period in which the aggregate bit rate of all streams is high.

Results for Energy Saving

We compute the average energy saving γ achieved across all video streams, which represents the average amount of time that the wireless interface is in off mode. This is done based on the formulation for average energy saving described in Section 3. The results are shown in Figure 6. The figure also shows the impact of changing α on the energy saving achieved by the ADT algorithm. The average over all video streams of the energy saving is 87.59% for the ADT algorithm when α = 0.10 which is approximately the same as the SMS algorithm. Increasing α to 0.50 increases the energy saving to 93.08%. The small improvement of 5.49% in energy saving is non-trivial but it might not be large enough in many practical situations to offset the advantage of minimizing the number of dropped frames by setting α = 0.10. Also, our experiments show that the energy saving achieved by ADT is considerably higher than MBS, which achieves average energy saving of 49%. We measured the energy saving for the receivers of each individual stream to check whether the ADT algorithm unfairly saves more energy for some receivers at the expense of others. A sample of our results is shown in Figure 7. The figure confirms that ADT does not sacrifice energy saving in some streams to achieve good average energy saving.

Conclusions

We have presented a new algorithm for transmitting multiple VBR video streams to energy-constrained mobile devices. The algorithm is to be used by wireless base stations in wide-area wireless networks that offer multimedia services in broadcast/multicast modes such as the MBMS (Multimedia Broadcast Multicast Service) of 3G/4G cellular networks, WiMAX networks, and DVB-H (Digital Video Broadcast-Handheld) networks. One of the novel aspects of the proposed algorithm is its ability to dynamically adjust the levels of receivers' buffers according to the bit rates of the video streams being received by each receiver. We presented a proof-of-concept implementation of the proposed algorithm in a mobile video streaming testbed. We also compared the new algorithm to recent algorithms in the literature and used in practice. We conducted an extensive empirical analysis using a large number of VBR video streams with diverse visual characteristics and bit rates. Our results show that the proposed algorithm yields high energy saving for mobile receivers and reduces the number of video frames that miss their deadlines. The results also demonstrate that the proposed algorithm outperforms the current state-of-the-art algorithms.

Fig. 1 .

 1 Fig. 1. The wireless network model considered in this paper.

Fig. 3 .Fig. 4 .Fig. 5 .

 345 Fig. 3. Total number of dropped video frames.

10 Fig. 6 .Fig. 7 .

 1067 Fig. 6. Average energy saving.


Chenguang Kong
email: cgkong@cs.hku.hk

Chuan Wu

Victor O K Li

SMS: Collaborative Streaming in Mobile Social Networks

Keywords: Applications and Services, Mobile Social Networks, Peer-Assisted Streaming

Mobile social applications have emerged in recent years. They explore social connections among mobile users in a variety of novel scenarios, including friend finding, message routing, and content sharing. However, efficiently supporting resource-demanding delay-sensitive streaming applications on the mobile platform remains a significant challenge. In this paper, we study collaborative VoD-type streaming of short videos among small groups of mobile users, so as to effectively exploit their social relationships. Such an application is practically set in a number of usage scenarios, including streaming of introductory video clips of exhibition items to visitors' mobile devices, such as in a museum. We design SMS, an architecture that engineers such Streaming over Mobile Social networks. SMS constructs a collaborative streaming overlay by carefully inspecting social connections among users and infrastructural characteristics of Bluetooth technologies. We evaluate our design based on prototype implementation on the Android platform.

Introduction

Novel mobile social applications have emerged in recent years. They explore advanced mobile technologies and social connections among mobile users for interactions and exchanges anywhere at any time. Representative mobile social networks can be grouped into two categories. Mobile social networks in the first category are a natural extension of online social networks over the Internet, where users participate in Facebook-like social applications using their mobile devices, e.g., Tencent QQ [3], Cyworld [2], both of which are enabled with web and mobile access. Exploiting geographic positions of the mobile users, locationbased features may be added, such as sharing of geotagged photos and news captured by mobile devices. In the second category, mobile users in physical proximity directly connect with each other, for friend making based on common interest (e.g., MagnetU [START_REF]MagnetU[END_REF]), or information searching by propagating queries (e.g., PeopleNet [START_REF] Motani | PeopleNet: Engineering a Wireless Virtual Social Network[END_REF]) as well as blog and photo sharing (e.g., Micro-Blog [START_REF] Gaonkar | Micro-Blog: Sharing and Querying Content Through Mobile Phones and Social Participation[END_REF]).

Internet access via 3G or WiFi is required for mobile devices to participate in social networks of the first category, while Bluetooth is largely exploited in the second category. We target the latter type of self-organized mobile social networks, where more challenges must be overcome to enable richer functionalities (that are comparable to those via Internet access) at cheaper device costs. In particular, we are interested in effective designs for supporting delay-sensitive streaming applications, which are more resource-demanding than sharing of blogs and photos with typical sizes of a few tens or hundreds of Kbytes.

We seek to design an efficient architecture and detailed protocols for collaborative VoD-type streaming of short videos in a peer-to-peer (P2P) fashion, which effectively exploit participants' social relationships. Such an objective is representative of a number of practical usage scenarios. For example, in a museum or a botanic garden, introductory videos are commonly seen accompanying items on exhibition to give the visitors rich information about the items. Compared to the current way of broadcasting each video with a dedicated screen, a superior solution is to implement cooperative streaming of the video to mobile devices of the group of audience surrounding the exhibition item in a P2P VoD fashion, to save hardware cost and provide viewing flexibility (a visitor can begin watching from the beginning whenever he approaches the item and drag to view any part of the video at will). There are other usage scenarios such as sharing amusing video clips one has in his cellphone to friends in a party.

To achieve the above objective, we design and implement SMS, an architecture to engineer VoD-type Streaming over Mobile Social networks, consisting of virtual communities of mobile users interested in particular videos. Our contributions in the novel design of SMS are three-fold: First, we explore social connections among participants in the virtual community, to facilitate voluntary collaborative streaming according to users' personal preferences. Specifically, we quantify social connections into different levels, namely friends, matches of social attributes, and others. Users are allowed to specify personal preferences in video streaming, to friends only, to friends and attribute matches, or to anyone, based on their own levels of social selfishness, altruism, or practical concerns such as the current battery levels. Second, we construct streaming overlays by synergistically combining participants' preferences, video segment availability, and characteristics of Bluetooth infrastructures. The broadcast nature of wireless transmissions is also exploited in efficient streaming of segments of common interests. Third, we design detailed protocols to implement SMS, which effectively tackle dynamics of the mobile users, including movements and VCR operations. We also implement our design on the Android platform and carry out extensive evaluations on streaming performance and battery consumption.

The remainder of the paper is organized as follows. We present the architecture and detailed design of SMS in Sec. 2 and Sec. 3, respectively. Sec. 4 gives results of the experimental evaluation. We discuss related work in Sec. 5 and conclude the paper in Sec. 6.

System Architecture

We focus on collaborative streaming of short videos among small groups of mobile users. For each video, there is one source S, which could be the video-emitting device besides an exhibition item in the museum scenario, or the mobile user who owns the video to be shared in the party scenario. The video is partitioned into n consecutive segments for dissemination. A set of mobile users, V, in close proximity of the source and interested in viewing the video, form a virtual community and retrieve the video segments in a P2P fashion via Bluetooth connections. We assume the source and mobile users are within the Bluetooth transmission ranges of each other. Each mobile user may start to view the video at any time, e.g., when he approaches the exhibition item or first joins the group of friends who are sharing the video, and can drag the sliding bar on his video player to view any part of the video at will. Therefore, Video on Demand (VoD) type of streaming is investigated in our design.

We consider mobile users are social entities, with different levels of selfishness and altruism. In collaborative streaming within each virtual community, the mobile users may have different preferences in contributing resources (battery, bandwidth) to upload video streams to others, which we classify into three categories: (1) strongly socially selfish type, corresponding to mobile users who wish only to upload to their friends; (2) weakly socially selfish type, for those who are willing to upload to friends as well as strangers with certain social attributes (e.g., the same hometown, the same hobby, etc.); (3) altruistic type, for users willing to help anyone else in streaming. Completely selfish users, who do not wish to upload to anyone else, are excluded from the system, by enforcing that only users who pick one of the above options and enable at least one upload connection can participate in streaming.

To achieve efficient streaming over such mobile social networks, we design SMS, an architecture for collaborative streaming with voluntary resource contributions, by exploring social preferences of the mobile users. Our architecture consists of four functional modules.

Bluetooth Protocols. Video transmissions among mobile users are based on Bluetooth in SMS. The Bluetooth protocols deal with connection setup and data transfer between Bluetooth devices. The detailed functions include device discovery, service discovery, connection establishment, and data transmission. Specifically, we carefully explore characteristics of Bluetooth infrastructures, i.e., piconet and scatternet, when constructing the P2P streaming topology among mobile users, for high transmission efficiency and low latency during streaming.

Social Preferences. The social preference module handles inquiry and matching of preferences and attributes among the mobile users. Each user maintains a profile, which records his upload preference, friend list, as well as a number of attributes he wishes to share with others (e.g., hometown, university/school graduated from, hobbies, etc.). Potential streaming links will be established only between users with matching preference and attributes.

P2P and upload of video segments among users. The establishment of streaming links from one mobile user to another is contingent on whether the upstream peer has the video segments the downstream peer needs, as well as the upload preference of the upstream peer, social connections between the two, and the transmission efficiency of the resulting Bluetooth infrastructures. In particular, broadcast opportunities are explored as much as possible among sub groups of users with similar viewing progresses, by organizing them into a piconet, for the best dissemination efficiency.

User Interface. This module provides interfaces on the mobile devices for users to maintain their profile, i.e., indicating their upload preferences, friend list, and attribute values. It also provides the video player interface for users to view the video and to control the playback progress.

An illustration of the SMS architecture is given in Fig. 1. We design detailed protocols to implement each module in the following section.

SMS: Detailed Design and Protocols

We first present detailed approaches to construct efficient collaborative streaming topology, based on social preferences and Bluetooth characteristics. We then present practical protocols to implement the design on individual dynamic users.

Collaborative Streaming Design

The key design issue is to decide which other peers each mobile user streams from and uploads video segments to at each time, i.e. the dynamic construction of collaborative streaming topology. Three aspects are investigated.

Segment Availability. To minimize the number of times for costly teardown and setup of Bluetooth connections, a mobile user should connect to a peer owning the largest number of video segments it needs. The suitability for user y to establish a download connection from user x can be decided as follows.

Let

S x = (s 1 x , s 2 x , • • • , s n
x ) be the bitmap indicating which video segments user x has, where

s i x = { 1 : X holds video segment i 0 : otherwise , i = 1, . . . , n. Let R y = (r 1 y , r 2 y , • • • , r n y
) denote the segment request list at a mobile user, where

r i y = { ρ i-p : i ≥ p 0 : otherwise , i = 1, . . . , n,
with parameter ρ < 1 and p indicating the index of the segment the user is currently playing. Here different segments are assigned different weights according to how close they are to the playback deadlines, to be used to prioritize request sequence of the segments.

The suitability for user y to stream from user x can then be calculated as

F (x, y) = n ∑ i=1 r i y × s i x .
A larger F (x, y) means that user x may supply user y more segments it urgently needs.

Social Preferences in Uploading. Whether y can download segments from x depends on social preference of x. There are three scenarios in which x is willing to upload to y:

(1) y is a friend of x;

(2) y shares the same social attributes with x, while x is willing to upload to users with matching social attributes; (3) y is neither a friend nor matches the social attributes, but x is willing to upload to anyone.

Let W (x, y) denote the level of preference for x to upload to y. Let a, b, and c be three system parameters satisfying We define

a + b + c = 1, a > b > c > 0.
W (x, y) =        a : Case (1), b : Case (2), c : Case (3), 0 : otherwise.
Combining segment availability with social preferences, we derive the following download preference for y to prioritize his connection requests towards potential supplying peers:

P (x, y) = W (x, y) • F (x, y).
The larger P (x, y) is, the more likely x can upload more needed segments to y.

Bluetooth Transmission Efficiency.

The construction of streaming topology should be efficiently combined with Bluetooth transmission technology, and exploits the broadcast nature of wireless transmissions for optimized streaming efficiency. In our design, we organize mobile users into an efficient Bluetooth scatternet, and explore broadcast opportunities within each piconet as much as possible.

Fig. 2 illustrates the Bluetooth network the mobile users form. Specifically, there are three different types of nodes in this Bluetooth scatternet: master nodes (MNs), master/slave nodes (MSNs), and slave nodes (SNs). The MNs own the complete video (e.g., the original source of the video or mobile users who have completed the download), and serve as seeds in the streaming network. Each MSN serves as the master node in one piconet and a slave node in another piconet concurrently, corresponding to mobile users who upload cached video segments to peers while downloading further needed video segments. The SNs are mobile users who have just started downloading (e.g., those just joined the system) and have not served others yet.

The Bluetooth network is dynamically constructed based on users' upload preferences and evolving with the streaming progress and dynamics of users. We make two design choices in constructing the collaborative streaming overlay over the Bluetooth network.

First, each mobile user maintains only one download connection at a time and maximally retrieves all segments the upstream peer can provide, before tearing down the connection and reconnecting to another supplier. Mapping to the Bluetooth scatternet, each node may serve as a slave in one piconet only.

This design aims to minimize the cost of establishing Bluetooth connections, as well as guaranteeing the download speed at each mobile user. In a Bluetooth network, each piconet maintains a unique pseudo-random frequency hopping sequence (FHS) and time division duplexity (TDD) is used for transmission scheduling. If a mobile user participates in more than two piconets, time is partitioned for different transmissions. The effective transmission time of each connection could be reduced, leading to degraded download speed.

Second, mobile users with similar segment requests are maximally arranged into the same piconet, while whether the master node is willing to upload to those peers considering. In this way, broadcast opportunities within each piconet are maximally explored: master node x periodically collects segment requests from slave nodes, and prioritizes the sequence of segment broadcast according to the sum of download preferences, i.e. ∑ y∈Y r i y W (x, y), for each segment i from different slaves in set Y.

Among the slaves in a piconet, some may serve as master nodes in other piconets (i.e., the case of MSNs). Since MSNs may only be active in one piconet at a time (by synchronizing to its FHS), they could miss data broadcast from the piconet where it serves as a slave. To resolve this issue, An MSN may send the same request again, if it has not received a segment for some time.

Practical Protocols

We next discuss practical protocols to implement the design in realistic dynamic environments.

Joining the system. When a mobile user first joins the streaming system, he customizes his user profile, including upload preference, social attributes, and friend list. His Bluetooth device enters the inquiry mode and discovers other Bluetooth devices within the radio range. Then it inquires service records of other devices through Service Discovery Protocol (SDP). A Bluetooth device providing service publishes its service record enclosing a number of service attributes; some service attributes are common to all (e.g., ServiceClassIDList, ProviderName), but others can be defined by the service providers themselves. [START_REF] Yang | E-SmallTalker: A Distributed Mobile System for Social Networking in Physical Proximity[END_REF] proposes an approach for information exchange by modifying the attributes of service records. In our implementation, we make use of a similar approach to exchange information for collaborative streaming, including upload preferences, social attributes, and segment availability.

Making use of the information acquired, a newly joined user identifies the most appropriate supplying peer to connect to, based on the design in Sec. 3.1. Then the user establishes a temporary connection with the selected supplier and sends a connection request. The supplier then invites the user into its piconet. If there are seven slaves including the new user, the supplier stops publishing its service record to prevent new connection request. According to the design on segment availability, the user will join a piconet in which slaves have similar requests.

Streaming video segments.

After a new slave node joins in a piconet, he will send his segment request to the master node at the first time slot assigned to him. The master node in a piconet collects segment requests from slave nodes and schedules segment transmissions. At a Bluetooth device, the frequency-hopping rate is 1600 hops per second, and each time slot for a frequency hop is 625µs. A regular Bluetooth packet can carry at most 2745 bits of data. In the streaming system, the size of a segment is typically at a few Kbytes. Therefore, multiple time slots are needed to send a video segment in a piconet. For each receiver of the segment, it remains active and follows the frequency-hopping sequence in the piconet.

A slave node in a piconet listens to each packet from the master node at the beginning of each odd time slot, and identifies the destination of a packet based on its LT ADDR field. A master node can broadcast packets to all slave nodes on the ASB-U, PSB-C, or PSB-U logical transport. When the master node is broadcasting, the LT ADDR field of the packets are set to zero.

Switching download connections.

As the streaming progresses, segment availability at each mobile user changes. Such updated information will be published by the user via updated service records.

Mobile users may alter their download connections when their current suppliers can no longer serve video segments they need, in cases when the slave user has performed some VCR operations during his video playback and when the master user moves beyond the radio range of the slave. When a change of download link is necessary, the mobile user tears down the connection in its original piconet, and restarts the procedure to search for a new supplier, following the similar service discovery steps as carried out by a newly joined user.

Detailed steps of our protocols are summarized in Algorithm 1.

Performance Evaluation

We evaluate SMS by implementing our design and protocols on Android 2.1 platforms. 6 HTC Wildfire mobile phones are used in our experiments. They are equipped with 528MHz Qualcomm MSM7225 processor, 512MB ROM, 384MB RAM, and a lithium-ion battery with 1300mAh capacity.

In our experiments, a 15MB video file is distributed, with a playback time of 320 seconds. One mobile device serves as the source, with the video file preloaded.

the number of peers with matching attributes at each user are both randomly chosen from 1, 2, and 3. Given the limited number of mobile devices, we restrict the number of slaves in each piconet to two, in order to form a Bluetooth scatternet for evaluation.

Streaming Performance

We first evaluate the streaming performance at the mobile users, by measuring the time taken for each user to complete the video download and the total waiting time during the download due to seeking suitable segment suppliers. We note that the streaming rate of the video is 15M B × 10 3 × 8bits/320seconds = 375Kbps, and data rate along Bluetooth connections is around 540Kbps. Therefore, segment download should be faster than the viewing progress, which guarantees smooth playback at the users. On the other hand, the total waiting time reflects the delay overhead incurred with our streaming protocols, due to service discovery (exchanging segment availability, social attributes, etc.), tearing down and establishing new connections.

We repeat our experiment for 10 times and plot the average results among all mobile users in Fig. 3 and Fig. 4, respectively. We observe from Fig. 3 that the average video download time is around 220 seconds, which is much less than the playback duration of the video, showing smooth playback can be achieved at the mobile users. Fig. 4 shows the percentage of waiting time during the entire download process is as low as 1.2%, exhibiting low delay overhead involved in our protocols.

We have also compared SMS with a P2P streaming protocol over mobile networks, by which mobile users select suppliers only based on segment availability and all users are willing to upload to anyone else. The results in Fig. 3 show that when more practical considerations on users' social selfishness are included (the case of SMS), the download performance is only slightly worse, as compare to the performance upper-bound achieved when all users are altruistic. Fig. 4 confirms the conclusion. In most case, the difference of the total waiting time between SMS and a P2P streaming protocol is small, bringing little influence on the user experience.

Power Consumption

We next evaluate battery consumption on the mobile devices when running our collaborative streaming protocol. In our experiments, the mobile devices are fully charged before start.

We first select four mobile devices with representative roles in the Bluetooth network, i.e., a master node with one slave, a slave node, a master/slave node with one slave, and a master/slave node with two slaves, and monitor their battery levels when running SMS using PowerTutor [START_REF]PowerTutor[END_REF].

Fig. 5 shows that the more nodes a mobile device is uploading to, the more energy is consumed. In addition, uploading consumes more energy than downloading. Nevertheless, we observe that the battery consumption during a time interval sufficient to download the entire video (about 250 seconds), is only less than 1% of the full battery power at all devices. This shows that SMS is effecient in energy consumption.

Next, we compare the battery consumption at mobile users with different upload preferences. We measure the total power consumption during a 250second runtime at a user who wishes only to upload to friends, a user who can serve both friends and strangers with matching attributes, and a user who is willing to serve anyone. Fig. 6 shows that the altruistic user could spend 19% more battery power than a strongly socially selfish user. However, the overall energy consumption at each user is still lower than 1% of the full battery power. This shows that a mobile user can be less concerned with his battery consumption when participating in SMS, and should be more altruistic to boost the overall download speed in the system (the case of all altruistic users in Fig. 3).

Related Work

Mobile social applications that are natural extensions of online social networks have been extensively explored. In Micro-Blog [START_REF] Gaonkar | Micro-Blog: Sharing and Querying Content Through Mobile Phones and Social Participation[END_REF], users generate geotagged data using their mobile phones, and share them with others via the Internet. Other applications in this category include PeopleTones [START_REF] Li | PeopleTones: A System for the Detection and Notification of Buddy Proximity on Mobile Phones[END_REF], Just-for-Us [START_REF] Kjeldskov | Just-for-Us: A Context-Aware Mobile Information System Facilitating Sociality[END_REF], Mobi-Clique [START_REF] Pietiläinen | MobiClique: middleware for mobile social networking[END_REF], FriendLee [START_REF] Ankolekar | Friendlee: A Mobile Application for Your Social Life[END_REF], and Social Serendipity [START_REF] Eagle | Social Serendipity: Mobilizing Social Software[END_REF].

In the other category, mobile users in physical proximity directly connect with each other. They store data (e.g., profiles) locally in their mobile devices, and no central Internet server is involved. E-SmallTalker [START_REF] Yang | E-SmallTalker: A Distributed Mobile System for Social Networking in Physical Proximity[END_REF] is a mobile communications system facilitating social networking among people in physical proximity, and can discover and suggest topics of common interests for conversations. PeopleNet [START_REF] Motani | PeopleNet: Engineering a Wireless Virtual Social Network[END_REF] presents an architecture that facilitates information seeking over a wireless virtual social network. SocialNet [START_REF] Michael | Social net: using patterns of physical proximity over time to infer shared interests[END_REF] is an interest-matching application that uses patterns of collocation to infer common interests between users over time. Besides mobile social application design, there exist other work exploiting social connections of users in their system design [START_REF] Jahanbakhsh | Social-Greedy: a socially-based greedy routing algorithm for delay tolerant networks[END_REF] [START_REF] Mei | Give2Get: Forwarding in Social Mobile Wireless Networks of Selfish Individuals[END_REF]. But none of them have categorized social relationships in the same way as we do.

There are some work exploiting the Bluetooth technology and protocols. [6][7][17] propose approaches to form stable Bluetooth scatternet, without taking into account the video streaming and social network scenario. Sewook et al. [START_REF] Sewook | BlueTorrent: Cooperative Content Sharing for Bluetooth Users[END_REF][START_REF] Sewook | Peer to peer video streaming in Bluetooth overlays[END_REF] propose P2P streaming system designs over interconnected Bluetooth piconets. Their work focus on Bluetooth network construction without taking social relationship and selfishness of mobile users into consideration. In contrast, our work explores users' social connections and Bluetooth characteristics in an integral design, for voluntary collaborative streaming with high efficiency.

Concluding Remarks

This paper presents SMS, an architecture for VoD-type Streaming over Mobile Social networks, to achieve efficient collaborative distribution of short videos among mobile users. Our contributions in this paper are three-fold: First, we explore social connections among participants in the mobile social network, to facilitate voluntary collaborative streaming according to users' own upload preferences. Second, we construct streaming overlays by synergistically combining participants' preferences, video segment availability, and characteristics of the Bluetooth infrastructures, while effectively exploiting the broadcast nature of wireless transmissions. Third, we design detailed protocols to implement SMS, which efficiently tackles varies dynamics of the mobile users. We also implement our design on Android platforms and carefully evaluate the runtime performance of SMS. Preliminary results over a small-scale mobile network have shown satisfying streaming performance as well as low battery consumption with our protocols. In our ongoing work, we are implementing a practical Bluetooth emulation platform, in order to break the limitation of available hardware devices and carry out evaluations in a larger scale under realistic settings.

Fig. 2 .

 2 Fig. 2. Bluetooth network structure: an illustration.

Fig. 3 .

 3 Fig. 3. Average video download time.

Fig. 4 .

 4 Fig. 4. Average waiting time during download.

Fig. 5 .

 5 Fig. 5. Power consumption at devices of different roles.

Fig. 6 .

 6 Fig. 6. Power consumption at devices of different upload preferences.

  Streaming. The P2P streaming module constructs P2P streaming topology among mobile users in the virtual community, and implements request

			SMS
	User	Interface	Video Player	User Profile
	P2P	Streaming	Block Request/Transfer	Streaming Topology Construction
	Social	Preferences	Preference and Attribute Inquiry	Preference and Attribute Match
	Bluetooth	Protocols	Connection Setup	Data Transmission

Fig. 1. Architecture of SMS.

Acknowledgement

This research is supported in part by the University of Hong Kong Strategic Research Theme of Information Technology.

The other mobile devices join the streaming network one by one, with joining times uniformly distributed within a total duration of 9 minutes. Upon joining, a user starts requesting and viewing the video from the beginning. The users are configured with different upload preferences, friend relationships, and social attributes: the type of each user is randomly chosen among the three (strongly socially selfish, weakly socially selfish, and altruistic); the number of friends and