程序员社区

计算机网络春招面试复习:计算机网络之数据链路层

功能:保证数据正确的顺序,无错和完整
#1 链路层概述
数据链路层使用的信道主要有以下两种类型

  • 点对点信道
    一对一的点对点通信方式
  • 广播信道
    一对多的广播通信方式,过程比较复杂。广播信道上连接的主机很多,必须使用专用的共享信道协议来协调这些主机的数据发送
    数据链路层的简单模型
    数据链路层的简单模型( 续)
    链路层地址:LAN地址,物理地址或称为MAC地址

1 链路层的三个基本问题

  • 封装成帧(framing)
    一段数据的前后分别添加首部和尾部,构成一个帧
    首部和尾部的一个重要作用就是进行帧定界
    封帧图解
  • 透明传输
    “在数据链路层透明传送数据”,表示无论什么样的比特组合的数据都能够通过这个数据链路层
    数据看不见数据链路层有什么妨碍数据传输的东西
    数据链路层对于这些数据来说是透明的
    • 解决透明传输问题
      发送端的数据链路层在数据中出现控制字符“SOH”或“EOT”的前面插入一个转义字符“ESC”(其十六进制编码是 1B)。
      字节填充(byte stuffing)或字符填充(character stuffing)——接收端的数据链路层在将数据送往网络层之前删除插入的转义字符。
      如果转义字符也出现数据当中,那么应在转义字符前面插入一个转义字符。当接收端收到连续的两个转义字符时,就删除其中前面的一个。
  • 差错检测
    在传输过程中可能会产生比特差错:1 可能会变成0 ,而0也可能变成1
    在一段时间内,传输错误的比特占所传输比特总数的比率称为误码率 BER (Bit Error Rate)
    为了保证数据传输的可靠性,在计算机网络传输数据时,必须采用各种差错检测措施

2 点对点协议 PPP (Point-to-Point Protocol)的组成

三个组成部分

  • 一个将 IP 数据报封装到串行链路的方法。
  • 链路控制协议 LCP (Link Control Protocol)。
  • 网络控制协议 NCP (Network Control Protocol)。

3 透明传送,字节填充,零比特填充

  • 字节填充
    RFC1662规定的填充方法:
    将信息字段中出现的每一个 0x7E 字节转变成为 2 字节序列(0x7D, 0x5E)。
    若信息字段中出现一个 0x7D 的字节, 则将其转变成为 2 字节序列(0x7D, 0x5D)。
    若信息字段中出现 ASCII 码的控制字符(即数值小于 0x20 的字符),则在该字符前面要加入一个 0x7D 字节,同时将该字符的编码加以改变。
  • 零比特填充
    • PPP 协议用在 SONET/SDH 链路时,是使用同步传输(一连串的比特连续传送)。这时 PPP 协议采用零比特填充方法来实现透明传输。
    • 标志字段0x7E(二进制01111110)
    • 在发送端,只要发现有 5 个连续 1,则立即填入一个 0。接收端对帧中的比特流进行扫描。每当发现 5 个连续1时,就把这 5 个连续 1 后的一个 0 删除。

5 CRC差错检测,求冗余码

基于循环冗余检验(CRC)的差错检测技术

  • 在发送端,先把数据划分为组。假定每组 k 个比特。
  • 假设待传送的一组数据 M = 101001(现在 k = 6)。我们在 M 的后面再添加供差错检测用的 n 位冗余码一起发送。

冗余码的计算

  • 用二进制的模 2 运算进行 2n 乘 M 的运算,这相当于在 M 后面添加 n 个 0。
  • 得到的 (k + n) 位的数除以双方事先选定好的长度为 (n + 1) 位的除数 P,得出商是 Q 而余数是 R,余数 R 比除数 P 少1 位,即 R 是 n 位。
    冗余码的计算举例

4 交换局域网

4.1 链路层寻址和ARP

4.2 以太网

4.2.1 概述

“统治地位”的有线LAN技术

  • 造价低廉(NIC不足¥100.00)
  • 应用最广泛的LAN技术
  • 比令牌局域网和ATM等,简单、便宜
  • 满足网络速率需求:10 Mbps – 10 Gbps
    Metcalfe的以太网草图

4.2.2 以太网:物理拓扑

总线(bus): 上世纪90年代中期前流行

  • 所有结点在同一冲突域(collision domain) (可能彼此冲突)

星型(star): 目前主流网络拓扑

  • 中心交换机(switch)
  • 每个结点一个单独冲突域(结点间彼此不冲突)
    总线(bus): 同轴电缆&&星型(star)

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

无连接(connectionless): 发送帧的网卡与接收帧的网卡间没有“握手”过程

