UNIT 9

Routing Algorithms

9.1 Router

• It is a process of selecting path along which data can be transferred from the source to the destination. Routing can be performed by a special device which is known as a router.
• It works at the network layer in the OSI model and internet layer in TCP/IP model
• It is a networking device that forwards the packet based on the information available and in the packet header and forwarding table.
• The routing algorithms which is used for routing the packets. The routing algorithm is nothing but it is the software responsible for deciding the optimal path through which the packet can be transmitted.
• The routing protocols use the metric which is to determine the best path for the packet delivery. The metric which is the standard of measurement for example hop count, bandwidth, delay, current load on the path, etc. which is used by the routing algorithm to determine the optimal path to destination.
• The routing algorithm initializes and maintains the routing table for the process of path determination.

Types of Routing

Routing can be classified into three categories:

• Static Routing
• Default Routing
• Dynamic Routing

 Static Routing

• Static Routing can also know as Nonadoptive Routing.
• Static Routing is a technique in which the administrator manually adds the routes in a routing table.
• A Router can send the packets for destination along the route which is defined by the administrator.
• In this technique, routing decisions are not made based on the condition or topology of the networks

Advantages of Static Routing

• No Overhead: It has how overhead on the CPU usage of the router. Therefore, cheaper router can be used to obtain static routing.
• Bandwidth: It has no bandwidth usage between the routers.
• Security: It provides security as the system administrator is allowed only to have control over the routing to a particular network.

Disadvantages of Static Routing:

• For a large network, it becomes a very difficult task to add each route manually to routing table.
• The system administrator should be knowledgeable of a topology as he has to add each route manually.

Default Routing

• Default Routing is a technique in which the router which is configured to send all packets to the same hop device, and it does not matter whether it belong to a particular network or not. The Packet is transmitted to the device for which it is configured in default routing.
• It is used when networks deal with the single exit point.
• Default routing is also useful when bulk of transmission networks have to transmit the data to the same hop device.
• When a specific route is mentioned in the routing table, the router will choose the specific route rather than the default route. The default route is chosen only when a specific route is not mentioned in the routing table.

Dynamic Routing

• Dynamic routing is also known as Adaptive Routing.
• Dynamic routing is a technique in which a router adds a new route in the routing table for each packet in response to the changes in the condition or topology of the network.
• Dynamic protocols are used to discover the new routes to reach the destination.
• In Dynamic Routing, RIP and OSPF are the protocols used to discover the new routes.
• If any route goes down, then automatic adjustment will be made to reach destination.

The Dynamic protocol should have the following features:

• All routers must have same dynamic routing protocol in order to exchange routes.
• If router discovers any change in the condition or topology, then router broadcast this information to all other routers.

Advantages of Dynamic Routing:

• Easy to configure.
• More effective in selecting the best route in response to the changes in the condition or topology.

Disadvantages of Dynamic Routing:

• It is expensive in terms of CPU and bandwidth usage.
• Less secure as compared to default and static routing.

9.2 Distance Vector Routing Algorithm

A distance-vector routing (DVR) protocol is that it requires that a router should inform its neighbours of topology changes takes place periodically. Historically it is known as the old ARPANET routing algorithm (or it is also known as Bellman-Ford algorithm).

Bellman Ford Basics – Each router maintains its Distance Vector table which are containing the distance between itself and all possible destination nodes. Distances is based on a chosen metric and are computed using information from the neighbours’ distance vectors.

Information which are kept by DV router -

• Each router has its own ID
• IT is associated with each link that are connected to a router,
• There is a cost of the link (static or dynamic).
• Intermediate hops

Distance Vector Table Initialization -

• Distance to itself = 0
• Distance to all other routers = infinity number.

Distance Vector Algorithm –

1. A router transmits its distance vector to that of each of its neighbours in that of a routing packet.
2. Each router receives and then saves the most recently received distance vector from each of its neighbours.
3. A router recalculates its distance vector when the following happens:
   • It receives a distance vector from that of its neighbour containing different information than before.
   • It discovers that a link to a neighbour has slow down.

The DV calculation is based on minimizing the cost to each destination

