第5章 链路层和局域网

1、1第第5章章 链路层和局域网链路层和局域网r网络层：网络层： 主机和主机之间主机和主机之间传输传输数据报数据报。r链路层：链路层： 在在相邻节点之间相邻节点之间传输数据传输数据帧帧 。应用层应用层运输层运输层网络层网络层链路层链路层物理层物理层2网络层网络层提供两台提供两台主机之主机之间间的通信服务。的通信服务。路径：路径：由源主机由源主机和目的主机之间和目的主机之间的一系列的一系列通信链通信链路和路由器路和路由器组成组成接受接受链路层链路层服务服务链路链路3网络层的网络层的数据报如何被数据报如何被封装封装成链路层的帧；成链路层的帧；分组分组如何通过各段链路如何通过各段链路链路层协议是否能够提

2、链路层协议是否能够提供路由器之间的供路由器之间的可靠数可靠数据传输；据传输；通信路径上不同的链路通信路径上不同的链路是否采用不同的链路层是否采用不同的链路层协议。协议。链路链路链路层的工作链路层的工作4学习内容学习内容m数据链路层服务数据链路层服务m差错检测和纠错差错检测和纠错m多址访问协议：多址访问协议：共享广播信道共享广播信道m链路层寻址链路层寻址m可靠传输可靠传输m链路层技术的实现链路层技术的实现5链路层信道类型链路层信道类型 广播广播链路链路 点对点点对点链路链路 6广播链路广播链路 许多主机被连接到相同的通信信道（共享信道）许多主机被连接到相同的通信信道（共享信道）需要解决的问题：需

3、要解决的问题：采用采用媒体访问协议媒体访问协议来协调传输来协调传输和避免和避免“碰撞碰撞”（冲突）。（冲突）。常用于常用于局域网局域网LAN、无线无线LAN、卫星网和光纤电、卫星网和光纤电缆混合缆混合(HFC)接入网。接入网。 7点对点链路点对点链路直连两个节点的链路，每一端有一个节点直连两个节点的链路，每一端有一个节点。 如两台路由器之间的通信链路，或住宅的调如两台路由器之间的通信链路，或住宅的调制解调器与制解调器与ISP路由器之间的通信链路。路由器之间的通信链路。 访问控制简单。访问控制简单。需要解决的问题：需要解决的问题：成帧、可靠数据传输、差错检成帧、可靠数据传输、差错检测和流量控制等

4、。测和流量控制等。 8主要内容主要内容5.1 概述与服务概述与服务5.2 差错检测和纠错差错检测和纠错 5.3多路访问协议多路访问协议5.4 链路层编址链路层编址5.5 以太网以太网5.6 集线器和交换机集线器和交换机5.7 PPP5.8 链路虚拟化链路虚拟化: ATM5.9 小结小结95.1 概述和服务概述和服务节点：节点：主机或路由器主机或路由器链路：链路：连接相邻节点的通连接相邻节点的通信信道。信信道。r链路层传输数据报的过程链路层传输数据报的过程发送节点发送节点将数据报封装成将数据报封装成链路层帧，发送到链路上链路层帧，发送到链路上接收节点接收节点接收该帧，并提接收该帧，并提取出数据报

5、。取出数据报。节点节点链路链路5.1.1 链路层提供的服务链路层提供的服务5.1.2 适配器适配器101、链路层功能和协议、链路层功能和协议r链路层功能：链路层功能：将将帧帧(frame)从一个节点通过一条链从一个节点通过一条链路传输到下一个节点。帧封装了一个网络层的数路传输到下一个节点。帧封装了一个网络层的数据报。据报。r链路层协议：链路层协议： 定义定义了了帧的格式帧的格式，以及发送和接收分组时，以及发送和接收分组时节点节点采取的动作采取的动作：包括差错检测、重传、流量控制和：包括差错检测、重传、流量控制和随机访问等。随机访问等。典型协议：典型协议：以太网、以太网、802.11无线无线LA

6、N、令牌环、令牌环、PPP，以及，以及ATM。112、网络层与链路层关系、网络层与链路层关系网络层：网络层：将运输层报文段将运输层报文段从源主机传送到目的从源主机传送到目的主机。主机。 能够在各段能够在各段链路层提供异构服务链路层提供异构服务的情况的情况下，完成端到端的工作。下，完成端到端的工作。链路层：链路层：将网络层数据报将网络层数据报从一个节点传送到下从一个节点传送到下一个节点一个节点（单段链路）。（单段链路）。 不同的链路可采用不同的链路层协议不同的链路可采用不同的链路层协议，提，提供不同的服务。供不同的服务。12类比例类比例旅行社组织游客从旅行社组织游客从A地到地到B地。经过地。经过

7、3段旅程。段旅程。游客：游客：数据报；数据报；旅行社：旅行社：选路协议；选路协议；旅程区段：旅程区段：通信链路；通信链路；运输方式：运输方式：链路层协议，如汽车、飞机和火车。链路层协议，如汽车、飞机和火车。汽车汽车 飞机飞机 火车火车AB133、链路层能够提供的可能服务、链路层能够提供的可能服务基本服务：基本服务：将帧通过一条链路将帧通过一条链路从一个节点从一个节点“移移动动”到相邻的节点。到相邻的节点。可能服务：可能服务：r成帧：成帧：把网络层数据封装成链路层帧把网络层数据封装成链路层帧，再传，再传送到链路上。送到链路上。 包括若干字段：如编号、物理地址等包括若干字段：如编号、物理地址等 不

