Network Layer: Control Plane Flashcards
Introduction
Network-Layer Functions
Forwarding: move pckts from router input to output, local action, data-plane
Routing: determine route from src-dest, global action, control-plane
Introduction
Two approaches to structuring network control plan
- Per-router control (traditional)
- Logically centralized control (software defined networking)
Introduction
Per-Router Control Plane
- Traditional
- Individual routing algorithm components in each router
- Router makes its own routing table
Introduction
Software-Defined Networking (SDN) Control Plane
- Remote controller computes, installs forwarding tables in routers
Introduction
Routing Protocol Goal
Determine “good” paths from sending hosts to recieving host through network of routers
Introduction
Path
- Sequence of routers
- Packets traverse from given initial src host to final dest host
Introduction
“Good” Path
Least cost, fastest, least congested
Introduction
Routing Alogirithm Classification
- Global
- Static
- Dynamic
- Decentralized
Introduction
Routing Algorithm Classification: Global
- All routers have complete topology, link cost info
- Uses link state algorithms
Introduction
Routing Algorithm Classification: Static
Route changes slowly over time
Introduction
Routing Algorithm Classification: Dynamic
- Routes change more quickly
- Periodic updates or in reponse to link cost changes
Introduction
Routing Algorithm Classification: Decentralized
- Iterative process of computation, exchange of info with neighbors
- Routers intilially only know link cost to attached neighbors
- uses distance vector algorithms
Routing Protocols: Link State
Dijkstra’s Link-State Routing Algorithm
All link costs known by all nodes
Centralized: network topology, link cost known to all nodes, accomplished via “link state broadcast*”
Computes least cost path frfrom one node to all other nodes
Iterative: after k iterations, know least cost path to k destinations
Routing Protocols: Link State
Dijkstra’s Example
Routing Protocols: Link State
Djikstra’s Algorithm Complexity
- n Nodes
- Each of n iterations, need to check all nodes, w, not in N
- n(n+1)/2 comparisons: O(n^2) complexity
Routing Protocols: Link State
Djikstra’s Message Complexity
- Each router must broadcast its link state info to all other n routers
- Efficient broadcast algorithms: O(n) link crossings to disseminate a broadcast message
- Each router’s message crosses O(n) links: overall message complexity: O(n^2)
Routing Protocols: Link State
Djikstra’s Algorithm: Oscillations Possible
- When link costs depend on traffic volume (congestion), route oscillations possible
- So, would need to recalculate least-cost path
Routing Protocols: Distance Vector
Bellman-Ford Distance Vector Algorithm
*Nodes only know link cost of neighbors
D_x(y) = min_v{c_x,v + D_v(y)}
Dx(y):cost of least-cost path from x to y
min_v: min taken over all neighbors v of x
c_x,v: direct cost of link from x to v
D_v(y): v’s estimated least-cost path cost to y
(Each node stores cost until goal)
(works kinda like greedy)
Routing Protocols: Distance Vector
Distance Vector Alg Key Idea
- from time-to-time, each node sends its own distance vector estinmate to neighbors
- When x recieves new DV estimate from any neighbor, updates its own DV using B-F equation:
D_x(y) <- min_v{c_x,v + D_v(y)}
Routing Protocols: Distance Vector
Distance Vector Algorithm Steps
For each node:
wait: for change in local link cost or msg from neighbor
recompute: DV estimates using DV received from neighbor
notify: neighbors if DV to dest has changes
Routing Protocols: Distance Vector
Distance Vector Algorithm Attributes
Iterative, Asynchronous: each local iteration cause by local link cost change or msg from neighbor
Distributed, Self-Stopping: each node notifies nieghbors only when its DV changes, if no notification recieved then no action taken
Routing Protocols: Distance Vector
Distance Vector Algorithm Example
Routing Protocols: Distance Vector
Bellman-Ford Example
Intra-ISP Routing
Scalable Routing
- Billions of possible destinations, can’t store all in routing tables
- Use hierarchy routing
Intra-ISP Routing
Administrative Autonomy Routing
- Internet is network of networks
- Each local network can have its own routing policy
Intra-ISP Routing
Intra-AS (intra-domain)
- Routing within the same AS/network
- All routers in same AS must run same intra-domain routing protocol
Intra-ISP Routing
Inter-AS (inter-domain)
- Routing among different AS/networks
- Gateway routers perform both inter and intra-domain routing
Intra-ISP Routing
Gateway Router
- At edge of its own AS
- Has link to routers in other AS
Intra-ISP Routing
OSPF
- Open shortest path first
- “open”: publicly avaliable
- Link-state routing, each router floods OSPF link-state advertisements directly over IP
- Each router has full topology
Intra-ISP Routing
OSPF Security
All OSPF messages authenticated to prevent malicious intrusion
Intra-ISP Routing
Heirarchical OSPF
- Two-level heirarchy, local area and backbone
- Link-state advertisements flooded only in backbone/area
- Each node has detailed backbone/area topology
Intra-ISP Routing
OSPF: Area Border Routers
- “Summarize” distances to destinations in own area
- Advertise in backbone
Intra-ISP Routing
OSPF: Local Routers
- Flood LS in area only
- Compute routing within area
- Forward packets to outside via area border
Intra-ISP Routing
OSPF: Boundary Router
Connects to other AS/networks
Intra-ISP Routing
OSPF: Backbone Router
Runs OSPF limited to backbone/area
