lehetőségeinek vizsgálata, továbbá a szóba jövő módszerek elemzése, implementálása és tesztelése. A dolgozat második fejezetében röviden ismertetem a

Tartalom   1.   Bevezetés ................................................................................................................................................. ......5   2.   Session Initiation Protocol......................................................................................................................... .....7 2.1.   A session........................................................................................................................ ..........................7 2.2.   A SIP működése................................................................................................................... ....................7 2.3.   A SIP üzenetek felépítése............................................................................................................ .............9 2.4.   A SIP kiszolgáló eszközei:................................................................................................ .....................11   3.   A tömörítésről.................................................................................................................... ..........................13   4.   Signalling Compression.............................................................................................................................. ..15 4.1.   A SigComp üzenet felépítése...................................................................................... ...........................17 4.2.   A SigComp architektúrális felépítése....................................................................................... ..............18 4.2.1.   Compressor dispatcher................................................................................................ ...................19 4.2.2.   Compressor........................................................................................................ ............................20 4.2.3.   Decompressor dispatcher.................................................................................... ...........................20 4.2.4.   Decompressor (UDVM).............................................................................................. ...................20 4.2.5.   Statehandler.......................................................................................................................... ..........24   5.   Tömörítés........................................................................................................................... ..........................26 5.1.   Rice algoritmus........................................................................................................... ...........................26 5.2.   SubExponencial algoritmus........................................................................................................... .........27 5.3.   Huffman algoritmus..................................................................................................... ..........................27 5.4.   LZ77 algoritmus........................................................................................................................ .............28 5.5.   LZSS algoritmus.................................................................................................................................... .30 5.6.   Deflate algoritmus................................................................................................................... ...............30   6.   A match függvény................................................................................................................ ........................31 6.1.   A naiv megoldás......................................................................................................................... ............31 6.2.   Knuth Morris Pratt algoritmusa..................................................................................................... .........31 6.3.   Láncolt lista.............................................................................................................................. ..............33 6.4.   Hash tábla.................................................................................................................................... ...........33   7.   Az LZSS algoritmus alkalmazása............................................................................................................. ....35 7.1.   Match függvény az algoritmusunkhoz................................................................................................. ...36 7.1.1.   A hash táblás megoldás............................................................................................. .....................37 7.1.2.   Hash tábla mátrixszal.............................................................................................. .......................38 7.1.3.   A „reverse index” bevezetése............................................................................................. ............39 7.1.4.   Hash­elés 3 karakter hosszú részstringekkel............................................................ ......................40 7.1.5.   A mátrix kiváltása speciális listákkal....................................................................... ......................41   8.   Mérési eredmények............................................................................................................. .........................44 8.1.   Illeszkedés keresés...................................................................................................... ...........................44 8.2.   Teljesítménybeli különbség a match függvény megvalósításai között................................... ................45 8.3.   Static, dynamic, shared és extended tömörítések......................................................... ..........................46 8.4.   Összehasonlítás az ismert tömörítőkkel....................................................................... ..........................49   9.   Összefoglalás......................................................................................................................................... .......52 10.   Hivatkozások................................................................................................................................. ...............53

1.   Bevezetés  Mára a mobiltelefonok kinőttek az egyszerű telefon szerepből. Egyre inkább fejlődnek és  kezdik átvenni a kéziszámítógépek szerepét. Rendelkeznek egy sor multimédiás képes­ séggel, tudnak mp3 zeneállományokat lejátszani, képesek digitális fényképek készítésére,  küldésére, fogadására. Nem ritka az amelyik már operációs rendszerrel is rendelkezik, így  a tulajdonosa könnyen telepíthet rá harmadik fél által készített programokat is. Természe­ tes az igény, hogy ezek a készülékek közelebb kerüljenek az internethez. Már történtek  ilyen irányú lépések (GPRS, WAP), de az igazi áttörés ezután következik, ugyanis a 3rd  Generation   Partnership   Project   (3GPP)   közösség   az   Internet   Protocol­t   választotta   az  Universal Mobile Telecommunication System (UMTS) alapjául, ezáltal a mobiltelefonok  is rendelkeznek majd IP címmel, így ők is szerves részei lesznek a világhálónak. Az internet számos alkalmazása használ session alapú kommunikációt. Ilyenek példá­ ul a multimédiás alkalmazások, amelyek valós idejű kép, illetve hang adatforgalmat bo­ nyolítanak le. Ezek az alkalmazások saját, jól definiált protokollokon keresztül kommuni­ kálnak egymással. Ezen alkalmazások implementálása mobil eszközökre nehézségekbe  ütközik, ugyanis olyan problémákkal is találkozhatunk, amelyek a hagyományos eszkö­ zök esetében nem fordulnak elő. Ilyen például az, hogy a felhasználó a kommunikáció so­ rán megváltoztathatja a pozícióját (pl. autózás közben telefonál, és a beszélgetés ideje  alatt egyik cella tartományából átmegy egy másikba). A gyakorlatban használt eszköz a fenti probléma megoldására, a Session Initiation  Protocol (SIP) alkalmazása. Ez a protokoll biztosítja a feltételeket az őt használó alkalma­ zásoknak, a session alapú kommunikációhoz. A SIP protokoll alkalmazása azonban újabb  problémát vet fel. A SIP üzenetek szöveges üzenetek, a mobil eszközök pedig a vezetékes  hálózatokhoz képest a nagyságrendileg kisebb sávszélességű vezeték nélküli hálózaton  kommunikálnak.   A   SIP   üzeneteket   ezért   célszerű   tömöríteni.   A   tömörítés   feladata   a  Signalling Compression (SigComp) alrendszeré. Egy jó arányú tömörítéssel sokat spórol­ hatunk a adatátvitelen, ezért a SigComp implementálása kritikus lépés a telefon vagy tele­ fonközpont vezérlőszoftverének irásakor. Dolgozatomban átfogó leírást nyújtok a Signalling Compression alrendszerről, részle­ tesen ismertetem a tömörítéshez gyakrabban használt algoritmusokat, majd egy, a gya­ korlatban is használt konkrét megvalósítást írok le. A kutatásokat a Nokia Hungary Kft.­nél végeztem. A dolgozatomban ismertetett meg­ oldást, a gazdasági életben fogják alkalmazni a Nokia fejlesztési programjának keretében.   A   projekten   belül   feladatom   volt   a   mérési   módszerek   elméleti   kidolgozása,   és   a  mérési   környezet   kialakítása,   valamint   a   tömörítő   algoritmus   optimalizálási  5

lehetőségeinek vizsgálata, továbbá a szóba jövő módszerek elemzése, implementálása és  tesztelése. A dolgozat második fejezetében röviden ismertetem a Session Initiation Protocol mű­ ködését, és üzeneteinek felépítését.  A harmadik fejezetben a tömörítésről mint technikáról írok.  A   negyedik   fejezetben   kerül   ismertetésre   a   Signalling   Compression.   Bemutom   a  SigComp architekturális felépítését, külön alfejezetet szentelek az öt fő komponensnek:  Compressor dispatcher, Compressor, Decompressor dispatcher, Decompressor (UDVM),  Statehandler. Itt lesz szó a SigComp üzenet felépítéséről is.  Az ötödik fejezet a tömörítő algoritmusokról szól: Rice, Sub Exponential, Huffman,  LZ77, LZSS és Deflate.  A hatodik fejezetben az LZ77, illetve az LZSS algoritmus által használt match függ­ vény megvalósításáról lesz szó, azaz a különböző lehetséges módszereknek melyek az  előnyei és a hátrányai.  A hetedik fejezetben egy konkrét megvalósítás kerül bemutatásra. Körbejárjuk a kér­ dést, hogy milyen megszorításokra volt szükség az elméleti algoritmusok implementálá­ sához, hogyan döntöttünk azokban a kérdésekben, amelyekre a választ a szabvány nem  adja meg, illetve az implementátorokra bízza stb.  A nyolcadik fejezet a mérési eredményeké, amelyek alátámasztják hetedik fejezetbeli  döntéseink helyességét.  Végül a kilencedik fejezetben kap helyet az összefoglaló.

6

2.   Session Initiation Protocol A Session Initiation Protocol (SIP) [1] nem egy kizárólagos protokoll, ami a jövőben ki­ váltja a már létező, alkalmazás specifikus session protokollokat, hanem inkább kiegészíti,  bővebb funkcionalitással látja el azokat.

2.1.   A session A számítógépes hálózatokban session­nek [2] nevezünk egy kliens és egy szerver közti  tartós kapcsolatot. Session alapú kommunikáció esetében a kapcsolatot csak egyszer, a  kommunikáció   megkezdése   előtt   építjük   fel,   és   az   él   egészen   annak   befejezéséig.  Eközben számos adatcsomag vándorol a szervertől a kliensig és vissza. A session proto­ kollok feladata ezen kapcsolat fennállásának és hibamentes működésének biztosítása, va­ lamint a szolgáltatás eléréséhez egy interfész biztosítása az őket használó alkalmazások  felé. A számítógépes hálózatokban a valós idejű kommunikációt megkövetelő kapcsola­ tok   (telefonbeszélgetés,   videokonferencia   stb.)   mind   session   alapú   kommunikációt  igényelnek.

2.2.   A SIP működése Ha egy mobil eszköz valamilyen session alapú kapcsolatot szeretne létrehozni egy másik­ kal, akkor rendelkezik azzal a protokollal, ami az adott típusú kommunikáció megköve­ tel. Azonban a kapcsolat kialakításához szükséges lokalizálni a másik eszközt. Ez a SIP  protokollon keresztül történik. Ezután szintén a SIP protokollon keresztül a hívó fél meg­ határozza, hogy a hívott oldal képes­e fogadni a hívást, azaz rendelkezik­e a kapcsolat le­ bonyolításához   szükséges   protokollal.   A   kommunikáció   lezárultával   a   SIP   bontja   a  session kapcsolatot. A SIP tehát képes létrehozni, módosítani, megszakítani multimédia  session­öket (pl. internetes telefonhívás), illetve új résztvevőket invitálni a már meglévő  session­be (pl. konferenciahívás).  A SIP az alábbi szolgáltatásokat nyújtja: • • • •

Végpont helyének meghatározása. Felhasználó elérhetősége (a hívott fél részt kíván­e venni a kommunikációban). Végpont képességeinek meghatározása (milyen multimédiás paraméterekkel rendelke­ zik a hívott végpont). Session   beállítás   (a   hívott   félnél   csengetés,   majd   a   session   paraméterek  beállítása  mindkét oldalon). 7

• •

Session menedzsment (szükség szerint a session paramétereinek módosítása, a session  megszakítása, illetve különböző szolgáltatások meghívása). Működik mind az IPv4, mind az IPv6 felett. [3]

Lássunk egy példát session alapú kommunikációra két felhasználói végpont között. Azért  nem mobiltelefont említettem, mert ezek az eszközök lehetnek, akár számítógépek, pda­k  vagy bármilyen más eszközök, amelyek rendelkeznek IP címmel és képesek valamilyen  session alapú kommunikációra egymással. Ez lehet telefonbeszélgetés, videokonferencia,  szöveges üzenet vagy képküldés, fogadás stb. A mi példánkban Alice szeretne kapcsola­ tot létesíteni Bobbal. Ez a kapcsolat legyen hagyományos telefonbeszélgetés, de mint lát­ ni fogjuk tulajdonképpen ez a SIP szempontjából lényegtelen.  Alice hívást kezdeményezve küld egy INVITE üzenetet Bob SIP URI­jának címezve.  Az megérkezik, és Bob rögtön visszajelez egy  „100 Trying”­ot küldve, hogy vette az  üzenetet.   Ezután   Bob   telefonja   csörögni   kezd   és   egy   „180   Ringing”   üzenetet   küld  Alicenak.  Bob dönthet, hogy elfogadja a hívást, vagy visszautasítja. Tegyük fel, hogy  most elfogadja. Ekkor Bob telefonjától egy „200 OK” SIP üzenet érkezik, és ezt Alice te­ lefonja egy „ACK” üzenettel nyugtázza. Innentől a SIP háttérbe vonul, és átadja a terepet  egy, a beszélgetésre alkalmas protokollnak. Tételezzük fel, hogy a beszélgetés végén Bob  teszi le először a kagylót. Küld egy „BYE” üzenetet Alicenak, amire ő egy „200 OK”  üzenettel reagál. A beszélgetés során lezajlott üzenetváltásokat az 1. ábrán tekinthetjük  meg.

8

2.3.   A SIP üzenetek felépítése A SIP üzenetek szöveges üzenetek. Felépítésük hasonlít a HTML header­ek struktúrájára.  Az első sor a status sor, itt egy utasítás vagy egy utasításra a válasz szerepel. Ezután pe­ gig következnek a SIP header­ek. Ezek tetszőleges sorrendben követhetik egymást. Mi­ előtt megvizsgálnánk a SIP utasításokat és header­eket nézzünk meg egy konkrét utasítást  és arra a választ az előző alfejezet példájából. Az üzenet: INVITE sip:[email protected] SIP/2.0 Via: SIP/2.0/UDP pc33.atlanta.com;branch=z9hG4bK776asdhds Max-Forwards: 70 To: Bob <sip:[email protected]> From: Alice <sip:[email protected]>; tag=1928301774 Call-ID: [email protected] CSeq: 314159 INVITE Contact: <sip:[email protected]> Content-Type: application/sdp Content-Length: 142

