diff options
Diffstat (limited to 'framework/src/onos/apps/routing/src/main/java/org/onosproject/routing/bgp/BgpRouteEntry.java')
-rw-r--r-- | framework/src/onos/apps/routing/src/main/java/org/onosproject/routing/bgp/BgpRouteEntry.java | 494 |
1 files changed, 494 insertions, 0 deletions
diff --git a/framework/src/onos/apps/routing/src/main/java/org/onosproject/routing/bgp/BgpRouteEntry.java b/framework/src/onos/apps/routing/src/main/java/org/onosproject/routing/bgp/BgpRouteEntry.java new file mode 100644 index 00000000..974da808 --- /dev/null +++ b/framework/src/onos/apps/routing/src/main/java/org/onosproject/routing/bgp/BgpRouteEntry.java @@ -0,0 +1,494 @@ +/* + * Copyright 2014-2015 Open Networking Laboratory + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.onosproject.routing.bgp; + +import com.google.common.base.MoreObjects; +import org.onlab.packet.Ip4Address; +import org.onlab.packet.IpAddress; +import org.onlab.packet.IpPrefix; +import org.onosproject.routing.RouteEntry; + +import java.util.ArrayList; +import java.util.Objects; + +import static com.google.common.base.Preconditions.checkNotNull; + +/** + * Represents a route in BGP. + */ +public class BgpRouteEntry extends RouteEntry { + private final BgpSession bgpSession; // The BGP Session the route was + // received on + private final byte origin; // Route ORIGIN: IGP, EGP, INCOMPLETE + private final AsPath asPath; // The AS Path + private final long localPref; // The local preference for the route + private long multiExitDisc = BgpConstants.Update.MultiExitDisc.LOWEST_MULTI_EXIT_DISC; + + /** + * Class constructor. + * + * @param bgpSession the BGP Session the route was received on + * @param prefix the prefix of the route + * @param nextHop the next hop of the route + * @param origin the route origin: 0=IGP, 1=EGP, 2=INCOMPLETE + * @param asPath the AS path + * @param localPref the route local preference + */ + public BgpRouteEntry(BgpSession bgpSession, IpPrefix prefix, + IpAddress nextHop, byte origin, + BgpRouteEntry.AsPath asPath, long localPref) { + super(prefix, nextHop); + this.bgpSession = checkNotNull(bgpSession); + this.origin = origin; + this.asPath = checkNotNull(asPath); + this.localPref = localPref; + } + + /** + * Gets the BGP Session the route was received on. + * + * @return the BGP Session the route was received on + */ + public BgpSession getBgpSession() { + return bgpSession; + } + + /** + * Gets the route origin: 0=IGP, 1=EGP, 2=INCOMPLETE. + * + * @return the route origin: 0=IGP, 1=EGP, 2=INCOMPLETE + */ + public byte getOrigin() { + return origin; + } + + /** + * Gets the route AS path. + * + * @return the route AS path + */ + public BgpRouteEntry.AsPath getAsPath() { + return asPath; + } + + /** + * Gets the route local preference. + * + * @return the route local preference + */ + public long getLocalPref() { + return localPref; + } + + /** + * Gets the route MED (Multi-Exit Discriminator). + * + * @return the route MED (Multi-Exit Discriminator) + */ + public long getMultiExitDisc() { + return multiExitDisc; + } + + /** + * Sets the route MED (Multi-Exit Discriminator). + * + * @param multiExitDisc the route MED (Multi-Exit Discriminator) to set + */ + void setMultiExitDisc(long multiExitDisc) { + this.multiExitDisc = multiExitDisc; + } + + /** + * Tests whether the route is originated from the local AS. + * <p> + * The route is considered originated from the local AS if the AS Path + * is empty or if it begins with an AS_SET (after skipping + * AS_CONFED_SEQUENCE and AS_CONFED_SET). + * </p> + * + * @return true if the route is originated from the local AS, otherwise + * false + */ + boolean isLocalRoute() { + PathSegment firstPathSegment = null; + + // Find the first Path Segment by ignoring the AS_CONFED_* segments + for (PathSegment pathSegment : asPath.getPathSegments()) { + if ((pathSegment.getType() == BgpConstants.Update.AsPath.AS_SET) || + (pathSegment.getType() == BgpConstants.Update.AsPath.AS_SEQUENCE)) { + firstPathSegment = pathSegment; + break; + } + } + if (firstPathSegment == null) { + return true; // Local route: no path segments + } + // If the first path segment is AS_SET, the route is considered local + if (firstPathSegment.getType() == BgpConstants.Update.AsPath.AS_SET) { + return true; + } + + return false; // The route is not local + } + + /** + * Gets the BGP Neighbor AS number the route was received from. + * <p> + * If the router is originated from the local AS, the return value is + * zero (BGP_AS_0). + * </p> + * + * @return the BGP Neighbor AS number the route was received from. + */ + long getNeighborAs() { + PathSegment firstPathSegment = null; + + if (isLocalRoute()) { + return BgpConstants.BGP_AS_0; + } + + // Find the first Path Segment by ignoring the AS_CONFED_* segments + for (PathSegment pathSegment : asPath.getPathSegments()) { + if ((pathSegment.getType() == BgpConstants.Update.AsPath.AS_SET) || + (pathSegment.getType() == BgpConstants.Update.AsPath.AS_SEQUENCE)) { + firstPathSegment = pathSegment; + break; + } + } + if (firstPathSegment == null) { + // NOTE: Shouldn't happen - should be captured by isLocalRoute() + return BgpConstants.BGP_AS_0; + } + + if (firstPathSegment.getSegmentAsNumbers().isEmpty()) { + // NOTE: Shouldn't happen. Should check during the parsing. + return BgpConstants.BGP_AS_0; + } + return firstPathSegment.getSegmentAsNumbers().get(0); + } + + /** + * Tests whether the AS Path contains a loop. + * <p> + * The test is done by comparing whether the AS Path contains the + * local AS number. + * </p> + * + * @param localAsNumber the local AS number to compare against + * @return true if the AS Path contains a loop, otherwise false + */ + boolean hasAsPathLoop(long localAsNumber) { + for (PathSegment pathSegment : asPath.getPathSegments()) { + for (Long asNumber : pathSegment.getSegmentAsNumbers()) { + if (asNumber.equals(localAsNumber)) { + return true; + } + } + } + return false; + } + + /** + * Compares this BGP route against another BGP route by using the + * BGP Decision Process. + * <p> + * NOTE: The comparison needs to be performed only on routes that have + * same IP Prefix. + * </p> + * + * @param other the BGP route to compare against + * @return true if this BGP route is better than the other BGP route + * or same, otherwise false + */ + boolean isBetterThan(BgpRouteEntry other) { + if (this == other) { + return true; // Return true if same route + } + + // Compare the LOCAL_PREF values: larger is better + if (getLocalPref() != other.getLocalPref()) { + return (getLocalPref() > other.getLocalPref()); + } + + // Compare the AS number in the path: smaller is better + if (getAsPath().getAsPathLength() != + other.getAsPath().getAsPathLength()) { + return getAsPath().getAsPathLength() < + other.getAsPath().getAsPathLength(); + } + + // Compare the Origin number: lower is better + if (getOrigin() != other.getOrigin()) { + return (getOrigin() < other.getOrigin()); + } + + // Compare the MED if the neighbor AS is same: larger is better + medLabel: { + if (isLocalRoute() || other.isLocalRoute()) { + // Compare MEDs for non-local routes only + break medLabel; + } + long thisNeighborAs = getNeighborAs(); + if (thisNeighborAs != other.getNeighborAs()) { + break medLabel; // AS number is different + } + if (thisNeighborAs == BgpConstants.BGP_AS_0) { + break medLabel; // Invalid AS number + } + + // Compare the MED + if (getMultiExitDisc() != other.getMultiExitDisc()) { + return (getMultiExitDisc() > other.getMultiExitDisc()); + } + } + + // Compare the peer BGP ID: lower is better + Ip4Address peerBgpId = getBgpSession().remoteInfo().bgpId(); + Ip4Address otherPeerBgpId = other.getBgpSession().remoteInfo().bgpId(); + if (!peerBgpId.equals(otherPeerBgpId)) { + return (peerBgpId.compareTo(otherPeerBgpId) < 0); + } + + // Compare the peer BGP address: lower is better + Ip4Address peerAddress = getBgpSession().remoteInfo().ip4Address(); + Ip4Address otherPeerAddress = + other.getBgpSession().remoteInfo().ip4Address(); + if (!peerAddress.equals(otherPeerAddress)) { + return (peerAddress.compareTo(otherPeerAddress) < 0); + } + + return true; // Routes are same. Shouldn't happen? + } + + /** + * A class to represent AS Path Segment. + */ + public static class PathSegment { + // Segment type: AS_SET(1), AS_SEQUENCE(2), AS_CONFED_SEQUENCE(3), + // AS_CONFED_SET(4) + private final byte type; + private final ArrayList<Long> segmentAsNumbers; // Segment AS numbers + + /** + * Constructor. + * + * @param type the Path Segment Type: AS_SET(1), AS_SEQUENCE(2), + * AS_CONFED_SEQUENCE(3), AS_CONFED_SET(4) + * @param segmentAsNumbers the Segment AS numbers + */ + PathSegment(byte type, ArrayList<Long> segmentAsNumbers) { + this.type = type; + this.segmentAsNumbers = checkNotNull(segmentAsNumbers); + } + + /** + * Gets the Path Segment Type: AS_SET(1), AS_SEQUENCE(2), + * AS_CONFED_SEQUENCE(3), AS_CONFED_SET(4). + * + * @return the Path Segment Type: AS_SET(1), AS_SEQUENCE(2), + * AS_CONFED_SEQUENCE(3), AS_CONFED_SET(4) + */ + public byte getType() { + return type; + } + + /** + * Gets the Path Segment AS Numbers. + * + * @return the Path Segment AS Numbers + */ + public ArrayList<Long> getSegmentAsNumbers() { + return segmentAsNumbers; + } + + @Override + public boolean equals(Object other) { + if (this == other) { + return true; + } + + if (!(other instanceof PathSegment)) { + return false; + } + + PathSegment otherPathSegment = (PathSegment) other; + return Objects.equals(this.type, otherPathSegment.type) && + Objects.equals(this.segmentAsNumbers, + otherPathSegment.segmentAsNumbers); + } + + @Override + public int hashCode() { + return Objects.hash(type, segmentAsNumbers); + } + + @Override + public String toString() { + return MoreObjects.toStringHelper(getClass()) + .add("type", BgpConstants.Update.AsPath.typeToString(type)) + .add("segmentAsNumbers", this.segmentAsNumbers) + .toString(); + } + } + + /** + * A class to represent AS Path. + */ + public static class AsPath { + private final ArrayList<PathSegment> pathSegments; + private final int asPathLength; // Precomputed AS Path Length + + /** + * Constructor. + * + * @param pathSegments the Path Segments of the Path + */ + AsPath(ArrayList<PathSegment> pathSegments) { + this.pathSegments = checkNotNull(pathSegments); + + // + // Precompute the AS Path Length: + // - AS_SET counts as 1 + // - AS_SEQUENCE counts how many AS numbers are included + // - AS_CONFED_SEQUENCE and AS_CONFED_SET are ignored + // + int pl = 0; + for (PathSegment pathSegment : pathSegments) { + switch (pathSegment.getType()) { + case BgpConstants.Update.AsPath.AS_SET: + pl++; // AS_SET counts as 1 + break; + case BgpConstants.Update.AsPath.AS_SEQUENCE: + // Count each AS number + pl += pathSegment.getSegmentAsNumbers().size(); + break; + case BgpConstants.Update.AsPath.AS_CONFED_SEQUENCE: + break; // Ignore + case BgpConstants.Update.AsPath.AS_CONFED_SET: + break; // Ignore + default: + // NOTE: What to do if the Path Segment type is unknown? + break; + } + } + asPathLength = pl; + } + + /** + * Gets the AS Path Segments. + * + * @return the AS Path Segments + */ + public ArrayList<PathSegment> getPathSegments() { + return pathSegments; + } + + /** + * Gets the AS Path Length as considered by the BGP Decision Process. + * + * @return the AS Path Length as considered by the BGP Decision Process + */ + int getAsPathLength() { + return asPathLength; + } + + @Override + public boolean equals(Object other) { + if (this == other) { + return true; + } + + if (!(other instanceof AsPath)) { + return false; + } + + AsPath otherAsPath = (AsPath) other; + return Objects.equals(this.pathSegments, otherAsPath.pathSegments); + } + + @Override + public int hashCode() { + return Objects.hash(pathSegments); + } + + @Override + public String toString() { + return MoreObjects.toStringHelper(getClass()) + .add("pathSegments", this.pathSegments) + .toString(); + } + } + + /** + * Compares whether two objects are equal. + * <p> + * NOTE: The bgpSession field is excluded from the comparison. + * </p> + * + * @return true if the two objects are equal, otherwise false. + */ + @Override + public boolean equals(Object other) { + if (this == other) { + return true; + } + + // + // NOTE: Subclasses are considered as change of identity, hence + // equals() will return false if the class type doesn't match. + // + if (other == null || getClass() != other.getClass()) { + return false; + } + + if (!super.equals(other)) { + return false; + } + + // NOTE: The bgpSession field is excluded from the comparison + BgpRouteEntry otherRoute = (BgpRouteEntry) other; + return (this.origin == otherRoute.origin) && + Objects.equals(this.asPath, otherRoute.asPath) && + (this.localPref == otherRoute.localPref) && + (this.multiExitDisc == otherRoute.multiExitDisc); + } + + /** + * Computes the hash code. + * <p> + * NOTE: We return the base class hash code to avoid expensive computation + * </p> + * + * @return the object hash code + */ + @Override + public int hashCode() { + return super.hashCode(); + } + + @Override + public String toString() { + return MoreObjects.toStringHelper(getClass()) + .add("prefix", prefix()) + .add("nextHop", nextHop()) + .add("bgpId", bgpSession.remoteInfo().bgpId()) + .add("origin", BgpConstants.Update.Origin.typeToString(origin)) + .add("asPath", asPath) + .add("localPref", localPref) + .add("multiExitDisc", multiExitDisc) + .toString(); + } +} |