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

By Steve Brachmann
February 4, 2016

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

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.

reliable broadcastOn 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 preventing loopsTree 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.

The Author

Steve Brachmann

Steve Brachmann is a writer located in Buffalo, New York. He has worked professionally as a freelancer for more than seven years. He has become a regular contributor to IPWatchdog.com, writing about technology, innovation and is the primary author of the Companies We Follow series. His work has been published by The Buffalo News, The Hamburg Sun, USAToday.com, Chron.com, Motley Fool and OpenLettersMonthly.com. Steve also provides website copy and documents for various business clients.

Warning & Disclaimer: The pages, articles and comments on IPWatchdog.com do not constitute legal advice, nor do they create any attorney-client relationship. The articles published express the personal opinion and views of the author and should not be attributed to the author’s employer, clients or the sponsors of IPWatchdog.com. Read more.

Discuss this

There are currently 6 Comments comments.

  1. EG February 4, 2016 9:54 am

    Hey Steve,

    Thanks for noting Ms Perlman’s significant achievement in advancing computer networking. But one also has to wonder under Alice whether US 5086428 would have been deemed a patent-ineligible “abstract idea” by the Royal Nine. That is, unfortunately, how far down the “rabbit hole” we’ve gone with the broken and subjective Alice test which requires no factual record and utterly conflates at least 4 different patent statutes (35 USC 112, 102, 103, and 101, the order they should be considered).

  2. Anon February 4, 2016 10:34 am

    It is not without a certain sad irony, EG, that the historical context of all of this is something that is not noted (or at least, not noted for its significance).

    Prior to 1952, all four different statutes that you reference were part of a single paragraph.

    There was a clear and well recognized reason why Congress acted in 1952 and reset that paragraph into the different statutes that you indicate.

    And yet, today, we have a branch of the government rewriting the law back to a day when that branch did have a certain authority to write law by the common law model.

    Of course, I am referencing the authority supplied to the judicial branch by the legislative branch to determine by common law the meaning of the word “invention.”

    That power ended in 1952.

    ALL of the current “realm” of judicial activism can be tied to the fact that the judicial branch does not want to let go of that power that it once had.

    Patent law is statutory law.

    What the Court does when it chooses to rewrite the law with its implicit and explicit (technological) “scrivining” is ultra vires and without legitimacy.

    Sadly, the branch of the government that should be most upset at this taking of power that does not belong to the judicial branch is so mired in politics and driven by corporate “voices” (yes, Citizens United is a sign of how deep that sickness has gone) that it is apparently incapable of recognizing the parallels with pre-1952 history.

  3. Jim Forster February 4, 2016 11:41 pm

    Radia’s poem at the start of her seminal paper:

    Algorhyme

    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 that 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.
    óRadia Perlman

  4. ms February 5, 2016 10:52 am

    Perlman was already working for DEC when she went back to MIT for her PhD (granted 1988).

  5. Joachim Martillo February 5, 2016 1:40 pm

    The Spanning Tree Protocol, which is synthetic knowledge created or invented by Radia Perlman, represents an innovative method of organizing communications computers/packet switches. It cannot be described of a computerization of a human activity. Correctly written method or system claims, in which the Spanning Tree Protocol represented the innovative element, would certainly have been patent-eligible at the time when Radia invented this protocol.

    The distributed parallel Spanning Tree Algorithm, which the Spanning Tree Protocol uses and which is analytic knowledge derived by Radia, is pure math (technically a graph-theoretic procedure). A claim directly solely to this algorithm would not be patent-eligible.

    Radia makes the distinction between the protocol and the algorithm in the first paragraph of her famous 1985 paper entitled An Algorithm for Distributed Calculation of a Spanning Tree in an Extended LAN.

    A protocol and algorithm are given in which bridges in an extended Local Area Network of arbitrary topology compute, in a distributed fashion, an acyclic spanning subset of the network.

    Backes ‘137 Transparent load sharing for parallel networks is an example of a protocol/method and protocol/system patent whose claims are directed to an extension of the Spanning Tree Protocol.

    This protocol extension is based on redefining the graph that is equivalent to the physical networking and then identifying certain BACKUP links (BLOCKED ports in current terminology) that can transceive packets without causing a looping condition. This extension is meant to make more effective use a bandwidth in the extended LAN. There are better ways to achieve similar results.

  6. Night Writer February 6, 2016 1:05 pm

    >>A claim directly solely to this algorithm would not be patent-eligible.
    @5

    That is the mistake. It should be patent eligible. It is a component to build a machine. And it is not “pure” math whatever in the world that is supposed to mean. No modern thinker that understands cognitive science is going to buy into this pure math nonsense. Your brain is making stuff up. Symbols to process information and represent the world. That stuff is the component of information processing machines.