Load Balancing Module

Algorithm

The Load Balancing algorithm is published in “Distributed Load Balancing for FREEDM system” by Akella. The algorithm labels each process as being in Supply, Demand, or Neutral state and distributes that state to other processes in the group. Processes in the supply state have more generation and storage than load, neutral have equal generation and load, and demand processes have more load than generation. Each time the algorithm runs, a quantum of power is migrated from a supply process to a demand process. The amount that is migrated is a configurable but static value “Migration Step.”

Algorithm Implementation Overview

A majority of the work is controlled by the LoadManage() function. The function performs the following actions to complete the algorithm.

  1. Schedule Next Round – The first thing the algorithm does is schedule the next time it will run. This will either be in the same phase or in the next phase. This is done to prevent the algorithm from running over its allotted execution time.
  2. Read Devices – The state of the attached devices is read. This is done once per round so that the DGI can react to sudden changes in device state during the course of a load balance phase. Read devices measures the attached SST’s sum gateway value (which is the amount of power it is sending to other processes) and computes the difference between the power available and the attached load (generation + storage – load). This difference is the process’s “net generation”
  3. Update State – This function uses the values measured after reading the devices to determine which load balancing state the DGI is in. If the amount of power the DGI is sending to other processes is less than the amount of net generation the SST has, and the DGI has sufficient net generation to send a migration to another process it is in the supply state. If the process is in a state where another quantum of power being drawn through the gateway would help it fulfill a deficit in net generation, the process is in a demand state. If neither of these conditions are met the process is in the normal state.
  4. Load Table – This function prints the read device state and the state of the processes in the system to the screen.
  5. At this point, the DGI checks to see if a “Logger” type device is attached. If the device is attached its “dgiEnable” value must be set to 1 for the DGI to actually perform a migration. If there is no device attached, the DGI will always attempt to perform a migration. This is useful for avoiding transients in some simulations. If the logger device is attached but the DGI is not enabled the DGI will write the gateway value it read in Read Devices back to the SST.
  6. If the DGI process is in the demand state, the DGI sends an announcement to all other processes in its group inform them that it is in demand.
  7. If the DGI process is in the supply state, it will check to see if it has received a message from state collection for the current phase. The collected state is used to set the initial value of a predicted SST gateway value that predicts how the SST’s real power injection will change in response to the DGI commands. This predicted value is used during the course of load balance instead of the measured SST real power injection since the power simulation may not respond immediately to DGI commands. If a message has not yet been received from state collection, then the supply node will do nothing for the current round.
  8. After load balance receives the collected state message, the DGI will check the invariant. If the supply process determines the invariant hasn’t been violated, it will send a “Draft Request” message to all demand processes to offer them a migration. The DGI will then wait for responses to that message. Once this timeout expires the “Draft Standard” function will run.
  9. On receipt of the Draft Request, the receiving process will note the sender is in a supply state and send a “Draft Age” message as a response. This message indicates the amount of demand the receiver has. This value is used by the sender (the supply process) to determine which processes have the greatest need.
  10. On receipt of the “Draft Age” message, the supply node places the response in a table. When the timer expires and the “Draft Standard” function runs, the table is processed. Processes with an age of 0 are moved to the normal set. The process with the greatest age is selected. If that process’ age is greater than the size of a migration step, the supply process will send the selected demand process a “Draft Select” message. Additionally, the process will change its gateway value to send power to the selected demand process.
  11. On receipt of the Draft Select message, the demand process will determine if it still need the offered power. If it does, it will send a Draft Accept message, and adjust its power levels to accept the incoming power. If it does not need the power it will respond with a Too Late message. If the Too Late message is received the supply node will roll back its half of the transaction with the demand node. If the Malicious flag is set, the DGI will drop the draft select message and not send the draft accept message.
  12. On receipt of the Draft Accept message, the supply process notes that the transaction has been completed.
  13. This process repeats a fixed number of times each round, determined by potential difference that DGI can accrue between the actual measurements and the predicted value while load balancing.

Invariant Checking

The invariant check included in DGI 2.0 is an older invariant based on the frequency stability of a microgrid with a single isochronous generator. This model assumed there would be no droop generator used to stabilize frequency, and that large frequency oscillations would occur when the imbalance between generation and load at each SST reached a certain point. As this model is no longer consistent with the HIL-Testbed, the invariant is disabled by default and it is recommended the invariant not be used.

