Supplemental material to:

QoS-Aware Management of Monotonic Service Orchestrations

This page is supplemental material to: A. Benveniste, C. Jard, A. Kattepur, S. Rosario, and J.A. Thywissen, "QoS-Aware Management of Monotonic Service Orchestrations," In Formal Methods in System Design, 44:1-43, 2013.

The code presented here is from Appendix B of the paper, with Println output added to illuminate the events occurring during the program execution.

• QoS.orc—Declaration of the QoS operators for the Cost and ResponseTime QoS domains.
• TravelAgent2-sim.orc—The Orc specification of the TravelAgent2 orchestration
• TravelAgent2-weaved—The QoS-weaved description of the TravelAgent2 orchestration

QoS.inc (top)

The QoS operator definitions for the response time domain, cost domain, and more interestingly, the composite cost-response time domain.

Note the following about the cost domain implementation: In the body of the article, lattice operators' semantics forced us to use multisets to represent cost. Since the join operator is defined explicitly here, as an optimization, we deviate from the lattice semantics for the cost domain, so it can be defined as a single number.

--------
-- Response time
--------

def class ResponseTimeDomainClass() =
  def leq(x, y) = x <= y
  def min(xs) = cfold(lambda(x, y) = if leq(x, y) then x else y, xs)
  def max(xs) = cfold(lambda(x, y) = if leq(y, x) then x else y, xs)
  def oPlus(x, y) = x + y
  def zero() = 0
  def join(xs) = max(xs)
  def compete(x, ys) = x
  stop

val responseTimeDomain = ResponseTimeDomainClass() -- Singleton

--------
-- Cost
--------

def class CostDomainClass() =
  def leq(x, y) = x <= y
  def min(xs) = cfold(lambda(x, y) = if leq(x, y) then x else y, xs)
  def max(xs) = cfold(lambda(x, y) = if leq(y, x) then x else y, xs)
  def oPlus(x, y) = x + y
  def zero() = 0
  def join(xs) = cfold(oPlus, xs)
  def compete(x, ys) = x
  stop

val costDomain = CostDomainClass() -- Singleton

--------
-- Cost and response time
--------

def class CostAndRTDomainClass() =
  def leq((c1, rt1), (c2, rt2)) = if c1 /= c2 then costDomain.leq(c1, c2) else responseTimeDomain.leq(rt1, rt2)
  def min(xs) = cfold(lambda(x, y) = if leq(x, y) then x else y, xs)
  def max(xs) = cfold(lambda(x, y) = if leq(y, x) then x else y, xs)
  def oPlus((c1, rt1), (c2, rt2)) = (costDomain.oPlus(c1, c2), responseTimeDomain.oPlus(rt1, rt2))
  def zero() = (costDomain.zero(), responseTimeDomain.zero())
  def join(xs) = unzip(xs) >(cs,rts)> (costDomain.join(cs), responseTimeDomain.join(rts))
  def compete((cx,rtx), ys) = unzip(ys) >(_,rtys)> (cx, responseTimeDomain.join(rtx:rtys))
  stop

val costAndRTDomain = CostAndRTDomainClass() -- Singleton

TravelAgent2-sim.orc (top)

The Orc specification of the TravelAgent2 orchestration. This is the non-QoS-aware base implementation, to be contrasted with with the QoS-aware version below. To run this program, simply press the run button below the listing.

--------
-- Air travel quote service
--------

def randomPrice() = Random(50)
def simulateDelay() = Random(150) >d> Rwait(d) >> d

def class Airline(name) =
  def quoteAvailPrice(order) =
    randomPrice()  >p>
    simulateDelay()  >d>
    Println("Order "+order+": Airline '"+name+"' quote="+p+" (response time "+d+" ms)") >>
    {. supplier = name, price = p .}
  stop

--------
-- Hotel accommodation quote service
--------

type RoomCategory = Deluxe() | Standard()
def randomRoomCat() = if Random(2) = 0 then Deluxe() else Standard()

def class Hotel(name) =
  def quoteAvailPrice(order) =
    randomPrice()  >p>
    randomRoomCat() >r>
    simulateDelay()  >d>
    Println("Order "+order+": Hotel '"+name+"' room category="+r+", quote="+p+" (response time "+d+" ms)") >>
    {. supplier = name, roomCat = r, price = p .}
  stop

