Article(id=1329455921652150905, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1329455653363495339, articleNumber=null, orderNo=null, doi=10.7544/issn1000-1239.202220914, pmid=null, cstr=null, oa=null, hot=null, price=null, onlineType=0, articleFormat=0, articleType=null, articleTypeStr=null, receivedDate=1667404800000, receivedDateStr=2022-11-03, revisedDate=1681401600000, revisedDateStr=2023-04-14, acceptedDate=null, acceptedDateStr=null, onlineDate=1794896591818, onlineDateStr=2026-11-17, pubDate=1706803200000, pubDateStr=2024-02-02, doiRegisterDate=null, doiRegisterDateStr=null, onlineIssueDate=1794896591818, onlineIssueDateStr=2026-11-17, onlineJustAcceptDate=null, onlineJustAcceptDateStr=null, onlineFirstDate=null, onlineFirstDateStr=null, sourceXml=null, magXml=null, createTime=1794896591818, creator=13701087609, updateTime=1794896591818, updator=13701087609, issue=Issue{id=1329455653363495339, tenantId=1146029695717560320, journalId=1324759914146529478, year='2024', volume='61', issue='2', pageStart='273', pageEnd='538', issueExtLink='null', onlineDate='null', pubDate='1706803200000', pubDateStr='2024-02-02', beforeIssueId=null, nextIssueId=null, price=null, status=1, issueComplete=1, articleOrder=1, issueType=-1, specialIssue=null, createTime=1794896527853, creator='13701087609', updateTime=1794896527853, updator='13701087609', preIssue=null, nextIssue=null, articleTotal=null, ext=null, issueFiles=null, downloadFileDto=null}, startPage=529, endPage=538, ext={EN=ArticleExt(id=1329455921828311674, articleId=1329455921652150905, tenantId=1146029695717560320, journalId=1324759914146529478, language=EN, title=An Intra-Domain Routing Protection Algorithm Based on Forwarding Graph, columnId=1329419589001261979, journalTitle=Journal of Computer Research and Development, columnName=Network Technology, runingTitle=null, highlight=null, articleAbstract=

Currently, intra-domain routing protocols which are deployed on the Internet respond to network failures through a global convergence mechanism. In the process of routing convergence, a large number of data packets will be discarded, leading to network interruption. The industry proposes to use routing protection methods to solve the above problem. However, the existing routing protection methods have the following four problems: 1) they cannot cope with all possible single failures in the network; 2) they need the assistance of additional auxiliary mechanisms; 3) they do not support incremental deployment; 4) each node stores multiple backup next hops for each destination, increasing storage and computation costs. We propose an intra-domain routing protection algorithm based on forwarding graph (RPBFG) to solve the above four problems of existing routing protection algorithms. We first establish a routing protection model with the goal of maximizing the failure protection ratio and the constraint that the forwarding graph contains the reverse shortest path tree; then a genetic algorithm is proposed to construct a forwarding graph that satisfies the above goal; finally, the backup next hop of all nodes arriving at the destination node is calculated according to the constructed forwarding graph. We compare the performance of RPBFG, NPC, U-turn, MARA-MA and MARA-SPE in 11 real topologies, including failure protection ratio and path stretch. The experimental results show that RPBFG can deal with all possible single failures in the network, and that is to say the failure protection ratio of RPBFG is 100%, while the average failure protection ratio of NPC, U-turn, MARA-MA and MARA-SPE is 45.05%, 74.53%, 89.78% and 91.24% respectively. In the aspect of path stretch, RPBFG decreased by 0.11%, 0.72%, 37.79% and 36.26% respectively compared with NPC, U-turn, MARA-MA and MARA-SPE. The research results will help to promote the progress of Internet service providers in deploying intra-domain routing protection schemes in real networks.

, authors=Haijun Geng1, 2, 3, Zhuo Meng1, 3, Shanshan Yao1, 3, Jing Yang2, 3, Haotian Chi2, Xia Yin4, *, authorsList=Haijun Geng, Zhuo Meng, Shanshan Yao, Jing Yang, Haotian Chi, Xia Yin, authorCompany=null, correspAuthors=Xia Yin, authorNote=

born in 1983. PhD, associate professor. His main research interests include network architecture and routing algorithm

born in 1998. Master candidate. His main research interests include network architecture and routing algorithm

born in 1989. PhD, associate professor. Her main research interests include big data retrieval and pattern recognition

born in 1990. PhD, lecturer. Her main research interests include fuzzy systems and image reconstruction

born in 1990. PhD, lecturer. His main research interests include Internet of Things security, wireless security, and privacy protetion

born in 1972. PhD, professor, PhD supervisor. Her main research interests include future Internet architecture and protocol testing

, correspAuthorsNote=null, copyrightStatement=Copyright © 2024 Journal of Computer Research and Development. All rights reserved., copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=null, magXml=null, pdfUrl=null, pdf=null, pdfFileSize=null, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=null, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=null, mapNumber=null, fund=null), CN=ArticleExt(id=1329455923724137103, articleId=1329455921652150905, tenantId=1146029695717560320, journalId=1324759914146529478, language=CN, title=一种基于转发图的域内路由保护算法, columnId=1329419589143868317, journalTitle=计算机研究与发展, columnName=网络技术, runingTitle=null, highlight=null, articleAbstract=

业界提出利用路由保护算法来解决网络中的故障问题,然而已有的路由保护算法存在4个方面的问题:1)无法应对网络中所有可能的单故障情形;2)需要额外辅助机制的协助;3)不支持增量部署;4)每个结点存储多个到达目的地址的备份下一跳. 提出一种基于转发图的域内路由保护算法(an intra-domain routing protection algorithm based on forwarding graph, RPBFG)来解决这4个问题. 首先建立了以最大化故障保护率为目标、以转发图包含反向最短路径树为约束条件的路由保护模型;然后提出了利用遗传算法构造满足上述目标的转发图;最后根据构造的转发图计算出所有结点到达目的结点的备份下一跳. 在11个真实拓扑结构中比较了RPBFG,NPC,U-turn,MARA-MA,MARA-SPE在故障保护率和路径拉伸度的性能. 实验结果表明,RPBFG可以应对网络中所有可能的单故障;在平均路径拉伸度方面,RPBFG比NPC,U-turn,MARA-MA,MARA-SPE分别降低了0.11%,0.72%,37.79%,36.26%.

, authors=耿海军1, 2, 3, 孟卓1, 3, 姚姗姗1, 3, 杨静2, 3, 池浩田2, 尹霞4, *, authorsList=耿海军, 孟卓, 姚姗姗, 杨静, 池浩田, 尹霞, authorCompany=null, correspAuthors=尹霞, authorNote=

1983年生. 博士,副教授. 主要研究方向为网络体系结构、路由算法

1998年生. 硕士研究生. 主要研究方向为网络体系结构、路由算法

1989年生. 博士,副教授. 主要研究方向为大数据检索、模式识别

1990年生,博士,讲师. 主要研究方向为模糊系统、图像重建

1990年生. 博士,讲师. 主要研究方向为物联网安全、无线安全、隐私保护

1972年生. 博士,教授,博士生导师. 主要研究方向为未来互联网体系结构、协议测试

