What is fowarding?
move packets from router input port to appropriate output port
what is routing?
determine route taken by packets from source to destination
two approaches for network control plane
- per router (traditional)
- logically centralized control
logically centralized control plane?
Remote controller interacts with local control agents (CAs) in routers to compute fowarding tables
Per-router system?
- routing algorithm components in EVERY ROUTER to compute fowarding tables
What is the cost of an edge?
- physical length
- link speed
- monetary cost
centralized routing algortihm?
- has complete topology (link cost info)
- “link state” algorithms
Decentralized routing algorithm
- router knows physically-connected neighbours and link cost for these
- iterative process to exchange info with neighbours
- “distance vector” algorithms
Static routing algorithms
- routes change slowly over time
- usually requires human intervention
dynamic routing algorithm
- routes change more quickly
- periodic update
- in response to link cost changes
What does distributed mean for the distance vector algorithm
- each node receives some info from one or more of its DIRECTLY ATTACHED neighbours
- performs a calculation
- distributes the results of its calculation back to its neighbours
what does “iterative” mean with the distance vector algorithm
continues until no more info is exchanged between neighbours
what does asynchronous mean with distance vector algorithm
- it does not require all nodes to operate in lockstep with each other
Comparing LS and DV algorithms
Message complexity:
LS - with n nodes, E links, O(nE) messages sent
DV - exchange between neighbours only
Speed of convergence:
LS - O(n^2) algorithm requires O(nE) messages (could have oscillations)
DV - convergence time varies (routing loops or count to infinity)
Robustness (router malfunctions?):
LS - advertise incorrect link cost
each node only computes only its own table
DV - can advertise incorrect path cost
intra-AS routing
- routing between routers in same network
- routers must run SAME intra-domain protocol
- routers in different AS (autonomous systems) can run different AS protocols
- gateway router: edge of AS. has links to routers in other AS
inter-AS routing
- routing amoung different AS
- gateways performs inter-domain routing (and intra-domain routing)
Hierarchy of OSPF
- each area runs its own OSPF link-state rotuing algorithm
- each router broadcasts link state to all other routers in area
- area border routers:
summarize distances to nets in own area and advertise to other area border routers - backbone routers:
run OSPF routing - boundary routers:
connect to other AS
Open shortest path first (OSPF)
- publically available
- uses link state
- router will flood OSPF link-state to all routers in AS
- messages carried directly over IP rahter than TCP or UDP
Border gateway protocol (BGP)
-inter domain protocol
- determines good routes based on reachability and policy
eBGP
obtain subnet reachability info from neighbouring AS
iBGP
propagate reachability info to all AS-internal routers
Hot potato routing
choose local gateway that has least intra domain cost. Dont worry about inter-domain cost
BGP route selection
1.) local preference (policy)
2.) shortest AS-path
3.) closest next-hop router (hot potato)
4.) additional criteria
Why different intra-, inter-AS routing?
Policy:
inter - admin wants to control how traffic routed and who routes through its net
intra - single admin, so no policy decisions
scale:
- heriarchical routing saves table size, reduced update traffic
performance:
intra - can focus on performance
inter - policy can dominate over performance
