第二章、链路层和局域网

2.1介绍和链路层的服务

术语

datagram数据报
communication link链路
communication link链路
routing algorithm路由算法

链路层服务

Framing, link access: 帧的封装和链路的访问
- 将数据包封装成帧，加上头部和尾部
  encapsulate datagram into frame, adding header, trailer
- 信道访问
  channel access if shared medium
- 链路层寻址（帧的头部使用的mac地址，用于识别源和目的）
  “MAC” addresses used in frame headers to identify source, dest
Reliable delivery between adjacent nodes
相邻节点间的可靠传输
- 至少要保证不错，很少用在低位错误链路（光纤fiber、双绞线twisted pair）
- 第三章学习如何实现
Flow Control: 流量控制
- 相邻发送节点和接受节点之间的步调
Error Detection: 错误检测
- 由信号衰减、噪声引起的误差
- 接收方检测是否存在（presence）错误
- 信号发送方用于检查是否重新传输或丢帧
Error Correction: 错误修正
- 接收方识别并纠正错误
Half-duplex and full-duplex全双工和半双工
- 使用半双工，链路两端节点不可以同时传输

链路层实现位置

网络边缘
in each and every host
适配器（网络接口卡网卡）和网卡
adaptor chip

-
连接主机的系统总线
硬件、软件、固件组合

2.2校验和纠正

Error detection and correction

EDC：Error Detection and Correction bits检错纠错码（为后添加的冗余数据）

不是百分之百可靠
~EDC长度越长检测效果越好

检错流程（可能发生比特位发生翻转）

1.Parity checking(奇偶位校验)

Single Bit Parity(奇偶校验)
- 最不实用但简单
- 缺点：不能改错，有误报情况，只能测出一半的错误（奇位错）
Two Dimensional Bit Parity:二维奇偶校验
- 优：可定位错误
- 缺：有误报

2.Internet checksum(校验和)

只能检测不能纠正，只在❗传输层使用（因为实现麻烦，需要cpu辅助）
目标：检测在传输段中的错误:
detect “errors” in transmitted segment
发送端sender
- 将段的内容视为十六位整数
  treat segment contents as sequence of 16-bit integers
- 校验和：段内容的反码和
  addition (1’s complement sum) of segment 进位contents（最高位循环加到最后一位，不丢数据）
- 把校验和放到udp校验和字段中
  - UDP(User Datagram Protocol)用户数据报协议
接收端receiver
- 计算接受端的校验和
- 检查计算的校验和是否等于校验和字段值（）
  - 如果不为0，则有错误
  - 为0，则正确（发送端计算为反码）

3.Checksumming: Cyclic Redundancy Check

（校验和：循环冗余校验）（CRC❗链路层使用）

D：要发送的数据，看成的二进制数
G：r+1位模式（生成器），一个接收方知道的数
最后R加到数据末尾
检测用到异或，计算方便
够用就行,G位数越多检测能力越强
每个CRC标准能够检测不多于r+1位的猝发错误和任意的奇数个比特错误

2.3 多路访问协议（解决共享信道的问题）

Multiple access Protocols（MAC协议）

Multiple Access Links and Protocols多个访问链接和协议（两类连接）

点对点point-to-point
- 家用或路由器
- 以太网
广播broadcast
（shared wire or medium共享电路和介质

分类法a taxonomy

Channel Partitioning信道划分
- 特点
  - divide channel into smaller “pieces” (time slots, frequency, code)
  - allocate piece to node for exclusive专属 use
- TDMA：time division multiple access
  - 每个站在每轮中获得固定长度的插槽（长度= pkt传输时间）
- 利用率低 FDMA
  - 因为没有使用的信道都是空闲的
Random Access随机访问
- channel not divided, allow collisions
- “recover” from collisions冲突
- 处理的问题
  - 如何检测碰撞
    - “碰撞检测”就是计算机边发送数据边检测信道上的信号电压大小。当几个站同时在总线上发送数据时，总线上的信号电压摆动值将会增大（互相叠加）。当一个站检测到的信号电压摆动值超过一定的门限值时，就认为总线上至少有两个站同时在发送数据，表明产生了碰撞。所谓“碰撞”就是发生了冲突。因此“碰撞检测”也称为“冲突检测”。结果就是两个帧都变得无用
  - 如何从冲突中恢复（例如，通过延迟转播）
