Communication Networks/Routing

Routing

Routing is the process of getting information packets where they need to go. Routing is a surprisingly complicated task, and there are a number of different algorithms used to find the shortest route between two points.

Introduction

IP addressing is based on the concept of hosts and networks. A host is essentially anything on the network that is capable of receiving and transmitting IP packets on the network, such as a workstation or a router. Routing is a process of moving data from one host computer to another. The difference between routing and bridging is that bridging occurs at Layer 2 (the link layer) of the OSI reference model, whereas routing occurs at Layer 3 (the network layer). Routing determines the optimal routing paths through a network.

To do:
Introduce Routing Tables

Routing Algorithms

The routing algorithm is stored in the router's memory. The routing algorithm is a major factor in the performance of your routing environment. The purpose of the routing algorithm is to make decisions for the router concerning the best paths for data. The router uses the routing algorithm to compute the path that would best serve to transport the data from the source to the destination. Note that you do not directly choose the algorithm that your router uses. Rather, the routing protocol you choose for your network determines which algorithm you will use. For example, whereas the routing protocol Routing Information Protocol (RIP) may use one type of routing algorithm to help the router move data, the routing protocol Open Shortest Path First (OSPF) uses another. The routing algorithm cannot be changed. The only way to change it is to change routing protocols. The overall performance of your network depends mainly on the routing algorithm, so you should research the algorithms each protocol uses before deciding which to implement on your network. There are two major categories of routing algorithms - distance vector or link-state. Every routing protocol named "distance vector" uses the distance vector algorithm, and every link-state protocol uses the link-state algorithm.

To do:
See if Bellman-Ford Algorithm gets mentioned

Routing Algorithms within Routing Protocols

One of the jobs of the routing protocol is to provide the information needed by the routing algorithm to compute its decisions. This is the point where many protocols differ. The information provided to the algorithm can be different from protocol to protocol.

The routing protocol gathers information about networks and routers from the surrounding environment and stores the information within a routing table in the router's memory. The routing algorithm is run using the information within this table to calculate the best path from one network to another. Calculating the new values within the formula then generates a sum. The result of this calculation is used then to determine where to send information. For example, the table below illustrates a sample routing table for a fictitious routing environment. The information that is passed to the routing algorithm within the routing table is gathered by the routing protocol through a process known as a routing update. Through a series of updates, each router will tell the other what information it has. Eventually, an entire routing table will be built.

Router Link	Metric
Router A to Router B	2
Router B to Router C	3
Router A to Router C	6
Router C to Router D	5

The sample routing algorithm states that the best path to any destination is the one that has the lowest metric value. A metric is a number that is used as a standard of measurement for the links of a network. Each link is assigned a metric to represent anything from monetary cost to use the line, to the amount of available bandwidth. When Router A is presented with a packet bound from Router C, the routing table shows two possible paths to choose from. The first choice is to send the packet from Router A directly over the link to Router C. The second option is to send the packet from Router A to Router B and then on to Router C. The routing algorithm is used to determine which option is best.

Some routing protocols might only provide one metric to the routing algorithm, whereas others might provide up to ten. On the other hand, whereas two protocols might both send only one metric to the algorithm, the origin of that metric might differ from protocol to protocol. One routing protocol might give an algorithm the single metric of cost, but that cost could represent something different than another protocol using the same metric.

The algorithm in our example states that the best path is the one with the lowest metric value. Therefore, by adding the metric numbers associated with each possible link, we see that the route from Router A to Router B to Router C has a metric value of 5, while the direct link to Router C has a value of 6. The algorithm selects the A-B-C path and sends the information along.

To do:
Cover Hop-by-Hop Routing

Distance Vector Algorithms

A distance vector algorithm uses metrics known as costs in order to help determine the best path to a destination. The path with the lowest total cost is chosen as the best path.

When a router utilizes a distance vector algorithm, different costs are gathered by each router. These costs can be completely arbitrary numbers. Costs can also be dynamically gathered values, such as the amount of delay experienced by routers when sending packets over one link as opposed to another. All the costs are compiled and placed within the router's routing table and then they are used by the algorithm to calculate a best path for any given network scenario.

Although there are many resources that will offer complex mathematical representations of what distance vector algorithms are and how they compute their decisions, the core concept remains the same - by adding the metrics for every optional path on a network, you will come up with at least one best path. The formula for this is as follows:

M(i,k) = min [M(i,t) + M(t,k)]

This formula states that the best path between two networks (M(i,k)) can be found by finding the lowest (min) value of paths between all network points. Let's look again at the routing information in the table above. Plugging this information into the formula, we see that the route from A to B to C is still the best path:

