Existem algumas maneiras de fazer isso.
mdns - o que a apple chama de zeroconf é comumente configurado por padrão em muitos linux boxen, suportado no OS X como bonjour e linux como avahi. Ele faz endereços "blah.local".
Se você estiver executando o samba, acredito que nmbd seja executado , permitindo que você execute a resolução de nomes de rede "windows".
Você também pode executar um servidor DNS local. Os nomes de hosts estão em um nível mais alto do que "roteamento", embora eu suponha que você possa / possa executar um servidor DNS no roteador médio do consumidor.