Dx(y) = Estimate of least cost from x to y

C(x,v) =  Node x knows cost to each neighbour v

Dx   = [Dx(y): y ∈ N] = Node x maintains distance vector

Node x also maintains its neighbours’ distance vectors

– For each neighbour v, x maintains Dv = [Dv(y): y ∈N ]

Note –

• From time-to-time, each of the node sends its own distance vector which is estimate to its neighbours.
• When a node x receives new DV estimate from any neighbour v, it saves v’s distance vector and it updates its own DV using B-F equation:
• Dx(y) = min { C(x,v) + Dv(y)} for each node y ∈ N

Example – Consider 3-routers X, Y and Z as shown in figure. Each router has their routing table. Every routing table will contain distance to the destination nodes.

Consider router X , X will share it routing table to neighbors and neighbors will share it routing table to it to X and distance from node X to destination will be calculated using bellmen- ford equation.

Dx(y) = min { C(x,v) + Dv(y)} for each node y ∈ N

As we can see that distance will be less going from X to Z when Y is intermediate node(hop) so it will be update in routing table X.

Similarly for Z also –
 

Finally the routing table for all –

Advantages of Distance Vector routing are as follows –

• It is very simple to configure and it maintains link state routing.

Disadvantages of Distance Vector routing are as follows –

• It is very slow to converge than link state.
• It is at high risk from the count-to-infinity problem.
• It creates more traffic than that of link state since a hop count changes must be propagated to all routers and then processed on each router. Hop count updates take place on periodic basis, even if there are no networks changes in the topology, so bandwidth-wasting broadcasts still occur.
• For the very large networks, distance vector routing results in larger routing tables than link state since each router must know also about all of the other routers. This can also lead to congestion on WAN links.

Note – For UDP (User datagram protocol) transportation it uses Distance Vector routing

9.3 Routing Information Protocol (RIP)

Routing Information Protocol (RIP) is dynamic routing protocol which uses a hop count method as a routing metric to find its best path between the source network and the destination network. It is a distance vector routing protocol which has its AD value 120 and works on the application layer of the OSI model. 520 port numbers is used by RIP.

Hop Count:
Hop count is the number of routers which are occurring in between the source and the destination network. The path with that of the lowest hop count is considered to be as the best route to reach a network and therefore it is placed in the routing table. RIP prevents the routing loops by limiting the number of hopes allowed in a path from the source and the destination.15 is the maximum hop count allowed for RIP and hop count of 16 is considered to be as network unreachable.

Features of RIP:

1. Updates of the network are to be exchanged periodically.
2. Updates (routing information) are always to be broadcast.
3. Full routing tables are to be sent in updates.
4. Routers always trust on routing information received from neighbour routers. This is also called routing on rumours.

RIP versions:
There are three visions of routing information protocol – RIP Version1, RIP Version2 and RIPng.

RIP v1is called Classful Routing Protocol because it doesn’t send information of subnet mask in its routing update.
RIP v2 is called Classless Routing Protocol because it sends information of subnet mask in its routing update.

9.4 Link State Routing and OSPF Routing Protocol

Unicast – Unicast is the transmission from single sender to single receiver. It has point to point communication between the sender end and the receivers end. There are various types of unicast protocols for example TCP, HTTP, etc.

• The most commonly used unicast protocol is TCP. It is a connection oriented protocol that will rely on an acknowledgement from that of the receiver side.
• HTTP is Hyper Text Transfer Protocol. It is an object oriented protocol for that of the communication.

Three major protocols for unicast routing are:

1. Distance Vector Routing
2. Link State Routing
3. Path-Vector Routing

Link State Routing –
The second family of routing protocols is Link state routing. While the distance vector routers uses a distributed algorithm to compute to their routing tables and link-state routing uses its link-state routers for the exchanging of messages that allows each of the router to learn the entire of the network topology. Based on this learned topology, each router is then will able to compute its own routing table by using a shortest path computation.

Link state routing protocols features –

• Link state packet – It is a small packet which contains routing information.
• Link state database – It is a collection of information gathered from the link state packet.
• Shortest path first algorithm (Dijkstra algorithm) – The calculation performed on the database which results into the shortest path
• Routing table – It is a list of known paths and interfaces.

