Thursday, October 30, 2008

Reading for Lecture Oct 30

Chord: A Scalable Peer-to-peer Lookup Service for Internet Application

Chord provides support for just one operation: given a key, it maps the key onto a node. Chord uses a variant of consistent hashing to assign keys to Chord nodes. This tends to balance load, since each receives roughly the same number of keys. The major features of Chord are simplicity, provable correctness and provable performance.

Chord node need routing information about O(log N) nodes and a node resolves the hash function by communicating with other nodes. It resolves all lookups via O(log N) messages to other nodes. Chord maintains its information as nodes join and leave the system; with high probability each such event results in no more than O(log^2N) message.

The consistent hash function assigns each node and keys an m-bit identifier using a base hash function such as SHA-1. A node’s identifier is chosen by hashing the node’s IP address, while a key identifier is produced by hashing the key. Identifiers are ordered in an identifier circle modulo 2^m. The key k is assigned to the first node whose identifier is equal to or follows k in the identifier space. If identifiers are represented as a circle of numbers from 0 to 2^m – 1, then successor(k) is the first node clockwise from k.

Each node n maintains a routing table with at most m entries called the finger table. The i^th entry in the table at node n contains the identity of node s = successor(n + 2^i) where 1 <= I <= m. Thus each node only has to store information about a small number of nodes and know more about nodes closely follow it on the identifier circle then about nodes farther away. When a node n does not know the successor of a key k, it can find a node whose ID is closer than its own to k. That node will know more about the identifier circle in the region of k than n does.

I do not really understand the “with high probability” phrase.

Looking Up Data in P2P Systems

This paper describes the data looking-up mechanism in P2P systems. The mechanism needs to be scalable, and distributable.

In tree-like routing, each node records, for each prefix, the location of some node with that prefix. Pastry, an instance of the algorithm, gives each node a randomly chosen ID indicating its position on an identifier circle. It routes messages with a key to the live node with a node ID numerically closest to the key.

Each node n maintains a leaf set L, which is the set of |L|/2 nodes closest to n and larger than n, and the set of |L|/2 nodes closest to n and smaller than n. The correctness of this leaf set is the only requirement for correctness; forwarding is always correct, unless |L|/2 nodes with adjacent IDs fail simultaneously.

When a node n’s sought key is in the leaf set, the query is forwarded to that node. If it is not there, it tries to forward the query to the node in the leaf set that have the same closest prefix to the key. This continues until the query reach the destination.

Tuesday, October 28, 2008

Reading for Lecture Oct 28

Resilient Overlay Networks
RON is an architecture that allows distributed Internet applications to detect and recover from path outages and periods of degraded performance within several seconds. It is an application layer overlay on top of the existing Internet routing substrate.

The main goal of RON is to enable a group of nodes to communicate with each other in the face of problems with the underlying Internet paths connecting them. It aggressively probes and monitors the paths connecting its nodes to detect link failures and find the best paths. Information exchanged between nodes is metrics including latency, packet loss rate, and available throughput.

RON takes advantages of underlying Internet path redundancy on time-scales of a few seconds, reacting responsively to path outages and performance failure. It is closely tied to the application using it and it more readily integrates application specific path metrics and path selection policies. It demonstrate fast recovery from failure and improved latency and loss-rate even over short-time scale.

For each link, the latency estimate is updated as: lat ← α . lat + (1-α). new_sample. The overall latency for a path is the sum of the individual virtual link latencies: lat_path = Σlat_link. The loss rate metric is multiplicative on a path. The score = (1.5^0.2)/(rtt*p^0.5) is used to prevent large route oscillations from single packet losses.

Active network vision and reality lessons from a capsule-based system


Active networks help deploying new services rapidly but enabling the programmability at each router in the networks. Some active networks provide extensibility to individual devices; this kind of systems is well suited to the task of imposing policy or functionality at particular network location like boundary devices. Another style of system provides programmability across multiple odes for control tasks rather than new data transfer service.

