Power Laws again

I just read that wars are also scale-free: the distribution of number of deaths in a conflict follows a power law with coefficient 2.5.

This result was found by Neil Johnson (Miami). http://www.dradio.de/dlf/sendungen/forschak/885102/

MapReduce Again!

Matei Zaharia, Andy Konwinski, Anthony D. Joseph, Randy Katz, Ion Stoica, "Improving MapReduce Performance in Hereogenous Environments"


Intro

• Hadoop is an open-source implementation of Map Reduce (and distributed filesystem?)
• new deployment: virtualized environments, datacenters with several generations of hardware display heterogenity
• want to optimize scheduler to finish fastest without wasting unnecceary resources
  

Scheduling the next empty task slot

• Priority 1: failed tasks
• Priority 2: non-running tasks
• Priority 3: Speculative execution

Speculative execution, the native Hadoop way

• Speculative execution depends on progress score [0,1] devided equally between copy, sort and reduce phase.
• process is marked straggler if its progress <>
• a task of a straggler is given to another machine (but at most one speculative execution) based on data locality

(underlying assumptions see 2.2)

New speculative execution: LATE=Longest Approximate Time to End

• Idea: speculatively execute the task that will finish fathest into the future (greatest opportunity to save time)
• different methods for estimating time left: basic is linear extrapolation from progress score
• speculative tasks scheduled on fast nodes (through threshold how much work a node already has performed)
• rank tasks by time finished, schedule speculative task if it is likely to finish before other node
• refinements to account for costs of speculative execution: SpeculativeCap on number of concurrent speculative tasks and SlowTaskThreshold

Result: LATE reduces running time by a quarter to a half

Policy-aware Switching Layer for Data Centers

Dilip Antony Joseph, Arsalan Tavakoli, Ion Stoica, "A Policy-aware Switching Layer for Data Centers"

Ideas

• shares some ideas with "Middleboxes no longer considered harmful": traffic can be directed to traverse middleboxes without the middlebox being on the physical path
• but: differs because it is not introducing new properties to IP, but instead replaces Layer II by PLayer
  
• usual approach: put middleboxes on the physical path, hard to configure, possibly multiple physical paths between two nodes, different traffic supposed to go through different middleboxes
• new approach: among Layer II switches, add (policy-aware) pswitches which route the packets through the middleboxes on Layer II based on policy specification
  

Goals

• Correctness: Traffic should traverse middleboxes in the sequence specified by the nework administrator
• Flexibility: sequence of middleboxes should be easily reconfigured
• Efficiency: traffic should not traverse unnecessary middleboxes

Principles

• Separating policy from (physical) reachability
• taking middleboxes off the physical network data path
• policies: [Start,(5-tuple traffic selector)] -> sequence
• translated into rules ([Previous Hop, Traffic Selector]: Next Hop) which is used by pswitch
  
• policy schemas (versioned) are created by administrator and pushed onto the pswitches

Mechanisms

• decoupling switch core (can use traditional core, usual techniques to learn MAX addresses and build spanning trees) from policy core (where the new rules are applied) with additional failure detection
  
• encapsule Ethernet frames in Ethernet-II frames (which contain policy version): the algorithm to build the spanning tree needs another Source-MAC (a more physical one) than the FireWall (a more logical one)
• SrcMacRewrite to decapsulate Ethernet-II frames before entering (legacy) middlebox
• in some situations pswitches require per-flow state
  

Other

• implementation in Click, results
  
• detailed discussions on various topologies
• formal analysis

I like this more than the "Middleboxes no longer considered harmful" because

• it integrates better into exisiting layerII structures instead of adding yet another identifier
• in "Middleboxes no longer considered harmful" nodes had to be configured to use the off the physical path FireWall, it was unclear how an IP packet destined for a computer behind a off-the physical path Firewall will actually be hindered from reaching the computer. In this paper this is clear.

I got a bit confused because MAC addresses are used in two different ways, onc address is used for forwarding between pswitches, but another can be used when the packet is handed to a middlebox. I think the paper should have given these MACs different names, if possible.