Calculation of shortest path –
To find shortest path, each node need to run the famous Dijkstra algorithm. Following are the steps of this algorithm:

• Step-1: The node is taken and then chosen as a root node of the tree, this will creates the tree with a single node, and now set the total cost of each of the node to some value based on the information in the Link State Database
• Step-2: Now the node will select one node, among all of the nodes that is not in the tree like structure, which is nearest to that of the root, and then adds this to the tree. Then the shape of the tree gets changed.
• Step-3: After this entire node is added to the tree, then the cost of all the nodes which is not in the tree needs to be updated because of the paths may have been changed.
• Step-4: The node repeats the Step 2. And Step 3. Until entire nodes are added in the tree

Link State protocols in comparison to Distance Vector protocols have:

1. Large amount of memory is required.
2. Many CPU circles are required for shortest path computations.
3. If the network uses the small bandwidth then it quickly reacts to changes in the topology.
4. All items in the database must be sent to the neighbours to form link state packets.
5. All neighbours must be trusted in the topology.
6. Authentication mechanisms can be used to avoid undesired adjacency and problems.
7. In the link state routing no split horizon techniques are possible.

9.5 Open shortest path first (OSPF) routing protocol –

• Open Shortest Path First (OSPF) is a unicast routing protocol which is developed by working group of the Internet Engineering Task Force (IETF).
• It is an intra domain routing protocol.
• It is an open source protocol.
• It is similar to that of Routing Information Protocol (RIP)
• Classless routing protocol is OSPF, which means that in its updates, it includes the subnet of each of its route it knows about, thus, enabling variable-length subnet masks. With variable-length subnet masks, an IP network can be broken into many subnets of various sizes. This provides network administrators with extra network-configuration flexibility. These updates are multicasts at specific addresses (224.0.0.5 and 224.0.0.6).
• OSPF is implemented as a program in the network layer using the services provided by the Internet Protocol
• IP datagram that carries the messages from OSPF sets the value 89 of protocol field
• OSPF is based on the SPF algorithm, which sometimes is also known as Dijkstra algorithm
• OSPF has two versions – version 1 and version 2. Mostly version 2 is used

OSPF Messages – OSPF is a very complex protocol. Five different message types are used. These are as follows:

      Hello message (Type 1) – It is used by the routers to introduce itself to the other routers.

      Database description message (Type 2) – It is normally sent in response to the Hello message.

      Link-state request message (Type 3) – It is used by the routers that need information about specific Link-State packet.

      Link-state update message (Type 4) – It is the main OSPF message for building Link-State Database.

      Link-state acknowledgement message (Type 5) – It is used to create reliability in the OSPF protocol.

9.6 Interior and Exterior Protocol

Routing is the process of moving the data from one of the network to another. Routing is unnecessary unless you are having multiple networks on different address ranges. If you have different combinations of IP addresses and that of subnet masks, you have separate networks. If you don't, you have to perform bridging or switching. You don't need to run a routing protocol unless you have multiple networks served by more than one router (and even then, manual static routes are easier for small networks). Once you get beyond three routers, it's time to start thinking about dynamic routing protocols. If you are going to connect your networks to the Internet, you will also have to think about running more than one kind of routing protocol.

INTERIOR GATEWAY PROTOCOLS

Interior Gateway Protocols (IGPs) handle routing within an Autonomous System (one routing domain).These dynamic routing protocols keep the track of paths which is used to move data from one end of the system to another of the system inside a network or set of networks that you are administrating. IGP's are how you get all the networks communicating with each other.

IGP's fall into two categories:

• Distance Vector Protocols
       Routing Information Protocol (RIP)
       Interior Gateway Routing Protocol (IGRP)
•  Link State Protocols
       Open Shortest Path First (OSPF)
       Intermediate System to Intermediate System (IS-IS)
   

EXTERIOR GATEWAY PROTOCOLS

