Paper Review #9: Controlling Queue Delay

A CS 255 Paper Review for  Controlling Queue Delay by Kathleen Nichols and Van Jacobson

In one of the past papers, we were able to see the RED (random early detection) model for congestion avoidance and the tail drop mechanism which have also been widely discussed in class. In these topics, queues have always been mentioned and it gives the impression that congestion results to queues but could also be the other way around, congestion happens because there are a lot of incoming packets from queues.

This paper presents a refreshing take on congestion avoidance and queue management. It clearly explains why queues exist and what are their original purpose – as shock absorbers for burst allowing for a smooth departure. Initial mechanisms, such as the first version of RED, were made in hopes of solving this congestion problem. But issues in usability, configurability, and user-friendliness was a hindrance for RED fully taking off. Succeeding AQMs inspired by RED were more complicated which made them not take off as well.

A lot of AQM (active queue management) systems have been developed but their success was hampered by their own misconceptions and wrongly perceived problems on the cause and meaning of queues. Since they are based on a wrong conceptual model – problems that were tried to be solved were actually not the root causes but could just be side effects or might not be related at all (solutions such minimizing bandwidth size, queue length, etc). Also, the need for dynamism in configurations is necessary as it is not impossible to pick a static size for all the metrics.

The paper was also full of helpful illustrations like the one below. It shows that when data comes through a bottle neck, from being the original vertical bar (height is in bits, width is in time), it stretches itself into a horizontal bar once it passes through the bottle link representing that it will take more time..

Screen Shot 2015-11-21 at 12.37.36 PM.png

Simple as it is, but I think this is really a good illustration on how bottlenecks affect queueing. And how when they return after 1 RTT, the packets are now spaced. Equality of arrival rate to departure rate has been achieved.

Another comprehensive but simple and easy to understand illustration was also shown where the queue does not go to zero but remain steady. This is where window is 25 (5 more than what can actually fit), standing queue. The standing queue created delays but no improvement in throughput since the excess packets can’t really be served.

Screen Shot 2015-11-21 at 12.38.07 PM.png

As the paper says, this is usually tried to be solved by limits imposed by providers to consumers (usage limits / penalties) but these don’t actually help much at all.

Queue, in its own essence, are not actually bad since they act as shock absorbers for bursts. Bt what makes a queue bad is if it stays long – more than 1 RTT. Queues that dissipate after 1 RTT (after a smooth and steady departure) are acceptable and are good!

In efforts to improve on the old RED algortihm, a new RED algorithm came up that required only one parameter: queue output bandwith / average departure rate. But again, it still has bias against bursty traffic.

As the paper defined, a good AQM is parameterless ( no need for configs to be manually set), dynamic (adapts to network situation), allows for bursts, and simple yet efficient. With these, CODEL (Controlled Delay) was introduced together with 3 of its innovations,  the use of a local minimum queue, a single state variable, and a packet sojourn time (actual delay experienced) made it efficient, dynamic, and flexible.

The paper also described well its simulation environment – use of NS2, CUBIC for file transfer, PackMime for web browsing emulation, SACK was also used and the Jain index for measurement of fairness.

The results showed that RED and CODEL had almost the same delay when bandwidth was  < 3 Mbps but CODEL had a little more when the bandwidth was higher. But for utilization, it was significant that CODEL had much more. This might be because in the recent improvement for RED, RED became more controlling that’s why the network was not utilized to its full capacity.

In comparison to Tail Drop, on the other hand, Tail Drop has almost the same utilization but CODEL has significantly lesser delays than Tail Drop which almost had delays all through out

Screen Shot 2015-11-21 at 12.38.58 PM.png

In terms of fairness, CODEL won too as the newer version on RED already employed a less random mechansim in choosing which packets to drop.

Overall, the paper presented the concepts very well and was very good in using illustrations — tables, graphs, pictorial representation to supplement understanding and visualization.. It also explained very well the original purpose of queues which enables the reader to fully appreciate the presence of queues and need for managing them. Comparisons to present and past mechanisms were also made. The paper also provided explanations and results as to why CODEL is better. Pending real life concerns such as where to implement these were present as well.

Definitely one of the greatest reads I had for this semester! 🙂

 

 

Illustrations from the Paper Controlling Queue Delay by Kathleen Nichols and Van Jacobson.

Paper Review #8: A Generalized Processor Sharing to Flow Control in Integrated Services Networks: The Single Node Case

