NL8000941A

NL8000941A - Werkwijze voor de radiooverdracht van datapakketten.

Info

Publication number: NL8000941A
Application number: NL8000941A
Authority: NL
Original assignee: Philips Nv
Priority date: 1980-02-15
Filing date: 1980-02-15
Publication date: 1981-09-16
Also published as: HK76186A; CA1161137A; JPS6326937B2; FR2476414A1; US4398289A; DE3105199A1; GB2069799B; SE457134B; JPS56129459A; NL189062B; GB2069799A; FR2476414B1; DE3105199C2; SE8100964L; NL189062C

Description

* * ' PHN 9693 1 N.V. Philips' Gloeilampenfabrieken te Eindhoven

Werkwijze voor de radiooverdracht van datapakketten.

De uitvinding heeft betrekking op een werkwijze voor de radiooverdracht van datapakketten van meerdere onderstations naar een hoofdstation via een voor de overdracht van deze datapakketten gemeenschappelijk kanaal, waarbij door het hoofdstation via een ander kanaal 5 een synchronisatiesignaal wordt uitgezonden dat bij ontvangst in de onderstations het begin van een periode aangeeft welke in een opeenvolging van tijdsleuven van onderling gelijke duur is verdeeld, en die onderstations, die een pakket voor overdracht naar het hoofdstation gereed hebben, dit pakket in een willekeurig uit genoemde opeenvolging 10 van tijdsleuven geselecteerde tijdsleuf naar het hoofdstation overdragen, en waarbij het hoofdstation onderscheid maakt tussen onverminkt en verminkt overgedragen pakketten, en de onverminkt overgedragen pakketten worden geregistreerd om vervolgens door het hoofdstation ter bevestiging van de goede ontvangst na elkaar via genoemd andere kanaal te 15 worden uitgezonden.

De uitvinding heeft tevens betrekking op een systeem voor toepassing van deze werkwijze, die in de desbetreffende vakliteratuur doorgaans wordt aangeduid met de benaming "slotted ALOHA" zoals moge blijken uit bijvoorbeeld het als referentie 1) genoemde artikel. Uit 20 dit artikel blijkt verder dat deze bekende "slotted ALOHA" strategie alleen dan met succes toepasbaar is, wanneer voldoende maatregelen- worden getroffen om te voorkomen dat het systeem bij groot verkeersaanbod in een instabiele toestand geraakt. Meer in het bijzonder treedt zulk een instabiele toestand op, indien, bij groot verkeersaanbod, de over-25 dracht van datapakketten van de onderstations naar het hoofdstation inefficiënt wordt, doordat het aantal verminkt overgedragen pakketten toeneemt, hetgeen een toename van het aantal opnieuw over te dragen pakketten betekent, die op hun beurt weer tot een grotere inefficiëntie leiden en waardoor uiteindelijk een volledige blokkering van het systeem 30 optreedt.

Ter oplossing van dit instabiliteits-probleem zijn al verschillende, op uitvoerige theoretische beschouwingen gebaseerde stra-tegiën voorgesteld, in verband waarmede verwezen kan worden naar 800 0 9 41

. f\ V

PHN 9693 2 bijvoorbeeld de referenties 2 tot en met 5. Afgezien nog daarvan, dat aan deze publikaties in de meeste gevallen geen directe implementatie van de ter oplossing van het genoemde probleem, voorgestelde besturings-maatregelen is te ontlenen, hebben deze bekende strategiën allen het na-5 deel dat zij de ten allen tijde willekeurige vrije toegang van de onder-stations tot het overdrachtskanaal te niet doen en daarmede tevens de eenvoud en robuustheid van het systeem, eigenschappen die juist als de meest belangrijke zijn te beschouwen.

De uitvinding beoogt voor het bovengenoemde instabiliteits-10 probleem een vzodanige oplossing te verschaffen, dat een willekeurige vrije toegang tot het overdrachtskanaal voor alle onderstations behouden blijft en daarmede de eenvoud en robuustheid van het systeem.

Overeenkomstig de uitvinding bezit de in de aanhef omschreven werkwijze daartoe het kenmerk, dat in het hoofdstation op basis 15 van de vóórgeschiedenis van onverminkt overgedragen pakketten en verminkt overgedragen een schatting wordt gemaakt van het aantal onderstations dat aan het begin van de volgende periode een pakket voor overdracht naar het hoofdstation gereed zal hebben, en dat het aantal tijdsleuven van genoemde volgende periode wordt aangepast op basis van genoemde 20 schatting.

