Transcript Chapter 15

Routing: Exterior Gateway
Protocols and Autonomous
Systems
Chapter 15
Adding Complexity to an internet
• We learned last time that we cannot continue to
add routers to an already full backbone and
continue to process efficiently. Why?
– It takes a lot of bandwidth for many routers to
communicate routing information
– In a large internet, networks and routers may be owned
or managed by different groups
• “…it is impractical for all routers in an arbitrarily
large internet to particpate in a single routing
update protocol.”
Issues on size of an internet
• Delay
– How long does it take to notify all routers of changes in
the internet?
• Overhead
– How much of the total traffic on an internet is made up
of routing data?
• What about combinations of:
– low delay and high capacity?
– high delay and low capacity?
Issues on size of an internet
• As the number of hosts on a network grows over
time, more of the network traffic is consumed by
the increased traffic
• Network managers usually implement a network
monitoring scheme
– a monitor listens passively to a network and records
statistics about the traffic, determining:
• network utilization - bandwidth used
• percentage of packets containing routing messages
The Extra Hop Problem
• Usually, we have several routers connecting to a
backbone and those routers agree on a single
routing protocol
– Another router may also be connected to that backbone,
but is considered a non-participating router, as in Figure
15.1
• If the non-participating router chooses one of the
particpating routers as its default router, routes
chosen may be suboptimal
• Router 3 wants to send to Router 2, but has Router 1
as its default; an extra hop is taken
Hidden Networks
• Local networks may be hidden from participating
routers, as local network 4 in Figure 15.2
• Information must flow in two directions
– Routing information flows from participating routers to
nonparticipating routers
– Nonparticipating routers pass information about hidden
networks to the participating group of routers
• Which router should do this? R3 which is one hop from R1, or
R4 which knows local network 4?
Autonomous Systems
• A group of networks and routers controlled
by a single administrative authority is called
an autonomous system (AS)
– One router apprises outside world of the
networks inside this group
• R3 might be chosen to serve that purpose
– The system is free to choose internal routing
architectures and protocols
• discovering, propagating, validating and checking
consistency of routes
From Core to Autonomous
Systems
• The natural evolution from the core system is
shown in Figure 15.3
• Advertisement of local information is made
available to other AS’s through a designated router
• Each AS is given an AS number (ASN) to
distinguish among the AS’s
An Exterior Gateway Protocol
• EGP is a general term for protocols used in
passing routing information between AS’s
• TCP/IP uses the Border Gateway Protocol version
4 (BGP)
• When AS’s agree to exchange routing information,
each designates a router to speak BGP on its
behalf
– the two routers are BGP peers of each other
– routers chosen are “near the edge”, thus Border, as in
Figure 15.4
BGP Characteristics
• Allows AS’s to communicate with each other
• Coordinates among multiple BGP speakers if there
is more than one
• Advertises reachable destinations
• Supplies next hop information (as distance vector)
• Allows a router’s configuration to adapt to various
policies
• Uses TCP for reliable transport
BGP Characteristics
• Advertises path information so receiver can learn
a series of AS’s along path to destination
• Exchanges full information once, then updates
with incremental changes
• Supports CIDR addressing and sending masks
• Aggregates route information
• Allows a receiver to verify the identity of a sender
(authentication)
BGP Functionality and
Message Types
• BGP performs 3 functions
– Initial peer acquisition and authentication
• Two peers establish a TCP connection
– Each side sends positive or negative reachability
information
• sender can advertise reachable destinations and next hop
• or sender can declare that previously available sites are no
longer accessible
– Continual verification that peers and network
connections are functioning correctly
BGP Functionality and
Message Types
• BGP defines 4 message types
–
–
–
–
Open - initialize communication
Update - advertise or withdraw routes
Notification - response to an incorrect message
Keepalive - continually check peer connectivity
BGP Message Header
• Marker field 16-octets - a value that both sides
agree to use to mark the beginning of a message
– initial message consists of all ones
– since TCP does not preserve message boundaries, this is
necessary
• Length field 16-bits - total message length in
octets, minimum is 19
• Type field 8 bits - indicates message type
OPEN Message
• Two BGP peers establish a TCP connection
• They send each other an OPEN with
– their ASN
– a value for a hold timer for the maximum time to wait
– a BGP identifier IP address (a router must choose one
of its IP addresses to use with all BGP peers
• See Figure 15.7
UPDATE Message
• Indicates:
– Destinations to be withdrawn (variable, not required if
there are none)
– Advertisement of new destinations (also variable)
– Lengths for both of the above - size zero if none
• See Figure 15.8
• Routers need to advertise a next hop that is
optimal from the outsider’s perspective, See
Figure 15.12
Compressed Mask-Address Pairs
• To accommodate classless addressing, for each of
the addresses in the UPDATE message, an IP
address and a mask are compressed
– See Figure 15.9
– Mask information is encoded into 8 bits, which
represents the number of bits in the mask (0-32)
– The address is also compressed
• If the value of the mask is < 8, one octet is covered and that is
what follows
• If the value is between 9 and 16, two octets follow, etc.
Path Attributes
• BGP is not a pure distance vector protocol because
it advertises more than a next hop
– Additional information is in the Path Attributes field of
the UPDATE message
– Allows the receiver to:
• check for routing loops and sender tospecify an exact path
through AS’s to destination
• implement policy constraints and accept/reject routes unsafe
• know the source of all routes
• Path attributes are factored, so that the attributes
apply to all destinations advertised in one message
Path Attributes
• The Path Attributes field consists of a triple:
(type, length, value)
• The two octets shown in Figure 15.10 precede
each item in the Path Attributes list of Figure 15.8
KEEPALIVE Message
• Verifies that two peers are continually functioning
• Consists of the header and no data (19 octets)
• Why?
– BGP uses TCP for transport and TCP does not have a
mechanism to continue to check for endpoint
reachability
– Saves bandwith as opposed to continually sending
routing information (which generally changes
infrequently)
• Standards recommend keepalive timer = 1/3 hold timer
A Restriction of Exterior
Gateway Protocols
• Exterior Gateway Protocols do not communicate
or interpret distance metrics
• BGP can only specify whether a destination is
reachable, it cannot determine a best path
• BGP does not know the cost of routes across
intermediate AS’s
• We say that BGP is a reachability protocol rather
than a routing protocol
• See consequences on pages 286 and 287
Internet Routing Arbiter System
• For an internet to work, routing information must
be globally consistent
• The Routing Arbiter (RA) system consists of a
replicated, authenticated database of reachability
information
– updates are authenticated
– generally, only the AS that owns a network is allowed
to adverise reachability
Internet Routing Arbiter System
• Major ISPs interconnect at Network Access Points
(NAPs)
– Thus, an NAP represents the boundary between
multiple AS’s
– Each NAP has a computer called a route server (RS)
that maintains a copy of the database and runs BGP
– Each ISP designates one router near a NAP to be a BGP
border router
• This router maintains a connection to the route server
• The ISP advertises reachability to its networks and networks of
its customers
NOTIFICATION Message
• This message type is used when errors occur
• Once an error is detected, the TCP connection is
closed
• Error codes are indicated in Figure 15.14
– Subcodes for each of the error codes are shown in
Figure 15.15
Unanswered Questions
• How can we move from a centralized router
system?
• Can we have trust between Autonomous Systems?
Summary
• Routers must be partitioned into groups or the
amount of routing information exchanged is too
large
• The Internet consists of many Autonomous
Systems
– consisting of routers and networks under one
administrative authority
– the AS’s use an EGP to advertise reachability of its
networks from outside
• TCP’s EGP is BGP
Summary
• Border Gateway Protocol is the most widely used
EGP
• BGP message types
–
–
–
–
initiate communication (OPEN)
send reachability information (UPDATE)
report errors (NOTIFICATION)
ensure that peers are connected (KEEPALIVE)
• Multiple ISP’s connect at NAP’s and each NAP
includes a route server, which uses BGP
For Next Time
• Read Chapter 16