回顾TCP/IP参考模型，明确链路层和物理层在整个模型中的地位，简要提出链路层要解决的问题是单段链路的数据传输，物理层解决的是数字信号与电气信号之间的相互转换。
链路层概述
节点：主机和路由器(包括网桥和交换机)
链路：沿着通信路径连接相邻节点的通信信道
有线链路
无线链路
局域网
帧：链路层协议交换的数据单元。封装网络层数据报
数据链路层的职责：将分组通过一个链路，从一个节点传输到临近的另一个节点。
分组传输可以经过不同的链路使用不同的链路层协议实现:
例如，以太网，帧中继，最802.11无线LAN
每个链路协议提供不同的服务
例如，可以在链路上提供或不提供可靠的传输
传输类比
从成都到九寨沟的旅途
打的：成都某地到成都机场
飞机：成都机场到黄龙机场
大巴：黄龙机场到风景区
旅客 = 数据包
运输段 = 通信链路
运输模式 = 链路层协议
旅行社 = 路由算法
链路层服务：
成帧（Framing）：
把网络层数据报加头和尾（唯一一个加尾部的层），封装成帧
帧头中包括指明目的和源的“物理地址”（不同于IP地址）
链路接入（Link access）：
媒体访问控制（Medium Access Control，MAC）协议
共享媒体的多路访问
可靠交付（Reliable delivery）
在出错率很低的链路上很少用 (光纤，部分双绞线)--链路层不一定要具有全部的这些功能服务。
无线链路：高出错率
流量控制（Flow control）：
节点具有有限容量的帧缓冲能力
在邻接的发送节点和接收节点间的同步调节
差错检测（Error detection）:
差错由信号衰减和噪声引起
接收者检测错误：如果发现差错，发送者重传帧或丢帧
纠错（Error correction）：
接收者检测和纠正错误，不需发送者重传
半双工和全双工（Half-duplex and Full-duplex）
半双工，一个节点不能同时传输和接收
全双工，节点可以同时传输和接收
差错检测和纠错技术
奇偶校验
奇校验:用户数据和校验信息中1的个数为奇数个时，奇偶位为1
偶校验:用户数据和校验信息中1的个数为偶数个时，奇偶位为1
加单个奇偶位
二维奇偶校验:
检测和纠正单个位错误,检测的两个位错误
差错检测-循环冗余编码CRC
多项式编码，该编码将比特串看作是0和1的一个多项式
101001 => x5+x3+1（幂次是后面的位数，x0=1）
r+1位模式G，称为生成多项式
CRC原理：在K位信息码（目标发送数据）后再拼接R位校验码，使整个编码长度为N位，因此这种编码也叫（N,K）码。
通俗的说，就是在需要发送的信息后面附加一个数（即校验码），生成一个新的发送数据发送给接收端。这个数据要求能够使生成的新数据被一个特定的数整除。这里的整除需要引入模 2除法的概念。
那么，CRC校验的具体做法就是
（1）选定一个标准除数（K位二进制数据串）
（2）在要发送的数据（m位）后面加上K-1位0，然后将这个新数（M+K-1位）以模2除法的方式除以上面这个标准除数，所得到的余数也就是该数据的CRC校验码（注：余数必须比除数少且只少一位，不够就补0，补前面）
（3）将这个校验码附在原m位数据后面，构成新的M+K-1位数据，发送给接收端。
（4）接收端将接收到的数据除以标准除数，如果余数为0则认为数据正确。
注意：CRC校验中有两个关键点：
一是要预先确定一个发送端和接收端都用来作为除数的二进制比特串（或多项式）标准数；
二是把原始帧与上面选定的除进行二进制除法运算，计算出FCS校验码。
前者可以随机选择，也可按国际上通行的标准选择，但最高位和最低位必须均为“1”
模2运算的加法运算与减法运算是相同的，等价于按位异或（XOR），比如
1011 XOR 0101 = 1110
1001 XOR 1101 = 0100
1011 - 0101 = 1110
1001 - 1101 = 0100
G=1001，所以知道r+1=4，r=3，所以D后面+了三个0，除出来R=011
接收方则用R加在D后面，看能不能整除。
假设:
通信双方协商的生成多项式为:
G=X4+X2+X+1
发送放要发送的数据为:
D=11001100
问题:
CRC校验信息需要多少位?
发送方最终发送的数据是多少位?
发送方最终发送的数据内容是什么?
如果传输过程中出现1位错误能否检测?出现6位错误能否检测?为什么
G=10110，CRC校验码的长度始终比G短一位，所以校验信息需要4位。
发送方最终发送的数据是D+R=8+4=12位。
数据内容，110011001010
出现一位比特错误能检验。出现六位不能。
CRC能检测r比特或更少的错误位
因为1位错误会导致余数发生变化，而CRC校验可以捕捉到这种变化。
奇偶校验能力最弱，CRC校验能力最强
奇偶校验通常用于简单的串口通信
校验和通常应用于网络层及其之上的层次，要求简单快速的软件实现方式
CRC通常应用于链路层，一般由适配器硬件实现
多址访问协议Multiple Access Protocol, MAC（媒体访问控制）
两种链路类型
点对点链路
PPP（用于拨号访问）或HDLC
在以太网交换机和主机间的点到点链路
广播链路
传统以太网
802.11无线局域网
引入链路层的又一大功能服务－－媒体访问控制。在广播或共享信道链路上称之为多路访问。
需要意识到链路有点对点和广播或共享信道链路2大类型。
广播链路共享广播信道会出现冲突，某节点同时接收两个或多个节点信号时，发生冲突
某个时刻只有一个节点发送数据时，才可成功发送信息
多址访问协议：决定各节点如何共享信道，共享信道既要负责数据传输，又要负责控制信息的传输
分类
分为3大类:
第一类：信道划分
把信道划分为小“片” (时隙，频分，码分)，给节点分配专用的小“片”
第二类：随机访问（动态）
不划分信道，允许冲突，能从冲突中“恢复”
ALOHA, S-ALOHA, CSMA, CSMA/CD
载波侦听：有线网络容易实现，无线网络困难
CSMA/CD用于以太网,CSMA/CA用于无线网络
第三类：轮转
通过集中调整共享访问避免冲突
中心节点轮询，令牌传递
随机访问
节点有数据包发送，以信道满数据率R传送，节点间没有协调者
2个或更多的发送节点 -> “冲突collision”----允许冲突
随机访问MAC协议要求:
能够检测冲突，能够从冲突中恢复 (例如：通过延时重传)
随机访问MAC协议实例：
ALOHA
时隙ALOHA
CSMA, CSMA/CD, CSMA/CA
纯ALOHA（非时隙）
非时隙Aloha: 简单，不需同步，帧一到达，就立即传输
冲突概率增加:
在t0发送的帧和在 [t0-1,t0+1]的发送的其它帧冲突
概率问题，不冲突的时候就成功发送，那么成功发送的概率：
时隙ALOHA
假设
所有帧大小相同
时间被划分为相同大小的时隙，一个时隙等于传送一帧的时间
节点只能在一个时隙的开始才能传送
如果一个时隙有多个节点同时传送，所有节点都能检测到冲突
实现
当节点要发送新帧，它等到下一时隙开始时传送
没有冲突，节点可以在下一时隙发送新帧
如果有冲突，节点在随后的时隙以概率p重传该帧，直到成功为止
C：collision，E：empty，S：success
可以看出来，成功传输的只有三次
优点
单个活跃节点可以持续以满速率传送帧
具有高分散性: 只需节点的时隙同步
简单
缺点
冲突，浪费时隙
空闲时隙
节点只有在传输数据包时才能检测到冲突
效率 ：当有很多节点，每个节点有很多帧要发送时，成功时隙所占的百分比
最佳: 信道有 37%的有效传输（也没有太显著提升。）
CSMA（Carrier Sense Multiple Access) 载波侦听多路访问
CSMA:
传送前侦听:
如果信道闲：传送整个帧
如果信道忙：延迟传送
冲突还是可能发生:传播延迟可能导致两个节点没侦听到其它节点的传送（两个节点同时或者相距极短的时间
如图，t0时刻B发出，A C与B距离近，t1时检测到B发出了，但D距离B远，在t1时没有检测到发出，所以自己发了，造成冲突。
距离和传播延时决定冲突概率，因为这将决定侦听消息的传播速率
）
CSMA/CD（冲突检测）
CSMA/CD:
在一个短时间内检测冲突
放弃传送，减少带宽浪费
冲突检测:
有线LANs中容易：测量信号强度，比较传送和接收信号
无线LANs中困难: 传输中接收信号比传送信号很微弱
基本思想：
当一个节点要发送数据时，首先监听信道，看是否有载波
如果信道空闲，则发送数据
如果信道忙，则继续对信道进行监听。一旦发现空闲，便立即发送
如果在发送过程中检测到碰撞，则停止自己的正常发送，转而发送一短暂的干扰信号jam，强化冲突，使其它站点都能知道出现了冲突
发送了干扰信号后，退避随机时间，重新尝试发送
轮转MAC
分割信道MAC协议
高负载效率高：信道共享公平高效
低负载效率低：延迟访问，如果只有一个活跃节点只分配了 1/N的带宽
随机访问MAC协议
低负载效率高：单个节点可以获得整个信道
高负载：冲突开销大
“轮转”协议
两者的折中!
1. 轮询:
主节点轮流 “邀请”从属节点传送数据
缺陷：
轮询开销
延迟
主节点失效，整个网络失效
2. 令牌传递：
控制令牌从一个节点顺序传到下一个节点
令牌消息
缺陷：
令牌开销
延时
令牌失效
链路层编址：
32位IP地址，网络层地址
用于把分组源网络送到目的IP网络，IP协议初始化前配置
48位MAC(或LAN 或物理或Ethernet)地址: 链路层地址
用于把数据帧从一个接口传送到另一个接口(同一网络中)
48位（2进制，16进制一位相当于4位2进制，所以就变成12位）MAC地址固化在适配器的ROM
在局域网中的每一个适配器都有一个唯一的LAN地址（源地址和目的地址）
MAC地址由IEEE统一分配，厂商购买一块MAC地址空间 (要保证唯一性)
比较:
(a) MAC地址: 类比于身份证号码
(b) IP地址: 类比于邮政地址
MAC地址具有扁平结构 => 可移动，但不会变（身份证号移到哪都无所谓）
MAC地址是一种全局性的平面地址，能从一个LAN移动到另一个LAN
IP地址具有层次结构 => 移动会改变，依赖节点所依附的IP网络
ARP: 地址解析协议
协议原理：主机动态缓存IP/MAC地址映射。
局域网上的每个IP节点(Host, Router)都有ARP表
ARP表: IP/MAC地址映射，格式如下：
< IP address; MAC address; TTL>
TTL (Time To Live): 映射地址的失效时间 (典型为20分钟)
假设：A想发送分组给B，A知道B的IP地址，B的MAC地址不在A的ARP表中
（1）A广播包含B的IP地址的ARP查询包
目的MAC地址= FF-FF-FF-FF-FF-FF
在局域网上的所有机器都能收到ARP查询
（2）B收到ARP包，回给A一个带有B的MAC地址的包
包单播unicast发送给A的MAC地址
（3）A缓存IP-to-MAC地址对在A的ARP表中，直到信息过期 (timeout)
数据链路层的目的地址和源地址都是MAC地址。
相同子网的ARP
不同子网的ARP
发送站A将广播对“默认网关”即路由器左端口192.168.0.1的ARP请求，获得其MAC地址后将把发送给B的数据先发送到路由器左端口
路由器收到数据并路由后，将在右端口广播B的ARP请求，获得B的MAC地址后进行数据转发。
ARP（Address Resolution Protocol）地址解析协议，是根据IP地址获取物理地址的一个TCP/IP协议。主机发送信息时将包含目标IP地址的ARP请求广播到局域网络上的所有主机，并接收返回消息，以此确定目标的物理地址；收到返回消息后将该IP地址和物理地址存入本机ARP缓存中并保留一定时间（TTL），下次请求时直接查询ARP缓存以节约资源。
DHCP（动态主机配置协议）是一个局域网的网络协议。指的是由服务器控制一段IP地址范围，客户机登录服务器时就可以自动获得服务器分配的IP地址和子网掩码。DHCP通常被应用在大型的局域网络环境中，主要作用是集中的管理、分配IP地址，使网络环境中的主机动态的获得IP地址、Gateway地址、DNS服务器地址等信息，并能够提升地址的使用率。
DHCP协议采用客户端/服务器模型，主机地址的动态分配任务由网络主机驱动。
DHCP具有以下功能：
（1）保证任何IP地址在同一时刻只能由一台DHCP客户机所使用。
（2）DHCP可以给用户分配永久固定的IP地址。
（3）DHCP可以同用其他方法获得IP地址的主机共存（如手工配置IP地址的主机）。
DHCP工作原理
DHCP协议采用UDP作为传输协议，主机发送请求消息到DHCP服务器的67号端口，DHCP服务器回应应答消息给主机的68号端口。详细的交互过程如下图。
设备使用DHCP获取IP地址后，可以通过ARP找到局域网中其他设备的MAC地址，进行实际的数据传输。（联系）
以太网
以太网是目前最流行的LAN技术
以太网的拓扑结构的衍变（总线型），今天以集线器和交换机为中心的星型拓扑！
不握手、不发送确认帧，CRC校验发现错误，则丢弃帧
丢弃帧导致，传递到网络层的数据报流可能有间隙
如果传输层使用TCP协议，间隙会被填好
如果传输层使用UDP协议，应用能看见间隙
以太网物理层传输机制
有很多以太网的物理层标准（与传输介质相对应）：
10BASE-T
10BASE2
10BASE5
100BASE-T
1000BASE-T
1000BASE-LX
1000BASE-SX等
例：Ethernet技术100BASE-T
速率：100 Mbps
被称为 “快速ethernet”
T表示双绞线
各节点都连接到集线器上 “星型拓扑结构”
在节点和适配器间最大距离为100米
以太网物理层编码：曼彻斯特编码
利用一个时钟周期中间位置的电平跳变来表示“0”和“1”。
中间跳变是由低电平跳变到高电平表示“1”
中间跳变是由高电平跳变到低电平表示“0”
注：
(1)在时钟周期边界处可以任意跳变而不影响编码含义
(2)采用曼切斯特编码，调制速率应为传输速率的2倍
以太网链路层控制技术
媒体访问控制（MAC）
MAC帧中使用的地址标识即MAC地址，又称为硬件地址或物理地址。
MAC地址包括：
目的地址
源地址
MAC地址长度为48位，它被固化在网卡的ROM中
非时隙
采用了载波侦听机制
采用了冲突检测机制
在试图重传之前，适配器会等待一个随机时间,即随机访问
指数回退
拥塞信号：48比特，确保所有传送者知道冲突发生
比特时间（发送一比特所需要的时间）： 对于10 Mbps Ethernet 为0.1微秒，当K=1023，等待时间大约50毫秒
指数回退：
目标：适配器依据当前负载情况重传，重负载时等待时间变长（指数变长）
第一次冲突： 在{0,1}中选k值；延迟Kx512比特时间传送
第二次冲突：在{0,1,2,3}中选k值…
10次以后，在 {0,1,2,3,4,…,1023}中选k值。0-2^10-1。
以太网交换机
交换机工作在链路层
存储和转发以太网帧
检查帧头,并根据目的MAC地址有选择的转发帧
交换机直接连接的计算机不需要使用CSMA/CD协议，实现点到点的数据通信；但是，当MAC帧被转发到某一共享网段时,需要使用CSMA/CD访问该网段
透明性
主机不关心交换机的存在
即插即用,自学习
交换机不需要被配置
物理上和逻辑上都是星型结构
交换：A-to-A’和 B-to-B’同时工作，不冲突
交换机具有大量接口
所有主机可以直接使用交换机连接成网络:全交换网络
实现全双工模式运行：带宽变为原来的两倍
交换机转发（MAC转发表）
路由是特指路由器在网络层根据分组的目的IP地址匹配IP路由表表项来选择转发IP接口。路由表是一个目的网络地址与下一跳路由器IP接口地址（对应该路由器的IP接口地址）的映射表。
交换机转发是在链路层根据帧的目的MAC地址匹配交换表表项选择转发接口。交换表是一个交换机接口号与接口下属MAC地址的映射表。
交换机内部保存一个源地址表又称为交换表
交换表的表项:
(MAC地址, 接口, 时间)，过期的表项将被删除 (TTL 可以是60分钟)
当接收一数据帧时,交换机“学习”发送者的位置，即数据进入交换机的LAN网段与接口之间的对应关系、在交换表中记录发送者/位置对应关系
上述机制称之为交换机的“自学习”，获取每个帧的源MAC地址，建立（ MAC地址, 接口）交换表。
自学习
如果转发表中没有目的的地址，就只能广播。
假设A发送数据帧到B会有什么结果呢
交换机接收来自A的数据帧
注意在交换表中A在交换机的接口1上,B也在交换机的接口1上
数据帧将被交换机丢弃
假如AB同时发消息给交换机
交换机会接收到来自端口1的冲突信息
冲突信息将被交换机丢弃
当交换机接收一数据帧时:
根据接收帧的目的MAC地址检索交换表
if 目的MAC地址的表项被发现then{
if 如果目的地址在接收帧的网段中 then 丢弃该帧
else 转发该帧到指定的接口
}
else 广播（向所有(除接收帧所在的接口外)其它接口转发）
交换机冲突隔离
交换机将一个子网划分成若干个LAN网段
交换机过滤数据包:
同一LAN网段的数据帧传输不被转发到其它LAN网段
每个LAN网段变成一个独立的冲突域
交换机不能划分网络层的IP子网，但可以在链路层隔离逻辑网段和隔离冲突域。
交换机某端口连接共享网段时,该端口需要使用CSMA/CD访问该网段
交换机的交换方式
存储转发：具有差错检测功能，转发时延较大，适用于出错率高的链路。
快速分组又称直通交换：不具有差错检测功能，转发时延较小，适用于时延要求高，出错率低的链路。
三层交换机
三层交换是相对于传统的交换概念而提出的
传统的交换技术是在OSI网络参考模型中的第二层（即数据链路层）进行操作的，通常称做“二层交换机”。
三层交换技术能够在网络模型中的第三层（网络层）实现数据包的高速转发。
简单地说，三层交换技术就是二层交换技术+三层转发技术，三层交换机就是“二层交换机+基于硬件的路由器”
集线器互联各物理网段的特点—汇集冲突域。
路由器交换机比较
集线器、路由器、交换机
集线器会汇集冲突
交换机可以直通交换也可以存储转发。
PPP：点到点协议
一个发送者，一个接收者，一条链路: 较广播链路简单
没有媒体访问控制
不需MAC寻址
是广域网的链路接入技术，例如：拨号链路
链路层的点到点链路控制比广播链路控制简单得多！
典型的点到点链路控制协议有PPP和HDLC。
PPP设计需求
错误恢复，流量控制，数据排序都交给上层管理!
无媒体访问控制、无MAC寻址
在网络层数据通信之前，数据链路对等端必须配置PPP链路 (最大帧长,认证)
LCP链路控制协议
学习/配置网络层信息(NCP,Network Control Protocol)，IPCP网络控制协议
字节填充
数据透明性”需要： 数据域可以包含标志模式 <01111110>（帧头帧尾2个连续7E字节与数据字段中连续两个7E字节数据的混淆。）
问题: 如何知道<01111110>是数据还是标志?
发送方:
在每个< 01111110>数据之前增加一个填充字节< 01111101>
在每个< 01111101>数据之前也增加一个 填充字节< 01111101>（为了防止将原本就有的去掉）
接受方:
遇到< 01111101> 就去掉，接收后面的数据
单个01111110: 标志字节
只填充数据的。
零比特填充法
在发送端，只要发现有 5 个连续 1，则立即填入一个 0。接收端对帧中的比特流进行扫描。每当发现 5 个连续1时，就把这 5 个连续 1 后的一个 0 删除
链路虚拟化ATM和MPLS
资源的虚拟化：虚拟机
抽像的层次:不关心更低层细节，只抽像的处理更低层
不同网络的区别:地址规范、分组格式、错误恢复、路由
IP层的IP协议和路由协议为低层异构的局域网和链路提供统一的寻址和路由。
链路虚拟化概念
两个层次地址: 互联网和本地网
新的层次(IP)使所有的网络在互联网层同构,屏蔽了下层网络的差异（如下）
低层的本地网络技术
电缆
卫星
56K 电话调制解调器
今天的: ATM, MPLS
…上述技术在互联网层是 “不可见的”. 对于IP来说就象是一个链路层技术!
ATM概念异步传输
ATM:异步传输模式，Asynchronous Transfer Mode
融合了分组交换和电路交换的优点
采用面向连接的虚电路分组交换机制
分组具有固定长度（称为信元），便于实现电路交换
采用异步传输模式进行交换转发
异步传输：发送方可以在任何时刻发送这些比特组，而接收方从不知道它们会在什么时候到达。
异步传输: 你传输吧，我去做我的事了，传输完了告诉我一声
同步传输: 你现在传输，我要亲眼看你传输完成，才去做别的事 。
ATM网络参考模型
AAL：在ATM网络的边缘，数据分割和重组，类似Internet的传输层
ATM 层: 类似于Internet的网络层，信元交换,路由
物理层：实现信元发送和接收
ATM适配层（AAL）:
ATM适配层(AAL): “适配”上层(IP或ATM应用)到下面的ATM层
AAL出现在端系统中，不在交换机中
不同的ATM服务有不同版本的AAL层:
AAL1: 恒定比特率(CBR)服务和电路模拟
AAL2: 可变比特率(VBR)服务，例如： MPEG视频
AAL5: 数据传输，例如：IP数据报
ATM 层: 虚电路
虚电路传输: 信元从源到目的在虚电路上传输
发送数据传输前需要建立一条虚电路
每个信元需要包含一个虚电路标识VC（不是目的标识）
源到目的路径上的每一次交换，都要维护传递连接的状态
为了得到类似电路的性能，链路、交换资源（带宽和缓冲）可能被分配给虚电路
永久VCs (PVCs)长期存在的连接
典型: IP路由器之间的永久路由
交换VCs (SVC):
为每个请求动态设置的
ATM VC的优点:
能提供QoS性能保证 (带宽，时延，时延抖动)
ATM VC缺点:
支持数据报效率低下
在源和目的之间建立的永久虚电路的数量不成比例 (N个入口和N个出口需要N*N条连接)
交换虚电路引入请求建立虚电路的延时，对于短连接开销大
ATM 层: ATM信元
5字节ATM信元头部
48字节负载
Why?: 小负载->缩短数字音频段创建信元时的延迟
ATM 网络提供的服务
CBR (Constant Bit Rate)：提供固定速率的服务。
VBR (Variable Bit Rate)：提供可变速率的服务，尽量满足用户的平均速率需求。
ABR (Available Bite Rate)：保证最小传输频宽的可变速率服务。
UBR (Unspecified Bit Rate)：无任何保障的服务。
其中AAL1支持CBR或UBR，AAL2支持VBR或UBR，AAL5支持所有类型。
C-》V-〉A
