Monday, November 9, 2009

Internet Indirection Infrastructure

Originally Internet based on point-to0point communication abstraction, but many applications have emerged like multicast, anycast and host mobility that require more general abstraction and a layer of indirection that decouples the sending host from the receiving host mismatched with the original one. however, implementing these general abstraction at IP layer or application layer poses many difficulties. This paper portrays a single overlay network to serve as an indirection infrastructure i3 that combine the generality of IP layer solutions with the deployability of overlay solutions. It offers best effort service without reliability or ordered delivery.
i3 serves as a rendezvous-based communication abstraction where a single node in this network is responsible to store packets sent to all identifiers id's that agree in the first k bits. Receiver sends trigger (idt, addr) to indicate that all packets with longest prefix match id should be forwarded by the i3 infrastructure to the node identified by addr. i3 achieves general communication abstraction of
i) mobility by maintaining end-to-end connectivity even when both end points move simultaneously by simply updating the receiver's trigger to consider the new address
ii) multicast by simply having hosts maintain triggers with the same identifier
iii) Anycast by simply having hosts of anycast group maintain triggers which are identical in a prefix of length k bits. This also is helpful to encode application preferences through the use of m-k bits which can used to balance the load over the servers
Another generalization of i3 is to replace an identifier by identifier stack that can be a list of identifier or address such that a source can send a packet to a series of identifier. These type of generalization is helpful to transform the data by third part server or to pass the data through firewall before its delivering to the destination, to enabling heterogeneous receivers to subscribe to same multicast group.
i3 is implemented depending on Chord lookup protocol using circular identifier space with m=256bits and k=128 bits, such overlay Check Spellingnetwork is self configuring in that a node can join i3 infrastructure simply. i3 uses soft state approach to be robust against node failures depending on the packet routing, end-host's periodic refreshing to maintain their triggers and stack identifier. However, the routing in i3 overlay network is less efficient than routing via IP. Thus, the clients caches the i3 server's IP address and the receiver has to choose their triggers with an identifier that is located on nearby server.
The paper simulates i3's efficiency with randomly distributed identifier. The big challenge was to achieve efficient routing since the end-host doesn't have good control over the location of it's triggers. A ratio of inter node latency on i3 network to that on IP network is used to enhance the performance of i3.

Monday, November 2, 2009

LOOKINGUP DATA in P2P SYSTEMs

one of the main challenges in Large P2P systems is the lookup problem without a centralized server. Many algorithms have been developed based on DHT interface while the algorithm must be able to locate the node that is responsible to store the data associated with a specific key. This requires that each node has to maintain IP address of neighbors to form an overlay network. DHT implementation includes that keys and node are identified using a number of m-bits, and each key is associated to data stored in node with ID close to that key. The paper discusses recent scalable algorithms with low latency and balanced distribution of keys among the nodes.
In Chord, each node has a finger table based on power of two data structure such that- a query for a key k is forwarded to the node in finger table with the highest ID not exceeding k and at least half of the remaining ID-space distance to k. the distance function is unidirectional and asymmetric. It depends on the numeric difference between two ID.
Pastry, Tapesry and Kademlia based on tree-like data structure. In Pastry and Tapesry, each node maintains a the location of some node with each prefix such that the distance function is symmetric but not unidirectional. The correctness requires that each node has a leaf set (nodes closest smaller and larger than the node). Pastry optimize the forwarding performance by maintaining a routing table that will be used to find a node has a longer shared prefix (than current node or at least equal) with the queried key.
Kademlia's distance function depends on XOR of two ID that means it is symmetric and unidirectional.
In CAN, each node is responsible for a rectangular zone and it maintains a routing table of the neighbors in coordinate space. The lookup is performed by forwarding the query in straight path roughly to the neighbor to the node storing the key.
Each of the aforementioned algorithms involves a procedure to adapt to node's arrival and departure with a a key difference in the data structure they use as a routing table. However, these P2P lookup algorithms have been analyzed under static conditions only. As it is obvious, they have many common and different aspects and they need further work to get more strength one.

Tuesday, October 20, 2009

White Space Networking with Wi-Fi like Connectivity

The paper focuses on setting up a UHF white space WhiteFi network without interference with wireless transmissions of primary users and with ability to handle spectrum fragmentation of different width. UHF channel of 30 segments each of 6 MHz width