8、同的链路层协议，帧格式可能不同不同的链路层协议，帧格式可能不同14r多路访问控制：多路访问控制：由由媒体访问控制媒体访问控制MAC协议协调协议协调多个节点的帧的发送。一般用于多个节点共享一多个节点的帧的发送。一般用于多个节点共享一个链路的广播链路。个链路的广播链路。3、链路层提供的服务、链路层提供的服务153、链路层提供的服务、链路层提供的服务r可靠交付：可靠交付： 保证无差错地经过链路层移动网络层数据报。保证无差错地经过链路层移动网络层数据报。方法：方法：与运输层类似，与运输层类似，通过确认和重传实现，通过确认和重传实现，通常用于高差错率链路通常用于高差错率链路高差错率的链路：高差错率的链路

9、： 如无线链路，如无线链路，在本地在本地 ( (发生差错的链路发生差错的链路) )纠正差纠正差错错，不通过上层进行端到端的数据重传。，不通过上层进行端到端的数据重传。低差错率的链路：低差错率的链路： 如光纤、同轴电缆、双绞线链路，如光纤、同轴电缆、双绞线链路，不需提供不需提供链路层的可靠交付链路层的可靠交付服务。服务。16r流量控制：流量控制：防止发送节点的发送速率过高防止发送节点的发送速率过高，避，避免接收节点来不及处理。免接收节点来不及处理。链路节点的链路节点的帧缓存容量有限帧缓存容量有限。当帧到达接收节点的速率大于其处理速率，接当帧到达接收节点的速率大于其处理速率，接收方缓冲区产生溢出，

10、帧会丢失。收方缓冲区产生溢出，帧会丢失。r运输层：运输层：可为可为两个进程之间两个进程之间提供端到端可靠传提供端到端可靠传输。流量控制是在输。流量控制是在端到端端到端提供。提供。r链路层：链路层：在一条链路相连的在一条链路相连的两个节点之间两个节点之间提供提供可靠传输；可靠传输； 流量控制是在流量控制是在相邻节点相邻节点之间提供。之间提供。 3、链路层提供的服务、链路层提供的服务173、链路层提供的服务、链路层提供的服务r差错检测：差错检测：帧在传输时有可能出现帧在传输时有可能出现比特差错比特差错（10、01） 差错检测用来差错检测用来检测是否存在一个或多个比特差检测是否存在一个或多个比特差错

11、错。 发送节点：发送节点：在帧中在帧中设置设置差错检测比特；差错检测比特； 接收节点：接收节点：对收到的帧进行对收到的帧进行差错检测差错检测。 通过硬件实现。通过硬件实现。r差错纠正：差错纠正：与差错检测类似。与差错检测类似。 接收方不仅能检测帧中是否出现差错，还能接收方不仅能检测帧中是否出现差错，还能判断差错的位置，并进行判断差错的位置，并进行纠正纠正。183、链路层提供的服务、链路层提供的服务r半双工和全双工：半双工和全双工：全双工传全双工传输：输：链路两端的节点可以链路两端的节点可以同时同时传输分组。传输分组。半双工传输：半双工传输：链路两端的节点链路两端的节点不能同时不能同时传输和接传

12、输和接收，只能交替。收，只能交替。195.1.2 链路层的实现：网卡链路层的实现：网卡r网卡：网络接口卡网卡：网络接口卡NIC （Network Interface Card） 网络适配器网络适配器 （Network Adapter）r作用：作用：计算机通过计算机通过网卡与传输介质网卡与传输介质连接组成网络。连接组成网络。 90年代：年代：是是独立独立的物理的物理部件；安装在计算机的部件；安装在计算机的主板扩展槽主板扩展槽中。中。 现代：现代：大多被综合进主大多被综合进主机的主板。机的主板。 PCI PCI网卡网卡201、网卡的功能网卡的功能完成完成物理层和数据链路层物理层和数据链路层的大部分

13、功能。的大部分功能。r主要功能：主要功能：（1）帧的封装与解封帧的封装与解封（2）链路访问控制：链路访问控制：如如CSMA/CD协议的实现协议的实现（3）编码与译码：编码与译码：如曼彻斯特编码与解码如曼彻斯特编码与解码CPU存储器存储器控制器控制器物理传输物理传输主机总线主机总线适配器适配器( (网卡网卡) )主机主机链路层链路层物理层物理层上层上层链路层链路层物理层物理层212、实现链路层功能、实现链路层功能r相邻节点间帧的传输：相邻节点间帧的传输：发送节点：发送节点：网络层将网络层将数据报数据报传递到网卡，传递到网卡，封装成帧，封装成帧，将帧传输将帧传输到通信链路。到通信链路。接收节点：接

14、收节点：网卡网卡接收帧接收帧，解封，解封取出数据报，传递给网取出数据报，传递给网络层络层。控制器控制器CPU存储器存储器控制器控制器CPU存储器存储器数据报数据报数据报数据报数据报帧帧封装封装发送发送接收接收解封解封222、实现链路层功能、实现链路层功能r差错检测：差错检测： 发送网卡设置差错检测比特，接收网卡完成差错发送网卡设置差错检测比特，接收网卡完成差错检测。检测。r可靠交付：可靠交付： 采取可靠交付的机制，如序号、定时器和确认。采取可靠交付的机制，如序号、定时器和确认。r媒体访问控制：媒体访问控制：实现随机访问协议，实现随机访问协议，如如CSMA/CD234、网卡类型网卡类型按总线类型

15、分按总线类型分（1）ISA接口网卡：接口网卡：Industry Standard Architecture 工业标准体系结构。工业标准体系结构。速度低、安装麻烦。很少用速度低、安装麻烦。很少用（2）PCI接口网卡：接口网卡：Peripheral Component Interconnect 外设部件互连。外设部件互连。性价比高、安装简单。应用最广性价比高、安装简单。应用最广泛，用于台式机。泛，用于台式机。（3）USB接口网卡：接口网卡：Universal Serial Bus 通用串行总线。通用串行总线。新技术，主要用于没有内置网卡新技术，主要用于没有内置网卡的笔记本用户，通过主板上的的笔记本

