Thursday, October 30, 2008

DHT versus DNS

Today was a great class discussion about Chord, DNS and co. Here is my list of questions and thoughts, I never got to ask in class, some got at least partially answered during the discussion.

Pro DHT:
  • google does not use chord and uses more traditional hierarchical systems, but should we trust all of our data to single companies as hierarchical systems do?
  • Authority: Can we trust the data if we replaced hierarchical DNS by Chord? Yes, if we have a hierarchical system of digital signatures (data and public keys signed by the root, country registrars and domain, subdomain owners), bootstrapped by root signatures which correspond to us needing to know the IP addresses of root servers.
  • DHTs like chord do (theoretically) a beautiful job on load balancing and scalability (compare to BGP where each router needs the 200000 prefix entries routing information whereas chord only needs 31 fingers for 2^32 IDs)
Pro DNS:
  • Malicious nodes can still spoof the non-existence of a certain domain in DHT.
  • DHT provides no geographic locality, doesn't allow for techniques like anycast
  • DNS recursers can be placed at strategic places, e.g. my provides can put a DNS recursers between its clients and and the DNS name servers, so DNS querries would follow how packets would flow instead of detouring which would mean latencies
  • DNS has designated servers
  • DNS caching is very efficient because 99% of all querries are probably for the same 1000 domains. This also plays to the importance of putting htem at good strategic places, i.e. each ISP should put it its own cache close to its edge routers

Some more words on Active Networks

  • It seems to me that Active Networks can only be a compromise between security and usability.
  • In the paper the API was so restricted that the only thing an active node could do was really only forward packets (maybe modify the header a little bit). Using code for this decision is superflous, source routing would give the client actually the same control.
  • This would be more interesting if active nodes could actually in some way process data like aggregate information, so maybe Active Networks are interesting for Sensor-Networks like applications.

Wednesday, October 29, 2008

Chord and tree-like diagrams

I made a picture to show how tree-like DHT forward queries.



and how chord forward queries

The Beauty of Chord

Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balikrishnan, "Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications"

Chapter 3 motivates applications.

Underlying geometry
  • ID space is a ring
  • each ID in ID space is mapped to a node. A node corresponds to a block of consecutive IDs. For redundancy, these blocks can overlap.
  • a node maintains a "routing" table (called fingers) which has an entry to reach the node which is responsible for the ID with distance 1, 2, 4, 8, 16, 32, 64, 128, ...
  • for handling node failures, node also maintains a table of its immeadite k successor in the ID space
  • this really is a small-world network: the entries to its immeadiate successors makes it highly clustered, the routing table entries with long distances make the path length short (log size of ID space)
Mechanisms
  • Node (say A) joins: it is assigned a block in ID space. It computes the IDs with distance 1, 2, 4, 8 ,16, 32, ... from its own block. It uses the existing routing tables of other nodes to query which nodes are responsible for these IDs and constructs a routing table. It also traces back which routing tables of nodes have to be changed (at most log n, querying each costs log n) and updates the existing nodes. Last it has to move data which is left to the application.
  • every node periodically runs stabilization to correct routing tables to account for new nodes
The routing table could list several nodes per n where the distances in ID space are less but close to 2^n. That way lookup failures could be reduced if nodes fail.

P2P DHT Intro

Hari balakrishnan, Frank Kaashoek, David Karger, Robert Morris, Ion Stoica, "Looking up Data in P2P Systems"

General
  • A really nice introduction to P2P systems. It mostly focuses on how to look up data in a decentralized and scalable manner without discussing how to build a system like file-sharing on top of it.
  • P2P has other aspects than illegal music sharing to it
  • Some more words on resilence and definition of correctness would be nice: network will fail, any key could be manipulated or only node's share of keys will be lost or manipulated in case of a failing or malicious node
  • the paper mixed desired features (like scalability) of DHT and mechanisms (like distance function)
Desired Features of DHT
  • hash function: name -> hash (in "ID space"), DHT: hash -> node, node stores value for key, application decides what value means (value could be reference where file is stored)
  • no centralized servers, hierarchy
  • load-balanced key lookup
  • "routing" information at each hop scales logarithmically
  • "routing" hops scale logarithmically
  • adaptive to nodes concurrently leaving and joining
  • low overhead
  • correctness while "routing" tables are still converging, but performance penalty allowed
  • fault tolerance
  • advanced: proximity routing
  • advanced: isolating the impact of malicious nodes
  • advanced: queries like keyword search
