Shim6 Implementation Report : LinShim6
draft-barre-shim6-impl-00

Status of this Memo

By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79.

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.

This Internet-Draft will expire on August 8, 2008.

Abstract

LinShim6 is an implementation of the Shim6 and REAP protocols, on the Linux platform. This draft provides a brief description of the architecture and describes the current state of our implementation. For each feature of the protocols, its level of support is described. Protocol conformance is evaluated against [refs.shim6] (Bagnulo, M. and E. Nordmark, “Shim6: Level 3 Multihoming Shim Protocol for IPv6,” .) and [refs.reap] (Arkko, J. and I. van Beijnum, “Failure Detection and Locator Pair Exploration Protocol for IPv6 Multihoming,” .).

Table of Contents

1.  Introduction
2.  General architecture
    2.1.  Kernel patch
    2.2.  LinShim6 daemon
3.  RFC 2119 evaluation
    3.1.  Checks common to all control messages
    3.2.  I1 Message
    3.3.  R1 Message
    3.4.  I2 Message
    3.5.  R2 Message
    3.6.  R1bis, I2bis, Update Request and Update Acknowledgement
    3.7.  Keepalive and Probe Messages
    3.8.  Keepalive Timeout Option
    3.9.  Error messages
    3.10.  Message Options
    3.11.  Payload data
    3.12.  General requirements of the Shim6 draft
    3.13.  General requirements of the REAP draft
4.  Protocol conformance by feature
5.  Conclusion and further work
6.  Acknowledgments
7.  References
§  Authors' Addresses
§  Intellectual Property and Copyright Statements

1.  Introduction

LinShim6 has been developped from scratch at UCL (Belgium), and it is available at http://inl.info.ucl.ac.be/LinShim6. It has been used to evaluate the performance of REAP path exploration [refs.sigcomm] (Barré, S. and O. Bonaventure, “Improved Path Exploration in shim6-based Multihoming,” .). The architecture has been thought to be well integrated, easy to use and efficient. We define a heuristic that tries to avoid starting a Shim6 negotiation when the corresponding overhead would be too high. LinShim6 supports the base Shim6 protocol (negotiation and address rewriting) as well as failure detection and recovery. In terms of security, CGA support has been added recently (most of the code for the CGA module comes from the DoCoMo SEND project) and HBA will be supported soon as well.

Some features have not yet a real application and are not supported for this reason. They will be added as soon as a need for them arises. This is the case for the Forked Instance Identifier that is only useful if a socket API is implemented (such as the API defined in [refs.api] (Komu, M., Bagnulo, M., Slavov, K., and S. Sugimoto, “Socket Application Program Interface (API) for Multihoming Shim,” .)). The Locator Preference Option or the Keepalive Timeout option may only be used if the corresponding tuning capability is provided, either by the user or by an automated technique.

Other features are just absent for time reasons, and were omitted because they did not seem essential for a correct working of the protocol. Thus we still have in the TODO list features like locator list updates, Handling of ICMP error messages or context recovery.

In this document we use the terminology defined in section 2 of [refs.shim6] (Bagnulo, M. and E. Nordmark, “Shim6: Level 3 Multihoming Shim Protocol for IPv6,” .).

2.  General architecture

The LinShim6 implementation is made of a kernel patch and a user space daemon. The kernel patch adds support for shim6 negotiation trigger, address rewriting and Failure detection. The daemon is responsible for managing the whole Shim6 control plane (negotiation, path exploration). The kernel communicates with the user space daemon through the Netlink interface [refs.rfc3549] (Salim, J., Khosravi, H., Kleen, A., and A. Kuznetsov, “Linux Netlink as an IP Services Protocol,” .).

2.1.  Kernel patch

The negotiation trigger makes use of the NF_IP6_LOCAL_IN and NF_IP6_LOCAL_OUT netfilter hooks to listen to the packets travelling through the networking stack. A Shim6 negotiation is triggered when either 2 KB of data have been seen for a given address pair or the flow exists for one minute.

