пятница, 18 марта 2016 г.

VLAN calculation algorithm design

I've had a task to automate calculation and setting up VLANs on switches of our regional network.

The task was naturally split into two phases:
  1. calculate VLAN numbers on the switches and trunks;
  2. synchronize switch configurations to the calculated result.
The first one was not quite obvious, a new algorithm needed to be designed. The second was done by another programmer.

I have designed and implemented the algorithm. Key points:
  • We have list of devices, trunks, client port VLANs on each device as input data. VLAN sets for each trunk is the output. The network has multiple loops for redundancy.
  • VLAN should be included on a trunk if it is two-way on the trunk, this means that we can spread VLANs from their endpoints on the graph and then calculate VLANs on trunks as intersection of sets of one direction and the other.
  • We spread VLAN set from each device as a bit vector. Each trunk has two associated  VLAN sets, one for each direction.
  • If we use STP protocol, then VLANs should be unified across each group of connected cycles (which have a common trunk).
  • If we use ERPS, then the VLANs should be unified starting from most outer half-loop to the base loop.
  • We can prune VLAN propagation if the trunk already contains all VLANs from the propagation set (an exception was necessary for multiply connected non-switch devices), thus runtime is reduced significantly.
I used perl and Bit::Vector module. The first version did not prune VLAN propagation and it took 1-2 minutes to complete on our network topology (more than 1600 devices), and after implementing the pruning it takes just 4 seconds (including database queries).

The following article was invaluable for understanding multi-ring ERPS topologies:
D. Lee, K. Lee, S. Yoo and J. K. K. Rhee, "Efficient Ethernet Ring Mesh Network Design," in Journal of Lightwave Technology, vol. 29, no. 18, pp. 2677-2683, Sept.15, 2011.