Re: [icnrg] [EXT] Question on the NIST NDN forwarder

Junxiao Shi <shijunxiao@email.arizona.edu> Wed, 22 April 2020 15:39 UTC

Return-Path: <shijunxiao@email.arizona.edu>
X-Original-To: icnrg@ietfa.amsl.com
Delivered-To: icnrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id B12033A0EDF for <icnrg@ietfa.amsl.com>; Wed, 22 Apr 2020 08:39:21 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.896
X-Spam-Level:
X-Spam-Status: No, score=-1.896 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_NONE=0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=email-arizona-edu.20150623.gappssmtp.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id BocEjfWS4p9S for <icnrg@ietfa.amsl.com>; Wed, 22 Apr 2020 08:39:19 -0700 (PDT)
Received: from mail-oo1-xc42.google.com (mail-oo1-xc42.google.com [IPv6:2607:f8b0:4864:20::c42]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9B9833A0ECD for <icnrg@irtf.org>; Wed, 22 Apr 2020 08:39:19 -0700 (PDT)
Received: by mail-oo1-xc42.google.com with SMTP id x16so595681oop.13 for <icnrg@irtf.org>; Wed, 22 Apr 2020 08:39:19 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=email-arizona-edu.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=R7cmi6IarvWQxCsPFVTNsdxqKjE5S+Q/F5CTpBk09OY=; b=kGEhhtPJDFGXPNuhcPskuM6rtEqls4CYzL4yVhhOSehvUsczMDm+XL9SRFH9n3TYUu fhdZLHzL4V2THU8/GPsUDwiH1l9/AT28NoO8s1nuDUYOsvEVdBiwNbd0xzrC3GXjKTQP r95I9owTQxCumUT5J236nnxyRS9ods1AMOXEyjFw50PLhZL6hcpw/LQeHwVJTNr85mad frNTt2a/rnl8KlfQsdIUGyRSIao4xXagCs8F1BRVRtvSziPyGnothz+pocnZCnwhw2jV l4e6ts2MOgg6SkdqB6iBVns9y6VVHl/E2/P1yLCx87ACFI56OZMFIaZzx/7NjGIJjmqe BeUg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=R7cmi6IarvWQxCsPFVTNsdxqKjE5S+Q/F5CTpBk09OY=; b=LtgeWjXqv/2a/SsmsAH5Oxk6cRvsqGCLtyjh8egSbm5wZl/6zPikjb1ZVikCUzqYpv ZPtqHuCnK3ZoewmSh68ziU/n2GSEGj892t19WM1iSvL+iXjY3inICUJAT/t7vxUNwYsM 88uqFw98bEP3V3hbjtRDlC+gHiwP414XpXLpROLtsNskfDehnmWzQeSAXAE0LQ6xcAXl oWhWwr9gnyF1+Xd/dqVqRz0NHGMtD2KYf7ut5E5dnrNN7/Ja9ZML292bnTIK73tcyLfk r4BGhYe8uQpjS/uLQ0KrIRaJTvOoHuLfV72pgGarx1pdg5OHRD4ar5xmVEmWj0t/4vq9 /ysQ==
X-Gm-Message-State: AGi0PuY4B0gCYHwVObcsBU+bTx7SRsyibcop20tGR6xisPCDRNnG74IN 8diXv//hHaaObSHJUpC3/UbWQI9AO+DfbPX4HJIAEmvF0Em81XPO83yTkP2l3ff026zRE7vLByh YwIwv+HlvB5E=
X-Google-Smtp-Source: APiQypLu7bQUq4oYsoPFNDMVM3Mpr5ek9JIVqWXosKT/Ub6Vm35DR/xvGL9PTafHLqS/yaoWA4c1EAta4rhUI7lGnhE=
X-Received: by 2002:a4a:1ec3:: with SMTP id 186mr21190947ooq.66.1587569958696; Wed, 22 Apr 2020 08:39:18 -0700 (PDT)
MIME-Version: 1.0
References: <060E1A5C-4B55-4850-900A-6A29C8596861@orandom.net> <CAOFH+Ob2WnjDueHDftfJJ+_DWyH64gd9An7TDMKrNk8h45EbLg@mail.gmail.com> <9CAE2FCA-658A-4032-BDDE-7326BB1C151F@orandom.net>
In-Reply-To: <9CAE2FCA-658A-4032-BDDE-7326BB1C151F@orandom.net>
From: Junxiao Shi <shijunxiao@email.arizona.edu>
Date: Wed, 22 Apr 2020 11:38:42 -0400
Message-ID: <CAOFH+OYfnfaNvpWJM7v7PQ=kQgPV8UgxOHukf=U-T4rbBpMCTQ@mail.gmail.com>
To: "David R. Oran" <daveoran@orandom.net>
Cc: "Shi, Junxiao" <junxiao.shi@nist.gov>, ICNRG <icnrg@irtf.org>
Content-Type: multipart/alternative; boundary="00000000000071d16605a3e2ef36"
X-ua-ms: gsuite
Archived-At: <https://mailarchive.ietf.org/arch/msg/icnrg/3WtK1rIAznjLb8VT3CLKXQmVMng>
Subject: Re: [icnrg] [EXT] Question on the NIST NDN forwarder
X-BeenThere: icnrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Information-Centric Networking research group discussion list <icnrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/icnrg>, <mailto:icnrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/icnrg/>
List-Post: <mailto:icnrg@irtf.org>
List-Help: <mailto:icnrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/icnrg>, <mailto:icnrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 22 Apr 2020 15:39:22 -0000

Hi Dave

Thanks! This helps a lot. I’m somewhat surprised to see this a bit buried
> in a forwarder API description - is there something in an architecture
> document that explains to applications what the allowable semantics are?
>
The NDN forwarding behavior in Chapter 2 and 3 of NDN in Local Area Networks
<https://hdl.handle.net/10150/625652> says the following for the Content
Store:

When an Interest arrives, the node queries the CS to see if there is a
cached Data that can satisfy the Interest. Given an Interest, the CS is
expected to return a Data that satisfy the Interest, i.e. the Data name
must start with the Interest name, and the Data must not violate any
selectors in the Interest. If the CS finds a Data that satisfies
the Interest, the Data is returned to the downstream, and the Interest is
not forwarded further. This saves upstream bandwidth, and shortens data
retrieval delay.

Note: this was written in 2017 so some terminology is outdated. "selectors"
has been replaced by "CanBePrefix and MustBeFresh".

While the CS is "expected" to return a Data that satisfies the Interest, it
is not required to do so.
The network as a whole would still be functional even if the CS on some or
all nodes are reporting MISS when the Data actually exists.

One quick followup, since I’m clearly missing something in the explanation
> it says: “When an incoming Data satisfies an Interest with a prefix name or
> a full name…”. I don’t understand how you can tell whether the PIT for an
> interest with a prefix name is satisfied by that data without either
> already having the indirect entry somewhere, or doing a full LNPM into the
> PIT or CS to discover the Data object matches. Cluebat please?
>
NDN-DPDK inserts a PIT token on the hop-by-hop header of every outgoing
Interest. The upstream node MUST put the same PIT token when they send back
Data/Nack in reply to the Interest. The PIT token not only indicates which
forwarding thread processed the Interest, but also contains an index of the
PIT entry.
For an incoming Data, the forwarder knows exactly which PIT entry is being
satisfied. It does not need to perform any name matching in the PIT.


NDN-DPDK design is influenced by Network Algorithmics
<https://books.google.com/books/about/Network_Algorithmics.html?id=fnZ9WWpVK7oC>.
Chapter 3.3 gives some implementation principles. The relevant ones are:

P3 relax system requirements - P3c shift computation in time

The CS cannot find cached Data if an Interest is using a prefix name that
has not been used before. This improves forwarding speed, at the cost of
shifting the computation of such name discovery to the producer node or an
edge forwarder (note that NDN-DPDK is not an edge forwarder).

P7 avoid unnecessary generality

Although consumers may use any prefix name to perform name discovery, this
is a rarely used feature. A well-designed application would use a
consistent prefix name to perform name discovery.

P10 pass hints in protocol headers

PIT token is passed in the hop-by-hop header, so that PIT lookup can be
greatly simplified.

P11 optimize the expected case

The expected case is that the application is using a consistent prefix name
to perform name discovery. The network as a whole optimizes for this
expected case.



Yours, Junxiao