path: root/doc/rfc/rfc911.txt

Network Working Group
Request for Comments: 911






                      EGP GATEWAY UNDER BERKELEY UNIX 4.2



                                  PAUL KIRTON


       University of Southern California, Information Sciences Institute
     Visiting Research Fellow from Telecom Australia Research Laboratories

                                22 August 1984











                                   ABSTRACT

This  report  describes an implementation of the Exterior Gateway Protocol that
runs under the Unix 4.2 BSD operating system.  Some  issues  related  to  local
network configurations are also discussed.



Status of this Memo:

This  memo describes  an implementation of the Exterior Gateway Protocol  (EGP)
(in that sense it is a status report).  The memo also discusses  some  possible
extentions  and  some  design  issues   (in that sense it is an invitation  for
further discussion).  Distribution of this memo is unlimited.



    Funding for this research was provided by DARPA and Telecom Australia.
^L
RFC 911                                                                       i


                               Table of Contents

1. INTRODUCTION                                                               1

1.1 Motivation for Development                                                1
1.2 Overview of EGP                                                           2

2. GATEWAY DESIGN                                                             4

2.1 Routing Tables                                                            4
     2.1.1 Incoming Updates                                                   5
     2.1.2 Outgoing Updates                                                   5
2.2 Neighbor Acquisition                                                      6
2.3 Hello and Poll Intervals                                                  6
2.4 Neighbor Cease                                                            7
2.5 Neighbor Reachability                                                     7
2.6 Sequence Numbers                                                          8
2.7 Treatment of Excess Commands                                              8
2.8 Inappropriate Messages                                                    8
2.9 Default Gateway                                                           9

3. TESTING                                                                   10

4. FUTURE ENHANCEMENTS                                                       11

4.1 Multiple Autonomous Systems                                              11
4.2 Interface Monitoring                                                     11
4.3 Network Level Status Information                                         11
4.4 Interior Gateway Protocol Interface                                      12

5. TOPOLOGY ISSUES                                                           13

5.1 Topology Restrictions and Routing Loops                                  13
     5.1.1 Background                                                        13
     5.1.2 Current Policy                                                    14
5.2 Present ISI Configuration                                                15
     5.2.1 EGP Across ARPANET                                                17
     5.2.2 EGP Across ISI-NET                                                17
     5.2.3 Potential Routing Loop                                            18
5.3 Possible Future Configuration                                            18
     5.3.1 Gateway to UCI-ICS                                                18
     5.3.2 Dynamic Switch to Backup Gateway                                  19
          5.3.2.1 Usual Operation                                            19
          5.3.2.2 Host Initialization                                        19
          5.3.2.3 When Both the Primary and Backup are Down                  20
          5.3.2.4 Unix 4.2 BSD                                               20

6. ACKNOWLEDGEMENT                                                           21

7. REFERENCES                                                                22
^L
RFC 911                                                                       1


1. INTRODUCTION

The Exterior Gateway Protocol (EGP) [Rosen 82; Seamonson & Rosen 84; Mills 84a]
has been specified to allow autonomous development of different gateway systems
while  still  maintaining  global distribution of internet routing information.
EGP provides a means for  different  autonomous  gateway  systems  to  exchange
information about the networks that are reachable via them.

This  report  mainly  describes  an  implementation  of EGP that runs as a user
                               *                                  **
process under the Berkeley Unix  4.2 operating system run on a VAX    computer.
Some  related issues concerning local autonomous system configurations are also
discussed.

The EGP implementation is experimental and is not a part of Unix 4.2 BSD. It is
anticipated that Berkeley will incorporate a version of EGP in the future.

The program is written in C. The EGP  part  is  based  on  the  C-Gateway  code
written  by  Liza  Martin at MIT and the route management part is based on Unix
4.2 BSD route management daemon, "routed".

The EGP functions are consistent with the specification of [Mills  84a]  except
where noted.

A  knowledge  of  EGP  as  described  in  [Seamonson  & Rosen 84; Mills 84a] is
assumed.

This chapter discusses the motivation for the project, Chapter 2 describes  the
gateway  design,  Chapter 3 is on testing, Chapter 4 suggests some enhancements
and Chapter 5 discusses topology issues.

Further information about running the EGP program and describing  the  software
is being published in an ISI Research Report ISI/RR-84-145 [Kirton 84].

Requests  for  documentation  and  copies  of the EGP program should be sent to
Joyce Reynolds (JKReynolds@USC-ISIF.ARPA). Software support is not provided.


1.1 Motivation for Development

With the introduction of EGP, the internet gateways  will  be  divided  into  a
"core"  autonomous  system  (AS)  of  gateways  maintained by Bolt, Beranek and
Newman  (BBN)  and  many  "stub"  AS's  that  are   maintained   by   different
organizations  and  have at least one network in common with a core AS gateway.
The core AS will act as a  hub  for  passing  on  routing  information  between

_______________

  *
   Unix is a trade mark of AT&T
  **
    VAX is a trade mark of Digital Equipment Corporation
^L
RFC 911                                                                       2


different  stub AS's so that it will only be necessary for stub AS's to conduct
EGP with a core gateway. Further detail is given in [Rosen 82].

At the time of this  project  there  were  28  "non-routing"  gateways  in  the
internet.  Non-routing  gateways  did  not  exchange  routing  information  but
required static entries in the core gateway routing tables.   Since  August  1,
1984  these  static  entries  have  been  eliminated and previously non-routing
gateways are required to communicate this  information  to  the  core  gateways
dynamically via EGP [Postel 84].

At the USC Information Sciences Institute (ISI) there was a non-routing gateway
to  the  University  of  California  at  Irvine  network  (UCI-ICS).  With  the
elimination of  non-routing  gateways  from  the  core  gateway  tables  it  is
necessary to inform the core ISI gateway of the route to UCI-ICS using EGP.

