diff --git a/requirements.txt b/requirements.txt
index dd73257..d567082 100644
--- a/requirements.txt
+++ b/requirements.txt
@@ -5,7 +5,7 @@
 cliff!=1.16.0,!=1.17.0,>=1.15.0 # Apache-2.0
 jsonschema!=2.5.0,<3.0.0,>=2.0.0 # MIT
 testtools>=1.4.0 # MIT
-paramiko>=1.16.0 # LGPL
+paramiko>=2.0 # LGPL
 netaddr!=0.7.16,>=0.7.12 # BSD
 testrepository>=0.0.18 # Apache-2.0/BSD
 pyOpenSSL>=0.14 # Apache-2.0
@@ -19,7 +19,7 @@
 fixtures<2.0,>=1.3.1 # Apache-2.0/BSD
 testscenarios>=0.4 # Apache-2.0/BSD
 PyYAML>=3.1.0 # MIT
-stevedore>=1.9.0 # Apache-2.0
+stevedore>=1.10.0 # Apache-2.0
 PrettyTable<0.8,>=0.7 # BSD
 os-testr>=0.4.1 # Apache-2.0
-urllib3>=1.8.3 # MIT
+urllib3>=1.15.1 # MIT
diff --git a/tempest/api/compute/servers/test_attach_interfaces.py b/tempest/api/compute/servers/test_attach_interfaces.py
index 8201363..fdf55e5 100644
--- a/tempest/api/compute/servers/test_attach_interfaces.py
+++ b/tempest/api/compute/servers/test_attach_interfaces.py
@@ -13,10 +13,10 @@
 #    License for the specific language governing permissions and limitations
 #    under the License.
 
-import netaddr
 import time
 
 from tempest.api.compute import base
+from tempest.common.utils import net_utils
 from tempest import config
 from tempest import exceptions
 from tempest.lib import exceptions as lib_exc
@@ -125,18 +125,21 @@
 
     def _test_create_interface_by_fixed_ips(self, server, ifs):
         network_id = ifs[0]['net_id']
-        ip_list = [
-            ifs[n]['fixed_ips'][0]['ip_address'] for n in range(0, len(ifs))]
-        ip = str(netaddr.IPAddress(sorted(ip_list)[-1]) + 1)
+        subnet_id = ifs[0]['fixed_ips'][0]['subnet_id']
+        ip_list = net_utils.get_unused_ip_addresses(self.ports_client,
+                                                    self.subnets_client,
+                                                    network_id,
+                                                    subnet_id,
+                                                    1)
 
-        fixed_ips = [{'ip_address': ip}]
+        fixed_ips = [{'ip_address': ip_list[0]}]
         iface = self.client.create_interface(
             server['id'], net_id=network_id,
             fixed_ips=fixed_ips)['interfaceAttachment']
         self.addCleanup(self.ports_client.delete_port, iface['port_id'])
         iface = self.wait_for_interface_status(
             server['id'], iface['port_id'], 'ACTIVE')
-        self._check_interface(iface, fixed_ip=ip)
+        self._check_interface(iface, fixed_ip=ip_list[0])
         return iface
 
     def _test_show_interface(self, server, ifs):
diff --git a/tempest/api/network/test_floating_ips.py b/tempest/api/network/test_floating_ips.py
index 2156e64..2abbf93 100644
--- a/tempest/api/network/test_floating_ips.py
+++ b/tempest/api/network/test_floating_ips.py
@@ -13,10 +13,9 @@
 #    License for the specific language governing permissions and limitations
 #    under the License.
 
-import netaddr
-
 from tempest.api.network import base
 from tempest.common.utils import data_utils
+from tempest.common.utils import net_utils
 from tempest import config
 from tempest import test
 
@@ -192,8 +191,12 @@
     @test.idempotent_id('45c4c683-ea97-41ef-9c51-5e9802f2f3d7')
     def test_create_update_floatingip_with_port_multiple_ip_address(self):
         # Find out ips that can be used for tests
