Beschreibung

Titel

Speichersystem mit statischer Zuordnung von Speichermedien sowie Verfahren zur Einrichtung des Speichersystems

Stand der Technik

Die Erfindung betrifft ein Speichersystem mit einer Anzahl von M

Speichermedien, mit einer Anzahl von N Datenproduzenten, die jeweils einen

Datenstrom bereitstellen und jeweils eine oder mehrere Datenmitglieder aufweisen, und mit einer Speichermanagementeinrichtung zur Verteilung der Datenströme der N Datenproduzenten an die M Speichermedien. Die Erfindung betrifft auch ein Verfahren zur Einrichtung des Speichersystems.

Speichersystem üblicher Architektur können eine Mehrzahl von

datenproduzierenden Einrichtungen sowie eine Mehrzahl von Speichermedien aufweisen, welche in einem Netzwerk angeordnet sind und die Daten der datenproduzierenden Einheiten speichern. Die Verteilung der Speichermedien auf die speicherproduzierenden Einheiten erfolgt über einen Speichermanager, der auch für das sogenannte Load Balancing verantwortlich ist, das

gewährleisten soll, dass die Speichermedien optimal genutzt werden und im Falle des Ausfalls einzelner Speichermedien die Aufzeichnung auf andere Speichermedien fortgesetzt werden kann. Hierbei kann der Speichermanager prinzipiell auf alle Speichermedien in einem Netzwerk frei zugreifen.

Besonders im Bereich der Überwachungssysteme mit Überwachungskameras ist die Organisation der Speicherung der entstehenden Daten eine

Herausforderung, da zum einen durch die Überwachungskameras große

Datenmengen erzeugt werden und zum anderen es für den Anwender besonders wünschenswert ist, dass diese Daten lückenlos und insbesondere ohne Ausfall gespeichert werden.

In diesem Zusammenhang offenbart die Druckschrift DE10301455A1 , die wohl den nächstkommenden Stand der Technik bildet, ein Verfahren zur Aufzeichnung von Video-/Audiodaten. Bei dem Verfahren wird vorgeschlagen, dass ein lokaler Datenspeicher über eine datentechnische Kopplung mit mindestens einer Aufzeichnungsvorrichtung verbunden ist, die eine größere Speicherkapazität aufweist als der lokale Datenspeicher, so dass ein virtueller Datenspeicher für die Aufnahmevorrichtung gebildet wird. Die Aufzeichnungsvorrichtung kann über eine Vielzahl von Speichermedien verfügen. Das Verfahren wird grundsätzlich auch als NVR-Prinzip (NVR-Network Video Recording) bezeichnet.

Offenbarung der Erfindung

Im Rahmen der Erfindung wird ein Speichersystem mit den Merkmalen des Anspruchs 1 sowie ein Verfahren mit den Merkmalen des Anspruchs 9 vorgeschlagen. Bevorzugte oder vorteilhafte Ausführungsformen der Erfindung ergeben sich aus den Unteransprüchen, der nachfolgenden Beschreibung sowie den beigefügten Figuren.

Das erfindungsgemäße Speichersystem ist zur Speicherung von digitalen Daten geeignet und/oder ausgebildet. Es umfasst eine Anzahl von M Speichermedien, welche prinzipiell durch flüchtige und/oder nicht-flüchtige Speicher gebildet sein können. Um jedoch einen Datenverlust bei einem Stromausfall zu vermeiden, ist es bevorzugt, dass mindestens der Großteil, vorzugsweise alle M

Speichermedien als nicht-flüchtige Speicher ausgebildet sind. Insbesondere sind die Speichermedien als physikalische Speichermedien, z.B. als Festplatten ausgebildet.

Das Speichersystem umfasst ferner eine Anzahl von N Datenproduzenten, die jeweils einen Datenstrom mit einer Übertragungsrate bereitstellen. Ein

Datenstrom ist eine zeitliche Abfolge von Daten, beispielsweise von Bilddaten bei einem Bilddatenstrom. Der Datenstrom weist insbesondere digitale Daten auf. Jeder der N Datenproduzenten kann eine oder mehrere Datenmitglieder aufweisen. Bei einem Datenproduzenten kann es sich somit um ein einziges Datenmitglied oder um eine Gruppe Datenmitglieder handeln, die zu einem Datenproduzenten zusammengefasst sind. Die Datenmitglieder erzeugen den Datenstrom eines Datenproduzenten.

Das Speichersystem umfasst eine Speichermanagementeinrichtung, welche zur Verteilung der Datenströme der N Datenproduzenten an die M Speichermedien ausgebildet ist. Dies wird insbesondere realisiert, indem die

Speichermanagementeinrichtung die N Datenproduzenten den M

Speichermedien zuordnet, so dass die Datenströme der Datenproduzenten an die ihnen zugeordneten Speichermedien geleitet werden.

Im Rahmen der Erfindung wird vorgeschlagen, dass jedem der N

Datenproduzenten eine Gruppe von (A+1) der M Speichermedien statisch zugeordnet ist, wobei die Ungleichung 1 < A < M gilt. Besonders bevorzugt gilt für jeden der N Datenproduzenten der gleiche Wert für A, so dass jedem der N Datenproduzenten die gleiche Anzahl der M Speichermedien statisch zugeordnet ist.

Der Erfindung liegt die Überlegung zugrunde, dass die existierenden

Speichersysteme, welche bei der Speichervergabe auf alle Speichermedien frei zugreifen können, solange ausgezeichnet funktionieren, solange alle

Speichermedien verfügbar sind und es keine Bandbreiten- bzw. Session- Limitierungen gibt. Soweit derartige Limitierungen vorliegen, sind solche

Verteilungsstrategien nicht mehr optimal.

Demgegenüber schlägt die Erfindung vor, ein statisches und damit einfach zu kontrollierendes Speichersystem zu verwenden. Statisch bedeutet insbesondere, dass nicht jeder Datenproduzent auf jedes Speichermedium aufzeichnen darf, sondern, dass der Datenproduzent je nach geforderter Ausfallsicherheit des Speichersystems auf eine beschränkte Anzahl von Speichermedien,

