Abstract
In a computer network that consists of $M$ subnetworks, the $L$-bit address of a machine consists of two parts: A prefix $s_i$ that contains the address of the subnetwork to which the machine belongs, and a suffix (of length $L-|s_i|$) containing the address of that particular machine within its subnetwork.
In fixed-length subnetwork addressing, $|s_i |$ is independent of $i$, whereas in variable-length subnetwork addressing, $|s_i|$ varies from one subnetwork to another. To avoid ambiguity when decoding addresses, there is a requirement that no $s_i$ be a prefix of another $s_j$.
An interesting practical problem is how to find a suitable set of $s_i$'s in order to maximise the total number of addressable machines, when the $i$th subnetwork contains $n_i$ machines. A solution might leave some subnetworks completely unsatisfied and the rest of the subnetworks completely satisfied;
The abstract problem implied by this formulation is:
Given an integer $L$, and given $M$ (not necessarily distinct) positive integers $n_1 , \cdots , n_M$, find $M$ binary strings $s_1 , \cdots , s_M$ (some of which may be empty) such that (i) no nonempty string $s_i$ is a prefix of another string $s_j$,
(ii) no $s_i$ is more than $L$ bits long
(iii) the quantity $\sum_{|s_i | \neq 0} $ is maximised and
(iv) Every nonempty prefix completely satisfies the corresponding subnetwork - \emph{i.e.,} $|s_i| \neq 0 \Longrightarrow 2^{L-|s_i|} \geq n_i, 1 \leq i \leq M$.
We present a polynomial time algorithm for solving the aforementioned abstract problem.
We also provide an algorithm to solve the case where each $n_i$ has a priority associated with it and there is an additional constraint involving priorities:
Some subnetworks are then more important than others and are treated preferentially when assigning addresses.
We also make observations about the case where there is a hierarchy of subnetworks present.
