INTERNET DRAFT                                              C. Huitema
<draft-ietf-ngtrans-shipworm-00.txt>                         Microsoft
Expires August 25, 2001                                August 25, 2001

Shipworm: Tunneling IPv6 over UDP through NATs

Status of this memo

This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.

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."

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

We propose here a service that enables nodes located behind one or
several IPv4 NATs to obtain IPv6 connectivity by tunneling packets
over UDP; we call this the Shipworm service. The establishment of
the tunnel is automatic, and does not require any configuration
parameters on the client. Running the service requires the help of
"Shipworm servers" and "Shipworm relays"; the Shipworm servers are
stateless, and only have to manage a small fraction of the traffic
between Shipworm clients; the Shipworm relays act as IPv6 routers
between the Shipworm service and the "native" IPv6 Internet.

1       Introduction

Classic tunneling methods envisaged for IPv6 transition operate by
sending IPv6 packets as payload of IPv4 packets; the 6to4 proposal
proposes automatic discovery in this context. A problem with these
methods is that they don't work when the IPv6 candidate node is
isolated behind a Network Address Translation device: NAT are
typically not programmed to allow the transmission of arbitrary
payload types; even when they are, the local address cannot be used
in a 6to4 scheme. 6to4 will work with NAT if the NAT and 6to4 router
functions are in the same box; we want to cover the relatively
frequent case when the NAT cannot be readily upgraded to provide a
6to4 router function.

A possible way to solve the problem is to rely on a set of "tunnel

Huitema                                                      [Page  1]


INTERNET DRAFT               Shipworm                    July 25, 2001

brokers." There are however limits to any solution that is based on
such brokers: the quality of service is not very good, since the
traffic follows a "dog leg" route from the source to the broker and
then the destination; the broker has to provide sufficient
transmission capacity to relay all packets and thus suffers a high
cost. For these two reasons, we tend to prefer solutions that allow
for "automatic tunneling", i.e. let the packets follow a direct path
to the destination.

The automatic tunneling requirement is indeed at odds with some of
the specificities of NATs. Establishing a direct path supposes that
the IPv6 Candidate can retrieve a "globally routable" address that
results from the translation of its local address by one or several
NATs; it also supposes that we can find a way to bypass the various
"per destination protections" that many NATs implement. In this
memo, we will explain how IPv6 candidates located behind NATs can
enlist the help of "v6 UDP routers" to learn their "global address"
and to obtain connectivity.

2       Definitions

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 [RFC2119].

This specification uses the following definitions:

2.1     Shipworm service

The transmission of IPv6 packets over UDP, as defined in this memo.

2.2     Shipworm Client

A node that has some access to the IPv4 Internet and that wants to
gain access to the IPv6 Internet. This node may behave either as an
IPv6 host or as an IPv6 router.

2.3     Shipworm Server

A node that has access to the IPv4 Internet through a globally
routable address, and that is used as a helper to provide IPv6
connectivity to Shipworm Client. The node is also reachable through
the Shipworm IPv4 anycast address.

2.4     Shipworm relay router

An IPv6 router that can receive traffic destined to Shipworm clients
and forward it using the Shipworm service.

2.5     Shipworm IPv6 service prefix

A 16 bit IPv6 addressing prefix, whose value is XXXX::/16. (TBD

Huitema                                                      [Page  2]


INTERNET DRAFT               Shipworm                    July 25, 2001

IANA)

2.6     Shipworm IPv4 anycast prefix

An IPv4 address prefix, whose value is x.x.x.0/24. (TBD IANA)
This prefix is announced in the IPv4 routing tables.

2.7     Shipworm IPv4 anycast address

An IPv4 address whose value is x.x.x.y, where "x.x.x" is the 24 bit
Shipworm IPv4 anycast prefix. (TBD IANA)
IPv4 Packets sent to this address are directed to the nearest
Shipworm server.

2.8     Shipworm UDP port

An UDP port number at which Shipworm Servers are waiting for
packets. The value of this port is PPPP. (TBD IANA)

2.9     Shipworm bubble

A packet sent over UDP by a Shipworm agent in order to trigger a
side effect in the NAT.

2.10    Shipworm Discard port

An UDP port number that is used as the destination of Shipworm
bubbles. The normal value for that port number is 9, i.e. the port
number reserved by IANA for the discard service.

2.11    Shipworm service port

The port over which the Shipworm client sends Shipworm packets. This
port is attached to one of the client's IPv4 interfaces. The IPv4
address may or may not be globally routable, as the client may be
located behind one or several NAT.

2.12    Shipworm mapped address and Shipworm mapped port

A global IPv4 address and a UDP port that results from the
translation by one or several NAT of the IPv4 address and UDP port
of a client's Shipworm service port. The client learns these values
through the Shipworm protocol described in this memo.

2.13    Shipworm IPv6 client prefix

A global scope 64 bit IPv6 prefix composed from the Shipworm IPv6
service prefix, the Shipworm mapped address and Shipworm mapped
port.

2.14    Shipworm IPv6 address


Huitema                                                      [Page  3]


INTERNET DRAFT               Shipworm                    July 25, 2001

A Shipworm IPv6 address obtained by combining a Shipworm IPv6 client
prefix and a 64 bit node identifier.

2.15    Shipworm IPv6 anycast address

A global scope IPv6 address obtained by combining the Shipworm IPv6
service prefix, the Shipworm IPv4 anycast address, the Shipworm port
and a null 64 bit node identifier (i.e., all zeroes).

2.16    Shipworm Refresh Interval