The authors have implemented WhiteFi on the KNOWS platform that incorporates a Wi-Fi card, a UHF band converter, and SDR. The platform has two key features
1) Variable Channel Widths where the transmitted and received signal can be of bandwidth 5, 10 and 20 MHz. this will impose longer time to scan and discover AP since the scanning has also include the probable combination between the available channels

2) SIFT analyzes incoming signals in the time domain to detect transmissions over different channel widths without changing the channel width of the wireless card. It is able to distinguish intermittent data from noise. SIFT is important to reduce the required time to discover APs that have switched to a different part of the spectrum

WhiteFi requires applying adaptive spectrum-assignment algorithm that periodically reevaluates the assignment based on white space availability at the AP and clients using the spectrum map and airtime utilization observed at each of the clients. AP must pick a channel that is free for all its clients.

Monday, October 19, 2009

Interactive WiFi Connectivity For Moving Vehicles

The challenges in a network with vehicular clients are sharp drop in the connection and unpredictably and the difficulty of estimating the continuously changing channel quality.

The paper presents the design and performance measurement of diversity-based handoff protocol ViFi, a protocol that minimizes disruptions in WiFi network connectivity to support interactive applications from vehicular clients. The measurement study is for two commonly used interactive applications: VoIP and short TCP transfers of two vehicular mobile network testbeds; VanLAN and DieselNet in different cities. ViFi exploits macrodiversity (i.e connection with multiple basestation on the same channel simultaneously) and opportunistic receptions by nearby basestations to minimize disruptions for mobile clients. The challenge in designing ViFi is in coordinating among basestations that opportunistically receive packets. ViFi imposes inter-BS communication within limited bandwidth, minimum overhead, low latency per packet.
In ViFi, the client broadcasts the identity of the selected nearby BS as anchor that provides Internet access, the auxiliary set of BSes and the previous anchor. The old anchor transfers any unacknowledged packets that were received from the Internet to the new anchor that treats these packets as if they arrived directly from the Internet.

The paper investigates four practical and two ideal handoff policies, five of them are based on hard handoff strategy where the client associate with one BS at a time depending on different factors. Two performance measurements are used to evaluate the performance of these different policies: aggregate performance and period of uninterrupted connectivity where it has been found that more packets can be delivered, less number of interruptions and longer uninterrupted session can be achieved as with multi-BS handoff policy. The deployed prototype doubles the number of successful TCP transfers and doubles the length of disruption-free VoIP calls compared to a hard handoff protocol. However, it performs poorly in case of high number of auxiliary BSes and/or equal distance from the auxiliary BSes to the source and the destination.

Thursday, October 15, 2009

ExOR: Opportunistic Multi-Hop Routing for Wireless Network


The paper presents design, implementation and evaluation of a new link/network-layer routing technique. Depending on periodic measurement of delivery probability of node pairs, sub set of the useful nodes between the source and destination will agree to receive broadcasted packets from the source. Each packet contains a list of candidate and prioritized forwarders. The closest node to the destination (with the highest priority) will forward the packet by broadcasting it again to new sub set and so on till it reaches the destination. this requires time scheduling to avoid collision and agreement to choose one forwarder to avoid duplication. But the agreement overhead is propotional to the number of nodes, so the sub set must be chosen carefuly to avoid including useless nodes or that enforce transmission more than once.
ExOR header is longer than that of traditional one and depends on the forwarder list size. It is unlike traditional routing can deal with asymmetric links and also with long route with high loss rate that are avoided by tradtional routing.

ExOR was evaluated on outdoor roof-top 802.11 network. It has been found that ExOR's throughput is higher than the throughput using traditional routing over long and short links, where the highest achievement is over longest routes of five and seven hops. It ensure fewer transmission of each packet which results in less interference for network's users on the same spectrum.
But if ExOR routing achieves improvement in the throughput, why it is applied to transfer just 90% of the packets while the remaining packets are transferred with traditional routing.

Tuesday, October 6, 2009

Architecture and Evaluation of an Unplanned 802.11b Mesh Network