Bij toepassing van de werkwijze volgens de uitvinding is het aantal aan de onderstations ter beschikking staande tijdsleuven een functie van de voortdurend bijgewerkte schatting van het aantal onderstations dat een datapakket voor overdracht gereed heeft. Hierdoor wordt 25 bereikt dat het aantal tijdsleuven is aangepast aan de behoefte. Bij een juiste schatting zijn er niet meer tijdsleuven dan nodig, niet minder maar ook niet meer. Deze adaptieve ALOHA- strategie maakt'’'·: dat het systeem stabiel is en kan bovendien resulteren in een grotere efficiëntie, aangezien het gemiddeld aantal tijdsleuven per periode kleiner kan zijn 30 dan het vaste aantal tijdsleuven per periode, dat bij toepassing van de bekende "slotted A L 0 H A"-strategie nodig is.

Referenties; 1. Leonard Kleinrock and Simon S. Lam, "Packet Switching in a Multiaccess Broadcast Channel: Performance 35 Evaluation", IEEE Transactons on Communicatons, Vol. CDM-23, No. 4, April 1975, pp 410-423.

800 0 9 41 if -rf"* PHN 9693 3 2. Simon S. Lam and Leonard Kleinrock: "Packet Switching in a Multiaccess Broadcast Channel: Dynamic control Procedures", IEEE Transactions on Communications, Vol. CDM-23, No. 9, September 1975, pp 891-904 5 3. G. Fayolle et Al, "Stability and Control of Packet-switching Broad cast Channels", IRIA - Laboratoire de REcherche en Informatique et Automatique, Rapport de Recherche No 116, Avril 1975 4. Hiromi Okada et Al, "Analysis and Application of Framed ALOHA Channel in Satellite Packet-Switching Networks - F A D R A Method" 10 Electronics and Communcations in Japan, Vol. 60 - B, No. 8, 1977 pp 72-80.

5. Leonard Kleinrock and V. Yemini, "An optimal Adaptive Scheme for Multiple Access Broadcast Communciation", Conference Record 1978, International conference on Communications, Vol 1, pp 7.2.1. - 7.2.5.

15 De uitvinding en haar voordelen worden nader toegelicht aan de hand van de tekening, waarvan

Figuur 1 een systeem toont voor de overdracht van data-pakketten tussen een hoofdstation en meerdere onderstations, en

Figuur 2 een stromingsdiagram toont van in het hoofdstation 20 uitgevoerde computerfuncties ter realisering van de methode volgens de uitvinding.

Het in figuur 1 weergegeven systeem voor de overdracht van datapakketten omvat een hoofdstation A en een aantal geographisch verspreid gelegen vaste of bewegelijke onderstations B^, B2, B^, ...Bn· 25 Het hoofdstation A is voorzien van een centrale computer 1 met een bijbehorend klokcircuit 2 en met randapparatuur in de vorm van een modem 3.

Het hoofdstation omvat verder een tweetal zend-ontvangers 4, 5, die via een schakelmatrixnetwerk 6 en genoemde modem 3 op de centrale computer 1 zijn aangesloten. Ce onderstations B^, B2> B^, .... Bn zijn allen gelijk 30 van opbouw en bevatten elk een computer die via randapparatuur op een zendontvanger is aangesloten.

Het tot dusver beschreven systeem is bekend en dient voor de overdracht van datapakketten die tik een enkele boodschap overdragen en die allen dezelfde lengte bezitten. Meer in het bijzonder wordt elk 35 pakket gevormd door een bepaald aantal identificatie- en controlebits, een bepaald aantal informatiebits en een bepaald aantal pariteitsbits.

De pariteits-bits in elk pakket worden gebruikt voor een cyclische fout detectiecode. Het systeem heeft de beschikking over tenminste twee kanalen 800 0 9 41

, V

