NO309918B1 - FremgangsmÕte relatert til et datakommunikasjonssystem - Google Patents

Description

Den foreliggende oppfinnelse vedrører et datakommunika-sjonssystem, og nærmere bestemt multipleksing av rammerelé ("frame relay multiplexing") i et slikt system, og nærmere bestemt en prioritetsstyring for multipleksing av ramme relé.

Méd andre ord vedrører oppfinnelsen en fremgangsmåte som angitt i den innledende del av det vedlagte patentkrav 1.

Termer og definisjoner

For å forstå den tekniske bakgrunn ved den foreliggende oppfinnelse bedre, bør man merke seg de følgende termer og definisj oner: LAPD - Link Access Protocol D Kanal for linkaksessproto- koll, referanse: ITU Q.921.

OSI- modell - " Open Systeras OSI-modellen deler en kommu-Interconnectlon"- modell nikasjonsprosess i lag 1-7

Fysisk lag OSI-modell for det laveste lag, 1, som er ansvarlig for aktivering, opprettholdelse og deaktivering av fysiske kretser.

Datalinklag Lag 2 for OSI-modellen, som er ansvarlig for overføring av data via en link med

'gjenvinning fra tapte data og data med feil.

Rammeréle Datakommunikasjon, hvor bare den nedre del av lag 2 utfø-res i noder mellom nodene med terminering av fullt lag 2 uten gjenoppretting av feil.

Teknisk bakgrunn

I forbindelse med datakommunikasjon benyttes rammerelé of-te. I dette tilfelle videreføres datarammer ved hjelp av mange noder, før protokollen for lag 2 avsluttes. Hvis én av disse noder utfører en multipleksing og konsentrasjon av trafikken fra mange kilder, er det mulighet for kommunika-sjonsoverflod i noen tidsintervaller. Hvis summen av kildenes datahastighet er større enn i destinasjonsretningen, vil en rammekø bygges ved utmatingselementet. Rammene kan forsinkes for mye i denne kø til å bekreftes, før timeren for retransmisjon i lag 2-kilden løper ut.

Problemområdet

Lag 2-protokollen, slik som LAPD, har en retransmisjonstid på Tl sekunder mislighold. Summen av transmisjonstid, kø-forsinkelsen og transmisjonstid for bekreftelsesrammen må ikke overskride disse Tl sekunder. Hvis denne sum er større en Tl, vil rammen rettransmitteres fra kilden. Rammen vil sannsynligvis plasseres i køen en gang til. Dette betyr i sin tur at trafikk fra andre kilder kan forsinkes altfor mye, og den nyttige gjennomstrømning vil reduseres.

Kjent teknikk og kjente løsninger

Én måte å løse dette problem på vil være å måle den reelle utgangskø, og gi alle kilder den samme sannsynlighet til å

tre inn i innkøen basert på en statistisk måling av kildene. Denne løsning krever mange beregninger.

Fra US patentskrift 5,231,633 (Hluchyj et al.) er det kjent en fremgangsmåte for prioritering, selektiv forkastning og multipleksing av forskjellig raske pakker av forskjellig trafikktype, og nærmere bestemt en innkøings- og utkøings-mekanisme til bruk i et integrert raskt pakkenett.

I henhold til den kjente teknikk multiplekseres raske pakker fra forskjellige trafikktyper med hverandre ved bruk av en allokeringsmekanisme for veiet omløps- ("round-robin") båndbredde. Selv om denne tidligere kjente teknikk har å gjøre med pakkekommunikasjon og multipleksing som er asso-siert md det, er denne kjente teknikk taus med hensyn til ethvert foreslag for å bruke fuzzy logikk for bestemmelse av når en dataramme skal slettes fra den aktuelle data-strøm.

Hensikter med oppfinnelsen

Hovedhensikten med den foreliggende oppfinnelse er å tilveiebringe en passende løsning på innkøingen av datarammer i et kommunikasjonsnett.

En annen hensikt med oppfinnelsen er å tilveiebringe en fremgangsmåte, ved hvilken datarammer som estimeres til å ha liten mulighet for å transmitteres i tide ved hjelp av fuzzy logikk, og utelates og sendes ikke til utgangskøen, fortrinnsvis ved å la rammer fra kilder med høy trafikk slettes først.

Enda en annen hensikt med oppfinnelsen er å tilveiebringe en fremgangsmåte, ved hvilken størrelsen på utgangsdatakøen påvirkes ved å bruke fuzzy logikk.

Sammenfatning av oppfinnelsen

Hensiktene ovenfor oppnås ved en fremgangsmåte som angitt i den innledende del, som er karakterisert ved trekkene som er angitt i den karakteriserende del av det vedlagte patentkrav 1.

Med andre ord løser oppfinnelsen problemet ovenfor ved en lengdesimulering av utgangskøing, en estimator for inn-gangskildetrafikk og fuzzy logikk for bestemmelse av når en dataramme må slettes fra datastrømmen. Hovedfordelene ved denne løsning er lav prosessor belastning og forenkling av en kombinasjon av få prinsipper.

