自治和分布式寻址与路由体系结构的计算机博士论文

订单号论文呈现给L’UNIVERSITÉ DE数学与计算机科学博士学院[美]西里尔·卡萨涅著要获得的等级医生专业：计算机科学用于互联网中灵活通信的自治和分布式寻址和路由体系结构支持日期：2012年11月12日根据报告员的意见：PascalLorenz教授菲利普·鲁斯。... ... ... ... ... ... ...高级讲师-HDR在审查委员会面前，塞尔日·肖梅特。... ... ... ... ...教授。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...评审团主席Emmanuelle Anceaume CRCNRS审查员菲利普·奥韦扎尔斯基。. ... ... ..................................................CR CNRS-HDR审查员达米安·马戈尼。... ... ... ... ... ...教授。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...论文主任2012谢谢你C’est 啊!谢谢你。首先，我要感谢菲利普·鲁斯和帕斯卡尔·洛伦兹接受了我的报告员这一艰巨任务。还要感谢Philippe Owezarski和Emmanuelle An- ceaume同意感谢Serge Chaumette再次感谢Serge，他从硕士学位开始就一直支持我，在然后我要感谢我的论文导师达米安·马戈尼，没有他，我就这篇论文是它显然与这一成功有关。我感谢他这三年，也感谢他三年前的选择。在这三年我不能不说几句关于我的工作环境和我在CVT的同事的话来继续这些感谢我错过了资格...关于这些成员，Telesphore订阅者每年有几个月的时间，然后是Mikey、Bibi、Dub、Joe、Jérémie、Hugox和Kaze，他们每天都在LaBRI的这个飞地工作这个地方，有时是一个避风港，有时是一个地狱，催化尽管一切好心情。我还要感谢我在旅行中在这里和那里遇到的所有人。这些交流让我在这三年里不断发展和进步。J’ai 所以，感谢Arnaud让我当然要感谢菲利普和马克对我的但老实说，我必须感谢从Yon到Pierre再到Jean-Michel，谢谢!有许多人，无论远近，都影响了我的职业生涯，但对于论文来说，我在安格利特的时光与此有很大关系。最后，我不能不感谢我的家人和朋友，他们肯定永远不会打开这篇谢谢你，读得好!我ii.目录引言11最新技术水平1.1走向双曲平面模型81.1.1基数9的变换1.1.2合规转换111.1.3分布式铺设算法141.2从命名到1.2.1数论17.1.2.2地址空间1.2.3名称决议211.3问题221.3.1升级到1.3.2L’itinéraire optimal1.3.3查找移动目的251.3.4地址的复杂性261.4从1.4.1地址等坐标281.4.2更好地传递1.4.3双曲几何路由331.5合成342庞加莱37中的寻址和路由2.1同伴行为382.1.1启动协议382.1.2消息协议392.1.3动态图形的管理432.2静态模拟482.2.1模拟的配置和参数化482.2.2模拟492.3动态模拟532.3.1模拟的配置和参数化532.3.2模拟542.4L’infini en pratique2.4.1浮点精度问题65iii.iv目录2.4.2度对坐标数的影响672.4.3深度对坐标数的影响672.5结论683虚拟网络及其应用713.1虚拟或重叠网络（RR）723.1.1P2P架构：提醒723.1.2启动问题733.2在覆盖P2PTV74的网络中重新分发3.2.1理论分析753.2.2非活动对等体773.2.3过度活跃的同龄人783.3P2PTV网络中对等体选择算法的有效性3.3.1对覆盖78的网络的影响3.3.2对一对79的影响3.4覆盖P2PTV 79的网络仿真3.4.1模拟的参数和度量793.4.2模拟结果813.5结论83结论853.6研究前景86图表1.1双曲面与两片-摘录自书"发现宇宙的法律"由R. 彭罗斯......................................... 8号1.2双曲平面共形模型81.3基本复数变换101.4不保留元素大小的一致转换111.5三角............................................................................................................................形15的铺设1.6多边形边的长度。. . . .... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ... ... ...152.1 P2P网络中的集成协议. ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ... ... ...402.2 ALIVE消息交换协议... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...412.3贪婪路由和局部最小值.... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ... ... ...472.4最大深度测量标准树寻址计划492.5使用hy树寻址计划测量最大深度双曲492.6使用词典式路由的502.7双曲贪婪路由的平均对等。... ...502.8使用词典式路由测量2.9使用双曲布线测量2.10使用路由进行拥塞词典编纂522.11使用路由进行拥塞双曲522.12250个对等体542.13贪婪路由的交付率与设置的时间间隔维护和维护552.14每单位丢失数据包的累积在500个对等体的网络中的时间2.15每单位数据包丢失的累积2000个对等体网络中的时间562.16每单位丢失数据包的累积在1000个对等体的网络中的时间2.17500个对等体2.181000个对等体2.192000个对等体2.20网络中不同路由算法的交付率1000对，up=16，fl=32582.211000个对等体2.22每单位丢失数据包的累积1000个对等体网络中的时间592.23每500个对等体的592.24每1，000个对等体的60六、图表2.25 每2，000个对等体的路由算法交付率602.26 作为报头大小函数的G-P算法的递送率每包500对602.27 详细的贪婪路由算法执行发布同行612.28 详细的贪婪路由算法执行发布同行612.29 500个对等体的路由表大小622.30 每1，000个对等体的622.31 2000个对等体的路由表大小622.32 每1，000个对等体的数据包所采用的路由路径长度622.33 2000个对等体的数据包所采用的路由路径长度622.34 500个对等体的数据包所采用的路由路径长度632.35 扩展500个网络中的数据包所采用的路径同行632.36 扩展1000个数据包的网络中的路径第64章2.37 2000年网络中数据包所采用路径的拉伸第64章2.38 500个网络中控制流量传输中的字节数第64章2.39 网络中控制流量传输中的字节数1000对652.40 网络中控制流量传输中的字节数2000对652.41 具有网络的入站对等体的起始列表的演变从500对652.42 根据浮点精度阈值66的寻址能力2.43 度对理论地址数的影响2.44 程度对实际地址数量的影响2.45 程度对地址数量3.1网络容量与非活动对等773.2网络容量与过度活跃的对等体783.3平均观看时间与流量的关系813.4被拒绝的对等体与流量823.5每个对等体的平均中断数简介自20世纪90年代以来，网络的网络，通常被称为互联网（英语：Inter-networking），已经L’accession à Internet est devenue ordinaire 事实上，每个人都可以决定对互联网上已经存在的我们触及了这一点，也许是它成功的第一个原因：自由。我们所说的自由是指创造和获取的自由然而，让我们记住，这种自由是由科学家创造的，他们提供了工具，使每个人都有可能 因此，用文顿·瑟夫2的话来说：从这一创新中诞生了一种新型的应用，其中用户参与所谓的对等模型是内容分发/共享应用程序的基础 强大是因为在此模型中实现的服务旨在在参与者之间分散因此，每个参与者都贡献并受益于可用的内容或P2P系统或应用允许直接从生产者到消费者的信息共享，即没有中间的中央服务器。不可否认，缺乏中央实体使得网络对于任何级别（物理和软件）的故障或攻击（合法或不合法）都是健壮的。然而，P2P应用对于涉及参与者之间的信任关系的软件攻击并不是本机鲁棒的尽管如此，这使得这种模式非常适合提供服务或可持续内容，例如：– 电话（Skype等）– 视频流（Zattoo等）– 文件共享（Napster、GNUnet等）– 分布式计算（Boinc等）今天的互联网是由成千上万个所谓的自治网络组成的。实现不同通信协议的软件体系结构基于分层模型，其中只有相邻层交换信息。在此体系结构1. Web是英语术语World Wide Web的一种误用，缩写为WWW，指的是像2. http：googleblog.blogspot.fr/2005/11/vint-cerf-speaks-out-on-net-neutrality.html12I内导管端到端模型此模型旨在使网络上的所有其他计算机都可以访问和查看一台计算机这是P2P应用程序成功的关键因素之一。然而，由这些应用程序引发的热潮已经产生了大量的流量，由于某些参数的可变性（例如，端口号在不到十年的时间里，这种交通量似乎因此，毫无疑问，自从Napster以来，P2P应用程序已经在互联网上站稳了脚跟然而，由于在交通流中观察到的不平衡，这引起了相当大的关注这会使网络管理复杂化并降低用户性能。对于最悲观的人来说，它还降低了网络的鲁棒性，因为一些元素变得比其他元素更不可或缺事实上，P2P应用程序和其他应用程序的用户或多或少地传输大量此外，这些应用程序会产生额外的内部流量，以便进行协调。更不用说随之而来的技术问题，如"最后一英里"或网络不对称，这使得创建高性能应用程序变得性能的质量是根据所需的内部流量、速度和消息传递的保证来评估的这种流量不平衡的根源是选择与技术需求相关的每种信息的对等）。自从因特网创建以来，对其协议的修改已经被提出，并且有时被部署以支持越来越多的点对点内容传输应用，从电子邮件到P2P再到客户端-服务器。事实上，互联网诞生于众多网络的互联，如今已成为众多问题（社会、经济、数据安全、能源生态）的核心。然而 此外，这种新架构不应成为创造力和创新的障碍 为了应对，有两种方法是对立的：彻底[TBD + 11]或不[BFCW09]。这一挑战的基础是当前传输层及其信息路由服务的局限性。在这篇论文中，我们并事实上，边缘用户设备所遵循的演变并没有解决任何问题，因为网络访问不再仅限于个人计算机。公共设备现在已经这些对象无处不在，更不用说无处不在，并提供了在虚拟世界中持续交互的可能性。 此外，这些物品的物质能力也在不断提高。按照这个速度，我们可以预测信息高速公路上的交通堵塞3随着我们都成为潜在的内容生产者，而不仅仅是消费者，尽管搭便车者和播种者可能会继续对用户进行分类，但这可能会让我们面临数十亿字节的随着技术的不断发展，当对象实现机器对机器（M2M）通信以进行交互时，它们也成为用户赋予这些东西"思考"能力的技术是一个与无处不在的计算相关的概念的基础：物联网这些对象进入互联网的大规模进入创造了新的可能性，因为互联网允许这些设备不断互连（技术和社会）。然而，无论应用（例如P2P）或底层通信网络的类型（例如UMTS、802.15.4、802.11、以太网等）所需的基本功能是使用能够处理数百万对象的算法来路由信息。然而，目前还不能保证路由的扩展。在移动性不断提高的环境中，此基本功能的实施实际上，物理（ad hoc）和/或软件（P2P）网络中的参与者的波动性是最近的现象，其规模正在增长并且使路由问题复杂化，然而，已经提出了一些解决方案来鼓励参与者以可预测的方式留在网络中，特别是使用博弈论（多参与者针锋相对或启发式预测）。所有这些原因都促使我们解决提供信息的问题在过去的十年里，网络理论界对这个长期存在的问题--路由--重新产生了兴趣因为随着这首先是为了测试和部署我们的解决方案，我们正在研究虚拟网络虚拟网络是建立在底层图之上的抽象图。度可以是有界的，并且拓扑可以是动态的，因为存在波动性。 通常，程度取决于用户终端的配置和物理能力。此外，用于这些虚拟网络的理想互连模型 为了测试我们的解决方案，我们在模拟器中实施了我们的P2P系统，该模拟器提供了通常的统计和概率模型，如指数分布。虚拟网络旨在位于OSI（开放系统互连）模型的传输协议层（TCP或UDP）之上因此，我们的系统考虑了我们提出了一种分布式算法，它我们针对静态网络和动态网络对该算法进行了评估。路由问题是：– L’étirement4I内导管– L’utilisation d’un routage indéfectible qui passe à l’échelle et où le messageest dirigé– L’influence de l’interconnexion des pairs afin de créer une structureparticulière (e.g.然而，这些系统的设计比客户端-服务器模型的系统更复杂P2P系统的构建– 定义一个或多个命名协议，用于在系统中添加和删除对等体– 选择网络拓扑是否为结构化拓扑以及数据的路由方式– 定义数据管理模式（索引、访问），如– 在Internet的传输层（TCP或UDP）上定义有效的文件传输协议P2P系统构建中的这些步骤不是独立的，因为某些选择限制了解决方案的数量，但是没有服务器使得有可能在参与者之间分配负载：控制流量、要管理的请求在本文中，我们通过一个P2P虚拟网络，研究了我们的寻址和路由服务在动态环境中为这样一个网络的成员提供的此服务的目的是实现用于管理用户会话和内容的事实上，我们的最终架构旨在支持虚拟会话管理，以提高互联网上通信的灵活性。P2P应 用程 序 将 能 够 通 过 会 话 管 理 / 恢 复 在 通 信 期 间 灵 活 地 绑 定 用 户 、 应 用 程 序和 设 备 。文件结构本文档的结构如下。我们用尽可能高的抽象层次来表达问题，以便更好地理解它们的范围，从而理解它们的重要性。然后，我们在整个文档中细化我们的解释，以便只关注与我们的领域相关的问题 如有必要，我们将在每一章的开头回顾必要的概念。第1章：最新技术水平在第1章中，我们介绍了用于将图形嵌入曲面的工具的数学基础。 这种潜水是通过两个公式实现的，我们解释了这两个公式的起源。然后，我们研究了所选表面的数字化精度，并解释了这些含义。从第1.2节开始，我们将介绍在路由中执行的搜索，包括命名和我们将讨论贪婪路由，这是第1章和第2章的核心。当然，这会给我们带来估计问题。5在诸如因特网的网络中的距离然后，作为通过探索来估计距离的替代，我们讨论了重叠图提取技术，该技术允许提取边不相交的图。这些结构在贪婪路由算法中是必不可少的。重叠图是平面中的许多路由或导航算法的基础，因为它们允许在潜水后使用表征表面的度量（即距离函数）。第2章：庞加莱盘中的寻址和路由在第二章中，我们讨论了通过庞加莱模型在双曲曲面中实现贪婪路由。 我们尽可能准确地展示和评估我们的解决方案。在不失去一般性的情况下，我们展示并解释了我们的解决方案可以移植到任何类型的静态（互联网）或动态（MANet）异构通信网络中，在这些网络中，点对点路由的需求变得明显第3章：虚拟网络及其应用在第三章中，我们首先简要回顾了不同类型的然后，我们研究用于广播P2PTV视频流的对等网络我们在P2PTV网络中的视频再分发的上下文中讨论缩放因此，我们提出并评估了基于算法的对等体选择机制，通过模拟欧洲最大的P2PTV提供商之一Zattoo的架构获得模拟结果6I内导管第1章最新技术水平总结1.1走向双曲平面81.1.1基本。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...91.1.2合规转换111.1.3分布式铺设141.2从命名到1.2.1数论17.1.2.2地址空间1.2.3名称决议211.3问题221.3.1升级到1.3.2L’itinéraire optimal1.3.3查找移动目的251.3.4地址的复杂性261.4从1.4.1地址等坐标281.4.2更好地传递1.4.3双曲几何路由331.5合成34在本章中，我们将介绍该领域包括一组概念、协议、算法和技术，对这些概念、协议、算法和技术的理解被视为事实上，隐藏在现有通信网络背后的机器在两本主要的手工参考书中得到了揭示：《网络》[Tan04]和《计算机网络》[KR09]。然而，我们将回到一些基本概念，这些概念在过去十年中再次出现在科学舞台的前沿。我们的工作的贡献是满足了对一种算法的日益增长的需求，该算法在信息量减少的情况下，能够在有线或非有线网络中以分散的方式路由信息。78第一章。 最新技术水平H从因此，在本章中，我们介绍了解决与这一需求相关的问题的工作在第1.1节中，我们介绍了理解我们的工作所需的概念和工具实际上，我们提出了双曲平面的模型以及该曲面的几何性质。然后，我们提出了一个算法算法，一个具体的使用所选择的双曲模型。在第二节1.2中，我们回顾了命名、寻址和名称解析的概念，然后在第三节1.3中，我们详细说明了我们必须处理的问题。最后，在最后一节1.4中，我们介绍了1.1走向双曲在本节中，我们将介绍使我们的算法发挥作用的数学概念。我们使用精确的曲面，即双曲平面。几个几何或解析性质定义了超曲面空间。为了研究这些性质，数学家们在欧几里得平面中建立了双曲平面的表示法。这些表示是沉浸的结果，角度或平行线的概念FIGURE 1.1- -摘自《发现宇宙法则》一书彭罗斯图1.2-接下来，我们将使用双曲平面来导航图形，因此它的重要性 此外，双曲面也是闵可夫斯基空间M3的表示。二维双曲几何和三维闵可夫斯基空间M3与Beltrami共形表示直接相关，如图所示。1.1. 我们将在本节的最后看到代表性1.1. 走向双曲平面的模型9HU{骨干} |||}U{骨干} |||}>>>通过将空间+从双曲面的南极（-1，0，0）投影到赤道平面t = 0中的单位圆的内侧来获得贝尔特拉米共形（称为庞加莱）换句话说，Beltrami共形模型（称为庞加莱模型）是通过立体投影[RP07]构建的。由于这个原因，图1.2中双曲平面的表示有时被称为双曲平面的"共形模型"，通常被称为"庞加莱盘"（贝尔特拉米的）。从闵可夫斯基空间到庞加莱盘的变换使现在我们将更详细地研究在庞加莱圆盘内发生的变换1.1.1基本变换首先，庞加莱圆盘上的无穷点注意到，圆是由模为一个单位的复数组成的，这些点形成了圆盘的极限或闭合在数学术语中，圆的元素是zCz=1。如果欧几里德平面有一个标准化的正交坐标系，其轴代表虚坐标，则可以识别复数坐标。圆<内的点的集合表示双曲平面上的点的集合，即开单位盘DzCz1。开放意味着极限圆盘上的点被排除在集合D之外。存在几个模型来表示欧几里得平面中的双曲平面，每个模型都具有或多或少相似的性质。在本文的其余部分，我们将只通过庞加莱盘来讨论双曲平面度量空间在这里，我们介绍了距离和度量空间的概念和定义度量空间是可以定义每个点之间的距离的拓扑空间。度量的概念允许定义两个对象之间的距离空间X上的距离d是d：X的映射。X[0; +][电话 什么：– d（x，y）=0当且仅当x=y（相似性）;– d（x，y）>=0（非负性）– d（x，y）=d（y，x）（对称性）– d（x，z）=›→›→c+d-/^^›→{\displaystyle\{\displaystyle\网络。2dD（z，w）= acosh（1 + 2（1 −）|Z|（2）（1-）|w|（2）（1.1）复数在介绍基本的复杂变换之前，让我们简要回顾一下记录这些数字的不同方法一个数Complexe p可以写成：– 或者以笛卡尔形式z = a + ib，其中|Z|=√A2 + B2，– 或者以其极性形式z = |Z|iarg（ ），– 或者用欧拉公式eiθ= cos（θ）+isin（θ），其中cos（θ）=（z）/|Z|其中sin（θ）==（z）/|Z|其中z =|Z|（s（θ）+isin（θ）），图1.3图1.3总结了最基本的复杂变换。详细信息可以在[Che08]的"莫比乌斯变换"一章中找到总而言之，图1.3显示了加法和乘法运算产生的位移。例如，乘以虚指数z eiφz会旋转中心O和角度φ。这相当于在极坐标记法中将角度相加。最后，这些变换的合成，如zaz+b，被称为线性变换。在我们的例子中，我们特别感兴趣的变换是双线性变换或莫比乌斯变换，它们是形式为T（z）= a���+b的 有 理 函 数 T ： C C ， 其中a，b，c，d C是常数，ad bc = 0 [Sti92]。此外，确保庞加莱盘在变换期间保持不变的关键变换是z 1 /z反转。因为T（z）是反转的乘积，因为方程可以表示为以下形式的变换的乘积：z 1 /z，zxz，z y+z，其中x，yC中的每一个都可以看作是反转的乘积[Sti92]。我们刚刚简要地看到了图1.3中复平面的所有基本变换。 我们将在后面介绍和使用这些变换，特别是莫比乌斯变换，在开单位盘中。1.1. 走向双曲平面的模型11A1.1.2一致的转换提出的概念是"共形几何"。正如罗杰·彭罗斯（Roger Penrose）所解释的一般来说，从平面的一个区域（称为开放区域）到另一个区域的变换 为了便于理解这个概念R.彭罗斯考虑在平面上画的小（无穷小）圆。在保形变换之后，可以扩展小圆。或收缩，但不会变形为椭圆形。此外，保形变换会保留曲线之间的角度这最后一个性质对于我们使用双曲平面是必不可少的，事实上，在双曲平面中，两条曲线在其交点处的角度的概念与 两条 曲线 在其 交 点处 的角 度 的欧几里得度量完全相同 [R P07] 。图1.4图1.4是一个例子，它显示了双曲平面上共形变换的结果这样的转换不会保留元素的大小实际上，图1.4中中心区域的图形被转换成与圆在空间中的新位置相对应的最小的圆位于边界圆的正前方 彭罗斯用无穷小的小圆圈具体地说，我们将详细描述的变换允许通过平移或旋转来移动庞加莱圆盘内的点，同时保持无穷小的性质，如用圆所解释的。但是，在变换过程中，这是我们的路由算法正常工作的必要条件。因此，我们对等距感兴趣。在几何学中，等距是保持长度不变的变换。数学家们还讨论了庞加莱圆盘的自同构，表示为ut（D），这是保持圆盘的复变换[Bia08，Emm08]。共形自同构群12第一章。 最新技术水平D→Dc+d1A>>›→1+ i> θ- {}单位盘的全纯等距是因为，如果dD（z，w）=lD（γ），则连接z和w的路径γ称为双曲测地线弧其中LD（γ）是z和w之间的路径长度。这意味着长度是最小的。然而，在曲面（如双曲平面）中存在的唯一最小路径是测地线。在图1.5中，树的弧似乎在接近极限圆时收缩，或者在图1.4中，圆的直径似乎在但这实际上，图1.5中绿弧的长度在双曲平面内保持严格相同，圆1.4的直径也是如此。庞加莱度规的圆盘等距群与圆盘的全纯双射群等同[Pan05]。的所有全纯双射的形式都是a���+b。此表单表示一个集合莫比乌斯变换s，其中i表示vel���b o r + i a> e n tatio n（例如， v向量）。特别是变换T（z）=a+b。对于平面图中打开的单元盘复变换，如果α奏效D且p是D的一个元素，则参数化变换定义为由fα，p=eiα。 ���-A-保存单位磁盘[Ghy06]。 这就引出了第一个方程。对我们的算法至关重要：zp+pz›→1+p›z=eiθw+p（1.2）P W给定任意两个点zp和pD，变换群中的一个元素将第一个点p发送到第二个点z p，其中zp由弧长和角度参数化[BM06]。全纯双射是对方程1.2形式的双线性变换的圆盘的限制。 为了得到方程1.2，我们必须通过z p的极坐标来考虑z p。中心双曲极坐标是通过在D中设置一个点p来定义的，该点称为基于p的极坐标的中心。对于θR，ρθ（p）表示例如，在θ=0的情况下，欧几里得切线单位向量与半径（0，1）混淆，而ρ0（p）被称为从p开始的水平双曲测地线，因为p处的切线单位向量是水平的。设zp（s，θ）=w且s=dD（p，w）zp（s，θ），其中s是从p到w的双曲距离，θ是 实际上，坐标的中心可以看作是半径为弧长s的圆[MM06，BM06]。 那么zp是ρ θ（p）的双曲弧长的参数化。在p处具有不同切单位向量的两条测地线射线是不相交的，但在p处除外，它们从p处发出。或者，换句话说，对于Dp中的每个点w，存在唯一的测地线半径ρθ（p），其包含w点w相对于中心p的极坐标，即对（s，θ）=w。L’équation 因为因此，这项工作向我们表明，与特定变换方程相关的庞加莱模型在数字化到计算精度时是正确的。事实上，有了这个方程，我们可以P