How are DHT's different or similar from normal routing?
  • routing forwards packets until reach destination, DHT's redirect key lookups to a different node until the right node is found
  • the table of a DHT maps ID space to nodes, the routing table at A maps space of nodes to nodes connected to A
  • the table of a DHT can map an ID to an arbitray node, a routing table is constrained to connected nodes
Mechanisms
  • All DHT algorithms are inspired by putting structure on the ID space and equipping with a distance function
  • chord: one-dimensional ring, distance is numeric difference (not absolute value, i.e. unidirectional), "routing" table points to nodes at distance 1, 2, 4, 8, 16, 32, 64, 128, ...
  • tree-like routing: nodes are leaves of (binary) tree, distance is prefix-length with numerical difference as tie-breaker, "routing" table at node has an entry for each prefix-length pointing to a random node who is not in that prefix
  • n-dimensional space: each node covers a hypercube of ID's, "routing" table contains neighboring hypercubes, distance probably=Euclidean distance in n-space (was not explained in paper)
  • algorithms maintaining keys, routing information for node joins, leaves, load-balancing. Algorithms maintain invariants for correctness, converge to efficient routing tables for performance

Monday, October 27, 2008

Are Active Networks just Computer Viruses?

David Wetherall, "Active network vision and reality: lessons from a capsule-based system"

If I think about it: the way capsules propagate through a network is by injecting code into the router software to spread to the next router. So this is really how a worm/virus spreads through a network. There have been implemented several active networks already: code red worm, melissa, happy99.exe, Chernobyl. Some of this research lead to imprisonment eventually, apparently the FBI doesn't like research on Active Networks. There are even organizations fighting Active networks, for example Symantec. And unfortunately, Windows is a little ahead of Linux in terms of Active Network implementations.

Active Network basics
  • a packet is called a capsule and carries code (perhaps by reference) executed on the router (active node) to process and eventually forward it
  • benefits: flexible network layer, decoupling services from the underlying infrastructure, enables fast deployment of new features across WANs
  • concerns: mobile code raises security and performance issues
Characterization of Active networks
  • capsule model of programmability
  • accessibility of that model to all users
  • applications that can be constructed
Mechanisms in the paper
  • code is carried by reference which is MD5 encrypted hash = "type of service" field, reduces capsule header to be comparable to IP header
  • code also given a human readable name, distributed through DNS-like directory service
  • code cached locally
  • capsules are forwarded as IP packets between conventional routers, processed as capsules by active routers: this allows for a gradual deployment, deployment on heterogenous network, router can be split into layer processing some packets in hardware fast, and some in software slow
  • code is written in type-safe language (e.g. Java ) or with proof
  • code is executed in isolation from capsules of different type, in sandbox
  • code's runtime and resources are limited
  • code may not change type of service when routing or creating new packets
  • code must lower TTL
  • code can only create limited number of new capsules (e.g. limited by total TTL)
  • but still: code is certified by trusted authority (IETF)
  • API for capsule's code: query node environment, soft-state storage, routing, possibly loss information
  • tests run on ANTA kit, in Java, as overlay network on UDP
Findings
  • code distribution provides insignificant overhead
  • analysis of protection attempts to answer the following questions: 1. can the node runtime be corrupted by service code? 2. can distributed service code be corrupted or sppofed? 3. Can the state cached be inadvertently manipulated by another service?
  • analysis of resource management: 1. Can a capsule consume a large, possibly unbounded amout of resource at a single node? 2. Across a large number of nodes? 3. Can an application running on an end-system be used to inject a large possibly unbounded number of capsules into the network?
Possible Applications
  • Characterization of servies: expressible, compact, fast, incrementally deployable
  • new services based on network layer state
  • multicast, reliable multicast support, ECN, PIP, anycast
Comments
  • The idea of active networks is very interesting, particular regarding the many algorithms and techniques like fair queueing, ECN, XCP, RED, multicast, QoS, anycast which exists but are difficult to deploy on existing infrastructure.
  • But unfortunately the security and resource concerns restrict the abilities of the capsule's code (e.g. isolation from other flows) to implement some of these algorithms. The list of remaining techniques did not convince me. Anycast works reasonably implemented in BGP and through DNS. Maybe it is the revival of multicast?

RON

David Andersen, Hari Balakrishnan, Frans Kaashoek, Robert Morris, "Resilient Overlay Networks"

