分组成功传输的概率NetworkDesignandAnalysis

多址接入协议（一）主要内容多址接入协议概述固定多址接入协议随机多址接入协议冲突分解算法预约多址协议主要内容多址接入协议概述固定多址接入协议随机多址接入协议载波侦听型多址协议冲突分解算法预约多址协议多址接入协议概述（1）网络中的终端设备通过通信子网来访问网络中的资源。当多个终端同时访问同一资源（如共享的通信信道）时，就可能会产生信息碰撞，导致通信失败。典型的共享链路有：卫星链路和蜂窝移动通信系统的链路、局域网、分组无线电网等多址接入协议概述（2）为了有效的进行通信，就需要有某种机制来决定资源的使用权，这就是网络的多址接入控制问题。所谓多址接入协议（MultipleAccessProtocol）就是在一个网络中，解决多个用户如何高效共享一个物理链路资源的技术。多址协议应尽量避免用户之间的碰撞，并使信道利用率最高。多址接入协议概述（3）在ISO的OSI参考模型中，数据链路层的功能相对简单。它只负责将数据从一个节点可靠地传输到相邻节点。但在局域网中，多个节点共享传输介质，必须有某种机制来决定下一个时刻，哪个设备占用传输介质传送数据。因此，局域网的数据链路层要有介质访问控制的功能。为此，一般将数据链路层又划分成两个子层：

●逻辑链路控制LLC（LogicLineControl）子层

●介质访问控制MAC（MediaAccessControl）子层

