Network Working Group K. Katsnelson INTERNET DRAFT Elipromm Private Company draft-katsnelson-sddf-ip-cloud-00.txt January 1996 Expires: July 28, 1996 Source-Dependant Default Forwarding in an IP Cloud 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 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." To learn the current status of any Internet-Draft, please check the "lid-abstracts.txt" listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast). Distribution of this memo is unlimited. Please send suggestions and comments to author or to the IETF mailing list . Table Of Contents 1. Abstract...........................................................2 2. Background.........................................................2 3. Comparison To IP Tunneling.........................................4 4. Routing Algorithm..................................................4 5. Data Propagation Protocol..........................................6 5.1. Introduction...................................................6 5.2. Class IDs......................................................6 5.3. Sequence IDs...................................................6 5.4. Security.......................................................6 5.5. Protocol Description...........................................7 5.6. A Participant boot-up..........................................8 5.7. UDP port number................................................8 5.8. The OFFER UDP Message..........................................8 Katsnelson draft-katsnelson-sddf-ip-cloud-00.txt [Page 1] Source-Dependant Default Forwarding in an IP Cloud January 1996 5.9. The SENDME UDP Message.........................................9 5.10. Data Instance Header..........................................9 6. Trusted Networks Table March Format And Class ID...................9 7. SDDF Table March Format And Class ID..............................10 8. Security Considerations...........................................11 9. References........................................................11 10. Author's address.................................................11 1. Abstract This memo describes Source Driven Default Forwarding (SDDF) procedures. These procedures are intended for establishing proper routing in an autonomous system (AS) that consists of a number of interconnected routers, and provides filtered IP transport between its border networks. Such an AS is called "IP cloud" further within this document. The SDDF method is an alternative to IP tunneling, which is used in such a networks nowadays. This memo also defines an algorithm used by a router in the cloud, structure of tables used by the algorithm, and a protocol used to distribute these tables across the cloud. 2. Background The SDDF task emerged from real needs of a company that intents to install such a system. The cloud of routers has connections to both IP Service Providers (ISP) and their clients. An ISP has also another connection(s), that are to provide client's access to the rest of the Internet. We call networks that are lying by other side of ISP connections "distant networks." In turn, networks inside ISPs and clients, and the cloud itself, are "near networks." The "client" in such terms is a group of networks that sends IP packets to the cloud destined to either near or distant networks. ISP itself sends to the cloud only those packets, that are destined to its clients, i.e., only to local networks. This follows from the fact that no ISP is a client to another ISP in the cloud, otherwise this should cause packet to travel twice through the cloud, once from client to first ISP, and once from that ISP to another ISP. So, we have three sorts of packets transmitted over the cloud. There are: i) packets originated at local network and destined to a local network, ii) packet originated at distant network and destined to a local network (through ISP) and iii) packets originated at local network and destined to a distant network. Types i) and ii) are supported by traditional, destination-based routing model, provided that routing information from local networks Katsnelson draft-katsnelson-sddf-ip-cloud-00.txt [Page 2] Source-Dependant Default Forwarding in an IP Cloud January 1996 is advertised or otherwise known to the cloud routers. So any packet destined to a local network can be forwarded to the border gateway of the system carrying the network by usual routing means. Type iii) is a different case. Packet destined to a distant network should be routed first to an ISP of a client that originated the packet. So the packet should be forwarded within the cloud as if it were destined to the ISP of the client originated it. This cannot be done by traditional router, since packet's source address is not taken into account while routing. This led us to introduce a different kind of routing: SDDF. When a packet is determined to be destined to a distant network, it is routed using SDDF. Otherwise, traditional destination-driven algorithm is used. SDDF router knows an ISP border gateway address for each of local networks. When routing a packet, SDDF algorithm determines ISP's gateway given packet's source address, and then uses traditional routing procedure to route the packet as if it was destined to that gateway. Resolution is performed by a table-driven algorithm. When IPS's address cannot be resolved from the source address, then packet sender is notified with ICMP Network Unreachable message[4], and the packet is discarded. SDDF algorithm, as it has been said before, is applied by the router only to packets destined to distant networks. So, there must be a way to determine whether destination is local or distant. This determination can be easily made by traditional routing table lookup, provided that no distant networks are advertised by routing information interchange protocols to the cloud routers. In this case, packet first routed using traditional routing scheme. If this scheme causes routing miss event, failing to determine next hop router due to missing of a destination address in its routing tables, then the packet is destined to a distant network, and the SDDF algorithm should be used. The SDDF algorithm in described in section 4. Beyond the algorithm itself, this memo defines a protocol that keeps SDDF tables in-sync at all cloud routers. Tables are propagated from a single host, called "primary host." Each router keeps two tables: one is for SDDF forwarding algorithm itself, and another, called "trusted networks table," defines which networks have read-only access to the tables, and which are allowed to change the tables. Read-only access is helpful for ISPs, in their track for unsolicited traffic and other network problems, while full access is intended for tables propagation and should be set only for networks comprising the cloud. The protocol is described in section 5 through 6. Katsnelson draft-katsnelson-sddf-ip-cloud-00.txt [Page 3] Source-Dependant Default Forwarding in an IP Cloud January 1996 3. Comparison To IP Tunneling Currently, similar behavior is achieved by using IP over IP encapsulation (IP tunnels)[1,2]. Advantages of the SDDF are that: * it eliminates the overhead of transmitting extra data, since packets are transferred in non-encapsulated form; * it shortcuts packet paths when a client of some provider uses different provider's public services (for instance, FTP, WWW and others). 4. Routing Algorithm Suppose we have a number of interconnected routers (at least one), which form the cloud, at least two ISPs and at least two clients connected to the cloud. All considerations are applicable to this model scaled to an arbitrary number of routers/ISPs/clients. Single routing action performed by the router is defined as calculation of next hop address given source and destination IP addresses as they appear in the packet. Traditional routing action [3] is performed based on destination address of the packet: next_hop_address = trad_routing (packet.ip_dest_address); If next fop address cannot be determined, then routing miss occurs. We will indicate this by condition next_hop_address == ROUTING_MISS Usually, when routing miss occurs, an ICMP Host Unreachable packet is send back to the originator of the packet. So, pseudo-code of traditional routing procedure can be written that way: packet = get_ip_packet (); next_hop_address = trad_routing (packet.ip_dest_address); if (next_hop_address == ROUTING_MISS) send_ICMP_host_unreachable_to (packet.ip_src_address); else send_packet_to (packet, next_hop_address); In our model system, routing miss can result from one of the following conditions: i) Packet originated at client's host and destined to a distant host. Katsnelson draft-katsnelson-sddf-ip-cloud-00.txt [Page 4] Source-Dependant Default Forwarding in an IP Cloud January 1996 ii) Packet originated at any other host, and packet destination is not known to the traditional routing procedure. Source-dependent default routing comes to play when traditional routing procedure leads to routing miss. SDDF router tries to forward the packet to an ISP assigned to the client that has originated the packet, for that ISP to route it farther: assigned_ISP_address = SDDF_routing (packet.ip_src_address); In the case i), this procedure returns ISP address. The packet then routed exactly as if it were destined to this address. In the case ii), when source address is not an address of a registered client, this procedure fails to determine ISP address: assigned_ISP_address == SDDF_MISS The pseudo-code for SDDF router is shown below: packet = get_ip_packet (); next_hop_address = trad_routing (packet.ip_dest_address); if (next_hop_address == ROUTING_MISS) { ISP_address = SDDF_routing (packet.ip_src_address); if (ISP_address == SDDF_MISS) send_ICMP_host_unreachable_to (packet.ip_src_address); else { next_hop_address = trad_routing (ISP_address); if (next_hop_address == ROUTING_MISS) /* Unlikely case: unreachable ISP! */ send_ICMP_host_unreachable_to (packet.ip_src_address); else send_packet_to (packet, next_hop_address); } } else send_packet_to (packet, next_hop_address); The mentioned above SDDF_routing function, which calculates assigned ISP address given client's address, is table-driven, where each entry in the table consists of client net address and ISP border router address: struct SDDF_table_entry { ip_address client_address; ip_address client_mask; ip_address ISP_router_address; }; The size of the ip_address type may vary across implementations. This enables support for non-IP and future IP networks. This variable size is a part of the table march (see section 7). Katsnelson draft-katsnelson-sddf-ip-cloud-00.txt [Page 5] Source-Dependant Default Forwarding in an IP Cloud January 1996 5. Data Propagation Protocol 5.1. Introduction At is has been said in Background section, the data propagation protocol (DPP) is intended to distribute router control tables across the cloud. The protocol itself does not define table data format; table is considered as a solid sequential block of data. Each table format is referred to as "class" within this protocol description. Table packed for transmission over network is referred to as "march." An instance of the table transmitted using DPP is referred to as "data instance." Data instance consists of a march plus protocol control fields. Propagation starts at the primary host, goes to its neighbors, then to neighbors of that neighbor, and so on. Such a propagation does not necessary starts each time on the same host; although the protocol carries no protection against emitting conflicting (equally tagged but different) data simultaneously by several hosts. So emitting updated data of each class each time from the same host without taking other precautions looks the only reliable approach. The protocol uses UDP for updated data offers/requests between hosts, and TCP for data transmission. 5.2. Class IDs Each different class of data transferred with DPP is assigned its own unique identifier. This allows different classes to be distinguished in transmissions. Class ID is an unsigned 32-bit number and transmitted over network in network byte order. 5.3. Sequence IDs Each instance of data is tagged with Sequence identifier. Sequence identifier is assigned at the primary host, before first introducing instance to the cloud. Sequence IDs must be assigned in increasing order. The higher Sequence ID a data instance carries, the fresher it is assumed. Sequence ID is an unsigned 32-bit number and transmitted over network in network byte order. 5.4. Security A participant of the protocol has a trusted networks table, which gives other participants rights to receive data from and/or send updated data to that participant. Access is controlled on per-class basis. This table is also distributed across the cloud, by using the DPP itself. The march format of the trusted networks table in described in Section 6. Katsnelson draft-katsnelson-sddf-ip-cloud-00.txt [Page 6] Source-Dependant Default Forwarding in an IP Cloud January 1996 5.5. Protocol Description Each participant of the protocol sends notification messages, OFFER, via UDP to its neighbors. Neighbors are hosts and routers that are in exactly one hop far from the participant. Each message contains Class IDs and Sequence IDs of data instances it currently holds. Messages are sent at regular configured intervals, and upon renewal of any of its data instances. Upon receipt of OFFER message, a participant first checks if a sender of the message is valid, i.e., has rights to modify data of a class it offers. If security check fails, the data of that class is not requested. Recipient of the OFFER message then decides whether it needs renewed data, and of what of offered class exactly. For each of these classes, it then checks if offeror has modify rights on the data. If it needs it, it sends SENDME message, also via UDP, to a participant that offered update. The SENDME message contains only Class IDs for data being requested; since Sequence IDs are always increase, requester is guaranteed to receive only instance of the same or higher Sequence ID from the offeror. The SENDME message also contains TCP port number, on which sender of the message waits for a connection from offeror. If SENDME message is not to be sent, because no new data is required and/or security check failed, then the OFFER message is discarded silently, and no notification is sent to its sender. Note that the SENDME message can be issued without preceding OFFER message. This is useful for someone who wants to receive copy of the data for examination. Upon receipt of the SENDME message, a participant opens TCP connection to the sender of the SENDME message, to the port specified in the SENDME command. Then it checks if it has data of requested class(es), and if the sender of the message has read access to these data. If there is any data to send, it sends data instances to the TCP connection, without padding and intermediate information. Receiptor of the SENDME message then closes the connection. Note that if there is no data to be sent, TCP connection is still opened and then closed. The peer side, upon accepting the connection, checks if its peer is the same host as that the SENDME command was send to. If this check fails, the participant closes the connection and listens for the next one. Katsnelson draft-katsnelson-sddf-ip-cloud-00.txt [Page 7] Source-Dependant Default Forwarding in an IP Cloud January 1996 After transmission of each instance, a participant demarshalls the data and checks them for a validity. If the received data is invalid, it marks the peer as incompatible or malfunctioning, in per-class basis, notifies network administrator on the event and never requests data of that class from this peer until the administrator manually resets this behavior back to normal. Early connection termination is not considered as an error of that kind; only fully received marches are demarshalled and checked, while unreceived are asked again for. 5.6. Participant boot-up Upon boot-up, a participant must first build its initial trusted networks table. Initial network table is built based on the table of trusted interfaces, that is stored on its hard disk, ROM or other power independent storage. Interface table consists of interface names or other identity, depending on participant's internal structure. Upon start, the participant waits while a line with a next hop accessible over a trusted interface appears in its routing tables. This next hop address then added into initially empty trusted networks table, with modify access to trusted networks table class. Then participant then sends SENDME message requesting trusted networks table, to that next hop address. The process is repeated on other trusted interfaces. The SENDME message is repeated at configured intervals, on all interfaces, until real trusted networks table is received. Since that moment, the participant goes to the described above discipline of service. 5.7. UDP port number This draft document does not define UDP port number used by this protocol. The number will be requested from IANA in the case of approval of this memo as a RFC. 5.8. The OFFER UDP Message The OFFER message has the following format: struct SDDF_DPP_OFFER { unsigned_int16 message_code; unsigned_int16 number_of_offers_in_this_message; struct _single_offer { unsigned_int32 class_id; unsigned_int32 sequence_id; } [AS_MANY_AS_OFFERS_IN_THIS_MESSAGE]; }; Type "unsigned_int16" stands for 16-bit unsigned integer value, and "unsigned_int32" for 32-bit unsigned integer value. The "message_code" in this message is set to 1 (one). Katsnelson draft-katsnelson-sddf-ip-cloud-00.txt [Page 8] Source-Dependant Default Forwarding in an IP Cloud January 1996 5.9. The SENDME UDP Message The SENDME message has the following format: struct SDDF_DPP_OFFER { unsigned_int16 message_code; unsigned_int16 number_of_classes_requested_in_this_message; unsigned_int16 tcp_port_number; unsigned_int16 filler_to_32bits_boundary_reserved_must_be_0; unsigned_int32 class_id [AS_MANY_AS_REQUESTED_CLASSES]; }; The "message_code" in this message is set to 2 (two). 5.10. Data Instance Header Data instance is transferred over TCP connection as a header and a march following it. While march format is not a matter of this protocol, the header is defined by this specification. The format of the header is: struct SDDF_DPP_DATA_INSTANCE_HEADER { unsigned_int32 class_id; unsigned_int32 sequence_id; unsigned_int32 march_size_in_octets; }; This data header is immediately followed by a march, which, in turn, followed immediately by next data header, and so on. TCP connection is closed after last byte of the last transferred march. 6. Trusted Networks Table March Format And Class ID Trusted network table is assigned a class ID of 1 (one). Trusted Networks Table March consists of a header and a number of entry marches. Header is transmitted first, then entry marches, without any padding or dividing. Overall length of the march thus equals to size of the entry march multiplied by number of marches plus size of the table march header. Type "unsigned_int16" stands for 16-bit unsigned integer value, and "unsigned_int32" for 32-bit unsigned integer value. Integer numbers are transferred in network byte order. The structures are defined below: struct SDDF_DPP_Trusted_Networks_Table_March_Header { unsigned_int16 ip_address_lenght_in_octets; unsigned_int16 number_of_entry_marches; }; Katsnelson draft-katsnelson-sddf-ip-cloud-00.txt [Page 9] Source-Dependant Default Forwarding in an IP Cloud January 1996 The field ip_address_lenght_in_octets gives the size of IP address and mask in entry marches. Each implementation must support IPv4 addresses; support for IPv6 is highly recommended. struct SDDF_DPP_Trusted_Networks_Table_Entry_March { ip_address trusted_network_address; ip_address trusted_network_mask; unsigned_int32 class_id_this_entry_gives_access_to; unsigned_int32 access_mask; }; Upon checking access, the table is looked up downwards from the beginning against the given network address. Search stops upon hitting the first match, so order of entries is important for subnets with different size masks. If match is not found, host receives no access to the given class. If the "class_id_this_entry_gives_access_to" field is zero, this entry is considered to be wildcards, and applies to all classes. The "access_mask" field has the following format: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | R E S E R V E D |M|R| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |31 |1|0| Bit 0, when set, allows read access to the class data from the network. Bit 1 gives modify access. Bits 2 through 31 are reserved and must be all set to zero. 7. SDDF Table March Format And Class ID SDDF Table is assigned a class ID of 2 (two). SDDF Table March consists of a header and a number of entry marches. Header is transmitted first, then entry marches, without any padding or dividing. Overall length of the march thus equals to size of the entry march multiplied by number of marches plus size of the table march header. Type "unsigned_int16" stands for 16-bit unsigned integer value, and "unsigned_int32" for 32-bit unsigned integer value. Integer numbers are transferred in network byte order. The structures are defined below: struct SDDF_DPP_March_Table_March_Header { unsigned_int16 ip_address_lenght_in_octets; unsigned_int16 number_of_entries; }; Katsnelson draft-katsnelson-sddf-ip-cloud-00.txt [Page 10] Source-Dependant Default Forwarding in an IP Cloud January 1996 The field "ip_address_lenght_in_octets" gives the size of IP address and mask in entries. Each implementation must support IPv4 addresses; support for IPv6 is highly recommended. struct SDDF_DPP_March_Table_Entry_March { ip_address client_address; ip_address client_mask; ip_address ISP_router_address; }; Upon finding the ISP border router address, the table is looked up downwards from the beginning against the given network address. Search stops upon hitting the first match, so order of entries is important for subnets with different size masks. 8. Security Considerations Section 5, "Data Propagation Protocol," deals with security of the protocol is divisions 5.4 and 5.6. Security at boot-up relies on correctness of routing information supplied via routing information interchange protocols. Although, since boot-up trusted network table is based on the interface table, and links via those interfaces are probably leading to trusted hosts, spoofing routing information seems not to be possible. At the time of normal (versus boot-up) operation, it also looks hard to fake a TCP connection between neighboring hosts while being on a host that is some hops far. 9. References [1]. W. Simpson, "IP in IP Tunneling", 10/04/1995, RFC 1853. [2]. Y. Rekhter, "Routing in a Multi-provider Internet", 04/14/1995, RFC 1787. [3]. F. Baker, "Requirements for IP Version 4 Routers", 06/22/1995, RFC 1812. [4]. J. Postel, "Internet Control Message Protocol", 09/01/1981, RFC 792, STD 5. 10. Author's address Kirill M Katsnelson Elipromm Priv. Co. Nizhni Novgorod Svirskaya 19-11 Russia 603054 Katsnelson draft-katsnelson-sddf-ip-cloud-00.txt [Page 11] Source-Dependant Default Forwarding in an IP Cloud January 1996 E-mail: Phone: +7(831)222-5603 This Internet-Draft expires on July 28, 1996 Katsnelson draft-katsnelson-sddf-ip-cloud-00.txt [Page 12]