The paper tries to combine the best characteristics of multi-hop and single-hop network types; unplanned mesh network with wide coverage and acceptable performance. It evaluates such architecture using Roofnet which is a multi-hop 802.11b Internet access network with 37 nodes spread over four square Km of densely populated area. The main characteristics of Roofnet are

  • Each Roofnet node involves PC with Internet access via Ethernet port, 802.11b card, omni-directional antenna and software; Linux, routing software, DHCP and Web server
  • Each node has a unique Roofnet layer address (assigned automatically via Roofnet software) and IP address (assigned via DHCP server) that will be used inside Roofnet only
  • If a Roofnet node success to connect to an ISP, it will advertise itself as Internet gateway and provide wireless sharing of Internet connection for other nodes using NAT. Otherwise it is default router for the host and it can connect to the Internet via the gateway with the best ETT metric (lowest ETT or highest throughput).
  • ETT uses periodic broadcast of 1500-byte in a forward direction at each available 802.11 bit rate and 60-byte at 1Mbps in reverse direction
  • Roofnet routing protocol Srcr uses Dijkstra's algorithm on the partial database of many link's metrics to find highest throughput route whenever the node learns of changed link metric
  • The nodes learn the link's metric either from dummy queries from gateway or from the forwarded data packets which includes the link's current metric in the packet's source route.
  • Roofnet uses SampleRate algorithm to select bit rate that provide highest throughput depending on the delivery probability, as it send data packet
Evaluation of Roofnet found that the average throughput over all links is 627 kbps and it decreases with number of hops and average RT delay of 39 msec. Roofnet users talk to Internet gateway with an average throughput of 1395 kbps and average RT delay of 22 msec. Also, it has been found that Srcr effectively selects short links of a few hundred meters and ignores long links

Sunday, October 4, 2009

Modeling Wireless Links for Transport Protoocols

New transport protocol should be designed for good performance over both fixed and wireless links. However, Variable bandwidth, corruption, channel allocation delay and asymmetry of wireless links can affect negatively on transport protocol performance. This paper presents a model for cellular, WLAN and satellite links wireless links that help to minimize these impacts on transport protocols. It considers single or multiple Wireless links located at one end or in the middle of the communication path

The goal is to optimized realistic (set up parameters that accurately portrays real world behavior), easy, exploring wide space of the parameters, and detailed traffic model to evaluate the effect of link-level mechanisms on transport protocol's performance for two ways transfers. Performance metric of wireless link is the goodput that reflects the energy and spectrum efficiencies, interference and cost.

The authors discussed some characteristics of wireless link, their effects on transport protocol and how they can be modeled, like

  • Error loss can reduce the sending rate by triggering lengthy retransmission timeout. At the same time the bursty loss can increase the throughput than in case of equivalent number of non-bursty losses. Such impact can be modeled at the end of the link by dropping packets
  • Abrupt increase in link delay can trigger spurious timeout, retransmission and reduce the sending rate. The delay can be modeled by deferring the data transmission on the link.
  • Packet reordering due to link-level retransmission can incorrectly trigger congestion control responses for TCP while such delivery is helpful to decrease the delay for unreliable transport protocol. It can be modeled by swapping the packets in a queue, or delaying one packet at a time and letting other to pass
  • Resource allocation delay translates to increased delay to the user and it can be modeled by introducing additional delay when a packet arrives to a queue that has been empty for a time longer than the channel hold time
  • Decrease in link bandwidth results in triggering spurious timeouts in TCP while increase in the bandwidth could result in inefficient utilization of link bandwidth. This oscillation also leads to packet reordering. It can be modeled by changing link bandwidth
  • Asymmetric bandwidth and latency in up/downlink directions of a wireless link could result in congestion and limit the throughput. It requires configuration different parameters for up/downlink's bandwidth and latency.

    The paper also discusses
    1) the buffering model and its management and size impacts on transport protocol. While large size of buffer leads to poor loss recovery, small buffer size results in low link utilization and packet drop. Drop-Tail queue management can lead to bursty loss of packet followed by triggering retransmission timeout.
    2) Mobility model and its effects, where the mobility can result in packet loss, introduce delay and can also lead to change in link bandwidth and latency.

    Finally, the paper suggests that cross-layer communication (between link layer and transport layer) could be helpful to optimize the performance over wireless link. It could be investigated for transport protocol to inform the link layer that it is tolerant to packet reordering, or the degree of delay or bit errors –tolerance. It can also be investigated for link-layers to inform transport end-nodes of bandwidth or delay changes from handovers