The interval during which a Shipworm IPv6 Address is expected to
remain valid in the absence of "refresh" traffic. For a client
located behind a NAT, the interval depends on configuration
parameters of the local NAT, or in fact of the combination of NATs
on the path to the Shipworm server. By default, clients assume an
interval value of 30 seconds; a longer value may be determined by
local tests, described in section 4.

3       Model, requirements

The Shipworm service requires the cooperation of three kinds of
actors: Shipworm clients, who want to use IPv6 despite being located
behind a NAT, Shipworm servers who will facilitate the service, and
Shipworm relays that provide for the interconnection between the
service and the "native IPv6 Internet."

In order to enable the service, the Shipworm servers must have an
unencumbered IPv4 connection, i.e. they must have a global IPv4
address. In fact, these servers must be dual homed, capable of
receiving packet on a specific, topology dependent, IPv4 address,
and also of receiving packets on the generic "Shipworm anycast IPv4
address."

The Shipworm routers must be connected to the IPv6 Internet and must
participate in IPv6 routing; they must be able to announce
reachability over IPv6 of the "Shipworm service IPv6 prefix." They
must then be able to relay packets over IPv4 UDP towards Shipworm
clients. It is very sensible to combine the functions of Shipworm
server and Shipworm relay in a single box.

The primary role of the servers is to enable the NAT traversal. The
service is designed in such a way that, when NAT traversal is
guaranteed, packets can flow on a direct path between source and
destination, without necessarily involving a relay by a Shipworm
server.

3.1     Robustness requirement

The Shipworm service is designed primarily for robustness: packets
are carried over UDP in order to cross as many NAT implementations
as possible. The servers are designed to be stateless, which means

Huitema                                                      [Page  4]


INTERNET DRAFT               Shipworm                    July 25, 2001

that they can easily be replicated. We expect indeed to find many
such servers replicated at multiple Internet locations.

3.2     Protection against denial of service attacks

Shipworm servers will act as a relay for IPv6 packets. Improperly
designed packet relays can be used by denial of service attackers to
hide their address, making the attack untraceable. The shipworm
service must include adequate protection against such misuse.

3.3     Non requirement of permanent addresses

Our design objective is that any node that has obtained a legitimate
IPv4 connection, even behind a NAT, can obtain a globally reachable
IPv6 address. We want to achieve this objective in the most
automatic manner, without requiring any explicit configuration:
explicit configuration is easy to manage by sophisticated users, but
the experience shows that it can be an insurmountable hurdle for
novice users.

The absence of explicit configuration excludes another potential
requirement, that nodes obtain a "permanent" address: such permanent
assignments require that nodes provide explicit credentials when
they connect to the network, which in turn implies explicit
management of these credentials.

The absence of permanent addresses can be palliated by "name
services" or "rendezvous services" through which the node can
publish its address of the moment to its peers; for example, the
nodes can be
When permanent addresses are required, they can be obtained and
managed by other means; in particular, the Shipworm Address can be
used as a "care of" address in a Mobile IPv6 service.

4       Description of the solution

The Shipworm service is realized by having clients interact with
"Shipworm servers" through the Shipworm service protocol.

The Shipworm server is designed to be stateless. It waits for
Shipworm requests or test requests on the Shipworm service and
Shipworm test ports, and processes by sending a response to the
adequate address and port; it waits for IPv6 packets on the Shipworm
relay port, and forwards them to the adequate IPv4 address and UDP
port.

4.1     Message formats

4.1.1   Shipworm IPv6 addresses

Shipworm IPv6 addresses are composed of four components:


Huitema                                                      [Page  5]


INTERNET DRAFT               Shipworm                    July 25, 2001

   +------+------------+----+-----------------------------+
   |Prefix|IPv4 address|Port|       Node identifier       |
   +------+------------+----+-----------------------------+

The 16 bit prefix is the "Shipworm IPv6 Prefix."

The next 32 bits contain a globally routable IPv4 address.

The next 16 bits contain a port number associated with that address.

The last 64 bits contain a node identifier.

4.1.2   Shipworm IPv6 packets encapsulation

Shipworm IPv6 packets are transmitted as UDP packets [RFC768] within
IPv4 [RFC791].  The source and destination IP addresses and UDP port
take values that are specified in this section.

4.1.3   Maximum Transmission Unit

Since Shipworm uses UDP as an underlying transport, a Shipworm
Maximum Transfer Unit (MTU) could potentially be as large as the
payload of the largest valid UDP datagram (65527 bytes).  However,
since Shipworm packets can travel unto unpredictable path over the
Internet, it is best to contain this MTU to a small size, in order
to minimize the effect of packet fragmentation and reassembly. The
default link MTU assumed by a host, and the link MTU supplied by a
Shipworm server during Router Advertisement SHOULD normally be set
to the minimum IPv6 MTU size of 1280 bytes [RFC2640].

Shipworm implementations SHOULD NOT set the "do not fragment" (DF)
bit of the encapsulating IPv4 header.

4.1.4   Shipworm bubble

A Shipworm bubble is a minimal UDP packet sent to a specific
destination to "prime" a NAT for later accepting packets from this
destination. The bubble has the following parameter:

- IPv4 source address: the Shipworm mapped address of the sender

- IPv4 destination address: the IPv4 address of the target

- UDP source port: the Shipworm mapped port of the sender

- UDP destination port: the Shipworm mapped port of the target.

- UDP payload: a minimal IPv6 packet, as follow

- IPv6 source: the Shipworm IPv6 address of the sender

- IPv6 destination: the Shipworm IPv6 address of the target

Huitema                                                      [Page  6]


INTERNET DRAFT               Shipworm                    July 25, 2001