A CS 255 Paper Review for  A Generalized Processor Sharing to Flow COntrol in Integrated Services Networks: The Single Node Case by Abhay K. Parekh

In our tech-savvy world today, we see and use a variety of network traffic types (realtime games, video, audio, chat, etc) in our every day lives. Because of this, network flexibility is becoming a primary concern to network providers and administrators. With the needed flexibility, other important network aspects such as performance guarantees and fairness should still not be compromised. Fairness such that other users’ experience should not be degraded just to serve a more demanding traffic on another. Flexibility such that the network can give different performance guarantees to different customers depending on their needs and demands in the network.

These concepts, concerns, and solutions were widely tackled in the paper A Generalized Processor Sharing to Flow Control in Integrated Services Networks: The Single Node Case by Abhay K. Parekh. The use of the Generalized Processor Sharing (GPS) together with leaky buckets was given focused especially on its ability to provide flexibility as well as worst case performance guarantees. The paper assumes that rate admission control is done in the leaky buckets as it shapes incoming traffic.

GPS, in its vanilla version, does not transmit packets as entities but instead assumes that packets are infinitely divisible. With this limitation came another variant: the GPS with leaky bucket that operates on packets called the Weighted Fair Queueing or PGPS (Packet by packet Generalized Processor Sharing).

Proofs and lemmas were shown where appropriate to better strengthen the concepts being discussed.  The paper is also effective in uniting and connecting two separate proofs to arrive at another final conclusion.

A comparison of PGPS to other schemes such as the virtual clock multiplexing by Zhang was tackled next. The virtual clock multiplexing provides a guaranteed rate as well but what makes it different from PGPS is that it has a bias against bursts even if network load is light. A helpful numerical example was given for this concept:

Screen Shot 2015-11-18 at 11.20.01 AM

At time 0 to 900, only session 1 is using the network but on t = 901 onwards, another session, session 2, also started transmitting in the network. In this setup, at 901, only connection 2 will be served with virtual clock multiplexing. Only until all of its packets have been transmitted will connection 1 be served again. Connection 1 was “punished” for having solely used the network during 0 – 900 even if it was not in the expense of session 2 or any other sessions. In contrast to this mechanism, PGPS uses a round robin fashion in determining who it will serve next in the event that multiple sessions are needing network throughput ensuring that everyone get’s their network share in a limited amount of time.

Leaky buckets were widely discussed next and how it is able to bound busy system periods. Sessions are provided with tokens which they can use to transmit. As long as tokens are still available, sessions are free to transmit in the network.

Overall, the paper provided a very comprehensive and technical discussion on generalized processing systems (and its per packet counterpart) as well as on leaky buckets. Proofs, lemmas, graphs, and illustrations were very helpful to prove and elaborate on different major points and concepts. The paper could have also capped off its technicality with a brief conclusion summarizing its main points but this is only minor as the introduction had already given an overview of what the paper is all about. 🙂

 

Paper Review #7: Random Early Detection Gateways for Congestion Avoidance

A CS 255 Paper Review for Random Early Detection Gateways for Congestion Avoidance by Sally Floyd and Van Jacobson

The paper comprehensively discusses Random Early Detection (RED) gateways for congestion avoidance.This algorithm notifies connections of congestion either by dropping packets or tagging each arriving packet (by setting a bit in the packet headers) randomly with a certain probability if the average queue length is between a given range. A probability such that it is proportional to the connection’s share in network throughput. RED gateways are designed for transport layer protocols that respond to congestion through marked packets (either dropped or with the congestion bit set). It was also mentioned that even if the transport protocol is not cooperating (it still floods the network even with congestion), the RED algorithm can still control the average queue length since it can drop the non-cooperating connection’s packets.

The paper also extensively compared early models of early detection congestion avoidance mechanisms and how each performed in various scenarios. The two most discussed mechanisms were Early Random Drop and Drop Tail gateways. The Early Randrom Drop gateway is almost the same as RED but it uses a  fixed probability (i.e. does not adjust to network throughput) in determining which connection to notify. While for Drop Tail, on the other hand, since packets are dropped from several connections, global synchronization is introduced. Global synchronization is where multiple nodes receive the congestion notice so they all decrease their throughput at the same time, thus falling below optimal utilization of the network – a scenario that must be avoided and has long been studied.

Another congestion avoidance scheme that was thoroughly discussed and compared with RED is the DECbit congestion avoidance scheme. In contrasts to RED, DECbit marks all incoming packet when there is a congestion (RED select randomly with probability). Because of this, the receiving transport layer protocol still have to compute if the fraction of the received bits are enough to imply congestion. The arking overhead issue was also brought up with DECbit as it tags all incoming packets.