Internet Data Transfer

Nirja Tolia, Michael Kaminsky, David G. Andersen, Swapnil Patil, "An Architecture for Internet Data Transfer"

Principles

• separating content negotiation from data transfer (motivation: 70% of Internet traffic is bulk transfer)
  
• common interface between various applications and transfer service architecture, application developer does not need to reinvent transfer service for each new application
  
• Figure 3 explains how the application works in the DOT framework. The application calls the GTC for the data transfer

Data transfer methods can even include physically moving hard disks. One benefit is that the same data can be cached across different applications like Web and electronic email.

Delay Tolerant Networks

Kevin Fall, "A Delay-Tolerant Network Architecture for Challenged Internets"

This paper is abstract. It suggests a overlay network which is running on networks different from the usual Internet and hence providing a very different service model. But there is no implementation (except one mentioned in one sentence in the conclusion) and no results section, no new algorithms.
I wonder whether the picture in Figure 1 really is a typical example: are there really applications where challenged networks are used for transit, or aren't most applications (e.g. sensor networks, satellite connections, ...) just having challenged networks at one or both ends?
And regarding the US Postal System as model for challenged Internets: looking back at my experiences so far, I kind of doubt whether this is a good idea...

Targeted networks

• Terrestial Mobile Networks
  
• Excotic Media Networks (e.g. deep space, acoustic links)
  
• military Ad-Hoc Networks
• Sensor Networks

Violated Assumptions

• E2E path exist, no disconnection
  
• max RTT not excessive, reasonable queuing time
  
• drop probability <<>

Possibilities to deal with the violated assumptions

• fix link-layer
• attach challenged networks at the edge of Internet through proxy, e.g. sensor networks, protocol boosters (e.g. HTTP proxy for satellite connections)
• electronic mail (mostly reliable, likely failure notification)
• DTN
  

New principles of DTN

• Message-switching (instead of packets)
• Regions with DTN gateways inbetween
• name includes region and entity name within that region
• several services (motivated by USPS)
• path selection and scheduling, trying to predict when the next contact to a certain region takes place
• custody transfer and reliability, e.g. if a message is sent from one node to another node, does the old node need to keep a copy until confirmation the message was delivered
• convergence layers
• time synchronization
• congestion and flow control

Internet Measurements

Vern Paxson, "End-to-End Internet Packet Dynamics"

I found this paper hard to read, not because it is badly written, but because it discusses the measurements and results in extraordinary depth, discussing the measured effect, coming up with potential explanations, possible effects on higher layers and even suggestions for implementations. The lecture on Thursday luckily turned my frustration when reading the paper in admiration for the pioneering role Paxson played in introducing internet measurement methodology and the enormous body of results he produced.

Methodology

• large-scale experiment: 37 sites, N to N bulk transfer, done at Dec 1994 and 1995
  
• TCP bulk transfer (versus ICMP packet probing): 1. this is how most Internet traffic really looks like, 2. TCP adapts to avoid unduly loading the network
• TCP measurements intertwine network and transport, tcpanaly separates these behaviors, TCP implementation specific (Vegas versus Reno, Windows NT versus Linux), tcpanaly can not recover time series analysis
  

Measurements

• Pathologies: Reordering (on certain paths as high as 36%, due to route flaps), Replication (rare) and Corruption (1 in 5000 packets)
• Bottleneck bandwidth (difficult to estimate, basic idea: send two consecutive packets, at bottleneck bandwidth, the second packet has to wait for the transmission of the first packet, limited by time resolution, refined through bunches)
• packet loss (distinguishes between data and ack loss, loss at loaded and unloaded links) and effect on TCP (causes of a redundant retransmission: unavoidable, coarse feedback (no SACK), bad RTO)
• packet delay (due to queing/bandwidth, but even compression observed)

Conclusion

• Justification of measurement (TCP) methodology over other measurement techniques
• wide variety of path properties
• underlying assumptions about the network often broken
• robust TCP implementations can work non the less
  

X-Trace

Rodrigo Fonseca, George Porter, Randy H. Katz, Scott Shenker, Ion Stoica, "X-Trace: A pervasive Network Tracing Framework"