Also,  we  would  like a backup gateway between ISI-NET and the ARPANET in case
the core ISI gateway is down. Such, a gateway  would  need  to  convey  routing
information  via EGP. Details of the ISI network configuration are discussed in
Section 5.2.

Of the 28 non-routing gateways 23 were implemented by Unix  systems,  including
ISI's.  Also, ISI's proposed backup gateway was a Unix system. Thus there was a
local and general need for an EGP implementation to run under Unix. The current
version  of  Unix  that  included  Department  of  Defense  (DoD) protocols was
Berkeley Unix 4.2 so this was selected.


1.2 Overview of EGP

This report assumes a knowledge of EGP, however a brief overview is given  here
for completeness. For further details refer to [Rosen 82] for the background to
EGP,  [Seamonson & Rosen 84] for an informal description, and [Mills 84a] for a
more formal specification and implementation details.

EGP is generally conducted between gateways in  different  AS's  that  share  a
common network, that is, neighbor gateways.

EGP  consists  of three procedures, neighbor acquisition, neighbor reachability
and network reachability.

Neighbor acquisition is a two way handshake in which gateways agree to  conduct
EGP  by exchanging Request and Confirm messages which include the minimum Hello
and Poll  intervals.    Acquisition  is  terminated  by  exchanging  Cease  and
Cease-ack messages.

Neighbor  reachability  is  a  periodic exchange of Hello commands and I-H-U (I
heard you) responses to ensure that each gateway is up. Currently a  30  second
minimum interval is used across ARPANET. Only one gateway need send commands as
the   other   can  use  them  to  determine  reachability.  A  gateway  sending
reachability commands is said to be in the active mode, while  a  gateway  that
just responds is in the passive mode.
^L
RFC 911                                                                       3


Network  reachability  is  determined by periodically sending Poll commands and
receiving Update responses which indicate the networks  reachable  via  one  or
more  gateways  on  the  shared network. Currently 2 minute minimum interval is
used across ARPANET.
^L
RFC 911                                                                       4


2. GATEWAY DESIGN

EGP  is a polling protocol with loose timing constraints. Thus the only gateway
function requiring good performance is packet forwarding.  Unix 4.2 already has
packet forwarding built into the kernel where best performance can be achieved.
At the time of writing Unix 4.2 did not send  ICMP  (Internet  Control  Message
Protocol)  redirect  messages  for  misrouted packets. This is a requirement of
internet gateways and will later be added by Berkeley.

The EGP and route update functions are implemented as a  user  process.    This
facilitates  development and distribution as only minor changes need to be made
to the Unix kernel.  This is a similar approach to the Unix route  distribution
program  "routed"  [Berkeley  83]  which  is  based  on  the  Xerox  NS Routing
Information Protocol [Xerox 81].


2.1 Routing Tables

A route consists of a destination network  number,  the  address  of  the  next
gateway  to  use  on  a  directly  connected  network,  and a metric giving the
distance in gateway hops to the destination network.

There are two sets of routing  tables,  the  kernel  tables  (used  for  packet
forwarding) and the EGP process tables. The kernel has separate tables for host
and  network  destinations.  The EGP process only maintains the network routing
tables. The EGP tables are updated when EGP Update messages are received.  When
a  route is changed the kernel network tables are updated via the SIOCADDRT and
SIOCDELRT ioctl system calls. At  initialization  the  kernel  network  routing
tables  are  read  via the kernel memory image file, /dev/kmem, and copied into
the EGP tables for consistency.

This EGP implementation is designed to run on a gateway that is  also  a  host.
Because  of  the relatively slow polling to obtain route updates it is possible
that the host may receive notification of routing changes  via  ICMP  redirects
before  the EGP process is notified via EGP. Redirects update the kernel tables
directly. The EGP process listens for redirect messages on  a  raw  socket  and
updates its routing tables to keep them consistent with the kernel.

The  EGP  process routing tables are maintained as two separate tables, one for
exterior routes (via different AS gateways) and one for  interior  routes  (via
the  gateways of this AS).  The exterior routing table is updated by EGP Update
messages. The interior  routing  table  is  currently  static  and  is  set  at
initialization  time. It includes all directly attached nets, determined by the
SIOCGIFCONF ioctl system call and any interior non-routing gateways  read  from
the  EGP  initialization file, EGPINITFILE. The interior routing table could in
future be updated dynamically by an Interior Gateway Protocol (IGP).

Maintaining separate tables for exterior and interior routing  facilitates  the
preparation  of  outgoing  Update  messages which only contain interior routing
information [Mills 84b].  It also permits alternative external  routes  to  the
internal  routes  to  be  saved  as  a  backup in case an interior route fails.
Alternate routes are flagged,  RTS_NOTINSTALL,  to  indicate  that  the  kernel
^L
RFC 911                                                                       5


routes  should  not  be updated. In the current implementation alternate routes
are not used.



2.1.1 Incoming Updates

EGP Updates are used to update  the  exterior  routing  table  if  one  of  the
following is satisfied:

   - No  routing  table  entry  exists for the destination network and the
     metric indicates the route is reachable (< 255).

   - The advised gateway is the same as the current route.

   - The advised distance metric is less than the current metric.

   - The current route is older (plus a  margin)  than  the  maximum  poll
     interval  for  all  acquired  EGP  neighbors.  That is, the route was
     omitted from the last Update.

If any exterior route entry, except the default route, is not  updated  by  EGP
within  4  minutes  or  3  times  the  maximum  poll interval, whichever is the
greater, it is deleted.

If there is more than one acquired EGP neighbor, the Update  messages  received
from each are treated the same way in the order they are received.

In  the worst case, when a route is changed to a longer route and the old route
is not first notified as unreachable, it  could  take  two  poll  intervals  to
update  a  route. With the current poll interval this could be 4 minutes. Under
Unix 4.2  BSD  TCP  connections  (Transmission  Control  Protocol)  are  closed
automatically  after  they  are idle for 6 minutes. So this worst case will not
result in the automatic closure of TCP connections.



