计算机网络 直接连接网络

1、1第 3 章 直接连接的网络2教学提示教学目的教学目的n理解理解数据链路层数据链路层服务服务，掌握，掌握可靠数据传输可靠数据传输和和多路访问多路访问原理原理，熟练掌握熟练掌握各种链路层协议与设备各种链路层协议与设备重要知识点重要知识点n成帧成帧n差错检测差错检测n可靠数据传输可靠数据传输n多路访问技术多路访问技术学习方法学习方法n以基础性问题为中心展开学习以基础性问题为中心展开学习 MAC地址 CSMA/CD 以太网交换机 IEEE 802.113直连连接的网络中的机制和设备机制设备在其他层可用4What is a Link?4Communication MediumNetwork Adapt

2、er5数据链路层的基本概念 n链路(link)是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。n一条链路只是一条通路的一个组成部分。n数据链路(data link) 除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。n现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。n一般的适配器都包括了数据链路层和物理层这两层的功能。 6工作场景最简单网络：用某种传输媒体连接所有主机n涉及涉及数据链路层数据链路层技术技术n单段链路单段链路使用使用点到点点到点通信协议通信协议或广播或广播多路访问多路访问协议协议n为为大型

3、网络大型网络提供提供某某“一跳一跳”的低层通信的低层通信支撑支撑以太网无线局域网路由器IP网络通信网7第3章：内容提要3.1 3.2 成帧成帧3.3 差错检测和纠正技术差错检测和纠正技术3.4 可靠数据传输原理可靠数据传输原理3.5 多路访问协议多路访问协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结8链路层环境n链路层协议链路层协议n任务：任务：通过通过单段链路单段链路，点到点点到点传送上层数据报传送上层数据报n定义了定义了链路两端结点间交互的链路两端结点间交互的帧格式帧格式，以及以及发送和接发送和接收帧时收帧时的的操作操作n两

4、种网络链路类型两种网络链路类型n点对点链路点对点链路n广播链路广播链路9n点对点链路：由链路一端的单个发送结点和链路另一端的单个接收结点组成。这种链路使用一对一的点对点通信方式。n广播链路：能够让多个发送结点和接收结点都连接到单一的，共享的广播信道上。这种链路使用一对多的广播通信方式。因广播链路上连接的主机很多，必须使用专用的共享链路协议来协调这些主机的数据发送。10链路层环境n链路层环境重要特点链路层环境重要特点n一条路径上的一条路径上的不同链路可不同链路可运行运行不同不同的的链路层协议链路层协议n链路层协议提供的服务可链路层协议提供的服务可以以不同不同n通信环境较为简单通信环境较为简单11

5、利用不同交通工具旅游的例子北京杭州黄山首都机场杭州机场黄山火车站12 链路层的基本服务就是将网络层分组通过链路层的基本服务就是将网络层分组通过单段通信链路单段通信链路从一个结点移动到相邻结点。从一个结点移动到相邻结点。 且其所提供的且其所提供的服务服务会随着链路层协议转变会随着链路层协议转变而改变。而改变。13链路层协议的设计问题1.成帧成帧n将数据报封装进帧，加上首部和尾部，帧定界问题将数据报封装进帧，加上首部和尾部，帧定界问题2.媒体访问媒体访问n规定了结点在链路上传输帧的规则规定了结点在链路上传输帧的规则n如何共享媒体，如何访问信道？如何共享媒体，如何访问信道？n用媒体访问控制用媒体访问

6、控制(MAC)协议协调结点之间的帧传输协议协调结点之间的帧传输 3.相连结点间的可靠交付相连结点间的可靠交付n是网络中基础性问题（无差错的传输每个帧）是网络中基础性问题（无差错的传输每个帧）n在比特差错低的链路很少使用在比特差错低的链路很少使用 (光纤，双绞线光纤，双绞线)n无线链路无线链路: 高差错率则需要高差错率则需要14链路层服务的设计问题(续)4.流量控制流量控制n相邻发送和接收结点间的步调协调（防止接收结点相邻发送和接收结点间的步调协调（防止接收结点缓冲区溢出）缓冲区溢出）5.差错检测差错检测n差错由信号衰减、噪声所致差错由信号衰减、噪声所致n接收方检测出差错，将帧丢弃接收方检测出差

7、错，将帧丢弃n发送方负责重传发送方负责重传n通常用硬件实现通常用硬件实现6.纠错纠错n接收方接收方识别和纠正识别和纠正比特差错，而不采取重传比特差错，而不采取重传15网络适配器及其与协议栈功能的关系问题：链路层功能在哪里？n网络适配器n设备驱动程序16n网络适配器也成为网络接口卡或网卡。n网络适配器通常与系统的I/O总线相连，在结点内存和网络链路之间传输数据。n结点上运行的一个软件模块称为设备驱动程序，用来管理网络适配器。n链路层功能的主体部分是在网络适配器中实现的（链路层控制器）。1718第3章：内容提要3.1 3.2 成帧成帧3.3 差错检测和纠正技术差错检测和纠正技术3.4 可靠数据传输

8、原理可靠数据传输原理3.5 多路访问协议多路访问协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结19IP 数据报1010 0110帧取出数据链路层网络层链路结点 A结点 B物理层数据链路层结点 A结点 B帧(a)(b)发送帧接收链路IP 数据报1010 0110帧装入数据链路层传送的是帧20n在分组交换网络中，结点交换的是数据块而不是比特流。n结点的网络适配器通过链路层协议在结点之间交换帧（一个比特序列）。n为了完成帧在结点之间的传输，适配器首先要准确识别这个比特序列具有什么样的帧结构，即决定帧从哪里开始到哪里结束。21面向比特的

