软件测试管理

当前位置:首页 > 软件测试管理

《计算机网络:自顶向下方法》第五章 续1

5.3多路访问链路和协议


在本章概述中,我们提到了有两种类型的网络链路:点对点链路和广播链路。点对点链路(point-to point link)由链路端的单个发送方和链路另一端的单个接收方组成。许多链路层协议都是为点对点链路设计的,如点对点协议( point- to- point protocol, PPP)和高级数据链路控制( high- level data link control, HDLC)就是两种这样的协议,我们将在本章后面涉及它们。第二种类型的链路是广播链路( broadcast link), 它能够让多个发送和接收结点都连接到相同的、单一的、共享的广播信道上。这里使用术语“广播”是因为当任何一个结点传输一个帧时,信道广播该帧,每个其他结点都收到个副本。 以太网和无线局域网是广播链路层技术的例子。在本节,我们暂缓讨论特定的链路层协议,而先研究一个对链路层很重要的问题:如何协调多个发送和接收结点对一个共享广播信道的访问,这就是多路访问问题( multiple access problem)。广播信道通常用于局域网中局域网是一个地理上集中在一座建筑物中(或者在一个公司,或者在大学校园)的网络。因此我们还将在本节后面考察一下多路访问信道是如何在局域网中使用的。


我们都很熟悉广播的概念, 因为自电视发明以来 就使用了这种通信方式。但是传统的电视是一种一个方向的广播(即一个固定的结点向许多接收结点传输),而计算机网络广播信道上的结点既能够发送也能够接收。也许对广播信道的一个更有人情味的类比是鸡尾酒会,在那里许多人聚集在一个大房间里(空气为提供广播的媒体)谈论和倾听。第二个切题的类比是许多读者都很熟悉的地方,即一间教室,在那里老师们和同学们同样共享相同的、单一的广播媒体。在这两种场景下,一个中心问题是确定谁以及在什么时候获得说话权力(也就是向信道传输)。作为人类,为了共享这种广播信道,我们已经演化得到了一个精心设计的协议集了:


“给每个人一个讲话的机会。”


“该你讲话时你才说话。”


“不要一个人独占整个谈话。


“如果有问题请举手。”


“当有人讲话时不要打断。”


“当其他人讲话时不要睡觉。”


计算机网络有类似的协议,也就是所谓的多路访问协议( multiple access protocol), 即结点通过这些协议来规范它们在共享的广播信道上的传输行为。如图5-8所示,在各种各样的网络环境下需要多路访问协议,包括有线和无线接入网,以及卫星网络。尽管从技术上讲每个结点通过它的适配器访问广播信道,但在本节中我们将把结点作为发送和接收设备。在实践中,数以百计或者甚至数以千计个结点能够通过一个广 播信道直接通信。


《计算机网络:自顶向下方法》第五章


因为所有的结点都能够传输帧,所以多个结点可能会同时传输帧。当发生这种情况时,所有结点同时接到多个帧:这就是说,传输的帧在所有的接收方处碰撞( collide)了。通常,当碰撞发生时,没有一个接收结点能够有效地获得任何传输的帧;在某种意义下,碰撞帧的信号纠缠在一起。 因此,涉及此次碰撞的所有帧都丢失了,在碰撞时间间隔中的广播信道被浪费了。显然,如果许多结点要频繁地传输帧,许多传输将导致碰撞,广播信道的大量带宽将被浪费掉。


当多个结点处于活跃状态时,为了确保广播信道执行有用的工作,以某种方式协调活跃结点的传输是必要的。这种协调工作由多路访问协议负责。在过去的40年中,已经有上千篇文章和上百篇博士论文研究过多路访问协议;有关这部分工作前20年来的一个内容丰富的综述见[ Rom 1990]。此外,由于新类型链路尤其是新的无线链路不断出现,在多路访问协议方面研究的活跃状况仍在继续。


这些年来,在大量的链路层技术中已经实现了几十种多路访问协议。尽管如此,我们能够将任何多路访问协议划分为3种类型之一: 信道划分协议( channel partitioning protocol),随机接入协议( random access protocol)和轮流t协议( taking-turms protocol)。我们将在后续的3个小节中讨论这几类多路访问协议。


在结束概述之前,我们给出下列条件。在理想情况下,对于速率为R bps的广播信道,多路访问协议应该具有以下所希望的特性:


1)当仅有一个结点有数据发送时,该结点具有R bps的吞吐量;


2)当有M个结点要发送数据时,每个结点吞吐量为R/M bps。这不必要求M结点中的每一个结点总是有R/M的瞬间速率,而是每个结点在一些适当定义的时间间隔内应该有R/M的平均传输速率。


