[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00

NETWORK Working Group                                 Cuneyt Akinlar
INTERNET-DRAFT                                        David Braun
Category: Informational                               Sarit Mukherjee
<draft-akinlar-zeroconf-zrip-00.txt>                  Panasonic Research
August 15 2000

     ZRIP: Zero-Configuration Routing Information Protocol

Status of this Memo

  This document is an Internet-Draft and is in full conformance with all
provisions of Section 10 of RFC2026.

Internet-Drafts are working documents of the Internet Engineering Task
Force (IETF), its areas, and its working groups.  Note that other groups
may also distribute working documents as Internet-Drafts.  Internet-
Drafts are draft documents valid for a maximum of six months and may be
updated, replaced, or obsoleted by other documents at any time.  It is
inappropriate to use Internet-Drafts as reference material or to cite
them other than as "work in progress."

     The list of current Internet-Drafts can be accessed at
     http://www.ietf.org/ietf/1id-abstracts.txt

     The list of Internet-Draft Shadow Directories can be accessed at
     http://www.ietf.org/shadow.html.

The distribution of this memo is unlimited.  It is filed as <draft-
akinlar-zeroconf-zrip-00.txt>, and expires February 15, 2001. Please
send comments to the authors.

Abstract

   Zero-Configuration(Zeroconf) Networking is becoming highly popular
with the proliferation of cheap network attached devices and computers.
Zeroconf networks are a particular class of TCP/IP networks that may be
established in the home, in small offices or for ad-hoc purposes.
Zeroconf networks do not have and should not be expected to have user
configurable network infrastructure such as DHCP, DNS and other
administered services [4].

  Zeroconf networks can consist of single segments, multiple segments
connected by a single router as well as multiple segments connected by
multiple routers. Router auto-configuration is an important problem in
multi-router zeroconf networks. Although a router can easily self-
configure itself by assigning unique subnet numbers to each of its
interfaces from a private address range, auto-configuring a multi-router
network formed by connecting several such self-configuring routers is a
major issue. In [5], the author proposes that a zeroconf router self-
configures itself by assigning an internally unique subnet number to
each of its interfaces from the private address range 192.168.x/24
during initialization. When several such self-configuring routers are
connected together to form a multi-router zeroconf network, there is a
need for not only dynamic exchange of routing information between the
routers but also for consistent subnet assignment in the network. That
is, all segments of the zeroconf network must have unique subnet
numbers. As new routers are added to the zeroconf network, any subnet
conflicts must be detected and resolved.

  Two types of dynamic routing protocols are used in administered



Akinlar, Braun, Mukherjee       Informational           [Page 1]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


networks: Distance Vector protocols exemplified by RIP [1, 2] and link-
state protocols exemplified by OSPF [3]. This draft describes how RIP
can be changed to solve both the problem of dynamic routing exchange and
consistent subnet assignment in zeroconf networks. We call the protocol
Zero-Configuration Routing Information Protocol, ZRIP.

Conventions

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [6].

1. Zero-Configuration Networks

  Zero Configuration (Zeroconf) Networks are a particular class of
TCP/IP networks. These networks may be established in a home, small
office or for ad-hoc purposes. Zeroconf networks typically do not have
and should not be expected to have user configurable network iDS
Lrastructure such as DHCP, DNS and other administered services [4].

  Zeroconf networks could range from very simple networks such as two
hosts connected back to back, to medium complex networks such as multi-
segment networks connected by a single router to the most complex
networks with multiple segments connected by multiple routers.

  Each router in a zeroconf network self-configures itself during
initialization by randomly assigning a subnet number and a subnet mask
to each of its directly connected segments(interfaces). In [5] the
author proposes that a zeroconf router assign a unique subnet number
from the private address space 192.168.x/24 to each of its interfaces
during initialization. After the unique subnet assignment is done, the
router starts a mini-DHCP server to configure the hosts connected to
each segment.

  In this draft we consider multi-router zeroconf networks formed by
connecting several self-configuring routers. Because each router self-
configures itself independent of other routers, there can be subnet
conflicts when two or more routers coincidentally select the same subnet
number. In such networks, there is a need not only for routers to
exchange routing information but also for subnet conflict or collision
detection and resolution. The network MUST automatically be brought to a
consistent state as quickly as possible. The consistent (stable) state
is defined as one where each IP segment within the zeroconf network has
a unique subnet number.

  RIP[2] (In this draft RIP refers to RIP Version 2 [RFC 2453]) and OSPF
are two popular dynamic routing protocols used in administered networks.
In this draft we describe how RIP can be changed to solve both the
problem of dynamic routing exchange and subnet conflict detection and
resolution in zeroconf networks.

2. Can RIP Detect Subnet Conflicts?

  In an administered network, RIP is used to exchange routing
information between the routers in the network. Subnet conflict
detection is not an issue in this case since there won't be subnet
conflicts in a network that is correctly administered.

  A RIP packet consists of a header and several Routing Table Entry(RTE)
records. The RIP packet format is [2]:



Akinlar, Braun, Mukherjee       Informational           [Page 2]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |  command (1)  |  version (1)  |       must be zero (2)        |
      +---------------+---------------+-------------------------------+
      |                                                               |
      ~                         RIP Entry (20)                        ~
      |                                                               |
      +---------------+---------------+---------------+---------------+


The format for the 20-octet route entry (RTE) for RIP-2 is [2]:


    0                   1                   2                   3 3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Address Family Identifier (2) |        Route Tag (2)          |
   +-------------------------------+-------------------------------+
   |                         IP Address (4)                        |
   +---------------------------------------------------------------+
   |                         Subnet Mask (4)                       |
   +---------------------------------------------------------------+
   |                         Next Hop (4)                          |
   +---------------------------------------------------------------+
   |                         Metric (4)                            |
   +---------------------------------------------------------------+



  Figure 1 depicts a zeroconf network with 2 routers and a gateway which
connects the zeroconf network to a non-zeroconf network such as the
Internet. Assume that initially R1 and R2 are stand-alone routers.
Router R1, during initialization, assigns subnet numbers X, Y and Z to
its interfaces 1, 2 and 3 respectively. Similarly, R2 assigns subnet
numbers V, X and W to its interfaces 1, 2 and 3. The hosts on the seg-
ments connected to each router can configure themselves from the mini-
DHCP running at the router as suggested in [5]. Thus, host A, B and C
will be configured by the mini-DHCP server running at R1, D, E and F
will be configured by the mini-DHCP server running at R2. Now, routers
R1 and R2 are connected together at the point marked (X) on the segment
that host C and D are connected to. That is, interface 3 of R1 is con-
nected to interface 1 of R2. In an administered network using RIPv2, the
routers exchange RIP messages and learn the new routes.



















Akinlar, Braun, Mukherjee       Informational           [Page 3]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


                  +---------------------------+
                  |   Non-Zeroconf Network    |
                  +------------+--------------+
                               |
                      +--------+-------+
   *******************|     Gateway    |************************
   * Zeroconf Network +-+--------------+                       *
   *                    |                                      *
   *                    |                                      *
   *           ***********                ***********          *
   *           *   R1    *                *   R2    *          *
   * +---+     *         *                *         *    +---+ *
   * | A |-----*1(X) 3(Z)*----+--X---+----*1(V) 3(W)*----| F | *
   * +---+     *         *    |      |    *         *    +---+ *
   *           *   2(Y)  *  +---+  +---+  *   2(X)  *          *
   *           ***********  | C |  | D |  ***********          *
   *                |       +---+  +---+       |               *
   *              +---+                      +---+             *
   *              | B |                      | E |             *
   *              +---+                      +---+             *
   *                                                           *
   *************************************************************

     Figure 1: A zeroconf network with 2 routers and a gateway


  Assume that R1 sends a RIP packet first. Below we show the RTEs con-
tained in this RIP message:



 IP | netmask   | next-hop | metric
----+-----------+----------+-------
 X  | netmask11 | Z.R13    |  1
 Y  | netmask12 | Z.R13    |  1
 Z  | netmask13 | Z.R13    |  1


Before R2 receives the first RIP packet from R1, its routing table is as
follows:


 Destination|  Gateway   | Netmask   | Flags |Interface | Metric
 -----------+------------+-----------+-------+----------+-------
 127.0.0.0  | 127.0.0.1  | 255.0.0.0 |  UH   |   lo     |   1
 V.0        | V.R21      | netmask21 |  UG   |   1      |   1
 X.0        | X.R22      | netmask22 |  UG   |   2      |   1
 W.0        | W.R23      | netmask23 |  UG   |   3      |   1


When R2 receives the RIP packet from R1, it calculates a new routing
table augmented with the new routes it just learned:











Akinlar, Braun, Mukherjee       Informational           [Page 4]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


 Destination|  Gateway   | Netmask   | Flags |Interface | Metric
 -----------+------------+-----------+-------+----------+-------
 127.0.0.0  | 127.0.0.1  | 255.0.0.0 |  UH   |   lo     |   1
 V.0        | V.R21      | netmask21 |  UG   |   1      |   1
 X.0        | X.R22      | netmask22 |  UG   |   2      |   1
 W.0        | W.R23      | netmask23 |  UG   |   3      |   1
 Y.0        | Z.R13      | netmask12 |  UG   |   1      |   2
 Z.0        | Z.R13      | netmask13 |  UG   |   1      |   2


Notice that the entry for subnet X.0 is unchanged. This is correct
according to the RIPv2 specification [2]. R2 discards the X.0 entry from
R1 since R2 already has a route with a better metric. There is no way R2
can detect that the two subnets are for different segments. RIP was
designed to operate in a "correct" environment where subnet numbers are
unique.

When R1 receives a RIP packet from R2 it will do a similar calculation
and will not change its subnet assignment on interface 1. So, at this
point there are 2 segments in the zeroconf network that use the same
subnet number. Hosts A, B and C cannot talk to host E. Similarly, hosts
D, E and F cannot talk to host A. The subnet conflict in the new zero-
conf network must be resolved. For consistency both routers have to
change their subnet assignment X to new unique subnet numbers and bring
the network to a consistent state. (The reason why both routers have to
change their conflicting subnet mappings is explained in Appendix A). As
the above example shows, regular RIP cannot detect subnet conflicts.

3. Unique Interface Identifier

  Each routing table entry (RTE) in a regular RIP message specifies a
subnet number, a netmask, the next hop router to reach the subnet and
the hop count to reach the subnet. This information is sufficient if
there won't be subnet conflicts as in an administered network. In a
zeroconf network however there could be more than one router that
assigns the same subnet number to its directly connected segments since
each router makes the subnet assignment decision independently. In order
to detect subnet conflicts after the routers are connected together, we
propose the use of a unique interface identifier (UID) with each RIP
entry. A UID uniquely identifies a segment connected to an interface of
a router within the zeroconf network. When a router boots up, it MUST
generate a UID for each of its interfaces and then randomly assign a
locally unique subnet number. Thus, each subnet is associated with a UID
that is unique within the zeroconf network.

  We propose that the UID be 9 bytes in length. The first byte is a
unique hardware type identifier for the interface. The remaining 8 bytes
can be generated from the hardware address of the interface or randomly
generated in case the interface does not have a hardware address. For
example, if the interface is Ethernet, the first byte will be IANA
assigned hardware number for Ethernet and the last 8 bytes of the UID
will be the 6 bytes of Ethernet hardware address concatenated with 2
bytes of 0's. Since Ethernet addresses are globally unique, this will
generate a unique UID for the interface within the zeroconf network. A
UID can be generated similarly for other types of interfaces.

  Each subnet number is now associated with a UID within the zeroconf
network. When a router advertises its routes, it now augments each RTE
with the UID associated with the subnet. In our example above, the con-
tents of the RIP packet that goes from R1 to R2 will now be:



Akinlar, Braun, Mukherjee       Informational           [Page 5]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


 UID   | IP | netmask   | next-hop | metric
-------+----+-----------+----------+-----
 UID11 | X  | netmask11 | Z.R13    |  1
 UID12 | Y  | netmask12 | Z.R13    |  1
 UID13 | Z  | netmask13 | Z.R13    |  1


Before R2 receives the first RIP packet from R1 its routing table is as
follows:


 UID   | Destination|  Gateway   | Netmask   | Flags |Interface | Metric
-------+------------+------------+-----------+-------+----------+-------
       | 127.0.0.0  | 127.0.0.1  | 255.0.0.0 |  UH   |   lo     |   1
 UID21 | V.0        | V.R21      | netmask21 |  UG   |   1      |   1
 UID22 | X.0        | X.R22      | netmask22 |  UG   |   2      |   1
 UID23 | W.0        | W.R23      | netmask23 |  UG   |   3      |   1



When R2 receives the RIP packet from R2, it calculates a new routing
table augmented with the new routes it just learned:


 UID   | Destination |  Gateway   | Netmask   | Flags |Interface | Metric
-------+-------------+------------+-----------+-------+----------+-------
       |  127.0.0.0  | 127.0.0.1  | 255.0.0.0 |  UH   |   lo     |   1
 UID21 |  V.0        | V.R21      | netmask21 |  UG   |   1      |   1
 UID22 | *X.0        | X.R22      | netmask22 |  UG   |   2      |   1
 UID23 |  W.0        | W.R23      | netmask23 |  UG   |   3      |   1
 UID11 | *X.0        | Z.R13      | netmask11 |  UG   |   1      |   2
 UID12 |  Y.0        | Z.R13      | netmask12 |  UG   |   1      |   2
 UID13 |  Z.0        | Z.R13      | netmask13 |  UG   |   1      |   2


Now instead of comparing subnet numbers and metrics, the router compares
subnet number, UID and metric. If subnet number and UID match, the entry
with the lowest metric is retained. If the UID does not match, then both
entries are retained. Because each segment route is now uniquely identi-
fied by a UID, R2 easily detects subnet collisions. In the table above,
the subnet collisions are marked with "*". R2 detects that R1 has
assigned subnet "X" to its interface identified by UID11 and it has
assigned the same subnet "X" to its interface identified by UID21. In
case of subnet collisions both of the routers have to change their sub-
net mappings (see Appendix A for a discussion on why ).

4. Subnet Conflict Notification and Resolution

  Once a subnet conflict is detected by a router, it must be resolved.
The conflict resolution involves notifiying the routers that made the
conflicting subnet assignments so that they can assign new subnet num-
bers that are unique within the zeroconf network.

  The first step in resolution is the notification of the conflict. In
our example above, once router R2 detects the conflict on subnet X, it
will immediately assign another subnet number to its interface 2. The
new subnet will be something other than X, Y, Z, V, W so that it is
unique within R2's context. Assume that the new subnet mapping is
(UID22, T). This resolves one end of the conflict. But R2 still needs to
notify R1 of the conflict on UID11 so that R1 can also change the subnet



Akinlar, Braun, Mukherjee       Informational           [Page 6]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


mapping (UID11, X). In order to solve the problem of conflict notifica-
tion, we propose that each RTE within a RIP packet is marked with a flag
indicating its current status. A RTE could be in one of the 2 states:


     NORMAL_ENTRY: Valid RTE.
     CHANGE_ENTRY: There was a conflict somewhere in the network. This RTE
                   must be changed by the owner of the interface.


  When R2 detects the collision on UID11, it marks this RTE as
CHANGE_ENTRY. We now extend each RTE with a 1 byte status field indicat-
ing its current status. When R2 sends out a RIP packet, all of RTEs are
included within the packet with their status marked appropriately. The
RTEs marked NORMAL_ENTRY are intended to be new route advertisements and
those marked as CHANGE_ENTRY are intended to be conflict notifications.
In our example above, the RIP message from R2 to R1 will then contain:


 UID   | IP | netmask   | next-hop | metric | status
-------+----+-----------+----------+--------+--------------
 UID21 | T  | netmask21 | T.R21    |    1   | NORMAL_ENTRY
 UID22 | V  | netmask22 | T.R21    |    1   | NORMAL_ENTRY
 UID23 | W  | netmask23 | T.R21    |    1   | NORMAL_ENTRY
 UID11 | X  | netmask11 | T.R21    |    2   | CHANGE_ENTRY
 UID12 | Y  | netmask12 | T.R21    |    2   | NORMAL_ENTRY
 UID13 | Z  | netmask13 | T.R21    |    2   | NORMAL_ENTRY


As the above table shows, the route identified by UID11 is marked as
CHANGE_ENTRY. When R1 gets this message, it learns that somewhere in the
network there was a subnet conflict with its subnet assignment (UID11,
X) and it changes it. Also note that, although we show that the RIP
packet from R2 to R1 includes RTEs (UID12, Y) and (UID13, Z), we don't
have to send these two routes back to R1 because we just learned them
from R1. In fact, in RIP-2, R2 won't include these two RTEs in the
packet that it sends to R1. This is called split horizon. That is, a
router R2 does not send the routes that it learns from some other router
R1 back to R1. This makes the convergence faster when a router fails.
The same technique SHOULD be used in ZRIP. But, the subnet (UID11, X)
MUST be sent back to R1 because this is a subnet conflict notification
rather than a route advertisement. So, the split horizon technique
SHOULD be used only for NORMAL RTEs. Any time the status of a RTE
changes to CHANGE_ENTRY, it MUST be reported to the originator (the
router from which the route was learned).

5. The need for a sequence number for each Routing Table Entry.

  As a zeroconf network becomes more complex, it is possible that a
router can get conflicting values for the same routing table entry(RTE)
in the network. In order to make sure that everyone uses the latest copy
of a RTE, we propose that each RTE is augmented with a 2 byte sequence
number assigned and changed by the owner of the RTE. This is very simi-
lar to the way sequence numbers for links are used in OSPF [3]. In OSPF,
each link has a sequence number which is incremented by the router that
advertises it. This makes sure that other routers in the network use the
latest copy of the link state. In ZRIP, each router MUST maintain a
sequence number for each of its subnet assignments. This sequence number
MUST be incremented when a router changes the subnet mapping due to a
subnet conflict. Each subnet mapping (RTE) is now identified by a



Akinlar, Braun, Mukherjee       Informational           [Page 7]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


2-tuple: (UID, seqno). As a RTE is propagated through the network, each
router will eventually get the latest copy of a (UID, seqno, subnet)
triplet and the network will stabilize. Without the use of this sequence
number, a router might get confused as to which copy of a RTE it should
use. An example on how this might occur is described in Appendix B.

6. Backward Compatibility to RIP-2

  We propose that Zeroconf Routers run ZRIP protocol as defined in this
draft. ZRIP uses the same multicast address as RIP but uses a different
port number. In order for hosts running RIP daemon to learn all the
routes in the network, a ZRIP daemon running at a zeroconf router multi-
casts a RIP message following a ZRIP message on the segment. This way,
the hosts do not have to implement ZRIP in order to learn the routes.
Hosts can continue using legacy RIP implementations and learn all the
routes in the network. Only zeroconf routers MUST implement ZRIP proto-
col.

7. Protocol Specification and Message Format

  ZRIP is a dynamic routing protocol used in zeroconf networks that not
only solves the problem of dynamic route advertisement but also the sub-
net conflict detection, notification and resolution. ZRIP is based on
RIP-2. RIP-2 is used in administered networks to solve the dynamic route
advertisement problem. As there will be no subnet conflicts in an admin-
istered network, subnet collision detection and resolution is not an
issue. In previous sections, we described how RIP routing table entries
(RTEs) can be changed so that RIP can be used to solve both of the prob-
lems. This section describes the ZRIP message format and how routers
process ZRIP packets.

7.1. Basic Router Operation

  When a router boots up, it determines the hardware type of each of its
interfaces, and assigns a unique interface identifier(UID) to each of
them generating a random identifier if necessary (in the case when the
interface does not have a hardware address such as PPP links). Then the
router assigns random subnet numbers to each of its interfaces and
assigns a sequence number of 1. Thus each interface of the router is
identified by a triplet (UID, subnet, seqno). The router then configures
the hosts on segments connected to each of its interfaces. This can be
done by a mini-DHCP running at the router and serving each interface as
described in [5]. The router then sends out ZRIP requests on each inter-
face. The ZRIP request will trigger neighboring routers to send ZRIP
responses. The router will then process each of these ZRIP packets as
described in section 7.3. When everything settles, the router sends
periodic ZRIP messages on each of its interfaces advertising the routes
that it knows about. While all of the routing table could be sent, opti-
mizations like split horizon of RIP SHOULD be used.

7.2. ZRIP Message Format

  ZRIP uses a message format similar to RIP except that ZRIP augments a
RTE with additional fields used for subnet conflict detection and noti-
fication.

  The ZRIP packet format is:






Akinlar, Braun, Mukherjee       Informational           [Page 8]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  command (1)  |  version (1)  |       must be zero (2)        |
   +---------------+---------------+-------------------------------+
   |                                                               |
   ~                        ZRIP Entry (32)                        ~
   |                                                               |
   +---------------+---------------+---------------+---------------+


  The format for the 32-octet route entry (RTE) for ZRIP is:


    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Address Family Identifier (2) |        Route Tag (2)          |
   +-------------------------------+---------------+---------------+
   |      sequence number (2)      |   status (1)  | intf. type (1)|
   +-------------------------------+---------------+---------------+
   |                  Interface Identifier (8)                     |
   |                                                               |
   +---------------------------------------------------------------+
   |                         IP Address (4)                        |
   +---------------------------------------------------------------+
   |                         Subnet Mask (4)                       |
   +---------------------------------------------------------------+
   |                         Next Hop (4)                          |
   +---------------------------------------------------------------+
   |                         Metric (4)                            |
   +---------------------------------------------------------------+


   Field sizes are given in octets.  Unless otherwise specified, fields
contain binary integers, in network byte order, with the most- signifi-
cant octet transmitted first (big-endian).  Each tick mark represents
one bit.

  Comparison of a ZRIP RTE to a RIP RTE shows ZRIP adds 12 more bytes to
the entry. These are bytes 4-15 inclusive. The Address Family Identifier
and Route Tag fields have the same meaning as in RIP. The Address Family
Identifier is always AF_INET as in RIP-1 and means that it is an Inter-
net address. The intended use of the Route Tag in RIP-2 is to provide a
method of separating "internal" RIP routes (routes for networks within
the RIP routing domain) from "external" RIP routes, which may have been
imported from an EGP or another IGP. Because ZRIP is intended to be used
as an IGP in a zeroconf network, this field always indicates that the
route is an IGP.

  The "sequence number" field is the sequence number of the RTE as
assigned and maintained by the "owner" of the subnet. The "status" field
is the current status of the RTE which is either NORMAL_ENTRY or
CHANGE_ENTRY. The next 9 bytes of the RTE, "interface type" augmented
with the "interface identifier" makes up the unique interface id, UID
for the route. UID identifies the interface of the router that uses this
RTE. The rest of the fields in a RTE have the same meaning as in RIP.
The "IP Address" field is the IP address of the subnet number for the
segment connected to the interface of the router, "netmask" is the net-
work mask assigned by the router and "Next Hop" is the IP address of the



Akinlar, Braun, Mukherjee       Informational           [Page 9]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


router where the packets must be sent to reach this route. "metric" is
the distance of the segment(route) from the router advertising the RTE
in terms of the number of hops. 1 means that the segment is directly
connected to the router.

  Each RTE in a ZRIP message is 32 bytes. Because an individual ZRIP
packet can be at most 512 bytes, a ZRIP message can contain at most 15
RTEs. If the routing table of a router contains more routes, additional
packets are sent.

8.3. Processing of ZRIP Messages

  Each router keeps a ZRIP table that contains all the routes in the
zeroconf network. For example, for router R1 in Figure 1, the initial
ZRIP table will be as follows:


seqno | status | UID   | Dest | Gateway | Netmask| Flags |Intf | Metric
------+--------+-------+------+---------+--------+-------+-----+-------
  1   | NORMAL | UID11 | X.0  | X.R11   | mask11 |  UG   |  1  |   1
  1   | NORMAL | UID12 | Y.0  | Y.R12   | mask12 |  UG   |  2  |   1
  1   | NORMAL | UID13 | Z.0  | Z.R13   | mask13 |  UG   |  3  |   1


In this section we present an algorithm used by a zeroconf router to
process a ZRIP message received from a neighboring router. Figures 2, 3
and 4 show the flowchart of the algorithm. Each ZRIP packet contains a
number of RTEs. Each RTE is processed in a sequence. If the RTE contains
``semantically incorrect'' data, the RTE or the whole ZRIP packet is
thrown away.

The algorithm can be tought of as consisting of 3 parts.

Part 1: This is where a router learns a new route. Checking whether a
route is new or not is done by simply checking if the UID of the cur-
rently processed RTE exists in the ZRIP table. The flowchart in Figure 2
handles this case and shows how this new RTE is processed.

Parts 2 & 3: If the currently processed route (RTE.UID) is already
known, then we go to the flowchart shown in Figure 3. Here we first com-
pare the sequence number of the RTE within the packet with the sequence
number of the entry corresponding to this RTE in the ZRIP table
(entry.UID==RTE.UID). The flowchart in Figure 3 handles the cases where
the sequence number of the RTE within the packet is "equal to OR smaller
than" what we already have in the ZRIP table. If the sequence number of
the RTE within the packet is bigger, then the RTE is processed with the
algorithm shown in Figure 4.

In the algorithms, the function "New()" randomly generates a new unique
subnet number. This function could be implemented in different ways. One
simple way to implement it would be to check the current valid mappings
and generate one that is not being used. Another possible way for imple-
mentation is to keep a history of subnet mappings and try to generate
new mappings that were not used in the recent past.

Each numbered rectangular box in the figures corresponds to a possible
state. The upper half of the box describes the condition to reach the
box and the lower half describes the action(s) taken when that state is
reached. Below, with the aid of simple examples, we describe how the
router can arrive at each of the possible states. For each case a



Akinlar, Braun, Mukherjee       Informational          [Page 10]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


zeroconf network transition is exemplified.


             +-----+
             |START|
             +--+--+
                |
+-------------->|<---------------(A)
|               |
|   +-----------V------------+
|   |Get the next ZRIP packet|
|   +-----------+------------+
|               |<---------------------------------------------------------+<--(B)
|       ________V________                                                  |
|  No  /                 \                                                 |
+<----/      More RTE     \                                                |
      \    in this pkt?   /                                                |
       \_________________/                                                 |
                V                                                          |
                | Yes                                                      |
  +-------------V-----------------+                                        |
  |RTE=Get next RTE of this packet|                                        |
  +-------------+-----------------+                                        |
                |                                                          |
        ________V_________                                                 |
       /                  \     Yes                                        |
      /  RTE.UID present   \----------->(C)                                |
      \  in my ZRIP Table? /                                               |
       \__________________/                                                |
                V                                                          |
                | No                +----------------------------------+   |
        ________V_________       (1)| Learned a new RTE                |   |
       /                  \   No    | with status=CHANGE               |   |
      /     RTE.status     \------->+----------------------------------+-->+
      \     is NORMAL?     /        | * Insert RTE in ZRIP Table       |   |
       \__________________/         |   with status=CHANGE             |   |
                V                   +----------------------------------+   |
                |                                                          |
                | Yes               +----------------------------------+   |
        ________V_________       (2)| Learned a new RTE that does NOT  |   |
       /                  \   No    | conflict with any other          |   |
      /  RTE.Subnet exists \------->+----------------------------------+-->+
      \  in my ZRIP Table? /        | * Insert RTE in ZRIP Table       |   |
       \__________________/         |   with status=NORMAL             |   |
                V                   | * Compute metric                 |   |
                | Yes               +----------------------------------+   |
   (Continued on the next page)                              (Continued on the next page1)
















Akinlar, Braun, Mukherjee       Informational          [Page 11]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


   (Continued from the previous page)                   (Continued from the previous page1)
                |                                                          |
  +-------------V-----------------+                                        |
  | Cnflct=Entry in my ZRIP Table |                                        |
  |     conflicting with RTE      |                                        |
  +-------------+-----------------+                                        |
                |                   +----------------------------------+   |
        ________V_________       (3)| Learned a new RTE that conflicts |   |
       /                  \   No    | with another known RTE           |   |
      /   Am I the owner   \------->+----------------------------------+-->+
      \     of RTE.UID     /        | * Insert RTE in ZRIP Table       |   |
       \__________________/         |   with status=CHANGE             |   |
                V                   | * Cnflct.Status=CHANGE           |   |
                |                   +----------------------------------+   |
                |                                                          |
                |                   +----------------------------------+   |
                |                (4)| Learned new RTE that conflicts   |   |
                |   Yes             | with one of mine.                |   |
                +------------------>+----------------------------------+-->+
                                    | * Insert RTE in ZRIP Table       |
                                    |   with Status=CHANGE             |
                                    | * Cnflct.Subnet=New()            |
                                    | * Increment Cnflct.Seq_number    |
                                    +----------------------------------+

 Figure 2: Algorithm used by a ZRIP router to process ZRIP packets. The number
           beside each box is used in the text for reference.




































Akinlar, Braun, Mukherjee       Informational          [Page 12]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


                (C)
                 |
    +------------V--------------+
    |entry = Entry in ZRIP Table|
    |      matching RTE.UID     |
    +------------+--------------+
                 |
         ________V________      (10)+------------------------+
      > /                 \ <       | Received known RTE with|
(D)<---/  RTE.Seq_number:: \------->| smaller Seq_number     |
       \  entry.Seq_number /        +------------------------+------------>+
        \_________________/         | * Invalidate RTE       |             |
                 V                  +------------------------+             |
                 | ==                                                      |
         ________V_________                                                |
        /                  \  No                                           |
       /    RTE.Status is   \---+                                          |
       \        NORMAL?     /   |                                          |
        \__________________/    |                                          |
                V               |                                          |
                | Yes           |                                          |
                |       ________V_________ (11)+-----------------------+   |
                |      /                  \    | Received refresh with |   |
                |     / Am I the owner of  \-->| Status=CHANGE for a   |   |
                |     \      RTE.UID?      /No | known RTE.            |   |
                |      \__________________/    +-----------------------+-->|
                |              V               | * entry.status=CHANGE |   |
                |              |Yes            +-----------------------+   |
                |              |                                           |
                |              |    +----------------------------------+   |
                |              |(12)| Someone detected conflict        |   |
                |              |    | with my RTE                      |   |
                |              +--->+----------------------------------+-->+
                |                   | * entry.Subnet = New()           |   |
                |                   | * Increment entry.Seq_number     |   |
                |                   +----------------------------------+   |
                |                                                          |
                |                   +----------------------------------+   |
        ________V_________      (13)| Received a valid refresh         |   |
       /                  \  ==     | for a known RTE                  |   V
      /     RTE.Subnet::   \------->+----------------------------------+-->+-->(B)
      \     entry.Subnet   /        | * Update entry.time_of_expr.(RIP)|
       \__________________/         | * Update entry.metric (RIP)      |
                V                   +----------------------------------+
                | !=
                |                   +----------------------------------+
                |               (14)| Received known RTE with same     |
                |   Yes             | Seq_number but different Subnet  |
                +------------------>+----------------------------------+------->(A)
                                    | * Invalidate ZRIP Packet         |
                                    +----------------------------------+
 Figure 3: Algorithm used by a ZRIP router to process ZRIP packets. The number
           beside each box is used in the text for reference.










Akinlar, Braun, Mukherjee       Informational          [Page 13]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


               (D)
                |
        ________V________        (5)+----------------------------------+
       /                 \  Yes     | Received my RTE with a bigger    |
      / Am I the owner of \-------->| bigger Sequence number           |
      \      RTE.UID?     /         +----------------------------------+----->(A)
       \_________________/          | * Invalidate the ZRIP packet.    |
                V                   +----------------------------------+
                | No
                |
                |                   +----------------------------------+
        ________V_________       (6)| Received a new mapping of a      |
       /                  \   No    | known RTE with Status=CHANGE     |
      /     RTE.status     \------->+----------------------------------+-->+
      \     is NORMAL?     /        | * entry.Status=CHANGE            |   |
       \__________________/         +----------------------------------+   |
                V                                                          |
                |                                                          |
                | Yes               +----------------------------------+   |
        ________V_________       (7)| Received a new mapping of a      |   |
       /                  \   No    | known RTE that does not          |   |
      /  RTE.Subnet exists \------->| conflict with any other          |-->+
      \  in my ZRIP Table? /        +----------------------------------+   |
       \__________________/         | * entry.Status=NORMAL            |   |
                V                   +----------------------------------+   |
                | Yes                                                      |
  +-------------V-----------------+                                        |
  | Cnflct=Entry in my ZRIP Table |                                        |
  |     conflicting with RTE      |                                        |
  +-------------+-----------------+                                        |
                |                   +----------------------------------+   |
        ________V_________       (8)| Received a new mapping of a      |   |
       /                  \   No    | known RTE that conflicts with    |   |
      /   Am I the owner   \------->| another known RTE                |-->+
      \    of Cnflct.UID   /        +----------------------------------+   |
       \__________________/         | * Cnflct.Status=CHANGE           |   |
                V                   +----------------------------------+   |
                |
                |                   +----------------------------------+   |
                |                (9)| Received a new mapping of a      |   |
                |   Yes             | known RTE that conflicts with    |   |
                +------------------>| one of mine                      |   |
                                    +----------------------------------+-->+--->(B)
                                    | * entry.Status=CHANGE            |
                                    | * Cnflct.Subnet=New()            |
                                    | * Increment Cnflct.Seq_number    |
                                    +----------------------------------+

 Figure 4: Algorithm used by a ZRIP router to process ZRIP packets. The number
           beside each box is used in the text for reference.




Below we give examples on how each of the cases marked on the flowchard
could occur. Below (X, Y, Z) corresponds to an RTE where X represents
the UID, Y is the subnet number and Z is the sequence number managed by
the "owner" of the RTE.





Akinlar, Braun, Mukherjee       Informational          [Page 14]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


+=======================================================================+
  CASE (1): Learned a new RTE with Status = CHANGE:
+-----------------------------------------------------------------------+
   [R1]-------[R2]---X---[R3]

  R1 and R2 are stable. R3 is connected to R2. R2 learns about (I31,
  a11, N). It then marks (I11, a11, N) as CHANGE_ENTRY. It also marks
  (I31, a11, N) as CHANGE_ENTRY. Then R2 sends ZRIP on all of its
  interfaces. Now R1 learns about (I31, a11, N) with status
  CHANGE_ENTRY. R1 simply inserts (I31, a11, N) into its ZRIP table but
  does not create a routing entry for this interface yet since the
  route is still being defined.



+=======================================================================+
  CASE (2): Learned a new RTE that does not conflict  with any other:
+-----------------------------------------------------------------------+
  [R1]--X--[R2]

  R1 and R2 are isolated and stable. R1 and R2 are then connected. R1
  learns about (I21, a21, N) which does not collide with any of its
  mappings that it knows. R1 simply inserts (I21, a21, N) into its ZRIP
  table and updates its routing table to include the new route.




+=======================================================================+
  CASE (3): Learned a new RTE that conflicts with another known RTE:
+-----------------------------------------------------------------------+
  [R1]-------[R2]---X---[R3]

  R1 and R2 are stable. R2 knows about (I11, a11, N). R3 is connected to
  R2. R2 learns about (I31, a11, N). It then marks (I11, a11, N) as
  CHANGE_ENTRY. It also marks (I31, a11, N) as CHANGE_ENTRY.



+=======================================================================+
  CASE (4): Learned a new RTE that conflicts with one of mine:
+-----------------------------------------------------------------------+
  [R1]--X--[R2]

  R1 and R2 are stand-alone. R1 and R2 are connected. R1 initially has
  (I11, a11, N). It know learns (I21, a11, N). R1 then changes (I11,
  a11, N) to (I11, new, N+1) and marks (I21, a11, N) as CHANGE_ENTRY.



+=======================================================================+
  CASE (5): Received my RTE with a bigger sequence number:
+-----------------------------------------------------------------------+
  This case won't ever occur if someone is not injecting invalid ZRIP
  packets into the network. A router which owns an interface can never
  get a ZRIP packet which tells it that its interface RTE has a bigger
  sequence number than what it holds.






Akinlar, Braun, Mukherjee       Informational          [Page 15]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


+=======================================================================+
  CASE (6): Received a new mapping of a known RTE with status = CHANGE:
+-----------------------------------------------------------------------+
  [R1]---[R2]---X---[R4]
   |   /
   |  /
   | /
   |/
  [R3]---X---[R5]

  R1, R2 and R3 are stable. R1 knows about (I21, a21, N). First R4 is
  connected. R2 gets (I41, a21, N) from R4. Changes (I21, a21, N) to
  (I21, new, N+1). Sends ZRIP on all interfaces. R1 does not get this ZRIP
  message and still has (I21, a21, N). R3 gets it and updates (I21, a21,
  N) to (I21, new, N+1). Right at this point R5 is connected to R3. R3
  gets (I51, new, N) from R5. So, it invalidates (I21, new, N+1). That is
  R3 changes the status of (I21, new, N+1) from NORMAL_ENTRY to
  CHANGE_ENTRY and sends ZRIP on all interfaces. Now R1 gets (I21, new,
  N+1) with status CHANGE_ENTRY from R3. R1 then deletes its old route to
  I21 and then sends out ZRIP message on all interfaces.



+=======================================================================+
  CASE (7): Received a new mapping of a known  RTE that does NOT
            conflict with any other:
+-----------------------------------------------------------------------+
  [R3]------X-----[R1]----------[R2]

  R1 and R2 are stable. R2 knows about (I11, a11, N). R3 is attached. R1
  learns (I31, a11, N). R1 changes (I11, a11, N) to (I11, new, N+1) and
  sends ZRIP on all interfaces. R2 learns about (I11, new, N+1) and
  updates (I11, a11, N) to (I11, new, N+1) and starts using it. Notice
  that "new" MUST not clash with whatever R2 knows. Otherwise this is
  one of the cases below. (CASE 8 or 9).



+=======================================================================+
  CASE (8): Received a new mapping of a known RTE that conflicts
            with another known RTE:
+-----------------------------------------------------------------------+
  [R3]------X-----[R1]----------[R2]-----X-----[R4]

  This is very similar to CASE 9 below. R1 and R2 are stable. R1 knows
  about (I21, a21, N). R3 is attached to R1. R1 learns about (I31, new,
  N). R1 sends ZRIP on all interfaces but this message never makes it to
  R2. So, R2 does not know about (I31, new, N). Now R4 is attached to
  R2. R2 learns about (I41, a22, N) but it has (I22, a22, N). So, it
  changes its mapping to (I22, new, N+1). Notice that R2 does not know
  that R1 has (I31, new, N), so it assigns "new" as its subnet mapping
  to I22. Then R2 sends ZRIP on all interfaces. R1 gets (I22, new, N+1)
  which collides with (I31, new, N). Both of these need to change again.










Akinlar, Braun, Mukherjee       Informational          [Page 16]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


+=======================================================================+
  CASE (9): Received a new mapping of a known RTE that conflicts
            with one of mine:
+-----------------------------------------------------------------------+
  [R3]------X-----[R1]----------[R2]-----X-----[R4]

  R1 and R2 are stable. R1 knows about (I21, a21, N). R3 is attached to
  R1. R1 learns about (I31, a11, N) but it has (I11, a11, N). Changes
  (I11, a11, N) to (I11, new, N+1). R1 sends ZRIP on all interfaces but
  this message never makes it to R2. So, R2 still knows about (I11, a11,
  N). Now R4 is attached to R2. R2 learns about (I41, a22, N) but it
  has (I22, a22, N). So, it changes its mapping to (I22, new, N+1). Notice
  that R2 does not know that R1 now uses (I11, new, N+1), so it assigns
  "new" as its subnet mapping to I22. Then R2 sends ZRIP on all
  interfaces. R1 gets (I22, new, N+1) which collides with (I11, new,
  N+1). They need to change again.



+=======================================================================+
  CASE (10): Received known RTE with smaller sequence number:
+-----------------------------------------------------------------------+
  [R1]------[R2]---X---[R4]
   |
   |
   |
  [R3]

R1, R2 and R3 are stable. R3 has (I21, a21, N). R4 is connected to
R2. R2 learns about (I41, a21, N), changes its (I21, a21, N) to (I21,
new, N+1) and sends ZRIP on all interfaces. R1 gets this ZRIP and
updates it table to include (I21, new, N+1). Right at this time a
periodic update from R3 arrives specifying (I21, a21, N). R1 ignores
this message as the sequence number is smaller and refers to old the
mapping.



+=======================================================================+
  CASE (11): Received refresh with Status = CHANGE for a known RTE:
+-----------------------------------------------------------------------+
  [R1]--------[R2]----X-----[R3]


R1 and R2 are stable. R2 knows about (I11, a11, N). R3 is
attached. Assume R3 gets the first ZRIP from R2, and (I11, a11, N)
clashes with (I31, a11, N). R3 changes (I31, a11, N) to (I31, new, N+1)
and marks the status of (I11, a11, N) as CHANGE_ENTRY. Then R3 sends
ZRIP on all interfaces. R2 will get (I11, a11, N) with status
CHANGE_ENTRY and deletes its route to I11 and forward the entry to R1.













Akinlar, Braun, Mukherjee       Informational          [Page 17]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


+=======================================================================+
  CASE (12): Someone detected conflict with my RTE:
+-----------------------------------------------------------------------+
  [R1]------[R2]
    |
    X
    |
  [R3]

R1 and R2 are stable. R1 knows about (I21, a21, 1 ). R3 is
connected. R1 gets a ZRIP from R3 and learns about (I31, a21, N). Then
it changes the status of (I21, a21, N) from NORMAL_ENTRY to
CHANGE_ENTRY and sends ZRIP on all interfaces. R2 gets this ZRIP from
R1. This message says (I21, a21, N) with status CHANGE_ENTRY. R2 then
randomly chooses a new subnet for I21.



+=======================================================================+
  CASE (13): Received valid refresh for a known RTE:
+-----------------------------------------------------------------------+
  [R1]---[R2]
    |   /
    X  /
    | /
    |/
  [R3]


R1, R2 and R3 are stable. R1 knows about (I31, a31, N) with a metric
of 3. Now we connect R3 to R1. R1 gets a ZRIP from R3 specifying (I31,
a31, N) with a metric of 1. So, it updates its ZRIP table and the
routing table with a metric of 2 to RTE (I31, a31, N).



+=======================================================================+
  CASE (14): Received known RTE with same sequence number but
             different subnet:
+-----------------------------------------------------------------------+
  Under normal circumstances this will never occur.


10. References

  [1] C. Hedrick, Routing Information Protocol, RFC 1058, June 1988.

  [2] G. Malkin, RIP Version 2, RFC 2453, November 1998.

  [3] J. Moy, OSPF Version 2, RFC 2328, April 1998.

  [4] M. Hatting, Zeroconf Requirements,
      draft-ietf-zeroconf-reqts-03.txt, March 2000. A work in progress.

  [5] Bernard Aboba, Auto-Addressing in Multi-segment Networks,
      draft-aboba-zeroconf-multi-00.txt, Oct 1999. A work in progress.

  [6] Bradner, S., "Key words for use in RFCs to Indicate Requirement
      Levels", BCP 14, RFC 2119, March 1997.




Akinlar, Braun, Mukherjee       Informational          [Page 18]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


Appendix A: Why both routers have to change subnet assignments in
            subnet conflicts.

  In the text, we said that in the case of a subnet conflict, both of
the routers involved in the conflict must change their subnet assign-
ments. Changing one of the subnet assignment and leaving the other one
unchanged may cause problems. In particular, the packets on the existing
connections may go to the wrong hosts.

  The following is an example zeroconf network configuration which shows
why both routers involved in a subnet conflict must change the old sub-
net mappings.


               [a1.H1]--(a1.0)--[R1]--(a2.0)--[a2.H2]    (1)
                                 |
                                 |
                                 X
                                 |
                                 |
               [a3.H3]--(a3.0)--[R2]--(a2.0)--[a2.H2]    (2)

     [an.Hn]--- Host with IP address an.Hn
     (an.0) --- Subnet number of the segment assigned by the router.


Initially each router is isolated. Router R1 has assigned subnets a1 and
a2 to its interfaces as shown. There is a host, a1.H1, connected to one
of its subnets and another one a2.H2 connected to another subnet as
shown. Assume that a1.H1 is streaming video to a2.H2 using UDP packets.
Router R2 is also isolated. It has assigned a3 and a2 to its subnets.
Similar to R1, there is a single host a3.H3 on the a3 segment and a host
on a2.H2 on the a2 segment. Further assume that a3.H3 is streaming video
to a2.H2.

  While both of these multi-segment single router zeroconf networks were
stable, we connect R1 and R2 as shown with a "X". Assume that R1 gets a
ZRIP packet from R2 and detects that R2 is also using the subnet number
a2. R1 changes its subnet mapping from a2 to a4 which is unique on the
new zeroconf network. But R1 does not notify R2 of the conflict assuming
that subnet a2 of R2 is valid. R1 then updates its routing table with
new subnets a3 and a2 and sends any packets destined to these subnets to
router R2. Immediately after R1 updates its routing table, UDP packets
from host a1.H1 will now go to a2.H2 connected to router R2. The host
a2.H2 connected to R2 will now get packets from a3.H3 in addition to
a1.H1 which may cause serious problems.In order to prevent these unde-
sirable situations, we require that both of the routers involved in a
subnet conflict change their subnet mappings. So, using ZRIP, first R1
will change its subnet mapping and then it will notify R2 of the con-
flict. R2 will change its mapping and will send the new mapping to R1
and the network will stabilize. During the transition R1 will stop using
the route for a2 since it is in "changing" state. This will break exist-
ing connections which is better than getting invalid packets.

Appendix B: The need for sequence number for each RTE in a ZRIP
            message.

  In the text, we said that each RTE advertised by a router has to be
augmented with a sequence number assigned and managed by the owner of
the RTE. The owner of a RTE is that router which creates the RTE by



Akinlar, Braun, Mukherjee       Informational          [Page 19]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


assigning the route(the subnet) to one of its interfaces. Without
sequence numbers, an intermediate router in the network can get a stale
(old) copy of a subnet mapping and will be confused as to which one to
use.


                                   segment subnet: a41
                                   |
                                   V
[R1]-------[R2]-----[R3]-----[R4]--------X----[R6]
 |                            |
 |                            |
[R5]--------------------------+


Consider the above network. Initially R1, R2, R3, R4 and R5 are con-
nected and are stable. R5 knows that R4 has a mapping (R41, a41) on its
interface 1. Notice from the figure that R1 sends packets to R5 in order
to reach a41 because a41 is 3 hops away through R5 but 4 hops away
through router R2. Now, assume that R6 is connected to R4 and that R6
has the mapping (R61, a41). When R4 gets a ZRIP message from R6, it will
detect the subnet conflict and change the subnet mapping (R41, a41) to
(R41, a41-new). R4 will then send a ZRIP packet to both R3 and R5 noti-
fying them of the changes. Assume that this ZRIP message to R5 is lost.
R3 gets the ZRIP packet, updates its routing table forwards it on. But
R5 still has the old mapping. When R1 gets a ZRIP from R2 with the new
mapping (R41, a41-new) it has to make a decision as to whether it is
going to accept this new route or not. Notice that the new subnet
assignment is still 4 hops away through R2 but has a different subnet
assignment. Without additional information, R1 cannot make a decision.
Worse yet, if R1 accepts the new subnet assignment (R41, a41-new) and
starts sending the packet to R2 to reach the subnet a41-new, when R5
sends its periodic ZRIP message to R1 it will contain the old mapping
(R41, a41) with a smaller hop count (metric). R1 has no way of identify-
ing whether (R41, a41) is the old copy or it is yet another new subnet
assignment.

  Augmenting each RTE with a sequence number assigned and maintained by
the owner of the RTE solves the problem. Initially (R41, a41) has a
sequence number of 1. When R4 changes the subnet assignment to (R41,
a41-new) it increases the sequence number to 2 and then notifies the
neighbors. When R1 gets the ZRIP from R2 containing the new mapping
(R41, a41-new), it can easily determine that (R41, a41) is the old map-
ping as its sequence number is 1. So, R1 deletes the old subnet mapping
and starts using the new mapping which has a sequence number of 2. Any
stale copy that arrives from R5 to R1 will have sequence number of 1 for
this RTE so R1 will not use it. When R5 eventually learns about the new
mapping and notifies R1 with a smaller hop count for the subnet, R1 will
send the packets for (R41, a41-new) to R5 instead of R2.

6.  Authors' Addresses


Cuneyt Akinlar
Panasonic Research
2 Research Way
Princeton NJ 08540
Phone: +1 (609) 734-7356
EMail: akinlar@research.panasonic.com




Akinlar, Braun, Mukherjee       Informational          [Page 20]


INTERNET-DRAFT ZRIP: Zero-Conf Routing Information Protocol   March 2000


David Braun
Panasonic Research
2 Research Way
Princeton NJ 08540
Phone: +1 (609) 734-7322
EMail: braun@research.panasonic.com



Sarit Mukherjee
Panasonic Research
2 Research Way
Princeton NJ 08540
Phone: +1 (609) 734-7347
EMail: sarit@research.panasonic.com
















































Akinlar, Braun, Mukherjee       Informational          [Page 21]


Html markup produced by rfcmarkup 1.123, available from https://tools.ietf.org/tools/rfcmarkup/