【教学课件】第四章原则的运用.ppt

《【教学课件】第四章原则的运用.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第四章原则的运用.ppt（107页珍藏版）》请在三一办公上搜索。

1、第四章 原则的运用,4.1 应用设备通道的缓冲区验证,应用设备通道（Application Device Channels）允许应用程序直接读写网络适配器的存储区域来进行网络收发。需要一种隔离应用程序的保护机制：内核为每个应用程序分配一组用于网络收发的内存页，并用这组内存页设置网络适配器。网络适配器必须保证每个应用程序只能从分配给它的内存页中读写。,问题,功能需求：当应用程序P发出读写请求时，适配器必须验证请求中指定的页属于P的合法页集合。朴素的解决方案：将合法页的页号组织在一个线性表中，适配器顺序检查。验证的代价为O(n)，n为合法页的数量。问题：如果n很大，如何加速验证的过程？,分析,运用

2、P15，设计更好的数据结构：哈希表：平均查找时间O(1)，但冲突概率小的哈希函数计算复杂度高，最差性能不能保证。二分查找：可以提供logN的最坏查找时间，但当N较大时开销也比较大（要求排序）。,分析,运用P15，设计更好的数据结构：哈希表：平均查找时间O(1)，但冲突概率小的哈希函数计算复杂度高，最差性能不能保证。二分查找：可以提供logN的最坏查找时间，但当N较大时开销也比较大（要求排序）。采用系统思维：令应用程序在请求中传递一个线索，帮助适配器快速找到指定的页。（P9，在模块接口中传递线索）,解决方案,适配器将不同应用的合法页号保存在不同的数组中应用在读写请求中向适配器传递一个句柄，指出指

3、定的页号在数组中的索引适配器使用该句柄快速查找并验证页号最坏情况性能：一次数组查找，一次比较操作通过传递线索改进了最坏情况下的性能,4.2 ATM流量控制调度器,ATM是一种面向连接的网络：通信前先建立虚电路（VC），然后在VC上传输长度为53字节的信元（cell）ATM适配器可同时支持几百条已经建立的VC每条VC上使用流量控制限制其发送速度VC上的流量控制：VC每隔一定的时间获得一些credit，每个credit可以发送一个信元,VC状态表,问题,功能需求：从VC状态表中选择下一个要发送的VC简单的方法：调度器依次检查每个VC，寻找一个合格的如果有许多不合格的VC，顺序查找很低效问题：如何避

4、免查找不合格的VC？,分析,为避免查找不合格的VC，可将合格的VC抽出来组织在一起，供调度器查找。运用P12（增加额外的状态），增加一个线性表来维护合格的VC。如何有效维护合格的VC表是一个难点：合格VC的加入不合格VC的删除发送了一个信元的VC怎么处理（要体现公平）,解决方案,除VC状态表外，再维护一个合格VC列表。合格VC列表的维护：当一个VC在服务后变成了不活跃的（没有信元或credit为0），将其从列表中删除；否则，将其添加到列表尾部（以实现公平调度）；当一个VC从不合格变成合格，将其添加到列表尾部。,4.3 使用Dijkstra算法计算路由,从源节点开始，在每一轮迭代中，都从当前未包

5、含在最小路径树的节点中选择代价最小的节点加入树中。,问题,算法的要求：每次迭代需要一个优先级队列，迭代的次数等于网络中的节点个数N。通用的方法：通用的、性能最好的优先级队列（如堆），找到最小单元的代价为O(logN)，整个运行时间为O(NlogN)。问题：如果N很大，如何加速路由的计算？,分析,链路代价是一个小整数，域内路由适用的网络规模也不大，因此路径代价也是一个小整数。对于小规模问题能不能有特殊的数据结构呢？（P14）,分析,链路代价是一个小整数，域内路由适用的网络规模也不大，因此路径代价也是一个小整数。对于小规模问题能不能有特殊的数据结构呢？（P14）对于小整数来说，桶排序是比较有效的，

6、因此，能不能构造一个基于桶排序的优先级队列呢？,解决方案,构造一个基于桶排序的优先级队列。假定最大的链路代价为MaxLinkCost，网络直径为Diam，用一个长度为Diam*MaxLinkCost的数组C存放0(Diam*MaxLinkCost-1)所有可能的代价。如果节点X的当前代价为c，将X存放在数组元素Cc指向的列表中。每当节点X的代价从c变为c，将节点X从Cc指向的列表中删除，并移入Cc指向的列表。,基于桶排序的优先级队列,解决方案（续）,查找最小代价节点：初始化一个指针CurrentMin为0，它对应源节点S的代价。每当希望寻找下一个最小代价节点时，CurrentMin加1，直至到