, correspAuthorsNote=
尹霞()
, copyrightStatement=版权所有 © 2024 计算机研究与发展编辑部, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=7n1Xrr9oypSumILlzLixbA==, magXml=Z3LBl82gNIESc68wsEmyxg==, pdfUrl=null, pdf=3E8qIaUKo/QCoFIwzSUn4A==, pdfFileSize=1166110, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=Xe7NJfbimxNjPbWm1RqhMA==, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=CwF0nSEVOdf9jlcC8C5x2w==, mapNumber=null, fund=null)}, authors=[Author(id=1329455924294562461, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=genghaijun@sxu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329455924441363105, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455924294562461, language=EN, stringName=Haijun Geng, firstName=Haijun, middleName=null, lastName=Geng, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1School of Computer and Information Technology, Shanxi University, Taiyuan 030006
2School of Automation and Software Engineering, Shanxi University, Taiyuan 030006
3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006, bio={"content":"

born in 1983. PhD, associate professor. His main research interests include network architecture and routing algorithm

"}, bioImg=null, bioContent=

born in 1983. PhD, associate professor. His main research interests include network architecture and routing algorithm

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329455924596552354, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455924294562461, language=CN, stringName=耿海军, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1山西大学计算机与信息技术学院 太原 030006
2山西大学自动化与软件学院 太原 030006
3山西大学大数据科学与产业研究院 太原 030006, bio={"img":"g91i49ioX37v5Yvs3P9SgQ==","content":"

1983年生. 博士,副教授. 主要研究方向为网络体系结构、路由算法

"}, bioImg=g91i49ioX37v5Yvs3P9SgQ==, bioContent=

1983年生. 博士,副教授. 主要研究方向为网络体系结构、路由算法

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329455923933852304, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=1, ext=[AuthorCompanyExt(id=1329455923942240913, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455923933852304, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer and Information Technology, Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455923946435218, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455923933852304, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1山西大学计算机与信息技术学院 太原 030006)]), AuthorCompany(id=1329455924017738387, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=2, ext=[AuthorCompanyExt(id=1329455924026126996, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924017738387, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2School of Automation and Software Engineering, Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455924034515605, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924017738387, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2山西大学自动化与软件学院 太原 030006)]), AuthorCompany(id=1329455924105818774, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=3, ext=[AuthorCompanyExt(id=1329455924114207383, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924105818774, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455924122595992, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924105818774, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3山西大学大数据科学与产业研究院 太原 030006)])]), Author(id=1329455924705604260, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329455924785296039, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455924705604260, language=EN, stringName=Zhuo Meng, firstName=Zhuo, middleName=null, lastName=Meng, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 3, address=1School of Computer and Information Technology, Shanxi University, Taiyuan 030006
3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006, bio={"content":"

born in 1998. Master candidate. His main research interests include network architecture and routing algorithm

"}, bioImg=null, bioContent=

born in 1998. Master candidate. His main research interests include network architecture and routing algorithm

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329455924839821992, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455924705604260, language=CN, stringName=孟卓, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 3, address=1山西大学计算机与信息技术学院 太原 030006
3山西大学大数据科学与产业研究院 太原 030006, bio={"img":"gRliuQdOONW2F39ZHKx/GA==","content":"

1998年生. 硕士研究生. 主要研究方向为网络体系结构、路由算法

"}, bioImg=gRliuQdOONW2F39ZHKx/GA==, bioContent=

1998年生. 硕士研究生. 主要研究方向为网络体系结构、路由算法

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329455923933852304, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=1, ext=[AuthorCompanyExt(id=1329455923942240913, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455923933852304, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer and Information Technology, Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455923946435218, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455923933852304, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1山西大学计算机与信息技术学院 太原 030006)]), AuthorCompany(id=1329455924105818774, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=3, ext=[AuthorCompanyExt(id=1329455924114207383, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924105818774, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455924122595992, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924105818774, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3山西大学大数据科学与产业研究院 太原 030006)])]), Author(id=1329455924898542250, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329455925011788461, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455924898542250, language=EN, stringName=Shanshan Yao, firstName=Shanshan, middleName=null, lastName=Yao, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 3, address=1School of Computer and Information Technology, Shanxi University, Taiyuan 030006
3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006, bio={"content":"

born in 1989. PhD, associate professor. Her main research interests include big data retrieval and pattern recognition

"}, bioImg=null, bioContent=

born in 1989. PhD, associate professor. Her main research interests include big data retrieval and pattern recognition

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329455925108257454, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455924898542250, language=CN, stringName=姚姗姗, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 3, address=1山西大学计算机与信息技术学院 太原 030006
3山西大学大数据科学与产业研究院 太原 030006, bio={"img":"+WLwuiwOmNigG9it/wEjeg==","content":"

1989年生. 博士,副教授. 主要研究方向为大数据检索、模式识别

"}, bioImg=+WLwuiwOmNigG9it/wEjeg==, bioContent=

1989年生. 博士,副教授. 主要研究方向为大数据检索、模式识别

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329455923933852304, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=1, ext=[AuthorCompanyExt(id=1329455923942240913, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455923933852304, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer and Information Technology, Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455923946435218, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455923933852304, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1山西大学计算机与信息技术学院 太原 030006)]), AuthorCompany(id=1329455924105818774, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=3, ext=[AuthorCompanyExt(id=1329455924114207383, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924105818774, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455924122595992, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924105818774, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3山西大学大数据科学与产业研究院 太原 030006)])]), Author(id=1329455925171172016, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329455925250863795, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455925171172016, language=EN, stringName=Jing Yang, firstName=Jing, middleName=null, lastName=Yang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, 3, address=2School of Automation and Software Engineering, Shanxi University, Taiyuan 030006
3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006, bio={"content":"

born in 1990. PhD, lecturer. Her main research interests include fuzzy systems and image reconstruction

"}, bioImg=null, bioContent=

born in 1990. PhD, lecturer. Her main research interests include fuzzy systems and image reconstruction

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329455925330555572, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455925171172016, language=CN, stringName=杨静, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, 3, address=2山西大学自动化与软件学院 太原 030006
3山西大学大数据科学与产业研究院 太原 030006, bio={"img":"B4/KQm9jWaof2nHguCbpWA==","content":"

1990年生,博士,讲师. 主要研究方向为模糊系统、图像重建

"}, bioImg=B4/KQm9jWaof2nHguCbpWA==, bioContent=

1990年生,博士,讲师. 主要研究方向为模糊系统、图像重建

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329455924017738387, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=2, ext=[AuthorCompanyExt(id=1329455924026126996, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924017738387, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2School of Automation and Software Engineering, Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455924034515605, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924017738387, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2山西大学自动化与软件学院 太原 030006)]), AuthorCompany(id=1329455924105818774, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=3, ext=[AuthorCompanyExt(id=1329455924114207383, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924105818774, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455924122595992, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924105818774, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3山西大学大数据科学与产业研究院 太原 030006)])]), Author(id=1329455925393470134, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329455925477356216, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455925393470134, language=EN, stringName=Haotian Chi, firstName=Haotian, middleName=null, lastName=Chi, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, address=2School of Automation and Software Engineering, Shanxi University, Taiyuan 030006, bio={"content":"

born in 1990. PhD, lecturer. His main research interests include Internet of Things security, wireless security, and privacy protetion

"}, bioImg=null, bioContent=

born in 1990. PhD, lecturer. His main research interests include Internet of Things security, wireless security, and privacy protetion

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329455925603185337, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455925393470134, language=CN, stringName=池浩田, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, address=2山西大学自动化与软件学院 太原 030006, bio={"img":"LQXOKe5c0wX7LOgUAppVgg==","content":"

1990年生. 博士,讲师. 主要研究方向为物联网安全、无线安全、隐私保护

"}, bioImg=LQXOKe5c0wX7LOgUAppVgg==, bioContent=

1990年生. 博士,讲师. 主要研究方向为物联网安全、无线安全、隐私保护

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329455924017738387, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=2, ext=[AuthorCompanyExt(id=1329455924026126996, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924017738387, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2School of Automation and Software Engineering, Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455924034515605, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924017738387, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2山西大学自动化与软件学院 太原 030006)])]), Author(id=1329455925670294203, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, orderNo=5, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=yxia@tsinghua.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1329455925745791677, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455925670294203, language=EN, stringName=Xia Yin, firstName=Xia, middleName=null, lastName=Yin, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=4, *, address=4Department of Computer Science and Technology, Tsinghua University, Beijing 100084, bio={"content":"

born in 1972. PhD, professor, PhD supervisor. Her main research interests include future Internet architecture and protocol testing

"}, bioImg=null, bioContent=

born in 1972. PhD, professor, PhD supervisor. Her main research interests include future Internet architecture and protocol testing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329455925812900542, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455925670294203, language=CN, stringName=尹霞, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=4, *, address=4清华大学计算机科学与技术系 北京 100084, bio={"img":"4xpKtiA/eatWJJhPdXPM4w==","content":"

1972年生. 博士,教授,博士生导师. 主要研究方向为未来互联网体系结构、协议测试

"}, bioImg=4xpKtiA/eatWJJhPdXPM4w==, bioContent=

1972年生. 博士,教授,博士生导师. 主要研究方向为未来互联网体系结构、协议测试

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329455924189704857, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=4, ext=[AuthorCompanyExt(id=1329455924198093466, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924189704857, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=4Department of Computer Science and Technology, Tsinghua University, Beijing 100084), AuthorCompanyExt(id=1329455924210676379, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924189704857, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=4清华大学计算机科学与技术系 北京 100084)])])], keywords=[Keyword(id=1329455925917758143, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=EN, orderNo=1, keyword=routing protection), Keyword(id=1329455925980672704, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=EN, orderNo=2, keyword=network failure), Keyword(id=1329455926047781569, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=EN, orderNo=3, keyword=failure protection ratio), Keyword(id=1329455926114890434, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=EN, orderNo=4, keyword=path stretch), Keyword(id=1329455926181999299, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=EN, orderNo=5, keyword=directed acyclic graph), Keyword(id=1329455926257496772, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=EN, orderNo=6, keyword=forwarding graph), Keyword(id=1329455926324605637, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=CN, orderNo=1, keyword=路由保护), Keyword(id=1329455926391714502, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=CN, orderNo=2, keyword=网络故障), Keyword(id=1329455926450434759, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=CN, orderNo=3, keyword=故障保护率), Keyword(id=1329455926513349320, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=CN, orderNo=4, keyword=路径拉伸度), Keyword(id=1329455926572069577, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=CN, orderNo=5, keyword=有向无环图), Keyword(id=1329455926634984138, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=CN, orderNo=6, keyword=转发图)], refs=[Reference(id=1329455928602112737, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=1, rfOrder=0, authorNames=null, journalName=null, refType=null, unstructuredReference=Moy J. RFC 2328 OSPF Version 2 [S/OL]. The Internet Engineering Task Force, 1998[2022-09-06].https://www.ietf.org/rfc/rfc2328, articleTitle=null, refAbstract=null), Reference(id=1329455928681804514, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=2, rfOrder=1, authorNames=null, journalName=null, refType=null, unstructuredReference=David O. RFC 1142 OSI IS-IS Intra-domain Routing Protocol [S/OL]. The Internet Engineering Task Force, 1990[2022-08-12].https://www.ietf.org/rfc/rfc1142, articleTitle=null, refAbstract=null), Reference(id=1329455928769884899, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=3, rfOrder=2, authorNames=null, journalName=null, refType=null, unstructuredReference=Duijn I V, Jensen P G, Jensen J S, et al. Automata-theoretic approach to verification of MPLS networks under link failures[J]. IEEE/ACM Transactions on Networking, 2022, 30(2): 766−781, articleTitle=null, refAbstract=null), Reference(id=1329455928983794404, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=3, authorNames=null, journalName=null, refType=null, unstructuredReference=Foerster K T, Kamisiski A, Pignolet Y A, et al. Improved fast rerouting using postprocessing[J]. IEEE Transactions on Dependable and Secure Computing, 2022, 19(1): 537−550, articleTitle=null, refAbstract=null), Reference(id=1329455929055097573, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=4, authorNames=null, journalName=null, refType=null, unstructuredReference=Yang Ze, Yeung K L. SDN candidate selection in hybrid IP/SDN networks for single link failure protection[J]. IEEE/ACM Transactions on Networking, 2020, 28(1): 312−321, articleTitle=null, refAbstract=null), Reference(id=1329455929130595046, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=5, authorNames=null, journalName=null, refType=null, unstructuredReference=Geng Haijun, Zhang Han, Shi Xingang, et al. Efficient computation of loop-free alternates[J]. Journal of Network and Computer Applications, 2020, 151: 1−12, articleTitle=null, refAbstract=null), Reference(id=1329455929197703911, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=7, rfOrder=6, authorNames=null, journalName=null, refType=null, unstructuredReference=Jia Xuya, Li Dan, Zhu Jing, et al. Metro: An efficient traffic fast rerouting scheme with low overhead[J]. IEEE/ACM Transactions on Networking, 2019, 27(5): 2015−2027, articleTitle=null, refAbstract=null), Reference(id=1329455929260618472, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=8, rfOrder=7, authorNames=null, journalName=null, refType=null, unstructuredReference=Borokhovich M, Pignolet Y A, Schmid S, et al. Load-optimal local fast rerouting for dense networks[J]. IEEE/ACM Transactions on Networking, 2018, 26(6): 2583−2597, articleTitle=null, refAbstract=null), Reference(id=1329455929327727337, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=8, authorNames=null, journalName=null, refType=null, unstructuredReference=Yang Yuan, Xu Minwei, Li Qi. Fast rerouting against multi-link failures without topology constraint[J]. IEEE/ACM Transactions on Networking, 2018, 26(1): 384−397, articleTitle=null, refAbstract=null), Reference(id=1329455929390641898, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=9, authorNames=null, journalName=null, refType=null, unstructuredReference=Shukla A, Foerster K T. Shortcutting fast failover routes in the data plane [C] //Proc of the 16th Symp on Architectures for Networking and Communications Systems. Piscataway, NJ: IEEE, 2021: 15−22, articleTitle=null, refAbstract=null), Reference(id=1329455929457750763, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=11, rfOrder=10, authorNames=null, journalName=null, refType=null, unstructuredReference=Atlas A, Zinin A. RFC 5286 Basic Specification for IP Fast Reroute: Loop-free Alternates [S/OL]. The Internet Engineering Task Force, 2008[2022-10-08].https://www.ietf.org/rfc/rfc5286, articleTitle=null, refAbstract=null), Reference(id=1329455929533248236, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=11, authorNames=null, journalName=null, refType=null, unstructuredReference=耿海军,施新刚,王之梁,等. 基于最小路径交叉度的域内路由保护方案[J]. 软件学报,2020,31(5):1536−1548, articleTitle=null, refAbstract=null), Reference(id=1329455929600357101, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=12, authorNames=null, journalName=null, refType=null, unstructuredReference=Geng Haijun, Shi Xingang, Wang Zhiliang, et al. Intra-domain routing protection scheme based on minimum intersection paths[J]. Journal of Software, 2020, 31(5): 1536−1548 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1329455929663271662, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=13, rfOrder=13, authorNames=null, journalName=null, refType=null, unstructuredReference=Yang Xiaowei, Wetherall D. Source selectable path diversity via routing deflections[J]. Computer Communication Review, 2006, 36(4): 159−170, articleTitle=null, refAbstract=null), Reference(id=1329455929751352047, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=14, rfOrder=14, authorNames=null, journalName=null, refType=null, unstructuredReference=Ohara Y , Imahori S , Meter R V. MARA: Maximum alternative routing algorithm[C] //Proc of the 28th Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2009: 298−306, articleTitle=null, refAbstract=null), Reference(id=1329455929814266608, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=15, rfOrder=15, authorNames=null, journalName=null, refType=null, unstructuredReference=Vo H Q, Lysne O, Kvalbein A. Routing with Joker links for maximized robustness[C/OL] //Proc of the 12th Int Conf on IFIP Networking Conf. Piscataway, NJ: IEEE, 2013[202-10-17].https://ieeexplore.ieee.org/document/6663494, articleTitle=null, refAbstract=null), Reference(id=1329455929872986865, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=16, rfOrder=16, authorNames=null, journalName=null, refType=null, unstructuredReference=Schneider K, Zhang Beichuang, Benmohamed L. Hop-by-hop multipath routing: Choosing the right nexthop set[C] //Proc of the 39th Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2020: 2273−2282, articleTitle=null, refAbstract=null), Reference(id=1329455929944290034, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=17, rfOrder=17, authorNames=null, journalName=null, refType=null, unstructuredReference=Menth M, Hartmann M, Martin R, et al. Loop-free alternates and not-via addresses: A proper combination for IP fast reroute?[J]. Computer Networks, 2010, 54(8): 1300−1315, articleTitle=null, refAbstract=null), Reference(id=1329455930028176115, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=18, rfOrder=18, authorNames=null, journalName=null, refType=null, unstructuredReference=Anbiah A, Sivalingam K M. Efficient failure recovery techniques for segment-routed networks[J]. Computer Communications, 2022, 182: 1−12, articleTitle=null, refAbstract=null), Reference(id=1329455930095284980, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=19, rfOrder=19, authorNames=null, journalName=null, refType=null, unstructuredReference=Markopoulou A, Iannaccone G, Bhattacharyya S, et al. Characterization of failures in an operational IP backbone network[J]. IEEE/ACM Transactions on Networking, 2008, 16(4): 749−762, articleTitle=null, refAbstract=null), Reference(id=1329455930166588149, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=20, rfOrder=20, authorNames=null, journalName=null, refType=null, unstructuredReference=Chiesa M, Kamisinski A, Rak J, et al. A survey of fast-recovery mechanisms in packet-switched networks[J]. IEEE Communications Surveys and Tutorials, 2021, 23(2): 1253−1301, articleTitle=null, refAbstract=null), Reference(id=1329455930229502710, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=21, rfOrder=21, authorNames=null, journalName=null, refType=null, unstructuredReference=Kwong K W, Gao Lixin, Guérin R. On the feasibility and efficacy of protection routing in IP networks[J]. IEEE/ACM Transactions on Networking, 2011, 19(5): 1543−1556, articleTitle=null, refAbstract=null), Reference(id=1329455930284028663, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=22, rfOrder=22, authorNames=null, journalName=null, refType=null, unstructuredReference=Rétvári G, Csikor L, Tapolcai J, et al. Optimizing IGP link costs for improving IP-level resilience with loop-free alternates[J]. Computer Communications, 2013, 36(6): 645−655, articleTitle=null, refAbstract=null), Reference(id=1329455930351137528, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=23, rfOrder=23, authorNames=null, journalName=null, refType=null, unstructuredReference=Rétvári G, Tapolcai J, Enyedi G, et al. IP fast reroute: Loop free alternates revisited[C] //Proc of the 30th Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2011: 2948−2956, articleTitle=null, refAbstract=null), Reference(id=1329455930414052089, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=24, rfOrder=24, authorNames=null, journalName=null, refType=null, unstructuredReference=Francois P, Bonaventure O. An evaluation of IP-based fast reroute techniques[C] //Proc of the ACM Conf on Emerging Network Experiment and Technology. New York: ACM, 2005: 244−245, articleTitle=null, refAbstract=null), Reference(id=1329455930481160954, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=25, rfOrder=25, authorNames=null, journalName=null, refType=null, unstructuredReference=Enyedi G, Szilágyi P, Rétvári G, et al. IP fast reroute: Lightweight not-via without additional addresses[C] //Proc of the 28th Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2009: 2771−2775, articleTitle=null, refAbstract=null), Reference(id=1329455930539881211, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=26, rfOrder=26, authorNames=null, journalName=null, refType=null, unstructuredReference=Zheng Jiaqi, Xu Hong, Zhu Xiaojun, et al. We've got you covered: Failure recovery with backup tunnels in traffic engineering[C/OL] //Proc of the 24th Int Conf on Network Protocols. Piscataway, NJ: IEEE, 2016[2022-09-18]. https://ieeexplore.ieee.org/document/7784449, articleTitle=null, refAbstract=null), Reference(id=1329455930611184380, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=27, rfOrder=27, authorNames=null, journalName=null, refType=null, unstructuredReference=Kvalbein A, Hansen A F, Čičić T, et al. Fast IP network recovery using multiple routing configurations[C] //Proc of the 25th Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2006: 1677−1687, articleTitle=null, refAbstract=null), Reference(id=1329455930678293245, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=28, rfOrder=28, authorNames=null, journalName=null, refType=null, unstructuredReference=Lakshminarayanan K, Caesar M, Rangan M, et al. Achieving convergence-free routing using failure-carrying packets[J]. Computer Communication Review, 2007, 37(4): 241−252, articleTitle=null, refAbstract=null), Reference(id=1329455930741207806, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=29, rfOrder=29, authorNames=null, journalName=null, refType=null, unstructuredReference=周明华,汪国昭. 基于遗传算法的B样条曲线和Bézier曲线的最小二乘拟合[J]. 计算机研究与发展,2005,42(1):134−143, articleTitle=null, refAbstract=null), Reference(id=1329455930808316671, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=29, rfOrder=30, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhou Minghua, Wang Guozhao. Genetic algorithm based least square fitting of B-spline and Bézier curves[J]. Journal of Computer Research and Development, 2005, 42(1): 134−143 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1329455930867036928, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=30, rfOrder=31, authorNames=null, journalName=null, refType=null, unstructuredReference=University of Adelaide. The Internet topology zoo [EB/OL]. [2022-09-07]. http://www.topology-zoo.org/, articleTitle=null, refAbstract=null)], funds=null, companyList=[AuthorCompany(id=1329455923933852304, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=1, ext=[AuthorCompanyExt(id=1329455923942240913, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455923933852304, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer and Information Technology, Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455923946435218, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455923933852304, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1山西大学计算机与信息技术学院 太原 030006)]), AuthorCompany(id=1329455924017738387, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=2, ext=[AuthorCompanyExt(id=1329455924026126996, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924017738387, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2School of Automation and Software Engineering, Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455924034515605, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924017738387, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2山西大学自动化与软件学院 太原 030006)]), AuthorCompany(id=1329455924105818774, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=3, ext=[AuthorCompanyExt(id=1329455924114207383, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924105818774, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455924122595992, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924105818774, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3山西大学大数据科学与产业研究院 太原 030006)]), AuthorCompany(id=1329455924189704857, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=4, ext=[AuthorCompanyExt(id=1329455924198093466, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924189704857, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=4Department of Computer Science and Technology, Tsinghua University, Beijing 100084), AuthorCompanyExt(id=1329455924210676379, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924189704857, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=4清华大学计算机科学与技术系 北京 100084)])], figs=[ArticleFig(id=1329455926785979083, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=EN, label=Figure 1, caption=Network topology structure, figureFileSmall=eUTsAlWQEIKomruwW03Efg==, figureFileBig=Xe7NJfbimxNjPbWm1RqhMA==, tableContent=null), ArticleFig(id=1329455926844699340, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=CN, label=图1, caption=网络拓扑结构, figureFileSmall=eUTsAlWQEIKomruwW03Efg==, figureFileBig=Xe7NJfbimxNjPbWm1RqhMA==, tableContent=null), ArticleFig(id=1329455927008277197, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=EN, label=Figure 2, caption=Reverse shortest path tree, figureFileSmall=dDHC+6TwM2x3FF/PvN0HFA==, figureFileBig=0PF1QdckeFhRor7CBIBsjg==, tableContent=null), ArticleFig(id=1329455927066997454, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=CN, label=图2, caption=反向最短路径树, figureFileSmall=dDHC+6TwM2x3FF/PvN0HFA==, figureFileBig=0PF1QdckeFhRor7CBIBsjg==, tableContent=null), ArticleFig(id=1329455927121523407, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=EN, label=Figure 3, caption=Forwarding graph, figureFileSmall=YCu71Rt7/W5XxWlVuBxbDA==, figureFileBig=t02a0rLpdkJig9oqDH/K2w==, tableContent=null), ArticleFig(id=1329455927192826576, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=CN, label=图3, caption=转发图, figureFileSmall=YCu71Rt7/W5XxWlVuBxbDA==, figureFileBig=t02a0rLpdkJig9oqDH/K2w==, tableContent=null), ArticleFig(id=1329455927276712657, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=EN, label=Figure 4, caption=Failure protection ratio of different algorithms in real topologies, figureFileSmall=89U8+aLfKsjdI0c5DWeoMA==, figureFileBig=Nxzi+TBi94Lfd6ZpqksA/g==, tableContent=null), ArticleFig(id=1329455927339627218, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=CN, label=图4, caption=不同算法在真实拓扑中的故障保护率, figureFileSmall=89U8+aLfKsjdI0c5DWeoMA==, figureFileBig=Nxzi+TBi94Lfd6ZpqksA/g==, tableContent=null), ArticleFig(id=1329455927457067731, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=EN, label=Table 1, caption=

Comparison of Routing Protection Algorithms

, figureFileSmall=null, figureFileBig=null, tableContent=
算法是否是链路
状态路由协议
是否支持
逐跳转发
是否支持100%
的单故障保护
OSPF[1]√√×
LFA[11]√√×
MARA-MA[14]√√×
MARA-SPE[14]√√×
JNHOR-SP[15]√√×
LFID[16]√√×
SR[18]××√
U-turn[24]√√×
Not-Via[25]××√
MRC[27]××√
FCP[28]××√
RPBFG
(本文)
√√√
), ArticleFig(id=1329455927536759508, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=CN, label=表1, caption=

路由保护算法的比较

, figureFileSmall=null, figureFileBig=null, tableContent=
算法是否是链路
状态路由协议
是否支持
逐跳转发
是否支持100%
的单故障保护
OSPF[1]√√×
LFA[11]√√×
MARA-MA[14]√√×
MARA-SPE[14]√√×
JNHOR-SP[15]√√×
LFID[16]√√×
SR[18]××√
U-turn[24]√√×
Not-Via[25]××√
MRC[27]××√
FCP[28]××√
RPBFG
(本文)
√√√
), ArticleFig(id=1329455927616451285, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=EN, label=Table 2, caption=

Symbols Defined in Our paper

, figureFileSmall=null, figureFileBig=null, tableContent=
符号含义
G=(V, E)网络拓扑图
V网络中结点(路由器)的集合
E网络中边(链路)的集合
r(d)目的地址为d的反向最短路径树
G(d)目的地址为d的转发图
P(v, G(d))转发图G(d)的故障保护率
bestn(v, d)结点v到结点d的最优下一跳
backn(v, d)结点v到结点d的备份下一跳
), ArticleFig(id=1329455927683560150, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=CN, label=表2, caption=

本文定义的符号

, figureFileSmall=null, figureFileBig=null, tableContent=
符号含义
G=(V, E)网络拓扑图
V网络中结点(路由器)的集合
E网络中边(链路)的集合
r(d)目的地址为d的反向最短路径树
G(d)目的地址为d的转发图
P(v, G(d))转发图G(d)的故障保护率
bestn(v, d)结点v到结点d的最优下一跳
backn(v, d)结点v到结点d的备份下一跳
), ArticleFig(id=1329455927746474711, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=EN, label=Table 3, caption=

Real Network Topology

, figureFileSmall=null, figureFileBig=null, tableContent=
网络拓扑结点的数量边的数量
Abilene1114
Ans1724
Arpanet197191822
Arpanet197232427
Arpanet197282932
AttMpls2556
Belnet20041834
Cernet1416
Agis1621
NJLATA1123
USLD2845
), ArticleFig(id=1329455927805194968, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=CN, label=表3, caption=

真实网络拓扑

, figureFileSmall=null, figureFileBig=null, tableContent=
网络拓扑结点的数量边的数量
Abilene1114
Ans1724
Arpanet197191822
Arpanet197232427
Arpanet197282932
AttMpls2556
Belnet20041834
Cernet1416
Agis1621
NJLATA1123
USLD2845
), ArticleFig(id=1329455927880692441, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=EN, label=Table 4, caption=

Comparison Result of Path Stretch for NPC and RPBFG

, figureFileSmall=null, figureFileBig=null, tableContent=
网络拓扑NPCRPBFG(本文)
平均值方差平均值方差
Abilene1.00420.03341.00270.0208
Ans1.00190.02051.00150.0191
Arpanet197191.00080.01251.00060.0110
Arpanet197231.00020.00441.00010.0041
Arpanet197281.00000.00091.00000.0010
AttMpls1.00290.02691.00040.0121
Belnet20041.00000.00001.00000.0000
Cernet1.00000.00001.00000.0000
Agis1.00120.01651.00200.0269
NJLATA1.00680.04271.00020.0026
USLD1.00340.02701.00180.0201
), ArticleFig(id=1329455928023298778, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=CN, label=表4, caption=

NPC和PBFG路径拉伸度比较结果

, figureFileSmall=null, figureFileBig=null, tableContent=
网络拓扑NPCRPBFG(本文)
平均值方差平均值方差
Abilene1.00420.03341.00270.0208
Ans1.00190.02051.00150.0191
Arpanet197191.00080.01251.00060.0110
Arpanet197231.00020.00441.00010.0041
Arpanet197281.00000.00091.00000.0010
AttMpls1.00290.02691.00040.0121
Belnet20041.00000.00001.00000.0000
Cernet1.00000.00001.00000.0000
Agis1.00120.01651.00200.0269
NJLATA1.00680.04271.00020.0026
USLD1.00340.02701.00180.0201
), ArticleFig(id=1329455928094601947, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=EN, label=Table 5, caption=

Comparison Result of Path Stretch for U-turn and RPBFG

, figureFileSmall=null, figureFileBig=null, tableContent=
网络拓扑U-turnRPBFG(本文)
平均值方差平均值方差
Abilene1.02060.10771.01160.0677
Ans1.01980.09711.01190.0736
Arpanet197191.01530.07681.01230.0689
Arpanet197231.00970.05581.00960.0562
Arpanet197281.00320.03091.00390.0408
AttMpls1.02160.15731.00160.0258
Belnet20041.00790.09771.00000.0000
Cernet1.01430.08771.01430.0877
Agis1.01390.08711.01140.0727
NJLATA1.02260.12371.00010.0022
USLD1.01550.08061.00690.0469
), ArticleFig(id=1329455928165905116, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=CN, label=表5, caption=

U-turn和RPBFG路径拉伸度比较结果

, figureFileSmall=null, figureFileBig=null, tableContent=
网络拓扑U-turnRPBFG(本文)
平均值方差平均值方差
Abilene1.02060.10771.01160.0677
Ans1.01980.09711.01190.0736
Arpanet197191.01530.07681.01230.0689
Arpanet197231.00970.05581.00960.0562
Arpanet197281.00320.03091.00390.0408
AttMpls1.02160.15731.00160.0258
Belnet20041.00790.09771.00000.0000
Cernet1.01430.08771.01430.0877
Agis1.01390.08711.01140.0727
NJLATA1.02260.12371.00010.0022
USLD1.01550.08061.00690.0469
), ArticleFig(id=1329455928245596893, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=EN, label=Table 6, caption=

Comparison Result of Path Stretch for MARA-MA and RPBFG

, figureFileSmall=null, figureFileBig=null, tableContent=
网络拓扑MARA-MARPBFG(本文)
平均值方差平均值方差
Abilene1.57511.37491.01240.0737
Ans1.65281.11851.00830.0599
Arpanet197191.29890.57741.01890.0970
Arpanet197231.36340.73511.01880.0939
Arpanet197281.37670.85561.03110.1455
AttMpls2.23321.14131.00180.0275
Belnet20041.25870.27521.00000.0000
Cernet1.67481.33871.01360.0925
Agis1.40220.62731.00800.0616
NJLATA1.76280.82021.00030.0045
USLD2.27501.91011.00580.0415
), ArticleFig(id=1329455928329482974, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=CN, label=表6, caption=

MARA-MA和RPBFG路径拉伸度比较结果

, figureFileSmall=null, figureFileBig=null, tableContent=
网络拓扑MARA-MARPBFG(本文)
平均值方差平均值方差
Abilene1.57511.37491.01240.0737
Ans1.65281.11851.00830.0599
Arpanet197191.29890.57741.01890.0970
Arpanet197231.36340.73511.01880.0939
Arpanet197281.37670.85561.03110.1455
AttMpls2.23321.14131.00180.0275
Belnet20041.25870.27521.00000.0000
Cernet1.67481.33871.01360.0925
Agis1.40220.62731.00800.0616
NJLATA1.76280.82021.00030.0045
USLD2.27501.91011.00580.0415
), ArticleFig(id=1329455928396591839, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=EN, label=Table 7, caption=

Comparison Result of Path Stretch for MARA-SPE and RPBFG

, figureFileSmall=null, figureFileBig=null, tableContent=
网络拓扑MARA-SPERPBFG(本文)
平均值方差平均值方差
Abilene1.56871.00681.02470.1066
Ans1.56041.00551.00980.0648
Arpanet197191.19710.47111.01240.0767
Arpanet197231.23040.44121.02090.0984
Arpanet197281.27540.74571.02800.1383
AttMpls2.17651.02431.00240.0310
Belnet20041.36480.42431.00000.0000
Cernet1.71561.42561.01340.0905
Agis1.48580.70401.01100.0744
NJLATA1.74420.80131.00030.0045
USLD2.14111.67961.00560.0403
), ArticleFig(id=1329455928476283616, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, language=CN, label=表7, caption=

MARA-SPE和RPBFG路径拉伸度比较结果

, figureFileSmall=null, figureFileBig=null, tableContent=
网络拓扑MARA-SPERPBFG(本文)
平均值方差平均值方差
Abilene1.56871.00681.02470.1066
Ans1.56041.00551.00980.0648
Arpanet197191.19710.47111.01240.0767
Arpanet197231.23040.44121.02090.0984
Arpanet197281.27540.74571.02800.1383
AttMpls2.17651.02431.00240.0310
Belnet20041.36480.42431.00000.0000
Cernet1.71561.42561.01340.0905
Agis1.48580.70401.01100.0744
NJLATA1.74420.80131.00030.0045
USLD2.14111.67961.00560.0403
)], attaches=null, journal=Journal(id=1324759606947315908, delFlag=0, nameCn=计算机研究与发展, nameEn=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, issn=1000-1239, eissn=null, cn=11-1777/TP, coden=null, periodic=0, language=CN, oaType=null, ccby=null, superviseOffice=null, ownerOffice=null, pubOffice=null, editorOffice=null, officeType=null, aims=null, clcCode=null, officeProv=null, officeCity=null, officeAddr=null, officeZip=null, officeEmail=null, officePhone=null, editDirector=null, officeDirector=null, officeDirectorPhone=null, officeStaffNum=null, officeEmpNum=null, coverPicUrl=k2l8zgqwstuxxevFX2qxVA==, journalPrice=null, startedYear=null, abbrevIsoEn=Journal of Computer Research and Development, journalRemark=null, publicationField=null, createdTime=1793776903141, updatedTime=1793850698612, createdBy=18614031015, updatedBy=13701087609, firstLetterCn=J, firstLetterEn=J, subjectCode=Electronic Information, subjectName=null, subjectCodeEn=Electronic Information, subjectNameEn=null, picCn=k2l8zgqwstuxxevFX2qxVA==, picEn=r6k0Ry+RD+c/VXj5QarmDw==, jcr=null, cjcr=null, exts=[JournalExt(id=1325069127710286688, language=CN, name=计算机研究与发展, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698640, updatedTime=1793850698640, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""}), JournalExt(id=1325069127777395553, language=EN, name=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698656, updatedTime=1793850698656, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""})], databaseList=null, tenantJournalId=1324759914146529478, websiteList=[Website(id=1325070300139892771, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN, language=CN, createTime=1793850978169, createBy=18614031015, updateTime=1793851040259, updateBy=18614031015, name=计算机研究与发展-中文, tplId=1146099689490845704, title=计算机研究与发展, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070893751349360, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=articleTextType, value=kx, createTime=1793851119697, updateTime=1793851119697, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893730377837, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=banner, value=null, createTime=1793851119692, updateTime=1793851119692, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893772320883, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=grayFlag, value=0, createTime=1793851119702, updateTime=1793851119702, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893721989228, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851119690, updateTime=1793851119690, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893784903797, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=minRunFlag, value=0, createTime=1793851119705, updateTime=1793851119705, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893742960751, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic, createTime=1793851119695, updateTime=1793851119695, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893780709492, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=silenceFlag, value=0, createTime=1793851119704, updateTime=1793851119704, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893738766446, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_cn_619/, createTime=1793851119694, updateTime=1793851119694, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893755543665, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeColor, value=null, createTime=1793851119698, updateTime=1793851119698, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893763932274, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeStyle, value=null, createTime=1793851119700, updateTime=1793851119700, creator=18614031015, updator=18614031015)]), Website(id=1325070300580294698, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN, language=EN, createTime=1793850978274, createBy=18614031015, updateTime=1793851036638, updateBy=18614031015, name=计算机研究与发展-英文, tplId=1146101810881728533, title=Journal of Computer Research and Development, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070925288321148, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=articleTextType, value=kx, createTime=1793851127216, updateTime=1793851127216, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925263155321, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=banner, value=null, createTime=1793851127210, updateTime=1793851127210, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925309292671, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=grayFlag, value=0, createTime=1793851127221, updateTime=1793851127221, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925254766712, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851127208, updateTime=1793851127208, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925326069889, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=minRunFlag, value=0, createTime=1793851127225, updateTime=1793851127225, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925279932539, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic, createTime=1793851127214, updateTime=1793851127214, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925317681280, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=silenceFlag, value=0, createTime=1793851127223, updateTime=1793851127223, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925271543930, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_en_623/, createTime=1793851127212, updateTime=1793851127212, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925292515453, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeColor, value=null, createTime=1793851127217, updateTime=1793851127217, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925300904062, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeStyle, value=null, createTime=1793851127219, updateTime=1793851127219, creator=18614031015, updator=18614031015)])], journalTitle=计算机研究与发展, weixinUrl=null, journalUrl=https://crad.ict.ac.cn/, iacademicId=null, status=1, seqNo=null, journalTitleEn=Journal of Computer Research and Development, journalPhotoCn=k2l8zgqwstuxxevFX2qxVA==, journalPhotoEn=r6k0Ry+RD+c/VXj5QarmDw==, journalFirstLetter=J, journalRecommend=null, journalNew=null, journalCollection=null, jcrJf=null, cjcrJf=null, jcrJfStr=null, cjcrJfStr=null, submissionFirstDecision=null, sciSubjectClassification=null, casSubjectClassification=null, citeScore=null, totalCitationFrequency=null, icpCode=null, psCode=null, advertisingLicenseCode=null, copyrightInformation=null, country=null, option=, provinceCode=null, provinceName=null, collectFlag=false, interPubPlatform=, interPubPlatformUrl=null), detailUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202220914, detailUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202220914, pdfUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/PDF/10.7544/issn1000-1239.202220914, pdfUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/PDF/10.7544/issn1000-1239.202220914, aliStartDate=0, aliEndDate=0, collectionFlag=false, citedCount=null, citedUrl=null, previewStatus=0, delFlag=0, hasFullText=1, orderTime=1706803200000, fullTextJson=null, articleText=null, reference=null)
收藏切换
一种基于转发图的域内路由保护算法
耿海军 1, 2, 3 , 孟卓 1, 3 , 姚姗姗 1, 3 , 杨静 2, 3 , 池浩田 2 , 尹霞 4, *
计算机研究与发展 | 网络技术 2024,61(2): 529-538
收起
收藏切换
计算机研究与发展 |网络技术 2024 , 61 (2) : 529 -538
一种基于转发图的域内路由保护算法
全屏
[Author(id=1329455924294562461, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=genghaijun@sxu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329455924441363105, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455924294562461, language=EN, stringName=Haijun Geng, firstName=Haijun, middleName=null, lastName=Geng, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1School of Computer and Information Technology, Shanxi University, Taiyuan 030006
2School of Automation and Software Engineering, Shanxi University, Taiyuan 030006
3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006, bio={"content":"

born in 1983. PhD, associate professor. His main research interests include network architecture and routing algorithm

"}, bioImg=null, bioContent=

born in 1983. PhD, associate professor. His main research interests include network architecture and routing algorithm

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329455924596552354, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455924294562461, language=CN, stringName=耿海军, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1山西大学计算机与信息技术学院 太原 030006
2山西大学自动化与软件学院 太原 030006
3山西大学大数据科学与产业研究院 太原 030006, bio={"img":"g91i49ioX37v5Yvs3P9SgQ==","content":"

1983年生. 博士,副教授. 主要研究方向为网络体系结构、路由算法

"}, bioImg=g91i49ioX37v5Yvs3P9SgQ==, bioContent=

1983年生. 博士,副教授. 主要研究方向为网络体系结构、路由算法

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329455923933852304, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=1, ext=[AuthorCompanyExt(id=1329455923942240913, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455923933852304, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer and Information Technology, Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455923946435218, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455923933852304, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1山西大学计算机与信息技术学院 太原 030006)]), AuthorCompany(id=1329455924017738387, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=2, ext=[AuthorCompanyExt(id=1329455924026126996, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924017738387, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2School of Automation and Software Engineering, Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455924034515605, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924017738387, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2山西大学自动化与软件学院 太原 030006)]), AuthorCompany(id=1329455924105818774, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=3, ext=[AuthorCompanyExt(id=1329455924114207383, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924105818774, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455924122595992, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924105818774, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3山西大学大数据科学与产业研究院 太原 030006)])]), Author(id=1329455924705604260, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329455924785296039, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455924705604260, language=EN, stringName=Zhuo Meng, firstName=Zhuo, middleName=null, lastName=Meng, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 3, address=1School of Computer and Information Technology, Shanxi University, Taiyuan 030006
3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006, bio={"content":"

born in 1998. Master candidate. His main research interests include network architecture and routing algorithm

"}, bioImg=null, bioContent=

born in 1998. Master candidate. His main research interests include network architecture and routing algorithm

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329455924839821992, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455924705604260, language=CN, stringName=孟卓, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 3, address=1山西大学计算机与信息技术学院 太原 030006
3山西大学大数据科学与产业研究院 太原 030006, bio={"img":"gRliuQdOONW2F39ZHKx/GA==","content":"

1998年生. 硕士研究生. 主要研究方向为网络体系结构、路由算法

"}, bioImg=gRliuQdOONW2F39ZHKx/GA==, bioContent=

1998年生. 硕士研究生. 主要研究方向为网络体系结构、路由算法

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329455923933852304, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=1, ext=[AuthorCompanyExt(id=1329455923942240913, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455923933852304, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer and Information Technology, Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455923946435218, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455923933852304, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1山西大学计算机与信息技术学院 太原 030006)]), AuthorCompany(id=1329455924105818774, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=3, ext=[AuthorCompanyExt(id=1329455924114207383, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924105818774, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455924122595992, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924105818774, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3山西大学大数据科学与产业研究院 太原 030006)])]), Author(id=1329455924898542250, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329455925011788461, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455924898542250, language=EN, stringName=Shanshan Yao, firstName=Shanshan, middleName=null, lastName=Yao, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 3, address=1School of Computer and Information Technology, Shanxi University, Taiyuan 030006
3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006, bio={"content":"

born in 1989. PhD, associate professor. Her main research interests include big data retrieval and pattern recognition

"}, bioImg=null, bioContent=

born in 1989. PhD, associate professor. Her main research interests include big data retrieval and pattern recognition

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329455925108257454, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455924898542250, language=CN, stringName=姚姗姗, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 3, address=1山西大学计算机与信息技术学院 太原 030006
3山西大学大数据科学与产业研究院 太原 030006, bio={"img":"+WLwuiwOmNigG9it/wEjeg==","content":"

1989年生. 博士,副教授. 主要研究方向为大数据检索、模式识别

"}, bioImg=+WLwuiwOmNigG9it/wEjeg==, bioContent=

1989年生. 博士,副教授. 主要研究方向为大数据检索、模式识别

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329455923933852304, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=1, ext=[AuthorCompanyExt(id=1329455923942240913, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455923933852304, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer and Information Technology, Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455923946435218, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455923933852304, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1山西大学计算机与信息技术学院 太原 030006)]), AuthorCompany(id=1329455924105818774, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=3, ext=[AuthorCompanyExt(id=1329455924114207383, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924105818774, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455924122595992, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924105818774, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3山西大学大数据科学与产业研究院 太原 030006)])]), Author(id=1329455925171172016, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329455925250863795, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455925171172016, language=EN, stringName=Jing Yang, firstName=Jing, middleName=null, lastName=Yang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, 3, address=2School of Automation and Software Engineering, Shanxi University, Taiyuan 030006
3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006, bio={"content":"

born in 1990. PhD, lecturer. Her main research interests include fuzzy systems and image reconstruction

"}, bioImg=null, bioContent=

born in 1990. PhD, lecturer. Her main research interests include fuzzy systems and image reconstruction

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329455925330555572, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455925171172016, language=CN, stringName=杨静, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, 3, address=2山西大学自动化与软件学院 太原 030006
3山西大学大数据科学与产业研究院 太原 030006, bio={"img":"B4/KQm9jWaof2nHguCbpWA==","content":"

1990年生,博士,讲师. 主要研究方向为模糊系统、图像重建

"}, bioImg=B4/KQm9jWaof2nHguCbpWA==, bioContent=

1990年生,博士,讲师. 主要研究方向为模糊系统、图像重建

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329455924017738387, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=2, ext=[AuthorCompanyExt(id=1329455924026126996, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924017738387, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2School of Automation and Software Engineering, Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455924034515605, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924017738387, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2山西大学自动化与软件学院 太原 030006)]), AuthorCompany(id=1329455924105818774, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=3, ext=[AuthorCompanyExt(id=1329455924114207383, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924105818774, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455924122595992, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924105818774, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3山西大学大数据科学与产业研究院 太原 030006)])]), Author(id=1329455925393470134, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329455925477356216, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455925393470134, language=EN, stringName=Haotian Chi, firstName=Haotian, middleName=null, lastName=Chi, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, address=2School of Automation and Software Engineering, Shanxi University, Taiyuan 030006, bio={"content":"

born in 1990. PhD, lecturer. His main research interests include Internet of Things security, wireless security, and privacy protetion

"}, bioImg=null, bioContent=

born in 1990. PhD, lecturer. His main research interests include Internet of Things security, wireless security, and privacy protetion

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329455925603185337, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455925393470134, language=CN, stringName=池浩田, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, address=2山西大学自动化与软件学院 太原 030006, bio={"img":"LQXOKe5c0wX7LOgUAppVgg==","content":"

1990年生. 博士,讲师. 主要研究方向为物联网安全、无线安全、隐私保护

"}, bioImg=LQXOKe5c0wX7LOgUAppVgg==, bioContent=

1990年生. 博士,讲师. 主要研究方向为物联网安全、无线安全、隐私保护

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329455924017738387, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=2, ext=[AuthorCompanyExt(id=1329455924026126996, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924017738387, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2School of Automation and Software Engineering, Shanxi University, Taiyuan 030006), AuthorCompanyExt(id=1329455924034515605, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924017738387, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2山西大学自动化与软件学院 太原 030006)])]), Author(id=1329455925670294203, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, orderNo=5, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=yxia@tsinghua.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1329455925745791677, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455925670294203, language=EN, stringName=Xia Yin, firstName=Xia, middleName=null, lastName=Yin, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=4, *, address=4Department of Computer Science and Technology, Tsinghua University, Beijing 100084, bio={"content":"

born in 1972. PhD, professor, PhD supervisor. Her main research interests include future Internet architecture and protocol testing

"}, bioImg=null, bioContent=

born in 1972. PhD, professor, PhD supervisor. Her main research interests include future Internet architecture and protocol testing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329455925812900542, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, authorId=1329455925670294203, language=CN, stringName=尹霞, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=4, *, address=4清华大学计算机科学与技术系 北京 100084, bio={"img":"4xpKtiA/eatWJJhPdXPM4w==","content":"

1972年生. 博士,教授,博士生导师. 主要研究方向为未来互联网体系结构、协议测试

"}, bioImg=4xpKtiA/eatWJJhPdXPM4w==, bioContent=

1972年生. 博士,教授,博士生导师. 主要研究方向为未来互联网体系结构、协议测试

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329455924189704857, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, xref=4, ext=[AuthorCompanyExt(id=1329455924198093466, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924189704857, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=4Department of Computer Science and Technology, Tsinghua University, Beijing 100084), AuthorCompanyExt(id=1329455924210676379, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329455921652150905, companyId=1329455924189704857, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=4清华大学计算机科学与技术系 北京 100084)])])]
耿海军1, 2, 3 , 孟卓1, 3, 姚姗姗1, 3, 杨静2, 3, 池浩田2, 尹霞4, *
作者信息
  • 1山西大学计算机与信息技术学院 太原 030006
  • 2山西大学自动化与软件学院 太原 030006
  • 3山西大学大数据科学与产业研究院 太原 030006
  • 4清华大学计算机科学与技术系 北京 100084
