Virtlab:Řídící server/Mapovací algoritmus
Z VirtlabWiki
Obsah |
[editovat]
Popis
Celkový postup mapovacího algoritmu:
- rychlé ověřění jednoduchých podmínek, jestli má mapování šanci na úspěch
- 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
- 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
- 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]
- 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.
- vlastní mapovací část realizovaná funkcí virtlabMapping::Map()
- 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í:
- porovnání typu zařízení s vrcholem (při neshodě vrácena hodnota virtlabValues::badType)
- 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)
- 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)
- porovnání speciálních vlastností zařízení (pokud nejsou splněny všechny požadavky, je vrácena hodnota virtlabValues::noDeviceFeature)
- 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í)
- zjištění způsobilostí rozhraní pro všechny požadované linky (počítáno přes všechny linky a rozhraní)
- porovnání speciálních vlastností rozhraní a linky
- 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
- zjistění vhodnosti je komplexní problém, které se skládá z mnoha částí:
- 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í
- 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)
- 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
- 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
- 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 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
- 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
- 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)
- 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):
[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>
Kategorie: Komponenty virtlabu | Server | Řídící server | PHP | XML | UNCOMPLETE
