| |||||||||

Static load balancing in a computer network Description Static load balancing in a tree computer network with two-way traffic.
A set of heterogeneous host computers are interconnected; every
node processes jobs (the jobs arrive at each node according to a time
invariant Poisson process) locally or sends it to a remote node.
In the latter case, there is a communication delay for forwarding the job
and getting a response back.
Source Files Data Files loadbal.mos (!********************************************************************* Mosel NL examples ================= file loadbal.mos ```````````````` Convex NLP problem Static load balancing in a tree computer network with two-way traffic. A set of heterogeneous host computers are interconnected, in which each node processes jobs (the jobs arriving at each node according to a time invariant Poisson process) locally or sends it to a remote node. In the latter case, there is a communication delay of forwarding the job and getting a response back. The problem is then to minimize the mean response time of a job. The example considered here features 11 computers arranged as follows: 1 6 9 \ | / \ | / 2---4---5---8---10 / | \ / | \ 3 7 11 Based on AMPL model loadbal.mod Source: http://www.orfe.princeton.edu/~rvdb/ampl/nlmodels/cute Reference: J. Li and H. Kameda, "Optimal load balancing in tree network with two-way traffic", Computer networks and ISDN systems, vol. 25, pp. 1335-1348, 1993. (c) 2008 Fair Issac Corporation author: S. Heipcke, Sep. 2008, rev. Mar. 2013 *********************************************************************!) model "loadbal" uses "mmxnlp", "mmsystem" declarations NODES : range ! Set of nodes (computers) RL : range ! Set of directional arcs ARC: dynamic array(NODES,NODES) of integer ! Network topology: matching node pairs with arcs NCAP: array(NODES) of real ! Limits on node workload DEM: array(NODES) of real ! Processing requests at nodes FCAP: array(RL) of real ! Capacity of arcs flow: array(RL) of mpvar ! Flow on arcs process: array(NODES) of mpvar ! Workload at nodes end-declarations initialisations from "loadbal.dat" ARC DEM NCAP FCAP end-initialisations ! Push variables away from bounds to avoid division by zero BoundaryPush := 0.01 ! Bounds and start values forall(n in NODES) do process(n)>=0; process(n)<=NCAP(n) - BoundaryPush setinitval(process(n), DEM(n)) end-do ! Objective function: minimize response time Obj:= sum(n in NODES) process(n)/(NCAP(n)-process(n))/102.8 + sum(n,m in NODES | exists(ARC(n,m))) ((flow(ARC(n,m))/(BoundaryPush + FCAP(ARC(n,m))-(80*flow(ARC(n,m))+20*flow(ARC(m,n))))/6.425)+ (flow(ARC(n,m))/(BoundaryPush + FCAP(ARC(n,m))-(20*flow(ARC(n,m))+80*flow(ARC(m,n))))/25.7)) ! Limits on arcs forall(n,m in NODES | exists(ARC(n,m))) CtrA(ARC(n,m)):= 20*flow(ARC(n,m))+80*flow(ARC(m,n)) <= FCAP(ARC(n,m)) ! Flow balance in nodes forall(n in NODES) CtNODES(n):= sum(m in NODES | exists(ARC(m,n))) flow(ARC(m,n)) - sum(m in NODES | exists(ARC(n,m))) flow(ARC(n,m)) = process(n) - DEM(n) ! Solve the problem setparam("XNLP_verbose", true) setparam("XNLP_solver", 0) minimise(Obj) ! Test whether a solution is available nlstat:=getparam("XNLP_STATUS") if nlstat<>XNLP_STATUS_LOCALLY_OPTIMAL and nlstat<>XNLP_STATUS_OPTIMAL then writeln("No solution found.") exit(0) end-if ! Display the results writeln("Solution: ", Obj.sol) EPS:=0.001 writeln("Transfer:") forall(n,m in NODES | exists(ARC(n,m)) and flow(ARC(n,m)).sol>EPS) writeln(" ", n, "->", m, ": ", flow(ARC(n,m)).sol) writeln("Workload at nodes:") forall(n in NODES) do write(strfmt(n,3), ": dem: ", DEM(n), " sol: ", process(n).sol, " (lim:", NCAP(n), ")") forall(m in NODES | exists(ARC(n,m)) and flow(ARC(n,m)).sol>EPS) write(" ->", m, ": ", flow(ARC(n,m)).sol) forall(m in NODES | exists(ARC(m,n)) and flow(ARC(m,n)).sol>EPS) write(" <-", m, ": ", flow(ARC(m,n)).sol) writeln end-do end-model | |||||||||

Copyright 2017 Fair Isaac Corporation. |