9、协议n面向比特的协议把帧看成比特的集合面向比特的协议把帧看成比特的集合n以以HDLC协议为例，用特别的比特序列表示帧的协议为例，用特别的比特序列表示帧的开始和结束（开始和结束（01111110）n比特填充比特填充 (bit stuffing)法法(用于发送前用于发送前/接收后接收后)n发送方：报文中发送方：报文中5个连续个连续1，插入，插入0n接收方接收方：收到：收到5个连续个连续1：后为后为0 ，去掉；，去掉；为为1，后，后为为0，则帧结束；否则则帧结束；否则出错出错22PPP协议n点对点协议点对点协议(PPP) n家庭家庭主机到第一跳路由器的主机到第一跳路由器的点对点链路的链路层协议点对点

10、链路的链路层协议n用户使用拨号电话线接入因特网时，一般都是使用用户使用拨号电话线接入因特网时，一般都是使用 PPP 协议。协议。nPPP协议是家庭用户的计算机和协议是家庭用户的计算机和ISP进行通信时所使用的进行通信时所使用的数据链路层协议。数据链路层协议。23用户到 ISP 的链路使用 PPP 协议用户至因特网已向因特网管理机构申请到一批 IP 地址ISP接入网PPP 协议24PPP 协议的帧格式协议代码25PPP 协议的帧格式nPPP 有一个 2 个字节的协议字段。n当协议字段为 0 x0021 时，PPP 帧的信息字段就是IP 数据报。n若为 0 xC021, 则信息字段是 PPP 链路

11、控制数据。n若为 0 x8021，则表示这是网络控制数据。 IP 数据报1211字节12不超过 1500 字节PPP 帧先发送7EFF03FACFCSF7E协议信 息 部 分首部尾部26面向字节的协议n早期每帧都看成是字节的集合n保留一组字符为控制字符n同步字符同步字符SYN；首部开始符首部开始符SOH；正文开始符正文开始符STX；正正文结束符文结束符ETX；转义字符转义字符DLEn效率较低，目前已很少使用nDLE字符的“转义”作用n信息信息DLE STX A DLE B DLE ETX在网络中传送在网络中传送27第3章：内容提要3.1 链路层概述3.2 成帧3.3 奇偶校验奇偶校验检验和方法

12、检验和方法循环冗余检测循环冗余检测(CRC)3.4 可靠数据传输原理可靠数据传输原理3.5 多路访问协议多路访问协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结28n为了保证数据的可靠传输，在数据传输出现错误后，有两种处理方法，一是检错重发；二是前向纠错。 29处理帧差错两种方法n检错检错重重发发(detect and retransmission)n检测到发送方报文受损，检测到发送方报文受损，则通知发送方重传副本则通知发送方重传副本n差错率低差错率低效果好效果好n前向纠错前向纠错(Forward Error Correction

13、, FEC)n纠错通过纠错通过“预先预先”发送发送额额外信息进行外信息进行n时效性好时效性好n适用场合适用场合n检错重检错重发发适合链路差错适合链路差错率很低的场合率很低的场合，如有线，如有线通信通信n前向纠错适合对时间要前向纠错适合对时间要求很高求很高的场合，的场合，如航天如航天和实时控制和实时控制30 为此，首先要检查出误码。这样就需要在传输数据时加上能够检查出错误或能够定位错误的冗余信息。n冗余信息用某种明确定义的算法直接从原始报文中导出的信息。31差错检测EDC：差错检测和纠错比特：差错检测和纠错比特 (冗余冗余)D ： 数据由差错校验保护，可能包括首部字段数据由差错校验保护，可能包括

14、首部字段 易出现比特错链路易出现比特错链路 32n差错检测不是差错检测不是100%可靠可靠!n 协议可能漏掉某些差错，但是非常少协议可能漏掉某些差错，但是非常少n 较大的较大的EDC字段产生更好的检测和纠正字段产生更好的检测和纠正n一种优秀的差错检测方法应当满足：加入的冗余一种优秀的差错检测方法应当满足：加入的冗余信息较少，而能检测出所有的差错。信息较少，而能检测出所有的差错。 33差错检测方法n奇偶校验n检验和方法n循环冗余检验34奇偶校验奇偶校验码是奇偶校验码是奇校验码奇校验码和和偶校验码偶校验码的统称，是一种的统称，是一种最基本的检错码。最基本的检错码。n用用单个奇偶校验位单个奇偶校验位

15、可检测出链路发生的可检测出链路发生的单个比特差错。单个比特差错。n发送方发送的信息由发送方发送的信息由n-1n-1位位信息元和信息元和1 1位位校验元组成，可校验元组成，可以表示成为（以表示成为（n n，n-1n-1）。）。n如果是如果是奇校验码奇校验码，在附加上一个校验元以后，码长为，在附加上一个校验元以后，码长为n n的的码字中码字中“1”1”的个数为的个数为奇数奇数个；个；n如果是如果是偶校验码偶校验码，在附加上一个校验元以后，码长为，在附加上一个校验元以后，码长为n n的的码字中码字中“1”1”的个数为的个数为偶数偶数个。个。 例： 信息字段 奇校验码 偶校验码 0110001 011

