Right Arrow Callout: IntroductionRight Arrow Callout: Path Diversity Spread Routing

Right Arrow Callout: End-to-End adaptive FEC

Right Arrow Callout: Adaptive Redundancy Overall Need (ARON)

Right Arrow Callout: Real-Time streaming and choice of an encoder

Right Arrow Callout: Choice of the MDS FEC block size

Right Arrow Callout: Capillary Routing

Right Arrow Callout: Building Capillary Routing

Right Arrow Callout: ARON of Capillary Routing

Right Arrow Callout: Implementation suggestions

Right Arrow Callout: References

Right Arrow Callout: Glossary

 

Introduction

 

Media streaming is becoming increasingly important in Internet. The major cause for multimedia quality degradation in IP-networks is packet loss. Packet loss occurs in network due to bursts and link failures or packets may be dropped in the application, if they are received too late.

 

Forward Error Correction is a mechanism that may allow the streaming application to overcome losses without utilizing retransmissions. Real-time media or files sent over the internet are chopped into packets, and each packet is either received without error or not received. Packetized communications over internet thus behave like erasure channels and the erasure resilient FEC codes, such as Reed Solomon or another Maximum Distance Separable (MDS) code can be applied on the packet level to a stream of UDP (User Datagram Protocol) data packets.

 

With the proper amount of redundant data included in the stream of transmitted packets, erasure resilient FEC can mitigate the impact of packet loss on the data. For numerous packetized applications, employment of erasure resilient FEC codes offered spectacular results: in satellite feedback-less broadcasts of recurrent voluminous updates of GPS (Global Positioning System) maps to millions of motor vehicles under the condition of arbitrary fragmental visibility due to their locations and trajectories: tunnels, underground parking, buildings and garages [honda04]; in a film industry for a fast delivery over Internet of the day’s film footage from the location it has been shot to the studio that is many thousand miles away [hollywood03] using LT codes [Luby02]. 3GPP, 3rd Generation Partnership Project, recently adopted Raptor [Shokrollahi04] as a mandatory code in Multimedia Broadcast/Multicast Service (MBMS), a part of 3G standard, for its low CPU usage and for the significant performance in media broadcasting and file transfer [MBMS05a], [MBMS05b], [MBMS05c].

 

The above references are rather examples of off-line applications, where there are no constrains on the buffering time because the sender is not obliged to deliver in time the “fresh” packets of a very short life time.

 

Regarding from the stand point of a real-time application, in the film transfer or in the GPS map update, the buffering time is practically unlimited. Several publications studied application of FEC in real-time media streaming. [Johansson02] reported improvements from the application of FEC if the packet losses range is between 1% and 5%. [Huang05] proposed to combine retransmissions, if the round trip time (RTT) is low, with FEC, and reported improved speech quality perception in a practical experiment. [Padhye00] reported high overheads from the use of FEC during bursts but proposed to survey the history of losses (experienced by the application) after reconstruction to choose a good FEC. Other publications have shown that for two-way, delay-sensitive real-time communications, the application of FEC on the packet level can not give any valuable results at all [Altman01].

 

In the off-line streaming success examples (MBMS or GPS map update) it was the long (or almost unlimited) buffering time that let FEC be an efficient solution of the fault tolerance. However according to [Altman01] in real-time applications with limited buffering time, only negligible improvement from application of FEC can be obtained at the cost of very high overheads. Voice over IP, a widely demanded interactive application, is an example of a poor FEC efficiency: the ratio of the lossy network path’s failure time over the permitted limit on the buffering time is too high.

 

If it is still believed that FEC can however significantly improve the tolerance of real-time streaming, we must exploit other dimensions which can “replace” the long buffering time and open to FEC the true perspectives in the domain of real-time streaming.

 

All previous studies stressing on the poor FEC efficiency assumed that the media stream always follows a single path. Short granular failures can be still mitigated at a certain cost of the FEC overhead, but obviously, there is no FEC which can solve a problem of a complete link failure on the single route path if the failure duration is long enough to overpass the permitted maximum of the buffering time (long bursts or congestions, hardware or software circuit outages until the recovery triggering, deny of service – DOS attacks).

 

Application of FEC to the real-time streaming however is not hopeless, because, there exists the other unexploited dimension: the underlying network routing, an alternative orthogonal method toward the buffering. The previous studies ignored the effort that could have been provided by the underlying routing.

 

The advantage of the flow following multiple paths versus a single path routing is obvious: a long link failure on the single path route leaves the application completely helpless, but the application can apply FEC to recover a single link failure of a spread multi-path route.

 

