计算机网络直接连接网络

计算机网络直接连接网络第一页，共169页。教学提示教学目的理解数据链路层服务，掌握可靠数据传输和多路访问原理，熟练掌握各种链路层协议与设备重要知识点成帧差错检测可靠数据传输多路访问技术学习方法以基础性问题为中心展开学习

MAC地址CSMA/CD以太网交换机IEEE802.112第二页，共169页。直连连接的网络中的机制和设备机制设备在其他层可用3第三页，共169页。WhatisaLink?4CommunicationMediumNetworkAdapter4第四页，共169页。数据链路层的基本概念

链路(link)是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。一条链路只是一条通路的一个组成部分。数据链路(datalink)除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。现在最常用的方法是使用适配器（即网卡）来实现这些协议的硬件和软件。一般的适配器都包括了数据链路层和物理层这两层的功能。

5第五页，共169页。工作场景最简单网络：用某种传输媒体连接所有主机涉及数据链路层技术单段链路使用点到点通信协议或广播多路访问协议为大型网络提供某“一跳”的低层通信支撑以太网无线局域网路由器IP网络通信网6第六页，共169页。第3章：内容提要3.1链路层概述3.2成帧3.3差错检测和纠正技术3.4可靠数据传输原理3.5多路访问协议3.6以太网3.7链路层交换机3.8802.11无线局域网3.9小结7第七页，共169页。链路层环境链路层协议任务：通过单段链路，点到点传送上层数据报定义了链路两端结点间交互的帧格式，以及发送和接收帧时的操作两种网络链路类型点对点链路广播链路8第八页，共169页。点对点链路：由链路一端的单个发送结点和链路另一端的单个接收结点组成。这种链路使用一对一的点对点通信方式。广播链路：能够让多个发送结点和接收结点都连接到单一的，共享的广播信道上。这种链路使用一对多的广播通信方式。因广播链路上连接的主机很多，必须使用专用的共享链路协议来协调这些主机的数据发送。9第九页，共169页。链路层环境链路层环境重要特点一条路径上的不同链路可运行不同的链路层协议链路层协议提供的服务可以不同通信环境较为简单10第十页，共169页。利用不同交通工具旅游的例子北京杭州黄山首都机场杭州机场黄山火车站11第十一页，共169页。链路层的基本服务就是将网络层分组通过单段通信链路从一个结点移动到相邻结点。且其所提供的服务会随着链路层协议转变而改变。12第十二页，共169页。链路层协议的设计问题1.成帧将数据报封装进帧，加上首部和尾部，帧定界问题2.媒体访问规定了结点在链路上传输帧的规则如何共享媒体，如何访问信道？用媒体访问控制(MAC)协议协调结点之间的帧传输

3.相连结点间的可靠交付是网络中基础性问题（无差错的传输每个帧）在比特差错低的链路很少使用(光纤，双绞线)无线链路:高差错率则需要13第十三页，共169页。链路层服务的设计问题(续)4.流量控制相邻发送和接收结点间的步调协调（防止接收结点缓冲区溢出）5.差错检测差错由信号衰减、噪声所致接收方检测出差错，将帧丢弃发送方负责重传通常用硬件实现6.纠错接收方识别和纠正比特差错，而不采取重传14第十四页，共169页。网络适配器及其与协议栈功能的关系问题：链路层功能在哪里？网络适配器设备驱动程序15第十五页，共169页。网络适配器也成为网络接口卡或网卡。网络适配器通常与系统的I/O总线相连，在结点内存和网络链路之间传输数据。结点上运行的一个软件模块称为设备驱动程序，用来管理网络适配器。链路层功能的主体部分是在网络适配器中实现的（链路层控制器）。16第十六页，共169页。17第十七页，共169页。第3章：内容提要3.1链路层概述3.2成帧3.3差错检测和纠正技术3.4可靠数据传输原理3.5多路访问协议3.6以太网3.7链路层交换机3.8802.11无线局域网3.9小结18第十八页，共169页。IP数据报1010……0110帧取出数据链路层网络层链路结点A结点B物理层数据链路层结点A结点B帧(a)(b)发送帧接收链路IP数据报1010……0110帧装入数据链路层传送的是帧19第十九页，共169页。在分组交换网络中，结点交换的是数据块而不是比特流。结点的网络适配器通过链路层协议在结点之间交换帧（一个比特序列）。为了完成帧在结点之间的传输，适配器首先要准确识别这个比特序列具有什么样的帧结构，即决定帧从哪里开始到哪里结束。20第二十页，共169页。面向比特的协议面向比特的协议把帧看成比特的集合以HDLC协议为例，用特别的比特序列表示帧的开始和结束（01111110）比特填充(bitstuffing)法(用于发送前/接收后)发送方：报文中5个连续1，插入0接收方：收到5个连续1：后为0，去掉；为1，后为0，则帧结束；否则出错21第二十一页，共169页。PPP协议点对点协议(PPP)家庭主机到第一跳路由器的点对点链路的链路层协议用户使用拨号电话线接入因特网时，一般都是使用PPP协议。PPP协议是家庭用户的计算机和ISP进行通信时所使用的数据链路层协议。22第二十二页，共169页。用户到ISP的链路使用PPP协议用户至因特网已向因特网管理机构申请到一批

IP地址ISP接入网PPP

协议23第二十三页，共169页。PPP协议的帧格式协议代码24第二十四页，共169页。PPP协议的帧格式PPP有一个2个字节的协议字段。当协议字段为0x0021时，PPP帧的信息字段就是IP数据报。若为0xC021,则信息字段是PPP链路控制数据。若为0x8021，则表示这是网络控制数据。

