《计算机网络》复习笔记_链路层

二、链路层
(i)基本服务：
1.分帧

2.链路访问控制
(1)点到点链路
(2)广播链路
MAC:Multiple Access Control
为了避免多个节点共享信道导致collision,需要一个纯分布式的算法来决定哪一个节点可以传输。

3.可靠传输
(1)防止出错
(2)防止溢出

Method 1: Stop and Wait

Method 2: Sliding Window(主流流控制方法)

Example:

4.检错和纠错
(1)一维奇偶校验
(2)二位奇偶校验
采用二维奇偶校验不仅可以检测到出现单个比特差错的事实，而且还可以利用存在奇偶校验差错的比特并纠正它。
(3)CRC(循环冗余校验码)

注意：求余数时不是相减，而是上下异或

(ii)LAN
(1)令牌环（token ring）

(iii)Ethernet
分帧（从比特流转为帧）：
(1)count byte
会出错，出错后之后的帧全都作废

(2)哨兵
为了避免哨兵出现在帧数据里造成干扰，我们需要使用bit stuffing来修改帧内的部分数据

(iv)Medium Acess Control(MAC)
(1)信道切分


（2）轮询
主从式，令牌环
(3)random access
①ALOHA:

Example:

②slotted ALOHA:

Example:

③CSMA(载波侦听多路访问)

(1)非持续CSMA

(2)1持续CSMA

(3)p持续CSMA

④CSMA-CD（CD=Collision Detection）IEEE 802.3

最小冲突间隔时间：

二进制指数退递：

⑤MAC performance
(1)Point to Point with no ACK

(2)Ring

(3)slotted ALOHA


(4)pure ALOHA

(5)CSMA/CD

(v)MAC ADDRESS
ARP协议(Adress resolution protocal)

(vi)网桥和二层交换机
(1)avoid broadcast storm->avoid loop
方法：构造spanning tree(perlman 算法)



Example:

确保鲁棒性：
根节点会周期性地发送消息确认自己的地位。其他节点如果在一段时间后没有收到，则重启算法

(2)地址学习
网桥的X端口接收到一个来自地址Addr的帧，则桥会记住Addr在端口X的一侧

桥的forwarding算法：

(3)其它设备
Hub:可以看做所有连接的设备共享一根总线

Layer 2 switch:

(vii)无线移动网络
IEEE 802.11（WIFI协议）
术语：

两种扫描AP的方式：
A.被动
AP周期性发送信标帧，设备监听选择

B.主动
设备发送一个Probe探索帧，AP响应，终端选择并应答

隐藏终端问题：

解决办法：四帧交换

Example:
一开始A向B发送RTS，B收到后向A,C都发送一个CTS，这样A知道可以发送数据了，也让C知道有人在向B发送数据。于是，C保持静默。B接受完之后，向A,C都发送ACK，这样A知道自己的数据被收到了，C知道B已经接受完数据可以接受自己的数据。于是C被唤醒。