src/probe-stats/wifi_stats.hxx

/*
 * WiPal - A library and a set of tools to manipulate wireless traces.
 * Copyright (C) 2007, 2008, 2009  Universite Pierre et Marie Curie - Paris 6
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 * MA  02110-1301  USA
 *
 * Author: Thomas Claveirole <thomas.claveirole@lip6.fr>
 */
#ifndef WIFI_STATS_HXX_
# define WIFI_STATS_HXX_

# include <cmath>
# include <iostream>

# include <wipal/wifi/frame.hh>

# include "wifi_stats.hh"

namespace stats
{

  /*-------------.
  | distribution |
  `-------------*/

  inline
  distribution::distribution(float min, float max, float gran):
    min_ (min),
    max_ (max),
    gran_ (gran),
    dist_ (2 + size_t (std::ceil((max - min) / gran))),
    total_ (0)
  {
  }

  inline
  void
  distribution::insert(float p)
  {
    size_t      i;

    if (p < min_)
      i = 0;
    else if (p > max_)
      i = dist_.size() - 1;
    else
      i = 1 + size_t ((p - min_) / gran_);

    ++dist_[i];
    ++total_;
  }

  inline
  std::ostream&
  operator << (std::ostream& os, const distribution& d)
  {
    return d.dump(os);
  }

  /*-------------.
    | timed_events |
    `-------------*/

  inline
  boost::posix_time::time_duration
  timed_events::insert(const ptime& ev)
  {
    const size_t        old_size = evs_.size();

    evs_.push_back(ev);
    return
      old_size ? ev - evs_[old_size - 1]: boost::posix_time::not_a_date_time;
  }

  inline
  const std::vector<boost::posix_time::ptime>&
  timed_events::evs() const
  {
    return evs_;
  }

  template <class C>
  std::vector<boost::posix_time::time_duration>
  its(const C& evs)
  {
    using boost::posix_time::time_duration;

    typedef typename C::const_iterator  const_iterator;

    std::vector<time_duration>  r;

    const_iterator      curr = evs.begin();
    for (const_iterator prev = curr++; curr != evs.end(); prev = curr++)
      r.push_back(*curr - *prev);

    return r;
  }

  template <class C>
  boost::posix_time::time_duration
  mean(const C& its)
  {
    boost::posix_time::time_duration    m (0, 0, 0, 0);

    for (typename C::const_iterator i = its.begin(); i != its.end(); ++i)
      m += *i;
    return m / its.size();
  }

  template <class C>
  boost::posix_time::time_duration
  stddev(const C& its, const boost::posix_time::time_duration* mean_)
  {
    using boost::posix_time::time_duration;
    using boost::posix_time::microseconds;

    time_duration       m = mean_ ? *mean_ : mean(its);
    double              d = 0;

    for (typename C::const_iterator i = its.begin(); i != its.end(); ++i)
      d += std::pow(double ((*i - m).total_microseconds()), 2);
    return microseconds (unsigned (std::sqrt(d / its.size())));
  }

  template <class C>
  boost::posix_time::time_duration
  median(const C& its)
  {
    using boost::posix_time::time_duration;

    const size_t                        s = its.size();
    const size_t                        m = s / 2;
    std::vector<time_duration>  r (m + 1);

    std::partial_sort_copy(its.begin(), its.end(), r.begin(), r.end());
    return s % 2 ? r[m] : (r[m - 1] + r[m]) / 2;
  }

  template <class C>
  distribution
  make_distribution(float min, float max, float gran, const C& its)
  {
    distribution        r (min, max, gran);

    for (typename C::const_iterator it = its.begin(); it != its.end(); ++it)
      r.insert(it->total_microseconds());

    return r;
  }

  /*-----------.
  | addr_state |
  `-----------*/

  inline
  addr_state::addr_state():
    pr_answers (),
    last_presp (0),
    heard_as_tmiter (0),
    mentioned_as_ap (0)
  {
    for (unsigned i = 0; i < sizeof (pr_stats) / sizeof (*pr_stats); ++i)
      pr_stats[i] = timed_events ();
  }

  inline
  addr_state::presp_attr::presp_attr():
    arrival (),
    ack_expected_arrival (),
    ack_arrival (),
    retries (0),
    acks (0)
  {
  }

  /*---------------.
  | probe_requests |
  `---------------*/

  inline
  probe_requests::probe_requests(addr_state_map& m):
    count (0),
    addrs (&m),
    it_dist (min, max, gran)
  {
  }

  inline
  void
  probe_requests::update(const wpl::wifi::mgt::header   *frame,
                         const ptime&                   toa)
  {
    using boost::posix_time::time_duration;
    using wpl::wifi::mgt::header;

    addr_state_map&     m = *addrs;

    count++;
    m[frame->addrs[header::da]].pr_stats[header::da].insert(toa);
    m[frame->addrs[header::bssid]].pr_stats[header::bssid].insert(toa);

    addr_state& s = m[frame->addrs[header::sa]];

    const time_duration d = s.pr_stats[header::sa].insert(toa);
    if (not d.is_not_a_date_time())
      it_dist.insert(d.total_microseconds());

    s.pr_answers.push_back(addr_state::preq_answer_set ());
  }