-        ips = list(netaddr.IPNetwork(self.subnet['cidr']))
-        list_ips = [str(ip) for ip in ips[-3:-1]]
+        list_ips = net_utils.get_unused_ip_addresses(
+            self.ports_client,
+            self.subnets_client,
+            self.subnet['network_id'],
+            self.subnet['id'],
+            2)
         fixed_ips = [{'ip_address': list_ips[0]}, {'ip_address': list_ips[1]}]
         # Create port
         body = self.ports_client.create_port(network_id=self.network['id'],
diff --git a/tempest/common/utils/net_utils.py b/tempest/common/utils/net_utils.py
new file mode 100644
index 0000000..d98fb32
--- /dev/null
+++ b/tempest/common/utils/net_utils.py
@@ -0,0 +1,48 @@
+# Copyright 2016 Hewlett Packard Enterprise Development Company
+#
+# Licensed under the Apache License, Version 2.0 (the "License"); you may
+# not use this file except in compliance with the License. You may obtain
+# a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+# License for the specific language governing permissions and limitations
+# under the License.
+
+import itertools
+import netaddr
+
+from tempest.lib import exceptions as lib_exc
+
+
+def get_unused_ip_addresses(ports_client, subnets_client,
+                            network_id, subnet_id, count):
+
+    """Return a list with the specified number of unused IP addresses
+
+    This method uses the given ports_client to find the specified number of
+    unused IP addresses on the given subnet using the supplied subnets_client
+    """
+
+    ports = ports_client.list_ports(network_id=network_id)['ports']
+    subnet = subnets_client.show_subnet(subnet_id)
+    ip_net = netaddr.IPNetwork(subnet['subnet']['cidr'])
+    subnet_set = netaddr.IPSet(ip_net.iter_hosts())
+    alloc_set = netaddr.IPSet()
+
+    # prune out any addresses already allocated to existing ports
+    for port in ports:
+        for fixed_ip in port.get('fixed_ips'):
+            alloc_set.add(fixed_ip['ip_address'])
+
+    av_set = subnet_set - alloc_set
+    ip_list = [str(ip) for ip in itertools.islice(av_set, count)]
+
+    if len(ip_list) != count:
+        msg = "Insufficient IP addresses available"
+        raise lib_exc.BadRequest(message=msg)
+
+    return ip_list
diff --git a/tempest/config.py b/tempest/config.py
index 30cd501..6360c3e 100644
--- a/tempest/config.py
+++ b/tempest/config.py
@@ -672,7 +672,7 @@
     cfg.StrOpt('network_for_ssh',
                default='public',
                help="Network used for SSH connections. Ignored if "
-                    "use_floatingip_for_ssh=true or run_validation=false.",
+                    "connect_method=floating or run_validation=false.",
                deprecated_opts=[cfg.DeprecatedOpt('network_for_ssh',
                                                   group='compute')]),
 ]
diff --git a/tempest/lib/common/rest_client.py b/tempest/lib/common/rest_client.py
index fafb303..30750de 100644
--- a/tempest/lib/common/rest_client.py
+++ b/tempest/lib/common/rest_client.py
@@ -15,6 +15,7 @@
 #    under the License.
 
 import collections
+import email.utils
 import logging as real_logging
 import re
 import time
@@ -637,7 +638,10 @@
                     resp, self._parse_resp(resp_body)) and
                 retry < MAX_RECURSION_DEPTH):
             retry += 1
-            delay = int(resp['retry-after'])
+            delay = self._get_retry_after_delay(resp)
+            self.LOG.debug(
+                "Sleeping %s seconds based on retry-after header", delay
+            )
             time.sleep(delay)
             resp, resp_body = self._request(method, url,
                                             headers=headers, body=body)
@@ -645,6 +649,51 @@
                             resp, resp_body)
         return resp, resp_body
 
