You can put a PC on each end of the connection running an application like QCheck (www.netiq.com - free), or you can hit one of the bandwidth test sites like www.broadbandreports.com or www.bandwidth.com.
Using QCheck will give you a bit more control, and will work for "point-to-point" frame-relay circuits (between two locations versus location-to-Internet).
If you couple the Qcheck tests with a detailed bandwidth report from your provider, and / or statistics from the interface of your router, and / or a protocol analyzer, you can evaluate your shaping and policing by looking at FECNs, BECNs, timeouts, re-transmits, etc...
Good Luck
Scott