题材网前段时间
据我所知这不是F视频题材acebook第一次改名，熟习Facebook生长纪传题材电影《社交关系互联小说题材网》同窗，能够关于其中包括人物肖恩的经典中的经典台词“DroptheThe.JustFacebook.It\’cleaner.印象十分深入，不得已说事先这一改是神来之笔，Facebook确是比”TheFacebook愈加简约、嘹亮，但是这一次Facebook丢掉的可不是定惯词The,而是宇宙Vers依照我了解这大约也可以以为Facebook也可以做Meta元的观点，但是不是能做成宇宙就无从知晓了
这也不是Facebook第一次宣布AllIn一个概念，2019年他公布了基于区块链的数字钱币-Libra不外Libra开展之路却是种种崎岖，无意思的今年年末Libra也改名为Diem并且听说这一次Facebook改为Meta后也会重点与区块链的最新观点NTF相结合，Facebook这样的打不外就改名的形式是否值得我去学习，也值得观察。
固然笔者并不关怀以上这些和技术无关的科技旧事，这里笔者想探讨的话题是不久之前FaceBook发作的那次由于BGP路由签署设置错误的形成的史诗级中断事故，事先毛病时期FaceBook一切旗下APP片面对外效劳中缀，并且毛病的工夫长达7个小时之久。针对这个话题我也写过一篇博客《一行小错为什么发生宏大毁坏-Facebook史诗级毛病大反思》作文题材停止过总结，而如果这次Facebook真的要AllIn元宇宙，那么说相关互联网路由协议的成绩还需求进一步的优化，不彻底地处理互联网方面的成绩，只是发明一个时常宕机的元宇宙的话，也没任何价值和意义。
路由协议的中心成绩到底是啥？
所谓路由协议，归根到底就是要找到从起始点S动身到目的所在D最短路径。这其实也就是熟知的游览计划成绩，要视频题材经过算法答复游览者从S都会动身怎样以最小的价格达到都会D而针对这个成绩早就有经典算法dikjstra处理。
因为网上能搜短片题材索到现成算法大多是依据Leecod等算法网站上的原题给出的谜底，运算后果只输入终点和终点的间隔和费用，既也没记载详细的行走途径，也也没详尽引见算法的头脑，为了说清这个成绩上面我先把dikjstra算法做一下介绍。
?再读游览计划标题
游览计划的标题也可以归咎于为以下说法，一张自驾旅游度假道路图显示了都会及公路的数目，高速公路长度、过路费。现在要经过一个算法，找一条动身地和目的地之间的最短路径。假如有及一条路径都是最短的那么说需求输入最便宜的一条路径。
实践在互联网路由规划中，都会代表着网络上的节点，调整后公路代表互联网上的通道，公路长度普通代表互联网通道的传输功能，过路费用的数据在实践工程中能够代表着线路其质量等参数。
示例代码中的变量阐明：NMSD辨别代表都会个数、调整后公路条数、游览者初始都会编号、游览者目的地城市编号，其中包括N2≤N≤500都会的个数，三维数组g存储高速公路的相关信息，记载初始都会、起点都会、高影视题材速公路长度、免费额，如g[i影视题材][瀑布题材j][1]代表编号为i都会到编号为j都会之间的间隔，g[i][j][2]代表编号为i都会到编号为j都会过路的用度，?哈希表Path记载由旅行者的初始都会S编号为i都会之间的最短路径信息，如起始城市Si之间经由jk学生题材最短，那么说Path[i]值应该是[j,k]留意jk关于先后顺序很敏感。Dis小说题材t数据记载游览者起始市S编号为i都会之间的间隔数值，cost数据记载游览者起始市S编号为i都会之间的破费，Known数组记录城市是否被算法遍历确认，
比方经典中的经典路由协议OSPFOpenShortestPathFirst中的SPF最短路径优先实在就非常清楚的直接表达出了dijks影视题材tra算法的精华，实践上这个算法就是不时找到离起点S前段时间的未确认城市A并尝试通过A直达能不能优化到S间隔，如下所示图所学生题材示：
注：绿色代表终点都会
蓝色代表k小说题材nown形态曾经迭代的都会
白色代表unknown形态的都会
dijkstra算法先要做的就是找到一切未知节点中与起始地S前段时间的都会A由于经城市A现在离S前段时间，那么说经城市A直达，就有能四季题材够会缩短S其它目的地城市D间隔。比方上图中SA间隔是2停止现在是S其它都会中距离最短的一条路径，那么说经A跳转则有能够取得一个比从S直接把到D更短的途径。上图例中在运用A行过一轮迭代以后，SD间隔也可以由直接访问的间隔6优化为经A直达的间隔5完成4一轮优化后A节点会被记录为known形态，接上去会用非known形态的节点中找到离初始点最近的谁人做下一轮迭代。如下所示图所示：
如图所示，这轮迭代中间隔初始点D前段时间的都会是B那么说，算法会重复刚刚的具体步骤，实验经过B直达去起点S优化到其它unknown形态都会的间隔，这个例子中，也可以将由SC间隔优化到4迭代完成后b会被标识作文题材为known形态，算法继续迭代，直到一切都会所有瀑布题材形态所有都是known为止。
以go言语为例，代码如下所示：
packagmainimport"fmt""strconv"constNint=4constINFint=501varg[N][N][2]intvardi[N+1]intvarpai[N]intvarknown[N]boolvarn,m,s,d,i,j,t1,t2,vintvarpathmap[int][]intfuncfindMinDist{disMin:=INFfori:=0;i<n;i++{if!known[i]&&dis[i]<disMin{v=idisMin=dis[i]}}}funcdijkstra{fork:=1;k<n;k++{findMinDist//先把状态为unknown节点中到终点间隔最短的点 //接上去依照之前引见的算法运用间隔最短的节点对其它节点停止优化 known[v]=truefori=0;i<n;i++{if!known[i]&&g[v][i][0]<INF{ifdis[v]+g[v][i][0]<dis[i]{dis[i]=dis[v]+g[v][i][0]pay[i]=pay[v]+g[v][i][1]footPrint:=path[v]path[i]=appendfootPrint,v}elsif!known[i]&&dis[v]+g[v][i][0]==dis[i]&&pay[v]+g[v][i][1]<pay[i]{pay[i]=pay[v]+g[v][i][1]}}}}}funcmain{//以下是初始化城市个数、高速公路条数、初始都会、起点都会的任务 path=makemap[int][]intn=4m=5s=0d=3//初始化时先把path对应的途径置为空 fori:=0;i<n;i++{s1:=make[]int,0path[i]=s1}//初始化化时先把g数组对应的途径置为空 fori=0;i<n;i++{forj:=0;j<n;j++{g[i][j][0]=INFg[i][j][1]=INF}}keyInput:=[...][5]int{{0,1,1,20},{1,2,3,30},{0,3,40,10},{0,2,10,20},{2,3,2,20}}//把路途相关信息写入g数组 for;m>0;m--{i=keyInput[m-1][0]j=keyInput[m-1][1]t1=keyInput[m-1][2]t2=keyInput[m-1][3]g[i][j][0]=t1g[j][i][0]=t1g[i][j][1]=t2g[j][i][1]=t2}//fmt.Printlng//初始化known数组全部置为fals形态 fori=0;i<N;i++{known[i]=fals}//初始化起点到编号为j节点的间隔及花费信息 forj=0;j<n;j++{dis[j]=g[s][j][0]pay[j]=g[s][j][1]}dis[s]=0pay[s]=0dis[n]=INFdijkstra//挪用dijkstra算法 ifdis[d]<INF{fmt.Println"Distancis"+strconv.Itoadis[d]+",Thecostis"+strconv.Itoapay[d]fmt.Println"Pathis",path[d]}}例程中各城市之间的之间的关系如下所示，
从A0号城市)短片题材D3号城市）最短路径需要经B1号城市）和C2号城市)直达，途径用红色标出
代码运转后果如下所示：
Distis6,Thecostis70Pathis[12]契合预四季题材期。
路由协议的中心成绩到底是啥？
聊完经典算法dikjstra后我终于等到也可以联合互联网中的实践使用，也就是路由协议的话题了实在现在种种路由协议的坑本质上都是从dijkstra算法承继而来的固然这里并不是说dijkstra算法不优秀，而是与路由算法的角度差别，笔者总结路由协议存在成绩，次要是由以下几方面造成的
Dijkstra实质上是游览者算法而不是互联网路由算法
复杂来说dijkstra为游览者而设计的站在游览者的角度去考虑问题，但是从网络的实践运用状况上看，算法中的游览者对应使用层的数据包，依照互联网构造层的明确分工界线，使用层只担任提供更多目的IP餐厅地址，详细怎样路由到目的IP完完全全不是数据包的发送方需要关心的成绩。
而站在互联网装备的角度上看，假设下面例程中的都会A下台路由器，那么说它上就可要完全掌握最优途径前后一个城市C路由相关信息就可以了完全掌握整体途径的全貌，费时艰苦不说，也没有必要。
但在实践工程中假如不存整体最优路径的全体路由信息，就能够会成环，
以上图为例，A节点以为发送给D包应该经过BB以为包应该经过CC路由表又把包路由给A也就是数据包会在这个互联网环里转圈，永远是也出不去，像BGP签署去环的次要办法就是检查路由信息里是否包含了本身的AS编号，假如包括则拒绝接收。但鱼与熊掌不行兼得，要想完完全全防止环路，就要牺性肯定的效率方面，现在djklstra算法框架下建立的路由协议，都要正视频题材面临这个可以选择，这可能也是将来路由协议优化的一个重要方向。
Dijkstra算法的工夫庞大度决议路由签署干脆被限制节点数，干脆将将网络分区。
熟习算法的小伙伴一定一眼就能看出来，Dijkstra算法的工夫庞大度接近于On*n并且我刚也讲了Dijkstra每步迭代的之间是有前后先后顺序之间的关系的很难像搜素那样停止散布式并行盘算革新。因而这也就使得路由签署必需要被限制治理节点的个数，由于假如要给整体互联网上几十亿节点跑一遍Dijkstra算法，很显然不是一种可行的盘算具体方案。
而大大降低治理节点的形式有两种，一种是把网络分区，内部网关协议EGP只处置区和区之间的路由，外部网关协议IGP只处置区域内外部的互联网之间的关系。这也是为何路由签署会分为四季题材EGP内部网关协议和IGP外部网关签署两大类协议的基本缘由。
内部网关协议中的BGP把整体互联网分为几万个自治区（AS外部网关协议OSPF签署要把互联网分为差别AREA 实质上都是受Dijkstra算法工夫庞大度的影响而做出的让步。固然也也可以直接把被限制治理的互联网节点个数，比方RIP就把路由的步数设置在16跳以内，这在处置小规模互联网区域内时也不失一个好的形式。
固然本文只是把成绩提出来了详细怎样优化处理，笔者也正在考虑，现在也没有答案，假如列位读者有好的一些想法欢送私信或者留言。最初笔者还是要重申一下，假如Facebook关于刚出的史诗级毛病都没给出一个靠谱的处理晋级强烈建议，就忙着去炒作啥元宇宙，那这样的造出来的元宇宙能够波动性也会堪忧。
原文链接：https://blog.csdn.net/BEYONDMA /article/details/121065653?ops_request_misc=%257B%2522request%255Fid%2522%253A %2522166856496116782414955790%2522%252C%2522scm%2522%253A %252220140713.130102334.pc%255Fblog.%2522%257D&request_id=166856496116782414955790&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~times_rank-27-121065653-null-null.nonecase&utm_term=%E9%A 2%98%E6%9D%90
未经允许不得转载：题材网 » Facebook路由事故未圆，何能元宇宙？
