From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm1-f67.google.com (mail-wm1-f67.google.com [209.85.128.67]) by dpdk.org (Postfix) with ESMTP id D445B160 for ; Wed, 3 Oct 2018 00:02:46 +0200 (CEST) Received: by mail-wm1-f67.google.com with SMTP id 193-v6so3632592wme.3 for ; Tue, 02 Oct 2018 15:02:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=6wind-com.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:content-transfer-encoding:in-reply-to :user-agent; bh=r7MRywZrJ4Hq5TOOpExSq+hmTDvK6XAxi6Cu4YHZmgs=; b=QABfWCSGcjaNnHvPTZSgQafcvg4BqwmBIvaR/7XMdjl1bumaR94rJEz6KlHBm+PKkz 5C7M8zKuk1GDh/fAV7K30VKsaa5q7/Z4d6sVAdcT5d+b55dF73gvtQIkxeCKp3hUnE9u 2djGOhTGAsBtqGj1/ftPuFv6GcY2m7UHypk9CWxLWO+LF1/dzoxHGbE3xk96OJiqAukA tM418eR3htSuWdf5+jC1e1dlxP3cZA7DepzokrMsdAV4KTfJVOZJnNFozAW413Wwaxjk Ru4Wpk4hmvb8516+zJrKZsR8kwMliapD/9rig6xduBTIUOxEcfqeD1Q1cV5Ll4cdh600 MakQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:content-transfer-encoding :in-reply-to:user-agent; bh=r7MRywZrJ4Hq5TOOpExSq+hmTDvK6XAxi6Cu4YHZmgs=; b=KjFzaC6pTdtx5kbIy6w2ttRfPvfubkyrfPtzo//N3vI6aaQwpCMs3wxOZ+KGMTidZm rDnCo2/SRWoEFCcjimpYSWEFQxHXh2EOAtl3Z3mXiFlYV+BTpy07Bew92KnR8ACHFItp jT4QjiwQXO/nbHgO1feVDwqRf1UgnTKH0f0ghb9wfzX8mxKMGxG3CB4qPDP7lXPjITRK pBOEFy+Za+ZhY4iiT4QJpHkWZdAQ3gKCywtT75LENj5P1/qwh2YCTWgcCCIvOMJJpljd yI14X6sXEibul4RImfPclpQLpD8r02khsux4t7XTKu7AXJZoMVsJqvzFSvfvddUWEONZ RDCQ== X-Gm-Message-State: ABuFfohbsHXsO1MgjAJuAA+pvOHNgj/gBnKvr4JxP7NWkQrXn6Abez4j /Vef7BwMYmJRINuAX0aSBCO2/w== X-Google-Smtp-Source: ACcGV615yLgfiT2X6t7X+YpMB+xUo6LzocUWyAlTteI8IaQpWc39x+I4Ki1eeFKXDxjgLkl2x5Mruw== X-Received: by 2002:a1c:ed1a:: with SMTP id l26-v6mr3201664wmh.61.1538517766001; Tue, 02 Oct 2018 15:02:46 -0700 (PDT) Received: from bidouze.vm.6wind.com (host.78.145.23.62.rev.coltfrance.com. [62.23.145.78]) by smtp.gmail.com with ESMTPSA id 185-v6sm17107270wmy.38.2018.10.02.15.02.44 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Tue, 02 Oct 2018 15:02:44 -0700 (PDT) Date: Wed, 3 Oct 2018 00:02:27 +0200 From: =?iso-8859-1?Q?Ga=EBtan?= Rivet To: Ali Volkan Atli Cc: Pavel Chuprikov , "users@dpdk.org" Message-ID: <20181002220227.5frhmua25b36ibk5@bidouze.vm.6wind.com> References: <16bf9ae8c8b34297b76018c92f910c29@MX1.argela.com.tr> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <16bf9ae8c8b34297b76018c92f910c29@MX1.argela.com.tr> User-Agent: NeoMutt/20170113 (1.7.2) Subject: Re: [dpdk-users] How to find an IPv4 and IPv6 hash function X-BeenThere: users@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK usage discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 02 Oct 2018 22:02:49 -0000 Hi Ali, Routing will generally perform the same operation, matching IP addresses and gathering results marked for these addresses. Usually, hashing is done to map large sets to a limited number of buckets. It works well at scale for choosing RX queues, but you will have poor data locality in a naive hash-table, as it would usually be implemented with a linked-list. You could then either design a hash-table with good data-locality even with a lot of collisions, but it would probably be simpler to use a trie, as you suggested I think by referencing dynamic arrays. You did not say whether your monitoring was done on src or dst addresses, but if you suggest using a trie, I assume you are only using one and not both. If you need to match both, then you will be better off by hashing the addresses and taking care of data locality in your hash-table. Otherwise, you will find an extensive litterature going back decades on matching IP addresses, this has been studied for a long time now. The classic solution is generally a trie if you only need to match one IP address, with path-compression used to avoid using too much memory, which will kill performances if you do a lot of insertion and deletion in your trie. So you need to know how long those entries will be live in your monitor and how often they would disappear. If you are never removing any, path compression seems a good point to start. You can look into librte_lpm. I have never used it, but "Longest Prefix Match" is referring to the operation of matching an IP address. On Tue, Oct 02, 2018 at 07:20:39PM +0000, Ali Volkan Atli wrote: > > First of all, thanks you Pavel > > Actually I didn't ask the question properly. I have already used the l3fwd application as basis for 5-tuple "flows" in my application. Now I just need a data structure to keep 32-bit IPv4 address or 128-bit IPv6 address, just one IP address. I can use jenkins hash, murmurhash, fast fibonacci etc.. Also I have just found out that DPDK has the jenkins hash functions. Before asking the question to this e-mail group, I was thinking of why I did not use a dynamic array for 32-bit IPv4 address instead of hash table. Thus I could fetch the data in one shot. It still makes sense but of course it doesn't work for IPv6. Anyway I asked the question here because DPDK library designed for network and maybe someone could suggest a paper, blog, a DPDK API for just one IP-based data-structure. > > I apologize if the e-mail group is the wrong place. > > Best regards > > - Volkan > > ________________________________________ > From: Pavel Chuprikov [pschuprikov@gmail.com] > Sent: Tuesday, October 2, 2018 8:32 PM > To: Ali Volkan Atli > Cc: users@dpdk.org > Subject: Re: [dpdk-users] How to find an IPv4 and IPv6 hash function > > Hi, > > The l3fwd application [1] might serve as a starting point and in particular l3fwd_em.c [2]. > > [1]: http://doc.dpdk.org/guides/sample_app_ug/l3_forward.html > [2]: http://doc.dpdk.org/api/examples_2l3fwd_2l3fwd_em_8c-example.html > > Hope it helps, > Pavel > > пн, 1 окт. 2018 г. в 14:37, Ali Volkan Atli >: > Dear DPDK users > > I am trying to write a code to monitor user data traffic by using DPDK. Each user has one IP address which can be IPv4 or IPv6. Therefore I'm thinking of creating two hash tables for IPv4 and IPv6. The key of these hash tables will be an IPv4 or IPv6 address and the data of these hash tables will be user traffic (uplink and downlink) > > First, is there any API, example etc.. to calculate IPv4 hash and IPv6 hash on DPDK library? If not, does anyone know where I might find any paper or writing how I can calculate IPv4 and IPv6 hash? Also is there a more appropriate data structure than the hash table for the problem? > > Thanks in advance. > > - Volkan -- Gaëtan Rivet 6WIND