CSCI 4550/8556

Computer Networks
Internet Routing

Department of Information Technology, TIST IT7/ACN/AGK

 Routing in the Global Internet
• The global internet is too large for each
router to maintain complete
information:
• Instead, a two-level routing hierarchy is
used.
• Interior and Exterior Protocols

Department of Information Technology, TIST IT7/ACN/AGK

 Exterior and Interior Protocols
• An Exterior Gateway Protocol (EGP) is used to
exchange routing information with a router in
another autonomous system.
– More complex, but more flexible than IGPs.
– Summarizes routing information before passing it on.
– Can use policy constraints to restrict information
release to the outside.
• Routers within an autonomous system use an
Interior Gateway Protocol (IGP) to exchange
information.
– There are several different IGPs available.
– Usually easy to install and operate.
– Each has its own limitations.

Department of Information Technology, TIST IT7/ACN/AGK

 IGP/EGP Illustration

Department of Information Technology, TIST IT7/ACN/AGK

 Optimal Routes, Routing Metrics, and IGPs

• Optimal routes are selected using

routing metrics comprised of two
components:
– administrative cost – assigned
manually to reflect organizational
routing policies
– hop count – reflects actual number of
routers/networks in a path

Department of Information Technology, TIST IT7/ACN/AGK

 Optimal Routes, Routing Metrics, and IGPs

• IGPs use routing metrics to find optimal

routes within an autonomous system,
since the routing metrics are consistent
within the organization.
• EGPs do not use routing metrics, since
they have no basis for comparing the
metrics used by different autonomous
systems.

Department of Information Technology, TIST IT7/ACN/AGK

 • IGP (Interior Gateway Protocol)
– RIP
– OSPF

Department of Information Technology, TIST IT7/ACN/AGK

 The Routing Information Protocol
(RIP)
• RIP, one of the first IGP protocols
used with IP.
• RIP’s chief advantage is simplicity.
– Is an Interior Gateway Protocol
– Measures distance in hops (1 hop
to an adjacent network)
– Uses UDP for all routing messages

Department of Information Technology, TIST IT7/ACN/AGK

 The Routing Information Protocol
(RIP)
– Intended for use on LANs; version 1
uses broadcast, version 2 allows
multicast
– Allows routers to advertise a default
route
– Uses the distance-vector routing
algorithm, with route advertisements
giving (destination, distance) pairs.
– Allows hosts to retrieve routing
information

Department of Information Technology, TIST IT7/ACN/AGK

 RIP Packet Format

Department of Information Technology, TIST IT7/ACN/AGK

 RIP Packet Format
• RIP packets contain
– An address and subnet mask for each
network
– Next hop address and distance for each net
– Address family (2 for IP)
– A command (1=request, 2=response, others
obsolete)
– Route tags to allow entries to be grouped

Department of Information Technology, TIST IT7/ACN/AGK

 Open Shortest Path First Protocol
(OSPF)
• RIP messages contain complete lists of
destinations and distances, making
them large. It works well with a small
number of routers but doesn’t scale
well.
• A newer protocol, OSPF, that can scale
to large organizations was devised by
the IETF.

Department of Information Technology, TIST IT7/ACN/AGK

 Open Shortest Path First Protocol
(OSPF)
• OSPF is an Interior Gateway Protocol.
• Subnet masks are included with network
addresses.
• Message exchanges can be authenticated.
• Routes can be imported from other sources
(e.g. BGP).
• Uses the link-state routing (SPF) algorithm
(based on Dijkstra’s shortest path algorithm)
• Designates a single router on broadcast
networks to handle all broadcasts (rather
than having each router broadcast)

Department of Information Technology, TIST IT7/ACN/AGK

 OSPF Example

(a) An internetwork consisting of seven networks

interconnected by routers
(b) a corresponding OSPF graph. In the simplest case,
each router corresponds to a node in the graph.

Department of Information Technology, TIST IT7/ACN/AGK

 OSPF Areas
• OSPF includes the ability to perform
hierarchical routing.
– Instead of dealing with just a single
autonomous network, OSPF can deal with
subsets called areas.
– Routers (using OSPF) within an area
exchange link status messages periodically.
– One router in each area also communicates
summary information with one or more
routers in other areas.
– Each broadcast is limited to a specific area.

