李 永，陆 伟

(盐城师范学院 信息工程学院，江苏 盐城 224002)

1 概 述

随着计算机网络的飞速发展，各种计算机应用不再局限于单机的或独立的系统，而是通过网络进行连接，以分布式的形式开展各种应用，地理上分散的多个端用户端节点能够在一个共享的统一的网络虚拟环境中通过分布式交互和协作完成特定任务。这类应用被称为分布式交互应用(distributed interactive application，DIA)，是近年来的研究热点[1-4]。目前分布交互应用主要体现在分布式虚拟环境、分布式交互仿真、协同设计与制造、军事仿真系统、网络在线游戏、视频会议等方面。路由问题是DIA中的基础和关键问题之一。地理上分散的DIA节点通过计算机网络进行相连，为了实现DIA中各节点间的状态一致性和协同交互，DIA中各节点之间要进行大量的数据通信。这些交互数据不仅要求传输时延小，而且到达各节点时，必须是完整的和正确的。DIA对信息传输的基本要求可归纳为：实时性、高带宽、可靠性等[5]。

DIA中信息数据路由需求可分为一到多(single-to-many)、多到多(many-to-many)、全部到全部(all-to-all)[6-9]。其中，many-to-many可以看成是多个single-to-many的简单叠加；而在all-to-all中，每个DIA节点都发送信息数据到所有其他的节点。在DIA的全部到全部路由中，每一个节点既是发送者，又是接收者；尤其是具有延时约束的全部到全部的分布式交互应用对底层网络数据通信的要求苛刻。目前关于DIA全部到全部路由问题的研究大致可分为四类。一是采用组播有源树的路由方式，针对每一个需要发送数据的节点都以它为根构造一棵数据分发树，这样的数据分发方式延时性能较好，但费用开销大，尤其是当大量的节点参与DIA应用时，导致网络设施无法支撑DIA应用。……