不可靠(unreliable): 接收网卡不向发送网卡进行确认

  • 差错帧直接丢弃,丢弃帧中的数据恢复依靠高层协议 (e.g., TCP),否则,发生数据丢失

以太网的MAC协议: 采用二进制指数退避算法的CSMA/CD

4.2.4 CSMA/CD(Carrier Sense Multiple Access with Collision Detection),协议的工作过程,最短帧长与争用期的关系(重点)

概念

载波监听多点接入/碰撞检测
“多点接入”:许多计算机以多点接入的方式连接在一根总线上
“载波监听”:每一个站在发送数据之前先要检测一下总线上是否有其他计算机在发送数据,如果有,则暂时不要发送数据,以免发生碰撞
“碰撞检测”:计算机边发送数据边检测信道上的信号电压大小

原理

载波监听
碰撞检测
随机退避

4.2.4.3 工作过程(从与广播信道相连的网卡角度)

  1. NIC从网络层接收数据报,创建数据帧,并放入帧适配器缓存中
  2. 监听信道:
  • NIC监听到信道闲,则开始发送帧
  • NIC监听到信道忙,则一直等待到信道闲,然后发送帧

发送过程中,NIC监视来自其他使用该广播信道的适配器的信号能量的存在(即边发送边检测)
3. 没有检测到其他结点的数据发送,NIC发送完整个帧,发送成功
4. 如果NIC检测到其他结点传输数据,则中止发送,并发送堵塞信号(jam signal)
5. 中止发送后,NIC进入二进制指数退避:

  • 第m次连续冲突后:
    •取n = Min(m, 10)
    •NIC 从{0,1,2, …, 2n-1}中随机选择一个数K
    •NIC等待K·512比特的传输延迟时间,再返回第2步

  • 连续冲突次数越多,平均等待时间越长。

  • 争用期

    • 最先发送数据帧的站,在发送数据帧后至多经过时间 2 (两倍的端到端时延)就可知道发送的数据帧是否遭受了碰撞。
    • 以太网的端到端往返时延 2 称为争用期,或碰撞窗口。
    • 经过争用期这段时间还没有检测到碰撞,才能肯定这次发送不会发生碰撞
    • 长度
      以太网争用期的时间取为51.2微秒
      对于 10 Mb/s 以太网,在争用期内可发送512 bit,即 64 字节。因此,也可以说争用期是512比特时间。
      以太网在发送数据时,若前 64 字节没有发生冲突,则后续的数据就不会发生冲突
  • 最短有效帧长

    • 如果发生冲突,就一定是在发送的前 64 字节之内
    • 以太网规定了最短有效帧长为 64 字节
    • 若要发送的数据非常少,则必须加入一些填充字节,使帧长不小于64字节
    • 凡长度小于 64 字节的帧都是由于冲突而异常中止的无效帧

4.2.5 以太网帧结构

发送端网卡将IP数据报(或其他网络层协议分组)封装到以太网帧中:
计算机网络春招面试复习:计算机网络之数据链路层插图6

各个字段意义

  • 前导码(Preamble)(8B):

    • 7个字节的10101010,第8字节为10101011
    • 用于发送端与接收端的时钟同步
  • 目的MAC地址、源MAC地址(各6B):

    • 如果网卡的MAC地址与收到的帧的目的MAC地址匹配,或者帧的目的MAC地址为广播地址(FF-FF-FF-FF-FF-FF),则网卡接收该帧,并将其封装的网络层分组交给相应的网络层协议
    • 否则,网卡丢弃(不接收)该帧
  • 类型(Type)(2B): 指示帧中封装的是哪种高层协议的分组 (如,IP数据报、Novell IPX数据报、AppleTalk数据报等)

  • 数据(Data)(46-1500B): 指上层协议载荷

    • R=10Mbps,RTTmax=512μs,Lmin / R = RTTmax
    • Lmin=512bits=64B,Datamin=Lmin-18=46B
  • CRC(4B): 循环冗余校验码

    • 丢弃差错帧

4.2.6 802.3以太网标准: 链路与物理层

  • 许多不同的以太网标准
    • 相同的MAC协议和帧格式
    • 不同速率: 2 Mbps, 10 Mbps, 100 Mbps, 1Gbps, 10G bps
    • 不同物理介质: 光纤, 线缆
      计算机网络春招面试复习:计算机网络之数据链路层插图7

5 交换机(switch)

5.1 以太网交换机(switch)

  • 链路层设备
    • 存储-转发以太网帧
    • 检验到达帧的目的MAC地址,选择性(selectively) 向一个或多个输出链路转发帧
    • 利用CSMA/CD访问链路,发送帧
  • 透明(transparent)
    • 主机感知不到交换机的存在
    • 即插即用(plug-and-play)
    • 自学习(self-learning)
    • 交换机无需配置