- IPv6 payload type: 59 (No Next Header, as per [RFC2460])

- IPv6 payload length: 0

4.2     Shipworm Client specification

A Shipworm client expects to exchange IPv6 packets through an UDP
port, the Shipworm service port. The client will maintain the
following variables that reflect the state of the Shipworm service:

- Shipworm connectivity status,
- Mapped address and port number of the Shipworm service port,
- Shipworm IPv6 prefix associated with the Shipworm service port,
- Shipworm IPv6 address or addresses derived from the prefix,
- Date and time of the last interaction with the Shipworm server,
- Shipworm Refresh Interval,
- List of recent Shipworm peers.

Before sending any packets, the client must perform the Shipworm
qualification procedure, which determines the Shipworm connectivity
status, the mapped address and port number, and the Shipworm IPv6
prefix. If the qualification is successful, the client may use the
Shipworm service port to transmit and receive IPv6 packets,
according to the transmission and reception procedures; these
procedures use the "list of recent peers". For each peer, the list
contains:

- The mapped IPv4 address and mapped UDP port of the peer,
- The date and time of the last reception from the peer,
- The date and time of the last transmission to the peer,
- The number of bubbles transmitted to the peer.

The list of peers is used to "optimize" the transmission of IPv6
packets by using a "direct path" for the recently active peers. The
list of peers could grow over time. Clients should implement a list
management strategy, such as for example deleting the least recently
used entries. Clients should make sure that the list has a
sufficient size, so that most traffic goes over the "direct path."

The client must regularly perform the maintenance procedure in order
to guarantee that the Shipworm service port remains usable; the need
to use this procedure or not depend on the delay since the last
interaction with the Shipworm server. The refresh procedure takes as
a parameter the "shipworm refresh interval". This parameter is
initially set to 30 seconds; it can be updated as a result of the
optional "interval determination procedure."

4.2.1   Qualification procedure

The purpose of the qualification procedure is to establish the
status of the local IPv4 connection, and to determine the Shipworm

Huitema                                                      [Page  7]


INTERNET DRAFT               Shipworm                    July 25, 2001

IPv6 client prefix of the local Shipworm interface. The procedure
starts when the service is in the "initial" state, and results in a
"qualified" state if successful, in an "off-line" stage if
unsuccessful.

          /---------\
          | Initial |
          \---------/
               |
          +----+----+
          | Start   |<------+
          +----+----+       |
               |            |
               v            |
          /---------\ Timer |
          |Starting |-------+ N attempts   /----------\
          \---------/--------------------->| Off-line |
               | Response                  \----------/
               |
               V
          /---------\
          |Qualified|
          \---------/

Initially, the Shipworm connectivity status is set to "Initial".
When the interface is initialized, the system first performs the
"start action" by sending a Router Solicitation Message, as defined
in [RFC2461]. The IPv6 destination of the RS is the Shipworm IPv6
anycast address; the IPv6 source is the unspecified address; the
packet will be sent over UDP to the Shipworm anycast address and
Shipworm service port. The connectivity status moves then to
"Starting".

In the starting state, the client waits for a router advertisement
from the Shipworm server. If no response comes within a time-out,
the client should repeat the start action, by resending the Router
Solicit packet. If no response has arrived after N=4 repetitions,
the client concludes that it cannot use UDP, and that the Shipworm
service is not available; the status is set to "Off-line."

If a response arrives, the client checks that the response is a
valid router advertisement as defined in [RFC2461], and that it
contains exactly one advertised Prefix Information parameter. This
prefix should be a valid Shipworm IPv6 client prefix:

- the first 16 bits contain the Shipworm service TLA,

- the next 32 bits are the client's Shipworm mapped address,

- the next 16 bits are the client's Shipworm mapped port.

The source address of the Router Advertisement is the Shipworm IPv6

Huitema                                                      [Page  8]


INTERNET DRAFT               Shipworm                    July 25, 2001

address of the Shipworm server. This address must be built using an
IPv4 unicast address of the server, and a port number at which the
server is waiting for packets.

If the response is a valid router advertisement, from a valid
Shipworm source address, and containing a valid Shipworm address
prefix, the client should build a Shipworm IPv6 address using the
Shipworm IPv6 client prefix learned from the RA and locally selected
identifier. The client is qualified, and can start using the
Shipworm service.

4.2.2   Packet reception

The Shipworm client receives packet over the Shipworm interface. The
role of the packet reception procedure, besides receiving packets,
is to maintain the date and time of the last interaction with the
Shipworm server, and the "list of recent peers." Each entry in the
list contains an IPv4 address, a UDP port, and a date and time.

When a UDP packet is received, the Shipworm client examines the IPv4
source address and port number from which the packet is received. If
these values match the Shipworm IPv4 anycast address and Shipworm
port, the client updates the "date and time of the last interaction
with the Shipworm server" to the current data and time.

If the values are different, the client examines the IPv6 source
address of the encapsulated packet. If the IPv6 source address is
not a valid Shipworm IPv6 address, or if the IPv4 address embedded
in the Shipworm address is not in the format of a global unicast
address, the packet MUST be silently discarded. If the source IPv6
address is a Shipworm IPv6 address, the client extracts the "peer
IPv4 address" and "peer UDP port" corresponding to that address. If
these addresses and port don't match the source IP address and
source UDP port of the packet, the packet MUST be silently rejected;
if they match the client has received a direct packet from a peer.
If the address and port pair are already represented in the "list of
recent peers", the client MUST update the data and time of last
reception from this peer. If the pair is not yet represented, the
client MUST create a new list entry for the pair, setting the last
reception date do the current date and time, the last transmission
date to 30 seconds before the current date, and the number of bubble
to zero.