16、用户，通过主板上的USB引接。引接。244、网卡类型网卡类型按总线类型分按总线类型分（4）PCMCIA接口网卡：接口网卡：个人电脑内存卡国际协会个人电脑内存卡国际协会Personal Computer Memory Card International Association 用于笔记本电脑。用于笔记本电脑。 PCI PCI网卡网卡 PCMCIA PCMCIA网卡网卡 USB USB网卡网卡254、网卡类型网卡类型 按传输速度按传输速度（1）10M网卡网卡（2）10/100M自适应网卡自适应网卡（3）10/100/1000M自适应网卡自适应网卡 按是否需要网线按是否需要网线（1）有线网卡）有线

17、网卡（2）无线网卡）无线网卡265.2 差错检测和纠错技术差错检测和纠错技术r 实现比特级差错检测和纠错实现比特级差错检测和纠错对一个节点发送到相邻节点的帧，对一个节点发送到相邻节点的帧，检测是否出现检测是否出现比特差错比特差错，并纠正。，并纠正。 相关技术很多。相关技术很多。27差错检测和纠错过程差错检测和纠错过程网络层网络层DEDC数据报数据报数据报数据报DEDC易出现比特差错的链路易出现比特差错的链路DD中所有中所有比特正确比特正确数据链路层数据链路层的帧的帧发送节点：发送节点：将将数据数据D附加若干附加若干差错检测和纠错差错检测和纠错EDC位位，一起发送，一起发送D为要保护的网络层传来

18、的为要保护的网络层传来的数据报数据报以及以及帧首部帧首部。 接收节点：接收节点：接收比特序列接收比特序列D和和EDC。根据根据D和和EDC，判断，判断D是否和初始的是否和初始的D相同相同（传输（传输是否正确）。是否正确）。 正确：正确：解封取出数据报，交给网络层；解封取出数据报，交给网络层； 出错：出错：差错处理。差错处理。28说明说明不能保证接收方检测到所有的比特差错，即不能保证接收方检测到所有的比特差错，即可能可能出现未检测到的比特差错出现未检测到的比特差错。差错检测和纠正技术有多种。差错检测和纠正技术有多种。技术越好，能检测的错误越多，但越复杂，开销技术越好，能检测的错误越多，但越复杂，

19、开销越大越大。29三种主要差错检测技术三种主要差错检测技术奇偶校验：奇偶校验：最基本的方法。最基本的方法。检查和方法：检查和方法：常用于常用于运输层运输层。循环冗余检测：循环冗余检测：常用于常用于链路层链路层。5.2.1 奇偶校验奇偶校验5.2.2 检查和方法检查和方法5.2.3 循环冗余检测循环冗余检测30 1 1、单比特奇偶校验、单比特奇偶校验r 发送方：发送方： 在要发送的信息在要发送的信息D（d位）后面位）后面附加一个奇偶校验位附加一个奇偶校验位 使使“1”的个数（的个数（ d+1位）是位）是奇数（奇数（奇校验奇校验）或或偶数（偶数（偶校偶校验验） 一起传输发送（一起传输发送（d+1位

20、）。位）。01110001101010111d位数据位数据校校验验位位偶校验偶校验311 1、单比特奇偶校验、单比特奇偶校验r 接收方：接收方： 检测收到的信息（检测收到的信息（d+1位）中位）中“1”的个数。的个数。偶校验：偶校验：发现奇数个发现奇数个“1”，至少有一个比特发，至少有一个比特发生差错，并且是奇数个比特差错。生差错，并且是奇数个比特差错。奇校验：奇校验：发现偶数个发现偶数个 “1”，至少有一个比特，至少有一个比特发生差错，并且是奇数个比特差错。发生差错，并且是奇数个比特差错。01110001101010111d位数据位数据校校验验位位偶校验偶校验32特点特点可以查出任意可以查出

21、任意奇数奇数个比特的错误，但不能发现个比特的错误，但不能发现偶数偶数个的错误。个的错误。若比特若比特出错概率很小出错概率很小，且差错独立发生，且差错独立发生，单比单比特奇偶校验可满足要求特奇偶校验可满足要求。若比特差错集中一起发生，一个帧中未检测到若比特差错集中一起发生，一个帧中未检测到差错的概率达到差错的概率达到50%。332、 二维奇偶校验（垂直水平奇偶校验）二维奇偶校验（垂直水平奇偶校验）发送方将要传数据划分发送方将要传数据划分固定长度的固定长度的组组( i 个组，每个组，每组组 j 位位)，每组一行排列；，每组一行排列；对对每行每行和和每列每列分别进行奇偶校验分别进行奇偶校验i+j+1

22、个奇偶比特与数据一起发送个奇偶比特与数据一起发送如数据：如数据：101101101100101001100划分划分3组组每组每组7个个比特比特34特点特点可以可以检测并纠正检测并纠正单个单个比特差错（数据或校验位比特差错（数据或校验位中）。中）。能够能够检测（但不能纠正）检测（但不能纠正）任意任意两个两个比特的差错。比特的差错。行、列确定行、列确定35前向差错纠正前向差错纠正FECFEC 接收方的接收方的检测和纠正差错能力检测和纠正差错能力被称为被称为前向差错纠正前向差错纠正FEC（forward error correction）。可与可与ARQ技术技术(确认重传技术确认重传技术)一起使用，

