In this paper we present an algorithmic framework for solving a class of combinatorial optimization problems on graphs with bounded pathwidth. The problems are NP-hard in general, but solvable in linear time on this type of graphs. The problems are relevant for assessing network reliability and improving the network's performance and fault tolerance. The main technique considered in this paper is dynamic programming.

In the paradigm of Software-Defined Networking (SDN), its data plane generally perform packet forwarding based on flow table lookup on TCAM with high energy consumption. Popular energy-saving methods employ caching techniques for most packets to bypass energy-intensive TCAM lookups. However, existing energy-saving caches cannot adapt to network traffic fluctuation with sufficient utilization of cache space due to non-negligible hash conflicts. To overcome this issue, we design a traffic-aware energy-saving cache with optimal utilization for TCAM flow tables in SDN data plane. In particular, we first devise a nearly conflict-free hashing algorithm for the cache called FelisCatus, which provides three candidate locations for each incoming flow by adjacent hopping, and searches for an empty or replaceable entry for each conflicting flow by co-directional kicking. Then, we propose an adaptive adjustment mechanism of flow activity criterion, i.e., packet inter-arrival time threshold, for enabling the cache to consistently accommodate the most active exact flows in network traffic. Furthermore, we build an energy-efficient SDN flow table storage architecture by applying the above cache and exploiting the accessing features of different memories. Finally, we verify the performance of our designed energy-saving cache and flow table storage architecture by experiments with backbone network traffic traces. Experimental results indicate that, our designed energy-saving cache obtains stable and high hit rates around 75% even under network traffic fluctuation, and our proposed flow table storage architecture achieve high energy saving rates around 71%, with the increase of 7.89% compared to state-of-the-art ones.