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 netw

ork, 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 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 termi

nology, 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, a

nd 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 use

s 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 r

outing 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 "IG

P". 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 messag

es 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 stor

es 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 figur

e 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 id

entifier for IP is 2.

Route tag - Attribute assigned to a route which must be p

reserved 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 constructin

g 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 p

ackets based solely on the destination IP address foun

d 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 "l

ink state" describing its routing database to all the other routers, so that all router

s 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 th

erefore 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 belo

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 L

ink 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 pack

et.

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 are

a. 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 (N

SAP) - 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 Add ress

Intradomain 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 us

ed 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 de

stination 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 i

t does is download the entire routing table of each neighboring router. After th

at 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 communication

s 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 sen

t by neighboring route

rs.

- 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 mess

ages:

- Open - Used to open an initial connection with a neighboring router.

- Update - These messages do most of the work, exchanging routing i

nformation between neighboring routers, and contain one of the follow

ing 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 con

sists 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 messag

e to each neighboring router to let them know that it is still ope

rational 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 receive

s an update messa

ge 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 m

essage 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 administra

tors 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 res

ult 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 bette

r 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 BG

P 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 c

omputer 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 Distan

ce Vector algorithms, every router h

as 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 ro

uting 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 depi

cted 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

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

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

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)

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