The included invariant was coded for a specific 7-node PSCAD simulation, and the equation used in load balance has hard-coded constants that correspond to that particular simulation. During the course of the simulation, the DGI keeps track of two values: the current frequency, which is measured in PSCAD and sent to each of the DGI, and the current power imbalance. At the start of each phase, the power imbalance is set equal to the isochronous generator’s real power as reported by state collection. Then over the course of several load balance rounds, this value is updated by keeping track of incomplete power migrations. A power migration is considered incomplete until Step 12 of the above load manage description where a supply node receives a draft accept message.

To enable the invariant, which again is not recommended, the check-invariant flag must be set to 1 in the DGI configuration file for all DGI processes. A demand process must also set the malicious-behavior flag to 1 to ensure that it does not increase its load during the course of a simulation, leading to the imbalance between generation and load that would lead to frequency oscillations. This flag works by causing a demand node to ignore the draft select message entirely. It neither increases it load, nor sends a response to the supply DGI that increased its generation, leading to an incomplete power migration that increases the imbalance between generation and load. Without the malicious flag, it is highly unlikely that the normal operation of the DGI will lead to potential violations of the invariant.

Migration Size

The migration step size is set in the FREEDM configuration file and defaults to 2.

Limitations

  • The Load Balancing algorithm needs to be able to predict how the devices will react to its commands or the device will need to react instantaneously to its commands. If the device does not react sufficiently quickly enough, Load Balancing will repeatedly issue the same commands to the device and appear to not be working.
  • The Load Balancing algorithm will move all power values to within one migration step of perfectly balanced. Since the migration step is currently a static value, the algorithm cannot perfectly balance the system. Additionally, there are many computations that include a migration step in order to prevent the DGIs from oscillating when they are near the perfect balance.

LBAgent Reference

class

Public Functions

LBAgent()

LBAgent

Description:
: Constructor for the load balancing module
Precondition:
: Posix Main should register read handler and invoke this module
Postcondition:
: Object is initialized and ready to run load balancing
Limitations:
: None

int Run()

Run

Description:
Main function which initiates the algorithm
Precondition:
: Posix Main should invoke this function
Postcondition:
: Triggers the drafting algorithm by calling LoadManage()
Limitations:
None

Protected Functions

CPeerNode GetMe()

Gets a CPeerNode representing this process.

GetMe

Description:
Gets a CPeerNode that refers to this process.
Return
A CPeerNode referring to this process.

std::string GetUUID() const

Gets the UUID of this process.

GetUUID

Description:
Gets this process’s UUID.
Return
This process’s UUID

Private Functions

void DraftStandard(const boost::system::error_code & error)

The code that runs after the draft request replies have arrived.

DraftStandard

Description:
This function is used to select the process(es) that the migration will happen with. The demand nodes send DraftAge messages indicating the amount of demand to fill.
Precondition:
DraftRequests were sent to the nodes whose replies will be processed
Postcondition:
DraftSelect messages are sent to the selected demand nodes.

void FirstRound(const boost::system::error_code & error)

The code that runs the firtst round of the LB phase.

FirstRound

Description:
The code that is executed as part of the first loadbalance each round.
Precondition:
None
Postcondition:
if the timer wasn’t cancelled this function requests state collection and calls the first load balance.
Parameters
  • error -

    The reason this function was called.

void HandleCollectedState(const sc::CollectedStateMessage & m)

Handles the collected state coming from state collection.

HandleCollectedState

Description:
State collection returns the collected state (via a message) this function handles that message and stores it into this node.
Precondition:
The message is valid
Postcondition:
The aggregate gateway, normal and demand member variables are set. Sends the normal to the members of the group.
Interaction Peers:
My state collection module, Members of my group.
Limitations:
Does not validate the source, integrity or contents of the message.
Parameters
  • m -

    The message body that was recieved by this process.

void HandleCollectedState(const CollectedStateMessage & m)

Handles the collected state coming from load balancing.

HandleCollectedState

Description:
When the collected state arrives, the leader computes normal and pushes it out to all the peers. This method sets the normal value at this peer.
Precondition:
The message is valid
Postcondition:
This node is resynchronized.
Interaction Peers:
My leader.
Limitations:
Does not validate the source, integrity or contents of the message.
Parameters
  • m -

    The message body that was recieved by this process.

