Haizea

# -------------------------------------------------------------------------- #

# Copyright 2006-2009, University of Chicago                                 #

# Copyright 2008-2009, Distributed Systems Architecture Group, Universidad   #

# Complutense de Madrid (dsa-research.org)                                   #

#                                                                            #

# 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.                                             #

# -------------------------------------------------------------------------- #

"""This module provides the lease data structures:

* Lease: Represents a lease

* LeaseStateMachine: A state machine to keep track of a lease's state

* Capacity: Used to represent a quantity of resources

* Timestamp: An exact moment in time

* Duration: A duration

* SoftwareEnvironment, UnmanagedSoftwareEnvironment, DiskImageSoftwareEnvironment:

  Used to represent a lease's required software environment.

* LeaseWorkload: Represents a collection of lease requests submitted

  in a specific order.

* Site: Represents the site with leasable resources.

* Nodes: Represents a collection of machines ("nodes"). This is used

  both when specifying a site and when specifying the machines

  needed by a leases.

"""

from haizea.common.constants import LOGLEVEL_VDEBUG, RES_MEM, SUSPRES_EXCLUSION_GLOBAL, SUSPRES_EXCLUSION_LOCAL

from haizea.common.utils import StateMachine, round_datetime_delta, get_lease_id, compute_suspend_resume_time, get_config

from haizea.core.scheduler.slottable import ResourceReservation

from mx.DateTime import DateTime, TimeDelta, Parser

import logging

try:

    import xml.etree.ElementTree as ET

except ImportError:

    # Compatibility with Python <=2.4

    import elementtree.ElementTree as ET