2.1.2 Outgoing Updates

Outgoing Updates include the direct  and  static  networks  from  the  interior
routing table, except for the network shared with the EGP neighbor.

The  networks  that  are  allowed  to be advised in Updates may be specified at
initialization in EGPINITFILE. This allows particular  routes  to  be  excluded
from  exterior updates in cases where routing loops could be a problem. Another
case where this option is necessary, is when there  is  a  non-routing  gateway
belonging  to  a different AS which has not implemented EGP yet. Its routes may
need to be included in the kernel routing table but they are not allowed to  be
advised in outgoing updates.

If  the  interior routing table includes other interior gateways on the network
shared with the EGP neighbor they are include in  Updates  as  the  appropriate
^L
RFC 911                                                                       6


first hop to their attached networks.

The  distance to networks is set as in the interior routing table except if the
route is marked down in which case the distance  is  set  to  255.  At  present
routes are only marked down if the outgoing interface is down. The state of all
interfaces  is  checked  prior  to  preparing  each  outgoing  Update using the
SIOCGIFFLAGS ioctl system call.

Unsolicited Updates are not sent.


2.2 Neighbor Acquisition

EGPINITFILE lists the addresses of trusted EGP  neighbor  gateways,  which  are
read  at  initialization.  These  will  usually  be  core gateways as only core
gateways provide full internet routing information.  At  the  time  of  writing
there  were  three  core  gateways  on  ARPANET which support EGP, CSS-GATEWAY,
ISI-GATEWAY and PURDUE-CS-GW, and two on MILNET, BBN-MINET-A-GW and AERONET-GW.

EGPINITFILE also includes the maximum number of these gateways that  should  be
acquired  at  any  one  time.  This is usually expected to be just one. If this
gateway is declared down another gateway on the  list  will  then  be  acquired
automatically  in  sufficient  time  to  ensure that the current routes are not
timed out.

The gateway will only accept acquisitions from neighbors on  the  trusted  list
and  will  not  accept  them if it already has acquired its maximum quota. This
prevents Updates being accepted from possibly unreliable sources.

The ability to acquire core gateways that are not on the trusted list but  have
been  learned of indirectly via Update messages is not included because not all
core gateways run EGP.

New acquisition Requests are sent to neighbors in  the  order  they  appear  in
EGPINITFILE.  No  more new Requests than the maximum number of neighbors yet to
be  acquired  are  sent  at  once.  Any  number  of  outstanding  Requests  are
retransmitted at 32 second intervals up to 5 retransmissions each at which time
the  acquisition  retransmission  interval  is increased to 4 minutes. Once the
maximum number of  neighbors  has  been  acquired,  unacquired  neighbors  with
outstanding  Requests  are  sent  Ceases.  This  approach provides a compromise
between fast response when neighbors do not initially respond and a  desire  to
minimize  the  chance that a neighbor may be Ceased after it has sent a Confirm
but before it has been received.  If the specified maximum number of  neighbors
cannot  be  acquired, Requests are retransmitted indefinitely to all unacquired
neighbors.


2.3 Hello and Poll Intervals

The Request and Confirm messages include minimum  values  for  Hello  and  Poll
intervals.  The advised minimums by this and the core gateways are currently 30
and 120 seconds respectively.
^L
RFC 911                                                                       7


The  received  intervals  are  checked  against  upper  bounds to guard against
nonsense values. The upper bounds are currently set  at  120  and  480  seconds
respectively.  If,  they are exceeded the particular neighbor is considered bad
and not sent further Requests for one hour. This allows  the  situation  to  be
corrected  at  the  other  gateway and normal operation to automatically resume
from this gateway without an excess of unnecessary network traffic.

The actual Hello and Poll intervals are chosen by first selecting  the  maximum
of  the  intervals  advised  by this gateway and its peer. A 2 second margin is
then added to the Hello interval to take  account  of  possible  network  delay
variations  and the Poll interval is increased to the next integer ratio of the
Hello interval. This results in 32 second Hello and 128 second Poll intervals.

If an Update is not received in response to a Poll, at most  one  repoll  (same
sequence number) is sent instead of the next scheduled Hello.


2.4 Neighbor Cease

If  the EGP process is sent a SIGTERM signal via the Kill command, all acquired
neighbors are sent Cease(going down) commands.  Ceases are retransmitted at the
hello interval at most 3 times.  Once all have either responded with Cease-acks
or been sent three retransmitted Ceases the process is terminated.


2.5 Neighbor Reachability

Only  active  reachability  determination  is  implemented.  It  is   done   as
recommended in [Mills 84a] with a minor variation noted below.

A  shift  register  of responses is maintained.  For each Poll or Hello command
sent a zero is shifted into the shift register.  If a response  (I-H-U,  Update
or  Error) is received with the correct sequence number the zero is replaced by
a one.  Before each new command is  sent  the  reachability  is  determined  by
examining  the  last  four  entries  of  the shift register. If the neighbor is
reachable  and  <=  1  response  was  received  the  neighbor   is   considered
unreachable.  If the neighbor is considered unreachable and >= 3 responses were
received it is now considered reachable.

A neighbor is considered reachable immediately after acquisition  so  that  the
first  poll  received  from  a  core  gateway  (once  it considers this gateway
reachable) will be responded to with an Update. Polls are  not  sent  unless  a
neighbor  is considered reachable and it has not advised that it considers this
gateway unreachable in its last Hello, I-H-U or Poll message.    This  prevents
the first Poll being discarded after a down/up transition. This is important as
the  Polls  are  used  for reachability determination. Following acquisition at
least one message must be received before the first Poll is sent.  This  is  to
determine  that  the  peer  does  not  consider this gateway down. This usually
requires at least one Hello to be sent prior to the first poll. The  discussion
of  this  paragraph  differs  from  [Mills 84a] which recommends that a peer be
considered down following acquisition and Polls may be sent as soon as the peer
is  considered  up.  This  is  the  only   significant   departure   from   the
^L
RFC 911                                                                       8