16、00010 01100011编码效率： Q/(Q+1) (信息字段占Q个比特)35奇偶校验二维比特奇偶校验二维比特奇偶校验:检测到所有检测到所有1,2,3个比特差错和大部分个比特差错和大部分4bit差错和纠正差错和纠正1个比特差错。个比特差错。00奇偶差错奇偶差错可纠正的单比特可纠正的单比特差错差错无差错36检验和方法n检验和方法（可用于因特网网络层）n思想：将传输的所有字节当做整数加起来，其和作为检验和，然后将这个检验和连同数据传输到接收方，接收方对收到的数据执行相同的计算，再把得到的结果与收到的检验和进行比较。n因特网检验和就基于这种方法。37因特网检验和发送方:n将段内容作为16比特整数

17、序列来处理n检验和: 连续两两求和，校验和为和的反码n发送方将检验和的值放入 检验和字段接收方:n计算接收到段的检验和n检查是否计算的检验和等于 检验和字段的值:nNO 检测到差错检测到差错nYES 没有检测到差错，仍可能没有检测到差错，仍可能有错有错目标：目标：检测检测传输段传输段中的中的“差错差错”(如比特翻转如比特翻转)38因特网检验和例子n注意：当作加法时，最高位进比特位的进位需要加到结果中n例子： 3个16 bit的整数1100011001100110，1111010101010101，1000111100001100相加1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1

18、 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 11 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 11 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 0 0 0 1 1 0 01 0 1 0 0 1 0 1 0 1 1 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 0 1 0 0 11 1 0 1 1 0 1 0 1 0 0 1 1 0 1 1 0回卷 和检查和(求反)和回卷 39因特网检验和检错效果 对不同的报文，容易找到具有相同检验和的另一段对不同的报文，容易找到具有相同检验和的另

19、一段报文报文:I O U 10 0 . 99 B O B49 4F 55 3130 30 2E 3939 42 D2 42messageASCII formatB2 C1 D2 ACI O U 90 0 . 19 B O B49 4F 55 3930 30 2E 3139 42 D2 42messageASCII formatB2 C1 D2 AC不同的报文不同的报文但相同的检验和但相同的检验和!效果不好! 报文 报文 ASCII形式 ASCII形式 40循环冗余检验循环冗余检验 为了提供很强的差错检测能力，现代计算机网络普遍在链路层用硬件芯片实现了基于循环冗余检验（CRCCyclic Red

20、undancy Check）编码的差错检验技术。 41循环冗余检验的原理 n假设待传送的数据 M = 1010001101（共k bit）。n发送方和接收方协商一个m bit的除数Pn即可确定我们在数据M的后面添加的供差错检测用冗余码的长度为n bit（n=m-1）。 42冗余码的计算 n用二进制的模 2 运算进行 2n 乘 M 的运算，这相当于在 M 后面添加 n 个 0。n得到的 (k + n) bit 的数除以事先选定好的长度为 m bit 的数 P，得出商是 Q 而余数是 R（即为所求的冗余码），所得余数 R 比除数 P 至少要少1 个比特。 43n设 M = 1010001101 ,

21、 P = 110101，即 n = 5, 模 2 运算的结果是：商 Q = 1101010110， 余数R = 01110。n将余数 R 作为冗余码添加在数据 M 的后面发送出去，即发送的数据是101000110101110，或 2nM + R。44 1101010110 Q 商 除数 P 110101 101000110100000 2nM 被除数 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110 R 余数45n接收方如何检测呢？接收方如何检测呢？n用接收端收到得数据除以用接收

22、端收到得数据除以P（发送端事先定好的那个）n如果所得余数为0，则在传输过程中没有产生误码；n如果所得余数不为0，则在传输过程中产生了误码；46n但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。n一旦检测出差错，就丢弃这个出现差错的帧。注意：能不能说所得余数为0，就肯定没有出现差错？ 只要经过严格的挑选，并使用位数足够多的除数 P，那么出现检测不到的差错的概率就很小很小。 检测出错了？检测出错了？47 任何一个由二进制数位串组成的代码可以和一个只含有0和1两个系数的多项式建立一一对应的关系。 例如，代码1010111对应的多项式为X6+X4+X2+X+1，而多项式X5+X3+X2十X

23、十1对应的代码为101111。48目前，广泛使用的除数P主要有四种: nCRC12X12十X11十X3十X2+1 nCRC16X16十X15十X2十1(IBM公司) nCRC16X16十X12十X5十1(CCITT) nCRC32X32十X26十X23十X22十X16十X11十X10十X8十X7十X5十X4十X2+X+1 49应当注意 n仅用循环冗余检验 CRC 差错检测技术只能做到无差错接受(accept)。n“无差错接受”是指：“凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于 1 的概率认为这些帧在传输过程中没有产生差错”。n也就是说：“凡是接收端数据链路层接受的帧都没有差错”（有

24、差错的帧就丢弃而不接受）。n传输差错可分为两大类：帧出现比特差差错；帧丢失、帧重复和帧失序。n“可靠传输”（即发送什么就收到什么）就必须再加上帧编号、确认和重传机制。 50第3章：内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 设计可靠数据传输协议设计可靠数据传输协议流水线可靠数据传输协议流水线可靠数据传输协议回退回退N步协议步协议选择重传协议选择重传协议3.5 多路访问协议多路访问协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结51可靠数据传输：服务模型与服务实现n可靠数据传输是互联网中最为重要的问题之一