IP数据报1211字节12不超过1500字节PPP帧先发送7EFF03FACFCSF7E协议信息部分首部尾部25第二十五页，共169页。面向字节的协议早期每帧都看成是字节的集合保留一组字符为控制字符同步字符SYN；首部开始符SOH；正文开始符STX；正文结束符ETX；转义字符DLE效率较低，目前已很少使用DLE字符的“转义”作用信息DLESTXADLEBDLEETX在网络中传送26第二十六页，共169页。第3章：内容提要3.1链路层概述3.2成帧3.3差错检测和纠正技术奇偶校验检验和方法循环冗余检测(CRC)3.4可靠数据传输原理3.5多路访问协议3.6以太网3.7链路层交换机3.8802.11无线局域网3.9小结27第二十七页，共169页。为了保证数据的可靠传输，在数据传输出现错误后，有两种处理方法，一是检错重发；二是前向纠错。28第二十八页，共169页。处理帧差错两种方法检错重发(detectandretransmission)检测到发送方报文受损，则通知发送方重传副本差错率低效果好前向纠错(ForwardErrorCorrection,FEC)纠错通过“预先”发送额外信息进行时效性好适用场合检错重发适合链路差错率很低的场合，如有线通信前向纠错适合对时间要求很高的场合，如航天和实时控制29第二十九页，共169页。

为此，首先要检查出误码。这样就需要在传输数据时加上能够检查出错误或能够定位错误的冗余信息。冗余信息——用某种明确定义的算法直接从原始报文中导出的信息。30第三十页，共169页。差错检测EDC：差错检测和纠错比特(冗余)D：数据由差错校验保护，可能包括首部字段

易出现比特错链路

31第三十一页，共169页。差错检测不是100%可靠!

协议可能漏掉某些差错，但是非常少较大的EDC字段产生更好的检测和纠正一种优秀的差错检测方法应当满足：加入的冗余信息较少，而能检测出所有的差错。

32第三十二页，共169页。差错检测方法奇偶校验检验和方法循环冗余检验33第三十三页，共169页。奇偶校验奇偶校验码是奇校验码和偶校验码的统称，是一种最基本的检错码。用单个奇偶校验位可检测出链路发生的单个比特差错。发送方发送的信息由n-1位信息元和1位校验元组成，可以表示成为（n，n-1）。如果是奇校验码，在附加上一个校验元以后，码长为n的码字中“1”的个数为奇数个；如果是偶校验码，在附加上一个校验元以后，码长为n的码字中“1”的个数为偶数个。例：

信息字段

奇校验码

偶校验码

0110001

01100010

01100011编码效率：Q/(Q+1)

(信息字段占Q个比特)34第三十四页，共169页。奇偶校验二维比特奇偶校验:检测到所有1,2,3个比特差错和大部分4bit差错和纠正1个比特差错。00奇偶差错奇偶差错可纠正的单比特差错无差错35第三十五页，共169页。检验和方法检验和方法（可用于因特网网络层）思想：将传输的所有字节当做整数加起来，其和作为检验和，然后将这个检验和连同数据传输到接收方，接收方对收到的数据执行相同的计算，再把得到的结果与收到的检验和进行比较。因特网检验和就基于这种方法。36第三十六页，共169页。因特网检验和发送方:将段内容作为16比特整数序列来处理检验和:连续两两求和，校验和为和的反码发送方将检验和的值放入

检验和字段接收方:计算接收到段的检验和检查是否计算的检验和等于检验和字段的值:NO–

检测到差错YES–

没有检测到差错，仍可能有错目标：检测传输段中的“差错”(如比特翻转)37第三十七页，共169页。因特网检验和例子注意：当作加法时，最高位进比特位的进位需要加到结果中例子：

3个16bit的整数1100011001100110，1111010101010101，1000111100001100相加1

1100011001100110

111

1010101010101110111011101110111

1011101110111100100011110000110010100101011001000010010101100100111011010100110110回卷和检查和(求反)和回卷38第三十八页，共169页。因特网检验和检错效果

对不同的报文，容易找到具有相同检验和的另一段报文:IOU100.99BOB494F553130302E393942D242messageASCIIformatB2C1D2ACIOU900.19BOB494F553930302E313942D242messageASCIIformatB2C1D2AC不同的报文但相同的检验和!效果不好!

报文

报文ASCII形式ASCII形式39第三十九页，共169页。循环冗余检验为了提供很强的差错检测能力，现代计算机网络普遍在链路层用硬件芯片实现了基于循环冗余检验（CRC—CyclicRedundancyCheck）编码的差错检验技术。

40第四十页，共169页。循环冗余检验的原理

假设待传送的数据M=1010001101（共kbit）。发送方和接收方协商一个mbit的除数P即可确定我们在数据M的后面添加的供差错检测用冗余码的长度为nbit（n=m-1）。

41第四十一页，共169页。冗余码的计算

用二进制的模2

运算进行2n乘M的运算，这相当于在M后面添加n个0。得到的(k+n)bit的数除以事先选定好的长度为mbit

的数P，得出商是Q而余数是R（即为所求的冗余码），所得余数R比除数P至少要少1个比特。

42第四十二页，共169页。设

M=1010001101,P=110101，即

n=5,模2运算的结果是：商Q=1101010110，

余数R=01110。将余数R作为冗余码添加在数据M的后面发送出去，即发送的数据是101000110101110，或2nM+R。43第四十三页，共169页。

1101010110

←

Q

商

除数

P→

110101101000110100000

←

2nM被除数

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101

01110

←

R

