Question

IPv4 packet header has a bit field called DF. The semantics of this bit is “Don’t frangment”, as such, when a router sees a IPv4 packet whose DF bit is set and the packet is bigger than MTU, it will discard the packet and returns an ICMP Destination Unreachable messages with a code meaning “fragmentation needed and DF set”. (a) Relying on only this mechanism, devise an algorithm for a host that sends a sequence of IPv4 packets with varying length to discover the path MTU. (b) Argue that the algorithm is efficient (or whether it is efficient) (Hint: using Big-O notation on packets sent by the host)

Answer 1

The problem of finding path MTU is similar to finding a number in sorted list with only difference that the length of the list or the highest number in it is not known to us.
Had that be known we can simply apply binary search algorithm picking up half of the size and give a try, to ultimately reach the number which is allowed and one more byte from that is not allowed thus giving path MTU.

Lets say the maximum packet size is known. M.

subroutine findMTU(1, M+1) // we assume 1 size will go thorough and M+1 won't

{

while (start < end)
{

S = integer of [(start + end)/2]

result = attempt sending packet with size S

If the result == Destination not reachable

end = S - 1
result = Start

else // the destination is reachable

result = start
start = S + 1

endif

}

return MTU = result

}

being based on the binary search the the complexity is O(lgN) (log is base 2) which is by far the best for this scenario.

But the problem can arise if the biggest possible packet size is not known a priori
Here we first need to find the range of value between which the MTU lies, and then we can use above mentioned binary search like algorithm to figure out the MTU.

i.e. if we can find efficiently the rangle 500 to 1000 for the the range in which the MTU value lies, we can run binary algorithm on it and find the MTU in O(lgN) which is by far the best.

To find the range insted of breaking the list into equal half, we start from 1 or other logical value and enlarge the list by double every cycle.

find_range_for_MTU(start) // assumption MTU will be greater that start.

{

next = start * 2

result = send_packet_of_size(next);

while (result != destination_not_reachable)
{
start = next

next = start * 2

result = send_packet_of_size(next);

}

return range(start, next);

}

This algorithm doesnot work on divide and conqur but opposite, i.e merge and build. But since in every cycle the list grows double the original size. We will reach the range in O(lgN) time.

So combining this two algorithm i.e. first to find the range in which MTU lies and then running binary search kind of algorithm to find exact MTU in that range again with complexity O(lgR)

We have the complexity. O(lgN) + O(lg(N/2)) ~ 2O(lgN) i.e. O(lgN)

This would be the most effective approach.