Whatever the IPv4 source address and UDP source port, the client
that receives an IPv6 packet from a Shipworm IPv6 source address MAY
start sending a Shipworm Bubble towards that target, as specified in
section 4.2.5.

4.2.3   Packet transmission

When a Shipworm client has to transmit a packet over a Shipworm
interface, it examines the destination IPv6 address. If the

Huitema                                                      [Page  9]


INTERNET DRAFT               Shipworm                    July 25, 2001

destination is not a Shipworm IPv6 address, the packet is posted
over UDP to the Shipworm IPv4 anycast address and Shipworm UDP port.

If the destination is a Shipworm IPv6 address, the client extracts
the "peer IPv4 address" and "peer UDP port" corresponding to that
address. Before sending the packet, the Shipworm Client MUST check
that the IPv4 destination address is in the format of a global
unicast address; if this is not the case, the packet MUST be
silently discarded.

If there is an entry for this address and port pair in the list of
recent Shipworm peers, and if the date and time associated with that
list entry is less that 30 seconds from the current time the packet
SHOULD be send over UDP directly to the specified "peer IPv4
address" and "peer UDP port", and the transmission date for that
list entry should be set to the current time.

If there is no entry in the list, or if the date and time associated
to the entry is too old, the client should then send the IPv6 packet
over IPv4 UDP to the Shipworm IPv4 anycast address and Shipworm UDP
port; the client MAY start sending a Shipworm Bubble towards the
destination IPv6 address, as specified in section 4.2.5.

4.2.4   Maintenance

The Shipworm client must ensure that the mappings that it uses
remain valid. It does so by checking that packets are regularly
received from the Shipworm server.

At regular intervals, the client must check the "date and time of
the last interaction with the Shipworm server", to ensure that at
least one packet has been received in the last Shipworm Refresh
Interval. If this is not the case, the client SHOULD send a router
solicitation message to the Shipworm IPv6 Anycast address. When the
router advertisement is received, the client MUST check that the
advertised prefix corresponds to the current Shipworm service
prefix. If this is not the case, the mapping has changed; the client
MUST check that the new prefix is valid, as specified in the
qualification procedure. It should then invalidate the addresses
derived from the old prefix.

4.2.5   Sending Shipworm Bubbles

The Shipworm client may decide to send a bubble towards another
Shipworm client, either after a packet reception or after a
transmission attempt, as explained in sections 4.2.1 and 4.2.2.

When a Shipworm client attempts to send a bubble, it extracts the
mapped IPv4 address and mapped UDP port from the Shipworm IPv6
address of the target. It then checks whether there is already an
entry for this address and port pair in the current list. If the
pair is not yet represented, the client MUST creates a new list

Huitema                                                      [Page 10]


INTERNET DRAFT               Shipworm                    July 25, 2001

entry for the pair, setting the last reception date and the last
transmission date to 30 seconds before the current date, and the
number of bubbles to zero.

The client MUST NOT send a bubble if the last transmission date and
time is less than 10 seconds before the current date and time, or if
the number of transmitted bubbles is larger than 4 and the last
reception date and time is less than 300 seconds before the current
date and time. In the other cases, the client MAY proceed with the
transmission of the bubble, which MUST be composed as specified in
section 4.1.4. When transmitting the bubble, the client MUST update
the last transmission date and time to that peer, and must also
increment the number of transmitted bubbles.

4.2.6   Optional Refresh Interval Determination Procedure

In addition to the regular client resources described in the
beginning of this section, the refresh interval determination
procedure uses an additional UDP port, the Shipworm secondary port,
and the following variables:

- Shipworm secondary connectivity status,
- Mapped address and port number of the Shipworm secondary port,
- Shipworm secondary IPv6 prefix associated with the secondary port,
- Shipworm secondary IPv6 address derived from this prefix,
- Date and time of the last interaction on the secondary port,
- Maximum Shipworm Refresh Interval.
- Candidate Shipworm Refresh Interval.

The secondary connectivity status, mapped address and prefix are
determined by running the qualification procedure on the secondary
port. When the client uses the interval determination procedure, the
qualification procedure MUST be run for the secondary port
immediately after running it on the service port. If the secondary
qualification fails, the interval determination procedure will not be
used, and the interval value will remain to the default value, 30
seconds. If the secondary qualification succeeds, the maximum refresh
interval is set to 960 seconds, and the candidate shipworm refresh
interval is set to 60 seconds, i.e. twice the shipworm refresh
interval. The procedure is then performed at regular intervals, until
it concludes:

1) wait until the candidate refresh interval is elapsed after the
last interaction on the secondary port;

2) send a Shipworm Bubble to the Shipworm secondary IPv6 address,
through the service port.

3) wait for reception of the bubble on the secondary port. If a timer
of 2 seconds elapses without reception, repeat step 2 at most three
times. If there is still no reception, the candidate has failed; if
there is a reception, the candidate has succeeded.

Huitema                                                      [Page 11]


INTERNET DRAFT               Shipworm                    July 25, 2001

4) if the candidate has succeeded, set the shipworm refresh interval
to the candidate value, and set a new candidate value to the minimum
of twice the new refresh interval, or the average of the refresh
interval and the maximum refresh interval.

5) if the candidate has failed, set the maximum refresh interval to
the candidate value. If the current refresh interval is larger than
or equal to 75% of the maximum, the determination procedure has
concluded; otherwise, set a new candidate value to the average of the
refresh interval and the maximum refresh interval.

