1
1
// -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*-
3
// Copyright (c) 2001-2007 International Computer Science Institute
3
// Copyright (c) 2001-2008 International Computer Science Institute
5
5
// Permission is hereby granted, free of charge, to any person obtaining a
6
6
// copy of this software and associated documentation files (the "Software")
12
12
// notice is a summary of the XORP LICENSE file; the license in that file is
13
13
// legally binding.
15
// $XORP: xorp/bgp/aspath.hh,v 1.29 2007/04/05 02:02:48 zec Exp $
15
// $XORP: xorp/bgp/aspath.hh,v 1.31 2008/01/04 03:15:17 pavlin Exp $
17
17
#ifndef __BGP_ASPATH_HH__
18
18
#define __BGP_ASPATH_HH__
64
66
* AS_CONFED_SET: unordered set of Member AS Numbers in
65
67
* the local confederation that the UPDATE message has traversed
70
* 4-byte AS numbers need to be handled carefully. There are two main
71
* cases to consider: when we are configured to do 4-byte AS numbers,
72
* and when we are not.
74
* When we are not configured to do 4-byte AS numbers all AS path
75
* information received from peers will be 2-byte AS numbers. If
76
* they're configured to do 4-byte AS numbers, they will send us an
77
* AS_PATH and an AS4_PATH, but if we're not configured to do 4-byte
78
* AS numbers, we shouldn't care. We don't merge the two; we
79
* propagate AS4_PATH unchanged, and do the normal stuff with the
80
* regular AS_PATH. The AS4_PATH is actually stored internally in an
81
* UnknownAttribute, as we don't need to know anything about it.
83
* When we are configured to do 4-byte AS numbers, we can tell from
84
* the negotiated capabilities whether a peer is sending 4-byte AS
85
* numbers or 2-byte AS numbers. If a peer is sending 4-byte AS
86
* numbers, these arrive in the AS_PATH attribute, and we store them
87
* internally in an AS4Path, but stored in the ASPathAttribute, NOT in
88
* the AS4PathAttribute. If a peer is sending 2-byte AS numbers in
89
* AS_PATH, he may also propagate an AS4_PATH. We merge these on
90
* input, cross-validate the two, and store the results just like we
91
* would if we'd received a 4-byte AS_PATH. So, whatever our peer
92
* does, the only place we have AS path information that we use for
93
* the decision process is in the ASPathAttribute.
95
* If we're doing 4-byte AS numbers and our peer is doing 4-byte AS
96
* numbers, then all routes we send him will contain 4-byte AS_PATH
97
* attributes. We just need to make sure we use the right encode()
98
* method. If our peer is not doing 4-byte AS numbers, then we send a
99
* 2-byte AS_PATH, substituting AS_TRANS for any AS numbers that can't
100
* be represented in 2 bytes. We also construct an AS4_PATH from our
101
* ASPathAttribute, and send that too.
79
* Parent class for AsPath elements, which can be either AsSet or AsSequence.
114
* Parent class for ASPath elements, which can be either ASSet or ASSequence.
83
118
typedef vector <AsNum>::iterator iterator;
84
119
typedef vector <AsNum>::const_iterator const_iterator;
85
120
typedef vector <AsNum>::const_reverse_iterator const_reverse_iterator;
88
* Constructor of an empty AsSegment
123
* Constructor of an empty ASSegment
90
AsSegment(ASPathSegType t = AS_NONE) : _type(t) {
125
ASSegment(ASPathSegType t = AS_NONE) : _type(t) {
91
126
_aslist.reserve(16);
107
142
* Copy constructor
109
AsSegment(const AsSegment& a) :
144
ASSegment(const ASSegment& a) :
110
145
_type(a._type), _aslist(a._aslist) {}
113
148
* The destructor has nothing to do, the underlying container will
114
149
* take care of the thing.
119
154
* reset whatever is currently contained in the object.
217
252
* compares internal representations for equality.
219
bool operator==(const AsSegment& him) const;
254
bool operator==(const ASSegment& him) const;
222
257
* Compares internal representations for <.
224
bool operator<(const AsSegment& him) const;
259
bool operator<(const ASSegment& him) const;
226
261
ASPathSegType type() const { return _type; }
227
262
void set_type(ASPathSegType t) { _type = t; }
243
/* subsclass of AsSegment to handle encoding and decoding of 4-byte AS
278
/* subsclass of ASSegment to handle encoding and decoding of 4-byte AS
244
279
numbers from a AS4_PATH attribute */
245
class As4Segment : public AsSegment {
280
class AS4Segment : public ASSegment {
247
As4Segment(const uint8_t* d) throw(CorruptMessage) { decode(d); }
282
AS4Segment(const uint8_t* d) throw(CorruptMessage) { decode(d); }
249
284
* Convert the external representation into the internal one.
250
285
* _type is d[0], _entries is d[1], entries follow.
267
302
return 2 + 4 * _aslist.size();
270
/* no storage, as this is handled by the underlying AsSegment */
305
/* no storage, as this is handled by the underlying ASSegment */
274
* An AsPath is a list of AsSegments, each of which can be an AS_SET,
309
* An ASPath is a list of ASSegments, each of which can be an AS_SET,
275
310
* AS_CONFED_SET, AS_SEQUENCE, or an AS_CONFED_SEQUENCE.
279
typedef list <AsSegment>::const_iterator const_iterator;
280
typedef list <AsSegment>::iterator iterator;
314
typedef list <ASSegment>::const_iterator const_iterator;
315
typedef list <ASSegment>::iterator iterator;
282
AsPath() : _num_segments(0), _path_len(0) {}
317
ASPath() : _num_segments(0), _path_len(0) {}
285
320
* Initialize from a string in the format
286
321
* 1,2,(3,4,5),6,7,8,(9,10,11),12,13
288
AsPath(const char *as_path) throw(InvalidString);
323
ASPath(const char *as_path) throw(InvalidString);
291
326
* construct from received data
293
AsPath(const uint8_t* d, size_t len) throw(CorruptMessage) {
328
ASPath(const uint8_t* d, size_t len) throw(CorruptMessage) {
298
* construct an aggregate from two AsPaths
333
* construct an aggregate from two ASPaths
300
AsPath(const AsPath &asp1, const AsPath &asp2);
335
ASPath(const ASPath &asp1, const ASPath &asp2);
303
338
* Copy constructor
305
AsPath(const AsPath &a) : _segments(a._segments),
340
ASPath(const ASPath &a) : _segments(a._segments),
306
341
_num_segments(a._num_segments), _path_len(a._path_len) {}
310
void add_segment(const AsSegment& s);
311
void prepend_segment(const AsSegment& s);
345
void add_segment(const ASSegment& s);
346
void prepend_segment(const ASSegment& s);
313
348
size_t path_length() const { return _path_len; }
328
363
string str() const;
329
364
string short_str() const;
331
const AsSegment& segment(size_t n) const {
366
const ASSegment& segment(size_t n) const {
332
367
if (n < _num_segments) {
333
368
const_iterator iter = _segments.begin();
334
369
for (u_int i = 0; i<n; i++)
338
XLOG_FATAL("Segment doesn't exist.");
373
XLOG_FATAL("Segment %u doesn't exist.", (uint32_t)n);
339
374
xorp_throw(InvalidString, "segment invalid n\n");
364
399
* Add the As number to the begining of the AS_SEQUENCE that starts
365
* the As path, or if the AsPath starts with an AS_SET, then add a
366
* new AS_SEQUENCE with the new AsNum to the start of the AsPath
400
* the As path, or if the ASPath starts with an AS_SET, then add a
401
* new AS_SEQUENCE with the new AsNum to the start of the ASPath
368
403
void prepend_as(const AsNum &asn);
371
406
* Add the As number to the begining of the AS_CONFED_SEQUENCE
372
* that starts the As path, or if the AsPath does not start with
407
* that starts the As path, or if the ASPath does not start with
373
408
* an AS_CONFED_SEQUENCE, then add a new AS_CONFED_SEQUENCE with
374
* the new AsNum to the start of the AsPath
409
* the new AsNum to the start of the ASPath
376
411
void prepend_confed_as(const AsNum &asn);
386
421
bool contains_confed_segments() const;
388
bool operator==(const AsPath& him) const;
390
bool operator<(const AsPath& him) const;
423
ASPath& operator=(const ASPath& him);
425
bool operator==(const ASPath& him) const;
427
bool operator<(const ASPath& him) const;
392
429
void encode_for_mib(vector<uint8_t>& aspath) const;
396
433
* represented entirely as two-byte AS numbers */
397
434
bool two_byte_compatible() const;
437
* Merge an AS4Path into a 2-byte AS Path. Both paths will end up
438
* containing the same data
440
* param as4path the AS4_PATH to be merged.
442
void merge_as4_path(AS4Path& as4_path);
401
446
* internal representation
403
list <AsSegment> _segments;
448
list <ASSegment> _segments;
404
449
size_t _num_segments;
405
450
size_t _path_len;
409
* populate an AsPath from received data. Only used in the constructor.
454
* populate an ASPath from received data. Only used in the constructor.
411
456
void decode(const uint8_t *d, size_t len) throw(CorruptMessage);
414
459
/* subclass to handle 4-byte AS encoding and decoding */
415
class As4Path : public AsPath {
460
class AS4Path : public ASPath {
418
* construct from received data. This needs to take the regular
419
* AsPath in addition to the AS4_PATH data, because it needs to
420
* cross-validate the two.
422
As4Path(const uint8_t* d, size_t len, const AsPath& as_path)
463
* Construct from received data from 4-byte peer.
465
AS4Path(const uint8_t* d, size_t len) throw(CorruptMessage);
468
* Initialize from a string in the format
469
* 3.1,2,(3,10.4,5),6,7,8,(9,10,11),12,13
471
AS4Path(const char *as_path) throw(InvalidString)
477
* Construct from received data from 2-byte peer. This needs to
478
* take the regular ASPath in addition to the AS4_PATH data,
479
* because it needs to cross-validate the two.
481
AS4Path(const uint8_t* d, size_t len, const ASPath& as_path)
423
482
throw(CorruptMessage);
426
487
* Convert from internal to external representation, with the
427
488
* correct representation for the original AS4_PATH attribute.
436
497
size_t wire_size() const;
499
void cross_validate(const ASPath& as_path);
440
* populate an AsPath from received data. Only used in the constructor.
503
* populate an ASPath from received data. Only used in the constructor.
442
505
void decode(const uint8_t *d, size_t len) throw(CorruptMessage);
443
void cross_validate(const AsPath& as_path);
444
void pad_segment(const AsSegment& old_seg, AsSegment& new_seg);
445
void do_patchup(const AsPath& as_path);
506
void pad_segment(const ASSegment& old_seg, ASSegment& new_seg);
507
void do_patchup(const ASPath& as_path);
448
510
#endif // __BGP_ASPATH_HH__
added
removed
bgp/aspath.hh