void HandleDraftAccept(const DraftAcceptMessage & m, CPeerNode peer)

Handles the draft accept message coming from the demand node.

HandleDraftAccept

Description:
An accept message will arrive from a demand node that has selected to accept a migration from this supply node.
Precondition:
m and peer is valid.
Postcondition:
If the node is in supply, it will adjust the gross powerflow to note the reciever has adjusted their power.
Interaction Peers:
A demand node in my group.
Limitations:
Does not validate the source, integrity or contents of the message.
Parameters
  • m -

    The message body that was recieved by this process.

  • peer -

    The process that the message orginated from.

void HandleDraftAge(const DraftAgeMessage & m, CPeerNode peer)

Handles the draft age message coming from the demand node.

HandleDraftAge

Description:
A DraftAge message is sent by the demand node to a supply to indicate it is still in a demand state and would like to migrate. After the message is recieved this node will respond with drafting to instruct the demand node to commit a power change.
Precondition:
The message and peer are valid. This node should have sent a draft request message to peer previously.
Postcondition:
If in supply and the demand node is selected, a drafting message will be sent to the demand node.
Interaction Peers:
A demand node in the group.
Limitations:
Does not validate the source, integrity or contents of the message.
Parameters
  • m -

    The message body that was recieved by this process.

  • peer -

    The process that the message orginated from.

void HandleDraftRequest(const DraftRequestMessage & m, CPeerNode peer)

Handles the draft request originating from the supply node.

HandleDraftRequest

Description:
Handler for a DraftRequest message. A request message is sent by a supply node to see if a demand node wants to perform a migration.
Precondition:
The message is fully populated. The peer is valid.
Postcondition:
If this process is in the demand state, a DraftAge message is sent back to the orginating process.
Interaction Peers:
A group member who was in the supply state.
Limitations:
Does not validate the source, integrity or contents of the message.
Parameters
  • m -

    The message body that was recieved by this process.

  • peer -

    The process that the message orginated from.

void HandleDraftSelect(const DraftSelectMessage & m, CPeerNode peer)

Handles the draft select message coming from the supply node.

HandleDraftSelect

Description:
A draft select message is accepted by a demand node as an indication a supply node is about to give it some tasty power. When the drafting message arrives the demand node will actuate it’s physical leaves and signal the supply node to do the same by sending back an accept message.
Precondition:
There is a valid message pointer and peer passed into the module. All required ptree keys are present.
Postcondition:
If the node is in demand and will take the supply node’s power this node will generate an accept message and change a device value to accept the new float.
Interaction Peers:
A supply node in my group.
Limitations:
Does not validate the source, integrity or contents of the message.
Parameters
  • m -

    The message body that was recieved by this process.

  • peer -

    The process that the message orginated from.

virtual void HandleIncomingMessage(boost::shared_ptr< const ModuleMessage > m, CPeerNode peer)

First handler for an incoming message.

HandleIncomingMessage “Downcasts” incoming messages into a specific message type, and passes the message to an appropriate handler.

Precondition:
None
Postcondition:
The message is handled by the target handler or a warning is produced.
Parameters
  • m -

    the incoming message

  • peer -

    the node that sent this message (could be this DGI)

void HandlePeerList(const gm::PeerListMessage & m, CPeerNode peer)

Handles the peerlist coming from the group leader.

HandlePeerList

Description:
Updates the list of peers this node is aware of.
Precondition:
There is a valid message pointer and peer passed into the module.
Postcondition:
The AllPeers, Normal, Supply, and Demand peersets are reset.
Interaction Peers:
Group leader.
Limitations:
Does not validate the source, integrity or contents of the message.
Parameters
  • m -

    The message body that was recieved by this process.

  • peer -

    The process that the message orginated from.

void HandleStateChange(const StateChangeMessage & m, CPeerNode peer)

Handles a node announcing its state change.

HandleStateChange

Description:
Handles a peer announcing it is in a new state
Precondition:
The state message is fully populated. The peer is valid.
Postcondition:
The peer is removed from any state sets it is currently in and placed in a set by the contents of the message.
Interaction Peers:
A Group member.
Limitations:
Does not validate the source, integrity or contents of the message.
Parameters
  • m -

    The message body that was recieved by this process.

  • peer -

    The process that the message orginated from.

void HandleTooLate(const TooLateMessage & m)

Handles the draft reject message coming from the demand node.