6) if the procedure has not concluded, perform the maintenance
procedure on the secondary port, which will reset the date and time
of the last interaction on the secondary port, and may result in the
allocation of a new Shipworm secondary address; this would not affect
the values of the refresh interval, candidate interval or maximum
refresh interval.

The secondary port MUST NOT be used for any other purpose than the
interval determination procedure. If a spurious packet is received on
the secondary port, the client SHOULD repeat the maintenance
procedure on this port and reset the date and time of the last
interaction on the secondary port.

4.3     Shipworm Server specification

The Shipworm server is designed to be stateless. The Shipworm server
waits for incoming UDP packets at the Shipworm Relay Port. The
incoming packets may be sent to either the Shipworm IPv4 Anycast
Address, or to the specific unicast address of the Shipworm Server.

The Shipworm server acts as an IPv6 router. As such, it will receive
Router Solicitation messages, to which it will respond with router
advertisement packets as explained in the "router solicitation"
procedure; it may also receive other packets, for example ICMP
packets, which are processed according to the IPv6 specification.

The Shipworm service may be made available to neighboring Autonomous
Systems by advertising the Shipworm IPv4 Anycast prefix in the IPv4
EGP, as specified in 4.3.4. The domain managers must be ready to
perform fault isolation as specified in 4.3.5.

4.3.1   Processing of Shipworm IPv6 packets

Upon reception of a packet on the Shipworm port, the Shipworm server
will first check that the UDP payload contains a valid IPv6 packet;
if this is not the case, the packet will be silently discarded.

Before processing the packet, the Shipworm server MUST check the
validity of the encapsulated IPv6 source address, the IPv4 source
address and the UDP source port:

Huitema                                                      [Page 12]


INTERNET DRAFT               Shipworm                    July 25, 2001

1)      If the IPv4 source address does not belong to a range of IPv4
addresses for which the Shipworm server is providing service, the
server MAY silently discard the packet.

2)      If the IPv4 source address is not in the format of a global
unicast address, the packet MUST be silently discarded.

3)      If the IPv6 source address is a Shipworm IPv6 anycast address, if
the IPv4 source address and UDP source port match the values
embedded in the IPv6 source address, and if the IPv4 source
address the packet MUST be accepted.

4)      If the IPv6 source address is the IPv6 unspecified address, and
if the IPv6 source address is the Shipworm IPv6 anycast address,
the packet MUST be accepted.

5)      In all other cases, the packet MUST be rejected.

The Shipworm server will then check the IPv6 destination address of
the encapsulated IPv6 packet.

If the IPv6 destination address is either the Shipworm IPv6 anycast
address or the Shipworm IPv6 address associated to the local
interface, the Shipworm server processes the packet; it may in
particular have to process "router solicitation" messages.

If the IPv6 destination address is a valid Shipworm IPv6 address,
the Shipworm Server MUST check that the IPv4 destination address is
in the format of a global unicast address; if this is not the case,
the packet MUST be silently discarded. If the address is valid, the
Shipworm server encapsulates the IPv6 packet in a new UDP datagram,
in which the following parameters are set:

- The destination IPv4 address is derived from the IPv6 destination.

- The source IPv4 address is the Shipworm IPv4 anycast address.

- The destination UDP port is derived from the IPv6 destination.

- The source UDP port is set to the Shipworm Relay Port.

If the destination address is not a Shipworm IPv6 address, the
packet should be relayed to the IPv6 Internet using regular IPv6
routing.

4.3.2   Processing of router solicitations

When the Shipworm server receives a router solicitation message (RS,
[RFC2641]), it retains the IPv4 address and UDP port from which the
solicitation was received; these become the Shipworm mapped address
and Shipworm mapped port of the client. The router uses these values

Huitema                                                      [Page 13]


INTERNET DRAFT               Shipworm                    July 25, 2001

to compose a Shipworm IPv6 Prefix.

The Shipworm server responds to the router solicitation by sending a
Router Advertisement [RFC2641]. The router advertisement MUST
advertise the Shipworm IPv6 prefix composed from the mapped address
and mapped port. The IPv6 destination address is normally set to the
IPv6 source address of the RS; if that address was the unspecified
address, the IPv6 destination should be set to the Shipworm IPv6
anycast address. The Router Advertisement must be sent over UDP to
the Shipworm mapped address and Shipworm mapped port of the client;
the IPv4 source address and UDP source port should be set to the
Shipworm IPv4 anycast address and Shipworm Port. Before sending the
packet, the Shipworm Router MUST check that the IPv4 destination
address is in the format of a global unicast address; if this is not
the case, the packet MUST be silently discarded.

Before relaying packets received on the Shipworm port, the Shipworm
server MUST perform the security tests described in section 7.

4.3.3   Processing of bubbles

Shipworm servers may receive Shipworm Bubbles; these messages are
silently discarded.

4.3.4   Advertising of the Shipworm IPv4 anycast prefix

If the managers of an IPv4 autonomous domain that includes Shipworm
servers want to provide the Shipworm service to neighbor Autonomous
Systems, they MAY advertise reachability of the Shipworm IPv4
anycast prefix using the EGP of their IPv4 autonomous system, as if
it where a connection to an external network. When this
advertisement is done using BGP, the initial AS path MUST contain
the AS number of the announcing AS.  The AS path should also include
an indication of the actual router providing the service; there is a
suggestion to perform this function by documenting the specific IPv4
address of the Shipworm server in the BGP aggregator attribute of
the path; further work is needed on this point.

Any Shipworm server corresponding to this specification SHOULD
include a monitoring function, to check that the Shipworm service is
operational.  The route leading to the Shipworm IPv4 anycast prefix
MUST NOT be announced if the service is not operational.

4.3.5   Fault isolation

