A Hypercube-based Approach to the Multicast Address Allocation Problem

April 18, 2002
1:30 pm - 2:30 pm
Halligan 111
Host: Dr. A. Blummer


The multicast address allocation problem is one of several key unsolved problems that has delayed the deployment of native IP multicast throughout the Internet. As blocks of multicast addresses are allocated and deallocated to Internet administrative domains, over time the address space becomes fragmented. The result is poor utilization and ultimately failure to fulfill requests for multicast addresses. In this talk, we show that the multicast address allocation problem bears a strong resemblance to the subcube allocation problem in hypercubes. We show how results from subcube allocation -- including its compact notation, complexity results, and algorithms -- can be adapted to the practical exigencies of the "malloc problem." Our preliminary simulations show that several hypercube-based allocation algorithms hold promise for use within the multicast protocol currently proposed by the MASC/BGMP working group. Biographical Sketch: Ginnie Lo received her Ph.D. from the University of Illinois at Urbana-Champaign in 1983. Her research interests are in the areas of scheduling for parallel and distributed computing systems, and in structures for group communication in the Internet. Her work has been supported by grants from the National Science Foundation and Intel Corporation. She has been a faculty member at the University of Oregon since 1985. (Her daughter is currently an undergraduate at Tufts!)