Die Erfindung betrifft eine Kennungscodierungseinrichtung zur Zuordnung einer Kennung zu einer Eiementiiste zum Zweck der Datenverteiiung in einem Netzwerk, wobei die Elementliste eine Mehrzahl von aus einer Elementmenge ausgewählten Elementen aufweist, wobei jedes Element durch eine ganze Zahl repräsentiert ist und wobei die Elementmenge eine vorbestimmte Gesamtzahl von Elementen aufweist. Des Weiteren betrifft die vorliegende Erfindung eine Kennungsdecodierungseinrichtung zur Zuordnung einer Elementliste zu einer Kennung zum Zwecke der Verteilung von Daten in einem Netzwerk, wobei die Kennung eine ganze Zahl ist, wobei die zu ermittelnde Elementliste eine Mehrzahl von aus einer Elementmenge ausgewählten Elementen aufweist, wobei jedes Element durch eine ganze Zahl repräsentiert ist und wobei die Elementmenge eine vorbestimmte Gesamtzahl von Elementen aufweist. Darüber hinaus betrifft die vorliegende Erfindung eine Cachezuordnungseinrichtung, eine Gruppencodierungseinrichtung, eine Koordinierungseinrichtung und eine Dateisystemeinrichtung, die jeweils wenigstens eine Kennungsdecodierungsein- richtung oder eine Kennungsdecodierungseinrichtung aufweisen.

Die Verteilung von großen Datenmengen an Endgeräte in paketvermittelten Netzwerken, insbesondere in Mobilfunknetzen, findet derzeit hauptsächlich durch so genannte Punkt zu Punkt- Verbindungen statt. Jedes der Endgeräte kann zu diesem Zweck Verbindungen über das Netzwerk mit einem Server, auf dem die Daten abgelegt sind, aufbauen. Dies kann beispielsweise mittels TCP/I P-Verbindungen geschehen, mittels derer Dateien von dem Server herunterladbar sind. Eine Anforderung über derartige Verbindungen führt dazu, dass die jeweils angeforderte Datei vollständig übertragen werden muss. Dies ist auch dann der Fall, wenn mehrere Endgeräte dieselbe Datei anfordern. Das Netzwerk wird in diesem Fall für jedes Endgerät erneut mit den Daten der Datei beiastet, wodurch die benötigte Bandbreite erhöht wird.

Es sind verschiedene Lösungsansätze dafür bekannt, die Bandbreite für derartige Dateiübertragungen für den Fall zu reduzieren, dass es sich bei den großen Datenmengen um einen Datenbestand handelt, aus dem unterschiedliche Endgeräte häufig dieselben Daten anfordern werden. So ist es beispielsweise möglich, zu Zeiten, in denen das Netzwerk nur wenig genutzt wird, häufig angeforderte Elemente des Datenbestands vorsorglich an die Endgeräte zu übertragen. Die Endgeräte legen diese Elemente, die im Wesentlichen Dateien, Datenblöcke oder Dateifragmente sind, in einem Cachespeicher ab.

Fordern zwei Endgeräte nunmehr Elemente an, die in dem jeweils anderen Endgerät bereits in dem Cachespeicher vorgehalten werden, so kann der Server die beiden angeforderten Elemente miteinander zu einem einzelnen Datenblock mit der Länge eines einzelnen Elements verknüpfen und diesen als Broadcast an alle Endgeräte gleichzeitig versenden. Die Endgeräte können anschließend unter Zuhilfenahme der bereits vorhandenen Elemente in ihrem Cachespeicher aus dem so übermittelten Datenblock die angeforderten Daten rekonstruieren. Dieses Verfahren ist gegebenenfalls auch dazu geeignet, mehr als zwei Datenblöcke gemeinsam zu codieren und somit für die Übertragung einer Vielzahl von Datenblöcken lediglich Bandbreite entsprechend in etwa einem einzigen Datenblock zu verbrauchen.

Beispiele für derartige Verfahren finden sich in der US 2015/0207881 A1 , der US

2015/0207895 A1 , der US 2015/0207896 A1 und der US 2012/0254459 A1 . Des Weiteren sind aus der DE 10 2014 102 898 A1 Verfahren und Vorrichtungen zur Verteilung großer Datenmengen bekannt.

Um die Identifikation der in einem Cachespeicher eines Endgeräts vorhandenen Elemente bzw. Datenblöcke und/oder der Endgeräte, die ein bestimmtes Element in ihrem Cachespeicher vorhalten, zu ermöglichen, werden diese Elemente oder Endgeräte jeweils als Mengen oder Listen zusammengefasst und eindeutig identifizierbaren Elementemengen o- der -listen Kennungen zugeordnet, mittels derer die Ermittlung der zu verknüpften Elemente vereinfacht wird. Für die damit verbundenen Zuordnungsvorgänge wird entweder eine große Rechenleistung zum Durchlaufen aller möglichen Zuordnungen oder eine große Menge Speicher zur Ablage vorberechneter Zuordnungen benötigt.

Die Erfindung geht auf die Aufgabe zurück, Vorrichtungen und Verfahren zu schaffen, welche die oben beschriebene Datenverteilung ressourcenschonender durchführen und an die besonderen Bedürfnisse von Endgeräten in Mobilfunknetzen angepasst sind.

Zur Lösung werden eine Kennungscodierungseinrichtung gemäß Anspruch 1 und eine Ken- nungsdecodierungseinrichtung gemäß Anspruch 2 vorgeschlagen. Diese Einrichtungen haben gegenüber den bekannten Lösungen den Vorteil, dass nicht alle theoretisch möglichen Zuordnungen von Kennungen zu Elementlisten kombinatorisch ermittelt und verifiziert werden müssen. Darüber hinaus ist der Speicherbedarf auf wenige kompakt speicherbare Variablen beschränkt. Somit ist sowohl die zum Aufbau und der Verwendung der Vorrichtungen notwendige Rechenleistung als auch der Speicherbedarf reduziert.

Die Aufgabe wird darüber hinaus durch eine Cachezuordnungseinrichtung gemäß Anspruch 3 gelöst, die eine Kennungsdecodierungseinrichtung aufweist, mittels derer aus einer Anzahl von Gruppenkennungen, einem Codierungsparameter, einer Gruppenkennung, einer Datenblockkennung und einer Dateikennung eine Elementliste erzeugbar ist, in der Gruppenkennungen enthalten sind, deren Endgeräte einen durch die Datenblockkennung identifizierbaren Datenblock Zwischenspeichern sollen. Die Cachezuordnungseinrichtung weist vorteilhaft eine Entscheidungseinrichtung auf, die zum Auffinden der Gruppenkennung in der Elementliste ausgebildet ist, wobei die Cachezuordnungseinrichtung zur Erzeugung eines Zwischenspeichersignals ausgebildet ist, sofern die Gruppenkennung in der Elementliste enthalten ist und wobei die Cachezuordnungseinrichtung zur Erzeugung eines Nichtzwischenspeichersignals ausgebildet ist, sofern die Gruppenkennung nicht in der Elementliste enthalten ist. Das Zwischenspeichersignal kann beispielsweise ein Endgerät dazu anweisen, den Datenblock in einen Cachespeicher aufzunehmen und das Nichtzwischenspeichersignal kann ein Endgerät dazu anweisen, den Datenblock nicht in den Cachespeicher aufzunehmen Beispielsweise kann ein in seinen verfügbaren Ressourcen beschränktes Endgerät mittels der Cachezuordnungsvorrichtung vereinfacht ermitteln, ob es einen ihm übermittelten Datenblock Zwischenspeichern soll.