25、n该问题在多层协议中出现n一般服务模型52设计可靠数据传输协议n基本思想：在分组传输过程进行差错检测，一旦接收方发现差错，就应当告知发送方，由发送方重传该分组n学习方法：研究一系列协议，一步解决一个问题，直至实用53设计可靠数据传输协议：SW0协议前提条件：信道不丢包n解决方案：n接到正确接到正确PKT，发送一，发送一个肯定确认个肯定确认(ACK)n收到收到错误错误PKT，发送一，发送一个个否定确认否定确认(NAK)，重重传原传原PKTn停止等待停止等待(stop-and-wait, SW)协议n实用中有不少漏洞54设计可靠数据传输协议：SW1协议条件：信道丢包nSW0的发送方会一直等待ACK

26、，引起协议死锁死锁n解决方案：n增加增加超时定时器超时定时器n每发PKT，启动超时定时器，称为超时重传超时重传机制n重传时间略大于平均RTTn无需NAK（否认确认）55设计可靠数据传输协议：SW2协议条件：确认分组丢失n出现了分组冗余冗余的差错n解决方案：n增加一种新机制：增加一种新机制：发送发送序号序号n序号空间要较小n如发送序号如发送序号3 bit，在在07间循环使用间循环使用56设计可靠数据传输协议：SW3协议对确认进行编号？n收到重复的确认，无法分辨对应哪个分组n解决方案：n增加增加确认序号机制确认序号机制，分分辨出确认辨出确认对应对应哪个分组哪个分组n综合以上机制为综合以上机制为SW

27、协议，协议，或或自动重传请求自动重传请求(ARQ)设计可靠数据传输协议机制设计可靠数据传输协议机制：差错检测、接收方确认差错检测、接收方确认(肯定/否定)、重、重传、定时器和序号传、定时器和序号(数据和确认)57第3章：内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 设计可靠数据传输协议设计可靠数据传输协议流水线可靠数据传输协议流水线可靠数据传输协议回退回退N步协议步协议选择重传协议选择重传协议3.5 多路访问协议多路访问协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结58流水线协议n2.5Gbps光传输系

28、统，RTT为35ms。分组长L1,500 byte，发送时延n信道的利用率n改进停止等待协议，提高传输效率sbpspktbitRLttrans8.4105.2/815009000137.00048.350048.0/RLRTTRLU59流水线: 提高协议利用率60n可连续发送若干个分组，提高信道利用率n实际的协议一次至少允许连续发送256个分组，协议效率至少提高256倍!n看似n个分组被填充到一条流水线上，故此技术被称为流水线61流水线传输 n流水线:发送方允许发送多个、传输中、未应答的分组，不必每发完一个分组就停顿下来等待对方的确认。n由于信道上一直有数据不间断地传送，这种传输方式可获得很高

29、的信道利用率。 B分组ttAACK62流水线协议n必须增加序号范围必须增加序号范围n发送方和发送方和/或接收方设有缓冲或接收方设有缓冲n两种流水线协议: 回退回退N步（步（go-Back-N）, 选择性重传（选择性重传（S-R） 63第3章：内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 设计可靠数据传输协议设计可靠数据传输协议流水线可靠数据传输协议流水线可靠数据传输协议回退回退N步协议步协议选择重传协议选择重传协议3.5 多路访问协议多路访问协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结64如何处理流水

30、线差错？n使用流水线技术传输分组时，若出现接收方或网络来不及处理这些分组情况，就会导致丢包。n当流水线差错时，对所需序号窗口和缓冲的要求取决于数据传输协议处理丢失、损坏及时延过大分组的方式n恢复流水线差错的两种基本方法n回退回退N步步(Go-Back-N，GBN)n选择重传选择重传(Selective Repeat, SR)65nGBN协议在流水线传输的基础上。通过发送窗口机制来限制发送方连续发送分组的个数。回退N步协议(Go-Back-N)66回退N步协议(Go-Back-N)发送方发送方:n在分组首部需要K比特序号，2k=N（序号循环使用）n“窗口”最大为N, 允许连续发送N个没有应答分组

31、滑动窗口滑动窗口(流水线流水线)已确认已发送但未确认可用但未发送不可用窗口长度N发送基序号 下一个序号 67发送窗口机制 123456789101112(a) 发送方维持发送窗口（发送窗口是 5）发送窗口(b) 收到对第一个分组的确认后发送窗口向前滑动向前123456789101112发送窗口位于发送窗口的中的分组可位于发送窗口的中的分组可以连续发送出去，而不需要以连续发送出去，而不需要等待对方的确认信息等待对方的确认信息68GBN协议注意点n接收方按序根据滑动窗口的序号接收分组nGBN协议的接收窗口的长度为1n窗口中失序的分组将被丢弃（接收方除了丢弃失序分组外，还要对最近按序接收的分组进行确

32、认）n发送方采用超时机制来重传出现丢失会差错的分组n接收方可采用累积确认的方式69GBN协议例子n发送窗口为3，序号范围为0，370第3章：内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 设计可靠数据传输协议设计可靠数据传输协议流水线可靠数据传输协议流水线可靠数据传输协议回退回退N步协议步协议选择重传协议选择重传协议3.5 多路访问协议多路访问协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结71选择性重传(Selective Repeat)问题：GBN是否还能够改善？(单一差错可能导致大量不必要重传)n接收

