MapReduce scheduling

MapReduce is fairly new and Hadoop implementation, as described in the paper , seems rather primitive and has a lot of room for improvement. I am not saying the creators of Hadoop did not do their job, but rather systems like these take time to evolve themselves. LATE is a big step towards improving its performance. The best part about this paper is that it is easy to understand , contrary to the usual scheduling paper where lots of math are used to describe their scheduling policy.

Enough praises.. I didn't like the parameters. I know the authors spent two pages of sensitivity analysis justifying them, and I respect their diligence. I just don't trust such static parameters can adapt to such a wide range of workloads. When things get overly complex, can we autotune it like how parallel programming community has done? It is almost impossible to predict performance because there are so many variable factors involved.

This work has much potential, especially because map reduce is merely scratching the surface of many powerful parallel distributed computation models. Many of these are only possible because of the rapid increase in network bandwidth. However, there is still significant differences in network bandwidth between different hosts in a data center. The scheduling decision here does not account for network topology and current machine workload. There are risks to using machines near the straggler as backup though, there is a higher chance for correlated failure because of network issue or machine issue (for a different thread / core on the same physical host)

All in all, this paper is great, but surely there are a lot more to be done.

Policy aware switching layer for data centers

This paper describes a way to insert middle boxes into the network in a logical but not physical fashion. This certainly relates to previous paper we have read that argues why middle boxes are disliked by the academic community because they break certain assumptions that were made during the design of the Internet.

Given a controlled environment such as Internet data center, the designer is essentially given the freedom to start from a clean slate. This allows this work to have a chance to be deployed as supposed to be a pure academic exercise, which I am really looking forward to. I suspect only real deployment will tell whether the complexity in its design is going to be an issue in daily operation or not.

In addition, I am worried that the performance overhead in the design (presenting itself as reduction in throughput as well as increase in latency) is going to render the system not cost effective economically. I am not sure how much of it comes from the fact it is Click-based and its software overhead, but it would be nice if authors could have attributed the overhead in more detail. (or perhaps our course project would help)

Delay Tolerant Network

The author argues the TCP has fundamental assumptions that are broken in "challenged" networks both in network characteristics and end point capabilities. Instead, the author proposes an architecture that is delay and link loss tolerant using a store and forward overlay to interconnect them.

I liked the ideas behind this paper and more importantly, the ideas in the paper have been in real deployments which is always a validation of the work. Although I am not sure if the rural areas are truly connected using this sort of technology. To have seamless transition from normal network to "challenged" network, the interface needs to be much more general. Most application written today rarely handle network failure gracefully, and to have these networks as functional as well connected networks, I believe network infrastructure is merely a first step. An application framework that makes failure handling explicit is also needed.

An Architecture for Internet Data Transfer

This paper describes an architecture to separate data transfer mechanism and the setup of the transfer, and thus enable the use of innovative transfer methods such as multipath and peer to peer protocols.

Overall a fairly straightforward idea, essentially a level of indirection to transfer large amounts of data using an asynchronous I/O model (receiver pull) . It uses plugins to add new transfer mechanisms to the system while maintaining backwards compatibility. It also divides data into chunks so that optimizations such as caching are more effective.

I think the main advantage is that this architecture allows features such as multipath and caching to be added hidden behind a very general interface. This is very powerful, but it allows little application control over caching and multipath policies. These plugins are ultimately shared resources between different application and I don't think the current design expose any application control over this. For example, if a bulk transfer happens between US and UK millitary , they probably don't want their data cached in intermediate nodes in other countries or want to control the multiple path selection process.

XTrace

This paper talks about tagging data and trace through different layers of protocol to provide better diagnostic tools in a distributed application. Overall a very good idea, as many applications are very difficult to analyze when it breaks down and faster diagnosis can lead to shorter downtime.

I assume this is to be used in online fashion. So it works like insurance against potential failure. There is some cost to instrument code to use xtrace, however it will likely reduce the pain when problem happens. Is this motivation strong enough for a company to adopt? How does this compare to the google approach of running multiple copies to buy them diagnosis time.

Also because this is online approach, performance overhead can also be a problem. But it is justified if it reduces the number of fail over copies a deployment needs.

