Internet Routing Protocols

New networks are being added to the Internet all the time, old networks are taken down, and networks can move around. How do the routing tables of a router get populated and how do they keep up with all of these changes?

Typically a host is attached to a single router, the default router or first hop router (on the same LAN). In this case, routing is trivial. When a host on a LAN wants to send a packet to the Internet, it always sends it to its default router.

The routing table on the default router is almost as simple. It knows how to route packets on its own LAN, it may know how to route packets on other subnets, but it just forwards all the packets which are destined anywhere else on the planet to its own default router.

The routing tables for an ISP are larger, but they do not need to know about every network on the Internet, They need to know where to send packets for all of their own customers, but often they have a default route as well. They simply forward packets destined to other network to their Tier 1 router.

Unfortunately, the Tier 1 routers cannot use default routing like everyone else can; they have to know about every network on the Internet.

The Internet is a set of Autonomous Systems (ASs); that is, independent organizations, each of which runs some small fraction of the Internet. There are two classes of routing algorithms, interior gateway algorithms, which choose a path within an Autonomous System, and Exterior Gateway Algorithms, which exchange routing information between Autonomous Systems. Not surprisingly, an AS can choose whatever interior algorithm it wants to, but all systems on the Internet have to use the same exterior gateway protocol, the Border Gateway Protocol (BGP).

Routing is complicated by the fact that new networks are constantly being added to the Internet, other networks are moved around, and yet others are removed.

There are several types of routing algorithms. A centralized algorithm, or global routing algorithm has all information about all connections between routers. A decentralized routing algorithm is one in which the calculation are done iteratively based only on local information.

A static routing algorithm is one in which routes change slowly, often as a result of human intervention. A dynamic routing algorithm changes in real time based on congestion, path changes, etc.

Routing within an AS (interior gateway routing)

There are two widely used Interior Gateway Protocols, the Routing Information Protocol (RIP), and the Open Shortest Pathway First (OSPF) algorithm.

RIP

RIP is a fairly simple routing algorithm. It was included in the original BSD4.2 distribution, 1982, (RFC 1958) but it is still widely used on small networks.

The metric is the hop count, i.e. how many hops does it take to get from one node to another node. It does not take into account that some links may be much faster than others or that some nodes may be much more congested than others.

Neighboring routers exchange distance vectors with each other. This is the current estimate of the shortest path distance from that router to subnets in the AS. Routing updates are exchanged every 30 seconds using a RIP response message. This contains up to 25 destination subnets within the AS along with the senders distance to each of these.

Each router has a RIP table, with an entry for each subnet, along with the output line and the hop count. It starts at 1 (a subnet directly reachable from a router). In the case of ties, the router does not update its table (this prevents oscillation).

Here is an example. Consider this network.

Initially each routing table only knows about its own immediate neighbors. The routing table for B would look like this.

Host	Hops	Line
A	1 hop	A
C	1 hop	C
D	1 hop	D
E	1 hop	E

At time one, router B will receive a copy of the routing table for each of its immediate neighbors. It will look for new hosts. After this update, the routing table for B would look like this.

Host	Hops	Line
A	1 hop	A
C	1 hop	C
D	1 hop	D
E	1 hop	E
F	2 hop	D
G	2 hop	D
J	2 hop	E

At time two, after each immediate neighbor has sent its routing table a second time, B's routing table would look like this.

Host	Hops	Line
A	1 hop	A
C	1 hop	C
D	1 hop	D
E	1 hop	E
F	2 hop	D
G	2 hop	D
H	3 hop	D
I	3 hop	D
J	2 hop	E

Eventually the system would converge, and B's routing table would look like this.

Host	Hops	Line
A	1 hop	A
C	1 hop	C
D	1 hop	D
E	1 hop	E
F	2 hop	D
G	2 hop	D
H	3 hop	D
I	3 hop	D
J	2 hop	E
K	5 hop	D
L	4 hop	D

RIP works very well for small networks. However, there is a problem called "slow convergence". In our example, suppose the link from D to G goes down, so that G is no longer reachable. D stops advertising a link to G as it should, but E continues to advertise that it can reach G in three hops, because it has not yet received the news that G is unreachable. Thus, B thinks that it can get to G in three hops through E, so it continues to forward packets destined for G, and it continues to advertise to other routers that it can reach G.

Open Shortest Path First (OSPF)

OSPF is link-state algorithm. That is, each node knows the state of every node and edge on the network and models this as a graph. Unlike RIP, edges can have costs associated with them; although these costs (weights) have to be set manually by the system administrator.

Each node then uses Dijkstra's Algorithm to compute the least cost path to every other node on the network, using itself as a root.

Everyone should know Dijkstra's Algorithm, so I am not going to go over it again. Here are some links if you want to review it.

Dijkstra's Algorithm 1
Dijkstra's Algorithm 2

OSPF provides a number of features not available on RIP

