Virtlab:Řídící server/Mapovací algoritmus

Z VirtlabWiki

< Virtlab:Řídící serverVerze z 12:11, 22. 10. 2007; zobrazit aktuální verzi
← Starší verze | Novější verze →
Přejít na: navigace, hledání

Obsah

[editovat]

Popis

Celkový postup mapovacího algoritmu:

  1. rychlé ověřění jednoduchých podmínek, jestli má mapování šanci na úspěch
    1. srovnání typů zařízení ve vybavení a virtuální topologii. Pokud je třeba mít v topologii typ zařízení, které nemáme mezi vybavením, tak není třeba s mapováním pokračovat - nepovede se.
    2. srovnání speciálních vlastností zařízení v topologii a vybavení. Pokud v topologii požaduji po zařízení určitou speciální vlastnost, která se v celém vybavení vůbec nevyskytuje - mapování se nepovede.
    3. srovnání speciálních vlastností jednotlivých linek a rozhraní zařízení ve vybavení. Pokud je v topologii po některé lince požadována speciální vlastnost, musí tuto vlastnost mít obě rozhraní, které tvoří konce této linky. Takže na každou vlastnost linky musí připadat alespoň dvě vlastnosti rozhraní.
  2. vlastní mapovací část realizovaná funkcí virtlabMapping::Map()
    1. ze seznamu zařízení (virtlabParserEquipment::getDevicesList()) a vrcholů linek virtuální topologie (virtlabParserTopology::getVertexesList()) se vytvoří dvojrozměrné pole (indexováno prvky ze získaných seznamů), jehož hodnoty jsou 1 pokud příslušný prvek nemůže být daným vrcholem. Nebo pole, určující na kterých linkách může být které rozhraní - zajištěno funkcí virtlabMapping::Availability($device, $vertex) (viz ukázka 1):
      • zjistění vhodnosti je komplexní problém, které se skládá z mnoha částí:
        1. porovnání typu zařízení s vrcholem (při neshodě vrácena hodnota virtlabValues::badType)
        2. porovnání platformy zařízení s požadovanou platformou (požadavek na platformu je považován za regulární výraz) (při neshodě vrácena hodnota virtlabValues::badPlatform)
        3. porovnání verze OS (požadavek na verzi OS je považována za regulární výraz) (při neshodě vrácena hodnota virtlabValues::badOS)
        4. porovnání speciálních vlastností zařízení (pokud nejsou splněny všechny požadavky, je vrácena hodnota virtlabValues::noDeviceFeature)
        5. zjištění dostatečného počtu rozhraní (pokud nemá zařízení dostatek rozhraní, aby mohla pokrýt potřeny topologie, je vrácena hodnota virtlabValues::notEnoughInterfaces - kontroluje se i typ rozhraní)
        6. zjištění způsobilostí rozhraní pro všechny požadované linky (počítáno přes všechny linky a rozhraní)
          1. porovnání speciálních vlastností rozhraní a linky
          2. porovnání technologie - u linek typu serial se porovnává rychlost rozhraní a požadovaná rychlost linky, u linek typu ethernet se porovná typ ethernetu (na lince, která má mít rychlost fast, může být rozhraní gigabit, ale ne legacy, ...)
          • pokud se pro nějakou linku nenajde ani jedno rozhraní, je vrácena hodnota virtlabValues::VertexDeviceMismatch
    2. na základě pole, které vzniklo (viz ukázka 1) se vyrobí pole další, které už ale není kompletní maticí vrcholy X zařízení, ale obsahuje jen takové body, u kterých bylo zjištěno, že vrchol a zařízení jsou pro sebe vhodné. Jeho hodnoty budou hodnocení zařízení vyrobené funkcí virtlabMapping::Evaluate($device) (viz ukázka 2)
      • jednotlivá vnitřní pole se seřadí vzestupně, podle hodnot zařízení
    3. takhle vyrobené pole slouží jako vstup funkce virtlabMapping::Mapping($map2, &$vysledek), které rekurzivně zjišťuje jestli je namapování možné - tuto informaci nám sdělí návratová hodnota (0 nebo 1). V případě kladného výsledku se v proměnné $vysledek bude nacházet výsledek mapovaní (viz ukázka 3)
      1. ve vstupním poli se zjistí jestli všechny vnitřní pole obsahují alespoň jeden prvek - pokud by neobsahovaly, znamená to, že pro nějaký vrchol není dosavadní mapovaní možné a vratí se hodnota 0
      2. pokud vstupní pole obsahuje už jen jednu položku vnějšího pole (jeden nenamapovaný vrchol), vezme se první prvek vnitřního pole (kvůli úvodnímu setřízení, to bude minimální prvek), příslušná dvojice vrchol - zařízení se uloží do $vysledek a vrátí se 1
      3. projdou se všechny vrcholy, jestli některý nemá už jen jedno možné zařízení na namapování
        1. příslušná dvojice vrchol - zařízení (je všemy výskyty zařízení) se odstraní ze vstupního pole (pomocí funkce MatrixClear) a na zbytek se spustí funkce virtlabMapping::Mapping (zde dochází ke zmíněné rekurzi), pričemž se zjišťuje návratová hodnota této funkce. Kladný výsledek (reprezentován 1), znamená že výběr dvojice vede k úspěšnému namapování a dvojice se tady uloží do $vysledek a je vrácena hodnota 1. Záporný výsledek znamená (reprezentován 0), že namapování zbytku se nepovedlo, a jelikož tato dvojice je jediná možná (pro daný vrchol neexistuje jiné možné zařízení) a je vrácena0
      4. pokud každý vrchol, ve vstupním poli, má ještě několik možných zařízení, začneme pole procházet do šířky (klasicky pomocí dvou vnořených cyklu for). Pro každou dvojici vrchol - zařízení se pokusíme spustit funkci virtlabMapping::Mapping se zbytkem vstupního pole, přičemz kontrolujeme náratovou hodnotu. Kladný výsledek (reprezentován 1), znamená že výběr dvojice vede k úspěšnému namapování a dvojice se tady uloží do $vysledek a je vrácena hodnota 1. Záporný výsledek znamená (reprezentován 0), že namapování zbytku se nepovedlo, a pokračuje dále v procházení dvojic
    4. po úsměšném namapování zařízení na vrcholy virtuální topologie, je potřeba namapovat jednotlivá rozhraní, zvolených prvků, na linky příslušného vrcholu. Jde o stejný problém, jako u prvního mapovaní zařízení na vrcholy a proto můžeme použít opětovně funkcí virtlabMapping::Mapping, jejiž algoritmus je popsát výše. Výstup této fáze je vidět v ukázka 4
      • čístě pro přehlednost funkce na konci generuje zjednodušený výpis (viz ukázka 5)
