Complexity issues intrinsic to certain fundamental data dissemination problems in high performance network topologies are discussed. In particular, the p-pairwise node, as well as the edge, disjoint shortest paths problem. An efficient algorithm for the p-pairwise node disjoint shortest paths problem when every source point is at a distance at most two from its target is presented and it is shown that for distance three pairs the problem is NP-complete. The problem remains NP-complete even when near-shortest paths are allowed and it is NP-hard for arbitrary length paths. The p-pairwise edge disjoint shortest paths problem is shown to be solvable in polynomial time when every source point is at a distance at most two from its target and it is shown to be NP-complete for distance three pairs. Computational complexity issues for related problems are also discussed.