通讯作者:
作者简介:

1983年生. 博士,副教授. 主要研究方向为网络体系结构、路由算法

1998年生. 硕士研究生. 主要研究方向为网络体系结构、路由算法

1989年生. 博士,副教授. 主要研究方向为大数据检索、模式识别

1990年生,博士,讲师. 主要研究方向为模糊系统、图像重建

1990年生. 博士,讲师. 主要研究方向为物联网安全、无线安全、隐私保护

1972年生. 博士,教授,博士生导师. 主要研究方向为未来互联网体系结构、协议测试

An Intra-Domain Routing Protection Algorithm Based on Forwarding Graph
Haijun Geng1, 2, 3 , Zhuo Meng1, 3, Shanshan Yao1, 3, Jing Yang2, 3, Haotian Chi2, Xia Yin4, *
Affiliations
  • 1School of Computer and Information Technology, Shanxi University, Taiyuan 030006
  • 2School of Automation and Software Engineering, Shanxi University, Taiyuan 030006
  • 3Industry of Big Data Science and Industry , Shanxi University, Taiyuan 030006
  • 4Department of Computer Science and Technology, Tsinghua University, Beijing 100084
  • born in 1983. PhD, associate professor. His main research interests include network architecture and routing algorithm

    born in 1998. Master candidate. His main research interests include network architecture and routing algorithm

    born in 1989. PhD, associate professor. Her main research interests include big data retrieval and pattern recognition

    born in 1990. PhD, lecturer. Her main research interests include fuzzy systems and image reconstruction

    born in 1990. PhD, lecturer. His main research interests include Internet of Things security, wireless security, and privacy protetion

    born in 1972. PhD, professor, PhD supervisor. Her main research interests include future Internet architecture and protocol testing