- 分类
  - slotted ALOHA（有时隙的）
    - 假设，所有帧都等长，时间等分时隙（slot），一个时隙恰好发送一个数据帧，只能从开始的地方发送，节点间同步，两个节点冲突，所有节点都可以检测到
    - 操作：当节点获得新帧时，它会在下一个插槽中传输
      如果没有冲突，节点可以在下一个槽中发送新帧
      如果发生冲突，节点在每个后续插槽中用 prob. p 重新传输帧直到成功
    - 优点（pros）
      - 单个主动节点可以全速率连续传输通道独占带宽
      - 高度去中心化：去中心化节点中只有插槽需要同步
      - 简单
    - 缺点cons
      - 碰撞，浪费slot
      - 空闲slot
      - 节点可能能够在传输数据包的不到一段时间内检测到冲突
      - 时钟同步困难
    - 基于时间同步，n无限大时，可达到37%传输效率
  - Pure (unslotted) ALOHA无时隙的（始终不用同步
    - 效率不高，但简单，最高0.18
  - CSMA (Carrier Sense Multiple Access)载波监听
    - 传输前就监听
      - 如果通道检测到空闲：传输整个帧
      - 如果信道检测到繁忙，就推迟传输
    - 冲突问题：由于传播时延导致没有及时监听到
      - 如果冲突，整个数据包也传输，却不能用，所以浪费时间，且半径越小越容易检测冲突
      - 距离越远，带宽越低（传的慢）出现传播时延造成的冲突的可能性越大
  - CSMA/CD (Collision Detection)载波监听冲突检测多路复用used in Ethernet
    - 在短时间内检测到冲突
    - 碰撞传输中止（aborted），减少通道浪费
    - 碰撞检测
      - 易于在有线LAN中：测量信号强度，比较发射和接收的信号
      - 无线局域网中的困难：接收机在传输时关闭
  - CSMA/CA used in 802.11
“Taking turns”轮转
- Nodes take turns, but nodes with more to send can take longer turns
- 通道分区MAC协议（channel partitioning MAC protocols）：在高负载下高效、公平地共享通道
  - 低负载时效率低下：通道访问延迟，即使只有1个主动节点，也分配1/N带宽！
- 随机访问 MAC 协议
  - 低负载时高效：单节点可充分利用通道
  - 高负载：碰撞开销
- 方式：
  - 轮询polling
    - 主节点”邀请”从属节点依次传输master node “invites” slave nodes to transmit in turn
    - 通常与哑设备（“dumb” slave devices）一起使用
    - 缺点
      - polling overhead 轮循开销
      - latency延迟
      - single point of failure (master）一旦master主节点故障，所有都出问题
    - 优点：利用random优势
  - token（令牌） passing依次传递
    - 控制令牌按顺序（sequentially）从一个节点传递到下一个节点。
    - 令牌消息
    - 缺点
      - 令牌开销token overhead
      - 延迟latency
      - 单点故障（令牌token)任何一个故障，都不能运转
- Bluetooth, FDDI使用

Cable access network有线接入网络？？？

DOCSIS：电缆数据服务接口规范data over cable service interface spec
上行、下行频率通道上 FDM
TDM 上行：已分配某些插槽，某些插槽存在争用
- 下行 MAP 帧：分配上游插槽
- 请求在选定插槽中传输的上游插槽（和数据）传输随机访问（二进制退避）

LAN technologies局域网技术？？？

services, error detection/correction, multiple access

争用期

最先发送数据帧的站，在发送数据帧后至多经过时间 2τ（两倍的端到端往返时延）就可知道发送的数据帧是否遭受了碰撞。
以太网的端到端往返时延 2τ 称为争用期，或碰撞窗口。
经过争用期这段时间还没有检测到碰撞，才能肯定这次发送不会发生碰撞。
以太网争用期：
- 以太网取 51.2 μs 为争用期的长度。
- 对于 10 Mb/s 以太网，在争用期内可发送512 bit，即 64 字节。
- 以太网在发送数据时，若前 64 字节没有发生冲突，则后续的数据就不会发生冲突。

最短有效帧长

以太网规定了最短有效帧长为 64 字节，凡长度小于 64 字节的帧都是由于冲突而异常中止的无效帧。

帧间最小间隔

帧间最小间隔为 9.6 μs，相当于 96 bit 的发送时间。
一个站在检测到总线开始空闲后，还要等待 9.6μs 才能再次发送数据。
这样做是为了使刚刚收到数据帧的站的接收缓存来得及清理，做好接收下一帧的准备。

2.4 Addressing寻址

MAC地址(or LAN or physical or Ethernet) 身份证号一样独一无二

