A Policy-aware Switching Layer for Data Centers

The main idea of this paper is to provide a policy layer that does not mandate placing the middleboxes in sequence on the physical network paths. PLayer uses policies that propagate to the switches, which then route packets through middleboxes before delivering them to their destination.

This is a very nice idea that tries to alleviate the complexity of configuring middleboxes, ensures correctness, network flexibility and efficient resource usage. The authors also discuss why minimizing the changes required for adopting PLayer is crucial. It is true that the success of any new technique is tightly coupled to the amount of changes it requires for deployment.

It was nice that the authors also thought about security issues related to PLayer. They discuss how policy violations can take place during policy churn and how these can be solved.

I really liked reading the paper because it gave detailed explanation about the limitations of current techniques and explained PLayer very nicely with all relevant details listed. I would recommend keeping this paper in the class.

Improving MapReduce Performance in Heterogeneous Environments

The authors in this paper propose a new scheduling algorithm LATE that improves performance in heterogeneous environments. The paper is very interesting to read and is well written. Hadoop scheduler makes assumptions like homogeneous environment, tasks progress at constant time, no cost in launching speculative tasks, equal weight to all functions in a reduce task etc. These assumptions degrade performance.

Pros:

• Thinks about heterogeneous environments.
• Execution of speculative tasks is estimated from the time left to finish the task.
• I liked that authors discuss how their time left estimation technique may fail in certain scenarios.
• I really enjoyed reading the paper. It was very nicely written.
• This solves a problem in the data parallel applications that are being used in the industry and are getting adopted by more and more companies.
  

Thoughts:

• The authors suggest that different methods can be used to estimate the time left for a task. Currently, they estimate it as (1- ProgressScore)/ProgressRate. Is there a way to store history of tasks to gather statistics and then use that for estimating the time taken by a task?
• Has there been future work in the area of finding more sophisticated methods for estimating finish times.

A Delay-Tolerant Network Architecture for Challenged Internets

This paper proposes an architecture that uses overlays for achieving interoperability between diverse networks. The motivation behind building this architecture is to address problems with the TCP/IP model with respect to challenged networks. Some of these problems are network partitioning, high latencies and unexpected data transfer delays.

The architecture includes regions and gateways. Gateways are responsible for storing messages to provide reliable delivery. For routing messages they use a naming scheme that uses name tuples. Name tuples are of the form {Region, entity} where region names are unique. Convergence layers add features like reliability, and message boundaries.

Pros:

• Provides in-network storage and retransmissions in challenged networks
• The prototype implementation convinces the practicality of the architecture to a certain extent.

Cons:

• Existing application may need to be changed in adoption of the architecture
• Necessary to evaluate the overhead of using messages instead of packets
• Does it break the end-to-end model?
  

An Architecture for Internet Data Transfer

The authors in this paper propose DOT architecture that separates content negotiation from data transfer. The main idea is to provide a transfer service that can be used by applications for bulk point-to-point transfer. The advantages of providing a transfer service include:

• re-use available transfer service
• ease in adopting new transfer techniques

Instead of iterating how the authors design DOT I would list my views about the paper. I do not have any specific negative points to the proposed scheme. The main motivation is to provide a general data transfer service that anybody can use without spending time re-implementing the same service. It is good to provide general implementations that anybody can use but along with such implementations comes a drawback. The disadvantage is to be unable to add optimizations specific to the application that is using the transfer service.

X-Trace: A Pervasive Network Tracing Framework

X-trace is a tool built to ease the process of diagnosing complex tasks like web requests and DNS resolution. The main concept involves inserting X-trace metadata into a network task by a client. Metadata involves a task identifier that uniquely identifies the task. When a node sees X-Trace metadata it generates a report which is used for reconstructing the datapath. Task tree construction is performed offline by the user. The user collects reports and uses the information to build a request tree and diagnose the path traced by the request.

The main motivation for this work is to ease the method of diagnosing complex systems that have an interplay of multiple applications and protocols. I feel that with the rapid evolution of the Internet and multiple application running over it, it is really required to build better mechanisms for debugging. X-trace aids in automating the process of debugging rather than collecting reports and then manually trying to assemble them.

Even though X-trace shows to be really helpful, first thing that concerned me was related to its adoption. Success of X-trace relies on the easiness of modifying current applications and protocols. Partial deployment of X-trace can limit the view a user may get while diagnosing the problem. I was happy that the authors were aware about these issues and have discussed them in the paper. I would recommend keeping this paper in the syllabus.

Internet Indirection Infrastructure

The authors in this paper propose an overlay based scheme to provide services like multicast, anycast and mobility. The main idea of the paper involves sending a packet with an identifier and the receivers set triggers for receiving packets associated with an identifier.

I liked this scheme because it is neat and simple. The sender has to communicate with the intermediary and not with all the interested receivers of the packet. This aids in decoupling the act of sending from receiving.

This scheme relies heavily on the performance of the overlay. The overlay used should be: Robust, Scalable, Efficient and Stable. The authors choose Chord and say that it satisfies all the requirements.

I really like the concept for its simplicity but few things that concern me are:
1. What happens when a chord node goes down? This involves copying the triggers registered with the failed node to another node. This requires a robust replication and that will make the system more complicated.
2. Efficiency of this system is less because we have introduced indirection.
3. How is revocation of triggers handled neatly?

Middleboxes No Longer Considered Harmful

This paper discusses how middle-boxes such as NAT and firewalls violate the two principles of the Internet architecture:

1. Unique identifier for each Internet entity.
2. Packets processed by their respective owners.

The authors say that even though the middle-boxes break the rules but they are required for important reasons. Few reasons being security and performance improvement through caching as well as load balancing. The paper then proposes an architecture to include the functionality of middle-boxes without breaking the principles.

The architecture called Delegation Oriented Architecture proposes the following things:

1. Globally unique ID in flat namespace which is carried by the packets
   
2. Sender and Receiver can define the intermediaries that should process the packet.
   

Without going into the details of the architecture and how it works, I want to list some of the things that concerned me:

1. After adding the intermediary information in the packet we are still defying the end-to-end principle. What happens if the intermediary crashes?
   
2. The unique identifiers are said to be 160 bit long. The packet is supposed to have 2 160-bit identifiers. Isn't this an overhead for small packets?
3. The idea seems to be interesting but I am concerned about performance. Even though the architecture provides flexibility by allowing the intermediaries to be anywhere and not in the path to the destination. The packet now has to be first traversed to the intermediary and then to the destination. Also, it is required to lookup of the path to the intermediary.
4. Another question that get raised with such systems is scalability. With so many machines in the Internet, if every machine sends the message to an intermediary and the DHT being used for EID resolving, an important question arises that we are relying on the performance of the DHT for lookup and information retrieval.
   

DNS Performance and the Effectiveness of Caching

This paper provides analysis of:

1. DNS performance (latency and failure)
2. Effect of varying TTL and degree of caching affect

