$Id: IMPLEMENTATION.txt,v 1.2 2005/02/15 17:10:03 gdt Exp $

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_info (10 words/40 bytes)
    call bgp_info_add with rn and bgp_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_rd: router distinguisher: 8 octects
  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_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.