beispielsweise auf zwei Speichermedien, begrenzt, insbesondere ausschließlich, zugreifen darf. Durch die statische Zuweisung können systembedingte

Limitierungen für einen Worst-Case-Fall überprüft werden und somit für die Laufzeit des Systems garantiert werden. Insbesondere erhöht sich die

Vorhersehbarkeit des Speichersystems bei Worst-Case-Szenarien. Bei einer besonders bevorzugten Ausführungsform der Erfindung ist das

Speichersystem als ein Überwachungssystem und/oder mindestens ein

Datenmitglied oder ein Datenproduzent als eine Überwachungskamera ausgebildet. Insbesondere sind das oder die Datenmitglieder mit den

Speichermedien über ein Netzwerk verbunden. Wie bereits eingangs erläutert, ist gerade bei Überwachungssystemen, wie sie zum Beispiel zur Überwachung von öffentlichen Gebäuden, Plätzen, Unternehmen oder Fertigungsstandorten etc. eingesetzt werden, entscheidend, dass zum einen Datenströme mit inhaltlich zusammenhängenden Daten generiert werden und zum zweiten, dass es notwendig ist, diese Daten verlustfrei zu speichern. Insbesondere soll sichergestellt werden, dass die Daten zu einem späteren Zeitpunkt wieder zu einer Videoszene zusammengesetzt werden können. Bei klassischen Systemen, die das Speichermedium frei wählen können, ist stets zu befürchten, dass die Vergabestrategie zu vollständig zerstückelten Aufzeichnungen führt. Besonders gefährdet ist diese Vergabestrategie nach Hinzufügen oder Wegnehmen von Speichermedien.

Durch die statische Zuweisung ist dagegen sichergestellt, dass

zusammengehörige Daten eines Datenmitglieds oder Datenproduzenten, insbesondere einer Überwachungskamera, auf einer genau definierten, nämlich statisch festgelegten Anzahl von Speichermedien nachvollziehbar abgelegt wird.

Besonders stark treten die Vorteile der Erfindung hervor, wenn die Anzahl N der Datenproduzenten größer als 6, vorzugsweise größer als 10 und insbesondere größer als 32 gewählt ist. Zugleich sollte der Wert A < 6, vorzugsweise < 4 und insbesondere < oder < 2 gewählt sein. Bei einer freien Verteilung der

Datenströme der Datenproduzenten auf alle verfügbaren Speichermedien werden die Datenströme stark defragmentiert. Dagegen ist durch das

erfindungsgemäße Speichersystem sichergestellt, dass jeder Datenproduzent auf eine sehr überschaubare und/oder bekannte Menge von Datenmedien schreibt.

Eine Überlegung der Erfindung, um das Speichersystem sicher gegenüber Ausfällen von einer Anzahl von A Speichermedien zu gestalten, ist es jedem Datenproduzenten mindestens A+1 Speichermedien zum Aufzeichnen zur Verfügung zu stellen, also zuzuordnen. Aus Kostengründen ist es bevorzugt, A klein, insbesondere so klein wie möglich zu wählen. Eine mögliche Konstellation der Erfindung sieht daher vor, dass N Datenproduzenten auf M Speichermedien verteilt werden, wobei jeder Datenproduzent zwei Speichermedien bekommt, so dass A = 1 gewählt ist. Damit kann es maximal 2 aus M,

