第三章 计算机网络体系结构

第3章计算机网络体系结构1.通信协议人际交流的协议:人类之间语言和文字系统语法、意义、对话交替顺序…

说明发送的消息…说明接收到某消息后所应采取的行动…说明动作的次序通信协议:计算机之间网络中所有的通信活动都是由协议所控制协议：

定义网络实体间发送和接收报文的格式、顺序以及当传送和接收消息时应采取的行动。（语义、语法和时序）协议设计目的计算机之间的信息交互time连接响应发送文件连接请求获取文件交流的基础：

共同的语言、互相理解，

共同语义……有同学提问吗？我有问题请说协议设计目的是什么呢？3人们之间的信息交互

网络协议协议设计目的网络协议为进行网络中的数据交换而建立的规则、标准或约定，即网络协议(networkprotocol)通信双方需要共同遵守，互相理解三要素语法：规定传输数据的格式（如何讲）语义：规定所要完成的功能（讲什么）时序：规定各种操作的顺序（双方讲话的顺序）网络协议设计目的可靠性资源分配拥塞问题自适应性安全问题4

网络协议协议层次结构

用户应用层

信件递送层

交通运输层

交通工具层运送部门铁路部门邮局运送部门汽运部门汽运部门邮包邮包货物货物火车汽车货物货物信件传递的信息邮包货物用户B用户A邮局运送部门铁路部门邮包货物信件信件5

网络协议协议层次结构层次栈为了降低网络设计的复杂性，大部分网络都组成一个层次栈，每一层都建立在其下一层的基础上对等实体不同机器上构成相应层次的实体成为对等实体接口在每一对相邻层次之间的是接口；接口定义了下层向上层提供哪些原语操作与服务网络体系结构层和协议的集合为网络体系结构，一个特定的系统所使用的一组协议，即每层的协议，称为协议栈第五层第四层第三层第二层第一层物理介质第五层第四层第三层第二层第一层主机A主机B第四/五层接口第三/四层接口第二/三层接口第一/二层接口对等实体对等实体对等实体对等实体对等实体6

网络协议服务原语两种不同类型的服务：面向连接和无连接面向连接：按照电话系统模型建立的（一个常见的例子）拨姑姑家的电话号码。她家的电话铃响了。她拿起电话。你听到响铃停止。你邀请她来喝茶。她听到了你的邀请。她说她很高兴来。你听到她接受邀请。你挂断电话。她听到了，也挂断电话。面向连接的服务每个“请求”或“响应”后，都在对方产生一个“指示”或“确认”动作7

网络协议服务原语无连接：按照邮政系统模型建立的（一个常见的例子）有快递要发给朋友快递员上门取件快递进入区域集散中心区域集散中心通过运输系统发到目的地区域集散中心分发给目的地快递员快递员按照地址派送无连接的服务邮件携带了完整的目标地址，传输过程不需要应答8

网络协议服务原语服务典型服务：面向连接传输服务，无连接传输服务服务由一组可用于用户进程以访问服务的原语（操作）形式指定原语告诉服务执行某些操作或报告对等实体所采取的操作六个核心服务原语（以面向连接服务为例）系统调用内核协议栈驱动器系统调用内核协议栈驱动器（1）连接请求（2）接受响应（3）请求数据（4）应答（5）请求断开（6）断开连接服务进程客户进程客户机服务器9

网络协议服务与协议的关系协议是“水平”的，服务是“垂直”的实体使用协议来实现其定义的服务上层实体通过接口使用下层实体的服务协议(n+1)接口接口交换信息交换信息实体(n+1)服务提供者第n层第n+1层实体(n+1)服务的用户实体(n)实体(n)协议(n)10

网络协议OSI参考模型简介计算机网络面临的问题

用户的资源和信息存储在采用不同操作系统的主机中，这些主机分布在网络的不同地方，需要在不同的传输介质上实现采用不同操作系统的主机之间的通信，解决异种机和异种网络互连问题的方法。分层的好处

容易解决通信的异质性（heterogeneity）问题；上层解决不同种语言的相互翻译（数据的不同表示）；下层解决信息传递；使复杂问题简化，高层屏蔽低层细节问题；每层只关心本层的内容，不用知道其他层如何实现；使设计容易实现，每个层次向上一层提供服务，向下一层请求服务。参考模型的必要性互联网大厂X讯与X东的合作12层级组织（分层）总裁-总监-经理-码农内部独立（模块）我用Python;我用GO铁打的项目，流水的码农沟通协作（标准）合作协议、项目文档、接口定义日报、周报、月报总裁总监经理码农战略合作确定项目细化功能代码接口参考模型参考模型的必要性计算机网络的复杂与异构介质：光纤、铜缆、空气...接入：有线、WLAN、移动数据网络、蓝牙...应用：无人驾驶、万物互联、短视频、邮件...高速更新迭代大哥大1G（模拟）、2G(数字)、3G、4G、5GIEEE802.3：2020年推出4个版本...13分层结构统一标准模块独立明晰简化，便于分析学习各层独立，加速技术演进统一接口，确保技术互通（interoperable）开发个游戏直播软件，是否需要针对3G/

4G/5G还是WiFi单独开发？WiFi发展为新版本WiFi6，那么WiFi6是否要对已有直播、微信或支付宝做适配？

参考模型OSI参考模型OSI7层模型OSI：OpenSystemsInterconnectionDay,Zimmermann,1983物理层（PhysicalLayer）定义如何在信道上传输0、1：Bitsonthewire机械接口（Mechanical）：网线接口大小形状、线缆排列等电子信号（Electronic）：电压、电流等时序接口（Timing）：采样频率、波特率、比特率等介质（Medium）：各种线缆、无线频谱等...14应用层ApplicationLayer表示层PresentationLayer会话层SessionLayer传输层TransportLayer网络层NetworkLayer数据链路层DataLinkLayer物理层PhysicalLayer