余数44第四十四页，共169页。接收方如何检测呢？用接收端收到得数据除以P（发送端事先定好的那个）如果所得余数为0，则在传输过程中没有产生误码；如果所得余数不为0，则在传输过程中产生了误码；45第四十五页，共169页。但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。一旦检测出差错，就丢弃这个出现差错的帧。注意：能不能说所得余数为0，就肯定没有出现差错？只要经过严格的挑选，并使用位数足够多的除数P，那么出现检测不到的差错的概率就很小很小。

检测出错了？46第四十六页，共169页。

任何一个由二进制数位串组成的代码可以和一个只含有0和1两个系数的多项式建立一一对应的关系。

例如，代码1010111对应的多项式为X6+X4+X2+X+1，而多项式X5+X3+X2十X十1对应的代码为101111。47第四十七页，共169页。目前，广泛使用的除数P主要有四种:CRC12＝X12十X11十X3十X2+1CRC16＝X16十X15十X2十1(IBM公司)CRC16＝X16十X12十X5十1(CCITT)CRC32＝X32十X26十X23十X22十X16十X11十X10十X8十X7十X5十X4十X2+X+1

48第四十八页，共169页。应当注意

仅用循环冗余检验CRC差错检测技术只能做到无差错接受(accept)。“无差错接受”是指：“凡是接受的帧（即不包括丢弃的帧），我们都能以非常接近于1的概率认为这些帧在传输过程中没有产生差错”。也就是说：“凡是接收端数据链路层接受的帧都没有差错”（有差错的帧就丢弃而不接受）。传输差错可分为两大类：帧出现比特差差错；帧丢失、帧重复和帧失序。“可靠传输”（即发送什么就收到什么）就必须再加上帧编号、确认和重传机制。

49第四十九页，共169页。第3章：内容提要3.1链路层概述3.2成帧3.3差错检测和纠正技术3.4可靠数据传输原理设计可靠数据传输协议流水线可靠数据传输协议回退N步协议选择重传协议3.5多路访问协议3.6以太网3.7链路层交换机3.8802.11无线局域网3.9小结50第五十页，共169页。可靠数据传输：服务模型与服务实现可靠数据传输是互联网中最为重要的问题之一该问题在多层协议中出现一般服务模型51第五十一页，共169页。设计可靠数据传输协议基本思想：在分组传输过程进行差错检测，一旦接收方发现差错，就应当告知发送方，由发送方重传该分组学习方法：研究一系列协议，一步解决一个问题，直至实用52第五十二页，共169页。设计可靠数据传输协议：SW0协议前提条件：信道不丢包解决方案：接到正确PKT，发送一个肯定确认(ACK)收到错误PKT，发送一个否定确认(NAK)，重传原PKT停止等待(stop-and-wait,SW)协议实用中有不少漏洞53第五十三页，共169页。设计可靠数据传输协议：SW1协议条件：信道丢包SW0的发送方会一直等待ACK，引起协议死锁解决方案：增加超时定时器每发PKT，启动超时定时器，称为超时重传机制重传时间略大于平均RTT无需NAK（否认确认）54第五十四页，共169页。设计可靠数据传输协议：SW2协议条件：确认分组丢失出现了分组冗余的差错解决方案：增加一种新机制：发送序号序号空间要较小如发送序号3bit，在0~7间循环使用55第五十五页，共169页。设计可靠数据传输协议：SW3协议对确认进行编号？收到重复的确认，无法分辨对应哪个分组解决方案：增加确认序号机制，分辨出确认对应哪个分组综合以上机制为SW协议，或自动重传请求(ARQ)设计可靠数据传输协议机制：差错检测、接收方确认(肯定/否定)、重传、定时器和序号(数据和确认)56第五十六页，共169页。第3章：内容提要3.1链路层概述3.2成帧3.3差错检测和纠正技术3.4可靠数据传输原理设计可靠数据传输协议流水线可靠数据传输协议回退N步协议选择重传协议3.5多路访问协议3.6以太网3.7链路层交换机3.8802.11无线局域网3.9小结57第五十七页，共169页。流水线协议2.5Gbps光传输系统，RTT为35ms。分组长L＝1,500byte，发送时延信道的利用率改进停止等待协议，提高传输效率58第五十八页，共169页。流水线:提高协议利用率59第五十九页，共169页。可连续发送若干个分组，提高信道利用率实际的协议一次至少允许连续发送256个分组，协议效率至少提高256倍!看似n个分组被填充到一条流水线上，故此技术被称为流水线60第六十页，共169页。流水线传输流水线:发送方允许发送多个、传输中、未应答的分组，不必每发完一个分组就停顿下来等待对方的确认。由于信道上一直有数据不间断地传送，这种传输方式可获得很高的信道利用率。B分组ttAACK61第六十一页，共169页。流水线协议必须增加序号范围发送方和/或接收方设有缓冲两种流水线协议:

回退N步（go-Back-N）,选择性重传（S-R）62第六十二页，共169页。第3章：内容提要3.1链路层概述3.2成帧3.3差错检测和纠正技术3.4可靠数据传输原理设计可靠数据传输协议流水线可靠数据传输协议回退N步协议选择重传协议3.5多路访问协议3.6以太网3.7链路层交换机3.8802.11无线局域网3.9小结63第六十三页，共169页。如何处理流水线差错？使用流水线技术传输分组时，若出现接收方或网络来不及处理这些分组情况，就会导致丢包。当流水线差错时，对所需序号窗口和缓冲的要求取决于数据传输协议处理丢失、损坏及时延过大分组的方式恢复流水线差错的两种基本方法回退N步(Go-Back-N，GBN)选择重传(SelectiveRepeat,SR)64第六十四页，共169页。GBN协议在流水线传输的基础上。通过发送窗口机制来限制发送方连续发送分组的个数。回退N步协议(Go-Back-N)65第六十五页，共169页。回退N步协议(Go-Back-N)发送方:在分组首部需要K比特序号，2k=N（序号循环使用）“窗口”最大为N,允许连续发送N个没有应答分组滑动窗口(流水线)已确认已发送但未确认可用但未发送不可用窗口长度N发送基序号下一个序号66第六十六页，共169页。发送窗口机制123456789101112(a)发送方维持发送窗口（发送窗口是5）发送窗口(b)收到对第一个分组的确认后发送窗口向前滑动向前123456789101112发送窗口位于发送窗口的中的分组可以连续发送出去，而不需要等待对方的确认信息67第六十七页，共169页。GBN协议注意点接收方按序根据滑动窗口的序号接收分组GBN协议的接收窗口的长度为1窗口中失序的分组将被丢弃（接收方除了丢弃失序分组外，还要对最近按序接收的分组进行确认）发送方采用超时机制来重传出现丢失会差错的分组接收方可采用累积确认的方式68第六十八页，共169页。GBN协议例子发送窗口为3，序号范围为[0，3]69第六十九页，共169页。第3章：内容提要3.1链路层概述3.2成帧3.3差错检测和纠正技术3.4可靠数据传输原理设计可靠数据传输协议流水线可靠数据传输协议回退N步协议选择重传协议3.5多路访问协议3.6以太网3.7链路层交换机3.8802.11无线局域网3.9小结70第七十页，共169页。选择性重传(SelectiveRepeat)问题：GBN是否还能够改善？(单一差错可能导致大量不必要重传)接收方可分别确认所有正确接收的报文段缓存失序分组,以便最后按序交付给上层发送方只需要重传没有收到ACK的分组发送方定时器对每个分组计时发送窗口N个连续的序号也需要限制已发送但尚未应答分组的序号71第七十一页，共169页。选择性重传:发送方/接收方窗口a.发送方看到的序号b.接收方看到的序号已经确认可用，还未发送发送，还未确认不可用可接受（窗口内）失序(已缓存)但已被确认期待，还未收到不可用窗口长度N窗口长度N发送基序号接收基序号下一个序号72第七十二页，共169页。选择性重传算法上层传来数据:如果窗口中下一个序号可用,发送报文段timeout(n):重传丢失分组n,重启其计时器ACK(n)在[发送基,发送基+N]:标记分组n已经收到如果n是最小未收到应答的分组，向前滑动窗口基指针到下一个未确认序号发送方分组n在[接收基,接收基+N-1]发送ACK(n)失序:缓存按序:交付(也交付所有缓存的按序分组),向前滑动窗口到下一个未收到报文段的序号分组n在[接收基-N,接收基-1]ACK(n)其他:忽略接收到的分组接收方73第七十三页，共169页。选择重传的例子74第七十四页，共169页。SR:窗口长度问题（序号空间有限时）例子:序号:0,1,2,3窗口长度=3接收方：在(a)和(b)两种情况下，接收方没有发现两者间的差别!在(a)和(b)接收方无法区分接收到的分组是重传的还是新的。问题:

序号长度与窗口长度有什么关系?回答：窗口长度小于等于序号空间的一半75第七十五页，共169页。可靠数据传输机制及用途小结机制用途和说明检验和用于检测在一个传输分组中的比特错误。定时器用于超时/重传一个分组，可能因为该分组（或其ACK）在信道中丢失了。由于当一个分组被时延但未丢失（过早超时），或当一个分组已被接收方收到但从接收方到发送方的ACK丢失时，可能产生超时事件，所以接收方可能会收到一个分组的多个冗余拷贝。序号用于为从发送方流向接收方的数据分组按顺序编号。所接收分组的序号间的空隙可使该接收方检测出丢失的分组。具有相同序号的分组可使接收方检测出一个分组的冗余拷贝。确认接收方用于告诉发送方一个分组或一组分组已被正确地接收到了。确认报文通常携带着被确认的分组或多个分组的序号。确认可以是逐个的或累积的，这取决于协议。否定确认接收方用于告诉发送方某个分组未被正确地接收。否定确认报文通常携带着未被正确接收的分组的序号。窗口、流水线发送方也许被限制仅发送那些序号落在一个指定范围内的分组。通过允许一次发送多个分组但未被确认，发送方的利用率可在停等操作模式的基础上得到增加。窗口长度可根据接收方接收和缓存报文的能力或网络中的拥塞程度，或两者情况来进行设置。76第七十六页，共169页。第3章：内容提要3.1链路层概述3.2成帧3.3差错检测和纠正技术3.4可靠数据传输原理3.5多路访问协议信道划分协议轮流协议随机接入协议3.6以太网3.7链路层交换机3.8802.11无线局域网3.9小结77第七十七页，共169页。多路访问(multipleaccess)链路和协议多路访问多个发送/接收结点同时使用广播信道，如何协调它们共享一个信道局域网环境，密集端系统通常使用多路访问方式应用场景：信道资源紧缺，大量端系统或者频繁访问网络，或者以较小概率访问网络78第七十八页，共169页。多路访问协议：共享单一广播信道两个或更多结点并行传输相互干扰碰撞：如果结点同时接收到两个或更多信号多路访问协议决定结点怎样共享信道的分布式算法，如：决定何时结点能够传输？出现碰撞时如何解决？共享信道的通信必须使用信道本身!不能用带外信道来协调79第七十九页，共169页。理想的多路访问协议速率Rbps的广播信道1.当只有一个结点时，能够以速率R发送2.当有M个结点时，每个能以平均速率R/M发送3.分布式:无特殊结点来协调传输无同步时钟、时隙4.简单80第八十页，共169页。多路访问协议:分类有3种类型:信道划分将信道划分为较小的“段”