To get from place to place outside your network(s), that is on the Internet, you must use an Exterior Gateway Protocol. Exterior Gateway Protocols handle routing outside an Autonomous System and get you from your network, through your Internet provider's network and onto any other network. BGP is used by different companies with more than one Internet provider that allows them to have redundancy and the load balancing of their data which are transported to and from the Internet.

Examples of an EGP:
    Border Gateway Protocol (BGP)
    Exterior Gateway Protocol (Replaced by BGP)

Gateway is a network node which connects two networks using different protocols together.

Gateway also acts as a gate between two networks. It can be a router or a firewall or a server or any other device that enables traffic to flow in and out of the network.

1. Border Gateway Protocol (BGP) is a routing protocol which is used to transfer data and the information between different host gateways, the Internet or the autonomous systems. It is a Path Vector Protocol (PVP), which maintains paths to different hosts, networks and gateway routers which determines the routing decision based on that.

• BGP is an inter-domain protocol which is used to exchange network reachability information between two or more BGP routers (also known as BGP speakers).
• BGP is used to enable two different autonomous systems to exchange the routing information in such a way so that IP traffic can flow across the autonomous system border.
• Each BGP router that can establish a TCP connection with one or more BGP routers.
• If two of the routers are connected in the same subnetwork, they are considered as neighbours.
• If two of the routers are connected in different autonomous systems, they are allowed to exchange the routing information. BGP uses TCP/IP protocol to create reliable connection in sessions.
• BGP connections inside an autonomous system are known as internal BGP and connection between two different autonomous systems are known as external BGP.

References:

1. Data Communication & Networking by Forouzan, Tata McGraw Hill.
2. Computer Network, 4e, by Andrew S. Tenenbaum, Pearson Education/ PHI.
3. Data Communication and Computer Networks, by Prakash C.Gupta, PHI.
4. Networking Ali-in-one Desk Reference by Doug Lowe, Wiley Dreamtech
5. Computer Networking: A Top-Down Approach featuring the Internet, 3e by James F.Kurose.
6. Computer Network by Godbole, Tata McGraw Hill.
7. Computer Networking, by Stanford H. Rowe, Marsha L. Schuh    

UNIT 9

Routing Algorithms

9.1 Router

• It is a process of selecting path along which data can be transferred from the source to the destination. Routing can be performed by a special device which is known as a router.
• It works at the network layer in the OSI model and internet layer in TCP/IP model
• It is a networking device that forwards the packet based on the information available and in the packet header and forwarding table.
• The routing algorithms which is used for routing the packets. The routing algorithm is nothing but it is the software responsible for deciding the optimal path through which the packet can be transmitted.
• The routing protocols use the metric which is to determine the best path for the packet delivery. The metric which is the standard of measurement for example hop count, bandwidth, delay, current load on the path, etc. which is used by the routing algorithm to determine the optimal path to destination.
• The routing algorithm initializes and maintains the routing table for the process of path determination.

Types of Routing

Routing can be classified into three categories:

• Static Routing
• Default Routing
• Dynamic Routing

 Static Routing

• Static Routing can also know as Nonadoptive Routing.
• Static Routing is a technique in which the administrator manually adds the routes in a routing table.
• A Router can send the packets for destination along the route which is defined by the administrator.
• In this technique, routing decisions are not made based on the condition or topology of the networks

Advantages of Static Routing

• No Overhead: It has how overhead on the CPU usage of the router. Therefore, cheaper router can be used to obtain static routing.
• Bandwidth: It has no bandwidth usage between the routers.
• Security: It provides security as the system administrator is allowed only to have control over the routing to a particular network.

Disadvantages of Static Routing:

• For a large network, it becomes a very difficult task to add each route manually to routing table.
• The system administrator should be knowledgeable of a topology as he has to add each route manually.

Default Routing

• Default Routing is a technique in which the router which is configured to send all packets to the same hop device, and it does not matter whether it belong to a particular network or not. The Packet is transmitted to the device for which it is configured in default routing.
• It is used when networks deal with the single exit point.
• Default routing is also useful when bulk of transmission networks have to transmit the data to the same hop device.
• When a specific route is mentioned in the routing table, the router will choose the specific route rather than the default route. The default route is chosen only when a specific route is not mentioned in the routing table.

