03-05-2014, 03:55 PM
Distance Vector vs. Link State Routing
Distance Vector.ppt (Size: 607 KB / Downloads: 13)
With distance vector routing, each node has information only about the next hop:
Node A: to reach F go to B
Node B: to reach F go to D
Node D: to reach F go to E
Node E: go directly to F
Distance vector routing makes
poor routing decisions if
directions are not completely
correct
(e.g., because a node is down).
If parts of the directions incorrect, the routing may be incorrect until the routing algorithms has re-converged.
Link State Routing: Basic princples
1. Each router establishes a relationship (“adjacency”) with its neighbors
2.Each router generates link state advertisements (LSAs) which are distributed to all routers
LSA = (link id, state of the link, cost, neighbors of the link)
3. Each router maintains a database of all received LSAs (topological database or link state database), which describes the network has a graph with weighted edges
4. Each router uses its link state database to run a shortest path algorithm (Dijikstra’s algorithm) to produce the shortest path to each network
Features of OSPF
Provides authentication of routing messages
Enables load balancing by allowing traffic to be split evenly across routes with equal cost
Type-of-Service routing allows to setup different routes dependent on the TOS field
Supports subnetting
Supports multicasting
Allows hierarchical routing
Link State Database
The collection of all LSAs is called the link-state database
Each router has and identical link-state database
Useful for debugging: Each router has a complete description of the network
If neighboring routers discover each other for the first time, they will exchange their link-state databases
The link-state databases are synchronized using reliable flooding
Autonomous Systems
An autonomous system is a region of the Internet that is administered by a single entity.
Examples of autonomous regions are:
UVA’s campus network
MCI’s backbone network
Regional Internet Service Provider
Routing is done differently within an autonomous system (intradomain routing) and between autonomous system (interdomain routing).
BGP
BGP = Border Gateway Protocol
Currently in version 4
Note: In the context of BGP, a gateway is nothing else but an IP router that connects autonomous systems.
Interdomain routing protocol for routing between autonomous systems
Uses TCP to send routing messages
BGP is neither a link state, nor a distance vector protocol. Routing messages in BGP contain complete routes.
Network administrators can specify routing policies