Network Layer Flashcards
Discuss connectionless and connection-oriented routing
Connectionless: Every packet contains the end address and is routed independently. This is done by following the routing tables of different routers the packet passes through. These tables, and thus the best route to the destination, may change over time. (Example: IP).
Connection-oriented: At connection setup, different virtual circuits are calculated. Instead of the end address, each packet carries a circuit identifier. Packets with the same identifier follow the same path through the network. Virtual circuits can be merged. This is called label switching. It’s important to notice that a connectionless model is needed to bring the routing information to each router.
Virtual circuits vs datagrams
Virtual circuits:
- Simple routing without complex lookup
- Small routing tables
- Circuit identifiers are smaller than end addresses
- Resources reserved during connection setup = QoS
Datagrams:
- No set-up phase
- Resilient to router crashes
-
Discuss Dijkstra’s algorithm
Assume we want to make a routing table to go from router A to different routers. At the start, every path is labeled with infinite cost. Then, adjacent routers of A get examined. If the distance to the adjacent router is lower than the previous cost, replace it. The router with the lowest distance is made permanent and its adjacent routers will be examined next. It’s important that you calculate the total distance, starting from the starting router A.
Discuss Bellmann-Ford
Each router measures the distance to each neighbor using ECHO datagrams. Each router periodically exchanges its routing tables with all neighbors. New entries are created based on the received routing tables and the measured delays. The new entry is the minimum value of the measured distance to the neighbor and the distance from that neighbor to the target router.
Discuss count to infinity problem
Bellman-Ford only uses local knowledge to create the ‘optimal’ routing table entries. Good news travels fast, but bad news travels slow. Imagine the network A-B-C-D-E. The distances to A are 0, 1, 2, 3 and 4 respectively. When A goes down, the distance from B to A will become infinite. However, router B sees that its neighbor, router C, can route to A with a cost of 2. Therefore, the new routing distance from B to A will become 3 ( B –> C = 1, C –> A = 2). The problem with this is the lack of global knowledge. B doesn’t know that itself is included in the path from C to A. In the next exchange, C sees that the distance from B to A changed from 1 to 3, so it updates its routing distance to 4 (C –> B = 1, B –> A = 3). In the next exchanges, these distances keep growing to infinity. The count to infinity problem is the biggest issue of distance vector routing.
Discuss link state routing
Link state routing replaces distance vector routing due to the count to infinity problem. Every router sets the distances to its neighbors. This is done by sending a HELLO message to all neighbors. They respond with their address. This information, combined with a sequence number (duplicate detection) and age (out of date data), is put in a packet and is sent to all other routers through flooding. To limit flooding overhead, each packet gets a TTL. Dijkstra’s algorithm is used to calculate the shortest path to every router.
Link state routing solves the count to infinity problem, but the routers need to do much more computations and store more data. Therefore, we need to limit our routing tables by using hierarchical routing.
Discuss hierarchical routing
Hierarchical routing reduces the size of the routing tables. Each router is assigned to a region. The routers within a region know the internal structure. However, they only know the entry point of other regions. The only downside of hierarchical routing is that it can increase the path length, depending on where you start in a certain region and where you want to end up in another region.
Discuss broadcasting methods
Naive broadcasting: Unicast message to every receiver
- Wasteful of bandwidth
- Sender knows all end addresses
Multi-destination broadcasting: Send a message with a list of all destinations
- A lot of work for the routers
- Sender knows all end addresses
Flooding broadcast: Message with TTL and sequence number retransmitted by routers.
– Not the most efficient bandwidth use
Reverse path broadcast: Exploiting the sink tree. Forward packet on all spanning tree lines (= shortest path links).
Discuss broadcasting methods
Naive broadcasting: Unicast message to every receiver
- Wasteful of bandwidth
- Sender knows all end addresses
Multi-destination broadcasting: Send a message with a list of all destinations
- A lot of work for the routers
- Sender knows all end addresses
Flooding broadcast: Message with TTL and sequence number retransmitted by routers.
– Not the most efficient bandwidth use
Reverse path broadcast: Exploiting the sink tree. Forward packet on all spanning tree lines (= shortest path links).
Discuss OSPF
Open Shortest Path First is an interior gateway protocol, used for intra-domain routing within an autonomous system. It uses link state routing to create the routing tables. Load balancing is done using ECMP (Equal Cost Multi Path). Packets are split across paths with equal length.
Discuss BGP
Border Gateway Protocol is an exterior gateway protocol used for inter domain routing between different autonomous systems. Making is connection with another AS is done with IXPs. The AS may pay for transit (third party connections) or peer for free with a neighbor AS. It’s important to notice that the BGP path runs in the reversed direction of the IP packet flow. BGP uses the distance vector protocol on paths instead of routers. To avoid the count to infinity problem, the path contains a sequence of AS on that path. Boundary routers of an AS must know the routes of the other boundary routers. This is done with internal BGP.
What is a problem with mobile hosts? How is this solved?
It’s hard to keep remote clients connected to mobile hosts since they constantly change location. This is solved with triangular routing. A mobile device has one fixed home address. When a mobile device goes to a new location, DHCP acquires a new address (the care-of-address). This new address is reported to the home agent. When a remote host wants to connect to a mobile device, it sends a datagram to the home agent. The agent encapsulates the datagram and tunnels it to the care-of-address. The mobile host then de-encapsulates the datagram and responds to the remote host. From that point on, there is a tunnel between the remote and mobile host until he changes location again.
Discuss Ad-hoc networks and AODV
Ad-hoc networks contain moving routers and hosts. This causes the topology to change constantly. Ad-Hoc On Demand Vector Routing is related to distance vector routing. However, routes are only discovered on-demand. To route a message, a ROUTE_REQUEST message is flooded over the network. This message contains a sequence number and a time to live to control the flooding. When the destination is found, a ROUTE_REPLY message is sent back to the originator. Intermediate nodes add the route to their tables. This method can lead to high broadcast overhead. To reduce overhead, ROUTE_REQUESTs are sent with a TTL=1. If this fails, the TTL is increased. The downside of this method is the long timeouts when it failed to find a route.
What happens when a node fails in AODV?
If a node fails in the network, all routes containing this node need to be flushed from the routing tables, which is done recursively. This sidesteps the count to infinity problem of Distance Vector Routing.
Discuss assured forwarding
All traffic gets a priority and a discard class. There are four priority classes determining which packets get sent first. The three discard classes determine whether other packets neet to be thrown away before yours or not. A classifier and policer give the classes to the packets and enable the DiffServ mark.
