计算机网络知识点及例题总结（五）数据链路层与局域网
本博客已整理成pdf文件，文件资源链接：哈尔滨工业大学-计算机网络期末
知识点部分
1.数据链路层服务
术语：
①结点：主机和路由器
②链路：连接相邻结点的通信信道eg:有线链路，无线链路和局域网
③帧：链路层数据分组，封装网络层数据报。
数据链路层负责通过一条链路从一个结点向另一个物理链路直接相连的相邻结点传送数据。
数据链路层服务：
①组帧：封装数据报构成数据帧，加首部和尾部，帧同步
②链路接入：如果是共享介质，需要解决信道接入；帧首部中的MAC地址用于标识帧的源和目的
③相邻结点间可靠交付：无线链路常采用，因其误码率高
④流量控制
⑤差错检测
⑥差错纠正
⑦全双工和半双工通信控制：全双工指链路两端结点同时双向传输、半双工指链路两端结点交替双向传输。
2.差错检验与纠正
汉明距离ds：编码集中两个等长字符串对应位置不同字符的个数(取最小不同个数为汉明距离)。
检错码：ds=r+1，则差错编码可以检测r位的差错；
纠错码：ds=2r+1，则差错编码可以纠正r位的差错，将一个无效的码字纠正为距离最近的码字。
奇偶校验码：差错检测最简单的方式就是用单个奇偶校验位，使1的总数总是偶数； 如果出现偶数个比特的差错无法检测出；检测能力50%，检测效率高；
二维奇偶校验：检测奇数位差错、部分偶数位差错；纠正同一行/列的奇数位错
Internet校验和(Checksum)：发送端:将“数据”(校验内容)划分为16位的二进制“整数”序列；求和(sum)：补码求和(最高位进位的“1”，返回最低位继续加）；校验和(Checksum)：sum的反码；放入分组(UDP、TCP、IP)的校验和字段；接收端：与发送端相同算法计算，计算得到的"checksum"：为16位全0（sum为16位全1）无错；否则有错。
循环冗余检测编码CRC：
检错能力更强大的差错编码，广泛应用于实际网络(以太网，802.11 WiFi，ATM)
将数据比特D视为一个二进制数；选择一个r+1位的比特模式G，称为生成多项式
目标：选择r位的CRC比特R，满足（1）<D,R>刚好可以被G模2整除（2）接收端检错：利用G除<D,R>，余式全0，无错；否则，有错！
（3）可以检测所有突发长度
3.MAC协议
单一共享广播信道，两个或者两个以上结点同时传输可能会发生冲突，则需要协议来控制。
多路访问控制协议MAC：采用分布式算法决策结点何时可以传输数据，必须基于信道本身；
理想MAC协议：速率为R bps的广播的信道，期望一个结点使用速率为R，M个结点使用速率为R/M，完全分散控制(无需特定结点协调，无需时钟同步、时隙同步)，简单。
MAC分类：①信道划分MAC协议(多路复用技术)：TDMA，CDMA，FDMA，WDMA
②随机访问MAC协议：信道不划分，允许冲突；采用冲突恢复机制。
典型的随机访问MAC协议：时隙ALOHA，ALOHA，CSMA，CSMA/CD，CSMA/CA(应用于802.11);
时隙ALOHA：结点只能在时隙开始时刻发送帧。优点①单个结点活动，可以连续以信道全部速率传输数据②高度分散化需同步时隙③简单；缺点①易产生冲突，浪费时隙②空闲时隙③时钟同步④无法及时检测冲突。效率：最大为1/e=0.37。即在有多个结点时信道被成功利用的时间仅占37%。
ALOHA：有新的帧生成直接发送。优点①更简单②无需同步；缺点①更容易产生冲突。效率：1/2e=0.18比时隙ALOHA更差。
CSMA载波监听多路访问协议：发送之前，监听信道(通过载波判断)：分类①1-坚持CSMA：监听到信道忙，一直以p=1监听信道，只要空就发送帧；②非-坚持CSMA：监听到信道忙则随机等待一段时间，再监听信道，不忙则发送数据；③P-坚持CSMA：以概率P坚持监听信道，概率P随机等待一段时间。冲突仍然可能发生，信号传播延迟，可能造成信道资源浪费。
CSMA/CD带有冲突检测载波监听多路访问协议(应用于以太网)：一旦发现信道冲突，则中止传输，节省信道资源浪费；边发送数据边监听，不发不听。效率：趋近于1，远优于ALOHA，并且简单，分散。
③轮转访问MAC协议(应用于蓝牙，)：结点轮流使用信道。综合前两者优点。
轮询，令牌传递。缺点①轮询开销/令牌开销②等待延迟③单点故障
4.ARP协议（地址解析协议，重点：MAC地址与IP地址转换，详见自测题）
MAC地址(LAN地址，物理地址，以太网地址)：作用用于局域网内在数据链路层标识一个帧从哪个接口发出，到达哪个物理相连的其它接口。48位MAC地址。局域网内每块网卡都有唯一MAC地址。由IEEE同意管理与分配。
ARP协议：同一局域网内，A向B发送数据报，若B的MAC地址不在A的ARP表中，则A广播查询，此时目的MAC地址：FF-FF-FF-FF-FF-FF,B接受ARP查询，IP地址匹配成功，向A应答MAC地址；若获取超时则刷新，再次获取。
内网到内网：源和目的IP地址不变；
内网到互联网：源IP地址改变；
互联网到内网：目的MAC地址改变；
以上过程源和目的MAC地址均按转发情况改变。
5.以太网
以太网是具有统治地位的有线局域网技术：造价低，应用广泛，简单便宜，满足网络速率需求。
以太网物理拓扑：总线，星型（目前主流）。以太网无连接不可靠服务。二进制退避指数算法(超过连续16次冲突，不再尝试，向上层报错)计算随机等待时间，1-坚持CSMA。
以太网帧结构：
前导码：8B（计算帧长度一般不包括前导码）
目的，源MAC地址：各6B
类型：2B
数据Data：46-1500B
CRC：4B。
许多不同的以太网标准：相同的MAC协议和帧格式。不同速率和不变通物理介质。
6.交换机
典型的链路层设备，存储-转发以太网帧，利用CSMA/CD访问链路，透明(主机感知不到交换机存在)，具有自学习功能，自学自用。全双工。
交换表来记录自学习，学习源MAC地址和接口。
7.VLAN虚拟局域网
支持VLAN划分的交换机，可以在一个物理LAN架构上配置定义多个VLAN。
实现流量隔离，基于端口划分；动态成员：端口可以动态分配给不同的VLAN；VLAN间转发。
中继端口：在跨越多个物理交换机定义的VLAN承载帧，802.1q协议标记。
8.PPP协议
点对点链路协议，一个发送端和一个接收端，一条链路。
常见协议：HDLC，PPP。
PPP协议：支持以下功能：组帧将网络层数据报封装到数据链路层帧中；实现比特透明传输；差错检测；连接活性检测；网络层地址协商：动态地址分配。
不支持：差错纠正/恢复；流量控制；乱序交付；多点链路。
PPP数据帧：