Dynamic Routing

• Dynamic routing is also known as Adaptive Routing.
• Dynamic routing is a technique in which a router adds a new route in the routing table for each packet in response to the changes in the condition or topology of the network.
• Dynamic protocols are used to discover the new routes to reach the destination.
• In Dynamic Routing, RIP and OSPF are the protocols used to discover the new routes.
• If any route goes down, then automatic adjustment will be made to reach destination.

The Dynamic protocol should have the following features:

• All routers must have same dynamic routing protocol in order to exchange routes.
• If router discovers any change in the condition or topology, then router broadcast this information to all other routers.

Advantages of Dynamic Routing:

• Easy to configure.
• More effective in selecting the best route in response to the changes in the condition or topology.

Disadvantages of Dynamic Routing:

• It is expensive in terms of CPU and bandwidth usage.
• Less secure as compared to default and static routing.

9.2 Distance Vector Routing Algorithm

A distance-vector routing (DVR) protocol is that it requires that a router should inform its neighbours of topology changes takes place periodically. Historically it is known as the old ARPANET routing algorithm (or it is also known as Bellman-Ford algorithm).

Bellman Ford Basics – Each router maintains its Distance Vector table which are containing the distance between itself and all possible destination nodes. Distances is based on a chosen metric and are computed using information from the neighbours’ distance vectors.

Information which are kept by DV router -

• Each router has its own ID
• IT is associated with each link that are connected to a router,
• There is a cost of the link (static or dynamic).
• Intermediate hops

Distance Vector Table Initialization -

• Distance to itself = 0
• Distance to all other routers = infinity number.

Distance Vector Algorithm –

1. A router transmits its distance vector to that of each of its neighbours in that of a routing packet.
2. Each router receives and then saves the most recently received distance vector from each of its neighbours.
3. A router recalculates its distance vector when the following happens:
   • It receives a distance vector from that of its neighbour containing different information than before.
   • It discovers that a link to a neighbour has slow down.

The DV calculation is based on minimizing the cost to each destination

Dx(y) = Estimate of least cost from x to y

C(x,v) =  Node x knows cost to each neighbour v

Dx   = [Dx(y): y ∈ N] = Node x maintains distance vector

Node x also maintains its neighbours’ distance vectors

– For each neighbour v, x maintains Dv = [Dv(y): y ∈N ]

Note –

• From time-to-time, each of the node sends its own distance vector which is estimate to its neighbours.
• When a node x receives new DV estimate from any neighbour v, it saves v’s distance vector and it updates its own DV using B-F equation:
• Dx(y) = min { C(x,v) + Dv(y)} for each node y ∈ N

Example – Consider 3-routers X, Y and Z as shown in figure. Each router has their routing table. Every routing table will contain distance to the destination nodes.

Consider router X , X will share it routing table to neighbors and neighbors will share it routing table to it to X and distance from node X to destination will be calculated using bellmen- ford equation.

Dx(y) = min { C(x,v) + Dv(y)} for each node y ∈ N

As we can see that distance will be less going from X to Z when Y is intermediate node(hop) so it will be update in routing table X.

Similarly for Z also –
 

Finally the routing table for all –

Advantages of Distance Vector routing are as follows –

• It is very simple to configure and it maintains link state routing.

Disadvantages of Distance Vector routing are as follows –

• It is very slow to converge than link state.
• It is at high risk from the count-to-infinity problem.
• It creates more traffic than that of link state since a hop count changes must be propagated to all routers and then processed on each router. Hop count updates take place on periodic basis, even if there are no networks changes in the topology, so bandwidth-wasting broadcasts still occur.
• For the very large networks, distance vector routing results in larger routing tables than link state since each router must know also about all of the other routers. This can also lead to congestion on WAN links.

Note – For UDP (User datagram protocol) transportation it uses Distance Vector routing

9.3 Routing Information Protocol (RIP)

Routing Information Protocol (RIP) is dynamic routing protocol which uses a hop count method as a routing metric to find its best path between the source network and the destination network. It is a distance vector routing protocol which has its AD value 120 and works on the application layer of the OSI model. 520 port numbers is used by RIP.

