Compressietechnieken vr een weinig data

[Verwijderd]

Hello,

Graag zou ik de performance van een server willen verbeteren door de data die deze verstuurt&ontvangt te verkleinen. De data zijn redelijk kleine packages van slechts enkele bytes.
Is het mogelijk om data te comprimeren als deze slechts 5 bytes (of meer) groot is?

Greetz&thanks,
Ken

[Glimi]

Wat heb je zelf al geprobeerd, onderzocht ed? Heb je al gekeken naar Huffman en andere lossless compressie vormen?
Kortom: Welkom in P&W -> Quickstart (update 2/10/2002)

[Verwijderd]

5 bytes hoef je niet te gaan comprimeren denk ik, de overhead die dat veroorzaakt zal waarschijnlijk al meer dan 5 bytes zijn

Wat voor server ?
Hoe groot zijn de packages gemiddeld?

Ik heb zelf op een simpele manier compressie toegepast, door een hoeveelheid data gewoon via zlib te compressen voordat ik het verstuur.

[ Voor 28% gewijzigd door Verwijderd op 24-03-2003 23:32 ]

[Soultaker]

Met een leuke constante Huffmann codering kun je je pakketgrootte misschien halveren (omdat je geen extra header of dictionary data nodig hebt) maar als het om een byte of 10 gaat die je via een netwerk wilt versturen, heeft dat absoluut geen zin. (Gezien de overhead van de packet en het feit dat de meeste media nauwelijks verschil in snelheid kennen, zolang de pakketjes onder de MTU blijven).

[Verwijderd]

Ik denk dat ivm overhead het niet efficient is om daarop compressie toe te passen, maar je kan natuurlijk wel je server/netwerk zodanig optimaliseren dat zo min mogelijk herverzending/opvraag van info plaatsvindt.

Wellicht dat het ook makkelijker is om een voorbeeld van de data hier op GoT te posten? Want verschillende data is divers te optimaliseren...

[MSalters]

Je kunt de performance waarschijnlijk verbeteren door de pakketjes te vergroten!

Als je van TCP/UDP afstapt en RTP gebruikt, dan heb je geen foutcorrectie. Dat betekent dus ook dat je standaard geen resends krijgt. Als je redundant data toevoegt, dan heb je veel minder resends nodig, omdat je veel verminkte packets toch kunt lezen.

Zelfs UDP kan om dit soort redenen efficienter zijn dan TCP.

[CubicQ]

Maar over het algemeen heb je ook nog lagere lagen die al pakketjes gaan lopen weggooien als er errors optreden. Dus dan schiet het nog niet zo op, want dan krijg je geen verminkte packets binnen.

edit:
nog even afgezien van het feit dat er bij wired links vrijwel nooit packets verloren gaan vanwege transmissiefouten (1^-9 a 1^-12 ofzo), je zit dan bijna altijd met congestie. Bij wireless links heb je het probleem wel, maar daar heb je meestal al FER ingebouwd.

[ Voor 42% gewijzigd door CubicQ op 25-03-2003 11:49 ]

[Verwijderd]

De compressie technieken (zoals bvb Huffman, lzw, zip-varianten) zijn inderdaad niet bruikbaar doordat ze oftewel een overhead geven of simpelweg niet toepasbaar zijn. De data van de (game-)server zelfs is al héél erg geoptimaliseerd waardoor ik in principe tot 8 clients op een DSL/kabel verbinding zou kunnen connecten. Compressie op een 5-tal bytes (want dat is de packagegrootte meestal) is inderdaad niet makkelijk, maar het lijkt me niet onmogelijk.
En wat als ik bvb een 20 a 30-tal bytes wil comprimeren (bvb chat text)? Is dat mogelijk? Ik zou een gewone dictionary gebruiken plús een bestaande compressietechniek.
Met dictionary bedoel ik:

"Dit is een tekst"
Als:
tekst ~ 1
Dan:
"Dit is een *1"

