Routing Flashcards
Routing def.
Determine a path through the network for packets
Forwarding def.
- Advance packets through the network
- includes also the routing decision
On the fly routing algorithms
- Routing by network address
- label switching
- source routing
Proactive routing algorithms
- Non adaptive (static)
- fixed directory routing
- selective flooding and derivatives
- Admin has full control
- error prone
- does not adapt to changes
- Adaptive algos (dynamic)
- centralized routing
- Routing control center calculates and distributes tables
- single point of failure and bottleneck, not suitable for highly dynamic networks
- isolated routing
- each node decides independently, no exchange of information
- backward learning
- distributed routing: combines advantages of both isolated and centralized routing
- distance vector
- link state
- centralized routing
Distance vector algorithm
DV:
- List of all reachable destinations
- ditance from announcing router
- generated by each router
- received from neighbors
Issues: they are all about instability
- black hole
- count to infinity
- bouncing effect (loop)
Advantages:
- simple to implement
- protcols are simple to deploy, with very little configuration
Shortcomings:
- exponential wors case complexity (n2)
- convergence time limited by slower links
- complex tuning and troubleshooting
- large routing traffic and storage (not suitable for large and complex networks)
Solution to DV issues
They are partial solutions:
- split horizon: If C reaches destination A through B, it is useless for B trying to reach A through C.
- prevents loops between two nodes, speeds up convergence
- DV do not contain non useful destinations (the one from that node)
- path hold down: il L fails, all destinations reachable through it are considered unreachable for some time.
- high convergence time
- route poisoning: invalid route is advertise as infinite instead of omitting it, it will have to expire for that, yields a faster convergence time
Routing protocol def.
Enables routers to exchange information on the network to determine the best route for each destination.
It is based on routing algorithms.
Link state algorithm
- Information on the state of each link.
- A local map
- Sent by each node to all others node (selective flooding)
- Nodes build a network map
- Each node computes routes on the map (dijkstra)
Advantages:
- LSs spred quickly
- Link state are small
- Fast and efficient neighbor greeting
- Rarely generates loops
- Simple to understand and troubleshoot (all nodes have the same db)
Shortcomings:
- High implementation complexity
- selective flooding
- first imple. took several years
- Protocols with complex configuration
Link state generation:
Actual protocols generate LSs periodically, but in principle they only when there is a topology change
Routing protocols compared with the internet layers
Between IP and TCP/UDP
Routing domain def
- A set of routers deploying the same routing protocol.
- It is a connected portion of the network.
- Redistribution:
- A router may belong to different domains using different routing protocols
- It can redistribute information learned from one protocol to another.
- Redistribution policies
- by admin
- advertisement filters
- metric conversion (bandwidth to cost)
- information source priority.
Autonomous systems, why?
Subnets grouped by topology, organizational criteria.
Identified by two byte number, assigned by IANA.
Example: Large ISP’s subnets.
Why?
- To control addressing and routing in a tight way, possibly with internal routing domains
- Scalability: not all information is propagated everywhere
- destination can be aggregated → hierarchical routing
- Exterior routing might cause sub-optimal routing.
- destination can be aggregated → hierarchical routing
- Administration: autonomous internal routing choices, negotiated external routing choices.
*
NAP and IXP
Neutral Access Point/Internet eXchange Point
A LAN to which different AS’s are connected
Pairs of routers exchange information (BGP)
