再说说TCP和UDP源端口的确定

栏目: 服务器 · 发布时间: 6年前

内容简介:到达杭州已经两周了,基本已经适应了新环境的工作节奏,在生活上依然有些许困难会感到无助,但相信所有问题在不久终究会解决的,遇到困难的时候就是成长的时候,比如这两周我学会了识别洗发露和护发素,比如我学会了用支付宝扫码坐公交车,等等…本周来说一个老话题,即可以先看看我之前的分析:

到达杭州已经两周了,基本已经适应了新环境的工作节奏,在生活上依然有些许困难会感到无助,但相信所有问题在不久终究会解决的,遇到困难的时候就是成长的时候,比如这两周我学会了识别洗发露和护发素,比如我学会了用支付宝扫码坐公交车,等等…

本周来说一个老话题,即 一个TCP连接如何确定自己的源端口 。这个问题在几年前就分析过,正好前些天一个朋友又问了,我就又进一步进行了思考,觉得正好可以作为本周的话题来讨论一下。

可以先看看我之前的分析:

TCP源端口选择算法与列维模型 https://blog.csdn.net/dog250/article/details/14054987

简单谈一点 linux 内核中套接字的bind机制–数据结构以及端口确定 https://blog.csdn.net/dog250/article/details/5303572

先不要管所谓的什么 列维模型 ,它只是一个大自然中高效的聚集搜索模式,类似幂律一样普遍,这个后面再说,几年前的事了,少时不知愁滋味,纸上谈兵。

现在只看算法就足够了。

当然,这篇文章并没有描述更多的细节,所以我打算在本文中补充一二。

先看内核是如何组织TCP源端口号数据结构,我依然用一个图示表达,这比代码更加清晰一些:

再说说TCP和UDP源端口的确定

以上这个结构在内核中叫做bhash,是TCP协议实现中3个核心hash之一,这3个hash结构分别是:

  • bhash:维护连接的源端口号,以源端口号计算hash值
  • ehash:维护establish连接,以四元组计算hash值
  • lhash:维护侦听TCP,以{srcIP,srcPORT}二元组计算hash值

显然,关于如何确定源端口的问题就转化为了上述数据结构的查询,插入的问题,这个问题的解法是明确的,即:

为新的待确定源端口的连接socket查询到一个最优的插入位置并插入。

我们非常明确的一个目标就是: 维持四元组的唯一性!

这无疑是一个搜索结构的操作问题。哈哈,又是一道面试题咯。

接下来要解决的是,在两个不同的场景下,如何操作以上这个数据结构。两个场景分别如下:

  1. TCP socket在bind的时候
  2. TCP socket在connect的时候

显然,在TCP进行bind的时候,由于此时并不确定目标是谁,无论是目标IP还是目标端口都不确定,甚至不晓得这个TCP是不是一个Listener,那么四元组的唯一性约束显然强化了不少,即: 必须保证{srcIP,srcPORT}二元组的唯一性! 事实上此时我们要保证的是{srcIP,srcPORT,0,0}元组的唯一性。

与bind场景不同的是,如果一个socket事先没有bind,直接调用了connect,当我们调用connect的时候,此时确定的是{dstIP,dstPORT}元组,那么此时的约束就松了不少,也就是说要想保证四元组唯一性,这种场景下给我们的机会会更多一些。

具体来讲,我给出一个流程:

再说说TCP和UDP源端口的确定

有了connect的场景分析,bind场景就再简单不过了,省略下面ehash的部分即可:

再说说TCP和UDP源端口的确定

理清了关系之后,很简单是吧。这里讲的是TCP,对于UDP而言也一样适用,只不过UDP有更简单的解法。

以上就是确定源端口的基本原则,然而在具体操作过程中,还有一个原则,即维护数据结构的平衡型,我们不希望单独的hash冲突链表过长,因为遍历一个冲突链表的时间复杂度是O(n),这显然毫无可扩展性,所以在插入过程中需要 尽量插入到短的hash bucket链表中