ANTS does not a priori restrict who can program which nodes. It aims to allow each user to construct new data transfer services across the wide-area. ANTS is based on an aggressive “capsule” approach in which code is associated with packets and run at selected IP routers that are extensible.

In ANTS, applications obtain customized network services by sending and receiving special types of packets called capsules via a programmable router referred to as an active node. The field type to determine the service, hence, which code to run. If a node does not have that code, it requests from previous node. The ANTS places of limit of 16KB on the code each service to limit the impact of code transfers on the network.

Does processing capsule affect the performance at each node? With 16Kb code, what services can be supported? Do functionalities also depends on infrastructure at each node? Does active network violate end-to-end argument?
Resilient Overlay Networks
RON is an architecture that allows distributed Internet applications to detect and recover from path outages and periods of degraded performance within several seconds. It is an application layer overlay on top of the existing Internet routing substrate.

The main goal of RON is to enable a group of nodes to communicate with each other in the face of problems with the underlying Internet paths connecting them. It aggressively probes and monitors the paths connecting its nodes to detect link failures and find the best paths. Information exchanged between nodes is metrics including latency, packet loss rate, and available throughput.

RON takes advantages of underlying Internet path redundancy on time-scales of a few seconds, reacting responsively to path outages and performance failure. It is closely tied to the application using it and it more readily integrates application specific path metrics and path selection policies. It demonstrate fast recovery from failure and improved latency and loss-rate even over short-time scale.

For each link, the latency estimate is updated as: lat ← α . lat + (1-α). new_sample. The overall latency for a path is the sum of the individual virtual link latencies: lat_path = Σlat_link. The loss rate metric is multiplicative on a path. The score = (1.5^0.2)/(rtt*p^0.5) is used to prevent large route oscillations from single packet losses.

Active network vision and reality lessons from a capsule-based system


Active networks help deploying new services rapidly but enabling the programmability at each router in the networks. Some active networks provide extensibility to individual devices; this kind of systems is well suited to the task of imposing policy or functionality at particular network location like boundary devices. Another style of system provides programmability across multiple odes for control tasks rather than new data transfer service.

ANTS does not a priori restrict who can program which nodes. It aims to allow each user to construct new data transfer services across the wide-area. ANTS is based on an aggressive “capsule” approach in which code is associated with packets and run at selected IP routers that are extensible.

In ANTS, applications obtain customized network services by sending and receiving special types of packets called capsules via a programmable router referred to as an active node. The field type to determine the service, hence, which code to run. If a node does not have that code, it requests from previous node. The ANTS places of limit of 16KB on the code each service to limit the impact of code transfers on the network.

Does processing capsule affect the performance at each node? With 16Kb code, what services can be supported? Do functionalities also depends on infrastructure at each node? Does active network violate end-to-end argument?

Tuesday, October 21, 2008

On Power-Law Relationships of the Internet Topology

The power-laws for the topology of the Internet over the duration of 1998 are determined from the topology of the Internet. The power law are expression of the form y ∝ x^a, where a is a constant and x and y are measures of the interest and ∝ stands for proportional to.

The sample space during that time is rather limited, though the size of the network increased substantially (45%), making any generalizations would be premature. However, the power-laws of Internet growth the same way the power-laws describing various natural networks such as the human respiratory system and automobile network.

The topology of the Internet can be divided into two different granularies: router level and inter-domain level. The metrics used to describe the graph are mainly the node outdegree and the distances between nodes. The power laws have been used to describe traffic in communication networks but not their topology.

The first power-law is called rank exponent. The outdegree of a node is proportional to the rank of the node to the power of the constant. The second power-law called outdegree exponent states that the frequency of an outdegree is proportional to the outdegree to the power of a constant. The third power-law, eigen exponent, states that the eigenvalues of a graph are proportional to the order to the power of a constant.

The power-law can be useful for predict future Internet based on the similarity with other network.

A First-Principles Approach to Understanding the Internet’s Router-level Topology

The degree distributions and other large scale statistics are popular metrics for evaluating how representative a given topology is and proposed topology generators are often evaluated on the basis of whether or not they can reproduce the same types of macroscopic statistics, especially power-law distributions.

