计算机网络第5章

1、链路层和局域网5-1第五章第五章 数据链路层和数据链路层和局域网局域网链路层和局域网5-2第第 5 章章: 数据链路层和局域网数据链路层和局域网目的目的: p了解数据链路层服务及协议原理了解数据链路层服务及协议原理:m差错检测和纠错差错检测和纠错m共享广播信道：多路访问协议共享广播信道：多路访问协议m链路层寻址链路层寻址m可靠传输，流量控制可靠传输，流量控制p各种链路层技术的实现各种链路层技术的实现链路层和局域网5-3链路层链路层p5.1 概述和服务概述和服务p5.2差错检测和纠差错检测和纠错技术错技术p5.3多址访问协议多址访问协议p5.4链路层编址链路层编址p5.5以太网以太网p5.6集线

2、器和交换集线器和交换机机p5.7 PPPPPP：点到点协：点到点协议议p5.8链路虚拟化链路虚拟化: ATM ATM 和和 MPLSMPLS链路层和局域网5-4链路层：介绍链路层：介绍常用术语常用术语:p节点：节点：主机和路由器主机和路由器(包括网桥包括网桥和交换机和交换机)p 链路：链路：沿着通信路径连接相邻沿着通信路径连接相邻节点的通信信道节点的通信信道p 有线链路有线链路p 无线链路无线链路p 局域网局域网p帧：帧：链路层协议交换的数据单链路层协议交换的数据单元。封装网络层数据报元。封装网络层数据报数据链路层的职责：将数据链路层的职责：将分组通过一个链路，从分组通过一个链路，从一个节点传

3、输到临近的一个节点传输到临近的另一个节点。另一个节点。“link”链路层和局域网5-5链路层的特点链路层的特点p分组传输可以经过不同的分组传输可以经过不同的链路使用不同的协议实现链路使用不同的协议实现:m例如，最初的链路是以太网例如，最初的链路是以太网，然后是帧中继，最后的是，然后是帧中继，最后的是802.11p每个链路协议提供不同的每个链路协议提供不同的服务服务m例如，可以在链路上提供或例如，可以在链路上提供或不提供可靠的传输不提供可靠的传输传输类比传输类比p从成都到九寨沟的旅途从成都到九寨沟的旅途m打的：打的：成都某地到成都机场成都某地到成都机场m飞机：成都机场到九寨沟机飞机：成都机场到九

4、寨沟机场场m大巴：九寨沟机场到清华风大巴：九寨沟机场到清华风景区景区p旅客旅客 = 数据包数据包p运输段运输段 = 通信链路通信链路p运输模式运输模式 = 链路层协议链路层协议p旅行社旅行社 = 路由算法路由算法链路层和局域网5-6链路层服务链路层服务p成帧：成帧：m把网络层数据报加头和尾，封装成帧把网络层数据报加头和尾，封装成帧m帧头中包括指明目的和源的帧头中包括指明目的和源的“物理地址物理地址”（不同于（不同于IP地址）地址）p链路访问：链路访问：m媒体访问控制（媒体访问控制（Medium Access Control，MAC）协议）协议m共享媒体的多路访问共享媒体的多路访问 p在邻接节点

5、间的可靠传输在邻接节点间的可靠传输m我们已经在第三章学习了怎么做！我们已经在第三章学习了怎么做！m在出错率很低的链路上很少用在出错率很低的链路上很少用 (光纤，部分双绞线光纤，部分双绞线)m无线链路：高出错率无线链路：高出错率 问题：为何链路层和端到端的层都要提供可靠性服务问题：为何链路层和端到端的层都要提供可靠性服务?链路层和局域网5-7链路层服务链路层服务(续续)p流量控制：流量控制：m在邻接的发送节点和接收节点间的同步调节在邻接的发送节点和接收节点间的同步调节p差错检测差错检测:m差错由信号衰减和噪声引起差错由信号衰减和噪声引起m接收者检测错误：如果发现差错接收者检测错误：如果发现差错

6、发送者重传帧或丢帧发送者重传帧或丢帧p纠错：纠错：m接收者检测和纠正错误，不需发送者重传接收者检测和纠正错误，不需发送者重传p半双工和全双工半双工和全双工m半双工，一个节点不能同时传输和接收半双工，一个节点不能同时传输和接收m全双工，节点可以同时传输和接收全双工，节点可以同时传输和接收链路层和局域网5-8适配器通信适配器通信p链路层在链路层在 “适配器适配器” (网网卡卡)中实现中实现 mEthernet卡，卡，PCMCIA卡，卡， 802.11卡卡p发送方：发送方：m封装分组成帧封装分组成帧m增加检错位、可靠传输、流增加检错位、可靠传输、流量控制等量控制等p接收方接收方m检测差错、可靠交付、

7、流量控检测差错、可靠交付、流量控制等制等m提取分组，传给接收节点提取分组，传给接收节点p适配器是半自治的适配器是半自治的p链路层链路层 & 物理层物理层发送节发送节点点帧帧接收节点接收节点数据报数据报帧帧适配器适配器适配器适配器链路层协议链路层协议链路层和局域网5-9链路层链路层p5.1 概述和服务概述和服务p5.2差错检测和纠差错检测和纠错技术错技术p5.3多址访问协议多址访问协议p5.4链路层编址链路层编址p5.5局域网概述局域网概述p5.6以太网以太网p5.7集线器和交换集线器和交换机机p5.8 PPPPPP：点到点协：点到点协议议p5.9链路虚拟化链路虚拟化: ATM ATM