参考模型OSI参考模型数据链路层(DataLinkLayer)实现相邻（Neighboring）网络实体间的数据传输成帧（Framing）：从物理层的比特流中提取出完整的帧错误检测与纠正：为提供可靠数据通信提供可能物理地址（MACaddress）：48位，理论上唯一网络标识，烧录在网卡，不便更改流量控制，避免“淹没”（overwhelming）:当快速的发送端遇上慢速的接收端，接收端缓存溢出共享信道上的访问控制（MAC）：同一个信道，同时传输信号。如同：同一间教室内，多人同时发言，需要纪律来控制。...15应用层ApplicationLayer表示层PresentationLayer会话层SessionLayer传输层TransportLayer网络层NetworkLayer数据链路层DataLinkLayer物理层PhysicalLayer

参考模型OSI参考模型网络层(NetworkLayer)将数据包跨越网络从源设备发送到目的设备（hosttohost）路由（Routing）：在网络中选取从源端到目的端转发路径，常常会根据网络可达性动态选取最佳路径，也可以使用静态路由路由协议：路由器之间交互路由信息所遵循的协议规范，使得单个路由器能够获取网络的可达性等信息服务质量（QoS）控制：处理网络拥塞、负载均衡、准入控制、保障延迟异构网络互联：在异构编址和异构网络中路由寻址和转发16应用层ApplicationLayer表示层PresentationLayer会话层SessionLayer传输层TransportLayer网络层NetworkLayer数据链路层DataLinkLayer物理层PhysicalLayer思考：为何在唯一的MAC地址之外，还需要唯一的IP地址？参考模型OSI参考模型传输层(TransportLayer)将数据从源端口发送到目的端口（进程到进程）网络层定位到一台主机（host），传输层的作用域具体到主机上的某一个进程网络层的控制主要面向运营商，传输层为终端用户提供端到端的数据传输控制两类模式：可靠的传输模式，或不可靠传输模式可靠传输：可靠的端到端数据传输，适合于对通信质量有要求的应用场景，如文件传输等不可靠传输：更快捷、更轻量的端到端数据传输，适合于对通信质量要求不高，对通信响应速度要求高的应用场景，如语音对话、视频会议等17应用层ApplicationLayer表示层PresentationLayer会话层SessionLayer传输层TransportLayer网络层NetworkLayer数据链路层DataLinkLayer物理层PhysicalLayer

参考模型OSI参考模型会话层(SessionLayer)利用传输层提供的服务，在应用程序之间建立和维持会话，并能使会话获得同步表示层（PresentationLayer）关注所传递信息的语法和语义，管理数据的表示方法，传输的数据结构应用层（ApplicationLayer）通过应用层协议，提供应用程序便捷的网络服务调用18应用层ApplicationLayer表示层PresentationLayer会话层SessionLayer传输层TransportLayer网络层NetworkLayer数据链路层DataLinkLayer物理层PhysicalLayer参考模型层层的名称设备协议7|5应用层表示层会话层TFTP、FTP、SMTP、Telnet、HTTP、SNMP、DNS、

NFS、rlogin4传输层TCP、UDP、IPX3网络层路由器、三层交换机AppleTalk、DECnet、IP、IPX、Vines、XNS、ICMP、ARP、RARP等2数据链路层交换机、网桥、网卡ATM、PPP、HDLC、帧中继、802.2、802.31物理层集线器

设备、协议与其所在的层1.各层功能总览

SummaryofLayerFunctionsL1L2L3L4L5L6L7PhysicalLayerNetworkLayerTransportSessionPresentationApplicationDataLinkControl7应用层6表示层5会话层4传输层3网络层2数据链路层1物理层

用户系统层

数据通信网衔接

软件主要由软件实现（面向通信用户）

资源子网的任务

网络主要由硬件实现（完成传送服务）通信子网任务

OSI参考模型示意图TCP/IP参考模型TCP/IP参考模型：ARPANET所采用以其中最主要的两个协议TCP/IP命名Vint

Cerf和Bob

Kahn于1974年提出链路层（LinkLayer）描述了为满足无连接的互联网络层需求，链路必须具备的功能互联网层（InternetLayer）允许主机将数据包注入网络，让这些数据包独立的传输至目的地，并定义了数据包格式和协议（IPv4协议和IPv6协议）传输层（TransportLayer）允许源主机与目标主机上的对等实体，进行端到端的数据传输：TCP，UDP应用层（ApplicationLayer）传输层之上的所有高层协议：DNS、HTTP、FTP、SMTP...22应用层applicationLayer传输层transportLayer互联网层internetLayer网络接口层host-to-network

Layer

参考模型先有TCP/IP协议栈，然后有TCP/IP参考模型参考模型只是用来描述协议栈的

ARPNET

最终采用TCP和IP为主要协议TCP/IP参考模型TCP/IP参考模型摒弃电话系统中“笨终端&聪明网络”的设计思路采用聪明终端&简单网络，由端系统TCP负责丢失

恢复等，简单的网络大大提升了可扩展性实现了建立在简单的、不可靠部件上的可靠系统IP分组交换的特点可在各种底层物理网络上运行(IPovereverything)可支持各类上层应用(EverythingoverIP)每个IP分组携带各自的目的地址，网络核心功能

简单（通过路由表转发分组），适应爆炸性增长23

参考模型TCP/IPTCP/IP的沙漏模型OSI模型与TCP/IP模型比较7层模型与4层模型TCP/IP模型的网络接口层定义主机与传输线路之间的接口，描述了链路为无连接的互联网层必须提供的基本功能TCP/IP模型的互联网层、传输层与OSI模型的网络层、传输层大致对应TCP/IP模型的应用层包含了OSI模型的表示层与会话层基本设计思想：通用性与实用性OSI：先有模型后设计协议，不局限于特定协议，明确了服务、协议、接口等概念，更具通用性TCP/IP模型：仅仅是对已有协议的描述无连接与面向连接OSI模型网络层能够支持无连接和面向连接通信TCP/IP模型的网络层仅支持无连接通信（IP）24应用层表示层会话层传输层网络层数据链路层物理层应用层传输层互联网层网络接口层OSI7层模型TCP/IP4层模型

