Please enable JavaScript.
Coggle requires JavaScript to display documents.
CHAPTER 5: NETWORK LAYER - CONTROL PLANE - Coggle Diagram
CHAPTER 5: NETWORK LAYER - CONTROL PLANE
Network Control Plane Overview
Two key network-layer functions
Forwarding (Data Plane): Move packets from input → output link
Routing (Control Plane): Determine the path packets take from source to destination
Two approaches to control
Per-router control plane (Traditional)
Each router runs its own routing algorithm
Routers exchange information with neighbors
Software-Defined Networking (SDN)
Logically centralized controller computes routes
Installs forwarding tables into routers remotely
Routing Protocols
Goal
Determine “good” paths (least cost, fastest, least congested) from source to destination
Terminology
Path: sequence of routers a packet traverses
Cost: metric for evaluating routes (can depend on bandwidth, congestion, distance)
Graph Model: G = (N, E)
N: set of routers
E: set of links
C(a,b): cost of link between a and b (can be ∞ if no direct link)
Routing Algorithm Classification
Information
Global (Link-State): All routers know full topology and link costs
Decentralized (Distance Vector): Routers know only neighbor link costs and exchange info iteratively
Dynamics
Static: Routes change slowly
Dynamic: Routes adapt quickly to cost or topology changes
Link-State Routing (Dijkstra's Algorithm)
Core Ideas
Centralized view: all nodes know the network topology and link costs
Each node computes least-cost paths to all others → builds forwarding table
Uses iterative process: After k iterations, knows least-cost paths to k destinations
Notation
Cx,y: link cost from x to y (∞ if not neighbors)
D(v): current estimate of cost to destination v
p(v): predecessor node on the path to v
N': set of nodes with definitive least-cost path
Algorithm Steps
Initialize: N' = {source}. D(v) = C(source,v)
Find node a not in N' with minimum D(a)
Add a to N'
Update D(b) = min(D(b), D(a) + Ca,b) for all b adjacent to a
Repeat until all nodes in N'
Complexity
Computation: O(n^2), can be optimized to O(n log n)
Message Complexity: Each router floods its link-state info → O(n^2) total messages
Problem: Possible oscillations if link costs depend on traffic load
Distance Vector Routing (Bellman-Ford Algorithm)
Dx(y) = minv {Cx,v + Dv(y)
Each node x calculates cost to y as the minimum of (cost to neighbor v + v’s cost to y)
Operation
Each node maintains a distance vector (DV) – table of distances to all destinations
Periodically sends its DV to all neighbors
Updates its DV upon receiving updates or when local link cost changes
Characteristics
Iterative and asynchronous: updates triggered by local events or neighbor messages
Distributed: only local neighbor information is exchanged
Self-stopping: stops when no updates occur
Example Concepts
Nodes exchange and recompute DV iteratively
Distance info gradually diffuses through the network (hop by hop)
Link Cost Changes: "good news travels fast" but "bad news travels slow"
Leads to count-to-infinity problem
Solutions include poisoned reverse, split horizon, etc
Comparison
Link-State (LS)
Information: Global topology known
Convergence: Fast, predictable
Complexity: O(n^2)
Robustness: Localized faults
Issues: Oscillations
Distance Vector (DV)
Information: Neighbor info only
Convergence: Slower, may loop
Complexity: Variable
Robustness: Errors may propagate
Issues: Count-to-infinity
Hierarchical Routing
Scalability & Autonomy
The Internet = network of networks
Routers grouped into Autonomous Systems (AS)
Each AS has its own routing policy
Intra-AS routing: within the same AS
Inter-AS routing: between ASes
Types
Intra-AS Routing (Interior Gateway Protocols – IGP): RIP, EIGRP, OSPF
Inter-AS Routing (Exterior Gateway Protocol – EGP): BGP
Key Router Types
Gateway router: connects AS to others
Internal routers: operate within AS
Intra-AS Routing: OSPF (Open Shortest Path First)
Features
Link-state routing algorithm (based on Dijkstra)
Floods link-state advertisements (LSAs) to all routers in AS
Supports multiple metrics: bandwidth, delay, etc.
All OSPF messages are authenticated (security)
Hierarchical OSPF
Two-level hierarcy
Backbone area
Local areas
Routers
Internal routers: route within an area
Area border routers: summarize distances to other areas
Backbone routers: route within backbone
Boundary routers: connect to other ASes
Difference Intra- vs Inter-AS Routing
Intra-AS
Policy: Single admin → simple
Scale: smaller
Performance: Optimize efficiency
Inter-AS
Policy: Multiple admins → policy control crucial
Scale: Large-scale → hierarchical
Performance: Optimize policy compliance
Inter-AS Routing: BGP (Border Gateway Protocol)
Role
The de facto inter-domain routing protocol
“The glue that holds the Internet together”
Allows ASes to
Advertise reachable prefixes
Determine best routes based on policies and path attributes
Types
eBGP: exchanges between different ASes
iBGP: distributes routes within an AS
BGP Route Advertisement: Prefix + Attributes
AS-PATH: sequence of ASes traversed
NEXT-HOP: next router to reach destination
BGP Messages
OPEN: establish connection, authenticate peers.
UPDATE: advertise or withdraw routes.
KEEPALIVE: maintain connection.
NOTIFICATION: error or close session.
Routing Policies
Routes selected based on
Local preference (policy)
Shortest AS path
Closest next-hop (hot-potato routing)
Additional criteria
Policy control: ISPs may refuse to carry transit traffic (non-customers)
Hot Potato Routing: Choose the exit gateway with least intra-domain cost, ignoring inter-domain distance
Summary
Two approaches to control plane
Traditional per-router
Centralized (SDN)
Routing Algorithms
Link-State (OSPF) → global topology view
Distance Vector (Bellman-Ford) → local neighbor view
Scalable Routing
Hierarchical (AS structure)
Protocols
OSPF (intra-AS)
BGP (inter-AS)
Internet routing is a mix of efficiency, policy, and scalability