Because X Trace is designed to be deployed across many ADs, if there is a bug in XTrace, it could potentially introduce correlated failure, which worries me a bit. Now things like performance bugs are multiplied and security bugs allows attackers to attack multiple ADs at once and through the entire application.

End to End Internet Packet Dynamics

This paper reports a large scale study of Internet performance using daemons installed on more than thirty nodes. The study goes on the conclude a list of result about various irregularities seen in Internet routing. It clears some misconceptions and shows that these irregularities do happen and sometimes frequently. Many of these irregularities also happen in site dependent fashion.

While many of these results are interesting facts and potentially lead to other further investigations of Internet irregularities. However, I feel the more valuable lesson from this particular study is the process of evaluating Internet performance at large scale. They were able to obtain a controlled experiment environment by embedding network daemons at various sites. I feel it will be more and more difficult to convince organizations to participate in today's world, especially non-academic settings.

They mentioned that they used 100k data to test bulk transfer. That seems quite low for any network today, and perhaps even low for Internet in 1995.

i3

This paper presents an Internet overlay that delivery packets in a rendezvous fashion. I think it is a very elegant solution to the problem of mobility and multicast, because ultimately the data is what the receiver is after. Its location is only a mean for it to obtain that piece of data. This sort of reminds me of web mail but with a much tighter latency constraint. We get mobility of webmail by having a pull model instead of a push model, however it is certainly too slow if we do the samething at packet level. So i3 essentially uses webmail model as control plane and establish a fast data path for more packets.

I like the basic idea behind i3. I am not certain the implementation can be widely deployed due to the problem in scaling up. They are already seeing some performance overhead with using DHT as trigger maintenance method. Nevertheless this model of communication opens up a wide range of possiblities to improve and hopefully overtime there will be innovation in the details of implementation of such system that overhead and scaling problem can be resolved.

Middlebox no longer considered harmful

This paper presents a new architecture of routing and naming so that the design of the Internet makes incorporating middleboxes easier. The authors argue that although middleboxes violates two of the tenets, the reason is that original Internet design is not flexible enough.

The new design uses the notion of EID to serve as global unique identifier, and uses method such as delegation to hop from one EID to another EID. This is how they enable middleboxes not on the physical path. It depends on DHT for naming lookup, translating EIDs to IP addresses or other EIDs.

It wasn't particularly clear to me that the problem with NAT and middleboxes are very serious. I think as ugly as middleboxes and NATs are, they are working fairly well. Everyone is buying them and manufacturs are coming up with various configuration tools to make sure they are set up correctly. This architecture has a clean design to it, but at what cost? Having an entire routing architecture depedant on a dynamic system like DHT just sounds like a bad idea. Particularly because the DHT is on the critical path of every flow until it is cached. The author recognizes the latency of DHT look up as a problem and throws out the caching as a general solution, but I think it is more difficult than that. Also the distributed nature of DHT makes it hard to find problems should one of the node respond slowly or fail.

DNS Performance and Effectiveness of Caching

This paper studies the performance of DNS by taking traces at two campus networks. The result was surprising because I rarely have issues with DNS lookup. Even more surprising is the fact that a large percentage of lookups are never answered.. I suspect the situation has improved since this study was done. Perhaps we need to do another round of study of this sort.

The authors conclude that since short TTL is being employed for a number of applications such as loadbalancing, NS caching is far more effective compared to caching of the actual result. The number of referrals have significant impact on the latency of the lookup.

I like this paper and this sort of large scale studies on the Internet, because there are just so many factors that affect a typical user's Internet experience. Users often do not know where the problem is when they experience a problem. DNS certainly would not be the first place I think of when I have connectivity issues.

Development of the Domain Name System

This paper describes the Domain Name System, which is the de-facto standard in Internet naming protocol. It describes the original goals of DNS, how it evolved and the design decisions behind DNS. Compared to other descriptions of DNS I have seen before, this paper focuses much more on the broader case of resource look up rather than the narrower sense of translating domain name into ip address. Unfortunately, some of these features such as multiple type and class did not see significant expansion even until today. This is not an isolated instance where systems were designed over generic.

