L3 - Internet Routing

Question 1

What type of data structure is the internet?

Answer 1

Web graph

Question 2

What are Packets? What information do they contain?

Answer 2

The fundamental data unit that is transmitted over the internet. Files are split into packets for sending.

Each packet contains a sender IP, recipient IP, data load.

Question 3

On what layer are packets routed? What protocol is used?

Answer 3

Network Layer.
TCP/IP

Question 4

Define Routing and Forwarding in regards to Data Packets being sent via TCP/IP

Answer 4

Routing is the end to end process of finding the optimum path from end to end. I.e Finding the route of least cost to get the data packets from sender to receiver.

Forwarding is the process of establishing the next optimal local route from a router forwarding table. I.e At each router, the router uses the forwarding table to establish the next lowest cost path to send the packet down.

Question 5

Define Packet Switching…

Answer 5

The process of segmenting a file into data packets for efficient transmission.

Question 6

What are the 3 core components of a router?

Answer 6

• Input interface
• Output interface
• Forwarding Table

Question 7

What is a Forwarding Table?

Answer 7

A table that each router has that lists what network paths the router can send a data packet down.

Question 8

What is the goal of routing algorithms?

Answer 8

To find a route across a graph / network that has the minimum possible cost from the origin node to the destination node.

Question 9

What are Linked State algorithms?

Answer 9

Algorithms that are Global and Static.

Global : each node has a complete topology.

Static : routes change slowly over time.

Question 10

What are Distance Vector algorithms?

Answer 10

Algorithms that are Distributed and Dynamic

Distributed : Each node only has topology knowledge of neighbours.

Dynamic : routes change quickly due to cost changes.

Question 11

Why are Distance Vector Algorithms Async and Continuous?

Answer 11

To enable us to continuously find the optimal routes whilst links costs are dynamically changing.

Question 12

What is the Time Complexity of Dijkstras?

Answer 12

O( N^2 )

Question 13

What category of routing algorithm is Dijkstras? Why?

Answer 13

Greedy Link State because each node has complete topology.

Question 14

In Link State algorithms, how do routers exchange information?

Answer 14

Link State Packets : Give each router information about the topology of its neighbours.