当前位置: 首页 > news >正文

计算机网络:数据链路层 - CSMA/CD协议

计算机网络:数据链路层 - CSMA/CD协议

    • 媒体接入控制
    • CSMA/CD协议
      • 截断二进制指数退避算法
      • 帧长与帧间间隔
      • 信道利用率


媒体接入控制

如图所示,这是一根同轴电缆,有多台主机连接到这根同轴电缆上,他们共享这根传输媒体,形成了一个总线型的局域网。各主机竞争使用总线随机的在信道上发送数据。

在这里插入图片描述

如果恰巧有两个或更多的站点在同一时刻发送数据,那么信号在共享媒体上就要产生碰撞,即发生了冲突,使得这些站点的发送都失败。

共享信道要着重考虑的一个问题就是如何协调多个发送和接收站点对一个共享传输媒体的占用,也就是媒体接入控制

媒体接入控制技术主要分为两类,静态划分信道动态接入控制

静态划分信道:

静态划分信道主要有频分多址时分多址波分多址码分多址

静态划分信道,也就是预先固定分配好信道。这类方法非常不灵活,对于突发性数据传输,信道利用率会很低。通常在无线网络的物理层中使用,而不是在数据链路层中使用。该方面知识我已在物理层讲解:[计算机网络:物理层 - 信道复用]

动态接入控制:

动态接入控制又可以分为两类,一类是受控接入,另一类是随机接入

受控接入

用户要遵循一定的规则发送数据,而不能随意的发送数据

随机接入:

所有站点通过竞争随机的在信道上发送数据

随机接入存在一个问题,因为站点发送信息是随机的,如果恰巧有两个或更多的站点在同一时刻发送数据,那么信号在共享媒体上就要产生碰撞,使得这些站点的发送都失败。因此,随机接入这类协议要解决的关键问题是如何尽量避免冲突,以及在发生冲突后如何尽快恢复通信

著名的共享式以太网采用的就是随机接入。需要注意的是,随着技术的发展,交换技术的成熟和成本的降低,具有更高性能的使用点对点链路和链路层交换机的交换式局域网在有限领域已完全取代了共享式局域网,但由于无线信道的广播天性,无线局域网仍然使用的是共享媒体技术。


CSMA/CD协议

如图所示,多个主机连接到一根总线上,各主机随机发送帧:

在这里插入图片描述

当两个或多个主机同时发送帧时,代表帧的信号就会产生碰撞或成为冲突。又或者当某个主机正在使用总线发送帧的过程中,另一台主机也要发送帧,这同样也会产生碰撞。

很显然,如何协调总线上各主机的工作,尽量避免产生碰撞是一个必须要解决的重要问题。早期的共享式以太网采用载波监听多点接入碰撞检测,也就是CSMA/CD协议来解决该问题。

多点接入MA:多个主机连接在一条总线上,竞争使用总线
载波监听CS:每一个站点在发送帧之前,先要检测一下总线上是否有其他站点在发送帧
碰撞检测CD:每一个正在发送帧的同时,一边发送帧一边检测。一旦发现总线上出现碰撞,则立即停止发送,退避一段随机时间后再次重新发送

这三个特性都还比较好理解,多点接入也就是一条线上有多个主机,它们随机发送信息就有可能产生碰撞;载波监听就是再发送数据前,要先检测一下现在有没有其他主机在发送,如果有就先不发送;碰撞检测就是在发送数据的时候,要确保数据发送的时候没有发生碰撞。

而三者的英文缩写分别是MACSCD,因此该协议称为CSMA/CD协议。

第一个问题就是,主机明明在发送数据之前,就已经检测了信道上有没有主机在发送数据,为什么还有可能会发生碰撞?

我们看到以下情况:

在这里插入图片描述
现在整个信道上都没有信号传输,A检测到信道空闲,发送数据。

在这里插入图片描述

A发送信号不久后,此时信号还没有传送到D,D也想发送信号,D检测到信道空闲,也发送了信号。于是两个信号就会发生碰撞:

在这里插入图片描述

也就是说,电磁波在信道上传播的速率是有限的,当计算机监听到信道空闲而发送数据时,有可能已经有其它计算机在发送数据了

