Description:

Privacy leaks are an unfortunate and an integral part of the current Internet domain name resolution. Each DNS query generated by a user reveals -- to one or more DNS servers -- the origin and target of that query. Over time, a user's browsing behavior might be exposed to entities with little or no trust. Current DNS privacy leaks stem from fundamental features of DNS and are not easily fixable by simple patches. Moreover, privacy issues have been overlooked by DNS security efforts (i.e. DNSSEC) and are thus likely to propagate into future versions of DNS.

In order to mitigate privacy issues in current DNS, this paper proposes a Privacy-Preserving Domain Name System (PPDNS), which maintains privacy during domain name resolution. PPDNS is based on distributed hash tables (DHTs), an alternative naming infrastructure, and computational private information retrieval (cPIR), an advanced cryptographic construct. PPDNS takes advantage of the DHT's index structure to improve name resolution query privacy, while leveraging cPIR to reduce communication overhead for bandwidth-sensitive clients. Our analysis shows that PPDNS is a viable approach for obtaining a higher degree of privacy for name resolution queries. PPDNS also serves as a demonstration of blending advanced systems techniques with their cryptographic counterparts.

People Involved: Yanbin Lu and Gene Tsudik

Description:

TCP is shown to be inefficient and unstable in high speed and long latency networks. The eXplicit Control Protocol (XCP) is a new and promising protocol that outperforms TCP in terms of efficiency, stability, queue size, and convergence speed. However, Low et al. recently discovered a weakness of XCP. In a multi-bottleneck environment, XCP may achieve as low as 80% utilization at a bottleneck link and consequently some flows may only receive a small fraction of their max-min fair rates.

To address this problem, we developed iXCP, an improved version of XCP aimed at achieving Max-Min fair bandwidth allocation. The basic idea is to enable each link to identify the flows bottlenecked at itself and shuffle traffic only among these bottlenecked flows.

People Involved:  Yanbin Lu, Xiaowei Yang and Lei Zhan

Description:

My basic requirements for a binary heap are

1. It is based on STL. (general-purpose, lightweight and efficient)
2. Its element is mutable (For example, if an element's value is changed, the element can be moved to the correct position inside the heap)
3. The position of each element inside the heap is tractable. (When one wants to update an element by update_heap_pos, the position of the element inside the heap should be provided. If the position of the element is unknown, one has to go over the whole heap to determine its position, which is quite inefficient.)

I have been looking for such a binary heap implementation for a long time. To my disappointment, nothing completely meets the above requirements. The STL built-in heap does not support value updating (req#2), not to mention position tracking (req#3). The most closely matched one is Mutable heaps in C++ provided by Danny Tarlow, which is evolved from HEAPPlus . Again, it does not support position tracking (req#3).

So I took the implementation from Danny Tarlow and changed it to my purpose. What I basically do is add one more argument to all functions to keep track of the position change of each element. During the testing, a bug was found and fixed in HEAPPlus' initial implementation of __down_heap function which may cause memory violation.

#include "binaryheap.h"
#include <vector>
#include <iostream>
using namespace std;

class Element
{
public:
  Element(int v)
  {
    m_value = v;
  }
  int& Value()
  {
    return m_value;
  }
  uint32_t& heap_pos() { return m_heap_pos; }
private:
  int m_value;
  uint32_t m_heap_pos;
};
ostream &operator<<(ostream &os, Element &n) {
  os << n.Value()<<" pos: "<<n.heap_pos();
  return os;
}
bool operator<(Element a, Element b) {
  return (a.Value() < b.Value());
}

struct CompareElementStar {
  bool operator()(Element *a, Element *b) {
    return (a->Value() < b->Value());
  }
};


struct UpdateElementPos {
  void operator()(Element *a, uint32_t pos) {
    a->heap_pos() = pos;
  }
};

void print_heappos(vector<Element >& ve)
{
  vector<Element>::iterator it;
  for (it = ve.begin(); it != ve.end(); ++it)
    {
      Element e = *it;
      cout<<e<<endl;
    }
}



int main()
{
  vector<Element > velement;	// stores elements
  vector<Element *> vheap;	// heap structure
  
  velement.push_back(Element(0));
  velement.push_back(Element(3));
  velement.push_back(Element(5));
  velement.push_back(Element(6));
  velement.push_back(Element(4));
  velement.push_back(Element(1));
  velement.push_back(Element(2));
  
  for (size_t i = 0; i < velement.size(); i++)
    {
      vheap.push_back(&velement[i]);
    }


  make_heap (vheap.begin(), vheap.end(), CompareElementStar(), UpdateElementPos());

  print_heappos(velement);

  // to update the value of the second element in velement from 3 to 7;
  velement[1].Value() = 7;
  update_heap_pos (vheap.begin(), vheap.end(), vheap.begin() + velement[1].heap_pos(), 
		   CompareElementStar(), UpdateElementPos());

  cout<<"after 3 is changed to 7"<<endl;
  print_heappos(velement);

  return 0;
}