A válasz: SIP/2.0 200 OK Via: SIP/2.0/UDP server10.biloxi.com ;branch=z9hG4bKnashds8;received=192.0.2.3 Via: SIP/2.0/UDP bigbox3.site3.atlanta.com ;branch=z9hGbK77ef4c2312983.1;received=192.0.2.2 Via: SIP/2.0/UDP pc33.atlanta.com ; branch=z9hG4bK776asdhds;received=192.0.2.1 To: Bob <sip:[email protected]>;tag=a6c85cf From: Alice <sip:[email protected]>; tag=1928301774 Call-ID: [email protected] CSeq: 314159 INVITE Contact: <sip:[email protected]> Content-Type: application/sdp Content-Length: 131

A SIP protokoll hat alap utasítást definiál: •

INVITE:

•

ACK:

Egy felhasználót invitál egy új sessionbe, vagy egy meglevő  session paramétereit módosítja. Elfogadja a session létrehozási kérelmet. 9

•

OPTION:

Információt kér a szervertől, hogy az milyen protokollokat ismer.

•

BYE:

Session vége.

•

CANCEL:

Visszavonja a folyamatban levő kérést.

•

REGISTER: Regisztrálja a User Agent­et.

Válaszok a SIP üzenetekre: A fogadó fél, miután megkapta a kérést, válaszol rá. A válaszban visszaküldi a kapott  üzenetet, csak az első sorát (status sor) változtatja meg. Az első sor tartalmazza a fogadó  fél által használt SIP verzió számát, a válasz kódszámát, és egy rövid leírást.  A válaszkódokat az alábbi csoportokba oszthatjuk: • 1xx: Ideiglenes üzenetek. •

2xx:

Sikeres válaszok.

•

3xx:

Átirányítással kapcsolatos válaszok.

•

4xx:

Eljárásbeli hibák.

•

5xx:

Szerverhibák.

•

6xx:

Globális hibák.

Fejlécek: A SIP üzenetek fejlécei üzeneteket szállítanak a SIP entitásoknak. A főbb fejlécek az  alábbiak: • Via: Mutatja a használt szállítási protokollt és a kérés útvonalát. Minden  Proxy hozzáad egy bejegyzést ehhez a mezőhöz. • From: A hívó fél címét tartalmazza. •

To:

A hívott fél címét tartalmazza.

•

Call­Id:

•

Cseq:

A hívás egyedi azonosítóját és a host címét. Az értéke a tranzakció  összes üzenetében azonos kell, hogy legyen. Egy véletlen számmal kezdődik és az üzenetváltások során egyel nő.

•

Contact:

•

Egy vagy több címet tartalmaz ahol kapcsolatba lehet lépni a  felhasználóval. User Agent: Az a kliens amivel a kommunikáció zajlik.

SIP URI: A   SIP   entitás   a   felhasználót   a   SIP   URI   (Uniform   Resource   Identifiers)   alapján  azonosítja. A pontos definíció megtalálható [4]­ben. Formátuma hasonlít az e­mailcímek  10

formátumához, egy felhasználó és egy domain nevet tartalmaz @ jellel elválasztva.  Néhány példa a SIP URI­ra: •

user@domain:

 Ahol a domain a teljesn domain név.

•

user@machine:

 Ahol a machine egy SIP entitás neve.

•

user@ip_address:

•

 Ahol az ip_address egy IPv4, vagy egy IPv6­os  IP cím. telephone_number@gateway:  Ahol a gateway egy olyan entitás amelyik a  telefonszámból le tudja kérdezni a felhasználó  user nevét.

2.4.   A SIP kiszolgáló eszközei: A SIP protokolt kiszolgáló eszközök [5] két nagy csoportra bonthatók:  User Agent­ ekre (UA), valamint SIP szerverekre. A User Agent­ek a session alapú kommunikáció végpontjai. Ezek lehetnek mobiltele­ fonok, desktop számítógépek stb. Logikailag két csoportra bonthatjuk a őket, kliensekre  és szerverekre. Az a User Agent lesz a kliens, amelyik kérést küld, majd választ vár egy  másiktól, és szerver lesz az, amelyik fogadja, és válaszol a kérésre. Ez a kliens­szerver  besorolás csak egy adott session­re vonatkozik. Egy User Agent, ha adott időben több  másik User Agent­el kommunikál – azaz több session kapcsolatot is kiépített –, akkor el­ képzelhető, hogy az egyik session­ben a kliens, a másikban pedig a szerver szerepét tölti  be.  A SIP szervereket három csoportba oszthatjuk. Az első csoportban vannak a Proxy  szerverek. Ezek feladata, hogy továbbítsák a User Agent­től, illetve egy másik Proxy  szervertől   kapott   kéréseket.   Az   ő   feladatuk   az   is,   hogy   eldöntsék,   melyik   Proxy   felé  továbbítsák a kérést, azaz forgalomirányító szerepük is van. A Proxy szervereknek két  típusuk van:  Stateful Proxy  és  Stateless Proxy.  A Stateful Proxy eltárolja a tranzakció  állapotát, amíg a kérés feldolgozásra nem kerül. Ez lehetővé teszi például azt, hogy a  kérést egyszerre több szomszédos Proxy szervernek továbbítsa, így lehetővé téve, hogy  párhuzamosan több úton keresse a kérés címzettjét. A Stateless Proxy nem tartja meg a  tranzakció állapotát, csak egyszerűen továbbítja a kérést. A másik csoportba a Registrar  szerverek tartoznak. Ezeknek a szervereknek a feladata, hogy elfogadják és kezeljék a  User Agent­től érkező  REGISTER  kéréseket, és azok címéről, pozíciójáról információt  szolgáltassanak. A harmadik csoportba a Redirect szerverek tartoznak. Ezek a szerverek  feladata a beérkező kérések más címre való átirányítása. Végül térjünk vissza a fejezet elején levő példánkhoz. A kapcsolat most kiépítését  11

Egy összetettebb rendszeren vizsgáljuk (2. ábra). Amikor Alice, bekapcsolja a telefonját,  Bob pedig a számítógépén elindít egy valamilyen hang alapú kommunikációra alkalmas  programot, azok egy­egy REGISTER üzenetet küldenek a hozzájuk legközelebb levő a  Proxy szerverek felé, amelyek a Registrar szerveren keresztül hitelesítik a kérést, és egy  200   OK   üzenetet   küldenek   vissza.   A   legközelebbi   alatt   nem   feltétlenül   a   fizikailag  legközelebb levőt kell érteni, hanem azt, amelyik leghamarabb tud reagálni a kérésre.  Ezután   Alice   hívhatja   Bobot.   Az   INVITE   üzenetet   szintén   a   Proxy­nak   küldi,   az   a  redirect   szervertől   megtudja,   hogy   merre   kell   továbbítani   a   kérést.   A   kérést   ezután  továbbítja  Bob felé és  visszaküld egy 100 Trying üzenetet, Alicenak. Ez két érdekes  dolgot vet fel. A Proxy szerver hasonlóan működik, mint az internet esetében a HTTP  proxy   szerver,   hiszen   Alice   felé   azt   szimulálja,   hogy   Bob   (aki   a   session  kommunikációban a szervernek felel meg), már visszaküldte a 100 Trying üzenetet. Ez  pedig   azért   hasznos,   mert   ezáltal   Alice   befejezheti   az   INVITE   üzenet   küldését   más  Proxy­k felé, hiszen egy már fogadta a kérést. A Proxy szerver pedig továbbítja a kérést  Bob   felé.   Megvárja   amíg   Bob­tól   érkezik   egy   180   Ringing,   majd   ezt   visszaküldi  Alicenak. Innentől már hasonlóan megy a kapcsolat kiépítése, a beszélgetés és a kapcso­ lat lebontása. mint az első példában, csak annyi a különbség, hogy az üzenetváltásokat a  Proxy szerverek közvetítik.

2. ábra

12

3.   A tömörítésről Az adattömörítés feladata egy adott információ minél kisebb helyigényű leírása. Azt a fo­ lyamatot, amíg az eredeti adatot tömörített formára hozzuk kódolásnak, a visszaalakítást  pedig dekódolásnak nevezzük. A kódolás módja szerint kétféle tömörítésről beszélünk:  veszteségmentes, illetve veszteséges tömörítés. Veszteségmentes tömörítés esetén száz  százalékig képesek vagyunk visszaállítani az eredeti adathalmazt, veszteséges tömörítés  során pedig mind a kódolás, mind a dekódolás esetében előfordulhat információvesztés.  Az utóbbi esetben az információvesztés árán jobb tömörítési arányt érhetünk el. Veszte­ séges tömörítést akkor alkalmazunk, amikor nem szükséges az eredeti állapot visszanye­ rése, például video­, kép­ és zeneállományok, tömörítése. Többek között az mpeg, jpeg,   mp3  is veszteségesen tömörített adatformátum. Veszteségmentes tömörítésre akkor van  szükség, ha nélkülözhetetlen az eredeti állapot visszaállítása. Ilyen például a futtatható  állományok, különböző szöveges állományok tömörítése stb. A dolgozatomban csak a  veszteségmentes tömörítésekkel  foglalkozok,  ugyanis   a  SIP  üzenetek esetében  fontos,  hogy vissza tudjuk kapni az eredeti üzenetet. Könnyen belátható, hogy nem létezik olyan általános veszteségmentes tömörítő algo­ ritmus, amely minden sorozathoz rövidebb sorozatot rendel. Ha ugyanis ez igaz lenne,  akkor az algoritmus ismételt alkalmazásával előbb utóbb megkapnánk az üres sorozatot,  abból pedig nem tudnánk dekódolni az eredetit. Ennél több is igaz: [6]  Tétel:  Ha   egy   invertálható   függvény   minden   bitsorozathoz   olyan   sorozatot   rendel,  amelynek   hossza   nem   nagyobb,   mint   az   eredeti,   akkor   minden   sorozathoz   pontosan  önmagával   megegyező   hosszúságú   sorozatot   rendel.   Tehát   nem   tömörít,   legfeljebb  átkódol.  Bizonyítás: Legyen f :  BnBn, ahol  Bn  a legfeljebb n hosszúságú bitsorozatokból álló  halmaz.   Mivel   f   invertálható,   ezért   bijektív   kell   hogy   legyen.   A   bijektív   függvény  szürjektív is, ezért a képhalmaz minden eleme felvetetik értékként. Ekkor viszont, ha  lenne olyan sorozat, amihez a függvény rövidebb sorozatot rendelne, akkor lennie kellene  olyannak is, amihez hosszabbat rendel, hiszen az adott legfeljebb n hosszúságú sorozatok  száma rögzített. Felmerül a kérdés, hogy akkor hogyan léteznek mégis tömörítő algoritmusok. A válasz  az, hogy a gyakorlatban nem az összes sorozatot kell tömöríteni, hanem azok egy szűk  részhalmazát, ráadásul azokban a sorozatokban vannak szabályosságok, ismétlődések, és  a jelek is különböző gyakoriságban szerepelnek. A tömörítő  algoritmusok pedig ezen  információk   alapján   tudják   a  sorozatok   halmazának  egy   kis   részhalmazát  hatékonyan  13

tömöríteni.   Ebből   látszik,   hogy   más­más   algoritmusok   tudnak   hatékonyan   tömöríteni  kép­, video­, zene­ vagy akár szöveges állományokat. Szöveges állománynak tekintünk minden olyan állományt, ami főként az ábécé betűi­ ből, számokból és írásjelekből áll, és valamilyen beszélt nyelv szavai szerepelnek benne.  Azt azonban megengedjük, hogy ezek a szavaknak a beszélt nyelvtől idegen struktúrája  legyen. Így a programnyelvek forrásállományait, egy XML dokumentumot vagy pedig a  SIP üzenetek állományait is szöveges állománynak tekintjük.  Online tömörítésről beszélünk akkor, ha a betömörítendő állományt nem kell teljes  egészében kódolni, hogy azt dekódolni tudjuk. Ez hasznos például egy hálózati alkalma­ zás esetében, amikor a küldő, ha betömörítette az üzenet egy részét, azt már el is küldheti,  és amíg ő az üzenet további részeinek kódolásával foglalkozik, a fogadó oldal már meg­ kezdheti a megkapott üzenetrészek dekódolását. Offline tömörítésről pedig akkor beszé­ lünk, amikor az egész üzenetet kódolni kell, hogy azt később dekódolni tudjuk. A SIP  üzeneteket offline tömörítjük. Bár a SIP üzenetek kódolására választható algoritmusok  közül több képes lenne az online tömörítésre, a SIP architekturális felépítése nem igényli  ennek kihasználását.

14

