IMPLEMENTATION.txt 5.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170
  1. $Id: IMPLEMENTATION.txt,v 1.2 2005/02/15 17:10:03 gdt Exp $
  2. This file contains notes about the internals of the BGP
  3. implementation. The initial impetus is understanding the memory usage
  4. of Quagga'a BGP implementation. There may be some inaccuracies; it is
  5. in the repository in the hopes that it will be significantly more
  6. helpful than not.
  7. * FILES
  8. bgp_advertise.[hc]:
  9. data structures: advertised prefixes, attributes
  10. bgp_aspath.[hc]:
  11. struct aspath:
  12. These are stored in a hash, apparently in wire format.
  13. bgp_attr.[hc]:
  14. struct attr: contains all attributes
  15. size(ILP32) 26 words/104 bytes (poor packing, v6/multicast is 10)
  16. bgp_attr_parse: origin, aspath, next hop probably most of interest
  17. bgp_attr_origin: set flag bit
  18. bgp_attr_aspath: put in refcounted hash table, so share pointer
  19. bgp_attr_nexthop: store in attribute structure
  20. bgp_btoa.c: ? test program
  21. bgp_clist.[hc]:
  22. data structures: community lists (including permit/deny state)
  23. bgp_community.[hc]:
  24. data structures: community atttributes (multiple communities per struct)
  25. bgp_damp.[hc]:
  26. per-route damping data, and damping control information
  27. bgp_debug.[hc]:
  28. debugging support (vty config, dump of packets)
  29. bgp_dump.[hc]:
  30. MRT-compatible dump format routines
  31. bgp_ecommunity.[hc]:
  32. Extended communities attributes (multiple ecommmunities per struct)
  33. bgp_filter.[hc]:
  34. AS path access list filtering
  35. bgp_fsm.[hc]:
  36. Per-peer state machine for TCP connection, hold time, etc.
  37. bgp_main.c:
  38. Daemon startup.
  39. bgp_mplsvpn.[hc]:
  40. parsing of attribute structures for MPLS VPNs [need better description]
  41. bgp_network.[hc]:
  42. Opening and binding of sockets, finding addresses for interfaces
  43. bgp_nexthop.[hc]:
  44. data structures: Nexthop cache [not clear how used, if truly cache
  45. in sense of memoization, or something else]
  46. importing EGP routes into IGP (thread created)
  47. "scanning" (thread created)
  48. bgp_scan: has useful clues to data structure complexity. Scanning
  49. process iterates over database of received advertisements, and
  50. builds 'cache' structure.
  51. bgp_open.[ch]:
  52. Open messages, and capability negotiation
  53. bgp_packet.[hc]
  54. sending and receiving of UPDATE/WITHDRAW
  55. collision resolution for simultanteous opens
  56. bgp_read: top-level read routine: reads whole packet (nonblocking)
  57. and dispatches to per-message-type receive
  58. bgp_update_receive:
  59. calls bgp_attr_parse
  60. reads nrli into struct bgp_nrli update
  61. uninterning of aspath, community, ecommmunity, cluster,
  62. transit which were interned in bgp_attr_parse
  63. bgp_regex.[ch]:
  64. Glue to convert BGP regexps to standard (_ means many things).
  65. bgp_route.[hc]:
  66. data structures: routes as received, static routes
  67. Application of filters. Lots of route processing.
  68. bgp_nlri_parse:
  69. sanity checks, then calls bgp_update with peer, prefix, attributes pointer
  70. bgp_update: bgp_update_main, then RS processing
  71. bgp_update_main:
  72. find 'struct bgp_node *' for this afi/safi
  73. look for route in table, then 'intern' attributes
  74. ** interning is process of
  75. looking for data in hash table, and putting there if missing, refcnt
  76. using pointer to existing data
  77. many validity checks
  78. get new struct bgp_info (10 words/40 bytes)
  79. call bgp_info_add with rn and bgp_info
  80. call bgp_process
  81. bgp_routemap.c
  82. implementation of route maps (match and set)
  83. bgp_snmp.c
  84. SNMP glue. Not particularly interesting except to add variables or
  85. debug SNMP.
  86. bgp_table.[hc]
  87. data structures: struct bgp_table, struct bgp_node
  88. allocation/lookup/utility operations - not a lot of protocol processin
  89. bgp_vty.[hc]
  90. protocol-wide vty hooks
  91. bgp_zebra.[hc]
  92. Processing interface events from zebra, redistribution of routes.
  93. bgpd.h
  94. struct bgp_master: daemon main data structure
  95. struct bgp: per-instance structure
  96. struct peer_group
  97. struct bgp_notify: (in-core representation of wire format?)
  98. struct bgp_nexthop: (v4 and v6 addresses, *ifp)
  99. struct bgp_rd: router distinguisher: 8 octects
  100. struct bgp_filter: distribute, prefix, aslist, route_maps
  101. struct peer: neighbor structure (very rich/complex)
  102. struct bgp_nlri: reference to wire format
  103. #define of protocol constants
  104. attribute type codes
  105. fsm states/events
  106. timer values
  107. bgpd.c
  108. instance/peer allocation
  109. configuration
  110. initialization/termination
  111. * DATA STRUCTURE SIZES
  112. Question: How much memory does quagga's bgpd use as a function of
  113. state received from peers?
  114. It seems that a struct bgp_info is kept for each prefix. The "struct
  115. attr *" is interned, and variables within that are interned. So, 40
  116. bytes are kept per received prefix, plus interned shared values. This
  117. could be 36 if 'int suppress' where changed to a u_char and moved to
  118. be with the other u_chars. Without MPLS, this could be 32 bytes.
  119. Note that 8 bytes of this is linked list overhead, meaning that 24
  120. bytes are the raw per-prefix storage requirements.
  121. Also, a struct bgp_damp_info is apparently maintained per route; this
  122. is fairly large (about 44 bytes).
  123. [TODO: the role of struct bgp_node.]
  124. * TIME COMPLEXITY
  125. It appears that received prefixes from each peer are stored in a
  126. linked list.