Skip to content. | Skip to navigation

Personal tools

Navigation

You are here: Home / Projects / FIB Aggregation / ORTC Update Handling

ORTC Update Handling

ORTC Update Hanlding

Announcement

1. Existing Node

    1.1 Leaf node

 

        1.1.1 announced nexthop is the as old original_nexthop

 

           1.1.1.1 change node type to REAL_NODE

        1.2.1  announced nexthop is different from old origial_nexthop

 

            Get node's nearest IN_FIB ancestor

           1.2.1.1 change node's selected_nexthop,original nexthop,merged_nexthop to new announced nexthop

           1.2.1.2 get nearest IN_FIB ancestor.

           1.2.1.3 update subtree of the node by using almost the same algorithms as aggregation part. The difference is when one node

                   is added into FIB, the new one will try to aggregate it with its sibling node.It will use the nearest IN_FIB ancestor to decide whether one node will be

IN_FIB or NON_FIB.

           1.2.1.4 aggregate current node with its sibling nodes if they're adjcent and have the same selected_nexthop

    1.2 Internal Node
          

Get node's nearest IN_FIB ancestor.

        1.2.1 Announced nexthop is the as old original_nexthop

 

             1.2.1.1 Node is FAKE_NODE

                  1.2.1.1.1 change node to REAL_NODE

                  1.2.1.1.2 Update Fake node in the sub tree of this node.When doing this, FAKE_NODE and TMP_NODE's original nexthop,merged_nexthops will be updated and the algorithm will stop at REAL_NODE with updating its merged_nexthops to its original nexthop.

                   1.2.1.1.3 Update current node's merged_nexthops

                   1.2.1.1.4 update subtree of the node.

                   1.2.1.1.5 aggregte current node with its sibling nodes if feasible

             1.2.1.2 Node is TMP_NODE

                    1.2.1.2.1 Change node type to REAL_NODE

             1.2.1.3 Node is REAL_NODE

                     do nothing

         1.2.2 Announced nexthop is different from the old original_nexthop

 

              Get node's nearest IN_FIB ancestor.

              1.2.2.1 Node is FAKE_NODE

                    1.2.2.1.1 Change node to REAL_NODE

                    1.2.2.1.2 Change node's original nexhop to new one

                    1.2.2.1.3 Update FAKE_NODE and TMP_NODE in the subtree of this node.

                    1.2.2.1.4 Update Current node's merged_nexthops

                    1.2.2.1.5 Update subtree of the node

                    1.2.2.1.6 aggregate current node with its sibling nodes if feasible 

              1.2.2.2 Node is TMP_NDOE

                     1.2.2.2.1 Change node to REAL_NODE

                     1.2.2.2.2 Change node's original nexhop to new one

                     1.2.2.2.3 Update FAKE_NODE and TMP_NODE in the subtree of this node.

                     1.2.2.2.4 Update Current node's merged_nexthops

                     1.2.2.2.5 Update subtree of the node

                     1.2.2.2.6 aggregate current node with its sibling nodes if feasible 

              1.2.2.3 NODE is REAL_NODE

                     1.2.2.3.1 Change node's original nexhop to new one

                     1.2.2.3.2 Update FAKE_NODE and TMP_NODE in the subtree of this node.

                     1.2.2.3.3 Update Current node's merged_nexthops

                     1.2.2.3.4 Update subtree of the node

                     1.2.2.3.5 aggregate current node with its sibling nodes if feasible 

2. New Node

       2.1 add node to RIB first
       2.2 get node's nearest IN_FIB ancestor
       2.3 node is leaf node
          
2.3.1 set node's original_nexthop,selected_nexthop and merged_nexthop as the announced nexthop
          

2.3.2 update subtree of this node

           2.3.3 aggregate sibling node if feasible.
       2.4 node is internal node

 

           2.4.1 Update FAKE_NODE and TMP_NODE in the subtree of this node.

           2.4.2 set Current node's merged_nexthops

           2.4.3 Update subtree of the node

           2.4.4 aggregate current node with its sibling nodes if feasible              

Withdrawl

1. Leaf Node

 

    1.1 Get nearest IN_FIB ancestor

    1.2 IF node is IN_FIB, remove node from FIB

    1.3 Get nearest REAL_NODE

    1.4 set node's original_nexthop

          1.4.1 if nearest REAL_NODE exist and its prefix length larger than nearest IN_FIB ancestor prefix length, set node's original_nexthop as nearest REAL_NODE's.

          1.4.2 else set it as the nearest IN_FIB ancestor's.

   1.5 set node's selected_nexthop as -1

   1.6 set node's merged nexthop as the new original nexhop

   1.7 update subtree of this node

   1.8 aggregate current node with its sibling nodes if feasible recursively

   1.9 if node is NON_FIB,nearest IN_FIB ancestor is TMP_NODE and nearest IN_FIB ancestor original_nexthop is -1, recursively de-aggregate nearest IN_FIB

ancestor until nearest IN_FIB ancestor is REAL_NODE or is NULL. This step is for not inserting NULL node at root. Because if we do not de-aggregate those TMP_NODE,we'll

introduce extra routing space.

2. Internal Node

 

   2.1 Get nearest IN_FIB ancestor

   2.2 If node is IN_FIB, remove node from FIB

   2.3 Update FAKE_NODE, TMP_NODE in subtree of this node

   2.4 set node's original nexthop by using the same algorithms as Leaf node case

   2.5 Set nod's merged_nexthops

   2.6 update subtree of this node

   2.7 aggregate current node with its sibling nodes if feasible recursively

   2.8 deaggregate nearest TMP_NODE ancestor the same way as leaf node case.

  

 

Document Actions

« December 2017 »
December
MoTuWeThFrSaSu
123
45678910
11121314151617
18192021222324
25262728293031