Des Weiteren wird die Aufgabe durch eine Gruppencodierungseinrichtung zum Ermitteln einer Liste von gemeinsam codierbaren Anforderungen aus einer Liste von wartenden Anforderungen gemäß Anspruch 4 gelöst, wobei jede Anforderung wenigstens eine Gruppenkennung und eine Datenblockkennung aufweist, wobei die Gruppencodierungseinrichtung zur Verarbeitung einer ausgewählten Anforderung aufweist: eine Kennungsdecodierungsein- richtung zum Ermitteln einer Liste der Gruppenkennungen, in deren zugeordneten Cachespeichern der Datenblock mit der angeforderten Kennung vorgehalten wird, eine Kandidatenermittlungseinrichtung zum Ermitteln einer Liste aller Gruppenkennungen und Listen, die sich durch Entnehmen einer Gruppenkennung aus der Liste und Einsetzen der Gruppenkennung der ausgewählten Anforderung in die Liste ergeben; eine Kennungscodierungseinnchtung zum Ermitteln einer Liste von Gruppenkennungen und Datenblockkennungen aus der Liste, wobei die Kennungscodierungseinnchtung jeder Liste aus der Liste eine Kennung zuweist, wobei die Kennungscodierungseinnchtung gemäß Patentanspruch 1 ausgebildet ist, und eine Anforderungsauswahleinrichtung zum Ermitteln einer Liste mittels Verknüpfung der Liste und der Liste von wartenden Anforderungen, dass je Eintrag (i',c') der Liste höchstens ein Eintrag der Liste der Form (i, f, c) derart zur Aufnahme in die Liste ausgewählt wird, dass i'=i und c'=c. Dadurch ist insbesondere die Ermittlung von gemeinsam codierbaren Datenblöcken anhand der angeforderten Datenblöcke auf ressourcenschonende Weise möglich.

Zur Lösung der Aufgabe wird auch eine Kommunikationseinrichtung zum Umsetzen von Informationen über einen gemeinsam codierten Datenblock in Kopfdaten gemäß Anspruch 5 vorgeschlagen, wobei der Kommunikationseinrichtung als Informationen über den Datenblock eine Liste von Gruppenkennungen, eine Liste von Dateikennungen sowie ein Systemparameter übergeben werden, wobei die Kommunikationseinrichtung eine Kennungscodie- rungseinrichtung zur Umsetzung der Liste von Gruppenkennungen in einen Index und eine Kopfdatenerzeugungseinrichtung zur Umsetzung des Index zusammen mit der Liste von Dateikennungen in Kopfdaten aufweist. Durch die Umsetzung der Liste von Gruppenkennungen in einen Index wird die über ein Netzwerk zu übertragende Datenmenge reduziert und somit der mögliche Nutzdatenanteil in diesem Netzwerk verbessert.

Zur Lösung der Aufgabe wird gemäß Anspruch 6 auch eine Dateisystemeinrichtung zum Zuweisen einer lokalen Datenblockkennung zu einer Datenblockkennung, mit einer Ken- nungsdecodierungseinrichtung zum Erstellen einer Liste von Gruppenkennungen der den mit der Datenblockkennung bezeichneten Datenblock vorhaltenden Gruppen, einer Abbil- dungseinrichtung zum Umsetzen der Liste und einer Kennungscodierungseinrichtung zum Erhalten der lokalen Datenblockkennung aus der umgesetzten Liste, vorgeschlagen. Die Kennungsdecodierungseinrichtung und/oder die Kennungscodierungseinrichtung sind insbesondere gemäß einer hierin bzw. zuvor beschriebenen Ausführungsart ausgebildet.

Die Aufgabe wird darüber hinaus durch eine Dateisystemeinrichtung gemäß Anspruch 7 zum Ermitteln einer Datenblockkennung zu einer lokalen Datenblockkennung, mit einer Kennungsdecodierungseinrichtung zum Erstellen einer Liste von Gruppenkennungen, einer Abbildungseinrichtung zum Umsetzen der Liste und einer Kennungscodierungseinrichtung zum Erhalten der Datenblockkennung aus der umgesetzten Liste gelöst. Die Kennungsde- codierungseinrichtung und/oder die Kennungscodierungseinrichtung sind insbesondere gemäß einer hierin bzw. zuvor beschriebenen Ausführungsart ausgebildet.

Zur Lösung werden ferner komplementäre Verfahren gemäß den Ansprüchen 8 und 10 vorgeschlagen. Diese Verfahren haben gegenüber den bekannten Lösungen den Vorteil, dass nicht alle möglichen Zuordnungen kombinatorisch ermittelt und verifiziert werden müssen. Darüber hinaus ist der Speicherbedarf auf wenige kompakt speicherbare Variablen beschränkt. Somit ist sowohl die für die Durchführung des Verfahrens notwendige Rechenleistung als auch der Speicherbedarf reduziert.

Vorteilhaft kann gemäß den Ansprüchen 9 und 1 1 vorgesehen sein, dass anstatt einer individuellen Berechnung der Binomialkoeffizienten eine vorberechnete Tabelle dieser Koeffizienten zum Einsatz kommt. Hierdurch wird die notwendige Rechenleistung weiter reduziert, indem eine geringfügige Vergrößerung des Speicherbedarfs in Kauf genommen wird.

Die Aufgabe wird darüber hinaus durch ein Netzwerk gemäß Anspruch 12 gelöst, bei dem wenigstens ein Endgerät eine Zuordnungseinrichtung aufweist, die zur Durchführung eines der oben genannten Verfahren ausgebildet ist.

Ebenso wird die Aufgabe durch ein Netzwerk gemäß Anspruch 13 gelöst, bei dem wenigstens ein Server an das Netzwerk angeschlossen ist, der eine Zuordnungseinrichtung aufweist, die zur Durchführung eines der oben genannten Verfahren ausgebildet ist.

Die Erfindung wird nachfolgend anhand von Zeichnungen näher erläutert, welche die Erfindung lediglich schematisch zeigen und den Schutzbereich nicht beschränken sollen. Es zeigen im Einzelnen:

Fig. 1 ein Flussdiagramm eines Verfahrens zur Ermittlung einer Kennung zu einer Elementliste gemäß einer ersten Ausführungsform der Erfindung;

Fig. 2 ein Flussdiagramm eines Verfahrens zur Ermittlung einer Elementliste zu einer Kennung gemäß einer ersten Ausführungsform der Erfindung;