8、和和 MPLSMPLS链路层和局域网5-10差错检测差错检测错误检测不是错误检测不是100%可靠！可靠！ 协议有可能漏掉一些错误，但很少协议有可能漏掉一些错误，但很少 大的校验信息域能提供更好的检错能力大的校验信息域能提供更好的检错能力用户数据用户数据 校验信息校验信息传输信道传输信道用户数据用户数据差错检测差错检测算法算法用户数据用户数据校验信息校验信息用户数据用户数据差错检测差错检测算法算法是否相等是否相等是是错误处理错误处理否否链路层和局域网5-11奇偶校验奇偶校验单个奇偶位单个奇偶位: :检测奇数个位的错误检测奇数个位的错误事实上，发生未检测到错误的概率为事实上，发生未检测到错误的概率

9、为50%-50%-有必要深入研究有必要深入研究r奇校验奇校验: :用户数据和校验信息中用户数据和校验信息中1 1的个数为奇的个数为奇数个。数个。r偶校验偶校验: :用户数据和校验信息中用户数据和校验信息中1 1的个数为偶的个数为偶数个。数个。10011001奇校验：奇校验：10011001 1链路层和局域网5-12奇偶校验奇偶校验单个奇偶位单个奇偶位:检测单个位的错误检测单个位的错误二维偶数奇偶校验二维偶数奇偶校验:检测和纠正单个位的错误检测和纠正单个位的错误,检测任意组合的两个错误检测任意组合的两个错误00一比特偶校验一比特偶校验事实上，发生未检测到事实上，发生未检测到错误的概率为错误的概率

10、为50%-有必要深入研究有必要深入研究链路层和局域网5-13InternetInternet校验和校验和发送方发送方: :r把数据段内容看成把数据段内容看成16-16-bitbit的整数序列的整数序列r检查和：把数据段内容检查和：把数据段内容加起来加起来, ,求反码求反码r发送方把校验和放入发送方把校验和放入UDPUDP的校验和域的校验和域接收方：接收方：r计算接收字段的校验和计算接收字段的校验和r检测计算的校验和与校验检测计算的校验和与校验和域的值是否相等：和域的值是否相等：lNO NO 检测到错误检测到错误lYES YES 没有检测到错没有检测到错误。误。但可能有错但可能有错. .目标目标

11、: : 检测在传输数据段中的检测在传输数据段中的 “错误错误”链路层和局域网5-14Internet Internet 校验和例子校验和例子1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 01 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 0 1 1 1 0 1 1 1 0 1 1 1 0 1 111 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0累加和累加和0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1校验和校验和变反变反求和求和回卷回卷求和时产生的进位必求和时产生的进位必须回卷加到结果上须回卷加到结果上最后的累加和必须按位最后的累加和

12、必须按位变反才是校验和变反才是校验和链路层和局域网5-15循环冗余校验循环冗余校验CRCCRC（Cyclic Redundancy CheckCyclic Redundancy Check）基本思想：基本思想：r把数据把数据D D，看成，看成d d位二进制数位二进制数r发送方与接收方商定一个发送方与接收方商定一个r+1r+1位模式位模式 ( (生成多项式生成多项式), G ), G r目标目标: : 选择选择r r位循环冗余位位循环冗余位, , R R, , 将它们添加到将它们添加到D D后面形成要发送的数据后面形成要发送的数据D, ，要求满足下列特性：，要求满足下列特性：l D, 的的d+r

13、d+r位二进制数使用模位二进制数使用模2 2运算能被运算能被r+1r+1位的二进制数位的二进制数 G G整除整除l接收方用接收方用G G去除接收到的去除接收到的D, 的的d+rd+r位二进制数，如果余数非零，错位二进制数，如果余数非零，错误发生；否则，正确。误发生；否则，正确。链路层和局域网5-16循环冗余校验循环冗余校验CRCCRC数学表达式为：数学表达式为：能被能被G G整除整除, ,即即: :D D. .2 2r r XOR R = nG XOR R = nGR = remainder D.2rG如果用如果用G G来除来除 D.2D.2r r ，余数等于，余数等于R : R : 两边都异

14、或两边都异或R:R:D D. .2 2r r = nG XOR R = nG XOR R 链路层和局域网5-17CRCCRC例子例子链路层和局域网5-18CRCCRC练习练习假设假设: :通信双方协商的生成多项式为通信双方协商的生成多项式为: : G=X G=X4 4+X+X2 2+X+1+X+1发送放要发送的数据为发送放要发送的数据为: : D=11001100 D=11001100问题问题: :CRCCRC校验信息需要多少位校验信息需要多少位? ?发送方最终发送的数据是多少位发送方最终发送的数据是多少位? ?发送方最终发送的数据内容是什么发送方最终发送的数据内容是什么? ?如果传输过程中出

15、现一位错误能否检测如果传输过程中出现一位错误能否检测? ?出现六位错出现六位错误能否检测误能否检测? ?链路层和局域网5-19r国际标准已经定义了国际标准已经定义了8-、16-、32-位生成多项位生成多项式式G；8-位位CRC用于用于ATM头部头部5字节的保护；字节的保护；32-CRC用于大量链路层用于大量链路层IEEE协议。协议。r其他检错方法不常用，故不作专门介绍其他检错方法不常用，故不作专门介绍循环冗余校验循环冗余校验CRCCRC链路层和局域网5-20r奇偶校验能力最弱，奇偶校验能力最弱，CRC校验能力最强。校验能力最强。r奇偶校验奇偶校验通常用于简单的串口通信通常用于简单的串口通信r校