(时隙，频率，编码)为每个结点分配一部分专用轮流结点轮流，信息较多的轮流发送的时间较长随机访问不划分信道，允许碰撞设法从“碰撞”恢复问题：协议应用场景不同，设计协议的方法是否有所不同？81第八十一页，共169页。信道划分协议:TDMATDMA:时分多路访问

“循环”访问信道每个站点在每个循环中获得固定长度时隙(长度=分组传输时间)不使用的时隙则空闲例子：6个站点的LAN,时隙1、3、4有分组,时隙2、5、6空闲(浪费)82第八十二页，共169页。信道划分协议:FDMAFDMA:频分多路访问

信道频谱划分为频带每个站点分配固定的频带频带中未使用的传输时间空闲例子：6个站点的LAN,频带1、3、4有分组,频带2、5、6空闲(浪费)83第八十三页，共169页。FDM和TDM特点消除了碰撞且公平结点在每个帧时间内得到了专用的传输速率R/Nbps若系统仅有少数几个有大量分组要发送的结点分配的频率或时隙被浪费适合场合所有结点都持续有大量数据发送CDMA是另一种信道划分协议2.3.2节84第八十四页，共169页。第3章：内容提要3.1链路层概述3.2成帧3.3差错检测和纠正技术3.4可靠数据传输原理3.5多路访问协议信道划分协议轮流协议随机接入协议3.6以太网3.7链路层交换机3.8802.11无线局域网3.9小结85第八十五页，共169页。两种轮流协议轮询(有中心):

主结点“邀请”从结点依次传输关注问题:轮询开销时延单点故障(主结点)令牌传递(无中心):控制令牌从一个结点顺序地传递到下一个令牌报文关注问题:令牌开销时延单点故障(令牌消失)适用于希望共享信道但却无法预测访问结点的数量的场景86第八十六页，共169页。第3章：内容提要3.1链路层概述3.2成帧3.3差错检测和纠正技术3.4可靠数据传输原理3.5多路访问协议信道划分协议轮流协议随机接入协议3.6以太网3.7链路层交换机3.8802.11无线局域网3.9小结87第八十七页，共169页。随机访问协议大量结点以小概率发送分组以信道全部速率R传输结点间无优先权协调两个或更多传输结点发送➜

“碰撞”(小概率)随机访问协议定义了:如何检测碰撞如何从碰撞中恢复(例如，经延迟后重新传输)随机访问协议的实例:ALOHA时隙ALOHACSMA,CSMA/CD,CSMA/CA88第八十八页，共169页。ALOHA协议

一种用于解决在分组无线通信系统中分配广播信道的分布式方法假定所有帧有相同长度结点随时传输帧结点是异步的如果2+结点同时传输，所有结点检测碰撞操作当结点获得新帧，将随时传输无碰撞，结点能够继续发送新帧如果碰撞，结点能够检测到，以概率P重传帧89第八十九页，共169页。时隙ALOHA特点单个活跃结点能够连续地以信道的全速传输结点中的时隙需要同步简单碰撞，浪费时隙空闲时隙结点能以小于传输分组的时间检测到碰撞节点时钟同步困难90第九十页，共169页。在时隙ALOHA协议和纯ALOHA协议中,一个结点的成功传输取决于连接在这个广播信道上的其他结点的活动。由于无线信道的特点，传输结点有时无法得知其他结点的活动情况。有线局域网中就不一样了。91第九十一页，共169页。CSMA(载波侦听多路访问)CSMA:

工作原理：发送前监听。每个站点在发送数据之前要监听信道上是否有数据在传送。若有，则此站不能发送，以免发生碰撞，需等待一段时间后重试。人类类比：

不要打断他人说话!避免两人同时讲话!CSMA用于有线，ALOHA用于无线92第九十二页，共169页。CSMA：载波监听多点访问载波监听策略：非坚持CSMA：一旦监听到信道忙，就不再监听；延迟一个随机时间后再次监听。坚持CSMA：监听到信道忙时，仍继续监听，直到信道空闲。

1-坚持CSMA：一听到信道空闲就立即发送数据

p-坚持CSMA：听到信道空闲时，以概率p发送数据（以概率1-p延迟一段时间后再发送）93第九十三页，共169页。CSMA：载波监听多点访问CSMA技术能解决发送时出现的冲突现象帧在发送过程中有可能出现“碰撞”CSMA技术不能解决发送中出现的冲突现象

94第九十四页，共169页。问题：

既然发送前已经监听到信道空闲，为什么发送时还要继续监听信道？95第九十五页，共169页。电磁波在总线上的有限传播速率的影响

当某个站监听到总线是空闲时，也可能总线并非真正是空闲的。A向B发出的信息，要经过一定的时间后才能传送到B。B若在A发送的信息到达B之前发送自己的帧(因为这时B的载波监听检测不到A所发送的信息)，则必然要在某个时间和A发送的帧发生碰撞。碰撞的结果是两个帧都变得无用。

96第九十六页，共169页。CSMA碰撞碰撞:整个分组传输时间被浪费产生碰撞的分组变得无用注意:距离与传播时延在决定碰撞概率中的作用97第九十七页，共169页。CSMA/CD(碰撞检测)CSMA/CD:

传送过程中也进行载波侦听在短时间内检测到碰撞碰撞的传输尽快结束，以减少信道浪费碰撞检测:

在有线的LAN中容易:测量信号强度，比较传输的和接收的信号在无线LAN中困难：碰撞可能听不到人类类比:礼貌的交谈者问题：能否进一步提高CSMA效率？98第九十八页，共169页。CSMA/CD的基本工作原理工作原理：每个站发送数据前先监听信道是否空闲，若空闲则立即发送数据。在发送时，边发送边检测。若检测到冲突，则立即停止发送。等待一段随机时间（称为退避）以后，再重新尝试。CSMA/CD可归结为四句话：

