Thursday, October 16, 2014

MPLS LSP Multipath Trace

Any Operator dealing with MPLS network will predominantly use MPLS LSP Ping tool to validate the LSP health. As defined in MPLS LSP Ping, the packet will be carrying IP destination as loopback address and helps detect any failure in LSP by avoiding the packet get IP routed. So whenever there is end-to-end connectivity issue, it is obvious to see Operators using LSP Ping as the first step to eliminate any LSP failure. 

But incase of multipath scenarios, the LSP Ping may not always help identify any LSP failure. As it might be noted, any LSR on receiving a labeled packet and if there are multiple egress interface, it uses some keys from the packet and input to hashing algorithm to decide the egress interface. Depending on vendor, HW etc, any of the below options may be considered for hashing:

  • Incoming label stack alone. 
  • Incoming label stack and IP header details (If the payload is IP).
  • Incoming label stack, IP header, and transport header details.


Normally, Cisco routers consider a combination of label stack and IP header if the stack is of size less than or equal to 3 (with IP as the payload).



In the above topology, there are 3 ECMP paths from R1 to R5 as below,

PATH1 à R1-R2-R3-R4-R5
PATH2 à R1-R2-R6-R4-R5
PATH3 à R1-R2-R6-R7-R5

Now assume there is some issue between R6 and R7 (like broken LDP or label misprogramming etc) causing the traffic from R1 to R5 via PATH3 fails. If LSP Ping from R1 takes PATH1 or PATH2, Operators may end up assuming that the path between R1 and R5 is fine.

LSP Ping allows setting the IP destination address as any one from 127.0.0.0/8 range. While one simple option is to manually try sending multiple ping packets with different destination address, there is no guarantee that all possible ECMP paths will be validated.  We simply need a way that queries and validate all possible paths between ingress and egress. LSP Multipath tree trace helps us with validating all ECMP paths that leverages the “Multipath Information Encoding” defined in Section 3.3.1 of RFC4379.

How does it work?

Initiator will send MPLS Echo Request to each hop by setting the TTL in the top label in incremental manner (starting from 1). The Echo Request will carry Multipath Information TLV that carries a range of IP address (within 127.0.0.0/8 range) or entropy label range. Currently Cisco device supports the IP destination option and so our example will be detailed with IP address range.

Each transit LSR on receiving the Request will reply with all ECMP outgoing interface and associate a range of IP address (or entropy label) from the Request for each interface.

A detailed explanation with topology is defined below:


For simplicity, we explained the example with address range as 127.0.0.0-127.0.0.200.

Initiator will send the Echo Request with below details:
Ø  IP destination as 127.0.0.0
Ø  Multipath Information TLV carrying the address range as 127.0.0.0 to 127.0.0.200.
Ø  The TTL of the top label will be set to 1.  

R2 on receiving the same will reply back with Multipath Information for each egress interface. In our example, it will reply as below:


Ø  If IP destination is within 127.0.0.0 to 127.0.0.100, packet will be sent to R3.
Ø  If IP destination is within 127.0.0.101 to 127.0.0.200, packet will be sent to R6.

R1 realizes that there are 2 possible ECMP paths and so need to send 2 Echo Request with TTL set to 2.  From various testing, it was observed that Initiator always finishes off with 1 path before going to next. (But this might be a local implementation).



R1 will now send the Echo Request with below details:
Ø  IP destination as 127.0.0.0
Ø  Multipath Information TLV carrying the address range as 127.0.0.0 to 127.0.0.100.
Ø  The TTL of the top label will be set to 2. 

R2 will forward the packet to R3 (as the destination address is 127.0.0.0). R3 on receiving the same will reply back with same Multipath Information, as there is only one egress interface.

The same hold true till it reaches R5.


Once PATH1 is done (by receiving reply from Egress), Initiator will now query PATH2.  This is performed by sending the Echo Request with below details:

Ø IP destination as 127.0.0.101
Ø Multipath Information TLV carrying the address range as 127.0.0.101 to 127.0.0.200
Ø The TTL of the top label set to 2.

R2 will forward the packet to R6 (as the destination address is 127.0.0.101). R6 on receiving the same will reply back with Multipath Information as below:

Ø  If IP destination is within 127.0.0.101 to 127.0.0.150, packet will be sent to R4.
Ø  If IP destination is within 127.0.0.151 to 127.0.0.200, packet will be sent to R7.

R1 realizes that there is one more ECMP path making the total possible paths as 3. R1 continue querying PATH2 by sending the next Echo Request with below details:

Ø  IP destination as 127.0.0.101
Ø  Multipath Information TLV carrying the address range as 127.0.0.101 to 127.0.0.150
Ø  The TTL of top label set to 3.


R2 will forward to R6 (as the destination is 127.0.0.101) and R6 will forward to R4 (as the destination is 127.0.0.101). R4 doesn’t have any ECMP path and so will reply back with same Multipath Information. The next packet will reach egress R5.

Since PATH2 is done, R1 will continue the query for PATH3. This is performed by sending the Echo Request with below details:

Ø  IP destination as 127.0.0.151
Ø  Multipath Information TLV carrying the address range as 127.0.0.151 to 127.0.0.200
Ø  The TTL of top label set to 3.

