Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS 455 > Network Layer: Control Plane > Flashcards

Network Layer: Control Plane Flashcards

1
Q

Introduction

Network-Layer Functions

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Introduction

Two approaches to structuring network control plan

A
  • Per-router control (traditional)
  • Logically centralized control (software defined networking)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Introduction

Per-Router Control Plane

A
  • Traditional
  • Individual routing algorithm components in each router
  • Router makes its own routing table
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Introduction

Software-Defined Networking (SDN) Control Plane

A
  • Remote controller computes, installs forwarding tables in routers
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Introduction

Routing Protocol Goal

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Introduction

Path

A
  • Sequence of routers
  • Packets traverse from given initial src host to final dest host
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Introduction

“Good” Path

A

Least cost, fastest, least congested

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Introduction

Routing Alogirithm Classification

A
  1. Global
  2. Static
  3. Dynamic
  4. Decentralized
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Introduction

Routing Algorithm Classification: Global

A
  • All routers have complete topology, link cost info
  • Uses link state algorithms
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Introduction

Routing Algorithm Classification: Static

A

Route changes slowly over time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Introduction

Routing Algorithm Classification: Dynamic

A
  • Routes change more quickly
  • Periodic updates or in reponse to link cost changes
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Introduction

Routing Algorithm Classification: Decentralized

A
  • Iterative process of computation, exchange of info with neighbors
  • Routers intilially only know link cost to attached neighbors
  • uses distance vector algorithms
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Routing Protocols: Link State

Dijkstra’s Link-State Routing Algorithm

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Routing Protocols: Link State

Dijkstra’s Example

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Routing Protocols: Link State

Djikstra’s Algorithm Complexity

A
  • n Nodes
  • Each of n iterations, need to check all nodes, w, not in N
  • n(n+1)/2 comparisons: O(n^2) complexity
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Routing Protocols: Link State

Djikstra’s Message Complexity

A
  • 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)
17
Q

Routing Protocols: Link State

Djikstra’s Algorithm: Oscillations Possible

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

Routing Protocols: Distance Vector

Bellman-Ford Distance Vector Algorithm

A

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

19
Q

Routing Protocols: Distance Vector

Distance Vector Alg Key Idea

A
  • 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)}
20
Q

Routing Protocols: Distance Vector

Distance Vector Algorithm Steps

A

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

21
Q

Routing Protocols: Distance Vector

Distance Vector Algorithm Attributes

A

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

22
Q

Routing Protocols: Distance Vector

Distance Vector Algorithm Example

A
23
Q

Routing Protocols: Distance Vector

Bellman-Ford Example

A
24
Q

Intra-ISP Routing

Scalable Routing

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

Intra-ISP Routing

Administrative Autonomy Routing

A
  • Internet is network of networks
  • Each local network can have its own routing policy
26
Q

Intra-ISP Routing

Intra-AS (intra-domain)

A
  • Routing within the same AS/network
  • All routers in same AS must run same intra-domain routing protocol
27
Q

Intra-ISP Routing

Inter-AS (inter-domain)

A
  • Routing among different AS/networks
  • Gateway routers perform both inter and intra-domain routing
28
Q

Intra-ISP Routing

Gateway Router

A
  • At edge of its own AS
  • Has link to routers in other AS
29
Q

Intra-ISP Routing

OSPF

A
  • 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
30
Q

Intra-ISP Routing

OSPF Security

A

All OSPF messages authenticated to prevent malicious intrusion

31
Q

Intra-ISP Routing

Heirarchical OSPF

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

Intra-ISP Routing

OSPF: Area Border Routers

A
  • “Summarize” distances to destinations in own area
  • Advertise in backbone
33
Q

Intra-ISP Routing

OSPF: Local Routers

A
  • Flood LS in area only
  • Compute routing within area
  • Forward packets to outside via area border
34
Q

Intra-ISP Routing

OSPF: Boundary Router

A

Connects to other AS/networks

35
Q

Intra-ISP Routing

OSPF: Backbone Router

A

Runs OSPF limited to backbone/area

CS 455 (11 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions