# US 2014/0192813 A1 · Method and a device for defining implementation of a look-up table 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/0192813 A1 - Document ID: US20140192813A1 - Status: Published application - Kind: A1 - Application number: 14/147,994 - Filed: 2014-01-06 - 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/US20140192813A1 ## CPC - H04L 45/54: {Organization of routing tables} - H04L 41/0803: Configuration setting - H04L 41/0895: Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements - H04L 41/342: between virtual entities, e.g. orchestrators, SDN or NFV entities - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A method and a device for defining implementation of a look-up table for a network element of a software-defined network “SDN” is presented. The network element includes hardware for implementing the look-up table in two or more mutually alternative ways. The method includes selecting (301) an optimal, or at least a suitable, one of the mutually alternative ways to implement the look-up table on the basis of a) the hardware available for implementing the look-up table, b) information about one or more look-up keys, and c) at least one of the following: the maximum number of entries of the look-up table, an average time between successive look-ups, an average time between successive modifications of the look-up table. The method enables the network element to be configured in a way that the hardware resources of the network element are utilized in an optimal or at least a suitable way. ## Claims ### Claim 1 A device for defining implementation of a first look-up table for a network element of a software-defined network, the network element comprising hardware for implementing the first look-up table in two or more mutually alternative ways, the device comprising a processing system adapted to: receive one or more first data items providing information about one or more look-up keys of the first look-up table, receive one or more second data items indicating at least one of the following: the maximum number of entries of the first look-up table, an average time between successive look-ups from the first look-up table, an average time between successive modifications of the first look-up table, and select one of the two or more mutually alternative ways to implement the first look-up table on the basis of the hardware available for implementing the first look-up table, the one or more first data items, and the one or more second data items. ### Claim 2 (depends on 1) A device according to claim 1, wherein the processing system is adapted to compute a weighted sum of the one or more first data items and the one or more second data items and to compare the weighted sum to a first threshold so as to make a selection between an implementation based on content access memory technology and an implementation based on a retrieval tree algorithm and random access memory technology. ### Claim 3 (depends on 1) A device according to claim 1, wherein the processing system is adapted to compare a second threshold to a third data item indicating a ratio of the number of don't care key matching bit positions of the first look-up table to the number of all key matching bit positions of the first look-up table so as to make a selection between an implementation based on binary content access memory technology and an implementation based on ternary content access memory technology. ### Claim 4 (depends on 2) A device according to claim 2, wherein the processing system is adapted to compare a second threshold to a third data item indicating a ratio of the number of don't care key matching bit positions of the first look-up table to the number of all key matching bit positions of the first look-up table so as to make a selection between an implementation based on binary content access memory technology and an implementation based on ternary content access memory technology. ### Claim 5 (depends on 1) A device according to claim 1, wherein the processing system is adapted to determine hardware remaining free for implementing a second look-up table after implementation of the first look-up table and to select one of the two or more mutually alternative ways to implement the second look-up table on the basis of the hardware available for implementing the second look-up table and data related to the second look-up table and indicating corresponding information as the one or more first data items and the one or more second data items indicate relating to the first look-up table. ### Claim 6 (depends on 2) A device according to claim 2, wherein the processing system is adapted to determine hardware remaining free for implementing a second look-up table after implementation of the first look-up table and to select one of the two or more mutually alternative ways to implement the second look-up table on the basis of the hardware available for implementing the second look-up table and data related to the second look-up table and indicating corresponding information as the one or more first data items and the one or more second data items indicate relating to the first look-up table. ### Claim 7 (depends on 3) A device according to claim 3, wherein the processing system is adapted to determine hardware remaining free for implementing a second look-up table after implementation of the first look-up table and to select one of the two or more mutually alternative ways to implement the second look-up table on the basis of the hardware available for implementing the second look-up table and data related to the second look-up table and indicating corresponding information as the one or more first data items and the one or more second data items indicate relating to the first look-up table. ### Claim 8 (depends on 4) A device according to claim 4, wherein the processing system is adapted to determine hardware remaining free for implementing a second look-up table after implementation of the first look-up table and to select one of the two or more mutually alternative ways to implement the second look-up table on the basis of the hardware available for implementing the second look-up table and data related to the second look-up table and indicating corresponding information as the one or more first data items and the one or more second data items indicate relating to the first look-up table. ### Claim 9 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 specifying a look-up table to be implemented in the network element, hardware for implementing the look-up table in two or more mutually alternative ways, and a device for defining implementation of the look-up table, the device comprising a processing system adapted to: receive one or more first data items providing information about one or more look-up keys of the look-up table, receive one or more second data items indicating at least one of the following: the maximum number of entries of the look-up table, an average time between successive look-ups from the look-up table, an average time between successive modifications of the look-up table, and select one of the two or more mutually alternative ways to implement the look-up table on the basis of the hardware available for implementing the look-up table, the one or more first data items, and the one or more second data items. ### Claim 10 (depends on 9) A network element according to claim 9, wherein the network element is at least one of the following: an Internet Protocol router, a multiprotocol label switching switch, a packet optical switch, an Ethernet switch. ### Claim 11 A method for defining implementation of a first look-up table for a network element of a software-defined network, the network element comprising hardware for implementing the first look-up table in two or more mutually alternative ways, the method comprising selecting one of the two or more mutually alternative ways to implement the first look-up table on the basis of the hardware available for implementing the first look-up table, one or more first data items, and one or more second data items, where: the one or more first data items provide information about one or more look-up keys of the first look-up table, and the one or more second data items indicate at least one of the following: the maximum number of entries of the first look-up table, an average time between successive look-ups from the first look-up table, an average time between successive modifications of the first look-up table. ### Claim 12 (depends on 11) A method according to claim 11, wherein the method comprises computing a weighted sum of the one or more first data items and the one or more second data items and comparing the weighted sum to a first threshold so as to make a selection between an implementation based on content access memory technology and an implementation based on a retrieval tree algorithm and random access memory technology. ### Claim 13 (depends on 11) A method according to claim 11, wherein the method comprises comparing a second threshold to a third data item indicating a ratio of the number of don't care key matching bit positions of the first look-up table to the number of all key matching bit positions of the first look-up table so as to make a selection between an implementation based on binary content access memory technology and an implementation based on ternary content access memory technology. ### Claim 14 (depends on 12) A method according to claim 12, wherein the method comprises comparing a second threshold to a third data item indicating a ratio of the number of don't care key matching bit positions of the first look-up table to the number of all key matching bit positions of the first look-up table so as to make a selection between an implementation based on binary content access memory technology and an implementation based on ternary content access memory technology. ### Claim 15 (depends on 11) A method according to claim 11, wherein the method comprises determining hardware remaining free for implementing a second look-up table after implementation of the first look-up table and selecting one of the two or more mutually alternative ways to implement the second look-up table on the basis of the hardware available for implementing the second look-up table and data related to the second look-up table and indicating corresponding information as the one or more first data items and the one or more second data items indicate relating to the first look-up table. ### Claim 16 (depends on 12) A method according to claim 12, wherein the method comprises determining hardware remaining free for implementing a second look-up table after implementation of the first look-up table and selecting one of the two or more mutually alternative ways to implement the second look-up table on the basis of the hardware available for implementing the second look-up table and data related to the second look-up table and indicating corresponding information as the one or more first data items and the one or more second data items indicate relating to the first look-up table. ### Claim 17 (depends on 13) A method according to claim 13, wherein the method comprises determining hardware remaining free for implementing a second look-up table after implementation of the first look-up table and selecting one of the two or more mutually alternative ways to implement the second look-up table on the basis of the hardware available for implementing the second look-up table and data related to the second look-up table and indicating corresponding information as the one or more first data items and the one or more second data items indicate relating to the first look-up table. ### Claim 18 A non-transitory computer readable medium encoded with a computer program for defining implementation of a look-up table for a network element of a software-defined network, the network element comprising hardware for implementing the look-up table in two or more mutually alternative ways, the computer program comprising computer executable instructions for controlling a programmable processing system to select one of the two or more mutually alternative ways to implement the look-up table on the basis of the hardware available for implementing the look-up table, one or more first data items, and one or more second data items, where: the one or more first data items provide information about one or more look-up keys of the look-up table, and the one or more second data items indicate at least one of the following: the maximum number of entries of the look-up table, an average time between successive look-ups from the look-up table, an average time between successive modifications of the look-up table. ### Claim 19 A software-defined network comprising: a controller system for transmitting configuration data to the one or more network elements so as to configure the one or more network elements, the configuration data specifying a look-up table to be implemented in the one or more network elements, and one or more network elements, wherein each of the network elements comprises: a data transfer interface for receiving data and for transmitting data, the received data specifying a look-up table to be implemented in the network element, hardware for implementing the look-up table in two or more mutually alternative ways, and a device for defining implementation of the look-up table, the device comprising a processing system adapted to: receive one or more first data items providing information about one or more look-up keys of the look-up table, receive one or more second data items indicating at least one of the following: the maximum number of entries of the look-up table, an average time between successive look-ups from the look-up table, an average time between successive modifications of the look-up table, and select one of the two or more mutually alternative ways to implement the look-up table on the basis of the hardware available for implementing the look-up table, the one or more first data items, and the one or more second data items. ### Claim 20 (depends on 19) A software-defined network according to claim 19, 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.