计网-链路层和局域网

6.1 链路层概述

链路层服务

• 实现点到点的通信，使用MAC地址来进行标识
  链路层服务的原则
• 错误检测、矫正
• 共享广播信息、多址访问
• 链路层寻址（MAC）
• 局域网：以太网、VLAN

术语

• 节点：主机和路由器
• 链路：沿着通信路径连接相邻节点的通信信道
  • 有线链路
  • 无线链路
• 链路层帧：链路的PDU（Protocol Data Unit）

链路层主要功能

• 负责将数据报从一个节点传到物理上相邻的节点

链路层协议修改的是帧头帧尾的内容

6.1.1 链路层提供的服务

• 成帧
  • 将来自网络层的数据加到数据段，加上帧头和帧尾（上面的几层并没有）
  • 链路接入
• 链路接入
  • 共享介质的信道访问
    • 对于公用的信道（比如电磁波），要如何通过协议设计避免不同数据的混淆和丢失？
  • 可靠交付
    • 通常用于差错率高的信道（如无线信道）
    • 很多有线信道的链路层协议都不进行差错校验
• 差错检测以及矫正
  • 误码来源于信道上的噪声&信号衰减
  • 如果能够直接纠正误码，就不必要进行重传
  • 通常由硬件实现
• 流量控制
  • 在相邻的收发节点限制流量（限制发的速度）
• 半双工和全双工
  • 半双工：两边都能传但是不能同时传
  • 全双工：

6.1.2 链路层在何处实现

大多数情况下，链路层是在被称为网络适配器的硬件上实现的，也被称为网络接口控制器（NIC）

网卡是半自治单元，有一部分功能依靠CPU实现

发送方：封装数据报、增加差错检测位、可靠交付、流量检测
接收方：查找错误、可靠交付、流量控制；取出数据报，交给网络层

6.2 差错检测和纠正技术

差错检测模型

EDC(Error Detection and Correction bytes) 差错检测位
D是数据段，可以包括首部

6.2.1 奇偶校验

• 单比特奇偶校验：检测单个比特错误（记录数据段中的奇数位数）
• 二维奇偶校验：检测和纠正单个比特错误（记录每一行以及每一列的比特的奇数位数）

FEC(Forward Error Correction)前向纠错 接收方检测和纠正差错的能力

6.2.2 检验和方法

（参考之前提到的checksum）

6.2.3 循环冗余检测

模2计算实际上是异或运算

如何求R

6.3 多路访问链路和协议

• 点到点链路
  • PPP,HDLC
  • 以太网交换机和主机之间的点到点链路
• 广播链路
  • 传统以太网
  • 802.11无线LAN
  • HFC

多路访问协议

• 信道划分协议
• 随机接入协议
• 轮流协议
  理想的多路访问协议特性
• 1、单个节点发送数据的时候能使用全部带宽
• 2、多个节点共同发送数据时带宽能均分
• 3、去中心化
• 4、简单

6.3.1 信道划分协议

TDMA/TDM（Time Division Multiple Access）

• 循环访问信道
• 每个节点在每次循环（每个时间帧）中获得固定长度的时隙
• 没有数据发送的时隙空闲

STDM(统计时分复用)

Q:由谁统计？怎么统计？

FDMA

• 信道按照频谱被分为若干个频段
• 每个节点分配固定频段
• 频段不用的时候被闲置/浪费

CDMA

• 所有节点在整个频段上同时传输，用编码原理进行传输
• 完全无冲突
• 频段不用的时候信道被闲置和浪费

6.3.2 随机接入协议

不规避碰撞，而是重碰撞中恢复

1、时隙ALOHA

假设

动作
发送成功就在下一个时隙继续发；发送失败（有碰撞）就在每个时隙的开始以p概率决定要不要发送，即在未来的“某个时间”发送

ALOHA的p要设置为多少？
评价指标：

• 成功时隙 ： 只有一个节点发送数据的时隙
• 效率 ：大量节点发送大量帧的时候，长期运行中成功时隙的份额

时隙ALOHA中，如有N个节点，那么任意一个节点成功发送的概率是
$$
Np(1-p)^{N-1}
$$
经过演算，最大效率为
$$
\frac{1}{e} = 0.37
$$
信道使用率并不理想

2、ALOHA

有数据就发，不进行同步，检测到碰撞就立即以p的概率传送该帧

效率表达式为
$$
p(1-p)^{2N-1}
$$

最后计算出来的最大效率为
$$
\frac{1}{2e} = 0.18
$$

3、 CSMA 载波侦听多路访问

• 传输前侦听（载波侦听）
  • 空闲则发送
  • 忙则延迟传送（碰撞检测）
• 碰撞仍旧有可能发生
  • 由于传播时延，并不能保证主机侦听有效
