Network topologies

Star, bus, ring and mesh, and routing around a failure in a mesh of robots.

F10.4NetworksGCSE20 min

A topology is the layout of a network: which devices are joined to which. The layout decides what happens when a cable breaks or a device fails, how much cable is needed, and how data gets from one place to another. This lesson compares the four topologies on the exam, and finds routes through a mesh of robots.

Four topologies

Star: every device connects to a central switch. - A broken cable only affects one device, and it is easy to add devices. - If the switch fails, the whole network fails. It needs a lot of cable.

Bus: every device connects to one main cable, the backbone, with a terminator at each end. - Cheap, with little cable. - If the backbone breaks, the whole network fails. Data collides when more devices send, so it slows down as it grows.

Ring: each device connects to the next, in a loop, and data travels round in one direction. - No collisions, because data flows one way. - One broken link or device can stop the whole ring.

Mesh: devices connect to many others. In a full mesh, every device connects to every other; in a partial mesh, to some. - There are many routes, so if one link fails, data takes another. Very reliable. - A full mesh needs a lot of connections: with n devices, n × (n - 1) ÷ 2 of them.

Wi-Fi networks are usually a star around the wireless access point. The internet is a huge partial mesh of routers.

Routes through a mesh

Robots with short-range radios can form a mesh: each passes messages on to the robots it can reach. To get a message from A to F, find a route along the links:

A breadth-first search finds the shortest route: try every robot one link away, then two links away, and so on, remembering how you reached each one.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

links = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"], "D": ["B", "C", "F"], "E": ["C", "F"], "F": ["D", "E"]}

came_from = {"A": None}
queue = ["A"]
while queue:
    robot = queue.pop(0)
    for neighbour in links[robot]:
        if neighbour not in came_from:
            came_from[neighbour] = robot
            queue.append(neighbour)
print("how each robot was first reached:", came_from)

Run this in the simulator

To read the route to F, start at F and follow came_from back to A.

Task: route around a failure

Write route(links, start, end) that returns the shortest route as a list of robots, using a breadth-first search. Print route: A-B-D-F style for the route from A to F, joining the names with -, and send the same text by radio. Then the link between D and F fails: remove it from both robots' lists, find the route again, and print after D-F fails: <route>.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

links = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"], "D": ["B", "C", "F"], "E": ["C", "F"], "F": ["D", "E"]}

Challenges

1. How many links does a full mesh of 6 robots need? Check with a loop.
2. Make C fail completely. Is there still a route from A to F?
3. Change the network into a star with a switch in the middle. What happens to every route if the switch fails?