16、验和校验和通常应用于通常应用于网络层及其之上网络层及其之上的层次，要的层次，要求简单快速的求简单快速的软件实现软件实现方式方式rCRC通常应用于通常应用于链路层链路层，一般由适配器，一般由适配器硬件实硬件实现现。差错检测方法比较差错检测方法比较链路层和局域网5-21 为了校错和纠错，我们在发送方对信息位进行编码，为了校错和纠错，我们在发送方对信息位进行编码，而在接收方进行解码，以还原信息。编码的原理是增加冗而在接收方进行解码，以还原信息。编码的原理是增加冗余信息检验位。余信息检验位。 假设要传送的信息为假设要传送的信息为m位，校验位为位，校验位为r位，则编码的位，则编码的总长度为总长度为mr位

17、。所谓编码就是把位。所谓编码就是把m位信息码映射为位信息码映射为mr位的编码。但是位的编码。但是m位信息仅有位信息仅有2m种信息码，而种信息码，而mr位则位则有有2mr种编码。因此我们把种编码。因此我们把mr位的编码分为两大类：位的编码分为两大类：有效码和无效码，有效码指与信息码有一一映射关系的编有效码和无效码，有效码指与信息码有一一映射关系的编码，所以有效码只有码，所以有效码只有2m个。而其余的编码则称之为无效码个。而其余的编码则称之为无效码，无效码共有，无效码共有2n2m=2mr2m=（2r1）2m个。发方进个。发方进行编码就是把信息码映射为有效码。行编码就是把信息码映射为有效码。检错纠错

18、的基本原理检错纠错的基本原理链路层和局域网5-22 由于信道有错，有效码在传送过程中有可能变成了无由于信道有错，有效码在传送过程中有可能变成了无效码。当收方收到信道传来的编码信息时，首先判断它是效码。当收方收到信道传来的编码信息时，首先判断它是有效码还是无效码。如果是有效码则通过逆映射关系，解有效码还是无效码。如果是有效码则通过逆映射关系，解码出原信息；如果是无效码，则认为出了错，这就是检验码出原信息；如果是无效码，则认为出了错，这就是检验出错误。假设通过无效码能够分析出它是由哪一个有效码出错误。假设通过无效码能够分析出它是由哪一个有效码出错而来的，从而找出原信息码，这就称为纠错（编码）出错而

19、来的，从而找出原信息码，这就称为纠错（编码）。如果信道出错，使一个有效码变成另一个有效码，则收。如果信道出错，使一个有效码变成另一个有效码，则收方检不出错。方检不出错。检错纠错的基本原理检错纠错的基本原理链路层和局域网5-23 我们把两个等长二进制数（或两个等长码）不相同对应位的位数称为距我们把两个等长二进制数（或两个等长码）不相同对应位的位数称为距离。例如离。例如10000和和00100的距离为的距离为2。 定义定义海明距离海明距离(Hamming Distance)：某种编码任意两个有效码间的最小：某种编码任意两个有效码间的最小距离称为该编码的海明距离。距离称为该编码的海明距离。 结论结论

20、1，可以检出，可以检出d个错误的检错码，其汉明距离至少为个错误的检错码，其汉明距离至少为d1。 结论结论2，可以纠出，可以纠出d个错误的纠错码，其汉明距离至少为个错误的纠错码，其汉明距离至少为2d1。d+12d+1有效码有效码i 有效码有效码j 有效码有效码I 有效码有效码j 海明编码海明编码-纠错纠错链路层和局域网5-24海明码：能够纠正一位错编码称为海明码。海明码：能够纠正一位错编码称为海明码。 假设信息位假设信息位m位，检验位位，检验位r位。有效码有位。有效码有2m个。个。n = m+r,由于能由于能够纠正一位错，则对于每个有效码有够纠正一位错，则对于每个有效码有n个无效码，共有无效码个

21、无效码，共有无效码2mn个，所以有效码和无效码的总数为个，所以有效码和无效码的总数为2m2mn个，它们应小于等于个，它们应小于等于2n个。个。 2mmmn2n 即即 2m（n1）2n n12r 2r-r m1 （式（式1） 例一帧例一帧1000位，求检验位长度，我们采用试探法解式（位，求检验位长度，我们采用试探法解式（1），），r选选为为10。 海明码将信息位和检验位混排如下：海明码将信息位和检验位混排如下：r1r2m3r4m5m6m7r8m9m10m11m12m13m14m15r16m17 （式（式2） 检验位的序号为检验位的序号为2的整次幂的整次幂1，2，4，8，16，。而信息位的序。而信

22、息位的序号为号为2的非整次幂，的非整次幂，3，5，6，7，9，10，11，12，13，。 海明码海明码链路层和局域网5-25 定义定义mk与与rj相关或相关或rj与与mk相相关，如果用关，如果用2的整次幂的和来表示的整次幂的和来表示k，j为其中一个为其中一个2的整次幂，则该的整次幂，则该mk与与rj相相关。或说关。或说rj与与mk相相关。关。 例如：例如：11=821则说则说m11和和r8，r2，r1相相关关 5=41则说则说m5和和r4、r1相相关关 3=21则说则说m3和和r2、r1相相关关 或说或说r1与与m11、m5和和m3相相关关 r2与与m11、m3相相关关 r4与与m5相相关关

23、r8与与m11相相关关 发方的海明编码，也就是如何用信息位来表示检验位。发方的海明编码，也就是如何用信息位来表示检验位。 ri=各相关信息位之异或各相关信息位之异或 （式（式3） 若若ri仅和一个信息位仅和一个信息位mp相关，则相关，则ri=mp 收方纠错过程如下：收方纠错过程如下： 首先对累加器首先对累加器A清清0， 然后对所有的然后对所有的ri进行相关位异或，若进行相关位异或，若ri与相与相关各信息位之异或为关各信息位之异或为1，则，则A+=i 运算后累加器运算后累加器A的累加和就是出错位数（变反纠错）。的累加和就是出错位数（变反纠错）。链路层和局域网5-26 例：有两位信息位的海明编码为

