Network Working Group J.L. Lan
Internet Draft J.H. Zhang
Expires: January 28, 2011 B.Wang
W.F. Liu
National Digital Switching System Engineering and Technological
Research Center, P.R.China
X.Li
BEIJING UNIVERSITY OF POSTS AND TELECOMMUNICATIONS
Node Potential Oriented Multi-NextHop Routing Protocol
draft-ndsc-npmnrp-routing-protocol-01.txt
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. This document may not be modified,
and derivative works of it may not be created, and it may not be
published except as an Internet-Draft.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
This Internet-Draft will expire on January 20, 2009.
Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents carefully,
as they describe your rights and restrictions with respect to this
document. Code Components extracted from this document must include
NDSC Expires January 28, 2011 [Page 1]
Internet-Draft The NPMNRP Routing Protocol July 2010
Simplified BSD License text as described in Section 4.e of the Trust
Legal Provisions and are provided without warranty as described in
the Simplified BSD License.
Abstract
The Node Potential Oriented Multi-Nexthop Routing Protocol (NP-
MNRP)bases on the idea of "hop-by-hop routing forwarding, multi-
backup next hop" and combines with the phenomena that water flows
from higher place to lower. NP-MNRP defines a metric named as node
potential, which is based on hop count and the actual link bandwidth,
and calculates multiple next-hops through the potential difference
between the nodes.
Table of Contents
1. Introduction.................................................3
2. Conventions used in this document............................5
3. Terminology..................................................5
4. Protocol operation...........................................8
4.1. Network prefix Information Advertisement................8
4.1.1. Methodology........................................8
4.1.2. Network Layer Reachable Information Advertisement..9
4.2. Neighbor Node Discovery and Adjacency Establishment....11
4.3. Calculation of Node Potential Value....................13
4.3.1. Protocol Packets Sending and Processing...........13
4.3.1.1. Network Layer Graph Routing Request Packet
processing............................................13
4.3.1.2. Network Layer Graph Information Advertisement
Packet sending........................................14
4.3.2. Calculation of the Node Potential Value...........14
4.4. network Event Sensing..................................16
4.4.1. Message Sending and Processing....................16
4.4.2. Forward Direction link Sensing....................17
4.4.3. Inverse Link Sensing..............................18
4.5. Update of the Node Potential...........................19
4.5.1. Update of Network Layer Value.....................19
4.5.2. Update of Node Potential Value....................20
5. Routing Information Base....................................22
6. NP-MNRP Packets Format......................................23
6.1. Encapsulation of NP-MNRP Packets.......................23
6.2. Packet Format..........................................24
6.2.1. The NP-MNRP Packet Header.........................24
6.2.2. Various types of Protocol Packets.................26
6.2.2.1. Network Layer Reachable Information Flood
Advertisement Packet, NLRI-FAP........................26
NDSC Expires January 28, 2011 [Page 2]
Internet-Draft The NPMNRP Routing Protocol July 2010
6.2.2.2. Network Layer Reachable Information Specific
Request Packet, NLRI-SRP..............................27
6.2.2.3. Network Layer Reachable Information Direction
Answer Packet, NLRI-DAP...............................28
6.2.2.4. Network Layer Graph Construction Trigger Packet,
NLG-CTP...............................................31
6.2.2.5. Network Layer Graph Information Advertisement
Packet, NLG-IAP.......................................31
6.2.2.6. Network Layer Graph Routing Request Packet, NLG-RRP
.....................................................32
6.2.2.7. Network Layer Graph Request Update Packet, NLG-RUP
.....................................................33
6.2.2.8. Link State Detect Packet, Detect.............34
6.2.2.9. REPLY Message Packet, REPLY..................35
7. References..................................................36
8. Acknowledgments.............................................37
1. Introduction
The inspiration of this routing protocol comes from the natural
water flow, which is a phenomenon of potential energy driven. Water
flows through all feasible channels from a high potential site to a
low potential site. If in every router all feasible next-hops for one
certain destination can be found, then all the packets to that
destination can be transferred in many paths.
This routing protocol obeys the Internet philosophy of "hop-by-hop
routing paradigm" and enhances it with "multiple feasible next-hops".
That means that the protocol can manage to calculate multiple next-
hops for each node and does not find multi-path end to end. The
forwarding direction of packets is constrained by routing metrics.
Different packets to one destination can be distributed into multiple
next-hops in parallel, which can make full use of all feasible next
hops, so that the link utility ratio is globally even.
NDSC Expires January 28, 2011 [Page 3]
Internet-Draft The NPMNRP Routing Protocol July 2010
Compared with the nature water flow phenomenon, the routing protocol
defines a routing metric named as node potential in communication
networks. Node potential is a parameter to measure the ability to
transfer packets from one certain node to its destination. So the
routing protocol is named as the node potential oriented multiple
next-hops routing protocol (NP-MNRP for short).
NP-MNRP is designed to calculate multiple next-hops for one
destination in networks without knowing the globally topology
information. Distance vector routing protocols such as RIP and BGP
are used for reference. The NP-MNRP protocol consists of the network
reachable information advertisement process and the node potential
calculation process.
But unlike those protocols, NP-MNRP ensures the following properties:
(1) Multiple feasible next-hops for each destination. When a node
finds the main next-hop unreachable, it chooses one from the backup
next-hops to forward the packet.
(2) Accelerate the convergence speed and reduce route flap.
Compared with the single shortest-path routing, NP-MNRP can
effectively avoid congestion and shorten protection switching delay.
The path establishment and maintenance can be accomplished by routing
information advertisement mechanism between peers. The control
overhead of the protocol is smaller than other multi-path routing
protocols. When kinds of concurrent failures occur in networks, NP-
MNRP can provide more feasible next-hops and high recovery
probability.
NDSC Expires January 28, 2011 [Page 4]
Internet-Draft The NPMNRP Routing Protocol July 2010
2. Conventions used in this document
In examples, "C:" and "S:" indicate lines sent by the client and
server respectively.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC-2119 [RFC2119].
In this document, these words will appear with that interpretation
only when in ALL CAPS. Lower case uses of these words are not to be
interpreted as carrying RFC-2119 significance.
In this document, the characters ">>" preceding an indented line(s)
indicates a compliance requirement statement using the key words
listed above. This convention aids reviewers in quickly identifying
or finding the explicit compliance requirements of this RFC.
3. Terminology
Carrier Network: It refers to the network in which the nodes run the
Node Potential Oriented Routing Protocol.
User Network: It refers to the network that needs message transfer
service provided by the Carrier Network.
Boundary Node: According to the nodes' location in the carrier
network, the nodes are divided into boundary nodes and intermediate
nodes. Boundary nodes are further divided into two categories
according to the flow direction. In terms of user network flow, the
node which flows into the carrier network, is called the ingress node;
the node which flows out of the carrier network, is called egress
node.
Intermediate Node: It refers to the other nodes in the carrier
network except the Boundary Nodes.
NDSC Expires January 28, 2011 [Page 5]
Internet-Draft The NPMNRP Routing Protocol July 2010
Potential Reference Node: It refers to the egress nodes through which
the user network traffic flows out from the carrier network. In the
route calculation process, these nodes will set their node potential
value to zero and act as reference nodes in the node potential
computation procedure.
Network Layer Diagram: It refers to the diagram that describes the
distribution of all nodes' layer value relative to a destination node.
Node Potential: It is a metric that measures the accessibility from a
node to zero potential nodes in the carrier network.
Router ID: It refers to a 32-bit number assigned to each router
running the NP-MNRP protocol. This number uniquely identifies the
router in the carrier network. One algorithm for Router ID assignment
is to choose the largest or smallest IP address assigned to the
router.
Set of Available Next-hops: It refers to the set of available next-
hops of node i when it sends packets to the destination node j, which
is denoted as A (i,j).
Network Layer Reachable Information Flood Advertisement Packet (NLRI-
FAP): The packet is used to advertise the information of binding
relations between network prefix and egress nodes to its neighbors.
The IP address and subnet mask of its binding user network are
included in this packet.
Network Layer Reachable Information Specific Request Packet (NLRI-
SRP): The packet is used to request a particular egress node for
NDSC Expires January 28, 2011 [Page 6]
Internet-Draft The NPMNRP Routing Protocol July 2010
certain prefix binding relationship information. IP address and
subnet mask of user network whose binding relationship needs to know
are included in this packet.
Network Layer Reachable Information Direction Answer Packet (NLRI-
DAP): The packet is used to respond to a Network Layer Reachable
Information Specific Request Packet. The IP address and subnet mask
of user network and its bound router ID are included in this packet.
Network Layer Graph Construction Trigger Packet (NLG-CTP): The packet
is used to trigger the building of network layer diagram.
Network Layer Graph Information Advertisement Packet (NLG-IAP): The
packet is used to advertise its layer information relative to one
egress node to its neighbors. The egress node ID and its layer value
relative to this egress node are included in this packet.
Network Layer Graph Routing Request Packet (NLG-RRP): The packet is
used to request the neighbors' layer information relative to one
egress node and this egress node ID is included in this packet.
Network Layer Graph Request Update Packet (NLG-RUP): The packet is
used to inform the nodes which are on a particular layer relative to
one destination node, to rebuild their layer information and that
layer value is included in this packet.
Link State Detect Packet (Detect): The packet is used to detect the
link status between itself and its neighbors. The sequence number of
this packet and the period for sending Detect are included in this
packet.
NDSC Expires January 28, 2011 [Page 7]
Internet-Draft The NPMNRP Routing Protocol July 2010
REPLY Packet (REPLY): The packet is used to respond to the Detect
indicating the good link state. The sequence number of this packet
and the period for sending Detect are included in this packet.
4. Protocol operation
4.1. Network prefix Information Advertisement
4.1.1. Methodology
Because the NP-MNRP protocol is designed as an IGP inside the
autonomous system, it should route transit network traffic and local
network traffic. The network IP prefix is divided into two parts: the
IP prefix information of the transit network and the IP prefix
information of the network running the NP-MNRP protocol.
CNRT: Carrier Network Router
---- ---- ----
/ \ / \ / \
* UN1 * * UN2 * * UN3 *
\----/ \----/ \----/
| | |
******|*******************|*******************|******
* +-----+ +-----+ +-----+ *
* |CNRT1|-------------|CNRT2|-------------|CNRT3| *
* +-----+ +-----+ +-----+ *
* | | | *
* | | | *
* +-----+ +-----+ +-----+ *
* |CNRT5|-------------|CNRT6|-------------|CNRT4| *
* +-----+ CN +-----+ +-----+ *
******|***************************************|******
__|_ __|_
/----\ /----\
* UN5 * * UN4 *
\----/ \----/
Figure 1 Network Model
NDSC Expires January 28, 2011 [Page 8]
Internet-Draft The NPMNRP Routing Protocol July 2010
In view of the NP-MNRP protocol, the network is divided into the
user network and the carrier network, as shown in Figure 1. The user
network is abbreviated as UN and the carrier network is abbreviated
as CN. Each node in CN will run NP-MNRP protocol to establish a
multiple next-hops routing information base. Otherwise, it is not
necessary for nodes in UN to run the NP-MNRP protocol.
The nodes in UN will finish local communication and transmit the
network traffic whose destinations are not in the user network itself
to the Carrier network. The network prefix of UN is named as Network
Layer reachable information. The carrier network mainly transfers
transit traffic for UN. The network prefix of CN is treated as
network topology information and will be advertised by potential
calculation process. The boundary nodes of CN are also named as
egress nodes. They advertise network layer reachable information to
neighbor nodes periodically and initiate the node potential
calculation procedure.
This advertisement method separates the information of the CN
topology from the network layer reachable information and advertises
them in different manners. The advertisement of topology information
is independent on network layer reachable information. From this way,
the flexibility of routing information distribution can be enhanced.
4.1.2. Network Layer Reachable Information Advertisement
Network layer reachable information that means the user network
prefix is advertised through NLRI-FAP, NLRI-SRP and NLRI-DAP packets.
The boundary nodes in CN are responsible for advertising user network
reachable information, as shown in Figure 2.
NDSC Expires January 28, 2011 [Page 9]
Internet-Draft The NPMNRP Routing Protocol July 2010
The boundary nodes in CN advertise network layer reachable
information to neighbor nodes periodically through NLRI-FAP. Once
receiving the NLRI-FAP, the nodes in CN extract network prefix
information from packets and add them to the network layer reachable
information database of their own.
................
. UN .
. Host1 Host2 .
. \ / .
. \ / .
. +-----+ .
. |UNRT1| .
. +-----+ . Host1 Host2 .Host1 Host2
.......|........ \ / \ /
****************|*****************\ /*********************\ /***
* +------+ +------+ * +-----+*
* +-----|CNBRT1|------------|CNBRT2|----------------|UNRT2|*
* | +------+ +------+ * +-----+*
* | | | | *
* | | | * | *
* | +-----+ +-----+ +-----+* | *
* | |CNRT6|-------------|CNRT3|-------|CNRT2|* | *
* | +-----+ +-----+ +-----+* | *
* | | | | * | *
* | | | | * | *
* +------+ +-----+ +-----+ +------+* | *
* |CNBRT4|---|CNRT5|-------------|CNRT4|------|CNBRT3|-------+ *
* +------+ +-----+ CN +-----+ +------+* *
******|******************************************/ \************
......|......... / \
+-----+ . Host1 Host2
|UNRT3| .
+-----+ .
/ \ .
/ \ .
Host1 Host2 .
................
NDSC Expires January 28, 2011 [Page 10]
Internet-Draft The NPMNRP Routing Protocol July 2010
Figure 2 Network layer reachable information advertisements
CNRT: Carrier Network Router;
CNBRT: Carrier Network Boundary Router
When the nodes in CN don't know user network prefix, these nodes
will act as inquirers and send NLRI-SRP to query other nodes and set
a query timer. When a node receives the NLRI-SRP, and the network
prefix information or attached router information is in its database,
it responds to the inquirer with an NLRI-DAP packet. Otherwise, it
sends the NLRI-SRP packet to its neighbors except for the enquirers.
This process will continue until the inquirer get an response from
other nodes or such query timer is timed out.
When bound to the egress node (relative information is absent in the
network layer reachable information database of the node), the node
sends NLRI-SRP flooding to the inquirer, called the enquirer.
4.2. Neighbor Node Discovery and Adjacency Establishment
When a new node joins in the network, other nodes discover it and
initialize their local routing tables as the following steps:
(1): Broadcast a Detect packet and a NLG-CTP packet. This node sets
the sequence number of Detect with 0.The Detect will be sent
periodically by defaulted period set in the protocol;
(2): When other nodes receive a Detect packet or a NLG-CTP packet,
they operate as follows:
(a) If the received Detect comes from an unknown node and its
sequence number equal to 0, the receivers know that a new node is
NDSC Expires January 28, 2011 [Page 11]
Internet-Draft The NPMNRP Routing Protocol July 2010
added to the network, and add it to their neighbor node database and
record Detect's sequence number;
(b) Reply to the unknown node with a REPLY packet; Send an NLG-IAP
packet which contains all egress nodes information in the database.
(c) According to the computation rules of node potential, they
compute layer value and potential value relative to the egress node.
(3): When receiving a REPLY packet and an NLG-IAP packet, the new
node operates as follows:
(a) Adds the neighbor node to routing information database;
(b) According to NLG-IAP, it calculates its own layer value in the
following formula:
L(i,i)=0;
L(i,j)=min[L(k,j)]+1, for each k blongs to Ki, j blongs to N, and
k,j are not equal to i.
L(i,j) is the layer value of node i reference to egress node j, N is
the set of network nodes, Ki is the set of neighbor nodes about node
i.
(c) Based on the layer values of its neighbors, bandwidth and its
own layer value, the new node computes node potential value of its
neighbors and its own.
NDSC Expires January 28, 2011 [Page 12]
Internet-Draft The NPMNRP Routing Protocol July 2010
4.3. Calculation of Node Potential Value
NP-MNRP defines node potential value as a mixed metric of hop count
and bandwidth. Hop count metric records the number of routers which a
packet passes through and each router is recorded as one hop. The
actual link bandwidth is allocated\configured by router in the
network initialization.
4.3.1. Protocol Packets Sending and Processing
4.3.1.1. Network Layer Graph Routing Request Packet processing
Network Layer Graph Routing Request Packet (NLG-RRP) has two
different types. One type is the all-nodes layer information request
packet which will request the receiver to send layer information of
all nodes. The other is the partial-nodes layer information request
packet which will request the receiver to send layer information of
the specified nodes.
The NLG-RRP will be used in the following conditions:
Condition 1: When a new node is attached to the network, all nodes
layer information request packet will be sent to its neighbors.
Condition 2: When the node wants to get some certain network prefix
information from its neighbors, partial nodes layer information
request packet will be sent.
Once receiving a NLG-RRP packet, each node should process as the
following steps:
NDSC Expires January 28, 2011 [Page 13]
Internet-Draft The NPMNRP Routing Protocol July 2010
(a): Firstly, the type of the packet will be verified whether or not
it is a correct NLG-RRP packet.
(b): When NLG-RRP is the all-nodes layer information request packet,
it sends its own layer information relative to the other nodes to the
request node.
(c): When NLG-RRP is the partial-nodes layer information request
packet, it sends its own layer information relative to the
destination node in the packet to the query node.
4.3.1.2. Network Layer Graph Information Advertisement Packet sending
The Network Layer Graph Information Advertisement Packet (NLG-IAP)
is broadcasted to its neighbors in the following cases:
Case 1: All-nodes' layer values are specified after the network
layer graph has been divided.
Case 2: When layer information of any node is changed, which may be
caused by the change of layer values of some routers when they
receive NLG-FAP or some new nodes are added to the network.
Case 3: An NLG-RRP packet is received and the receiver's layer
information reference to certain egress node is changed.
The processing rules of NLG-IAP are described in Section 3.5.
4.3.2. Calculation of the Node Potential Value
In NP-MNRP, the node potential value is a mixed metric, including
hop count and actual link bandwidth. Each egress node activates its
NDSC Expires January 28, 2011 [Page 14]
Internet-Draft The NPMNRP Routing Protocol July 2010
neighbors to build Network Layer graph by sending an NLG-CTP packet
to neighbors. It is calculated as follows:
(1) In the algorithm initialization, egress node assigns its layer
value as 0, and then sends a NLG-CTP packet to its neighbors, which
contains the actual link bandwidth.
(2) The neighbor node that received a NLG-CTP packet from the 0-
layer node sets itself as 1-layer, and generates a NLG-CTP packet and
sends to its neighbors., and so on.
(3) Repeat the above step (2) until the nodes whose layer value are
smaller than f-layer which have been determined.
(4) After the f-layer has been constructed completely, each node in
F-layer knows that it is in F-layer and knows which neighbors are in
F-1 layer. The nodes in F-1layer know which ones are in F layer,
which ones are in F-1 layer, and which ones are in f-2 layer.
(5) Suppose F-layer has been constructed, and the algorithm has not
been terminated, then the construction of the f +1 layer will begin.
The nodes in F-layer will send an NLG-CTP packet to its neighbors.
(6) When all the nodes are traveled, the algorithm ends.
All nodes in the network not only are aware of their own layer value
but also know their neighbors' layer value and the actual bandwidth
between themselves.
Next each node calculates the potential value as follows:
NDSC Expires January 28, 2011 [Page 15]
Internet-Draft The NPMNRP Routing Protocol July 2010
(1) 0-layer nodes directly define their own potential value as 0;
(2) Each node of the other layers chooses the largest potential
value node among its neighbors in the same and lower layers as its
reference node for defining potential value, then defines its
potential values as the reference node's potential value plus one and
its neighbors' potential value are equal to their layer value.
(3) When all the neighbors' potential value are defined, the node
will choose the neighbor nodes whose potential values are less than
its potential values as its feasible next-hops.
4.4. network Event Sensing
The NP-MNRP protocol can sense events such as new nodes are added to
the network or a neighbor node is down. The node senses these events
by sending out the Detect packet and receiving the REPLY packet
periodically.
4.4.1. Message Sending and Processing
Each NP-MNRP node broadcasts periodically a Detect packet. When a
Detect packet is received, the receiver sends a REPLY packet to the
sender. The detailed steps are as follows:
Step1: Each node broadcasts periodically a Detect packet. Detect
carries a sequence number and the detect message's periodic interval.
Step2: When a Detect packet is received, its sequence number is
compared with the expected sequence number for this neighbor. Then
the receiver sends a REPLY packet to the sender and evaluates inverse
link quality according to the sequence number.
NDSC Expires January 28, 2011 [Page 16]
Internet-Draft The NPMNRP Routing Protocol July 2010
Step3: When a Reply packet is received, its sequence number should
be equal to the sequence number of the Detect packet's sequence
number. Then the receiver evaluates link quality according to the
sequence number and the use of sent/receive message time.
4.4.2. Forward Direction link Sensing
A(Ti) represents the mean interval from node i sending out the
Detect packet to receiving the REPLY packet. FA (Ti) represents the
latest mean interval time. Node i adjusts the period of sending out a
Detect packet according to the following rules:
(1) If FA(Ti) < A(Ti), it means that the link quality is stable. At
this period, when three continuous Detect packets are all low, then
increase the Detect interval;
(2) If FA(Ti) > A(Ti), it means that the link quality is unsteady or
becomes bad. At this period, when three continuous Detect packets are
all high, then reduce the Detect interval;
(3) When a Detect packet is sent out but a REPLY packet is not
received in the 2*FA(Ti) time, the node will reduce the period into
half, then continue sending out the next sequence number Detect
packet. If a REPLY packet is still not received, the node insulates
that node and thinks of link breakdown or link congestion.
(4) The isolate node will not be used as the next-hop to forwarding
packets. The processing node should continue sending the Detect
packet and adjust strategies according to the following conditions:
NDSC Expires January 28, 2011 [Page 17]
Internet-Draft The NPMNRP Routing Protocol July 2010
(a) If three continuous REPLY packets are received, then the node
deletes the isolate node and uses nodes which reply to the REPLY
packet as the next-hops to forwarding packets.
(b) If no packet is received after 6 Detect intervals, so that the
node is thought to be breakdown, no longer send the Detect packet
again , and wait for 6 Detect intervals, if still not receiving a
Detect packet from other node, so judge the node breakdown and delete
all its neighbors' routing information;
(c) If the node can receive a Detect packet or a REPLY packet which
is sent out from the isolation node, and then it will continue
sending a Detect packet until the isolation node recovery or judge
node breakdown.
4.4.3. Inverse Link Sensing
Each node broadcasts periodically Detect packets. Every Detect
packet carries a sequence number and the interval.
When a Detect packet is received, the sequence number is compared
with the next expected sequence number for this neighbor, if the
sequence number of the received Detect packet is higher than the
expected, then one or more Detect packets have been missed. If the
sequence number is lower, then this neighbor decreases the Detect
interval, and part of the history must be undone.
From the history of received Detect packets, a node computes an
estimate of the inverse link quality.
NDSC Expires January 28, 2011 [Page 18]
Internet-Draft The NPMNRP Routing Protocol July 2010
4.5. Update of the Node Potential
4.5.1. Update of Network Layer Value
As the set of next-hop is empty, the node will trigger update about
the layer value through the following operations:
(1) Firstly, the node will check whether the set of its neighbors on
the same layer is empty. If not, it will change itself layer value
and generate NLG-IAP packets that are sent to its neighbors.
(2) If the set is empty, then the node will perform the following
steps:
(a) Flooding NLG-RUP packets, whose layer value will be revised to
the old layer value minus 2, however, if old layer value minus 2 is
less than 0, the value is set to 0. What's more, all information
about this egress node will be deleted.
(b) The node which received an NLG-RUP packet will check if it has
ever received this message. If having received such a message, the
packet will be ignored, otherwise the layer value in this packet will
be viewed. If the value is greater than the value of its own, the
node will discard the packet, otherwise, go on flooding NLG-RUP
packets to its neighbors and delete all information about this egress
node.
(c) If the layer value in the packet is equal to its own, the node
will stop flooding to send NLG-RUP and send an NLG-CTP packet about
the egress node.
NDSC Expires January 28, 2011 [Page 19]
Internet-Draft The NPMNRP Routing Protocol July 2010
(d) The Neighbor node which received an NLG-CTP packet will
calculate its new layer value. If new value is the same with the
original, the node stops sending NLG-CTP packets and the layer value
update algorithm will terminate.
4.5.2. Update of Node Potential Value
The potential value of the nodes will be updated in the following
conditions.
(1) Potential value update caused by NLG-IAP packet.
The main contents of an NLG-IAP packet are layer information of a
node relative to the egress node in the network. The node adjusts its
potential value according to the NLG-IAP packets received from its
neighbors. Specific updates come as follows:
(a) NLG-IAP packet generation
When the node finds its layer information relative to one certain
egress node changed, the new layer information relative to all egress
nodes will be written into its generated NLG-IAP packet.
(b) NLG-IAP to send
The node will broadcast its generated NLG-IAP packets to its
neighbors, and then wait for confirmation from its neighbors. When
the node receives REPLY pockets with sequence number 0XFFFF from its
neighbors, this update ends.
(c) When the node received the NLG-IAP packet, it performs the
following steps:
NDSC Expires January 28, 2011 [Page 20]
Internet-Draft The NPMNRP Routing Protocol July 2010
Firstly, this node will verify the NLG-IAP packet. If the packet is
validated, it sends a REPLY packet with sequence number 0XFFFF to the
source node of the NLG-IAP packet.
Secondly, this node will extract layer information from the NLG-IAP
packet supposing a received routing entries includes RUIi =<
RouterID, EgressnodeID, Layi> and the corresponding routing entry
stored in the database is RUI'I =< RouterID, EgressnodeID, Lay'i>,
when one of the following three cases are met, the node updates its
own routing table according to the information received.
Case 1: If the EgressnodeID included in the received routing table
entry dose not exist in its own routing table, the router will add it
and send an NLG-RRP packet about the destination address of the
network to its neighbors. After receiving NLG-IAP packets, it will
calculate its layer value relative to this egress node according to
the formula in 3.2, get the neighbors' layer value, and then define
the neighbors' potential value relative to this destination node.
Case 2: If the EgressnodeID included in the received routing table
entry exists in its own routing table and Lay'i < Layi, the router
will adjust its neighbors' layer value and potential value. If the
neighbor's potential value is greater than its own and the neighbor
node is just in its own next-hop collection, the router will remove
the node from next-hop collection, if not, do nothing.
Case 3: If Layi < Lay'i, then the router will adjust this neighbor
node's layer value and potential value. If the neighbor's potential
value is less than its own and the neighbor node is not in its own
NDSC Expires January 28, 2011 [Page 21]
Internet-Draft The NPMNRP Routing Protocol July 2010
next-hop collection, then the router will add it into the next-hop
collection, if it exists, nothing needs to be done. However, the
router will not adjust its layer value and potential value in this
case.
(2) Potential value update caused by the change of layer value
When the node's layer value reference to a particular destination
node changes, firstly it will modify layer value of itself and its
neighbors. Then the new potential value will be calculated according
to the update strategy.
5. Routing Information Base
Each routing node maintains the Routing Information Base to forward
IP packets. The NP-MNRP protocol can calculate multi-nexthop routing
information in the network. The route computation process descried in
Section 3 will record all the feasible next-hops for every
destination. The multi-nexthop routing entry is composed of three
fields.
The first field is named as the destination IP address field.
The second field is named as the destination IP address mask filed.
The first and second fields are 32-bit numbers which define network
destination information of each routing entry. And the route
information base is indexed by the first and second field.
The third field is named as the feasible nexthop filed, whose form
is a couple of next-hop IP address value and node potential
difference value. The next-hop IP address is the IP address of the
NDSC Expires January 28, 2011 [Page 22]
Internet-Draft The NPMNRP Routing Protocol July 2010
neighbor node which will act as a feasible next-hop for this routing
node to forward IP packets to the network destination. Compared with
the single next-hop routing information, the number of the feasible
next-hop filed in a multi-nexthop routing entry may be a value bigger
than one.
The routing node will gain more agility in the IP packet forwarding
procedure. It can choose , forward all the packets to one best next-
hop and use other feasible next-hop entries as backup entries.
Through this way, the network availability will be improved in the
scene where network failure or mal-function occurs frequently. It can
also choose and forward all the IP packets to all feasible next-hop
entries. In this manner, this routing node can assign each next-hop a
traffic ratio for each destination. All the packets will be forwarded
to all available next-hops . This will make the network resource
utilization more even and avoid network congestion in some ways.
6. NP-MNRP Packets Format
The NP-MNRP protocol runs directly over the IP network layer. Before
any packet format is described, the details of the NP-MNRP
encapsulation are explained.
6.1. Encapsulation of NP-MNRP Packets
NP-MNRP runs directly over the Internet Protocol's network layer.
Therefore, NP-MNRP packets are encapsulated solely by IP and local
data-link headers. NP-MNRP does not define a way to fragment its
protocol packets, and depends on IP fragmentation when transmitting
packets larger than the network MTU.
NDSC Expires January 28, 2011 [Page 23]
Internet-Draft The NPMNRP Routing Protocol July 2010
NP-MNRP uses IP protocol number 99. Routing protocol packets are
sent with the IP precedence set to the inter-network Control. NP-MNRP
protocol packets should be given precedence over regular IP data
traffic, in both sending and receiving.
6.2. Packet Format
There are nine distinct NP-MNRP packet types. All NP-MNRP packet
types begin with a standard 20 byte header. This header is described
first. Each packet type is then described in a succeeding section. In
these sections each packet's division into fields is displayed, and
then the field definitions are enumerated.
6.2.1. The NP-MNRP Packet Header
Every NP-MNRP packet starts with a standard 20 byte header. This
header contains all the information necessary to determine whether
the packet should be accepted for further processing. This
determination is described in Section 5.2 of the specification.
0 1 2 3
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Byte 1 | Byte 2 | Byte 3 | Byte 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version # | Type | Packet length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Check Sum | Authentication Type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 0-3) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 4-7) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
NDSC Expires January 28, 2011 [Page 24]
Internet-Draft The NPMNRP Routing Protocol July 2010
Version:The NP-MNRP version number. This specification documents
version 1 of the protocol.
Type:The length of the NP-MNRP protocol packet in bytes. This length
includes the standard NP-MNRP header.
---------------------
| Type| Description |
|-----|---------------
| 1 | NLRI-FAP |
| 2 | NLRI-SRP |
| 3 | NLRI-DAP |
| 4 | NLG-CTP |
| 5 | NLG-IAP |
| 6 | NLG-RRP |
| 7 | NLG-RUP |
| 8 | Detect |
| 9 | REPLY |
---------------------
Router ID:The Router ID of the packet's source.It is the minimum or
maximum IP address or any IP address in all the interfaces; however,
it WOULD be always fixed once the agreement starts.
Check Sum:The standard IP checksum of the entire content of the
packet starts with the NP-MNRP packet header but excluding the 64-bit
authentication field. If the length of the package is less than 16-
bit, 0 byte WOULD be added before the checksum byte.
Authentication Type:Identify the authentication procedure used for
the packet. Authentication is discussed in the specification.
Authentication Info:64-bit authentication information field depends
on the chosen authentication type, to carry identification
information such as identity authentication.
NDSC Expires January 28, 2011 [Page 25]
Internet-Draft The NPMNRP Routing Protocol July 2010
6.2.2. Various types of Protocol Packets
NP-MNRP protocol packets have a total of 9 species.
6.2.2.1. Network Layer Reachable Information Flood Advertisement Packet,
NLRI-FAP
The NLRI-FAP packet is the NP-MNRP packet type 1.The packet is sent
by an egress node in the carrier network and is used to advertise the
user network prefix information which is bound to this node. The node
that received this packet WOULD consider this egress node reachable
and the user network which is bound to this node reachable too.
0 1 2 3
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Byte 1 | Byte 2 | Byte 3 | Byte 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version # | 1 | Packet length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Check Sum | Authentication Type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 0-3) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 4-7) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IP address of the network 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Subnet mask of the network 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ...... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IP address of the network n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Subnet mask of the network n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
IP address of the network:The IP address of a user network is bound
to this egress node.
NDSC Expires January 28, 2011 [Page 26]
Internet-Draft The NPMNRP Routing Protocol July 2010
Subnet Mask of the Network:The subnet mask of user network is
denoted in the above field.
6.2.2.2. Network Layer Reachable Information Specific Request Packet,
NLRI-SRP
The NLRI-SRP packet is the NP-MNRP packet type 2.This packet is used
by the node in the carrier network to request the network layer
reachable information. When the node doses not know which egress node
one network prefix is bound to, the NLRI-SRP packet is sent.
If the IP address and the subnet mask of the network 1 is all 0, all
the network prefixes WOULD be requested, and usually this request is
sent by a node which just joins into the carrier network.
NDSC Expires January 28, 2011 [Page 27]
Internet-Draft The NPMNRP Routing Protocol July 2010
0 1 2 3 4
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Byte 1 | Byte 2 | Byte 3 | Byte 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version # | 2 | Packet length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Check Sum | Authentication Type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 0-3) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 4-7) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IP address of the network 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Subnet mask of the network 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ...... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IP address of the network n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Subnet mask of the network n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
IP address of the network:The IP address of a user network whose
binding relationship this node want to request.
Subnet Mask of the Network
The Subnet mask of a user network denoted is in the above field,
whose binding relationship this node wants to request
6.2.2.3. Network Layer Reachable Information Direction Answer Packet,
NLRI-DAP
The NLRI-DAP packet is the NP-MNRP packet type 3. The node that
receives the NLRI-SRP packet WOULD check its information database to
seek for the corresponding binding relationship. If the binding
relationship exists in its own information database, it WOULD send an
NDSC Expires January 28, 2011 [Page 28]
Internet-Draft The NPMNRP Routing Protocol July 2010
NLRI-DAP packet to the requesting node, if not, it WOULD send NLRI-
SRP packets to its all neighbor nodes except for the requesting node.
If a node which sends the NLRI-SRP packets at the same time receives
more than one packets about the same IP prefix binding relationship,
and these packets are conflictive, it WOULD go on sending NLRI-SRP
packets, until the egress node which the network prefix is bound to
answers the request.
NDSC Expires January 28, 2011 [Page 29]
Internet-Draft The NPMNRP Routing Protocol July 2010
0 1 2 3 4
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Byte 1 | Byte 2 | Byte 3 | Byte 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version # | 3 | Packet length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Check Sum | Authentication Type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 0-3) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 4-7) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IP address of the network |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Subnet mask of the network 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Egress node ID 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ...... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IP address of the network n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Subnet mask of the network n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Egress node ID n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
IP Address of the Network:The IP address of a user network whose
binding relationship this node wants to know in the receiving NLRI-
SRP packet.
Subnet Mask of the Network:The subnet mask of a user network denoted
in the above field, whose binding relationship this node wants to
know in the receiving NLRI-SRP packet.
Egress Node ID:This field denotes the user network, whose IP address
and subnet mask emerge in the front two fields, is bound to this
egress node.
NDSC Expires January 28, 2011 [Page 30]
Internet-Draft The NPMNRP Routing Protocol July 2010
6.2.2.4. Network Layer Graph Construction Trigger Packet, NLG-CTP
The NLG-CTP packet is the NP-MNRP packet type 4.When one egress node
joins into the carrier network, it WOULD send this packet to urge the
other nodes to build network layer graph relative to itself.
0 1 2 3 4
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Byte 1 | Byte 2 | Byte 3 | Byte 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version # | 4 | Packet length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Check Sum | Authentication Type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 0-3) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 4-7) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Egress node ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Layer value |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Egress Node ID:The node that received this packet calculates its
layer value relative to this egress node.
Layer Value:This is the sender's layer value relative to the node
denoted in the above field
6.2.2.5. Network Layer Graph Information Advertisement Packet, NLG-IAP
The NLG-IAP packet is the NP-MNRP packet type 5. This packet is sent
to all neighbor nodes using multicast address to advertise its layer
value relative to the node whose ID is included in this packet, this
packet is usually to start the neighbor nodes to adjust their
potential dynamically.
NDSC Expires January 28, 2011 [Page 31]
Internet-Draft The NPMNRP Routing Protocol July 2010
0 1 2 3 4
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Byte 1 | Byte 2 | Byte 3 | Byte 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version | 5 | packet length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Egress node ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Check Sum | Authentication Type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 0-3) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 4-7) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Egress node ID 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Layer value 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ....... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Egress node ID n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Layer value n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Egress Node ID:The receiver need adjust its layer value relative to
this node
Layer Value:This is the layer value of the sender relative to the
egress node denoted in the above field.
6.2.2.6. Network Layer Graph Routing Request Packet, NLG-RRP
The NLG-RRP packet is the NP-MNRP packet type 6. This packet is used
by one node to request the neighbor nodes to send their own layer
information relative to the appointed egress node to it. This packet
has two types: one is for all nodes and the other is for some nodes.
NDSC Expires January 28, 2011 [Page 32]
Internet-Draft The NPMNRP Routing Protocol July 2010
If the egress node ID in the packet is empty, the packet is the NLG-
RRP packet for all nodes, if not; the packet is the NLG-RRP packet
for the appointed nodes included in this packet.
0 1 2 3 4
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Byte 1 | Byte 2 | Byte 3 | Byte 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version | 6 | packet length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Check Sum | Authentication Type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 0-3) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 4-7) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Egress node ID1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Egress node ID2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ....... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Egress Node ID:This field denotes the receiver needed to respond its
layer value relative to this egress node.
6.2.2.7. Network Layer Graph Request Update Packet, NLG-RUP
The NLG-RUP packet is the NP-MNRP packet type 7. When a node finds
its next hops and its neighbors on the same layer are all unreachable,
it sends this packet to neighbors to update its layer value.
NDSC Expires January 28, 2011 [Page 33]
Internet-Draft The NPMNRP Routing Protocol July 2010
0 1 2 3 4
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Byte 1 | Byte 2 | Byte 3 | Byte 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version | 7 | packet length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Check Sum | Authentication Type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 0-3) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 4-7) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Egress node ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Layer value |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Egress Node ID:This field denotes the receiver needs to update its
value relative to this node
Layer Value:The layer value in NLG-RUP packet is the layer value
relative to high egress node minus 2.
6.2.2.8. Link State Detect Packet, Detect
The Detect packet is the NP-MNRP packet type 8. This packet is
periodically sent to neighbor nodes to evaluate the link quality.
NDSC Expires January 28, 2011 [Page 34]
Internet-Draft The NPMNRP Routing Protocol July 2010
0 1 2 3 4
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Byte 1 | Byte 2 | Byte 3 | Byte 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version | 8 | packet length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Check Sum | Authentication Type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 0-3) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 4-7) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Sequence number | Period |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Sequence Number:The sequence number in this packet is the sequence
number of the Detect message, and it is an increasing positive
integer.
Period:The period in this packet is the interval time between this
and the last one.
6.2.2.9. REPLY Message Packet, REPLY
The REPLY packet is the NP-MNRP packet type 9. The node that
received a detect packet will send a reply packet to the sender,
which can evaluate the reverse link quality according to this packet.
The sequence number in this packet denotes it is the reply to the
Detect message that has the corresponding sequence number. If the
number is all-1, it means the packet is the confirmation message to
an NLG-IAP message.
NDSC Expires January 28, 2011 [Page 35]
Internet-Draft The NPMNRP Routing Protocol July 2010
0 1 2 3 4
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Byte 1 | Byte 2 | Byte 3 | Byte 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version | 9 | packet length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Check Sum | Authentication Type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 0-3) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication Info(8 array 4-7) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Serial number | Period |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Serial Number:The sequence number in this packet is the sequence
number of the REPLY, and it is an increasing positive integer.
Period:This field denotes that the node sending this packet will
send Detect messages at this period.
7. References
[1] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", BCP 14, RFC 2119, March 1997.
[2] Crocker, D. and Overell, P.(Editors), "Augmented BNF for Syntax
Specifications: ABNF", RFC 2234, Internet Mail Consortium and
Demon Internet Ltd., November 1997.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2234] Crocker, D. and Overell, P.(Editors), "Augmented BNF for
Syntax Specifications: ABNF", RFC 2234, Internet Mail
Consortium and Demon Internet Ltd., November 1997.
NDSC Expires January 28, 2011 [Page 36]
Internet-Draft The NPMNRP Routing Protocol July 2010
8. Acknowledgments
This research was sponsored by the National High-Tech Research and
Development Plan of China under grant numbers 2007AA01Z2a1 and
2008AA01Z214; the National Grand Fundamental Research Program of
China under grant number 2007CB30710; the National Key Technology R&D
Program of China under grant number 2008BAH37B02.
This document was prepared using 2-Word-v2.0.template.dot.
Authors' Addresses
Julong Lan
National Digital Switching System Engineering and Technological
Research Center
NDSC, No.7 , Jianxue Street,Jinshui District
Zhengzhou, 450002,
P.R.China
Phone: +86-371-8163-2988
Email: ndscljl@163.com
URI: http://www.ndsc.com.cn/
Jianhui Zhang
National Digital Switching System Engineering and Technological
Research Center
NDSC, No.7 , Jianxue Street,Jinshui District
Zhengzhou, 450002,
P.R.China
Phone: +86-371-8163-2988
Email: ndsc155@163.com
URI: http://www.ndsc.com.cn/
Bin Wang
National Digital Switching System Engineering and Technological
Research Center
NDSC, No.7 , Jianxue Street,Jinshui District
Zhengzhou, 450002,
P.R.China
Phone: +86-371-8163-2909
Email: wbin2006@gmail.com
URI: http://www.ndsc.com.cn/
Wenfen Liu
National Digital Switching System Engineering and Technological
Research Center
NDSC, No.7 , Jianxue Street,Jinshui District
Zhengzhou, 450002,
NDSC Expires January 28, 2011 [Page 37]
Internet-Draft The NPMNRP Routing Protocol July 2010
P.R.China
Phone: +86-371-8163-0340
Email: wenfenliu@sina.com
URI: http://www.ndsc.com.cn/
Xin Li
BEIJING UNIVERSITY OF POSTS AND TELECOMMUNICATIONS
No.10 Xi Tu Cheng Road Haidian District
Beijing,100876
P.R.China
Phone: +8613581614576
Email: cplalx@gmail.com
http://www.bupt.edu.cn/
NDSC Expires January 28, 2011 [Page 38]