• 类型
  • 非坚持CSMA
    • 检测到信道忙，则延迟一段时间再侦听
    • 时隙非坚持CSMA
      • 增加了时隙的划分
  • 1坚持CSMA
    • 检测到忙，则一直侦听，如果侦听到空闲则重发；发生冲突，就等待随机长的时间然后重新开始
  • P坚持CSMA
    • 侦测到忙，一直监听，侦听到空闲的话，p概率重发，（1-p）概率等待随机长的时间重新开始

4、CSMA/CD

CD:碰撞检测
一边发一边监听
短时间内碰撞被检测，如果发生碰撞，马上停止传输数据（因为传出去也没用）

强化碰撞：
检测到发生碰撞后，除了立即停止发送数据后，还要发送一段人为的干扰信号，则所有用户都停止发送数据，信道整个被清空

一些定义

• 争用期/碰撞窗口
  • 在争用期内没有检测到碰撞，则认为数据成功发送（是一个往返时延）

以太网CSMA/CD算法

5、CSMA/CD效率

#TBS

效率近似式
$$
\frac{1}{1+\frac{5d_{prop}}{d_{trans}}}
$$

6.3.3 轮流协议

类似前两种协议的这种方式

轮询协议

由主节点（master）决定哪个从节点（slave）来传输

令牌传送协议

• 控制令牌依次通过各个节点，谁拿到令牌谁发送
• 要关注令牌如何传输以及单点失效问题

6.4 交换局域网

6.4.1 链路层寻址和ARP

1、MAC地址

扁平结构
广播地址FF-FF-FF-FF-FF-FF

2、ARP协议

目标：根据IP地址获取MAC地址

ARP表
<IP,MAC,TTL>
每个主机都会独立维护，一般将TTL设置为20min

ARP请求包

ARP应答包

6.4.2 以太网

Ethernet
实现：网卡

以太网类型

• 总线式以太网
  • 对包的丢弃发生在主机
  • 
• 交换式以太网（星状结构）
  • 

组网载体发展：同轴电缆（总线式）->集线器（hub）（星状）->交换机(switch)（星状）

以太网的帧结构

前同步码用于同步发送方与接收方时钟（为了实现前面提到的时隙？）

目的地址和源地址是MAC地址/广播地址
适配器通过对地址进行分析来决定是否要丢弃该帧

类型指的是上层协议的类型（IP等）

CRC由接收方检查，用于差错校验

以太网提供的服务

• 无连接服务
  • 不需要握手
• 不可靠服务
  • 接收适配器不会发送确认帧等给发送方

以太网使用的CSMA/CD

• 没有时隙
• CSMA/CD本身对冲突的检测和处理机制
• 重传之前等待一段时间（随机访问）（指数回退）

几个定义
拥塞信号 用来确保所有传输者都能检测到碰撞而传输的信号 ；48比特长
比特时间 传输一比特所需要的时间
指数回退算法

应该说是期望的等待时间变大了？
争用期长度 10Mb/s 51.2微秒， 100Mb/s 5.12微秒
争用期内能够发送的字节为64字节
最短有效帧长 以太网规定为64字节，任何小于64个字节的帧都被认为是无效帧
特点

• 半双工通信
• 不能确定是否发生碰撞（传播时延）

传统以太网的物理层

不同的电缆编号的解读

100BASE-T:100Mbps，基带传输，物理媒介为双绞铜线(Twisted Pair)

最初的以太网是基于同轴电缆和转发器(repeater) 来实现的

基带信号是数字信号，传输距离增大会使得信号失真
为了消除波形失真，会每隔一段传输距离加一个中继器（信号放大器？）

千兆以太网

现在的以太网与最初构想的以太网有很大不同，但是以太网帧格式依旧没有改变

信号编码

曼彻斯特编码

电平升高为0，电平升高为1
电平在一个”时隙“后变为一个默认值

差分曼彻斯特编码

#TBS 什么叫“翻转？”是发生在每个”时隙“开始时间是否翻转吗

集线器（ 或转发器）互联

本质上是物理层的中继器

同样速率

没有帧缓存

6.4.3 链路层交换机

• 存储、转发以太网帧
• 查看输入帧的MAC地址，选择性转发，使用CSMA/CD
• 对于主机透明
• 即插即用，自学习 交换机不需要配置
• 支持多路同时传输，全双工

交换机维护一个交换表
(主机MAC地址，连接主机的接口，时间戳)

交换表的建立：学习

数据帧进入交换机时，交换机学习发送方所连接的接口，并建立起发送方MAC和接口的映射关系

交换机互联

仍旧是通过学习（交换机对另一个交换机也是透明的？）

网桥互联

实现不同局域网在MAC层次的互联

会进行差错检测，有差错则丢弃
不转发源和目的端口一致的帧
不修改帧的源地址

网桥的缺点

• 增加了时延
• 帧丢失现象（有缓存就有缓存溢出）
• 修改字段要耗费时间
• 广播风暴

集线器和网桥的区别

#TBS PPT

透明网桥

#TBS PPT

交换机和路由器的区别

两者都是存储转发设备，路由器属于网络层，交换机属于链路层

6.4.4 虚拟局域网

#TBS PPT