Eine alternative Netzwerktopologie schlug Paul Baran (1964) von der RAND Corporation vor. Mit seinem Vorschlag versuchte Baran, der Sorge der US Air Force um die Überlebensfähigkeit ihrer Kommandostruktur im Falle eines sowjetischen Nuklearangriffs Rechnung zu tragen. An Stelle des konventionellen Sterns sah Baran ein "distributed network" vor, bei dem spinnwebförmig eine Vielzahl von Verbindungen zwischen den in das Netzwerk eingebundenen Rechnern vorgesehen war. Durch den Wegfall eines Zentralrechners sollte das Datenaufkommen im Netzwerk gleichmäßig auf die einzelnen Leitungen aufgeteilt werden. Da viele Leitungen redundant sind, gibt es in einem verteilten Netzwerk stets mehrere Wege von einem Start- zu einem Zielrechner. Ein Totalausfall des Netzes kann deshalb erst auftreten, wenn jeder einzelne mögliche Pfad ausfällt. Damit ist eine sehr viel höhere Zuverlässigkeit als bei einem Telefonnetz mit festen Leitungsverbindungen erreichbar.

Den militärischen Auftraggebern wurde das verteilte Netzwerk mit dem Argument schmackhaft gemacht, es könne seine Funktion sogar bei dem im Falle eines Krieges befürchteten Ausfall großer Teile des Gesamtnetzes aufrechterhalten. Obwohl die Air Force von Barans Idee begeistert war, wurde das Netz in seiner geplanten Form nicht realisiert, weil das Verteidigungsministerium auf einem Gesamtnetz für alle Streitkräfte bestand. Barans Vorschläge flossen aber in die späteren Überlegungen anderer Netzwerkentwickler ein. Als einflussreich erwies sich dabei vor allem die Idee des "packet switching".

Anstatt für die Übertragung einer Nachricht eine feste Leitung wie beim Telefonieren einzurichten, hielt Baran für sein Netzwerk das Aufspalten der Nachrichten in viele kleine Pakete für die geeignete Übertragungsmethode. Seine Überlegung war, auf diese Weise das Datenaufkommen im Netzwerk besser zu verteilen. Für jedes einzelne Paket würde in Analogie zum Versand konventioneller Postpakete individuell bestimmt werden, welches der gerade jeweils günstigste Weg zum Bestimmungsort ist. Wenn eine Leitung verstopft ist oder ausfällt, nimmt das Paket einfach einen anderen Weg. Falls ein Paket verloren geht, wird nur das verloren gegangene Paket erneut verschickt, nicht aber die ganze Nachricht. Auf dem Zielrechner kann nach Eintreffen aller Pakete die ursprüngliche Nachricht wieder zusammengesetzt werden, wobei es gleichgültig ist, ob die Pakete in der richtigen Reihenfolge an ihrem Bestimmungsort ankommen oder nicht. Da jedes Datenpaket und jeder Rechner im Netz "weiß", wie und wohin die Informationen weiterzusenden sind, ist eine zentrale Steuereinheit nicht erforderlich. Die verschickten Datenpakete sind prinzipiell in der Lage, beliebige Inhalte aufzunehmen: Computerprogramme und -daten, digitalisierte Stimmen, Töne, Texte, hochauflösende Grafiken oder bewegte Bilder.

Viele Skeptiker zweifelten zunächst am Sinn des "packet switching". Der nicht unerhebliche zusätzliche Aufwand, alle einzelnen Pakete mit dem Zielort zu beschriften und an jedem Knotenpunkt im Netzwerk neu zu bestimmen, wohin ein Paket am besten weitergeleitet wird, schien das System unnötig komplex und störanfällig zu machen. Fraglich schien weiter, ob die Speicherkapazität der Zielrechner immer ausreichen würde, um die einzelnen Teile mehrerer Nachrichten bis zum Eintreffen des letzten Paketes aufzunehmen. Besonders Telefontechniker bezweifelten, dass das Eintreffen jedes einzelnen Paketes auf dem Zielrechner gewährleistet werden könne, wenn der gewählte Weg für jedes Paket neu bestimmt wird.

Die Societe Internationale de Telecommunications Aeronautiques (SITA) entschloss sich 1965 dennoch, Barans Vorschlag aufzugreifen und erstmals das Prinzip des "packet switching" für die Kommunikation der ihr angeschlossenen 175 Fluggesellschaften einzusetzen (Hirsch, 1974). Neun Knotenpunkte - Amsterdam, Brüssel, Frankfurt, Hong Kong, London, Madrid, New York, Paris und Rom - wurden mit fest gemieteten Telefonleitungen untereinander verbunden. Alle Nachrichten wurden zum jeweils nächstgelegenen Netzknoten weitergeleitet, bis der Zielflughafen erreicht war. Das SITA-Netz war ein voller Erfolg. Bereits im Jahr 1973 überstieg das Datenvolumen des Systems das des gesamten internationalen Telegraphieverkehrs. Ein weiteres paketorientiertes Netz wurde 1965 im National Physical Laboratory in England aufgebaut. Es blieb jedoch in einem experimentellen Stadium, weil aus Kostengründen der ursprüngliche Plan einer landesweiten Vernetzung nicht realisiert werden konnte (Abbate, 1994).

Ein Jahr später nahm IPTO die Idee in Angriff, nach Barans Plänen die über das ganze Land verstreuten ARPA-Computerzentren miteinander zu vernetzen. Unter Zugrundelegung der "packet switching"-Technologie plante man eine landesweite, verteilte Topologie. Durch effiziente Routing-Algorithmen sollte die rasche und effiziente Verschickung der anfallenden Datenpakete gewährleistet werden.