题目：面向实时流媒体的自组织覆盖网关键问题研究

以TCP/IP协议为核心的Internet受益于端点复杂中间节点简单的设计理念，但是随着应用种类的增加，它也逐渐暴露了控制简单，服务质量有局限，路由收敛慢，安全机制不完善等弱点，难以满足很多新型应用的需求。所以，在现有网络之上根据特定的需求，构建特定用途的覆盖网已经成为网络发展的一个重要方向。随着网络用户的不断增长，网络带宽的逐渐提高，互联网范围的大规模实时流媒体服务成为一类新的有吸引力的应用，具有广阔的前景。在现有网络上构建覆盖网，支持流媒体传输是一个有效的解决方式。本文研究了以覆盖网方式承载流媒体传输的网络组织、资源分配、合作激励等关键技术，对互联网体系结构的进一步发展和演变提供参考。围绕以结构化覆盖网支撑流媒体传输的问题，提出了一种基于簇的结构化覆盖网GSON，可以提高网络对节点变化的自适应能力，并以此为基础，提出了一种负载平衡的多播算法。GSON采用分布式哈希表（DHT）作为全局信息结构；在局部，将物理上距离较近的节点根据一个自组织协议形成簇。每个簇选择一个代表节点加入全局的DHT；代表节点负责全局DHT和簇内节点的沟通与信息映射。将系统对节点的加入和退出响应转化为局部操作，减轻对全局信息结构的影响。在此结构的基础上，提出了一种结合Pull和Push的多播算法，将数据源发出的数据流分成多个分支，根据DHT的键值特点构建层次性的虚拟多播树，将不同的数据分支映射到具有不同键值表达式特征的节点，以Push方式推送数据。其它节点根据地址特征进行查询和请求数据分支，互相交换和补充信息。试验表明，与典型的DHT网络Chord相比，GSON能够更好地应对节点的突发性的加入和退出，能够在较短的时间内，花费较小的代价使系统恢复到稳定状态，同时这种簇结构没有降低查询性能。基于该结构的多播算法具有较好的可扩展性，能够达到较好的负载平衡。围绕以随机Mesh方式支持流媒体传输的问题，在网络演化的各个阶段分别提出了节点邻居选择、数据分支调整、失效分支替换算法，进行系统的性能调优。首先提出了流媒体网络演化模型，用来描述网络随节点变化的演变特征，并在网络演化的各个阶段从邻居选择的角度分别提出了性能调优策略。为了减弱节点的动态加入和退出对数据传输稳定性的影响，数据源以冗余方式将数据流编码为多个等长的分支，并分别发送给不同的后继节点。网络中的每个节点通过与其它节点建立邻居关系获取所需的数据分支。在新节点加入的过程中提出了一种高效的邻居节点选择算法，充分利用编码的冗余性特点降低算法的时间复杂度。由于节点需要接收到一定数量的数据分支才能解码播放，所以播放的初始时延取决于时延最大的数据分支。为了降低初始时延，提出一种邻居调整策略，逐渐替换时延较大的数据分支的来源，去除系统瓶颈。在节点失效的处理过程中提出了一种数据分支的轮转替换机制，用以保证数据传输的连续性。分析与试验表明，在节点频繁变动的场景下，1）采用冗余编码和节点失效后的父节点替代算法都可以有效地减少数据中断；2）高冗余度的编码能够更好地适应高度变动的网络，冗余编码不会显著降低网络的传输效率，网络传输效率对编码的冗余度不敏感；3）数据分支的个数在8－16之间时传输性能较高；4）邻居调整策略可以有效地降低节点的初始时延，并能显著降低网络整体的传输时延。 为了促进覆盖网络对带宽资源的合理分配，提出一种分布式的启发式流量分配算法。将覆盖网的数据传输问题映射到底层物理网络，采用了一种以网络整体加权平均时延最低为目标的性能评价模型。该模型支持多源点多终点的覆盖网络，支持多个多播组的流媒体传输。以网络加权平均时延为评价依据，提出启发式流量分配算法，该算法在覆盖网的任意相邻两节点间计算路径平均加权时延，作为衡量路径时延状况的指标，并根据该指标分配共享瓶颈带宽，解决多数据流冲突。基于这种冲突处理方式，数据源节点采用一个两级反馈算法分配输出的数据流量。模拟试验表明，加权平均时延与表征流媒体传输质量的数据片命中率存在很高的线性相关性，对传输质量有指导意义；流量分配算法对网络整体传输效率有显著提高，对流量分配的调节快速有效。与平均分配共享带宽的方式相比，网络整体的加权平均时延有比较显著的下降。为了促进覆盖网节点之间的合作，以任意相邻的两个节点为博弈参与者，提出一种可以容忍故障的节点间合作激励策略。在静止状态下用纯策略博弈建立了问题模型，证明静止状态下的节点数据转发博弈是典型的囚徒困境。用无限重复囚徒困境博弈建立模型，证明了在真实网络环境下，基于针锋相对策略的合作均衡是脆弱的，偶然的网络故障会导致惩罚行为，从而引起节点间的不合作。提出一种可容错的针锋相对策略TTFT，该策略能够在一定时间内容忍网络故障的发生。证明了使用该策略可以在发生网络故障的情况下，在有限时间内使节点达到稳定的合作状态，并且作弊行为的收益增量相对较低，能够有效降低节点作弊的可能性。模拟试验证明，在多个节点的环境下，该策略可以容忍一定比率的故障，促进节点合作，显著提高全体节点的收益总额，并可以降低作弊节点的收益，有效防止作弊。