Hop Count:
Hop count is the number of routers which are occurring in between the source and the destination network. The path with that of the lowest hop count is considered to be as the best route to reach a network and therefore it is placed in the routing table. RIP prevents the routing loops by limiting the number of hopes allowed in a path from the source and the destination.15 is the maximum hop count allowed for RIP and hop count of 16 is considered to be as network unreachable.

Features of RIP:

1. Updates of the network are to be exchanged periodically.
2. Updates (routing information) are always to be broadcast.
3. Full routing tables are to be sent in updates.
4. Routers always trust on routing information received from neighbour routers. This is also called routing on rumours.

RIP versions:
There are three visions of routing information protocol – RIP Version1, RIP Version2 and RIPng.

RIP v1is called Classful Routing Protocol because it doesn’t send information of subnet mask in its routing update.
RIP v2 is called Classless Routing Protocol because it sends information of subnet mask in its routing update.

9.4 Link State Routing and OSPF Routing Protocol

Unicast – Unicast is the transmission from single sender to single receiver. It has point to point communication between the sender end and the receivers end. There are various types of unicast protocols for example TCP, HTTP, etc.

• The most commonly used unicast protocol is TCP. It is a connection oriented protocol that will rely on an acknowledgement from that of the receiver side.
• HTTP is Hyper Text Transfer Protocol. It is an object oriented protocol for that of the communication.

Three major protocols for unicast routing are:

1. Distance Vector Routing
2. Link State Routing
3. Path-Vector Routing

Link State Routing –
The second family of routing protocols is Link state routing. While the distance vector routers uses a distributed algorithm to compute to their routing tables and link-state routing uses its link-state routers for the exchanging of messages that allows each of the router to learn the entire of the network topology. Based on this learned topology, each router is then will able to compute its own routing table by using a shortest path computation.

Link state routing protocols features –

• Link state packet – It is a small packet which contains routing information.
• Link state database – It is a collection of information gathered from the link state packet.
• Shortest path first algorithm (Dijkstra algorithm) – The calculation performed on the database which results into the shortest path
• Routing table – It is a list of known paths and interfaces.

Calculation of shortest path –
To find shortest path, each node need to run the famous Dijkstra algorithm. Following are the steps of this algorithm:

• Step-1: The node is taken and then chosen as a root node of the tree, this will creates the tree with a single node, and now set the total cost of each of the node to some value based on the information in the Link State Database
• Step-2: Now the node will select one node, among all of the nodes that is not in the tree like structure, which is nearest to that of the root, and then adds this to the tree. Then the shape of the tree gets changed.
• Step-3: After this entire node is added to the tree, then the cost of all the nodes which is not in the tree needs to be updated because of the paths may have been changed.
• Step-4: The node repeats the Step 2. And Step 3. Until entire nodes are added in the tree

Link State protocols in comparison to Distance Vector protocols have:

1. Large amount of memory is required.
2. Many CPU circles are required for shortest path computations.
3. If the network uses the small bandwidth then it quickly reacts to changes in the topology.
4. All items in the database must be sent to the neighbours to form link state packets.
5. All neighbours must be trusted in the topology.
6. Authentication mechanisms can be used to avoid undesired adjacency and problems.
7. In the link state routing no split horizon techniques are possible.

9.5 Open shortest path first (OSPF) routing protocol –

• Open Shortest Path First (OSPF) is a unicast routing protocol which is developed by working group of the Internet Engineering Task Force (IETF).
• It is an intra domain routing protocol.
• It is an open source protocol.
• It is similar to that of Routing Information Protocol (RIP)
• Classless routing protocol is OSPF, which means that in its updates, it includes the subnet of each of its route it knows about, thus, enabling variable-length subnet masks. With variable-length subnet masks, an IP network can be broken into many subnets of various sizes. This provides network administrators with extra network-configuration flexibility. These updates are multicasts at specific addresses (224.0.0.5 and 224.0.0.6).
• OSPF is implemented as a program in the network layer using the services provided by the Internet Protocol
• IP datagram that carries the messages from OSPF sets the value 89 of protocol field
• OSPF is based on the SPF algorithm, which sometimes is also known as Dijkstra algorithm
• OSPF has two versions – version 1 and version 2. Mostly version 2 is used