5(A,C) = min[2(A,B) + 3(B,C)]

Whereas the formula for the direct route A to C looks like this:

6(A,C) = min[6(A,C)]

This example shows how distance vector algorithms use the information passed to them to make informed routing decisions. The algorithms used by routers and routing protocols are not configurable, nor can they be modified.

Another major difference between distance vector algorithms and link state protocols is that when distance vector routing protocols update each other, all or part of the routing table (depending on the type of update) is sent from one router to another. By this process, each router is exposed to the information contained within the other router's tables, thus giving each router a more complete view of the networking environment and enabling them to make better routing decisions. Examples of distance vector algorithms include RIP and BGP, two of the more popular protocols in use today. Other popular protocols such as OSPF are examples of protocols which use the link state routing algorithm.

Distance vector algorithms are also known as Bellman-Ford routing algorithms and Ford-Fulkerson routing algorithms. In these algorithms, each router has a routing table which shows it the best route for any destination. A typical graph and routing table for router J is shown below.

Destination	Weight	Line
A	8	A
B	20	A
C	20	I
D	20	H
E	17	I
F	30	I
G	18	H
H	12	H
I	10	I
J	0	N/A
K	6	K
L	15	K

The table shows that if router J wants to get packets to router D, it should send them to router H first. When the packets arrive at router H, the current router checks its own table and makes a decision how to send the packets to D. In distance vector algorithms, each router has to follow the following steps:

1. It counts the weight of the links directly connected to it and saves the information to its table.

2. In a particular period of time, the router sends its table to its neighbor routers (not to all routers) and receives the routing table of each of its neighbors.

3. Based on the information the router receives from its neighbors' routing tables, it updates its own.

Let's consider one more example (the figure represented below).

The cost of each link is set to 1. Thus, the least cost path is simply the path with the fewer hops. The table below represents each node knowledge about the distance to all other nodes:

Information stored at node	Distance to reach node
Information stored at node	A	B	C	D	E	F	G
A	0	1	1	$\infty$	1	1	$\infty$
B	1	0	1	$\infty$	$\infty$	$\infty$	$\infty$
C	1	1	0	1	$\infty$	$\infty$	$\infty$
D	$\infty$	$\infty$	1	0	$\infty$	$\infty$	1
E	1	$\infty$	$\infty$	$\infty$	0	$\infty$	$\infty$
F	1	$\infty$	$\infty$	$\infty$	$\infty$	0	1
G	$\infty$	$\infty$	$\infty$	1	$\infty$	1	0

Initially, each node sets a cost of 1 to its directly connected neighbors and infinity to all the other nodes. Below is shown the initial routing table at node A:

Destination	Cost	Next Hop
B	1	B
C	1	C
D	$\infty$	-
E	1	E
F	1	F
G	$\infty$	-

During the next step, every node sends a message to its directly connected neighbors. That message contains the node's personal list of distances. Node F, for example, tells node A that it can reach node G at cost of 1; node A also knows that it can reach F at a cost of 1, so it adds these costs to get the cost of reaching G by means of F. Because 2 is less than the current cost of infinity, node A records that it can reach G at a cost of 2 by going trough F. Node A learns from C that node B can be reached from C at a cost of 1, so it concludes that the cost of reaching B via C is 2. Because this is worse than the current cost of reaching B, which is 1, the new information is ignored. The final routing table at node A is shown below:

Destination	Cost	Next Hop
B	1	B
C	1	C
D	2	C
E	1	E
F	1	F
G	2	F

The process of getting consistent routing information to all the nodes is called convergence. The final set of costs from each node to all other nodes is shown in the table below:

Information stored at node	Distance to reach node
Information stored at node	A	B	C	D	E	F	G
A	0	1	1	2	1	1	2
B	1	0	1	2	2	2	3
C	1	1	0	1	2	2	2
D	2	2	1	0	3	2	1
E	1	2	2	3	0	2	3
F	1	2	2	2	2	0	1
G	2	3	2	1	3	1	0

The cost of each link is set to 1. Thus, the least cost path is simply the path with the fewer hops.

One of the problems with distance vector algorithms is called "count to infinity." Let's examine the following problem with an example:

Consider a network with a graph as shown below. There is only one link between D and the other parts of the network.

with vectors

d [A][A] = 0 d [A][B] = 1 d [A][C] = 2 d [A][D] = 3

	A	B	C	D
A	0	1	2	3
B	1	0	1	2
C	2	1	0	1
D	3	2	1	0

