Internet Draft G. Malkin/Xylogics Updates RFC 1058 and RFC 1288 C. Huitema/INRIA June 1993 SIP-RIP Abstract This document specifies a routing protocol, based on the Routing Information Protocol (RIP), as defined in [1,2], for the Simple Internet Protocol (SIP), as defined in [3]. A companion document will define the SNMP MIB objects for SIP-RIP (TBD). Status of this Memo This document is an Internet Draft. 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. Internet Drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a "working draft" or "work in progress." Please check the I-D abstract listing contained in each Internet Draft directory to learn the current status of this or any other Internet Draft. It is intended that this document will be submitted to the IESG for consideration as a standards document. Distribution of this document is unlimited. Acknowledgements Thanks to those whose contributions to RIP-2 have been propogated into SIP-RIP. Special to Yakov Rekhter of IBM Research for suggesting the "loop control" improvement, and to J.J. Garcia-Luna- Aceves of UCSC for reviewing the text. Malkin, Huitema Expires: 29Dec93 [Page 1] Internet Draft SIP-RIP June 1993 Table of Contents 1. Justification . . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3. Protocol Design . . . . . . . . . . . . . . . . . . . . . . . . 3 3.1 Packet Format . . . . . . . . . . . . . . . . . . . . . . . . 3 3.2 Prefered Route Determination . . . . . . . . . . . . . . . . 5 3.3 Loop Control . . . . . . . . . . . . . . . . . . . . . . . . 6 3.4 Authentication . . . . . . . . . . . . . . . . . . . . . . . 7 4. Security Considerations . . . . . . . . . . . . . . . . . . . . 8 Appendicies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11 1. Justification SIP is the Simple Internet Protocol. It stands to reason that the simplest, and best understood, routing protocol should be modified to support it. At the same time, SIP-RIP will make use of many of the RIP-2 extensions. 2. Overview SIP-RIP is not a new version of IP RIP. It is a new protocol which will be run over its own UDP port. Despite that, the changes are only to the format of the routing entries within a routing packet, the basic manipulation of routes and the routing table remains unchanged. SIP-RIP makes use of most of the RIP-2 enhancements; only the route tag field has been omitted. The subnet mask has been replaced by a single byte which specifies the number of bits in the subnet mask, which therefore disallows the use of discontiguous subnet masks. The metric has been reduced to a single byte, but the maximum number of hops permitted is now 32 instead of 16. A new field, throughput class, has been added to characterize the links which are used by a route. The most important change, however, is the increase in the size of the address fields from 32 bits to 64 bits. SIP-RIP includes a loop control algorithm [5,6] which is not part of RIP-2. This algorithm makes SIP-RIP loop-free as it converges after a topology change, but it requires that each routing entry carry a First Hop field. The new field brings the size of an entry from 24 to 32 bytes. Malkin, Huitema Expires: 29Dec93 [Page 2] Internet Draft SIP-RIP June 1993 3. Protocol Design SIP-RIP will be run on UDP port ???. Periodic SIP-RIP responses will be sent to the SIP "all routers on this link" multicast address, 7F02:0000:0000:0002. 3.1 Packet Format IP RIP packets are limited to 25 routing entries which limits the maximum packet size to 512 bytes (including UDP header). This can cause unnecessary overhead on LANs with larger MTUs when there are more than 25 routes to be advertised. Since routing updates are not forwarded, there is no reason to artificially limit the maximum packet size. Therefore, the number of routing entries in any given SIP RIP update shall be governed by the MTU of the link over which the update is to be transmitted. For example, on an Ethernet there may be up to 45 entries in a single update (45 entries times 32 bytes per entry plus 4 bytes of RIP header plus 8 bytes of UDP header plus 20 bytes of IP header equals 1484 bytes). A SIP-RIP packet has the following format. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Command (1) | Version (1) | Routing Domain (2) | +---------------+---------------+-------------------------------+ | Type (1) | Mask Length(1)| TP Class (1) | Metric (1) | +-------------------------------+-------------------------------+ | SIP Address (8) | | | +---------------------------------------------------------------+ | Next Hop (8) | | | +---------------------------------------------------------------+ | First Hop (8) | | | +---------------------------------------------------------------+ All fields are coded in SIP network byte order (big-endian). Command: 1 - request 2 - response Malkin, Huitema Expires: 29Dec93 [Page 3] Internet Draft SIP-RIP June 1993 Version: 1 - SIP-RIP version 1 Routing Domain: The Routing Domain (RD) number is the number of the routing process to which this update belongs. This field is used to associate the routing update to a specific routing process on the receiving router. The RD is needed to allow multiple, independent RIP "clouds" to co-exist on the same physical wire. This gives administrators the ability to run multiple, possibly parallel, instances of RIP in order to implement simple policy. This means that a router operating within one routing domain, or a set of routing domains, should ignore RIP packets which belong to another routing domain. RD 0 is the default routing domain. Type: 1 - Packet Authentication (see section 3.3) 2 - SIP Route Mask Length: The number of one bits in the address/subnet mask, moving left to right. The mask, when applied to the SIP address, yields the non-host portion of the address. Use of a mask length, rather than a complete mask, allows the SIP route entries to be smaller. The drawback, is that discontiguous masks cannot be specified. TP Class: The Throughput Class allows information about the bandwidth of the route to be propogated between routers. The throughput will be encoded with the following formula. INT(10 * log10(datarate_in_Kbps)) There will be no negative Throughput Classes, so datarates under 1Kbps will have a Throughput Class of 0. The following table shows the Throughput Classes for a few common datarates. Malkin, Huitema Expires: 29Dec93 [Page 4] Internet Draft SIP-RIP June 1993 Datarate TP Class Datarate TP Class 7 ___________________ ___________________ 1200bps 0 4Mbps 36 9600bps 9 10Mbps 40 19.2Kbps 12 16Mbps 42 56Kbps 17 45Mbps 46 115.2Kbps 20 100Mbps 50 1.544Mbps 31 1Gbps 60 Of course, the maximum datarate that can be encoded in one byte is only 3,162,277,000,000,000,000Tbps. Metric: The number of hops to the destination. Infinity is 32. SIP Address: The SIP address of this routes destination. Next Hop: The immediate next hop SIP address to which packets to the destination specified by this route entry should be forwarded. Specifying a value of 0 in this field indicates that routing should be via the originator of the packet. An address specified as a next hop must, per force, be directly reachable on the logical subnet over which the advertisement is made. The Next Hop field has two purposes. The first purpose is to eliminate packets being routed through extra hops in the system. It is particularly useful when SIP-RIP is not being run on all of the routers on a network, as exampled in Appendix A. The second purpose is to enable the efficient creation of "reverse trees" for the routing of SIP multicast packets, as described in Appendix B. First Hop: The various routing entries determine a path between the local router and the destination. The First Hop field contains the SIP address of the last router on this route before reaching the destination. This information is used to prevent the formation of loops during the distributed computation of routes. 3.2 Prefered Route Determination The prefered route is determined by taking into account both the Throughput Class and the Metric according to the following rules. Malkin, Huitema Expires: 29Dec93 [Page 5] Internet Draft SIP-RIP June 1993 1- When a routing update is received, the Metric is incremented by 1 and the Throughput Class is set to the minimum of: a) the received value decremented by 1, or zero if the received value was zero; b) the Throughput Class of the subnet over which the update was received. The effect of this rule is to diminish the throughput available from remote links. Only 80% of the link capacity appears available after one relay. 2- If the Metric has reached infinity, the route shall not be used. 3- When two routes have different Throughput Classes, the route with the larger Throughput Class value is considered to be the shorter, prefered route. 4- When two routes have equal Throughput Classes, the route with the lesser Metric is the shorter, prefered route. 3.3 Loop Control The First Hop field is initialized to a null value by the router that initiates the route. If a router receive a RIP message where the First Hop field is null, it fills it with "its own address"; otherwise, the field will be propagated unchanged. It is important, for the loop detection to work, that the router picks exactly one of its IP addresses, and always use this same address, to fill the First Hop field. It is also essential that the router propagates one route that leads exactly to this IP address. The absence of a loop in a given route can be checked for by using the algorithm presented in [5] and [6], which uses the First Hop field. For example, suppose that a host, L, wants to propagate a route, R, to its neighbor, N. Let H be the address of the first hop for route R. The loop detection algorithm can be executed by the following pseudo-code. while (H != L) { if (H == N) return (LOOP_DETECTED); Find R, the route towards H. Let H be the first hop of the route R. } return (ROUTE_IS_SANE); Malkin, Huitema Expires: 29Dec93 [Page 6] Internet Draft SIP-RIP June 1993 If a loop is detected, the metric of the route should be set to infinity. There is a problem with this algorithm in the case of broadcast networks where the SIP-RIP routes will be multicast to several neighbors at the same time. One simple resolution is to check the route information received from broadcast networks, setting N to the address of the local router and L to the address of the router that sent the SIP-RIP message. One current practice within autonomous systems is to aggregate routes; that is, propagating only one route with a prefix of "01101" after receiving two different routes with prefixes of "011010" and "011011". This form of aggregation is incompatible with the loop control algorithm, as the two aggregated routes have different First Hops. One way to maintain the loop control property of the algorithm and also allow aggregation is to organize the autonomous systems as a collection of areas, and to only authorize aggregations of routes "coming out of the same area". 3.4 Authentication The authentication mechanism is similar to that used in RIP-2. If the Type field of the first (and ONLY the first) entry in the packet is type 1, then the remainder of the 20 byte entry is interpreted as a packet authentication. This means that there can be, at most, 24 RIP entries in the remainder of the packet. If authentication is not in use, then no entries in the packet should have an Type field value of 1. The beginning of a packet with an authentication entry has the following format. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Command (1) | Version (1) | Routing Domain (2) | +---------------+---------------+-------------------------------+ | Type = 1 | Authtype (1) | reserved (2) | +-------------------------------+-------------------------------+ ~ Authentication (16) ~ +---------------------------------------------------------------+ Currently, the only Authentication Type is simple password and it is type 2. The Authentication field contains the plain text password. If the password is under 16 bytes, it must be left-justified and padded to the right with nulls (0x00). A password is not null terminated; it is 16 bytes long. Malkin, Huitema Expires: 29Dec93 [Page 7] Internet Draft SIP-RIP June 1993 4. Security Considerations SIP-RIP uses the same authentication mechanism as RIP-2. The authentication types are described in section 3.4 Malkin, Huitema Expires: 29Dec93 [Page 8] Internet Draft SIP-RIP June 1993 Appendix A Use of SIP-RIP Next Hop to eliminate extra hops ----- ----- ----- ----- ----- ----- |IR1| |IR2| |IR3| |XR1| |XR2| |XR3| --+-- --+-- --+-- --+-- --+-- --+-- | | | | | | --+-------+-------+---------------+-------+-------+-- ^------------SIP-RIP------------^ Assume that IR1, IR2, and IR3 are all "internal" routers which are under one administration (e.g. a campus) which has elected to use SIP RIP as its IGP. XR1, XR2, and XR3, on the other hand, are under separate administration (e.g. a regional network, of which the campus is a member) and are using some other routing protocol (e.g. OSPF). XR1, XR2, and XR3 exchange routing information among themselves such that they know that the best routes to networks N1 and N2 are via XR1, to N3, N4, and N5 are via XR2, and to N6 and N7 are via XR3. By setting the Next Hop field correctly (to XR2 for N3/N4/N5, to XR3 for N6/N7), only XR1 need exchange SIP-RIP routes with IR1/IR2/IR3 for routing to occur without additional hops through XR1. Without the Next Hop it would be necessary for XR2 and XR3 to also participate in the SIP-RIP protocol to eliminate extra hops. Malkin, Huitema Expires: 29Dec93 [Page 9] Internet Draft SIP-RIP June 1993 Appendix B Use of SIP-RIP Next Hop for multicast routing Multicast routing is based on "reverse routes". A multicast packet from originator "O" received from subnet "S1" should only be propagated on subnet "S2" if: 1- The scope of the multicast address authorizes this relaying [3], 2- The information obtained through SGMP [4] mentions that the multicast address is "of interest" on subnet "S2", and 3- A packet bound for the address "O" would have been routed through subnet "S1". The route calculated by SIP-RIP can be used to implement the third condition. However, this condition is not sufficient to prevent duplicate delivery when several routers are present on subnet "S2"; one must also analyze the "next hop" information received from these routers. 1- If the local router would not advertise on "S2" a null next hop for the route leading to "O" through "S2", it should not propagate the multicast packet. 2- If several routers advertise a null next hop for the route leading to "O" on "S2", only the router with the lesser SIP address shall propagate the multicast packet. Malkin, Huitema Expires: 29Dec93 [Page 10] Internet Draft SIP-RIP June 1993 References [1] Hedrick, C., "Routing Information Protocol", Request For Comments 1058, Rutgers University, June 1988. [2] Malkin, G., "RIP Version 2 - Carrying Additional Information", Request For Comments 1388, Xylogics, Inc., January, 1993. [3] Deering, S., "Simple Internet Protocol (SIP) Specification", draft-deering-sip-00.txt, Xerox PARC, November 1992. [4] Davin, J., J.D. Case, M. Fedor, M.L. Schoffstall, "Simple Gateway Monitoring Protocol", Request For Comments 1028, November 1987. [5] Cheng, C., R. Riley, S. Kumar, J.J. Garcia-Luna-Aceves, "A Loop- Free Extended Bellman-Ford Routing Protocol Without Bouncing Effect", ACM Sigcomm'89 symposium, September 1989. [6] Rajagopalan, B., M. Faiman, "A New Responsive Distributed Shortest-Path Routing Algorithm", ACM Sigcomm'89 symposium, September 1989. Authors' Addresses Gary Scott Malkin Xylogics, Inc. 53 Third Avenue Burlington, MA 01803 Phone: (617) 272-8140 EMail: gmalkin@Xylogics.COM Christian Huitema INRIA 2004 Route des Lucioles, BP 93 06902 Sophia-Antipolis, France Phone: +33 93 65 77 15 EMail: Christian.Huitema@sophia.inria.fr Malkin, Huitema Expires: 29Dec93 [Page 11]