出版时间: 2024-02-02 doi: 10.7544/issn1000-1239.202220914
文章导航
收藏切换

业界提出利用路由保护算法来解决网络中的故障问题,然而已有的路由保护算法存在4个方面的问题:1)无法应对网络中所有可能的单故障情形;2)需要额外辅助机制的协助;3)不支持增量部署;4)每个结点存储多个到达目的地址的备份下一跳. 提出一种基于转发图的域内路由保护算法(an intra-domain routing protection algorithm based on forwarding graph, RPBFG)来解决这4个问题. 首先建立了以最大化故障保护率为目标、以转发图包含反向最短路径树为约束条件的路由保护模型;然后提出了利用遗传算法构造满足上述目标的转发图;最后根据构造的转发图计算出所有结点到达目的结点的备份下一跳. 在11个真实拓扑结构中比较了RPBFG,NPC,U-turn,MARA-MA,MARA-SPE在故障保护率和路径拉伸度的性能. 实验结果表明,RPBFG可以应对网络中所有可能的单故障;在平均路径拉伸度方面,RPBFG比NPC,U-turn,MARA-MA,MARA-SPE分别降低了0.11%,0.72%,37.79%,36.26%.

路由保护  /  网络故障  /  故障保护率  /  路径拉伸度  /  有向无环图  /  转发图