功能
- 在”本地”使用，将帧从一个接口获取到另一个物理连接的接口（同一网络，在IP寻址意义上）（同一局域网）
48 位（12位16进制） MAC 地址（对于大多数 LAN）刻录在 NIC ROM 中（写在主机的配置文件中），有时软件也可设置
每一个链路层端口都有一个mac地址
由 IEEE 管理的 MAC 地址分配
制造商购买部分MAC地址空间（以确保唯一性）
MAC 平面地址 ➜ 便携性
- 可以将局域网卡从一个局域网移动到另一个局域网
IP 分层地址不可移植
- 取决于节点附加到的 IP 子网

ARP协议（Address Resolution Protocol）地址解析协议

LAN 上的每个 IP 节点（主机、路由器）都有 ARP 表
ARP 表：某些 LAN 节点的 IP/MAC 地址映射
- < IP 地址;MAC 地址;TTL>
  - TTL（Time To Live生存时间）：地址映射将被遗忘的时间（通常为 20 分钟）
同一个局域网下查询
- A 希望将数据报发送到 B，而 B 的 MAC 地址不在 A 的 ARP 表中。
- A （广播broadcasts） ARP 查询数据包（其中包含A的mac地址），其中包含 B 的 IP 地址
  - Dest MAC 地址 = FF-FF-FF-FF-FF-FF-FF
  - LAN 上的所有计算机都接收 ARP 查询
- B 接收 ARP 数据包，使用其（B 的） MAC 地址回复 A（ARP应答包）
  - 发送到 A 的 MAC 地址的帧（单播）
- 在其 ARP 表中缓存（保存）IP 到 MAC 地址对，直到信息变旧（超时times out ），过期后需要重新问
  - 软状态soft state：除非刷新，否则超时（消失）的信息
- ARP 是”即插即用（plug-and-play）”的：
  - 节点创建其 ARP 表，无需网络管理员干预（intervention）

寻址Addressing：路由到另一个 LAN（跨局域）（A通过R和B发数据报）

问题：
- 专注于寻址 – 在 IP（数据报）和 MAC 层（帧）
- A 知道 B 的 IP 地址
- A 怎么知道第一跳路由器 R 的 IP 地址（由路由协议完成
- A怎么知道 R 的 MAC 地址（同一个局域网可以问
步骤
- A 使用 IP 源 A（目标 B）创建 IP 数据报
- A 创建链路层帧，将 R 的 MAC 地址作为目标地址，帧包含 A 到 B IP 数据报
- R 使用 IP 源 A（目标 B）转发数据报
- R 创建链路层帧，其中 B 的 MAC 地址为 dest，帧包含 A 到 B 的 IP 数据报

2.5 Ethernet以太网

“占主导地位dominant”的有线局域网技术：

便宜$20 100Mbs！
首次广泛使用局域网技术
比令牌 LAN 和 ATM 更简单、更便宜
跟上速度赛速：10 Mbps – 10 Gbps

物理拓扑：physical topology

bus: popular through mid 90s
- all nodes in same collision domain (can collide with each other)
star: prevails today现在占上风
- active switch in center
- each “spoke分支” runs a (separate) Ethernet protocol (nodes do not collide冲突 with each other)

以太网帧的结构v1

7 个字节，模式为10101010，后跟一个字节，最终模式：10101011
用于同步接收机、发送器时钟速率
Addresses: 6 byte source, destination MAC addresses
- 如果适配器接收具有匹配目标地址或广播地址（例如ARP数据包）的帧，则它将帧中的数据传递到网络层协议
- 否则，适配器将丢弃帧
Type: 表示（indicate）更高层的协议（主要是 IP，但可能支持其他协议，如 Novell IPX 和 AppleTalk）
CRC: 在接收器处检查，如果检测到错误，则浅丢一下帧（以太网中32位，4个字节）

以太网 V2 的 MAC 帧格式（数据字段的正式名称是 MAC 客户数据字段，最小长度 64 字节-18 字节的首部和尾部 = 数据字段的最小长度）

无效的 MAC 帧

帧的长度不是整数个字节；
用收到的帧检验序列 FCS 查出有差错；
数据字段的长度不在 46 ~ 1500 字节之间。
有效的 MAC 帧长度为 64 ~ 1518 字节之间。
对于检查出的无效 MAC 帧就简单地丢弃。以太网不负责重传丢弃的帧（以太网不提供有效传输）。

Unreliable, connectionless service

无连接：发送和接收 NIC 之间无需握手
不可靠：接收 NIC 不会向发送 NIC 发送确认或 nack
- 仅当初始发送方使用更高层 rdt（例如 TCP）时，才会恢复丢弃帧中的数据，否则丢弃的数据将丢失
以太网的 MAC 协议：无插槽 CSMA/CD，带二进制退避

