software defined networking (SDN) nodes may be required to
coexist with legacy nodes to form hybrid networks. It has been
shown that such a hybrid network has better performance than
a pure legacy network due to smarter transmission scheduling.
Despite such advantages, limited budgets continue to hinder
the rapid adaptation of SDNs. Only a part of the network can
be upgraded at a time especially for large-scale networks.
In this paper, we define the minimum percentage of SDN nodes
in a path, and paths with at least one SDN node, as the hop
coverage and path coverage, respectively. We intend to evaluate
the relationship between cost and coverage in the partially
deployed SDNs. We formulate SDN node selection as four
optimization problems with hop/path coverage and cost as
objectives and constraints, respectively, and vice-versa.
We propose two heuristic solutions: 1) maximum number
of uncovered path first (MUcPF) and 2) maximum number
of minimum hop covered path first (MMHcPF), to these
NP-hard problems. Through a MATLAB experiment, we
show that MUcPF is significantly better in terms of economy
and efficiency to establish a hybrid path between every pair
of hosts in the network. In particular, it required 5%–15% less
investment to achieve 100% path coverage compared to other
algorithms. The results show the coverage consistency of
MMHcPF on each individual path along with gains in terms of
cost and efficiency. It takes 5%–20% less investment to achieve
certain hop coverage target compared to other existing algorithms.