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

Z VirtlabWiki

(Rozdíly mezi verzemi)
Přejít na: navigace, hledání
Verze z 22:19, 23. 2. 2007
Vav166 (Diskuse | příspěvky)
(→Ukázky)
← Předchozí porovnání		 Verze z 22:23, 23. 2. 2007
Vav166 (Diskuse | příspěvky)
(→Zdrojové XML soubory)
Následující porovnání →
Řádka 158: Řádka 158:
== Zdrojové XML soubory == == Zdrojové XML soubory ==
=== Topologie === === Topologie ===
 +<pre>
 +&lt;?xml version="1.0" encoding="utf-8" ?&gt;
 +&lt;!DOCTYPE virtual_topology SYSTEM "topology.dtd"&gt;
 +
 +&lt;virtual_topology&gt;
 + &lt;edge technology="serial" name="Kocour"&gt;
 + &lt;vertex name="ra"/&gt;
 + &lt;vertex name="rb"/&gt;
 + &lt;/edge&gt;
 +
 + &lt;edge technology="ethernet" ether_type="fast" name="Krokodyl"&gt;
 + &lt;vertex name="rc"/&gt;
 + &lt;vertex name="rd"/&gt;
 + &lt;/edge&gt;
 +
 + &lt;edge technology="serial" name="Kacena"&gt;
 + &lt;vertex name="ra"/&gt;
 + &lt;vertex name="rd"/&gt;
 + &lt;min_bps&gt;100000&lt;/min_bps&gt;
 + &lt;edge_feature&gt;SPAM&lt;/edge_feature&gt;
 + &lt;/edge&gt;
 +
 + &lt;vertex_detail type="router" name="ra"&gt;
 + &lt;os relation="eq"&gt;12&lt;/os&gt;
 + &lt;vertex_feature&gt;***&lt;/vertex_feature&gt;
 + &lt;/vertex_detail&gt;
 +
 + &lt;vertex_detail type="router" name="rb"&gt;
 + &lt;/vertex_detail&gt;
 +
 + &lt;vertex_detail type="router" name="rc"&gt;
 + &lt;/vertex_detail&gt;
 +
 + &lt;vertex_detail type="router" name="rd"&gt;
 + &lt;poss_platforms&gt;
 + &lt;platform&gt;17..&lt;/platform&gt;
 + &lt;/poss_platforms&gt;
 + &lt;/vertex_detail&gt;
 +
 +&lt;/virtual_topology&gt;
 +</pre>
 +