The analysis was performed on three traces that included DNS packets and TCP SYN, FIN and RST packet information. The authors found that over third of all DNS lookups were not answered successfully. 23% of the client lookups in the MIT trace failed to arrive at an answer while 13% lookups gave errors in the answer.

The authors show that name popularity distribution is zipf-like. Effectiveness of caching is determined by finding how useful is it to share DNS caches and the impact of choice of TTL value. Intuitively, I was under the assumption that reducing the TTL will severely affect the performance of DNS but the authors show that reducing TTLs of address(A) records to few hundred seconds has little effect on the hit rate. Also, sharing a forwarding DNS cache does not improve performance.

I found the paper very interesting to read. The analysis of performance of DNS is not dependent on aggressive caching is opposite to the general notion of DNS performance being tightly tied to caching. This observation is directly related to the relationship between TTL values and name popularity. Popular names will be cached effectively even with short TTL while unpopular names may not gain even with long TTL values.

It will be nice to discuss how would the results vary if analyzed with current time traces.

Development of the Domain Name System

This paper discusses the motivation behind the design and need of DNS. Prior to DNS each machine downloaded a file called HOSTS.TXT from the central server on to their system. This file contained the mapping between host names and addresses. This scheme had the inherent problem of distribution and update. With the rise of the number of machines connected to the Internet came the need of building a distributed system for the functionality of HOSTS.TXT.

DNS was designed for this need. It is a hierarchical naming system that had the following design goals:

1. provide all information of HOSTS.TXT
2. Allow distributed implementation of the database
3. Have no size limit issues
4. Be inter-operable
   
5. Provide tolerable performance

DNS contains two main components: name servers and resolvers. Name servers store information and answer queries from the information they possess. Resolvers are the interface to client programs and contain algorithms for querying name servers. DNS name space is organized in the structure of a variable-depth tree. Each node in the tree has a label associated with it and domain name of a node is the concatenation of all the labels on the path from the node to the root of the tree.

One of the main things that makes DNS fast is caching the results of the queries. This overcomes the need to fire a query every time a name lookup has to be performed. Although this optimization comes at the cost of a security concern. People have exploited this feature to perform DNS cache poisoning attacks.

I really enjoyed reading the paper because it gave a good explanation of the ideas behind the design of a system that plays an important role in today's Internet. I would recommend keeping this paper in the syllabus.

Lookup Data in P2P Systems

This paper gives a brief summary of lookup operation in P2P networks. It gives an overview of why P2P networks are attractive, discusses the lookup problem, which is basically "Given data X stored in a set of dynamic nodes, how to find it". I really enjoyed reading the last section. The paper discusses talks about CAN, Chord, Kademlia, Pastry, Tapestry and Viceroy.

All these DHTs use different overlay networks (underlying topological structure). Different overlays have different complexity for lookup. Differences between DHTs include distance functions that are combination of being symmetric and unidirectional, cost of node join/failure operations when they happen frequently, network aware routing, malicious nodes etc.

I would recommend keeping this paper.

Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications

This paper talks about the Chord DHT and how it is useful. Instead of giving the complete summary of how it works I want to list the pros and cons of Chord.

The authors in Chord use ring geometry and choice of the DHT geometry greatly affects performance. "The Impact of DHT Routing Geometry on Resilience and Proximity" paper shows that amongst different DHT geometries ring geometry provides greatest flexibility. Another thing I like about Chord is its simplicity.

One place where Chord may not work well is in cases where there is lot of churning. This observation has been made by the Bamboo DHT designers. Also, Chord periodically performs stabilization. This requires that the periodic epoch needs to be tuned as per the need of the network where the nodes reside. Another thing that Chord does not consider is the network topology. DHTs like Tapestry and Pastry take into consideration the network locality and try to minimize the distance traveled by messages.

Active Network Vision and Reality: Lessons from a Capsule-Based System

Active networks allow individual user, or groups of users, to inject customized programs into the nodes of the network. This aids in building a range of applications that can leverage computation within the network. The authors in this paper use ANTS active network toolkit in designing and implementing active networks and share their experience.

The authors express their findings in comparison to the general vision of active networks in three areas:

1. Capsules: They can be a competitive forwarding mechanism whenever software-based routers are viable. Capsule code can be carried by reference and local on demand. The cost of capsule processing is not high when forwarding is also performed in software.
   
2. Accessibility: Each user can handle their packets within the network. Also, code from untrusted users should not do any harm to users of other service.
   
3. Applications: Capsules aid in experimenting with new services and deploying them.

The concept of active networks is new to me. The paper was good to read because it talked about the issues active networks have and how the authors experience these issues and resolve them. The only thing that concerns me is the issue that a malicious member of a group can harm other users of the group. The authors talk about this problem and also say that it is not specific to active networks.

Resilient Overlay Networks

This paper proposes an architecture that enables a group of nodes to provide communication in case of failures in the underlying Internet paths. Group of nodes in RON have an application-level protocol for communicating with the other nodes in RON. The protocol ensures that high-speed recovery of path failures, low-latency, and improved loss rate and throughput exist among the nodes participating in the RON.

RON was designed to improve the underlying Internet routing protocols (BGP). BGP can take a long time to converge after link failure. RON aids in recovering from outages and performance issues in seconds. Other goals of RON are tighter integration of routing and path selection with the application and expressive policy routing.

I liked that the authors are proposing an architecture to solve the inherent problem of BGP convergence. Although there are issues that still remain undressed. These include machines behind NAT and violation of BGP policies. The authors discuss these problems as well. The evaluation results are very good but with such techniques one is never sure how they will work in real large scale deployment. Also, it would have been nice see how RON would work in case of congestion, that is how tolerant is RON itself? One more concern I have is related to RONs pushing too aggressively to find alternate routes. This can cause a lot of traffic and be very expensive.

I would recommend keeping this paper because it can stir up a very good discussion in the class regarding the design decisions and their pros and cons.

A First Principles Approach to Understanding the Internet’s Router-level Topology

The authors in this paper argue that previous researchers who have analyzed the structure of Internet topology have not considered factors like router technology and network economics. There can be other key factors that affect the structure and should be taken into consideration along with using statistics and graph theory. The paper considers router capacity constraints, as well as likelihood to model router-level topologies and discuss understanding the evolution of networks in order to accurately model router-level graphs.

I agree with the arguments proposed by the authors. One thing that comes to my mind is how BGP is greatly influenced with the economic policies integrated in making route decisions. Thus, while understanding the Internet topology, router technology and network economics play an important role. The authors discuss different factors and also discuss the importance of robustness of the network to node /link failures. The authors do not discuss about this feature because of its complexity. It will be nice to discuss how robustness complicates the model and how much does it affect if not considered.

On Power-Law Relationships of the Internet Topology