recommendations in [Mills 84a].

Polls  received  by  peers  that  are  considered unreachable are sent an Error
response which allows their reachability determination to  progress  correctly.
This action is an option within [Mills 84a].

When  a  neighbor  becomes  unreachable  all  routes  using it as a gateway are
deleted from the routing table. If there are  known  unacquired  neighbors  the
unreachable gateway is ceased and an attempt is made to acquire a new neighbor.
If all known neighbors are acquired the reachability determination is continued
for  30  minutes  ([Mills  84a]  suggests  60  minutes)  after  which  time the
unreachable neighbor is ceased and reacquisition  attempted  every  4  minutes.
This is aimed at reducing unnecessary network traffic.

If  valid  Update  responses  are  not  received for three successive polls the
neighbor is ceased and an alternative acquired or reacquisition is attempted in
4 minutes. This provision is provided in case erroneous Update data formats are
being sent by the neighbor. This situation did occur  on  one  occasion  during
testing.


2.6 Sequence Numbers

Sequence  numbers  are  managed  as recommended in [Mills 84a]. Single send and
receive sequence numbers are maintained for each neighbor.  The  send  sequence
number  is  initialized  to  zero  and is incremented before each new Poll (not
repoll) is sent and at no other time. The send sequence number is used  in  all
commands.  The  receive  sequence  number is maintained by copying the sequence
number of the last Request, Hello, or Poll command received  from  a  neighbor.
This  sequence  number  is  used  in outgoing Updates. All responses (including
Error responses) return the sequence number of the message just received.


2.7 Treatment of Excess Commands

If more than 20 commands are received from a neighbor in any  8  minute  period
the  neighbor  is  considered  bad,  Ceased and reacquisition prevented for one
hour.

At most one repoll (same sequence number) received before the poll interval has
expired (less a 4 second margin for network delay variability) is responded  to
with  an  Update,  others are sent an Error response. When an Update is sent in
response to a repoll the unsolicited bit is not set,  which  differs  from  the
recommendation in [Mills 84a].


2.8 Inappropriate Messages

If  a Confirm, Hello, I-H-U, Poll or Update is received from any gateway (known
or unknown) that is in the unacquired state, synchronization has probably  been
lost  for  some  reason. A Cease(protocol violation) message is sent to try and
reduce unnecessary network traffic. This action is an option in [Mills 84a].
^L
RFC 911                                                                       9




2.9 Default Gateway

A  default gateway may be specified in EGPINITFILE. The default route (net 0 in
Unix 4.2 BSD) is used by the kernel packet forwarder if there  is  no  specific
route for the destination network. This provides a final level of backup if all
known EGP neighbors are unreachable. This is especially useful if there is only
one available EGP neighbor, as in the ISI case, Section 5.2.2.

The  default route is installed at initialization and deleted after a valid EGP
Update message is received. It  is  reinstalled  if  all  known  neighbors  are
acquired  but  none  are  reachable,  if routes time out while there are no EGP
neighbors that are acquired and reachable, and prior to process termination.

It is deleted after a valid EGP Update message is received because the  default
gateway will not know any more routing information than learned via EGP.  If it
were  not deleted, all traffic to unreachable nets would be sent to the default
gateway under Unix 4.2 forwarding strategy.

The default gateway should normally be set to a full-routing core gateway other
than the known EGP neighbor gateways to give another backup in case all of  the
EGP gateways are down simultaneously.
^L
RFC 911                                                                      10


3. TESTING

A few interesting cases that occurred during testing are briefly described.

The   use   of  sequence  numbers  was  interpreted  differently  by  different
implementers. Consequently some implementations  rejected  messages  as  having
incorrect  sequence numbers, resulting in the peer gateway being declared down.
The main problem was that the specification was solely in narrative form  which
is  prone  to  inconsistencies, ambiguities and incompleteness. The more formal
specification of [Mills 84a] has eliminated these ambiguities.

When testing  the  response  to  packets  addressed  to  a  neighbor  gateway's
interface  that  was  not  on  the  shared net a loop resulted as both gateways
repeatedly exchanged  error  messages  indicating  an  invalid  interface.  The
problem  was that both gateways were sending Error responses after checking the
addresses but before the EGP message type was checked.  This was  rectified  by
not  sending  an  Error response unless it was certain that the message was not
itself an Error response.

On one occasion a core gateway had some  form  of  data  error  in  the  Update
messages  which  caused  them to be rejected even though reachability was being
satisfactorily conducted. This resulted in all routes being  timed  out.    The
solution  was  to  count  the  number of successive Polls that do not result in
valid Updates being received and if this number reaches  3  to  Cease  EGP  and
attempt to acquire an alternative gateway.

Another  interesting idiosyncrasy, reported by Mike Karels at Berkeley, results
from having multiple gateways between MILNET and ARPANET. Each ARPANET host has
an assigned gateway to use for access to MILNET. In cases where the EGP gateway
is a host as well as  a  gateway,  the  EGP  Update  messages  may  indicate  a
different  MILNET/ARPANET  gateway from the assigned one. When the host/gateway
originates a packet that is routed  via  the  EGP  reported  gateway,  it  will
receive  a  redirect to its assigned gateway.  Thus the MILNET gateway can keep
being switched between the gateway reported by EGP and the assigned gateway.  A
similar thing occurs when using routes to other nets reached via MILNET/ARPANET
gateways.
^L
RFC 911                                                                      11


4. FUTURE ENHANCEMENTS

4.1 Multiple Autonomous Systems

The  present  method  of  acquiring  a  maximum  number of EGP neighbors from a
trusted list implies that all the neighbors are in the same AS.  The  intention
is  that  they all be members of the core AS. When updating the routing tables,
Updates are treated independently with no distinction made as  to  whether  the
advised  routes  are  internal  or  external  to  the peer's AS.  Also, routing
metrics are compared without reference to the AS of the source.