24、例：有两位信息位的海明编码为r1r2m3r4m5，设，设m3=0，m5=1。编码过程：编码过程： r1=m5m3=10=1 r2=m3=0 r4=m5=1编码为编码为10011，假设信道出错，使之成为，假设信道出错，使之成为10010。 纠错过程：纠错过程： 累加器累加器A清清0 r1m5m3=100=1，A+=1 r2m3=00=0 r4m5=10=1 A+=4 A=5 出错位为第出错位为第5位位m5，将之变反成为，将之变反成为1就完成了纠错。就完成了纠错。链路层和局域网5-27链路层链路层p5.1 概述和服务概述和服务p5.2差错检测和纠差错检测和纠错技术错技术p5.3多址访问协议多址访问

25、协议p5.4链路层编址链路层编址p5.5以太网以太网p5.6集线器和交换集线器和交换机机p5.7 PPPPPP：点到点协：点到点协议议p5.8链路虚拟化链路虚拟化: ATM ATM 和和 MPLSMPLS链路层和局域网5-28多址访问协议多址访问协议两种类型的两种类型的 “链路链路”:p点对点点对点mPPP （用于拨号访问）或（用于拨号访问）或HDLCm在以太网交换机和主机间的点到点链路在以太网交换机和主机间的点到点链路p广播广播(有线或无线共享有线或无线共享)m传统以太网传统以太网m802.11无线局域网无线局域网链路层和局域网5-29多址访问协议多址访问协议p单个共享广播信道单个共享广播信

26、道p两个或多个节点同时传输：冲突（碰撞）两个或多个节点同时传输：冲突（碰撞）m冲突（碰撞）：一个节点同时接收两个或多个信号时发冲突（碰撞）：一个节点同时接收两个或多个信号时发生冲突生冲突m在某个时刻只有一个节点发送数据才可以发送在某个时刻只有一个节点发送数据才可以发送成功成功信息信息多址访问协议多址访问协议p分布式算法决定各节点如何共享信道，即决定节点分布式算法决定各节点如何共享信道，即决定节点什么时候可以传数据什么时候可以传数据p共享信道既要负责进行数据传输，又要负责分布式共享信道既要负责进行数据传输，又要负责分布式算法的控制信息的传输算法的控制信息的传输m没有带外信道传输控制信息没有带外信

27、道传输控制信息链路层和局域网5-30理想的多址访问协议理想的多址访问协议速率为速率为R bps的广播信道的广播信道1. 当一个节点有数据发送时，它能以当一个节点有数据发送时，它能以R bps的速率发送的速率发送.2. 当有当有M个节点要发送数据，每个节点的平均发送速率个节点要发送数据，每个节点的平均发送速率为为 R/M3. 完全分散完全分散:m不需要主节点协调传输不需要主节点协调传输m不需要时钟、时隙同步不需要时钟、时隙同步4. 简单简单链路层和局域网5-31MAC 协议协议:分类分类3大类大类:p信道划分信道划分m把信道划分为小把信道划分为小“片片” (时隙，频分，码分时隙，频分，码分)m给

28、节点分配专用的小给节点分配专用的小“片片”p随机访问随机访问m不划分信道，允许冲突不划分信道，允许冲突m能从冲突中能从冲突中“恢复恢复”p轮转轮转m通过集中调整共享访问避免冲突通过集中调整共享访问避免冲突链路层和局域网5-32时分多路访问时分多路访问: TDMATDMA: time division multiple access p轮流访问信道轮流访问信道p在每个循环中，每个站点得到一个固定长度的时隙在每个循环中，每个站点得到一个固定长度的时隙m时隙长度通常为数据服务单元的发送时间时隙长度通常为数据服务单元的发送时间p未被使用的时隙空闲未被使用的时隙空闲p例子：例子：6个站点的局域网，个站点

29、的局域网， 1,3,4 被使用，被使用，2,5,6空空闲闲 链路层和局域网5-33频分多路访问频分多路访问: FDMAFDMA: frequency division multiple access p信道被分成不同频段信道被分成不同频段p每个站点分配一个固定的频段每个站点分配一个固定的频段p未被使用的频段空闲未被使用的频段空闲p例子：例子：6个站点的局域网，个站点的局域网， 1,3,4 被使用，被使用，2,5,6空闲空闲frequency bandstime链路层和局域网5-34码分多路访问码分多路访问 (CDMA)CDMA (Code Division Multiple Access) p

30、每个节点分配一个唯一的编码每个节点分配一个唯一的编码p每个节点用它唯一的编码来对它发送的数据进行每个节点用它唯一的编码来对它发送的数据进行编码编码p允许多个节点允许多个节点“共存共存” ，信号可叠加，即可以同，信号可叠加，即可以同时传输数据而无冲突时传输数据而无冲突 (如果编码如果编码 是是“正交化正交化”的的)链路层和局域网5-35随机访问协议随机访问协议p节点有数据包发送节点有数据包发送m以信道满数据率以信道满数据率R传送传送m节点间没有协调者节点间没有协调者p2个或更多的发送节点个或更多的发送节点 - “冲突冲突collision”,p随机访问随机访问MAC协议协议要求要求: m能够检测

