10. NAT, IPv6, RIP, OSPF, BGP

NAT

Motivations:

Each device has an internal IP address, but packets exiting the network have their source address transformed into a single public IP address.

Question: how does the router know which host to forward returning traffic if all devices have the same public IP address?

A table mapping a (external IP, external port) tuple to an (internal IP, internal port) tuple. When the device sends a packet, the router will randomly choose an external port to use, and when the response packet arrives, it can simply map this to the device’s internal IP and port.

The port number is a 16 bit field, so it theoretically allows over 60,000 simultaneous connections.

Controversy:

IPv6

Motivations:

Datagram Format

IPv6 is simpler; no fragmentation, no checksums, fixed length (40 bytes) header:

Transition

Old devices only support IPv4, and some routers cannot be upgraded. Hence, ‘flag days’, where the world switches protocol on some specified day, will not work.

With a dual-stack approach, all IPv6 nodes also have complete IPv4 implementations, allowing packets to be transformed in both directions as it is routed. This loses IPv6 or IPv4 specific fields.

Another approach is tunnelling: stuff the whole IPv6 datagram as the payload of a IPv4 datagram. If the packet is small enough and DF is set, a IPv6 router can then parse the payload and forward it as a IPv6 packet.

Due to DHCP, CIDRised addresses and NAT partially solving the IP address shortage problem (in the short term), IPv6 adoption has been slow.

Routing in the Internet

Flat networks don’t scale: if you have millions of hosts, storing routing information for each requires large amounts of memory. If link-state routing is used, broadcasting LS updates takes too much bandwidth, and if distance-vector routing is used, it will never converge.

Hierarchical Routing

Hierarchical routing aggregates routers into autonomous regions, where routers belong to the same organization and run the same intra-AS routing protocol.

Gateway routers have a direct link to a router in another AS.

The forwarding table is configured by both intra- and inter-AS routing algorithms:

Routing between ASes

Case 1: a single gateway router to only one other AS:

Case 2: two or more physical links to other ASes (typically a transit AS):

RIP - Routing Information Protocol

Uses the distance vector algorithm.

Distance metric:

To determine subnets, detach each interface from its host/router to create islands of isolated networks; the interfaces are the endpoints of the isolated networks, called subnets.

RIP advertisements:

Example:

w-- A --x-- D --y-- B-- ... --`z`
    |
    C

The routing table in D would have:

Dest. net Next router Num. hops
w A 2
y B 2
z B 7
x NA 1

If A then advertises its own routing table where the cost to z (through C) is 4, D would use the Bellman-Ford equation and update its routing table to route requests to z through A with a cost of 5.

After 180 seconds of no advertisements, the neighbor/link is declared dead; routes going through that neighbor are invalidated and new advertisements are sent to neighbors. Through this, the link failure information propagates through the entire network.

Differences between RIP and the DV Algorithm

OSPF - Open Shortest Path First

Advanced features not in RIP:

OSPF ASes are configured into areas. Within an area:

There is one backbone area which links areas together. In the backbone:

BGP - Border Gateway Protocol

The de facto standard. Provides each AS with the ability to:

Pairs of routers - BGP peers, exchange routing information over TCP connections (called BGP sessions).

eBGP sessions allow routers in two different AS’s to exchange reachability information - when it advertises a prefix, it promises that it can forward any datagrams destined to that prefix. The receiver can then create an entry for that prefix in its forwarding table and re-advertise the same information to others via iBGP (between routers in the same AS) or eBGP sessions.

The advertisement is a combination of the prefix and attributes. Two important attributes are:

Route selection

Routers may learn about more than one route to a given prefix, so it uses elimination rules to pick one:

  1. Local preference value attribute (policy decision)
  2. Shortest AS-PATH (DV algorithm)
  3. Closest NEXT-HOP router (hot potato routing)
  4. Additional criteria

Routing policy can affect routing. For example, a keep silent policy could occur if X is a dual-homed (e.g. for redundancy) customer network connected to B and C provider networks; it will not want to route traffic from B to C and hence hence, it will not advertise to B a route to C, or vice versa.