[edit] Voor de chat text zou ik dan ook een 7-bit ascii code gebruiken ipv 8-bit.

[ Voor 8% gewijzigd door Verwijderd op 25-03-2003 19:22 ]

[xoror]

Als het om kleine TCP pakketten (size < mtu) gaan, kan je naggle algo uitschakelen. die zorgt ervoor dat je paketten 'gestalled' worden tot je mtu size is bereikt en dan stuurt ie het pas.

zonder naggle verstuurt je server het pakketje meteen. wat wellicht tot betere responstijden lijdt.

[Verwijderd]

Als de packages zo klein zijn, dan moeten er wel mana-veel packages verstuurd worden wil jij tegen je bandbreedte limiet oplopen, denk ik. Ik denk dat je je oplossing ergens anders moet zoeken.

[Verwijderd]

Verwijderd schreef op 26 maart 2003 @ 02:03:
Als de packages zo klein zijn, dan moeten er wel mana-veel packages verstuurd worden wil jij tegen je bandbreedte limiet oplopen, denk ik. Ik denk dat je je oplossing ergens anders moet zoeken.

Voor de client zijn de packages klein, maaaar onderstaand heb je een klein voorbeeldje van hoe de server dit moet verwerken:

- 8 clients zijn geconnect op de server
- elke client doet 160 bytes per seconde (dat is het ongeveer)
- dus de server ontvangt 8x160 bytes per seconde, ongeveer 1kB per seconde dus.
- de server moet - bijna - al deze data naar élke client (buiten de client die zijn eigen pakketje stuurde) versturen, dus: 8x7x160 bytes. Dit geeft 9 kilobytes per seconde upload.

In het kort: als elke client 160 bytes per seconde doorstuurt, dan moet de server er 9kBytes per seconde sturen. Of kan je via internet en tcp/ip op een of andere manier een soort broadcasting doen?

p.s. voor de bovenstaande berekeningen heb ik wel een excel sheetje hoor

[hobbit_be]

als je zegt 160b/s bedoel je dan dat dat verschillende sends zijn? ie 4x40b of zo? of hou je het effe bij en verstuurt dan alles - of is het meer een soort router?. 9Kbytes is toch niet te erg of zit je op een modem? als je de client kunt programmeren kun je natuurlijk ook iedereen met iedereen connecten een echt web dus maar ik neem aan dat dat niet de bedoeling is.

[Verwijderd]

hobbit_be schreef op 26 maart 2003 @ 19:25:
als je zegt 160b/s bedoel je dan dat dat verschillende sends zijn? ie 4x40b of zo? of hou je het effe bij en verstuurt dan alles - of is het meer een soort router?. 9Kbytes is toch niet te erg of zit je op een modem? als je de client kunt programmeren kun je natuurlijk ook iedereen met iedereen connecten een echt web dus maar ik neem aan dat dat niet de bedoeling is.

Het is in feite 236 bytes per seconde per client (ongeveer het gemiddelde), deze bestaan uit verschillende pakketjes:

- 140bps aan verplaatsingsdata niveau 1 (20 keer 4 bytes per seconde)
- 30 bps aan verplaatsingsdata niveau 2 (5 keer 3 bytes per seconde)
- 0.3 bps aan verplaatsingsdata niveau 3 (3 bytes, elke 30 seconden)
- 13 bps aan chat data (10 bytes, elke seconde)
- 53 bps aan systeemdata (50 bytes, elke seconde)

Bij elk pakketje komen 2 bytes aan extra gegevens bij, daarom dat een gewone vermenigvuldigingsberekening niet zou kloppen hierboven

Nota: De verplaatsingsdata is in niveau's opgedeeld. De coordinaten bevatten 6 digits (bvb 1234,56) waarvan bvb de laatste 2 digits centimeters zijn (niveau 1) en dus vaak moeten worden geupdate), de middelste 2 digits (34) zijn meters en de eerste 2 digits (12) zijn meters in honderdtallen.

[hobbit_be]

