Routing And Internetworking

Routing is the set of decisions that determine where a packet of data goes next.

11 frameworks, from 1961 to today · Networks · Computer Science

still a working view ended · each leads to its entry below

Overview

Routing is the set of decisions that determine where a packet of data goes next1. Internetworking is the larger project of joining many separate networks into one that behaves, more or less, like a single network2. The two are inseparable: the moment you connect two networks, someone has to decide which traffic crosses the boundary and by what path. What is at stake is coordination without central control. No one owns the Internet, yet billions of machines route packets across it every second. The history of this subfield is the story of how engineers built that coordination out of local decisions, and of the repeated crises—scale, address exhaustion, security, and the tension between automation and policy—that forced each new layer of machinery into being.

Packet switching and the first routing problem

The founding idea was packet switching, developed in the 1960s in work by Paul Baran at RAND and Donald Davies at the UK's National Physical Laboratory, and realized in the ARPANET, whose first link connected UCLA and Stanford Research Institute in 1969. Instead of reserving a circuit, packet switching chops messages into small units that share links statistically. That immediately raised the routing question: with no reserved path, each packet needs a next hop chosen at the moment it travels.

ARPANET's early answer was a distributed, adaptive scheme3. Each node kept a table of the least-delayed path to every destination and updated it by exchanging delay estimates with neighbours. The lesson learned painfully in the early 1970s was that adaptive schemes can oscillate—everyone shifts to the "best" path, congesting it, then shifts away. The fix was to damp updates and to separate the algorithm (how paths are computed) from the protocol (how routers exchange what they know). That separation has organized the field ever since.

Two families of routing algorithms

By the late 1970s two competing approaches had crystallized, and their rivalry still structures routing.

Distance-vector routing has each router tell its neighbours its own estimate of the distance to every destination; a router adopts a neighbour's route if going through that neighbour is shorter13. It is simple and needs little memory, but it converges slowly and suffers from the "count-to-infinity" problem, where a broken link is advertised around a loop and distances creep upward. The classic remedy, split horizon with poisoned reverse, was refined through the 1970s and 1980s. The Routing Information Protocol (RIP), standardized in the 1980s, is the canonical distance-vector protocol34.

Link-state routing takes the opposite approach: each router floods the network with the state of its own links, so every router builds an identical map of the whole topology and runs Dijkstra's shortest-path algorithm on it15. The idea descends from work at BBN and elsewhere in the late 1970s; the Open Shortest Path First (OSPF) protocol, developed in the late 1980s and standardized in the early 1990s, became its dominant embodiment, alongside IS-IS, which had been developed for the ISO protocol suite. Link-state converges faster and avoids loops, at the cost of memory and flooding overhead. The trade-off—simple and local versus complete and costly—is a recurring theme.

Internetworking: the Internet Protocol

The decisive move came with the design of the Internet Protocol by Vint Cerf and Bob Kahn, published in 1974 and refined into IPv4 in 198167. Their insight was to make the network's job minimal: a common packet format and a common addressing scheme, with no guarantee of delivery, ordering, or reliability. Reliability would live in the endpoints—the end-to-end principle later articulated by Jerome Saltzer, David Reed, and David Clark in 1984. This "best-effort" datagram model let wildly different underlying networks (ARPANET, satellite links, Ethernet, radio) interconnect, because the only thing they had to agree on was the IP header.

The corollary was that routing had to be hierarchical. Within an organization, routers could use whatever interior protocol suited them; between organizations, they needed a common exterior protocol. The terms interior gateway protocol and exterior gateway protocol date from this period. The first widely used exterior protocol, EGP, appeared in the early 1980s; it was replaced by the Border Gateway Protocol (BGP), first specified in 1989 and brought to version 4 in 1994.

Interdomain policy routing and the rise of BGP

BGP solved a problem the interior protocols could not: the Internet is not one administrative domain but tens of thousands, each owned by a different party with its own commercial and political interests. A path between two networks is not chosen for shortness but for policy—who is willing to carry whose traffic, and on what terms. BGP lets each network (an autonomous system) advertise the routes it will accept and the paths it offers, and each chooses among them by local rules89. The result is a routing system that is decentralized, path-vector rather than distance-vector (it carries the full AS path, which also serves to detect loops), and fundamentally about trust and business relationships rather than optimality.

This design made the Internet scale, but it also made it fragile in ways that would take decades to confront. BGP has no built-in authentication: a network can, by misconfiguration or malice, advertise routes it does not own and hijack traffic. Notable incidents—such as the 2008 leak by Pakistan Telecom that briefly took YouTube offline worldwide—made the vulnerability concrete.

Scaling the address space: classless routing and NAT

IPv4's original addressing divided the world into fixed classes (A, B, C), a scheme that wasted addresses badly. By the early 1990s exhaustion was in sight10. Two responses reshaped routing.

Classless Inter-Domain Routing (CIDR), introduced in 1993, abandoned fixed classes for arbitrary-length prefixes and, crucially, allowed route aggregation: many contiguous addresses could be advertised as one prefix, keeping global routing tables from exploding11. CIDR also made longest-prefix matching the core forwarding operation—a router picks the most specific matching route12.

Network Address Translation (NAT) let many devices share one public address by rewriting addresses at the boundary10. NAT was conceived as a short-term fix but became pervasive, and it changed the Internet's topology: it made the end-to-end principle conditional, since hosts behind NAT are not directly reachable. Together, CIDR and NAT bought decades of life for IPv4.