Ytterligere fordeler med den foreliggende oppfinnelse vil fremgå av den følgende oppfinnelse tatt i forbindelse med den vedlagte tegning, så vel så av de vedlagte patentkrav.

Kort omtale av tegningen

Figur 1 er et blokkdiagram som illustrerer en nettstruktur, hvor en utførelsesform for den foreliggende oppfinnelse kan realiseres i.

Detaljert beskrivelse av oppfinnelsen

På figur 1 er det illustrert en nettstruktur i. blokkdiagram, hvor løsningen i henhold til den foreliggende oppfinnelse er realisert.

På figur 1 er det illustrert en rekke inngangskilder Sl, S2...Sp, og båndbredden fra kildene indikeres med IB (IB1, IB2... IBp, respektivt). Kildene kan ha forskjellige bånd-bredder, men ligningene, som skal benyttes, er gyldige for den samme hastighet for alle kilder.

Rammene fra de mange kilder Sl, S2...Sp multiplekseres i en rammemultiplekser, FM, til én utgående datastrøm, ODS. Summen av båndbreddene fra alle kilder vil i dette tilfelle være større enn båndbredden, OP, for den utgående data-strøm, ODS. Følgelig vil trafikk fra de nevnte kilder i visse tidsperioder være høyere enn den mulige utdatastrøm

ODS.

Simulator for utgangskø

Lengden på utgangskøen simuleres hvert Tl/N sekund, hvor timeren for retransmisjon av lag 2 og N = 2 eller 4. Simu-lering av kølengden utføres ved forminskning av en byteteller, QN, hvert Tl/N sekund med en verdi OB <*> Tl/N, som representerer de transmitterte data i det siste Tl/N-intervall. Nevnte■QN-teller økes med antall byter i rammen hver gang en ramme føres inn i den reelle kø.

Hvert Tl/N sekund prosesseres følgende kommandoer:

For hver ramme som sendes inn i den reelle kø:

Måling av inngangstrafikk

Inngangen til hver kilde beregnes hvert Tl/N sekund. Verdien beregnes som det transmitterte antall av byter for det siste sekund. For å utføre dette, trengs N+l-tellere for hver kilde. Én teller brukes for hvert av de N intervaller i et sekund, og én teller beholder summen for de N tellere. For hvert intervall beregnes summen, Mp, for tellerne, og den eldste verdi fjernes.

Båndbredden for kilden er IB (byter/s) og Mp er alltid være mindre enn IB.

Midlere inngangsestimator

Den midlere verdi for inngangskilder beregnes (MI). Dette gjøres hvert Tl/N sekund. Denne verdi vil brukes av fuzzy-logikken, når denne må bestemme om en ramme bør slettes.

I den midlere verdiberegning er bare kilder over et lite innivå på 1/10 <*> IB inkludert. Man ønsker bare å beregne den midlere verdi for kildene som transmitterer mye data.

Fuzzy logikk

Fuzzy-logikken kan med ord uttrykkes på denne måte:

Når en ramme mottas og innkøen er så lang at rammen sannsynligvis vil sendes for sent, ér det bedre å slette den nå. Rammen slettes ikke, hvis den er meget kort. Rammen slettes, hvis rammen kommer fra en kilde som har sendt mer enn gjennomsnittet blant kildene som sender mye.

Når en ramme mottas fra en hvilken som helst kilde, utføres følgende: Hvis lengden på utgangskø, QN, er lenger enn det som kan transmitteres i dette intervall og en fraksjon d(0 < d < 1) for det neste intervall, det vil si QN < (1 + d) <*> OB<*> Tl/N, er rammen en kandidat for papirkurven. Hvis rammen er en styreramme (lengde < 20 byter), så slettes denne ikke. Slett rammen, hvis rammen kommer fra en kilde med en trafikkindikator Mp > MI. Hvis Qn > 2 <*> OB <*> Tl/N, slett rammen uten noen test på Mp.

Fordeler

Fordelene med den foreliggende oppfinnelse er:

• Høyere gjennomstrømning i en multiplekser for rammerelé

• Stopper blokkering fra en kilde

• Gir prioritet til korte rammer

• Gir prioritet til kilder under gjennomsnittet

• Lav prosesseringsbelastning

• Små krav til lagerplass

• Ingen kjennskap til den reelle utgangskø kreves (dette kan være vanskelig å beregne, fordi køen kan delvis være maskinvare)

• Forskjellige prioritetsopplegg kan implementeres

• Prioritetsopplegget kan forstås på en intuitiv måte

• Algoritmen vil ikke redusere gjennomstrømningen, når den midlere trafikk er lav

Utvidelse

Disse prinsipper kan brukes hvor en konsentrasjon av trafikk oppstår, og hvor det er viktig å holde forsinkelsesti-den på utgangskøen under en grense.

I vedlegget gis det et eksempel på algoritmene for en pakke konsentrator med p = 14 kilder og 1 utgangskø.

VEDLEGG

Et eksempel på algoritmer for en pakkekonsentrator med p = 14 kilder og 1 utgangskø beskrives nedenfor.

Kildenes båndbredde er IB = 2000 byter/sekund og utgangens båndbredde er OB = 8000 byter/sekund.