23、减少发送方重一起使用，减少发送方重发的次数发的次数适用于实时网络应用和长时延链路适用于实时网络应用和长时延链路(如卫星通信如卫星通信)365.2.2 检查和方法检查和方法TCP和和UDP协议协议：对整个分组对整个分组(其实还包括部分网其实还包括部分网络层首部字段络层首部字段)计算检查和。计算检查和。有些协议有些协议：对首部计算一个检查和，对整个分组计对首部计算一个检查和，对整个分组计算另一个检查和。算另一个检查和。37检查和检查和q发送方：发送方：将数据将数据(检查和字段置检查和字段置0)分成若干分成若干16位的块位的块；将所有将所有16 位的数求和位的数求和(高高位进位加到低位位进位加到低位

24、)求反求反，得到检查和，放入，得到检查和，放入首部检查和字段，一起发首部检查和字段，一起发送。送。q 接收方：接收方：对接收到的信息对接收到的信息 (包括检查包括检查和和)求和求和全全“1”：数据无错；：数据无错；否则否则：数据出错：数据出错38 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 例例r例，有三个例，有三个1

25、6 比特比特的字：的字：求求和和求反，得检查和求反，得检查和接收方求和应为：接收方求和应为： 1 0 1 1 0 1 0 1 0 0 1 1 1 1 0 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 139检查和特点检查和特点开销小：开销小：所用位数较少，例如所用位数较少，例如TCP, UCP只用只用16比特；比特；差错检测能力弱差错检测能力弱：适用于适用于运输层运输层（其差错检测（其差错检测用软件实现用软件实现，而检查和，而检查和方法简单、快速）。方法简单、快速）。链路层链路层的差错检测由网卡中的差错检测由网卡中的硬件实现的硬件实现，因此采用，因此采用检测能力更强、更复杂的检

26、测能力更强、更复杂的CRC方法。方法。405.2.3 循环冗余检测循环冗余检测CRC计算机网络中广泛采用。计算机网络中广泛采用。r 循环冗余检测循环冗余检测CRC (cyclic redundancy check)编码编码 又称为又称为多项式编码多项式编码，把要发送的比特串看作，把要发送的比特串看作为为系数是系数是0或或1的一个多项式，对比特串的操作看的一个多项式，对比特串的操作看作为多项式运算。作为多项式运算。 如比特串如比特串10111 ： x4+x2+x+141核心思想核心思想1. 双方约定好一个双方约定好一个r+1位的除数位的除数G（如（如G=101）；）；2. 发送方：发送数据为发送

27、方：发送数据为D（如（如D=1101），在其后加一个），在其后加一个r位的冗余位的冗余码码R，使得，使得DR能被能被G整除，发送整除，发送DR.3. 接收方：接收到接收方：接收到DR，如果：，如果： DR能被能被G整除：无错，整除：无错， DR不能被不能被G整除：出错整除：出错关键算法：求冗余码关键算法：求冗余码R DR % G = 0 R =D 00 % G （G为为r+1位，则位，则R为为r位）位） 1011 xx % 101 = 0 xx =1011 00 % 101=10 即：即： DR= 101110r位位42CRC基本思想基本思想假设：假设：发送节点要发送的发送节点要发送的数据数据

28、D (d 比特比特)双方事先约定一个双方事先约定一个生成多项式生成多项式 G (r+1比特比特)，其最其最高位高位 (最左边最左边)为为1。r发送方：发送方：计算出一个计算出一个冗余码冗余码 R (r比特比特)，添加到添加到D的后面产的后面产生生DR (d+r 比特比特)，一起发送。一起发送。特点特点：DR能被能被 G 整除整除(采用模采用模2运算运算)D : 数据（数据（d位）位）R : 冗余码冗余码（r位）位）DR（d+r 位）位）43r接收方：接收方：将收到的将收到的DR除以除以G，采用模，采用模2运算运算整除：传输正确，去掉尾部整除：传输正确，去掉尾部r位，得所需数据位，得所需数据D不

29、能整除：传输发生差错不能整除：传输发生差错CRC基本思想基本思想D : 要发送的数据（要发送的数据（d位）位）R : 冗余码冗余码（r位）位）DR（d+r 位）位）44模模2运算运算加法和减法不进位不借位加法和减法不进位不借位，都等同于按位，都等同于按位异或异或 (XOR)例例 1011+0101=1110; 1011 XOR 0101=1110 1001-1101=0100; 1001 XOR 1101=0100乘法和除法与二进制运算类似：乘法和除法与二进制运算类似：乘以乘以2r，即以比特模式左移，即以比特模式左移r个位置个位置。 D2r = D0000 (r 个个 0)DR (d+r比特比

30、特) = D0000 XOR R = D2r XOR R 45如何计算如何计算R RDR能能被被G模模2运算整除运算整除：即：即 DR = D2r XOR R = nG 等式两边都用等式两边都用R异或，得到异或，得到 D2r = nG XOR R（相当于：相当于：D2r = nG +R） 即即R等于等于D2r除以除以G所得的余数所得的余数R的计算：的计算：将数据将数据D后面添加后面添加r个个0，除以给定的生成，除以给定的生成多项式多项式G (r+1位位)，所得，所得余数即为余数即为R (r位位)。46例例设设 D = 101110，d = 6，G = 1001，r = 3实际传输的数据是实际传

31、输的数据是101110011r+1位位D后添加后添加3个个0余数取余数取3位，得位，得R相减不借位相减不借位就算是就算是1000也要商也要商147循环冗余检测循环冗余检测r 国际标准已定义了国际标准已定义了8、12、16和和32 位的生成多项位的生成多项式式G。 8 比特比特的的CRC用于保护用于保护ATM信元首部；信元首部； 32 比特比特的的CRC-32用于用于链路层的链路层的IEEE协议：如协议：如 GCRC-32 = 100000100110000010001110110110111rCRC特点：特点：能检测能检测小于小于r+1 比特比特的差错和任何的差错和任何奇奇数个比特数个比特的差