33、方可分别确认所有正确接收的报文段n缓存失序分组缓存失序分组, 以便最后按序交付给上层以便最后按序交付给上层n发送方只需要重传没有收到ACK的分组n发送方定时器对每个分组计时发送方定时器对每个分组计时n发送窗口nN个连续的序号个连续的序号n也需要限制已发送但尚未应答分组的序号也需要限制已发送但尚未应答分组的序号72选择性重传: 发送方/接收方窗口a. 发送方看到的序号b. 接收方看到的序号已经确认可用，还未发送发送，还未确认不可用可接受（窗口内） 失序(已缓存)但已被确认期待，还未收到不可用 窗口长度N窗口长度N发送基序号接收基序号下一个序号 73选择性重传算法上层传来数据上层传来数据 :r如果

34、窗口中下一个序号可用如果窗口中下一个序号可用, 发送报文段发送报文段timeout(n):r重传丢失分组重传丢失分组n, 重启其计时重启其计时器器ACK(n) 在在发送基,发送基+N:r标记分组标记分组 n 已经收到已经收到r如果如果n 是最小未收到应答的是最小未收到应答的分组，向前滑动窗口基指针分组，向前滑动窗口基指针到下一个未确认序号到下一个未确认序号发送方发送方分组分组n在在 接收基接收基,接收基接收基+N-1r发送发送 ACK(n)r失序失序: 缓存缓存r按序按序: 交付交付 (也交付所有缓存也交付所有缓存的按序分组的按序分组),向前滑动窗口到向前滑动窗口到下一个未收到报文段的序号下一

35、个未收到报文段的序号分组分组n在在接收基接收基-N,接收基接收基-1rACK(n)其他其他: r忽略接收到的分组忽略接收到的分组 接收方接收方74选择重传的例子75SR: 窗口长度问题（序号空间有限时）例子:n序号: 0, 1, 2, 3n窗口长度 = 3n接收方：在(a)和(b)两种情况下，接收方没有发现两者间的差别!n在 (a)和(b)接收方无法区分接收到的分组是重传的还是新的。问题: 序号长度与窗口长度有什么关系?回答：窗口长度小于等于序号空间的一半76可靠数据传输机制及用途小结机制机制用途和说明用途和说明检验和检验和用于检测在一个传输分组中的用于检测在一个传输分组中的比特比特错误。错误

36、。定时器定时器用于超时用于超时/重传一个分组，可能因为该分组（或其重传一个分组，可能因为该分组（或其ACK）在信道中丢失了。）在信道中丢失了。由于当一个分组被时延但未丢失（过早超时），或当一个分组已被接由于当一个分组被时延但未丢失（过早超时），或当一个分组已被接收方收到但从接收方到发送方的收方收到但从接收方到发送方的ACK丢失时，可能产生超时事件，所丢失时，可能产生超时事件，所以接收方可能会收到一个分组的多个冗余拷贝。以接收方可能会收到一个分组的多个冗余拷贝。序号序号用于为从发送方流向接收方的数据分组按顺序编号。所接收分组的序号用于为从发送方流向接收方的数据分组按顺序编号。所接收分组的序号间的

37、空隙可使该接收方检测出丢失的分组。具有相同序号的分组可使间的空隙可使该接收方检测出丢失的分组。具有相同序号的分组可使接收方检测出一个分组的冗余拷贝。接收方检测出一个分组的冗余拷贝。确认确认接收方用于告诉发送方一个分组或一组分组已被正确地接收到了。确认接收方用于告诉发送方一个分组或一组分组已被正确地接收到了。确认报文通常携带着被确认的分组或多个分组的序号。确认可以是逐个的报文通常携带着被确认的分组或多个分组的序号。确认可以是逐个的或累积的，这取决于协议。或累积的，这取决于协议。否定确认否定确认接收方用于告诉发送方某个分组未被正确地接收。否定确认报文通常携接收方用于告诉发送方某个分组未被正确地接收

38、。否定确认报文通常携带着未被正确接收的分组的序号。带着未被正确接收的分组的序号。窗口、流水线窗口、流水线发送方也许被限制仅发送那些序号落在一个指定范围内的分组。通过允发送方也许被限制仅发送那些序号落在一个指定范围内的分组。通过允许一次发送多个分组但未被确认，发送方的利用率可在停等操作模式许一次发送多个分组但未被确认，发送方的利用率可在停等操作模式的基础上得到增加。窗口长度可根据接收方接收和缓存报文的能力或的基础上得到增加。窗口长度可根据接收方接收和缓存报文的能力或网络中的拥塞程度，或两者情况来进行设置。网络中的拥塞程度，或两者情况来进行设置。77第3章：内容提要3.1 链路层概述3.2 成帧3

39、.3 差错检测和纠正技术3.4 可靠数据传输原理3.5 信道划分协议信道划分协议轮流协议轮流协议随机接入协议随机接入协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结78多路访问(multiple access)链路和协议多路访问多路访问n多个发送/接收结点同时使用广播信道，如何协调它们共享一个信道n局域网局域网环境，密集端系统通常使用多路访问方式应用场景：应用场景：信道资源紧缺，大量端系统信道资源紧缺，大量端系统或者频繁或者频繁访问网络，或者访问网络，或者以较小概率访问网络以较小概率访问网络79多路访问协议：n共享单一广播信道n两

