Open Shortest Path First (OSPF)
Introduction
Routing Protocols link state are acknowledged because of their complexity much larger than its equivalent distance vectors. But, the funtionality and basic configurations of the routing protocols link state aren't complexes at all.
The Open Shortest Path First (OSPF) protocol, defined in RFC 2328, is an Interior Gateway Protocol used to distribute routing information within a single Autonomous System.
OSPF is a routing protocol link state, and as its own name says, it uses spf algorithm (dijkstra). This algorithm accumulates costs among every route, since the begining to the end. While the algorithm is called Dijkstra's algorithm Shortest first path, this is indeed the goal of every routing algorithm.
Justification
OSPF was chosen to aproach it, because according to CISCO is one of the best interior gateway protocol. It has overcome a lot of mistakes that the oders protocols (IGP) had.
This routing protocol link state also present lot of features for helping us to enhance the performance of the network topology.
Background Information
OSPF protocol was developed due to a need in the internet community to introduce a high functionality non-proprietary Internal Gateway Protocol (IGP) for the TCP/IP protocol family. The discussion of the creation of a common interoperable IGP for the Internet started in 1988 and did not get formalized until 1991. At that time the OSPF Working Group requested that OSPF be considered for advancement to Draft Internet Standard.
The OSPF protocol is based on link-state technology, which is a departure from the Bellman-Ford vector based algorithms used in traditional Internet routing protocols such as RIP. OSPF has introduced new concepts such as authentication of routing updates, Variable Length Subnet Masks (VLSM), route summarization, and so forth.
Development
Shortest Path First Algorithm
OSPF uses a shorted path first algorithm in order to build and calculate the shortest path to all known destinations.The shortest path is calculated with the use of the Dijkstra algorithm. The algorithm by itself is quite complicated. This is a very high level, simplified way of looking at the various steps of the algorithm.
The algorithm places each router at the root of a tree and calculates the shortest path to each destination based on the cumulative cost required to reach that destination. Each router will have its own view of the topology even though all the routers will build a shortest path tree using the same link-state database. The following sections indicate what is involved in building a shortest path tree.
OSPF Cost
The cost (also called metric) of an interface in OSPF is an indication of the overhead required to send packets across a certain interface. The cost of an interface is inversely proportional to the bandwidth of that interface. A higher bandwidth indicates a lower cost. There is more overhead (higher cost) and time delays involved in crossing a 56k serial line than crossing a 10M ethernet line. The formula used to calculate the cost is:
· cost= 10000 0000/bandwith in bps
For example, it will cost 10 EXP8/10 EXP7 = 10 to cross a 10M Ethernet line and will cost 10 EXP8/1544000 = 64 to cross a T1 line.
By default, the cost of an interface is calculated based on the bandwidth; you can force the cost of an interface with the ip ospf cost <value> interface subconfiguration mode command.
Shortest Path Tree
Assume we have the following network diagram with the indicated interface costs. In order to build the shortest path tree for RTA, we would have to make RTA the root of the tree and calculate the smallest cost for each destination.
The above is the view of the network as seen from RTA. Note the direction of the arrows in calculating the cost. For example, the cost of RTB's interface to network 128.213.0.0 is not relevant when calculating the cost to 192.213.11.0. RTA can reach 192.213.11.0 via RTB with a cost of 15 (10+5). RTA can also reach 222.211.10.0 via RTC with a cost of 20 (10+10) or via RTB with a cost of 20 (10+5+5). In case equal cost paths exist to the same destination, Cisco's implementation of OSPF will keep track of up to six next hops to the same destination.
After the router builds the shortest path tree, it will start building the routing table accordingly. Directly connected networks will be reached via a metric (cost) of 0 and other networks will be reached according to the cost calculated in the tree.
Areas and Border Routers
As previously mentioned, OSPF uses flooding to exchange link-state updates between routers. Any change in routing information is flooded to all routers in the network. Areas are introduced to put a boundary on the explosion of link-state updates. Flooding and calculation of the Dijkstra algorithm on a router is limited to changes within an area. All routers within an area have the exact link-state database. Routers that belong to multiple areas, and connect these areas to the backbone area are called area border routers (ABR). ABRs must therefore maintain information describing the backbone areas and other attached areas.
An area is interface specific. A router that has all of its interfaces within the same area is called an internal router (IR). A router that has interfaces in multiple areas is called an area border router (ABR). Routers that act as gateways (redistribution)between OSPF and other routing protocols (IGRP, EIGRP, IS-IS, RIP, BGP, Static) or other instances of the OSPF routing process are called autonomous system boundary router (ASBR). Any router can be an ABR or an ASBR.
Enabling OSPF on the Router
Enabling OSPF on the router involves the following two steps in config mode:
1. Enabling an OSPF process using the router ospf <process-id> command.
2. Assigning areas to the interfaces using the network <network or IP address> <mask> <area-id> command.
OSPF Authentication
It is possible to authenticate the OSPF packets such that routers can participate in routing domains based on predefined passwords. By default, a router uses a Null authentication which means that routing exchanges over a network are not authenticated. Two other authentication methods exist: Simple password authentication and Message Digest authentication (MD-5).
The Backbone and Area 0
OSPF has special restrictions when multiple areas are involved. If more than one area is configured, one of these areas has be to be area 0. This is called the backbone. When designing networks it is good practice to start with area 0 and then expand into other areas later on.
The backbone has to be at the center of all other areas, i.e. all areas have to be physically connected to the backbone. The reasoning behind this is that OSPF expects all areas to inject routing information into the backbone and in turn the backbone will disseminate that information into other areas. The following diagram will illustrate the flow of information in an OSPF network:
In the above diagram, all areas are directly connected to the backbone. In the rare situations where a new area is introduced that cannot have a direct physical access to the backbone, a virtual link will have to be configured. Virtual links will be discussed in the next section. Note the different types of routing information. Routes that are generated from within an area (the destination belongs to the area) are called intra-area routes. These routes are normally represented by the letter O in the IP routing table. Routes that originate from other areas are called inter-area or Summary routes. The notation for these routes is O IA in the IP routing table. Routes that originate from other routing protocols (or different OSPF processes) and that are injected into OSPF via redistribution are called external routes. These routes are represented by O E2 or O E1 in the IP routing table. Multiple routes to the same destination are preferred in the following order: intra-area, inter-area, external E1, external E2. External types E1 and E2 will be explained later.
Virtual Links
Virtual links are used for two purposes:
· Linking an area that does not have a physical connection to the backbone.
· Patching the backbone in case discontinuity of area 0 occurs.
Neighbors
Routers that share a common segment become neighbors on that segment. Neighbors are elected via the Hello protocol. Hello packets are sent periodically out of each interface using IP multicast (Appendix B). Routers become neighbors as soon as they see themselves listed in the neighbor's Hello packet. This way, a two way communication is guaranteed. Neighbor negotiation applies to the primary address only. Secondary addresses can be configured on an interface with a restriction that they have to belong to the same area as the primary address.
Two routers will not become neighbors unless they agree on the following:
1. Area-id
2. Authentication
3. Hello and Dead Intervals
4. Stub area flag
Adjacencies
Adjacency is the next step after the neighboring process. Adjacent routers are routers that go beyond the simple Hello exchange and proceed into the database exchange process. In order to minimize the amount of information exchange on a particular segment, OSPF elects one router to be a designated router (DR), and one router to be a backup designated router (BDR), on each multi-access segment. The BDR is elected as a backup mechanism in case the DR goes down. The idea behind this is that routers have a central point of contact for information exchange. Instead of each router exchanging updates with every other router on the segment, every router exchanges information with the DR and BDR. The DR and BDR relay the information to everybody else. In mathematical terms, this cuts the information exchange from O(n*n) to O(n) where n is the number of routers on a multi-access segment. The following router model illustrates the DR and BDR:
Summaries
Summary Links Advertisements are sent by Area Border Routers and by default they advertise every individual network within each area to which it is connected. Networks can be condensed into a network summary so reducing the number of Summary Links Advertisements being sent and reduces the LSDB's of routers outside the area. In addition, if there is a network change then this will not be propagated into the backbone and other areas so minimising the recalculation of SPF.
There are two types of summarisations:
· Inter-Area Route Summarisation is carried out on ABRs and applies to routes from within each area rather than external routes redistributed into OSPF.
· External Route Summarisation is specific to external routes redistributed into OSPF.
A summary is configured by defining a range within which the subnets that need to be summarised fall. The range is made up of an address and a summary mask, the address encompasses the range of subnetworks to be included within the summary and the mask describes the range of addresses.
Using the network in the following diagram, summaries can be created to illustrate the process:
Within Area 1: The summary address is 128.128.16.0 because of the way summarising works. This forms the bottom of the range of addresses within the summary mask of 255.255.240.0 and gives available addresses up to 128.128.31.0, see below:
All the network possibilities from 16 to 31 are defined by the mask (third octet of 240), the existing networks can be added to. If 17 had been used as the summary address instead of 16, then the third octet would be 00010001, the problem here is that a subnet bit is set to '1' in the host area of the address. The system will not use bits that are set to '1', it only increments from '0' to '1', this means that subnet 19 would be ignored, and 21 etc. etc. The other areas can be summarised in a similar manner.
If an Area Border Router does not have an interface in area 0.0.0.0 then a virtual link needs to be created between an Area Border Router that is connected to the backbone and ends at an Area Border Router of the non-contiguous area. The virtual link is tied to the least-cost path through the 'Transit area' between the backbone and the non-contiguous area. An adjacency is formed between the two routers and the timers need to be identical.
External Routes
In order to make non-OSPF networks available to routers within an OSPF network, the router connected to the non-OSPF network needs to be configured as an AS Boundary Router (ASBR). As described earlier AS External Link Advertisements (one for each external route) are flooded into the OSPF network (except Stub networks). There are two types of metric for external detinations:
· Type-1 destination networks: The cost to an external network directly connected to the ASBR (close) plus the internal path cost within the OSPF network gives the total cost.
· Type-2 destination networks: The cost to a 'far away' network (i.e. not directly connected to the ASBR) is merely the number of hops from the ASBR to the external network.
If a number of routes to a network are advertised to an internal OSPF router, then the router picks the Type-1 route rather than the Type-2 route. If this router learns the route via different protocols then it decides which route to use based on firstly the preference value (configurable) and then on route weight (non-configurable).
Redistributing Routes into OSPF
Redistributing routes into OSPF from other routing protocols or from static will cause these routes to become OSPF external routes. To redistribute routes into OSPF, use the following command in router configuration mode:
redistribute protocol [process-id] [metric value]
[metric-type value] [route-map map-tag] [subnets]
Note: The above command should be on one line.
The protocol and process-id are the protocol that we are injecting into OSPF and its process-id if it exits. The metric is the cost we are assigning to the external route. If no metric is specified, OSPF puts a default value of 20 when redistributing routes from all protocols except BGP routes, which get a metric of 1. The metric-type is discussed in the next paragraph.
The route-map is a method used to control the redistribution of routes between routing domains. The format of a route map is:
route-map map-tag [[permit | deny] | [sequence-number]]
When redistributing routes into OSPF, only routes that are not subnetted are redistributed if the subnets keyword is not specified.
Conclusion
The OSPF protocol defined in RFC 1583, provides a high functionality open protocol that allows multiple vendor networks to communicate using the TCP/IP protocol family. Some of the benefits of OSPF are, fast convergence, VLSM, authentication, hierarchical segmentation, route summarization, and aggregation which are needed to handle large and complicated networks.
BIBLIOGRAPHY
2. http://www.youtube.com/watch?v=a_CQfAbVktQ
No hay comentarios:
Publicar un comentario