7、达一个非空元素，将该元素所指列表中的所有节点加入最小路径树。算法复杂度：O(N+Diam*MaxLinkCost)，远低于O(NlogN)。,思考,在图示的例子中，如何在添加了节点C之后使算法终止，而不是一直扫描到数组结束？如何快速地将一个节点从一个列表中删除，然后加入到另一个列表？,4.4 使用网桥硬件的以太网监视器,将网桥改造成以太网流量监视器，统计每一对活跃节点A与B之间的流量PA,B。每个包的统计工作要求在64微秒内完成。瓶颈是查找与A、B两个MAC地址相关联的PA,B。网桥有一个查找引擎，可快速查找与一个MAC地址相关联的状态：查找引擎用lookup(X,D)调用，X为48位的关键字

8、，D为要查找的数据库，返回与X相关联的状态如果数据库不超过64000个关键字，调用延迟为1.4微秒,问题,功能需求：每当一个从A到B的数据包到来，监视器要快速找到PA,B。已有硬件：监视器的查找引擎只能查找单个MAC地址，而不是一个地址对。问题：如何使用已有硬件查找地址对？（P4c）,分析,原理上，可将PA,B组织在一个二维表中，分别用A和B的地址作为行、列索引。内存使用太多！减少内存的简单方案：先将A和B转换成较小的（小于24比特）索引 IA 和 IB，然后分别用IA和IB作为行、列索引。若当前活跃的节点对数远小于N*N（N为网络中的节点数），内存使用仍然很多！如何令内存使用量与当前活跃的节

9、点对成正比？,解决方案,基本思路：将IA和IB合并成一个新的查找关键字，查找一个一维表。方案：先使用两次查找，分别将A和B转换成小于24比特的索引 IA和IB（查找MAC-索引数据库）然后将IA和IB合并成一个新的查找关键字IAB，再查找，得到PA,B（查找IAB-PA,B 数据库）,三次查找,4.5 x-kernel中的解复用,协议解复用：根据包头中的协议域，将包交给相应的协议实体处理大多数协议基于协议头中的标识符解复用，不同协议头中的标识符长度可能不同X-kernel允许对可变长度的协议标识符解复用：系统初始化时，协议例程向x-kernel注册它所定义的协议标识符和协议之间的映射数据包到达

10、时，协议例程从包头中获得协议标识符，查询x-kernel的解复用例程，获得协议,问题,要求：解复用例程必须很快最快的查找方法是哈希表：先对标识符 K 计算哈希索引，查找哈希表，比较表项中的关键字 L 与 K（逐字节比较）。假设最常见的情形是4字节标识符，而4字节刚好是一个机器字，更有效的是字比较。问题：如何利用高效的字比较（P4c）来优化最常见的情形（P11），与此同时仍然支持任意协议？,分析,比较例程是一个可以利用的自由度：针对最常见的情形（如字比较，长字比较），使用更高效的比较例程对于其它情形，使用缺省的比较例程（逐字节比较）解复用例程如何知道对于哪个协议应使用哪个比较例程?,解决方案,系

11、统初始化时，客户协议向x-kernel传递一些信息，声明其定义的协议标识符（包括长度）和协议的对应关系利用以上信息，x-kernel为每个客户协议维护一个查找协议标识符的哈希表，给每个哈希表关联一个比较例程,运用的原则,传递线索（P9）：系统初始化时，客户向X-kernel声明协议标识符的长度这个线索通过关联的比较例程被传递给解复用例程进行某些预先计算（P2a）：系统初始化时，x-kernel为每个客户协议预计算一个哈希表,4.6 带压缩节点的trie,Trie是网络中常用的一种树形结构，每个节点是具有M个元素的数组，用于保存关键字或指向另一个节点的指针。,Trie节点的查找,若c=log2M

12、，将输入字符串划分成大小为c的块，从树根开始，第 j 个块查第 j 层的节点。如果块 j 的值等于i，检查节点中第 i 个数组元素：若是一个指向节点N的非空指针，用块j+1查找节点N；否则查找结束。如果许多节点是稀疏的，空间被极大地浪费了。,问题,压缩节点的简单方法：将数组换成一个形如（i,val）的列表，例如根节点表示为(1,ptr)；(7,key1)。缺点：必须顺序查找（i,val）列表，极大地降低查找速度。问题：如何压缩trie节点，使得查找速度的降低不超过一个小的常数因子？,分析,必须保持数组索引的有效性，即不查找列表，就能迅速知道有无要查找的元素，以及（如果有）定位到要查找的数组元素