40、个或更多结点并行传输相互干扰n碰撞：碰撞：如果结点同时接收到两个或更多信号如果结点同时接收到两个或更多信号多路访问协议n决定结点怎样共享信道的分布式算法，如：决定何时结点能够传输？出现碰撞时如何解决？n共享信道的通信必须使用信道本身! n不能用带外信道来协调不能用带外信道来协调80理想的多路访问协议速率R bps的广播信道1. 当只有一个结点时，能够以速率R发送2. 当有M个结点时，每个能以平均速率R/M发送3. 分布式:n无特殊结点来协调传输无特殊结点来协调传输n无同步时钟、时隙无同步时钟、时隙4. 简单81多路访问协议: 分类有3种类型:n信道划分n将信道划分为较小的将信道划分为较小的“段

41、段” (时隙，频率，编码时隙，频率，编码)n为每个结点分配一部分专用为每个结点分配一部分专用n轮流n结点轮流，信息较多的轮流发送的时间较长结点轮流，信息较多的轮流发送的时间较长n随机访问n不划分信道，允许碰撞不划分信道，允许碰撞n设法从设法从“碰撞碰撞”恢复恢复问题：问题：协议应用协议应用场景不同场景不同，设计，设计协议的协议的方法方法是否有所不同？是否有所不同？82信道划分协议: TDMATDMA: 时分多路访问 n“循环”访问信道n每个站点在每个循环中获得固定长度时隙(长度=分组传输时间)n不使用的时隙则空闲n例子：6个站点的LAN, 时隙1、3、4 有分组, 时隙2、5、6 空闲(浪费)

42、83信道划分协议: FDMAFDMA: 频分多路访问 n信道频谱划分为频带n每个站点分配固定的频带n频带中未使用的传输时间空闲n例子： 6个站点的LAN, 频带1、3、4 有分组, 频带2、5、6 空闲(浪费)84FDM和TDM特点n消除了碰撞且公平n结点在每个帧时间内得到了专用的传输速率结点在每个帧时间内得到了专用的传输速率R/N bpsn若系统仅有少数几个有大量分组要发送的结点n分配的频率或时隙被浪费分配的频率或时隙被浪费n适合场合n所有结点都持续有大量数据发送所有结点都持续有大量数据发送nCDMA是另一种信道划分协议n2.3.2节85第3章：内容提要3.1 链路层概述3.2 成帧3.3

43、差错检测和纠正技术3.4 可靠数据传输原理3.5 信道划分协议轮流协议轮流协议随机接入协议随机接入协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结86两种轮流协议轮询(有中心): n主结点“邀请”从结点依次传输n关注问题:n轮询开销n时延n单点故障(主结点)令牌传递令牌传递(无中心无中心):控制令牌从一个结点顺序地传控制令牌从一个结点顺序地传递到下一个递到下一个令牌报文令牌报文关注问题关注问题: 令牌开销令牌开销 时延时延单点故障单点故障(令牌消失令牌消失) 适用于适用于希望共享信道但希望共享信道但却无法预测访问结点的却无法预测访

44、问结点的数量的场景数量的场景87第3章：内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 可靠数据传输原理3.5 信道划分协议轮流协议随机接入协议随机接入协议3.6 以太网以太网3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结88随机访问协议n大量结点大量结点以小概率以小概率发送分组发送分组n以信道全部速率以信道全部速率R传输传输n结点间无优先权协调结点间无优先权协调n两个或更多传输结点发送两个或更多传输结点发送 “碰撞碰撞”(小概率小概率)n随机访问协议随机访问协议定义了定义了: n如何检测碰撞如何检测碰撞n如何从碰撞中恢复如何从

45、碰撞中恢复 (例如，经延迟后重新传输例如，经延迟后重新传输)n随机访问协议的实例随机访问协议的实例:nALOHAn时隙时隙ALOHAnCSMA, CSMA/CD, CSMA/CA89ALOHA协议 一种用于解决在分组无线通信系统中分配广播信道的分布式方法假定n所有帧有相同长度n结点随时传输帧n结点是异步的n如果2+结点同时传输，所有结点检测碰撞操作n当结点获得新帧，将随时传输n无碰撞，结点能够继续发送新帧n如果碰撞，结点能够检测到，以概率P重传帧90时隙ALOHA特点n单个活跃结点能够连续地以信道的全速传输n结点中的时隙需要同步n简单n碰撞，浪费时隙n空闲时隙n结点能以小于传输分组的时间检测到

46、碰撞n节点时钟同步困难91在时隙在时隙ALOHA协议和纯协议和纯ALOHA协议中协议中,一个一个结点的成功传输取决于连接在这个广播信道结点的成功传输取决于连接在这个广播信道上的其他结点的活动。上的其他结点的活动。由于无线信道的特点，传输结点有时无法得由于无线信道的特点，传输结点有时无法得知其他结点的活动情况。知其他结点的活动情况。有线局域网中就不一样了。有线局域网中就不一样了。92CSMA(载波侦听多路访问)CSMA: 工作原理：发送前监听。每个站点在发送数据之前要监听信道上是否有数据在传送。若有，则此站不能发送，以免发生碰撞，需等待一段时间后重试。n人类类比： 不要打断他人说话! 避免两人同