This paper analyzes Internet and describes three power laws of the Internet topology. The reason these laws are important is that they aid in understanding the topology of the Internet and help in designing more efficient protocols. Also, we can design more accurate simulation models as well as estimate topological parameters for analysis of protocols and speculations of the Internet topology in the future.

The authors use three inter-domain level instances of the Internet from 97-98 during which the topology grew by 45%. They also used the router-level instance of the Internet in 95. The three power laws are:

1. Rank Exponent: The out-degree of a node 'v' is proportional to the rank of the node to the power of a constant
2. Out-degree Exponent: The frequency of an out-degree 'd' is proportional to the out-degree to the power of a constant
3. Hot-plot Exponent: The total number of pairs of nodes within 'h' hops is proportional to the number of hops to the power of a constant

It is observed that all the laws are expressions of the form "y is proportional to x to the power of constant a". Some of the constant do not change significantly over time. During 1998 the power laws linearly fit in log-log plots and the correlation coefficient of the fit is at least 96%.

The paper used real-data for evaluation and used more than one instance of the dataset. The authors argue that the power-laws apply to a range of values because their analysis shows similar results for datasets that were taken when the Internet changed drastically.

The main thing that comes to my mind is the validity of the power laws in the current Internet topology. Do these laws still hold? It will be nice to have a discussion about this. I would recommend keeping this paper because this paper puts forward laws that can be used to design simulation models that are similar to the current Internet topology.

XORs in the AIR: Practical Wireless Network Coding

This paper discusses COPE that exploits network coding theory techniques to improve throughput in wireless networks. COPE also exploits the shared nature of wireless medium. Briefly COPE uses following techniques:

1. Opportunistic listening - Exploiting the shared nature of wireless medium, COPE sets the nodes in promiscuous modes and makes the nodes snoop on all communications over wireless medium and store overheard packets for time T. Reception reports are sent back.
   
2. Opportunistic coding - A node codes multiple packets together such that all the neighbors that will receive the packet can decode.
   
3. Learning neighbor state - Each node has to know what packets its neighbors contain. Each node announces to its neighbors its reception report. In case of loss of these reports wireless routing protocols compute the delivery probability between every pair of nodes and use it to identify good paths.

COPE is the first architecture that uses wireless network coding that has been deployed and provides a study of the results. The results show that network coding can improve wireless throughput. Congested UDP flows have throughput gain of 3-4x. In case of TCP their is not much significant improvement. The gain depends on the traffic pattern as well as the coding opportunities available.

The paper is interesting to read because it portrays implementing the theoretical concept of network coding into reality. Something that concerns me is the variation of results based on the type of the network, its topology and traffic pattern. This raises the question of how well COPE will work in real world deployment?

ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

The authors in this paper propose a technique that is very different from traditional routing schemes. In traditional routing protocols the receiver of the packet is chosen before forwarding the packet. ExOR proposes forwarding the packet to a set of nodes and later deciding which node will forward the packet to the destination. The idea is to exploit the broadcast nature of wireless medium.

ExOR technique involves:

• Source operating on batches of packets. This is done to reduce the communication involved for synchronization.
  
• The source node adds a list of candidate forwarders (sorted in descending order of priority) to each packet in the batch and forwards the packet to all the candidates. Priority is based on the distance of the node from the destination.
  
• Highest priority node then forwards the packet further with its list of candidate forwarders.
• Remaining forwarders transmit in order but only send packets that have not been acknowledged in the batch maps of the higher priority nodes.
• The forwarders continue to cycle through the priority list until 90% of the packets have been received by the destination.
• Remaining packets use traditional routing.

Without going into too much details I just want to go through the advantages of the scheme and then talk about things that concerned me.

Pros:

1. Takes advantage of the broadcast medium
2. Opportunistically takes advantage of long lossy links
3. Provides reliability through diversity
4. Low priority nodes will most likely not forward packets
5. ExOR protocol improves throughput by a factor of 2 or 4 over ETX since it uses multiple relay nodes to forward the packet to the destination.

Concern:

1. ExOR scheme suggests that forwarders (other than the highest priority forwarder) transmit packet if there are unacknowledged packets that were sent by the higher priority node. This means that the higher priority forwarders have to communicate to other forwarders that the packet has not been acknowledged. This seems to be too much of a communication overhead.
2. There is too much state to be kept with each node. Each node has to store each packet it receives in its buffer.
3. After 90% packets have been received rest of the packets use tradition routing. Also these 90% packets can take different routes. Thus, the rate at which packets are arriving at the receiver may vary a lot.
4. There seems to be not much study about the interference of communication between forwarders.
   

A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols

This paper provides an analysis on the comparison of a variety of multi-hop wireless ad hoc network routing protocols. The ad hoc routing protocols evaluated are:

1. DSDV (Destination Sequenced Distance Vector) - It is a hop-by-hop distance vector routing protocol that requires each node to periodically broadcast routing updates. This guarantees loop free routing. DSDV maintains a routing table that lists the next hop for each destination. Each route update is tagged with a sequence number and route R is updated only if the update message has a higher sequence number than old update message.
   
2. TORA (Temporally-Ordered Routing algorithm) - This is a distributed routing protocol based on link reversal algorithm. It discovers routes on demand, provide multiple routes to a destination, establish routes quickly and minimize the communication overhead by localizing algorithmic reaction to topological changes.
   
3. DSR (Dynamic Source Routing) - The header of each packet carries the complete ordered list of nodes through which the packet must pass.
   
4. AODV (Ad Hoc On-Demand Distance Vector) - This is a combination of both DSR and DSDV.

These four protocols are compared based on:

1. Path Optimality - Number of hops a packet took to reach its destination compared to the length of the shortest path in the network
   
2. Packet Delivery Ratios - Packet loss rate seen by the protocol.
   
3. Routing Overhead - Total number of routing packets transmitted during the simulation

The paper has made a lot of observations in their comparison analysis. It has been observed that both DSDV-SQ and DSR use routes very close to optimal while TORA and AODV-LL have a significant tail, TORA is not designed to find shortest path, DSDV performs well in low node mobility, AODV performs as well as DSR.

Things I would like to take away from the paper is the ns network simulator extension. I agree with Stephen about the point that performance should have been evaluated with several models.

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

This paper talks about ETX metric that ensures finding high-throughput paths in a wireless network. The authors argue that most protocols in wireless networks concentrate on minimizing the hop count when choosing paths for routing. Minimum hop count can maximize the distance traveled in each hop and large travel distances are likely to increase losses due to loss in signal strength. They propose ETX that requires few expected number of transmissions required to deliver packets to the destination.

As stated in the paper "ETX of a link is the predicted number of data transmissions required to send a packet over that link including retransmissions. ETX of a route is the sum of the ETX of each link in the route". Each link's ETX is calculated using forward and reverse delivery ratios of the link. Delivery ratio is the measured probability that a packet(data or ACK) successfully arrives at the recipient.