发前先监听空闲即发送边发边检测冲突时退避99第九十九页，共169页。1kmABt碰撞t=2

A检测到发生碰撞t=

B发送数据B检测到发生碰撞t=t=0单程端到端传播时延记为

100第一百页，共169页。1kmABt碰撞t=

B检测到信道空闲发送数据t=

/2发生碰撞t=2

A检测到发生碰撞t=

B发送数据B检测到发生碰撞t=ABABABt=0A检测到信道空闲发送数据ABt=0t=B检测到发生碰撞停止发送STOPt=2

A检测到发生碰撞STOPAB单程端到端传播时延记为

101第一百零一页，共169页。强化碰撞

当发送数据的站一旦发现发生了碰撞时，除了立即停止发送数据外，还要再继续发送若干比特的阻塞信号(jammingsignal)，以便让所有用户都知道现在已经发生了碰撞。

102第一百零二页，共169页。数据帧干扰信号TJ阻塞信号

ABTBtB发送数据A检测到冲突开始冲突信道占用时间A发送数据B也能够检测到冲突，并立即停止发送数据帧，接着就发送干扰信号。这里为了简单起见，只画出A发送干扰信号的情况。103第一百零三页，共169页。多路访问协议比较信道划分协议在高负载时高效、公平地共享信道低负载时低效：信道访问中延时，当1个活跃结点时，甚至仅有分配了1/N带宽!随机访问协议低负载是有效：单个结点能够全面利用信道高负载：碰撞开销大轮流协议兼有两方面的优点!104第一百零四页，共169页。多路访问协议小结问题：对共享媒体你需要做些什么?信道划分,通过时间、频率或编码时分,频分轮流从中心站点轮询，令牌传递随机划分(动态的),ALOHA,S-ALOHA,CSMA,CSMA/CD载波侦听:在某些技术(有线)中容易，在另一些(无线)中困难CSMA/CD用在以太网中CSMA/CA用在802.11中105第一百零五页，共169页。第3章：内容提要3.1链路层概述3.2成帧3.3差错检测和纠正技术3.4可靠数据传输原理3.5多路访问协议3.6以太网MAC地址CSMA/CD以太网技术标准3.7链路层交换机3.8802.11无线局域网3.9小结106第一百零六页，共169页。以太网(Ethernet)以太网——占统治地位的有线LAN技术来自20世纪70年代在20世纪80年代和90年代早期，流行的局域网技术主要有两类：一类以太网局域网，它基于随机接入协议；另一类令牌传递技术局域网，它基于令牌传递协议。107第一百零七页，共169页。以太网(Ethernet)占统治地位的有线LAN技术（简单者生存）：

率先广泛使用的LAN技术100Mbs网卡低于$10!比令牌LAN和ATM等更简单、便宜在速率竞赛中取胜:10Mbps~10GbpsMetcalfe的以太网草图108第一百零八页，共169页。从总线拓扑到星型拓扑到20世纪90年代，总线拓扑流行使用总线拓扑的以太网是一种广播局域网总线：同轴电缆109第一百零九页，共169页。从总线拓扑到星型拓扑到20世纪90年代后期，集线器出现使以太网在物理上呈星型拓扑结构，而逻辑上让保持为总线结构，提高了以太网的可靠性集线器是一种物理层设备，它作用于各个比特而不是作用于帧如果集线器同时从两个不同的接口接收到比特，将出现一次碰撞，必须重新传输它们。110第一百一十页，共169页。从总线拓扑到星型拓扑交换机的出现使以太网升级为交换以太网交换以太网不仅是无碰撞的，还是存储转发的中心为交换机（二层设备）交换机星形111第一百一十一页，共169页。MAC地址点对点链路：广播链路：多个结点之间为了进行通信，每个结点都必须具有唯一的标识。即链路层地址。112第一百一十二页，共169页。MAC地址以太网工作在数据链路层，以太网适配器具有唯一的链路层地址。LAN地址=物理地址=MAC地址，通常用6字节16进制表示如1a-03-65-3F-2e-46共有248个LAN地址IEEE地址分配方式：固定前24bit，公司生成后24bit，每个适配器具有唯一MAC地址适配器的MAC地址具有扁平(没有层次)结构，且保持不变113第一百一十三页，共169页。MAC地址与MAC地址形成对照的是，IP地址（网络层地址）是有层次结构的，且当主机移动时，IP地址通常需要改变MAC地址<——>身份证号IP地址<——>邮政地址就像邮政地址和身份证号都有特定用途一样，一个结点必须同时具有MAC地址和IP地址114第一百一十四页，共169页。网卡检查MAC地址

网卡从网络上每收到一个数据帧就首先用硬件检查该数据帧中的MAC地址。如果是发往本站的帧则收下，然后再进行其他的处理。否则就将此帧丢弃，不再进行其他的处理。“发往本站的帧”包括以下三种帧：

单播(unicast)帧（一对一）广播(broadcast)帧（一对全体）多播(multicast)帧（一对多）115第一百一十五页，共169页。以太网帧结构发送端适配器在以太网帧中封装上层数据如：IP数据报。116第一百一十六页，共169页。以太网帧结构MAC帧物理层MAC层IP层以太网V2MAC帧目的地址源地址类型数据FCS6624字节46~1500IP数据报1010101010101010101010101010101011前同步码帧开始定界符7字节1字节…8字节插入前导码:为了达到比特同步，需增加8个字节，其中，第一个字段共7个字节，是前同步码，用来迅速实现MAC帧的比特同步。第二个字段是帧开始定界符，表示后面的信息就是MAC帧。117第一百一十七页，共169页。以太网帧结构MAC帧物理层MAC层IP层以太网V2MAC帧目的地址源地址类型数据FCS6624字节46~1500IP数据报目的地址字段6字节源地址字段6字节118第一百一十八页，共169页。以太网帧结构MAC帧物理层MAC层IP层以太网V2MAC帧目的地址源地址类型数据FCS6624字节46~1500IP数据报类型字段2字节

