6.3. Pseudo-Algol Routing Algorithm

This is a pseudo-Algol description of the routing algorithm a gateway should use. The algorithm is shown in figure 1. Some definitions are:

      RouteLink(host)

         A function taking a host address as a parameter and returning
         the first-hop link from the gateway to the host.

      RouteHost(host)

         As above but returns the first-hop host address.

      ResolveAddress(host)

         Returns the hardware address for an IP host.

      IncomingLink

         The link on which the packet arrived.

      OutgoingLinkSet

         The set of links on which the packet should be sent.

      OutgoingHardwareHost

         The hardware host address to send the packet to.

      Destination.host

         The host-part of the destination address.

      Destination.subnet

         The subnet-part of the destination address.

      Destination.ipnet

         The IP-network-part of the destination address.

Figure 1: Pseudo-Algol algorithm for routing broadcasts by gateways

BEGIN
   IF Destination.ipnet IN AllLinks THEN
      BEGIN
         IF IsSubnetted(Destination.ipnet) THEN
            BEGIN
               IF Destination.subnet = BroadcastSubnet THEN
                  BEGIN      /* use Reverse Path Forwarding algorithm */
                     IF IncomingLink = RouteLink(Source) THEN
                        BEGIN IF Destination.host = BroadcastHost THEN
                              OutgoingLinkSet <- AllLinks -
                           IncomingLink;
                           OutgoingHost <- BroadcastHost;
                           Examine packet for possible internal use;
                        END
                     ELSE  /* duplicate from another gateway, discard */
                        Discard;
                  END
               ELSE
                  IF Destination.subnet = IncomingLink.subnet THEN
                     BEGIN           /* forwarding would cause a loop */
                        IF Destination.host = BroadcastHost THEN
                           Examine packet for possible internal use;
                        Discard;
                     END
                  ELSE BEGIN    /* forward to (possibly local) subnet */
                        OutgoingLinkSet <- RouteLink(Destination);
                        OutgoingHost <- RouteHost(Destination);
                     END
            END
         ELSE BEGIN         /* destined for one of our local networks */
               IF Destination.ipnet = IncomingLink.ipnet THEN
                  BEGIN              /* forwarding would cause a loop */
                     IF Destination.host = BroadcastHost THEN
                        Examine packet for possible internal use;
                     Discard;
                  END
               ELSE BEGIN                     /* might be a broadcast */
                     OutgoingLinkSet <- RouteLink(Destination);
                     OutgoingHost <- RouteHost(Destination);
                  END
            END
      END
   ELSE BEGIN                    /* forward to a non-local IP network */
         OutgoingLinkSet <- RouteLink(Destination);
         OutgoingHost <- RouteHost(Destination);
      END
   OutgoingHardwareHost <- ResolveAddress(OutgoingHost);
END