47、时讲话!nCSMA用于有线，ALOHA用于无线93CSMA：载波监听多点访问载波监听策略：载波监听策略：非坚持非坚持CSMA：一旦监听到信道忙，就不再监听；延迟一：一旦监听到信道忙，就不再监听；延迟一个随机时间后再次监听。个随机时间后再次监听。坚持坚持CSMA：监听到信道忙时，仍继续监听，直到信道空：监听到信道忙时，仍继续监听，直到信道空闲。闲。 1-坚持坚持CSMA：一听到信道空闲就立即发送数据：一听到信道空闲就立即发送数据 p-坚持坚持CSMA：听到信道空闲时，以概率：听到信道空闲时，以概率p发送数据（发送数据（以概率以概率1-p延迟一段时间后再发送）延迟一段时间后再发送）94CSMA：载

48、波监听多点访问nCSMA技术能解决技术能解决发送时发送时出现的冲突现象出现的冲突现象n帧在发送过程中有可能出现帧在发送过程中有可能出现“碰撞碰撞”nCSMA技术不能解决技术不能解决发送中发送中出现的冲突现象出现的冲突现象 95问题： 既然发送前已经监听到信道空闲， 为什么发送时还要继续监听信道？96电磁波在总线上的有限传播速率的影响 n当某个站监听到总线是空闲时，也可能总线并非真正是空闲的。 nA 向 B 发出的信息，要经过一定的时间后才能传送到 B。nB 若在 A 发送的信息到达 B 之前发送自己的帧(因为这时 B 的载波监听检测不到 A 所发送的信息)，则必然要在某个时间和 A 发送的帧发

49、生碰撞。n碰撞的结果是两个帧都变得无用。 97CSMA碰撞碰撞碰撞:整个分组传输时间被浪费整个分组传输时间被浪费产生碰撞的分组变得无用产生碰撞的分组变得无用注意注意:距离与传播时延在决定碰撞概率中的作用距离与传播时延在决定碰撞概率中的作用98CSMA/CD (碰撞检测)CSMA/CD: 传送过程中也进行载波侦听传送过程中也进行载波侦听n在短时间内检测到碰撞在短时间内检测到碰撞n碰撞的传输尽快结束，以减少信道浪费碰撞的传输尽快结束，以减少信道浪费n碰撞检测碰撞检测: n在有线的在有线的LAN中容易中容易: 测量信号强度，比较传输的和接测量信号强度，比较传输的和接收的信号收的信号n在无线在无线LA

50、N中困难：碰撞可能听不到中困难：碰撞可能听不到n人类类比人类类比: 礼貌的交谈者礼貌的交谈者 问题：问题：能否进一步提高能否进一步提高CSMA效率效率？99CSMA/CD的基本工作原理工作原理：工作原理：每个站发送数据前每个站发送数据前先监听信道先监听信道是否是否空闲，若空闲则立即发送数据。在发送时，空闲，若空闲则立即发送数据。在发送时，边边发送边检测发送边检测。若检测到冲突，则立即停止发送。若检测到冲突，则立即停止发送。等待一段随机时间（称为退避）以后，再重新等待一段随机时间（称为退避）以后，再重新尝试。尝试。 CSMA/CD可归结为四句话：可归结为四句话： 发前先监听发前先监听 空闲即发送

51、空闲即发送 边发边检测边发边检测 冲突时退避冲突时退避1001 kmABt碰撞t = 2 A 检测到发生碰撞 t = B 发送数据B 检测到发生碰撞 t = t = 0单程端到端传播时延记为 1011 kmABt碰撞t = B 检测到信道空闲发送数据t = / 2发生碰撞t = 2 A 检测到发生碰撞 t = B 发送数据B 检测到发生碰撞 t = ABABAB t = 0 A 检测到信道空闲发送数据ABt = 0t = B 检测到发生碰撞停止发送STOPt = 2 A 检测到发生碰撞STOPAB单程端到端传播时延记为 102强化碰撞 n当发送数据的站一旦发现发生了碰撞时，除了立即停止发送数据

52、外，还要再继续发送若干比特的阻塞信号(jamming signal)，以便让所有用户都知道现在已经发生了碰撞。 103数据帧干扰信号 TJ阻塞信号 ABTBt B 发送数据A 检测到冲突开始冲突信道占用时间A 发送数据B 也能够检测到冲突，并立即停止发送数据帧，接着就发送干扰信号。这里为了简单起见，只画出 A 发送干扰信号的情况。104多路访问协议比较信道划分协议信道划分协议n在高负载时高效、公平地共享信道在高负载时高效、公平地共享信道n低负载时低效：信道访问中延时，当低负载时低效：信道访问中延时，当1个活跃结点时，个活跃结点时，甚至仅有分配了甚至仅有分配了 1/N 带宽带宽! 随机访问协议随