Fig. 3 eine Übersicht über ein Netzwerk zur Verteilung von Daten an Endgeräte in dem Netzwerk;

Fig. 4 eine Übersicht über Endgeräte und deren Speichereinrichtungen in dem Netzwerk;

Fig. 5 eine Übersicht über Endgeräte und deren Speichereinrichtungen in einem weiteren Netzwerk;

Fig. 6 einen schematischen Aufbau einer Cachezuordnungseinrichtung gemäß einer Ausführungsform der vorliegenden Erfindung; Fig. 7 einen schematischen Aufbau einer Gruppencodierungseinrichtung gemäß einer Ausführungsform der vorliegenden Erfindung;

Fig. 8 einen schematischen Aufbau einer Koordinierungseinrichtung gemäß einer Ausführungsform der vorliegenden Erfindung;

Fig. 9 einen schematischen Aufbau einer Dateisystemeinrichtung gemäß einer Ausführungsform der vorliegenden Erfindung und

Fig. 10 einen schematischen Aufbau einer Dateisystemeinrichtung komplementär zu der Dateisystemeinrichtung aus Fig. 9.

Das in Fig. 3 gezeigte Netzwerk 10 ist beispielsweise als Mobilfunknetzwerk ausgestaltet. Das Mobilfunknetzwerk 10 weist eine Basisstation 12 auf, die mittels eines Mediums 14, beispielsweise mittels elektromagnetischer Wellen, mit einer Vielzahl von Endgeräten 16a- 16f kommunizieren kann. An das Netzwerk 10 ist eine Datenbereitstellungseinrichtung (Server) 18 angeschlossen, die Daten zum Abruf durch die Endgeräte 16a-16f bereithält.

Die Endgeräte 16a-16f können über das Mobilfunknetzwerk 10, beispielsweise unter Verwendung des I P-Protokolls, Daten von der Datenbereitstellungseinrichtung 18 abrufen. Diese Daten werden anschließend über das Mobilfunknetzwerk 10 an die Endgeräte 16a- 16f übermittelt. Das Medium 14 verfügt über eine begrenzte Bandbreite, wodurch die Menge der je Zeiteinheit übertragbaren Daten begrenzt ist. In einem drahtlosen Medium 14 teilen sich die dieses benutzenden Endgeräte 16a-16f die verfügbare Bandbreite. Dadurch kann die Übertragung der von einem der Endgeräte 16a-16f angeforderten Daten verlangsamt sein, wenn von den Endgeräten 16a-16f große Mengen Daten angefordert werden.

Die Menge der angeforderten Daten in real existierenden Mobilfunknetzwerken 10 ist gewöhnlich von der Tageszeit abhängig. So werden beispielsweise Videos, die besonders große Datenmengen umfassen, häufig abends angefordert, so dass Mobilfunknetzwerke 10 zu dieser Zeit besonders ausgelastet sind. In den frühen Morgenstunden hingegen werden nur wenige Daten angefordert, so dass in dem Mobilfunknetzwerk 10 zu diesem Zeitpunkt große ungenutzte Kapazitäten vorgehalten werden. Aus diesem Umstand ergibt sich das Bestreben, häufig angeforderte Daten, beispielsweise Daten einer Online- Videobibliothek, zu Zeiten vorsorglich zu übermitteln, in denen die Auslastung des Mobilfunknetzes 10 gering ist, so dass eine erneute Übertragung zu Zeiten, zu denen die Auslastung des Mobilfunknetzes 10 hoch ist, nicht mehr notwendig ist.

Gewöhnlich weisen Videobibliotheken allerdings so viele Daten auf , dass ein vollständiges Zwischenspeichern auf mobilen Endgeräten 16a-16f aufgrund der beschränkten Größe der in diesen enthaltenen Speichereinrichtungen nicht praktisch umsetzbar ist. Darüber hinaus sind derzeit die in Mobilfunknetzwerken 10 verfügbaren Bandbreiten nicht für eine regelmäßige vorsorgliche Übertragung derartiger Datenmengen geeignet.

Insbesondere in Mobilfunknetzwerken 10 ist das Medium 14 so ausgestaltet, dass ein und dieselben Daten an alle Endgeräte 16a-16f gleichzeitig gesendet werden können (Rundsendung, Broadcast), wobei die Bandbreite für die Übertragung lediglich einmal für alle Endgeräte 16a-16f und nicht für alle Endgeräte 16a-16f separat erneut benötigt wird.

Diesen Umständen trägt die Anwendung der sogenannten Indexkodierung (index coding) Rechnung. Diese kann auf den Endgeräten 16a-16f beispielsweise so umgesetzt werden, wie es in Fig. 4 gezeigt ist. Jedes der Endgeräte 16a-16f weist eine Speichereinrichtung 20a-20f, die auch Cachespeicher genannt wird, auf, in der Datenblöcke 22 ablegbar sind. Jeder der Datenblöcke 22 kann Teil einer größeren Datei, beispielsweise einer Videodatei, oder in sich selbst eine abgeschlossene Datei sein. Jeder der Datenblöcke 22 ist somit ein Element einer Gesamtmenge von Elementen, die in der Datenbereitstellungseinrichtung 18 abgelegt sind. Um die Datenblöcke 22 eindeutig zu identifizieren, ist jedem der Datenblöcke 22 beziehungsweise Elemente eine ganze Zahl als Datenblockkennung c zugeordnet.

In der Speichereinrichtung 20a des Endgeräts 16a sind beispielsweise die Datenblöcke 22 mit den Datenblockkennungen 1 , 8, 17, 28 sowie einige weitere abgelegt. In der Speichereinrichtung 20b des Endgeräts 16b sind beispielsweise die Datenblöcke 22 mit den Datenblockkennungen 4, 7, 1 1 , 17 sowie einige weitere abgelegt. Fordert nunmehr das Endgerät 16a den Datenblock 22 mit der Datenblockkennung c=4 und gleichzeitig das Endgerät 16b den Datenblock 22 mit der Datenblockkennung c=1 an, so können diese beiden Datenblöcke 22, beispielsweise in der Datenbereitstellungseinrichtung 18, mathematisch miteinander kombiniert werden, beispielsweise mittels einer exklusiv-oder-Operation (XOR). Der daraus resultierende codierte Datenblock 1 +4 ist mit dem Datenblock 22 mit der Datenblockkennung c=4 so kombinierbar, dass daraus der Datenblock 22 mit der Datenblockkennung c=1 erhältlich ist. Des Weiteren ist der Datenblock 1 +4 mit dem Datenblock 22 mit der Da- tenblockkennung c=1 so kombinierbar, dass daraus der Datenblock 22 mit der Datenblock- kennung c=4 erhältlich ist.

Der Datenblock 1 +4 nimmt durch die Möglichkeit der Rundsendung die Bandbreite des Mediums 14 nur einmal in Anspruch. Dennoch haben sowohl das Endgerät 16a als auch das Endgerät 16b die angeforderten Daten erhalten. In diesem Fall wird die benötigte Bandbreite also um die Hälfte reduziert.

