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/cli/test_execute.py b/tempest/tests/lib/cli/test_execute.py
index b846c46..cc9c94c 100644
--- a/tempest/tests/lib/cli/test_execute.py
+++ b/tempest/tests/lib/cli/test_execute.py
@@ -12,26 +12,65 @@
 #    under the License.
 
 
+import mock
+import subprocess
+
 from tempest.lib.cli import base as cli_base
 from tempest.lib import exceptions
 from tempest.tests import base
 
 
 class TestExecute(base.TestCase):
-    def test_execute_success(self):
+
+    @mock.patch('subprocess.Popen', autospec=True)
+    def test_execute_success(self, mock_popen):
+        mock_popen.return_value.returncode = 0
+        mock_popen.return_value.communicate.return_value = (
+            "__init__.py", "")
         result = cli_base.execute("/bin/ls", action="tempest",
                                   flags="-l -a")
+        args, kwargs = mock_popen.call_args
+        # Check merge_stderr == False
+        self.assertEqual(subprocess.PIPE, kwargs['stderr'])
+        # Check action and flags are passed
+        args = args[0]
+        # We just tests that all pieces are passed through, we cannot make
+        # assumptions about the order
+        self.assertIn("/bin/ls", args)
+        self.assertIn("-l", args)
+        self.assertIn("-a", args)
+        self.assertIn("tempest", args)
+        # The result is mocked - checking that the mock was invoked correctly
         self.assertIsInstance(result, str)
         self.assertIn("__init__.py", result)
 
-    def test_execute_failure(self):
+    @mock.patch('subprocess.Popen', autospec=True)
+    def test_execute_failure(self, mock_popen):
+        mock_popen.return_value.returncode = 1
+        mock_popen.return_value.communicate.return_value = (
+            "No such option --foobar", "")
         result = cli_base.execute("/bin/ls", action="tempest.lib",
                                   flags="--foobar", merge_stderr=True,
                                   fail_ok=True)
+        args, kwargs = mock_popen.call_args
+        # Check the merge_stderr
+        self.assertEqual(subprocess.STDOUT, kwargs['stderr'])
+        # Check action and flags are passed
+        args = args[0]
+        # We just tests that all pieces are passed through, we cannot make
+        # assumptions about the order
+        self.assertIn("/bin/ls", args)
+        self.assertIn("--foobar", args)
+        self.assertIn("tempest.lib", args)
+        # The result is mocked - checking that the mock was invoked correctly
         self.assertIsInstance(result, str)
         self.assertIn("--foobar", result)
 
-    def test_execute_failure_raise_exception(self):
+    @mock.patch('subprocess.Popen', autospec=True)
+    def test_execute_failure_raise_exception(self, mock_popen):
+        mock_popen.return_value.returncode = 1
+        mock_popen.return_value.communicate.return_value = (
+            "No such option --foobar", "")
         self.assertRaises(exceptions.CommandFailed, cli_base.execute,
                           "/bin/ls", action="tempest", flags="--foobar",
                           merge_stderr=True)
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):