A New Solution Based on Optimal Link-State Routing for Named Data MANET

Guo Xian,Yang Shengya,Cao Laicheng,Wang Jing,Jiang Yongbo

School of Computer and Communication,Lanzhou University of Technology,Lanzhou,730050,China.

Abstract:NDN is an important instance of Information-Centric Networking.When integrating NDN into MANET,exploring new routing is a necessary task for this research area.The LSAs flooding is a common method to obtain network topology during route establishment.However,the LSAs flooding often results in a broadcast storm in high-density MANET.Using the MPR set proposed in the OLSR can effectively reduce the number of LSAs in the process of route establishment and can further solve the broadcast storm.In this paper,an enhanced neighbor discovery protocol firstly is designed to establish a MPR set.The new protocol can effectively avoid the problem incurred by unidirectional links that impact the network performance in a wireless environment.And then a new and proactive routing NOLSR based on OLSR for NDN-MANET is proposed to support NDN in MANET.And another important work is that NOLSR is implemented on top of NDN Forwarding Daemon NFD.Finally,we make a comparative analysis between NOLSR and the two most relative schemes such as traditional LSA-flooding and the scheme[1]by emulation experiments in the NDN emulator mini-NDN.

Keywords:named-data networking;NLSR;MANET;OLSR

I.INTRODUCTION

With the development of science and technology,the application of MANET has become more and more popular.Researches on MANET applications in the fields of military,disaster relief,VANET and so on have never stopped [2–10].However,these studies were conducted in traditional MANET architecture based on a TCP/IP network.Limited by the TCP/IP structure,each node in traditional MANET needs to use an IP address as its identifier in a network,and data transmission must rely on the end-to-end transmission established in advance based on the IP address.Due to the frequent change in topology caused by the movement of nodes in MANET,this host-centric structure makes mobility and flexibility of the network worse,and the end-to-end delivery of data can’t efficiently take advantage of a broadcast channel in the wireless network [11].The future internet architecture NDN [12,13]can efficiently solve these problems in MANET[4,14,15].

NDN is an instance of Information-Centric Networking(ICN)[16,17].In NDN,the scheme naming data takes place of that naming a host in a traditional IP network.When a consumer wants to request an interested data from a network,it will broadcast an interest packet containing the data name to the network.When a data owner receives the interest packet,a data packet containing the named data in its content will be generated and returned to the consumer according to the reverse path of the interest packet transmission.This original forwarding solution in native NDN is also generally known as “ bread crumb ” routing.It does not require the route establishment process in advance to forward interest packets in order to retrieve data,but rather requires a node to broadcast interest packets to the node where the requested data can be stored.Then,the owner of the data will forward the data along the best reverse path traversed by an interest packet.

Another important feature in NDN is the innetworking caching.That is to say,intermediate nodes that forwarded a data packet are required to store the forwarded data to satisfy potential consumers in the future.So,in NDN,the binding relationship between a node and its IP address is not necessary,and communication between nodes does not require the establishment of the end-to-end connection,which enhances the mobility,scalability,and flexibility of a network.At the same time,other nodes in the network can also store the forwarded data and support multi-path forwarding,which can provide more efficient data distribution than an IP-based network.

Due to these characteristics mentioned above,NDN has a natural advantage when it is applied to mobile Ad Hoc networks such as MANET,VANET and so on[3,4,14,15].The MANET that supported the NDN scheme is abbreviated as NDN-MANET in this paper.

The role of routing in NDN-based networks is to provide a path to the owner of content for an interest/data packet,to avoid broadcast storms caused by blind flooding of interest packets,and further to improve data transmission efficiency.From the perspective of content discovery,existing NDN-MANET routings can be classified into two main types [3,4,10]:proactive routing and reactive routing.In a proactive routing [17–19,1,20,21],the nodes proactively advertise their network status and store content produced by themselves to the network.Each node utilizes the received network information to calculate routes to the content providers in the network in advance,and then update the FIB (similar to the routing table in the IP network,described in 3.1).When a network node receives an interest packet from a consumer to request an interested data,the node will forward the interest packet to a next-hop node according to the routes recorded in FIB.

In addition,the“bread crumb”routing actually is a reactive content routing.Although this scheme is more suitable for dynamically mobile Ad Hoc networks,there are some inherent problems[3,4,10]:(1)Unrestricted interest packet flooding may cause broadcast storm problem;(2)When data packets are transmitted via the reverse path of interest packets,the nodes on the reverse path may have moved;(3)This pull-based communication model is not fit to the large amount of push-based information in some application environment.To resolve the above issues,researchers propose some variants of bread crumb routing,such as timerbased schemes,counter-based schemes,geolocationbased schemes and so on,for different application scenarios[22–30].

In addition,in the VANET community,some researchers focus on machine learning-based solutions to select an appropriate data transmission path [31–33].In [34],a Bayesian-based forwarding decision scheme for an interest packet is proposed in NDNVANET.

