(Hopefully correct) solved exercises

Exercises from Walid's PDF

(Sorry for the bad translation, my French is not that great :))

Question 1: efficiency of classful addressing

Sub-question 1

Calculate the maximum theoretical number of addressable objects with IPv4.

If we don't take into account the different subnetworks reserved for special purposes, the address space has $2^{32} = 4294967296$ valid IP addresses.

If we take them into account:

RFC1700 0.0.0.0/8
RFC1918 10.0.0.0/8
RFC1700 127.0.0.0/8
RFC3330 169.254.0.0/16
RFC1918 172.16.0.0/12
RFC? 192.0.2.0/24
RFC1918 192.168.0.0/16
RFC3171 - Multicast 224.0.0.0/4
RFC1700 - Reserved 240.0.0.0/4

We then have to substract:

(1)
\begin{equation} 2^{32} - 2^{32-8} + 2^{32-8} + 2^{32-8} + 2^{32-16} + 2^{32-12} + 2^{32-24} + 2^{32-16} + 2^{32-4} + 2^{32-4} = 4294967296 - 85065984 = 4209901312 \end{equation}

Sub-question 2

Considering the mechanism for classful addressing with the A, B, and C classes, as well as the D class (multicast) that correspond to the addresses beginning with 1110. The addresses that start with 1111 are reserved and cannot be assigned. What is the number of addresses that can be assigned in each class?

Class Prefix Addresses per network Total addresses
A 0 224 231
B 10 216 230
C 110 28 229
D 1110 N/A 228

It is customary to substract two addreses per network for the "network" and "broadcast" addresses, but as far as I understand there's no requirement for that in the RFCs, nor the routers interpret them specially outside of the concerned network.

Sub-question 3

. Be Nt the total number of addresses that can be assigned with a classful addressing. Calculate the efficiency H of the allocation procedure (defined in RFC 1715) as $H = \frac { \log_{10} (N_t) } {32}$.

If the total number of addresses assignable is $2^{31} + 2^{30} + 2^{29} = 3758096384$ (Excluding the multicast class D, and the reserved class E), the value for H would be $\frac {log_{10}(3758096384)} {32} \approx \frac {9.57} {32} \approx 0.299$, which according to the RFC is a overly efficient number. It is not clear if this ratio calculation is of any parctical value.

Question 2: CIDR addressing

A router has the following CIDR entries in its routing table:

Address/mask Nexthop
208.12.16.0/20 Routeur 2
208.12.21.0/24 Routeur 3
208.12.16.0/24 Routeur 4
192.53.40.0/23 Routeur 3
135.46.56.0/22 Routeur 4
135.46.60.0/22 Routeur 3
default Routeur 2
  • What do the first three entries mean?
  • For each of the following IP addresses, what will the router do when receiving a datagram with that IP as destination? Why?
    • 135.46.63.10, 135.46.57.14, 135.46.52.2, 192.53.40.7, 192.53.56.7, 208.12.16.0, 208.12.21.0, 208.12.31.0, 208.12.44.0.

The first three entries show the use of CIDR to allow asymmetric subnetting:

208.12.16.0 = 11010000 00001100 00010000 00000000
mask (/20)  = 11111111 11111111 11110000 00000000

208.12.21.0 = 11010000 00001100 00011001 00000000
mask (/24)  = 11111111 11111111 11111111 00000000

208.12.16.0 = 11010000 00001100 00010000 00000000
mask (/24)  = 11111111 11111111 11111111 00000000

Using the rule of the longest matching prefix, packets targetted to the networks 208.12.21.0/24 and 208.12.16.0/24 will go the routers 3 and 4, respectively. And any other package targeted to 208.12.16.0/20, which doesn't match the former prefixes (i.e. networks 208.12.{17-20,22-31}.0/24), will be targeted to router 2.

  • 135.46.63.10: matches rule #6, netxhop: R3.
  • 135.46.57.14: matches rule #5, netxhop: R4.
  • 135.46.52.2: matches (default) rule #7, netxhop: R2.
  • 192.53.40.7: matches rule #4, netxhop: R3.
  • 192.53.56.7: matches (default) rule #7, netxhop: R2.
  • 208.12.16.0: matches rule #3, netxhop: R4.
  • 208.12.21.0: matches rule #2, netxhop: R3.
  • 208.12.31.0: matches rule #1, netxhop: R2.
  • 208.12.44.0: matches (default) rule #7, netxhop: R2.