Now the C to D link crashes So cost [C][D] = ∞ C used to forward any packets with address D directly on the CD link, but now link is down, so C has to recompute its distance vector (and make a new choice of how to forward packets to D) - similarly D has to update its vector. After updating their vectors at C and D, we have

	A	B	C	D
A	0	1	2	3
B	1	0	1	2
C	2	1	0	3
D	$\infty$	$\infty$	$\infty$	0

C views B as the best route to D, with cost 1 + 2, so C sends new vector to B. B learns that its former choice for sending to D via C now has higher cost, so B should recompute its vector.

	A	B	C	D
A	0	1	2	3
B	1	0	1	4
C	2	1	0	3
D	$\infty$	$\infty$	$\infty$	0

View of B is that routing to D can either go via A or C with equal cost - B sends updated vector. Both A and C get updated vector from B and learn that their preferred route to D now has higher cost, so they recompute their own vectors.

	A	B	C	D
A	0	1	2	5
B	1	0	1	4
C	2	1	0	5
D	$\infty$	$\infty$	$\infty$	0

Then A and C send their vectors, B has to update its vector again, sending another round to A and C, obtaining.

	A	B	C	D
A	0	1	2	7
B	1	0	1	6
C	2	1	0	7
D	$\infty$	$\infty$	$\infty$	0

Notice that the routing table is very slowly converging to the fact that

d [x][D] = ∞ for x = A or x = B or x = C

This process loops until all nodes find out that the weight of link to D is infinity. In this way, experts say that distance vector algorithms have a slow convergence rate. In conclusion, distance vector algorithm is not robust. One way to solve this problem is for routers to send information only to the neighbors that are not exclusive links to the destination. For example, in this case, B should not send any information to C about D, because C is the only way to D.

Link-State Algorithms

Distance vector algorithms and link-state algorithms both favor the path with the lowest cost. However, link-state protocols work in more localized manner. Whereas a router running a distance vector algorithm will compute the end-to-end path for any given packet, a link-state protocol will compute that path as it relates to the most immediate link. That is, where a distance vector algorithm will compute the lowest metric between Network A and Network C, a link-state protocol will compute it as two distinct paths, A to B and B to C. This process is very efficient for larger environments. Link-state algorithms enable routers to focus on their own links and interfaces. Any one router on a network will only have direct knowledge of the routers and networks that are directly connected to it (or, the state of its own links). In larger environments, this means that the router will use less processing power to compute complicated paths. The router simply needs to know which one of its direct interfaces will get the information where it needs to go the quickest. The next router in line will repeat the process until the information reaches its destination. Another advantage to such localized routing processes is that protocols can maintain smaller routing tables. Because a link-state protocol only maintains routing information for its direct interfaces, the routing table contains much less information than that of a distance vector protocol that might have information for multiple routers. Like distance vector protocols, link-state protocols require updates to share information with each other. These routing updates, known as Link State Advertisements (LSAs), occur when the state of a router's links changes. When a particular link becomes unavailable (changes state), the router sends an update through the environment alerting all the routers with which it is directly linked.

In Link-State Algorithms, every router has to follow these steps:

1. Identify the routers that are physically connected to them and get their IP addresses When a router starts working, it first sends a "HELLO" packet over network. Each router that receives this packet replies with a message that contains its IP address.

2. Routers measure the delay time (or any other important parameters of the network, such as average traffic) for neighbor routers. In order to do that, routers send echo packets over the network. Every router that receives these packets replies with an echo reply packet. By dividing round trip time by 2, routers can count the delay time. The delay time includes both transmission and processing times - the time it takes the packets to reach the destination and the time it takes the receiver to process it and reply.

3. Broadcast its information over the network for other routers and receive the other routers' information. In this step, all routers share their knowledge and broadcast their information to each other. In this way, every router can know the structure and status of the network.

4. Routers use an appropriate algorithm to identify the best route between two nodes of the network. In this step, routers choose the best route to every node. They do this using an algorithm, such as the Dijkstra shortest path algorithm. In this algorithm, a router, based on information that has been collected from other routers, builds a graph of the network. This graph shows the location of routers in the network and their links to each other. Every link is labeled with a number called the weight or cost. This number is a function of delay time, average traffic, and sometimes simply the number of hops between nodes. For example, if there are two links between a node and a destination, the router chooses the link with the lowest weight.

Dijkstra algorithm

The Dijkstra algorithm goes through the following steps:

The router builds a graph of the network. Then it identifies source and destination nodes, for example R1 and R2. The router builds then a matrix, called the "adjacency matrix." In the adjacent matrix, a coordinate indicates weight. [i, j], for example, is the weight of a link between nodes Ri and Rj. If there is no direct link between Ri and Rj, this weight is identified as "infinity."
The router then builds a status record for each node on the network. The record contains the following fields:
- Predecessor field - shows the previous node.
- Length field - shows the sum of the weights from the source to that node.
- Label field - shows the status of node; each node have one status mode: "permanent" or "tentative."
In the next step, the router initializes the parameters of the status record (for all nodes) and sets their label to "tentative" and their length to "infinity".
During this step, the router sets a T-node. If R1 is to be the source T-node, for example, the router changes R1's label to "permanent." Once a label is changed to "permanent," it never changes again.
The router updates the status record for all tentative nodes that are directly linked to the source T-node.
The router goes over all of the tentative nodes and chooses the one whose weight to R1 is lowest. That node is then the destination T-node.
If the new T-node is not R2 (the intended destination), the router goes back to step 5.
If this node is R2, the router extracts its previous node from the status record and does this until it arrives at R1. This list of nodes shows the best route from R1 to R2.

Dijkstra algorithm example:

Let’s find the best route between routers A and E. There are six possible routes between them (ABE, ACE, ABDE, ACDE, ABDCE, ACDBE), and it's obvious that ABDE is the best route because its weight is the lowest. But life is not always so easy, and there are some complicated cases in which we have to use algorithms to find the best route.

1. The source node (A) has been chosen as T-node, and so its label is permanent (permanent nodes are showed with filled circles and T-nodes with the -> symbol).

2. In this step, the status record of tentative nodes directly linked to T-node (B, C) has been changed. Also, because B has less weight, it has been chosen as T-node and its label has changed to permanent.

3. Like in step 2, the status records of tentative nodes that have a direct link to T-node (D, E), have been changed. Because router D has less weight, it has been chosen as T-node and its label has changed to permanent.

4. Because we do not have any tentative nodes, we just identify the next T-node. Because node E has the least weight, it has been chosen as T-node.

Now we have to identify the route. The previous node of E is node D, and the previous node of D is node B, and B's previous node is node A. So, we determine that the best route is ABDE. In this case, the total weigh is 4 (1+2+1). This algorithm works well, but it is so complicated that it may take a long time for routers to process it. That would cause the efficiency of the network to fail. Another note we should make here is that if a router gives the wrong information to other routers, all routing decisions will be ineffective.

The next example shows how to find the best routes among all the nodes in a network. The example uses the Shortest Path Dijkstra algorithm. Consider the network shown below:

Let's use the Dijkstra's algorithm to find the routes that A will use to transmit to any of the notes on the network. The Dijkstra's routing algorithm is represented in the following table:

		B	C	D	E	F	G	H	I
Step 1	A	2-A	3-A	5-A	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
Step 2	AB		3-A	5-A	7-B	9-B	$\infty$	$\infty$	$\infty$
Step 3	ABC			4-C	4-C	9-B	$\infty$	$\infty$	$\infty$
Step 4	ABCD				4-C	9-B	$\infty$	11-D	$\infty$
Step 5	ABCDE					8-E	12-E	7-E	$\infty$
Step 6	ABCDEH					8-E	12-E		11-H
Step 7	ABCDEHF						10-F		11-H
Step 8	ABCDEHFG								11-H
Step 9	ABCDEHFGI

This is how the network looks after all the updates, showing the shortest route among the nodes:

Interior Routing

Packet routing in the Internet is divided into two general groups: interior and exterior routing. Interior routing happens inside or interior to an independent network system. In TCP/IP terminology, these independent network systems are called autonomous systems. Within an autonomous system (AS), routing information is exchanged using an interior routing protocol chosen by the autonomous system's administration. The exterior routing protocols, on the other hand are used between the autonomous systems. Interior routing protocols determine the "best" route to each destination, and they distribute routing information among the systems on a network. There are several interior protocols:

- The Routing Information Protocol (RIP) is the interior protocol most commonly used on UNIX systems. RIP uses distance vector algorithm that selects the route with the lowest "hop count" (metric) as the best route. The RIP hop count represents the number of gateways through which data must pass to reach its destination. RIP assumes that the best route is the one that uses the fewest gateways.

- Hello is a protocol that uses delay as the deciding factor when choosing the best route. Delay is the length of time it takes a datagram to make the round trip between its source and destination.

- Intermediate System to Intermediate System (IS-IS) is an interior routing protocol from the OSI protocol suite. It is a link-state protocol. It was the interior routing protocol used on the T1 NSFNET backbone.

