I tried switching my outbound traffic to the customers in question over to he.net (with a static route, which I know is the dumb way to do it.) with no improvement.
Hm. I need to learn more about bgp, specifically tags and communities, can you recommend me a book?
Also, you probably want to pick some community to affix to all routes you learn from your customers / originate yourself, and to make sure isn't affixed to routes you learn from your upstreams, so that you can then have a route map check for the presence or absence of that community when deciding which routes get passed along to your upstreams. (BGP doesn't directly solve the problem that an AS doesn't carry traffic unless the source and/or destination is ultimately a customer of that AS, it just provides mechanisms that can be used to make that happen.)
You may want to define communities to let your customers selectively decide to suppress announcements to each of your upstreams, and you may want to pass through the communties recognized by your upstreams in their official documentation if your customers send those communities to you, if you want to let your customers control their advertisements in that fashion. (The only reason I can think of you wouldn't want to let your customers do this is if it would let them move traffic from a link that's cheap for you to a link that's expensive for you.)
Also, playing with looking glasses can be helpful in understanding what's going on with BGP from the perspective of other networks. http://www.bgp4.net/wiki/doku.php?id=tools:ipv4_looking_glas... has a list, which doesn't seem to include AT&T. Going to http://www.nordu.net/connectivity/looking-glass/lg.cgi and selecting bgp and entering prgmr.com's IPv4 address isn't very exciting, in that it only lists one ASN in the path (it seems they have direct peering with Hurricane Electric, who is announcing the block that includes that IP address under their ASN). Putting in an IP address advertised under your ASN at the looking glass of a network that peers with both Hurricane Electric and Cogent might be more interesting if you manage to see routes via both.
I ended up learning most of what I know about BGP not via a book, which makes that hard.
But basically, back in the days of 16 bit ASNs, communities were just 32 bit values that were attached to routes being advertised by BGP, usually expressed as the two 16 bit halves separated by a colon, generally with the ASN that defines the meaning of the community being on the left of the colon, and that ASN defining arbitrary values on the right side of the colon for flags that they want to recognize.
Then, there are route maps or whatever the router vendor wants to call them that use the data from the communities.
Typically when the router is deciding what route to use, it looks for the route with the highest localpref, and if there's a tie, then it looks at how many ASNs are listed in the path, and if there's still a tie, then the router may use MED. http://www.cisco.com/en/US/tech/tk365/technologies_tech_note... explains how this works in the Cisco BGP implementation with all of the additional factors that are considered; Linux and Juniper BGP implementations may consider a slightly different set of factors.
IIRC, Level 3 generally sets localpref to 86 on routes heard on non-customer peer sessions, and 100 on routes heard on customer BGP sessions, but if customers want localpref to be 90 or 80 or 70 instead, they can send community 3356:90 or 3356:80 or 3356:70. If you had two links to Level 3 and wanted to use one as backup only, you could send community 3356:90 on your routes on your backup link, and potentially no communities on your primary link. If you had a really slow link to Level 3 that was backup only and some other ASN was your primary, then you'd want to send Level 3 3356:80 or 3356:70. I doubt you have any desire to set your upstream's localpref values in your configuration, but this may shed some light on why they offer it to their other customers. Also, if you ever have customers speaking BGP who want to use you as backup only, you need to offer some way for routes they advertise to you to have localpref less than what you set on routes you learn from your upstreams; typically this seems to be done by letting your customers send you a community so the customer controls this, but you could just have a special route-map for customers who are backup only that would just set all of their routes to low localpref regardless of the BGP communities, and just apply the right route-map to those BGP sessions.
http://www.onesc.net/communities/as3356/ mentions that Level 3 supports 65004:[ASN] for four prepends when advertising to ASN. If you were a Level 3 customer, and traffic coming to you via one of their peering links was overloaded, sending a community of that form would be a good way to discourage traffic from taking that link by making the path have a large number of ASNs and thus look undesirable. I say this mostly to illustrate the sort of thing that it looks like you might find useful for Cogent to support, though it appears that Cogent doesn't support that.
It's likely that Hurricane Electric and Cogent will recognize some communities that you could send them that will influence their routing, but as far as I know, their peers won't necessarily end up accepting any communities from you, so the key is to either find documentation on the web of what communties Hurricane Electric and Cogent recognize, or ask them for it.
You can also sometimes get geographic data about which major city is closest to a network block by recieving community data from an upstrem, but it's not obvious to me why you'd want that. It may sometimes be used when hot potato routing is not desired, or when a CDN is trying to identify which geographically close server to use.
Hm. I need to learn more about bgp, specifically tags and communities, can you recommend me a book?