If EGP is to be  conducted  with  additional  AS's  beside  the  core  AS,  all
neighbors  on  the  list  would  need  to  be  acquired in order to ensure that
gateways from both AS's were always acquired. This results  in  an  unnecessary
excess  of  EGP  traffic if redundant neighbors are acquired for reliability. A
more desirable approach would be to have separate lists of trusted EGP gateways
and the maximum number to be acquire, for each AS. Routing entries  would  need
to  have  the  source AS added so that preference could be given to information
received from the owning AS (see Section 5.1.2)


4.2 Interface Monitoring

At present, interface status is only checked immediately prior to  the  sending
of  an  Update  in response to a Poll.  The interface status could be monitored
more regularly and an unsolicited Update sent when a change is  detected.  This
is  one  area where the slow response of EGP polling could be improved. This is
of particular interest to networks that may  be  connected  by  dial-in  lines.
When such a network dials in, its associated interface will be marked as up but
it  will not be able to receive packets until the change has been propagated by
EGP. This is one case where the unsolicited  Update  message  would  help,  but
there  is still the delay for other non-core gateways to poll core EGP gateways
for the new routing information.

This  was  one  case  where  it  was  initially  thought  that  a  kernel   EGP
implementation  might  help.  But  the kernel does not presently pass interface
status changes by interrupts so a new facility would need to  be  incorporated.
If  this was done it may be just as easy to provide a user level signal when an
interface status changes.


4.3 Network Level Status Information

At present, network level status reports, such as IMP  Destination  Unreachable
messages,  are  not used to detect changes in the reachability of EGP neighbors
or other neighbor gateways. This information should  be  used  to  improve  the
response time to changes.
^L
RFC 911                                                                      12


4.4 Interior Gateway Protocol Interface

At  present  any  routing  information that is interior to the AS is static and
read from the initialization file. The internal route management functions have
been written so that it should be reasonably  easy  to  interface  an  IGP  for
dynamic  interior  route  updates. This is facilitated by the separation of the
exterior and interior routing tables.

The outgoing EGP Updates will be correctly prepared from the  interior  routing
table by rt_NRnets() whether or not static or dynamic interior routing is done.
Functions  are  also  provided  for  looking  up, adding, changing and deleting
internal routes, i.e. rt_int_lookup(), rt_add(),  rt_change()  and  rt_delete()
respectively.

The  interaction  of an IGP with the current data structures basically involves
three functions: updating the interior routing table using a  function  similar
to rt_NRupdate(), preparing outgoing interior updates similarly to rt_NRnets(),
and timing out interior routes similarly to rt_time().
^L
RFC 911                                                                      13


5. TOPOLOGY ISSUES

5.1 Topology Restrictions and Routing Loops



5.1.1 Background

EGP  is  not  a  routing  algorithm.  it  merely  enables exterior neighbors to
exchange routing information which is likely to  to  be  needed  by  a  routing
algorithm.  It does not pass sufficient information to prevent routing loops if
cycles exist in the topology [Rosen 82].

Routing loops can occur when two gateways think there are alternate  routes  to
reach a third gateway via each other. When the third gateway goes down they end
up  pointing  to  each  other  forming a routing loop.  Within the present core
system, loops are broken by counting to "infinity" (the  internet  diameter  in
gateway  hops).  This  (usually)  works  satisfactorily  because GGP propagates
changes fairly quickly as routing updates are sent as soon  as  changes  occur.
Also  the  diameter of the internet is quite small (5) and a universal distance
metric, hop count, is used. But this will be changed in the future.

With EGP, changes are propagated  slowly.  Although  a  single  unsolicited  NR
message  can  be  sent,  it  won't  necessarily  be passed straight on to other
gateways who must hear about it  indirectly.  Also,  the  distance  metrics  of
different  AS's  are  quite  independent  and  hence  can't be used to count to
infinity.

The initial proposal was to prevent routing loops by restricting  the  topology
of  AS's to a tree structure so that there are no multiple routes via alternate
AS's.  Multiple routes within the same AS are allowed as  it  is  the  interior
routing strategies responsibility to control loops.

[Mills  84b]  has  noted that even with the tree topology restriction, "we must
assume that transient loops may form within the core system from time  to  time
and  that  this  information  may escape to other systems; however, it would be
expected that these loops would not persist for very long and would  be  broken
in  a  short  time  within the core system itself. Thus a loop between non-core
systems can persist until the first round of Update messages sent to the  other
systems  after  all traces of the loop have been purged from the core system or
until the reachability information ages out of  the  tables,  whichever  occurs
first".

With the initial simple stub EGP systems the tree topology restriction could be
satisfied. But for the long term this does not provide sufficient robustness.

[Mills  83]  proposed a procedure by which the AS's can dynamically reconfigure
themselves such that the topology restriction is always met, without  the  need
for  a  single  "core" AS.  One AS would own a shared net and its neighbor AS's
would just conduct EGP with the owner. The owner would pass on such information
indirectly as the core system does now. If the  owning  AS  is  defined  to  be
closest  to  the  root  of the tree topology, any haphazard interconnection can
^L
RFC 911                                                                      14


form  itself  into  an appropriate tree structured routing topology. By routing
topology I mean the topology as advised in routing updates. There may  well  be
other  physical  connections  but if they are not advised they will not be used
for routing. Each AS can conduct EGP with at most one AS that owns one  of  its
shared nets. Any AS that is not conducting EGP over any net owned by another AS
is  the  root of a subtree. It may conduct EGP with just one other AS that owns
one of its shared nets. This "attachment" combines  the  two  subtrees  into  a
single  subtree  such  that  the  overall  topology  is still a tree.  Topology
violations can be determined because two different AS's will report  that  they
can reach the same net.

With  such  a  dynamic  tree,  there may be preferred and backup links. In such
cases it is necessary to monitor the failed link so that routing can be changed
back to the preferred link when service is restored.