When an error is reported, e.g., by a user, the domain manager
should be able to find the specific Shipworm Server that is causing
the problem.

The first step of fault isolation is to retrieve the specific IPv4
address of the server used by the user.  If the server is located
within the domain, this information will have to be retrieved from

Huitema                                                      [Page 14]


INTERNET DRAFT               Shipworm                    July 25, 2001

the IGP tables.  If the service is obtained through a peering
agreement with another domain, the information will be retrieved
from the EGP data, e.g., the BGP path attributes.

The second step is obviously to perform connectivity tests using the
specific IPv4 address.

4.4     Shipworm Relay specification

Shipworm relays are IPv6 routers that advertise reachability of the
Shipworm service IPv6 prefix through the IPv6 routing protocols.
Shipworm relays will receive IPv6 packets bound to Shipworm clients.
Shipworm routers MUST be able to use the Shipworm IPv4 anycast
address as the source address of UDP packets.

The Shipworm relay that receive packets bound to a Shipworm IPv6
address will transmit the IPv6 packets directly to the target
Shipworm client: the IPv4 destination address and UDP destination
port are derived from the destination Shipworm IPv6 address; the
IPv4 source address and UDP source port are set to the Shipworm IPv4
anycast address and Shipworm UDP port.

It is obviously desirable to combine the functions of Shipworm relay
and Shipworm server, but this is not mandatory.

5       Discussion of the solution

5.1     How can we learn the address?

In order to explain how Shipworm works, we will use an hypothetical
example: a shipworm client is located at the private IP address
10.0.0.2 in a private network; the NAT connecting this network to
the public Internet responds to the local address 10.0.0.1 and is
visible as the public address 9.0.0.1.

                                          .-----------------------
                                          |  Private network
                .--.                    .-----.     .----------.
               (IPv4)  src=9.0.0.1:4096 | NAT |     | Shipworm |
             (Internet)<--------------  | BOX | <-- |  Client  |
               (    )   (UDPv4 tunneled |     |     '----------'
                '--'         IPv6)      '-----'       10.0.0.2:1234
                 |                9.0.0.1 | 10.0.0.1
                 |                        |
                 |                        |
                 V                        |
          .--------------.                '-----------------------
          |   Shipworm   |
          |   Server     |
          '--------------'
            [IPv4-anycast]


Huitema                                                      [Page 15]


INTERNET DRAFT               Shipworm                    July 25, 2001

When the Shipworm client is turned up, it sends an IPv6 router
solicitation over UDP to the IPv4 anycast address of the Shipworm
server, using the source address and ports 10.0.0.2:1234. The NAT
captures the packet, establishes a mapping, and changes the source
address and port to 9.0.0.1:4096. (These values are indeed just
examples.)

The Shipworm receives the packet and notes the source address. It
uses it to construct a Shipworm IPv6 client prefix:

         PREF:0900:0001:2860::/64

In this prefix, "PREF" is the 16 bit Shipworm IPv6 service prefix;
"0900:0001" is the hexadecimal notation of the IPv4 mapped address
"9.0.0.1"; and "2860" is the hexadecimal notation of the mapped port
"4096".

The router sends the router advertisement back over UDP to the
mapped IPv4 address 9.0.0.1:4096. The IPv4 packet is received by the
NAT, which has presumably remembered the mapping between this
external address and the private address and port pair,
10.0.0.2:1234; the NAT forwards the packet to the Shipworm client.
Further packets coming from the Internet will use the same mapping.

5.2     Why do we have bubbles and lists of peers?

Experience shows that the implementers of NAT products can adopt
widely different treatments of UDP packets:

1. Some implement the simplest solution, which is to map an internal
UDP port, defined by an internal address and a port number on the
corresponding host, to an external port, defined by a global address
managed by the NAT and a port number valid for that address. In this
simple case, the mapping is retained as long as the port is active,
and is removed after an inactivity timer. As long as the mapping is
retained, any packet received by the NAT for the external port is
relayed to the internal address and port.

2. Some implement a more complex solution, in which the NAT not only
establishes a mapping for the UDP port, but also maintains a list of
external hosts to which traffic has been sent from that port. The
packets originating from third party hosts to which the local host
has not yet sent traffic are rejected.

3. Instead of keeping just a list of authorized hosts, some NAT
implementations keep a list of authorized host and port pairs. UDP
packets coming from remote addresses are rejected if the internal
host has not yet sent traffic to the outside host and port pair.

4. Finally, some NAT map the same internal address and port pair to
different external address and port pairs, depending on the address
of the remote host.

Huitema                                                      [Page 16]


INTERNET DRAFT               Shipworm                    July 25, 2001

Measurement campaigns and studies of documentations have shown that
most NAT implement either option 1 or option 2. The combination of
"bubbles" and "list of peers" allows us to cross all types of NAT,
including those of type 3 and 4; we optimize the direct transmission
between NAT of types 1 and 2.

5.3     Could we make do with fewer bubbles?

It is true that if we knew the type of the NAT at each end, we could
diminish the amount of bubbles that we send. For example, a Shipworm
client behind a type-1 NAT never needs to send or receive bubbles:
the NAT will let packet through from any destination. Similarly, a
Shipworm client behind a type 3 NAT should not bother sending
bubbles, since these bubbles will never have any effect on the NAT.
On the other end, bubbles are useful for type-2 NAT, which according
to our sample represent about half the implementations.

