iptables com tc ? Então, novamente, eu acho que lembro do pfSense (sim, não é o Ubuntu: /), usado para modelagem de tráfego, entre seus muitos papéis, em um pequeno escritório em que eu costumava trabalhar. Como estávamos em uma LAN, tudo passa pelo pfSense. Cada usuário é considerado como 1 IP.
Que tipo de configuração você tem, thin clients conectados a um servidor?