OSPF, BGP and multicast

The algorithms on the previous page were on paper. In the real Internet there are protocols that run them: OSPF inside an organization, BGP between organizations. There is also multicast, the way to send a packet to many receivers at once. From this page the exam mostly asks concept questions and small calculations. Golden rules:

1. Inside an AS = performance, between ASes = policy.
2. OSPF is link-state and runs directly over IP (protocol 89).
3. BGP is path-vector and runs over TCP 179.
4. BGP selection is ordered: LOCAL_PREF, then AS-PATH length, then hot potato.
5. Multicast MAC = 01:00:5e + the low 23 bits of the IP.

Autonomous systems (AS)

The Internet is not a single network but a union of thousands of autonomous systems (AS). Each AS has a number (ASN) and manages its own routers itself. There are two reasons for two-level routing:

• Scale: it is impossible for all routers to know all links. Link-state packets would eat all the bandwidth.
• Administrative autonomy: each organization wants to choose its own algorithm and hide its topology inside its network.

OSPF (Open Shortest Path First)

OSPF is a link-state protocol. Each router spreads the state of its links to everyone in the AS by flooding (link-state advertisement, LSA). It does so when something changes, and also periodically even if nothing changes (at least every 30 minutes). Each router runs Dijkstra on the same map and builds its own shortest-path tree.

Features:

• Messages go directly inside IP, with protocol 89. No TCP/UDP; OSPF provides reliable delivery itself.
• Authentication: messages can be authenticated against the injection of forged LSAs. This matters for the security part of the course.
• If there are several equal-cost paths, traffic can be split (ECMP).
• Hierarchy: large ASes are divided into areas. LSAs spread within an area. All areas connect to the backbone, which is area 0. Routers on an area boundary are ABRs (area border routers), and those connecting outside the AS are ASBRs.

OSPF cost calculation

The administrator determines the link cost. A common default (Cisco style): reference bandwidth / interface bandwidth, rounded down to an integer, at least 1.

reference = 100 Mbps
10 Mbps     → 100/10    = 10
100 Mbps    → 100/100   = 1
1 Gbps      → 100/1000  = 0.1 → at least 1
45 Mbps     → 100/45    = 2.22 → 2
1.544 Mbps  → 100/1.544 = 64.77 → 64      (T1)

path: T1 + 100 Mbps + 10 Mbps = 64 + 1 + 10 = 75
path: 45 Mbps + 100 Mbps + 100 Mbps = 2 + 1 + 1 = 4

PITFALL · fast links become equal. With a reference of 100, 100 Mbps, 1 Gbps and 10 Gbps all come out as 1. OSPF sees them all as the same. With a reference of 10000, 100 Mbps → 100, 1 Gbps → 10, 10 Gbps → 1.

BGP (Border Gateway Protocol)

BGP is the protocol that holds the Internet together. It gives each AS two things: learning which prefixes are reachable through neighbouring ASes, and spreading this information to all the routers inside its own AS. And most importantly: deciding by policy which route to use and to whom to advertise.

Sessions. Two BGP routers open a session over TCP port 179.

• eBGP: between two border routers (gateways) in different ASes.
• iBGP: between routers inside the same AS; it distributes the route learned by eBGP inward.

Route = prefix + attributes. BGP is a path-vector protocol: for each destination it advertises not just a cost but the whole AS path.

If a router sees its own AS number in the AS-PATH of an advertisement, it rejects the advertisement. This is how loops are prevented.

Route selection

If there are several routes for the same prefix, the rules are applied in order; when a rule leaves a single candidate, you stop:

1. Highest LOCAL_PREF.
2. Shortest AS-PATH.
3. Closest NEXT-HOP (the exit with the lowest intra-AS cost): hot potato routing.
4. For remaining ties, binding rules such as the BGP router ID.

Example. R1 learned three routes for prefix 198.18.0.0/16:

route  LOCAL_PREF  AS-PATH       intra-AS cost to NEXT-HOP
K      150         AS2 AS9       7
L      150         AS4 AS9       3
M      100         AS9           1

1) Highest LOCAL_PREF: K and L (150). M is eliminated (even though its AS-PATH is the shortest)
2) AS-PATH: both are 2 ASes → equal
3) hot potato: L's NEXT-HOP is closer (3 < 7) → L is selected

PITFALL · mixing up the order. Choosing M because it has the shortest AS-PATH is wrong. The LOCAL_PREF rule comes earlier and expresses the administrator’s policy.

Policy

An AS also chooses which routes to advertise. A typical rule: traffic going to customer networks is carried, but free transit is not given between two providers. A stub network does not advertise itself as transit, even if it is connected to several providers (multi-homed). Security note: BGP advertisements are not verified by default. If an AS advertises a prefix that does not belong to it, traffic flows to it (prefix hijacking). Mechanisms such as RPKI try to prevent this.

Broadcast and multicast

Broadcast sends a packet to everyone in the network, multicast only to those who are members of a group. Sending N separate copies for N receivers (N-way unicast) uses up the source’s link. Copying inside the network is more efficient.

Broadcast methods. Uncontrolled flooding produces endless copies in loops (broadcast storm). Solutions:

• Sequence-number-controlled flooding: each node does not forward a (source, sequence number) pair it has seen before.
• Reverse path forwarding (RPF): if the packet arrived on the interface of the router’s own shortest path to the source, it is forwarded on all other interfaces; if it came from another interface, it is dropped.
• Spanning tree: a spanning tree is built first, and the packet moves only along the edges of the tree.

Multicast addresses. In IPv4, class D: 224.0.0.0/4, that is 224.0.0.0 to 239.255.255.255. 224.0.0.x is reserved for the local link (e.g. 224.0.0.5 for OSPF routers).

IGMP runs between a host and the router directly attached to it: the router asks “is there a member of this group?” (membership query), and the host answers (membership report). Multicast trees between routers are built by PIM (Protocol Independent Multicast) or DVMRP.

From multicast IP to Ethernet MAC

The Ethernet multicast MAC starts with 01:00:5e, followed by one 0 bit and the low 23 bits of the IP address.

239.200.15.7
2nd octet 200 = 11001000 → top bit dropped → 1001000 = 0x48
3rd octet 15 = 0x0f, 4th octet 7 = 0x07
MAC = 01:00:5e:48:0f:07

224.10.20.30   → 01:00:5e:0a:14:1e
224.138.20.30  → 01:00:5e:0a:14:1e   (138 & 0x7f = 10)
225.10.20.30   → 01:00:5e:0a:14:1e   (the first octet does not enter at all)

There are 28 bits for the group (the first 4 bits 1110 are fixed), and 23 of them enter the MAC. Because of the 5 lost bits, $2^5 = 32$ groups share the same MAC. The card receives them, and the IP layer drops the unwanted ones.

TIP · quick calculation. If the second octet is less than 128, write it as is; if it is 128 or more, subtract 128. Then append the hexadecimal values of the three octets after 01:00:5e.

Common mistakes

Route  LOCAL_PREF  AS-PATH         NEXT-HOP IGP cost
X      100         AS2 AS5         4
Y      200         AS3 AS4 AS5     9
Z      200         AS6 AS5         12