Embedding-Based K-Means for Multi-Controller Placement in Software-Defined Networks: A Cross-Scale Empirical Study on Internet Topology Zoo

Multi-controller deployments in Software-Defined Networking require choosing both the number of controllers and their placement on the topology. Clustering-based methods, particularly k-means, are widely used for this problem, but the topology representation that the clustering operates on is rarely chosen explicitly. We treat the representation step as a design axis: the clustering algorithm is held fixed at k-means with k-means++ initialisation, and the input is varied across three classical, training-free embeddings of the propagation-delay distance matrix: metric multidimensional scaling (MDS), Isomap, and Laplacian Eigenmaps (Spectral). The evaluation covers thirteen Internet Topology Zoo backbones grouped into three scale tiers under an effective-N definition, with the controller count K varied from 2 to 10, and reports node-to-controller latency (N2C), controller-to-controller latency (C2C), and load imbalance jointly rather than singly, with paired significance tests over ten distinct seeds. The representation choice is consequential: 60% of pairwise embedding comparisons are statistically separated (Holm-corrected Wilcoxon, α=0.05), and the median best-versus-worst gap per configuration is 23–25% on the two latency metrics and 71% on load imbalance. Metric MDS achieves the lowest N2C in most regimes; Spectral achieves the lowest C2C on the medium and large tiers at mid-to-high K; Isomap trades single-metric wins for worst-case robustness and is non-dominated in 79% of the 63 large-tier configurations. Across all 117 configurations, each embedding is empirically non-dominated (within the embeddings compared and on this benchmark) in 67–85% of configurations, and 16% admit a single statistically separated best choice. Two baselines contextualise these results: k-means on the raw latency matrix leads in under 8% of configurations, and a Node2Vec baseline is competitive on C2C and load balance but trails the classical methods on N2C at one to two orders of magnitude higher embedding cost. Best-embedding identities transfer from k-means to a k-medoids variant in 70% of configurations. Capacity-, energy-, and reliability-aware extensions remain open.