R2 will forward to R6 which in turn will forward to R7 (due to the destination address). R7 will reply back with same Multipath Information TLV. The next packet reaches the egress R5.

Now R1 will have the below details:


By using the destination address within 127.0.0.0 to 127.0.0.100, the packet will be influenced over PATH1 while using the address from other range will influence the packet over the respective path.

Now Initiator will send 3 Echo Request with TTL set to 255 and select address from each range so that all paths will be validated end-to-end.

The command to be used for ECMP trace is “traceroute mpls multipath ipv4

R1#traceroute mpls multipath ipv4 10.1.5.5 255.255.255.255
Starting LSP Multipath Traceroute for 10.1.5.5/32

Codes: '!' - success, 'Q' - request not sent, '.' - timeout,
  'L' - labeled output interface, 'B' - unlabeled output interface,
  'D' - DS Map mismatch, 'F' - no FEC mapping, 'f' - FEC mismatch,
  'M' - malformed request, 'm' - unsupported tlvs, 'N' - no label entry,
  'P' - no rx intf label prot, 'p' - premature termination of LSP,
  'R' - transit router, 'I' - unknown upstream index,
  'l' - Label switched with FEC change, 'd' - see DDMAP for return code,
  'X' - unknown return code, 'x' - return code 0

Type escape sequence to abort.
LLL!
Path 0 found,
 output interface Et0/0.12 nexthop 10.1.12.2
 source 10.1.12.1 destination 127.0.0.4
LL!
Path 1 found,
 output interface Et0/0.12 nexthop 10.1.12.2
 source 10.1.12.1 destination 127.0.0.2
L!
Path 2 found,
 output interface Et0/0.12 nexthop 10.1.12.2
 source 10.1.12.1 destination 127.0.0.0

Paths (found/broken/unexplored) (3/0/0)
 Echo Request (sent/fail) (9/0)
 Echo Reply (received/timeout) (9/0)
 Total Time Elapsed 27 ms

It can be observed that the output shows that there are 3 paths and all paths are working fine. Similarly a verbose with the above output will list all the hops in eac path as below:

R1#

R1#traceroute mpls multipath ipv4 10.1.5.5 255.255.255.255 verbose
Starting LSP Multipath Traceroute for 10.1.5.5/32

Codes: '!' - success, 'Q' - request not sent, '.' - timeout,
  'L' - labeled output interface, 'B' - unlabeled output interface,
  'D' - DS Map mismatch, 'F' - no FEC mapping, 'f' - FEC mismatch,
  'M' - malformed request, 'm' - unsupported tlvs, 'N' - no label entry,
  'P' - no rx intf label prot, 'p' - premature termination of LSP,
  'R' - transit router, 'I' - unknown upstream index,
  'l' - Label switched with FEC change, 'd' - see DDMAP for return code,
  'X' - unknown return code, 'x' - return code 0

Type escape sequence to abort.
LLL!
Path 0 found,
 output interface Et0/0.12 nexthop 10.1.12.2
 source 10.1.12.1 destination 127.0.0.4
  0 10.1.12.1 10.1.12.2 MRU 1500 [Labels: 22 Exp: 0] multipaths 0
L 1 10.1.12.2 10.1.23.3 MRU 1500 [Labels: 23 Exp: 0] ret code 8 multipaths 2
L 2 10.1.23.3 10.1.34.4 MRU 1500 [Labels: 22 Exp: 0] ret code 8 multipaths 1
L 3 10.1.34.4 10.1.45.5 MRU 1500 [Labels: implicit-null Exp: 0] ret code 8 multipaths 1
! 4 10.1.45.5, ret code 3 multipaths 0
LL!
Path 1 found,
 output interface Et0/0.12 nexthop 10.1.12.2
 source 10.1.12.1 destination 127.0.0.2
  0 10.1.12.1 10.1.12.2 MRU 1500 [Labels: 22 Exp: 0] multipaths 0
L 1 10.1.12.2 10.1.26.6 MRU 1500 [Labels: 16 Exp: 0] ret code 8 multipaths 2
L 2 10.1.26.6 10.1.46.4 MRU 1500 [Labels: 22 Exp: 0] ret code 8 multipaths 2
L 3 10.1.46.4 10.1.45.5 MRU 1500 [Labels: implicit-null Exp: 0] ret code 8 multipaths 1
! 4 10.1.45.5, ret code 3 multipaths 0
L!
Path 2 found,
 output interface Et0/0.12 nexthop 10.1.12.2
 source 10.1.12.1 destination 127.0.0.0
  0 10.1.12.1 10.1.12.2 MRU 1500 [Labels: 22 Exp: 0] multipaths 0
L 1 10.1.12.2 10.1.26.6 MRU 1500 [Labels: 16 Exp: 0] ret code 8 multipaths 2
L 2 10.1.26.6 10.1.67.7 MRU 1500 [Labels: 17 Exp: 0] ret code 8 multipaths 2
L 3 10.1.67.7 10.1.57.5 MRU 1500 [Labels: implicit-null Exp: 0] ret code 8 multipaths 1
! 4 10.1.57.5, ret code 3 multipaths 0

Paths (found/broken/unexplored) (3/0/0)
 Echo Request (sent/fail) (9/0)
 Echo Reply (received/timeout) (9/0)
 Total Time Elapsed 29 ms

R1#