IPv6 and the long transition

The long-term answer was a new protocol with a vastly larger address space. IPv6 was designed through the early 1990s and standardized in 1998. It also simplified the header and was meant to restore end-to-end addressing. But deployment has been slow and incremental, and the field's real history is one of coexistence: dual-stack hosts running both protocols, tunnelling IPv6 over IPv4, and translation mechanisms at the boundary. The transition is still incomplete, and the coexistence machinery—not the clean replacement—is what practitioners actually built.

Securing the routing system

Because BGP trusts what it is told, the 2000s and 2010s saw a sustained effort to add verification. The Resource Public Key Infrastructure (RPKI) lets address holders certify which networks are authorized to originate which prefixes, so routers can validate route origins13. The approach is real and deployed, but partial: it secures origin, not the full path, and adoption has been uneven. The open question—how to secure interdomain routing without breaking its decentralized, policy-driven character—remains live.

Separating control from forwarding: SDN and segment routing

The most recent turning point reverses an assumption. Traditionally every router ran its own control software, computing routes independently. Software-Defined Networking pulls the control logic out into a separate, programmable controller that computes paths centrally and installs them in the switches, which become simple forwarders14. The idea grew from earlier work on separating control and data planes and on programmable networks in the 2000s; the OpenFlow protocol, around 2008, gave it a concrete interface, and it became widely used in data centres and wide-area backbones where centralized control is practical. SDN did not replace distributed routing on the public Internet—scale and autonomy still favour it—but it changed how networks are operated and made routing programmable.

Segment routing, developed in the 2010s, takes a different tack: instead of signalling state along a path, a source lists a short sequence of "segments" (instructions) in the packet header, and routers execute them. It simplifies traffic engineering and is now used in large service-provider networks.

Where the field stands

Today's routing runs on the same two-tier skeleton: link-state and distance-vector protocols inside domains, BGP between them, with CIDR aggregation and NAT holding the address system together while IPv6 coexistence slowly deepens. Around this core sit the newer layers—RPKI for origin validation, SDN controllers for programmable operation, segment routing for traffic engineering. The open questions are the ones the history kept postponing: how to secure interdomain routing end to end without centralizing it, how to complete the IPv6 transition, and how to keep a system built on local trust and local decisions robust as it grows and as its operators' interests diverge.

References

  1. Routing (introduction, Distance vector algorithms, Link-state algorithms), Wikipedia
  2. Internetworking, Wikipedia
  3. Distance-vector routing protocol (introduction, Development of distance-vector routing), Wikipedia
  4. Routing Information Protocol, Wikipedia
  5. Link-state routing protocol, Wikipedia
  6. Internet Protocol, Wikipedia
  7. IPv4 (History), Wikipedia
  8. Border Gateway Protocol, Wikipedia
  9. BGP hijacking (Background), Wikipedia
  10. Network address translation (History, introduction), Wikipedia
  11. Classless Inter-Domain Routing, Wikipedia
  12. Longest prefix match, Wikipedia
  13. Resource Public Key Infrastructure, Wikipedia
  14. Software-defined networking, Wikipedia

The frameworks of Routing And Internetworking

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1961-Present

    Packet Switching

    How can data be transmitted without reserving a dedicated path?

    Fly to its tower in Nousfarer

  2. 1974-Present

    Internet Protocol

    What minimal requirements must a network use to connect disparate networks?

    Fly to its tower in Nousfarer

  3. 1975-Present

    Distance-vector routing protocol

    How can a router determine the best path using only neighbor information?

    Fly to its tower in Nousfarer

  4. 1989-Present

    Interdomain Policy Routing

    How should routing decisions be made when different networks have different business rules?

    Fly to its tower in Nousfarer

  5. 1993-Present

    Classless Inter-Domain Routing

    How can address space be used more efficiently when prefixes are not fixed?

    Fly to its tower in Nousfarer

  6. 1994-Present

    Network Address Translation

    How can multiple private devices share a single public address?

    Fly to its tower in Nousfarer

  7. 1998-Present

    List of IPv6 transition mechanisms

    How can a network transition between different addressing schemes?

    Fly to its tower in Nousfarer

  8. 2008-Present

    Routing Security and Origin Validation

    How can the origin of a network route be cryptographically verified?

    Fly to its tower in Nousfarer

  9. 2008-Present

    Software-Defined Networking

    How can the logic for path computation be separated from the forwarding hardware?

    Fly to its tower in Nousfarer

  10. 2013-Present

    Segment Routing

    How can a packet be instructed to follow a specific sequence of network hops?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Packet SwitchingInternet ProtocolDistance-vector routing protocolLink-state routing protocolInterdomain Policy RoutingClassless Inter-Domain RoutingNetwork Address TranslationList of IPv6 transition mechanismsRouting Security and Origin ValidationSoftware-Defined NetworkingSegment Routing

Beyond the field

Where Routing And Internetworking's ideas came from in other fields, and what they led to there: the strongest 12 of 50 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Routing And Internetworking is a planet in Nousfarer

Its city has a tower for each of these 11 frameworks. Land, walk in, and climb one concept at a time.

Land on Routing And Internetworking

Related fields

Fields its ideas are linked to

More in Networks

See where Routing And Internetworking sits on the Map of Human Knowledge