Path Diversity Spread Routing

Addressing the problem of fault-tolerance from the routing point of view, we propose to route a media stream in a way which minimizes the impact of individual link failures to the quality of the media. Even if failure recovery mechanisms are assumed in the network, the way we route the end to end transmission over the network must maximally protect the media before the network detects and recovers the failure. Suggested routing does not require additional capacities from the network; it simply spreads the packetized transmission over as many independent paths as possible.

If a network can sustain a given number of independent transmissions each following a single path, then in principle, the same transmissions can traverse the network in a spread fashion, without requiring additional capacity.

Transmissions following a single path

Transmissions spread over multiple paths do not require extra network capacity

Spread routing alone does not solve the problem of tolerance. If media stream is not capable to sustain any losses at all, by spreading the transmission the media becomes more vulnerable to link failures, since there are more links whose failure will damage the stream. However if media is equipped with a certain level of tolerance toward losses, the spreading of flow may protect the transmission. With sufficient redundancy and spreading factor the transmissions can be protected completely against any single link failure.

A tolerance of media to losses can be the part of the nature of the media itself. If the media is destined for a human perception (VOIP, image or video), it can still conserve its content with a quite high level of stochastic losses. With g729r8, g723r53, g723r63 and gsmfr VOIP compression codecs the speech remains comprehensible with 8% to 11% losses. Similarly, a video compression codec (e.g. MPEG) also ensure a certain tolerance to losses, e.g. due to passive error concealment (level of tolerance of video streams is lower compared with voice).

Natural tolerance of media may be not sufficient to make a real benefice from the spread routing. For any type of real-time media transmission, tolerance to losses can be obtained by injection at the source of some redundancy provided by erasure resilient forward error correction codes (e.g. Reed Solomon codes).

For the two figures above, assuming a tolerance of 1/3 for each media stream, in the single path scenario, any single link failure would kill one of the media streams. At the same time all multiple path streams will sustain a complete failure of any of three links.

Most internet routers employ First-In-First-Out (FIFO) policy in which, the successive arrived packets are dropped if the network buffer becomes full. Hence a model of fragmental link failures can be adopted to approximate link outages, bursts and congestions. Link is either in the operational or in a faulty state and is characterized by its average failure and operation time.

It is not however very efficient to permanently transmit with the media stream a large amount of constant redundancy. It is much better to increase the redundancy on demand. The receiving node can detect the deficit of delivered packets and demand an appropriate increase of the source coding. In this paper we propose a combination of the following three factors: (1) an optimal friendly spread routing, (2) a little permanent constant tolerance to combat bursts and (3) an added layer of a dynamic adaptive end-to-end coding to combat outages, congestions and long failures.