The internet has always been structured to give "best-effort" service. It deliver packets in the most efficient or fair manner, in the protocol design point of view. However, the author argues that the best network design should be sensitive the application requirements that may be different for everyone. The overall performance of the network is measured by the sum of the utility functions for each app. Utility functions take delivery delay as parameter (i.e. each app has a different sensitivity to delay).
The way to maximize these utility functions is to extend the existing "best-effort" service model by incorporating other kinds of services. For example, the paper mentioned elastic, hard RT, delay-adaptive RT, and rate-adaptive RT. There are potentially more that would even depend on parameters other than delay.
There is simple analysis of suggesting how to extend the service model. It shows having multiple homogeneous service networks is less efficient than having heterogeneous service networks. This seems counter-intuitive at first. It seems there can be more optimization opportunities in a homogeneous setting (i.e. more assumptions can be made). In terms of RT and non-RT scheduling, this suggests that the two actually complements each other. For example, datagram service can fill up the leftover BW of the RT traffic.
The choice of having admission control or overprovisioning is a concern for future network design. On one hand, overprovisioning affects application performance. But having admission control is nice because one can avoid potentially all overloading (or congestion).
I like the paper. It presents the big ideas for future network design. Although the analysis were quite simplistic, it does illustrates the design issues.
Thursday, September 18, 2008
Supporting Real-Time App in a Integrated Services Packet Network: Architecture and Mechanism (MIT)
The paper introduces the idea of Integrated Services Packet Network (ISPN), which allows real-time (RT) and non-RT traffic to share bandwidth. It classifies three types of services: guaranteed, predicted, and datagram. Guaranteed is real-time service that has a hard deadline of delivery. Clients need to declare a usage rate before being admitted into the network. Predicted is more like "soft" real-time, where the delay bound of delivery is assumed to be adaptive and adjusted by previous experienced delay. Datagram is relatively time-insensitive but is reserved with some minimal amount (10%, chosen in the paper) of BW to ensure progress.
Jitter is a main problem in RT services. Many reasons lead to jitters. The transport layer, in particular, induces jitter from multiplexing packets from different sources. Packets get delayed because of delivery of packets of other unrelated sources. This is the commonly known side-effect of sharing. Interestingly, the author suggests that jitter can be minimized if sharing is prioritized.
Isolation is inevitable for hard real-time services, but isolation is expensive. Providing a integrated service can be seen as tradeoff between cost and performance. At the same time, users can easily switch between RT and non-RT servicing. This may allow future applications to have a more dynamic and finer-grained timing behavior.
For soft RT and non-RT servicing, the author proposes FIFO+, which incoporate the concept of priority into FIFO, to mimize the max delay (jitter). It uses the expected instead of actual arrival time. The expected arrival time is driven by the packet's deadline.
Priority can be set at different granularity. The common way is to associated a priority number with each connection link. In multihop environment, the paper suggests that priority of packets can change at each hop. This leads to a more dynamic and flexible scheduling, since packets can now "accelerate" to catch up with their deadline.
The paper is nice in that it shows a new dimension, timing, in network service. It also shows how to incorporate this new "stricter" service with the traditional services.
Jitter is a main problem in RT services. Many reasons lead to jitters. The transport layer, in particular, induces jitter from multiplexing packets from different sources. Packets get delayed because of delivery of packets of other unrelated sources. This is the commonly known side-effect of sharing. Interestingly, the author suggests that jitter can be minimized if sharing is prioritized.
Isolation is inevitable for hard real-time services, but isolation is expensive. Providing a integrated service can be seen as tradeoff between cost and performance. At the same time, users can easily switch between RT and non-RT servicing. This may allow future applications to have a more dynamic and finer-grained timing behavior.
For soft RT and non-RT servicing, the author proposes FIFO+, which incoporate the concept of priority into FIFO, to mimize the max delay (jitter). It uses the expected instead of actual arrival time. The expected arrival time is driven by the packet's deadline.
Priority can be set at different granularity. The common way is to associated a priority number with each connection link. In multihop environment, the paper suggests that priority of packets can change at each hop. This leads to a more dynamic and flexible scheduling, since packets can now "accelerate" to catch up with their deadline.
The paper is nice in that it shows a new dimension, timing, in network service. It also shows how to incorporate this new "stricter" service with the traditional services.
Tuesday, September 16, 2008
Congestion Control for High Bandwidth-Delay Product Networks ('02)
The paper proposes the Explicit Control Protocol (XCP). It aims to address issues that TCP is not good at. For example, TCP is not very efficient in filling up the available bandwidth (not increasing fast enough) in high bandwidth environment. TCP has bias against high latency links because its throughput is inversely proportional to RTT.
XCP is a end-point AND gateway solution. Explicit congestion control information is exchanged between the end hosts and routers. The fairness controller (FC) and an efficiency controller (EC) are purposely separated for simplicity and modularity (separation of concerns). However, EC augments the feedback responses produced by FC. There is potentially a fixed-point issue here (i.e. Should EC's response affect FC's?). Also, allocation in terms of window size seems problematic. What if their windows are larger than they need?
The simulation results for XCP were unrealistically good. This is significant in that it shows how much we can improve from having more control information. It shows how much off TCP is from the "upper bound". A big problem however is the question of trust. It has to trust the end-points to cooperate by sending proper header info.
XCP is a end-point AND gateway solution. Explicit congestion control information is exchanged between the end hosts and routers. The fairness controller (FC) and an efficiency controller (EC) are purposely separated for simplicity and modularity (separation of concerns). However, EC augments the feedback responses produced by FC. There is potentially a fixed-point issue here (i.e. Should EC's response affect FC's?). Also, allocation in terms of window size seems problematic. What if their windows are larger than they need?
The simulation results for XCP were unrealistically good. This is significant in that it shows how much we can improve from having more control information. It shows how much off TCP is from the "upper bound". A big problem however is the question of trust. It has to trust the end-points to cooperate by sending proper header info.
Random Early Detection Gateways for Congestion Avoidance (LBL '93)
The paper presents another congestion avoidance algorithm called Random Early Detection (RED) for gateways. Its main goal is to minimize delay (while keeping high throughput), avoid global synchronization, and sensitive to bursty traffic. It's cheap, using a single FIFO queue with no per-connection states.
RED operates around the knee. It uses thresholds "min" and "max" to define three operation modes: mark-nothing, randomly-mark, mark-everything. All the interesting parts are in the second mode. It has to prepare for congestion but at the same time allow bursty traffic, which mean it has to allow packets to get on the queue under certain conditions. But it ultimately has to keep the queue length as small as possible.
Random-drop is better than drop-tail. It has a chance to drop packets for connections that are "hogging" the bandwidth, whereas drop-tail is forced to drop late comers.
RED implements both choices of marking and dropping packets as explicit and implicit congestion signals. It treats the two as equivalent legitimate implementations. I wonder what's the discussion over this. What advantages or disadvantages each has? Has anyone measure the effectiveness for each approach?
RED is basically a compromise between implementation cost and features. On one hand, we have the FQ and CSFQ, which maintains per-connection queues and states. On the other, FIFO drop-tail is the lower bound in cost, but is not sensitive to bursty traffic. By introducing "randomness", RED can allow the queue size to grow occasionally (preferably at times of bursty traffic).
This paper should be kept on the list. It's nice to see the comparison between RED and the other algorithms we read before. The paper is cleanly written overall. It has a clear focus and shows in-depth details of the RED algorithm. The simulation results again were on artifically made models. By now, i would imagine simulating a real network workload is quite difficult. No paper we read so far has done it.
The way they show the nonexistence of global synchronization isn't really working for me. Instead of showing the avg. utiliziation, they should show the variance of the avg. utilization over time.
RED operates around the knee. It uses thresholds "min" and "max" to define three operation modes: mark-nothing, randomly-mark, mark-everything. All the interesting parts are in the second mode. It has to prepare for congestion but at the same time allow bursty traffic, which mean it has to allow packets to get on the queue under certain conditions. But it ultimately has to keep the queue length as small as possible.
Random-drop is better than drop-tail. It has a chance to drop packets for connections that are "hogging" the bandwidth, whereas drop-tail is forced to drop late comers.
RED implements both choices of marking and dropping packets as explicit and implicit congestion signals. It treats the two as equivalent legitimate implementations. I wonder what's the discussion over this. What advantages or disadvantages each has? Has anyone measure the effectiveness for each approach?
RED is basically a compromise between implementation cost and features. On one hand, we have the FQ and CSFQ, which maintains per-connection queues and states. On the other, FIFO drop-tail is the lower bound in cost, but is not sensitive to bursty traffic. By introducing "randomness", RED can allow the queue size to grow occasionally (preferably at times of bursty traffic).
This paper should be kept on the list. It's nice to see the comparison between RED and the other algorithms we read before. The paper is cleanly written overall. It has a clear focus and shows in-depth details of the RED algorithm. The simulation results again were on artifically made models. By now, i would imagine simulating a real network workload is quite difficult. No paper we read so far has done it.
The way they show the nonexistence of global synchronization isn't really working for me. Instead of showing the avg. utiliziation, they should show the variance of the avg. utilization over time.
Wednesday, September 10, 2008
Core-Stateless Fair Queuing: Achieving Approximately Fair Bandwidth Allocation s in High Speed Networks (CMU '98)
Core-Stateless Fair Queuing (CSFQ) is an approximation of FQ implementation. It is designed to lessen the expense of implementing the full-blown version of FQ. CSFQ operates over an "island" of routers (s.t. inner routers are called core, and the perimeter called edge), where flow classification needs to be done once only at the edges. Core routers merely operate and propagate flow information. Like the other paper, CSFQ is compared with a handful of other alternatives, in this case both the hypothetical upper bound and other cheaper implementations that abstract away flow-states or multiple buffers.
CSFQ does not explicitly keep track of separate flow buffers, rather it keeps a small number of per-flow states (i.e. drop rate, arrival index). It computesthe drop probability for a incoming packet. In essence, it achieves similar desired effects of providing protection and being fair. It's also sensitive to burstiness of flow, which is a good thing (i.e. bursty flows can have good turn around time).
It's great that probabilistic method minimize the states we have to keep. Now, i see more reason why packets can be delivered out of order. Dropping packets randomly and regularly in the middle of a packet stream correspondingly adds burden on the endpoints to deal with these random "holes". Thus, we can see this as pushing the complexity away from the network and into the end-points.
Although the paper address the cost issue with FQ, it didn't give the full details on the bottleneck. I would like to see more on that in terms of implementation issues. I am also skeptical about the core-edge separation. Heterogeneity impedes scalability, in general. CSFQ also assumes that flow goes through a fixed set of routes, which doesn't map well to dynamic routing.
The paper explicitly talked about the concept of "punishment", which seems controversial. Basically, users who are nice are rewarded with more bandwidth while barbbling idiots get their share cut backed. This assumes that everyone is equal. But the reality is there are stratifications, like class, authority and etc. Should users with superior hardware and technology not be rewarded? Should everyone use the network the same?
CSFQ does not explicitly keep track of separate flow buffers, rather it keeps a small number of per-flow states (i.e. drop rate, arrival index). It computesthe drop probability for a incoming packet. In essence, it achieves similar desired effects of providing protection and being fair. It's also sensitive to burstiness of flow, which is a good thing (i.e. bursty flows can have good turn around time).
It's great that probabilistic method minimize the states we have to keep. Now, i see more reason why packets can be delivered out of order. Dropping packets randomly and regularly in the middle of a packet stream correspondingly adds burden on the endpoints to deal with these random "holes". Thus, we can see this as pushing the complexity away from the network and into the end-points.
Although the paper address the cost issue with FQ, it didn't give the full details on the bottleneck. I would like to see more on that in terms of implementation issues. I am also skeptical about the core-edge separation. Heterogeneity impedes scalability, in general. CSFQ also assumes that flow goes through a fixed set of routes, which doesn't map well to dynamic routing.
The paper explicitly talked about the concept of "punishment", which seems controversial. Basically, users who are nice are rewarded with more bandwidth while barbbling idiots get their share cut backed. This assumes that everyone is equal. But the reality is there are stratifications, like class, authority and etc. Should users with superior hardware and technology not be rewarded? Should everyone use the network the same?
Analysis and Simulation of a Fair Queueing Algorithm (PARC '90)
It describes a conceptual queuing model for network gateways, called fair queuing (FQ). It aims to provide protection between user loads for a router. It proposes to use separate queues to hold different user streams, and transmits with a round-robin fashion. FQ is contrasted with first-come-first-serve (FCFS) in terms of fairness, throughout, efficiency (i.e. # of dropped packets), and promptness (or avg. rtt). The two is simulated with rather unrealistic but isolated (understandable) scenarios.
FQ is found to be more fair in relation to users. The bulk of it is in defining what is "fair" and what is considered a "user". It turns out varying these definitions gives very different implications. For example, comparing package count favors large packages over small ones. The paper defined fairness in terms of bit-by-bit (rather than packet-by-packet) transmission ratio between users, and a user to be a source-dest conversation.
FQ rewards well-behaved users. Ill-behaved users would end up overwriting their own queues, thus increase their number of retransmits. This means that flow-control algorithm used by the end-hosts is encouraged the play nice and not create any congestion, since they are only hurting themselves. The paper showed that the Jain-Karel flow control with slow-start + AIMD out-performs other not-as-nice flow-controls. But what is considered to be nice enough, the paper didn't say...
One thing FQ adds is a trust boundary between gateways and end-hosts. One end host misbehaves may not influence others. It separates flow-control (end hosts) and queuing (gateway). In effect, gateways are "smarter" in resolving congestion problems on its own.
FQ is found to be more fair in relation to users. The bulk of it is in defining what is "fair" and what is considered a "user". It turns out varying these definitions gives very different implications. For example, comparing package count favors large packages over small ones. The paper defined fairness in terms of bit-by-bit (rather than packet-by-packet) transmission ratio between users, and a user to be a source-dest conversation.
FQ rewards well-behaved users. Ill-behaved users would end up overwriting their own queues, thus increase their number of retransmits. This means that flow-control algorithm used by the end-hosts is encouraged the play nice and not create any congestion, since they are only hurting themselves. The paper showed that the Jain-Karel flow control with slow-start + AIMD out-performs other not-as-nice flow-controls. But what is considered to be nice enough, the paper didn't say...
One thing FQ adds is a trust boundary between gateways and end-hosts. One end host misbehaves may not influence others. It separates flow-control (end hosts) and queuing (gateway). In effect, gateways are "smarter" in resolving congestion problems on its own.
Monday, September 8, 2008
Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks
The paper poses a (linear) control system view in looking at the congestion avoidance problem. It attempts to formally explain the reasoning behind multiplicative decrease and additive increase for distributed network flow control. In fact, the paper proves that multiplicative decrease and additive increase is only algorithm that would converge, w/o truncation.
The paper assumes a very simple feedback mechanism, basically binary signals, to advice increase or decrease for a user load, and these signals are tagged on by routers. It uses the concepts of efficiency and fairness to define the feasible region (or optimal state), and convergence and distributedness to measure the practicality of different increase-decrease control parameters.
The quality of the paper is superb. The authors did a very good job in illustrating the research problem (i.e. using "cliff" and "knee" to show the difference between congestion avoidance and control), and also in setting up the 4 metrics to quantify their results. They used fairness, convergence, distributedness, and efficiency, each of which is modeled formally using mathematical equations. The modeling equations and their proofs were quite elegant and understandable.
There is a short discussion toward the end that compares between the use of linear and nonlinear controls. Linear has the upper-hand in terms of simplicity and robustness to system parameters like max #users, but has the tradeoffs of "responsiveness" and "smoothness". Basically, it is hard to balance between reaching the optimal point quickly and not overshooting. Non-linear control on the other hand has more flexibility in achieving the optimal load; however, there are many more parameters to configure which lead to less robustness.
It is interesting to note the oscillation mentioned in the paper does not come from delay as commonly with feedback systems. It is from the lack of central coordination (i.e. the sum of individual changes overshoots what is needed). This results from router sending the same control signal to everyone in the network. It shows the beauty of the control being totally stateless (except the clients need to remember their request load).
Throughout the paper, it has a very simplistic view about the network (e.g. a relatively static pool of users). However, we all know that's not the case. I would want to see what are some "peculiarities" that arises in real network flow. What are the effects of having network elements that behaves differently (i.e. bursty, regular, and etc.)?
The paper assumes a very simple feedback mechanism, basically binary signals, to advice increase or decrease for a user load, and these signals are tagged on by routers. It uses the concepts of efficiency and fairness to define the feasible region (or optimal state), and convergence and distributedness to measure the practicality of different increase-decrease control parameters.
The quality of the paper is superb. The authors did a very good job in illustrating the research problem (i.e. using "cliff" and "knee" to show the difference between congestion avoidance and control), and also in setting up the 4 metrics to quantify their results. They used fairness, convergence, distributedness, and efficiency, each of which is modeled formally using mathematical equations. The modeling equations and their proofs were quite elegant and understandable.
There is a short discussion toward the end that compares between the use of linear and nonlinear controls. Linear has the upper-hand in terms of simplicity and robustness to system parameters like max #users, but has the tradeoffs of "responsiveness" and "smoothness". Basically, it is hard to balance between reaching the optimal point quickly and not overshooting. Non-linear control on the other hand has more flexibility in achieving the optimal load; however, there are many more parameters to configure which lead to less robustness.
It is interesting to note the oscillation mentioned in the paper does not come from delay as commonly with feedback systems. It is from the lack of central coordination (i.e. the sum of individual changes overshoots what is needed). This results from router sending the same control signal to everyone in the network. It shows the beauty of the control being totally stateless (except the clients need to remember their request load).
Throughout the paper, it has a very simplistic view about the network (e.g. a relatively static pool of users). However, we all know that's not the case. I would want to see what are some "peculiarities" that arises in real network flow. What are the effects of having network elements that behaves differently (i.e. bursty, regular, and etc.)?
Subscribe to:
Posts (Atom)