The Spanning Tree Algorithm for Beginners

A spanning tree is a subset of a network that reaches all nodes in the network and has no loops. The "nodes" are the red circles in the picture to the left. The spanning tree is the blue path through the network. Note that the path spans (reaches) all the nodes, but there's only one path to each node from any other node. There are no loops. It's a tree. Granted, this example makes it look like kind of a funny tree, but use your imagination.

The spanning tree algorithm converts a mesh network into a tree-shaped network. To understand a mesh network, think of the Los Angeles freeway system, with its numerous interconnected roads. To understand a tree, think of a real tree with a root and branches, but no interconnected, looped branches. Or think of an org chart (an upside down tree) or a file system on your computer that has directories, subdirectories, and files. Going back to the Los Angeles freeway system, to understand the spanning tree algorithm, think of yourself sitting at home in, let’s say Redondo Beach, trying to get to San Bernardino.

In the computer field, a mesh network has the advantages of backup links and multiple paths, in case a path goes down or gets as crowded as the 101 freeway during rush hour. But a mesh also has the disadvantage that data could reach the recipient more than once, which would be bad. So we need an algorithm that lets us build networks with redundancy but ensures that data travels a single path to arrive just once at the recipient. Some spanning tree algorithms also ensure that the data takes the shortest path, though that’s a particular type of spanning tree algorithm, a so-called minimum spanning tree algorithm.

It’s not accurate to say that Radia Perlman’s spanning tree algorithm is used on the Internet, which is a misconception that I see so often that it inspired me to write this blog post. The first few words of this beautifully-written blog, for example, are misleading. Dr. Perlman’s algorithm isn’t used to get data to Google, YouTube, etc., (well, unless you count once the data gets into Google or YouTube’s internal network.) Her algorithm is used inside enterprise networks to build a path to a recipient across a mesh network of interconnected Ethernet switches. Enterprise networks include the internal networks at corporations, universities, government agencies, ISPs, etc. (Note, that it’s used inside ISPs, not ISP-to-ISP, though).

Spanning tree algorithms are used in many aspects of computer science and were not invented by Radia Perlman. The first algorithm for finding a minimum spanning tree was developed by Czech scientist Otakar Borůvka in 1926 (see Borůvka's algorithm). Its purpose was an efficient electrical coverage of Moravia, a region in Central Europe. Spanning tree algorithms are used by routers too, not just switches, but not on the routers that connect the Internet (which run Border Gateway Protocol, which uses a distance-vector algorithm, not link-state and spanning tree). Oh dear, now I’m getting into jargon.

Here are some good resources regarding the spanning tree algorithm:

• Wikipedia’s article on minimum spanning trees is good.
  
• Wikipedia’s article on the particular spanning tree protocol that Radia Perlman invented for use on internal switched (bridged) networks is good too.
  
• Cisco's article on the rapid spanning tree protocol used by switches is a must-read for those of us in the networking field.
  
• I wrote about Radia Perlman last year for Ada Lovelace Day.
  
• Finally, be sure to read Dr. Perlman’s famous poem about spanning trees at the bottom of this terrific interview with her.
  

Ada Lovelace Day Hangover

I feel wiped out today. I only had one tiny glass of wine with my women friends, but I drank abundantly from the fountain of inspiration that was Ada Lovelace Day. I spent many hours reading hundreds of posts about terrific women in science and technology. Today I'm trying to make sense of it all. Here are a few insights I came up with:

• The shorter blogs were the best. Mine was too long. :-)
• Bullets are good.
• Attention spans are even shorter than they were last year when we celebrated Ada Lovelace Day. Are they going to keep getting shorter? What has Twitter done to us?
• Blogs that taught me something held my interest.
• The best blogs included pictures, videos, and personal stories.
• The most moving blogs were about multiple women and communities of women.
• Good writing matters. The blogs that I read from beginning to end were written by professional writers or people who blog frequently.

I made a list of my favorite blogs here:

• My favorite blog was an appeal to women from a male manager looking for programmers. He's an experienced writer and the writing in this post really moved me: http://www.jgc.org/blog/2010/03/appeal-to-unremarkable-women.html
  


• I like this next one because of its great use of graphics and portraits: http://www.spellboundblog.com/2010/03/24/ada-lovelace-day-portraits-of-women-in-technology/


• This is a nice wacky one about a German mathematician, Emily Noether, who lived near where I lived when I spent my junior year abroad in Germany at the University of Erlangen: http://thonyc.wordpress.com/2010/03/24/emmy-and-the-habilitation/


• I liked learning about Hypatia. I'd never heard of her: http://utterlyelastic.wordpress.com/2010/03/24/hypatia/


• Ada Fruit blogged about a woman once per hour! Ada Fruit is an interesting company that builds and sells DIY open source electronics equipment: http://www.adafruit.com/blog/