类型字段用来标志上一层使用的是什么协议，以便把收到的MAC帧的数据上交给上一层的这个协议。119第一百一十九页，共169页。以太网帧结构MAC帧物理层MAC层IP层以太网V2MAC帧目的地址源地址类型数据FCS6624字节46~1500IP数据报

数据字段的最小长度=最小长度64字节

18字节的首部和尾部。当数据字段的长度小于46字节时，应在数据字段的后面加入整数字节的填充字段，以保证以太网的MAC帧长不小于64字节。数据字段46~1500

字节FCS字段4

字节120第一百二十页，共169页。帧的长度不是整数个字节；用收到的帧检验序列

FCS查出有差错；数据字段的长度不在46~1500字节之间。注意：对于检查出的无效MAC帧就简单地丢弃。以太网不负责重传丢弃的帧。

无效的MAC帧

121第一百二十一页，共169页。为了通信的简便

以太网采取了不可靠、无连接服务无连接:

在发送和接收适配器之间不必先建立连接就可以直接发送数据。不可靠:

接收适配器不向发送适配器发送应答或否定应答这样做的理由是局域网信道的质量很好，因信道质量产生差错的概率是很小的。

以太网提供的服务是不可靠的交付，即尽最大努力的交付。122第一百二十二页，共169页。当目的站收到有差错的数据帧时就丢弃此帧，其他什么也不做。差错的纠正由高层来决定。如果应用程序使用TCP，将能弥补丢包否则，应用程序将发现丢包如果高层发现丢失了一些数据而进行重传，但以太网并不知道这是一个重传的帧，而是当作一个新的数据帧来发送。

123第一百二十三页，共169页。第3章：内容提要3.1链路层概述3.2成帧3.3差错检测和纠正技术3.4可靠数据传输原理3.5多路访问协议3.6以太网MAC地址CSMA/CD以太网技术标准3.7链路层交换机3.8802.11无线局域网3.9小结124第一百二十四页，共169页。当多个结点通过集线器互联时，该以太网形成了一个总线广播信道。若某适配器传输一帧，局域网上的所有适配器都能收到帧。这时需要多路访问协议来解决帧之间的碰撞。125第一百二十五页，共169页。以太网协议(CSMA/CD)1.适配器从网络层接收数据报并生成帧2.如果适配器感知信道空闲，它开始传输帧；如果它感知信道忙，等待信道空闲再传输3.当适配器传输整个帧时，一直检测另一个帧的传输4.如果适配器传输过程中检测到另一次传输,中止并发送强化冲突信号5.中止后,适配器进入指数回退:在第m次碰撞后,适配器随机地从{0,1,2,…,2m-1}选择一个K值。适配器等待K*512比特时间并返回到第2步126第一百二十六页，共169页。以太网协议(CSMA/CD)(续)强化冲突信号:

确保所有的其他传输方都知道碰撞;48bit长比特时间:

对10Mbps以太网传每比特需0.1μs;对K=1023,等待时间约为50msec

若碰撞次数达到16次，则放弃传输。指数回退:

目标：估计当前负载，适应重传尝试重负载:随机等待时间更长首次碰撞后:从{0,1}中选择K；时延是K*512bit传输时间第二次碰撞后:从{0,1,2,3}选择K10次碰撞后,从{0,1,2,3,4,…,1023}选择K127第一百二十七页，共169页。CSMA/CD效率τ=LAN中的2站点之间的最大传播时间T0=传输最长帧的时间随着τ趋于0,效率趋于1随着T0趋于无穷大，效率趋于1比ALOHA好得多,简单且便宜

128第一百二十八页，共169页。第3章：内容提要3.1链路层概述3.2成帧3.3差错检测和纠正技术3.4可靠数据传输原理3.5多路访问协议3.6以太网MAC地址CSMA/CD以太网技术标准3.7链路层交换机3.8802.11无线局域网3.9小结129第一百二十九页，共169页。802.3以太网标准:链路&物理层许多不同的以太网标准共同的MAC协议和帧格式不同的速率:2Mbps,10Mbps,100Mbps,1Gbps,10Gbps不同的物理层媒体应用层运输层网络层链路层物理层MAC协议和帧格式100BASE-TX100BASE-T4100BASE-FX100BASE-T2100BASE-SX100BASE-BX光纤物理层铜(双绞线)物理层130第一百三十页，共169页。第3章：内容提要3.1链路层概述3.2成帧3.3差错检测和纠正技术3.4可靠数据传输原理3.5多路访问协议3.6以太网3.7链路层交换机转发和过滤自学习链路层交换机的性质3.8802.11无线局域网3.9小结131第一百三十一页，共169页。集线器的一些特点

集线器的主要功能是对接收到的信号进行再生整形放大，以扩大网络的传输距离，同时把所有节点集中在以它为中心的节点上。

集线器很像一个多端口的转发器，工作在物理层。集线器是使用电子器件来模拟实际电缆线的工作，因此整个系统仍然像一个传统的以太网那样运行。使用集线器的以太网在逻辑上仍是一个总线网，各端系统使用的还是CSMA/CD

