Computer Networks and the Internet

Graph theory is an excellent method for mapping computer networks and looking for weaknesses in them.

What You Should Learn

  • The definition of a computer network.
  • How computer networks can be modeled with graphs.
  • What a "single point of failure" is and how it relates to bridges

Computer specialists have a special word for a bridge: single point of failure. They use the term to refer to one thing that, if it breaks, will leave an entire system unusable. Take a look at the simple computer network in the diagram below. Each of the c vertices represents an individual computer in a small office. The r vertex is a piece of equipment called a router. All of the computers connect the router which then connects to the Internet. This arrangement allows all of the computers to share one Internet connection.

In our example, the router is the single point of failure. If it goes down then all ten of the other computers will loose their connection to the Internet.

graph 46

In many cases a single point of failure is unavoidable. To fix the situation in our previous example we would have to have (and pay for) a second Internet connection and a second router into which all of the computers connect. Of course, every computer would also have to have a second network card to make the connection with. Basically the company would have to create a second network parallel to the first one. A second, more cost effective plan, would be to have a second router in a storage cabinet. In the unlikely event that the first router fails, the second one can be installed leaving the office with a minimal amount of down-time.

The Internet

The Internet is often described as a "network of networks". The idea is a simple one. Take networks from all over the world and let them connect to each other. The Internet has built in "redundancy" that was designed to allow it to work around the failure of individual parts. The graph below is a simple example. Say a computer in network n1 in Southern California is trying to connect to a web site on a web server in network n7 in London. The direct route is through the n1 - n7 edge but let's say that line is broken. The way the Internet's routers are setup the attempt will automatically be rerouted through another available path, for example n1 - n2 - n6 - n7.

graph 47

Minimal Graphs and Trees >><< Broken Graphs, Exercises