Transcript CSC 335 Data Communications and Networking I

CSC 600
Internetworking
with
TCP/IP
Unit 6a: IP Routing and Exterior
Routing Protocols
(Ch. 14, 15)
Dr. Cheer-Sun Yang
Spring 2001
Routing Protocols
• Cores, Peers, and Algorithms :Distance
Vector(Bellman-Ford), Link State(Dijkstra),
Gateway-to-Gateway Protocol(GGP),
• Interior: within an autonomous system
• Exterior: between two autonomous systems
• Exterior Routing Protocols :Border Gateway
Protocol(BGP)
• Interior Routing Protocols :RIP(distance vector),
OSPF(link state).
Routing Protocols
• Routing Information
– About topology and delays in the internet
• Routing Algorithm
– Used to make routing decisions based on
information
The Evolution of Internet
Architecture
• Core system : many non-core routers are
conneced to a set of core routers.
• Peer-to-peer : many routers are connected to
a backbone.
• Architectural: many autonomous systems
are connected to their own gateways and
gateways are connected as “peers”.
Original Internet Architecture and
Cores
• A small number of routers kept complete
information about all possible destinations and a
large set of routers only kept partial information.
• The routing table in a given router contains partial
information about possible destinations.
• Routing that uses partial information allows sites
autonomy in making local routing changes.
Core vs. Noncore
• Core routers are controlled by the Internet
Network Operations Center (INOC).
• Noncore routers are controlled by individual
groups.
• This architecture can introduce the possibility of
inconsistencies that may make some destinations
unreachable from some sources unless the chain of
all default routers (core) reaches every router in a
giant cycle as shown in next slide.
Core System is Impractical
When the NSFNET became the major part of the
Internet, the core architecture became impractical
for the following reasons:
• The Internet outgrew a single, centrally managed
long-haul backbone.
• Not every site could have a core router connected
to the backbone.
• Because core routers all interacted to ensure
consistent routing information, the core
architecture did not scale to arbitrary size.
The peer-to-peer architecture is formed.
Routing Becomes Complicated
• For example, how can a datagram be routed
from host 3 to host 2?
• Which path should be taken?
• How can routing be optimized?
• How can loops be eliminated?
Summary of Core System
Architecture
• A core routing architecture assumes a centralized
set of routers which serves as the repository of
information about all possible destinations in an
internet.
• Core systems work best for internets that have a
single, centrally managed backbone.
• Expanding the topology to multiple backbones
makes routing complex; attempting to partition the
core architecture so that all routers use default
routers introduces potential routing loops.
Automatic Propagation of
Routing Information
The Internet is not static!
Distance Vector
(Bellman-Ford)
Routing
Gateway-to-Gateway Protocol (GGP)
 Sometimes known as exterior routing
protocols.
 It is a true distance-vector protocol.
 It measures distance in router hops.
Autonomous Systems
 Although it is desirable for routers to
exchange routing information, it is
impractical for all routers on an
arbitrarily large internet to participate in
a single routing update protocol.
 The number of routers that participate
in a single routing protocol must be
limited.
Autonomous Systems
 This idea works fine. However, it
implies that some routers will be outside
the group.
 If a router outside of an AS uses a
member of the group as the default route,
routing will be suboptimal.
 R1 and R2 are in one AS, while R3 is
not.
 If R3 sends datagrams via R1 for
sending datagrams to R2, it is not
optimal.
Hidden Networks
Architectural Approach:
Autonomous Systems (AS)
•
•
•
•
Group of routers
Exchange information
Common routing protocol
Set of routers and networks managed by
single organization - an autonomous system
• The Internet is organized into a collection of
Ass, each of which is normally administered
by a single entity. A corporation or
university campus often defines an AS. The
NSF backbone forms an AS.
Architectural Approach:
Autonomous Systems (AS)
• Each Autonomous system can select its own
routing protocol to communicate between
the routers in that AS. This is called an
interior gateway protocol (IGP) or
intradomain routing protocol.
• Separate routing protocols called exterior
gateway protocol (EGS) or interdomain
routing protocol are used between the
routers in different autonomous systems.
Interior Routing Protocols
• Routing Information Protocol (RIP): a
distance vector (Bellman-Ford)
• Open Shortest Path First Protocol (OSPF): a
link state algorithm (Dijkstra’s algorithm)
Exterior Routing Protocol
• Border Gateway Protocol (BGP)
Application of IRP and ERP
Border Gateway Protocol (BGP)
•
•
•
•
•
•
•
•
•
•
Inter-autonomous system communication
Coordination among multiple BGP gateways
Propagation of reachability information
Next-hop paradigm
Policy support
Reliable transport
Incremental updates
Support for classless addressing
Route aggregation
Authentication
Border Gateway Protocol (BGP)
• For use with TCP/IP internets
• Preferred EGP of the Internet
• Messages types sent over TCP connections
–
–
–
–
Open
Update: advertise or withdraw routes
Keep alive: actively test peer connectivity
Notification: response to an incorrect message
• Procedures
– Neighbor acquisition
– Neighbor reachability
– Network reachability
BGP
Messages
BGP Procedure
• Open TCP connection
• Send Open message
– Includes proposed hold time
• Receiver selects minimum of its hold time
and that sent
– Max time between Keep alive and/or update
messages
Other Message Types
• Keep Alive
– To tell other routers that this router is still here
• Update
– Info about single routes through internet
– List of routes being withdrawn
– Includes path info
•
•
•
•
•
•
Origin (IGP or EGP)
AS_Path (list of AS traversed)
Next_hop (IP address of boarder router)
Multi_Exit_Disc (Info about routers internal to AS)
Local_pref (Inform other routers within AS)
Atomic_Aggregate, Aggregator (Uses address tree structure to
reduce amount of info needed)
Uses of AS_Path and Next_Hop
• AS_Path
– Enables routing policy
•
•
•
•
•
Avoid a particular AS
Security
Performance
Quality
Number of AS crossed
• Next_Hop
– Only a few routers implement BGP
• Responsible for informing outside routers of routes to other
networks in AS
The Key Restriction of EGP
• An exterior gateway protocol does not
communicate or interpret distance metrices,
even if metrics are available.
The Routing Arbiter System
• For an internet to operate correctly, routing
information must be globally consistent.
• Individual protocols such as BGP does not
guarantee global consistency.
• The RA system consists of a replicated
authenticated database of reachability
information.Each ISP designates one of the routers
near a Network Access Point (NAP) to be a BGP
border router.
• The designated router maintains a connection to
the route server over which it uses BGP. BGP
notification messages are exchanged.
BGP Routing Information
Exchange
• Within AS, router builds topology picture
using IGP
• Router issues Update message to other
routers outside AS using BGP
• These routers exchange info with other
routers in other AS
• Routers must then decide best routes
Notification Message
• Message header error
– Authentication and syntax
• Open message error
– Syntax and option not recognized
– Unacceptable hold time
• Update message error
– Syntax and validity errors
• Hold time expired
– Connection is closed
• Finite state machine error
• Cease
– Used to close a connection when there is no error