A Routing Scheme for Content-Based Networking
Carzaniga, Rutherford, Wolf
content-centric networking ccn routing
@inproceedings{carzaniga:infocom-2004,
title={A Routing Scheme for Content-Based Networking},
author={Antonio Carzaniga and Matthew J. Rutherford and
Alexander L. Wolf},
booktitle={Proceedings of IEEE INFOCOM 2004},
year={2004},
address={Hong Kong, China},
month={March}
}
[ Download PDF ]
Abstract:
This paper proposes a routing scheme for content-based networking. A content-based network is a communication network that features a new advanced communication model where messages are not given explicit destination addresses, and where the destinations of a message are determined by matching the content of the message against selection predicates declared by nodes. Routing in a content-based network amounts to propagating predicates and the necessary topological information in order to maintain loop-free and possibly minimal forwarding paths for messages. The routing scheme we propose uses a combination of a traditional broadcast protocol and a content-based routing protocol. We present the combined scheme and its requirements over the broadcast protocol. We then detail the content-based routing protocol, highlighting a set of optimization heuristics. We also present the results of our evaluation, showing that this routing scheme is effective and scalable.
Message content is set of attribute/value pairs; subscriptions (selection predicates) are disjunctions of conjunctions of elementary constraints over attributes
Overlay point-to-point network; content-based layer imposed over broadcast layer
- Broadcast layer forwards to all matching nodes
- Loop free and possibly minimal
- Also propagates control information
- Content-based layer prunes broadcast to just matching nodes
Nodes advertise queries defining the messages of interest to them
- Queries forwarded along broadcast tree from source
To work with higher level strategy, broadcast layer must
- Define a function to return all outgoing interfaces given a source node
- Have all-pairs path symmetry
- Tree from n1 to n2 must meet tree from n2 to n1
- This is a fairly typical property for must broadcast schemes, e.g., spanning tree, or easily met under typical usages, or easily supported with minor adaptation
Forwarding table associates filters to each external interface and local applications
- Routing determines all interfaces message matches, then intersects with outgoing interfaces from broadcast function with input of the message source
Nodes periodically advertise their filters, and/or when they change
- On receipt, if the filter is already covered by (subsumed by) the filter associated with the incoming interface, it's dropped
- Otherwise it is forwarded along the interfaces from broadcast function with input the source of the advertisement
Nodes can also request advertisements from all routers
- Complements advertisement push: Balances address inflation, compensate for lost advertisements
- Generates a lot of traffic
- Mitigated by using carefully, caching and reusing responses
- Can only be snooped, reused when downstream from current node matches that of original requester
- Only send requests along interfaces generating a lot of outgoing traffic
Can apply query optimization type techniques to simplify filters
- Very similar to OntoNet schemes
Evaluation has three main characteristics
- Functionality: Messages delivered to interested nodes?
- Filtering: Unnecessary message traffic curtailed?
- Scalability: Reasonable and stable amount of control traffic?
Network setup
- Flat, random, router-level topologies created by BRITE using Waxman edge selection
- Unlimited bandwidth on all links
- No disruption or mobility
Poisson senders and receivers
- Sending at 2, 3, 5 minutes
- Changing interests at 20 minutes
- Expect message rates several orders of magnitude more than filter change
Must capture setting where most apps are not interested in most data
- Otherwise broadcast makes more sense
Message delivery rate (false negatives)
Overhead (false positives)
See also:
- Siena event notification service [3] (TCS 2001)
- [5] discusses parameterization of query workload (SIGCOMM 2003 paper)
- Gryphon pub/sub