Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

Bevezetés a számításelméletbe, Algoritmusok elmélete

A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

A hallgatók megismerkednek az infokommunikációs hálózatok legfontosabb mérnöki kihívásaival, tervezési kérdéseivel kisebb hálózatoktól kezdve a maghálózaton keresztül az Internetig. A hallgatók áttekintést kapnak a hálózatok modellezésének legfőbb technikáiról, melyeket maguk is elsajátítanak a tárgy keretein belül. Az alkotott modelleken keresztül a hallgatók elmélyíthetik, gyakorlatban is kipróbálhatják a korábbi tanulmányaik során felhalmozott algoritmikus tudást az Internet forgalmi-, útvonal-, topológia-, és sávszélesség-tervezésén keresztül.

• IP forgalomtovábbítás és tömörített adatstruktúrák
• IP címzési rendszer, IP forgalomtovábbítás, skálázhatósági problémák
• Prefix fák tömörítése, információ-elméleti korlátok, tömörített adatstruktúrákon való keresés
• Hatékony sávszélesség kihasználás kódolással
• Hálózatok sávszélesség tervezése, multicast útvonalválasztás
• Mérnöki modellek leíróerejének demonstrálása a hálózati kódolás példáján keresztül
• Virtuális hálózatok tervezése
• Fizikai hálózatok felett kialakított virtuális hálózatok gyakorlati megvalósításai (cloud computing, SDN, stb.)
• Virtuális hálózatok hatékony erőforrás kiosztása, virtuális csomópontok és szakaszok leképezése a fizikai erőforrásokra
• Forgalmi tervezés az Interneten
• Az Internet forgalmi tervezésének alapjai
• A telefonhálózatokban jól ismert egyszerű Erlang formulához hasonló összefüggés létezésének demonstrálása az Internet esetén
• Hálózati erőforrások méretezése hálózat kalkulus segítségével
• Klasszikus sorbanállás-elméleti rendszer: bejövő (aggregált forgalomból származó) csomagok, buffer, kiszolgáló egység
• Hálózati kalkulus alkalmazása a korábbi bonyolult tömegkiszolgálási modellek egyszerűsítésére
• Forgalomszabályozás az Interneten
• TCP zárt hurkú szabályozásának folyadékmodellje, folytonos idejű visszacsatolt rendszerek, szabályozók
• TCP (és újabb verziók) torlódásszabályozása, hálózat stabilitásának vizsgálata, illetve stabil működésének garantálása

Heti 2 óra tantermi előadás és kéthetenkénti 2 órás tantermi gyakorlat. Az előadáson elmondott ismereteket a tantermi gyakorlatokon esettanulmányok és tervezési példák egészítik ki. A házi feladatok megfelelő elkészítése esetén megajánlott jegy szerezhető.

1. A szorgalmi időszakban: házi feladatok elkészítése, melyek alapján megajánlott jegy szerezhető.
2. A vizsgaidőszakban: írásbeli vizsga.
3. Elővizsga: a vizsgaidőszakot megelőző héten.

Órák előtt és után, továbbá a tanszéken, egyeztetés szerint.

Ajánlott irodalom

Az egyes anyagrészeknél megadjuk a felhasználható szakirodalmat.

R. Koetter and M. Médard, "An algebraic approach to network coding," IEEE/ACM Trans. on Networking, vol. 11, no. 5, pp. 782-795, 2003

Bonald, Thomas, and James W. Roberts. "Internet and the Erlang formula." ACM SIGCOMM Computer Communication Review vol. 42 no. 1, pp. 23-30, 2012

Le Boudec, J. Y., Thiran, P. Network calculus: a theory of deterministic queuing systems for the internet (Vol. 2050). Springer. 2001