Routing tables Flashcards
What are the properties of a routing table?
Source independence
Hierarchical
Universal routing
Optimal routes
Default route
What does source independence mean?
next hop does not depend on packet source only its destination
What does hierarchical mean?
only need to know how to reach a network not each machine
What does universal routing mean?
theres a next hop for every possible destination
What does optimal route mean?
next hop should give the shortest path to destination
What does default route mean?
a catch all route for anything not matched by a more specific route
What are the 2 types of routing table
Static and dynamic
How is static routing table built?
built when the router boots and calculates possible routes to the different networks and fills in table
doesnt change until machine rebooted
What is the problem with static routing table?
inflexible cannot adopt to changes in a network like a link going down and would still try to send packets over the dead link
What solves statics problem?
Dynamic routing table
How does Dynamic routing table work?
program running on router builds an initial table at boot which is then updated as network conditions change
How does Dynamic routing table know when conditions change?
routers talk to each other informing them of changes
how is Dynamic routing table compared to static?
more complex but flexible and autonomous
What happens if a route fails in a Dynamic routing table?
system will route around them
how are routing tables built more deeply?
software models the network as a graph
nodes are the networks and edges are the link between edges
What is each edge given?
a weight
What is the sum of paths?
distance between 2 nodes
What algorithm calculates the path
Dijkstras algorithm
what needs to be known in Dijkstras algorithm
complete graph and weight of all edges
How does Dijkstras algorithm work?
initialise a set S to contain all nodes except the source node
Initialise a table D so that D[v] is the weight of an edge from the source
to node v, or infinity if no edge exists
Initialise a table R so that R[v] is v if an edge exists from the source to v,
and zero otherwise
Whats another way to build up the table?
Distributed algorithm
How does Distributed algorithm work?
routers build up table of what they know then pass it on to peers
When they receive these messages, they can update their own routing
tables and then send the updated one out again
what are 2 main algorithms of Distributed algorithm?
vector-distance routing
link-state routing
What is vector-distance routing?
status messages are pairs of destinations that router can reach plus the distance
when received router updates its table if it finds shorter path
What is link-state routing?
routers communicate details of when links go up and down
other routers use this to build graph of network
which then calculates shorter path
Why is link-state better?
more faster to cope with links going down