PHN 9693 4 voor de radiooverdracht van datapakketten, namelijk een eerste kanaal voor de overdracht van datapakketten van het hoofdstation A naar de onderstations B,, EL, EL, ... B en een tweede kanaal voor de overdracht van datapakketten van de onderstations B^, ^y ··· naar 5 hoofdstation A. Deze beide radiooverdrachtkanalen werken met dezelfde bit-rate . De overdracht van datapakketten van het hoofdstation naar de onderstations levert geen moeilijkheden op, aangezien de zender bestuurd kan worden en de toepassing van een buffergeheugen in de centrale computer van het hoofdstation het mogelijk maakt om de datapakkettten voor de onder-10 stations in een bepaalde volgorde, bijvoorbeeld via een bepaald priori-teitsschema, via het eerste kanaal uit te zenden. De overdracht van datapakketten van de onderstations naar het hoofdstation is echter minder eenvoudig aangezien deze datapakketten niet zonder meer geordend kunnen worden om in opeenvolging via het tweede kanaal naar het hoofdstation 15 te worden overgedragen. Het systeem maakt daartoe gebruik van de bekende methode volgens welke door het hoofdstation via het tweede kanaal een synchronisatiesignaal wordt uitgezonden dat bij ontvangst in de onderstations het begin van een periode aangeeft welke in een opeenvolging van tijdsleuven van onderling gelijke duur is verdeeld, waarbij die onder- / Λ 20 stations, die een datapakket voor overdracht naar het hoofdstaton gereed hebben, dit pakket in een willekeurig uit genoemde opeenvolging van tijdsleuven geselecteerde tijdsleuf naar het hoofdstation overdragen, en waarbij het hoofdstation onderscheid maakt tussen onverminkt en verminkt overgedragen pakketten, en de onverminkt overgedragen pakketen in een 25 geheugen worden geregistreerd om vervolgens door het hoofdstation ter bevestiging van de goede ontvangst na elkaar via het tweede kanaal te worden uitgezonden.

Een door een onderstation uitgezonden datapakket kan in het hoofdstation verminkt worden ontvangen als gevolg van twee soorten van 30 fouten, namelijk: (1) willekeurig optredende fouten die door ruis worden veroorzaakt, en (2) fouten die worden veroorzaakt door interferentie welke optreden kan als gevolg van de gelijktijdige selectie van êên en dezelfde tijdsleuf door meer dan êên onderstation.

35 De tweede soort van fouten, die veroorzaakt wordt door interferentie, zal vooral dan optreden wanneer een groot aantal onderstations het gemeenschappelijke overdrachtskanaal gelijktijdig proberen 800 0 9 41 5 ^ PHN 9693 5 te benutten. Interferentie-fouten beperken derhalve het aantal gebruikers van het gemeenschappelijke overdrachtskanaal en de efficiëntie van het systeem. Dit verlies aan'efficiëntie kan, zoals in het voorgaande werd toegelicht en in genoemde referentie 3 in detail is uiteengezet, 5 gemakkelijk leiden tot systeeminstabiliteit, dat wil zeggen een totale ineenstorting van de overdrachtsmogelijkheid.

Overeenkomstig de uitvinding kan dit instabiliteitsprobleem op bijzonder elegante wijze worden opgelost indien in het hoofdstation op basis van de vóórgeschiedenis van onverminkt overgedragen pakketten 10 en verminkt overgedragen pakketten een schatting wordt gemaakt van het aantal onderstations, dat aan het begin van de volgende periode een pakket voor overdracht naar het hoofdstation gereed zal hebben, en indien het aantal tijdsleuven wordt aangepast op basis van geroemde schatting.

De methode volgens de uitvinding voorkomt niet alleen dat 15 het systeem bij groot verkeersaanbod in een instabiele toestand kan geraken, maar resulteert bovendien, doordat het aantal tijdsleuven per periode is aangepast aan de geschatte behoefte, in een grotere efficiëntie en beter rendement.

De methode volgens de uitvinding heeft verder het belang-20 rijke voordeel dat zij zich op eenvoudige wijze laat implementeren.

Bij een voorkeursuitvoeringsvorm van het systeem volgens de uitvinding is iedere periode 'onderverdeeld in een aantal opeenvolgende frames en wordt de aanpassing van het aantal tijdsleuven gerealiseerd door variatie van' het aantal tijdsleuven per frame en/of het aan-25 tal frames per periode.

Bij deze uitvoeringsvorm geeft het door het hoofdstation uitgezonden synchronisatiesignaal bij ontvangst in de onderstations het begin van elk van de frames aan. Meer in het bijzonder wordt het synchronisatiesignaal daarbij gevormd door een eerste in gecodeerde 30 vorm overgedragen getalwaarde welke het aantal frames per periode aangeeft en tenminste een tweede in gecodeerde vorm overgedragen getalwaarde welke de rangorde van het desbetreffende frame binnen de periode aangeeft alsmede een derde in gecodeerde vorm overgedragen getalwaarde welke het aantal tijdsleuven van het desbetreffende frame 35 aangeeft. Het aantal tijdsleuven per frame en/of het aantal frames per periode is daarbij variabel en wordt in het hoofdstation bepaald in afhankelijkheid van de geschatte behoefte. Dit kan op eenvoudige 800 0 9 41 PHN 9693 6 wijze worden gerealiseerd. Hiertoe is het namelijk slechts nodig dat de gegevens omtrent het al of niet verminkt zijn van de in het hoofdstation ontvangen pakketten met behulp van de centrale computer 1 volgens een bepaald programma worden verwerkt. Het programma realiseert een 5 algorithme waarvan het stromingsdiagram in Figuur 2 is weergegeven en dat is gebaseerd op twee niveaus van terugkoppelinformatie. Op niveau 1 wordt als functie van de historie van onverminkt en verminkt overgedragen pakketten een schatting gemaakt van de mate van toe- of afname van het aantal pakketten, dat voor overdracht naar het hoofdstation gereed is.

