FRR BGP 协议分析 0 --- IMPLEMENTATION abourt BGP structures

今天药忘吃喽~ 2023-06-14 04:21 94阅读 0赞

This file contains notes about the internals of the BGP implementation.  The initial impetus is understanding the memory usage of Quagga'a BGP implementation.  There may be some inaccuracies; it is in the repository in the hopes that it will be significantly more helpful than not.

#    \* FILES   bgp\_advertise.\[hc\]: #

data structures: advertised prefixes, attributes

#    bgp\_aspath.\[hc\]: #

struct aspath: These are stored in a hash, apparently in wire format.

#    bgp\_attr.\[hc\]: #

struct attr: contains all attributes size(ILP32) 26 words/104 bytes (poor packing, v6/multicast is 10)  
  bgp\_attr\_parse: origin, aspath, next hop probably most of interest

bgp\_attr\_origin: set flag bit  
  bgp\_attr\_aspath: put in refcounted hash table, so share pointer

bgp\_attr\_nexthop: store in attribute structure

# bgp\_btoa.c: #

? test program

#    bgp\_clist.\[hc\]: #

data structures: community lists (including permit/deny state)

#    bgp\_community.\[hc\]: #

data structures: community atttributes (multiple communities per struct)

#    bgp\_damp.\[hc\]: #

per-route damping data, and damping control information

#    bgp\_debug.\[hc\]: #

debugging support (vty config, dump of packets)

#    bgp\_dump.\[hc\]: #

MRT-compatible dump format routines

#    bgp\_ecommunity.\[hc\]: #

Extended communities attributes (multiple ecommmunities per struct)

#    bgp\_filter.\[hc\]: #

AS path access list filtering

#    bgp\_fsm.\[hc\]: #

Per-peer state machine for TCP connection, hold time, etc.

#    bgp\_main.c: Daemon startup. #

#    bgp\_mplsvpn.\[hc\]: #

parsing of attribute structures for MPLS VPNs \[need better description\]

#    bgp\_network.\[hc\]: #

Opening and binding of sockets, finding addresses for interfaces

#    bgp\_nexthop.\[hc\]: #

data structures: Nexthop cache \[not clear how used, if truly cache  
  in sense of memoization, or something else\]  
  importing EGP routes into IGP (thread created)  
  "scanning" (thread created)  
  bgp\_scan: has useful clues to data structure complexity.  Scanning process iterates over database of received

advertisements,   and builds 'cache' structure.

bgp\_open.\[ch\]:

Open messages, and capability negotiation

#    bgp\_packet.\[hc\] #

sending and receiving of UPDATE/WITHDRAW  
  collision resolution for simultanteous opens  
  bgp\_read: top-level read routine: reads whole packet (nonblocking) and dispatches to per-message-type receive

bgp\_update\_receive: calls bgp\_attr\_parse  
    reads nrli into struct bgp\_nrli update  
    uninterning of aspath, community, ecommmunity, cluster,  
    transit which were interned in bgp\_attr\_parse

# bgp\_regex.\[ch\]: #

Glue to convert BGP regexps to standard (\_ means many things).

#    bgp\_route.\[hc\]: #

data structures: routes as received, static routes  
  Application of filters.  Lots of route processing.

bgp\_nlri\_parse: sanity checks, then calls bgp\_update with peer, prefix, attributes pointer

bgp\_update: bgp\_update\_main, then RS processing

bgp\_update\_main:

find 'struct bgp\_node \*' for this afi/safi  
    look for route in table, then 'intern' attributes  
    \*\* interning is process of looking for data in hash table, and putting there if missing, refcnt using pointer to existing data many validity checks  
    get new struct bgp\_path\_info  
    call bgp\_path\_info\_add with rn and bgp\_path\_info  
    call bgp\_process

# bgp\_routemap.c #

implementation of route maps (match and set)

# bgp\_snmp.c #

SNMP glue.  Not particularly interesting except to add variables or debug SNMP.

bgp\_table.\[hc\] data structures:

struct bgp\_table, struct bgp\_node  
  allocation/lookup/utility operations - not a lot of protocol processin

#    bgp\_vty.\[hc\] #

protocol-wide vty hooks

#    bgp\_zebra.\[hc\] #

Processing interface events from zebra, redistribution of routes.

#    bgpd.h #

struct bgp\_master: daemon main data structure   
  struct bgp: per-instance structure  
  struct peer\_group  
  struct bgp\_notify: (in-core representation of wire format?)  
  struct bgp\_nexthop: (v4 and v6 addresses, \*ifp)  
  struct bgp\_filter: distribute, prefix, aslist, route\_maps  
  struct peer: neighbor structure (very rich/complex)  
  struct bgp\_nlri: reference to wire format  
  \#define of protocol constants attribute type codes fsm states/events  
  timer values

# bgpd.c #

instance/peer allocation  
  configuration  
  initialization/termination  
\* DATA STRUCTURE SIZES

Question: How much memory does quagga's bgpd use as a function of state received from peers?  
It seems that a struct bgp\_path\_info is kept for each prefix.  The "struct attr \*" is interned, and variables within that are interned.  So, 40 bytes are kept per received prefix, plus interned shared values.  This could be 36 if 'int suppress' where changed to a u\_char and moved to be with the other u\_chars.  Without MPLS, this could be 32 bytes. Note that 8 bytes of this is linked list overhead, meaning that 24 bytes are the raw per-prefix storage requirements.  
Also, a struct bgp\_damp\_info is apparently maintained per route; this is fairly large (about 44 bytes).  
\[TODO: the role of struct bgp\_node.\]  
\* TIME COMPLEXITY  
It appears that received prefixes from each peer are stored in a linked list.