Damit dieses Verfahren anwendbar ist, muss die Datenbereitstellungseinrichtung 18 Informationen darüber erhalten, welche Datenblöcke 22 in welchen Endgeräten 16a-16f abgelegt wurden und welche Kombination von Anforderungen sich zu kombinierten Datenblöcken zusammenfassen lässt. Um diese Informationen effizient übermitteln und verarbeiten zu können, werden bei der Indexcodierung Listen zu Indizes codiert. Beispielsweise kann einer Liste, die als Elemente alle Endgeräte 16a-16f aufweist, die einen Datenblock 22 mit einer bestimmten Datenblockkennung c in ihrer Speichereinrichtung 20a-20f zwischengespeichert haben, ein Index in Form einer Kennung zugeordnet werden. Dieser Kennung ist dadurch auch eindeutig eine Elementliste zugewiesen. Dadurch können beispielsweise Endgeräte 16a-16f zu Gruppen zusammengefasst werden, denen jeweils eine Gruppenken- nung i zugeordnet ist. Die Liste beziehungsweise die Kennung kann auch andere Informationen repräsentieren, beispielsweise welche Datenblöcke 22 in der Speichereinrichtung 20a-20f eines bestimmten Endgeräts 16a-16f abgelegt sind.

Die Zuordnung zwischen der Elementliste (subset) und der Kennung (index) kann beispielsweise durch Abzählen nach dem folgenden in Pseudocode beschriebenen Verfahren durchgeführt werden: subset = index to subset(index, N, K) {

count <- 1

for (i = 1 :2 ^Λ Ν-1 ) {

set <- binary-to-set( number-to-binary(i) )

if (Isetl == K) { count<- count +1 }

if (count == index) { return set }

}

}

index = subset to index(subset _: N, K) {

count <- 1 binary-subset <- set-to-binary(subset)

for (i = 1 :2 ^Λ Ν-1 ) {

set <- binary-to-set( number-to-binary(i) )

if (iset! == K) {

count <- count +1

if ( binary-subset == number-to-binary(i) ) { return i }

}

}

}

Bei diesem Verfahren zur Zuordnung von Elementlisten zu Kennungen werden im Wesentlichen alle möglichen Zuordnungen ausprobiert, bis die korrekte Zuordnung gefunden wurde. Dies erfordert eine große Rechenleistung.

Alternativ dazu kann die Zuordnung von Elementlisten zu Kennungen im Vorfeld berechnet und dann als vorberechnete Zuordnung abgespeichert werden. Dies benötigt viel Speicherplatz. Bereits bei moderaten Mengen von Endgeräten 16a-16f und Datenblöcken 22 können zur Speicherung dieser vorberechneten Zuordnung über 50GB Daten anfallen. Derartig große Datenstrukturen sind nur schwer in mobilen Endgeräten 16a-16f vorzuhalten.

Die in Fig. 1 gezeigte Kennungscodierungseinrichtung 30 ist zur Ausführung eines im Folgenden beschriebenen Verfahrens zur Zuordnung einer Kennung zu einer bekannten Elementliste ausgebildet. Der Kennungscodierungseinrichtung 30 wird eine Elementliste S übergeben. Die Elementliste S enthält eine Mehrzahl von Elementen, wobei jedes Element durch eine ganze Zahl repräsentiert wird. Die Elemente sind einer Elementmenge entnommen, die alle möglichen Elemente, beispielsweise alle Datenblöcke 22, repräsentiert. Diese Elementmenge weist eine vorbestimmte Gesamtzahl N von Elementen auf.

Ausgehend von der Elementliste S wird in einem ersten vorbereitenden Schritt 100 zunächst eine Anzahl der Elemente, die in der Elementliste S enthalten sind, ermittelt. Diese Anzahl wird gewöhnlich Kardinalität genannt. Das Ergebnis wird in einem Kardinalitätszäh- ler k abgelegt. In einem zweiten vorbereitenden Schritt 101 wird die Zahl O in einem Begrenzungszähler b abgelegt. In einem dritten vorbereitenden Schritt 102 wird die Zahl O in einem Zwischenspeicher c abgelegt.

Die vorbereitenden Schritte 100-102 können in jeder beliebigen Reihenfolge ausgeführt werden. In einem ersten Schritt 103 wird das kleinste Element der Elementliste S ermittelt und in einem Elementzwischenspeicher m abgelegt. Das in dem Elementzwischenspeicher m abgelegte kleinste Element der Elementliste S wird in einem zweiten Schritt 104 aus der Elementliste S entfernt.

In einem dritten Schritt 106 wird der Wert des Elementzwischenspeichers m und des Begrenzungszählers b verglichen. Sind die Werte nicht identisch, so wird mit einem weiter unten beschriebenen achten Schritt 108 fortgefahren.

In einem vierten Schritt 1 14 wird der Kardinalitätszähler k um 1 verringert. In einem daran anschließenden fünften Schritt 1 16 wird der Wert des Kardinalitätszählers k mit O verglichen. Ist der Wert des Kardinalitätszählers k gleich 0, so wird mit einem weiter unten beschriebenen Abschlussschritt 122 fortgefahren.

In einem sechsten Schritt 1 18 wird der Begrenzungszähler b um 1 erhöht.

In einem siebten Schritt 120 wird festgestellt, ob der Begrenzungszähler b der Gesamtzahl N von Elementen entspricht. Ist dies der Fall, so wird mit dem Abschlussschritt 122 fortgefahren. Ist dies nicht der Fall, so wird mit dem ersten Schritt 103 fortgefahren.

In dem achten Schritt 108 wird ein Binomialkoeffizient wie folgt berechnet ^~ ^ ^~ ^ und zu dem Zwischenspeicher c hinzuaddiert.

In einem neunten Schritt 1 10 wird der Begrenzungszähler b um 1 erhöht. In einem zehnten Schritt 1 12 wird der Begrenzungszähler b mit der Gesamtzahl N verglichen. Sind die Werte identisch, so wird mit dem Abschlussschritt 122 fortgefahren. Ansonsten wird mit dem dritten Schritt 106 fortgefahren.

In dem Abschlussschritt 122 wird der Inhalt des Zwischenspeichers c übergeben.

Er stellt die ermittelte Kennung dar und wird von der Kennungszuordnungseinrichtung 30 beispielsweise als der Elementliste S zugeordnete Kennung c ausgegeben. Diese Kennung kann beispielsweise eine globale und/oder lokale Datenblockkennung c sein, die einen Datenblock 22 beschreibt, der in den in der Elementliste S enthaltenen Endgeräten 16a-16f zwischengespeichert ist. Die in Fig. 2 gezeigte Kennungsdecodierungseinrichtung 40 ist zur Ausführung eines im Folgenden beschriebenen Verfahrens zur Zuordnung einer Elementliste S zu einer bekannten Kennung ausgebildet. Der Kennungsdecodierungseinrichtung 40 wird eine Kennung (beispielsweise eine Datenblockkennung c) in Form einer ganzen Zahl übergeben und in einem Kennungszwischenspeicher c abgelegt. Die zu ermittelnde Elementliste S soll eine vorbestimmte Kardinalität aufweisen, die in einem Kardinalitätszähler k abgelegt ist. Darüber hinaus weist eine Elementmenge, aus der die Elemente der Elementliste S ausgewählt werden sollen, eine vorbestimmte Gesamtzahl N von Elementen auf.

