An Interactive Connectivity Establishment, ICE, based NAT traversal mechanism is described for use by originating/terminating P-CSCF nodes (114a/114b) in an IMS network (105). The originating P-CSCF node (114a) receives a SIP INVITE request from first user equipment (UE) (101 ) originating a call towards a second UE (103). If a relay candidate address for the first UE (101) is not present in the SIP INVITE request, the SIP INVITE request is modified to include a first address provided by an originating IMS-AGW node (115a) as a relay candidate for the first UE (101) and forwarded to the second UE (103). The originating P-CSCF node (114a) receives a SIP INVITE response message from the second UE (103) in response to the SIP INVITE request. If a relay candidate address for the second UE (103) is not present in the SIP INVITE response, the SIP INVITE response is modified to include a second address provided by an originating IMS-AGW node (115a) as a relay candidate for the second UE (103) and forwarded to the first UE (101). The corresponding candidate address information is used by the both UEs (101, 103) in ICE procedures. If a relay server is required, then only the IMS-AGW node (115a) is deployed.