Currently, intra-domain routing protocols which are deployed on the Internet respond to network failures through a global convergence mechanism. In the process of routing convergence, a large number of data packets will be discarded, leading to network interruption. The industry proposes to use routing protection methods to solve the above problem. However, the existing routing protection methods have the following four problems: 1) they cannot cope with all possible single failures in the network; 2) they need the assistance of additional auxiliary mechanisms; 3) they do not support incremental deployment; 4) each node stores multiple backup next hops for each destination, increasing storage and computation costs. We propose an intra-domain routing protection algorithm based on forwarding graph (RPBFG) to solve the above four problems of existing routing protection algorithms. We first establish a routing protection model with the goal of maximizing the failure protection ratio and the constraint that the forwarding graph contains the reverse shortest path tree; then a genetic algorithm is proposed to construct a forwarding graph that satisfies the above goal; finally, the backup next hop of all nodes arriving at the destination node is calculated according to the constructed forwarding graph. We compare the performance of RPBFG, NPC, U-turn, MARA-MA and MARA-SPE in 11 real topologies, including failure protection ratio and path stretch. The experimental results show that RPBFG can deal with all possible single failures in the network, and that is to say the failure protection ratio of RPBFG is 100%, while the average failure protection ratio of NPC, U-turn, MARA-MA and MARA-SPE is 45.05%, 74.53%, 89.78% and 91.24% respectively. In the aspect of path stretch, RPBFG decreased by 0.11%, 0.72%, 37.79% and 36.26% respectively compared with NPC, U-turn, MARA-MA and MARA-SPE. The research results will help to promote the progress of Internet service providers in deploying intra-domain routing protection schemes in real networks.