The main thing to take away from the paper is that the performance of a route is dependent on the packet delivery rate of the links. The packet delivery rate takes into consideration both the directions of communication where one direction is used to sending data and the other is used for sending ACKs.

The ETX metric performs better than shortest hop count routing protocols. It considers lossy links, asymmetric links and interference while choosing the routing path. The issues that still remain unanswered are network load (it does not consider congestion) and adaptiveness to mobility.

ETX is computed by each node broadcasting a probe packet every second. The probe packets sent are of fixed size at an average rate of T. These packets may not depict the same loss rate that the data packets may face. This can happen because data packets may be coming at a much higher rate and their size may be different as well.

Architecture and Evaluation of an Unplanned 802.11 Mesh Network

The authors propose an architecture for wireless mesh network that has four goals:

• Unconstrained node placement
• Omni-directional antennas
• Multi-hop routing
• Optimization of routing for throughput in a slowly changing network
  

These goals provide the ease of deployment which is an important requirement for community wireless networks. The evaluation of the architecture is done by deploying 37 nodes spread over 4 square kilometers of urban area.

The evaluation determines the end-to-end performance of Roofnet and the effect of the design decisions. The measurements are based on:

• Multi-hop TCP data: 15 second one-way bulk TCP transfer between each pair of Roofnet nodes
  
• Single-hop TCP: direct radio link between each pair of routes
  
• Loss matrix: loss rate between each pair of nodes using 1500-byte broadcasts
• Multi-hop density: TCP throughput between a fixed set of four nodes varying the number of Roofnet nodes that are participating in routing

The end-to-end performance of Roofnet is determined by the basic performance, link quality and distance, effect of density and mesh robustness.

I liked the fact that the paper uses a network that is deployed in the real world to evaluate the architecture. This aids in understanding the real-time traffic and how the network works in such scenarios. Another thing to take away from the paper is how the authors have taken great care to provide ease of deployment and maintenance. This aided in deployment of Roofnet by volunteer users.

The evaluation shows that the average throughput decreases to 43% if the best two nodes are lost. This can be a huge problem because you are relying on these two nodes for higher throughput. Another thing that is not clear to me is how crucial is their placement of few nodes at the top of tall buildings? The paper lacks investigating the architecture in terms of the dynamics of the network. It does not handle the effects of user joining/departing and also about varying network performance over time.

Modeling wireless Links for Transport Protocols

Wireless links face issues like variable bandwidth, corruption, variable latency etc. This affects the performance of TCP because TCP assumes packet losses are due to congestion. Link layer protocols like FEC/ARQ have been proposed to improve performance but they suffer from drawbacks like large link-level queues.

This paper proposes models that should be used for evaluating transport protocols over wireless links. Wireless links include Cellular, WLAN and satellite. The authors say that the traffic model can have significant effect on the simulation results. It is often the case that if we do not model all types of traffic in the network then the evaluation of the protocol will not be complete. Transport protocols are generally evaluated over throughput, delay, fairness and dynamics. In case of wireless networks it makes sense to see how much useful data got through with respect to all the delivered data. The authors term this as "goodput".

Models used should be realistic, explore all the parameters, do not use something overly realistic and should be available to be used by others. The paper gives very good examples related to these features.

Modeling of wireless links include:

1. Error loss and corruption should be modeled by dropping packets at a per-packet, per-bit or time-based loss probability. Losses due to data corruption should be modeled at the end of the link while handover losses should be modeled before the link.
2. Delay variation can be modeled by suspending the data transmission on a simulated link.
   
3. Packet reordering requires either building a queue and swapping packets or delaying one packet for a given time.
4. On demand resource allocation can use a model where additional delay is introduced when a packet arrives to a queue that has been empty for a longer time.
   
5. Bandwidth variation can be modeled by having periods of low and high bandwidth.
6. Asymmetry is modeled by having different settings for uplink and downlink.
7. Queue management
• WLAN/Cellular links: use drop-tail buffer with configurable maximum size in packets
• Satellite links: use RED
8. Effects of mobility have to be modeled based on whether underlying mechanisms of handover have to be evaluated or the effects of the handover need to b e evaluated.

The authors in the end discuss how bit errors in wireless links should be handled at the link level while reordering of packets be handled at the transport level. Transport protocols can be made robust to address delay variations while link-level protocols can be changed to hide delay variations from the transport payer.

The paper was interesting to read because it explained different environments that wireless communication can face and how the models should take these into consideration.

The paper says that currently wireless links at both ends is not common. Is this true today as well? I am not sure what the authors mean. Do they mean that complete communication uses wireless links or that both the machines communicating are not using wireless links?

A Comparison of MechanA Comparison of Mechanisms for Improving TCP Performance over Wireless Linisms for Improving TCP Performance over Wireless Links

Summary:
TCP proves to not provide good throughput in case of wireless networks. This is because packet losses in TCP are handled by invoking congestion control and avoidance algorithms. Wireless networks face packet losses due to high bit error rates, intermittent connectivity etc. There have been several schemes proposed to improve TCP performance in wireless networks:

1. End-to-End protocol - In this scheme the losses are handled by the sender. There are two techniques that are typically used:
• SACK provides selective acknowledgement to allow the sender to recover from multiple packet losses in a window without invoking timeout.
• Use ELN (explicit loss notification) to distinguish loss from congestion.
2. Link-Layer protocols - This protocol tries to hide the link layer losses from the sender by using local transmissions (ARQ) and FEC (forward error connection). The TCP sender may see the effect of losses because the lossy link is part of the connection. There are some protocols that use the knowledge of TCP along with link-layer protocols.
3. Split-connection protocols - This scheme uses a separate reliable connection between the base and the sender to communicate SACK/NACK.
4. Snoop Protocol - This places a snoop agent at the base station which monitors every packet in the TCP connection. A cache of packets that have not been acknowledged is kept by the receiver. Small number of duplicate acknowledgements or local timeout causes the snoop agent to retransmit the packet (if it is in the cache) and suppresses the duplicate acknowledgements.

Impact and Critique:
The authors evaluate different schemes that use one of the three protocols for improving performance. It is found that reliable link layer protocol with some knowledge of TCP provides very good performance. This is due to the fact that typical link layer protocols are affected by the TCP fast retransmissions while TCP aware link layer protocols suppress the excess duplicate acknowledgements thus improving performance. End-to-End protocols that have both ELN and SACK out perform typical end-to-end protocols. While split connection protocols improve performance but they are worse that TCP aware link layer protocols.

I found the paper interesting to read because it discusses what issues TCP faces in case of wireless networks. TCP is designed keeping in mind wired networks that generally have packet loss due to congestion. Comparison of different wireless protocols and how they perform in wireless networks was very insightful. Since I did not know much about wireless protocols this paper helped me understand different schemes that have been proposed and also the issues they face.