• Type of Service Routing: a router can send different packets on different routes depending on type of service.
• Authentication: OSPF messages can be authenticated to prevent a malicious user from spoofing.
• Load Balancing: A router can know of more than one route to a particular node and can send packets over either one.
• A network can be divided into areas, and routing in each area is done separately.

A large network can be divided into areas. Each area then runs its own implementation of Dijkstra's Algorithm. Exactly one area is called the backbone area, and serves as a link to all of the others. There must be a router in each area which is also a router in the backbone area. These are called Area Border Routers. The backbone router typically has at least one Gateway Router which links the network to the rest of the Internet. A Gateway Router would run BGP as well as OSPF.

The Border Gateway Protocol (BGP)

The Autonomous Systems (AS's) on the Internet exchange routing information using BGP. This is an Internet standard, and it is the way that each subnet (AS) advertises its existence to the rest of the Internet. Each subnet (AS) advertises its existence to the rest of the Internet.

Pairs of BGP routers exchange information over semi-permanent TCP connections on Port 179. There is one connection for each pair of connected routers in two different ASs. (an external BGP session). It is also possible for a single AS to run BGP internally.

What is exchanged is not hosts, but CIDRized prefixes with each prefix representing a subnet or collection of subnets. Each BGP connection advertises the list of prefixes that are reachable from itself. Each advertisement is a promise to deliver packets to all subnets in that address. When a gateway router receives a list of subnets from an outside router, it propagates this information within the AS. If it has multiple gateways, it also propagates this information to its other neighbors.

Each entry in the advertised BGP table has a number of fields. The two most important ones are

• AS-PATH - a list of the ASs through which the advertisement has passed. When a prefix is passed to an AS, that AS adds its path. This is used to detect and prevent looping. If a router sees that its AS is contained in the path list, it discards the advertisement.
• NEXT-HOP A pair of ASs may have multiple physical links that directly connect them. When a gateway advertises, it includes its own IP. One AS may receive multiple routes with the same prefix, each passing through a different next hop router.

Routers may receive several routes to the same subnet. A router can determine which one to used based on its own policies. These may be purely practical (use the shortest path) involve political considerations (This route goes through our competitor, don't use it).

There are some general Internet policies. Since all backbone ASs are connected to every other backbone AS, all packets processed by a particular AS should have either a source or destination network that is a customer of the AS.

All traffic entering a stub network must be destined for that network (even if it has links to other backbone ASS) and all traffic leaving that network must have originated in that network. network.

BGP does not provide distance metrics, only reachability. Thus, BGP does not necessarily provide optimal routing.

IPv6

IP version 4 has been in use since 1983, and it has worked well, but there are plans to upgrade it. The next version is IP version 6, (IPv6 or IPng for next generation). The major reason why this upgrade is occurring is that we are running out of IPv4 addresses, but there are other motivations as well. IPv6 will provide better mechanisms for authentication and other security issues, and it will make routing easier.

The basic concept of packet switching is unchanged. The IP is still connectionless and unreliable. Here are some of the changes

• The most obvious is that the size of the IP address is expanded from the current 32 bits to 128 bits. This is obviously overkill if the goal is simply to get more IP addresses. Every man, woman, and child on the planet can be assigned their own block of 4 billion IP addresses; allowing them to assign an IP address to their refrigerator, their toaster and other household appliances with plenty left over for other purposes.
• There is a more flexible header. Every IPv6 packet has a 40 byte fixed size header. This is followed by a linked list of additional headers

• Version (4 bits) always 6
• Traffic class (8 bits) (like Type of Service)
• Flow label (20 bits) used to identify a flow of datagrams, i.e all the messages associated with a particular telephone conversation.
• payload length (16 bits) In bytes, so max payload size is 64K bytes
• next header (8 bits) the type of the next header
• hop limit (8 bits) - like ttl
• Source address (128 bits)
• Destination address (128 bits)

No header checksum (not needed since the link layer and the transport layers typically perform this)

The headers form a linked list. The type of the next header is shown in the next header field.

Some of the headers which are currently implemented are Route Information, and Security Information.

There has been extensive discussion of how to implement this. Clearly there cannot be a simple switch-over day like there was when TCP/IP was introduced in 1983. There are two possibilities: The first is that most routers would implement a dual stack for a while; that is, they would be able to process both IPv4 and IPv6 packets. The second possibility is tunneling. If an IPv6 packet arrives at a router which only uses IPv4 (or the reverse), the router can treat the entire packet, including the IPv6 header(s) as the payload and construct one or more IPv4 packets, which it forwards. When these packets get to the end of the IPv4 network (often just a single hop), the IPv4 header is stripped off and the IPv6 packet is sent on its way.

Required Reading:
Cisco's description of RIP
Cisco's description of OSPF. You are only required to read up to the section entitled Link-State Packets.

Here is the Wikipedia entry on BGP

There is not much good material on IPv6. Here is the Wikipedia description of IPv6