OSPF Messages – OSPF is a very complex protocol. Five different message types are used. These are as follows:

      Hello message (Type 1) – It is used by the routers to introduce itself to the other routers.

      Database description message (Type 2) – It is normally sent in response to the Hello message.

      Link-state request message (Type 3) – It is used by the routers that need information about specific Link-State packet.

      Link-state update message (Type 4) – It is the main OSPF message for building Link-State Database.

      Link-state acknowledgement message (Type 5) – It is used to create reliability in the OSPF protocol.

9.6 Interior and Exterior Protocol

Routing is the process of moving the data from one of the network to another. Routing is unnecessary unless you are having multiple networks on different address ranges. If you have different combinations of IP addresses and that of subnet masks, you have separate networks. If you don't, you have to perform bridging or switching. You don't need to run a routing protocol unless you have multiple networks served by more than one router (and even then, manual static routes are easier for small networks). Once you get beyond three routers, it's time to start thinking about dynamic routing protocols. If you are going to connect your networks to the Internet, you will also have to think about running more than one kind of routing protocol.

INTERIOR GATEWAY PROTOCOLS

Interior Gateway Protocols (IGPs) handle routing within an Autonomous System (one routing domain).These dynamic routing protocols keep the track of paths which is used to move data from one end of the system to another of the system inside a network or set of networks that you are administrating. IGP's are how you get all the networks communicating with each other.

IGP's fall into two categories:

• Distance Vector Protocols
       Routing Information Protocol (RIP)
       Interior Gateway Routing Protocol (IGRP)
•  Link State Protocols
       Open Shortest Path First (OSPF)
       Intermediate System to Intermediate System (IS-IS)
   

EXTERIOR GATEWAY PROTOCOLS

To get from place to place outside your network(s), that is on the Internet, you must use an Exterior Gateway Protocol. Exterior Gateway Protocols handle routing outside an Autonomous System and get you from your network, through your Internet provider's network and onto any other network. BGP is used by different companies with more than one Internet provider that allows them to have redundancy and the load balancing of their data which are transported to and from the Internet.

Examples of an EGP:
    Border Gateway Protocol (BGP)
    Exterior Gateway Protocol (Replaced by BGP)

Gateway is a network node which connects two networks using different protocols together.

Gateway also acts as a gate between two networks. It can be a router or a firewall or a server or any other device that enables traffic to flow in and out of the network.

1. Border Gateway Protocol (BGP) is a routing protocol which is used to transfer data and the information between different host gateways, the Internet or the autonomous systems. It is a Path Vector Protocol (PVP), which maintains paths to different hosts, networks and gateway routers which determines the routing decision based on that.

• BGP is an inter-domain protocol which is used to exchange network reachability information between two or more BGP routers (also known as BGP speakers).
• BGP is used to enable two different autonomous systems to exchange the routing information in such a way so that IP traffic can flow across the autonomous system border.
• Each BGP router that can establish a TCP connection with one or more BGP routers.
• If two of the routers are connected in the same subnetwork, they are considered as neighbours.
• If two of the routers are connected in different autonomous systems, they are allowed to exchange the routing information. BGP uses TCP/IP protocol to create reliable connection in sessions.
• BGP connections inside an autonomous system are known as internal BGP and connection between two different autonomous systems are known as external BGP.

References:

1. Data Communication & Networking by Forouzan, Tata McGraw Hill.
2. Computer Network, 4e, by Andrew S. Tenenbaum, Pearson Education/ PHI.
3. Data Communication and Computer Networks, by Prakash C.Gupta, PHI.
4. Networking Ali-in-one Desk Reference by Doug Lowe, Wiley Dreamtech
5. Computer Networking: A Top-Down Approach featuring the Internet, 3e by James F.Kurose.
6. Computer Network by Godbole, Tata McGraw Hill.
7. Computer Networking, by Stanford H. Rowe, Marsha L. Schuh