32、错。的差错。485.3 多路（址）访问协议多路（址）访问协议r两种网络链路：两种网络链路：点对点链路：点对点链路：链路两端各一个节点链路两端各一个节点。一个发送和一。一个发送和一个接收。可采用点到点协议个接收。可采用点到点协议PPP。广播链路：广播链路： 多个节点连接到一个共享的广播信道多个节点连接到一个共享的广播信道 任何节点传输时，信号在信道上广播，其他节点都任何节点传输时，信号在信道上广播，其他节点都可以收到一个拷贝。可以收到一个拷贝。 常用于局域网常用于局域网LAN中，如传统以太网和无线局中，如传统以太网和无线局域网。本节主要学习域网。本节主要学习广播链路中的信道共享技术。广播链路中的

33、信道共享技术。49多路访问协议多路访问协议r目的：目的：避免避免广播链路中多个节点同时广播链路中多个节点同时使用信道，使用信道，发生冲突发生冲突。冲突（冲突（collide）：）：两个以上的节点同时传输帧两个以上的节点同时传输帧，使接收方收不到正确的帧使接收方收不到正确的帧(所有冲突的帧都会受所有冲突的帧都会受损损)，造成广播信道时间的浪费。，造成广播信道时间的浪费。 r可用于许多不同的网络环境可用于许多不同的网络环境, 如有线和无线局域如有线和无线局域网、卫星网等网、卫星网等:50共享无线共享无线（如（如WiFi）共享无线共享无线（如卫星）（如卫星） 共享线路共享线路（如总线以太网）（如总线

34、以太网）聚会聊天聚会聊天共享空气共享空气51多路访问协议的理想特性多路访问协议的理想特性设广播信道的速率为设广播信道的速率为R b/s只有只有一个节点发送数据一个节点发送数据时：该节点的吞吐量为时：该节点的吞吐量为R b/s有有N个节点发送数据个节点发送数据时：每个节点吞吐量为时：每个节点吞吐量为 R/N b/s协议是协议是分散的分散的：不需要主节点协调传输：不需要主节点协调传输协议是协议是简单的简单的：实现方便、价格适中：实现方便、价格适中52多路访问协议的类型多路访问协议的类型r信道划分协议信道划分协议m划分信道，给不同节点分配不同的时隙、频划分信道，给不同节点分配不同的时隙、频率或编码方

35、式率或编码方式 r随机访问协议随机访问协议m不划分信道，不划分信道，允许冲突允许冲突m能从冲突中能从冲突中“恢复恢复”r轮流协议轮流协议m节点轮流访问信道来节点轮流访问信道来避免冲突避免冲突m发送节点越多，轮流时间越长发送节点越多，轮流时间越长535.3.1 信道划分协议信道划分协议主要类型：主要类型：TDM、FDM、CDMA三种。三种。设信道支持设信道支持N个节点，且传输速率是个节点，且传输速率是R b/s。54时分多路复用（时分多路复用（TDM）将信道传输时间划分为将信道传输时间划分为时间帧时间帧，每个时间帧再，每个时间帧再划分为划分为N个时隙个时隙（长度保证能发送一个分组），（长度保证能

36、发送一个分组），分别分配给分别分配给N个节点。个节点。 每个节点只在每个节点只在固定分配的时隙固定分配的时隙中传输。中传输。 例：例：6个站点的个站点的LAN, 时隙时隙1、3、4 有分组有分组, 时隙时隙2、5、6 空闲空闲 1 13 34 41 13 34 4时间帧时间帧55TDM特点特点避免冲突、公平避免冲突、公平：每个节点专用速率：每个节点专用速率R/N b/s节点速率有限、效率不高节点速率有限、效率不高：R/N b/s56 将信道带宽将信道带宽划分为划分为N个较小频段个较小频段，带宽分别为，带宽分别为R/N，分配给分配给N个节点。个节点。 例：例： 6个站点的个站点的LAN, 频带频

37、带1、3、4 有分组有分组, 频频带带2、5、6 空闲空闲频分多路复用（频分多路复用（FDM）frequency bandstime57FDM特点特点与与TDM类似。类似。 避免冲突、公平避免冲突、公平：N个节点公平划分带宽；个节点公平划分带宽； 节点带宽有限、效率不高节点带宽有限、效率不高：节点带宽为：节点带宽为R/N。58码分多址码分多址CDMA (code division multiple access)q基本思想：基本思想：给每个节点分配不同的编码方式；给每个节点分配不同的编码方式；每个节点每个节点用惟一的编码用惟一的编码对要发送的数据进行编码对要发送的数据进行编码不同节点可以同时发

38、送不同节点可以同时发送，并正确到达接收方（不，并正确到达接收方（不会互相干扰）。会互相干扰）。第第6章将详细介绍。章将详细介绍。r最初：最初：用于军事通信，抗干扰能力强；用于军事通信，抗干扰能力强； 目前：目前：用于无线蜂窝移动通信等。用于无线蜂窝移动通信等。595.3.2 随机访问协议随机访问协议q基本思想：基本思想：发送节点以信道全部速率（发送节点以信道全部速率（R b/s）发送；）发送；发生发生冲突冲突时，冲突的每个节点分别时，冲突的每个节点分别等待等待一个随一个随机时间，再机时间，再重发重发，直到发送成功。，直到发送成功。q典型的随机访问协议：典型的随机访问协议：ALOHA协议协议CS

