Routing Information Protocol in Computer Networks.ppt

Routing Information 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. UNICAST ROUTING PROTOCOLSUNICAST ROUTING PROTOCOLS
Today, an internet can be so large that one
routing protocol cannot handle the task of
updating the routing tables of all routers. For
this reason, an internet is divided into
autonomous systems.
An autonomous system (AS) is a group of
networks and routers under the authority of a
single administration.
Routing inside an autonomous system is called
intra-domain routing. Routing between
autonomous systems is called inter-domain
routing.

3. 22.3
Figure 22.12 Autonomous systems

4. INTERNET STRUCTUREINTERNET STRUCTURE
At a lower level, , there are some provider there are some provider
networks that use the backbones for global networks that use the backbones for global
connectivity but provide services to Internet connectivity but provide services to Internet
customers. customers.
Finally, there are some consumer networks that that
use the services provided by the provider use the services provided by the provider
networks. networks.
Any of these three entities (backbone, provider Any of these three entities (backbone, provider
network, or customer network) can be network, or customer network) can be called an called an
Internet Service Provider (ISP). Internet Service Provider (ISP). They provide They provide
services, but at different levels.services, but at different levels.

5. UNICAST ROUTING PROTOCOLSUNICAST ROUTING PROTOCOLS
The The routing protocol run in each AS is
referred to as intra-AS routing protocol, to as intra-AS routing protocol, intra intra
domain routing protocol, domain routing protocol, or interior gateway or interior gateway
protocol (IGP); protocol (IGP);
The global routing protocol is referred to as is referred to as
inter-AS routing protocol, inter-AS routing protocol, inter domain inter domain
routing protocol, or exterior gateway protocol routing protocol, or exterior gateway protocol
(EGP). (EGP).
Presently, the two common Presently, the two common intra domain
routing protocols are RIP and OSPF; the only
inter domain routing protocol is BGP.

6. 22.6
Unicast Routing Protocols

7. Autonomous SystemAutonomous System
Autonomous System are categorized Autonomous System are categorized according to the according to the
way they are connected to other ASs. We have way they are connected to other ASs. We have stub ASs,
multihomed ASs, and transient ASs..
Stub AS. Stub AS. A stub AS has A stub AS has only one connection to another
AS. The data traffic can be either initiated or terminated in . The data traffic can be either initiated or terminated in
a stub AS. Example : Consumer Networka stub AS. Example : Consumer Network
Multihomed AS. Multihomed AS. A multihomed AS can have A multihomed AS can have more than
one connection to other ASs, , but it does not allow data but it does not allow data
traffic to pass through it. Example Consumer network get traffic to pass through it. Example Consumer network get
service from morethan one provider network.service from morethan one provider network.
Transient AS. Transient AS. A transient AS is A transient AS is connected to more than
one other AS and also allows the traffic to pass through. to pass through.
The provider networks and the backbone are good The provider networks and the backbone are good
examples of transient ASs.examples of transient ASs.

8. Areas in an autonomous system

9. Routing Information protocol (RIP)Routing Information protocol (RIP)

The Routing Information Protocol (RIP) is an intra-
domain (interior) routing protocol used inside an
autonomous system.

It is a very simple protocol based on distance
vector routing.

RIP implements distance vector routing directly
with some considerations.

10. Routing Information protocol (RIP)Routing Information protocol (RIP)
Hop CountHop Count
A router in this protocol basically implements the A router in this protocol basically implements the
distance-vector routing algorithmdistance-vector routing algorithm..
The The cost is defined as the number of hopscost is defined as the number of hops, which , which
means the number of networks (subnets) a packet means the number of networks (subnets) a packet
needs to travel through from the source router to the needs to travel through from the source router to the
final destination hostfinal destination host
Figure 8.15 shows the concept of hop count Figure 8.15 shows the concept of hop count
advertised by three routers from a source host to a advertised by three routers from a source host to a
destination host. destination host.
RIP can be used only in autonomous systems in RIP can be used only in autonomous systems in
which the diameter of the AS is not more than 15 which the diameter of the AS is not more than 15
hops. hops.

11. Routing Information protocol (RIP)Routing Information protocol (RIP)