多址接入协议概述（4）从分层的角度来看，多址技术是数据链路层的一个子层。它处于数据链路逻辑控制层下方，物理层的上方，一般称为介质访问控制子层－－MAC层。该层用于在各种通信节点中分配多路访问介质，仲裁介质的使用权，即规定站点何时可以使用通信介质。MAC层将有限的资源分配给多个用户，从而使得在众多用户之间实现公平、有效地共享有限的带宽资源；实现各用户之间良好的连通性，获得尽可能高的系统吞吐量、以及尽可能低的系统时延。逻辑链路控制（LLC）子层为本节点提供了到其相邻节点的“链路”，而如何协调本节点和其它节点来有效地共享带宽资源，是媒质接入控制子层⎯MAC层的主要功能。多址接入协议概述（5）如果多台计算机连接到一条共有链路上，这些计算机就必须使用相同的规则来访问共享的链路，这个功能就是访问控制。由于链路是共享的，MAC必须在每个分组上加入目的端的物理地址，每个物理地址唯一地表示一个在共享链路中的设备。在点对点的链路中是不需要这样的物理地址的。一般有四种不同格式的以太网帧在使用：EthernetII即DIX2.0。Cisco名称为：ARPA。（格式见下图）Ethernet802.3raw。Cisco名称为：Novell-Ether。Ethernet802.3SAP。Cisco名称为：SAP。Ethernet802.3SNAP。Cisco名称为：SNAP。多址接入协议概述（6）MAC层实现连接到公共链路上的计算机之间的不可靠分组传输。逻辑链路控制LLC层使用MAC层提供的不可靠的分组传输来实现连接在一条共享链路上的计算机之间的差错检测或是可靠的分组传输。LLC的功能和点到点链路的数据链路层的功能是一样的。LLC层和MAC层共同组成了多点访问链路的数据链路层：它们使用物理层的不可靠比特链路来实现连接在一条共享链路上的计算机之间的无差错的分组传输服务或可靠的分组传输服务。多址接入协议概述（7）多址协议的分类（1）固定分配多址接入协议：是指在用户接入信道时，专门为其分配一定的信道资源（如频率、时隙、码字或空间），用户独享该资源，直到通信结束。－－FDMA、TDMD等随机分配多址接入协议：是指用户可以随时接入信道，并且可能不会顾及其它用户是否在传输。当信道中同时有多个用户接入时，在信道资源的使用上就会发生冲突（碰撞）。因此，对于有竞争的多址接入协议如何解决冲突从而使所有碰撞用户都可以成功进行传输是一个非常重要的问题。基于预约方式的多址接入协议：是指在数据分组传输之前，先进行资源预约。一旦预约到资源（如频率、时隙），则在该资源内可进行无冲突的传输。多址接入协议概述（8）多址协议的分类（2）多址接入协议概述（9）系统模型（1）从排队论的观点出发，多址信道可以看成一个多进单出的排队系统（即该系统有多个输入而仅仅有一个输出）。每一个节点都可以独立的产生分组，而信道则相当于服务员，它要为各个队列服务。由于各个排队队列是相互独立的，各节点无法知道其它队列的情况，服务员也不知道各个队列的情况，所以增加了系统的复杂性。如果我们可以通过某种措施，使各个节点产生的分组在进入信道之前排列成一个总的队列，然后由信道来服务，则可以有效的避免分组在信道上的碰撞，大大提高信道的利用率。多址接入协议概述（10）系统模型（2）多址接入协议概述（11）系统模型（3）用户到达是随机的目标：协调用户的传输，有效地使用信道多址接入协议概述（12）系统模型（4）：为了能够有效的分析多址接入协议，需要根据应用环境做一些假设。在讨论每种多址协议时，应该考虑下列问题：网络的连通特性。通常我们将网络按其连通模式分为：单跳、两跳及多跳网络：所谓单跳网络是指网络中所有的节点都可以接收到其它节点发送的数据；所谓两跳网络是指网络中的部分节点之间不能直接通信，需要经过一次中继才能通信；所谓多跳网络是指网络中源节点和目的节点之间的通信可能要经过多次中继。多跳网络既可以是有线网络，也可以是无线网络。我们知道，在无线通信网络中，通信节点之间的有效通信距离是由发端的发送功率、节点之间的距离、以及接收机灵敏度等条件决定的。这里主要讨论的是对称的信道，即任意两个在通信距离内的节点都可以有效的和对方进行通信。多址接入协议概述（13）系统模型（5）：同步特性。通常用户是可以在任意时刻接入信道，但也可以以时隙为基础接入信道。在基于时隙的系统中，用户只有在时隙的起点才能接入信道。在这种系统中，要求全网有一个统一的时钟，同时将时间轴划分成若干个相等的时间段，称之为时隙。系统中所有数据的传输开始点都必须在一个时隙的起点。反馈和应答机制。反馈信道是用户获得信道状态的途径。这里的讨论都假设用户（节点）可以获得信道的反馈信息，即信道是空闲、碰撞还是进行了一次成功传输。数据产生模型。所有的用户都按照泊松过程独立地产生数据。主要内容多址接入协议概述固定多址接入协议随机多址接入协议冲突分解算法预约多址协议固定多址接入协议(1)固定多址接入协议又称为无竞争的多址接入协议或静态分配的多址接入协议。固定多址接入为每个用户固定分配一定的系统资源，这样当用户有数据发送时，就能不受干扰地独享已分配的信道资源固定多址接入的优点在于可以保证每个用户之间的“公平性”（每个用户都分配了固定的资源）以及数据的平均时延。典型的固定多址接入协议有：频分多址（FDMA）、时分多址（TDMA）、码分多址（CDMA）及空分多址（SDMA）等。频分多址（1）频分多址FrequencyDivisionMultipleAccess（FDMA）是把通信系统的总频段划分成若干个等间隔的频道（或称信道），并将这些频道分配给不同的用户使用，这些频道之间互不交叠。频分多址（2）FDMA的最大优点是相互之间不会产生干扰。当用户数较少且数量大致固定、每个用户的业务量都较大时（比如在电话交换网中），FDMA是一种有效的分配方法。但是，当网络中用户数较多且数量经常变化，或者通信量具有突发性的特点时，采用FDMA就会产生一些问题。最显著的两个问题是：当网络中的实际用户数少于已经划分的频道数时，许多宝贵的频道资源就白白浪费了；而且当网络中的频道已经分配完后，即使这时已分配到频道的用户没有进行通信，其他一些用户也会因为没有分配到频道而不能通信。时分多址时分多址TimeDivisionMultiple

