Debian: Traffic shaping

Ich hab in meinem Router 5 NICs, einmal Internet und vier unterschiedliche Subnetze. Nun sollen diese 5 Subnetze unterschiedlich priorisiert werden.

Der Internetanschluß stellt 4 MBit zur Verfügung, die zB für Subnetz 1 immer verfügbar sein sollen, dh. wenn dieses Subnetz alle Bandbreite braucht, werden die anderen auf ein Minimum zurückgeschraubt, zB 10kB/s oder so.

Problem: Für die ganze Angelegenheit steht eine öffentliche IP zur Verfügung, dh es kommt NAT zum Einsatz.

Für dynamisches Trafficshaping müßte ich doch mit tc die ingress queue (Internet) klassifizieren, aber das geht nicht wirklich, weil dank NAT alle Pakete die gleiche IP haben.

Hat irgendjemand eine Idee, wies trotzdem funktioniert? Ich habs auch mit markieren der Pakete mit iptables versucht, ging auch nicht wirklich... Any ideas?