- Open Shortest Path First (OSPF) is another link-state protocol developed for TCP/IP. It is suitable for very large networks and provides several advantages over RIP.

Routing Information Protocol (RIP)

RIP (Routing Information Protocol) is a standard for exchange of routing information among gateways and hosts. It is a distance-vector protocol. RIP is most useful as an "interior gateway protocol". The network is organized as a collection of "autonomous systems". Each autonomous system has its own routing technology, which may well be different for different autonomous systems. The routing protocol used within an autonomous system is referred to as an interior gateway protocol, or "IGP". Routing Information Protocol (RIP) is designed to work with moderate-size networks using reasonably homogeneous technology. Thus, it is suitable as an Interior Gateway Protocol (IGP) for many campuses and for regional networks using serial lines whose speeds do not vary widely. It is not intended for use in more complex environments. RIP2 derives from RIP, which is an extension of the Routing Information Protocol (RIP) intended to expand the amount of useful information carried in the RIP messages and to add a measure of security. RIP2 is an UDP-based protocol.

What makes RIP work is a routing database that stores information on the fastest route from computer to computer, an update process that enables each router to tell other routers which route is the fastest from its point of view, and an update algorithm that enables each router to update its database with the fastest route communicated from neighboring routers:

Database - Each RIP router on a given network keeps a database that stores the following information for every computer in that network:

IP Address - The Internet Protocol address of the computer.

Gateway - The best gateway to send a message addressed to that IP address.

Distance - The number of routers between this router and the router that can send the message directly to that IP address.

Route change flag - A flag that indicates that this information has changed, used by other routers to update their own databases.

Timers - Various timers.

Algorithm - The RIP algorithm works like this:

Update - At regular intervals each router sends an update message describing its routing database to all the other routers that it is directly connected to. Some routers will send this message as often as every 30 seconds, so that the network will always have up-to-date information to quickly adapt to changes as computers and routers come on and off the network. The Protocol Structure for RIP & and RIP2 is shown in the figure below:

The Protocol Structure for RIP & and RIP2 is shown in the figure below:

8 bits	16 bits	32 bits
Command	Version	Unused
Address Family Identifier		Route Tag (only for RIP2; 0 for RIP)
IP Address
Subnet Mask (only for RIP2; 0 for RIP)
Next Hop (only for RIP2; 0 for RIP)
Metric

Command - The command field is used to specify the purpose of the datagram. There are five commands: Request, Response, Traceon (obsolete), Traceoff (obsolete) and Reserved.

Version - The RIP version number. The current version is 2.

Address family identifier - Indicates what type of address is specified in this particular entry. This is used because RIP2 may carry routing information for several different protocols. The address family identifier for IP is 2.

Route tag - Attribute assigned to a route which must be preserved and readvertised with a route. The route tag provides a method of separating internal RIP routes (routes for networks within the RIP routing domain) from external RIP routes, which may have been imported from an EGP or another IGP.

IP address - The destination IP address.

Subnet mask - Value applied to the IP address to yield the non-host portion of the address. If zero, then no subnet mask has been included for this entry.

Next hop - Immediate next hop IP address to which packets to the destination specified by this route entry should be forwarded.

Metric - Represents the total cost of getting a datagram from the host to that destination. This metric is the sum of the costs associated with the networks that would be traversed in getting to the destination.

Open Shortest Path First Protocol (OSPF)

OSPF is an interior gateway protocol used for between routers that belong to a single Autonomous System. OSPF uses link-state technology in which routers send each other information about the direct connections and links which they have to other routers. Each OSPF router maintains an identical database describing the Autonomous System’s topology. From this database, a routing table is calculated by constructing a shortest- path tree. OSPF recalculates routes quickly in the face of topological changes, utilizing a minimum of routing protocol traffic. An area routing capability is provided, enabling an additional level of routing protection and a reduction in routing protocol traffic. In addition, all OSPF routing protocol exchanges are authenticated. OSPF routes IP packets based solely on the destination IP address found in the IP packet header. IP packets are routed "as is" - they are not encapsulated in any further protocol headers as they transit the Autonomous System. OSPF allows sets of networks to be grouped together. Such a grouping is called an area. The topology of an area is hidden from the rest of the Autonomous System. This information hiding enables a significant reduction in routing traffic. Also, routing within the area is determined only by the area’s own topology, lending the area protection from bad routing data.

The OSPF algorithm works as described below:

Startup - When a router is turned on it sends Hello packets to all of its neighbors, receives their Hello packets in return, and establishes routing connections by synchronizing databases with adjacent routers that agree to synchronize.

