Internet DRAFT - draft-dhelder-somecast
draft-dhelder-somecast
INTERNET DRAFT D. Helder
S. Jamin
University of Michigan
July 2000
Expires: January 2001
IPv4 Option for Somecast
<draft-dhelder-somecast-00.txt>
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]
