Transcript ICN_and_CBR

Content-based Routing for
Information Centric Networks
D. Reininger
ECE 544
Spring 2014
Introduction
• Apart from routing protocols that use a direct identifier
of nodes, networking can take place based directly on
content.
• Content can be collected from the network, processed
in the network, and stored in the network
• Goal is to provide a network infrastructure capable of
providing services better suited to today’s application
requirements:
– content distribution & mobility
– more resilience to disruption and failures
• We look next at such content-based networking and
data aggregation mechanisms.
Networking Evolution
• Traditional networking
– Host-centric communications addressing end-points
• Information-centric networking
– Data-centric communications addressing information
(e.g., data in context).
– Decoupling in space – neither sender nor receiver
need to know their partner.
– Decoupling in time – “answer” not necessarily directly
triggered by “question”, asynchronous
communication.
Information-centric Networking
• Approach
– Named Data Objects (NDOs)
– in-network caching
– multi-party communication through replication
– decoupled senders from receivers
• Architectural questions
– How do we address information?
– How do we obtain information?
– How do we route information?
ICN Communication Model
Chart notes describe the information exchange.
Dissemination networking
• Data is request by name, using any and all
means available (IP, VPN tunnels, multicast,
proxies, etc).
• Anything that hears the request and has a
valid copy of the data can respond.
• The returned data is signed, and optionally
secured, so its integrity & association with
name can be validated (data centric security)
ICN Stack
(1) Van Jacobson, et al, Networking Named Content, CoNEXT 2009
• Change of network abstraction from “named host” to “named
content”
• Security built-in: secures content and not the hosts
• Mobility is present by design
• Can handle static as well as dynamic content
• Use of 2 messages: Interest and Data Objects
Universal?
• Any architecture that runs over anything is an
overlay (IP is an overlay).
• IP started as a phone system overlay; today much
of the phone system is an IP overlay. System
theorists would say ‘IP is universal’.
• ICN has the same character: it can run over
anything, including IP, and anything can run over
ICN, including IP.
• And ICN has a simpler, more general relationship
with lower layers than IP.
Example: Content Distribution
Example: Content Distribution
Example: Content Distribution
Example: Content Distribution
Example
• Content goes only where there’s
interest.
• It takes at most one trip across any link.
• Average latency is minimized.
• Total bandwidth is minimized.
• There’s no routing or control traffic
associated with the replicas.
Approaches
• Content Centric Networks
–
–
–
–
–
–
Naming: Hierarchical naming, single address
Security: Signed content
Routing: Longest prefix matching
Caching: Local or network based
Content existence knowledge: Not part of the CCN core
Producer-consumer meeting: Propagation of interests
• Network of Information
–
–
–
–
–
–
Naming: Flat naming
Security: Signed content
Routing: (1) Name resolution (2) Information transfer
Caching: Network based
Content existence knowledge: Through name resolution service
Producer-consumer meeting: Name resolution service provide locations
Approaches
• Publish Subscribe Internet Routing Paradigm
–
–
–
–
–
–
Naming: Multi-level identifiers
Security: Signed content
Routing: (1) Name resolution (2) Information transfer
Caching: Network based
Content existence knowledge: Registrations in Rendezvous system
Producer-consumer meeting: Rendezvous system provides location
• Data Oriented Networking Architecture
–
–
–
–
–
–
Naming: Flat naming
Security: Signed content
Routing: Queries are resolved to locations
Caching: Network based
Content existence knowledge: Through resolution infrastructure
Producer-consumer meeting: Resolution infrastructure provides location
Naming
• Solution 1: Name the data
– Flat, not human readable identifiers
• 1DB76EB8DFD6B0b92A293AADC8421830BDE73CB6
– Hierarchical, meaningful structured names
• /nytimes/sport/baseball/mets/game022414/
• Solution 2: Describe the data
– With a set of tags
• baseball, new york, mets
– With a schema that defines attributes, values and
relations among attributes
Using Names in CCN
• The hierarchical structure is used to do
‘longest match’ lookups (similar to IP prefix
lookups) which helps guarantee log(n) state
scaling for globally accessible data.
• Although CCN names are longer than IP
identifiers, their explicit structure allows
lookups as efficient as IP’s.
(see hashing work by Rasmus Pagh and Martin Dietzfelbinger)
Routing
• Three general approaches
– Name Resolution Routing (NRR)
– Content-based Routing (CBR)
– Name-based routing (NBR)
• Two phases
– Routing of NDO requests
– Routing of NDO back to the requester
Name-Based Routing
• Client asks for a data object sending interest packets
which are routed toward the publisher of the name
prefix using longest-prefix matching in the forwarding
information base (FIB) of each node.
• The FIB is built using routing protocols of the Internet.
• When a note receives multiple requests for the same
NDO, only the first is forwarded to the source.
• When a copy of the data object is encountered on the
path, a data packet containing the requested object is
sent on the reverse path back to the client and all
nodes along the path cache a copy.
Content Centric Network (CCN)
Chart notes describe numbered steps
CCN packets
There are two CCN packet types:
interest (similar to http “get”) and data
(similar to http response). Both are
encoded in an efficient binary XML.
CCN node model
Get /parc.com/videos/
WidgetA.mpg/v3/s2
Publish-Subscribe Internet Routing
Paradigm (PSIRP)
Chart notes describe numbered steps
Content-based Publish-Subscribe
Routing
Content-based Pub/Sub Routing
Content-based Pub-Sub Routing
Forwarding on Bloomed link ids
• The FI encodes the network links (rather than the nodes) on the
path of interest between the producer and consumers
• FI is encoded in a probabilistic data structure called a Bloom filter
that routers use for selecting interfaces on which to forward an
NDO.
– Bloom filters encode source route-style forwarding information into
packet headers, enabling forwarding without depending on end-toend addressing.
– Routers do not need to keep forwarding state. Forwarding decisions
are simple and forwarding tables are small, potentially allowing faster,
smaller, and more energy-efficient switches.
• The use of Bloom filters result in a certain number of false positives;
in this case this means forwarding on some interfaces where there
are no receivers.
Pub/Sub Routing using Link ID and FI
zFilter: FI Bloom Filter
See chart notes for further description
Network of Information
Name Resolution Routing
• Use a Name Resolution Service (NRS) that stores the
bindings from object names to topology-based locators
pointing to corresponding storage locations in the network.
• Three conceptual routing phases:
– Routing the request message to the responsible NRS node
where the object name is translated into one or multiple source
addresses
– Routing the request message to the source address(es)
– Routing the data from the source(s) to the requester.
• All phases can potentially use different routing algorithms.
– A name-based routing method might be used for the first phase.
– The second and third phases might use a topology-based
routing like IP.
– There are multiple alternatives to loosely or tightly integrate the
phases in an ICN architecture.
Summary of characteristics of the ICN
approaches
Content-Based Security
• Name-content mapping verification via per-data
packet signature
– Data packet is authenticated with digital signature
ICN trust establishment by associating
content namespaces w/ public keys
Basic ICN forwarding
• Consumer ‘broadcasts’ an ‘interest’ over any
& all available communications media:
get ‘/rutgers/ECE544/Lecture06-14.pdf’
• Interest identifies a collection of data - all data
items whose name has the interest as a prefix.
• Anything that hears the interest and has an
element of the collection can respond with
that data:
HereIs ‘/rutgers/ECE544/presentation.pdf/p1’
<data>
Basic ICN transport
• Data that matches an interest ‘consumes’ it.
• Interest must be re-expressed to get new data.
(Controlling the re-expression allows for traffic
management and environmental adaptation.)
• Multiple (distinct) interests in same collection
may be expressed (similar to TCP window).
Caching
• Storage for caching NDOs is an integral part of
the ICN service.
• All nodes potentially have caches; requests for
NDOs can be satisfied by any node holding a
copy in the cache.
• ICN combines caching at the network edge as
in P2P and other overlay networks with innetwork caching (e.g., transparent web
caches)
Advantages of the ICN approach
• Scalable and cost-efficient content distribution
– IP traffic to quadruple from 2010 – 2015
– Mobile data traffic increased 26x
– Mostly attributed to media traffic that continues
to be 90% of global consumer traffic by 2015
Issues
• Scalability
• Privacy (interest subscription and content
description)
• Legal (caching NDOs)
• Business case for deployment
References
•
•
•
•
•
•
•
A Survey of Information-Centric Networking, B. Ahlgren, et. al. IEEE Communications
Magazine, July 2012,
http://itec.hust.edu.cn/~jwchen/courses/compnet2013/references/A%20Survey%20of%20In
formation-Centric%20Networking-CommMag-ADI+12.pdf
A Survey of Information-Centric Networking Research, G. Xylomenos, et. al., Published in IEEE
Communications Surveys and Tutorials
Is Information-Centric Multi-Tree Routing Feasible? ICN Workshop 2013, M. Papalini et. al.
LIPSIN: Line Speed Publish/Subscribe Inter-Networking, Petri Jokela, et.al.
Information-Centric Networking: Seeing the Forest for the Trees, Ali Ghodsi, Scott Shenker,
et.al.
Bloom Filters
• http://billmill.org/bloomfilter-tutorial/
• http://en.wikipedia.org/wiki/Bloom_filter#Examples
A Multi-Level DHT Routing Framework with Aggregation, H. Liu et. al,
http://conferences.sigcomm.org/sigcomm/2012/paper/icn/p43.pdf