Well,
In my experience it depends on the model of router. I had a 3640 (granted, it’s old) with 128MB that was just fine until a couple of months ago, now it’s not enough. For one BGP table you will have to have at least 256MB in a 36xx router. Our 720xVXR routers currently have 256MB in them as well, but we’ve already ordered upgrades to 1GB with new NPE-G1s…
36xx or 72xx
Old != bad .
All you need is MEMORY = >= 256 Mb.
"Erik Amundson" <Erik.Amundson@oati.net> writes:
In my experience it depends on the model of router.� I had a 3640
(granted, it's old) with 128MB that was just fine until a couple of
months ago, now it's not enough.� For one BGP table you will have to
have at least 256MB in a 36xx router.� Our 720xVXR routers currently
have 256MB in them as well, but we've already ordered upgrades to
1GB with new NPE-G1s...
It helps immensely to be running pre-ST-merge 12.0 code where possible
(some situations in non-trivial networks can be positively affected by
post-merge code, but you're not likely to find 36xx or 720xVXRs in
central locations in such networks). You are not risking your
"coolness points" to still be running 12.0(21)S8. 
---Rob
256M should be considered a minimum. As far back as a year ago it was dicey to run BGP with 128M...you could load the table, but a BGP flap would cause MALLOCFAILs aplenty. If there's a router out there that can hold today's table in 128M, it won't stay that way for long.
How may BGP peers are you planning on homing on this box? If you're looking at more than a handful, I'd even say that 256M may not be enough for long...
-C