用户注册 登录
珍珠湾全球网 返回首页

岳东晓 -- 珍珠湾全球网 ... http://ydx.zzwave.com [收藏] [复制] [分享] [RSS] 岳东晓 -- 珍珠湾全球网

日志

穿墙神器的数学

已有 1660 次阅读2023-1-21 04:37 |个人分类:科普|系统分类:科技

前两天在用 WireGuard 将两个分别在不同路由器后面的局域网连起来,结果发现有一款穿墙神器 Tailscale 不仅将 WireGuard 设置大大简化,而且巧妙的用到数学知识进行穿墙,实现不同局域网直连。不得不大赞。

WireGuard 是一个基于 UDP的极为简单高效的点对点加密通信与转送协议 (https://www.wireguard.com/)。我最初的设置是在互联网服务器上安装 WireGuard作为中转站,两个局域网都用 WireGuard 与这个中转站建立通道,这样两个局域网就通过中转相连了。看起来相当不错,缺点数据都得经过一个中转站。在网上搜索时发现有一个以 WireGuard 作为数据面的称为 TAILSCALE 的控制系统可以实现局域网不通过中转直连。而为了实现穿墙直连,TAILSCALE 开发者可谓绞尽脑汁。

WireGuard 通道建立的前提是点对点之间能够互相发送-接收 UDP 数据包。UDP数据包从局域网节点发出去时,路由器会进行数据包网络源地址进行翻译,将数据包的IP转换成路由器的公开IP,将数据包的源端口进行替换。这叫做 NAT。NAT又分两种,一种是源端口替换只取决于源IP与端口,这是一种容易穿透的墙 --- 通讯双方通过一个第三方进行端口信息交换即可,且让我们称之为软墙。一种是源端口的替换不仅取决于源IP与端口,还取决于目标IP与端口,这要穿透就难了--这是一堵硬墙。难道这种情况下由只能回到通过中转进行通讯了吗?TAILSCALE 开发者们没有轻易放弃。他们给出了一端是软墙、一端是硬墙的穿透方案。那就是随机猜测硬墙一端的端口。而这里面用到了所谓“生日悖论”的数学知识。

一个人生日有365种可能性,从1月1日,到12月31日(不考虑特殊年份)。一个班有  n 名学生,至少有两个同学生日相同(同月同日)的几率是多少呢?我们可以计算没有任何两个同学生日相同的几率(也就是所有同学生日都不同),然后用100%减去它,就是至少有两个同学生日相同的几率了。

以班上只有5人为例,第二个同学与第一个同学生日不同的几率是 364/365, 第三名同学与前二人生日不同的几率是 353/364。以此类推,5人生日完全不同的几率是 364/365 * 363/365 * 362/365*361/365 ~ 0.97,也就是说 5人中至少两人生日相同的几率是 3%。稍作推算,如果是 n 个学生,其生日完全不同的几率是(365-1)!/(365-n)!/(365)^(n-1) 。如果是50人,这是 364!/315!/365^49 ~ 2.95% 。也就是说 一个50人的班里,至少有两个同学生日相同的几率是 97%。

受生日问题的启发,TAILSCALE 为了解决软墙-硬墙的穿透问题采取的方法是,在硬墙内部一端,随机选择 P 个源端口,向软墙一端发送UDP数据包,同时软墙内部则随机挑选 G 个目标端口向硬墙发送UDP数据包,如果两者正好对上了,软墙发出的数据包就能被硬墙内的一端收到,从此实现穿墙。现在让我们计算一下两个随机选择正好有一组对上的几率。

设端口数的范围是 N (对于现有协议来说,端口是16比特数,N是从1到 2^26-1 = 65535)。软墙一段第一次碰对的几率是 (N-P)/N。第二次尝试时,可能目标减少了一个,变成 N-1,因此第二次碰对的几率是 (N-1-P)/(N-1)。G 次尝试全部没有碰对的几率 是 p =(N-P)/N * (N-1-P) / (N-1) * (N-2-P)/(N-2) ...* (N-G+1-P) /(N-G+1)。
也就是  p= (N-P)! * (N-G)! /N! / (N-P-G)! 。假设 P = 256, G=1024,也就是一段随机选择 256 端口,另一端进行 1024次随机猜测,全部猜错的几率是 (65535-256)!*(65535-1024)!/65535! /(65535-256-1024)! = 0.0176,也就是说猜对端口的几率是 98.24%。TAILSCALE 的开发人员写了一个Python 程序,用随机模拟的方法得到了这个几率,具体来说就是随机选择P个端口,然后随机进行G次猜测,这样反复多次,看碰对的成功率 (https://github.com/danderson/nat-birthday-paradox/blob/master/paradox.py)。但这有点小学生而且浪费CPU,我们应该给出一个解析公式。

由于N 相当大,而 P, G,相对较小,我们可以使用斯特林近似。$\ln n! \approx \int_1^n \ln x dx = [x \ln x -x ]_1^n = n \ln n -n +1 $


$\ln p= \ln \frac{(N-P)! (N-G)! }{N! (N-P-G)! } \\ \approx (N-P) \ln (N-P) -(N-P) + (N-G) \ln (N-G) - (N-G) - N \ln N +N - (N-P-G) \ln (N-P-G) +(N-P-G) \\ = N \ln \frac{N-P}{N} -P \ln (N-P) +(N-G) \ln \frac{N-G}{N-P-G} +P \ln (N-P-G)\\ \approx -P +P -P \ln \frac{N-P}{N-P-G} \\ \approx -\frac{P \ G}{N-P-G} $
 
上面利用  ln(1+x) = x 的近似进行了简化,我最终得到 

$\ln p = - P G /(N-P-G) $
 
也就是说  $p = e^{-\frac {P \ G}{N-P-G}}$

最后,我们得到随机对碰成功几率为 

$S = 1-p = 1- e^{-\frac {P \ G}{N-P-G}}$

JavaScript 代码为  
function collisionProbability ( P,G, N=65535) { 
return  1- Math.exp ( - P*G /(N-G-P)) ;
}

下面是S公式的代入不同P,G值的数据,与 TAILSCALE 开发人员模拟出的结果一致 (tailscale.com/blog/how-nat-traversal-works/):
P=256, G = 174, S = 0.495
P=256, G = 256, S = 0.635
P=256, G =1024, S = 0.983
P=256, G =2048, S = 0.999


路过

鸡蛋

鲜花

支持

雷人

难过

搞笑
 

评论 (0 个评论)

facelist

您需要登录后才可以评论 登录 | 用户注册

Archiver|手机版|珍珠湾全球网

GMT+8, 2024-3-28 19:20 , Processed in 0.028609 second(s), 8 queries , Apc On.

Powered by Discuz! X2.5

回顶部