However,in above mentioned reactive routing,control overhead generally will waste network resources.A proactive routing that in advance needs to calculate paths to a named data can avoid the broadcast storm in NDN-MANET.Interest packets can be forwarded along these paths instead of blind broadcast.In this paper,we will further improve our new routing NOLSR proposed in[35].NOLSR is a proactive routing protocol based on the link-state Algorithm.We introduce a novel neighbor discovery protocol that provides unidirectional link detection.The new NOLSR also takes advantage of MPR in OLSR[36]to reduce LSAs flooding.Each node selects its own MPR set and only nodes in the MPR set will forward LSAs.Compared with the classic LSAs flooding,NOLSR is optimized in two aspects:(1)Only these nodes in the MPR set will forward LSAs;(2)LSAs only contain information of the originating node and information of other nodes that select this originating node as a node in the MPR set.

In the implementation of NOLSR,we refer to the Named-data Link State Routing protocol(NLSR)[37]and exhaustively illustrate the implementation process of NOLSR.NLSR is also a link-state routing protocol for wired NDN networks.Its implementation utilizes NDN’s Forwarding Daemon (NFD) [38]that makes forwarding decisions for packets originated by NLSR.Similar to NLSR,the code implementation of NOLSR forwarding strategy also depends on NFD.

Finally,we make an emulation analysis for NOLSR in mini-NDN that is an emulation platform for NDN.NOLSR is a proactive routing.Therefore,we make a comparison between NOLSR and the two most relative schemes such as the traditional LSA-flooding and the scheme in [1].The emulation results show that using the MPR set can effectively reduce the propagation number of LSAs compared to blind LSAs flooding.And we also can conclude that the routing scheme[1]and NOLSR can all calculate the routes and be more efficient than the classic LSA flooding scheme in NDN-MANET.And the routing scheme[1]performs better in smaller-scale network,and NOLSR behaves better in larger-scale network.

The remainder of this paper is organized as follows:Section 2 simply surveys the related work.Section 3 introduces preliminaries.Section 4 introduces the basic components of our novel routing protocol NOLSR.Section 5 describes the implementation details of our proposed routing.Section 6 makes a simulation comparison between NOLSR and the scheme [1],classic flooding used for traditional routing protocols and finally,the section 7 concludes our paper.

II.RELATED WORK

Proactive routing is an important routing type in MANET.In the literature [17],a novel solution that proactively constructs a Steiner tree structure by using a Dijkstra algorithm is proposed for NDN-based network,so that a content requester and a content producer are respectively located at a root node and a leaf terminal.Thus,the interest/data packet can be transferred on this tree structure that established in advance.

TOPCCN [18]is also a proactive routing solution.In this solution,HELLO protocol is also used to collect the network status information,and then each node in network will partially set up one-hop and two-hop neighbor information to set up a MPR set.So,TOPCCN also only require nodes in MPR to forward the received interest packet instead of blind flooding.TOPCCN is specially designed for DNDVANET.However,it is not friendly for high speed NDN-VANET.

MobileCCN in[19]is a system that applies Content-Centric Network [13](the architecture is similar to NDN) into MANET.The routing within the system uses the most basic flooding to advertise content proactively.Each node periodically floods its own name prefixes to the network.Other nodes update their forwarding tables according to these name prefixes and request content by flooding interest packets to a network.Due to the simple flooding,there are many flooded packets in the network,and MobileCCN is only suitable for small-scale ad hoc networks.In[1],the authors propose a proactive routing protocol for NDN-MANET in the specific context of disaster relief.In this routing protocol,each node broadcasts its identifier to discover neighbors and synchronizes a same table to provide multipath forwarding.

In addition,integration of SDN and NDN is also a research hot.in the literature [20],a solution is designed based on SDN for NDN-MANET.A controller in SDN is used to make global forwarding decisions according to the collected entire information of network topology.So,the solution is also a proactive routing scheme.Moreover,the solution also considers network resource consumption and network load problems,which helps to improve data transmission performance.

In [21],a secure content routing MPR-SCR is proposed to prevent from selecting nodes that controlled by an attacker when generate a MPR set.In MPRSCR,some security mechanisms,such as cooperative authentication,statistical detection,and voting scheme etc.,are introduced to resolve security issues.By using cooperative authentication based on Merkle Tree,nodes in a network can cooperatively verify a new node that wants to join the network.PIT-based statistical detection,that benefits from NDN’s stateful forwarding feature,and voting scheme are used to prevent from selecting a node that is controlled by an attacker,as a node in MPR.

Contrary to the proactive routing,a reactive routing do not require to proactively discover paths to the content providers in advance,and only flood interest packets to the producer in some manner when needed.The type scheme is more suitable for high-speed movement networks such as VANET.

In[22],the authors propose a reactive routing solution NAIF and make a comprehensive comparison between NAIF and another two schemes such as LFBL[23]and the“bread crumb”routing.The content discovery process of LFBL and NAIF is similar to the“bread crumb” routing.Instead of establishing route entries in proactive routings,these protocols all rely on the reverse path of interest packets to the content provider to transfer the requested content.The difference between these two protocols and the “bread crumb” routing is that LFBL and NAIF optimize the forwarding process of interest packets,and resolves the blind flooding of an interest packet in the“bread crumb ” routing by introducing distance-aware forwarding and neighbor-aware forwarding respectively,which reduces the spread of interest packets.Experimental analysis and comparison show that NAIF has the best performance.Compared with the default“bread crumb” routing,NAIF reduces the bandwidth by up to 54%.

NDN-VANET is a special application scenario of NDN-MANET.Compared with NDN-MANET,NDN-VANET has the characteristics of faster topology change and more interruptible connections.Therefore,it is difficult to implement a proactive routing in NDN-VANET that calculates routes in advance.And most existing NDN-VANET forwarding solutions are reactive routings.A main issue in these solutions is that they can’t adaptively select a forwarding node according to the current network status.

In[24],a controlled transmission scheme of packets is proposed to limit an interest/data packet flooding by using two components such as the hop counter h and the Time To Live(TTL).The hop counter h in any interest packet is used to keep a record of the number of hops experienced by the interest packet,and the Time To Live (TTL) in a data packet is used to limit the number transferred the extra copies of the data packet on the network.

In NDN-based networks,the selection of forwarders of interest packets is calculated via a completely distribution method.In[25],a Distributed Interest packet Forwarder Selection (DIFS) scheme is proposed for NDN-VANET to suppress the broadcast storm problem incurred by the interest packets.In DIFS,each vehicle also need to collet speed,direction,and location information about its neighbors.According to these information,the vehicles distributed select possible forwarding nodes.These nodes generally have the longest connection time and best link quality with other nodes in both front and rear directions.

In[26],a Robust Forwarding Selection mechanism(RUFS)that allows a node received an interest packet selects only one vehicle among neighboring vehicles to forward interest packets is proposed.RUFS uses two data structures:Neighbors Satisfied List (NSL)and Recent Satisfied List (RSL).The NSL contains information about the satisfied interest packets collected by the relevant node by exchanging RSLs with its neighboring vehicles.This information is periodically exchanged by using beacon messages to obtain the latest NSL and select best forwarder of an interest packet.The RUFS can avoid the situation where a single same forwarding node is selected by multiple vehicles,and it can further reduce the probability of conflict and congestion.However,the process that periodically exchange the beacon messages can result in a large overhead.

To improve the broadcast quality of WiFi,a greedy forwarding strategy is proposed in[27].It firstly calculates the distance from the node to the source node forwarded the interest packet when a vehicle node receives an interest packet.And then it will set a random waiting timer that the wait time is inversely proportional to the distance value.If other nodes have forwarded the interest packet during the waiting process,the vehicle node will discard the received interest packet.Otherwise,the interest packet will be forwarded when the timer expires.

In NDN-VANET,the geographical location-based forwarding scheme is an important type.In this class schemes,interest packets are often guided by the geographic location information and forwarded from the sender to those intermediate nodes moving in the same direction.This forwarding strategy can solve the problem incurred by high-speed movement in mobile Ad Hoc networks by limiting the number of transmitted packets.In[28],a Location-Based Deferred Broadcast(LBDB)scheme is designed to improve the efficiency and performance of interest broadcast in NDN-based Ad Hoc networks.The scheme LBDB takes advantage of location information to set up timers when rebroadcasting an interest.

In [29],the geographic location information is bound to a data’s name for making forwarding decision in NDN-VANET.The solution is efficient in highspeed mobile VANET.

In addition,[30]proposes a multi-hop and multipath routing algorithm for NDN-VANET.This routing protocol introduces two new fields which are Target Mac Address and Origin Mac Address in the interest/data packets,PIT and FIB (NDN communication components,described in 3.1)to identify intermediate forwarding nodes.In this way,it can provide multiple paths to provide faster content retrieval speed for NDN-VANET.

In VANET community,some researchers focus on machine learning-based solutions to select an appropriate message transmission path [31–33].The powerful capabilities in processing data of machine learning have been applied to some broadcast suppression techniques based on neighbor information in Ad hoc networks.In [31,32],a scheme based on machine learning is proposed.Nodes in network are required to collect the traffic information such as vehicle density,speed,direction and so on.According to those information,machine learning is used to predict vehicles movement and select an appropriate message transmission path to forward packets.

To resolve broadcast storm,a solution based on machine learning is proposed in [33].The new solution makes use of techniques such as genetic algorithms and particle swarm optimization.In this solution,integrating machine learning into a black-box optimization algorithm to automatically discover a decision threshold value for the distance-to-mean method.

Inspired by [31–33],a Bayesian-based Receiver Forwarding Decision (BRFD) scheme of the interest packet for NDN-VANET in [34],which is adaptive to a dynamic change of network topology.The purpose of this novel scheme is to solve the broadcast storm problem caused by the interest flooding in NDN-VANET.In BRFD,a vehicle that received an interest packet will make a forwarding decision according to the knowledge of network conditions (such as driving speed,driving direction and neighboring information,etc.) learned in the recent period.

III.RESEARCH BACKGROUND

3.1 NDN Communication Model

In NDN,communication between nodes depends on two types of packets:interest packet,data packet[12,13].The communication process is shown in Figure1.The interest packet carrying a content name is used to request an interested data by a consumer and the data packet carrying content is used to forward the requested content to a consumer by a data provider.The entire communication process is divided into two phases:the data request phase and data response phase.In the data request phase,a consumer starts a data request process by sending an interest packet to a network.The forwarding strategy of an interest packet decides how to forward the interest packet on a node in the network,namely,which interfaces are used to forward.The forwarding strategy in the native NDN often uses a broadcast method.That is to say,the consumer first broadcasts this interest packet to its all neighbors.If these neighbors do not store the content,they will continue to broadcast this interest packet until it reaches the content producer.In the data response phase,a content provider returns a data packet carrying content to the consumer according to the bread crumb path of the first received interest packet.It is worth mentioning that the nodes that forward the interest packet in the data request phase are called the intermediate nodes.These intermediate nodes in the data response phase can store this forwarded data packet.In the case when other consumers request the same content again in the future,the intermediate nodes that are closer to the consumer can directly meet the consumer’s request.This mechanism improves content distribution and transmission efficiency.In the end,the consumer will receive the requested data contained in a data packet,which also indicates that a complete communication process has finished.

Figure1.NDN communication principle.

In this communication process,three components such as Content Store (CS),Forwarding Information Base (FIB) and Pending Interest Table(PIT) often play important roles.CS is a repository for content owned by nodes.FIB is similar to the routing table in IP networks in that it provides forwarding paths.To be specific,FIB provides the routes to name prefixes for the forwarding strategy.These routes can be established by routing protocols or added by administrators(operators)manually.However,the forwarding strategy makes the forwarding decisions of interest packets based on but not all of the information in the FIB.There are other factors that influence the final forwarding decision of an interest packet.PIT is used to record the unsatisfied interest packets in the data request phase.It records the upstream and downstream interfaces of each unsatisfied interest packet,that is to say,the inbound interface and the outbound interface.In the data response phase,intermediate nodes forward a data packet to the upstream interface of the corresponding interest packet recorded in PIT hop by hop until the data packet arrives in the consumer.PIT ensures the successful retrieval of data packets from the producer to the consumer and plays an important role in the entire communication process.

3.2 OLSR

OLSR (Optimized Link State Routing Protocol)is a proactive routing protocol for MANET.In order to reduce the network overhead and adapt to the frequent changes of topology in MANET,OLSR proposes an idea of using a MultiPoint Relay (MPR) set to optimize the traditional link-state routing protocol.The MPR set is a subset of a node’s neighbor nodes.The establishment of the MPR set follows the rule that can also reach all two-hop nodes only resorting to parts of one-hop neighbors.So,only these selected neighbors in the MPR set are required to forward packets.Neighbors that are not in the MPR set won’t forward these received packets.The blind flooding in the traditional link-state routing protocols requires all nodes to broadcast the received packets.Using the MPR set aims to replace the blind flooding to reduce the duplicate packets transmitted in the network.The implementation of OLSR mainly depends on two types of packets:Hello packet,TC packet.The Hello packet is required to carry neighbor information and the TC packet is required to carry link-state information.These two types of packets are used in two phases of the route establishment respectively:neighbor discovery and link-state propagation.In the neighbor discovery phase,a node can obtain its neighbor information by periodically broadcasting a Hello packet.The MPR set is established based on the neighbor information carried in the Hello packets.In the linkstate propagation phase,each node uses its MPR set to periodically send a TC packet to the network.Each node obtains the entire network topology and calculates routes to other nodes based on the received TC packets.

IV.NOLSR COMPONENTS

In NOLSR,a new neighbor discovery protocol is introduced.All nodes will broadcast hello packets to discover their neighbors proactively.Based on neighbor information,each node will establish its own MPR set.And then each node will also disseminate LSAs by the established MPR set instead of flooding.According to the topology information obtained during the LSAs propagation process,all nodes will calculate the best route to each name prefix.So,the introduction of the MPR set can reduce the unnecessary flooding of LSAs,further improve the transmission efficiency of LSAs in the network,and solve the problem that proactive routing protocols for NDN-MANET may heavily increase the network overhead.

4.1 Neighbor Discovery Protocol

The new neighbor discovery protocol used in this paper is also called the hello protocol.Each node will periodically broadcast hello packets containing its own network information to its neighbors.Note that the hello packet only exists between neighbors and won’t be forwarded by neighbors again.In other words,neighbors only receive and process hello packets,not forward them.According to the received hello packets,each node will know the existence of neighbors and learn the network information.The network information will be used to detect unidirectional links between neighbors,establish a MPR set(described in 4.2 below) and calculate routes.By putting the network information into hello packet,each node can confirm the connectivity of the bidirectional links without any reply packet,which not only avoids the issues caused by a unidirectional link but also reduces network overhead.

A hello packet will be a special data packet carrying network status and used for neighbor sensing.The format of the hello packet is shown in Figure2.The name of each hello packet follows the form of“/NOLSR/HelloProtocol/router”,where the first two name components are fixed and indicate that this packet belongs to the hello protocol of NOLSR,therouteris the name of a node that originates this hello packet.The content of a hello packet containsrouter energywhich is a value representing the originator node’s residual energy,used for the MPR selection (described in 4.2 below),number of received nodeswhich is a value indicating the number of nodes whose hello packet has been received by this originator node,andReceived Nodes List (RNL)which is a list of the detailed description of these received nodes.Each element ofRNLhas three fields.The first field node indicates the name of a node,the second fieldflag_neighborindicates whether the node is a neighbor of the originator node,the third fieldflag_mprindicates whether the node belongs to the MPR set of this originator node.RNLis mainly used to detect a unidirectional link between two adjacent nodes,which is described in the next two paragraphs.

Figure2.Hello packet format.

In the actual MANET environment,some factors,such as the constrained node energy,the different transmission range and other environmental factors,may cause a unidirectional link issue between nodes[39].For example,we assume that there are two nodesAandBin MANET.For some reason,the signal ofAcan coverB,butBis not in a communication range ofA.Thus,the link fromAtoBis a unidirectional link.The unidirectional link may cause a result thatAconsidersBas a neighbor andBdoesn’t considerAas a neighbor.Finally,wrong neighbor information can be set up in a network,and further will lead to the wrong routing information occurring in a routing table.

Figure3.Neighbor discovery process.

In NOLSR,our hello protocol can not only discover neighbors but also avoids the issues caused by a unidirectional link.Figure3 depicts this process.The rectangles in the figurerepresent the hello packets transmitted between two adjacent nodes.The description in the rectangles represents theRNLcontained in the content of hello packets.Before each node broadcasts a hello packet to its neighbors,it must check whether it has received a hello packet from its neighbors.If it has received before,these received neighbors are added to theRNL.Otherwise,theRNLis empty.Therefore,in Figure3,we note that two adjacent nodesAandBrespectively send a hello packet that theirRNLis empty to the opposite side in the initialization phase of the neighbor discovery.They will send hello packets again after an intervalT.AndRNLof these two hello packets will contain the information of each other because they have received each other’s hello packet before.Note that we assume that two nodes exchange hello packets simultaneously,so theflagneighborinRNLis false.At this time,whenAreceives a hello packet fromB,Awill find a record about it inRNLof this packet.It indicates thatBhas received a hello packet fromAtoo.So,Aconsiders that there is a bidirectional link betweenAandBand setsB’s status as active in its neighbor list.The process is the same forB.In the future,they will exchange hello packets thatflag_neighborabout each other inRNLis true periodically to maintain this active neighbor status.During the neighbor sensing,each node can get active neighbors and get the neighbor’s neighbors(two-hop neighbors) from the neighbor list in a hello packet.According to a principle that a neighbor’s neighbor is a two-hop neighbor,each node can obtain its two-hop neighbors.When the status of a neighbor changes,the node will originate a latest hello packet and an LSA to advertise the latest network status to the network and recalculate the routing table.By putting the link information into the hello packet,the hello protocol can confirm the connectivity of the bidirectional links and avoid the impact of possible unidirectional links in MANET.

In order to speed up network convergence,the hello protocol introduces the validity period of a neighbor.If a node can receive a hello packet from its neighbor within the validity period,the node refreshes the neighbor’s validity period.Otherwise,the node considers that the neighbor isdownfor some reason.It sets the status of the neighbor asinactiveand stops sending hello packets to the neighbor.

4.2 MPR and MPR Selector Set

As a link-state routing protocol,each node needs to disseminate its own LSAs to other nodes.In the classical flooding,each node is required to broadcast all the received LSAs,which may result in that a large number of copies for the same LSA are transferred and further increasing network overhead.In order to reduce the number of LSAs transferred on a network,NOLSR requires that only nodes in a node’s MPR set to forward the received LSAs.So,each node is required to firstly establish its own MPR set.Of course,each node is also required to maintain a MPR Selector set.Here,the MPR Selector set of a selected node is a set of nodes that puts the selected node in its MPR set.As shown in Figure4,the nodeNselects three black nodes in all its one-hop neighbors as nodes in its MPR set.Thus,the node N is also a node in the MPR Selector set of each black node.We can easily get the information needed for MPR selection from the concept of MPR:information about one-hop neighbors and twohop neighbors discovered by the hello protocol.The update of these two sets such as the MPR set and the MPR Selector set depends on the interaction of hello packets in the hello protocol.

Figure4.MPR and MPR selector.

The value of therouter enengyin the hello packet represents the residual energy of a node It is also one of the required information for establishing the MPR set.Therouter energyis an integer from 0-5.When the node is fully charged,the value is 5 As the node works longer,this value gets lower and lower.The higher the value,the more energy the node has,and the greater the probability that the node will be selected as MPR.So nodes with low energy can work for more time.This mechanism enhances the flexibility and scalability of NOLSR.The MPR selection algorithm is shown in Algorithm 1.

?

Firstly,a node calculates the value ofRof each node in its one-hop neighbors,whereRrepresents the number of two-hop neighbors that can reach through this one-hop neighbor.It selects the neighbor who has the highest value ofrouter energyfrom its one-hop neighbors as a node in its MPR set.When there are multiple neighbors with the same value,the one with the highestRis selected.Then,two-hop neighbors that can reach by the selected node are added toCN(Covered Neighbors) set.Finally,the MPR set and the nodes included in theCNset are removed from the set of one-hop neighbors and the set of two-hop neighbors respectively.This iteration process will continue until the set of two-hop neighbors is an empty set.When the iteration process ends,we can get the latest MPR set.

After the MPR set of a node is established,the MPR set will be transferred to all neighbors by theflagMPRfiled ofRNLin a hello packet.In theRNL,theflagMPRof a neighbor selected as a node in the MPR set is set to true,on the contray theflagMPRof a neighbor that is not a node in the MPR set is set to false.When a neighbor receives a hello packet,it checks theflag-MPRfield about itself in RNL.If the neighbor has been selected as a node in the MPR set by the originator node of the hello packet,the neighbor puts the originator node into the set of the MPR Selector.

When the following cases occur,the node will recalculate its MPR set:(1)A node discoveries some new neighbors.(2) The existing neighbor becomesdownor therouter energyof an existing neighbor changes.(3)The set of two-hop neighbors changes.

4.3 LSA Propagation

The purpose of the NDN-MANET routing protocol is to establish paths to every name prefix.Therefore,nodes in NDN-MANET not only need to obtain the topology information but also need to know the name prefixes owned by each node.For this purpose,LSAs of NOLSR are classified into two types:LSAMSandLSANP.TheLSAMScarries the MPR Selector set which recorded as part of neighbors,and theLSANPcarries the name prefixes stored by the node.Similar to the hello packets,the LSAs are also special data packets carrying network information used to establish routes.As shown in Figure5,all LSAs are named according to the name format of”NOLSR/router/LSA/-type/sequence”.Therouterindicates the source node that originates the LSA propagation.Thetypein the formatis nameorMSrespectively indicates that the LSA type isLSANPorLSAMS;Thesequenceis used to determine whether the LSA is the latest.

Content in aLSANPis all of the name prefixes stored in its originator node.In order to reduce the size of aLSAMSpacket,the content in theLSAMSpacket doesn’t contain all neighbors of the originator node,only a part of MPR Selector neighbors.Because each node must establish its own MPR set as a MPR Selector,each node is written to LSAs as a MPR Selector.In this way,althoughLSAMSonly contains partial neighbors,each node can also learn the entire network topology through these LSAs.

Figure5.LSA format.

Each node periodically originates the latest LSA propagation to inform the other nodes of its latest link state through its MPR set forwarding.Of course,each time a new LSA is originated,thesequencein the LSA name is incremented by one.When the link fluctuation causes a change of the MPR Selector set,even if it is waiting for the next newly originatedLSAMS,the node immediately originates a newLSAMSpropagation to the network to inform the other nodes of the latest neighbor information.Similarly,when the node adds or deletes any name prefix it also immediately originates the latestLSANPtransmission to propagate this change to the network.

When a node receives a new LSA,it first compares thesequenceof the received LSA with the highest number received before.If it is lower than the highest number received before,this may be due to the illegal LSA caused by the network delay or other factors.The node directly discards the LSA.When it is higher than the highest number,the content of the LSA is processed and the highest number is updated with thesequence.Processing different types of LSAs have different operations.When processing aLSANP’s content,the node updates the Name Database (NDB)that holds name prefixes for each node.When processing aLSAMS’s content,the node updates the topology table.The table holds information about the reachable node and the last hop node that can reach this node.The format of each entry is (destnode,lastnode).Each MPR Selector of aLSAMSin the content is a neighbor of theLSAMSoriginator node,which means that each MPR Selector can be reached through the originator node.Therefore,we use each MPR Selector as the destination node.And the LSA originator node is the last hop node that can reach the destination node.Then the topology table entry in the form of(MPR Selector,Originator Node)is added.

4.4 Routing Algorithm

NOLSR calculates multi-hop routes between every pair of nodes in a network.According to the set of one-hop neighbors and the set of two-hop neighbors established by the hello protocol and the topology table established by the received LSAs,NOLSR uses the Dijkstra algorithm [40]to calculate the optimal path to each node from a node.Algorithm 2 shows the process of establishing a routing table.First,onehop and two-hop neighbors are added to a routing table with the distance of one-hop and two-hop respectively byiteration1anditeration2.Theniteration3iterates each entry in the topology table set to find the entry in which thelastnodeis a two-hop neighbor.The correspondingdestnodein the entry is a node that can reach through this two-hop neighbor and clearly,the distance is 3 hops away.In order avoid a network loop,thedestnodeis added to the routing table when there is not a route entry to thedestnodein the routing table set and there exists a route entry to thelastnode.Iteration3continues to discover the paths of the four-hop,five-hop nodes,and so on until the routes to the entire network are established.It should be noted that whenever a node is added to the routing table,NOLSR will lookup name prefixes owned by the node in the NDB.According to the NDB entries about the node,the path to all the name prefixes owned by this node can be obtained.Finally,paths to all the name prefixes in the entire network can be calculated.

?

Figure6.NOLSR architecture.

V.NOLSR IMPLEMENTATION

5.1 Overall Architecture

In NDN-MANET,the node plays two kinds of roles:host and router.As a routing node,its architecture is shown in Figure6.NFD is a module designed for NDN to forward interest/data packets.All packets originated by a node itself or received from other nodes are processed by NFD.NFD will make a process decision to forward,discard or store a packet when it receives a packet.The NOLSR module will provide a route to forward an interest packet to retrieve a data packet.The process of a hello packet or a LSA packet originated by NOLSR relies on the packet forwarding module,namely NFD.In order to distinguish NOLSR’s packets used to establish a route in NDN-MANET from NDN’s common packets used for data transmission between a consumer and a data provider,we design a Data Filter module to intercept the NOLSR packets.As shown in Figure7,when the NFD module receives an external packet from other nodes on the network,it first uses the Data Filter to identify the type of this packet.If this packet meets the judgment conditions(described in Figure7.later)set in Data Filter module,which indicates that it is a NOLSR packet,NFD will deliver it to the NOLSR for further processing.Otherwise,it is an interest/-data packet used for NDN communication.NFD will directly process it to get a forward decision as usual.When the NOLSR sends a hello or LSA packet for establishing a route to the network,it will send the packet to NFD firstly,and then the packet will be forwarded to the external network by NFD.Since the processes of NFD and NOLSR are locally independent in a node,their communications between them are performed by Unix domain sockets as shown in Figure6.

Figure7.NOLSR packets process.

The Data Filter of NFD is a filter based on the proposed naming scheme of a NOLSR packet.Both the hello and LSA packet of NOLSR have a fixed name format respectively.The type of packet is identified by its name format to achieve the purpose of intercepting a NOLSR packet.The detail of the Data Filter is shown in Figure7.When the NFD receives an external or local NOLSR packet from interface 1 or 2 in Figure6,the Data Filter will identify the packet and then make a judgment according to the different type of a packet.If a local hello or LSA packet generated by the node itself is received,it is broadcasted to all the neighbors.If an external hello or LSA packet is received,it is forwarded to local NOLSR for processing.Similarly,there is also a Data Filter inside NOLSR to identify the type of received NOLSR’s packets.When receiving a NOLSR packet which has been intercepted by NFD (interface 3 in Figure6),the Data Filter of NOLSR will identify the type of the packet and different types of packets are processed by different modules respectively illustrated in 4.1 or 4.3.

5.2 Main NOLSR Modules

The implementation of NOLSR depends on seven main modules,which cooperate closely and depend on each other.The table 1 describes the function of each module.Among them,hello protocol,algorithm,and LSA are the three most important modules in NOLSR,which are responsible for implementing neighbor discovery,LSA propagation,and route calculation respectively.The Network Information Base(NIB) module is used to store all network information.The Unix Face module provides an interface for communication between different processes in a node.The Data Filter module is used to identify the type of NOLSR packets.In addition,there are other modules that implement some non-core functions.

Table1.The description of NOLSR modules.

In fact,in the specific implementation process,each module is a class.These classes provide the various functions of NOLSR.As shown in Figure8,the UML class diagrams show more details of how NOLSR was implemented at class level.The NOLSR class is the core of the routing protocol,which schedules all classes.The main function of the algorithm class is to establish routes and generate a MPR set of the node in the network.Information required in these calculations is stored in the NIB.For example,the topology information and NDB are necessary for route calculation and neighbor information is required to set up the MPR set of a node.When these processes are finished,the routing table and MPR information stored in NIB will be updated by the algorithm class.In addition,the algorithm class also will inform the latest calculated routes to the NFD module.

Figure8.UML class diagram for NOLSR class.

The main function of the hello protocol class is to implement neighbor discovery.When the hello protocol class originates a hello packet,it needs to obtain the neighbor information written into the hello packet from NIB.Then,the hello protocol class will utilize the Unix socket provided by the Unix Face class to send the hello packet to NFD.And NFD will send the hello packet to the external network.When the status of neighboring changes,the hello protocol class will update the neighbor information stored in NIB,trigger the LSA class to originate the latest LSA,and the algorithm class to recalculate the MPR set.

The main function of the LSA class is to utilize the calculated MPR set to propagate LSAs and process the received LSAs to update the topology information in time.Similar to the hello protocol class,the LSA class also depends on the Unix socket during LSAs forwarding.In addition,when receiving or originating a new LSA,the LSA class will update the topology information in NIB and trigger the algorithm class to recalculate routes.

5.3 NOLSR Working Mechanism

When a network is initialized or a new node joins into a network,a node begins to run NOLSR to establish routes.The successful establishment of a route requires cooperation between various NOLSR modules on a node.Figure9 shows the working mechanism between modules on a node during route establishment.First,a node that wants to establish a route broadcasts hello packets to the network to discover its neighbors by using the hello protocol.Of course,its neighbors also send hello packets to it.When the node’s NFD module receives a hello packet from a neighbor,the NFD’s Data Filter will identify the packet and hands it over to NOLSR for processing.In NOLSR,its Data Filter will continue to identify types of the packet and hand it over to the hello protocol.If the status of a neighbor has been changed,the node will update its neighbor information stored in NIB according to the content of the hello packet.Changing a neighbor’s status can also trigger a new calculation process for a MPR set.Then,the latest MPR set will be timely updated in NIB.The node will also request the latest link state stored in NIB to originate the latest LSA,further to inform the latest neighbor information to the other nodes in the network.The forwarding of LSAs relies on NFD,so NOLSR will deliver the latest LSA to NFD to send it to other nodes in the network.After the latest LSA is propagated,NOLSR will calculate the latest routes based on the latest topology information and store the latest routes in NIB.Finally,NFD will update its own FIB according to the routes calculated by NOLSR and provides a path for potential forwarding in the future.The node has completed its own route establishment process by now.

Figure9.Route establishment and maintenance process.

After the route is established,a node will maintain its routing table in time.In the route maintenance phase,only when the status of a neighbor changes compared with that in the route establishment phase or when a new LSA is received (LSA originated by a new node or the LSA of an existing node with its content changed),the node will recalculate its routes.Then the new route will be sent to NFD to update FIB.

5.4 NOLSR Testing

