Scalable Domain-based Routing Scheme
draft-lee-icnrg-domainbasedrouting-00
The information below is for an old version of the document.
| Document | Type |
This is an older version of an Internet-Draft whose latest revision state is "Expired".
|
|
|---|---|---|---|
| Author | Joo-Chul Lee | ||
| Last updated | 2014-02-14 | ||
| RFC stream | (None) | ||
| Formats | |||
| Stream | Stream state | (No stream defined) | |
| Consensus boilerplate | Unknown | ||
| RFC Editor Note | (None) | ||
| IESG | IESG state | I-D Exists | |
| Telechat date | (None) | ||
| Responsible AD | (None) | ||
| Send notices to | (None) |
draft-lee-icnrg-domainbasedrouting-00
Network Working Group J. Lee
Internet Draft ETRI
Intended status: Informational February 15, 2014
Expires: August 2014
Scalable Domain-based Routing Scheme
draft-lee-icnrg-domainbasedrouting-00.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 August 15, 2014.
Lee Expires August 15, 2014 [Page 1]
Internet-Draft Scalable Domain-based Routing February 20144
Copyright Notice
Copyright (c) 2014 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 routing scheme for information centric
networks. Moving the focus from "nodes" to "information objects"
raises scalability issue because aggregation of flat name for objects
is not easy task and the number of addressable information objects is
so huge than the IP address space. For scalable routing, we propose
hierarchically-organized domain architecture. A domain is a "logical
group" of information objects and each domain has its own ID. The
concatenation of domain IDs from top level domain to the current
domain plays the role of "locator". Thus, we can get scalable routing
table and it is more scalable by means of "topology reduction". More
challenging issue is name-based forwarding. It is hard to aggregate
forwarding table due to flat name space, therefore we propose
"reactive path setup".
Table of Contents
1. Introduction ................................................ 3
2. Conventions used in this document............................ 3
3. Terminologies ............................................... 3
4. Scalable Domain-based Routing................................ 4
4.1. Hierarchically-organized Domain Architecture............ 4
4.1.1. Locator ........................................... 5
4.2. Name-Locator Mapping System (NLMS) (name resolution step)5
4.3. Domain-based Routing.................................... 5
5. Name-based Forwarding (discovery step)....................... 6
6. Delivery step ............................................... 6
7. Security Considerations...................................... 6
8. IANA Considerations ......................................... 7
9. References .................................................. 7
9.1. Informative References.................................. 7
Lee Expires August 15, 2014 [Page 2]
Internet-Draft Scalable Domain-based Routing February 20144
1. Introduction
ICN routing locates a data object based on its name which is
initially provided by a requestor. Currently, the Internet is
addressing on the order of 10^9 nodes, whereas the number of
addressable ICN objects is expected to be several orders of magnitude
higher [ICNRG charter]. Therefore, it raises scalability issues in
routing based on locator and forwarding based on name.
ICN routing may comprise 3 steps: a name resolution step, a discovery
step, and a delivery step [ICN challenges]. Name resolution step is
not the main concern of this memo, but scalable routing in discovery
and forwarding in delivery are mainly described.
In this memo we propose hierarchically-organized domain architecture
with topology reduction for scalable routing, and reactive path setup
for scalable forwarding.
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. Terminologies
o Domain: a logical group of "information objects" which have
similar characteristics (E.g. geographical region, same type of
contents, similar category of contents etc.) or "other domains".
o Domain Gateway: a border gateway for a domain. This domain gateway
exchanges or filters LSAs (Link-State Advertisement) for domain-
based routing, and forwards control messages or data object to the
next-hop domain gateway.
Lee Expires August 15, 2014 [Page 3]
Internet-Draft Scalable Domain-based Routing February 20144
4. Scalable Domain-based Routing
4.1. Hierarchically-organized Domain Architecture
Movie (Id:0x0A)
+-----------------------------------------------------------------+
| <---------> |
| +-----------< user A > |
| | <---------> |
| | ^^^^^^^^ |
| | +--------------------| NLMS | |
| SF (Id:0x0B) | | ^^^^^^^^ |
| +-------------------[GW #1]--------------------------------+ |
| | | | |
| | | | |
| | | | |
| | +-------------------------------+ | |
| | North America | | | |
| | (Id:0x0C) | | | |
| | +----------------[GW #2]-+ Asia Server (Id:0x0D) | | |
| | | | | +=====================+=+ | |
| | | | | | [Snowpiercer] | | |
| | | US server (Id:0x0D)| | | [2009: lost memories]| | |
| | | +=============+ | | | .... | | |
| | | | [StarWars] | | | | | | |
| | | | [Tron] | | | | | | |
| | | | [RoboCop] | | | | | | |
| | | | .... +-----+ | +=======================+ | |
| | | | | | | | |
| | | +=============+ | | | |
| | | | | | |
| | | Canada server | | | |
| | | (Id:0x0E) | | | |
| | | +===============+ | | | |
| | | | [Cube] | | | | |
| | | | .... +---+ | | |
| | | | | | | |
| | | +===============+ | | |
| | +------------------------+ | |
| +----------------------------------------------------------+ |
+-----------------------------------------------------------------+
Figure 1 Sample domain architecture
In this scheme we compose network as a set of domains, and each of
which may be further decomposed into smaller domains recursively. A
domain is a logical group of information objects which have similar
characteristics or other sub-domains. Figure 1 shows an example of
Lee Expires August 15, 2014 [Page 4]
Internet-Draft Scalable Domain-based Routing February 20144
domain architecture. In our scheme contents server itself is also a
domain (see US server, Canada server, and Asia server)
4.1.1. Locator
Each domain has its own ID (domain Id) and a concatenation of domain
IDs from top level domain to the current domain plays the role of
"locator". (E.g. locator for domain North America is 0x0A:0x0B:0x0C).
4.2. Name-Locator Mapping System (NLMS) (name resolution step)
Name resolution step is done by querying locator mapped to a name to
the NLMS. For fast processing we use bloom filter technique. NLMS is
composed as a form of tree. More detailed structure is out of scope
of this memo (it will be written as another I-D).
4.3. Domain-based Routing
Each domain gateway (including contents server, of course) runs
"modified link-state routing protocol". Each LSA transfers "locator"
instead of IP prefix. Thus, locator appears in destination field and
IP address of a domain gateway takes next-hop field of routing table
entries.
Unlike existing link-state routing protocol, each domain gateway
forwards LSA to the other domain according to the following filtering
rule:
o LSAs in tier N domain are forwarded to all domain gateways which
belong to tier N
o LSAs in tier N-1 are injected to tier N
o LSAs in tier N+1 are filtered, LSA which only includes aggregated
locator is injected to tier N instead. (E.g. GW #2 delivers LSA
which includes 0x0A:0x0B:0x0C)
This results in topology reduction effect. Therefore, each domain
gateway would have topology graph which is as reduced as possible in
its current position.
Lee Expires August 15, 2014 [Page 5]
Internet-Draft Scalable Domain-based Routing February 20144
+----------------+--------------+--------+
| Destination | nexthop | out if |
+----------------+--------------+--------+
| 0x0A:0x0C | GW #2's IP | if0 |
+----------------+--------------+--------+
| 0x0A:0x0B:0x0D | - | lo |
+----------------+--------------+--------+
Figure 2 Routing table portion of Asia server
5. Name-based Forwarding (discovery step)
As we described earlier it is very difficult to aggregate flat names.
Thus we chose "reactive path setup" for scalability of forwarding
table.
Detailed procedure of reactive path setup is as follows:
1. A user issues request for certain named content. This request is
forwarded to the default domain gateway ("GW #1" in Figure 1).
2. If the default gateway receives the request from user, it checks
there is any forwarding cache entry matching with the name. If
there is any, it forwards the request to the next-hop domain
gateway according to the found forwarding cache.
3. If there is none, it queries current locator for the name to the
NLMS. After getting the locator for the name, the domain gateway
looks up its routing table entry matching the locator. Finally a
forwarding cache for the name is made by using next-hop
information of found routing table entry. If this is the first
domain gateway which doesn't have forwarding cache for the name,
the domain gateway keeps user request for a while and sends "path
discovery message" including "locator". This will reduce
unnecessary NLMS lookup.
The forwarding cache is managed in "reactive" manner. Unused cache
entries for certain time will be removed immediately.
6. Delivery step
Once user request arrives at the contents server, it can send data
object to the source address of request.
7. Security Considerations
TBD.
Lee Expires August 15, 2014 [Page 6]
Internet-Draft Scalable Domain-based Routing February 20144
8. IANA Considerations
TBD.
9. References
9.1. Informative References
[ICNRG charter] http://irtf.org/icnrg
[ICN Challenges] D.Kutscher, "ICN Research Channelges", internet-
draft, July 2013
[aRoute] Ahmed, Reaz, Md Faizul Bari, Shihabur Rahman Chowdhury, Md
Golam Rabbani, Raouf Boutaba, and Bertrand Mathieu.
"Route: A Name Based Routing Scheme for Information
Centric Networks." In IEEE International Conference on
Computer Communications (INFOCOM) Mini-Conference, 2013.
Authors' Addresses
Joo-Chul Lee
ETRI
161 Gajeong-dong, Yuseong-gu, Daejon
Phone:
Email: rune@etri.re.kr
Lee Expires August 15, 2014 [Page 7]