关于实际构造最大带宽路径算法的研究

建立最大带宽路径一直是网络路由研究，尤其是在最近的网络QoS路由研究中的基本问题，在以往的文献中，有人提出了利用修改的Dijkstra算法或修改的Bellman-Ford算法来构建最大带宽路径。该文给出了一个简单的证明，指出了最大生成树与最大带宽路径之间的特殊关系，证明了可以使用修改的Kruskal算法来构建最大带宽路径，文中给出了修改的Kruskal算法，并且与已有的Kijkstra算法作了性能上的比较，尽管从理论上说，Dijstra算法和Kruskal算法的时间复杂度具有同样的阶，但在多种不同网络结构上的模拟测试结果表明，用Kruskal算法构建最大带宽路径的实际运行比Dijkstra算法至少要快3倍，而且在实际上比Dijkstra算法更简单，灵活。     

一种最小化最大带宽利用率的TE路由算法

随着网络中流量的迅速增长，流量工程对于减小拥塞、提高网络资源的使用效率、满足业务的QoS要求，正在起着越来越重要的作用．提出了一种对Dijkstra算法进行改进的最小化最大带宽利用率TE路由算法．该算法在搜寻路径的过程中，将原来Dijkstra算法中的以路径代价最小为目标，更改为以最小化最大带宽利用率为目标．仿真证明，算法在一定程度上达到了均衡负载分布的作用．     

第k条最大可用带宽路径算法

该文提出了无环路的第k条最大可用带宽路径算法．由于具有凹性的带宽和具有加性的代价存在本质区别,第k条最大可用带宽路径算法不能通过简单修改第k条最短路径算法得到．该文结合两个新定义的路径操作和修改的二重扫除算法完成第k条最大可用带宽路径算法,并证明其正确性、无环性和具有多项式复杂性,最后给出实例并讨论算法实际应用．该文解决了基于带宽度量的路由算法中一类很基本的问题;因算法采用能反映网络实时特性的可用带宽作为路由度量,能直接保证网络带宽资源的最优利用．     

基于CDMA-over-TDMA的多路带宽预留算法

讨论了在进行有QoS保证的路由选择的研究中所遇到的一些问题,并提出了一种新的带宽预留的路由选择算法MBR。MBR算法把路由选择分为两个阶段：路由发现和带宽预留。在路由发现阶段,算法首先寻找多条到达目的节点的路径,然后在带宽预留阶段,对寻找到的路径进行带宽预留,最后由目的节点决定使用哪些路径进行传输。由于MBR算法是采用同时寻找多条路径来进行带宽预留,因此它与其它带宽预留算法相比,具有更高的成功率。     

一种加权的启发式QoS路由算法

本文推广启发式搜索算法公式,提出了一种基于费用和延迟的加权启发式QoS路由选择算法。根据带宽和抖动等限制条件的不同特性,对费用和延迟加上不同的权值,得到费用最少的QoS路由,并研究了在不同的权值下对搜索性能的影响。仿真结果验证了该算法的有效性。     

一种高效的虚路径带宽分配最优算法

作者提出了一种在电信网中对虚路径的带宽进行分配的步进式最优算法．在给定网络拓扑结构、链路容量、虚路径路由以及通信量的条件下,此算法能够对虚路径的带宽进行优化分配,从而使得网络中所有(源-目的)点对的最大呼损率(Call Blocking Probability．CBP)达到最小．在每一点对之间只取一条虚路径的条件下,该文对此算法的最优性进行了证明．基于该文中给出的测试网络,作者将另一种流行的最优算法“二分法”和此算法的性能进行了对比．从实验结果中可以看到,步进式算法能给出最优的最大呼损率．速度是二分法的三倍以上,而且平均呼损率相对降低了20％以上．     

一种新的实现效用函数最大最小公平性的分布式算法

计算机网络中的一个核心问题就是如何在竞争的流之间公平地分配带宽。由于网络是分布式的,因此又要求带宽分配算法可以是分布式的,这样就可以在路由器端和用户端配置,从而分别不停地调节速率以达到网络平衡和最优状态。不同的算法对应不同的公平性标准,其中应用最为广泛的就是最大最小公平性以及效用函数最大最小公平性。本文提出了一种新的方法来实现效用函数最大最小公平性,这种方法基于非线性优化中的向量优化方法和Kuhn-Tucker条件。利用这种方法可以把网络优化问题转化为一系列等价的条件,这些条件的最优解就是原问题的解。而求解这些条件可以运用经典的非线性优化的梯度投影算法,由此产生了一种分布式的用户链路算法并通过案例验证了其正确性及性能。     

一种无线Ad Hoc网络中的最大最小公平性带宽分配优化方法

本文提出了一种无线Ad Hoc网络中的最大最小公平性带宽分配优化方法,通过此优化方法所求得的带宽分配不仅能保证最大最小公平性,而且能更有效地利用网络资源,从而提高网络的吞吐量。     

关于最大团问题的一种新算法

