The Evolution of the Internet: The spanning tree protocol, a major achievement in Internet routing

Radia Perlman, inventor of U.S. Patent No. 5,086,428, issued February 4, 1992, will be inducted into the Inventors Hall of Fame on May 5, 2016.

The use of switched network environments to forward digital data transmission packets known as frames is a very basic concept in networking and telecommunications. Network switches work to direct frame traffic by broadcasting frame data it receives to other switches which are linked to it. Switched network environments are created whenever multiple devices communicate on the same network. To get all computing devices with Internet capabilities communicating on the same network, however, many times a network bridge is required in order to enable communication of wired Ethernet devices with wirelessly connected devices, for example.

Standards in telecommunications and networking are developed by the Institute of Electrical and Electronics Engineers (IEEE) and both local area networks (LAN) and metropolitan area networks (MAN) are standardized by the IEEE 802 family of networking standards. The networking architectures created by these IEEE standards have enabled a great deal of flexibility and security in network management. Each new release of IEEE networking standards represents advances made in the field of telecommunications which support more robust systems for data transmission.

While the history of Internet development involves many names and was not reliant on a single discovery, it is also true that certain innovations have done more to enable better networks for all. It is with that idea in mind that we’d like to profile the achievements made by Radia Perlman, the inventor of spanning tree protocol (STP) and a 2016 inductee into the National Inventors Hall of Fame. Thanks to spanning tree protocol, switched network environments are capable of connecting bridges and switches with multiple paths for data transmission redundancies without those redundancies causing a network loop, which can seriously degrade network service. Without STP, a single frame looping on an Ethernet network would create out of control data traffic that would prevent communications of all other data. February 4th marks the 24th anniversary of the issue of the U.S. patent protecting spanning tree protocol.

Perlman, the inventor of spanning tree protocol, was born in Portsmouth, VA, and pursued her collegiate studies at the Massachusetts Institute of Technology. After completing her Ph.D in computer science, she would go on to work for computing tech developer Digital Equipment Corporation (DEC), which she joined in 1980. Perlman would complete her pioneering work in STP while at this company, helping to transform Ethernet from a small-scale networking solution into networks that can handle hundreds of thousands of nodes spread in different areas.

The algorithm for implementing spanning tree protocol was invented by Perlman in 1985 and introduced in DEC’s two-port Ethernet bridge, which was first sold in the mid-1980s. STP works as a distributed algorithm which helps network bridges to automatically adjust to link failures or the installation of new bridges in a data link layer computing topology. At the time of its development, it enabled “plug and play” style architectures to which additional switches could be installed without creating network loops. STP was also capable of supporting future generations of applications and network services and their ability to work with earlier technologies. The STP algorithm was incorporated into IEEE media access control standard 802.1D, published in 1990, and serves as a basic component of LAN architectures.

To prevent loops in a switched network environment, spanning tree protocol analyzes the topology of switches that exist in a network and shuts off links between switches that could cause loops; the STP algorithm is performed every time new bridges are connected to or removed from a network. When a bridge receives a bridge protocol data unit (BPDU), issued in response to the topology change, it begins STP by selecting a root bridge that will serve as the central bridge through which all data flows. Once a root bridge is selected, the shortest path between all other bridges and the root bridge is then determined, which helps identify the root port on each bridge. Upon the determination of each bridge’s shortest path and the root port through which to send frames to the root bridge, all of the other ports on the bridge are closed. This enables a bridge to continue broadcasting frames to the root bridge without sending that frame to a bridge that has already received the data, which would create a loop.

On February 4th, 1992, the U.S. Patent and Trademark Office issued U.S. Patent No. 5,086,428, entitled Reliable Broadcast of Information in a Wide Area Network. Although this patent does not specifically cover the spanning tree protocol, it protected a claimed a method for aging and purging packets expiring over time from storage in each node of a distributed system of nodes. The method involves causing each node to regularly modify the data to indicate that less time remains before each packet expires than the time that remained before the data was modified and then causing each node to wait for a purge time equal to the time necessary for a packet to propagate through the distributed system. The use of the purging packet in this networking innovation helps to renounce previously originated link state packets in order to transfer networking duties from one router to another.

The spanning tree protocol was a major advance in computer networking at the time of its inception in the 1980s. However, as with most computing technologies, the passage of time brings ever new computing architectures and capabilities and there are instances now where STP can actually create issues in network design. Thus the work of Radia Perlman continued on at her new position with Sun Microsystems, where she developed a second technology that will put her in the National Inventors Hall of Fame: U.S. Patent No. 7,339,900, titled Method and Apparatus for Preventing Spanning Tree Loops During Traffic Overload Conditions (Reader Note: This is one of the few patents reviewed by this writer which contains a poem in the related art section of the description and the oddity may be worth an extra glance).

Issued March 4th, 2008, the ‘900 patent protects a method that prevents loops from occurring when spanning tree configuration messages are lost while executing an STP across bridges in a network; the method involves executing the STP which configures each port into either a forwarding state or a backup state on a bridge, monitoring ports coupled to the bridge to determine when messages are lost by the ports due to temporary network conditions and refraining from forwarding messages to or from the port until no messages are lost by the port for an amount of time. This method prevents loops created from messages lost during temporary network conditions, such as when poorly performing bridge hardware is incapable of processing spanning tree configuration messages during heavy traffic, causing the message to be lost and loops to be created in the network.

Radia Perlman’s work in developing answers to looping problems in networks has earned a great deal of recognition from around the technology world. Along with her induction this year into the National Inventors Hall of Fame, she is also a 2014 inductee to the Internet Hall of Fame and in 2015, she was elected to the National Academy of Engineering for her contributions to Internet routing and bridging protocols. She also holds more than 100 U.S. patents, making her a very prolific American inventor.