QoS egress priority queue and tunnel devices

Hello, world!

My custom-built router runs Linux and uses Shorewall to set up the firewall and routing. Until recently, there was only one outgoing interface (eth1). But now, there are several tunnels using eth1: The 6in4 device provides IPv6 connectivity, and two VPN tunnels (tun0 and tun1) connect to two other sites.

Now, any traffic that travels via, e.g., tun0, also travels via eth1 in the end, since the tunnel is established via the outgoing interface. Or, if the VPN endpoint is reachable via IPv6, the traffic via tun1 goes via 6in4, which in turn transmits via eth1.

That was all nice and dandy until VoIP started in the LAN behind the router, and traffic to the two VPN-connected sites increased. I would like to establish priority queues on the router to, e.g., priorize DNS traffic over HTTP traffic. These priorities should be common for all outgoing packets, regardeless of whether they travel via eth1, 6in4, tun0, or tun1. Is there a way to achieve packet QoS priorities over a set of devices instead of having the queue tied to one device?

That the router is using Shorewall for IPtables/tc is not important here, in fact, I would prefer if anyone could explain a potential setup to me basic tc commends - I'll happily translate them into a Shorewall configuration after gaining insight into the topic. :)

Thanks in advance for any hint!