Update - At regular intervals each router sends an update message called its "link state" describing its routing database to all the other routers, so that all routers have the same description of the topology of the local network.

Shortest path tree - Each router then calculates a mathematical data structure called a "shortest path tree" that describes the shortest path to each destination address and therefore indicates the closest router to send to for each communication; in other words - "open shortest path first".

The Protocol Structure of OSPF (Open Shortest Path First version 2) is shown below:

8 bits	16 bits	24 bits
Version No.	Packet Type	Packet Length
Router ID
Area ID
Checksum		AuType
Authentication

Version number - Protocol version number (currently 2).

Packet type - Valid types are as follows: 1 Hello 2 Database Description 3 Link State Request 4 Link State Update 5 Link State Acknowledgment.

Packet length - The length of the protocol packet in bytes. This length includes the standard OSPF header.

Router ID - The router ID of the packet’s source. In OSPF, the source and destination of a routing protocol packet are the two ends of an (potential) adjacency.

Area ID - identifying the area that this packet belongs to. All OSPF packets are associated with a single area. Most travel a single hop only.

Checksum - The standard IP checksum of the entire contents of the packet, starting with the OSPF packet header but excluding the 64-bit authentication field.

AuType - Identifies the authentication scheme to be used for the packet.

Authentication - A 64-bit field for use by the authentication scheme.

Intermediate System to Intermediate System Routing Protocol(IS-IS)

Intermediate System-to-Intermediate System (IS-IS) is a link-state protocol where IS (routers) exchange routing information based on a single metric to determine network topology. It behaves similar to Open Shortest Path First (OSPF) in the TCP/IP network. In an IS-IS network, there are End Systems, Intermediate Systems, Areas and Domains. End systems are user devices. Intermediate systems are routers. Routers are organized into local groups called "areas", and several areas are grouped together into a "domain". IS-IS is designed primarily providing intra-domain routing or routing within an area. IS-IS, working in conjunction with CLNP, ES-IS, and IDRP, provides complete routing over the entire network. IS-IS routing makes use of two-level hierarchical routing. Level 1 - routers know the topology in their area, including all routers and hosts, but they do not know the identity of routers or destinations outside of their area. Level 1 routers forward all traffic for destinations outside of their area to a level 2 router within their area which knows the level 2 topology. Level 2 routers do not need to know the topology within any level 1 area, except to the extent that a level 2 router may also be a level 1 router within a single area. IS-IS has been adapted to carry IP network information, which is called Integrated IS-IS. Integrated IS-IS has the most important characteristic necessary in a modern routing protocol: It supports VLSM and converges rapidly. It is also scalable to support very large networks. There are two types of IS-IS addresses: Network Service Access Point (NSAP) - NSAP addresses identify network layer services, one for each service running. Network Entity Title (NET) - NET addresses identify network layer entities or processes instead of services. Devices may have more than one of each of the two types of addresses. However NET’s should be unique and the System ID portion of the NSAP must be unique for each system. The Protocol Structure of IS-IS (Intermediate System to Intermediate System Routing Protocol) is shown below:

8 bits				16 bits
Intradomain routing protocol discriminator				Length Indicator
Version/Protocol ID Extension				ID Length
R	R	R	PDU Type	Version
Reserved				Maximum Area Address

Intra-domain routing protocol discriminator - Network layer protocol identifier assigned to this protocol

Length indicator - Length of the fixed header in octets.

Version/protocol ID extension - Equal to 1.

ID length - Length of the ID field of NSAP addresses and NETs used in this routing domain.

R - Reserved bits.

PDU type - Type of PDU. Bits 6, 7 and 8 are reserved.

Version - Equal to 1.

Maximum area addresses - Number of area addresses permitted for this intermediate systems area.

The format of NSAP for IS-IS is shown below:

<-IDP->		<-DSP->
		<-HO-DSP->
AFI	IDI	Contents assigned by authority identified in IDI field
<-Area Address->			<-ID->	<-SEL->

IDP - Initial Domain Part

AFI - Authority and Format Identifier (1-byte); Provides information about the structure and content of the IDI and DSP fields.

IDI - Initial Domain Identifier (variable length)

DSP - Domain Specific Part

HO-DSP - High Order Domain Specific Part

Area Address (variable)

ID - System ID 1- 8 bytes

SEL - n-selector (1-byte value that serves a function similar to the port number in Internet Protocol).

Exterior Routing