53、机访问协议n低负载是有效：单个结点能够全面利用信道低负载是有效：单个结点能够全面利用信道n高负载：碰撞开销大高负载：碰撞开销大轮流协议轮流协议兼有两方面的优点兼有两方面的优点!105多路访问协议小结问题：对共享媒体你需要做些什么问题：对共享媒体你需要做些什么?n信道划分信道划分, 通过时间、频率或编码通过时间、频率或编码n时分时分, 频分频分n轮流轮流n从中心站点轮询，令牌传递从中心站点轮询，令牌传递n随机划分随机划分 (动态的动态的), nALOHA, S-ALOHA, CSMA, CSMA/CDn载波侦听载波侦听: 在某些技术在某些技术(有线有线)中容易，在另一些中容易，在另一些(无线无线

54、)中困难中困难nCSMA/CD 用在以太网中用在以太网中nCSMA/CA 用在用在 802.11中中106第3章：内容提要3.1 链路层概述3.2 成帧3.3 差错检测和纠正技术3.4 可靠数据传输原理3.5 多路访问协议3.6 以太网以太网MAC地址地址CSMA/CD以太网技术标准以太网技术标准3.7 链路层交换机链路层交换机3.8 802.11无线局域网无线局域网3.9 小结小结107以太网(Ethernet)以太网占统治地位的有线LAN技术n来自20世纪70年代在20世纪80年代和90年代早期，流行的局域网技术主要有两类：一类以太网局域网，它基于随机接入协议；另一类令牌传递技术局域网，它

55、基于令牌传递协议。108以太网(Ethernet)占统治地位的有线LAN技术（简单者生存）： n率先广泛使用的LAN技术n100Mbs网卡低于$10!n比令牌LAN和ATM等更简单、便宜n在速率竞赛中取胜: 10 Mbps 10 Gbps Metcalfe的以太网草的以太网草图图109从总线拓扑到星型拓扑n到20世纪90年代，总线拓扑流行n使用总线拓扑的以太网是一种广播局域网总线：同轴电缆总线：同轴电缆110从总线拓扑到星型拓扑n到20世纪90年代后期，集线器出现n使以太网在物理上呈星型拓扑结构，而逻辑上让保持为总线结构，提高了以太网的可靠性n集线器是一种物理层设备，它作用于各个比特而不是作用

56、于帧n如果集线器同时从两个不同的接口接收到比特，将出现一次碰撞，必须重新传输它们。111从总线拓扑到星型拓扑n交换机的出现使以太网升级为交换以太网n交换以太网不仅是无碰撞的，还是存储转发的n中心为交换机（二层设备）中心为交换机（二层设备）交换机星形112MAC地址n点对点链路：n广播链路：n多个结点之间为了进行通信，每个结点都必须多个结点之间为了进行通信，每个结点都必须具有唯一的标识。即具有唯一的标识。即链路层地址链路层地址。113MAC地址n以太网工作在数据链路层，以太网适配器具有唯一的链路层地址。nLAN地址地址=物理地址物理地址=MAC地址地址，通常用6字节16进制表示n如1a-03-6

57、5-3F-2e-46n共有248个LAN地址nIEEE地址分配方式：固定前24 bit，公司生成后24 bit，每个适配器具有唯一MAC地址n适配器的MAC地址具有扁平(没有层次)结构，且保持不变114MAC地址n与MAC地址形成对照的是，IP地址（网络层地址）是有层次结构的，且当主机移动时，IP地址通常需要改变nMAC地址身份证号nIP地址邮政地址n就像邮政地址和身份证号都有特定用途一样，一个结点必须同时具有MAC地址和IP地址115网卡检查 MAC 地址 n网卡从网络上每收到一个 数据帧就首先用硬件检查 该数据帧中的 MAC 地址。n如果是发往本站的帧则收下，然后再进行其他的处理。n否则就

58、将此帧丢弃，不再进行其他的处理。n“发往本站的帧”包括以下三种帧： n单播(unicast)帧（一对一）n广播(broadcast)帧（一对全体）n多播(multicast)帧（一对多）116以太网帧结构发送端适配器在以太网帧中封装上层数据如：IP数据报。117v以太网帧结构MAC 帧帧物理层物理层MAC 层层IP 层层以太网以太网 V2 MAC 帧帧目的地址目的地址源地址源地址类型类型数数 据据FCS6624字节字节46 1500IP 数据报数据报10101010101010 10101010101010101011前同步码前同步码帧开始帧开始定界符定界符7 字节字节1 字节字节8 字节字节

59、插入插入前导码:为了达到为了达到比特同步比特同步，需增加，需增加 8 个字节，其中，第一个字节，其中，第一个字段共个字段共 7 个字节，是前同步码，用来迅速实现个字节，是前同步码，用来迅速实现 MAC 帧的比帧的比特同步。第二个字段是帧开始定界符，表示后面的信息就是特同步。第二个字段是帧开始定界符，表示后面的信息就是MAC 帧。帧。118v以太网帧结构MAC 帧帧物理层物理层MAC 层层IP 层层以太网以太网 V2 MAC 帧帧目的地址目的地址源地址源地址类型类型数数 据据FCS6624字节字节46 1500IP 数据报数据报目的地址字段目的地址字段 6 字节字节源地址字段源地址字段 6 字节

60、字节119v以太网帧结构MAC 帧帧物理层物理层MAC 层层IP 层层以太网以太网 V2 MAC 帧帧目的地址目的地址源地址源地址类型类型数数 据据FCS6624字节字节46 1500IP 数据报数据报类型字段类型字段 2 字节字节 类型字段用来标志类型字段用来标志上一层上一层使用的是什么协议，以便使用的是什么协议，以便把收到的把收到的 MAC 帧的数据上交给上一层的这个协议。帧的数据上交给上一层的这个协议。 120v以太网帧结构MAC 帧帧物理层物理层MAC 层层IP 层层以太网以太网 V2 MAC 帧帧目的地址目的地址源地址源地址类型类型数数 据据FCS6624字节字节46 1500IP 数据报数