计算机网络第五章链路层和局域网

5-1第五章链路层和局域网Chapter5TheLinkLayerandLocalNetworksComputerNetworking

ATop-DownApproach5-2本章要求重点掌握链路层提供的服务、差错检测的方法、以太网技术、互联设备及其相关技术、ARP协议的功能和实现过程；一般掌握适配器通信过程、多址访问协议的种类及其实现方法、PPP协议的相关技术；了解链路虚拟化的基本概念、ATM技术、MPLS技术、网络硬件连接方法。5-3链路层5.1概述和服务5.2差错检测和纠错技术5.3多址访问协议5.4链路层编址5.5以太网5.6集线器和交换机5.7PPP：点到点协议5.8链路虚拟化:ATM和MPLS5-4链路层：介绍常用术语:节点：主机和路由器(包括网桥和交换机)链路：沿着通信路径连接相邻节点的通信信道有线链路无线链路局域网帧：链路层协议交换的数据单元。封装网络层数据报数据链路层的职责：将分组通过一个链路，从一个节点传输到临近的另一个节点。“link”5-5链路层的特点分组传输可以经过不同的链路使用不同的链路层协议实现:例如，以太网，帧中继，最802.11无线LAN每个链路协议提供不同的服务例如，可以在链路上提供或不提供可靠的传输传输类比从成都到九寨沟的旅途打的：成都某地到成都机场飞机：成都机场到黄龙机场大巴：黄龙机场到风景区旅客=数据包运输段=通信链路运输模式=链路层协议旅行社=路由算法5-6链路层服务成帧（Framing）：把网络层数据报加头和尾，封装成帧帧头中包括指明目的和源的“物理地址”（不同于IP地址）链路接入（Linkaccess）：媒体访问控制（MediumAccessControl，MAC）协议共享媒体的多路访问可靠交付（Reliabledelivery）在出错率很低的链路上很少用(光纤，部分双绞线)无线链路：高出错率5-7链路层服务(续)流量控制（Flowcontrol）：节点具有有限容量的帧缓冲能力在邻接的发送节点和接收节点间的同步调节差错检测（Errordetection）:差错由信号衰减和噪声引起接收者检测错误：如果发现差错，发送者重传帧或丢帧纠错（Errorcorrection）：接收者检测和纠正错误，不需发送者重传半双工和全双工（Half-duplexandFull-duplex）半双工，一个节点不能同时传输和接收全双工，节点可以同时传输和接收5-8适配器通信链路层在“适配器”

(网卡)中实现Ethernet卡，PCMCIA卡，802.11卡发送方：封装分组成帧增加检错位、可靠传输、流量控制等接收方检测差错、可靠交付、流量控制等提取分组，传给接收节点发送节点帧接收节点数据报帧适配器适配器链路层协议5-9链路层5.1概述和服务5.2差错检测和纠错技术5.3多址访问协议5.4链路层编址5.5局域网概述5.6以太网5.7集线器和交换机5.8PPP：点到点协议5.9链路虚拟化:ATM和MPLS5-10差错检测错误检测不是100%可靠！协议有可能漏掉一些错误，但很少越大的校验信息域能提供更好的检错能力用户数据校验信息传输信道用户数据差错检测算法用户数据校验信息用户数据差错检测算法是否相等是错误处理否5-11差错检测—奇偶校验单个奇偶位:检测奇数个位的错误事实上，发生未检测到错误的概率为50%奇校验:用户数据和校验信息中1的个数为奇数个偶校验:用户数据和校验信息中1的个数为偶数个10011001奇校验：1001100115-12二维奇偶校验单个奇偶位:检测单个位的错误二维奇偶校验:检测和纠正单个位错误,检测的两个位错误001比特偶校验事实上，发生未检测到错误的概率为50%5-13差错检测—校验和发送方:把数据段内容看成16-bit的整数序列检查和：把数据段内容加起来,求反码发送方把校验和放入的校验和域接收方：计算接收字段的校验和检测计算的校验和与校验和域的值是否相等：NO–检测到错误YES–没有检测到错误。目标:

检测在传输数据段中的“错误”5-14差错检测—循环冗余校验CRC（CyclicRedundancyCheck）

CRC编码也称为多项式编码，该编码将比特串看作是0和1的一个多项式

101001=>x5+x3+1基本思想：把数据D，看成d位二进制数发送方与接收方商定一个r+1位模式G，称为生成多项式选择r位循环冗余位R,添加到D形成数据<D,R>，满足特性：

<D,R>是d+r位二进制数，用模2运算能被G整除接收方用G去除接收到的<D,R>，如果余数非零，则错误发生；否则，数据正确5-15注意：模2运算的加法运算与减法运算是相同的，等价于按位异或（XOR），比如1011XOR0101=11101001XOR1101=01001011-0101=11101001-1101=01005-16CRC的数学表达<D,R>能被G整除,即:D.2rXORR=nGR=remainder[]D.2rG等价于：如果用G来除D.2r

