Intra-AS routing (OSPF)

Assuming that all routers over the world run the same routing algorithm is too simple for two main reasons:

1. scale:
   • as the number of routers becomes large, costs become prohibitive:
     • exchanging routing information
     • computing routes
     • storing routing tables
   • the Internet needs a way to reduce this complexity
2. administrative control:
   • each organization wants to manage its own network
   • organizations may choose different routing algorithms
   • they may also want to keep their internal network structure private

Autonomous Systems (AS)

To solve these problems, routers are grouped into Autonomous Systems (ASs):

• an AS is a set of routers under one administrative control
• usually, one ISP corresponds to one AS, but large ISPs may use multiple ASs
• each AS has a unique identifier called an Autonomous System Number (ASN) (RFC 1930):
  • assigned by Regional Internet Registries (RIRs)
  • under allocation from IANA (Internet Assigned Numbers Authority)
  • which operates under ICANN

Routers within the same AS all run the same routing algorithm.

ISP Tier Model

Internet Service Providers are informally grouped into a tier model based on how they interconnect and exchange Internet traffic.

Tier 1 ISPs

Tier 1 ISPs are global networks that can reach every other network on the Internet without paying for IP transit, relying only on mutual peering.

• they sit at the top of the Internet hierarchy
• they own large global backbone networks and are sometimes referred to as backbone Internet providers
• they exchange traffic with other Tier 1 networks through peering agreements
• they do not need to buy Internet connectivity from another provider
• they build and operate large-scale infrastructure, including international fiber networks and submarine cable systems (often in consortia with other organizations)
• they sell IP transit services to Tier 2 providers and other networks

Tier 1 status is not formally defined by any standards body and depends on a network's peering relationships.

As a result, the exact list of Tier 1 networks can change over time as peering agreements evolve, companies merge, and Internet economics shift.

Tier 2 ISPs

Tier 2 ISPs are networks that can reach part of the Internet through peering agreements but must purchase IP transit to reach full global Internet connectivity.

They sit in the middle of the Internet hierarchy, between Tier 1 backbone providers and smaller access providers.

• they purchase IP transit from one or more Tier 1 providers to reach the full Internet
• they also peer with other Tier 2 ISPs and sometimes large content and cloud networks
• they often operate national or regional backbone networks
• they may provide Internet access directly to residential customers, businesses, and organizations
• they sell transit to smaller ISPs (Tier 3) and enterprise networks

As with Tier 1 networks, Tier 2 is an informal classification based on peering and transit relationships rather than a formal technical standard.

Tier 3 ISPs

Tier 3 ISPs provide Internet access directly to end users (homes, businesses, and organizations) and rely on upstream providers for Internet connectivity.

They sit at the bottom of the Internet hierarchy.

• they provide last-mile connectivity using technologies such as fiber, cable, DSL, or wireless networks
• they purchase IP transit from upstream providers (Tier 2 or Tier 1 ISPs) to reach the rest of the Internet
• they usually have limited or no peering relationships
• their infrastructure and coverage are regional or local, rather than national or global

In practice, Tier 3 ISPs are what most people interact with directly when they buy Internet service.

Open Shortest Path First (OSPF)

OSPF (and a related protocol, IS-IS) is used for routing inside an autonomous system (intra-AS).

The term Open in OSPF means it is not proprietary, in contrast to Cisco's older EIGRP protocol which was proprietary for a long time.

OSPF is a link-state routing protocol.

Link costs

Each network link is assigned a cost by the administrator.

This may be:

• a fixed value like 1 (for simple hop-count-like behavior)
• a value derived from bandwidth (where higher-capacity links have lower cost)

Routers

Each router:

• discovers neighbors using the Hello protocol
• builds a complete map (topology graph) of its OSPF area
• runs Dijkstra's shortest path first algorithm, using itself as the root

Routers exchange and flood link-state information using Link-State Advertisements (LSAs). This flooding occurs:

• when a topology change happens (link up/down or cost change)
• periodically, even if no changes occur (typically every 30 minutes, as defined in RFC 2328)

Complexity

OSPF includes its own mechanisms for reliable flooding, neighbor discovery, and area-based hierarchy, which makes it a relatively complex protocol.

However, this design improves scalability and convergence performance.