Und zwar hier.
Papierkurzfassung
Die Autoren des Artikels haben eine Software implementiert, die die Ideen umsetzt, die sie im Artikel beschreiben. Diese Software heisst Bullet’ (ausgesprochen Bulletprime), und verteilt Daten, so in etwa wie Bittorrent das macht. Bullet’ setzt sich aus verschiedenen Komponenten zusammen. Die Knotenlisten (also welche Knoten es in dem Netz gibt, und mit welcher Anbindung) werden mit dem P2P-Framework RanSub ausgetauscht. Sobald ein Knoten eine neue Peerliste bekommt, guckt er, ob er seine jetzigen Peers (Sender und Empfänger) ersetzen kann durch Knoten in dieser neuen Liste. Damit wird kontinuierlich die Performance des Netzwerks geupdaet. Bullet’ schliesst die Verbindung zu Peers, die von der Durchschnittsbandbreite signifikant abweichen. Mal sehen, inwiefern man diese Ideen umsetzen kann für unseren P2P-Streamer.
Bald kriegen wir einen Planetlab Account, um unsere Software zu entwickeln, mal sehen wie sich unsere Ansätze in der “realen” Welt verhalten 🙂
Posted in Netzstaub, Programmstaub
Leave a comment
Papierkurzfassung, weiter geht’s
Anfragestrategie
Ähnlich wie bei den Algorithmen für das Entdecken von neuen Peers sind auch die Algorithmen für die Anfrage von Daten extrem wichtig. Hier gibt es wieder zwei grundlegende Möglichkeiten: der Empfänger kann die Daten analysieren, die er empfangen hat, und anhand dieser Daten neue Datenblöcken bei seinen Nachbarn anfordern. Bei der zweiten Möglichkeit bekommt der Sender von allen Empfängern eine Zusammenfassung der empfangenen Daten, und entscheidet dementsprechend, welche Daten er den Empfängern zukommen lässt. Dadurch wird die Logik des Empfängers extrem vereinfacht, weil er praktisch nur noch “dumm” die Daten empfängt. Nachteil ist allerdings, dass Synchronisierung unter mehreren Sendern notwendig ist, um das Senden vielfache Senden derselben Datenmenge zu verhindern.
Anfragestrategie heisst aber auch, welche Datenblöcke (ziemlich alle Verfahren teilen die zu versendende Datenmenge in kleinere Blöcke auf) in welcher Reihenfolge anzufordern sind. Empfangen zum Beispiel alle Knoten die Daten in derselben Reihenfolgen, bleibt kaum noch Spielraum übrig, um von mehreren Knoten gleichzeitig andere Daten zu empfangen um so den Durchsatz zu erhöhen. Weiter stellt sich die Frage, ob ein Knoten direkt nachdem er erfahren hat, dass es neue Daten gibt, diese anfordert (bzw. zugeschickt bekommt, je nach Anfragemodell)? Würde er ein bisschen warten, wäre es möglich, diese Daten auch bei anderen Knoten zu bekommen. Es muss also zwischen “Geschwindigkeit” und “Fairness” abgewogen werden.
Da mich P2P-Streaming mehr interessiert: bei Streaming fällt zumindest die Frage nach der “Frische” der Daten weg. Alle Knoten bekommen halbwegs dieselben Daten gleichzeitig, ein grosser Spielraum macht da kein Sinn, weil dann der Stream ja veraltet ist, und für Empfänger nicht mehr interessant. Streuen könnte man da höchstens innerhalb der “Pufferzeit”, also der Zeit, die von den Peers benutzt wird, um einigermassen viele Daten zusammen zu kriegen, damit der Stream nicht ruckelt. Ich meine auch, dass bei Streams ein Anfragemodell, wo die Empfänger die Sender fragen, nicht effizient ist (aber das wird sich noch reinstellen, dividuum ist da anderer Meinung, und im Moment funktioniert sein Ansatz deutlich besser :).
So, demnächst geht es weiter
Posted in Netzstaub, Programmstaub
Leave a comment
Papierkurzfassung: Maintaining High Bandwidth…
Wie versprochen, eine kleine Zusammenfassung des Papiers “Maintaining High Bandwidth under Dynamic Network Conditions”, das ich gestern kurz verlinkt hatte. Thema des Artikels ist das Verteilen von Daten in einem Peer-to-Peer Netzwerk, zum Beispiel um ISOs oder Patches zu verteilen, oder Multimediadaten zu verteilen, ohne einen hohen Load auf den “primären” Datenverteiler einbüssen zu müssen. Die Daten, die verteilt werden, sind meistens nur von einer einzigen Quelle erhältlich, werden aber von vielen Leuten gleichzeitig und schnell gezogen (in dem Artikel, und scheinbar auch woanders, wird dieser Effekt “flash-crowd effect” genannt).
Seit geraumer Zeit gibt es jetzt zum Beispiel BitTorrent, in dem Artikel wird untersucht, wie man ein solches Verfahren verbessern kann. Das Interessante ist aber, dass bei dem Versuch diese Verteilungsverfahren zu optimieren, verschiedene Alternativen vorgeschlagen und dokumentiert werden. Man kriegt also einen Einblick, wie solche Peer-to-Peer Protokolle zu designen sind, je nachdem, welchen Schwerpunkt man haben will. Eine wichtige Entscheidung ist z.B., ob man ein faires Netzwerk haben will, wo praktisch jeder Knoten gleich runterlädt und hochlädt, oder ein schnelles Netzwerk (bei dem also ein Knoten so schnell zu den Daten kommt, die er haben will). Die untersuchten Entscheidungen in dem Artikel sind:
- Ob Knoten (bzw. Peers) in dem P2P-Netz die Daten gesendet bekommen (PUSH-Modell), oder diese Daten anfragen (PULL-Modell)
- Welcher Algorithmus eingesetzt wird, um neue Knoten zu finden, die gute “Transfer”-Charakteristiken haben (Bandbreite, Latenz)
- Welche Daten angefordert werden sollen, je nachdem wie die Netzwerksituation ist
- Welche Daten anderen Peers zu senden sind
- Welche Verfahren eingesetzt werden, um die Daten umzukodieren (z.B. Fehlerkorrektur, oder gar keine Kodierung)
Push oder Pull?
Push ist natürlich die Methode, die einfacher zu realisieren ist. Bei Streaming-anwendungen sollten z.B. alle empfangenden Knoten dieselben Daten mit derselben Geschwindigkeit bekommen. Allerdings wird es gleich komplizierter, wenn Daten von mehreren Sendern gleichzeitig empfangen werden. In dem Fall müssen die Empfänger den Sendern mitteilen, welche Daten sie schon empfangen, damit nicht doppelte Pakete verschickt werden (alles klar?). Bei Pull können die Empfänger genauer kontrollieren, was sie empfangen wollen und von wem. Allerdings wird dadurch die Latenz der Kommunikation erhöht, und es kann unter Umständen auch zu einer nicht zu ignorierenden Erhöhung der ausgetauschten Datenmenge kommen. Hier gibt es also keinen klaren Gewinner, und in dem implementierten Ansatz der Autoren werden auch beide Verfahren gleichzeitig verwendet.
Nachbarnsuche (Peering-Strategie)
Ein extrem wichtiger Punkt (vielleicht der wichtigste) ist, wie ein Knoten seine Nachbarn findet, wie es sie auswählt, und wie er neue Nachbarn hinzuzieht, wenn Knoten ausfallen oder sich ihre Verbindung verschlechtert. Im Idealfall weiss jeder Knoten über alle anderen Knoten bescheid, und kennt auch ihre Parameter in Sachen Bandbreite, usw… Das ist natürlich kaum möglich, denn der Overhead, diese ganze Daten im Netzwerk zu verteilen wäre viel zu hoch (das ist auch so eins der Probleme der herkömmlichen Multicast-Routing Algorithmen). Eine andere Möglichkeit wäre, das ein zentraler Knoten diese Information festhält, und ich glaube (aber ich weiss nicht wirklich genau wie Bittorrent funktionniert), dass in Bittorrent diese Rolle von dem Tracker übernommen wird. Ist dieser Tracker nun weg oder schlecht erreichbar, bricht das Ganze zusammen. Nicht zu übersehen ist auch die Bandbreite, die der Tracker dann zur Verfügung stellen muss, um diese Daten managen zu können. Ein weitere “triviale” Möglichkeit wäre einfach, dass jeder Knoten eine feste Liste von Nachbarn ermittelt, und diese dann nicht mehr ändert. Wenn diese Knoten aufhören oder nicht mehr erreichbar sind, oder diese Anfangsliste einfach schlecht ist, hat der Knoten verloren. Ein sinnvoller Ansatz ist also eine Peeringstrategie, wo der Knoten nicht über ein globales Wissen verfügen muss (das gesamte Netzwerk kennen), und auch nicht mit vielen Nachbarknoten kommunizieren muss, aber trotzdem relativ schnell gute Nachbarn finden kann.
Ich weiss nicht, wie die das im Artikel lösen (noch nicht komplett durchgelesen), aber ein sinnvoller Ansatz wäre denke ich eine Art “randomisierte” Aggregierung von Nachbarsdaten durch die Knoten selber. Also Knoten A kommuniziert mit 10 Knoten, welche selber 10 Knoten als Nachbarn haben, A kann mit diesen 10 Knoten die kompletten Nachbarsdaten austauschen (also mit Tiefe 1), irgendwie die 5 Besten + 5 Zufällige zusammenbasteln, und an weitere Knoten schicken (oder an den Tracker, der deswegen nicht alle Daten von allen Peers kennen muss). Kommt ein neuer Knoten in das Netz, kriegt er eine zufällige, aggregierte Menge von Nachbarn, und kann sich so durchhangeln. Gehen ein paar Knoten hops, können ihre Nachbarn beim Tracker wieder “randomisierte”, im Durchschnitt gute Nachbarn bekommen. Hauptsache, im Durchschnitt klappt es gut, und relativ schnell kann man die Nachbarnauswahl verfeinern, indem man neue Nachbarn hinzunimmt, und die schlechtesten rauswirft.
So, das ist auch genug für heute, denn langsam wird es spät. Mehr in den nächsten Tagen.
Posted in Netzstaub, Programmstaub
Leave a comment
Drucken und drucken…
Dieser Eintrag wird ein bisschen nach Anfaenger-Eintrag aussehen, aber was solls. Ich habe beschlossen all die Dinger, mit denen ich rumgefrustet habe, zu bloggen, dann bleibt wenigstens eine Spur fuer mich uebrig. Und dieses “Ach den Schrott hab ich doch schonmal gemacht, wie ging das denn nur”-Gefuehl ist dann hoffentlich weg. Ein ganz christlicher Hintergedanke dabei ist auch, dass ich dadurch anderen Leuten vielleicht helfen kann. Dann wird mein Karma besser, ich kann ohne Alptraueme schlafen, und der ganzen guten Welt geht es dann praechtig.
Also, erster Eintrag in dieser Kategorie: heute habe ich beschlossen meinen alten guten lauten langsamen DecLaser 3500 zu ersetzen, und zwar durch einen billig-Tintenpisser. Der DecLaser kann nicht mal Dokumente korrekt ausdrucken, die mit Pages erzeugt worden sind. Auf jeder Seite ist dann so eine Art haesslicher grauer Hintergrund zu sehen, der total nach Apple-hype aussehend Brief sieht dann nur noch nach Guelle aus, und sowieso hat der Drucker keine Duplex-Einheit. Die hat naemlich TNT auf dem Schrott entsorgt, *seufz*. Da ist er also, der neue Drucker, ein CANON PIXMA iP3000 (weil die Patronen so billig sind, “dass sich sogar Refillen nicht mehr lohnt”). Der kann naemlich auch CDs bedrucken, was sehr wichtig ist (wie will man sonst professionell aussehende Software-releases unters Volk bringen?). Also, Drucker ausgepackt, erstmal 10 Minuten nach dem Stromanschluss gesucht (das nicht im Handbuch dokumentiert ist): wer es auch sucht, links hinten 🙂 Dann den Drucker in den Airport Express gesteckt, Patronen eingesteckt, und dann gings los mit der Scheisssoftware. Ich habe 2 Clientrechner fuer den Drucker, spaeter wird Dividuum noch das Teil mit CUPS benutzen: eine OSX Kiste, und eine WinXP Kiste. Angefangen mit der XP Kiste, Treiber von der CD installiert, dann neuen Drucker hinzufuegen ueber die XP Oberflaeche. Da ist es ganz wichtig, als PORT einen TCP/IP PORT zu definieren mit der IP des Airport Expresses, und den “RAW”-Modus auszuwaehlen (bei mir war LPR angewaehlt, und das mit dem RAW habe ich dann erst 2 Stunden spaeter rausgekriegt). Danach als Druckertyp einfach Canon PIXMA iP3000 auswaehlen, Printer Heads konfigurieren, und alles muesste funktionnieren. Ganz wichtig ist wie gesagt dieser “RAW” Modus, port 9100, SNMP hab ich ausgeklickt.
Unter OSX war das noch einfacher. CD rein, Treiber installiert, neustarten (na super), dann Print irgendwo auswaehlen, und automagisch taucht da der iP3000 in der Liste auf (als Rendezvous printer). Das wars. OSX ist in dem Punkt schon ganz nett 🙂
Posted in Computerstaub
Leave a comment
Da gibt es nette Musik
Und zwar hier, ich habe bis jetzt nur ein paar Tracks von MMW with John Scofield (was auch immer MMW ist). Das Dir kam durch Schrikdraad.
Posted in Musikstaub
Leave a comment
Und ecto spinnt auch rum
Irgendwie spinnt die Zeit in ecto rum, deswegen die komische Reihenfolge der Beiträge. Ob das wohl mit meinem LD_PRELOAD zusammenhängt? :}
Posted in Programmstaub
Leave a comment
Streamingpapier
Ein sehr interessantes Paper zum Thema Contentdistribution über P2P Netzwerke ist Maintaining High Bandwidth under Dynamic Network Conditions, von Dejan Kostic, Ryan Braud, Charles Killian, Erik Vandekieft, James W. Anderson, Alex C. Snoeren und Amin Vahdat. Morgen mehr zu dem Paper.
Posted in Netzstaub, Programmstaub
Leave a comment
Der geile bl0rgo-caster
Ich lebe in der wilden bl0rg-wg, und die muss ganz im bl0rg-stil auch komplett automatisiert, überwacht und verkabelt werden. Zum Beispiel müssen die Einkäufe automatisch erfasst werden, damit der Traum des selbstfüllenden Kühlschranks ein bisschen näher rückt. Das Tolle ist: ziemlich jedes Produkt, das man kaufen kann, ist mit einem Barcode versehen (bis auf das Brot vom Bäcker, aber das kriegen wir auch noch irgendwie geregelt). Im Entropia lag noch ein alter Barcodescanner, der prompt analysiert wurde, und wie sich rausstellte ganz bequem die Barcodes über seriell rausgebeamt hat. Nach ein bisschen Rumfrusten mit bestimmten seriellen Interfaces, die nicht funktionierten, kann man jetzt die Barcodes ganz “bequem” (*hüstel*) mit folgendem Shellscript extrahieren:
#!/bin/sh
DEV=/dev/ttyE0
stty -F $DEV cs8 -parenb -cstopb speed 9600 icrnl -ixon
while true; do
i=`head -n 1 $DEV`
echo -en "barcode $i\nquit\n" | nc localhost 12345
done
DEV ist hier die serielle Schnittstelle. Als erstes setzt das Skript die nötigen Parameter für die Kommunikation (9600 bauds, 8n2, Carriage Return unix-konform nach Newline konvertieren, und Flowcontrol aus). Dann wird jeweils die neuste Zeile gelesen (also das neuste Barcode), und dieser Barcode wird dem Bl0rgo-caster übergeben. Insgesamt also schön einfach, nur ein bisschen Glue notwendig. Hiermit hätten wir schonmal die Sprache Shell benutzt (und das sind auch die einzigen Zeilen code von mir in diesem geilen System, der Rest ist alles von Dividuum. Ich hab mich da gleich zu Anfang irgendwie mit meinem UDP Broadcast-system verfahren, und konnte nicht mal sinnvoll UDP-Nachrichten auf dem Ethernet schicken).
Der bl0rgo-caster an sich besteht aus einem Server, der über UDP Broadcast messages senden und empfangen kann, und diese Nachrichten über TCP an verschiedene Listener dann übermitteln kann. Also, wenn man einfach nur Nachrichten broadcasten will, kann man eine UDP Nachrichten schicken. Wenn man sie empfangen will, kann man über TCP connecten, und lauschen. Der Clou ist aber, dass der bl0rgo-caster über LUA skriptbar ist. Wenn man also per TCP connected, kriegt man eigentlich eine LUA-Shell, und kann dort LUA-Kommandos absetzen. Beim Start parst der Server eine Skript-datei, die er dann auch später reloaden kann. Dort kann man dann z.B. Kommandos einbauen, um XMMS zu steuern. Der bl0rgo-caster benutzt libevent, um die verschiedenen Datenquellen zu pollen. Der LUA-Code, der z.B. unsere XMMS-Barcodes analysiert, sieht wie folgt aus:
function onBroadcast(datatype, data)
-- print("onUDPData: " .. datatype .. " - " .. data)
-- print(datatype)
-- print(data)
-- print("---")
if datatype == 0 then
Client.writelnAll("Message: " .. data)
elseif datatype == 1 then
Client.writelnAll("Barcode scanned: " .. data)
if (data == "1234567") then
os.execute("xmms -r")
elseif (data == "1231313") then
os.execute("xmms -f")
else
print("huh?")
end
end
end
Hier sieht man, wie der Messagetyp analysiert wird, und wenn ein Barcode kam XMMS gesteuert wird. Doch das war für den wilden Dividuum nicht genug, ein weiteres Tool in der bl0rgo-caster Suite zeigt Broadcast messages als X11-Popup an, so dass man immer am Laufenden gehalten wird, was gerade in der WG passiert (denn nachher werden alle Sensoren in der WG ihre Nachrichten in den bl0rgo-caster dumpen). Diese Popuptool ist in Ruby geschrieben, und verwendet intern TK um die Grafik anzuzeigen. Das sind also insgesamt 5 Sprachen, die zum Einsatz kommen: ruby, C, shell, Lua und Tk (insofern Tk als Sprache gilt). Beim Testen von Popup unter meiner Debian kam noch ein komischer Fehler vor: die clear Methode von TkText war irgendwie nicht definiert (?), also mussten wir wirklich ein Stückchen Tk reinziehen:
# UAAAAAAAAAAAAAAArgggggg
class TkText
def clear
tk_send_without_enc('delete', "1.0", 'end')
self
end
end
Wie lecker… 🙂
Den Code für den bl0rgo-caster könnt ihr aus unserem Subversion ziehen:
$ svn co svn://bl0rg.net/bl0rgo-caster/
Erweiterungsideen sind z.B. ein Listener, der alle Events als RSS veröffentlicht. Mal sehen, das werden wir bestimmt in Lisp oder so hacken, damit der Sprachenchaos komplett ist.
Posted in Programmstaub
1 Comment
Zeit faken unter Unix
Weil jemand im IRC danach gesucht hat, hier ein kleines Stück Code um die Zeit für ein Programm zurückzusetzen. Ziemlich alle Unixoide Programme werden wohl den Systemcall gettimeofday benutzen, um die Uhrzeit zu bekommen. Zum Glück ruft man syscalls nicht von Hand auf, denn es gibt ganz viele schöne Wrapperfunktionen in der libc. In dem Fall die gut benannte Funktion gettimeofday. Nun wird die libc meistens dynamisch verlinkt, so dass man einen weit verbreiteten Trick anwenden kann, um System Calls zu hijacken. Der dynamische Loader kann nämlich Libraries “vorschalten”. Im Klartext heisst das also: wir tun gar nicht Syscalls hijacken, sondern die Wrapperfunktionen zu diesen Syscalls. Und weil wir selber so faul sind, wollen wir aus unserer Hijackfunktion nicht noch selber den richtigen Syscall aufrufen, sondern rufen gleich die eigentlich Funktion auf. Im Code sieht das dann so aus:
#include <stdlib.h>
#include <sys/time.h>
#include <dlfcn.h>
#include <assert.h>
typedef int (*gettimeofday_t)(struct timeval *, struct timezone *);
static gettimeofday_t old_gettimeofday = NULL;
#ifndef RTLD_NEXT
/* linux... */
#define RTLD_NEXT (-1l)
#endif
int gettimeofday(struct timeval *tp, struct timezone *tzp) {
int ret;
if (old_gettimeofday == NULL) {
old_gettimeofday = (gettimeofday_t)dlsym(RTLD_NEXT, "gettimeofday");
assert(old_gettimeofday != NULL);
}
ret = (*old_gettimeofday)(tp, tzp);
if (tp) {
tp->tv_sec -= 50000;
}
return ret;
}
Als erstes checken wir ob wir schon die Adresse von der “richtigen” Funktion kennen, und wenn nicht, dann holen wir die uns mit der Funktion dlsym. An der Stelle ein kleiner übler Hack für Linux. Da muss man irgendwie __USE_GNU definieren, damit der sich die gewollte Definition von dlsym holt, nach 2 Versuchen ging das bei mir irgendwie nicht, ich hatte nicht weiter bock, deswegen dieses #define RTLD_NEXT. Nachdem wir die alte Funktion haben, rufen wir diese auf, ziehen 5000 Sekunden von dem Ergebnis ab, et voila. Das Ganze kann mit folgendem Makefile compilen:
all: libfakedate.so
libfakedate.so: fakedate.c
$(CC) -D__USE_GNU -fPIC -shared -o $@ $
Und mit folgender Zeile dann benutzen:
$ LD_PRELOAD=`pwd`/libfakedate.so date
Schick! Unter OSX tut das nicht, sondern loopt, aus welchen undefinierbaren Gründen auch immer (kein ELF, sondern Mach-O, portiertes dlcompat, ach-weiss-ich…).
Posted in Programmstaub
1 Comment