4.2 Network Layer - The Control Plane Flashcards
what are the two approaches to structuring the network control plane?
Per-router control plane:
Individual routing algorithm components in each and every router interact with each other in control plane to compute forwarding tables
Logically centralised control plane: A distinct (typically remote) controller interacts with local control agents (CAs) in routers to compute forwarding tables
what are the classifications of routing algorithm? (4)
Q: global or decentralised information? global: • all routers have complete topology, link cost info •“link state” algorithms decentralised: • router knows physicallyconnected neighbours, link costs to neighbours • iterative process of computation, exchange of info with neighbours •“distance vector” algorithms
Q: static or dynamic? static: • routes change slowly over time dynamic: • routes change more quickly • periodic update • in response to link cost changes
what is Dijksta’s algorithm?
Dijkstra’s algorithm
• net topology, link costs known to all nodes
• accomplished via “link state broadcast”
• all nodes have same info
• 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 dest.s
c(x,y): link cost from node x to y; = ∞ if not directneighbours
• D(v): current value of cost of path from source to
dest. v
• p(v): predecessor node along path from source to v
• N’: set of nodes whose least cost path definitively
known
1 Initialization:
2 N’ = {u}
3 for all nodes v
4 if v adjacent to u
5 then D(v) = c(u,v)
6 else D(v) = ∞
7
8 Loop
9 find w not in N’ such that D(w) is a minimum
10 add w to N’
11 update D(v) for all v adjacent to w and not in N’ :
12 D(v) = min( D(v), D(w) + c(w,v) )
13 /* new cost to v is either old cost to v or known
14 shortest path cost to w plus cost from w to v */
15 until all nodes in N’
what is the bellman-ford equation?
a distance vector algorithm
let dx(y) := cost of least-cost path from x to y then
dx(y) = min {c(x,v) + dv(y) }
min is taken of all neighbours v of x
c is the cost to neighbour v
key idea:
• from time-to-time, each node sends its own distance vector
estimate to neighbours
• when x receives new DV estimate from neighbour, it updates
its own DV using B-F equation
iterative, asynchronous: each local iteration caused by: • local link cost change • DV update message from neighbour distributed: • each node notifies neighbours only when its DV changes • neighbours then notify their neighbours if necessary
what are problems with the distance vector algorith?
idk look it up in the bookl
how do distance vector and link state algorithms compare? message complexity, speed of convergence, robustness
message complexity • LS: with n nodes, E links, O(nE) msgs sent • DV: exchange between neighbours only • convergence time varies
speed of convergence • LS: O(n^2) algorithm requires O(nE) msgs • may have oscillations • DV: convergence time varies • may be routing loops • count-to-infinity problem
robustness: what happens if router malfunctions? LS: • node can advertise incorrect link cost • each node computes only its own table DV: • DV node can advertise incorrect path cost • each node’s table used by others • errors propagate through network
how does the internet deal with scalable routing? why?
can’t store all the routing data on every possible node, wouldn’t scale and setup would swamp the network
aggregate routers into regions known as “autonomous systems” (AS) (a.k.a. “domains”)
intra-AS routing
routing among hosts, routers in same AS (“network”)
all routers in AS must run same intra-domain protocol
routers in different AS can run different intra-domain
routing protocol
gateway router: at “edge” of its own AS, has link(s) to
router(s) in other AS’es
inter-AS routing
• routing among AS’es
• gateways perform interdomain routing (as well
as intra-domain routing)
how does a router in an AS (domain) know which gateway to use?
AS1 must:
- learn which dests are reachable through AS2, which through AS3
- propagate this reachability info to all routers in AS1
•RIP: Routing Information Protocol •OSPF: Open Shortest Path First (IS-IS protocol essentially same as OSPF) •IGRP: Interior Gateway Routing Protocol (Cisco proprietary for decades, until 2016)
what is hierarchical OSPF?
two-level hierarchy: local area, backbone.
• link-state advertisements only in area
• each nodes has detailed area topology; only know direction
(shortest path) to nets in other areas.
• area border routers: “summarise” distances to nets in own area,
advertise to other Area Border routers.
• backbone routers: run OSPF routing limited to backbone.
• boundary routers: connect to other AS’
es.
what is the BGP?
BGP (Border Gateway Protocol): the de facto inter-domain routing protocol
• “glue that holds the Internet together”
allows subnet to advertise its existence to rest of Internet: “I am here”
BGP provides each AS a means to:
• eBGP: obtain subnet reachability information from
neighbouring ASes
• iBGP: propagate reachability information to all AS-internal
routers.
• determine “good” routes to other networks based on reachability
information and policy
BGP session: two BGP routers (“peers”) exchange BGP
messages over semi-permanent TCP connection:
• advertising paths to different destination network prefixes (BGP is a “path vector” protocol)
when AS3 gateway router 3a advertises path AS3,X to AS2 gateway router 2c:
• AS3 promises to AS2 it will forward datagrams towards X
advertised prefix includes BGP attributes
• prefix + attributes = “route”
• two important attributes:
• AS-PATH: list of ASes through which prefix advertisement has passed
• NEXT-HOP: indicates specific internal-AS router to next-hop AS
AS2 router 2c receives path advertisement AS3,X (via eBGP) from AS3 router 3a
Based on AS2 policy, AS2 router 2c accepts path AS3,X,
propagates (via iBGP) to all AS2 routers
Based on AS2 policy, AS2 router 2a advertises (via eBGP) path
AS2, AS3, X to AS1 router 1c
gateway router may learn about multiple paths to destination:
what are the four BGP messages?
• 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; also used to close
connection
what is hot potato routing?
• 2d learns (via iBGP) it can route to X via 2a or 2c
• hot potato routing: choose local gateway that has least intra-domain
cost (e.g., 2d chooses 2a, even though more AS hops to X): don’t
worry about inter-domain cost!
how can slimy ISPs maniuplate BGP?
choose not to advertise routes to ASs because they dont want to take the traffic
Why different Intra-, Inter-AS routing?
policy:
• inter-AS: admin wants control over how its traffic routed, who
routes through its net.
• intra-AS: single admin, so no policy decisions needed
scale:
• hierarchical routing saves table size, reduced update traffic
performance:
• intra-AS: can focus on performance
• inter-AS: policy may dominate over performance
