Network Layer: Control Plane

Question 1

Introduction

Network-Layer Functions

Answer 1

Forwarding: move pckts from router input to output, local action, data-plane
Routing: determine route from src-dest, global action, control-plane

Question 2

Introduction

Two approaches to structuring network control plan

Answer 2

• Per-router control (traditional)
• Logically centralized control (software defined networking)

Question 3

Introduction

Per-Router Control Plane

Answer 3

• Traditional
• Individual routing algorithm components in each router
• Router makes its own routing table

Question 4

Introduction

Software-Defined Networking (SDN) Control Plane

Answer 4

• Remote controller computes, installs forwarding tables in routers

Question 5

Introduction

Routing Protocol Goal

Answer 5

Determine “good” paths from sending hosts to recieving host through network of routers

Question 6

Introduction

Path

Answer 6

• Sequence of routers
• Packets traverse from given initial src host to final dest host

Question 7

Introduction

“Good” Path

Answer 7

Least cost, fastest, least congested

Question 8

Introduction

Routing Alogirithm Classification

Answer 8

1. Global
2. Static
3. Dynamic
4. Decentralized

Question 9

Introduction

Routing Algorithm Classification: Global

Answer 9

• All routers have complete topology, link cost info
• Uses link state algorithms

Question 10

Introduction

Routing Algorithm Classification: Static

Answer 10

Route changes slowly over time

Question 11

Introduction

Routing Algorithm Classification: Dynamic

Answer 11

• Routes change more quickly
• Periodic updates or in reponse to link cost changes

Question 12

Introduction

Routing Algorithm Classification: Decentralized

Answer 12

• Iterative process of computation, exchange of info with neighbors
• Routers intilially only know link cost to attached neighbors
• uses distance vector algorithms

Question 13

Routing Protocols: Link State

Dijkstra’s Link-State Routing Algorithm

Answer 13

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

Question 14

Routing Protocols: Link State

Dijkstra’s Example

Question 15

Routing Protocols: Link State

Djikstra’s Algorithm Complexity

Answer 15

• n Nodes
• Each of n iterations, need to check all nodes, w, not in N
• n(n+1)/2 comparisons: O(n^2) complexity

Question 16

Routing Protocols: Link State

Djikstra’s Message Complexity

Answer 16

• 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)

Question 17

Routing Protocols: Link State

Djikstra’s Algorithm: Oscillations Possible

Answer 17

• When link costs depend on traffic volume (congestion), route oscillations possible
• So, would need to recalculate least-cost path

Question 18

Routing Protocols: Distance Vector

Bellman-Ford Distance Vector Algorithm

Answer 18

*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)

Question 19

Routing Protocols: Distance Vector

Distance Vector Alg Key Idea

Answer 19

• 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)}

Question 20

Routing Protocols: Distance Vector

Distance Vector Algorithm Steps

Answer 20

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

Question 21

Routing Protocols: Distance Vector

Distance Vector Algorithm Attributes

Answer 21

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

Question 22

Routing Protocols: Distance Vector

Distance Vector Algorithm Example

Question 23

Routing Protocols: Distance Vector

Bellman-Ford Example

Question 24

Intra-ISP Routing

Scalable Routing

Answer 24

• Billions of possible destinations, can’t store all in routing tables
• Use hierarchy routing

Question 25

# Intra-ISP Routing Administrative Autonomy Routing

Answer 25

* Internet is network of networks * Each local network can have its own routing policy

Question 26

# Intra-ISP Routing Intra-AS (intra-domain)

Answer 26

* Routing within the same AS/network * All routers in same AS must run same intra-domain routing protocol

Question 27

# Intra-ISP Routing Inter-AS (inter-domain)

Answer 27

* Routing among different AS/networks * Gateway routers perform both inter and intra-domain routing

Question 28

# Intra-ISP Routing Gateway Router

Answer 28

* At edge of its own AS * Has link to routers in other AS

Question 29

# Intra-ISP Routing OSPF

Answer 29

* 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

Question 30

# Intra-ISP Routing OSPF Security

Answer 30

All OSPF messages authenticated to prevent malicious intrusion

Question 31

# Intra-ISP Routing Heirarchical OSPF

Answer 31

* Two-level heirarchy, **local area** and **backbone** * Link-state advertisements flooded only in backbone/area * Each node has detailed backbone/area topology

Question 32

# Intra-ISP Routing OSPF: Area Border Routers

Answer 32

* "Summarize" distances to destinations in own area * Advertise in backbone

Question 33

# Intra-ISP Routing OSPF: Local Routers

Answer 33

* Flood LS in area only * Compute routing within area * Forward packets to outside via area border

Question 34

# Intra-ISP Routing OSPF: Boundary Router

Answer 34

Connects to other AS/networks

Question 35

# Intra-ISP Routing OSPF: Backbone Router

Answer 35

Runs OSPF limited to backbone/area