A problem with any "smart" approach is that it requires a
"characterization" procedure for the local NAT, which is complex and
possibly error prone. More importantly, any smart approach
introduces failure modes. A particularly nasty problem arises when
two clients are located behind the same NAT; this can happen when
the NAT is installed by an ISP. In this case, even if the NAT is
"type-1", we may have a problem, as exposed in the following
diagram:

                                          .-----------------------
                                          |  Private network
                .--.   src=9.0.0.1:4096 .-----.     .----------.
               (IPv4)  src=9.0.0.1:4097;| NAT |     | Shipworm |
             (Internet)<--------------  | BOX | <-- | Client-1 |
               (    )   (UDPv4 tunneled |     | <.  '----------'
                '--'         IPv6)      '-----'  |    10.0.0.2:1234
                 |                9.0.0.1 |      |  .----------.
                 |                        |      |  | Shipworm |
                 |                        |      '- | Client-2 |
                 V                        |         '----------'
          .--------------.                |           10.0.0.3:1234
          |   Shipworm   |                '-----------------------
          |   Server     |
          '--------------'
            [IPv4-anycast]

The first client uses the private address and port 10.0.0.2:1234,
which is mapped to 9.0.0.1:4096 by the NAT; the second client uses
10.0.0.3:1234, mapped to 9.0.0.1:4097. If the first client tries to
send a direct packet to the second client, that packet will be
routed to the address 9.0.0.1:4097, i.e. to the external IP address
of the local NAT. What happens next is everybody's guess: some NAT
may do the right thing, some may drop the packet.


Huitema                                                      [Page 17]


INTERNET DRAFT               Shipworm                    July 25, 2001

Our algorithm is designed to privilege robustness: unless the client
knows otherwise, the packets will always be sent through a Shipworm
server, and will always be received through the single "pin-hole"
that allows communication between the Shipworm client and the
Shipworm anycast address. The packets will only be sent on the
direct path if the client actually received a packet or a bubble on
that direct path, demonstrating the existence of a chain of mappings
on all the NAT located between the Shipworm peers.

The algorithm for sending bubbles is designed to be conservative: we
only send bubbles when necessary, and limit the transmission rate
when we suspect that the sending of the bubbles is useless. In a
type 3 NAT, we will send at most four bubbles to a destination, and
then we will observe a silence period of 300 seconds.

5.4     Do we need the Refresh Interval Determination Procedure?

When the client is initialized, the Shipworm Refresh Interval is set
to 30 seconds. This value is lower than the minimum interval found
necessary in a measurement campaign conducted by a Microsoft team in
January 2001; the measured values ranged between 45 seconds and 15
minutes. There is always a risk that some NAT manufacturers program
some ever smaller time to live intervals for their mappings, but
doing so would break many applications and would probably generate
uproar from Internet users. By picking a conservatively small value,
we guarantee that the service will work with most NATs.

On the other hand, picking a conservative value increases the
maintenance traffic and the load on the Shipworm servers. We know
that in many cases interval as large as 5 or 10 minutes would be
adequate. The determination procedure is designed to quickly find
whether a larger value is adequate.

5.5     Why do we need an anycast address?

The use of an IPv4 anycast address to locate the Shipworm server has
many advantages. An obvious one is that it solves configuration
issues, making it very easy for the Shipworm client to locate the
nearest server. A less obvious one is the interaction with the NAT.
The type 2 and type 3 NAT check that the packet comes from a source
with which the local client already interacted; by using a single
unicast address as the source address of all UDP packets coming from
all Shipworm servers, we guarantee that the "pin-hole in the NAT"
can be used by all of these servers.

The use of an anycast address is facilitated by the stateless
implementation of Shipworm servers: since the service is performed
in exactly the same way by any server, it does not matter whether
anycast routing carries the packet to a specific server or another.

Scaling, failover and access control


Huitema                                                      [Page 18]


INTERNET DRAFT               Shipworm                    July 25, 2001

The consequences of the use of anycast addresses on access control,
scaling, and failover are discussed in [RFC3068] in the context of
the "6to4" service.

Using an anycast address and stateless servers has beneficial
consequences on scaling. It is possible to start deployment with a
small number of Shipworm servers, reachable across the Internet. It
is then possible to deploy more servers across the Internet, as
demand increases.

Shipworm packets will be naturally forwarded to the nearest server,
as specified in the IPv4 routing tables. If a Shipworm server
somehow breaks, or loses connectivity to the v6 Internet, it will
cease to advertise reachability of the Shipworm IPv4 prefix prefix.
At that point, the local IGP will automatically compute a route
towards the "next best" Shipworm server.  We expect that adequate
monitoring tools will be used to guarantee timely discovery of
connectivity losses.

Only those ASes that run Shipworm Servers and are willing to provide
access to the v6 network announce a path to the Shipworm IPv4
anycast prefix.  They can use the existing structure of peering and
transit agreements to control to whom they are willing to provide
service, and possibly to charge for the service.


5.6     When to use Shipworm?

Shipworm is designed to robustly enable IPv6 traffic through NAT,
and the price of robustness is a reasonable amount of overhead, due
to UDP encapsulation, transmission of bubbles, and relaying of
packets through the Shipworm servers. Nodes that want to connect to
the IPv6 Internet should only use the Shipworm service as a "last
resort" option: they should prefer using direct IPv6 connectivity if
it is locally available, and they should prefer using the less
onerous "6to4" encapsulation if they can use a global IPv4 address.

5.7     What about firewalls?

The Shipworm service is not designed to "transparently traverse
firewalls." A local administrator can decide to allow or disallow
the service, by programming the local firewall to authorize or deny
traffic on the Shipworm UDP port.

5.8     Why do we use the name Shipworm?

