Added some comment

2 files changed, 132 insertions, 109 deletions

diff --git a/src/rpc/graph_algo.rs b/src/rpc/graph_algo.rs
index 13c60692..5bd6cc51 100644
--- a/src/rpc/graph_algo.rs
+++ b/src/rpc/graph_algo.rs
@@ -6,10 +6,10 @@ use std::cmp::{max, min};
 use std::collections::HashMap;
 use std::collections::VecDeque;
 
-//Vertex data structures used in all the graphs used in layout.rs.
-//usize parameters correspond to node/zone/partitions ids.
-//To understand the vertex roles below, please refer to the formal description
-//of the layout computation algorithm.
+///Vertex data structures used in all the graphs used in layout.rs.
+///usize parameters correspond to node/zone/partitions ids.
+///To understand the vertex roles below, please refer to the formal description
+///of the layout computation algorithm.
 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
 pub enum Vertex {
 	Source,
@@ -20,8 +20,7 @@ pub enum Vertex {
 	Sink,
 }
 
-//Edge data structure for the flow algorithm.
-//The graph is stored as an adjacency list
+///Edge data structure for the flow algorithm.
 #[derive(Clone, Copy, Debug)]
 pub struct FlowEdge {
 	cap: u32,    //flow maximal capacity of the edge
@@ -30,8 +29,7 @@ pub struct FlowEdge {
 	rev: usize,  //index of the reversed edge (v, self) in the edge list of vertex v
 }
 
-//Edge data structure for the detection of negative cycles.
-//The graph is stored as a list of edges (u,v).
+///Edge data structure for the detection of negative cycles.
 #[derive(Clone, Copy, Debug)]
 pub struct WeightedEdge {
 	w: i32, //weight of the edge
@@ -42,13 +40,14 @@ pub trait Edge: Clone + Copy {}
 impl Edge for FlowEdge {}
 impl Edge for WeightedEdge {}
 
-//Struct for the graph structure. We do encapsulation here to be able to both
-//provide user friendly Vertex enum to address vertices, and to use usize indices
-//and Vec instead of HashMap in the graph algorithm to optimize execution speed.
+///Struct for the graph structure. We do encapsulation here to be able to both
+///provide user friendly Vertex enum to address vertices, and to use internally usize
+///indices and Vec instead of HashMap in the graph algorithm to optimize execution speed.
 pub struct Graph<E: Edge> {
 	vertextoid: HashMap<Vertex, usize>,
 	idtovertex: Vec<Vertex>,
 
+	//The graph is stored as an adjacency list
 	graph: Vec<Vec<E>>,
 }
 
@@ -69,8 +68,8 @@ impl<E: Edge> Graph<E> {
 }
 
 impl Graph<FlowEdge> {
-	//This function adds a directed edge to the graph with capacity c, and the
-	//corresponding reversed edge with capacity 0.
+	///This function adds a directed edge to the graph with capacity c, and the
+	///corresponding reversed edge with capacity 0.
 	pub fn add_edge(&mut self, u: Vertex, v: Vertex, c: u32) -> Result<(), String> {
 		if !self.vertextoid.contains_key(&u) || !self.vertextoid.contains_key(&v) {
 			return Err("The graph does not contain the provided vertex.".to_string());
@@ -94,8 +93,8 @@ impl Graph<FlowEdge> {
 		Ok(())
 	}
 
-	//This function returns the list of vertices that receive a positive flow from
-	//vertex v.
+	///This function returns the list of vertices that receive a positive flow from
+	///vertex v.
 	pub fn get_positive_flow_from(&self, v: Vertex) -> Result<Vec<Vertex>, String> {
 		if !self.vertextoid.contains_key(&v) {
 			return Err("The graph does not contain the provided vertex.".to_string());
@@ -110,7 +109,7 @@ impl Graph<FlowEdge> {
 		Ok(result)
 	}
 
-	//This function returns the value of the flow incoming to v.
+	///This function returns the value of the flow incoming to v.
 	pub fn get_inflow(&self, v: Vertex) -> Result<i32, String> {
 		if !self.vertextoid.contains_key(&v) {
 			return Err("The graph does not contain the provided vertex.".to_string());
@@ -123,7 +122,7 @@ impl Graph<FlowEdge> {
 		Ok(result)
 	}
 
-	//This function returns the value of the flow outgoing from v.
+	///This function returns the value of the flow outgoing from v.
 	pub fn get_outflow(&self, v: Vertex) -> Result<i32, String> {
 		if !self.vertextoid.contains_key(&v) {
 			return Err("The graph does not contain the provided vertex.".to_string());
@@ -136,14 +135,14 @@ impl Graph<FlowEdge> {
 		Ok(result)
 	}
 
-	//This function computes the flow total value by computing the outgoing flow
-	//from the source.
+	///This function computes the flow total value by computing the outgoing flow
+	///from the source.
 	pub fn get_flow_value(&mut self) -> Result<i32, String> {
 		self.get_outflow(Vertex::Source)
 	}
 
-	//This function shuffles the order of the edge lists. It keeps the ids of the
-	//reversed edges consistent.
+	///This function shuffles the order of the edge lists. It keeps the ids of the
+	///reversed edges consistent.
 	fn shuffle_edges(&mut self) {
 		let mut rng = rand::thread_rng();
 		for i in 0..self.graph.len() {
@@ -157,7 +156,7 @@ impl Graph<FlowEdge> {
 		}
 	}
 
-	//Computes an upper bound of the flow n the graph
+	///Computes an upper bound of the flow on the graph
 	pub fn flow_upper_bound(&self) -> u32 {
 		let idsource = self.vertextoid[&Vertex::Source];
 		let mut flow_upper_bound = 0;
@@ -167,9 +166,9 @@ impl Graph<FlowEdge> {
 		flow_upper_bound
 	}
 
-	//This function computes the maximal flow using Dinic's algorithm. It starts with
-	//the flow values already present in the graph. So it is possible to add some edge to
-	//the graph, compute a flow, add other edges, update the flow.
+	///This function computes the maximal flow using Dinic's algorithm. It starts with
+	///the flow values already present in the graph. So it is possible to add some edge to
+	///the graph, compute a flow, add other edges, update the flow.
 	pub fn compute_maximal_flow(&mut self) -> Result<(), String> {
 		if !self.vertextoid.contains_key(&Vertex::Source) {
 			return Err("The graph does not contain a source.".to_string());
@@ -270,11 +269,11 @@ impl Graph<FlowEdge> {
 		Ok(())
 	}
 
-	//This function takes a flow, and a cost function on the edges, and tries to find an
-	// equivalent flow with a better cost, by finding improving overflow cycles. It uses
-	// as subroutine the Bellman Ford algorithm run up to path_length.
-	// We assume that the cost of edge (u,v) is the opposite of the cost of (v,u), and only
-	// one needs to be present in the cost function.
+	///This function takes a flow, and a cost function on the edges, and tries to find an
+	/// equivalent flow with a better cost, by finding improving overflow cycles. It uses
+	/// as subroutine the Bellman Ford algorithm run up to path_length.
+	/// We assume that the cost of edge (u,v) is the opposite of the cost of (v,u), and
+	/// only one needs to be present in the cost function.
 	pub fn optimize_flow_with_cost(
 		&mut self,
 		cost: &CostFunction,
@@ -309,7 +308,7 @@ impl Graph<FlowEdge> {
 		Ok(())
 	}
 
-	//Construct the weighted graph G_f from the flow and the cost function
+	///Construct the weighted graph G_f from the flow and the cost function
 	fn build_cost_graph(&self, cost: &CostFunction) -> Result<Graph<WeightedEdge>, String> {
 		let mut g = Graph::<WeightedEdge>::new(&self.idtovertex);
 		let nb_vertices = self.idtovertex.len();
@@ -334,7 +333,7 @@ impl Graph<FlowEdge> {
 }
 
 impl Graph<WeightedEdge> {
-	//This function adds a single directed weighted edge to the graph.
+	///This function adds a single directed weighted edge to the graph.
 	pub fn add_edge(&mut self, u: Vertex, v: Vertex, w: i32) -> Result<(), String> {
 		if !self.vertextoid.contains_key(&u) || !self.vertextoid.contains_key(&v) {
 			return Err("The graph does not contain the provided vertex.".to_string());
@@ -345,12 +344,12 @@ impl Graph<WeightedEdge> {
 		Ok(())
 	}
 
-	//This function lists the negative cycles it manages to find after path_length
-	//iterations of the main loop of the Bellman-Ford algorithm. For the classical
-	//algorithm, path_length needs to be equal to the number of vertices. However,
-	//for particular graph structures like our case, the algorithm is still correct
-	//when path_length is the length of the longest possible simple path.
-	//See the formal description of the algorithm for more details.
+	///This function lists the negative cycles it manages to find after path_length
+	///iterations of the main loop of the Bellman-Ford algorithm. For the classical
+	///algorithm, path_length needs to be equal to the number of vertices. However,
+	///for particular graph structures like in our case, the algorithm is still correct
+	///when path_length is the length of the longest possible simple path.
+	///See the formal description of the algorithm for more details.
 	fn list_negative_cycles(&self, path_length: usize) -> Vec<Vec<Vertex>> {
 		let nb_vertices = self.graph.len();
 
@@ -384,8 +383,8 @@ impl Graph<WeightedEdge> {
 	}
 }
 
-//This function returns the list of cycles of a directed 1 forest. It does not
-//check for the consistency of the input.
+///This function returns the list of cycles of a directed 1 forest. It does not
+///check for the consistency of the input.
 fn cycles_of_1_forest(forest: &[Option<usize>]) -> Vec<Vec<usize>> {
 	let mut cycles = Vec::<Vec<usize>>::new();
 	let mut time_of_discovery = vec![None; forest.len()];
diff --git a/src/rpc/layout.rs b/src/rpc/layout.rs
index d2ed8af8..38e56b88 100644
--- a/src/rpc/layout.rs
+++ b/src/rpc/layout.rs
@@ -17,6 +17,8 @@ use crate::ring::*;
 
 use std::convert::TryInto;
 
+const NB_PARTITIONS: usize = 1usize << PARTITION_BITS;
+
 //The Message type will be used to collect information on the algorithm.
 type Message = Vec<String>;
 
@@ -28,9 +30,11 @@ pub struct ClusterLayout {
 
 	pub replication_factor: usize,
 
-	//This attribute is only used to retain the previously computed partition size,
-	//to know to what extent does it change with the layout update.
+	///This attribute is only used to retain the previously computed partition size,
+	///to know to what extent does it change with the layout update.
 	pub partition_size: u32,
+	///Parameters used to compute the assignation currently given by
+	///ring_assignation_data
 	pub parameters: LayoutParameters,
 
 	pub roles: LwwMap<Uuid, NodeRoleV>,
@@ -48,8 +52,9 @@ pub struct ClusterLayout {
 	#[serde(with = "serde_bytes")]
 	pub ring_assignation_data: Vec<CompactNodeType>,
 
-	/// Role changes which are staged for the next version of the layout
+	/// Parameters to be used in the next partition assignation computation.
 	pub staged_parameters: Lww<LayoutParameters>,
+	/// Role changes which are staged for the next version of the layout
 	pub staging: LwwMap<Uuid, NodeRoleV>,
 	pub staging_hash: Hash,
 }
@@ -65,8 +70,6 @@ impl AutoCrdt for LayoutParameters {
 	const WARN_IF_DIFFERENT: bool = true;
 }
 
-const NB_PARTITIONS: usize = 1usize << PARTITION_BITS;
-
 #[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Debug, Serialize, Deserialize)]
 pub struct NodeRoleV(pub Option<NodeRole>);
 
@@ -77,12 +80,13 @@ impl AutoCrdt for NodeRoleV {
 /// The user-assigned roles of cluster nodes
 #[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Debug, Serialize, Deserialize)]
 pub struct NodeRole {
-	/// Datacenter at which this entry belong. This information might be used to perform a better
-	/// geodistribution
+	/// Datacenter at which this entry belong. This information is used to
+	/// perform a better geodistribution
 	pub zone: String,
-	/// The (relative) capacity of the node
+	/// The capacity of the node
 	/// If this is set to None, the node does not participate in storing data for the system
 	/// and is only active as an API gateway to other nodes
+	// TODO : change the capacity to u64 and use byte unit input/output
 	pub capacity: Option<u32>,
 	/// A set of tags to recognize the node
 	pub tags: Vec<String>,
@@ -110,6 +114,7 @@ impl NodeRole {
 	}
 }
 
+//Implementation of the ClusterLayout methods unrelated to the assignation algorithm.
 impl ClusterLayout {
 	pub fn new(replication_factor: usize) -> Self {
 		//We set the default zone redundancy to be equal to the replication factor,
@@ -231,7 +236,7 @@ To know the correct value of the new layout version, invoke `garage layout show`
 	}
 
 	///Returns the uuids of the non_gateway nodes in self.node_id_vec.
-	pub fn useful_nodes(&self) -> Vec<Uuid> {
+	pub fn nongateway_nodes(&self) -> Vec<Uuid> {
 		let mut result = Vec::<Uuid>::new();
 		for uuid in self.node_id_vec.iter() {
 			match self.node_role(uuid) {
@@ -291,13 +296,14 @@ To know the correct value of the new layout version, invoke `garage layout show`
 	///Returns the sum of capacities of non gateway nodes in the cluster
 	pub fn get_total_capacity(&self) -> Result<u32, Error> {
 		let mut total_capacity = 0;
-		for uuid in self.useful_nodes().iter() {
+		for uuid in self.nongateway_nodes().iter() {
 			total_capacity += self.get_node_capacity(uuid)?;
 		}
 		Ok(total_capacity)
 	}
 
 	/// Check a cluster layout for internal consistency
+	/// (assignation, roles, parameters, partition size)
 	/// returns true if consistent, false if error
 	pub fn check(&self) -> bool {
 		// Check that the hash of the staging data is correct
@@ -377,7 +383,7 @@ To know the correct value of the new layout version, invoke `garage layout show`
 		//Check that the partition size stored is the one computed by the asignation
 		//algorithm.
 		let cl2 = self.clone();
-		let (_, zone_to_id) = cl2.generate_useful_zone_ids().expect("Critical Error");
+		let (_, zone_to_id) = cl2.generate_nongateway_zone_ids().expect("Critical Error");
 		match cl2.compute_optimal_partition_size(&zone_to_id) {
 			Ok(s) if s != self.partition_size => return false,
 			Err(_) => return false,
@@ -388,6 +394,7 @@ To know the correct value of the new layout version, invoke `garage layout show`
 	}
 }
 
+//Implementation of the ClusterLayout methods related to the assignation algorithm.
 impl ClusterLayout {
 	/// This function calculates a new partition-to-node assignation.
 	/// The computed assignation respects the node replication factor
@@ -397,16 +404,13 @@ impl ClusterLayout {
 	/// the former assignation (if any) to minimize the amount of
 	/// data to be moved.
 	// Staged role changes must be merged with nodes roles before calling this function,
-	// hence it must only be called from apply_staged_changes() and it is not public.
+	// hence it must only be called from apply_staged_changes() and hence is not public.
 	fn calculate_partition_assignation(&mut self) -> Result<Message, Error> {
-		//The nodes might have been updated, some might have been deleted.
-		//So we need to first update the list of nodes and retrieve the
-		//assignation.
-
 		//We update the node ids, since the node role list might have changed with the
-		//changes in the layout. We retrieve the old_assignation reframed with the new ids
+		//changes in the layout. We retrieve the old_assignation reframed with new ids
 		let old_assignation_opt = self.update_node_id_vec()?;
 
+		//We update the parameters
 		self.parameters = self.staged_parameters.get().clone();
 
 		let mut msg = Message::new();
@@ -420,14 +424,14 @@ impl ClusterLayout {
 
 		//We generate for once numerical ids for the zones of non gateway nodes,
 		//to use them as indices in the flow graphs.
-		let (id_to_zone, zone_to_id) = self.generate_useful_zone_ids()?;
+		let (id_to_zone, zone_to_id) = self.generate_nongateway_zone_ids()?;
 
-		let nb_useful_nodes = self.useful_nodes().len();
-		if nb_useful_nodes < self.replication_factor {
+		let nb_nongateway_nodes = self.nongateway_nodes().len();
+		if nb_nongateway_nodes < self.replication_factor {
 			return Err(Error::Message(format!(
 				"The number of nodes with positive \
             capacity ({}) is smaller than the replication factor ({}).",
-				nb_useful_nodes, self.replication_factor
+				nb_nongateway_nodes, self.replication_factor
 			)));
 		}
 		if id_to_zone.len() < self.parameters.zone_redundancy {
@@ -457,6 +461,7 @@ impl ClusterLayout {
 				partition_size
 			));
 		}
+		//We write the partition size.
 		self.partition_size = partition_size;
 
 		if partition_size < 100 {
@@ -467,14 +472,15 @@ impl ClusterLayout {
 			);
 		}
 
-		//We compute a first flow/assignment that is heuristically close to the previous
-		//assignment
-		let mut gflow = self.compute_candidate_assignment(&zone_to_id, &old_assignation_opt)?;
+		//We compute a first flow/assignation that is heuristically close to the previous
+		//assignation
+		let mut gflow = self.compute_candidate_assignation(&zone_to_id, &old_assignation_opt)?;
 		if let Some(assoc) = &old_assignation_opt {
-			//We minimize the distance to the previous assignment.
+			//We minimize the distance to the previous assignation.
 			self.minimize_rebalance_load(&mut gflow, &zone_to_id, assoc)?;
 		}
 
+		//We display statistics of the computation
 		msg.append(&mut self.output_stat(
 			&gflow,
 			&old_assignation_opt,
@@ -538,14 +544,13 @@ impl ClusterLayout {
 		// (2) We retrieve the old association
 		//We rewrite the old association with the new indices. We only consider partition
 		//to node assignations where the node is still in use.
-		let nb_partitions = 1usize << PARTITION_BITS;
-		let mut old_assignation = vec![Vec::<usize>::new(); nb_partitions];
+		let mut old_assignation = vec![Vec::<usize>::new(); NB_PARTITIONS];
 
 		if self.ring_assignation_data.is_empty() {
 			//This is a new association
 			return Ok(None);
 		}
-		if self.ring_assignation_data.len() != nb_partitions * self.replication_factor {
+		if self.ring_assignation_data.len() != NB_PARTITIONS * self.replication_factor {
 			return Err(Error::Message(
 				"The old assignation does not have a size corresponding to \
                 the old replication factor or the number of partitions."
@@ -580,11 +585,11 @@ impl ClusterLayout {
 
 	///This function generates ids for the zone of the nodes appearing in
 	///self.node_id_vec.
-	fn generate_useful_zone_ids(&self) -> Result<(Vec<String>, HashMap<String, usize>), Error> {
+	fn generate_nongateway_zone_ids(&self) -> Result<(Vec<String>, HashMap<String, usize>), Error> {
 		let mut id_to_zone = Vec::<String>::new();
 		let mut zone_to_id = HashMap::<String, usize>::new();
 
-		for uuid in self.useful_nodes().iter() {
+		for uuid in self.nongateway_nodes().iter() {
 			if self.roles.get(uuid) == None {
 				return Err(Error::Message(
 					"The uuid was not found in the node roles (this should \
@@ -603,17 +608,16 @@ impl ClusterLayout {
 	}
 
 	///This function computes by dichotomy the largest realizable partition size, given
-	///the layout.
+	///the layout roles and parameters.
 	fn compute_optimal_partition_size(
 		&self,
 		zone_to_id: &HashMap<String, usize>,
 	) -> Result<u32, Error> {
-		let nb_partitions = 1usize << PARTITION_BITS;
 		let empty_set = HashSet::<(usize, usize)>::new();
 		let mut g = self.generate_flow_graph(1, zone_to_id, &empty_set)?;
 		g.compute_maximal_flow()?;
 		if g.get_flow_value()?
-			< (nb_partitions * self.replication_factor)
+			< (NB_PARTITIONS * self.replication_factor)
 				.try_into()
 				.unwrap()
 		{
@@ -630,7 +634,7 @@ impl ClusterLayout {
 			g = self.generate_flow_graph((s_down + s_up) / 2, zone_to_id, &empty_set)?;
 			g.compute_maximal_flow()?;
 			if g.get_flow_value()?
-				< (nb_partitions * self.replication_factor)
+				< (NB_PARTITIONS * self.replication_factor)
 					.try_into()
 					.unwrap()
 			{
@@ -658,14 +662,21 @@ impl ClusterLayout {
 		vertices
 	}
 
+	///Generates the graph to compute the maximal flow corresponding to the optimal
+	///partition assignation.
+	///exclude_assoc is the set of (partition, node) association that we are forbidden
+	///to use (hence we do not add the corresponding edge to the graph). This parameter
+	///is used to compute a first flow that uses only edges appearing in the previous
+	///assignation. This produces a solution that heuristically should be close to the
+	///previous one.
 	fn generate_flow_graph(
 		&self,
-		size: u32,
+		partition_size: u32,
 		zone_to_id: &HashMap<String, usize>,
 		exclude_assoc: &HashSet<(usize, usize)>,
 	) -> Result<Graph<FlowEdge>, Error> {
 		let vertices =
-			ClusterLayout::generate_graph_vertices(zone_to_id.len(), self.useful_nodes().len());
+			ClusterLayout::generate_graph_vertices(zone_to_id.len(), self.nongateway_nodes().len());
 		let mut g = Graph::<FlowEdge>::new(&vertices);
 		let nb_zones = zone_to_id.len();
 		let redundancy = self.parameters.zone_redundancy;
@@ -685,10 +696,10 @@ impl ClusterLayout {
 				)?;
 			}
 		}
-		for n in 0..self.useful_nodes().len() {
+		for n in 0..self.nongateway_nodes().len() {
 			let node_capacity = self.get_node_capacity(&self.node_id_vec[n])?;
 			let node_zone = zone_to_id[&self.get_node_zone(&self.node_id_vec[n])?];
-			g.add_edge(Vertex::N(n), Vertex::Sink, node_capacity / size)?;
+			g.add_edge(Vertex::N(n), Vertex::Sink, node_capacity / partition_size)?;
 			for p in 0..NB_PARTITIONS {
 				if !exclude_assoc.contains(&(p, n)) {
 					g.add_edge(Vertex::PZ(p, node_zone), Vertex::N(n), 1)?;
@@ -698,28 +709,34 @@ impl ClusterLayout {
 		Ok(g)
 	}
 
-	fn compute_candidate_assignment(
+	///This function computes a first optimal assignation (in the form of a flow graph).
+	fn compute_candidate_assignation(
 		&self,
 		zone_to_id: &HashMap<String, usize>,
-		old_assoc_opt: &Option<Vec<Vec<usize>>>,
+		prev_assign_opt: &Option<Vec<Vec<usize>>>,
 	) -> Result<Graph<FlowEdge>, Error> {
-		//We list the edges that are not used in the old association
+		//We list the (partition,node) associations that are not used in the
+		//previous assignation
 		let mut exclude_edge = HashSet::<(usize, usize)>::new();
-		if let Some(old_assoc) = old_assoc_opt {
-			let nb_nodes = self.useful_nodes().len();
-			for (p, old_assoc_p) in old_assoc.iter().enumerate() {
+		if let Some(prev_assign) = prev_assign_opt {
+			let nb_nodes = self.nongateway_nodes().len();
+			for (p, prev_assign_p) in prev_assign.iter().enumerate() {
 				for n in 0..nb_nodes {
 					exclude_edge.insert((p, n));
 				}
-				for n in old_assoc_p.iter() {
+				for n in prev_assign_p.iter() {
 					exclude_edge.remove(&(p, *n));
 				}
 			}
 		}
 
-		//We compute the best flow using only the edges used in the old assoc
+		//We compute the best flow using only the edges used in the previous assignation
 		let mut g = self.generate_flow_graph(self.partition_size, zone_to_id, &exclude_edge)?;
 		g.compute_maximal_flow()?;
+
+		//We add the excluded edges and compute the maximal flow with the full graph.
+		//The algorithm is such that it will start with the flow that we just computed
+		//and find ameliorating paths from that.
 		for (p, n) in exclude_edge.iter() {
 			let node_zone = zone_to_id[&self.get_node_zone(&self.node_id_vec[*n])?];
 			g.add_edge(Vertex::PZ(*p, node_zone), Vertex::N(*n), 1)?;
@@ -728,26 +745,35 @@ impl ClusterLayout {
 		Ok(g)
 	}
 
+	///This function updates the flow graph gflow to minimize the distance between
+	///its corresponding assignation and the previous one
 	fn minimize_rebalance_load(
 		&self,
 		gflow: &mut Graph<FlowEdge>,
 		zone_to_id: &HashMap<String, usize>,
-		old_assoc: &[Vec<usize>],
+		prev_assign: &[Vec<usize>],
 	) -> Result<(), Error> {
+		//We define a cost function on the edges (pairs of vertices) corresponding
+		//to the distance between the two assignations.
 		let mut cost = CostFunction::new();
-		for (p, assoc_p) in old_assoc.iter().enumerate() {
+		for (p, assoc_p) in prev_assign.iter().enumerate() {
 			for n in assoc_p.iter() {
 				let node_zone = zone_to_id[&self.get_node_zone(&self.node_id_vec[*n])?];
 				cost.insert((Vertex::PZ(p, node_zone), Vertex::N(*n)), -1);
 			}
 		}
-		let nb_nodes = self.useful_nodes().len();
+
+		//We compute the maximal length of a simple path in gflow. It is used in the
+		//Bellman-Ford algorithm in optimize_flow_with_cost to set the number
+		//of iterations.
+		let nb_nodes = self.nongateway_nodes().len();
 		let path_length = 4 * nb_nodes;
 		gflow.optimize_flow_with_cost(&cost, path_length)?;
 
 		Ok(())
 	}
 
+	///This function updates the assignation ring from the flow graph.
 	fn update_ring_from_flow(
 		&mut self,
 		nb_zones: usize,
@@ -775,19 +801,18 @@ impl ClusterLayout {
 		Ok(())
 	}
 
-	//This function returns a message summing up the partition repartition of the new
-	//layout.
+	///This function returns a message summing up the partition repartition of the new
+	///layout, and other statistics of the partition assignation computation.
 	fn output_stat(
 		&self,
 		gflow: &Graph<FlowEdge>,
-		old_assoc_opt: &Option<Vec<Vec<usize>>>,
+		prev_assign_opt: &Option<Vec<Vec<usize>>>,
 		zone_to_id: &HashMap<String, usize>,
 		id_to_zone: &[String],
 	) -> Result<Message, Error> {
 		let mut msg = Message::new();
 
-		let nb_partitions = 1usize << PARTITION_BITS;
-		let used_cap = self.partition_size * nb_partitions as u32 * self.replication_factor as u32;
+		let used_cap = self.partition_size * NB_PARTITIONS as u32 * self.replication_factor as u32;
 		let total_cap = self.get_total_capacity()?;
 		let percent_cap = 100.0 * (used_cap as f32) / (total_cap as f32);
 		msg.push("".into());
@@ -813,21 +838,21 @@ impl ClusterLayout {
 		));
 
 		//We define and fill in the following tables
-		let storing_nodes = self.useful_nodes();
+		let storing_nodes = self.nongateway_nodes();
 		let mut new_partitions = vec![0; storing_nodes.len()];
 		let mut stored_partitions = vec![0; storing_nodes.len()];
 
 		let mut new_partitions_zone = vec![0; id_to_zone.len()];
 		let mut stored_partitions_zone = vec![0; id_to_zone.len()];
 
-		for p in 0..nb_partitions {
+		for p in 0..NB_PARTITIONS {
 			for z in 0..id_to_zone.len() {
 				let pz_nodes = gflow.get_positive_flow_from(Vertex::PZ(p, z))?;
 				if !pz_nodes.is_empty() {
 					stored_partitions_zone[z] += 1;
-					if let Some(old_assoc) = old_assoc_opt {
+					if let Some(prev_assign) = prev_assign_opt {
 						let mut old_zones_of_p = Vec::<usize>::new();
-						for n in old_assoc[p].iter() {
+						for n in prev_assign[p].iter() {
 							old_zones_of_p
 								.push(zone_to_id[&self.get_node_zone(&self.node_id_vec[*n])?]);
 						}
@@ -839,8 +864,8 @@ impl ClusterLayout {
 				for vert in pz_nodes.iter() {
 					if let Vertex::N(n) = *vert {
 						stored_partitions[n] += 1;
-						if let Some(old_assoc) = old_assoc_opt {
-							if !old_assoc[p].contains(&n) {
+						if let Some(prev_assign) = prev_assign_opt {
+							if !prev_assign[p].contains(&n) {
 								new_partitions[n] += 1;
 							}
 						}
@@ -849,7 +874,7 @@ impl ClusterLayout {
 			}
 		}
 
-		if *old_assoc_opt == None {
+		if *prev_assign_opt == None {
 			new_partitions = stored_partitions.clone();
 			new_partitions_zone = stored_partitions_zone.clone();
 		}
@@ -857,7 +882,7 @@ impl ClusterLayout {
 		//We display the statistics
 
 		msg.push("".into());
-		if *old_assoc_opt != None {
+		if *prev_assign_opt != None {
 			let total_new_partitions: usize = new_partitions.iter().sum();
 			msg.push(format!(
 				"A total of {} new copies of partitions need to be \
@@ -950,9 +975,8 @@ mod tests {
 	fn check_against_naive(cl: &ClusterLayout) -> Result<bool, Error> {
 		let over_size = cl.partition_size + 1;
 		let mut zone_token = HashMap::<String, usize>::new();
-		let nb_partitions = 1usize << PARTITION_BITS;
 
-		let (zones, zone_to_id) = cl.generate_useful_zone_ids()?;
+		let (zones, zone_to_id) = cl.generate_nongateway_zone_ids()?;
 
 		if zones.is_empty() {
 			return Ok(false);
@@ -961,12 +985,12 @@ mod tests {
 		for z in zones.iter() {
 			zone_token.insert(z.clone(), 0);
 		}
-		for uuid in cl.useful_nodes().iter() {
+		for uuid in cl.nongateway_nodes().iter() {
 			let z = cl.get_node_zone(uuid)?;
 			let c = cl.get_node_capacity(uuid)?;
 			zone_token.insert(
 				z.clone(),
-				zone_token[&z] + min(nb_partitions, (c / over_size) as usize),
+				zone_token[&z] + min(NB_PARTITIONS, (c / over_size) as usize),
 			);
 		}
 
@@ -978,15 +1002,15 @@ mod tests {
 			id_zone_token[zone_to_id[z]] = *t;
 		}
 
-		let mut nb_token = vec![0; nb_partitions];
-		let mut last_zone = vec![zones.len(); nb_partitions];
+		let mut nb_token = vec![0; NB_PARTITIONS];
+		let mut last_zone = vec![zones.len(); NB_PARTITIONS];
 
 		let mut curr_zone = 0;
 
 		let redundancy = cl.parameters.zone_redundancy;
 
 		for replic in 0..cl.replication_factor {
-			for p in 0..nb_partitions {
+			for p in 0..NB_PARTITIONS {
 				while id_zone_token[curr_zone] == 0
 					|| (last_zone[p] == curr_zone
 						&& redundancy - nb_token[p] <= cl.replication_factor - replic)