参考模型OSI模型与TCP/IP模型比较从未真正被实现TCP/IP已成为事实标准，OSI缺少厂家支持技术实现糟糕OSI分层欠缺技术考虑：会话层、表示层很少内容；数据链路层、网络层内容繁杂。模型和协议过于复杂分层间功能重复：差错控制、流量控制等在不同层反复出现非技术因素TCP/IP实现为UNIX一部分，免费OSI被认为是政府和机构的强加标准25OSI模型的不足核心概念未能体现未明确区分服务、接口和协议等核心概念不具备通用性不适于描述TCP/IP之外的其它协议栈混用接口与分层的设计链路层和物理层一起被定义为网络接口层，而非真正意思上的分层模型欠缺完整性未包含物理层与数据链路层物理层与数据链路层是至关重要的部分TCP/IP模型的不足参考模型OSI的失败：糟糕的时机、技术、实现、政策本教程内容的分层组织突出核心概念区分接口与分层体现完整性体现通用性简化分层，易于教学26应用层表示层会话层传输层网络层数据链路层物理层应用层传输层互联网层网络接口层OSI7层模型TCP/IP4层模型应用层传输层网络层数据链路层物理层本教程的分层组织

参考模型分层模型与网络实例端到端通信实例：主机A上的QQ，发送消息；主机B上的QQ，接收消息发送端层层封装，接收端层层解封装不同层对应协议数据单元（PDUProtocolDataUnit）27应用层传输层网络层链路层物理层发送：hello

helloHthelloHnHthello

HlHnHthello应用层传输层网络层链路层物理层链路层物理层链路层物理层网络层链路层物理层接收：hello101101010000...

hello

Hthello

HnHthello

HlHnHthello101101010000...消息message段segment数据报packet帧frame主机A交换机交换机主机B路由器封装Encapsulation解封装De-encapsulation参考模型数据链路层的功能链路管理包括：链路的建立、维持、释放成帧（Framing）将比特流划分成“帧”的主要目的是为了检测和纠正物理层在比特传输中可能出现的错误，数据链路层功能需借助“帧”的各个域来实现差错控制（ErrorControl）处理传输中出现的差错，如位错误、丢失等流量控制（FlowControl）确保发送方的发送速率，不大于接收方的处理速率避免接收缓冲区溢出283.1数据链路层的设计问题数据链路层提供的服务无确认无连接服务（

Unacknowledgedconnectionless

）接收方不对收到的帧进行确认适用场景：误码率低的可靠信道；实时通信；网络实例：以太网有确认无连接服务（

Acknowledgedconnectionless

）每一帧都得到单独的确认适用场景：不可靠的信道（无线信道）网络实例：802.11有确认有连接服务（

Acknowledgedconnection-oriented

）适用场景：长延迟的不可靠信道293.1数据链路层的设计问题成帧（Framing）分组(packet)与帧(frame)的关系303.1数据链路层的设计问题数据链路层网络层分组发送方头标尾标分组接收方头标尾标帧有效载荷有效载荷成帧（Framing）关键问题：如何标识一个帧的开始？接收方必须能从物理层接收的比特流中明确区分出一帧的开始和结束，这个问题被称为帧同步或帧定界关键：选择何种定界符？定界符出现在数据部分如何处理？成帧（framing）的方式字节计数法（Bytecount）带字节填充的定界符法（

Flagbyteswithbytestuffing）带比特填充的定界符法（

Flagbitswithbitstuffing）物理层编码违例（Physicallayercodingviolations）313.1数据链路层的设计问题成帧（Framing）字节计数法：无差错传输的情形323.1数据链路层的设计问题第1帧5字节第2帧5字节第3帧8字节第4帧6字节512345123481234567612345问题：如果某个计数字节出错会发生什么情况？成帧（Framing）字节计数法：出现了一个字节差错的情形333.1数据链路层的设计问题第1帧5字节第2帧出现差错第3帧8字节第4帧6字节512348123481234567612345破坏了帧的边界，导致一连串帧的错误成帧（Framing）带字节填充的定界符法定界符（FLAG）：一个特殊的字节，比如01111110，即0x7E，用于区分前后两个不同的帧343.1数据链路层的设计问题FLAG头标有效载荷尾标FLAG一个帧定界符定界符问题：如果有效载荷部分包含与“定界符”相同的字节会有什么问题？成帧（Framing）带字节填充的定界符法：发送方检查有效载荷，进行字节填充353.1数据链路层的设计问题FLAG头标有效载荷尾标FLAGFLAGBAESCBAESCBAFLAGESCBAFLAGESCBAESCESCBAESCESCBAESCESCFLAGESCBAESCESCESC转义字节成帧（Framing）带字节填充的定界符法：接收方的处理逐个检查收到的每一个字节收到ESC则后一字节无条件成为有效载荷，不予检查收到FLAG则为帧的边界363.1数据链路层的设计问题成帧（Framing）带字节填充的定界符法：收方的处理示例373.1数据链路层的设计问题ESCBAFLAGESCBAESCESCBAESCESCFLAGESCBAESCESCESCFLAGBAESCBAESCBAFLAGESCBAESC接收方收到的数据

处理后的数据