13、,分析,必须保持数组索引的有效性，即不查找列表，就能迅速知道有无要查找的元素，以及（如果有）定位到要查找的数组元素使用一个比特串来标记数组中空元素及非空元素的位置,解决方案,压缩后的trie节点由一个比特串和一个仅包含非空元素的数组组成。,压缩节点的查找,用一个block（假设值为i）查找当前节点的过程：读入当前节点的bitmap；用 i 作为索引，检查bitmap中的第 i 位：若该位为“0”，查找结束；若该位为“1”，令 C=bitmap中前 i 位中“1”的个数，读数组中第C个元素。两次访存：一次访问bitmap，一次访问数组,运用的原则,P14（小规模问题使用高效算法）：比特串的方法仅

14、适用于长度较小的串P4a（利用局部性）：将空元素、非空元素的位置放在一个比特串中一次读入,4.7 路由器中的包过滤,接收节点通过一个包过滤器（也称分类器）表明它希望接收的数据包（流）。路由器应将数据包发送给所有提出请求的接收节点。,问题,功能需求：每个到来的数据包必须同所有的过滤器进行匹配，过滤器描述了数据包使用的源地址、源端口和目的端口。若数据包匹配了某个过滤器F，数据包必须发送给所有声明了F的接收节点。过滤器查找：如果过滤器数量很大，顺序查找很低效。问题：如何加快过滤器查找的操作？,分析,包分类是一种开销很高的操作，利用cache优化预期情形（P11a）是目前相对容易操作的方法。Cache

15、可看成是由形如的值对构成的数据库，a为索引。给定输入a，首先查找cache：若cache中存在a，返回f(a)若不存在，用某种方法计算出f(a)，插入,分析（续）,本例的包过滤问题：计算与数据包P关联的一组接收节点，P用三元组 进行刻画本例中，a=，f(a)=一组接收节点更一般地，a可能包含包头中的任何域缓存多个包头域的时空开销很大：关键字很宽，cache查找的时间开销很大空间开销大，cache命中率低,分析（续）,能否仅缓存12个唯一指示数据包 P 的包头域，而不是大量的包头域？IPv6报头中有流标签域；IPv4中没有，但有一个ToS域（可自定义）流标识是全局的还是本地的？为避免全局命名的标

16、准化过程，最好使用本地命名的标识符,解决方案,源节点为每个流分配一个本地标识符，用二元组作为查找关键字。源节点的应用程序向路由层请求一个流标识符，该应用发送的所有数据包都加上该流标识符（如放在IPv4包头的ToS域）。,解决方案（续）,应用数据包第一次到达路由器时：路由器使用包头中的多个域对所有过滤器执行一个（较慢的）线性查找，确定一组接收节点路由器将作为查找关键字，缓存与一组接收节点的映射关系后续数据包到达时:路由器用查找缓存，获得一组接收节点,4.8 避免链路状态分组的分片,在使用链路状态路由时，路由器必须定期发送一个包含所有邻居节点的链路状态分组（LSP），LSP采用扩散法传输。路由器使

17、用分组序号识别重复及过时的LSP，并只使用最新的链路状态计算最小代价路由。路由器可能有大量直接连接的主机邻居，使得LSP远远超过大多数常见链路的MTU。（假定每个端节点使用8个字节：6个字节标识端节点，2个字节表示代价）,LSP分片传输的问题,如果对LSP进行分片，存在以下问题：每一跳传输都要进行LSP的分片和重组，极大地增加了LSP的处理时间和传输时间。无法独立传输每个分片：每个LSP具有唯一的序号，如果分片使用相同的序号，则后到的分片会被丢弃；如果使用不同的序号，序号大的分片会淘汰序号小的分片。原因：同一个路由器发布的同一时刻的链路状态必须放在同一个LSP中传输。,问题,所有主机的信息必须

18、放在同一个LSP中传输吗？如果不是，能否由源路由器将主机信息分片，分别封装成独立的LSP传输，以避免传输过程中分片？（在空间上移动计算P3c）如果能够这么做，路由器如何识别哪些LSP分片属于同一个原始LSP？,解决方案,修改链路状态路由协议：允许任何一个路由器拥有多个伪路由器；端节点集合在伪路由器间划分，每个伪路由器的LSP可放入一个链路层帧中。,解决方案（续）,伪路由器概念的实现：令每个LSP携带一个7字节的ID（6字节路由器ID+1字节伪路由器ID）伪路由器ID由拥有该伪路由器的实际路由器分配具有相同路由器ID（前6个字节）的LSP被认为来自同一个路由器具有相同路由器ID和序号的LSP，其