Exterior routing occurs between autonomous systems, and is of concern to service providers and other large or complex networks. The basic routable element is the Autonomous System.While there may be many different interior routing scheme, a single exterior routing system manages the global Internet, based primarily on the BGP-4 exterior routing protocol.

Border Gateway Protocol (BGP)

The Border Gateway Protocol (BGP) ensures that packets get to their destination network regardless of current network conditions. BGP is essentially a distance-vector algorithm, but with several added twists. First, BGP router establishes connections with the other BGP routers with which it directly communicates. The first thing it does is download the entire routing table of each neighboring router. After that it only exchanges much shorter update messages with other routers. BGP routers send and receive update messages to indicate a change in the preferred path to reach a computer with a given IP address. If the router decides to update its own routing tables because this new path is better, then it will subsequently propagate this information to all of the other neighboring BGP routers to which it is connected, and they will in turn decide whether to update their own tables and propagate the information further.

BGP uses the TCP/IP protocol on port 179 to establish connections. It has strong security features, including the incorporation of a digital signature in all communications between BGP routers. Each BGP router contains a Routing Information Base (RIB) that contains the routing information maintained by that router. The RIB contains three types of information:

Adj-RIBs-In - The unedited routing information sent by neighboring routers.
Loc-RIB - The actual routing information the router uses, developed from Adj-RIBs-In.
Adj-RIBs-Out - The information the router chooses to send to neighboring routers.

BGP routers exchange information using four types of messages:

Open - Used to open an initial connection with a neighboring router.
Update - These messages do most of the work, exchanging routing information between neighboring routers, and contain one of the following pieces of information:
- Withdrawn routes - The IP addresses of computers that the router no longer can route messages to.
- Paths - A new preferred route for an IP address. This path consists of two pieces of information - the IP address, and the address of the next router in the path that is used to route messages destined for that address.
Notification - Used to indicate errors, such as an incorrect or unreadable message received, and are followed by an immediate close of the connection with the neighboring router.
Keepalive - Each BGP router sends a 19 byte Keepalive message to each neighboring router to let them know that it is still operational about every 30 seconds, and no more often than every three seconds. If any router does not receive a Keepalive message from a neighboring router within a set amount of time, it closes its connection with that router, and removes it from its Routing Information Base, repairing what it perceives as damage to the network.

Routing messages are the highest precedence traffic on the Internet, and each BGP router gives them first priority over all other traffic. This makes sense - if routing information can't make it through, then nothing else will.

The BGP algorithm is run after a BGP router receives an update message from a neighboring router, and consists of the following three steps performed for each IP address sent from the neighbor:

Update - If the path information for an IP address in the update message is different from the information previously received from that router, then the Adj-RIBs-In database is updated with the newest information.
Decision - If it was new information, then a decision process is run that determines which BGP router, of all those presently recorded in the Adj-RIBs-In database, has the best routing path for the IP address in the update message. The algorithm is not mandated, and BGP administrators can set local policy criteria for the decision process such as how long it takes to communicate with each neighboring router, and how long each neighboring router takes to communicate with the next router in the path. If the best path chosen as a result of this decision process is different from the one currently recorded in the Loc-RIB database, then the database is updated.
Propagation - If the decision process found a better path, then the Adj-RIBs-Out database is updated as well, and the router sends out update messages to all of its neighboring BGP routers to tell them about the better path. Each neighboring router then runs their own BGP algorithm in turn, decides whether or not to update their routing databases, and then propagates any new and improved paths to neighboring routers in turn.

One of the other important functions performed by the BGP algorithm is to eliminate loops from routing information. For example, a routing loop would occur when router A thinks that router B has the best path to send messages for some computer and B thinks the best path is through C, but C thinks the best path is back through A. If these sort of routing loops were allowed to happen, then any message to that computer that passed through routers A, B, or C would circulate among them forever, failing to deliver the message and using up increasing amounts of network resources. The BGP algorithm traps and stops any such loops.

Hierarchical Routing

In both Link-State and Distance Vector algorithms, every router has to save some information about other routers. When the network size grows, the number of routers in the network increases. As a result, the size of routing tables increases, as well, and routers can not handle network traffic as efficiently. Hierarchical routing are used to overcome this problem. Let us examine an example:

Distance Vector algorithms algorithms are used to find best routes between nodes. In the situation depicted below, every node of the network has to save a routing table with 17 records.

Here is a typical graph and routing table for A:

Destination	Line	Weight
A	N/A	N/A
B	B	1
C	C	1
D	B	2
E	B	3
F	B	3
G	B	4
H	B	5
I	C	5
J	C	6
K	C	5
L	C	4
M	C	4
N	C	3
O	C	4
P	C	2
Q	C	3

