Packet classification is a key mechanism that classifies incoming packets into flows to enable software-defined networking as well as a variety of networking services. Currently, ternary content addressable memory (TCAM) has been widely used for high-speed and low-latency packet classification. However, both range expansion and update performance are the fundamental issues for TCAM-based packet classification. A rule containing ranges could be replicated to multiple rules after converting its ranges into prefixes or ternary strings to occupy more than one TCAM entry. Many range encoding algorithms have been proposed to alleviate or avoid the problem of range expansion. These algorithms can be classified into database-independent (DI) and database-dependent (DD). While database-independent algorithms can accommodate new ranges without re-encoding the existing ranges, they may still cause rule replication. In contrast, database-dependent algorithms could avoid rule replication by adaptively encoding ranges, but new ranges may result in updates of the existing ranges. Accordingly, both types of algorithms may multiply the cost of TCAM updates. In this paper, we propose a DD range-encoding algorithm, Longest Enclosure Prefix Range Encoding (LEPRE), which can ensure that any new range does not cause any rule replication and re-encoding of the existing ranges. LEPRE employs the original fields as a part of range encoding to significantly decrease the requirements of extra bits for range encoding. Our experiment results show that LEPRE can maximize the TCAM storage efficiency. LEPRE also fully supports incremental updates to minimize the latency of TCAM updates.

OpenFlow discovery protocol (OFDP) is the standard protocol for discovering network topologies for OpenFlow. Each controller generates and receives OFDP messages for each switch to yield a network topology. However, for a network with a large number of switches, the controller may suffer from high overhead to perform OFDP even though the network topology remains unchanged. In this article, we improve the efficiency of network topology discovery by implementing a delegated function in OpenFlow switches. Our mechanism can reduce controller’s overhead for topology discovery to shorten the time of discovering a network topology. It also provides with the interoperability with switches which only perform OFDP. The experimental results demonstrate that the proposed scheme can improve the time for discovering a new network topology by decreasing the number of messages. Our scheme also eliminates unnecessary Packet-Out and Packet-In messages when the network topology remains unchanged. As a result, the controller overhead, including CPU usage and traffic load, is greatly reduced to shorten the response latency of controllers. Hence, the proposed scheme improves the feasibility of achieving scalable OpenFlow networking.