Kezdőlap / Kidolgozott tételek / DEIK Mérnökinformatikus BSC 2017 / 14. tétel

14. Tétel — NAT/PAT címcsere és adatszerkezetek

Frissítve: 2026-09-09

Ez a tétel két nagyobb témakört fed le: a NAT/PAT címcsere-mechanizmusokat, valamint az adatszerkezetekkel kapcsolatos alapfogalmakat, az elemi és összetett adatszerkezeteket, illetve a fákat.

Témák

I. Témakör: NAT/PAT címcsere mechanizmusok

• Magyarázza a NAT/PAT címcsere mechanizmusokat!

II. Témakör: Adatszerkezetekkel kapcsolatos alapfogalmak, elemi és összetett adatszerkezetek, valamint fák

• Adatszerkezetekkel kapcsolatos alapfogalmak: modellezés, absztrakció, absztrakt adatszerkezetek.
• Elemi adatszerkezetek: lista, verem, sor.
• Halmaz, multihalmaz, mátrix.
• Fák ábrázolása, keresések, bejárások, törlés, beszúrás.

I. Témakör: NAT/PAT címcsere mechanizmusok

1. Bevezetés és a NAT alapkoncepciója

A hálózati címfordítás, angolul Network Address Translation (NAT), egy olyan, a hálózati útválasztókban (routerekben) implementált mechanizmus, amely lehetővé teszi a belső, privát IP-címmel rendelkező hálózati eszközök számára, hogy egy vagy több külső, publikus IP-címen keresztül kommunikáljanak a globális internettel. A technológia elsődleges célja az volt, hogy enyhítse az IPv4-címek kimerüléséből fakadó problémát. A NAT lényegében egyfajta "fordítóként" működik a privát és a publikus hálózat határán, módosítva az IP-csomagok fejlécében található forrás- vagy cél-IP-címeket.

1. Kérés indítása a belső hálózaton: Egy helyi eszköz elküld egy adatcsomagot egy internetes szerver felé.
2. A csomag megérkezése a routerhez: A helyi hálózat routere elfogja a csomagot, mielőtt az elhagyná a helyi hálózatot.
3. Címcsere és port-hozzárendelés: A router a csomagban lévő belső forrás IP-címet lecseréli a saját nyilvános IP-címére, és hozzárendel egy egyedi portszámot.
4. Rögzítés a NAT-táblázatban: A router eltárolja a kapcsolat adatait a NAT-táblájában (melyik belső IP-cím melyik külső porttal párosul), hogy majd tudja kezelni a választ.
5. Továbbítás az internetre: A router elküldi a módosított csomagot az internetre. A célállomás szerver számára úgy tűnik, mintha a kérés közvetlenül a routertől érkezett volna.
6. Válasz megérkezése: A távoli szerver visszaküldi a választ a router nyilvános IP-címére és a hozzá tartozó portra.
7. Visszafordítás és kézbesítés: A router ellenőrzi a NAT-táblázatot, visszacseréli a nyilvános címet az eredeti belső IP-címre, majd továbbítja a csomagot a helyes belső eszköznek.

2. A statikus NAT, a dinamikus NAT és a PAT (NAT Overload) összehasonlítása

A címfordításnak több megvalósítási szintje létezik:

• Statikus NAT (Static NAT): Egy-az-egyhez (1:1) leképezést valósít meg egy belső privát IP-cím és egy külső publikus IP-cím között. Ez a módszer nem oldja meg az IP-címek hiányát, hanem olyan belső szerverek külső elérését biztosítja, amelyeknek fix publikus címmel kell rendelkezniük.
• Dinamikus NAT (Dynamic NAT): Egy belső privát IP-címet a publikus IP-címek egy előre definiált pooljából kap meg ideiglenes jelleggel, amíg a kapcsolat fennáll. Ha a készlet kimerül, újabb belső gép nem tud kapcsolatot létesíteni az internet irányába, amíg egy korábbi felszabadul.
• PAT (Port Address Translation) / NAT Overload: A PAT nemcsak a csomag hálózati rétegbeli IP-címét módosítja, hanem a transzport réteg portszámait is bevonja a folyamatba. Ennek köszönhetően egyetlen publikus IP-cím mögé egy teljes belső hálózat (akár több ezer eszköz) is elrejthető, mivel a belső privát_IP : privát_port párokat a router a saját egyedi publikus IP-címére és egyedileg kiosztott publikus_port párjaira képezi le.

  A PAT egyfajta alapvető tűzfalként is funkcionál. Mivel a fordítási táblázat bejegyzéseit a belső hálózatból kifelé irányuló forgalom hozza létre, a rendszer alapértelmezetten eldob minden olyan bejövő csomagot, amely nem egy már létező, belülről kezdeményezett kommunikációra érkezik válaszként.

II. Témakör: Adatszerkezetekkel kapcsolatos alapfogalmak, elemi és összetett adatszerkezetek, valamint fák

1. Modellezés, absztrakció és az Absztrakt Adatszerkezet (ADT)

• Modellezés: Az a folyamat, amely során a vizsgált valós rendszer vagy probléma lényeges tulajdonságait, összefüggéseit és entitásait matematikai, illetve informatikai struktúrákként (változók, objektumok, kapcsolatok) fogalmazzuk meg.
• Absztrakció: Az a kognitív és tervezési elv, amely elhanyagolja a nem lényeges, alacsony szintű részleteket (pl. a hardveres címezhetőséget vagy a memóriafoglalás fizikai mikéntjét), és a feladat szempontjából kulcsfontosságú logikai tulajdonságokra fókuszál.
• Absztrakt Adatszerkezet (ADT – Abstract Data Type): Olyan matematikai modell vagy specifikáció, amely az adatok halmazát és azokon végezhető megengedett műveleteket kizárólag a viselkedésük alapján definiálja, függetlenül attól, hogy azt a programozási nyelvben hogyan implementálják.

2. Elemi adatszerkezetek: Lista, Verem, Sor

Az elemi adatszerkezetek a lineáris adatszerkezetek családjába tartoznak, ami azt jelenti, hogy elemeik között egyenes, egymás utáni (sorrendi) kapcsolat van.

• Lista: Olyan lineáris adatszerkezet, amely elemek véges sorozatát tárolja, ahol egy elem többször is előfordulhat.
  • Tömbalapú megvalósítás: Gyors közvetlen elérést biztosít az indexek alapján, azonban a mérete statikus, és a közbülső beszúrások/törlések költségesek az elemek eltolása miatt.
  • Láncolt lista megvalósítás: Az elemek nem memóriafolytonosan helyezkednek el, hanem egy adattagot és a következő elemre mutató hivatkozást (pointert) tartalmaznak. A beszúrás és törlés hatékony, de az elérés szekvenciális.
• Verem: LIFO (Last-In, First-Out) elvű adatszerkezet, ahol az adatok felvétele és elvétele mindig ugyanazon a végponton (a verem tetején) történik. Tipikus alkalmazási területei: függvényhívások kezelése, fordítóprogramokban a zárójelek helyességének ellenőrzése, visszalépéses algoritmusok.
• Sor: FIFO (First-In, First-Out – elsőként be, elsőként ki) elven működő lineáris adatszerkezet. Az elemek beszúrása a sor végén, míg a törlése a sor elején történik.

3. Halmaz, Multihalmaz, Mátrix