It would have been nice to discuss the pros and cons of each protocol in more detail. I could not understand how the ELN scheme distinguishes whether a loss is due to congestion or packet loss. It seems to me that the TCP aware Link layer protocol violates the layered concept. We are now mixing link layer with transport layer. Also, it would have been insightful if the paper also showed how the protocols perform in case of congestion.

MACAW: A Media Access Protocol for Wireless LAN's

Summary:
The authors in this paper propose MACAW that modifies MACA. Techniques that have been proposed for wireless communication include:

• CSMA (Carrier Sense Multiple Access) that senses carrier before sending data. this faces "Hidden node" and "exposed node" problem.
• MACA (Multiple Access Collision Avoidance) uses RTS-CTS-Data along with exponential backoff to select retransmission time.

MACAW proposes four changes:

1. Fairness:
   
• The binary exponential backoff (BEB) algorithm does not provide fairness. It can happen that a terminal with low backoff counter will always win over another terminal with higher backoff counter where both terminals are sending data at channel capacity. MACAW proposes to have all terminals in a range update their backoff counter on hearing a packet.
  
• To make BEB algorithm not have large oscillations the authors propose MILD technique.
• Fairness over stream instead of per station is achieved by implementing separate queues for each stream.
2. RTS-CTS-DS-DATA-ACK modifications:
• RTS-CTS-DATA-ACK exchange provides error checking at link level.
• Send DS before DATA so that all nearby terminals wait until ACK is heard. This provides efficient synchronization of information about contention periods.
  
• RRTS solves contention problem due to lack of synchronization. Example we have A-to-B and D-to-C stream where B and C are close to each other. In this case D-to-C stream RTS may not be responded because A-to-B stream has large data size and short gaps between complete data transmission as well as completion of B's next CTS. In order to solve this problem RRTS can be issued by C to D (as response to non-responded RTS) during the next contention period in order to initiate communication .
  
3. Location dependent
• Since congestion varies per region it is required to modify BEB to be per sender-receiver pair. This is achieved by having the backoff scheme copy both sender and receiver backoff counters.

Background:
It is helpful to read about 802.11 MAC protocol before reading this paper.

Impact and Critique:
The paper very nicely gives a brief overview over the past protocols and their drawbacks. I felt that per stream implementation by keeping separate queue for each stream was similar to the concept of VOQ.

MACAW protocol addresses a lot of issues like fairness and better congestion control but there are issues like NACK and multicast that have not been addressed or do not have a good solution. While reading the paper I felt that few modifications were made to handle very specific type of traffic and may have resulted in making the protocol very complicated. Moreover the experiments are run on a simulator thus the scenario may not be exactly the same as real-time traffic. The MILD scheme increases the counter interval by 1.5 times and decreases by 1. There is no mention about how these parameters were chosen. Do they need to be changed as per traffic pattern?

Scaling Internet Routers Using Optics

After reading the previous paper I had raised a concern that a centralized scheduler can cause problems and the authors in this paper discuss that removing the central scheduler can make the router more scalable. It is proposed that optics with zero power consumption can be used to place the fabric of a 100Tb/s router in a single rack without losing throughput guarantees.

The load balancing architecture provides an extra load-balancing stage that helps in spreading non-uniform traffic and making it uniform. Uniform arrival of packets have guaranteed throughput of 100% with fixed equal-rate switch that has virtual queues. The load balancing switch does not have a central scheduler but it requires a switch fabric of NxN that can be reconfigured for each packet transfer. To get rid of reconfigurations the switch fabric can be replaced with a fixed mesh of optical channels. Each fixed equal-rate switch can be replaced with NxN fixed channels. The mesh needs to be uniform if the traffic matrix is not known. Wavelength division multiplexing (WDM) can be used to reduce the number of fibers by having each linecard multiplex N WDM channels onto one fiber. FOFF (Full Ordered Frames First) is used to have packets leave the switch in order. Failure of linecards raises the need to scatter traffic in uniformly. The solution is to increase the number of paths M between local switches.

The architecture proposed in the paper removes the centralized scheduler and have a switch fabric that does not need to be reconfigured.

The paper was interesting to read but for me it was difficult to follow all the details given in the paper. I feel that I have not learned much out of this paper and there are lots of things that I have missed. Probably after tomorrow's lecture this paper will be more clear to me.

A Fast Switched Backplane for a Gigabit Switched Router

The paper discusses the need of switched backplanes to provide simultaneous transfer of multiple packets. Routers most perform datapath function (forwarding decision) on each datagram. Thus improving routers performance requires improving the performance of datapath functions. General trend in performance improvement involves implementing datapath functions at the hardware level, adding parallelism and replacing shared buses.

The author proposes using crossbar switch in which multiple line cards can communicate with each other simultaneously and this greatly enhances performance. He argues that very high speed shared backplanes are impractical because of congestion (since bandwidth is shared) and transfer capacity of a multiport shared bus is limited by electrical loading.

A crossbar switch gives high performance because the connections from the line cards to the central switch are simple point-to-point links and thus they can operate at high speed. Also, it can support multiple bus transactions simultaneously increasing aggregate bandwidth. It is simple to pass fixed-length cells across a switched backplane and they are chosen for providing better performance. Even though crossbar switches are non-blocking they experience head-of-line (HOL), input and output blocking. HOL is addressed by virtual queueing and prioritization mechanisms address the delay introduced due to input and output blocking.

Crossbar scheduling algorithm should provide high throughput, be starvation free, fast and simple to implement. The paper discusses iSLIP algorithm that is used by crossbar switches. Multicast traffic can be handled easily by closing multiple crosspoints simultaneously thus performing cell replication within the fabric.

It was insightful to see how the hardware of a router is designed to achieve better performance. Until now I had never thought about hardware techniques used improving router performance. I must say that the paper is written very nicely. I was under the assumption that since the paper is more about hardware I will not understand the paper very nicely. But the paper gave a very clear picture of what decisions were made and why. The paper should definitely be kept in the syllabus.

It seems that the centralized scheduler can become a bottleneck in case of high-speed traffic and cause delay.

Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism

This paper is mainly targeted for real-time applications. The authors propose that real-time traffic require guaranteed service or predicted service (adjust themselves based on the network delay). The architecture discussed handles both types of traffic.

Real-time applications are sensitive to data delivery delay, require delay information to set playback point, data should be delivered before its playback point and can tolerate only a certain fraction of packet losses. It is required that real-time applications get service as if they are the only one using the link and they should not be affected by other application traffic. Service commitments made to an end-user depends on the traffic commitment of the end-user.

For guaranteed traffic it is proposed to use token bucket filters to handle the rate of traffic while WFQ is used for scheduling. For the predicted services the authors propose FIFO+. To make both these algorithms work together guaranteed service flows are assigned as different WFQ flows while datagram/predicted service flows are assigned a pseudo flow 0. This flow has different priority classes and each class runs FIFO+.

