From patchwork Mon Jan 16 19:21:58 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: "De Lara Guarch, Pablo" X-Patchwork-Id: 19635 Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [IPv6:::1]) by dpdk.org (Postfix) with ESMTP id D3AE42BF2; Tue, 17 Jan 2017 22:02:54 +0100 (CET) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 668931094 for ; Mon, 16 Jan 2017 20:20:32 +0100 (CET) Received: from fmsmga004.fm.intel.com ([10.253.24.48]) by orsmga102.jf.intel.com with ESMTP; 16 Jan 2017 11:20:31 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.33,240,1477983600"; d="scan'208";a="214020723" Received: from silpixa00381631.ir.intel.com (HELO silpixa00381631.ger.corp.intel.com) ([10.237.222.122]) by fmsmga004.fm.intel.com with ESMTP; 16 Jan 2017 11:20:29 -0800 From: Pablo de Lara To: dev@dpdk.org Cc: Pablo de Lara , Sameh Gobriel Date: Mon, 16 Jan 2017 19:21:58 +0000 Message-Id: <1484594519-227376-5-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1484594519-227376-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1484559804-133610-1-git-send-email-pablo.de.lara.guarch@intel.com> <1484594519-227376-1-git-send-email-pablo.de.lara.guarch@intel.com> MIME-Version: 1.0 X-Mailman-Approved-At: Tue, 17 Jan 2017 22:02:41 +0100 Subject: [dpdk-dev] [PATCH v6 4/5] doc: add EFD library section in Programmers guide X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Signed-off-by: Sameh Gobriel Acked-by: Christian Maciocco --- MAINTAINERS | 1 + doc/guides/prog_guide/efd_lib.rst | 440 +++++++++++ doc/guides/prog_guide/img/efd_i1.svg | 130 ++++ doc/guides/prog_guide/img/efd_i10.svg | 384 ++++++++++ doc/guides/prog_guide/img/efd_i11.svg | 319 ++++++++ doc/guides/prog_guide/img/efd_i12.svg | 1008 +++++++++++++++++++++++++ doc/guides/prog_guide/img/efd_i2.svg | 280 +++++++ doc/guides/prog_guide/img/efd_i3.svg | 634 ++++++++++++++++ doc/guides/prog_guide/img/efd_i4.svg | 203 ++++++ doc/guides/prog_guide/img/efd_i5.svg | 183 +++++ doc/guides/prog_guide/img/efd_i6.svg | 1254 ++++++++++++++++++++++++++++++++ doc/guides/prog_guide/img/efd_i7.svg | 790 ++++++++++++++++++++ doc/guides/prog_guide/img/efd_i8.svg | 182 +++++ doc/guides/prog_guide/img/efd_i9.svg | 390 ++++++++++ doc/guides/prog_guide/index.rst | 23 + doc/guides/rel_notes/release_17_02.rst | 3 + 16 files changed, 6224 insertions(+) create mode 100644 doc/guides/prog_guide/efd_lib.rst create mode 100644 doc/guides/prog_guide/img/efd_i1.svg create mode 100644 doc/guides/prog_guide/img/efd_i10.svg create mode 100644 doc/guides/prog_guide/img/efd_i11.svg create mode 100644 doc/guides/prog_guide/img/efd_i12.svg create mode 100644 doc/guides/prog_guide/img/efd_i2.svg create mode 100644 doc/guides/prog_guide/img/efd_i3.svg create mode 100644 doc/guides/prog_guide/img/efd_i4.svg create mode 100644 doc/guides/prog_guide/img/efd_i5.svg create mode 100644 doc/guides/prog_guide/img/efd_i6.svg create mode 100644 doc/guides/prog_guide/img/efd_i7.svg create mode 100644 doc/guides/prog_guide/img/efd_i8.svg create mode 100644 doc/guides/prog_guide/img/efd_i9.svg diff --git a/MAINTAINERS b/MAINTAINERS index b124f6e..66e9466 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -532,6 +532,7 @@ EFD M: Byron Marohn M: Pablo de Lara Guarch F: lib/librte_efd/ +F: doc/guides/prog_guide/efd_lib.rst F: app/test/test_efd* F: examples/flow_distributor/ diff --git a/doc/guides/prog_guide/efd_lib.rst b/doc/guides/prog_guide/efd_lib.rst new file mode 100644 index 0000000..5b8e4e3 --- /dev/null +++ b/doc/guides/prog_guide/efd_lib.rst @@ -0,0 +1,440 @@ +.. BSD LICENSE + Copyright(c) 2016-2017 Intel Corporation. All rights reserved. + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in + the documentation and/or other materials provided with the + distribution. + * Neither the name of Intel Corporation nor the names of its + contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +.. _Efd_Library: + +Elastic Flow Distributor Library +================================ + +Introduction +------------ + +In Data Centers today, clustering and scheduling of distributed workloads +is a very common task. Many workloads require a deterministic +partitioning of a flat key space among a cluster of machines. When a +packet enters the cluster, the ingress node will direct the packet to +its handling node. For example, data-centers with disaggregated storage +use storage metadata tables to forward I/O requests to the correct back end +storage cluster, stateful packet inspection will use match incoming +flows to signatures in flow tables to send incoming packets to their +intended deep packet inspection (DPI) devices, and so on. + +EFD is a distributor library that uses perfect hashing to determine a +target/value for a given incoming flow key. It has the following +advantages: first, because it uses perfect hashing it does not store the +key itself and hence lookup performance is not dependent on the key +size. Second, the target/value can be any arbitrary value hence the +system designer and/or operator can better optimize service rates and +inter-cluster network traffic locating. Third, since the storage +requirement is much smaller than a hash-based flow table (i.e. better +fit for CPU cache), EFD can scale to millions of flow keys. Finally, +with the current optimized library implementation, performance is fully +scalable with any number of CPU cores. + +Flow Based Distribution +----------------------- + +Computation Based Schemes +~~~~~~~~~~~~~~~~~~~~~~~~~ + +Flow distribution and/or load balancing can be simply done using a +stateless computation, for instance using round-robin or a simple +computation based on the flow key as an input. For example, a hash +function can be used to direct a certain flow to a target based on +the flow key (e.g. ``h(key) mod n``) where h(key) is the hash value of the +flow key and n is the number of possible targets. + +.. _figure_efd1: + +.. figure:: img/efd_i1.* + + Load Balancing Using Front End Node + +In this scheme (:numref:`figure_efd1`), the front end server/distributor/load balancer +extracts the flow key from the input packet and applies a computation to determine where +this flow should be directed. Intuitively, this scheme is very simple +and requires no state to be kept at the front end node, and hence, +storage requirements are minimum. + +.. _figure_efd2: + +.. figure:: img/efd_i2.* + + Consistent Hashing + +A widely used flow distributor that belongs to the same category of +computation-based schemes is ``consistent hashing``, shown in :numref:`figure_efd2`. +Target destinations (shown in red) are hashed into the same space as the flow +keys (shown in blue), and keys are mapped to the nearest target in a clockwise +fashion. Dynamically adding and removing targets with consistent hashing +requires only K/n keys to be remapped on average, where K is the number of +keys, and n is the number of targets. In contrast, in a traditional hash-based +scheme, a change in the number of targets causes nearly all keys to be +remapped. + +Although computation-based schemes are simple and need very little +storage requirement, they suffer from the drawback that the system +designer/operator can’t fully control the target to assign a specific +key, as this is dictated by the hash function. +Deterministically co-locating of keys together (for example, to minimize +inter-server traffic or to optimize for network traffic conditions, +target load, etc.) is simply not possible. + +Flow-Table Based Schemes +~~~~~~~~~~~~~~~~~~~~~~~~ + +When using a Flow-Table based scheme to handle flow distribution/load +balancing, in contrast with computation-based schemes, the system designer +has the flexibility of assigning a given flow to any given +target. The flow table (e.g. DPDK RTE Hash Library) will simply store +both the flow key and the target value. + +.. _figure_efd3: + +.. figure:: img/efd_i3.* + + Table Based Flow Distribution + +As shown in :numref:`figure_efd3`, when doing a lookup, the flow-table +is indexed with the hash of the flow key and the keys (more than one is possible, +because of hash collision) stored in this index and corresponding values +are retrieved. The retrieved key(s) is matched with the input flow key +and if there is a match the value (target id) is returned. + +The drawback of using a hash table for flow distribution/load balancing +is the storage requirement, since the flow table need to store keys, +signatures and target values. This doesn't allow this scheme to scale to +millions of flow keys. Large tables will usually not fit in +the CPU cache, and hence, the lookup performance is degraded because of +the latency to access the main memory. + +EFD Based Scheme +~~~~~~~~~~~~~~~~ + +EFD combines the advantages of both flow-table based and computation-based +schemes. It doesn't require the large storage necessary for +flow-table based schemes (because EFD doesn't store the key as explained +below), and it supports any arbitrary value for any given key. + +.. _figure_efd4: + +.. figure:: img/efd_i4.* + + Searching for Perfect Hash Function + +The basic idea of EFD is when a given key is to be inserted, a family of +hash functions is searched until the correct hash function that maps the +input key to the correct value is found, as shown in :numref:`figure_efd4`. +However, rather than explicitly storing all keys and their associated values, +EFD stores only indices of hash functions that map keys to values, and +thereby consumes much less space than conventional flow-based tables. +The lookup operation is very simple, similar to a computational-based +scheme: given an input key the lookup operation is reduced to hashing +that key with the correct hash function. + +.. _figure_efd5: + +.. figure:: img/efd_i5.* + + Divide and Conquer for Millions of Keys + +Intuitively, finding a hash function that maps each of a large number +(millions) of input keys to the correct output value is effectively +impossible, as a result EFD, as shown in :numref:`figure_efd5`, +breaks the problem into smaller pieces (divide and conquer). +EFD divides the entire input key set into many small groups. +Each group consists of approximately 20-28 keys (a configurable parameter +for the library), then, for each small group, a brute force search to find +a hash function that produces the correct outputs for each key in the group. + +It should be mentioned that, since the online lookup table for EFD +doesn't store the key itself, the size of the EFD table is independent +of the key size and hence EFD lookup performance which is almost +constant irrespective of the length of the key which is a highly +desirable feature especially for longer keys. + +In summary, EFD is a set separation data structure that supports millions of +keys. It is used to distribute a given key to an intended target. By itself +EFD is not a FIB data structure with an exact match the input flow key. + +.. _Efd_example: + +Example of EFD Library Usage +---------------------------- + +EFD can be used along the data path of many network functions and middleboxes. +As previously mentioned, it can used as an index table for + pairs, meta-data for objects, a flow-level load balancer, etc. +:numref:`figure_efd6` shows an example of using EFD as a flow-level load +balancer, where flows are received at a front end server before being forwarded +to the target back end server for processing. The system designer would +deterministically co-locate flows together in order to minimize cross-server +interaction. +(For example, flows requesting certain webpage objects are co-located +together, to minimize forwarding of common objects across servers). + +.. _figure_efd6: + +.. figure:: img/efd_i6.* + + EFD as a Flow-Level Load Balancer + +As shown in :numref:`figure_efd6`, the front end server will have an EFD table that +stores for each group what is the perfect hash index that satisfies the +correct output. Because the table size is small and fits in cache (since +keys are not stored), it sustains a large number of flows (N*X, where N +is the maximum number of flows served by each back end server of the X +possible targets). + +With an input flow key, the group id is computed (for example, using +last few bits of CRC hash) and then the EFD table is indexed with the +group id to retrieve the corresponding hash index to use. Once the index +is retrieved the key is hashed using this hash function and the result +will be the intended correct target where this flow is supposed to be +processed. + +It should be noted that as a result of EFD not matching the exact key but +rather distributing the flows to a target back end node based on the +perfect hash index, a key that has not been inserted before +will be distributed to a valid target. Hence, a local table which stores +the flows served at each node is used and is +exact matched with the input key to rule out new never seen before +flows. + +.. _Efd_api: + +Library API Overview +-------------------- + +The EFD library API is created with a very similar semantics of a +hash-index or a flow table. The application creates an EFD table for a +given maximum number of flows, a function is called to insert a flow key +with a specific target value, and another function is used to retrieve +target values for a given individual flow key or a bulk of keys. + +EFD Table Create +~~~~~~~~~~~~~~~~ + +The function ``rte_efd_create()`` is used to create and return a pointer +to an EFD table that is sized to hold up to num_flows key. +The online version of the EFD table (the one that does +not store the keys and is used for lookups) will be allocated and +created in the last level cache (LLC) of the socket defined by the +online_socket_bitmask, while the offline EFD table (the one that +stores the keys and is used for key inserts and for computing the +perfect hashing) is allocated and created in the LLC of the socket +defined by offline_socket_bitmask. It should be noted, that for +highest performance the socket id should match that where the thread is +running, i.e. the online EFD lookup table should be created on the same +socket as where the lookup thread is running. + +EFD Insert and Update +~~~~~~~~~~~~~~~~~~~~~ + +The EFD function to insert a key or update a key to a new value is +``rte_efd_update()``. This function will update an existing key to +a new value (target) if the key has already been inserted +before, or will insert the pair if this key has not been inserted +before. It will return 0 upon success. It will return +``EFD_UPDATE_WARN_GROUP_FULL (1)`` if the operation is insert, and the +last available space in the key's group was just used. It will return +``EFD_UPDATE_FAILED (2)`` when the insertion or update has failed (either it +failed to find a suitable perfect hash or the group was full). The function +will return ``EFD_UPDATE_NO_CHANGE (3)`` if there is no change to the EFD +table (i.e, same value already exists). + +EFD Lookup +~~~~~~~~~~ + +To lookup a certain key in an EFD table, the function ``rte_efd_lookup()`` +is used to return the value associated with single key. +As previously mentioned, if the key has been inserted, the correct value +inserted is returned, if the key has not been inserted before, +a ‘random’ value (based on hashing of the key) is returned. +For better performance and to decrease the overhead of +function calls per key, it is always recommended to use a bulk lookup +function (simultaneous lookup of multiple keys) instead of a single key +lookup function. ``rte_efd_lookup_bulk()`` is the bulk lookup function, +that looks up num_keys simultaneously stored in the key_list and the +corresponding return values will be returned in the value_list. + +EFD Delete +~~~~~~~~~~ + +To delete a certain key in an EFD table, the function +``rte_efd_delete()`` can be used. The function returns zero upon success +when the key has been found and deleted. Socket_id is the parameter to +use to lookup the existing value, which is ideally the caller's socket id. +The previous value associated with this key will be returned +in the prev_value argument. + +.. _Efd_internals: + +Library Internals +----------------- + +This section provides the brief high-level idea and an overview +of the library internals to accompany the RFC. The intent of this +section is to explain to readers the high-level implementation of +insert, lookup and group rebalancing in the EFD library. + +Insert Function Internals +~~~~~~~~~~~~~~~~~~~~~~~~~ + +As previously mentioned the EFD divides the whole set of keys into +groups of a manageable size (e.g. 28 keys) and then searches for the +perfect hash that satisfies the intended target value for each key. EFD +stores two version of the table: + +- Offline Version (in memory): Only used for the insertion/update + operation, which is less frequent than the lookup operation. In the + offline version the exact keys for each group is stored. When a new + key is added, the hash function is updated that will satisfy the + value for the new key together with the all old keys already inserted + in this group. + +- Online Version (in cache): Used for the frequent lookup operation. In + the online version, as previously mentioned, the keys are not stored + but rather only the hash index for each group. + +.. _figure_efd7: + +.. figure:: img/efd_i7.* + + Group Assignment + +:numref:`figure_efd7` depicts the group assignment for 7 flow keys as an example. +Given a flow key, a hash function (in our implementation CRC hash) is +used to get the group id. As shown in the figure, the groups can be +unbalanced. (We highlight group rebalancing further below). + +.. _figure_efd8: + +.. figure:: img/efd_i8.* + + Perfect Hash Search - Assigned Keys & Target Value + +Focusing on one group that has four keys, :numref:`figure_efd8` depicts the search +algorithm to find the perfect hash function. Assuming that the target +value bit for the keys is as shown in the figure, then the online EFD +table will store a 16 bit hash index and 16 bit lookup table per group +per value bit. + +.. _figure_efd9: + +.. figure:: img/efd_i9.* + + Perfect Hash Search - Satisfy Target Values + +For a given keyX, a hash function ``(h(keyX, seed1) + index * h(keyX, seed2))`` +is used to point to certain bit index in the 16bit lookup_table value, +as shown in :numref:`figure_efd9`. +The insert function will brute force search for all possible values for the +hash index until a non conflicting lookup_table is found. + +.. _figure_efd10: + +.. figure:: img/efd_i10.* + + Finding Hash Index for Conflict Free lookup_table + +For example, since both key3 and key7 have a target bit value of 1, it +is okay if the hash function of both keys point to the same bit in the +lookup table. A conflict will occur if a hash index is used that maps +both Key4 and Key7 to the same index in the lookup_table, +as shown in :numref:`figure_efd10`, since their target value bit are not the same. +Once a hash index is found that produces a lookup_table with no +contradictions, this index is stored for this group. This procedure is +repeated for each bit of target value. + +Lookup Function Internals +~~~~~~~~~~~~~~~~~~~~~~~~~ + +The design principle of EFD is that lookups are much more frequent than +inserts, and hence, EFD's design optimizes for the lookups which are +faster and much simpler than the slower insert procedure (inserts are +slow, because of perfect hash search as previously discussed). + +.. _figure_efd11: + +.. figure:: img/efd_i11.* + + EFD Lookup Operation + +:numref:`figure_efd11` depicts the lookup operation for EFD. Given an input key, +the group id is computed (using CRC hash) and then the hash index for this +group is retrieved from the EFD table. Using the retrieved hash index, +the hash function ``h(key, seed1) + index *h(key, seed2)`` is used which will +result in an index in the lookup_table, the bit corresponding to this +index will be the target value bit. This procedure is repeated for each +bit of the target value. + +Group Rebalancing Function Internals +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +When discussing EFD inserts and lookups, the discussion is simplified by +assuming that a group id is simply a result of hash function. However, +since hashing in general is not perfect and will not always produce a +uniform output, this simplified assumption will lead to unbalanced +groups, i.e., some group will have more keys than other groups. +Typically, and to minimize insert time with an increasing number of keys, +it is preferable that all groups will have a balanced number of keys, so +the brute force search for the perfect hash terminates with a valid hash +index. In order to achieve this target, groups are rebalanced during +runtime inserts, and keys are moved around from a busy group to a less +crowded group as the more keys are inserted. + +.. _figure_efd12: + +.. figure:: img/efd_i12.* + + Runtime Group Rebalancing + +:numref:`figure_efd12` depicts the high level idea of group rebalancing, given an +input key the hash result is split into two parts a chunk id and 8-bit +bin id. A chunk contains 64 different groups and 256 bins (i.e. for any +given bin it can map to 4 distinct groups). When a key is inserted, the +bin id is computed, for example in :numref:`figure_efd12` bin_id=2, +and since each bin can be mapped to one of four different groups (2 bit storage), +the four possible mappings are evaluated and the one that will result in a +balanced key distribution across these four is selected the mapping result +is stored in these two bits. + + +.. _Efd_references: + +References +----------- + +1- EFD is based on collaborative research work between Intel and +Carnegie Mellon University (CMU), interested readers can refer to the paper +“Scaling Up Clustered Network Appliances with ScaleBricks;” Dong Zhou et al. +at SIGCOMM 2015 (`http://conferences.sigcomm.org/sigcomm/2015/pdf/papers/p241.pdf`) +for more information. diff --git a/doc/guides/prog_guide/img/efd_i1.svg b/doc/guides/prog_guide/img/efd_i1.svg new file mode 100644 index 0000000..7f8fcb3 --- /dev/null +++ b/doc/guides/prog_guide/img/efd_i1.svg @@ -0,0 +1,130 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Page-1 + + + Square + LB + + + + + + + + + + LB + + Sheet.3 + + + + Square.4 + Target 1 + + + + + + + + + + Target 1 + + Square.5 + Target 2 + + + + + + + + + + Target 2 + + Square.7 + Target N + + + + + + + + + + Target N + + Sheet.8 + + + + Sheet.9 + + + + Sheet.11 + + + + Sheet.12 + + + + diff --git a/doc/guides/prog_guide/img/efd_i10.svg b/doc/guides/prog_guide/img/efd_i10.svg new file mode 100644 index 0000000..d26ec61 --- /dev/null +++ b/doc/guides/prog_guide/img/efd_i10.svg @@ -0,0 +1,384 @@ + + + + + + + + + + + + + + + + + + Page-1 + + + Sheet.3 + + + + Sheet.4 + + + + Sheet.5 + Key1: Value = 0 + + + + Key1: Value = 0 + + Sheet.6 + + + + Sheet.7 + + + + Sheet.8 + Key3: Value = 1 + + + + Key3: Value = 1 + + Sheet.9 + + + + Sheet.10 + + + + Sheet.11 + Key4: Value = 0 + + + + Key4: Value = 0 + + Sheet.12 + + + + Sheet.13 + + + + Sheet.14 + Key7: Value = 1 + + + + Key7: Value = 1 + + Sheet.15 + + + + Sheet.16 + + + + Sheet.17 + + + + Sheet.18 + F + + + + F + + Sheet.19 + (key, + + + + (key, + + Sheet.20 + hash_index = + + + + hash_index = + + Sheet.21 + i) + + + + i) + + Sheet.22 + + + + Sheet.23 + + + + Sheet.24 + Key1: Position 4 + + + + Key1: Position 4 + + Sheet.25 + + + + Sheet.26 + + + + Sheet.27 + Key3: Position 6 + + + + Key3: Position 6 + + Sheet.28 + + + + Sheet.29 + + + + Sheet.30 + Key4: Position 14 + + + + Key4: Position 14 + + Sheet.31 + + + + Sheet.32 + + + + Sheet.33 + Key7: Position 14 + + + + Key7: Position 14 + + Sheet.34 + + + + Sheet.35 + + + + Sheet.36 + + + + Sheet.37 + 0000 + + + + 0000 + + Sheet.38 + 0 + + + + 0 + + Sheet.39 + 0 + + + + 0 + + Sheet.40 + 1 + + + + 1 + + Sheet.41 + 0 0000 00 + + + + 0 0000 00 + + Sheet.42 + ? + + + + ? + + Sheet.43 + 0 + + + + 0 + + Sheet.44 + + + + Sheet.45 + + + + Sheet.46 + + + + Sheet.47 + + + + Sheet.48 + + + + Sheet.49 + Values + + + + Values + + Sheet.50 + + + + Sheet.51 + + + + Sheet.52 + + + + Sheet.53 + + + + Sheet.54 + + + + Sheet.55 + + + + Sheet.56 + Lookup_table + + + + Lookup_table + + Sheet.57 + (16 bits) + + + + (16 bits) + + diff --git a/doc/guides/prog_guide/img/efd_i11.svg b/doc/guides/prog_guide/img/efd_i11.svg new file mode 100644 index 0000000..f2cc656 --- /dev/null +++ b/doc/guides/prog_guide/img/efd_i11.svg @@ -0,0 +1,319 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + Page-1 + + + Sheet.5 + + + + Sheet.6 + + + + Sheet.7 + Key + + + + Key + + Sheet.8 + + + + Sheet.9 + + + + Sheet.10 + + + + Sheet.11 + hash + + + + hash + + Sheet.12 + + + + Sheet.13 + + + + Sheet.14 + 0x0102ABCD + + + + 0x0102ABCD + + Sheet.15 + + + + Sheet.16 + + + + Sheet.17 + + + + Sheet.18 + + + + Sheet.19 + + + + Sheet.20 + + + + Sheet.21 + hash_index = + + + + hash_index = + + Sheet.22 + 38123 + + + + 38123 + + Sheet.23 + + + + Sheet.24 + + + + Sheet.25 + lookup_table = + + + + lookup_table = + + Sheet.26 + 0110 1100 0101 1101 + + + + 0110 1100 0101 1101 + + Sheet.27 + Group ID: 0x0102 + + + + Group ID: 0x0102 + + Sheet.28 + + + + Sheet.29 + + + + Sheet.30 + + + + Sheet.31 + + + + Sheet.35 + + + + Sheet.36 + + + + Sheet.37 + + + + Sheet.38 + Position = 6 + + + + Position = 6 + + Sheet.39 + + + + Sheet.41 + Apply the equation + + + + Apply the equation + + Sheet.42 + to retrieve the bit + + + + to retrieve the bit + + Sheet.43 + position in the + + + + position in the + + Sheet.44 + lookup_table + + + + lookup_table + + 1-D word balloon + Retrieve the value “0' from the specified location in the loo... + + + + + + + + + Retrieve the value “0' from the specified location in the lookup table + + Sheet.48 + F(Key, hash_index = 38123 + + + + F(Key, hash_index = 38123 + + 1-D word balloon.49 + Apply the equation to retrieve the bit position in the lookup... + + + + + + + + + Apply the equation to retrieve the bit position in the lookup_table + + Sheet.50 + + + + Sheet.51 + (Hash(key,seed1)+38123*hash(key,seed2))%16 + + + + (Hash(key,seed1)+38123*hash(key,seed2))%16 + + diff --git a/doc/guides/prog_guide/img/efd_i12.svg b/doc/guides/prog_guide/img/efd_i12.svg new file mode 100644 index 0000000..a309d58 --- /dev/null +++ b/doc/guides/prog_guide/img/efd_i12.svg @@ -0,0 +1,1008 @@ + + + + + + + + + + + + + + + + + + Page-1 + + + Sheet.3 + + + + Sheet.4 + + + + Sheet.5 + Bins + + + + Bins + + Sheet.6 + Groups + + + + Groups + + Sheet.7 + + + + Sheet.8 + + + + Sheet.9 + 0 + + + + 0 + + Sheet.10 + + + + Sheet.11 + Chunks + + + + Chunks + + Sheet.12 + + + + Sheet.13 + + + + Sheet.14 + 1 + + + + 1 + + Sheet.15 + + + + Sheet.16 + + + + Sheet.17 + … + + + + … + + Sheet.18 + + + + Sheet.19 + + + + Sheet.20 + variable + + + + variable + + Sheet.21 + # of + + + + # of + + Sheet.22 + chunks + + + + chunks + + Sheet.23 + (power + + + + (power + + Sheet.24 + of 2) + + + + of 2) + + Sheet.25 + + + + Sheet.26 + + + + Sheet.27 + + + + Sheet.28 + + + + Sheet.29 + + + + Sheet.30 + + + + Sheet.31 + + + + Sheet.32 + + + + Sheet.33 + + + + Sheet.34 + + + + Sheet.35 + + + + Sheet.36 + + + + Sheet.37 + + + + Sheet.38 + + + + Sheet.39 + + + + Sheet.40 + + + + Sheet.41 + + + + Sheet.42 + + + + Sheet.43 + 0 + + + + 0 + + Sheet.44 + 4 + + + + 4 + + Sheet.45 + + + + Sheet.46 + + + + Sheet.47 + 1 + + + + 1 + + Sheet.48 + + + + Sheet.49 + + + + Sheet.50 + 2 + + + + 2 + + Sheet.51 + 3 + + + + 3 + + Sheet.52 + +1 + + + + +1 + + Sheet.53 + + + + Sheet.54 + + + + Sheet.55 + 3 + + + + 3 + + Sheet.56 + + + + Sheet.57 + + + + Sheet.58 + 4 + + + + 4 + + Sheet.59 + 0 + + + + 0 + + Sheet.60 + + + + Sheet.61 + + + + Sheet.62 + 5 + + + + 5 + + Sheet.63 + + + + Sheet.64 + + + + Sheet.65 + 6 + + + + 6 + + Sheet.66 + + + + Sheet.67 + + + + Sheet.68 + 7 + + + + 7 + + Sheet.69 + 2 + + + + 2 + + Sheet.70 + + + + Sheet.71 + + + + Sheet.72 + 8 + + + + 8 + + Sheet.73 + + + + Sheet.74 + + + + Sheet.75 + 9 + + + + 9 + + Sheet.76 + + + + Sheet.77 + + + + Sheet.78 + 10 + + + + 10 + + Sheet.79 + 1 + + + + 1 + + Sheet.80 + + + + Sheet.81 + + + + Sheet.82 + 11 + + + + 11 + + Sheet.83 + + + + Sheet.84 + + + + Sheet.85 + 12 + + + + 12 + + Sheet.86 + + + + Sheet.87 + + + + Sheet.88 + … + + + + … + + Sheet.89 + + + + Sheet.90 + + + + Sheet.91 + 255 + + + + 255 + + Sheet.92 + + + + Sheet.93 + + + + Sheet.94 + + + + Sheet.95 + + + + Sheet.96 + + + + Sheet.97 + + + + Sheet.98 + + + + Sheet.99 + … + + + + … + + Sheet.100 + + + + Sheet.101 + + + + Sheet.102 + 5 + + + + 5 + + Sheet.103 + + + + Sheet.104 + + + + Sheet.105 + 4 + + + + 4 + + Sheet.106 + 2 + + + + 2 + + Sheet.107 + 4 + + + + 4 + + Sheet.108 + 10 + + + + 10 + + Sheet.109 + 1 + + + + 1 + + Sheet.110 + +4 + + + + +4 + + Sheet.111 + + + + Sheet.112 + + + + Sheet.113 + 3 + + + + 3 + + Sheet.114 + + + + Sheet.115 + + + + Sheet.116 + 1 + + + + 1 + + Sheet.117 + 2 + + + + 2 + + Sheet.118 + + + + Sheet.119 + 7 + + + + 7 + + Sheet.120 + 5 + + + + 5 + + Sheet.121 + - + + + + - + + Sheet.122 + 3 + + + + 3 + + Sheet.123 + + + + Sheet.124 + + + + Sheet.125 + 0 + + + + 0 + + Sheet.126 + 0 + + + + 0 + + Sheet.127 + 4 + + + + 4 + + Sheet.128 + + + + Sheet.129 + + + + Sheet.130 + 64 + + + + 64 + + Sheet.131 + 96 + + + + 96 + + Sheet.132 + 7 + + + + 7 + + Sheet.133 + + + + Sheet.134 + + + + Sheet.135 + 6 + + + + 6 + + Sheet.136 + 98 + + + + 98 + + Sheet.137 + 5 + + + + 5 + + Sheet.138 + + + + Sheet.139 + + + + Sheet.140 + 2 + + + + 2 + + Sheet.141 + 99 + + + + 99 + + Sheet.142 + 9 + + + + 9 + + Sheet.143 + + + + Sheet.144 + + + + Sheet.145 + 7 + + + + 7 + + Sheet.146 + 97 + + + + 97 + + Sheet.147 + 6 + + + + 6 + + Sheet.148 + + + + Sheet.149 + + + + Sheet.150 + Insert key + + + + Insert key + + Sheet.151 + + + + Sheet.152 + + + + Sheet.153 + + + + Sheet.154 + hash + + + + hash + + Sheet.155 + + + + Sheet.156 + + + + Sheet.157 + 0x0102ABCD + + + + 0x0102ABCD + + Sheet.158 + + + + Sheet.159 + + + + Sheet.160 + + + + Sheet.161 + + + + Sheet.162 + chunk id + + + + chunk id + + Sheet.163 + + + + Sheet.164 + bin id + + + + bin id + + Sheet.165 + + + + Sheet.166 + + + + Sheet.167 + + + + Sheet.168 + + + + Sheet.169 + + + + Sheet.170 + Move bin from group 1 to 4 + + + + Move bin from group 1 to 4 + + diff --git a/doc/guides/prog_guide/img/efd_i2.svg b/doc/guides/prog_guide/img/efd_i2.svg new file mode 100644 index 0000000..a5f43f9 --- /dev/null +++ b/doc/guides/prog_guide/img/efd_i2.svg @@ -0,0 +1,280 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Page-1 + + + Circle + + + + + + + + + + Circle.3 + + + + + + + + + + Circle.4 + + + + + + + + + + Circle.5 + + + + + + + + + + Circle.6 + + + + + + + + + + Circle.7 + + + + + + + + + + Circle.8 + + + + + + + + + + Circle.9 + + + + + + + + + + Circle.10 + + + + + + + + + + Circle.11 + + + + + + + + + + Circle.12 + + + + + + + + + + Circle.13 + + + + + + + + + + Circle.14 + + + + + + + + + + Circle.15 + + + + + + + + + + Circle.16 + + + + + + + + + + Circle.17 + + + + + + + + + + Ellipse + + + + + + + + + + Sheet.19 + + + + Sheet.20 + Target Hashed Value + + + + Target Hashed Value + + Sheet.21 + + + + Sheet.23 + Keys + + + + Keys + + Sheet.24 + + + + diff --git a/doc/guides/prog_guide/img/efd_i3.svg b/doc/guides/prog_guide/img/efd_i3.svg new file mode 100644 index 0000000..ae22903 --- /dev/null +++ b/doc/guides/prog_guide/img/efd_i3.svg @@ -0,0 +1,634 @@ + + + + + + + + + + + + + + + + + + + + + + + Page-1 + + + + Rectangle + Packet Header + + + + + + + + + + Packet Header + + Rectangle.3 + Payload + + + + + + + + + + Payload + + Rectangle.4 + Flow Key + + + + + + + + + + Flow Key + + Sheet.5 + + + + Sheet.8 + Fields of the packet are used to form a flow Key + + + + Fields of the packet are used to form a flow Key + + Sheet.13 + + Trapezoid + + + + + + + + + + Sheet.12 + H(..) + + + + H(..) + + + Simple Arrow + + + + + + + + + + + Sheet.15 + Hash function is used to create a flow table index + + + + Hash function is used to create a flow table index + + Rectangle.58 + Key 1 + + + + + + + + + + Key 1 + + Rectangle.59 + Action 1 + + + + + + + + + + Action 1 + + Rectangle.60 + Key 2 + + + + + + + + + + Key 2 + + Rectangle.61 + Action 2 + + + + + + + + + + Action 2 + + Rectangle.62 + + + + + + + + + + Rectangle.63 + + + + + + + + + + Rectangle.64 + + + + + + + + + + Rectangle.65 + + + + + + + + + + Rectangle.66 + + + + + + + + + + Rectangle.67 + + + + + + + + + + Rectangle.68 + + + + + + + + + + Rectangle.69 + + + + + + + + + + Rectangle.70 + Key x + + + + + + + + + + Key x + + Rectangle.71 + Action x + + + + + + + + + + Action x + + Rectangle.72 + Key y + + + + + + + + + + Key y + + Rectangle.73 + Action y + + + + + + + + + + Action y + + Rectangle.74 + Key z + + + + + + + + + + Key z + + Rectangle.75 + Action z + + + + + + + + + + Action z + + Rectangle.76 + + + + + + + + + + Rectangle.77 + + + + + + + + + + Rectangle.78 + + + + + + + + + + Rectangle.79 + + + + + + + + + + Rectangle.80 + Key N + + + + + + + + + + Key N + + Rectangle.81 + Action N + + + + + + + + + + Action N + + Rectangle.82 + + + + + + + + + + Sheet.83 + + + + Sheet.84 + Load Balancing Flow Table + + + + Load Balancing Flow Table + + Rectangle.85 + + + + + + + + + + Sheet.86 + + + + Sheet.87 + Hash value used to index Flow table + + + + Hash value used to index Flow table + + Sheet.88 + + + + Sheet.89 + + + + Rectangle.90 + Key x + + + + + + + + + + Key x + + Rectangle.91 + Key z + + + + + + + + + + Key z + + Sheet.96 + + Trapezoid + + + + + + + + + + Sheet.98 + Match + + + + Match + + + Sheet.99 + + + + Sheet.100 + + + + Sheet.101 + + + + Rectangle.102 + Key y + + + + + + + + + + Key y + + Rectangle.103 + Flow Key + + + + + + + + + + Flow Key + + Sheet.104 + + + + Sheet.105 + Retrieved keys are matched with input key + + + + Retrieved keys are matched with input key + + Rectangle.106 + Action + + + + + + + + + + Action + + Simple Arrow.111 + + + + + + + + + + + diff --git a/doc/guides/prog_guide/img/efd_i4.svg b/doc/guides/prog_guide/img/efd_i4.svg new file mode 100644 index 0000000..5be5ccd --- /dev/null +++ b/doc/guides/prog_guide/img/efd_i4.svg @@ -0,0 +1,203 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Page-1 + + + Sheet.2 + Key 1 Key 2 ... Key 28 + + + + Key 1Key 2...Key 28 + + Sheet.9 + Target Value + + + + Target Value + + Sheet.11 + 0 1 0 + + + + 010 + + Sheet.8 + + + + Sheet.10 + + + + Sheet.4 + + + + Sheet.5 + + + + Sheet.6 + + + + Sheet.7 + + + + Sheet.12 + 0 0 0 + + + + 000 + + Sheet.26 + H1(x) + + + + H1(x) + + Sheet.27 + 1 1 0 + + + + 110 + + Sheet.28 + H2(x) + + + + H2(x) + + Sheet.29 + 0 1 0 + + + + 010 + + Sheet.30 + Hm(x) + + + + Hm(x) + + Sheet.31 + ….. + + + + ….. + + Sheet.32 + Store m for this group of keys + + + + + + + Store m for this group of keys + + Sheet.36 + + + + Sheet.44 + + Sheet.42 + + + + Sheet.43 + + + + + Sheet.45 + + Sheet.46 + + + + Sheet.47 + + + + + diff --git a/doc/guides/prog_guide/img/efd_i5.svg b/doc/guides/prog_guide/img/efd_i5.svg new file mode 100644 index 0000000..b6540ba --- /dev/null +++ b/doc/guides/prog_guide/img/efd_i5.svg @@ -0,0 +1,183 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Page-1 + + + Rectangle + All Keys + + + + + + + + + + All Keys + + Rectangle.3 + Group 1 + + + + + + + + + + Group 1 + + Rectangle.4 + Group 2 + + + + + + + + + + Group 2 + + Rectangle.5 + Group 3 + + + + + + + + + + Group 3 + + Rectangle.6 + Group X + + + + + + + + + + Group X + + Sheet.7 + + + + Sheet.8 + + + + Sheet.9 + + + + Sheet.10 + + + + Sheet.11 + + + + Sheet.12 + H7 + + + + H7 + + Sheet.13 + H267 + + + + H267 + + Sheet.14 + H46 + + + + H46 + + Sheet.15 + H132 + + + + H132 + + Sheet.16 + Store hash function index for each group of keys + + + + Store hash function index for each group of keys + + diff --git a/doc/guides/prog_guide/img/efd_i6.svg b/doc/guides/prog_guide/img/efd_i6.svg new file mode 100644 index 0000000..9aee30b --- /dev/null +++ b/doc/guides/prog_guide/img/efd_i6.svg @@ -0,0 +1,1254 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Page-1 + + + Rectangle.58 + Key 1 + + + + + + + + + + Key 1 + + Rectangle.59 + Action 1 + + + + + + + + + + Action 1 + + Rectangle.60 + Key 2 + + + + + + + + + + Key 2 + + Rectangle.61 + Action 2 + + + + + + + + + + Action 2 + + Rectangle.62 + + + + + + + + + + Rectangle.63 + + + + + + + + + + Rectangle.64 + + + + + + + + + + Rectangle.65 + + + + + + + + + + Rectangle.66 + + + + + + + + + + Rectangle.67 + + + + + + + + + + Rectangle.68 + + + + + + + + + + Rectangle.69 + + + + + + + + + + Rectangle.70 + Key x + + + + + + + + + + Key x + + Rectangle.71 + Action x + + + + + + + + + + Action x + + Rectangle.72 + Key y + + + + + + + + + + Key y + + Rectangle.73 + Action y + + + + + + + + + + Action y + + Rectangle.74 + Key z + + + + + + + + + + Key z + + Rectangle.75 + Action z + + + + + + + + + + Action z + + Rectangle.76 + + + + + + + + + + Rectangle.77 + + + + + + + + + + Rectangle.78 + + + + + + + + + + Rectangle.79 + + + + + + + + + + Rectangle.80 + Key N + + + + + + + + + + Key N + + Rectangle.81 + Action N + + + + + + + + + + Action N + + Rectangle.82 + + + + + + + + + + Sheet.28 + Local Table for N Specific Flows Serviced at Node 1 + + + + Local Table for N Specific Flows Serviced at Node 1 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Load balancer + + Sheet.35 + + + + + + + + + + + Sheet.36 + + + + + + + + Rectangle + + + + + + + + + + Sheet.38 + EFD Table + + + + EFD Table + + Rectangle.39 + Group_id + + + + + + + + + + Group_id + + Rectangle.40 + Hash index + + + + + + + + + + Hash index + + Rectangle.41 + + + + + + + + + + Rectangle.42 + + + + + + + + + + Rectangle.43 + + + + + + + + + + Rectangle.44 + + + + + + + + + + Rectangle.45 + + + + + + + + + + Rectangle.46 + + + + + + + + + + Sheet.47 + + + + Sheet.48 + Supports X*N Flows + + + + Supports X*N Flows + + Sheet.49 + Frontend Server or Load Balancer + + + + Frontend Serveror Load Balancer + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Server + + Sheet.52 + + + + + + + Sheet.53 + + + + + + + Sheet.54 + + + + + + + + + + + + Sheet.59 + + + + Sheet.60 + Backend Server 1 + + + + Backend Server 1 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Server.61 + + Sheet.62 + + + + + + + Sheet.63 + + + + + + + Sheet.64 + + + + + + + + + + + + Sheet.65 + Backend Server 2 + + + + Backend Server 2 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Server.66 + + Sheet.67 + + + + + + + Sheet.68 + + + + + + + Sheet.69 + + + + + + + + + + + + Sheet.70 + Backend Server X + + + + Backend Server X + + Sheet.71 + + + + Sheet.72 + + + + Rectangle.73 + Key 1 + + + + + + + + + + Key 1 + + Rectangle.74 + Action 1 + + + + + + + + + + Action 1 + + Rectangle.75 + Key 2 + + + + + + + + + + Key 2 + + Rectangle.76 + Action 2 + + + + + + + + + + Action 2 + + Rectangle.77 + + + + + + + + + + Rectangle.78 + + + + + + + + + + Rectangle.79 + + + + + + + + + + Rectangle.80 + + + + + + + + + + Rectangle.81 + + + + + + + + + + Rectangle.82 + + + + + + + + + + Rectangle.83 + + + + + + + + + + Rectangle.84 + + + + + + + + + + Rectangle.85 + Key x + + + + + + + + + + Key x + + Rectangle.86 + Action x + + + + + + + + + + Action x + + Rectangle.87 + Key y + + + + + + + + + + Key y + + Rectangle.88 + Action y + + + + + + + + + + Action y + + Rectangle.89 + Key z + + + + + + + + + + Key z + + Rectangle.90 + Action z + + + + + + + + + + Action z + + Rectangle.91 + + + + + + + + + + Rectangle.92 + + + + + + + + + + Rectangle.93 + + + + + + + + + + Rectangle.94 + + + + + + + + + + Rectangle.95 + Key N + + + + + + + + + + Key N + + Rectangle.96 + Action N + + + + + + + + + + Action N + + Rectangle.97 + + + + + + + + + + Sheet.98 + Local Table for N Specific Flows Serviced at Node X + + + + Local Table for N Specific Flows Serviced at Node X + + Sheet.99 + + + + Sheet.100 + + + + Sheet.101 + + + + Sheet.102 + Supports N Flows + + + + Supports N Flows + + diff --git a/doc/guides/prog_guide/img/efd_i7.svg b/doc/guides/prog_guide/img/efd_i7.svg new file mode 100644 index 0000000..98f8000 --- /dev/null +++ b/doc/guides/prog_guide/img/efd_i7.svg @@ -0,0 +1,790 @@ + + + + + + + + + + + + + + + + + + + + + + + Page-1 + + + Sheet.3 + + + + Sheet.4 + + + + Sheet.5 + Key1 + + + + Key1 + + Sheet.6 + + + + Sheet.7 + + + + Sheet.8 + + + + Sheet.9 + hash + + + + hash + + Sheet.10 + + + + Sheet.11 + + + + Sheet.12 + 0x0102ABCD + + + + 0x0102ABCD + + Sheet.13 + + + + Sheet.14 + + + + Sheet.15 + + + + Sheet.16 + + + + Sheet.17 + Key2 + + + + Key2 + + Sheet.18 + + + + Sheet.19 + + + + Sheet.20 + + + + Sheet.21 + hash + + + + hash + + Sheet.22 + + + + Sheet.23 + + + + Sheet.24 + 0x0103CDAB + + + + 0x0103CDAB + + Sheet.25 + + + + Sheet.26 + + + + Sheet.27 + + + + Sheet.28 + + + + Sheet.29 + Key3 + + + + Key3 + + Sheet.30 + + + + Sheet.31 + + + + Sheet.32 + + + + Sheet.33 + hash + + + + hash + + Sheet.34 + + + + Sheet.35 + + + + Sheet.36 + 0x0102BAAD + + + + 0x0102BAAD + + Sheet.37 + + + + Sheet.38 + + + + Sheet.39 + + + + Sheet.40 + + + + Sheet.41 + Key4 + + + + Key4 + + Sheet.42 + + + + Sheet.43 + + + + Sheet.44 + + + + Sheet.45 + hash + + + + hash + + Sheet.46 + + + + Sheet.47 + + + + Sheet.48 + 0x0104BEEF + + + + 0x0104BEEF + + Sheet.49 + + + + Sheet.50 + + + + Sheet.51 + + + + Sheet.52 + + + + Sheet.53 + Key5 + + + + Key5 + + Sheet.54 + + + + Sheet.55 + + + + Sheet.56 + + + + Sheet.57 + hash + + + + hash + + Sheet.58 + + + + Sheet.59 + + + + Sheet.60 + 0x0103DABD + + + + 0x0103DABD + + Sheet.61 + + + + Sheet.62 + + + + Sheet.63 + + + + Sheet.64 + + + + Sheet.65 + Key6 + + + + Key6 + + Sheet.66 + + + + Sheet.67 + + + + Sheet.68 + + + + Sheet.69 + hash + + + + hash + + Sheet.70 + + + + Sheet.71 + + + + Sheet.72 + 0x0102ADCB + + + + 0x0102ADCB + + Sheet.73 + + + + Sheet.74 + + + + Sheet.75 + + + + Sheet.76 + + + + Sheet.77 + Key7 + + + + Key7 + + Sheet.78 + + + + Sheet.79 + + + + Sheet.80 + + + + Sheet.81 + hash + + + + hash + + Sheet.82 + + + + Sheet.83 + + + + Sheet.84 + 0x0104DBCA + + + + 0x0104DBCA + + Sheet.85 + + + + Sheet.86 + + + + Sheet.87 + + + + Sheet.88 + + + + Sheet.89 + 0x0102 + + + + 0x0102 + + Sheet.90 + 4 + + + + 4 + + Sheet.91 + + + + Sheet.92 + + + + Sheet.93 + 0x0103 + + + + 0x0103 + + Sheet.94 + 2 + + + + 2 + + Sheet.95 + + + + Sheet.96 + + + + Sheet.97 + 0x0104 + + + + 0x0104 + + Sheet.98 + 1 + + + + 1 + + Sheet.99 + + + + Sheet.100 + + + + Sheet.101 + + + + Sheet.102 + + + + Sheet.103 + + + + Sheet.104 + + + + Sheet.105 + + + + Sheet.106 + + + + Sheet.109 + + + + Sheet.110 + Groups + + + + Groups + + Sheet.111 + + + + Sheet.112 + group id + + + + group id + + Sheet.114 + - + + + + - + + Sheet.115 + Keys separated into + + + + Keys separated into + + Sheet.116 + groups based on + + + + groups based on + + Sheet.117 + some bits from hash + + + + some bits from hash + + Sheet.118 + - + + + + - + + Sheet.119 + Groups contain a + + + + Groups contain a + + Sheet.120 + small number of + + + + small number of + + Sheet.121 + keys (<28) + + + + keys (<28) + + Sheet.122 + + + + Sheet.123 + Group + + + + Group + + Sheet.124 + Identifier + + + + Identifier + + Sheet.125 + (simplified) + + + + (simplified) + + Sheet.127 + Keys separated into groups based on some bits from hash. Grou... + + + + + + + · Keys separated into groups based on some bits from hash.· Groups contain a small number of keys (<28) + + Sheet.129 + Total # of keys in group so far + + + + Total # of keys in group so far + + diff --git a/doc/guides/prog_guide/img/efd_i8.svg b/doc/guides/prog_guide/img/efd_i8.svg new file mode 100644 index 0000000..d0fd463 --- /dev/null +++ b/doc/guides/prog_guide/img/efd_i8.svg @@ -0,0 +1,182 @@ + + + + + + + + + + + + + + + + + + Page-2 + + + Sheet.4 + + + + Sheet.5 + + + + Sheet.6 + + + + Sheet.7 + + + + Sheet.8 + hash_index + + + + hash_index + + Sheet.9 + (integer, 16 bits) + + + + (integer, 16 bits) + + Sheet.10 + + + + Sheet.11 + + + + Sheet.12 + lookup_table + + + + lookup_table + + Sheet.13 + (16 bits) + + + + (16 bits) + + Sheet.14 + Group ID: 0x0102 + + + + Group ID: 0x0102 + + Sheet.15 + + + + Sheet.16 + + + + Sheet.17 + Key1: Value = 0 + + + + Key1: Value = 0 + + Sheet.18 + + + + Sheet.19 + + + + Sheet.20 + Key3: Value = 1 + + + + Key3: Value = 1 + + Sheet.21 + + + + Sheet.22 + + + + Sheet.23 + Key4: Value = 0 + + + + Key4: Value = 0 + + Sheet.24 + + + + Sheet.25 + + + + Sheet.26 + Key7: Value = 1 + + + + Key7: Value = 1 + + Sheet.27 + + + + diff --git a/doc/guides/prog_guide/img/efd_i9.svg b/doc/guides/prog_guide/img/efd_i9.svg new file mode 100644 index 0000000..b2e385d --- /dev/null +++ b/doc/guides/prog_guide/img/efd_i9.svg @@ -0,0 +1,390 @@ + + + + + + + + + + + + + + + + + + Page-1 + + + Sheet.68 + + + + Sheet.69 + + + + Sheet.70 + (hash(key, seed1) + hash_index * + + + + (hash(key, seed1) + hash_index * + + Sheet.71 + hash(key + + + + hash(key + + Sheet.72 + , seed2)) % 16 + + + + , seed2)) % 16 + + Sheet.73 + + + + Sheet.74 + + + + Sheet.75 + + + + Sheet.76 + lookup_table + + + + lookup_table + + Sheet.77 + bit + + + + bit + + Sheet.78 + index for key1 + + + + index for key1 + + Sheet.79 + + + + Sheet.80 + + + + Sheet.81 + lookup_table + + + + lookup_table + + Sheet.82 + bit + + + + bit + + Sheet.83 + index for key3 + + + + index for key3 + + Sheet.84 + + + + Sheet.85 + + + + Sheet.86 + lookup_table + + + + lookup_table + + Sheet.87 + bit + + + + bit + + Sheet.88 + index for key4 + + + + index for key4 + + Sheet.89 + + + + Sheet.90 + + + + Sheet.91 + lookup_table + + + + lookup_table + + Sheet.92 + bit + + + + bit + + Sheet.93 + index for key7 + + + + index for key7 + + Sheet.94 + + + + Sheet.95 + CRC32 (32 + + + + CRC32 (32 + + Sheet.96 + bit output) + + + + bit output) + + Sheet.97 + + + + Sheet.98 + Goal: Find a valid + + + + Goal: Find a valid + + Sheet.99 + hash_index + + + + hash_index + + Sheet.100 + + + + Sheet.101 + Lookup Table has + + + + Lookup Table has + + Sheet.102 + 16 bits + + + + 16 bits + + Sheet.103 + + + + Sheet.104 + CRC32 (32 + + + + CRC32 (32 + + Sheet.105 + bit output) + + + + bit output) + + Sheet.106 + + + + Sheet.107 + Goal is to find a hash_index that produces + + + + Goal is to find a hash_index that produces + + Sheet.108 + a lookup_table with no contradictions + + + + a lookup_table with no contradictions + + Sheet.109 + + + + Sheet.110 + + + + Sheet.111 + Key1: Value = 0 + + + + Key1: Value = 0 + + Sheet.112 + + + + Sheet.113 + + + + Sheet.114 + Key3: Value = 1 + + + + Key3: Value = 1 + + Sheet.115 + + + + Sheet.116 + + + + Sheet.117 + Key4: Value = 0 + + + + Key4: Value = 0 + + Sheet.118 + + + + Sheet.119 + + + + Sheet.120 + Key7: Value = 1 + + + + Key7: Value = 1 + + Sheet.121 + + + + diff --git a/doc/guides/prog_guide/index.rst b/doc/guides/prog_guide/index.rst index ed7f770..7f825cb 100644 --- a/doc/guides/prog_guide/index.rst +++ b/doc/guides/prog_guide/index.rst @@ -47,6 +47,7 @@ Programmer's Guide link_bonding_poll_mode_drv_lib timer_lib hash_lib + efd_lib lpm_lib lpm6_lib packet_distrib_lib @@ -167,6 +168,28 @@ Programmer's Guide :numref:`figure_figure39` :ref:`figure_figure39` +:numref:`figure_efd1` :ref:`figure_efd1` + +:numref:`figure_efd2` :ref:`figure_efd2` + +:numref:`figure_efd3` :ref:`figure_efd3` + +:numref:`figure_efd4` :ref:`figure_efd4` + +:numref:`figure_efd5` :ref:`figure_efd5` + +:numref:`figure_efd6` :ref:`figure_efd6` + +:numref:`figure_efd7` :ref:`figure_efd7` + +:numref:`figure_efd8` :ref:`figure_efd8` + +:numref:`figure_efd9` :ref:`figure_efd9` + +:numref:`figure_efd10` :ref:`figure_efd10` + +:numref:`figure_efd11` :ref:`figure_efd11` + **Tables** diff --git a/doc/guides/rel_notes/release_17_02.rst b/doc/guides/rel_notes/release_17_02.rst index 8673d22..7dff3a2 100644 --- a/doc/guides/rel_notes/release_17_02.rst +++ b/doc/guides/rel_notes/release_17_02.rst @@ -68,6 +68,9 @@ New Features is much smaller than a hash-based flow table and therefore, it can better fit for CPU cache, being able to scale to millions of flow keys. + See the :ref:`Elastic Flow Distributor Library ` documentation in + the Programmers Guide document, for more information. + Resolved Issues ---------------