Department of Information Technology, TIST IT7/ACN/AGK

 • Because of hierarchical routing
abilities,
– OSPF can scale to handle a larger
number of routers than other
IGPs.

Department of Information Technology, TIST IT7/ACN/AGK

 Multicast Routing
• A multicast allows a single address
to be used for a dynamically
changing group of recipients not
necessarily on the same network.
• Unicast routing design goals
include stability: routes don’t
change frequently.

Department of Information Technology, TIST IT7/ACN/AGK

 Multicast Routing
• Multicast routing differs significantly:
– Hosts can choose to join a multicast group at
any time and begin receiving a copy of all
packets sent to the group.
– Hosts can choose to leave a multicast group
at any time.
– Multicast group membership is private; no
receiver or sender knows the identity or
number of group members.
– Any application can send a message to any
multicast group at any time.

Department of Information Technology, TIST IT7/ACN/AGK

 The IGMP Protocol
• Used by a host to inform a nearby
router that it wishes to change
membership status in a multicast
group.

Department of Information Technology, TIST IT7/ACN/AGK

 The IGMP Protocol
• Internet Group Management Protocol
• Only hosts are members of groups,
not individual applications;
– multiple applications on the same host
that wish to receive multicast
messages will receive copies from the
host network software.
• IGMP is used only on the network
between the host and the router.

Department of Information Technology, TIST IT7/ACN/AGK

 Forwarding and Discovery
Techniques
• When a host joins a multicast
group, the router it informs
must
– establish a path to the group
– forward datagrams for the group
to the host

Department of Information Technology, TIST IT7/ACN/AGK

 Forwarding and Discovery
Techniques
• Dynamic groups and anonymous
senders make general-purpose
multicasting extremely difficult.
• The size of groups can vary
significantly, from small (3-5
hosts) to worldwide groups.
• Multicast routing protocols must
be able to change routing quickly
and continually.

Department of Information Technology, TIST IT7/ACN/AGK

 Multicast Data Forwarding
Techniques
• Flood-and-prune – good for small
groups with hosts connected to
contiguous LANs.
– Multicast messages sent to all
networks, where routers use
hardware broadcast on LANs.
– When a router reports back that
it has no group members,
flooding to that network stops
(it’s pruned).

Department of Information Technology, TIST IT7/ACN/AGK

 Multicast Data Forwarding
Techniques
• Configuration-and-tunneling –
good for geographically dispersed
groups.
– One router at each site knows about
other sites.
– Messages broadcast on directly
attached LANs.
– Other sites receive copies using IP-in-
IP tunneling.

Department of Information Technology, TIST IT7/ACN/AGK

 Multicast Data Forwarding
Techniques
• Core-based discovery – good
for graceful scaling of group
sizes
– A core unicast address is
associated with the group.
– The routers participating in the
group form a tree rooted at the
core address, and communicate
using IP-in-IP tunneling.

Department of Information Technology, TIST IT7/ACN/AGK

 Multicast Protocols
• Distance Vector Multicast Routing
Protocol –
– performs local multicast and uses
IP-in-IP to send to other sites.
• Core Based Trees –
– builds a tree from a central point,
with membership messages sent
toward the core.
• Protocol Independent Multicast –
Sparse Mode –
– like CBT, but doesn’t depend on any
particular
Department of unicast routing protocol.
Information Technology, TIST IT7/ACN/AGK
 Multicast Protocols
• Protocol Independent Multicast –
Dense Mode –
– uses flood and prune; good for use
within an organization.
• Multicast extensions to OSPF –
– for use within an organization; uses
many of the OSPF concepts and
facilities.

Department of Information Technology, TIST IT7/ACN/AGK

 Summary
• Hosts and routers use IP routing tables, mostly
static in hosts and dynamic in routers.
• Internet is divided into autonomous systems.
– EGPs are used to pass routing information between
systems; BGP is the primary EGP in the Internet.
– IGPs are used to exchange routing information within
a system; RIP and OSPF are popular IGPs.
• Multicast route propagation is difficult because
membership is dynamic and arbitrary hosts can
send messages to the group. No Internet-wide
multicast technology exists.

Department of Information Technology, TIST IT7/ACN/AGK