Shortcomings of today's routing structure
  • A quarter of randomly picked connections between two hosts suffers outages of more than half an hour in a three day period
  • BGP filters and summarizes routing information in the interest of scalability and policy enforcement, delays information to prevent oscillations
  • BGP deems connection alive if BGP session is still alive, however persisten congestion a link might degrade E2E performance
  • BGP policies often do not use private peering links to provide failover capabilities
Proposal
  • Overlay Network of nodes routing packets between them based on RON header
  • Size: a couple of dozen nodes (cluster maintained through RON membership manager)
  • Virtual link between each pair of distinct nodes
  • optimizes different application-specific metrics: API provides explicit way for application to prioritize among throughput, delay, packet loss rate and to define failures
  • fast failure detection and recovery (<20sec) through constant active and passive monitoring of virtual links
  • expressive policy routing
  • Data path: application --conduit API--> entry node --> RON routers --> exit node
  • link state, hop-by-hop routing
  • RON routers and RON membership managers communicate through RON network (versus IP)
  • RON headers have tag identifying flow, keeps flow to a chosen path
  • hysteresis to avoid route flapping
Results
  • outages for no longer than 20secs
  • maximal 30% packet loss rate
  • in most cases RON reduces latency
  • in some cases, RON can significantly improve TCP performance

Comments
  • Exact routing mechanism unclear, looks like hop-by-hop routing, but wouldn't source rouing be better to optimize the application-specific metric, and optimize it only once at the source? (doesn't really matter because most of the time the chosen route has only one RON hop between E2E)
  • What would large-scale deployment of RON mean for the Internet? Will RON further inflate data paths? Will it RON nodes deployed in two peering ASs turn these into ASs defacto transiting traffic?
  • How does RON's forwarding compare to a TCP split connection (split at RON forwarder)?
  • The user experience does contradict the statement that 1/4 of the the routes experience outages of half-an hour in three days. Does this mean that the Internet is really partitioned into Clients and Servers with reliable routes between Clients and Servers, but actually less reliable communication between Clients and Clients? Or is the user experience due to the fact that websites deploy servers across multiple different networks and our querries in fact do not go through the "Inter-"net?

Monday, October 20, 2008

Internet Topology

Michalis Faloutsos, Petros Faloutsos, Christos Faloutsos, "On Power-Law Relationships of the Internet Topology"

Lun Li, David Alderson, Walter Willinger, John Doyle, "A First-Principle Approach to Understanding the Internet's Router-level Topology"

Introduction

There have been developed various measures to classify graphs (=networks) which are coarser than graph isomorphism and various algorithms to generate graphs with different characteristics. These have been applied in numerous areas like neuroscience to understand the wiring of neurons or the web as hypertext, where one particular eigenvector problem called PageRank had tremendous success as a search engine. Among them are:

Measures:
  • Diameter = longest shortest path between any two vertices, can be an unstable measure
  • Average path length = shortest path averaged between any pair of vertices
  • Shortest path length distribution
  • Clustering Coefficient, CC of a vertex is defined by taking the subgraph generated by the vertex and its neighbors and divide its number of edges by the number of edges of a complete graph. CC of a graph is the CC averaged over the vertices
  • degree distributions of vertices
  • eigenvalues of wiring matrix (symmetric with positive entries only, so diagonalizable over R with only positive eigenvalues)
Typical graphs:
  • random graph (short average path length, low CC, normal distribution of degrees)
  • small-world (short average path length, high CC)
  • hierarchical networks
  • scale-free networks where the degree distribution follows a power law
Algorithms:
  • small-world network generation due to Watts/Strogatz observation that little rewiring of a highly clustered network drops the path length [Watts, Strogatz, "Collective dynamics of 'small-world' networks"]
  • scale-free networks can be archived using degree-preserving rewiring: pick four vertices A, B, C, D with edges A-B and C-D. Drop edges A-B and C-D and create edges A-C and B-D. This procedure is ergodic.