问题：带字节填充的定界符法有什么不足？成帧（Framing）带比特填充的定界符法定界符：两个0比特之间，连续6个1比特，即01111110，0x7E383.1数据链路层的设计问题010110111111001110001011定界符上一帧下一帧问题：如果有效载荷部分包含与“定界符”相同的位组合如何解决？成帧（Framing）带比特填充的定界符法：发送方检查有效载荷若在有效载荷中出现连续5个1比特，则直接插入1个0比特393.1数据链路层的设计问题011111011111100011100010原始载荷载荷填充01111100111110100011101000成帧（Framing）带比特填充的定界符法：接收方的处理若出现连续5个1比特若下一比特为0，则为有效载荷，直接丢弃0比特若下一比特为1，则连同后一比特的0，构成定界符，一帧结束403.1数据链路层的设计问题00011111011111100011100010处理后的载荷收到的比特流011111011111100011101000丢弃丢弃成帧（Framing）物理层编码违例：核心思想：选择的定界符不会在数据部分出现4B/5B编码方案4比特数据映射成5比特编码，剩余的一半码字（16个码字）未使用，可以用做帧定界符例如：00110组合不包含在4B/5B编码中，可做帧定界符前导码存在很长的前导码（preamble），可以用作定界符例如：传统以太网、802.11曼切斯特编码/差分曼切斯特编码正常的信号在周期中间有跳变，持续的高电平（或低电平）为违例码，可以用作定界符例如：802.5令牌环网413.1数据链路层的设计问题差错控制链路层存在的一个问题：信道的噪声导致数据传输问题差错（incorrect）：数据发生错误丢失（lost）：接收方未收到乱序（outoforder）：先发后到，后发先到重复（repeatedlydelivery）：一次发送，多次接收解决方案：差错检测与纠正、确认重传确认：接收方校验数据（差错校验），并给发送方应答，防止差错定时器：发送方启动定时器，防止丢失顺序号：接收方检查序号，防止乱序递交、重复递交423.1数据链路层的设计问题流量控制链路层存在的另一个问题：接收方的处理速率接收方的接收缓冲区溢出解决方案基于反馈(feedback-based)的流量控制接收方反馈，发送方调整发送速率基于速率(rate-based)的流量控制发送方根据内建机制，自行限速43面临的问题3.1数据链路层的设计问题本章内容3.1数据链路层的设计问题3.2差错检测和纠正3.3基本的数据链路层协议3.4滑动窗口协议3.5数据链路协议实例44差错检测与纠正概述典型的纠错码典型的检错码差错检测和纠正概述如何解决信道传输差错问题通常采用增加冗余信息（或称校验信息）的策略简单示例：每个比特传三份，如果每比特的三份中有一位出错，可以纠正453.2差错检测和纠正0100100010110101011010101101010010101011010133.3%66.7%原始数据冗余信息携带2/3的冗余信息！冗余信息量大！差错检测和纠正概述目标：保证一定差错检测和纠错能力的前提下，如何减少冗余信息量？考虑的问题信道的特征和传输需求冗余信息的计算方法、携带的冗余信息量计算的复杂度等两种主要策略检错码（error-detectingcode）纠错码（error-correctingcode)463.2差错检测和纠正差错检测和纠正概述检错码（error-detectingcode）在被发送的数据块中，包含一些冗余信息，但这些信息只能使接收方推断是否发生错误，但不能推断哪位发生错误，接收方可以请求发送方重传数据主要用在高可靠、误码率较低的信道上，例如光纤链路偶尔发生的差错，可以通过重传解决差错问题473.2差错检测和纠正差错检测和纠正概述纠错码（error-correctingcode)发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，并能纠正错误（定位出错的位置）主要用于错误发生比较频繁的信道上，如无线链路也经常用于物理层，以及更高层（例如，实时流媒体应用和内容分发）使用纠错码的技术通常称为前向纠错（FEC，ForwardErrorCorrection)483.2差错检测和纠正差错检测和纠正概述码字(codeword)：一个包含m个数据位和r个校验位的n位单元描述为(n,m)码，n=m+r码率(coderate)：码字中不含冗余部分所占的比例，可以用m/n表示海明距离(Hammingdistance)：两个码字之间不同对应比特的数目例：0000000000与0000011111的海明距离为5如果两个码字的海明距离为d，则需要d个单比特错就可以把一个码字转换成另一个码字为了检查出d个错（比特错），可以使用海明距离为d+1的编码为了纠正d个错，可以使用海明距离为2d+1的编码493.2差错检测和纠正差错检测和纠正概述例如：一个只有4个有效码字的编码方案：0000000000,0000011111,1111100000,1111111111海明距离为5，可以检测4位错，纠正2位错如果已知只有1位或2位错误，接收方接收0000000111则可知原码字为：0000011111如果发生3位错误，例如0000000000变成0000000111，接收方无法纠正错误，但可以检测出错误503.2差错检测和纠正典型检错码常用的检错码包括：奇偶检验

(ParityCheck)：1位奇偶校验是最简单、最基础的检错码校验和(Checksum)：主要用于TCP/IP体系中的网络层和传输层循环冗余校验(CyclicRedundancyCheck，CRC)：数据链路层广泛使用的校验方法3.2差错检测和纠正典型检错码—奇偶校验1位奇偶校验：增加1位校验位，可以检查奇数位错误523.2差错检测和纠正1011010010110101偶校验：保证1的个数为偶数个，例如：奇校验：保证1的个数为奇数个，例如：数据位校验位数据位校验位考虑二维奇偶校验，是否可以进行纠错？典型检错码—校验和TCP/IP体系中主要采用的校验方法3.2差错检测和纠正111100110011001101110101010101010111011101110111011110111011101111001

010001000100001153发送方：进行16位二进制补码求和运算，计算结果取反，随数据一同发送接收方：进行16位二进制补码求和运算（包含校验和），结果非全1，则检测到错误校验和数据1111001100110011011101010101010101110111011101110111

0100010001000011

