Internet DRAFT - draft-truong-icnrg-ndn-osn
draft-truong-icnrg-ndn-osn
ICN Research Group P. Truong
Internet Draft Orange
Intended status: Informational K. Satzke
Expires: September 4, 2015 Alcatel-Lucent
B. Mathieu
Orange
E. Stephan
Orange
March 4, 2015
Named data networking for social network content delivery
draft-truong-icnrg-ndn-osn-00.txt
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other documents
at any time. It is inappropriate to use Internet-Drafts as
reference material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
This Internet-Draft will expire on September 04, 2015
Copyright Notice
Copyright (c) 2015 IETF Trust and the persons identified as the
document authors. All rights reserved.
P. Truong Expires 04 September, 2015 [Page 1]
Internet-Draft NDN for OSN Delivery (NoD) March 2015
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with
respect to this document.
Abstract
Online Social Networking (OSN) applications have attracted millions
of people over the last few years. Their traffic represents a large
part of the traffic of the Internet. For instance, Facebook
represents near 25 percent of the Internet traffic [14][15], and a
part of this traffic is exchanged amongst groups of end-users which
are located in the same geographic area. In this document, we
introduce a Named Data Networking (NDN) architecture to improve the
delivery of OSNs contents requested by end-users in the
neighbourhood of the publishers: Having the knowledge of the social
network graph and the end-users network location, a SDN-based NDN
controller dynamically configures the NDN routers to route the
interest requests directly between the end-users.
Table of Contents
1. Introduction 3
2. Analysis of OSN Networking Behaviour 4
3. NDN-based Naming Scheme 5
4. Locality-aware Name-based Routing 6
5. SDN-based routing configuration employing OSN information 7
5.1. Notification to the controller for setting routes to the OSN
server 8
5.2. Notification to the controller for OSN users' location 9
6. Application Call Flows 10
P. Truong Expires: 04 September, 2015 [Page 2]
Internet-Draft NDN for OSN Delivery (NoD) March 2015
6.1. Publication of Tweets 11
6.2. Retrieval of Tweets 11
6.3. Retrieval of Tweets for Non-Local Users 12
7. Security Considerations 12
8. IANA Considerations 12
9. Informative References 12
10. Acknowledgments 13
1. Introduction
Internet usage has rapidly evolved over the last decade, moving
beyond simple one-to-one connections toward more complex
interconnections between hosts. Online Social Networking (OSN)
services are distributed platforms through which people sharing the
same interests, activities, background and so on can interact. The
most prominent OSNs are Facebook, Twitter and LinkedIn [1].
Analysing the OSN end-users behaviour is done by several research
teams, wishing to better understand the social relationships between
users, their habits, their way of using and consuming OSNs, etc.
From those papers, such as [2][3][4], we can say that locality plays
an important role in OSN applications. People are very frequently
connected to other people that are in the same town, same region, in
short in a close vicinity (e.g. tweets are distributed locally to
local followers, users often send their tweets from the same
location, etc.), except for very popular accounts (e.g. a Twitter
account having millions of followers). However, the current
networking behaviour of the OSN applications does not take this into
account. Messages are always transferred toward remote centralised
servers, while the real destinations of the messages can be very
close[3].
We then defined a framework of NDN for OSN Delivery (NOD), which is
an name-based forwarding scheme designed to optimize the delivery of
OSN data, based on the social relationships. Our NOD framework
focuses on four key features:
P. Truong Expires: 04 September, 2015 [Page 3]
Internet-Draft NDN for OSN Delivery (NoD) March 2015
- The separation of the NDN control plane from forwarding plane
- A centralized NDN controller and view of the network topology
- Interface between the NDN controller and the OSN server to share
social network graph information
- Interface between the NDN controller and the NDN routers to
dynamically configure the forwarding plane.
This migration of control, formerly tightly bound in individual
network devices, enables the underlying infrastructure to be
abstracted for applications and network services, which can treat
the network as a logical or virtual entity.
The centralized view and the separation of the control plane and the
data plane mean that the controller can create and maintain a
topology of how the forwarding nodes under his control are connected
and, based on some combination algorithms, can create paths through
the network. That allows the controller to better manage traffic
flows across the entire network and to react to changes quicker and
more intelligently.
The examples given in the draft configure the forwarding plane using
SDN interfaces to highlight how Information-Centric Networking (ICN)
concepts can help to deliver OSN contents more efficiently. These
interfaces and underlying networking data transport could be done
using other content naming schemes or routing protocols.
2. Analysis of OSN Networking Behaviour
OSN applications work on graph structures that define the social
relationships between end-users. The study [4] of the graph of the
user communities of Twitter and Facebook shows that they are very
similar:
. A majority of users have friends in the immediate vicinity
(city, district or country).
. Only very popular users have "friends" (or followers)
distributed almost everywhere around the world.
The delivery of contents amongst OSN users can then be categorized
into two groups:
a) OSN users having a mainly local (e.g., national) follower group,
their content is consumed locally
P. Truong Expires: 04 September, 2015 [Page 4]
Internet-Draft NDN for OSN Delivery (NoD) March 2015
b) OSN users having non-local (i.e., international) follower group,
their content is consumed worldwide.
The study of OSN network traffic shows that the flows do not reflect
the end-users graphs. OSN applications currently forward end-users'
requests toward either the OSN remote servers or some CDN caches
irrespectively of the end-users' relationships. For example, the
exchange of OSN content between two users, who are friends on the
OSN and located in the same access ISP network, is directed outside
the ISP network toward the OSN servers.
The delivery of OSN content locally represents an important field of
resources saving (transit cost, quality of experience, ...).
Our study proposes a new architectural solution for optimizing
content delivery in OSNs. It is based on a routing scheme that takes
into account end-users' co-locality.
This draft proposes a network model based on Named Data Networking
(NDN) and the knowledge about the co-locality of end-users: The NDN
controller configures NDN routing states in the network based on its
knowledge about the locations of NDN forwarding nodes and OSN
content, as well as the social graph from the OSN.
3. NDN-based Naming Scheme
While our approach leverages name-based routing principles, it does
not depend on a particular naming scheme. We propose to adopt a
hierarchical naming scheme allowing addressing OSN applications,
end-users of a specific OSN and the contents produced by end-users.
As an example, for a particular OSN application the following
hierarchical naming scheme is proposed:
/OSNapp/UserID/contentID
The name prefix /OSNapp denotes a specific OSN application. Then,
the prefix /OSNapp/UserID identifies an end-user in this OSN
"OSNapp". Finally, /OSNapp/UserID/contentID refers to a content
produced by the end-user "UserID" of the OSN "OSNapp".
P. Truong Expires: 04 September, 2015 [Page 5]
Internet-Draft NDN for OSN Delivery (NoD) March 2015
4. Locality-aware Name-based Routing
Based on the analysis of the OSN networking behaviour and the end-
users behavior as described in Section 2, we propose a centralised
controller-based NDN forwarding scheme that differentiates end-users
based on their OSN graph, in particular on the properties of the
list of followers of an OSN user.
Popular end-users, whose content is consumed worldwide, should have
a different way of working than non-popular local end-users, whose
content will be locally consumed. For popular end-users the current
networking behaviour of OSNs (e.g.; requests toward the centralized
server and data given back by the server) can be retained. It
enables OSN providers to keep knowledge of their clients and
possibly adapt some processing for very popular end-users.
Furthermore, it can be an added value for them (and something they
can monetize) for popularity measurements, targeted advertisement
(e.g. announcement of a live of a popular singer that is followed by
millions of people, etc.).
For local end-users, i.e. for users that have mainly friends in the
immediate vicinity, we adopt a modified architecture to alleviate
the load on the OSN server and to reduce the network load between
the users' access networks and the OSN server, as according to our
research the majority of the traffic stays locally. As such, we
suggest to route interest requests for local content toward the
local end-users themselves who will provide the content.
To make local routing possible, we first define the notion of
locality between OSN end-users by using the network routing hop. We
say that two users are local if there are separated by two routing
hops (or any other value depending on the design configuration).
We assume now that all end-users (local end-users but also non-local
ones and popular ones) can announce their prefix name in the
network.
Following the hierarchical naming approach described in the previous
section, locality-aware name-based routing is possible since NDN
allows for the routing of interests based on the longest-prefix
matching on the name. Indeed, let us suppose that locality is
defined by 2 routing hops, and that the user Bob requests an
Interest for Alice's content who name is "/OSNapp/Alice/content245".
We then have the two following possible situations:
P. Truong Expires: 04 September, 2015 [Page 6]
Internet-Draft NDN for OSN Delivery (NoD) March 2015
. If Bob is located more than 2 routing hops far from Alice, his
Interest will be routed toward the OSN server based on the OSN
application name prefix "/OSNapp". (Note that this forwarding
process toward the OSN server is also very likely to be applied
to popular end-users who have friends/followers located in
numerous places around the world.)
. On the opposite side, if Bob is located within the network
region delimited by 2 routing hops, his Interest will be
directly routed toward Alice using the name prefix
"/OSNapp/Alice". Alice is then required to serve Bob's Interest
by send the requested content in a Data message to Bob
As we can see, in addition to have the route for the prefix
"/OSNapp", we should then have different entries "/OSNapp/UserID"
(for locally serving content requests) in the Forwarding Information
Base (FIB) of the NDN routers. So in order to avoid a scalability
issue when storing those routes for local users in the FIBs, we
advocate the use of a logically-centralized NDN controller to
dynamically configure the routes toward end-users taking into
account information from their OSN application social graph
required, as described in the following section.
5. SDN-based routing configuration employing OSN information
We advocate for a dynamic and temporary configuration of the FIB
tables with the help of the NDN controller because is not realistic
to think that every forwarding node will keep knowledge of all end-
users in their FIB table for scalability reasons.
For ensuring better scalability in the control plane with user's
prefix announcements, we adopt a dynamical approach, based a
Software-Defined Networking (SDN)-like architecture between a
centralized controller and the NDN routers, which allows to
dynamically configure the NDN forwarding tables for applying our
local routing scheme, based on the social interactions in the OSN
(e.g. add route in the local NDN routers according to the network
operator's requirements and policies for a certain network region
and/or a particular group of contents/users). In a general context
of the workflow, when the controller receives an update message from
the OSN server containing information about OSN contents or users'
locations, it can decide to re-calculate routes using topological
and OSN social graph information. If a newly calculated route
requires modifications to one or more NDN forwarding elements, the
P. Truong Expires: 04 September, 2015 [Page 7]
Internet-Draft NDN for OSN Delivery (NoD) March 2015
controller communicates the changes to the registered NDN forwarding
nodes, respectively.
A threshold value can be defined for each local user to estimate his
popularity which takes into account the number of followers in an
OSN application.
If the user's number of followers exceeds the predefined threshold
value, the OSN application can instruct the NDN controller to modify
the FIBs of forwarding nodes located in close vicinity to the user
location as discussed above by adding new prefixes and targets.
On the other hand, if the number of followers of the local user is
below a predefined threshold, the OSN application can instruct the
NDN controller to modify the FIBs of the previously selected
forwarding nodes to remove the additional FIB entries for the
particular local user.
This helps scaling the name-based routing approach by avoiding the
accumulation of unnecessary FIB entries in the forwarding nodes.
We describe in the following the main types of notification which
can be sent to our NDN controller.
5.1. Notification to the controller for setting routes to the OSN
server
At the startup, the OSN provider is responsible for announcing its
name prefix '/OSNapp' in the network: this allows to set up routes
in the network toward the OSN server. The announcement can be
registered by a service running on the NDN controller to calculate
routes for interest requests in the network to the OSN application
server.
Subsequently the controller populates the Forwarding Information
base (FIB) of the registered NDN forwarding nodes. The FIB of each
forwarding node will then contain at least one entry matching
'/OSNapp' to forward all requests for OSNapp content to the
respective application server if no other FIB entry has a longer
prefix match. It is presumed that the OSN application servers are
stable and always on so that there will no requirements for frequent
updates of this particular FIB entry.
P. Truong Expires: 04 September, 2015 [Page 8]
Internet-Draft NDN for OSN Delivery (NoD) March 2015
5.2. Notification to the controller for OSN users' location
When an user, let us say Joe, is getting online, the OSN server
notifies the controller that Joe is now available. In the
notification message, the OSN server provides the controller with
information about Joe, such as:
. the location of the NDN router to which Joe is connected
. the list of Joe's friends/followers who are currently online,
along with their location (i.e. the location of the NDN routers
to which Joe's online friends are connected)
. the list of users Joe follows (friendship in OSNs is not
necessarily two-way, reciprocal.)
. additionally, some other optional meta-information, which can
be especially useful when Joe defines different access rights
to his contents for his friends. For example, Joe can restrict
the access to his personal photos to only his family members.
Based on those elements from the OSN server and on its knowledge of
the network topology and policies, the controller can configure the
network with new routes toward Joe, by adding the entry
"/OSNapp/Joe" into the FIB of the NDN nodes that are located within
the local network region around Joe (i.e. located at most 2 routing
hops far from the Joe, supposing that we have set the locality value
to 2 - the value depends on network topology and configuration).
Note that this route is added to a local NDN router only if it is
the access router of Joe or there are Joe's online friends attached
to the router.
After the controller has configured the local NDN forwarding nodes
for Joe's reachability, local friends can retrieve Joe's contents
from himself: all related content requests will thus forwarding to
Joe who is responsible for serving the demand.
Now, when Joe is disconnecting, the OSN server notifies the
controller again, which in turn can check the list of Joe's
followers to evaluate with the help of a pre-defined threshold value
if the number of followers of Joe still exceeds the threshold or if
the FIB of a NDN forwarding node can be cleaned from the entries
corresponding to "/OSNapp/Joe" name prefix. And also in the reverse
operation, the controller can check the list of users that Joe
himself follows in order to check if it can remove other FIB entries
to those users to improve scalability of the approach.
P. Truong Expires: 04 September, 2015 [Page 9]
Internet-Draft NDN for OSN Delivery (NoD) March 2015
6. Application Call Flows
This section describes in details the call flows for our local-aware
NDN-based architecture with dynamic routing configuration.
Let us consider the network configuration as illustrated by Figure
1. We represent the different NDN routers in the Figure by their FIB
(F1, F2, etc). All NDN routers have been registered with the
controller. Therefore, as described in Section 5.1, all the FIBs,
F1, F2,...,F6 in the Figure, contain, as a minimum, the entry
"/OSNapp" for the route to the OSN server.
+---------------+
|NDN Controller |
+-------------+-+
|
+-+-+ +---+ +-------------+
| F3+--------| F4+----| OSN Server |
+-+-+\ +---+ +-------------+
| \
| \
+-+-+ \ +---+
+------+ F2+ +------+ F5+----------+
| +-+-+ +---+ |
+-+-+ \ |
| F1| \ |
+-+-+ \ +-+-+
/ \ \ | F6|
/ \ \ +-+-+
/ \ \ |
+--+---+ +-+-+ ++-+--+ +--+--+
|Walter| |Joe| |Alice| | Bob |
+------+ +---+ +-----+ +-----+
Figure 1: Social- and Local-aware network routing configuration
P. Truong Expires: 04 September, 2015 [Page 10]
Internet-Draft NDN for OSN Delivery (NoD) March 2015
6.1. Publication of Tweets
For local-aware routing, we set the locality as network regions
delimited by two routing hops. As a consequence, Alice, Joe, Walter
are local users, i.e. located in the same local area.
1. Joe is getting online: he connects to the OSN server using an
application client on his smartphone or computer.
2. The OSN server registers Joe's client and evaluates the number of
Joe's followers
3. In case the number of followers exceeds a predefined threshold
value, the OSN server can decide to inform the NDN controller with
a notification message containing meta information related to Joe
4. The NDN controller configures the local NDN routers (located at
most two routing hops from Joe) by adding the route "/OSNapp/Joe"
for Joe's reachability in the related FIBs (F1 and F2 in Figure
1). (Note that in Figure 1, we suppose Alice and Walter follow
Joe. However, if Alice does not follow Joe, and there are no other
users following Joe under the same router, the controller does not
add the route "/OSNapp/Joe" to the FIB.)
5. The NDN router FIBs F1 and F2 contain now an entry "/OSNapp/Joe"
for the route to Joe's device.
6. Joe can now publish his new content: the content object is stored
in the OSN server.
6.2. Retrieval of Tweets for Local Users
We keep the same network configuration as in 6.1 (Figure 1). As we
set locality to two routing hops, Alice and Walter are local users
compared to Joe's location. They are located in the same local
network region. Alice and Walter can then benefits from local-aware
routing.
1. Alice wants to retrieve Joe's content. She then expresses an
Interest for "/OSNapp/Joe/Video10".
2. Thanks to the previous routing configuration by the controller,
(the router FIBs F1 and F2 in Figure 1 contain a route for
"/OSNapp/Joe"), the network knows how to forward the
Interest("/OSNapp/Joe/Video10"), which will finally directed to
Joe.
3. Joe, receiving the Interest, returns a Data message for serving
the requested content /OSNapp/Joe/Video10.
4. While forwarding the Data message on the reverse path (taken by
the Interest), Joe's content is also cached in the Content Store
of the traversed routers.
5. Alice can then enjoy Joe's content.
P. Truong Expires: 04 September, 2015 [Page 11]
Internet-Draft NDN for OSN Delivery (NoD) March 2015
6. Now, when Walter requests Joe's content /OSNapp/Joe/Video10, he
will get it directly from the cache of his NDN access router.
6.3. Retrieval of Tweets for Non-Local Users
Now, we suppose that Bob wants to retrieve Joe's content Video10
(Figure 1). In this case, as Bob is a non-local user, i.e. located
too far from Joe, his Interest for "/OSNapp/Joe/Video10" will be
forwarded using the prefix "/OSNapp". The OSN server is then
responsible for serving the request, and the sent content will be
cached in the content store of the different traversed NDN routers
on the reverse path.
7. Security Considerations
This document does not impact the security of the Internet.
8. IANA Considerations
This document presents no IANA considerations.
9. Informative References
[1] http://www.alexa.com/topsites/category/Computers/Internet/
On_the_Web/Online_Communities/Social_Networking
[2] M. P. Wittie, V. Pejovic, L. Deek, K. C. Almeroth, and B. Y.
Zhao, "Exploiting locality of interest in online social networks,"
in ACM CoNEXT '10, New York, USA, 2010, pp. 25:1-25:12.
[3] R. Cuevas, R. Gonzalez, A. Cuevas, and C. Guerrero,
"Understanding the locality effect in twitter: measurement and
analysis," Personal and Ubiquitous Computing, pp. 1-15, 2013.
[4] eCousin Deliverable D3.1, "Measurement, Modelling, and
Prediction of Social-Content Interdependencies": www.ict-
ecousin.eu/public-deliverables-dissemination/public-
deliverables/ecousin-deliverable-d3.1-v1.2-
final.pdf/at_download/file
P. Truong Expires: 04 September, 2015 [Page 12]
Internet-Draft NDN for OSN Delivery (NoD) March 2015
[5] W. Wongyai and L. Charoenwatana, "Examining the network traffic
of facebook homepage retrieval: An end user perspective," in
Computer Science and Software Engineering (JCSSE), 2012
International Joint Conference on, 2012, pp. 77-81.
[6] B. Ahlgren, C. Dannewitz, C. Imbrenda, D. Kutscher, and B.
Ohlman, "A survey of information-centric networking," Communications
Magazine, IEEE, vol. vol.50, July 2012.
[7] L. Wang, M. A. Hoque, C. Yi, A. Alyyan, and B. Zhang, "OSPFN: An
OSPF Based Routing Protocol for Named Data Networking," Name Data
Networking, Tech. Rep. NDN-003, July 2012.
[8] V. Jacobson, D. K. Smetters, N. H. Briggs, M. F. Plass, P.
Stewart, J. D. Thornton, and R. L. Braynard, "VoNDN: voice-over
content-centric networks," in Proceedings of the 2009 workshop on
Re-architecting the internet, ser. ReArch '09. New York, NY, USA:
ACM, 2009, pp. 1-6.
[9] A. K. M. M. Hoque, S. O. Amin, A. Alyyan, B. Zhang, L. Wang, and
L. Zhang, "NLSR: Named-data link state routing protocol", In SIGCOMM
2013 ICN Workshop, 2013
[10] M. Almishari, P. Gasti, N. Nathan, and G. Tsudik, "Optimizing
bi-directional low-latency communication in named data networking",
SIGCOMM Comput. Commun. Rev. 44, 1 (December 2013), 13-19.
[14] http://www.adweek.com/socialtimes/in-q2-facebook-drove-nearly-
a-quarter-of-web-traffic/300175
[15] http://www.digitaltrends.com/mobile/facebook-25-pct-of-u-s-
traffic-and-100-million-app-downloads/
10. Acknowledgments
The research leading to these results has received funding from the
European Union's Seventh Framework Programme ([FP7/2007-2013]) under
grant agreement n 18398, project eCOUSIN.
The views and conclusions contained herein are those of the authors
and should not be interpreted as necessarily representing the
official policies or endorsements, either expressed or implied, of
the eCOUSIN project or the European Commission.
P. Truong Expires: 04 September, 2015 [Page 13]
Internet-Draft NDN for OSN Delivery (NoD) March 2015
This document was prepared using 2-Word-v2.0.template.dot.
Authors' Addresses
Patrick Truong
Orange Labs
2 Av. Pierre Marzin
22300 Lannion
France
Email: patrick.truong@orange.com
Klaus Satzke
Alcatel-Lucent Bell Labs
Lorenzstrasse 10
70435 Stuttgart
Email: Klaus.Satzke@alcatel-lucent.com
Bertrand Mathieu
Orange Labs
2 Av. Pierre Marzin
22300 Lannion
France
Email: bertrand2.mathieu@orange.com
P. Truong Expires: 04 September, 2015 [Page 14]
Internet-Draft NDN for OSN Delivery (NoD) March 2015
Emile Stephan
Orange Labs
2 Av. Pierre Marzin
22300 Lannion
France
Email: emile.stephan@orange.com
P. Truong Expires: 04 September, 2015 [Page 15]