Address rewriting is implemented as an extension to the XFRM framework, originally designed for IPsec [refs.ipsec] (Kanda, M., Miyazawa, K., and H. Esaki, “USAGI IPv6 IPsec development for Linux,” .). The XFRM framework allows for dynamically adding a new sublayer in the Networking stack for some flows, according to a policy. Examples of already defined sublayers are the AH sublayer (Authentication Header) or the ESP sublayer (Encapsulating Security Payload). We define a new Shim6 sublayer. The policies responsible for directing packets to this new module are communicated from the daemon to the kernel, through Netlink, when a change in the locators is needed or a new Shim6 context is created. For outgoing packets, the policy has the form of a matching rule with the ULIDs. For Incoming packets that do not have the Shim6 extension header the same kind of matching rule is used. We also defined a matching rule based on the context tag, to be able to demultiplex tagged incoming packets.

Failure detection is performed inside the kernel for efficiency reasons : A timer must be started or stopped for each incoming of outgoing packets. We thus maintain a small REAP state in the XFRM states that stores the failure detection timers, and notifies the daemon when a keepalive must be sent or an exploration is to be started.

2.2.  LinShim6 daemon

The daemon is made of an infinite loop that listens to three kinds of events. First, Shim6 and REAP control messages are received through a raw socket. Second, Netlink messages provide information from the kernel, for example if a context must be created, a keepalive must be sent or an exploration must be started. Finally, messages can be received through a pipe where the other threads may write commands. Four threads are currently defined :

• XFRM : Listens to the XFRM events from the kernel. Currently only the state expiry event is used. It is generated when a kernel context has seen no traffic during more than 10 minutes. The result is that the daemon deletes the corresponding association.
• Timer : It maitains a timer queue and wakes up when any timer expires. It the asks the main thread to run the corresponding handling function.
• Information server : A simple telnet server that provides a convenient interface to the daemon.
• Main thread : Maintains all the critical states.

A more extensive description can be found in [refs.ring] (Barré, S. and O. Bonaventure, “Implementing SHIM6 using the Linux XFRM framework,” .) or in the pdf documentation provided with the LinShim6 package.

3.  RFC 2119 evaluation

In this section we detail the conformance of the LinShim6 implementation in terms of the RFC2119 [refs.rfc2119] (Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” .) terminology. Note that if a MUST is followed by "FEATURE NOT SUPPORTED", this means that the MUST has sense only if the feature exists. That is, the implementation is still conformant but does not implement the particular feature.

3.1.  Checks common to all control messages

A host MUST silently discard any received control message that does not statisfy all of the following validity checks :

• The Shim header length field is verified against the length of the IPv6 packet to make sure that the shim message doesn't claim to end past the end of the IPv6 packet. : YES (Checked in the kernel)
• the checksum is correct : YES (Checked in the kernel)
• Neither the IPv6 destination field nor the IPv6 source field is a multicast address nor the unspecified address : YES (Checked in the kernel)

3.2.  I1 Message

• The Reserved1 field MUST be ignored on receipt: YES
• The R field MUST be ignored on receipt: YES
• When another instance of an existent context with the same ULID pair is being created, a Forked Instance Identifier option MUST be included to distinguish this new instance from the existent one : FEATURE NOT SUPPORTED (LinShim6 never maintains two instances of a context with the same ULID pair, because this would happen only if a socket API were implemented)
• The I1 message MUST include the ULID pair : YES (always in the IPv6 header since the ULID option is not supported)
• A host MUST silently discard any received I1 message that does not statisfy all of the following validity checks :
  • Hdr Ext Len field at least 1 : YES
  • If the ULID pair option is present, the host verifies that the locator of the Initiator is included in Ls(peer) : FEATURE NO SUPPORTED (ULID pair option)

3.3.  R1 Message

• The Reserved1 field MUST be ignored on receipt: YES
• The Reserved2 field MUST be ignored on receipt: YES
• The Responder Validator Option MUST be included : YES
• A host MUST silently discard any received R1 message that does not statisfy all of the following validity checks :
  • Hdr Ext Len field at least 1 : YES
  • the host looks for an existing context which matches the Initiator Nonce and where the locators are contained in Ls(peer) and Ls(local), respectively. If no such context is found, then the R1 message is silently discarded : YES
  • If the context found using the above rules is not in I1-SENT state, the R1 message is silently discarded : YES