• Halmaz: Olyan matematikai struktúra, amely valamilyen tulajdonság alapján megegyező, rendezetlen elemek gyűjteményét reprezentálja. Alapvető műveletei: unió, metszet, halmazkülönbség, valamint az elemtartalmazás vizsgálata.
• Multihalmaz: A halmaz általánosítása, ahol egy elem többször is szerepelhet a gyűjteményben; a halmazelméleti szemlélettel ellentétben itt a multiplicitásnak (az elemek előfordulási számának) is van jelentősége.
• Mátrix: Kétdimenziós, téglalap alakú rácsszerkezetbe rendezett adatszerkezet, amelyet m sor és n oszlop határoz meg. A programozásban leggyakrabban kétdimenziós tömbként valósítják meg, memóriában sor- vagy oszlopfolytonos linearizációval. Elengedhetetlen eszköz a lineáris algebrai számításokhoz, gráfelméletben a relációk és súlyozott élek (szomszédsági mátrixok) ábrázolásához.

4. Fák ábrázolása, keresések, bejárások, törlés és beszúrás

A fa nemlineáris, hierarchikus adatszerkezet, amely csomópontokból és azokat összekötő élekből áll.

Fogalmak és ábrázolás

• Gyökér: A fa legfelső szintjén lévő kiindulópont.
• Szülő, Gyermek, Testvér: A hierarchikus kapcsolatokat leíró fogalmak.
• Levél: Olyan csomópont, amelynek nincsenek gyermekadatai.
• Ábrázolás: Dinamikus láncolt szerkezettel (ahol minden csomópont tartalmazza az adatot és a gyermekekre mutató pointereket, pl. bal- és jobboldali mutató bináris fák esetén), vagy speciális esetben tömbbel (pl. kupacoknál, ahol az indexek matematikai összefüggései határozzák meg a szülő-gyermek kapcsolatot).

Bináris Keresőfák és Műveleteik

A bináris keresőfa olyan bináris fa, amelyre igaz, hogy bármely csomópontra vonatkozóan a bal oldali részfa összes eleme kisebb, míg a jobb oldali részfa összes eleme nagyobb a csomópont értékénél.

• Keresés: A gyökértől indulva összehasonlítjuk a keresett értéket az aktuális csomópontéval. Ha kisebb, balra lépünk; ha nagyobb, jobbra; ha megegyezik, megtaláltuk.
• Beszúrás: Megkeressük azt a helyet, ahová az elemet illeszteni kellene; ha az üres, oda hozzuk létre az új csomópontot levélként a szabályok megtartásával.
• Törlés: Három esetet különböztetünk meg:
  • A törlendő elem levélcsúcs: Egyszerűen eltávolítjuk, a szülő mutatóját nullázzuk.
  • A törlendő elemnek egy gyermeke van: A csomópontot töröljük, és a helyére emeljük az egyetlen gyermekét.
  • A törlendő elemnek két gyermeke van: Megkeressük a jobb oldali részfa minimumát (vagy a bal oldali maximumát), átmásoljuk az értékét a törlendő csomópontba, majd azt a levélelemet töröljük.

Fa bejárási algoritmusok

A bejárás azt jelenti, hogy a fa minden egyes csomópontját pontosan egyszer látogatjuk meg. A bejárás iránya szerint három alapvető mélységi bejárást ismerünk:

• Preorder bejárás (Gyökér – Bal – Jobb): Először a gyökeret dolgozzuk fel, majd rekurzíven a bal részfát, végül a jobb részfát.
• Inorder bejárás (Bal – Gyökér – Jobb): Először a bal részfát járjuk be, feldolgozzuk a gyökeret, majd a jobb részfát.
  • Kiemelkedő tulajdonság: Ha egy bináris keresőfán inorder bejárást hajtunk végre, az elemeket szigorúan növekvő sorrendben kapjuk vissza.
• Postorder bejárás (Bal – Jobb – Gyökér): Először a bal és jobb részfát járjuk be, és a gyökeret csak a legvégén látogatjuk meg.
• Szint szerinti (Level-order / Szélességi) bejárás: Sor adatszerkezet segítségével szintenként, balról jobbra haladva látogatjuk meg a csomópontokat.