39、MA协议协议CSMA/CD协议协议60ALOHAqALOHA： 20世纪世纪70年代初，夏威夷大学研制年代初，夏威夷大学研制的一个无线电广播通信网。的一个无线电广播通信网。 采用采用星型拓扑结构星型拓扑结构，地理上分散的用户通，地理上分散的用户通过无线电使用中心主机。过无线电使用中心主机。 中心主机通过中心主机通过下行信道下行信道向二级主机向二级主机广播广播分组；分组；二级主机通过二级主机通过上行信道上行信道向中心主机发送分组向中心主机发送分组（无线电信道是一个公用信道，可能会（无线电信道是一个公用信道，可能会冲突冲突）r有若干种形式：有若干种形式： 时隙时隙ALOHA 纯纯ALOHA中心61

40、1、时隙时隙ALOHA假设：假设：所有的所有的帧长帧长 L 比特比特；时间被时间被划分为若干等长的时隙划分为若干等长的时隙（长度为一帧的（长度为一帧的传输时间传输时间L/R s）；）；节点只节点只在时隙的开始点传输帧在时隙的开始点传输帧；所有所有节点同步传输节点同步传输，知道时隙什么时候开始；，知道时隙什么时候开始；如果一个时隙的开始点有如果一个时隙的开始点有多个节点同时传送多个节点同时传送，所有节点都所有节点都能检测到冲突。能检测到冲突。62时隙时隙ALOHA操作过程操作过程当节点有新的帧要发送，需等到当节点有新的帧要发送，需等到下一个时隙开下一个时隙开始始，才能发送。发送时有两种情况：，才

41、能发送。发送时有两种情况：无冲突：无冲突：节点成功传输帧。节点成功传输帧。有冲突：有冲突：节点检测到冲突后，以节点检测到冲突后，以概率概率p (0 p =1) 在后续的每一个时隙重传该帧，直到成功。在后续的每一个时隙重传该帧，直到成功。重传重传C:C:碰撞时隙碰撞时隙E:E:空闲时隙空闲时隙S:S:成功时隙成功时隙63特点特点当只有当只有一个节点一个节点要发送时，信道以要发送时，信道以全速全速R传输。传输。分散的分散的：每个节点检测冲突并每个节点检测冲突并独立决定独立决定何时重何时重传；传；发送控制简单；发送控制简单；有有多个活动节点时效率低多个活动节点时效率低。64三种可能的时隙三种可能的时

42、隙冲突时隙冲突时隙C：出现帧冲突，被出现帧冲突，被“浪费浪费”。空闲时隙空闲时隙E：所有活动节点停止传输，被所有活动节点停止传输，被“浪浪费费”成功时隙成功时隙S：只有一个节点在传输的时隙。只有一个节点在传输的时隙。65效率（效率（efficiency） 当有许多活动节点时，当有许多活动节点时，在发送的许多帧在发送的许多帧中，成功时隙所占的份额。中，成功时隙所占的份额。最低效率情况：最低效率情况：没有任何访问控制，每个节点没有任何访问控制，每个节点都在冲突之后立即重传，都在冲突之后立即重传，效率为零效率为零。66效率计算效率计算r假设：假设：有有N个节点；个节点；每个节点都有一帧（新帧或重传帧

43、）要发送，每个节点都有一帧（新帧或重传帧）要发送，试图在每个时隙以试图在每个时隙以概率概率p传输。传输。r成功时隙的概率成功时隙的概率：即：即只有一个节点传输而其他只有一个节点传输而其他N-1个节点不传输的概率：个节点不传输的概率： p(1-p)N-167时隙时隙ALOHA的效率的效率N个节点中，个节点中，任意节点任意节点成功传送的概率：成功传送的概率： Np(1-p)N-1N趋于无穷时，取极限，趋于无穷时，取极限，最大效率为最大效率为1/e = 0.37 即当许多节点都有帧要传输时，最多只有即当许多节点都有帧要传输时，最多只有37%的时隙在成功传输的时隙在成功传输，信道有效的传输速率是，信道

44、有效的传输速率是0.37R b/s。类似可得出：剩余的时隙类似可得出：剩余的时隙37%为空，为空，26%有冲突。有冲突。682、纯、纯ALOHA ALOHA的最初形式。是一个的最初形式。是一个非时隙、完全分散非时隙、完全分散的随机接入的随机接入协议。协议。时隙时隙ALOHA：所有所有节点同步传输节点同步传输，知道时隙什么时候开始；，知道时隙什么时候开始；纯纯ALOHA： 没有时隙，节点间不同步，任何时刻都可能传没有时隙，节点间不同步，任何时刻都可能传 （只要收到上层分组，就立即传输）（只要收到上层分组，就立即传输）q工作过程：工作过程：节点节点有帧要发，就立即传输有帧要发，就立即传输。如果与其

45、他帧产生冲突，在该冲突帧传完之后如果与其他帧产生冲突，在该冲突帧传完之后 以以概率概率p立即重传该帧；立即重传该帧； 否则等待一个帧的传输时间，再以否则等待一个帧的传输时间，再以概率概率p传输该帧，传输该帧， 直到成功直到成功为止。为止。69纯纯ALOHA最大效率最大效率r假设：假设：帧的传输时间为帧的传输时间为一个时间单元一个时间单元。任何给定时间，某个节点传输一帧的概率是任何给定时间，某个节点传输一帧的概率是p节点节点 i 在时间在时间t0开始传输帧，如图所示。开始传输帧，如图所示。r结果：结果：在在t0发送的帧会和其他节点在发送的帧会和其他节点在 t0-1, t0+1 发送的其它帧冲突。

