Hola:
Hay personas que te pueden decir algunas cosas más, o cosas menos. Yo
pensaría en iptables, iproute (o iproute2) y ldp-es-garl (apt-get;
página 20 y sucesivas).
No es que quiera echar tierra a Linux, pero si quieres hacerte de un
router, casi todos los lugares que veo recomiendan NetBSD (o FreeBSD,
no recuerdo bien -que actualmente se encuentra en desarrollo un port
de Debian FreeBSD y NetBSD http://www.debian.org/ports/ al final de
la página-), yo estoy pensando en armarme una máquina para probarlo.
Y también tienes Freesco (free cisco).
Si no tienes mucha idea de como empesar, la Guia de Administración de
Redes con Linux es un documento indispensable y obligatorio.