Module 4: IP Routing - I Flashcards
flat vs. hierarchical addressing
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
what does network mask define?
which bits are used to describe the network part
Describe addressing for IP addresses.
Classful Addressing vs. Classless
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.
Internet Routing:
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
Intra-domain routing protocols is based on what?
unreliable datagram delivery
How does link state work?
Open shortest-path first (OSPF)
Each network periodically floods immediate reachability information to other routers
Fast convergence, but high communication and computation overhead
How does distance vector work?
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
What is flooding?
Every node broadcasts information to every node
Be careful not to do anything redundant or make cycles!
Why is DV more efficient than link state?
Because we don’t have to flood the network like in LS. Minimal communication.
Even though DV has less communication overhead than LS, what is the downside?
Takes longer to converge, i.e., in proportion to the maximum path length
Might not converge at all (infinite loops)
What is the goal of routing?
determine a “good”path through the network from source to destination
good = the shortest path usually
Describe the network modeled as a graph
routers -> nodes
link -> edges
(edge costs = delays, congestion, etc)
T/F
BGP is an intra domain protocol used to connect one AS to another
False
It is an INTER-domain routing protocol
Describe link state flooding
- 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)
key advantage of link state
fast convergence
When a router receives a LSP, it will forward this packet to all links connected to it.
False
What is the end result of the link state flooding?
Every node has all the topology information
Dijkstra’s algorithm
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
In the Dijkstra algorithm, D(v) always goes down monotonically, which is the cost from a specific node to node v?
True
What is the basic idea of the DV algo?
- 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
DV Routing algo is…
- iterative: continues until no nodes exchange info
- asynchronous: nodes need not exchange info/iterate in lock steps
- distributed: each node communicates only with directly attached neighbors
In DV, what is contained in table
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
Describe DV Routing
pseudo code for DV
What are some advantages to DV?
“good news travels fast”
fast convergence
count to infinity problem
could take a very long time or never converge
this happens when there is “bad news”
Which of the following problems does poisoned reverse attempt to solve
when we have routing loops in a cycle of two nodes
LS vs. DV
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
advantage of LS
impose policies in a globally consistent way
