Fault Tolerance and Redundancy: How the Internet Survives Failures

Intermediate35 min3 exercises45 XP

Prerequisites

Python Dictionaries: The Complete Guide with Real Examples Python While Loops: When For Loops Aren't Enough Python Functions: Define, Call, and Return Values

0/3 exercises

A system is fault-tolerant when it keeps working even though some of its parts have failed, and the Internet was built that way on purpose. Construction crews cut cables, storms knock out power to routers, and whole data centers go offline, yet most of the time your messages still get through. The secret is extra parts and extra paths.

What does fault-tolerant mean?

When a system can support failures and still continue to function, it is called fault-tolerant. This matters because parts of complex systems fail at unexpected times, and they often fail in groups: one storm can take out every router in a neighbourhood, and one power outage can shut down a whole building of servers. Fault tolerance lets people keep using the network while the broken parts are repaired.

The benefits reach everyone who depends on the system. Students can still hand in homework during a local outage, a hospital can still look up a patient's records, emergency calls still connect, and an online store keeps taking orders. Engineers get time to fix the fault properly instead of racing against angry users.

The Internet has been engineered to be fault-tolerant, with abstractions for routing and transmitting data. When your chat app sends a message, it does not choose routers or check which cables work today. It hands the message to the Internet's protocols, and they deal with failures underneath: routers find another way around a broken link, and TCP resends packets that were lost. The app sees a message that arrived, and the details of what went wrong on the way stay hidden.

What is redundancy?

Redundancy is the inclusion of extra components that can be used to reduce the damage when other components fail. A car carries a spare tire. A plane has two pilots. A hospital keeps a backup generator for when the power goes out.

In a network, one way to build in redundancy is to have more than one path between any two connected devices. Then, if a particular device or connection fails, later data are sent along a different route, if one is possible. That last part matters: redundancy only helps where an alternative path really exists.

Redundancy has a cost. It usually requires additional resources, such as more cables, more routers, and more money and work to run them, in exchange for the benefit of fault tolerance. On the Internet, the redundancy of routing options between two points increases reliability and also helps the network scale to more devices and more people, because traffic can spread across many routes instead of piling onto one.

How can a program tell whether two devices are still connected?

Here is a small school district network. Each device maps to the list of devices it is directly connected to. A connection goes both ways, so it appears twice: "router A" lists "school", and "school" lists "router A".

To find out whether one device can reach another, the program spreads out from the start the way news spreads: the start tells its neighbours, they tell theirs, and so on. It keeps a list of devices still to visit and a set of devices already seen, so it never visits one twice. If the goal is ever reached, a path exists.

Searching a network for a path

network = {

"school": ["router A", "router B"],

"router A": ["school", "router C"],

"router B": ["school", "router C", "router D"],

"router C": ["router A", "router B", "router E"],

"router D": ["router B", "router E", "library"],

"router E": ["router C", "router D", "data center"],

"library": ["router D"],

"data center": ["router E"],

}

def can_reach(network, start, goal):

to_visit = [start]

seen = {start}

while to_visit:

device = to_visit.pop()

if device == goal:

return True

for neighbour in network[device]:

if neighbour not in seen:

seen.add(neighbour)

to_visit.append(neighbour)

return False

print("school can reach data center:", can_reach(network, "school", "data center"))

Output

school can reach data center: True

Trace the first few steps. The list starts as [school]. Visiting the school adds router A and router B. The search takes router B next (pop() takes the last item) and adds router C and router D. Router D adds router E and the library. The library leads nowhere new, router E adds the data center, and visiting the data center ends the search with True. The seen set is what stops the search from going around in circles, since this network has loops: school, A, C, B and back to school.

Now break things. remove_link makes a copy of the network without one connection, so the original stays intact for the next test.

Breaking connections one at a time

def remove_link(network, a, b):

"""Return a copy of the network without the connection a-b."""

copy = {device: list(neighbours) for device, neighbours in network.items()}

copy[a].remove(b)

copy[b].remove(a)

return copy

damaged = remove_link(network, "router C", "router E")

print("After C-E fails: ", can_reach(damaged, "school", "data center"))