network-congestion-vpisystems.png

Hope there’s also a RED algorithm for traffic congestion.

Next,  the Design for the RED algorithm was presented. One of the highlights was flexibility through the parameters min, max, and average wherein the first 2 can be controlled and set by the system administrator. This flexibility also was complemented by the paper’s provided guidelines in choosing the right values( i.e. the minimum should not be too low that it would already lead to low network utilization, while the maximum must be high enough to approximate bursts but not too high that it won’t be able to prevent congestion).

The paper also did not lack in discussing the implementation details such as employing parallel computation so as to not consume much computation time especially in networks where a lot already happens in a split second. And how RED will tag all arriving packets if the average queue length is already way past the given maximum threshold.

Elaborations on actual network issues such as bursts (and what are the most like reasons behind them) and misbehaving users (users who still consume a large chunk of the network even if network congestion notice has already been sent) and how RED respond to these scenarios capped off the entire paper with a feel of real life applications and solutions.

Overall, the paper was a great and comprehensive read on the Random Early Detection gateways for congestion avoidance. Motivations behind, related mechanisms, design, and implementation details were thoroughly discussed and tackled. There was also an abundance of graphs, formulas, and chunks of pseudocode which made understanding the paper easier.

Photo from: community.michelinchallengebibendum.com

[ CS 255 ] Project Idea

Project idea for CS 255, 1st Sem 2015-2016:

Paper: Applying Ceritifcate-Based Routing to a Kademlia-Based Distributed Hash Table
Authors: Michael Kohnen, Jan Gerbecks, Erwin P. Rathgeb

The paper discusses the effects of a binary trust system in structured P2P systems specifically on a Kademlia-based Distribution Hash Table. A Kademlia-based DHT poses only a few routing restrictions and is widely used in networks today (i.e. BitTorrent).

The binary trust system the paper describes is employed with the use of certificates, where nodes, to be considered trustworthy, should be certified. Having a central certification authority may not be aligned with the peer-to-peer principle but the authors argued that if a DHT won’t work under these very simplified conditions, what more in reality.

One of the paper’s future work recommendations was to develop a non-binary metric for reputation and trust (i.e. trustworthiness and/or maliciousness of nodes). With this, I would like to further extend the paper by looking into applying non-binary metrics for trust and reputation and analyze their effects in the routing and storage mechanisms of structured P2P networks, especially on a Kademlia-based DHT. Some of the non-binary metrics that could be applied are:

  1. Peer reputation
  2.  File reputation
  3. Evaluation reputation

With these metrics, it is not only the peers that are checked but also the files that are being shared as well as their evaluations in light of improving system security.

Other reference papers:

  • Paper:  Kademlia: A Peer-to-peer Information System Based on the XOR Metric
    Authors: Petar Maymounkov and David Mazieres
  • Paper: A Reputation Management System in Structured Peer-to-Peer Networks
    Authors: So Young Lee, O-Hoon Kwon, Jong Kim and Sung Je Hong
  • Paper: Reputation Management for DHT-based Collaborative Environments
    Authors: Natalya Fedotova and Luca Veltri