最大团问题是图论中重要的NP完全问题,目前求解最大团问题的方法只适合某些特殊的图,活则消耗时间长,求解效率低。该文提出了一种新的算法,蚁群算法来解决最大团问题。蚁群优化算法是一种基于自然启发的算法,是一种解决组合优化问题的有效方法。实验结果显示,算法的有效性。     

关于最大团问题的一种新算法

最大团问题是图论中重要的NP完全问题,目前求解最大团问题的方法只适合某些特殊的图,活则消耗时间长,求解效率低。该文提出了一种新的算法．蚁群算法来解决最大团问题。蚁群优化算法是一种基于自然启发的算法,是一种解决组合优化问题的有效方法。实验结果显示,算法的有效性。     

一个新的最大流问题增载轨算法

通过放松Ahujia和Orlin算法的约束，给出了一个新的增载轨算法．该算法实质上提供了一个构造、阻塞无环网络的策略，它可以在每次构造无环网络中得到更多的增载轨．从而进一步降低了找到每条增载轨的代价．实验表明，新的算法比Dinic算法快2～5倍，和目前实验性能最好的预流推进算法基本相近．说明增载轨类算法在实际性能方面未必落后于预流推进类算法．     

多逻辑链路最大可用带宽比流量调度算法

针对多逻辑链路间流量调度不平衡问题,分析逻辑链路流量调度模型,给出逻辑链路可用带宽计算方法,提出＂可用带宽比＂指标,以更准确地刻画各链路负载状况,量化特定链路上调度流量的大小。仿真实验证明,该算法有较好的流量调度能力,能有效控制各链路的流量,改善多链路间负载均衡,提高链路利用率。     

大规模通信网络带宽优化分配问题研究

提出一种大规模通信网络带宽分配的新方法．作者将大系统理论中的分解—协调方法运用于解决大规模通信网络带宽分配的优化问题，大型网络的优化问题被分解成一些互相关联的小型子网的优化问题．整个带宽优化分配问题的解决分为三个阶段：分解、协调优化及合并优化．计算结果表明，与现有算法相比，分解—协调大规模带宽管理算法(DCLPBM)既保证了很高的计算精度，又降低了时间与空间复杂度．由于算法中用到的协调机制较简单，DCLPBM易于推广到分布式计算环境，从以网络来治理网络的角度看，它具有较广的前景．     

一种新的Kth最短路径搜索算法

借助于“背离”路径的概念,论文在2nd最短路径搜索算法的基础上提出了一种新的Kth最短路径搜索算法,并将其应用至实际环境中。通过K-1次2nd最短路径搜索算法的迭代,该算法可以求出网络中任意两个给定节点之间的Kth最短路径,2nd最短路径搜索算法在计算上具有简单性,因而也同样具有简洁、快速的特点。     

MANET中基于遗传算法的带宽计算

在MANET中寻找满足带宽约束的QoS路由的前提是确定路径上带宽的大小,在MAC层采用CDMAoverTDMA的网络中,路径上带宽的计算并非单纯地取路径上所有链路的最小带宽,其计算时间复杂度已经被证明是个NP完全问题。该文提出将遗传算法用于带宽计算,并提出了基于空闲时隙链路块的编码方法。仿真结果表明:该算法可以应用于网络规模比较小的带宽计算中,并且可以比其它带宽计算方法获得更大的带宽。     

Walker星座中一种新的最短路径路由算法

利用卫星运行的规律性和星际链路连接的规则性,提出了Walker星座中的缩水最短路径路由算法.算法根据最少跳数下最短路径的路由选择原则,将路由选择分为方向估计与方向选择两个阶段,方向估计阶段给出使得路径跳数最少的节点的两种选择方向,方向选择阶段基于方向估计的成果划定路径搜索的节点空间,最终得到使得路径距离最短的第一选择方向.通过分析与仿真,在算法的运算量与有效性方面将缩水最短路径路由算法与Dijkstra算法进行比较,结果显示,在有效性几乎一致的情况下,缩水最短路径路由算法减小了搜索空间,从而使算法的运算量有了大幅下降.     

一种求解网络图最大流的新算法

给出一种求解网络最大流的新算法,该算法是针对增广链选取的顺序不当而无法得到理想的最大流,且在计算过程中每步都需要画一个网络图等问题进行的改进。利用分层及度差的概念,在选择增广链时优先选择路径最短且度差较大的路径,相同层次度差相同时优先选择容差较大的路径,在饱和的弧上画上终止符。最后用实例进行了验证并和Ford—Fulkerson算法做了比较,体现了它的高效性,避免了标号,且只需要在一个图上即可完成。整个运算过程直观性强,计算方便。     

一种关于重叠服务网络的可用带宽测量技术

本论文介绍的是一种关于在一条网络路径上的两端主机之间的可用带宽测量的新算法。这种算法是对目前在线网络测量中使用的主动测量方法的一种调整。这种测量是由TCP的数据包和确认包的传输和接受的时间间隔中推断出来的网络特性的信息实现的。在全方位服务网络中在线网络测量起到很大的作用,在其中可用带宽的最近数据信息将会尽快的被下一层的IP层获得。在本论文中,首先介绍了这种算法,然后讨论在主动TCP连接中应用这种算法所遇到的问题。