Ethernet uses CSMA/CD

carrier sense载波监听
collision detection冲突检测
- 处理采用指数退避Exponential Backoff：
  - 目标：使重新传输尝试适应估计的当前负载
    - 负载重：随机等待会更长
  - 第一次冲突：从 {0，1} 中选择 K;延迟为K·512位传输次数
  - 第二次冲突后：从 {0，1，2，3} 中选择 K…
  - 在十次冲突后，从 {0，1，2，3，4,…,1023} 中选择 K
  - 当重传达 16 次仍不能成功时即丢弃该帧，并向高层报告。
在尝试重新传输之前，适配器会等待随机时间，即随机访问
无时隙
算法实现
- 1. 网卡（NIC）从网络层接收数据报，创建帧
- 1. 如果 NIC 检测到通道空闲，则开始帧传输。如果 NIC 检测到信道繁忙，则等待通道空闲（idle），然后进行传输。
- 1. 如果网卡传输整个帧而没检测到另一个传输，则网卡是用帧完成的！
- 1. 如果 NIC 在传输时检测到另一个传输，则中止并发送卡纸信号
- 1. 中止后，NIC 进入二进制（指数）退避：
  - 在第 m 次冲突后，NIC 从 {0，1，2， …， 2m-1} 中随机选择 K。网卡等待 K·512 位时间，返回步骤 2
  - 更长的回退间隔，更多的碰撞
效率
- Tprop = max prop between 2 nodes in LAN最远两个节点间的传播时延
- Ttrans = time to transmit max-size frame最大帧的发送时延
- Efficiency goes to 1 as tprop goes to 0
- Goes to 1 as ttrans goes to infinity传播时延无限大时效率高？
- Much better than ALOHA, but still decentralized分散, simple, and cheap
- 效率公式显示，帧越多效率越高，带宽足够低效率高，但这是不可能的，就像慢慢走，但是一直在走着
使用 CSMA/CD 协议的以太网不能进行全双工通信而只能进行双向交替通信（半双工通信）。

节点连接到集线器（hub）：”星形拓扑”;节点和集线器之间的最大距离为 100 m

2.6 Interconnections & VLAN

Interconnections

中继器repeater/relay: （物理层）对信号整形放大
Manchester encoding（物理层）改变编码方式，采用高低电平变化表示01，允许发送节点和接收节点中的时钟彼此同步，无需在节点间使用集中的全局时钟
转换器Translater/transformer：信号转换的中继器（两边类型不一样）
- 如光电转换, 10base-2转换到10BaseT
集线器hub: （物理层）（多端口中继器）
- 集线器是中继器的一种形式，也称为多端口中继器。
- 不检测冲突（由端节点检测）
- 无缓存
- 可能会让网络很混乱
- 5-4-3-2-1 Rule
  - 5：允许5个网段，每网段最大长度100米。
  - 4：在同一信道上允许连接4个中继器或集线器。
  - 3：在其中的三个网段上可以增加节点。
  - 2：在另外两个网段上，除做中继器链路外，不能接任何节点。
  - 1：上述将组建一个大型的冲突域，最大站点数1024，网络直径达2500米。
交换机switch: （链路层）前身为网桥
- 交换机是网桥的一种形式，也称为多端口网桥（网桥连接的为两个网络）
- takes an active role链路层，可以存储转发，能选择性转发
  - 存储，转发以太网帧
  - 检查传入帧的 MAC 地址，在要在分段上转发帧时有选择地将帧转发到一个或多个传出链路，使用 CSMA/CD 访问分段
- 透明transparent
  - 主机不知道交换机的存在
- 即插即用，自学plug-and-play, self-learning
  - 交换机不需要配置configured
- 多个同时传输multiple simultaneous transmissions时：每个传入链路上使用以太网协议，但没有冲突;全双工，每个链路都是其自身的冲突域（隔离冲突）
- Switch forwarding table交换机转发表：一个交换机一个
  - （主机的 MAC 地址、到达主机的接口、时间戳）看起来像一个路由表！
- frame filtering/forwarding帧过滤/转发，当帧到达交换机时
  - 1. record incoming link, MAC address of sending host

index switch table using MAC destination address
if entry found for destination then {
if destination on segment from which frame arrived then drop frame
else forward frame on interface indicated by entry
}
else flood /* forward on all interfaces except arriving interface */
- Switches vs. routers
  - 两者都是存储和转发：
    - 路由器：网络层设备（检查网络层标头）
    - 交换机：链路层设备（检查链路层标头）
  - 两者都有转发表：
    - 路由器：使用路由算法的计算表，IP 地址
    - 交换机：使用 flooding, learning, MAC addresses学习转发