routing protection  /  network failure  /  failure protection ratio  /  path stretch  /  directed acyclic graph  /  forwarding graph
耿海军, 孟卓, 姚姗姗, 杨静, 池浩田, 尹霞. 一种基于转发图的域内路由保护算法. 计算机研究与发展, 2024 , 61 (2) : 529 -538 . DOI: 10.7544/issn1000-1239.202220914
Haijun Geng, Zhuo Meng, Shanshan Yao, Jing Yang, Haotian Chi, Xia Yin. An Intra-Domain Routing Protection Algorithm Based on Forwarding Graph[J]. Journal of Computer Research and Development, 2024 , 61 (2) : 529 -538 . DOI: 10.7544/issn1000-1239.202220914
开放最短路径优先(open shortest path first, OSPF)[1]协议和中间系统到中间系统(intermediate system to intermediate system, IS-IS)协议是互联网目前使用的2个典型的域内路由协议[2],这2个协议采用最短路径将报文从源地址转发到目的地址. 在OSPF和IS-IS中,每个路由器通过交互链路状态通告获得整个网络的拓扑结构,然后该路由器通过迪杰斯特拉算法计算以自身为根的最短路径树,最后该路由器根据最短路径树构造出自己的路由表. 当网络出现故障时,OSPF和IS-IS采用重新收敛机制来应对网路中的故障. 但是研究表明[3-5],它们的重新收敛时间大概在几秒甚至几十秒左右,在路由协议重新收敛的过程中受这些故障影响的报文将会被丢弃,严重影响了网络的性能,大大降低了用户的体验. 互联网部署的实时应用对网络的收敛时间提出了更高的要求[6-8]. 传统的路由协议无法满足实时应用对网络收敛时间的要求[9]. 为此,业界提出利用路由保护算法来解决此问题,研究表明路由保护算法[10]可以大大降低由于故障造成的网络中断时间,显著减少报文丢失.
在已有的路由保护算法中,最经典的方法是IP快速重路由(IP fast rerouting, IPFRR)[11],该算法可以选择事先计算好的备份下一跳绕过故障,从而降低由于故障造成的报文丢失率. 与最短路径路由相比,IPFRR有明显的优点:可以立即重新转发数据包,而不是等待路由重新收敛(通常为几秒甚至几十秒),从而避免在路由重新收敛阶段出现路由环路和数据包丢失问题[12].
路由保护算法最核心的技术是如何为每个结点计算到达目的结点的无环路备份下一跳. 下游规则(downstream criterion, DC)[13]是一种经典的无环路计算规则,该规则选择距目的地址更近的邻居结点作为备份下一跳. 以目的结点构造有向无环图(directed acyclic graph, DAG),也可以计算出无环路备份下一跳. 基于最大邻接顺序的最大可选择性路由算法(maximum alternative routing algorithm, MARA)[14]的核心思想就是将网络拓扑转换为DAG. 但是文献[13-14]算法和网络拓扑结构密切相关,在某些拓扑结构中故障保护率较低. 在DAG图中,每条链路仅有1个方向,这个要求大大降低了结点可以计算出无环路备份下一跳的可能性. JNHOR-SP(shortest path compatible Joker-capable next hop optimality routing)[15]利用路由结点排序和Joker链路来提高DAG图的故障保护率,网络中的Joker链路具有2个方向,但是由于计算Joker链路算法的缺陷,JNHOR-SP平均仅能提供95%左右的故障保护率. 基于报文入端口的无环路路由(loop free inport-dependent, LFID)[16]通过扩展DAG,将部分链路修改为双向链路,从而同时解决网络故障和网络拥塞问题,但是LFID的故障保护率为88.9% ~ 98.2%. Not-Via[17]和段路由[18](segment routing, SR)可以保护网络所有可能的单故障,但是二者需要借助辅助机制的协助,在实际中部署比较困难.
已有的路由保护算法存在4个方面的问题:1)无法应对网络中所有可能的单故障情形;2)需要额外辅助机制的协助;3)不支持增量部署;4)需要存储多个备份下一跳. 我们拟设计一个路由算法,该算法满足4个要求:1)每个路由器存储2个下一跳,其中一个为最优下一跳,另外一个为备份下一跳;2)可以应对网络中所有可能出现的单故障情形;3)不需要额外辅助机制的协助;4)支持增量部署. 基于此本文提出了一个满足这4个要求的基于转发图的域内路由保护算法(an intra-domain routing protection algorithm based on forwarding graph, RPBFG). 受JNHOR-SP和LFID这2个算法的启发,本文通过构造转发图来解决DAG图故障保护率较低的问题. 在转发图中,每条链路可能存在2个方向,这将明显提高故障保护率. 与JNHOR-SP和LFID不同的是,RPBFG可以提供100%故障保护率. 我们将在后面的章节中详细介绍什么是转发图,如何构造转发图,如何利用转发图计算无环路备份下一跳.
本文的主要贡献包括4个方面:
1) 提出了以最大化故障保护率为目标,转发图包含反向最短路径树为约束条件的路由保护算法模型RPBFG.
2) 针对提出的路由保护算法模型,首先提出了利用RPBFG解决快速构造转发图的算法,然后利用转发图为每个结点计算唯一一个备份下一跳.
3) RPBFG是对当前链路状态路由协议的扩展,不会改变路由协议报文的交互过程. RPBFG需要的数据都可以从链路状态路由协议中获得,唯一的变化是路由计算部分,因此RPBFG支持增量部署.
4) 在11个真实网络拓扑中进行了实验,实验结果表明RPBFG不仅可以支持100%的单故障保护,而且具有较小的路径拉伸度.
根据这4点贡献的描述可知RPBFG可以应对网络中所有可能的单故障情形,不需要额外辅助机制的协助,支持增量部署,每个结点存储唯一一个到达目的地址的备份下一跳. 因此RPBFG可以解决文中描述的已有路由保护算法存在的4个问题.
已有研究[19]证实,互联网中每天都会出现大量的网络故障. 为了应对互联网中频繁出现的故障,业界提出了路由保护算法[20],从而尽量降低由于故障造成的损失. 根据报文在转发过程中是否需要辅助机制的协助,可以将路由保护算法分为2类:第1类不需要借助辅助转发机制;第2类需要借助辅助转发机制.
第1类路由保护算法主要包括等价多路径路由(equal cost multipath routing, ECMP)、 无环路备选条件(loop-free alternates, LFA)、U-turn、MARA-MA、基于扩展最短路径的最大可选择性路由算法(maximum alternative routing algorithm-shortest path extension, MARA-SPE)等;第2类路由保护算法主要包括Not-Via、SR、多配置路由(multiple routing configuration, MRC)、报文携带故障(failure carrying packet, FCP)等. 第1类算法和目前使用的路由协议是兼容的,因此支持增量部署. 然而第2类路由保护算法需要对目前使用的路由协议进行修改,实现难度较大. 本文重点研究第1类路由保护算法,下面将分别介绍这类路由算法.
OSPF协议增加了对ECMP的支持,但是ECMP仅仅支持代价相同的最短路径,因此对提高路由可用性的贡献比较有限[21]. 为了应对ECMP在解决路由可用性方面存在的问题,国际互联网工程任务组(Internet Engineering Task Force, IETF)提出了快速重路由的基本框架. LFA就是基于此框架提出的无环路路由. LFA包括3种应对故障的保护条件:链路保护条件(link protection condition, LPC)、结点保护条件(node protection condition, NPC)和DC. 文献[22-23]分别介绍了如何通过调整链路权值和修改网络拓扑结构提高LFA的故障保护率. U-turn[24]将选择备份下一跳扩展到计算结点邻居的邻居,即如果计算结点的邻居没有满足无环路规则的下一跳,但是计算结点的邻居的邻居有满足无环路规则的下一跳,则该邻居可以作为计算结点的备份下一跳,因此U-turn可以进一步提高故障保护率. MARA-MA[14]以最大化最小连通性为目标构造DAG,MARA-SPE[14]和MARA-MA的目标是一致的,但是MARA-SPE的约束条件为DAG必须包含最短路径树.
文献[25]提出了基于Not-Via地址的快速重路由机制. 在该算法中,网络中的每条链路都有2个地址,一个是正常的IP地址,另一个Not-Via地址. 该机制使用Not-Via地址显示的说明网络中出现故障的结点或者链路,从而使报文避开该故障. 基于隧道的路由保护算法[26]为所有源目的对计算中转隧道结点,然而并不是所有的结点对之间都存在中转结点. 基于SR[14]的路由保护算法将网络的路径分成一个个的小段,然后为这些段和网络结点分配Segment Routing的ID,通过对这些 Segment Routing ID进行有序的排列,就可以生成一条完整的转发路径.
MRC[27]通过改变网络中链路的代价计算出多个配置图,这些不同配置图可以应对网络中出现的不同故障,从而达到提高路由可用性的目的,但是MRC部署开销较大. FCP[28]的核心思路为:首先将报文遇到的故障存放在其头部,然后根据该头部信息更新网络拓扑结构,最后利用新的网路拓扑结构计算新的最短路径. FCP可以应对网络中的单故障问题,但是该方法需要改变路由协议,部署难度较大.
表1列出了RPBFG和已有路由保护算法的链路状态路由协议,在支持逐跳转发和支持100%的单故障保护等方面进行比较.
1) 链路状态路由协议. 每个路由器根据网络拓扑结构做出最终的路由决策.
2) 支持逐跳转发. 每个路由器基于目标地址查找数据报的下一跳,转发过程不需要借助额外机制的协助.
3) 支持100%的单故障保护. 当网络出现单故障时,只要网络依然保持链路,数据报就可以被正确转发到目的地址.
本节首先定义了反向最短路径树、转发图、故障保护率和路径拉伸度,然后对基于转发图的路由保护算法进行了形式化的描述. 为了便于读者阅读,将文中使用的部分符号总结在表2中.
本文使用无向图G=(V, E) 来表示一个网络,其中V是无向图中的结点集合,代表网络中的路由器,E是无向图中的边集合,代表网络中的链路. 对于网络中的任意一个结点$ v \in V $,bestn(v, d)表示结点v到结点d的最优下一跳,backn(v, d)表示结点v到结点d的备份下一跳. 下面给出反向最短路径树、转发图、故障保护率和路径拉伸度的定义.
定义1. 反向最短路径树. 对于目的结点d,其余结点到目的结点d都具有最短路径的树. r(d)表示目的地址为d的反向最短路径树.
定义2. 转发图. 按照一定的规则遍历无环路的有向图. G(d)表示目的地址为d的转发图.
定义3. 在转发图G(d)中,对于任意的结点$ v \in V,v \ne d $,如果v到d的最优下一跳出现故障,v依然可以到达目的地址d,我们称在G(d)中结点v可以被保护,否则结点v未被保护.
定义4. 转发图G(d)的故障保护率可以表示为$ P(v,G(d)) = \dfrac{{\displaystyle\sum\limits_{v \in V} {f(v,d)} }}{{|V| - 1}} $,其中当结点v被保护时f(v, d)=1,否则f(v, d)=0.
定义5. 路径拉伸度. 当网络出现故障时,利用路由保护算法计算出的所有源目的对之间的代价总和与利用最短路径计算出的所有源目的对之间的代价总和的比值.
我们通过一个简单的例子解释上面的定义1~5. 图1表示网络拓扑结构,链路上的数字表示该链路对应的代价. 图2表示以结点d为根的反向最短路径树,实线表示在反向最短路径树中的边,从图2中可以计算出每个结点到目的结点d的最优下一跳. 例如,f到d的最优下一跳可以表示为bestn(f, d)=c, k到d的最优下一跳是bestn(k, d)=j. 图3是以d为目的地址的转发图,从图3中可以计算出每个结点到目的结点d的备份下一跳. 在图3中实线箭头表示结点的最优下一跳,空心箭头表示结点的备份下一跳. 例如,f到d的备份下一跳可以表示为backn(f, d)=e, k到d的备份下一跳可以表示为backn(k, d)=h. 转发图是如何构造出来的,为什么利用转发图可以计算出结点的备份下一跳将在后面的章节中详细介绍.
为了解决已有路由保护算法存在的4个问题,我们形式化地描述了本文需要解决的科学问题. 在已知网络拓扑结构G=(V, E) 的前提条件下,对于目的结点$ d \in V $,如何构造一组转发图G(d)包含反向最短路径树r(d),从而使得故障保护率最高. 该问题可以形式化表示为
$ \mathrm{Maximize} \frac{{\displaystyle \sum _{d\in V}{\displaystyle \sum _{v\in V,v\ne d}P(v,G(d))}}}{\left|V\right|}, $
$ \mathrm{s}.\mathrm{t}.\quad G(d) \supseteq r(d),$
其中式(1)为目标函数,即最大化故障保护率;式(2)表示反向最短路径树属于转发图.
在构造转发图的过程中,需要解决2个关键问题:1)如何设计遍历算法,即转发算法;2)如何给转发图中链路设置方向,从而使得该转发图包含反向最短路径树.
对于问题1我们采用互联网部署的路由转发算法,这样设计的算法和互联网是兼容的,便于实际部署. 我们对转发算法进行简单地描述:在网络中,当路由器收到一个报文后,就会根据报文中目的地址的信息从路由表中查找对应的下一跳,然后将该报文直接发送给对应的下一跳. 具体的转发规则为:
1) 如果最优下一跳路由器发生了故障,就从备份路由表中查找备份下一跳,将报文发送给备份下一跳;
2) 如果收到的报文来自最优下一跳,也将报文发送给备份下一跳;
3) 其他情况均将报文发送给最优下一跳.
下面通过一个例子来解释转发算法. 在图3中,假设报文的源地址是c,目的地址是d,当结点a出现故障时,结点c将报文转发给备份下一跳f,结点f发现该报文来自于自己的最优下一跳c,因此结点f将报文发送给其备份下一跳e,接着结点e将报文转发给最优下一跳b,最后b将报文转发给目的地址d.
下面重点描述如何解决问题2. 给定目的地址d,构造G(d)就是为网络拓扑中的链路设定特定的方向. 其中G(d)包含r(d)的条件比较容易实现,只需要在反向最短路径树r(d)的基础上构造转发图即可. 如何保证构造的图是转发图成为本文研究的重点和难点. 构造转发图就是为网络中的链路指定方向,对于网络中的链路$ (u,v) \in E $,每条链路有4种状态:第1种状态是该链路不在转发图中;第2种状态是该链路的方向为$ u \to v $;第3种状态是该链路的方向为$ v \to u $;第4种状态是$ u \to v $和$ v \to u $都在转发图中,用$ v - u $来表示. 如果$ (u,v) \in r(d)$,假设链路的方向为$ u \to v $,则该链路的状态只有$ u \to v $和$ v - u $这2种可能性;反之假设链路的方向为$ v \to u $,则该链路的状态只有$ v \to u $和$ v - u $这2种可能性. 通过上述分析可知当链路$ (u,v) \in r(d)$时,该链路的状态有2种可能性;当$ (u,v) \notin r(d)$,则该链路的状态有4种可能性;对于一个包含|V|个结点、|E|条边的网络拓扑来讲,有|V|−1条链路在反向最短路径树上,|E|+|V|+1条链路不在反向最短路径树上,因此链路状态的数量为$ {2^{|V| - 1}} \times {4^{|E| - |V| + 1}} = {2^{2 \times |E| - |V| + 1}} $,如果把所有的链路状态的组合都枚举出来,然后从中选择符合条件的转发图,在实际网络中部署是一种不现实的解决方案.
为了解决该问题,本文提出利用遗传算法来构造转发图,该算法包含2个步骤:1)计算以结点d为根的反向最短路径树r(d);2)在r(d)的基础上,利用遗传算法构造转发图.
算法1(RPBFG算法)描述了利用遗传算法构造转发图的过程. 算法的输入为网络拓扑结构G=(V, E),输出为每个结点的备份路由表. 下面以目的地址d为例进行描述.RPBFG主要通过3个步骤实现:首先对网络中的链路进行编码,在链路编码的基础上生成初始转发图;然后利用选择、交叉和变异操作计算出最优个体,根据选择的最优个体构造出最优转发图;最后根据最优转发图计算出所有结点的备份下一跳.
算法1. RPBFG算法.
输入:G=(V, E);
输出:backn(v, d),$ v \in V,v \ne d $.
① for each $ v \in V,v \ne d $
②   backup(v, d)$ \leftarrow \varnothing $;
③ end for
④ compute r(d);
⑤ population$ \leftarrow $InitPopulation(G, d);
  /* 利用r(d)生成初始种群*/
