登入帳戶　 |　訂單查詢　 |　購物車/收銀台(0)　|　在線留言板　 |　付款方式　 |　聯絡我們　 |　運費計算　 |　幫助中心　|　 加入書簽
	全部範圍 - 圖書 - 　- 中文簡體書(大陸書) - 　- 英文書（原版） - - 音碟 - 　- 音樂 - 　- 影視 - - 雜誌 - 全文 精確	會員登入 新註冊 |　新用戶登記

HOME新書上架暢銷書架好書推介特價區會員書架精選月讀2023年度TOP分類閱讀雜誌

香港／國際用戶

最新/最熱/最齊全的簡體書網

品種：超過100萬種書，正品正价，放心網購，悭钱省心

送貨：速遞 / EMS，時效：出貨後2-3日

新書推薦： 《 精致考古--山东大学实验室考古项目论文集（一） 》 售價：NT$ 1112.0 《 从天下到世界——国际法与晚清中国的主权意识 》 售價：NT$ 347.0 《 血色帝国：近代英国社会与美洲移民 》 售價：NT$ 265.0 《 海外中国研究·王羲之：六朝贵族的世界（艺术系列） 》 售價：NT$ 811.0 《 唐宋绘画史 全彩插图版 》 售價：NT$ 449.0 《 海洋、岛屿和革命：当南方遭遇帝国（文明的另一种声音） 》 售價：NT$ 485.0 《 铝合金先进成型技术 》 售價：NT$ 1214.0 《 英雄之旅：把人生活成一个好故事 》 售價：NT$ 398.0