这就涉及到另一个问题,即:

图示中初始的探测端口port=pn如何选择的问题!

这里就是列维模型在起作用了!

物理类聚,这是普世真理。Linux内核在实现这个确定源端口的过程中,经过了几次进化,但万变不离其宗,对于TCP而言,Linux从一个随机确定的hash bucket开始探测,然后环状遍历所有的bhash bucket,对每一个bucket执行上面图示里的算法。

对于UDP而言,我劝大家review一下Linux内核2.6.18,3.10,4.9+的代码,这代表了三个进化阶段,起初在2.6.18版本时,UDP维护了一个全局的 udp_port_rover 变量,指示下一次探测可用源端口时从哪里开始,然而到了3.10,4.x版本,实现方式便起了变化,不再通过链表数据结构进行多次广度优先遍历,而是采用深度优先原则使用位图来实现,但这并没有改变实质。

代码并不难懂,相对于像屎一样的TCP拥塞控制算法的代码,这个要好很多,找 get_port 回调函数就好,然后看看 tcp_v4_connect 函数,大概10分钟应该可以读懂,我这里就不再赘述细节,记住一个原则,如果你要实现自己的算法,优先找最短的冲突链表进行遍历插入,你稍微费点事,带来的是整个系统性能的提升,可谓人人为我,我为人人。

最后,我还想说说列维模型。

列维模型最初是2004年由一个名为Dirk Brockmann 的德国物理学家发现的一个普世模型,我最开始看到后简直深陷而不可自拔!

我发现这个简单的模型竟然能解释人类文明的形成,我是多么喜欢历史学,我发现这个模型竟然能解释它,并且能预测未来!

当我看完了《三体》三部曲之后,这更加加深了我对列维模型的好感和狂热!

盗自己之前文章一张图吧,实在是忍着饥饿在写这段文字:

再说说TCP和UDP源端口的确定

这就是列维模型!TCP和UDP确定源端口的算法绝对符合这个模型,不信你接受10w+的连接后导出数据画成图标看看,我试过,你也试试,非常壮美。

你会发现,自然界,我们生活的空间,没有什么东西是平铺平淡的, 正是聚集造就了我们美好的世界 ,不然一堆原子均匀的分布在宇宙空间,那才没有任何意义,然而墒总是在增加,宇宙趋向于无序,这也是宇宙最终的结局,不禁令人感到悲哀!

我一直在关注幂律,如何结合列维模型,我发现列维模型是导致幂律的根本缘由,然而进一步问,列维模型的原因是什么?

我的答案就是 惰性

就我自己而言,我喜欢喝各种新上市的饮料,酒类,我会不断尝试新的东西,但是最终我总是会聚焦到某一个牌子,从此不再过问别的,只买这个牌子,比如真露烧酒,比如百事可乐,比如红标威士忌… 我不换别的牌子不是因为我喜欢这些牌子,而是因为我习惯了这些牌子 , 仅此而已,我的惰性让我在选饮料选酒时,给了真露,百事,红标更多的权重,仅此而已。

进一步思考,这是为什么?

也许就是我大脑的cache吧!我的大脑并不能随时拥抱变化,你的也不行,再强大的大脑都不行,所以我觉得,分级cache是现代计算机科学中非常非常非常重要的一个设计!

拥抱变化,成了一个多么优秀且不可及的潜质,因为没人想拥抱变化!

幂律是什么导致的,我觉得就是惰性的影响导致的聚集效应导致的。

好了,本文该结束了。现在,温州老板正在香港进货。


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

极简人工智能

极简人工智能

[英] 理查德·温 / 有道人工翻译、吴乔 / 电子工业出版社 / 2018-3-1 / 50

本书以通俗的语言和生动的案例带领你探索人工智能的世界,全面展示人工智能的概念、理论框架与应用价值,探讨人工智能的过去和将来,是一本深入浅出的人工智能通识书。从蚂蚁习性谈到股票市场,本书将带领你开启人工智能的奇幻之旅。一起来看看 《极简人工智能》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具