class Lease(object):

    """A resource lease

    This is one of the main data structures used in Haizea. A lease

    is "a negotiated and renegotiable agreement between a resource

    provider and a resource consumer, where the former agrees to make

    a set of resources available to the latter, based on a set of

    lease terms presented by the resource consumer". All the gory

    details on what this means can be found on the Haizea website

    and on the Haizea publications.

    See the __init__ method for a description of the information that

    is contained in a lease.

    """

    # Lease states

    STATE_NEW = 0

    STATE_PENDING = 1

    STATE_REJECTED = 2

    STATE_SCHEDULED = 3

    STATE_QUEUED = 4

    STATE_CANCELLED = 5

    STATE_PREPARING = 6

    STATE_READY = 7

    STATE_ACTIVE = 8

    STATE_SUSPENDING = 9

    STATE_SUSPENDED_PENDING = 10

    STATE_SUSPENDED_QUEUED = 11

    STATE_SUSPENDED_SCHEDULED = 12

    STATE_MIGRATING = 13

    STATE_RESUMING = 14

    STATE_RESUMED_READY = 15

    STATE_DONE = 16

    STATE_FAIL = 17

    STATE_REJECTED_BY_USER = 18

    # String representation of lease states

    state_str = {STATE_NEW : "New",

                 STATE_PENDING : "Pending",

                 STATE_REJECTED : "Rejected",

                 STATE_SCHEDULED : "Scheduled",

                 STATE_QUEUED : "Queued",

                 STATE_CANCELLED : "Cancelled",

                 STATE_PREPARING : "Preparing",

                 STATE_READY : "Ready",

                 STATE_ACTIVE : "Active",

                 STATE_SUSPENDING : "Suspending",

                 STATE_SUSPENDED_PENDING : "Suspended-Pending",

                 STATE_SUSPENDED_QUEUED : "Suspended-Queued",

                 STATE_SUSPENDED_SCHEDULED : "Suspended-Scheduled",

                 STATE_MIGRATING : "Migrating",

                 STATE_RESUMING : "Resuming",

                 STATE_RESUMED_READY: "Resumed-Ready",

                 STATE_DONE : "Done",

                 STATE_FAIL : "Fail",

                 STATE_REJECTED_BY_USER : "Rejected by user"}

    # Lease types

    BEST_EFFORT = 1

    ADVANCE_RESERVATION = 2

    IMMEDIATE = 3

    DEADLINE = 4

    UNKNOWN = -1

    # String representation of lease types

    type_str = {BEST_EFFORT: "Best-effort",

                ADVANCE_RESERVATION: "AR",

                IMMEDIATE: "Immediate",

                DEADLINE: "Deadline",

                UNKNOWN: "Unknown"}

    def __init__(self, lease_id, submit_time, user_id, requested_resources, start, duration,

                 deadline, preemptible, software, state, extras = {}):

        """Constructs a lease.

        The arguments are the fundamental attributes of a lease.

        The attributes that are not specified by the arguments are

        the lease ID (which is an autoincremented integer), the

        lease state (a lease always starts out in state "NEW").

        A lease also has several bookkeeping attributes that are

        only meant to be consumed by other Haizea objects.

        Arguments:

        id -- Unique identifier for the lease. If None, one

        will be provided.

        submit_time -- The time at which the lease was submitted

        requested_resources -- A dictionary (int -> Capacity) mapping

          each requested node to a capacity (i.e., the amount of

          resources requested for that node)

        start -- A Timestamp object containing the requested time.

        duration -- A Duration object containing the requested duration.

        deadline -- A Timestamp object containing the deadline by which

          this lease must be completed.

        preemptible -- A boolean indicating whether this lease can be

          preempted or not.

        software -- A SoftwareEnvironment object specifying the

          software environment required by the lease.

        extras -- Extra attributes. Haizea will ignore them, but they

          may be used by pluggable modules.

        """

        # Lease ID (read only)

        self.id = lease_id

        # Lease attributes

        self.submit_time = submit_time

        self.user_id = user_id

        self.requested_resources = requested_resources

        self.start = start

        self.duration = duration

        self.deadline = deadline

        self.preemptible = preemptible

        self.software = software

        self.price = None

        self.extras = extras

        # Bookkeeping attributes:

        # Lease state

        if state == None:

            state = Lease.STATE_NEW

        self.state_machine = LeaseStateMachine(initial_state = state)

        # End of lease (recorded when the lease ends)

        self.end = None

        # Number of nodes requested in the lease

        self.numnodes = len(requested_resources)

        # The following two lists contain all the resource reservations

        # (or RRs) associated to this lease. These two lists are

        # basically the link between the lease and Haizea's slot table.

        # The preparation RRs are reservations that have to be

        # completed before a lease can first transition into a

        # READY state (e.g., image transfers)

        self.preparation_rrs = []

        # The VM RRs are reservations for the VMs that implement

        # the lease.

        self.vm_rrs = []

        # Enactment information. Should only be manipulated by enactment module

        self.enactment_info = None

        self.vnode_enactment_info = dict([(n, None) for n in self.requested_resources.keys()])

    @classmethod

    def create_new(cls, submit_time, user_id, requested_resources, start, duration,

                 deadline, preemptible, software):

        lease_id = get_lease_id()

        state = Lease.STATE_NEW

        return cls(lease_id, submit_time, user_id, requested_resources, start, duration,

                 deadline, preemptible, software, state)

    @classmethod

    def create_new_from_xml_element(cls, element):

        lease = cls.from_xml_element(element)

        if lease.id == None:

            lease.id = get_lease_id()

        lease.state_machine = LeaseStateMachine(initial_state = Lease.STATE_NEW)

        return lease

    @classmethod

    def from_xml_file(cls, xml_file):

        """Constructs a lease from an XML file.

        See the Haizea documentation for details on the

        lease XML format.

        Argument:

        xml_file -- XML file containing the lease in XML format.

        """

        return cls.from_xml_element(ET.parse(xml_file).getroot())

    @classmethod

    def from_xml_string(cls, xml_str):

        """Constructs a lease from an XML string.

        See the Haizea documentation for details on the

        lease XML format.

        Argument:

        xml_str -- String containing the lease in XML format.

        """

        return cls.from_xml_element(ET.fromstring(xml_str))

    @classmethod

    def from_xml_element(cls, element):

        """Constructs a lease from an ElementTree element.

        See the Haizea documentation for details on the

        lease XML format.

        Argument:

        element -- Element object containing a "<lease>" element.

        """

        lease_id = element.get("id")

        if lease_id == None:

            lease_id = None

        else:

            lease_id = int(lease_id)

        user_id = element.get("user")

        if user_id == None:

            user_id = None

        else:

            user_id = int(user_id)

        state = element.get("state")

        if state == None:

            state = None

        else:

            state = int(state)

        submit_time = element.get("submit-time")

        if submit_time == None:

            submit_time = None

        else:

            submit_time = Parser.DateTimeFromString(submit_time)

        nodes = Nodes.from_xml_element(element.find("nodes"))

        requested_resources = nodes.get_all_nodes()

        start = element.find("start")

        if len(start.getchildren()) == 0:

            start = Timestamp(Timestamp.UNSPECIFIED)

        else:

            child = start[0]

            if child.tag == "now":

                start = Timestamp(Timestamp.NOW)

            elif child.tag == "exact":

                start = Timestamp(Parser.DateTimeFromString(child.get("time")))

        duration = Duration(Parser.DateTimeDeltaFromString(element.find("duration").get("time")))

        deadline = element.find("deadline")

        if deadline != None:

            deadline = Parser.DateTimeFromString(deadline.get("time"))

        extra = element.find("extra")

        extras = {}

        if extra != None:

            for attr in extra:

                extras[attr.get("name")] = attr.get("value")

        preemptible = element.get("preemptible").capitalize()

        if preemptible == "True":

            preemptible = True

        elif preemptible == "False":

            preemptible = False

        software = element.find("software")

        if software.find("none") != None:

            software = UnmanagedSoftwareEnvironment()

        elif software.find("disk-image") != None:

            disk_image = software.find("disk-image")

            image_id = disk_image.get("id")

            image_size = int(disk_image.get("size"))

            software = DiskImageSoftwareEnvironment(image_id, image_size)

        return Lease(lease_id, submit_time, user_id, requested_resources, start, duration,

                     deadline, preemptible, software, state, extras)

    def to_xml(self):

        """Returns an ElementTree XML representation of the lease

        See the Haizea documentation for details on the

        lease XML format.

        """

        lease = ET.Element("lease")

        if self.id != None:

            lease.set("id", str(self.id))

        lease.set("state", str(self.get_state()))

        lease.set("preemptible", str(self.preemptible))

        if self.submit_time != None:

            lease.set("submit-time", str(self.submit_time))

        capacities = {}

        for capacity in self.requested_resources.values():

            key = capacity

            for c in capacities:

                if capacity == c:

                    key = c

                    break

            numnodes = capacities.setdefault(key, 0)

            capacities[key] += 1

        nodes = Nodes([(numnodes,c) for c,numnodes in capacities.items()])

        lease.append(nodes.to_xml())

        start = ET.SubElement(lease, "start")

        if self.start.requested == Timestamp.UNSPECIFIED:

            pass # empty start element

        elif self.start.requested == Timestamp.NOW:

            ET.SubElement(start, "now") #empty now element

        else:

            exact = ET.SubElement(start, "exact")

            exact.set("time", str(self.start.requested))

        duration = ET.SubElement(lease, "duration")

        duration.set("time", str(self.duration.requested))

        software = ET.SubElement(lease, "software")

        if isinstance(self.software, UnmanagedSoftwareEnvironment):

            ET.SubElement(software, "none")

        elif isinstance(self.software, DiskImageSoftwareEnvironment):

            imagetransfer = ET.SubElement(software, "disk-image")

            imagetransfer.set("id", self.software.image_id)

            imagetransfer.set("size", str(self.software.image_size))

        return lease

    def to_xml_string(self):

        """Returns a string XML representation of the lease

        See the Haizea documentation for details on the

        lease XML format.

        """

        return ET.tostring(self.to_xml())

    def get_type(self):

        """Determines the type of lease

        Based on the lease's attributes, determines the lease's type.

        Can return Lease.BEST_EFFORT, Lease.ADVANCE_RESERVATION, or

        Lease.IMMEDIATE

        """

        if self.start.requested == Timestamp.UNSPECIFIED:

            return Lease.BEST_EFFORT

        elif self.start.requested == Timestamp.NOW:

            return Lease.IMMEDIATE

        else:

            if self.deadline == None:

                return Lease.ADVANCE_RESERVATION

            else:

                return Lease.DEADLINE

    def get_state(self):

        """Returns the lease's state.

        """

        return self.state_machine.get_state()

    def set_state(self, state):

        """Changes the lease's state.

        The state machine will throw an exception if the

        requested transition is illegal.

        Argument:

        state -- The new state

        """

        self.state_machine.change_state(state)

    def print_contents(self, loglevel=LOGLEVEL_VDEBUG):

        """Prints the lease's attributes to the log.

        Argument:

        loglevel -- The loglevel at which to print the information

        """

        logger = logging.getLogger("LEASES")

        logger.log(loglevel, "__________________________________________________")

        logger.log(loglevel, "Lease ID       : %i" % self.id)

        logger.log(loglevel, "Type           : %s" % Lease.type_str[self.get_type()])

        logger.log(loglevel, "Submission time: %s" % self.submit_time)

        logger.log(loglevel, "Start          : %s" % self.start)

        logger.log(loglevel, "Duration       : %s" % self.duration)

        logger.log(loglevel, "Deadline       : %s" % self.deadline)

        logger.log(loglevel, "State          : %s" % Lease.state_str[self.get_state()])

        logger.log(loglevel, "Resource req   : %s" % self.requested_resources)

        logger.log(loglevel, "Software       : %s" % self.software)

        logger.log(loglevel, "Price          : %s" % self.price)

        logger.log(loglevel, "Extras         : %s" % self.extras)

        self.print_rrs(loglevel)

        logger.log(loglevel, "--------------------------------------------------")

    def print_rrs(self, loglevel=LOGLEVEL_VDEBUG):

        """Prints the lease's resource reservations to the log.

        Argument:

        loglevel -- The loglevel at which to print the information

        """

        logger = logging.getLogger("LEASES")

        if len(self.preparation_rrs) > 0:

            logger.log(loglevel, "DEPLOYMENT RESOURCE RESERVATIONS")

            logger.log(loglevel, "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~")

            for r in self.preparation_rrs:

                r.print_contents(loglevel)

                logger.log(loglevel, "##")

        logger.log(loglevel, "VM RESOURCE RESERVATIONS")

        logger.log(loglevel, "~~~~~~~~~~~~~~~~~~~~~~~~")

        for r in self.vm_rrs:

            r.print_contents(loglevel)

            logger.log(loglevel, "##")

    def get_active_vmrrs(self, time):

        """Returns the active VM resource reservations at a given time

        Argument:

        time -- Time to look for active reservations

        """

        return [r for r in self.vm_rrs if r.start <= time and time <= r.end and r.state == ResourceReservation.STATE_ACTIVE]

    def get_scheduled_reservations(self):

        """Returns all scheduled reservations

        """

        return [r for r in self.preparation_rrs + self.vm_rrs if r.state == ResourceReservation.STATE_SCHEDULED]

    def get_last_vmrr(self):

        """Returns the last VM reservation for this lease.

        """

        if len(self.vm_rrs) > 0:

            return self.vm_rrs[-1]

        else:

            return None

    def get_vmrr_at(self, time):

        """...

        """

        vmrr_at = None

        for vmrr in self.vm_rrs:

            if time >= vmrr.get_first_start() and time < vmrr.get_final_end():

                vmrr_at = vmrr

                break

        return vmrr_at

    def get_vmrr_after(self, time):

        """...

        """

        vmrr_after = []

        for vmrr in self.vm_rrs:

            if vmrr.get_first_start() > time:

                vmrr_after.append(vmrr)

        return vmrr_after

    def get_endtime(self):

        """Returns the time at which the last VM reservation

        for this lease ends.

        Note that this is not necessarily the time at which the lease

        will end, just the time at which the last currently scheduled

        VM will end.

        """

        vmrr = self.get_last_vmrr()

        if vmrr == None:

            # Nothing scheduled, no endtime

            return None

        else:

            return vmrr.get_final_end()

    def get_accumulated_duration_at(self, time):

        """Returns the amount of time required to fulfil the entire

        requested duration of the lease at a given time.

        """

        t = TimeDelta(0)

        for vmrr in self.vm_rrs:

            if time >= vmrr.end:

                t += vmrr.end - vmrr.start

            elif time >= vmrr.start and time < vmrr.end:

                t += time -vmrr.start

                break

            else:

                break

        return t

    def get_remaining_duration_at(self, time):

        """Returns the amount of time required to fulfil the entire

        requested duration of the lease at a given time.

        """

        return self.duration.requested - self.get_accumulated_duration_at(time)

    def append_vmrr(self, vmrr):

        """Adds a VM resource reservation to the lease.

        Argument:

        vmrr -- The VM RR to add.

        """

        self.vm_rrs.append(vmrr)

        self._update_prematureend()

    def remove_vmrr(self, vmrr):

        """Removes a VM resource reservation from the lease.

        Argument:

        vmrr -- The VM RR to remove.

        """

        if not vmrr in self.vm_rrs:

            raise Exception, "Tried to remove an VM RR not contained in this lease"

        else:

            self.vm_rrs.remove(vmrr)

    def append_preparationrr(self, preparation_rr):

        """Adds a preparation resource reservation to the lease.

        Argument:

        preparation_rr -- The preparation RR to add.

        """

        self.preparation_rrs.append(preparation_rr)

    def remove_preparationrr(self, preparation_rr):

        """Removes a preparation resource reservation from the lease.

        Argument:

        preparation_rr -- The preparation RR to remove.

        """

        if not preparation_rr in self.preparation_rrs:

            raise Exception, "Tried to remove a preparation RR not contained in this lease"

        else:

            self.preparation_rrs.remove(preparation_rr)

    def clear_rrs(self):

        """Removes all resource reservations for this lease

        (both preparation and VM)

        """

        self.preparation_rrs = []

        for rr in self.vm_rrs:

            rr.clear_rrs()

        self.vm_rrs = []

    def get_waiting_time(self):

        """Gets the waiting time for this lease.

        The waiting time is the difference between the submission

        time and the time at which the lease start. This method

        mostly makes sense for best-effort leases, where the

        starting time is determined by Haizea.

        """

        return self.start.actual - self.submit_time

    def get_slowdown(self, bound=10):

        """Determines the bounded slowdown for this lease.

        Slowdown is a normalized measure of how much time a

        request takes to make it through a queue (thus, like

        get_waiting_time, the slowdown makes sense mostly for

        best-effort leases). Slowdown is equal to the time the

        lease took to run on a loaded system (i.e., a system where

        it had to compete with other leases for resources)

        divided by the time it would take if it just had the

        system all to itself (i.e., starts running immediately

        without having to wait in a queue and without the

        possibility of being preempted).

        "Bounded" slowdown is one where leases with very short

        durations are rounded up to a bound, to prevent the

        metric to be affected by reasonable but disproportionate

        waiting times (e.g., a 5-second lease with a 15 second

        waiting time -an arguably reasonable waiting time- has a

        slowdown of 4, the same as 10 hour lease having to wait

        30 hours for resources).

        Argument:

        bound -- The bound, specified in seconds.

        All leases with a duration less than this

        parameter are rounded up to the bound.

        """

        time_on_dedicated = self.duration.actual

        time_on_loaded = self.end - self.submit_time

        bound = TimeDelta(seconds=bound)

        if time_on_dedicated < bound:

            time_on_dedicated = bound

        return time_on_loaded / time_on_dedicated

    def estimate_suspend_time(self):

        """ Estimate the time to suspend an entire lease

        Most of the work is done in __estimate_suspend_resume_time. See

        that method's documentation for more details.

        Arguments:

        lease -- Lease that is going to be suspended

        """

        rate = get_config().get("suspend-rate")

        override = get_config().get("override-suspend-time")

        if override != None:

            return override

        else:

            return self.__estimate_suspend_resume_time(rate)

    def estimate_resume_time(self):

        """ Estimate the time to resume an entire lease

        Most of the work is done in __estimate_suspend_resume_time. See

        that method's documentation for more details.

        Arguments:

        lease -- Lease that is going to be resumed

        """

        rate = get_config().get("resume-rate")

        override = get_config().get("override-resume-time")

        if override != None:

            return override

        else:

            return self.__estimate_suspend_resume_time(rate)

    def estimate_shutdown_time(self):

        """ Estimate the time to shutdown an entire lease

        Arguments:

        lease -- Lease that is going to be shutdown

        """

        enactment_overhead = get_config().get("enactment-overhead").seconds

        return get_config().get("shutdown-time") + (enactment_overhead * self.numnodes)

    def add_boot_overhead(self, t):

        """Adds a boot overhead to the lease.

        Increments the requested duration to account for the fact

        that some time will be spent booting up the resources.

        Argument:

        t -- Time to add

        """

        self.duration.incr(t)

    def add_runtime_overhead(self, percent):

        """Adds a runtime overhead to the lease.

        This method is mostly meant for simulations. Since VMs

        run slower than physical hardware, this increments the

        duration of a lease by a percent to observe the effect

        of having all the leases run slower on account of

        running on a VM.

        Note: the whole "runtime overhead" problem is becoming

        increasingly moot as people have lost their aversion to

        VMs thanks to the cloud computing craze. Anecdotal evidence

        suggests that most people don't care that VMs will run

        X % slower (compared to a physical machine) because they

        know full well that what they're getting is a virtual

        machine (the same way a user of an HPC system would know

        that he/she's getting processors with speed X as opposed to

        those on some other site, with speed X*0.10)

        Argument:

        percent -- Runtime overhead (in percent of requested

        duration) to add to the lease.

        """

        self.duration.incr_by_percent(percent)

    def sanity_check(self):

        prev_time = None

        prev_vmrr = None

        for vmrr in self.vm_rrs:

            if len(vmrr.pre_rrs) > 0:

                prev_time = vmrr.pre_rrs[0].start - 1

            else:

                prev_time = vmrr.start - 1

            if prev_vmrr != None:

                if vmrr.is_resuming():

                    assert prev_vmrr.is_suspending()

            else:

                assert not vmrr.is_resuming()

            for pre_rr in vmrr.pre_rrs:

                assert pre_rr.start >= prev_time

                assert pre_rr.end >= pre_rr.start

                prev_time = pre_rr.end

            assert vmrr.start >= prev_time

            assert vmrr.end >= vmrr.start

            prev_time = vmrr.end

            if vmrr.prematureend != None:

                assert vmrr.prematureend >= vmrr.start and vmrr.prematureend <= vmrr.end

            for post_rr in vmrr.post_rrs:

                assert post_rr.start >= prev_time

                assert post_rr.end >= post_rr.start

                prev_time = post_rr.end

            prev_vmrr = vmrr

        if len(self.preparation_rrs) > 0 and len(self.vm_rrs) > 0:

            assert self.preparation_rrs[-1].end <= self.vm_rrs[0].start

    def __estimate_suspend_resume_time(self, rate):

        """ Estimate the time to suspend/resume an entire lease

        Note that, unlike __compute_suspend_resume_time, this estimates

        the time to suspend/resume an entire lease (which may involve

        suspending several VMs)

        Arguments:

        lease -- Lease that is going to be suspended/resumed

        rate -- The rate at which an individual VM is suspended/resumed

        """

        susp_exclusion = get_config().get("suspendresume-exclusion")

        enactment_overhead = get_config().get("enactment-overhead")

        time = 0

        for vnode in self.requested_resources:

            mem = self.requested_resources[vnode].get_quantity(RES_MEM)

            # Overestimating when susp_exclusion == SUSPRES_EXCLUSION_LOCAL

            time += compute_suspend_resume_time(mem, rate) + enactment_overhead

        return time

    def __repr__(self):

        """Returns a string representation of the Lease"""

        return "L%i" % self.id

    # ONLY for simulation

    def _update_prematureend(self):

        known = self.duration.known

        acc = TimeDelta(0)

        for vmrr in self.vm_rrs:

            if known != None:

                rrdur = vmrr.end - vmrr.start

                if known - acc <= rrdur:

                    vmrr.prematureend = vmrr.start + (known-acc)

                    break

                else:

                    vmrr.prematureend = None

                    acc += rrdur

            else:

                vmrr.prematureend = None

class LeaseStateMachine(StateMachine):

    """A lease state machine

    A child of StateMachine, this class simply specifies the valid

    states and transitions for a lease (the actual state machine code

    is in StateMachine).

    See the Haizea documentation for a description of states and

    valid transitions.

    """

    transitions = {Lease.STATE_NEW:                 [(Lease.STATE_PENDING,    "")],

                   Lease.STATE_PENDING:             [(Lease.STATE_SCHEDULED,  ""),

                                                     (Lease.STATE_QUEUED,     ""),

                                                     (Lease.STATE_CANCELLED,  ""),

                                                     (Lease.STATE_REJECTED,   ""),

                                                     (Lease.STATE_REJECTED_BY_USER,   "")],