We are installing 2 Norstar VOIP Gateways that will network 2 Norstars and a BCM50. The data network currently uses NAT and they do not have point to point T1's. All voice traffic will be going out over the internet. The IT guy wants to put the VOIP gateways and the BCM50 on public IP's. I know that there is little to no QOS in the internet cloud. Here is the suggestion that I would like to give to the IT guy, he needs to setup a VPN between the sites and make sure that he has QOS setup at each site. What suggestions would you have for me? I appreciate your help.

A VPN is technically unnecessary unless you just want it for security reasons. Although a VPN tunnel would make the SIP/STUN/Nat Traversal issue disappear tho. You will need to see what kind of average latency you get through the nat with VPN. I always like to keep it under 250ms if at all possible but I have seen it "work" with up to 500ms pings. Starts to sound like an overseas call tho.

Plan B is setting up a STUN server on a machine with a public IP or trying to use some of the public-use STUN servers. Everyone has mixed results with this so your mileage may vary. Also going to depend on what kind of SIP support your BCM50 Gateways have. Ahhh the joys of VoIP

It would be nice if they would at least get static IP's. Otherwise they WILL experience outages whenever the IP changes. Services like Verizon FiOS (from what I hear) change IP's every 3-5 hours whether you like it or not. My road-runner (brighthouse) IP has stayed that same for about 3-months now. Regardless, they all eventually change.

NetGear's ProSafe routers have built-in support for various dynamic DNS services like DynDNS.org. This will automatically update a dns record like siteA.bcm50company.com to whatever their current WAN IP is, letting you use a DNS name instead of IP in the gateway config.

Most likely the VPN will not help your QOS issues since the VPN will be going over the internet. The VPN QOS might help if you're pushing a lot of data traffic over the connection. However, it migh make it worse since the VPN will require a certain amount of headroom just for the tunnel.

If the data connection at each site is going to be used for both the office "internet access" AND VOIP traffic then getting a QOS capable router is your best bet of keeping the voice traffic sounding as good as possible given the setup.

Even though you can't control the rest of the Internet, the first place you run into problems is where it leaves the local network. The Internet "cloud" in general has a whole lot more bandwidth than your office's T1 or DSL connection.
With QOS routers at each end, it will help keep "mary joe" from killing your phone conversation when she decides to send 20 mp3's at once to her sister but it won't work magic.

A VPN will help keep the gateway configuration a little more on the simple side but also adds to the bandwidth needed to transport each packet. Another problem with using a VPN is if the VPN router doesn't have enough "horsepower" to encrypt the packets fast enough you will have the latency issues Kumba mentioned.

If it's a good VPN Router the manufacturer will list throughput at different encryption levels. Typically a T1's worth of data throughput isn't an issue but Mary Joe loves her bandwidth.

The reason for the VPN was to have encryption and because they are using NAT. Placing the BCM and the VOIP Gateways on the public network leaves them vulnerable. I understand that there is nothing we can do when the packets go into the internet cloud, but I will suggest to the IT guy to implement QOS at his routers at each site.