Routing

Question 1

Link state routing

Answer 1

Each router has complete network

Information about neighbors flooded to every other, to keep link states consistent across routers

Independent calculation via Dijkstra

OSPF

Question 2

Distance vector routing

Answer 2

Distributed computation

Each router knows neighbors
Each router has provisional shortest path
Routers exchange info with neighbors
Routers update idea of best path depending on info received by neighbors

Bellman Ford Algorithm

Question 3

Path vector routing

Answer 3

Instead of just exchanging cost of path, exchange entire path to destination

Nodes can use arbitrary metrics, ie policies, economic factors, traffic etc.

Loopless, but maybe not convergent

Question 4

Hierarchical routing

Answer 4

Aggregate routers into autonomous systems
In AS’s every router runs same protocol: intra AS routing
At the gateways: inter AS routing

Forwarding table calculated by both protocols

InterAS task is to obtain info about neighboring ASs and tell inner routers about it
Example internet: BGP

IntraAS protocols aka Interior Gateway Protocols
Examples: RIP, OSPF, IGRP

Question 5

RIP

Answer 5

Routing Information Protocol

Distance vector algorithm with max hop count
DV exchanged periodically

Uses poison reverse

Question 6

BGP

Answer 6

Border Gateway Protocol

Intra domain routing
Path vector protocol