3.4.  I2 Message

• The Reserved1 field MUST be ignored on receipt: YES
• The R field MUST be ignored on receipt: YES
• The Reserved2 field MUST be ignored on receipt: YES
• The Responder Validator Option MUST be included : YES
• The Responder Validator Option MUST be generated copying the Responder Validator option received in the R1 message : YES
• When the IPv6 source and destination addresses in the IPv6 header do not match the ULID pair, this option MUST be included : FEATURE NOT SUPPORTED (Makes sense in case of recovery from a lost context, which is not yet supported)
• When another instance of an existent context with the same ULID pair is being created, a Forked Instance Identifier option MUST be included to distinguish this new instance from the existent one : FEATURE NOT SUPPORTED (LinShim6 never maintains two instances of a context with the same ULID pair)
• When the Locator List Option is sent, the necessary HBA/CGA information for verifying the locator list MUST also be included : YES (Only CGAs are used currently)
• The CGA PDS option MUST be included when the locator list is included : YES.
• The CGA Signature option MUST be included when some of the locators in the list use CGA (and not HBA) for verification : YES (All locators use CGA currently)
• If the initiator does not receive an R2 message after I2_TIMEOUT time after sending an I2 message it MAY retransmit the I2 message, using binary exponential backoff and randomized timers : YES
• In the case that the initiator decides not to retransmit I2 messages or in the case that the initiator still does not recieve an R2 message after retransmitting I2 messages I2_RETRIES_MAX times, the initiator SHOULD fall back to retransmitting the I1 message : YES
• A host MUST silently discard any received I2 message that does not statisfy all of the following validity checks :
  • Hdr Ext Len field at least 2 : YES
  • The responder nonce is a recent one. Nonces that are no older than VALIDATOR_MIN_LIFETIME SHOULD be considered recent : YES
  • the Responder Validator option matches the validator the host would have computed for the ULID, locators, responder nonce, initiator nonce and FII : YES
  • If a CGA Parameter Data Structure (PDS) is included in the message, then the host MUST verify if the actual PDS contained in the message corresponds to the ULID(peer) : YES
  • If the state is I1-SENT, then the host verifies if the source locator is included in Ls(peer) or, it is included in the Locator List contained in the I2 message and the HBA/CGA verification for this specific locator is successful: YES
• If a host is in I1-SENT state, receives an I2 message and all the above checks are successful, then it MUST send a R2 message back : YES

3.5.  R2 Message

• The Reserved1 field MUST be ignored on receipt: YES
• The R field MUST be ignored on receipt: YES
• When the Locator List Option is sent, the necessary HBA/CGA information for verifying the locator list MUST also be included : YES (Only CGAs are used currently)
• Before an R2 message is sent, the host MUST look for a possible context confusion : YES (this is verified at I2/R2 reception)
• A host MUST silently discard any received R2 message that does not statisfy all of the following validity checks :
  • Hdr Ext Len field at least 1 : YES
  • the host looks for an existing context which matches the Initiator Nonce and where the locators are contained in Ls(peer) and Ls(local), respectively. If no such context is found, then the R2 message is silently dropped : YES
  • If state is I1-SENT, I2-SENT or I2BIS-SENT and a CGA Parameter Data Structure (PDS) is included in the message, then the host MUST verify if the actual PDS contained in the message corresponds to the ULID(peer) : YES
• Before the host completes the R2 processing it MUST look for a possible context confusion : YES

3.6.  R1bis, I2bis, Update Request and Update Acknowledgement

Those messages are not supported yet. They are never sent, and are ignored on receipt.

3.7.  Keepalive and Probe Messages

• The Type field must be 66 for a keepalive, 67 for a probe : YES
• The Reserved1 and Reserved2 fields MUST be ignored on receipt : YES
• The R bit MUST be ignored on receipt : YES
• A keepalive MAY contain options : NO (no option is currently defined)
• The first set of sent probe fields of a probe message pertains to the currently sent probe message and MUST be present : YES
• This value SHOULD be generated using a random number generator that is known to have good randomness properties as outlined in RFC 4086 : YES (we rely on the random() function, with a seed taken from /dev/random when the daemon starts)
• If the host is using a non-default Send Timeout value, it SHOULD communicate this value as a Keepalive Timeout value to the peer : NO
• When sending a Probe message, the State field MUST be set to a value that matches the conceptual state of the sender after sending the Probe : YES