The paper puts forward the need and requirement for servicing real-time application traffic. The discussion of predicted service shows that not all of the real-time traffic requires guaranteed service. One of the main weaknesses of the paper is the lack of concrete evaluation. Also, it has not been discussed how deployment will be handled. Techniques that propose changes to the Internet should always keep in mind the ease of deployment and the incentive for people to adopt the scheme.

Fundamental Design Issues for the future Internet

With the evolution of the Internet the requirements for service have changed dramatically. Moreover, there are different types of traffic that flow through the Internet. This raises the need to revisit the design and architecture of Internet and evaluate its performance. The author in the paper discusses some of these issues and also suggests the changes that can make Internet work in the future.

The authors say that the Internet was designed with having a single class of "best-effort" service with no admission control or delivery guarantee. Most of the applications can handle packet losses or varied delays but multimedia applications are not tolerant against these problems. To make real-time applications work well we can either change the application or the network implementation. Both approaches have their pros and cons and these are discussed in great length in this paper.

The goal of the Internet is to provide better performance to users. To make network more efficient it is more plausible to provide a service model instead of increasing bandwidth or providing separate networks for different types of traffic. Providing a service model raises the need of deciding which service to pick and who makes this decision. This decision can be implicitly decided by the network based on the packet information or an application can explicitly request a service. Explicit request must be used with incentives to encourage users to choose a correct service. Another issue that explicit approach faces is that the applications need to be aware of these choices. Any change in the service model requires updating all the applications.

Admission control is used by networks to avoid overloading. Over-provisioning Internet for special traffic (real-time applications) so that no admission control is required does not prove to be cost effective.The paper shows that the traditional applications worked efficiently with no admission control but with the real-time applications it is required to drop some flows for providing better efficiency.

The paper was very interesting to read because it put forward how the design of the Internet needs to be changed for special traffic. The design decisions change as Internet evolves. It will be nice to discuss whether some of the changes discussed in the paper have been incorporated in the Internet today. Also, with security coming into play we have to also take into consideration malicious users. We also have traffic from different types of network like wireless networks and sensor networks. These networks require different types of algorithms for providing efficiency.

Random Early Detection Gateways for Congestion Avoidance

Most congestion control and fairness techniques do not work well because they need large queue size for connections with large delay-bandwidth products, require global synchronization, have no isolation against unresponsive flows and are biased towards bursty traffic.

RED algorithm proposed by the authors tries to address these issues. Congestion avoidance is provided by controlling the average queue size. Average queue size is compared between two thresholds. When the average queue size is below minimum threshold no packet is marked while all packets are marked if average queue size is above maximum threshold. When average queue size is between minimum and maximum threshold packets are marked with probability p.

Queue size determines the degree of burstiness allowed by the gateway. Average queue size is calculated with an exponential weighted moving average and this aids in handling burst of packets. RED gets rid of global synchronization by marking packets at a rate that is as low as possible. Fairness is achieved by marking each connections packet based on its share of bandwidth.

I feel that the most challenging aspect of using RED is setting all RED parameters correctly. I am curios to know whether RED has been implemented in routers today? Even if it is implemented in the routers do the routers use this option? It will be interesting to see how RED performs today with such varied type of traffic.

Congestin Control for High Bandwidth-Delay Product Networks

XCP was designed keeping in mind the increased use of high bandwidth and latency networks. The authors argue that conventional TCP implementation and congestion control schemes falter in settings that involve high bandwidth links and large delays. Moreover with the growth of the Internet we now have a mix of networks that have varied bandwidth and delays. This raises the need to make sure that the transport layer protocol is stable in extreme scenarios and handle congestion control. Also, TCP biases against flows that has large round trip time and short flows get stuck in the slow-start phase.

XCP proposes to solve these problems. The authors propose modifying explicit congestion notification (ECN) and have routers inform senders about the degree of congestion at the bottleneck. They argue that a binary variable is not enough to convey congestion information. Sending rate of a source should be adjusted based on RTT and fairness should be independent of the number of flows. They also decouple utilization control from fairness.

Each XCP packet contains a congestion header that has H_cwnd, H_rtt and H_feedback. The sender sets H_cwnd and H_rtt. Routers along the path update H_feedback using EC (efficiency controller) and FC (fairness controller). EC uses MIMD while FC uses AIMD. The receiver copies H_feedback to ACK and the sender updates its CWND based on the feedback.

This paper was insightful to understand the requirements for high speed networks. How the current implementation of TCP does not cater to these requirements and what needs to be done. With the evolution of Internet happening at such fast pace we need to always keep in mind how current protocols scale with respect to today's requirements. I would recommend keeping this paper in the syllabus.

XCP outperforms TCP because it sends complete information of the degree of congestion instead of sending a bit signaling congestion. Decoupling FC and EC enables utilizing spare bandwidth and it also considers the delay in feedback while updating CWND. It is scalable because this does not require per-flow state to be stored at the routers.

One thing that seemed weird is that XCP is depending on the feedback sent in the ACK packet. The authors say that packet losses happen rarely but if a router is malicious or due to some other reasons that ACK is lost or it is modified then XCP can become unstable. Also, XCP is relying that the sender updates H_cwnd and H_rtt as per the rules. In case of an ill-behaved user XCP can be fooled to work incorrectly.

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

The authors in the paper argue that fair allocation mechanisms require complex operations to be implemented at the router level. These operations include maintenance of state per flow and performing operations on a per flow basis which are not suited for high speed network routers. The authors propose a technique called core-stateless fair queueing where the edge routers maintain per flow state and insert labels into the packets. These labels convey the estimated flow rate and are used by core routers. The core routers perform FIFO scheduling with probabilistic dropping of packets based on the packet labels.

Edge routers compute flow arrival rate using exponential averaging. The estimated rate of arrival of each new packet is computed from the inter arrival time, the length of the packet and the previous rate. At the core router fair rate is estimated from the algorithm of aggregated arrival rate and aggregated accepted rate which are updated on each packet arrival. In case of congestion at a router the packet labels are not correct and they need to be updated as minimum of old label and fair rate. The paper also discusses weighted CSFQ which supports flows with different weights. The authors show simulations comparing CSFQ with FIFO, RED, FRED and DRR.

The argument that laid the basis of the research involved reducing the complex operations performed by routers in order to achieve fairness. I am curious what is the current trend, do we use CSFQ type implementation or is DRR used these days. Also, are there scenarios where the estimations used in CSFQ do not work well in complex scenarios where flows come and go simultaneously and their life span is too short. The simulations show that CSFQ performs better with TCP burstiness but how long does it take to stabilize when multiple new connections are started.

I would recommend having this paper in the syllabus because it ties very well with the other reading for fair queuing lecture.

Analysis and Simulation of a Fair Queueing Algorithm