Retransmisjonstimer Tl = 1 sekund.

Antall sampler per sekund er N = 2.

Timer for tidsovervåkning Tl/N =0,5 sekunder.

Hvert 0, 5 sekund blir det følgende beregnet:

Simulator for utgangskø, QN, beregnes som:

Den simulerte kø er korrekt etter denne beregning.

Trafikken for inngangskilde over de siste to intervaller: Midlere inngangsestimator

For hver ramme sendt fra enhver av kildene til utgangskøen, utfør fuzzy logikk med d = 0, 75:

Claims (14)

1. Fremgangsmåte relatert til et datakommunikasjonssy-stem, og nærmere bestemt multipleksing av rammerelé, hvori systemdatarammer videreføres ved hjelp av noder, som blant annet utfører multipleksing og konsentrasjon av trafikk fra en rekke inngangskilder, og hvori summen av den aktuelle transmisjonstid, innkøforsinkelsen og transmisjonstiden for bekreftelsesramme ikke bør overskride en innstilling for transmisjonstimer (Tl), karakterisert ved å kombinere de følgende trinn: a) å simulere en lengde på utgangskø, b) å estimere en trafikkverdi for innkilde, c) å bruke fuzzy logikk, for derved å bestemme når en dataramme må slettes fra datastrømmen.

2. Fremgangsmåte som angitt i krav 1, karakterisert ved at lengden på utgangskøen simuleres hvert Tl/N sekund, hvor Tl er innstillingen for transmisjonstimer av lag 2 og N er et tilfeldig tall, fortrinnsvis 2 eller 4.

3. Fremgangsmåte som angitt i krav 1 eller 2, karakterisert ved at lengdesimuleringen av utgangskøen utføres ved forminskning av en teller, spesielt en byteteller (QN) hvert Tl/N sekund, spesielt en verdi, OB <*> Tl/N, som representerer de transmitterte data i det siste Tl/N-intervall.

4. Fremgangsmåte som angitt i krav 3, karakterisert ved at nevnte teller (QN) økes med antall byter i rammen hver gang en ramme føres inn i den reelle kø.

5. Fremgangsmåte som angitt i ett av kravene 1-4, karakterisert ved at for hvert Tl/N sekund prosesseres følgende kommandoer:

6. Fremgangsmåte som angitt i ett av de foregående krav, karakterisert ved at for hver ramme som sendes inn i den reelle kø, vil følgende relasjon anvendes: QN = QN + (effektiv rammelengde inkludert flagg)

7 . Fremgangsmåte som angitt i ett av de foregående krav, karakterisert ved at inngangen fra en hvilken som helst inngangskilde beregnes hvert Tl/N sekund, idet verdien beregnes som det transmitterte antall byter for det siste sekund.

8 . Fremgangsmåte som angitt i ett av de foregående krav, karakterisert ved at for hver inngangskilde (Sl, S2...Sp) benyttes én teller for hvert av de N siste intervaller og én for summen Mp (trafikkindikator) som beregnes som summen av intervalltellerne på slutten av hvert Tl/N intervall, og den eldste verdi fjernes derfra.

9. Fremgangsmåte som angitt i ett av de foregående krav, karakterisert ved at den midlere inn-gangsverdi (MI) for inngangskildene beregnes hvert Tl/N sekund, idet beregningen effektueres på kilder som transmitterer mye data, for eksempel en viss fraksjon av båndbredden for inngangskilde (IB, byter/s), nærmere bestemt 1/10 <* >IB.

10. Fremgangsmåte som angitt i ett av de foregående krav, karakterisert ved at fuzzy-logikken benyttes for å forhåndsestimere hvorvidt en mottatt ramme og køen er så lang at rammen sannsynligvis vil transmitteres for sent, for derved å slette en hvilken som helst slik ramme fra køen.

11. Fremgangsmåte som angitt i ett av de foregående krav, karakterisert ved at fuzzy-logikken be-stemmer hvorvidt en ramme er en kandidat for papirkurven, hvis kølengden (QN) er større enn det som kan transmitteres i nevnte intervall (Tl/N) og en fraksjon (d) av det neste intervall (1+d), og nærmere bestemt i henhold til QN > (1+d) <*> OB <*> Tl/N.

12. Fremgangsmåte som angitt i ett av de krav 10 eller 11, karakterisert ved at hvis rammen er en potensiell styreramme (lengde < 20 byter), slettes en slik ramme.

13. Fremgangsmåte som angitt i ett av de foregående krav, karakterisert ved at hvis rammen kommer fra en kilde, som har en trafikkindikator (Mp) som er stør-re enn den midlere verdi av inngangskildene (MI), slettes en slik ramme.

14. Fremgangsmåte som angitt i ett av de foregående krav, karakterisert ved at hvis en simulert fraksjon av lengde på en utgangskø (QN) er lenger enn to ganger verdien som representerer de transmitterte data (OB) i det siste intervall (Tl/N), bør en slik relatert ramme slettes uten testing på trafikkindikatoren (Mp), det vil si hvis QN > 2 <*> OB <*> Tl/N.