In einem ersten vorbereitenden Schritt 200 wird die Zahl 0 in einem Begrenzungszähler b und in einem zweiten vorbereitenden Schritt 201 in einem Elementzähler m abgelegt. In einem dritten vorbereitenden Schritt 202 wird eine zunächst leere Liste als Elementliste S abgelegt.

Die vorbereitenden Schritte 200-202 können in jeder beliebigen Reihenfolge

durchgeführt werden.

In einem ersten Schritt 204 wird ein Binomialkoeffizient ^ ^{~ ό ~ 1} berechnet und in einem Zwischenspeicher z abgelegt.

In einem zweiten Schritt 206 werden der Wert des Kennungszwischenspeichers c und des Zwischenspeichers z miteinander verglichen. Sofern der Kennungszwischenspeicher c einen Wert aufweist, der größer oder gleich dem Wert des Zwischenspeichers z ist, wird mit einem weiter unten beschriebenen sechsten Schritt 214 fortgefahren.

In einem dritten Schritt 208 wird der Wert des Kennungszwischenspeichers c um den Wert des Zwischenspeichers z verringert beziehungsweise reduziert.

In einem vierten Schritt 210 wird der Begrenzungszähler b um 1 erhöht.

In einem fünften Schritt 212 wird der Wert des Begrenzungszählers b mit der Gesamtzahl N verglichen. Sofern die Werte gleich sind, wird mit dem ersten Schritt 204 fortgefahren, ansonsten wird mit einem Abschlussschritt 220 fortgefahren.

In dem Abschlussschritt 220 wird die Elementliste S von der Kennungsdecodierungseinrich- tung 40 als Ergebnis ausgegeben. In dem sechsten Schritt 214 wird der Wert des Elementzählers m zu der Elementliste S hinzugefügt.

In einem siebten Schritt 215 wird der Elementzähler m um 1 erhöht.

In einem achten Schritt 216 wird der Kardinalitätszähler k um 1 verringert.

In einem neunten Schritt 218 wird der Wert des Kardinalitätszählers k mit 0 verglichen und mit dem Abschlussschritt 220 fortgefahren, wenn dies der Fall ist. Ansonsten wird mit dem vierten Schritt 210 fortgefahren.

Das Ausgeben als Ergebnis in den Schritten 122, 220 kann beispielsweise durch Übergabe an eine weiterverarbeitende Einrichtung oder durch Ablage in einem Speicherbereich erfolgen.

Die beiden Verfahren 100-122, 200-220 sind insofern komplementär, als sie jeweils die Umkehrung voneinander darstellen.

Die Verfahren 100-122, 200-220 können beispielsweise in Anweisungen an eine

Rechenmaschine, beispielsweise Programmcode, umgesetzt werden, die eine

Rechenmaschine dazu veranlassen, die Verfahren 100-122, 200-220 auszuführen. Die Verfahren 100-122, 200-220 werden nicht notwendigerweise in ein und derselben Einrichtung ausgeführt. Beispielsweise kann das erste Verfahren 100-122 in einer Kennungscodierungseinrichtung 30 eines Endgeräts 16a-16f ausgeführt werden, oder beispielsweise das zweite Verfahren 200-220 in einer Kennungsdecodierungseinrichtung 40 der Datenbereitstellungseinrichtung 18 ausgeführt werden oder umgekehrt. Es ist ebenso denkbar, dass die Verfahren 100-122, 200-220 zur Zuordnung unterschiedlicher Aspekte einer Verteilung von Datenblöcken 22 in verschiedenen Einrichtungen des Netzwerks 10 ausgeführt werden.

Das vorliegend gezeigte Netzwerk 10 weist lediglich eine einzige Datenbereitstellungseinrichtung 18 sowie sechs Endgeräte 16a-16f auf. Die Verfahren 100-122, 200-220 und somit auch die Kennungscodierungseinrichtung 30 und die Kennungsdecodierungseinrichtung 40 sind nicht auf diese Anzahlen beschränkt. Es ist vielmehr möglich, eine beliebige Anzahl von Datenbereitstellungseinrichtungen 18 sowie eine beliebige Anzahl von Endgeräten 16a- 16f in dem Netzwerk 10 vorzuhalten. Das Netzwerk 10 bildet ein Datenverteilungssystem. In dem Netzwerk 10 kann jeder Benutzer beziehungsweise jedes Endgerät 16a-16f bestimmte Abschnitte (Datenblöcke) von Dateien zur Auslieferung von der Datenbereitstellungseinrichtung 18 anfordern. Die Datenbereitstellungseinrichtung 18 kann beispielsweise eine Datenbibliothek mit einer Vielzahl von großen Dateien, beispielsweise eine Video- oder Audiobibliothek, aufweisen. Jede der Dateien ist in Datenblöcke (Chunks) 22 unterteilt, denen jeweils eine Datenblockkennung (chunk id) c zugewiesen ist. Jeder der Datenblöcke 22 kann von jedem Endgerät 16a-16f angefordert werden. Jedes Endgerät 16a-16f kann in seinem Cachespeicher 20a-20f einige oder alle Datenblöcke 22 einiger Video-, Audio- oder Datendateien lokal vorhalten. Das bedeutet, dass diese Datenblöcke 22 beispielsweise zu einem vorbestimmten Zeitpunkt vorsorglich an das Endgerät 16a-16f übermittelt werden, da erwartet wird, dass sie zu einem späteren Zeitpunkt benötigt werden.

Zur Auswahl der von jedem Endgerät 16a-16f in seinem Cachespeicher 20a-20f vorzuhaltenden Datenblöcke 22 kann beispielsweise die Datenbereitstellungseinrichtung 18 eine Auswahleinrichtung aufweisen, welche die Datenblöcke 22 aus der Gesamtmenge verfügbarer Datenblöcke 22 auswählt. Diese Auswahl kann beispielsweise mittels eines Auswahlverfahrens durchgeführt werden.

Das Auswahlverfahren kann beispielsweise einen Verfahrensschritt aufweisen, in dem ein zufälliger Datenblock 22 ausgewählt wird. In einem weiteren Schritt kann dem Endgerät 16a-16f die Information übermittelt werden, diesen Datenblock 22 bei Übermittlung in den Cachespeicher 20a-20f aufzunehmen. Diese Schritte werden wiederholt, bis der Cachespeicher 20a-20f jedes Endgeräts gefüllt ist oder eine vorbestimmte Anzahl Datenblöcke 22 aufweist.