This paper discusses queuing algorithms implemented at the gateway and how fair queueing aids in congestion control. Queueing algorithms attempt to allocate bandwidth, promptness and buffer space. The most common queueing algorithm FCFS uses the order of packet arrival to determine allocation. On the other hand Nagle's FQ algorithm uses the concept of having separate queues per flow and service the queues in a round-robin fashion. The authors in this paper propose a FQ algorithm that is a modified version of Nagle's approach and discuss how their modified version resolves some of the drawbacks of Nagle's alogrithm.

Authors argue that bandwidth and buffer allocation per user changes based on what constitutes a user. A user can be a source, a receiver, process or a source-destination pair. The authors propose allocation on the basis of source-destination pairs because this fits well with respect to security and efficiency.

Nagle's proposed approach does not do fair allocation of bandwidth in case of varying packet sizes. This problem can be solved by sending packets in a bit-by-bit fashion but that has a lot of overhead. They emulate the bit-by-bit concept by servicing a packet that is going to finish transmission first if the bit-by-bit algorithm was used. This algorithm allocates bandwidth to competing flows fairly. No flow may be further ahead than another by more than the maximum packet size. Promptness fairness is addressed by giving less delay to packets from flows that are using less than their fair share of the bandwidth. The authors briefly describe several flow control algorithms used at the source and present simulations of using these algorithms in conjuction with fair queuing and FCFS and compare the results with reapect to throughput, RTT, number of retransmissions and dropped packets.

The paper was interesting to read and the simulations aided in understanding how FCFS and FQ perform when coupled with other flow control algorithms and with different type of source and different network settings. FQ algorithms proposed in this paper require complex operations to be performed at the router. The authors argue about this and give reasoning behind it. CSFQ algorithm proposed by Stoica et al. tries to address this issue. It will be nice to discuss the pros and cons of both these approaches and also talk what is used these days.

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

The authors say that congestion control and avoidance algorithms in computer networks fall in the general category of dynamic resource management problems. They analyze the algorithms based on metrics like efficiency, fairness, distributed nature, convergence time and size of oscillations. The analysis is done on analyze increase/decrease algorithms used in the binary feedback scheme. This scheme sets a bit in the packet to send feedback whether the resource is overloaded or underloaded.

The network performance graph in the paper shows the pattern of throughput as load increases. The point at which packets start getting lost is called a cliff while knee represents the point at which increase is throughput is very less compared to the large increase in response time. Congestion avoidance schemes try to keep the network to the left of the cliff.

In order to analyze the algorithms the authors show graphs that show the system state transitions in a 2 dimensional space depicting 2 users. The graphs aid in understanding the argument to a great length. The efficiency line shows settings where the total is equal to the maximum load while the fairness line is at 45 degrees depicting equal usage. The optimal point lies that the intersection of these two lines. The trajectory path of additive increase/multiplicative decrease converges to the optimal state. The authors then use rigorous mathematical proofs to show that in order to achieve fairness policy multiplicative decrease should be used while additive increase along with multiplicative decrease aids in maximizing fairness and efficiency at each feedback cycle.

I liked this paper because it explains the mathematical reasoning behind the algorithms used in computer networks. Reading such papers helps in finding the proofs behind the algorithms used in the field of networking. It is nice to have this paper in the syllabus.

The only thing that I did not like in the paper is that it does not assume things like delayed feedback and asynchronous operations. The authors discuss these issues in the paper very briefly but the settings have changed significantly since the time this paper was written. We now have different type of traffic flowing on the same link. Does this complicate calculation of congestion per link? Maybe for different types of flows the feedback signal should be interpreted differently. There are many questions like this that come up because of the current design and usage of networks.

Congestion Avoidance and Control

This is a seminal paper on congestion control for TCP. The authors say that the initial implementation of window-based TCP can behave wrongly in case of congestion. The algorithms proposed in the paper use the principle of "packet conservation" to gain network stability. Conservation principle means that when the connection is running stably with full window of data being transmitted, no new packet should be put into the network until an old packet leaves the connection.

Three problems that violate packet conservation: (as stated in the paper)

1. The connection does not get equilibrium
2. A sender injects a new packet before an old packet has exited
3. The equilibrium cannot be reached because of resource limits along the path
   

Solution for problem 1 is proposed by the slow start algorithm. This algorithm is used to start self-clocking systems. A self-clocking system generates packet at the rate at which acks are sent. It is difficult to start a self-clocked system thus the slow start algorithm gradually increases the amount of data in-transit. Per-connection variable 'cwnd' variable is set to 1 in case of a start or restart and is incremented by 1 in case of an ack.

Problem 2 is addressed by improving the retransmit timer. In order to survive heavy loads the timer should consider variation of the round trip time as well. Variation estimates help in eliminating unnecessary retransmissions. Also, exponential back off after retransmit aids in stabilizing an unstable system

In order to address problem 3 the authors say that if the timers are working correctly then in case of a packet loss the main reason can be congestion (given loss due to physical damages are rare). For congestion avoidance a additive increase and multiplicative decrease algorithm is proposed. At the end the authors discuss how congestion control at the gateway is required for fair sharing of the bandwidth.

Relevant background needed for this paper requires a good understanding of TCP protocol and its working. Most of the algorithms discussed in the paper are used today and have a great impact on Internet. With the growth of the Internet one of the main problems that had to be addressed was congestion control and avoidance. This is an early paper that proposes how to solve the major concerns. It also shows how problems in computer networks were actually well-studied in the context of control theory and queuing theory.

Another aspect that comes into picture after reading this paper is about security. These algorithms rely on the fact that the receiver is not misbehaving. There is a paper by Savage et al. that shows how a misbehaving receiver can make the sender go fast without losing end-to-end reliability.

This paper should be kept in the syllabus because the algorithms proposed lay the platform for the congestion control algorithms used these days.

On Inferring Autonomous Sytem Relationships in the Internet

Understanding AS relationships in the Internet can be useful to provide a deep understanding of traffic flow and also aiding ASes to make policy changes for improvement. Unfortunately these relationships are not known. The paper proposes generating an augmented AS graph that will represent the relation between ASes as customer-provider, provider-customer, peering and sibling relationship. Gao suggests that these relationships can be inferred from BGP routing table entries.

The author says that export policies depict the kind of relationship between ASes (export policies are explained in the previous post on interdomain routing). Based on the export policies the author explains a selective export rule and says that if the export policies adhere to the selective rule then the AS path of a routing table entry is Valley-Free. Valley free property states that after traversing a provider-to-customer or peer-to-peer edge the AS path cannot traverse a customer-to-provider or peer-to-peer edge. Routing table entry patterns have been classified as downhill path, uphill path, maximal uphill path and maximal downhill path.

The heuristic algorithm proposed in the paper rely on the assumption that a provider is larger in size than its customer and the size of an AS is proportional to its degree in the AS graph. In the AS graph, top provider of an AS path is the AS that has the highest degree among all ASes in the path.

The background needed for this paper requires a good understanding of BGP and the export and import policies. The Interdomain Internet Routing lecture reading is perfect to read before reading this paper.