However the above perspective is not complete and in need of correction actions. There exists many different graphs having the same distribution of node degree, some of which may be considered opposites from the viewpoint of network engineering. The first principles approach is to understand Internet topology at the router level.

Each of the topology generators uses one of the three probabilistic generation methods: 1) preferential attachment which says the growth and each newly added node connects to some existing nodes preferentially such that it is more likely to connect with a node that already has many connections. 2) General model of random graphs with a given expected degree sequence. The construction proceeds first by assigning each node its degree then probabilistically insert edges between nodes. 3) The power law random graph involves forming a set L of nodes containing as many distinct copies of a given vertex as the degree of that vertex, choosing a random matching of the elements of L, and applying a mapping of a given matching into an appropriate graph.

The commonly-used metrics are node degree distribution; expansion, resilience, distortion; hierarchy. Given the purpose for building a network is to carry effectively a projected overall traffic demand, others performance-related metrics are considered: throughput; router utilization; end user bandwidth distribution. The likelihood metric is used to differentiate between graphs having the same vertex set and the same degree distribution.

Wednesday, October 15, 2008

Thursday, October 9, 2008

Reading for Lecture Oct 9

XORs in The Air: Practical Wireless Network Coding

The paper shows that intelligently mixing packets increases network throughput. The COPE architecture’s principles exploit the broadcast nature of the wireless channel and the theory of network coding. It inserts a coding shim between the IP and MAC layers, which identifies coding opportunities and benefits from them by forwarding multiple packets in a single transmission.

The basic idea of COPE is that a COPE router XORs two packets from two nodes sending to each other and broadcast the XORed packet to both of the nodes so that the two can again XOR with their packets to get their expected packets, thus this process needs only three transmissions instead of 4. COPE architecture incorporates three main techniques: 1) Opportunistic listening; 2) Opportunistic Coding; and 3) Learning neighbor state.

Opportunistic listening happens since wireless is a broadcast medium so that nodes have many opportunities to overhear packets when they equipped with omni-directional antennae. Cope nodes in promiscuous mode snoop on all communications over the wireless medium and store overheard packets for a limited period of time. In addition, each node broadcasts reception reports to its neighbors about the overheard packets.

The opportunistic coding aims at maximizing the number of native packets delivered in a single transmission, while ensuring that each intended next hop has enough information to decode its native packets.

Since report packets can be lost during congestions, thus a node has to guess to learn about packets that its neighbors have using ETX metric broadcast to all nodes then estimates the probability that a particular neighbor has a packet as the delivery probability of the link between the packet’s previous hop and the neighbor.

The COPE actually has beneficial side effect on MAC because it reduces the mismatch between edge nodes and the routers resulting in fewer packets dropped and thus better gain.
The paper does not address the issue of packet reordering as they prefer to code packets of the same size. When finding the maximum number of packets encoded, they do not account for the error in wireless environment and implicitly assume that the links are error free. This probably not true since when n too large the probability that one packet is corrupted become considerably large, and if a node can not receive one packet out of n, it can not decode its expected packet thus a retransmission is likely to happen for each node.

ExOR: Opportunistic Multi-Hop Routing for Wireless Network

The ExOR chooses each hop of a packet’s route after the transmission for that hop so that the choice can reflect which intermediate nodes actually received the transmission. This deferred choice allows each transmission multiple opportunities to make progress by choosing the best possible current routes.

The basic idea of this routing is that when a source wants to send a packet, it broadcasts the packets and some sub-set of nodes will receive the packet. All the nodes run a protocol to discover and agree on which nodes are in that sub-set. The nodes in the subset closest to the destination broadcast the packet. Again the nodes receiving the second transmission agree on the closest receiver, which then broadcast the packet. This process continues until the destination has received the packet.

The agreement protocol must have low enough overhead that it does not overwhelm the potential throughput gain and must be robust in the face of packet loss that disagreement and thus duplicate forwarding are rare. ExOR must have a metric reflecting the cost of moving a packet forward from any node to the destination thus it helps choosing the closest node.

