dbo-simulation

Overview

DBO (Delivery Based Ordering) is a novel mechanism that guarantees fairness by post-hoc offsetting the latency differences among market participants in the cloud. This repository contains the simulation framework for DBO using real cloud traces collected over Azure, which includes:

1. A simulation framework for Financial Exchanges which can be extended to simulate various algorithms and evaluate their performance based on latency and fairness achieved.
2. A real 15 min cloud trace on Azure using 10 MPs. The RBs and MPs are implemented as independent processes on same VMs.
3. Scripts to reproduce the simulation results from our paper, DBO: Fairness for Cloud-Hosted Financial Exchanges, published at SIGCOMM'23. Please see our paper for more details about the architecture and schemes: https://dl.acm.org/doi/10.1145/3603269.3604871

Organization

The repository is organized as follows:

• algorithms contains the various algorithms simulated in our framework:
  • algorithm.py defines the base class with methods to be defined by various algorithms.
  • dbo.py extends the base class to implement the DBO algorithm.
  • cloudex.py extends the base class to implement the Cloudex algorithm (see more details here).
  • direct.py extends the base class to implement direct delivery where the data and trades are transmitted without any delays the the RB or the OB.
  • max_rtt.py extends the DBO class to simulate the bounds for Response Time Fairness defined in Section 4.2.1 of the paper.
• single_run.py is used to run a simulation of a particular algorithm by specifying particular attributes.
• run_simulation.py is used to run various simulations using the trace data traces/direct.zip. The output for each algorithm is stored to traces/simulation.dat. It extends single_run.py to run and save results from multiple simulation runs.
• traces should contain the cloud trace and
  • simulation.dat contains the output from various simulation runs using run_simulation.py.
  • trace_indices.py contains the constants used for simulation.
• plot_figures.py uses the outputs of various runs from traces/simulation.dat to plot the graphs and figures.
• figures stores the figures generated by various scripts.
• util.py contains various functions used to generate random RTT traces or to read and format traces from the trace files.

Running Simulations

To run simulations using the cloud trace, first download the trace file direct.zip from the release page of v1: https://github.com/eash3010/dbo-simulation/releases/tag/v1 and place it in the traces/ directory. For more details about the cloud trace, please refer to the next subsection.

Now, you can simulate an algorithm using:

$ python3 single_run.py --algo dbo --num_p 10 --delta 20 --batch_size 25 --trace traces/direct.zip
Reading cloud trace file...
Generating RTTs from trace of MP: 1
Running DBO(20|25|0) for 10 MPs

Response Time Fairness ratio: 1.000000
LRTF fairness ratio (delta=20.000000): 1.000000
Mean latency: 57.713950 us
99th percentile latency: 135.694481 us

Please run python3 single_run.py -h to learn how to configure the various arguments. run_simulation.py extends the simulation to run multiple algorithms on various number of participants. Run python3 run_simulation.py to generate the traces/simulation.dat file which contains the results of all the simulations in the form of a csv. This file has already been generated and is present in the traces/ directory, containing the results of relevant algorithms evaluated by us in the paper. The various columns of the csv traces/simulation.dat are:

<algorithm title and parameters>,<number of participants>,<fairness ratio>,<LRTF fairness ratio>,<mean latency>,<99p latency>,<maximum latency>

where each row contains the results of an algorithm with a particular set of parameters. Example:

DBO(20|25|0),10,1.0,1.0,57.713949790464476,135.69448061427101,445.73724861914525
MaxRTT,10,1.0,1.0,31.12021299373728,46.87189941399265,403.4315758519224
DBO(20|25|0),20,1.0,1.0,60.686777310062695,221.48316430105479,450.3654986593174
Cloudex(10|10),10,0.9779103111111109,0.9779103111111109,27.5380116367638,31.518927120083234,403.38039447917254
Cloudex(15|15),10,0.995140088888889,0.995140088888889,30.182915867603317,31.597716406024965,403.38039447917254
...

Metrics

The main metrics evaluated by us are as follows (described in more detail in the paper, Section 6):

Fariness Ratio

We define two different definitions of fairness in our paper, response time fairness and limited response time fairness. Both of these are evaluated and reported by us in the simulation framework. The figures plotted in the next subsection plot the response time fairness ratio. Note that to evaluate the high-frequency trading (HFT) workloads, we evaluate on MPs with response times faster than 20μs. Accordingly, the choice of delta for DBO and LRTF is also 20μs.

Latency

The latency of the system is evaluated from point of data generation to the trade execution. To only get the system latency, we deduct the response time taken by the MP to submit a trade after receiving a data point. We call this end-to-end latency (see Section 6.1).

Plotting figures from the paper

The outputs from traces/simulation.dat can be used by plot_figures.py to generate figures in the figures/ directory.

python3 plot_figures.py

Cloud trace

The cloud trace can be downloaded from release page: https://github.com/eash3010/dbo-simulation/releases/tag/v1. The cloud trace is a pandas dataframe which has one row for each trade generated by each MP. It can be read in python using:

import pandas
cloud_trace = pandas.read_csv("traces/direct.zip")

The columns in the dataframe are as follows:

Column name	Defination
data_id	ID of data point to which this trade was a response.
generation_time	Timestamp at generation of data point at the CES in μs.
mp_id	The MP ID which sent the trade.
response_time	Time taken by MP to respond.
pacing_delay	Time taken by RB before it is sent to MP.
execution_time	Timestamp of trade execution at the CES in μs.
ces_recv_time	Timestamp when OB receives the trade from the MP in μs.

All times are measured in μs.

Testing custom algorithms

Various algorithms for a financial exchange that follow the same architecture as Figure 1 (from the paper) can be implemented by defining the delivery algorithm at the RB and the ordering algorithm at the OB. See how DBO is implemented in algorithms/dbo.py to extend the Algorithm class for more details.

The Algorithm class defined in algorithms/algorithm.py can also be extended to implement the other schemes described in our earlier workshop paper, Rethinking cloud-hosted financial exchanges for response time fairness, published at HotNets'22: https://dl.acm.org/doi/10.1145/3563766.3564098.

Authors

• Prateesh Goyal
• Eashan Gupta
• Ilias Marinos

Citation

Please cite our paper if you find our code useful.

@inproceedings{10.1145/3603269.3604871,
author = {Gupta, Eashan and Goyal, Prateesh and Marinos, Ilias and Zhao, Chenxingyu and Mittal, Radhika and Chandra, Ranveer},
title = {DBO: Fairness for Cloud-Hosted Financial Exchanges},
year = {2023},
isbn = {9798400702365},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3603269.3604871},
doi = {10.1145/3603269.3604871},
booktitle = {Proceedings of the ACM SIGCOMM 2023 Conference},
pages = {550–563},
numpages = {14},
keywords = {cloud, high frequency trading, financial exchange, fairness, logical clock},
location = {New York, NY, USA},
series = {ACM SIGCOMM '23}
}