链路层:链路,接入网与局域网

链路层:链路,接入网与局域网

链路层概述

• 链路层: 在两台主机之间, 数据报跨越一系列通信链路传输, 一些是有线链路, 一些是无线链路, 从源主机起始, 通过一系列分组交换机(交换机和路由器), 在目的主机结束.
• 结点(node): 运行链路层协议的任何设备均成为结点, 包括路由器, 交换机, 主机, wifi接入点
• 链路(link): 沿通信路径连接相邻结点的通信信道称为链路.
• 在通过特定链路时, 传输结点将数据报封装在链路层帧中.

链路层提供的服务:

• 成帧(framing): 网络层的数据包经链路传送之前, 几乎所有链路层协议都要将其用链路层帧封装起来
• 链路接入: 媒体访问控制(Medium Access Control, MAC)协议规定了帧在链路上传输的规则
• 可靠交付
• 差错检测和纠正

链路层的实现

• 链路层的主体部分是在网络适配器中实现的, 网络适配器有时也称网络接口卡(NIC)

差错检测和纠正

• 差错检测和纠正比特(Error-Detection and Correction, EDC): 在发送节点, 为保护比特不出错, 使用EDC来增强数据D.
  

奇偶校验

• 一维校验: 假设发送信息D中有d个比特, 在校验方案中, 发送方只需包含一个附加比特, 使得d+1个比特中1的总数是偶数
• 二维校验: D中的d个比特被划分为i行j列, 对每列和每行计算奇偶值, 产生的i+j+1奇偶比特构成了链路层帧的差错检测比特.
• 前向纠错: 接收方检测和纠正差错的能力被称为前向纠错(Forward Error Corrention, FEC)

检验和方法

• d比特数据被作为一个k比特整数的序列处理, 一个简单检验和方法就是将k比特整数加起来, 并用得到的和作为差错检测比特.因特网检验和(Internet checksum)就是基于这种方法. 即数据的字节作为16比特的整数对待并求和.

循环冗余检测(Cyclic Redundancy Check, CRC)

• CRC编码也成为多项式编码(polynomial code), 该编码能够将要发送的比特串看作为系数是0和1的一个多项式.
• 生成多项式(generator, G): 考虑d比特的数据D, 发送方和接收方首先协商一个r+1比特模式, 称为生成多项式(generator), 表示为G. 要求G的最高有效位的比特为1.
• CRC编码思想: 对于数据段D, 发送方要选择r个附加比特R, 并将它们附加到D上, 使得得到的d+r比特模式用模2算术恰好能被G整除. 如果余数为零, 则表示正确接收
• 模2运算中, 加减法结果相同, 等价于异或运算
• 二进制算术中, 乘 2 r 2^r 2r就是左移k个位置. 这样, 给定D和R, D ⋅ 2 r X O R R Dcdot 2^r XOR R D⋅2rXOR R产生了下图所示的d+r比特模式.
  
• 要使得R对n有 D ⋅ 2 r X O R R = n G Dcdot 2^r XOR R=nG D⋅2rXOR R=nG, 对该式两边都用R异或, 得到
  D ⋅ 2 r = n G X O R R Dcdot 2^r=nG XOR R D⋅2r=nG XOR R
  即 R = r e m a i n d e r D ⋅ 2 r G R=remainderfrac{Dcdot 2^r}{G} R=remainderGD⋅2r​
  
• 每个CRC标准都能检测小于r+1比特的特发差错, 长度大于r+1比特的差错以概率 1 − 0. 5 r 1-0.5^r 1−0.5r被检测到; CRC标准也能检测到任何奇数个比特差错.

多路访问链路和协议

• 点对点链路(point-to-point link)由链路一端的单个发送方和链路另一端单个接收方组成
• 广播链路(broadcase link): 多个发送和接收节点都连接到相同的, 单一的, 共享的广播信道上.
• 多路访问协议(multiple access protocol): 结点通过这些协议来规范在共享的广播信道上的传输行为.
• 碰撞(collide): 结点同时接收到多个帧
• 理想情况下, 对于速率为Rbps的广播信道, 多路访问协议应有以下特性:
  • 当仅有一个结点有数据发送时, 该节点具有Rbps的吞吐量
  • 当有M个节点发送数据时, 每个节点吞吐量为R/Mbps的平均值
  • 协议是分散的, 不因某个结点故障而崩溃

信道划分协议

TDM: 时分多路复用

