Prefix Allocation

This article describes the Deterministic prefix Allocation(DPA) / Centralized Prefix Allocation(CPA) functionality and configuration. It describes cnWave’s algorithm for allocating prefix to the nodes.

Basic

cnWave nodes operate with IPv6 subnet prefixes which are allocated from the Seed prefix configured in the Controller.

There are two different types for allocating subnet prefixes to the nodes with open/R.

Centralized(default)- Centralized prefix allocation is managed by E2E controller. The controller does all prefix allocations, which prevents collisions and provide more sophisticated allocation algorithm (Recommended for Single POP deployment)

Deterministic- Deterministic prefix allocation is also managed by E2E controller. The controller assigns prefixes to nodes based on the network topology to provide an advantage of route summarization and load balance the ingress traffic (Recommended for multi POP deployment)

Both Centralized and Deterministic prefix allocation requires below two basic parameters to be configured on to the controller

Seed Prefix- The prefix of entire cnWave network should be in in CIDR notation.

Prefix Length- specifies the bit-length of prefixes allocated to each node

Centralized Prefix Allocation

Controller will allocate prefixes automatically to the nodes once they are ignited. Allocation is performed by sequentially iterating the prefix specified in Seed Prefix.

For example:

seed prefix: 2001:a20:c305:ff00::/56

Allocation Prefix length: 64

The controller will assign prefixes in the following order,

2001:a20:c305:ff00::1

2001:a20:c305:ff01::1

:

2001:a20:c305:ffff::1

There is no subnetting of seed prefix happens in CPA and all the POP nodes will advertise the entire seed prefix to the upstream router. This makes the ingress traffic to choose the non-optimal POP nodes to reach the destination and may stress only few POPs in the network. Because of these limitations this Allocator is not recommended to be used for multi POP deployments.

Deterministic Prefix Allocation

The CPA allocation is somewhat arbitrary. That is, no subnetting of the seed prefix occurs and each POP node is only able to advertise the entire seed prefix to BGP peers, rather than a more specific subnet. This makes it possible for ingress traffic to enter the network through a suboptimal POP node.

Deterministic Prefix Allocation (DPA) assigns prefixes to nodes based on a given topology to allow POP nodes to take advantage of route summarization and help load balance ingress traffic. DPA attempts to segment a cnWave network so that each POP site can advertise its own specific BGP routes. Ingress traffic will then automatically flow through the optimal POP, instead of tromboning between POPs.

dpa_prefix_zones

Terminologies to know,

Prefix zone is a group of nodes closest to a specific POP site, DPA will segment the network into prefix zones (one per POP site).

Prefix space denotes the maximum number of nodes in the network, which is calculated by

Prefix space = 2^(Allocation prefix length – prefix length)

For example:

seed prefix: 2001:a20:c305:ff00::/56

Allocation Prefix length: 64

Prefix space = 2^(64-56) = 256

For the given seed prefix, we have 256 unique networks of /64 which will be assigned to each node.

Zone prefixes are assigned to a prefix zone. Zone prefixes are used to allocate node prefixes.

Node prefix is a prefix with Allocation prefix length that can be assigned to a node.

Segmentation into Prefix Zones

DPA begins by segmenting the network into prefix zones (one per POP site). This is accomplished by running a BFS algorithm starting from POP sites to find the closest POP site, in terms of hop count, to each node. Nodes closest to a specific POP site form a prefix zone.

Allocation of Prefix Spaces

Each prefix zone is allocated a number of prefixes so that the sum of their prefix spaces is at least as large as the number of nodes in the zone.

We Will investigate an example to understand the algorithm for subnetting the seed prefix into zone prefixes.

The deployment has 3 zones where the node count of each zone is listed below

Prefix zone A with 100 nodes

Prefix zone B with 68 nodes

Prefix zone C with 20 nodes

Seed Prefix : 2001:a20:c305:ff00::/56

Allocation Prefix Length: 64