is dit toevallig voor robo-football? Ik weet te weining van TCP/IP af maar ik het vermoeden dat die veel te veel overhead heeft voor zo'n kleine dingen. De header alleen is groter dan de data die je verstuurt (vermoed ik). een custom protocol met sockets lijkt me toch aan te raden. waar zit eigenlijk je probleem?. met 4 bytes met fixed point heb je wel erug veel plaats voor beweging een short int zou ook misschien kunnen doen. of zelfs een 3byter...
als je data doorstuurt kun je misschien alleen de delta's doorsturen. Wat doet quake eigenlijk? ik kan me niet inbeelden dat ie zo'n refresh rate heeft... Mogen weten waarvoor het dient want om die mini packages te verkleinen lijkt me een beetje pointless met zoveel traffic...

[Verwijderd]

hobbit_be schreef op 26 March 2003 @ 20:57:
is dit toevallig voor robo-football? Ik weet te weining van TCP/IP af maar ik het vermoeden dat die veel te veel overhead heeft voor zo'n kleine dingen. De header alleen is groter dan de data die je verstuurt (vermoed ik). een custom protocol met sockets lijkt me toch aan te raden. waar zit eigenlijk je probleem?. met 4 bytes met fixed point heb je wel erug veel plaats voor beweging een short int zou ook misschien kunnen doen. of zelfs een 3byter...
als je data doorstuurt kun je misschien alleen de delta's doorsturen. Wat doet quake eigenlijk? ik kan me niet inbeelden dat ie zo'n refresh rate heeft... Mogen weten waarvoor het dient want om die mini packages te verkleinen lijkt me een beetje pointless met zoveel traffic...

Ik werk al een paar maanden aan een 3D multiplayer first person tactical shooter, genaamd 'AlterNova'. Sinds kort ben ik beginnen werken aan de server, vandaar dat ik het traffic wil beperken. Alle data wordt binair opgeslagen en omgezet (bvb 7 bits woorden), dus ints, short ints e.d. worden niet gebruikt (ze worden wel gebruikt, maar niet in die vorm doorgestuurd).

Dit is de AlterNova homepage. Hier vind je het GoT topic van het spel en hier heb je wat screenshots (klikken om te vergroten):

[madwizard]

De 'pakketten' zoals je ze in je programma definieerd hebben meestal geen enkele relatie met de TCP pakketten. Door het nagle algoritme wordt data niet meteen verstuurd op het moment dat je daarom vraagt maar worden meerdere sends samengevoegd tot 1 pakket. De overhead zou anders veel te groot worden (ongeveer 20 bytes voor TCP/IP). Dit zorgt wel voor wat vertraging natuurlijk, maar ook voor een veel betere benutting van de bandbreedte. Je kunt dit uitzetten maar ik denk niet dat je daarop vooruit gaat tenzij je zelf de frames gaat indelen.

UDP wordt wel direct verzonden en heeft minder overhead (dacht 8 bytes) maar daar staat wel tegenover dat het niet reliable is. Bij audio/video applicaties e.d. is wat data loss niet erg maar volgens mij wil jij wel dat je data goed aankomt. Je kunt uiteraard zelf zorgen dat de boel reliable wordt maar dan ben je eigenlijk TCP aan het herschrijven..

Aan wat ik gezien heb van je protocol ziet het eruit als text-based, een binaire versie is natuurlijk efficienter. Bijvoorbeeld een coordinaat van 6 ascii karakters kan ook als 24-bits getal (3 bytes) opgeslagen worden. Chat tekst kan zoals je al zei ook met 7-bits ascii maar als je wel je data gaat comprimeren is 8-bits misschien handiger (meeste algoritmes werken op byte niveau, met 7 bits zou de tekst niet meer op byte boundaries lopen). Verplaatsingsdata kan ook relatief aan de vorige waarde worden opgeslagen zodat het minder ruimte inneemt.