Motivation

• current diagnostic tools limited to one particular proctocol, e.g. traceroute
• need for comprehensive view of the system's behavior
• complex systems: e.g. wikipedia has different sites, web caches, DNS round-robin, load balancers, web servers, database servers (and memcached)
• tracing across different administrative domains needed

Ideas and design principles

• integrated tracing framework
• network protocols modified to propagate X-Trace metadata
• works inter-layer
• works inter-Administrative Domains
• decouples client of application and recipient of tracing data (Design principle 3), destination part of the X-Trace metadata
  
• trace initiated by inserting X-Trace metadata by user application or network operator
  
• trace identified by task identifier
• X-Trace data send to report server (can be client application or delegated server)
  
• X-Trace constructs task tree offline, two axis: one across "layers" (an event causes another event in lower layer), one across "time" (an event causes another in the same layer), each node in the task tree has an ID, children link to their parents
  
• Design principle 1: trace request are sent in-band
• Design principle 2: trace data are sent out-of-band
• ASCII report format
• report library, report collection thorugh e.g. Postgres
• visualization of task tree
  

Deployment

• API for application has pushNext() and pushDown() to propagate X-trace MetaData across the two axis, device reports information accessible at its own layer, can include additional information like load
  
• gradual deployment: for legacy clients, devices in the network can add X-Trace metadata
• retrofitting X-Trace into exisiting applications faces difficulties: change to various protocols (IP options, TCP, HTTP headers, SQL), partial deployment impairs ability to trace parts of the network, lost trace reports can be interpreted as false positives
• certain request topologies cannot be captured, e.g. requests spreads through the network and rendezvous at a node
• unique() function returning identifier for task tree not specified in paper
  

Uses and Experiences

• low performance overhead
• Web request and recursive DNS queries
• Web hosting site (LAMP), user could intiate traces through JavaScript/PHP library
• overlay network
• Tunnels, ISP connectivity
  