31、冲突能够检测冲突m能够从冲突中恢复能够从冲突中恢复 (例如：通过延时重传例如：通过延时重传)p随机访问随机访问MAC协议实例：协议实例：mALOHAm时隙时隙ALOHAmCSMA, CSMA/CD, CSMA/CA链路层和局域网5-36纯纯 (非时隙非时隙) ALOHAp非时隙非时隙Aloha: 简单，不需同步简单，不需同步p帧一到达帧一到达m 立即传输立即传输p冲突概率增加冲突概率增加:m在在t0发送的帧和在发送的帧和在 t0-1,t0+1的发送的其它帧冲突的发送的其它帧冲突链路层和局域网5-37纯纯Aloha效率效率P(给定节点成功传送给定节点成功传送) = P(节点传送节点传送) . P

32、(没有其他节点在没有其他节点在t0-1,t0内传送内传送) . P(没有其他节点在没有其他节点在t0,t0 +1内传送内传送) = p . (1-p)N-1 . (1-p)N-1 = p . (1-p)2(N-1) 选择选择p值，然后求值，然后求N-无穷时的极限无穷时的极限. = 1/(2e) = 0.18 链路层和局域网5-38时隙时隙ALOHA假设假设p所有帧大小相同所有帧大小相同p时间被划分为相同大小的时间被划分为相同大小的时隙，一个时隙等于传送时隙，一个时隙等于传送一帧的时间一帧的时间p节点只能在一个时隙的开节点只能在一个时隙的开始才能传送始才能传送p节点需要同步节点需要同步p如果一个

33、时隙有多个节点如果一个时隙有多个节点同时传送，所有节点都能同时传送，所有节点都能检测到冲突检测到冲突实现实现p当节点要发送新帧，它等到当节点要发送新帧，它等到下一时隙开始时传送下一时隙开始时传送p没有冲突，节点可以在下一没有冲突，节点可以在下一时隙发送新帧时隙发送新帧p如果有冲突，节点在随后的如果有冲突，节点在随后的时隙以概率时隙以概率p重传该帧，直重传该帧，直到成功为止。到成功为止。链路层和局域网5-39时隙时隙ALOHA优点优点p单个活跃节点可以持续单个活跃节点可以持续以满速率传送帧以满速率传送帧p具有高分散性具有高分散性: 只需节只需节点的时隙同步点的时隙同步p简单简单缺点缺点p冲突，浪

34、费时隙冲突，浪费时隙p空闲时隙空闲时隙p节点只有在传输数据包节点只有在传输数据包时才能检测到冲突时才能检测到冲突链路层和局域网5-40时隙时隙Aloha效率效率p假设有假设有N个节点，每个节点在个节点，每个节点在时隙以概率时隙以概率p发送发送p一个节点在一个时隙成功传一个节点在一个时隙成功传送的概率送的概率 = p(1-p)N-1p任一节点传送成功的概率任一节点传送成功的概率 = Np(1-p)N-1 p为了得到为了得到N个活跃节点的个活跃节点的最大效率，必须找出使表最大效率，必须找出使表达式达式Np(1-p)N-1 取最大取最大值的值的p*p为了得到大量活跃节点的为了得到大量活跃节点的最大效

35、率，最大效率， 我们求我们求N趋趋近无穷时近无穷时Np*(1-p*)N-1 极限值，计算可知最大效极限值，计算可知最大效率为率为1/e =0 .37效率效率 ：当有很多节点，每个节点：当有很多节点，每个节点有很多帧要发送时，成功时隙所有很多帧要发送时，成功时隙所占的百分比占的百分比最佳最佳: 信道有信道有 37%的的有效传输有效传输链路层和局域网5-41CSMA (Carrier Sense Multiple Access)载波侦听多路访问载波侦听多路访问CSMA: 传送前侦听传送前侦听:p如果信道闲：传送整个帧如果信道闲：传送整个帧p如果信道忙：延迟传送如果信道忙：延迟传送p类比人类行为：不

36、打断他人！类比人类行为：不打断他人！链路层和局域网5-42CSMA冲突冲突冲突还是可能发生冲突还是可能发生:传播延迟可能导致传播延迟可能导致两个节点没侦两个节点没侦听到其它节点的传送听到其它节点的传送冲突冲突:整个数据包的传送时间被浪整个数据包的传送时间被浪费费spatial layout of nodes 注意注意:距离和传播延时决定冲突概率距离和传播延时决定冲突概率链路层和局域网5-43CSMA/CD (冲突检测冲突检测)CSMA/CD:m在一个短时间内检测冲突在一个短时间内检测冲突m放弃冲突传送，减少带宽浪费放弃冲突传送，减少带宽浪费p冲突检测冲突检测: m在有线在有线LANs中容易：测

37、量信号强度，比较传送和接收中容易：测量信号强度，比较传送和接收信号信号m在无线在无线LANs中困难中困难: 传输中接收者可能关闭传输中接收者可能关闭p人类行为：有礼貌的会谈人类行为：有礼貌的会谈链路层和局域网5-44CSMA/CD协议基本思想：p当一个节点要发送数据时，首先监听信道，看是否有载波。p如果信道空闲，则发送数据。p如果信道忙，则继续对信道进行监听（1持续CSMA）。一旦发现空闲，便立即发送。p如果在发送过程中检测到碰撞，则停止自己的正常发送，转而发送一短暂的干扰信号jam，强化冲突，使其它站点都能知道出现了冲突。p发送了干扰信号后，退避一随机时间，重新尝试发送。链路层和局域网5-4

