Routing

Question 1

What is the internet?

Answer 1

A web of systems connected via buses and wires

Question 2

What is routing?

Answer 2

A way to determine an end-to-end path through a network

Question 3

What is a forwarding table, and how is it used in routing?

Answer 3

A table containing information on the ‘next hop’ for a packet to reach the next destination, used to determine where to send the data

Question 4

A router may have multiple ports, which are used for…

Answer 4

Taking in and sending data

Question 5

What do routing algorithms determine?

Answer 5

A good path through a network from source to destination

Question 6

How is a network graph defined? (HINT: Use sets N and E)

Answer 6

As an undirected graph of N nodes, each connected by a set of E node-pair edges which define the links between each node. Each edge has a link cost, which is usually the cost of going from one node to another

Question 7

What is meant by a neighbour in a network graph?

Answer 7

An adjacent node to the current one

Question 8

What does it mean for a routing algorithm to be global?

Answer 8

The algorithm knows the complete topology and link cost information of the router’s network

Question 9

What does it mean for a routing algorithm to be decentralised?

Answer 9

The algorithm only knows the router’s physically connected neighbours and their link costs

Question 10

What does it mean for a routing algorithm to be static?

Answer 10

Routes change slowly over time

Question 11

What does it mean for a routing algorithm to be dynamic?

Answer 11

Routes change quickly over time

Question 12

What does it mean for a routing algorithm to be load sensitive?

Answer 12

If it considers traffic in its calculations

Question 13

What does it mean for a routing algorithm to be load insensitive?

Answer 13

If it does not consider traffic in its calculations

Question 14

What is the primary difference between link state and distance vector algorithms?

Answer 14

Link state is global while distance vector is local

Question 15

The Distance Vector (DV) algorithm uses what data structure to estimate cost to some destination?

Answer 15

Vectors

Question 16

The Link State algorithm uses what other type of algorithm to calculate a path?

Answer 16

Shortest path algorithms like Dijkstra’s or A*

Question 17

What is Dijkstra’s algorithm used for?

Answer 17

Calculating least-cost paths from one node to all others in a network

Question 18

What type of routing algorithm is Dijkstra’s?

Answer 18

Link state

Question 19

What time complexity does Dijkstra’s run in?

Answer 19

Polynomial

Question 20

What are the limitations of link state algorithms in highly dynamic networks?

Answer 20

A slow response to changes, large routing tables and frequent link state messages consuming bandwidth

Question 21

What does it mean when we say that the Distance Vector (DV) routing algorithm is distributed?

Answer 21

Each node transmits and receives data only to and from its direct neighbours

Question 22

What does it mean when we say that the Distance Vector (DV) routing algorithm is iterative?

Answer 22

Continues until no more information is exchanged

Question 23

What does it mean when we say that the Distance Vector (DV) routing algorithm is asynchronous?

Answer 23

Doesn’t require all nodes to exchange information at the same time

Question 24

How do Distance Vector (DV) algorithms store routing information?

Answer 24

In a routing table

Question 25

What do routing tables store?

Answer 25

Cost between each neighbour, its distance vector (least-cost paths to all nodes in N), and the distance vectors of its neighbours

Question 26

How does Distance Vector (DV) calculate least cost paths?

Answer 26

Each node periodically sends its own distance vector to its neighbours, and when a node receives a new distance vector, it updates its own distance vector using Bellman-Ford

Question 27

If we lose connection to a node, we will reach an infinite distance to that node again, but how is this process inefficient?

Answer 27

The distance vector changes one at a time in a loop, creating infinite updates across all nearby nodes

Question 28

How can we fix the issue caused by nodes disconnecting?

Answer 28

Route poisoning - when a router advertises that failed route as infinite, "poisoning" it, and advertising that value to its neighbours

Question 29

What is the complexity of Bellman-Ford?

Answer 29

O(|N||E|)

Question 30

What is hierarchical routing?

Answer 30

The grouping of routers into clusters, or autonomous systems

Question 31

Why do we use hierarchical routing?

Answer 31

The internet is extremely large, so if each router is treated separately, the routing tables would have to be massive

Question 32

Routers in the same autonomous system (AS) run [the same/different] protocols.

Answer 32

The same

Question 33

Gateway routers that connect autonomous systems (AS) together run [the same/outside/inside and outside] protocols.

Answer 33

Inside and outside

Question 34

Who decides what data is routed through its network?

Answer 34

The admin of the network

Question 35

What is the Routing Information Protocol (RIP)?

Answer 35

A distance vector algorithm where the distance metric is measured as 'hops' - the number of subnets traversed along the shortest path - and we exchange DVs every 30 seconds via advertisement

Question 36

What is the Broader Gateway Protocol (BGP)?

Answer 36

An inter-AS protocol that enables each subnet to obtain information from neighbouring subnets, propagate that information to all internal routers and to determine good routes to subnets based on reachability/policy

Question 37

What is the Open Shortest Path First (OSPF)?

Answer 37

A link state algorithm where routers construct a complete topological map of the entire AS at each node using Dijkstra's, broadcasting link state information whenever there is a change at a link