The results provided in the paper are very promising with an accuracy of almost 99.1%. I was not very happy with the way the paper was written. It was little difficult to follow the proofs. Moreover I am curious to see how this method worked on other data. I have a feeling that the refined algorithm that handles misconfiguration by setting a value L may cherry pick a value.

I think it will be nice to discuss some other algorithms that were designed after this paper since this paper was the first one in this area of research . Also, how this research has benefited ASes, customers or providers in the real world. Overall the paper was an interesting read and is nice to have in the syllabus because it ties very well with the routing policies of BGP.

Interdomain Internet Routing

This lecture reading gives a description of how communication between different ASes work in the Internet. The lecture in the beginning shows real Internet routing infrastructure diagram compared to the general image that people have. Internet infrastructure involve a large number of commercial entities (ISPs) that provide Internet service and cooperation is required between these entities to provide global connectivity. ISPs are categorized as Tier1 (global scope), Tier2 (regional scope) and Tier3 (have small number of localized customers).

The routing architecture uses the concept of ASes instead of ISPs. ASes are managed by a single ISP though there can be multiple ASes in an ISP. Border Gateway Protocol (BGP) is the protocol that is used between ASes (by their border routers) to share reachability information for achieving global connectivity. Within an AS Interior Gateway Protocol (IGP) is used. IGP includes protocols like OSPF, IS-IS and RIP. BGP is designed to be scalable while IGP concentrates on optimizing path cost.

There are two kinds of AS-AS connection types: Transit (provider-customer, involves financial agreement) and peering (generally does not have a financial agreement). Rules for routing information:

• Exporting routes:
• Provider sends customer routes to every AS (customer, provider, peer).
• ASes generally do not share provider routes.
• Peer ASes share their transit customers routes and internal ISP routes with peers
  
• Importing routes
• Customer routes are preferred over peer route and peer routes are preferred over provider routes. LOCAL PREF attribute is used to implement this priority.
  

BGP was designed with three goals in mind: Scalability, Policy and Cooperation. BGP does not optimize over path cost. Rather, it has a set of attributes that are used to make the decision. These attributes are Next Hop, AS Path, Local Preference and Multiple-Exit Discriminator (MED). AS Path attribute includes AS identifiers of the ASes the route advertisement message has passed through. MED is used for comparing two or more routes from the same AS. MEDs are generally used to allow enforcement of cold-potato routing.

BGP has two flavors:

1. eBGP - this runs between BGP routers in different ASes.
   
2. iBGP - this is run between BGP routers within an AS. The topology used for iBGP is full-mesh but that can have scalability issues. Two methods used to solve this problem involve using route reflectors or setting up confederations of BGP routes.

There have been security issues related to BGP like DoS and issues due to misconfiguration. Some limitations of BGP include no authentication of route attributes and tampering of route information. Also, from the reading it wasn't clear what export and import policies are applied between two ASes that have the same provider.

It will be nice to have a small discussion about the security issues and how people have addressed them. Another thing which confused me in the beginning was the difference between iBGP and IGP. It was not very clear when is IGP used and when is iBGP used.

I really enjoyed reading it because before this I did not know about the internals of BGP and how routing between commercial entities took place. In fact I really liked the way the lecture explained how selection of routes is directly tied to the economic model. Hot-potato routing and route export and import policies were interesting to read. This reading is a must for the class.

The Design Philosophy of the DARPA Internet Protocols

This paper discusses how the TCP/IP protocol design decisions were made. The main goal of the protocol was to interconnect existing networks and other new networks that emerge. Store and forward packet switching technique was used to address this requirement. The structure of the Internet was a network of multiple networks communicating using packet switching and using gateways that use store and forward packet forwarding.

Secondary goals included survivability, support for different types of services, accommodating variety of networks and management of resources. The paper introduces the concept of fate-sharing for survivability. In the fate-sharing model where endpoint is responsible for storing the state information for any of its communication. In the beginning it was thought that TCP would be general to provide support for any type of service. Large number of varied service types caused the split to have TCP and IP. TCP provided reliable sequenced data stream while IP proved to be the basic building block for all types of services. UDP was created to provide datagram service. It was decided to have flow control and acknowledgment in TCP based on byte number.

It was required for the Internet architecture to support variety of networks. This is achieved by making very few assumptions like the network can support packet or datagram, the network has some suitable form of addressing. Some of the drawbacks of the Internet are lack of tools for doing management of resources, high cost for attaching a host to the Internet, poor implementation of the methods and lack of accountability.

The current design of the Internet is influenced by a lot of factors. Packet switching was chosen because most applications at that time fitted well with this scheme and also most of the networks were packet switching networks. Although after the design it has been seen that circuit switching properties are being included in the current architecture (MPLS). Stateless nature has brought up issues related to accountability (IP spoofing). It will be nice to have a discussion regarding what design decisions would have been made if Internet was designed today.

It was really informative reading the paper. Quite a few of us have read about the protocols and mechanisms used in the Internet but did not now what led to the design of these. These kind of papers help in understanding the reasoning behind why things are the way they have been. I would highly recommend having this paper in the syllabus.

End-To-End Arguments In System Design

The paper argues about the placement of functions at higher level instead of providing them at low levels in a distributed system. The argument is supported by a detailed example of file transfer between two machines. Things that can go wrong during the transfer range from file corruption due to error in copying or buffering, hardware processor or memory transient error, loss or corruption of data in packets etc. One might think of addressing these problems at the lower level by providing duplicate copies, timeout and retries at each step. Even though the lower layers may provide correction mechanism but still the end system will have to perform end-to-end check for corruption during file reading or copying and host crashing. Thus, having the lower layer provide checks proves to be redundant and more of an overhead.

The argument is also supported by giving other examples like delivery guarantees, secure transmission of data, duplicate message suppression, FIFO message delivery, transaction management and encryption. End-to-end argument does not work in case of applications that require reliable delivery of message. In this case it is better to have checks for reliability at the lower layer than provide it at the application layer. Application layer checks will require retransmission of the complete message thus proving to be more expensive.

The end-to-end argument varies as per the requirement of the applications. It lays a good ground for layered architectures and is one of the main design principles used for Transport Control Protocol. Although the argument proposed in the paper is against the general notion of trying to put everything at the lower layer, but the supporting points given for the argument are relevant and make sense.

I feel that even though the argument and examples in the paper are relevant but providing everything at the higher layer may prove to be a drawback. This can raise security concerns. Programs at the application layer can be tampered with and may not run as expected. This is one of the issues that TCP faces. TCP Congestion Control with a Misbehaving Receiver paper by Savage et al. talks about how clients can misbehave and what should be done to address these problems.

The paper should be kept in the syllabus because it puts forward the issues one should think about before making a design decision. It also helps a person in understanding the decision made behind the TCP/IP protocol layered architecture. I also liked the paper presentation. The argument proposed by the author is supported by giving examples.