  /*-------.
  | frames |
  `-------*/

  inline
  frames::frames():
    frame_count (0),
    total_len (0),
    total_caplen (0),
    phy_error_count (0),
    pr (addrs),
    first (),
    last ()
  {
  }

  inline
  void
  frames::update(const wpl::pkt::metadata& h, const void* f)
  {
    using boost::posix_time::microseconds;

    const ptime                 toa = update_counters(h);
    const wpl::wifi::addr       *ta = wpl::wifi::transmitter_address(f);
    const wpl::wifi::addr       *ba = wpl::wifi::bssid_address(f);

    if (ta)
      ++addrs[*ta].heard_as_tmiter;
    if (ba and *ba != wpl::wifi::addr::broadcast())
      ++addrs[*ba].mentioned_as_ap;

    const wpl::wifi::type::frame_type   ty = wpl::wifi::type_of(f);
    const unsigned                      subty = wpl::wifi::subtype_of(f);

    switch (ty)
      {
      case wpl::wifi::type::management:
        {
          namespace mgt         = wpl::wifi::mgt;
          namespace subtype     = mgt::subtype;

          const mgt::header* mh = reinterpret_cast<const mgt::header*> (f);

          switch (subty)
            {
            case subtype::probe_req:
//            std::cerr << toa << " PReq " << mh->addrs[mgt::header::sa]
//                      << '\n';

              pr.update(mh, toa);
              break;
            case subtype::probe_resp:
              {
                typedef addr_state::pr_answers_t        pr_answers_t;

                const wpl::wifi::addr&  sa = mh->addrs[mgt::header::sa];
                const wpl::wifi::addr&  da = mh->addrs[mgt::header::da];
                pr_answers_t&           pr_answers = addrs[da].pr_answers;

//              std::cerr << toa << " PResp " << sa << " -> " << da << '\n';

                if (not pr_answers.empty())
                  {
                    typedef addr_state::presp_attr                presp_attr;
                    typedef addr_state::preq_answer_set::iterator iterator;
                    typedef
                      addr_state::preq_answer_set::value_type
                      value_type;

                    const unsigned duration =
                      wpl::tool::extract_little_endian_short_u(mh->duration);
                    if (duration > 32767)
                      std::cerr << "WARNING: Invalid duration." << std::endl;

                    std::pair<iterator, bool>   insertion = pr_answers.back().
                      insert(value_type (sa, presp_attr ()));
                    presp_attr&         attr = insertion.first->second;

                    if (not insertion.second)
                      ++attr.retries;
                    addrs[sa].last_presp = &attr;
                    attr.arrival = toa;
                    attr.ack_expected_arrival = toa + microseconds(duration);
                    attr.ack_arrival = boost::posix_time::not_a_date_time;
                  }
                break;
              }
            default:
              break;
            }
          break;
        }

      case wpl::wifi::type::control:
        {
          namespace ack         = wpl::wifi::ctl::ack;
          namespace subtype     = wpl::wifi::ctl::subtype;

          if (subty == subtype::ack)
            {
              const ack::header* ah =
                reinterpret_cast<const ack::header*> (f);


              addr_state::presp_attr* last_presp = addrs[ah->ra].last_presp;

              if (last_presp and
                  toa < last_presp->ack_expected_arrival + microseconds(1))
                {
                  ++last_presp->acks;
                  last_presp->ack_arrival = toa;

//                std::cerr << toa << " ACK -> " << ah->ra
//                          << " (" << last_presp->acks << ", "
//                          << (last_presp->ack_expected_arrival - toa)
//                          << ")\n";
                }
            }
        }
        break;

      default:
        break;
      }
  }

  inline
  void
  frames::update(const wpl::pkt::metadata& h, const wpl::prism::header* p)
  {
    if (p->noise.get(false)) // Incorrectly received frame.
      {
        update_counters(h);
        phy_error_count++;
        return;
      }

    update(h, reinterpret_cast<const void*> (p + 1));
  }

  inline
  boost::posix_time::ptime
  frames::update_counters(const wpl::pkt::metadata& h)
  {
    using boost::gregorian::date;
    using boost::gregorian::Jan;
    using boost::posix_time::seconds;
    using boost::posix_time::microseconds;

    const ptime toa (date(1970, Jan, 01),
                     seconds (h.ts.tv_sec) +
                     microseconds (h.ts.tv_usec));

    if (first.is_not_a_date_time())
      first = toa;
    last = toa;
    frame_count++;
    total_len += h.len;
    total_caplen += h.caplen;

    return toa;
  }

} // End of namespace stats.

#endif // ! WIFI_STATS_HXX_

---