INTERNET DRAFT D. Helder S. Jamin University of Michigan July 2000 Expires: January 2001 IPv4 Option for Somecast 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. Abstract Somecast is a multi-point delivery technology that allows a packet to be sent to a set of destinations. Somecast delivery means that the network delivers one copy of a packet to each destination listed in the packet. Somecast can be used in small multi-user sessions, such as multimedia conferences and multiplayer games, or used with endhost multicast for larger sessions. This document describes a possible implementation of somecast in IPv4. Somecast is implemented by using an IPv4 header option that includes a list of up to 9 additional destination addresses. This document also describes how somecast can be incrementally deployed. Table of Contents 1 Introduction Helder et al. Expires January 2001 [Page 1] INTERNET-DRAFT IPv4 Option for Somecast July 2000 2 Implementation 2.1 Somecast packet 2.2 Routing 2.3 Deployment 2.4 BSD Sockets API Extensions 3 Miscellany 3.1 Detecting somecast 3.2 Differences between somecast and multicast 3.3 Partioning large membership lists 3.4 Deployment using "fork-late" routing 4 Justification 4.1 Small multimedia sessions 4.2 Endhost multicast 4.3 Some-pings 5 Security Considerations 6 Acknowledgements 7 Authors 1 Introduction Somecast is a multi-point delivery technology that allows a packet to be sent to a set of destinations. Somecast delivery means that the network delivers one copy of a packet to each destination listed in the packet. Somecast can be used in small multi-user sessions, such as multimedia conferences and multiplayer games. It is ideal for endhost multicast, where endhosts organize themselves into a virtual network used to forward multicast data without router cooperation. When available, somecast can improve the efficiency of endhost multicast. This document describes a possible implementation of somecast in IPv4. Somecast is implemented by using an IPv4 header option that includes a list of up to 9 additional destination addresses. When a router receives a somecast packet it examines the destinations. If two or more destinations have different outgoing interfaces, the router "forks" the somecast packet. To fork the packet, the router forwards a copy to each of these interfaces. Each copy is first modified to include only the destinations appropriate for that interface. The IPv4 implementation does not require Internet-wide deployment. Host can benefit from somecast even if it is only deployed at the first router. It would mainly benefit hosts with low-bandwidth uplinks to their ISPs (e.g., wireless, one-way cable modem, ADSL) that participate in small multi-user sessions or endhost multicast. Helder et al. Expires January 2001 [Page 2] INTERNET-DRAFT IPv4 Option for Somecast July 2000 2 Implementation Somecast is implemented by using an IP header option that includes a list of additional destination addresses. When a router receives a somecast packet it may fork the somecast packet into multiple somecast packets based on the destinations and the outgoing interfaces. This section describes the IPv4 option for somecast and how a somecast-aware router should process a somecast packet. It also includes notes on the deployment of somecast. 2.1 Somecast Packet A "somecast packet" is an IPv4 packet with an IPv4 option for somecast. The option includes an option code and a list of IPv4 addresses that the packet should be sent to IN ADDITION to the address in the regular destination field of the packet. The destination field is always used. If a somecast packet has a single address, either there will be no somecast option or there will be a somecast option with no addresses listed. The former is recommended because it will save bandwidth and router processing time. Note that such a packet would be indistinguishable from a regular IP packet, though we will still refer to such a packet as a "somecast packet". A diagram of the somecast option is shown below. 0 + X 8 + X 16 + X 24 + X 32 + X +--------------+---------------+--------------+--------------+ | OPTION CODE | LENGTH | RESERVED (0) | +--------------+---------------+--------------+--------------+ | somecast address 1 | +--------------+---------------+--------------+--------------+ | [...] | +--------------+---------------+--------------+--------------+ | somecast address N | +--------------+---------------+--------------+--------------+ Every IP option has an OPTION CODE. The OPTION CODE consists of a COPY bit, OPTION CLASS, and OPTION NUMBER. The COPY bit for the somecast option is 1 (on) and the OPTION CLASS is 0 (datagram or network control). The OPTION NUMBER for the somecast option will be assigned later. Helder et al. Expires January 2001 [Page 3] INTERNET-DRAFT IPv4 Option for Somecast July 2000 Following the option code, there is a one byte LENGTH field specifying the length of the list of addresses. Following the LENGTH field, there are two reserved bytes. They should both be zero. Following the RESERVED field is a list of LENGTH addresses which the packet should be sent to in addition to the address in the destination field. Each address is a 4-byte IPv4 address. Note that only 40 bytes of an IPv4 header can be used for options. Therefore, there can be at most 9 addresses listed in the somecast option, or at most 10 destinations total in a somecast packet. If a packet must be sent to more than 10 destinations, multiple somecast packets must be sent. 2.2 Routing We will call a router capable of understanding the somecast option and performing somecast routing "somecast-aware". Similarly, a router that does not understand the somecast option is "somecast-unaware". When a somecast-aware router receives a somecast packet it examines the destinations. If two or more destinations have different outgoing interfaces, the router "forks" the somecast packet. To fork the packet, the router forwards a copy to each of these interfaces. Each copy is first modified to include only the destinations appropriate for that interface. Each destination address listed in an incoming somecast packet will be in one and only one outgoing packet. The router should not include the somecast option field if a resulting forked packet has only one address. However, we do not consider it incorrect to include a somecast option with no addresses listed. The pseudo-code in table CODE illustrates one way a router can perform somecast routing. ---------------------------------------- Table CODE Assume interfaces are numbered from 0 to NUM_INTERFACES MAX_ADDRESSES = 10 NUM_INTERFACES = number of interfaces int num_addresses[NUM_INTERFACES] Helder et al. Expires January 2001 [Page 4] INTERNET-DRAFT IPv4 Option for Somecast July 2000 address_t addresses[NUM_INTERFACES][MAX_ADDRESSES] zero out num_addresses zero out addresses for each address a in packet i = route_to_interface (a) addresses[i][num_addresses[i]] = a num_addresses[i] = num_addresses[i] + 1 for each interface i if (num_addresses[i] > 0) if (num_addresses[i] == 1) copy packet without somecast option new_packet.destination address = addresses[0] else copy packet with somecast option of size 4 + 4 * (num_addresses[i] - 1) bytes new_packet.destination address = addresses[0] for each address a 1 to num_addresses[i] put address[num_adddres[a]] in option send packet ---------------------------------------- When a somecast-unaware router receives a somecast packet, it will ignore the somecast option (since, by definition, it does not understand it) and forward the packet based on the destination address in the standard destination field of the IP header. Somecast-unaware routers will only receive somecast packets in special and rare circumstances discussed in the next section and section 3.4. 2.3 Deployment Somecast can be deployed incrementally. It is unlikely that somecast will be widely deployed in the near future. Hence we consider issues in its incremental deployment. We envision somecast first being emulated in OS kernels. When a user sends a somecast packet, the kernel will convert the packet into regular, unicast packets and forward them in the usual way. Next, edge routers would deploy somecast and kernel emulation could be Helder et al. Expires January 2001 [Page 5] INTERNET-DRAFT IPv4 Option for Somecast July 2000 turned off. Detecting whether the first router is somecast-aware is discussed in 3.1. Finally, core routers will deploy somecast, but this may not be until the distant future or may never occur. One issue to consider is the interaction between somecast-aware and somecast-unaware routers [1]. Consider the case where a somecast-aware router has a somecast packet it must forward to a somecast-unaware router [2]. If all routers on the path to the destination of the somecast packet are somecast-unaware, then the destination host would be responsible for forking the packet. However, this will only happen if the destination host is somecast-aware. If it isn't, the destination addresses listed in the somecast option will never receive the packet. Therefore, a somecast-aware router should not forward somecast packets to somecast-unaware routers. Instead, it should convert the somecast packet into many regular, unicast packets and forward those instead. The only time a somecast-aware router may forward to a somecast-unaware router is if it knows for certain it will later reach a somecast-aware router. For example, a 2-port router may be somecast-unaware, but the routers on either side are somecast-aware. It would be acceptable for either router to forward a somecast router to the 2-port router because they know the next router will be a somecast-aware router. In section 3.4, we discuss an alternate routing policy called "fork-late" routing, which would allow a somecast-aware router to forward a somecast packet to a somecast-unaware router in the general case. This would require modifications to the somecast option as presented, so we do not discuss it here. [1] We assume that a somecast-router knows whether a neighbor router is somecast-aware or not. It may have been manually configured by the network adminatrator to know this, detected this using a technique described in 3.1, or by some other means. [2] Note the reverse case is easy: if a somecast-unaware router forwards a somecast packet to a somecast-aware router, the somecast-aware router should process it in the regular way. 2.4 BSD Sockets API Extensions This subsection includes notes on the extensions to the BSD sockets Helder et al. Expires January 2001 [Page 6] INTERNET-DRAFT IPv4 Option for Somecast July 2000 API that would be required for somecast. The idea presented here could be applied to other API's also. Receiving a somecast packet would be the same as receiving a UDP or raw IP packet. Whether a received packet was a somecast packet would be invisible to the user. Ideally, the kernel receives the somecast transmitted packet as a regular IP packet (i.e., without the somecast option). There are at least two ways to implement sending somecast packets. The problem is when to specify the list of destinations. The first way is to bind a socket with an array of addresses as you might bind a UDP socket with a single address. The second way is to send a packet with an array of destination addresses as you might use sendto with a socket descriptor and an address. The first could easily be implemented by adding a new socket option (changing bind is unrealistic). The second would be more difficult to implement, though would be easier for the programmer to use if the list of destination addresses is changed frequently. The kernel should allow the array of addresses, however specified, to be sufficiently large so that the programmer does not need to manually partition the list of addresses except in rare cases. A good limit is 256 destinations; 10 destinations is not a good limit. One issue to consider is port reuse. Two processes may need to bind to the same port to receive somecast packets for two different `somecast sessions'. With IP multicast, each process would set the SO_REUSEADDR (or SO_REUSEPORT) option for the socket. When a packet sent to a multicast address arrives, the kernel would give each process a copy of the packet. It would then be up to each process to determine whether it should process or ignore the packet. This is similar for broadcast. Similarly for somecast, the kernel would need to allow processes to set the SO_REUSEADDR or SO_REUSEPORT for a port. The kernel should not allow the process to set the flag if another process has bound to the port but not set the flag. In some kernels this may already work as described. But, other kernels may not duplicate packets that are sent to non-multicast and non-broadcast addresses. [See discussion in Stevens' UNP pp. 195-6] 3 Miscellany 3.1 Detecting somecast It is easy for a host to detect if the path to a destination host is "somecast-aware". A path is somecast-aware if the destination is Helder et al. Expires January 2001 [Page 7] INTERNET-DRAFT IPv4 Option for Somecast July 2000 somecast-aware or there is a router between the source and the destination that is somecast-aware. To detect this, the host can send a somecast packet addressed to the destination host and itself. (That is, the somecast packet has the destination field set to the address of the destination host and the address list of the somecast option includes only the source address.) If a router on the path is somecast-aware, both the source and the destination will receive the packet. Otherwise, only the destination will receive the packet. Note that because IP datagram delivery is unreliable, not receiving the packet back does not mean the path is not somecast-aware. Moreover, routes can change. A route that was previously somecast-aware may become somecast-unaware and vice versa. It is probably not useful to be able to determine whether any host is somecast-aware. I know of no way of doing this currently [1]. However, it is useful for a somecast source to know whether the first router is somecast-unaware so that somecast emulation can be turned on in its kernel. For example, the kernel may send a somecast detection probe when it boots up, when the network configuration is changed, or probe the router periodically. If the first router is not somecast-aware, the source will use somecast emulation. [1] We could add a "destination fork only" flag to the somecast option. If a non-destination router receives a somecast packet with the flag set, it won't fork the packet. If a destination host receives a somecast packet with the flag set, it will fork the packet. We could then use self-addressed somecast packets with this flag set to determine if _any_ host is somecast-aware. 3.2 Differences between somecast and multicast Please note that somecast is _NOT_ being proposed as a complete replacement for IP multicast. This section explains technical and conceptual differences. Membership in multicast is implicit. Hosts can join or leave a group without knowledge of other members. A multicast group is identified by a multicast IP address. In somecast, membership is explicit; session management must be done at a higher level. Because anyone can join a mulitcast session, the session must be encrypted to achieve any measure of privacy. However, in somecast, there is some privacy even without encryption because membership is explicit. Note though that someone could still eavesdrop at the IP level (e.g., packet sniffing) or receive a misdirected packet. Helder et al. Expires January 2001 [Page 8] INTERNET-DRAFT IPv4 Option for Somecast July 2000 Another difference is that somecast does not scale well. If a host wants to send a packet to hundreds of hosts, it would need to send several somecast packets since the number of addresses that can fit into an IPv4 somecast packet is small. If the host intends to send to a large group, it should use multicast (or endhost multicast with somecast). Multicast routers need to store routing information about multicast groups and send and receive state updates. Somecast-aware routers do not require extra state or state updates, but do need more processing resources to process a somecast packet. 3.3 Partitioning large membership lists If a host wants to send a somecast packet to more than 10 hosts, it must partition the list into sets of at most 10 hosts and send a somecast packet to each of these sets. This may be done at the user or kernel level. If two hosts are nearby in the network, it would be more efficient if they were listed in the same somecast packet than if they were not. The question is, is there a good way to do this? Given topology information the host could optimally partition the list. However, this is probably impractical. But, there may be heuristics for making good partitions. If the host sorts the list before partitioning, two hosts that are in the same network and have the same address prefix will probably be put in the same somecast packet. 3.4 Deployment using "fork-late" routing With some modifications, somecast could be deployed using a routing policy we call "fork-late" routing. In fork-late routing, a somecast-aware router can forward a somecast packet to a somecast-unaware router. The hope is that the packet will later reach a somecast-aware router and the router will possibly fork the packet. We will call the routing policy described in 2.3 "fork-early" routing. There are many situations when fork-late routing will perform better than fork-early routing. For example, consider a somecast packet destined for two hosts in the same AS. In the likely case that the edge routers are somecast-aware and the core somecast-unaware, fork-early routing would fork the packet just before it reaches the core resulting in two unicast packets crossing the core. In fork-late routing, however, a single somecast packet would cross the core and then be split at the appropriate point by a somecast-aware router within the AS. [TODO: DIAGRAM] Helder et al. Expires January 2001 [Page 9] INTERNET-DRAFT IPv4 Option for Somecast July 2000 The main problem with fork-late routing is that it requires a host to know whether there is a somecast-aware router downstream from a somecast-unaware router. If there isn't and the destination host is not somecast-aware, the other destinations will not receive the packet. Another disadvantage is that a somecast packet traveling through a somecast-unaware router would be not be in the router's "fast-path" because of the somecast option. This would add extra delay to the somecast packet. It may then be a good idea to add a fork-late flag option to the somecast option. A host could trace the routes to the destinations, detect which routers and destinations are somecast-aware [1], and use this information to determine if fork-late routing should be used. An implementation issue is how to get around egress routing restrictions. When the endhost forks the somecast packet, it sends a packet with a source address different from its own address. The problem is a router may restrict hosts from sending IP packets with source addresses that aren't in the network. This is done to prevent hackers from forging packets. The host could set itself as the source, but this may confuse a higher-level protocol that now cannot know who the true sender is. Also, the host could now be used by a hacker source to hide an attack against the destinations. [1] Detecting whether a given host or router is somecast-aware may require another flag in the option. This is described in the footnote in section 3.1. 4 Justification 4.1 Small multimedia sessions Somecast would be ideal for small multimedia sessions such as video/audio conferences and network gaming. A higher level protocol would be needed to organize the participants and distribute membership information. It would also save bandwidth for hosts with a low-bandwidth uplink to their ISP (e.g., wireless, one-way cable modem, ADSL). Even if routers beyond the ISP were somecast-unaware, it would be worth deploying for the ISP. 4.2 Endhost multicast Helder et al. Expires January 2001 [Page 10] INTERNET-DRAFT IPv4 Option for Somecast July 2000 In endhost multicast (EM), endhosts organize themselves into a virtual network used to forward multicast data without router cooperation. EM may be implemented in the hosts' kernels or user level programs using any transport protocol. A trivial example of EM is where the hosts elect a server which forwards any data sent to it to all other hosts. One issue in EM is `fanout', the number of hosts a given host is connected to. If a host has a high fanout (i.e., the host is connected to many hosts), then the host will use more bandwidth forwarding packets and increase the stress on nearby links. However, the connected graph will have a lower diameter and hence the latency between any two hosts in the group will be low. On the other hand, if a host has a low fanout (i.e., the host is connected to only a few hosts), then the host will not use as much bandwidth, but latency between two hosts in the group will be high. In the presence of somecast, the host could increase the fanout and get the benefits of a large fanout without significantly using more bandwidth or significantly increasing the stress on nearby links. 4.3 Some-pings A `ping' is an action that finds the round-trip-time between a host and another host. In IPv4, it is usually done by sending an ICMP echo-request packet to the destination host and measuring the time between the time that packet was sent and the time an ICMP echo-reply packet is received from the destination. The distance, or latency, between the source and destination is half the round-trip-time. If the paths are symmetric, this gives a good estimate of the actual distance. Somecast could be used to do a `someping' - a ping of a set of hosts. ICMP is layered on top of IPv4, so this can be supported without extra modifications to router software. One problem with this technique though is that if the somecast packet travels through multiple somecast-unaware routers before being forked, the results may be off because the ping packet travels through more routers than a normal packet would. As long as somecast routers fork the packet as soon as they encounter a non-somecast router, this shouldn't happen. One problem with this is that a hacker could forge the source address of the somecast packet to a target address. The recipients of the someping will all reply to the target address. If multiple somecast packets were sent to many sources, the hacker could use all of the target's bandwidth. This is commonly called a "smurf attack". We do not have a good way to prevent smurf attacks. Helder et al. Expires January 2001 [Page 11] INTERNET-DRAFT IPv4 Option for Somecast July 2000 5 Security Considerations Security considerations will be included in a future draft. 6 Acknowledgements The authors thank Paul Francis for his comments on this draft. 7 Authors David Helder University of Michigan EECS Building 1301 Beal Ave. Ann Arbor, MI 48103 Phone: (734) 647-0031 Email: dhelder@eecs.umich.edu Sugih Jamin University of Michigan EECS Building 1301 Beal Ave. Ann Arbor, MI 48103 Phone: (734) 763-1583 Email: jamin@eecs.umich.edu Helder et al. Expires January 2001 [Page 12]