This paper considers the problem of upgrading a legacy network into a Software Defined Network (SDN) over multiple stages and maximizing energy saving (ES) in the resulting upgraded network or hybrid SDN. In each stage, an operator needs to select and replace legacy switches with SDN switches and seek to switch off as many cables as possible over each link. This paper addresses the said problem where it considers (i) the available budget at each stage, (ii) maximum path delays, (iii) maximum link utilization, (iv) per-stage increase (decrease) in traffic size (upgrade cost), and (v) each non SDN switch must comply with the Open Shortest Path First (OSPF)-Equal Cost Multi-Path (ECMP) protocol. It outlines a Mixed Integer Program (MIP) and a heuristic algorithm called M-GMSU. The results show that (i) MIP and M-GMSU achieve ES of up to 71.93%, (ii) using a larger budget and/or number of stages increases ES, and (iii) the ES of M-GMSU is within 3.55% away from the optimal ES computed by MIP.

Dynamic IP router table schemes, proposed in the literature, perform an IP lookup or an on-line prefix update in O(log n) memory accesses. In term of lookup time, they are still slower than FEC (CNHA/CWA) scheme, which requires exactly (at most) three memory accesses for each lookup, irrespective of the number of prefixes n. The prefix update in FEC (CNHA/CWA) has a drawback: Off-line solutions need structure reconstruction, or implementing on-line prefix updates is difficult. This paper solves this problem. We propose the use of lexicographic ordered prefixes to reduce off-line construction time. Simulations on several real routing databases, run on the same platform, show that our approach constructs FEC (CNHA/CWA) tables in 2.56 to 7.74 (1.56 to 2.7) times faster than that from previous techniques. Our on-line update scheme uses an updatable-address-set and selectively decompresses the FEC and CNHA/CWA structures to modify only the next-hops of the addresses in the set. Recompressing the updated structures, the resulting tables are identical to what would have been obtained by structure reconstructions, but at much lower computational cost. Our on-line update for FEC (CNHA/CWA) scheme takes at most 10.1 (7.21) -Ýs, which is of same order as achieved by the recently proposed schemes.