Another aspect to consider is the possibility of detecting  routing  loops  and
then  breaking  them. Expiration of the packet time-to-live (TTL) could be used
to do this. If such a loop is suspected a diagnostic packet, such as ICMP echo,
could be sent over the suspect route to confirm whether it is a loop. If a loop
is detected a special  routing  packet  could  be  sent  over  the  route  that
instructs  each gateway to delete the route after forwarding the packet on. The
acceptance of new routing information may need to be delayed for  a  hold  down
period.  This approach would require sensible selection of the initial TTL. But
this is not done by many hosts.



5.1.2 Current Policy

Considering the general trend to  increased  network  interconnection  and  the
availability of alternative long-haul networks such as ARPANET, WBNET (wideband
satellite  network),  and public data networks the tree topology restriction is
generally unacceptable. A less restrictive topology is  currently  recommended.
The following is taken from [Mills 84b].

EGP topological model:

   - An  autonomous  system  consists  of  a  set of gateways connected by
     networks.  Each gateway in the system must be  reachable  from  every
     other  gateway in its system by paths including only gateways in that
     system.

   - A gateway in a system may run EGP with a gateway in any other  system
     as  long  as the path over which EGP itself is run does not include a
     gateway in a third system.

   - The "core system" is distinguished from the others by the  fact  that
     only  it  is  allowed  to  distribute  reachability information about
     systems other than itself.

   - At least one gateway in every system must have a net in common with a
     gateway in the core system.
^L
RFC 911                                                                      15


   - There  are  no  topological  or  connectivity restrictions other than
     those implied above.

A gateway  will  use  information  derived  from  its  configuration  (directly
connected  nets),  the  IGP of its system, called S in the following, (interior
nets) and EGP (interior and exterior nets of neighboring systems) to  construct
its routing tables. If conflicts with respect to a particular net N occur, they
will be resolved as follows:

   - If  N  is  directly connected to the gateway, all IGP and EGP reports
     about N are disregarded.

   - If N is reported by IGP as  interior  to  S  and  by  EGP  as  either
     interior  or  exterior  to  another  system,  the  IGP  report  takes
     precedence.

   - If N is reported by EGP as interior to one  system  and  exterior  to
     another, the interior report takes precedence.

   - If  N  is  reported  as  interior by two or more gateways of the same
     system using EGP, the reports specifying the smallest hop count  take
     precedence.

   - In all other cases the latest received report takes precedence.

Old information will be aged from the tables.

The   interim   model  provides  an  acceptable  degree  of  self-organization.
Transient routing loops can occur between systems,  but  these  are  eventually
broken by old reachability information being aged out of the tables.  Given the
fact  that  transient  loops  can occur due to temporary core-system loops, the
additional loops that might occur in the case of local nets homed  to  multiple
systems does not seem to increase the risk significantly.


5.2 Present ISI Configuration

A  simplified  version of the ISI network configuration is shown in Figure 5-1.
ISI-Hobgoblin can provide a backup gateway function  to  the  core  ISI-Gateway
between  ARPANET and ISI-NET. ISI-Hobgoblin is a VAX 11/750 which runs Berkeley
Unix  4.2.  The  EGP  implementation  described  in  this  report  is  run   on
ISI-Hobgoblin.

ISI-Troll  is part of a split gateway to the University of California at Irvine
network (UCI-ICS). The complete logical gateway consists of ISI-Troll, the 9600
baud link and UCI-750A [Rose 84]. ISI-Troll runs Berkeley Unix 4.1a  and  hence
cannot  run  the  EGP  program.  It  is  therefore  a non-routing gateway.  The
existence of UCI-ICS net must be advised to the core AS by ISI-Hobgoblin.  This
can be done by including an appropriate entry in the EGPINITFILE.

Hosts on ISI-NET, including ISI-Troll, have  static  route  entries  indicating
ISI-Gateway as the first hop for all networks other than UCI-ICS and ISI-NET.
^L
RFC 911                                                                      16


          -------------------------------------------------
         /                                                 \
        /                      ARPANET                      \
        \                        10                         /
         \                                                 /
          -------------------------------------------------
             |                    |                    |
             |                    |                    |
             |                    |                    |
      +-------------+      +-------------+      +---------------+
      | ISI-PNG11   |      |             |      |               |
      | Arpanet     |      | ISI-GATEWAY |      | ISI-HOBGOBLIN |
      | Address     |      |             |      |   Vax 11/750  |
      | logical     |      |  Core EGP   |      |   Unix 4.2    |
      | multiplexer |      |             |      |               |
      +-------------+      +-------------+      +---------------+
             |                    |                    |
             |                    |                    |
             |                    |                    |
      ---------------          ----------------------------
     /               \        /                            \
    / 3 Mb/s Ethernet \      /           ISI-NET            \
    \     net 10      /      \            128.9             /
     \               /        \                            /
      ---------------          ----------------------------
                                      |
                                      |
                                      |
                               +--------------+
                               |  ISI-TROLL   |
                               |  Vax 11/750  |
                               |  Unix 4.1a   |
                               |  Non-routing |
                               |      |       |
                               |      | 9600  |   ISI-TROLL, UCI-750A
                               |      | baud  |   and the link form a
                               |      | link  |   single logical gateway
                               |      |       |
                               |  UCI-750A    |
                               |  Vax 11/750  |
                               |  Unix 4.2    |
                               +--------------+
                                      |
                                      |
                                      |
                            ----------------------
                           /                      \
                          /        UCI-ICS         \
                          \        192.5.19        /
                           \                      /
                            ----------------------


              Figure 5-1:   Simplified ISI Network Configuration
^L
RFC 911                                                                      17


EGP can either be conducted with ISI-Gateway across ARPANET or ISI-NET.



5.2.1 EGP Across ARPANET

ISI-Hobgoblin  will  advise  ISI-Gateway  across  ARPANET,  and  hence the core
system, that it can reach ISI-NET and UCI-ICS.