In general, I liked this paper because it gave me a lot of historical perspective and the shortcoming and surprises that authors did not original expect. However, the description of DNS in this paper reads too much like a functional specification. A lack of typical usage pattern can cause some confusion for someone who is not very familar with DNS (me). In this respect, I find the second paper to be more helpful.

Chord

This paper describes in detail the design and implementation of Chord DHT system. It is a dynamic system that allows efficient content retrieval based on key value pairs and without centralized coordination.

The central idea to CHord is consistent hashing to allow some ways of balancing the load on different nodes in the chord ring. To further enhance the performance, Chord uses finger tables to allow O(log n) look up time of a particular key in the ring.

There are a couple of issues in this paper that were not clearly addressed. Issues such as fault recovery and migration of state between nodes on a planned take down of a node seems central to the correct functioning and operation of chord ring but received very little attention.

Another problem with this design is the latency in the lookup. Although Log(n) in terms of number of nodes in the hash space, the delay is still significant. Also each hop in the chord ring is an overlay and might translate into multiple hops in IP.

Overall, I still like this DHT compared to others in that it is simple to follow and works reasonably well. As system designers, in many cases, we tend to over design a system and makes it difficult to get implementation right. At some point, law of diminishing return kicks in and it is better to use the simpler design. I think Chord strikes a balance between simplicity and functionality, which is why it is one of the more popular DHTs.

Looking up data in P2P systems

This paper discusses reason behind P2p DHT like systems. Main reason for it is for fault tolerant data look up. They depend on symmetric lookup instead of hierarchical lookup. This way, no single failure is going to bring down the network , however, they tend to not scale as well.

The paper compares different DHT systems based on how they organize the data structure for key lookup. (tree vs. skiplist) and poses a number of open problems.

I like this paper because it gives a gentle introduction to set of problems in DHT and motivation behind it. It also gives nice taxonomy of different DHT project, which serves as a nice lead in to Chord.

Active Network

This paper talks about Active Network. Active networks allows per packet specific processing and embed the processing inside of packet using the concept of a capsule. This gives the network the flexibility to adapt to different need quickly and allows rapid deployment of new protocols.

The main problem that I see and author recognize in this setting is security and performance. To address security, they are using a restricted subset of Java. However, I don't think they are considering the problem of resource exhaustion. Of course, they have a certificate based solution as back up. However, that is very heavy weight, and usually the root trust has to be traced to one entity. I doubt all the networks in the world would trust a single entity to certify active code running in their networks. Subtle problems such as routing loops can occur simply because of a bug. Performance is also a critical issue. If the active content is not cached at the node, loading the node could introduce significant latency.

I like this paper in the curriculum because it introduces necessary background of active networks and gives some reflection on the experience of implementing such a toolkit.

RON

This paper describes an overlay network that is designed to improve recovery time in routing when failure happens and integrate path selection and routing more tightly with distributed applications. They argue that BGP infrastructure takes too long to stabilize.
Ron addresses this by forming a relatively small scale overlay network and maintain link state information to other Ron nodes. It actively sends out probes periodically to detect outage relatively quickly.

I like this paper because it gives a clear goal of overlay networks. It is usually designed to solve a particular issue that is difficult to solve without overhauling entire routing protocol. (in this case, BGP) However, just by limiting the scale of the problem and implementing functionality at application level, RON provides a practical path to deploy such systems. I think that is generally a big win for overlay networks and that's why they have been such active research areas.

Power Laws of Internet

The authors proposed thee laws of power relationships on the topology of the Internet and used measurement studies on a sample of the Internet to validate these proposals.
1. The outdegree of a node is proportional to the rank of the node to the power of a constant.
This is useful to estimate the number of edges in the Internet as the function of number of nodes.
2. The frequency of an outdegree is proportional to the outdegree to the power of a constant.
3. The eigen values of a graph is proportional to the order to some power of a constant.

I find this paper to be somewhat strange. The author proposed three laws based on some intuition and used specific sample to validate those claims. This somehow lacks rigor and it seems to be that there is no way to know if the same law holds today without redoing a comprehensive measurement. Perhaps there is something significant that I am missing, but I find this paper to lack some rigor and I was hardly convinced after reading it.