Sofern die Auswahl mittels eines derartigen Verfahrens durchgeführt wird, kann es nützlich sein, in der Datenbereitstellungseinrichtung 18 eine Liste vorzuhalten, in der abgespeichert ist, welches Endgerät 16a-16f in seinem Cachespeicher 20a-20f welche Datenblöcke 22 zwischenspeichert. Dadurch kann vermieden werden, dass die Liste der jeweils vorgehaltenen Datenblöcke 22 bei jedem Übertragungsvorgang erneut von dem Endgerät 16a-16f angefordert werden muss.

Ein weiteres Auswahlverfahren (siehe Fig. 5) kann darin bestehen, zunächst eine Mehrzahl von Endgeräten 50-55 mit Cachespeichern 60-65, die ähnlich oder genauso aufgebaut sind, wie die Endgeräte 16a-16f mit den Cachespeichern 20a-20f, zu einer Gruppe 70-73 zusammenzufassen, wobei jeder der Gruppen 70-73 eine Gruppenkennung (user id) i zugewiesen ist. Alle Endgeräte 50-55, die Mitglieder derselben Gruppe 70-73 sind, weisen in ihrem Cachespeicher 60-65 dieselben Datenblöcke 22 auf. Somit ist für jedes Endgerät 50- 55 nicht mehr der komplette Zustand des Cachespeichers 60-65 von der Datenbereitstellungseinrichtung 18 zu speichern, sondern lediglich die Zuordnung des jeweiligen Endgeräts 50-55 zu einer der Gruppen 70-73.

