What is IP Routing?
The purpose of the different IP Routing protocols and how they work.
Routing protocols implement algorithms that tell routers the best paths through internetworks. Routing protocols include Border Gateway Protocol (BGP), Interior Gateway Routing Protocol (IGRP), Routing Information Protocol, and Open Shortest Path First (OSPF) to name a few. Routing protocols provide the layer 3 network state update. Protocols that are transported through a network, such as Internet Protocol (IP), Novell Internetwork Packet eXchange (IPX), and AppleTalk are called routed protocols.
In short, routing protocols route datagrams through a network. Routing is a layer 3 function, thus, routing and routed protocols are network-layer entities. Routing tables on the layer 3 switch (router) are populated by information from routing protocols. A routed protocol will enter an interface on a router, be placed in a memory buffer, then it will be forwarded out to an interface based on information in the routing table.
Routing tables are critically important to the routing process. It is possible for these tables to be manually maintained by network administrators, but this is tedious, time-consuming and doesn't allow routers to deal with changes or problems in the internetwork. Instead, most modern routers are designed with functionality that lets them share route information with other routers, so they can keep their routing tables up to date automatically. This information exchange is accomplished through the use of routing protocols.
Note:-Some of the protocols in this section are generic enough that they could be applied to support the routing of any network layer protocol. They are most often associated with IP, however, as TCP/IP is by far the most popular internetworking protocol suite, and that is my assumption in describing them. Also, this section focuses primarily on the routing protocols used in Internet Protocol version 4. There is limited discussion of IPv6 versions of the protocols at this time.
Reference:
-dataconnection
-TCP/IP Guide
-O'Reilly
Saturday, 6 September 2008
Tuesday, 2 September 2008
IP Routing
What is IP Routing?
IP Routing is an umbrella term for the set of protocols that determine the path that data follows in order to travel across multiple networks from its source to its destination. Data is routed from its source to its destination through a series of routers, and across multiple networks. The IP Routing protocols enable routers to build up a forwarding table that correlates final destinations with next hop addresses.
These protocols include:
BGP->Border Gateway Protocol
(More details:Data Connection, Cisco)
IS-IS->Intermediate System - Intermediate System
(More details:Data Connection, Cisco)
OSPF->Open Shortest Path First
(More details:Data Connection, Cisco)
RIP->Routing Information Protocol
(More details:Data Connection, Cisco)
OER->Cisco Optimized Edge Routing
(More details:Cisco)
EIGRP->Enhanced Interior Gateway Routing Protocol
(More details:Cisco)
IGRP->Interior Gateway Routing Protocol
(More details:Cisco)
OSPF->Open Shortest Path First
(More details:Cisco)
ODR->On-Demand Routing
(More details:Cisco)
MBGP->Multiprotocol BGP
(More details:Cisco)
When an IP packet is to be forwarded, a router uses its forwarding table to determine the next hop for the packet's destination (based on the destination IP address in the IP packet header), and forwards the packet appropriately. The next router then repeats this process using its own forwarding table, and so on until the packet reaches its destination. At each stage, the IP address in the packet header is sufficient information to determine the next hop; no additional protocol headers are required.
The Internet, for the purpose of routing, is divided into Autonomous Systems (ASs). An AS is a group of routers that are under the control of a single administration and exchange routing information using a common routing protocol. For example, a corporate intranet or an ISP network can usually be regarded as an individual AS. The Internet can be visualized as a partial mesh of ASs. An AS can be classified as one of the following three types.
* A Stub AS has a single connection to one other AS. Any data sent to, or received from, a destination outside the AS must travel over that connection. A small campus network is an example of a stub AS.
* A Transit AS has multiple connections to one or more ASs, which permits data that is not destined for a node within that AS to travel through it. An ISP network is an example of a transit AS.
* A Multihomed AS also has multiple connections to one or more ASs, but it does not permit data received over one of these connections to be forwarded out of the AS again. In other words, it does not provide a transit service to other ASs. A Multihomed AS is similar to a Stub AS, except that the ingress and egress points for data traveling to or from the AS can be chosen from one of a number of connections, depending on which connection offers the shortest route to the eventual destination. A large enterprise network would normally be a multihomed AS.
An Interior Gateway Protocol (IGP) calculates routes within a single AS. The IGP enables nodes on different networks within an AS to send data to one another. The IGP also enables data to be forwarded across an AS from ingress to egress, when the AS is providing transit services.
Routes are distributed between ASs by an Exterior Gateway Protocol (EGP). The EGP enables routers within an AS to choose the best point of egress from the AS for the data they are trying to route.
The EGP and the IGPs running within each AS cooperate to route data across the Internet. The EGP determines the ASs that data must cross in order to reach its destination, and the IGP determines the path within each AS that data must follow to get from the point of ingress (or the point of origin) to the point of egress (or the final destination).
The diagram below illustrates the different types of AS in a network. OSPF, IS-IS and RIP are IGPs used within the individual ASs; BGP is the EGP used between ASs.
Reference:
Data Connection
Cisco
IP Routing is an umbrella term for the set of protocols that determine the path that data follows in order to travel across multiple networks from its source to its destination. Data is routed from its source to its destination through a series of routers, and across multiple networks. The IP Routing protocols enable routers to build up a forwarding table that correlates final destinations with next hop addresses.
These protocols include:
BGP->Border Gateway Protocol
(More details:Data Connection, Cisco)
IS-IS->Intermediate System - Intermediate System
(More details:Data Connection, Cisco)
OSPF->Open Shortest Path First
(More details:Data Connection, Cisco)
RIP->Routing Information Protocol
(More details:Data Connection, Cisco)
OER->Cisco Optimized Edge Routing
(More details:Cisco)
EIGRP->Enhanced Interior Gateway Routing Protocol
(More details:Cisco)
IGRP->Interior Gateway Routing Protocol
(More details:Cisco)
OSPF->Open Shortest Path First
(More details:Cisco)
ODR->On-Demand Routing
(More details:Cisco)
MBGP->Multiprotocol BGP
(More details:Cisco)
When an IP packet is to be forwarded, a router uses its forwarding table to determine the next hop for the packet's destination (based on the destination IP address in the IP packet header), and forwards the packet appropriately. The next router then repeats this process using its own forwarding table, and so on until the packet reaches its destination. At each stage, the IP address in the packet header is sufficient information to determine the next hop; no additional protocol headers are required.
The Internet, for the purpose of routing, is divided into Autonomous Systems (ASs). An AS is a group of routers that are under the control of a single administration and exchange routing information using a common routing protocol. For example, a corporate intranet or an ISP network can usually be regarded as an individual AS. The Internet can be visualized as a partial mesh of ASs. An AS can be classified as one of the following three types.
* A Stub AS has a single connection to one other AS. Any data sent to, or received from, a destination outside the AS must travel over that connection. A small campus network is an example of a stub AS.
* A Transit AS has multiple connections to one or more ASs, which permits data that is not destined for a node within that AS to travel through it. An ISP network is an example of a transit AS.
* A Multihomed AS also has multiple connections to one or more ASs, but it does not permit data received over one of these connections to be forwarded out of the AS again. In other words, it does not provide a transit service to other ASs. A Multihomed AS is similar to a Stub AS, except that the ingress and egress points for data traveling to or from the AS can be chosen from one of a number of connections, depending on which connection offers the shortest route to the eventual destination. A large enterprise network would normally be a multihomed AS.
An Interior Gateway Protocol (IGP) calculates routes within a single AS. The IGP enables nodes on different networks within an AS to send data to one another. The IGP also enables data to be forwarded across an AS from ingress to egress, when the AS is providing transit services.
Routes are distributed between ASs by an Exterior Gateway Protocol (EGP). The EGP enables routers within an AS to choose the best point of egress from the AS for the data they are trying to route.
The EGP and the IGPs running within each AS cooperate to route data across the Internet. The EGP determines the ASs that data must cross in order to reach its destination, and the IGP determines the path within each AS that data must follow to get from the point of ingress (or the point of origin) to the point of egress (or the final destination).
The diagram below illustrates the different types of AS in a network. OSPF, IS-IS and RIP are IGPs used within the individual ASs; BGP is the EGP used between ASs.
Reference:
Data Connection
Cisco
Monday, 1 September 2008
Ad-hoc network and Pro-active Routing Protocal Part2 : Destination-Sequenced Distance-Vector Routing (DSDV)
Ad-hoc network and Pro-active Routing Protocal Part1: AWDS and Babel.
Type of protocols
Pro-active Routing (Table-driven)
This protocols maintains fresh lists of destinations and their routes by periodically distributing routing tables throughout the network. The main disadvantages of such algorithms are -
1. Respective amount of data for maintenance.
2. Slow reaction on restructuring and failures.
Examples of proactive algorithms are (con.)-
C).Destination-Sequenced Distance-Vector Routing (DSDV) is a table-driven routing scheme for ad hoc mobile networks based on the Bellman-Ford algorithm. It was developed by C. Perkins and P.Bhagwat in 1994. The main contribution of the algorithm was to solve the Routing Loop problem. Each entry in the routing table contains a sequence number, the sequence numbers are generally even if a link is present; else, an odd number is used. The number is generated by the destination, and the emitter needs to send out the next update with this number. Routing information is distributed between nodes by sending full dumps infrequently and smaller incremental updates more frequently.
For example the routing table of Node A in this network is
Destination Next Hop Number of Hops Sequence Number Install Time
A A 0 A 46 001000
B B 1 B 36 001200
C B 2 B 28 001500
Naturally the table contains description of all possible paths reachable by node A, along with the next hop, number of hops and sequence number.
Selection of Route
If a router receives new information, then it uses the latest sequence number. If the sequence number is the same as the one already in the table, the route with the better metric is used. Stale entries are those entries that have not been updated for a while. Such entries as well as the routes using those nodes as next hops are deleted.
Advantages
DSDV was one of the early algorithms available. It is quite suitable for creating ad hoc networks with small number of nodes. Since no formal specification of this algorithm is present there is no commercial implementation of this algorithm. Many improved forms of this algorithm have been suggested.
Disadvantages
1. DSDV requires a regular update of its routing tables, which uses up battery power and a small amount of bandwidth even when the network is idle.
2. Whenever the topology of the network changes, a new sequence number is necessary before the network re-converges; thus, DSDV is not suitable for highly dynamic networks. (As in all distance-vector protocols, this does not perturb traffic in regions of the network that are not concerned by the topology change.)
Influence
While DSDV itself does not appear to be much used today[citation needed], other protocols have used similar techniques. The best-known sequenced distance vector protocol is AODV, which, by virtue of being a reactive protocol, can use simpler sequencing heuristics. Babel is an attempt at making DSDV more robust and more efficient within the framework of proactive protocols.
References
1.Perkins, Charles E. and Bhagwat, Pravin (1994). "Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers" (pdf). Retrieved on 2006-10-20.
2.wikipedia
3..Securing the Destination-Sequenced Distance Vector Routing Protocol (S-DSDV)
Additional Research : Securing
1.Securing the Destination-Sequenced Distance Vector Routing Protocol (S-DSDV)
propose : a secure routing protocol based on DSDV, namely S-DSDV, in which, a well-behaved node can successfully detect a malicious routing update with any sequence number fraud (larger or smaller) and any distance fraud (shorter, same, or longer) provided no two nodes are in collusion.
compare : security properties and efficiency of S-DSDV with superSEAD. Our efficiency analysis shows that S-DSDV generates high network overhead, however, which can be reduced by configurable parameters.
believe : the S-DSDV overhead is justified by the enhanced security.
Type of protocols
Pro-active Routing (Table-driven)
This protocols maintains fresh lists of destinations and their routes by periodically distributing routing tables throughout the network. The main disadvantages of such algorithms are -
1. Respective amount of data for maintenance.
2. Slow reaction on restructuring and failures.
Examples of proactive algorithms are (con.)-
C).Destination-Sequenced Distance-Vector Routing (DSDV) is a table-driven routing scheme for ad hoc mobile networks based on the Bellman-Ford algorithm. It was developed by C. Perkins and P.Bhagwat in 1994. The main contribution of the algorithm was to solve the Routing Loop problem. Each entry in the routing table contains a sequence number, the sequence numbers are generally even if a link is present; else, an odd number is used. The number is generated by the destination, and the emitter needs to send out the next update with this number. Routing information is distributed between nodes by sending full dumps infrequently and smaller incremental updates more frequently.
For example the routing table of Node A in this network is
Destination Next Hop Number of Hops Sequence Number Install Time
A A 0 A 46 001000
B B 1 B 36 001200
C B 2 B 28 001500
Naturally the table contains description of all possible paths reachable by node A, along with the next hop, number of hops and sequence number.
Selection of Route
If a router receives new information, then it uses the latest sequence number. If the sequence number is the same as the one already in the table, the route with the better metric is used. Stale entries are those entries that have not been updated for a while. Such entries as well as the routes using those nodes as next hops are deleted.
Advantages
DSDV was one of the early algorithms available. It is quite suitable for creating ad hoc networks with small number of nodes. Since no formal specification of this algorithm is present there is no commercial implementation of this algorithm. Many improved forms of this algorithm have been suggested.
Disadvantages
1. DSDV requires a regular update of its routing tables, which uses up battery power and a small amount of bandwidth even when the network is idle.
2. Whenever the topology of the network changes, a new sequence number is necessary before the network re-converges; thus, DSDV is not suitable for highly dynamic networks. (As in all distance-vector protocols, this does not perturb traffic in regions of the network that are not concerned by the topology change.)
Influence
While DSDV itself does not appear to be much used today[citation needed], other protocols have used similar techniques. The best-known sequenced distance vector protocol is AODV, which, by virtue of being a reactive protocol, can use simpler sequencing heuristics. Babel is an attempt at making DSDV more robust and more efficient within the framework of proactive protocols.
References
1.Perkins, Charles E. and Bhagwat, Pravin (1994). "Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers" (pdf). Retrieved on 2006-10-20.
2.wikipedia
3..Securing the Destination-Sequenced Distance Vector Routing Protocol (S-DSDV)
Additional Research : Securing
1.Securing the Destination-Sequenced Distance Vector Routing Protocol (S-DSDV)
propose : a secure routing protocol based on DSDV, namely S-DSDV, in which, a well-behaved node can successfully detect a malicious routing update with any sequence number fraud (larger or smaller) and any distance fraud (shorter, same, or longer) provided no two nodes are in collusion.
compare : security properties and efficiency of S-DSDV with superSEAD. Our efficiency analysis shows that S-DSDV generates high network overhead, however, which can be reduced by configurable parameters.
believe : the S-DSDV overhead is justified by the enhanced security.
Subscribe to:
Posts (Atom)