现在规定,一条信道中,最远的两台主机之间发送信号所需的时延为 τ \tau τ τ \tau τ音同“涛”。以上例子中,A和D就是该信道里面最远的两台主机,假设A发送数据的时间节点为0,那么该数据到达D的时间节点就是 τ \tau τ,而D在 τ − δ \tau - \delta τδ时刻发送了数据:

在这里插入图片描述

那么有以下重要时间点:

发生碰撞的时间为 τ − δ 2 {\color{red}\tau - \frac{\delta}{2}} τ2δ
D检测到碰撞的时间为 τ {\color{red}\tau} τ
A检测到碰撞的时间为 2 τ − δ {\color{red}2\tau - \delta} 2τδ

δ \delta δ可以视为是在即将接收到A信号前的 δ \delta δ时间,D发送了数据。当 δ \delta δ趋近于0,那么A检测到碰撞的时间就越接近 2 τ {\color{red}2\tau} 2τ。因为此时A和D已经是信道中最远的两台主机了,因此可以理解为一台主机发送一个信号,最多经过 2 τ {\color{red}2\tau} 2τ的时间,就可以确定自己是否发生了碰撞。因为只有在 2 τ {\color{red}2\tau} 2τ时间内,才有可能有其他主机发送数据产生碰撞,一旦过了 2 τ {\color{red}2\tau} 2τ的时间,所有主机一旦想发送数据,就会先进性载波监听,发现信道已经被占用了,就不会再发送数据了。

其中 2 τ {\color{red}2\tau} 2τ被称为争用期或者碰撞窗口,以太网中争用期被规定为 51.2 μ s 51.2\mu s 51.2μs。主机发送数据的同时,只需要进行 2 τ 2\tau 2τ时间的载波监听,就可以不再进行监听了,因为后续传送的数据一定不会发生碰撞。

显然,在以太网中主机越多,端到端的往返时延越大,发生碰撞的概率就越大。因此共享式以太网不能连接太多主机,使用的总线也不能太长

10Mb/s的以太网把争用期定为512比特发送时间,即 51.2 μ s 51.2\mu s 51.2μs,因此其总线长度不能超过5120m,但是由于一些其它因素,比如信号衰减等,以太网规定总线长度不能超过2500m。

现在我们讲解完了什么情况下会碰撞,以及如何检测出碰撞。那么两个信号发生碰撞后,要怎么办呢?


截断二进制指数退避算法

当两个主机发送的数据发生碰撞后,都要进行一个退避操作,简单来说就是过一会再发送一次,那么过一会是多久呢?如果说退避时长差不多,那么两主机过一段时间后同时发送,又会发生碰撞,因此这个退避时间必须是随机的。在CSMA/CD协议中,采用了截断二进制指数退避算法来进行退避操作,以产生随机的数值进行退避,确保主机碰撞后退避的时间不同。

算法如下:

  1. 规定基本退避时间为 2 τ 2\tau 2τ
  2. 定义参数 k = min(重传次数, 10)
  3. 从整数区间[0, 2 k − 1 2^{k} - 1 2k1]随机选一个数字r,最后的退避时间为 r × 2 τ {\color{Red} r \times 2\tau } r×2τ
  4. 如果重传16次依然不成功,丢弃该帧并向高层汇报

接下来我再详细讲解以上算法的执行过程。

首先要设置一个基本的退避时间,该时间被设置为 2 τ 2\tau 2τ。而最后的总退避时间,就等于一个随机数r乘以这个基本退避时间 2 τ 2\tau 2τ,也就是 r × 2 τ {\color{Red} r \times 2\tau } r×2τ

那么现在的问题就是,要如何生成这个随机数r。该随机数r取自一个区间[0, 2 k − 1 2^{k} - 1 2k1],而这个k不是一个固定的数值,其与重传次数相关。

  • 如果重传次数小于10,那么 k 就是重传次数
  • 如果重传此处大于10,那么 k = 10

比如说当前是第2次重传,那么k = 2,r的取值范围就是[0, 2 2 − 1 2^{2} - 1 221],也就是[0, 3]。最后r在这个区间内随机取一个值,最终的退避时间就是 r × 2 τ r \times 2\tau r×2τ