• This one is interesting because it's about a community of women in systems and because it comes from Turkey (most blogs were from Europe and the US): http://www.cmpe.boun.edu.tr/%7Ebayhan/AdaLovelaceDay2010.html

• Anita Borg's compendium here has a list of some really good blogs, including mine: http://anitaborg.org/news/archive/anita-borg-institute-and-friends-celebrate-ada-lovelace-day/


• This isn't really a blog, but Victoria Law's historiography is a terrific way to learn about Ada Lovelace: http://hubpages.com/hub/Historiography-of-Ada-Augusta-Lovelace


• This isn't a blog either, but it shows a video from a potluck un-conference hosted by Ada Lovelace Day founder and organizer, Suw Charman-Anderson. Thank you, Suw, for all your hard work making such a successful day! http://blog.findingada.com/blog/2010/03/25/video-ald10-potluck-unconference/

Melissa Hathaway: Internet Security Advocate

In honor of Ada Lovelace Day, today I am writing about a woman in technology. In particular, my topic for today is Melissa Hathaway, an Internet security expert. Melissa Hathaway serves as Senior Security Advisor for Cisco Systems and as Senior Advisor for the Belfer Center for Science and International Affairs at Harvard's John F. Kennedy School of Government. Ms. Hathaway has a B.A. degree from the American University in Washington, DC, and graduated from the U.S. Armed Forces Staff College with a special certificate in Information Operations.

In 2009, Ms. Hathaway worked in President Obama's administration as Acting Senior Director for Cyberspace for the National Security Council and the Homeland Security Council. In this role, she carried out an interagency review of cyber security plans, programs, and activities, providing an important link between the Bush and Obama administrations. During Bush's administration, Ms. Hathaway served as Senior Advisor to the Director of National Intelligence and as Cyber Coordination Executive. In August, 2009, Ms. Hathaway returned to the private sector where she is President of Hathaway Global Strategies, LLC.

If you made it through all those impressive titles and are still with me, I'd like to explain why I admire Ms. Hathaway. I admire her because, like our hero, Ada Lovelace, she's a good communicator and team player. To understand the importance of this, you need to understand the network security field.

OK, I'm not being politically correct here, but let's just come right out and say it: the network security field has generally been male-dominated with a pervasive attitude of cowboy one-up-manship. Many old-timers learned security on their own, spending countless Mountain Dew-powered hours working alone in a lab, tinkering with hardware firewalls, and penetration-testing corporate networks. You just need to read that phrase, penetration testing, to know that this was a male-dominated field.

Ms. Hathaway represents an evolution in the security field to a bigger focus on communications and collaboration. Her work to bridge the Bush and Obama administrations' security programs demonstrates that, as does her work during the Bush administration on the Comprehensive National Cybersecurity Initiative (CNCI), where she built consensus among nearly two dozen diverse organizations. You can read more about her work in that area in this IEEE interview.

To protect networks from attackers, security professionals need to collaborate with other stakeholders, which can include co-workers, business managers, other companies, and governments. They should share information about problems and solutions, think in terms of systems and policies, and understand users, not just hardware. Soft skills, often more associated with the Yin world of business than the Yang world of network security, are just as important as engineering skills.

An important area for collaboration (that is especially suited to Ms. Hathaway's background) is in the private/public interface. Despite all the talk about Cyber Czars and Internet security laws, most of the Internet is privately owned. Governments need to collaborate with businesses. Governments also need to work with other governments in an international push to avoid a cyber meltdown.

As an engineering instructor, I'm especially pleased when I hear Ms. Hathaway comment on the need for practical training for security professionals. Using terminology from government hiring practices (which hopefully will become more popular in industry as well), she talks about the need to understand the knowledge, skills, and abilities (KSAs) required of security practitioners, engineers, CIOs, and CSIOs.

In this video from Cisco, about 29 minutes in, I found myself cheering as she discussed the importance of on-the-job training that provides real-life practical exercises. She mentions, for example, lab exercises that might let learners deal with the Conficker worm in a simulated lab, or analyze an infected thumb drive, or configure protections from a distributed denial of service. She suggests that the exercises should also help students learn soft skills where they can practice responding to a security breach and communicating the problem to executives. In turn, executives should practice communicating about the problem to employees, customers, and governments.

Ms. Hathaway also talks about the importance of telling stories, certainly a tried-and-true method of education. She suggests explaining cyber security in simple terms, helping people understand that online shopping could be affected by an attack, for example. Ms. Hathaway is skilled at helping the layperson understand security risks, as can be seen in this paper she wrote about the five myths of cyber security.

In summary, I feel privileged to have this opportunity to blog about a modern technical woman, a person who demonstrates some of the same skills that Ada Lovelace had, and who continues to persevere in a male-dominated field (though that is changing!) in her essential role as an Internet security advocate.