HandleTooLate

Description:
An accept message will arrive from a demand node that has selected to accept a migration from this supply node, but no longer needs that power.
Precondition:
m and peer is valid.
Postcondition:
This node will adjust its gross powerflow and revert the power setting to cancel the migration.
Interaction Peers:
A demand node in my group.
Limitations:
Does not validate the source, integrity or contents of the message.
Parameters
  • m -

    The message body that was recieved by this process.

bool InvariantCheck()

Check the invariant prior to starting a new migration.

InvariantCheck

Description:
Evaluates the current truth of the physical invariant
Precondition:
none
Postcondition:
calculate the physical invariant using the Omega device
Return
the truth value of the physical invariant

void LoadManage(const boost::system::error_code & error)

The code that the supply nodes use to start doing migrations.

LoadManage

Description:
: Manages the execution of the load balancing algorithm by broadcasting load changes and initiating SendDraftRequest() if in Supply
Precondition:
: Node is not in Fail state
Postcondition:
: Load state change is monitored, specific load changes are advertised to peers and restarts on timeout
Interaction Peers:
All peers in case of Demand state and transition to Normal from Demand;
Limitations:

void LoadTable()

Displays the load table to show DGI state.

LoadTable

Description:
Prints the load table: A tool for observing the state of the system.
Precondition:
None
Postcondition:
None
Limitations:
Some entries in Load table could become stale relative to the global state. The definition of Supply/Normal/Demand could change in future

ModuleMessage MessageCollectedState(float state)

MessageCollectedState

Description:
Given a state, return a message that announces that new state.
Precondition:
none
Postcondition:
returns a new message
Parameters
  • state -

    the normal value to send out.

ModuleMessage MessageDraftAccept(float amount)

Generates the message that the demand node uses to confirm the migration.

MessageDraftAccept

Description:
Generates a new accept message
Precondition:
None
Postcondition:
an Accept message is generated.

ModuleMessage MessageDraftAge(float age)

Generates message demand nodes send in response to DraftRequest.

MessageDraftAge

Precondition:
None
Postcondition:
A new message is generated
Description:
Creates a new DraftAge message.

ModuleMessage MessageDraftRequest()

Generates message supply nodes send to demand nodes.

MessageDraftRequest

Precondition:
None
Postcondition:
A new message is generated
Description:
Creates a new DraftRequest message.

ModuleMessage MessageDraftSelect(float amount)

Generates the message that the supply node uses to select a demand node.

MessageDrafting

Description:
Generates a new DraftSelect message.
Precondition:
None
Postcondition:
a new message is generated.

ModuleMessage MessageStateChange(std::string state)

Generates the message announcing current node state.

MessageStateChange

Description:
Generates a state change message
Precondition:
None
Postcondition:
Returns the new message.
Parameters
  • state -

    is a string describing the new state of Load Balancing

ModuleMessage MessageStateCollection()

Generates the message used to request a state collection.

MessageStateCollection

Description:
Returns a message which is sent to state collection requesting that state collection runs for the given devices.
Precondition:
None
Postcondition:
A CollectState message is created.

ModuleMessage MessageTooLate(float amount)

Generates the message sent by the demand node to refuse migration.

MessageTooLate

Description:
Generates a new too late message
Precondition:
None
Postcondition:
A too late message is generated.

void MoveToPeerSet(PeerSet & ps, CPeerNode peer)

Moves a peer to the specified peerset.

MoveToPeerSet Moves the given peer to the given peerset, removing it from all other categorized peersets (Normal, Supply Demand).

Precondition:
None
Postcondition:
Peer is removed from all specialized peersets, and then readded to ps.
Parameters
  • ps -

    The peerset to move the peer to.

  • peer -

    the peer to move.

ModuleMessage PrepareForSending(const LoadBalancingMessage & m, std::string recipient = "lb")

Boilerplate for preparing a message.

Wraps a LoadBalancingMessage in a ModuleMessage.

Return
a ModuleMessage containing a copy of the LoadBalancingMessage
Parameters
  • m -

    the message to prepare. If any required field is unset, the DGI will abort.

  • recipient -

    the module (sc/lb/gm/clk etc.) the message should be delivered to

void ReadDevices()

Updates the state from the devices.

ReadDevices

Description:
Reads the device state and updates the appropriate member vars.
Precondition:
None
Postcondition:
m_gateway and m_netgeneration are updated.

