Abstract
Abstract-Multicast is an efficient technique to deliver video content over a network. In this paper, we consider such a multicast system to serve both wireless and wireline users when there is error over the wired network and wireless hop. Since packets are likely to be dropped in the wired networks while bit errors are more likely over the wireless hop, a combination of both packet-level and byte-level FEC is required to recover these errors. Given the estimated error and bandwidth characteristics reported by end users, the server needs to optimally allocate the packet-level and byte-level FEC to achieve maximum video quality. We study two schemes pertaining to whether or not the wireless gateway is able to transcode the video packets from the wired network before forwarding it to the wireless users. We first develop a model to analyze the system; and then propose an efficient algorithm for the FEC computation. We finally compare the schemes in terms of the optimal parameters used in the FEC, and the video quality achieved.
I. INTRODUCTION
Multicast is an efficient technique to deliver video to its end users. In such a system, the video files stored or captured in a server are multicast to its clients distributed in a network. Data is usually multicast in a "TCP-friendly" manner, by which we mean that the streaming rate is not more than the available bandwidth in the network [1] , [2] . The end client may be wired or wireless. 1 In the case of wireless network, the base station is generally connected to a gateway. In its simplest form, the gateway simply forwards whatever packets it receives to the wireless client without any re-packetization or fragmentation. A more sophisticated gateway, on the other hand, can take into consideration of the wireless characteristics and repacketizes the packets it receives from the wired infrastructure, adds or removes some information in them (e.g., error redundancy codes) before forwarding them to the end clients. This technique is known as "transcoding", as data packets are re-encoded in the process. The "transcoding" gateway is beneficial since the packet error characteristics are different in the wired and wireless networks. In wired networks (such as the Internet), packets are lost mainly due to congestion at the routers, while in the wireless hop, packets are often lost due to random bit error caused by fading or multipath effect [3] .
I. INTRODUCTION
To recover packet loss, feedback recovery or forward error correction code can be used [4] . In general, feedback recovery does not work very well over large scale networks with real-time guarantee. FEC such as the Reed-Solomon (RS) code, on the other hand, is more appropriate for real-time communications by introducing some redundancy [5] . It consists of arranging the data and redundancy bits in such a way that even if a partial fraction of the bits are received, the original data may still be recovered. An FEC scheme adapting to the network error conditions is very efficient to maintain video quality. In this paper, we will mainly concerned with FEC to achieve maximum video quality. FEC strategies would be different over the wireless and wired networks, due to their different error characteristics. In the wired network, some packet-level FEC should be used, in which redundant or This work was supported, in part, by the Hong Kong Telecom Institute of Information Technology (97/98.EG01), and Sino Software Research Institute at the Hong Kong University of Science and Technology(SSRI00/01.EG04).
I. INTRODUCTION
1 In this paper, we distinguish a "user" from a "client" in that a user is the person requesting a video, while a "client" is the station/machine the user uses.
I. INTRODUCTION
parity packets are added so that packet loss can be recovered [3] , [4] , on the other hand, byte-level FEC should be used over the wireless hop, in which redundant or parity bytes within a packet can be added to recover bit error [3] . We consider that the clients periodically feedback to the source its "estimated" end-to-end bandwidth, packet loss and bit error rate between itself and the source (How to estimate the end-to-end bandwidth and packet drop rates accurately is beyond the scope of this paper. Interested readers are referred to [6] and references therein). Given these feedbacks, it is therefore of particular interest to address the following issue: under the multicast environment and given the heterogeneous error and bandwidth characteristics of its end users, how should the packet-level and byte-level FEC be allocated for a single video stream in order to maximize the overall video quality, in both cases of simple and "transcoding" gateways? We primarily concern the optimization for a single stream in this paper, since there are already many rich issues to be considered pertaining to FEC allocation and transoding gateways. Our approach and discussion here readily extend to and would be useful for the layered multicast case, in which the video is multicast via multiple layers, and each layer has different FEC capability.
I. INTRODUCTION
Traditionally video quality is measured by distortion given by PSNR [7] . It has been widely observed that such PSNR is proportional to the video goodput defined by useful data bits per second received by the end clients after FEC, given that the residual packet error rate is below a certain low value (≤ 3%) [8] . Therefore, maximize video quality in PSNR is equivalent to maximize the overall goodput of the system, subjected to a certain low loss constraint.
I. INTRODUCTION
Our contributions in this paper are 3-fold: i) We have studied video multicast to wired and wireless users; ii) We have investigated optimal allocation of packet-level and byte-level FEC for video delivery; and iii) We have developed a model and presented an analysis of transcoding gateway at the wireless hop. Our results show that the scheme with transcoding gateways outperforms the scheme with no transcoding gateways by a small margin, for wide ranges of packet drop rate.
I. INTRODUCTION
We briefly present some previous works as follows. In [1] , [2] , Zhang et al. discussed rate adaptation approaches for video delivery. It consists of bandwidth estimation and adapting the transmission rate of the videos. Multiple video streams are carefully controlled by a quadratic rate-distortion function in order to unicast it in a "TCPfriendly" manner. Our work differs from theses by considering video streaming in a multicast environment. Also, we consider the application of FEC on the video stream and the optimal partition of the available bandwidth for video data and parity bits. Recovering dropped packet by retransmission and delaying the playout time at the client have been discussed in [9] , [10] . However, these works are related to wired environment and have not considered the wireless media and the optimal allocation of FEC codes. Other recovery schemes pertaining to limited retransmission and FEC (the socalled hybrid ARQ-FEC scheme), have been discussed in [11] , [12] . Research has also been done sending delayed version of parity across different multicast groups, and clients can subscribe to different groups, according to their loss profiles and desired level of protection [13] . However, all of them are discussed under the context of a single medium only, and have not discussed "mixed" media (wired and wireless networks) and how packet-level and byte-level FEC can be optimally combined in such case. Furthermore, there has not been work examining the design of gateways for FEC. This paper is organized as follows. We first present the schemes depending on whether the gateway transcodes the packets or not, and the goodput analysis in Sect. II. In Sect. III, we present some illustrative examples, and demonstrate the effectiveness of the schemes. We conclude in Sect. IV.
II. SCHEME DESCRIPTION AND ANALYSIS
Since every client has to receive the video with good quality, the bandwidth allocated to the video stream (including FEC encoding) should be equal to the minimum end-to-end bandwidth. Thus, the only concern here is how the error control should be applied to serve both wireless and wired clients so that its overall quality is optimized. As noted before, the quality is measured by the aggregate goodput in the system, or equivalently, average goodput of the client.
II. SCHEME DESCRIPTION AND ANALYSIS
In this section, we first describe packet-level and byte-level FEC schemes in Sect. II-A. In Sect. II-B, we analyze and optimize video quality in terms of system goodput for non-transcoding and transcoding gateway, given client packet loss and bit error rate.
A. FEC Scheme Descriptions
We propose mixed packet-level and byte-level FEC to protect the video stream. We study the scheme with and without a transcoding gateway.
A.1 Non-transcoding gateway
With non-transcoding gateway, both packet-level and byte-level FEC encodings have to be done at the video server, and error correction are only done at the end clients. At the server, the compressed stream is first encoded with byte-level FEC followed by packet-level FEC. The decoding part is the reverse of the encoding process. Note that with this system, the byte-level FEC does not really help those wired clients (where packet drops occur) in improving their error resilience capability.
A.1 Non-transcoding gateway
We show in Fig. 1 how to generate the two levels of FEC based on RS code. For the byte-level FEC, the encoder processes in symbols, where each symbol consists of m = 8 bits. Given a packet of size n b bytes, k b (≥ 1) bytes of source data is packed with n b − k b parity bytes, where
A.1 Non-transcoding gateway
code, which is able to correct up to t b symbol errors in a packet, where
A.1 Non-transcoding gateway
With every k p of these byte-encoded video packets, packet-level FEC is then applied to generate n p −k p parity packets for a block of n p packets, where k p = n p , n p − 1, . . ., 1. This is generated as follows. to generate n b − k b parity bytes. The generated parity bytes are then redistributed as the ith byte of each of the n p −k p parity packets. Since all the packets are sequenced, up to tp = np − kp packet losses in a block can be corrected. Clearly, as a block of packets has to be ready before packet-level FEC is done, the delay of the system increases with np. Therefore, in reality user delay requirement determines the n p that can be used.
A.1 Non-transcoding gateway
The server computes the optimal allocation between the video data rate, the packet-level FEC rate (i.e., the number of packet-level FEC parity bits per second) and the byte-level FEC rate (i.e., the number of byte-level FEC parity bits per second) given the feedbacks from the end clients. Let G be the multicast group size. The feedbacks for client g (1 ≤ g ≤ G) are in terms of the estimated end-to-end available bandwidthBg and the packet drop rateP l,g (P l,g may be estimated by the missing sequence numbers of the packets), 2 and, for wireless clients, the bit-error-rate of the wireless hopê b,g (ê b,g may be estimated by using a two-state Markov process as given in [14] ).
A.1 Non-transcoding gateway
Given the feedback information, the server has to first decide the packet-level and byte-level FEC rates for the video stream, with its transmission rate including all the redundant bits is equal to the least end-to-end bandwidth in the multicast group (i.e., R0 = min gBg ). Let the packet-level FEC rate be R p and byte-level FEC rate be R b . Given (n p , k p ) and (n b , k b ), R p and R b are clearly given by
A.1 Non-transcoding gateway
and
A.1 Non-transcoding gateway
The video source rate R s , defined as the data rate excluding all the FEC, is then given by
A.1 Non-transcoding gateway
The nomenclature used in this paper is listed in Table I .
A.2 Transcoding Gateway
A transcoding gateway transcodes video packets from packet-level FEC to byte-level FEC before forwarding the packets to the wireless clients. The gateway first recovers any dropped packet by the packetlevel FEC, and then pads the video packets with byte-level FEC parity. Note that the wired clients need to perform packet-level FEC operations only, and, in contrast with the non-transcoding gateway, bytelevel FEC encoding is done at the gateway rather than the server. We consider a simple transcoding gateway which does not do any packet fragmentation or reassembly. We see that a transcoding gateway achieves lower bandwidth requirement than the non-transcoding one (or equivalently higher video quality given a bandwidth constraint) by trading off some system complexity.
A.2 Transcoding Gateway
We show the detail of the encoding process in Fig. 2 . The gateway first recovers the k p data packets (out of the n p FEC block) each of k b bytes, and then transcodes the packets to n b bytes by padding them with some byte-level FEC. Given the transmission rate of R0 bits/s, the packet-level and byte-level FEC rates are clearly given by the same expressions as of Eqs. (1) and (2), respectively. The source rate is, however, given by Rs = R0 × (kp/np).
B. Quality Optimization
In this subsection, we analyze the system with non-transcoding and transcoding gateways and consider how the video quality can be maximized over all the clients in the system. As mentioned before, we consider minimizing the sum of PSNR over all the clients. For the error rate of interest, this is equivalent to maximizing the aggregate goodput Γ (bits/s), defined as the useful data bits delivered per second over all clients after error correction. Further let Γg be the goodput of the gth client.
B. Quality Optimization
Therefore, we study the following byte-level and packet-level FEC allocation problem: Given n b and np, find the optimal np, kp, and k b in order to maximize
B. Quality Optimization
such that the end-to-end packet loss rate (after error correction) is no more than a certain value ε o (say, 0.01 -0.03) over all clients. Here, we consider the sum of the individual goodput, i.e., all the clients in the system have the same priority or importance. If it is not that case, we need to assign some weight to each Γg (and thereof each PSNR). This extension is straightforward and would not be pursued further here.
B.1 Optimization for non-transcoding gateway
Let's consider a particular client g (and hence the subscript "g" in some of our equations) and obtain its goodput givenP l,g andê b,g . In the wireless hop, a symbol is considered in "error" if any of the m bits in the symbol are transmitted in error. Clearly, given bit error ratê e b,g in the wireless channel, the symbol error rate is es,g = 1 − (1 −  e b,g ) m . Since the RS(n b , k b ) code corrects up to t b symbol errors, the probability that a random packet cannot be recovered by byte-level FEC is given by
B.1 Optimization for non-transcoding gateway
Note that for the wired clients, αg = 0 asê b,g = 0 by definition. A packet is "dropped" if it is dropped in the wired networks (with rateP l,g ), or if it is in unrecoverable error (with probability α g ) over the wireless hop. Since the two events are independent, the end-toend packet drop rate from the source to the client is given by
B.1 Optimization for non-transcoding gateway
Note that the dropped packets may be recovered by the packet-level FEC (see Fig. 1 ). Since up to tp = np − kp dropped packets in the same block can be recovered by packet-level FEC. By considering the number of packet drops in an FEC block, the probability that a random packet is permanently "lost" (i.e., the end-to-end packet loss rate after error correction) is given by
B.1 Optimization for non-transcoding gateway
The goodput of the client g is hence given by
B.1 Optimization for non-transcoding gateway
The allocation problem is a two dimensional search on kp and k b , which is of complexity O(Gnpn b ) and is not efficient. Validated by extensive runs, we found that packet-level FEC optimization can be done independently with that of byte-level FEC without affecting the results much (less than 1%). Therefore, we can greatly reduce the complexity to O(G(np + n b )) by means of the following two-step procedure: 1. (Packet-level FEC optimization) For all clients, let P l = maxgP l,g . If P l ≤ εo, STOP and proceed to the next step (The packet drop rate is so low that k * p = np). Otherwise, for all the clients witĥ P l,g > εo, search for the largest kp < np (for minimum overheads) such that g (in accordance to Eq. (5)) of all these clients are no more than εo. This is the k * p required.
(Byte-level FEC optimization)
Given k * p , find the largest k b < n b such that g for all the wireless clients are no more than εo. This is the k * b required.
B.2 Optimization for transcoding gateway
Consider a client g. The probability that a random packet is permanently lost over the wired network is clearly given by
B.2 Optimization for transcoding gateway
If it is a wireless client, the packets corrected after packet-level FEC are transmitted over the wireless hop. The probability that these packets cannot be recovered due to wireless error has already been obtained as αg in Eq. (4) (again, for the wired user, αg = 0). Therefore, the end-to-end packet loss rate after error correction is given by (by the independence of error rates in the wired and wireless networks)
B.2 Optimization for transcoding gateway
and hence the goodput of the client is
B.2 Optimization for transcoding gateway
As in the non-transcoding case, we again observe that the packetlevel FEC can be done independently of the byte-level FEC for the transcoding case. The optimization procedure is hence the same as that of the non-transcoding case, except that g is replaced by ηg in Eq. (8).
III. ILLUSTRATIVE NUMERICAL EXAMPLES AND RESULTS
In this section, we compare the performance of transcoding and non-transcoding gateways. We consider a baseline system of G = 10 clients, with half of them wireless clients. We show in Table IIP l,g andê b,g of each client, which are generated by assuming that they are uniformly distributed with mean P l = 2% and e b = 10 −4 , respectively. Note that clients 1 to 5 are wireless clients, while the remaining are wired. The other baseline parameters are εo = 1%, n b = 255, np = 40, and R0 = 100 kbits/s (kb/s). Optimal FEC allocation will first be performed given these parameters. Then in our sensitivity analysis, we vary the other parameters, one at a time.
III. ILLUSTRATIVE NUMERICAL EXAMPLES AND RESULTS
We show in Fig. 3 to the same optimization step in k * p ). k * p increases with εo in a stepwise manner (due to the constraint on integral value). Note that kp is already very close to np, indicating that little packet-level FEC is necessary to achieve a low end-to-end packet loss. The packet-level FEC is so effective that even though most of theP l,g 's are greater than 2%, only a few overhead packets (2 in this case) are needed to bring εo to as low as 1%. No overhead is necessary when εo ≥ maxgP l,g (as all clients hasP l,g < εo).
III. ILLUSTRATIVE NUMERICAL EXAMPLES AND RESULTS
We next show in Fig. 4 the corresponding k * b versus εo for transcoding and non-transcoding gateways. Both cases share almost the same k * b . As compared with k * p , k * b is quite insensitive to εo; it increases relatively very slowly. Therefore, as εo changes, kp is a more important parameter to adjust. Note that forê b,g = 10 −4 , a random packet without any byte-level FEC is in error occurs with probability of 1 − (1 −ê b,g ) mn b = 0.18. Even with this packet loss rate, only a few overhead bytes (about 4-6 in our plot) is enough to bring this error rate down to a low level given by εo. This again indicates the efficiency of byte-level FEC. The "dips" in the figure corresponds to the "rises" in Fig. 3 . This is because once k * p is increased, the packet-level error correction capability decreases and hence a lower k * b (and thereof a stronger byte-level correction capability) is needed to compensate. As εo increases, the k * b jumps back up as the system can tolerate more end-to-end packet loss. We show in Fig. 5 the corresponding optimal goodput Γ * (i.e., with k * p and k * b ) versus ε o for the transcoding and non-transcoding cases. Though the goodput for the transcoding case is higher, there is no much difference between them (only about 2% difference here). This is expected because, from Eqs. (9) and (6), the ratio of the non-transcoding and transcoding goodputs for client g is given by From Fig. 4 we have already seen that k * b for the non-transcoding gateway is very close to n b , and hence the difference is small. As εo increases, Γ * in general first increases and then decreases (the decrease is shown for the transcoding case). This is due to the following. Γ is affected by two factors: i) the end-to-end packet loss rate g and ηg (Γ decreases with them), and ii) k * p and k * b (Γ increases with them). From the figure, we see that when εo is small, the effect of k * p and k * b dominate, while when εo is higher, the error rate dominate and Γ * decreases. For the cases of interest (i.e., ε o ≤ 5%), Γ * increases with ε o .
III. ILLUSTRATIVE NUMERICAL EXAMPLES AND RESULTS
In Fig. 6 , we show how k * p varies with P l . Clearly, k * p decreases with P l as more error protection is necessary. The packet-level FEC is quite effective, as only a few parity packets (given by np − k * p ) are able to bring a high P l (say, 7-8%) to a low εo value (1%).
III. ILLUSTRATIVE NUMERICAL EXAMPLES AND RESULTS
In Fig. 7 , we show k * b versus e b for transcoding and non-transcoding cases. Clearly, there is no much difference between these cases. In general, k * b decreases with e b because more parity bytes are needed.
III. ILLUSTRATIVE NUMERICAL EXAMPLES AND RESULTS
As e b increases, k * b remains quite flat at the beginning and then sharply decreases. This indicates that when the bit error is high, many more parity bytes are needed to achieve a certain error rate after FEC. From the figure, we also see that when e b is greater than a certain value (about 5% in this case), the bit error rate is too high that byte level FEC is no longer effective to bring errors in the wireless hop down to εo. Thus, the system can only tolerate wireless channel with bit error rate from 10 −6 to 10 −2 .
IV. CONCLUSIONS
In this paper, we have studied a video multicast system over wired and wireless networks with client feedback. The main challenge is to optimize the overall video quality by means of layer FEC allocations for the set of clients given their heterogenous bandwidth and error characteristics, subject to a certain overall loss rate requirement. Furthermore, since there may be a transcoding gateway (which transcodes from packet-level FEC to byte-level FEC) between the wireless clients and the wired network, we have studied the value of such a gateway. We have analyzed the system and proposed an efficient allocation policy.
IV. CONCLUSIONS
In order to serve all the clients, the transmission rate of the video stream should be equal to the minimum bandwidth of the clients. The issue of the video transmission is hence how to allocate packet-level and byte-level FEC so as to maximize video quality (in terms of goodput). Instead of a 2-dimensional search, we have presented an efficient algorithm for such optimal FEC allocation.
IV. CONCLUSIONS
Our results show that the transcoding scheme performs only slightly better in terms of system goodput than the non-transcoding scheme (by about 2%). This is mainly due to the efficiency of FEC encoding (which occupies less than 20% of the data for the packet-level FEC, and less than 10% for byte-level FEC). This small difference may not justify the complexity of such a transcoding gateway. A gateway which transcodes data in some other ways may be more useful.
IV. CONCLUSIONS
The schemes can be extended to apply in delivering layered video, which each layer is multicast in separate groups with different loss constraint. Future work can be done in combining the optimization in both FEC and bandwidth allocation across the layers.

{'paper_id': '8236435', 'title': 'Optimal allocation of packet-level and byte-level FEC in video multicasting over wired and wireless networks', 's2_url': 'https://api.semanticscholar.org/CorpusID:8236435', 'source': 'S2ORC'}