We test the feasibility of NOLSR in NDN emulator Mini-NDN.As shown in Figure10,the testing network topology consists of ten nodes and fourteen links that connect them,where a link indicates two nodes are in a mutual wireless communication range.After the network emulation starts,the node acts as a ndnServer that provides a name prefix “ndn/a-site/a”.The connectivity between the nodes a and b,c,d is tested by using the ndnping command offered by the Mini-NDN.According to the log files of these four nodes in Figure11 (a),it shows that the other three nodes can access the name prefix of node a.In addition,routing entries calculated by the node a can be showed through the commands of the routing table in the Mini-NDN.Figure11(b)demonstrates that nodes in NOLSR can calculate paths to other nodes.

Figure10.Network topology snap.

VI.SIMULATION ANALYSIS

This section evaluates the performance of NOLSR with different network sizes.Most existing routing schemes belong to reactive routing.So NOLSR is only compared with the proactive routing scheme in [1]and LSA flooding-based forwarding from three different aspects:the network convergence speed,the total number of packets forwarded on the network,and the average number of packets forwarded by each node.All experiments are done in platform Mini-NDN.All the experiments works on a computer with an Intel i3-7100 CPU.The number of nodes in the experimental topology will be incremented from 10 to a maximum of 60.Constrained by the computational resources,in order to reduce the number of data packets forwarded on a network in the same period and to reduce the CPU overhead,all the transmission interval of periodic packets is set to 10s.

Figure11.Test result.

Figure12.Convergence speeds in different-scale networks.

The convergence speed refers to the time it takes for a node in a network to capture the latest topology.Whether a network can converge in a short time is the most basic standard for measuring a routing protocol.The convergence speed is also an important parameter showing the performance of a routing protocol.Figure12 shows the convergence speed of the routing scheme in [1]and NOLSR.The two curves in Figure12 reflect the different convergence times from initialization to obtain the entire network topology as the network scale expands.It indicates that all nodes in two different routing schemes can successfully obtain the entire network topology information and calculate the best route to each node.As the size of the network increases,the convergence speed becomes slower and slower.By the trend of two curves in Figure12,we can draw a conclusion that the routing scheme in [1]converges faster than NOLSR in small-scale networks and NOSLR performs better in large-scale networks.In addition,limited by our computer resource,the transmission interval 10s of packets in the experiment makes the convergence speed of more than 26s seem much slower.In the actual NDNMANET,both the transmission intervals of the packets should not be so long,and the convergence speed should not be such slow.

Figure13.Number of LSAs forwarded in different-scale networks.

In order to verify whether using a MPR set in NOLSR can effectively reduce the number of packets forwarded and reduce the network overhead,we compare it with the routing scheme[1]and the classic LSA flooding which is the most popular method in proactive routing protocols for NDN-MANET.Specifically,the total number of forwarded packets in these three different schemes within two minutes after initialization is calculated respectively.Moreover,in order to analyze the performance of three schemes when the network size increases,we compare the total number of packets of six networks with different numbers of nodes(from 10 to 60).Figure13 shows that:(1)The MPR mechanism of NOLSR and the routing scheme[1]differs greatly from the flooding over the total number of packets.The introduction of a MPR set in NOLSR and the routing scheme[1]can greatly reduce the number of packets in the network.(2)The routing scheme[1]has a better performance than NOLSR in small-scale networks.But when the network size increases,the number of packets of NOLSR is less than the routing scheme [1].This shows that NOLSR is better than the scheme in [1]as the number of nodes increases.That is to say,NOLSR is more suitable for a larger-scale network.

In order to compare the performance of the three routing schemes in a more intuitive way,we select the topology of 30 nodes and count the growth trend of the number of packets forwarded by the three routing schemes every 15s within two minutes.Figure14 shows the specific trends of these three schemes.The curve of NOLSR and the routing scheme [1]is more gradual than that of the classic LSA flooding.And the speed of packets growth of the routing scheme [1]is slower than NOLSR in the early stages,faster in the late stages.In addition,as time goes on,the numbers of packets forwarded by the three schemes are getting much more different.The advantage of NOLSR in reducing LSAs flooding is also becoming more and more obvious.

Figure14.Average number of packets forwarded by per node.

Therefore we can conclude that the routing scheme[1]and NOLSR can all calculate the routes and be more efficient than classic LSA flooding scheme in NDN-MANET.And the routing scheme[1]performs better in smaller-scale network,and NOLSR behaves better in larger-scale network.

VII.CONCLUSION

Replacing IP with NDN in MANET can solve the problem of lacking mobility for end-to-end transmission mode in a traditional IP network.A routing protocol for NDN-MANET aims to provide a path to forward a named data and to avoid the broadcast storm issue.So,we propose the proactive routing protocol,NOLSR,which is applied to NDN-MANET.The main mechanisms of NOLSR are as follows:(1) The hello protocol is used to discover neighbors and two-hop neighbors;(2)The MPR-based forwarding reduces the flooding of LSAs in the network.The experimental results tested in Mini-NDN show that NOLSR can successfully converge,calculate the routes to the entire network,and reduce the number of LSAs flooded.Our future work will focus on the optimization of routing algorithms for NOLSR,which can provide multiple forwarding paths for a named data to enhance the data distribution in NDN-MANET.

ACKNOWLEDGEMENT

This work is supported by NSFC No.61461027,No.61562059;Innovation Promotion Education Fund of Ministry of Education 2018A05003;Gansu province science and technology plan project under grant No.20JR5RA467.We thank the referees for their helpful comments.