Open Shortest Path First Protocol in Computer Networks.ppt

Open Shortest Path First Protocol in Computer Networks

1. 22.1
UNIT-IV
Unicast Routing
Protocols
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.

2. Open Shortest Path First (OSPF)
Open Shortest Path First (OSPF) Open Shortest Path First (OSPF) is also is also
an intra domain routing protocol like RIP, an intra domain routing protocol like RIP,
but it is based on the link-state routing but it is based on the link-state routing
protocol. protocol.
OSPF is an open protocolOSPF is an open protocol, which means , which means
that the specification is a public documentthat the specification is a public document
...

3. Open Shortest Path First (OSPF)
MetricMetric
In OSPF, like RIP, the cost of reaching a the cost of reaching a
destination from the host is calculated from the source destination from the host is calculated from the source
router to the destination network. However, router to the destination network. However, each link
(network) can be assigned a weight based on the
throughput, round-trip time, reliability, and so on. .
An administration can also decide to use the hop count An administration can also decide to use the hop count
as the cost. An interesting point about the cost in as the cost. An interesting point about the cost in OSPF OSPF
is that different service types (TOSs) can have different is that different service types (TOSs) can have different
weights as the cost. weights as the cost. Figure 8.19 shows the idea of the Figure 8.19 shows the idea of the
cost from a router to the destination host network. cost from a router to the destination host network.

4. 22.4

5. Open Shortest Path First (OSPF)
Forwarding TablesForwarding Tables
Each OSPF router Each OSPF router can create a can create a
forwarding table after finding the shortest-forwarding table after finding the shortest-
path tree between itself and the destination path tree between itself and the destination
using Dijkstra’s algorithmusing Dijkstra’s algorithm. .
Figure 8.20 shows the forwarding tables Figure 8.20 shows the forwarding tables
for the simple AS in Figure 8.19. for the simple AS in Figure 8.19.
Comparing the forwarding tables for the Comparing the forwarding tables for the
OSPF and RIP OSPF and RIP in the same AS, we find in the same AS, we find
that the only that the only difference is the cost valuesdifference is the cost values. .

6. 22.6

7. Open Shortest Path First (OSPF)

Compared with RIP, which is normally used in
small ASs, OSPF was designed to be able to
handle routing in a small or large autonomous
system.

Although this may not create a problem in a
small AS, it may have created a huge volume of
traffic in a large AS.

To prevent this, the AS needs to be divided
into small sections called areas.

8. Open Shortest Path First (OSPF)

OSPF uses another level of hierarchy in
routing: The first level is the autonomous
system, the second is the area.

one of the areas in the AS is designated as
the backbone area, responsible for gluing the
areas together.

The routers in the backbone area are
responsible for passing the information
collected by each area to all other areas.

9. 22.9

10. Open Shortest Path First (OSPF)
OSPF is based on the link-state routing algorithm,
which requires that a router advertise the state of each link
to all neighbors for the formation of the LSDB

The different types of links that connect each node to
its neighbors, and the different types of cost associated
with each link.

We can have five types of link-state advertisements:
router link, network link, summary link to network,
summary link to AS border router, and external link. Figure
8.22 shows these five advertisements and their uses.

11. 22.11

12. Open Shortest Path First (OSPF) - Implementation

OSPF is implemented as a program in the network layer
that uses the service of the IP for propagation.

An IP datagram that carries a message from OSPF sets
the value of the protocol field to 89.

OSPF has gone through two versions: version 1 and
version 2. Most implementations use version 2

13. Open Shortest Path First (OSPF) - Messages

OSPF is a very complex protocol.
it uses five different
types of messages.

In Figure 8.23, we first show the format of the OSPF
common header (which is used in all messages) and the
link-state general header (which is used in some
messages).

14. 22.14
OSPF Common Header and General Header

15. Open Shortest Path First (OSPF) - Messages

We then give the outlines of five message types used in
OSPF. The hello message (type 1) is used by a router to
introduce itself to the neighbors and announces all
neighbors that it already knows.

The database description message (type 2) is normally
sent in response to the is normally sent in response to the
hello message to allow a newly joined router to acquire the
full LSDB.

16. Open Shortest Path First (OSPF) - Messages

The link-state request message (type 3) is sent by a
router that needs information about a specific LS.

The link-state update message (type 4) is the main
OSPF message used for building the LSDB.

The link-state acknowledgment message (type 5) is
used to create reliability in OSPF; each router that receives
a link-state update message needs to acknowledge it.

17. 22.17
OSPF Message Types

18. Open Shortest Path First (OSPF) - Algorithms

OSPF implements the link-state routing algorithm.

However, some changes and augmentations need to be
added to the algorithm:

After each router has created the shortest-path tree, the
algorithm needs to use it to create the corresponding
routing algorithm.

The algorithm needs to be augmented to handle
sending and receiving all five types of messages.

19. Open Shortest Path First (OSPF) - Performance

Update messages. The link-state messages in OSPF have a somewhat
complex format. They also are flooded to the whole area. If the area is large,
these messages may create heavy traffic and use a lot of bandwidth.

Convergence of forwarding tables. When the flooding of LSPs is
completed, each router can create its own shortest-path tree and forwarding
table; convergence is fairly quick. However, each router needs to run the
Dijkstra’s algorithm, which may take some time.

Robustness. The OSPF protocol is more robust than RIP because, after
receiving the completed LSDB, each router is independent and does not
depend on other routers in the area. Corruption or failure in one router does
not affect other routers as seriously as in RIP.

20. 22.20
Figure 22.25 Types of links

21. 22.21
Figure 22.26 Point-to-point link

22. 22.22
Figure 22.27 Transient link

23. 22.23
Figure 22.28 Stub link

24. 22.24
Figure 22.29 Example of an AS and its graphical representation in OSPF

25. 22.25
Figure 22.30 Initial routing tables in path vector routing

26. 22.26
Figure 22.31 Stabilized tables for three autonomous systems

27. 22.27
Figure 22.32 Internal and external BGP sessions

28. 22.28
22-4 MULTICAST ROUTING PROTOCOLS22-4 MULTICAST ROUTING PROTOCOLS
In this section, we discuss multicasting and multicast In this section, we discuss multicasting and multicast
routing protocols. routing protocols.
Unicast, Multicast, and Broadcast
Applications
Multicast Routing
Routing Protocols
Topics discussed in this section:Topics discussed in this section:

29. 22.29
Figure 22.33 Unicasting

30. 22.30
In unicasting, the router forwards the
received packet through
only one of its interfaces.
Note

31. 22.31
Figure 22.34 Multicasting

32. 22.32
In multicasting, the router may
forward the received packet
through several of its interfaces.
Note

33. 22.33
Figure 22.35 Multicasting versus multiple unicasting

34. 22.34
Emulation of multicasting through
multiple unicasting is not efficient
and may create long delays,
particularly with a large group.
Note

35. 22.35
In unicast routing, each router in the
domain has a table that defines
a shortest path tree to possible
destinations.
Note

36. 22.36
Figure 22.36 Shortest path tree in unicast routing

37. 22.37
In multicast routing, each involved
router needs to construct
a shortest path tree for each group.
Note

38. 22.38
Figure 22.37 Source-based tree approach

39. 22.39
In the source-based tree approach, each
router needs to have one shortest path
tree for each group.
Note

40. 22.40
Figure 22.38 Group-shared tree approach

41. 22.41
In the group-shared tree approach, only
the core router, which has a shortest
path tree for each group, is involved in
multicasting.
Note

42. 22.42
Figure 22.39 Taxonomy of common multicast protocols

43. 22.43
Multicast link state routing uses the
source-based tree approach.
Note

44. 22.44
Flooding broadcasts packets, but
creates loops in the systems.
Note

45. 22.45
RPF eliminates the loop in the
flooding process.
Note

46. 22.46
Figure 22.40 Reverse path forwarding (RPF)

47. 22.47
Figure 22.41 Problem with RPF

48. 22.48
Figure 22.42 RPF Versus RPB

49. 22.49
RPB creates a shortest path broadcast
tree from the source to each destination.
It guarantees that each destination
receives one and only one copy
of the packet.
Note

50. 22.50
Figure 22.43 RPF, RPB, and RPM

51. 22.51
RPM adds pruning and grafting to RPB
to create a multicast shortest
path tree that supports dynamic
membership changes.
Note

52. 22.52
Figure 22.44 Group-shared tree with rendezvous router

53. 22.53
Figure 22.45 Sending a multicast packet to the rendezvous router

54. 22.54
In CBT, the source sends the multicast
packet (encapsulated in a unicast
packet) to the core router. The core
router decapsulates the packet and
forwards it to all interested interfaces.
Note

55. 22.55
PIM-DM is used in a dense multicast
environment, such as a LAN.
Note

56. 22.56
PIM-DM uses RPF and pruning and
grafting strategies to handle
multicasting.
However, it is independent of the
underlying unicast protocol.
Note

57. 22.57
PIM-SM is used in a sparse multicast
environment such as a WAN.
Note

58. 22.58
PIM-SM is similar to CBT but uses a
simpler procedure.
Note

59. 22.59
Figure 22.46 Logical tunneling

60. 22.60
Figure 22.47 MBONE