[ Review #6 ] Bumps Along The Way

Week 2 | Review of Understanding BGP Misconfiguration by Ratul Mahajan, David Wetherall, and Tom Anderson

Any system intended for good use can cause disruption when misconfigured or not used properly and with care. The Border Gateway Protocol (BGP) is no exception. The paper Understanding BGP Misconfiguration looks at misconfiguration errors with BGP and aims to determine how frequent they happen, what the usual causes are, how big their impact is, and how could they be lessened.

The paper’s quantitative nature (it claims to be the first quantitative study on BGP misconfigurations) is evident through the paper with the inclusion of tables and graphs which made analysis and comparison with the numbers easier. Misconfigurations are often times not reported (and even not detected as they don’t always result to connectivity issues) except for a few that landed in news articles due to the widespread outage and/or network disruption they have caused. With this challenge, the paper have thoroughly documented the methodology and data used. Historical data on a 3-week period from 23 different vantage points were used to observe traffic and determine abnormalities. They have contacted the ISPs involved to verify if the abnormality was in fact a misconfiguration. Due to the staleness of the data, 30% of the emails bounced or got accepted by the wrong person (no longer connected to the company or not connected at all). Nevertheless, for the responses, the paper have reported that even with limited data, the answers of the limited correspondents still converged to the same things.

The paper looks at BGP misconfiguration problems and mainly classified them into 2 (import and export) and further subdivided them into 2: slips and mistakes. Slips were defined to be an error in execution of a correct plan while mistakes, on the other hand, are errors that have originated early in the planning and even if the plan was executed correctly, errors would still exists.

For most of the instances, it was human error that caused a huge chunk of misconfigurations. TO address these, several solutions were proposed to aid the human operator in making less mistakes. This included the proposition of a more friendly interface, the ability to set up configurations automatically, an easier way to detect if configuration errors have gone wrong, etc.

Aggressive error reporting and detection was also one of the proposed solutions. As what the paper has always reiterated, most errors are left undetected (since they just fail silently or erroneous packets are just dropped) unless a connectivity error arises or network administrators turn off filters in special scenarios.

Overall, the paper provided a comprehensive view of BGP misconfigurations, its types and classifications, usual causes, and possible preventive solutions. There was a part in the paper though that I felt loss in differentiating exports and import misconfigurations (maybe that was just me though). Maybe a thorough introduction and explanation on imports and exports and a concrete example of these types of misconfigurations before diving in the actual numbers and comparison would be more helpful. The succeeding examples, tables, graphs, and actual measurements were very helpful in analyzing how the different errors compare and how one is more frequent or more disruptive than another. The paper has also described very well the methodology used and how results were obtained, as well as its scope and limitations.

[ Review #5 ] Around the World in A Millisecond

Week 2 | Review on Interdomain Internet Routing by Hari Balakrishnan

The internet is such a vast architecture whose view of its internal workings have already been simplified to us, users. For example, as you are reading this, dear reader, hundreds of packets are travelling hundreds of miles around the world, passing through routers and getting carried through by links. The paper Interdomain Internet Routing discusses what’s happening behind the scenes of the internet – how your requested content from the other side of the world arrives to you in a split second!

This paper is a really nice read after having read the past 4 papers* that discussed how distributed (rather than a single centralized) administration was one of the original goals of the internet and is fortunately still being preserved through the years. Distributed management allows administrative borders possible between networks which then allows these networks to have their own rules and policies governing their respective spaces. This division also calls for a system with a set of rules and protocols to manage the exchange of messages between each network.

This paper discussed a lot about addresses and how they allow delivery of messages to their intended destinations. The paper also described topological addressing (use of prefixing such that addresses could be chopped to segments to determine to which intermediary router it should be sent first) which allowed communication and routing between millions and billions of network possible.

It was also interesting to know that there exists a “competitive cooperation” between different domains (a.ka. Autonomous Systems) in the pursuit of profit and interconnection. Despite competition, there is still the need to cooperate and communicate which forced them to make compromises and still find a way to become profitable.

Two kinds of relationships that exist between networks were then discussed. These are transit and peering. It’s just notable that terms have actually developed to describe these kinds of relationships which just shows that there was great necessity to define these relationships especially in contracts and financial settlements. With these relationships, the paper have also expounded on the different instances by which ISPs would prefer to prioritize one request over another in the pursuit of making money, saving money, and pursuing their own benefit.

The Border Gateway Protocol (BGP), which allows interconnection between different autonomous systems, were also widely discussed. It is interesting to also know that there actually exists two types, eBGP (external) and iBGP (internal). The paper made a good point to clear out that iBGP is not the same with Internal Gateway Protocols (protocols which are responsible for path metrics inside the same network). And these two types of BGP (whether internal or external) are still the ones responsible in knowing the addresses of the external domains they’ll be connecting on. Different attributes such as NEXT HOP, A SPATH, LOCAL PREF, and MULTIPLE-EXIT DISCRIMINATOR, were also discussed to give a view on how networks prioritize and determine as to which router it will route the message next.

Overall, the paper provided a great overview on how different domains allow routing to and from them and the many factors that affect their prioritization and willingness to do so. The paper also never failed to give an insight to the current situation and scenario, the problems that have arose and the solutions applied. Mistakes and intentional attacks are not foreign in the Interne such as the real life example of Youtube being inaccessible to consumers due to a single person’s error and the lack of control and checks in succeeding entities where the error got passed on. This just emphasises the fact that at the end of the day, we are still interconnected and one’s error and wrongdoing could affect the whole world.

Because at the end of the day, our actions are still interconnected to one another wherever domain we belong.

On a one last note, the line “… good technical research can be be shaped and challenged by commercial realities” hit me the most and made me realize that each domain in the network (and even in life) have their own motives and agendas and these affect their decisions in different scenarios. As what the past papers* said, investment and funding affect the direction as to which network development is going.

P.S. I just remembered that this paper could also be related with the current Internet scene here in the Philippines – in the news, many groups have already expressed concern regarding our Internet connectivity which is super slow and whose service quality is below par yet but whose prices are already skyrocketing.

ASEAN Internet Speed

Based on the ASEAN Internet Speed Survey of 2014, the Philippines have the slowest Internet in Southeast Asia, and the 2nd in whole Asia.

Photo from ASEAN DNA.

Some people have attributed this problem with ISP monopoly where, according to them, many ISPs are actually owned by only 3-4 business conglomerates. Despite these, it is still heartwarming to know that there are efforts in making the Internet available to everyone here in the country, such as WifiNation and Internet.org’s launch here in the Philippines.

Another P.S. (Aug 22, 2015, 12:01 AM): Just came across a Youtube link to the live streaming (c/o Rappler) of the Senate Hearing on PH Internet speed last August 18, 2015.

[ Paper Review #4 ] Casting the Net into the Wider Ocean

A Paper Review for “Rethinking the design of the Internet: The end to end arguments vs. the brave new world” by David D. Clark

David D. Clark’s Rethinking the design of the Internet: The end to end arguments vs. the brave new world  looks at the internet’s evolution through the years which has gone from being a military tool to something that is now commercial and more consumer oriented. This evolution is vastly influenced by a growing user base with varying motivations and purposes in using the internet.

The desire of the rising third parties (i.e. government, ISPs, organizations, etc)  to be involved so as to manage and control the internet has also pulled the internet evolution into many different ways as well.

The end to end argument, one of the major design philosophies behind the original internet structure, was the paper’s main backbone in showing the reader how the internet has evolved and how it continues to evolve. The end to end argument states that the responsibility for additional features should be handled via the end hosts and only minimal extra work should be done by the network core though different needs and wants of the different sectors of the society today (i.e. need for protection – anonymity and accountability, need for accommodation of more advanced applications, need for ISP service differentiation, need and want of third-parties to get involved) gear the Internet away from the end to end argument and shift its development to a design where most of the work is done by the network core and less is done by the end-users.

Instances of the the internet’s misuse and abuse has also lead to users’ erosion of trust, the most fundamental change that is evident today. Many users are now more conscious of their security and privacy, desiring for anonymity but at the same time, also of accountability. Consumers have also been vigilant that it is not only the network that could be dangerous but also the hardware and software that they own.

The rise of third parties also had a great gravity on where the internet is heading. Governments wanting to track citizen activities for security, taxation, and surveillance purposes, organizations claiming their right for transmitted data (i.e. copyright, fee, collection, etc), and ISPs being our gateways and determinants of what kind and type of service is accessible just show the rich objectives of the society and the various, but sometimes contradicting, values they employ.

On a positive note, the use of third parties can also address the need for security by verifying the communication between two parties (i.e. with the use of public key certificates, etc). But with this solutions comes another dilemma, how could end users be sure that it is really the third party verifying the communication?

The effect and importance of laws for the cyberspace have also been thoroughly discussed as a possible major tool in protecting users of the internet (i.e. laws that impose strict compliance of data labelling rules) and as a driving force to lessen (if not fully eliminate) its misuse and abuse.

The paper concluded with an assessment of where we are right now and a suggestion that we don’t need to drift completely away from the end-to-end argument but instead we can build a set of principles that interoperate with the end-to-end argument as well as new principles to address the current situation and community the Int.

The paper has thoroughly discussed the current situation in the Internet today and was able to compare how it was before to how it performs now and if it still aligns with the basic guiding principles and design approaches of the initial creators. This comparison is helpful to the reader in seeing the different factors that shaped the Internet. Citing real life examples and scenarios was also helpful in helping the reader relate to the paper. 

Indeed, there exists a tug of war between the different key players in the Internet (users, government, ISP, organizations, investors, etc) in influencing one’s experience with the Internet. There are those who impose rules and there are those who evade them, there are those who want to be anonymous, and there are those who want accountability disclosed. With these driving forces, it is exciting to see where the Internet will be 10 years from now, scary to think of the possible abuses people can do with it, but also hopeful to think of the possible defences and benefits it could give its users in the future.