5.2 交换机: 多端口间同时传输

  • 主机利用独享(dedicated)链路直接连接交换机
  • 交换机缓存帧
  • 交换机在每段链路上利用CSMA/CD收发帧,但无冲突,且可以全双工
    • 每段链路一个独立的冲突域
  • 交换(switching): A-A’与B-B’的传输可以同时进行,没有冲突
    6个接口交换机 (1,2,3,4,5,6)

5.3 交换机转发表:交换表

Q: 交换机怎么知道A’可以通过接口4到达,而B’可以通过接口5到达?

  • A: 每个交换机有一个交换表(switch table), 每个入口(entry):
    • (主机的MAC地址, 到达主机的接口, 时间戳)
    • 看起来很像路由表!
  • Q: 交换表入口信息如何创建和维护的那?
    • 类似于路由协议?

5.4 交换机: 自学习

交换机通过自学习,获知到达主机的接口信息

  • 当收到帧时,交换机“学习”到发送帧的主机(通过帧的源MAC地址),位于收到该帧的接口所连接的LAN网段
  • 将发送主机MAC地址/接口信息记录到交换表中
    计算机网络春招面试复习:计算机网络之数据链路层插图9

5.5 交换机: 帧过滤/转发

当交换机收到帧:

  1. 记录帧的源MAC地址与输入链路接口
  2. 利用目的MAC地址检索交换表
  3. if 在交换表中检索到与目的MAC地址匹配的入口(entry)
    then {
    if 目的主机位于收到帧的网段
    then 丢弃帧
    else 将帧转发到该入口指向的接口
    }
    else 泛洪(flood) /* 向除收到该帧的接口之外的所有接口转发 */

6 集线器、转发器、网桥、以太网交换机的异同

集线器的特点

  • 使用集线器的以太网在逻辑上仍是一个总线网,各工作站使用的还是 CSMA/CD 协议,并共享逻辑上的总线。
  • 集线器有许多接口,因此很像一个多接口的转发器。
  • 工作在物理层,每个借口仅仅简单地转发比特。
  • 采用专门的芯片,进行自适应串音回波抵消。

网桥

  • 在数据链路层扩展局域网是使用网桥。
  • 它根据 MAC 帧的目的地址对收到的帧进行转发和过滤。
  • 网桥具有过滤帧的功能。当网桥收到一个帧时,并不是向所有的接口转发此帧,而是先检查此帧的目的 MAC 地址,然后再确定将该帧转发到哪一个接口,或者丢弃(即过滤)。
  • 多个局域网通过一种工作在数据链路层的设备连接起来,这个设备叫网桥。网桥用于连接多个局域网,它根据 MAC 帧的目的地址对收到的帧进行转发。网桥具有过滤帧的功能。当网桥收到一个帧时,并不是向所有的接口转发此帧,而是先检查此帧的目的 MAC 地址,然后再确定将该帧转发到哪一个接口。网桥的优点:过滤通信量、扩大屋里范围、提高可靠性、互连不同物理层、不同MAC层和不同速率的局域网。目前使用得最多的网桥是透明网桥(transparent bridge)。

集线器在转发帧时,不对传输媒体进行检测。
网桥在转发帧之前必须执行 CSMA/CD 算法。

多接口网桥-以太网交换机

  • 通常都有十几个接口。因此,以太网交换机实质上就是一个多接口的网桥,可见交换机工作在数据链路层。
  • 每个接口都直接与主机相连,并且一般都工作在全双工方式。
  • 能同时连通许多对的接口,使每一对相互通信的主机都能像独占通信媒体那样,进行无碰撞地传输数据。
  • 由于使用了专用的交换结构芯片,其交换速率就较高。

7 网桥转发表的建立过程

  • 若从 A 发出的帧从接口 x 进入了某网桥,那么从这个接口出发沿相反方向一定可把一个帧传送到 A。
  • 网桥每收到一个帧,就记下其源地址和进入网桥的接口,作为转发表中的一个项目。
  • 在建立转发表时是把帧首部中的源地址写在“地址”这一栏的下面。
  • 在转发帧时,则是根据收到的帧首部中的目的地址来转发的。这时就把在“地址”栏下面已经记下的源地址当作目的地址,而把记下的进入接口当作转发接口

8 了解网络适配器的主要功能及其工作在哪一层

网络接口板又称为通信适配器(adapter)或网络接口卡NIC(Network Interface Card),或“网卡”

  • 进行串行/并行转换;
  • 对数据进行缓存;
  • 在计算机的操作系统安装设备驱动程序;
  • 实现以太网协议
赞(0) 打赏
未经允许不得转载:IDEA激活码 » 计算机网络春招面试复习:计算机网络之数据链路层

一个分享Java & Python知识的社区