4.   Signalling Compression A   SIP   üzenetek,   mint   láthattuk   szöveg   alapúak.   E   megoldásnak   vannak   előnyei   és  hátrányai is. Előnyei többek között, hogy könnyen olvashatók és szerkeszthetők lesznek  az üzenetek. Egyik nagy hátránya azonban az, hogy a méretük lényegesen nagyobb lesz,  mintha   valamilyen   bináris   formát   választottak   volna   neki.   Ez   a   méretbeli   különbség  különösen kritikus a mobil eszközöknél, hiszen azok a kommunikációra vezeték nélküli  hálózatot használnak, ahol kisebb a sávszélesség, költségesebb az adatátvitel. Kézenfekvő  ötletnek   tűnik,   hogy   tömörítsük   a   SIP   üzeneteket.  A   tömörítés   feladatát  a  Signalling   Compression (SigComp) [7] látja el.  A SigComp nemcsak egy egyszerű be­ és kitömörítő algoritmus. Természetesen a fő  feladata az üzenetek be­ és kitömörítése, de hogy ezt hatékonyan tudja tenni, számos  egyéb funkciót is meg kell valósítania. A szabvány nem írja elő, hogy melyik algoritmust  kell alkalmazni a tömörítéshez, csak annyit, hogy annak veszteségmentesnek kell lennie.  Ezenfelül ajánlott a szótár alapú tömörítő algoritmus használata. Azért választhatunk sza­ badon a tömörítő algoritmusok között, mert a kitömörítő oldalon a SigComp egy virtuális  gépet valósít meg, amin a kitömörítő algoritmus fut. Az első üzenettel együtt a kitömörítő  algoritmus byte kódját is el kell küldenünk. Ezt a byte kódot a SigComp elmenti és a  többi üzenetben csak hivatkozni kell rá. A virtuális gép Universal Decompressor Virtual   Machine (UDVM), a Java Virtual Machine­hez hasonlítható, azzal a különbséggel, hogy  itt olyan utasítás készlet áll rendelkezésre, ami megkönnyíti és hatékonyabbá teszi a kitö­ mörítő algoritmusok implementálását. Ha jó az UDVM implementációja, akkor ezen a  virtuális gépen történő kitömörítés elenyésző mértékben lesz csak lassabb mintha azt egy  natív algoritmus végezné. Az UDVM használatával, egy kis kényelmetlenség árán (az  első üzenettel el kell küldeni a byte kódot), nagyon sokat nyerhetünk. Egyrészt minden  szolgáltató (értem ez alatt a telefonközpontokat, illetve a telefonokat és egyéb SIP eszkö­ zöket gyártó cégek), szabadon dönthet, hogy milyen tömörítő algoritmust alkalmaz, más­ részt ha az idők folyamán felfedeznek egy sokkal jobb hatásfokkal tömörítő algoritmust,  akkor azt rögtön tudják alkalmazni, nem kell például frissítőcsomagot írni a régebbi mo­ dellekhez.   Természetesen  ebben   az   esetben   a   régebbi   készülék   nem   lesz   képes   az   új  algoritmussal betömöríteni az üzeneteit, de minden további nélkül tudja dekódolni majd  az ezzel tömörítetteket. A SigComp ugyan nem követeli meg, de javasolja a szótár alapú tömörítő algoritmu­ sok használatát. Az általános célú szótár alapú tömörítő algoritmusok üres szótárral indul­ nak,   esetleg   még   tartalmazzák   az   ábécé   betűit,   és   csak   később,   a   tömörítés   előre  haladtával kerülnek bele a már betömörített szövegrészek. A SigComp a tömörítési arány  15

javítása érdekében speciálisan epít(het)i fel a szótárt. Létezik egy előre definiált SIP/SDP  [8] szótár (az SDP a  Session Description Protocolra utal [9], az is szöveges üzeneteket  használ,   és   annak   az   üzeneteit   is   tömöríthetjük   SigComp­al),   mely   a   SIP   és   az   SDP  kulcsszavait tartalmazza. Tömörítés előtt ezen előre definiált szótár tartalmával, valamint  a korábbi üzenetek elmentett részeivel építjük fel szótárunkat [10], így már kezdetben  találhatunk hosszú illeszkedéseket a tömörítendő üzenetben. A korábbi üzenetek, illetve  azok   részeinek   elmentését   és   lekérhetőségét   a  statehandler  biztosítja.   Az   elmentett  üzenetrészt pedig state­nek nevezzük. Az elnevezés egy kicsit zavaró lehet, hiszen egy  state nem más mint egy string néhány adattal kiegészítve (azonosító, prioritás stb.) A  kitömörítés sikeressége érdekében fontos, hogy mind a küldő, mind a fogadó oldalon  ugyanazok   a   state­ek   elérhetők   legyenek.  Küldő   oldalon   az   üzenet   betömörítése   után  elmenthetjük az új state­eket, fogadó oldalon pedig a felküldött kitömörítő algoritmus  byte kódjával tudjuk elérni, hogy ott is elmentődjenek a kívánt state­ek. Természetesen  nem feltételezhetjük, hogy egy üzenet minden esetben sértetlenül megérkezik a címzett­ hez, így nem mondthatjuk azt, hogy a kitömörítő algoritmusunk, majd biztosan elmenti a  megfelelő state­eket. Ezért minden state­hez bevezetünk egy ack logikai értéket, és tömö­ rítés előtt a szótár építésénél csak azokat a state­eket vesszük figyelembe, amelyek ack  értéke igaz. A tömörítés után elmentendő state­ek ack értéke hamis. Ha a fogadó oldal ki  tudta tömöríteni az üzenetet, akkor ő is elmenti a kívánt state­eket, igaz ack értékkel –  hiszen ezeket a küldő oldalon már eltároltuk –, és egy feedback rekordban elmenti az  azonosítóikat. Amikor majd a fogadó oldal küld vissza egy üzenetet a küldő oldalnak,  akkor elküldi ezt a feedback rekordot is, jelezve ezzel, hogy nála is rendelkezésre állnak  ezek a state­ek. Így a küldő oldal a következő üzenet tömörítéséhez már fel tudja őket  használni.   Arra   is   figyelni   kell,   hogy   mindkét   helyen   a   szótárépítésnél   ugyanolyan  sorrendben használjuk fel őket.  A telefonközpont egy időben több telefonnal is kommunikál. Ezért a statehandler min­ den session­höz létrehoz egy tárterületet (Compartment), ahol az oda tartozó state­eket  tárolja. Minden Compartment­hez saját tömörítő stratégia tartozik. Azaz egy telefonköz­ pont egy időben a különböző telefonoknak küldött SIP üzeneteit különböző algoritmusok­ kal tömörítheti be. Előfordulhat,   hogy   a   fogadó   oldal   valami   okból   nem   tudja   kitömöríteni   a   kapott  üzenetet. Ennek számos oka lehet: nincs meg neki a kitömörítő algoritmus byte kódja,  nem talál meg egy szükséges state­et, vagy meghibásodott az üzenet stb. Ekkor nemcsak  egy egyszerű hibajelzést küld vissza, hanem megmondja azt is, hogy mi volt az. Ezt a  mechanizmust Negative Acknowladgement­nek (Nack) [11] hívjuk. 

16

4.1.   A SigComp üzenet felépítése A SigComp üzenetet kétféle módon építhetjük fel. (3. ábra)

3. ábra

Mindkét   típusú   üzenetben   az   alacsonyabb   téglalap   pontosan   egy   byte­ot   jelent,   a  magasabb pedig többet. (A pontos értéket a többi adatból határozhatjuk meg.) Mindkét  típusú üzenetnek az első 5 bitje 1­es. Ez azért van, mert nincs olyan unikódú karakter,  ami szintén így kezdődne, ezáltal könnyen meg tudjuk különböztetni a tömörített és a  nem tömörített üzeneteket. Az első típusú üzenet nem tartalmaz byte kódot, csak egy  hivatkozást rá. A partial state identifier mező tartalmazza a byte kód azonosítóját. A len  mező megadja a partial state identifier mező értékét, az alábbi módon: len mező értéke            partiel state identifier mező hossza 1 6 2 9 3 12

17

A második típusban a len mező értéke 0. A 12 bites  code_len  mező mondja meg, a  feltöltött byte kód hosszát, a  destination mező azt az UDVM memória címet adja meg,  ahonnan kezdődik a byte kód helye. Az  uploaded UDVM bytecode  mező pedig a byte  kódot   tartalmazza.  A  remaining   SigComp   message  tartalmazza  a   tényleges  tömörített  üzenetet és a kitömörítéshez szükséges state­ek azonosítóit. A T bit mondja meg, hogy  van­e  feedback adat.  Ha  a  T  bit  0,  akkor  a  returned  feedback item  mező hiányzik  a  SigComp üzenetből. Ha a T bit 1, akkor a returned feedback item kétféle lehet.  (4. ábra)

4. ábra

Az első típus egy egy byte hosszú feedback­et jelöl, a második esetben pedig az első  byte megadja a feedback hosszát, majd ezután jön a tényleges adat.

4.2.   A SigComp architektúrális felépítése A SigComp két kommunikációs végpont közötti adatforgalmat bonyolít le. Amint ezt az  5.   ábrán   is   láthatjuk,   az   alkalmazási   és   a   szállítási   réteg   között   helyezkedik   el.   Az  alkalmazástól kapott üzenetet betömöríti, majd tovább adja a szállítási rétegnek, amely az  üzenet célba juttatásáért felel. A szállítási réteg alkalmazhat TPC és UDP protokollt is.  Ha  üzenet érkezik, akkor a szállítási  réteg átadja azt a SigComp­nak, majd annak az  UDVM­je kitömöríti azt, és tovább adja az alkalmazásnak. 

18

5. ábra

4.2.1.   Compressor dispatcher A comressor dispatcher egy interfész az alkalmazás felé. Az alkalmazás ezen keresztül  tudja   tömörítve   elküldeni   az   üzenetet.   Üzenetet   fogad   az   alkalmazástól,   majd   ezt   a  compartment identifier alapján továbbítja a megfelelő compressor objektumnak, valamint  a kész SigComp üzenetet átveszi a tőle, és átadja azt a szállítási rétegnek.

19

4.2.2.   Compressor Feladata   az   üzenetek   betömörítése   és   azok   SigComp   formátumra   alakítása.   Minden  session­höz   tartozik   egy   compartment,   és   minden   compartment­nek   saját   compressor  objektuma van. Így a telefonközpont a különböző készülékekkel kommunikálva, külön­ böző algoritmusokkal tömörítheti be az üzeneteket. (pl. LZSS, Huffman, Deflate stb.)  Természetesen az is előfordulhat, hogy minden compartmenthez ugyanaz a compressor  osztály egy­egy példánya tartozik. A compressor objektum feladata, hogy a tömörítés  során (végén) a kívánt üzenetrészeket elmentesse a statehandler­rel. A tömörítő algorit­ musokat egy későbbi fejezetben részletezem.

4.2.3.   Decompressor dispatcher A   decompressor   dispatcher   interfész   a   szállítási   réteg   és   az   alkalmazás   között.   A  megérkezett SigComp üzenetet a szállítási réteg a decompressor dispatcher­nek adja. A  decompressor dispatcher létrehozza az UDVM osztály egy új példányát. (Minden egyes  kitömörítéshez, új UDVM objektumot hoz létre. Ennek biztonságtechnikai okai vannak.)  Az   üzenetet   kitömörítteti   az   UDVM­mel,   majd   átadja   azt   az   alkalmazásnak.   Ha   az  alkalmazás engedélyezi a state­ek elmentését, akkor az visszaküldi azt a compartment  azonosítót, amelyik az aktuális session­höz tartozik, így a decompressor  el tudja menteni  a state­eket.

4.2.4.   Decompressor (UDVM) A   decompressor   feladata,   hogy   kitömörítse   az   üzenetet,   majd   azt   visszaadja   a  decompressor   dispatcher­nek.   A   kitömörítés   során   csak   a   megadott   decompression  memóriával gazdálkodhatunk. A szabvány minimum 2 kilobyte memóriát ír elő, de az  implementációtól függően ez akár 64 kilobyte is lehet. Ebben a memóriában tároljuk le a  kapott   tömörített   üzenetet,   és   itt   hagyunk   helyet   a   feedback­nek   is.   A   fennmaradó  memória áll az UDVM rendelkezésre. Az UDVM memória  szó  szervezésű. Az első 32  byte­on   az   UDVM   beállításokat   tároljuk,   utána   jön   maga   az   UDVM   byte   kód,   és   a  fennmaradó terület cirkuláris bufferként a szótárt tartalmazza. Az első 32 byte felépítését  az 6. ábra mutatja. A fejlécben a bitek sorrendje szerepel, a táblázat jobb oldalán pedig  az, hogy az adott mező melyik byte­okon foglal helyet.

20

6. ábra

A mezők magyarázata: UDVM_memory_size:

megadja, a rendelkezésre álló udvm memória méretét.

Cycles_per_bit:  azt   határozza   meg,   hogy   egy   bit   üzenet   kitömörítéséhez  legfeljebb hány UDVM ciklus áll rendelkezésre. Minden UDVM utasítás végrehajtása  valamennyi UDVM ciklus ideig tart. Hasonlóan a gépi kódú utasítások végrehajtásához,  de   ez   csak   egy   logikai   érték,   a   műveletek   költségét   fejezi   ki,   és   biztonságtechnikai  okokból kerültek bevezetésre. Ugyanis rosszindulatú felhasználó elküldhet nekünk egy  olyan üzenetet, ahol a  „kitömörítő”  algoritmusban végtelen ciklus van. Ha nem lenne  limitálva, az üzenet kitömörítésére felhasználható UDVM ciklus, akkor ilyen eszközökkel  meg   lehetne bénítani  a telefonközpontot. A szabvány szerint minimum  16 kell, hogy  legyen az értéke. SigComp_version:

az aktális SigComp verzió számát adja.

Partial_state_ID_length:

megadja, hogy a byte kódot tartalmazó state 20 byte­os  azonosítójából hány byte­ot használunk. (Minimum a 6.)

State_length: 

a byte kódot tartalmazó state hosszát adja meg.

Reserved: 

későbbi fejlesztésekhez fenntartott. Az értéke most 0.