I really liked the framework this paper suggests. I think it is very useful. Though there has been a lot of experience, scalabe websites are still non-trivial to setup, still require some manual work to tune and integrate caches, and work across a lot of different layers as mentioned in the introduction. Some difficulties not mentioned in the introduction are: there are even more caching layers like SQL query cache and memcache, relational databases don't scale and huge websites shard the data across multiple machines, Brewer's theme on performance versus consistency (a website is not truely transactional, just enough so that the users don't preceive it as bad, but when a user sees it, it is hard to track down). This paper introduces the debugging tool I am aware of which is addressing all these things together.
The only thing I would add to this framework is the ability to send encrypted X-Trace data.

Post-lecture: Middleboxes done right?

Last lecture on Thursday again ended in a very interesting discussion.

Randy commented on my last post: "I always like the format you use for these comments! Any thoughts on whether the idea of outsourcing middlebox functions makes any sense?"

Here is my answer:
Yes:

• framework provides the same functionality without breaking the two principles mentioned in the introduction
• performance will be competitive only if the middlebox will be close or on the network path, i.e. where the middlebox is anyway
  
• user benefits from being able to choose between the middlebox service and direct service

No:

• extra conceptual overhead
• how to gradually deploy?
• because middlebox is not phyisically on the network path blocking IP packets, certain attacks on computers are still possible
• user needs to configure their computer to use middlebox service (half will forget and leave the network vulnerable)
• middleboxes might be deployed to actually prevent certain kinds of services, with middlebox being outsourced this can be circumvented
• NAT on traditional boxes offer anonymity, invisibility from the outside
  

Middleboxes done right?

Michael Walfish, Jeremy Stribling, Maxwell Krohn, Hari Balakrishnan, Robert Morris, Scott Shenker, "Middleboxes No Longer Considered Harmful"

Benefits of Intermediate Network Elements like NAT, firewall, transparent cache

• NAT: private IP spaces allow protection, more hosts than available IPs
• Fiewalls prevent attacks on endhosts
• security, flexibility, convenience
  
• exist for a "important and permanent reason"
  

They violate the following internetworking principles

• 1. "Every Internet entity has a unique network-layer identifier that allows others to reach it."
• 2."Network elements should not process [the payload of IP] packets that are not addresses to them."

Consequences

• "scorn" and "dismay"
• halts spread of newer protocols, P2P systems
• layer violation, rigidity in network infrastructure, may not accomodate new traffic classes

New Idea: Delegation-Oriented Architecture (DOA)

• implement intermediaries without violating principles
• Extra DOA Header between IP and TCP
• Firewall does not need to be in the "physical path", but hosts can "outsource" to "off-path" hosts, end host has primitive to choose a machine to delegate NAT or Firewall functionality to
  
• DOA header has: 1. references to persistent host identifier (in globally flat name space, stays with host even when IP changes), 2. a way to resolve these references to delegated machine
• does not reqires change to IP (routers), allows incremental deployment
• but cannot: circumvent tenet-violating middleboxes (e.g. by censorious government)
• persistent host identifier= EID (endpoint identifier) is 160 bit, contains cryptographic meaning
• mapping service: EID -> IP of delegated host, more EIDs (to chain several intermediares, loose source-routing)

Internet Indiretion Infrastructure

Ion Stoica, Daniel Adkins, Shelley Zhuang, Scott Shenker, Sonesh Surana, "Internet Indirection Infrastructure"

What kind of flavor of network is this?

• It is a little bit like circuit-switched networking (allowing packet processing on top of it) in the sense that the receivers set up triggers which will then identify how a flow will be routed through the Internet.
• It is not at all like Active Networks because the "routers" are not "programmed" by the senders through injecting code into the packet, but actually by the receivers through setting up triggers.
• It uses DHTs to load balance.
  

Goals

• generalize Internet P2P communication abstraction
• implement features like multicast, anycast, mobility on application layer (challenging on IP layer, previous proposals provided disjoint solutions for each problem separately). load-balancing
  
• data processing (H.263->MPEG conversion) while routing
  
• decoupling the act of sending and receiving through rendezvous-based communication abstraction
• receivers can control routing, can built trees for multicast
  

Concepts

• each packet has an identifier, receiver asks infrastruction for delivery of the packets with a given identifier
  
• receiver addr expresses interest in identifier id through triggers (id,addr)
  
• triggers are matched to packets by largest prefix overlap, have to exceed exact-match threshold
  
• sending and receiving hosts don't need to know each others identity or location
  
• indirection, e.g. home agent in Mobil IP
• private versus public identifier, e.g. for flows versus name lookups
• Advacned: stack of identifiers is a list of identifiers or addresses written as id_stack. A trigger can contain stacks (id,id_stack), a packet can contain a stack (id_stack,payload)
• soft-state of maintaining triggers (and possibly redundancy)
  

Main Ideas

• identifiers map to unique i3 node through Chord, inheriting through Chord Robustness, Scalability, Efficiency, Stability
  
• senders send packet to i3 node corresponding to identifier
• receivers install triggers on the i3 node corresponding to identifier
• i3 nodes routes packets matching triggers to receiver
• Advanced: if a trigger has a stack, a packet can be routed to another identifier (e.g. i3 node) who will then essentially further route it down the stack, e.g. loose source routing. The algorithm is given in Figure 3.
• Advanced: identifiers can be routed through applications, e.g. HTML-> WML transformation

Details and further ideas

• server selection through least significant bits in identifier, random for load-balancing, through geographic properties for CDN
• private and public triggers, example in 4.2
• scalability because per-flow state disributed among many servers
• avoiding hot-spots in multicast through pushing copies of triggers
• i3 proxy allows legacy UDP-applications

DNS more contemporary

Jaeyeon Jung, Emil Sit, Hari Balakrishnan, Robert Morris, "DNS Performance and the Effectiveness of Caching"

The paper makes and mentions a lot of interesting measurements and results. There are two prime investigations:

• overall DNS performance (from a user perspective and from an amount of traffic perspective)
  
• the impact of caches and TTL. The motivation comes from the dichotomoy: load-balancing applications respond with queries with short validity limiting the use of cache BUT the scalability of DNS is said to arise (besides the hierarchical organization) from queries answered from cache
  

Methodology

• collect Internet traces: DNS packets and TCP SYN/FIN/RST packets
  
• trace through 60 second window the process of iterating lookups until the answer is foun
• track TCP connections associated to a DNS query
• group clients' IP addresses and simulate a common DNS cache for them

Performance results

• distribution of types of DNS lookups (mostly A records hostname -> IP address)
  
• half of the DNS lookups are associated to a TCP connection
• DNS query latency has median of 1/10 second but a significant portion takes up to 10s of seconds, distribution of number of referals
  
• 70% of the querries do not hit a root/server gTLD (i.e. cached NS improve performance and greatly reduce load on root servers)
• a successful DNS query needs on average ~1.3 packets
• unanswered queries (due to e.g. NS records to no longer existing servers) might cause substantially more traffic per query due to loops and retransmissions

Effect of Caching

• name popularity is Zipf distribution, 10% of names account for 68% of answers + long tail
  
• current TTL distributions
• most caching benefit is achieved with 10-20 clients per cache
• most caching benefit is achieved for TTL~several minutes for A records of Webservers (I think though that in Figure 13, they should plot the cache miss rate. A hit rate of 97% and 99% sound the same, but mean a three times lower miss rate, but that implies we can serve 3 times as many clients from the same e.g. gTLD server)
• effect of eliminating A-record caching, per-client caching...

Concluding Remark: "The reasons for the scalability of DNS are due less to the hierarchical design of its name space or good A-record caching (as seems to be widely believed); rather, the cacheability of NS-records efficiently partition the name space and avoid overloading any single name server in the Internet." I think that is a rather provocative statement. If you cache no single IP address, you have to start every query at a root server, so it is not scalable, so how do I have to understand their remark?

I think the numbers in the abstract are fairly useless unless one has read the paper, because only later in the paper one finds the answers to the following questions:

• it is mentioned what fraction of lookups are unsuccessful: but are these network failures due to overload or dropped packets (which would be bad) or just because a user typed a domain name wrong (for which we expect the lookup to result in no answer)?
• is the cache miss rate meant for a query destined for a root, gTLD or domain server? E.g. is the conclusion we can draw from the measurements that if we didn't have caches anymore, suddenly the 13 root servers would be just horribly underscaled, or that the name servers for some popular sites would just hit a little more load?
• The browser also has cache for DNS entries, so is the cache miss rate with respect to each TCP connection the browser makes, or just for every DNS lookup the browser cannot answer itself?
  

One thing which doesn't make sense to me is the fact that root servers get more lookups than gTLD (TABLE VI).

DNS Intro

Paul V. Mockapetris, Kevin J. Dunlap, "Development of the Domain Name System"

Basic design assumptions

• provide at least all the same information as hosts.txt
• allow the database to be maintained in a distributed manner
• no obvious size limits for names, name components, data associated with a name, etc.
• interoperate across the DARPA Internet and in as many other environments as possible
• tolerable performance
• Lean service versus general distributed database

Design

• Hierarchical organization (zones) and namespace
• Caching, negative caching
• Resource Record: Type, Class, TTL, data of variable types
• servers and resolvers
• root servers (with rates of 1 query/sec in 1988)
• datagram (UDP) access

Things I was surprised about

• Pre-DNS: hosts.txt was used for quiet a long time
• it took time to convert more hosts from pre-DNS hosts.txt to DNS and delegate domains
• the importance of Berkeley UNIX's bind
• applications had to be modified to handle transient failures when using DNS instead of hosts.txt lookups
• DNS was intended to be far more general to lookup up names of anything. Today it is used almost exclusively to map "hostname <-> IP (+MX)"
• in the early days, people controling a domain didn't necessarily have the expertise to configure DNS correctly (and I thought in the good old days, only people who knew what they were doing had access to the Internet)
• RR had Class field which would allow different namespaces for DARPA net, ISO directory service, ...
  

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.
  

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
  

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?
  

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.