46、发送的其它帧冲突。与与 i 帧开始帧开始部分重叠部分重叠与与 i 帧结束帧结束部分重叠部分重叠70r保证保证 i 帧成功传输：帧成功传输：在时间间隔在时间间隔t0 -1，t0中，不能有其他节点开始传中，不能有其他节点开始传输，输，概率是概率是(1-p)N-1并且当节点并且当节点 i 传输时，在时间间隔传输时，在时间间隔t0 , t0+1中，也中，也不能有其他节点开始传输，不能有其他节点开始传输，概率是概率是(1-p)N-171纯纯ALOHA效率效率P(给定节点给定节点成功传送成功传送) = P(节点传送节点传送) P(没有其他节点在没有其他节点在t0-1, t0内传送内传送) P(没有其他节点

47、在没有其他节点在t0, t0 +1内传送内传送) = p . (1-p)N-1 . (1-p)N-1 = p . (1-p)2(N-1) 取极限为取极限为 1/(2e) = 0.185 效率只有时隙效率只有时隙ALOHA协议的一半。协议的一半。72ALOHA协议特点协议特点各节点的活动是相互各节点的活动是相互独立独立的。的。一个节点开始传输时一个节点开始传输时不知道是否不知道是否有其他节点正有其他节点正在传输。在传输。发生发生冲突时不会停止冲突时不会停止传输。传输。效率不高效率不高。733、改进方法、改进方法增加两个规则。增加两个规则。r载波侦听载波侦听CS：某个节点在发送之前，先监听信某个节

48、点在发送之前，先监听信道道。信道忙：信道忙：有其他节点正发送帧，该节点有其他节点正发送帧，该节点随机等待一随机等待一段时间段时间，然后再侦听信道。，然后再侦听信道。信道空：信道空：该节点该节点开始传输帧开始传输帧。r冲突检测冲突检测 CD ：边发送边监听边发送边监听，即节点在传输同时，即节点在传输同时侦听信道。侦听信道。 如果检测到有其他节点也在传输帧，如果检测到有其他节点也在传输帧，发生冲发生冲突，立即停止传输突，立即停止传输，并用某种方法来决定何时再重，并用某种方法来决定何时再重新传输。新传输。74两种相应的协议两种相应的协议载波侦听多路访问载波侦听多路访问CSMA（carrier sen

49、se multiple access）带冲突检测的载波侦听多路访问带冲突检测的载波侦听多路访问CSMA/CD (CSMA with collision detection)75CSMA 只增加只增加“载波侦听载波侦听”规则。规则。r基本原理：基本原理： 传送前侦听传送前侦听信道闲：信道闲：传送整个帧传送整个帧信道忙：信道忙：延迟再侦听延迟再侦听r特点：特点：发前侦听，可发前侦听，可减少冲突减少冲突。由于传播由于传播时延时延的存在，仍有的存在，仍有可能出现冲突，并造成可能出现冲突，并造成信道浪费信道浪费。76例例 一个广播总线依次连接一个广播总线依次连接4个节点个节点(A、B、C、D)，传输的时

50、空图：，传输的时空图：节点空间分布节点空间分布 77时间时间 t0：节点节点B侦听到侦听到信道空，开始传输帧，信道空，开始传输帧，沿着媒体传播比特。沿着媒体传播比特。时间时间 t1 (t1 t0)：节点节点D有帧要发送。有帧要发送。B的传输的传输信号未到信号未到D，D检测到信检测到信道空道空，开始传输。，开始传输。 很快，很快，B的传输开始的传输开始在在D节点干扰节点干扰D的传输的传输（冲突）。（冲突）。传输过程传输过程78 信号从一个节点传信号从一个节点传播到另一个节点所花费播到另一个节点所花费的时间。的时间。 传播时延越长，节传播时延越长，节点不能侦听到另一个节点不能侦听到另一个节点已经开

51、始传输的可能点已经开始传输的可能性越大。性越大。端到端信道传播时延端到端信道传播时延79CSMA主要问题主要问题节点没有进行冲突检测节点没有进行冲突检测，发，发送后既使发生了冲突也不知送后既使发生了冲突也不知道，节点仍继续传输整个道，节点仍继续传输整个帧。帧。该帧已经被破坏、是无用的该帧已经被破坏、是无用的帧。浪费信道传输时间。帧。浪费信道传输时间。80带冲突检测的带冲突检测的CSMA(CSMA/CD) 增加增加“载波侦听载波侦听”和和“冲突检测冲突检测”规则。规则。r 基本原理：基本原理： 传送前侦听传送前侦听信道忙：信道忙：延迟再侦听延迟再侦听信道闲：信道闲：发送整个帧发送整个帧发送同时进

52、行发送同时进行冲突检测：冲突检测：一旦检测到冲突就立一旦检测到冲突就立即停止传输，即停止传输， 尽快重发。尽快重发。r可缩短无效传送时间，可缩短无效传送时间，提高信道的利用率提高信道的利用率81例例 两个节点两个节点B、D在检测到冲突之后很短的时间在检测到冲突之后很短的时间内都放弃传输。内都放弃传输。传统的以太网采传统的以太网采用用CSMA/CD协议协议检测到冲突，检测到冲突，很快放弃传输很快放弃传输825.3.3 轮流协议轮流协议r多路访问协议的理想特性：多路访问协议的理想特性：只有只有一个节点一个节点活动时，吞吐量活动时，吞吐量R bps；有有N个节点个节点活动时，吞吐量活动时，吞吐量R/

53、N bps。 信道划分协议满足第二个特性，不满足第信道划分协议满足第二个特性，不满足第一个；随机接入协议满足第一个，但不满足第一个；随机接入协议满足第一个，但不满足第二个。二个。两种轮流协议：两种轮流协议：1、轮询协议、轮询协议2、令牌传递协议、令牌传递协议831、轮询协议、轮询协议 (polling protocol)r指定一个主节点，以循环的方式轮询每个节指定一个主节点，以循环的方式轮询每个节点点。并告诉节点能够传输的最大帧数。并告诉节点能够传输的最大帧数。r轮询顺序：轮询顺序： 1 2 n 主节点通过观察信道上是否有信号来判断主节点通过观察信道上是否有信号来判断节点是否完成了帧的发送，再

