CS计算机代考程序代写 database Slide 1

Slide 1

CMPT 471
Networking

OSPF
© Janice Regan, 2006-2017

© Janice Regan, 2006-2017
2
OSPF messages
Encapsulated in IP datagrams
5 types of messages, all message types begin with a common header
Message types are
Hello
establish and test neighbor reachability (two OSPF router may be neighbors if they are on the same network segment)
elect designated routers on multi access networks
Database description (initial router network topology database)

© Janice Regan, 2006-2017
3
OSPF messages
5 types of messages, all message types begin with a common header including
Link status request used for forming adjacencies
Adjacencies are agreements to exchange LSAs,
adjacencies are formed with designated routers for multi access networks, and neighbors
Link status update (also used for forming adjacencies) LSAs
Link status acknowledgement (ACKs each link status update message)

© Janice Regan, 2006-2017
4
link state advertisements (1)
Router link advertisement
Originated by all routers
Flooded throughout a single area only
Describes the states of the router’s interfaces to the area
Network link advertisement
Originated by broadcast networks
Flooded throughout a single area only
Contains a list of routers connected to the network

© Janice Regan, 2006-2017
5
link state advertisements (2)
Summary link advertisement
Originated by border area routers
Flooded throughout a area and backbone
Describes a route outside the local area but within the AS
AS external link advertisement
Originated by AS boundary area routers
Flooded throughout the AS
Contains a route to a destination outside the AS in another AS

© Janice Regan, 2006-2017
6
Maintaining databases
Each router originates some LSAs, routes to neighbor networks, and for designated routers routes to each router the is part of its group.
The LSAs originating at a router are flooded through the local area each time they are updated, an periodically (every 30 minutes)
Summary LSA’s are sent by border area routers to provide summary information on their areas through the backbone to other areas

© Janice Regan, 2006-2017
7
Flooding protocol: conditions
A message(LSA) contains a database record. A database record contains information about one link between two routers in the graph discussed earlier. (one link is in one direction)
Each message contains a time stamp or message number
These message numbers are used by the receiving node to determine age of the record
Send means transmit through all attached interfaces except the one on which the incoming message arrived

© Janice Regan, 2006-2017
8
Flooding protocol
Receive message: Find the corresponding record in the local database if it exists
If the record is not yet in the local database add the record. Send the message
If the record’s message number is larger than the message number in the data base, replace the message in the database with the new record. Send the message.
If the records message number is the same as the message number in the database do nothing
If the records message number is smaller than the message number in the database, send the record in the database back through the interface on which the message arrived

© Janice Regan, 2006-2017
10
OSPF header fields
Version: specifies version being used, currently 2
Type: see slide 23 for details
Message length: length of the packet in octets
Source router IP: IP address of the router wishing to send the message
Area ID: identify the area the router is a part of (backbone routers have an Area ID of 0)
Checksum: computed for the whole OSPF packet (excluding the authentication field)
Authentication type: 0 for none 1 for 8 character password 2 for cryptographic authentication

© Janice Regan, 2006-2017
11
The Hello protocol
Hello is used
To check that links are operational.
To initiate and maintain neighbor relationships. Two routers on the same network segment may become neighbors
To maintain the connectivity
To elect the designated router
To elect the backup designated router

© Janice Regan, 2006-2017
13
Hello message fields (1)
Network mask: the network/subnetwork mask of the network to which the interface connects
Dead timer: If an update LSA is not received within the dead time the neighbor relationship is broken (dead time > hello interval)
Hello interval: interval between sending of successive Hello packets

© Janice Regan, 2006-2017
14
Hello message fields (2)
Gway priority: priority of the router, each router is configured with a set priority. These priorities are used in the election of designated routers
Designated Router: Address of the designated router or 0 if no router has yet been designated.
Backup Designated Router: Address of the backup designated router or 0 if no router has yet been designated.

© Janice Regan, 2006-2017
15
Hello message fields (3)
Neighbor IP addresses
When a router receives a hello message from another router it adds the IP address of the router that sent that hello message to it’s list of neighbors
For any subsequent Hello messages sent by the receiving router the IP address of the sending router is included in the list of neighbors of the sending router (in the hello message)

INIT
DOWN
2WAY

Hello received
Does not contain my address

ExSTART

Hello received
Does contain my address
NO Hello received
before end of deadtime interval
DR and BDR elected

© Janice Regan, 2006-2017
17
States: Interface state machine
Down:
The initial state of a neighbor conversation.
Indicates that no recent information (hello’s) have been received from the other router
Init:
A Hello packet has just been seen from the other router. Bidirectional communication has not yet been established ( the receiving router’s IP did not appear in the Hello packet received from the other router).
The IP of the other router will be listed in the subsequent Hello packets sent
2-way:

© Janice Regan, 2006-2017
18
States: Interface state machine
Down:
Init:
2-way:
Bidirectional communication has established
A Hello packet containing this routers address has been received from the other router. The two routers are now neighbors
The (Backup) Designated Router is selected from the set of neighbors in state 2-Way or greater.

© Janice Regan, 2006-2017
19
Uses for HELLO messages
The hello protocol
establishes neighbor relationships
Maintains neighbor relationships, checks that links are operating
elects designated (DR)
elects backup designated routers (BDR)