38、5CSMA/CD协议讨论我有数据要发送监听链路层和局域网5-46CSMA/CD协议讨论我有数据要发送监听网上有载波，等待链路层和局域网5-47CSMA/CD协议讨论我有数据要发送监听发生冲突，立即回退冲突了！我也有数据要发送链路层和局域网5-48“轮转轮转”MAC协议协议分割信道分割信道MAC协议协议m在高负载的情况下，信道共享公平高效在高负载的情况下，信道共享公平高效m低负载效率低：延迟访问，如果只有一个活跃节点低负载效率低：延迟访问，如果只有一个活跃节点只分配了只分配了 1/N的带宽的带宽随机访问随机访问MAC协议协议m低负载效率高：单个节点可以获得整个信道低负载效率高：单个节点可以获得整

39、个信道m高负载：冲突开销大高负载：冲突开销大“轮转轮转”协议协议两者的折中两者的折中!链路层和局域网5-49“轮转轮转” MAC协议协议轮询轮询: p主节点轮流主节点轮流 “邀请邀请”从属节点传送数据从属节点传送数据p关注：关注：m轮询开销轮询开销 m延迟延迟m主节点失效，整个网主节点失效，整个网络失效络失效令牌传递：令牌传递：p控制令牌从一个节点顺序传到控制令牌从一个节点顺序传到下一个节点下一个节点p令牌消息令牌消息p关注：关注：m令牌开销令牌开销m延时延时m令牌失效令牌失效 链路层和局域网5-50MAC协议总结协议总结p共享介质共享介质m信道分割：时间，频率，代码信道分割：时间，频率，代码

40、 时分，码分，频分时分，码分，频分m随机分割随机分割 (动态动态) ALOHA, S-ALOHA, CSMA, CSMA/CD 载波侦听：有线网络容易实现，无线网络困难载波侦听：有线网络容易实现，无线网络困难 CSMA/CD用于以太网用于以太网,CSMA/CA用于无线网络用于无线网络m轮转轮转 中心节点轮询，令牌传递中心节点轮询，令牌传递链路层和局域网5-515.3.3 局域网局域网p多址访问协议广泛应用于局域网多址访问协议广泛应用于局域网p基于随机访问的基于随机访问的CSMA/CD广泛应用于局域网广泛应用于局域网p基于令牌传递技术的令牌环和基于令牌传递技术的令牌环和FDDI在局域网在局域网技

41、术中变得次要技术中变得次要p链路层技术的发展，局域网、城域网、广域网链路层技术的发展，局域网、城域网、广域网的概念变得越来越模糊和不重要的概念变得越来越模糊和不重要链路层和局域网5-52局域网概述局域网基本概念局域网基本概念计算机网络拓扑结构计算机网络拓扑结构计算机与局域网的互连计算机与局域网的互连局域网的体系结构局域网的体系结构链路层和局域网5-53局域网概述局域网概述主要特点：网络为一个单位所拥有，且地主要特点：网络为一个单位所拥有，且地理范围和站点数目均有限理范围和站点数目均有限局域网按拓扑结构进行分类：星形网、环局域网按拓扑结构进行分类：星形网、环形网、总线网、树形网和网状网形网、总线

42、网、树形网和网状网链路层和局域网5-54局域网概述局域网基本概念局域网基本概念计算机网络拓扑结构计算机网络拓扑结构计算机与局域网的互连计算机与局域网的互连局域网的体系结构局域网的体系结构链路层和局域网5-55常见的网络拓扑结构常见的网络拓扑结构 一、星型结构一、星型结构PC1PC4PC3PC2连接器连接器链路层和局域网5-56常见的网络拓扑结构常见的网络拓扑结构 一、星型结构一、星型结构 辐射状连接辐射状连接 中央结点集中式通信控制中央结点集中式通信控制优点：优点：结构简单，访问协议简结构简单，访问协议简单，单个节点的故障不会影单，单个节点的故障不会影响到整个网络。响到整个网络。缺点：缺点：对

43、中央结点的可靠性要求很对中央结点的可靠性要求很高，一有故障，全网瘫痪。高，一有故障，全网瘫痪。链路层和局域网5-57常见的网络拓扑结构常见的网络拓扑结构 二、总线结构二、总线结构PC1PC4PC2PC3链路层和局域网5-58常见的网络拓扑结构常见的网络拓扑结构 二、二、总线结构总线结构 所有的站点都连接在同一根所有的站点都连接在同一根传输线，即传输线，即“总线总线”上。上。 优点：优点：结构简单，易于扩充。结构简单，易于扩充。 缺点：缺点：故障检测比较困难。故障检测比较困难。链路层和局域网5-59常见的网络拓扑结构常见的网络拓扑结构 三、环型结构三、环型结构PC1PC3PC4PC2链路层和局域

44、网5-60常见的网络拓扑结构常见的网络拓扑结构 三、环型结构三、环型结构 站与站点之间首尾相接，形站与站点之间首尾相接，形成一个环，数据只能沿单方向传输。成一个环，数据只能沿单方向传输。 优点：优点：这种结构适合于光纤介质。这种结构适合于光纤介质。实时性较强。实时性较强。 缺点：缺点：如果处理不当站点的故障会如果处理不当站点的故障会引起全网故障。引起全网故障。链路层和局域网5-61常见的网络拓扑结构常见的网络拓扑结构 四、树型结构四、树型结构PC2PC3PC4PC1连接器连接器连接器连接器连接器连接器链路层和局域网5-62常见的网络拓扑结构常见的网络拓扑结构 四、树型结构四、树型结构 它是从星

