Layer-3 Routing

Natawut Nupairoj, Ph.D.

Department of Computer Engineering
Chulalongkorn University
Outline
 Overview.
 Interconnection Devices.
 Routing Concepts.
 Routing Algorithms.
Overview
 End-to-end delivery
 Across multiple links (or
hops).
 Must concern
 Find paths in different
networks.
 Choose appropriate
paths.
 Avoid overloading links.

 Data-Link is just for

machine-to-machine
over single link.
Interconnection Devices
Device Overview
Repeater
 Focus at physical layer.
 But not an amplifier.
Repeater
Bridge
 Connect two (or more) LANs together
 Forward packages between LANs.
 Smart hub.
 Focus at Layer-2
 Use MAC addresses to decide if it should forward
packages.
Bridge Functions
Transparent Bridge
 No need to configure
the addresses
 Self-updating.
 How does a bridge
learn addresses?
 Initially, know nothing.
 If found unknown
address, send to all
ports.
 Also, note the port of the
source address.
Bridge in OSI Model
Router
 Similar to bridge, but focus on layer-3.
 Forward to neighbor network or next router
toward the destination.
Router in OSI Model
Gateway
 Operate in all seven layers.
 Protocol converter.
Gateway in OSI Model
Switch
 Smart multiport bridge
 Multiple ports.
 Transparent bridge
functions (Layer-2).
 Packet buffers.
 Next generations
 L3 Switch.
Routing Concepts
 Key design elements
 Performance criteria.
 Decision time.
 Decision place.
 Network information source.
 Network information update timing.
Performance Criteria (PC)
 What route should I take?
 Hop count – simplest.
 Links’ bandwidths – better.
 Current delay in the queue – more realistic.
 Example of least-cost algorithms
 Distance vector routing.
 Link-state routing.
Decision Time and Place
 Decision Time (DT)
 When finding the route, what level should I decide for ?
 Per-packet.

 Per-session.

 Decision Place (DP)

 Who will decide the route ?
 Switching node (e.g. router).

 Central node.

 Source node.
Network Information (NI)
 What should I obtain the information regarding to
current network information ?
 Topology.
 Traffic load.
 Link cost.
 Scope of the information
 Cost from the router to all other routers.
 Cost from the router to its neighbors.
Network Information Source (NS)
 Where do I obtain the information regarding to
current network information ?
 None.
 Local.
 Adjacent (neighbor) node.
 Node along the route (of packet).
 All nodes – centrally or distributed.
Network Information Updating
Time (NU)
 How often should I collect network information ?
 Never.
 Continuous.
 Periodic.
 Major load change.
 Topology change.
 The more often you collect
 The better routing decision you can make.
 The more overhead you generate.
Routing Strategies
 Fixed Routing
 all routes are predetermined.
 simple but not flexible.
 Source Routing
 Source node determines the route.
 Routing patterns can be pre-arranged.
 Good for special network.
 Flooding
 send to everyone.
 require no network information.
 generate lots of traffic.
Routing Strategies
 Random Routing
 simple and require no network information with less traffic.
 may not be the least-cost routing.
 Adaptive Routing
 complex
 generate some traffic overheads
 react too quick / too slow ?
Distance Vector Routing
 Keys
 PC: N/A.
 DP: router.
 DT: N/A.
 NI: to all routers.
 NS: exchange with neighbors.
 NT: periodic (e.g. every 30 seconds).
Example: Network
Example: NI-NS-NT
Distance Vector Routing Table
Routing Table Distribution
Network Information Updating
Final Routing Tables
Link-State Routing
 Keys
 PC: N/A.
 DP: router.
 DT: N/A.
 NI: to neighbors.
 NS: exchange with all routers -- flooding.
 NT: major changes.
Example: NI-NS
Cost in Link-State Routing
Link-State Packet
Flooding of A’s Link-State Packets
Link-State Database
Cost in Dijkstra Algorithm
Shortest Path Calculation
Figure 21-31, Part III

Shortest Path Calculation, Part X

Routing Table for Router A