再比如当前是第14次重传,由于重传次数超过10,那么k = 10,r的取值范围就是[0, 2 10 − 1 2^{10} - 1 2101],也就是[0, 1023]。最后r在这个区间内随机取一个值,最终的退避时间就是 r × 2 τ r \times 2\tau r×2τ

随机数 r 是从离散的整数集合[0, 2 k − 1 2^{k} - 1 2k1]中随机选出的一个数,这也是该算法名称截断二进制指数称谓的由来。


帧长与帧间间隔

最短帧长

假设主机 A 正在给主机 D 发送一个很短的帧,边发送边检测碰撞,主机 A 很快就将该帧发送完毕了,之后就不再对该帧检测碰撞:

在这里插入图片描述

在该帧的传输过程中,主机 C 也要发送帧,主机 C 检测到总线空闲后就立即发送帧。

在这里插入图片描述

这必然会产生碰撞,主机 D 最终会收到主机 A 发送的并遭遇碰撞的帧。主机 D 会将该帧丢弃,但对于主机 A 而言,他并不知道自己已发送完毕的该帧在总线上传输的过程中遭遇了碰撞,因此不会重发该帧。很显然,使用CSMA/CD协议的以太网的帧长不能太短。

以太网规定最小帧长为 64 字节,即 512 个比特,而发送 512 个比特的时间即为争用期。如果要发送的数据非常少,那么必须加入一些填充字节,使帧长不小于 64 字节以太网的最小帧长确保了主机可在帧发送完成之前就检测到该帧在发送过程中是否遭遇了碰撞

最大帧长

假设主机 A 正在给主机 D 发送一个很长的帧:
在这里插入图片描述

这会使得主机 A 长时间占用总线,而总线上的其他主机迟迟拿不到总线的使用权。另外,由于帧很长,还可能导致主机 D 的接收缓冲区无法装下该帧而产生溢出,因此以太网的帧长应该有其上限。

例如这是以太网版本 2 的MAC帧格式:
在这里插入图片描述

  • 最大帧长:其数据载荷的最大长度为 1500 字节,加上首部和尾部共 18 字节,帧的最大长度为 1518 字节

  • 最短帧长:数据载荷的最小长度不能小于 46 字节,这样加上首部和尾部共 18 字节,正好满足帧的最小长度为 64 字节

帧间间隔

另外,以太网还规定帧间最小间隔为 9.6 μ s 9.6\mu s 9.6μs在没有发生碰撞的情况下,一台计算机即使检测到信道空闲,也要等 9.6 μ s 9.6\mu s 9.6μs才能再次发送数据

这是为例使刚刚收到数据帧的计算机的缓存来得及清理,为接收下一帧做好准备。


信道利用率

接下来我们来讨论一下使用 CSMA/CD 协议的共享式以太网的信道利用率。如图所示,横坐标为时间:

在这里插入图片描述

总线上的某个主机可能发生多次碰撞,进行多次退避后成功发送了一个帧,最后帧经过发送时延 T 0 T_{0} T0把数据发送了出去。

在最极端的情况下,两台主机处于总线两端,因此还要经过一个单程端到端的传播时延后,总线才能完全进入空闲状态。因此发送一帧所需的平均时间为多个争用期 2 τ 2\tau 2τ 加上一个帧的发送时延 T 0 T_{0} T0,再加上一个单程端到端的传播时延 τ \tau τ

发送一帧的时间 = n × 2 τ + T 0 + τ 发送一帧的时间 = n \times 2\tau + T_{0} +\tau 发送一帧的时间=n×2τ+T0+τ

考虑以下这种理想情况,各主机发送帧都不会产生碰撞,总线一旦空闲,就有某个主机立即发送帧。发送一帧所占用总线的时间为 T 0 T_{0} T0,加上传播时延 τ \tau τ。这样就可得出极限信道利用率的表达式:

S max ⁡ = T 0 T 0 + τ S_{\max }=\frac{T_{0}}{T_{0}+\tau} Smax=T0+τT0

在以太网中,我们把参数a定为 τ \tau τ T 0 T_{0} T0之比:

a = τ T 0 a=\frac{\tau}{T_{0}} a=T0τ

因此极限信道利用率可以写为:
S max ⁡ = T 0 T 0 + τ = 1 1 + a S_{\max }=\frac{T_{0}}{T_{0}+\tau}=\frac{1}{1+a} Smax=T0+τT0=1+a1

