Project Topics
Get Complete Project Material File(s) Now! »
Comparison between the various approaches
The aforementioned ICN architectures have similarities and differences in the techniques used for implementing the key ICN functionalities. Tables 2.1 summarize the techniques used by each ap-proach for handling the naming, name resolution and routing, caching, mobility, name data object granularity and security.
In this chapter, we have described five ICN architectures proposed in different projects: DONA, PURSUIT, NetInf, Mobility First, and NDN. However, there exist other architectures that are not described such as: CONVERGENCE [27], Sail [28], COMET [29], 4WARD [30], and ANR CONNECT project funded by The French National Research Agency Projects for science [31] which adopts NDN architecture. Although, the aforementioned architectures propose different ap-proaches, they share the same design paradigm which is centric-content rather than centric-host. In practicability side of view, few of these architectures are declared to be applicable.
We have detailed more the NDN architecture as our contribution are designed according to it. In the next chapter we will investigate the NDN routing issue and we will present the literature related to this topic.
Traditional Routing in IP
In IP architecture, the routers route and forward the packets according to the IP source and des-tination address. The routing plane in IP networks serves to announce IP prefixes, an IP router announces IP prefixes of networks connected to it. Each router announces the IP address of hosts and networks connected to it, and computes the paths. The routing protocols such as Link State or vector distance, OSPF, BGP, etc. are responsible for propagating of announcements through the network, and every router builds its FIB based on received routing announcements and compute the best next hop. Thus, the IP RIB (Routing Information Base), which corresponds roughly to the FIB table in NDN entry usually contains a single best next hop and its information. More specifically, in IP networks the routing plane is responsible for populating the RIB tables of routers and keeping them updated in face of network changes, including both long-term topology and policy changes as well as short-term churns. As result, the routing plane is the control plane, it is state-full, intelligent and adaptive manner. It performs all the work, when the forwarding plane is dumb, one-way traffic, and stateless. Furthermore, at the data plane, routers forward packets strictly following the RIB ta-ble via single interface [22]. Consequently, the robust packet delivery in IP networks depends only on the routing plane.
While the routing plane is responsible of all the work in IP networks, when there is a change in the network i.e. failure detection, routers need to exchange routing updates between them in order to achieve new global consistency. The time period between the instant when a failure is detected at the network and the instant when all routers are updated to a new situation is called the routing con-vergence time. The routing convergence time can be divided into four different components: failure detection, update propagation, route computation and RIB update. As result, in order to reduce packet loss and resume packet delivery after network is updated, IP routing protocols need to con-verge fast. However, fast routing convergence is challenging in large operational networks, because it conflicts with routing stability and scalability i.e. it is very difficult to reach a fast convergence, stability and scalability simultaneously.
The routing stability is very important for applications that suffer from RTT fluctuation. Scala-bility is necessary to support a large network composed from a big number of routers, links and IP prefixes. For example, the distance/path-vector routing protocols, where routers keep only the hops count between them as information that used for route and forward packets, without full knowledge of the topology ensures a better scalability, but the convergence time may be long (tens of minutes). Link-state routing protocols, however, as each router knows the entire topology, can converge fast, but it suffers from poor stability and limited scalability.
Concerning the multi-path routing, in IP network it is considered as challenging, because the IP architecture does not support multi-path routing inherently. Furthermore, multi-path routing needs to maintain routing consistency to make sure there will be no loops. Consequently, the routing plane is responsible to guarantee loop-free paths by the fast convergence when it detects looping packets.
Routing Plane in NDN
In NDN network, the routers route and forward the packets according to names, which eliminates the problems related to IP addresses. First, there is no address exhaustion problem since the names-pace in NDN is unbounded. Second, there is no NAT traversal problem since the routing system does not requires for the hosts to expose its address private or public in order to offer content, but the routers guide back the retrieved data to its requesters according to the interfaces tracks stored in its PIT data structure. Finally, address assignment and management is no longer required in local area networks [9].
The routing plane in NDN serves the same goal like in IP networks. Instead of announcing IP prefixes, a NDN router announces name prefixes that cover the data that the router is willing to serve. The content providers announce the names prefixes and the other routers compute the paths. This announcement is propagated through the network via a routing protocol, and every router builds its FIB based on the received routing announcements [8]. Indeed, the routing plane is responsible for populating the FIB tables of routers and keeping them updated. Any routing scheme that works well for IP should also work for NDN, because forwarding model of NDN is a strict superset of the IP model [6]. So, the conventional IP routing protocols such as link-state, OSPF, etc. can be used in NDN networks. It is worth mentioning that until now there is none standardized NDN routing protocol.
Since NDN network has an intelligent and adaptive data plane, the design of the NDN routing plane can be different from today existing routing plane, as it only helps the forwarding plan by populating the FIB.
Forwarding Plane in NDN
The data plane in NDN network is composed of two-step process: consumers send Interest packets, then Data packets flow back across the same path but in the opposite direction. Therefore, adap-tive forwarding is enabled by this symmetric Interest-data packets exchange and forwarding state maintained at routers [23] [22]. Since, by recording pending Interests and observing Data packets coming back, each NDN router can measure packet delivery performance such as round-trip time and throughput, and can detect the problems that lead to packet losses such as link failures or con-gestion. For example, the requested data is supposed to come back within reasonable time, so if a router does not receive the requested data from the same interface from where the Interest was forwarded in this period (time out), that means something is not right: dropped due to congestion, link failures, loops, etc. So, the forwarding plane can bypass problematic areas by using multiple alternative paths. It is worth mentioning that in [23] [22] it is introduced for the first time the interest Nack. So, when an NDN node can neither satisfy nor forward the incoming Interest, it generates and sends back to the downstream node an Interest Nack, to notify the network problem quickly. An Interest Nack carries the same name as the incoming Interest, plus a code that explain why it was generated.
The forwarding plane can detect and recover from network failures on its own. Indeed, it enables each router to handle networks failures locally and immediately without waiting for the global routing convergence [32]. The forwarding plane can also detect and handle looping packets issue, since each Interest carries a nonce field (a random number) which, together with the Interest name, uniquely identifies the Interest. Furthermore, each router records the nonce of received Interest in the matching PIT entry; hence if the incoming Interest, name plus nonce together, has a matching record in PIT, the incoming Interest is looped and a router drop it. In addition, since the Data packets follow the same paths crossed by the corresponding Interests but in the reverse direction, the Interests packets cannot loop either. As result, an NDN router can forward an Interest using multiple interfaces without worrying about loops.
One of the most important features of NDN is the inherent support of multipath routing ensured by forwarding plane, which prevents the network from packets looping. NDN routers can forward a received packet toward multiple paths i.e. interfaces. Consequently, NDN FIB entry contains a ranked list of multiple interfaces and it records its routing and forwarding planes information. The received interest is send out toward the interface(s) selected by the forwarding strategy module based on routing information, forwarding information, and forwarding policies set by the operator that must take into consideration all NDN features, especially caching.
Routing and Forwarding Coordination in NDN
As we explained in previously section, NDN inherently supports multipath routing. Consequently, each NDN FIB entry contains a ranked list of multiple interfaces and records its routing and for-warding planes information. The former determines which paths are available to forwarding plane, while the latter determines which paths may be used and in which order. At first time the interfaces are ranked according to routing information, but subsequently the interfaces will be ranked ac-cording to both routing and forwarding information. These information are considered as input for the forwarding strategy module, which used them and the coordination between them in incoming Interest forwarding process through the optimal paths toward the request data.
The coordination between routing and forwarding is discussed in [32]. The authors raise the question of whether routing protocols are still needed in NDN. If so, what impact may an intelli-gent and powerful forwarding plane have on the design and operation of NDN routing protocols and to what extent? They found, through extensive simulations and analysis that a routing proto-col is highly beneficial in bootstrapping the forwarding plane for effective data retrieval, efficient probing of new links or recovered links, because routing protocol provides information that reduce probing upon searching the working path. Furthermore, since the forwarding plane is able to detect and recover quickly from network failure on its own, NDN routing does not need to converge fast according to network changes. In addition, routing stability and scalability can be significantly im-proved, because NDN routers can handle network failures at the forwarding plane, and the routing protocol can be freed from short-lived failures. Based on the coordination between NDN routing and forwarding plane, the routing algorithms that would not work fine in IP network may work fine in an NDN network.
Building the FIB table
In NDN, in order to make the data stored on producer available for retrieval. The producer appli-cation firstly registers the prefix of data with the NDN forwarder on the same host machine (i.e., local registration). Secondly, it signals available data, in order to be fetched by remote NDN for-warders. There are many ways to achieve this task: by using the routing protocols such as NLSR, OSPFN, etc. as explained in Section 3.3, or manual configuration, or opportunistic data discovery strategies (e.g., the access strategy, and auto-registration of the specified prefix(es) upon creation of on-demand faces). These methods have different tradeoffs in ease of use, implementation com-plexity, and communication overhead. To address the aforementioned issue an Automatic Prefix Propagation (APP) protocol is proposed in [33]. Automatic Prefix Propagation (APP) enables the local NDN forwarder in one producer to automatically propagate local prefix registrations to the re-mote forwarder on attached router. Local prefix registration triggers the propagation when an active remote NDN gateway exists, while the local forwarder possesses a private key and the correspond-ing NDN certificates that it matches or covers the locally registered namespace. In the case of two or more candidates for the keys/namespace, the selected key corresponds to the shortest namespace. This allows the forwarder to aggregate multiple local registrations into one remote action, reducing communication and bookkeeping overheads. After the initial prefix propagation, NFD (NDN For-warding Deamon) periodically refreshes the registration, unless the prefix is no longer registered locally or there are no NDN gateways configured.
To implement and validate our proposals, the ndnSIM simulator for ns3 [34] has been chosen; because the studies performed in [?] about ICN software tools show that the ndnSIM represents a fairly good compromise between completeness and scalability. Also it is the best one for security and routing issues among CCN/NDN simulators.
In ndnSIM simulator for ns3 [34], the FIB table is built as follow: all forwarding strategies use the FIB (Forwarding Information Base) table for forwarding Interests. By default, all nodes have empty FIB. They need either to manually configure routes, use global routing controller, or (not recommended) enable default routes.
It should be noted that, although OSPF can build a FIB with name prefixes, it has important limitations. One important limitation affects the forwarding strategy, which cannot explore natively multiple paths to retrieve a piece of named data. Consequently, OSPFN limits the effectiveness of the NDN. In order to allow multi-path routing support over OSPFN, the operators may manually configure a list of alternative next-hops and install them in the FIB in addition to the best outgoing interface.
OSPFN is the first routing protocol developed for NDN network, it is a short-term solution to get the NDN testbed operational; it does not support dynamic multipath forwarding and has no mechanism to authenticate routing data [25].
NLSR: NDN Link State Routing
NDN Link State Routing protocol (NLSR) [36, 37], as its name indicates, is a link state routing protocol like OSPFN, developed to replace OSPFN inability. It is an NDN intra-domain routing protocol, that uses names instead of IP addresses to identify the various components of a routing system such as network, routers, processes, data, and key. Furthermore, it uses the packets Interest and Data to distribute routing updates. It can use any underlying communication mechanisms that NDN uses (Ethernet, IP tunnels, TCP/UDP tunnels) for routing message exchanges. NLSR uses hierarchically structured names scheme to identify various components: routers, routing processes, routing data, and keys because the relationship among them is inherently hierarchical.
Table of contents :
1 Introduction
1.1 Scope
1.2 Problem Statement and Objectives
1.3 Dissertation Contributions
1.4 Dissertation Organization
2 Information Centric Networks
2.1 Introduction
2.2 ICN Fundamental Architectures
2.2.1 DONA
2.2.1.1 Naming
2.2.1.2 Name Resolution and Data Routing
2.2.1.3 Security
2.2.1.4 Transport
2.2.1.5 Caching
2.2.1.6 Mobility
2.2.2 PURSUIT (PSIRP)
2.2.2.1 Naming
2.2.2.2 Name Resolution and Data Routing
2.2.2.3 Security
2.2.2.4 Transport
2.2.2.5 Caching
2.2.2.6 Mobility
2.2.3 NetInf
2.2.3.1 Naming
2.2.3.2 Security
2.2.3.3 Transport
2.2.3.4 Caching
2.2.3.5 Mobility
2.2.4 MobilityFirst
2.2.4.1 Naming
2.2.4.2 Name Resolution and Data Routing
2.2.4.3 Security
2.2.4.4 Caching
2.2.4.5 Mobility
2.2.5 Named Data Networking
2.2.5.1 NDN node architecture
2.2.5.2 Forwarding Process
2.2.5.3 Naming
2.2.5.4 Security
2.2.5.5 Transport
2.2.5.6 Caching
2.2.5.7 Mobility
2.3 Comparison between the various approaches
2.4 Conclusion
3 RelatedWork
3.1 Introduction
3.2 Traditional Routing in IP
3.3 Routing Plane in NDN
3.4 Forwarding Plane in NDN
3.5 Routing and Forwarding Coordination in NDN
3.6 Building the FIB table
3.7 NDN Routing Protocols: a survey
3.7.1 OSPFN: OSPF for Named Data Networking
3.7.2 NLSR: NDN Link State Routing
3.7.3 Hyperbolic routing
3.8 QoS based routing in NDN network
3.8.1 Problem Formulation
3.9 Forwarding Strategies: a Survey
3.9.1 High level taxonomy
3.9.1.1 Forwarding strategies that handle the network failure
3.9.1.2 Forwarding strategies that handle the caching issue
3.9.1.3 Forwarding strategies that handle the security issue
3.9.1.4 Forwarding strategies that handle the congestion issue
3.9.1.5 Forwarding strategies with QoS
3.9.1.6 Hybrid forwarding strategies
3.10 Conclusion
4 QoS-based Forwarding Strategy for NDN
4.1 Introduction
4.2 Reinforcement Learning
4.2.1 Mathematical Model of Reinforcement Learning
4.2.2 Value functions
4.2.3 Rewards
4.2.4 Definitions of functions of V-value and Q-value
4.2.5 Value function and optimal policy
4.2.6 Q-Learning
4.3 Our proposal: the QoS forwarding strategy
4.3.1 Functional Model
4.3.2 Designing the QoS forwarding strategy
4.3.2.1 Criterion 1: Bandwidth
4.3.2.2 Criterion 2: Round Trip Time (RTT)
4.3.2.3 Exploration and exploitation phases
4.3.2.4 Forwarding decision-making algorithms
4.4 Performance Evaluation
4.5 Conclusion
5 Ant Colony based QoS aware Forwarding Strategy for NDN
5.1 Introduction
5.2 Ant colony optimization
5.2.1 Meta-heuristic optimization
5.2.2 Ant colony algorithms principles
5.2.3 Ant system
5.2.4 Ant Colony System (ACS)
5.3 Our Proposal: the Ant Colony Based QoS-aware Forwarding Strategy
5.3.1 Designing AC-QoS-FS
5.3.1.1 Criterion 1: Bandwidth
5.3.1.2 Criterion 2: Cost
5.3.1.3 Criterion 3: Round Trip Time (RTT)
5.3.1.4 The moving rule
5.3.1.5 Pheromone update
5.3.2 Forwarding decision-making algorithms
5.3.2.1 After receiving an Interest
5.3.2.2 After receiving a Data packet
5.4 Performance Evaluation
5.5 Conclusion
6 Multi-Criteria QoS-based Forwarding Strategy for NDN
6.1 Introduction
6.2 Our Proposal: Multi Criterion Ant Colony Based QoS-aware Forwarding Strategy( MC-QoS-FS)
6.2.1 Designing MC-QoS-FS
6.2.1.1 The moving rule
6.2.1.2 Pheromone update
6.2.2 Forwarding decision-making algorithms
6.2.2.1 After receiving an Interest
6.2.2.2 After receiving a Data packet
6.3 Flow Congestion Reduction Ant colony based Quality of Service aware forwarding strategy (FCR-QoS-FS)
6.3.1 Designing of FCR-QoS-FS
6.3.1.1 Criterion 1: Bandwidth
6.3.1.2 Criterion 2: Cost
6.3.1.3 Criterion 3: Round Trip Time (RTT)
6.3.1.4 Criterion 4: Interest Arrival Rate (IAR)
6.3.1.5 Criterion 5: Data Satisfaction Rate (DSR)
6.3.1.6 Computing Node IAR and DSR
6.3.1.7 Updating of the IAR and DSR path
6.3.1.8 The moving rule
6.3.1.9 Pheromone update
6.3.2 Forwarding decision-making algorithms
6.3.2.1 After receiving an Interest
6.3.2.2 After receiving a Data packet
6.4 Performance Evaluation
6.5 Conclusion
7 Conclusion
7.1 Summary of Contributions
7.2 Future work
7.3 Publications
8 Version Franc¸aise Abr´eg´ee
8.1 Contexte G´en´eral de la th`ese
8.2 Probl´ematique
8.2.1 Routage et acheminement des paquets dans NDN
8.2.2 Routage avec Qualit´e de Service
8.2.3 Formulation du Probl`eme
8.3 Nos contributions
8.3.1 QoS-FS : Strat´egie d’acheminement bas´ee sur la QoS pour NDN
8.3.2 AC-QoS-FS : Strat´egie d’acheminement avec qualit´e de service bas´ee sur les colonies de fourmis
8.3.3 MC-QoS-FS : Strat´egie d’acheminement bas´ee sur multi crit`eres de qualit´e de service
8.4 Conclusion
