IGP Extensions for Intra-Domain SAV

2.1. SAV Table and its Usage

Every node (i.e., IGP control plane on the node) in a Autonomous System (AS) builds and maintains its own Source Address Validation (SAV) Table based on its Link-State Database (LSDB). The format of a SAV table is shown in Figure 1.¶

    +==========+============+     +===========+================+
    |Source    |Incoming    |     |Destination|Outgoing        |
    |Prefix    |Interface   |     |Prefix     |Interface       |
    +==========+============+     +===========+================+
    |S-prefix-1|Interface-a |     |D-prefix-1 |Out-interface-a |
    +----------+------------+     +-----------+----------------+
==> |S-prefix-2|Interface-b | ==> |D-prefix-2 |Out-interface-b | ==>
 ^  +----------+------------+  ^  +-----------+----------------+  ^
 |     ...                     |      ...                         |
 |  +----------+------------+  |  +-----------+----------------+  |
 |  |S-prefix-n|Interface-x |  |  |D-prefix-n |Out-interface-x |  |
 |  +----------+------------+  |  +-----------+----------------+  |
 |   Format of SAV Table       |             FIB                  |
 |                             |                                  |
Packet in                  forward Packet                  Packet out
               if source address and receiving interface
               of Packet in SAV Table

When there is a shortest path from source prefix S-prefix-i to a destination through node N and interface Interface-j of node N, the SAV table of node N has a row containing S-prefix-i as Source Prefix and Interface-j as Incoming Interface. For example, the first row in the SAV table of node N contains S-prefix-1 as Source Address and Interface-a as Incoming Interface. This row indicates that there is a shortest path from S-prefix-1 to a destination through node N and Interface-a of node N.¶

The SAV table is sent to the data plane and used to validate the source address of a packet. When receiving a packet from an interface, the node validates the packet using its SAV table.¶

If the source address of the packet and the receiving/incoming interface are in the SAV table (i.e., there is one row in the SAV table containing the source address and the receiving/incoming interface), the packet is forwarded according to the FIB and destination address of the packet as shown in the figure; otherwise (i.e., there is no row in the SAV table containing the source address and the receiving/incoming interface), the packet is blocked or dropped.¶

2.2. Intra-Area SAV

This section introduces a method for a node to build its SAV table in a special case where an AS has only one area or SAV is for only one area.¶

When every routing/forwarding path in an AS is symmetric (i.e., every path has the same cost in both directions), every node in the AS builds and maintains its SAV table using its RIB/FIB. The node can determine whether every path is symmetric by checking its LSDB. If every link in its LSDB is symmetric (i.e., has the same metric or cost in both directions), then every path is symmetric; otherwise (i.e., there is an asymmetric link, its metric/cost in one direction is different from the one in the other/reverse direction), there are some asymmetric paths.¶

The node builds its SAV table using the RIB/FIB by including a row in its SAV table for each prefix with a next hop interface in its RIB/FIB. The row contains the prefix and the interface in the Source Prefix and Incoming Interface columns respectively.¶

When there is a routing/forwarding path which is not symmetric, every node X builds its SAV table in the following steps:¶

1. Builds reverse shortest path tree (RSPT). Node X computes/builds a shortest path tree from node X to the other nodes using the link metric or cost of each link in the reverse direction.¶

2. Builds reverse routing table (RRT) using RSPT. When node X finds a shortest path from node X to node Y with a next hop interface in its RSPT, node X adds an entry for each prefix attached to Y into its RRT. The entry has the prefix as the destination and the next hop interface as the next hop.¶

3. Builds SAV table using RRT. Node X includes a row in its SAV table for each prefix with a next hop interface in its RRT. The row contains the prefix and the interface in the Source Prefix and Incoming Interface columns respectively.¶

There are a few options below for the scope of the prefixes to be validated.¶

Option 1:

The prefixes attached to every node.¶

Option 2:

The prefixes attached to each ASBR and ABR.¶

Option 3:

The prefixes indicated/configured on any node.¶

The method above builds the SAV table for option 1.¶

For option 2, we consider only ASBR and ABR Y in step 2. Thus the RRT contains only the prefixes attached to ASBRs and ABRs. So does the SAV table.¶

For option 3, we consider only the prefixes attached to node Y and indicated/configured by node Y in step 2. Thus the RRT contains only these prefixes. So does the SAV table.¶

2.3. Inter-Area SAV

This section introduces a method for a node to build its SAV table in a general case where an AS has multiple areas and SAV is for all the areas. The method is based on the one described in Section 2.2.¶

For any area A, every node X in A builds its SAV table using the following steps:¶

1. Gets area shortest path tree (ASPT). The ASPT is a tree from node X as root to all the other nodes in area A. If every link in area A is symmetric, the ASPT is the SPT built by node X for its RIB, which is reused; otherwise (i.e., there is asymmetric link in area A), the ASPT is a RSPT from node X as root to all the other nodes in area A. Node X computes/builds the RSPT as described in Section 2.2.¶

2. Extends ASPT. For each leaf node L of ASPT, node X attaches node L of ASPT every prefix of node L if the cost from the prefix to L is minimal. If every link in area A is symmetric and every path between any ABR and a summary prefix/address from the ABR is symmetric, the extended ASPT is the SPT with the prefixes of each node in area A built by node X for its RIB, which is reused.¶

3. Builds reverse routing table (RRT) using extended ASPT. When node X finds a shortest path from node X to node Y with a next hop interface in its extended ASPT, node X adds an entry for each prefix attached to Y into its RRT. The entry has the prefix as the destination and the next hop interface as the next hop.¶

4. Builds SAV table using RRT. Node X includes a row in its SAV table for each prefix with a next hop interface in its RRT. The row contains the prefix and the interface in the Source Prefix and Incoming Interface columns respectively.¶

The method above builds the SAV table for option 1.¶

For option 2, we consider only ASBR and ABR Y in step 3. Thus the RRT contains only the prefixes attached to ASBRs and ABRs. So does the SAV table.¶

For option 3, we consider only the prefixes attached to node Y and indicated/configured by node Y in step 3. Thus the RRT contains only these prefixes. So does the SAV table.¶