Browse Prior Art Database

BEHAVIORAL ADAPTIVE CACHE MANAGEMENT: A NEW CACHE DATABASE MANAGEMENT SYSTEM, OPTIMIZED FOR SCALED SOFTWARE –DEFINED NETWORKING ENVIRONMENTS

IP.com Disclosure Number: IPCOM000244337D
Publication Date: 2015-Dec-02
Document File: 22 page(s) / 3M

Publishing Venue

The IP.com Prior Art Database

Related People

Salvatore Valenza: AUTHOR [+4]

Abstract

Mechanisms and systems are provided to improve the management of cache memories and generic databases in software-defined networking (SDN) environments. A self-adaptive behavior recognizer is provided that is operated based on CPU data, database (DB) runtime status and related statistics to optimize a weak Georgy Adelson-Velsky and Evgenii Landis (WAVL) tree-based DB that is pre-filtered by a Counting Bloom Filter (CBF). This allows selecting either a "WAVL Access Through Adaptive CBF" (WATAC) methodology or a "WAVL Access through Method Analyzer and CBF" (WAMAC) methodology to improve the search time in the DB and to manage a high number of entries in the cache memories and in the generic databases.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 16% of the total text.

Page 01 of 22

BEHAVIORAL ADAPTIVE CACHE MANAGEMENT: A NEW CACHE DATABASE MANAGEMENT SYSTEM, OPTIMIZED FOR SCALED SOFTWARE -DEFINED

NETWORKING ENVIRONMENTS

AUTHORS:

Salvatore Valenza

Domenico Ficara

Roberto Muccifora
Leo Caldarola

CISCO SYSTEMS, INC.

ABSTRACT

    Mechanisms and systems are provided to improve the management of cache memories and generic databases in software-defined networking (SDN) environments. A self-adaptive behavior recognizer is provided that is operated based on CPU data, database (DB) runtime status and related statistics to optimize a weak Georgy Adelson- Velsky and Evgenii Landis (WAVL) tree-based DB that is pre-filtered by a Counting Bloom Filter (CBF). This allows selecting either a "WAVL Access Through Adaptive CBF" (WATAC) methodology or a "WAVL Access through Method Analyzer and CBF" (WAMAC) methodology to improve the search time in the DB and to manage a high number of entries in the cache memories and in the generic databases.

DETAILED DESCRIPTION

    SDN solutions are starting to be ubiquitously utilized in network routers and switches. Within SDN controllers an increasing demand for managing a large number of flows associated with multiples network nodes has been observed. This results in an extended need for using large databases. In order to reduce the traffic between the network elements and the SDN controller, caching mechanisms are needed to ensure that the SDN controller only requests data from the nodes if the data is not obsolete. These cache memories usually manage several thousands of entries and are implemented utilizing a WAVL tree.

Copyright 2015 Cisco Systems, Inc.

1


Page 02 of 22

    The search complexity of a WAVL tree is small (i.e., it is O(log(n)). As the SDN controller manages larger and larger amounts of data, the number of items in the cache memories or databases normally increases up to a few million entries, making a WAVL tree search cumbersome.

    After configuration or after flow establishment, WAVL tree-based caches under analysis are managing about the same number of keys. The introduction of new keys is a quite slow process with respect to the overall activities of the SDN controller, even if the data are updated at run time.

    In conventional systems, in order to avoid a continuous WAVL tree search on the DB, a CBF can be applied to the incoming request so that the WAVL search runs only for the items that are actually present in the DB.

FIG. 1 shows CBF pre-processing on a WAVL tree DB system

FIG. 1

    As shown in FIG. 1, a cache manager handles an external item query as follows. At 1, when the cache manager receives an external item query, the cache manager sends a message to the CBF requesting an analysis. There are two possible scenarios. In a first scenario, at 2.1 in FIG. 1, the CBF detects that the item is not present in the WAVL tree DB and reports the determination result to the cache manager. At 3.1, the cache manager reports to the SDN controller that the data is not present or stores a ne...