交换机中周期流优化调度问题的复杂性

研究了交换机中周期流量的优化调度问题,着重讨论了该问题的复杂性.依据呼损率定义了交换机周期流量调度的最优化问题,并对其子问题,嵌套周期流优化调度的复杂性进行了研究.证明了一种受限Max2Sat问题的NP完全性,并通过将该问题多项式归约到交换机周期流量调度的最优化问题,由此证明了仅有1和2周期的交换机周期流优化调度问题是强NPC问题.并利用该结果证明了任意嵌套周期的优化调度问题也是强NPC的.这表明对于任意嵌套周期流优化调度问题不存在伪多项式算法.

多QoS约束路由算法综述

QoS(Quality of Service)路由算法是解决QoS问题的关键,也是当前网络领域里的一大研究热点。QoS路由算法的主要目的是为接入的业务选择满足服务质量要求的传输路径,同时保证整个网络资源的有效利用。改文深入探讨了QoS路由问题的实质,并对以往的QoS路由算法进行了归纳总结。基于已有的QoS路由算法的研究,该文对QoS路由算法的发展方向进行了预测。