Routing
When network becomes large, it will have many routers and many links
=> You need a mechanism to determine which path should go
Routing protocol - Determine "good" path thru network from source to destination. "Good" depends on
- Cost $
- Congestion level
- delay
- no. of hop
Static route- Routes changes slowly over time
- Usually manually set by command in router
Dynamic route
routes change more quickly - periodic update
- in response to link cost changes
- Affected by other routers changes and changed itself
Link-State Routing - LSP
- Each router is responsible for meeting its neighbors and learning their names
-Sending Hello / Keep-alive messages - Each router constructs a packet known as a link state packet (LSP) which contains a list of names of and cost to each of its neighbors
- The LSP is flooded to all other routers, and each router stores the most recently generated LSP from each other router in the whole network.
- Each router, now armed with a complete map of the network topology
-Shortest-path-based route will be used
*If not use shortest-path algorithm, looping will occur
Distance Vector routing Algorithm
- Each router consider themselves as [Distance 0]
- Each router saves its own ID and attached links's cost
- Transmit these data to neighbor routers
- Form a DV table eventually
Example of Distance table of E in the figure
And it forms a routing table
When there is changes (E.g. UNplug a router)
LS vs DV
- DV has count to infinity problem - I.E. A dead loop will occur when link cost change suddenly
- LS: Node may advertise incorrect link cost to other routers and other routers use it to build its own table
- DV may advertise incorrect path cost
- LS & DV can be down if just one router in the network not following the rules
When network goes large --> cannot store the whole routing table in each single router
Large network is
- interconnections of Autonomous Systems (AS)
- Each of AS undergoes Inter-domain routing
AS
- There are gateway routers
- Gateway routers run inter-as routing protocol with other ASes
- Gateway routers run intra-as routing protocol with other routers in a AS
- Hierarchical Routing