李 富，程子敬，李 周，王 瑞

（北京卫星信息工程研究所 北京 100086）

为了提高网络可靠性，交换机连接为环型拓扑或网状拓扑，但会形成二层环路，IEEE STP生成树协议[1]通过有选择性地阻塞网络冗余链路来达到消除网络二层环路的目的。但STP导致负载分配不均和瓶颈，尤其在接近根交换机的位置。同时在没有经过优化的拓扑结构中，可能会存在较大传输时延。所以，良好的网络拓扑设计是避免网络时延影响的第一步。

网络拓扑设计问题作为一个复杂的组合优化问题，同样可归结为一个NP-hard问题。文献[2]提出可靠性和成本平衡的拓扑设计方法，但没有考虑交换机的容量限制。文献[3]采用遗传算法来优化子网划分，平衡各个子网的通信负荷。文献[4]研究了TS（Tabu Search）算法来优化交换式网络。文献[5]中利用模拟退火（SA）算法作为找到最佳网络拓扑结构的技术。

文中根据终端节点之间的业务优先级及其静态流量要求，提出了一种网络拓扑选择算法，确定交换机的生成树拓扑以及终端节点和交换机的连接关系。该方法对拓扑进行评分，在所有可能的拓扑结构中找到最好的拓扑结构，确定交换机之间的树型拓扑和终端节点的分布位置。在网络拓扑评估中考虑两条准则：交换机负载均衡，和流量最短路径选择。定义两个系数α，β分别对应上述准则，根据目标确定每个准则的权重。算法独立于上层应用，可以用来保证高优先级的业务流量经过最短路径，同时避免网络资源的利用不足。……