Network topologies

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

F10.4NetworksGCSE20 min

Covers OCR J277 1.3.1 Networks and topologies · Edexcel 1CP2 4.1.8 Topologies

Do this lesson in the simulator

Print it: worksheet (PDF) · answers (PDF) · as a web page

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

Four network topologies: star, bus, ring and meshswitchStarBusRingMesh
Four network topologies: star, bus, ring and mesh

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.

One failure in each topology: a broken cable in a star cuts off one device; a broken backbone stops a bus; a broken link stops a ring; a broken link in a mesh is routed aroundstar: one cable breaksswitchonly that device is cut offbus: the backbone breaksthe whole network failsring: one link breaksdata cannot get round: the ring stopsmesh: one link breaksdata takes another route (green)
The same kind of fault in all four. Only in the star and the mesh do the other devices carry on, and only the mesh keeps every device connected.

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 partial mesh of six robots: each line is a radio linkABCDEF
A partial mesh of six robots: each line is a radio link

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.

The robots arranged by how many links they are from A: B and C are one link away, D and E two, F three; an arrow from each robot points back to the robot it was first reached from0 links away1 link away2 links away3 links awayABCDEFgreen arrow: came_from, back to where it was first reached from
The search reaches every robot one link away before any robot two links away, so the first time it reaches a robot is by a shortest route. The dashed links lead to robots it had already reached.

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?