Source: ../../bgp/aspath.hh


 
LOGO
 Annotated List  Files  Globals  Hierarchy  Index  Top
// -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*-

// Copyright (c) 2001-2005 International Computer Science Institute
//
// Permission is hereby granted, free of charge, to any person obtaining a
// copy of this software and associated documentation files (the "Software")
// to deal in the Software without restriction, subject to the conditions
// listed in the XORP LICENSE file. These conditions include: you must
// preserve this copyright notice, and you cannot mention the copyright
// holders in advertising related to the Software without their permission.
// The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
// notice is a summary of the XORP LICENSE file; the license in that file is
// legally binding.

// $XORP: xorp/bgp/aspath.hh,v 1.24 2005/12/20 13:00:38 atanu Exp $

#ifndef __BGP_ASPATH_HH__
#define __BGP_ASPATH_HH__

#include <sys/types.h>
#include <inttypes.h>
#include <string>
#include <list>
#include <vector>

#include "libxorp/xorp.h"
#include "libxorp/debug.h"
#include "libxorp/xlog.h"
#include "libxorp/asnum.hh"
#include "libxorp/exceptions.hh"
#include "exceptions.hh"

/**
 * This file contains the classes to manipulate AS segments/lists/paths
 *
 * An AS_PATH is made of a list of segments, each segment being
 * an AS_SET or an AS_SEQUENCE.
 * Logically, you can think an AS_SEQUENCE as a list of AsNum,
 * and an AS_SET as an unordered set of AsNum; the path would then be
 * made of alternate AS_SET and AS_SEQUENCEs. However, the max number
 * of elements in an AS_SEQUENCE is 255, so you might need to split a
 * sequence into multiple ones.
 *
 * The external representation of AS_SET or AS_SEQUENCE is:
 *   1 byte:	segment type
 *   1 byte:	number of element in the segment
 *   n entries:	the ASnumbers in the segment, 2 or 4 bytes each
 *
 * In terms of internal representation, it might be more efficient
 * useful to store segments as either an AS_SET, or a sequence of size 1,
 * and then do the necessary grouping on output.
 *
 * The current implementation allows both forms.
 *
 * Note that the external representation (provided by encode()) returns
 * a malloc'ed chunk of memory which must be freed by the caller.
 *
 * RFC 3065 (Autonomous System Confederations for BGP) introduced two
 * additional segment types:
 *
 * AS_CONFED_SEQUENCE: ordered set of Member AS Numbers
 * in the local confederation that the UPDATE message has traversed
 *
 * AS_CONFED_SET: unordered set of Member AS Numbers in
 * the local confederation that the UPDATE message has traversed
 *  
 */

// AS Path Values
enum ASPathSegType {
    AS_NONE = 0,	// not initialized
    AS_SET = 1,
    AS_SEQUENCE = 2,
    AS_CONFED_SEQUENCE = 3,
    AS_CONFED_SET = 4
};

/**
 * Parent class for AsPath elements, which can be either AsSet or AsSequence.
 */
class AsSegment {
public:
    typedef list <AsNum>::iterator iterator;
    typedef list <AsNum>::const_iterator const_iterator;
    typedef list <AsNum>::const_reverse_iterator const_reverse_iterator;

    /**
     * Constructor of an empty AsSegment
     */
    AsSegment(ASPathSegType t = AS_NONE) : _type(t), _entries(0) {}

    /**
     * constructor from external representation will just decode
     * the chunk of data received, and convert to internal representation.
     * In fact, the external representation is quite simple and effective.
     *
     * _type is d[0], l is d[1], entries follow.
     */
    AsSegment(const uint8_t* d) throw(CorruptMessage) { decode(d); }

    /**
     * Copy constructor
     */
    AsSegment(const AsSegment& a) :
	    _type(a._type), _entries(a._entries), _aslist(a._aslist)	{}

    /**
     * The destructor has nothing to do, the underlying container will
     * take care of the thing.
     */
    ~AsSegment()					{}

    /**
     * reset whatever is currently contained in the object.
     */
    void clear()					{
	_type = AS_NONE;
	_aslist.clear();
	_entries = 0;
    }

    /**
     * @return the path length, which is 1 for an AS_SET,
     * and the length of the sequence for an AS_SEQUENCE
     */
    size_t path_length() const				{
	if (_type == AS_SET || _type == AS_CONFED_SET)
	    return 1;
	else if (_type == AS_SEQUENCE || _type == AS_CONFED_SEQUENCE)
	    return _entries;
	else
	    return 0; // XXX should not be called!
    }

    size_t as_size() const				{ return _entries; }

