Source: ../../bgp/aspath.hh
|
|
|
|
// -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*-
// Copyright (c) 2001-2004 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.16 2004/06/10 22:40:28 hodson 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/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.
*/
// AS Path Values
enum ASPathSegType {
AS_NONE = 0, // not initialized
AS_SET = 1,
AS_SEQUENCE = 2
};
/**
* 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) { 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)
return 1;
else if (_type == AS_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", (uint32_t)_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", (uint32_t)_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;
/**
* Convert the external representation into the internal one.
* _type is d[0], _entries is d[1], entries follow.
*/
void decode(const uint8_t *d);
/**
* 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;
private:
ASPathSegType _type;
size_t _entries; // # of AS numbers in the as path
list <AsNum> _aslist;
};
/**
* An AsPath is a list of AsSegments, each of which can be an AS_SET
* or an AS_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) { 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);
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 {
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);
}
assert("Segment doesn't exist.\n"); // XXX eh ?
xorp_throw(InvalidString, "segment invalid n\n");
}
size_t num_segments() const { return _num_segments; }
/**
* 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.
* 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);
bool operator==(const AsPath& him) const;
bool operator<(const AsPath& him) const;
void encode_for_mib(vector<uint8_t>& aspath) const;
private:
/**
* populate an AsPath from received data. Only used in the constructor.
*/
void decode(const uint8_t *d, size_t len);
/**
* internal representation
*/
list <AsSegment> _segments;
size_t _num_segments;
size_t _path_len;
};
#endif // __BGP_ASPATH_HH__
Generated by: pavlin on possum.icir.org on Thu Jul 8 23:48:33 2004, using kdoc $.