为了提高信道利用率,参数 a 的值应尽量小,要是参数 a 的值尽量小, τ \tau τ的值应该尽量小。这意味着端到端的距离应受到限制,不应太长,而 T 0 T_{0} T0 的值应当尽量大。这意味着以太网的帧长应尽量大一些


相关文章:

计算机网络:数据链路层 - CSMA/CD协议

计算机网络:数据链路层 - CSMA/CD协议 媒体接入控制CSMA/CD协议截断二进制指数退避算法帧长与帧间间隔信道利用率 媒体接入控制 如图所示,这是一根同轴电缆,有多台主机连接到这根同轴电缆上,他们共享这根传输媒体,形成…...

力扣LeetCode138. 复制带随机指针的链表 两种解法(C语言实现)

目录 题目链接 题目分析 题目定位: 解题思路 解题思路1(粗暴但是复杂度高) 解题思路2(巧妙并且复杂度低) 题目链接 138. 复制带随机指针的链表https://leetcode-cn.com/problems/copy-list-with-random-pointer/ …...

强大的压缩和解压缩工具 Keka for Mac

Keka for Mac是一款功能强大的压缩和解压缩工具,专为Mac用户设计。它支持多种压缩格式,包括7z、Zip、Tar、Gzip和Bzip2等,无论是发送电子邮件、备份文件还是节省磁盘空间,Keka都能轻松满足用户需求。 这款软件的操作简单直观&…...

论文速读:Do Generated Data Always Help Contrastive Learning?

在对比学习领域,最近很多研究利用高质量生成模型来提升对比学习 给定一个未标记的数据集,在其上训练一个生成模型来生成大量的合成样本,然后在真实数据和生成数据的组合上执行对比学习这种使用生成数据的最简单方式被称为“数据膨胀”这与数据…...

华为欧拉系统(openEuler-22.03)安装深信服EasyConnect软件(图文详解)

欧拉镜像下载安装 iso镜像官网下载地址 选择最小化安装,标准模式 换华为镜像源 更换华为镜像站,加速下载: sed -i "s#http://repo.openeuler.org#https://mirrors.huaweicloud.com/openeuler#g" /etc/yum.repos.d/openEuler.r…...

git commit --amend用法

一、git commit --amend 修改提交信息:您可以使用 git commit --amend 命令来修改最新提交的提交信息。执行该命令后,Git 将会打开文本编辑器(通常是的默认文本编辑器),以便编辑提交信息。完成编辑后保存并关闭编辑器…...

分布式系统:缓存与数据库一致性问题

前言 缓存设计是应用系统设计中重要的一环,是通过空间换取时间的一种策略,达到高性能访问数据的目的;但是缓存的数据并不是时刻存在内存中,当数据发生变化时,如何与数据库中的数据保持一致,以满足业务系统…...

JavaEE企业开发新技术5

目录 2.18 综合应用-1 2.19 综合应用-2 2.20 综合应用-3 2.21 综合应用-4 2.22 综合应用-5 Synchronized : 2.18 综合应用-1 反射的高级应用 DAO开发中,实体类对应DAO的实现类中有很多方法的代码具有高度相似性,为了提供代码的复用性,降低…...

mysql dump导出导入数据

前言 mysqldump是MySQL数据库中一个非常有用的命令行工具,用于备份和还原数据库。它可以将整个数据库或者特定的表导出为一个SQL文件,以便在需要时进行恢复或迁移。 使用mysqldump可以执行以下操作: 备份数据库:可以使用mysqld…...

刷题记录3

# 10 字符个数统计 描述 编写一个函数,计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内( 0~127 ,包括 0 和 127 ),换行表示结束符,不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次 例如,对…...

Decorator 装饰

意图 动态的给一个对象添加一些额外的职责。就增加功能而言,Decorator模式比生成子类更加灵活 结构 其中: Component定义一个对象接口,可以给这些对象动态的添加职责。ConcreteComponent定义一个对象,可以给这个对象添加一些职…...

SpringMVC:搭建第一个web项目并配置视图解析器

👉需求:用spring mvc框架搭建web项目,通过配置视图解析器达到jsp页面不得直接访问,实现基本的输出“hello world”功能。👩‍💻👩‍💻👩‍💻 1 创建web项目 1…...