    /**
     * Add AsNum at the end of the segment (order is irrelevant
     * for AS_SET but important for AS_SEQUENCE)
     * This is used when initializing from a string.
     */
    void add_as(const AsNum& n)				{
	debug_msg("Number of As entries %u\n", XORP_UINT_CAST(_entries));
	_aslist.push_back(n);
	_entries++;
    }

    /**
     * Add AsNum at the beginning of the segment (order is irrelevant
     * for AS_SET but important for AS_SEQUENCE).
     * This is used e.g. when a node is adding its AsNum to the sequence.
     */
    void prepend_as(const AsNum& n)			{
	debug_msg("Number of As entries %u\n", XORP_UINT_CAST(_entries));
	_aslist.push_front(n);
	_entries++;
    }

    /**
     * Check if a given AsNum is contained in the segment.
     */
    bool contains(const AsNum& as_num) const		{
	list <AsNum>::const_iterator iter;

	for (iter = _aslist.begin(); iter != _aslist.end(); ++iter)
	    if (*iter == as_num)
		return true;
	return false;
    }

    const AsNum& first_asnum() const;

    /**
     * find the n'th AS number in the segment 
     */
    const AsNum& as_num(int n) const {
	list <AsNum>::const_iterator iter;
	iter = _aslist.begin();
	while (n > 0) {
	    iter++;
	    n--;
	    XLOG_ASSERT(iter != _aslist.end());
	}
	return *iter;
    }

    /**
     * Convert the external representation into the internal one.
     * _type is d[0], _entries is d[1], entries follow.
     */
    void decode(const uint8_t *d) throw(CorruptMessage);

    /**
     * Convert from internal to external representation.
     * If we do not pass a buffer (buf = 0), then the routine will
     * allocate a new one; otherwise, len indicates the size of the
     * input buffer, which must be large enough to store the encoding.
     * @return the pointer to the buffer, len is the actual size.
     */
    const uint8_t *encode(size_t &len, uint8_t *buf) const;

    /**
     * @return the size of the list on the wire.
     */
    size_t wire_size() const			{ return 2 + 2*_entries; }

    /**
     * @return fancy string representation of the segment
     */
    string str() const;

    /**
     * @return compact string representation of the segment
     */
    string short_str() const;

    /**
     * compares internal representations for equality.
     */
    bool operator==(const AsSegment& him) const;

    /**
     * Compares internal representations for <.
     */
    bool operator<(const AsSegment& him) const;

    ASPathSegType type() const			{ return _type; }
    void set_type(ASPathSegType t)		{ _type = t; }

    size_t encode_for_mib(uint8_t* buf, size_t buf_size) const;

    /**
     * returns true if the AS segment does not lose information when
     * represented entirely as two-byte AS numbers 
     */
    bool two_byte_compatible() const;

protected:
    ASPathSegType	_type;
    size_t		_entries;	// # of AS numbers in the as path
    list <AsNum>	_aslist;
};


/* subsclass of AsSegment to handle encoding and decoding of 4-byte AS
   numbers from a NEW_AS_PATH attribute */
class NewAsSegment : public AsSegment {
public:
    NewAsSegment(const uint8_t* d) throw(CorruptMessage) { decode(d); }
    /**
     * Convert the external representation into the internal one.
     * _type is d[0], _entries is d[1], entries follow.
     */
    void decode(const uint8_t *d) throw(CorruptMessage);

    /**
     * Convert from internal to external representation.
     * If we do not pass a buffer (buf = 0), then the routine will
     * allocate a new one; otherwise, len indicates the size of the
     * input buffer, which must be large enough to store the encoding.
     * @return the pointer to the buffer, len is the actual size.
     */
    const uint8_t *encode(size_t &len, uint8_t *buf) const;

    /**
     * @return the size of the list on the wire.
     */
    size_t wire_size() const			{ return 2 + 4*_entries; }
private:
    /* no storage, as this is handled by the underlying AsSegment */
};

/**
 * An AsPath is a list of AsSegments, each of which can be an AS_SET,
 * AS_CONFED_SET, AS_SEQUENCE, or an AS_CONFED_SEQUENCE.
 */
class AsPath {
public:
    typedef list <AsSegment>::const_iterator const_iterator;
    typedef list <AsSegment>::iterator iterator;

    AsPath() : _num_segments(0), _path_len(0)		{}

    /**
     * Initialize from a string in the format
     *		1,2,(3,4,5),6,7,8,(9,10,11),12,13
     */
    AsPath(const char *as_path) throw(InvalidString);

    /**
     * construct from received data
     */
    AsPath(const uint8_t* d, size_t len) throw(CorruptMessage) {
	decode(d, len); 
    }

