Can this be easily parallelized? I'll bet it could.
However this assumes that the state of the traffic shaping system is per connection. If it's per site<>client or just client<>net over a duration then this wouldn't help.
Reminds me a lot of hierarchical token bucket filters and letting clients burst over their normal allocation as long as there was spare bandwidth (then squeezing them when others woke up and wanted to use bandwidth as well).
An ideal N would be high enough where the cost of the TCP handshake and slow-start are minimal, but small enough not to trip the traffic shaper to downgrade the connection from the fast flow to the slower one.