Since seed prefix is /56, Prefix space is calculated as,

Prefix space = 2^(64-56) =256, Which can accommodate 256 nodes in the network.

Since subnetting can be done in powers of 2, the algorithm divides the prefix space into 4,

Zone A(100) Zone B(68) Zone C(20) Remaining
64 64 64 64

Prefix zone C is satisfied since it has only 20 nodes. Since prefix zones A and C are not yet satisfied, recurse using the remaining prefix space of 64. Split the the network prefix space (64) equally (divide by 2) and assign the prefix spaces (32) to each zone:

Zone A(100) Zone B(68) Zone C(20) Remaining
64 64 64 64
32 32 0

Now, prefix zone B is satisfied, but prefix zone A is not and there is no more remaining prefix space. The algorithm reaches a dead end, so it backtracks to the previous state:

Zone A(100) Zone B(68) Zone C(20) Remaining
64 64 64 64
32 32 0

This time, instead of dividing by 2, the divisor is multiplied by 2 and we divide the remaining (64) by 4. Then, assign a prefix space (16) to each of the two unsatisfied zones:

Zone A(100) Zone B(68) Zone C(20) Remaining
64 64 64 64
16 16 32

Now, prefix zone A is the only unsatisfied zone and it can use the rest of the remaining prefix space.

Zone A(100) Zone B(68) Zone C(20) Remaining
64 64 64 64
16 16 32
32 0

All prefix zones are satisfied, and the entire network prefix space has successfully been divided up.

Note: Algorithm reserves a headroom of 7 per zone to allow future addition of nodes.

Prefix spaces to prefix lengths

Next, the prefix spaces need to be converted to prefix lengths.

The prefix space to prefix length conversion is trivial:

prefix_length = allocPrefixLen - log_2 (prefix_space)

The log_2 will work nicely since prefix spaces are restricted to powers of 2. The prefix spaces from the previous example turn into:

Prefix Zone A(100) Prefix Zone B(68) Prefix Zone C(20)
/58 /58 /58
/60 /60
/59
4 Likes

We currently have a small live deployment with a single POP but we are currently testing a much larger deployment that has 2 POP nodes setup, but this deployment will eventually have at least 4 POP nodes. The E2E controller for the new deployment is setup to use Deterministic prefix allocation with a /52 seed prefix, Layer 2 bridging is also enabled. Running V1.2.1 external E2E controller and firmware. We currently have one other DN connected wirelessly to one of the POP nodes for testing. However, both POP nodes are advertising the full /52 prefix via BGP and it looks to be allocating /64 prefixes to nodes sequentially, the same as is done using Centralized allocation. In fact, the DN connected wirelessly to one of the POP nodes actually has its Layer 2 tunnel to the other POP node, not the one it is directly connected to, which does not make much sense, as this will cause customer traffic to trombone between the two POP nodes. Can you please confirm the following details:

1: Is the behavior we are seeing, as described, expected?

2: How and when is the BFS algorithm run e.g. does the controller do this periodically or whenever new nodes are added to the topology?

3: Is there any way to find out which nodes and prefixes are allocated to individual prefix zones?

4: Is there any way to override this and manually control the prefix distribution, if required?

Thanks.

Is the behavior we are seeing, as described, expected?

I think its because there are no clients to second POP. Can you add a DN or CN to the second POP and let us know the observations.

How and when is the BFS algorithm run e.g. does the controller do this periodically or whenever new nodes are added to the topology?

On addition, deletion of nodes

Is there any way to find out which nodes and prefixes are allocated to individual prefix zones?

In the map, if you click on show prefix zones, zones are shown visually. Mouse hover and click on zone shows some information.

Is there any way to override this and manually control the prefix distribution, if required?

No

Thanks for the information. I think the issue was that we had the two POP nodes on the same site, as they are in the same physical location. When we changed this to using two separate logical sites, on cnMeastro, the two prefix zones appeared as expected.

1 Like