The ExOR must choose the most useful nodes as participants and avoid simultaneous transmissions by different nodes to minimize collisions. The ExOR operates in batches of packets and includes a list of prioritized candidate forwarders in each packet. The receiving nodes buffer successfully received packets and wait to the end of the batch. The forwarders then broadcast the packets in their buffer in prioritized order. The batch map included in each packet indicates the highest-priority node known to have received a copy of that packet.
Since ExOR operates in batches of packets, packets likely suffer from large delay.

Tuesday, October 7, 2008

Reading for Lecture Oct 7

A High Throughput Path Metric for Multi-Hop Wireless Routing

The Expected Transmission Count metric (ETX) minimizes the expected number of packet transmissions (including retransmissions) requires to successfully deliver a packet to the ultimate destination, thus by which finds high-throughput paths on multi-hop wireless network. The ETX is used as a metric for DSDV and DSR protocols.

The commonly used metric by existing ad-hoc routing protocols is minimum hop-count often implicitly assumes that the links either work well or don’t work at all, which is true for wired networks but not for wireless networks. The 802.11b ACK mechanism resends lost packets locally, thus making all the worst 802.11b links appear loss-free, however the retransmissions reduce path throughput and interfere with other traffics. The ETX find paths with the fewest expected number of transmissions.

The best path between each pair of nodes was found by sending data along ten potential best paths, one at a time, and selecting the path with the highest throughput. An offline routing algorithm is used to find potential best paths using as input measurement of per-link loss ratios and with a penalty to reflect the reduction in throughput caused by interference between successive hops of multi-hop paths.

The ETX metric must account for the following issues: 1) the wide range of link loss ratios; 2) the existence of links with asymmetric loss ratio; 3) the interference between successive hops of multi-hop paths. The ETX of a link is calculated from the forward delivery ratio df, the probability that a data packet successfully arrives at the recipient, and the reverse delivery ratio dr, the probability that the ACK packet is successfully received. Thus the expected probability that a transmission is successful is df x dr then ETX = 1/ df x dr.

These delivery ratios are measured using dedicated link probe packets. Each node broadcasts link probes of a fixed size at an average period τ with jitter. Each node remembers the probes it receives in during the last w seconds, thus allowing it to calculate the delivery ratio from the sender at any time t as r(t) = count(t – w, t)/(w/τ).

The ETX only makes sense for networks with local link-layer retransmission and furthermore, ETX assumes that radios have a fixed transmit power level. ETX loss measurements do not reflect how busy a link. And 802.11b can be unfair under high load causing a node might never be able to send its probes, causing its neighbors to believe that reverse delivery ratio had become zero.

A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols

In wireless mobile ad-hoc network, each mobile node operates not only as a host but also as a router forwarding packets for other mobile nodes in the network that may not in direct wireless transmission range of each other. The ns-2 network simulator is extended to include node mobility, a realistic physical layer, radio network interfaces and IEEE802.11 MAC protocol using DCF.

The DSDV protocol requires each node to periodically broadcast routing updates. Each DSDV node maintains a routing table listing the next hop for each reachable destination. DSDV tags each route with a sequence number and considers a route R more favorable than R’ if R has a greater sequence number, or if the two routes have equal sequence numbers but R has a lower metric.

The TORA protocol is designed to discover routes on demand provide multiple routes to a destination, establish routes quickly, and minimize communication overhead by localizing algorithmic reaction to topological changes when possible. The mechanism of TORA resembles water flowing downhill towards a destination node through a network of tubes that models the routing state of the real network.

The DSR protocol consists of two mechanisms: route discovery and route maintenance. The route discovery mechanism discovers routes when a node S wishing to send a packet to node D and obtains a new route to D. The route maintenance operates by which a source S detects if the network topology has changed such that it can no longer use its route to the destination D because some two nodes in its route have moved out of each other’s range, thus disconnected. The AODV is essentially a combination of both DSR and DSDV.