[editovat]

Ukázky

ukázka 1: 

Array
(
   [ra] => Array
       (
           [swa] => 0
           [r7] => Array
               (
                   [Kacena] => Array
                       (
                           [2] => s0/2/2
                       )
                   [Kocour] => Array
                       (
                           [4] => s0/2/4
                           [3] => s0/2/3
                           [2] => s0/2/2
                           [1] => s0/2/1
                           [0] => s0/2/0
                       )
               )
           [r5] => 0
           [r3] => 0
           [r1] => 0
       )
   [rb] => Array
       (
           [swa] => 0
           [r7] => Array
               (
                   [Kocour] => Array
                       (
                           [4] => s0/2/4
                           [3] => s0/2/3
                           [2] => s0/2/2
                           [1] => s0/2/1
                           [0] => s0/2/0
                       )
               )
           [r5] => Array
               (
                   [Kocour] => Array
                       (
                           [0] => s0/0
                       )
               )
           [r3] => Array
               (
                   [Kocour] => Array
                       (
                           [0] => s0
                       )
               )
           [r1] => Array
               (
                   [Kocour] => Array
                       (
                           [2] => s0/1/1
                           [1] => s0/2/1
                           [0] => s0/1/0
                       )
               )
       )
   [rc] => Array
       (
           [swa] => 0
           [r7] => 0
           [r5] => Array
               (
                   [Krokodyl] => Array
                       (
                           [1] => gi0
                       )
               )
           [r3] => Array
               (
                   [Krokodyl] => Array
                       (
                           [2] => fa0/1
                           [1] => fa0/0
                       )
               )
           [r1] => 0
       )
   [rd] => Array
       (
           [swa] => 0
           [r7] => 0
           [r5] => Array
               (
                   [Kacena] => Array
                       (
                           [0] => s0/0
                       )
                   [Krokodyl] => Array
                       (
                           [1] => gi0
                       )
               )
           [r3] => 0
           [r1] => 0
       )
)

ukázka 2: 

Array
(
   [ra] => Array
       (
           [r7] => 1005
       )
   [rb] => Array
       (
           [r3] => 180
           [r5] => 375
           [r1] => 605
           [r7] => 1005
       )
   [rc] => Array
       (
           [r3] => 180
           [r5] => 375
       )
   [rd] => Array
       (
           [r5] => 375
       )
)

ukázka 3: 

Array
(
   [0] => Array
       (
           [vertex] => rb
           [device] => r1
       )
   [1] => Array
       (
           [vertex] => rc
           [device] => r3
       )
   [2] => Array
       (
           [vertex] => rd
           [device] => r5
       )
   [3] => Array
       (
           [vertex] => ra
           [device] => r7
       )
)

ukázka 4: 

Array
(
   [rb] => Array
       (
           [device] => r1
           [links] => Array
               (
                   [Kocour] => s0/1/1
               )
       )
   [rc] => Array
       (
           [device] => r3
           [links] => Array
               (
                   [Krokodyl] => fa0/1
               )
       )
   [rd] => Array
       (
           [device] => r5
           [links] => Array
               (
                   [Krokodyl] => gi0
                   [Kacena] => s0/0
               )
       )
   [ra] => Array
       (
           [device] => r7
           [links] => Array
               (
                   [Kocour] => s0/2/4
                   [Kacena] => s0/2/2
               )
       )
)

