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.