In hierarchical routing, routers are classified in groups known as regions. Each router has only the information about the routers in its own region and has no information about routers in other regions. That way, routers just save one record in their table for every other region. In this example, we have classified our network into five regions (see below).

Destination	Line	Weight
A	N/A	N/A
B	B	1
C	C	1
Region 2	B	2
Region 3	C	4
Region 4	C	3
Region 5	C	2

If A wants to send packets to any router in region 2 (D, E, F or G), it sends them to B, and so on. As you can see, in this type of routing, the tables can be summarized, so network efficiency improves. The above example shows two-level hierarchical routing. We can also use three-level or four-level hierarchical routing. In three-level hierarchical routing, the network is classified into a number of clusters. Each cluster is made up of a number of regions, and each region contains a number or routers. Hierarchical routing is widely used in Internet routing and makes use of several routing protocols.

Summary

In Distance Vector Algorithms send everything you know to your neighbors, since Link-State Algorithms send info about your neighbors to everyone.

The Message size is small with Link-State Algorithms, and it is potentially large with Distance Vector Algorithms

The message exchange is large in Link-State Algorithms, while in Distance Vector Algorithms, the exchangement is only to neighbors

Convergence speed:

– Link-State Algorithms: fast

– Distance Vector Algorithms: fast with triggered updates

Space requirements:

– Link-State Algorithms maintains entire topology

– Distance Vector Algorithms maintains only neighbor state

Robustness:

• Link-State Algorithms can broadcast incorrect/corrupted LSP – localized problem

• Distance Vector Algorithms can advertise incorrect paths to all destinations – incorrect calculation can spread to entire network

Exercises

1. For the network given below, give global distance-vector tables when

a) each node knows only the distances to its immediate neighbors

b) each node has reported the information it had in the preceding step to its immediate neighbors

c) step b) happens a second time

2. For the network in exercise 1, show how the link-state algorithm builds the routing vector table for node D.

3. For the network given in the figure below, give global distance-vector tables when

a) each node knows only the distances to its immediate neighbors

b) each node has reported the information it had in the preceding step to its immediate neighbors

c) step b) happens a second time

4. Suppose we have the forwarding tables shown below for nodes A and F, in a network where all links have cost 1. Give a diagram of the smallest network consistent with these tables.

For node A we have:

Node	Cost	Next Hop
B	1	B
C	1	C
D	2	B
E	3	C
F	2	C

For node F we have:

Node	Cost	Next Hop
A	2	C
B	3	C
C	1	C
D	2	C
E	1	E

5. For the network below, find the least cost routes from node A as a source using the Shortest Path Dijkstra's algorithm.

Answers

1.

a)

Information stored at node	Distance to reach node
Information stored at node	A	B	C	D	E	F
A	0	$\infty$	3	8	$\infty$	$\infty$
B	$\infty$	0	$\infty$	$\infty$	2	$\infty$
C	3	$\infty$	0	$\infty$	1	6
D	8	$\infty$	$\infty$	0	2	$\infty$
E	$\infty$	2	1	2	0	$\infty$
F	$\infty$	$\infty$	6	$\infty$	$\infty$	0

b)

c)

Information stored at node	Distance to reach node
Information stored at node	A	B	C	D	E	F
A	0	6	3	6	4	9
B	6	0	3	4	2	9
C	3	3	0	3	1	6
D	6	4	3	0	2	9
E	4	2	1	2	0	7
F	9	9	6	9	7	0

2.

D	Confirmed	Tentative
1.	(D,0,-)
2.	(D,0,-)	(A,8,A) (E,2,E)
3.	(D,0,-) (E,2,E) (C,3,E)	(A,8,A) (B,4,E)
4.	(D,0,-) (E,2,E) (C,3,E)	(A,6,E) (B,4,E) (F,9,E)
5.	(D,0,-) (E,2,E) (C,3,E) (B,4,E)	(A,6,E) (F,9,E)
6.	previous + (A,6,E)
7.	previous + (F,9,E)

3.

a)

Information stored at node	Distance to reach node
Information stored at node	A	B	C	D	E	F
A	0	2	$\infty$	5	$\infty$	$\infty$
B	2	0	2	$\infty$	1	$\infty$
C	$\infty$	2	0	2	$\infty$	3
D	5	$\infty$	2	0	$\infty$	$\infty$
E	$\infty$	1	$\infty$	$\infty$	0	3
F	$\infty$	$\infty$	3	$\infty$	3	0