hsep.c File Reference

---

Detailed Description

Horizon Size Estimation Protocol 0.2.

Protocol is defined here: http://www.menden.org/gnutella/hsep.html

Author:

Thomas Schuerger

Jeroen Asselman

Date:

2004

General API information:

• hsep_init() should be called once on startup of GtkG
• hsep_connection_init(node) should be called once for each newly established HSEP-capable connection
• hsep_connection_close(node) should be called when a HSEP-capable connection is closed
• hsep_timer() should be called frequently to send out HSEP messages to HSEP-capable nodes as required
• hsep_notify_shared(files, kibibytes) should be called whenever the number of shared files and/or kibibytes has changed
• hsep_process_msg(node) should be called whenever a HSEP message is received from a HSEP-capable node
• hsep_reset() can be used to reset all HSEP data (not for normal use)
• hsep_get_global_table(dest, triples) can be used to get the global HSEP table
• hsep_get_connection_table(conn, dest, triples) can be used to get a per-connection HSEP table
• hsep_add_global_table_listener(cb, freqtype, interval) can be used to add a listener that is informed whenever the global HSEP table changes.
• hsep_remove_global_table_listener(cb) can be used to remove an added listener for global HSEP table changes.
• hsep_has_global_table_changed(since) can be used to check if the global HSEP table has changed since the specified point in time.
• hsep_get_non_hsep_triple(tripledest) can be used to determine the reachable resources contributed by non-HSEP nodes (this is what direct neighbors that don't support HSEP tell us they're sharing).

Obtaining horizon size information on demand:

To obtain horizon size information, use the global HSEP table or the per-connection HSEP table, obtained using hsep_get_global_table(...) or hsep_get_connection_table (...), respectively (never access the internal arrays directly). To check if the global table has changed, use hsep_has_global_table_changed(...). The usable array indexes are between 1 (for 1 hop) and HSEP_N_MAX (for n_max hops). Note that the arrays only consider other nodes (i.e. exclude what we share ourselves), so the array index 0 always contains zeros. Note also that each triple represents the reachable resources *within* the number of hops, not at *exactly* the number of hops. To get the values for exactly the number of hops, simply subtract the preceeding triple from the desired triple.

Obtaining horizon size information using event-driven callbacks (only for the global HSEP table):

You can register a callback function for being informed whenever the global HSEP table changes by calling hsep_add_global_table_listener(...). On change of the global HSEP table the callback will be called with a pointer to a copy of the HSEP table and the number of provided triples. You must remove the listener later using hsep_remove_global_table_listener(...).

Note:

To support exchanging information about clients that don't support HSEP, these clients' library sizes (from PONG messages) are taken into account when HSEP messages are sent (that info is added to what we see in a distance of >= 1 hop).

#include "common.h"
#include "gmsg.h"
#include "routing.h"
#include "nodes.h"
#include "hsep.h"
#include "uploads.h"
#include "share.h"
#include "features.h"
#include "if/gnet_property.h"
#include "if/gnet_property_priv.h"
#include "lib/endian.h"
#include "lib/glib-missing.h"
#include "lib/tm.h"
#include "lib/walloc.h"
#include "lib/override.h"

Functions
	RCSID ("$Id:hsep.c, v 1.20 2005/09/10 08:17:28 daichik Exp $")
void	hsep_fire_global_table_changed (time_t now)
	Fires a change event for the global HSEP table.
gboolean	hsep_check_monotony (hsep_triple *table, unsigned int triples)
	Checks the monotony of the given triples.
void	hsep_sanity_check (void)
	Sanity check for the global and per-connection HSEP tables.
void	hsep_dump_table (void)
	Outputs the global HSEP table to the console.
unsigned int	hsep_triples_to_send (const hsep_triple *table, unsigned int triples)
	Takes a list of triples and returns the optimal number of triples to send in a HSEP message.
void	hsep_init (void)
	Initializes HSEP.
void	hsep_add_global_table_listener (GCallback cb, frequency_t t, guint32 interval)
	Adds the specified listener to the list of subscribers for global HSEP table change events.
void	hsep_remove_global_table_listener (GCallback cb)
void	hsep_reset (void)
	Resets all HSEP data.
void	hsep_connection_init (struct gnutella_node *n)
	Initializes the connection's HSEP data.
void	hsep_timer (time_t now)
	Sends a HSEP message to all nodes where the last message has been sent some time ago.
void	hsep_connection_close (struct gnutella_node *n)
	Updates the global HSEP table when a connection is about to be closed.
void	hsep_process_msg (struct gnutella_node *n, time_t now)
	Processes a received HSEP message by updating the connection's and the global HSEP table.
void	hsep_send_msg (struct gnutella_node *n, time_t now)
	Sends a HSEP message to the given node, but only if data to send has changed.
void	hsep_notify_shared (guint64 own_files, guint64 own_kibibytes)
	This should be called whenever the number of shared files or kibibytes change.
unsigned int	hsep_get_global_table (hsep_triple *buffer, unsigned int maxtriples)
	Copies the first maxtriples triples from the global HSEP table into the specified buffer.
unsigned int	hsep_get_connection_table (const struct gnutella_node *n, hsep_triple *buffer, unsigned int maxtriples)
	Copies the first maxtriples triples from the connection's HSEP table into the specified buffer.
void	hsep_close (void)
	Used to shutdown HSEP.
gboolean	hsep_has_global_table_changed (time_t since)
	Checks whether the global HSEP table has changed since the specified point in time.
void	hsep_get_non_hsep_triple (hsep_triple *tripledest)
	Gets a HSEP-compatible triple for all non-HSEP nodes.
const gchar *	hsep_get_static_str (gint row, gint column)
gint	hsep_get_table_size (void)
Variables
hsep_triple	hsep_global_table [HSEP_N_MAX+1]
	global HSEP table
