Look at the error you get, specifically Libdnet.xs:35:18: error: dnet.h: No such file or directory. Looking at the contents of libdumbnet-dev (via "dpkg -L libdumbnet-dev") one can see that it does indeed not include dnet.h, but it _does_ include dumbnet.h. Replacing dnet.h with dumbnet.h in Libdnet.xs, and -ldnet with -ldumbnet in Makefile.PL makes the module successfully compile and pass tests on my machine (Kubuntu Gutsy Gibbon). Incidentally, there is a bug report on rt.cpan.org which shows someone else had the same issue. If these changes fix the compile for you then you could add this to the bug report to help others who may have the same problem