谈谈CSMACD，TCP中的⼆进制指数退避算法
下⾬，正则安喝完奶睡了，⼩⼩在补她那由于拖延⽽必须在今天下午完成的数学作业，疯⼦正好趁此睡⼀会⼉，她带两个孩⼦，太累了。⽽我，作⽂。
交换式以太⽹，IP路由互联⽹，PCIe总线，这些都不再是 共享资源的随机系统 了，它们都进化成了 排队系统 ，如今这种共享资源的随机系统，只剩下了TCP！
由于⼈们已经不再记得CSMA/CD，绝⼤多数⼈对TCP存在跪舔式的误解，我还是⼀如既往地喜欢喷TCP！但本⽂不是。本⽂没时间扯TCP，没意思。
⼀个共享资源的随机系统，什么最重要？是性能，还是公平性？业内普遍的结论是公平性，这才招致了很多⼈剑⾛偏锋在性能上⾛⽕⼊魔，⽐如TCP加速这种。但凡优化性能的，就⼀定会损失公平性，然⽽，who care…
⼆进制指数退避算法，就是共享资源随机系统的⼀个伟⼤的算法。
记得刚学计算机⽹络课程的时候，讲过CSMA/CD算法，这是⼀个共享总线式的随机协同系统，没有控制中⼼安排节点发送数据的顺序，⼤家也都彼此不沟通，然⽽神奇的是， 所有节点 想什么时候发送数据就能什么时候发送，只要在发现冲突后遵循指数退避等待相应的时间后再重发即可！
这个指数退避规则很简单，本⽂不会详细描述，直接百度⼀下就好。
后来，我们学习了TCP协议，并且任何教科书上都会讲到TCP超时定时器的处理，最终我们学到了， TCP超时时间也是指数退避的。
TCP和早期共享总线以太⽹貌似⼋竿⼦打不着，但是却遵循了同样⼀个指数级退避原则，这⾥⾯必有关联。
后来，哦，不，是直到很久以后，我们觉得TCP是个端到端主机协议，对于真正的⽹络⽽⾔，它和早期的供共享总线的以太⽹对链路的认知⼀样，就是个盲⼈。
所以，我们可以把整个互联⽹看作是⼀个共享总线(实际上是共享带宽)的以太⽹，TCP节点节点就是CSMA/CD的主机，TCP节点之间互相不沟通，但是它们却和CSMA/CD系统的主机⼀样，想什么时候发送就什么时候发送，只要遵循 退避原则 即可。
对于CSMA/CD以太⽹⽽⾔，冲突意味着要退避；
对于TCP⽽⾔，超时意味着要退避(⾄于什么快速重传，那是后来的事情，⼀开始只有超时！)。
现在问题来了， 退避为什么要指数级退避，⽽不是减法退避，或者乘以某个系数退避？
这个问题，此后再也不好答案。
不信你去搜搜，看看有没有解释这个，如此简单的事实却没有⼈从数学上去解释…
本⽂，我来通俗解释⼆进制指数退避算法的缘由。即为什么是⼆进制指数退避，⽽不是减法退避，也不是固定系数乘法退避。
当知道了⼆进制退避算法的具体操作之后，谁还会在乎Why呢？知道Why并不会多赚钱，不会晋升，也不会让⽼婆称赞…
但是知道Why，会使⼈开⼼。
⼆进制退避算法，其实换个名字，就很好理解了，那就是 确定系统中的节点数量，并到⾃⼰的slot。
i n slot i
是的， 节点在和⼀互相不通信不沟通的系统个节点的资源争抢博弈中，到⾃⼰。
为什么是⼆进制指数退避，要先从⼆分法说起。不要纠结于什么⼆进制指数退避这种名⼦，所谓的⼆进制指数退避，你就把它当成 ⼆分法探测 就好了。
系统中的节点是彼此不沟通的，没有任何⼀个节点知道系统的全局情况，这是⼀个真正随机的分布式系统。
⼀开始，节点假设整个系统只有节点⾃⼰，这是⼀个初始状态，于是它开始直接使⽤共享资源，忽略其它节点的存在，直到⼀个 冲突事件 将其纠正。
节点检测了冲突，以太⽹冲突信号或者TCP超时，它怎么办呢？
它理所当然会认为 系统中⾄少还存在着另外⼀个节点。 于是节点会把⾃认为全部属于⾃⼰的资源让出⼀半给这个想象中的竞争者。于是，节点的资源降低为之前的⼀半试试看。
同样收到冲突信号的另⼀个节点也会相应地假设。
现在假设总资源分别被如⼆者分成了两份，那么两个节点该如何判断哪⼀份是属于⾃⼰的呢？由于系统运作的前提是所有节点彼此不沟通，那么，最好的⽅案就是 随机 。即：
两个节点随意使⽤⼀共2个slot的资源。
这样两个节点共享两个slot，它们还是有冲突的可能，它们有的可能会争抢同⼀个slot…
问题是，像这样，两个节点再次出现冲突，怎么办？答案只能是(算法的要求，为什么？这点后⾯会说)继续⼆分退避。此时冲突的概率就降低到了，如果再次冲突，就再次⼆分退避，冲突概率继续降低到…
两个节点的情况下，如此反复，最终，两个节点之间不冲突的概率随着冲突次数⽽降低，序列就是，即 如果继续⼆分切分资源，互不沟通的两个节点总会不冲突把数据发送成功的！
第⼀个推论已经完成。就像做菜⼀样，放在⼀边，备⽤。
接下来继续分析。我来推倒多⽶诺⾻牌。
事实上，由于每个节点对系统的理解都是局部的，没有任何节点具有全局视图，因此，没有哪个节点知道系统中⼀共有多少节点。当节点在第⼀次检测到冲突后退避了⼀半的资源之后再次检测到冲突，该节点⽆法分辨下⾯的两种情况：
1. 和唯⼀另外的节点再次以的概率发⽣了冲突；
2. 出现了第三个节点，并与其发⽣了冲突。
根据以上分析，当第⼀种情况发⽣时，按照⼆进制指数减半资源的使⽤，是可以趋向于成功抢占资源的。那么问题就是第⼆种情况如何处理。
最优美的答案就是唯⼀的答案， 那就是和第⼀种情况⼀样，既然⽆法区分两种情况，那就全部当成第⼀种情况！
如果出现第三个节点，由于随机协作系统所有节点都是公平对等的，所有 这第三个节点对于既有的两个节点的影响是均等的。 也就是说，既有的每⼀个节点均需要 假设有⼀个新的节点与之竞争。 这个新的节点对既有的两个节点的影响，在 概率上 是相等的。按照协作系统公平性假设，检测到冲突的节点就需要出让⼀半的资源给潜在的竞争者。
1. 如果某个节点第⼀次遭遇冲突，那么它假设检测到第个共存节点，⾃⾝可利⽤资源承诺⾃减到
2. 在承诺的资源中使⽤，如果再检测到冲突，那么它假设检测到第个共存节点，⾃⾝可利⽤资源承诺⾃减，另⼀个节点也同样概率
检测到该冲突
3. 在承诺的资源中使⽤，如果再检测到冲突，那么它假设检测到第个共存节点，⾃⾝可利⽤资源承诺⾃减，另两个节点也同样概率
检测到该冲突
4. …
n n n n n 50%25%12.5%(1−)，(1−21)，(1−
41
)，...，(≈81
1)50%12
1
21241
41381
把这个基本事实归纳下去。所以，结论就是：
数学二进制的算法不管系统中当前有多少()节点，只要检测到冲突(CSMA/CD检测到冲突信号，或者TCP 超时)，检测节点均要假设有⼀个节点与之进⾏公平对等竞争，检测节点均需要分配⼀半资源给与之冲突的节点：
假设为冲突次数，那么节点需要退避到的资源使⽤率就是，由于⽹络分层协议的保证，为了保证效率，⼀般会有最⼤值约束，超过该最值，则传输放弃。
以上这些话，就是 ⼆进制指数退避算法 的具体操作要旨！
理解了上⾯的描述，对于理解 为什么是减半，⽽不是减1 就很容易了。这是因为，只有减半才能让系统平衡。
⼆进制指数退避算法，只是共享资源的随机系统中的 ⼀种可⾏的确保稳定的算法，⽽不是最⾼效的算法。
CSMA/CD的冲突检测退避算法就是⼀个简单的优化。它采⽤了 再随机算法 平滑了误判的影响。
所谓的误判，就是上⾯两点之间的误判，重复⼀遍：
1. 和唯⼀另外的节点再次以的概率发⽣了冲突；
2. 出现了第三个节点，并与其发⽣了冲突。
所以，假设⼀个节点已经经历了次冲突，按照⼆进制指数退避算法，它理应退避到的资源使⽤，然⽽搞不好其它所有节点都是新来的
呢，所以，⼤家再次随机，让每个检测到冲突的节点，在中随机选择⼀个作为资源退避的份额即可。
总结来讲， ⼆进制指数退避算法 ，如果不叫这个名字，改作 ⼆分法资源探测算法 ，我想就更加容易被理解了。你要明⽩，适⽤这个算法的系统，必须有以下特征：节点随机使⽤资源；节点完全公平对等；
节点间互不知情。同时，我们要知道，正是因为上述的第3点解耦合带来的灵活性，造成了：
⼆进制指数退避算法不是最优的。但是，⽆论如何，它是：公平的；
稳定的。所以，它是：
优美的！
此外，所有的共享总线资源随机分布式系统，均可以转化为排队系统，⽐如：
≥2k ()21
k k 50%i ()21
i {0,,...()}2121
k
总线式以太⽹转换为交换式以太⽹
PCI总线转换为PCIe总线
缓存⼀致性协议中的写操作
…
只有IP路由⽹络，⼀开始就是排队系统…
⽆论是哪种，它们的核⼼都是 资源的统计复⽤。
当然了，我知道有⼈会觉得我这天天分析这种简单⼜不赚钱不讨好的东西，很low，没关系，我觉得你也很low，⼈各有所好，不可强求，不在⼀个频道上，所以我也不屑交流。
我敢肯定，绝⼤多数⼈是不懂这些东西的，⽹上也很少⼏乎没有⼈去分析，所以，我想帮助这些希望获得答案的⼈。仅此。
浙江温州，⽪，鞋湿，
下⾬，进⽔，不会，胖。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。