Module 4: IP Routing - I

Question 1

flat vs. hierarchical addressing

Answer 1

flat:
- ethernet addressing

hierarchical:
- provide layers or a hierarchy to the address (phone number)
- ip addressing uses hierarchical

MAC and IP address functionality
- the MAC address generally remains fixed and follows the network device, but the IP address changes as the network device moves from one network to another

Question 2

what does network mask define?

Answer 2

which bits are used to describe the network part

Question 3

Describe addressing for IP addresses.

Answer 3

Question 4

Classful Addressing vs. Classless

Answer 4

Classful:
simple
tends to be wasteful
uses the same subnet mask for each subnet, and all the subnets have the same number of addresses in them

Classless:
refers to VLSM
benefits: allows the use of multiple mask lengths, breaks up an address block into smaller custom blocks, provides more flexibility in network design.

Question 5

Internet Routing:

Answer 5

What is the first level? autonomous systems (AS’s)

AS’s run an intra domain routing protocol (eg DV (Routing Information Protocol), LS (Open Shortest Path First)

Between AS’s runs inter-domain routing protocols (Border Gateway Routing)

today: BGP-4

Question 6

Intra-domain routing protocols is based on what?

Answer 6

unreliable datagram delivery

Question 7

How does link state work?

Answer 7

Open shortest-path first (OSPF)
Each network periodically floods immediate reachability information to other routers
Fast convergence, but high communication and computation overhead

Question 8

How does distance vector work?

Answer 8

Routing information protocol (RIP) based on Bellman-Ford
Each neighbor periodically exchange reachability information to its neighbors
Minimal communication overhead, but it takes long to converge, i.e., in proportion to the maximum path length

Question 9

What is flooding?

Answer 9

Every node broadcasts information to every node
Be careful not to do anything redundant or make cycles!

Question 10

Why is DV more efficient than link state?

Answer 10

Because we don’t have to flood the network like in LS. Minimal communication.

Question 11

Even though DV has less communication overhead than LS, what is the downside?

Answer 11

Takes longer to converge, i.e., in proportion to the maximum path length
Might not converge at all (infinite loops)

Question 12

What is the goal of routing?

Answer 12

determine a “good”path through the network from source to destination

good = the shortest path usually

Question 13

Describe the network modeled as a graph

Answer 13

routers -> nodes
link -> edges
(edge costs = delays, congestion, etc)

Question 14

T/F
BGP is an intra domain protocol used to connect one AS to another

Answer 14

False
It is an INTER-domain routing protocol

Question 15

Describe link state flooding

Answer 15

• each router maintains link state database and periodically sends link state packets (LSP) to neighbor
• LSP = router, neighbors, costs
  -each router forwards LSPs not already in its database on all ports except where received
• each LSP will travel over the same link at most once in each direction
• flooding is fast, and can be made reliable with link-layer acknowledgements and periodic re-flooding
• two types of updates: triggered and periodic
• when link/router fails need to remove all data using sequence numbers to determine new data, send a new LSP with cost infinity to signal a link down, LSP have TTL (soft-state)

Question 16

key advantage of link state

Answer 16

fast convergence

Question 17

When a router receives a LSP, it will forward this packet to all links connected to it.

Answer 17

False

Question 18

What is the end result of the link state flooding?

Answer 18

Every node has all the topology information

Question 19

Dijkstra’s algorithm

Answer 19

Net topology, link costs known to all node
– flooding
– all nodes have the same info
Compute least cost paths from one node to all other nodes
Iterative: after k iterations, know least cost paths to k closes destinations

Question 20

In the Dijkstra algorithm, D(v) always goes down monotonically, which is the cost from a specific node to node v?

Answer 20

True

Question 21

What is the basic idea of the DV algo?

Answer 21

• tell neighbors about learned distances to all destinations
• each router maintains a vector of costs to all destinations as well as a routing table
• initialize neighbors with known cost, others with infinity

Question 22

DV Routing algo is…

Answer 22

1. iterative: continues until no nodes exchange info
2. asynchronous: nodes need not exchange info/iterate in lock steps
3. distributed: each node communicates only with directly attached neighbors

Question 23

In DV, what is contained in table

Answer 23

each router maintains:
row for each possible destination
column for each directly-attached neighor to node
entry in row Y and column Z of node X
best known distance from X to Y via Z as next hop

Question 24

Describe DV Routing

Answer 24

Question 25

pseudo code for DV

Answer 25

Question 26

What are some advantages to DV?

Answer 26

“good news travels fast”
fast convergence

Question 27

count to infinity problem

Answer 27

could take a very long time or never converge

this happens when there is “bad news”

Question 28

Which of the following problems does poisoned reverse attempt to solve

Answer 28

when we have routing loops in a cycle of two nodes

Question 29

LS vs. DV

Answer 29

storage:
LS stores all links
DV entry for each possible destination/next-hop

convergence:
LS reacts more quickly in bounded time to connectivity changes
DV count to infinity problem; slower convergence; bounded path length

global policies:
LS able to impose global policies in a globally consistent way
DV harder since do not have complete network topology

Question 30

advantage of LS

Answer 30

impose policies in a globally consistent way