+    def _get_retry_after_delay(self, resp):
+        """Extract the delay from the retry-after header.
+
+        This supports both integer and HTTP date formatted retry-after headers
+        per RFC 2616.
+
+        :param resp: The response containing the retry-after headers
+        :rtype: int
+        :return: The delay in seconds, clamped to be at least 1 second
+        :raises ValueError: On failing to parse the delay
+        """
+        delay = None
+        try:
+            delay = int(resp['retry-after'])
+        except (ValueError, KeyError):
+            pass
+
+        try:
+            retry_timestamp = self._parse_http_date(resp['retry-after'])
+            date_timestamp = self._parse_http_date(resp['date'])
+            delay = int(retry_timestamp - date_timestamp)
+        except (ValueError, OverflowError, KeyError):
+            pass
+
+        if delay is None:
+            raise ValueError(
+                "Failed to parse retry-after header %r as either int or "
+                "HTTP-date." % resp.get('retry-after')
+            )
+
+        # Retry-after headers do not have sub-second precision. Clients may
+        # receive a delay of 0. After sleeping 0 seconds, we would (likely) hit
+        # another 413. To avoid this, always sleep at least 1 second.
+        return max(1, delay)
+
+    def _parse_http_date(self, val):
+        """Parse an HTTP date, like 'Fri, 31 Dec 1999 23:59:59 GMT'.
+
+        Return an epoch timestamp (float), as returned by time.mktime().
+        """
+        parts = email.utils.parsedate(val)
+        if not parts:
+            raise ValueError("Failed to parse date %s" % val)
+        return time.mktime(parts)
+
     def _error_checker(self, method, url,
                        headers, body, resp, resp_body):
 
@@ -771,10 +820,7 @@
         if (not isinstance(resp_body, collections.Mapping) or
                 'retry-after' not in resp):
             return True
-        over_limit = resp_body.get('overLimit', None)
-        if not over_limit:
-            return True
-        return 'exceed' in over_limit.get('message', 'blabla')
+        return 'exceed' in resp_body.get('message', 'blabla')
 
     def wait_for_resource_deletion(self, id):
         """Waits for a resource to be deleted
diff --git a/tempest/tests/lib/test_rest_client.py b/tempest/tests/lib/test_rest_client.py
index 2959294..2a6fad5 100644
--- a/tempest/tests/lib/test_rest_client.py
+++ b/tempest/tests/lib/test_rest_client.py
@@ -547,6 +547,65 @@
         self.assertIsNotNone(str(self.rest_client))
 
 
+class TestRateLimiting(BaseRestClientTestClass):
+
+    def setUp(self):
+        self.fake_http = fake_http.fake_httplib2()
+        super(TestRateLimiting, self).setUp()
+
+    def test__get_retry_after_delay_with_integer(self):
+        resp = {'retry-after': '123'}
+        self.assertEqual(123, self.rest_client._get_retry_after_delay(resp))
+
+    def test__get_retry_after_delay_with_http_date(self):
+        resp = {
+            'date': 'Mon, 4 Apr 2016 21:56:23 GMT',
+            'retry-after': 'Mon, 4 Apr 2016 21:58:26 GMT',
+        }
+        self.assertEqual(123, self.rest_client._get_retry_after_delay(resp))
+
+    def test__get_retry_after_delay_of_zero_with_integer(self):
+        resp = {'retry-after': '0'}
+        self.assertEqual(1, self.rest_client._get_retry_after_delay(resp))
+
+    def test__get_retry_after_delay_of_zero_with_http_date(self):
+        resp = {
+            'date': 'Mon, 4 Apr 2016 21:56:23 GMT',
+            'retry-after': 'Mon, 4 Apr 2016 21:56:23 GMT',
+        }
+        self.assertEqual(1, self.rest_client._get_retry_after_delay(resp))
+
+    def test__get_retry_after_delay_with_missing_date_header(self):
+        resp = {
+            'retry-after': 'Mon, 4 Apr 2016 21:58:26 GMT',
+        }
+        self.assertRaises(ValueError, self.rest_client._get_retry_after_delay,
+                          resp)
+
+    def test__get_retry_after_delay_with_invalid_http_date(self):
+        resp = {
+            'retry-after': 'Mon, 4 AAA 2016 21:58:26 GMT',
+            'date': 'Mon, 4 Apr 2016 21:56:23 GMT',
+        }
+        self.assertRaises(ValueError, self.rest_client._get_retry_after_delay,
+                          resp)
+
+    def test__get_retry_after_delay_with_missing_retry_after_header(self):
+        self.assertRaises(ValueError, self.rest_client._get_retry_after_delay,
+                          {})
+
+    def test_is_absolute_limit_gives_false_with_retry_after(self):
+        resp = {'retry-after': 123}
+
+        # is_absolute_limit() requires the overLimit body to be unwrapped
+        resp_body = self.rest_client._parse_resp("""{
+            "overLimit": {
+                "message": ""
+            }
+        }""")
+        self.assertFalse(self.rest_client.is_absolute_limit(resp, resp_body))
+
+
 class TestProperties(BaseRestClientTestClass):
 
     def setUp(self):