A behavior prediction algorithm predicts a call by monitoring user inputs to detect an action by the user suggesting the user may be about to instigate the call, and identifying a candidate callee for the call. A network address associated with the callee is also retrieved from a data store. In response to the behavior detection algorithm predicting the call, a connection establishment message is transmitted to the network address via a network, so as to establish over the network a signalling connection for transmitting messages to a device available to the callee. After the connection establishment message has been transmitted, an explicit instruction is received from the user to instigate the call to the callee. In response to receiving the explicit instruction, a call invite is transmitted to the device via the signalling connection, thereby causing the device to output an incoming call notification.