CNT3004 - Final Exam (CH.5&6)

control plane goals

* understand principles behind network control plane
* instantiation and implementation in Internet

control plane principles

* traditional routing algorithms
* SDN controllers
* network management and configuration

Internet instantiation/implementation

* OSFP, BGP
* OpenFlow, ODL, and ONOS controllers
* ICMP (Internet Control Message Protocol)
* SNMP, YANG/NETCONF

network layer functions

1\.) forwarding

2\.) routing

forwarding

* move packets from router's input to appropriate router output
* data plane

routing

* determine route taken by packets from source to destination
* control plane

structuring network control plane

2 approaches:


1. per-router control plane (traditional)
2. legally centralized control (software-defined networking)

per-router control plane

individual routing algorithm components in each and every router interact in control plane

software-defined networking (SDN) control plane

remote controller computes and installs forwarding table in routers

routing protocol

goal: determine "good" paths/routes from sending hosts to receiving host thru networking of routers

path

sequence of routers that packets traverse from given initial source host to final destination host

"good" path

least cost, fastest, least congested

Ca,b

cost of direct link connecting a and b

G = (N,E)

graph of link costs

N

set of routers = {u, v, w, x, y, z}

E

set of links = { (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z)}

routing algorithm classifications

1.) global2.) decentralized3.) static4.) dynamic

global

- all routers have complete topology and list cost info- ex: "link state" algorithms

decentralized

- iterative process of computation and exchange of info with neighbors- routers initially only know link costs to attached neighbors- ex: "distance vector" algorithm

static

routes change slowly over time

dynamic

- routing change more quickly- periodic updates or in response to link cost changes

centralized

- network topology, link costs known to all nodes- done via "link state broadcast"- all nodes have same info

Dijkstra's link-state routing algorithm

- computes least cost paths from one node (source) to all other nodes- gives forwarding table for that node

iterative

after k iterations, know least cost path to k destinations

Dijkstra's algorithm notation

- Cx,y: direct link cost from node x to y, equals to infinity if not direct neighbor- D(v): current estimate of cost of least-cost-path from source to destination vD(V) = min( D(v), D(w) + Cw,v)- p(v): predecessor node along path from source to v- N': set of nodes whose least-cost-path definitively known

Bellman-Ford equation

- Let Dx(y): cost of least-cost path from x to yThen: Dx(y) = min_v { Cx,v + Dv(y) }- min_v = min taken over all neighbors v of x- Cx,v = direct cost of link from x to v- Dv(y) = v's estimated least-cost-path cost to y

distance vector algorithm

- each node sends own distance vector estimate to neighbors- when x receives new DV estimate from any neighbor, updates its own DV using B-F equation- under minor and natural conditions: Dx(y) estimate converges to actual last cost dx(y)

distance vector algorithm steps

each node:1.) wait for change in local link cost or message from neighbor2.) recompute distance vector (DV) estimates using DV received from neighbor3.) if DV to any destination has changed, notify neighbors

iterative and asynchronous

each local iteration caused by:- local link cost change- DV update message from neighbor

distributed and self-stopping

each node notifies neighbors only when its DV changes- neighbors then notify their neighbors only if necessary- no notif received --> no actions taken

routing scale

- billions of destinations- can't store all in routing tables- routing table exchange would swamp links

administrative autonomy

- Internet: a network of networks- each network admin may want to control routing in its own network

autonomous systems

- AKA domains- regions that routers are aggregated into- 2 types:1.) intra-AS2.) inter-AS

intra-AS

- AKA "intra-domain"- routing within same AS (network)- all routers in AS must run same intra-domain protocol- routers in diff AS can run diff intra-domain routing protocols

gateway router

at "edge" of its own AS, has link(s) to router(s) in other AS'es

inter-AS

- AKA "inter-domain"- routing among AS'es- gateways perform inter-domain and intra-domain routing

Interconnected AS'es

- forwarding table configured by intra- and inter-AS routing algorithm- intra-AS routing determine entries for destination within AS- inter-AS and intra-AS determine entries for external destinations

AS inter-domain routing

must:- learn which destinations are reachable through neighboring AS'es- propagate this reachability info to all routers in AS

intra-AS routing protocols

1.) Routing Information Protocol (RIP)2.) Enhanced Interior Gateway Routing Protocol (EIGRP)3.) Open Shortest Path First (OSPF)

routing information protocol (RIP)

- classic DV: DVs exchanged every 30 secs- no longer widely used

enhanced interior gateway routing protocol (EIGRP)

- DV based- formerly Cisco-proprietary for decades

open shortest path first (OSPF)

- link-state routing- IS-IS protocol

OSPF routing

- "open" and publicly available- classic link-state- security: all OSPF messages authenticated to prevent malicious intrusion

classic link-state

- each router floods OSPF link-state advertisements to all other routers in entire AS- multiple link costs metrics possible (bandwidth, delay)- each router has full topology and uses Dijkstra's algorithm to compute forwarding table

hierarchical OSPF

- 2 level hierarchy: local area and backbone- link-state advertisements flooded only in area or backbone- each node has detailed area topology (only knows direction to reach other destinations)

area border routers

"summarize" distances to destinations in own area, advertise in backbone

local routers

- flood link state in area only- compute routing within area- forward packets to outside via area border router

boundary router

connects to other AS'es

backbone router

runs OSPF limited to backbone

Border Gateway Protocol (BGP)

- the "de facto" inter-domain routing protocol- allows subnet to advertise its existence and destinations it can reach to rest of Internet- provides each AS to determine "good" routes to other networks

