idnits 2.17.1 draft-lanzhangwang-rtgwg-npmnrp-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** There is 1 instance of too long lines in the document, the longest one being 2 characters in excess of 72. == There are 11 instances of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 342 has weird spacing: '...mber is equal...' == Line 344 has weird spacing: '...mber of the D...' == Line 488 has weird spacing: '...ber and perio...' == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (April 04, 2018) is 2207 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 3 errors (**), 0 flaws (~~), 6 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group J.L. Lan 2 Internet-Draft J.H. Zhang 3 Intended status: Informational B.Wang 4 Expires: October 04, 2018 W.F. Liu 5 Y.J. Bu 6 T. Duan 7 National Digital Switching System Engineering and Technological 8 Research Center, P.R.China 9 X. Li 10 BEIJING UNIVERSITY OF POSTS AND TELECOMMUNICATIONS 11 April 04, 2018 13 Node Potential Oriented Multi-NextHop Routing Protocol 14 draft-lanzhangwang-rtgwg-npmnrp-05 16 Abstract 18 The Node Potential Oriented Multi-Nexthop Routing Protocol (NP-MNRP) 19 bases on the idea of "hop-by-hop routing forwarding, multi-backup 20 next hop" and combines with the phenomena that water flows from 21 higher place to lower. NP-MNRP defines a metric named as node 22 potential, which is based on hop count and the actual link bandwidth, 23 and calculates multiple next-hops through the potential difference 24 between the nodes. 26 Requirements Language 28 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 29 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 30 document are to be interpreted as described in RFC 2119 [RFC2119]. 32 Status of This Memo 34 This Internet-Draft is submitted in full conformance with the 35 provisions of BCP 78 and BCP 79. 37 Internet-Drafts are working documents of the Internet Engineering 38 Task Force (IETF). Note that other groups may also distribute 39 working documents as Internet-Drafts. The list of current Internet- 40 Drafts is at http://datatracker.ietf.org/drafts/current/. 42 Internet-Drafts are draft documents valid for a maximum of six months 43 and may be updated, replaced, or obsoleted by other documents at any 44 time. It is inappropriate to use Internet-Drafts as reference 45 material or to cite them other than as "work in progress." 47 This Internet-Draft will expire on October 04, 2018. 49 Copyright Notice 51 Copyright (c) 2015 IETF Trust and the persons identified as the 52 document authors. All rights reserved. 54 This document is subject to BCP 78 and the IETF Trust's Legal 55 Provisions Relating to IETF Documents 56 (http://trustee.ietf.org/license-info) in effect on the date of 57 publication of this document. Please review these documents 58 carefully, as they describe your rights and restrictions with respect 59 to this document. Code Components extracted from this document must 60 include Simplified BSD License text as described in Section 4.e of 61 the Trust Legal Provisions and are provided without warranty as 62 described in the Simplified BSD License. 64 Table of Contents 66 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2 67 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 3 68 3. Protocol operation . . . . . . . . . . . . . . . . . . . . . . 5 69 3.1. LFBs Network prefix information advertisement . . . . . . . 5 70 3.2. Neighbor Node Discovery and Adjacency establishment . . . . 7 71 3.3. Calculation of node potential value . . . . . . . . . . . . 8 72 3.4. network event sensing . . . . . . . . . . . . . . . . . . . 10 73 3.5. Update of the node potential . . . . . . . . . . . . . . . 12 74 4. Routing information base . . . . . . . . . . . . . . . . . . . 14 75 5. NP-MNRP packets format . . . . . . . . . . . . . . . . . . . . 15 76 5.1. Encapsulation of NP-MNRP packets . . . . . . . . . . . . . 15 77 5.2. Packet format . . . . . . . . . . . . . . . . . . . . . . . 15 78 6. Informative References . . . . . . . . . . . . . . . . . . . . 24 79 7. Author's Address . . . . . . . . . . . . . . . . . . . . . . . 24 81 1. Introduction 83 The inspiration of this routing protocol comes from the natural water 84 flow, which is a phenomenon of potential energy driven. Water flows 85 through all feasible channels from high potential site to low 86 potential site. If in every router all feasible next-hops for one 87 certain destination can be found, then all the packets to that 88 destination can be transferred in many paths. 90 This routing protocol obeys the Internet philosophy of "hop-by-hop 91 routing paradigm" and enhances it with "multiple feasible next-hops". 92 That means protocol try to calculate multiple next-hops for each node 93 and not find multi-path end to end. The forwarding direction of 94 packets is constrained by routing metrics. Different packets to one 95 destination can be distributed into multiple next-hops in parallel, 96 which can make full use of all feasible next hops, so that the link 97 utility ratio is globally even. 99 Compared with nature water flow phenomenon, the routing protocol 100 defines a routing metric named as node potential in communication 101 networks. Node potential is a parameter to measure the ability to 102 transfer packets from one certain node to its destination. So the 103 routing protocol is named as node potential oriented multiple next- 104 hops routing protocol (NP-MNRP in short). 106 NP-MNRP is designed to calculate multiple next-hops for one 107 destination in network without knowing the globally topology 108 information. Distance vector routing protocols such as RIP and BGP 109 are used for reference. NP-MNRP protocol is consisted of network 110 reachable information advertisement process and node potential 111 calculation process. But unlike those protocols, NP-MNRP ensures the 112 following properties. 114 (1) Multiple feasible next-hops for each destination. When node finds 115 the main next-hop unreachable, it chooses one from the backup 116 next-hops to forward the packet. 118 (2) Accelerate the convergence speed and reduce route flap. Compared 119 with the single shortest-path routing, NP-MNRP can effectively avoids 120 congestion and shorten protection switching delay. The path 121 establishment and maintenance can be accomplished by routing 122 information advertisement mechanism between peers. The control 123 overhead of the protocol is smaller than other multi-path routing 124 protocols. When kinds of concurrent failures occur in network, NP- 125 MNRP can provide more feasible next-hops and high recovery 126 probability. 128 2. Terminology 130 Carrier Network: The network in which the nodes run Node Potential 131 Oriented Routing Protocol. 133 User Network: The network that needs message transfer service 134 provided by Carrier Network. 136 Boundary Node: According to the location of nodes in the carrier 137 network, the nodes are divided into boundary nodes and intermediate 138 nodes. Boundary nodes are also divided into two categories according 139 to the flow direction. In terms of user network flow, the node 140 through which flow into the carrier network, is called ingress node; 141 the node through which flow out of the carrier network, is called 142 egress node. 144 Intermediate Node: The other nodes in the carrier network except the 145 Boundary Nodes. 147 Potential Reference Node: The egress nodes which the user network 148 traffic flows out from the carrier network. In the route calculation 149 process, these nodes will be set its node potential value to zero and 150 be act as reference node in node potential computation procedure. 151 Network Layer Diagram: The diagram that describes the distribution of 152 the layer value of every node relative to a destination node. 154 Node Potential: A metric that measures the accessibility from a node 155 to zero potential nodes in the carrier network. 157 Router ID: A 32-bit number assigned to each router running the NP- 158 MNRP protocol. This number uniquely identifies the router in the 159 carrier network. One algorithm for Router ID assignment is to choose 160 the largest or smallest IP address assigned to the router. 162 Set of Available Next-hops: The set of available next-hops of node i 163 when it sends packets to the destination node j, which is denoted as 164 A(i,j). 166 Network Layer Reachable Information Flood Advertisement Packet 167 (NLRI-FAP): The packet is used to advertise the information of 168 binding relations between network prefix and egress nodes to its 169 neighbors. IP address and subnet mask of its binding user network are 170 included in this packet. 172 Network Layer Reachable Information Specific Request Packet (NLRI- 173 SRP): The packet is used to request a particular egress node for 174 certain prefix binding relationship information. IP address and 175 subnet mask of user network whose binding relationship needs to know 176 are included in this packet. 178 Network Layer Reachable Information Direction Answer Packet (NLRI- 179 DAP): The packet is used to respond to a Network Layer Reachable 180 Information Specific Request Packet. IP address and subnet mask of 181 user network and its bound router ID are included in this packet. 183 Network Layer Graph Construction Trigger Packet (NLG-CTP): The packet 184 is used to trigger the building of network layer diagram. 186 Network Layer Graph Information Advertisement Packet (NLG-IAP): The 187 packet is used to advertise its layer information relative to one 188 egress node to its neighbors. The egress node ID and its layer value 189 relative to this egress node is included in this packet. 191 Network Layer Graph Routing Request Packet (NLG-RRP): The packet is 192 used to request the neighbors to update it's layer information 193 relative to one egress node and this egress node ID is included in 194 this packet. 196 Network Layer Graph Request Update Packet (NLG-RUP): The packet is 197 used to inform the nodes which are on a particular layer relative to 198 one destination node, to rebuild their layer information and that 199 layer value is included in this packet. 201 Link State Detect Packet (Detect): The packet is used to detect the 202 link status between itself and its neighbors. The sequence number of 203 this packet and the period for sending Detect are included in this 204 packet. 206 REPLY Packet (REPLY): The packet is used to respond to the Detect 207 indicating the good link state. The sequence number of this packet 208 and the period for sending Detect are included in this packet. 210 3. Protocol operation 212 3.1. LFBs Network prefix information advertisement 214 Because NP-MNRP protocol is designed as an IGP inside the autonomous 215 system, it should route transit network traffic and local network 216 traffic. The network IP prefix is divided into two parts: the IP 217 prefix information of transit network and the IP prefix information 218 of the network running NP-MNRP protocol own. 220 In view of NP-MNRP protocol, network is divided into user network and 221 carrier network, as shown in the figure 1. User network is 222 abbreviated as UN and carrier network is abbreviated as CN. Each node 223 in CN will run NP-MNRP protocol to establish multiple next-hops 224 routing information base. Otherwise, it is not necessary for nodes in 225 UN to run NP-MNRP protocol. 227 CNRT: Carrier Network Router 228 ---- ---- ---- 229 / \ / \ / \ 230 * UN1 * * UN2 * * UN3 * 231 \----/ \----/ \----/ 232 | | | 233 ******|*******************|*******************|****** 234 * +-----+ +-----+ +-----+ * 235 * |CNRT1|-------------|CNRT2|-------------|CNRT3| * 236 * +-----+ +-----+ +-----+ * 237 * | | | * 238 * | | | * 239 * +-----+ +-----+ +-----+ * 240 * |CNRT5|-------------|CNRT6|-------------|CNRT4| * 241 * +-----+ CN +-----+ +-----+ * 242 ******|***************************************|****** 243 __|_ __|_ 244 /----\ /----\ 245 * UN5 * * UN4 * 246 \----/ \----/ 247 Figure 1: Network Model 249 The nodes in UN will finish local communication and transmit the 250 network traffic whose destinations are not in the user network itself 251 to the Carrier network. The network prefix of UN is named as Network 252 Layer reachable information. Carrier network mainly transfer transit 253 traffic for UN. The network prefix of CN is treated as network 254 topology information and will be advertised by potential calculation 255 process. The boundary nodes of CN are also named as egress nodes. 256 They advertise network layer reachable information to neighbor nodes 257 periodically and initiate node potential calculation procedure for 258 itself. 260 This advertisement method separates the information of CN topology 261 from the network layer reachable information and advertises them in 262 different manner. The advertisement of topology information is 263 independent with network layer reachable information. From this way, 264 the flexibility of routing information distribution can be enhanced. 266 3.1.2 Network layer reachable information advertisement 268 Network layer reachable information that means the user network 269 prefix is advertised through NLRI-FAP, NLRI-SRP and NLRI-DAP packets. 270 The boundary nodes in CN are responsible for advertising user network 271 reachable information, as shown in the figure 2. 273 ................ 274 . UN . 275 . Host1 Host2 . 276 . \ / . 277 . \ / . 278 . +-----+ . 279 . |UNRT1| . 280 . +-----+ . Host1 Host2 .Host1 Host2 281 .......|........ \ / \ / 282 ****************|*****************\ /***************** \ / 283 * +------+ +------+ * +-----+ 284 * +-----|CNBRT1|------------|CNBRT2|----------------|UNRT2| 285 * | +------+ +------+ * +-----+ 286 * | | | | 287 * | | | * | 288 * | +-----+ +-----+ +-----+* | 289 * | |CNRT6|-------------|CNRT3|-------|CNRT2|* | 290 * | +-----+ +-----+ +-----+* | 291 * | | | | * | 292 * | | | | * | 293 * +------+ +-----+ +-----+ +------+* | 294 * |CNBRT4|---|CNRT5|-------------|CNRT4|------|CNBRT3|-------+ 295 * +------+ +-----+ CN +-----+ +------+* 296 ******|******************************************/ \*** 297 ......|......... / \ 298 +-----+ . Host1 Host2 299 |UNRT3| . 300 +-----+ . 301 / \ . 302 / \ . 303 Host1 Host2 . 304 ................ 305 Figure 2: Network layer reachable information advertisements 307 CNRT: Carrier Network Router. 309 CNBRT: Carrier Network Boundary Router. 311 The boundary nodes in CN advertise network layer reachable 312 information to neighbor nodes periodically through NLRI-FAP. Once 313 receiving the NLRI-FAP, the nodes in CN extract network prefix 314 information from packets and add them to the network layer reachable 315 information database of their own. 317 When the nodes in CN don't know user network prefix, these nodes will 318 act as inquirers and send NLRI-SRP to query other nodes and set a 319 query timer. When a node receives the NLRI-SRP, and the network 320 prefix information or attached router information is in its database, 321 it responses to inquirer with a NLRI-DAP packet. Otherwise, it sends 322 the NLRI-SRP packet to its neighbors except for the enquirers. This 323 process will continue until the inquirer get an response from other 324 nodes or such query timer is timed out. 326 When bound to the egress node (relative information is absent in 327 network layer reachable information database of the node), the node 328 send NLRI-SRP flooding to inquirer, called enquirers. 330 3.2. Neighbor Node Discovery and Adjacency establishment 332 When a new node joins in the network, other nodes discover it and 333 initialize their local routing tables as the following steps. 335 (1) Broadcast a Detect packet and a NLG-CTP packet. This node sets 336 the sequence number of Detect with 0.The Detect will be sent 337 periodically by defaulted period set in the protocol; 339 (2) When other nodes receive a Detect packet or a NLG-CTP packet, 340 they operate as follows. 341 (a) If the received Detect message is ca from an unknown node and 342 sequence number is equal to 0, the receivers know that a new 343 node add to network and add it to their neighbor node database 344 and record sequence number of the Detect message; 345 (b) Reply to the unknown node with an REPLY packet; Send a NLG- 346 IAP packet which contains all egress nodes information in the 347 database; 348 (c) According to the computation rules of node potential, they 349 compute layer value and potential value relative to the egress 350 node. 351 (3) When received a REPLY packet and a NLG-IAP packet, the new node 352 operates as follows. 353 (a) Adds the neighbor node to routing information database; 354 (b) According to NLG-IAP, it calculates its own layer value as 355 following formula. 356 L(i,i)=0, 357 L(i,j)=min[L(k,j)]+1, 358 for each k blongs to Ki, j blongs to N, and k,j are not equal 359 to i. 360 L(i,j) is the layer value of node i reference to egress node 361 j, N is the set of network nodes, Ki is the set of neighbor nodes 362 about node i. 363 (c) Based on the layer values of its neighbors, bandwidth and its 364 own layer value, the new node computes node potential value of 365 its neighbors and its own. 367 3.3. Calculation of node potential value 368 3.3.1 Definition of node potential value 370 NP-MNRP defines node potential value as a mixed metric of hop count 371 and bandwidth. Hop count metric records the number of routers which a 372 packet passes through and each router is recorded as one hop. The 373 actual link bandwidth is allocated\configured by router in the 374 network initialization. 376 3.3.2 Protocol packets sending and processing 378 3.3.2.1 Network Layer Graph Routing Request Packet processing 380 Network Layer Graph Routing Request Packet (NLG-RRP) has two 381 different types. One type is all nodes layer information request 382 packet which will request the receiver to send layer information of 383 all nodes. The other is partial nodes layer information request 384 packet which will request the receiver to send layer information of 385 the specified nodes. 387 The NLG-RRP will be used in the following conditions. 389 Condition 1: When a new node is attached to the network, all nodes 390 layer information request packet will be sent to its neighbors. 392 Condition 2: When the node want to get some certain network prefix 393 information from its neighbors, partial nodes layer information 394 request packet will be sent. 396 Once receiving a NLG-RRP packet, each node should process as the 397 following steps. 399 (a) Firstly, the type of the packet will be verified whether or not 400 it is a correct NLG-RRP packet. 402 (b) When NLG-RRP is the all nodes layer information request packets, 403 it sends its own layer information relative to the other nodes to the 404 request node. 406 (c) When NLG-RRP is the partial nodes layer information request 407 packet, it sends its own layer information relative to the 408 destination node in the packet to the query node. 410 3.3.2.2 Network Layer Graph Information Advertisement Packet sending 412 Network Layer Graph Information Advertisement Packet (NLG-IAP) is 413 broadcast to its neighbors in the following cases. 415 Case 1: Each layer value of every node is specified after the network 416 layer graph has been divided. 418 Case 2: When the layer information of any node is changed, which may 419 be caused by the change of layer values of some routers when they 420 received NLG-FAP or some new nodes are added to the network. 422 Case 3: A NLG-RRP packet is received and the layer value of receiver 423 reference to certain egress node is changed. 425 The processing rules of NLG-IAP are described in section 3.5. 427 3.3.3 Calculation of the node potential value 429 In NP-MNRP, the node potential value is a mixed metric, including hop 430 count and actual link bandwidth. Each egress node activates its 431 neighbors to build Network Layer graph by sending a NLG-CTP packet to 432 neighbors. Calculated as follows. 434 (1) In the algorithm initialization, egress node assigns its layer 435 value as 0, and then sends a NLG-CTP packet to its neighbors, which 436 contains the actual link bandwidth. 438 (2) The neighbor node that received a NLG-CTP packet from the 0- 439 layer node sets itself as 1-layer, and generates a NLG-CTP packet and 440 sends to its neighbors. And so on. 442 (3) Repeat the above step (2) until the nodes whose layer value are 443 smaller than f-layer which have been determined. 445 (4) After the f-layer has been constructed completely, each node in 446 f-layer knows that it is in f-layer and knows that which neighbors 447 are in f-1 layer. The nodes in f-1layer know that which ones are in f 448 layer, which ones are in f-1 layer, and which ones are in f-2 layer. 450 (5) Supposed f-layer has been constructed, and the algorithm has not 451 been terminated, then the construction of the f +1 layer will begins. 452 The nodes in f-layer will send a NLG-CTP packet to its neighbors. 454 (6) When all the nodes are traveled, algorithm ends. 456 All nodes in the network not only are aware of their own layer value 457 but also know the layer values of their neighbors and the actual 458 bandwidth between themselves. 460 Next, each node calculates the potential value as follows. 462 (1) 0-layer nodes directly define their own potential value as 0; 464 (2) Each node of the other layers chooses the largest potential value 465 node among its neighbors in the same and lower layers as its 466 reference node for defining potential value, then defines its 467 potential value as potential value of the reference node plus one and 468 potential values of its neighbors which are equal to their layer 469 value; 471 (3) When each potential value of the neighbors is defined, the node 472 will choose the neighbor nodes whose potential values are less than 473 its own as feasible next-hops of itself. 475 3.4. network event sensing 477 NP-MNRP protocol can sense events such as new node add to network or 478 neighbor node is down. The node senses these events through sending 479 out Detect packet and receiving REPLY packet periodically. 481 3.4.1 Message sending and processing 483 Each NP-MNRP node broadcasts periodically Detect packet. When a 484 Detect packet is received, the receiver sends a REPLY packet to the 485 sender. The detailed steps are as follows. 487 Step1: Each node broadcasts periodically a Detect packet. Detect 488 packet carries a sequence number and periodic interval. 490 Step2: When a Detect packet is received, its sequence number is 491 compared with the expected sequence number for this neighbor. Then 492 the receiver sends a REPLY packet to the sender and evaluates inverse 493 link quality according to the sequence number. 495 Step3: When a Reply packet is received, its sequence number should be 496 equaled to the sequence number of the Detect packet. Then the 497 receiver evaluates link quality according to the sequence number and 498 the use of sent/receive message time. 500 3.4.2 Forward direction link sensing 502 A(Ti) represents the mean interval from node i sending out Detect 503 packet to receiving REPLY packet. FA (Ti) represents the latest mean 504 interval time. Node i adjust the period of sending out Detect packet 505 according to the following rules. 507 (1) If FA(Ti) < A(Ti), it means that the link quality is stable. At 508 this period, when three continuous Detect packets are all low, then 509 increase the Detect interval; 511 (2) If FA(Ti) > A(Ti), it means that the link quality is unsteady or 512 become bad. At this period, when three continuous Detect packets are 513 all high, then reduce Detect interval; 515 (3) When a Detect packet is sent out but a REPLY packet is not 516 received in the 2*FA(Ti) time, the node will reduce the period at 517 half, then continue sending out the next sequence number Detect 518 packet. If a REPLY packet still not received, the node insulates that 519 node and thinks link breakdown or link congestion. 521 (4) The isolate node will not be used as the next-hop to forwarding 522 packets. The processing node should continue sending Detect packet 523 and adjust strategy according to the following conditions. 524 (a) If three continuous REPLY packets received, then the node 525 deletes the isolate node and uses nodes which reply the REPLY 526 packet as the next-hops to forwarding packets. 528 (b) If no packet is received after 6 Detect intervals, so that 529 node is thought to be breakdown, unable to send Detect packet 530 again. Waiting 532 (c) If the node can receive a Detect packet or a REPLY packet 533 which is send out from isolate node, and then it will continue 534 sending a Detect packet until the isolate node recovery or judge 535 node breakdown. 536 3.4.3 Inverse link sensing 538 Each node broadcasts periodically Detect packet. Every Detect carries 539 a sequence number and the interval. 541 When a Detect packet is received, compared sequence number with the 542 next expected sequence number for this neighbor, if the sequence 543 number of the received Detect packet is higher than the expected, 544 then one or more Detect packets have been missed. If the sequence 545 number is lower, then this neighbor decrease the Detect interval, and 546 part of the history must be undone. 548 From the history of received Detect packets, a node computes an 549 estimate of the inverse link quality. 551 3.5. Update of the node potential 553 3.5.1. Update of network layer value 555 As the set of next-hop is empty, the node will trigger update about 556 the layer value through the following operations. 558 (1) Firstly, the node will check whether the set of its neighbors on 559 the same layer is empty. If is not, it will change itself layer value 560 and generate NLG-IAP packets that are sent to its neighbors. 562 (2) If the set is empty, then the node will perform the following 563 steps. 565 (a) Flooding NLG-RUP packets, whose layer value will be revised 566 to the old layer value minus 2, however, if old layer value minus 567 2 is less than 0, the value is set to 0. What's more, all 568 information about this egress node will be deleted. 570 (b) The node received a NLG-RUP packet will check if it has ever 571 received this message. If having received such message, the 572 packet will be ignored, otherwise view the layer value in this 573 packet. If the value is greater than the value of its own, the 574 node will discard the packet, otherwise, go on flooding NLG-RUP 575 packets to its neighbors and delete all information about this 576 egress node. 578 (c) If the layer value in the packet is equal to its own, the 579 node will stop flooding to send NLG-RUP and send a NLG-CTP packet 580 about the egress node. 582 (d) Neighbor node received a NLG-CTP packet will calculate its 583 new layer value. If new value is same with the original, the node 584 stops sending NLG-CTP packets and the layer value update 585 algorithm will terminate. 587 3.5.2. Update of node potential value The potential value of the 588 nodes will be updated in the following conditions. 590 (1) Potential value update caused by NLG-IAP packet. The main content 591 of a NLG-IAP packet are layer information of a node relative to the 592 egress node in the network. The node adjusts its potential value 593 according to the NLG-IAP packets received from its neighbors. 594 Specific updated as follows. 596 (a) NLG-IAP packet generation When the node finds its layer 597 information relative to one certain egress node changed, the new 598 layer information relative to all egress nodes will be written 599 into its generated NLG-IAP packet. 601 (b) NLG-IAP to send The node will broadcast its generated NLG-IAP 602 packets to its neighbors, and then wait for confirmation from its 603 neighbors. When the node receives REPLY pockets with sequence 604 number 0XFFFF from its neighbors, this update ends. 606 (c) When the node received the NLG-IAP packet, it performs the 607 following steps. 609 Firstly, this node will verify NLG-IAP packet. If the packet is 610 validated, it sends a REPLY packet with sequence number 0XFFFF to 611 source node of NLG-IAP packet. 613 Secondly, this node will extract layer information from the NLG- 614 IAP packet supposing a received routing entries includes RUIi =< 615 RouterID, EgressnodeID, Layi> and the corresponding routing entry 616 stored in the database is RUI'i =< RouterID, EgressnodeID, 617 Lay'i>, when one of the following three cases are met, the node 618 update its own routing table according to the information 619 received. 621 Case 1: If the EgressnodeID included in the received routing 622 table entry dose not exist in its own routing table, the router 623 will add it and send a NLG-RRP packet about the destination 624 address of the network to its neighbors. After received NLG-IAP 625 packets, it will calculate its layer value relative to this 626 egress node according to formula in 3.2, and get layer values of 627 it's neighbors, then define the potential value of neighbor node 628 reference to this destination node. 630 Case 2: If the EgressnodeID included in the received routing 631 table entry exists in its own routing table and Lay'i < Layi, the 632 router will adjust the layer values of its neighbors and 633 potential value. If the potential value of neighbor is greater 634 than its own and the neighbor node is just in its own next-hop 635 collection, the router will remove the node from next-hop 636 collection, if not, do nothing. 638 Case 3: If Layi < Lay, then the router will adjust the layer 639 value of neighbor node and potential value. If the potential 640 value of neighbor is less than its own and the neighbor node is 641 not in its own next-hop collection, then the router will add it 642 into the next-hop 644 (2) Potential value update caused by the change of layer value 646 When the layer value reference to a particular destination node 647 changes, firstly it will modify layer value of itself and its 648 neighbors. Then the new potential value will be calculated according 649 to update strategy. 651 4. Routing information base 653 Each routing node maintains the Routing Information Base to forward 654 IP packets. NP-MNRP protocol can calculate multiple next-hops routing 655 information in the network. The route computation process descried in 656 Section 3 will record all the feasible next-hops for every 657 destination. The multiple next-hops routing entry is composed of 658 three fields. 660 The first field is named as destination IP address field. 662 The second field is named as the destination IP address mask filed. 663 The first and second fields are 32-bit numbers which define network 664 destination information of each routing entry. And the route 665 information base is indexed by the first and second field. 667 The third field is named as feasible next-hop filed, whose form is a 668 couple of next-hop IP address value and node potential difference 669 value. The next-hop IP address is IP address of the neighbor node who 670 will act as a feasible next-hop for this routing node to forward IP 671 packets to the network destination. Compared with the single next-hop 672 routing information, the number of feasible next-hop filed in a 673 multiple next-hops routing entry may be a value bigger than one. 675 The routing node will gain more agility in IP packet forwarding 676 procedure. It can choose forward all the packets to one best next-hop 677 and use other feasible next-hop entries as backup entries. Through 678 this way, the network availability will be improved in the scene that 679 network failure or mal-function occurs frequently. It can also choose 680 forward all the IP packets to all feasible next-hop entries. In this 681 manner, this routing node can assign each next-hop a traffic ratio 682 for each destination. All the packets will be forwarded to variable 683 next-hop pro rata. This will make the network resource utilization 684 more evenness and avoid network congestion in some ways. 686 5. NP-MNRP packets format 688 The NP-MNRP protocol runs directly over the IP network layer. Before 689 any packet format is described, the details of the NP-MNRP 690 encapsulation are explained. 691 5.1. Encapsulation of NP-MNRP packets 693 NP-MNRP runs directly over the Internet Protocol's network layer. 694 Therefore, NP-MNRP packets are encapsulated solely by IP and local 695 data-link headers. NP-MNRP does not define a way to fragment its 696 protocol packets, and depends on IP fragmentation when transmitting 697 packets larger than the network MTU. 699 NP-MNRP uses IP protocol number 99. Routing protocol packets are sent 700 with IP precedence set to inter-network Control. NP-MNRP protocol 701 packets should be given precedence over regular IP data traffic, in 702 both sending and receiving. 704 5.2. Packet format 706 There are nine distinct NP-MNRP packet types. All NP-MNRP packet 707 types begin with a standard 20 byte header. This header is described 708 first. Each packet type is then described in a succeeding section. In 709 these sections each packet's division into fields is displayed, and 710 then the field definitions are enumerated. 712 5.2.1 The NP-MNRP packet header 714 Every NP-MNRP packet starts with a standard 20 byte header. This 715 header contains all the information necessary to determine whether 716 the packet should be accepted for further processing. This 717 determination is described in Section 5.2 of the specification. 719 0 1 2 3 720 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 721 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 722 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | 723 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 724 | Version # | Type | Packet length | 725 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 726 | Router ID | 727 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 728 | Check Sum | Authentication Type | 729 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 730 | Authentication Info(8 array 0-3) | 731 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 732 | Authentication Info(8 array 4-7) | 733 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 735 Version 736 The NP-MNRP version number. This specification documents version 1 737 of the protocol. 739 Type 740 Type Description 741 --------------------- 742 1 NLRI-FAP 743 2 NLRI-SRP 744 3 NLRI-DAP 745 4 NLG-CTP 746 5 NLG-IAP 747 6 NLG-RRP 748 7 NLG-RUP 749 8 Detect 750 9 REPLY 752 Router ID 753 The Router ID of the packet's source. 755 Check Sum 756 The standard IP checksum of the entire content of the packet. Note 757 that the packet starts with the NP-MNRP header but excluding the 64- 758 bit authentication field. If the length of the package is less than 759 16-bit, 0 byte WOULD be added before the checksum byte. 761 Authentication Type Identify the authentication procedure used for 762 the packet. Authentication is discussed in the specification. 764 Authentication Info 64-bit authentication information field depends 765 on the chosen authentication type, to carry identification 766 information such as identity authentication. 768 5.2.2 Various types of protocol packets 770 NP-MNRP protocol packets have total of 9 species. 772 5.2.2.1 Network Layer Reachable Information Flood Advertisement 773 Packet, NLRI-FAP 775 NLRI-FAP packet is NP-MNRP packet type 1.The packet is send by an 776 egress node in the carrier network and is used to advertise the user 777 network prefix information which is bound to this node. The node that 778 received this packet WOULD consider this egress node is reachable and 779 the user network which is bound to this node is reachable too. 781 0 1 2 3 782 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 783 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 784 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | 785 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 786 | Version # | 1 | Packet length | 787 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 788 | Router ID | 789 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 790 | Check Sum | Authentication Type | 791 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 792 | Authentication Info(8 array 0-3) | 793 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 794 | Authentication Info(8 array 4-7) | 795 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 796 | IP address of the network 1 | 797 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 798 | Subnet mask of the network 1 | 799 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 800 | ...... | 801 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 802 | IP address of the network n | 803 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 804 | Subnet mask of the network n | 805 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 807 IP address of the network 808 The IP address of a user network is bound to this egress node. 810 Subnet mask of the network 811 Subnet mask of user network is denoted in the above field. 813 5.2.2.2 Network Layer Reachable Information Specific Request Packet, 814 NLRI-SRP 816 NLRI-SRP packet is NP-MNRP packet type 2.This packet is used by the 817 node in the carrier network to request the network layer reachable 818 information. When the node doses not know which egress node, one 819 network prefix is bound to, the NLRI-SRP packet is sent. 821 If the IP address and the subnet mask of the network 1 is all 0, all 822 the network prefixes WOULD be requested, and usually this request is 823 sent by a node which just joins into the carrier network. 825 0 1 2 3 826 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 827 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 828 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | 829 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 830 | Version # | 2 | Packet length | 831 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 832 | Router ID | 833 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 834 | Check Sum | Authentication Type | 835 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 836 | Authentication Info(8 array 0-3) | 837 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 838 | Authentication Info(8 array 4-7) | 839 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 840 | IP address of the network 1 | 841 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 842 | Subnet mask of the network 1 | 843 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 844 | ...... | 845 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 846 | IP address of the network n | 847 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 848 | Subnet mask of the network n | 849 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 851 IP address of the network 852 The IP address of a user network whose binding relationship this 853 node want to request. 855 Subnet mask of the network 856 The Subnet mask of a user network denoted in the above field, who 857 binding relationship this node wants to request 859 5.2.2.3 Network Layer Reachable Information Direction Answer Packet, 860 NLRI-DAP 862 NLRI-DAP packet is NP-MNRP packet type 3. The node that receives the 863 NLRI-SRP packet WOULD check its information database to seek for the 864 corresponding binding relationship. If the binding relationship 865 exists in its own information database, it WOULD send NLRI-DAP packet 866 to the requesting node, if not, it WOULD send NLRI-SRP packets to its 867 all neighbor nodes except for the requesting node. 869 If a node who sends the NLRI-SRP packets at the same time receives 870 more than one packet about the same IP prefix binding relationship, 871 and these packets are conflictive, it WOULD go on sending NLRI-SRP 872 0 1 2 3 873 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 874 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 875 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | 876 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 877 | Version # | 3 | Packet length | 878 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 879 | Router ID | 880 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 881 | Check Sum | Authentication Type | 882 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 883 | Authentication Info(8 array 0-3) | 884 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 885 | Authentication Info(8 array 4-7) | 886 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 887 | IP address of the network | 888 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 889 | Subnet mask of the network 1 | 890 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 891 | Egress node ID 1 | 892 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 893 | ...... | 894 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 895 | IP address of the network n | 896 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 897 | Subnet mask of the network n | 898 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 899 | Egress node ID n | 900 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 902 IP address of the network 903 The IP address of a user network whose binding relationship is wants 904 to know in the receiving NLRI-SRP packet. 906 Subnet mask of the network 907 The subnet mask of a user network denoted in the above field, whose 908 binding relationship is wants to know in the receiving NLRI-SRP 909 packet. 911 Egress node ID 912 This field denotes the user network, whose IP address and subnet 913 mask emerge in the front two fields, is bound to this egress node. 915 5.2.2.4 Network Layer Graph Construction Trigger Packet, NLG-CTP 916 NLG-CTP packet is NP-MNRP packet type 4.When one egress node joins 917 into the carrier network, it WOULD send this packet to urge the other 918 nodes to build network layer graph relative to itself. 920 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 921 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 922 Byte 1 | Byte 2 | Byte 3 | Byte 4 | 923 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 924 Version # | 4 | Packet length | 925 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 926 | Router ID | 927 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 928 Check Sum | Authentication Type | 929 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 930 Authentication Info(8 array 0-3) | 931 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 932 Authentication Info(8 array 4-7) | 933 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 934 Egress node ID | 935 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 936 Layer value | 937 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 939 Egress node ID The node that received this packet calculates its 940 layer value relative to this egress node. 942 Layer value The value of the sender relative to the node denoted in 943 the above field 945 5.2.2.5 Network Layer Graph Information Advertisement Packet, NLG-IAP 947 NLG-IAP packet is NP-MNRP packet type 5. This packet is sent to all 948 neighbor nodes using multicast address to advertise its layer value 949 relative to the node whose ID includes in this packet, this packet is 950 usually to start the neighbor nodes to adjust their potential 951 dynamically. 953 0 1 2 3 954 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 955 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 956 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | 957 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 958 | Version | 5 | packet length | 959 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 960 | Router ID | 961 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 962 | Egress node ID | 963 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 964 | Check Sum | Authentication Type | 965 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 966 | Authentication Info(8 array 0-3) | 967 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 968 | Authentication Info(8 array 4-7) | 969 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 970 | Egress node ID 1 | 971 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 972 | Layer value 1 | 973 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 974 | ....... | 975 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 976 | Egress node ID n | 977 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 978 | Layer value n | 979 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 981 Egress node ID 982 The receiver need adjust its layer value relative to this node 984 Layer value 985 This is the layer value of the sender relative to the egress node 986 denoted in the above field. 988 5.2.2.6 Network Layer Graph Routing Request Packet, NLG-RRP 990 NLG-RRP packet is NP-MNRP packet type 6. This packet is used by one 991 node to request the neighbor nodes to send their own layer 992 information relative to the appointed egress node to it. This packet 993 has two types: one is for all nodes and the other is for some nodes. 994 If the egress node ID in the packet is empty, the packet is NLG-RRP 995 packet for all nodes, if not; the packet is NLG-RRP packet for the 996 appointed nodes included in this packet. 998 0 1 2 3 999 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1000 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1001 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | 1002 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1003 | Version | 6 | packet length | 1004 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1005 | Router ID | 1006 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1007 | Check Sum | Authentication Type | 1008 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1009 | Authentication Info(8 array 0-3) | 1010 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1011 | Authentication Info(8 array 4-7) | 1012 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1013 | Egress node ID1 | 1014 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1015 | Egress node ID2 | 1016 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1017 | ....... | 1018 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1020 Egress node ID 1021 This field denotes the receiver need to respond its layer value 1022 relative to this egress node. 1024 5.2.2.7 Network Layer Graph Request Update Packet, NLG-RUP 1026 NLG-RUP packet is NP-MNRP packet type 7. When a node finds its next 1027 hops and its neighbors on the same layer are all unreachable, it 1028 sends this packet to neighbors to update its layer value. 1029 0 1 2 3 1030 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1031 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1032 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | 1033 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1034 | Version | 7 | packet length | 1035 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1036 | Router ID | 1037 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1038 | Check Sum | Authentication Type | 1039 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1040 | Authentication Info(8 array 0-3) | 1041 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1042 | Authentication Info(8 array 4-7) | 1043 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1044 | Egress node ID | 1046 Egress node ID 1047 This field denotes the receiver needs to update its value relative 1048 to this node 1050 Layer value 1051 The layer value in NLG-RUP packet is the layer value relative to 1052 high egress node minus 2. 1054 5.2.2.8 Link State Detect Packet, Detect 1056 Detect packet is NP-MNRP packet type 8. This packet is periodically 1057 sent to neighbor nodes to evaluate the link quality. 1059 0 1 2 3 1060 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1061 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1062 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | 1063 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1064 | Version | 8 | packet length | 1065 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1066 | Router ID | 1067 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1068 | Check Sum | Authentication Type | 1069 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1070 | Authentication Info(8 array 0-3) | 1071 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1072 | Authentication Info(8 array 4-7) | 1073 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1074 | Sequence number | Period | 1075 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1077 Sequence number 1078 The sequence number in this packet is the sequence number of the 1079 Detect message, and it is an increasing positive integer. 1081 Period 1082 The period in this packet is the interval time between this to the 1083 last one. 1085 5.2.2.9 REPLY Message Packet, REPLY 1087 REPLY packet is NP-MNRP packet type 9. The node that received a 1088 detect packet will send a reply packet to the sender, which can 1089 evaluate the reverse link quality according to this packet. The 1090 sequence number in this packet denotes it is the reply to the Detect 1091 message that has the corresponding sequence number. If the number is 1092 full-1, it means the packet is confirmation message to a NLG-IAP 1093 message. 1095 0 1 2 3 1096 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1097 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1098 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | 1099 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1100 | Version | 9 | packet length | 1101 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1102 | Router ID | 1103 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1104 | Check Sum | Authentication Type | 1105 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1106 | Authentication Info(8 array 0-3) | 1107 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1108 | Authentication Info(8 array 4-7) | 1109 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1110 | Serial number | Period | 1111 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1113 Serial number 1114 The sequence number in this packet is the sequence number of the 1115 REPLY, and it is an increasing positive integer. 1117 Period 1118 This field denotes that the node sending this packet will sends 1119 Detect message at this period. 1120 6. Informative References 1122 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1123 Requirement Levels", RFC 2119, March 1997. 1125 7. Author's Address 1127 Julong Lan 1128 National Digital Switching System Engineering and Technological 1129 Research Center 1130 NDSC, No.7 , Jianxue Street,Jinshui District 1131 Zhengzhou, 450002, 1132 P.R.China 1133 Phone: +86-371-8163-2988 1134 Email: ndscljl@163.com 1135 URI: http://www.ndsc.com.cn/ 1137 Jianhui Zhang 1138 National Digital Switching System Engineering and Technological 1139 Research Center 1140 NDSC, No.7 , Jianxue Street,Jinshui District 1141 Zhengzhou, 450002, 1142 P.R.China 1143 Phone: +86-371-8163-2988 1144 Email: ndsc155@163.com 1145 URI: http://www.ndsc.com.cn/ 1147 Bin Wang 1148 National Digital Switching System Engineering and Technological 1149 Research Center 1150 NDSC, No.7 , Jianxue Street,Jinshui District 1151 Zhengzhou, 450002, 1152 P.R.China 1153 Phone: +86-371-8163-2909 1154 Email: ndscmt@163.com 1155 URI: http://www.ndsc.com.cn/ 1157 Wenfen Liu 1158 National Digital Switching System Engineering and Technological 1159 Research Center 1160 NDSC, No.7 , Jianxue Street,Jinshui District 1161 Zhengzhou, 450002, 1162 P.R.China 1163 Phone: +86-371-8163-0340 1164 Email: wenfenliu@sina.com 1165 URI: http://www.ndsc.com.cn/ 1167 Youjun Bu 1168 National Digital Switching System Engineering and Technological 1169 Research Center 1170 NDSC, No.7 , Jianxue Street,Jinshui District 1171 Zhengzhou, 450002, 1172 P.R.China 1173 Phone: +86-371-8163-2670 1174 Email: buyoujun2009@hotmail.com 1175 URI: http://www.ndsc.com.cn/ 1177 Tong Duan 1178 National Digital Switching System Engineering and Technological 1179 Research Center 1180 NDSC, No.7 , Jianxue Street,Jinshui District 1181 Zhengzhou, 450002, 1182 P.R.China 1183 Phone: +86-371-8163-2670 1184 Email: duantong21@126.com 1185 URI: http://www.ndsc.com.cn/ 1187 Xin Li 1188 BEIJING UNIVERSITY OF POSTS AND TELECOMMUNICATIONS 1189 No.10 Xi Tu Cheng Road Haidian District 1190 Beijing,100876 1191 P.R.China 1192 Phone: +8613581614576 1193 Email: cplalx@gmail.com 1194 URI: http://www.bupt.edu.cn/