，余数等于R:等价于：两边都异或R:D.2r=nGXORR5-17CRC例子5-18CRC练习假设:通信双方协商的生成多项式为:G=X4+X2+X+1发送放要发送的数据为:D=11001100问题:CRC校验信息需要多少位?发送方最终发送的数据是多少位?发送方最终发送的数据内容是什么?如果传输过程中出现1位错误能否检测?出现6位错误能否检测?5-19国际标准已经定义了8-、16-、32-位生成多项式G；8-位CRC用于ATM头部5字节的保护；32-CRC用于大量链路层IEEE协议。CRC能检测r比特或更少的错误位循环冗余校验CRC5-20奇偶校验能力最弱，CRC校验能力最强奇偶校验通常用于简单的串口通信校验和通常应用于网络层及其之上的层次，要求简单快速的软件实现方式CRC通常应用于链路层，一般由适配器硬件实现差错检测方法比较5-21链路层5.1概述和服务5.2差错检测和纠错技术5.3多址访问协议5.4链路层编址5.5以太网5.6集线器和交换机5.7PPP：点到点协议5.8链路虚拟化:ATM和MPLS5-22两种链路类型点对点链路PPP（用于拨号访问）或HDLC在以太网交换机和主机间的点到点链路广播链路传统以太网802.11无线局域网5-23多址访问协议（MultipleAccessProtocol,MAC）广播链路共享广播信道冲突（碰撞）某节点同时接收两个或多个节点信号时，发生冲突某个时刻只有一个节点发送数据时，才可成功发送信息多址访问协议决定各节点如何共享信道共享信道既要负责数据传输，又要负责控制信息的传输5-24理想的多址访问协议假设：速率为Rbps的广播信道1.当一个节点有数据发送时，它能以R的速率发送2.当有M个节点要发送数据，每个节点的平均发送速率为R/M3.特点：完全分散:不需要主节点协调传输不需要时钟、时隙同步简单5-25MAC协议:分类分为3大类:信道划分把信道划分为小“片”(时隙，频分，码分)给节点分配专用的小“片”随机访问不划分信道，允许冲突能从冲突中“恢复”轮转通过集中调整共享访问避免冲突5-26信道划分—

时分多路访问:TDMATDMA:timedivisionmultipleaccess

轮流访问信道每个站点对应一个固定长度的时隙时隙长度通常为数据服务单元的发送时间未被使用的时隙空闲例：6个站点的局域网

1,3,4被使用，2,5,6空闲

5-27信道划分—频分多路访问:FDMAFDMA:frequencydivisionmultipleaccess

信道被分成不同频段每个站点分配一个固定的频段未被使用的频段空闲例：6个站点的局域网，1,3,4被使用，2,5,6空闲frequencybandstimeFDMcable5-28信道划分—码分多路访问(CDMA)CDMA(CodeDivisionMultipleAccess)

每个节点分配一个唯一的编码每个节点用它唯一的编码来对它发送的数据进行编码允许多个节点“共存”，信号可叠加，即可以同时传输数据而无冲突(如果编码是“正交化”的)5-29随机访问协议节点有数据包发送以信道满数据率R传送节点间没有协调者2个或更多的发送节点->“冲突collision”随机访问MAC协议要求:能够检测冲突能够从冲突中恢复