3)协议是分散的;这就是说不会因某主结点故障而使整个系统崩溃。


4)协议是简单的,使实现不昂贵。


5.3.1信道划分协议


我们前面在1.3节讨论过,时分多路复用(TDM)和频分多路复用(FDM)是两种能够用于在所有共享信道结点之间划分广播信道带宽的技术。举例来说,假设一个支持N个结点的信道且信道的传输速率为R bps。TDM将时间划分为时间帧( time frame),并进一步划分每个时间帧为N个时隙(slot)。 (不应当把TDM时间帧与在发送和接收适配器之间交换的链路层数据单元相混淆,后者也被称为帧。为了减少混乱,在本小节中我们将链路层交换的数据单元称为分组。)然后把每个时隙分配给N个结点中的一个。无论何时某个结点在有分组要发送的时候,它在循环的TDM帧中指派给它的时隙内传输分组比特。通常,选择的时隙长度应使一个时隙内能够传输单个分组。图5-9表示一个简单的4个结点的TDM例子。再回到我们的鸡尾酒会类比中,一个采用TDM规则的鸡尾酒会将允许每个聚会客人在固定的时间段发言,然后再允许另一个聚会客人发言同样时长,以此类推。一旦每个人都有了说话机会,将不断重复着这种模式。


《计算机网络:自顶向下方法》第五章 续1


TDM是有吸引力的,因为它消除了碰撞而且非常公平:每个结点在每个帧时间内得到了专用的传输速率R/N bps。然而它有两个主要缺陷。首先,结点被限制于R/N bps的平均速率,即使当它是唯一有分组要发送的结点时。其次,结点必须总是等待它在传输序列中的轮次,即我们再次看到,即使它是唯一一个有帧要发送的结点。想象一下某聚会客人是唯 一“个有话要说的人的情形 (并且想象一下这种十分罕见的情况,即酒会上所有的人都想听某一个人说话)。显然,一种多路访问协议用于这个特殊聚会时,TDM是一种 很糟的选择。


TDM在时间上共享广播信道,而FDM将Rbps信道划分为不同的频段(每个频段具有R/N带宽),并把每个频率分配给N个结点中的一个。因此FDM在单个较大的R bps信道中创建了N个较小的R/N bps信道。FDM也有TDM同样的优点和缺点。它避免了碰撞,在N个结点之间公平地划分了带宽。然而,FDM也有TDM所具有的主要缺点,也就是限制一个结点只能使用R/N的带宽,即使当它是唯一一个有分组要发送的结点时。


第三种信道划分协议是码分多址( Code Division Multiple Access, CDMA)。TDM和FDM分别为结点分配时隙和频率,而CDMA对每个结点分配种不同的编码。 然后每个结点用它唯一的编码来对它 发送的数据进行编码。如果精心选择这些编码,CDMA网络具有一种奇妙的特性,即不同的结点能够同时传输,并且它们各自相应的接收方仍能正确接收发送方编码的数据比特(假设接收方知道发送方的编码),而不在乎其他结点的干扰传输。CDMA已经在军用系统中使用了一段时间(由于它的抗干扰特性),目前已经广泛地用于民用,尤其是蜂窝电话中。因为CDMA的使用与无线信道紧密相关,所以我们将把有关CDMA技术细节的讨论留到第6章。此时,我们知道CDMA编码类似于TDM中的时隙和FDM中的频率,能分配给多路访问信道的用户就可以了。


5.3.2随机接入协议


第二大类多访问协议是随机接人协议。在随机接人协议中,一个传输结点总是以信道的全部速率(即Rbps)进行发送。当有碰撞时,涉及碰撞的每个结点反复地重发它的帧(也就是分组),到该帧无碰撞地通过为止。但是当一个结点经历一次碰撞时, 它不必立刻重发该帧。相反,它在重发该帧之前等待一个随机时延。涉及碰撞的每个结点独立地选择随机时延。因为该随机时延是独立地选择的,所以下述现象是有可能的:这些结点之一所选择的时延充分小于其他碰撞结点的时延,并因此能够无碰撞地将它的帧在信道中发出。


文献中描述的随机接人协议即使没有上百种也有几十种[ Rom 1990; Bertsekas1991]。在本节中,我们将描述一些最常用的随机接入协议,即ALOHA协议[ Abramson1970; Abramson 1985; Abramson 2009]和载波侦听多路访问(CSMA)协议[ Kleinrock1975b]。以太网[ Metcalfe 1976]是一种流行并广泛部署的CSMA协议。


1.时隙ALOHA


我们以最简单的随机接人协议之一——时隙ALOHA协议,开始我们对随机接人协议的学习。在对时隙ALOHA的描述中,我们做下列假设:


●所有帧由L比特组成。


●时间被划分成长度为L/R秒的时隙(这就是说,一个时隙等于传输一帧的时间)。


●结点只在时隙起点开始传输帧。


●结点是同步的,每个结点都知道时隙何时开始。


●如果在一个时隙中有两个或者更多个帧碰撞,则所有结点在该时隙结東之前检测到该碰撞事件。


令p是一个概率,即一个在0和1之间的数。在每个结点中,时隙ALOHA的操作是简单的:


●当结点有一个新帧要发送时,它等到下一个时隙开始并在该时隙传输整个帧。


●如果没有碰撞,该结点成功地传输它的帧,从而不需要考虑重传该帧。( 如果该结点有新帧,它能够为传输准备一个新帧。)


●如果有碰撞, 该结点在时隙结束之前检测到这次碰撞。该结点以概率p 在后续的每个时隙中重传它的帧,直到该帧被无碰撞地传输出去。


我们说以概率p重传,是指某结点有效地投掷一个有偏倚的硬币:硬币正面事件对应着重传,而重传出现的概率为p。硬币反面事件对应着“ 跳过这个时隙,在下个时隙再掷硬币”;这个事件以概率(1-p)出现。所有涉及碰撞的结点独立地投掷它们的硬币。


时隙ALOHA看起来有很多优点。与信道划分不同,当某结点是唯一活跃的结点时(一个结点如果有帧要发送就认为它是活跃的),时隙ALOHA允许该结点以全速R连续传输。时隙ALOHA也是高度分散的,因为每个结点检测碰撞并独立地决定什么时候重传。(然而,时隙AL0OHA的确需要在结点中对时隙同步;我们很快将讨论ALOHA协议的一个不分时隙的版本以及CSMA协议,这两种协议都不需要这种同步。)时隙ALOHA也是一个极为简单的协议。


对当只有一个活跃结点时, 时隙ALOHA工作出色,但是当有多个活跃结点时效率又将如何呢?这里有两个可能要考虑的效率问题。首先,如在图5-10中所示,当有多个活跃结点时,一部分时隙将有碰撞,因此将被“浪费”掉了。第二个考虑是,时隙的另-部分将是空闲的,因为所有活跃结点由于概率传输策略会节制传输。唯一“ 未浪费的"时隙是那些刚好有一个结点传输的时隙。刚好有一个结点传输的时隙称为一个成功时隙(sucessfulslot)。时隙多路访问协议的效率( fficiency)定义为:当有大量的活跃结点且每个结点总有大量的帧要发送时,长期运行中成功时隙的份额。注意到如果不使用某种形式的访问控制,而且每个结点都在每次碰撞之后立即重传,这个效率将为零。时隙ALOHA显然增加了它的效率,使之大于零,但是效率增加了多少呢?


《计算机网络:自顶向下方法》第五章 续1


现在我们继续概要讨论时隙ALOHA最大效率的推导过程。为了保持该推导简单,我们对协议做了一点修改,假设每个结点试图在每个时隙以概率p传输一帧。( 这就是说,我们假设每个结点总有帧要发送,而且结点对新帧和已经经历一次碰撞的帧都以概率p传输。)假设有N个结点。则一个给定时隙是成功时隙的概率为结点之一传输而余下的IN-1个结点不传输的概率。一个给定结点传输的概率是p;剩余结点不传输的概率是(1-p)N-1因此,一个给定结点成功传送的概率是p(1-p)N-1。因为有N个结点,任意一个结点成功传送的概率是Np(1-p)N-1


因此,当有N个活跃结点时,时隙ALOHA的效率是Np(1-p)N-1。为了获得N个活跃结点的最大效率,我们必须求出使这个表达式最大化的p*。(对这个推导的一个大体描述参见课后习题。)而且对于大量活跃结点,为了获得最大效率,当N趋于无穷时,我们取Np*(1-p*)N-1的极限。(同样参见课后习题。)在完成这些计算之后,我们会发现这个协议的最大效率为1/e=0.37。这就是说,当有大量结点有很多帧要传输时,则(最多)仅有37%的时隙做有用的工作。因此该信道有效传输速率不是R bps,而仅为0.37R bps!相似的分析还表明37%的时隙是空闲的,26%的时隙有碰撞。试想一个整脚的网络管理员购买了一个100Mbps的时隙ALOHA系统,希望能够使用网络在大量的用户之间以总计速率如80Mbps来传输数据。尽管这个信道能够以信道的全速100Mbps传输-个给定的帧,但从长时间范围看,该信道的成功吞吐量将小于37Mbps。


相关内容

文章评论

表情

共 0 条评论,查看全部
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~