XORs in The Air: Practical Wireless Network Coding

This paper describes COPE, an encoding scheme that takes advantage of the wireless broadcast communication pattern to mix packets from different sources together to increase the amount of information conveyed using a fixed amount of packets sent.

This is definitely a neat idea. However, this scheme seems rather complex to implement because it violates so many assumptions that network applications now assumes. TCP scheme will likely not work well with this either since the batching of packets can be seen as a source of delay.

ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

This paper describes a technique that combines MAC layer and routing together. This breaks the conventional layering structure in network protocol, but offers better throughput as now it takes advantage of the slight chance that some packets might get "lucky" and travel further than it could reliably transfer.
The main problem with this scheme is how to prevent the overhead of communication between the recipients from overwhelming the benefit the scheme might offer. ExOR did the following:
1. batching of packets
2. use of batch map with packet transfer so that information is transferred at the same time as verifying the previous hop's transfer.
However, because this scheme is not compatible with existing TCP protocol, dedicated proxy is required to convert TCP connections into this kind of connection. This could be an obstacle that prevents its wide deployment. Many other technically superior solutions are not deployed because of compatibily issues.

A High-Throughput Path Metric for Multi-Hop Wireless Routing

This paper describes the underlying routing protocol used in Roofnet, called ETX (expected transmission count). The key idea is that wireless medium breaks the assumption that link is either working or not working. Minimal hop count can be suboptimal because the smaller the number of hop is, the chance of a weak link increases. Instead, ETX considers three factors: transmission loss ratio, assymmetry in the network link quality, interference causing reduction in throughput as the number of hops increase.

I liked the paper because this scheme neatly integrats all of the three mentioned dimensions that affect the throughput of the route. It also has extensive evaluation to prove the ETX is more optimal than minimum hop count in most cases.

The environment described in this paper is very similar to that of Roofnet. Certainly in a loosely connected Roofnet environment, because ETX considers link quality in its routing decision, it provides better quality routes. However, if the environment is changed to a densely connected, corporate environment, would ETX's overhead of link probing make it unsuitable candidate to use in these settings? Even in roofnet, some parts of it (i.e. near MIT campus) would be much densely connected. In these settings, I would argue interference is much more important factor to consider than loss ratio. Smart channel allocation will probably provide a much better gain in throughput.

Architecture and Evaluation of an Unplanned 802.11b Mesh Network

Compared to the previous paper, which takes the route of simulation, this paper is much more convincing since it carries a physical deployment in a real environment. There are so many factors not modeled(or difficult to model correctly) that can have significant impact on network performance in complex urban neighborhood. (Obstruction, interference , etc.)

The main contribution of the paper is the evaluation of the multi hop routing performance and their routing protocol Srcr which tries to find highest useful throughput rate between any pairs of nodes. It seems plausible in urban environment because of the high density of quality links, this sort of sharing between different home users can boost speed even higher (due to time multiplexing) and possibly guard against outage of a single provider.

Modeling Wireless Links for Transport Protocol

This paper summarizes a series of issues in current modeling of wireless links and how these inaccuracies can lead to potentially incorrect design decisions for transport protocol. As the underlying link layer characteristics change, the upper layer would need to adapt as well to perform optimally.

This paper characterizes many aspects and details of wireless network that makes it so hard to get accurate model. However, after reading it, I only feel that no matter how careful my model is, it is still not going to represent reality accurately enough. Certainly modeling is much more efficient to evaluate a new protocol or a proposal to change an existing protocol, but all I got from the paper is that modeling is probably never going to be good enough. Now I feel to make a very convincing argument, I will need real deployment data. Perhaps modeling would only serve as a first level filter in a feasibility study.

That leads to my second question. Given limited time to develop a model just to check if my protocol has a chance to perform well, which of these characteristics should I consider. This was not answered in the paper, and I feel that would benefit me and other network researchers a lot.

This paper is still an excellent paper to read, since it summarizes many link layer characteristics in different wireless networks that directly lead to many decisions that we made at the transport layer. It also serves well in the curriculum as a lead-in to a number of more detailed wireless papers.

Scaling Internet Routers Using Optics