(例如：通过延时重传)随机访问MAC协议实例：ALOHA时隙ALOHACSMA,CSMA/CD,CSMA/CA5-30纯(非时隙)ALOHA非时隙Aloha:简单，不需同步帧一到达，就立即传输冲突概率增加:在t0发送的帧和在[t0-1,t0+1]的发送的其它帧冲突5-31纯Aloha效率P(给定节点成功传送)=P(节点传送).P(没有其他节点在[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-32时隙ALOHA假设所有帧大小相同时间被划分为相同大小的时隙，一个时隙等于传送一帧的时间节点只能在一个时隙的开始才能传送节点需要同步，每个节点知道时隙何时开始如果一个时隙有多个节点同时传送，所有节点都能检测到冲突实现当节点要发送新帧，它等到下一时隙开始时传送没有冲突，节点可以在下一时隙发送新帧如果有冲突，节点在随后的时隙以概率p重传该帧，直到成功为止5-33时隙ALOHA优点单个活跃节点可以持续以满速率传送帧具有高分散性:只需节点的时隙同步简单缺点冲突，浪费时隙空闲时隙节点只有在传输数据包时才能检测到冲突5-34时隙Aloha效率假设有N个节点，每个节点在时隙以概率p发送一个节点在一个时隙成功传送的概率=p(1-p)N-1任一节点传送成功的概率

=Np(1-p)N-1

为了得到N个活跃节点的最大效率，必须找出使表达式Np(1-p)N-1

取最大值的p*为了得到大量活跃节点的最大效率，我们求N趋近无穷时Np*(1-p*)N-1极限值，计算可知最大效率为1/e=0.37效率：当有很多节点，每个节点有很多帧要发送时，成功时隙所占的百分比最佳:

信道有37%的有效传输5-35CSMA(CarrierSenseMultipleAccess)

载波侦听多路访问CSMA:

传送前侦听:如果信道闲：传送整个帧如果信道忙：延迟传送

类比人类行为：不打断他人！5-36CSMA冲突冲突还是可能发生:传播延迟可能导致两个节点没侦听到其它节点的传送冲突:整个数据包的传送时间被浪费spatiallayoutofnodes注意:距离和传播延时决定冲突概率5-37CSMA/CD(冲突检测)CSMA/CD:在一个短时间内检测冲突放弃传送，减少带宽浪费冲突检测:

有线LANs中容易：测量信号强度，比较传送和接收信号无线LANs中困难:传输中接收信号比传送信号很微弱人类行为：有礼貌的会谈5-38CSMA/CD协议基本思想：当一个节点要发送数据时，首先监听信道，看是否有载波如果信道空闲，则发送数据如果信道忙，则继续对信道进行监听。一旦发现空闲，便立即发送如果在发送过程中检测到碰撞，则停止自己的正常发送，转而发送一短暂的干扰信号jam，强化冲突，使其它站点都能知道出现了冲突发送了干扰信号后，退避随机时间，重新尝试发送5-39CSMA/CD协议讨论我有数据要发送监听5-40CSMA/CD协议讨论我有数据要发送监听网上有载波，等待5-41CSMA/CD协议讨论我有数据要发送监听发生冲突，立即回退冲突了！我也有数据要发送5-42“轮转”MAC协议分割信道MAC协议高负载效率高：信道共享公平高效低负载效率低：延迟访问，如果只有一个活跃节点只分配了1/N的带宽随机访问MAC协议低负载效率高：单个节点可以获得整个信道高负载：冲突开销大“轮转”协议两者的折中!5-43“轮转”

MAC协议1.轮询:

主节点轮流“邀请”从属节点传送数据缺陷：轮询开销延迟主节点失效，整个网络失效2.令牌传递：控制令牌从一个节点顺序传到下一个节点令牌消息缺陷：令牌开销延时令牌失效

5-44MAC协议总结信道分割：时间，频率，代码时分，码分，频分随机分割

(动态)ALOHA,S-ALOHA,CSMA,CSMA/CD载波侦听：有线网络容易实现，无线网络困难CSMA/CD用于以太网,CSMA/CA用于无线网络轮转中心节点轮询，令牌传递5-455.3.3局域网多址访问协议广泛应用于局域网基于随机访问的CSMA/CD广泛应用于局域网基于令牌传递技术的令牌环和FDDI在局域网技术中变得次要链路层技术的发展，局域网、城域网、广域网的概念变得越来越模糊和不重要5-46局域网概述局域网基本概念计算机网络拓扑结构计算机与局域网的互连局域网的体系结构5-47局域网概述主要特点：网络为一个单位所拥有，且地理范围和站点数目均有限局域网按拓扑结构进行分类：星形网、环形网、总线网、树形网和网状网5-48局域网概述局域网基本概念计算机网络拓扑结构计算机与局域网的互连局域网的体系结构5-49常见的网络拓扑结构

一、星型结构PC1PC4PC3PC2连接器5-50常见的网络拓扑结构

一、星型结构

辐射状连接中央结点集中式通信控制优点：结构简单，访问协议简单，单个节点的故障不会影响到整个网络。缺点：对中央结点的可靠性要求很高，一有故障，全网瘫痪。5-51常见的网络拓扑结构

二、总线结构PC1PC4PC2PC35-52常见的网络拓扑结构

二、总线结构所有的站点都连接在同一根传输线，即“总线”上。

优点：结构简单，易于扩充。

缺点：故障检测比较困难。5-53常见的网络拓扑结构

三、环型结构PC1PC3PC4PC25-54常见的网络拓扑结构

三、环型结构站与站点之间首尾相接，形成一个环，数据只能沿单方向传输。

优点：这种结构适合于光纤介质。实时性较强。

缺点：如果处理不当站点的故障会引起全网故障。

5-55常见的网络拓扑结构

四、树型结构PC2PC3PC4PC1连接器连接器连接器5-56常见的网络拓扑结构

四、树型结构它是从星型拓扑演变而来的，形状像一棵倒挂的树。

特点：与星型拓扑大致相似。它与星型结构相比降低了通信线路成本，增加了网络复杂性。5-57常见的网络拓扑结构

五、网状结构PC2PC3PC4PC1连接器连接器连接器连接器5-58常见的网络拓扑结构

五、网状结构网状网络的每一个站点都与其它站点一一直接互连。

优点：连接方法主要是利用冗余的连接，实现站与站之间的高速传输和高容错性能，以提高网络的速度和可靠性。

缺点：关系复杂，建网难，维护难5-59局域网概述局域网基本概念计算机网络拓扑结构计算机与局域网的互连局域网的体系结构5-60计算机与局域网的连接

计算机与局域网通过网络接口板进行连接，网络接口板又称通信适配器（Adapter）或网络接口卡NIC（NetworkInterfaceCard），通常我们称为“网卡”5-61计算机与局域网的通信计算机CPU高速缓存存储器网络接口卡（网卡）I/O总线并行通信至局域网串行通信5-62局域网概述局域网基本概念计算机网络拓扑结构计算机与局域网的互连局域网的体系结构5-63局域网体系结构计算机局域网现在已经成为计算机网络的主流，因此美国电气与电子工程师协会IEEE802委员会制定的IEEE802局域网标准已经得到了国际标准化组织ISO的采纳，成为计算机局域网的事实标准。IEEE802局域网参考模型是针对局域网的网络体系结构特点而制定的，它遵循ISO/OSI参考模型的原则，解决物理层和数据链路层的功能以及与网络层的接口服务、网际互连的高层功能5-64IEEE802与OSI参考模型对应关系应用层传输层网络层数据链路层物理层逻辑链路控制子层介质访问控制子层物理层（）（）（）服务访问点网卡网卡驱动程序OSI参考模型IEEE802参考模型5-65IEEE802网络协议标准IEEE802.1体系结构及高层接口IEEE802.2逻辑链路控制LLCIEEE802.3CSMA/CD（带冲突检测的载波侦听多路复用）访问控制方法和物理层技术规范IEEE802.4令牌总线访问控制方法和物理技术规范IEEE802.5令牌环访问控制方法和物理层规范IEEE802.6城域网访问控制方法和物理层技术规范5-66IEEE802标准的相互联系802.2802.1802.3802.4802.5802.6物理层介质访问控制子层逻辑链路控制子层5-67链路层5.1概述和服务5.2差错检测和纠错技术5.3多址访问协议5.4链路层编址5.5以太网5.6集线器和交换机5.7PPP：点到点协议5.8链路虚拟化:ATM和MPLS5-68局域网地址回顾：32位IP地址网络层地址用于把分组源网络送到目的IP网络IP协议初始化前配置48位MAC(或LAN或物理或Ethernet)地址:链路层地址用于把数据帧从一个接口传送到另一个接口(同一网络中)48位MAC地址固化在适配器的ROM5-69局域网地址在局域网中的每一个适配器都有一个唯一的LAN地址广播地址

=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-53LAN(wiredorwireless)5-70局域网地址MAC地址由IEEE统一分配厂商购买一块MAC地址空间

(要保证唯一性)比较:(a)MAC地址:类比于身份证号码

(b)IP地址:类比于邮政地址MAC地址具有扁平结构

=>可移动，但不会变能从一个LAN移动到另一个LANIP地址具有层次结构

=>移动会改变依赖节点所依附的IP网络5-71回顾：路由讨论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:查找B的IP地址，发现B和A在同一网络中链路层发送分组给B，该分组包含在链路层帧中B’sMACaddrA’sMACaddrA’sIPaddrB’sIPaddrIPpayloaddatagramframeframesource,destaddressdatagramsource,destaddress5-72ARP:地址解析协议局域网上的每个IP节点(Host,Router)都有ARP表ARP表:IP/MAC地址映射，格式如下：<IPaddress;MACaddress;TTL>

TTL(TimeToLive):

映射地址的失效时间(典型为20分钟)问题：主机A知道B的IP地址，它怎么知道B的MAC地址?IP地址MAC地址TTL222.222.222.22188-B2-2F-54-1A-0F13:45:00222.222.222.2235C-66-AB-90-75-B113:52:005-73ARP协议:实现假设：A想发送分组给B，A知道B的IP地址，B的MAC地址不在A的ARP表中（1）A广播包含B的IP地址的ARP查询包目的MAC地址=FF-FF-FF-FF-FF-FF在局域网上的所有机器都能收到ARP查询（2）B收到ARP包，回给A一个带有B的MAC地址的包包单播unicast发送给A的MAC地址（3）A缓存IP-to-MAC地址对在A的ARP表中，直到信息过期(timeout)ARP是即插即用的:无需网络管理员干预，节点就能创建ARP表5-74主机A路由到主机BA通过R向B发送分组假设A知道B的IP地址路由器R：有两个ARP表，每个针对一个IP网络(LAN)主机：知道路由器的IP：111.111.111.110主机的ARP表：发现路由器MAC地址E6-E9-00-17-BB-4BARB5-75A创建一个分组，源地址为A，目的地址为BA使用ARP表获得R的IP为111.111.111.110的MAC地址A创建一个链路层帧，该帧以R的MAC地址为目的地址，并包含A-to-B的IP数据包A的适配器发送帧R的适配器收到帧R从Ethernet帧中提取IP数据包，得知目的地址为BR使用ARP获得B的MAC地址R创建一个包含A-to-B的IP数据包的帧发送给BARB5-76相同子网的ARP发送站A将直接广播对B的ARP请求5-77不同子网的ARP发送站A将广播对“默认网关”即路由器左端口192.168.0.1的ARP请求，获得其MAC地址后将把发送给B的数据先发送到路由器左端口路由器收到数据并路由后，将在右端口广播B的ARP请求，获得B的MAC地址后进行数据转发。5-78注意：ARP协议与DHCP协议之间的区别和联系。DHCP协议参考第4章5-795.1概述和服务5.2差错检测和纠错技术5.3多址访问协议5.4链路层编址5.5以太网链路层5.6集线器和交换机5.7PPP：点到点协议5.8链路虚拟化:ATM和MPLS5-80以太网以太网是目前最流行的LAN技术70年代由DigitalEquipment、Intel和Xerox三家公司开发的局域网组网规范80年代初首次出版，称为DIX1.01982年修改后的版本为DIX2.0不久这三家公司公布了与IEEE802.3一致的以太网规范。Ethernet和IEEE802.3虽然有很多规定不同，但术语Ethernet通常认为与802.3是兼容的。IEEE将802.3标准提交国际标准化组织(ISO)第一联合技术委员会(JTC1),再次经过修订变成了国际标准ISO802.3。以太网使用的物理层标准有10BASE-T、10BASE2、10BASE5、10BASE-F等5-81以太网机构：星型拓扑90年代中期流行总线拓扑结构现在星型拓扑结构盛行连接设备:集线器hub或交换机switchtwistedpairhub5-82以太网：不可靠的无连接服务无连接：发送和接收适配器间不“握手”类似于传输层的UDP服务不可靠：接收适配器不向发送适配器发送确认帧CRC校验发现错误，则丢弃帧丢弃帧导致，传递到网络层的数据报流可能有间隙如果传输层使用TCP协议，间隙会被填好如果传输层使用UDP协议，应用能看见间隙因此，以太网提供的是不可靠的无连接服务5-83以太网技术以太网物理层传输机制以太网链路层控制技术5-84以太网物理层标准以太网的物理层标准（与传输介质相对应）：10BASE-T10BASE210BASE5100BASE-T1000BASE-T1000BASE-LX1000BASE-SX等5-85例：Ethernet技术100BASE-T速率：100Mbps被称为“快速ethernet”

T表示双绞线各节点都连接到集线器上“星型拓扑结构”在节点和适配器间最大距离为100米twistedpairhub5-86时间电平以太网物理层编码：曼彻斯特编码数据：01100101编码：5-87曼彻斯特编码机制利用一个时钟周期中间位置的电平跳变来表示“0”和“1”。中间跳变是由低电平跳变到高电平表示“1”中间跳变是由高电平跳变到低电平表示“0”注：

(1)在时钟周期边界处可以任意跳变而不影响编码含义

(2)采用曼切斯特编码，调制速率应为传输速率的2倍5-88以太网技术以太网物理层传输机制以太网链路层控制技术5-89媒体访问控制（MAC）MAC子层主要功能数据封装媒体访问管理帧同步、帧定界地址确定错误检测机制媒体分配（避免冲突）冲突解决（冲突处理）5-90MAC帧格式前导码SFDDASA类型数据（填充）CRC用于帧同步，7字节10101010帧开始定界符，1字节10101011目的地址，6字节源地址，6字节数据类型，2字节（网络层协议）上层要传输的数据，46-1500字节帧校验，4字节5-91MAC地址MAC帧中使用的地址标识即MAC地址，又称为硬件地址或物理地址。

MAC地址包括：目的地址源地址

MAC地址长度为48位，它被固化在网卡的ROM中。5-92MAC地址格式在目的地址中：第一比特为“0”时，表示帧要发送给某一工作站，即所谓单站地址当第一比特为“1”时，表示帧发送给一组工作站，即所谓组地址全“1”的组地址表示广播地址在源地址中第1比特恒为“0”I/G=0单站地址U/L=0全局地址I/G=1组地址U/L=1局部地址5-93全球MAC地址的管理IEEE的注册管理委员会(RAC)是局域网全球MAC地址的法定管理机构RAC负责分配MAC地址中的前3个字节，形成机构惟一标识符OUI网卡厂家向IEEE购买机构惟一标识符，然后厂家在自行指派低3个字节的扩展标识符最后形成6个字节的MAC地址，即MAC-48或扩展的惟一标识符EUI-485-94以太网媒体访问控制功能图LLC子层MAC子层物理层发送数据封装接收数据解封接收介质访问管理发送数据编码接收数据解码发送数据接收数据发送介质访问管理5-95Ethernet使用CSMA/CD协议非时隙采用了载波侦听机制采用了冲突检测机制在试图重传之前，适配器会等待一个随机时间,即随机访问5-96Ethernet的CSMA/CD算法1.适配器从网络层得到分组,创建帧2.如果适配器侦听到信道空闲,开始传送帧。如果信道忙,它会等到信道空闲才传送帧3.如果适配器传送整个帧都没有检测到其他传输（无冲突）,就完成该帧的传送4.如果适配器在发送中检测到其它传送（有冲突）,就放弃传送，并发送一个拥塞信号5.放弃传送后，适配器进入指数回退阶段，即该帧经过n次冲突后，适配器在{0,1,2,…,2m-1}中随机选取一个K值，其中m=min(n,10),然后等待K*512比特时间后,回到第2步5-97Ethernet的CSMA/CD算法(续)拥塞信号：48比特，确保所有传送者知道冲突发生比特时间：对于10MbpsEthernet为0.1微秒，

当K=1023，等待时间大约50毫秒指数回退：目标：适配器依据当前负载情况重传，重负载时等待时间变长第一次冲突：在{0,1}中选k值；延迟Kx512比特时间传送第二次冲突：在{0,1,2,3}中选k值…10次以后，在{0,1,2,3,4,…,1023}中选k值。5-985.1概述和服务5.2差错检测和纠错技术5.3多址访问协议5.4链路层编址5.5局域网概述链路层5.6集线器和交换机5.7PPP：点到点协议5.8链路虚拟化:ATM和MPLS5-99集线器－Hub集线器本质上是物理层的中继器：处理的基本单位是位信号放大，延长网络距离收到的位发送给所有其它连接节点多个端口使用相同的传输速率，没有帧缓存没有CSMA/CD：由计算机的网卡检测冲突twistedpairhubABCD5-100集线器内部逻辑结构端口1端口2端口3端口4集线器连接的网络物理上是星型拓扑结构逻辑上是总线型拓扑结构twistedpairhubABCD5-101集线器(Hub)所有集线器连接形成一个共享的逻辑网段，实现半双工的通信模式5-102集线器(Hub)各物理网段的冲突域汇集成一个大的冲突域（逻辑网段）冲突5-103集线器－Hub特点集线器工作在物理层（位为单位进行处理）广播式的通信方式，形成一个共享网段，导致大的冲突域，浪费网络带宽资源半双工的数据通信模式但是转发速度快twistedpairhubABCD5-104Ethernet交换机交换机工作在链路层基于帧转发,实现MAC地址过滤物理上和逻辑上都是星型结构交换：A-to-A’和B-to-B’同时工作，不冲突5-105交换机转发

交换机怎么确定将接收到的MAC帧转发到哪一个网段呢?hubhubhubswitchABCDEFGHI1235-106交换机的交换机制交换机内部保存一个源地址表又称为交换表交换表的表项:(MAC地址,接口,时间)

过期的表项将被删除(TTL可以是60分钟)交换机学习哪一个主机可以通过哪一个接口到达交换机当接收一数据帧时,交换机“学习”发送者的位置，即数据进入交换机的LAN网段与接口之间的对应关系在交换表中记录发送者/位置对应关系上述机制称之为交换机的“自学习”5-107交换机内部逻辑结构接口处理接口处理学习逻辑学习逻辑虑波/转发查找逻辑源地址表SAT地址端口5-108交换机举例假设A发送数据帧到E交换机接收来自A的数据帧注意在交换表中A在交换机的接口1上，E在交换机的接口2上交换机将转发数据帧到接口数据帧被E接收hubhubhubswitchABCDEFGHI接口ABEG1123123MAC地址5-109交换机举例假设C发送数据帧到D交换机接收来自C的数据帧记录C所对应的接口号1因为D不在交换表中,交换机将转发数据帧到接口2和3数据帧被D接收hubhubhubswitchABCDEFGHI接口ABEG1123123MAC地址C15-110交换机举例假设D回复数据帧给C.交换机接收来自D的数据帧记录D所对应的接口号为2因为C在交换表中，并且接口为1，则交换机只向接口1转发数据帧数据帧被C接收hubhubhubswitchABCDEFGHI接口1123123MAC地址C1ABEGD25-111交换机举例假设A发送数据帧到B会有什么结果呢？交换机接收来自A的数据帧注意在交换表中A在交换机的接口1上,B也在交换机的接口1上数据帧将被交换机丢弃hubhubhubswitchABCDEFGHI接口ABEG1123123MAC地址丢弃相同接口的数据帧5-112过滤/转发当交换机接收一数据帧时:

根据接收帧的目的MAC地址检索交换表if目的MAC地址的表项被发现

then{if如果目的地址在接收帧的网段中

then

丢弃该帧

else

转发该帧到指定的接口

}

else

广播

向所有(除接收帧所在的接口外)其它接口转发5-113交换机举例假设A和B同时发送数据帧会有什么结果呢？交换机会接收到来自端口1的冲突信息冲突信息将被交换机丢弃hubhubhubswitchABCDEFGHI123接口ABEG1123MAC地址冲突检测到冲突并丢弃5-114交换机:冲突隔离交换机将一个子网划分成若干个LAN网段交换机过滤数据包:

同一LAN网段的数据帧传输不被转发到其它LAN网段每个LAN网段变成一个独立的冲突域hubhubhubswitchcollisiondomaincollisiondomaincollision

domain5-115Ethernet交换机(Switch)主机A向主机C发送数据，同时主机D向主机B发送数据，将会出现？交换机某端口连接共享网段时,该端口需要使用CSMA/CD访问该网段冲突如何处理？？5-116Ethernet交换机总结链路层设备存储和转发以太网帧检查帧头,并根据目的MAC地址有选择的转发帧交换机直接连接的计算机不需要使用CSMA/CD协议，实现点到点的数据通信；但是，当MAC帧被转发到某一共享网段时,需要使用CSMA/CD访问该网段透明性主机不关心交换机的存在即插即用,自学习交换机不需要被配置5-117全交换网络:交换机专用接入交换机具有大量接口所有主机可以直接使用交换机连接成网络:全交换网络实现全双工模式运行：带宽变为原来的两倍switchAA’BB’CC’5-118交换机的交换特点识别目的MAC地址，根据交换表进行端口选择识别源MAC地址更新交换表在识别目的MAC地址和源MAC地址的过程中是否需要接收并缓存完整的帧呢？5-119存储转发交换方式接收操作端口1入数据端口2出数据发送操作差错检测缓冲区SAT虑波转发交换器整个帧整个帧5-120端口2出数据端口1入数据快速分组交换方式转发逻辑SAT入出交换器FCS数据域长度SADASFD前同步码5-121交换机的交换方式存储转发：具有差错检测功能，转发时延较大，适用于出错率高的链路。快速分组又称直通交换：不具有差错检测功能，转发时延较小，适用于时延要求高，出错率低的链路。5-122三层交换机三层交换是相对于传统的交换概念而提出的

传统的交换技术是在OSI网络参考模型中的第二层（即数据链路层）进行操作的，通常称做“二层交换机”。三层交换技术能够在网络模型中的第三层实现数据包的高速转发。简单地说，三层交换技术就是二层交换技术+三层转发技术，三层交换机就是“二层交换机+基于硬件的路由器”

5-123三层交换机的交换机制一次路由，多次交换125-124三层交换机的工作原理发送站点A在开始发送时，把自己的IP地址与B站的IP地址比较，判断B站是否与自己在同一子网内。若目的站B与发送站A在同一子网内，则进行二层的转发。若两个站点不在同一子网内，则发送站A要向“缺省网关”发出ARP请求，请求获得B的MAC地址。如果三层交换机知道B的MAC地址，则向A回复B的MAC地址。否则三层交换机根据路由信息向B站广播一个ARP请求，B站得到此ARP请求后向三层交换机回复其MAC地址，三层交换机将B站的MAC地址保存到二层交换引擎的MAC地址表中，并回复给发送站A。A直接用B的MAC地址封装数据帧，三层交换机接收到数据后直接进行二层交换。5-125兼容现有协议的三层交换机实现发送站点A在开始发送时，把自己的IP地址与B站的IP地址比较，判断B站是否与自己在同一子网内。若目的站B与发送站A在同一子网内，则进行二层的转发。若两个站点不在同一子网内，则发送站A要向“缺省网关”发出ARP请求，请求获得网关的MAC地址。发送站A根据网关的MAC地址，发送所有的数据到三层交换机三层交换机接收发送站A的第一个数据时进行路由选择并向B发出ARP请求，获得B的MAC地址，转发数据给B，同时保存B的IP地址、MAC地址和端口到高速缓存。三层交换机后续接收到的所有到达B的分组将直接根据高速缓存进行二层交换。5-126机构网络举例Switch/hubswitchtoexternalNetwork/OtherIPSubnetRouter/L3-switchIPsubnetmailserverwebserverSwitch/hubSwitch/hub5-127交换机vs.路由器比较都是存储转发设备路由器：网络层设备，转发分组交换机：数据链路层设备，转发帧路由器实现路由算法建立路由表，并转发分组交换机实现自学习包含交换表、转发/过滤switch5-128综合比较流量隔离即插即用优化路由直通交换5-1295.1概述和服务5.2差错检测和纠错技术5.3多址访问协议5.4链路层编址5.5以太网链路层5.6集线器和交换机5.7PPP：点到点协议5.8链路虚拟化:ATM和MPLS5-130点到点数据链路控制一个发送者，一个接收者，一条链路:较广播链路简单没有媒体访问控制不需MAC寻址是广域网的链路接入技术，例如：拨号链路,ISDN流行的点到点DLC（数据链路控制）协议:PPP(point-to-pointprotocol)HDLC:Highleveldatalinkcontrol5-131PPP设计需求[RFC1557]分组成帧:

把网络层分组封装到数据链路层帧中可以同时承载任何网络层协议数据单元可以向上多路分解支持多种网络层协议：支持运行多种网路层协议多种类型链路：运行在各种不同链路上透明性:

在数据域中可以装载网络层分组的任何位模式错误检测：检测接收帧中的比特错误(不纠错)连接的活性:

检测链路层故障，可将链路故障通知网络层网络层地址协商:

通信双方能学习/配置各自网络地址简单性5-132PPP不需的功能无错误纠正/恢复无流量控制无顺序提交不支持多点链路错误恢复，流量控制，数据排序都交给上层管理!5-133PPP工作原理初始状态建立连接请求数据通信状态5-134PPP数据控制协议在网络层数据通信之前，数据链路对等端必须配置PPP链路(最大帧长,认证)LCP链路控制协议学习/配置网络层信息(NCP,NetworkControlProtocol)IPCP网络控制协议5-135PPP帧格式标志域地址域控制域协议域信息域校验和标志域011111101111111111111100协议信息校验和01111110标识帧开始控制帧传输传输的数据标识帧结束标识目的地址传输数据协议类型，如：

LCP-C021，IPCP-8021IP-0021差错检查：CRC5-136字节填充

“数据透明性”需要：数据域可以包含标志模式<01111110>问题:

如何知道<01111110>是数据还是标志?发送方:

在每个<01111110>数据之前增加一个填充字节<01111101>

在每个<01111101>数据之前也增加一个填充字节<01111101>接受方:

遇到<01111101>就去掉，接收后面的数据单个01111110:标志字节5-137字节填充标志域地址域控制域协议域信息域校验和标志域011111101111111111111100协议信息校验和011111100111111011111111111111000010000101111110校验和01111110011111101111111111111100001000010111110101111110校验和01111110字节填充发送前发送数据011111101111111111111100001000010111110101111110校验和011111100111111011111111111111000010000101111110校验和01111110接收数据处理5-138字符填充使用控制字节0x7D对信息字段中出现的每一个0x7E进行处理。将信息字段中出现的每一个0x7E字节转变成为2字节序列(0x7D,0x5E)，其中后一个字节是原始字节与0x20异或的结果。若信息字段中出现一个0x7D的字节,则将其转变成为2字节序列(0x7D,0x5D)。若信息字段中出现ASCII码的控制字符（即数值小于0x20的字符），则在该字符前面要加入一个0x7D字节，同时将该字符的编码加以改变。5-139零比特填充PPP协议用在SONET/SDH链路时，是使用同步传输（一连串的比特连续传送）。这时PPP协议采用零比特填充方法来实现透明传输。在发送端，只要发现有5个连续1，则立即填入一个0。接收端对帧中的比特流进行扫描。每当发现5个连续1时，就把这5个连续1后的一个0删除5-1405.1概述和服务5.2差错检测和纠错技术5.3多址访问协议5.4链路层编址5.5以太网链路层5.6集线器和交换机5.7PPP：点到点协议5.8链路虚拟化:ATM和MPLS5-141虚拟化资源的虚拟化:系统工程中的一个强有力的抽象实例:虚拟内存,虚拟设备虚拟机:例如,Java虚拟机1960’s/70’s的IBMVMos抽像的层次:不关心更低层细节，只抽像的处理更低层5-142Internet:虚拟化网络1974:多个独立的网络

ARPAnet电缆传输数据网络卫星分组网络(Aloha)无线分组网络不同网络的区别:地址规范分组格式错误恢复路由ARPAnetsatellitenet"AProtocolforPacketNetworkIntercommunication",V.Cerf,R.Kahn,IEEETransactionsonCommunications,May,1974,pp.637-648.5-143Internet:虚拟化网络ARPAnetsatellitenetgateway互联网层(IP):

地址:

为低层异构的局域网提供统一的编址方式实现网络到网络的连接网关:

嵌入互联网分组到本地包格式中或者扩展格式中路由(在互联网层)到下一个网关5-144互联网结构什么是虚拟化?两个层次地址:互联网和本地网新的层次(IP)使所有的网络在互联网层同构,屏蔽了下层网络的差异低层的本地网络技术电缆卫星56K电话调制解调器今天的:ATM,MPLS

…上述技术在互联网层是“不可见的”.对于IP来说就象是一个链路层技术!5-145ATM和MPLSATM:异步传输模式，AsynchronousTransferModeMPLS:多协议标签交换，MultiprotocolLabelSwitchingATM,MPLS用它们自己的方式划分网络具有与Internet不同的服务模型、地址和路由从Internet的观点来看，它们作为连接IP路由器的逻辑链路就象拨号链路(电话网络)一样，它们也是不同网络的组成部分ATM和MPLS的技术研究集中在它们自己的技术领域5-146异步传输模式:ATM(AsynchronousTransferMode)随着人们对集话音、图像和数据为一体的多媒体通信需求的日益增加，人们提出了宽带综合业务数字网（B-ISDN），而B-ISDN的实现需要一种全新的传输模式，此即异步传输模式（ATM）。1990年，国际电报电话咨询委员会（CCITT）正式建议将ATM作为实现B－ISDN的一项技术基础，这样，以ATM为机制的信息传输和交换模式也就成为电信和计算机网络操作的基础和2l世纪通信的主体之一。5-147ATM基本概念融合了分组交换和电路交换的优点采用面向连接的虚电路分组交换机制分组具有固定长度（称为信元），便于实现电路交换采用异步传输模式进行交换转发

5-148同步传输模式5-149异步传输模式5-150ATM网络参考模型高层协议ATM适配层（AAL）ATM层物理层ATM适配层（AAL）:

在ATM网络的边缘数据分割和重组类似Internet的传输层ATM层:

类似于Internet的网络层信元交换,路由物理层：实现信元发送和接收5-151ATM网络高层协议AALATM层物理层高层协议AALATM层物理层ATM层物理层5-152ATM适配层(AAL)ATM适配层(AAL):“适配”上层(IP或ATM应用)到下面的ATM层AAL出现在端系统中，不在交换机中AAL层的段(头部/尾部，数据)被分割到多个ATM的信元里类似:TCP被分割到多个IP包里5-153ATM适配层(AAL)[续]不同的ATM服务有不同版本的AAL层:AAL1:

恒定比特率(CBR)服务和电路模拟AAL2:

可变比特率(VBR)服务，例如：MPEG视频AAL5:

数据传输，例如：IP数据报AALPDUATMcellUserdata汇聚子层拆装子层5-154ATM网络提供的服务CBR(ConstantBitRate)：提供固定速率的服务。VBR(VariableBitRate)：提供可变速率的服务，尽量满足用户的平均速率需求。ABR(AvailableBiteRate)：保证最小传输频宽的可变速率服务。UBR(UnspecifiedBitRate)：无任何保障的服务。其中AAL1支持CBR或UBR，AAL2支持VBR或UBR，AAL5支持所有类型。5-155ATM网络提供的服务与IP服务的比较NetworkArchitectureInternetATMATMATMATMServiceModelbesteffortCBRVBRABRUBRBandwidthnoneconstantrateguaranteedAve.rateguaranteedminimumnoneLossnoyesyesnonoOrdernoyesyesyesyesTimingnoyesyesnonoCongestionfeedbackno(inferredvialoss)nocongestionnocongestionyesnoGuarantees?5-156ATM层:虚电路虚电路传输:

信元从源到目的在虚电路上传输发送数据传输前需要建立一条虚电路每个信元需要包含一个虚电路标识（不是目的标识）源到目的路径上的每一次交换，都要维护传递连接的状态为了得到类似电路的性能，链路、交换资源（带宽和缓冲）可能被分配给虚电路永久VCs(PVCs)长期存在的连接典型:IP路由器之间的永久路由交换VCs(SVC):为每个请求动态设置的5-157ATMVCsATMVC的优点:能提供QoS性能保证(带宽，时延，时延抖动)ATMVC缺点:支持数据报效率低下在源和目的之间建立的永久虚电路的数量不成比例(N个入口和N个出口需要N*N条连接)交换虚电路引入请求建立虚电路的延时，对于短连接开销大5-158ATM层:ATM信元5字节ATM信元头部48字节负载Why?:小负载->缩短数字音频段创建信元时的延迟信元头-5B负载-48BSARPDU5-159ATM信元头部VPI/VCI:

虚通路或虚通道标识从一个链路到另一个链路VCI会发生变化PT:

负载类型CLP:

信元丢失优先级比特CLP=1意味着是低优先级信元，如果拥塞可以丢弃HEC:

首部差错控制字节循环冗余效验VPI/VCIPTCLPHEC负载-48B5-160ATM物理层2个子层:传输汇聚子层(TCS):

使ATM层能适配下面的PMD子层物理介质相关子层(PMD):

依赖所用的物理介质TCS功