nemo-impl/src/main/java/org/opendaylight/nemo/intent/computation/VNComputationUnit.java

   1 /*\r
   2  * Copyright (c) 2015 Huawei, Inc. and others. All rights reserved.\r
   3  *\r
   4  * This program and the accompanying materials are made available under the\r
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,\r
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html\r
   7  */\r
   8 \r
   9 package org.opendaylight.nemo.intent.computation;\r
  10 \r
  11 import java.util.ArrayList;\r
  12 import java.util.HashMap;\r
  13 import java.util.HashSet;\r
  14 import java.util.List;\r
  15 import java.util.Map;\r
  16 import java.util.Set;\r
  17 import java.util.UUID;\r
  18 import java.util.concurrent.ExecutionException;\r
  19 \r
  20 import org.opendaylight.controller.md.sal.binding.api.DataBroker;\r
  21 import org.opendaylight.controller.md.sal.binding.api.DataChangeListener;\r
  22 import org.opendaylight.controller.md.sal.binding.api.ReadWriteTransaction;\r
  23 import org.opendaylight.controller.md.sal.common.api.data.AsyncDataBroker.DataChangeScope;\r
  24 import org.opendaylight.controller.md.sal.common.api.data.AsyncDataChangeEvent;\r
  25 import org.opendaylight.controller.md.sal.common.api.data.LogicalDatastoreType;\r
  26 import org.opendaylight.nemo.intent.algorithm.Edge;\r
  27 import org.opendaylight.nemo.intent.algorithm.RoutingAlgorithm;\r
  28 import org.opendaylight.nemo.intent.algorithm.Vertex;\r
  29 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.VirtualNetworks;\r
  30 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.networks.VirtualNetwork;\r
  31 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.networks.VirtualNetworkKey;\r
  32 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.networks.virtual.network.VirtualLinks;\r
  33 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.networks.virtual.network.VirtualNodes;\r
  34 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.networks.virtual.network.VirtualPaths;\r
  35 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.networks.virtual.network.VirtualRoutes;\r
  36 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.networks.virtual.network.virtual.links.VirtualLink;\r
  37 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.networks.virtual.network.virtual.nodes.VirtualNode;\r
  38 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.networks.virtual.network.virtual.paths.VirtualPath;\r
  39 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.networks.virtual.network.virtual.paths.VirtualPathBuilder;\r
  40 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.networks.virtual.network.virtual.paths.VirtualPathKey;\r
  41 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.networks.virtual.network.virtual.routes.VirtualRoute;\r
  42 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.networks.virtual.network.virtual.routes.VirtualRouteBuilder;\r
  43 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.networks.virtual.network.virtual.routes.VirtualRouteKey;\r
  44 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.path.instance.VirtualLinkBuilder;\r
  45 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.nemo.common.rev151010.UserId;\r
  46 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.nemo.engine.common.rev151010.VirtualLinkId;\r
  47 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.nemo.engine.common.rev151010.VirtualNetworkId;\r
  48 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.nemo.engine.common.rev151010.VirtualNodeId;\r
  49 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.nemo.engine.common.rev151010.VirtualPathId;\r
  50 import org.opendaylight.yangtools.concepts.ListenerRegistration;\r
  51 import org.opendaylight.yangtools.yang.binding.DataObject;\r
  52 import org.opendaylight.yangtools.yang.binding.InstanceIdentifier;\r
  53 import org.slf4j.Logger;\r
  54 import org.slf4j.LoggerFactory;\r
  55 \r
  56 import com.google.common.base.Optional;\r
  57 \r
  58 /**\r
  59  * The virtual network computation unit implements the following functions:\r
  60  * (1) Maintain a user's virtual network topology information generated in\r
  61  *     terms of the user's intents through subscribing from the data store.\r
  62  * (2) Automatically recompute all routes of the virtual network when it\r
  63  *     changed, and store or update the routes into the data store.\r
  64  * (3) Provide the path computation with SLA constraints to any other modules\r
  65  *     that need it.\r
  66  *\r
  67  * @author Zhigang Ji\r
  68  */\r
  69 public class VNComputationUnit implements AutoCloseable {\r
  70     private static final Logger LOG = LoggerFactory.getLogger(VNComputationUnit.class);\r
  71 \r
  72     private final DataBroker dataBroker;\r
  73 \r
  74     /**\r
  75      * The user id for the virtual network maintained by\r
  76      * this computation unit.\r
  77      */\r
  78     private UserId userId;\r
  79 \r
  80     /**\r
  81      * The routing algorithm instance.\r
  82      */\r
  83     private RoutingAlgorithm routingAlgorithm;\r
  84 \r
  85     /**\r
  86      * The virtual routers in the virtual network.\r
  87      */\r
  88     private Set<VirtualNodeId> virtualRouters;\r
  89 \r
  90     /**\r
  91      * The registration for the virtual node change listener.\r
  92      */\r
  93     private ListenerRegistration<DataChangeListener> virtualNodeChangeListenerReg;\r
  94 \r
  95     /**\r
  96      * The registration for the virtual link change listener.\r
  97      */\r
  98     private ListenerRegistration<DataChangeListener> virtualLinkChangeListenerReg;\r
  99 \r
 100     public VNComputationUnit(DataBroker dataBroker, UserId userId) {\r
 101         super();\r
 102 \r
 103         this.dataBroker = dataBroker;\r
 104         this.userId = userId;\r
 105         routingAlgorithm = new RoutingAlgorithm();\r
 106         virtualRouters = new HashSet<VirtualNodeId>();\r
 107 \r
 108         VirtualNetworkKey virtualNetworkKey = new VirtualNetworkKey(new VirtualNetworkId(userId.getValue()));\r
 109         InstanceIdentifier<VirtualNode> virtualNodeIid = InstanceIdentifier\r
 110                 .builder(VirtualNetworks.class)\r
 111                 .child(VirtualNetwork.class, virtualNetworkKey)\r
 112                 .child(VirtualNodes.class)\r
 113                 .child(VirtualNode.class)\r
 114                 .build();\r
 115         InstanceIdentifier<VirtualLink> virtualLinkIid = InstanceIdentifier\r
 116                 .builder(VirtualNetworks.class)\r
 117                 .child(VirtualNetwork.class, virtualNetworkKey)\r
 118                 .child(VirtualLinks.class)\r
 119                 .child(VirtualLink.class)\r
 120                 .build();\r
 121 \r
 122         virtualNodeChangeListenerReg = dataBroker.registerDataChangeListener(LogicalDatastoreType.CONFIGURATION,\r
 123                 virtualNodeIid, new VirtualNodeChangeListener(), DataChangeScope.BASE);\r
 124         virtualLinkChangeListenerReg = dataBroker.registerDataChangeListener(LogicalDatastoreType.CONFIGURATION,\r
 125                 virtualLinkIid, new VirtualLinkChangeListener(), DataChangeScope.BASE);\r
 126 \r
 127         LOG.debug("Initialized the virtual network computation unit for the user {}.", userId.getValue());\r
 128 \r
 129         return;\r
 130     }\r
 131 \r
 132     public VNComputationUnit(DataBroker dataBroker, VirtualNetwork virtualNetwork) {\r
 133         super();\r
 134 \r
 135         this.dataBroker = dataBroker;\r
 136         userId = virtualNetwork.getUserId();\r
 137         routingAlgorithm = new RoutingAlgorithm();\r
 138         virtualRouters = new HashSet<VirtualNodeId>();\r
 139 \r
 140         List<VirtualNode> virtualNodes = virtualNetwork.getVirtualNodes().getVirtualNode();\r
 141         Vertex vertex;\r
 142 \r
 143         for ( VirtualNode virtualNode : virtualNodes ) {\r
 144             vertex = new Vertex(virtualNode.getNodeId().getValue());\r
 145             routingAlgorithm.addVertex(vertex);\r
 146 \r
 147             if ( VirtualNode.NodeType.Vrouter == virtualNode.getNodeType() ) {\r
 148                 virtualRouters.add(virtualNode.getNodeId());\r
 149             }\r
 150         }\r
 151 \r
 152         List<VirtualLink> virtualLinks = virtualNetwork.getVirtualLinks().getVirtualLink();\r
 153 \r
 154 \r
 155         for ( VirtualLink virtualLink : virtualLinks ) {\r
 156             routingAlgorithm.addEdge(new Edge(virtualLink));\r
 157         }\r
 158 \r
 159 //        computeRoute(virtualNetwork);\r
 160 \r
 161         return;\r
 162     }\r
 163 \r
 164     /**\r
 165      * Compute a shortest virtual path from the given source vertex to\r
 166      * target one without any constraint.\r
 167      *\r
 168      * @param source The given source virtual node id.\r
 169      * @param target The given target virtual node id.\r
 170      * @return The virtual path if successful，or null otherwise.\r
 171      */\r
 172     public VirtualPath computePath(VirtualNodeId source, VirtualNodeId target) {\r
 173         List<Edge> edges = routingAlgorithm.computePath(routingAlgorithm.getVertex(source.getValue()),\r
 174                 routingAlgorithm.getVertex(target.getValue()));\r
 175 \r
 176         if ( null == edges || edges.isEmpty() ) {\r
 177             return null;\r
 178         }\r
 179 \r
 180         List<org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.path.instance.VirtualLink> virtualLinks =\r
 181                 new ArrayList<org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.path.instance.VirtualLink>(edges.size());\r
 182         org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.path.instance.VirtualLink virtualLink;\r
 183         long metric = 0;\r
 184         long delay = 0;\r
 185 \r
 186         for ( Edge edge : edges ) {\r
 187             virtualLink = new VirtualLinkBuilder()\r
 188                     .setLinkId(new VirtualLinkId(edge.getId()))\r
 189                     .setOrder((long) virtualLinks.size())\r
 190                     .build();\r
 191             virtualLinks.add(virtualLink);\r
 192 \r
 193             metric += edge.getMetric();\r
 194 //            delay += edge.getDelay();\r
 195         }\r
 196 \r
 197         VirtualPath virtualPath = new VirtualPathBuilder()\r
 198                 .setPathId(new VirtualPathId(UUID.randomUUID().toString()))\r
 199                 .setVirtualLink(virtualLinks)\r
 200                 .setMetric(metric)\r
 201                 .setBandwidth(0L)\r
 202                 .setDelay(delay)\r
 203                 .build();\r
 204 \r
 205         return virtualPath;\r
 206     }\r
 207 \r
 208     /**\r
 209      * Compute a shortest virtual path with the given bandwidth from the\r
 210      * given source vertex to target one.\r
 211      *\r
 212      * @param source The given source virtual node id.\r
 213      * @param target The given target virtual node id.\r
 214      * @param bandwidth The given bandwidth for the virtual path.\r
 215      * @return The virtual path if successful，or null otherwise.\r
 216      */\r
 217     public VirtualPath computePath(VirtualNodeId source, VirtualNodeId target, long bandwidth) {\r
 218         List<Edge> edges = routingAlgorithm.computePath(routingAlgorithm.getVertex(source.getValue()),\r
 219                 routingAlgorithm.getVertex(target.getValue()), bandwidth);\r
 220 \r
 221         if ( null == edges || edges.isEmpty() ) {\r
 222             return null;\r
 223         }\r
 224 \r
 225         List<org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.path.instance.VirtualLink> virtualLinks =\r
 226                 new ArrayList<org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.path.instance.VirtualLink>(edges.size());\r
 227         org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.generic.virtual.network.rev151010.virtual.path.instance.VirtualLink virtualLink;\r
 228         long metric = 0;\r
 229         long delay = 0;\r
 230 \r
 231         for ( Edge edge : edges ) {\r
 232             edge.setBandwidth(edge.getBandwidth() - bandwidth);\r
 233             routingAlgorithm.updateEdge(edge);\r
 234 \r
 235             virtualLink = new VirtualLinkBuilder()\r
 236                     .setLinkId(new VirtualLinkId(edge.getId()))\r
 237                     .setOrder((long)virtualLinks.size())\r
 238                     .build();\r
 239             virtualLinks.add(virtualLink);\r
 240 \r
 241             metric += edge.getMetric();\r
 242 //            delay += edge.getDelay();\r
 243         }\r
 244 \r
 245         VirtualPath virtualPath = new VirtualPathBuilder()\r
 246                 .setPathId(new VirtualPathId(UUID.randomUUID().toString()))\r
 247                 .setVirtualLink(virtualLinks)\r
 248                 .setMetric(metric)\r
 249                 .setBandwidth(bandwidth)\r
 250                 .setDelay(delay)\r
 251                 .build();\r
 252 \r
 253         return virtualPath;\r
 254     }\r
 255 \r
 256     @Override\r
 257     public void close() throws Exception {\r
 258         if ( null != virtualNodeChangeListenerReg ) {\r
 259             virtualNodeChangeListenerReg.close();\r
 260         }\r
 261 \r
 262         if ( null != virtualLinkChangeListenerReg ) {\r
 263             virtualLinkChangeListenerReg.close();\r
 264         }\r
 265 \r
 266         return;\r
 267     }\r
 268 \r
 269     /**\r
 270      * Compute the routes between all virtual routers in the virtual\r
 271      * network, and store or update them into the data store.\r
 272      */\r
 273     private void computeRoute() {\r
 274         Map<VirtualRouteKey, VirtualPath> routes = new HashMap<VirtualRouteKey, VirtualPath>();\r
 275         VirtualPath virtualPath;\r
 276 \r
 277         for ( VirtualNodeId source : virtualRouters ) {\r
 278             for ( VirtualNodeId target : virtualRouters ) {\r
 279                 if ( !source.equals(target) ) {\r
 280                     virtualPath = computePath(source, target);\r
 281 \r
 282                     if ( null == virtualPath ) {\r
 283                         continue;\r
 284                     }\r
 285 \r
 286                     routes.put(new VirtualRouteKey(source, target), virtualPath);\r
 287                 }\r
 288             }\r
 289         }\r
 290 \r
 291         updateRoute(routes);\r
 292 \r
 293         return;\r
 294     }\r
 295 \r
 296     /**\r
 297      * Compute the routes between all virtual routers in the virtual\r
 298      * network, and store them into the virtual network.\r
 299      *\r
 300      * @param virtualNetwork The virtual network to store the routes.\r
 301      */\r
 302     private void computeRoute(VirtualNetwork virtualNetwork) {\r
 303         List<VirtualRoute> virtualRoutes = virtualNetwork.getVirtualRoutes().getVirtualRoute();\r
 304         List<VirtualPath> virtualPaths = virtualNetwork.getVirtualPaths().getVirtualPath();\r
 305         VirtualRoute virtualRoute;\r
 306         VirtualPath virtualPath;\r
 307 \r
 308         for ( VirtualNodeId source : virtualRouters ) {\r
 309             for ( VirtualNodeId target : virtualRouters ) {\r
 310                 if ( !source.equals(target) ) {\r
 311                     virtualPath = computePath(source, target);\r
 312 \r
 313                     if ( null == virtualPath ) {\r
 314                         continue;\r
 315                     }\r
 316 \r
 317                     virtualRoute = new VirtualRouteBuilder().setSrcNodeId(source)\r
 318                             .setDestNodeId(target)\r
 319                             .setPathId(virtualPath.getPathId())\r
 320                             .build();\r
 321 \r
 322                     virtualPaths.add(virtualPath);\r
 323                     virtualRoutes.add(virtualRoute);\r
 324                 }\r
 325             }\r
 326         }\r
 327 \r
 328         return;\r
 329     }\r
 330 \r
 331     /**\r
 332      * Update the given routes into the data store. If the route\r
 333      * already exists, remove it's old virtual path and store the\r
 334      * given new one into the data store.\r
 335      *\r
 336      * @param routes The given routes to be updated.\r
 337      */\r
 338     private void updateRoute(Map<VirtualRouteKey, VirtualPath> routes) {\r
 339         ReadWriteTransaction readWriteTransaction = dataBroker.newReadWriteTransaction();\r
 340 \r
 341         VirtualNetworkKey virtualNetworkKey = new VirtualNetworkKey(new VirtualNetworkId(userId.getValue()));\r
 342         InstanceIdentifier<VirtualRoute> virtualRouteIid;\r
 343         InstanceIdentifier<VirtualPath> virtualPathIid;\r
 344         Optional<VirtualRoute> result;\r
 345         VirtualRoute virtualRoute;\r
 346 \r
 347         for ( Map.Entry<VirtualRouteKey, VirtualPath> route : routes.entrySet() ) {\r
 348             virtualRouteIid = InstanceIdentifier.builder(VirtualNetworks.class)\r
 349                     .child(VirtualNetwork.class, virtualNetworkKey)\r
 350                     .child(VirtualRoutes.class)\r
 351                     .child(VirtualRoute.class, route.getKey())\r
 352                     .build();\r
 353 \r
 354             try {\r
 355                 result = readWriteTransaction.read(LogicalDatastoreType.CONFIGURATION, virtualRouteIid).get();\r
 356             } catch ( InterruptedException | ExecutionException exception ) {\r
 357                 LOG.error("Can not read the virtual route from the virtual node {} to {}.",\r
 358                         route.getKey().getSrcNodeId().getValue(), route.getKey().getDestNodeId().getValue());\r
 359 \r
 360                 continue;\r
 361             }\r
 362 \r
 363             if ( result.isPresent() ) {\r
 364                 virtualRoute = result.get();\r
 365                 virtualPathIid = InstanceIdentifier.builder(VirtualNetworks.class)\r
 366                         .child(VirtualNetwork.class, virtualNetworkKey)\r
 367                         .child(VirtualPaths.class)\r
 368                         .child(VirtualPath.class, new VirtualPathKey(virtualRoute.getPathId()))\r
 369                         .build();\r
 370                 readWriteTransaction.delete(LogicalDatastoreType.CONFIGURATION, virtualPathIid);\r
 371             }\r
 372 \r
 373             virtualPathIid = InstanceIdentifier.builder(VirtualNetworks.class)\r
 374                     .child(VirtualNetwork.class, virtualNetworkKey)\r
 375                     .child(VirtualPaths.class)\r
 376                     .child(VirtualPath.class, route.getValue().getKey())\r
 377                     .build();\r
 378             readWriteTransaction.put(LogicalDatastoreType.CONFIGURATION, virtualPathIid, route.getValue(), true);\r
 379 \r
 380             virtualRoute = new VirtualRouteBuilder().setSrcNodeId(route.getKey().getSrcNodeId())\r
 381                     .setDestNodeId(route.getKey().getDestNodeId())\r
 382                     .setPathId(route.getValue().getPathId())\r
 383                     .build();\r
 384             readWriteTransaction.put(LogicalDatastoreType.CONFIGURATION, virtualRouteIid, virtualRoute, true);\r
 385         }\r
 386 \r
 387         readWriteTransaction.submit();\r
 388 \r
 389         return;\r
 390     }\r
 391 \r
 392     /**\r
 393      * A listener to change events related to virtual nodes being\r
 394      * added, removed or updated.\r
 395      *\r
 396      * @author Zhigang Ji\r
 397      */\r
 398     private class VirtualNodeChangeListener implements DataChangeListener {\r
 399         @Override\r
 400         public void onDataChanged(AsyncDataChangeEvent<InstanceIdentifier<?>, DataObject> change) {\r
 401             if ( null == change ) {\r
 402                 return;\r
 403             }\r
 404 \r
 405             Map<InstanceIdentifier<?>, DataObject> createdData = change.getCreatedData();\r
 406 \r
 407             if ( null != createdData && !createdData.isEmpty() ) {\r
 408                 VirtualNode virtualNode;\r
 409                 Vertex vertex;\r
 410 \r
 411                 for ( DataObject dataObject : createdData.values() ) {\r
 412                     if ( dataObject instanceof VirtualNode ) {\r
 413                         virtualNode = (VirtualNode)dataObject;\r
 414                         vertex = new Vertex(virtualNode.getNodeId().getValue());\r
 415 \r
 416                         routingAlgorithm.addVertex(vertex);\r
 417 \r
 418                         if ( VirtualNode.NodeType.Vrouter == virtualNode.getNodeType() ) {\r
 419                             virtualRouters.add(virtualNode.getNodeId());\r
 420                         }\r
 421                     }\r
 422                 }\r
 423             }\r
 424 \r
 425             return;\r
 426         }\r
 427     }\r
 428 \r
 429     /**\r
 430      * A listener to change events related to virtual links being\r
 431      * added, removed or updated.\r
 432      *\r
 433      * @author Zhigang Ji\r
 434      */\r
 435     private class VirtualLinkChangeListener implements DataChangeListener {\r
 436         @Override\r
 437         public void onDataChanged(AsyncDataChangeEvent<InstanceIdentifier<?>, DataObject> change) {\r
 438             if ( null == change ) {\r
 439                 return;\r
 440             }\r
 441 \r
 442             Map<InstanceIdentifier<?>, DataObject> createdData = change.getCreatedData();\r
 443 \r
 444             if ( null != createdData && !createdData.isEmpty() ) {\r
 445 \r
 446                 boolean needRerouting = false;\r
 447 \r
 448                 for ( DataObject dataObject : createdData.values() ) {\r
 449                     if ( dataObject instanceof VirtualLink ) {\r
 450                         VirtualLink virtualLink = (VirtualLink)dataObject;\r
 451                         Edge edge = new Edge(virtualLink);\r
 452 \r
 453                         routingAlgorithm.addEdge(edge);\r
 454 \r
 455                         if ( virtualRouters.contains(virtualLink.getSrcNodeId())\r
 456                                 && virtualRouters.contains(virtualLink.getDestNodeId()) ) {\r
 457                             needRerouting = true;\r
 458                         }\r
 459                     }\r
 460                 }\r
 461 \r
 462                 if ( needRerouting ) {\r
 463                     computeRoute();\r
 464                 }\r
 465             }\r
 466 \r
 467             return;\r
 468         }\r
 469     }\r
 470 }\r