协议，并共享逻辑上的总线。在同一时刻至多只允许一个站发送数据。132第一百三十二页，共169页。集线器集线器的工作过程：节点发信号到线路，集线器接收该信号，因信号在电缆传输中有衰减，集线器接收信号后将衰减的信号整形放大，最后集线器将放大的信号广播转发给其他所有端口。与集线器连接的所有结点相互碰撞无帧缓存在小型以太网中并不会造成很大问题，并且可以很好的工作，但是如果网络上的通讯量有增加，或者连接的节点数目很多的时候，“冲突”会严重影响网络的性能。133第一百三十三页，共169页。交换机链路层设备：比集线器智能化存储并转发以太网帧当帧在网段上转发时，检查帧首部并基于MAC目的地址，选择性地向一个或多个链路转发帧透明性主机不知道交换机的存在即插即用,自学习交换机不必配置134第一百三十四页，共169页。以太网交换机的每个端口都直接与主机或另外一个集线器相连，并且一般都工作在全双工方式。交换机能同时连通许多对的端口，使每一对相互通信的主机都能像独占通信媒体那样，进行无碰撞地传输数据。以太网交换机由于使用了专用的交换结构芯片，其交换速率就较高。以太网交换机的特点135第一百三十五页，共169页。对于普通10Mb/s的共享式以太网，若共有N个用户，则每个用户占有的平均带宽只有总带宽(10Mb/s)的N分之一。使用以太网交换机时，虽然在每个端口到主机的带宽还是10Mb/s，但由于一个用户在通信时是独占而不是和其他网络用户共享传输媒体的带宽，因此对于拥有N对端口的交换机的总容量为N10Mb/s。这正是交换机的最大优点。以太网交换机的特点136第一百三十六页，共169页。用以太网交换机扩展局域网

集线器集线器集线器一系三系二系10BASE-T至因特网100Mb/s100Mb/s100Mb/s万维网服务器电子邮件服务器以太网交换机路由器137第一百三十七页，共169页。交换机:并行传输扩大容量端系统与交换机有专门的直接连接交换机缓存分组在链路上使用以太网协议：全双工，无碰撞交换:

A到A’和B到B’能够同时无碰撞地进行而集线器无法办到!AA’BB’CC’具有6个接口的交换机(1,2,3,4,5,6)123456138第一百三十八页，共169页。转发与过滤过滤：是交换机决定应该将一个帧转发到某个接口还是将其丢弃的功能转发：是决定应该将一个帧导向哪个接口并把该帧移动到相应接口的交换机功能。交换机转发或过滤分组是基于MAC地址进行的139第一百三十九页，共169页。交换机表问题:

交换机如何知道经接口4可达A’,经接口5可达B’?交换机具有一个交换表，每表项:(MAC地址,到达接口,到达时间)问题:

这些表项是如何创建的，谁维护交换机表?AA’BB’CC’123456具有6个接口的交换机(1,2,3,4,5,6)140第一百四十页，共169页。交换机开机初始化时，MAC地址表是空的，因为MAC地址表是存储在内存中的。141第一百四十一页，共169页。如果计算机A发送数据帧到计算机C,此时交换机的E0口接收该数据帧，交换机记录下该数据帧的源地址A的对应关系及E0口的对应关系。由于交换机并不知道C的MAC地址，所以将此数据帧对除了E0口以外的其他端口进行转发。142第一百四十二页，共169页。如果是计算机D发送数据帧到计算机C，此时交换机的E3口接收该数据帧，交换机记录下该数据帧的源地址D的地址与端口的对应关系。此时交换机仍然不知道C的地址，所以还是要对除了E0口以外的其他端口上进行转发。143第一百四十三页，共169页。交换机不断记录每个接口上接收到的数据帧的地址，一段时间以后所有的端口所连接的MAC地址都会记录到MAC地址表中。此时计算机A再向计算机C发送数据时，就直接查MAC地址表进行转发即可，不会再转发到其他端口上。144第一百四十四页，共169页。图中计算机A和计算机B通过HUB连接到Switch的E0口上，所以在MAC地址表中记录两个MAC地址对应同一个端口，此时如果A与B通讯，则交换机不会转发该数据帧，因为源和目标MAC都在同一个接口上。145第一百四十五页，共169页。交换机:自学习初始化过程：加电开机，交换表初始化为空。学习过程：P111更新过程（刷新/老化期）AA’BB’CC’123456AA’Source:ADest:A’MAC地址接口时间交换机表(初始为空)A18:32146第一百四十六页，共169页。交换机：帧过滤/转发算法当交换机收到帧:1.记录与发送主机关联的链路2.使用MAC目的地址索引交换机表3.if

（找到目的地项）

{

if

（目的地位于帧到达的段）

{丢弃帧}

else

在指示的接口转发该帧

}

else

洪泛向所有接口(除了该帧到达的)转发该帧147第一百四十七页，共169页。自学习、转发的例子AA’BB’CC’123456AA’源:A目的地:A’MACaddrinterface时间A18:32AA’AA’AA’AA’AA’帧目的地未知:洪泛A’A目的地A位置已知：A’48:35选择性发送交换机表(初始为空)148第一百四十八页，共169页。交换表的建立方法：在转发过程中逆向学习——若帧的源地址不在表中，则插入到表中。工作原理归纳为：学习源地址，丢弃本网段帧，转发异网段帧，广播未知帧。149第一百四十九页，共169页。站地址：登记收到的帧的源MAC地址。端口：登记收到的帧进入该交换机的端口号。时间：登记收到的帧进入该交换机的时间。转发表中的MAC地址是根据源MAC地址写入的，但在进行转发时是将此MAC地址当作目的地址。在转发表中登记以下三个信息

150第一百五十页，共169页。交换机互联交换机能够连接在一起AB问题:从A向G发送，S1怎