This paper discusses a design to make use of optics in high performance internet routers. First, it discusses the architecture of a loadbalancing crossbar router using two stages of crossbar. Then it goes on to address problems with existing design of load-balancing routers using FOFF. Using optical switch can potentially enable a high performance router of using very little power, which is increasingly attractive since power is becoming a bottleneck and main cost in many datacenters.

The paper proposes a design based on hybrid optical and electrical that is more practical and can be implemented in three years, but provides no evaluation or simulation to justify the practicality. Perhaps the community familiar with optical design can immediately see why they are easier to design than a pure optical one, but it was not very clear to me personally.

Gb Switched Router

This paper presents an alternative architecture for high speed router design. Instead of using a traditional shared bus, it opts to use a crossplane that can enable multiple flows being routed from input port to output port simultaneously. In addition, it proposes destination based multiple queues and use of priority class to improve the delay vs. throughput curve. Moreover, it uses a combined unicast and multicast scheduler to maintain priority and avoid starvation.

As a white paper, it gives a lot of background in router design and archtecture, which is why I chose to read it first. I would suggest putting this paper before the other one to give students a good background in how commodity routers are designed.

This design is clearly geared towards building top end high speed router that have many input and output ports. As we know today, power is becoming an important constraint on routers. The paper did not analyze how this architectural change affects power usage. Some recent proposals indicates that many smaller commodity routers can potentially be used to build larger and faster routers.

Supporting Real-Time ...

This paper proposes mechanisms to support real time service in an ISPN. It makes distinction that some real time applications can adapt to the current network condition and do not have a hard bound on the latency like the rest of the real time applications. Because of this distinction, the paper proposes WFQ for the intolerable applications which focuses on isolation of service class and FIFO+ to minimize delay bound. It also proposes a way to combine the two elegantly into a unified framework.

In addition, the paper also discusses the importance of pricing in providing QoS in their architecture. In current Internet architecture, it is difficult to argue which one service is more important than other services and therefore it is an important reason why QoS is not widely deployed today.

Unfortunately, the architecture proposed requires an overhaul of Internet architecture, or at least at the backbone level. This is a very expensive task to undertake and will not provide the benefit it promises until everyone adopts these QoS control measures.

Fundamental Design Issues for the Future Internet

This paper was written in 1995, when Internet really started to take off in its growth. It looks at the applications on the network, particularly applications with real time requirement such as audio/video applications, and discusses options for supporting a service model that supports more than one single class of best-effort service. The paper argues that routers have to be able to differentiate between different class of service and give priority to application with real time constraint.

However, looking at the Internet today. Multimedia applications are everywhere, yet explicit admission control is not used in the network. The reality is that bandwidth has grown so quickly and now it can comfortably satisfy normal video viewing with proper buffering.

This paper gives very comprehensive view of the Internet architecture from a historical perspective (in 1995). Definitely a very good fit in the syllabus and a great introduction to the next paper.

Congestion Control for High Bandwidth-Delay Product Networks

This paper proposes a completely redesigned protocol that helps to manage congestion. Instead of using packet drop as a binary indicator, the paper extends on previous Explicit Congestion Notification (ECN), and use explicit headers from end hosts and precise feedback from the gateway to achieve congestion control. This is also designed to solve the instability and oscillation problem found in some previous congestion avoidance schemes based on TCP.

Key ideas:
1. decouple the fairness control from utilization control.
2. Error loss != congestion loss , especially true for wireless links and links with long delays

Cons:
1. Deployment will need to be a complete overhaul.
2. Leaving too much power in the hand of the end hosts. The control state contained in the packet can be modified to benefit the end hosts in several ways.

Random Early Detection Gateways for Congestion

This paper describes a technique to manage the queues at gateway level such that the queue size on average will be small but also accommodates occasional bursty traffic. This is also designed to mitigate the issue where all hosts decides to back off transmission in synchronization, as a reaction to dropped packet. This is in contrast to the traditional "tail drop" policy used at the time when the paper was first published, and is not biased towards bursty traffic.

