数据链路层服务

概述

image.png

服务

image.png
image.png

链路层的具体实现

image.png

网卡间通信

image.png

练习

题1 链路层服务

image.png

差错编码

差错检测：差错编码

差错编码基本原理：

image.png

差错编码的检错能力

image.png

奇偶校验码

image.png

Internet校验和(Checksum)

image.png

循环冗余校验码(CRC)

image.png

练习

题1 差错检测

image.png

  • 答案为ABC；Internet不使用奇偶校验

    题2 CRC

    image.png

  • 答案为BC，注意G为r+1位模式，故r=3,计算的时候进位不进，借位不借。

    题3 CRC2 考虑到5bit生成多项式，G = 10011，并且假设D为1010101010。

    R的值是什么？image.png

    题4 假设CRC编码的生成比特模式G=10011。请回答下列问题：

    （1）如果数据D=1010101010，则CRC编码后=？
    解：利用G=10011去除1010101010 0000，得R=0100，所以，CRC编码后=10101010100100。
    （2）如果数据D=1010100000，则CRC编码后=？
    解：利用G=10011去除1010100000 0000，得R=1001，所以，CRC编码后=10101000001001。
    （3）如果接收端收到码字01011010101001，则该码字在传输过程中是否发生差错？
    解：利用G=10011去除01011010101001，得余式=0110，不为0000，因此该码字在传输过程中发生差错。
    （4）如果接收端收到码字10010101010000, 则该码字在传输过程中是否发生差错？
    解：利用G=10011去除10010101010000, 得余式=0000，因此该码字在传输过程中未发生差错。

多路访问控制(MAC)协议

image.png

多路访问控制(MAC)协议

image.png

理想MAC协议

image.png

MAC协议分类

image.png

信道划分MAC协议

TDMA

image.png

FDMA

image.png

随机访问MAC协议

image.png

时隙ALOHA协议

image.png
image.png

ALOHA协议

image.png

CSMA协议

image.png

CSMA/CD协议

image.png
image.png

  • 当传输一个给定帧时，在该帧经历了一连串的n次碰撞后，节点随机地从{0,1，2，…，2n-1}中选择一个K值。
  • 一个节点等待的实际时间为K*512比特时间（对100Mbps以太网来说为5.12ms）


轮转访问MAC协议

image.png

轮询(polling)

image.png

令牌传递(token passing)

image.png

MAC协议总结

image.png

练习

题1 MAC协议

image.png

  • 答案为ABC

    题2 CSMA/CD

    image.png

  • 答案为D

    题3 最小数据传输帧

    image.png

  • 答案为A，2500bit；答案少写了0

    题4 轮转MAC

    image.png

  • 答案为BCD

    题5 csma/cd工作原理

    1)适配器从网络层一条获得数据报，准备链路层帧，并将其放人帧适配器缓存中。
    2)如果适配器侦听到信道空闲(即无信号能量从信道进人适配器)，它开始传输帧。在另一方面，如果适配器侦听到信道正在忙，它将等待，直到侦听到没有信号能量时才开始传输帧。
    3)在传输过程中，适配器监视来自其他使用该广播信道的适配器的信号能量的存在。
    4)如果适配器传输整个帧而未检测到来自其他适配器的信号能量，该适配器就完成了该帧。在另一方面，如果适配器在传输时检测到来自其他适配器的信号能量，它中止传输(即它停止了传输帧)。
    5)中止传输后，适配器等待一- 随机时间量，然后返回步骤2。

    题6 时隙ALOHA

    假定4个活跃结点A、B、C和D都使用时隙ALOHA来竞争访问某信道。假设每个结点有无限个分组要发送。每个结点在每个时隙中以概率p尝试传输。第一个时隙编号为时隙1，第二个时隙编号为时隙2，等等

  • A．结点A在时隙5中首先成功的概率是多少？

假设结点A成功的概率为p（A）：
那么在时隙5成功，时隙1~4失败的概率为：
P（A）（1-p（A））^4
又：p（A）=P（1-P）^3
则A在时隙5中首先成功的概率为：
P（1-P）^3【1-（P（1-P）^3）】^4

  • B．某个结点（A、B、C或D）在时隙4中成功的概率是多少？

每一节点在时隙4成功的概率都是：P（1-P）^3
那么A/B/C/D成功的概率为：4p（1-p）^3

  • C．在时隙3中出现首个成功的概率是多少？

任意一个结点在某个时隙成功的概率是：4p（1-p）^3
则时隙3中出现首个成功的概率：
【1-4【p（1-p）^3】】^2 4p（1-p）^3

  • D．这个4结点系统的效率是多少？

效率为：4p（1-p）^3

题7 假设结点A和结点B在相同的10Mbps广播信道上，并且这两个结点的传播时延为245比特时间。假设A和B同时发生以太网帧，帧发生了碰撞，然后A和B在CSMA/CD算法中选择不同的K值。假设没有其他结点处于活跃状态，来自A和B的重传会碰撞吗？为此，完成下面的例子就足以说明问题了。假设A和B在t=0比特时间开始传输。它们在t=245比特时间都检测到了碰撞。假设KA=0,KB=1。B会将它的重传调整到什么时间？A在什么时间开始发送？A的信号在什么时间到达B呢？B在它预定的时刻一直传输吗？