編輯推薦： 1. 深刻剖析了互联网络僵化问题产生的原因，全面介绍了国际国内关于下一代互联网络研究的前沿技术，解决方案及关键技术；2. 全书从覆盖网络的产生背景、基本原理及应用出发，通过分析现有互联网存在的问题，以及覆盖网络的不足之处，研究了覆盖网络拓扑构建、多路径负载均衡路由、覆盖网无状态多播、以及覆盖路由与底层物理网络流量工程之间目标不一致而导致的路由冲突问题。3. 全书结构清晰，条理分明，遵循IP网络的运行规律，通过问题抽象、模型构建、算法设计与求解、理论证明、实验验证等一系列严谨的过程，其结论对于下一代互联网的规划与设计具有一定的借鉴意义。 內容簡介： 覆盖网络技术是下一代互联网、云计算数据中心网领域研究的热门技术。本书紧紧围绕互联网发展的前沿课题，介绍下一代互联网的热点问题及其解决思路。全书从覆盖网络的产生背景、基本原理及应用出发，通过分析现有互联网存在的问题，以及覆盖网络的不足之处，研究了覆盖网络拓扑构建、多路径负载均衡路由、覆盖网无状态多播，以及覆盖路由与底层物理网络流量工程之间目标不一致而导致的路由冲突问题。 本书是作者在密切跟踪该领域研究成果的基础上深入研究的结果，是一本全面论述覆盖网络弹性路由与跨层优化的著作。全书图文并茂、深入浅出，理论与实践相结合，可读性强。可作为计算机科学与技术、网络工程、物联网、信息工程等相关专业的高年级本科生和研究生的教学参考用书，也可以作为关注新一代互联网理论与实践的研究者的参考用书。 目錄： 目录 第1章绪论1 1.1覆盖网络产生的背景1 1.1.1互联网的设计缺陷1 1.1.2下一代互联网设计思路2 1.2覆盖网络的本质7 1.2.1覆盖网络体系结构7 1.2.2覆盖网络的缺陷7 1.3本书的研究内容及结构安排11第2章覆盖网络概述12 2.1覆盖网络基本概念12 2.2覆盖网络的分类13 2.3覆盖网络的应用15 2.3.1P2P网络15 2.3.2内容分发网16 2.3.3应用层多播17 2.3.4增强服务质量（QoS）19 2.3.5云计算数据中心网20 2.3.6覆盖网络在SDN中的应用22 2.4覆盖网络研究现状23覆盖网络弹性路由与跨层优化目录2.4.1覆盖网拓扑构建24 2.4.2覆盖网路由31 2.4.3覆盖网多播34 2.4.4覆盖网感知方式41 2.5本章小结42第3章基于超节点的覆盖网络拓扑构建算法43 3.1研究背景43 3.2基于超节点的覆盖网拓扑构建46 3.2.1问题的描述46 3.2.2超节点的选取47 3.2.3K最小生成树覆盖网拓扑48 3.3覆盖网一跳路由快速恢复机制51 3.4算法性能评价53 3.4.1仿真实验53 3.4.2结果分析55 3.5本章小结62第4章负载均衡的覆盖网络多路径路由机制研究63 4.1研究背景63 4.2负载均衡的一跳覆盖网多路径路由64 4.2.1网络模型64 4.2.2线性规划模型66 4.3启发式算法68 4.3.1中继节点的选择68 4.3.2多路径流量切割率71 4.4多路径覆盖网络的部署72 4.5性能评价72 4.5.1仿真实验72 4.5.2结果分析74 4.6本章小结78第5章基于包内布隆过滤器的无状态覆盖网络多播80 5.1研究背景80 5.2具有节点邻近意识的覆盖网拓扑82 5.2.1节点的网络坐标82 5.2.2TransitStub覆盖网层次拓扑83 5.3基于包内布隆过滤器的覆盖网多播87 5.3.1包内布隆过滤器88 5.3.2无状态多播机制89 5.3.3数据转发中的误判率91 5.4性能评价92 5.4.1仿真实验92 5.4.2结果分析93 5.5本章小结96第6章覆盖网络路由冲突问题98 6.1研究背景98 6.2流量工程概述98 6.2.1流量工程概念98 6.2.2流量工程分类99 6.3路由冲突问题模型103 6.3.1冲突问题模型103 6.3.2冲突问题研究现状105 6.4覆盖路由之间的交互107 6.5本章小结109第7章多覆盖网络共存环境下的混合交互110 7.1研究背景110 7.2网络模型和问题描述112 7.2.1网络模型112 7.2.2交互目标114 7.3n 1参与者非合作博弈117 7.3.1纳什均衡117 7.3.2静态最优反应算法118 7.3.3动态最优反应算法119 7.41领导者n跟随者斯塔克尔伯格纳什博弈123 7.4.1斯塔克尔伯格纳什均衡124 7.4.2斯塔克尔伯格纳什博弈求解算法125 7.5性能评价126 7.5.1仿真实验126 7.5.2结果分析128 7.6本章小结135第8章混合交互的联盟合作机制136 8.1研究背景136 8.2联盟博弈136 8.2.1联盟目标函数136 8.2.2联盟分配方案137 8.3联盟形式139 8.4性能评价141 8.4.1仿真环境141 8.4.2仿真结果141 8.5本章小结146 参考文献147 內容試閱： 前言 随着互联网的进一步普及，基于网络的新型应用不断涌现，如视频点播、视频会议、远程教育、网络多媒体交互协作平台、在线网络游戏等，这些新型应用要求通信网络提供高可靠性、高带宽、低时延的服务。然而，在互联网规模日益扩大的同时，Internet本身的僵化现象越来越明显。例如，链路故障恢复时间长以及路由膨胀等问题，严重影响端到端的传输性能；IP多播的部署难和可扩展性差等问题，限制了日益增长的一对多和多对多数据传输；缺乏对QoS的有效保障，无法满足某些业务的需求。此外，互联网的基础服务提供商（ISP）之间存在复杂的商业利益关系，这使得对现有技术的重大调整变得异常困难。覆盖网络（Overlay Network）的出现为现有互联网的改造和升级提供了新的思路。覆盖网络是建立在已有网络上的一种逻辑网络，利用隧道或封装机制将覆盖节点（Overlay Nodes）互连起来，形成覆盖网络拓扑来完成数据传输，而无须改变原有的互联网基础设施。覆盖网络除了能完成类似P2P（PeertoPeer）、CDN（Content Delivery Network）这样的内容分发与共享服务之外，随着终端节点性能（CPU带宽和存储能力）的不断提升，也可以提供路由和组播这些原本只能由路由器完成的基础性服务。另一方面，随着服务器虚拟化和存储虚拟化技术的日臻完善，网络虚拟化技术成为国内外科学界研究的热点。覆盖网络技术作为网络虚拟化的一种有效的解决方案，为下一代互联网、云计算和数据中心网的规划设计提供了一种可行的思路。虽然覆盖网络在提高路由质量、保障QoS、提供组播服务等方面能够对现有的互联网络基础设施起到很好的补充作用，但在构建覆盖网络时如何感知基础设施结构，达到上下层优势互补，还有许多关键问题亟待解决。例如，如何考虑物理网络中部分关键节点对覆盖网络拓扑构造、路由和数据分发的影响；如何解决两条或多条覆盖链路共享物理链路，造成性能下降的问题；如何建立具有节点邻近意识的覆盖网络，减少端到端的时延；在多播通信中如何降低节点状态的维护代价等。其次，覆盖路由是通过覆盖网络进行的路由模覆盖网络弹性路由与跨层优化前言式，是根据用户的特定需求在应用层上计算路由，是覆盖网络研究的关键技术，受到了国内外学者的广泛关注。在现实中，为了提升服务的性能，服务提供商（SP）在互联网上部署了大量支持各种类型服务的覆盖网络。然而，覆盖路由的本质是自私路由，它根据具体服务的需求进行路由，与物理网络流量工程的路由目标通常并不一致，因此常常会发生冲突；同时，共存的覆盖网络之间也可能会因为竞争网络资源而出现冲突。这种冲突所引起的路由交互问题，严重影响了网络的效率和稳定性。本书针对上述问题，对覆盖网络拓扑构建、多路径路由、应用层多播、上下层路由冲突等覆盖网络关键问题进行了深入细致的研究。在研究过程中，遵循IP网络的运行规律，通过问题抽象、模型构建、算法设计与求解、理论证明、实验验证等一系列严谨的过程，其结论对于下一代互联网的规划与设计具有一定的借鉴意义。全书共分为8章，其中1～6章由田生文编写，第7章和第8章由龚军编写。在撰写过程中，参考且引用了国内外有关覆盖网络、Internet网络等方面的大量文献，在此，向相关作者表示衷心的感谢。本书的出版得到国家自然科学基金（No. 61170161）的资助。另外，本书的编写还得到鲁东大学邹海林教授、王刚教授、杨洪勇教授；北京邮电大学廖建新教授、王晶教授、王敬宇老师、戚琦老师的大力支持，在此对他们的支持和帮助表示衷心的感谢。特别感谢清华大学出版社，感谢责任编辑及其他参与此书编辑和出版的各位老师，为本书的顺利出版付出的辛勤劳动。由于作者水平有限，书中不足之处在所难免，恳请广大读者和同行批评指正。作者邮箱： sw_tian@yeah.net。 编者2017年1月 第5章基于包内布隆过滤器的无状态覆盖网络多播5.1研 究 背 景随着互联网的进一步普及，面向组通信的新型多媒体应用不断涌现，例如，视频点播、电视电话会议、证券交易、在线游戏等，一对多或多对多的多播通信已引起了科研领域以及产业界的极大关注。然而，由于IP网络的层次化布局以及路由协议的特性，现有的IP多播仅在域内得到应用，而域间的部署受到极大的限制。覆盖网多播弥补了这一缺陷\[32\]\[36\]，可以满足新型多播应用的需求。覆盖网多播在应用层实现多播数据的传输，包括两个部分： 覆盖网多播拓扑和运行在该拓扑上的多播数据转发算法。覆盖网多播中的节点由参与多播转发的终端主机或端系统服务器组成；节点间的链路是一种逻辑链路，对应一条物理路径，由一条或多条物理链路构成。多播转发算法建立在多播拓扑之上，通常形成一棵多播转发树，如图51a所示，但在物理网络上是通过单播的方式实现数据的转发，如图51b所示。值得注意的是，在覆盖网多播中，数据的转发是由终端主机或端系统服务器完成的，而不是路由器。图51覆盖网多播示意图覆盖网络弹性路由与跨层优化第5章基于包内布隆过滤器的无状态覆盖网络多播根据多播数据源数目的不同，覆盖网多播可以分为单源多播和多源多播两种。单源多播常采用树状结构拓扑，而多源多播则采用网状结构拓扑。树状结构\[98\]是以源节点为根建立最短路径多播转发树，有高效的转发效率，但单点故障使其备受争议；网状结构\[110\]则需要在其网络拓扑上建立最小生成树，提高了转发的可靠性，但这一优点是以转发大量冗余信息维护网状拓扑为代价的。因此，在已有研究中，无论是树状还是网状结构拓扑，都需要维护多播转发树，即维护转发节点在多播转发树中的状态，这对于带宽有限的终端节点来说，其代价是可想而知的。另一方面，在覆盖网多播中，时延是影响多播转发性能的一个重要因素。与IP多播相比较，由于缺乏物理拓扑意识，覆盖网多播有较长的端到端的时延。针对这个问题，已有的研究通过建立最优化模型，使得覆盖网的平均时延最小或最大时延最小\[124\]\[125\]，然而，这需要探测或评估所有节点对之间的时延，其可扩展性受到一定的影响。FPCast\[151\]提出了一种具有节点邻近意识的覆盖网多源多播算法，但没有解决节点状态维护代价较高的问题。近年来，包内布隆过滤器技术\[152\]也被用在IP多播研究中。LIPSIN\[153\]提出了服务于PulishSubscribe模式的IP多播算法，是第一个将包内布隆过滤器应用于IP多播的研究。为了解决可能出现的环状转发问题，LIPSIN为每个参与多播转发的路由器上的每条链路设置d个链路ID标识；通过与这d个标识进行匹配，决定是否对数据包进行转发。该机制在一定程度上减少了路由环的数量，但给路由器带来了额外的状态维护代价，增加了处理时延。SwitchediBF\[154\]将IP多播转发树分割为多棵子树，并为每棵子树建立一个包内布隆过滤器，这样可以提高IP多播的可扩展性，但如何合理分割多播树是一个开放性问题。BloomCast\[155\]应用一种位排列（Bit Permutation）方法构造包内布隆过滤器，目的是减少IP多播中的转发异常，但其可扩展性受到一定限制。DOM\[156\]将IP多播中的目的IP地址编码并封装在一个包内布隆过滤器内，旨在解决IP多播中的转发环（Forwarding Loop）问题。以上这些包内布隆过滤器的应用都集中在IP多播中，需要改变路由器的结构和路由算法，使其支持对过滤器的相关操作。本章提出了基于包内布隆过滤器（inpacket Bloom Filter，iBF）的无状态覆盖网多播算法。通过考虑节点间的邻近关系，以及节点的异质性，构造了具有节点邻近意识的层次化覆盖网多播拓扑；在此基础上，设计了无状态覆盖网多播算法。该算法采用逆向路径转发方式，对参与多播转发的节点和接口进行编码且映射到两个不同的布隆过滤器（节点布隆过滤器和接口布隆过滤器）。在多播数据转发的过程中，将这两个布隆过滤器的信息封装到数据包的首部，与数据部分一起被路由。算法的优点在于，将多播转发树的状态信息携带到数据包内，减少了维护多播转发树的代价\[150\]。此外，在多播转发过程中，通过对节点布隆过滤器和接口布隆过滤器进行两阶段解码，降低了错误转发率，提高多播转发效率。另一方面，采用固定长度的包内布隆过滤器，可以进行线速（Linespeed）转发操作，减少了转发的处理时延。仿真结果表明，基于包内布隆过滤器的无状态覆盖网多播算法提高了转发效率，增强了可扩展性。本章提出的基于包内布隆过滤器的无状态覆盖网多播算法充分考虑了转发时延和状态维护代价两个方面的因素。通过将多播转发树的信息编码成布隆过滤器，且封装在数据包的首部，降低了维护多播转发状态的代价；采用网络节点坐标的方法构建层次化覆盖网多播拓扑，使得多播结构具有一定的物理拓扑意识，且提高了可扩展性。同时，与现有的用于IP多播的包内布隆过滤器相比，本章提出的覆盖网多播算法在应用层实现，不需要对互联网基础设施做任何修改。5.2具有节点邻近意识的覆盖网拓扑构建覆盖网拓扑是设计与运行覆盖网多播算法的基础。为了减少多播数据转发的端到端时延，这里构建了具有节点邻近意识的覆盖网拓扑。首先为覆盖节点设置网络坐标（Internet Coordinate），使得节点间的几何距离尽可能体现该对节点间数据传输的时延，即时延长，则几何距离也大；时延短，相应的几何距离也小。其次，由于节点的异质性（这里主要考虑节点的处理能力和参与多播的周期），将覆盖网络节点划分为TransitPeers和StubPeers两种类型，并构造TransitStub层次化覆盖网拓扑，提高可扩展性。5.2.1节点的网络坐标这里应用PIC（Practical Internet Coordinates）算法\[157\]计算覆盖网节点的网络坐标。PIC算法是一种通过计算节点坐标估计互联网中节点间距离的方法。在此，用m代表节点坐标的维数，且定义m=2，即将每一个覆盖网节点映射到一个二维欧式空间中的一个点，使得任何两点间的几何距离能够反映相应覆盖节点间的测量距离（即时延）。众所周知，节点的坐标值是相对于某个或某些坐标点设置的。根据PIC算法，至少需要m 1个节点构成的参考点（landmarks）集合L。这里采取随机选取参考点的方法，即当一个新节点n加入覆盖网络时，随机选取3个已具有网络坐标的节点作为节点n的参考点，应用单纯形下山算法（Simplex Downhill）\[158\]计算相应的网络坐标，使得下列误差函数达到最小： |L|i=1dmi-dpidmi251其中，dmi是节点n与L中第i个节点间的测量距离，是通过ping协议得到的两点间端到端的时延，也可以用物理链路的跳数近似代替。dpi是节点n与L中第i个节点间的预测距离，是通过两节点的网络坐标计算而得的几何距离。单纯形下山算法又称为NelderMead方法，是用于求解多元函数最小值的常用方法。该算法借助简单几何体（单纯形）获得函数的最小值。m维单纯形必须有m 1个初始点，形成初始单纯形，二维单纯形是三角形。该方法通过基本操作（反射、扩展和压缩）形成新的单纯形。经多次迭代，最后得到最小值。应用PIC算法计算所有覆盖网节点的网络坐标，并将其映射到二维几何平面中。有了节点的网络坐标，就可以计算节点间的几何距离，为下一步层次化拓扑构建做好准备。5.2.2TransitStub覆盖网层次拓扑1. TransitPeers节点的选取由于覆盖网节点存在一定的异质性，即节点的处理能力不同，且不同的节点参与多播组的周期也存在一定的差异，本文将覆盖网节点划分为TransitPeers和StubPeers两类，并建立两层覆盖网多播拓扑： TransitPeers层和StubPeers层，如图52所示。为了减少覆盖节点动态性（节点频繁地加入和退出）对覆盖网多播的影响，这里选择那些处理能力强且相对稳定的覆盖节点作为TransitPeers节点，构建低时延高带宽的覆盖多播骨干网，即TransitPeers层；而其他的普通节点（被定义为StubPeers节点）则连接到最近的TransitPeers节点，形成StubPeers层。TransitPeers节点除完成自己的数据分发任务外，还负责为其他TransitPeers节点以及StubPeers节点提供中继或数据转发服务，而StubPeers节点仅分发自己的多播数据，不负责为其他节点提供服务。图52TransitPeersStubPeers覆盖网拓扑当一个新节点加入覆盖多播网络时，如果该节点满足下列条件，则该节点属于TransitPeers节点，否则该节点是StubPeers节点。（1） 丰富的带宽： 要求TransitPeer节点有充足的带宽为其他TransitPeers节点和下层的StubPeers节点提供数据传输与转发服务。（2） 高可靠性： 要求TransitPeer节点性能稳定可靠，服务周期长，即不会频繁地加入或离开覆盖多播网络。2. TransitStub层次拓扑我们应用Symm Yao \[159\]方法建立TransitPeers之间的覆盖网链路，形成TransitPeers层。Symm Yao是Yaograph\[160\]的一种改进方法。Yaograph是以几何角度和距离同时作约束条件的邻近图结构。它以每个节点u为中心，在几何平面中引出k条射线将平面等分为k个扇形域，在每个扇形域内如果有其他点，则选择距离u最近的点v，使有向边u,vYaograph。文献\[161\]证明k6时，Yaograph具有最小生成树的特性，即由Yaograph构成的网络总代价最小。在Yaograph中保留那些对称的有向边，即u,v和v,u，去掉点对间的单向边形成的图就是Symm Yao。文献\[159\]证明，Symm YaoYao graph。这里，首先建立由所有TransitPeers节点构成的Yaograph。我们以每个TransitPeer节点为中心，将它所在的二维平面划分为等角度=3的6个扇形域；在每个扇形域中建立从该TransitPeer节点到距离最近的TransitPeer节点间的有向边。这里的距离最近指的是根据节点的网络坐标计算的几何距离最小。然后，保留节点对间对称的有向边，去掉节点对间的单向边，并且将每对节点间两条方向相反的有向边合并形成一条无向边，构成TransPeers层结构，如图53所示。TransPeers层可以为覆盖网多播通信提供低时延、高带宽的服务。同时，TransPeers层的构造过程是分布式的，维护代价并不高。图53TransitPeers层覆盖网拓扑接下来，在StubPeers层建立StubPeer节点与TransitPeer节点之间的连接关系。每个StubPeer节点被连接到与它几何距离最近的一个TransitPeer节点。对于每个StubPeer节点，需要计算它到每个TransitPeer节点的几何距离，计算复杂度为ONTNS，其中，NT和NS分别表示TransitPeer节点数和StubPeer节点数。为了降低计算复杂度，这里应用简单的聚类算法（如kmenas），根据节点间的几何距离，将所有TransitPeer节点聚成几个簇。根据StubPeer节点与每个簇中心的距离，首先确定每个StubPeer节点所属的簇；然后在该簇中找到距离最近的TransitPeer节点，建立覆盖链路，称该TransitPeer节点为这个StubPeer的父节点，如图54所示。图54StubPeer与相应的TransitPeer节点相连至此，TransitStub层次化覆盖网多播拓扑已形成，其中的链路权重为两点间的几何距离。3. 拓扑维护为了维护覆盖网拓扑的一致性，每个节点周期性地向相邻节点发送一种KeepAlive报文，保持双方处于活动状态。当一个新节点加入网络，或已有节点离开网络时，覆盖网络需要做相应更新。1） 新节点加入当一个新节点n申请加入网络，首先根据5.2.1节判断该节点是TransitPeer节点还是StubPeer节点。如果节点n是TransitPeer节点，则加入过程分为4个步骤。（1 以节点n为中心，将所在平面等分为6个扇形域；在每个扇形域依据Symm Yao算法连接最近的一个TransitPeer节点。（2 节点n向相邻节点发送KeepAlive 报文，启动局部拓扑维护算法Local_Update，重构TransitPeers层。（3 计算节点n与各簇中心点的距离，确定节点n所属的簇。（4 在节点n所属的簇内，启动StubPeerTransitPeer更新算法，计算每个StubPeer节点与节点n间的几何距离，决定是否更改节点n作为其父节点。如果节点n是StubPeer节点，首先计算节点n与各簇中心的距离，确定节点n所属的簇；在该簇内计算节点n与该簇内所有TransitPeer节点间的距离，选择距离最小的TransitPeer节点作为节点n的父节点，并在两者间建立覆盖链路。2） 已有节点离开已有节点n离开网络，可以分为主动离开和出现故障突然离开两种情况。（1 主动离开： 如果节点n是StubPeer节点，则只需要向其父节点发送离开消息，通知该父节点断开连接即可。如果节点n是TransitPeer节点，则需要主动向相邻的TransitPeer节点发送离开消息，启动局部拓扑维护算法Local_Update，重构TransitPeers层。如果节点n是TransitPeer节点且与某一个或几个StubPeer相连，则主动向这些StubPeer节点发送离开消息，在节点n所在的簇内重新为这些StubPeer节点选择父节点。（2 出现故障突然离开： 假设节点是一个与故障节点n相连接的节点。当节点m向节点n发送KeepAlive 报文且在规定时间内未收到应答报文，则向节点n连续发送3个KeepAlive报文，如果在规定时间内仍未收到应答报文，则认为对方出现故障，于是节点m立即断开与节点n的连接。如果节点m是一个TransitPeer节点，则启动局部拓扑维护算法Local_Update，重构TransitPeers层；如果节点m是一个StubPeer节点，则故障节点n是其父节点，此时需要在节点m所属簇内重新计算距离，重新确定父节点。由于TransitPeer节点服务周期长且处理能力较强，所以覆盖拓扑中TransitPeer层的稳定性较强，维护代价较低。5.3基于包内布隆过滤器的覆盖网多播覆盖网多播拓扑构建好后，需要设计在此拓扑上运行的多播算法。本文提出了基于包内布隆过滤器的覆盖网多播算法，可以实现节点间无状态多播数据传输，降低了节点的状态维护代价。5.3.1包内布隆过滤器布隆过滤器Bloom Filter,BF是由Burton Howard Bloom于1970年提出，它是一种空间利用率较高的概率型数据结构，是由一个二进制向量和一系列Hash函数组成，用于判断一个元素是否在集合中。它的优点是存储空间小，查询速度快，但存在一定的误识别率，即假阳性（False Positive），常被称为误判率。具体地讲，一个BF由一个m位的二进制数组和k个相互独立的Hash函数构成，用来表达具有n个元素的集合S={x1,x2,,xn}。初始时数组的m位全都置为0，Hash函数的值域是\[0,m-1\]。布隆过滤器涉及两种基本二进制位操作。（1） 通过OR操作加入元素到数组构造一个BF。（2 通过AND操作查寻某元素是否在集合中。当加入一个元素xS到数组时，将k个不同的Hash函数值hix1ik所对应的数组中的二进制位全部置为1。如果查询某元素y是否在集合S中，判断yS，当且仅当k个二进制位hiy全部为1。如图55所示为布隆过滤器的一个实例，集合中3个元素x、y和z，应用k=3个不同的Hash函数，每个元素经Hash后映射到数组中的3个不同的位置。判断元素w是否属于集合，由于Hash后对应数组中的值不全为1，表明w不属于该集合。图55Bloom Filter实例包内布隆过滤器（inpacket Bloom Filter，iBF）是布隆过滤器的一种特殊情形。将构建好的布隆过滤器封装到数据包的首部，与数据一起在网络中传输，在经过的每一个节点针对过滤器进行元素的查询，就形成了包内布隆过滤器。这里应用iBF，将覆盖网多播转发树的信息封装在包内，降低了状态维护的代价，提高了多播效率。5.3.2无状态多播机制1. 构造包内布隆过滤器在本章建议的算法中，为每个覆盖节点以及该节点的每个覆盖链路接口定义一个唯一的标识符，且应用预先定义的k个Hash函数，将每个覆盖节点的标识符和相应的各个覆盖链路接口标识符分别映射到不同的m位数组中，分别表示为Node ID和Interface ID。每个Node ID和Interface ID中有k位为1，其他m-k位为0。本书应用逆向路径转发的方法构造包内布隆过滤器。该布隆过滤器包括节点布隆过滤器NodeBF和接口布隆过滤器InterfaceBF。当一个节点准备发送多播数据时，首先向覆盖网络广播一个通知消息，消息中包含这一多播数据的描述信息。收到广播消息且准备加入此多播组的节点被称为接收节点，它采用单播通信的方式向源节点发送一个应答消息。单播路径是覆盖网络中接收节点到源节点的最短路径，由覆盖路由算法决定。在应答报文格式中，应答数据包的首部封装两个布隆过滤器： NodeBF和InterfaceBF。初始时NodeBF和InterfaceBF中m位全为0。在发送应答报文过程中，沿途每经过一个覆盖节点（包括源节点和接收节点），将该节点的Node ID和入接口的Interface ID分别与报文首部中的NodeBF和InterfaceBF进行OR操作，并用所得结果刷新首部中的NodeBF和InterfaceBF。最后，源节点收到来自所有接收节点的应答报文，拆封各报文首部，将得到的所有NodeBF和InterfaceBF进行OR操作，得到最终的NodeBF和InterfaceBF，并封装到多播数据包的首部，形成了包内布隆过滤器，称为之NI_iBF，如图56所示（这里假定m=8，k=2）。NIiBF携带的是多播分发树的信息。图56NIiBF布隆过滤器

書城介紹　 |　合作申請　|　索要書目　 |　新手入門　|　聯絡方式　 |　幫助中心　|　找書說明　 |　送貨方式　|　付款方式	香港用户　 |　台灣用户　|　海外用户
megBook.com.tw
Copyright (C) 2013 - 2024 （香港）大書城有限公司　All Rights Reserved.