This paper's work precedes previously discussed fair queueing work choronologically, so it was a little strange to read it in this order. This paper tries to do active queue management without keeping per flow state and differentiating between different flows. This simplifies the design at the gateway level. A good lesson from this paper is that by using active dropping packet before absolutely necessary, the gateway operates in a more optimal range and delivers packets with lower latency. Reactive systems requires the system to operate in a suboptimal state for a while before recovering, and thus are often not the best solution.

Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks

Under the assumption that maintaining of state information to achieve fair queueing implementation is overly costly, this paper proposes a solution to push the relatively more expensive operations to the edge routers and keeping core routers simple and extremely low latency. This is achieved by using packet labeling at the edge routers and provide hints to core routers to influence their dropping policy. Furthermore, the paper gives theoretical bounds that the combined effect of core and edge router fair queueing does not allow a user to exceed its fair share.

This architecture assumes that core routers and edge routers are configured under one entity. In reality, this is not true. Tier 1 ISPs frequently peer with each other, and packets often enter and leave these administrative domains. If all peering points are considered edge routers, would that add enough complexity to the system to render it impractical? If not, what is preventing ISP a to fake its label to gain priority on ISP b's network?
A large scale deployment of such configuration or simulation results with multiple administrative domain would help to clarify this issue and would be interesting to investigate.

Fair Queueing Algorithm

This paper presents a fair queueing algorithm designed to give each network conversation a fair share. When used with other endhost based congestion avoidance scheme, fair queueing can protect the network from malicious ill-behaved users. In addition, this scheme allows independent allocation policies for promptness, buffer and bandwidth . This leads to a faster response time for interactive sessions such as Telnet sessions.

To implement fair queueing algorithm at the gateway level, gateways are forced to keep flow level information. This was less than ideal because these state manipulation adds latency to the link, and makes fault recovery difficult to implement, which is the exact motivation of the next paper. However, in today's world, the need to keep flow level state information is growing because of traffic engineering and security needs. The balance between functionality vs. latency and reliability is likely going to depend on the operating environment and the particular application needs.

The definition of conversation is contriversial till this day. Could there be a better way to associate traffic with a particular user? What are the privacy implications of such association? I am curious to find out how many of current abuse of networks stems from the inability of network gateways to define user exactly.

This paper lays good foundation of what fair queueing is and serves as good background material for the next paper.

Congestion Avoidance and Control

This classic paper describes TCP congestion control and avoidance mechanisms in detail. It specifically stresses the principle of "packet conservation", i.e. input rate should match output rate of network. It addresses three scenarios where packet conservations fails, using techniques such as slow-start, round trip time estimates, and congestion avoidance.

TCP, as described in the paper, assumes the end points are going to behave well and has incentive to keep the network running as smoothly as possible. That is hardly the case in today's Internet. End points can achieve local optimal results, and damage other's quality of service.

TCP slow start sometimes can be too slow for an extremely fast, reliable, dedicated link in environments such as data centers. Modifications are usually made to boost congestion window to kick start the transfer.

This paper is an excellent choice for this class. It explains reasoning behind each optimization in TCP. However, I do want to point out that many of us have read it as part of CS262A.

Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks

This paper presents the theoretical reasoning behind TCP's additive increase and multiplicative decrease algorithm for adjusting its sending window to control congestion. It compares different byte feedback control algorithms using four metrics: Efficiency, Fairness, Convergence time and size of oscillations.

I really like the organization and the progression of the paper. First, it proposes four conditions a congestion avoidance algorithm must satisfy. Then it introduces a few conditions at a time to filter out possible solutions from a wide selection. This makes a theoretical paper easy to follow and what used to seem like "black magic" now makes perfect sense.

Distributedness was not originally listed as one of four metrics, but it is certainly an important factor. Internet was designed to be scalable because it does not have centrally managed parts, congestion avoidance continues to follow that model.

The paper argues that increased bit feedback may reduce amount of oscillation. I think it actually will help with the convergence speed as well. Previously in class, we have discussed to separate control and data channels, how would this congestion control mechanism benefit from dedicated channel. Is the data channel currently affecting the convergence speed of congestion avoidance?

This paper should definitely stay in the curriculum. It introduces a well known concept in a formal way, and explains the reasoning quite logically. There are a lot of concepts that are intuitive but difficult to explain why.

