This paper reports on a study of traffic patterns among Autonomous Systems (ASes), based on traces taken at various points in the Internet. The traces display a highly non-uniform distribution of traffic on flows between pairs of hosts, networks, and ASes, accentuates this non-uniform distribution. In one typical trace, for example, the top 9% of flows between ASes accounts for 86.7% of the pack ets and 90.7% of the bytes transmitted. A highly non-uniform traffic pattern sug gests that routers need to maintain only limited QoS flow state. The paper discusses the implications of this phenomenon on different proposed QoS mechanisms.