idnits 2.17.1 draft-lanzhangwang-rtgwg-npmnrp-06.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 3 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 341 has weird spacing: '...mber is equal...' == Line 343 has weird spacing: '...mber of the D...' == Line 487 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 (September 27, 2018) is 2009 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: March 27, 2019 W.F. Liu 5 T. Duan 6 National Digital Switching System Engineering and Technological 7 Research Center, P.R.China 8 X. Li 9 BEIJING UNIVERSITY OF POSTS AND TELECOMMUNICATIONS 10 September 27, 2018 12 Node Potential Oriented Multi-NextHop Routing Protocol 13 draft-lanzhangwang-rtgwg-npmnrp-06 15 Abstract 17 The Node Potential Oriented Multi-Nexthop Routing Protocol (NP-MNRP) 18 bases on the idea of "hop-by-hop routing forwarding, multi-backup 19 next hop" and combines with the phenomena that water flows from 20 higher place to lower. NP-MNRP defines a metric named as node 21 potential, which is based on hop count and the actual link bandwidth, 22 and calculates multiple next-hops through the potential difference 23 between the nodes. 25 Requirements Language 27 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 28 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 29 document are to be interpreted as described in RFC 2119 [RFC2119]. 31 Status of This Memo 33 This Internet-Draft is submitted in full conformance with the 34 provisions of BCP 78 and BCP 79. 36 Internet-Drafts are working documents of the Internet Engineering 37 Task Force (IETF). Note that other groups may also distribute 38 working documents as Internet-Drafts. The list of current Internet- 39 Drafts is at http://datatracker.ietf.org/drafts/current/. 41 Internet-Drafts are draft documents valid for a maximum of six months 42 and may be updated, replaced, or obsoleted by other documents at any 43 time. It is inappropriate to use Internet-Drafts as reference 44 material or to cite them other than as "work in progress." 46 This Internet-Draft will expire on March 27, 2019. 48 Copyright Notice 50 Copyright (c) 2015 IETF Trust and the persons identified as the 51 document authors. All rights reserved. 53 This document is subject to BCP 78 and the IETF Trust's Legal 54 Provisions Relating to IETF Documents 55 (http://trustee.ietf.org/license-info) in effect on the date of 56 publication of this document. Please review these documents 57 carefully, as they describe your rights and restrictions with respect 58 to this document. Code Components extracted from this document must 59 include Simplified BSD License text as described in Section 4.e of 60 the Trust Legal Provisions and are provided without warranty as 61 described in the Simplified BSD License. 63 Table of Contents 65 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2 66 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 3 67 3. Protocol operation . . . . . . . . . . . . . . . . . . . . . . 5 68 3.1. LFBs Network prefix information advertisement . . . . . . . 5 69 3.2. Neighbor Node Discovery and Adjacency establishment . . . . 7 70 3.3. Calculation of node potential value . . . . . . . . . . . . 8 71 3.4. network event sensing . . . . . . . . . . . . . . . . . . . 10 72 3.5. Update of the node potential . . . . . . . . . . . . . . . 12 73 4. Routing information base . . . . . . . . . . . . . . . . . . . 14 74 5. NP-MNRP packets format . . . . . . . . . . . . . . . . . . . . 15 75 5.1. Encapsulation of NP-MNRP packets . . . . . . . . . . . . . 15 76 5.2. Packet format . . . . . . . . . . . . . . . . . . . . . . . 15 77 6. Informative References . . . . . . . . . . . . . . . . . . . . 24 78 7. Author's Address . . . . . . . . . . . . . . . . . . . . . . . 24 80 1. Introduction 82 The inspiration of this routing protocol comes from the natural water 83 flow, which is a phenomenon of potential energy driven. Water flows 84 through all feasible channels from high potential site to low 85 potential site. If in every router all feasible next-hops for one 86 certain destination can be found, then all the packets to that 87 destination can be transferred in many paths. 89 This routing protocol obeys the Internet philosophy of "hop-by-hop 90 routing paradigm" and enhances it with "multiple feasible next-hops". 91 That means protocol try to calculate multiple next-hops for each node 92 and not find multi-path end to end. The forwarding direction of 93 packets is constrained by routing metrics. Different packets to one 94 destination can be distributed into multiple next-hops in parallel, 95 which can make full use of all feasible next hops, so that the link 96 utility ratio is globally even. 98 Compared with nature water flow phenomenon, the routing protocol 99 defines a routing metric named as node potential in communication 100 networks. Node potential is a parameter to measure the ability to 101 transfer packets from one certain node to its destination. So the 102 routing protocol is named as node potential oriented multiple next- 103 hops routing protocol (NP-MNRP in short). 105 NP-MNRP is designed to calculate multiple next-hops for one 106 destination in network without knowing the globally topology 107 information. Distance vector routing protocols such as RIP and BGP 108 are used for reference. NP-MNRP protocol is consisted of network 109 reachable information advertisement process and node potential 110 calculation process. But unlike those protocols, NP-MNRP ensures the 111 following properties. 113 (1) Multiple feasible next-hops for each destination. When node finds 114 the main next-hop unreachable, it chooses one from the backup 115 next-hops to forward the packet. 117 (2) Accelerate the convergence speed and reduce route flap. Compared 118 with the single shortest-path routing, NP-MNRP can effectively avoids 119 congestion and shorten protection switching delay. The path 120 establishment and maintenance can be accomplished by routing 121 information advertisement mechanism between peers. The control 122 overhead of the protocol is smaller than other multi-path routing 123 protocols. When kinds of concurrent failures occur in network, NP- 124 MNRP can provide more feasible next-hops and high recovery 125 probability. 127 2. Terminology 129 Carrier Network: The network in which the nodes run Node Potential 130 Oriented Routing Protocol. 132 User Network: The network that needs message transfer service 133 provided by Carrier Network. 135 Boundary Node: According to the location of nodes in the carrier 136 network, the nodes are divided into boundary nodes and intermediate 137 nodes. Boundary nodes are also divided into two categories according 138 to the flow direction. In terms of user network flow, the node 139 through which flow into the carrier network, is called ingress node; 140 the node through which flow out of the carrier network, is called 141 egress node. 143 Intermediate Node: The other nodes in the carrier network except the 144 Boundary Nodes. 146 Potential Reference Node: The egress nodes which the user network 147 traffic flows out from the carrier network. In the route calculation 148 process, these nodes will be set its node potential value to zero and 149 be act as reference node in node potential computation procedure. 150 Network Layer Diagram: The diagram that describes the distribution of 151 the layer value of every node relative to a destination node. 153 Node Potential: A metric that measures the accessibility from a node 154 to zero potential nodes in the carrier network. 156 Router ID: A 32-bit number assigned to each router running the NP- 157 MNRP protocol. This number uniquely identifies the router in the 158 carrier network. One algorithm for Router ID assignment is to choose 159 the largest or smallest IP address assigned to the router. 161 Set of Available Next-hops: The set of available next-hops of node i 162 when it sends packets to the destination node j, which is denoted as 163 A(i,j). 165 Network Layer Reachable Information Flood Advertisement Packet 166 (NLRI-FAP): The packet is used to advertise the information of 167 binding relations between network prefix and egress nodes to its 168 neighbors. IP address and subnet mask of its binding user network are 169 included in this packet. 171 Network Layer Reachable Information Specific Request Packet (NLRI- 172 SRP): The packet is used to request a particular egress node for 173 certain prefix binding relationship information. IP address and 174 subnet mask of user network whose binding relationship needs to know 175 are included in this packet. 177 Network Layer Reachable Information Direction Answer Packet (NLRI- 178 DAP): The packet is used to respond to a Network Layer Reachable 179 Information Specific Request Packet. IP address and subnet mask of 180 user network and its bound router ID are included in this packet. 182 Network Layer Graph Construction Trigger Packet (NLG-CTP): The packet 183 is used to trigger the building of network layer diagram. 185 Network Layer Graph Information Advertisement Packet (NLG-IAP): The 186 packet is used to advertise its layer information relative to one 187 egress node to its neighbors. The egress node ID and its layer value 188 relative to this egress node is included in this packet. 190 Network Layer Graph Routing Request Packet (NLG-RRP): The packet is 191 used to request the neighbors to update it's layer information 192 relative to one egress node and this egress node ID is included in 193 this packet. 195 Network Layer Graph Request Update Packet (NLG-RUP): The packet is 196 used to inform the nodes which are on a particular layer relative to 197 one destination node, to rebuild their layer information and that 198 layer value is included in this packet. 200 Link State Detect Packet (Detect): The packet is used to detect the 201 link status between itself and its neighbors. The sequence number of 202 this packet and the period for sending Detect are included in this 203 packet. 205 REPLY Packet (REPLY): The packet is used to respond to the Detect 206 indicating the good link state. The sequence number of this packet 207 and the period for sending Detect are included in this packet. 209 3. Protocol operation 211 3.1. LFBs Network prefix information advertisement 213 Because NP-MNRP protocol is designed as an IGP inside the autonomous 214 system, it should route transit network traffic and local network 215 traffic. The network IP prefix is divided into two parts: the IP 216 prefix information of transit network and the IP prefix information 217 of the network running NP-MNRP protocol own. 219 In view of NP-MNRP protocol, network is divided into user network and 220 carrier network, as shown in the figure 1. User network is 221 abbreviated as UN and carrier network is abbreviated as CN. Each node 222 in CN will run NP-MNRP protocol to establish multiple next-hops 223 routing information base. Otherwise, it is not necessary for nodes in 224 UN to run NP-MNRP protocol. 226 CNRT: Carrier Network Router 227 ---- ---- ---- 228 / \ / \ / \ 229 * UN1 * * UN2 * * UN3 * 230 \----/ \----/ \----/ 231 | | | 232 ******|*******************|*******************|****** 233 * +-----+ +-----+ +-----+ * 234 * |CNRT1|-------------|CNRT2|-------------|CNRT3| * 235 * +-----+ +-----+ +-----+ * 236 * | | | * 237 * | | | * 238 * +-----+ +-----+ +-----+ * 239 * |CNRT5|-------------|CNRT6|-------------|CNRT4| * 240 * +-----+ CN +-----+ +-----+ * 241 ******|***************************************|****** 242 __|_ __|_ 243 /----\ /----\ 244 * UN5 * * UN4 * 245 \----/ \----/ 246 Figure 1: Network Model 248 The nodes in UN will finish local communication and transmit the 249 network traffic whose destinations are not in the user network itself 250 to the Carrier network. The network prefix of UN is named as Network 251 Layer reachable information. Carrier network mainly transfer transit 252 traffic for UN. The network prefix of CN is treated as network 253 topology information and will be advertised by potential calculation 254 process. The boundary nodes of CN are also named as egress nodes. 255 They advertise network layer reachable information to neighbor nodes 256 periodically and initiate node potential calculation procedure for 257 itself. 259 This advertisement method separates the information of CN topology 260 from the network layer reachable information and advertises them in 261 different manner. The advertisement of topology information is 262 independent with network layer reachable information. From this way, 263 the flexibility of routing information distribution can be enhanced. 265 3.1.2 Network layer reachable information advertisement 267 Network layer reachable information that means the user network 268 prefix is advertised through NLRI-FAP, NLRI-SRP and NLRI-DAP packets. 269 The boundary nodes in CN are responsible for advertising user network 270 reachable information, as shown in the figure 2. 272 ................ 273 . UN . 274 . Host1 Host2 . 275 . \ / . 276 . \ / . 277 . +-----+ . 278 . |UNRT1| . 279 . +-----+ . Host1 Host2 .Host1 Host2 280 .......|........ \ / \ / 281 ****************|*****************\ /***************** \ / 282 * +------+ +------+ * +-----+ 283 * +-----|CNBRT1|------------|CNBRT2|----------------|UNRT2| 284 * | +------+ +------+ * +-----+ 285 * | | | | 286 * | | | * | 287 * | +-----+ +-----+ +-----+* | 288 * | |CNRT6|-------------|CNRT3|-------|CNRT2|* | 289 * | +-----+ +-----+ +-----+* | 290 * | | | | * | 291 * | | | | * | 292 * +------+ +-----+ +-----+ +------+* | 293 * |CNBRT4|---|CNRT5|-------------|CNRT4|------|CNBRT3|-------+ 294 * +------+ +-----+ CN +-----+ +------+* 295 ******|******************************************/ \*** 296 ......|......... / \ 297 +-----+ . Host1 Host2 298 |UNRT3| . 299 +-----+ . 300 / \ . 301 / \ . 302 Host1 Host2 . 303 ................ 304 Figure 2: Network layer reachable information advertisements 306 CNRT: Carrier Network Router. 308 CNBRT: Carrier Network Boundary Router. 310 The boundary nodes in CN advertise network layer reachable 311 information to neighbor nodes periodically through NLRI-FAP. Once 312 receiving the NLRI-FAP, the nodes in CN extract network prefix 313 information from packets and add them to the network layer reachable 314 information database of their own. 316 When the nodes in CN don't know user network prefix, these nodes will 317 act as inquirers and send NLRI-SRP to query other nodes and set a 318 query timer. When a node receives the NLRI-SRP, and the network 319 prefix information or attached router information is in its database, 320 it responses to inquirer with a NLRI-DAP packet. Otherwise, it sends 321 the NLRI-SRP packet to its neighbors except for the enquirers. This 322 process will continue until the inquirer get an response from other 323 nodes or such query timer is timed out. 325 When bound to the egress node (relative information is absent in 326 network layer reachable information database of the node), the node 327 send NLRI-SRP flooding to inquirer, called enquirers. 329 3.2. Neighbor Node Discovery and Adjacency establishment 331 When a new node joins in the network, other nodes discover it and 332 initialize their local routing tables as the following steps. 334 (1) Broadcast a Detect packet and a NLG-CTP packet. This node sets 335 the sequence number of Detect with 0.The Detect will be sent 336 periodically by defaulted period set in the protocol; 338 (2) When other nodes receive a Detect packet or a NLG-CTP packet, 339 they operate as follows. 340 (a) If the received Detect message is ca from an unknown node and 341 sequence number is equal to 0, the receivers know that a new 342 node add to network and add it to their neighbor node database 343 and record sequence number of the Detect message; 344 (b) Reply to the unknown node with an REPLY packet; Send a NLG- 345 IAP packet which contains all egress nodes information in the 346 database; 347 (c) According to the computation rules of node potential, they 348 compute layer value and potential value relative to the egress 349 node. 350 (3) When received a REPLY packet and a NLG-IAP packet, the new node 351 operates as follows. 352 (a) Adds the neighbor node to routing information database; 353 (b) According to NLG-IAP, it calculates its own layer value as 354 following formula. 355 L(i,i)=0, 356 L(i,j)=min[L(k,j)]+1, 357 for each k blongs to Ki, j blongs to N, and k,j are not equal 358 to i. 359 L(i,j) is the layer value of node i reference to egress node 360 j, N is the set of network nodes, Ki is the set of neighbor nodes 361 about node i. 362 (c) Based on the layer values of its neighbors, bandwidth and its 363 own layer value, the new node computes node potential value of 364 its neighbors and its own. 366 3.3. Calculation of node potential value 367 3.3.1 Definition of node potential value 369 NP-MNRP defines node potential value as a mixed metric of hop count 370 and bandwidth. Hop count metric records the number of routers which a 371 packet passes through and each router is recorded as one hop. The 372 actual link bandwidth is allocated\configured by router in the 373 network initialization. 375 3.3.2 Protocol packets sending and processing 377 3.3.2.1 Network Layer Graph Routing Request Packet processing 379 Network Layer Graph Routing Request Packet (NLG-RRP) has two 380 different types. One type is all nodes layer information request 381 packet which will request the receiver to send layer information of 382 all nodes. The other is partial nodes layer information request 383 packet which will request the receiver to send layer information of 384 the specified nodes. 386 The NLG-RRP will be used in the following conditions. 388 Condition 1: When a new node is attached to the network, all nodes 389 layer information request packet will be sent to its neighbors. 391 Condition 2: When the node want to get some certain network prefix 392 information from its neighbors, partial nodes layer information 393 request packet will be sent. 395 Once receiving a NLG-RRP packet, each node should process as the 396 following steps. 398 (a) Firstly, the type of the packet will be verified whether or not 399 it is a correct NLG-RRP packet. 401 (b) When NLG-RRP is the all nodes layer information request packets, 402 it sends its own layer information relative to the other nodes to the 403 request node. 405 (c) When NLG-RRP is the partial nodes layer information request 406 packet, it sends its own layer information relative to the 407 destination node in the packet to the query node. 409 3.3.2.2 Network Layer Graph Information Advertisement Packet sending 411 Network Layer Graph Information Advertisement Packet (NLG-IAP) is 412 broadcast to its neighbors in the following cases. 414 Case 1: Each layer value of every node is specified after the network 415 layer graph has been divided. 417 Case 2: When the layer information of any node is changed, which may 418 be caused by the change of layer values of some routers when they 419 received NLG-FAP or some new nodes are added to the network. 421 Case 3: A NLG-RRP packet is received and the layer value of receiver 422 reference to certain egress node is changed. 424 The processing rules of NLG-IAP are described in section 3.5. 426 3.3.3 Calculation of the node potential value 428 In NP-MNRP, the node potential value is a mixed metric, including hop 429 count and actual link bandwidth. Each egress node activates its 430 neighbors to build Network Layer graph by sending a NLG-CTP packet to 431 neighbors. Calculated as follows. 433 (1) In the algorithm initialization, egress node assigns its layer 434 value as 0, and then sends a NLG-CTP packet to its neighbors, which 435 contains the actual link bandwidth. 437 (2) The neighbor node that received a NLG-CTP packet from the 0- 438 layer node sets itself as 1-layer, and generates a NLG-CTP packet and 439 sends to its neighbors. And so on. 441 (3) Repeat the above step (2) until the nodes whose layer value are 442 smaller than f-layer which have been determined. 444 (4) After the f-layer has been constructed completely, each node in 445 f-layer knows that it is in f-layer and knows that which neighbors 446 are in f-1 layer. The nodes in f-1layer know that which ones are in f 447 layer, which ones are in f-1 layer, and which ones are in f-2 layer. 449 (5) Supposed f-layer has been constructed, and the algorithm has not 450 been terminated, then the construction of the f +1 layer will begins. 451 The nodes in f-layer will send a NLG-CTP packet to its neighbors. 453 (6) When all the nodes are traveled, algorithm ends. 455 All nodes in the network not only are aware of their own layer value 456 but also know the layer values of their neighbors and the actual 457 bandwidth between themselves. 459 Next, each node calculates the potential value as follows. 461 (1) 0-layer nodes directly define their own potential value as 0; 463 (2) Each node of the other layers chooses the largest potential value 464 node among its neighbors in the same and lower layers as its 465 reference node for defining potential value, then defines its 466 potential value as potential value of the reference node plus one and 467 potential values of its neighbors which are equal to their layer 468 value; 470 (3) When each potential value of the neighbors is defined, the node 471 will choose the neighbor nodes whose potential values are less than 472 its own as feasible next-hops of itself. 474 3.4. network event sensing 476 NP-MNRP protocol can sense events such as new node add to network or 477 neighbor node is down. The node senses these events through sending 478 out Detect packet and receiving REPLY packet periodically. 480 3.4.1 Message sending and processing 482 Each NP-MNRP node broadcasts periodically Detect packet. When a 483 Detect packet is received, the receiver sends a REPLY packet to the 484 sender. The detailed steps are as follows. 486 Step1: Each node broadcasts periodically a Detect packet. Detect 487 packet carries a sequence number and periodic interval. 489 Step2: When a Detect packet is received, its sequence number is 490 compared with the expected sequence number for this neighbor. Then 491 the receiver sends a REPLY packet to the sender and evaluates inverse 492 link quality according to the sequence number. 494 Step3: When a Reply packet is received, its sequence number should be 495 equaled to the sequence number of the Detect packet. Then the 496 receiver evaluates link quality according to the sequence number and 497 the use of sent/receive message time. 499 3.4.2 Forward direction link sensing 501 A(Ti) represents the mean interval from node i sending out Detect 502 packet to receiving REPLY packet. FA (Ti) represents the latest mean 503 interval time. Node i adjust the period of sending out Detect packet 504 according to the following rules. 506 (1) If FA(Ti) < A(Ti), it means that the link quality is stable. At 507 this period, when three continuous Detect packets are all low, then 508 increase the Detect interval; 510 (2) If FA(Ti) > A(Ti), it means that the link quality is unsteady or 511 become bad. At this period, when three continuous Detect packets are 512 all high, then reduce Detect interval; 514 (3) When a Detect packet is sent out but a REPLY packet is not 515 received in the 2*FA(Ti) time, the node will reduce the period at 516 half, then continue sending out the next sequence number Detect 517 packet. If a REPLY packet still not received, the node insulates that 518 node and thinks link breakdown or link congestion. 520 (4) The isolate node will not be used as the next-hop to forwarding 521 packets. The processing node should continue sending Detect packet 522 and adjust strategy according to the following conditions. 523 (a) If three continuous REPLY packets received, then the node 524 deletes the isolate node and uses nodes which reply the REPLY 525 packet as the next-hops to forwarding packets. 527 (b) If no packet is received after 6 Detect intervals, so that 528 node is thought to be breakdown, unable to send Detect packet 529 again. Waiting 531 (c) If the node can receive a Detect packet or a REPLY packet 532 which is send out from isolate node, and then it will continue 533 sending a Detect packet until the isolate node recovery or judge 534 node breakdown. 535 3.4.3 Inverse link sensing 537 Each node broadcasts periodically Detect packet. Every Detect carries 538 a sequence number and the interval. 540 When a Detect packet is received, compared sequence number with the 541 next expected sequence number for this neighbor, if the sequence 542 number of the received Detect packet is higher than the expected, 543 then one or more Detect packets have been missed. If the sequence 544 number is lower, then this neighbor decrease the Detect interval, and 545 part of the history must be undone. 547 From the history of received Detect packets, a node computes an 548 estimate of the inverse link quality. 550 3.5. Update of the node potential 552 3.5.1. Update of network layer value 554 As the set of next-hop is empty, the node will trigger update about 555 the layer value through the following operations. 557 (1) Firstly, the node will check whether the set of its neighbors on 558 the same layer is empty. If is not, it will change itself layer value 559 and generate NLG-IAP packets that are sent to its neighbors. 561 (2) If the set is empty, then the node will perform the following 562 steps. 564 (a) Flooding NLG-RUP packets, whose layer value will be revised 565 to the old layer value minus 2, however, if old layer value minus 566 2 is less than 0, the value is set to 0. What's more, all 567 information about this egress node will be deleted. 569 (b) The node received a NLG-RUP packet will check if it has ever 570 received this message. If having received such message, the 571 packet will be ignored, otherwise view the layer value in this 572 packet. If the value is greater than the value of its own, the 573 node will discard the packet, otherwise, go on flooding NLG-RUP 574 packets to its neighbors and delete all information about this 575 egress node. 577 (c) If the layer value in the packet is equal to its own, the 578 node will stop flooding to send NLG-RUP and send a NLG-CTP packet 579 about the egress node. 581 (d) Neighbor node received a NLG-CTP packet will calculate its 582 new layer value. If new value is same with the original, the node 583 stops sending NLG-CTP packets and the layer value update 584 algorithm will terminate. 586 3.5.2. Update of node potential value The potential value of the 587 nodes will be updated in the following conditions. 589 (1) Potential value update caused by NLG-IAP packet. The main content 590 of a NLG-IAP packet are layer information of a node relative to the 591 egress node in the network. The node adjusts its potential value 592 according to the NLG-IAP packets received from its neighbors. 593 Specific updated as follows. 595 (a) NLG-IAP packet generation When the node finds its layer 596 information relative to one certain egress node changed, the new 597 layer information relative to all egress nodes will be written 598 into its generated NLG-IAP packet. 600 (b) NLG-IAP to send The node will broadcast its generated NLG-IAP 601 packets to its neighbors, and then wait for confirmation from its 602 neighbors. When the node receives REPLY pockets with sequence 603 number 0XFFFF from its neighbors, this update ends. 605 (c) When the node received the NLG-IAP packet, it performs the 606 following steps. 608 Firstly, this node will verify NLG-IAP packet. If the packet is 609 validated, it sends a REPLY packet with sequence number 0XFFFF to 610 source node of NLG-IAP packet. 612 Secondly, this node will extract layer information from the NLG- 613 IAP packet supposing a received routing entries includes RUIi =< 614 RouterID, EgressnodeID, Layi> and the corresponding routing entry 615 stored in the database is RUI'i =< RouterID, EgressnodeID, 616 Lay'i>, when one of the following three cases are met, the node 617 update its own routing table according to the information 618 received. 620 Case 1: If the EgressnodeID included in the received routing 621 table entry dose not exist in its own routing table, the router 622 will add it and send a NLG-RRP packet about the destination 623 address of the network to its neighbors. After received NLG-IAP 624 packets, it will calculate its layer value relative to this 625 egress node according to formula in 3.2, and get layer values of 626 it's neighbors, then define the potential value of neighbor node 627 reference to this destination node. 629 Case 2: If the EgressnodeID included in the received routing 630 table entry exists in its own routing table and Lay'i < Layi, the 631 router will adjust the layer values of its neighbors and 632 potential value. If the potential value of neighbor is greater 633 than its own and the neighbor node is just in its own next-hop 634 collection, the router will remove the node from next-hop 635 collection, if not, do nothing. 637 Case 3: If Layi < Lay, then the router will adjust the layer 638 value of neighbor node and potential value. If the potential 639 value of neighbor is less than its own and the neighbor node is 640 not in its own next-hop collection, then the router will add it 641 into the next-hop 643 (2) Potential value update caused by the change of layer value 645 When the layer value reference to a particular destination node 646 changes, firstly it will modify layer value of itself and its 647 neighbors. Then the new potential value will be calculated according 648 to update strategy. 650 4. Routing information base 652 Each routing node maintains the Routing Information Base to forward 653 IP packets. NP-MNRP protocol can calculate multiple next-hops routing 654 information in the network. The route computation process descried in 655 Section 3 will record all the feasible next-hops for every 656 destination. The multiple next-hops routing entry is composed of 657 three fields. 659 The first field is named as destination IP address field. 661 The second field is named as the destination IP address mask filed. 662 The first and second fields are 32-bit numbers which define network 663 destination information of each routing entry. And the route 664 information base is indexed by the first and second field. 666 The third field is named as feasible next-hop filed, whose form is a 667 couple of next-hop IP address value and node potential difference 668 value. The next-hop IP address is IP address of the neighbor node who 669 will act as a feasible next-hop for this routing node to forward IP 670 packets to the network destination. Compared with the single next-hop 671 routing information, the number of feasible next-hop filed in a 672 multiple next-hops routing entry may be a value bigger than one. 674 The routing node will gain more agility in IP packet forwarding 675 procedure. It can choose forward all the packets to one best next-hop 676 and use other feasible next-hop entries as backup entries. Through 677 this way, the network availability will be improved in the scene that 678 network failure or mal-function occurs frequently. It can also choose 679 forward all the IP packets to all feasible next-hop entries. In this 680 manner, this routing node can assign each next-hop a traffic ratio 681 for each destination. All the packets will be forwarded to variable 682 next-hop pro rata. This will make the network resource utilization 683 more evenness and avoid network congestion in some ways. 685 5. NP-MNRP packets format 687 The NP-MNRP protocol runs directly over the IP network layer. Before 688 any packet format is described, the details of the NP-MNRP 689 encapsulation are explained. 690 5.1. Encapsulation of NP-MNRP packets 692 NP-MNRP runs directly over the Internet Protocol's network layer. 693 Therefore, NP-MNRP packets are encapsulated solely by IP and local 694 data-link headers. NP-MNRP does not define a way to fragment its 695 protocol packets, and depends on IP fragmentation when transmitting 696 packets larger than the network MTU. 698 NP-MNRP uses IP protocol number 99. Routing protocol packets are sent 699 with IP precedence set to inter-network Control. NP-MNRP protocol 700 packets should be given precedence over regular IP data traffic, in 701 both sending and receiving. 703 5.2. Packet format 705 There are nine distinct NP-MNRP packet types. All NP-MNRP packet 706 types begin with a standard 20 byte header. This header is described 707 first. Each packet type is then described in a succeeding section. In 708 these sections each packet's division into fields is displayed, and 709 then the field definitions are enumerated. 711 5.2.1 The NP-MNRP packet header 713 Every NP-MNRP packet starts with a standard 20 byte header. This 714 header contains all the information necessary to determine whether 715 the packet should be accepted for further processing. This 716 determination is described in Section 5.2 of the specification. 718 0 1 2 3 719 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 720 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 721 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | 722 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 723 | Version # | Type | Packet length | 724 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 725 | Router ID | 726 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 727 | Check Sum | Authentication Type | 728 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 729 | Authentication Info(8 array 0-3) | 730 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 731 | Authentication Info(8 array 4-7) | 732 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 734 Version 735 The NP-MNRP version number. This specification documents version 1 736 of the protocol. 738 Type 739 Type Description 740 --------------------- 741 1 NLRI-FAP 742 2 NLRI-SRP 743 3 NLRI-DAP 744 4 NLG-CTP 745 5 NLG-IAP 746 6 NLG-RRP 747 7 NLG-RUP 748 8 Detect 749 9 REPLY 751 Router ID 752 The Router ID of the packet's source. 754 Check Sum 755 The standard IP checksum of the entire content of the packet. Note 756 that the packet starts with the NP-MNRP header but excluding the 64- 757 bit authentication field. If the length of the package is less than 758 16-bit, 0 byte WOULD be added before the checksum byte. 760 Authentication Type Identify the authentication procedure used for 761 the packet. Authentication is discussed in the specification. 763 Authentication Info 64-bit authentication information field depends 764 on the chosen authentication type, to carry identification 765 information such as identity authentication. 767 5.2.2 Various types of protocol packets 769 NP-MNRP protocol packets have total of 9 species. 771 5.2.2.1 Network Layer Reachable Information Flood Advertisement 772 Packet, NLRI-FAP 774 NLRI-FAP packet is NP-MNRP packet type 1.The packet is send by an 775 egress node in the carrier network and is used to advertise the user 776 network prefix information which is bound to this node. The node that 777 received this packet WOULD consider this egress node is reachable and 778 the user network which is bound to this node is reachable too. 780 0 1 2 3 781 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 782 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 783 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | 784 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 785 | Version # | 1 | Packet length | 786 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 787 | Router ID | 788 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 789 | Check Sum | Authentication Type | 790 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 791 | Authentication Info(8 array 0-3) | 792 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 793 | Authentication Info(8 array 4-7) | 794 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 795 | IP address of the network 1 | 796 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 797 | Subnet mask of the network 1 | 798 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 799 | ...... | 800 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 801 | IP address of the network n | 802 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 803 | Subnet mask of the network n | 804 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 806 IP address of the network 807 The IP address of a user network is bound to this egress node. 809 Subnet mask of the network 810 Subnet mask of user network is denoted in the above field. 812 5.2.2.2 Network Layer Reachable Information Specific Request Packet, 813 NLRI-SRP 815 NLRI-SRP packet is NP-MNRP packet type 2.This packet is used by the 816 node in the carrier network to request the network layer reachable 817 information. When the node doses not know which egress node, one 818 network prefix is bound to, the NLRI-SRP packet is sent. 820 If the IP address and the subnet mask of the network 1 is all 0, all 821 the network prefixes WOULD be requested, and usually this request is 822 sent by a node which just joins into the carrier network. 824 0 1 2 3 825 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 826 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 827 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | 828 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 829 | Version # | 2 | Packet length | 830 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 831 | Router ID | 832 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 833 | Check Sum | Authentication Type | 834 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 835 | Authentication Info(8 array 0-3) | 836 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 837 | Authentication Info(8 array 4-7) | 838 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 839 | IP address of the network 1 | 840 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 841 | Subnet mask of the network 1 | 842 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 843 | ...... | 844 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 845 | IP address of the network n | 846 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 847 | Subnet mask of the network n | 848 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 850 IP address of the network 851 The IP address of a user network whose binding relationship this 852 node want to request. 854 Subnet mask of the network 855 The Subnet mask of a user network denoted in the above field, who 856 binding relationship this node wants to request 858 5.2.2.3 Network Layer Reachable Information Direction Answer Packet, 859 NLRI-DAP 861 NLRI-DAP packet is NP-MNRP packet type 3. The node that receives the 862 NLRI-SRP packet WOULD check its information database to seek for the 863 corresponding binding relationship. If the binding relationship 864 exists in its own information database, it WOULD send NLRI-DAP packet 865 to the requesting node, if not, it WOULD send NLRI-SRP packets to its 866 all neighbor nodes except for the requesting node. 868 If a node who sends the NLRI-SRP packets at the same time receives 869 more than one packet about the same IP prefix binding relationship, 870 and these packets are conflictive, it WOULD go on sending NLRI-SRP 871 0 1 2 3 872 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 873 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 874 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | 875 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 876 | Version # | 3 | Packet length | 877 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 878 | Router ID | 879 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 880 | Check Sum | Authentication Type | 881 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 882 | Authentication Info(8 array 0-3) | 883 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 884 | Authentication Info(8 array 4-7) | 885 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 886 | IP address of the network | 887 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 888 | Subnet mask of the network 1 | 889 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 890 | Egress node ID 1 | 891 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 892 | ...... | 893 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 894 | IP address of the network n | 895 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 896 | Subnet mask of the network n | 897 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 898 | Egress node ID n | 899 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 901 IP address of the network 902 The IP address of a user network whose binding relationship is wants 903 to know in the receiving NLRI-SRP packet. 905 Subnet mask of the network 906 The subnet mask of a user network denoted in the above field, whose 907 binding relationship is wants to know in the receiving NLRI-SRP 908 packet. 910 Egress node ID 911 This field denotes the user network, whose IP address and subnet 912 mask emerge in the front two fields, is bound to this egress node. 914 5.2.2.4 Network Layer Graph Construction Trigger Packet, NLG-CTP 915 NLG-CTP packet is NP-MNRP packet type 4.When one egress node joins 916 into the carrier network, it WOULD send this packet to urge the other 917 nodes to build network layer graph relative to itself. 919 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 920 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 921 Byte 1 | Byte 2 | Byte 3 | Byte 4 | 922 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 923 Version # | 4 | Packet length | 924 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 925 | Router ID | 926 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 927 Check Sum | Authentication Type | 928 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 929 Authentication Info(8 array 0-3) | 930 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 931 Authentication Info(8 array 4-7) | 932 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 933 Egress node ID | 934 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 935 Layer value | 936 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 938 Egress node ID The node that received this packet calculates its 939 layer value relative to this egress node. 941 Layer value The value of the sender relative to the node denoted in 942 the above field 944 5.2.2.5 Network Layer Graph Information Advertisement Packet, NLG-IAP 946 NLG-IAP packet is NP-MNRP packet type 5. This packet is sent to all 947 neighbor nodes using multicast address to advertise its layer value 948 relative to the node whose ID includes in this packet, this packet is 949 usually to start the neighbor nodes to adjust their potential 950 dynamically. 952 0 1 2 3 953 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 954 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 955 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | 956 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 957 | Version | 5 | packet length | 958 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 959 | Router ID | 960 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 961 | Egress node ID | 962 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 963 | Check Sum | Authentication Type | 964 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 965 | Authentication Info(8 array 0-3) | 966 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 967 | Authentication Info(8 array 4-7) | 968 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 969 | Egress node ID 1 | 970 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 971 | Layer value 1 | 972 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 973 | ....... | 974 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 975 | Egress node ID n | 976 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 977 | Layer value n | 978 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 980 Egress node ID 981 The receiver need adjust its layer value relative to this node 983 Layer value 984 This is the layer value of the sender relative to the egress node 985 denoted in the above field. 987 5.2.2.6 Network Layer Graph Routing Request Packet, NLG-RRP 989 NLG-RRP packet is NP-MNRP packet type 6. This packet is used by one 990 node to request the neighbor nodes to send their own layer 991 information relative to the appointed egress node to it. This packet 992 has two types: one is for all nodes and the other is for some nodes. 993 If the egress node ID in the packet is empty, the packet is NLG-RRP 994 packet for all nodes, if not; the packet is NLG-RRP packet for the 995 appointed nodes included in this packet. 997 0 1 2 3 998 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 999 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1000 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | 1001 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1002 | Version | 6 | packet length | 1003 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1004 | Router ID | 1005 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1006 | Check Sum | Authentication Type | 1007 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1008 | Authentication Info(8 array 0-3) | 1009 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1010 | Authentication Info(8 array 4-7) | 1011 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1012 | Egress node ID1 | 1013 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1014 | Egress node ID2 | 1015 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1016 | ....... | 1017 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1019 Egress node ID 1020 This field denotes the receiver need to respond its layer value 1021 relative to this egress node. 1023 5.2.2.7 Network Layer Graph Request Update Packet, NLG-RUP 1025 NLG-RUP packet is NP-MNRP packet type 7. When a node finds its next 1026 hops and its neighbors on the same layer are all unreachable, it 1027 sends this packet to neighbors to update its layer value. 1028 0 1 2 3 1029 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 1030 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1031 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | 1032 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1033 | Version | 7 | packet length | 1034 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1035 | Router ID | 1036 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1037 | Check Sum | Authentication Type | 1038 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1039 | Authentication Info(8 array 0-3) | 1040 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1041 | Authentication Info(8 array 4-7) | 1042 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1043 | Egress node ID | 1045 Egress node ID 1046 This field denotes the receiver needs to update its value relative 1047 to this node 1049 Layer value 1050 The layer value in NLG-RUP packet is the layer value relative to 1051 high egress node minus 2. 1053 5.2.2.8 Link State Detect Packet, Detect 1055 Detect packet is NP-MNRP packet type 8. This packet is periodically 1056 sent to neighbor nodes to evaluate the link quality. 1058 0 1 2 3 1059 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 1060 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1061 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | 1062 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1063 | Version | 8 | packet length | 1064 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1065 | Router ID | 1066 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1067 | Check Sum | Authentication Type | 1068 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1069 | Authentication Info(8 array 0-3) | 1070 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1071 | Authentication Info(8 array 4-7) | 1072 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1073 | Sequence number | Period | 1074 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1076 Sequence number 1077 The sequence number in this packet is the sequence number of the 1078 Detect message, and it is an increasing positive integer. 1080 Period 1081 The period in this packet is the interval time between this to the 1082 last one. 1084 5.2.2.9 REPLY Message Packet, REPLY 1086 REPLY packet is NP-MNRP packet type 9. The node that received a 1087 detect packet will send a reply packet to the sender, which can 1088 evaluate the reverse link quality according to this packet. The 1089 sequence number in this packet denotes it is the reply to the Detect 1090 message that has the corresponding sequence number. If the number is 1091 full-1, it means the packet is confirmation message to a NLG-IAP 1092 message. 1094 0 1 2 3 1095 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 1096 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1097 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | 1098 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1099 | Version | 9 | packet length | 1100 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1101 | Router ID | 1102 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1103 | Check Sum | Authentication Type | 1104 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1105 | Authentication Info(8 array 0-3) | 1106 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1107 | Authentication Info(8 array 4-7) | 1108 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1109 | Serial number | Period | 1110 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1112 Serial number 1113 The sequence number in this packet is the sequence number of the 1114 REPLY, and it is an increasing positive integer. 1116 Period 1117 This field denotes that the node sending this packet will sends 1118 Detect message at this period. 1119 6. Informative References 1121 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1122 Requirement Levels", RFC 2119, March 1997. 1124 7. Author's Address 1126 Julong Lan 1127 National Digital Switching System Engineering and Technological 1128 Research Center 1129 NDSC, No.7 , Jianxue Street,Jinshui District 1130 Zhengzhou, 450002, 1131 P.R.China 1132 Phone: +86-371-8163-2988 1133 Email: ndscljl@163.com 1134 URI: http://www.ndsc.com.cn/ 1136 Jianhui Zhang 1137 National Digital Switching System Engineering and Technological 1138 Research Center 1139 NDSC, No.7 , Jianxue Street,Jinshui District 1140 Zhengzhou, 450002, 1141 P.R.China 1142 Phone: +86-371-8163-2988 1143 Email: ndsc155@163.com 1144 URI: http://www.ndsc.com.cn/ 1146 Bin Wang 1147 National Digital Switching System Engineering and Technological 1148 Research Center 1149 NDSC, No.7 , Jianxue Street,Jinshui District 1150 Zhengzhou, 450002, 1151 P.R.China 1152 Phone: +86-371-8163-2909 1153 Email: ndscmt@163.com 1154 URI: http://www.ndsc.com.cn/ 1156 Wenfen Liu 1157 National Digital Switching System Engineering and Technological 1158 Research Center 1159 NDSC, No.7 , Jianxue Street,Jinshui District 1160 Zhengzhou, 450002, 1161 P.R.China 1162 Phone: +86-371-8163-0340 1163 Email: wenfenliu@sina.com 1164 URI: http://www.ndsc.com.cn/ 1166 Tong Duan 1167 National Digital Switching System Engineering and Technological 1168 Research Center 1169 NDSC, No.7 , Jianxue Street,Jinshui District 1170 Zhengzhou, 450002, 1171 P.R.China 1172 Phone: +86-371-8163-2670 1173 Email: duantong21@126.com 1174 URI: http://www.ndsc.com.cn/