第三章 数据链路层3.1 数据链路层的设计介于网络层和物理层之间1) 物理线路与数据链路物理线路仅提供比特流传输功能没有采取差错控制机制因此比传输可能出错。数据链路物理线路 数据链路层协议的软硬件组成以帧为单位的虚通信功能如网卡适配器。也解释了为什么局域网中的主机、交换机等必须要实现数据链路层而传输过程中由于物理介质的特性不同、网络拓扑和连接方式不同、性能需求和服务质量QoS要求不同等原因都导致经过的不同的链路层可能采用不同的数据链路层协议。2) 信道类型点对点信道一对一通信。广播信道一对多通信必须使用共享信道协议协调发送。3) 主要功能封装成帧检测和纠正物理层在比特传输中可能出现的错误framing在一段数据的前后分别添加首部和尾部构成一个帧首部和尾部帧定界。透明传输不管来自网络层的数据是什么样的比特组合,都能够以帧的形式在链路上传输。1.字符计数法在帧头部设置一个长度字段标明该帧包含的字符总数。接收方读取长度字段后就知道帧在何处结束。但如果长度字段在传输中出错收发双方将彻底失去帧边界同步且无法自动恢复因此很少单独使用。2. 字符/字节填充法用特殊的 ASCII 控制字符标记帧的开始与结束Flag)。若数据部分恰好出现这些特殊字符就在其前面插入转义字符 ESCESC的后一字节无条件成为有效载荷不予检查接收方再去掉该转义字符。如PPP 协议在异步传输链路中使用 0x7E 作为帧标志起止定界符。如果数据中出现 0x7E就转换为 0x7D, 0x5E如果出现转义字符 0x7D 本身则转换为 0x7D, 0x5D。原理是基于字节字符边界要求每个字节都是可识别的字符如ASCII即于依赖特定字符集适合面向字符的异步传输。3. 比特填充法:用一种特殊的比特模式作为帧标志如 01111110。发送方在数据中只要连续遇到 5 个 1就自动插入一个 0避免出现与标志相同的位模式。接收方每当收到 5 个连续的 1就检查并删除后面的 0。不依赖特定字符编码能做到“比特透明”广泛应用于同步通信。差错检测与纠正Error control保证一定差错检测和纠错能力的前提下尽可能减少冗余信息量。误码率 (BERBit Error Rate)传输错误的比特占所传输比特总数的比率。解决信道传输差错问题通常采用增加冗余信息校验信息的策略。由此可以引出两种方向1.检错码error-detectingcode发现出错就重传。就需要信道高可靠、误码率较低这样偶尔才需要重传。1奇偶校验在数据后附加一个校验位使整个码字中“1”的个数恒为奇数奇校验或偶数偶校验。发送10110014个1若采用偶校验则附加0凑成偶数个1若误传导致1的个数为奇数立刻发现单比特错。二维奇偶校验: 检测并纠正单个比特差错2校验和将数据按固定长度如16位分成若干段逐段补码求和运算计算结果取反作为校验和附在数据后。接收方同样相加并与校验和比对不一致即出错。实现简单但检错能力弱于CRC不能检测出偶数个对称位反转等情况。用于TCP/UDP校验和、IP首部校验等。3循环冗余校验CRC将数据看作一个大的二进制数用双方约定的生成多项式进行模2除法不考虑进位和借位运算过程类似于异或得到的余数即为冗余码Frame Check SequenceFCS帧检验序列附加在数据后发送。接收方用同样的生成多项式除整个帧余数为0则认为无错。能检测所有奇数个错误、所有双比特错误前提是多项式选得好、所有长度≤r的突发错误r为冗余位数是目前数据链路层如HDLC、以太网最常用的检错方式。如数据1101011011生成多项式G(x)x^4 x^1 1二进制10011。先在数据后补4个0生成多项式最高次幂4得到1101011011 0000用10011做模2除法得余数1110即CRC码。发送帧为1101011011 1110。接收方用10011除这个比特串余数为0表示正确。•反馈重发(Automatic Request for Repeat, ARQ)若接收数据无错则向发送端发送传输正确ACK信息否则向发送端发送传输错误NAK信息。发送端收到NAK信息后就会重发。(也会有一个计时器因为接收方可能根本没有收到数据或者回传时丢失避免死锁)•超时重发(Timeout Retransmission)若数据无错则向发送端发送传输正确ACK信息否则丢弃出错数据。此时发送端在定时器发送时启动定时器时间一般不低于“从发完数据帧到收到ACK确认帧所需的平均时间”超时时没有收到ACK信息就会重发。2.纠错码error-correctingcode)发现出错并知道怎么修正不用重传。可靠传输ARQ、超时重传、序号。3.2 点对点控制协议 PPP(Point-to-Point Protocol)PPP 由 IETF 制定简单灵活能够在不同的链路上运行,可承载多种网络层协议是使用最多的数据链路层协议之一主要功能成帧、透明传输、差错检测、链路监测、设置链路最大传输单元MTU、网络层地址协商、数据压缩协商。组成封装Encapsulation)定义了将网络层数据包IP、IPX等封装成帧的格式允许多种协议在同一条链路上复用。链路控制(LCP, Link Control Protocol负责链路的自动建立、配置参数如最大帧长、认证方式、检测链路质量以及在通信结束后释放链路。网络层控制(NCP, Network Control) Protocol为不同的网络层协议分别提供配置。例如IPCP用于分配IP地址、设置DNS等。认证支持可选的用户身份验证常见的有PAP口令认证协议和CHAP挑战握手认证协议用于确保连接合法性。帧格式Flag | Address | Control | Protocol | Information | FCS | Flag。0x0021IP 数据报 0x8021网络控制数据 NCP 0xC021链路控制数据 LCP透明传输异步传输收发双方时钟独立以字符字节为最小单位用字节填充避免出现与Flag0x7E相同的字段定义转义字符0X7D并使用字节填充 将信息字段中出现的0x7E 字节转变成为2字节序列(0x7D, 0x5E) 若信息字段中出现一个0x7D 字节, 则将其转变成为2字节序列(0x7D, 0x5D) 若信息字段中出现 ASCII 码的控制字符即数值小于 0x20 的字符则在该字符前面要加入一个 0x7D 字节同时将该字符的编码0x20加以改变同步传输收发双方时钟严格同步以连续比特流为处理单位用比特填充−采用比特填充方法来实现透明传输。 −信息字段中出现了和标志字段 F 完全一样的 8 比特组合0x7E −发送端在 5 个连 1 之后填入 0 比特再发送出去 −在接收端把 5 个连 1之后的 0 比特删除PPP 链路初始化过程1用户拨号接入 ISP用于获得访问互联网权限 后就建立了一条从用户个人电脑到 ISP 的物理连接。 2用户个人电脑向 ISP 发送一系列的链路控制协议 LCP 分组封装成多个 PPP 帧以便建立LCP连接。 3之后进行网络层配置。网络控制协议 NCP 给新接入的用户个人电脑分配一个临时的 IP 地址。 4当用户通信完毕时NCP 释放网络层连接收回原来分配出去的IP地址。LCP 释放数据链路层连接。最后释放的是物理层的连接。3.3 使用广播信道的数据链路层1) 共享介质问题多站点同时发送会冲突。解决方式静态划分时分频分波分码分或动态接入随机/受控。2) 随机接入协议Aloha 是夏威夷语它有多种含义包括“你好”、“再见”、“爱”和“和平”。在夏威夷文化中Aloha 也是一种生活方式代表着尊重、善良和热情好客。ALOHA随时都可以发。-随时可能冲突时隙 ALOHA时间分成时隙时隙的长度对应一帧的传输时间。帧的发送必须在时隙的起点。 -在时隙的起点可能冲突CSMACarrier Sense Multiple Access先听后发仍可能因同时传送或传播时延产生冲突。非持续式CSMA①经侦听如果介质空闲开始发送 ②如果介质忙则等待一个随机分布的时间然后重复步骤①1-持续式CSMAp1①经侦听如介质空闲则发送 ②如介质忙持续侦听一旦空闲立即发送 ③如果发生冲突等待一个随机分布的时间再重复步骤①p-持续式CSMA①经侦听如介质空闲那么以 p的概率 发送以(1–p)的概率延迟一个时间单元发送 ②如介质忙持续侦听一旦空闲重复① ③如果发送已推迟一个时间单元再重复步骤①CSMA/CDCSMA Collision Detection先听后发、边发边听、冲突停发、退避重发。①经侦听如介质空闲则发送。 ②如介质忙持续侦听一旦空闲立即发送。 ③如果发生冲突等待一个随机分布的时间再重复步骤①CSMA/CD要侦听到冲突就要延长发送帧的时间相当于占用用来检测是否冲突至少为冲突窗口发送站发出帧后能检测到冲突的最长时间2t往返传播时延。即最小帧长LminLmin/V≥2D/τ总线长度为D m信号传播速度为τ/s主机发送速率为V bps。使用CSMA/CD检测到冲突后会立即中止传输并发出一个短冲突加强信号JAM在等待一段随机时间后重发。随机时间取值范围如下 截断式二进制指数后退(truncated Binary exponential backoff )的CSMA/CD 确定基本退避时间槽其长度为传输介质上往返传播时间(2τ) 定义重传次数k min[ 重传次数 , 10 ] 从[0,2k-1]中随机地取出一个整数r 重传所需的时延就是r倍的时间槽2τ 当重传达 16 次仍不能成功时即丢弃该帧并向高层报告。4) 以太网Ethernet局域网范畴随机接入不必先建立连接就可以直接发送数据。实现共享信道下的高效竞争。 无需确认对发送的数据帧不进行编号也不要求对方发回确认。规避竞争式确认造成的低效循环并遵从端到端设计 尽力而为尽最大努力交付对有差错帧是否需要重传则由高层来决定。牺牲局部可靠性换取了极低的成本和至上层的最大灵活性帧格式DIX Ethernet V2 (Type)IEEE 802.3Length7B前导码Preamble和1B帧前定界符SFD也有写作SOFStart of Frame保证接收电路在帧的目的地址字段到来之前达到正常接收状态。8字节的前导码和帧前定界符不需要保留也不计入帧头长度。由网卡硬件在发送数据前自动发出用完就直接被丢弃MAC 地址MediaAccessControlAddress硬件地址,又称为物理地址唯一标识符。例如单播unicast 5C-26-0A-7E-4E-4C 广播broadcastFF-FF-FF-FF-FF-FF 组播multicast 01-00-5E-00-00-00https://en.wikipedia.org/wiki/File:MAC-48_Address.svg源地址后面的两个字节在Ethernet V2为上一层的协议类型具体对照表见Ethertypes在IEEE802.3为数据长度。数据字段46B - 1500B实际开始接收的是MAC帧MAC帧最小 64B46B18B帧最大1518BMTU1500B 18B)。MAC帧最小是因为802.3规范中的10Mbps以太网最大长度为2500m具有4个中继器在最差情况下往返一次时间大约是50微秒在这个时间内能发送500b加上安全余量增加至512b即64B。从而确保如果发生冲突就一定是在发送的前 64 B之内就被检测到。凡长度小于 64 B的帧都是由于冲突而异常中止的无效帧。校验和FCSFrame Check SequenceCRC-32 计算除了校验和以外的其他字段对检查出的无效MAC帧丢弃不重传。无效MAC帧 数据字段的长度与长度字段的值不一致 帧的长度不是整数个字节 用收到的帧检验序列 FCS 查出有差错 数据字段的长度不在 46 ~ 1500 字节之间。以太网的帧间最小间隔IFG:IEEE 802.规定帧间最小间隔为 9.6 ms相当于 96 bit 的发送时间。一个站在检测到总线开始空闲后还要等待 9.6 ms 才能再次发送数据。这是为了使刚刚收到数据帧的站的接收缓存来得及清理做好接收下一帧的准备。3.4 扩展的以太网1) 物理层扩展信号在介质上传输会造成信号衰减。中继器Repeater扩展。5-4-3-2-1 原则任意两个收发器之间距离不得超过2.5km且任意两个收发器之间经过的中继器不能超过4个以保证MAC协议正常工作。集线器(Hub,相当于多端口的中继器)扩展光纤扩展碰撞域collision domain/ 冲突域网络中一个站点发出的帧会与其他站点发出的帧产生碰撞或冲突的那部分网络。 碰撞域越大发生碰撞的概率越高。在物理层扩展以太网构成了一个更大的碰撞域扩大了地理覆盖范围总的吞吐量未提高2) 数据链路层扩展交换机是多接口的网桥Bridge端口全双工每端口一个碰撞域有并行性。即插即用自学习根据源 MAC 建立交换表即内容可寻址存储器CAM (Content addressable Memory)。交换方式对称交换所有端口必须工作在同一速率下。入快出慢假设千兆口发给百兆口输入端“灌”数据极快输出端“倒”得慢。因为必须收到前64字节就开始转发不能预先缓存输出缓冲会瞬间被淹没。当输出口忙于处理堆积的数据时新到的尾部就会因无法及时写入而被迫丢弃导致帧损坏。入慢出快当百兆口发给千兆口时由于输入速率慢输出口发完开头64字节后后续数据就会供应不上产生“发送空档”。这严重违反了以太网“帧内间隙”的规范接收方会将其视为无效帧而丢弃。直通交换收到帧的目的地址8B就发不支持非对称交换。无碎片交换接收到帧的前64字节再开始发过滤了冲突碎片不支持非对称交换。存储转发转发前必须接收整个帧、执行CRC校验不转发出错帧、支持非对称交换。交换机交换带宽是指交换机单位时间内的数据吞吐量即 Σ(端口*端口速率 (全双工模式再乘以2))单位bps。广播风暴存在环路解决广播风暴的方法消除环路STP3) VLAN广播域广播帧能够到达的范围。VLAN 是独立广播域。交换机通过划分VLAN来分隔广播域提升安全与管理性。基于端口、 基于MAC地址、 基于协议、基于子网帧标记标准802.1Q 在帧中插入 4 字节 VLAN 标记。带VLAN标记的帧称为标记帧Tagged Frame 不携带VLAN标记的普通以太网帧称为无标记帧Untagged FrameAccess 端口只属于一个 VLAN用户设备无需识别802.1Q帧的设备Trunk 端口承载多个 VLAN交换机之间。3.5 高速以太网100MFast Ethernet保留以太网帧格式与协议。1GGigabit支持全双工半双工需载波延伸与分组突发。载波延伸将争用时间增大为 512 字节。凡发送的 MAC 帧长不足 512 字节时就用一些特殊字符填充在帧的后面。 分组突发当很多短帧要发送时第 1 个短帧采用载波延伸方法进行填充随后的一些短帧则可一个接一个地发送只需留有必要的帧间最小间隔即可。这样就形成可一串分组的突发直到达到 1500 字节或稍多一些为止。10G/40G/100G只支持全双工重点在物理层演进不再使用CSMA/CD。为什么不用了CSMA/CD 强制要求发送完一个最短帧64字节之前必须能检测到最远端的冲突。这就产生了一个约束速率提升距离必须反比缩短。100Mbps 时最远 200 米1Gbps 时理论只剩 20 米那么 10Gbps 呢如果 10G 继续用半双工和 CSMA/CD检测冲突的时间窗口极短传输距离会被压缩到只有几米彻底失去实用价值。9.1 无线局域网 WLAN1) 组网模式SSID、BSSID、MAC地址之间的关系基础架构模式分布式系统DS、访问点AP、站点STA标识符 SSID(Service Set Identifier)/BSSIDBasic Service Set Identifier即AP 的 MAC 地址。 基本服务集BSS、扩展服务集ESS、站点之间通信通过AP转发自组织模式Ad hoc站点STA、独立基本服务集IBSS 站点之间直接通信共享同一无线信道2) 接入方式固定接入 (fixed access)在作为网络用户期间用户设置的地理位置保持不变。 移动接入 (mobility access)用户设置能够以车辆速度移动时进行网络通信。当发生切换时通信仍然是连续的。 便携接入 (portable access)在受限的网络覆盖面积中用户设备能够在以步行速度移动时进行网络通信提供有限的切换能力。 游牧接入 (nomadic access)用户设备的地理位置至少在进行网络通信时保持不变。如用户设备移动了位置则再次进行通信时可能还要寻找最佳的基站。3IEEE 802.11 物理层与标准演进2.4⁄5 GHz ISM 频段调制从 DSSS 到 OFDMA、MU-MIMO。标准802.11b/a/g/n/ac/ax 等速率与密集接入能力持续提升。4) CSMA/CA为什么不用CSMA/CD 1.冲突检测困难难以实现“边发边听“发送功率和接收功率相差太大。当一个无线设备在发送时其自身发出的强信号会淹没掉同一频率上远处其他设备传来的微弱信号。2.隐藏终端问题 由于距离太远或障碍物导致站点无法检测到竞争对手的存在隐藏站点不能侦听到发送端但能干扰接收端。 3.暴露终端问题由于侦听到其他站点的发送而误以为信道忙导致不能发送暴露站点能侦听到发送端但不会干扰接收端。所以采用从“检测”转向“避免”的策略CSMA/CA采用碰撞避免CACollision Avoidance所有站点完成发送后必须等待一段很短的时间才能发送下一帧。这段时间通称为帧间间隔或帧间隙 (IFSInter-Frame Space)。不同类型的帧间间隔类别不同DIFSSIFS 当信道空闲时间大于IFS帧间隙立即传输当信道忙时延迟直到当前传输结束IFS时间。开始随机退避过程 从0CWindow中选择一个随机数作为退后计数器backoff counter通过侦听确定每个时间槽是否活动 如果没有活动则减少退避时间 退避过程中如果信道忙则冻结退避过程解决站点之间的公平问题在当前帧传输结束后恢复退避过程避免发生碰撞的两种机制停止等待协议链路层确认解决碰撞后重传发送数据等待确认超时重传重传定时器如果达到最大重传限制(6次该帧被丢弃并告知上层协议。添加图片注释不超过 140 字可选IFS 优先级SIFS最高优先级用于Ack, CTS, 轮询响应等 PIFS中等优先级SIFS1槽口时间轮询服务 DIFS最低优先级 SIFS2槽口时间异步数据服务RTS/CTS可选 通过信道预约避免长帧冲突发送端发送RTSrequest to send 接收端回送CTSclear to send RTS和CTS中的持续时间Duration中指明传输所需时间数据控制 其他相关站点能够收到RTS或和CTS维护NAV。 RTS和CTS帧很短即使产生冲突信道浪费较少。4) 802.11 帧管理帧、控制帧、数据帧。地址字段 1~4 的含义依赖“去往/来自 DS”确定。经过AP1 / 2经过路由器3帧控制域含重传、更多分片、电源管理、WEP 等标志。5) 关联与漫游设备如何关联到AP从而上网关联流程扫描 → 认证 → 关联。漫游的核心目的是让终端在移动中从一个接入点AP切换到另一个时保持网络连接不中断上层应用无感知。建立关联的两种方法-被动扫描AP 周期性发出信标帧 (beacon frame)其中包含 SSID 、速率等系统参数。 移动站 A 扫描 11 个信道选择加入到 AP2 所在的基本服务集 BSS2向 AP2 发出关联请求帧 (Association Request frame)。 AP2 同意移动站 A 发来的关联请求向移动站A发送关联响应帧 (Association Response frame)。-主动扫描移动站 A 主动发出广播的探测请求帧 (Probe Request frame)让所有能够收到此帧的接入点知道有移动站要求建立关联。 两个 AP 都回答探测响应帧 (Probe Response frame)。 移动站 A 向 AP2 发出关联请求帧 (Association Response frame)。 AP2 向移动站 A 发送关联响应帧与移动站 A 建立关联。认证当站点找到与其有相同 SSID 的 AP在 SSID 匹配的 AP 中根据收到的 AP 信号强度选择一个信号最强的 AP然后进入认证阶段认证方式有开放系统身份认证 (open-system authentication) 共享密钥认证 (shared-key authentication WPA PSK认证pre-shared key 802.1X EAP认证关联身份认证获得通过后 进入关联阶段。站点向 AP 发送关联请求Association Request包含Capability, Listen Interval, SSID, Supported Rates AP 向站点返回关联响应Association Response包含Capability, Status Code, Station ID, Supported Rates AP维护站点关联表并记录站点的能力如能够支持的速率等自组织模式建立关联站点先寻找具有指定SSID的IBSS是否已存在。如果存在则加入若不存在则自己创建一个IBSS发出Beacon等其他站来加入。 IBSS中的所有站点参与Beacon发送保证健壮性每个站点在Beacon窗口竞争Beacon的产生。对于每个站点 •确定一个随机数k•等待k个时间槽 •如果没有其他站点发送Beacon则开始发送Beacon站点漫游重关联请求/响应DS 通知旧 AP。当前的AP的通道质量下降时站点漫游到不同的AP。 通过扫描功能发现通道质量更好的AP被动扫描、主动扫描 站点向新的AP发送重关联请求Reassociation Request当使用分离 (dissociation) 服务时可终止这种关联 如果AP接受重关联请求AP 向站点返回重关联响应Reassociation Response •如果重关联成功则站点漫游到新的AP •新的AP通过分布系统通知之前的AP站点睡眠延长电池的续航时间。无线网卡的空闲接收状态占电量消耗的主要部分关闭无线网卡可以减少电量的消耗关联的AP允许空闲站睡眠AP跟踪睡眠的站点并为之缓存数据保证数据不丢失保证会话的持续性。•Beacons 中的TIMTraffic Indication Map通知睡眠站点有需要接收的数据 •睡眠站点定期唤醒接收数据如果有数据要接收发送PS-Poll帧请求AP发送数据帧省电AP 缓存数据TIM 通知PS-Poll 拉取。参考资料Aloha