Packets from AS's exterior to ISI and destined for UCI-ICS will be  routed  via
ISI-Gateway,  ISI-Hobgoblin  and  ISI-Troll.  The extra hop via ISI-Gateway (or
other core EGP gateway) is because the core gateways do not currently  pass  on
indirect-neighbor   exterior   gateway   addresses   in   their   IGP  messages
(Gateway-to-Gateway Protocol).  Packets originating from UCI-ICS  destined  for
exterior  AS's will be routed via ISI-Troll and ISI-Gateway.  Thus the incoming
and out going packet routes are different.

Packets originating from ISI-Hobgoblin as a host and destined for exterior AS's
will be routed via the appropriate gateway on ARPANET.

UCI-ICS can only communicate with exterior AS's if ISI-Troll, ISI-Hobgoblin and
ISI-Gateway are all up. The dependence on ISI-Gateway could  be  eliminated  if
ISI-Troll  routed  packets via ISI-Hobgoblin rather than ISI-Gateway.  However,
as ISI-Hobgoblin is primarily a host and not a gateway it  is  preferable  that
ISI-Gateway route packets when possible.

ISI-Hobgoblin  can  provide a back-up gateway function to ISI-Gateway as it can
automatically switch to an alternative core EGP peer if ISI-Gateway goes  down.
Even  though  ISI-Hobgoblin  normally advises the core system that it can reach
ISI-NET the core uses its own internal route  via  ISI-Gateway  in  preference.
For hosts on ISI-NET to correctly route outgoing packets they need their static
gateway  entries  changed  from  ISI-Gateway to ISI-Hobgoblin.  At present this
would have to be done manually. This would only be appropriate  if  ISI-Gateway
was going to be down for an extended period.



5.2.2 EGP Across ISI-NET

ISI-Hobgoblin   will  advise  ISI-Gateway  across  ISI-NET  that  its  indirect
neighbor, ISI-Troll, can reach UCI-ICS net.

All exterior packet routing  for  UCI-ICS  will  be  via  ISI-Gateway  in  both
directions   with   no  hops  via  ISI-Hobgoblin.    Packets  originating  from
ISI-Hobgoblin as a host and destined for  exterior  AS's  will  be  routed  via
ISI-Gateway, rather than the ARPANET interface, in both directions, thus taking
an additional hop.

UCI-ICS  can  only  communicate with exterior AS's if ISI-Troll and ISI-Gateway
are up and ISI-Hobgoblin has advised  ISI-Gateway  of  the  UCI-ICS  route.  If
ISI-Hobgoblin   goes   down,  communication  will  still  be  possible  because
ISI-gateway (and other core gateways)  do  not  time  out  routes  to  indirect
^L
RFC 911                                                                      18


neighbors.  If  ISI-Gateway  then  goes  down,  it will need to be readvised by
ISI-Hobgoblin of the UCI-ICS route, when it comes up.

Conducting EGP over ISI-NET rather than ARPANET should  provide  more  reliable
service  for  UCI-ICS  for  the  following reasons: ISI-Gateway is specifically
designed as a gateway, it is expected to be up more than ISI-Hobgoblin,  it  is
desirable  to  eliminate  extra  routing  hops where possible and, the exterior
routing  information  will  persist  after  ISI-hobgoblin  goes   down.      If
ISI-Hobgoblin  is to be used in its back-up mode, EGP could be restarted across
ARPANET after the new gateway routes  are  manually  installed  in  the  hosts.
Therefore, EGP across ISI-NET was selected as the preferred mode of operation.



5.2.3 Potential Routing Loop

Because  both  ISI-Gateway and ISI-Hobgoblin provide routes between ARPANET and
ISI-NET there is a potential routing loop. This topology in fact  violates  the
original  tree  structure  restriction. Provided ISI-Hobgoblin does not conduct
EGP simultaneously with ISI-Gateway over ISI-NET and ARPANET, the gateways will
only ever know about the alternative route from the shared EGP network and  not
from  the  other  network.  Thus  a loop cannot occur.  For instance, if EGP is
conducted over ISI-NET, both ISI-Gateway and ISI-Hobgoblin will know about  the
alternative  routes  via  each other to ARPANET from ISI-NET, but they will not
know about the gateway addresses on ARPANET to be able to access  ISI-NET  from
ARPANET.  Thus  they have insufficient routing data to be able to route packets
in a loop between themselves.


5.3 Possible Future Configuration



5.3.1 Gateway to UCI-ICS

An improvement in the reliability and performance of  the  service  offered  to
UCI-ICS  can  be  achieved  by  moving  the UCI-ICS interface from ISI-Troll to
ISI-Hobgoblin. Reliability  will  improve  because  the  connection  will  only
require  ISI-Hobgoblin  and its ARPANET interface to be up and performance will
improve because the extra gateway hop will be eliminated.

This will also allow EGP to be conducted across ARPANET giving  access  to  the
alternative  core gateways running EGP. This will increase the chances of being
able to reliably acquire an EGP neighbor at all times. It will  also  eliminate
the  extra hop via ISI-Gateway for packets originating from ISI-Hobgoblin, as a
host, and destined for exterior networks.

This configuration change will be made at sometime in the future.  It  was  not
done  initially because ISI-Hobgoblin was experimental and down more often than
ISI-Troll.
^L
RFC 911                                                                      19


5.3.2 Dynamic Switch to Backup Gateway

It  was  noted in Section 5.2.1 that ISI-Hobgoblin can provide a backup gateway
function to ISI-Gateway between ARPANET and ISI-NET. Such backup gateways could
become a common approach to providing increased reliability.

At present the change over to the backup gateway requires the new gateway route
to be manually entered for hosts on ISI-NET. This section describes a  possible
method  for achieving this changeover dynamically when the primary gateway goes
down.