45、型拓扑演变而来的它是从星型拓扑演变而来的，形状像一棵倒挂的树。，形状像一棵倒挂的树。 特点：特点：与星型拓扑大致相似。它与与星型拓扑大致相似。它与星型结构相比降低了通信线路成本，星型结构相比降低了通信线路成本，增加了网络复杂性。增加了网络复杂性。链路层和局域网5-63常见的网络拓扑结构常见的网络拓扑结构 五、网状结构五、网状结构PC2PC3PC4PC1连接器连接器连接器连接器连接器连接器连接器连接器链路层和局域网5-64常见的网络拓扑结构常见的网络拓扑结构 五、网状结构五、网状结构 网状网络的每一个站点都与网状网络的每一个站点都与其它站点一一直接互连。其它站点一一直接互连。 优点：优点：连接方

46、法主要是利用冗余的连接方法主要是利用冗余的连接，实现站与站之间的高速传输和连接，实现站与站之间的高速传输和高容错性能，以提高网络的速度和可高容错性能，以提高网络的速度和可靠性。靠性。 缺点：缺点：关系复杂，建网难，维护难关系复杂，建网难，维护难链路层和局域网5-65局域网概述局域网概述局域网基本概念局域网基本概念计算机网络拓扑结构计算机网络拓扑结构计算机与局域网的互连计算机与局域网的互连局域网的体系结构局域网的体系结构链路层和局域网5-66计算机与局域网的连接 计算机与局域网通过网络接口计算机与局域网通过网络接口板进行连接，网络接口板又称通信适配板进行连接，网络接口板又称通信适配器（器（Ada

47、pter）或网络接口卡）或网络接口卡NIC（Network Interface Card），通常我），通常我们称为们称为“网卡网卡”链路层和局域网5-67计算机与局域网的通信计算机计算机CPU高高速速缓缓存存存储器存储器网络接口卡网络接口卡（网卡）（网卡）I/O总线总线并行通信并行通信至局域网至局域网串行通信串行通信链路层和局域网5-68局域网概述局域网基本概念局域网基本概念计算机网络拓扑结构计算机网络拓扑结构计算机与局域网的互连计算机与局域网的互连局域网的体系结构局域网的体系结构链路层和局域网5-69局域网体系结构局域网体系结构l计算机局域网现在已经成为计算机网络的主计算机局域网现在已经成为

48、计算机网络的主流，因此美国电气与电子工程师协会流，因此美国电气与电子工程师协会IEEE802IEEE802委员会制定的委员会制定的IEEE802IEEE802局域网标准已经得到了局域网标准已经得到了国际标准化组织国际标准化组织ISOISO的采纳，成为计算机局域的采纳，成为计算机局域网的事实标准。网的事实标准。lIEEE802IEEE802局域网参考模型是针对局域网的网络局域网参考模型是针对局域网的网络体系结构特点而制定的，它遵循体系结构特点而制定的，它遵循ISO/OSIISO/OSI参考参考模型的原则，解决物理层和数据链路层的功模型的原则，解决物理层和数据链路层的功能以及与网络层的接口服务、网

49、际互连的高能以及与网络层的接口服务、网际互连的高层功能层功能链路层和局域网5-70IEEE802IEEE802与与OSIOSI参考模型对应关系参考模型对应关系应用层应用层表示层表示层会话层会话层传输层传输层网络层网络层数据链路层数据链路层物理层物理层逻辑链路控制子层逻辑链路控制子层介质访问控制子层介质访问控制子层物理层物理层（ ）（ ）（ ）服务访问点服务访问点网卡网卡网卡驱网卡驱动程序动程序OSI参考模型参考模型IEEE802参考模型参考模型链路层和局域网5-71IEEE802IEEE802网络协议标准网络协议标准IEEE802.1 IEEE802.1 体系结构及高层接口体系结构及高层接口I

50、EEE802.2 IEEE802.2 逻辑链路控制逻辑链路控制LLCLLCIEEE802.3 CSMA/CDIEEE802.3 CSMA/CD（带冲突检测的载（带冲突检测的载波侦听多路复用）访问控制方法和物理波侦听多路复用）访问控制方法和物理层技术规范层技术规范IEEE802.4 IEEE802.4 令牌总线访问控制方法和令牌总线访问控制方法和物理技术规范物理技术规范IEEE802.5 IEEE802.5 令牌环访问控制方法和物令牌环访问控制方法和物理层规范理层规范IEEE802.6 IEEE802.6 城域网访问控制方法和物城域网访问控制方法和物理层技术规范理层技术规范链路层和局域网5-72

51、IEEE802IEEE802标准的相互联系标准的相互联系802.2802.2802.1802.1802.802.3 3802.802.4 4802.802.5 5802.802.6 6物理层物理层介质访问控制子层介质访问控制子层逻辑链路控制子层逻辑链路控制子层链路层和局域网5-73链路层链路层p5.1 概述和服务概述和服务p5.2差错检测和纠差错检测和纠错技术错技术p5.3多址访问协议多址访问协议p5.4链路层编址链路层编址p5.5以太网以太网p5.6集线器和交换集线器和交换机机p5.7 PPPPPP：点到点协：点到点协议议p5.8链路虚拟化链路虚拟化: ATM ATM 和和 MPLSMPLS

52、链路层和局域网5-74局域网地址局域网地址32位位IP地址地址p网络层地址网络层地址p用于把分组送到目的用于把分组送到目的IP网络网络 (回忆回忆IP网络定义网络定义)pIP协议初始化前配置协议初始化前配置48位位MAC(或或LAN 或物理或或物理或Ethernet)地址地址: p链路层地址链路层地址p用于把数据帧从一个接口传送到另一个接口用于把数据帧从一个接口传送到另一个接口 (同同一网络中一网络中)p48位位MAC地址固化在适配器的地址固化在适配器的ROM链路层和局域网5-75局域网地址局域网地址在局域网中的每一个适配器都有一个唯一的在局域网中的每一个适配器都有一个唯一的LAN地址地址广播