Access

(TDMA)也是一种典型的固定多址接入协议。TDMA多址接入协议将时间分割成周期性的帧，每一帧再分割成若干个时隙（无论帧或时隙都是互不重叠的），然后根据一定的时隙分配原则，使每个用户只能在指定的时隙内发送。在时分多址的系统中，用户在每一帧中可以占用一个时隙，如果用户在已分配的时隙上没有数据传输，则这段时间将被浪费。固定多址接入协议(2)CDMA的物理信道在时间和频谱上是重叠的，它是利用码字（或波形）的正交性来区分不同的物理信道SDMA是利用阵列天线形成载波束（每个波束仅照射有限的区域）来实现空间上的分割，不同的用户占据不同的空间，而这些用户可以使用相同的频率、时隙和码字。固定多址接入协议(3)固定分配多址技术的优点是适合于恒定比特流的业务传输不足主要是当用于突发性数据业务传输时，通常会引入较大的时延固定多址技术可以采用M/M/m排队模型来分析主要内容多址接入协议概述固定多址接入协议随机多址接入协议冲突分解算法预约多址协议随机多址接入协议随机多址协议又叫做有竞争的多址接入协议。网络中的节点在网络中的地位是等同的，各节点通过竞争获得信道的使用权。随机多址接入协议又可细分为完全随机多址接入协议（ALOHA协议）和载波侦听型多址接入协议。不论是哪种随机多址接入协议，我们主要关心两个方面的问题：一个是稳态情况下系统的通过率和时延性能，另一个是系统的稳定性。ALOHA协议(1)ALOHA协议是70年代Hawaii大学建立的在多个数据终端到计算中心之间的通信网络中使用的协议。其基本思想是：若一个空闲的节点有一个分组到达，则立即发送该分组，并期望不会和其它节点发生碰撞。为了分析随机多址接入协议的性能，假设系统是由m个发送节点组成的单跳系统，信道是无差错及无捕获效应的信道，分组的到达和传输过程满足如下假定：各个节点的到达过程为独立的、参数为λ/m的Poisson到达过程，系统总的到达率为λ。ALOHA协议(2)在一个时隙或一个分组传输结束后，信道能够立即给出当前传输状态的反馈信息。反馈信息为“0”表明当前时隙或信道无分组传输，反馈信息为“1”表明当前时隙或信道仅有一个分组传输（即传输成功），反馈信息为“e”表明当前时隙或信道有多个分组在传输，即发生了碰撞，导致接收端无法正确接收。

碰撞的节点将在后面的某一个时刻重传被碰撞的分组，直至传输成功。如果一个节点的分组必须重传，则称该节点为等待重传的节点。ALOHA协议(3)对于节点的缓存和到达过程作如下假设:假设A：无缓存情况。在该情况下，每个节点最多容纳一个分组。如果该节点有一个分组在等待传输或正在传输，则新到达的分组被丢弃且不会被传输。在该情况下，所求得的时延是有缓存情况下时延的下界（Low

Bound）。假设B：

系统有无限个节点

（m=

）。

每个新产生的分组到达一个新的节点。这样网络中所有的分组都参与竞争，导致网络的时延增加。因此，在该假设情况下求得的时延是有限节点情况下的时延上界