eBGP

obtain subnet reachability info from neighboring AS'es

iBGP

propagate reachability info to all AS-internal routers

BGP session

- 2 BGP routers ("peers") exchange BGP messages over semi-permanent TCP connection- advertising paths to different destination network prefixes- BGP is a "path vector" protocol

BGP advertised route

- prefix and attributes- 2 important attributes:1.) AS-PATH2.) NEXT-HOP

prefix

destination being advertised

AS-PATH

list of AS'es through which prefix advertisement has passed

NEXT-HOP

indicates specific internal-AS router to next-hop AS

policy-based routing

- gateway receiving route advertisement uses import policy to accept/decline path- AS policy also determines whether to advertise path to other neighboring AS'es

BGP messages

- exchanges between peers over TCP connection- 4 types:1.) OPEN2.) UPDATE3.) KEEPALIVE4.) NOTIFICATION

OPEN

opens TCP connection to remote BGP peer and authenticates sending BGP peer

UPDATE

advertises new path (or withdraws old)

KEEPALIVE

- keeps connection alive in absence of UPDATES- also ACKS OPEN request

NOTIFICATION

- reports errors in previous msg- used to close connection

inter vs intra AS -- policy

- inter-AS: admin wants control over how traffic is routed and who routes thru its network- intra-AS: single admin, less of a policy issue

inter vs intra AS -- performance

- intra-AS: can focus on performance- inter-AS: policy dominates over performance

hierarchical routing

- saves table size- reduced upon traffic

hot potato routing

- choose local gateway that has least intra-domain cost- doesn't worry about inter-domain cost

BGP route selection

router selects route based on:1.) local preference value attribute (policy decision)2.) shortest AS-PATH3.) closes NEXT-HOP router (hot potato routing)4.) additional criteria

logically centralized control plane

- easier network management: avoid router misconfigs, greater flexibility of traffic flows- table-based forwarding allows "programming" routes- open (non-proprietary) implementation of control plane

centralized "programming"

- easier- compute tables centrally and distribute

distributed "programming"

- more difficult- compute tables as a result of distributed algorithm (protocol) implemented in each and every router

SDN aspects

1.) generalized "flow-based" forwarding (ex: OpenFlow)2.) control and data plane separation3.) control plane functions are outside data-plane switches4.) programmable control applications

data-plane switches

- fast, simple, commodity switches implementing generalized data-plane forwarding in hardware- flow (forwarding) table computed and installed under controller supervision- API for table-based switch control --> defines what is controllable and what's not- protocol for communicating with controller- ex: OpenFlow

SDN controller

- AKA network operating system- maintain network state info- interacts with network control applications "above" via northbound API- interacts with network switches "below" via southbound API- implemented as distributed system for performance, scalability, fault-tolerance, robustness

network-control apps

- "brains" of control: implement control functions using lower-level services and API provided by SDN controller- unbundled: can be provided by 3rd party (different from routing vendor or SDN controller)

SDN controller components

1.) interface layer2.) network-wide state management3.) communication

interface layer

- for network control apps- contains abstractions API and network graphs

network-wide state management

- state of network links, switches, and services- a distributed database- contains flow tables

communication

- communicate between SDN controller and controlled switches- includes OpenFlow and SNMP

OpenFlow protocol

- operates between controller and switch- TCP used to exchange messages- 3 classes of messages:1.) controller-to-switch2.) asynchronous (switch to controller)3.) symmetric (misc.)

OpenFlow API

- used to specify generalized forwarding actions- *not* the same as OpenFlow protocol

controller-to-switch messages

4 key messages:1.) features2.) configure3.) modify-state4.) packet-out

features

controller queries switch features, switch replies

configure

controller queries/sets switch configuration parameters

modify-state

add, delete, and modify flow entries in the OpenFlow tables

packet-out

controller can send this packet out of specific switch port

switch-to-controller messages

3 key messages:1.) packet-in2.) flow-removed3.) port-status

packet-in

transfer packet (and its control) to controller

flow-removed

flow table entry deleted at switch

port status

inform controller of a change on a port

control/data plane interaction example

1.) router experiences link failure, uses OpenFlow port status message to notify controller2.) SDN controller receives OpenFlow message and updates link status info3.) Dijkstra's routing algorithm application is called (registered to be called whenever link status changes)4.) Dijkstra's routing algorithm accesses network graph info and link state info in controller, computes new routes5.) link state routing app interacts with flow table computation component in SDN controller (which computes new flow tables needed)6.) controller uses OpenFlow to install new tables in switches that need updating

internet control message protocol (ICMP)

- used by hosts and routers to communicate network-level info- used for error reporting (unreachable host/network/port) and to echo request/reply (ping)- network layer "above" IP

ICMP message

- type, code, and first 8 bytes of IP datagram causing error- carried in IP datagramsex: type 8 -- echo request (ping)

traceroute and ICMP

- source sends sets of UDP segments to destinations- datagram in nth set arrives to nth router --> router discards datagram and sends source ICMP message- record RTTs when ICMP message arrives at source

traceroute and ICMP stopping criteria

- UDP segment eventually arrives at destination host- destination returns ICMP "port unreachable" message (type 3, code 3)- source stops

autonomous systems

- AKA network- thousands of interaction hardware/software components

network management

- management and coordination of hardware, software, and human elements- manage network resources in order to meet performance requirements

components of network management

- managing server- network management protocol- managed device- data

managing server

application, typically with network managers (humans) in loop

network management protocol

- used by managing server to query, configure, and manage devices- used by devices to inform managing server of data and events