    /**
     * Copy constructor
     */
    AsPath(const AsPath &a) : _segments(a._segments), 
	_num_segments(a._num_segments), _path_len(a._path_len) {}

    ~AsPath()						{}

    void add_segment(const AsSegment& s);
    void prepend_segment(const AsSegment& s);

    size_t path_length() const				{ return _path_len; }

    bool contains(const AsNum& as_num) const		{
	const_iterator i = _segments.begin();
	for (; i != _segments.end(); ++i)
	    if ((*i).contains(as_num))
		return true;
	return false;
    }

    const AsNum& first_asnum() const			{
	XLOG_ASSERT(!_segments.empty());
	return _segments.front().first_asnum();
    }

    string str() const;
    string short_str() const;

    const AsSegment& segment(size_t n) const		{
	if (n < _num_segments) {
	    const_iterator iter = _segments.begin();
	    for (u_int i = 0; i<n; i++)
		++iter;
	    return (*iter);
        }
	XLOG_FATAL("Segment doesn't exist.");
	xorp_throw(InvalidString, "segment invalid n\n");
    }

    size_t num_segments() const			{ return _num_segments; }

    /**
     * Convert from internal to external representation, with the
     * correct representation for the original AS_PATH attribute.  If
     * there are any 4-byte AS numbers, they will be encoded as
     * AS_TRAN.
     *
     * If we do not pass a buffer (buf = 0), then the routine will
     * allocate a new one; otherwise, len indicates the size of the
     * input buffer, which must be large enough to store the encoding.
     * @return the pointer to the buffer, len is the actual size.
     */
    const uint8_t *encode(size_t &len, uint8_t *buf) const;

    /**
     * @return the size of the list on the wire.
     * XXX this should be made more efficient.
     */
    size_t wire_size() const;

    /**
     * Add the As number to the begining of the AS_SEQUENCE that starts
     * the As path, or if the AsPath starts with an AS_SET, then add a
     * new AS_SEQUENCE with the new AsNum to the start of the AsPath
     */
    void prepend_as(const AsNum &asn);

    /**
     * Add the As number to the begining of the AS_CONFED_SEQUENCE
     * that starts the As path, or if the AsPath does not start with
     * an AS_CONFED_SEQUENCE, then add a new AS_CONFED_SEQUENCE with
     * the new AsNum to the start of the AsPath
     */
    void prepend_confed_as(const AsNum &asn);

    /**
     * remove all confederation segments from aspath 
     */
    void remove_confed_segments();

    /**
     * @return true if the AS_PATH Contains confederation segments.
     */
    bool contains_confed_segments() const;

    bool operator==(const AsPath& him) const;

    bool operator<(const AsPath& him) const;

    void encode_for_mib(vector<uint8_t>& aspath) const;

    /**
     * returns true if the AS path does not lose information when
     * represented entirely as two-byte AS numbers */
    bool two_byte_compatible() const;

protected:
    /**
     * internal representation
     */
    list <AsSegment>	_segments;
    size_t		_num_segments;
    size_t		_path_len;

private:
    /**
     * populate an AsPath from received data. Only used in the constructor.
     */
    void decode(const uint8_t *d, size_t len) throw(CorruptMessage);
};

/* subclass to handle 4-byte AS encoding and decoding */
class NewAsPath : public AsPath {
public:
    /**
     * construct from received data.  This needs to take the regular
     * AsPath in addition to the NEW_AS_PATH data, because it needs to
     * cross-validate the two.
     */
    NewAsPath(const uint8_t* d, size_t len, const AsPath& as_path)
	throw(CorruptMessage);

    /**
     * Convert from internal to external representation, with the
     * correct representation for the original NEW_AS_PATH attribute.
     *
     * If we do not pass a buffer (buf = 0), then the routine will
     * allocate a new one; otherwise, len indicates the size of the
     * input buffer, which must be large enough to store the encoding.
     * @return the pointer to the buffer, len is the actual size.
     */
    const uint8_t *encode(size_t &len, uint8_t *buf) const;

    size_t wire_size() const;

private:
    /**
     * populate an AsPath from received data. Only used in the constructor.
     */
    void decode(const uint8_t *d, size_t len) throw(CorruptMessage);
    void cross_validate(const AsPath& as_path);
    void pad_segment(const AsSegment& old_seg, AsSegment& new_seg);
    void do_patchup(const AsPath& as_path);
};

#endif // __BGP_ASPATH_HH__

Generated by: pavlin on possum.icir.org on Thu Mar 9 04:43:34 2006, using kdoc $.