生成树是一样重要的接受和传播以太网,从而能够连接以太网段不创建循环和包的风暴,它的发明者,拉迪亚帕尔曼说,她总是认为这是一个坏主意。
毕竟,帕尔曼一层3向导。她设计的路由协议层3的数字设备公司dec网络架构通过ISO,更名为到底是什么——却,,今天仍然广泛部署。“以太网(2层)应该只是和邻居说话的一种方式,”她说。“路由之间的链接是第三层的工作。当我试图争辩说,我们可能需要转发数据包从一个以太网链接到另一个,回答是“客户永远不会想要这样做”。他们的看法是第三层只是不必要的字节的线。”
但没多久,短视变得明显。
客户做的,毕竟,想说从一个以太网到另一个地方。
第3层交换机(路由器),不能直接转发数据包,除非最后节点实现路由器的第三层协议。“所以有必要发明某种组装机,所谓将成为一座桥梁,可以向前以太网数据包,而不需要结束节点以不同的方式做任何事情比以太网邻居说话的时候,“帕尔曼说。
写在墙上,帕尔曼的经理在12月转向她的分布式算法和专家给了她他认为是一个复杂的问题:“想出你塞在一起没有配置,它打破了所有的对称性和与一个出来,无路由循环的拓扑来转发数据包,”帕尔曼回忆说。
”他认为这将是非常困难的,我认为很有趣,他说,“让它规模,使算法的开销一个常数,所以不管有多少桥梁和链接网络,内存需要运行这个东西的数量将是一个常数。””
没有什么是一个常数,帕尔曼说。“也许线性如果你是幸运的,更有可能的是N的平方。”
他给了她这个难题在周五下午和下周走了所有和遥不可及的。但那天晚上帕尔曼打瞌睡,闪光灯泡爆炸了。“我意识到,‘哦,我的天哪,这是微不足道的,此外,它鳞片作为常数。””
生成树诞生了。
这真是一个简单的算法,帕尔曼谦虚地说。“如果你是一个桥有六个港口,每当你看到一个生成树信息在任何港口,你必须把它比作一个存储。包中有三个主要领域。最好的ID是根桥接器你有听说过,你的成本,然后自己的ID。如果你将这些作为一种multi-precision整数,然后数值小的“生成树信息值是更好的。如果你只是收到了比你存储,你扔掉,和存储新的。
“这种方式每个人都最终会收敛在桥上最低的ID是根。所以你只需要记住每个端口上的一个消息和消息是大约50个字节长所以需要一座桥六端口300字节运行算法无论有多少桥梁和链接。”
她拍摄从床上把想法写下来吗?
“绝对”帕尔曼笑着说。“我真的会生气如果我等到第二天,忘记这是什么。”
不需要多长时间来完善这个想法,因为它本质上是如此的简单,她说。她花了下个星期的星期一和星期二详细写出来,这就像25页。”但我的经理还是走了,我不能集中注意力在任何事情上,因为我觉得这个东西很酷,所以我花了剩下的星期在一首诗在我论文的文摘发表的算法:“
Algorhyme
我认为我永远不会看到的
图比树更可爱。
树的关键属性
是无路由循环连接。
树必须确保跨度
所以数据包可以到达每一个局域网。
第一根必须选择
通过ID是选举产生的。
从根最小成本路径跟踪
这些路径放置在树上。
网是由像我这样的人。
然后桥梁找到一个生成树。
简单而优雅,生成树不应该超过几年,直到人们改变他们所犯的错误,采用了第三层,帕尔曼说。“还有其他的第三层协议,使桥梁容易摆脱。不幸的是胜出的一个IP。在IP,每个链接都有一个不同的地址,所以需要很多的配置路由器知道哪个地址是在哪个港口,和结束节点必须改变他们的第三层地址如果他们移动。
“相比之下,ISO CLNP数据包格式(无连接网络层协议)的底部标高路由是一整块的网络,有很多链接的共享同一块地址,在块内的路由器不需要配置,和结束节点可以在不改变他们的地址块。如果互联网采用CLNP、桥梁会死的和平。”
鉴于IP和生成树的缺点以太网,帕尔曼决定是时候来创建一个新的概念;结合以太网的优点(便于管理)和IP(最优路线,多路径)。这个想法一直在IETF标准化颤音(透明互连的大量的链接)。而不是做生成树,一种新型的桥(RBridge呼吁“路由桥”)使用是什么,寿命是协议计算层存在的路径。
“如果你有一个很大的以太网可以取代任何子集的桥梁与RBridges结束节点仍然认为他们只是在一个以太网和现有的开关还在做他们的工作。但你取代RBridges,拓扑你会得到更好的利用,它将会更加稳定。”
使它更容易迁移到大,平的,2层网络,这是今天风靡一时。
所以即使生成树逐渐消退,帕尔曼保证至少有一个她的发明未来的网络运行。