11111111111111111数据校验和未检测到错误典型检错码—循环冗余校验CRCCRC校验码计算方法设原始数据D为k位二进制位模式如果要产生n位CRC校验码，事先选定一个n+1位二进制位模式G(称为生成多项式，收发双方提前商定)，G的最高位为1将原始数据D乘以2n（相当于在D后面添加n个0），产生k+n位二进制位模式，用G对该位模式做模2除，得到余数R（n位，不足n位前面用0补齐）即为CRC校验码3.2差错检测和纠正原始数据DCRC校验码发送数据k

位n

位k+n

位CRC校验能力：能检测出少于n+1位的突发错误接收端如何计算？54检错码—循环冗余校验CRCCRC校验码计算示例D=1010001101n=5G=110101或G=x5+x4+x2+1R=01110实际传输数据：1010001101011103.2差错检测和纠正

1101010110

G→

110101101000110100000

←

2nD

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101

01110

←

R55检错码—循环冗余校验CRC四个国际标准生成多项式CRC-12=x12+x11+x3+x2+x+1CRC-16=x16+x15+x2+1CRC-CCITT=x16+x12+x5+1CRC-32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1例如，以太网、无线局域网使用CRC-32生成多项式引自：清华大学崔勇老师提供的讲稿3.2差错检测和纠正典型纠错码设计纠错码要求：m个信息位，r个校验位，纠正单比特错对2m个有效信息中任何一个，有n个与其距离为1的无效码字：可以考虑将该信息对应的合法码字的n位逐个取反，得到n个距离为1的非法码字，需要n+1个位模式来标识因此有：(n+1)2m

2n利用n=m+r，得到(m+r+1)2r在给定m的情况下，利用该式可以得出纠正单比特错误校验位数的下界573.2差错检测和纠正引自：清华大学崔勇老师提供的讲稿典型纠错码—海明码目标：以奇偶校验为基础，如何找到出错位置，提供1位纠错能力理解海明码编码过程，以(15,11)海明码为例例如：11比特的数据0101100110111比特数据按顺序放入数据位校验位：2的幂次方位（记为p1,p2,p4,p8）每个校验位对数据位的子集做校验，缩小定位错误的范围问题：每个校验位如何计算？583.2差错检测和纠正校验位数据位右下角数字为码字中位序号10101100101123456789101112131415纠错码—海明码子集的选择与校验位计算海明码缺省为偶校验（也可以使用奇校验）593.2差错检测和纠正101011001011234567891011121314155个1p1=111010110010112345678910111213141510101100101123456789101112131415101011001011234567891011121314152个1p2=0010第1组第2组第3组第4组每组的数据位每组的校验位5个1p4=14个1p8=0纠错码—海明码码字的发送与接收如果发送过程中第7位出现差错，如何定位错误？603.2差错检测和纠正101100101100101123456789101112131415校验位数据位校验位数据位101100111010001101100100100101123456789101112131415发送方接收方纠错码—海明码定位错误与纠正组1和组2的校验结果可以定位错误所在的列613.2差错检测和纠正101001001011234567891011121314155个1有错误1101001001011234567891011121314151个1有错误0第1组第2组出错列234组1╳√╳组2√╳╳例如：组1和组2校验结果都指明存在错误，可定位错误位于第4列其他出错情况判断纠错码—海明码定位错误与纠正（续）组3和组4的校验结果可以定位错误所在的行623.2差错检测和纠正出错行234组3╳√╳组4√╳╳101001001011234567891011121314151010010010112345678910111213141510第3组第4组结论：错误位于第2行、第4列（位置7）5个1有错误4个1无错误例如：组3校验结果指明存在错误，组4校验结果指明无错误，可定位错误位于第2行其他出错情况判断纠错码—海明码定位错误与纠正（续）总体的定位错误列表633.2差错检测和纠正出错位123456789101112131415组1╳√╳√╳√╳√╳√╳√╳√╳组2√╳╳√√╳╳√√╳╳√√╳╳组3√√√╳╳╳╳√√√√╳╳╳╳组4√√√√√√√╳╳╳╳╳╳╳╳纠错码—海明码海明码纠正的实现过程每个码字到来前，接收方计数器清零接收方检查每个校验位k(k=1,2,4…)的奇偶值是否正确（每组运算）若pk奇偶值不对，计数器加k所有校验位检查完后，若计数器值为0，则码字有效；若计数器值为j，则第j位出错。例：若校验位p1、p2、p8出错，则第11位变反使用海明码纠正突发错误可采用k个码字（n=m+r）组成

kn矩阵，按列发送，接收方恢复成

kn矩阵kr个校验位，km个数据位，可纠正最多为k个的突发性连续比特错643.2差错检测和纠正

具有最简单流量控制的数据链路层协议在发送结点：

(1)从主机取一个数据帧。

(2)将数据帧送到数据链路层的发送缓存。

(3)将发送缓存中的数据帧发送出去。

(4)等待。

(5)若收到由接收结点发过来的信息，则从主机取一个新的数据帧，然后转到(2)。在接收结点：

(1)等待。

(2)若收到由发送结点发过来的数据帧，则将其放入数据链路层的接收缓存。

(3)将接收缓存中的数据帧上交主机。

(4)向发送结点发一信息，表示数据帧已经上交给主机。

(5)转到(1)。

两种情况的对比（传输均无差错）ABDATADATADATADATA送主机B送主机B送主机B送主机BABDATA送主机BDATA送主机B时间不需要流量控制需要流量控制