© Janice Regan, 2006-2017
20
Maintaining Neighbor relationships
Each router will send Hello messages to its neighbors once each Hello interval. These messages will contain the addresses of all neighbors
Messages are encapsulated in UDP packets so may not arrive (best effort delivery)
The ‘dead interval’ is usually ≥3X the Hello interval
Each time a hello message containing router A’s address is received the ‘dead timer’ for the neighbor relation with A is reset to the ‘dead interval’
The neighbor relationship is broken when no ‘hello’ is received from neighbor A before the dead timer expires

© Janice Regan, 2006-2017
21
DR election and booting
After a router is booted OSPF will be in a “waiting” state for up to a “waiting interval” equal to the dead time. During this interval
Hello packets are sent, but the router will not propose itself for election as DR or BDR
Information in received Hello packets will be saved
At the end of the “waiting” period the BDR and DR are elected based on accumulated information from the received hello packets.
The addresses of the elected routers are included in subsequent Hello messages

© Janice Regan, 2006-2017
22
DR election and booting
After a router is booted OSPF will be in a “waiting” state for up to a “waiting interval” equal to the dead time. During this interval
When leaving the waiting state the router may
Accept the election of other routers as both DR and BDR and form adjacencies with both the BDR and the DR
Become DR (will not replace a previously elected DR)
Become BDR (will not replace a previously elected BDR)

Waiting
DOWN
DR

Interface turned on
BDR

DR Other

© Janice Regan, 2006-2017
24
Backup designated router
A router cannot declare itself both BDR and DR
If no router has declared itself a BDR in its hello packet, (by inserting their own address in the BDR field) then
Routers that are declared to be DR by having their own address in the designated router field of some LSA’s from other routers are ignored
The router with the highest priority (that is not declared as DR) will be declared BDR

© Janice Regan, 2006-2017
25
Backup designated router
If some routers have a declared themselves backup designated routers in their Hello packets then the declared designated backup router with the highest priority is elected backup designated router.
If no routers have declared themselves designated routers in their hello packets, the backup designated router is promoted to be designated router. Then a new backup designated router is elected

© Janice Regan, 2006-2017
26
Electing designated routers
If some routers have a declared themselves designated router in their Hello packets then the declared designated router with the highest priority is elected designated router.
If a new DR or BDR has been declared repeat the procedure for determining BDR and DR. This assures that no router is both DR and BDR
See the protocol for more details on this process

© Janice Regan, 2006-2017
27
Adjacency
Routers establish an adjacency if they will be exchanging LSAs.
The DR for a network segment will have adjacency relationships with
Neighbors on that network segment
DR for each attached network or network segment
A router that attaches to n networks and is not the DR for any of those networks will be adjacent to the DR for each network it attaches to.
LSAs are exchanged between routers with adjacency relationships (established and maintained by the HELLO protocol)

EXCHANGE
ExStart
LOADING

Negotiation done

FULL

Exchange done
Transfer done

© Janice Regan, 2006-2017
29
Synchronizing of databases
Uses an exchange protocol
When an adjacency relationship is established between two routers the databases of those two routers need to be synchronized
Initial synchronization is done using the exchange protocol
Subsequently synchronization is maintained through the other protocols within OSPF
If a adjacency is broken an then reestablished the synchronization using the exchange protocol will be repeated.

© Janice Regan, 2006-2017
31
Fields: Database Description
I,M,S: Bits used to indicate master/slave status and router initiating the exchange
Database sequence number: Unique number labeling a particular database synchronization procedure
Database record description: the remaining information in the DD message (link type, link id, advertising router … )

© Janice Regan, 2006-2017
32
Synchronizing databases : 1
One of the adjacent routers is declared the master the other is declared the slave. The master is the router that initiates the exchange. The master is responsible for retransmission
The master sends an initialization packet (setting sequence number) with I=M=S=1
The slave acks with the same sequence number and I=M=1 S=0
Negotiation complete, the router moves into EXCHANGE state
I-initial M-more S master 1/slave 0

© Janice Regan, 2006-2017
33
Synchronizing databases : 2
The master then sends a database description (DD) packets describing the next link in its database. I=0 M=S=1
The slave sends a DD packet describing the next link in its own database in response. I=S=0 M=1. This packet is treated as an ACK of the masters packet. If the ACK is not received the master will retransmit its packet
This procedure repeats until all database description information has been exchanged. If the master runs out of records before the slave it will continue sending empty DD packets until it receives an ACK with M set to 0 indicating the slave has completed sending its database information

© Janice Regan, 2006-2017
34
Synchronizing databases: 3
When the master or slave receives a DD message it will compare the record to its own database.
It will check to see if there is a record with the same description
If the record is not in their database they will place the description in the ‘records to request’ list
It will check the sequence number (age) to see if the received record is newer
If the received record is newer they will place the description in the ‘records to request’ list

© Janice Regan, 2006-2017
35
Synchronizing databases: 4
When the records to request list on both the master and slave are complete
All database records in the master’s database have been compared to the slave’s database
All database records in the slave’s database have been compared to the master’s database
The routers move into LOADING state

© Janice Regan, 2006-2017
36
Processing the records to request list
Each record on the records to request list will be requested using a link state request message. One link state request message may request several record updates
Each record update requested is described by three pieces of data, link type, link id, and advertising router
In response to a received link state request the router will build a link state update message containing the data in the requested records
Each time an update message is received in response the request message the corresponding entry in the ‘records to request’ list is removed.

/docProps/thumbnail.jpeg

Related Posts