Brainscape's Knowledge GenomeTM

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


See full index

CS3102: Networking > Control Plane > Flashcards

Control Plane Flashcards

1
Q

What is the goal of a routing protocol?

A

Determine good paths from sending hosts to receiving host, through network of routers.

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

What does good mean in terms of routing protocols?

A

Least cost
Fastest
Least congested

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

What is a global routing algorithm?

A

All routers have complete topology and link cost info of the network

Link state algorithms

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

What is a decentralised routing algorithm?

A

Router knows neighbours and link cost to them.

Iteratively compute and exchange information with neighbours

Distance vector algorithms

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

Give an example of a link-state routing algorithm

A

Dijkstra’s algorithm:
Network topology and link costs known to all nodes, done via broadcast.

Computes least cost paths from one node to all other nodes; Giving the forwarding table for that node.

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

What is the notation used for Dijkstra’s algorithm

A

c(x,y) - cost from node x to y

D(v): current value of cost of path from source to dest v.

p(v): Predeccessor node along path from source to v

N’: set of nodes whose least cost path definitively known.

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

How does Dijkstra’s algorithm work?

A

Initialise all nodes, finding the cost of all edges between adjacent nodes.

Find the minimum path between current node and a destination node.

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

What is the Bellman-Ford equation?

A

d_x(y) = cost of least-cost path from x to y.

then

d_x(y) = min{c(x,v) + d_v(y)}

AKA minimum of the cost of going to a neighbour, and then from the neighbour to the destination, for all neighbours.

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

What is the key idea behind the distance vector algorithm?

A

From time-to-time, each node sends its own distance vector estimate to neighbours. When x receives new DV estimate from neighbors, it updates its own DV using B-F equation

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

What are properties of the distance vector algorithm?

A

iterative and asynchronus: Each local iteration caused by link cost change or neighbour update.

Distributed: Each node notifies only when its DV changes.

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

How are link cost changes detected in Distance Vector algorithms?

A

Node detects local link cost change

Updating routing info, recalculates and if there’s a change, notifies neighbours.

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

How are positive changes in the cost of nodes distributed when using the distance vector algorithm?

A

Y detects link-cost change, updates its DV and informs its neighbours

Z receives update from y, updates its table, computes new least cost to x and sends its neighbours its DV

y receives z’s update, updates its distance table. y’s least costs do not change, so y doesn’t send a message to z.

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

How are negative changes in the cost of nodes distributed when using the distance vector algorithm?

A

Node detect local link cost change, and bad news travels slow. Tells others it’s an infinite cost so no-one will take it, until a stabilisation is met.

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

What are the comparisons between Link-state and Distance-Vector algorithms?

A

Message complexity: LS with n nodes, E links, O(nE) msgs sent.

Speed of convergence:
LS: O(n^2) algorithm require O(nE) msgs.
DV:

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

What are the differences in message complexity between Link-State and Distance-Vector algorithms?

A

Link-state: With n nodes, E edges, O(nE) messages sent

Distance-Vector: Exchanges between neighbours only, varying convergence time.

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

What are the differences in speed of convergence between Link-state and Distance-vector algorithms?

A

LS: O(n^2) algorithm requires O(nE) msgs, may have oscillations

DV: Convergence time varies, may be routing loops and also suffers from the counting to infinity problem.

17
Q

What are the differences in robustness between Link-state and Distance-vector algorithms

A

LS: Can advertise incorrect link cost, each node computes only its own table.

DV: Node can advertise incorrect path cost, each node’s table used by others - causing errors to be propagated through the network.

18
Q

What is the count to infinity problem when using Distance-Vector algorithms.

A

Routing loop.
Routing loops usually occur when an interface goes down.

Can also occur when two routers send updates to each other at the same time.

19
Q

How is routing made scalable?

A

Through the use of autonomous systems (AS) aka: Domains.

20
Q

Why does routing need to be made scalable?

A

With billions of devices, it’s not feasible to store all destinations in routing tables - otherwise the tables would swamp links.

21
Q

What is intra-AS routing?

A

Routing among hosts, routers in same network.

All routers in AS run same intra-domain protocol.

22
Q

What is a gateway router?

A

At edge of its own AS, has link(s) to router(s) in other AS’es

23
Q

What is inter-AS routing?

A

Routing among AS’es

Gateways perform inter-domain routing (as well as intra-domain routing).

24
Q

How are routing destinations’s entries to the routing table handle dby an AS

A

Inter-AS and Intra-AS determine entries for external destinations.

intra-AS routing determines entries for internal destinations.

25
Q

What is the Interior gateway protocol (IGP)?

A

AS learns the destinations reachable via it’s connected AS’es, then propogates the information to all routers in intra-AS.

26
Q

What is OSPF?

A

Open shortest Path First

Uses link-state algorithm.

Floods OSPF link-state advertisements to all other routers in the entire AS, carried over IP.

Spreads information on cost of links throughout the network.

27
Q

What are the advanced features of OSPF?

A

Security as messages are authenticated.

Can have multiple same-cost paths.

Can have multiple cost metrics for different types of service.

Supports uni and multicast.

Hierarchical OSPF in large domains.

28
Q

What is BGP?

A

Border Gateway Protocol.

eBGP: Obtain subnet reachability information from neighbouring ASes

iBGP: Propogate reachability information to all AS-internal routers.

Determine good routes to other networks based on reachability and information policy.

29
Q

How does BGP work?

A

Two reouters exchange BGP messages over semi-permanent TCP connection - advertises paths to different destination network prefixes.

When advertised, AS is saying that it will be glad to forward packets for advertised router.

30
Q

What are the attributes of a path?

A

AS-PATH: List of ASes through which prefix advertisement has passed.

NEXT-HOP: Indicates specific internal-AS router to next-hop AS

31
Q

What is policy-based routing?

A

Gateway receiving route advertisement uses import policy to accept/decline path.

AS policy also determines whether to advertise path to other neighbouring ASes.

EG: don’t route through China.

32
Q

What are the BGP messages?

A

OPEN: opens TCP connection to remote BGP peer & authenticates sending BGP peer.

UPDATE: Advertises new path, or withdraws old.

KEEPALIVE: Keeps connection alive, also ACKS the OPEN.

NOTIFICATION: Report errors in msg or close connection.

33
Q

How does BGP select a route to take?

A

Makes decisions based on:

  1. Policy decisions
  2. Shortest AS-PATH
  3. Closest NEXT-HOP router: Hot potato routing
  4. Other things.
34
Q

What is hot potato routing?

A

Choose a local gateway that has least intra-domain cost

35
Q

How can BGP policy be enforced?

A

Don’t advertise to AS that aren’t allowed in policy.

36
Q

Why have an intra and inter AS for routing with policy enforcement?

A

Policy enforcement: Inter-AS the admin wants control over how traffic is routed and who is routed through net.

Intra-AS: Single admin, so no plicy decisions needed

37
Q

Why have an intra and inter AS for routing with scale?

A

Hierarchical routing saves table size, reduced update traffic.

Performance: intra-AS: can focus on performance.

Inter-AS: Policy may dominate over performance.

CS3102: Networking (6 decks)

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