53、地址广播地址 =FF-FF-FF-FF-FF-FF= 适配器（网卡）适配器（网卡）1A-2F-BB-76-09-AD58-23-D7-FA-20-B00C-C4-11-6F-E3-9871-65-F7-2B-08-53 LAN(wired orwireless)链路层和局域网5-76局域网地址局域网地址pMAC地址由地址由IEEE统一分配统一分配p厂商购买一块厂商购买一块MAC地址空间地址空间 (要保证唯一性要保证唯一性)p比较比较: (a) MAC地址地址: 好像身份证号码好像身份证号码 (b) IP地址地址: 好像邮政地址好像邮政地址pMAC平面地址平面地址 = 可移动可移动m能从一个能从

54、一个LAN移动到另一个移动到另一个LANpIP层次地址层次地址m 依赖节点所依附的依赖节点所依附的IP网络网络回忆应用层的主机名，网络层回忆应用层的主机名，网络层IP地址，链路层地址，链路层MAC地址。地址。有利于保持各层独立的原则。有利于保持各层独立的原则。链路层和局域网5-77回忆前面的路由讨论回忆前面的路由讨论223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27ABEA把把IP分组发送给分组发送给 B:l查找查找B的网络地址，发现的网络地址，发现B和和A在在同

55、一网络中同一网络中l链路层发送分组给链路层发送分组给B，该分组包含，该分组包含在链路层帧中在链路层帧中Bs MACaddrAs MACaddrAs IPaddrBs IPaddrIP payloaddatagramframeframe source,dest addressdatagram source,dest address链路层和局域网5-78ARP: 地址解析协议地址解析协议p每个在局域网上的每个在局域网上的IP节点节点 (Host, Router)都有都有ARP 表表pARP表表: 局域网上一局域网上一些节点的些节点的IP/MAC地地址映射址映射 m TTL (Time To Liv

56、e): 映射地址的失映射地址的失效时间效时间 (典型为典型为20分分钟钟)问题：知道问题：知道B的的IP地址怎么地址怎么知道它的知道它的MAC地址地址1A-2F-BB-76-09-AD58-23-D7-FA-20-B00C-C4-11-6F-E3-9871-65-F7-2B-08-53 LAN237.196.7.23237.196.7.78237.196.7.14237.196.7.88链路层和局域网5-79ARP协议协议pA想发送分组给想发送分组给 B，A知道知道 B的的IP地址地址p假设假设B的的MAC地址不在地址不在A的的ARP表中表中pA广播广播包含包含B的的IP地址的地址的ARP查查

57、询包询包 m目的目的MAC地址地址= FF-FF-FF-FF-FF-FFm在局域网上的所有机器都能在局域网上的所有机器都能收到收到ARP查询查询pB收到收到 ARP包，回给包，回给A一个带一个带有有B的的MAC地址的包地址的包m包单播包单播unicast发送给发送给A的的MAC地址地址pA缓存缓存IP-to-MAC地址对在地址对在 ARP表中，直到信息过期表中，直到信息过期 (timeout)m软件规定软件规定: 如果如果ARP表的表的信息在一定时间内没有刷信息在一定时间内没有刷新，则信息将过期。新，则信息将过期。pARP是即插即用的是即插即用的:m无需网络管理员干预，节无需网络管理员干预，节

58、点就能创建点就能创建ARP表表链路层和局域网5-80路由到其他局域网路由到其他局域网A通过通过R向向B发送分组发送分组 假设假设A知道知道B的的IP地址地址p在路由器在路由器R中有两个中有两个ARP表，每个针对一个表，每个针对一个IP网络网络 (LAN)p在主机的路由表中发现路由器的在主机的路由表中发现路由器的IP：111.111.111.110p在主机的在主机的ARP表中发现表中发现MAC地址：地址：E6-E9-00-17-BB-4B等等等等ARB链路层和局域网5-81pA创建一个分组，源地址为创建一个分组，源地址为A，目的地址为，目的地址为BpA使用使用ARP得到得到R的的111.111.

59、111.110的的MAC地址地址pA创建一个链路层帧，该帧以创建一个链路层帧，该帧以R的的MAC地址为目的地址地址为目的地址，并包含，并包含 A-to-B的的IP数据包数据包pA的适配器发送帧的适配器发送帧pR的适配器收到帧的适配器收到帧pR从从Ethernet帧中提取帧中提取IP数据包，得知目的地址为数据包，得知目的地址为BpR使用使用 ARP得到得到B的的MAC地址地址pR创建一个包含创建一个包含A-to-B的的IP数据包的帧发送给数据包的帧发送给BARB链路层和局域网5-82相同子网的相同子网的ARPp发送站发送站A A将直接广播对将直接广播对B B的的ARPARP请求请求链路层和局域网

60、5-83不同子网的不同子网的ARPp发送站发送站A A将广播对将广播对“默认网关默认网关”即路由器左端口即路由器左端口192.168.0.1192.168.0.1的的ARPARP请求，获得其请求，获得其MACMAC地址后将把地址后将把发送给发送给B B的数据先发送到路由器左端口的数据先发送到路由器左端口p路由器收到数据并路由后，将在右端口广播路由器收到数据并路由后，将在右端口广播B B的的ARPARP请求，获得请求，获得B B的的MACMAC地址后进行数据转发。地址后进行数据转发。链路层和局域网5-84p5.1 概述和服务概述和服务p5.2差错检测和纠差错检测和纠错技术错技术p5.3多址访问协议多址访