3.8.  Keepalive Timeout Option

This option is not supported yet

3.9.  Error messages

Those messages are optional and are not supported yet.

3.10.  Message Options

• The length field MUST NOT include the padding : YES
• Any added padding bytes MUST be zeroed by the sender : YES
• The values of the padding bytes SHOULD NOT be checked by the receiver : YES
• If C=1 and the option is not recognized by the receiver, then the host SHOULD send back a Shim6 error message with Error Code=1, with the Pointer referencing the first octet in the Option Type field.: NO (because the error messages are not yet supported)
• If C=1 and the option is not recognized by the receiver, then the rest of the message MUST NOT be processed : YES
• Locator Preferences : Any element definition of length greater than 3 MUST be defined so that the first three bytes agree the definition given in the draft : YES (we do not define longer element fields).
• The Reserved2 field of the ULID pair option MUST be ignored on receipt : FEATURE NOT SUPPORTED (ULID pair option support not implemented).
• If the verification method in the Locator List option is not supported by the host, or if the verification method is not consistent with the CGA Parameter Data Structure, then the host MUST ignore the Locator List and the message in which it is contained : YES
• If the verification method in the Locator List option is not supported by the host, or if the verification method is not consistent with the CGA Parameter Data Structure, then the host SHOULD generate a Shim6 Error message with Error Code=2, with the Pointer referencing the octet in the Verification method that was found inconsistent. : NO

3.11.  Payload data

• The insertion of the Shim6 extension header in payload packets MUST NOT cause any recalculation of the ULP checksums : YES
• When receiving a packet with a context tag that does not match any context, the receiver SHOULD generate a R1bis message : NO (Because context recovery is not supported yet)
• If payload data is received with a context tag that matches with a context in state I2-SENT or I2BIS-SENT, the host resp. sends back a I2 or I2bis and proceeds to process the message : NO (We currently only process the message if the state is ESTABLISHED)

3.12.  General requirements of the Shim6 draft

• The I1, I2 and I2bis messages MUST contain the ULID pair, either in the IPv6 header or in a ULID pair option : YES (During negotiation the locators are always the identifiers, thus the ULID pair option is not needed.)
• The context tag MUST be unique for each context : YES
• At least 30 bits of the context tag MUST be populated by random or pseudo-random bits : YES (all 47 bits are pseudo-random)
• The host SHOULD randomly cycle through the unstructured tag name space : YES (we rely on the random() function, with a seed taken from /dev/random when the daemon starts)
• The HBA/CGA verification SHOULD be performed by the host before the host acknowledges the new locator, by sending an Update Acknowledgement message, or an R2 message. : YES (Currently HBA and the Update Acknowledgement are not implemented, but we check the CGAs before sending the R2)
• Before a host can use a locator (different from the ULID) as the destination locator it MUST perform the HBA/CGA verification if this was not performed before upon the reception of the locator set. : YES (Checked upon reception)
• Before a host can use a locator (different from the ULID) as the destination locator, it MUST verify that the ULID is indeed present at that locator. This verification is performed by doing a return- routability test as part of the Probe sub-protocol : YES
• I2, I2bis and R2 messages MUST include a sufficiently large set of locators in a Locator List option that the peer can determine whether or not two contexts have the same host as the peer by comparing if there is any common locators in Ls(peer) : YES (currently we send the whole set of available locators, since may change later when the socket API will be implemented)
• In case of context confusion detection ([refs.shim6] (Bagnulo, M. and E. Nordmark, “Shim6: Level 3 Multihoming Shim Protocol for IPv6,” .)), the old context which used the context tag MUST be removed : YES
• An implementation MAY re-create a context to replace the one that was removed because of confusion detection : NO (it is not automatically re-created, but it can be negotiated again if the ULP sends a sufficient amount of traffic for the heuristic to trigger a context establishment)
• It is RECOMMENDED that hosts do not tear down the context when they know that there is some upper layer protocol that might use the context : YES (We delete a context when no traffic has been seen during 10 minutes, the implementation is not yet aware of ULP opened sockets, however)
• The minimum acceptable key length for public keys used in the generation of CGAs SHOULD be 1024 bits : YES
• in case that IPsec is implemented as Bump-In-The-Wire (BITW), either the shim MUST be disabled, or the shim MUST also be implemented as Bump-In-The-Wire, in order to satisfy the requirement that IPsec is layered above the shim : CONFIGURABLE (It is up to the user to disable Shim6 if he wants to use a BITW IPsec device)