Question 3: Distance vector routing

Let's consider the network in Figure 1 (V = {A, B, C, D, E, F}, E = {(A, B), (B, C), (C, D), (B, D), (D, F), (F, E), (E, C)} using a DV routing protocol.
All the links among the routers have lenght 1, except DF and EF, that have lenght 2. A announces systematically a 0 distance to its network 1.2.8/21 (indicating in this way that the prefix is reachable by A). The same happens for E and F, announcing 0 distance to 1.2.4/22 and 1.2.6/23, respectively. (An IP address will be always found in the subnetwork with the longest matching prefix). Note: I believe that this would not work on real networks, since usually local information prevails over anything learnt from the network.

In case of having multple paths to choose, we will suppose that a router will always choose the first neighbour (in alphabetic order) that offers the shortest path (choosing B to C, for example).

Sub-question a

What will be the routes followed by these IP packets:

  1. from 1.2.8.1 to 1.2.6.1,
  2. from 1.2.4.2 to 1.2.12.2,
  3. from 1.2.15.15 to 1.2.5.15,
  4. from 1.2.7.7 to 1.2.8.8 ?

Assuming that the network is already stable:

  1. ABDF
  2. ECA
  3. ACE
  4. FDBA

Sub-question b

What is the maximum distance that we could observe in the network (with possible failures)? What value would you advocate for infinity?

If BC and any of the other cost 1 links goes down, there will be distances of up to 7 (between the nodes that share the broken link). Therefore, 8 is a good value for infinity.

Sub-question c

We suppose that the routers will transmit their distance vectors during the same period T in the cyclic order A, B, C, D, E, F: A transmits its distance vector to its neighbours, then B, then C… We suppose also that the routing table is not recalculated until the moment to announce the distance vector.

Trace in a table the evolution of the distances for 1.2.4/22 on each router if the CE link breaks. After how many periods the network is stabilised? On which links a traffic from 1.2.8.1 to 1.2.4.1 with a TTL value of 255 will impact the most?

T A B C D E F Notes
0 2, C 2, C 1, E 3, B 0, E 2, E Just before the break
1 2, C 2, C 3, A 2, B 0, E 2, E C decides to route through A (start of routing loop)
2 3, B 4, A 4, A 4, F 0, E 2, E A changes, B & C decide that A is better, D founds the correct way
3 5, B 5, C 6, A 4, F 0, E 2, E Continues the loop, B switches to C
4 6, B 5, D 6, B 4, F 0, E 2, E The loop is fixed: B goes to D, A already switched to B by chance, C goes to B too
5 6, B 5, D 6, B 4, F 0, E 2, E Final state

The network is stabilised in 4 periods. The impact on the traffic will be different at each step:

  • Period 1, C switches: packets loop in AC.
  • Period 2, A switches to B: packets loop in AB-BC-CA.
  • Period 2, B switches to A: loop in AB.
  • Period 2, C switches to A: no change
  • Period 3, B switches to C: loop in AB-BC-CA.
  • Period 4, B switches to D: packets flow normally again.

Sub-question d

Show in a table the evolution of distances to 1.2.4/22 if the protocol uses the "split horizon" mechanism (which consist in hiding certain entries of the distance vector to each neighbour). What advantage does this technique provide here?

T A B C D E F Notes
0 2, C 2, C 1, E 3, B 0, E 2, E Just before the break.
1 2, C 2, C ∞ 3, B 0, E 2, E C doesn't see the routes from A and B that would loop, therefore cannot route to E.
2 3,B ∞ 4, A 4, E 0, E 2, E A switches to B, B cannot route (D is not publishing), D finds the route.
3 ∞ 5, D 6, B 4, E 0, E 2, E A cannot route, B founds the route, and C inmediately finds it too.
4 6, B 5, D 6, B 4, E 0, E 2, E A finds the route and the loop is ended
5 6, B 5, D 6, B 4, F 0, E 2, E Final state