void ScheduleNextRound()

Schedules the LoadManage that runs next round.

ScheduleNextRound

Description:
Computes how much time is remaining and if there isn’t enough requests the loadbalance that will run next round.
Precondition:
None
Postcondition:
LoadManage is scheduled for this round OR FirstRound is scheduled for next time.

void ScheduleStateCollection()

Sends the request to perform state collection.

ScheduleStateCollection

Description:
Sends the request to the state collection module to perform state collection
Precondition:
None
Postcondition:
If this node is the leader a state collection request is sent.

void SendDraftAccept(CPeerNode peer, float step)

Sends draft accept to the specified peer.

void SendDraftAge(CPeerNode peer)

Sends draftage to the specified peer.

SendDraftAge

Description:
Sends a DraftAge message to specified peer announcing how much demand this node has.
Precondition:
None
Postcondition:
Sends a DraftAge message if this process was in the demand state.
Parameters
  • peer -

    The process to send this to.

void SendDraftRequest()

Sends Draft request to all the demand peers.

SendDraftRequest

Description:
Advertise willingness to share load whenever you can supply
Precondition:
: Current load state of this node is ‘Supply’
Postcondition:
: Send DraftRequest message to peers in demand state

void SendDraftSelect(CPeerNode peer, float step)

Sends a draft select to the specified peer.

SendDraftSelect

Description:
Sends a DraftSelect Message to specified peer.
Precondition:
Peer and step are valid
Postcondition:
A Draft select emssage is sent to the peer

void SendTooLate(CPeerNode peer, float step)

Sends too late to the specified peer.

void SendToPeerSet(const PeerSet & ps, const ModuleMessage & m)

Sends a message to all peers in a peerset.

SendToPeerSet

Description:
Given a message m, send it to every process in peerSet
Precondition:
None
Postcondition:
m is sent to all processes in peerSet
Interaction Peers:
peerSet
Parameters
  • m -

    The message to send

  • ps -

    the processes to send the message to.

void SetDESD(float desd)

Sets DESD value to the specified level.

SetDesd

Description:
Migrates power by adjusting the gateway settings of the attched Desds
Precondition:
: Current load state of this node is ‘Supply’ or ‘Demand’
Postcondition:
: Set command(s) to Desd
Parameters
  • Desd -

    the new desd setting to use.

void SetPStar(float pstar)

Sets PStar to the specified level.

SetPStar

Description:
Migrates power by adjusting the gateway settings of the attched SSTs
Precondition:
: Current load state of this node is ‘Supply’ or ‘Demand’
Postcondition:
: Set command(s) to SST
Parameters
  • pstar -

    the new pstar setting to use.

void Synchronize(float k)

Synchronizes the Fast-Style Loadbalance with the physical system.

Synchronize

Description:
Sets the start of phase values for member variables using the results obtained from state collection.
Precondition:
none
Postcondition:
sets the value of m_PowerDifferential and m_PredictedGateway
Parameters
  • k -

    The new value to use for m_PowerDifferential

void UpdateState()

Updates the node’s state.

UpdateState

Description:
Determines the state of this node with respect to Supply, Demand, Normal.
Precondition:
The values used such as the gateway and migration step are valid and up to date.
Postcondition:
This node may change state.

Private Members

PeerSet m_AllPeers

All peers in group.

std::map< std::string, float > m_DraftAge

Pending migrations.

float m_Gateway

The gateway of this node.

PeerSet m_InDemand

Peers in the demand state.

PeerSet m_InNormal

Peers in the normal state.

PeerSet m_InSupply

Peers in the supply state.

std::string m_Leader

The coordinator of the group.

float m_MigrationStep

The amount to migrate.

float m_NetGeneration

The amount of generation created by attached devices.

float m_PowerDifferential

The powerflow used by the physical invariant.

float m_PredictedGateway

The gateway that we predict will be met by the devices.

CBroker::TimerHandle m_RoundTimer

Timer handle for the round timer.

State m_State

The current state of this peer.

bool m_Synchronized

If the system is synchronized with the physical system.

CBroker::TimerHandle m_WaitTimer

Timer handle for the request timer.

const boost::posix_time::time_duration REQUEST_TIMEOUT

The time it takes to get a draftrequest response.

const boost::posix_time::time_duration ROUND_TIME

The amount of time it takes to do an LB round.