<type xmlns:prefix="urn:opendaylight:params:xml:ns:yang:controller:bgp:rib:impl">prefix:bgp-peer-registry</type>
<name>global-bgp-peer-registry</name>
</accepting-peer-registry>
+ </module>
+ <!--<module>
+ <type xmlns:prefix="urn:opendaylight:params:xml:ns:yang:controller:bgp:path:selection:mode">prefix:advertise-n-paths</type>
+ <name>n-paths</name>
+ <n-best-paths>2</n-best-paths>
</module>
+ <module>
+ <type xmlns:prefix="urn:opendaylight:params:xml:ns:yang:controller:bgp:rib:impl">prefix:bgp-psm-impl</type>
+ <name>ipv4-unicast-path-selection-mode</name>
+ <path-address-family>
+ <type xmlns:ribimpl="urn:opendaylight:params:xml:ns:yang:controller:bgp:rib:impl">ribimpl:bgp-table-type</type>
+ <name>ipv4-unicast</name>
+ </path-address-family>
+ <path-selection-mode>
+ <type xmlns:ribimpl="urn:opendaylight:params:xml:ns:yang:controller:bgp:path:selection:mode">ribimpl:path-selection-mode-factory</type>
+ <name>n-paths</name>
+ </path-selection-mode>
+ </module>-->
<!--
A single BGP peer. Note this section is deactivated because a misconfigured peer
<type xmlns:prefix="urn:opendaylight:params:xml:ns:yang:controller:bgp:rib:impl">prefix:bgp-table-type</type>
<name>ipv4-l3vpn</name>
</local-table>
+ <!--<path-selection-mode>
+ <type xmlns:prefix="urn:opendaylight:params:xml:ns:yang:controller:bgp:rib:impl">prefix:bgp-path-selection-mode</type>
+ <name>ipv4-unicast-path-selection-mode</name>
+ </path-selection-mode>-->
<extensions>
<type xmlns:ribspi="urn:opendaylight:params:xml:ns:yang:controller:bgp:rib:spi">ribspi:extensions</type>
<name>global-rib-extensions</name>
<provider>/config/modules/module[name='bgp-linkstate-topology']/instance[name='example-linkstate-topology']</provider>
</instance>
</service>
+ <!--<service>
+ <type xmlns:prefix="urn:opendaylight:params:xml:ns:yang:controller:bgp:path:selection:mode">prefix:path-selection-mode-factory</type>
+ <instance>
+ <name>n-paths</name>
+ <provider>/config/modules/module[name='advertise-n-paths']/instance[name='n-paths']</provider>
+ </instance>
+ </service>
+ <service>
+ <type xmlns:prefix="urn:opendaylight:params:xml:ns:yang:controller:bgp:rib:impl">prefix:bgp-path-selection-mode</type>
+ <instance>
+ <name>ipv4-unicast-path-selection-mode</name>
+ <provider>/modules/module[type='bgp-psm-impl'][name='ipv4-unicast-path-selection-mode']</provider>
+ </instance>
+ </service>-->
</services>
</data>
</configuration>
--- /dev/null
+/*
+ * Copyright (c) 2016 Cisco Systems, Inc. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.controller.config.yang.bgp.path.selection.mode;
+
+import org.opendaylight.controller.config.api.JmxAttributeValidationException;
+import org.opendaylight.protocol.bgp.mode.impl.add.n.paths.AddPathBestNPathSelection;
+
+public final class AdvertiseNPathsModule extends org.opendaylight.controller.config.yang.bgp.path.selection.mode.AbstractAdvertiseNPathsModule {
+ public AdvertiseNPathsModule(org.opendaylight.controller.config.api.ModuleIdentifier identifier, org.opendaylight.controller.config.api.DependencyResolver dependencyResolver) {
+ super(identifier, dependencyResolver);
+ }
+
+ public AdvertiseNPathsModule(org.opendaylight.controller.config.api.ModuleIdentifier identifier, org.opendaylight.controller.config.api.DependencyResolver dependencyResolver, org.opendaylight.controller.config.yang.bgp.path.selection.mode.AdvertiseNPathsModule oldModule, java.lang.AutoCloseable oldInstance) {
+ super(identifier, dependencyResolver, oldModule, oldInstance);
+ }
+
+ @Override
+ public void customValidation() {
+ JmxAttributeValidationException.checkNotNull(getNBestPaths(), "value is not set.", nBestPathsJmxAttribute);
+ }
+
+ @Override
+ public java.lang.AutoCloseable createInstance() {
+ return new AddPathBestNPathSelection(getNBestPaths());
+ }
+
+}
--- /dev/null
+/*
+ * Copyright (c) 2016 Cisco Systems, Inc. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.controller.config.yang.bgp.path.selection.mode;
+public class AdvertiseNPathsModuleFactory extends org.opendaylight.controller.config.yang.bgp.path.selection.mode.AbstractAdvertiseNPathsModuleFactory {
+
+}
* @return the path attributes
*/
ContainerNode getAttributes();
+
/**
*
* @return pathId
* Remove route
*
* @param routerId router ID in unsigned integer format from an Ipv4Address
+ * @param remotePathId remote path Id received
* @return return true if it was the last route on entry
*/
- boolean removeRoute(UnsignedInteger routerId);
+ boolean removeRoute(UnsignedInteger routerId, long remotePathId);
/**
* Create value
/**
* @param routerId router ID in unsigned integer format from an Ipv4Address
+ * @param remotePathId remote path Id received
* @param attrII route Attributes Identifier
* @param data route Data change
* @return returns the offset
*/
- int addRoute(UnsignedInteger routerId, NodeIdentifier attrII, NormalizedNode<?, ?> data);
+ int addRoute(UnsignedInteger routerId, Long remotePathId, NodeIdentifier attrII, NormalizedNode<?, ?> data);
/**
* Update LocRibOut and AdjRibsOut by removing stale best path and writing new best
* @param tx DOM transaction
*/
void writeRoute(PeerId peerId, PathArgument routeId, YangInstanceIdentifier rootPath, PeerExportGroup peerGroup, TablesKey localTK,
- RIBSupport ribSupport, DOMDataWriteTransaction tx);
+ ExportPolicyPeerTracker peerPT, RIBSupport ribSupport, CacheDisconnectedPeers discPeers, DOMDataWriteTransaction tx);
}
\ No newline at end of file
--- /dev/null
+/*
+ * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.protocol.bgp.mode.impl;
+
+import com.google.common.base.Preconditions;
+import com.google.common.cache.CacheBuilder;
+import com.google.common.cache.CacheLoader;
+import com.google.common.cache.LoadingCache;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSet.Builder;
+import java.lang.reflect.Array;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+import java.util.Set;
+import java.util.stream.Collectors;
+import javax.annotation.Nonnull;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/**
+ * A map of Router identifier to an offset. Used to maintain a simple
+ * offset-based lookup across multiple RouteEntry objects,
+ * which share either contributors or consumers.
+ * We also provide utility reformat methods, which provide access to
+ * array members and array management features.
+ */
+public final class OffsetMap<E extends Comparable<E>> {
+ private static final Logger LOG = LoggerFactory.getLogger(OffsetMap.class);
+ private static final String NEGATIVEOFFSET = "Invalid negative offset %s";
+ private static final String INVALIDOFFSET = "Invalid offset %s for %s router IDs";
+ private final Comparator<E> IPV4_COMPARATOR = E::compareTo;
+ private final E[] routeKeys;
+ private final Class<E> clazz;
+ private final LoadingCache<Set<E>, OffsetMap<E>> keyCache = CacheBuilder.newBuilder().weakValues().build(new CacheLoader<Set<E>, OffsetMap<E>>() {
+ @Override
+ public OffsetMap<E> load(@Nonnull final Set<E> key) throws Exception {
+ return new OffsetMap<>(key, clazz);
+ }
+ });
+
+ public OffsetMap(final Class<E> clazz) {
+ this.clazz = clazz;
+ this.routeKeys = (E[]) Array.newInstance(clazz, 0);
+ }
+
+ private OffsetMap(final Set<E> keysSet, final Class<E> clazz) {
+ this.clazz = clazz;
+ final E[] array = keysSet.toArray((E[]) Array.newInstance(this.clazz, keysSet.size()));
+ Arrays.sort(array, IPV4_COMPARATOR);
+ this.routeKeys = array;
+ }
+
+ public List<E> getRouteKeysList() {
+ return Arrays.stream(this.routeKeys).collect(Collectors.toList());
+ }
+
+ public E getRouterKey(final int offset) {
+ Preconditions.checkArgument(offset >= 0);
+ return this.routeKeys[offset];
+ }
+
+ public int offsetOf(final E key) {
+ return Arrays.binarySearch(this.routeKeys, key, IPV4_COMPARATOR);
+ }
+
+ public int size() {
+ return this.routeKeys.length;
+ }
+
+ public OffsetMap<E> with(final E key) {
+ // TODO: we could make this faster if we had an array-backed Set and requiring
+ // the caller to give us the result of offsetOf() -- as that indicates
+ // where to insert the new routerId while maintaining the sorted nature
+ // of the array
+ final Builder<E> b = ImmutableSet.builder();
+ b.add(this.routeKeys);
+ b.add(key);
+
+ return keyCache.getUnchecked(b.build());
+ }
+
+ public OffsetMap<E> without(final E key) {
+ final Builder<E> b = ImmutableSet.builder();
+ int index = indexOfRouterId(key);
+ if (index < 0) {
+ LOG.trace("Router key not found", key);
+ } else {
+ b.add(removeValue(this.routeKeys, index));
+ }
+ return keyCache.getUnchecked(b.build());
+ }
+
+ private int indexOfRouterId(final E key) {
+ for (int i = 0; i < this.routeKeys.length; i++) {
+ if (key.equals(this.routeKeys[i])) {
+ return i;
+ }
+ }
+ return -1;
+ }
+
+ public <T> T getValue(final T[] array, final int offset) {
+ Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
+ Preconditions.checkArgument(offset < routeKeys.length, INVALIDOFFSET, offset, routeKeys.length);
+ return array[offset];
+ }
+
+ public <T> void setValue(final T[] array, final int offset, final T value) {
+ Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
+ Preconditions.checkArgument(offset < routeKeys.length, INVALIDOFFSET, offset, routeKeys.length);
+ array[offset] = value;
+ }
+
+ public <T> T[] expand(final OffsetMap oldOffsets, final T[] oldArray, final int offset) {
+ @SuppressWarnings("unchecked")
+ final T[] ret = (T[]) Array.newInstance(oldArray.getClass().getComponentType(), this.routeKeys.length);
+ final int oldSize = oldOffsets.routeKeys.length;
+
+ System.arraycopy(oldArray, 0, ret, 0, offset);
+ System.arraycopy(oldArray, offset, ret, offset + 1, oldSize - offset);
+
+ return ret;
+ }
+
+ public <T> T[] removeValue(final T[] oldArray, final int offset) {
+ final int length = oldArray.length;
+ Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
+ Preconditions.checkArgument(offset < routeKeys.length, INVALIDOFFSET, offset, length);
+
+ final T[] ret = (T[]) Array.newInstance(oldArray.getClass().getComponentType(), length - 1);
+ System.arraycopy(oldArray, 0, ret, 0, offset);
+ if (offset < length - 1) {
+ System.arraycopy(oldArray, offset + 1, ret, offset, length - offset - 1);
+ }
+
+ return ret;
+ }
+
+ public boolean isEmty() {
+ return this.size() == 0;
+ }
+}
--- /dev/null
+/*
+ * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.protocol.bgp.mode.impl.add;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.Map;
+import javax.annotation.concurrent.NotThreadSafe;
+import org.opendaylight.controller.md.sal.common.api.data.LogicalDatastoreType;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataWriteTransaction;
+import org.opendaylight.protocol.bgp.mode.api.BestPath;
+import org.opendaylight.protocol.bgp.mode.impl.OffsetMap;
+import org.opendaylight.protocol.bgp.mode.spi.AbstractRouteEntry;
+import org.opendaylight.protocol.bgp.rib.spi.CacheDisconnectedPeers;
+import org.opendaylight.protocol.bgp.rib.spi.ExportPolicyPeerTracker;
+import org.opendaylight.protocol.bgp.rib.spi.PeerExportGroup;
+import org.opendaylight.protocol.bgp.rib.spi.RIBSupport;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.PeerId;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.PeerRole;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.rib.TablesKey;
+import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
+import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier;
+import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
+import org.opendaylight.yangtools.yang.data.api.schema.ContainerNode;
+import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
+import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
+import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNodes;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/**
+ * A single route entry inside a route table. Maintains the attributes of
+ * from all contributing peers. The information is stored in arrays with a
+ * shared map of offsets for peers to allow lookups. This is needed to
+ * maintain low memory overhead in face of large number of routes and peers,
+ * where individual object overhead becomes the dominating factor.
+ */
+@NotThreadSafe
+public abstract class AddPathAbstractRouteEntry extends AbstractRouteEntry {
+
+ private static final Logger LOG = LoggerFactory.getLogger(AddPathAbstractRouteEntry.class);
+ protected List<AddPathBestPath> bestPath = new ArrayList<>();
+ protected List<AddPathBestPath> bestPathRemoved = new ArrayList<>();
+ protected OffsetMap<RouteKey> offsets = new OffsetMap<>(RouteKey.class);
+ protected ContainerNode[] values = new ContainerNode[0];
+ protected Long[] pathsId = new Long[0];
+ private long pathIdCounter = 0L;
+
+ private int addRoute(final RouteKey key, final ContainerNode attributes) {
+ this.pathIdCounter++;
+ int offset = this.offsets.offsetOf(key);
+ if (offset < 0) {
+ final OffsetMap<RouteKey> newOffsets = this.offsets.with(key);
+ offset = newOffsets.offsetOf(key);
+ final ContainerNode[] newAttributes = newOffsets.expand(this.offsets, this.values, offset);
+ final Long[] newPathsId = newOffsets.expand(this.offsets, this.pathsId, offset);
+ this.values = newAttributes;
+ this.offsets = newOffsets;
+ this.pathsId = newPathsId;
+ }
+
+ this.offsets.setValue(this.values, offset, attributes);
+ this.offsets.setValue(this.pathsId, offset, this.pathIdCounter);
+ LOG.trace("Added route from {} attributes {}", key.getRouteId(), attributes);
+ return offset;
+ }
+
+ protected int addRoute(final RouteKey key, final NodeIdentifier attributesIdentifier, final NormalizedNode<?, ?> data) {
+ LOG.trace("Find {} in {}", attributesIdentifier, data);
+ final ContainerNode advertisedAttrs = (ContainerNode) NormalizedNodes.findNode(data, attributesIdentifier).orNull();
+ return addRoute(key, advertisedAttrs);
+ }
+
+ /**
+ * Remove route
+ *
+ * @param key RouteKey of removed route
+ * @param offset Offset of removed route
+ * @return true if it was the last route
+ */
+ protected final boolean removeRoute(final RouteKey key, final int offset) {
+ this.values = this.offsets.removeValue(this.values, offset);
+ this.pathsId = this.offsets.removeValue(this.pathsId, offset);
+ this.offsets = this.offsets.without(key);
+ return this.offsets.size() == 0;
+ }
+
+ @Override
+ public void updateRoute(final TablesKey localTK, final ExportPolicyPeerTracker peerPT, final YangInstanceIdentifier locRibTarget, final RIBSupport ribSup,
+ final CacheDisconnectedPeers discPeers, final DOMDataWriteTransaction tx, final PathArgument routeIdPA) {
+ this.bestPathRemoved.forEach(path -> removePathFromDataStore(path, isFirstBestPath(bestPathRemoved.indexOf(path)), routeIdPA, locRibTarget, ribSup,
+ peerPT, localTK, discPeers,tx));
+ this.bestPathRemoved = Collections.emptyList();
+
+ this.bestPath.forEach(path -> addPathToDataStore(path, isFirstBestPath(this.bestPath.indexOf(path)), routeIdPA, locRibTarget, ribSup,
+ peerPT, localTK, discPeers,tx));
+ }
+
+ @Override
+ public void writeRoute(final PeerId destPeer, final PathArgument routeId, final YangInstanceIdentifier rootPath, final PeerExportGroup peerGroup,
+ final TablesKey localTK, final ExportPolicyPeerTracker peerPT, final RIBSupport ribSup, final CacheDisconnectedPeers discPeers,
+ final DOMDataWriteTransaction tx) {
+ final boolean destPeerSupAddPath = peerPT.isAddPathSupportedByPeer(destPeer);
+ this.bestPath.stream().filter(path -> filterRoutes(path.getPeerId(), destPeer, peerPT, localTK, discPeers) &&
+ peersSupportsAddPathOrIsFirstBestPath(destPeerSupAddPath, isFirstBestPath(this.bestPath.indexOf(path))))
+ .forEach(path -> writeRoutePath(destPeer, routeId, peerGroup, destPeerSupAddPath, path, rootPath, localTK, ribSup, tx));
+ }
+
+ private void writeRoutePath(final PeerId destPeer, final PathArgument routeId, final PeerExportGroup peerGroup, final boolean destPeerSupAddPath,
+ final BestPath path, final YangInstanceIdentifier rootPath, final TablesKey localTK, final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
+ final PathArgument routeIdAddPath = ribSup.getRouteIdAddPath(path.getPathId(), routeId);
+ final ContainerNode effectiveAttributes = peerGroup.effectiveAttributes(path.getPeerId(), path.getAttributes());
+ if (destPeerSupAddPath) {
+ writeRoute(destPeer, getAdjRibOutYII(ribSup, rootPath, routeIdAddPath, localTK), effectiveAttributes, createValue(routeIdAddPath, path), ribSup, tx);
+ } else {
+ writeRoute(destPeer, getAdjRibOutYII(ribSup, rootPath, routeId, localTK), effectiveAttributes, createValue(routeId, path), ribSup, tx);
+ }
+ }
+
+ private void addPathToDataStore(final BestPath path, final boolean isFirstBestPath, final PathArgument routeIdPA, final YangInstanceIdentifier locRibTarget,
+ final RIBSupport ribSup, final ExportPolicyPeerTracker peerPT, final TablesKey localTK, final CacheDisconnectedPeers discPeers,
+ final DOMDataWriteTransaction tx) {
+ final PathArgument routeIdAddPath = ribSup.getRouteIdAddPath(path.getPathId(), routeIdPA);
+ final YangInstanceIdentifier pathAddPathTarget = ribSup.routePath(locRibTarget.node(ROUTES_IDENTIFIER), routeIdAddPath);
+ final MapEntryNode addPathValue = createValue(routeIdAddPath, path);
+ final MapEntryNode value = createValue(routeIdPA, path);
+ LOG.trace("Selected best value {}", addPathValue);
+ fillLocRib(pathAddPathTarget, addPathValue, tx);
+ fillAdjRibsOut(isFirstBestPath, path.getAttributes(), value, addPathValue, routeIdPA, routeIdAddPath, path.getPeerId(), peerPT, localTK,
+ ribSup, discPeers, tx);
+ }
+
+ private void removePathFromDataStore(final BestPath path, final boolean isFirstBestPath, final PathArgument routeIdPA,
+ final YangInstanceIdentifier locRibTarget, final RIBSupport ribSup, final ExportPolicyPeerTracker peerPT, final TablesKey localTK,
+ final CacheDisconnectedPeers discPeers, final DOMDataWriteTransaction tx) {
+ LOG.trace("Best Path removed {}", path);
+ final PathArgument routeIdAddPath = ribSup.getRouteIdAddPath(path.getPathId(), routeIdPA);
+ final YangInstanceIdentifier pathAddPathTarget = ribSup.routePath(locRibTarget.node(ROUTES_IDENTIFIER), routeIdAddPath);
+
+ fillLocRib(pathAddPathTarget, null, tx);
+ fillAdjRibsOut(isFirstBestPath, null, null, null, routeIdPA, routeIdAddPath, path.getPeerId(), peerPT, localTK, ribSup, discPeers, tx);
+ }
+
+ private void fillAdjRibsOut(final boolean isFirstBestPath, final ContainerNode attributes, final NormalizedNode<?, ?> value, final MapEntryNode addPathValue,
+ final PathArgument routeId, final PathArgument routeIdAddPath, final PeerId routePeerId, final ExportPolicyPeerTracker peerPT, final TablesKey
+ localTK, final RIBSupport ribSup, final CacheDisconnectedPeers discPeers, final DOMDataWriteTransaction tx) {
+ /*
+ * We need to keep track of routers and populate adj-ribs-out, too. If we do not, we need to
+ * expose from which client a particular route was learned from in the local RIB, and have
+ * the listener perform filtering.
+ *
+ * We walk the policy set in order to minimize the amount of work we do for multiple peers:
+ * if we have two eBGP peers, for example, there is no reason why we should perform the translation
+ * multiple times.
+ */
+ for (final PeerRole role : PeerRole.values()) {
+ if (PeerRole.Internal.equals(role)) {
+ continue;
+ }
+ final PeerExportGroup peerGroup = peerPT.getPeerGroup(role);
+ if (peerGroup != null) {
+ final ContainerNode effectiveAttributes = peerGroup.effectiveAttributes(routePeerId, attributes);
+ for (final Map.Entry<PeerId, YangInstanceIdentifier> pid : peerGroup.getPeers()) {
+ final PeerId destPeer = pid.getKey();
+ final boolean destPeerSupAddPath = peerPT.isAddPathSupportedByPeer(destPeer);
+ if (filterRoutes(routePeerId, destPeer, peerPT, localTK, discPeers) && peersSupportsAddPathOrIsFirstBestPath(destPeerSupAddPath, isFirstBestPath)) {
+ if (destPeerSupAddPath) {
+ update(destPeer, getAdjRibOutYII(ribSup, pid.getValue(), routeIdAddPath, localTK), effectiveAttributes, addPathValue,
+ ribSup, tx);
+ } else {
+ update(destPeer, getAdjRibOutYII(ribSup, pid.getValue(), routeId, localTK), effectiveAttributes, value, ribSup, tx);
+ }
+ }
+ }
+ }
+ }
+ }
+
+ private void update(final PeerId destPeer, final YangInstanceIdentifier routeTarget, final ContainerNode effAttr, final NormalizedNode<?, ?> value,
+ final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
+ if (!writeRoute(destPeer, routeTarget, effAttr, value, ribSup, tx)) {
+ LOG.trace("Removing {} from transaction for peer {}", routeTarget, destPeer);
+ tx.delete(LogicalDatastoreType.OPERATIONAL, routeTarget);
+ }
+ }
+
+ protected final OffsetMap<RouteKey> getOffsets() {
+ return this.offsets;
+ }
+
+ protected void selectBest(final RouteKey key, final AddPathSelector selector) {
+ final int offset = this.offsets.offsetOf(key);
+ final ContainerNode attributes = this.offsets.getValue(this.values, offset);
+ final Long pathId = this.offsets.getValue(this.pathsId, offset);
+ LOG.trace("Processing router key {} attributes {}", key, attributes);
+ selector.processPath(attributes, key, offset, pathId);
+ }
+
+ /**
+ * Process best path selection
+ *
+ * @param localAs The local autonomous system number
+ * @param keyList List of RouteKey
+ * @return the best path inside offset map passed
+ */
+ protected AddPathBestPath selectBest(final long localAs, final List<RouteKey> keyList) {
+ /*
+ * FIXME: optimize flaps by making sure we consider stability of currently-selected route.
+ */
+ final AddPathSelector selector = new AddPathSelector(localAs);
+ keyList.forEach(key -> selectBest(key, selector));
+ LOG.trace("Best path selected {}", this.bestPath);
+ return selector.result();
+ }
+
+ protected boolean isFirstBestPath(final int bestPathPosition) {
+ return bestPathPosition == 0;
+ }
+
+ private boolean peersSupportsAddPathOrIsFirstBestPath(final boolean peerSupportsAddPath, final boolean isFirstBestPath) {
+ return !(!peerSupportsAddPath && !isFirstBestPath);
+ }
+}
--- /dev/null
+/*
+ * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.protocol.bgp.mode.impl.add;
+
+import com.google.common.base.MoreObjects.ToStringHelper;
+import com.google.common.base.Preconditions;
+import com.google.common.primitives.UnsignedInteger;
+import javax.annotation.Nonnull;
+import org.opendaylight.protocol.bgp.mode.api.BestPathState;
+import org.opendaylight.protocol.bgp.mode.spi.AbstractBestPath;
+import org.opendaylight.protocol.bgp.rib.spi.RouterIds;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.PeerId;
+
+public final class AddPathBestPath extends AbstractBestPath {
+ private final RouteKey routeKey;
+ private final int offsetPosition;
+ private final long pathId;
+
+ public AddPathBestPath(@Nonnull final BestPathState state, @Nonnull final RouteKey key, final int offsetPosition, final Long pathId) {
+ super(state);
+ this.routeKey = Preconditions.checkNotNull(key);
+ this.offsetPosition = offsetPosition;
+ this.pathId = pathId;
+ }
+
+ public RouteKey getRouteKey() {
+ return this.routeKey;
+ }
+
+ @Override
+ protected ToStringHelper addToStringAttributes(final ToStringHelper toStringHelper) {
+ toStringHelper.add("routeKey", this.routeKey);
+ toStringHelper.add("state", this.state);
+ toStringHelper.add("offsetPosition", this.offsetPosition);
+ toStringHelper.add("pathId", this.pathId);
+ return toStringHelper;
+ }
+
+ @Override
+ public int hashCode() {
+ final int prime = 31;
+ int result = 1;
+ result = prime * result + this.routeKey.hashCode();
+ result = prime * result + this.state.hashCode();
+ return result;
+ }
+
+ @Override
+ public boolean equals(final Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (!(obj instanceof AddPathBestPath)) {
+ return false;
+ }
+ final AddPathBestPath other = (AddPathBestPath) obj;
+ if (!this.routeKey.equals(other.routeKey)) {
+ return false;
+ }
+ /*
+ We don't check offset position since it will change as new path is added, and we want to be able to use List comparison between old
+ bestpath list and new best path list.
+ */
+ if (!this.state.equals(other.state)) {
+ return false;
+ }
+
+ return this.pathId == other.pathId;
+ }
+
+ @Override
+ public final UnsignedInteger getRouterId() {
+ return this.routeKey.getRouteId();
+ }
+
+ @Override
+ public final PeerId getPeerId() {
+ return RouterIds.createPeerId(this.routeKey.getRouteId());
+ }
+
+ @Override
+ public long getPathId() {
+ return this.pathId;
+ }
+}
--- /dev/null
+/*
+ * Copyright (c) 2016 Cisco Systems, Inc. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.protocol.bgp.mode.impl.add;
+
+import com.google.common.base.Preconditions;
+import com.google.common.primitives.UnsignedInteger;
+import org.opendaylight.protocol.bgp.mode.api.BestPathState;
+import org.opendaylight.protocol.bgp.mode.impl.BestPathStateImpl;
+import org.opendaylight.protocol.bgp.mode.spi.AbstractBestPathSelector;
+import org.opendaylight.yangtools.yang.data.api.schema.ContainerNode;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+public final class AddPathSelector extends AbstractBestPathSelector {
+ private static final Logger LOG = LoggerFactory.getLogger(AddPathSelector.class);
+
+ private RouteKey bestRouteKey;
+ private int bestOffsetPosition;
+ private Long bestPathId;
+
+ public AddPathSelector(final Long ourAs) {
+ super(ourAs);
+ }
+
+ public void processPath(final ContainerNode attrs, final RouteKey key, final int offsetPosition, final Long pathId) {
+ Preconditions.checkNotNull(key.getRouteId(), "Router ID may not be null");
+
+ // Consider only non-null attributes
+ if (attrs != null) {
+ final UnsignedInteger originatorId = replaceOriginator(key.getRouteId(), attrs);
+
+ /*
+ * Store the new details if we have nothing stored or when the selection algorithm indicates new details
+ * are better.
+ */
+ final BestPathState state = new BestPathStateImpl(attrs);
+ if (this.bestOriginatorId == null || !isExistingPathBetter(state)) {
+ LOG.trace("Selecting path from router {}", key);
+ this.bestOriginatorId = originatorId;
+ this.bestState = state;
+ this.bestRouteKey = key;
+ this.bestOffsetPosition = offsetPosition;
+ this.bestPathId = pathId;
+ }
+ }
+ }
+
+ public AddPathBestPath result() {
+ return this.bestRouteKey == null ? null : new AddPathBestPath(this.bestState, this.bestRouteKey, this.bestOffsetPosition, this.bestPathId);
+ }
+}
--- /dev/null
+/*
+ * Copyright (c) 2016 Cisco Systems, Inc. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.protocol.bgp.mode.impl.add;
+
+import com.google.common.base.MoreObjects;
+import com.google.common.primitives.UnsignedInteger;
+import javax.annotation.Nonnull;
+
+public final class RouteKey implements Comparable<RouteKey> {
+ private final Long remotePathId;
+ private final UnsignedInteger routerId;
+
+ public RouteKey(final UnsignedInteger routerId, final Long remotePathId) {
+ this.routerId = routerId;
+ this.remotePathId = remotePathId;
+ }
+
+ private Long getExternalPathId() {
+ return this.remotePathId;
+ }
+
+ public UnsignedInteger getRouteId() {
+ return this.routerId;
+ }
+
+ private MoreObjects.ToStringHelper addToStringAttributes(final MoreObjects.ToStringHelper toStringHelper) {
+ toStringHelper.add("externalPathId", this.remotePathId);
+ toStringHelper.add("routerId", this.routerId);
+ return toStringHelper;
+ }
+
+ @Override
+ public int hashCode() {
+ final int prime = 27;
+ int result = 1;
+ result = prime * result + this.remotePathId.hashCode();
+ result = prime * result + this.routerId.hashCode();
+ return result;
+ }
+
+ @Override
+ public boolean equals(final Object obj) {
+ if (this == obj) {
+ return true;
+ }
+
+ if (!(obj instanceof RouteKey)) {
+ return false;
+ }
+
+ final RouteKey other = (RouteKey) obj;
+ return this.remotePathId.equals(other.remotePathId) && this.routerId.equals(other.routerId);
+ }
+
+ @Override
+ public String toString() {
+ return addToStringAttributes(MoreObjects.toStringHelper(this)).toString();
+ }
+
+ @Override
+ public int compareTo(@Nonnull final RouteKey otherRouteKey) {
+ final int routeIdCompareTo = this.routerId.compareTo(otherRouteKey.getRouteId());
+ return routeIdCompareTo == 0 ? this.remotePathId.compareTo(otherRouteKey.getExternalPathId()) : routeIdCompareTo;
+ }
+}
--- /dev/null
+/*
+ * Copyright (c) 2016 Cisco Systems, Inc. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+
+package org.opendaylight.protocol.bgp.mode.impl.add.n.paths;
+
+import java.util.ArrayList;
+import java.util.List;
+import org.opendaylight.protocol.bgp.mode.impl.add.AddPathAbstractRouteEntry;
+import org.opendaylight.protocol.bgp.mode.impl.add.AddPathBestPath;
+import org.opendaylight.protocol.bgp.mode.impl.add.RouteKey;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+abstract class AbstractNPathsRouteEntry extends AddPathAbstractRouteEntry {
+ private static final Logger LOG = LoggerFactory.getLogger(AbstractNPathsRouteEntry.class);
+
+ private final long nBestPaths;
+
+ AbstractNPathsRouteEntry(final Long nBestPaths) {
+ this.nBestPaths = nBestPaths;
+ }
+
+ @Override
+ public final boolean selectBest(final long localAs) {
+ final List<AddPathBestPath> newBestPathList = new ArrayList<>();
+ final List<RouteKey> keyList = this.offsets.getRouteKeysList();
+ final long maxSearch = this.nBestPaths < this.offsets.size() && this.nBestPaths != 0 ? this.nBestPaths : this.offsets.size();
+ for (long i = 0; i < maxSearch; ++i) {
+ final AddPathBestPath newBest = selectBest(localAs, keyList);
+ newBestPathList.add(newBest);
+ keyList.remove(newBest.getRouteKey());
+ }
+
+ this.bestPathRemoved = new ArrayList<>(this.bestPath);
+ if (this.bestPathRemoved.removeAll(newBestPathList) || !this.bestPath.equals(newBestPathList)) {
+ this.bestPath = newBestPathList;
+ LOG.trace("Actual Best {}, removed best {}", this.bestPath, this.bestPathRemoved);
+ return true;
+ }
+ return false;
+ }
+}
--- /dev/null
+/*
+ * Copyright (c) 2016 Cisco Systems, Inc. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+
+package org.opendaylight.protocol.bgp.mode.impl.add.n.paths;
+
+import org.opendaylight.protocol.bgp.mode.api.PathSelectionMode;
+import org.opendaylight.protocol.bgp.mode.api.RouteEntry;
+
+public class AddPathBestNPathSelection implements PathSelectionMode {
+ private final Long nBestPaths;
+
+ public AddPathBestNPathSelection(final Long nBestPaths) {
+ this.nBestPaths = nBestPaths;
+ }
+
+ @Override
+ public void close() throws Exception {
+ //no-op
+ }
+
+ @Override
+ public RouteEntry createRouteEntry(final boolean isComplex) {
+ if (isComplex) {
+ return new ComplexRouteEntry(this.nBestPaths);
+ } else {
+ return new SimpleRouteEntry(this.nBestPaths);
+ }
+ }
+}
\ No newline at end of file
--- /dev/null
+/*
+ * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.protocol.bgp.mode.impl.add.n.paths;
+
+import com.google.common.primitives.UnsignedInteger;
+import org.opendaylight.protocol.bgp.mode.api.BestPath;
+import org.opendaylight.protocol.bgp.mode.impl.OffsetMap;
+import org.opendaylight.protocol.bgp.mode.impl.add.AddPathBestPath;
+import org.opendaylight.protocol.bgp.mode.impl.add.RouteKey;
+import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier;
+import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
+import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
+import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
+
+final class ComplexRouteEntry extends AbstractNPathsRouteEntry {
+ private static final MapEntryNode[] EMPTY_VALUES = new MapEntryNode[0];
+ private MapEntryNode[] values = EMPTY_VALUES;
+
+ public ComplexRouteEntry(final Long nBestPaths) {
+ super(nBestPaths);
+ }
+
+ @Override
+ public boolean removeRoute(final UnsignedInteger routerId, final long remotePathId) {
+ final RouteKey key = new RouteKey(routerId, remotePathId);
+ final OffsetMap<RouteKey> map = getOffsets();
+ final int offset = map.offsetOf(key);
+ final boolean ret = removeRoute(key, offset);
+ this.values = map.removeValue(this.values, offset);
+ return ret;
+ }
+
+ @Override
+ public MapEntryNode createValue(final PathArgument routeId, final BestPath path) {
+ final OffsetMap<RouteKey> map = getOffsets();
+ final int offset = map.offsetOf(((AddPathBestPath) path).getRouteKey());
+ return map.getValue(this.values, offset);
+ }
+
+ @Override
+ public int addRoute(final UnsignedInteger routerId, final Long remotePathId, final NodeIdentifier attributesIdentifier, final NormalizedNode<?, ?> data) {
+ final OffsetMap<RouteKey> oldMap = getOffsets();
+ final int offset = addRoute(new RouteKey(routerId, remotePathId), attributesIdentifier, data);
+ final OffsetMap<RouteKey> newMap = getOffsets();
+
+ if (!newMap.equals(oldMap)) {
+ this.values = newMap.expand(oldMap, this.values, offset);
+ }
+
+ newMap.setValue(this.values, offset, data);
+ return offset;
+ }
+}
\ No newline at end of file
--- /dev/null
+/*
+ * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.protocol.bgp.mode.impl.add.n.paths;
+
+import com.google.common.primitives.UnsignedInteger;
+import org.opendaylight.protocol.bgp.mode.api.BestPath;
+import org.opendaylight.protocol.bgp.mode.impl.add.RouteKey;
+import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier;
+import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifierWithPredicates;
+import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
+import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
+import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
+import org.opendaylight.yangtools.yang.data.impl.schema.Builders;
+import org.opendaylight.yangtools.yang.data.impl.schema.builder.api.DataContainerNodeAttrBuilder;
+
+final class SimpleRouteEntry extends AbstractNPathsRouteEntry {
+ public SimpleRouteEntry(final Long nBestPaths) {
+ super(nBestPaths);
+ }
+
+ @Override
+ public boolean removeRoute(final UnsignedInteger routerId, final long remotePathId) {
+ final RouteKey key = new RouteKey(routerId, remotePathId);
+ return removeRoute(key, getOffsets().offsetOf(key));
+ }
+
+ @Override
+ public MapEntryNode createValue(final PathArgument routeId, final BestPath path) {
+ final DataContainerNodeAttrBuilder<NodeIdentifierWithPredicates, MapEntryNode> b = Builders.mapEntryBuilder();
+ b.withNodeIdentifier((NodeIdentifierWithPredicates) routeId);
+ b.addChild(path.getAttributes());
+ return b.build();
+ }
+
+ @Override
+ public int addRoute(final UnsignedInteger routerId, final Long remotePathId, final NodeIdentifier attributesIdentifier, final NormalizedNode<?, ?> data) {
+ return addRoute(new RouteKey(routerId, remotePathId), attributesIdentifier, data);
+ }
+}
\ No newline at end of file
import org.opendaylight.controller.md.sal.common.api.data.LogicalDatastoreType;
import org.opendaylight.controller.md.sal.dom.api.DOMDataWriteTransaction;
import org.opendaylight.protocol.bgp.mode.api.BestPath;
-import org.opendaylight.protocol.bgp.mode.api.RouteEntry;
+import org.opendaylight.protocol.bgp.mode.impl.OffsetMap;
+import org.opendaylight.protocol.bgp.mode.spi.AbstractRouteEntry;
import org.opendaylight.protocol.bgp.rib.spi.CacheDisconnectedPeers;
import org.opendaylight.protocol.bgp.rib.spi.ExportPolicyPeerTracker;
import org.opendaylight.protocol.bgp.rib.spi.PeerExportGroup;
import org.opendaylight.protocol.bgp.rib.spi.RIBSupport;
-import org.opendaylight.protocol.bgp.rib.spi.RibSupportUtils;
import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.PeerId;
import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.PeerRole;
-import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.bgp.rib.rib.peer.AdjRibOut;
-import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.rib.Tables;
import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.rib.TablesKey;
-import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.rib.tables.Routes;
import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier;
import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
import org.slf4j.LoggerFactory;
@NotThreadSafe
-abstract class BaseAbstractRouteEntry implements RouteEntry {
+abstract class BaseAbstractRouteEntry extends AbstractRouteEntry {
- private static final NodeIdentifier ROUTES_IDENTIFIER = new NodeIdentifier(Routes.QNAME);
private static final Logger LOG = LoggerFactory.getLogger(BaseAbstractRouteEntry.class);
private static final ContainerNode[] EMPTY_ATTRIBUTES = new ContainerNode[0];
- private OffsetMap offsets = OffsetMap.EMPTY;
+ private OffsetMap<UnsignedInteger> offsets = new OffsetMap<>(UnsignedInteger.class);
private ContainerNode[] values = EMPTY_ATTRIBUTES;
private Optional<BaseBestPath> bestPath = Optional.empty();
private Optional<BaseBestPath> removedBestPath = Optional.empty();
private int addRoute(final UnsignedInteger routerId, final ContainerNode attributes) {
int offset = this.offsets.offsetOf(routerId);
if (offset < 0) {
- final OffsetMap newOffsets = this.offsets.with(routerId);
+ final OffsetMap<UnsignedInteger> newOffsets = this.offsets.with(routerId);
offset = newOffsets.offsetOf(routerId);
this.values = newOffsets.expand(this.offsets, this.values, offset);
// Select the best route.
for (int i = 0; i < this.offsets.size(); ++i) {
- final UnsignedInteger routerId = this.offsets.getRouterId(i);
+ final UnsignedInteger routerId = this.offsets.getRouterKey(i);
final ContainerNode attributes = this.offsets.getValue(this.values, i);
LOG.trace("Processing router id {} attributes {}", routerId, attributes);
selector.processPath(routerId, attributes);
}
@Override
- public int addRoute(final UnsignedInteger routerId, final NodeIdentifier attrII, final NormalizedNode<?, ?> data) {
- LOG.trace("Find {} in {}", attrII, data);
- final ContainerNode advertisedAttrs = (ContainerNode) NormalizedNodes.findNode(data, attrII).orNull();
+ public int addRoute(final UnsignedInteger routerId, final Long remotePathId, final NodeIdentifier attributesIdentifier, final NormalizedNode<?, ?> data) {
+ LOG.trace("Find {} in {}", attributesIdentifier, data);
+ final ContainerNode advertisedAttrs = (ContainerNode) NormalizedNodes.findNode(data, attributesIdentifier).orNull();
return addRoute(routerId, advertisedAttrs);
}
}
@Override
- public void writeRoute(final PeerId destPeer, final PathArgument routeId, final YangInstanceIdentifier rootPath,
- final PeerExportGroup peerGroup, final TablesKey localTK, final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
+ public void writeRoute(final PeerId destPeer, final PathArgument routeId, final YangInstanceIdentifier rootPath, final PeerExportGroup peerGroup,
+ final TablesKey localTK, final ExportPolicyPeerTracker peerPT, final RIBSupport ribSup, final CacheDisconnectedPeers discPeers,
+ final DOMDataWriteTransaction tx) {
if (this.bestPath.isPresent()) {
final BaseBestPath path = this.bestPath.get();
- final ContainerNode effAttrib = peerGroup.effectiveAttributes(path.getPeerId(), path.getAttributes());
- writeRoute(destPeer, getAdjRibOutYII(ribSup, rootPath, routeId, localTK), effAttrib, createValue(routeId, path), ribSup, tx);
+ if (filterRoutes(path.getPeerId(), destPeer, peerPT, localTK, discPeers)) {
+ final ContainerNode effAttrib = peerGroup.effectiveAttributes(path.getPeerId(), path.getAttributes());
+ writeRoute(destPeer, getAdjRibOutYII(ribSup, rootPath, routeId, localTK), effAttrib, createValue(routeId, path), ribSup, tx);
+ }
}
}
fillAdjRibsOut(path.getAttributes(), value, routeIdPA, path.getPeerId(), peerPT, localTK, ribSup, discPeers, tx);
}
- private boolean writeRoute(final PeerId destPeer, final YangInstanceIdentifier routeTarget, final ContainerNode effAttrib,
- final NormalizedNode<?, ?> value, final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
- if (effAttrib != null && value != null) {
- LOG.debug("Write route {} to peer AdjRibsOut {}", value, destPeer);
- tx.put(LogicalDatastoreType.OPERATIONAL, routeTarget, value);
- tx.put(LogicalDatastoreType.OPERATIONAL, routeTarget.node(ribSup.routeAttributesIdentifier()), effAttrib);
- return true;
- }
- return false;
- }
-
- protected final OffsetMap getOffsets() {
+ protected final OffsetMap<UnsignedInteger> getOffsets() {
return this.offsets;
}
- private void fillLocRib(final YangInstanceIdentifier routesYangId, final NormalizedNode<?, ?> value, final DOMDataWriteTransaction tx) {
- if (value != null) {
- LOG.debug("Write route to LocRib {}", value);
- tx.put(LogicalDatastoreType.OPERATIONAL, routesYangId, value);
- } else {
- LOG.debug("Delete route from LocRib {}", routesYangId);
- tx.delete(LogicalDatastoreType.OPERATIONAL, routesYangId);
- }
- }
-
@VisibleForTesting
private void fillAdjRibsOut(final ContainerNode attributes, final NormalizedNode<?, ?> value,
final PathArgument routeId, final PeerId routePeerId, final ExportPolicyPeerTracker peerPT, final TablesKey localTK, final RIBSupport ribSup,
final ContainerNode effAttrib = peerGroup.effectiveAttributes(routePeerId, attributes);
peerGroup.getPeers().stream()
.filter(pid -> filterRoutes(routePeerId, pid.getKey(), peerPT, localTK, discPeers))
- .forEach(pid -> update(pid.getKey(), getAdjRibOutYII(ribSup, pid.getValue(), routeId, localTK), effAttrib, value,
- ribSup, tx));
+ .forEach(pid -> update(pid.getKey(), getAdjRibOutYII(ribSup, pid.getValue(), routeId, localTK), effAttrib, value, ribSup, tx));
}
}
}
- private boolean filterRoutes(final PeerId rootPeer, final PeerId destPeer, final ExportPolicyPeerTracker peerPT,
- final TablesKey localTK, final CacheDisconnectedPeers discPeers) {
- return !rootPeer.equals(destPeer) && isTableSupported(destPeer, peerPT, localTK) && !discPeers.isPeerDisconnected(destPeer);
- }
-
private void update(final PeerId destPeer, final YangInstanceIdentifier routeTarget, final ContainerNode effAttrib,
final NormalizedNode<?, ?> value, final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
if (!writeRoute(destPeer, routeTarget, effAttrib, value, ribSup, tx)) {
tx.delete(LogicalDatastoreType.OPERATIONAL, routeTarget);
}
}
-
- private boolean isTableSupported(final PeerId destPeer, final ExportPolicyPeerTracker peerPT, final TablesKey localTK) {
- if (!peerPT.isTableSupported(destPeer)) {
- LOG.trace("Route rejected, peer {} does not support this table type {}", destPeer, localTK);
- return false;
- }
- return true;
- }
-
-
- private YangInstanceIdentifier getAdjRibOutYII(final RIBSupport ribSup, final YangInstanceIdentifier rootPath, final PathArgument routeId,
- final TablesKey localTK) {
- return ribSup.routePath(rootPath.node(AdjRibOut.QNAME).node(Tables.QNAME).node(RibSupportUtils.toYangTablesKey(localTK))
- .node(ROUTES_IDENTIFIER), routeId);
- }
}
\ No newline at end of file
import com.google.common.primitives.UnsignedInteger;
import org.opendaylight.protocol.bgp.mode.api.BestPath;
+import org.opendaylight.protocol.bgp.mode.impl.OffsetMap;
import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier;
import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
private MapEntryNode[] values = EMPTY_VALUES;
@Override
- public int addRoute(final UnsignedInteger routerId, final NodeIdentifier attrII, final NormalizedNode<?, ?> data) {
- final OffsetMap oldMap = getOffsets();
- final int offset = super.addRoute(routerId, attrII, data);
- final OffsetMap newMap = getOffsets();
+ public int addRoute(final UnsignedInteger routerId, final Long remotePathId, final NodeIdentifier attrII, final NormalizedNode<?, ?> data) {
+ final OffsetMap<UnsignedInteger> oldMap = getOffsets();
+ final int offset = super.addRoute(routerId, remotePathId, attrII, data);
+ final OffsetMap<UnsignedInteger> newMap = getOffsets();
if (!newMap.equals(oldMap)) {
this.values = newMap.expand(oldMap, this.values, offset);
@Override
public MapEntryNode createValue(final PathArgument routeId, final BestPath path) {
- final OffsetMap map = getOffsets();
+ final OffsetMap<UnsignedInteger> map = getOffsets();
return map.getValue(this.values, map.offsetOf(path.getRouterId()));
}
@Override
- public boolean removeRoute(final UnsignedInteger routerId) {
- final OffsetMap map = getOffsets();
+ public boolean removeRoute(final UnsignedInteger routerId, final long remotePathId) {
+ final OffsetMap<UnsignedInteger> map = getOffsets();
final int offset = map.offsetOf(routerId);
final boolean ret = removeRoute(routerId, offset);
this.values = map.removeValue(this.values, offset);
*/
package org.opendaylight.protocol.bgp.mode.impl.base;
-import com.google.common.base.Optional;
import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableList;
import com.google.common.primitives.UnsignedInteger;
-import java.util.Collection;
-import javax.annotation.Nonnull;
import org.opendaylight.protocol.bgp.mode.api.BestPathState;
import org.opendaylight.protocol.bgp.mode.impl.BestPathStateImpl;
-import org.opendaylight.protocol.bgp.rib.spi.RouterIds;
-import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.message.rev130919.OriginatorId;
-import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.types.rev130919.BgpOrigin;
-import org.opendaylight.yangtools.yang.common.QName;
-import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier;
-import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
+import org.opendaylight.protocol.bgp.mode.spi.AbstractBestPathSelector;
import org.opendaylight.yangtools.yang.data.api.schema.ContainerNode;
-import org.opendaylight.yangtools.yang.data.api.schema.LeafNode;
-import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
-import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNodes;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
-final class BasePathSelector {
+final class BasePathSelector extends AbstractBestPathSelector {
private static final Logger LOG = LoggerFactory.getLogger(BasePathSelector.class);
- private static final Collection<PathArgument> ORIGINATOR_ID = ImmutableList.<PathArgument>of(new NodeIdentifier(OriginatorId.QNAME), new NodeIdentifier(QName.create(OriginatorId.QNAME, "originator")));
- private final Long ourAs;
- private UnsignedInteger bestOriginatorId = null;
private UnsignedInteger bestRouterId = null;
- private BestPathState bestState = null;
BasePathSelector(final Long ourAs) {
- this.ourAs = Preconditions.checkNotNull(ourAs);
+ super(ourAs);
}
void processPath(final UnsignedInteger routerId, final ContainerNode attrs) {
// Consider only non-null attributes
if (attrs != null) {
- /*
- * RFC 4456 mandates the use of Originator IDs instead of Router ID for
- * selection purposes.
- */
- final Optional<NormalizedNode<?, ?>> maybeOriginatorId = NormalizedNodes.findNode(attrs, ORIGINATOR_ID);
- final UnsignedInteger originatorId;
- if (maybeOriginatorId.isPresent()) {
- originatorId = RouterIds.routerIdForAddress((String) ((LeafNode<?>)maybeOriginatorId.get()).getValue());
- } else {
- originatorId = routerId;
- }
-
+ final UnsignedInteger originatorId = replaceOriginator(routerId, attrs);
/*
* Store the new details if we have nothing stored or when the selection algorithm indicates new details
* are better.
}
}
+
BaseBestPath result() {
return this.bestRouterId == null ? null : new BaseBestPath(this.bestRouterId, this.bestState);
}
-
- /**
- * Chooses best route according to BGP best path selection.
- *
- * @param state attributes of the new route
- * @return true if the existing path is better, false if the new path is better
- */
- private boolean isExistingPathBetter(@Nonnull final BestPathState state) {
- // 1. prefer path with accessible nexthop
- // - we assume that all nexthops are accessible
- /*
- * 2. prefer path with higher LOCAL_PREF
- *
- * FIXME: for eBGP cases (when the LOCAL_PREF is missing), we should assign a policy-based preference
- * before we ever get here.
- */
- if (this.bestState.getLocalPref() == null && state.getLocalPref() != null) {
- return true;
- }
- if (this.bestState.getLocalPref() != null && state.getLocalPref() == null) {
- return false;
- }
- if (state.getLocalPref() != null && state.getLocalPref() > this.bestState.getLocalPref()) {
- return false;
- }
- if (state.getLocalPref() != null && state.getLocalPref() < this.bestState.getLocalPref()) {
- return true;
- }
- // 3. prefer learned path
- // - we assume that all paths are learned
-
- // 4. prefer the path with the shortest AS_PATH.
- if (this.bestState.getAsPathLength() != state.getAsPathLength()) {
- return this.bestState.getAsPathLength() < state.getAsPathLength();
- }
-
- // 5. prefer the path with the lowest origin type
- // - IGP is lower than Exterior Gateway Protocol (EGP), and EGP is lower than INCOMPLETE
- if (!this.bestState.getOrigin().equals(state.getOrigin())) {
- final BgpOrigin bo = this.bestState.getOrigin();
- final BgpOrigin no = state.getOrigin();
-
- // This trick relies on the order in which the values are declared in the model.
- return no.ordinal() > bo.ordinal();
- }
- // FIXME: we should be able to cache the best AS
- final Long bestAs = this.bestState.getPeerAs();
- final Long newAs = state.getPeerAs();
-
- /*
- * Checks 6 and 7 are mutually-exclusive, as MEDs are comparable
- * only when the routes originated from the same AS. On the other
- * hand, when they are from the same AS, they are in the same iBGP/eBGP
- * relationship.
- *
- */
- if (bestAs.equals(newAs)) {
- // 6. prefer the path with the lowest multi-exit discriminator (MED)
- if (this.bestState.getMultiExitDisc() != null || state.getMultiExitDisc() != null) {
- final Long bmed = this.bestState.getMultiExitDisc();
- final Long nmed = state.getMultiExitDisc();
- return nmed > bmed;
- }
- } else {
- /*
- * 7. prefer eBGP over iBGP paths
- *
- * EBGP is peering between two different AS, whereas IBGP is between same AS (Autonomous System),
- * so we just compare the AS numbers to our AS.
- *
- * FIXME: we should know this information from the peer directly.
- */
- if (!this.ourAs.equals(bestAs) && this.ourAs.equals(newAs)) {
- return true;
- }
- }
-
- // 8. Prefer the path with the lowest IGP metric to the BGP next hop.
- // - no next hop metric is advertised
-
- /*
- * 9. When both paths are external, prefer the path that was received first (the oldest one).
- *
- * FIXME: we do not want to store an explicit timer for each set due to performance/memory
- * constraints. Our caller has the information about which attributes have changed
- * since the selection process has ran last time, which may be a good enough approximation,
- * but its properties need to be analyzed.
- */
-
- /*
- * 10. Prefer the route that comes from the BGP router with the lowest router ID.
- *
- * This is normally guaranteed by the iteration order of our caller, which runs selection
- * in the order of increasing router ID, but RFC-4456 Route Reflection throws a wrench into that.
- *
- * With RFC-5004, this gets a bit easier, because it completely eliminates step f) and later :-)
- *
- * RFC-5004 states that this algorithm should end here and select existing path over new path in the
- * best path selection process. Benefits are listed in the RFC: @see http://tools.ietf.org/html/rfc500
- * - This algorithm SHOULD NOT be applied when either path is from a BGP Confederation peer.
- * - not applicable, we don't deal with confederation peers
- * - The algorithm SHOULD NOT be applied when both paths are from peers with an identical BGP identifier
- * (i.e., there exist parallel BGP sessions between two BGP speakers).
- * - not applicable, BUG-2631 prevents parallel sessions to be created.
- */
- return true;
- }
}
\ No newline at end of file
final class BaseSimpleRouteEntry extends BaseAbstractRouteEntry {
@Override
- public boolean removeRoute(UnsignedInteger routerId) {
+ public boolean removeRoute(UnsignedInteger routerId, final long remotePathId) {
return removeRoute(routerId, getOffsets().offsetOf(routerId));
}
+++ /dev/null
-/*
- * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved.
- *
- * This program and the accompanying materials are made available under the
- * terms of the Eclipse Public License v1.0 which accompanies this distribution,
- * and is available at http://www.eclipse.org/legal/epl-v10.html
- */
-package org.opendaylight.protocol.bgp.mode.impl.base;
-
-import com.google.common.base.Preconditions;
-import com.google.common.cache.CacheBuilder;
-import com.google.common.cache.CacheLoader;
-import com.google.common.cache.LoadingCache;
-import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.ImmutableSet.Builder;
-import com.google.common.primitives.UnsignedInteger;
-import java.lang.reflect.Array;
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.Set;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
-/**
- * A map of Router identifier to an offset. Used to maintain a simple
- * offset-based lookup across multiple {@link BaseAbstractRouteEntry} objects,
- * which share either contributors or consumers.
- * We also provide utility reformat methods, which provide access to
- * array members and array management features.
- */
-final class OffsetMap {
- static final OffsetMap EMPTY = new OffsetMap(Collections.<UnsignedInteger>emptySet());
- private static final Logger LOG = LoggerFactory.getLogger(OffsetMap.class);
- private static final LoadingCache<Set<UnsignedInteger>, OffsetMap> OFFSETMAPS = CacheBuilder.newBuilder().weakValues().build(new CacheLoader<Set<UnsignedInteger>, OffsetMap>() {
- @Override
- public OffsetMap load(final Set<UnsignedInteger> key) throws Exception {
- return new OffsetMap(key);
- }
- });
- private static final Comparator<UnsignedInteger> IPV4_COMPARATOR = new Comparator<UnsignedInteger>() {
- @Override
- public int compare(final UnsignedInteger o1, final UnsignedInteger o2) {
- return o1.compareTo(o2);
- }
- };
- private final UnsignedInteger[] routerIds;
-
- private OffsetMap(final Set<UnsignedInteger> routerIds) {
- final UnsignedInteger[] array = routerIds.toArray(new UnsignedInteger[routerIds.size()]);
- Arrays.sort(array, IPV4_COMPARATOR);
- this.routerIds = array;
- }
-
- UnsignedInteger getRouterId(final int offset) {
- Preconditions.checkArgument(offset >= 0);
- return this.routerIds[offset];
- }
-
- int offsetOf(final UnsignedInteger routerId) {
- return Arrays.binarySearch(this.routerIds, routerId, IPV4_COMPARATOR);
- }
-
- int size() {
- return this.routerIds.length;
- }
-
- boolean isEmty() {
- return this.routerIds.length == 0;
- }
-
- OffsetMap with(final UnsignedInteger routerId) {
- // TODO: we could make this faster if we had an array-backed Set and requiring
- // the caller to give us the result of offsetOf() -- as that indicates
- // where to insert the new routerId while maintaining the sorted nature
- // of the array
- final Builder<UnsignedInteger> b = ImmutableSet.builder();
- b.add(this.routerIds);
- b.add(routerId);
-
- return OFFSETMAPS.getUnchecked(b.build());
- }
-
- OffsetMap without(final UnsignedInteger routerId) {
- final Builder<UnsignedInteger> b = ImmutableSet.builder();
- int index = indexOfRouterId(routerId);
- if (index < 0) {
- LOG.trace("RouterId not found", routerId);
- }
- b.add(removeValue(this.routerIds, index));
- return OFFSETMAPS.getUnchecked(b.build());
- }
-
- private int indexOfRouterId(final UnsignedInteger routerId) {
- final int startIndex = 0;
- for (int i = startIndex; i < this.routerIds.length; i++) {
- if (routerId.equals(this.routerIds[i])) {
- return i;
- }
- }
- return -1;
- }
-
- <T> T getValue(final T[] array, final int offset) {
- Preconditions.checkArgument(offset >= 0, "Invalid negative offset %s", offset);
- Preconditions.checkArgument(offset < routerIds.length, "Invalid offset %s for %s router IDs", offset, routerIds.length);
- return array[offset];
- }
-
- <T> void setValue(final T[] array, final int offset, final T value) {
- Preconditions.checkArgument(offset >= 0, "Invalid negative offset %s", offset);
- Preconditions.checkArgument(offset < routerIds.length, "Invalid offset %s for %s router IDs", offset, routerIds.length);
- array[offset] = value;
- }
-
- <T> T[] expand(final OffsetMap oldOffsets, final T[] oldArray, final int offset) {
- @SuppressWarnings("unchecked")
- final T[] ret = (T[]) Array.newInstance(oldArray.getClass().getComponentType(), this.routerIds.length);
- final int oldSize = oldOffsets.routerIds.length;
-
- System.arraycopy(oldArray, 0, ret, 0, offset);
- System.arraycopy(oldArray, offset, ret, offset + 1, oldSize - offset);
-
- return ret;
- }
-
- <T> T[] removeValue(final T[] oldArray, final int offset) {
- final int length = oldArray.length;
- Preconditions.checkArgument(offset >= 0, "Invalid negative offset %s", offset);
- Preconditions.checkArgument(offset < routerIds.length, "Invalid offset %s for %s router IDs", offset, length);
-
- final T[] ret = (T[]) Array.newInstance(oldArray.getClass().getComponentType(), length - 1);
- System.arraycopy(oldArray, 0, ret, 0, offset);
- if (offset < length - 1) {
- System.arraycopy(oldArray, offset + 1, ret, offset, length - offset - 1);
- }
-
- return ret;
- }
-}
public final String toString() {
return addToStringAttributes(MoreObjects.toStringHelper(this)).toString();
}
-}
\ No newline at end of file
+}
--- /dev/null
+/*
+ * Copyright (c) 2016 Cisco Systems, Inc. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+
+package org.opendaylight.protocol.bgp.mode.spi;
+
+import com.google.common.base.Optional;
+import com.google.common.collect.ImmutableList;
+import com.google.common.primitives.UnsignedInteger;
+import java.util.Collection;
+import javax.annotation.Nonnull;
+import org.opendaylight.protocol.bgp.mode.api.BestPathState;
+import org.opendaylight.protocol.bgp.rib.spi.RouterIds;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.message.rev130919.OriginatorId;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.types.rev130919.BgpOrigin;
+import org.opendaylight.yangtools.yang.common.QName;
+import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
+import org.opendaylight.yangtools.yang.data.api.schema.ContainerNode;
+import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
+import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNodes;
+
+public class AbstractBestPathSelector {
+ private static final Collection<YangInstanceIdentifier.PathArgument> ORIGINATOR_ID = ImmutableList.<YangInstanceIdentifier.PathArgument>of(new
+ YangInstanceIdentifier.NodeIdentifier(OriginatorId.QNAME), new YangInstanceIdentifier.NodeIdentifier(QName.create(OriginatorId.QNAME, "originator")));
+
+ private final Long ourAs;
+ protected UnsignedInteger bestOriginatorId = null;
+ protected BestPathState bestState = null;
+
+ protected AbstractBestPathSelector(final Long ourAs) {
+ this.ourAs = ourAs;
+ }
+
+ /**
+ * RFC 4456 mandates the use of Originator IDs instead of Router ID for
+ * selection purposes.
+ * @param routerId routerID
+ * @param attrs router attributes
+ * @return returns originators Id if present otherwise routerId
+ */
+ protected UnsignedInteger replaceOriginator(final UnsignedInteger routerId, final ContainerNode attrs) {
+ final Optional<NormalizedNode<?, ?>> maybeOriginatorId = NormalizedNodes.findNode(attrs, ORIGINATOR_ID);
+ if (maybeOriginatorId.isPresent()) {
+ return RouterIds.routerIdForAddress((String) maybeOriginatorId.get().getValue());
+ } else {
+ return routerId;
+ }
+ }
+
+ /**
+ * Chooses best route according to BGP best path selection.
+ *
+ * @param state attributes of the new route
+ * @return true if the existing path is better, false if the new path is better
+ */
+ protected boolean isExistingPathBetter(@Nonnull final BestPathState state) {
+ // 1. prefer path with accessible nexthop
+ // - we assume that all nexthops are accessible
+ /*
+ * 2. prefer path with higher LOCAL_PREF
+ *
+ * FIXME: for eBGP cases (when the LOCAL_PREF is missing), we should assign a policy-based preference
+ * before we ever get here.
+ */
+ if (this.bestState.getLocalPref() == null && state.getLocalPref() != null) {
+ return true;
+ }
+ if (this.bestState.getLocalPref() != null && state.getLocalPref() == null) {
+ return false;
+ }
+ if (state.getLocalPref() != null && state.getLocalPref() > this.bestState.getLocalPref()) {
+ return false;
+ }
+ if (state.getLocalPref() != null && state.getLocalPref() < this.bestState.getLocalPref()) {
+ return true;
+ }
+ // 3. prefer learned path
+ // - we assume that all paths are learned
+
+ // 4. prefer the path with the shortest AS_PATH.
+ if (this.bestState.getAsPathLength() != state.getAsPathLength()) {
+ return this.bestState.getAsPathLength() < state.getAsPathLength();
+ }
+
+ // 5. prefer the path with the lowest origin type
+ // - IGP is lower than Exterior Gateway Protocol (EGP), and EGP is lower than INCOMPLETE
+ if (!this.bestState.getOrigin().equals(state.getOrigin())) {
+ final BgpOrigin bo = this.bestState.getOrigin();
+ final BgpOrigin no = state.getOrigin();
+
+ // This trick relies on the order in which the values are declared in the model.
+ return no.ordinal() > bo.ordinal();
+ }
+ // FIXME: we should be able to cache the best AS
+ final Long bestAs = this.bestState.getPeerAs();
+ final Long newAs = state.getPeerAs();
+
+ /*
+ * Checks 6 and 7 are mutually-exclusive, as MEDs are comparable
+ * only when the routes originated from the same AS. On the other
+ * hand, when they are from the same AS, they are in the same iBGP/eBGP
+ * relationship.
+ *
+ */
+ if (bestAs.equals(newAs)) {
+ // 6. prefer the path with the lowest multi-exit discriminator (MED)
+ if (this.bestState.getMultiExitDisc() != null || state.getMultiExitDisc() != null) {
+ final Long bmed = this.bestState.getMultiExitDisc();
+ final Long nmed = state.getMultiExitDisc();
+ return nmed > bmed;
+ }
+ } else {
+ /*
+ * 7. prefer eBGP over iBGP paths
+ *
+ * EBGP is peering between two different AS, whereas IBGP is between same AS (Autonomous System),
+ * so we just compare the AS numbers to our AS.
+ *
+ * FIXME: we should know this information from the peer directly.
+ */
+ if (!this.ourAs.equals(bestAs) && this.ourAs.equals(newAs)) {
+ return true;
+ }
+ }
+
+ // 8. Prefer the path with the lowest IGP metric to the BGP next hop.
+ // - no next hop metric is advertised
+
+ /*
+ * 9. When both paths are external, prefer the path that was received first (the oldest one).
+ *
+ * FIXME: we do not want to store an explicit timer for each set due to performance/memory
+ * constraints. Our caller has the information about which attributes have changed
+ * since the selection process has ran last time, which may be a good enough approximation,
+ * but its properties need to be analyzed.
+ */
+
+ /*
+ * 10. Prefer the route that comes from the BGP router with the lowest router ID.
+ *
+ * This is normally guaranteed by the iteration order of our caller, which runs selection
+ * in the order of increasing router ID, but RFC-4456 Route Reflection throws a wrench into that.
+ *
+ * With RFC-5004, this gets a bit easier, because it completely eliminates step f) and later :-)
+ *
+ * RFC-5004 states that this algorithm should end here and select existing path over new path in the
+ * best path selection process. Benefits are listed in the RFC: @see http://tools.ietf.org/html/rfc500
+ * - This algorithm SHOULD NOT be applied when either path is from a BGP Confederation peer.
+ * - not applicable, we don't deal with confederation peers
+ * - The algorithm SHOULD NOT be applied when both paths are from peers with an identical BGP identifier
+ * (i.e., there exist parallel BGP sessions between two BGP speakers).
+ * - not applicable, BUG-2631 prevents parallel sessions to be created.
+ */
+ return true;
+ }
+}
--- /dev/null
+/*
+ * Copyright (c) 2016 Cisco Systems, Inc. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+
+package org.opendaylight.protocol.bgp.mode.spi;
+
+import org.opendaylight.controller.md.sal.common.api.data.LogicalDatastoreType;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataWriteTransaction;
+import org.opendaylight.protocol.bgp.mode.api.RouteEntry;
+import org.opendaylight.protocol.bgp.rib.spi.CacheDisconnectedPeers;
+import org.opendaylight.protocol.bgp.rib.spi.ExportPolicyPeerTracker;
+import org.opendaylight.protocol.bgp.rib.spi.RIBSupport;
+import org.opendaylight.protocol.bgp.rib.spi.RibSupportUtils;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.PeerId;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.bgp.rib.rib.peer.AdjRibOut;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.rib.Tables;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.rib.TablesKey;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.rib.tables.Routes;
+import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
+import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier;
+import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
+import org.opendaylight.yangtools.yang.data.api.schema.ContainerNode;
+import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+abstract public class AbstractRouteEntry implements RouteEntry {
+ protected static final NodeIdentifier ROUTES_IDENTIFIER = new NodeIdentifier(Routes.QNAME);
+ private static final Logger LOG = LoggerFactory.getLogger(AbstractRouteEntry.class);
+
+ protected final void fillLocRib(final YangInstanceIdentifier routeTarget, final NormalizedNode<?, ?> value, final DOMDataWriteTransaction tx) {
+ if (value != null) {
+ LOG.debug("Write route to LocRib {}", value);
+ tx.put(LogicalDatastoreType.OPERATIONAL, routeTarget, value);
+ } else {
+ LOG.debug("Delete route from LocRib {}", routeTarget);
+ tx.delete(LogicalDatastoreType.OPERATIONAL, routeTarget);
+ }
+ }
+
+ protected final boolean writeRoute(final PeerId destPeer, final YangInstanceIdentifier routeTarget, final ContainerNode effAttrib,
+ final NormalizedNode<?, ?> value, final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
+ if (effAttrib != null && value != null) {
+ LOG.debug("Write route {} to peer AdjRibsOut {}", value, destPeer);
+ tx.put(LogicalDatastoreType.OPERATIONAL, routeTarget, value);
+ tx.put(LogicalDatastoreType.OPERATIONAL, routeTarget.node(ribSup.routeAttributesIdentifier()), effAttrib);
+ return true;
+ }
+ return false;
+ }
+
+ protected final boolean filterRoutes(final PeerId rootPeer, final PeerId destPeer, final ExportPolicyPeerTracker peerPT,
+ final TablesKey localTK, final CacheDisconnectedPeers discPeers) {
+ return !rootPeer.equals(destPeer) && isTableSupported(destPeer, peerPT, localTK) && !discPeers.isPeerDisconnected(destPeer);
+ }
+
+ private boolean isTableSupported(final PeerId destPeer, final ExportPolicyPeerTracker peerPT, final TablesKey localTK) {
+ if (!peerPT.isTableSupported(destPeer)) {
+ LOG.trace("Route rejected, peer {} does not support this table type {}", destPeer, localTK);
+ return false;
+ }
+ return true;
+ }
+
+ protected final YangInstanceIdentifier getAdjRibOutYII(final RIBSupport ribSup, final YangInstanceIdentifier rootPath, final PathArgument routeId,
+ final TablesKey localTK) {
+ return ribSup.routePath(rootPath.node(AdjRibOut.QNAME).node(Tables.QNAME).node(RibSupportUtils.toYangTablesKey(localTK))
+ .node(ROUTES_IDENTIFIER), routeId);
+ }
+}
base "config:service-type";
config:java-class "org.opendaylight.protocol.bgp.mode.api.PathSelectionMode";
}
+
+ identity advertise-n-paths {
+ base config:module-type;
+ config:provided-service path-selection-mode-factory;
+ config:java-name-prefix AdvertiseNPaths;
+ }
+
+ augment "/config:modules/config:module/config:configuration" {
+ case advertise-n-paths {
+ when "/config:modules/config:module/config:type = 'advertise-n-paths'";
+ leaf n-best-paths {
+ description "Expected n best path selection.";
+ type uint32;
+ default 2;
+ }
+ }
+ }
}
\ No newline at end of file
import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;
+import com.google.common.primitives.UnsignedInteger;
import org.junit.Test;
+import org.opendaylight.protocol.bgp.mode.impl.OffsetMap;
import org.opendaylight.protocol.bgp.rib.spi.RouterIds;
public class OffsetMapTest {
@Test
public void testAllMethods() {
- final OffsetMap offsetMap = OffsetMap.EMPTY.with(RouterIds.routerIdForAddress(LOCAL_ADDRESS));
- assertEquals(EXPECTED_ROUTER_OFFSET, offsetMap.offsetOf(RouterIds.routerIdForAddress(LOCAL_ADDRESS)));
- assertEquals(LOCAL_ADDRESS_DECIMAL, offsetMap.getRouterId(EXPECTED_ROUTER_OFFSET).intValue());
+ final OffsetMap<UnsignedInteger> offsetMap = new OffsetMap<>(UnsignedInteger.class);
+ final OffsetMap<UnsignedInteger> newOffsets = offsetMap.with(RouterIds.routerIdForAddress(LOCAL_ADDRESS));
+ assertEquals(EXPECTED_ROUTER_OFFSET, newOffsets.offsetOf(RouterIds.routerIdForAddress(LOCAL_ADDRESS)));
+ assertEquals(LOCAL_ADDRESS_DECIMAL, newOffsets.getRouterKey(EXPECTED_ROUTER_OFFSET).intValue());
- assertEquals(EXPECTED_VALUE, (int) offsetMap.getValue(TESTED_VALUES, EXPECTED_ROUTER_OFFSET));
- offsetMap.setValue(TESTED_VALUES, EXPECTED_ROUTER_OFFSET, CHANGED_VALUE);
- assertEquals(CHANGED_VALUE, (int) offsetMap.getValue(TESTED_VALUES, EXPECTED_ROUTER_OFFSET));
- assertArrayEquals(TESTED_VALUES_REMOVE, offsetMap.removeValue(TESTED_VALUES, 0));
- assertEquals(0, offsetMap.without(RouterIds.routerIdForAddress(LOCAL_ADDRESS)).size());
+ assertEquals(EXPECTED_VALUE, (int) newOffsets.getValue(TESTED_VALUES, EXPECTED_ROUTER_OFFSET));
+ newOffsets.setValue(TESTED_VALUES, EXPECTED_ROUTER_OFFSET, CHANGED_VALUE);
+ assertEquals(CHANGED_VALUE, (int) newOffsets.getValue(TESTED_VALUES, EXPECTED_ROUTER_OFFSET));
+ assertArrayEquals(TESTED_VALUES_REMOVE, newOffsets.removeValue(TESTED_VALUES, 0));
+ assertEquals(0, newOffsets.without(RouterIds.routerIdForAddress(LOCAL_ADDRESS)).size());
}
}
package org.opendaylight.protocol.bgp.rib.impl;
import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Optional;
import com.google.common.collect.ImmutableCollection;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.inet.rev150305.ipv4.routes.Ipv4Routes;
import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.inet.rev150305.ipv4.routes.ipv4.routes.Ipv4Route;
import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.inet.rev150305.update.attributes.mp.reach.nlri.advertized.routes.destination.type.DestinationIpv4CaseBuilder;
+import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.message.rev130919.PathId;
import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.multiprotocol.rev130919.update.attributes.MpReachNlri;
import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.multiprotocol.rev130919.update.attributes.MpReachNlriBuilder;
import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.multiprotocol.rev130919.update.attributes.MpUnreachNlri;
import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifierWithPredicates;
import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
import org.opendaylight.yangtools.yang.data.api.schema.ChoiceNode;
+import org.opendaylight.yangtools.yang.data.api.schema.DataContainerChild;
import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNodes;
final List<Ipv4Prefixes> prefs = new ArrayList<>(routes.size());
for (final MapEntryNode route : routes) {
final String prefix = (String) route.getChild(this.routeKeyLeaf).get().getValue();
- prefs.add(new Ipv4PrefixesBuilder().setPrefix(new Ipv4Prefix(prefix)).build());
+ final Ipv4PrefixesBuilder prefixBuilder = new Ipv4PrefixesBuilder().setPrefix(new Ipv4Prefix(prefix));
+ final Optional<DataContainerChild<? extends PathArgument, ?>> pathIdChild = route.getChild(this.pathIdLeaf);
+ if(pathIdChild.isPresent()) {
+ prefixBuilder.setPathId(new PathId((Long) pathIdChild.get().getValue()));
+ }
+ prefs.add(prefixBuilder.build());
}
return prefs;
}
final PeerRole newPeerRole = this.peerPolicyTracker.getRole(IdentifierUtils.peerPath(rootPath));
final PeerExportGroup peerGroup = this.peerPolicyTracker.getPeerGroup(newPeerRole);
this.routeEntries.entrySet().forEach(entry -> entry.getValue().writeRoute(peerIdOfNewPeer, entry.getKey(), rootPath, peerGroup,
- this.localTablesKey, this.ribSupport, tx));
+ this.localTablesKey, this.peerPolicyTracker, this.ribSupport, this.cacheDisconnectedPeers, tx));
}
}
final PathArgument routeId = route.getIdentifier();
RouteEntry entry = this.routeEntries.get(routeId);
final Optional<NormalizedNode<?, ?>> maybeData = route.getDataAfter();
+ final Optional<NormalizedNode<?, ?>> maybeDataBefore = route.getDataBefore();
if (maybeData.isPresent()) {
if (entry == null) {
entry = createEntry(routeId);
}
- entry.addRoute(routerId, this.attributesIdentifier, maybeData.get());
- } else if (entry != null && entry.removeRoute(routerId)) {
+ entry.addRoute(routerId, this.ribSupport.extractPathId(maybeData.get()), this.attributesIdentifier, maybeData.get());
+ } else if (entry != null && entry.removeRoute(routerId, this.ribSupport.extractPathId(maybeDataBefore.get()))) {
this.routeEntries.remove(routeId);
LOG.trace("Removed route from {}", routerId);
}