19、包含的链路状态信息是同一时刻由同一个路由器发布的,4.9 监督流量模式,为防止网络瞬间超载，有些协议限制应用的最大突发流量。比如，在任何一个T秒间隔内，源节点发送的数据量不能超过B比特。网络应当有监督应用流量的措施，以抓住那些不遵守约定的应用。假定路由器可以通过分类器将数据包划归到一个流，路由器如何发现违约的流？,分析,简单的方法：路由器使用一个周期为T的定时器和一个计数器，在每个测量周期结束时，如果计数值超过B，路由器就检测到一个违约的流。存在问题：定时器只能监视某些时间段。观察事实：由于违约流可能在任何时刻启动，因此，无论使用多少个定时器和计数器，都不能保证抓住所有的违约流。,分析（续）,

20、能否只用一个定时器来抓住违约的流？,分析（续）,能否只用一个定时器来抓住违约的流？一定要在间隔固定的时间点上启动测量过程吗？,分析（续）,能否只用一个定时器来抓住违约的流？一定要在间隔固定的时间点上启动测量过程吗？利用自由度（P13）：测量过程不需要在固定的时间点上启动，在连续的两个测量周期之间允许有空隙。,分析（续）,能否只用一个定时器来抓住违约的流？一定要在间隔固定的时间点上启动测量过程吗？利用自由度（P13）：测量过程不需要在固定的时间点上启动，在连续的两个测量周期之间允许有空隙。如何选择测量周期之间的空隙？,分析（续）,能否只用一个定时器来抓住违约的流？一定要在间隔固定的时间点上启动测

21、量过程吗？利用自由度（P13）：测量过程不需要在固定的时间点上启动，在连续的两个测量周期之间允许有空隙。如何选择测量周期之间的空隙：考虑使用随机化方法（P3a）。,解决方案,路由器使用一个周期为 T 的定时器和一个计数器。在一个监视周期结束后，若计数器超过B，抓到一个违约流。此时，设置一个标志，为定时器设置 0,T之间的一个随机数，启动定时器，插入一段空隙。定时器超时后，清除标志和计数器，定时器复位到T，开始下一个监视周期。,4.10 找出资源使用大户,设备希望有一种简单的方法找到资源使用大户最简单的方法是使用一个堆，但如果用户数量很大，在高速网络中不可接受如果资源使用数量的数值很大，桶排序也

22、不适用 假定不要求找到精确的最大值，可以接受2倍以内的误差,问题,设计一个软件或硬件模块跟踪用户使用的资源该模块需要一个简单的方法来找到消费最多资源的用户由于普通的堆太慢，设计者愿意放宽系统要求（P3b，牺牲精度换时间）不超过2倍问题：在精度上放宽要求后，能够找到一个更有效的算法吗？,分析,放宽精度要求后，可以将资源使用差异在2倍之内的用户聚合到一个“资源使用组”，寻找最大用户变为寻找最大组（P3b）。,分析,放宽精度要求后，可以将资源使用差异在2倍之内的用户聚合到一个“资源使用组”，寻找最大用户变为寻找最大组（P3b）。用户分组：将资源使用数量在2i,2i+1-1之间的用户划为一组。,分析,

23、放宽精度要求后，可以将资源使用差异在2倍之内的用户聚合到一个“资源使用组”，寻找最大用户变为寻找最大组（P3b）。用户分组：将资源使用数量在2i,2i+1-1之间的用户划为一组。使用什么数据结构组织用户？,分析,放宽精度要求后，可以将资源使用差异在2倍之内的用户聚合到一个“资源使用组”，寻找最大用户变为寻找最大组（P3b）。用户分组：将资源使用数量在2i,2i+1-1之间的用户划为一组。使用什么数据结构组织用户：二项式桶（P14，小规模问题使用高效的数据结构），桶 i 包含资源使用在2i,2i+1-1之间的所有用户。,二项式桶排序,解决方案,使用二项式桶，桶 i 包含资源使用在2i,2i+1-