damaged = remove_link(damaged, "router B", "router D")

print("After B-D fails too: ", can_reach(damaged, "school", "data center"))

Output

After C-E fails:      True
After B-D fails too:  False

When C to E fails, data can still go school, B, D, E, data center: the redundant path takes over. When B to D fails as well, there is no route left, so the school is cut off from the data center even though most of the network still works.

Exercise 1: Count the Connections

Write Code

Redundancy costs resources, and one way to measure the cost is the number of connections (cables or links) a network needs. Write count_links(network), which returns how many connections the network has. In the dictionary, every connection appears twice, once for each end, but it should be counted once.

count_links({'A': ['B', 'C'], 'B': ['A'], 'C': ['A']})  ->  2

def count_links(network):

# Each connection is listed by both of its devices

pass

Exercise 2: Still Connected?

Write Code

Write still_connected(network, start, goal, broken). broken is a list of failed connections, each a tuple of two devices, such as ('B', 'D'). A connection is broken in both directions, so ('B', 'D') also blocks D to B. Return True if start can still reach goal using only working connections.

Tip: start from the can_reach search in the lesson, and skip any neighbour that is joined to the current device by a broken connection.

net = {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C']}
still_connected(net, 'A', 'D', [('B', 'D')])              ->  True   (A, C, D)
still_connected(net, 'A', 'D', [('B', 'D'), ('A', 'C')])  ->  False

def still_connected(network, start, goal, broken):

# Search like can_reach, but never cross a broken connection

pass

How do you find the weak spots in a network?

A system's vulnerabilities to failure are the parts whose loss would stop it from working. The worst kind is a single point of failure: one device or one connection that, on its own, can cut part of the network off. A program can find them all by trying every failure in turn.

Which single link would cut someone off?

def all_connected(network):

devices = list(network)

return all(can_reach(network, devices[0], other) for other in devices[1:])

links = []

for device, neighbours in network.items():

for neighbour in neighbours:

if device < neighbour: # list each connection once

links.append((device, neighbour))

for a, b in links:

if not all_connected(remove_link(network, a, b)):

print(f"Single point of failure: the link {a} - {b}")

Output

Single point of failure: the link library - router D
Single point of failure: the link data center - router E

The library and the data center each hang off the network by one link. Every other connection has a backup.

So how fault-tolerant is this network? For the school, every route to router E has a second option: if A or C fails, traffic goes through B and D, and if B or D fails, it goes through A and C. The weak spot is the last step, the single link from router E to the data center, and the library has the same problem with its link to router D. To fix both, engineers would add a second link to each, ideally to a different router.

Because failures often come in groups, it is also worth testing pairs. The next program finds the pairs of links that cut the school off from the data center when they fail together, even though neither one would on its own.

Failures that come in pairs

from itertools import combinations

dangerous_alone = {("data center", "router E"), ("library", "router D")}

for first, second in combinations(links, 2):

if first in dangerous_alone or second in dangerous_alone:

continue # already a weak spot on its own

damaged = remove_link(remove_link(network, *first), *second)

if not can_reach(damaged, "school", "data center"):

print(f"{first[0]} - {first[1]} together with {second[0]} - {second[1]}")

Output

router A - school  together with  router B - school
router A - router C  together with  router B - school
router B - router D  together with  router C - router E
router C - router E  together with  router D - router E

Four pairs are dangerous. Each pair cuts every route at once, for example both of the school's own links, or both links into router E.

Redundancy also has to be weighed against its cost. Connecting every router directly to every other router would give the most backup paths, but the number of links grows very fast:

The cost of connecting everything to everything

for routers in [5, 10, 50, 1000]:

chain = routers - 1 # the fewest links that join them all

everything = routers * (routers - 1) // 2

print(f"{routers:>5} routers: {chain:>4} links as a chain, {everything:>7,} links fully connected")

Output

    5 routers:    4 links as a chain,      10 links fully connected
   10 routers:    9 links as a chain,      45 links fully connected
   50 routers:   49 links as a chain,   1,225 links fully connected
 1000 routers:  999 links as a chain, 499,500 links fully connected

Real networks sit in between. They add enough extra links that no single failure, and few likely groups of failures, can cut anyone off, without paying for every possible link.

Where does the real Internet use redundancy?

The same idea shows up at every size:

Between continents, hundreds of cables run along the ocean floor. When a ship's anchor cuts one, traffic shifts to the others. Pages may load more slowly in the affected region, but they still load.

Between networks, large companies and Internet providers connect to several other networks instead of one, so a failure at one neighbour does not cut them off.

Inside data centers, servers often have two power supplies and two network connections, and important data such as your photos and email are stored as copies in more than one building, so one building going dark loses nothing.

At home, your phone falls back to the cell network when the Wi-Fi drops: two paths to the Internet, chosen automatically.

Each of these costs money to build and run, and each one is there because a single failure would otherwise reach millions of people.

Exercise 3: Find the Single Points of Failure

Write Code

Write single_points_of_failure(network). It returns a sorted list of the devices whose failure would leave the remaining devices unable to all reach each other. When a device fails, it and all of its connections disappear.

The starter code includes the lesson's can_reach, which you may use.

chain = {'A': ['B'], 'B': ['A', 'C'], 'C': ['B']}
single_points_of_failure(chain)  ->  ['B']

If A fails, B and C can still reach each other, so A is not on the list.

def can_reach(network, start, goal):

to_visit = [start]

seen = {start}

while to_visit:

device = to_visit.pop()

if device == goal:

return True

for neighbour in network[device]:

if neighbour not in seen:

seen.add(neighbour)

to_visit.append(neighbour)

return False

def single_points_of_failure(network):

# Try removing each device, then check the devices that are left

pass

Check your understanding

Which of the following best describes a fault-tolerant system?

AA system that continues to function even when some of its components failBA system whose components never failCA system that shuts down safely as soon as any component failsDA system that uses the fewest possible components

In a network, these pairs of devices are directly connected: A and B, A and C, B and C, C and D, D and E, D and F, E and F. If exactly one connection fails, which failure would stop A from communicating with F?

AA and BBB and CCC and DDE and F

Use the same network: A and B, A and C, B and C, C and D, D and E, D and F, E and F. Engineers want A to stay able to reach F if any single connection fails. Which of the following changes would do this? Select two answers.

Select 2 answers.

AAdd a connection between B and DBAdd a connection between A and ECAdd a new device G that is connected only to CDRemove the connection between B and C

A school pays for a second Internet connection from a different provider, in case the first one goes down. Which of the following best describes this decision?

AIt uses additional resources to make the school's Internet access fault-tolerant.BIt is wasted money, because Internet connections cannot fail.CIt doubles the speed of every website the school visits.DIt makes the school's network smaller and easier to manage.

You are loading a web page when a router on the path between your laptop and the web server fails. Which of the following is most likely to happen?

ALater packets are sent along a different route, if one exists.BEvery device on the Internet stops working until the router is fixed.CYour laptop must be connected directly to the web server.DThe web page is changed to remove the parts sent through that router.

A city has two cables connecting it to the rest of the Internet. To save money, both cables were laid in the same underground tunnel. Which of the following best describes the vulnerability?

AOne event, such as a flood in the tunnel, could break both cables at once.BHaving two cables makes the network slower than having one.CCables in a tunnel cannot carry packets.DThe city has more redundancy than it needs.

The two lists below describe a network: the connections are A to B, A to C, B to D, C to D and D to E. What is displayed when the code segment runs?

fromList ← ["A", "A", "B", "C", "D"]
toList ← ["B", "C", "D", "D", "E"]
count ← 0
i ← 1
REPEAT LENGTH(fromList) TIMES
{
  IF((fromList[i] = "D") OR (toList[i] = "D"))
  {
    count ← count + 1
  }
  i ← i + 1
}
DISPLAY(count)

A3B2C1D5

Run this pseudocode

Exam topics: 4.2 Fault Tolerance (CSN-1.E)

What does fault-tolerant mean?

What is redundancy?

How can a program tell whether two devices are still connected?

How do you find the weak spots in a network?

Where does the real Internet use redundancy?

Check your understanding

Related Tutorials