（UpBound）。纯ALOHA协议(1)纯ALOHA协议是最基本的ALOHA协议。只要有新的分组到达，就立即被发送并期望不与别的分组发生碰撞。一旦分组发生碰撞，则随机退避一段时间后进行重传。纯ALOHA协议(2)如果从数据分组开始发送的时间起点到其传输结束的这段时间内，没有其它数据分组发送，则该分组就不会和其它分组发送碰撞。在什么情况下图中阴影部分表示的数据分组（在t0+t时刻产生的分组）可以不受任何干扰的发送呢？为了便于分析，假设系统中所有分组的长度相等，传输数据分组所需的时间定义为系统的单位时间，为了简化描述，令该值等于t，并在下面的分析中令其等于1。纯ALOHA协议(3)我们将时间区间[t0,t0+2t]称为阴影分组（在t0+t时刻产生的分组）的易受破坏区间。很显然，在纯ALOHA协议中，只有在数据分组的易受破坏区间内没有其它分组传输，则该分组可以成功传输。为了分析方便，设系统有无穷多个节点（假设B），假定重传的时延足够随机，重传分组和新到达分组合成的分组流是到达率为G的Poisson到达过程。则在纯ALOHA系统中，一个分组成功传输的概率，就是在其产生时刻前一个时间单位内没有分组发送，并且在该分组产生时刻的后一个时间单位内仅有一个分组发送的概率纯ALOHA协议(4)根据泊松公式，在单位时间内，产生k个分组的概率是则根据上面的分析，我们可以得到在纯ALOHA系统中，分组成功传输的概率纯ALOHA协议(5)在单位时间的意义上，系统分组成功发送的概率即为系统的通过率对上式求最大值，可得系统的最大通过率为对应的G=0.5纯ALOHA协议(6)纯ALOHA（P-ALOHA）是一种完全随机的多址方式，全网不需要定时和同步，各站发射时间是完全随机的。当小站数目不多时，系统能够很好地工作，其信道利用率比TDMA按需分配方式还要高，并具有一定的抗干扰能力。而当小站数目很多，传输业务繁忙时，发生碰撞的概率增大，信道的传输效率就降低，最高只能达到18.4％，且存在潜在不稳定性。时隙ALOHA协议(1)从前面的描述中可以看到，在纯ALOHA协议中，节点只要有分组就发送，易受破坏区间为两个单位时间。如果我们缩小易受破坏区间，就可以减少分组碰撞的概率，提高系统的利用率。基于这一出发点，提出了时隙ALOHA协议时隙ALOHA系统将时间轴划分为若干个时隙，所有节点同步，各节点只能在时隙的开始时刻才能够发送分组，时隙宽度等于一个分组的传输时间，当一个分组到达某时隙后，它将在下一时隙开始传输，并期望不会与其它节点发生碰撞。如果在某时隙内，仅有一个分组到达（包括新到达的分组和重传分组的到达），则该分组会传输成功。如果在某时隙内到达两个或两个以上的分组，则将会发生碰撞。碰撞的分组将在以后的时隙中重传。很显然，此时的易受破坏区间长度减少为一个单位时间（时隙）。时隙ALOHA协议(2)

利用前面的假设条件，并假定系统有无穷多个节点(假设B)。从图中可以看出在一个时隙内到达的分组包括两个部分：一部分是新到达的分组，另一部分是重传的分组。设新到达的分组是到达率为λ(分组数/时隙)的Poisson过程。假定重传的时延足够随机化，这样就可以近似地认为重传分组的到达过程和新分组的到达过程之和是到达率为G(>λ)的Poisson过程。时隙ALOHA协议(3)ALOHA协议的通过率曲线时隙ALOHA协议(4)若干个终端用纯ALOHA随机接入协议与远端主机通信。信道速率为2.4kb/s。每个终端平均每3分钟发送一个帧，帧长为200bit，问系统中最多可容纳多少个终端？若采用时隙ALOHA协议，其结果又如何？时隙ALOHA协议稳定性分析(1)时隙ALOHA协议稳定性分析(2)时隙ALOHA协议稳定性分析(3)为了分析系统的动态行为，先采用假设A（无缓存的情况）来进行讨论。时隙ALOHA的行为可以用离散时间马尔可夫链来描述，其系统