As the network physical layer changes, how will congestion control be affected? Also how does congestion avoidance work / fail under malicious attacks? Those are likely interesting topics of further research.

On Inferring Autonomous System Relationships in the Internet

This paper explains the various relationships between different Autonomous systems (AS) in the Internet and how their routing policies ensure these economic relationships. It goes on to attempt to infer these relationships by looking at publicly available routing table entries based on some patterns authors observed.

Like all other reverse engineering types of work, there is a bit of heuristics involved. The author makes the assumption that businesses define their routing tables based on their business relationships. Therefore, we can work out the business relationship based on routing tables. However, through this work, interestingly enough, they were able to uncover misconfigurations of routing policies.

The author used a lot of formal mathematics in explaining the details, which is perhaps a bit difficult to understand for someone who is not well versed in network theory and graph theory. I would not mind reading something else instead since the idea is neat but the details are not as interesting.

Interdomain Internet Routing

This lecture notes summarizes the key points in inter domain routing, and specifically focuses on the policy decisions that are made in BGP, and how BGP operates to achieve these policies. It explains in detail how BGP allows flexible policy configuration through a number of parameters.

I would have liked to see some explaination of how the BGP protocol helps to achieve some of the goals of Internet mentioned in first lecture. That is perhaps a worthwhile discussion in class.

Overall it is a very informative lecture notes. Its focus on the economic motivation behind a lot of these policies is particularly interesting. We should definitely keep it in the syllabus. However, I did notice that some concepts were repeatedly mentioned but not defined or explained. I think it is perfectly fine to refer to other papers in a technical paper, but as lecture notes, a brief definition would help students a lot. (eg, route oscillation, provider-based addressing etc.)

The Design Philosophy of the DARPA Internet Protocols

Key points of the paper:
1. Goals of the original DARPA Internet
Reliability was most important criteria. It must handle transient failure such as failure of a router. This directly resulted in the end to end approach (fate sharing) instead of replication being taken in the design.
2. Different applications have different requirement for transport protocol, and thus we have TCP and UDP.
3. Generality over specialized implementations allows Internet to handle different types of private networks being connected together.
4. Performance of protocol implementation is difficult to evaluate, and it leaves potentially broken network stacks to hurt the overall performance of the network.

Thoughts on the paper:
1. Design for generality over specialization: TCP/IP stack was designed to work with most services, and therefore it may not be the best answer for specialized environment such as data centers and sensor networks. That's why there has been a lot of research to tweak or completely replace these transport protocols in non-traditional networks.
2. Because the middle points of the network are designed to be "dumb", this allows malicious hosts to inject traffic into network that hurts its performance. Firewall is a great example of state in the network, between hosts.
3. The author was worried about implementation differences in end hosts leading to bad network performance. This has not really happened because of aggressive code reuse and sharing.

End-to-end Arguments in System Design

This paper argues that functions placed at lower level of a system may be redundant and less effective compared to functions placed at the application level. It uses several examples to show that lower level implementations may only offer a performance advantage over higher level functions. The paper focuses on communication subsystem, but can be applied to other parts of a distributed system design.

This is a seminal paper describing a design principle that is found everywhere even in modern network design. It is an excellent choice to start off the term. Examples used in the paper such as error recovery, secure transmission, etc. are still very relevant today, and are still implemented following end-to-end principle.

However, I do not completely agree with all aspects of the paper. This paper was written in 1981, when the number of applications running on top of the network is relatively small. In addition to possible performance advantages, implementing features in-network or at lower level has the benefit of benefiting all application at once and ease of deployment. Network switches are getting more and more advanced to perform traffic shaping, network filtering, firewall functions that may be implemented on end hosts better, but would be a nightmare to maintain and deploy.

Future research will continue to revolve around where the ends are in a system and moving functionality to and away from end points. Because of constraints such as mobility and power, some features are becoming prohibitively expensive to perform on the end hosts.

Welcome to Network Bits

Welcome to Network Bits. My name is David Zhu. I am a graduate student attending University of California, Berkeley. I will use this blog to write down and reflect on any thoughts on the readings in CS 268 class taught by Prof. Randy Katz in Fall 2008.