退避算法

怼烎@ 2022-06-08 14:24 110阅读 0赞

在通信中经常遇到同一线路中出现多个信息需要同时发送，这个时候会产生信息碰撞，导致信息丢失。有什么解决方式呢？退避算法是一种较为常用的解决方式。在ETH网络通信中，使用CSMA方式，载波监听，多次重发方式来规避冲突。

退避算法是指在一次传输失败后，经过一个随机补偿等待时间T后，避免产生第二次冲突。其主要用于CSMA冲突分解，二进制指数退避可以取得较好的分解效果。

**转载：**

退避算法是在在单个信道的基于竞争的介质的一种访问控制（MAC）协议。每当一个以上的节点在同一时刻试图访问介质的时候，它会导致分组碰撞。如果相撞的节点试图再次访问信道，在节点做及时同步的时候数据包将发生碰撞。因此，节点需要时间位差。为了产生这种位差，退避算法（例如二进制指数退避（BEB）） 。例如，在BEB算法中，每当一个节点的传输涉及在与另一个节点的传输发生碰撞，两个节点都将选择一个随机的等待时间，在下次再次尝试前需要等待选择的随机时间。如果他们在这样的尝试都没有成功，他们自己的竞争窗口增加一倍，在发射前再次选择等待一个随机时间。这个过程将被重复一定次数的尝试。如果经过数次尝试之后都失败了，那么其传输的数据包将被从传输队列中移除。

早期以太网使用的退避算法称为二进制指数类型退避算法，具体进行如下：

1）确定基本退避时间（基数），一般定为2τ，也就是一个争用期时间（争用期在后面给出定义），对于以太网就是51.2μs。

2）定义一个参数K，为重传次数，K＝min\[重传次数，10\]，可见K≤10。

3）从离散型整数集合\[0，1，2，……，(2^k－1)\]中，随机取出一个数记做R。

（备注：2^k是2的k次方幂，这里上标表示不出来，敬请原谅）

那么重传所需要的退避时间为R倍的基本退避时间：即：T＝R×2τ。

4）同时，重传也不是无休止的进行，当重传16次不成功，就丢弃该帧，传输失败，报告给高层协议。

如：第一次重传K＝1，R＝0，1；T＝0，2t。T在二者中随机选择。

那么第二次重传呢？K＝2，R＝0，1，2，3；T＝0，2t，4t，6t。

如此可见，重传数次越多，则退避的时间就越长，称为动态退避。

说到这里大家应该所有明白了吧，还有什么问题可以接着跟贴提出！

附录：什么是争用期？

在总线传输线路上，单程端到端的传输时延记做t。一个站点在发出数据到接收到线路冲突的时间小于等于2倍t，也就是时延为2t，这个时间被称为争用期。（contention period）

发表评论取消回复

表情：

评论列表（有 0 条评论，110人围观）

还没有评论，来说两句吧...

相关阅读

相关算法--排序算法

首发网址：[算法--排序算法\_IT利刃出鞘的博客-CSDN博客][--_IT_-CSDN] 其他网址 [一文搞定十大经典排序算法（Java实现） - 简书][Java

叁歲伎倆/ 2023年02月14日 02:23/ 0 赞/ 151 阅读

相关重试中的指数退避算法

重试中的指数退避算法退避算法：退避算法是在在单个信道的基于竞争的介质的一种访问控制（MAC）协议。每当一个以上的节点在同一时刻试图访问介

待我称王封你为后i/ 2022年08月08日 14:49/ 0 赞/ 56 阅读

相关分布式系统的SDK端通用退避策略

分布式系统的SDK端通用退避策略分布式系统中SDK端一般使用退避算法进行重试行为，根据业务使用的场景不同，sdk端退避算法主要有两种：

客官°小女子只卖身不卖艺/ 2022年06月16日 05:07/ 0 赞/ 51 阅读

相关算法-->穷举算法

package 穷举算法; import java.util.Scanner; public class QiongJu { static

╰+哭是因爲堅強的太久メ/ 2022年06月12日 00:57/ 0 赞/ 217 阅读

相关退避算法

在通信中经常遇到同一线路中出现多个信息需要同时发送，这个时候会产生信息碰撞，导致信息丢失。有什么解决方式呢？退避算法是一种较为常用的解决方式。在ETH网络通信中，使用CSMA方

怼烎@/ 2022年06月08日 14:24/ 0 赞/ 111 阅读

相关【算法】KMP算法

【[fishing-pan][]：[https://blog.csdn.net/u013921430][https_blog.csdn.net_u013921430]转载请注

淩亂°似流年/ 2022年05月30日 04:27/ 0 赞/ 407 阅读

相关算法 BF算法

BF算法是字符匹配的一种算法，也称暴力匹配算法算法思想：从主串s1的pos位置出发，与子串s2第一位进行匹配若相等，接着匹配后一位字符若不相等，则返回到s

逃离我推掉我的手/ 2022年05月27日 12:15/ 0 赞/ 268 阅读

相关 flume backoff 退避算法

原文链接： [https://qiuqiang1985.iteye.com/blog/1513049][https_qiuqiang1985.iteye.com_blog_15

妖狐艹你老母/ 2022年03月09日 14:35/ 0 赞/ 93 阅读

相关算法-排序算法

插入排序 / 插入排序 @param arr / public static <T extends Comparab

Love The Way You Lie/ 2022年02月26日 11:12/ 0 赞/ 341 阅读

相关 H3C CSMA/CD冲突检测和退避

![1722024-20190711132346326-261340175.png][] 转载于:https://www.cnblogs.com/fanweisheng

- 日理万妓/ 2021年11月23日 12:34/ 0 赞/ 98 阅读