3.13.  General requirements of the REAP draft

• Available addresses are discovered and monitored through mechanisms outside the scope of SHIM6.SHIM6 implementations MUST be able to employ information provided by IPv6 Neighbor Discovery, Address Autoconfiguration, and DHCP (when DHCP is implemented). This information includes the availability of a new address and status changes of existing addresses (such as when an address becomes invalid) : PARTIAL SUPPORT (Address discovery is performed using all mechanisms available in the kernel, but they are not yet monitored later)
• Locally operational addresses are discovered and monitored through mechanisms outside the SHIM6 protocol.SHIM6 implementations MUST be able to employ information provided from Neighbor Unreachability Detection : NO
• Locally operational addresses are discovered and monitored through mechanisms outside the SHIM6 protocol. Implementations MAY also employ additional, link layer specific mechanisms : NO
• SHIM6 implementations MUST support the discovery of operational address pairs through the use of explicit rechability tests and Forced Bidirectional Communication (FBD), described later in this specification : YES
• In addition, implementations MAY employ the following additional mechanisms:
  • Positive feedback from upper layer protocols : NO
  • Negative feedback from upper layer protocols : NO
  • ICMP error messages : NO
• After the reception of a data packet from the peer, REAP keepalive packets SHOULD continue to be sent at the Keepalive Interval until either a data packet in the SHIM6 context has been sent to the peer or the Keepalive Timeout expires : YES
• Upon changing to a new address pair, the network path traversed most likely has changed, thus the ULP SHOULD be informed : NO
• Out of the set of possible candidate address pairs, nodes SHOULD attempt to test through all of them until an operational pair is found, and retrying the process as is necessary : YES
• All nodes MUST perform the exploration process sequentially and with exponential back-off : YES
• The externally observable behaviour of an implementation MUST conform to the REAP state machine : YES
• Unprotected indications from other parts of the protocol stack SHOULD NOT be taken as a proof of connectivity problems. : YES

4.  Protocol conformance by feature

• Context forking : No (Only useful if an API exists)
• Context recovery : Not yet
• Locator preferences option : Not yet
• Locator list updates : Not yet
• Cryptographically Generated Addresses : YES
• Hash Based Addresses : Not yet
• Failure detection and recovery : YES
• Context confusion detection ([refs.shim6] (Bagnulo, M. and E. Nordmark, “Shim6: Level 3 Multihoming Shim Protocol for IPv6,” .) sec. 7.6): YES
• Handling of ICMP error messages : Not yet
• Keepalive Timeout Option : Not yet

5.  Conclusion and further work

This draft describes the current state of the LinShim6 implementation. It uses a heuristic to decide whether to trigger a Shim6 negotiation, and it is able to monitor the state of the communication thanks to the REAP state machine. It has been shown to successfully support the switch to an alternative locator pair, and it supports the minimal security checks and features given in the specifications (only HBA addresses are not yet supproted). LinShim6 is a work in progress and is still being improved. We aim at finally providing the complete set of features. In the near future we will work on HBA support, context recovery, locator list updates and error messages. Other missing features seem to have a lower priority and are let for later.

6.  Acknowledgments

7. References

Authors' Addresses

Full Copyright Statement

Copyright © The IETF Trust (2008).

This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.

This document and the information contained herein are provided on an “AS IS” basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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.

Intellectual Property

The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79.

Copies of IPR disclosures made to the IETF Secretariat 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 proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr.

The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org.