21

Az UDVM nyelv 36 utasításból áll (1. táblázat). Vegyesen fordulnak elő alacsony illetve  magas szintű utasítások. Utasítás neve

Byte kódja

DECOMPRESSION­FAILURE

0

AND

1

OR

2

NOT

3

LSHIFT

4

RSHIFT

5

ADD

6

SUBTRACT

7

MULTIPLY

8

DIVIDE

9

REMAINDER

10

SORT­ASCENDING

11

SORT­DESCENDING

12

SHA­1

13

LOAD

14

MULTILOAD

15

PUSH

16

POP

17

COPY

18

COPY­LITERAL

19

COPY­OFFSET

20

MEMSET

21

JUMP

22

COMPARE

23

CALL

24

RETURN

25

SWITCH

26

CRC

27

INPUT­BYTES

28

22

Utasítás neve

Byte kódja

INPUT­BITS

29

INPUT­HUFFMAN

30

STATE­ACCESS

31

STATE­CREATE

32

STATE­FREE

33

OUTPUT

34

END­MESSAGE

35

1. táblázat

Az   utasítások   argumentumai   négyfélék   és   1,   2   vagy   3   byte   hosszúak   lehetnek.   Az  argumentumokat kódolt formában tároljuk, hogy a gyakran használt értékek kevesebb  helyet foglaljanak. ●