54、询问下一节点。节点是否完成了帧的发送，再询问下一节点。数据帧数据帧主节点主节点12n轮询轮询帧帧84轮询协议的特点轮询协议的特点消除了冲突和空时隙消除了冲突和空时隙，效率高。，效率高。有轮询时延有轮询时延：活动节点不能立即传输帧，要等：活动节点不能立即传输帧，要等待轮询；待轮询；如果主节点失效，整个信道都不能用。如果主节点失效，整个信道都不能用。852、令牌传递协议、令牌传递协议 (token-passing protocol)没有主节点，一般用于环形网和总线网。没有主节点，一般用于环形网和总线网。设置一个设置一个令牌令牌T(token，小的专用帧，小的专用帧)；令牌令牌以固定顺序循环传递以固

55、定顺序循环传递， 如：如：1 2 n节点收到令牌，才有权发送：节点收到令牌，才有权发送： 有帧要发送，传输，有帧要发送，传输，传完后将令牌转发传完后将令牌转发到下一节点到下一节点 否则，否则，直接将令牌转发直接将令牌转发到下一节点。到下一节点。T86特点特点令牌传递是令牌传递是分散的，效率高分散的，效率高。一个一个节点的失效节点的失效会使整个信道崩溃。会使整个信道崩溃。一个节点忘记释放令牌，必须恢复令牌到环中一个节点忘记释放令牌，必须恢复令牌到环中 相应协议标准：如相应协议标准：如FDDI和和IEEE802.5令牌环协议。令牌环协议。875.3.4 局域网局域网 (LAN)qLAN：是一个是一

56、个地理范围小地理范围小的计算机网络。的计算机网络。q特点：特点： 地理地理范围小范围小：几公里。如一栋楼，一所大学。：几公里。如一栋楼，一所大学。可使用可使用多路访问控制协议多路访问控制协议：如：如CSMA/CD。数据数据传输速率高传输速率高：10Mb/s、100Mb/s、1Gb/s、10G b/s一个单位拥有一个单位拥有LAN只有物理层和数据链路层只有物理层和数据链路层88局域网的拓扑结构局域网的拓扑结构 星形、环形、总线、树形星形、环形、总线、树形89局域网的应用局域网的应用范围广。范围广。r典型应用：典型应用：单位用户单位用户通过通过LAN接入因特网。接入因特网。 用户主机用户主机先组成

57、先组成LAN，LAN通过路由器通过路由器接接入因特网。入因特网。90局域网的协议标准局域网的协议标准IEEE 802标准系列。标准系列。qIEEE 802委员会：委员会：电子和电气工程师协会电子和电气工程师协会IEEE在在1980年年2月成立的一个分委员会，专门制订局月成立的一个分委员会，专门制订局域网的相关标准。域网的相关标准。 q典型标准：典型标准：IEEE 802.3：CSMA/CD以太网以太网IEEE 802.4：令牌总线网：令牌总线网IEEE 802.5：令牌环形网：令牌环形网IEEE 802.11：无线局域网：无线局域网915.4 链路层编址链路层编址 每个节点有每个节点有网络层地

58、址和链路层地址网络层地址和链路层地址。r网络层地址：网络层地址：如因特网中的如因特网中的IP地址地址。用于把用于把IP数据数据报报送到目的主机（通常位于其他网络）送到目的主机（通常位于其他网络）。长度为长度为32比特（比特（IPv4）。）。 包括两部分：包括两部分：网络号：网络号：指明主机所在指明主机所在物理网络的编号物理网络的编号。主机号：主机号：主机主机在物理网络中的在物理网络中的编号。编号。r链路层地址：链路层地址：如如MAC地址地址。 用于把数据帧从用于把数据帧从一个节点传送到另一个节点一个节点传送到另一个节点(同一网络中同一网络中)。长度为。长度为48个比特。个比特。925.4.1

59、MAC地址地址qMAC地址地址（LAN地址、地址、物理地址、硬件地物理地址、硬件地址址）：）：是一个是一个全局地址全局地址，世界范围，世界范围惟一惟一。是节点的是节点的网卡所带的、永久的地址网卡所带的、永久的地址（生产时固化（生产时固化在网卡的在网卡的ROM里）。里）。MAC地址长度通常为地址长度通常为6 字节字节，共，共248个。个。6字节地址用字节地址用16进制表示进制表示，每个字节表示为一对，每个字节表示为一对16进制数。进制数。如图所示：如图所示：93例例1A-2F-BB-76-09-AD58-23-D7-FA-20-B00C-C4-11-6F-E3-9871-65-F7-2B-08-

60、53 LAN(有线的有线的或无线的或无线的)适配器（网卡）适配器（网卡）在控制台中使用在控制台中使用 ipconfig /all 可查看可查看94MAC地址的分配地址的分配rIEEE管理机构管理机构负责分配负责分配前三个字节，后三个字节前三个字节，后三个字节由设备厂商对设备网卡进行分配。由设备厂商对设备网卡进行分配。MAC地址是平面结构：地址是平面结构：带有同一网卡的节点，在带有同一网卡的节点，在任何网络中任何网络中都有同样的都有同样的MAC地址地址。IP地址是层次结构：地址是层次结构：当节点移动到当节点移动到不同网络不同网络时，时，节点的节点的IP地址发生改变。其网络号部分指明所在地址发生改