解：

时间 事件
0 A和B开始传输
245 A和B检测碰撞并停止发送数据
293（245+48） A和B完成阻塞信号的发送
538（245+293）

634（538+96）		 B的最后一位到达A，A检测到空闲通道
A开始传输
805（293+512）

901（805+96）

879（634+245）		 B返回步骤2（B发送完拥塞信号开始认为信道空闲）

发送之前，B再继续等待96比特时间

A的传输到达B

901>879，说明A重传在B的预定重传时间前到达B，B在重传时不进行传输。因此A和B不会碰撞。

  • 对于以太网，一个节点等待的实际时间量是K*512比特时间
  • 强化碰撞，当发送数据的站检测到了碰撞，除了立即停止发送数据外，还要继续发送 32 比特或 48 比特的人为干扰信号，以便让所有用户都知道现在已经发生了碰撞。
  • 帧间最小间隔：以太网规定帧间最小间隔为 9.6 μs，即 96比特时间

    题8 在CSMA/CD中，在第5次碰撞后，结点选择K=4的概率有多大?结果K=4在10Mbps以太网上对应于多少秒的时延?

    答：1/2^5=1/32；时延为4 * 51.2μs = 204.8μs

    题9 假设在采用广播链路的10Mbps以太网中，回答下列问题：

    （1）某结点连续第5次冲突后，按二进制指数退避算法，选择K=4的概率是多少？相应地延迟多久再次重新尝试发送帧？
    解：连续第5次冲突后，结点网卡从{0, 1, 2,…, 31}中选择K，因此，选择到K=4的概率为1/32，相应地延迟时间为4512/(1010^6)=0.2048ms=204.8μs。
    （2）如果连续第12次冲突，该结点最多延迟多久再次重新尝试发送帧？
    解：当连续12次冲突后，网卡将从{0, 1, 2,…,1022，1023}中选择K，因此最多延迟时间是选择到K=1023，相应地延迟时间为1023512/(1010^6)=52.3776ms。

    题10 某局域网采用CSMA/CD协议实现介质访问控制，数据传输速率为10 Mbps，主机甲和主机乙之间的距离为2km，信号传播速度是200000km/s。请回答下列问题：

    （1）若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经过多长时间？最长需经过多长时间？（假设主机甲和主机乙发送数据过程中，其他主机不发送数据）
    解：主机甲和主机乙之间单向传播延迟时间= 2km/(200000km/s)=10μs；两台主机均检测到冲突时，最短所需时间和最长所需时间对应下面两种极端情况：
    ①主机甲和主机乙同时各发送一个数据帧，信号在信道中发生冲突后，冲突信号继续向两个方向传播。因此，双方均检测到冲突需要1个单向传播延迟，即10μs。因此，甲乙两台主机均检测到冲突时，最短需经过10μs。
    ②主机甲（或主机乙）先发送一个数据帧，当该数据帧即将到达主机乙（或主机甲）时，主机乙（或主机甲）也开始发送一个数据帧。这时，主机乙（或主机甲）将立即检测到冲突；而主机甲（或主机乙）要检测到冲突，冲突信号还需要从主机乙（或主机甲）传播到主机甲（或主机乙），因此，主机甲（或主机乙）检测到冲突需要2个单向传播延迟，即20μs。因此，甲乙两台主机均检测到冲突时，最长需经过20μs。
    （2）若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据帧向主机乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲发送一个64字节的确认帧，主机甲收到确认帧后方可发送下一个数据帧。此时主机甲的有效数据（上层协议数据）传输速率是多少？（不考虑以太网帧的前导码）
    解：以太网最大帧长为1518B；发送1518B的数据帧所用时间(传输延迟) = 1518×8 bits/10 Mbps=1214.4μs；
    发送64B的确认帧所用时间(传输延迟) = 64×8bits/10Mbps=51.2μs；
    主机甲从发送数据帧开始到收完确认帧为止的时间记为T总，则T总=1214.4+51.2+2×10=1285.6 μs；
    在1285.6μs内发送的有效数据长度=1518B-18B=1500B=12000bits；
    因此，主机甲的有效数据传输速率=12000bits/1285.6μs ≈ 9.33Mbps。

局域网

MAC地址

image.png
image.png

ARP: 地址解析协议

image.pngimage.png

寻址: 从一个LAN路由至另一个LAN

image.png
image.png
image.png

以太网(ETHERNET)

image.png

以太网：不可靠、无连接服务

image.png

以太网CSMA/CD算法

image.png

以太网帧结构

image.png

交换机

image.png

交换表和自学习

image.png

交换机: 帧过滤/转发

image.png

自学习与转发过程举例

image.png

交换机互联

image.png

多交换机自学习举例

image.png

组织机构(Institutional)网络

image.png

交换机 vs. 路由器

image.png

虚拟局域网(VLAN)

image.png

