rfc823.txt

来自「RFC 的详细文档！」· 文本 代码 · 共 2,611 行 · 第 1/5 页

     DARPA Internet Gateway                             September 1982
     RFC 823



     4.4.3  Exchanging Routing Information


          The gateway sends routing information in GGP Routing  Update

     messages.  The gateway receives and transmits routing information

     reliably using sequence-numbered messages  and  a  retransmission

     and acknowledgment scheme as explained below.  For each neighbor,

     the gateway remembers the Receive Sequence  Number,  R,  that  it

     received  in  the  most recent routing update from that neighbor.

     This value is initialized with the sequence number in  the  first

     Routing  Update  received  from  a neighbor after that neighbor's

     status is set to "up."  On receipt of a  routing  update  from  a

     neighbor,  the  gateway subtracts the Receive Sequence Number, R,

     from the sequence number in the routing update, S. If this  value

     (S-R)  is greater than or equal to zero, then the gateway accepts

     the routing update, sends an acknowledgment (see Appendix  A)  to

     the  neighbor  containing the sequence number S, and replaces the

     Receive Sequence Number, R, with S. If this value (S-R)  is  less

     than  zero,  the  gateway  rejects the routing update and sends a

     negative  acknowledgment  [Appendix  A]  to  the  neighbor   with

     sequence number R.


          The gateway has a  Send  Sequence  Number,  N,  for  sending

     routing  updates  to  all of its neighbors.  This sequence number




                                   -17-





     DARPA Internet Gateway                             September 1982
     RFC 823



     can be initialized to any value.  The  Send  Sequence  Number  is

     incremented  each  time  a  new  routing  update  is created.  On

     receiving an acknowledgment for a  routing  update,  the  gateway

     subtracts  the  sequence  number  acknowledged,  A, from the Send

     Sequence Number, N.  If the value (N-A) is non-zero, then an  old

     routing  update  is being acknowledged.  The gateway continues to

     retransmit the most recent routing update to  the  neighbor  that

     sent  the  acknowledgment.   If (N-A) is zero, the routing update

     has been acknowledged.  Note that only the  most  recent  routing

     update  must  be  acknowledged;  if  a  second  routing update is

     generated before the first routing update is  acknowledged,  only

     the second routing update must be acknowledged.


          If  a  negative  acknowledgment  is  received,  the  gateway

     subtracts  the  sequence  number negatively acknowledged, A, from

     its Send Sequence Number, N.  If this value (N-A)  is  less  than

     zero, then the gateway replaces its Send Sequence Number, N, with

     the sequence number negatively acknowledged plus  one,  A+1,  and

     retransmits the routing update to all of its neighbors.  If (N-A)

     is greater than or equal to zero, then the gateway  continues  to

     retransmit  the routing update using sequence number N.  In order

     to maintain the correct sequence numbers at all gateways, routing

     updates  must  be  retransmitted  to  all  neighbors  if the Send



                                   -18-





     DARPA Internet Gateway                             September 1982
     RFC 823



     Sequence Number changes, even if the routing information does not

     change.


          The gateway retransmits routing updates  periodically  until

     they  are  acknowledged  and  whenever  its  Send Sequence Number

     changes.  The gateway sends routing  updates  only  to  neighbors

     that are in the "up" state.




     4.4.4  Computing Routes


          A routing update  contains  a  list  of  networks  that  are

     reachable  through  this  gateway, and the distance in "number of

     hops"  to  each  network  mentioned.   The  routing  update  only

     contains information about a network if the gateway believes that

     it is as close or closer to that network then the neighbor  which

     is  to receive the routing update.  The network address may be an

     internet class A, B, or C address.


          The information inside a  routing  update  is  processed  as

     follows.   The gateway contains an N x K distance matrix, where N

     is the number of  networks  and  K  is  the  number  of  neighbor

     gateways.   An  entry  in this matrix, represented as dm(I,J), is

     the distance to network I from neighbor J as reported in the most




                                   -19-





     DARPA Internet Gateway                             September 1982
     RFC 823



     recent routing update from neighbor J.  The gateway also contains

     a vector indicating  the  connectivity  between  itself  and  its

     neighbor  gateways.   The  values  in this vector are computed as

     discussed above (see Section 4.4.2, Determining  Connectivity  to

     Neighbors).   The value of the Jth entry of this vector, which is

     the connectivity between the gateway and  the  Jth  neighbor,  is

     represented as d(J).


          The gateway copies the routing update received from the  Jth

     neighbor  into  the  appropriate row of the distance matrix, then

     updates its routes as follows.  The gateway calculates a  minimum

     distance  vector  which  contains  the  minimum  distance to each

     network  from  the  gateway.   The  Ith  entry  of  this  vector,

     represented as MinD(I) is:


       MinD(I) = minimum over all neighbors of d(J) + dm(I,J)


     where d(J) is the  distance  between  the  gateway  and  the  Jth

     neighbor,  and  dm(I,J)  is the distance from the Jth neighbor to

     the Ith network.  If the Ith network is attached to  the  gateway

     and  the  gateway  can  send  and  receive traffic on its network

     interface (see Section 4.4.2), then  the  gateway  sets  the  Ith

     entry of the minimum distance vector to zero.





                                   -20-





     DARPA Internet Gateway                             September 1982
     RFC 823



          Using the minimum distance vector, the  gateway  computes  a

     list  of  neighbor gateways through which to send traffic to each

     network.  The entry for a  given  network  contains  one  of  the

     neighbors that is the minimum distance away from that network.


          After updating its  routes  to  the  networks,  the  gateway

     computes  the  new  routing  updates to be sent to its neighbors.

     The gateway reports a network to a neighbor  only  if  it  is  as

     close  to  or closer to that network than its neighbor.  For each

     network I, the routing update contains the address of the network

     and the minimum distance to that network which is MinD(I).


          Finally, the gateway must determine whether it  should  send

     routing  updates to its neighbors.  The gateway sends new updates

     to its neighbors if every one of the following  three  conditions

     occurs:   1)  one  of the gateway's interfaces changes state,  2)

     one of the gateway's neighbor gateways changes state, and  3) the

     gateway  receives  a  routing  update  from  a  neighbor  that is

     different from the update that it had  previously  received  from

     that  neighbor.   The  gateway  sends  routing  updates  only  to

     neighbors that are currently in the "up" state.


          The gateway requests a routing update  from  neighbors  that

     are  in  the  "up"  state,  but  from which it has yet received a



                                   -21-





     DARPA Internet Gateway                             September 1982
     RFC 823



     routing update.  Routing updates are  requested  by  setting  the

     appropriate  bit  in  the routing update being sent [Appendix A].

     Similarly, if a gateway receives from a neighbor a routing update

     in  which the bit requesting a routing update is set, the gateway

     sends the neighbor the most recent routing update.




     4.4.5  Non-Routing Gateways


          A Non-routing Gateway is a gateway  that  forwards  internet

     traffic,  but  does  not  implement  the  GGP  routing algorithm.

     Networks that are behind a Non-routing Gateway are known a-priori

     to  Routing Gateways.  There can be one or more of these networks

     which are considered to be directly connected to the  Non-routing

     Gateway.   A  Routing  Gateway  will forward a datagram to a Non-

     routing Gateway if it is addressed to a network behind  the  Non-

     routing   Gateway.    Routing  Gateways  currently  do  not  send

     Redirects for  Non-routing  Gateways.   A  Routing  Gateway  will

     always  use  another  Routing Gateway as a path instead of a Non-

     routing Gateways if both exist and are the same  number  of  hops

     away from the destination network.  The Non-routing Gateways path

     will be used only when the Routing Gateway path is down; when the

     Routing Gateway path comes back up, it will be used again.




                                   -22-





     DARPA Internet Gateway                             September 1982
     RFC 823



     4.4.6  Adding New Neighbors and Networks


          Gateways  dynamically  add  routing  information  about  new

     neighbors   and  new  networks  to  their  tables.   The  gateway

     maintains a list of neighbor gateway addresses.  When  a  routing

     update  is  received, the gateway searches this list of addresses

     for the Internet source address of the  routing  update  message.

     If  the  Internet  source  address  of  the routing update is not

     contained in the list of neighbor  addresses,  the  gateway  adds

     this  address  to  the  list  of  neighbor addresses and sets the

     neighbor's connectivity status to "down."   Routing  updates  are

     not  accepted  from neighbors until the GGP polling mechanism has

     determined that the neighbor is up.


          This strategy of adding  new  neighbors  requires  that  one

     gateway   in  each  pair  of  neighbor  gateways  must  have  the

     neighbor's address configured in its tables.  The newest  gateway

     can be given a complete list of neighbors, thus avoiding the need

     to re-configure older gateways when new gateways are installed.


          Gateways obtain routing information about  new  networks  in

     several  steps.   The  gateway has a list of all the networks for

     which it currently maintains routing information.  When a routing

     update  is  received,  if the routing update contains information



                                   -23-





     DARPA Internet Gateway                             September 1982
     RFC 823



     about a new network, the gateway adds this network to the list of

     networks  for  which it maintains routing information.  Next, the

     gateway adds  the  new  network  to  its  distance  matrix.   The

     distance  matrix comprises the is the matrix of distances (number

     of hops) to networks as reported  in  routing  updates  from  the

     neighbor  gateways.   The  gateway  sets  the distance to all new

     networks to "infinity," and then  computes  new  routes  and  new

     routing updates as outlined above.




     4.5  Exterior Gateway Protocol


          The Exterior Gateway Protocol (EGP) is used to permit  other

     gateways  and  gateway systems to pass routing information to the

     DARPA Internet gateways.  The use of the EGP permits the user  to

     perceive  all  of  the networks and gateways as part of one total

     Internet system, even though the "exterior" gateways are disjoint

     and  may  use  a  routing  algorithm  that  is  different and not

     compatible with  that  used  in  the  "interior"  gateways.   The

     important elements of the EGP are:


     o Neighbor Acquisition

          The procedure by which a gateway requests that it  become  a
          neighbor  of  another  gateway.  This is used when a gateway
          wants to become a neighbor  of  another  in  order  to  pass



                                   -24-





     DARPA Internet Gateway                             September 1982
     RFC 823



          routing information.  This includes the capability to accept
          or refuse the request.

     o Neighbor Up/Down

          The procedure by which a gateway decides if another  gateway
          is up or down.

     o Network Reachability Information

          The facility used to pass routing and  neighbor  information
          between gateways.

     o Gateway Going Down

          The ability of a gateway to inform other gateways that it is
          going  down  and  no  longer  has  any  routes  to any other
          networks.  This permits a gateway to go down in  an  orderly
          way without disrupting the rest of the Internet system.


     A complete description of the EGP can be found  in  IEN-209,  the

     "Exterior Gateway Protocol" [10].























                                   -25-





     DARPA Internet Gateway                             September 1982