12. Routing Information protocol (RIP)Routing Information protocol (RIP)
Forwarding TablesForwarding Tables
The The routers in an autonomous system need to keep
forwarding tables to forward packets to their
destination networks.
A A forwarding table in RIP is a three-column table forwarding table in RIP is a three-column table
in which the in which the first column first column is the address of the is the address of the
destination network, the destination network, the second column second column is the is the
address of the next router to which the packet should address of the next router to which the packet should
be forwarded, and the be forwarded, and the third column third column is the cost (the is the cost (the
number of hops) to reach the destination network.number of hops) to reach the destination network.
A forwarding table in RIP A forwarding table in RIP defines only the next
router in the second column,, it gives the information it gives the information
about the whole least-cost treeabout the whole least-cost tree..

13. Routing Information protocol (RIP)Routing Information protocol (RIP)

14. RIP ImplementationRIP Implementation
RIP is implemented as a process RIP is implemented as a process that uses the service of User that uses the service of User
Datagram Protocol (UDP) on the well-known port number 520. Datagram Protocol (UDP) on the well-known port number 520.
RIP is a daemon process RIP is a daemon process (a process running at the (a process running at the
background), background),
RIP is a routing protocol to help IP RIP is a routing protocol to help IP route its datagrams route its datagrams
through the AS, through the AS,
 RIP runs at the application layer, RIP runs at the application layer, but creates forwarding tables but creates forwarding tables
for IP at the network later. for IP at the network later.
RIP has gone through two versions: RIP has gone through two versions: RIP-1 and RIP-2RIP-1 and RIP-2. .
The second version is backward-compatible with the first The second version is backward-compatible with the first
section; section;
It allows the use of more information in the RIP messages that It allows the use of more information in the RIP messages that
were set to 0 in the first version. We discuss only RIP-2 in this were set to 0 in the first version. We discuss only RIP-2 in this
section. section.

15. RIP MessagesRIP Messages
Two RIP processes, Two RIP processes, a client and a server, like any other a client and a server, like any other
processes, need to exchange messages. processes, need to exchange messages. RIP-2 defines the format RIP-2 defines the format
of the message, as shown in Figure 8.17. of the message, as shown in Figure 8.17.
RIP has two types of messages: request and response. RIP has two types of messages: request and response.
A request message is sent by a router that has just come up or A request message is sent by a router that has just come up or
by a router that has
 some time-out entries
by a router that has
 some time-out entries
. .
A request message can ask A request message can ask about specific entries or all entriesabout specific entries or all entries. .
A response (or update) message can be either A response (or update) message can be either solicited or solicited or
unsolicitedunsolicited. .
A solicited response A solicited response message is message is sent only in answer to a request sent only in answer to a request
message. It contains information about the destination specified message. It contains information about the destination specified
in the corresponding request message. in the corresponding request message.
An An unsolicited response unsolicited response message, on the other hand, is message, on the other hand, is sent sent
periodically, every 30 s or when there is a change in the periodically, every 30 s or when there is a change in the
forwarding tableforwarding table

16. 22.16
RIP Message Format

17. RIP AlgorithmRIP Algorithm
RIP RIP implements the implements the same algorithm as the distance-same algorithm as the distance-
vector routing algorithm vector routing algorithm ..
However, some changes need to be made to the However, some changes need to be made to the
algorithm algorithm to enable a router to update its forwarding to enable a router to update its forwarding
table: table:
Instead of sending only distance vectors, Instead of sending only distance vectors, a router needs a router needs
to send the whole contents of its forwarding table in a to send the whole contents of its forwarding table in a
response message. response message.
The receiver adds one hop to each cost and changes The receiver adds one hop to each cost and changes
the next router field to the address of the sending router. the next router field to the address of the sending router.
We call each route in the modified forwarding table the We call each route in the modified forwarding table the
received route and each route in the old forwarding table received route and each route in the old forwarding table
the old route. The received router selects the old routes the old route. The received router selects the old routes
as the new ones except in the following three cases:as the new ones except in the following three cases:

18. RIP AlgorithmRIP Algorithm
1.If the received 1.If the received route does not exist in the old route does not exist in the old
forwarding tableforwarding table, it should be added to the route. , it should be added to the route.
2. If the 2. If the cost of the received route is lower than the cost of the received route is lower than the
cost of the old onecost of the old one, the received route should be , the received route should be
selected as the new one. selected as the new one.
3. If the 3. If the cost of the received route is higher than the cost of the received route is higher than the
cost of the old one, but the value of the next router is cost of the old one, but the value of the next router is
the same in both routesthe same in both routes, the received route should be , the received route should be
selected as the new one. selected as the new one.
The The new forwarding table needs to be sorted new forwarding table needs to be sorted
according to the destination routeaccording to the destination route