基于端口的VLAN和跨越多交换机的VLAN

image.png

802.1Q VLAN帧格式

image.png

PPP协议

点对点数据链路控制

image.png

PPP设计需求[RFC 1557]

image.png

PPP无需支持的功能

image.png

PPP数据帧

image.png

字节填充(Byte Stuffing)

image.png

PPP数据控制协议

image.png

802.11无线局域网

image.png

IEEE 802.11体系结构

image.png

802.11：信道与AP关联

image.png

802.11AP关联：被动扫描与主动扫描

image.png

多路访问控制

image.png

CSMA/CA

image.png

冲突避免(CA): RTS-CTS交换

image.png

802.11 MAC帧和数据帧

image.png
image.png

练习

题1 ARP协议

image.png

  • 答案为ACD

    题2 以太网

    image.png

  • 答案为ACD

    题3 交换机

    image.png

  • 答案为AC

    题4 自学习

    image.png
    image.png

  • 答案为AD

    题5 PPP

    image.png

  • 答案为ABC

    题6 802.11

    image.png

  • 答案为ABCD

    题7 VLAN的作用

    解：把一个广播帧所能到达的整个范围称为二层广播域，简称广播域。显然，一个交换网络其实就是一个广播域。
    image.png
    结果：目的主机PC 10接收到应该接收的Y帧，但是同时，PC3、PC4、PC5、PC6、PC7、PC8这几个主机都接收到了这个本不该接收的Y帧。

  • 这便产生了一些问题： 1.网络安全问题（接收到本不该接收的数据帧，就可能存在安全隐患）；2.垃圾流量问题（会浪费网络的带宽资源以及计算机的处理资源）。而且，广播域越大，上面存在的安全问题和垃圾流量问题就会越严重。

  • VLAN 技术：通过在交换机上部署 VLAN 机制，可以将一个规模较大的广播域在逻辑上划分成若干个不同的、规模较小的广播域，可以有效的提高网络的安全性，减少垃圾流量的产生。
  • 通常将划分前的、规模较大的广播域称为 LAN，把划分后、规模较小的每一个广播域称为一个Virtual LAN或VLAN 。例如：把一个规模较大的广播域划分成4个规模较小的广播域时，可以说成把一个LAN划分成了4个VLAN。
  • 一个VLAN就是一个广播域，所以在同一个VLAN内部，计算机之间的通信就是二层通信。如果计算机与目的计算机处在不同的 VLAN 中，那么它们之间是无法进行二层通信的，只能进行三层通信来传递信息。
  • VLAN 作用：
    • 限制广播域：广播域被限制在一个VLAN内，节省了带宽，提高了网络处理能力。
    • 增强局域网的安全性：不同VLAN内的报文在传输时是相互隔离的，即一个VLAN内的用户不能和其它VLAN内的用户直接通信。
    • 提高了网络的健壮性：故障被限制在一个VLAN内，本VLAN内的故障不会影响其他VLAN的正常工作。
    • 灵活构建虚拟工作组：用VLAN可以划分不同的用户到不同的工作组，同一工作组的用户也不必局限于某一固定的物理范围，网络构建和维护更方便灵活。

      题8 假设结点A、B和C（通过它们的适配器）都连接到同一个广播局域网上。如果A向B发送数千个IP数据报，每个封装帧都有B的MAC地址，C的适配器会处理这些帧吗？如果会，C的适配器将会把这些帧中的IP数据报传递给C的网络层吗？如果A用MAC广播地址来发送这些帧，你的回答将会有怎样的变化呢？

      解：对于这些帧，C 的适配器会处理。但是处理手段是将它们直接丢弃，而不会传递给网络层。
      如果使用MAC 广播地址，则C 的适配器将处理帧并将数据报传递到网络层。
      当适配器接收到一个帧时，将检查该帧中的目的MAC地址是否与它自己的MAC地址匹配。
      如果匹配，该适配器提取出封装的数据报，并将该数据报沿协议栈向上传递。
      如果不匹配，该适配器丢弃该帧，而不会向上传递该网络层数据报。
      然而，有时某发送适配器的确要让局域网上所有其他适配器来接收并处理它打算发送的帧。在这种情况下，发送适配器在该帧的目的地址字段中插入一个特殊的MAC广播地址。

      题9 ARP查询为什么要在广播域中发送呢？ARP响应为什么要在一个具有特定目的的MAC地址的帧中发送呢？

      答：ARP查询报文仅含有源和目的的IP地址, 还有源MAC地址, 它并不知道目的IP地址的MAC地址, 所以要在广播帧中发送。ARP响应报文已经知道了源和目的IP地址和MAC地址四个关键信息, 完全可以构建一个具有特定目的MAC地址的帧了, 不需要发送广播帧增加链路的负担。

      题10 ARP 协议的功能是什么？假设主机 1 和主机 2 处于同一局域网（主机 1 的 IP 地址是 192.168.22.167，主机 2 的 IP 地址是 192.168.22.11），简述主机 1 使用 ARP 协议解析主机 2 的物理地址 的工作过程。

      image.png