24、1之间的所有用户，每个桶包含一组未经排序的资源使用记录。使用一个比特串，每位对应一个桶，某位置1表示对应的桶非空。（使用比特串快速查找非空桶）查找资源使用大户：从比特串最右边开始，寻找第一个“1”的位置（非空桶，假设为i），返回第 i 个桶中位于表头的用户。,4.11 去除TCP的已打开连接链表,TCP连接是两个会话的端点间共享的一组状态BSD的TCP实现将已打开的连接维护在一个双向链表中，每个节点用连接的四元组进行标识：使用一个周期性定时器，每当定时时间到，扫描已打开连接链表，逐个检查是否有连接需要重传包，并执行必要的重传。每当一个TCP包到来，扫描已打开连接链表，查找TCP包所属的TCP连

25、接。（线性查找非常慢！）,X-kernel的改进,X-kernel增加了一个哈希表，用于实现快速TCP连接查找（P15），哈希冲突用链表解决。仍然保留BSD的已打开连接链表处理超时重传。,X-kernel的改进效果,经测量，X-kernel的新实现反而慢了！,X-kernel的改进效果,经测量，X-kernel的新实现反而慢了！原因：连接状态被重复存储在哈希表和线性链表，降低了数据cache的有效性。Q3：对系统某一部分显而易见的改进可能影响系统的其它部分,问题,能否保留哈希表，去除线性链表（P1，消除显而易见的浪费）？能否实现哈希表快速遍历，哪怕需要增加一些状态（P2，增加状态）？能否使用单

26、向链表，与此同时又不影响删除的速度？,分析（1）,为避免检查空的哈希表项，只需将非空的哈希表项用指针链起来，并保存指向每个冲突链的指针。为此，每个哈希表项需增加一个前向指针（P12）。,分析（2）,设计双向链表纯粹是为了方便删除节点。理想情况：当一个TCP连接终止后，立即释放其占用的资源（保存连接状态的TCB），供新建连接使用。（需要双向链表）如果不要求立即回收资源，可以只对节点做一个删除标记，等方便的时候再删除（P2b，Evaluate Lazily）。,解决方案,给每个哈希表项增加一个前向指针，指向下一个非空的哈希表项，冲突链表为单向链表。当一个TCP连接终止时，将其链表中的节点标记为未使

27、用（需要一个额外的状态比特，P12）。在下一次遍历链表的时候，如遇到一个标记为未使用的节点，删除之（修改前一个节点的指针，回收释放的节点）。,4.12 抑制确认,不少传输协议（如TCP）通过确认实现可靠传输，大多数协议采用累积确认。累积确认允许接收端可以批量确认（P2c，批处理）。,问题,在接收端实现聪明的抑制确认非常困难：接收端在发送确认前要等待多长时间？抑制确认会增加应用的响应延迟，对延迟敏感应用不利。问题：如果可以修改协议，增加什么信息可以让接收端做出明智的决定？,分析,在像FTP这样的应用中，哪个软件模块知道还有没有数据要发送？（发送端应用层）对于抑制确认，哪个软件模块想知道是否还有数

28、据要到来？（接收端传输层）考虑P9 和 P10（传递线索）。,解决方案,发送端应用传递1个比特给发送端传输层：当还有数据要发送时，该位置1。（P9）修改传输层协议，在包头中添加一个抑制比特。发送端传输层利用应用传递的信息设置抑制比特：当希望立即得到确认时，抑制比特置0，否则置1。（P10）抑制比特只是一个线索，接收端可以忽略该信息。,思考,对于TCP来说，以上方案是一个好主意吗？,思考,对于TCP来说，以上方案是一个好主意吗？激进的确认抑制可能会影响TCP的哪些方面？流量控制拥塞控制RTT估算,思考,对于TCP来说，以上方案是一个好主意吗？激进的确认抑制可能会影响TCP的哪些方面？流量控制：发

29、送方不能及时推进发送窗口，阻塞发送方拥塞控制：发送方不能及时检测到拥塞，也不能利用确认调整拥塞窗口大小RTT估算：不准确,思考,对于TCP来说，以上方案是一个好主意吗？激进的确认抑制可能会影响TCP的哪些方面？流量控制：发送方不能及时推进发送窗口，阻塞发送方拥塞控制：发送方不能及时检测到拥塞，也不能利用确认调整拥塞窗口RTT估算：不准确Q3：对系统某部分的改变是否会影响系统的其它部分？,4.13 对大数据库的增量访问,假定用户连续读一个存放在web网站的大数据库，用户只想知道自上一次读过之后变化了的内容。,问题,为数据库找到一种高效地执行增量查询的方法。令数据库记住每个用户之前读的内容是不现实

