Mobile Communication Networks

Lab 0: Hardware

Bei den Knoten in unserem Mesh-Netzwerk handelt es sich um Router der Firma Linksys (WRT54GS). Hierbei haben wir die vorhandene Firmware durch OpenWrt http://openwrt.org ausgetauscht. Nähere Informationen finden Sie dabei unter Programming_the_Linksys_WRT54GS_Wireless_Broadband_Router.

Für das Praktikum sei folgende sehr einfache Netztopologie für eine Multi-Hop Mesh-Netzwerk gegeben (siehe Abbildung):

Infrastructure of WRT lab network

Erkennbar hierbei ist, dass Knoten WRT6 direkt mit Knoten WRT7, jedoch nicht direkt mit Knoten WRT8 kommunizieren kann (er benötigt die Hilfe von Knoten WRT7). Als Routing-Protokoll haben wir das Dynamic Source Routing (http://www-2.cs.cmu.edu/~dmaltz/dsr.html ) Protokoll auf Layer 2 (Sicherungsschicht) prototypisch implementiert. Dieses soll auch im Praktikum verwendet werden.

Der Zugriff auf die Router erfolgt über telnet:

 zubow@linux:~> telnet wrt6

Lab 1: Cross-Compilation

Dieses Praktikum soll Ihnen einen Einblick in die Entwicklung von Software für Embedded Devices (Cross-Compilation) geben. Hierbei werden Sie mit Hilfe von OpenWrt Software für WRT54GS entwickeln. Zu diesem Zweck haben wir eine Linux-Entwicklungsumgebung (Toolchain, ect.) aufgebaut. Nähere Informationen dazu finden Sie unter Using_StandardizedDevelopmentEnvironment.

Für das Praktikum kann die Toolchain wie folgt gebaut und verwendet werden:

OpenWrt-Quellen

Die Quellen des OpenWRT-Projektes können über cvs abgerufen werden:

 cvs -d:pserver:anonymous@openwrt.org:/openwrt login
 cvs -d:pserver:anonymous@openwrt.org:/openwrt co buildroot

Benötigte Tools/Bibliotheken

Damit sich die Toolchain übersetzen lässt, werden die folgenden Tools bzw. Bibliotheken benötigt:

• wget, tftp
• cvs, subversion
• gcc, gcc-c++, bison, flex
• patch, gettext
• autoconf, automake
• zlib-devel

OpenWRT-Build-Prozess

Für die spätere Verwendung von Click wird ein C++-Compiler benötigt. Daher ist die folgende Änderung im $OPENWRT/buildroot/Makefile vorzunehmen:

 INSTALL_LIBSTDCPP:=true

Sollten alle benötigten Bibliotheken vorliegen, so kann OpenWRT mit Hilfe von make gebaut werden:

 linux:/home/wrt/buildroot/# make

Hinweis: Der initiale Build-Prozess ist sehr zeitaufwändig.

Andere Ansätze

Verwendung von CrossTool

Zugriff vom WRT auf Bibliotheken/Tools

Der (Flash-)Speicher auf den WRTs ist nicht nur limitiert, sondern auch extrem langsam. Für den Entwicklungsprozess kann man auf den WRTs Verzeichnisse via NFS mounten:

 @wrt6:/# mount MY_NFS_SERVER:/share/ /mnt/share -o nolock

Lab 2: Click

http://www.pdos.csail.mit.edu/click/click.gif

Click ist ein vom MIT entwickelter modularer Software-Router. Mit Hilfe der umfangreichen Click-API lassen sich schnell neue Router-Konfigurationen entwickeln. Auch wir werden uns bei der Entwicklung auf Click stützen.

Um Click mit Hilfe von OpenWRT zu bauen, muss das Makefile click.mk in das $OPENWRT/buildroot/make-Verzeichnis kopiert werden:

 #############################################################
 #
 # click
 #
 #############################################################
 CLICK_DIR:=$(BUILD_DIR)/click
 
 click-source: $(CLICK_DIR)/.unpacked
 
 
 $(CLICK_DIR)/.unpacked: $(DL_DIR)/$(CLICK_SOURCE)
       (cd $(BUILD_DIR); \
       svn co svn://merkur.sardmn.informatik.hu-berlin.de/brn/click)
       touch $(CLICK_DIR)/.unpacked
 
 
 $(CLICK_DIR)/.configured: $(CLICK_DIR)/.unpacked
       (cd $(CLICK_DIR); rm -rf config.cache; \
               $(TARGET_CONFIGURE_OPTS) \
               CFLAGS="$(TARGET_CFLAGS)" \
               AR_CREATEFLAGS="cru" \
               ./configure \
               --build=i686-pc-linux-gnu \
               --host=mipsel-linux \
               --disable-linuxmodule \
               --enable-brn \
               --enable-wifi \
               --enable-tools=mixed \
       );
       touch  $(CLICK_DIR)/.configured
 
 $(CLICK_DIR)/click: $(CLICK_DIR)/.configured
       $(MAKE) CC=$(TARGET_CC) -C $(CLICK_DIR)
 
 $(TARGET_DIR)/usr/bin/click: $(CLICK_DIR)/click
       install -c $(CLICK_DIR)/userlevel/click $(TARGET_DIR)/usr/bin/click
       $(STRIP) $(TARGET_DIR)/usr/bin/click > /dev/null 2>&1
 
 click: uclibc $(TARGET_DIR)/usr/bin/click 
 
 click-clean: 
       $(MAKE) -C $(CLICK_DIR) clean
       rm -rf $(TARGET_DIR)/usr/bin/click
 
 click-dirclean: 
       rm -rf $(CLICK_DIR)

Anschließend kann Click über den Aufruf:

 linux:/home/wrt/buildroot/# make click

gebaut werden.

Lab 3: Voice Over IP (VoIP)

Die IP-Telefonie, auch als Voice over IP (kurz VoIP) bekannt, ist das Telefonieren über ein Computernetzwerk auf der Grundlage des Internetprotokolls. Der wesentliche Unterschied zur herkömmlichen Telefonie besteht darin, dass die Sprachinformationen nicht über eine geschaltete Verbindung in einem Telefonnetz übertragen werden, sondern durch das Internet Protocol in Datenpakete aufgeteilt, auf nicht festgelegten Wegen in einem Netzwerk zum Ziel gelangen.

Ziel dieses Praktikums ist es, ein die Anwendbarkeit von VoIP in Wireless Multi-Hop Mesh-Netzwerken zu untersuchen und Lösungen zu unterbreiten. In diesem Zusammenhang sind folgende Fragen zu klären:

Session Initiation Protocol (SIP)

• Welche Anforderungen werden an die Infrastruktur gestellt?
• Welche Probleme existieren im Zusammenhang mit Firewall & NAT?
• Gibt es eine akzeptierte SIP-API (z.B. jain)?
• Ist die SIP-Infrastruktur (SIP Proxy Server, SIP Redirect Server, Registrar) per Definition zentral oder ist eine dezentrale Lösung (P2P) möglich? Welche Ansätze sind aus der Literatur bekannt?

Real-Time Transport Protocol (RTP)

• Welche Anforderungen werden an die Infrastruktur gestellt? (Latenzen, Bandbreite, etc.) Welche Qualität wird von einem Nutzer erwartet?
• VoIP vs. Push-To-Talk (PTT) - Welche Unterschiede gibt es hinsichtlich der Anforderungen, der Infrastruktur, ...? Ist PTT einfacher zu realisieren (Ansätze)?
• Wie wird ein Hand-Over (während eines Telefonats) zwischen APs bei 802.11 realisiert (Probleme im Zusammenhang mit VoIP)?
• Existieren Routing-Algorithmen, welche sich für das VoIP besonders eignen?

Im anwendungsorientierten Teil des Praktikums sollen die folgenden Aufgaben erfüllt werden:

• Installation eines SIP-Servers (WRT bzw. Netgear)
• First Call (z.B. via kPhone)
• Administration des SIP-Servers (Anlegen von neunen Nutzern, Anbindung unserer SIP-Server an bestehende SIP-Infrastruktur (z.B. sipgate.de)

SIP-API http://developers.sun.com/techtopics/mobility/apis/articles/sip/

Durchführung des Praktikums

SIP basics

Das Session Initiation Protocol (SIP) wird bei VoIP-Telefonie dazu benutzt, um die Parameter für die eigentliche Datenübertragung festzulegen und eine Adressierung und Lokalisierung von Teilnehmern unabhängig von ihrem Aufenthaltsort und ihrer IP-Adresse zu ermöglichen. Das Telefongespräch selbst wird nach der session initiation dann mittels RTP zwischen den Kommunikationspartnern direkt, also ohne weiter Beteiligung des SIP-Servers, statt.

Um einen Telefonanruf aufzubauen, versendet der VoIP-Client des Anrufers eine session initiation message an den für die Adresse des Angerufenen zuständigen SIP-Server. Die Liste der SIP-Server für eine Domain bezieht der client über DNS, analog zu SMTP-Servern. Der SIP-Server leitet, sofern der Angerufene verfügbar ist, die session initiation message an den Client des Angerufenen weiter.

Die session initiation message enthält eine Beschreibung der Sitzung, die der Anrufer aufbauen möchte. Zu dieser Beschreibung gehören auch Informationen über das zu verwendende Protokoll (z.B. RTP) und spezifische Parameter.

Nimmt der Anrufer den Telefonanruf an, antwortet der angerufene client direkt mit einer identischen Sitzungs-Beschreibung. Dann bestätigt der Anrufer noch den Empfang dieser Nachricht, womit die session initiation beendet ist.

SIP in mesh-Netzwerken

Die wohl wichtigsten Anforderungen an mesh-Netzwerke sind die Mobilität der Teilnehmer, Selbstorganisation mit möglichst wenig Konfigurationsaufwand und Robustheit gegenüber Störungen. Da als Übertragungsmedium Funk verwendet wird, können diese häufig vorkommen, und die Netzwerk-Topologie ändert sich oft. Es kann auch vorkommen, daß das mesh-Netzwerk in mehrere Teilnetze partitioniert wird und es in diesem Fall Paare von Nodes gibt, zwischen denen kein Pfad mehr existiert.

Da es in einem mesh-Netzwerk bestenfalls eine Vielzahl verschiedener Pfade zwischen je zwei Kommunikationspartnern gibt, wirken sich viele Störungen allerdings nur zeitlich und räumlich sehr begrenzt aus. Allerdings können durch die Benutzung verschiedener Pfade innerhalb einer Verbindung auch Probleme auftreten wie z.B. große Laufzeit-Unterschiede zwischen einzelnen Paketen, große Unterschiede zwischen nutzbaren Bandbreiten auf verschiedenen Pfaden und Mehrfach-Auslieferungen von Paketen.

Wie bereits beschrieben, basiert das SIP-Protokoll auf zentralen Servern, von deren Erreichbarkeit beide Kommunikationspartner abhängen. Für ein mesh-Netzwerk ist diese Architektur aufgrund der erwähnten Eigenschaften ungeeignet, da ausreichende Redundanz kaum zu realisieren ist.

Ausserdem müssen sich Teilnehmer im herkömmlichen SIP-Modell bei dem für sie zuständigen Server anmelden, um diesem die aktuelle IP-Adresse des clients mitzuteilen. Die IP-Adresse des eigenen SIP-Servers in der Konfiguration des clients einzutragen und sie ggf. nach einem Ortswechsel ändern zu müssen, widerspricht der Forderung nach Selbstorganisation in einem mesh-Netzwerk.

Problemstellung im Praktikum

Wir werden im Praktikum die beiden letzt genannten Probleme untersuchen und versuchen, Lösungsansätze zu finden. Zum einen soll der SIP-Server-Dienst dezentralisiert werden und auf WLAN Access Points zur Verfügung stehen. Damit wird der Forderung nach Redundanz und Robustheit gegen starke Veränderungen der Netzwerk-Topologie nachgekommen.

Ausserdem werden wir den click modular router verwenden, um Pakete, die zu SIP-Verbindungen gehören, zu filtern und ggf. verändert weiterzuleiten. Das ist nötig, um einen verteilten SIP-Dienst für VoIP-Clients maximal transparent zu realisieren und um die Forderung nach Selbstorganisation zu adressieren.

Diese Herangehensweise scheint sinnvoll, da VoIP-Telefonie im mesh-Netzwerk zuerst einmal verwendbar werden muss, bevor man die Parameter der Verbindungen und ihre Auswirkungen auf das Telefonat untersuchen kann.

Teilprobleme und Lösungsansätze

Die Bearbeitung der gewählten Aufgabe kann grob in dreigeteilt werden. Zuerst soll ein SIP-Server zentral im LAN aufgesetzt werden, so daß VoIP-Telefonie prinzipiell möglich wird. Um minimale Konfigurationsfreiheit und Selbstorganisation zu erzielen, wird dann mittels click ein Modul zur spezifischen Address Translation für SIP-Verbindungen entwickelt und integriert.

Im zweiten Schritt soll ein Distributed Hash Table entwickelt und implementiert werden, der die für die Aushandlung einer Session mit SIP wichtigen Daten redundant enthalten wird. Ausfallsicherheit im Fall von Netzwerk-Störungen und eine Ablösung der zentalistischen SIP-Architektur durch ein verteiltes Modell ist hierfür die Motivation. Über Aspekte der Sicherheit einer solchen Lösungen soll nachgedacht werden, wenn auch nicht unbedingt ein Ergebnis erzielt werden muss. Wenn der DHT verfügbar ist, kann der zentrale SIP-Server angepasst werden, um diesen Dienst statt seiner internen Datenbank zu benutzen, womit ein gfreifbares Zwischenergebnis vorläge.

Zum Abschluss des Praktikums soll ein minimaler SIP-Server implementiert werden, der auf den einzelnen Access-Points laufen wird und SIP-Verbindungen lokal auf dem dem Teilnehmer nächsten AP beantwortet. Diese SIP-Server werden den im letzten Arbeitsschritt erstellten DHT benutzen und click verwenden, um die SIP-Verbindungen abzufangen und auf das lokale System umzuleiten.

An dieser Stelle sollte dann eine verwendbare Infrastruktur für VoIP-Telefonie zur Verfügung stehen, so daß weitere Eigenschaften von VoIP in mesh-Netzwerken untersucht werden können. Diese weiteren Arbeiten sind allerdings nicht Bestandteil des Praktikums und Thema für weitere Arbeiten in diesem Bereich.

Dokumente zu SIP und DHTs

[Session Initiation Protocol [1]]

[Distributed Hash Tables [2]]

Chord, Pastry, Kademlia

Chord wurde bereits in C++ implementiert. Der Sourcecode der Implementation ist verfuegbar. Das folgende Dokument beschreibt, wie man diese Implementation bekommt und installiert: [3]. Leider hoert sich das nicht so wirklich benutzbar an: "This process (building applications with the existent Chord implementation) is not for the faint-of-heart: as of April 2005, it is not well documented and has only been done by graduate students that are very familiar with the internals of the Chord code. The difficulty is further compounded by the fact that the implementation makes use of the somewhat under-documented SFS libraries." Das hoert sich erst mal so an, als wuerden wir mehr Zeit damit zubringen, mit dieser Implementation klarzukommen als wir brauchen wuerden, selber eine zu bauen. Dazu kommt, was Christian schon bei der Vorstellung von Chord erzaehlt hatte: Dass Chord Probleme haben koennte, mit gleichzeitigen Node Joins/Leaves klarzukommen. Dem Chord-Paper ([4]) laesst sich entnehmen, dass im Fall von gleichzeitigen Joins/Leaves die Performance geopfert wird, um die Korrektheit des Systems zu erhalten. Chord arbeitet also unter diesen Umstaenden noch korrekt, aber - abhaengig von der Anzahl der Nodes etc - sehr viel weniger performant. Die von Chord unter normalen Umstaenden eingehaltene obere Grenze von O(log N) Nachrichten wird dann zu einer O(N)-Grenze - wenn ich das Paper richtig verstanden habe. Die Frage ist: Erwarten wir so eine starke Fluktuation fuer die SIP-Anwendung? Wie ist es bei der ARP-Anwendung? Waere dieser Performance-Einbruch akzeptabel? Weiterhin ist mir auch nicht klar, was die MIT-Implementation da genau implementiert, wie vollstaendig die ist etc. Implementieren die nur das Basic Chord Protocol oder auch die Erweiterungen? Basic Chord kommt naemlich mit gleichzeitigen Joins/Leaves gar nicht klar, das erreichen erst die Erweiterungen. Ein System, das scheinbar so aehnlich funktioniert wie Chord ist Pastry, das von Microsoft Research ([5]) entwickelt wird. Davon gibt es auch zwei Implementationen, eine in Java und eine in C#. Also nichts fuer uns. Kademlia verfolgt einen anderen Ansatz als Chord und Pastry: Dort werden die Nodes in einer Baumstruktur angeordnet statt in einem Kreis. Waehrend die Autoren des Chord-Papers sich laenglich ueber die Eigenschaften von Chord auslassen was Fehlertoleranz, Performance etc angeht, sind solche Eroerterungen in dem Kademlia-Paper eher duenn gesaet. Obwohl das Kademlia-Protokoll in einigen Systemen (Overnet, cdonkey) implementiert ist, gibt es scheinbar keine fuer uns benutzbare API.

Informationen zum SVN-Repository

Hacking the Netgear wgt634u