10 Deze niveau 1- informatie bepaalt het aantal tijdsleuven van het eerste frame van de periode. Op niveau 2 wordt de schatting van het aantal pakketten, dat voor overdracht naar het hoofdstation gereed is, bijgewerkt (up-dated) telkens met het resultaat van het voorafgaande frame. De niveau 2 - informatie is bepalend voor het aantal tijdsleuven 15 van het volgende frame en voor het al of niet aan de desbetreffende periode toevoegen van een nieuw frame.

De in het stromings-diagram van Figuur 2 aangegeven legenda hebben de volgende betekenis;

Variabelen; 20 ^ schatting van de toename per tijdseenheid van het aantal onderstations dat een pakket voor overdracht gereed zal hebben £ schatting van het aantal pakketten dat voor overdracht naar het hoofdstation gereed is 25 t tijd sinds de laatste overdrachtsperiode i frame nummer a^ aantal tijdsleuven van frame i t^ begintijdstip van frame i s^ aantal onverminkt overgedragen pakketten in frame i 30 g^ aantal verminkt overgedragen pakketten in frame i yi 9j» ^2’ s2’ ^2’ *····*··* sj[> 9^) historie van frames.

Functies en constanten; f^ schat Λ uitgaande van y^. Dit kan bijvoorbeeld als 35 volgt; Λ = - 3i_10g) / (tj - ti_1pp) 80 0 0 9 41 PHN 9693 7 f2 schat ~ uitgaande van s^, g^, a^ en de vorige waarde £

Dit kan bijvoorbeeld als volgt: Λ Λ r = g. * (1,81 + 0,56 * — ) + s. * (-0.04 + 0,21 * — ) 1 ai 1 ai g bepaal het aantal tijdsleuven in het volgende frame.

5 λ

Dit kan bijvoorbeeld als volgt: a. = max (1, int (r))

* A

1 geeft de onderste grenswaarde van r aan; beneden deze waarde wordt geen nieuw frame gestart.

Deze grenswaarde kan bijvoorbeeld 1 = 0,5 zijn.

10 zendt uit - een uitgangsfunctie, die het getal dat het aantal tijdsleuven a^ van frame ^ aangeeft, uitzendt als deel van het synchronisatiesignaal.

neem waar - is een ingangsfunctie, die aan de-antvangen pakketten het aantal onverminkt overgedragen pakketten s^ en het aantal 15 verminkt overgedragen pakketten g^ ontleent en die aan de tijdklok het begintijdstip t^ van frame nummer i ontleent.

Het zal duidelijk zijn dat de uitvinding niet is beperkt tot de in het voorgaande beschreven voorkeursuitvoeringsvorm, maar dat, 20 afhankelijk van de toepassing die van het systeem, wordt gemaakt, ook wel een uitvoeringsvorm zonder een indeling van de overdrachts-periode in een aantal opeenvolgende frames mogelijk is en dat de essentie van de uitvinding derhalve moet worden gezien in de aanpassing van het aantal tijdsleuven per overdrachtsperiode.

25 Verder zij opgemerkt, dat in figuur 2 met het blokje BGNP

het begin van een periode wordt aangeduid, met BGNF het begin van een frame bedoeld wordt, met NDF het einde van een frame bedoeld wordt en met DNP het einde van een periode bedoeld wordt.

30 35 800 0 9 41

Claims

1. Werkwijze voor de radiooverdracht van datapakketten van meerdere onderstations naar een hoofdstation via een voor de overdracht van deze pakketten gemeenschappelijk kanaal, waarbij door het hoofdstation via een ander kanaal een synchronisatiesignaal wordt uitge- . 5 zonden dat bij ontvangst in de onderstations het begin van een periode aangeeft welke in een opeenvolging van tijdsleuven van onderling gelijke duur is verdeeld, waarbij die onderstations, die een datapakket voor overdracht naar het hoofdstation gereed hebben, dit pakket in een willekeurig uit genoemde opeenvolging van tijdsleuven geselecteerde tijd- 10 sleuf naar het hoofdstation overdragen, en waarbij het hoofdstation onderscheid maakt tusen onverminkt en verminkt overgedragen pakketten, en de onverminkt overgedragen pakketten in een geheugen worden geregistreerd om vervolgens door het hoofdstation ter bevestiging van de goede ontvangst na elkaar via genoemd ander kanaal te worden uitgezonden, 15 met het kenmerk, dat in het hoofdstation op basis van de voorgeschiedenis van onverminkt overgedragen pakketten en verminkt overgedragen pakketten een schatting wordt gemaakt van het aantal onderstations dat, aan het begin van de volgende periode, een pakket voor overdracht gereed heeft, en dat het aantal tijdsleuven wordt aangepast op basis van genoemde 20 schattting.