30、的。有没有一个对数据库来说负担不那么重的方法？,分析,如果数据库不存储用户上一次读过的内容，那么用户在读请求中必须传递一些与上一次读请求相关的信息（P10）。,分析,如果数据库不存储用户上一次读过的内容，那么用户在读请求中必须传递一些与上一次读请求相关的信息（P10）。什么样的简单信息可以刻画用户的上一次请求？,分析,如果数据库不存储用户上一次读过的内容，那么用户在读请求中必须传递一些与上一次读请求相关的信息（P10）。什么样的简单信息可以刻画用户的上一次请求？上一次请求的时间,分析,如果数据库不存储用户上一次读过的内容，那么用户在读请求中必须传递一些与上一次读请求相关的信息（P10）。什么样

31、的简单信息可以刻画用户的上一次请求？上一次请求的时间在数据库中增加什么状态（P12），可以根据用户传递的信息来加快增量查询？,分析,如果数据库不存储用户上一次读过的内容，那么用户在读请求中必须传递一些与上一次读请求相关的信息（P10）。什么样的简单信息可以刻画用户的上一次请求？上一次请求的时间在数据库中增加什么冗余状态（P12），可以利用用户传递的信息来加快增量查询？数据库更新历史列表,解决方案,增加一个更新历史列表，仅保存数据库发生的更新。更新记录按照时间顺序排列，越近的更新越靠近表头。读请求中包含上一次读的时间 T，查询处理程序从表头开始扫描更新历史表，找到 T 之后所有的内容更新。,4.

32、14 长标识符的二分查找,假定每个标识符的长度为 W 个字，匹配一个标识符需要 W 次比较操作。如果表中有 N 条标识符，且已按字典序排列，简单的二分查找需要Wlog2N 次比较操作。若所有标识符的前（W-）个字都相同（有共同前缀），理想情况应只比较 log2N 次，而不是Wlog2N 次。希望修改二分查找，使得比较次数为 log2N+W。,按列进行二分查找,问题,修正当前的算法，使得经过（log2N+M）次操作后得到正确的结果。算法出现错误的原因：当查找移动到下一列、并且依据二分查找法确定一个新的查找位置时，假设该位置上的标识符和所要查找的标识符具有相同的字符前缀。这个假设一般是不成立的。问

33、题：增加什么状态可以避免做出这样错误的假设？,解决方案,给每一个元素增加两个指针，将二分查找约束在正确的范围内进行。,解决方案（续）,一般地，为每个多字条目（W1W2Wn）保存一个预先计算好的保护范围，其中Wi的保护范围指出前 i 个字为（W1W2Wi）的条目的范围。如果有N条标识符，该策略需要log2N+M次查找。代价是给每个元素增加了两个16位的指针，相当于增加了一倍的内存空间。这里运用了P12（增加状态）和 P2a（预先计算）两条原则。,4.15 基于ATM的视频会议,标准的ATM允许“一对多”虚电路（VC）：源节点发送的任何数据被交换机复制，发送给每个接收者。,many-to-many

34、 VC,ATM交换机硬件很容易实现“多对多”VC：交换机将任何一个源节点发送的数据复制后发送给所有的接收节点。“多对多”VC的问题：如果两个源节点同时发送，它们的数据（带有相同的VC号）可能以任意交错的顺序到达接收节点，引起混乱。ATM标准不支持“多对多”VC。,应用,设计一个视频会议应用：每个工作站上建立一个屏幕，显示当前正在说话的人，并播放其讲话。当两人进行对话时，能看到两个人的表情。,问题,问题：如何在ATM上实现 many-to-many 的视频会议？最简单的方法是使用N2个点-点 VC。较好的方法是使用N个one-to-many VC。但ATM交换机的带宽要在N个one-to-man

35、y VC之间静态划分，限制了参会的工作站数量。还有扩放性更好的方案吗？,分析,利用交换机硬件支持many-to-many VC的能力（P4c），但需要解决每次只能一个节点发送的问题。如何协调发送者？,解决方案,协调发送者（运用系统思维）：谁的视频最应当被输出：当前说话者。如何确定当前的说话者：给每个工作站添加一个语音检测器（P5，增加硬件）。原理：如果工作站 X 上的语音检测器检测到有意义的语音活动，检测器将 X 的视频连接到C。,优化预期情形,最常见情形是两个与会者之间对话，保留上一个说话人的视频图像可以提供视觉上的连续性。为此，使用两个many-to-many VC，C和L：C 用于传输当前说话人的视频L 用于传输上一次说话人的视频,