Internet DRAFT - draft-lee-icnrg-scalablerouting
draft-lee-icnrg-scalablerouting
Network Working Group J. Lee
Internet Draft ETRI
Intended status: Informational October 21, 2013
Expires: April 2014
Scalable Route-By-Name Routing Scheme
draft-lee-icnrg-scalablerouting-01.txt
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
This document may contain material from IETF Documents or IETF
Contributions published or made publicly available before November 10,
2008. The person(s) controlling the copyright in some of this
material may not have granted the IETF Trust the right to allow
modifications of such material outside the IETF Standards Process.
Without obtaining an adequate license from the person(s) controlling
the copyright in such materials, this document may not be modified
outside the IETF Standards Process, and derivative works of it may
not be created outside the IETF Standards Process, except to format
it for publication as an RFC or to translate it into languages other
than English.
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 April 21, 2014.
Lee Expires April 21, 2014 [Page 1]
Internet-Draft Scalable RBNR October 2013
Copyright Notice
Copyright (c) 2013 IETF Trust and the persons identified as the
document authors. All rights reserved.
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
This memo describes a scalable Route-By-Name Routing scheme for ICN.
[ICN Challenges] describes three possible routing schemes: Route-By-
Name Routing (RBNR), Lookup-By-Name Routing (LBNR), and Hybrid
Routing (HR). Among them, RBNR has advantages in terms of performance
and evolvability but scalability is a challenging issue. This memo
proposes a RBNR scheme using hierarchically-organized name space for
the scalability.
Table of Contents
1. Introduction ................................................ 2
2. Conventions used in this document............................ 3
3. Assumptions ................................................. 3
4. Functional details .......................................... 3
4.1. Hierarchical name space................................. 3
4.2. Building routing table.................................. 4
4.3. Packet format .......................................... 6
4.4. Discovery & Delivery.................................... 6
5. Security Considerations...................................... 6
6. IANA Considerations ......................................... 6
7. References .................................................. 6
7.1. Informative References.................................. 6
1. Introduction
[ICN Challenges] identified 3 steps in ICN routing, such as name
resolution, discovery, and delivery. Route-By-Name Routing has
advantage in terms of performance because it can omit the first step.
Also, RBNR is preferred in the context of evolvability because the
name can be independent from underlying technologies. In RBNR, the
primary issue to be addressed is the scalability as described in [ICN
Challenges]. In this memo, we propose scalable RBNR routing mechanism
Lee Expires April 21, 2014 [Page 2]
Internet-Draft Scalable RBNR October 2013
using hierarchical name. With the hierarchical name, the routing
table can be aggregated to the manageable size.
2. Conventions used in this document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC-2119 [RFC2119].
In this document, these words will appear with that interpretation
only when in ALL CAPS. Lower case uses of these words are not to be
interpreted as carrying RFC-2119 significance.
In this document, the characters ">>" preceding an indented line(s)
indicates a compliance requirement statement using the key words
listed above. This convention aids reviewers in quickly identifying
or finding the explicit compliance requirements of this RFC.
3. Assumptions
o "Name" has a structure similar to URI.
o Following Procedures are occurred within an administrative domain.
4. Functional details
4.1. Hierarchical name space
In this scheme, each "name segment" which comprises "name" represents
a contents provider. Let us suppose an example such as
"/Movieshop/Action/Sf/Superman". In this example "Movieshop",
"Action", and "Sf" represents a contents provider, and "Superman"
represents content itself.
To build aggregated routing table, each content provider has a hash
of its public key as its "ID" which has fixed length. Therefore, name
of data object can be described as follows:
o ID of content provider "Movieshop": HV1
o ID of content provider "Action": HV2
o ID of content provider "Sf": HV4
o "/Movieshop/Action/Sf/Superman" => "HV1:HV2:HV4:Superman"
The concatenation of IDs can play role of "locator".
Lee Expires April 21, 2014 [Page 3]
Internet-Draft Scalable RBNR October 2013
+---------------------+
| Movieshop (Id: HV1) | : Tier 1
+---------------------+
10.0.0.1, If0/ \2001:4000::1, If1
/ \
10.0.0.2, If0/ \ 2001:4000::2, If0
+-----------------+ +------------------+
| Action (Id: HV2)| | Romance (Id: HV3)| : Tier 2
+-----------------+ +------------------+
10.0.1.1,If1/ \10.0.2.1,If2 \2001:4001::1, If1
/ \ \
10.0.1.2,If0/ \10.0.2.2,If0 \2001:4001::2, If0
+-----------+ +---------------+ +------------------+
|Sf(Id: HV4)+--+Horror(Id: HV5)| |Historical(Id:HV6)| : Tier 3
+-----------+ +---------------+ +------------------+
Figure 1 Hierarchical name space
4.2. Building routing table
As described in 4.1. each contents provider has ID and uses the
concatenation of hierarchically consecutive IDs as "locator" (For
example, locator for Sf is "HV1:HV2:HV4", we call this as "Fully
Qualified Locator (FQL)"). In this scheme we use this locator as
"key" used to look up routing table entry, and to reduce the size of
routing table link-state routing protocol with LSA filtering is
adopted. By using LSA filtering the size of topology graph and
routing table can be reduced.
LSA filtering rule is like follows:
o To router at tier N-1: Blocks LSAs from tier N, instead the
locator of router at tier N is forwarded.
o To router at tier N: LSAs from tier N-1 are injected. Among the
peer routers of tier N, each of them forwards all LSAs that it has
to the all the other peer routers.
o To router at tier N+1: All LSAs including ones from tier N-1 are
injected
For example, some routing tables for Figure 1 are described as
follow:
o Movieshop (Tier 1):
Lee Expires April 21, 2014 [Page 4]
Internet-Draft Scalable RBNR October 2013
+-------------+--------------+--------+
| Destination | nexthop | out if |
+-------------+--------------+--------+
| HV1 | - | lo |
+-------------+--------------+--------+
| HV1:HV2 | 10.0.0.2 | if0 |
+-------------+--------------+--------+
| HV1:HV3 | 2001:4000::2 | if1 |
+-------------+--------------+--------+
o Action (Tier 2):
+-------------+--------------+--------+
| Destination | nexthop | out if |
+-------------+--------------+--------+
| HV1 | 10.0.0.1 | if0 |
+-------------+--------------+--------+
| HV1:HV2 | - | lo |
+-------------+--------------+--------+
| HV1:HV2:HV4 | 10.0.1.2 | if1 |
+-------------+--------------+--------+
| HV1:HV2:HV5 | 10.0.2.2 | if2 |
+-------------+--------------+--------+
o Romance (Tier 2):
+-------------+--------------+--------+
| Destination | nexthop | out if |
+-------------+--------------+--------+
| HV1 | 2001:4000::1 | if0 |
+-------------+--------------+--------+
| HV1:HV3 | - | lo |
+-------------+--------------+--------+
| HV1:HV3:HV6 | 2001:4001::2 | if1 |
+-------------+--------------+--------+
Lee Expires April 21, 2014 [Page 5]
Internet-Draft Scalable RBNR October 2013
4.3. Packet format
+--------------------------------------------------+
| General network layer header (IPv4, IPv6, etc..) |
+--------------------------------------------------+
| "name" described as "locator (FQL)" |
+--------------------------------------------------+
4.4. Discovery & Delivery
o When a user specifies a "name" like URI, it is transformed into
"locator (FQL)" format described previously.
o This "request" is forwarded to the default gateway (e.g. any
router in Figure 1).
o When a default gateway (router) receives the request, it retrieves
"locator" from packet header, and looks up routing table with it.
o If matched entry is found, the request is forwarded to the next
hop of it.
o When the request arrives at the last "name segment", the data
object is forwarded by means of bread-crumbs routing [BREADCRUMBS].
5. Security Considerations
TBD.
6. IANA Considerations
TBD.
7. References
7.1. Informative References
[ICN Challenges] D.Kutscher, "ICN Research Channelges", internet-
draft, July 2013
[DONA] Koponen, T., Ermolinskiy, A., Chawla, M., Kim, K., gon Chun,
B., and S. Shenker, "A Data-Oriented (and Beyond)Network
Architecture", In Proceedings of SIGCOMM 2007, August 2007.
Lee Expires April 21, 2014 [Page 6]
Internet-Draft Scalable RBNR October 2013
[BREADCRUMBS] Rosensweig, E. and J. Kurose, "Breadcrumbs: Efficient,
Best-Effort Content Location in Cache Networks", In
Proceedings of the IEEE INFOCOM 2009, April 2009.
Authors' Addresses
Joo-Chul Lee
ETRI
161 Gajeong-dong, Yuseong-gu, Daejon
Phone:
Email: rune@etri.re.kr
Lee Expires April 21, 2014 [Page 7]