Die Anzahl der zu bildenden Gruppen 70-73 ist ein Systemparameter N des Datenverteilungssystems. Die Gruppenkennungen oder auch Nutzeridentifikatoren i sind ganze Zahlen, so dass i e {0, ... , /V - 1}. Jede dieser Gruppenkennungen definiert einen Cachezustand, das heißt eine bestimmte Menge von in dem Cachespeicher 60-65 vorzuhaltenden Datenblöcken 22, wobei jeder Datenblock 22 beispielsweise durch einen Dateiidentifikator f e {0, F - 1 } und/oder eine Datenblockkennung c e {0, C - ljeindeutig identifizierbar ist.

Ein wählbarer Systemparameter k e { 1, 2, ... } beeinflusst, in wie vielen Gruppen 70-73 jedes Dateifragment 22 in dem Cachespeicher 60-65 vorgehalten wird.

Zur Auswahl der in dem Cachespeicher 60-65 abzulegenden Datenblöcke 22 kann eine Cachezuordnungseinrichtung 300, wie sie in Fig. 6 gezeigt ist, vorgesehen sein. Die Cachezuordnungseinrichtung 300 erhält als Eingabeparameter die Systemparameter N und k, sowie eine Gruppenkennung i und eine Datenblockkennung c.

Die Cachezuordnungseinrichtung 300 weist eine Kennungsdecodierungseinrichtung 302 auf, die zur Durchführung des oben beschriebenen Verfahrens 200-220 zur Zuordnung einer Elementliste zu einer Kennung ausgebildet ist. Die Kennungscodierungseinrichtung 302 verarbeitet die Eingabeparameter N, k und c zu einer Liste S von Gruppenkennungen von Gruppen 70-73, in denen der Datenblock 22 mit der Datenblockkennung c vorgehalten werden soll.

Die Liste S wird an eine Entscheidungseinrichtung 304 übergeben, die prüft, ob die Gruppenkennung i, die als Eingabeparameter an die Cachezuordnungseinrichtung 300 übergeben wurde, in der Liste S enthalten ist. Stellt die Entscheidungseinrichtung 304 fest, dass die Gruppenkennung i in der Liste S enthalten ist, so erzeugt sie ein Ausgangssignal 306, das aussagt, dass der Datenblock 22 mit der Datenblockkennung c von den Endgeräten 50-55 der Gruppe mit der Gruppenkennung i gespeichert wird oder werden soll (Zwischen- speichersignal). Stellt die Entscheidungseinrichtung 304 hingegen fest, dass die Gruppen- kennung i nicht in der Liste S enthalten ist, so erzeugt sie ein Signal, das das Gegenteil aussagt (Nichtspeichersignal, Datenblock 22 wird nicht gespeichert).

Die Cachezuordnungseinrichtung 300 kann Teil der Datenbereitstellungseinrichtung 18 o- der des Endgeräts 50-55 sein. In der Bereitstellungseinrichtung 18 dient die Cachezuordnungseinrichtung 300 beispielsweise dazu, festzustellen, ob ein bestimmter Datenblock 22 an ein bestimmtes Endgerät 50-55 überhaupt übertragen werden muss oder bereits in diesem Endgerät 50-55 vorgehalten wird. In einem Endgerät 50-55 kann die Cachezuordnungseinrichtung 300 beispielsweise dazu dienen, zu bestimmen, ob ein empfangener Datenblock 22 in den Cachespeicher 60-65 aufgenommen werden soll oder nicht.

Die Auswahl der aufgrund von Anforderungen der Endgeräte 50-55 gemeinsam codierbaren Datenblöcke 22 wird mittels einer Gruppencodierungseinrichtung 400 durchgeführt, die in Fig. 7 gezeigt ist. Die Gruppencodierungseinrichtung 400 weist eine Kennungsdecodie- rungseinrichtung 402, eine Kandidatenermittlungseinrichtung 406, eine Kennungscodie- rungseinrichtung 408 sowie eine Anforderungsauswahleinrichtung 410 auf.

Zunächst werden durch die Datenbereitstellungseinrichtung 18 verschiedene Anforderungen, die von Endgeräten 50-55 gesendet wurden, gesammelt. Eine Anforderung umfasst beispielsweise die Gruppenkennung i des anfordernden Endgeräts 50-55 sowie die Datenbiockkennung c des angeforderten Datenblocks 22.

Zusätzlich kann eine Anforderung auch die Dateikennung f der angeforderten Datei umfassen. Die Anforderungen können beispielsweise in einer Liste R abgelegt werden. Eine der Anforderungen wird ausgewählt und aus deren Datenbiockkennung c mittels der Kennungs- decodierungseinrichtung 402 eine Liste S der Gruppen 70-73 mit Gruppenkennungen i erstellt, in deren zugehörigen Cachespeichern 60-65 der Datenblock 22 mit der Datenbiockkennung c vorgehalten wird.

Die Liste S wird der Kandidatenermittlungseinrichtung 406 übergeben. Für jeden Eintrag i' in der Liste S ermittelt die Kandidatenermittlungseinrichtung 406 eine Liste von Tupeln (ί', S'), wobei S' dadurch erhalten wird, dass die Gruppenkennung i' aus S entfernt und stattdessen die Gruppenkennung i der ausgewählten Anforderung zu S hinzugefügt wird. Mittels der Kennungscodierungseinrichtung 408 wird in jedem der so ermittelten Tupel die Liste S' durch eine von der Kennungscodierungseinrichtung 408 ermittelte Datenblockken- nung c' ersetzt, so dass eine Liste von Tupeln (ί', c') entsteht, die wiederum der Anforderungsauswahleinrichtung 410 übergeben wird.

Die Anforderungsauswahleinrichtung 410 wählt daraufhin für jedes der Tupel (ί', c') höchstens eine Anforderung aus den Anforderungen R aus, deren Gruppenkennung i=i' und deren Datenblockkennung c=c' und legt diese Anforderungen in einer Liste R' ab. Die derart ausgewählten Anforderungen R' können zur gemeinsamen Übertragung codiert werden.

Nachdem die Gruppencodierungseinrichtung 400 eine Liste gemeinsam codierbarer Datenblöcke 22 erstellt hat, werden die entsprechenden Datenblöcke 22 zusammen in einen codierten Datenblock codiert (nicht gezeigt). Zur Übertragung des gemeinsam codierten Datenblocks wird dieser beispielsweise durch Kopfdaten ergänzt, die angeben, welche Datenblöcke 22 in dem codierten Datenblock gemeinsam codiert sind. Diese Information ist notwendig, damit die Endgeräte 50-55 aus ihren Cachespeichern 60-65 die Datenblöcke 22 auswählen können, mit denen der gemeinsam codierte Datenblock decodiert und die darin enthaltenen Daten nutzbar gemacht werden können.

Zu diesem Zweck ist eine Koordinierungseinrichtung oder Kommunikationseinrichtung 500 vorgesehen. Eine einfache Kommunikationseinrichtung 500 könnte beispielsweise zu jedem gemeinsam codierten Datenblock eine Liste der Datenblockkennungen c der gemeinsam codierten Datenblöcke 22 hinzufügen. Insbesondere bei codierten Datenblöcken, in denen viele Datenblöcke 22 gemeinsam codiert sind, kann eine derartige Liste allerdings unverhältnismäßig groß werden, so dass zusätzlich zu den Nutzdaten viele Kopfdaten übertragen werden müssen.

Aufgrund der Eigenschaften der in der Cachezuordnungseinrichtung 300 verwendeten Ken- nungsdecodierungseinrichtung 302 kann eine Kommunikationseinrichtung 500, wie sie in Fig. 8 gezeigt ist, die Menge der zu übertragenden Kopfdaten reduzieren. Die Kommunikationseinrichtung 500 weist eine Kennungscodierungseinrichtung 502 auf, die wie die Kennungscodierungseinrichtung 30 aufgebaut ist.

Der Kommunikationseinrichtung 500 wird neben dem Systemparameter N eine Liste V der Gruppenkennungen i übergeben, in deren Cachespeichern die in dem gemeinsam codierten Datenblock enthaltenen Datenblöcke 22 vorgehalten werden. Darüber hinaus wird der Kommunikationseinrichtung 500 eine Liste T mit Dateikennungen f übergeben, welche die Dateien repräsentieren, deren Inhalt jeweils teilweise für die gemeinsame Codierung verwendet wurde. Die Listen V und T haben jeweils eine Länge von k+1 . Die Kennungscodie- rungseinrichtung 502 verarbeitet die Liste V sowie die Parameter N und k+1 zu einem Index L.

Der Index L wird zusammen mit der Liste T an eine Kopfdatenerzeugungseinrichtung 504 übergeben und die von dieser erzeugten Kopfdaten 506 beispielsweise zu dem gemeinsam codierten Datenblock hinzugefügt. Ein Endgerät kann durch Umkehren des Vorgangs mittels einer Kennungsdecodierungseinrichtung die Liste V zurückerhalten und dadurch die Datenblockkennungen c der Datenblöcke bestimmen, welche in den gemeinsam codierten Datenblock eingeflossen sind.

In der Liste T der Dateikennungen f können beispielsweise bestimmte Werte für die Datei- kennung f bedeuten, das von dieser Datei kein Datenblock 22 mit in den gemeinsam codierten Datenblock eingeflossen ist. Dies ist insbesondere nützlich, um zu kennzeichnen, welche Datenblöcke 22 nicht gemeinsam codierbar waren.

Der Cachespeicher 60-65 enthält Datenblöcke 22, die jeweils aufgrund der Zugehörigkeit des Endgeräts 50-55 zu einer Gruppe 70-73 mit gesamten Datenbibliothek ausgewählt sind. Um die in dem Cachespeicher 60-65 gespeicherten Datenblöcke 22 anhand der systemweit vergebenen Datenblockkennung c identifizieren zu können, könnte mit den Datenblöcken 22 zusammen jeweils die Datenblockkennung c abgespeichert werden.

Um Platz zu sparen, können die Datenblöcke 22, die beispielsweise eine feste Länge beziehungsweise Abschnittsgröße G aufweisen, in dem Cachespeicher 60-65 auch linear aufeinanderfolgend abgespeichert werden. Der Speicherort kann in einem linearen Speichermedium beispielsweise aus der Datenblockkennung c mittels der Formel G ^* c ermittelt werden. Da jedoch lediglich ein Teil der Datenblöcke 22 in dem Cachespeicher 60-65 abgelegt wird, ergeben sich aus einer derartigen Zuordnung große ungenutzte Speicherbereiche innerhalb des Cachespeichers 60-65.

Daher kann es bevorzugt sein, den systemweiten Datenblockkennungen c lokale Datenblockkennungen d zuzuweisen, die eine kompakte Anordnung oder Speicherung der Datenblöcke 22 in dem Cachespeicher 60-65 erlauben. Zu diesem Zweck kann beispielsweise ein Endgerät 50-55 eine Datenblockkennungszuordnungseinrichtung 600 aufweisen, die als Eingabeparameter die Systemparameter N und k, sowie die Gruppenkennung i erhält. Die Datenblockkennungszuordnungseinrichtung 600 weist eine Kennungsdecodierungsein- richtung 602, eine Abbiidungseinrichtung 604 und eine Kennungscodierungseinrichtung 606 auf.

Die Kennungsdecodierungseinrichtung 602 wendet das Verfahren 200-220 zur Zuweisung einer Eiementiiste zu einer Kennung an, um aus den Parametern N, k und c eine Liste der Gruppenkennungen i zu erzeugen, in denen die Datenblöcke 22 mit der Datenblockken- nung c vorgehalten werden.

In einer ersten Ausführungsform übernimmt die Abbiidungseinrichtung 604 diese Liste und führt die folgenden Schritte aus: Entfernen der eigenen Gruppenkennung i aus der Liste; Verringern aller Gruppenkennungen um 1 , soweit sie dem Betrag nach größer sind als die eigene Gruppenkennung i. Die daraus entstandene Liste weist ein Element weniger auf als die von der Kennungscodierungseinrichtung 602 erzeugte Liste.

Die von der Abbiidungseinrichtung 604 erzeugte Liste wird der Kennungscodierungseinrichtung 606 übergeben, die unter Einbeziehung der Systemparameter N-1 und k-1 die lokale Datenblockkennung d erzeugt.

In einer zweiten Ausführungsform übernimmt die Abbiidungseinrichtung 604 die Liste und führt die folgenden Schritte aus: Prüfen, ob die Gruppenkennung 0 in der Liste enthalten ist: prüfen, ob die eigene Gruppenkennung i in der Liste enthalten ist; wenn die Gruppenkennung 0 in der Liste enthalten war, Entfernen der Gruppenkennung 0 und Hinzufügen der eigenen Gruppenkennung i; wenn die eigene Gruppenkennung i enthalten war, Entfernen der Gruppenkennung i und Hinzufügen der Gruppenkennung 0; wenn sowohl die Gruppenkennung 0 als auch die Gruppenkennung i enthalten waren, oder weder die Gruppenkennung 0 noch die Gruppenkennung i enthalten waren, keine Änderung.

Die derart erhaltene Liste wird der Kennungscodierungseinrichtung 606 übergeben, die unter Einbeziehung der Systemparameter N und k die lokale Datenblockkennung d erzeugt, beispielsweise durch Anwendung der Verfahrensschritte 100-122.

Die zweite Ausführungsform der Datenblockkennungszuordnungseinrichtung 600 erlaubt es, auch Datenblöcken 22 eine lokale Datenblockkennung d zuzuordnen, die nicht der Gruppenkennung i zugeordnet sind. Die lokalen Datenblockkennungen d der Datenblöcke 22, die der Gruppenkennung i zugeordnet sind, sind durch dieses Verfahren immer niedriger als die lokalen Datenblockkennungen d der Datenblöcke 22, die der Gruppenkennung i nicht zugeordnet sind. Somit ist es möglich, nicht der Gruppenkennung i zugehörige Datenblöcke 22 zu speichern, die der Gruppenkennung i zugehörigen Datenblöcke 22 werden aber weiterhin kompakt am Anfang des Cachespeichers 60-65 abgelegt.

In einer dritten Ausführungsform der Datenblockkennungszuordnungseinrichtung 600 übernimmt die Abbildungseinrichtung 604 die Liste und führt die folgenden Schritte aus: Prüfen, ob die eigene Gruppenkennung i in der Liste enthalten ist; wenn die eigene Gruppenkennung i nicht enthalten war, Erhöhen aller in der Liste enthaltenen Gruppenkennungen um 1 , soweit sie dem Betrag nach kleiner sind als die eigene Gruppenkennung i; wenn die eigene Gruppenkennung i enthalten war, Entfernen der Gruppenkennung i, Erhöhen aller in der Liste enthaltenen Gruppenkennungen um 1 , soweit sie dem Betrag nach kleiner sind als die eigene Gruppenkennung i und Hinzufügen der Gruppenkennung 0.

Die derart erhaltene Liste wird der Kennungscodierungseinrichtung 606 übergeben, die unter Einbeziehung der Systemparameter N und k die lokale Datenblockkennung d erzeugt, beispielsweise durch Anwendung der Verfahrensschritte 100-122.

Die dritte Ausführungsform der Datenblockkennungszuordnungseinrichtung 600 bewirkt wie die zweite Ausführungsform, dass die Datenblöcke 22, die der Gruppenkennung i zugeordnet sind, kompakt am Anfang des Cachespeichers 60-65 abgelegt werden. Die darauffolgenden Datenblöcke 22 werden darüber hinaus in der Reihenfolge ihrer Datenblockkennun- gen c abgelegt. Somit wird die Lokalität bei Zugriffen auf nicht der Gruppenkennung i zugehörige Datenblöcke 22, die trotzdem vorgehalten werden, verbessert.

Jedes Endgerät 16a-16f, 50-55 kann mittels empfangener Codesymbole (gemeinsam codierte Datenblöcke) und den in dem Cachespeicher 20a-20f, 60-65 vorgehaltenen Datenblöcken 22 die der Gruppe i zugewiesenen Dateien decodieren. Die in dem Cachespeicher 20a-20f, 60-65 vorgehaltenen Datenblöcke 22 entsprechen dabei einer Untermenge der existierenden Codesymbole. Lese- und Schreibzugriffe werden mittels einer Dateisystemeinrichtung 600 durchgeführt.

Um aus einer lokalen Datenblockkennung d die zugehörige systemweite Datenblockkennung c zu erhalten, kann eine weitere Datenblockkennungszuordnungseinrichtung 700 vorgesehen sein, wie sie in Fig. 10 gezeigt ist. Die Datenblockkennungszuordnungseinrichtung 700 weist eine Kennungsdecodierungseinrichtung 702, eine Abbildungseinrichtung 704 und eine Kennungscodierungseinrichtung 706 auf. Im Wesentlichen entspricht dieser Aufbau dem der Datenblockkennungszuordnungseinrichtung 600. Lediglich die Abbildungseinrich- tung 704 wandelt die Listen mit gegenüber der Abbildungseinrichtung 604 umgekehrten Operationen um.

Die hierin beschriebenen Verfahren 100-122, 200-218 sowie die hierin beschriebenen Netzwerke 10 stellen eine effiziente Umsetzung der Indexkodierung dar, die weder besonders Rechen intensiv noch besonders speicherintensiv ist. Dadurch sind die Verfahren 100-122, 200-218 sowie die Netzwerke 10 besonders gut zur Umsetzung in Verbindung mit Mobilfunknetzen geeignet.

Bezugszeichenliste

10 Mobilfunknetzwerk

12 Basisstation

14 Medium

16a-16f Endgerät

18 Datenbereitstellungseinrichtung

20a-20f Speichereinrichtung / Cachespeicher

22 Datenelement / Element/ Datenblock

30 Kennungscodierungseinrichtung

40 Kennungsdecodierungseinrichtung

50-55 Endgerät

60-65 Speichereinrichtung / Cachespeicher

70-73 Gruppe

100-122 Verfahrensschritte

200-220 Verfahrensschritte

300 Cachezuordnungseinrichtung (Cache Placement Module)

302 Kennungsdecodierungseinrichtung

304 Entscheidungseinrichtung

400 Gruppencodierungseinrichtung (Group Coder Module)

402 Kennungscodierungseinrichtung

406 Kandidatenermittlungseinrichtung

408 Kennungsdecodierungseinrichtung

410 Anforderungsauswahleinrichtung

500 Koordinierungseinrichtung (Coordination Module)

502 Kennungsdecodierungseinrichtung

504 Kopfdatenerzeugungseinrichtung

506 Kopfdaten

600, 700 Datenblockkennungszuweisungseinrichtung / Dateisystemeinrichtung

(File System Module)

602, 702 Kennungsdecodierungseinrichtung

604, 704 Abbildungseinrichtung

606,706 Kennungscodierungseinrichtung

b Begrenzungszähler

c Datenblockkennung (systemweit), Zwischenspeicher der Kennungscodierungs- einrichtung und der Kennungsdecodierungseinrichtung

d Datenblockkennung (lokal) f Dateikennung

G Systemparameter / Länge eines Datenblocks

i Nutzerkennung, Gruppenkennung (user id)

N System parameter/ Anzahl der Gruppen oder Gruppenkennungen k System parameter/ Kardinalität

L Index

R Liste wartender Anforderungen

R' Liste ausgewählter Anforderungen

S Kennungsliste / Elementliste

z Zwischenspeicher