# US 2014/0192811 A1 · Method and a device for defining a look-up system for a network element of a software-defined network > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0192811 A1 - Document ID: US20140192811A1 - Status: Published application - Kind: A1 - Application number: 14/146,132 - Filed: 2014-01-02 - Published: 2014-07-10 - Earliest claimed: 2013-01-04 - Assignees: Tellabs Oy - Applicants: Tellabs Oy - Inventors: Ville HALLIVUORI; Juhamatti KUUSISAARI - Web page: https://patentgrep.com/patent/US20140192811A1 ## CPC - H04L 45/7452: Multiple parallel or consecutive lookup operations (lookup operation involving Bloom filters H04L45/7459) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A method for defining a look-up system having functionality suitable for a network element of a software-defined network “SDN” includes maintaining (401) data specifying a set of look-up tables so that the look-up system is capable of being constructed in alternative ways using one or more look-up tables of the set of look-up tables and each of the look-up tables has a look-up table specific resource consumption estimate indicating a load factor of at least one component of the network element when running operations related to the look-up table. The method includes selecting (402), on the basis of the look-up table specific resource consumption estimates, such one of the alternative ways of constructing the look-up system which provides a look-up system that is optimal, or at least suitable, for the network element. ## Claims ### Claim 1 A device for defining a look-up system having functionality suitable for a network element of a software-defined network, the device comprising a processing system adapted to: maintain data specifying a set of look-up tables so that the look-up system is capable of being constructed in mutually alternative ways with the aid of one or more look-up tables belonging to the set of look-up tables, each of the look-up tables having a look-up table specific resource consumption estimate indicating a load factor of at least one component of the network element when running operations related to the look-up table, and select, on the basis of the look-up table specific resource consumption estimates, such one of alternative look-up systems which is more suitable for the network element than another one of the alternative look-up systems, each of the alternative look-up systems corresponding to one of the mutually alternative ways to construct the look-up system having the functionality suitable for the network element. ### Claim 2 (depends on 1) A device according to claim 1, wherein the processing system is adapted to compute resource consumption estimates for two or more of the alternative look-up systems on the basis of the look-up table specific resource consumption estimates related to the look-up tables contained by the two or more alternative look-up systems and to select a particular one of the two or more alternative look-up systems which has, according to the pre-determined criterion, the most advantageous resource consumption estimate. ### Claim 3 (depends on 1) A device according to claim 1, wherein the processing system is adapted to use a genetic algorithm implementing simulated evolution for selecting the one of the alternative look-up systems. ### Claim 4 (depends on 1) A device according to claim 1, wherein the processing system is adapted to use the Dijkstra or A* optimization algorithm for selecting the one of the alternative look-up systems from a search network where the look-up tables are related to nodes of the search network and the look-up table specific resource consumption estimates represents costs related to the nodes or to connections between adjacent nodes, an optimal one of the alternative look-up systems corresponding to a minimum cost route through the search network so that look-up tables related to the minimum cost route form a look-up system having the functionality suitable for the network element. ### Claim 5 (depends on 1) A device according to claim 1, wherein the look-up table specific resource consumption estimates comprise numerical values indicating load factors of two or more components of the network element and the processing system is adapted to compute, for each of the components of the network element and for each of the alternative look-up systems under consideration, a sum of the numerical values related to that component of the network element and to look-up tables of the corresponding alternative look-up system, the sums related to the components of the network element constituting a resource consumption estimate related to the corresponding alternative look-up system. ### Claim 6 (depends on 1) A device according to claim 1, wherein each of the look-up table specific resource consumption estimates comprises an estimate of at least one of the following load factors caused by the operations related to the corresponding look-up table: a load factor of a data forwarding section of the network element, a load factor of a control processor section of the network element, a load factor of random access memories of the network element, a load factor of content access memories of the network element, a load factor of ternary content access memories of the network element, a load factor of memory busses of the network element. ### Claim 7 A controller system for configuring a network element of a software-defined network, the controller system comprising: a device for defining a look-up system having functionality suitable for the network element, and a data interface for sending, to the network element, configuration data expressing the look-up system having the functionality suitable for the network element, wherein the device comprises a processing system adapted to: maintain data specifying a set of look-up tables so that the look-up system is capable of being constructed in mutually alternative ways with the aid of one or more look-up tables belonging to the set of look-up tables, each of the look-up tables having a look-up table specific resource consumption estimate indicating a load factor of at least one component of the network element when running operations related to the look-up table, and select, on the basis of the look-up table specific resource consumption estimates, such one of alternative look-up systems which is more suitable for the network element than another one of the alternative look-up systems, each of the alternative look-up systems corresponding to one of the mutually alternative ways to construct the look-up system having the functionality suitable for the network element. ### Claim 8 (depends on 7) A controller system according to claim 7, wherein a processing system is adapted to configure a routing topology of the software-defined network so that more data traffic load is allocated to the network element if a resource consumption estimate of the look-up system manifests lower loading of the network element than if the resource consumption estimate of the look-up system manifests higher loading of the network element, the resource consumption estimate of the look-up system being determined by the one or more look-up table specific resource consumption estimates related to one or more look-up tables comprised by the look-up system. ### Claim 9 (depends on 7) A controller system according to claim 7, wherein the controller system is adapted to read the look-up table specific resource consumption estimates from one or more data frames received at the controller system. ### Claim 10 (depends on 7) A controller system according to claim 7, wherein the controller system is adapted to send one or more first data frames to the network element and to read the look-up table specific resource consumption estimates from one or more second data frames received from the network element, the one or more first data frames containing descriptors of the look-up tables. ### Claim 11 (depends on 10) A controller system according to claim 10, wherein each of the descriptors of the look-up tables comprises at least one of the following: the maximum number of entries of the corresponding look-up table, the size of one or more look-up keys of the corresponding look-up table, allowed don't care key matching bit positions in the corresponding look-up table, definitions of tasks related to the entries of the corresponding look-up table, maximum look-up frequency of the corresponding look-up table, average time between successive updates of the corresponding look-up table. ### Claim 12 A network element for a software-defined network, the network element comprising: a data transfer interface for receiving data and for transmitting data, the received data expressing functionality needed for enabling the network element to operate as a part of the software-defined network, a device for defining a look-up system having the functionality expressed by the received data, and a data forwarding section for managing data frames in accordance with the look-up system, wherein the device comprises a processing system adapted to: maintain data specifying a set of look-up tables so that the look-up system is capable of being constructed in mutually alternative ways with the aid of one or more look-up tables belonging to the set of look-up tables, each of the look-up tables having a look-up table specific resource consumption estimate indicating a load factor of at least one component of the network element when running operations related to the look-up table, and select, on the basis of the look-up table specific resource consumption estimates, such one of alternative look-up systems which is more suitable for the network element than another one of the alternative look-up systems, each of the alternative look-up systems corresponding to one of the mutually alternative ways to construct the look-up system having the functionality suitable for the network element. ### Claim 13 A method for defining a look-up system having functionality suitable for a network element of a software-defined network, the method comprising: maintaining data specifying a set of look-up tables so that the look-up system is capable of being constructed in mutually alternative ways with the aid of one or more look-up tables belonging to the set of look-up tables, each of the look-up tables having a look-up table specific resource consumption estimate indicating a load factor of at least one component of the network element when running operations related to the look-up table, and selecting, on the basis of the look-up table specific resource consumption estimates, such one of alternative look-up systems which is more suitable for the network element than another one of the alternative look-up systems, each of the alternative look-up systems corresponding to one of the mutually alternative ways to construct the look-up system having the functionality suitable for the network element. ### Claim 14 (depends on 13) A method according to claim 13, wherein the method comprises computing resource consumption estimates for two or more of the alternative look-up systems on the basis of the look-up table specific resource consumption estimates related to the look-up tables contained by the two or more alternative look-up systems and selecting a particular one of the two or more alternative look-up systems which has, according to the pre-determined criterion, the most advantageous resource consumption estimate. ### Claim 15 (depends on 13) A method according to claim 13, wherein the one of the alternative look-up systems is selected with a genetic algorithm implementing simulated evolution. ### Claim 16 (depends on 13) A method according to claim 13, wherein the one of the alternative look-up systems is selected with the Dijkstra or A* optimization algorithm from a search network where the look-up tables are related to nodes of the search network and the look-up table specific resource consumption estimates represents costs related to the nodes or to connections between adjacent nodes, an optimal one of the alternative look-up systems corresponding to a minimum cost route through the search network so that look-up tables related to the minimum cost route form a look-up system having the functionality suitable for the network element. ### Claim 17 (depends on 13) A method according to claim 13, wherein the look-up table specific resource consumption estimates comprise numerical values indicating load factors of two or more components of the network element and the method comprises computing, for each of the components of the network element and for each of the alternative look-up systems under consideration, a sum of the numerical values related to that component of the network element and to look-up tables of the corresponding alternative look-up system, the sums related to the components of the network element constituting a resource consumption estimate related to the corresponding alternative look-up system. ### Claim 18 (depends on 13) A method according to claim 13, wherein each of the look-up table specific resource consumption estimates comprises an estimate of at least one of the following load factors caused by the operations related to the corresponding look-up table: a load factor of a data forwarding section of the network element, a load factor of a control processor section of the network element, a load factor of random access memories of the network element, a load factor of content access memories of the network element, a load factor of ternary content access memories of the network element, a load factor of memory busses of the network element. ### Claim 19 (depends on 13) A method according claim 13, wherein the method comprises configuring a routing topology of the software-defined network so that more data traffic load is allocated to the network element if a resource consumption estimate of the selected one of the alternative look-up systems manifests lower loading of the network element than if the resource consumption estimate of the selected one of the alternative look-up systems manifests higher loading of the network element, the resource consumption estimate of the selected one of the alternative look-up systems being determined by one or more look-up table specific resource consumption estimates related to one or more look-up tables comprised by the selected one of the alternative look-up systems. ### Claim 20 (depends on 13) A method according to claim 13, wherein the method comprises reading the look-up table specific resource consumption estimates from one or more data frames received at a controller system of the software-defined network. ### Claim 21 (depends on 13) A method according to claim 13, wherein the method comprises sending one or more first data frames to the network element and reading the look-up table specific resource consumption estimates from one or more second data frames received from the network element, the one or more first data frames containing descriptors of the look-up tables. ### Claim 22 (depends on 21) A method according to claim 21, wherein each of the descriptors of the look-up tables comprises at least one of the following: the maximum number of entries of the corresponding look-up table, the size of one or more look-up keys of the corresponding look-up table, allowed don't care key matching bit positions in the corresponding look-up table, definitions of tasks related to the entries of the corresponding look-up table, maximum look-up frequency of the corresponding look-up table, average time between successive updates of the corresponding look-up table. ### Claim 23 A non-transitory computer readable medium encoded with a computer program for defining a look-up system having functionality suitable for a network element of a software-defined network, the computer program comprising computer executable instructions for controlling a programmable processing system to: maintain data specifying a set of look-up tables so that the look-up system is capable of being constructed in mutually alternative ways with the aid of one or more look-up tables belonging to the set of look-up tables, each of the look-up tables having a look-up table specific resource consumption estimate indicating a load factor of at least one component of the network element when running operations related to the look-up table, and select, on the basis of the look-up table specific resource consumption estimates, such one of alternative look-up systems which is more suitable for the network element than another one of the alternative look-up systems, each of the alternative look-up systems corresponding to one of the mutually alternative ways to construct the look-up system having the functionality suitable for the network element. ### Claim 24 A software-defined network comprising: one or more network elements, and a controller system for transmitting configuration data to the one or more network elements so as to configure the one or more network elements, wherein the controller system comprises: a device for defining, for at least one of the network elements, a look-up system having functionality suitable for the network element, and a data interface for sending, to the network element, configuration data expressing the look-up system, and wherein the device comprises a processing system adapted to: maintain data specifying a set of look-up tables so that the look-up system is capable of being constructed in mutually alternative ways with the aid of one or more look-up tables belonging to the set of look-up tables, each of the look-up tables having a look-up table specific resource consumption estimate indicating a load factor of at least one component of the network element when running operations related to the look-up table, and select, on the basis of the look-up table specific resource consumption estimates, such one of alternative look-up systems which is more suitable for the network element than another one of the alternative look-up systems, each of the alternative look-up systems corresponding to one of the mutually alternative ways to construct the look-up system having the functionality suitable for the network element. ### Claim 25 (depends on 24) A software-defined network according to claim 24, wherein the controller system is configured to use the OpenFlow as a communication method for a control plane of the software-defined network to communicate with a data plane of the software-defined network.