I have a strange problem ever since I installed devstack with OpenStack version "Liberty". I can create instances on the machine and SSH into them without any problem. The devstack is created as a single node with the controller and the compute being on the same machine. The networking used is Nova with an floating IP range of 172.24.4.0. The problem occurs when I try to ssh to an instance from another computer. I have created a route in the router to direct all traffic from 172.24.4.0 to the IP of the machine where OpenStack is installed. I can telnet into the SSH port from this external machine:

$ telnet 172.24.4.9 22
Trying 172.24.4.9...
Connected to 172.24.4.9.
Escape character is '^]'.

However, whenever I try to SSH to an instance from the external machine, I am getting a timeout.

$ ssh -v -i ~/.ssh/xxx.key cirros@172.24.4.9
OpenSSH_6.9p1, LibreSSL 2.1.7
debug1: Reading configuration data /Users/username/.ssh/config
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 20: Applying options for *
debug1: Connecting to 172.24.4.9 [172.24.4.9] port 22.
debug1: Connection established.
debug1: identity file /Users/username/.ssh/xxx.key type 1
debug1: key_load_public: No such file or directory
debug1: identity file /Users/username/.ssh/xxx.key-cert type -1
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_6.9
ssh_exchange_identification: read: Operation timed out

This used to work in prior versions like Juno though I may have faced a similar issue in Kilo. Either way, this problem goes away whenever I ssh from within the machine where OpenStack is installed. This leads me to believe that there is no problem with the SSH server inside the instance.

Things I have already ensured:

1. The permission of the private key file is kept at 600.
2. The same key file was copied over using SCP from the local machine where it works fine.