 intervals of STUN messages are longer than in the fore validation sub-phase. In the most likely case, the fore validation sub-phase concludes with the discovery of an optimal SIP channel before the 200 OK SIP message is sent. The information related to the selected channel can be used to reduce the number of STUN messages needed to detect optimal chan- nels for the media flows by properly setting the priority sub-field of the ALEX-item fields related to media flows placed in the 200 OK answer. For example, if the optimal SIP channel is based on a relayed address, the the ALEX-item containing a relayed address is assigned highest priority for each media flow. ALEX stores the optimal channels discovered in the ALEX cache. The trans- port addresses stored in the cache will be checked first during subsequent session establishments since they probably have a high probability of success, i.e., of being reachable. Each entry of the ALEX cache contains an additional tag to keep its current state. Initially, the state of an optimal channel is set to live and the UA periodically sends a keepalive message on the channel to ensure that it is still working. If no keepalive messages are sent for a given period, the state of the channel is set to probed: the channel is no longer active, but it is kept in the cache as a hint to speed up the establishment of subsequent sessions. ALEX has been implemented in a modified version of the Open Wengo NG UA [15] and has been tested in some significant scenarios including different NAT behaviors [2]. The tests prove ALEX to be effective in providing end- to-end connectivity for both SIP and media flows at a very low cost in terms of the increase of the SIP message size and in terms of the number of STUN messages exchanged during the validation step. C 2009 by Taylor & Francis Group, LLC NAT Traversal References [1] Behavior Engineering for Hindrance Avoidance (behave), IETF Work- ing Group. http://www.ietf.org/html.charters/behave-charter.html. Accessed November 15, 2007. [2] Audet, F., 