Archive

Posts Tagged ‘Udp’

如何在高丢包率的链路上建立低延迟连接?

May 20th, 2016 No comments

这是其实通信领域的话题了,低延迟传输有上百种优化方式,上面说的那些冗余码只是很小一部分,不考虑信道容量的冗余编码系统都是在耍流氓,不用等到同信道内跑两套这样的协议你才会发现问题,一套协议再接近信道带宽容量限制时,就会出现指数上升的丢包率,所以不考虑带宽检测的冗余法就是一个残次品。

要系统的解决低延迟传输问题,需要同时在传输层,协议层,路由层,应用层几个方面着手:

传输层带外冗余:弱智重复法

设你要发送的数据为 x1-xn,你实际发送出去的包为 p1-pn,那么比如 Pn = [Xn, Xn-1, Xn-2],重复前面出现过的 1-2个数据,丢包了你可以随时恢复出来。

传输层带外冗余:异或法

每发四个包 x1-x4,你多发一个冗余包,内容为前面四个包的异或: R = x1 ^ x2 ^ x3 ^ x4,那么本组数据五个数据包(x1-x4, R)中任意丢失一个,都可以从其他四个异或得到。当然,不一定要四个包冗余一个,你可以根据情况和丢包率,两个包或者三个包冗余一个。

传输层带外冗余:解方程法

把每个数据包看成一个整数,要发送 x1-x4 四个包,并不直接发送x,而是将他们进行线性运算得到 y1-y7,然后发送出去:

A1 * x1 + B1 * x2 + C1 * x3 + D1 * x4 = y1   收到
A2 * x1 + B2 * x2 + C2 * x3 + D2 * x4 = y2   收到
A3 * x1 + B3 * x2 + C3 * x3 + D3 * x4 = y3   丢失
A4 * x1 + B4 * x2 + C4 * x3 + D4 * x4 = y4   收到
A5 * x1 + B5 * x2 + C5 * x3 + D5 * x4 = y5   丢失
A6 * x1 + B6 * x2 + C6 * x3 + D6 * x4 = y6   收到
A7 * x1 + B7 * x2 + C7 * x3 + D7 * x4 = y7   丢失

接收方收到一组数据以后,发现y3, y5, y7丢失,得到:

A1 * x1 + B1 * x2 + C1 * x3 + D1 * x4 = y1   
A2 * x1 + B2 * x2 + C2 * x3 + D2 * x4 = y2   
A4 * x1 + B4 * x2 + C4 * x3 + D4 * x4 = y4   
A6 * x1 + B6 * x2 + C6 * x3 + D6 * x4 = y6   

如果 y1-y7 在发送的过程中丢失了三个:y3, y5, y7 观察等式。变量任然有4个,参数也任然有四个A1, A2, A4, A6, B?, C?, D? 四个变量,四个等式,那么我们可以通过解方程求出x1-x4,这就是一个矩阵运算和求逆的过程,也就是俗称的 Read-Solomon 冗余码的基本原理(PS: shorthair/long hair 两个库写的很烂呀),实际传输时需要根据网络质量来选择每组数据和冗余包的比例。

传输层网络评估

需要一套比较强大的系统,实时评估当前网络质量(RTT, 丢包率,抖动值,可用带宽),为协议决策提供参考,比如这时一个带宽很大,延迟却很高的信道呢?还是带宽很小,延迟也很小的信道呢?不同的情况对应不同的策略,当前丢包是常规丢包?震荡性丢包?还是接近信道限制出现无可挽回的丢包?再根据当前协议出于什么情况?交互模式还是单向传输模式,来给出最佳的传输策略。不考虑这些情况的协议,都是比较弱智的(比如楼上提到的几种)。

协议层决策模型

根据不同的情况,来推导不同的数据包丢失后,对整体协议的影响,从而通过马科夫决策过程,来找到哪个包丢失的代价最大,以此来指导冗余包的生成过程:

Read more…

Categories: 网络编程 Tags: ,
Wordpress Social Share Plugin powered by Ultimatelysocial