Here the routers decide that the route is lost quite fast, even the convergence time is the same as before, if it weren't for the redundant link through BDFE, they would have needed much more time to decide the route is down. Also, in this case, there are no routing loops at all in the path from A to E (like in question c) during the convergence.

Question 4: Intra and inter-domain routing

Some AS indentified by the numbers 1, 2, 3, and 4 are connected between them by links inter-network to form the network of networks shown. The AS 1 handles all the addresses 1.*.*.*, AS 2 handles 2.0.*.*, AS 3 handles 3.*.*.*, and AS 4, 4.0.*.*. The AS 1 has only one router, A. AS 2 has routers B and C, AS 3 has D, E, and F; and AS 4 has G and H. Each router has one IP address per interface. B interfaces, for example, have the addresses 2.0.0.1, 2.0.0.2, and 2.0.0.3. Also, A serves as gateway to its sub-network 1.1.*.* (linked by ethernet), which is liked by 1.1.0.1. In the same fashin, F is the gateway for the 3.1.*.* sub-network, linked by 3.1.0.1.

We suppose that the protocols used inside an AS are link-state type protocols, like OSPF. Between them, a path-vector protocol is used, like BGP. (A path will be composed by a sequence of AS numbers to traverse in order to reach a given prefix.)

To verify the network, it's possible to send PING packets with ant TTL value. The target of a PING answers with a PONG packet. If a router receives a packet with 0 TTL, it answers with an ICMP error packet sourced with the address of the sending interface.

A traceroute consists in sending PINGs to a destination with TTL values 0, 1, 2,.. until the reception of a PONG. The list of intermediate router addresses that answer is then established.

  1. What would be the addresses listed by a traceroute from 1.1.1.1 to 3.1.3.3?
  2. For each node on the path from 1.1.1.1 to 3.1.3.3, indicate the routing table entry that allows to choose the next hop of the path. Indicate also the mechanisms that had inserted the relevant entry in the routing table (in particular, the routing protocol that did it).
  3. What would be the addresses listed by a traceroute from 1.1.1.1 to 3.1.3.3 after the link between C and D goes down (and after the routing protocols converge)?
  4. Let's suppose that the CD link is re-established, but C hasn't informed B of this even thought D informed E and F. What would be the addresses listed by a traceroute from 1.1.1.1 to 3.1.3.3?
  5. Explain how the counting to infinity problem will be avoided if the CD link and then the EH link break?
  1. First traceroute:
    1. 1.1.0.1
    2. 2.0.0.1
    3. 2.0.0.4
    4. 3.0.0.1
    5. 3.0.0.5
    6. 3.1.3.3
  2. As follows:
    1. @A: 3/8 via 2.0.0.1 (BGP)
    2. @B: 3/8 via 2.0.0.4 (OSPF, but it should be iBGP)
    3. @C: 3/8 via 2.0.0.1 (BGP)
    4. @D: 3/8 via 3.0.0.5 (OSFP)
    5. @F: 3.1/16 via local interface (static info)
  3. Second traceroute:
    1. 1.1.0.1
    2. 2.0.0.1
    3. 4.0.0.4
    4. 4.0.0.2
    5. 3.0.0.4
    6. 3.0.0.6
    7. 3.1.3.3
  4. The forward routes will be the same, but not the reverse routes (they will be like in the original case), so the routers will reply with different source addresses:
    1. 1.1.0.1
    2. 2.0.0.1
    3. 4.0.0.4
    4. 4.0.0.2
    5. 3.0.0.7 (E via D)
    6. 3.0.0.5 (F via D)
    7. 3.1.3.3
  5. In the case of BGP, the link path shows which ASs are to be traversed, so no host will accept a route that loops back to itself, avoiding entirely the problem. OSPF is not hanling the intra-AS routes, so it's not concerned with this problem

Question 5: distance vector routing problems

Sub-question a

