1 /* 2 * scamper_tracelb.h 3 * 4 * $Id: scamper_tracelb.h,v 1.61 2020/04/02 06:45:02 mjl Exp $ 5 * 6 * Copyright (C) 2008-2009 The University of Waikato 7 * Copyright (C) 2018-2020 Matthew Luckie 8 * Author: Matthew Luckie 9 * 10 * Load-balancer traceroute technique authored by 11 * Brice Augustin, Timur Friedman, Renata Teixeira; "Measuring Load-balanced 12 * Paths in the Internet", in Proc. Internet Measurement Conference 2007. 13 * 14 * This program is free software; you can redistribute it and/or modify 15 * it under the terms of the GNU General Public License as published by 16 * the Free Software Foundation, version 2. 17 * 18 * This program is distributed in the hope that it will be useful, 19 * but WITHOUT ANY WARRANTY; without even the implied warranty of 20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 21 * GNU General Public License for more details. 22 * 23 * You should have received a copy of the GNU General Public License 24 * along with this program; if not, write to the Free Software 25 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 26 * 27 */ 28 29 #ifndef __SCAMPER_TRACELB_H 30 #define __SCAMPER_TRACELB_H 31 32 #include "scamper_addr.h" 33 #include "scamper_list.h" 34 #include "scamper_icmpext.h" 35 36 /* forward declare some important structures */ 37 typedef struct scamper_tracelb_node scamper_tracelb_node_t; 38 typedef struct scamper_tracelb_link scamper_tracelb_link_t; 39 typedef struct scamper_tracelb_probe scamper_tracelb_probe_t; 40 typedef struct scamper_tracelb_reply scamper_tracelb_reply_t; 41 typedef struct scamper_tracelb_probeset scamper_tracelb_probeset_t; 42 typedef struct scamper_tracelb_probeset_summary scamper_tracelb_probeset_summary_t; 43 44 /* 45 * these values give the 'type' member of a scamper_tracelb_t structure 46 * some meaning. 47 */ 48 #define SCAMPER_TRACELB_TYPE_UDP_DPORT 0x01 /* vary udp-dport */ 49 #define SCAMPER_TRACELB_TYPE_ICMP_ECHO 0x02 /* vary icmp checksum */ 50 #define SCAMPER_TRACELB_TYPE_UDP_SPORT 0x03 /* vary udp-sport */ 51 #define SCAMPER_TRACELB_TYPE_TCP_SPORT 0x04 /* vary tcp-sport */ 52 #define SCAMPER_TRACELB_TYPE_TCP_ACK_SPORT 0x05 /* tcp-ack, vary sport */ 53 54 /* 55 * these values give the 'flags' member of a scamper_tracelb_t structure 56 * some meaning. 57 */ 58 #define SCAMPER_TRACELB_FLAG_PTR 0x01 /* do ptr lookups */ 59 60 /* 61 * these values give the 'flags' member of a scamper_tracelb_node_t 62 * structure some meaning. 63 */ 64 #define SCAMPER_TRACELB_NODE_FLAG_QTTL 0x01 65 66 #define SCAMPER_TRACELB_NODE_QTTL(node) \ 67 ((node)->flags & SCAMPER_TRACELB_NODE_FLAG_QTTL) 68 69 #define SCAMPER_TRACELB_REPLY_FLAG_REPLY_TTL 0x01 /* reply ttl included */ 70 #define SCAMPER_TRACELB_REPLY_FLAG_TCP 0x02 /* reply is TCP */ 71 72 #define SCAMPER_TRACELB_REPLY_IS_ICMP_TTL_EXP(reply) ( \ 73 ((reply)->reply_flags & SCAMPER_TRACELB_REPLY_FLAG_TCP) == 0 && \ 74 (((reply)->reply_from->type == SCAMPER_ADDR_TYPE_IPV4 && \ 75 (reply)->reply_icmp_type == 11) || \ 76 ((reply)->reply_from->type == SCAMPER_ADDR_TYPE_IPV6 && \ 77 (reply)->reply_icmp_type == 3))) 78 79 #define SCAMPER_TRACELB_REPLY_IS_ICMP_UNREACH(reply) ( \ 80 ((reply)->reply_flags & SCAMPER_TRACELB_REPLY_FLAG_TCP) == 0 && \ 81 (((reply)->reply_from->type == SCAMPER_ADDR_TYPE_IPV4 && \ 82 (reply)->reply_icmp_type == 3) || \ 83 ((reply)->reply_from->type == SCAMPER_ADDR_TYPE_IPV6 && \ 84 (reply)->reply_icmp_type == 1))) 85 86 #define SCAMPER_TRACELB_REPLY_IS_ICMP_UNREACH_PORT(reply) ( \ 87 ((reply)->reply_flags & SCAMPER_TRACELB_REPLY_FLAG_TCP) == 0 && \ 88 (((reply)->reply_from->type == SCAMPER_ADDR_TYPE_IPV4 && \ 89 (reply)->reply_icmp_type == 3 && (reply)->reply_icmp_code == 3) || \ 90 ((reply)->reply_from->type == SCAMPER_ADDR_TYPE_IPV6 && \ 91 (reply)->reply_icmp_type == 1 && (reply)->reply_icmp_code == 4))) 92 93 #define SCAMPER_TRACELB_REPLY_IS_TCP(reply) ( \ 94 ((reply)->reply_flags & SCAMPER_TRACELB_REPLY_FLAG_TCP) != 0) 95 96 #define SCAMPER_TRACELB_TYPE_IS_TCP(trace) ( \ 97 ((trace)->type == SCAMPER_TRACELB_TYPE_TCP_SPORT || \ 98 (trace)->type == SCAMPER_TRACELB_TYPE_TCP_ACK_SPORT)) 99 100 #define SCAMPER_TRACELB_TYPE_IS_UDP(trace) ( \ 101 ((trace)->type == SCAMPER_TRACELB_TYPE_UDP_SPORT || \ 102 (trace)->type == SCAMPER_TRACELB_TYPE_UDP_DPORT)) 103 104 #define SCAMPER_TRACELB_TYPE_IS_ICMP(trace) ( \ 105 ((trace)->type == SCAMPER_TRACELB_TYPE_ICMP_ECHO)) 106 107 #define SCAMPER_TRACELB_TYPE_VARY_SPORT(trace) ( \ 108 ((trace)->type == SCAMPER_TRACELB_TYPE_UDP_SPORT || \ 109 (trace)->type == SCAMPER_TRACELB_TYPE_TCP_SPORT || \ 110 (trace)->type == SCAMPER_TRACELB_TYPE_TCP_ACK_SPORT)) 111 112 /* 113 * scamper_tracelb_reply_t 114 * 115 * record details of each reply received. 116 */ 117 struct scamper_tracelb_reply 118 { 119 scamper_addr_t *reply_from; /* source of response */ 120 struct timeval reply_rx; /* receive time */ 121 uint16_t reply_ipid; /* IP ID of reply packet */ 122 uint8_t reply_ttl; /* ttl of the reply packet */ 123 uint8_t reply_flags; /* reply flags */ 124 125 union 126 { 127 struct scamper_tracelb_reply_icmp 128 { 129 uint8_t reply_icmp_type; /* icmp type of the reply */ 130 uint8_t reply_icmp_code; /* icmp code of the reply */ 131 uint8_t reply_icmp_q_tos; /* tos byte in quote */ 132 uint8_t reply_icmp_q_ttl; /* ttl byte in quote */ 133 scamper_icmpext_t *reply_icmp_ext; /* icmp extensions included */ 134 } icmp; 135 struct scamper_tracelb_reply_tcp 136 { 137 uint8_t reply_tcp_flags; /* tcp flags of the reply */ 138 } tcp; 139 } reply_un; 140 }; 141 142 #define reply_icmp_type reply_un.icmp.reply_icmp_type 143 #define reply_icmp_code reply_un.icmp.reply_icmp_code 144 #define reply_icmp_ext reply_un.icmp.reply_icmp_ext 145 #define reply_icmp_q_ttl reply_un.icmp.reply_icmp_q_ttl 146 #define reply_icmp_q_tos reply_un.icmp.reply_icmp_q_tos 147 #define reply_tcp_flags reply_un.tcp.reply_tcp_flags 148 149 /* 150 * scamper_tracelb_probe_t 151 * 152 * record details of each probe sent, and any replies received. 153 */ 154 struct scamper_tracelb_probe 155 { 156 struct timeval tx; 157 uint16_t flowid; 158 uint8_t ttl; 159 uint8_t attempt; 160 scamper_tracelb_reply_t **rxs; 161 uint16_t rxc; 162 }; 163 164 /* 165 * scamper_tracelb_probeset_t 166 * 167 * record details of each probe sent in a particular set. 168 */ 169 struct scamper_tracelb_probeset 170 { 171 scamper_tracelb_probe_t **probes; /* array of probes sent */ 172 uint16_t probec; /* number of probes sent */ 173 }; 174 175 struct scamper_tracelb_probeset_summary 176 { 177 scamper_addr_t **addrs; 178 int addrc; 179 int nullc; 180 }; 181 182 /* 183 * scamper_tracelb_node_t 184 * 185 * record details of each node encountered 186 */ 187 struct scamper_tracelb_node 188 { 189 scamper_addr_t *addr; /* address of the node */ 190 char *name; /* PTR for the addr */ 191 uint8_t flags; /* associated flags */ 192 uint8_t q_ttl; /* quoted ttl */ 193 scamper_tracelb_link_t **links; /* links */ 194 uint16_t linkc; /* number of links */ 195 }; 196 197 /* 198 * scamper_tracelb_link_t 199 * 200 * record probe details of each link encountered 201 */ 202 struct scamper_tracelb_link 203 { 204 scamper_tracelb_node_t *from; /* link from */ 205 scamper_tracelb_node_t *to; /* link to */ 206 uint8_t hopc; /* distance between the nodes */ 207 scamper_tracelb_probeset_t **sets; /* array of probesets, for each hop */ 208 }; 209 210 /* 211 * scamper_tracelb_t 212 * 213 * structure containing the results of probing to enumerate all load balanced 214 * paths towards a destination 215 */ 216 typedef struct scamper_tracelb 217 { 218 /* the current list, cycle, and defaults */ 219 scamper_list_t *list; 220 scamper_cycle_t *cycle; 221 uint32_t userid; 222 223 /* source and destination addresses of the load balancer trace */ 224 scamper_addr_t *src; 225 scamper_addr_t *dst; 226 scamper_addr_t *rtr; 227 228 /* when the load balancer trace commenced */ 229 struct timeval start; 230 231 /* load balancer traceroute parameters */ 232 uint16_t sport; /* base source port */ 233 uint16_t dport; /* base destination port */ 234 uint16_t probe_size; /* size of probe to send */ 235 uint8_t type; /* probe type to use */ 236 uint8_t firsthop; /* where to start probing */ 237 uint8_t wait_timeout; /* seconds to wait before timeout */ 238 uint8_t wait_probe; /* min. inter-probe time per ttl */ 239 uint8_t attempts; /* number of attempts per probe */ 240 uint8_t confidence; /* confidence level to attain */ 241 uint8_t tos; /* type-of-service byte to use */ 242 uint8_t gaplimit; /* max consecutive unresp. hops */ 243 uint8_t flags; /* flags */ 244 uint32_t probec_max; /* max number of probes to send */ 245 246 /* 247 * data collected: 248 * 249 * nodes: 250 * an IP address from each node inferred between the source and the 251 * destination, recorded in the order they were discovered in 252 * 253 * links: 254 * all links between the source and destination, sorted numerically by 255 * from address and then by to address; each link contains the replies 256 * collected for it 257 * 258 * probec: 259 * count of probes sent. includes retries. 260 * 261 * error: 262 * if non-zero, something went wrong. 263 */ 264 scamper_tracelb_node_t **nodes; 265 uint16_t nodec; 266 scamper_tracelb_link_t **links; 267 uint16_t linkc; 268 uint32_t probec; 269 uint8_t error; 270 } scamper_tracelb_t; 271 272 /* 273 * basic scamper_tracelb_t routines: 274 * 275 * scamper_tracelb_alloc: allocate a scamper_tracelb_t structure 276 * scamper_tracelb_free: free a scamper_tracelb_t and contents 277 * scamper_tracelb_addr: return destination address of the scamper_tracelb_t 278 * scamper_tracelb_type_tostr: return a string specifying the trace type 279 * scamper_tracelb_sort: sort nodes and links in a deterministic manner 280 */ 281 scamper_tracelb_t *scamper_tracelb_alloc(void); 282 void scamper_tracelb_free(scamper_tracelb_t *); 283 scamper_addr_t *scamper_tracelb_addr(const void *); 284 const char *scamper_tracelb_type_tostr(const scamper_tracelb_t *trace); 285 int scamper_tracelb_sort(scamper_tracelb_t *); 286 287 /* 288 * basic scamper_tracelb_node_t routines: 289 * 290 * scamper_tracelb_node_alloc: allocate a scamper_tracelb_node_t structure 291 * scamper_tracelb_node_free: free a scamper_tracelb_node_t and contents 292 * scamper_tracelb_node_add: add a node to a scamper_tracelb_t structure 293 * scamper_tracelb_node_find: find a node structure by address 294 * scamper_tracelb_node_cmp: comparison function for comparing nodes 295 */ 296 scamper_tracelb_node_t *scamper_tracelb_node_alloc(scamper_addr_t *); 297 void scamper_tracelb_node_free(scamper_tracelb_node_t *); 298 int scamper_tracelb_node_add(scamper_tracelb_t *, 299 scamper_tracelb_node_t *); 300 scamper_tracelb_node_t *scamper_tracelb_node_find(scamper_tracelb_t *, 301 scamper_tracelb_node_t *); 302 int scamper_tracelb_node_cmp(const scamper_tracelb_node_t *, 303 const scamper_tracelb_node_t *); 304 int scamper_tracelb_node_links_alloc(scamper_tracelb_node_t *, uint16_t); 305 void scamper_tracelb_node_links_sort(scamper_tracelb_node_t *); 306 307 /* 308 * basic scamper_tracelb_reply_t routines: 309 * 310 * scamper_tracelb_reply_alloc: allocate a scamper_tracelb_reply_t structure 311 * scamper_tracelb_reply_free: free a reply structure 312 */ 313 scamper_tracelb_reply_t *scamper_tracelb_reply_alloc(scamper_addr_t *); 314 void scamper_tracelb_reply_free(scamper_tracelb_reply_t *); 315 316 /* 317 * basic scamper_tracelb_probe_t routines: 318 * 319 */ 320 scamper_tracelb_probe_t *scamper_tracelb_probe_alloc(void); 321 void scamper_tracelb_probe_free(scamper_tracelb_probe_t *); 322 int scamper_tracelb_probe_reply(scamper_tracelb_probe_t *probe, 323 scamper_tracelb_reply_t *reply); 324 int scamper_tracelb_probe_replies_alloc(scamper_tracelb_probe_t *, uint16_t); 325 326 /* 327 * basic scamper_tracelb_link_t routines: 328 * 329 * scamper_tracelb_link_alloc: allocate a scamper_tracelb_link_t structure 330 * scamper_tracelb_link_free: free a scamper_tracelb_link_t and contents 331 * scamper_tracelb_link_cmp: convenient function to compare links with 332 * scamper_tracelb_link_find: convenient function to find a link in a trace 333 * scamper_tracelb_link_add: add a link to a scamper_tracelb_t structure 334 */ 335 scamper_tracelb_link_t *scamper_tracelb_link_alloc(void); 336 scamper_tracelb_link_t *scamper_tracelb_link_find(const scamper_tracelb_t *, 337 scamper_tracelb_link_t *); 338 void scamper_tracelb_link_free(scamper_tracelb_link_t *); 339 int scamper_tracelb_link_cmp(const scamper_tracelb_link_t *, 340 const scamper_tracelb_link_t *); 341 int scamper_tracelb_link_add(scamper_tracelb_t *, scamper_tracelb_link_t *); 342 int scamper_tracelb_link_zerottlfwd(const scamper_tracelb_link_t *); 343 int scamper_tracelb_link_probeset(scamper_tracelb_link_t *, 344 scamper_tracelb_probeset_t *); 345 int scamper_tracelb_link_probesets_alloc(scamper_tracelb_link_t *, uint8_t); 346 347 /* 348 * basic scamper_tracelb_probeset_t routines: 349 * 350 */ 351 scamper_tracelb_probeset_t *scamper_tracelb_probeset_alloc(void); 352 void scamper_tracelb_probeset_free(scamper_tracelb_probeset_t *); 353 int scamper_tracelb_probeset_add(scamper_tracelb_probeset_t *, 354 scamper_tracelb_probe_t *); 355 int scamper_tracelb_probeset_probes_alloc(scamper_tracelb_probeset_t *, 356 uint16_t); 357 358 /* 359 * routines to summarise a set of probes beyond a specific node 360 * 361 */ 362 scamper_tracelb_probeset_summary_t * 363 scamper_tracelb_probeset_summary_alloc(scamper_tracelb_probeset_t *); 364 void 365 scamper_tracelb_probeset_summary_free(scamper_tracelb_probeset_summary_t *); 366 367 /* 368 * these functions allocate arrays of appropriate size, all elements 369 * initialised to null. 370 */ 371 int scamper_tracelb_nodes_alloc(scamper_tracelb_t *, uint16_t); 372 int scamper_tracelb_links_alloc(scamper_tracelb_t *, uint16_t); 373 374 /* 375 * scamper_tracelb_fwdpathc 376 * 377 * this function determines the number of unique forward paths, counted 378 * in IP-links, observed from each node in the trace structure. this 379 * data is useful to then pull out redundant sections in the path. 380 * returns zero on success. 381 */ 382 int scamper_tracelb_fwdpathc(const scamper_tracelb_t *trace, int *fwdpathc); 383 384 /* 385 * scamper_tracelb_node_convergencepoint 386 * 387 * this function determines the index (if any) into the trace at which 388 * the path converges to a single node. the caller should pass the array 389 * 390 * if the path does not reconverge, -1 is passed back in the to variable. 391 * returns zero on success, or -1 if an error occurs. 392 */ 393 int scamper_tracelb_node_convergencepoint(const scamper_tracelb_t *trace, 394 const int *fwdpathc, 395 int from, int *to); 396 397 /* 398 * scamper_tracelb_nodes_extract 399 * 400 * this function supplies all nodes between two points in the graph in the 401 * nodes parameter. the caller therefore should pass a nodes array with 402 * enough space to store trace->nodec items. 403 * this function returns the number of nodes extracted, or -1 in an 404 * error. 405 */ 406 int scamper_tracelb_nodes_extract(const scamper_tracelb_t *trace, 407 scamper_tracelb_node_t *from, 408 scamper_tracelb_node_t *to, 409 scamper_tracelb_node_t **nodes); 410 411 #endif /* __SCAMPER_TRACELB_H */ 412