A "Shipworm" is a little saltwater critter that is common in the
harbors of warm seas and that digs holes in immersed wood pieces,
such as boat hulls or posts. The animal is not an actual worm - it
is a mollusk. The Shipworm service also digs holes, albeit in NATs,
not in wood.


Huitema                                                      [Page 19]


INTERNET DRAFT               Shipworm                    July 25, 2001

On one hand, one may think that the shipworm is a pretty nasty
animal. On the other hand, the animal only survives in relatively
clean and unpolluted water; its recent comeback in several Northern
American harbors is a testimony to their newly retrieved
cleanliness. The Shipworm service should, in turn, contributes to a
newly retrieved transparency of the Internet.

6       Future Work

Some - this is a second draft.

7       Security Considerations

The security considerations for using a dynamic encapsulation of
IPv6 over UDP are very similar to the implications of "6to4"
[RFC3056], which we partially reproduce here.

Implementors should be aware that, in addition to possible attacks
against IPv6, security attacks against IPv4 must also be considered.
Use of IP security at both IPv4 and IPv6 levels should nevertheless
be avoided, for efficiency reasons.  For example, if IPv6 is running
encrypted, encryption of IPv4 would be redundant except if traffic
analysis is felt to be a threat.  If IPv6 is running authenticated,
then authentication of IPv4 will add little.  Conversely, IPv4
security will not protect IPv6 traffic once it leaves the Shipworm
service. Therefore, implementing IPv6 security is required even if
IPv4 security is available.

In contrast with the 6to4 default, Shipworm traffic will not be
accepted and decapsulated from any source from which regular IPv4
traffic is accepted: the service is designed to prevent malevolent
agent from using Shipworm servers for "laundering" a denial of
service attack. Shipworm packets are always sent from either the
Shipworm IPv4 anycast address, or from an IPv4 address and UDP port
that is strictly consistent with the encapsulated IPv6 source
address; this MUST be checked by servers and clients, as specified
in sections 4.2.2 and 4.3.1. We expect that only routers controlled
by Internet Service Providers will be authorized to use the anycast
address as a source address for UDP packets.

In any case, any Shipworm traffic whose source or destination
address embeds a mapped IPv4 address which is not in the format of a
global unicast address MUST be silently discarded by Shipworm
clients, servers, and routers as specified in sections 4.2.2, 4.2.3,
4.3.1, and 4.4.  Specifically, this means that IPv4 addresses
defined in [RFC1918], broadcast, subnet broadcast, multicast and
loopback addresses are unacceptable.

8       IANA Considerations

This memo documents a request to IANA to allocate a Shipworm IPv6
service prefix, a Shipworm IPv4 anycast prefix, a Shipworm IPv4

Huitema                                                      [Page 20]


INTERNET DRAFT               Shipworm                    July 25, 2001

anycast address and a Shipworm UDP port.

9       Copyright

The following copyright notice is copied from RFC 2026 [Bradner,
1996], Section 10.4, and describes the applicable copyright for this
document.

Copyright (C) The Internet Society July 12, 2001. All Rights
Reserved.

This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph
are included on all such copies and derivative works.  However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.

The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assignees.

This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

10      Intellectual Property

The following notice is copied from RFC 2026 [Bradner, 1996],
Section 10.4, and describes the position of the IETF concerning
intellectual property claims made against this document.

The IETF takes no position regarding the validity or scope of any
intellectual property or other rights that might be claimed to
pertain to the implementation or use other technology described in
this document or the extent to which any license under such rights
might or might not be available; neither does it represent that it
has made any effort to identify any such rights.  Information on the
IETF's procedures with respect to rights in standards-track and
standards-related documentation can be found in BCP-11.  Copies of
claims of rights made available for publication and any assurances
of licenses to be made available, or the result of an attempt made
to obtain a general license or permission for the use of such

Huitema                                                      [Page 21]


INTERNET DRAFT               Shipworm                    July 25, 2001

proprietary rights by implementers or users of this specification
can be obtained from the IETF Secretariat.

The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights which may cover technology that may be required to practice
this standard.  Please address the information to the IETF Executive
Director.

11      Acknowledgements

Many of the ideas in this memo are the result of discussions between
the author and Microsoft colleagues, notably Brian Zill, John Miller
and Rick Rashid. Several encapsulation details are inspired from
early work by Keith Moore. The example in section 5.1 was suggested
by Pekka Savola, and the discussion in 5.3 by Art Shelest.

12      References

[RFC768] J. Postel, "User Datagram Protocol", RFC 768, August 1980.


[RFC791] J. Postel, "Internet Protocol", RFC 791, September 1981.

[RFC1918] Y. Rekhter, B. Moskowitz, D. Karrenberg, G. J. de Groot,
E. Lear, "Address Allocation for Private Internets", RFC 1918,
February 1996.

[RFC2119] S. Bradner, "Key words for use in RFCs to Indicate
Requirement Levels", RFC 2119, March 1997.

[RFC2460] S. Deering, R. Hinden, "Internet Protocol, Version 6
(IPv6) Specification", RFC 2460, December 1998.

[RFC2461] T. Narten, E. Nordmark, W. Simpson, "Neighbor Discovery
for IP Version 6 (IPv6)", RFC 2461, December 1998.

[RFC3056] B. Carpenter, K. Moore, "Connection of IPv6 Domains via
IPv4 Clouds", RFC 3056, February 2001.

[RFC3068] C. Huitema, "An Anycast Prefix for 6to4 Relay Routers",
RFC 3068, June 2001.

13      Authors' Addresses

Christian Huitema
Microsoft Corporation
One Microsoft Way
Redmond, WA 98052-6399

Email: huitema@microsoft.com


Huitema                                                      [Page 22]