◇◇新语丝(www.xys.org)(xys3.dxiong.com)(www.xysforum.org)(xys2.dropin.org)◇◇

　　美丽的生成树

　　作者：JJZ

　　如果你把你家里两台计算机联起来, 即使没与外界连通也是一个计算机网络。
计算机网络的发展历史就是把一个个独立的小网联起来从而形成的大网络的历史。
许多杰出的科学家, 工程师为网络和Internet的发展作出了重要贡献。 其中也
有一个让人佩服的女豪杰--拉迪亚·珀尔曼 (Radia Perlman) 博士。

　　二十世纪70年代初期局计算机域网有了快速的发展, 通常小网络是用广播的
方式传输数据的, 就像在一个教室, 当老师叫一个学生的名字大家都能听到一样, 
一个村庄最多装个扩音器就能让全村的人听到广播了。但是你很难想像把这种小
广播通信的方式用在一个大都市里, 小区域的范围里用广播的方式通信还是有一
些好处的。 例如以太网就是用了(CSMA/CD)技术规使多台电脑共享一个通道的广
播方法传输数据。随着局域网的发展, 需要把独立的小网络连在一起, 网桥, 交
换机就是一个能把几个小网络联起来的设备。通过记录分析网络上计算机设备的
MAC地址, 网桥可以判断它们在什么位置(哪一个网段)上。 只有格式完整的数据
包才能从一个网段进入另一个网段, 冲突和有错误的数据包则都被隔离了。 因
此网桥在网络物理层的中继器之基础上又上了一层, 这就OSI网络模型的第二层
数据链路层(Data Link Layer) 。 为了防止一个接点的失败导致整个网络联接
功能的丢失, 通常网桥(交换机)的网络设计中有冗余的链路及设备作备用。虽然
冗余设计可能消除的单点失败问题，但也导致了网络交换环路的产生，它会带来
如下问题：1.广播风暴, 2.同一帧的多份拷贝, 3.不稳定的MAC地址表, 其中广
播风暴可以引发整个网络的崩溃。在交换网络环路中很容易出现广播风暴, 这有
点像村庄里广播扩音器引发出的尖叫声音不断扩大, 直到把扩音器关掉尖叫声才
能停止一样。网络交换环路中的广播风暴不断拷贝, 循环转发直到整个网络的崩
溃为止。 许多网络科学家, 工程师为了解决网络联接, 交换环路, 广播风暴等
问题, 费尽心机百思不得其解。这个看起来很简单的网络交换环路问题, 一直没
有理想的答案。

　　珀尔曼在MIT数学硕士毕业后到了一个叫BBN的公司搞网络设备的软件研发。 
1980年, Digital Equipment Corp 的经理发现了珀尔曼的网络技术才华, 珀尔
曼被邀请到DEC工作。当时DEC正在研发一种可靠性更高的计算机网络设备, 珀尔
曼给DEC的研发团队带来他们想要的东西, 她运用极强的数学功力很快就找到解
答。 1983年, 珀尔曼发明了Spanning Tree Algorithms 生成树算法, 研制出了
用于网桥(交换机) 设备的 Spanning Tree Protocol(STP) 生成树协议。

　　生成树协议拓扑结构的思路是: 不论网桥(交换机)之间采用怎样物理联接, 
网桥(交换机)能够自动发现一个没有环路的拓扑结构的网路，这个逻辑拓扑结构
的网路必须是树型的。生成树协议还能够确定有足够的连接通向整个网络的每一
个部分。所有网络节点要么进入转发状态，要么进入阻塞状态,这样就建立了整
个局域网的生成树。当首次连接网桥或者网络结构发生变化时，网桥都将进行生
成树拓扑的重新计算。为稳定的生成树拓扑结构选择一个根桥, 从一点传输数据
到另一点, 出现两以上条路径时只能选择一条距离根桥最短的活动路径。 生成
树协议这样的控制机制可以协调多个网桥(交换机)共同工作, 使计算机网络可以
避免因为一个接点的失败导致整个网络联接功能的丢失, 而且冗余设计的网络环
路不会出现广播风暴。

　　珀尔曼还写过一首诗来描述生她的成树算法：

　　I think that I shall never see
　　A graph more lovely than a tree.
　　A tree whose crucial property
　　Is loop-free connectivity.
　　A tree which must be sure to span.
　　So packets can reach every LAN.
　　First the Root must be selected
　　By ID it is elected.
　　Least cost paths from Root are traced
　　In the tree these paths are placed.
　　A mesh is made by folks like me
　　Then bridges find a spanning tree

　　许多人很难解理生成树算法。 看了珀尔曼的诗后, 感觉她把网络的拓扑结
构描绘成了一幅像有棵美丽的树的风景油画。看过几个中文翻译的这首诗, 觉得
不很理想。 这里自己试着翻译一下, 还是找不到珀尔曼那种自然美的感觉。

　　人生难识一幅图
　　美丽比得上棵树
　　树有重要的特征
　　其无连接之环路
　　一棵树可延而生
　　数据能到达网络
　　首先选择树主根
　　选择 I D须借助
　　溯根求本寻捷径
　　枝径安置皆随布
　　我等绘网勤努力
　　网桥便有生成树

　　珀尔曼的工作实际上是给网络(Internet)制定了一个基本的数据传输的方法, 
生成树协议能保证数据包传递到网络任何一个网段, 生成树协议被IEEE定为网桥
(交换机) 技术的标准协议(802.1d), 珀尔曼还为IS-IS, OSPF链路状态路由协议
的算法, 标准, 及发展作出了重大贡献。实际上是珀尔曼发明了STP生成树协议
之后局域网和广局域网才有了大规模的联接, 珀尔曼博士因此还被人尊称为互联
网之母。

　　1988 年, 珀尔曼在MIT完成了她的计算机博士科学学位。 珀尔曼在1993年
离开了DEC去了Novell工作, 1997她又加入Sun Microsystems 公司。 珀尔曼博
士拥有80多个技术发明专利, 其中40多个是在Sun Microsystems 公司发明的。
珀尔曼博士还被哈佛大学和华盛顿大学聘请为客座教授。 珀尔曼博士在数据通
信领域的经典著作有: “Interconnections: Bridges, Routers, Switches, 
and Internetworking Protocols"; and "Network Security: Private 
Communication in a Public World." 珀尔曼博士被授予了许多杰出工程师奖, 
她被评为20个数据通信领域最有影响力的人之一。

　　参考文献：

　　http://en.wikipedia.org/wiki/Radia_Perlman
　　http://web.mit.edu/invent/iow/perlman.html
　　http://www.nationmaster.com/encyclopedia/Spanning-tree-(networks)

(XYS20090124)

◇◇新语丝(www.xys.org)(xys3.dxiong.com)(www.xysforum.org)(xys2.dropin.org)◇◇