--------
-- Travel Agency orchestration
--------

{- QoS-based comparisons -}

def bestPrice(vx, vy) = if vx.price <= vy.price then vx else vy

def bestCategoryPrice(vx, vy) if (vx.roomCat = vy.roomCat) = if vx.price <= vy.price then vx else vy
def bestCategoryPrice(vx, vy) if (vx.roomCat = Deluxe())   = vx
def bestCategoryPrice(vx, vy) if (vy.roomCat = Deluxe())   = vy

{- Service instances -}

val airline1 = Airline("Airline 1")
val airline2 = Airline("Airline 2")
val hotelA = Hotel("Hotel A")
val hotelB = Hotel("Hotel B")

{- The TravelAgent2 workflow -}

{- Wait for up to 't' milliseconds for the first value from x, then halt -}
def timeout(t, x) = Let(Some(x) | Rwait(t) >> None()) >Some(y)> y

def class TravelAgent2() = 
  def acceptOrder(order, budget) =
    (timeout(325,
      Println("Order "+order+": Accepted by travel agent") >>
      {. order = order .}  >invoice>
      bestPrice(airline1.quoteAvailPrice(order), airline2.quoteAvailPrice(order)) >air>
      invoice + {. airSegment = air .}  >invoice>
      bestCategoryPrice(hotelA.quoteAvailPrice(order), hotelB.quoteAvailPrice(order)) >hotel>
      invoice + {. hotelSegment = hotel .}  >invoice>
      invoice + {. totalPrice = invoice.airSegment.price + invoice.hotelSegment.price .}
    ) ; Println("Order "+order+": Timeout") >> stop)
      >invoice>
    ( if invoice.totalPrice <= budget 
      then (Println("Order "+order+": Orchestration completed") >> invoice)
      else (Println("Order "+order+": Budget exceeded, resubmitting") >> acceptOrder(order, budget)))
  stop


--------
-- Simulate some orders
--------

{- Simulation parameters -}
val numSimulatedOrders = 10
val budget = 40
val delayBetweenOrders = 200

def simulateOrders(_, 0) = stop
def simulateOrders(number, max) =
    TravelAgent2().acceptOrder(number, budget)
  | Rwait(delayBetweenOrders) >> simulateOrders(number + 1, max - 1)

simulateOrders(0, numSimulatedOrders)

TravelAgent2-weaved.orc (top)

The QoS-weaved description of the TravelAgent2 orchestration, to be contrasted with with the base version above. To run this program, simply press the run button below the listing.

--------
-- Response time
--------

def class ResponseTimeDomainClass() =
  def leq(x, y) = x <= y
  def min(xs) = cfold(lambda(x, y) = if leq(x, y) then x else y, xs)
  def max(xs) = cfold(lambda(x, y) = if leq(y, x) then x else y, xs)
  def oPlus(x, y) = x + y
  def zero() = 0
  def join(xs) = max(xs)
  def compete(x, ys) = x
  stop

val responseTimeDomain = ResponseTimeDomainClass() -- Singleton

--------
-- Cost
--------

def class CostDomainClass() =
  def leq(x, y) = x <= y
  def min(xs) = cfold(lambda(x, y) = if leq(x, y) then x else y, xs)
  def max(xs) = cfold(lambda(x, y) = if leq(y, x) then x else y, xs)
  def oPlus(x, y) = x + y
  def zero() = 0
  def join(xs) = cfold(oPlus, xs)
  def compete(x, ys) = x
  stop

val costDomain = CostDomainClass() -- Singleton

--------
-- Cost and response time
--------

def class CostAndRTDomainClass() =
  def leq((c1, rt1), (c2, rt2)) = if c1 /= c2 then costDomain.leq(c1, c2) else responseTimeDomain.leq(rt1, rt2)
  def min(xs) = cfold(lambda(x, y) = if leq(x, y) then x else y, xs)
  def max(xs) = cfold(lambda(x, y) = if leq(y, x) then x else y, xs)
  def oPlus((c1, rt1), (c2, rt2)) = (costDomain.oPlus(c1, c2), responseTimeDomain.oPlus(rt1, rt2))
  def zero() = (costDomain.zero(), responseTimeDomain.zero())
  def join(xs) = unzip(xs) >(cs,rts)> (costDomain.join(cs), responseTimeDomain.join(rts))
  def compete((cx,rtx), ys) = unzip(ys) >(_,rtys)> (cx, responseTimeDomain.join(rtx:rtys))
  stop

