brho's Articles, Page 1 of 2
GRUB is the GRand Unified Bootloader. For those unfamiliar, a bootloader is a critical piece of software used when a computer turns on. Its job is to load an operating system. The bootloader resides on a disk of some sort (floppy, hard) and is called by the BIOS, which is the real low-level program that runs on startup. GRUB is installed at a specific location on these devices.
Image files are byte-for-byte representations of block devices, such as a hard disk or floppy disk. They can be used for a variety of things, such as backup, offline investigation, or virtual machines. I was using the latter (specifically, Bochs and KVM). These programs act like a computer within a computer, and take an image file to be the disk for the virtual machine.
A Reliable Multicast Framework for Light-weight Sessions and Application Layer Framing
- - - - - - - - -
This is an attempt to build a general reliable multicast implementation on top of IP multicast. It attempts to leave many of the decisions to the application layer (in accordance with the E2E principle) and provide only the basics all MC implementations need. It’s fundamental flaw is that it relies on IP multicast, which no one uses.
Highlights include Receiver-based reliability and Application Layer Framing. Sender-enforced reliability won’t work for a variety of reasons (such as ACK implosion, the responses you get from 1000 other users). App layer framing is about requesting chunks of app-specific data, instead of just a byte stream.
A Delay-Tolerant Network Architecture for Challenged Internets (DTN)
- - - - - - - -——
Not all networks look like the Internet. Our current network stack is built on the assumptions: an end-to-end path exists, it has reasonable RTTs, and packets will arrive with reasonably high probability. These assumptions do not hold for may interesting networks, such as satellite networks, ad-hoc networks, sensor networks, poor-people networks, etc. One interesting network they use is a vehicle, like a bus, that drives from A to B. It physically moves packets around, and when a node is in range of the bus, it can send a load of packets to be delivered to the other end – very much like the postal service.
End-to-End Internet Packet Dynamics
- - - - - - - - - - -—
This is one of those measurement papers that bridge the gap between facts and intuition. It was done in 1995, and consisted of TCP communications between 35 sites. Initially, the paper started out a little dry and boring, but has a lot of interesting results.
- Out of order packet delivery is not that big of a deal, possibly because our current fast retransmit threshold for dups is conservative. More research is required to know if these values should be tuned.
- Packet corruption happens on 1/5000 packets (in 1995). Given each has a 1/65536 chance of being accepted, that means 1 in 300million packets are given to the application layer with no errors… This happens quite a lot, which leads in to discussions of E2E and larger checksums. One thing I am not convinced of is the 1/66536 odds of a corrupted packet being accepted. I know there are 2^16 choices for the checksum, but I’d have to be convinced that a corrupted packet has an equally likely chance to generate all checksums. Without thinking about it too much, it seems like it could be more complex than just a one in n chance. Then again, this is Vern we’re talking about.
- Packetloss: He talks a lot about ACK packetloss, which does not adapt to current network conditions. When I first read this, it seemed wrong since the ACKs are part of the self-clocking of TCP. But notice that networks are not symmetric, and one of Vern’s results are that packet losses from the forward (data) and reverse (ACK) paths can be independent.
Middleboxes No Longer Considered Harmful
Middleboxes are things like NAT boxes or firewalls. They violate basic tenets of the Internet, specifically that every node is uniquely identified and that network devices should not process packets. This paper presents and architecture (DOA – Delegation-Oriented Architecture) to enable the use of these middle boxes in a way that does not violate these tenets.
The main idea is to decouple the IP address from the host ID, called the EID (endpoint ID). The EID is independent of network topology. IPv6 is another approach to uniquely identifying an endpoint, but it is not independent from the topology. The authors downplayed the benefit of IPv6; it does get rid of the need for NAT-style middleboxes. Still, there are other things such as mobility that benefit from DOA’s location-independence that IPv6 lacks.
Development of the Domain Name System
This paper discusses the issues and motivations for the design of DNS. The main ideas are hierarchies and caching. The old way was to use a centralized text file (HOSTS.TXT), but this was in violation of one of the principles of the Internet – distributed management. Plus, the system was slow to respond and did not scale. DNS is about partitioning the name-space database, and it made sense to do so across the same organizational boundaries that make up the internet.
Chord: A Scalable P2P Lookup Service for Internet Applications
Chord is a distributed lookup service that maps keys on to nodes. It’s sole purpose is to perform a lookup function. Its benefits are that each node only needs to know about a subset of the total nodes to route queries, perform lookups, etc, which enhances its scalability.
Some specifics: it uses a ring logical topology to perform the mapping of keys to nodes with the assumption that keys will map to whatever node has the same or greater value as the keys value on the ring. It uses exponential/logarithmic algorithms to determine which nodes each node is aware of, which helps bound lookup and recovery time to log(n) or log^2(n). This subset of nodes a given node is aware of is stored in a "finger" table, of which the direct successor is the first finger. Check out Figure 3 or draw a picture with exponentially spaced neighbors. One other thing to consider is that these algorithms often give the ID of the next node. If there isn’t a node at that exact point, you round to the next node. It is possible that one node might appear as several successive finger entries.
Resilient Overlay Networks
RONs are small scale, application-centric networks that ride over IP that improve redundancy and performance for their applications. They are really impressive. Their main improvement comes from their small scale, which is also their main limitation. BGP is designed to scale well; it dampens route changes to prevent oscillations and hides many topoligical details so that the large-scale algorithms can complete. RONs typically involve far fewer nodes, and they are capable of using link-state routing algorithms to determine the best paths to take.
A typical scenario is that an application has several nodes that want to communicate (file share, virtual teleconference, etc). They maintain routing information about how to get to one another and the qualities of the links (latency, throughput, loss). Different applications have different requirements, so each RON will pick a route using the link-state measurements based on its needs. If an IP-route fails, RON will quickly detect it (the nodes constantly check their links) and route around the failure. It will send packets to another RON node, which will forward them to the real destination. The sort of tricks RON pulls cannot be done on the Internet due to the scale of the system. RON’s small scale gives it added flexibility.
On Power-Law Relationships of the Internet Topology
- - - - - - - --
First – read up on Power laws (Wikipedia). They basically are scale invariant relationships that can be used to express meaningful things in the long tail of the distribution. This is where the "interesting" things happen, esp in the Internet’s topology.
This paper was about using power laws to describe the topology of the internet. They present a few of these rules that they insist will remain somewhat fixed over the development of the Internet – barring any major technological change. These rules link features such as the degree of a node to the number of nodes with that rank.
Both of these papers are about networks of very small, power-constrained sensors and their interactions. These devices contain sensors, limited processing ability, and very tight power budgets. Both schemes attempt to limit the amount of communications, since radio transmissions are extremely expensive.
While they sound impressive, neither have ended up being worth much. Based on what we talked about in class, sensor networks have not delivered some of the crazy promises people imagined. Instead, the trend over the last few years was to just get them to work, and nearly every deployment that actually worked has only done collection and dissemination. Anything more complex simply hasn’t been worth it. Yet.
ExOR: Opportunistic Multi-Hop Routing for Wireless Networks
- - - - - - - - - -—
This is awesome, though I wish it scaled better. ExOR takes advantage of the broadcast nature of wireless. Instead of trying to hide the fact that multiple nodes share the carrier, it benefits from it. The general idea is for a node to broadcast a packet to a set of potential next hops, and the best of the next hops forwards it on. This flexibility allows ExOR to handle transient failures as well as take advantage of lucky low-chance transmission paths. ExOR is also more resilient than other algorithms in that it does not rely on a specific link. A traditional routing scheme would fail or need to retransmit heavily if the link it determined to use happened to miss several frames.
A High-Throughput Path Metric for Multi-Hop Wireless Routing
- - - - - - - - - -——
This paper presents a metric for multi-hop routing. Their metric minimizes the expected total number of transmissions. One packet over two hops equals two transmissions. If a packet needs to be retransmitted, that counts too. This is in response to the problems with the old "min hop count" metric. Vanilla min hop tended to ignore many things their model accounts for, such as asymmetry and delivery ratios. They have examples of networks where the highest-throughput path is not always the min hop.
Modeling Wireless Links for Transport Protocols
- - - - - - - -——
I like the general message of this paper: your models are crap. Many people had been using simulations making a wide variety of assumptions, and this paper is the wake up call. Real wireless networks can behave quite differently than researchers assume, leading to possibly incorrect results.
The authors discuss several issues, including the actual effects of error loss/corruption, delay variation, packet reordering, etc. Some are more valuable than others. For instance, the section on asymmetry in bandwidth and latency was rather weak, and they acknowledged a few others were not a big deal. Still, the message is clear – be more realistic.
MACAW: A Media Access Protocol for Wireless LANs
- - - - - - - - - -
This paper discusses many of the issues with media access specific to wireless LANS. The main differences between wireless LANs and wired LANs are congestion is location dependent and different stations can hear different sets of other stations.
They have some good ideas for this new environment, specifically the declaration of intent to broadcast so that interested parties can avoid collisions. However, for every nice idea they have, they come up with a scenario in which it fails. For instance, if a station hears an RTS but not a CTS, they say that station can transmit, since it will not interfere with the CTSer’s reception. However, they add in ACKS, and now they can’t transmit since they would squelch the ACKS. Their answer is the Data-Sending packet. But this isn’t enough for all cases, so they invent the RRTS message.