Literal (#): Byte kód 0nnnnnnn 10nnnnnn­nnnnnnnn 11000000­nnnnnnnn­nnnnnnnn

●

intervallum 0­127 0­16383 0­65535

argumentum értéke memory[2*N] memory[2*N] memory[N]

intervallum 0­127 0­16383 0­65535

Reference ($): Byte kód 0nnnnnnn 10nnnnnn­nnnnnnnn 11000000­nnnnnnnn­nnnnnnnn

●

argumentum értéke N N N

Multitype (%) lehet literal illetve reference is:  Byte kód 00nnnnnn 01nnnnnn 1000011n 10001nnn 111nnnnn 1001nnnn nnnnnnnn 101nnnnn nnnnnnnn 110nnnnn nnnnnnnn 10000000 nnnnnnnn nnnnnnnn 10000001 nnnnnnnn nnnnnnnn

argumentum értéke N memory[2*N] 2(N+6)  2(N+6)  N+65504 N+61440 N memory[N] N memory[N] 23

intervallum 0­63 0­65535 128, 256 256, ..., 32768 65504­65535 61440­65535 0­8191 0­65535 0­65535 0­65535

●

Address (@): Hasonlóan kódoljuk, mint a multitype­ot. A különbség annyi, hogy ebben az esetben a  tényleges   érték   az   argumentum   értéke   +   az   aktuális   utasítás   címe   modulo   65536.  Address típusú argumentumai a vezérlő utasításoknak vannak, ezzel biztosítva, hogy a  kód független legyen a tényleges helyétől az UDVM memóriában.

A 7. ábrán láthatjuk, hogy az UDVM milyen módon kommunikál a környezetével.

7. ábra

4.2.5.   Statehandler A Statehandler vezérli a state­műveleteket (mentés, keresés, törlés). Minden session­höz  tartozik egy compartment, amiben az oda vonatkozó state­eket tároljuk. Ezeken felül egy  különálló   compartmentben   tároljuk   a   lokális   state­eket,   például   a   SIP/SDP   szótárt,  amelyet minden session­ből el  lehet érni.  A compartmentekhez meghatározott méretű  memória   tartozik   (általában   8   Kilobyte).   Minden   state­hez   tartozik   egy   kétbyte­os  prioritás   érték,   ami   a   fontosságát   határozza   meg.   Minél   magasabb   ez   az   érték   annál  24

fontosabba a state. (A 65535 a ­1­nek felel meg.) Ha új state­et szeretnénk hozzáadni a  compartment­ünkhöz,  de  már  nincs  elég   szabad  memória,  akkor  a statehandler kidob  annyi régi state­et a legkisebb prioritásúak közül, hogy elférjen az új. Egy telefonközpont  egyszerre sok készülékkel kommunikálhat, így egy időben sok session lehet nyitva, ezért  sok   compartment­et   kell   kezelnie.   Gyakran   előfordulhat,   hogy   több   session­ben   zajló  kommunikáció ugyanazt a state elmentését indukálja, ezért, hogy ne pazaroljuk a fizikai  memóriát javasolt a state­eket külön tárhelyen, egyszer eltárolni és a compartment­ekben  csak   hivatkozni   rájuk.   Természetesen   ilyenkor   az   összes   ide   vonatkozó   compartment  memóriáját csökkenteni kell a state méretével. A decompressor részben tárgyaltuk, hogy  a   kitömörítő   algoritmus   byte   kódját   is   el   kell   küldeni   az   első   üzenettel.   Ezután   ezt  elmentjük és később elég csak hivatkozni rá. Ezeket a byte kódokat is state­ként mentjük  el. A statehandler szempontjából ezek is ugyanolyan state­ek, mint bármely mások, így  ugyanazok a szabályok vonatkoznak rájuk is. Nekünk azonban szükségünk van a byte  kódra a session végéig, ezért célszerű a byte kód state­jének magasabb prioritást adni a  többi state­nél. A SigComp­ot a state­ek kezelése szerint az alábbi módon osztályozhatjuk: Stateless:  Statefull: Static:  Dynamic:  Shared:  

Extended: 

Nem használunk state­eket, minden üzenettel el kell küldenünk a byte  kódot. (Ezt a változatot a valóságban nem alkalmazzák.) Csak a byte kódot mentjük el state­ként, semmilyen más state­et nem  használunk. Statefull + rendelkezésünkre áll a SIP/SDP szótár. Static + a régebbi üzenetek bizonyos részeit is elmentjük. (Azt, hogy  melyik részeket kell elmenteni, a szabvány nem írja elő.) Static + a teljes régebbi üzenetet elmentjük. Szabvány szerint a shared  state­ek prioritásának 65535 (azaz ­1)­nek kell lennie, így ezek kerülnek ki  leghamarabb a statehandler­ből. Ezért általában csak mindig a legutolsónak  elküldött teljes üzenet áll rendelkezésünkre.  Dynamic + shared.

25

5.   Tömörítés A szabvány nem írja elő, hogy milyen algoritmus alapján tömörítsük be üzeneteinket, de  ajánlja, hogy valamilyen szótár alapú algoritmust válasszunk. Ebben a fejezetben néhány  lehetséges algoritmust [12] ismertetek.

5.1.   Rice algoritmus Ennél   az   algoritmusnál   a   szótár   kulcsszavakat   tartalmaz.   Kulcsszónak   számítanak   az  ábécé betűi, valamint a SIP/SDP bejegyzések és az esetleges előző üzenetek részei is.  Tömörítés   során   vesszük   az   üzenetnek   azt   a   leghosszabb   prefixét,   ami   kulcsszóként  szerepel a szótárban, majd helyettesítjük azt a szótárbeli pozíciójával. Ezután a maradék  üzenetre újra alkalmazzuk ezt az eljárást. Így kapunk egy számsorozatot. A számsorozat  elemeit pedig a következő módszerrel kódoljuk: Válasszunk ki egy k természetes számot.  Legyen a kódolandó szám  n, és  rendeljünk hozzá egy bitsorozatot. A  bitsorozat első  [n/2k] darab bitje 1 legyen, ezt kövesse egy 0, majd pedig az (n mod 2 k) szám bitjei. Pl.  legyen k=3 és n=21, ekkor az n­hez rendelt bitsorozat: 110101. A jó tömörítési arány  eléréséhez megfelelő k érték választása szükséges. Könnyű belátni, hogy a kis számokhoz rövidebb kódot rendelünk, míg a nagyokhoz  hosszabbat. Ezért nem mindegy, hogy melyik kulcsszó hol szerepel a szótárban. Célszerű  a gyakrabban használtakat a szótár elején elhelyezni. Ez nem univerzális megoldás, mert  előfordulhat olyan SIP üzenet is, amiben olyan szó szerepel sokszor, ami egyébként nem  gyakori.   Ilyen   esetben   nagyon   rossz   hatékonysággal   tudunk   csak   tömöríteni.   Jobb  megoldást   kapunk,   ha   nem   csak   az   átlagos   gyakoriságra   hagyatkozunk,   hanem   a  tömörítés során gyakrabban előforduló szavakat valamilyen heurisztika alapján előbbre  hozzuk. A kitömörítő algorimtust a pszeudo kódjának megadásával ismertetem: bseq : tömörített üzenet byte sorozata; tmp : byte; result : byte; amíg bseq != <> tmp := 0; amíg bseq.front() = 1 tmp := tmp + 1; bseq.popfront(); bseq.popfront(); //kiolvasom a 0 bitet; 26

result := tmp * 2k + bseq.front(k); KIÍR: a szótár result pozícióján levő kulcsszava; bseq.popfront(k);

5.2.   SubExponencial algoritmus Ez az algoritmus az előbb ismertetett Rice algoritmus egy variációja. Annyiban különbö­ zik az előzőtől, hogy az n­számhoz más módon rendeli hozzá a bitsorozatot. • •

Ha n < 2k akkor a bitsorozat egy 0 és utána az n, pontosan k bit hosszan.  Ha n ≥ 2k akkor a bitsorozat  log(n) ­ k + 1 darab 1­es majd egy 0­ás bit és az n alsó   log(n) darab bitje.

A kitömörítés során, ha 0 bitet olvasunk, akkor az ezután következő k bit adja a kívánt  byte   értékét.   Ha   1­et   olvasunk,   akkor   egy   kicsit   bonyolultabb   a   helyzet.   Legyen   a  következő 0­ig található 1­esek száma r. Ekkor a kívánt érték a 2 k*(r­1) + a 0 utáni r  darab bit által reprezentált kettes számrendszerbeli szám.

5.3.   Huffman algoritmus Hasonlóan   a   Rice   algoritmushoz,   a   szótár   kulcsszavai   ebben   az   esetben   is   az   ábécé  betűiből,  valamint   a SIP/SDP   bejegyzéseiből  és   az  esetleges előző  üzenetekből, vagy  azok részeiből áll. Az algoritmusnak négy lépése van: 1. A   tömörítendő   üzenetet   kulcsszavakra   bontjuk,   majd   megszámoljuk   azok   gya­ koriságát. 2. Felépítjük a Huffman­fát a gyakoriság értékek alapján. Minden levélbe egy kulcsszó  kerül. 3. Az üzenetet betömörítjük a Huffman­fa alapján.  4. Információkat   csatolunk   a   betömörített   üzenethez   a   fáról,   hogy   a   fogadó   oldalon  tudjunk kitömöríteni. Egy Huffman­fának több mint 600 levele is lehet, ezért a teljes fa csatolásával nagyon  rossz tömörítési arányt kapunk. Bizonyos megszorítások mellett el tudjuk érni, hogy a  fáról   semmilyen   információt  se   kelljen   elküldenünk,   mégis   ki   lehessen   tömöríteni   az  üzenetünket. Ha lemondunk arról, hogy a kulcsszavak közé vegyük az előző üzeneteket  vagy   azok   egyes   részeit,   valamint   előre  definiáljuk   a   kulcsszavak   gyakoriságértékeit,  akkor mindkét oldalon az üzenetektől függetlenül felépíthetjük a Huffman­fát. Ezt elég  egyszer   a   session   kezdetén   megtenni,   így   gyorsabb   lesz   a   ki­   és   betömörítés.   Az  27

üzenetben levő kulcsszavakat nem feltétlenül kell teljesen figyelmen kívül hagyni. Egy  másik megoldást kapunk, ha a fát ugyan a kezdetben definiált gyakoriságértékek alapján  építjük fel, de miután egy kulcsszót kódoltunk, megnöveljük annak a gyakoriságértékét,  és ha kell, átalakítjuk a fát is. Ennél a módszernél sem kell semmilyen fára vonatkozó  információt elküldeni az üzenettel. hiszen a kiinduló fa független az üzenettől, és miután  egy kulcsszóhoz tartozó kódot visszakódoltak, annak a gyakoriságát megnövelve, és ha  kell a fát módosítva azt konzisztens állapotban tudják tartani. E módszer hátrányai: Szükséges egy gyors algoritmus, amely a fa karbantartását végzi. • Ha nagy a fa, a gyakoriságszámok olyan nagyok lehetnek, hogy már nem férnek el két  byte­on. Az UDVM pedig kizárólag két byte­os változókat kezel, így saját aritmetikai  műveleteket kell megvalósítani, ami lassítja az algoritmust. • Ha nagy a fa, akkor az ritkán változik, így az átlagos esetben nem eredményez jobb  tömörítési arányt. A kitömörítés egyszerű. Olvassuk a betömörített üzenet bitjeit, 0 esetén balra, 1 esetén  jobbra   lépünk   a   Huffman­fában.   Amikor   elérünk   egy   levélhez,   akkor   kiírjuk   az   ott  található kulcsszót és visszaugrunk a gyökérbe. Ezt az eljárást addig ismételjük, amíg el  nem el nem olvastuk a teljes üzenetet. •

5.4.   LZ77 algoritmus Az algoritmus megkeresi a szótár leghosszabb részstringjét, amely illeszkedik a tömörí­ tendő üzenet elejére, majd a szótárbeli pozíció és illeszkedés hossz párossal helyettesíti  azt. A részstringet végül hozzáfűzi a szótár végéhez, így a következő üzenetrész betömö­ rítésében már az is részt vesz. Ha a tömörítendő üzenet első karaktere nem szerepel a szó­ tárban, akkor a pozíció 0 lesz, és a hossz helyett maga a karakter lesz a páros második  tagja. Példa az algoritmus működésére (2. táblázat): Szótár

Üzenet

(pozíció, hossz)

abcabcbbbbbbbbabc

(0,a)

a

bcabcbbbbbbbbabc

(0,b)

ab

cabcbbbbbbbbabc

(0,c)

abc

abcbbbbbbbbabc

(1,3)

abcabc

bbbbbbbbabc

(2,1)

abcabcb

bbbbbbbabc

(2,1) 28

Szótár

Üzenet

(pozíció, hossz)

abcabcbb

bbbbbbabc

(7,2)

abcabcbbbb

bbbbabc

(7,4)

abcabcbbbbbbbb

abc

(1,3)

abcabcbbbbbbbbabc 2. táblázat

Jobb eredmény kaphatunk, ha nemcsak a szótárban keressük az illeszkedést, hanem  magában az üzenetben is. Az egyértelmű kitömörítéshez azonban meg kell követelnünk,  hogy az illeszkedés első karaktere a szótárban legyen.  Nézzük az előző példát, az új módszerrel (3. táblázat): Szótár

Üzenet

(pozíció, hossz)

abcabcbbbbbbbbabc

(0,a)

a

bcabcbbbbbbbbabc

(0,b)

ab

cabcbbbbbbbbabc

(0,c)

abc

abcbbbbbbbbabc

(1,3)

abcabc

bbbbbbbbabc

(2,1)

abcabcb

bbbbbbbabc

(7,7)

abcabcbbbbbbbb

abc

(1,3)

abcabcbbbbbbbbabc 3. táblázat

Mint láthatjuk az első példában 9 párból áll a betömörített üzenet, a másodikban pedig  csak 7­ből. Gyakorlati szempontból fontos, hogy a párosok ábrázolása. Ha kevés biten ábrázoljuk  a pozíciót, akkor a szótár maximális mérete is kicsi lesz, ha a hosszt ábrázoljuk kevés  biten, akkor a hosszú egyezéseket csak több lépésben kódolhatjuk le. Azonban ha sok  biten tároljuk, akkor pedig a rövid illeszkedések kódolásakor biteket pazarlunk. A   kitömörítés   során,   ha   (0,   x)   párt   olvasunk,   akkor   egyszerűen   kiírjuk   az   x­et   és  hozzáadjuk   a   szótárhoz   is.   Ha   (n,   k)   párt   olvasunk   (n   >   0),   akkor   a   szótár   n­edik  29

pozíciójától kezdődően kiírunk k karaktert, majd a szótár végéhez adjuk. Ha a második  módszerrel tömörítettünk, és (n, k) párt olvasunk, akkor a kiírást és a szótár végéhez  csatolást karakterenként végezzük.

5.5.   LZSS algoritmus Az   LZ77   algoritmus   0,   illetve   1   hosszú   illeszkedés   esetén   is   egy   párost   tárol  el.   Ez  pazarlás, különösen ha az üzenetben sokszor fordul elő ilyen eset. Az LZSS algoritmus  más utat választ. Egy 1­es bit­tel jelzi, hogy a következő kódolt rész egy pozíció–hossz  páros, egy 0­ás bit­tel pedig, ha az egy karakter. Az LZSS algoritmus átlagosan jobb  tömörítési arányt ér el mint az LZ77 [13].

5.6.   Deflate algoritmus Ez az algoritmus az LZSS, a Sub exponential és a Huffman algoritmus házasságából szár­ mazik. Először az üzenetet az LZSS algoritmussal tömörítjük. Ebben a betömörített üze­ netben vannak olyan karakterek, amelyeket nem tömörítettünk mert vagy nem szerepeltek  a szótárban, vagy túl rövid volt az illeszkedés. A második lépésben ezeket a karaktereket,  valamint a speciális karaktereket és a hossz értékeket Sub exponential algoritmussal, a  pozíció felső byte­ját pedig Huffman algoritmussal tömörítjük. A pozíció alsó byte­ját  változatlanul hagyjuk. Kitömörítéskor az ezen algoritmusoknál ismertetett dekódolási módszereket alkalmaz­ zuk a megfelelő sorrendben.

30

6.   A match függvény Az LZSS kódolás esetén a match függvény keresi meg a szótár azon pozícióját, ahonnan  a leghosszabb illeszkedés kezdődik a betömörítendő szöveg elejére. A visszatérési értéke  pedig a pozíció–hossz páros. A tömörítés hatékonysága nagyban függ a match függvény  megvalósításától.   Ezért   az   alábbiakban   megvizsgáljuk   [14],   hogy   milyen   megoldások  közül   választhatunk  a   match  fügvény   implementálásához.  A   másik   kritikus   pontja  az  algoritmusnak, a betömörített szónak a szótárba való beírása. Ez mint később láthatjuk,  nem feltétlenül csak egy k karakter hosszúságú string másolása.

6.1.   A naiv megoldás Indítunk egy maximum keresést a szótár elemeire, ahol egy elem értéke az lesz, hogy  attól a ponttól kezdve milyen hosszú illeszkedés található a szótárban. Az illeszkedés  hosszát egy számlálással meg tudjuk határozni, ahol a feltétel az, hogy a szótár aktuális  eleme megegyezik­e a megfelelő üzenetbeli elemmel. Legyen a szótár hossza m. Ekkor a  maximum keresés m összehasonlításból áll, a számlálás pedig legfeljebb k + 1­ből. (Ahol  k a lehető leghosszabb illeszkedés.) Az üzenetrész szótárba írása legfeljebb k értékadás.  Azt kapjuk tehát, hogy egy üzenetrész betömörítése legrosszabb esetben O(m(k+1)+k)

6.2.   Knuth Morris Pratt algoritmusa Induljunk ki most abból, hogy pontosan k karakter hosszú szöveget (a betömörítendő  üzenet soron következő k karaktere) kell megkeresnünk a szótárban. Nevezzük ezt mintá­ nak. A naiv megoldással a mintát a szótár elejére illesztjük és egy lineáris kereséssel  megkeressük az első nem egyező karakterpárt. Ha nem találunk ilyet, akkor készen va­ gyunk (megvan az illeszkedés helye), ha találunk, akkor a szótárban visszalépünk a kiin­ dulási + 1 pozícióra és a mintát arra illesztve újból indítjuk a lineáris keresést. Ezt addig  ismételjük , amíg vagy nem találunk illeszkedést, vagy a szótár végére nem érünk. Ez a  módszer azért nem hatékony, mert például ha a 15. karakternél romlik el az illeszkedés,  akkor 14 pozíciót vissza kell lépnünk a szótárban. Hatékonyabb megoldás a Knuth Morris és Pratt (KMP) mintaillesztő algoritmusa. Ez  az algoritmus is a lineáris keresésen alapszik, de lényegesen hatékonyabb annál. A mintát  az illesztés előtt feldolgozza, és minden pozíciójához meghatároz egy értéket, hogy ha ott  romlik   el   az   illeszkedés,   akkor   a   mintában   melyik   pozíciójára   kell   ugrani,   hogy  folytathassuk az illeszkedés vizsgálatát, anélkül, hogy visszalépnénk a szótárban. Így az  algoritmus   garantálja,  hogy  a   műveletigénye  legrosszabb   esetben   is   O(m+k)   lesz.  Az 

31

algoritmust   könnyen   módosíthatjuk   úgy,   hogy   ne   csak   a   pontosan   k   karakter  hosszú  illeszkedést   találja   meg,   hanem   ha   nincs   olyan,   akkor   a   leghosszabb   k   karakternél  rövidebbet is. 

A módosított algoritmus A  next  tömbben tároljuk, hogy mennyit ugorhatunk a szótárban, ha nincs egyezés,  N  a  szótár hossza, s a szótárt, m a mintát reprezentáló tömb (1­től kezdődően indexeljük). A  max  és  maxpos  változókban   tároljuk,   hogy   mennyi   és   hol   volt   eddig   a   leghosszabb  illeszkedés. Knuth­Morris­Pratt Initnext i,j,max,maxpos,cnt := 0,0,0,0,0 Ciklus amíg i
kereséses módszer.  A   betömörített  üzenetrészt ennél  az algoritmusnál  is  elegendő a szótárba írni, ami  csupán k értékadás. Más feladatunk nincs, ezért egy üzenetrész betömörítése legrosszabb  esetben is O(m+k+k).

6.3.   Láncolt lista Az ábécé minden betűjéhez hozzárendelünk egy listát, amiben nyilvántartjuk, hogy az  adott betű a szótár mely pozícióin fordul elő. Ezután megnézzük, hogy mi a kezdőbetűje  a betömörítésre váró üzenetnek. A leghosszabb illeszkedést a szótár csak azon pozícióitól  nézzük,   melyek   szerepelnek   a   listában.   Egy   üzenetrész   betömörítése   a   legrosszabb  esetben   O(m*k).   Ez   akkor   fordul   elő   például,   ha   a   szótár   csupa  „a”  betűből   áll,   a  tömörítendő üzenetrész pedig 15  „a”, majd egy a „b” betűből álló string. Azonban mi  szöveges  üzeneteket tömörítünk,   amelyekben nagyon  ritkán  fordul   elő  a  fent   említett  szélsőséges eset, hogy egy bizonyos karakter lényegesen többször fordul elő mint a többi,  ezért általában sokkal jobb eredményt tud elérni ez a módszer a naiv megoldásnál. Egy  kis  módosítással   hatékonyabb  megoldást  kaphatunk  az  egyszerű  láncolt  listás  módszernél.   Az   ötlet   az,   hogy   ne   csak   az   ábécé   egy­egy   betűjéhez,   hanem   minden  lehetséges betűpárhoz rendeljünk egy­egy listát. A listákban azon pozíciók szerepeljenek,  amilyeneken az adott betűpár található a szótárban. Legyen az ábécé elemeinek száma q.  Mivel   ezzel   a   módszerrel   nem   q,   hanem   q2  listánk   lesz,   így   azok   hossza   bizonyos  szélsőséges   esetek   kivételével   (melyeknek   rendkívül   kicsi   a   valószínűsége   szöveges  üzeneteknél) sokkal rövidebb lesz az előző változathoz képest. Hasonlóan   a   betűpárokhoz   tartozó   listás   megoldáshoz,   alkalmazhatjuk   a   módszert  betűhármasokra, betűnégyesekre stb. Azonban minden listához (az üresekhez is) legalább  egy kezdő pointer tartozik. Így a betűk számának növekedésével, exponenciálisan nő a  memóriaigény. A másik probléma pedig az, hogy a láncolt listás módszernél már nem  elég a betömörített szövegrészt beírni a szótárba, hanem a listákat is konzisztens módon  kell változtatni. Mivel a szótárunk cirkuláris buffer, ezért, ha betelik, akkor az elejétől  folytatjuk   az   üzenetrész   beírását,   felülírva   az   ott   szereplő   adatot.   Minden   betű   két  betűpároshoz, három betűhármashoz stb. tartozik, melyek a felülírással megváltoznak. A  megváltozott   betű   n­esek   kezdőpozícióját   a   régi   betű   n­eshez   tartozó   listából   át   kell  helyezni   az   új   betű   n­est   tartalmazó   listába.   Ez   a   művelet   annál   bonyolultabb   minél  nagyobb betű n­esekkel dolgozunk.

6.4.   Hash tábla Ez a módszer a láncolt listás megoldás továbbgondolása. Készítünk egy­egy hash táblát a  33

szótár 1, 2, 4 és 8 hosszúságú részstringjeihez, amelyekben a kulcsok ezen részstringek  (illetve azok az egész számok, amelyeket a hash függvény ezen részstringekhez rendel), a  tábla adatai pedig a szótárbéli előfordulásai lesznek. A 8­nál hosszabb részstringekkel  már nem érdemes foglalkoznunk, ugyanis a az angol szövegben az átlagos illeszkedés 4  karakter. A SIP üzemetek pedig az angol szövegre hasonlítanak.  A leghosszabb illeszkedést a következő módon keressük meg. Először megnézzük,  hogy a tömörítendő üzenet első karaktere benne van­e a szótárban. Azaz az 1 hosszú  részstringek hash táblájában megnézzük, hogy tartozik­e hozzá érték. Ha nem, akkor a  betű nem szerepel a szótárban, így 0 hosszú az illeszkedés. Ha igen, akkor vizsgáljuk a 2,  4,   majd   a   8   hosszú   részstringekhez   tartozó   hash   táblákat.   Ha   valamelyik   lépésnél  elakadunk,   akkor   az   előző   lépéshez   tartozó   pozícióktól   keressük   a   leghosszabb  illeszkedést. Ugyan kicsi az esélye, de előfordulhat, hogy a hash függvény két különböző  részstringhez   is   ugyanazt   a   kulcsot   rendeli,   ezért   az   illeszkedés   vizsgálatot   mindig   a  betömörítendő üzenet első karakterétől kell kezdeni. A   hash   tábla   alkalmazásával   megtartottuk   a   láncolt   listás   megoldás   előnyét,   és  kiküszöböltük a hatalmas memóriaigényt, ugyanis a hash táblában csak azon karakter  n­esek szerepelnek amelyek egyébként is benne vannak a szótárban, így egy hash tábla  pontosan szótárhossznyi bejegyzést tartalmaz. A hash táblát is, hasonlóan a láncolt listákhoz, konzisztens módon kell módosítani a  betömörített szöveg szótárba írásakor.

34

7.   Az LZSS algoritmus alkalmazása A SigComp compressor részének implementálásához az LZSS algoritmust választottuk,  ugyanis  [12]   alapján  azt  tapasztaltuk, hogy  minden előzőekben  ismertetett   algoritmus  átlagosan ugyanolyan arányban tömörítette a SIP üzeneteket,1 de az LZSS algoritmusnak  az UDVM kitömörítője háromszor gyorsabb volt. A szótárt cirkuláris bufferrel valósítottuk meg. Ez annyit tesz, hogy ha egy szónak a  szótárba írása során elérjük a szótár végét, akkor a beírást a szótár elejétől folytatjuk, fe­ lülírva az ott szereplő bejegyzéseket. A szótár mérete függ a kitömörítéshez felhasználha­ tó memóriától, az üzenet hosszától és egyéb dolgoktól, de nem lehet nagyobb mint 2048  byte. Ez a megszorítás azért kell, hogy a pozíció tárolásához elég legyen 12 bit. A hatéko­ nyabb tömörítés érdekében nem üres szótárral indítjuk az algoritmust. Először a SIP/SDP  szótár   legnagyobb   prioritású   szeletét   tesszük   a   szótárba,   majd   a  dynamic  és  shared  state­ek következnek (prioritásuk szerint csökkenő sorrendben, amennyi közülük belefér)  és legvégül, ha marad hely a SIP/SDP szótár többi része, szintén prioritásuk csökkenő  sorrendjében. A szótárépítés során még nem használjuk ki, hogy cirkuláris a bufferünk,  azaz ha betelik a szótár akkor leállunk a feltöltéssel. Azok a state­ek és a SIP/SDP részek,  amelyek kimaradnak, egyszerűen nem vesznek részt a tömörítésben. A leghosszabb illeszkedést 16 karakterben maximalizáltuk, aminek tárolásához elég 4  bit. Ez nem okoz lényeges hatékonyság csökkenést, ugyanis [14] mérései alapján kiderül,  hogy egy angol nyelvű szövegben, LZSS algoritmussal való tömörítéskor átlagosan 4  karakter hosszú illeszkedések találhatóak. Így a pozíció–hossz párokat két byte­on tudjuk  tárolni.   Ehhez   még   hozzá   adódik   az   egy   bit   jelzőbit,   ami   megadja,   hogy   egy   kódolt  üzenet, hossz pár következik vagy pedig egy kódolatlan karakter. A mi megvalósításunkban, a tömörítéskor csak a szótárban keressük az illesztést, a  még betömörítésre váró üzenetet nem csatoljuk a szótár végéhez. Ezáltal egyszerűsödik a  be­ és kitömörítő algoritmus. A lényeg a kitömörítő  algoritmus egyszerűsödésén van,  hiszen   ezáltal,   rövidebb   lesz   a   byte   kód,   így   az   első   üzenetünk   is   (ugyanis   az   első  üzenettel el kell küldenünk a kitömörítő algoritmus byte kódját is), és a kitömörítés futási  ideje is jobb lesz. Ezt az egyszerűsítést megtehetjük, mert a SIP üzenet szavaiban nagyon  ritkán találhatók ismétlődő részstringek, és ezért a bonyolultabb módszerrel sem kapnánk  jobb tömörítési arányt. Ezt az állítást a 8.2 fejezet mérési eredményeivel tudom igazolni. A   szótárt   cirkuláris   bufferrel   valósítottuk   meg,   de   az   illeszkedéskereséskor,   nem  használjuk ki cirkuláris voltát. Azaz tegyük fel, hogy az előző lépésben az „abc” értéket  úgy adtuk hozzá a szótárhoz, hogy az „ab” a sor végére, a „c” pedig az elejére került,  1 Extended tömörítés alkalmazásakor

35

ekkor,   ha   a   tömörítendő   üzenet   is   „abc”­vel   kezdődik,   nem   találunk   (sorvége­2,3)  illeszkedéspárost. Ez szintén nem okoz problémát, mert egyrészt nem tudjuk, hogy mi  lesz   a   tömörítendő   üzenet   következő   része,   és   akár   úgy   is   kialakulhat,   hogy   ezzel   a  módszerrel kapunk jobb tömörítési eredményt (8. ábra), másrészt a cirkuláris bufferünk  mérete általában alig kisebb mint a betömörítendő üzenetek hossza, így a fent vázolt  probléma csak nagyon ritkán fordul elő. 

8. ábra

36

7.1.   Match függvény az algoritmusunkhoz Az első implementációnál a naiv módszert alkalmaztuk. Ez kezdetben, amíg az alrendszer  funkcionális   helyességét   vizsgáltuk   megfelelő   volt,   valamint   a   későbbi   változatokhoz  összehasonlítási alapot adott. Azonban nyilvánvaló volt, hogy a végleges változatban en­ nél hatékonyabb megoldást kell adnunk. A következő lépésben a 6. fejezetben ismertetett  módszereket vizsgáltuk meg, hogy melyik lenne a legmegfelelőbb a mi esetünkben.

7.1.1.   A hash táblás megoldás A Knuth­Morris­Pratt módszerét [14] alapján elvetettük. A láncolt listás megoldás jónak  tűnt, de a memória igénye miatt helyette a hash táblás megoldást választottuk, egy kis  módosítással. A hash táblát láncolt listával valósítottuk meg [15], azaz volt egy M hosszú  vektorunk a kulcsoknak, és a vektor elemei láncolt listák voltak, amelyek tartalmazták a  kulcshoz tartozó értékeket (9. ábra).

9. ábra

Az eredeti módszerhez képest mi csak a kettő hosszúságú részstringekhez tartozó hash  táblát építettük fel, és az itt tárolt pozícióktól számlálással néztük meg a leghosszabb  egyezést. (A feltétel megegyezett, a naiv módszernél alkalmazott számlálás feltételével.)  Ha egy betűpárhoz nincs érték a hash táblában, azaz legfeljebb egy hosszú illeszkedés  lehet a szótárban, akkor nem nézzük meg, hogy az az egy hosszú illeszkedés létezik­e,  hanem nem létezőnek tekintjük. Ez azért nem okoz problémát, mert a tömörítés során  37

csak az egynél hosszabb illeszkedéseket tömörítjük. Az M értékét Knuth ötlete alapján  [15] 701­nek határoztuk meg. A hash függvényünk a h = 256 * ASCII(első_betű) + ASCII(második_betű) mod M lett. Azt is figyelembe kellett venni, hogy egy pozíción az  illeszkedés   hossza   lehet   nulla   is,   mert   a   hash   függvény   több   betűpároshoz   is  hozzárendelheti   ugyanazt   a   kulcsot.   Ezzel   a   módszerrel   sajnos   nem   volt   elég   a  betömörített   üzenetrészt   bemásolni   a   szótár   végéhez,   hanem   a   6.1.3.   fejezetben  ismertetett módon a láncolt listákat is karban kellett tartanunk. Meglepődve tapasztaltuk, hogy ez a módszer háromszor lassabb eredményt produkált,  mint a naiv megoldás. Arra gondoltunk, hogy amit nyerünk a hash táblával a leghosszabb  illeszkedés megtalálásakor, azt hatványozottan elvesztjük a listáink karbantartásával. Ez  be is bizonyosodott, amikor a Valgrind nevű szoftver Callgrind moduljával elemeztük az  algoritmusunkat. Az elemzés módját részletesen ismertetem majd a következő fejezetben.  Ebből látható, hogy jó döntés volt, hogy nem az [14] megoldását követtük, azaz a négy  hash   tábla   (az   1,   2,   4,   8   hosszú   részstringeknek)   helyett   csak   egyet   (a   2   hosszú  résztringeknek) használtunk, hiszen a kritikus pontunk a hash tábla karbantartása lett.

7.1.2.   Hash tábla mátrixszal Nem vetettük el teljesen az előző módszerünket, hiszen a Callgrind elemzésével láttuk,  hogy   leghosszabb   illeszkedés   megtalálása   sokkal   gyorsabb   így,   mint   a   naiv   módszer  esetén.   Megpróbáltuk   növelni   a   szótárba   írás   hatékonyságát.   A   listaműveleteknél   a  keresés mellett az új listaelem allokálása és felszabadítása is igen költséges művelet volt,  ezért megpróbáltuk ezt kiküszöbölni. A hash táblát a vektor és listás megvalósítás helyett  egy  701 x  „elég nagy”  mátrixszal implementáltuk. A 701 az M értéke,  ami az előző  megoldásban a vektor hossza volt. Az „elég nagy” pedig egy akkora, hogy abban biztosan  elférjen az összes oda tartozó pozíció érték. Mivel ez csak egy köztes megoldás az „elég  nagy” konstans értéke lényegtelen.  Ezenfelül bevezettünk egy 701 elemű vektort, ahol az  i­edik pozíción azt tároltuk, hogy a mátrix i­edik sorában hány érték szerepel. Ezzel mátrixos megoldással kiváltottuk azt, hogy memóriaterületet kelljen allokálni,  amikor új értéket adunk hozzá az egyik kulcshoz, illetve fel kelljen szabadítani, amikor  kivesszük azt. A Callgrind elemzés kimutatta, hogy ezzel a módszerrel a tömörítési idő a  2/3­ra csökkent. Egy nagy hátránya ennek a megoldásnak az, hogy sokkal több memóriát  használunk fel mint amennyire feltétlenül szükség lenne. A későbbiekben megpróbáltuk  ezt is kiküszöbölni.

7.1.3.   A „reverse index” bevezetése A mátrixnak a listákkal szemben a memóriaműveletek kiküszöbölése mellett van még  38

egy   előnye,   mégpedig   az,   hogy   bármelyik   elemét   közvetlenül   meg   tudjuk   címezni.  Ezáltal elkerülhető az, hogy ha egy kulcshoz tartozó értéket ki szeretnénk törölni, akkor  egy   lineáris   kereséssel   kelljen   megkeresni   azt.   Bevezettünk   egy   reverse   index   nevű  tömböt, aminek elemszáma egyel kevesebb a szótár betűinek számánál. A tömb i­edik  pozícióján levő érték azt mondja meg, hogy a szótár i és, i + 1­edik pozícióján levő  betűpárjához tartozó értéke, hányadik helyen van a mátrix megfelelő sorában. Lássunk  erről egy példát. (10. ábra)

10. ábra

Tegyük fel, hogy az ábrán félkövér betűvel szedett „bc” betűpárhoz tartozó értéket  szeretnénk   kitörölni   a   hash   táblánkból.   Az   értéket   tudjuk,   hogy   5,   hiszen   ez   a   „bc”  szótárbeli pozíciója. Először a hash függvényünkkel kiszámoljuk, hogy a „bc” betűpárhoz  milyen   kulcs   tartozik.   Legyen   ez   ezúttal   a   2.   Ahelyett,   hogy   most   végignéznénk   a  mátrixunk második sorát, az 5­ös  értékű elemét keresve, megnézzük, a reverse index  tömbünk ötödik elemét, és ott látjuk, hogy a mátrix második sorában a keresett érték a  második   indexű   helyen   van.   A   törlés   ezután   csak   abból   áll,   hogy   a   mátrix   második  sorának utolsó elemével (az index tömb második eleme mondja meg, hogy melyik az)  felülírjuk a másodikat és csökkentjük egyel az index tömb második elemét. A reverse  index tömbbel nem kell foglalkoznunk, mert csak akkor történik törlés a mátrixból, ha a  szótárban   egy   betűt   felülírtunk   egy   másikkal.   De   ekkor   a   törlést   rögtön   követi   egy 

39

beszúrás is, és a beszúrás során úgyis adunk értéket a tömb ezen indexű elemének.  A   beszúrás   sokkal   egyszerűbb,   mint   a   törlés.   Tegyük   fel,   hogy   a   szótár   i­edik  pozícióján változott meg a betű és az i, i+1 betűpárhoz tartozó pozícióértéket szeretnénk  beszúrni. Legyen k az a szám, amit a hash függvény rendelt hozzá a betűpárhoz. Ekkor  növeljük   egyel   az   index[k]   értékét,   a   mátrix   k­adik   sorának,   az   index[k]­adik   eleme  egyenlő lesz i­vel, és a reverse index i­edik eleme pedig egyenlő lesz index[k]­val. Ezzel   a   trükkel   sikerült   kiváltani   a   lineáris   keresést,   és   komoly   hatékonyságbeli  növekedést értünk el. Sikerült az algoritmus futási idejét harmadára csökkenteni, a naiv  megoldáshoz   képest.   A   memóriaigényünk   megint   nőtt   egy   kicsit.   Azonban   a   szótár  mérete nem lehet több 4 Kilobyte­nál, ezért a reverse index tömbünk sem lehet nagyobb  annál. Ezt a 4 Kilobyte memórianövekedést pedig bőven ellensúlyozza a felére csökkent  futási idő.

7.1.4.   Hash­elés 3 karakter hosszú részstringekkel Ugyan az előző megoldás már elfogadható eredményt produkált számunkra, de azért  megvizsgáltuk   azon  esetek   eredményeit  is,   amikor  nem   kettő,   hanem   három   karakter  hosszú   részstringekkel   dolgoztunk.   Ettől   a   módszertől   további   gyorsulást   vártunk,   a  tömörítési arány romlása mellet. A gyorsulást a 6.1.3 fejezetben ismertetett okok miatt  feltételeztük. A tömörítési  arány romlását pedig azért, mert ebben az esetben a kettő  hosszú illeszkedéseket nem találjuk meg. Egy kéthosszú illeszkedés kódja 17 bit (1 bit  jelzi, hogy kódolt üzenet jön, 12 bit a szótárbeli pozíció, és 4 bit a hossz), egy karakter  kódolatlanul pedig 9 bit (1 bit jelzi, hogy kódolatlan üzenet jön, majd 8 biten a karakter  ASCII kódja). Két karakter kódolatlanul való elküldése így 18 bit, ami egyel több, mintha  azt kódolva küldenénk el. Az eredmény meglepő volt. Ez a módszer alig lett gyorsabb az előzőnél, azonban a  betömörített   üzenet,   ha   csak   néhány   byte­al   is,   de   rövidebb   lett.   Az,   hogy   nem   lett  lényegesen gyorsabb, az annyira nem érdekes, mert ezzel a módszerrel bonyolultabb a  hash tábla karbantartása, ami elviszi a nyert időt. Annál izgalmasabb az, hogy rövidebb  lett az üzenet. Erre az lehet a magyarázat, hogy ha nem találunk legalább három hosszú  illeszkedést az üzenet aktuális betömörítendő részére, akkor nem tesszük be rögtön a két  következő karaktert kódolatlanul az elküldendő üzenetbe, hanem csak az elsőt. Ezután  pedig   újra   illeszkedést   keresünk,   és   ha   most   sem   találunk,   csak   akkor   tesszük   be   a  kódolatlanul a másodikat. De ha ekkor találunk illeszkedést, akkor előfordulhat az az  eset,   hogy   összességében   jobb   tömörítési   arányt   kapunk,   mintha   azt   a   két   karaktert  tömörítettük volna. Nézzünk meg erre egy példát:  Legyen a betömörítendő üzenet: aabcdef 40

A szótár tartalma: tabcdefaa Legyen az a helyzet, hogy a szótár cirkuláris volta miatt a következő beíráskor a „t”  karaktert írjuk felül. Először nézzük azt az esetet, amikor megtaláljuk a 2 karakter hosszú illeszkedést is.  (4. táblázat) üzenet

szótár

illeszkedés

szótárba kerül

aabcdef

tbcdefaa

(8,2)

aa

bcdef

aacdefaa

nincs

b

cdef

aabdefaa

nincs

c

def

aabcefaa

nincs

d

ef

aabcdfaa

nincs

e

f

aabcdeaa

nincs

f

aabcdefa 4. táblázat

A kódolt üzenet egy illeszkedést és öt kódolatlan betűt tartalmaz, aminek a hossza: 17 + 5*9 = 62 bit Most   nézzük   azt   az   esetet,   amikor   csak   a   legalább   3   karakter   hosszú   illeszkedést  találjuk meg. (5. táblázat) üzenet

szótár

illeszkedés

szótárba kerül

aabcdef

tbcdefaa

nincs

a

abcdef

abcdefaa

(1,6)

abcdef

aabcdefa 5. táblázat

A   kódolt   üzenet   most   egy   kódolatlan   betűt   és   egy   illeszkedést   tartalmaz,   aminek   hossza: 5 + 17 = 22 bit.

7.1.5.   A mátrix kiváltása speciális listákkal. Végül megpróbáltuk kiküszöbölni a mátrixos megoldás memória pazarlását hatékonyság  romlás nélkül. A megoldás kulcsa az volt, hogy amikor egy pozíció értéket kiveszünk egy  listából, akkor azt a következő lépésben úgy is beszúrjuk egy másikba. Ezért ezeket a  41

listaelemeket nem feltétlenük szükséges felszabadítani, majd újra allokálni, hanem elég  egyszerűen csak átfűzni a másik listába. A vektor elemeihez, ezért most nem külön álló  listákat rendeltünk hozzá, hanem egy speciális listákon alapuló adatszerkezetet. A reverse  index tömböt is megtartottuk, annyiban módosítva, hogy a mátrixbeli pozíció helyett,  most a megfelelő pozíciót reprezentáló listaelemre mutató mutatót tárol. Ezáltal a  listaelemek közvetlen elérése biztosítva maradt. A 11. ábrán láthatjuk az új  adatszerkezetet. Itt az egyszerűség kedvéért betűpárokhoz rendeltünk listákat.

11. ábra

Tegyük fel, hogy a szótárban az 5. pozíción levő b karaktert szeretnénk módosítani.  Ekkor a reverse index tömb 5. pozícióján találunk egy mutatót az 5. pozíciót reprezentáló  listaelemre. Ezt ki kell fűzni a "bc" stringhez tartozó listából. Mivel két irányú láncolt  listát alkalmazunk ezt, konstans időben megtehetjük. Ekkor felülírhatjuk a b karaktert. A  listaelemünk nem veszett el, hiszen a reverse index tömbben még mindig van rá mutató  mutató, így könnyen be tudjuk fűzni a megfelelő új listába. Mivel nem szükséges, hogy a  stringekhez tartozó listák rendezettek legyenek (hiszen sorrendtől függetlenül meg kell  vizsgálni azokon a pozíciókon a leghosszabb illeszkedést), ezért az új listaelemet a lista  42

elejére szúrjuk be. Ezt szintén konstans időben megtehetjük. A reverse index tömb pedig  a tömörítés alatt egyáltalán nem változik.  Ezzel a módszerrel egy hajszállal gyorsabb megoldást kaptunk mint a memóriapazarló  mátrixos megoldásnál. Ezt azzal magyarázzuk, hogy a mátrix esetében a revesre indexben  csak egy mátrixbeli pozíció érték volt, és utána még ki kellett számítani a megfelelő  mátrixelem címét, addig ez utóbbinál a reverse indexben már a konkrét listaelem címe  volt.

43

8.   Mérési eredmények A tömörítés hatékonyságának vizsgálatakor felhasználtunk egy  sipsequence.txt nevű  szöveges állományt, ami a második fejezetben található példához hasonló kommunikáció  24 SIP üzenetét tartalmazta. Erre az állományra sokat hivatkozunk a későbbiekben.

8.1.   Illeszkedés keresés Arra   próbáltunk   választ  kapni,   hogy  érdemes­e   azzal  bonyolítani   a  be­   és   kitömörítő  algoritmusunkat, hogy az illeszkedés vizsgálatát kiterjesszük az üzenet elejére, vagy csak  a szótárban keressük azt. Implementáltuk mindkét módszert, és static tömörítés mellett, a  sipsequence.txt állomány üzeneteit tömörítettük, majd megnéztük, hogy üzenetenként  mennyivel különbözik a tömörített üzenet hossza. Nem vettük figyelembe az első négy  üzenet tömörítési eredményét, hiszen azokban előfordulhatott a byte kód is. Ezenfelül  annyi   módosítást   végeztünk   a  sipsequence.txt  állományon,   hogy   a  hatodik  üzenet  végéhez hozzáfűztünk sok  „a” betűt, ezzel garantálva, hogy lesz olyan üzenet, aminek  egy része illeszkedik saját magára. Az 6. táblázatban látható a két módszer eredménye. A  táblázat első oszlopa az üzenet sorszámát, a második az eredeti hosszát, a harmadik és  negyedik   a   betömörített   üzenet   hosszát   tartalmazza  abban   az   esetben,   amikor   csak   a  szótárban kerestük az illeszkedést, illetve az üzenet elejére is kiterjesztettük azt. #

csak szótár

üzenet is

5

45,84%

45,84%

6

23,37%

23,11%

7

45,84%

45,84%

8

51,56%

51,56%

9

46,64%

46,64%

10

56,88%

56,88%

11

52,02%

52,02%

12

56,19%

56,19%

13

45,77%

45,77%

14

56,19%

56,19%

15

55,08%

55,08% 44

#

csak szótár

üzenet is

16

53,08%

53,08%

17

55,08%

55,08%

18

53,08%

53,08%

19

57,68%

57,68%

20

67,49%

67,49%

21

57,59%

57,59%

22

67,83%

67,83%

23

56,72%

56,72%

24

65,51%

65,51% 6. táblázat

Mint láthatjuk egyedül a mesterkélten módosított ötödik üzenetben van különbség a  két   módszer   között   és   ott   is   csak   minimális.   A   többi   SIP   üzenetet   mindkét   módszer  ugyanolyan hosszúra tömörítette be. Bátran állíthatjuk tehát, hogy fölösleges bonyolítani  az algoritmusunkat azzal, hogy az üzenet elején is keresse az illeszkedést.

8.2.   Teljesítménybeli különbség a match függvény megvalósításai   között. Írtunk   egy   tesztkörnyezetet,  amelyben  a  sipsequence.txt  üzeneteinek   betömörítésén  kívül nem csinálunk semmi mást. Implementáltuk a match függvényt a 7.1­es fejezetben  ismertetett módokon. Ezután a futtattuk a programunkat, és futását a Valgrind [16] nevű  szoftver Callgrind [17] moduljával elemeztük. Ez a szoftver megvalósít egy virtuális x86  számítógépet, és azon futtatja az elemezni kívánt programot, ezáltal lehetősége nyílik  különböző szempontok alapján kielemezni azt. A Valgrind csak a környezetet biztosítja,  az elemzést az alkalmazott modul végzi. A megfelelő modul választásával lehetőségünk  van memory leak­et keresnünk, kideríteni, hogy a programunk valahol nem megengedett  memória címet próbál­e elérni stb. A Callgrind modul azt  vizsgálja, hogy a program  függvényei   mennyi   ideig   futnak   (órajelben),   hány   x86   utasításból   állnak,   hányszor  kerülnek meghívásra a program futása során stb. Az alábbiakban megadom, hogy a kü­ lönböző match függvény megvalósítások mellett, hány órajel alatt sikerült végrehajtani a  tömörítést, ebből hány órajelet használt el a match függvény, az üzenetnek a szótárba  45

való beírására (copyToBuffer), a hash táblás módszernél hány órajel kellett egy kulcshoz  tartozó értéknek a hash táblából való kitörléséhez (remove), illetve a részstringhez a kulcs  hozzárendelésére (hash).  Csak   a   szignifikáns   függvények   futási   idejét   ismertetem.   Az   értékeket   százalékos  formában adom meg, a naiv tömörítést tekintve 100%­nak. Naiv módszer: tömörítés: match: copyToBuffer:

100% 92% 1%

Hash tábla mátrixszal: tömörítés: match: copyToBuffer: hash: remove:

57% 15% 5% 3% 28%

Hash tábla a reverse_index bevezetésével: tömörítés: 28% match: 14% copyToBuffer: 5% hash: 3% remove: 2% A mérési eredményekből látható, hogy a naiv módszer esetében a match függvény  futási ideje a kritikus, hiszen ez a teljes tömörítés idejének 92%­a. A copyToBuffer futási  ideje elenyésző, hiszen ebben az esetben nincs más dolgunk, csak a tömörített üzenetrészt  a   szótár   végére   írni.   A   mátrixos   megoldásnál   láthatjuk,   hogy   a   match   függvény  lényegesen gyorsabb lett. A copyToBuffer, ami a hash, illetve a remove függvényeket is  hívta   pedig valamennyit lassult. De azért így is sikerült a futási időt a naiv módszer  futási idejének 57%­ára lecsökkenteni. A reverse_index bevezetésével pedig a remove  függvény futási idejét tudtuk  drasztikusan, 28%­ról mindössze 2%­ra lecsökkenteni, s  ezáltal a teljes tömörítés futási idejét 57%­ról 28%­ra módosítani.

8.3.   Static, dynamic, shared és extended tömörítések Ebben az alfejezetben megvizsgáljuk, hogy hogyan változik a tömörítési arány, ha static,   dynamic, shared  és  extended tömörítéseket alkalmazunk. A tömörítés hatékonyságát a  46

sipsequence.txt mellett, számos más SIP üzenet váltást tároló állományon vizsgáljuk. 

Ezeknek  neve  scrNNNNN.txt  (ahol   az  NNNNN  egy  egyedi  szám).  Végül   megnézzük,  hogy   az   alrendszerünk   milyen   hatékonysággal   tömörítene,   ha   az   összes   állományban  található   üzenetváltások   mind   egy   kommunikációhoz   tartoznának.   Ezt   az  all.txt tartalmazza.   Ez   nem   mesterségesen   kreált   kérdés,   hiszen   a   valóságban   is   gyakran  előfordul olyan kommunikáció, amelyben számos üzenetváltásra kerül sor. A   9.   táblázat   tartalmazza   az   állomány   nevét,   az   állományban   található   üzenetek  hosszának összegét, valamint, azt hogy az állomány üzeneteit mekkorára tudtuk összessé­ gében betömöríteni static, shared, dynamic és extended tömörítéssel. Állomány

Static

Shared

Dynamic

Extended

sipsequence.txt

65,95%

51,64%

67,13%

57,69%

scr00131.txt

82,02%

67,22%

81,98%

71,42%

scr00142.txt

79,56%

64,40%

79,17%

68,15%

scr00215.txt

84,66%

84,76%

84,93%

84,99%

scr00222.txt

79,72%

63,00%

82,28%

71,90%

scr01131.txt

86,12%

69,60%

82,64%

73,76%

scr01142.txt

87,00%

70,76%

83,81%

74,74%

scr01215.txt

89,97%

85,67%

90,23%

86,90%

scr01222.txt

82,77%

67,33%

80,31%

74,69%

scr50131.txt

80,60%

66,16%

80,22%

70,09%

scr60131.txt

84,92%

71,44%

81,76%

74,84%

scr70131.txt

82,45%

67,53%

82,38%

71,74%

scr80131.txt

86,24%

69,71%

82,30%

101,04%

scr00002.txt

86,15%

86,15%

86,15%

86,15%

összesen

81,64%

68,40%

80,82%

72,88%

all.txt

58,96%

44,61%

80,32%

77,26%

9. táblázat

Az  összes  üzenetet figyelembe véve azt kaptuk  tehát, hogy a static  tömörítéssel  a  kommunikációban résztvevő adatmennyiség méretét 81 százalékra tudjuk lecsökkenteni,  shared­del   68­ra,   dynamic­kal   80­ra   és   extended­del   72­re.   Ami   meglepő,   hogy   a  dynamic tömörítés alig lett csak jobb a static­nál, és nem az extended lett a legjobb.  47

Dynamic state­ként az üzenet Via, From és To header értékeit mentjük el. Ez pedig az  üzenetváltások során csak akkor változik, ha az egyik végpont a kommunikáció során egy  cella tartományból áthalad egy másikba. Ez azért nem túl gyakori. Azonban ezeket az  adatokat minden üzenetváltás után elmentjük, state­ként, így ezek sokszorosan szerepel­ nek a statehandler­ben, kiszorítva az esetleges kisebb prioritású, de hasznos információ­ kat (pl. a régebbi shared state­eket). Ez lehet az oka, a dynamic tömörítés rossz szereplé­ sének. Az  all.txt  által reprezentált kommunikáció adatmennyiségét static és shared esetben  lényegesen jobb hatékonysággal tudtuk tömöríteni. A tömörítetlenhez képest 59, illetve  45 százalékra csökkentettük az elküldendő byte­ok számát. Azért tudtunk ilyen jelentős  eredményt   elérni,   mert   ebben   az   esetben   egy   kommunikációt   szimuláltunk,   így   csak  egyszer kerültek elküldésre a kitömörítő algoritmus byte kódjai, míg a másik esetben  minden állomány első üzenetei tartalmazták azokat. Ez a fontosabb eredmény számunkra,  mert a valóságban is általában hosszú kommunikáció zajlik. Vizsgáljuk   most   meg   az  extended  tömörítést   úgy,  hogy   a  dynamic  state­eket   csak  minden második, harmadik, negyedik, illetve ötödik üzenetváltás után mentjük el.  (10. táblázat)

Állomány

2.

3.

4.

5.

sipsequence.txt

54,67%

53,37%

53,26%

52,87%

scr00131.txt

69,14%

69,45%

68,24%

67,69%

scr00142.txt

66,02%

66,46%

65,21%

64,60%

scr00215.txt

85,17%

84,85%

84,88%

84,49%

scr00222.txt

67,01%

66,67%

65,32%

66,12%

scr01131.txt

71,82%

71,37%

70,64%

70,19%

scr01142.txt

72,78%

72,58%

71,82%

71,02%

scr01215.txt

86,01%

86,28%

85,78%

85,94%

scr01222.txt

70,01%

70,31%

68,91%

69,48%

scr50131.txt

67,87%

68,29%

67,04%

66,43%

scr60131.txt

72,81%

73,36%

72,51%

71,70%

scr70131.txt

69,46%

69,77%

68,55%

68,01%

scr80131.txt

71,53%

71,49%

70,75%

70,30%

scr00002.txt

86,15%

68,15%

86,15%

86,15%

48

Állomány

2.

3.

4.

5.

Összesen

70,45%

70,35%

69,51%

69,25%

all.txt

62,24%

59,74%

52,53%

51,86%

10. táblázat

Amint láthatjuk az extended tömörítés esetében minél kevesebbszer mentünk dynamic  state­et, annál hatékonyabban tömörítünk, és a tömörítési arány közelít a shared tömöríté­ si eredményéhez. Ezzel beláthatjuk, hogy a dynamic state­k elmentésére alkalmazott stra­ tégia nem jó. Egy jó stratégia megalkotása további kutatásokat igényel. 

8.4.   Összehasonlítás az ismert tömörítőkkel Ebben   a   fejezetben   az   általunk   implementált   tömörítő   algoritmust   hasonlítjuk   össze  néhány,   a   számítástechnikában   ismert   és   gyakran   használt   általános   célú   tömörítő  szoftverrel (zip, arj, rar).  Először olyan állományokat tömörítünk, amelyek több SIP üzenetet tartalmaznak. Az  állományok méretei: 10, 100, 200Kilobyte.   Ezeket az állományokat a SigComp nem  tudja tömöríteni, ugyanis nincs arra felkészítve, hogy ilyen nagy üzeneteket tömörítsen.  (Egy   SIP   üzenet   ritkán   nagyobb   1   Kilobyte­nál.)   Ezért   létrehoztunk   egy   olyan   teszt  alkalmazást,   ami   tetszőlegesen   nagy   állományt   képes   tömöríteni   a   SigComp­ban  alkalmazott   algoritmust   felhasználva.   Azonban   így   nem   vagyunk   képesek   eltárolni  információkat   az   előzőleg   tömörített   állományokból,   ezért   csak   a   SigComp   static  tömörítését tudjuk szimulálni. (11. táblázat) Másodszor a  sipsequence.txt állomány SIP üzeneteit külön­külön tömörítettük az  általános célú tömörítő szoftverekkel. Ebben az esetben a static mellett a shared tömörítés  adatait   is   meg   tudtuk   adni.   (A   dynamic   és   extended   tömörítés   eredményeit   az   előző  fejezetben ismertetett okok miatt kihagytam.)   A  sipsequence.txt első négy üzenetét  kihagytam a vizsgálatból, ugyanis azok tartalmazhatják a byte kódot is, ami torzítaná az  eredményt. (12. táblázat)

Méret

ZIP

ARJ

RAR

SigComp (static)

~ 10 Kilobyte

16,67%

16,77%

15,96%

28,65%

~ 100 Kilobyte

  8,13%

  8,19%

  7,23%

26,76%

~ 200 Kilobyte

  7,69%

  7,87%

  5,28%

26,16%

11. táblázat

49

Üzenet

ZIP

ARJ

RAR

SigComp   (static)

SigComp   (shared)

5.

108,33%

100,59%

88,69%

50,14%

35,24%

6.

  84,62%

  78,88%

73,05%

51,38%

45,49%

7.

108,33%

100,59%

89,28%

50,14%

23,78%

8.

  84,79%

  80,22%

73,57%

51,38%

41,07%

9.

  82,82%

  79,59%

74,31%

45,45%

47,27%

10.

107,52%

102,35%

92,94%

59,37%

60,95%

11.

  79,66%

  76,53%

72,62%

51,97%

39,14%

12. 

  85,21%

  81,56%

74,95%

56,03%

35,48%

13.

  83,16%

  79,93%

74,82%

45,61%

22,06%

14.

  85,21%

  81,56%

75,30%

56,03%

23,60%

15.

  86,83%

  82,91%

77,58%

54,93%

43,25%

16.

  66,15%

  63,39%

60,30%

52,97%

46,49%

17.

  86,83%

  82,91%

77,58%

54,93%

20,33%

18.

  66,15%

  63,39%

60,30%

52,97%

18,16%

19.

  70,42%

  68,44%

65,18%

57,58%

55,17%

20.

108,20%

102,82%

92,82%

70,22%

36,72%

21.

  70,41%

  68,60%

64,99%

57,49%

55,93%

22.

108,20%

102,82%

92,82%

70,07%

26,68%

23.

  69,25%

  67,49%

64,84%

56,72%

50,17%

24.

  82,79%

  79,05%

73,70%

65,57%

47,01%

12. táblázat

Amint a 11. táblázatból leolvasható, minél nagyobb állományokat tömörítünk annál  inkább nő a különbség a tömörítési arányban az általános célú szoftverek javára. Azonban  a mi feladatunk az, hogy SIP üzeneteket tömörítsünk. Egy SIP üzenet ritkán nagyobb 1  Kilobyte­nál.   A   12.   táblázatból   láthatjuk,   hogy   ilyen   kis   üzenetek   tömörítésekor   már  static  módszerrel is lényegesen jobb tömörítési arányt tudunk elérni az általános célú  szoftverekkel szemben. Shared tömörítés esetében pedig tovább javul az arány. Mivel az  50

üzeneteket külön­külön kell tömörítenünk, (nincs lehetőségünk bufferelni őket, és majd  ha összegyűlik sok, csak akkor tömöríteni és elküldeni őket) ezért láthatjuk, hogy a mi  módszerünk alkalmasabb erre az általános célú tömörítő szoftvereknél.

51

9.   Összefoglalás Megismertük   a   jövő   mobiltelefon   szabványának   alapját   képező  Session   Initiation   Protocoll­t. Láttuk, hogy az üzenetei szöveges alapúak, amiket tömöríteni kell. A tömörí­ tés a  Signalling Compression  alrendszer feladata. Mivel minden ki­ és bejövő üzenetet  kódolni, illetve dekódolni kell, ezért a Session Initiation Protocoll megfelelő működésé­ hez elengedhetetlen a Signalling Compression alrendszer hatékony implementációja. A  szabvány sok mindenben pontosan előírja, hogyan kell a SigComp­nak működni, de van­ nak olyan kérdések, amelyek megválaszolását az implementátorokra bízza.  Dolgozatomban   ezekre   a   kérdésekre   kerestük   a   választ.   A   hangsúlyt   a   SigComp  compressor moduljára fektettük, hiszen a szabvány ezen a ponton adta nekünk a legna­ gyobb szabadságot, ezáltal a SigComp hatékonyságát legjobban e modul optimalizásával  tudtuk javítani. Megvizsgáltuk,   hogy   a   compressor   modul   implementálásakor   milyen   algoritmusok  jöhetnek szóba. A választásunk az LZSS algoritmusra esett, hiszen a korábbi tanulmá­ nyok alapján ez az algoritmus a legalkalmasabb a feladat megoldására. A következő feladatunk egy gyors illeszkedéskereső függvény megalkotása volt. Ez  elmélyült kutatást és sok elemzést igényelt, hiszen még nem állt a Nokia Hungary Kft.  rendelkezésére konkrét, a SIP környezetre elkészített tanulmány. A mi feladatunk volt  ennek az elvégzése és implementálása.  Először megvizsgáltuk, hogy általában milyen módon valósítják meg az illeszkedéske­ reső függvényt, majd ezen ötletekből kiindulva alkottuk meg a saját, SIP környezetben  hatékonyan működő megoldásunkat. Az   én   feladatom   volt   a   szóba   került   megoldások   implementálása,   hatékonyság­ vizsgálata,   tesztelése,   valamint   az   ehhez   szükséges   környezet   kialakítása   és   a   mérési  módszerek kidolgozása. Algoritmusunk eredményessége, reményeink szerint, a jövőbeni alkalmazása során a  gyakorlatban is igazolást nyer.

52

10.   Hivatkozások   [1] J. Rosenberg–H. Schulzrinne–G. Camarillo–A. Johnston–J.Peterson–R. Sparks–M.  Handley–E. Schooler: Session Initiation Protocol. RFC 3261, 2002.   [2] http://en.wikipedia.org/wiki/Session_(computer_science)   [3] Andrew S. Tannembaum: Számítógép hálózatok   [4] T. Berners­Lee–R. Fielding–L. Masinter: Uniform Resource Identifiers (URI):  Generic Syntax. RFC 2396, 1998.   [5] http://www.en.voipforo.com/SIP/SIP_components.php   [6] Sike Sándor: Programozási Módszertan II: Algoritmusok.   [7] R. Price–C. Bormann–J. Christoffersson–H. Hannu–Z. Liu–J. Rosenberg:  Signaling Compression. RFC 3320, 2003.   [8]  M. Garcia­Martin–C. Bormann–J. Ott–R. Price–A. B. Roach: The Session  Initiation Protocol (SIP) and Session Description Protocol (SDP) Static  Dictionary for Signaling Compression (SigComp). RFC 3485, 2003.   [9] M. Handley–V. Jacobson: SDP: Session Description Protocol. RFC 2327, 1998. [10] H. Hannu–J. Christoffersson–S. Forsgren–K.­C. Leung–Z. Liu–R. Price: Signaling   Compression (SigComp) – Extended Operations. RFC 3321, 2003. [11] B. Adamson–C. Bormann–M. Handley–J. Macker: Negative­ Acknowledgment  (NACK)­Oriented Reliable Multicast (NORM) Building Blocks. RFC 3941, 2004. [12] Márta Fridrich–Mihály Bohus–László Sógor–Zoltán Sógor–Vilmos Bilicki–Zsolt   Galambos–Tamás Szilágyi–Krisztián Notaisz–Péter Siket–István Siket–Gábor Sey –Zsolt Márton–Gábor Tóth–Róbert István: Study Report of the Project: Signalling  Compression Protocoll Development. 2002. [13] Michael Dipperstein: http://michael.dipperstein.com/lzss/ [14] Timothy Bell–David Kulp: Longest­match String Searching for Ziv­Lempel  Compression. 1993. [15] Thomas H. Cormen–Charles E. Leiserson–Ronald L. Rivest: Algoritmusok. 2001. [16] http://valgrind.org [17] http://valgrind.org/docs/manual/cl­manual.html

53