ukázka 5: 

r7:s0/2/2 r5:s0/0 
r3:fa0/1  r5:gi0 
r7:s0/2/4 r1:s0/1/1
[editovat]

Zdrojové XML soubory

Soubory ukázané níže jsou jen příkladem, na kterém bylo mapování použito a výstupy z něj jsou zobrazeny v ukázkách.

[editovat]

Topologie 

<?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE virtual_topology SYSTEM "topology.dtd">

<virtual_topology>
    <edge technology="serial" name="Kocour">
        <vertex name="ra"/>
        <vertex name="rb"/>
    </edge>

    <edge technology="ethernet" ether_type="fast" name="Krokodyl">
        <vertex name="rc"/>
        <vertex name="rd"/>
    </edge>

    <edge technology="serial" name="Kacena">
        <vertex name="ra"/>
        <vertex name="rd"/>
        <min_bps>100000</min_bps>
        <edge_feature>SPAM</edge_feature>
    </edge>

    <vertex_detail type="router" name="ra">
        <os relation="eq">12</os>
        <vertex_feature>***</vertex_feature>
    </vertex_detail>

    <vertex_detail type="router" name="rb">
    </vertex_detail>

    <vertex_detail type="router" name="rc">
    </vertex_detail>

    <vertex_detail type="router" name="rd">
        <poss_platforms>
            <platform>17..</platform>
        </poss_platforms>
    </vertex_detail>

</virtual_topology>
[editovat]

Vybavení 

<?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE equipment SYSTEM "equipment.dtd">

<equipment>
    <device type="router" name="r1" serial_number="12345-54321" platform="7200">
        <os>12.8</os>
        <interfaces>
            <interface technology="serial" connect_group="1" name="s0/1/0">
                <max_bps>128000</max_bps>
                <int_feature>...</int_feature>
            </interface>
            <interface technology="serial" connect_group="1" name="s0/2/1">
                <max_bps>64000</max_bps>
                <int_feature>xxx</int_feature>
            </interface>
            <interface technology="serial" connect_group="1" name="s0/1/1">
                <max_bps>128000</max_bps>
                <int_feature>+++</int_feature>
            </interface>
            <interface technology="ethernet" ether_type="legacy" connect_group="2" name="e0">
                <int_feature>802.1q</int_feature>
            </interface>
        </interfaces>
        <special>
            <feature>mpls</feature>
        </special>
    </device>

    <device type="router" name="r3" serial_number="2345-5432" platform="1700">
        <os>12.6.321-ipsec:XXX</os>
        <interfaces>
            <interface technology="serial" connect_group="1" name="s0">
                <max_bps>64000</max_bps>
            </interface>
            <interface technology="ethernet" ether_type="fast" connect_group="3" name="fa0/0">
            </interface>
            <interface technology="ethernet" ether_type="fast" connect_group="3" name="fa0/1">
            </interface>
        </interfaces>
    </device>

    <device type="router" name="r5" serial_number="525444-69855" platform="1700">
        <os>12.0</os>
        <interfaces>
            <interface technology="serial" connect_group="1" name="s0/0">
                <max_bps>128000</max_bps>
                <int_feature>SPAM</int_feature>
            </interface>
            <interface technology="ethernet" ether_type="gigabit" connect_group="3" name="gi0">
            </interface>
        </interfaces>
        <special>
            <feature>mpls</feature>
        </special>
    </device>

    <device type="router" name="r7" serial_number="5244-55" platform="7200">
        <os>12.5.12-65.1</os>
        <interfaces>
            <interface technology="serial" connect_group="1" name="s0/2/0">
                <max_bps>128000</max_bps>
            </interface>
            <interface technology="serial" connect_group="1" name="s0/2/1">
                <max_bps>128000</max_bps>
            </interface>
            <interface technology="serial" connect_group="1" name="s0/2/2">
                <max_bps>128000</max_bps>
                <int_feature>SPAM</int_feature>
            </interface>
            <interface technology="serial" connect_group="1" name="s0/2/3">
                <max_bps>128000</max_bps>
            </interface>
            <interface technology="serial" connect_group="1" name="s0/2/4">
                <max_bps>128000</max_bps>
            </interface>
        </interfaces>
        <special>
            <feature>...</feature>
            <feature>+++</feature>
            <feature>***</feature>
        </special>
    </device>
    
    <device type="switch" name="swa" serial_number="345-543" platform="1900">
        <os>10.0</os>
        <special>
            <feature>nema porty :-)</feature>
        </special>
    </device>
</equipment>
Citováno z „http://infra2.cs.vsb.cz/vl-wiki/index.php/Virtlab:%C5%98%C3%ADd%C3%ADc%C3%AD_server/Mapovac%C3%AD_algoritmus“
Osobní nástroje