实用的停止等待协议时间ABDATA0送主机ACKDATA1送主机ACK(a)正常情况ABDATA0DATA0送主机ACK(c)数据帧丢失重传tout丢失！ABDATA0送主机ACKDATA0丢弃ACK(d)确认帧丢失重传tout丢失！ABDATA0NAKDATA0送主机ACK(b)数据帧出错重传出错四种情况无错信道上的停等式协议（1）不再假设接收方能够处理以无限高速进来的数据发送方以高于接收方能处理到达帧的速度发送帧，导致接收方被“淹没”(overwhelming)仍然假设通信信道不会出错（Error-Free）数据传输保持单向,但是需要双向传输链路（半双工物理信道）683.3基本的数据链路层协议无错信道上的停等式协议（2）停-等式协议（stop-and-wait）发送方发送一帧后暂停，等待确认（Acknowldgement）到达后发送下一帧接收方完成接收后，回复确认接收.确认帧的内容是不重要的：哑帧（dummyframe）69发送方接收方时间...数据帧哑帧确认等待确认3.3基本的数据链路层协议无错信道上的停等式协议（3）发送方完成一帧发送后等待确认到达确认到达后，发送下一帧70接收方完成一帧接收后交给物理层一个哑帧作为成功接收上一帧的确认3.3基本的数据链路层协议有错信道上的单工停等式协议（1）假设通信信道可能会出错，导致：帧在传输过程中可能会被损坏，接收方能够检测出来帧在传输过程中可能会丢失，永远不可能到达接收方一个简单的解决方案发送方增加一个计时器(timer)，如果经过一段时间没有收到确认，发送方将超时，于是再次发送该帧71发送方接收方时间丢失/出错超时重发启动计时器启动计时器接收3.3基本的数据链路层协议有错信道上的单工停等式协议（2）考虑一个特别场景A发送帧A1B收到了A1B生成确认ACKACK在传输中丢失A超时，重发A1B收到A1的另一个副本（并把它交给网络层）其他的场景另一个导致副本产生的场景是过长的延时(long

delay)72发送方A接收方B接收超时重发启动计时器启动计时器接收ACK丢失A1A1A1A13.3基本的数据链路层协议有错信道上的单工停等式协议（3）序号（SEQ：sequencenumber）接收方需要区分到达的帧是第一次发来的新帧让发送方在发送的帧的头部放一个序号，接收方可以检查它所收到的帧序号，由此判断这是个新帧还是应该被丢弃的重复帧。序号所需要的最小位数（bits）在这个协议中，唯一不明确的地方出现在当前帧（序号m）和它的直接后续帧（序号m+1）1

bit序号(0或1)就足以满足要求。自动重复请求，或带有重传的肯定确认ARQ(AutomaticRepeatreQuest)PAR(PositiveAcknowledgementwithRetransmission)73发送方接收方时间SEQ=0发送方接收方超时重发SEQ=0SEQ=0丢弃重复帧确认0丢失SEQ=1SEQ=0确认0确认1确认0确认0SEQ=1SEQ=0确认13.3基本的数据链路层协议有错信道上的单工停等式协议（4）74发送方初始化帧序号0，发送帧等待：正确的确认/错误的确认/超时正确确认：发送下一帧超时/错误确认：重发接收方初始化期待0号帧等待帧达到正确帧：交给网络层，并发送该帧确认错误帧：发送上一个成功接收帧的确认3.3基本的数据链路层协议有错信道上的单工停等式协议（5）效率的评估F=framesize(bits)

R=channelcapacity(Bandwidthinbits/second)I=propagationdelay+processorservicetime(second)

