Currently, programmer's guide for the RIB library is missing. This commit adds it.
Signed-off-by: Vladimir Medvedkin <vladimir.medved...@intel.com> --- doc/guides/prog_guide/img/rib_internals.svg | 148 +++++++++++++++++ doc/guides/prog_guide/img/rib_pic.svg | 152 +++++++++++++++++ doc/guides/prog_guide/index.rst | 1 + doc/guides/prog_guide/rib_lib.rst | 172 ++++++++++++++++++++ 4 files changed, 473 insertions(+) create mode 100644 doc/guides/prog_guide/img/rib_internals.svg create mode 100644 doc/guides/prog_guide/img/rib_pic.svg create mode 100644 doc/guides/prog_guide/rib_lib.rst diff --git a/doc/guides/prog_guide/img/rib_internals.svg b/doc/guides/prog_guide/img/rib_internals.svg new file mode 100644 index 0000000000..7e40046cba --- /dev/null +++ b/doc/guides/prog_guide/img/rib_internals.svg @@ -0,0 +1,148 @@ +<svg width="1740.327" height="670.034" viewBox="0 0 1305.249 502.526" xml:space="preserve" color-interpolation-filters="sRGB" version="1.1" id="svg997" xmlns:xlink="http://www.w3.org/1999/xlink"; xmlns="http://www.w3.org/2000/svg"; style="fill:none;fill-rule:evenodd;font-size:12px;overflow:visible;stroke-linecap:square;stroke-miterlimit:3"> + <style type="text/css" id="style740"> + .st1{fill:#ff0;fill-opacity:.15;stroke:#3c63ac;stroke-width:.75}.st2,.st3{fill:#fee599;stroke:#c7c8c8;stroke-width:.25}.st3{fill:#bfbfbf}.st4{marker-end:url(#mrkr4-12);stroke:#000;stroke-linecap:round;stroke-linejoin:round;stroke-width:1}.st10{stroke-width:.25}.st6{fill:#23d127}.st6,.st7,.st8,.st9{stroke:#c7c8c8;stroke-width:.25}.st7{fill:#00b0f0}.st8{fill:red}.st9{fill:#7030a0}.st10{fill:none;stroke:none}.st11{fill:#4672c4;font-family:Calibri;font-size:1.5em}.st12{font-size:1em} + </style> + <defs id="Markers"> + <marker id="mrkr4-12" refX="-7.04" orient="auto" markerUnits="strokeWidth" overflow="visible" style="fill:#000;fill-opacity:1;stroke:#000;stroke-opacity:1;stroke-width:.28409090909091"> + <use xlink:href="#lend4" transform="scale(-3.52)" id="use745" x="0" y="0" width="100%" height="100%"/> + </marker> + <g id="lend4"> + <path d="M2 1 0 0l2-1v2" style="stroke:none" id="path742"/> + </g> + </defs> + <g id="g995" transform="translate(-217.077 -27.932)"> + <g id="shape1025-1" transform="translate(504.643 -65.197)"> + <path d="M583.63 595.28 290.41 324.57 0 595.28Z" class="st1" id="path753"/> + </g> + <g id="shape2-3" transform="translate(992.354 -368.504)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path758"/> + </g> + <g id="shape3-5" transform="translate(1182.05 -467.717)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path763"/> + </g> + <g id="shape8-7" transform="translate(1190.35 -476.016)"> + <path d="m0 595.28-143.05 56.53" class="st4" id="path768"/> + </g> + <g id="shape22-13" transform="translate(1094.1 -297.638)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path773"/> + </g> + <g id="shape31-15" transform="translate(1366.3 -368.504)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path778"/> + </g> + <g id="shape33-17" transform="translate(1465.51 -297.638)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path783"/> + </g> + <g id="shape36-19" transform="translate(1230.44 -476.016)"> + <path d="m0 595.28 137.65 56.44" class="st4" id="path788"/> + </g> + <g id="shape1000-24" transform="translate(881.803 -297.638)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path793"/> + </g> + <g id="shape1002-26" transform="translate(994.885 -226.772)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st6" id="path798"/> + </g> + <g id="shape1006-28" transform="translate(1257.06 -297.638)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path803"/> + </g> + <g id="shape1007-30" transform="translate(1153.7 -226.772)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path808"/> + </g> + <g id="shape1008-32" transform="translate(1366.3 -226.772)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path813"/> + </g> + <g id="shape1012-34" transform="translate(768.113 -226.772)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path818"/> + </g> + <g id="shape1013-36" transform="translate(668.9 -155.906)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st7" id="path823"/> + </g> + <g id="shape1018-38" transform="translate(868.818 -155.906)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st8" id="path828"/> + </g> + <g id="shape1019-40" transform="translate(769.125 -85.04)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st9" id="path833"/> + </g> + <g id="shape1026-42" transform="translate(238.475 -510.236)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path838"/> + </g> + <g id="shape1027-44" transform="translate(238.475 -439.37)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path843"/> + </g> + <g id="shape1028-46" transform="translate(238.475 -368.504)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st6" id="path848"/> + </g> + <g id="shape1029-48" transform="translate(238.475 -297.638)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st7" id="path853"/> + </g> + <g id="shape1030-50" transform="translate(238.475 -226.772)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st8" id="path858"/> + </g> + <g id="shape1031-52" transform="translate(238.475 -155.906)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st9" id="path863"/> + </g> + <g id="shape1032-54" transform="translate(300.688 -518.013)"> + <path class="st10" id="rect870" d="M0 554.136h164.559v41.14H0z"/> + <text x="13.67" y="580.11" class="st11" id="text872">Intermediate node</text> + </g> + <g id="shape1033-57" transform="translate(300.688 -447.147)"> + <path class="st10" id="rect879" d="M0 554.136h164.559v41.14H0z"/> + <text x="15.71" y="569.31" class="st11" id="text883">Node containing a <tspan x="62.17" dy="1.2em" class="st12" id="tspan881">route</tspan></text> + </g> + <g id="shape1034-61" transform="translate(300.688 -376.281)"> + <path class="st10" id="rect890" d="M0 554.136h164.559v41.14H0z"/> + <text x="35.5" y="580.11" class="st11" id="text892">10.15.0.0/23</text> + </g> + <g id="shape1035-64" transform="translate(300.688 -305.414)"> + <path class="st10" id="rect899" d="M0 554.136h164.559v41.14H0z"/> + <text x="40.06" y="580.11" class="st11" id="text901">10.0.0.0/29</text> + </g> + <g id="shape1036-67" transform="translate(300.688 -234.548)"> + <path class="st10" id="rect908" d="M0 554.136h164.559v41.14H0z"/> + <text x="30.93" y="580.11" class="st11" id="text910">10.0.0.128/25</text> + </g> + <g id="shape1037-70" transform="translate(300.688 -163.682)"> + <path class="st10" id="rect917" d="M0 554.136h164.559v41.14H0z"/> + <text x="30.93" y="580.11" class="st11" id="text919">10.0.0.160/27</text> + </g> + <g id="shape1038-73" transform="translate(218.008 -100.593)"> + <path d="m85.56 595.28-42.78-41.14L0 595.28Z" class="st1" id="path924"/> + </g> + <g id="shape1039-75" transform="translate(308.827 -92.816)"> + <path class="st10" id="rect931" d="M0 554.136h164.559v41.14H0z"/> + <text x="8.82" y="558.51" class="st11" id="text937">Routes falling under <tspan x="5.62" dy="1.2em" class="st12" id="tspan933">common 10.0.0.0/24 </tspan><tspan x="61.23" dy="1.2em" class="st12" id="tspan935">prefix</tspan></text> + </g> + <g id="shape1040-80" transform="translate(1374.6 -376.804)"> + <path d="m0 595.28-62.71 27.91" class="st4" id="path942"/> + </g> + <g id="shape1041-85" transform="translate(1414.69 -376.804)"> + <path d="m0 595.28 52.87 27.52" class="st4" id="path947"/> + </g> + <g id="shape1042-90" transform="translate(1305.46 -305.938)"> + <path d="m0 595.28 62.71 27.91" class="st4" id="path952"/> + </g> + <g id="shape1043-95" transform="translate(1265.36 -305.938)"> + <path d="m0 595.28-56.94 27.69" class="st4" id="path957"/> + </g> + <g id="shape1044-100" transform="translate(1040.75 -376.804)"> + <path d="m0 595.28 55.35 27.62" class="st4" id="path962"/> + </g> + <g id="shape1045-105" transform="translate(1000.65 -376.804)"> + <path d="m0 595.28-64.01 27.95" class="st4" id="path967"/> + </g> + <g id="shape1046-110" transform="translate(930.196 -305.938)"> + <path d="m0 595.28 66.5 28.03" class="st4" id="path972"/> + </g> + <g id="shape1047-115" transform="translate(890.102 -305.938)"> + <path d="m0 595.28-67.1 28.05" class="st4" id="path977"/> + </g> + <g id="shape1048-120" transform="translate(816.506 -235.071)"> + <path d="m0 595.28 54.33 27.58" class="st4" id="path982"/> + </g> + <g id="shape1049-125" transform="translate(776.413 -235.071)"> + <path d="m0 595.28-52.87 27.52" class="st4" id="path987"/> + </g> + <g id="shape1050-130" transform="translate(877.117 -164.205)"> + <path d="m0 595.28-53.34 27.54" class="st4" id="path992"/> + </g> + </g> +</svg> diff --git a/doc/guides/prog_guide/img/rib_pic.svg b/doc/guides/prog_guide/img/rib_pic.svg new file mode 100644 index 0000000000..8a8b176502 --- /dev/null +++ b/doc/guides/prog_guide/img/rib_pic.svg @@ -0,0 +1,152 @@ +<svg width="1280.324" height="563.481" viewBox="0 0 960.246 422.611" xml:space="preserve" color-interpolation-filters="sRGB" version="1.1" id="svg249" xmlns:xlink="http://www.w3.org/1999/xlink"; xmlns="http://www.w3.org/2000/svg"; style="fill:none;fill-rule:evenodd;font-size:12px;overflow:visible;stroke-linecap:square;stroke-miterlimit:3"> + <style type="text/css" id="style9"> + .st1{fill:#eb94e0}.st1,.st2,.st3{stroke:#c7c8c8;stroke-width:.25}.st2{fill:#bfbfbf}.st3{fill:#00b0f0}.st4{marker-end:url(#mrkr4-16);stroke:#000;stroke-linecap:round;stroke-linejoin:round;stroke-width:1}.st7{fill:#00b0f0;fill-opacity:1;stroke:#00b0f0;stroke-opacity:1;stroke-width:.28409090909091}.st8,.st9{marker-end:url(#mrkr4-113);stroke:#00b0f0;stroke-linecap:round;stroke-linejoin:round;stroke-width:1}.st9{marker-end:url(#mrkr4-129);stroke:#eb94e0}.st11{fill:none;stroke:none;stroke-width:.25}.st12{fill:#4672c4;font-family:Calibri;font-size:1.5em} + </style> + <defs id="Markers"> + <marker id="mrkr4-16" refX="-7.04" orient="auto" markerUnits="strokeWidth" overflow="visible" style="fill:#000;fill-opacity:1;stroke:#000;stroke-opacity:1;stroke-width:.28409090909091"> + <use xlink:href="#lend4" transform="scale(-3.52)" id="use14" x="0" y="0" width="100%" height="100%"/> + </marker> + <marker id="mrkr4-107" class="st7" refX="-7.04" orient="auto" markerUnits="strokeWidth" overflow="visible"> + <use xlink:href="#lend4" transform="scale(-3.52)" id="use17" x="0" y="0" width="100%" height="100%"/> + </marker> + <marker id="mrkr4-113" class="st7" refX="-6.68" orient="auto" markerUnits="strokeWidth" overflow="visible"> + <use xlink:href="#lend4" transform="scale(-3.52)" id="use20" x="0" y="0" width="100%" height="100%"/> + </marker> + <marker id="mrkr4-129" refX="-6.68" orient="auto" markerUnits="strokeWidth" overflow="visible" style="fill:#eb94e0;fill-opacity:1;stroke:#eb94e0;stroke-opacity:1;stroke-width:.28409090909091"> + <use xlink:href="#lend4" transform="scale(-3.52)" id="use23" x="0" y="0" width="100%" height="100%"/> + </marker> + <g id="lend4"> + <path d="M2 1 0 0l2-1v2" style="stroke:none" id="path11"/> + </g> + </defs> + <g id="g247" transform="translate(-624.44 -59.113)"> + <g id="shape1000-1" transform="translate(1428.66 -396.85)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st1" id="path31"/> + </g> + <g id="shape1001-3" transform="translate(1527.87 -325.984)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st1" id="path36"/> + </g> + <g id="shape1002-5" transform="translate(1319.43 -325.984)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path41"/> + </g> + <g id="shape1003-7" transform="translate(1216.06 -255.118)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st1" id="path46"/> + </g> + <g id="shape1004-9" transform="translate(1428.66 -255.118)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path51"/> + </g> + <g id="shape1005-11" transform="translate(1436.96 -405.15)"> + <path d="m0 595.28-62.71 27.91" class="st4" id="path56"/> + </g> + <g id="shape1006-17" transform="translate(1477.05 -405.15)"> + <path d="m0 595.28 52.87 27.52" class="st4" id="path61"/> + </g> + <g id="shape1007-22" transform="translate(1367.82 -334.284)"> + <path d="m0 595.28 62.71 27.91" class="st4" id="path66"/> + </g> + <g id="shape1008-27" transform="translate(1327.73 -334.284)"> + <path d="m0 595.28-56.94 27.69" class="st4" id="path71"/> + </g> + <g id="shape1009-32" transform="translate(1230.24 -479.055)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path76"/> + </g> + <g id="shape1010-34" transform="translate(1031.81 -396.85)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st1" id="path81"/> + </g> + <g id="shape1011-36" transform="translate(1131.02 -325.984)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path86"/> + </g> + <g id="shape1014-38" transform="translate(1080.2 -405.15)"> + <path d="m0 595.28 52.87 27.52" class="st4" id="path91"/> + </g> + <g id="shape1015-43" transform="translate(1238.54 -487.355)"> + <path d="m0 595.28-151.53 40.3" class="st4" id="path96"/> + </g> + <g id="shape1016-48" transform="translate(1278.63 -487.355)"> + <path d="m0 595.28 151.53 40.3" class="st4" id="path101"/> + </g> + <g id="shape1017-53" transform="translate(922.779 -325.984)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path106"/> + </g> + <g id="shape1019-55" transform="translate(813.543 -255.118)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st1" id="path111"/> + </g> + <g id="shape1020-57" transform="translate(931.079 -334.284)"> + <path d="m0 595.28-62.71 27.91" class="st4" id="path116"/> + </g> + <g id="shape1022-62" transform="translate(1022.65 -255.118)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st2" id="path121"/> + </g> + <g id="shape1023-64" transform="translate(1121.86 -184.252)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path126"/> + </g> + <g id="shape1026-66" transform="translate(1071.04 -263.418)"> + <path d="m0 595.28 52.87 27.52" class="st4" id="path131"/> + </g> + <g id="shape1027-71" transform="translate(1040.11 -405.15)"> + <path d="m0 595.28-62.51 27.9" class="st4" id="path136"/> + </g> + <g id="shape1028-76" transform="translate(971.172 -334.284)"> + <path d="m0 595.28 53.52 27.55" class="st4" id="path141"/> + </g> + <g id="shape1029-81" transform="translate(914.275 -184.252)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st1" id="path146"/> + </g> + <g id="shape1030-83" transform="translate(1013.49 -113.386)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path151"/> + </g> + <g id="shape1031-85" transform="translate(805.039 -113.386)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path156"/> + </g> + <g id="shape1032-87" transform="translate(922.575 -192.552)"> + <path d="m0 595.28-62.71 27.91" class="st4" id="path161"/> + </g> + <g id="shape1033-92" transform="translate(962.668 -192.552)"> + <path d="m0 595.28 52.87 27.52" class="st4" id="path166"/> + </g> + <g id="shape1034-97" transform="translate(1030.95 -263.418)"> + <path d="m0 595.28-61.86 27.88" class="st4" id="path171"/> + </g> + <g id="shape1035-102" transform="translate(861.732 -134.646)"> + <path d="M0 588.19h144.72" id="path176" style="marker-end:url(#mrkr4-107);stroke:#00b0f0;stroke-linecap:round;stroke-linejoin:round;stroke-width:1"/> + </g> + <g id="shape1036-108" transform="translate(1061.88 -161.779)"> + <path d="M0 595.28c17.07 0 45.07 0 57.76-6.9 7.54-4.1 9.68-10.64 10.28-16.84l.01-.36" class="st8" id="path181"/> + </g> + <g id="shape1037-114" transform="translate(1147.7 -240.945)"> + <path d="M2.51 595.28c0-21.26 4.17-21.26 6.44-27.88 2.51-7.31 2.7-22.68 2.72-50.12v-.36" class="st8" id="path186"/> + </g> + <g id="shape1038-119" transform="translate(1187.72 -354.331)"> + <path d="M0 595.28c104.41 0 106.27 68.37 233.91 70.8h.36" class="st8" id="path191"/> + </g> + <g id="shape1039-124" transform="translate(870.236 -283.465)"> + <path d="M0 595.28c19.54 0 21.12 42.91 45.36 49.87l.36.05" class="st9" id="path196"/> + </g> + <g id="shape1040-130" transform="translate(942.622 -240.945)"> + <path d="M0 595.28c0-63.78 30.02-63.78 44.53-77.43 13.58-12.76 13.58-37.48 31.95-48.45 12.86-7.69 34.73-8.64 39.92-23.08l.06-.36" class="st9" id="path201"/> + </g> + <g id="shape1041-135" transform="translate(1088.5 -425.197)"> + <path d="M0 595.28c38.98 0 99.97 0 129.15 23.13 24.61 19.52 26.58 55.51 26.74 83.21v.36" class="st9" id="path206"/> + </g> + <g id="shape1042-140" transform="translate(1272.76 -283.465)"> + <path d="M0 595.28c15.13 0 20.44 0 23.89-5.12 6.37-9.46 6.37-36.42 6.37-61.42 0-27.19 0-52.06 16.86-64.04 15.08-10.73 43.68-11.14 101.75-11.16h.36" class="st9" id="path211"/> + </g> + <g id="shape1043-145" transform="translate(1485.35 -425.197)"> + <path d="M0 595.28c17.72 0 46.05 0 59.28 9.06 9.19 6.29 11.09 16.97 11.48 26.42l.01.36" class="st9" id="path216"/> + </g> + <g id="shape1044-150" transform="translate(624.567 -479.055)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st3" id="path221"/> + </g> + <g id="shape1045-152" transform="translate(624.567 -379.843)"> + <path d="M0 566.93a28.346 28.346 0 1 1 56.69 0 28.346 28.346 0 0 1-56.69 0z" class="st1" id="path226"/> + </g> + <g id="shape1046-154" transform="translate(695.501 -493.654)"> + <path class="st11" id="rect233" d="M0 567.78h90.709v27.496H0z"/> + <text x="4.67" y="586.93" class="st12" id="text235">Next hop A</text> + </g> + <g id="shape1047-157" transform="translate(697.019 -394.441)"> + <path class="st11" id="rect242" d="M0 567.78h90.709v27.496H0z"/> + <text x="4.99" y="586.93" class="st12" id="text244">Next hop B</text> + </g> + </g> +</svg> diff --git a/doc/guides/prog_guide/index.rst b/doc/guides/prog_guide/index.rst index 89af28dacb..0a53ec71c8 100644 --- a/doc/guides/prog_guide/index.rst +++ b/doc/guides/prog_guide/index.rst @@ -38,6 +38,7 @@ Programmer's Guide member_lib lpm_lib lpm6_lib + rib_lib flow_classify_lib packet_distrib_lib reorder_lib diff --git a/doc/guides/prog_guide/rib_lib.rst b/doc/guides/prog_guide/rib_lib.rst new file mode 100644 index 0000000000..e8bb35a2b6 --- /dev/null +++ b/doc/guides/prog_guide/rib_lib.rst @@ -0,0 +1,172 @@ +.. SPDX-License-Identifier: BSD-3-Clause + Copyright(c) 2021 Intel Corporation. + +RIB Library +=========== + +The Routing Information Base (RIB) library provides a data store for routing information. +This library is intended for use in control or management plane applications. +There are more suitable libraries for use in data plane applications such as +:ref:`LPM <LPM_Library>` or FIB. + + +Implementation details +---------------------- + +RIB implements a key-value store for routing information. + +Routing information is represented by a prefix (key) and a next hop ID (value). +The prefix type depends on the address family. IPv4 addresses are represented by +``uint32_t`` values. IPv6 addresses are represented as ``uint8_t[16]`` values. +Next hop IDs are represented by ``uint64_t`` values. + +.. note:: + + The API and implementation are very similar for IPv4's ``rib`` library and IPv6's ``rib6`` + library, therefore only the ``rib`` library will be discussed here. + Everything within this document except for the size of the prefixes is applicable to the + ``rib6`` library. + +Internally RIB is represented as a binary tree as shown in :numref:`figure_rib_internals`: + +.. _figure_rib_internals: + +.. figure:: img/rib_internals.* + + RIB internals overview + +The binary tree consists of two types of nodes: + +* Actual Routes. + +* Intermediate Nodes which are used internally to preserve the binary tree structure. + + +RIB API Overview +---------------- + +RIB has two configuration parameters: + +* The maximum number of nodes. + +* The size of the extension block within each node. This space is used to store + additional user defined data. + +The main methods within the ``rib`` library are: + +* ``rte_rib_insert()``: Add new routes. + +* ``rte_rib_remove()``: Delete an existing route. + +* ``rte_rib_lookup()``: Lookup an IP in the structure using longest match. + +* ``rte_rib_lookup_exact()``: Lookup an IP in the structure using exact match. + +* ``rte_rib_lookup_parent()``: Find a parent prefix within the structure. + +* ``rte_rib_get_nxt()``: Traverse a subtree within the structure. + +Given a RIB structure with the routes depicted in :numref:`figure_rib_internals`, +here are several usage examples: + +* The best route for ``10.0.0.1`` can be found by calling: + +.. code-block:: c + + struct rte_rib_node *route = rte_rib_lookup(rib, RTE_IPV4(10,0,0,1)); + +This returns an ``rte_rib_node`` pointing to the ``10.0.0.0/29`` prefix. + +* To find an exact match route: + +.. code-block:: c + + struct rte_rib_node *route = rte_rib_lookup_exact(rib, RTE_IPV4(10,0,0,128), 25); + +This returns an ``rte_rib_node`` pointing to the ``10.0.0.128/25`` prefix. + +and + +.. code-block:: c + + struct rte_rib_node *route = rte_rib_lookup_exact(rib, RTE_IPV4(10,0,0,0), 24); + +This returns ``NULL`` as no exact match can be found. + +* To retrieve a group of routes under the common prefix ``10.0.0.0/24`` + (yellow triangle in :numref:`figure_rib_internals`): + +.. code-block:: c + + struct rte_rib_node *route = NULL; + do { + route = rte_rib_get_nxt(rib, RTE_IPV4(10,0,0,0), 24, route, RTE_RIB_GET_NXT_ALL); + } while (route != NULL) + +This returns 3 ``rte_rib_node`` nodes pointing to ``10.0.0.0/29``, ``10.0.0.160/27`` +and ``10.0.0.128/25``. + +Extensions usage example +------------------------ + +Extensions can be used for a wide range of tasks. +By default, an ``rte_rib_node`` node contains only crucial information such as the prefix and +next hop ID, but it doesn't contain protocol specific information such as +metrics, administrative distance and other routing protocol information. +These examples are application specific data and the user can decide what to keep +and how it is stored within the extension memory region in each ``rte_rib_node``. + +It is possible to implement a prefix independent convergence using the RIB extension feature. +If the routing daemon can provide a feasible next hop ID along with a best (active) next hop ID, +it is possible to react to a neighbour failing relatively fast. +Consider a RIB with a number of routes with different next hops (A and B) as +shown in :numref:`figure_rib_pic`. Every route can have a feasible next hop +provided by the routing daemon. + +.. _figure_rib_pic: + +.. figure:: img/rib_pic.* + + RIB prefix independent convergence + +In case of a next hop failure, we need to replace an active failed next hop with a +feasible next hop for every corresponding route without waiting for the routing daemon +recalculation process to complete. +To achieve this we can link all existing routes with the same active next hop in a linked list, +saving the feasible next hop ID and a pointer inside the extension space of each ``rte_rib_node``. + +.. code-block:: c + + struct my_route_ext { + struct rte_rib_node *next; + uint64_t feasible_nh; + }; + + struct rte_rib_conf conf; + conf.ext_sz = sizeof(struct my_route_ext); + rib = rte_rib_create("test", 0, &conf); + ... + /* routing daemon task */ + struct rte_rib_node *route = rte_rib_insert(rib, RTE_IPV4(192,0,2,0), 24); + rte_rib_set_nh(route, active_nh_from_rd); + struct my_route_ext *ext = rte_rib_get_ext(route); + ext->feasible_nh = feasible_nh_from_rd; + list_insert(nh_table[active_nh_from_rd].list_head, route); + ... + /* dataplane monitoring thread */ + /* nexthop id fail_nh fails */ + route = NULL; + do { + route = get_next(nh_table[fail_nh].list_head, route); + uint32_t ip; + uint8_t depth; + rte_rib_get_ip(route, &ip); + rte_rib_get_depth(route, &depth); + ext = rte_rib_get_ext(route); + uint64_t new_nh = ext->feasible_nh; + /* do update to the dataplane, for example to the fib */ + rte_fib_add(fib, ip, depth, new_nh); + /* update nexthop if necessary */ + rte_rib_set_nh(route, new_nh); + } while (route != NULL); + -- 2.25.1
