Authors :
Dynamic routing occurs when routers talk to adjacent routers, informing each other of what network each router is currently connected to. The routers must communicate using a routing protocol that is running by the Routing Daemon. In Contrast to static protocol, the information placed into the routing tables - the routes, are added and deleted dynamically by a routing daemon, as routes change over time. The routing daemon adds a routing policy to the system, choosing which routes to insert into the kernel's routing table. In case of multiple routes to the same destination, the daemon choose which route is the best. In the other side, if a link has gone down, the daemon delete routes connected to that link, and find alternatives to the routes - if exist.
Many different routing protocols are used in big networks. The internet, for example, is divided to collection of autonomous systems ( ASs ) each of which is normally administrated by a single entity. A corporation or University may define an autonomous system. Every autonomous system uses its routing protocol to communicate between the routers in the autonomous system. This is called an Interior Gateway Protocol ( IGP ). The most popular IGP has been RIP. OSPF is a newer IGP that intends to replace RIP, at least in large networks.
RIP , the most widely used routing protocol has some problems: First, RIP has no knowledge of subnet addressing. If the normal 16 bit host ID of a class B address is nonzero, for example, RIP can't tell if the nonzero portion is subnet ID or if the IP address is a complete host address. Some implementations use the subnet mask of the interface through which the RIP information arrived, which isn't always correct.
Second, RIP takes a long time ( some minutes ) to stabilize after the failure of a router or a link. During this time, routing loops may occur.
Third, The use of the hop count as the routing metric omits other variables that should be taken into consideration. Also, a maximum of 15 for the metric limits the sizes of networks on which RIP can be used.
There is an extension to the old RIP , usually called RIP-2. The extensions don't change the protocol , but pass additional information that help with the RIP problems.
The OSPF - Open Shortest Path First - is an alternative to RIP as GIP. It overcomes all the limitations of RIP. OSPF is a link-state protocol, as opposed to RIP , which is distance-vector protocol. In a link-state protocol each router actively tests the status of its link to each of its neighbors, sends this information to its other neighbors and so on. Each router takes this link-state information and build a complete routing table. This method is much faster then the distance-vector protocols, especially in case of changes in the links in the network.
Other features that make OSPF superior to RIP:
There are more features but we will not mention all of them.
Summary :
The Open Shortest Path First routing protocol may be the answer to managing
complex multivendor networks. Common routing protocols, such as IP Routing
Information Protocol (RIP), are designed for simple networks that have
only a few routers and little redundancy. Such protocols are inefficient
in larger networks where routing messages take up significant amounts of
bandwidth. One way to address this problem is found in link state protocols,
such as OSPF, which produce a more stable network by getting the routers
to act on network changes predictably and simultaneously. An OSPF router
collects and advertises information about its neighboring routers via a
data structure called a router links advertisement. The router calculates
and sorts its neighbors, finding all the reachable routers and the most
optimal path. Specifics about the OSPF router, including its interface
and optimization methods, are discussed in detail.
to go back to the index press here 
OSPF allows sets of networks to be grouped together. Such a grouping is called an area and it's topology is hidden from the rest of the Autonomous System. This information hiding enables a significant reduction in routing traffic. An area is a generalization of an IP subnetted network.
All OSPF routing protocol exchanges are authenticated. This means that only trusted routers can participate in the AS's routing.
to goto go back to the index press here
to go back to the index press here
OSPF supports three types of physical networks: Point-to-point networks, Broadcast networks and Non-broadcast networks. Each network (stub or transit) in the graph has an IP address and associated network mask. The mask indicates the number of nodes on the network. Host attached directly to routers appear on the graph as stub network.
The topological database is pieced together from link state advertisements generated by the routers. The neighborhood of each transit vertex is represented in a single, separate link state advertisement.
Figure 1 shows a sample map of an Autonomous System. The rectangle labeled H1 indicates a host, which has a SLIP connection to Router RT12. Router RT12 is therefore advertising a host route. Lines between routers indicate physical point-to-point networks. The only point-to-point network that has been assigned interface addresses is the one joining Routers RT6 and RT10. Routers RT5 and RT7 have EGP (Exterior Gateway Protocol) connections to other Autonomous Systems. A set of EGP-learned routes have been displayed for both of these routers.
A cost is associated with the output side of each router interface. This cost is configurable by the system administrator. The lower the cost, the more likely the interface is to be used to forward data traffic. Costs are also associated with the externally derived routing data (e.g., the EGP- learned routes).
The directed graph resulting from the map in Figure 1 is depicted in Figure 2. Arcs are labeled with the cost of the corresponding router output interface. Arcs having no labeled cost have a cost of 0. Note that arcs leading from networks to routers always have cost 0; they are significant nonetheless. Note also that the externally derived routing data appears on the graph as stubs.
+
| 3+---+ N12 N14
N1|--|RT1|\ 1 \ N13 /
| +---+ \ 8\ |8/8
+ \ ____ \|/
/ \ 1+---+8 8+---+6
* N3 *---|RT4|------|RT5|--------+
\____/ +---+ +---+ |
+ / | |7 |
| 3+---+ / | | |
N2|--|RT2|/1 |1 |6 |
| +---+ +---+8 6+---+ |
+ |RT3|--------------|RT6| |
+---+ +---+ |
|2 Ia|7 |
| | |
+---------+ | |
N4 | |
| |
| |
N11 | |
+---------+ | |
| | | N12
|3 | |6 2/
+---+ | +---+/
|RT9| | |RT7|---N15
+---+ | +---+ 9
|1 + | |1
_|__ | Ib|5 __|_
/ \ 1+----+2 | 3+----+1 / \
* N9 *------|RT11|----|---|RT10|---* N6 *
\____/ +----+ | +----+ \____/
| | |
|1 + |1
+--+ 10+----+ N8 +---+
|H1|-----|RT12| |RT8|
+--+SLIP +----+ +---+
|2 |4
| |
+---------+ +--------+
N10 N7
Figure 1: A sample Autonomous System.
the three types of physical networks: point-to-point (RT6<->RT10),
multi-access (N8) and stub access (N7).
**FROM**
|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|RT|
|1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|N3|N6|N8|N9|
----- ---------------------------------------------
RT1| | | | | | | | | | | | |0 | | | |
RT2| | | | | | | | | | | | |0 | | | |
RT3| | | | | |6 | | | | | | |0 | | | |
RT4| | | | |8 | | | | | | | |0 | | | |
RT5| | | |8 | |6 |6 | | | | | | | | | |
RT6| | |8 | |7 | | | | |5 | | | | | | |
RT7| | | | |6 | | | | | | | | |0 | | |
* RT8| | | | | | | | | | | | | |0 | | |
* RT9| | | | | | | | | | | | | | | |0 |
T RT10| | | | | |7 | | | | | | | |0 |0 | |
O RT11| | | | | | | | | | | | | | |0 |0 |
* RT12| | | | | | | | | | | | | | | |0 |
* N1|3 | | | | | | | | | | | | | | | |
N2| |3 | | | | | | | | | | | | | | |
N3|1 |1 |1 |1 | | | | | | | | | | | | |
N4| | |2 | | | | | | | | | | | | | |
N6| | | | | | |1 |1 | |1 | | | | | | |
N7| | | | | | | |4 | | | | | | | | |
N8| | | | | | | | | |3 |2 | | | | | |
N9| | | | | | | | |1 | |1 |1 | | | | |
N10| | | | | | | | | | | |2 | | | | |
N11| | | | | | | | |3 | | | | | | | |
N12| | | | |8 | |2 | | | | | | | | | |
N13| | | | |8 | | | | | | | | | | | |
N14| | | | |8 | | | | | | | | | | | |
N15| | | | | | |9 | | | | | | | | | |
H1| | | | | | | | | | | |10| | | | |
Figure 2: The resulting directed graph
Networks and routers are represented by vertices.
An edge of cost X connects Vertex A to Vertex B iff
the intersection of Column A and Row B is marked
with an X.
to go back to the index press here
The tree gives the entire route to any destination network or host. However, only the next hop to the destination is used in the forwarding process. Note also that the best route to any router has also been calculated. For the processing of external data, we note the next hop and distance to any router advertising external routes.
The resulting routing table for Router RT6 is pictured in Figure 3. Note that there is a separate route for each end of a numbered serial line (in this case, the serial line between Routers RT6 and RT10).
Destination Next Hop Distance
__________________________________
N1 RT3 10
N2 RT3 10
N3 RT3 7
N4 RT3 8
Ib * 7
Ia RT10 12
N6 RT10 8
N7 RT10 12
N8 RT10 10
N9 RT10 11
N10 RT10 13
N11 RT10 14
H1 RT10 21
__________________________________
RT5 RT5 6
RT7 RT10 8
Figure 3: The portion of Router RT6's routing table
listing local destinations.
to go back to the index press here
The Hello Protocol works differently on broadcast networks, as compared to non-broadcast networks. On broadcast networks, each router advertises itself by periodically multicasting Hello Packets. This allows neighbors to be discovered dynamically. These Hello Packets contain the router's view of the DR's identity, and the list of routers whose Hello Packets have been seen recently.
On non-broadcast networks some configuration information is necessary for the operation of the Hello Protocol. Each router that may potentially become DR has a list of all other routers attached to the network. A router, having DR potential, sends Hello Packets to all other potential DR when its interface to the non-broadcast network first becomes operational. This is an attempt to find the DR for the network. If the router itself is elected DR, it begins sending Hello Packets to all other routers attached to the network.
After a neighbor has been discovered, bidirectional communication ensured, and (if on a multi-access network) a DR elected, a decision is made regarding whether or not an adjacency should be formed with the neighbor. An attempt is always made to establish adjacencies over point-to-point networks and virtual links. The first step in bringing up an adjacency is to synchronize the neighbors' topological databases.
to go back to the index press here
All routers connected to a common network must agree on certain parameters
(Network mask, HelloInterval and RouterDeadInterval).
These parameters are included in Hello packets, so that differences can
inhibit the forming of neighbor relationships.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version # | 1 | Packet length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Router ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Area ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Checksum | AuType |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Authentication |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Network Mask |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| HelloInterval | Options | Rtr Pri |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RouterDeadInterval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Designated Router |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Backup Designated Router |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
to go back to the index press here
The DR concept enables a reduction in the number of adjacencies required on a multi-access network. This in turn reduces the amount of routing protocol traffic and the size of the topological database.
When a router R has an LSP to propagate on the LAN, R doesn't multicast the LSP to all the other routers. Instead, R transmits it to the DR. But rather than send the LSP to the DR's personal data link address, R transmits it to the multicast address of all DRs, to which both the DR and the backup DR listen. When the DR receives the LSP, the DR multicasts the LSP to all the other routers. Then the DR collect acks for that LSP, which are transmitted to the multicast address of all the DRs (as described above). If the DR does not receive an ack from a subset of the routers, it sends explicit copies of the LSP to each router in that subset.
So, The DR performs two main functions for the routing protocol:
The Backup Designated Router does not generate a network links advertisement for the network. (If it did, the transition to a new DR would be even faster. However, this is a tradeoff between database size and speed of convergence when the DR disappears.) In some steps of the flooding procedure, the Backup DR plays a passive role, letting the DR do more of the work. This cuts down on the amount of local routing traffic.
Electing the DR
The DR calculation proceeds as follows: Call the router doing the calculation
Router X. The list of neighbors attached to the network and having established
bidirectional communication with Router X is examined. This list is precisely
the collection of Router X's neighbors (on this network) whose state is
greater than or equal to 2-WAY. Router X itself is also considered to be
on the list. Discard all routers from the list that are ineligible to become
DR (routers having router priority of 0) .
The following steps are then executed, considering only those routers that
remain on the list :
Once the DR and the backup DR are elected, OSPF makes every effort to keep them, even if another router subsequently comes up with a higher priority or ID. The reason behind the election algorithm's complexity is the desire for an orderly transition from backup DR to DR, when the current DR fails. This orderly transition is ensured through the introduction of hysteresis: no new backup DR router can be chosen until the old backup accepts its new DR responsibilities.
If router X is not itself eligible to become DR, it is possible that neither a backup DR nor a DR will be selected in the above procedure. Note also that if router X is the only attached router that is eligible to become DR, it will select itself as DR and there will be no backup DR for the network.
to go back to the index press here
The OSPF routing algorithm is based on Dijkstra shortest path algorithm.
the term "Shortest path" is inaccurate because what we really
want to find is the "Optimum path". To find the optimum path
in a network means to find a path with a minimal cost, considering factors
like time , money and quality of the received data. The route is not chosen
only by the cost, because in every network three constraints must be considered
:
if delay is excessive or if throughput is too little, the network does
not meet the needs of the users. The third constraint is quite obvious:
The gateways and networks must be able to reach each other; otherwise,
all other least-cost criteria are irrelevant.
The basic algorithm
--------------
The following general statements describe the preceding discussion :
The process is performed on each node,and a routing table is created
for the node's use. Each node's table is constructed in the same manner
just discussed.
Example : Routing topology for node A
=========================================================================
Step N A(B) A(C) A(D) A(E) A(F) A(G) A(H) A(I) A(J)
-------------------------------------------------------------------------
Initial {A} 8 4 . . . . . . .
1 {A,B} 8 (4) 5 8 . . . 11 .
2 {A,C,D} 7 4 (5) 7 . . . 11 .
3 {A,C,D,B} 7 4 5 (7) 11 . . 11 .
4 {A,C,D,B,E} (7) 4 5 7 11 9 . 11 .
5 {A,C,D,B,E,F} 7 4 5 7 11 (9) 14 11 .
6 {A,C,D,B,E,F,G} 7 4 5 7 11 9 (10) 10 .
7 {A,C,D,B,E,F,G,H} 7 4 5 7 11 9 10 (10) 18
8 {A,C,D,B,E,F,G,H,I} 7 4 5 7 (11) 9 10 10 15
9 {A,C,D,B,E,F,G,H,I,J} 7 4 5 7 11 9 10 10 (15)
------------------------------------------------------------------------
to go back to the index press here
OSPF bases its routing decisions on two fields in the IP datagram: the destination IP address and the TOS. Once the decision is made on how to the IP datagram, the datagram is routed without additional headers; that is, no additional encapsulation occurs. This approach is different from many networks in which PDUs are encapsulated with some type of internal network header to control the routing protocol within the subnetwork.
OSPF is classified as a dynamic, adaptive protocol in that it adjusts to problems in the network and provides short convergence periods to stabilize the routing table. It is also designed to prevent looping of traffic, which is quite important in mesh networks or in LANs where multiple bridges may be available to connect different LANs.
to go back to the index press here
Each router contains a routing directory (called a "routing database"). The database contains information about interfaces at the router that are operable as well as status information about each neighbor to a router. the database is the same for all participating routers.
The information focuses on the topology of the networks with a directed graph. Routers and networks forms the vertices of the graph. Periodically this information is broadcast (flooded) to all the routers in the autonomous system. An OSPF router computes the shortest path to all the other routers in the autonomous system regarding itself as the working node (the root).
A very flexible and powerful approach to this protocol is that separate cost metrics can be computed for each TOS. If the calculations reveal that two paths are of equal value, OSPF will distribute the traffic equally on these paths.
OSPF can support one to many networks. The networks can be grouped into what is termed an "area", and the design of the protocol allows an area to be hidden from other areas. Indeed, an area can be hidden from the full autonomous system.
Due to increasing concerns about security, OSPF includes authentication procedures. Routers must go through some simple procedure to authenticate the traffic between them. we have more to say about the authentication aspects of this protocol shortly.
OSPF works with directed graphs which are quite similar to the Dijkstra algorithm explained before. The graph contains values between two points, either networks or gateway. the values represent the weighted shortest path value, with the router established as the root. Consequently, the shortest path tree from the router to any point in an internet is determined by the router performing the calculation. The calculation only reveals the next hop to the destination in the hop-to-hop forwarding process. The topological database used in the calculation is derived from the information obtained by advertisements of the routers to their neighbors, with periodic flooding throughout the autonomous system.
Thus far we have discussed in general terms how OSPF performs routing within the autonomous system. The method to determine routing information outside the autonomous system is referred to as "external routing". Routing information pertaining to this capability is typically derived from OSPF as well as other protocols, such as the EGP. Alternately, routing information could be established through static routes between the autonomous systems.
Two types of external routing capabilities exist with OSPF. In type 1 external routing, the external metrics are the same as the internal OSPF link state metric. Type 2 external metrics only use the cost of the router to the external autonomous system. The type 2 method is simple and based on the assumption that routing between autonomous systems is the major cost of routing the packet (which in some actual operation is not true). This approach eliminates conversion between internal link state metrics of OSPF and external costs. (in which the autonomous system may have little influence).
The OSPF working group also adapted a very sound concept of autonomous system "areas" in which contiguous networks and hosts may be grouped together. In this situation, each area runs its own SPF algorithm. It also has its own topological database that differs from other areas. The purpose of the area is to isolate and partition portions of the autonomous system and to reduce the amount of information a router must maintain about the full autonomous system. Also, having such an area means that the overhead information transmitted between the routers to maintain OSPF routing tables is substantially reduced.
OSPF uses the term "backbone" to define that part of an autonomous
system conveys packets between areas . The full path of a packet proceeds
as follow:
The resources ( Links, Routers ) of a backbone should be contiguous. This configuration is permissible; the intervening networks simply become "virtual links" within the backbone for the purposes of constructing the topological database.
OSPF utilizes the Hello protocol for advertising state information between neighbors. Hello packets are used to confirm agreements among routers in a common network about a network musk and certain timers (dead intervals , hello interval). In effect, the Hello protocol is used to make certain that neighbor relationship make sense.
to go back to the index press here
Internetworking with TCP/IP
(Vol I) - Comer
Interconnections, Bridges
and Routers - Radia Perlman
TCP/IP Illustrated, Volume
I , The Protocols - W. Richard Stevens
RFC's 1131, 1245, 1253, 1583
to go back to the index press here