Transcript module10bx

Open Shortest Path First (OSPF)
• Uses Link State routing
• Each router acquires complete topology information
using link state updates
• Link-state - what it means:
• Link: That’s the interface of a router.
• State: Description of that interface and how it’s connected to
neighbor routers.
• Link state information must be flooded to all routers
(uses multicasting)
• Cost metric used to calculate shortest paths. Metric
can be any link or network parameter (time,
congestion, bandwidth, $$, distance) or a function that
combines several weighted parameters
• Guaranteed to converge
Link State Routing: Basic principles
1. Routers establish a relationship (“adjacency”) with neighbors.
Two types:
1.
2.
full neighbors: allows exchange of routing information
2way neighbor: no routing information exchange
2. Each router generates link state advertisements (LSAs) which are
distributed to all “adjacent” routers (after all routers have established
adjacencies).
LSA = (link id, state of the link, cost, neighbors of the link)
3. Each router maintains a database (LSDB) of all received LSAs
(topological database or link state database), which describes the
network as a graph with weighted edges
4. Each router uses its link state database to run a shortest path
algorithm (Dijikstra’s algorithm) to produce the shortest path to each
network
2
Operation of a Link State
Routing protocol
Received
LSAs
Dijkstra’s
Algorithm
Link State
Database
LSAs are flooded
to other interfaces
3
IP Routing
Table
Features of OSPF
• Provides authentication of routing messages
• Enables load balancing by allowing traffic to
be split evenly across routes with equal cost
• Type-of-Service routing allows setup of
different routes dependent on the TOS (DS)
field in IP header
• Uses AREAs to subdivide large networks,
providing a hierarchical structure and limits the
multicast LSAs within routers of the same
area. Area 0 is called the backbone area and
all other areas connect directly to it. All OSPF
networks must have a backbone area
4
OSPF Areas
Area Border Routers (ABR) are any routers that have one interface in
one area and another interface in another area
OSPF Operation
• HELLO messages are used to maintain adjacency with
neighbors.
• By default, OSPF routers send Hello packets every 10
seconds on broadcast networks and every 30 seconds on
non-broadcast segments
OSPF Operation contd.
• Link-state routing protocols generate routing updates only when a
change occurs in the network topology.
• When a link changes state, the device that detected the change
creates a link-state advertisement (LSA) concerning that link and
sends it to all neighboring devices using a special multicast
address.
• Each routing device reads the LSA, and updates its link-state
database (LSDB).
• The LSA has a sequence number that allows the router to check
to see if it has already seen that update. If old, it is discarded, if
new, LSDB info updated and LSA passed along to next
neighbors.
• The entire routing table (LSDB) is transmitted once every 30
minutes
Types of OSPF Messages
• There are five types of OSPF Link-State Packets (LSPs).
1. Hello: are used to establish and maintain adjacency
with other OSPF routers. They are also used to elect
the Designated Router (DR) and BackupDesignated
Router (BDR) on multiaccess networks.
2. Database Description (DBD or DD): contains an
abbreviated list of the sending router’s link-state
database and is used by receiving routers to check
against the local link-state database to make sure it
has the latest information
LSPs contd.
3. Link-State Request (LSR): used by receiving
routers to request more information about any
entry in the DBD
4. Link-State Update (LSU): used to reply to LSRs
as well as to announce new information. LSUs
can contain seven different types of Link-State
Advertisements (LSAs)
5. Link-State Acknowledgement (LSAck): sent to
confirm receipt of an LSU message
OSPF Packet Format
OSPF Message
IP header
OSPF Message
Header
OSPF packets are not
carried as UDP or TCP
payload!
OSPF has its own IP
protocol number: 89
TTL: set to 1 (in most cases)
Body of OSPF Message
Message Type
Specific Data
LSA
LSA
Header
Destination IP: neighbor’s IP address or 224.0.0.5
(ALLSPFRouters) or 224.0.0.6 (AllDRouters:
(designated and backup designated only)
LSA
... ...
LSA
LSA
Data
11
OSPF Packet Format
OSPF Message
Header
2: current version
is OSPF V2
Message types:
1: Hello (tests reachability)
2: Database description
3: Link Status request
4: Link state update
5: Link state acknowledgement
Standard IP checksum taken
over entire packet
Body of OSPF Message
version
type
message length
source router IPI address
D
ID of the Area
from which the
packet originated
Area ID
checksum
authentication type
authentication
authentication
32 bits
0: no authentication
1: Cleartext
password
2: MD5 checksum
(added to end
packet)
12
States of Establishing Adjacency
Before establishing an adjacency, OSPF routers need to go through several state
changes.
• Init state – router has received Hello message from other OSFP router
• 2-way state – neighbor has received Hello message and replied with a Hello
message of his own
• Exstart state – beginning of the LSDB exchange between both routers.
• Exchange state – DBD (Database Descriptor) packets are exchanged. DBDs contain
LSAs headers. Routers see what LSAs they need.
• Loading state – one neighbor start by sending LSRs (Link State Requests) for every
network it doesn't know about. The other neighbor replies with the LSUs (Link State
Updates) which contain information about requested links. After all the requested
information has been received, the other neighbor goes through the same process
• Full state (adjacency) - both routers have the synchronized database and are fully
adjacent with each other.
An Example
• Suppose OSPF has just been enabled on R1 & R2. Both
R1 and R2 are very eager to discover if they have any
neighbors nearby but before sending Hello messages
they must first choose an OSPF router identifier (routerid) to tell their neighbors who they are. The Router ID
(RID) is an IP address used to identify the router and is
chosen using the following sequence:
• The highest IP address assigned to a loopback (logical)
interface.
• If a loopback interface is not defined, the highest IP address of
all the active router’s physical interfaces will be chosen.
• The router ID can be manually assigned if necessary
Example contd.
• In this example, suppose R1 has 2 loopback interfaces &
2 physical interfaces:
• Loopback 0: 10.0.0.1
• Loopback 1: 12.0.0.1
• eth0/0: 192.168.1.1
• eth0/1: 200.200.200.1
• The loopback interfaces are preferred to physical
interfaces (because they are never down) so the highest
IP address of the loopback interfaces is chosen as the
router-id -> Loopback 1 IP address is chosen as the
router-id.
Router 1
Router 2
Next Step – Hello Msgs
• Now both the routers have the Router-ID so they
will send Hello packets on all OSPF-enabled
interfaces to determine if there are any neighbors
on those links.
• The information in the OSPF Hello includes the
OSPF Router ID of the router sending the Hello
packet.
Hello Packet Exchange
Hello Packet Content
* Indicates values that have to be the same for both routers if they are
to establish an adjacency, i.e., become neighbors
Description of Hello Values
• Router ID: Each OSPF router needs to have an unique ID which is the highest IP
• address on any active interface. More about this later.
• Hello / Dead Interval: Every X seconds we are going to send a hello packet, if we
don’t hear any hello packets from our network for X seconds we declare you “dead”
and we are no longer neighbors. These values have to match on both sides in order
to become neighbors.
• Neighbors: All other routers who are your neighbors are specified in the hello packet.
• Area ID: This is the area you are in. This value has to match on both sides in order to
become neighbors.
• Router Priority: This value is used to determine who will become designated or
backup designated router.
• DR and BDR IP address: Designated and Backup Designated router for multiple
access networks such as an Ethernet segment.
• Authentication password: You can use clear text and MD5 authentication for OSPF
which means every packet will be authenticated. Obviously you need the same
password on both routers in order to make things work.
• Stub area flag: Besides area numbers OSPF has different area types. Both routers
have to agree on the area type in order to become “neighbors”.
Hello Msg R1 to R2
• R1 wants to find out if it has any neighbor running OSPF
it sends a Hello message to the multicast address
224.0.0.5.
• This is the multicast address for all OSPF routers and all
routers running OSPF will process this message.
Establishing adjacency
• If an OSPF router receives an OSPF Hello packet
that satisfied all its requirements (all * values are
the same) then it will establish adjacency with the
router that sent the Hello packet. In this example,
if R1 meet R2′s requirements, meaning it has:
• the same Hello/Dead interval,
• AREA number,
• Password
• Stub Area Flag
 R2 will add R1 to its neighbor table.
