Aufgabe 1: Wie groß ist das Internet?a)Um die "Größe des Internet" tatsächlich bestimmen zu können muss man sich zunächst über die Begrifflichkeiten klar werden. Hier sind das vor allem die Begriffe Internet und Größe.Allgemein ist das Internet ein Zusammenschluss von verschiedenen autonomen Netzwerken bzw. Systemen (AS), die über Routingmechanismen miteinander kommunizieren können. Da sich als Basisinfrastruktur des Internet die TCP/IP Protokollsuite besonders verbreitet hat und entsprechend den allgemeinen Definitionen davon ausgehen kann, dass alle am Internet beteiligten Rechnerknoten (Hosts) über ein Protokoll der TCP/IP Suite erreichbar sind kann man ruhigen Gewissens das Internet auf diese Rechnerknoten beschränken. Alle übrigen Rechner sind entweder mit Routing-, Kappelungs-, oder anderen Umsetzungsmechanismen oper TCP/IP zu erreichen oder werden allgemein nicht als dem Internet zugehörig angesehen. Nun könnte man als Größe des Internet die beschriebenen autonomen Netze als gemeinsame Einheit heranziehen. Jedes dieser Netze bekommt im Rahmen der Selbstverwaltung des Internet eine eindeutige Nummer von der Internet Assigned Numbers Authority (IANA) oder einer ihrer regionalen Unterorganisationen zugwiesen. Da es sich dabei historisch um eine 16 Bit Ganzzahl handelt (zur Zeit findet gerade die Umstellung auf 32 Bit-Nummer statt), kann es maximal 65536 dieser Netzwerke geben. Davon können aber nur maximal 64511 an öffentliche Netzwerke zugeteilt werden. Die restlichen Nummern sind privaten Netzen vorbehalten. Jede Kommunikation zwischen zwei Hosts im Internet bewegt sich entweder inerhalb des selben AS statt oder über die Hierarchie der Netzwerke, die über AS Nummern bestimmbar sind. Laut http://www.iana.org/assignments/as-numbers/ sind z.Zt. (03. November 2008) 49151 Nummern vergeben. Was uns zu der Schlussfolgerung bringt, dass das Internet aus ebenso vielen Netzwerken besteht. Die Daten der IANA sind sehr zuverlässig und können mit einer hohen Aktualität abgerufen werden. Leider ist die Aussagekraft dieser Zahl sehr unbefriedigend, da sie nichts über die Größe dieser Netzwerke aussagt. Sie können sehr groß sein, aber auch nur aus einigen wenigen Hosts bestehen. Außerdem werden private Netzwerke ausgeblendet. Man könnte aber davon abstrahieren und sie dem öffentlichen AS zuschlagen, über das sie erreichbar sind. Hier ist aber wieder unkalr, wie mit Netzwerken umzugehen ist, die über mehrere andere AS angebunden sind (was der weitaus häufigste Fall sein dürfte). Aufgrund der wenig klaren Größe der Zahl der Autonomen Systeme wird meist versucht, die Größe des Internet mit der Zahl der daran zu einem gegebenen Zeitpunkt angeschlossenen Hosts zu messen. Diese Messung und Aussagen darüber sind aber nur auf den ersten Blick einfach durchzuführen, weil hier keine klar umrissene Definition existiert, wann ein Rechner bzw. ein Stück Hardware Teilnehmer des Internet ist
Man könnte wieder versuchen, auf Registrierungsdienste zurückzugreifen, die u.a. auch die Zuweisung von IP-Adressen registrieren und die Zahl der zugewiesenen IP-Adressen ermitteln. Dies ist aber nur ein sehr ungenaue Angabe, da viele einem Netzwerk zugewiesene IP-Adressen zur Zeit nicht verwendet sind. Außerdem werden hier alle Rechner in privaten Netzwerke mit nichtöffentlichen IP-Bereichen (z.B. aus dem Bereich 192.168.0.0/16) ausgeblendet. Dies könnte man umgehen, indem man versucht die von einem Punkt im Internet aus erreichbaren Rechner zu zählen. Hier müsste man sich entscheiden, auf welcher Protokollebene der OSI-Schicht man zählt und sich für ein entsprechendes Protokoll entscheiden. Da das Internet aber ständiger Veränderung unterworfen ist (verändertes Routing, neue Rechner tauchen auf, alte verschwinden...) müsste man zur exakten Zählung das Internet für die Dauer der Messung "einfrieren", was praktisch aber nicht möglich ist, sodass man hier mit einer gweissen Ungenauigkeit leben muss. Außerdem ist die Messmethode nicht klar. Man könnte es mit ICMP-Pings versuchen. Leider antworten nicht alle Rechner auf diese Anfragen. Außerdem werden auch hier Rechner, die sich hinter Proxies, Routern oder Firewalls sowie in Netzwerken mit privaten IPs befinden ausgeblendet, da die Pings meist schon an diesen Schnittstellen abgefangen werden. Eine mögliche Lösung für die Praxis wäre eine statistische Analyse darüber, wie viele tatsächliche Hosts (abhängig von der Beantwortung der obrigen Fragen) im Durchschnitt für eine antwortende IP-Adresse angenommen werden können. In den IP-Bereichen, die Hoster z.B. für ihre DSL-Kunden reservieren könnte man die durchschnittliche Zahl der sich dahinter befindlichen aktiven Rechner in einem Haushalt bestimmen. Dies ist aber wohl nur mit sehr ungenauen Schätzungen möglich und in der Praxis aufgrund der sehr unterschiedlichen bzw. unklaren Nutzungsszenarien in einzelnen Netzbereichen wohl unmöglich. Vor ähnliche Problemen steht auch der Versuch, die Zählung auf die Provider auszulagern, die ja zu idealerweise zu jedem Zeitpunkt wissen, wieviele Kunden sie aktuell bedienen. Könnte man alle Provider dazu bewegen, diese Zahlen zu ermitteln, zusammenzutragen und auf einen genauen Zeitpunkt zu normalisieren, dann wäre es möglich, ein recht genaues Nutzungsbild zu ermitteln. Auch dies wird aufgrund der stark hierarchischen und verteilten Natur des Internet in der Prxis wohl kaum erschöpfend möglich sein. Eine andere Variante wäre, sich auf einzelne "high-level" Dienste zu beschränken. Man könnte beispielsweise versuchen, die Zahl der Webserver im Internet zu ermitteln und damit die Größe des World-Wide-Web zu bestimmen versuchen. Systembedingt wird damit aber nur ein Teil des Internet "abgegrast". Client-Rechner (z.B. die "normalen" DSL-User) oder Mailserver beispielsweise fallen aus dem Messschema. Da eine Konvention des World-Wide-Web besagt, dass jede Website einem DNS-Eintrag zugeweisen ist könnte man alle Einträge im DNS durchsuchen und schauen, ob bei den zugehörigen Einträgen laufenden Rechnern ein Websererv erreichbar ist. Zur Vereinfachung könnte man sich auf Server beschränken, die auf Port 80 bzw. 443 lauschen (auch wenn damit ggf. ein Teil des (vor allem nichtöffentlichen) WWW ausgeschlossen wird). Hier stellt sich aber wieder das priblem der Rechnerfarmen. Die Webseite von Google ist beispielsweise über wenige IPs erreichbar, dahinter verbergen sich aber tausende von Servern, die die Webanfragen entgegennehmen und verarbeiten. Mit der oben beschriebenen Methode ist es nicht möglich, diese Rechner zu entdecken. Außerdem leidet sie - wie alle Methoden - unter dem Problem der Messdauer: wärend der Messung verändert sich das WWW, die Messung wird inkonsistent. Unabhängig von den technischen Aspekten kann man versuchen, auf die sozialen Aspekte des Internet abzuzielen und die Zahl der Menschen ermitteln, die das Internet nutzen. Dies könnte mittels der eher traditionellen Verfahreb wie Umfragen oder Volkszählungen geschehen. Bei einer hinreichend großen Zahl von Befragten und einer repräsentativen Auswahl aus der Weltbevölkerung könnte man ein recht genaues Bid über die Nutzung des Internet in der Weltbevölkerung gewinnen. Zusätzlich könnte man daraus Rückschlüsse auf die Zahl der tatsächlich verwendeten Netzwerkgeräte ziehen und eine wenn auch stark stistisch geprägte Aufstellung der am Internet beteiligten Geräte erhalten. Insgesamt ist zu sagen, dass aufgrund der dynamischen und relativ chaotischen Struktur des Internet eine genaue Bestimmung seiner Größe wohl nicht möglich ist. Der Autor dieses Textes würde das aber eher als Feature, denn als Bug ansehen :) b)Die technische Lösung der in 1a angesprochenen Möglichkeiten gestaltet sich in aller Regel sehr aufwändig. Das Anpingen aller registrierten IPs oder das Abgrasen von Webseiten erzeugt sehr große Datenmenge. Eine Parallelisierung ist unumgänglich, aufgrund der in 1a vorgschlagenen Tests aber recht gut möglich. Das Problem der sich während der Dauer des Tests ändernden Netzstruktur ist dabei aber ungelöst. Auch fallen Teile des Internet aus dem Schema (private Netzwerke, nicht antwortende Server bzw. Rechner ohne Webserver oder Webserver, die auf nicht-standard-Ports horchen)Man könnte hier versuchen, den Weg eines klassischen Webcrawlers zu gehen und eine Struktur des gesamten WWW aufzubauen. Dies lässt sich aber viel schlechter Paralallisieren (es ist ein gemeinsames Wissen über bereits besuchte Webseiten nötig) und erzeugt unverhältnismäßig viel mehr Datenverkehr. Sofern ein Kooperationswillen bei den Providern vorhanden ist könnte man Messsonden an ihrer zentralen Infrastruktur anbringen um so Statistiken über die über diese Knoten laufenden Daten und damit auch die Kommunikationsteilnehmer zu gewinnen. Im Zuge der in vielen Industriestaten (Europa, USA, Autralien, ...) fortschreitenden staatlichen Überwachung des Internets (bes. des WWW) mittels eben dieser Techniken und damit einhergehendem Zwang zur Kooperation der Provider könnten sich hier quasi als Abfallprodukt die Möglichkeiten zur statistischen Aufbereitung zu Forschungszwecken ergeben. Die angesproichene "soziale" Lösung des Problems durch Befragungen ließe sich durch ein großangelegtes internationales Forschungsprojekt lösen. Bei der statistisch korrekten und signifikaten Auswahl der befragten Personen lässt sie der Prozentsatz der am Internet teilnehmenden Weltbevölkerung recht gut abschätzen. Über zusätzliche Fragen zur verwendeten Netzinfrastruktur und Einbeziehung von möglichst vielen Providern und Carrieren könnte sich daraus auch eine Abschätzung der tatsächlich vorhandenen und zu einem Zeitpunkt genutzten Netzinfrastruktur erstellen. Die Umsetzbarkeit dieses Verfahrens ist wohl vor allem durch die Kapazitäten der Umfrageinstitute und des Mitwirkungswillens der Provider begrenzt. Es erscheint dem Autor aber zur Zeit die einzige Möglichkeit, halbwegs präzise Daten über die Internetnutzung zu gewinnen. Bei korrekter Fragestellung sind auch relativ gute Angaben über die Größe des Internet möglich. Dies ist aber wie gesagt vor allem von den Möglichkeiten der statistischen Auswertung der gewonnenen Daten abhängig. c)Ein Webcrawler hat eine Vielzahl von Probleme zu lösen, deren Hauptursache meist in der riesigen Zahl von Webseiten und der damit verbundenen Datenmenge liegt.Um das "ganze" Internet zu erfassen, muss man sich das ganze Internet quasi herunterladen, analysieren und verschlagworten bzw. strukturiert ablegen. Die Beschränkungen bei diesem Unterfangen sind vor allem die Bandbreite zum Internet, lokale Speicherkapazitäten, Rechenkapazitäten und damit einhergehend die Fähigkeit zur massiven Parallelisierung, da ein Rechner allein mit der Aufgabe hoffnungslos überfordert wäre. In all diesen Punkten hat sich bei Google eine sehr hohe Leistungsfähigkeit herausgebildet. Das grundsätzliche Vorgehen eines Webcrawlers ist das folgende:
Wie die Umsetzung in Aufgabe 1d zeigt, lässt sich dieses Vorgehen sehr gut parallelisieren, sodass man Beschränkungen an Rechen- und Speicherkapazität relativ einfach mit zusätzlicher Hardware erschlagen kann, wie es Google eindrucksvoll vormacht. Der begrenzende Faktor ist hier vor allem der benötigte Abstimmungsaufwand zwischen den einzelnen Arbeitsthreads / -prozessen / -maschinen / -clustern. Die Beschränkung der verfügbaren Bandbreite lässt sich eigentlich auch nur mit Parallelisierung lösen, indem die Crawler möglichst nah (netztopoligisch gesehen) an die zenteralen Knotenpunkte des Internets herangebracht werden und von dort abzweigen. Damit kann eine weltweite Präsenz in der Nähe der meisten Webserver und damit ein entsprechend hoher Datendurchsatz erreicht werden. Bei einer starken Parallelisierung ist das Hauptproblem, dass nur schwer verhindert werden kann, dass Webseiten doppelt besucht werden. Idealerweise existiert also eine Systemweite Liste mit bereits besuchten URLs. Befindet sich eine URL in dieser Liste, dann braucht sie bei zukünftigen Besuchen nicht mehr berücksichtigt zu werden. Ggf. kann man hier auch mit Zeitstempeln arbeiten um Webseiten nach einer gewissen Zeit erneut zu besuchen und auf Änderungen zu untersuchen. Bei einer solch engen Bindung des Systems an eine URL-Liste entsteht hier aber sehr schnell ein Performance-Engpass. Man kann aber ggf. zu einer Variante übergehen, bei der die URL-Liste nicht sofort aktualisiert wird. Dabei nimmt man dann in Kauf, dass einzelne URLS doch häufiger durchsucht werden. Über verschiedene Optimierungen sowie Cachingstufen und deren Lokalitäten kann hier aber sehr viel optimiert werden Ein weiteres Problem liegt in der häufig laxen Verwendungsweise von URLs. Diese sind selten sorgfältig geplant und aufgebaut. Einige Seiten sind unter mehreren URLs ansprechbar und haben eine nicht standardkonforme Struktur. Auch sind heute viele Seiten im Web mittels Scripten oder anderen Techniken dynamisch für jede Anfrage neu erzeugt. Es ergibt sich eine riesige Menge von potentiellen Zusammensetzungen für die imemr gleichen Stücke von Content, was aber für eine Suchmaschine, die sich vor allem auf URLs verlässt nur sehr schwer herauszubekommen ist. Das führt dazu, dass sich ein Crwaler leicht in einem Netz von automatisch generierten Links verfangen kann und den immer gleichen Content indiziert (Stichwort: Google-Spam) . Dies könnte sich durch statistische Auswertungen von Seiteninhalt und Aufbau lösen lassen, was dann zusammen mit den URLs in der oben beschriebenen globalen Liste gespeichert werden müsste (im Crawler in Aufgabe 1d nicht umgesetzt, da zu aufwändig). Damit würde sich auch teilweise das Problem der Aufbereitung der Suchergebnisse lösen lassen (das ja eigentlich nicht teil der ursprünglichen Aufgabe eines Webcrawlers ist) Ein bisher nur sehr unvollständig gelöstes Problem ist die zunehmende Verwendung von Javascript, Flash und anderen Techniken zur dynamischen Erzeugung von Seiteninhalten. Da hier in der Regel auch eine ganze Reihe von Links auf andere (ggf. dynamische) Inhalte erzeugt werden, wäre es vorteilhaft, diese Technologien durch den Webcrawler zu unterstützen und auch den dynamisch erzeugten Inhalt auszuwerten. Dies würde aber sehr viel Last auf dem Crawler erzeugen und ggf. auch Sicherheitslücken reißen. Häufig stellen sich die Suchmaschinenbetreiber auf den Standpunkt, dass es Aufgabe der Webentwickler sei, interoperable Webseiten zu erzeugen, die auch ohne Javascript und Flash funktionieren und ignorieren daher diese neuen Möglichkeiten. d)Siehe Anhang (WebCrawler.jar, Source Code), Nutzung: (`C-c` zum beenden.)x: Durchsuchte Seiten y: Gefunde Seiten z: Letzte durchsuchte Seite Folgende Rechnungen unter der (falschen) Annahme, dass der Crawler jede Seite nur einmal besucht, daher eine untere Grenze. Durchschnittliche Bearbeitungszeit einer Seite: 1.05s (davon ~98% HTTP Verbindung). --> 1.05 Sekunden * (10^12) ~ 33273 Jahre Stark parallelisierbar, aber (33273 Jahre) / (2^10) = 32.49 Jahre. TreeSet garantiert O(log(n)) Zeiten fuer add, remove, contains Operationen. (10^12) * 30 * (2 bytes) = 54.5696821 terabytes D.h. ~55TB wuerden allein fuer die Liste an URLs benoetigt, bei einer durchschnittlichen URL Laenge von 30 Charaktaeren. Ein SiteCrawler Objekt haelt nur die URL als Instanzvariable Aufgabe 2: Grenzen heutiger Suchmaschinena)Antwort: "Bei Hang Fung gibt es nämlich eine Toilette aus purem Gold. ""Nur wer zuvor Schmuck eingekauft hat (für mindestens 1000 Hongkonger Dollar, das sind umgerechnet etwa 270 DM), darf die Edeltoilette benutzen." (Gemeint sind vermutlich 100 Dollar, wie in einem späteren Satz erwähnt) Quelle: http://www.traumbad.de/nxs/746///traumbad/40/schablone1/platz_nehmen_und_sich_wie_ein_koenig_fuehlen__auf_der_toilette_aus_purem_gold.htm Suche: lam sai wing 100 dollar Position bei Google: 1 Aufwand: 2 Suchanfragen, <1min b)Antwort: "Im späten 19. und frühen 20. Jahrhundert etablierte sich die Anrede „Fräulein“ vor allem für berufstätige Frauen (z.B. Angestellte in Warenhäusern, Kellnerinnen und Lehrerinnen), da weibliche Berufstätigkeit damals noch strikt auf die Zeit vor der Ehe beschränkt war. Im Deutschen Reich gab es von 1880 bis 1919 sogar eine rechtliche Vorschrift (einen Ministererlass), wonach weibliche Lehrkräfte unverheiratet sein mussten, das „Lehrerinnenzölibat“."Quelle: http://de.wikipedia.org/wiki/Fr%C3%A4ulein Suche: lehrerinnen fräulein Position bei Google: 5 Aufwand: 1 Suchanfrage, <1min c)Antwort: "Ecuador hatte 2000 – vor Correas Amtsantritt – seine eigene Währung abgeschafft und durch den Dollar ersetzt."(war bereits in der Google-Vorschau lesbar) Quelle: http://www.neues-deutschland.de/artikel/138222.correa-will-waehrungsfonds-abschaffen.html Suche: währung abgeschafft 2000 Position bei Google: 4 Aufwand: 1 Suchanfrage, <1min d)Antwort: Hawaii (Vermutung)Quellen: http://de.wikipedia.org/wiki/US-Bundesstaat http://de.wikipedia.org/wiki/Hawaii Suchen: botswana; us-bundesstaaten Position bei Google: jeweils 1 Aufwand: 3 Suchanfragen, mehrere Wiki-Seiten lesen + menschliches Folgern, 3-5min - Anfrage ist schwer durch Suchmaschine beantwortbar, daher habe ich mir die Karten selbst angeschaut und durch "Hinschauen" die Frage beantwortet e)Antwort: Tycho BraheQuelle: http://de.wikipedia.org/wiki/Tycho_Brahe?title=Spezial:Booksources&isbn=3518369903 Suche: harnverhaltung mondkrater hamburg-wandsbek Position bei Google: 1 Aufwand: 4 Suchanfragen (bis richtige Kombination von Suchbegriffen gefunden wurde), 2-3min f)
Aufgabe 3: Qualität von Suchmaschinena)Grundsätzliche Herangehensweise
Anzahl Ergebnisse
Traditionelle Größen
Die üblichen Verdächtigen: |