Scalable Hybrid Routing for Information-Centric Networks
Author(s): Haibo Wu, Jun Li, Yi Sun, Haiyong Xie, Guoqiang Wang
Name-based routing in information-centric networks faces many challenges, one of which is the scalability challenge; in particular, content routers may not have sufficiently large FIB to store a large portion of name prefixes, even if the latter are...
Information-Centric Networking Research H. Xie Group Huawei & USTC Internet-Draft Y. Sun Intended status: Informational Institute of Computing Expires: August 22, 2013 Technology G. Wang Huawei (USA) H. Wu J. Li Institute of Computing Technology February 18, 2013 Scalable Hybrid Routing for Information-Centric Networks draft-xie-icnrg-hybrid-routing-00 Abstract Name-based routing in information-centric networks faces many challenges, one of which is the scalability challenge; in particular, content routers may not have sufficiently large FIB to store a large portion of name prefixes, even if the latter are aggressively aggregated. In many ICN designs routers have to rely on inefficient mechanisms (e.g., Interest broadcast in content-centric networks) in order to route requests. In this draft, we describe a hybrid, reactive routing approach, where we augment the information-centric network design with an Infrastructure Information Base (IIB) to reap the benefits of both name-based and infrastructure-based routing. Simulation-based evaluations demonstrate that this scheme can significantly improve the network scalability by cutting down the number of broadcast packets while maintaining the same level of the user-perceived latency. 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). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. 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." Xie, et al. Expires August 22, 2013 [Page 1] Internet-Draft ICN routing February 2013 This Internet-Draft will expire on August 22, 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. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Xie, et al. Expires August 22, 2013 [Page 2] Internet-Draft ICN routing February 2013 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Key Observations and Design Considerations . . . . . . . . . . 5 3.1. Proactive Routing vs. Reactive Routing . . . . . . . . . . 5 3.2. Interest Broadcast . . . . . . . . . . . . . . . . . . . . 6 3.3. Interest Starvation Problem . . . . . . . . . . . . . . . 7 4. A Hybird, Reactive Routing Scheme for ICN . . . . . . . . . . 8 4.1. Content Router . . . . . . . . . . . . . . . . . . . . . . 8 4.2. Packet Format . . . . . . . . . . . . . . . . . . . . . . 11 4.3. Packet Handling . . . . . . . . . . . . . . . . . . . . . 12 4.3.1. Handling Interest Packet . . . . . . . . . . . . . . . 12 4.3.2. Handling Data Packet . . . . . . . . . . . . . . . . . 13 5. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 13 6. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 14 7. Acknowlegements . . . . . . . . . . . . . . . . . . . . . . . 14 8. Security Considerations . . . . . . . . . . . . . . . . . . . 14 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 10. Informative References . . . . . . . . . . . . . . . . . . . . 14 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 15 Xie, et al. Expires August 22, 2013 [Page 3] Internet-Draft ICN routing February 2013 1. Introduction Recently Information-Centric Networking (ICN) has become an increasingly popular research topic and many exciting efforts have been made. Among these efforts, two closely related proposals, Content-Centric Network (CCN)  and Named Data Networking (NDN) , are attracting more and more attention. It has been a common belief that future networks are likely content-centric or information-centric, enabling the paradigm shift from the traditional "host-to-host" communication model to the ``host-to-content'' or ``host-to-information'' model. Researchers have made rapid progresses towards this direction in recent years. The name-based routing adopted by many ICN designs enables the new ``host-to-content'' or ``host-to-information'' communication model. In many ICN designs, content and information objects (referred to as content for short hereafter) have structured names. A content origin who owns the original content objects announces name prefixes into the network. Such announcements can be propagated throughout the network (e.g., via intradomain routing protocols such as OSPF). For instance, in CCN, the Forward Information Base (FIB) in each router stores to which interface ("face") the router should forward any request for a named content matching a given name prefix. Upon receiving name prefix announcements, each router updates its FIB accordingly. Clients send Interest packets requesting for interested content, and the network responds with Data packets of the requested content. ICN also introduce two new components to content routers: Content Store (CS) and Pending Interest Table (PIT). CS is leveraged to store cacheable content objects in order for efficient content distribution, and PIT is used to aggregate pending Interests for the same content and propagate Data packets, potentially in a multicast manner, towards the requesting clients. 2. Challenges Name-based routing in information-centric networks also poses new concerns on network scalability. We use CCN as an example to illustrate the main concerns: o Firstly, name prefix announcements in ICN have to be propagated throughout the network via either intradomain protocols such as OSPF or the like. However, the number of distinct name prefixes is expected to be enormously large; for instance, Google announced in July 2008 that the number of unique URLs it processed had exceeded 1 trillion. Even after extremely aggressive aggregation, the top-level name prefixes could still be enormously large. Statistics have shown that as of December 2011, the Internet has Xie, et al. Expires August 22, 2013 [Page 4] Internet-Draft ICN routing February 2013 more than half a billion domain names and that the number of domain names has doubled in the past three years. To propagate such an enormously large number of name prefixes can be a daunting task in that it could not only dramatically overload routers but also consume a significant portion of network bandwidth. o Secondly, the number of name prefixes is likely to be multiple orders of magnitude larger than what FIB can store, and the gap between these two mismatching numbers is likely to sustain. Hence, only a small portion of name prefixes could possibly be put in FIB. As a result, FIB misses (i.e., FIB has no knowledge about where to forward Interests) could be common and name-based routing has to heavily rely on some fall-back schemes (e.g., broadcast Interests), most likely on the slow path, to address FIB misses. This could dramatically degrade network performance and user experiences. o Last but not least, the current fall-back scheme adopted in CCN, namely, flooding Interests via broadcast on FIB misses, could become another dominating source overloading routers, consuming a significant portion of network bandwidth, and degrading network performance. In this draft, we consider the number of flooded packets as a metric suggesting the level of scalability, and describe a hybrid, reactive name-based routing approach in an attempt to address the aforementioned challenges on scalability in ICN. 3. Key Observations and Design Considerations We first describe a few key observations and design considerations in order to help understand the aforementioned challenges. We use CCN as an example scenario for concreteness. 3.1. Proactive Routing vs. Reactive Routing In many of the current ICN design, content origins (or their first- hop routers) are expected to pro-actively and periodically announce name prefixes that are owned by them, similar to how IP prefixes are announced in an intradomain network. We refer to this scheme as the proactive routing scheme. For example, in CCN, re-using intradomain routing protocols (e.g., OSPF with ICN adaptation) is proposed to propagate name prefixes to all routers in intradomain networks (see, e.g., ). However, proactive routing schemes face significant challenges due to the fact that the number of name prefixes can be tremendously large Xie, et al. Expires August 22, 2013 [Page 5] Internet-Draft ICN routing February 2013 in practice. This has significant impacts on both network control overhead and FIB. More specifically, it is likely that the number of name prefixes is at least at the scale of domain names in the Internet, such re-use of OSPF-like proactive schemes could easily lead to stringent challenges on network scalability. For instance, assuming domain names with an average length of 16 bytes, announcements of 0.5 billion domain names can generate as high as 8 billion bytes of traffic; if these names are announced in 1-minute intervals, then on each network link, the average bandwidth consumed by periodical active announcements alone is about 1 Gbps. Moreover, most likely the number of name prefixes, even after aggressive aggregation, is still much larger than the number of domain names. If the former is 10 times larger, then link bandwidth consumption due to name prefix announcement alone can be as high as 10 Gbps. At this scale, it is likely that FIB can only store a limited, small number of name prefixes; thus FIB misses are not uncommon. An alternative approach is the reactive routing scheme; namely, name prefixes are announced only when Interests for those prefixes are injected into the network. We believe that this scheme can be more preferable in information-centric networks. On the one hand, proactive announcements consume a significant portion of network bandwidth and may overload routers. When taking content popularity into account, announcing name prefixes for rarely or never accessed contents significantly wastes network bandwidth. On the other hand, because FIB sizes are multiple orders of magnitude smaller than the number of name prefixes, most name prefixes would not be able to fit in FIB; therefore, announcing such name prefixes not only wastes network bandwidth but also overload routers. The rationale behind the reactive routing scheme is that since FIB misses are inevitable, we should not require all names prefixes be squeezed into FIB (aggregation can still help to put as many prefixes as possible into FIB though). Instead, only those name prefixes that can maximize the network utility (e.g., reduce extra control overhead or service latency) should be put in FIB. Thus, FIB has eviction policies that regulate which entries should be kept in or evicted from FIB. To some degree, FIB exhibits behaviors similar to the content cache, except that the former stores name prefixes while the latter stores named data. 3.2. Interest Broadcast The preceding description suggests that FIB misses could be common in ICN when the number of name prefixes is large. FIB misses directly lead to Interest broadcast, which content routers have to rely on as the fall-back flooding mechanism to "search" for the content origin or a router that can fulfill the request. Therefore, Interest Xie, et al. Expires August 22, 2013 [Page 6] Internet-Draft ICN routing February 2013 broadcast is likely common and can thus incur significant extra overhead to the network. FIB hits, on the other hand, reflect a router's awareness of the content origin and enables the router to forward Interests to designated faces without flooding the network. However, FIB hits are likely heterogeneous; namely, an Interest resulting a FIB hit at one router may result a FIB miss at another, due to the fact that different router may decide to put different sets of name prefixes in their FIB. As a result, a previously FIB-hit Interest may still be broadcast by routers en route towards the content origin. It is favorable to leverage FIB hits as much as possible in a collective manner to reduce the number of flooded Interest as well as Data packets. 3.3. Interest Starvation Problem In CCN, Interests can be held "pending" in PIT. An Interest is pending if another Interest for the same content has been previously forwarded out but the corresponding Data has not been received yet, and it has not yet been timed out in PIT. Upon receipt of an Interest requesting for the content that has been requested by an existing pending Interest in PIT, a content router does not forward it; instead, the router uses PIT to track which incoming face(s) it receives the Interest. Thus, forwarding duplicate Interests for the same content can be avoided. (origin) (Client B) 8 2 5 4 1 7 +--------+---------+--------+-------.-------+ | | | | | | | | | | +--------+----.----+--------+---------------+ 9 6 3 0 10 (Client A) Figure 1 : Interest Starvation Problem However, this design could lead to an Interest Starvation Problem, which we illustrate in the example network shown in Figure 1. This network is an abbreviated figure of the Abilene network topology (left: west cost, right: east coast). In this example, Client A (connected to router 3) sends an Interest for a content owned by the origin connected to router 8. Router 3 broadcasts the Interest to its neighbors 5, 6 and 0. Xie, et al. Expires August 22, 2013 [Page 7] Internet-Draft ICN routing February 2013 Some of the Interests broadcast towards the east coast, however, will never reach the origin. One can observe that the Interest forwarded from 1 to 7 and the Interest from 7 to 1 will both lead to a PIT hit at router 7 and 1, respectively (and thus no further counterclockwise Interest forwarding to 4 or even 5). Consequently, when router 5 receives the returned Data, it will not forward it to router 4, as its PIT does not have a pending Interest coming from 4. In other words, although router 4's and 1's PIT has a pending Interest, they are unlikely to receive the Data. This in turn results in the starvation of future Interests requesting for the same content. For instance, when Client B requests for the same content at a later time (but before PIT expires the pending Interest), router 1 does not forward the Interest due to PIT hit. In this case, B may only be able to successfully receive the data when the corresponding PIT entry expires in router 1. Note that for any new content which has not been requested for, it is more likely that the interest starvation occurs in flash crowd scenarios, and such starvation can happen within a limited duration (mainly determined by the timers expiring pending PIT entries). However, it is likely in practice that FIB has misses, thus interest starvation could still occur even for old content. 4. A Hybird, Reactive Routing Scheme for ICN We describe the details of a hybrid, reactive routing scheme for ICN. For illustration purposes, we use CCN as a concrete example of ICN to describe the design details. The rationale behind our design is to leverage infrastructure-oriented routing whenever possible and reap the benefits of both name-oriented and host-oriented routing. 4.1. Content Router We make the following changes to the original CCN content router architecture, as shown in Figure 2. A complete CCN content router is depicted in Figure 3. Xie, et al. Expires August 22, 2013 [Page 8] Internet-Draft ICN routing February 2013 Index Ptr Type Reachability Info Base Forwarding Info Base +---+-----+ Dest. Forwarding Faces Name Destination List | * | CS | +-------+---------------+ +-------+---------------+ |---+-----| | R1 | 2 | | ... | ... | | * | PIT | |-------+---------------| |-------+---------------| |---+-----| | R3 | 0 | | /e/f | R3,R4 | | * | FIB | |-------+---------------| |-------+---------------| |---+-----| | R4 | 3 | | ... | ... | | * | IIB | +-------+---------------+ +-------+---------------+ +---+-----+ Figure 2 : Augmentation to CCN Content Router Xie, et al. Expires August 22, 2013 [Page 9] Internet-Draft ICN routing February 2013 +----------------------------------------------------------------+ | Content Store Reachability Info Base | | Name Data Dest. Forwarding Faces Face 0 | | +->+-----+----+ +---> +-------+---------------+ +---+ | | | |... |... | | | R1 | 2 | | |----> | | |-----+----| | |-------+---------------| | | | | | |/a/b | | | | R3 | 0 | | |<---- | | |-----+----| | |-------+---------------| +---+ | | | |... |... | | | R4 | 3 | | | | +-----+----+ | +-------+---------------+ | | | | Face 1 | | | +------------------+ +---+ | | | Index | | |----> | | Ptr Type | | | | | | +---+-----+ | | |<---- | +--------------------------| * | CS | | +---+ | | |---+-----| | | | +--------------------------| * | PIT | | | | | |---+-----| | | | | +-| * | FIB | | Face 2 | | | | |---+-----| | +---+ | | | | | * | IIB | | | |----> | | | +---+-----+ | | | | | | | | | | |<---- | | | +------------+ +---+ | | | | | | | Pending Interest Table | Forwarding Info Base | | | Name Requesting Faces | Name Destination List Face 3 | | | +----+-------------+ +--->+-------+---------------+ +---+ | | +->|/c/d| 0,3 | | ... | ... | | |----> | |----+-------------| |-------+---------------| | | | | |/e/f| 0,1 | | /e/f | R3,R4 | | |<---- | |----+-------------| |-------+---------------| +---+ | | |... | ... | | ... | ... | | | +----+-------------+ +-------+---------------+ | +----------------------------------------------------------------+ Figure 3: Augmented CCN Content Router Firstly, we require that every router in the network have a unique name and announce its name to all other routers via available intradomain routing protocols. Secondly, we introduce a new component, the Infrastructure Information Base (IIB), to reap the benefits of infrastructure- oriented routing. Specifically, IIB stores the forwarding face(s) to reach any router in the network. Note that IIB stores reachability information for an intradomain network and in typical intradomain networks the number of routers ranges from a few dozen to a couple of Xie, et al. Expires August 22, 2013 [Page 10] Internet-Draft ICN routing February 2013 thousand. Thus the size of IIB would be less than a couple of thousand. Since we require that routers announce their names using intradomain routing protocols, each router is able to build IIB on their own. Multi-path routing is feasible if multiple forwarding faces are allowed in any IIB entry; however, routing loop prevention schemes should be adopted (we leave it as a future work) Note that if only a single forwarding face is allowed in any IIB entry, then we end up with single-path routing and lose the benefits of potentially multi- path routing in ICN; however, the gain is simplified routing and improved scalability. Thirdly, we change the semantics of the original FIB. Specifically, each FIB entry now stores a name prefix and the names of "landmark" routers for this prefix. We refer to a router as a landmark router for a given name prefix if the router for sure has knowledge about how to reach the origin(s) of the name prefix. For instance, the router closest to an origin can be treated as the landmark router for the name prefixes announced by that origin. Since Data packets bears the origin's name (or an intermediate router's name), upon receipt of such a Data packet, a router can update its FIB accordingly. Lastly, we allow FIB to update its entries (i.e., routes) based on the popularity (or relevant, carrier-chosen measures) of individual routes. To some degree, now FIB is more like a cache for routes. Certain caching policies can be applied to evict cold routes in order to save space for popular routes. Keep in mind that the fall-back mechanisms (e.g., flooding-based mechanisms) can be used as the last resort in case of FIB misses (namely, no route is known for a given name or name prefix). The requests of FIB lookup for popular contents (triggered by interest packets destined for popular contents) account for a majority of the FIB lookup workload, thus storing popular routes is beneficial and improves the overall performance of the network. The other two components, Content Store and Pending Interest Table, remain the same as the original CCN/NDN design. 4.2. Packet Format In the Interest packet, we introduce a Broadcast flag bit to distinguish the broadcast Interest (i.e., B Interest) and non- broadcast Interest (i.e., NB Interest), and introduce a Destination field, as shown in the Figure 3. Xie, et al. Expires August 22, 2013 [Page 11] Internet-Draft ICN routing February 2013 Interest Packet Data Packet +------------------+ +------------------+ | Content Name | | Content Name | +------------------+ +------------------+ | Selector | | Signature | +------------------+ +------------------+ | Destination | | Signed Info | +------------------+ +------------------+ | Broadcast Flag | | Source | +------------------+ +------------------+ | Nonce | | Data | +------------------+ +------------------+ Figure 3: Packet Format An NB Interest is generally produced after a FIB hit at a router. Clearly the router has some knowledge about the content and the origin. In order to better leverage this knowledge, we let the router fill in the Destination field in the NB Interest with the name of a landmark router en route towards the origin (we recommend the router closest to the origin as the landmark). Other routers that receive such an Interest with this field filled out can therefore take advantage of this knowledge; however, it is recommended but not mandatory that routers should use the destination information in its decision process. In a B Interest, the destination field is always left empty. In the Data packet, we introduce a Source field for the content origin's identification, which provides a reference for updating FIB. Note that the origin can obfuscated its own name (e.g., a hash of its name) for privacy preservation purposes. Note also that there can be multiple origins for a given content and that intermediate routers may override this field with its own name. 4.3. Packet Handling We now describe how content routers should handle packets in the reactive routing scheme. 4.3.1. Handling Interest Packet The new Interest handling method is presented as below. According to our preceding description, the unsatisfied PIT hit could cause starvation of future Interests. We address this problem with a novel patch utilizing the broadcast flag. Note that the key property of the starvation is the underlying ring topology (e.g., the ring including routers 3,0,10,7,1,4,5 in Fig. 1) and some routers on the Xie, et al. Expires August 22, 2013 [Page 12] Internet-Draft ICN routing February 2013 ring (e.g., router 1) prohibit forwarding further Interests per their PIT policy (their PIT is in a mistaken state though). This starvation can be prevented by allowing routers such as router 1 to further forward the Interest. In Fig. 1, this corresponds to the Interest forwarding from 1 to 4 and further to 5 (as well as from 7 to 10 and further). When 5 receives the Data packet, this packet will also be forwarded to all routers along the ring. In this way, the broadcast Interest can traverse the ring topology in both clockwise and counterclockwise directions. Consequently, once any router in the ring receives the Data packet, all other routers will eventually clear the corresponding PIT entry. The above strategy indicates the following rule in the treatment of the broadcast Interest: when the broadcast Interest is not from a face existing in PIT (even if the corresponding content is pending), the Interest will still be further broadcasted. Note that in this rule the broadcast Interest from an existing face for the pending content can still be aggregated. For any broadcast Interest, it is eventually replied with the desired content if found in CS. Otherwise, if the incoming faces have no previous requests for the same content, it is broadcasted further if FIB has no destination information for the requested content. However, if FIB does have the destination information, then the Interest will be forward as a non-broadcast Interest (NB) (by changing the broadcast flag bit and fill the destination field) to faces towards the destination. For any non-broadcast Interest, since the destination is already filled, we can directly forward it according to IIB in a unicast manner. We can also fall back to the original CCN/NDN design and adopt a broadcast approach to forward the Interest. Still, we require that intermediate routers directly reply with the content data in case of a CS hit. 4.3.2. Handling Data Packet Handling Data packets is similar to the original CCN/NDN design. When a Data packet matches a PIT entry, it will be forwarded to all faces designated by the PIT entry along with a FIB update. Note that the origin or the router closest to the origin should update the destination field in the packet. 5. Conclusion In this draft, we describe a hybrid, reactive information-centric routing scheme to address the scalability challenge for intradomain networks. In the design, an Infrastructure Information Base (IIB) is Xie, et al. Expires August 22, 2013 [Page 13] Internet-Draft ICN routing February 2013 introduced to augment the original CCN content router design with new packet handling algorithms. The describe reactive routing scheme can lead to less broadcast packets than the original proactive scheme (simulation-based evaluations suggest that the reduction of broadcast packets could be as high as two orders of magnitude). It can also address the Interest Starvation Problem, and effectively reduces the broadcast Interest after the FIB hit. 6. Contributors The authors would like to thank Yang Wang for his many detailed reviews and helpful assistance on this draft. Yang Wang Georgia State University Atlanta, Georgia USA 7. Acknowlegements This memo is based upon work supported in part by the National Science Foundation of China (NSFC) under Grant No. 61073192 and the China 973 Program under Grant No. 2011CB302905. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the funding agencies. 8. Security Considerations Security issues are not discussed in this memo. 9. IANA Considerations This document makes no specific request of IANA. Note to RFC Editor: this section may be removed on publication as an RFC. 10. Informative References  Jacobson, V., Smetters, D., Thornton, J., Plass, M., Briggs, N., and R. Braynard, "Networking named content, in ACM CoNEXT 2009, Xie, et al. Expires August 22, 2013 [Page 14] Internet-Draft ICN routing February 2013 Rome, Italy", Dec 2009.  Zhang, L., Estrin, D., Burke, J., Jacobson, V., Thornton, J., Smetters, D., Zhang, B., Tsudik, G., K. Claffy, K., Krioukov, D., Massey, D., Papadopoulos, C., Abdelzaher, T., Wang, L., Crowley, P., and E. Yeh, "Named data networking (NDN) project, Palo Alto Research Center(PARC), Tech. Rep. NDN-0001", Oct 2010.  Xie, H., Wang, Y., and G. Wang, "Scalable Content Centric Networks via Reactive Routing, in IEEE ICC 2013, Budapest, Hungary", June 2013. Authors' Addresses Haiyong Xie Huawei & USTC Phone: Email: Haiyong.email@example.com Yi Sun Institute of Computing Technology No.6 Kexueyuan South Road Beijing, 100190 China Phone: (86)18611907658 Email: firstname.lastname@example.org Guoqiang Wang Huawei (USA) Phone: Email: Xie, et al. Expires August 22, 2013 [Page 15] Internet-Draft ICN routing February 2013 Haibo Wu Institute of Computing Technology No.6 Kexueyuan South Road Beijing, 100190 China Phone: (86)13811800085 Email: email@example.com Jun Li Institute of Computing Technology No.6 Kexueyuan South Road Beijing, 100190 China Phone: (86)18910572771 Email: firstname.lastname@example.org Xie, et al. Expires August 22, 2013 [Page 16]