NETWORK Working Group Cuneyt Akinlar INTERNET-DRAFT David Braun Category: Informational Sarit Mukherjee 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 , 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]