val costAndRTDomain = CostAndRTDomainClass() -- Singleton
{- EXAMPLE -}
--------
-- Air travel quote service
--------

def randomPrice() = Random(50)
def simulateDelay() = Random(150) >d> Rwait(d) >> d

def class Airline(name) =
  def quoteAvailPrice(order, qosParms) =
    randomPrice()  >p>
    simulateDelay()  >d>
    Println("Order "+order+": Airline '"+name+"' quote="+p+" (response time "+d+" ms)") >>
    ({. supplier = name, price = p .}, costAndRTDomain.oPlus(qosParms, (p,d)))
  stop

--------
-- Hotel accommodation quote service
--------

type RoomCategory = Deluxe() | Standard()
def randomRoomCat() = if Random(2) = 0 then Deluxe() else Standard()

def class Hotel(name) =
  def quoteAvailPrice(order, qosParms) =
    randomPrice()  >p>
    randomRoomCat() >r>
    simulateDelay()  >d>
    Println("Order "+order+": Hotel '"+name+"' room category="+r+", quote="+p+" (response time "+d+" ms)") >>
    ({. supplier = name, roomCat = r, price = p .}, costAndRTDomain.oPlus(qosParms, (p,d)))
  stop

--------
-- Travel Agency orchestration
--------

{- QoS-based comparisons -}

def bestPrice((vx, qx), (vy, qy)) = if vx.price <= vy.price then (vx, costAndRTDomain.compete(qx,[qy])) else (vy, costAndRTDomain.compete(qy,[qx]))

def bestCategoryPrice((vx, qx), (vy, qy)) if (vx.roomCat = vy.roomCat) = if vx.price <= vy.price then (vx, costAndRTDomain.compete(qx,[qy])) else (vy, costAndRTDomain.compete(qy,[qx]))
def bestCategoryPrice((vx, qx), (vy, qy)) if (vx.roomCat = Deluxe())   = (vx, costAndRTDomain.compete(qx,[qy]))
def bestCategoryPrice((vx, qx), (vy, qy)) if (vy.roomCat = Deluxe())   = (vy, costAndRTDomain.compete(qy,[qx]))

{- Service instances -}

val airline1 = Airline("Airline 1")
val airline2 = Airline("Airline 2")
val hotelA = Hotel("Hotel A")
val hotelB = Hotel("Hotel B")

{- The TravelAgent2 workflow -}

{- Wait for up to 't' milliseconds for the first value from x, then halt -}
def timeout(t, x) = Let(Some(x) | Rwait(t) >> None()) >Some(y)> y

def class TravelAgent2() = 
  def acceptOrder(order, budget) =
    (timeout(325,
      Println("Order "+order+": Accepted by travel agent") >>
      {. order = order .}  >invoice>
      costAndRTDomain.zero()  >qosParms>
      bestPrice(airline1.quoteAvailPrice(order, qosParms), airline2.quoteAvailPrice(order, qosParms)) >(air,qosParms)>
      (invoice + {. airSegment = air .})  >invoice>
      bestCategoryPrice(hotelA.quoteAvailPrice(order, qosParms), hotelB.quoteAvailPrice(order, qosParms)) >(hotel,qosParms)>
      (invoice + {. hotelSegment = hotel .})  >invoice>
      (invoice + {. totalPrice = invoice.airSegment.price + invoice.hotelSegment.price .}, qosParms)
    ) ; Println("Order "+order+": Timeout") >> stop)
      >(invoice, qosParms)>
    ( if invoice.totalPrice <= budget 
      then (Println("Order "+order+": Orchestration completed with (cost, response time) QoS delivered="+qosParms) >> (invoice, qosParms))
      else (Println("Order "+order+": Budget exceeded, resubmitting") >> acceptOrder(order, budget)))
  stop


--------
-- Simulate some orders
--------

{- Simulation parameters -}
val numSimulatedOrders = 10
val budget = 40
val delayBetweenOrders = 200

def simulateOrders(_, 0) = stop
def simulateOrders(number, max) =
    TravelAgent2().acceptOrder(number, budget)
  | Rwait(delayBetweenOrders) >> simulateOrders(number + 1, max - 1)

simulateOrders(0, numSimulatedOrders)