2. Werkwijze volgens conclusie 1, waarbij genoemde periode is onderverdeeld in een aantal opeenvolgende frames, die elk in een vast aantal tijdsleuven zijn onderverdeeld, en waarbij door de onderstations in ieder frame in een willekeurig geselecteerde tijdsleuf een 25 datapakket kan worden uitgezonden, met het kenmerk, dat genoemde aanpassing van het aantal tijdsleuven wordt gerealiseerd door variatie van het aantal frames binnen genoemde periode.

3. Werkwijze volgens conclusie 1, waarbij genoemde periode is onderverdeeld in een aantal opeenvolgende frames, die elk in een 30 aantal tijdsleuven zijn onderverdeeld, en waarbij door de onderstations in ieder frame in een willekeurig geselecteerde tijdsleuf een datapakket kan worden uitgezonden, met het kenmerk, dat genoemde aanpassing van het aantal tijdsleuven wordt gerealiseerd door variatie van het aantal tijdsleuven per frame.

4. Werkwijze volgens conclusie 2 of 3, waarbij het door het hoofdstation uitgezonden synchronisatiesignaal bij ontvangst in de on-derstations het begin van elk van de frames aangeeft, met het kenmerk, 80 0 0 9 41 -T3·- — — r» ·* . ^ PHN 9693 9 dat het synchronisatiesignaal wordt gevormd door tenminste een eerste in gecodeerde vorm overgedragen getalwaarde welke het aantal frames per periode aangeeft en tenminste een tweede in gecodeerde vorm overgedragen getalwaarde welke de rangorde van het desbetreffende frame binnen de 5 periode aangeeft.

5. Werkwijze volgens conclusie 4, met het kenmerk, dat de mogelijkheid tot selectie van een tijdslot in die onderstations, die eerst tijdens of na verloop van het eerste frame van een periode een pakket voor overdracht gereed hebben, wordt geblokkeerd voor de duur 10 van de desbetreffende periode.

6. Werkwijze volgens conclusie 1 en 2 of 3, met het kenmerk, dat het in het hoofdstation geschatte aantal onderstations dat aan het begin van een periode een pakket voor overdracht gereed heeft, telkens op basis van de uitkomst van een voorafgaand frame wordt ge- 15 corrigeerd (up-dated), en dat dit gecorrigeerde aantal bepalend is voor het aantal tijdsloten van het volgende frame respectievelijk: het al of niet toevoegen van een frame aan de desbetreffende periode.

7. Systeem voor de radiooverdracht van datapakketten van meerdere onderstations naar een hoofdstation via een voor de overdracht 20 van deze pakketten gemeenschappelijke kanaal, volgens de werkwijze van conclusie 1, waarbij het hoofdstation is voorzien van middelen met behulp waarvan via een ander kanaal een synchronisatiesignaal dat het begin van een periode aangeeft wordt uitgezonden en waarbij de onderstations middelen bevatten die bij ontvangst van het synchronisatiesig-25 naai de genoemde periode onderverdelen in een aantal opeenvolgende tijd-sleuven van onderling gelijke tijdsduur teneinde desgewenst in een willekeurig uit genoemde opeenvolging van tijdsleuven geselecteerde tijdsleuf een datapakket te kunnen overdragen, met het kenmerk, dat het hoofdstation eerste besturingsmiddelen bevat die op basis van de voorge-30 schiedenis van onverminkt en verminkt overgedragen pakketten een schatting maken van de mate van toe- of afname van het aantal pakketten dat voor overdracht naar het hoofdstation gereed is en die aan de hand van deze sehattting het aantal tijdsleuven per periode bepaalt welk aantal in gecodeerde vorm via genoemd andere kanaal als zijnde synchronisatie-35 signaal wordt overgedragen naar de onderstations, alsmede middelen welke genoemde geschatte waarde bijwerkt telkens met het resultaat van de voorgaande periode. 800 0 9 41