一文了解HTTPS的加密原理

HTTPS是一种安全的网络通信协议,用于在互联网上提供端到端的加密通信,确保数据在客户端(如Web浏览器)与服务器之间传输时的机密性、完整性和身份验证。HTTPS的加密原理主要基于SSL/TLS协议,以下详细阐述其工作过程&…...

Ubuntu系统空间整理

查看文件大小命令 查看文件以及文件夹大小 ls -hl #查看文件大小,-h 表示Human-Readable ll -h #查看文件夹的大小 #du命令查看文件或文件夹的磁盘使用空间,–max-depth 用于指定深入目录的层数。#查看当前目录已经使用总大小及当前目录下一级文件或…...

PHP Storm 2024.1使用

本文讲的是phpstorm 2024.1最新版本激活使用教程,本教程适用于windows操作系统。 1.先去idea官网下载phpstorm包,我这里以2023.2最新版本为例 官网地址:https://www.jetbrains.com/zh-cn/phpstorm/ 2.下载下来后安装,点下一步 …...

王东岳-知鱼之乐【边读边记】1

2024-04-15 21:00 终于打算开始读这本书了,作者王东岳,第一次听到这个名字,是因为传说王东岳是李善友的师父,我是先从混沌学院知道的李善友,因为李善友还是有东西的,所以我对王东岳起步也是非常尊敬的。所以…...

迁移docker部署的GitLab

目录 1. 背景2. 参考3. 环境4. 过程4.1 查看原docker启动命令4.2 打包挂载目录传至新宿主机并创建对应目录4.3 保存镜像并传至新宿主机下4.4 新宿主机启动GitLab容器 5 故障5.1 容器不断重启5.2 权限拒绝5.3 容器内错误日志 6 重启容器服务正常7 总结 1. 背景 最近接到一个任务…...

今年消费新潮流:零元购商业模式

今天给大家推荐一种极具创新的电子商务模式:零元购商业模式 这个模式支持消费者以零成本或极低成本购买商品。这种模式主要通过返现、积分、优惠券等方式来减少支付金额,使消费者实现“零成本”购物的目标。 人民网在去年发表了一篇文章。 总结了一下&a…...

Go导入私有仓库

使用go.mod依赖第三方库时,有以下要求: 代码仓库托管于VCS(版本控制系统);代码仓库是公开的;仓库地址使用域名访问;仓库域名支持HTTPS访问。 对于自己或者公司内部搭建的私有git,这些条件是比较难同时满足…...

GIS GeoJSON数据获取

1、工具地址 DataV.GeoAtlas地理小工具系列 2、界面预览...

书生·浦语大模型实战营 | 第3次学习笔记

