Não, provavelmente não é baseado em DNS ... Máquinas Windows nativamente usam Resolução de nomes NetBIOS para identificar outras máquinas no segmento de rede local. As caixas Linux, assumindo uma distribuição relativamente recente, quase certamente estão executando o samba por padrão, o que permite que elas acessem o sistema de mensagens SMB do Windows, dando-lhes acesso a mensagens NetBIOS e resolução de nomes. Nada disso depende do roteador - você poderia trocá-lo por um hub passivo estúpido e tudo funcionaria bem.