计算机网络chapter3.ppt
第三章第三章 介质访问子层介质访问子层MAC子子层层的的基基本本功功能能是是:如如何何确确定定网网上上哪哪一一台台计计算算机机占占有有介介质质(信信道道)进进行行发发送送,或或者者说说,如何分配介质的问题。如何分配介质的问题。介质分配的方法可分为两大类:介质分配的方法可分为两大类:一一、静静态态分分配配,例例如如频频分分多多路路复复用用(FDM)、异异步步分分时时复复用用(ATDM)和和同同步步分分时时复复用用(STDM)等。等。二、动态分配,又分为:二、动态分配,又分为:1.集集中中式式,例例如如询询问问式式和和100VG_Any LAN的的请求优先级,等等。请求优先级,等等。2.分分 布布 式式,例例 如如 以以 太太 网网、IEEE 802.3的的CSMA/CD协协议议,令令牌牌协协议议以以及及通通信信中中的的码码分分多址(多址(CDMA)协议等。协议等。1第一节第一节 信道的静态分配信道的静态分配所谓介质的静态分配是指介质分配给谁是预先确定好的,与介质所谓介质的静态分配是指介质分配给谁是预先确定好的,与介质实际发送情况无关。介质的静态分配又可分为以下几种:实际发送情况无关。介质的静态分配又可分为以下几种:一频分多路复用(一频分多路复用(FDM)这种方法用于模拟信道的分配这种方法用于模拟信道的分配二同步分时复用(二同步分时复用(STDM)例如一个例如一个E1信道可以传送信道可以传送30路话音和相应的信令。路话音和相应的信令。但每一但每一种信号都分配在确定的时隙上传送,所以称为同步分时复用。种信号都分配在确定的时隙上传送,所以称为同步分时复用。三异步分时复用(三异步分时复用(ATDM),),将多个异步信号放在同一个信道上传送,到达目的后再分开。将多个异步信号放在同一个信道上传送,到达目的后再分开。为了解决不同异步信号在同一个信道传送的问题,在复用前必为了解决不同异步信号在同一个信道传送的问题,在复用前必须进行缓存。须进行缓存。四、波分多路复用四、波分多路复用WDM(Wave lengh Division Multiplexing)采采用光波折射原理,使用衍射光栅或梭柱。用光波折射原理,使用衍射光栅或梭柱。通道两端的波长差在10100纳米范围内称为WDM,在110纳米范围内称为密集波分复用DWDM。当前见到的报导,一根光纤可以传送25640Gbps=10.24Tbps.的信号。2Poisson分布分布 (泊松分布)(泊松分布)稳定而与过去独立的事件在间隔稳定而与过去独立的事件在间隔t内发生内发生k次的概率是次的概率是:第二节第二节 动态分配的数学基础动态分配的数学基础是单位时间内发生的平均次数。是单位时间内发生的平均次数。3证明:证明:取取,在,在内,发生一次事件的概率内,发生一次事件的概率发生多次事件的概率发生多次事件的概率不发生事件的概率不发生事件的概率 一、先求一、先求P0(t)4两边取极限:两边取极限:即:即:初始条件初始条件P0(0)=1解得解得:即:即:5即:即:两边取极限:两边取极限:二、再求二、再求Pk(T)6初始条件:Pk(0)=0从从开始递推:开始递推:解:解:7在时间间隔在时间间隔 t 内,事件平均发生次数:内,事件平均发生次数:,即单位时间内发生事件的平均次数,即单位时间内发生事件的平均次数8例例:假假设设电电话话呼呼叫叫按按每每小小时时平平均均30次次的的Poisson过过程程进进行行变变化化,试试问问在在5分分钟钟间间隔隔内内不不呼呼叫叫和和有有3次次呼呼叫叫的的概概率率各为多少?各为多少?解:解:910二和的二和的Poisson分布分布有两离散随机变量有两离散随机变量k1,k2,则则 k=k1+k2 分布是分布是11 对可数多个离散变量对可数多个离散变量k1,k2,.kn和的分布仍为和的分布仍为Poisson分布分布即网上多计算机发送帧的数量也服从泊松分布。即网上多计算机发送帧的数量也服从泊松分布。12第三节第三节 信道的动态分配信道的动态分配基本假设(基本假设(5个)个)1站模型站模型 假设假设n站,每站发数据服从泊松分布站,每站发数据服从泊松分布2单信道单信道3冲突假设冲突假设4 站的发送时间站的发送时间 4a时间连续性假设时间连续性假设 4b时间分槽假设时间分槽假设 4c 其他时间假设其他时间假设5载波监听假设载波监听假设 5a发送前监听发送前监听 5b发送前后均监听发送前后均监听 5c发送前后均不监听发送前后均不监听133-3-1 ALOHA系统系统一纯一纯ALOHA采用的假设:采用的假设:1,2,3,4a,5c前提条件:各帧长度相同前提条件:各帧长度相同帧时帧时tf:发送一个标准长度的帧所需时间发送一个标准长度的帧所需时间产生率(负载)产生率(负载)G:每帧时发送的平均帧数每帧时发送的平均帧数 G=tf14吞吐率吞吐率S:每帧时网络成功发送的平均帧数每帧时网络成功发送的平均帧数我们有我们有 0=S=S 现在求吞吐率现在求吞吐率S S=G P成成 P成成为成功发送帧的概率为成功发送帧的概率tt0-tft0t0+tf冲突危险区冲突危险区发发送送一一帧帧15若要取得最大吞吐率,对上式求导,令若要取得最大吞吐率,对上式求导,令1617二分槽二分槽ALOHA采用的假设:采用的假设:1,2,3,4b,5c通常通常 时槽时槽=帧时,但不一定。帧时,但不一定。tf0-tft0t0+tf冲突危险区冲突危险区发发送送一一帧帧183-3-2载波监听多路访问CSMA类协议类协议一、1-坚持(1-persistent)CSMA协议每站发送前监听信道:若忙,则不发送;等待直到信道闲再发送。其吞吐率和负载的关系如图3.4所示。二、不坚持(Nonpersistent)CSMA协议每站发送前监听信道:若忙,则等待一个随机时间再监听;若空则发送。其吞吐率和负载关系如图3.4所示。这种协议比上一协议容易避免冲突,因而吞吐率较高,但延迟较大。三、p-坚持(p-persistent)CSMA协议每站发送前监听信道:若忙,则下一个时槽再监听;若空,则以概率p发送,而以概率1-p推到下一时槽再监听。19四四CSMA/CD 每站发送前像每站发送前像1-坚持坚持CSMA那样监听信道:若忙,则不那样监听信道:若忙,则不发送;等待直到信道闲再发送。而且发送后还要监听信道,发送;等待直到信道闲再发送。而且发送后还要监听信道,若监听到冲突则停止发送。重试;若监听到无冲突则成功。若监听到冲突则停止发送。重试;若监听到无冲突则成功。发送后要监听多少时间?发送后要监听多少时间?2 是网上最远两站间信号的传送时间,包括设备延迟时是网上最远两站间信号的传送时间,包括设备延迟时间和介质传播时间之和。间和介质传播时间之和。20 第三章习题第三章习题 1、纯、纯ALOHA信道容量为信道容量为1Mpbs.每帧每帧1000位,位,平均每秒有平均每秒有1000帧要发送(含始发帧和重发帧)求帧要发送(含始发帧和重发帧)求吞吐率。吞吐率。2、1万个站竟争使用一个分槽万个站竟争使用一个分槽ALOHHA信道,信道,各站每小时平均发出各站每小时平均发出18个帧。时槽长度为个帧。时槽长度为125微秒,微秒,总的产生率(负载)为多少总的产生率(负载)为多少?3、总线网下有、总线网下有8个站,采用基本位图法,当个站,采用基本位图法,当8个个站均要发送或仅有一站要发送时,试画出其总线工站均要发送或仅有一站要发送时,试画出其总线工作示意图。设竟争时槽作示意图。设竟争时槽851微秒,数据帧长微秒,数据帧长1ms,其效率和平均迟延为多少其效率和平均迟延为多少?4、设平均每帧时有、设平均每帧时有10帧和帧和0.1帧要发送。求分槽帧要发送。求分槽ALOH协议的吞吐率并比较二者的效率和迟延协议的吞吐率并比较二者的效率和迟延.21重负载时,吞吐率降低非常快重负载时,吞吐率降低非常快 效效率率:指指发发送送帧帧的的持持续续时时间间与与为为了了发发送送帧帧花花掉掉的的总总时时间间(包包括括竞竞争争时时间间和和发发送送持持续续时时间间等等等)之比的平均值。等)之比的平均值。迟迟延延:指指有有帧帧要要发发送送到到实实际际开开始始发发送送所所需需的的平均等待时间。平均等待时间。有冲突协议(有冲突协议(ALOHA类和类和CSMA类)类)重负载时效率重负载时效率低低 轻负载时迟延轻负载时迟延低低为提高吞吐率和效率,开发了无冲突协议为提高吞吐率和效率,开发了无冲突协议3-3-3 无冲突协议无冲突协议22一、基本位图法其中,其中,n为竞争时槽的时间;为竞争时槽的时间;d为发送为发送1帧的持续时间;帧的持续时间;m为网上的站数。为网上的站数。23二、二进制倒计数(二、二进制倒计数(Binary Countdown)法法 这种方法是位图法的变种。为了提高效率,减少竞争时这种方法是位图法的变种。为了提高效率,减少竞争时槽的位数。对于槽的位数。对于n个站的系统,竞争时槽不是个站的系统,竞争时槽不是n位,而是位,而是log2n位。位。1111 1.将自己站的站号的二进制数,从高位到低位写入将自己站的站号的二进制数,从高位到低位写入竞争时槽,竞争时槽,1写入写入1;0不写。不写。2.若本站未写入前,若发现竞争时槽更高位已被写入若本站未写入前,若发现竞争时槽更高位已被写入1,则停止写入,并且放弃发送。,则停止写入,并且放弃发送。3.紧随竞争时槽后的传送时间仅允许站号为竞争时槽紧随竞争时槽后的传送时间仅允许站号为竞争时槽写入数的一个站发送写入数的一个站发送轻负载时轻负载时重负载时重负载时24 二进制倒计数法的竞争槽时间包含有源站的序号,如二进制倒计数法的竞争槽时间包含有源站的序号,如果把它视为发送帧的源地址码,那么,二进制倒计数法无果把它视为发送帧的源地址码,那么,二进制倒计数法无论负载轻重,其效率最高为论负载轻重,其效率最高为100%;其延迟最低轻负载时;其延迟最低轻负载时为为0。3-4 有限竞争协议有限竞争协议 竞争类协议(竞争类协议(ALOHA类和类和CSMA类协议)轻负载时类协议)轻负载时迟延小,但重负载时效率低;而无冲突协议,轻负载时迟迟延小,但重负载时效率低;而无冲突协议,轻负载时迟延较大,而重负载时效率较高。人们期望着研究出一个协延较大,而重负载时效率较高。人们期望着研究出一个协议,兼有二者的优点,即轻负载时延迟小,而重负载时效议,兼有二者的优点,即轻负载时延迟小,而重负载时效率高。有限竞争协议就是这样的协议。率高。有限竞争协议就是这样的协议。有限竞争协议分为静态分组法和动态分组法两种。有限竞争协议分为静态分组法和动态分组法两种。25一、静态分组法一、静态分组法 设一个分槽设一个分槽ALOHA系统,有系统,有n个站。每个站的产生个站。每个站的产生率均为率均为Gi。我们将我们将n个站共分为个组,每个组具有个站共分为个组,每个组具有m个个站。站。应该使每个组的总产生率应该使每个组的总产生率G=mGi为为1,以保证吞吐,以保证吞吐率最大。则率最大。则m=1/G,这样可以保证每个组的吞吐率为这样可以保证每个组的吞吐率为0.37 下面举两个特例:下面举两个特例:1.Gi=1时,时,m=1,本法成为位图法一无冲突协议。本法成为位图法一无冲突协议。2.Gi=时时,n=m本本法法成成为为分分槽槽ALOHA协协议议竞竞争争类类协议。协议。26二、动态分组法二、动态分组法适应树搜索协议适应树搜索协议 A B C D E F G 0 1 2 3 4 5 6 7 图3.6 适应搜索树协议示意图27 A A B C D E F G 结束 0 1 2 3 4 5 6 728