NDN Routing Protocol Overview
Explore the NDN Routing Protocol, including NLSR features, motivation, contrast with Distance Vector Routing, components of NDN's Forwarding Plane, and forwarding process at an NDN node. Understand the concepts and workings of named-data networking for effective data routing.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
NLSR: Named-data Link State Routing Protocol The 3rd ACM SIGCOMM workshop on Information-centric networking, 2013 A K M Mahmudul Hoque, Syed Obaid Amin, Adam Alyyan, Beichuan Zhang, Lixia Zhang and Lan Wang 1
Motivation The previous version of NDN routing protocol is Open Shortest Path First for Named-data (OSPFN), which is an extension of Open Shortest Path First (OSPF). OSPFN features: 1. IP addresses as router IDs 2. Generic Routing Encapsulation (GRE) tunnels to cross legacy network 3. One single best next-hop provided for each name prefix Problems of OSPFN: 1. Difficulty of managing IP addresses and tunnels 2. Inadequate multipath support (This limits NDN s effectiveness.) Name Data Network (NDN) becomes one of the main topics in our laboratory. Let s know more about NDN. 2
NLSR (Named-data Link State Routing protocol) NLSR runs on top of NDN. NLSR disseminates Link State Advertisements (LSAs) to both build a network topology and distribute name prefix reachability. Features: 1. Naming: NLSR uses names, instead of IP addresses to identify routers and links. 2. Information Dissemination: Routing messages exchange by NDN s Interest/Data packets. 3. Multipath: The route computation produces multiple shortest paths and ranks the next-hops to facilitate multipath forwarding. 4. Trust: NLSR directly benefits from NDN s built-in data authenticity. 3
Link State Routing Protocol CONCEPT: 1. The routing information of each node is known by all the nodes while a network of topology changes. 2. Each node constructs a map of the connectivity to the network. 3. Each node independently calculates the next best logical path from it to every possible destination in the network. CONTRAST: Distance Vector Routing Protocol 1. The routing information of each node is ONLY known by its neighbors while the topology changes periodically. 2. Each node calculates the new shortest path to every possible destination with the tables of its neighbors. 4
Components of NDNs Forwarding Plane 1. Content Store (CS): It is used for caching data. 2. Pending Interest Table (PIT): It stores the unsatisfied Interest packets and the faces (interfaces) on which they were received. 3. Forwarding Information Base (FIB): It stores the forwarding entries that direct Interest packets toward potential source(s) of matching Data. 5
Forwarding Process at an NDN Node Forwarding Plane of an NDN node Interest Forward CS PIT FIB Data Add incoming interface Discard Create a PIT entry Last Hop Next Hop Pending Interest Table (PIT) Name Face /tw/ncnu/csie 1, 3 /tw/ncnu/csie/pearl 2 6 Courtesy of Chelsea
NLSR Naming Naming of an NLSR router: /<network>/<site>/<router> Example: /tw/NCNU/university/CSIE/router409 The NLSR process on a router: /tw/NCNU/university/CSIE/router409/NLSR 7
NLSR Naming (cont.) Wrong naming of Link State Advertisement (LSA): /tw/NCNU/university/CSIE/router409/NLSR/LSA Correct naming of LSA: /<network>/NLSR/LSA/<site>/<router> /<LSA prefix> Example: /tw/NCNU/NLSR/LSA/university/CSIE/router409 REASON: Content Centric Networking Synchronization Protocol (CCNx Sync) and CCNx Repository Protocol (CNNx Repo) is used to disseminate LSA data.8
Type Content Adjacency LSA # Active Links (N), Neighbor 1 Name, Link 1 Cost, ..., Neighbor N Name, Link N Cost LSAs Prefix LSA isValid (0,1), Name Prefix There are two types of LSAs: 1. Adjacency LSA: It is used to advertise all active link connecting one NDN router to its neighbors. 2. Prefix LSA: It is used to advertise a name prefix that has been registered with the router. Name format: 1. Adjacency LSA: /<LSA prefix>/<site>/<router>/LsType.1/<version> 2. Prefix LSA: /<LSA prefix>/<site>/<router>/LsType.2/LsId.<ID>/<version> The latest version of the LSAs are stored in a Link State Database (LSDB) at each router. 9
LSAs (cont.) Type Content Adjacency LSA 1, /tw/B/router, 10, /tw/C/router, 20 2, Prefix LSA 1, /tw/A/lab409 (Register) 0, /tw/A/lab409 (De-register) NDN Router B /tw/B/router 10 Adjacency Prefix LSA Prefix LSA Adjacency LSA LSA Register Link A-C is active. New Name Prefix /tw/A/lab409 20 or de-register NDN Router C /tw/C/router NDN Router A /tw/A/router /tw/A/lab409/router 10
CCNx Sync and Repo CCNx Sync and CCNx Repo are implemented to disseminate the LSAs to the neighboring routers. Root Network (Sync Area) R1.1 R2.1 NDN Router A NDN Router B Slice is defined as collections of named data. R1.2 R2.2 Repo B Repo A An Example of Hash Tree Slice 1 Slice 1 Slice 2 = LSA Slice 2 11
LSDB Synchronization (cont.) Router B Router A 1. Root Advise Interest (no reply) 2. Store LSA (2) 3. Root Advise Reply 4. Content Interest 5. Content Reply 2. Store LSA (1) 6. Sync Notification 7. Request for LSA LSDB A Adj. LSA 8. LSA Reply 12
Using Dijkstras Algorithm (O(V)) Multipath Calculation Step 1. Remove all immediately adjacent links except one Step 2. Calculate the cost of using that link to reach every destination Repeat step 1 & 2 for every adjacent link Rank the next-hops for each destination Destination (from A) Router B Router B Router B Router C (Next Hop, Cost) (Next Hop, Cost) (Next Hop, Cost) Destination (from A) (from A) Destination NDN Router A /tw/A NDN Router D /jp/D (1,10) (1,10) (2,17) (1,10) (2,17) (3,30) (1,20) (2,7) (3,20) 15 Face 3 Router C Router C (1,20) (1,20) (2,7) Face 1 Router D Router D Router D (1,25) (1,25) (2,12) (1,25) (2,12) (3,15) Face 2 10 7 5 Forwarding Information Base (FIB) Name prefix (Next Hop, Cost) /cn/B /kr/C (1,10) (2,17) (3,30) (2,7) (1,20) (3,20) 10 NDN Router B /cn/B NDN Router C /kr/C /jp/D (2,12) (3,15) (1,25) 14
NLSR continues sending Info Interests to detect the recovery of this adjacency at a relatively long interval Updating the Adjacency LSA Disseminating the LSA in the network Scheduling a routing table calculation. Failure and Recovery Detection Changing the adjacency status to Active 1. Link works 2. Link Failure 3. Recovery Router 213 is considered down. Time out! Info Info Info Info Info Info Data Data Info Interest Interest Interest Interest Interest Router 213 Router 409 1stTimer 2ndTimer 4thTimer 3rdTimer Time Line Info : /tw/NCNU/university/CSIE/router213/NLSR/info 15
Comparison IP-based Routing Protocol OSPFN IP address Name-based Routing Protocol NLSR Name Example Naming Information Dissemination Forwarding Synchronization Push Pull Single best path Flooding Multipath Hop-by-hop 16
Conclusion To meet NDN s routing needs, NLSR departs from the conventional routing protocol s single path forwarding and instead provides multiple forwarding options for each name prefix. However, in the design of NLSR, it is just a routing protocol that breaks the convention. For example, multipath calculation needs to go through all available faces produce the cost for each possible path. The time complexity is O(nV ). ( n is the number of faces on a router.) There is still a significant room for improvement of NLSR. 17