前言 书生浦语大模型应用实战营 第二期正在开营,欢迎大家来学习。(参与链接:https://mp.weixin.qq.com/s/YYSr3re6IduLJCAh-jgZqg 第三堂课的视频链接:https://www.bilibili.com/video/BV1QA4m1F7t4/ 本次笔记是学习完第三堂课…...

easyExcel - 按模板导出

目录 前言一、情景介绍二、文档介绍2.1 读取模板2.2 填充模板 三、代码示例3.1 案例一:工资表3.2 案例二:报价单 四、我所遇到的问题 前言 Java-easyExcel入门教程:https://blog.csdn.net/xhmico/article/details/134714025 之前有介绍过如…...

使用 Tranformer 进行概率时间序列预测实战

使用 Transformers 进行概率时间序列预测实战 通常,经典方法针对数据集中的每个时间序列单独拟合。然而,当处理大量时间序列时,在所有可用时间序列上训练一个“全局”模型是有益的,这使模型能够从许多不同的来源学习潜在的表示。…...

LLM大语言模型助力DataEase小助手,新增气泡地图,DataEase开源数据可视化分析平台v2.5.0发布

2024年4月8日,DataEase开源数据可视化分析平台正式发布v2.5.0版本。 这一版本的功能升级包括:新增DataEase小助手支持,通过结合智能算法和LLM(即Large Language Model,大语言模型)能力,DataEas…...

维修伊顿触摸屏不显示工业电脑人机界面EATON XVS-430-10MPI-1-10 深圳捷达工控维修

人机界面 (HMI) XP500 工业 PC 系列 以不同的方式思考工业平板电脑 对于严酷、高要求的应用,工业平板电脑设定了可配置性和稳健性的标准。伊顿的 XP500 系列工业平板电脑凭借防刮钢化玻璃屏幕、铸铝外壳和无风扇设计满足了这些需求。这些功能使 XP500 HMI成为一款节…...

趣话最大割问题:花果山之群猴博弈

内容来源:量子前哨(ID:Qforepost) 编辑丨浪味仙 排版丨 沛贤 深度好文:3000字丨15分钟阅读 趋利避害,是所有生物遵循的自然法则,人类也不例外。 举个例子,假如你是某生鲜平台的配…...

上周面试了一个大模型算法岗的女生,有点崩溃。。。

节前,我们星球组织了一场算法岗技术&面试讨论会,邀请了一些互联网大厂朋友、参加社招和校招面试的同学,针对算法岗技术趋势、大模型落地项目经验分享、新手如何入门算法岗、该如何准备、面试常考点分享等热门话题进行了深入的讨论。 汇总…...

AI系列:大语言模型的function calling

目录 大语言模型(LLM) 的function calling实验:OpenAI之function calling序列图:function calling如何工作详情: 对话内容参考代码 后续: 使用LangChain实现function calling参考 大语言模型(LLM) 的function calling 大语言模型(LLM)可以使用自然语言与…...

conda 创建、激活、退出、删除虚拟环境

一、conda 本地环境常用操作 #获取版本号 conda --version 或 conda -V #检查更新当前conda conda update conda #查看当前存在哪些虚拟环境 conda env list 或 conda info -e #查看--安装--更新--删除包 conda list: conda search package_name# 查询包 cond…...

【Entity Framework】聊一聊EF中继承关系

【Entity Framework】聊一聊EF中继承关系 文章目录 【Entity Framework】聊一聊EF中继承关系一、概述二、实体类型层次结构映射三、每个层次结构一张表和鉴别器配置四、共享列五、每个类型一张表配置六、每个具体类型一张表配置七、TPC数据库架构八、总结 一、概述 Entity Fra…...

高端网站鉴赏/免费引流微信推广

有时候共享了文件夹,别人却无法访问,有可能是因为对方访问的用户没有密码导致的,给访问用户设置密码就可以. 但是有时候由于各种原因,不能给用户设置密码,这可怎么办? 其实这是一个安全策略导致的,该策略要求:使用空密码的账户只能通过控制台登陆. 把它关了就行,它在这里: 转载…...

智能手机软件开发/湖北网站seo设计

题库来源:安全生产模拟考试一点通公众号小程序 2022熔化焊接与热切割操作考试题是熔化焊接与热切割考试题库仿真模拟预测!2022熔化焊接与热切割上岗证题目及模拟考试依据熔化焊接与热切割新考试大纲。熔化焊接与热切割复审模拟考试通过安全生产模拟考试…...

网站开发需要的技术人员有什么软件/武汉seo网站排名优化

java jupyter无论您在培训中遇到过障碍,无论是老师还是学生,我相信我们都有相同的经验:几个小时很难集中精力。 近年来,这种情况只会变得更糟,因为手机是分散注意力的巨大来源。 结果是最重要的部分是实践。 学生需要将…...

个人域名备案网站名称/搜索引擎优化的基本原理

第1章 第2章 第3章 第4章 第5章 第6章 第7章 第8章 第9章 第10章 第11章 第12章 第13章 第14章 第15章 第16章 第17章...

wordpress仪表盘404/aso优化吧

近年来,数字化转型已经成为当前全行业共同关注的话题,对于传统行业,尤其是中小型企业而言,如何减少构建数字解决方案所花费的时间和资源,加速数字化升级,才是决胜数字化时代的关键。而在数字化转型“降本增…...

网站建设具体工作有什么/400个成品短视频

一、初识正则表达式类似于对象、数组,正则表达式也有表达式写法和构造函数写法两种var re /a/ // 需要注意的是,这里//之间必须得有内容,否则会当做注释 var re new RegExp(a)复制代码以上两种写法是等价的。二、testtest方法用来判断…...