The Routing Game Library (RGL) is an open source library developed in C that exposes the necessary API to compute the different parameters needed for a generic routing game setting.
Calling to the built-in functions provided by the RGL, one can construct a routing game starting by an input routing cost array and get the list of routes that correspond to equilibrium strategy profiles of the game. In the current version, the computing method implemented in this library is strongly based on the algorithms presented in [1][2].
The Main functions of the routing game library include:
+ Encoding a cost array into a 32-bit value.
+ Decoding a 32-bit into separate cost values.
+ Building a routing game from the input cost array.
+ Building a routing game by parsing the configuration file.
+ Loading different game parameters such as the coordination policy, the potential threshold and the load balancing mode.
+ Computing equilibrium profiles of a routing game.
+ Computing the load-balancing weights for each solution strategy.
+ Writing the result of routing game in an output file.
+ Writing the strategy selected for each player in an output file.
You can download the latest version of the library from https://github.com/routing-games/routing-game-lib.
HOW TO USE RGL
1> Import the RGL by copying these two following files into your project, and including the header file “routegame.h” in your source code
routegame.c
routegame.h
2> The RGL provides user with two built-in functions : routing_game_main() and routing_game_output_file()
routing_game_main(int N, int P, float T, int U,path_cost PATHCOST[],strategy_profile ROUTINGGAME[n][n],routing_path SELECTEDPATH[])
This is the core function of the RGL. It combines multiple tasks (reading input cost array, loading configuration parameters, building routing game, computing payoff, calculating potential value, finding equilibrium strategy profiles and weighting selected profiles) into a single function call.
The input parameters of this function includes:
N: an integer number indicating the number of strategies available for each player. It is worth noting that in a routing game the number of strategies is the same for both player.
P: an integer number ranging from 0 to 3 that represents the coordination policy used in the routing game.
T: a real number, it is the potential threshold applied in the game.
I: an integer number, with value 0 or 1, in which 0 means “use an even load balancing” while 1 indicates turning on the subflow weighted load balancing.
PATHCOST: an array of path_cost type, path_cost being a RGL data type that merges all the routing costs associated with a path in a single structure. routing_game_main() processes it, considering each element as a path choice (or strategy) and constructing the routing game. Its precise structure is:
struct path_cost
{
unsigned int path_id;
unsigned int egresscost; // ingress IGP path cost at local AS
unsigned int Pingresscost; // ingress IGP path cost at peering AS
unsigned int Pegresscost; // egress IGP path cost at local AS
unsigned int ingresscost; // ingress IGP path cost at peering AS
}
ROUTINGGAME: an empty 2D array of strategy_profile, strategy_profile being a RGL data type that stores the payoff and potential values for each strategy profile.
routing_game_main() function maintains and updates it with payoff and potential value for every strategy profiles. Its precise structure is:
struct strategy_profile
{
unsigned int localcost; // cost for routing traffic at local AS
unsigned int peercost; // cost for routing traffic at peering AS
int pvalue; // potential value
short eq; // equilibria or not ? 1 YES 0 NO
short pe; // pareto efficiency or not ?
short status; // selected for the routing solution or not ? It is defined accordingly to the routing policy
}
SELECTEDPATH: is an empty array of type routing_path, a RGL data type that stores the paths selected by the routing game. routing_game_main() outputs in this array the selected strategies. Its precise structure is:
struct routing_path
{
int id;
int ingresscost;
int egresscost;
int freq; // frequency of occurrence in the array
int pvalue; // potential value
int status; // 1 selected 0 not selected
float tload; // calculated traffic load on this path
}
The output of routing_game_main() includes game data recorded in ROUTINGGAME array and a set of selected strategies updated in SELECTEDPATH array
routing_game_output_file(char FILENAME[],int n, strategy_profile ROUTINGGAME[][], int npath,routing_path SELECTEDPATH[])
It is the logging function that records the routing decision process (starts from building routing game until the decision is made) into an output text file.
This work is done by processing the ROUTINGGAME and SELECTEDPATH arrays, outputs of the routing_game_main() function.
RGL APPLICATIONS
Currently the RGL has been imported in the source code of Quagga routing software to support the development of a PEMP enable router.
More information about this project could be found on https://github.com/routing-games/quagga.
Additional applications will be done soon as mentioned in the homepage.
REFERENCES
[1] Stefano Secci et al, “Peering Equilibrium Multipath Routing: A Game Theory Framework for Internet Peering Settlements“, IEEE/ACM Transactions on Networking, Vol. 19, No. 2, pp: 419-432, April 2011.
[2] Ho Dac Duy Nguyen, Stefano Secci, “Equilibrium Routing: from Theory to Practice”, submitted.