Link State-Based Precomputation for Multi-Constrained Routing

CUI Yong; WU Jian-ping; XU Ke

您当前的位置：

首页 >

文章列表页 >

Link State-Based Precomputation for Multi-Constrained Routing

更新时间：2025-07-16

- Link State-Based Precomputation for Multi-Constrained Routing
- Acta Electronica Sinica Vol. 31, Issue 8, Pages: 1173-1177(2003)
- 作者机构：
  
  清华大学计算机科学与技术系,北京,100084
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP393.01
- Published：2003
- 稿件说明：
移动端阅览
CUI Yong, WU Jian-ping, XU Ke. Link State-Based Precomputation for Multi-Constrained Routing[J]. Acta Electronica Sinica, 2003, 31(8): 1173-1177.
DOI：

CUI Yong, WU Jian-ping, XU Ke. Link State-Based Precomputation for Multi-Constrained Routing[J]. Acta Electronica Sinica, 2003, 31(8): 1173-1177. DOI：

摘要

作为下一代高速网络的核心问题之一

多约束的服务质量路由(QoSR)至今尚无有效算法

为此基于线性能量函数设计了预计算算法MEFPA.该算法将每个QoS度量的重要性均匀分成若干个等级

从而在多维QoS度量空间中构造出多个均匀分布的线性能量函数;算法通过能量函数将QoS链路状态转化成单一能量值

再使用Dijkstra算法计算最小能量树

最终产生QoS路由表.文章分析了多约束下的线性能量函数对算法性能的影响

给出了判定多维空间中QoS约束的可行区域和不可行区域的方法

最后基于这些理论为多约束QoSR问题给出了预计算算法.广泛深入的实验结果表明

高可扩展性、高性能、易实现的预计算算法MEFPA是一种值得在下一代网络中考虑的路由算法.

Abstract

As one of the most challenging problems in the upcoming next-generation high-speed networks

quality-of-service routing (QoSR) with multiple constraints has the NP-complete complexity.A precomputation algorithm

MEFPA

was proposed.This algorithm divides the significance of each QoS weight into multiple degrees

and constructs a number of linear energy functions (LEFs) distributed uniformly in the multi-dimensional QoS metric space.Using LEFs

it then converts different QoS weights to a single energy.At last

it uses Dijkstra's algorithm to create the least energy trees

based on which the QoS routing table is created.The performance of LEFs with constraints is analyzed

and the method is given to determine the feasible and unfeasible areas in the multi-dimensional QoS metric space for a QoS constraint.Then MEFPA for the multi-constrained QoS routing problem was introduce.Extensive simulations show that our easily implemented MEFPA is a promising precomputation algorithm to provide QoSR with high scalability and high performance in high-speed networks.

关键词

Keywords

references

Views

1374

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

An Adjustable Heuristic Algorithm for Multi-Constrained Routing Problem

Research on Scalability of Blockchain Based on Sharding: A Survey

Scalable Network Verification Technologies: State of the Art and Future

Related Author

LIU San-yang

QI Xiao-gang

XU Ke

CUI Yong

LIU Ting-ting

XU Jia

YE Fei

MA Peng-cheng

Related Institution

Department of Applied Mathematics,Xidian University

School of Computer Science, Nanjing University of Posts and Telecommunications

Department of Computer Science and Technology， Tsinghua University

Beijing National Research Center for Information Science and Technology

Zhongguancun Laboratory

⁰