2 This file is part of GNUnet.
3 (C) 2010,2011 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @brief automatic transport selection API
23 * @author Christian Grothoff
24 * @author Matthias Wachs
28 * - extend API to get performance data
29 * - implement simplistic strategy based on say 'lowest latency' or strict ordering
30 * - extend API to get peer preferences, implement proportional bandwidth assignment
31 * - re-implement API against a real ATS service (!)
34 #include "gnunet_ats_service.h"
37 #define DEBUG_ATS GNUNET_EXTRA_LOGGING
39 #define LOG(kind,...) GNUNET_log_from (kind, "ats-api", __VA_ARGS__)
42 * Receive and send buffer windows grow over time. For
43 * how long can 'unused' bandwidth accumulate before we
44 * need to cap it? (specified in seconds).
46 #define MAX_WINDOW_TIME_S (5 * 60)
48 // NOTE: this implementation is simply supposed
49 // to implement a simplistic strategy in-process;
50 // in the future, we plan to replace it with a real
51 // service implementation
55 * Opaque handle to obtain address suggestions.
57 struct GNUNET_ATS_SuggestionContext
61 * Function to call with our final suggestion.
63 GNUNET_ATS_AddressSuggestionCallback cb;
73 struct GNUNET_ATS_SchedulingHandle *atc;
76 * Which peer are we monitoring?
78 struct GNUNET_PeerIdentity target;
84 * Count number of connected records.
86 * @param cls pointer to counter
87 * @param key identity of the peer associated with the records
88 * @param value a 'struct AllocationRecord'
89 * @return GNUNET_YES (continue iteration)
92 count_connections (void *cls, const GNUNET_HashCode * key, void *value)
94 unsigned int *ac = cls;
95 struct AllocationRecord *ar = value;
97 if (GNUNET_YES == ar->connected)
104 * Closure for 'set_bw_connections'.
106 struct SetBandwidthContext
111 struct GNUNET_ATS_SchedulingHandle *atc;
114 * Inbound bandwidth to assign.
116 struct GNUNET_BANDWIDTH_Value32NBO bw_in;
119 * Outbound bandwidth to assign.
121 struct GNUNET_BANDWIDTH_Value32NBO bw_out;
126 * Set bandwidth based on record.
128 * @param cls 'struct SetBandwidthContext'
129 * @param key identity of the peer associated with the records
130 * @param value a 'struct AllocationRecord'
131 * @return GNUNET_YES (continue iteration)
134 set_bw_connections (void *cls, const GNUNET_HashCode * key, void *value)
136 struct SetBandwidthContext *sbc = cls;
137 struct AllocationRecord *ar = value;
139 GNUNET_assert (GNUNET_SYSERR != ar->connected);
140 /* FIXME: ||1 because we currently NEVER get 'connected' events... */
141 if ( (GNUNET_YES == ar->connected) || 1)
143 ar->bandwidth_in = sbc->bw_in;
144 ar->bandwidth_out = sbc->bw_out;
145 GNUNET_BANDWIDTH_tracker_update_quota (&ar->available_recv_window,
147 LOG (GNUNET_ERROR_TYPE_DEBUG,
148 "Bandwidth assigned to peer %s is i:%u/o:%u bytes/s\n",
149 GNUNET_i2s ((const struct GNUNET_PeerIdentity *) key),
150 ntohl (ar->bandwidth_in.value__),
151 ntohl (ar->bandwidth_out.value__));
152 if (NULL != sbc->atc->alloc_cb)
153 sbc->atc->alloc_cb (sbc->atc->alloc_cb_cls,
154 (const struct GNUNET_PeerIdentity *) key,
155 ar->plugin_name, ar->plugin_addr,
162 else if (ntohl (ar->bandwidth_out.value__) > 0)
164 ar->bandwidth_in = GNUNET_BANDWIDTH_value_init (0);
165 ar->bandwidth_out = GNUNET_BANDWIDTH_value_init (0);
166 if (NULL != sbc->atc->alloc_cb)
167 sbc->atc->alloc_cb (sbc->atc->alloc_cb_cls,
168 (const struct GNUNET_PeerIdentity *) key,
169 ar->plugin_name, ar->plugin_addr,
170 ar->plugin_addr_len, ar->session, ar->bandwidth_out,
171 ar->bandwidth_in, NULL, 0);
174 LOG (GNUNET_ERROR_TYPE_DEBUG,
175 "Not communicating bandwidth assigned to peer %s: not connected and bw is: i:%u/o:%u bytes/s\n",
176 GNUNET_i2s ((const struct GNUNET_PeerIdentity *) key),
177 ntohl (ar->bandwidth_in.value__),
178 ntohl (ar->bandwidth_out.value__));
185 * Task run to update bandwidth assignments.
187 * @param cls the 'struct GNUNET_ATS_SchedulingHandle'
188 * @param tc scheduler context
191 update_bandwidth_task (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
193 struct GNUNET_ATS_SchedulingHandle *atc = cls;
195 struct SetBandwidthContext bwc;
197 atc->ba_task = GNUNET_SCHEDULER_NO_TASK;
198 /* FIXME: update calculations NICELY; what follows is a naive version */
199 GNUNET_CONTAINER_multihashmap_iterate (atc->peers, &count_connections, &ac);
203 GNUNET_assert (ac > 0);
204 bwc.bw_in = GNUNET_BANDWIDTH_value_init (atc->total_bps_in / ac);
205 bwc.bw_out = GNUNET_BANDWIDTH_value_init (atc->total_bps_out / ac);
206 LOG (GNUNET_ERROR_TYPE_DEBUG,
207 "Trivial implementation: bandwidth assigned to each peer is i:%u/o:%u bytes/s\n",
208 ntohl (bwc.bw_in.value__),
209 ntohl (bwc.bw_out.value__));
210 GNUNET_CONTAINER_multihashmap_iterate (atc->peers, &set_bw_connections, &bwc);
215 * Calculate an updated bandwidth assignment and notify.
218 * @param change which allocation record changed?
221 update_bandwidth_assignment (struct GNUNET_ATS_SchedulingHandle *atc,
222 struct AllocationRecord *change)
224 /* FIXME: based on the 'change', update the LP-problem... */
225 if (atc->ba_task == GNUNET_SCHEDULER_NO_TASK)
226 atc->ba_task = GNUNET_SCHEDULER_add_now (&update_bandwidth_task, atc);
231 * Function called with feasbile addresses we might want to suggest.
233 * @param cls the 'struct GNUNET_ATS_SuggestionContext'
234 * @param key identity of the peer
235 * @param value a 'struct AllocationRecord' for the peer
236 * @return GNUNET_NO if we're done, GNUNET_YES if we did not suggest an address yet
239 suggest_address (void *cls, const GNUNET_HashCode * key, void *value)
241 struct GNUNET_ATS_SuggestionContext *asc = cls;
242 struct AllocationRecord *ar = value;
245 LOG (GNUNET_ERROR_TYPE_DEBUG,
246 "Suggesting address for peer `%s', starting with i:%u/o:%u bytes/s\n",
248 asc->atc->total_bps_in/32,
249 asc->atc->total_bps_out/32);
252 /* trivial strategy: pick first available address... */
253 asc->cb (asc->cb_cls, &asc->target, ar->plugin_name, ar->plugin_addr,
254 ar->plugin_addr_len, ar->session,
255 GNUNET_BANDWIDTH_value_init (asc->atc->total_bps_out / 32),
256 GNUNET_BANDWIDTH_value_init (asc->atc->total_bps_in / 32), ar->ats,
264 map_it (void *cls, const GNUNET_HashCode * key, void *value)
266 LOG (GNUNET_ERROR_TYPE_DEBUG, "Found entry for %s\n", GNUNET_h2s (key));
271 * We would like to establish a new connection with a peer.
272 * ATS should suggest a good address to begin with.
275 * @param peer identity of the new peer
276 * @param cb function to call with the address
277 * @param cb_cls closure for cb
279 struct GNUNET_ATS_SuggestionContext *
280 GNUNET_ATS_suggest_address (struct GNUNET_ATS_SchedulingHandle *atc,
281 const struct GNUNET_PeerIdentity *peer,
282 GNUNET_ATS_AddressSuggestionCallback cb,
285 struct GNUNET_ATS_SuggestionContext *asc;
288 LOG (GNUNET_ERROR_TYPE_DEBUG,
289 "Looking up suggested address for peer `%s'\n", GNUNET_i2s (peer));
291 asc = GNUNET_malloc (sizeof (struct GNUNET_ATS_SuggestionContext));
293 asc->cb_cls = cb_cls;
296 (void) GNUNET_CONTAINER_multihashmap_get_multiple (atc->peers,
298 &suggest_address, asc);
305 GNUNET_CONTAINER_multihashmap_put (atc->notify_map, &peer->hashPubKey, asc,
306 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
312 * Cancel suggestion request.
314 * @param asc handle of the request to cancel
317 GNUNET_ATS_suggest_address_cancel (struct GNUNET_ATS_SuggestionContext *asc)
319 GNUNET_assert (GNUNET_OK ==
320 GNUNET_CONTAINER_multihashmap_remove (asc->atc->notify_map,
321 &asc->target.hashPubKey,
328 * Initialize the ATS subsystem.
330 * @param cfg configuration to use
331 * @param alloc_cb notification to call whenever the allocation changed
332 * @param alloc_cb_cls closure for 'alloc_cb'
333 * @return ats context
335 struct GNUNET_ATS_SchedulingHandle *
336 GNUNET_ATS_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
337 GNUNET_ATS_AddressSuggestionCallback alloc_cb,
340 struct GNUNET_ATS_SchedulingHandle *atc;
343 LOG (GNUNET_ERROR_TYPE_DEBUG, "ATS init\n");
345 atc = GNUNET_malloc (sizeof (struct GNUNET_ATS_SchedulingHandle));
347 atc->alloc_cb = alloc_cb;
348 atc->alloc_cb_cls = alloc_cb_cls;
349 atc->peers = GNUNET_CONTAINER_multihashmap_create (256);
350 atc->notify_map = GNUNET_CONTAINER_multihashmap_create (256);
351 GNUNET_CONFIGURATION_get_value_number (cfg, "core", "TOTAL_QUOTA_OUT",
352 &atc->total_bps_out);
353 GNUNET_CONFIGURATION_get_value_number (cfg, "core", "TOTAL_QUOTA_IN",
360 * Free an allocation record.
363 * @param key identity of the peer associated with the record
364 * @param value the 'struct AllocationRecord' to free
365 * @return GNUNET_OK (continue to iterate)
368 destroy_allocation_record (void *cls, const GNUNET_HashCode * key, void *value)
370 struct AllocationRecord *ar = value;
372 GNUNET_array_grow (ar->ats, ar->ats_count, 0);
373 GNUNET_free (ar->plugin_name);
380 * Shutdown the ATS subsystem.
385 GNUNET_ATS_shutdown (struct GNUNET_ATS_SchedulingHandle *atc)
388 LOG (GNUNET_ERROR_TYPE_DEBUG, "ATS shutdown\n");
390 if (GNUNET_SCHEDULER_NO_TASK != atc->ba_task)
392 GNUNET_SCHEDULER_cancel (atc->ba_task);
393 atc->ba_task = GNUNET_SCHEDULER_NO_TASK;
395 GNUNET_CONTAINER_multihashmap_iterate (atc->peers, &destroy_allocation_record,
397 GNUNET_CONTAINER_multihashmap_destroy (atc->peers);
398 GNUNET_assert (GNUNET_CONTAINER_multihashmap_size (atc->notify_map) == 0);
399 GNUNET_CONTAINER_multihashmap_destroy (atc->notify_map);
400 atc->notify_map = NULL;
406 * Closure for 'update_session'
408 struct UpdateSessionContext
413 struct GNUNET_ATS_SchedulingHandle *atc;
416 * Allocation record with new information.
418 struct AllocationRecord *arnew;
423 * Update an allocation record, merging with the new information
425 * @param cls a new 'struct AllocationRecord'
426 * @param key identity of the peer associated with the records
427 * @param value the old 'struct AllocationRecord'
428 * @return GNUNET_YES if the records do not match,
429 * GNUNET_NO if the record do match and 'old' was updated
432 update_session (void *cls, const GNUNET_HashCode * key, void *value)
434 struct UpdateSessionContext *usc = cls;
435 struct AllocationRecord *arnew = usc->arnew;
436 struct AllocationRecord *arold = value;
442 if (0 != strcmp (arnew->plugin_name, arold->plugin_name))
444 if (! (((arnew->session == arold->session) && (arnew->session != NULL)) ||
445 ((arold->session == NULL) &&
446 (arold->plugin_addr_len == arnew->plugin_addr_len) &&
448 memcmp (arold->plugin_addr, arnew->plugin_addr,
449 arnew->plugin_addr_len)))))
450 return GNUNET_YES; /* no match */
453 LOG (GNUNET_ERROR_TYPE_DEBUG,
454 "Updating session for peer `%s' plugin `%s'\n", GNUNET_h2s (key),
457 if (arnew->session != arold->session)
459 arold->session = arnew->session;
461 if ((arnew->connected == GNUNET_YES) && (arold->connected == GNUNET_NO))
463 arold->connected = GNUNET_YES;
466 /* Update existing value */
468 while (c_new < arnew->ats_count)
472 while (c_old < arold->ats_count)
474 if (arold->ats[c_old].type == arnew->ats[c_new].type)
477 LOG (GNUNET_ERROR_TYPE_DEBUG,
478 "Found type %i, old value=%i new value=%i\n",
479 ntohl (arold->ats[c_old].type), ntohl (arold->ats[c_old].value),
480 ntohl (arnew->ats[c_new].value));
482 arold->ats[c_old].value = arnew->ats[c_new].value;
488 if (found == GNUNET_NO)
491 LOG (GNUNET_ERROR_TYPE_DEBUG, "Added new type %i new value=%i\n",
492 ntohl (arnew->ats[c_new].type), ntohl (arnew->ats[c_new].value));
493 LOG (GNUNET_ERROR_TYPE_DEBUG, "Old array size: %u\n", arold->ats_count);
495 GNUNET_array_grow (arold->ats, arold->ats_count, arold->ats_count + 1);
496 GNUNET_assert (arold->ats_count >= 2);
497 arold->ats[arold->ats_count - 2].type = arnew->ats[c_new].type;
498 arold->ats[arold->ats_count - 2].value = arnew->ats[c_new].value;
499 arold->ats[arold->ats_count - 1].type = htonl (0);
500 arold->ats[arold->ats_count - 1].value = htonl (0);
502 LOG (GNUNET_ERROR_TYPE_DEBUG, "New array size: %i\n", arold->ats_count);
508 update_bandwidth_assignment (usc->atc, arold);
514 * Create an allocation record with the given properties.
516 * @param plugin_name name of the currently used transport plugin
517 * @param session session in use (if available)
518 * @param plugin_addr address in use (if available)
519 * @param plugin_addr_len number of bytes in plugin_addr
520 * @param ats performance data for the connection
521 * @param ats_count number of performance records in 'ats'
523 static struct AllocationRecord *
524 create_allocation_record (const char *plugin_name, struct Session *session,
525 const void *plugin_addr, size_t plugin_addr_len,
526 const struct GNUNET_ATS_Information *ats,
529 struct AllocationRecord *ar;
531 ar = GNUNET_malloc (sizeof (struct AllocationRecord) + plugin_addr_len);
532 ar->plugin_name = GNUNET_strdup (plugin_name);
533 ar->plugin_addr = &ar[1];
534 memcpy (&ar[1], plugin_addr, plugin_addr_len);
535 ar->session = session;
536 ar->plugin_addr_len = plugin_addr_len;
537 GNUNET_BANDWIDTH_tracker_init (&ar->available_recv_window, ar->bandwidth_in,
539 GNUNET_assert (ats_count > 0);
540 GNUNET_array_grow (ar->ats, ar->ats_count, ats_count);
541 memcpy (ar->ats, ats,
542 ats_count * sizeof (struct GNUNET_ATS_Information));
543 ar->connected = GNUNET_SYSERR; /* aka: not known / no change */
549 * Mark all matching allocation records as not connected.
551 * @param cls 'struct GTS_AtsHandle'
552 * @param key identity of the peer associated with the record
553 * @param value the 'struct AllocationRecord' to clear the 'connected' flag
554 * @return GNUNET_OK (continue to iterate)
557 disconnect_peer (void *cls, const GNUNET_HashCode * key, void *value)
559 struct GNUNET_ATS_SchedulingHandle *atc = cls;
560 struct AllocationRecord *ar = value;
562 if (GNUNET_YES == ar->connected)
564 ar->connected = GNUNET_NO;
565 update_bandwidth_assignment (atc, ar);
572 * We established a new connection with a peer (for example, because
573 * core asked for it or because the other peer connected to us).
574 * Calculate bandwidth assignments including the new peer.
577 * @param peer identity of the new peer
578 * @param plugin_name name of the currently used transport plugin
579 * @param session session in use (if available)
580 * @param plugin_addr address in use (if available)
581 * @param plugin_addr_len number of bytes in plugin_addr
582 * @param ats performance data for the connection
583 * @param ats_count number of performance records in 'ats'
586 GNUNET_ATS_peer_connect (struct GNUNET_ATS_SchedulingHandle *atc,
587 const struct GNUNET_PeerIdentity *peer,
588 const char *plugin_name, struct Session *session,
589 const void *plugin_addr, size_t plugin_addr_len,
590 const struct GNUNET_ATS_Information *ats,
593 struct AllocationRecord *ar;
594 struct UpdateSessionContext usc;
597 LOG (GNUNET_ERROR_TYPE_DEBUG,
598 "Connected to peer %s\n",
602 (void) GNUNET_CONTAINER_multihashmap_iterate (atc->peers, &disconnect_peer,
604 ar = create_allocation_record (plugin_name, session, plugin_addr,
605 plugin_addr_len, ats, ats_count);
606 ar->connected = GNUNET_YES;
610 GNUNET_CONTAINER_multihashmap_iterate (atc->peers, &update_session, &usc))
612 destroy_allocation_record (NULL, &peer->hashPubKey, ar);
615 GNUNET_assert (GNUNET_OK ==
616 GNUNET_CONTAINER_multihashmap_put (atc->peers,
617 &peer->hashPubKey, ar,
618 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
623 * We disconnected from the given peer (for example, because ats, core
624 * or blacklist asked for it or because the other peer disconnected).
625 * Calculate bandwidth assignments without the peer.
628 * @param peer identity of the new peer
631 GNUNET_ATS_peer_disconnect (struct GNUNET_ATS_SchedulingHandle *atc,
632 const struct GNUNET_PeerIdentity *peer)
635 LOG (GNUNET_ERROR_TYPE_DEBUG,
636 "Disconnected from peer %s\n",
639 (void) GNUNET_CONTAINER_multihashmap_get_multiple (atc->peers,
641 &disconnect_peer, atc);
646 * Closure for 'destroy_allocation_record'
648 struct SessionDestroyContext
653 struct GNUNET_ATS_SchedulingHandle *atc;
656 * Session being destroyed.
658 const struct Session *session;
663 * Free an allocation record matching the given session.
665 * @param cls the 'struct SessionDestroyContext'
666 * @param key identity of the peer associated with the record
667 * @param value the 'struct AllocationRecord' to free
668 * @return GNUNET_OK (continue to iterate)
671 destroy_session (void *cls, const GNUNET_HashCode * key, void *value)
673 struct SessionDestroyContext *sdc = cls;
674 struct AllocationRecord *ar = value;
676 if (ar->session != sdc->session)
679 if (ar->plugin_addr != NULL)
681 GNUNET_assert (GNUNET_OK ==
682 GNUNET_CONTAINER_multihashmap_remove (sdc->atc->peers, key,
684 if (GNUNET_YES == ar->connected) ;
686 /* FIXME: is this supposed to be allowed? What to do then? */
689 destroy_allocation_record (NULL, key, ar);
695 * A session got destroyed, stop including it as a valid address.
698 * @param peer identity of the peer
699 * @param session session handle that is no longer valid
702 GNUNET_ATS_session_destroyed (struct GNUNET_ATS_SchedulingHandle *atc,
703 const struct GNUNET_PeerIdentity *peer,
704 const struct Session *session)
706 struct SessionDestroyContext sdc;
709 sdc.session = session;
710 (void) GNUNET_CONTAINER_multihashmap_iterate (atc->peers, &destroy_session,
716 * Notify validation watcher that an entry is now valid
718 * @param cls 'struct ValidationEntry' that is now valid
719 * @param key peer identity (unused)
720 * @param value a 'GST_ValidationIteratorContext' to notify
721 * @return GNUNET_YES (continue to iterate)
724 notify_valid (void *cls, const GNUNET_HashCode * key, void *value)
726 struct AllocationRecord *ar = cls;
727 struct GNUNET_ATS_SuggestionContext *asc = value;
729 asc->cb (asc->cb_cls, &asc->target, ar->plugin_name, ar->plugin_addr,
730 ar->plugin_addr_len, ar->session,
731 GNUNET_BANDWIDTH_value_init (asc->atc->total_bps_out / 32),
732 GNUNET_BANDWIDTH_value_init (asc->atc->total_bps_in / 32), ar->ats,
734 GNUNET_ATS_suggest_address_cancel (asc);
741 * We have updated performance statistics for a given address. Note
742 * that this function can be called for addresses that are currently
743 * in use as well as addresses that are valid but not actively in use.
744 * Furthermore, the peer may not even be connected to us right now (in
745 * which case the call may be ignored or the information may be stored
746 * for later use). Update bandwidth assignments.
749 * @param peer identity of the peer
750 * @param valid_until how long is the address valid?
751 * @param plugin_name name of the transport plugin
752 * @param session session handle (if available)
753 * @param plugin_addr address (if available)
754 * @param plugin_addr_len number of bytes in plugin_addr
755 * @param ats performance data for the address
756 * @param ats_count number of performance records in 'ats'
759 GNUNET_ATS_address_update (struct GNUNET_ATS_SchedulingHandle *atc,
760 const struct GNUNET_PeerIdentity *peer,
761 struct GNUNET_TIME_Absolute valid_until,
762 const char *plugin_name, struct Session *session,
763 const void *plugin_addr, size_t plugin_addr_len,
764 const struct GNUNET_ATS_Information *ats,
767 struct AllocationRecord *ar;
768 struct UpdateSessionContext usc;
771 LOG (GNUNET_ERROR_TYPE_DEBUG,
772 "Updating address for peer `%s', plugin `%s'\n", GNUNET_i2s (peer),
775 ar = create_allocation_record (plugin_name, session, plugin_addr,
776 plugin_addr_len, ats, ats_count);
780 GNUNET_CONTAINER_multihashmap_iterate (atc->peers, &update_session, &usc))
782 destroy_allocation_record (NULL, &peer->hashPubKey, ar);
786 LOG (GNUNET_ERROR_TYPE_DEBUG,
787 "Adding new address for peer `%s', plugin `%s'\n", GNUNET_i2s (peer),
790 ar->connected = GNUNET_NO;
791 GNUNET_assert (GNUNET_OK ==
792 GNUNET_CONTAINER_multihashmap_put (atc->peers,
793 &peer->hashPubKey, ar,
794 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
795 GNUNET_CONTAINER_multihashmap_get_multiple (atc->notify_map,
796 &peer->hashPubKey, ¬ify_valid,
800 /* end of file gnunet-service-transport_ats.c */