From 98acbcc2ea6af60d64b96cd46c4eb446e03a7510 Mon Sep 17 00:00:00 2001 From: =?utf8?q?S=C3=A9bastien=20Miqu=C3=A9e?= Date: Wed, 24 Feb 2010 13:54:37 +0100 Subject: [PATCH] Implementation of fault tolerance functions in all algorithms. - In DefaultMapping, it returns in both cases the next node in the list. - In QM, it returns the best computing power node for the replacement, and a node from the cluster which has the most amount of free nodes for another node. - In LSM (Edge-cuts), it returns the nearest node for the replacement, and a node from the cluster which has the most amount of free nodes for another node. - Simple does the same thing as DefaultMapping. --- src/and/Mapping/DefaultMapping.java | 1 + src/and/Mapping/Grid.java | 2 + src/and/Mapping/LSM.java | 80 ++++++++++++++++++++- src/and/Mapping/QM.java | 108 ++++++++++++++++++++++++++-- src/and/Mapping/Simple.java | 41 +++++++++-- 5 files changed, 219 insertions(+), 13 deletions(-) diff --git a/src/and/Mapping/DefaultMapping.java b/src/and/Mapping/DefaultMapping.java index e03cfce..2f096b8 100644 --- a/src/and/Mapping/DefaultMapping.java +++ b/src/and/Mapping/DefaultMapping.java @@ -103,6 +103,7 @@ public class DefaultMapping extends Algo @Override public GNode getOtherGNode( ArrayList _ag ) { + /** Returning the first node in the list **/ if( _ag.size() > 0 ) { return _ag.get( 1 ) ; diff --git a/src/and/Mapping/Grid.java b/src/and/Mapping/Grid.java index 877ac33..d93b65e 100644 --- a/src/and/Mapping/Grid.java +++ b/src/and/Mapping/Grid.java @@ -325,8 +325,10 @@ public class Grid implements Serializable { if( _g != null ) { + /** Change in the cluster **/ getClusterOfNode( _g ).setGNodeStatus( _g, _status ) ; + /** Change in local list **/ for( int i = 0 ; i < gnodesList.size() ; i++ ) { if( _g.getId() == gnodesList.get( i ).getId() ) diff --git a/src/and/Mapping/LSM.java b/src/and/Mapping/LSM.java index 75657c3..0ac63a5 100644 --- a/src/and/Mapping/LSM.java +++ b/src/and/Mapping/LSM.java @@ -420,14 +420,54 @@ public class LSM extends Algo if( _dead != null ) { ArrayList ac = new ArrayList() ; + GNode tmp = null ; + /** Searching if clusters have some free nodes **/ for( int i = 0 ; i < gl.getNbCluster() ; i++ ) { if( gl.getClusters().get( i ).getNbFreeNodes() > 0 ) { - ac.add( gl.getClusters().get( i ).nextGNode() ) ; + tmp = gl.getClusters().get( i ).nextGNode() ; + + if( tmp != null ) + { + ac.add( tmp ) ; + } } } + + /** If there some nodes in clusters **/ + if( ac.size() > 0 ) + { + double dist = -1, best = -1 ; + int bestNode = -1 ; + + /** Searching the replacing node with the lower distance + * between it and the failed node + */ + for( int i = 0 ; i < ac.size() ; i++ ) + { + dist = gl.getDistance( _dead, ac.get( i ) ) ; + + if( best == -1 ) + { + best = dist ; + bestNode = i ; + } else { + if( dist < best ) + { + best = dist ; + bestNode = i ; + } + } + } + + /** Is there any node candidate ? **/ + if( bestNode != -1 ) + { + ret = ac.get( bestNode ) ; + } + } } /** Update in cluster the status of nodes **/ @@ -440,8 +480,44 @@ public class LSM extends Algo @Override public GNode getOtherGNode( ArrayList _ag ) { + GNode ret = null ; - return null; + /** Updating the grid if there is any modification **/ + if( _ag != null && _ag.size() != 0 ) + { + gl.updateGrid( _ag ) ; + } + + int free[] = new int[ gl.getNbCluster() ] ; + + /** Searching if clusters have some free nodes **/ + for( int i = 0 ; i < gl.getNbCluster() ; i++ ) + { + free[ i ] = gl.getClusters().get( i ).getNbFreeNodes() ; + } + + /** Returning a node from the cluster which has the most + * available nodes + */ + int most = -1, max = 0 ; + + for( int i = 0 ; i < free.length ; i++ ) + { + if( free[ i ] > max ) + { + max = free[ i ] ; + most = i ; + } + } + + /** Is there any cluster candidate ? **/ + if( most != -1 ) + { + ret = gl.getClusters().get( most ).nextGNode() ; + } + + + return ret ; } } diff --git a/src/and/Mapping/QM.java b/src/and/Mapping/QM.java index 70799f2..6483cd8 100644 --- a/src/and/Mapping/QM.java +++ b/src/and/Mapping/QM.java @@ -512,16 +512,116 @@ public class QM extends Algo @Override public GNode replaceNode(GNode _dead, ArrayList _ag ) { + GNode ret = null ; + + /** Updating the grid if there is any modification **/ + if( _ag != null && _ag.size() != 0 ) + { + gl.updateGrid( _ag ) ; + } + + /** If something has to be done **/ + if( _dead != null ) + { + ArrayList ac = new ArrayList() ; + GNode tmp = null ; + + /** Searching if clusters have some free nodes **/ + for( int i = 0 ; i < gl.getNbCluster() ; i++ ) + { + if( gl.getClusters().get( i ).getNbFreeNodes() > 0 ) + { + tmp = gl.getClusters().get( i ).nextGNode() ; + + if( tmp != null ) + { + ac.add( tmp ) ; + } + } + } + + /** If there some nodes in clusters **/ + if( ac.size() > 0 ) + { + double power = -1, best = -1 ; + int bestNode = -1 ; + + /** Searching the replacing node with the higher + * computing power + */ + for( int i = 0 ; i < ac.size() ; i++ ) + { + power = ac.get( i ).getPower() ; + + if( best == -1 ) + { + best = power ; + bestNode = i ; + } else { + if( power < best ) + { + best = power ; + bestNode = i ; + } + } + } + + /** Is there any node candidate ? **/ + if( bestNode != -1 ) + { + ret = ac.get( bestNode ) ; + } + } + } + /** Update in cluster the status of nodes **/ updateGrid() ; - return null; + + return ret ; } @Override - public GNode getOtherGNode( ArrayList _ag ) { - // TODO Auto-generated method stub - return null; + public GNode getOtherGNode( ArrayList _ag ) + { + GNode ret = null ; + + /** Updating the grid if there is any modification **/ + if( _ag != null && _ag.size() != 0 ) + { + gl.updateGrid( _ag ) ; + } + + int free[] = new int[ gl.getNbCluster() ] ; + + /** Searching if clusters have some free nodes **/ + for( int i = 0 ; i < gl.getNbCluster() ; i++ ) + { + free[ i ] = gl.getClusters().get( i ).getNbFreeNodes() ; + } + + /** Returning a node from the cluster which has the most + * available nodes + */ + int most = -1, max = 0 ; + + for( int i = 0 ; i < free.length ; i++ ) + { + if( free[ i ] > max ) + { + max = free[ i ] ; + most = i ; + } + } + + /** Is there any cluster candidate ? **/ + if( most != -1 ) + { + ret = gl.getClusters().get( most ).nextGNode() ; + } + + + return ret ; } } diff --git a/src/and/Mapping/Simple.java b/src/and/Mapping/Simple.java index 8bf957a..3092a99 100644 --- a/src/and/Mapping/Simple.java +++ b/src/and/Mapping/Simple.java @@ -119,22 +119,49 @@ public class Simple extends Algo @Override - public GNode replaceNode(GNode replaced, ArrayList _ag ) + public GNode replaceNode(GNode _dead, ArrayList _ag ) { - // TODO + GNode ret = null ; + + if( _dead != null ) + { + int pos = 0 ; + pos = mp.getIdOfAssociation( _dead ) ; + + if( pos == -1 ) + { + System.err.println( "GNode "+_dead+" does not exist in the mapping!" ) ; + return null ; + } + + if( _ag.size() > 0 ) + { + ret = _ag.get( 0 ) ; + + + } else { + System.err.println( "Not enought available nodes in gnodes to replace one !" ) ; + return null ; + } + } /** Update in cluster the status of nodes **/ updateGrid() ; - - return null ; + return ret ; } @Override - public GNode getOtherGNode( ArrayList _ag ) { - // TODO Auto-generated method stub - return null; + public GNode getOtherGNode( ArrayList _ag ) + { + /** Returning the first node in the list **/ + if( _ag.size() > 0 ) + { + return _ag.get( 1 ) ; + } + + return null ; } } -- 2.20.1