• TDM将时间划分为时间帧(time frame), 并进一步划分每个时间帧为N个时隙(slot), 把每个时隙分配给N个结点中的一个.结点只能在循环的TDM帧中指派个他的时隙内传输分组比特.
• TDM消除了碰撞, 但每个个节点被限制于R/Nbps的平均速率.

FDM: 频分复用

• FDM与TDM类似, 每个结点只能用R/N的带宽

CDMA: 码分多址

• CDMA对每个结点分配一种不同的编码, 使不同的结点能够同时传输, 并不受其他节点干扰.

随机接入协议

• 一个传输结点总以信道全部速率传输, 当有碰撞时, 每个结点反复重发帧,知道无碰撞地通过为止.

时隙ALOHA

• 在每个结点中, 时隙ALOHA的操作为
  • 当结点有一个新帧要发送时, 等到下一个时隙开始并传输
  • 如果没有碰撞, 该节点成功传输, 不考虑重传
  • 如果有碰撞, 结点在时隙结束之间检测到碰撞, 以概率p在后续每个时隙中重传该帧, 知道无碰撞地传输出去.
• 如果有N个结点, 任意一个几点成功传送地概率是 N p ( 1 − p ) N − 1 Np(1-p)^{N-1} Np(1−p)N−1, 最大效率为1/e=0.37

ALOHA

• 时隙ALOHA要求所有结点同步他们的传输, 以在每个时隙开始时开始传输
• 原始ALOHA协议是一个非时隙, 完全分散地协议.
• 纯ALOHA中一个结点成功传输一次的概率是 p ( 1 − p ) 2 ( N − 1 ) p(1-p)^{2(N-1)} p(1−p)2(N−1), 最大效率仅为1/(2e), 是时隙ALOHA的一半.

载波侦听多路访问(CSMA)

• 载波侦听(carrier sensing): 一个结点在传输前先听信道, 如果来自另一个结点的帧正在信道上发送, 节点则等待一小段时间再开始传输
• 碰撞检测(collision detection): 当一个传输结点在传输时一直侦听此信道, 如果检测到另一个结点正在传输干扰帧, 就停止传输
• 信道传播时延(channel propagation delay)会在CSMA中造成碰撞. 实验越长, 载波侦听结点不能侦听到网络中另一个结点已经开始的几率越大.

具有碰撞检测的CSMA(CSMA/CD)

• 二进制指数后退算法(binary eponential backoff): 传输一个给定帧时, 在该帧经历了一连串的n次碰撞后, 结点随机的从 { 0 , 1 , 2 , . . . , 2 n − 1 } {0,1,2,...,2^n-1} {0,1,2,...,2n−1}中选择一个K值
• 效率: CSMA/CD效率有下列近似式:
  p = 1 1 + 5 d p r o p / d t r a n s p=frac{1}{1+5d_{prop}/d_{trans}} p=1+5dprop​/dtrans​1​
  d p r o p d_{prop} dprop​表示信号能量在任意两个适配器之间传播所需的最大时间, d t a n s d_{tans} dtans​表示传输一个最大长度的3以太网帧时间.

轮流协议

• 上文中的ALOHA和CSMA都只具备理想多路访问协议的第一个特性, 但不具备第二个特性.
• 轮询协议: 这些结点之一被指定为主节点, 主结点以循环的方式轮询(poll)每个结点, 告知该节点能够传输帧的最多数量.
• 轮询协议的缺点是引入轮询时延, 并且主节点的故障使得整个信道不可操作.
• 令牌传递协议: 一个称为令牌(token)的特殊帧在结点之间以某种固定的次序进行交换. 当一个结点接收到令牌时, 仅当它有一些帧要发送时, 他才持有这个令牌, 否则立即向下一个结点转发令牌.
• 令牌传递协议的缺点是一个结点的故障会导致整个信道崩溃.

交换局域网

链路层寻址与ARP

MAC地址

• MAC地址: 主机或路由器的网络适配器具有链路层地址, 具有多个网络接口的主机或路由器将有多个链路层地址. 链路层地址有不同的称呼: LAN地址, 物理地址, MAC地址.
• MAC地址长度为6字节, 共有 2 48 2^{48} 248各可能的MAC地址.
• IEEE管理者MAC地址空间, IEEE分配MAC地址的方式是固定一个MAC地址的前14比特, 让公司自己为每个适配器生成后24比特的唯一组合.
• MAC地址是固定的, 与设备绑定
• 适配器向某些目的适配器发送帧时, 发送适配器将目的适配器的MAC插入该帧中, 并将帧发送到局域网中, 因此一块适配器可以接受并非向它寻址的帧. 这样, 适配器将在收到帧时检查其目的MAC地址是否匹配, 不匹配就会丢弃该帧.
• 当适配器确实要发送局域网上所有其他适配器来接受的帧时, 须在帧中插入一个特殊的MAC地址, 对于5字节地址的局域网, 广播地址为48个连续的1(FF-FF-FF-FF-FF-FF)