VLANs: motivation虚拟局域网

Port-based VLAN基于端口的虚拟局域网
- 流量隔离traffic isolationn
- 动态成员资格：可以在 VLAN 之间动态分配端口
- VLAN 之间的转发：通过路由完成（就像使用单独的交换机一样）
  - 在实践中，供应商销售组合交换机和路由器
VLANS spanning multiple switches跨多个交换机的 VLAN
- 中继端口trunk port：在通过多个物理交换机定义的 VLAN 之间传输帧
  - 交换机之间在 VLAN 中转发的帧不能是普通(vanilla)的 802.1 帧（必须携带 VLAN ID 信息info）
  - 802.1q 协议为中继端口之间转发的帧添加/删除了其他标头字段

2.7 PPP

Point to Point Data Link Control点对点数据链路控制

一个发送方，一个接收方，一个链路：比广播链路更容易：
- 无媒体访问控制
- 无需显式 MAC 寻址
流行的点对点DLC协议：
- PPP（点对点协议）
- HDLC：高级数据链路控制

数据链路层传送的是帧（在数据链路层，规程=协议）

数据链路层的三个基本问题

(1) 封装成帧
- 封装成帧(framing)就是在一段数据的前后分别添加首部和尾部，然后就构成了一个帧。确定帧的界限
- 首部和尾部的一个重要作用就是进行❗帧定界。
(2) 透明传输
- 发送端的数据链路层在数据中出现控制字符“SOH” ”(其十六进制编码是 01)或“EOT” (其十六进制编码是 04)的前面插入一个转义字符“ESC”(其十六进制编码是 1B)。
- 字节填充(byte stuffing)或字符填充(character stuffing)——接收端的数据链路层在将数据送往网络层之前删除插入的转义字符。
- 如果转义字符也出现数据当中，那么应在转义字符前面插入一个转义字符。当接收端收到连续的两个转义字符时，就删除其中前面的一个。
(3) 差错控制
- 在传输过程中可能会产生比特差错：1 可能会变成 0 而 0 也可能变成 1。
- 在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率 BER (Bit Error Rate)。
  - 误码率与信噪比有很大的关系。
- 为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施。

PPP协议的三个组成部分

一个将 IP 数据报封装到串行链路的方法。
- 数据包成帧：将网络层数据报封装在数据链路帧中
  - 同时承载任何网络层协议（而不仅仅是IP）的网络层数据
  - 向上解复用（demultiplex upwards
    ）的能力
- 位透明度：必须在数据字段中携带任何位模式
- 错误检测（无校正）
  error detection (no correction)
- 连接活性connection liveness：检测，信号链路故障到网络层
- 网络层地址协商：端点可以学习/配置彼此的网络地址
链路控制协议 LCP (Link Control Protocol)。
网络控制协议 NCP (Network Control Protocol)。
PPP不要求
- no error correction/recovery不错误检测
- no flow control没有流控制
- out of order delivery OK 乱序也可以传输
- no need to support multipoint links (e.g., polling)无需支持多点链接（如，轮询）

PPP Data Frame

Flag: delimiter (framing)分隔符（框架）
Address: does nothing (only one option)不执行任何操作（只有一个选项）
Control: 什么都不做;未来可能的多个控制领域
Protocol:上层协议，将帧传送到哪个帧（例如，PPP-LCP，IPCP等）
info: 正在承载的上层数据
check: cyclic redundancy check for error detection用于错误检测的循环冗余检查

PPP协议的工作状态

当用户拨号接入 ISP 时，路由器的调制解调器对拨号做出确认，并建立一条物理连接。
PC 机向路由器发送一系列的 LCP 分组（封装成多个 PPP 帧）。
这些分组及其响应选择一些 PPP 参数，和进行网络层配置，NCP 给新接入的 PC机分配一个临时的 IP 地址，使 PC 机成为因特网上的一个主机。
通信完毕时，NCP 释放网络层连接，收回原来分配出去的 IP 地址。接着，LCP 释放数据链路层连接。最后释放的是物理层的连接。

因为知识点很多，这部分的笔记最开始是用思维导图记的，但是图片都不能导出，xmind格式的到百度网盘自行下载或者联系我可以发叭，笔记效果如下（也不是那么好看，建议还是看PPT或者自己整理效率较高，我的笔记整理效果稍稍欠缺）：