五一小长假，和朋友开车去了浙江，发现了“基于目的地的最短距离算法”的弊端，也许就是这个算法导致了高速公路在某个时间段的定期规律性拥堵！
从嘉定出发，G1501一路畅通，但是一旦转到G60沪昆高速，瞬间拥堵起来，实际上，早在G1501上时，就有公告牌，说沪昆高速有施工，可是大家还是全部转到了沪昆高速，留下S19/G15成了被抛弃的摆设...知道原因是什么吗？很简单，因为沪昆高速那条路最近！人们太相信导航，很少有人没事研究地图，所以很多人都上了当，当然这并不包括我。很多导航都是根据Dijkstra算法计算最短路径的，除了距离权重外，做得好的也会把施工，拥堵等因素作为权重，但是这都不重要，重要的是Dijkstra算法计算的结果会将到达或者经过同一点的所有流量汇聚到一条路线，这就是问题的根本，这种算法是天生带有汇聚性行为的，这个结果给到达关键节点的某一条路径带来了巨大的压力，这就导致了一到节假日，某些高速公路就会异常拥堵，但是却存在好多好像被人们遗忘的空旷路线。不光是高速公路网，对于城市快速道路网也是一样，好几次，我都是因为不走延安路隧道到浦东，不走南北高架到中环而节省了时间，而延安路隧道几乎就是从延安路到陆家嘴的最短路径，而南北高架路也是从淮海路到北中环的最短路径。
通过对比一下目前的三个大型网络对于理解网络技术是有好处的，它们是高速公路网，铁路网，IP网络。
对于铁路网而言，火车完全根据铁轨怎么分叉而被导向不同方向，道岔工就像一个路由协议一样工作，但是铁路网的路线是事先规划好的，即它是一种统计复用和分时复用相结合的方式。铁路网的特点是，“数据包”(火车头或者动车组)没有自主性，完全依赖事先配置的路由，但是路由会动态调整，如何调整对于特定的时间是精确的，比如每天8点10分扳道岔向左，每天16点34分复位。之所以可以将分时复用和统计复用结合，是因为铁路网上没有瞬时突发流量，一切流量都是可控的，就算春运时期，一辆人满为患的列车和平时一辆空车，在铁道看来，都是一辆车。
对于高速公路网而言，不像铁路网，它本质上是完全统计复用的，但是高速公路网上的“数据包”是自导航自路由的，也就是说往哪里走不受控于任何第三方，全在驾驶员本人，只是“最短路径”已经深入人心，才导致所有驾驶员都开往明明知道会堵的地方，实际上多绕一点路，可能会更快到达目的地，距离成本外还要考虑时间成本。随着各种税费的增加，驾驶员往往会自行避开拥堵，除非他使用了一个完全按照最短路径算法工作的导航。高速公路网的路由实际上就是一种策略路由，而策略完全由驾驶员制定(管制期除外)。正是这种最短距离路由和策略路由相结合的方式使得高速公路往往可以应对突发流量，唯一要注意的是，不要有碰擦等小事故发生，实时的路况信息使高速公路网看起来在运行一种类似CSMA/CD/CA协议。
IP网络就像是铁路网和高速公路网的合体，数据包怎么走完全依赖路由器的路由表条目，完全没有自主性，IP网络更像铁路网，但是却不像铁路网那样分时复用，在复用方式上，它和高速公路网一样，是完全统计复用的。拓扑变更机制的背后没有道岔工，动态路由协议会自行处理拓扑变更，可是由于数据包没有自主性，路由的这一变更会趋向于将流量导向另外一条路线，要么全来要么全走，这就是IP路由的特点，拥堵在IP网络上的表现为：丢包重传，网络变得比较卡，...在存在大量不确定突发流量的情况下，拥堵更加严重。因此基于目标地址的IP路由面对最短路径算法在大流量时的问题要比高速公路网更加严重。幸运的是，你可以依赖策略路由以及静态路由来稍微改变这种情况。
虽然目前看来，所有的这些网络工作得还不错，但是借鉴高速公路网的经验，IP网络的路由也需要做一点改变。
在可达性是问题的时代，路径不多，因此流量也不多(当然，路径的数量和流量是相互促进的关系，在去浙江的路上，朋友说他小时候从南汇进一趟浦西要一天时间...)，确实用一个单一的统一度量来标示每条路径的开销比较简单，因此各种度量加权运算，合并成一个单一的度量，在可达性不再是问题的时代，路径开辟了很多，各种流量也随之增多，那么将每一种度量分开计算就比单一度量要更科学了，针对每一个度量都有一个最小开销，这些度量包括：路径长度，时间开销，丢包率(事故率)，拥堵指数，被监控的程度...我们的目的是到达目的地，更快只是一种方式，时间不紧迫时，同样可以选择更舒适的路径，即，在一种度量上的最优路径可能是另一种度量上的次优路径。以上说的是，当最短路径上的拥堵变成一种成本的时候，就应该考虑下是否用次短路径但最X的路径来平滑这种拥堵成本了。一味地朝着最短路径走是一种偏执的行为。
上述的多度量分开的思想有一个前提，那就是要保证线路的数量以及拓扑，一般而言不管是什么网络，一般都需要环线来疏导过境流量，中心辐射线路来分流核心区域流量，同时需要横贯/纵贯线路来快速引导核心区域外围一端到另一端的流量，如果按照这种模式来考虑，中国的IP网络规划确实不合理，很多大区核心节点之间没有直接或者隔跳互联，二者通信不得不绕道第四方甚至第N方，这就造成了环路拥堵，Chinanet没有贯线，除了要地之外，几乎也很少有辐射线，这非常类似北京的城市道路，上海的城市快速路要更合理一些，辐射线路一般都不是快速路，不过地铁加入进来的话，情况会好很多。
除了度量分开选择不同度量的最优路经这样的算法，当前的路由协议如果加入足够的反馈机制也是可以缓解不少问题的，比如路由器在发现自己过境流量拥堵的时候，主动发送IGP链路状态更新消息，阻止额外的流量再流进来，这样做虽然可以缓解，但是仍有两个问题，第一就是会把流量引入别的一条链路，第二就是会造成过多的收敛行为。所以并不是说只要一发生拥堵，就宣告链路更新，针对第二个问题，在IGP中引入一个“建议更新”我觉得更好，不过这就要再引入一个切断那些“不接受建议”的路由器引入的环路问题。高速公路之所以不会出现环路，是因为驾驶员的路由是自己决策的，不过还真有一些新手或者路盲绕圈的，甚至绕了好几圈才下来...
对比一下中美两国的IP网络布线拓扑，就会发现很多不合理的地方，从北京看丹桥机房到美国纽约，出站跳数要远多于入站跳数，反过来从美国纽约到北京，则出站跳数要小于入站跳数。如果是到安徽合肥，则在入站时可能要绕骨干网环路到北京，如果你觉得纽约和合肥相比有点不妥，那么我用上海到智利瓦尔帕莱索之间的线路测试，同样在中国的跳数要远大于境外跳数，而且运营商切换AS切换相当厉害，大部分运营商都要承载相当多的过境流量，这就说明，国内IP网络还处在相当初级的国道阶段，远未达到高速公路的阶段，但是和高速公路的巨量的收费站相比倒是有一拼，一个数据包可能不止要经过一个运营商网络...除了大环之外，局部辐射互联几乎没有，也没有横贯，纵贯线路，这就只能按照最短路径方案在大环线上堵着并接受检查，除此之外没有其它的方案，个谈不上分开度量选择别的线路了吧。难道这样更能方便审计，更方便wall的效率？我不清楚...当然，由于光速在介质中的损耗以及介质本身的局限，穿越太平洋光缆的时延依然是比较大的，但是这并不是开脱的理由，要知道你在沈海高速上开了一个小时走了100公里，和你在北京北四环开了10分钟走了100米的效果是不一样的。
我下班回家从来都不是走一条路，而是在几天内循环尝试不同路线，后来公司搬家了，我花了好几天时间走不同的路线上下班，迟到，早到...最终发现了5条路线，在不同情况下分别使用其中的一条，可以使上下班的时间固定在某个时间，因此很少出现“今天太堵了，所以来晚了”，“今天没挤上车，所以晚了”这样的吐嘈。当然，个人平时没事就喜欢看地图和路况，这多少也能帮我建立策略路由...
要说世界上第一个看得见用得着的大规模网络，那就是古罗马的道路网了，在那个纷乱的年代，我觉得正是这个道路网维持了罗马帝国对外的霸权和对内的和平，以至于帝国的衰败竟然花了300年之久，当网络被拆毁的时候，罗马帝国事实上便不存在了...在冷兵器时代，拆掉一个网络竟然花了300年，可见这个网络的高可用性设计得多么好。当日尔曼人突破莱茵多瑙防线的时候，这个网络拓扑动态变换，帝国的防御也随之由线型防御转变为纵深防御，在内圈形成新的线型防御，当日尔曼人再次突破内圈时，帝国一分为二，网络拓扑动态更新，但每一个部分依然畅通...值得借鉴吗？实际上，现如今的骨干网自愈环就和古罗马的道路网十分类似...
对当前网络路由的一点想法,布布扣,bubuko.com
对当前网络路由的一点想法
原文：http://blog.csdn.net/dog250/article/details/25488965
