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

Z VirtlabWiki

(Rozdíly mezi verzemi)

Přejít na: navigace, hledání

Verze z 21:05, 24. 2. 2007

Obsah

1 Popis
2 Ukázky
3 Zdrojové XML soubory
- 3.1 Topologie
- 3.2 Vybavení

Popis

Celkový postup mapovacího algoritmu:

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.
  - použijí se funkce virtlabParserTopology::getVertexesTypes() a virtlabParserEquipment::getDevicesTypes(), jejiž výstupy se jednoduše porovnají pomocí funkce array_diff
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.
  - použijí se funkce virtlabParserTopology::getVertexesFeatures() a virtlabParserEquipment::getDevicesFeatures(), jejiž výstupy se jednoduše porovnají pomocí funkce array_diff
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í.
  - použije se funkce virtlabParserTopology::getEdgesFeatures(), jejíž výstupní seznam se zdvojí funkcí DoubleArrayItems. Teto seznam se poravná funkcí array_porovnej (kvůli duplicitním hodnotám nejde použít array_diff) s výstupem funkce virtlabParserEquipment::getDevicesInterfacesFeatures(). array_diff]
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 0 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)

Ukázky

ukázka 1:

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
       )
)

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.

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>

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“

Kategorie: Diplomová práce | Jan Vavříček

 ## '''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í.
 ##* použije se funkce <tt>[[Virtlab:ParserTopology.php.inc|virtlabParserTopology]]::getEdgesFeatures()</tt>, jejíž výstupní seznam se zdvojí funkcí <tt>[[Virtlab:SupportFunctions.php.inc|DoubleArrayItems]]</tt>. Teto seznam se poravná funkcí <tt>[[Virtlab:SupportFunctions.php.inc|array_porovnej]]</tt> (kvůli duplicitním hodnotám nejde použít <tt>[http://www.php.net/array_diff array_diff]</tt>) s výstupem funkce <tt>[[Virtlab:ParserEquipment.php.inc|virtlabParserEquipment]]::getDevicesInterfacesFeatures()</tt>. array_diff]
-# '''vlastní mapovací část'''
+# '''vlastní mapovací část''' realizovaná funkcí <tt>[[Virtlab:Mapping.php.inc|virtlabMapping]]::Map()</tt>
-## ze seznamu zařízení (<tt>[[Virtlab:ParserEquipment.php.inc|virtlabParserEquipment]]::getDevicesList()</tt>) a vrcholů linek virtuální topologie (<tt>[[Virtlab:ParserTopology.php.inc|virtlabParserTopology]]::getVertexesList()</tt>) se vytvoří dvojrozměrné pole (indexováno prvky ze získaných seznamů), jehož hodnoty jsou <tt>0</tt> 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í <tt>[[Virtlab:Mapping.php.inc|virtlabMapping]]::Availability($device, $vertex)</tt> (viz '''ukázka 1'''):
+## ze seznamu zařízení (<tt>[[Virtlab:ParserEquipment.php.inc|virtlabParserEquipment]]::getDevicesList()</tt>) a vrcholů linek virtuální topologie (<tt>[[Virtlab:ParserTopology.php.inc|virtlabParserTopology]]::getVertexesList()</tt>) se vytvoří dvojrozměrné pole (indexováno prvky ze získaných seznamů), jehož hodnoty jsou <tt>0</tt> 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í '''<tt>[[Virtlab:Mapping.php.inc|virtlabMapping]]::Availability($device, $vertex)</tt>''' (viz '''ukázka 1'''):
 ##* zjistění ''vhodnosti'' je komplexní problém, které se skládá z mnoha částí:
 ##*# '''porovnání typu''' zařízení s vrcholem (při neshodě vrácena hodnota <tt>[[Virtlab:Values.php.inc|virtlabValues]]::badType</tt>)
 ## 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í <tt>[[Virtlab:Mapping.php.inc|virtlabMapping]]::Evaluate($device)</tt> (viz '''ukázka 2''')
 ##* jednotlivá ''vnitřní'' pole se seřadí vzestupně, podle hodnot zařízení
-## takhle vyrobené pole slouží jako vstup funkce <tt>[[Virtlab:Mapping.php.inc|virtlabMapping]]::Mapping($map2, &$vysledek)</tt>, které '''rekurzivně''' zjišťuje jestli je ''namapování'' možné
+## takhle vyrobené pole slouží jako vstup funkce '''<tt>[[Virtlab:Mapping.php.inc|virtlabMapping]]::Mapping($map2, &$vysledek)</tt>''', které '''rekurzivně''' zjišťuje jestli je ''namapování'' možné - tuto informaci nám sdělí návratová hodnota (<tt>0</tt> nebo <tt>1</tt>). V případě kladného výsledku se v proměnné <tt>$vysledek</tt> bude nacházet výsledek mapovaní (viz '''ukázka 3''')
+### 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 <tt>0</tt>
-...
+### 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 <tt>$vysledek</tt> a vrátí se <tt>1</tt>
+### projdou se všechny vrcholy, jestli některý nemá už jen '''jedno''' možné zařízení na namapování
+#### příslušná dvojice ''vrchol - zařízení'' (je všemy výskyty zařízení) se odstraní ze vstupního pole (pomocí funkce <tt>[[Virtlab:SupportFunctions.php.inc|MatrixClear]]</tt>) a na zbytek se spustí funkce <tt>[[Virtlab:Mapping.php.inc|virtlabMapping]]::Mapping</tt> (zde dochází ke zmíněné '''rekurzi'''), pričemž se zjišťuje návratová hodnota této funkce. Kladný výsledek (reprezentován <tt>1</tt>), znamená že výběr dvojice '''vede k úspěšnému namapování''' a dvojice se tady uloží do <tt>$vysledek</tt> a je vrácena hodnota <tt>1</tt>. Záporný výsledek znamená (reprezentován <tt>0</tt>), ž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ácena<tt>0</tt>
+### 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 <tt>for</tt>). Pro každou dvojici ''vrchol - zařízení'' se pokusíme spustit funkci <tt>[[Virtlab:Mapping.php.inc|virtlabMapping]]::Mapping</tt> se zbytkem vstupního pole, přičemz kontrolujeme náratovou hodnotu. Kladný výsledek (reprezentován <tt>1</tt>), znamená že výběr dvojice '''vede k úspěšnému namapování''' a dvojice se tady uloží do <tt>$vysledek</tt> a je vrácena hodnota <tt>1</tt>. Záporný výsledek znamená (reprezentován <tt>0</tt>), že namapování zbytku se '''nepovedlo''', a pokračuje dále v procházení dvojic
+## 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í <tt>[[Virtlab:Mapping.php.inc|virtlabMapping]]::Mapping</tt>, 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''')
 == Ukázky ==

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

Z VirtlabWiki

Verze z 21:05, 24. 2. 2007

Obsah

Popis

Ukázky

Zdrojové XML soubory

Topologie

Vybavení

Zobrazení

Osobní nástroje

Navigace

Aktuality

Pro vývojáře Virtlabu

Provoz

Hledat

Nástroje