This paper compares different techniques for improving TCP performance and evaluates them in the context of wireless links. The main 3 categories that they evaluated were end-to-end protocols, link layer protocols, and also split connection protocols. The results of the paper showed that link layer protocols were the most beneficial if they are TCP aware.
Thinking back on the various papers we read about TCP, when it was designed, the major issues that we read about were mostly about contention and congestion. Several switch design papers proposed mechanism to deal with congestion, and combined with TCP's resend mechanism it would prevent contention. However, now that we're using TCP over a very lossy link, if the guarantee mechanism was only on the end points, then if the link is lossy, we would possibly need to resend over and over again because the probability of packet loss is high in the middle of transit. Thus, intuitively, it's more beneficial to implement recovery services also at the link layer because of the lossy attributes at each link (back to the end to end argument). All in all, a comparison of different mechanisms for TCP over wireless links confirmed the intuition.
Tuesday, September 30, 2008
MACAW: a media access protocol for wireless LAN
This paper proposes a different MAC protocol for wireless medium which uses a request to send-clear to send-DATA packet exchange and binary exponential back off. There were several insights in the paper that led to this protocol:
1. The relevant congestion is at the receiver, not the sender. The paper provides a simple example to show this, by using 3 nodes (ABC) which A cannot hear from sender C and C can't hear from A, the author shows that both A and C can think the channel is clear and send, but contention happens at B when he is reciving.
2. Congestion is not a homogeneous phenomenon. The author states that it is not valid to only have a single backoff parameter, but we need separate back off parameters for each strem.
3. Congestion levels should be a collective enterprise. I felt like this was sort of related again back to the end to end arguments in which functionality need to be carefully evaluated as to where it is implemented. In this case, the author argues that individual congestion detection will lead to asymmetric views of the network, thus there should be a collective effort to create a better view.
4. the protocol should propagate synchronization information about contention periods, so all devices can contend equally.
While reading this paper, one thought related to the project came into mind, which is the guaranteed service for wireless LANs. I've read several papers on real-time ethernet or real-time LAN protocols which use token based mechanisms. But how well would those work for wireless environments? And how much synchronization mechanisms need to be introduced in order to easily guarantee service through a physically unreliable channel?
1. The relevant congestion is at the receiver, not the sender. The paper provides a simple example to show this, by using 3 nodes (ABC) which A cannot hear from sender C and C can't hear from A, the author shows that both A and C can think the channel is clear and send, but contention happens at B when he is reciving.
2. Congestion is not a homogeneous phenomenon. The author states that it is not valid to only have a single backoff parameter, but we need separate back off parameters for each strem.
3. Congestion levels should be a collective enterprise. I felt like this was sort of related again back to the end to end arguments in which functionality need to be carefully evaluated as to where it is implemented. In this case, the author argues that individual congestion detection will lead to asymmetric views of the network, thus there should be a collective effort to create a better view.
4. the protocol should propagate synchronization information about contention periods, so all devices can contend equally.
While reading this paper, one thought related to the project came into mind, which is the guaranteed service for wireless LANs. I've read several papers on real-time ethernet or real-time LAN protocols which use token based mechanisms. But how well would those work for wireless environments? And how much synchronization mechanisms need to be introduced in order to easily guarantee service through a physically unreliable channel?
Tuesday, September 23, 2008
Scaling Internet Routers using Optics
Reading the other paper puts this paper into perspective. This paper further motivates the same subject of switch and router designs and suggests that a cross bar is not enough for the router, but we should use optical networks to scale and reduce power. This paper goes into a good amount of detail about the design and also multi racks for routers. It also lists the different challenges and possible solutions that will be faced when actually implementing this architecture of using optics.
As mentioned in the previous blog, i don't have a lot of background on this subject of matter, thus it was a hard paper for me to read. But this paper does seem to go in a fair amount of detail in the design. One thing that i started thinking about is ways to characterize the router's delay. Since our research project involves an estimation of network delay, it seems that as routers are scaling faster and faster, and as the structure gets more and more complicated, an estimation of the delay will become harder and harder.
It's also interesting that as other electronics are getting smaller and smaller, it seems that the router is growing bigger and bigger. This paper suggests that we would need multiple racks because of the power consumption and heat dissipation , instead of a single rack.
As mentioned in the previous blog, i don't have a lot of background on this subject of matter, thus it was a hard paper for me to read. But this paper does seem to go in a fair amount of detail in the design. One thing that i started thinking about is ways to characterize the router's delay. Since our research project involves an estimation of network delay, it seems that as routers are scaling faster and faster, and as the structure gets more and more complicated, an estimation of the delay will become harder and harder.
It's also interesting that as other electronics are getting smaller and smaller, it seems that the router is growing bigger and bigger. This paper suggests that we would need multiple racks because of the power consumption and heat dissipation , instead of a single rack.
A fast switched backplane for a gigabit switched router
This paper motivated using switched backplanes for router designs. Although i don't have too much background in this area of specific router design, but it seems like the backplane they were talking about was basically the interconnect within the router that connects the input to output. It seems that previous to this paper, this interconnect was a bus. Buses in general have several disadvantages including its scalability and also contention, which is also mentioned in the paper. Thus, changing to a cross bar has it obvious advantages that now multiple packets and request can be forwarded to the outputs at the same time, thus increasing the bandwidth of the backplane. The paper then went on to explain the different design areas of a switched network.
Since i don't have much background on router designs, it's hard for me to comment on this paper. But it seems like since i started studying routers, what i learned was that the interconnect between input and output was a cross bar. Thus, i was quite shocked to hard that it used to be a single bus connecting everything. However, multicast does seem like it would be easier to do on a single bus, because i could imagine all of the outputs seeing the broadcast at the same time since they are all on the same bus. But as we move towards higher speed networks and domains, routers need to be able to support and keep up with the network.
Since i don't have much background on router designs, it's hard for me to comment on this paper. But it seems like since i started studying routers, what i learned was that the interconnect between input and output was a cross bar. Thus, i was quite shocked to hard that it used to be a single bus connecting everything. However, multicast does seem like it would be easier to do on a single bus, because i could imagine all of the outputs seeing the broadcast at the same time since they are all on the same bus. But as we move towards higher speed networks and domains, routers need to be able to support and keep up with the network.
Thursday, September 18, 2008
Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism
This paper is also a paper on the real-time guarantees of the internet. It explains the details and need of the architecture and mechanisms to allow real-time services in the internet. However, the author's view of real-time applications seem somewhat narrow to mostly multimedia streams or apps that can be categorized as having a "play back point." Although it does distinguish between guarantee service and predicted service, which is probably their way of saying hard and soft real-time tasks.
Both papers recognize that a network needs to support both datagram traffic and real-time traffic. We know that there are pre-existing virtual circuit networks (ATM) out there that guarantee delivery, and there is obviously packet switched networks that don't have guarantee. But based on the previous paper (fundamental design issues for the future internet), they state that having two seperate links doesn't have the most efficacy, but instead, a link that can satisfy different service models is a link that is the most efficient in utilizing it's bandwidth. Thus, this paper is about the different scheduling algorithm required, and how to unify them.
It seems like the effort for real-time internet boils down to a couple general points:
- Need to reserve bandwidth for real-time connections
-Need to have admission control, because real-time guarantees can't be effected by congestion
-Need to have some way to prevent abuse, namely, pricing
- Need to be compatible with current internet, so use leftover bandwidth to complete non real-time packet requests
But none really talk about security issues, they just use pricing as a mechanism to prevent abuse. Intuitively, if there is a real-time guarantee of delivery, then there can't be denial of service attack because the bandwidth is isolated from the rest of the packets. But can we also think of a denial of service when there is an admission control and real-time requests can't be serviced because it will disrupt the current schedule? This seems like an interesting research topic and a good choice for the semester project.
Both papers recognize that a network needs to support both datagram traffic and real-time traffic. We know that there are pre-existing virtual circuit networks (ATM) out there that guarantee delivery, and there is obviously packet switched networks that don't have guarantee. But based on the previous paper (fundamental design issues for the future internet), they state that having two seperate links doesn't have the most efficacy, but instead, a link that can satisfy different service models is a link that is the most efficient in utilizing it's bandwidth. Thus, this paper is about the different scheduling algorithm required, and how to unify them.
It seems like the effort for real-time internet boils down to a couple general points:
- Need to reserve bandwidth for real-time connections
-Need to have admission control, because real-time guarantees can't be effected by congestion
-Need to have some way to prevent abuse, namely, pricing
- Need to be compatible with current internet, so use leftover bandwidth to complete non real-time packet requests
But none really talk about security issues, they just use pricing as a mechanism to prevent abuse. Intuitively, if there is a real-time guarantee of delivery, then there can't be denial of service attack because the bandwidth is isolated from the rest of the packets. But can we also think of a denial of service when there is an admission control and real-time requests can't be serviced because it will disrupt the current schedule? This seems like an interesting research topic and a good choice for the semester project.
Fundamental design issues for the future internet
This was a very interesting paper to read. It seems that now the internet is well received, and the amount of users are growing by the day, it's hard to imagine any change in the fundamental design of internet. Most of us are used to the way things are, the TCP protocols and the IP and Ethernet designs that we often are blinded to the so called "issues" of the ethernet. This is also an interesting paper to read because for the project for this class our topic was going to be something related to real-time ethernet, or synchronous ethernet, so this was definitely a good intro paper to read.
The paper surveys the design issues of ethernet, defining the quantity V, the efficacy of the architecture, to be used to evaluate different design techniques. It evaluated the efficacy of having separate services on the internet to address different needs. Obviously the current internet architecture has no guarantee of service, delivery, order, or delay when a packet is sent through the internet. However, in the future, with bandwidth and speed both improving, more and more applications will need better services. This paper thus evaluates different design issues of incorporating the different services in one network.
One of the interesting discussions mentioned in this paper is the issue of pricing. I like to think of it also as an issue of security. If there are high priority packets that recieve better bandwidth, why doesn't everyone just use them or abuse them? Of course pricing could be an effective way of preventing regular users from accessing the high priority bandwidth. This would be used with some sort of admission control to limit the and guarantee the services of this reliable network. However, more and more security issues will start to come into play. For example, if a hacker hacks the control system that does the admission control, he could potentially flood the network with high priority packets preventing any other real-time service to be able to gain access to the link etc. This seems like a good topic to do some research on.
The paper surveys the design issues of ethernet, defining the quantity V, the efficacy of the architecture, to be used to evaluate different design techniques. It evaluated the efficacy of having separate services on the internet to address different needs. Obviously the current internet architecture has no guarantee of service, delivery, order, or delay when a packet is sent through the internet. However, in the future, with bandwidth and speed both improving, more and more applications will need better services. This paper thus evaluates different design issues of incorporating the different services in one network.
One of the interesting discussions mentioned in this paper is the issue of pricing. I like to think of it also as an issue of security. If there are high priority packets that recieve better bandwidth, why doesn't everyone just use them or abuse them? Of course pricing could be an effective way of preventing regular users from accessing the high priority bandwidth. This would be used with some sort of admission control to limit the and guarantee the services of this reliable network. However, more and more security issues will start to come into play. For example, if a hacker hacks the control system that does the admission control, he could potentially flood the network with high priority packets preventing any other real-time service to be able to gain access to the link etc. This seems like a good topic to do some research on.
Monday, September 15, 2008
Congestion Control for High Bandwidth-Delay Product Networks
This paper presents a new transport layer protocol called the Explicit Control Protocol (XPC). XPC addresses the problems of TCP where the the bandwidth is underutilized when TCP conservatively controls congestions through slow start and fairness control through the gateways. The proposal for XPC is to use control theory to model the protocol, and decouple the fairness and efficiency control mechanisms used to maintain flexibility and control. However, unlike the previous paper we read where the routers drop packets to control congestion, XPC instead appends a congestion header to all its data packets being sent around. The routers fill out congestion information in the congestion header for those packets and as the packets get routed from destination to destination, the most congested router would be the last to update the packet header, which then the end nodes use to control their sending window.
The XPC router splits efficiency and fairness into two separate algorithms, where as TCP uses the drop packet mechanism to maintain both. This allows the XPC protocol to efficiently use the underused bandwidth when recovering from a congestion slow down. And because it is decoupled from the fairness control, it doesn't have to worry about nodes not getting bandwidth, it just needs to keep the total utilized bandwidth at a high efficiency. The Fairness controller is the one that maintains the bandwidth fairness of the router.
The results of this paper seems to me that is was almost unrealistically good. There were almost no dropped packets, and the performance of the protocol is good when network is un-congested, and also good when the network is congested. Intuitively it seems that because this protocol and gateway doesn't drop packets (intentionally), the quality should be better, and it was built to overcome the flaws of TCP regarding recovery of congestion control mechanisms, thus, its performance can only be better than TCP, while the overhead includes an added packet header for each packet with different control algorithms. It's hard to believe just based on those it can have such a promising results.
The XPC router splits efficiency and fairness into two separate algorithms, where as TCP uses the drop packet mechanism to maintain both. This allows the XPC protocol to efficiently use the underused bandwidth when recovering from a congestion slow down. And because it is decoupled from the fairness control, it doesn't have to worry about nodes not getting bandwidth, it just needs to keep the total utilized bandwidth at a high efficiency. The Fairness controller is the one that maintains the bandwidth fairness of the router.
The results of this paper seems to me that is was almost unrealistically good. There were almost no dropped packets, and the performance of the protocol is good when network is un-congested, and also good when the network is congested. Intuitively it seems that because this protocol and gateway doesn't drop packets (intentionally), the quality should be better, and it was built to overcome the flaws of TCP regarding recovery of congestion control mechanisms, thus, its performance can only be better than TCP, while the overhead includes an added packet header for each packet with different control algorithms. It's hard to believe just based on those it can have such a promising results.
Random Early Detection Gateways for Congestion Avoidance
This paper presented the Random Early Detection gateway algorithm to avoid congestion in a packet switched network. The basic idea presented in this paper is that in order to avoid congestion at the gateway level, an average queue size should be maintained in order to provide constant throughput. To maintain the average queue size in the gateway, packets will be dropped randomly at a ratio proportionate to the queue size, which represents the congestion level of the network. If the queue passes a threshold size, all packets incoming will be dropped.
Of course this technique requires the end to end protocol to ensure guarantee of delivery because it doesn't contact the sender directly to slow down the sending window. Instead it uses a passive method of just dropping the packet, and then waits for the sender to realize that a packet has been dropped, and thus it needs to slow down. The paper provided detailed algorithms on each of the decisions that need to be made, including the probability of dropping a packet etc. It also set a max and min thresholds to the queue size. If the queue size reaches the min threshold, then it means that the network is under utilized, thus no packets are dropped or marked. If the queue size reaches the maximum threshold, then all the incoming packets are dropped.
It was also interesting how they defined fairness in this paper. It seems like instead of defining fairness as attempting to give all the nodes the same amount of bandwidth, the fairness was defined as, "there will be the same probability that everyone's packet will be dropped, we will not discriminate against certain nodes and no drop their packet." This is different from the papers we read before, and it certainly does not guarantee that it tries to give all nodes the same bandwidth, it is merely used for congestion control.
Although i can see that when working together with TCP or any higher level protocol which has reliable delivery this would work to control congestion, because end nodes can detect that a packet is dropped and then slow down its window, but intuitively it just seems like randomly dropping a packet seems not to be the most efficient way, and it really relies on the protocols to have reliable delivery. However, the other way is to have the gateways notify the nodes by actually sending messages to them, which would only create more traffic and use up more bandwidth. There is always a tradeoff there.
Of course this technique requires the end to end protocol to ensure guarantee of delivery because it doesn't contact the sender directly to slow down the sending window. Instead it uses a passive method of just dropping the packet, and then waits for the sender to realize that a packet has been dropped, and thus it needs to slow down. The paper provided detailed algorithms on each of the decisions that need to be made, including the probability of dropping a packet etc. It also set a max and min thresholds to the queue size. If the queue size reaches the min threshold, then it means that the network is under utilized, thus no packets are dropped or marked. If the queue size reaches the maximum threshold, then all the incoming packets are dropped.
It was also interesting how they defined fairness in this paper. It seems like instead of defining fairness as attempting to give all the nodes the same amount of bandwidth, the fairness was defined as, "there will be the same probability that everyone's packet will be dropped, we will not discriminate against certain nodes and no drop their packet." This is different from the papers we read before, and it certainly does not guarantee that it tries to give all nodes the same bandwidth, it is merely used for congestion control.
Although i can see that when working together with TCP or any higher level protocol which has reliable delivery this would work to control congestion, because end nodes can detect that a packet is dropped and then slow down its window, but intuitively it just seems like randomly dropping a packet seems not to be the most efficient way, and it really relies on the protocols to have reliable delivery. However, the other way is to have the gateways notify the nodes by actually sending messages to them, which would only create more traffic and use up more bandwidth. There is always a tradeoff there.
Thursday, September 11, 2008
Core-Stateless Fair Queueing
This paper addresses some of the issues from the previous paper about the scalability and complexity of the fair queuing algorithm. The author proposes using an island of routers, having the edge maintaining the basic flow state, while the middle routers (core routers) don't need to maintain state, and they simply use a probabilistic drop packet algorithm and a FIFO queue.
The results after testing showed that they achieved a significant degree of fairness. Although this can't compare to a real fairness queuing algorithm, they argue that it's "good enough" and also cost effective and scales well. It also out performs several other queuing algorithms in terms of fairness. It seems somewhat related to the idea of landmark routing, where instead of being fair at each node, dedicate some nodes to monitor the fairness while the other core nodes save computation and power by a simpler FIFO queue.
It's always interesting to see a proposed algorithm that doesn't perform as well as a previous one, but is "good enough" and cost effective. The author claims exactly that for this algorithm. The two papers together both agree that routing is a big aspect of flow control now, but it seems the proposals focused on different tradeoffs, with the FQ being focused on fairness of bandwidth etc, while this paper focuses on the scalability and complexity efficiency.
The results after testing showed that they achieved a significant degree of fairness. Although this can't compare to a real fairness queuing algorithm, they argue that it's "good enough" and also cost effective and scales well. It also out performs several other queuing algorithms in terms of fairness. It seems somewhat related to the idea of landmark routing, where instead of being fair at each node, dedicate some nodes to monitor the fairness while the other core nodes save computation and power by a simpler FIFO queue.
It's always interesting to see a proposed algorithm that doesn't perform as well as a previous one, but is "good enough" and cost effective. The author claims exactly that for this algorithm. The two papers together both agree that routing is a big aspect of flow control now, but it seems the proposals focused on different tradeoffs, with the FQ being focused on fairness of bandwidth etc, while this paper focuses on the scalability and complexity efficiency.
Analysis and Simulation of a Fair Queueing Algorithm
It is interesting to me how most of the topics interrelate one way or another. To me, the end to end argument is also being applied here as well, as the author first describes the importance of flow control, and how not just the end to end flow control mechanisms are required, but also the routing and even at the gateway level, which is the queueing of packages.
The author does a good job explaining the definitions of fair and also fair scheduling. THe goal was to describe a new fair queueing algorithm, and undersatnd the performance of the FQ algorithm, and also to evaluate it by simulating it. The paper also briefly mentions the different abuses that could happen with a poorly designed system, including users spamming packets to block up the receiver's queue, users who spawn processes to eat up bandwidth etc.
All in all, the fair queueing does provide a major role in network congestion, but this paper doesn't mention anything about implementation costs, which from the next paper we infer that it doesn't scale well. Also, it isn't tested on a real network load, the paper even mentions that the tests implemented were limited, so real load testing is definitely needed.
The author does a good job explaining the definitions of fair and also fair scheduling. THe goal was to describe a new fair queueing algorithm, and undersatnd the performance of the FQ algorithm, and also to evaluate it by simulating it. The paper also briefly mentions the different abuses that could happen with a poorly designed system, including users spamming packets to block up the receiver's queue, users who spawn processes to eat up bandwidth etc.
All in all, the fair queueing does provide a major role in network congestion, but this paper doesn't mention anything about implementation costs, which from the next paper we infer that it doesn't scale well. Also, it isn't tested on a real network load, the paper even mentions that the tests implemented were limited, so real load testing is definitely needed.
Monday, September 8, 2008
Analysis of Increase and Decrease Algorithms for COngestion Avoidance in Computer Networks
This paper was published after the previous paper on congestion control, and it attempts to evaluate different techniques for congestion control. The conclusion of course is that additive increase and multiplicative decrease is the best solution. The categories that are evaluated are basically combinations of additive increase/decreases and multiplicative increase/decrease. The paper proses several metrics used for comparison, such as efficiency, fairness, convergence time and size of oscillation.
The paper defines efficiency as the closeness of total load on the resource to its knee, basically maximizing the bandwidth use without going over. Fairness is between the users of the network, and the allowed bandwidth of each, not letting any one user dominate the bandwidth. Distributed is an interesting metric, because it wants to decentralize control. Thus, instead of a central unit telling a particular user to back off, they assume a binary feedback, where all users get same information, congested or not congested. And finally convergence is the speed in which the network reaches its equilibrium state.
It's interesting to read about the ways of proving the set of different metrics. I think a good way to think about is that if its additive increase additive decrease (or multiplicative for both), the network although is trying it's best to decrease congestion by having users decrease load, but users also add load as fast as its decreasing load, so congestion will happen again very quickly. Obviously multiplicative increase and additive decrease will do no good at all. Only by decreasing at a faster rate than your increasing, can you control the network to slowly increase bandwidth, increasing the time it takes for the network to be congested again.
The paper defines efficiency as the closeness of total load on the resource to its knee, basically maximizing the bandwidth use without going over. Fairness is between the users of the network, and the allowed bandwidth of each, not letting any one user dominate the bandwidth. Distributed is an interesting metric, because it wants to decentralize control. Thus, instead of a central unit telling a particular user to back off, they assume a binary feedback, where all users get same information, congested or not congested. And finally convergence is the speed in which the network reaches its equilibrium state.
It's interesting to read about the ways of proving the set of different metrics. I think a good way to think about is that if its additive increase additive decrease (or multiplicative for both), the network although is trying it's best to decrease congestion by having users decrease load, but users also add load as fast as its decreasing load, so congestion will happen again very quickly. Obviously multiplicative increase and additive decrease will do no good at all. Only by decreasing at a faster rate than your increasing, can you control the network to slowly increase bandwidth, increasing the time it takes for the network to be congested again.
Congestion Avoidance and Control
This paper presented techniques to avoid congestion in the network, which stemmed from the data throughput rate from LBL to Berkeley being dropped from 32Kbps to 40 bps. It states that congestion is not caused by the protocol itself, but the implementation of the protocol. I think although this might be true in the TCP case, but not all protocols are designed to avoid congestion, and a poorly designed protocol would still run into the problem even with good implementation. Thus, the congestion avoidance mechanism much also be built into the protocol. The author also generalizes all congestion avoidance algorithms to contain a conversation of packet principle.
It then lists the several techniques (which are mostly pretty simple but effective) to be able to avoid congestion. First is a slow start, which restricts communications to start slower, and increase if there is bandwidth. The problem with starting too slow is that it's overhead and wasting bandwidth that could be used to transfer. But starting too fast between two different linked speeds would cause congestion (it's interesting that some of these methods are enforced to maintain better compatibility with older connection links, which brings us back to the previous week's paper that internet needs to support a wide range of networks).
The second technique is round trip timing, which is used to calculate when a packet is dropped from the network. This is important because if the calculation is not conservative enough, we would start inserting the packet retries earlier that the packet is dropped, wasting bandwidth. The third technique is exponential back off, where the sender adjusts to the link. More proof on why exponential back off is required in the next paper. The future work is interesting in that it is also related to the end to end argument, that not just the end points should implement avoidance, but maybe the gateways as well, to improve the congestion control.
Congestion control is not just limited to networks, traffic jam is the perfect example. They employ techniques like slowing down incoming traffic by using stop lights at freeway entrances to slow the incoming rate (back off). Without congestion control, then we are very vulnerable to congestion collapses as mentioned in the paper, which will easily turn a high bandwidth link to a low one, just like with the LBL and UCB link.
It then lists the several techniques (which are mostly pretty simple but effective) to be able to avoid congestion. First is a slow start, which restricts communications to start slower, and increase if there is bandwidth. The problem with starting too slow is that it's overhead and wasting bandwidth that could be used to transfer. But starting too fast between two different linked speeds would cause congestion (it's interesting that some of these methods are enforced to maintain better compatibility with older connection links, which brings us back to the previous week's paper that internet needs to support a wide range of networks).
The second technique is round trip timing, which is used to calculate when a packet is dropped from the network. This is important because if the calculation is not conservative enough, we would start inserting the packet retries earlier that the packet is dropped, wasting bandwidth. The third technique is exponential back off, where the sender adjusts to the link. More proof on why exponential back off is required in the next paper. The future work is interesting in that it is also related to the end to end argument, that not just the end points should implement avoidance, but maybe the gateways as well, to improve the congestion control.
Congestion control is not just limited to networks, traffic jam is the perfect example. They employ techniques like slowing down incoming traffic by using stop lights at freeway entrances to slow the incoming rate (back off). Without congestion control, then we are very vulnerable to congestion collapses as mentioned in the paper, which will easily turn a high bandwidth link to a low one, just like with the LBL and UCB link.
Wednesday, September 3, 2008
On Inferring Autonomous System Relationships in the Internet
I read this paper after the previous lecture paper on Interdomain routing, which made this paper a lot easier to read. It seems like the author was trying to create a model of the current internet interdomain struture using the BGP protocol assumptions to infer the various relationships of the internet.
The first half of the paper explains the BGP protocol again and the different relationships that exists in the protocol. IT then describes the algorithms it uses to infer the relationships and model the routing tables. The decisions made by each router regarding how the routing tables are exported and imported are based on the different relationships (provider-customer, peer-to-peer etc), and these algorithms were written into a perl program and ran. The results came out very well, as 99.1% of the inference results was confirmed by AT&T.
Without any background for research in networks, this paper was a very good read. First it confirms the previous lecture in saying that most of the network routing is driven by profit, not speed or quality. Looking at the results of the paper, over 90% of the relationships that were inferred on the internet is a provide-customer relationship. This means that even though there are ASes that share peer-to-peer relationships, but it's less than 10%. In a management of technology class that i just took, the professor defined successful engineering as coming up with something useful. He then defined usefulness to mean profitable. Basically, anything that is profitable enough to sustain itself is useful. Looks like the internet is also a good example of it.
The first half of the paper explains the BGP protocol again and the different relationships that exists in the protocol. IT then describes the algorithms it uses to infer the relationships and model the routing tables. The decisions made by each router regarding how the routing tables are exported and imported are based on the different relationships (provider-customer, peer-to-peer etc), and these algorithms were written into a perl program and ran. The results came out very well, as 99.1% of the inference results was confirmed by AT&T.
Without any background for research in networks, this paper was a very good read. First it confirms the previous lecture in saying that most of the network routing is driven by profit, not speed or quality. Looking at the results of the paper, over 90% of the relationships that were inferred on the internet is a provide-customer relationship. This means that even though there are ASes that share peer-to-peer relationships, but it's less than 10%. In a management of technology class that i just took, the professor defined successful engineering as coming up with something useful. He then defined usefulness to mean profitable. Basically, anything that is profitable enough to sustain itself is useful. Looks like the internet is also a good example of it.
Interdomain Internet Routing
This paper is a lecture series which explains the workings of inter- domain routing, which is the back bone of the internet. The interdomain routing protocol is called the border gateway protocol, which is used the route between domains. Since the main goal of the internet was to connect different networks together to form a large interconnected communication channel, there needed to be a way to route the packets from various domains and networks.
The internet is formed by different Automonous Systems including ISPs and campuses. The network within the ASes usually are routed by the ASes themselves, but the routing between the ASes were governed by policies and financial motivations. Thus a scalable protocol that is easily customizable between domains was created to allow ASes to easily configure what routes to broadcast. ultimately it costs money to transmit packets, so the least amount of traffic results in the most saved in earnings. This paper describes the different AS relationships and the route broadcast mechanisms that's resulting from that.
It was quite interesting reading about it. In all the previous networking classes or routing lectures and research papers, it always seems like the main focus is shortest path, or congestion control or flow control. But in reality, research is put into minimizing cost and maximizing profit.
The internet is formed by different Automonous Systems including ISPs and campuses. The network within the ASes usually are routed by the ASes themselves, but the routing between the ASes were governed by policies and financial motivations. Thus a scalable protocol that is easily customizable between domains was created to allow ASes to easily configure what routes to broadcast. ultimately it costs money to transmit packets, so the least amount of traffic results in the most saved in earnings. This paper describes the different AS relationships and the route broadcast mechanisms that's resulting from that.
It was quite interesting reading about it. In all the previous networking classes or routing lectures and research papers, it always seems like the main focus is shortest path, or congestion control or flow control. But in reality, research is put into minimizing cost and maximizing profit.
Monday, September 1, 2008
End to End Arguments in System Design
This paper summarizes one of the key concepts and tradeoffs when designing the internet, or any type of network involving multiple layers interacting. The argument basically is how much functionality should be duplicated in each of the layers to ensure the guarantee of the functionality through the network to be robust. In the paper most examples are regarding robustness and reliability, but it could really be applied to any functionality that is to be implemented in the network.
The paper gives some detailed examples, starting with a careful file transfer protocol. It lists the concerns and errors that might occur during a simple file transfer protocol, and some of the methods to combat it. For example, if we just have the protocol application itself do the error checking, and resend the file if there was corruption or error in the transfer, then the lower level implementations wouldn't need to worry about the error checking. However, if error occurs frequently, then this would result in a huge performance loss and possibly network congestion because the whole file needs to be resent over and over. However, if we implement at a lower level, there still is a possibility that the protocol will result in error, so implementing at the lower level doesn't void the necessity to implement the repeated error checking function at a higher level. It's just the matter of how much.
The paper then lists out different scenarios and application backgrounds to help us understand that there is no correct answer but everything is a tradeoff. In particular, even the same type of application with a little different background can result in a different design. A real time voice communicator (phone) will probably care less about dropping one or two packets, and would care more about the latency, since the users can easily reask the information over the communication. However, if it's a voicemail, then we probably care more about the validity and quality of the content over the latency since we can't reask the information.
The examples used in the paper were very clear and really portrayed the ideas behind them. Instead of giving an absolute opinion on the end to end argument itself, the paper actually more serves as a guideline as to how to design the communication system and identify the needs in order to choose between the tradeoff.
I actually read this paper before the previous blog post paper, and i thought it was the perfect order to read the two papers of the week. This paper is a precursor of the different design difficulties faced in desiging the internet, especially in regards to using the datagram as a building block as opposed a more reliable building block. Ultimately the goal of the internet was to support a wide range of networks, and because of that, the reliable error checks and retransmission mechanisms might not be needed for all services and applications supported by the internet. As the argument states, implementing the functionalities in the lower level layers doesn't void the implemention at the higher layers, thus there was no need to have a reliable building block when a datagram is suffice. This clearly was one of the considerations taken into account when the internet was designed.
The paper gives some detailed examples, starting with a careful file transfer protocol. It lists the concerns and errors that might occur during a simple file transfer protocol, and some of the methods to combat it. For example, if we just have the protocol application itself do the error checking, and resend the file if there was corruption or error in the transfer, then the lower level implementations wouldn't need to worry about the error checking. However, if error occurs frequently, then this would result in a huge performance loss and possibly network congestion because the whole file needs to be resent over and over. However, if we implement at a lower level, there still is a possibility that the protocol will result in error, so implementing at the lower level doesn't void the necessity to implement the repeated error checking function at a higher level. It's just the matter of how much.
The paper then lists out different scenarios and application backgrounds to help us understand that there is no correct answer but everything is a tradeoff. In particular, even the same type of application with a little different background can result in a different design. A real time voice communicator (phone) will probably care less about dropping one or two packets, and would care more about the latency, since the users can easily reask the information over the communication. However, if it's a voicemail, then we probably care more about the validity and quality of the content over the latency since we can't reask the information.
The examples used in the paper were very clear and really portrayed the ideas behind them. Instead of giving an absolute opinion on the end to end argument itself, the paper actually more serves as a guideline as to how to design the communication system and identify the needs in order to choose between the tradeoff.
I actually read this paper before the previous blog post paper, and i thought it was the perfect order to read the two papers of the week. This paper is a precursor of the different design difficulties faced in desiging the internet, especially in regards to using the datagram as a building block as opposed a more reliable building block. Ultimately the goal of the internet was to support a wide range of networks, and because of that, the reliable error checks and retransmission mechanisms might not be needed for all services and applications supported by the internet. As the argument states, implementing the functionalities in the lower level layers doesn't void the implemention at the higher layers, thus there was no need to have a reliable building block when a datagram is suffice. This clearly was one of the considerations taken into account when the internet was designed.
The Design Philosophy of the DARPA Internet Protocols
This paper written by David D. Clark discusses the internet and its protocols, reflecting on it's design goals and evaluating the success and implementation of each goal. It first gives a brief history of the DARPA network and lists the goals in which the developers had in mind when designing it.
"The fundamental goal for the internet architecture was to develop an effective technique for multipexed utilization of existing interconnected networks. " Writes Clark. This meant combining all the preexisting commonly used networks (including the ARPA packet radio network, ARPANET etc) together so they can communicate and share information. And the technique selected for that was packet switching. Along with the fundamental goal, there are also second level goals, including fault tolerant, multiple types of services etc. The paper goes on to discuss in detail the second level goals, and how the implementation came to be why each implementation was decided.
The paper was definitely a good read. David Clark was the chief protocol architect in the development of the internet, so he obviously knew what he was talking about. He used explained each goal and the reasonings behind it, giving us a good picture of what was going on in his mind during that time.
The internet is something we take for granted everyday, and it's almost becoming something we can't live without. Looking back at the design goals, the fundamental goal of interconnecting a wide range of networks is probably what gave the internet its popularity today. Being able to connect to people from all over the world through these different sets of mediums is why the internet is so attractive, and is the definition of the internet itself. And the benefits of fault tolerant allows us a pretty reliable network to use.
We can see the tradeoff between the flexibility of the internet along with the performance. It was interesting reading Clark describing how the internet architect is actually something that can't really be described, because it encapsulates such a wide range of services, so it can only be defined by the end point services themselves. And the performance (latency) of the internet also cannot fully be comprehended because the design goal is to support any network of any latency. But because of that, we are seeing the internet being used in ways no one would have ever imagined when the internet was designed. Because of the flexibility in services, today the internet is even moving onto the mobile platforms and revolutionizing out experience with interacting with the network.
However, with the internet technology continues to evolve, it will be interesting to see the backwards compatibility continue to play in its effect. How much longer will apps or developers continue to support slow networks like 56k modem etc, given the fact that the design goals of the internet was to incorporate all the different networks into one giant network.
"The fundamental goal for the internet architecture was to develop an effective technique for multipexed utilization of existing interconnected networks. " Writes Clark. This meant combining all the preexisting commonly used networks (including the ARPA packet radio network, ARPANET etc) together so they can communicate and share information. And the technique selected for that was packet switching. Along with the fundamental goal, there are also second level goals, including fault tolerant, multiple types of services etc. The paper goes on to discuss in detail the second level goals, and how the implementation came to be why each implementation was decided.
The paper was definitely a good read. David Clark was the chief protocol architect in the development of the internet, so he obviously knew what he was talking about. He used explained each goal and the reasonings behind it, giving us a good picture of what was going on in his mind during that time.
The internet is something we take for granted everyday, and it's almost becoming something we can't live without. Looking back at the design goals, the fundamental goal of interconnecting a wide range of networks is probably what gave the internet its popularity today. Being able to connect to people from all over the world through these different sets of mediums is why the internet is so attractive, and is the definition of the internet itself. And the benefits of fault tolerant allows us a pretty reliable network to use.
We can see the tradeoff between the flexibility of the internet along with the performance. It was interesting reading Clark describing how the internet architect is actually something that can't really be described, because it encapsulates such a wide range of services, so it can only be defined by the end point services themselves. And the performance (latency) of the internet also cannot fully be comprehended because the design goal is to support any network of any latency. But because of that, we are seeing the internet being used in ways no one would have ever imagined when the internet was designed. Because of the flexibility in services, today the internet is even moving onto the mobile platforms and revolutionizing out experience with interacting with the network.
However, with the internet technology continues to evolve, it will be interesting to see the backwards compatibility continue to play in its effect. How much longer will apps or developers continue to support slow networks like 56k modem etc, given the fact that the design goals of the internet was to incorporate all the different networks into one giant network.
Subscribe to:
Posts (Atom)