The aim is to be able to detect when the primary gateway is down and  have  all
hosts  on  the local network change to the backup gateway with a minimum amount
of additional network traffic. The hosts should  revert  back  to  the  primary
gateway when it comes up again.

The  proposed  method  is  for  only  the backup gateway to monitor the primary
gateway status and for it to notify all hosts of the new gateway  address  when
there is a change.


5.3.2.1 Usual Operation

The backup gateway runs a process which sends reachability-probe messages, such
as  ICMP echoes, to the primary gateway every 30 seconds and uses the responses
to determine reachability as for EGP.  If  the  primary  gateway  goes  down  a
"gateway-address  message"  indicating  the backup gateway address is broadcast
(or preferably multicast) to all hosts.  When  the  primary  gateway  comes  up
another  gateway  message  indicating the primary gateway address is broadcast.
These broadcasts should be done four times at 30 second intervals to avoid  the
need for acknowledgements and knowledge of host addresses.

Each  host  would run a process that listens for gateway-address messages. If a
different gateway is advised it changes the default gateway entry  to  the  new
address.


5.3.2.2 Host Initialization

When  a  host comes up the primary gateway could be down so it needs to be able
to determine that it should use the backup gateway. The  host  could  read  the
address  of  the primary and backup gateways from a static initialization file.
It would then set its default  gateway  as  the  primary  gateway  and  send  a
"gateway-request  message" to the backup gateway requesting the current gateway
address. The backup gateway would respond with a gateway-address message.    If
no response is received the gateway-request should be retransmitted three times
at  30  second intervals.  If no response is received the backup gateway can be
assumed down and the primary gateway retained as the default.

Whenever the backup gateway comes up it broadcasts a gateway-address message.

Alternatively, a broadcast (or  multicast)  gateway-request  message  could  be
^L
RFC 911                                                                      20


defined  to  which  only  gateways  would  respond.  The backup gateway-address
message needs to indicate that it is the backup gateway so that future requests
need not be broadcast. Again, three retransmissions should be used.    But  the
primary gateway also needs to broadcast its address whenever it comes up.


5.3.2.3 When Both the Primary and Backup are Down

If the primary gateway is down and the backup knows it is going down, it should
broadcast  gateway-address  messages indicating the primary gateway in case the
primary gateway comes up first.

But the backup could go down without warning and the primary come up before it.
If the primary gateway broadcasts a gateway-address message when  it  comes  up
there  is  no problem. Otherwise, while hosts are using the backup gateway they
should send a gateway-request message every  10  minutes.  If  no  response  is
received it should be retransmitted 3 times at 30 second intervals and if still
no response the backup assumed down and the primary gateway reverted to.

Thus the only time hosts need to send messages periodically is when the primary
gateway  does  not  send  gateway-address  messages on coming up and the backup
gateway is being used. In some cases, such as at ISI, the  primary  gateway  is
managed  by  a  different  organization  and  experimental  features  cannot be
conveniently added.


5.3.2.4 Unix 4.2 BSD

One difficulty with the above is that there is no standard method of specifying
internet broadcast or multicast addresses. Multicast addressing  is  preferable
as  only those participating need process the message (interfaces with hardware
multicast detection are available). In the case of Unix  4.2  BSD  an  internet
address  with zero local address is assumed for the internet broadcast address.
However, the general Internet Addressing policy is to use an all ones value  to
indicate a broadcast function.

On  Unix  4.2  BSD systems, both the gateway and host processes could be run at
the user level so that kernel modifications are not required.

A User Datagram Protocol (UDP) socket could be reserved for host-backup-gateway
communication.

Super user access to raw sockets for sending and receiving ICMP  Echo  messages
requires a minor modification to the internet-family protocol switch table.
^L
RFC 911                                                                      21


6. ACKNOWLEDGEMENT

I acknowledge with thanks the many people who have helped me with this project,
but  in  particular,  Dave  Mills,  who  suggested  the project, Jon Postel for
discussion and encouragement, Liza Martin for providing the initial  EGP  code,
Berkeley  for  providing  the  "routed"  code, Mike Brescia for assistance with
testing, Telecom Australia for funding me, and ISI for providing facilities.
^L
RFC 911                                                                      22


7. REFERENCES


[Berkeley 83]   "Unix  Programmer's  Manual",  Vol.  1,  4.2  Berkeley Software
                Distribution, University of California, Berkeley.

[Kirton 84]     Kirton, P.A., "EGP Gateway Under Berkeley Unix 4.2", University
                of  Southern  California,   Information   Sciences   Institute,
                Research Report ISI/RR-84-145, to be published.

[Mills 83]      Mills,  D.L.,  "EGP Models and Self-Organizing Systems" Message
                to EGP-PEOPLE@BBN-UNIX, Nov. 1983.

[Mills 84a]     Mills, D.L., "Exterior Gateway Protocol Formal  Specification",
                Network Information Center RFC 904, April 1984.

[Mills 84b]     Mills,  D.L.,  "Revised  EGP  Model  Clarified  and Discussed",
                Message to EGP-PEOPLE@BBN-UNIX, May 1984.

[Postel 84]     Postel, J., "Exterior Gateway Protocol Implementation Schedule"
                Network Information Center RFC 890, Feb. 1984.

[Rose 84]       Rose, M.T., "Low-Tech Connection into  the  ARPA-Internet:  The
                Raw-Packet   Split  Gateway",  Department  of  Information  and
                Computer Science, University of California,  Irvine,  Technical
                Report 216, Feb. 1984.

[Rosen 82]      Rosen,  E.C.,  "Exterior Gateway Protocol", Network Information
                Center RFC 827, Oct. 1982.

[Seamonson & Rosen 84]
                Seamonson,  L.J.  and  Rosen,  E.C.,  "Stub  Exterior   Gateway
                Protocol", Network Information Center RFC 888, Jan. 84.

[Xerox 81]      "Internet   Transport   Protocols",  Xerox  System  Integration
                Standard XSIS 028112, Dec. 1981.