A link-state protocol builds three databases:
The first database is known as the neighbor or adjacency database. It keeps track of other routers on directly
connected networks.
The second database is the link-state database (LSDB) or topology database. This database keeps track of the
state of the links on other routers on the network. Link-state routers periodically send out “hello” messages to
neighboring routers as a type of keep-alive message. A router running the OSPF protocol will also periodically
send out link-state advertisements (LSAs), which are flooded across an internetwork. These messages contain
information on the router’s active links, its IP address, subnet mask, and the routers it knows about. The
information stored in the topology database is ultimately used to calculate the shortest path to a destination
network. It is also used to create the final database, the routing table.
The third database is the routing table, sometimes called the forwarding database. It is used by the router to
accurately forward IP packets to the destination network.
SPF Calculation:-
Link-state information is sent periodically and during topology changes to ensure topological database
synchronization.
LSAs are sourced by the router that is connected to the link that changes.
LSAs are flooded by all other routers.
LSAs are transmitted at each link-state change
In a link-state environment, routers use the sequence numbers for the following decisions when they receive linkstate
updates:
If the sequence number is lower than the one in the database, the link-state information is discarded and the
more recent update is sent back instead of an acknowledgment.
If the sequence number is the same as the one in the database, an ACK is sent. The link-state information is then
discarded.
If the sequence number is higher, the link-state information is populated in the topological database, an ACK is
sent, and the link-state information is forwarded to its neighbors
The basic flow of a packet of data through a network is as follows:
Device A (1.1.1.2) wants to send data to server D (2.2.2.2). Because device A is not located on the same segment
as device D, it must use the default gateway for the segment. This default gateway is seen as IP address 1.1.1.1
in the slide above. Device A will use address resolution protocol (ARP) to learn the MAC address of the gateway
from the IP address. The router responds with the MAC address of router B. Device A is now able to encapsulate
the data, as shown in the top block diagram. Note that the source and destination IP addresses identify the
overall source and destination devices, whereas the frame source and destination addresses identify the path
across the Ethernet segment only.
When the data arrives at the left router (router B), the router removes the L2 header and trailer, checks its
routing table, and determines that the data needs to be sent to the right router (router C). To accomplish this,
router B encapsulates the data in a PPP frame of data and forwards it.
Router C removes the PPP frame and consults its routing table. Seeing that the destination IP network is directly
connected to its Ethernet port, router C creates the frame of data and forwards it to device D.
When a router receives a packet to be forwarded, the basic forwarding rules are as follows:
First, the router compares the destination IP address in the received packet to the entries in the forwarding
information base (FIB), commonly called the routing table. The router performs a bit-by-bit comparison of
the destination IP address to these entries, searching for the entry that matches with the most common bits.
This matching algorithm is called longest-match or most-specific-match routing.
If no entries match any bits, the packet is discarded and, in most cases, an ICMP Unreachable message is sent
to the source.
If a matching entry in the FIB is located, the router requires two elements from the entry in the FIB to
forward the packet. First, the egress or outbound interface for the packet must be known, so that the router
can encapsulate the packet in the appropriate frame for forwarding toward the destination. Second, the
next-hop IP address must be known, so that the frame may be addressed and forwarded to the next router
(unless the packet destination is local to the router, in which case the frame is addressed to the destination
itself).
Control Plane and Data Plane
A typical IP router has two distinct functional components:
Control plane functionality
Data plane functionality
The 7750 SR physically separates the two functions:
Control plane functions are performed by the CPM
Data plane functions are performed by the IOMs
Control plane
Supports the operation and management of the router
Supports dynamic routing protocols to communicate with other routers
Builds the FIB and distributes it to the data plane
Data plane
Processes and forwards packets received on the physical interfaces
Distance vector routing algorithms (Bellman-Ford) pass periodic copies of a routing table from router to router.
Regular timed-interval updates between routers communicate changes in the network topology. With distance vector
routing protocols, no routing table is transmitted beyond the immediate neighbor. The distance vector algorithm
allows network metrics to accumulate and maintains a table showing the next hop for all destinations listed in the
table.
***********************************************************************Ospf************************************************************
1> Each router uses the Dijkstra algorithm to calculate the shortest path first this is also known as SPF.
2> Update is triggered when a state change occurs on a particular link.
3> Periodic hello messages are sent to maintain the connectivity.
4> OSPF updates uses ip header with a protocol number of 89.
5> SPF uses cost to determine the best path to a destination.
6> Cost=Reference bandwidth/ bandwidth
7> The reference bandwidth is 100 gbps.
8> The cost is configurable.
9> OSPF uses multicast address to communicate with its peers this is done to ensure the nodes which are not running ospf does not have to process these packets.
10> The addresses used are 224.0.0.5 and 224.0.0.6
11> Given below is the topology of the OSPF packet with the header details:-
Given below is the ospf header:-
These fields are always present during all ospf packets.
The OSPF header breaks down into the following fields:
1. Version number — Identifies the version of OSPF that this packet pertains to. Alcatel-Lucent only supports
OSPFv2.
2. Type — The type of packet that is being received. There are five different types of packet, described on
the following page.
3. Packet length — The overall size of the packet. This does not include the IP header but does include all
bytes in the OSPF update.
4. Router ID — The Router ID of the sending router.
5. Area ID — The area that the router is sending the packet from. All routers connected to a network must
agree on which area the network resides in.
6. Checksum — The CRC (similar to FCS) for the OSPF header.
7. Authentication type — All OSPF protocol exchanges can be authenticated. This means that only trusted
routers can participate in autonomous system routing. Alcatel-Lucent’s implementation of OSPF supports
simple password (plain-text) and MD5 authentication.
8. Authentication — When packets are sent with authentication invoked, this field is used to convey the
authentication information. MD5 allows one authentication key to be configured per network. Routers in
the same routing domain must be configured with the same key. When the MD5 hashing algorithm is used
for authentication, MD5 is used to verify data integrity by creating a 128-bit message digest from the data
input. The message digest is unique to that data. Alcatel-Lucent’s implementation of MD5 allows the
migration of an MD5 key by using a key ID for each unique key.
9. Data — This field varies depending on the type of OSPF packet being sent.
13> there are 5 different packet types for ospf as explained below:-
Packet Types
OSPF has five types of packets:
OSPF hello
OSPF database description
OSPF link-state request
OSPF link-state update
OSPF link-state ACK
14> Router ID
Each router must have a router ID, an ID by which the router is
known to OSPF.
The default RID is the last 32 bits of the chassis MAC address.
Configuring a system interface overrides the default.
— Using a system interface is easier to document.
15> Area ID
The area that this packet belongs to.
16> Check Sum
The standard IP checksum of the entire contents of the packet,
starting with the OSPF packet header, but excluding the 64-bit
authentication field.
17> To stop a router accepting invalid routing updates authentication is configured by default there is no authentication
18> To stop a attacker trying to maliciously disrupt the internet work hence authentication is enabled it is a 64 bit field.
19> MD5 authentication allows a authentication key to be configured per network
20> Simple authentication is also supported although it is not very secure.
21> OSPF hello packet Type 1 this is used to discover neighbor and form adjacencies.
In a broadcast network adjacency is formed between the DR and the BDR
23> In ptop network adjacencies are formed between the neighbors.
24> When an adjacency is formed both the routers wxchage LSDB.
25> Routers that do not form adjacent remains in a 2 way state.
Given above is an illustration of the ospf hello packet each part of the hello packet is described below:-
Type of packet used for hello is 1.
27> Network Mask:- This is the network mask for which the hellos are sent.
28> Hello interval:- This is the interval between which the hellos are sent, by defalt it is 10 seconds and the adjacency is brought down if no hellos are received from the neighbor within 40 seconds.
29> Options
This consists of two bits
E bit :- This is set to indicate that the router is not in a stub area. If this is set to 0 it means the router is present in a stub area.
N bit:- This indicates the NSSA capability of the router if a N bit is set on a particular interface for hello packet it means the router is capable of sending and receiving type 7 LSA.
30> Router Priority:- The priority effects the election of the DR and BDR in a broadcast network by default the priority is 1 if the priority is 0 it can never take part in a DR/BDR election.
31> Router Dead interval:- This is 40 seconds 4 times the hello interval
32> Designated Router: The field denotes the elected DR
33> BDR:- This field denotes the BDR
34> Neighbor:- The RID of the neighbor is displayed in this, routers which receives the hellos looks for this field to ensure that the router sending the hellos known them.
35> After the hellos are exchanged DBD packets are exchanged the router with the lower RID becomes master and start sending DBD packets to the slave.
Given above is a snapshot of the DD packets.
37> This contains a snapshot of the network in the LSA header field.
Typically this contains LSA type,sequence number, age and checksum.
38> The receiving router compares the network, subnet mask, and sequence number with its existing topology
database entries.
If the advertised network is unknown, or if the network is known but the advertised sequence is higher, the
receiving router requests more information about the network so that it can add the network to its
database.
If the network is already known and the sequence number is lower, the receiving router sends back an LSU
with more up-to-date information.
If the network is already in the database and the sequence numbers are identical, the receiving router
discards the information.
Options ― The Options field allows OSPF routers to support (or not support) optional capabilities, and to
communicate their capability level to other OSPF routers. Through this mechanism, routers of differing
capabilities can be mixed within an OSPF routing domain.
I-bit ― The Init bit. When set to 1, this packet is the first in the sequence of Database Description Packets.
M-bit ― The More bit. When set to 1, it indicates that more Database Description Pacets are to follow.
MS-bit ― The Master/Slave bit. When set to 1, it indicates that the router is the master during the Database
Exchange process. Otherwise, the router is the slave.
DD sequence number ― Used to sequence the collection of Database Description Packets. The initial value
(indicated by the Init bit set) should be unique. The DD sequence number then increments until the complete
database description has been sent.
It also contains an interface MTU.
39> After exchanging the DD packets a router may find some of its topological database is out of order or not properly updated in those cases it will ask for an update from the neighbor with the help of Link state request packets.
LSR identifies the networks for which the router wants full informaion
40> This request is made with the precise LS sequence number, LS Age and LS Checksum.
41>
Link state update packets are sent in response to a link state request packets.
42> These carries the LSA.
43> Several LSA's might be present in an LSU packet.
44> Each advertisement requested is specified by its LS type, Link State ID, and Advertising Router to uniquely
identify the advertisement.
45> Link State Update packets are multicast on those physical networks that support multicast/broadcast. In order
to make the flooding procedure reliable, flooded advertisements are acknowledged in Link State
Acknowledgment packets. If retransmission of certain advertisements is necessary, the retransmitted
advertisements are always carried by unicast Link State Update packets.
The LSR requests more information for those networks which is missing from the originating router.
46>
By default, the Alcatel-Lucent 7750 SR sends as much information as the network link can support. The size of
the packet is limited by the interface MTU.
An issue most frequently observed between OSPF routers is a MTU mismatch. This is when the maximum
transmission unit (MTU) settings for neighboring router interfaces do not match. If the router with the higher
MTU sends a packet larger that the MTU set on the neighboring router, the neighboring router ignores the
packet.The LSA's are stacked inside the LSU update messages.
47> To verify that the LSU are received properly link state acknowledgement is sent to the neighbouring router.48>To make the flooding of link state advertisements reliable, flooded advertisements are explicitly acknowledged.
This acknowledgment is accomplished through the sending and receiving of Link State Acknowledgment packets.
Multiple link state advertisements can be acknowledged in a single Link State Acknowledgment packet.
Depending on the state of the sending interface and the source of the advertisements being acknowledged, a
Link State Acknowledgment packet is sent either to the multicast address AllSPFRouters or as a unicast.
Above is a snapshot of the link state acknowledgementWhen the connection between two OSPF routers is a point-to-point link, there is no need for a DR or BDR. All
packets are sent using the 224.0.0.5 IP multicast address. This implementation is typically used on serial
interfaces; however, it can also be configured on point-to-point Ethernet segments, in which only two routers
are connected.
To significantly improve adjacency forming and network convergence, a network should be configured as pointto-
point if only two routers are connected, even if the network is a broadcast media such as Ethernet.
On a multi-access network, a Designated Router (DR) is elected. The DR is responsible for representing the
multi-access network and all the routers on it to the rest of the network, and is also responsible for the
management of the flooding process. The network itself becomes a pseudo-node; the pseudo-node is
represented by the DR and all other routers peer with the DR, which informs them of any changes on the multiaccess
network.Each router sends hellos.X The router with the highest priority is the DR.X
RID.If all priorities are the same, the DR is the router with the highestX
The DR is responsible for sending the LSA which reduces the network traffic.
All the other routers peers up with the DR
So the other routers forms adjacencies with the DR only and they exchange routing updates, with the other routers they form a neighbor relationship with 2-way.
Given below is a snapshot:-DR is non-preemptive (DR does not change once decided).
Routers use the 224.0.0.6 IP address to send updates to the DRs.X The BDR monitors the DR to ensure that it sends updates.X
Given below is an example:-The DR uses 224.0.0.5 to send updates to all OSPF routers.
When a new router becomes active in a multi-access broadcast topology, it generates a hello (type 1) packet.
The multicast address used is 224.0.0.5, which is the "all OSPF devices" address.
hello does not contain any neighbor RIDs because it has not yet seen any neighbors on the link.
This hello protocol will not only mention the RID of its own router, it will also mention the RID of router E and all the RID's in the network
Router C will also let Router E know the DR and the BDR in the network
The new router now sends the updates to the DR using the multicast address of 224.0.0.6 other routers will not respond as it only listens to 224.0.0.5
The DR sends an update to all the routers using the address 224.0.0.5, and awaits a LS ACK from all the other routers.
If there is a network change the following things occur:-As soon as the router detects the failure of a link (a link-state change), it immediately sends an update to
the DRs using the IP multicast address of 224.0.0.6.
2. The DR compares the update received with its topology database and sees that there is a change. It
generates an LSU and sends it to all OSPF speakers on the segment, using the IP multicast address of
224.0.0.5.
3. All devices, including the BDR and the originating router, acknowledge the LSU.
4. Any router that is connected to other networks forward the LSU packet to its downstream neighbors on
those networks.
There are 7 states for the OSPF :-Down
Initializing
2-Way
Exstart
Exchange
Loading
Full
When the interfaces are enabled for OSPF first hellos will be exchanged:-
The state changes from Down to Initializing:-
Both the routers exchanges the hellos and both observes the RID of the neighbor router, after both the router observes the RID of the neighbor router the state is changed to 2-Way.
Since the priority for both the routers are the same hence the router with the highest RID will become the DR.
The hello sent from R5 will set both the DR and BDR to the egress interface ip address
RTR4 once it receives the hello from R5 will compare with its own RID since its RID is lower it will consider R5 as the DR and populates the same in the hello protocol that it sends to R5.
Next the DD packets are sent as seen above the router with the higher RID becomes the master and sends the DD packets first with a sequence number.
Interface MTU is also negotiated during this process.
This is the exstart state.
R4 sends an DBDESC packet to R5 with the DB summary message and the sequence number negotiated in the exstart state is used
The same DB_DESC is seen by R5 also as seen in the below diagram.
This phase is known as exchange state.
The sequence number is incremented by R5.
The DB_DESC packet is first sent by R5 (higher RID) however the DBDESC with the LSA information is first sent by the slave router R4.
R5 will send a request for the LSA which it does not have in its database.
Same is true for R4.
This state is known as exchange state.
Next the LS_Update messages are exchanged between the two routers with full LSA information the routers still stays in the exchange state.
During this phase the state also changes to loading.
To validate that the Lsupdate is received an LSACK is sent by both the routers after it receives the Lsupdate message the neighborship now changes to Full.
OSPF areas:-
An OSPF network can be divided into sub-domains called areas, which are a logical collection of OSPF networks,
routers, and links that have the same area identification.
A router within an area must maintain a topological database for the area to which it belongs. However, it does
not have any detailed information about network topologies outside of its own area, thus the size of its
database is reduced.
The link-state database (LSDB) of each router within the same area must be synchronized to be exactly the
same. The main benefit of creating areas is a reduction in the number of routes to propagate.
LSA describes the state of a router or network including the router interfaces
From the
topological database, each router constructs a tree of shortest paths, with itself as root. From this tree, OSPF
can determine the best route to every destination in the network. The SPF tree is used to construct the routing
table.
Router 1 LSA:-
This includes all the active interfaces of the router, and are advertised within an area only.
Advertises with the ip-prefix/masks assigned to that link.
Link state ID is the advertising routers RID.
This is how the Router LSAtype 1 looks like:-
LS Age
a self-originated LSA from the area databases. It does this by prematurely "aging out" the LSA; that is, setting
the age of the LSA to MaxAge and then flooding the LSA. Receiving routers, seeing the MaxAge value, do a direct
acknowledgment and immediately reflood the LSA.―Gives the time, in seconds, since the LSA originated. The LSA age is used when a router wants to flush―Represents the optional capabilities supported by the router, such as option E that is used to indicate―Represents the types of LSA―Defines the identity of the link-state―Detects old or duplicate LSAs―Performs checksum on the LSA, not including LS age. An LSA can be corrupted during flooding or―Includes the length of the LSA, including the 20-byte header
Bit V — This bit is used to determine whether it is an endpoint of a virtual link.Bit E
Notice that this is different from the option E bit, discussed in the previous slide.— This bit is used to determine whether this router is an Autonomous System Boundary Router (ASBR).Bit B — This bit is used to determine whether this router is an Area Border Router (ABR).Number of Links
links in a single LSA for an area.— This includes the number of router links. Note that the router LSA includes all of the routerLink ID, Link Data, and Type
Link ID and Link Data, represent the 4-byte IP address value, depending on the network type. For links to transit
networks, numbered point-to-point links, and virtual links, the link data field contains the IP interface address
of the associated router interface. For links to stub networks, the field contains the stub network's IP address
mask. For unnumbered point-to-point links, the link data field is set to the unnumbered interface's ifIndex value.— The Type field represents the four types of router links. The other two fields,ToS and ToS Metric — These fields represents the type of service and are normally set to 0.Metric
can have a cost of 0. All other networks must have a cost of nonzero.
X
X
X
unnumbered point-to-point network. The link ID is set to the IP interface address, the link data field is set
to the mask /32 (indicating a host route), and the cost is set to 0.
Suppose if there are 6 routers in the area hence the number of Router LSA that will be present in the database is 6.
Type 1 (router) LSA for rtr1 in Area 0:X Link State ID is set to RID 1.1.1.1.X Number of links is 3: the system interface, interface to-rtr1, and interface to-rtr3.X The interface type between the routers is broadcast.Description of the link between rtr1 and rtr2:
X There is an adjacency; therefore, add a type 2 (transit network) link.X Link ID is set to the IP address of the DR (10.10.2.2).X
responsible for generating type 2 (network) LSAs.The link data field is set to the router’s own address (10.10.2.2); rtr1 is the DR for this network and isX The cost is equal to 1000.Description of the system interface:
X This is a loopback interface; therefore, add a type 3 (stub network) link.X Link ID is set to the IP interface address (1.1.1.1).X The link data field is the IP interface subnet mask (255.255.255.255).X The cost is set to 0.Description of the link between rtr1 and rtr3:
X There is an adjacency; therefore, add a type 2 (transit network) link.X Link ID is set to the IP address of the DR (10.10.3.2).X
responsible for generating type 2 (network) LSAs.The link data field is set to the router’s own address (10.10.3.1); rtr3 is the DR for this network and isX
Routers in a stub area do not have this value set.
Recall that options value E indicates that the originating router is in a backbone, transit, or non stub area.
If the interface is a loopback, a type 3 link (stub network) is added, as long as this is not an interface to anIf the link is down, the link is not added to the router LSA.If the link does not belong to area 1, the link is not added to the router LSA.The router examines its interfaces.— This field contains the OSPF cost of using a specific link. This is a configurable value. Stub networks Length LS Checksum
while kept in the memory, so this checksum is necessary. This field cannot have a value of 0 because 0 means
that the checksum has not been performed. The checksum is performed at the time of LSA generation or when
the LSA is received LS Sequence Number LSA ID LS Type Options
the originating router area type; when set, it indicates whether the originating area is a backbone, transit or
non-stub area.
No comments:
Post a Comment