Multicast [Konzept: 1. Was ist Multicast? 2. Tolle neue Möglichkeiten durch Multicast 3. Umsetzung im Ethernet 4. IGMP (Internet Group Management Protocol) 5. Anwendungsbereiche, was kann man damit überhaupt machen 6. Details, Details (bei wem subscribe ich, der Sender weiß nicht mal, wieviele zuhören) 7. Routing-Ansätze: Sparse Mode vs. Dense Mode 8. Die einzelnen Protokolle kurz angesprochen 9. Neuere Entwicklungen: Reliable Multicast ] [Abstract:] Ein Radiosender hat keine Mehrkosten, wenn ein Hörer mehr zuschaltet. Ein Fernsehsender ebenso. In IP-Netzen ist das anders, wenn man Streaming benutzt. Dort muß man die Daten an jeden Empfänger einzeln abschicken, d.h. Groß-Events brauchen mehr Bandbreite als man heute kaufen kann. Selbst mit Breitband-Internet gesegnete User müssen sich daher heute mit dünnen Strömchen begnügen, wenn sie an Live-Ausstrahlungen partizipieren möchten, da sonst zehn bis zwanzig ADSL- oder Kabelmodem-Empfänger alleine die gesamte Bandbreite des Senders verbrauchen würden. Es ist offensichtlich, daß hier ein anderes Konzept her muß. Es besteht kein Zweifel daran, daß die Datenpakete beim Empfänger ankommen müssen, aber warum sollte der Sender (oder überhaupt irgendjemand) die gleichen Daten mehrfach über die selbe Leitung verschicken? Warum sollte nicht einfach das Netz (d.h. die Router) die Pakete für jeden Zuhörer duplizieren? Am besten sollten die Pakete zum letzten möglichen Zeitpunkt vervielfältigt werden. Anders ausgedrückt: Kein Datenpaket soll mehr als einmal über eine Leitung gehen. Außerdem soll natürlich kein Datenpaket unnütz über eine Leitung gehen, d.h. wenn es dahinter niemand empfangen möchte. Diese Idee hat Steve Deering in den 80er Jahren in einer wissenschaftlichen Arbeit geäußert und sich Gedanken über eine mögliche Implementierung gemacht. Letztendlich handelt es sich aber eher um ein Konzept als um ein Protokoll, d.h. man kann es in einem Netzwerk in mehreren Schichten implementieren. Und tatsächlich wurden schon vor Deering im Usenet Daten so verteilt, so daß obige Forderungen erfüllt werden. Deerings Ansatz war nun aber, Multicast auf IP-Ebene umzusetzen, d.h. in der Abstraktionshierarchie sehr weit unten. Die Idee klang sehr vielversprechend, und so ist Steve Deering auch inzwischen bei Cisco (dem weltgrößten Router-Hersteller) unter Vertrag und arbeitet an Internet-Standards bezüglich Multicast und IPv6. Un tatsächlich: obwohl Multicast hauptsächlich mit Multimedia assoziiert wird, ergeben sich noch ganz andere Möglichkeiten. Für Newsticker, Mailinglisten und andere Push-Dienste wäre Multicast geradezu ideal. Man kann mit Multicast auch replizierte Datenbestände abgleichen (verteile Datenbanken, Cache-Abgleich, über die Erde verteilte Webserver wie bei Akamai oder Digital Island). Multicast ist aber auch als Transportmechanismus für VPNs geradezu prädestiniert, wo man sich im Moment mit kruden Punkt-zu-Punkt-Tunneln behilft. [Zwischentitel: Ethernet] Bevor man sich aber dem Multicast auf IP-Ebene widmet, muß man allerdings klären, ob die Schicht darunter das Konzept überhaupt umsetzen kann. Offensichtlich ist Multicast über Punkt-zu-Punkt- Verbindungen kein Problem, aber wie sieht es mit Bussen aus? Die häufigste Anbindung für Clients und Server ist Ethernet. Ethernet ist ein Bus, d.h. rein konzeptionell eine große Datenleitung, an der alle Teilnehmer hängen. Jeder kann zu jedem Zeitpunkt Daten auf die Leitung schreiben, die dann alle anderen Teilnehmer sehen. Wenn zwei Teilnehmer gleichzeitig Daten schreiben, dann spricht man von einer Kollision. Beide Sender können das erkennen und probieren es einfach nach einer zufällig gewählten Wartezeit nochmal. In allen Paketen stehen die Adressen des Absenders und des Adressaten in einem Header drin, damit Teilnehmer sehen können, welche Pakete für sie bestimmt sind und welche nicht. Es sehen also prinzipbedingt alle Teilnehmer alle Datenpakete auf dem Bus. Gigabit-Ethernet ist heute aber schneller als der System-Bus, d.h. es ist für einen Teilnehmer gar nicht möglich, die Daten auch nur komplett entgegenzunehmen, geschweige denn die Pakete zu filtern. Daher filtern Ethernet-Karten in Hardware, d.h. sie melden überhaupt nur die Pakete an den Rechner weiter, die an dessen Ethernet- (oder MAC-)Adresse adressiert sind. MAC steht für Media Access Control und ist dem OSI-Schichtenmodell entnommen (und ist damit nicht auf Ethernet beschränkt). Im Ethernet sind MAC-Adressen 48 Bits groß. Es gibt eine spezielle MAC-Adresse (die nur aus 1-Bits besteht), die immer alle Teilnehmer adressiert ("Broadcast"). Man kann bei Ethernet-Karten in Software sowohl die MAC-Adresse ändern als auch den Filter komplett abschalten. Ersteres braucht man, damit man die Zuverlässigkeit eines Systemes erhöhen kann, indem man einen identischen Backup-Rechner daneben stellt, der im Fall eines Ausfalls komplett einspringen kann - dazu gehört auch, daß er die gleiche MAC-Adresse benutzt. Letzteres braucht man für Netzwerk-Statistik, Tools zum Erkennen von Einbrüchen und sonstige Diagnosezwecke. Wenn man seinen Rechner jetzt frisch in ein Ethernet stöpselt und mit einem anderen Rechner sprechen möchte, kennt man aber nur dessen IP-Adresse, nicht dessen MAC-Adresse. Daher ist über Ethernet das Address Resolution Protkoll (ARP) definiert. Das Protokoll funktioniert so, daß man ein Paket an die Broadcast-Adresse schickt, in dem man nach der MAC-Adresse zu einer IP-Adresse fragt. Der Teilnehmer, der die gewünschte IP-Adresse hat, schickt dann ein Antwort-Paket mit seiner MAC-Adresse. Wie kann man nun mit diesen Mitteln Multicast abbilden? Im Header ist nur Platz für eine Empfänger-Adresse! Mehrere Lösungen wären denkbar: man könnte z.B. Multicast-Traffic immer an die Broadcast-Adresse schicken, man könnte verlangen, daß Empfänger grundsätzlich den Hardware-Filter abschalten oder man könnte spezielle MAC-Adressen für Multicast-Pakete vergeben. Bei näherer Betrachtung sind beides keine guten Lösungen. Wenn Multicast-Traffic immer an alle ginge, würde unbeteiligten Fileservern an dem gleichen Gigabit-Ethernet-Strang Performance entzogen, weil der Systembus mit Multicast-Paketen geflutet würde. Das gleiche gilt natürlich auch für die Empfänger, die die Multicast-Übertragungen auseinandersortieren müßten. Wenn man aber eine spezielle MAC-Adresse für Multicast vergibt, dann müßten die Filter in den Netzwerk-Karten auch nach dieser filtern können. Und angenommen, sie könnten das, dann würden sie trotzdem wieder nur alle Transmissionen oder keine empfangen. Um dieses Problem auch zu beheben, müßte man eben eine größere Menge an MAC-Adressen für Transmissionen reservieren. Was macht man dann aber, wenn ein Teilnehmer mehr als einen Datenstrom empfangen möchte? Netzwerk-Karten müssen dann eben nach mehr als einer Adresse filtern können. Als kurze Zwischenüberlegung sei gesagt, daß natürlich die gleichen Fragen auf IP-Ebene auch zu beantworten sind. Als zusätzlicher Sachzwang kommt aber hinzu, daß Router für ihre Entscheidungen IP-Adressen heranziehen, d.h. wenn verschiedene Transmissionen unterschiedlich geroutet werden sollen, dann müssen sie auch verschiedene IP-Nummern haben. Auf IP-Ebene hat man daher den Bereich 224.0.0.0/4 für Multicast reserviert - das sind über eine viertel Milliarde IP-Nummern. Es stellt sich also die Frage, wo die MAC-Adresse zu einer Multicast-IP herkommt. Per ARP läßt sie sich jedenfalls nicht herausfinden, weil der MAC-Adresse ja kein Rechner zugeordnet ist. Es bleibt also nur eine algorithmische Zuordnung, d.h. man definiert eine Funktion, die zu einer gegebenen IP-Nummer die MAC-Adresse berechnen kann. Die Standardisierungs-Gremien haben sich dafür entschieden, auch aus dem Pool der Ethernet-Adressen einen großen Teilbereich für Multicast zu reservieren, und zwar die mit dem Prefix 01 00 5e. Schnelle Rechner merken an dieser Stelle, daß im Ethernet nur 24 statt 28 Bits für die Adresse übrig bleiben, d.h. man hat nicht für jede IP-Adresse eine eigene Ethernet-Adresse. Das Ergebnis sind Kollisionen, d.h. Ethernet-Adressen, auf die mehr als eine IP-Adresse abgebildet wird, d.h. wenn die Hardware perfekt nach Ethernet-Adressen filtert, können immer noch ungewünschte Pakete durchkommen und das Betriebssystem muß nachfiltern. Unter diesen Voraussetzungen lohnt sich natürlich in den Netzwerkkarten der Aufwand für einen perfekten Filter nicht. In Ethernet-Filterchips ist daher normalerweise entweder eine Liste von gewollten Multicast-Adressen (Größenordnung 32) oder eine Hash-Tabelle (Größenordnung 512) eingebaut. Wenn man eine MAC-Adresse haben möchte, berechnet man eine Hash-Funktion darüber, setzt das resultierende Bit in der Tabelle auf 1 und kriegt daraufhin alle Pakete, deren MAC-Adresse ebenfalls auf diesen Wert hashen. Gute Chipsätze wie die tulip-Chipsätze von Digital haben beides im Angebot, so daß man die Hash-Methode erst benutzen muß, wenn die Liste voll ist. Was soll aber ein Multicast-Router im Ethernet tun? Router verhalten sich im Ethernet normalerweise genau wie alle anderen Teilnehmer. Wenn ein Paket an einen Rechner außerhalb des Netzes gehen soll, trägt man dessen IP-Adresse in den IP-Header aber die MAC-Adresse des Routers in den Ethernet-Header ein. Bei Multicast sieht das aber anders aus, denn der Router muß alle Multicast-Pakete im Ethernet empfangen können! Eine Liste von gewünschten MAC-Adressen hilft an der Stelle nicht weiter! Die Hash-Tabelle hilft aber weiter, wenn nur Pakete mit dem Multicast-Prefix über die Tabelle gefiltert werden, denn dann kann man einfach alle Bits setzen. Damit sind die Multicast-Probleme im Ethernet aber immer noch nicht alle gelöst. Was ist mit Switches? Switches betrachten die Absender-Adressen aller einkommenden Ethernet-Pakete und führen bei allen Ports darüber Buch, welche MAC-Adressen hinter diesem Port sitzen. Dann werden Pakete nur noch an Ports weitergeleitet, in deren MAC-Liste die Ziel-MAC-Adresse steht. Bei Multicast-Paketen ist die MAC-Adresse aber berechnet und es sendet sicher hinter keinem Port jemand mit einer Multicast-MAC-Adresse! Bridges und Switches aus der Bronzezeit (vor 1988) werden daher Multicast-Traffic an keinen Port weiterleiten. Die nächste Generation dieser Geräte schaltet Multicast komplett frei, d.h. die Pakete werden an alle Ports rausgeleitet. Damit ist Multicast zwar wieder möglich, aber der Switch kommt seiner Funktion nicht wirklich nach. Moderne Switches (etwa seit 1995) beherrschen IGMP Snooping. IGMP ist das Protokoll, mit dem Hosts dem Router mitteilen, daß sie einer Multicast-Gruppe beitreten möchten (siehe Kasten). Der Switch führt so also pro Port auch noch darüber Buch, welche Multicast-Gruppen an den Strang weitergeleitet werden sollen. So kann der Switch theoretisch perfekt filtern, d.h. auch Multicast-IPs wegfiltern, die auf eine abonnierte MAC-Adresse abgebildet werden. Nach diesen Überlegungen ist klar, daß selbst im eigentlich einfachen Medium Ethernet die Realisierung des Multicast-Konzepts durchaus anspruchsvoll ist. Tatsächlich haben alle Beteiligten die Komplexität des Themas zum Teil deutlich unterschätzt. In gerouteten IP-Netzen stellt sich die Situation leider noch deutlich komplizierter dar. Man muß im Moment leider konstatieren, daß Multicast in großen geswitchten Ethernets deutlich besser funktioniert als in gerouteten Netzen. [Multicast über IP] In einem IP-Netz stellen sich natürlich die gleichen Fragen wie im Ethernet. Wie bereits erwähnt ist ein sechzehntel des IPv4-Adressraumes für Multicast reserviert worden. Dieser Bereich ist aber weiter aufgeteilt worden. 224.0.0.0/24 ist reserviert für lokalen Multicast-Verkehr (d.h. dieser Bereich wird nicht geroutet). Die IP 224.0.0.1 ist die all-hosts Gruppe, 224.0.0.2 ist die all-routers Gruppe. Der Vorteil liegt auf der Hand - man kann mit einem einfachen Ping an eine Multicast-Gruppe die lokalen Router finden! Die Spezifikation geht noch weiter: für verschiedene Routing-Protokolle werden auch lokale Gruppen reserviert. Über diese elegante Methode kann man noch weitgehender Resource Discovery betreiben, wie IPv6 sehr schön demonstriert. Warum sollte man nicht auch z.B. die Nameserver so finden können (ohne irgendwo einen DHCP-Server installieren zu müssen)? Es ist für das Verständnis wichtig zu sehen, daß man auch auf einem Betriebssystem ohne Multicast-Support eine Transmission vornehmen kann. Nur das Empfangen ist kompliziert. Diese Umkehrung der Komplexität im Vergleich zu traditionellen Client-Server Erfahrungswerten tritt übrigens noch deutlicher bei Multimedia-Transmissionen zutage, wo die ganze Last der Reassemblierung und Fehlerkorrektur beim Client liegt, der Sender muß einfach nur seine Pakete abschicken. Für das tiefere Verständnis von IP-Multicast muß man die Sache aus Sicht des Anwender betrachten. Der Anwender möchte im Grunde eine Benutzeroberfläche wie beim Fernseher haben. Er möchte auswählen, welchen Kanal er gezeigt kriegt, er möchte nicht den Sendemast auswählen. Genau so ist das beim Multicast auch. Der Client sagt, an welcher Multicast-Gruppe er Interesse hat, ohne den Sender zu kennen. Überhaupt kommt die Nomenklatur "Multicast-Gruppe" daher, daß es auch mehr als einen Sender geben kann. Eine angedachte Anwendung für Multicast wäre z.B. eine verteilte Wettersimulation, bei der jeder Teilnehmer seine errechneten Daten allen anderen Beteiligten mitteilt. Es ist daher auf Protokollebene schon so, daß der Client keinen Sender angibt, sondern nur die IP der Multicast-Gruppe. Der Router muß dann sehen, wo er die Daten aquirieren kann. Warum macht man das nicht so, daß der User über irgendeinen Verzeichnisdienst den Sender herausfindet? Dazu muß man sich folgendes wichtige Ziel von Multicast vor Augen halten: die Gleichstellung der User. Multicast soll auch den kleinen Dialup-User mit einer einfachen ISDN-Leitung in die Lage versetzen, Radio für das gesamte Internet auszustrahlen. Daraus folgen mehrere wichtige Fakten: Die ISDN-Leitung ist schon mit dem Radio ausgelastet. Wenn sich plötzlich spontan 1000 Leute entscheiden, daß sie mithören wollen, und sie sagen das dem Sender, dann bricht für alle das Radio zusammen. Das geht also nicht. Daraus wiederum folgt, daß der Sender gar nicht weiß, wer zuhört! Der Sender weiß nicht einmal, wieviele Zuhörer es gibt, oder ob überhaupt jemand zuhört! Desweiteren würde das Radio auch zusammenbrechen, wenn der Sender Fehlermeldungen zugestellt bekäme. Nehmen wir an, ein Client tritt einer Multicast-Gruppe bei und das Radio-Abspielprogramm stürzt ab. Auf IP-Ebene würde es dann normalerweise ICMP-Fehlermeldungen geben, die sagen würden, daß die Daten nicht angekommen sind. Bei Multicast geht das nicht. Auch andere Rückmeldungen sind nicht möglich. Das Internet ist zwar paketbasiert, aber mit TCP wird der Benutzer in die Lage versetzt, Verbindungen aufzubauen. Natürlich gibt es da nicht wirklich Verbindungen im Internet, aber es reicht ja auch, wenn beide Seiten darüber geeinigt haben, daß sie ab jetzt eine Verbindung aufgebaut haben. Dieser Verbindungsdienst bieten nun Annehmlichkeiten, die auch bei Multicast sehr wünschenswert wären, wie an erster Stelle die Fehlerkorrektur. Wenn ein Paket nicht oder korrupt ankam, dann wird es noch einmal übertragen. Im Internet können Pakete auch doppelt oder in der falschen Reihenfolge ankommen. Auch diese Probleme kompensiert TCP. TCP basiert aber auf einer Einigung, d.h. auf Rückmeldungen. Bei Multicast gibt es ja keine Rückmeldungen. Also gibt es bei Multicast auch kein TCP und damit keine Verbindungen. Multicast ist rein unidirektional. Es bleibt also die reine Ausstrahlung, und zwar inklusive Übertragungsfehler. Eine für das Netz sehr wichtige Eigenschaft von TCP ist auch die Verstopfungskontrolle. Wenn TCP Paketverlust feststellt, wird die Senderate gedrosselt. Paketverlust tritt auf, weil eine Leitung auf dem Weg voll ist. Wenn TCP dann also weniger Daten schickt, wird die Situation so automatisch entkrampft. Bei TCP ist es auch so, daß man Daten nicht schneller schicken kann als der Empfänger sie liest. Bie Multicast weiß man nicht nur nicht, wie gut der Empfänger angebunden ist, man hat außerdem auch noch mehr als einen Empfänger, diese sind verschieden gut angebunden und bei ihnen gehen wahrscheinlich auch noch jeweils andere Pakete verloren. Unter anderem ergibt sich daraus für den Sender die zusätzliche Komplexität, daß er ein Video nicht schneller abschicken darf, als ein Empfänger es abspielen kann. Das heißt, daß der Sender Basis-Wissen über die Abspielgeschwindigkeit des zu übertragenden Inhalts haben muß. Bei simplem Streaming über TCP ist das nicht so. [Zwischentitel: Routing] Die wahre Komplexität bei Multicast ist aber das Routing. Das API ist sehr einfach: der Sender sendet einfach mit der Multicast-IP, der Client sagt dann, daß er diese Multicast-IP auch empfangen möchte. Nur: wem sagt er es? Grundsätzlich sind zwei Modelle denkbar: der Client könnte es dem Sender oder seinem lokalen Router sagen. Wenn der Client sich beim Sender anmeldet, hätte das den Vorteil, daß der Sender weiß, wer ihm zuhört. Außerdem wäre auch eine einfache Zugangskontrolle möglich. Das wäre der Wunsch aller Werbetreibenden, aber dem stehen relativ große Nachteile gegenüber: Zuerst einmal muß der Sender eindeutig und bekannt sein! Der Empfänger sollte den Sender nicht kennen müssen. Das Äquivalent beim Fernseher wäre, daß man nicht den Sender, sondern den Sendemast auswählt. Für diesen Fall könnte man mit viel Getrickse noch eine Art DNS aufbauen, wie man das auch für normale IPs macht, das wäre also technisch noch lösbar. Schwerwiegender ist die Einschränkung, daß der Sender eindeutig sein muß. Mit Multicast möchte man ja auch Anwendungen wie "shared whiteboard" umsetzen (d.h. zehn Leute schreiben und malen auf der gleichen virtuellen Tafel herum), wobei mehr als einer sendet, sogar zur gleichen Zeit. Ein weiterer Nachteil ist, daß der Sender ein Skalierungsproblem hat. Wenn pro Minute mehrere tausend Zapper hin- und wieder wegzappen, dann verbraucht der Sender am Ende seine ganze Bandbreite und Rechenzeit mit Verwaltungskram. Um zu sehen, warum das ein Problem ist, muß man sich den Privat-User mit Dialup-Modem vor Augen halten, der per Multicast Radio ausstrahlen können soll. Wenn von der ohnehin knappen Bandbreite noch Teile für Verwaltung weg gehen, dann kippt das ganze Projekt. Und nicht zu vergessen wäre die Anmeldung beim Sender nur sinnvoll, wenn der Sender in seinen Paketen alle Empfänger listet, und dann wäre ab hundert Empfängern kein Platz mehr für Nutzlast (die Paketgröße im Ethernet ist auf 1500 Zeichen beschränkt). Offensichtlich ist das im allgemeinen keine Lösung, obwohl es für wenige kleine Multicast-Gruppen durchaus sinnvoll sein kann, weshalb es auch Arbeit in dieser Richtung gibt. Bei IPv6 z.B. ist ein Option-Header definiert, mit dem man zusätzliche Empfänger listen kann. Es bleibt nur die andere Lösung, nämlich daß sich der Client beim lokalen Router anmeldet. So können wir auch mehr als einen Sender haben und jeder Dialup-User kann Radio ausstrahlen. Andererseits weiß der Sender nicht, wer zuhört. Er weiß nicht einmal, wie viele Leute seine Sendung abonniert haben! Auch die Zugangsbeschränkung ist so nicht in der Hand des Sender, d.h. man muß sie per Verschlüsselung erreichen. Woher weiß nun aber der Router des Senders, wo er die Daten hinschicken soll? Doch vor der Klärung dieser Frage steht bei Informatikern erstmal die Überlegung, wie gut man denn das Problem erwartungsgemäß wird lösen können. Wenn man über Skalierbarkeit beim Routing nachdenkt, fällt erstmal direkt auf, daß Multicast-IPs nicht aggregierbar sind. Beim normalen Routing benutzt man die Netzmaske, um benachbarte IPs zusammenzufassen und gemeinsam zu betrachten. Beim Multicast-Routing haben benachbarte IP-Adressen keinerlei Korrelation. Wenn man bedenkt, daß ein Kern-Router im Internet auch nur für die Hälfte der möglichen Gruppen Daten speichern muß, dann wären das schon über 100 Millionen IPs. Im Moment ist die Größenordnung der Routingtabellen auf zentralen Routern im Internet deutlich unter 100.000, d.h. hier liegt ein Größenunterschied von mehr als 1000 vor! Und schon durch die Routing-Tabellen wird im Moment auf den Routern der Speicher knapp. Außerdem muß man bedenken, daß für aktive Multicast-Gruppen mindestens für alle Interfaces gespeichert werden muß, ob dahinter Interessenten sitzen, und für alle anderen Gruppen muß der Router wissen, wo sie zu beziehen ist (auch wenn man das ohne Speicherbedarf im Router machen kann). Und die meisten Routing-Protokolle speichern noch deutlich mehr Daten! Im Internet gibt es eine auf Tunneln basierende Multicast Test-Infrastruktur namens MBone. Im MBone waren zu Hochzeiten nicht über 10.000 Gruppen aktiv. Man sieht also schon an dieser Stelle, daß das Problem offenbar ein schwieriges ist. Bei den Ingenieuren, die die Internet-Protokolle entworfen haben, ist in solchen Fällen die Herangehensweise, daß man erstmal den einfachen Fall löst. Und beim Multicast-Routing ist der einfache Fall, daß man an einem Campus-Netz arbeitet, wo die Leitungen alles vorbezahlte Standleitungen sind, d.h. man muß nicht so auf den Traffic achten. Diesen Fall kann man tatsächlich relativ einfach lösen. Wenn Daten auf einer Multicast-Gruppe hereinkommen, die bisher nicht benutzt war, dann schickt man die Daten einfach auf allen anderen Interfaces heraus. In einem LAN ohne weitere Router weiß der Router ja, welche Gruppen abonniert wurden, weil die Hosts das ja per IGMP mitgeteilt haben. In diesem Fall kann der Router also ungewünschte Multicast-Gruppen explizit abbestellen. Dieses grobe Vorgehen nennt man "flood and prune". Es gibt da noch ein paar Feinheiten, wie z.B. daß Router Multicastgruppen nach einer Weile ohne Traffic als unbenutzt markieren, und daß Router nur Daten annehmen, wenn sie auf dem Interface hereinkommen, über das auch die Unicast-Route zu dem Sender (der ja im Paket steht) geht. Damit macht man Im-Kreis-Routen unwahrscheinlicher. Dieser Ansatz klingt brutal ineffizient, aber er hat mehrere Jahre über nicht nur funktioniert, sondern war auch das Routing-Protokoll, mit dem der MBone betrieben wurde. Das Ergebnis war leider, daß die reine Teilnahme am MBone (ohne Daten zu senden oder irgendwo zu subscriben) Gerüchten zufolge ca. 7 mbps Bandbreite belegt, so daß sich das im Internet-Hochpreisland Deutschland nur wirklich große Provider und Unis leisten können. Tatsächlich ist es sehr schwierig, einen Provider zu finden, der Multicast-Routing und MBone-Zugang anbietet. Wie auch beim Unicast-Routing macht man sich bei Multicast-Routing natürlich auch die hierarchische Struktur des Internets in Form der autonomen Systeme zunutze. Grundsätzlich haben fast alle Hosts im Internet eine Default-Route. Wenn sie von einem Paket nicht wissen, wie es geroutet werden soll, dann geben sie es ihrer Default-Route folgend bei dem Default-Gateway ab. Das funktioniert allerdings nur innerhalb eines autonomen Systemes. ISPs mit mehr als einer Leitung nach draußen sind normalerweise autonome Systeme. Indem man der Default-Route folgt, gelangt man am Ende zu einem Router an der Grenze zwischen zwei autonomen Systemen, und der hat dann keine Default-Route mehr. Stattdessen kennt der alle anderen autonomen Systeme und kennt zu jedem eine Route. Über diesen Default-Mechanismus hat man in allen internen Routern Arbeit und Platz gespart. Bei Multicast Routing kann man dieses Prinzip genauso anwenden. Der kleine Router unter dem Tisch muß nicht wirklich wissen, welche Konferenz er wo beantragen muß. Er muß nur wissen, wo er bei Bedarf nachzufragen hat. Diese Gedanken ausnutzend unterscheidet man zwischen "Dense Mode" und "Sparse Mode". Dense heißt übersetzt "dicht", während sparse für "spärlich" steht. Gemeint ist nicht die Anzahl von Clients pro Router, sondern die Anzahl von datentragenden Leitungen pro Router, d.h. ob sich "flood and prune" negativ auswirkt oder nicht. Man spricht in Anlehnung an die berüchtigten Netzdiagramme, bei denen das Internet immer als große Wolke dargestellt wird, von "Dense Mode Clouds", die man mit einem Sparse Mode Protokoll vernetzt. Das bekannteste Dense Mode Verfahren ist DVMRP, das Distance Vector Multicast Routing Protocol, aber es gibt in dieser Kategorie auch noch MOSPF (Multcast Open Shortest Path First) und PIM Dense Mode (Protocol Independent Multicast). [Zwischentitel: DVMRP] DVMRP war das erste Multicast-Routingprotokoll und es ist immer noch sehr verbreitet. Die Referenzimplementation ist der freie mrouted, auf dem jahrelang der MBone aufbaute, in dem es auch heute noch eine tragende Rolle spielt. Es basiert größtenteils auf Reverse Path Forwarding, welches auch Basis der anderen Multicast Routing-Protokolle ist, mit ein paar Tricks. Reverse Path Forwarding heißt: 1. Akzeptiere Multicast-Pakete nur auf dem Interface, auf dem die Unicast-Router zum Sender liegt. 2. Wenn für die Multicast-Gruppe keine Liste existiert, trage alle benachbarten Router in die Liste ein. 3. Leite das Paket an alle Router in der Liste weiter. 4. Lösche periodisch die Listen für alle Multicast-Gruppen. 5. Wenn eine Liste leer ist, sende "prune" Nachricht für diese Multicast-Gruppe an den Router, von dem die Multicast-Pakete kommen. Wohlgemerkt: es gibt einen Unterschied zwischen "die Liste ist leer" und "die Liste existiert nicht". Es werden nicht nur die Listen der Multicast-Gruppen gelöscht, die keinen Traffic hatten, sondern die Listen aller Multicast-Gruppen. Wenn ein Host bei einer Gruppe subscriben will, muß der lokale Router nur warten, bis für diese Gruppe das periodische Fluten stattfindet. Das Flutet findet nur für Gruppen mit Traffic statt, das Verfahren ist also nicht ganz so ineffizient, wie es auf den ersten Blick aussieht. Eine DVMRP-Verfeinerung ist, daß der Router pro Interface speichert, ob er dahinter als Upstream erkannt wird. Hierzu muß DVMRP sich auch über Unicast-Routen austauschen, wofür ein eigenes Verfahren benutzt wird, welches auf Distanz-Vektoren aufbaut. Das ist eine potentielle Verdoppelung des Overheads, der durch Unicast-Routing entsteht. Distanz-Vektoren sind Meldungen der Art: "ich kenne eine Route zu X mit der Metrik Y", wobei man unter Metrik ein Maß für die Güte einer Route ist. Normalerweise benutzt man die Anzahl der Hops als Metrik, d.h. die Anzahl der Router zwischen hier und dem Ziel. Es gibt noch ein paar Details zu beachten, u.a. damit schlechte Routen nicht propagiert werden. Das verbreitetste Distanz-Vektor-Verfahren beim Unicast-Routing heißt RIP. [Zwischentitel: MOSPF] Ein Konkurrent zu RIP ist OSPF, wobei Router nicht nur die eigenen Routen mitteilen und auch nicht nur an ihre Nachbarn, sondern auch an weiter entfernte Router. Jeder Router baut dabei eine Datenstruktur aus, in der alle Router und alle Routen gespeichert sind und sucht sich dann die optimale Route über Dijstra's Algorithmus aus, einem Standard-Algorithmus aus der Graphentheorie. MOSPF benutzt nun OSPF als Unicast-Routingprotokoll, kein Distanz-Vektor-Protokoll wie DVMRP. Da alle Router und Routen pro Multicast-Gruppe in jedem Router gespeichert und zwischen Routern ausgetauscht werden, belegt MOSPF für die gleichen Daten viel mehr Netzbandbreite und RAM im Router als DVMRP und außerdem verbraucht Dijstra's Algorithmus viel Rechenzeit. MOSPF ist heute praktisch tot. [Zwischentitel: PIM-Dense Mode] DVMRP und MOSPF haben den Nachteil, daß sie auf einem bestimmten Unicast-Routingprotokoll abhängen. Die Internet Engineering Task Force hat sich daher daran gemacht, ein Multicast Routingprotokoll zu definieren, das unabhängig vom Unicast-Routingprotokoll ist. Dieses Protokoll heißt PIM (für Protocol Independent Multicast) und liegt in den Varianten Dense Mode und Sparse Mode vor. PIM-DM entspricht DVMRP ohne die Upstream-Ersparnis, erzeugt also etwas mehr überflüssigen Traffic. Es löst DVMRP trotzdem ab, da Cisco in seinen Routern nur PIM unterstützt, und Cisco stellt 90% der IP-Router in der Welt. [Zwischentitel: Sparse Mode Routing] Sparse Mode geht davon aus, daß Bandbreite knapp und teuer ist und nur wenige vereinzelte Empfänger pro Multicast-Gruppe existieren, d.h. Fluten kommt nicht in Frage. Es gibt zwei Protokolle, Core Based Trees und PIM Sparse Mode. [Zwischentitel: Core Based Trees] CBT geht von einem zentralen `Core'-Router aus, über den der gesamte Traffic fliesst. Der lokale Router meldet sich einfach bei diesem bekannten Core-Router an. Die Anfrage kommt auf dem Weg zum Core Router bei allen Routern vorbei, die auch dafür zuständig wären, den Multicast-Traffic weiterzuleiten, und der erste Router auf dem Weg, der die gewünschte Multicast-Gruppe bereits führt, leitet die Nachricht nicht mehr an den Core-Router weiter und leitet die Gruppe über das Interface weiter, auf dem die Nachricht kam. CBT hat die schöne Eigenschaft, daß niemand den kompletten Verteilungsbaum kennen muß, so daß an keiner Stelle Speicherplatz in einem Router verschwendet wird (außer natürlich im Core Router, der alle Multicast-Gruppen kennen muß). Auf der anderen Seite muß jede Multicast-Gruppe durch den Core-Router geroutet werden, d.h. dort gibt es Bandbreiten-Engpässe. Es gibt daher auch CBT-Varianten, die mehr als einen Core-Router erlauben. Es stellt sich aber die Frage, wer den Core-Router bezahlen soll, und wer für die Wartung und Upgrades zuständig sein soll. [Zwischentitel: PIM Sparse Mode] PIM-SM spricht von Rendezvous Points statt von core Routern, die Funktion ist aber ähnlich. PIM-SM baut anfänglich einen gemeinsamen Baum auf, wie bei CBT. Wenn ein Empfänger aber feststellt, daß viel Traffic von einem einzelnen Sender kommt, kann er über eine spezielle JOIN-Nachricht dafür sorgen, daß der Traffic direkt statt über den Rendezvous Point geroutet wird. Das entlastet den Rendezvous Point nicht, da dieser den Traffic auch führen muß, aber es kann zu einer kürzeren Route führen, wenn der Rendezvous Point netztopologisch weit entfernt ist. Die Entfernung wird auch bei PIM in Hops gemessen. Das ist problematisch, wenn Multicast über Tunnel implementiert wird, wie es im MBone momentan der Fall ist, weil dann potentiell schlechtere Routen gewählt werden. Weil sich auch bei PIM-SM die Frage stellt, wer für die Rendezvous Points zuständig ist, etabliert sich im Moment ein Aufbau, bei dem jeder ISP einen RP unterhält. Verschiedene PIM-Clouds sollen sich über das Protokoll MSDP abgleichen. Hauptgrund für diese Konstellation ist, daß ISP A keine Motivation hat, die Konfiguration ihres RPs zu reparieren, wenn nicht die eigenen Kunden sondern nur die von ISP B betroffen sind. Außerdem möchte ISP A nicht kostenlos Multicast-Traffic durch sein Netz leiten, wenn kein eigener Kunde zuhört. Die Frage, wie man Multicast-Traffic überhaupt abrechnen soll ist auch noch eher ungeklärt. Doch dazu später mehr. Aufmerksame Leser werden bemerkt haben, daß im Sparse Mode das Routing zustande kommt, sobald ein Empfänger einer Gruppe beitritt, während im Dense Mode das Routing zustande kommen, sobald der Sender das erste Mal Daten verschickt. Wenn man also auf dem Backbone Sparse Mode Routing benutzt, im LAN aber Dense Mode, dann kann nie ein Routing zustandekommen, weil die DVMRP-Router darauf warten, daß das erste Mal Traffic vorbeikommt. PIM ist ja explizit für diese Konstellation erfunden worden, aber bei DVMRP ist das ein echtes Problem. Im Moment werden Lösungen angedacht, bei denen der Router zwischen der DVMRP- und der PIM-SM-Cloud periodisch für alle Multicast-Gruppen ein Ping-Paket verschickt, aber so richtig effizient ist das natürlich nicht. Man sieht schon, bei Multicast liegt der Teufel in den Details. So ist im Moment auch noch ungeklärt, woher man denn die IP für die Multicast-Gruppe nehmen soll, wenn man jetzt eine Ausstrahlung durchführen möchte. Angedacht ist MADCAP, ein Protokoll, mit dem man sich bei Servern eine Multicast-IP zuweisen lassen kann, aber in der Praxis greifen sich die Leute halt eine zufällige IP und hoffen, daß nichts passiert. Durch die schiere Anzahl von möglichen Multicast-IPs gibt es da auch gewöhnlich keine Kollisionen, aber schon ab ein paar tausend parallelen Gruppen wächst die Wahrscheinlichkeit über 50% (analog zum sogenannten Geburtstags-Paradox: Wieviele Leute müssen in einem Raum sein, damit mit >50% Wahrscheinlichkeit zwei davon am gleichen Tag Geburgstag haben? Nur 23, denn bei 23 Leuten gibt es schon 253 verschiedene Paare). Das Problem sehen die Protokollexperten auch, aber zentrale Server sind eigentlich nicht, was man haben möchte. Also wurde das "PIM Express Model" vorgeschlagen, wobei die Sender-Unicast-IP einfach als Teil der Group-Adresse betrachtet wird. Dann müssten Kollisionen nur lokal zum jeweiligen Host vermieden werden, und PIM baut ja eh einen Verteilungsbaum pro Sender auf, das sieht also sehr gut aus. Leider hat sich aber gezeigt, daß die Shared Trees, die ja eigentlich zur besseren Skalierung vorgeschlagen wurden, auch nicht gut skalieren. Ein anderes Problem bei Multicast ist das Billing, d.h. die Traffic-Abrechnung. Normalerweise zahlt der Kunde den Traffic, den er selbst verursacht hat, aber Multicast sorgt ja gerade dafür, daß Daten nur einmal versendet werden, egal wie viele (>1) Empfänger hinter der Leitung sitzen. Es liegt daher nahe, daß sich die Empfänger die Kosten teilen. Daraus folgen einige interessante Sachen, nämlich a) zahlt der Sender nichts und b) sind Special Interest Ausstrahlungen teurer als populärer Kram. Wenn man daraus Schlußfolgerungen über das Internet in zwanzig Jahren ziehen darf, dann wird jeder kleine User ständig irgendwelche Sachen ausstrahlen (es kostet ja nichts, und MPEG-Camcorder sind schon heute erschwinglich für Privatpersonen) und wie heute im Fernsehen werden die meisten Leute das gleiche Einheitsprogramm gucken, weil das billiger ist. Aber egal wie wenig Leute sich ein Programm angucken, Multicast kostet den User niemals mehr als Unicast-Empfang. Wenn man sich die Traffic-Kosten aber mit tausenden oder Millionen teilt, dann könnte man sich in Zukunft auch Breitband-Empfang leisten, selbst wenn die Gigabyte-Kosten gleich bleiben würden. Es sind sogar Modelle denkbar, bei denen der Sender abhängig von der Anzahl der Empfänger sogar bezahlt wird. Bei Video-Streaming im Internet paßt sich der Stream der verfügbaren Bandbreite zum User an. Bei Multicast geht das nicht, daher stellt sich die Frage, wie man Video denn dann ausstrahlen kann. Die offensichtliche Methode wäre, daß man mehrere Ausstrahlungen macht, eine für 64 kbps, eine für 128 kbps, und so weiter. Weil das keine effiziente Bandbreitennutzung ist, haben sich die MPEG-Standardisierer überlegt, wie sie MPEG skalierbarer machen können, und sind dabei auf ein sehr schlaues Modell mit einem Basis-Layer und einem skalierbaren Enhancement-Layer gekommen. Das Basis-Layer muß jeder empfangen, das Enhancement-Layer verbessert die Bildqualität (sogar das Einfügen von Frames gegenüber dem Basis-Layer geht), auch wenn es nur in Fragmenten empfangen wird. An dieser Stelle ist Quality of Service oder Reliable Multicast wichtig, damit sichergestellt ist, daß der Empfänger zumindest das Basis-Layer komplett empfängt. Leute mit kleinerer Leitung empfangen dann automatisch nur soviel vom Enhancement Layer, wie durch ihre Leitung paßt, und haben damit dann ein entsprechend besseres Bild. Solange Quality of Service aber nicht internetweit verfügbar ist, haben sich die MPEG-Experten überlegt, daß man das Basis-Layer auf einer Multicast-Gruppe ausstrahlt und dann für jeweils eine weitere Gruppe für ein weiteres Stück Bandbreite hat, d.h. der Client subscribed so lange bei Gruppen, bis der Packet Loss deutlich steigt. Man sieht schon, daß das das Skalierungsproblem beim Multicast-Routing deutlich verschärft. Für andere Anwendungen als Video ist auch die Zuverlässigkeit wichtig. Eine solche gerne zitierte Anwendung ist ein Trading Floor, wo viele Day Trader die aktuellen Aktienkurse von der Börse über den Bildschirm scrollen haben, und da sollte dann natürlich kein Fehler auftreten. Dieses Problem heißt Reliable Multicast und es gibt im Moment mehrere Ansätze, die orthogonal angewendet werden können. a) Router-Assistiert, b) Fehlerkorrigierende Codes und c) MFTP. Router-Assistenz sieht vor, daß man fehlende Pakete beim Sender nachbestellt, aber Router auf dem Weg Pakete zwischenspeichern, und das Nachbestellungspaket wird dann vom ersten Router auf dem Weg beantwortet, der das gewünschte Paket noch hat. In Routern ist heute schon der Speicher knapp, daher ist diese Möglichkeit nicht sonderlich tragfähig, aber Cisco hat ein solches Protokoll (PGM) lizensiert. Fehlerkorrigierende Codes sehen vor, daß man Paritäts-Pakete mitschickt, d.h. erstmal mehr Traffic verursacht. Wenn aber ein Paket beim Empfänger nicht angekommen ist, kann er es über das Paritätspaket und die anderen Pakete berechnen und muß es daher nicht anfordern. Das ist unter anderem auch daher eine sehr wichtige Methode, weil der Sender bei Nachsende-Anfragen dann nicht alle angeforderten Pakete versenden muß, sondern nur ein weiteres Paritäts-Paket über diese Pakete berechnet, aus dem dann alle Empfänger das jeweils fehlende Paket berechnen können. MFTP heißt einfach, daß man beim Sender das Paket anfordert, wobei man beliebig weit zurückgreifen kann, weil die übertragenen Daten komplett beim Sender zugreifbar sind. Das funktioniert natürlich nur bei Dateiübertragungen, nicht bei Livesendungen, und es skaliert auch schlecht. Desweiteren stellt sich die Frage, ob man lieber ACKs oder lieber NAKs benutzen soll, d.h. ob der Empfänger empfangene Pakete bestätigt oder nicht empfangene Pakete anfordern soll. Im Moment zeichnet sich eine Baumstruktur mit ACKs und eine "Cloud-Struktur" mit NAKs ab, aber das ganze Gebiet ist den Kinderschuhen noch nicht entwachsen. Abschließend stellt sich die Frage, welche Anwendungen denn überhaupt mit Multicast realisierbar sind. Anwendung: Fernsehen über Multicast, d.h. ein Sender mit einer Million Empfängern. Dieser Fall ist prinzipiell gelöst, bis auf die oben genannten Skalierungsprobleme bei den Rendezvous Points. Eine vorgeschlagene Lösung ist "PIM Source Only", wobei man sich nicht beim RP sondern direkt beim Sender anmeldet. Das funktioniert erst ab IGMP 3, wo man erstmals einen Sender überhaupt angeben kann. In diese Richtung scheint sich PIM zu bewegen, weil das der Anwendungsfall ist, für den die meisten Leute ein Geschäftsmodell sehen, d.h. es ist die erhoffte "Killer-Applikation", die Multicast etablieren soll. Anwendung: Multiplayer-Spiele, d.h. 5 Sender, 5 Empfänger. Wenn dieser Fall ein paar Millionen Mal auftritt, brechen die Router zusammen, da sie pro Gruppe pro Sender einen Baum aufzubauen versuchen. Hier gibt es den Ansatz, daß der Sender alle Empfänger im IP-Header auflistet, aber das ist im Grunde zum Scheitern verurteilt, weil Router dann die Pakete inspizieren und jeweils neu zusammenbauen müssen an den ausgehenden Interfaces, und damit zerbricht dann das schnelle Hardware-Routen. Die Router-Hersteller werden das also nicht anbieten wollen. Diese Anwendung wird sich also wahrscheinlich nicht zu Multicast bewegen. Anwendung: Parallele Wetterberechnung, d.h. eine Million Sender pro Gruppe. Diese Anwendung kann man im Moment total vergessen, weil PIM pro Sender pro Gruppe Daten hält, d.h. eine einzige solche Gruppe würde den RAM im Router komplett füllen. Es gibt auch keine Lösungsansätze für diesen Fall. Zusammenfassend scheint das ganze Gebiet in einem katastrophalen Zustand zu sein, aber das ist der Nährboden, auf dem interessante Forschung stattfinden kann und das im Moment auch tut. Wer sich für ein herausforderndes Forschungsgebiet interessiert, ist bei Multicast gut aufgehoben. Kommerzielle Nutzung von Multicast ist in Deutschland im Moment praktisch gar nicht machbar - sie scheitert schon daran, daß man keinen ISP findet, der MBone-Zugang anbietet. [Kasten: IGMP] IGMP steht für Internet Group Management Protokoll, welches dazu dient, daß Router und Clients sich darüber austauschen können, an welchen Multicast-Gruppen Interesse besteht. IGMP ist wie ICMP im Schichtenmodell direkt über IP angesiedelt. Wie die meisten Internet-Protokolle fing es ganz klein und verständlich an und wuchs dann zu beträchtlichen Ausmaßen an. Version 1 (RFC 1112) kannte nur zwei Nachrichtentypen: Host Membership Query und Host Membership Report. Der Router kann mit IGMPv1 periodisch alle Hosts fragen, welche Gruppen sie denn empfangen möchten, und Hosts können als Antwort oder spontan pro Gruppe einen Report abschicken. Der Vollständigkeit halber sei erwähnt, daß in RFC 988 IGMPv0 definiert wurde, das aber noch völlig ohne Erfahrung auf dem Multicast-Gebiet definiert wurde. So beinhaltete das Protokoll noch Versuche der Zugriffsbeschränkung über Access Keys und private Gruppen. Bei Version 1 kann ein Host eine Gruppe nicht verlassen, er kann nur warten, bis der Router das nächste Mal eine Anfrage stellt und dann keinen Report mehr abschicken. Version 2 (RFC 2236) fügt eine Nachricht dazu, mit der man Groups verlassen kann, und spezifiziert eine Methode, wie mehr als ein Multicast-Router in einem Ethernet koexistieren können. Dabei wird der Router mit der kleineren IP-Nummer als Querier ausgewählt, d.h. fortan wird nur noch dieser Host Reports anfordern. Der andere Router übernimmt wieder, wenn der erste eine Anfrage nicht rechtzeitig gestellt hat (und damit ausgefallen zu sein scheint). Version 3 erlaubt die Angabe von ACLs zur Sender-Auswahl. Ein Host kann beim Beitritt zu einer Gruppe erklären, daß er nur Traffic von einem bestimmten Sender empfangen möchte (oder einer Liste von Sendern), oder er kann Sender explizit ausschließen. Die meisten Betriebssysteme implementieren im Moment IGMPv1, viele arbeiten an IGMPv2-Unterstützung.