Hello Msg Adjacency Parameters
Exchange DD or DBD packets
• R1 and R2 are neighbors now
• The neighbors must first determine who will be the
master and who will be the slave. The router with higher
Router-ID becomes master and initiates the link
exchange.
• They start by sending Database Description (DD or
DBD) packets which contain an abbreviated list of the
sending router’s link-state database
• The receiver acknowledges a received DD packet by
sending an identical DD packet back to the sender.
• Each DD packet has a sequence number and only the
master can increment sequence numbers.
DD Msg Exchange
Neighbor discovery and
database synchronization
10.1.10.1
Discovery of
adjacency
10.1.10.2
OSPF Hello
OSPF Hello: I heard 10.1.10.2
After neighbors are discovered the nodes exchange their databases
Database Description: Sequence = X
Sends database
description.
(description only
contains LSA
headers)
Acknowledges
receipt of
description
29
Database Description: Sequence = X, 5 6LSA
LSAheaders =
Router-LSA, 10.1.10.1, 0x80000006
Router-LSA,
10.1.10.2, 0x80000007
Router-LSA,
10.1.10.3, 0x80000003
Router-LSA,
10.1.10.4, 0x8000003a
Router-LSA,
10.1.10.5, 0x80000038
Router-LSA,
10.1.10.6, 0x80000005
Database Description: Sequence = X+1, 1 LSA header=
Router-LSA,
10.1.10.2, 0x80000005
Database Description: Sequence = X+1
Sends empty
database
description
Database
description of
10.1.10.2
LSA Request
R1 or R2 can send Request to get missing LSA from its neighbors
LSA Exchange
R2 sends back an
LSAck packet to
acknowledge the
packet
LSA exchanges – Request
and Response
10.1.10.1
Link State Request packets, LSAs =
Router-LSA,
10.1.10.1,
Router-LSA,
10.1.10.2,
Router-LSA,
10.1.10.3,
Router-LSA,
10.1.10.4,
Router-LSA,
10.1.10.5,
Router-LSA,
10.1.10.6,
10.1.10.1 sends
requested LSAs
Link State Update Packet, LSAs =
Router-LSA, 10.1.10.1, 0x80000006
Router-LSA, 10.1.10.2, 0x80000007
Router-LSA, 10.1.10.3, 0x80000003
Router-LSA, 10.1.10.4, 0x8000003a
Router-LSA, 10.1.10.5, 0x80000038
Router-LSA, 10.1.10.6, 0x80000005
Link State Update Packet, LSA =
Router-LSA,
10.1.1.6, 0x80000006
32
10.1.10.2
10.1.10.2 explicitly
requests each LSA
from 10.1.10.1
10.1.10.2 has more
recent (higher
sequence number)
value for 10.0.1.6 and
sends it to 10.1.10.1
Creating LSDBs
• Note that routers first exchange DD msgs that only list
the content of the LSDB but no details.
• Once a router gets that info, it can then check to see if it
has that information in its LSDB.
• If it doesn’t it requests an LSA to fill in the details.
• Reliable transmission: when a router receives an
Update, it sends an Ack to the Update sender.
• If the sender does not receive Ack within a specific
period, it times out and retransmits Update.
• OSPF uses Update-Ack to implement reliable
transmission. It does not use TCP!
Routing Data Distribution
• LSA-Updates are distributed to all other
routers via Reliable Flooding using
multicast addresses.
• Example: Flooding of LSA from 10.10.10.1
10.10.10.1
10.10.10.2
LSA
ACK
LSA
Update
database
Update
database
34
10.10.10.4
10.10.10.2
LSA
ACK
Update
database
LSA
10.10.10.6
Update
database
10.10.10.5
Update
database
Dissemination of LSA-Update
• A router sends and re-floods LSA-Updates,
whenever the topology or link cost changes. (If a
received LSA does not contain new information,
the router will not flood the packet)
• Exception: Infrequently (every 30 minutes), a
router will flood LSAs even if there are no new
updates.
• Acknowledgements of LSA-updates:
• explicit ACK, or
• implicit via reception of an LSA-Update from neighbor.
35
Filling the LSDB
Flow Chart
• In this example a new LSA is arriving at the router and OSPF has to decide
what to do with it:
1. If the LSA isn’t already in the LSDB it will be added and a LSAck
(acknowledgement) will be sent to the OSPF neighbor. The LSA will be
flooded to all other OSPF neighbors and we have to run SPF to update our
routing table.
2. If the LSA is already in the LSDB and the sequence number is the same
then we will ignore the LSA.
3. If the LSA is already in the LSDB and the sequence number is different then
we have to take action:
1.
2.
If the sequence number is higher it means this information is newer and we have
to add it to our LSDB.
If the sequence number is lower it means our OSPF neighbor has an old LSA
and we should help them. We will send a LSU (Link state update) including the
newer LSA to our OSPF neighbor. The LSU is an envelope that can carry
multiple LSAs in it.
Broadcast Environments: Designated
and Backup Designated Router
• To minimize OSPF traffic (LSAs) on broadcast networks, OSPF elects a
Designated Router (DR) and a Backup DR (BDR)
• How do we select a DR/BDR? During the process of becoming OSPF
neighbors, right after the two-way state that’s where routers elect who will
become DR or BDR. Who is going to win the election?
•
•
•
•
The router with the highest priority will become DR.
The router with the second highest priority will become BDR.
If the priority is the same the OSPF router ID is the tiebreaker. Higher wins.
DR/BDR election is non-preemptive. This means if you change the priority or router
ID you have to reset OSPF in order to select a new DR/BDR.
• Routers that are not DR or BDR show up as DROTHER.
• Only DR and BDR have adjacencies (full neighbor) with all routers on the
broadcast segment. The other routers are two-way neighbors. If a non
designated router has an update, the LSA is sent to the designated routers
using the 224.0.0.6 address. The LSA is then sent by the designated router to
all the routers on the broadcast segment using multicast address 224.0.0.5.
Example
Full neighbor state
Router Status
And router Susan (the BDR) sees the DR and DROTHER.
Two-way neighbor state
Choosing DR and BDR
• We can change which router becomes the DR/BDR by playing
with the priority.
• You change the priority if you like by using the ip ospf priority
command:
• The default priority is 1.
• A priority of 0 means you will never be elected as DR or BDR.
• You need to use clear ip ospf process before this change takes effect.
• Let’s turn router Nancy in the DR:
• Donna is still the DR, we need to reset the OSPF neighbor
adjacencies so that we’ll elect the new DR and BDR.
Susan is now DRother
Nancy is now DR
By Multiple Access not By Area
• Something you need to be aware of is that the DR/BDR election is
per multi-access segment…not per area!
• In the example below we have 2 multi-access segments. Between
router Donna and Nancy, and between router Donna and Susan.
For each segment there
will be a DR/BDR election.
You can see that router Nancy
is the DR for the 192.168.12.0/24
segment and router Susan is the
DR for the 192.168.23.0/24 segment.
Point to Point Links
• For a point-to-point link running say HDLC. You can see that we
have a neighbor but we didn’t do an election for DR or BDR.
Makes sense because there is always only one router on the
other side.
192.168.12.0
.1
.2
Link Cost and Path Choice
• What about the link metric? OSPF uses a metric called cost which is based on
the bandwidth of an interface, it works like this:
• Cost = Reference Bandwidth / Interface Bandwidth
• The reference bandwidth is a default value on Cisco routers which is a 100Mbit
interface.
• You divide the reference bandwidth by the bandwidth of the interface and you’ll
get the cost.
• Example: If you have a 100 Mbit interface what will the cost be?
• Cost = Reference bandwidth / Interface bandwidth
• 100 Mbit / 100 Mbit = COST 1
• Example: If you have a 10 Mbit interface what will the cost be?
• 100 Mbit / 10 Mbit = COST 10
• Example: If you have a 1 Mbit interface what will the cost be?
• 100 Mbit / 1 Mbit = COST 100
• The lower the cost the better the path is.
• If we have links that are > 100M the reference bandwidth is changed to always
have a link cost that is >1
OSPF LSA Types
• OSPF has many different types of LSAs:
• LSA Type 1: Router LSA
• LSA Type 2: Network LSA
• LSA Type 3: Summary LSA
• LSA Type 4: Summary ASBR LSA
• LSA Type 5: Autonomous system external LSA
• LSA Type 6: Multicast OSPF LSA (NOT USED)
• LSA Type 7: Not-so-stubby area LSA
• LSA Type 8: External attribute LSA for BGP
Router LSA
• Each router within the area will flood a type 1
router LSA within the area.
• In this LSA you will find a list with all the directly
connected links of this router.
• The router LSA will always stay within the area.
Network LSA
• The network LSA or type 2 is
created for multi-access network
that have a DR/BDR.
• If this is the case you will see
these network LSAs being
generated by the DR.
• The other routers in the segment
generate a type 1 LSA to inform
the DR of an update.
• In the type 2 LSA we will find all
the routers that are connected to
the multi-access network, the DR,
BDR, and the prefix and subnet
mask.
• The network LSA always stays
within the area.
Multi Area LSAs
• Type 1 router LSAs always stay within the area. OSPF however
works with multiple areas and you probably want full connectivity
within all of the areas. Router Nancy is flooding a router LSA within
the area so router Donna will store this in her LSDB.
• Router Mary and Susan also need to know about the topology in
Area 2.
• Router Donna is going to create a Type 3 summary LSA and
flood it into area 0. This LSA will flood into all the other areas of our
OSPF network. This way all the routers in other areas will know about
the prefixes from other areas.
An outside RIP Router
• In this example we have router Nancy who is redistributing information from the
RIP router into OSPF. This makes router Nancy an ASBR (Autonomous
System Border Router).
• Router Nancy will flip a bit in her router LSA to identify herself as an ASBR.
• When router Donna who is a ABR receives this router LSA she will create a
type 4 summary ASBR LSA and flood it into area 0.
• This LSA will also be flooded in all other areas and is required so all OSPF
routers know where to find the ASBR.
Outside Network
• Same topology but we’ve added a prefix (5.5.5.0 /24) at our RIP router. This
prefix will be redistributed into OSPF.
• Router Nancy (our ASBR) will take care of this and create a type 5 external
LSA for this that will contain the external network prefix.
• We still need type 4 summary ASBR LSA to locate router Nancy.
OSPF Tables
• There are 3 type of tables stored at a Router:
• Neighbor
• Topology
• Routing
Neighbor Table
• Contain information about the neighbors
• Neighbor is a router which shares a link on same
network
• Another relationship is adjacency
• Not necessarily all neighbors
• LSA updates are only when adjacency is
established
Topology Table
• Contains information about all networks and
paths to reach any network
• All LSA’s are entered into the topology table
• When topology changes, LSA’s are generated
and router sends new LSA’s
• Using the topology table a shortest path
connectivity graph is created (routing table), the
algorithm is known as SPF or Dijkstra’s algorithm
Routing Table
• Also known as forwarding database
• Generated when an algorithm is run on the
topology database
• Routing table for each router is unique