I've to say that do work problems I had to re-read QoS documents and during the research I re-found Wonder Shaper which I used a few years ago for testing purpouses. I decided to give it a try and I even found that there has been not much progress since April 2002 and now it is even debianized with a few patches, so after a few minutes I understanded the setup again and get marveled by the results. There has been many progress in kernel queues to make this happen since last time I gave a try.
There is a quick howto for Ubutu  ¶ 6:54 PM