=== Vybavení === === Vybavení ===
 +<pre>
 +&lt;?xml version="1.0" encoding="utf-8" ?&gt;
 +&lt;!DOCTYPE equipment SYSTEM "equipment.dtd"&gt;
 +
 +&lt;equipment&gt;
 + &lt;device type="router" name="r1" serial_number="12345-54321" platform="7200"&gt;
 + &lt;os&gt;12.8&lt;/os&gt;
 + &lt;interfaces&gt;
 + &lt;interface technology="serial" connect_group="1" name="s0/1/0"&gt;
 + &lt;max_bps&gt;128000&lt;/max_bps&gt;
 + &lt;int_feature&gt;...&lt;/int_feature&gt;
 + &lt;/interface&gt;
 + &lt;interface technology="serial" connect_group="1" name="s0/2/1"&gt;
 + &lt;max_bps&gt;64000&lt;/max_bps&gt;
 + &lt;int_feature&gt;xxx&lt;/int_feature&gt;
 + &lt;/interface&gt;
 + &lt;interface technology="serial" connect_group="1" name="s0/1/1"&gt;
 + &lt;max_bps&gt;128000&lt;/max_bps&gt;
 + &lt;int_feature&gt;+++&lt;/int_feature&gt;
 + &lt;/interface&gt;
 + &lt;interface technology="ethernet" ether_type="legacy" connect_group="2" name="e0"&gt;
 + &lt;int_feature&gt;802.1q&lt;/int_feature&gt;
 + &lt;/interface&gt;
 + &lt;/interfaces&gt;
 + &lt;special&gt;
 + &lt;feature&gt;mpls&lt;/feature&gt;
 + &lt;/special&gt;
 + &lt;/device&gt;
 +
 + &lt;device type="router" name="r3" serial_number="2345-5432" platform="1700"&gt;
 + &lt;os&gt;12.6.321-ipsec:XXX&lt;/os&gt;
 + &lt;interfaces&gt;
 + &lt;interface technology="serial" connect_group="1" name="s0"&gt;
 + &lt;max_bps&gt;64000&lt;/max_bps&gt;
 + &lt;/interface&gt;
 + &lt;interface technology="ethernet" ether_type="fast" connect_group="3" name="fa0/0"&gt;
 + &lt;/interface&gt;
 + &lt;interface technology="ethernet" ether_type="fast" connect_group="3" name="fa0/1"&gt;
 + &lt;/interface&gt;
 + &lt;/interfaces&gt;
 + &lt;/device&gt;
 +
 + &lt;device type="router" name="r5" serial_number="525444-69855" platform="1700"&gt;
 + &lt;os&gt;12.0&lt;/os&gt;
 + &lt;interfaces&gt;
 + &lt;interface technology="serial" connect_group="1" name="s0/0"&gt;
 + &lt;max_bps&gt;128000&lt;/max_bps&gt;
 + &lt;int_feature&gt;SPAM&lt;/int_feature&gt;
 + &lt;/interface&gt;
 + &lt;interface technology="ethernet" ether_type="gigabit" connect_group="3" name="gi0"&gt;
 + &lt;/interface&gt;
 + &lt;/interfaces&gt;
 + &lt;special&gt;
 + &lt;feature&gt;mpls&lt;/feature&gt;
 + &lt;/special&gt;
 + &lt;/device&gt;
 +
 + &lt;device type="router" name="r7" serial_number="5244-55" platform="7200"&gt;
 + &lt;os&gt;12.5.12-65.1&lt;/os&gt;
 + &lt;interfaces&gt;
 + &lt;interface technology="serial" connect_group="1" name="s0/2/0"&gt;
 + &lt;max_bps&gt;128000&lt;/max_bps&gt;
 + &lt;/interface&gt;
 + &lt;interface technology="serial" connect_group="1" name="s0/2/1"&gt;
 + &lt;max_bps&gt;128000&lt;/max_bps&gt;
 + &lt;/interface&gt;
 + &lt;interface technology="serial" connect_group="1" name="s0/2/2"&gt;
 + &lt;max_bps&gt;128000&lt;/max_bps&gt;
 + &lt;int_feature&gt;SPAM&lt;/int_feature&gt;
 + &lt;/interface&gt;
 + &lt;interface technology="serial" connect_group="1" name="s0/2/3"&gt;
 + &lt;max_bps&gt;128000&lt;/max_bps&gt;
 + &lt;/interface&gt;
 + &lt;interface technology="serial" connect_group="1" name="s0/2/4"&gt;
 + &lt;max_bps&gt;128000&lt;/max_bps&gt;
 + &lt;/interface&gt;
 + &lt;/interfaces&gt;
 + &lt;special&gt;
 + &lt;feature&gt;...&lt;/feature&gt;
 + &lt;feature&gt;+++&lt;/feature&gt;
 + &lt;feature&gt;***&lt;/feature&gt;
 + &lt;/special&gt;
 + &lt;/device&gt;
 +
 + &lt;device type="switch" name="swa" serial_number="345-543" platform="1900"&gt;
 + &lt;os&gt;10.0&lt;/os&gt;
 + &lt;special&gt;
 + &lt;feature&gt;nema porty :-)&lt;/feature&gt;
 + &lt;/special&gt;
 + &lt;/device&gt;
 +&lt;/equipment&gt;
 +</pre>
[[Kategorie:Diplomová práce]] [[Kategorie:Diplomová práce]]
[[Kategorie:Jan Vavříček]] [[Kategorie:Jan Vavříček]]

Verze z 22:23, 23. 2. 2007

Obsah

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

...

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

Zdrojové XML soubory

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“