Algorithms for variable length subnet address assignment

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-Is_iI) containing the address of that particular machine within its subnetwork. In fixed-length subnetwork addressing, Is_iI is independent of I, whereas, in variable length subnetwork addressing, Is_iI 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_i. The practical problem is how to find a suitable set of s_is in order to maximize the total number of addressable machines, when the ith subnetwork contains n_i machines. Not all of the n_i machines of a subnetwork i need be addressable in a solution: If n_i >2(L-|s_i|), then only 2(L-|s_j|) machines of that subnetwork are addressable (none is addressable s_i the solution assigns no address s_i to that subnetwork). The abstract problem implied by this formulation is: Given an integer L, and given M (not necessarily distinct) positive integers n₁,…,n_M, find M binary strings s₁,…,s_M (some of which may be empty) such that (1) no nonempty string s_i is prefix of another string s _j, (2) no s_i is more than L bits long, and (3) the quantity Σ(|s_k|≠0) min{n_k,2(L-|s_k |)} is maximized. We generalize the algorithm to the case where each n_i also has a priority p_i 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. The algorithms can be used to solve the case when L itself is a variable; that is, when the input no longer specifies L but, rather, gives a target integer γ for the number of addressable machines, and the goal is to find the smallest L whose corresponding optimal solution results in at least γ addressable machines