19. 22.19

20. Timers in RIPTimers in RIP
RIP uses three timers RIP uses three timers to support its operation. to support its operation.
The The periodic timer periodic timer controls the advertising of regular update controls the advertising of regular update
messages. Each router has one periodic timer that is randomly set messages. Each router has one periodic timer that is randomly set
to a number between 25 and 35 s (to prevent all routers sending to a number between 25 and 35 s (to prevent all routers sending
their messages at the same time and creating excess traffic).their messages at the same time and creating excess traffic).
The expiration timer The expiration timer governs the validity of a route. When a governs the validity of a route. When a
router receives update information for a route, router receives update information for a route, the expiration the expiration
timer is set to 180 s for that particular routetimer is set to 180 s for that particular route. Every time a new . Every time a new
update for the route is received, the timer is reset. Every route has update for the route is received, the timer is reset. Every route has
its own expiration timer. its own expiration timer.
The garbage collection timer The garbage collection timer is used to clean a route from the is used to clean a route from the
forwarding table. When the information about a route becomes forwarding table. When the information about a route becomes
invalid, the router does not immediately purge that route from its invalid, the router does not immediately purge that route from its
table.table.

21. 22.21
Timers in RIPTimers in RIP

22. Performance of RIPPerformance of RIP
Update messages. The update messages in RIP have a very simple
format and are sent only to neighbors; they are local.

Convergence of forwarding tables. RIP uses the distance-vector
algorithm, which can converge slowly if the domain is large, but, because
RIP allows only 15 hops in a domain (16 is considered as infinity), there is
normally no problem in convergence.

Robustness. As we said before, distance-vector routing is based on
the concept that each router sends what it knows about the whole domain
to its neighbors. This means that the calculation of the forwarding table
depends on information received from immediate neighbors, which in
turn receive their information from their own neighbors. If there is a
failure or corruption in one router, the problem will be propagated to all
routers and the forwarding in each router will be affected.

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

24. 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. We cost from a router to the destination host network. We
can compare Figure 8.19 with Figure 8.15 for the RIP.can compare Figure 8.19 with Figure 8.15 for the RIP.

25. 22.25

26. 22.26
Areas in an autonomous system

27. 22.27
Figure 22.25 Types of links

28. 22.28
Figure 22.26 Point-to-point link

29. 22.29
Figure 22.27 Transient link

30. 22.30
Figure 22.28 Stub link

31. 22.31
Figure 22.29 Example of an AS and its graphical representation in OSPF

32. 22.32
Figure 22.30 Initial routing tables in path vector routing

33. 22.33
Figure 22.31 Stabilized tables for three autonomous systems

34. 22.34
Figure 22.32 Internal and external BGP sessions

35. 22.35
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:

36. 22.36
Figure 22.33 Unicasting

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

38. 22.38
Figure 22.34 Multicasting

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

40. 22.40
Figure 22.35 Multicasting versus multiple unicasting

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

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

43. 22.43
Figure 22.36 Shortest path tree in unicast routing

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

45. 22.45
Figure 22.37 Source-based tree approach

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

47. 22.47
Figure 22.38 Group-shared tree approach

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

49. 22.49
Figure 22.39 Taxonomy of common multicast protocols

50. 22.50
Multicast link state routing uses the
source-based tree approach.
Note

51. 22.51
Flooding broadcasts packets, but
creates loops in the systems.
Note

52. 22.52
RPF eliminates the loop in the
flooding process.
Note

53. 22.53
Figure 22.40 Reverse path forwarding (RPF)

54. 22.54
Figure 22.41 Problem with RPF

55. 22.55
Figure 22.42 RPF Versus RPB

56. 22.56
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

57. 22.57
Figure 22.43 RPF, RPB, and RPM

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

59. 22.59
Figure 22.44 Group-shared tree with rendezvous router

60. 22.60
Figure 22.45 Sending a multicast packet to the rendezvous router

61. 22.61
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

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

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

64. 22.64
PIM-SM is used in a sparse multicast
environment such as a WAN.
Note

65. 22.65
PIM-SM is similar to CBT but uses a
simpler procedure.
Note

66. 22.66
Figure 22.46 Logical tunneling

67. 22.67
Figure 22.47 MBONE