ALGORITHMS FOR VARIABLE-LENGTH SUBNET ADDRESS ASSIGNMENT

In a computer network that consists of FA subnetworks, the L-bit addre ss 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 machi ne within its subnetwork. In fixed-length subnetwork addressing, \s(i) \ is independent of i, whereas, in variable-length subnetwork addressi ng, \s(i)\ varies from one subnetwork to another. To avoid ambiguity w hen decoding addresses, there is a requirement that no s(i) be a prefi x of another s(i). The practical problem is how to find a suitable set of s(i)s in order to maximize the total number of addressable machine s, when the i th subnetwork contains n(i) machines. Not all of the n(i ) machines of a subnetwork i need be addressable in a solution: If n(1 ) > 2(L-\si\), then only 2(L-\si\) machines of that subnetwork are add ressable (none is addressable ii 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) positiv e integers n(1), ..., n(M), find M binary strings s(1), ..., s(M) (som e of which may be empty) such that 1) no nonempty string s(i) is prefi x of another string s(j), 2) no s(i) is more than L bits long, and 3) the quantity Sigma(\sk\not equal 0) min{n(k),2(L-\sk\)} is maximized. We general re the algorithm to the case where each n(1) also has a pri ority p(i) associated with it and there is an additional constraint in volving priorities: Some subnetworks are then more important than othe rs and are treated preferentially when assigning addresses. The algori thms can be used to solve the case when L itself is a variable; that i s, when the input no longer specifies L but, rather, gives a target in teger gamma for the number of addressable machines, and the goal is to find the smallest L whose corresponding optimal solution results in a t least gamma addressable machines.