Programozható csomagütemezés: elmélet, algoritmusok, kiértékelés

Korábban a fix-funkciós hálózati eszközök minden képességüket, legyen szó csomagtovábbításról vagy forgalom-ütemezésről, hardverben valósították meg.

Nemrég azonban megjelentek a piacon programozható, P4-kompatiblis hálózati eszközök, melyek lehetővé teszik üzemeltetőik számára, hogy igényeik szerint változtassanak az általuk karbantartott adatsík viselkedésén.

Még ezekkel az eszközökkel is, felhasználók által programozható csomagütemezés eddig többnyire nem valósult meg. Felmerült ugyan a PIFO, egy hardveresen támogatott absztrakció amely egyszerre ígér programozhatóságot és sebességet, de jelenleg nem érhető el olyan hardver, amely ténylegesen implementálná. Részben erre, részben pedig a referencia PIFO implementáció korlátainak áthidalására jelent meg a az SP-PIFO, egy ütemező algoritmus, ami FIFO-k segítségével, egy adaptációs algoritmus segítségével közelíti a PIFO viselkedését azáltal, hogy a sorok összesített kimenetén minimalizálja a prioritás-inverziókat, és már a jelenleg is piacon elérhető eszközökön is implementálható.

Ebben a tanulmányban célként tűztem ki az eredeti SP-PIFO cikkben bemutatott, PUPD nevű adaptációs algoritmus elemzését, versenyképességének mérését tetszőleges bemeneti rang-eloszlásra az adott eloszláshoz igazított statikus korlátokkal szemben, illetve annak vizsgálatát, hogy lehetséges-e javítani az SP-PIFO teljesítményén az adaptációs függvény változtatásával.

E célból módosításokat eszközöltem a NetBench nevű hálózati szimulációs környezethez, melyek egyfelől lehetővé teszik a szimulációk párhuzamos kiértékelését, másfelől pedig megkönnyítik, hogy tetszőleges saját adaptációs algoritmussal vizsgáljam a PUPD-t.

Bemutatok továbbá egy algoritmust, ami lehetővé teszi ismert bementi rang-eloszlás esetén egy hibafüggvény tekintetében a statikus korlátok optimumának kiszámítását, illetve egy adaptációs algoritmust, amely képes gyorsan alkalmazkodni tetszőleges bemeneti rang-eloszláshoz, és bizonyos feltételek esetén képes lehet felülmúlni a PUPD-t azonos bemenetre.

szerző

• 
  Sarkadi Csaba
  Mérnök informatikus szak, mesterképzés
  mesterképzés (MA/MSc)

konzulensek

• 
  Dr. Rétvári Gábor
  tudományos főmunkatárs, Távközlési és Médiainformatikai Tanszék
• 
  Vass Balázs
  tanársegéd, Távközlési és Médiainformatikai Tanszék

helyezés