Provider-declared atoms ----------------------- Some time ago we came up with a technique that allows ASes to delegate atom declaration to their immediate providers. In certain cases this technique will enable providers to group prefixes belonging to different customers into the same atom, thus reducing the number of atoms. (This comes at the expense of additional work carried out by the routing protocol.) We call these 'provider-declared atoms'. Ruomei Gao has performed an analysis that estimates the reduction in the number of declared atoms using this technique. The reduction is significant, about 48%. Background ---------- In our architecture, atoms are defined and declared by the owner ASes. We estimate the number of declared atoms by counting the number of distinct origin link sets. For example: P3 / \ P1 P2 / | \ / | \ / | / \ | \ C1 C2 C3 C4 Px are providers. Cx are customers. Assume for this example that each Cx announces all of its prefixes to all of its providers. Then the origin link sets in the graph are: C1-P1 C2-P1 , C2-P2 C3-P1 , C3-P2 C4-P2 I.e. the estimated number of declared atoms is 4. Note that C2 and C3 announce prefixes to exactly the same set of providers: P1 and P2. As far as reachability is concerned there is no distinction between the prefixes announced by C2 and those announced by C3. Therefore these prefixes may as well have been declared as a single atom instead of two atoms. If the architecture is able to detect cases such as this and merge such prefixes into one atom, we can reduce the number of atoms. Some time ago we came up with a technique that allows atoms to be declared by the immediate provider of an owner AS of a prefix rather than the owner AS itself. The providers collectively group prefixes belonging to their customers into atoms. Prefixes are placed in the same atom if they have been announced to the same set of immediate providers. We call these 'provider-declared atoms'. We believe that we can implement this without requiring the providers to communicate directly with each other. In the example above, P1 would declare atoms containing prefixes from C1, C2 and C3. P2 would declare atoms comtaining prefixes from C2, C3 and C4. In all, the following atoms would be declared: atom contains prefixes from: declared by: 1 C1 P1 2 C2 + C3 P1 and P2 3 C4 P2 The number of atoms declared is now 3 instead of 4. The reduction is the result of merging prefixes that belong to C2 and C3 into a single atom. Note that the example does not show the case that a customer announces different prefixes to different providers; however this case is covered as well. The analysis that Ruomei has performed counts the number of atoms that results if the above technique is applied to prefixes owned by *stub* ASes. We think it is reasonable to assume that stub ASes delegate atom declaration to their providers but that providers will want to declare atoms for their own prefixes. So for example, any prefixes owned by P1 and P2 are declared as atoms by P1 and P2 themselves, not by P3. Difference with CIDR aggregation -------------------------------- Note that provider-declared atoms are not the equivalent of aggregation of a customer's routes into its providers' routes. Here is a more detailed example that illustrates this point: (10.0/16) P_1 P_2 (10.1/16) | \ / | | \ / | | X | | / \ | (10.0.1/24) | / \ | (10.1.1/24) (10.0.3/24) C_1 C_2 (10.1.3/24) P_x are providers and C_x are stub networks and customers of both P_x. Each AS announces the prefixes in the brackets. Below is how the P_x announce their customers' prefixes to their upstreams in each senario: CIDR aggregation: P_1 : (10.0/16, 10.1.1/24, 10.1.3/24) P_2 : (10.1/16, 10.0.1/24, 10.0.3/24) Note that under CIDR aggregation, all traffic will be drawn to one of the providers. Orig-link Atom: P_1 : (A_1, A_2, A_3) P_2 : (A_4, A_5, A_6) A_1 : with orig-link (P_1 - C_1): {10.0.1/24, 10.0.3/24}; A_2 : with orig-link (P_1 - C_2): {10.1.1/24, 10.1.3/24}; A_3 : {10.0/16}; A_4 : with orig-link (P_2 - C_1): {10.0.1/24, 10.0.3/24}; A_5 : with orig-link (P_2 - C_2): {10.1.1/24, 10.1.3/24}; A_6 : {10.1/16}; Prov-declared Atom: P_1 : (A_3, A_7) P_2 : (A_6, A_7) A_7 : with orig-AS C_1 and C_2: {10.0.1/24, 10.0.3/24, 10.1.1/24, 10.1.3/24}; In the "Prov-declared Atom" senario, the prefixes in A_7 can be part of the same atom, since they are identically routed. We are optimising for the fact that many customers multihome to the same providers in the same way. Placing prefixes together in an atom does not make them less specific than they were. That's where 'aggregation' by atoms differs from prefix aggregation. Results ------- The resulting figures are: #ASes #prfxs #org lnk sets #provider-declared atoms Stub AS : 13146 55312 18084 6427 Transit AS: 2567 67347 6346 N/A ----- ------ ----- 15713 122659 24430 (Computed from July 16 2003 12:00 Routeviews data, semi-global prefixes using 19 Routeviews participants out of 36.) The estimate for the number of owner-declared atoms is 24430. Using the technique of delegating atom declaration of stub AS prefixes to immediate providers, 18084 owner-declared atoms are replaced by 6427 provider-declared atoms, giving a total of 6427+6346=12773 atoms. This is a 48% reduction in the number of atoms.