Operations Research and Fuzziology
Vol. 13  No. 02 ( 2023 ), Article ID: 63728 , 7 pages
10.12677/ORF.2023.132049

——基于线性规划理论

—Based on Linear Programming Theory

Yongyi He, Xiankai Li

School of Science, Beijing University of Posts and Telecommunications, Beijing

Received: Mar. 7th, 2023; accepted: Apr. 2nd, 2023; published: Apr. 10th, 2023

ABSTRACT

Keywords:Optimization, Linear Programming, Network Load Balancing

1. 引言

2. 背景

2.1. 基于策略的启发式算法

2.2. 基于模型的优化算法

3. 一种新增链路数最小的网络负载均衡算法

3.1. 算法提出

3.2. 模型建立

3.2.1. 符号说明

3.2.2. 优化目标

3.2.3. 问题约束

$\underset{\forall e\in E}{\mathrm{max}}\left(\underset{m\in D}{\sum }\frac{{x}_{me}}{{b}_{e}}\right)\le \alpha$ ，为了使约束方便线性化求解，我们可以等价的要求每条边都满足该约束，即 $\underset{m\in D}{\sum }{x}_{me}\le \alpha {b}_{e},\forall e\in E$ 。非负约束要求我们的决策变量都是非负的，这是由于问题特性决定的，即 ${x}_{me}\ge 0$

3.2.4. 数学模型

$\begin{array}{ccc}\underset{{x}_{me}}{\mathrm{min}}& \underset{m\in D}{\sum }\underset{e\in E\{E}_{m}}{\sum }{\left({x}_{me}\right)}^{0}& \\ \text{s}\text{.t}\text{.}& \underset{e=\left(i,j\right)\in E}{\sum }{x}_{me}-\underset{e=\left(j,i\right)\in E}{\sum }{x}_{me}=\left\{\begin{array}{cc}\begin{array}{c}{d}_{m},\\ -{d}_{m},\\ 0,\end{array}& \begin{array}{c}\text{if}\text{\hspace{0.17em}}i={s}_{m}\\ \text{if}\text{\hspace{0.17em}}i={t}_{m}\\ \text{others}\end{array}\end{array}& \forall m\in D,\forall i\in V\\ & \underset{m\in D}{\sum }{x}_{me}\le \alpha {b}_{e},& \forall e\in E\\ & {x}_{me}\ge 0.& \end{array}$

3.3. 模型求解

$\begin{array}{ccc}\underset{{x}_{me}}{\mathrm{min}}& \underset{m\in D}{\sum }\underset{e\in E\{E}_{m}}{\sum }{x}_{me}& \\ \text{s}\text{.t}\text{.}& \underset{e=\left(i,j\right)\in E}{\sum }{x}_{me}-\underset{e=\left(j,i\right)\in E}{\sum }{x}_{me}=\left\{\begin{array}{cc}\begin{array}{c}{d}_{m},\\ -{d}_{m},\\ 0,\end{array}& \begin{array}{c}\text{if}\text{\hspace{0.17em}}i={s}_{m}\\ \text{if}\text{\hspace{0.17em}}i={t}_{m}\\ \text{others}\end{array}\end{array}& \forall m\in D,\forall i\in V\\ & \underset{m\in D}{\sum }{x}_{me}\le \alpha {b}_{e},& \forall e\in E\\ & {x}_{me}\ge 0.& \end{array}$

4. 数值实验

4.1. 测试网络拓扑

4.2. 数值结果

Figure 1. Comparison of OSPF-ECMP algorithm and the new algorithm in classic topology

Figure 2. Comparison of OSPF-ECMP algorithm and the new algorithm in random topology

5. 结论

A Network Load Balancing Model with Minimal New Links Added—Based on Linear Programming Theory[J]. 运筹与模糊学, 2023, 13(02): 504-510. https://doi.org/10.12677/ORF.2023.132049

1. 1. Al-Fares, M., Radhakrishnan, S., Raghavan, B., et al. (2010) Hedera: Dynamic Flow Scheduling for Data Center Networks. NSDI, 10, 89-92.

2. 2. Yan, Q., Yu, F.R., Gong, Q., et al. (2015) Software-Defined Networking (SDN) and Distributed Denial of Service (DDoS) Attacks in Cloud Computing Environments: A Survey, Some Research Issues, and Challenges. IEEE Communications Surveys & Tutorials, 18, 602-622. https://doi.org/10.1109/COMST.2015.2487361

3. 3. Hopps, C. (2000) Rfc2992: Analysis of an Equal-Cost Multi-Path Algorithm. https://doi.org/10.17487/rfc2992

4. 4. Schneider, G.M. and Nemeth, T. (2002) A Sim-ulation Study of the OSPF-OMP Routing Algorithm. Computer Networks, 39, 457-468. https://doi.org/10.1016/S1389-1286(02)00231-1

5. 5. Bley, A. (2011) An Integer Programming Algorithm for Routing Optimization in IP Networks. Algorithmica, 60, 21-45. https://doi.org/10.1007/s00453-009-9381-5

6. 6. Chekuri, C. and Idleman, M. (2018) Congestion Minimization for Multipath Routing via Multiroute Flows. 1st Symposium on Simplicity in Algorithms (SOSA 2018), Schloss Dagstuhl-Leibniz-Zentrumfuer Informatik, 7-10 January 2018, 3:1-3:12. https://doi.org/10.4230/OASIcs.SOSA.2018.3

7. 7. Das, B.C., Begum, M., Uddin, M.M., et al. (2020) Conic Programming Approach to Reduce Congestion Ratio in Communications Network. Cyber Security and Computer Science: Second EAI International Conference, ICONCS 2020, Dhaka, 15-16 February 2020, 566-577. https://doi.org/10.1007/978-3-030-52856-0_45

8. 8. Candes, E.J. and Tao, T. (2006) Near-Optimal Signal Recovery from Random Projections: Universal Encoding Strategies? IEEE Transactions on Information Theory, 52, 5406-5425. https://doi.org/10.1109/TIT.2006.885507

9. 9. Cohen, M.B., Lee, Y.T. and Song, Z. (2021) Solving Linear Programs in the Current Matrix Multiplication Time. Journal of the ACM (JACM), 68, 1-39. https://doi.org/10.1145/3424305

10. 10. Huangfu, Q. and Hall, J.A.J. (2018) Parallelizing the Dual Revised Simplex Method. Mathematical Programming Computation, 10, 119-142. https://doi.org/10.1007/s12532-017-0130-5

11. 11. Kou, C., Hu, D., Yuan, J., et al. (2019) Bisection and Exact Algorithms Based on the Lagrangian Dual for a Single-Constrained Shortest Path Problem. IEEE/ACM Transactions on Networking, 28, 224-233. https://doi.org/10.1109/TNET.2019.2955451

12. 12. Jozsa, B.G., Kiraly, Z.E., Magyar, G.E., et al. (2001) An Efficient Algorithm for Global Path Optimization in MPLS Networks. Optimization and Engineering, 2, 321-347. https://doi.org/10.1023/A:1015318600381