随着互联网技术的普及,计算机网络对于人们的影响不断加深,互联网应用的更新速度可谓日新月异。与此形成鲜明对比的是,今天的互联网基础设施与其诞生初期相比并没有太大本质上的区别。伴随互联网规模的不断扩大以及新兴应用的不断涌现,原有基础设施的一些不足之处开始变得越来越明显。例如:BGP路由机制存在路由故障恢复时间长以及路径膨胀等问题,可能严重影响端到端的传输性能;对组播等多元化传输模式支持的缺乏以及对QoS的保障的缺失则大大增加了网络应用在这些方面的实现难度。而另一方面,过去人们一直习惯把基础设施与终端节点(主机或各类服务器)对立起来,由基础设施提供接入及数据传输等基础服务,而终端节点只负责网络应用程序的运行。这个模型意味着要改造互联网基础设施必将波及原有大量的网络设备(如所有的路由器),需要大量的投入,在应用前景尚不明朗的情况下,网络运营商在面对新技术时往往采取比较保守的态度。这也促成了互联网基础设施发展的迟滞状态。层叠网(overlay network)的出现使人们对互联网基础设施有了新的认识。层叠网是指网络中的一部分节点为了实现某一特定目标,利用原有网络所提供的基础服务自发形成的上层网络。近年来,以弹性层叠网(resilient overlay network)和层叠网组播(overlay multicast)为代表的层叠网应用技术开始兴起。虽然这些层叠网建立在终端节点之上并都以网络应用自居,但它们的最终目的是为了提供路由或组播这些人们原本认为应当由基础设施来提供的基础性服务。因此我们认为,各种形式的层叠网本身可以成为互联网基础实施的重要组成部分,同时层叠网技术可以成为改造和更新当前互联网基础设施的一个重要手段。我们的这一观点主要基于以下两个事实:首先,从提供基础服务的角度来看,许多由终端节点组成的层叠网与由路由器组成的第三层网络具有相同的目的,在大多数情况下,前者可以看作是对后者有效的补充;其次,层叠网技术的一个重要思想是通过少部分节点的协同合作来实现面向应用的基础服务,这不需要全面和彻底地改造原有的互联网基础设施,大大降低了实现成本,具有良好的灵活性和可行性。根据以往的经验,层叠网在提高路由质量和提供组播服务等方面能够对当前的互联网基础设施起到很好的补充作用,但真正要让层叠网成为基础设施的一部分,还有许多关键问题亟待解决,本文正是围绕这些问题展开讨论的。本文的创新点主要有以下三条:1开创性地提出了在考虑BGP路由策略干扰情况下的路由层叠网的节点部署问题的数学模型,并将该问题分解成层叠路径布局与层叠路径合并两个子问题。针对这两个问题分别设计了LASER算法和最大交集启发式算法,这套算法组合能在多项式时间内针对特定的连接需求集计算出一个路由层叠网节点布局方案,以尽可能少的层叠节点成本消除BGP路由策略所带来的路径膨胀问题,实现最短AS路径路由。2创造性地提出了动态层叠网的概念并针对动态层叠网的拓扑拟合问题设计了一个全新的网络原语--JRF。JRF原语的独特之处在于它巧妙地借用了组播路由器的功能帮助层叠节点获取底层网络信息,同时又避免了IP组播的一些缺点,具有很好的实用前景。在JRF原语的基础上,我们又设计了TOMIMN层叠树路由算法,将基于JRF原语的层叠网拓扑拟合技术与具体的应用相融合,从而实现层叠树拓扑质量与应用性能的平衡。3创新地将Diffserv体系结构与层叠网组播技术融合在一起,形成了一套能够保证服务质量的层叠组播解决方案。这套方案的核心是1阶DIRA路由算法与n阶DIRA路由算法。这两套算法利用DS域的边界路由器作为层叠节点形成组播树,从而实现保证QoS的层叠网组播。