(Μλ

also

2 , viele unterschiedliche Gruppen von Speichermedien geben. Bei einer bevorzugten Verteilung gibt es genau einen Datenproduzenten pro Gruppe.

Bei einer bevorzugten Weiterbildung der Erfindung ist vorgesehen, dass jeder der N Datenproduzenten einen Datenstrom mit einer Datenübertragungsrate aufweist, wobei die Datenmitglieder der Datenproduzenten so gewählt sind, dass die Datenübertragungsrate der Datenströme der N Datenproduzenten aneinander oder an eine gemeinsame Systemübertragungsrate angenähert oder gleich sind. Die Auswahl der Datenmitglieder und Einordnung in die

Datenproduzenten wird von der Speichermanagementeinrichtung übernommen. Diese sortiert die Datenmitglieder so in Gruppen, dass die Gruppen in der Datenübertragungsrate ähnlich sind.

Es ist auch möglich, eine gemeinsame Systemübertragungsrate zu definieren und die Datenmitglieder so in die Datenproduzenten zu sortieren, dass die Datenübertragungsraten der Datenströme der Datenproduzenten gleich oder zumindest ähnlich zu der Systemübertragungsrate sind. Die gemeinsame Systemübertragungsrate kann wahlweise vom Benutzer vorgegeben werden oder abgeschätzt werden.

In einer konkretisierten Ausführungsform der Erfindung wird die gemeinsame Systemübertragungsrate festgelegt, wobei durch die

Speichermanagementeinrichtung sichergestellt ist, dass die Datenmitglieder so sortiert sind, dass die Datenübertragungsraten der Datenströme der

Datenproduzenten kleiner als das 2-fache, vorzugsweise kleiner als das 1 ,5- fache und insbesondere kleiner als das 1 ,3-fache und zugleich größer als das 0,5-fache, vorzugsweise größer als das 0,7-fache und insbesondere größer als das 0,8-fache der gemeinsamen Systemübertragungsrate ist. Betrachtet man die bevorzugte Ausführungsform, bei der A=1 gewählt ist, so kann das Speichersystem ohne Umkonfiguration die zuvor genannten

Abweichungen von der Systemübertragungsrate automatisch kompensieren, so dass die durchschnittliche Last auf alle Speichermedien konstant bleibt und damit die Lebensdauer der Daten für alle Datenproduzenten denselben Wert anstreben.

Bei einer bevorzugten Weiterbildung der Erfindung weist jedes der M

Speichermedien einen Zähler auf, welcher einen Zählerstand bereitstellt. Der Zählerstand wird in Abhängigkeit eines Quotienten zwischen vergebenem

Speicher und verfügbarer Speicherkapazität des Speichermediums erhöht. Weist das Speichermedium beispielsweise 100 Einheiten als Speicherkapazität auf und werden 10 Einheiten als Speicher vergeben, so wird der Zähler um 10/100, also um 0, 1 erhöht.

Die Speichermanagementeinrichtung ist ausgebildet, einen Datenstrom von einem Datenproduzenten auf das Speichermedium der Gruppe von

zugeordneten Speichermedien zu leiten, welches den niedrigsten Zählerstand aufweist. Die Speichermedien arbeiten nach einem FIFO-Prinzip, wobei - sobald das Speichermedium voll ist - der Speicher mit den ältesten Einträgen

überschrieben wird. Diese Verteilungssystematik hat den Vorteil, dass Daten von einem

Datenproduzenten gleichmäßig auf die dem Datenproduzenten zugeordneten Speichermedien verteilt werden und insbesondere, dass keine Clusterbildung in den Speichermedien entsteht. Für den Fall, dass die Zählerstände einer Gruppe von A+1 Speichermedien, die einem gemeinsamen Datenproduzenten zugeordnet sind, sich zu stark unterscheiden, wird als mögliche Gegenmaßnahme vorgeschlagen, alle

Zählerstände auf 0 zu setzen oder auf einen gemeinsamen Zählerstand anzugleichen. Auch dieser Ausgestaltung liegt die Überlegung zugrunde, die Clusterbildung bei der Ablage der Daten eines Datenproduzenten weitgehend zu vermeiden. Ist in einer Gruppe von A+1 Speichermedien, die einem einzigen Datenproduzenten zugeordnet ist, ein Speichermedium mit einem im Vergleich zu den anderen Speichermedien sehr kleinen Zählerstand vorhanden, so wird die Speichermanagementeinrichtung den Datenstrom auf das Speichermedium lenken, das diesen geringen Zählerstand aufweist. Dies führt jedoch wieder zu einer Clusterbildung auf diesem Speichermedium. Aus diesem Grund wird vorgeschlagen, zum Beispiel bei Einsetzen eines neuen Speichermediums in das Speichersystem (welches damit einen Zählerstand von 0 aufweist) oder bei einem Auseinanderdriften der Zählerstände, diese wieder aneinander anzugleichen.

Ein weiterer Gegenstand der Erfindung betrifft ein Verfahren zum Betreiben des Speichersystems, wie es zuvor beschrieben wurde, bzw. nach einem der vorhergehenden Ansprüche. Bei dem Verfahren werden zunächst die

Datenmitglieder auf die Datenproduzenten so verteilt, so dass jeder

Datenproduzent eine ähnliche Datenübertragungsrate oder eine

Systemübertragungsdatenrate aufweist. Nachfolgend werden den N

Datenproduzenten eine Gruppe von (A+1 ) der M Speichermedien statisch zugeteilt.

Ein weiterer Gegenstand betrifft ein Computerprogramm mit den Merkmalen des Anspruchs 12.

Weitere Merkmale der Erfindung ergeben sich den nachfolgenden

Beschreibungen bevorzugter Ausführungsbeispiele der Erfindung sowie der beigefügten Figuren. Dabei zeigen:

Figuren 1 bis 6 das Speichersystem in einer schematischen

Blockdarstellung;

Figur 7 eine Schematisierung der Speicherverteilung.

Die Figur 1 zeigt ein Speichersystem 1 mit einer Mehrzahl von N

Datenproduzenten 2 sowie eine Mehrzahl M von Speichermedien 3. Die

Datenproduzenten 2 sind mit den Speichermedien 3 datentechnisch, zum Beispiel über ein Netzwerk 4 verbunden. Bei dem Speichersystem 1 handelt es sich um ein Speichersystem 1 für ein Überwachungssystem mit einer Mehrzahl von Datenmitgliedern, wie z.B. Überwachungskameras 5. Die Überwachungskameras 5 sind bei beispielhaften Anwendungen auf Straßen, öffentliche Plätze, Firmengebäude etc. gerichtet und erzeugen Bilddatenströme, wobei die Bilddatenströme in den Speichermedien 3 abgelegt werden. Die Verteilung der Datenströme auf die verschiedenen Speichermedien 3 wird von einer Speichermanagementeinrichtung 6 organisiert. Jedem der

Datenproduzenten 2 kann genau ein Datenmitglied, z.B. eine

Überwachungskamera 5 oder - wie beispielhaft in der Figur 1 unten rechts gezeigt - eine Mehrzahl von Datenmitgliedern, z.B. mehrere

Überwachungskameras 5 umfassen.

Bei dem Speichersystem 1 wird ein statisches und damit einfach zu

kontrollierendes System umgesetzt. Statisch bedeutet dabei, dass nicht jeder Datenproduzent 2 bzw. jede Überwachungskamera 5 auf jedes Speichermedium 3 aufzeichnen darf, sondern die Auswahl - je nach geforderter Ausfallsicherheit des Speichersystems 1 - auf beispielsweise zwei Speichermedien 3 pro

Datenproduzent 2 begrenzt ist. Durch die statische Zuweisung können systembedingte Limitierungen für den Worst-Case-Fall überprüft werden und somit für die Laufzeit des Speichersystems 1 garantiert werden.

Um das Speichersystem 1 sicher gegenüber Ausfällen von A Speichermedien 3 zu gestalten, müssen jedem Datenproduzenten 2 mindestens A+1

Speichermedien 3 zum Aufzeichnen zur Verfügung stehen. Der Worst-Case ergibt sich nun, wenn alle Datenproduzenten (N an der Zahl), die einem gemeinsamen Speichermedium X zugeordnet sind, gleichzeitig auf dieses aufzeichnen. Anders herum ausgedrückt, kann jeder Datenproduzent 2, insbesondere jede Überwachungskamera 5 auf ein beliebiges seiner (A+1) Speichermedien 3 aufzeichnen und muss somit bei jedem dieser

Speichermedien 3 eine Session und entsprechende Bandbreite reservieren. Damit ergibt es sich, dass das Speichersystem 1 in Summe mindestens (A+1) x N viele Sessions und das (A+1)-fache an Gesamt-Streaming-Bandbreite zur Verfügung stellen muss. Daher ist es aus Kostengründen empfehlenswert, A so klein wie möglich zu wählen.

Im Folgenden wird daher der Fall betrachtet, dass A = 1 gewählt ist. Alle Überlegungen lassen sich aber auf den Fall A > 1 verallgemeinern. Sollen N Datenproduzenten auf M Speichermedien verteilt werden, so dass jeder Datenproduzent 2 zwei Speichermedien 3 bekommt, dann gibt es maximal zwei aus M unterschiedliche Gruppen von Speichermedien 3, wobei in einer besonders geschickten Auslegung jeder Datenproduzent 2 die Speichermedien 3 von genau einer dieser Gruppen benutzt. Im einfachsten Fall gibt es genau einen

Datenproduzenten 2 pro Gruppe, alle Datenproduzenten 2 schreiben mit derselben Bandbreite und alle Speichermedien 3 haben dieselben

Eigenschaften. Selbst unter diesen idealisierten Bedingungen wird die produzierte Bandbreite der Datenproduzenten 2 schwanken und nicht exakt vorhersehbar sein. Im Folgenden wird eine maximale Abweichung von der idealen Bandbreite hergeleitet, die das System ohne Umkonfiguration automatisch kompensieren kann, so dass die durchschnittliche Last auf alle Speichermedien konstant bleibt und damit die Lebensdauer der Daten für alle Datenproduzenten 2 oder

Datenmitglieder, insbesondere Überwachungskameras 5 denselben Wert anstreben.

Im worst-case gibt es eine Menge von Datenproduzenten 2 mit schwarzen Überwachungskameras 5 in Figur 2, die um einen Faktor x mehr Datenrate produzieren als die anderen Kameras (oder äquivalent die Komplement-Menge produziert um einen Faktor x weniger Datenrate). Im worst-case muss diese Menge alle Datenproduzenten 2 umfassen, die genau ein Speichermedium Y nicht benutzen. Dann sind die anderen Datenproduzenten 2 gezwungen die Überlast auszugleichen, indem sie ihre kompletten Daten auf Speichermedium Y wegschreiben (d.h. die gestrichelten Pfeile in Figur 2 werden in dieser Situation nicht benutzt). In dem betrachteten Szenario schreiben also (M-1)

Datenproduzenten 2 auf Speichermedium Y mit einer Rate R, während auf jedes andere Speichermedium M-2 Datenproduzenten 2 mit einer Rate von x * R / 2 schreiben (jeder Datenproduzent 2 verteilt im Prinzip seine Last gleichmäßig auf beide Speichermedien 3).

Damit erreicht das Speichersystem 1 eine Sättigung, wenn (M-1) * R = (M-2) * x * R / 2 gilt oder vereinfacht x = 2 * (M-1)/(M-2). D.h. für das skizzierte Beispiel erhält man eine mögliche Abweichung von x = 2 * 3 / 2 = 3. Eine größere

Abweichung würde dazu führen, dass die Schreib-Last nicht mehr gleichmäßig auf die Speichermedien 3 verteilt werden kann und somit das Speichersystem 1 den Gesamtspeicher aller Speichermedien 3 nicht mehr vollständig nutzen kann, d.h. die Lebensdauer der Daten muss bei der Nutzung des Gesamtspeichers zwangsläufig für verschiedene Datenproduzenten 2 divergieren.

Für größere Speichersysteme 1 mit mehr Speichermedien 3 sinkt zwar dieser worst-case Wert im Grenzfall auf 2, allerdings wird dessen Eintreten auch gleichzeitig immer unwahrscheinlicher. Diese einfache und statische Zuteilung von Datenproduzenten 2 auf Speichermedien 3 bleibt somit garantiert stabil, solange keine zwei Datenproduzenten 2 eine Bandbreitenabweichung oder

Abweichung der Übertragungsrate von mehr als Faktor 2 aufweisen. Diese Aussage lässt sich verallgemeinern, dass zwei Datenproduzenten 2 von

Überwachungskameras 5 (zwei Überwachungskameras 5 gehören zum selben Datenproduzenten 2, wenn sie denselben Speichermedien 3 zugeteilt sind) in Summe eine maximale Bandbreitenabweichung von 2 aufweisen dürfen.

Eine Anforderung an das Speichersystem 1 ist Ausfallsicherheit gegenüber Speichermedien 3, wie nachfolgend mit Bezug auf die Figur 3 diskutiert wird. Dies ist ein Grund, weshalb jedem Datenproduzenten 2 mehrere Speichermedien 3 zugewiesen werden. Fällt nun ein Speichermedium 3 (durchgestrichen) aus, ändert sich auch die maximal erlaubte Bandbreiteschwankung, bei der das Speichersystem 1 im worst-case immer noch stabil läuft. Die Berechnung erfolgt analog zu Figur 2. Auf Speichermedium Y zeichnen nach wie vor M-1 Datenproduzenten 2 auf, um die Überlast auf den anderen Speichermedien 3 zu kompensieren. Für die restlichen Datenproduzenten 2 steht nun ein Speichermedium 3 weniger zur Verfügung, so dass die Last auf die Verbleibenden entsprechend ansteigt. Eine Sättigung ergibt sich demnach, wenn (M-1)*R = (1 + (M-3)/2)*R*x bzw. nach Vereinfachung x = 2 gilt. D.h. ein Speichersystem 1 mit einfacher

Ausfallsicherheit (A=1) sollte so aufgesetzt werden, dass kein Datenproduzent 2 über einen größeren Zeitraum gemittelt (groß bedeutet kleiner als beispielsweise 10% der möglichen maximalen Aufzeichnungsdauer) um mehr als die doppelte Bandbreite irgendeines anderen Datenproduzenten produziert. Damit ist garantiert, dass selbst beim Ausfall eines Speichermediums 3, das

Speichersystem 1 stabil weiter arbeiten kann und die verbleibende Speicherkapazität optimal zwischen den Datenproduzenten 2 aufteilt. (Aufgrund des Ausfalls ist die Gesamtspeicherkapazität gesunken und somit die maximale Aufzeichnungsdauer.)

Soweit wurden gleichartige Speichermedien 3 betrachtet, d.h. insbesondere Speichermedien, die denselben Speicherplatz bzw. Speicherkapazität zur Verfügung stellen. Daraus ergibt sich, dass das Speichersystem 1

Bandbreitenschwankungen bis Faktor 2 selbst bei Ausfall eines

Speichermediums 3 kompensieren kann.

Dieses Ergebnis lässt sich nur bedingt auf inhomogene Speichersysteme 1 übertragen, bei denen die Speichermedien 3 unterschiedlich groß sind, wie anhand der Figur 4 dargelegt wird. Dazu wird der folgende Extremfall betrachtet, in dem ein Speichermedium 3 sehr viel größer ist als alle anderen, z.B. um den Faktor 300. Dieses Speichermedium 3 fällt nun aus und eines der verbleibenden muss darüber hinaus die Überlast auf die anderen Speichermedien 3

kompensieren. Aus Symmetriegründen müssen die 300 Speichereinheiten des ausgefallenen Speichermediums 3 gleichmäßig auf die anderen Speichermedien 3 verteilt werden. Damit ist aber die Hauptlast den verbleibenden drei

Speichermedien 3 bereits fix zugeteilt (jedes Speichermedium 3 hat im Beispiel dann eine Fixlast von 100) und die verbleibenden kleinen Gruppen können eventuelle Schwankungen von unter 5% ausgleichen. Diese Überlegung zeigt, dass in inhomogenen Systemen im Extremfall kein Bandbreitenausgleich möglich ist. Aus dieser Überlegung heraus wird das Speichersystem 1 mit homogenen Speichermedien 3, also in etwa gleich großen Speichermedien 3 ausgestattet.

Mit Bezug auf die Figur 5 wird sich darauf konzentriert, dass die kompensierbare Bandbreitenschwankung für den Fall maximiert wird, dass kein Speichermedium 3 ausfällt. Zunächst werden wie in Figur 5 gezeigt die Speicherkapazitäten der Speichermedien 3 mit C_i bezeichnet. Die Bandbreite eines Datenproduzenten, die auf Speichermedium i und j aufzeichnen, werden mit r ij und rji bezeichnet.

Dabei entspricht r ij der Bandbreite, die auf Speichermedium i geht, und rji entsprechend der Bandbreite, die auf Speichermedium j geht. Die

Gesamtbandbreite aller Datenproduzenten 2 zusammen sei R, die

Gesamtspeicherkapazität C und die Aufzeichnungsdauer T. Daraus ergeben sich sofort folgende Bedingungen: Die Aufzeichnungsdauer T entspricht dem Verhältnis aus

Gesamtspeicherkapazität und Gesamtbandbreite:

[0] T = C / R

Die Summe aller eingehenden Kanten eines Speichermediums 3 müssen das Speichermedium 3 innerhalb einer Zeitdauer T vollständig beschreiben

(vorausgesetzt das Speichersystem 1 befindet sich im Normalzustand), d.h.

[1] C_i = T * sum_{j!=i} r_ij.

Für die Gesamtspeicherkapazität C gilt:

[2] C = sum_i C_i.

Wählt man die Bandbreiten r ij = R * C_i * CJ / ((C - C_i) * C), so erhält man eine garantierte Bandbreitenkompensation von Faktor 2.

Diese Verteilung erfüllt Bedingung [1]:

[V] T * sum_{j!=i} r_ij

= T * R * C_i / ((C - C_i)*C) * sum{j!=i} CJ

= (C/R) * R * C_i / ((C - C_i)*C) * (C - C_i)

C_i

Um den Faktor 2 zu verifizieren werden wie im homogenen Fall die Bandbreiten aller Datenproduzenten 2, die nicht auf C_1 aufzeichnen können, um einen Faktor 2 erhöht, während die anderen Datenproduzenten 2 zum Ausgleich ihre volle Last auf C_1 geben. Dabei müssen die Lastverhältnisse auf die einzelnen Speichermedien 3 unverändert bleiben. In Formeln geschrieben erhält man für das Verhältnis von Speichermedium C_1 zu Speichermedium C_2 folgende Ungleichung:

[3] T*(sum_{i!=1} r_1 i + r_i1)/C_1 >= x*T*(-r_21 + sum_{i!=2}r_2i)/C_2 Unter Benutzung von [0], [1] und [2] erhält man: [4] 1 + (sum_{i!=1} C_i / (C - C_i)) >= x * (1 - C_1 / (C-C_2)) Es gilt nun folgende Ungleichheitskette:

[5] 1 + (sum_{i != 1 } C_i / (C - C_i)) >=

1 + (sum_{i!=1} C_i / C) >=

2 - C_1/C >=

2 * (1 - C_1 / (C-C_2))

D.h. die vorgeschlagene Verteilung verkraftet im inhomogenen Fall

Bandbreitenschwankungen von mindestens Faktor 2, wenn kein

Speichermedium 3 ausgefallen ist, und ist somit asymptotisch optimal.

Im vorherigen Abschnitt wurde für jeden Datenproduzenten G_ij eine asymptotisch optimale Gesamtbandbreite pro Datenproduzent hergeleitet. Diese beträgt r ij + rji = C_i * CJ * (1/(C-C_i) + 1/(C-CJ)) / T. Diese Bandbreite kann auch Systemübertragungsrate genannt werden.

Aufgabe der Speichermanagementeinrichtung ist es, die Datenmitglieder, insbesondere die Überwachungskameras 5 so auf die Datenproduzenten 2 zu verteilen, dass diese idealen Gesamtbandbreiten pro Datenproduzent 2 erreicht werden.

Die Verteilung kann beispielsweise durch den folgenden Algorithmus erreicht werden: const int N = // Anzahl der Speichermedien (3)

const int M = // Anzahl der Kameras (Datenmitglieder) const int G = N * (N-1)/2; // Anzahl der Gruppen/Datenproduzenten (2)

// Liste mit den Groessen der Speichermedien

vector< float > SpeicherGroessen(N, 0);

// Liste mit den Bandbreitenwerten der Kameras

vector< float > KameraBandbreiten(M);

// Liste mit den verbleibenden Bandbreitenkontingenten jeder Gruppe vector< float > GruppenRestGroessen(G,0); // Gruppen sortiert nach Groesse

set< pair< float, int > > SortierteRestGroessen;

// Zuordnung der Kameras zu Gruppen

vector< int > KameraGruppen(M,-1);

// Zuordnung der Gruppen zu Speicher

vector< pair< int, int > > GruppenSpeicher(G); void main() {

InitialisierungO;

GreedyZuordnung();

for(;LokaleOptimierung();); // Vertausche solange zwei Kameras, bis keine Verbesserung mehr moeglich ist

// Ausgabe

for( int Kamera = 0; Kamera < M; Kamera++ ) {

int Gruppe = KameraGruppen[Kamera];

cout « "Kamera " « Kamera « " zeichnet auf Speicher "

« GruppenSpeicher[Gruppe].first « " und "

« GruppenSpeicher[Gruppe].second « " auf" « endl;

}

void InitialisierungO {

// Fuelle SpeicherGroessen entsprechend der Groesse der Speichermedien

// Fuelle KameraBandbreiten entsprechend der erwarteten Bandbreiten der Kameras

// Berechne Gesamtspeicher und GesamtBandbreite

float Gesamtspeicher = 0;

for( int Speicher = 0; Speicher < N; Speicher++ )

Gesamtspeicher += SpeicherGroessen[Speicher];

float GesamtBandbreite = 0;

for( int Kamera = 0; Kamera < M; Kamera++ )

GesamtBandbreite += KameraBandbreiten[Kamera]; float T = Gesamtspeicher / GesamtBandbreite;

// Leite die zu erzielenden GruppenGroessen aus den SpeicherGroessen und KameraBandbreiten ab

int Gruppe = 0;

for( int Speicherl = 0; Speicherl < N; Speicherl ++ ) {

for( int Speicher2 = Speicher1 +1 ; Speicher2 < N; Speicher2++ ) {

GruppenRestGroessen[Gruppe] =

SpeicherGroessen[Speicher1] *

SpeicherGroessen[Speicher2]

* ( 1 / (Gesamtspeicher - SpeicherGroessen[Speicher1])

+ 1 / (Gesamtspeicher - SpeicherGroessen[Speicher2]) ) / T;

GruppenSpeicher[Gruppe].first = Speicherl ;

GruppenSpeicher[Gruppe].second = Speicher2;

Gruppe++;

}

}

// fuelle Hilfsstruktur

for( int i = 0; i < G; i++ )

SortierteRestGroessen.insert( make_pair(GruppenRestGroessen[i], i) );

} void GreedyZuordnung() {

// baue eine sortierte Liste der KameraBandbreiten

vector< pair< float, int > > SortierteBandbreiten( G );

for( int Kamera = 0; Kamera < M; Kamera++ ) {

SortierteBandbreiten[Kamera].first = KameraBandbreiten[Kamera];

SortierteBandbreiten[Kamera].second = Kamera;

}

sort( SortierteBandbreiten.beginO, SortierteBandbreiten.end() ); while( SortierteBandbreiten.sizeO ) {

// merke die Kamera mit der groessten Bandbreite und entferne sie aus der sortierten Liste int Kamera = SortierteBandbreiten.back().second;

SortierteBandbreiten.pop_back();

// fuege die Kamera der Gruppe zu, die noch am meisten Kontingent uebrig hat

int Gruppe = (~SortierteRestGroessen.end())->second;

SortierteRestGroessen.erase( -SortierteRestGroessen.end() );

KameraGruppen[Kamera] = Gruppe;

GruppenRestGroesse[Gruppe] -= KameraBandbreiten[Kamera];

SortierteBandbreiten.insert( make_pair(GruppenRestGroesse[Gruppe], Gruppe) );

}

} void AendereKameraZuordnung( int Kamera, int Gruppe ) {

int alteGruppe = KameraGruppen[Kamera];

if (alteGruppe == Gruppe) // gleiche Gruppe => nichts zu tun

return;

// entferne betroffene Gruppen aus der sortierte Menge

SortierteRestGroessen.erase( make_pair(GruppenRestGroesse[alteGruppe], alteGruppe) );

SortierteRestGroessen.erase( make_pair(GruppenRestGroesse[Gruppe], Gruppe) );

// veraendere die Gruppen und weise die Kamera der neuen Gruppe zu GruppenRestGroesse[alteGruppe] += KameraBandbreiten[Kamera];

KameraGruppen[Kamera] = Gruppe;

GruppenRestGroesse[Gruppe] -= KameraBandbreiten[Kamera];

// fuege die veraenderten Gruppen wieder in die sortierte Menge ein

SortierteRestGroessen.insert( make_pair(GruppenRestGroesse[Kamera], Kamera) );

SortierteRestGroessen.insert( make_pair(GruppenRestGroesse[alteGruppe], alteGruppe) );

} bool LokaleOptimierungO {

bool Aenderungen = false;

for( int Kamerai = 0; Kamerai < M; Kamerai ++ ) {

for( int Kamera2 = 0; Kamera2 < M; Kamera2++ ) {

int Gruppel = KameraGruppen[Kamera1];

int Gruppe2 = KameraGruppen[Kamera2];

// Suche nach Kameras, die in unterschiedlichen Gruppen liegen if (Gruppel == Gruppe2) continue;

// Wird der quadratische Abstand zur Gruppenzielgroesse kleiner, // wenn die beiden Kameras ausgetauscht werden? int RestGroessel = GruppenRestGroesse[Gruppe1] +

KameraBandbreiten[Kamera1] - KameraBandbreiten[Kamera2];

int RestGroesse2 = GruppenRestGroesse[Gruppe2] +

KameraBandbreiten[Kamera2] - KameraBandbreiten[Kamera1];

// square(x) berechnet das Quadrat von x: x*x

if (square(RestGroessel) + square(RestGroesse2) >=

square(GruppenRestGroesse[Gruppe1]) +

square(GruppenRestGroesse[Gruppe2]))

continue;

AendereKameraZuordnung( Kamerai , Gruppe2 );

AendereKameraZuordnung( Kamera2, Gruppel );

Aenderungen = true;

}

}

return Aenderungen;

Mit der hergeleiteten Übertragungsrate r ij kann bei einer

Bandbreitenschwankung von 2 eine optimale Auslastung der inhomogenen Speichermedien 3 garantiert werden. Figur 6 zeigt den Ausfall von

Speichermedium C4 und den gleichzeitigen Bandbreiten-Anstieg aller

Datenproduzenten 2, die nicht auf Speichermedium C1 aufzeichnen. Für das Lastverhältnis von Speichermedium C1 zu Speichermedium C2 ergibt sich dann folgende Ungleichung:

[6] T*(sum_{i!=1} r_1 i+r_i1)/C_1 >= x*T*(r_42-r_21+sum_{i!=2}r_2i)/C_2

Unter Benutzung von [0], [1] und [2] erhält man:

[7] 1 +sum{i!=1}C_i/(C-C_i) >= x*(1 - C_1/(C-C_2) + C_4/(C-C_4)) Der linke Term lässt sich nach unten mit 2 - C_1/C abschätzen. Das

Lastverhältnis x nimmt seinen schlechtesten Wert dann an, wenn C_2 und C_4 dem größten Speichermedium (im folgenden mit C_max bezeichnet) und C_1 dem kleinsten Speichermedium (im folgenden mit C_min bezeichnet) entsprechen. Es ergibt sich dann als garantierte untere Schranke für das Lastverhältnis:

[8] x >= (2 - C_min/C) * (C-C_max) / (C-C_min)

Mit Ungleichung [8] kann für jedes inhomogene Speichersystem 1 ein garantierter Lastausgleich für den Fall berechnet werden, dass ein

Speichermedium 3 ausfällt und somit die Güte der Auswahl der Speichermedien 3 ermittelt werden.

Die vorangegangenen Betrachtungen haben sich vorwiegend mit der

Eingangslast auf die Speichermedien beschäftigt. Damit verbleibt das Problem der optimalen Speicherfreigabe. Dazu wird für jeden Datenproduzenten 2 die aktuelle Aufzeichnungsdauer als diejenige Zeitspanne definiert, für die von jetzt bis in die Vergangenheit alle Videodaten ohne Verlust vorhanden sind (liegen Daten auf einem ausgefallen Speichermedium, so gelten diese nicht als verloren).

Kriterium [Z]: Ziel der Speichermanagementeinrichtung 6 ist es die kleinste Aufzeichnungsdauer über alle Kameras zu maximieren.

Hierzu werden zunächst wieder Extrembeispiele betrachtet, die zu vermeiden sind und von denen sich einfache Lösungsansätze nicht erholen. In der Figur 7 werden drei Speichermedien 3 mit gleicher Kapazität gezeigt. Alle drei Speichermedien 3 waren zu Beginn leer und wurden sequentiell gefüllt (beispielsweise weil ein Speichermedium 3 nach dem anderen in das

Speichersystem 1 aufgenommen wurde). Die mit zählen versehenen Rechtecke eines Speichermediums 3 entsprechen der Reihenfolge in der die

Speicherblöcke beschrieben wurden. D.h. um Kriterium [Z] zu optimieren würde man immer den Speicherblock mit der kleinsten Zahl als nächstes beschreiben. Nun werden Systemlimitierungen hinzu gefügt, so dass man gezwungen ist, eine

Verteilung wie bei der Figur 3 vorgeschlagen zu verwenden. Fällt nun

Speichermedium C1 aus, so müssen die Datenproduzenten 2, die nur zwischen C1 und C4 wählen können zwangsläufig auf C4 aufzeichnen. Das hat zur Folge, dass die jüngsten Blöcke als erstes überschrieben werden und somit nach obiger Zielvorgabe die tatsächliche Aufzeichnungsdauer gegen 0 geht.

Es ist zwar unwahrscheinlich, dass man diesen Extremfall in Reinform in der Praxis anfindet. Nichtsdestotrotz kann man daraus ein allgemeines

Speichervergabeprinzip ableiten. Und zwar müssen zeitliche Speichercluster bei der Speichervergabe vermieden werden, da ansonsten bei Speicherausfällen oder anderen Veränderungen des Speichersystems 1 , die Aufzeichnungsdauer dramatisch einbrechen kann. Umgekehrt formuliert muss die

Speichermanagementeinrichtung 6 gewährleisten, dass Speicherblöcke ähnlichen Alters möglichst gleichmäßig über die verschiedenen Speichermedien 3 verteilt sind.

Um dieses Ziel zu erreichen liegt es nahe, die aktuelle Altersstruktur bei der Vergabe zu berücksichtigen. Dieses Vorgehen hat allerdings den großen

Nachteil, dass jede Unregelmässigkeit in der Altersstruktur sich zwangsläufig nach einem kompletten Überschreiben des Speichers (im folgenden auch

Periode genannt) wiederfinden lässt (eventuell in abgeschwächter Form). Die einfachste Art die aktuelle Altersstruktur zu betrachten ist, den ältesten Block jedes Speichermediums zu betrachten. An einen Datenproduzenten 2 wird nun Speicher des Speichermediums 3 mit dem ältesten Block vergeben. Dabei werden nur Speichermedien 3 berücksichtigt, auf die der Datenproduzent 2 auch aufzeichnen darf. Dieses Vorgehen wiederholt im Wesentlichen die bereits existierende Altersstruktur und ist somit ungeeignet. Durch randomisierte Ansätze kann man die Situation etwas verbessern. Der Zufall hat hierbei die Aufgabe, die aktuelle Altersstruktur bei der Auswahl weniger stark zu

berücksichtigen und somit die Wiederholung der Speichercluster in der nächsten Periode zu reduzieren.

Als ein Ausführungsbeispiel wird nun ein Algorithmus vorgeschlagen, der die aktuelle Altersstruktur komplett ignoriert und sich damit nach spätestens einer Periode vollständig von Störungen erholt hat. Der Algorithmus arbeitet wie folgt. Für jedes Speichermedium 3 wird ein Zähler eingeführt, der jedes Mal, wenn

Speicher von diesem Speichermedium 3 an einen Datenproduzenten 2 vergeben wird, um den entsprechenden prozentualen Anteil des vergebenen Speichers zum Gesamtspeicher dieses Speichermediums 3 erhöht wird. Fordert ein Datenproduzent 2 Speicher der der Speichermanagementeinrichtung 6 an, so vergleicht die Speichermanagementeinrichtung 6 die Zählerstände der potentiellen Speichermedien 3 und teilt dem Datenproduzenten 2 Speicher von dem Speichermedium 3 mit dem geringsten Zählerstand zu. Damit hält die Speichermanagementeinrichtung 6 die Zählerstände möglichst auf Gleichstand. Driften die Zählerstände auseinander, wurden die Datenproduzenten 2 derart auf die Speichermedien 3 verteilt, dass es unmöglich ist, die Speichermedien 3 gleichmäßig zu befüllen. Sind die Zählerstände weit auseinander gedriftet, so würde der Algorithmus nach einer Korrektur der Zuweisung der

Datenproduzenten 2 oder Datenmitgliedern zu Datenproduzenten 2 und zu Speichermedien 3 anfangen, das Speichermedium 3 mit dem kleinsten

Zählerstand zu bevorzugen und somit eine Clusterbildung entstehen lassen. Daher müssen die Zählerstände nach einer Korrektur entweder wieder auf 0 gesetzt werden oder der minimale Zählerstand künstlich erhöht werden, wenn die Abweichung zum maximalen Zählerstand zu groß wird. Dieselbe Situation entsteht, wenn ein neues Speichermedium 3 in das Speichersystem

aufgenommen wird. Auch hier muss der Zählerstand des neuen

Speichermediums 3 beispielsweise auf den Durchschnitt der anderen Zähler initialisiert werden. Ist ein Speichermedium 3 ausgefallen und kommt wieder in das Speichersystem 1 zurück, gilt das gleiche.

Eine mögliche Ausführung zu der Speichervergabe ist nachfolgend dargestellt: // Zaehler fuer Speichermedium i

float SpeicherZaehler[M];

// Groesse des Speichermediums i

float SpeicherGroesse[M];

// Verfuegbarkeit des Speichermediums i

bool SpeicherOnline[M];

// Liste der Speichermedien, die von Kamera i benutzt werden duerfen.

vector<int> KameraSpeicher[N];

// initialisiere alle Variablen

void lnit() {

for (int i = 0; i < M; i++) {

// zu Beginn werden alle Zaehler auf den gleichen Wert gesetzt SpeicherZaehler[i] = 0;

// Setze die SpeicherGroesse

SpeicherGroesse[i] =

SpeicherOnline[i] = true;

}

// Fuege fuer jede Kamera i die erlaubten Speichermedien j in

// die Liste KameraSpeicher ein.

}

// Wenn eine Kamera neuen Speicher braucht, wird die Funktion HoleSpeicher auf,

// um den Index des Speichermediums zu erhalten, auf den die Kamera j als naechstes

// aufzeichnen soll.

// Returnwert ist -1 , wenn keines der zugewiesenen Speichermedien online ist. int HoleSpeicher( int Kamerald ) {

int Speicherld = -1 ;

for (int k = 0; k < KameraSpeicher[Kamerald].size(); k++) {

int Speicherld2 = KameraSpeicher[Kamerald][k];

if (SpeicherOnline[Speicherld2]) {

// auf welchen Speicher wurde weniger aufgezeichnet? if (Speicherld == -1 oder SpeicherZaehler[Speicherld2] < SpeicherZaehler[Speicherld]) Speicherld = Speicherld2;

}

}

if (Speicherld >= 0) {

// Erhoehe den Zaehler des ausgewaehlten Speichers um eine Einheit // normiert auf die Gesamt-SpeicherGroesse.

SpeicherZaehler[Speicherld] += 1/SpeicherGroesse[Speicherld];

}

return Speicherld;

}

// Wenn ein Speichermedium ausfaellt, wird die Funktion SpeicherAusgefallen gerufen.

void SpeicherAusgefallen( int Speicherld ) {

SpeicherOnline[i] = false;

}

// Ist ein ausgefallenes Speichermedium wieder verfuegbar, wird die Funktion // SpeicherVerfuegbar gerufen,

void SpeicherVerfuegbar( int Speicherld ) {

int OnlineZaehler = 0;

float ZaehlerSumme = 0;

for( int i = 0; i < M; i++ ) {

if (SpeicherOnline[i]) {

OnlineZaehler += 1 ;

ZaehlerSumme += SpeicherZaehler[i];

}

}

SpeicherOnline[Speicherld] = true;

// Setze den Zaehler auf den Mittelwert der Zaehler der verfuegbaren Speicher if (OnlineZaehler)

SpeicherZaehler[Speicherld] = ZaehlerSumme / OnlineZaehler;

// Wenn es keine anderen online Speicher gibt, muss der Zaehler auch nicht mit // anderen Zaehlern synchronisiert werden.

}