Rejected ideas for End to End Aggregation of Multicast Addresses

1. Introduction & Requirements

This document is simply a repository for ideas related to End to End Aggregation of Multicast Addresses [1], which may have some merit but were rejected in arriving at the scheme chosen.
 

2. Scheme Description (rejected items)

2.2 Further storage optimisation (for IPv4)

2.2.1 Mask offset, d

{Note: this section was written when the AMA construction rules were slightly different, viz:
s=0 was taken to mean the full range of values of v, not none of them.
meanings of s >= 2n were reserved but undefined.     ------(2)
}

Ideally, d would have been 5 bits wide so that masks could be in any position across the remainder. However, it is possible to achieve the same effect without the inelegance of a 23 bit wide remainder and without wasting half the value of a fifth bit on d (because it only needs to reach 24, not 32).

d should be chosen from a uniform random distribution between -8 and 15. However, if it is negative, the first bit of the first s in the AMA (and not subsequent values of s), is set and d is stored as its own twos complement. On retrieval from storage, the first bit of the first s is tested then cleared  if set, in which case the reverse operation on d is performed. d wraps to the start of the remainder and offsets from left to right. The example also shows how n > d makes n wrap round the remainder.

It is important that there is an equal chance of the base of an AMA being anywhere within the remainder, so d should not be from a uniform random distribution between -16 and 15 which would make it twice as likely to point to within the third octet than the second or fourth..

It should be noted that, under the rules for ws given under formula (4), an initial value of s with a leading bit set would break formula (2) in all cases.  Such a value of s can only be used in a subsequent (t,s) pair to the first -  after a t with at least the first bit set has been used to increment m. Therefore, this reuse of the first bit of the first s in an AMA is perfectly valid and safe.

A wider field for the offset would be useful, but the offset should be embedded in the multicast address used for sending which is matched against the AMA held in the routers tables. Otherwise routing becomes very cumbersome. Also, leaving d at 4 bits wide, leaves 8 bits clear of the mask (plus the 4 bits of d itself) for allocation related to the topology of the tree root, rather than receivers.

2.3 Alternatives explored and rejected

This section is more to document the process by which the results were arrived at than for the general reader.

There are two categories of alternative approach to this scheme, each with detailed alternatives within, that have all been investigated and discarded in favour of the approach presented. They are briefly documented before we forget the reason why they were rejected, in case they re-surface again later and need slaying. The differentiator between the two categories is the atomicity of address allocation.

2.6.1 Per-address allocation atomicity class

Taking the category in which the chosen scheme sits first. This category has per multicast address allocation atomicity - two separate AMAs can contain some of the same multicast addresses (but incidentally, not all the same), so testing of prior-use is on a per-multicast address basis - the AMAs just name aggregates, they don't name allocation units. This makes evolution easier, in that multicast addresses in isolation continue to mean a discrete group address. In other words, multicast addresses can be used ambiguously, depending on context.

There follows a discussion based around the various parameters used in this category and how they could have been incorporated differently:

wd
The mask offset could have been a third parameter outside the address, however, the design goal was to cram as much meaning into the address as possible (because it is being stored anyway), while ensuring that parameters that we wanted to vary (for address expansion and contraction) without the address varying were independent of the address.

s
Could have been implied as equal to vmin. That is, the group of addresses cold have been implicitly defined as from v = 0 to v = vmin (which would have been the max), with only the need to use 4 bits to state m. It was decided that what this saved in storage, it more than lost in flexibility. This would only have been useful for cumulative layering applications, and would have made more arbitrary aggregation, like for distributed simulations, very hard.

m
Instead of being a bit-mask width, m could have been a bit mask itself. This would have allowed arbitrary bits across the remainder field to make up v rather than being limited to contiguous bits (the ones in the mask indicating where the relevant bits of v were). However, given m is stored on the router for each AMA, this seemed unnecessary flexibility and would have also made a solution to large-scale aggregation harder.

2.6.2 Per-aggregation allocation atomicity class

The second (rejected) category is that where any one multicast address can only be in one aggregate. This makes evolution (even more) difficult, in that the meaning of any one multicast address can only be as part of an aggregate, so must change from its old meaning. The only way to do evolution in this scenario is to allocate a new range of IP addresses  multicast aggregates or have a "D Day" where the meaning of an existing range is switched all at once. This also wastes all the addresses in the unused corners of the aggregates, encouraging address hoarding.

This second category involves the allocation of a class of IP addresses for aggregated multicast. One example of such a scheme is given below where one bit of the IPv4 address space (the fifth) is assumed to be available to indicate that this is an aggregated multicast address (arbitrarily assume if it is set, it is aggregated).

First the end-system generates a random bit mask of length B with exactly n zeroes in it, where 2n is the maximum required size of set of addresses. For IPv4, take B = 8 and for example, if n = 3 it might choose:

Next the end-system chooses a random masked address of length B, except the bits that align with zeroes in the mask are "don't care" values (X). For example, it might choose: The full set of composite addresses represented by the combination of the mask and the masked address is then defined as all the 2n combinations of AM constrained to be fixed only where there is a 1 in the mask. Further, the combination of the mask, M, and any specific address Am is defined as implying the set of all addresses A0 - AM

Next the end-system chooses a random unmasked address of length R (the remainder of the address width). For example, it might choose:

Finally all six ordered combinations of the three octets, M, AM and AU are mapped to a combination enumerator, C (3 bits) Finally these are all concatenated after the 4 bits that signify multicast in IPv4 and the single bit that signifies this is the aggregated multicast class of address (COA): Thus, 232.181.170.52 is an aggregated multicast address representing the four addresses: With such a scheme, you need only test one multicast address to know that all those in a group should be free or not. However, it is difficult to expand and contract the group size so this will not be discussed further.

3. References

[1] R. Briscoe, BT, "End to End Aggregation of Multicast Addresses", Nov 1997 <http://www.labs.bt.com/people/briscorj/projects/lsma/e2ama.html>