⑥ for each $ i \in \{ 1,2,…,m\} $/*算法迭代次数*/
⑦  remains$ \leftarrow $RouWheelSel(population);
⑧  children$ \leftarrow \varnothing $;
⑨ for each parentA$ \in $remains
⑩   parentB$ \in $random_select_remains;
⑪   child$ \leftarrow $Cross(parentA, parentB);
⑫   child$ \leftarrow $Mutate(child);
⑬   children$ \leftarrow $children$ \cup ${child};
⑭   population$ \leftarrow $children$ \cup $remains;
⑮ end for
⑯ end for
⑰ FG$ \leftarrow $ComputeFG(Best(population));
⑱ for each $ v \in V,v \ne d $
⑲  backup(v, d)$ \leftarrow $ComputeBackup(FG);
⑳ end for
㉑ return backup(v, d),$ v \in V,v \ne d. $
在介绍RPBFG之前,我们描述链路编码的算法和适应度函数. 首先描述链路编码的算法. 对于网络中的链路$ (u,v) \in E $,用2位二进制编码来表示链路的状态:因此每条链路有4种状态:00表示该链路不在转发图中,01表示该链路的方向为$ u \to v $,10表示该链路的方向为$ v \to u $,11表示该链路的方向为$ v - u $. 例如网络中有5条链路,分别是(a, b),(b, c),(c, d),(a, d),(b, d),如果对应的链路编码为(1001101101),则表示链路(a, b)的方向为$ a \to b $,链路(b, c)的方向为$ c \to b $,链路(c, d)的方向为$ c \to d $,链路(a, d)的方向为$ a \to d $,链路(b, d)的方向为$ d \to b $. 然后描述适应度函数. 为了保证RPBFG在满足最大化故障保护率的同时,尽可能降低重路由路径的路径拉伸度,本文的适应度函数=故障保护率+0.001×路径拉伸度. 下面详细介绍算法RPBFG的执行过程,如算法1所示. 将备份下一跳集合初始化为空(行①~③);对于网络中的结点$ d \in V $,利用迪杰斯特拉算法计算反向最短路径树r(d)(行④). 行⑤表示生成初始化种群,本文利用r(d)生成初始种群,所有种群的规模数为N,所有初始种群的编码相同. 遗传算法的迭代过程中迭代次数为m(行⑥),在每次迭代中,利用轮盘赌算法[29]进行选择操作,该算法根据个体的适应度和累计概率计算个体被选择的概率,轮盘赌选择中个体的适应度越好越有可能被保留,如果要保留n个个体,则在现有的2n个个体中进行n次有放回抽样,每次抽样中每个个体被抽中的概率为 $ p_i ={{{f_i}}}\big/{{\displaystyle\sum\limits_{j = 1}^N {{f_j}} }} $,其中pi表示该个体被保留的概率,fi表示该个体的适应度,$ \displaystyle\sum\limits_{j = 1}^N {{f_j}} $表示所有个体适应度之和(行⑦ ). 行⑪和行⑫分别表示交叉和变异操作. 本文使用的交叉方法为多点交叉. 具体方法为:首先将要执行交叉的2个个体分别表示为A和B,然后随机选择若干个位置(每个位置被选择的概率是提前设置好的),将这些位置记为{i1,i2,…,in},而后将A和B中的{i1,i2,…,in}位置上的基因相互交换. 算法1中使用2个位置的基因表示1条边的方向,所以在交叉互换的过程中将基因两两视为一个整体,以确保边的方向信息作为整体被交换.
本文采用的变异方法为:用变异率p表示基因变异的概率,当1个染色体发生变异时,它的每个基因都按照概率p发生变异,当某个位置的基因发生变异时,如果基因未变异概率为1,则基因概率变异为0,反之,如果基因未变异概率为0,则基因概率变异为1. 为了保证变异后的染色体所表示的转发图不产生路由环路,在每次变异后都会检查其是否产生了环路,如果这次变异导致了环路,那就将该基因还原. 需要注意的是,染色体中表示最短路径树中有向边的基因不会发生变异,因为这些基因表示的是最优下一跳. 当迭代部分执行完毕以后,根据最优个体Best(population)中链路的方向利用ComputeFG(Best(population))计算出转发图(行⑰);然后利用该转发图为网络中的其他结点计算到达目的地址d的备份下一跳,为结点$ v \in V,v \ne d $计算备份下一跳的算法如下:遍历结点v的不是最优下一跳的邻居结点v,如果该边的编码为10或者11,则结点u可以将结点v作为备份下一跳(行⑱~⑳). 当算法1执行完毕以后,返回所有结点到达目的结点d的备份下一跳集合(行㉑).
下面分析算法的时间复杂度. 算法1的行①~③的时间复杂度为$ O(|V|) $,行④的时间复杂度为$ O(|V|\lg |V| + |E|) $,行⑤的时间复杂度为$ O(N) $,行⑥~⑯的时间复杂度为$ O(N \times m) $,行⑰的时间复杂度为$ O(|E|) $,行⑱~⑳的时间复杂度为$ O(|V|) $,RPBFG的总时间复杂度为$ O(|V|) $+$ O(|V|\lg |V| + |E|) $+$ O(N) $+$ O(N \times m) $+$ O(|E|) $+$ O(|V|) $,即$ O(|V|\lg |V| + 2|E|{\text{ + }}N \times m) $.
本节将RPBFG与NPC,U-turn,MARA-MA,MARA-SPE进行比较,采用Python实现这5种算法. 实验采用了11种真实的网络拓扑结构[30],如表3所示,使用真实拓扑结构使得实验结果更加真实准确. 实验采用的度量指标包括故障保护率和路径拉伸度. 故障保护率反映了算法应对网络中发生故障的能力,该值越大说明算法应对故障的能力越强. 路径拉伸度表示当网络出现故障以后,重路由路径的代价和最短路径的代价的比值,该值越小说明利用路由保护算法计算出的路径代价和利用最短路径计算出的路径代价接近,给网络带来的额外开销越低.
本节比较算法RPBFG,NPC,U-turn,MARA-MA,MARA-SPE的故障保护率. 图4描述了5种算法在11个真实网络拓扑图中的故障保护率. 在所有实验的网络拓扑结构中RPBFG的故障保护率均为1.0,NPC,U-turn,MARA-MA,MARA-SPE的故障保护率均低于1.0. 例如,在Abilene中,NPC,U-turn,MARA-MA,MARA-SPE对应的故障保护率分别是0.48 ,0.75, 0.85 ,0.88,在Arpanet 19728中, NPC,U-turn,MARA-MA,MARA-SPE对应的故障保护率分别是0.07,0.23 ,0.81 ,0.84. 这是因为NPC,U-turn,MARA-MA,MARA-SPE使用一定的规则计算备份下一跳,因为这些规则和网络拓扑结构密切相关,在某些网络拓扑结构中无法为所有的源目的结点对计算符合这些规则的备份下一跳. 而RPBFG与网络拓扑无关,只要网络中存在的路径可以到达目的地址,RPBFG就可以计算出相应的重路由路径.
在计算路径拉伸度的过程中,为了体现公平性,只考虑2个算法都能保护的路径. 具体计算算法为:算法A可以保护所有源目的结点对的集合$ \alpha $,算法B可以保护所有源目的结点对集合$ \beta $,这2个集合的交集$ C = \alpha \cap \beta $就是需要计算的源目的结点对集合. 表4列出了RPBFG和NPC的路径拉伸度的平均值和方差. 表5列出了RPBFG和U-turn的路径拉伸度的平均值和方差. 表6列出了RPBFG和MARA-MA的路径拉伸度的平均值和方差. 表7列出了RPBFG和MARA-SPE的路径拉伸度的平均值和方差. 从表4~7可以看出,RPBFG的路径拉伸度的平均值和方差几乎明显低于其余4种算法. 在平均路径拉伸度方面,RPBFG比NPC,U-turn,MARA-MA,MARA-SPE分别降低了0.11%,0.72%,37.79%,36.26%.
为了应对网络中频繁出现的故障,本文提出了一种基于转发图的域内路由保护算法(RPBFG),该算法通过构造最优转发图应对网络故障. 与已有路由保护算法不同,RPBFG仅为每个结点存储1个备份下一跳,这样可以大大降低存储开销. 我们首先描述了需要解决的关键科学问题;然后理论分析直接求解的复杂度;接着采用遗传算法来解决提出的问题,从而降低求解的复杂度;最后在11个真实拓扑中对RPBFG的性能进行了测试. 仿真测试表明该算法可以应对网络中所有可能的单故障情形,并且具有较小的路径拉伸度. RPBFG是一种域内路由保护算法,在未来的工作中将研究如何将RPBFG的核心思想应用到域间路由保护算法中,从而进一步提高网络的可用性.
作者贡献声明:耿海军提出了算法思路和实验方案,并撰写论文;孟卓负责执行实验方案;姚珊珊参与实验方案指导和对部分实验结果分析;杨静参与论文校对和实验方案指导;池浩田提出了指导意见并修改论文;尹霞提出方法的指导意见和审核论文.

