# Preventing a line hang-up: how often must you speak?

Consider the following problem. You have made a connection to a machine to which you want to transfer some data. You know that if you are silent for some finite, but unknown time, then the machine will hang-up on you. To keep the line open, you need to ‘ping’, or speak to, the machine at the other end. How often do you need to speak?

# How can I force my ISP to give me a new IP address?

Phrased that way, the answer is, of course, that you can’t force the ISP. What you can do is to disconnect from your ISP for a duration that exceeds the the DHCP lease time of the IP address. But that begs the original question.

## Analysis

I have not seen any literature related to the problem and I was surprised to learn, from my own analysis, just how time-expensive it is to pinpoint the lease time with any accuracy. I considered the following two, mutually exclusive possibilities: (a) I have a certain (as in sure) upper-bound for the lease-time, or (b) I have no idea of the lease time. If one were only reasonably sure, for example, that the lease-time is a couple of hours but were nonetheless absolutely certain that it could not exceed a year, then the situation would still meet the criterion for Scenario-a. I also make an important assumption that might, in fact, not be strictly true of the DHCP protocol. Specifically, I assume that by reconnecting to your ISP, the timer for the line will be reset so that the amount of lease-time that has expired on reconnection is zero.

### Binary search strategy

The strategy that I examined relating to each of the two possibile scenarios was essentially one of binary search. However, it is a kind of binary search quite unlike those that are normally described for solving problems such as finding an entry in a database. What I used was an approach that seems intuitively obvious although I have no proof of its optimality.

Imagine that you know for certain that the lease time is less than a week. You might then try disconnecting from your ISP for half a week and, if your IP number remains unchanged, try disconnecting for three-quarters of week. If that then proves to be successful in changing the IP address, you might try disconnecting for 5/8 of a week, and so forth. The difference between this strategy and a normal binary search on a random-access machine is that ‘time’ does not have a random-access feature! Even worse, it does not have a rewind feature as a tape drive would. To improve on your upper-bound for the lease time of three-quarters of a week, you cannot simply rewind by 1/8 of a week to test the effectiveness of a 5/8-week disconnection. Instead you have to restart from time zero.

## Experiments

For any given lease time that is less than the lease-time’s upper-bound, there is a specific total time—the discovery time— that it will take you to discover that that time is indeed the lease time. For example, assume that you know that 1024 time-units provides an upper bound on the lease time; that is, you know that the actual lease time is strictly less than 1024 time-units. Imagine also that the actual (but unknown) lease time is 73 time-units; in other words, 73 is the number that you are wanting to discover. The discovery process would proceed as an iteration of: (a) connection, (b) waiting, (c) checking whether a new IP number has been assigned, (d) increasing or decreasing the waiting time appropriately, and (e) disconnection. The waiting time (discovery) sequence would be: 512 units (half the upper bound), 256, 128, 64, 64 + 32 = 96, 64 + 16 = 80, 64 + 8 = 72, 64 + 8 + 4 = 76, 64 + 8 + 2 = 73, 64 + 8 + 1 = 73. The total time spent on the discovery process would then be 1431 time units … far greater than I would have guessed prior to doing the analysis.

I determined what the total discovery time would be for each (integer) lease time between 1 time-unit and 1023 time-units on the assumption that (Scenario 1) I knew that 1024 was an upper bound for the lease time, or (Scenario 2) I had no information regarding an upper bound.

The red line in the graph above shows the relationship between lease-time and discovery-time for Scenario 1. There are several things to note. First, the discovery time increases monotonically, though not strictly monotonically, with lease-time. For example, it takes as long (1577 time units) to pin-point a lease-time of 103 units as a lease-time of 104 units. Second, one can see that the red line does not intersect the origin, indicating that there is some fixed (time) cost for the discovery process, even if the lease-time proves to be very short. In fact, using the strategy that I’ve described it will cost 1023 time units to discover that the lease time is 1 time unit when the only available prior information is that the lease-time upper bound is 1024 and, in general, costs 2n–1 time-units to discover that the lease time is of duration 1 when the only known upper bound is 2n.

The violet line in the graph above shows the relationship between lease-time and discovery-time when there the upper-bound on the lease-time is unknown. The strategy that is assumed here is to begin with a disconnection of 1 time-unit and if that is unsuccessful in producing a change in IP address, disconnecting for 2 time-units, and then 4 time-units, and so forth, until a new IP address is obtained. Once that has been achieved, one has succeeded in obtaining a previously unknown upper-bound on the lease-time and one proceeds with a binary search following the strategy described for the scenario where the upper bound is known. As one can see from the graph, the times are short at the low end, but grow fast. In fact, the time-complexity for the case where there is no known upper-bound is O(n log n), as shown by the plot of the function n log2n (blue curve).

## Keywords

DHCP, lease time, binary search, IP address

Mark R. Diamond