The overall goal of the experiments was to measure the ability of the routing protocols to react to network topology change while continuing to successfully deliver data packets to the destination. The simulation of 50 wireless nodes forming an ad hoc network moving about over a rectangular 1500m x 100m flat space during 900 seconds. The sources send data at a constant bit rate. The metrics for comparing protocols are packet delivery ratio, routing overhead and path optimality.
The experiment tries to use sources with constant bit rate which is of often not realistic. Non-constant bit rate connections often cause more problems for wireless environment since the network cannot frequently check the status of routes in the network as well as discover new network topology.

Thursday, October 2, 2008

Readings for Lecture Oct 2, 2008

Architecture and Evaluation of an Unplanned 802.11b Mesh Network

The Roofnet wireless mesh architecture has unplanned node placement, omni directional antennas and multi-hop routing and optimization of routing in a slowly changing network. The design goals of this network are operating without extensive planning or central management but still providing wide coverage and acceptable performance. This architecture carries risks that lack of planning might render the network’s performance unusably low.

This Roofnet is designed over an area of about four square kilometers. Most of nodes are located in three or four-storey buildings. Line-of-sight signal propagation between nodes id often obstructed. Each node is hosted by a volunteer user.

Each Roofnet node consists of a PC, an 802.11b card and a roof-mounted omni-directional antenna. The 802.11b cards operate with RTS/CTS disabled and all share the same 802.11b channel. The cards use o non-standard “pseudo-IBSS” mode , similar to standard 802.11b IBSS mode. The Pseudo-IBSS omits 802.11b’s beacons and BSSID (network ID).

Each Roofnet node runs identical turn-key software consisting Linux, routing software implemented in CLICK, a DHCP server and a webserver. The nodes are completely self-configuring, thus the software must automatically solve problems like allocating addresses, finding a gateway between Roofnet and the Internet, and choosing a good multi-hop route to that gateway.

The Roofnet carries IP packets inside its own header format and routing protocol. Each node will assign address automatically based on Ethernet address and unused class A IP address block. Only a small fraction of Roofnet users connected to Internet via wired Internet access links. The nodes connected to Internet advertise itself to Roofnet as an Internet gateway. These gateways act as a NAT for connections. Other nodes select the gateway to which it has the best route metric.

This network’s architecture favors ease of deployment by using omni-directional antennas, self-configuring software and link quality. The average throughput between nodes is 627 kbits/second. Since each internal node has multiple output gateway and can choose best current gateway, the Roofnet’s multi-hop mesh increase both connectivity and throughput.

Modeling Wireless Links for Transport Protocols

The wireless links’ intrinsic characteristics that affect the performance of transport protocols like variable bandwidth, corruption, channel allocation delays, and asymmetry. Congestion control in today’s Internet supposes that almost all packets losses result from congestion, however, packet losses on wireless links that are from corruption rather than congestion violates this assumption.

Three main types of wireless links are: cellular, WLAN and satellite. Topologies play an important role in wireless links. The number and location of wireless links in the path can affect the performance of transport protocols. Latencies, error loss rates of multiple wireless links add up, making loss recovery and congestion control more difficult.

Traffic models have significant effects on simulations results. Typically, mobile users transfer more data downlink than uplink. The performance metrics for evaluating performance include throughput, delay, fairness and dynamics. The first problem is the use of unrealistic models. The second problem occurs when the models are realistic but explore only a small corner of the parameter space.

Error losses can be modeled by dropping packets according to a per-packet, per-bit or time-based loss probability. The sudden increase in the delay can have a negative impact on transport protocols i.e. causes unnecessary retransmissions and false congestion control. Wireless links can introduce packet reordering during link-level error recovery using retransmission. They also often allocate channels based on the availability of user traffic. The bandwidth variation in wireless links can cause spurious timeouts and the asymmetry in bandwidth and latency can cause the congestion for TCP ACK. The mobility, an intrinsic property for most wireless links, presents a major challenge to transport protocols through the packet losses and delay introduced by handover.

In some cases, the wireless link level technologies have been design to take into account the performance requirement of the current TCP standard. In other cases, discussion is about the adaptation of transport protocols to the need of wireless links. The paper consider different models and parameters to be used in answering the questions and others about transport protocol performance over wireless links.