多路访问控制（MAC）协议

两类链路：

点对点链路：拨号接入的PPP，以太网交换机与主机间的点对点链路
广播链路（共享介质）：早期的总线以太网，HFC的上行链路，802.11无限局域网

单一共享广播信道

两个或两个以上节点同时传输：干扰，产生冲突，导致接受失败

多路访问控制协议（multiple access control protocol）

采用分布式算法决定节点如何共享信道，即决策节点何时可以传输数据
必须基于信道本身，通信信道共享协调信息

MAC协议分类

信道划分 (channel partitioning) MAC协议
- 多路复用技术
- TDMA，FDMA，CDMA，WDMA等
随机访问 (random access) MAC协议
- 信道不划分，允许冲突
- 采用冲突“恢复”机制
轮转 (taking turns) MAC协议
- 节点轮流使用信道（保证节点在使用信道时不冲突，同时在使用的时候用的是信道的全部带宽）

信道划分MAC协议

TDMA: time division multiple access

“周期性”接入信道
每个站点在每个周期占用固定长度的时隙（这里的长度是指分组传输时间）
未用的时隙空闲（idle）
例如，6-slot的LAN，1、3、4传输分组，2、5、6空闲

FDMA: frequency division multiple access

信道频谱划分为若干频带(frequency bands)
每个站点分配一个固定的频带
没有传输数据的频带空闲
例如，6站点LAN，1、3、4频带传输数据，2、5、6频带空闲

随机访问MAC协议

当节点要发送分组时，利用信道全部数据速率R发送分组，没有事先的节点间协调。

会发生冲突。

随机访问MAC协议需要定义：如何检测冲突、如何从冲突中恢复（通过延迟重传）

典型的随机访问MAC协议：

时隙(sloted)ALOHA
ALOHA
CSMA, CSMA/CD, CSMA/CA

时隙ALOHA协议

假定：

所有帧大小相同
时间被划分为等长的时隙（每个时隙可以传输1个帧）
节点只能在时隙开始时刻发送帧
节点间时钟同步
如果2个及以上的节点在同一时隙发送帧，则检测到冲突

运行：

当节点有新的帧时，在下一个时隙(slot)发送
如果无冲突：该节点可以在下一个时隙继续发送新的帧
如果冲突，该节点在下一个时隙以概率p重传该帧，直至成功

优点：

单个节点活动时，可以连续以信道全部速率传输数据
高度分散化：只需同步时隙
简单

缺点：

冲突，浪费时隙
时钟同步
空闲时隙
节点也许能以远小于分组传输的时间检测到冲突

非时隙ALOHA

更加简单，无需同步

当有新的帧生成时，立即发送

$P(给定节点成功发送帧) = P(该节点发送) * P(无其他节点在[t0-1,t0]内发送帧) * P(无其他节点在[t0,t0+1]内发送帧) = p * (1-p)^{N-1} * (1-p)^{N-1} = p * (1-p)^{2N-2} = 1/2e = 0.18$

因此比时隙ALOHA协议更差。

CSMA协议

载波监听多路访问协议CSMA(carrier sense multiple access)

发送帧之前，监听信道（载波）：

信道空闲：发送完整帧
信道忙：推迟发送
- 1-坚持CSMA
- 非坚持CSMA
- P-坚持CSMA
冲突可能仍然发生：存在信号传播延迟

CSMA/CD协议

CSMA/CD: CSMA with Collision Detection

短时间内可以检测到冲突
冲突后传输中止，减少信道浪费

冲突检测：

有线局域网易于实现：测量信号强度，比较发射信号与接收信号
无线局域网很难实现：接收信号强度淹没在本地发射信号强度下

网络带宽：R bps

数据帧最小长度：$L_min$ (bits)

信号传播速度：V(m/s)

“边发边听，不发不听”

主机A、B之间的距离是$d_{max}$，A向B发送数据帧，快到达B时，B又向A发送了一个数据帧，两者在靠近B的地方相遇，于是发生了冲突。A发送的数据帧到达B时，B检测到了冲突，但此时B发送的数据帧还未到达A，因此A还没有检测出冲突。最后，两者都检测到冲突时，用了$2d_{max}/V$的时间。

满足：$L/R >= 2d_{max}/V$

那么：

$L_{min}/R >= 2d_{max}/V$

$L_{min}/R = RTT_{max}$

$t_{prop} = LAN中2个节点间的最大传播延迟$ $t_{trans} = 最长帧传输延迟$ $效率 = 1/(1+5t_{prop}/t_{trans})$

$t_{prop}$趋近于0或$t_{trans}$趋近于∞时，效率趋近于1.

远优于ALOHA，并且简单、分散。

ARP协议

MAC地址

32位IP地址：

接口的网络层地址
用于标识网络层（第3层）分组，支持分组转发

MAC地址（或称LAN地址，物理地址，以太网地址）

作用：用于局域网内标识一个帧从哪个接口发出，到达哪个物理相连的其他接口
48位MAC地址（用于大部分LANs），固化在网卡的ROM中，有时也可以软件设置
将48bits分为6个字节，16进制表示，e.g.: 1A-2F-BB-76-09-AD

局域网中的每块网卡都有一个唯一的MAC地址。

MAC地址由IEEE统一管理与分配。

网卡生产商购买MAC地址空间（前24比特），后24比特生产商依次分配。

类比：

MAC地址：身份证号
IP地址：邮政地址
MAC地址是“平面”地址，可”携带“，可以从一个LAN移到另一个LAN
IP地址是层次地址，不可“携带”，IP地址依赖于节点连接到哪个子网

ARP：地址解析协议

在同一个LAN内，如何在已知目的接口的IP地址前提下确定其MAC地址？

ARP表：LAN中每个IP节点（主机、路由器）维护一个表

存储某些LAN节点的IP/MAC地址映射关系。如：
存活时间TTL(time to live)：经过这个时间后，该映射关系会被遗弃（典型时间是20min）

ARP协议：同一局域网内

A想要向同一局域网中的B发送数据报，但B的MAC地址不在A的ARP表中
A广播ARP查询分组，其中包含B的IP地址。LAN中所有节点都会接收到ARP查询。
B也接收到了，IP地址匹配成功，B向A应答B的MAC地址。利用单播帧向A发送应答。
A在自己的ARP表中缓存B的IP-MAC地址对，直至超时。超时后，再次刷新。
ARP是“即插即用”协议，节点自主创建ARP表，无需干预。

数据链路层