This text attempts to resolve a number of outstanding issues for the first version of the atomised router. For each issue, the alternatives are listed, discussed, and marked as follows: -> proposed for v1 V2 proposed for some subsequent version VZ proposed for some version further in the future MM should implement so that we can measure the effect of the chosen alternative Terminology ------------ o Atomised region (aka scope). Region of the Internet where atomised routing is in effect. o (Non-)atomised router. BGP router with(out) atoms extensions. o Tagged packet. Packet that has been forwarded by an atomised router at some point and has been tagged with an atom ID. Any other packet is an 'untagged packet'. o Contents of an atom. The prefixes that are in an atom. o Routing of an atom. How an atom as a whole is routed. Issues ------ ISSUE-A: Assigning prefixes to atoms ------------------------------------ Alternatives: VZ 1. Compute. -> 2. Declare, e.g. at or near the origin AS(es) of prefixes. This issue has been discussed extensively. ISSUE-B: Where to declare atoms ------------------------------- Alternatives: -> 1. An atom is declared by one (administrive) entity (at or near the origin AS(es)). Other routers are not allowed to modify (e.g. split, aggregate) the atom and can only apply the same policy to all prefixes in an atom. VZ 2. An atom is declared by an entity but its policy may be subsequently modified, or the atom may be split or aggregated with other atoms by other routers. 1 is simpler, but 2 allows a closer approximation of existing policies. ISSUE-C: Absorbing instability of prefixes ------------------------------------------ We can think of several causes for BGP routing updates to prefixes: administrative changes (e.g. customers changing their connectivity to providers), reachability changes (broken/repaired links), IGP-originated updates (IGP attributes such as metrics being introduced into BGP, perhaps automatically?), BGP-originated instability (originating from the BGP protocol itself). Depending on how atoms are declared, we may be able to absorb reachability and IGP-originated updates to prefixes. QQ Would like comment on the above causes for BGP routing updates. Are there other causes of instability? How relevant are each of these causes? To what extent does IGP affect BGP, and are such changes manual or automatical? Alternatives: MM 1. Propagate instability of individual prefixes (as updates to the contents of atoms). -> 2. Declare atoms administratively and absorb (ignore) instability of individual prefixes in the atom. One concern is that providers might object to carrying traffic for unreachable destinations. Although study has shown ('BGP Routing Stability of Popular Destinations' by Rexford et. al.) that little traffic is destined for unstable prefixes. ISSUE-D: Whether to do atomised forwarding ------------------------------------------ Alternatives: V2/MM 1. Apply atoms to routing *and* forwarding (as per the original proposal). -> 2. Apply atoms only to routing. At this point it is uncertain whether applying atoms during forwarding (as described under ISSUE-E) will be effective or might even be too expensive (see IETF notes). We should consider the option of applying atoms to routing alone. Notes: * Applying atoms during forwarding allows smaller forwarding tables in a number of routers. Note that only a subset of routers can carry a smaller forwarding table, namely those routers that do not need to accept untagged packets for forwarding. * Applying atoms during forwarding requires processing which may or may not be expensive. It depends on whether this processing can be in the fast path (now or in theory). ISSUE-E: How to do atomised forwarding -------------------------------------- Assuming ISSUE-D-1, atomised forwarding is performed by tunneling packets across the atomised region. As the packet enters the tunnel it is tagged; it is then forwarded through the tunnel based on the tag; as it leaves the tunnel the tag is removed. There are several ways to implement this: -> 1. An atom ID is represented as an IPv4 address, and this is used as the tag. A packet is tagged by encapsulating it in another IP packet (IP over IP). The outer IP header has the atom ID as its destination. Forwarding a tagged packet is precisely the same as forwarding a regular IP packet, since the tagged packet looks like a regular IP packet. Untagging the packet consists of removing the encapsulation. VZ 2. Use MPLS. An atom ID is represented as an MPLS label. (Actually: different labels in different LSRs.) Tagging a packet means labeling a packet. Forwarding is label switching. Untagging is when the label finally gets removed. This option is mostly ignored in the remainder of the text. 3. The atom ID representation is independent of forwarding. A tag (IPv4 address or MPLS label) is *derived* from the atom ID, rather than being identical to the atom ID. Other than that, forwarding proceeds as under Options 1 or 2. This option is mostly ignored in the remainder of the text. Notes: o The tagged packets described above can be forwarded by non-atomised routers, as long as their forwarding tables have entries for the tags (see also ISSUE-F). QQ o MPLS is existing technology, and is presumably optimised. Is label swapping in the fast path? QQ o How many routers are/will be MPLS-enabled? QQ o To what extent is MPLS used between multiple providers? Do LSPs span multiple providers? o MPLS does label swapping at each hop, whereas option 1. requires only two modifications to a packet along the forwarding path: tagging and untagging. However, each atomised router through which the packet passes may need to ascertain whether the packet has already been tagged or not. ISSUE-F: Whether to allow non-atomised routers within the atomised region ------------------------------------------------------------------------- Alternatives: MM 1. Yes, but non-atomised routers can only forward tagged packets. -> 2. Yes, and non-atomised routers must be able to forward tagged and untagged packets. 3. Yes, some non-atomised routers need only forward tagged packets; others must forward tagged and untagged packets. MM 4. No. Notes: o 2 is the easiest to deploy, and allows the atomised region to be greater. Depending on the number / density of deployed atomised routers, we could switch to 1 or 4 at some point. o A router that forwards untagged packets needs a forwarding table containing all prefixes, and updates containing these prefixes must be sent to such routers. A router that only forwards tagged packets needs a forwarding table containing just atom ID destinations. Updates sent to such a router do not need to carry all prefixes. Option 3 is probably not feasible, since it requires some non-atomised routers to be updated with all prefixes, and others with only atom ID destinations. ISSUE-G: How to do atomised routing ----------------------------------- (This section is formatted differently than others.) This section covers routing of atoms as a whole and updating the contents of atoms. We assume choices ISSUE-D-2, ISSUE-F-2 and ISSUE-I-1. Considerations: o The following kinds of updates are possible in atomised routing: * Advertising an atom and its prefixes. * Withdrawing an atom and its prefixes. * Adding prefixes to a previously advertised atom. * Removing prefixes from a previously advertised atom. o Advertisments and withdrawals may be reordered by BGP routers when they are propagated, and regrouped in different messages. o To allow for ISSUE-F-2, non-atomised routers must be able to build up a forwarding table of all prefixes. In addition, such routers must be able to propagate atom-specific information in update messages. Under ISSUE-F-1, prefixes must be propagated by non-atomised routers, even if these routers don't enter the prefixes into the forwarding table. This is hard, and we will ignore this option for now. o BGP path attributes gover advertised routes, not withdrawn routes. When an atom is withdrawn, we cannot use path attributes to encode atoms-related information, which leaves the following options for withdrawal: -> 1 An atom is withdrawn by placing the atom ID in the withdrawal section of a BGP update. An atomised router must look for atom IDs in withdrawal sections of received BGP updates. 2 An atom is withdrawn by placing all prefixes of the atom in the withdrawal section. An atomised router must detect when all prefixes of an atom have been withdrawn and infer from this event that the atom as a whole is withdrawn. Notes: o 2 is more expensive than 1. o It may be useful to have empty atoms (??), which is precluded by 2. o Option 1 does not preclude the prefixes of an atom to *also* be withdrawn (see below). Advertising and withdrawing of atoms is processed independently of adding and removing prefixes of an atom. I think this will make it simpler to deal with reordering of updates. One consequence of this is that atom contents state may be maintained by an atomised router, even if the atom itself is not being advertised. Two attributes are introduced below, ADVERTISE_ATOM and ADD_PREFIXES. These can be new attributes, or we may reuse existing attributes. This is a separate issue, discussed under ISSUE-H. Advertise atom -------------- BGP update sections: attributes: ADVERTISE_ATOM NLRI : the atom ID withdrawn : empty Processing by non-atomised router: o As any other destination. The route to this atom ID is entered into Adj-RIBs-In, after which it may be selected as the best route to the atom ID, and if so entered into the forwarding table and propagated to other routers. Processing by atomised router: o As non-atomised router. o If the best route to the atom ID changes as a result, forwarding table entries for any known prefixes of the atom are created or modified by copying them from the forwarding table entry of the atom ID. Withdraw atom (see earlier this section) ------------- BGP update sections: attributes: empty NLRI : empty withdrawn : the atom ID Processing by non-atomised router: o As any other destination. The route withdrawal is entered into Adj-RIBs-In, which may cause the best route to the atom ID to be updated, or the atom ID to be removed entirely as a destination. If such a change occurs, the forwarding table is updated accordingly and the withdrawal is propagated to other routers. Processing by atomised router: o As non-atomised router. o If (a) the best route to the atom ID changes as a result, or (b) the atom ID is removed entirely as a destination, then the forwarding table entries for any known prefixes of the atom are (a) modified by copying them from the forwarding table entry of the atom ID or (b) removed. Add prefixes to atom -------------------- BGP update sections: attributes: ADD_PREFIXES which contains the atom ID NLRI : the prefixes to be added withdrawn : empty Processing by non-atomised router: o The prefixes in the NLRI are processed as any other destination by placing them in Adj-RIBs-In. Processing by atomised router: o The mapping of atoms to prefixes is updated by creating an entry for the atom ID if it does not exist, and adding the prefixes in the NLRI to the entry. o If a route to the atom ID exists (i.e. the atom ID was announced earlier), then forwarding table entries for these prefixes are copied from the forwarding table entry of the atom ID. o The individual prefixes are *not* placed in Adj-RIBs-In. XXX consistency issue: should we maintain separate tables for each neighbour? Remove prefixes from atom ------------------------- BGP update sections: attributes: empty NLRI : empty withdrawn : prefixes to be removed Processing by non-atomised router: o The prefixes are processed as any other destination by placing them in Adj-RIBs-In as withdrawals. Processing by atomised router: o The mapping of atoms to prefixes is updated by removing the prefixes in the withdrawal section from the entry (if it exists). If the entry becomes empty, it may be removed. o If a route to the atom ID exists (i.e. the atom ID was announced earlier), then the forwarding table entries for these prefixes are removed. o Withdrawals for the individual prefixes are *not* placed in Adj-RIBs-In. XXX consistency issue: should we maintain separate tables for each neighbour? Notes: o There is nowhere to place an atom ID, since path attributes cannot be attached to witdrawals. An alternative might be to somehow readvertise the entire atom. ISSUE-H: Representation of ADVERTISE_ATOM and ADD_PREFIXES attributes --------------------------------------------------------------------- ISSUE-G introduces ADVERTISE_ATOM and ADD_PREFIXES attributes. These can either be new attributes, or we may reuse existing attributes. In any case, they should be transitive BGP attributes so that they may be propagated by non-atomised routers. (This effectively rules out BGP multiprotocol extensions.) Alternatives for ADVERTISE_ATOM: 1. Community attribute. 2. Extended community attribute. 3. A newly defined attibute. 4. Other ??? Alternatives for ADD_PREFIXES: 1. Aggregator field (ISSUE-I-1 only). This requires ISSUE-J-1. 2. Community attribute (not possible for ISSUE-I-1, won't fit). 3. Extended community attribute. 4. A newly defined attibute. 5. Other??? Notes: o The ADVERTISE_ATOM attribute does not need to carry any data, it is merely a marker. QQ o How widely implemented are extended communities? QQ o The aggregator field semantics appears to match the semantics of the atom ID. However, could the aggregator field be overwritten if some other router decided to aggregate the IPv4 address into a prefix? ISSUE-I: Representation of atom ID ---------------------------------- Alternatives: -> 1. As an IPv4 address. VZ 2. As an MPLS label. 3. Have a separate atom ID name space (e.g. represent as an integer). Notes: * Depends mostly on ISSUE-D, ISSUE-E and ISSUE-H * The advantage of 3 (and 2?) over 1 is that 3 fits inside a BGP community, whereas 1 will not. Extended communities can fit any of these. ISSUE-J: IPv4 address range --------------------------- Assuming ISSUE-I-1, the alternatives are: 1. Take IPv4 addresses from a range reserved only for atom IDs (e.g. a subrange of class E). 2. No special range for atom IDs. For example, use IPv4 addresses from one or more existing blocks. As noted elsewhere, Option 1 allows distinguishing an atom ID from other IPv4 addresses (in particular during forwarding) in the absence of other 'markers'. However it may be hard to obtain an allocation for atom IDs. If we can mark the presence of an atom ID in other ways a special IPv4 address range is not needed: o During routing, we could use Type 0 extended communities to carry IPv4 address atom IDs. We would need to obtain an AS number for the Global Administrator field. This AS number acts as a marker. QQ o During forwarding, I'm not sure. Can we set a flag in the IP header? The choice depends mostly on ISSUE-E. ISSUE-K: IPv4 atom ID allocation scheme --------------------------------------- Assuming ISSUE-J-1, this section discusses several ways to format and assign class E atom IDs. In all cases we assume a /8 of class E address space has been reserved for atoms, for example 240/8. The alternatives are: 1. 240.AS-BYTE1.AS-BYTE2.LOCAL / 32 A two-byte AS number is placed in bytes AS-BYTE1 and AS-BYTE2. An AS can define 256 atoms by setting the LOCAL byte. o This scheme cannot handle future four byte AS numbers o No more than 256 atoms per AS are possible. o BGP routers that filter prefixes longer than /24 will not carry such atom IDs. VZ 2. 240.ALLOC1.ALLOC2.ALLOC3 / 32 Atom IDs are allocated by allocating bytes ALLOC1, ALLOC2 and ALLOC3. o Can handle up to 16777216 atom IDs. o BGP routers that filter prefixes longer than /24 will not carry such atom IDs. o Requires allocation registry. VZ 3. 240.ALLOC1.ALLOC2.0 /24 Atom IDs are allocated by allocating bytes ALLOC1 and ALLOC2. Byte '0' is not used. o Can handle up to 65536 atom IDs. o Will not be filtered out by BGP routers based on prefix length. o Requires allocation registry. -> 4. Hybrid: 240.AS-BYTE1.AS-BYTE2.0 /24 AS numbers up to 49151 are assigned one atom ID per AS, which are encoded as under scheme 1. The remaining values of these two bytes (49152-65535) are reserved for allocation as under scheme 3. The '0' byte is never used. o Will not be filtered out by BGP routers based on prefix length. o Can handle up to 65536 atom IDs, of which 49152 for ASes with one atom ID, and 16384 atom IDs for ASes with more than one atom ID. o Allocation for ASes with one atom is simple. o Requires allocation registry for ASes with more than one atom and for ASes that have a number greater than 49151 (when that time comes). For initial implementation scheme 4 seems a fair compromise between experimental use, and (limited) deployment. If the number of atoms should outgrow this scheme during deployment, we can switch to scheme 3. In addition, there would at that point be a case to for operators to adjust their /24 filters (allowing atom IDs through), and scheme 2 then becomes a possibility too. Other unresolved issues ----------------------- The following issues can be decided in the future. * Non-BGP multihomers. Concerns networks that have several providers but do not speak BGP. * Overlapping atoms. Should we guard against overlapping atoms (e.g. misconfigurations)? Is this a problem?