At the end of our discussion in class on XORs in The Air: Practical Wireless Network Coding, I began to think about the feasibility of a commercial implementation of the idea behind the article. This article proposes the application of network coding techniques to wireless networking to opportunistically increase the amount of data that can be sent in one transmission. It holds great potential because transmission time is a scarce resource that can't be scaled up with added hardware. Furthermore, use of the technique is orthogonal to many other strategies for improving network efficiency. The idea involves nodes listening and recording temporarily all packets they can hear, including those not meant for them. Then, a transmitting node can XOR new packets with previously transmitted ones to send more than one packet simultaneously. Listeners can XOR the transmitted packet with packets they have stored in memory to obtain their desired payload.
The technique has several important technical hurdles to overcome in transforming itself to commercial success. The main issue seems to be that all nodes participating in a network that uses network coding require custom software in their network stack. This leads to significant deployment challenges; specifically, standard 802.11 nodes can't join the network unaided. This problem could be mitigated by requiring only infrastructure nodes in multi-hop networks to use network coding, but this would also limit the opportunities for optimization by network coding. Second, the benefits of network coding vary widely with factors such as network topology and current traffic and congestion levels, so that it may be difficult to predict how much the average network might benefit from network coding. Third, the technique increases the complexity of the network software stack, as nodes must now store extra network-specific state in the form of past packets. Lastly, network coding software might have a significant negative impact on node power consumption, as nodes are now required to listen to every packet that is broadcast in the network.
In light of the above hurdles, I believe the potential benefits of network coding as presented in the paper do not seem to be worth the costs. That is not to say the paper is not successful; it combined novel ideas and inspired a host of excitement new research in wireless networking. However, more work would need to be done to integrate network coding successfully into live wireless networks.
Thursday, November 11, 2010
Overcoming the Challenges of Wireless Networking
Wireless networking poses unique challenges when compared to traditional networking. Two issues in particular are at the heart of these difficulties: every act of communication involves broadcasting and packet loss is much more frequent and dynamic. The broadcasting nature of wireless networks means that the medium of communication, air, is precious, as it must be shared by everyone. Also, it is very difficult for nodes to know whether or not adjacent nodes are available for communication, since an adjacent node may be busy communicating with a third node that the first node can't detect. Lastly, the packet loss characteristics of wireless communication in combination with TCP can lead to uneven resource availability and even full starvation, especially with multi-hop communication.
That said, researchers have applied their creative intellects to making the best of a fairly harsh networking environment. For instance, one paper proposed a change to a core multi-hop network to cause nodes in a network to work together to enforce fairness constraints at each hop of the network. While the algorithm could slightly reduce overall bandwidth utilization, it significantly reduced resource starvation and uneven resource usage between nodes. In another paper a group of researchers proposed that multiple packets be encoded together at once by XOR-encoding packets together. This method requires nodes to remember recent packets they have heard, as well as track other neighbor state, but could result in as much as 4x improvements in bandwidth usage. Lastly, we learned of a proposed technique to allow nodes to cooperate with another in sending a packet across a multi-hop network. When a node fires a batch of packets, all capable listeners are enabled to assist those packets in traversing the network, so that even if the original next-hop destination failed to hear some packets nearby neighbors could pass on the packets for it.
These innovative solutions showed me both just how difficult improving wireless networking and extending its use cases can be. At the same time, it showed me that difficult problems can provide fertile ground for creative thinkers to apply themselves.
That said, researchers have applied their creative intellects to making the best of a fairly harsh networking environment. For instance, one paper proposed a change to a core multi-hop network to cause nodes in a network to work together to enforce fairness constraints at each hop of the network. While the algorithm could slightly reduce overall bandwidth utilization, it significantly reduced resource starvation and uneven resource usage between nodes. In another paper a group of researchers proposed that multiple packets be encoded together at once by XOR-encoding packets together. This method requires nodes to remember recent packets they have heard, as well as track other neighbor state, but could result in as much as 4x improvements in bandwidth usage. Lastly, we learned of a proposed technique to allow nodes to cooperate with another in sending a packet across a multi-hop network. When a node fires a batch of packets, all capable listeners are enabled to assist those packets in traversing the network, so that even if the original next-hop destination failed to hear some packets nearby neighbors could pass on the packets for it.
These innovative solutions showed me both just how difficult improving wireless networking and extending its use cases can be. At the same time, it showed me that difficult problems can provide fertile ground for creative thinkers to apply themselves.
Saturday, October 30, 2010
NIRA is a new inter-domain routing architecture that allows a sender to encode the route a packet should take to arrive at its destination. Currently a sender can only encode the destination of a packet; the routers that carry the packet to its destination decide the path it should take at each hop. User choice in packet routing could provide the infrastructure needed to offer several new services on the Internet. Some new services I was able to think of include:
For me, the largest barrier to a technology such as NIRA succeeding in the current world is related to usability. Right now users don't have to think at all about the route their packets take throughout the Internet. If a new technology such as NIRA forces this choice on end users, then it must offer benefits that are significant enough to offset the new burden the technology places on them More likely, existing technologies like browsers and browser plugins would be augmented to make the choice intelligently for users so that they don't have to think about it beyond possibly an initial setup.
It's hard to tell from a superficial analysis how beneficial route choice would be for the growth of the Internet and for society as a whole, but it is an interesting feature to ponder new possibilities with.
- ISPs could allow users to choose between multiple backbone providers and switch between providers at will. This could lead to increased competition among backbone providers as users become able to adjust their Internet plans dynamically based on price, quality of service, and other factors.
- ISPs could specialize in different QOS's related to voice, video, gaming, and other uses of the Internet for which standard TCP connections provide a less-than-optimal user experience. Users could then purchase standard Internet services using one route but purchase a different route for specific applications like video and voice conferencing or online games.
- Route choice could provide incentives to help ISPs transition to pay-as-you-go services. ISPs are currently struggling under the current unlimited monthly services model to remain profitable due to the uneven distribution of actual Internet usage among users. By allowing users to purchase from multiple different providers offering different QOS levels for different applications, users may become more acclimated to the idea of paying for the directly services that they use.
For me, the largest barrier to a technology such as NIRA succeeding in the current world is related to usability. Right now users don't have to think at all about the route their packets take throughout the Internet. If a new technology such as NIRA forces this choice on end users, then it must offer benefits that are significant enough to offset the new burden the technology places on them More likely, existing technologies like browsers and browser plugins would be augmented to make the choice intelligently for users so that they don't have to think about it beyond possibly an initial setup.
It's hard to tell from a superficial analysis how beneficial route choice would be for the growth of the Internet and for society as a whole, but it is an interesting feature to ponder new possibilities with.
Tuesday, October 26, 2010
Architecture Design Trade-offs
Most new networking designs have trade-offs; they offer new features and improvements but bring with them their own unique costs and caveats. It is little wonder then that agreement cannot be reached on how best to evolve the architecture of the Internet. The research paper on NIRA, a new inter-domain routing architecture, is one example of an Internet proposal upgrade. The proposal is elegant, relies on existing ideas and deployments like IPv6 as much as possible, and offers feature that could be useful for society. Specifically, the protocol aims to give users the ability to choose between available routes between a source and destination. As a side effect, it will also exhibit improved scalability relative to the existing inter-domain routing protocol BGP.
Of course, NIRA is not without potential flaws. First, it allocates IPv6 addresses in a specific way so as to limit other potential uses for the same address space. Second, it's protocol for communicating topology changes and user up-graphs has a per-message overhead linear with the number of domain-level links in a user's up-graph. Third, the network state a user must maintain is theoretically exponential in the depth of a user's up-graph. And last of all, if NRLS updates, analogous to DNS updates, are frequent they could also result in scalability issues as the Internet grows.
On one hand, the authors argue effectively that all of the above potential issues are unlikely to be realized in practice. On the other hand, the protocols of the original Internet also met their most important design goals, but at the same time have been stretched in ways their original authors never imagined. Is NIRA's added value important enough to integrate in the next Internet? Would its design weaknesses eventually become serious problems? As with the current Internet architecture, only time will tell!
Of course, NIRA is not without potential flaws. First, it allocates IPv6 addresses in a specific way so as to limit other potential uses for the same address space. Second, it's protocol for communicating topology changes and user up-graphs has a per-message overhead linear with the number of domain-level links in a user's up-graph. Third, the network state a user must maintain is theoretically exponential in the depth of a user's up-graph. And last of all, if NRLS updates, analogous to DNS updates, are frequent they could also result in scalability issues as the Internet grows.
On one hand, the authors argue effectively that all of the above potential issues are unlikely to be realized in practice. On the other hand, the protocols of the original Internet also met their most important design goals, but at the same time have been stretched in ways their original authors never imagined. Is NIRA's added value important enough to integrate in the next Internet? Would its design weaknesses eventually become serious problems? As with the current Internet architecture, only time will tell!
Saturday, October 23, 2010
The Lawmaker's Dilemma
Reading economic papers on network neutrality and discussing the issues in class made me to wonder how lawmakers manage to get anything done. The issues are deep, complex, and spans multiple fields including technology economics, and politics. As a computer scientist I have a fairly deep understanding of the technical issues behind net neutrality and the effects of such regulation on software companies and network providers from that perspective, but I admit ignorance on most of the economic arguments brought to bear by Yoo, Lessig, and others. Interestingly, in one Berkeley paper I read I found significant fault with several of the technical issues mentioned along with their interpretation in the debate.
A lawmaker with potentially limited understanding of the issues, or, more importantly, the ramifications of his or her decisions, seems to have no way of rendering a correct verdict given the conflicting views presented by different schools of thought on net neutrality. If the intellectuals can't come to a solid agreement, should lawmakers be expected to succeed where the experts have failed? To me, this foray into politics further strengthened my position that a government should seek to be as minimal as possible while ensuring the rights of the people. Net neutrality is too complex, the consequences of legislation too difficult to predict. Let a good strong economic engine flesh out the issues before executive action is taken.
A lawmaker with potentially limited understanding of the issues, or, more importantly, the ramifications of his or her decisions, seems to have no way of rendering a correct verdict given the conflicting views presented by different schools of thought on net neutrality. If the intellectuals can't come to a solid agreement, should lawmakers be expected to succeed where the experts have failed? To me, this foray into politics further strengthened my position that a government should seek to be as minimal as possible while ensuring the rights of the people. Net neutrality is too complex, the consequences of legislation too difficult to predict. Let a good strong economic engine flesh out the issues before executive action is taken.
Thursday, October 21, 2010
More than Two Sides to Network Neutrality
After reading two different economics papers on net neutrality, I learned to my surprise that there are more than two sides to the network neutrality debate! From these two papers alone I saw three major themes in the debate, one favoring a free market and two involving very different kinds of regulation. The free market argument, led by Christopher Yoo at Vanderbilt, asserted that the currently proposed neutrality regulations would cause more harm than good by limiting the freedom of network providers to innovate, to differentiate themselves, and to absorb the congestion costs of the Internet. In effect this would hinder them from competing with one another and would reduce the incentive for companies to invest in network infrastructure. Furthermore, according to Yoo, price discrimination based on type of service requested would be the optimal strategy to control Internet usage in a way that benefits both providers and consumers.
On the opposite end, neutrality regulation advocates, as exemplified by Lawrence Lessiag at Stanford, have a strong opinion on how the Internet should work in that it should be a "dumb" pipe used to transport data between endpoints. Like other utilities such as highways and electricity, discrimination should not occur based on purpose or type of use, source, or destination, as such discrimination would greatly reduce the overall value of the Internet to society for the benefit only of the network providers. In order to prevent any such future abuses of network infrastructure, the government should intercede now by outlawing this behavior.
Lastly, Douglas Hass argued in 2007 that an analysis of the history of the Internet reveals that control over its direction has always been primarily dictated not by any national or local ISPs but by the purchasing power of users themselves. He gives a few high profile examples of attempts, perceived or real, at violating net neutrality and the backlash responses that have kept the Internet mostly in line. Furthermore because of how rapidly Internet technology has evolved, both at the infrastructure and application level, Hass believes we should not presume at this time to know what is best for the Internet in terms of neutrality. Instead, he advocates regulations that enforce transparency in the Internet services customers purchase, including transparency related to any kind of traffic discrimination a network provider might perform. This will allow users to be informed about their decisions and continue to drive the evolution of the Internet through their purchasing power.
Of all these opinions, I currently favor the last, although I now have a greater appreciation for the complexity of the issue. My biggest issue with the transparency approach is that it will be very difficult to define and enforce the regulations needed to ensure ISPs reveal all that they should about their network policies. However, if such transparency could be enforced, it alone would seriously regulate company behavior relative to neutrality simply based on the fact that their actions will be placed in the open for public scrutiny. Also, in the worst case, such regulation would reveal any glaring violations of net neutrality immediately as they occur, so that if more regulation is eventually needed it can be applied quickly and effectively.
As much as I admire the noble ideas of network neutrality, I also believe that the government already has its hands full regulating our selfish behavior as companies and as citizens. If unverifiable economic theory is the only proof of needed regulation, then perhaps it can wait until stronger proof is brought to light.
On the opposite end, neutrality regulation advocates, as exemplified by Lawrence Lessiag at Stanford, have a strong opinion on how the Internet should work in that it should be a "dumb" pipe used to transport data between endpoints. Like other utilities such as highways and electricity, discrimination should not occur based on purpose or type of use, source, or destination, as such discrimination would greatly reduce the overall value of the Internet to society for the benefit only of the network providers. In order to prevent any such future abuses of network infrastructure, the government should intercede now by outlawing this behavior.
Lastly, Douglas Hass argued in 2007 that an analysis of the history of the Internet reveals that control over its direction has always been primarily dictated not by any national or local ISPs but by the purchasing power of users themselves. He gives a few high profile examples of attempts, perceived or real, at violating net neutrality and the backlash responses that have kept the Internet mostly in line. Furthermore because of how rapidly Internet technology has evolved, both at the infrastructure and application level, Hass believes we should not presume at this time to know what is best for the Internet in terms of neutrality. Instead, he advocates regulations that enforce transparency in the Internet services customers purchase, including transparency related to any kind of traffic discrimination a network provider might perform. This will allow users to be informed about their decisions and continue to drive the evolution of the Internet through their purchasing power.
Of all these opinions, I currently favor the last, although I now have a greater appreciation for the complexity of the issue. My biggest issue with the transparency approach is that it will be very difficult to define and enforce the regulations needed to ensure ISPs reveal all that they should about their network policies. However, if such transparency could be enforced, it alone would seriously regulate company behavior relative to neutrality simply based on the fact that their actions will be placed in the open for public scrutiny. Also, in the worst case, such regulation would reveal any glaring violations of net neutrality immediately as they occur, so that if more regulation is eventually needed it can be applied quickly and effectively.
As much as I admire the noble ideas of network neutrality, I also believe that the government already has its hands full regulating our selfish behavior as companies and as citizens. If unverifiable economic theory is the only proof of needed regulation, then perhaps it can wait until stronger proof is brought to light.
Sunday, October 17, 2010
BGP is well-known for its faults. To me, it is interesting that the protocol is so different than TCP/IP, a protocol pair that has managed to scale so well as the Internet as grown. Using the deficiencies of BGP described in the paper "HLP: A Next Generation Inter-domain Routing Protocol", here a several ways in which the two protocol families differ.
- Scalability. TCP has scaled well as the number of users on the Internet increases because it has little to no intermediate state of interest to any other connections. TCP has had a difficult time scaling as available bandwidth and connection latency have both increased, but sender-only additions have been made to address this issue. BGP, on the other hand, doesn't scale as well. BGP routers must maintain state linear with the size of the Internet, and the number of globally visible state updates also grows linearly to the Internet size to synchronize this state.
- Convergence. TCP converges on one thing only: packet drops. Even though packet drops are related to a single piece of intermediate state, router queue size, the drop events themselves are local in scope, which greatly simplifies the transmission rate convergence process. BGP, on the other hand, as mentioned above, maintains a significant amount of global shared state. Furthermore, sender-side additions to TCP have greatly increased its ability to converge more rapidly to a healthy transmission rate, whereas no such improvements have been made to BGP.
- Fault isolation. Because of its initial use for military communication, the TCP/IP stack was designed to continue to operate in the face of local failures through the means of storing state on the ends. BGP, on the other hand, frequently requires global state updates to handle local faults.
Overall, the primary difference between the two protocol families is that one keeps all of its state on the ends and the other keeps complex state at the core of the Internet. While this analysis may not lead to improvements in BGP or inter-domain protocols, it is interesting to compare the two types of protocols to help understand the origins of BGP's current flaws.
- Scalability. TCP has scaled well as the number of users on the Internet increases because it has little to no intermediate state of interest to any other connections. TCP has had a difficult time scaling as available bandwidth and connection latency have both increased, but sender-only additions have been made to address this issue. BGP, on the other hand, doesn't scale as well. BGP routers must maintain state linear with the size of the Internet, and the number of globally visible state updates also grows linearly to the Internet size to synchronize this state.
- Convergence. TCP converges on one thing only: packet drops. Even though packet drops are related to a single piece of intermediate state, router queue size, the drop events themselves are local in scope, which greatly simplifies the transmission rate convergence process. BGP, on the other hand, as mentioned above, maintains a significant amount of global shared state. Furthermore, sender-side additions to TCP have greatly increased its ability to converge more rapidly to a healthy transmission rate, whereas no such improvements have been made to BGP.
- Fault isolation. Because of its initial use for military communication, the TCP/IP stack was designed to continue to operate in the face of local failures through the means of storing state on the ends. BGP, on the other hand, frequently requires global state updates to handle local faults.
Overall, the primary difference between the two protocol families is that one keeps all of its state on the ends and the other keeps complex state at the core of the Internet. While this analysis may not lead to improvements in BGP or inter-domain protocols, it is interesting to compare the two types of protocols to help understand the origins of BGP's current flaws.
Subscribe to:
Posts (Atom)