参考文献 引证文献
排序方式:
1
Moy J. RFC 2328 OSPF Version 2 [S/OL]. The Internet Engineering Task Force, 1998[2022-09-06].https://www.ietf.org/rfc/rfc2328
2
David O. RFC 1142 OSI IS-IS Intra-domain Routing Protocol [S/OL]. The Internet Engineering Task Force, 1990[2022-08-12].https://www.ietf.org/rfc/rfc1142
3
Duijn I V, Jensen P G, Jensen J S, et al. Automata-theoretic approach to verification of MPLS networks under link failures[J]. IEEE/ACM Transactions on Networking, 2022, 30(2): 766−781
4
Foerster K T, Kamisiski A, Pignolet Y A, et al. Improved fast rerouting using postprocessing[J]. IEEE Transactions on Dependable and Secure Computing, 2022, 19(1): 537−550
5
Yang Ze, Yeung K L. SDN candidate selection in hybrid IP/SDN networks for single link failure protection[J]. IEEE/ACM Transactions on Networking, 2020, 28(1): 312−321
6
Geng Haijun, Zhang Han, Shi Xingang, et al. Efficient computation of loop-free alternates[J]. Journal of Network and Computer Applications, 2020, 151: 1−12
7
Jia Xuya, Li Dan, Zhu Jing, et al. Metro: An efficient traffic fast rerouting scheme with low overhead[J]. IEEE/ACM Transactions on Networking, 2019, 27(5): 2015−2027
8
Borokhovich M, Pignolet Y A, Schmid S, et al. Load-optimal local fast rerouting for dense networks[J]. IEEE/ACM Transactions on Networking, 2018, 26(6): 2583−2597
9
Yang Yuan, Xu Minwei, Li Qi. Fast rerouting against multi-link failures without topology constraint[J]. IEEE/ACM Transactions on Networking, 2018, 26(1): 384−397
10
Shukla A, Foerster K T. Shortcutting fast failover routes in the data plane [C] //Proc of the 16th Symp on Architectures for Networking and Communications Systems. Piscataway, NJ: IEEE, 2021: 15−22
11
Atlas A, Zinin A. RFC 5286 Basic Specification for IP Fast Reroute: Loop-free Alternates [S/OL]. The Internet Engineering Task Force, 2008[2022-10-08].https://www.ietf.org/rfc/rfc5286
12
耿海军,施新刚,王之梁,等. 基于最小路径交叉度的域内路由保护方案[J]. 软件学报,2020,31(5):1536−1548
Geng Haijun, Shi Xingang, Wang Zhiliang, et al. Intra-domain routing protection scheme based on minimum intersection paths[J]. Journal of Software, 2020, 31(5): 1536−1548 (in Chinese)
13
Yang Xiaowei, Wetherall D. Source selectable path diversity via routing deflections[J]. Computer Communication Review, 2006, 36(4): 159−170
14
Ohara Y , Imahori S , Meter R V. MARA: Maximum alternative routing algorithm[C] //Proc of the 28th Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2009: 298−306
15
Vo H Q, Lysne O, Kvalbein A. Routing with Joker links for maximized robustness[C/OL] //Proc of the 12th Int Conf on IFIP Networking Conf. Piscataway, NJ: IEEE, 2013[202-10-17].https://ieeexplore.ieee.org/document/6663494
16
Schneider K, Zhang Beichuang, Benmohamed L. Hop-by-hop multipath routing: Choosing the right nexthop set[C] //Proc of the 39th Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2020: 2273−2282
17
Menth M, Hartmann M, Martin R, et al. Loop-free alternates and not-via addresses: A proper combination for IP fast reroute?[J]. Computer Networks, 2010, 54(8): 1300−1315
18
Anbiah A, Sivalingam K M. Efficient failure recovery techniques for segment-routed networks[J]. Computer Communications, 2022, 182: 1−12
19
Markopoulou A, Iannaccone G, Bhattacharyya S, et al. Characterization of failures in an operational IP backbone network[J]. IEEE/ACM Transactions on Networking, 2008, 16(4): 749−762
20
Chiesa M, Kamisinski A, Rak J, et al. A survey of fast-recovery mechanisms in packet-switched networks[J]. IEEE Communications Surveys and Tutorials, 2021, 23(2): 1253−1301
21
Kwong K W, Gao Lixin, Guérin R. On the feasibility and efficacy of protection routing in IP networks[J]. IEEE/ACM Transactions on Networking, 2011, 19(5): 1543−1556
22
Rétvári G, Csikor L, Tapolcai J, et al. Optimizing IGP link costs for improving IP-level resilience with loop-free alternates[J]. Computer Communications, 2013, 36(6): 645−655
23
Rétvári G, Tapolcai J, Enyedi G, et al. IP fast reroute: Loop free alternates revisited[C] //Proc of the 30th Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2011: 2948−2956
24
Francois P, Bonaventure O. An evaluation of IP-based fast reroute techniques[C] //Proc of the ACM Conf on Emerging Network Experiment and Technology. New York: ACM, 2005: 244−245
25
Enyedi G, Szilágyi P, Rétvári G, et al. IP fast reroute: Lightweight not-via without additional addresses[C] //Proc of the 28th Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2009: 2771−2775
26
Zheng Jiaqi, Xu Hong, Zhu Xiaojun, et al. We've got you covered: Failure recovery with backup tunnels in traffic engineering[C/OL] //Proc of the 24th Int Conf on Network Protocols. Piscataway, NJ: IEEE, 2016[2022-09-18]. https://ieeexplore.ieee.org/document/7784449
27
Kvalbein A, Hansen A F, Čičić T, et al. Fast IP network recovery using multiple routing configurations[C] //Proc of the 25th Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2006: 1677−1687
28
Lakshminarayanan K, Caesar M, Rangan M, et al. Achieving convergence-free routing using failure-carrying packets[J]. Computer Communication Review, 2007, 37(4): 241−252
29
周明华,汪国昭. 基于遗传算法的B样条曲线和Bézier曲线的最小二乘拟合[J]. 计算机研究与发展,2005,42(1):134−143
Zhou Minghua, Wang Guozhao. Genetic algorithm based least square fitting of B-spline and Bézier curves[J]. Journal of Computer Research and Development, 2005, 42(1): 134−143 (in Chinese)
30
University of Adelaide. The Internet topology zoo [EB/OL]. [2022-09-07]. http://www.topology-zoo.org/
2024年第61卷第2期
81
38
0
引用本文
BibTeX
文章信息
doi: 10.7544/issn1000-1239.202220914
  • 接收时间:2022-11-03
  • 首发时间:2026-11-17
  • 出版时间:2024-02-02
补充材料
相关文章
文章信息
作者
出版历史
  • 收稿日期:2022-11-03
  • 修回日期:2023-04-14
基金
作者信息
    1山西大学计算机与信息技术学院 太原 030006
    2山西大学自动化与软件学院 太原 030006
    3山西大学大数据科学与产业研究院 太原 030006
    4清华大学计算机科学与技术系 北京 100084

通讯作者:

参考文献
分享链接
https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202220914
分享至
全文二维码

扫描看全文

引用本文
BibTeX
本文的引用情况
2种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