Control Plane Flashcards
What is the goal of a routing protocol?
Determine good paths from sending hosts to receiving host, through network of routers.
What does good mean in terms of routing protocols?
Least cost
Fastest
Least congested
What is a global routing algorithm?
All routers have complete topology and link cost info of the network
Link state algorithms
What is a decentralised routing algorithm?
Router knows neighbours and link cost to them.
Iteratively compute and exchange information with neighbours
Distance vector algorithms
Give an example of a link-state routing algorithm
Dijkstra’s algorithm:
Network topology and link costs known to all nodes, done via broadcast.
Computes least cost paths from one node to all other nodes; Giving the forwarding table for that node.
What is the notation used for Dijkstra’s algorithm
c(x,y) - cost from node x to y
D(v): current value of cost of path from source to dest v.
p(v): Predeccessor node along path from source to v
N’: set of nodes whose least cost path definitively known.
How does Dijkstra’s algorithm work?
Initialise all nodes, finding the cost of all edges between adjacent nodes.
Find the minimum path between current node and a destination node.
What is the Bellman-Ford equation?
d_x(y) = cost of least-cost path from x to y.
then
d_x(y) = min{c(x,v) + d_v(y)}
AKA minimum of the cost of going to a neighbour, and then from the neighbour to the destination, for all neighbours.
What is the key idea behind the distance vector algorithm?
From time-to-time, each node sends its own distance vector estimate to neighbours. When x receives new DV estimate from neighbors, it updates its own DV using B-F equation
What are properties of the distance vector algorithm?
iterative and asynchronus: Each local iteration caused by link cost change or neighbour update.
Distributed: Each node notifies only when its DV changes.
How are link cost changes detected in Distance Vector algorithms?
Node detects local link cost change
Updating routing info, recalculates and if there’s a change, notifies neighbours.
How are positive changes in the cost of nodes distributed when using the distance vector algorithm?
Y detects link-cost change, updates its DV and informs its neighbours
Z receives update from y, updates its table, computes new least cost to x and sends its neighbours its DV
y receives z’s update, updates its distance table. y’s least costs do not change, so y doesn’t send a message to z.
How are negative changes in the cost of nodes distributed when using the distance vector algorithm?
Node detect local link cost change, and bad news travels slow. Tells others it’s an infinite cost so no-one will take it, until a stabilisation is met.
What are the comparisons between Link-state and Distance-Vector algorithms?
Message complexity: LS with n nodes, E links, O(nE) msgs sent.
Speed of convergence:
LS: O(n^2) algorithm require O(nE) msgs.
DV:
What are the differences in message complexity between Link-State and Distance-Vector algorithms?
Link-state: With n nodes, E edges, O(nE) messages sent
Distance-Vector: Exchanges between neighbours only, varying convergence time.
What are the differences in speed of convergence between Link-state and Distance-vector algorithms?
LS: O(n^2) algorithm requires O(nE) msgs, may have oscillations
DV: Convergence time varies, may be routing loops and also suffers from the counting to infinity problem.
What are the differences in robustness between Link-state and Distance-vector algorithms
LS: Can advertise incorrect link cost, each node computes only its own table.
DV: Node can advertise incorrect path cost, each node’s table used by others - causing errors to be propagated through the network.
What is the count to infinity problem when using Distance-Vector algorithms.
Routing loop.
Routing loops usually occur when an interface goes down.
Can also occur when two routers send updates to each other at the same time.
How is routing made scalable?
Through the use of autonomous systems (AS) aka: Domains.
Why does routing need to be made scalable?
With billions of devices, it’s not feasible to store all destinations in routing tables - otherwise the tables would swamp links.
What is intra-AS routing?
Routing among hosts, routers in same network.
All routers in AS run same intra-domain protocol.
What is a gateway router?
At edge of its own AS, has link(s) to router(s) in other AS’es
What is inter-AS routing?
Routing among AS’es
Gateways perform inter-domain routing (as well as intra-domain routing).
How are routing destinations’s entries to the routing table handle dby an AS
Inter-AS and Intra-AS determine entries for external destinations.
intra-AS routing determines entries for internal destinations.