On Power-Law Relationships of the Internet Topology

  • Regarding that there have been hundreds of papers who take some real world graph like the highway systems or a friend network and show that it is a scale-free network, it came as little surprise to me that also the degree distributions of Internet router (as of 1995) and AS graph (as measured three times in 1997-1998) are well approximated as scale-free.
  • The paper presents the rank degree distribution and the outdegree exponent as two power-laws when in fact they are the same: the rank of a node is given by integrating the frequency of an outdegree over all outdegrees higher than the node. But integration and inverting functions all turn power-laws into power-laws.
  • P(h) the number of pairs of nodes with distance
  • The eigenvalues follow a power law (it is not clear to me what the eigenvalues of a random graph are, so I don't know how meaningful this is)
A first-Principles Approach to Understanding the Internet's Router-level Topology

  • show that the degree distribution is an incomplete measure of network: by rewiring graphs with the same degree distribution can be obtained which have very different routing properties
  • stresses that low level(physical) links are more important than virtual (IP, AS) links: they determine performance, reliability and robustness
  • generation of realistic graphs has to go beyond creating abstract graphs and consider technological constraints: edges have bandwidths, economic routers only have a certain number of links, trade-off how many links versus BW/link, flow conservation. And economic considerations: degree of nodes decreases and BW increases from edge to core, few long-haul connections
  • new measures:

    • network performance: maximal (in alpha) total throughput where traffic is modeled as X_ij=alpha*x_i*x_j [Criticism: unrealistic regarding that most traffic goes from clients->websites]
    • network likelihood: gives an edge weight=product of degrees of vertices, likelihood=total weight, networks where edges are between high-degree links score higher
  • tested networks:
    • new: heuristically optimal (tree-like at edge, low-degree loose mesh at core) inspired by real networks
    • real networks
    • preferential attachment
    • random network with scale-free distribution
    • suboptimal networks
  • Results:
    • all networks have the same degree-distribution
    • but score differently with respect to new metric
    • performance decreases drastically with the likelihood
    • real networks have low likelihood and high performance
    • a "generic" graph with given degree distribution is having bad performance
This was a really great paper to read!!! It breaks down the assumptions of how relevant the degree-distribution really is, and then comes up with new measurements which yield good results - results which are actually corresponding to real links (physical) and not abstracted networks like IP layer.

Wednesday, October 8, 2008

XORs in the Air

Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Medard, Jon Crowcroft, "XORs in The Air: Practical Wireless Network Coding"

Principles
  • use broadcast nature of wireless (as previous paper)
  • network coding (here: use XORing of packets, pad packets to make them equal length)
The key example to illustrate the potential benefit is in Figure 1. The caption summarizes it so well that I will only refer to it here. COPE is sitting between IP and MAX layer.

Main techniques
  • opportunistic listening: overhear packets even if they are not destined for you, send reception reports to tell others which packets you received (broadcast, extra transmission or piggy-backed on another)
  • opportunistic coding: "maximize the number of native packets [i.e. not coded ones] delivered in a single transmission, while ensuring that each intended nexthop has enough information to decode its native packet [i.e. send A XOR B XOR C only if the nexthop has already two of the packets A, B, C so that it can decode]." Here the nexthop is picked to be the packet of the head of the queue, so that there is no delay introduced (though potentially reordering)
  • learning neighbor state: leverage probabilistic knowledge for coding decision when you lack feedback from reception reports
Refinement
  • have separate queues for different packet lengths to avoid excessive padding
  • MAC allocated bandwidth alters the dynamics benefinically
  • no delay: do not wait for coding opportunities before sending packet
  • never "code together packets heading for the same nexthop", therefore maintain virtual queues for each nexthop (and packet length)
  • reordering agent to fix reorder
  • details see pseudo code in paper
  • pseudo-broadcast: uses MAC unicast to send and puts other nodes into promicious mode, this enables MAC's backoff and ACK mechanism
Results
  • random UDP flows: 3x4 increase of throughput (even when congested)
  • TCP, gateway to Internet: 5% to 70% more throughput depending on upload/download ratio
  • hidden terminals are spoilers for TCP

ExOR

Sanjit Biswas, Robert Morris, "ExOr: Opportunistic Multi-Hop Routing for Wireless Networks"

Departure from traditional wireless routing
  • do not model wireless network as point-to-point links
  • use the broadcasting nature of wireless
  • Idea: to route packet from A to B, broadcast packet, see how far it went, i.e. which node N received it and is closest to B, repeat process from N
Example
  • Take sequence Src-A-B-C-D-E-Dst
  • It would be great if Src sends it, then the furthest station (which received the packet correctly) forwards it and so on
  • this works better because at most the probabilities are known which stations are likely to receive the packet, the routing decision is deferred until the packet is send and it is known which links worked and which didn't
  • each forwarding step is an independent random event
  • if there are parallel structures, there are independent chances which link will succed, hence the total chance of any of links succeding will be higher

Challenge
  • algorithm must find a node N or a set of nodes N which will forward the packets, all other nodes who received the packet will drop it
  • if this algorithm gives no such node N, the packet is lost, is the algorithm is likely to give more than one such node N, there will be a chain reaction flooding the network wasting capacity: robust algorithm giving 1 in almost all situations
  • algorithm is distributed and has to arrive at consensus
  • has to have little overhead
Proposed solution
  • collect packets together into a batch
  • each node maintains a routing table which has path length (metrix e.g. ETX) from neighbors to destination
  • a node uses the table to determine and prioritize (by closeness to destination) a list of forwarders (small to keep cost to arrive at agreement low)
  • the highest-priority forwarder will broadcast all packets in the batch it received correctly, it will include the list of these packets as "batch map"
  • the next forwarders will send packets which were not acknowledged through the "batch map" of higher priority nodes
  • traditional routing as fall back mechanism for remaining 10% of packets
  • scheduler so that only one node sends a time
  • link state protcol to give input on forwarder list algorithm
  • implemented in Click toolkit
Results
  • end-to-end throughput boosted by around 2 (even higher for multi-hop routes)
  • but bad TCP performance (fixed by split connection)
Criticism
  • algorithmic overhead
  • promicious mode: extra energy?
  • there is no use on allowing only one station to send if the stations are so far apart that no middle man can hear both stations, scheduler should take this into accoung

Monday, October 6, 2008

Four Ad Hoc Routing Protocols

Josh Broch, David Maltz, David Johnson, Yih-Chun Hu, Jorjeta Jetcheva, "A performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols"

Protocols
  • Destination -Sequenced Distance Vector (DSDV)
    • hop-by-hop protocol
    • sequence numbers to prevent aging of routes
    • each time step, every node sends a full dump of its routing table (destination, next hop, last sqn, metric) to its neighbors with route to itself attached as routing advertisement
    • routes are imported if they are newer (by sqn) or have better metric and not too old (? I did not really understand the WST fudge factor in this protocol ?)
  • Temporally Ordered Routing Algorithm (TORA)
    • hop-by-hop protocol
    • assigns height per node and per each destination
    • packets are routed "downhill" to destination
    • routes are requested through "QUERY" which initiates "UPDATES" which will set the heights
  • Dynamic Source Routing (DSR)
    • source-routing
    • route requests with unique ID flooded, intermediate nodes append own address to request re-broadcast, flooded route requests are repeated with increasing back-off time and TTL
    • destination replies to each route request with "route reply" containing the route sent back to originator of request along the reverse route
    • store overheared route replies in link cache, run Dijkstra's algorithm for source routing, send route request if no route in link cache
    • send route error back to origin of source-routed packet if 802.11 ACK fails, source has to recover
    • maintain blacklist for detected unidirectional links (per node)

  • Ad Hoc On-Demand Distance Vector (AODV)
    • hop-by-hop routing
    • combination of DSR and DSDV

Simulation
  • ns-2 network simulator extended to model MAC (RTS/CTS ACK) and physical layer (delay, capture, carrier sense, transmission power, antenna gain, receiver sensitivity) behavior of 802.11 and node mobility, ARP, packet buffering
  • ns is discrete even simulator
Performance metrics
  • Goal: "measure the ability of [...] routing protocols to react to network topology change while continuing to [...] deliver data packets [...]"
  • 50 nodes on 1500mx300m space, 210 different scenario files, CBR sources
  • No TCP measurements (this is probably a more relevant number as TCP most deployed, but maybe the TCP dynamics has to change to accomodate different link layer characteristics)
Results
  • DSDV-SQ fails to converge for high mobility, has high loss rates then
  • TORA has largest overhead (by almost 10 for high mobility), DSDV-SQ has almost constant overhead independent of number of sources and degree of mobility
  • TORA has high loss rates and bad overhead when >30 sources
  • DSDV-SQ and DSR give slightly better paths

The ETX Path Metric for multi-hop wireless

Douglas S.J. Dr Couto, Daniel Aguayo, John Bicket, Robert Morris, "A High-Throughput Path Metric for Multi-Hop Wireless Routing"

Computation of ETX metric
  • total metric=sum of the links
  • for one link, metric 1/(forward delivery ratio*reverse delivery ratio) (probability that packet was received, probability ACK was received)
  • estimation through 1 probe/sec broadcast by each node with jitter to avoid collision
  • gives expected value of total transmissions (with retransmissions) of packet along that path
Objectives (motivated by measurements of throughput through different routes)
  • accounts wide range of link loss ratios
  • accounts asymmetric loss ratios
  • accounts interference between successive hops of multi-hop paths (one can't send til one has completly received)
  • tends to minimize spectrum use, overall system capacity, energy
Results
  • Tested with two modified routing algorithms: DSDV and DSR in office environment
  • significant higher throughput through multi-hop routes
  • algorithm does not account different loss ratios for different packet sizes
I was wondering whether (when there several packets on its way) the network actually becomes a pipeline which can work (at least) partially parallel and therefore the ETX metric does not optimal for max throughput.
I also still do't understand why the graphs in figure 6 cross: this clearly is a contradiction to the fact that the best route should perform equally or better than any other route, so why does its graph suddenly lie above another route?

Wednesday, October 1, 2008

Roof Network

John Bicket, Daniel Aguayo, Sanjit Biswas, Robert Morris, "Architecture and Evaluation of an Unplanned 802.11b Mesh Network"

I really liked that hand-on project. Ashima has written a nice summary for it on her blog.
I will only write about a couple of details I found interesting about the mechanisms:
  • standard 802.11b hardware with RTS/CTS disabled, really? What is the benefit of disabling RTS/CTS?
  • single-channel
  • self-configuring network on preinstalled Linux boxes
  • network is a mesh with many routing choices
  • routing protocol: each node maintains partial matrix of link metrics between pairs of nodes, each node uses Dijkstra's algorithm for source-routing (not scalable)
  • link metrics communicated through 1. packet header when forwarding, 2. flood queries when route to destination is missing, 3. nodes overhearing responses to flood queries
  • probing of link quality through periodic broadcasts
  • link metric given by adding inverses of throughput
  • overriding default selection of transmit bit-rates of wireless hardware for optimization
I found interesting about the evaluation the detailed figures on e.g. the relation between throughput and distance, especially the figures on how the network performance drops when nodes are dropped.

I was missing a discussion on packet collisions which is relevant because of single-channel and omni-directional antennas.

Modeling Wireless links for Transport Protocols

Andrei Gurtov, Sally Floyd, "Modeling Wireless Links for Transport Protocols"

Interesting idea: cross-layer communication

Motivation
  • wrong assumptions about wireless links yield to bad design of link layer and transport layer protocols with low performance (the paper shows examples like tight assumptions on inter-packet delays to distinguish between loss and congestion)
  • accurate evaluation of mechanisms like Forward Error Correction, link-level error recovery
  • discuss the tussle whether changes should be implemented in the link layer or transport layer and which one should consider the dynamics of the other one (e.g. implementation of error recovery on both layers might yield to unnecessary retransmissions due to competing timeouts): there is interplay between the two layers
  • TCP assumes that packet loss means congestion
  • TCP Reno assumes that Dup ACKs mean packet loss (does not allow (any) reordering)
  • Metrics: goodput, also (for cell phones) power consumption
Types of wireless networks
  • wlan
  • wide-area cellular links (GSM, UTMS)
  • satellite links
Other aspects
  • network topology
  • shape of traffic (e.g. short Web requests versus Megabyte file sharing)
Link characteristics (for each one, the physical cause, the direct impact on the link layer and indirect impact on the transport layer is explained and a model is discussed)
  • error losses and corruption (FEC and limited number of retransmissions on the link layer might not hide them in really poor radio conditions, losses due to handovers between stations might not be recoverable on the link layer): modeled by probabilistic packet dropping, might have a certain distribution or state
  • delay variation (messes up delay-based congestion algorithms, rate-based protocols more affected than window based): model delay spikes by suspending data transmission in simulation
  • on-demand resource allocation (a radio frequency is only allocated after a link layer buffer has passed a threshold or timeout, channel allocation delay causes TCP timeouts): modeled by additional delay at packet arrival to queue
  • bandwidth variation (timeouts, congestion and underutilization)
  • asymmetry in bandwidth (congested TCP ACKs), example satellite 10-100x difference
  • Queue Management (used to accomodate bursty traffic, can cause high queueing delay and poor loss recovery (high RTT)): simulate tail-drop or RED
  • effects of mobility: deeper understanding of inter-system handover necessary
Impact
  • currently: link layer designed to deal with TCP's bad performance under packet reordering or loss (TCP could be changed), TCP designed to work over exisiting link layers (not necessarily having explicit loss notification)
  • explicit loss notification instead of timely link-layer recovery
  • buffers to fix reordering or make TCP robust against reordering
  • reduce delays on link layer or make TCP more robust
  • cross-layer communication