每帧发送时间(Timetotransmitasingleframe)=F/R总延迟(TotalDelay)=D=2I停止等待协议的发送工作时间是F/C，空闲时间是D当F<D时：信道利用率(lineutilization)=F/(F+R∙D)<50%753.3基本的数据链路层协议有错信道上的单工停等式协议（6）停止等待协议的效率问题停止等待协议的问题是只能有一个没有被确认的帧在发送中举例:长肥网络Shortframelength:1000bitframesHighbandwidth:1Mbpschannel(卫星信道)Longtransittime:270mspropagationdelay(传播延迟)763.3基本的数据链路层协议长肥网络(LFN，LongFatNetwork)：如果一个网络的带宽-延迟乘积(bandwidth-delayproduct)很明显的大于105bits(~12kB)，则可以被认为是长肥网络有错信道上的单工停等式协议（7）信道利用率很低：每一帧的发送时间是1毫秒(1000bits/(1,000,000bits/sec）).由于传播延迟较长，发送者在541毫秒之后才能收到确认，信道利用率1/541一种提高效率的方法：使用更大的帧可以使用更大的帧，但是帧的最大长度受到信道比特错误率（BER，Bit

Error

Ratio）的限制，帧越大，在传输中出错的概率越高，将导致更多的重传773.3基本的数据链路层协议本章内容3.1数据链路层的设计问题3.2差错检测和纠正3.3基本的数据链路层协议3.4滑动窗口协议3.5数据链路协议实例78停等协议的性能问题滑动窗口协议回退N协议选择重传协议停等协议的性能问题停止-等待机制降低了信道利用率设数据速率记为R，帧长度记为F，往返延迟记为D，则采用停-等协议的线路效率为：F/(F+R∙D)假如将链路看成是一根管道，数据是管道中流动的水，那么在传输延迟较长的信道上，停-等协议无法使数据充满管道，因而信道利用率很低解决办法流水线协议或管道协议：允许发送方在没收到确认前连续发送多个帧793.4滑动窗口协议滑动窗口协议—协议基本思想协议基本思想窗口机制发送方和接收方都具有一定容量的缓冲区（即窗口），发送端在收到确认之前可以发送多个帧问题发送端一次可以发送多少个帧?某个帧出错或丢失怎么处理？803.4滑动窗口协议滑动窗口协议—协议基本思想目的对可以连续发出的最多帧数（已发出但未确认的帧）作限制序号使用循环重复使用有限的帧序号流量控制：接收窗口驱动发送窗口的转动发送窗口：其大小记作WT，表示在收到对方确认的信息之前，可以连续发出的最多数据帧数接收窗口：其大小记作WR

，为可以连续接收的最多数据帧数累计确认：不必对收到的分组逐个发送确认，而是对按序到达的最后一个分组发送确认813.4滑动窗口协议滑动窗口协议—协议基本思想82序列号发送的最后帧序号发出一帧后窗口的下限前移一格收到确认后窗口的上限前移01234567012345670已发送的帧可发送帧已接收的帧最后确认的帧接收一帧后窗口的下限前移发出确认后窗口的上限前移可接收帧01234567012345670发送窗口与接收窗口(窗口大小7)3.4滑动窗口协议滑动窗口协议—协议基本思想83发送窗口与接收窗口(窗口大小7)01234567S01234567R01234567②发送0,1,201234567③收到0,1,201234567④发ACK,n=301234567⑤收到ACK,n=301234567⑦收3,4,发ACK,n=501234567⑥发3,4,5①发送窗口初始化为7①接收窗口初始化为7滑动窗口协议—协议的实现分析84while(1){wait_for_event(&event);if(event==frame_arrival){from_physical_layer(&r);if(r.ack==next_frame_to_send){from_network_layer(&buffer);inc(next_frame_to_send);}}=buffer;s.seq=next_frame_to_send;s.ack=1-frame_expected;to_physical_layer(&s);start_timer(s.seq);}发送方（

WT=WR=1，序号空间0和1）初始化：ack_expected=frame_expected=next_frame_to_send=0从网络层接收分组，放入相应的缓冲区，构造帧，物理层发送，开启计时。等待确认帧到达，从物理层接收一个帧，判断确认号是否正确，正确则停止计时器，并从网络层接收新分组。发送新的帧，跳转至33.4滑动窗口协议滑动窗口协议—协议的实现分析85while(1){wait_for_event(&event);if(event==frame_arrival){from_physical_layer(&r);if(r.seq==frame_expected){to_network_layer(&);inc(frame_expected);}}=buffer;s.seq=next_frame_to_send;s.ack=1-frame_expected;to_physical_layer(&s);start_timer(s.seq);}接收方（

WT=WR=1，序号空间0和1）初始化：ack_expected=frame_expected=next_frame_to_send=0等待帧到达，从物理层接收一个帧，校验和计算，并判断收到的帧序号是否正确，正确则交给网络层处理，期待帧号增加。返回确认帧，跳转至2。3.4滑动窗口协议回退N协议—协议设计思想出错全部重发当接收端收到一个出错帧或乱序帧时，丢弃所有的后继帧，并且不为这些帧发送确认发送端超时后，重传所有未被确认的帧适用场景该策略对应接收窗口为1的情况，即只能按顺序接收帧优缺点优点：连续发送提高了信道利用率缺点：按序接收，出错后即便有正确帧到达也丢弃重传863.4滑动窗口协议回退N协议—协议原理分析基本原理当发送方发送了N个帧后，若发现该N帧的前一个帧在计时器超时后仍未返回其确认信息，则该帧被判为出错或丢失，此时发送方就重新发送出错帧及其后的N帧。滑动窗口长度出错全部重发时，若帧序号为n位，接收窗口WR=1，发送窗口WT≤2n－1873.4滑动窗口协议回退N协议—协议原理分析正常情况下的GBN88在回退N步协议中，允许发送方发送多个分组而不用等待确认正常情况下，发送、接收窗口会随着帧的确认状态随包右移回退N协议—协议原理分析发送过程中数据包丢失89当发送过程中的2号包发生丢失时：发送方没有收到接收方的ACK2，于是后面发送的ACK3,ACK4全部变成了ACK1，代表接收方因为丢失了分组2，所以分组3和分组4都被丢弃，全部返回ACK1经过一段时间后，定时器确认超时没有收到ACK3,ACK4，所以发送方将重新发送。回退N协议—协议原理分析接收方返回的ACK丢失90假设ACK2发生了丢失时：如果接收方没有收到分组2，则后面返回的都是ACK1，因为本次返回的为ACK3,ACK4，所以发送方可以判断接收方已经接收到消息，不再进行重复发送。回退N协议—协议的实现分析91实现要点必须增加序号范围、发送方需要缓存多个分组两个窗口发送窗口：发送方维持一组连续允许发送的帧序号接收窗口：接收方维持一组连续的允许接收帧序号发送方必须响应的三件事上层的调用：检测有没有可以使用的序号，如果有就发送收到ACK：对n号帧的确认采用累积确认的方式超时事件：如果出现超时，就重传所有已发送未确认的分组3.4滑动窗口协议回退N协议—协议的实现分析92发送方：窗口尺寸：1<WT≤2n-1，最多连续发送窗口中的WT个PDU窗口滑动：收到期望的ACK(k)：窗口底部移到PDU(k)，窗口顶部向前移动，始终保持窗口里有WT个PDU未确认。窗口滑动后，发送新进入窗口的PDU超时重发：超过T未收到期望的ACK，重发窗口中的PDU（回退整个窗口）超次数失败：超过最大重发次数Nmax仍无正确应答3.4滑动窗口协议回退N协议—协议的实现分析93接收方：窗口尺寸：WR=1按序接收：按照PDU编号依序接收，出错、乱序PDU一律丢弃确认含义：ACK(k)表示对k-1及以前各编号的PDU的确认，同时期望接收第k号PDU确认策略：按序到达的PDU可立即确认，也可延迟确认(收到多帧后一起确认)，但出错或乱序的PDU，确认ACK(k)（期望接收k号PDU）或不应答3.4滑动窗口协议回退N协议—协议的实现分析94实现基本过程如下：初始化。ack_expected=0(此时处于发送窗口的下沿)；next_frame_to_send=0，frame_expected=0(初始化正在发送的帧和期待的帧序号)；nbuffered=0(进行发送大小初始化)等待事件发生（网络层准备好，帧到达，收到坏帧，超时）如果事件为网络层准备好，则执行以下步骤。从网络层接收一个分组，放入相应的缓冲区；发送窗口大小加1；使用缓冲区中的数据分组、next_frame_to_send和frame_expected构造帧，继续发送；next_frame_to_send加1；跳转（7）3.4滑动窗口协议while(1){wait_for_event(&event);switch(event){casenetwork_layer_ready:from_network_layer(&buffer[next_frame_to_send]);nbuffered=nbuffered+1;send_data(next_frame_to_send,frame_expected,buffer);inc(next_frame_to_send);break;

回退N协议—协议的实现分析95如果事件为帧到达，则从物理层接收一个帧，则执行以下步骤。首先检查帧的seq域，若正是期待接收的帧（seq=frame_expected），将帧中携带的分组交给网络层，frame_expected加1；然后检查帧的ack域，若ack落于发送窗口内，表明该序号及其之前所有序号的帧均已正确收到，因此终止这些帧的计时器，修改发送窗口大小及发送窗口下沿值将这些帧去掉，继续执行步骤（7）3.4滑动窗口协议caseframe_arrival:from_physical_layer(&r);if(r.seq==frame_expected){to_network_layer(&);inc(frame_expected);}while(between(ack_expected,r.ack,net_frame_to_send)){nbuffered=nbuffered-1;stop_timer(ack_expected);inc(ack_expected);}break;回退N协议—协议的实现分析96如果事件是收到坏帧，继续执行步骤（7）如果事件是超时。使next_frame_to_send=ack_expected，从发生超时的帧开始重发发送窗口内的所有帧，然后继续执行步骤（7）若发送窗口大小小于所允许的最大值（MAX-SEQ），则可继续允许网络层发送，否则则暂停网络层发送3.4滑动窗口协议casecksum_err:；break;casetimeout:next_frame_to_send=ack_expected;for(i=1;i<=nbuffered;i++){send_data(next_frame_to_send,frame_expected,buffer);inc(next_frame_to_send);}}if(nbuffered<MAX_SEQ)enable_network_layer();elsedisable_network_layer();}选择重传协议—协议设计思想设计思想若发送方发出连续的若干帧后，收到对其中某一帧的否认帧，或某一帧的定时器超时，则只重传该出错帧或计时器超时的数据帧适用场景该策略对应接收窗口大于1的情况，即暂存接收窗口中序号在出错帧之后的数据帧优缺点优点：避免重传已正确传送的帧缺点：在接收端需要占用一定容量的缓存973.4滑动窗口协议选择重传协议—协议原理分析基本原理在发送过程中，如果一个数据帧计时器超时，就认为该帧丢失或者被破坏；接收端只把出错的的帧丢弃，其后面的数据帧保存在缓存中，并向发送端回复NAK；发送端接收到NAK时，只重传出错的帧如果落在窗口内的帧从未接受过，那么存储起来，等比它序列号小的所有帧都正确接收后，按次序交付给网络层接收端收到的数据包的顺序可能和发送的数据包顺序不一样，因此在数据包里必须含有顺序号来帮助接收端进行排序。滑动窗口长度发送窗口的尺寸：WT≤2n-1,发送窗口应等于或小于序号空间的一半983.4滑动窗口协议选择重传协议—协议原理分析正常情况下SR993.4滑动窗口协议同样，在选择重传协议中，也允许发送方发送多个分组而不用等待确认，与回退N步不同的是，接收窗口大小是大于1的正常情况下，发送、接收窗口会随着帧的确认状态随包右移选择重传协议—协议原理分析发送过程中发生丢包1003.4滑动窗口协议当发送过程中的2号包发生丢失时：与GNB不同的是，接收方在没有收到分组2的情况下，依然返回了ACK3,ACK4当ACK1返回以后，分组5，分组6就已经可以发送。然后在接收方，分组3456都已经被缓存，等待分组2的计时器超时后，分组2将重新发送。选择重传协议—协议原理分析确认过程发生丢包3.4滑动窗口协议当ACK2丢弃时：发送方的分组已经由0-4到了2-6,在最后2-6的窗口中。分组2会因为ACK2被丢失然后在计时器计时后重新发送一次。如果在接收过程中有丢失发生，选择重传SR的效率是不如回退N步GBN的101选择重传协议—协议实现分析102实现要点在SR中，和GBN不同，SR是给每一个PDU设置定时器，发送端只重传出错PDU。接收端在接收到乱序的PDU的时候会进行缓存，当前面的PDU到达以后一起提交给上层两个窗口发送窗口：发送方维持一组连续允许发送的帧序号接收窗口：接收方维持一组连续的允许接收帧序号发送方必须响应的三件事上层的调用：检测有没有可以使用的序号，如果有就发送收到ACK：如果收到的是最小序号的ACK，窗口滑动。如果收到其他序号的ACK，进行标记超时事件：每个PDU都有定时器，哪个超时重传哪个3.4滑动窗口协议选择重传协议—协议实现分析103发送方：窗口尺寸：1<WT≤2n-1，最多连续发送窗口中的WT个PDU窗口滑动：与回退N帧协议相同选择重发：收到NAK

(k)，重发PDU(k)超时重发：超过T未收到期望的ACK，重发当前超时未应答的PDU超次数失败：超过最大重发次数Nmax仍无正确应答，报告上层失败实现基本过程与回退N协议基本类似，其中3.4滑动窗口协议选择重传协议—协议实现分析104接收方：窗口尺寸：1<WR≤2n-1窗口滑动：窗口底部数据上交，窗口向前滑动一步窗口内接收：窗口内的PDU全部接收，存储出错的后续PDU，按序交付；窗口外的PDU一律丢弃确认策略：按序到达的PDU可立即确认，也可延迟确认(收到多帧后一起确认)ACK(k)；出错用否定性确认NAK(k)（期望重发k号PDU）3.4滑动窗口协议选择重传协议—协议实现分析105实现基本过程如下：1、初始化。ack_expected=0(此时处于发送窗口的下沿)；next_frame_to_send=0，frame_expected=0（初始化正在发送的帧和期待的帧序号）；nbuffere