There is an emerging body of a literature addressing the advantages of multi-path routing in media streaming. The author of [Qu04] studied video communication following alternate paths and has shown that in disjoint paths the advantages of strong FEC are significant; in the correlated paths weak FEC can be still advantageous. In [Tawan04] the author proposed path diversity in Ad-Hoc network motivated by the load balance and capacity increase concerns but mostly by the choice of the adaptive routing protocol; the achieved efficiency in use of FEC was also mentioned. In [Ma03] and [Ma04] it was suggested to replace in MANET the link level Automatic Repeat Query (ARQ) by a link level FEC assuming intelligent regenerating nodes. The routing topology is simplified into a path with serial or parallel links between the nodes and it was suggested that the end-to-end packet loss rate as a function from hops will improve. However in such a hop by hop based FEC, since the retransmission of a lost media packet may be delayed until its recovery, for the stability of the real-time media the node needs a jitter buffer (of the size of the transmission block) and the jitter buffer’s constant delay will be propagated therefore with each hop, weakening this approach for the real-time streaming. In [Nguyen02] it was proposed the server diversity in one-way video, demonstrating that streaming to a single receiver from multiple servers improves the tolerance and increases the capacity. The author is focusing on the receiver driven protocol for allocating to sending servers the rates (based on RTT values measured from the receiver) and for partitioning non-overlappingly the packets to be transmitted. But for the buffered multi-point video delivery the author should have chosen instead of Reed-Solomon (RS) a rateless uniform fountain code (random linear fountain, LT or Raptor [MacKay05]) and would therefore skip from the protocol the packet partitioning part [Byers99]. The author also ignores the network topology, assuming that the routes from the senders to the client do not share links. The same author lately studied the path diversity effect, this time, on the protection of point to point real-time video streaming using a permanent RS(30,23) encoding (23 media packets and 7 redundant packets) at the sender [Nguyen03]. The author, similarly to [Qu04] compared two-path scenarios (shortest path together with an alternate completely disjoint or with an alternate but correlated path) with the single OSPF routing strategy and has shown clear advantages of the double path routing. The choice of RS versus fountain code is justified in [Nguyen03] by the limits of the real-time application on the buffering.

 

If one of the axes amplifying the effect of FEC was the buffering time, then the second orthogonal ax therefore is clearly the routing. While the first ax, the buffering [Weatherspoon02], [Krunz04], gave excellent results in the off-line streaming, the second, the routing ax, is hopefully suitable for the protection of real-time two-way streaming, insurmountable by the buffering ax alone, due to interactiveness and delay sensitivity.

 

All above referred publications suggested the important and promising impact the routing can have to the efficiency of FEC. However the considered topologies were simple and limited to only two, possibly correlated, paths [Qu04] and [Nguyen03], or in the best case to a sequence of parallel and serial links [Ma03]. We have not found a study of an impact of a wider range of routing patterns to the FEC efficiency. There is lack of a work in the literature studying the routing as a space of possibilities or as a dimension, and seeking in there the optimal point of FEC efficiency – the friendliest routing pattern. From this point of view we can say that the previous studies only proved the advantageousness of path diversity, most of the time of double-paths, toward only single path routing. The author of [Nguyen03] concludes that deployment of the second redundant path along with the default path effectively results in a factor of 3 reduction in irrecoverable packet loss as compared to uni-path scheme. In this paper we try to present a global comparative study across much larger number of friendly routing patterns, all multi-path, virtually erected along a routing ax. Single path routing, being considered as too hostile, will be even excluded from our comparison system. We begin from the strategies similar to multi-path approaches of [Qu04], [Nguyen03] and [Ma03] as our starting point, but we will develop them step by step into more elaborated, dispersed and advantageous routing samples. Addressing the parallelism and spreading aspects in the routing patters we assume several abstractions and simplifications for other network model parameters (e.g. uniform links and lack of delay prorogation). To compare one spread routing with another one, we will introduce a measure of the routing’s advantageousness. We will demonstrate that the first level of diversity obtained by converting a single path routing to the basic multi-path routing is not the terminal achievement of the path diversity approach. The routing can be still sensibly improved (toward FEC), layer by layer. Routing ax consisting of only spread routing patterns; can further burst the efficiency of FEC. We hope that our investigations will provide guidelines for future design and development of multi-path routing strategies in multimedia transmission.

 

 

Related links

 

-          Releases of Capillary Routing Builder and ARON measurer (Swiss Mirror site)

-          Releases of Capillary Routing Builder and ARON measurer (US Mirror site)