基于链路容量算法的集中式计算机网络优化

An optimal algorithm of link circuit capacity for centralized computer network

针对满足一定约束条件的网络能力配置问题,提出链路总费用最小的链路容量新算法。该算法基于一个集中式计算机网络,以M/M/1排队理论和利特尔定律为依据,先设定整个网段各条链路上传输的报文流都是泊松流且呈负指数长度分布,然后求解在链路平均时延约束下链路总费用最小的链路容量整体最优解。与最小费用流模型中的消圈算法、最小费用路算法及原始—对偶算法相比,链路容量算法在复杂度、可读性、解决大规模网络问题及处理相同数目节点所花费的时间等方面,都呈现一定的优势。实验结果表明,采用新算法进行网络优化后,全网总费用降低17.51%,对集中式计算机网络优化设计具有一定的指导意义。

In order to satisfy the constraint condition ot network capability coniiguration, a new algorithm of link capacity is put forward with minimum link total cost. The new algorithm is based on a centralized computer network. On the basis of M/M/1 queuing theory and Little＇s law,the message flow from every link of the total network section is set to be Poisson stream with the length of a negative exponential distribution. Then the best optimization solution of overall link capacity with minimum link total cost is found in the condition of average delay in the entire network limited within a boundary value. Compared with cycle-canceling algorithm, successive shortest path algorithm and primal-dual algorithm of minimum cost flow model, this circuit capacity algorithm is simpler and readable, and it took less time to solve massive network problems or to deal with the same nodes. The result also shows, the new algorithm can reduce 17.51% of the total communications link costs, and has a guiding significance to the centralized computer network optimization design.