hsep_triple	hsep_own = {1, 0, 0}
event_t *	hsep_global_table_changed_event
time_t	hsep_last_global_table_change = 0

---

Function Documentation

void hsep_add_global_table_listener (  GCallback  cb, frequency_t  t, guint32  interval )

Adds the specified listener to the list of subscribers for global HSEP table change events. The specified callback is called once immediately, independent of the given frequency type and time interval. This function must be called after hsep_init() has been called.

gboolean hsep_check_monotony (  hsep_triple *  table, unsigned int  triples )  [static]

Checks the monotony of the given triples. TRUE is returned if 0 or 1 triple is given. Returns TRUE if monotony is ok, FALSE otherwise.

void hsep_close (  void   )

Used to shutdown HSEP.

void hsep_connection_close (  struct gnutella_node *  n  )

Updates the global HSEP table when a connection is about to be closed. The connection's HSEP data is restored to zero and the CAN_HSEP attribute is cleared.

void hsep_connection_init (  struct gnutella_node *  n  )

Initializes the connection's HSEP data.

void hsep_dump_table (  void   )  [static]

Outputs the global HSEP table to the console.

void hsep_fire_global_table_changed (  time_t  now  )  [static]

Fires a change event for the global HSEP table.

unsigned int hsep_get_connection_table (  const struct gnutella_node *  n, hsep_triple *  buffer, unsigned int  maxtriples )

Copies the first maxtriples triples from the connection's HSEP table into the specified buffer. If maxtriples is larger than the number of triples in the table, it is truncated appropriately. Note that also the 0'th triple is copied, which is always zero. Returns: The number of copied triples.

unsigned int hsep_get_global_table (  hsep_triple *  buffer, unsigned int  maxtriples )

Copies the first maxtriples triples from the global HSEP table into the specified buffer. If maxtriples is larger than the number of triples in the table, it is truncated appropriately. Note that also the 0'th triple is copied, which is always zero. Returns: The number of copied triples.

void hsep_get_non_hsep_triple (  hsep_triple *  tripledest  )

Gets a HSEP-compatible triple for all non-HSEP nodes. The number of nodes is just the number of established non-HSEP connections, the number of shared files and KiB is the sum of the known PONG-based library sizes of those connections. Note that this takes only direct neighbor connections into account. Also note that the shared library size in KiB is not accurate due to Gnutella protocol limitations. The determined values are stored in the provided triple address.

const gchar* hsep_get_static_str (  gint  row, gint  column )

Returns: a static string of the cell contents of the given row and column. Attention: NB: The static buffers for each column are disjunct.

gint hsep_get_table_size (  void   )

Returns: the size of the global hsep table

gboolean hsep_has_global_table_changed (  time_t  since  )

Checks whether the global HSEP table has changed since the specified point in time. Returns TRUE if this is the case, FALSE otherwise.

void hsep_init (  void   )

Initializes HSEP.

void hsep_notify_shared (  guint64  own_files, guint64  own_kibibytes )

This should be called whenever the number of shared files or kibibytes change. The values are checked for changes, nothing is done if nothing has changed. Note that kibibytes are determined by shifting the number of bytes right by 10 bits, not by dividing by 1000.

void hsep_process_msg (  struct gnutella_node *  n, time_t  now )

Processes a received HSEP message by updating the connection's and the global HSEP table.

void hsep_remove_global_table_listener (  GCallback  cb  )

void hsep_reset (  void   )

Resets all HSEP data. The global HSEP table and all connections' HSEP tables are reset to zero. The number of own shared files and kibibytes is untouched. This can be used to watch how quickly the HSEP data converges back to the correct "static" state. As soon as we have received a HSEP message from each of our peers, this state should be reached. Use with care, because this reset will temporarily affect all HSEP-capable nodes in the radius of N_MAX hops!

void hsep_sanity_check (  void   )  [static]

Sanity check for the global and per-connection HSEP tables. Assertions are made for all these checks. If HSEP is implemented and used correctly, the sanity check will succed. Performed checks (* stands for an arbitrary value): own triple must be (1, *, *) global triple for 0 hops must be (0, 0, 0) per-connection triple for 0 hops must be (0, 0, 0) per-connection triple for 1 hops must be (1, *, *) per-connection triples must be monotonically increasing the sum of the n'th triple of each connection must match the n'th global table triple for all n

void hsep_send_msg (  struct gnutella_node *  n, time_t  now )

Sends a HSEP message to the given node, but only if data to send has changed. Should be called about every 30-60 seconds per node. Will automatically be called by hsep_timer() and hsep_connection_init(). Node must be HSEP-capable.

void hsep_timer (  time_t  now  )

Sends a HSEP message to all nodes where the last message has been sent some time ago. This should be called frequently (e.g. every second or every few seconds).

unsigned int hsep_triples_to_send (  const hsep_triple *  table, unsigned int  triples )  [static]

Takes a list of triples and returns the optimal number of triples to send in a HSEP message. The number of triples to send is n_opt, defined as (triple indices counted from 0): n_opt := 1 + min {n | triple[n] = triple[k] for all k in [n+1,triples-1]} If there is no such n_opt, n_opt := triples. If all triples are equal, 1 is returned, which is correct. Note: This algorithm works regardless of the byte order of the triple data, because only equality tests are used.

RCSID (  "$Id:hsep.  c, v 1.20 2005/09/10 08:17:28 daichik Exp $"  )

---

Variable Documentation

hsep_triple hsep_global_table[HSEP_N_MAX + 1] [static]

global HSEP table

event_t* hsep_global_table_changed_event [static]

time_t hsep_last_global_table_change = 0 [static]

hsep_triple hsep_own = {1, 0, 0} [static]

---