Compressie is niet makkelijk over zo'n kleine hoeveelheid data, hoewel je wel een soort van statistieken zou kunnen bijhouden (karakterfrequenties) aan beide kanten en daarmee huffman of arithmetic encoding toepassen. Zolang server en client dezelfde informatie bijhouden heb je geen compressieoverhead bij het versturen, en door de statistieken wordt de compressie steeds beter (er vanuit gaand dat de data ook goed comprimeerbaar is, dus veel herhaling enzo).

Kun je misschien een complete of halve seconde aan data posten (als dat niet te veel is)?

[Verwijderd]

@ madwizard:

De data wordt wel binair verhandeld hoor. Bijvoorbeeld, een 'gewone' coordinaat-update bevat:
- 20 bits aan coordinaatgegevens (dit geeft een getal van 6 digits, dat je opdeelt in 3x2 digits, voor 3 coordinaten dus)
- 8 bits voor de spelerhoek in 3d (dus nr waar hij kijkt)
- 1 bit om te zien of de speler beweegt nr voren
- 1 bit om te zien of hij staat/crouched
- 1 bit om te bepalen of de speler nr beneden kijkt of gewoon recht vooruit

Dit is een een voorbeeld van een aantal bytes chat-data uit 1 package:
0010101000010110100101101100111000000100100101101100111000000100100001100000010000101110101001101100111000101110

[edit] een hele/halve seconde aan data kan ik nog niet posten, want het server-encryptie-protocol is nog niet af.

[ Voor 13% gewijzigd door Verwijderd op 26-03-2003 22:07 ]

[madwizard]

Verwijderd schreef op 26 March 2003 @ 22:06:
@ madwizard:
De data wordt wel binair verhandeld hoor. Bijvoorbeeld, een 'gewone' coordinaat-update bevat:
- 20 bits aan coordinaatgegevens (dit geeft een getal van 6 digits, dat je opdeelt in 3x2 digits, voor 3 coordinaten dus)
- 8 bits voor de spelerhoek in 3d (dus nr waar hij kijkt)
- 1 bit om te zien of de speler beweegt nr voren
- 1 bit om te zien of hij staat/crouched
- 1 bit om te bepalen of de speler nr beneden kijkt of gewoon recht vooruit

Daar valt weinig aan te optimaliseren denk ik, alleen coordinaat zou van variabele grootte kunnen zijn met een paar bits ervoor die aangeven hoe groot het getal is. Bijvoorbeeld als de eerste 2 bits 00 zijn volgen er bits voor alleen de centimeters, bij 01 meters + centimeters, bij 10 ook nog 100-meters. Zo heb je bij kleinere verplaatsingen minder bits nodig dan bij grote. Maar een verbetering van 3 bytes naar 1 byte in sommige gevallen is niet echt spectaculair te noemen .

Dit is een een voorbeeld van een aantal bytes chat-data uit 1 package:
0010101000010110100101101100111000000100100101101100111000000100100001100000010000101110101001101100111000101110

Voor chatdata zou je wel huffman kunnen gebruiken met statistieken aan beide kanten zodat je geen tabellen over hoeft te sturen. Als je dan veel a's ofzo gebruikt gaan die na een tijdje minder ruimte innemen dan bijvoorbeeld een 'x' (bij huffman maximaal 8:1, arithmetic kan hogere ratio's halen).
edit: Je kan ook natuurlijk vaakgebruikte woorden gaan bijhouden en die met bepaalde codes oproepen in de chatdata.

[ Voor 9% gewijzigd door madwizard op 26-03-2003 22:33 ]

[Verwijderd]

Inderdaad, ik was reeds van plan met een soort dictionary te werken vr de chattekst

[Soultaker]

Volgens mij zie je helemaal niets van deze moeite terug in verhoogde performance of throughput rates, maar goed, daar kom je nog wel achter. Beperk je tot een simpele scheme (Huffman, of helemaal niets) en laat het daarbij. Verderde optimalisaties leveren marginale winsten op. Maar goed, het is jouw tijd.