1 $Id: IMPLEMENTATION.txt,v 1.2 2005/02/15 17:10:03 gdt Exp $
3 This file contains notes about the internals of the BGP
4 implementation. The initial impetus is understanding the memory usage
5 of Quagga'a BGP implementation. There may be some inaccuracies; it is
6 in the repository in the hopes that it will be significantly more
12 data structures: advertised prefixes, attributes
16 These are stored in a hash, apparently in wire format.
19 struct attr: contains all attributes
20 size(ILP32) 26 words/104 bytes (poor packing, v6/multicast is 10)
22 bgp_attr_parse: origin, aspath, next hop probably most of interest
23 bgp_attr_origin: set flag bit
24 bgp_attr_aspath: put in refcounted hash table, so share pointer
25 bgp_attr_nexthop: store in attribute structure
27 bgp_btoa.c: ? test program
30 data structures: community lists (including permit/deny state)
33 data structures: community atttributes (multiple communities per struct)
36 per-route damping data, and damping control information
39 debugging support (vty config, dump of packets)
42 MRT-compatible dump format routines
45 Extended communities attributes (multiple ecommmunities per struct)
48 AS path access list filtering
51 Per-peer state machine for TCP connection, hold time, etc.
57 parsing of attribute structures for MPLS VPNs [need better description]
60 Opening and binding of sockets, finding addresses for interfaces
63 data structures: Nexthop cache [not clear how used, if truly cache
64 in sense of memoization, or something else]
66 importing EGP routes into IGP (thread created)
67 "scanning" (thread created)
68 bgp_scan: has useful clues to data structure complexity. Scanning
69 process iterates over database of received advertisements, and
70 builds 'cache' structure.
73 Open messages, and capability negotiation
76 sending and receiving of UPDATE/WITHDRAW
77 collision resolution for simultanteous opens
78 bgp_read: top-level read routine: reads whole packet (nonblocking)
79 and dispatches to per-message-type receive
83 reads nrli into struct bgp_nrli update
85 uninterning of aspath, community, ecommmunity, cluster,
86 transit which were interned in bgp_attr_parse
89 Glue to convert BGP regexps to standard (_ means many things).
92 data structures: routes as received, static routes
93 Application of filters. Lots of route processing.
96 sanity checks, then calls bgp_update with peer, prefix, attributes pointer
98 bgp_update: bgp_update_main, then RS processing
101 find 'struct bgp_node *' for this afi/safi
102 look for route in table, then 'intern' attributes
103 ** interning is process of
104 looking for data in hash table, and putting there if missing, refcnt
105 using pointer to existing data
107 get new struct bgp_path_info
108 call bgp_path_info_add with rn and bgp_path_info
112 implementation of route maps (match and set)
115 SNMP glue. Not particularly interesting except to add variables or
119 data structures: struct bgp_table, struct bgp_node
120 allocation/lookup/utility operations - not a lot of protocol processin
123 protocol-wide vty hooks
126 Processing interface events from zebra, redistribution of routes.
129 struct bgp_master: daemon main data structure
130 struct bgp: per-instance structure
132 struct bgp_notify: (in-core representation of wire format?)
133 struct bgp_nexthop: (v4 and v6 addresses, *ifp)
134 struct bgp_filter: distribute, prefix, aslist, route_maps
135 struct peer: neighbor structure (very rich/complex)
136 struct bgp_nlri: reference to wire format
137 #define of protocol constants
143 instance/peer allocation
145 initialization/termination
147 * DATA STRUCTURE SIZES
149 Question: How much memory does quagga's bgpd use as a function of
150 state received from peers?
152 It seems that a struct bgp_path_info is kept for each prefix. The "struct
153 attr *" is interned, and variables within that are interned. So, 40
154 bytes are kept per received prefix, plus interned shared values. This
155 could be 36 if 'int suppress' where changed to a u_char and moved to
156 be with the other u_chars. Without MPLS, this could be 32 bytes.
157 Note that 8 bytes of this is linked list overhead, meaning that 24
158 bytes are the raw per-prefix storage requirements.
160 Also, a struct bgp_damp_info is apparently maintained per route; this
161 is fairly large (about 44 bytes).
163 [TODO: the role of struct bgp_node.]
167 It appears that received prefixes from each peer are stored in a