Distance vector of D:

to A to B to C to D
Beginning ∞ 1 4 0
Msg from C 8 1 4 0
Msg from B 2 1 2 0

Sub-question b

Distance vector sent by D:

to A to B to C to D
sent to B ∞ ∞ ∞ 0
sent to C 2 2 2 0

Sub-question c

The path vectors for D are:

  • To A: DBA
  • To B: DB
  • To C: DBC
  • To D: D

If BA falls, B sees that in the vector announced by D includes B itself, so ignores it and sets A as unreachable. When C learns that it cannot use B anymore to reach A, it will start to route directly through AC, and publish the path vector CA to B, which will in turn start using C to route to A.

Sub-question d

Reading the answers, it is evident that there was a typo.

1.

Host Dest Via Metric
A B C 5
A C C 4
A D C 6
B A C 5
B C C 1
B D D 1
C A A 4
C B B 1
C D B 2
D A B 6
D B B 1
D C B 2

2. Infinite
3. 6, as it is stiil routing through B.
4. to D, as it publishes a route to A.
5. 10, using D.
6. 11, using C.
7. 15.
8. When it reachs infinity (usually 16).

Question 6: BGP

  1. AS-PATHs:
    • AS6192: AS6192
    • AS11423: AS11423, AS6192
    • AS3357: AS3357, AS11423, AS6192
    • AS209: AS209, AS11423, AS6192
    • AS11537: AS11537, AS11423, AS6192
    • AS81: AS81, AS11537, AS11423, AS6192
    • AS513: AS513, AS11537, AS11423, AS6192 and AS513, AS3357, AS11423, AS6192. It will prefer the one with lower IP address.
  2. It will be considered as better route to p. It will also announce it, but the problem are the announces from 11357, that will undoubtedly accecpt the hijack.
  3. It will be preferred because it has a longer prefix.
  4. Because most published prefixes are longer than /24, therefore making this new announcement the preferred path. I'd suggest filtering from neighbours: one way is to prevent the AS for announcing too many new routes in a short period, and other is the one used in reality: registry directories that know who owns what.

Exercises from Chadi's PDF

Problem 1: Do not neglect the mobility

21 GB is equivalent to 168 Gbits = 168 x 230 (assuming powers of two multipliers). 18 km/h is equivalent to 5 m/s. So, the courier will be able to transfer its whole datagram in $t(d) = \frac d {5 m/s}$, giving a transfer rate $T(d) = \frac {168 \times 2^{30} b \times 5 m} {d s}$. We can find the turning point d just by equating with the link's transfer rate:

(2)
\begin{eqnarray} T(d) &=& 150 \times 2^{20} b/s \\ \frac {168 \times 2^{30} b \times 5 m} {d s} &=& \frac {150 \times 2^{20} b} s \\ d &=& \frac {168 \times 2^{30} \times 5 m} {150 \times 2^{20}} \\ d &=& \frac {168} {150} 2^{10} \times 5m \\ d &=& 5734.4m \\ \end{eqnarray}

Since T(d) shrinks as (the positive) d grows, we can conclude that the guy with the tape is more efficient in the range (0, 5.7344km).

Problem 2: Impact of handover on the download rate

Let's suppose w.l.o.g. that we put the circle in the cartesian coordinates (0, 0) and the pedestrian walks in a line paralel to the X axis. For simpliticy, I assume that the probability is uniform on the value of the y that the pedestrian is walking over. Since I don't know how to calculate this with proper probabilistics, I'll use the intuition that says that it's the area of the circle (the integral of all the values of d(y), divided by the diameter (the possible values of y) :-)

Then, the expected value would be $\frac {\pi r^2} {2r} = \frac {\pi r} 2 \simeq 157m$. The speed of the person is $6 Km/h = \frac 5 3 m/s$. Therefore, the average time in the network is $\frac 3 5 \frac {157m} {m/s} \simeq 94.25s$

page revision: 15, last edited: 20 Nov 2009 05:10
Edit Tags History Files Print Site tools + Options
Unclear, need to ask the teachers, since most is obviously derived works.