地址解析协议(ARP)

• ARP模块以局域网上任何IP地址作为输入, 然后返回相应的MAC地址.
• DNS在因特网中任何地方的主机解析主机名, 而ARP只为同一个子网上的主机和路由器解析IP地址.
• 每台主机或路由器在内存中有一个ART表, 表中包含IP地址到MAC地址的映射关系以及映射过期时间
  
• 如果发送方表中没有目的主机的表项, 发送发会构造一个ARP分组(ARP packet), ARP查询分组和相应分组都有相同的格式, 包括发送和接收方的IP和MAC地址. ARP查询分组的目的是寻味子网上所有的其他主机与路由器, 以确定要解析IP的MAC地址. 查询分组中将使用MAC广播地址, 该帧将被子网的所有其他适配器收到, 每个ARP模块将检查它的IP地址是否与ARP分组的目的IP地址匹配, 与之匹配的主机将返回一个带有所希望映射的ARP分组, 然后查询主机将跟新它的ARP表, 并发送IP数据包.

5.4.2 以太网

以太网帧结构

• 前同步码: 以太网帧以8字节的前同步码(Preamble)字段开始, 前同步码前7字节都是10101010; 最后一个字节是10101011, 前7字节用于唤醒接受适配器, 将他们的时钟和发送方的时钟同步; 第八个字节的最后两个比特用于提醒适配器B, 数据内容将到来
• 以太网技术都是无连接的, 提供不可靠服务, 当适配器B收到A的帧并没有通过CRC校验时, B也不会发送确认或否定确认帧.

链路层交换机

• 交换机用于接收链路层帧并将它们转发到出链路
• 交换机自身对子网中的主机和路由器是透明的, 也就是说, 主机或路由器寻址帧而不是向交换机寻址, 并不知道某交换机会接收该帧并将其转发.

交换机转发和过滤

• 过滤(filtering): 决定一个帧该转发到某个接口还是丢弃的交换机功能
• 转发(forwarding): 决定帧应该被导向哪个接口, 并将其移动到接口.
• 交换机的过滤和转发借助于交换机表(switch table)
  
  交换机的3种工作情况:
  1. 表中没有对应表项: 此时交换机广播该帧
  2. 表中有一个表项显示输出接口对映接收到该帧的输入接口, 此时交换机丢弃该帧
  3. 表中有对应的输出接口y ≠ neq ​=x, 此时交换机完成转发功能

自学习

交换机表的建立:

• 交换机表初始为空
• 对于每个接收到的帧, 交换机在表中储存该帧的源地址段中的MAC地址, 该帧到达的接口, 当前时间
• 如果一段时间后交换机没有接收到以该地址作为源地址的帧, 就删掉此地址

交换机与路由器的对比

• 路由器使用IP地址转发, 交换机使用MAC转发, 交换机是第二层的分组交换机, 路由器是第三层的分组交换机

虚拟局域网(virtual local network, VLAN)

• 支持VLAN的交换机允许经一个单一的物理局域网基础设施定义多个虚拟局域网.
• 在一个基于端口的VLAN中, 交换机的端口由网络管理员划分成组, 每个组构成一个VLAN, 每个VLAN中的端口形成一个广播域(即来自一个端口的广播流量仅能到达该组的其他端口)
• 两个VLAN联系的一种方式是将两个VLAN通过路由器相连
• VLAN干线连接(VLAN trunking): 每台交换机上的一个特殊端口被配置为干线端口, 以互联多台VLAN交换机. 该干线端口属于所有VLAN. 为区分干线端口发出的帧属于哪个VLAN, IEEE定了以一种扩展的以太网帧格式, 增加了4字节的VLAN标签. VLAN标签由一个2字节的标签协议标识符字段, 一个2字节的标签控制信息字段和一个3比特的优先权字段构成.
  

链路虚拟化: 网络层作为链路层

多协议标签交换(MPLS)

MPLS链路层帧格式

• MPLS首部位于第二层(如以太网)首部和第三层(IP)首部之间.
• MPLS使能的路由器常被称为标签交换路由器(label-switched router), 因为其可以通过在其转发表中查找MPLS标签来转发MPLS帧,而不需要解析IP首部

数据中心网络