22. A Performance Comparison of Multi-Hop Wireless Ad hoc Network Routing Protocols

This paper describes a wireless networks without fixed access points. This point-to-point connection is commonly refered to as ad hoc network. Four design choices were compared, namelyu, DSDV, TORA, DSR, and AODV. An extended version of ns-2 network simulator was used to test these different designs.

Each node in this infrastructureless network is linked by a single physical channel, and the power level where the packet was received is compared to two values,

sent to MAC layer

------------------ value 1) carrier sense threshould

packet error

------------------ value 2) receive threshould

noise

Distributed Coordination Function (DCF) is implemented to model the medium access control. it is similar to MACA and MACAW which use physical carrier sense and virtual carrier sense to reduce collisions.

Four protocols compared through topology change, see how packets react to it:

• Destination-Sequenced Distance Vector (DSDV): hop-by-hop distance vector. All nodes broadcast routing updates.
• Temporally-Ordered Routing Algorithm (TORA): "link reversal" discover routes on demind, sometimes longer routes are used to avoid discovering new routes.
• Dynamic Source Routing (DSR): complete list of nodes it passes through
• Ad Hoc On-Demand Distance Vector (AODV): combination of DSR and DSDV. combines 1) DSR: route discovery and route maintenance; 2)DSDV: hop-by-hop routing, sequence #s, perodic beacons

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

This paper is trying to solve the connection problems on multi-hop wireless networks like the previous paper on Rooftop network. But instead of having the antennae on the rooftops, this time it is placed in a university building with 29 nodes totally. The authors didn't really mention how they chose the locations of their hotspots, however. And they put it clear that mobility of these wireless access points are not put into consideration.

The factor they are trying to change in the 802.11b network this time, is the hop counter for routing protocols. It uses an Expected Transmission Count (ETX) which incorporates the ideas of:

• masking transmission errors, so that all but the worst connections appear loss-free
• finding a path with the fewest expected number of (re)transmissions
• predicting packet loss ratios in both directions of each link, so asymmetrical link speeds are taken into consideration
• penalizing interference between hops on multi-hop network

ETX = 1 / ( forward delivery ratio * reverse radio ), assumptions:

1. for protocols with link-layer retransmissions, such as 802.11b
2. fixed transmit power for the wireless

The fact that ETX does not avoid congested links makes it free from load-adaptive link delays. It also prefers paths less than 3 hops even when 4+ hops have better throughput, and avoiding wireless interference.

20. Architecture and Evaluation of an Unplanned 802.11b Mesh Network

This paper describes an experimental 37-nodes wireless network in Cambridge, Massachusetts. Users volunteer to install an antenna on their roofs and either connect it to a home broadband connection or not. Average throughput of the Rooftop network is 627 Kbps with averaging 3 hops.

Roofnet uses a unique addressing system on top of IP addresses. A special routing protocol, Srcr, was also introduced to automatically update the routing table among different wireless access points. Since most of the links in between are rather weak, the routing must find an optimum throughput itself. This is called Estimated Transmission Time (ETT).

Roofnet also uses its own algorithm, SampleRate, to determine the bit rates of 1, 2, 5.5, 11Mbps in 802.11b network. The decision is based on actual data speed rather than periodic probes.

Comments:

• The beauty of this system is that, you don't need elaborate planning ahead where to put the wireless hops. The antenna is omni-directional, and software is self-configured.
• I'm not sure if this is ever popular in the States, but there's this thing called FON, which basically gives you an almost-free wireless AP if you agree to share your existing Internet access, whether charging your users or not. And when you are out of your own FON AP, you can access others' depending on your sharing mode. This is/was very, very, very popular in Spain. Would it be possible to apply similar techniques to the FON firmware and give it a try?

19. Modeling Wireless Links for Transport Protocols

This paper provides a lot of background knowledge of wireless links and reviews several protocol solutions. As stated in previous papers, wireless networks have different bandwidth, lossy link, channel allocation delays, and asymmetrical data flows. Ad-hoc and sensor wireless networks are not discussed here, and the focus is mainly in wireless unicast transport protocols.

The main issues why TCP doesn't work well in wireless links are listed as follows,

• packet loss is considered as network congestion, lossy link isn't implemented in a separate packet header
• high round-trip time (RTT)

But in order to achieve interoperability between wireless and LANs, it is still beneficial to use the same TCP stack. Some error assumptions can be made on wireless links. For example, in poor GSM connections, timeouts should be rather common if running on TCP, but real world simulations show otherwise because the delay pattern is more of jitter in packet arrivals, resulting in higher values of TCP retransmit timer.

Several models are suggested so that researchers can simulate more accurately,

• Error losses and corruption: dropping packets probabilistically on a time-based loss, or by per-packet, or per-bit
• Delay variation: by suspending data transmission.
• Packet reordering: swapping two packets in the queue at a given time
• On-demand resource allocation: giving and additional delay when packets arrive at queue
• Bandwidth variation: changing bandwidth. e.g. CDMA2000 0.02-20s / 9.6~163Kbps.
• Asymmetry in bandwidth and latency: configuring uplink/downlink with different parameters for bandwidth and latency.
• Queue: WLAN, drop-tail; satellite, RED. (large buffer causes high queuing delay and poor loss recovery; small low link utilization and frequent packet drops)

Comment: This paper provides abundant background knowledge of wireless network and ways of simulating the iffy link environment. It is also very interesting to know that handovers happen once per minute while driving in a urban area.

18. A Comparison of Mechanisms for Improving TCP Performance over Wireless Links

In TCP protocol, packet drops are mostly considered to be network congestion. But in wireless links, they could result from iffy link conditions. TCP doesn't tell the difference between these, and drops transmission window size before retransmitting packets, and the link speed will be going from bad to worse.

Two approaches:

• hide non-congestion losses from TCP sender, making lossy link appears as high quality link with a reduced bandwidth. AIRMAIL, indirect-TCP, snoop protocols
• make sender aware of wireless hops and packet losses are not because of congestion, good bandwidth

Several schemes were proposed and are compared in this paper, including

• end-to-end retransmissions: selective ACKs (SACKs), Explicit Loss Notifications (ELN)
• split-TCP connections: hide wireless link from sender
• link-layer proposals: hide link losses from TCP sender by local retransmissions and forward error correction on wireless links

Benchmark was measured by throughput and goodput for wired and wireless link.

Comment: Would it be possible to apply XCP on wireless link because it has an extra field of congestion level, so that packet drops of lossy link can be distinguished from congestion?

17. MACAW: A Media Access Protocol for Wireless LAN's

Wireless network is a shared environment and resource is limited. WLAN are either token-based or multiple access. The protocols discussed in this paper focus on multiple access, including Carrier Sense Media Access (CSMA), Multiple Access Collision Avoidance (MACA), and their own modification of MACA, called MACAW.

CSMA:

• avoid collisions by testing the signal strength nearby
• collisions occur at receiver side, not sender

MACA:

• A Request-to-Send RTS) packet is sent before the transmission starts, and receiver respondes with Clear-to-Send (CTS) packet.
• Upon receiving a(n) RTS/CTS, all stations defer according to the proposed data transmission length included in the packet.
• avoids collisions at receiver, not sender
• Binary exponential backoff (BEB): backoff time is doubled after every collision, and reduced to min after every successful RTS-CTS exchange (unfair)

MACAW:

• add a backoff counter in the packet header to achieve fairness
• gentle adjustment when there's a collision (1.5x and -1, Multiplicative Increase and Linear Decrease, MILD)
• multiple stream model to be fair among uplinks and downlinks
• basic message exchange (802.11)

Comment: The idea of adding an ACK in RTS-CTS is great, and their high throughput / fair allocation lives up to the trend of today's network. I just wished they had more real world experiments to proove that MACAW is, indeed, better than MACA.

16. Understanding TCP Incast Throughput Collapse in Datacenter Networks

The unique workloads and fast connection low latency characteristics of data centers somewhat differs from what TCP was designed for in the first place. The infamous TCP incast collapse is a major problem in modern data centers. This paper analyzes the dynamics of incast and provides experiment results among different solutions.

The authors approach the incast from three perspectives,

1. it is not limited to particular network environments
2. causes of the problem should be identified and symptoms should be predictable
3. modifications to TCP stack to solve it

Method: synchronized read requests 100 blocks of data from a set of 1-48 storage servers

Things that do NOT help: TCP Reno, New Reno, SACK

Things do:

• reducing min value of RTO (but randomizing the minimum and initial RTO doesn't work, which is against intuition),
• fine-grained OS timers for sub-milisecond RTO,
• randomizing RTO,
• disabling TCP delayed ACKs when possible.

Comment: I like the way they search out all current solutions, but where are the analysis results from all these different working methods to TCP incast problem?

15. Safe and Effective Fine-grained TCP Retransmissions for Datacenter Communication

This paper deals with the TCP incast problem when inbound data overflows the switch buffers by using high resolution timers for TCP time-outs. When there are multiple end-node sending out queries, the client side cannot make forward progress until they receive responses from every server, this is referred to barrier-synchronized requests in the article.

TCP incast collapse:

• high-bandwidth, low-latency networks with small buffers in the switches
• clients issue barrier-sync requests in parallel
• servers respond with small amount of data per request

By enabling microsecond-granularity retransmission time-outs (RTO), the authors intended to solve the incast problem commonly seen in data centers,

1. modify TCP implementation to use high-resolution kernel timers, timeout = 2^backoff (RTO+ rand(0.5) * RTO )
2. prevent TCP incast collapse for up to 47 concurrent senders
3. recover in data centers do not affect performance

Comment: This is a different approach to solve the problems in data centers. The other papers we read strived for backward-compatibility, while this one modifies the TCP stack. Since data centers are usually confined to a fixed location and managed by normally one company, I guess it is a feasible way to solve TCP incast collapse.

14. VL2: A Scalable and Flexible Data Center Network

Today's data centers prevent high utilization, according to the authors, by several ways:

• Not providing enough capacity between the servers.
• Congestion and high resource utilization occurs in some of the servers while others are rather lightly-loaded.
• When one service has a traffic load, all other hosts in the same tree/branch suffer collateral damage.
• Lack of easy migration of VLANs.

By measuring network traffic, flow distribution, analyzing traffic matrix and failure characteristics, Virtual Layer 2 (VL2) is introduced to address the above issues. Design:

• Valiant Load Balancing to do random traffic spreading over multiple paths
• Based on IP
• Ability to host any service on any server, separating server names from locators.
• Replaces ARP queries to VL2 directory

Comments:

1. The last 2 papers are both IP-based to achieve backward compatibility, and replaces ARP broadcasts with queries to a specific server. Seems very promising in today's economy: optimal utilization with existing hardware.
2. It's good to see a paper addressing the 144-ports switches and 24-ports from the cost-effective perspective. It's very practical and yet hardly mentioned in "research", which kind of reminds me when I had my master thesis proposal, my advisors laughed at the idea of my mentioning how much can be saved if the technique could be implemented. I guess after working for Microsoft Research, the authors live in a more practical world than most of us bookworms, haha.

13. PortLand: A Scalable Fault-Tolerant Layer 2 Data Center Network Fabric

With the rapid growth of the Internet, modern computer trends are data centers with multi-core processors and end-host virtualization according to the paper. In view of the shortcomings of SEATTLE and TRILL, the authors proposed PortLand in order to make a plug-and-play-friendly environment for data center system administrators.

PortLand deals with the following issues successfully:

• Virtual Machines (VM) may migrate from one physical machine to another, and they don't need to change their IP addresses
• No switch configuration needed before deployment.
• Any end host can communicate with other hosts in the data center along any physical path.
• No forwarding loops (as SEATTLE would have when the number of hosts grow).
• Rapid failure detection.

Design of PortLand: layer 2 routing, forwarding and addressing for data center

• Fabric manager: centralized network topology, assisting ARP
• Positional Pseudo MAC Address (PMAC): provides location of the host in the topology
• Proxy-based ARP: intercepts IP2MAC and forwards to fabric manager, avoiding broadcast storm
• Distributed location discovery: applying location discovery protocol (LDP), so positioned can be changed without manual overriding.
• Provably loop free forwarding: after LDP, switches update their forwarding tables.
• Fault tolerant routing: switches informs fabric manager; fabric manager updates with the new info; fabric manager informs all affected switches

Comment: The idea of a plug-and-play data center network sounds great, but their simulation seemed to be performed locally. Is there any way it can also be used on 'cloud computing'?

12. Detailed Diagnosis in Enterprise Networks

From experience in small enterprise networks, the authors developed a diagnosic system scalable to large networks by analysing joint behavior of two components in the past and estimate the impact of current events.

• existing diagnostic systems: lack detail, require extensive knowledge, sacrifice details
• NetMedic:
  • framing detailed dignosis as an inference problem
  • estimate when two nodes in the network are impacting each other without knowing how they interact
  • captures state of network using many variables
  • application unrelated

By anaylizing logs of small enterprises for a month with 450,000 entries, a classification of the problems is established. Component states were captured and dependancy was generated to determine which impacts which. Later it is implemented to large enterprise networks and it works successfully and identifies 80% on their top 10 list.

Comment: I remember a couple years ago, NetMedic was THE hip network diagnosis software like Norton SystemWorks. Are they still popular these days? It's interesting to see they "trained" the software with small ethernet network and implements it on large networks.

11. Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises

The authors try to build a protocol that integrates the scalability of IP and simplicity of Ethernet.

• Advantages of ethernet: persistent MAC addresses, bridged automatically to build routing table (ARP, DHCP); plug-and-play
• Disadvantages of ethernet: initial setup includes broadcasting, consumes resources, security and privacy issues
• Pros of IP: shortest-path routing
• Cons of IP: subnetting wastes address space; Virtual LANs (VLANs) inefficient for large spanning trees

SEATTLE (Scalable Ethernet Architecture for Large Enterprises):

• one-hope, network layer DHT: stores the location of each end-host, distributed directory
• traffic-drive location resolution and caching: routers cache responses to queries; includes location info on ARP replies
• scalable, prompt cache-update protocol: based on unicast, instead of broadcast/timeout to update cache

Simulation: measures on cache eviction timeout, forwarding table size, path stability, switch failure rate, and host mobility rate.

Comment: In view of the high human-error rate of the previous reading "BPG Misconfiguration," SEATTLE's idea about making the network "plug-and-play-able" seems to be very convenient and fool-proof. While at the same time, it provides network administrators to customize network transport. Since this is a 2008 paper, I wonder how it works in the real world?

10. Congestion Control for High Bandwidth-Delay Product Networks

This paper proposed a new protocol in replace of TCP. The new protocol, eXplicit Control Protocol (XCP), addressed the issues of TCP by putting a congestion level field called Explicit Congestion Notification Proposal (ECN) in the packet headers. This XCP protocol does not maintain a per-flow state in routers and thus, requires less CPU cycles in busy routers.

TCP doesn't react well with high bandwidth, high latency links such as satellite and wireless. Under such circumstances, TCP tends to be unstable and oscillate. For example, TCP sends one packet per RTT to get more bandwidth, and it can takes thousands of RTTs to make good use of the high speed network.

Robustness to congestion should be independent of number of flows, according to the authors. And packet loss shouldn't be a signal of network congestion. Thus, XCP introduces decoupling utilization control from fairness control, which adjusts its aggressiveness according to the spare bandwidth in the network and the feedback delay. It also has a per-flow control in the protocol, rather than in routers, to achieve fairness. Furthermore, XCP distinguishes error loss pack-dropping from congestion, which is quite useful on wireless connections.

Comments:

1. I like the fact that in XCP, packet drops caused by congestion are highly uncommon because it separates drops caused by link errors from network congestion. These two factors should be viewed independently in the protocol and acted upon accordingly.
2. Like every new stuff in our lives, backward compatibility is a big issue. XCP is just like IPv6 where everyone knows about it, but no one seems to be using it. Would it be possible to implement XCP concepts one level up in OSI model in order to be compatible with TCP?

9. Random Early Detection Gateways for Congestion Avoidance

This is yet another algorithm for congestion avoidance. The Random Early Detection (RED) is implemented by computing an average size of the queue, and drops a packet or sets a "congestion bit" in the header by the proportion that connection's share of bandwidth in order to reach a certain fairness for all the end-notes on the network. It is designed to with with TCP or any other protocols with build-in congestion control.

In a traditional manner, a network wouldn't know it is congested until a packet had been dropped, and this could be a problem because the response time would have been greatly increased. The RED algorithm tries to slow down the traffic before it reaches the maximum capacity (cliff) while maintaining a high throughput.

The most effective detecting of congestion lies in the gateway itself, according to this paper, because it can distinguish between transmission delay and queueing delay. RED gateways monitor the average queue size, and either mark the congestion bit or drop a packet to signal sender's connection, depending on whether the packets are marked "essential" or "optional".

RED calculates the average queue size in the gateway by a low-pass filter and an exponential weighted moving average, and compared it to a min and max threshold. If the size is greater than max, all packets going through are marked/dropped; less than min, none. If the value falls between min and max, the probability of marking/dropping a packet is a function of average queue size.

Comment: It makes perfect sense that they drop/tag a packet based on the connection bandwidth share of a specific host. But how do we define a "host"? Is it one TCP connection, one software, one port, or one network interface card?

8. Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks

There are several Fair Queueing (FQ) mechanisms in routers, such as the last paper, and Flow Random Early Drop (FRED). These congestion controls require the routers to maintain state and operate on a per-flow basis, and the authors suggest that it could be the complexity of the per packet processing that prevents from wide-range adoption.

Fair Queueing can be very effective for congestion control. But if it is implemented in every router, it could be very complicated and costly. In responde to this concern, they try to distinguish the core routers and edge routers, giving the former no per-flow state as well as FIFO packet scheduling system, while leaving the latter to do complex Fair Queueing. This is called Core-Stateless Fair Queueing (CSFQ) in this paper.

CSFQ uses a distributed algorithm that core routers do not maintain per-flow state but in stead carry the information throught a label in each packet's header generated from the edge routers.

Secondly, FIFO queueing with probabilistic dropping on input was peformed on the core routers. Fluid Model Algorithm was first demostrated for an idealized bit-by-bit version and later extend to a practical packet-by-packet version.

Simulations between CSFQ and other four additional ones, namely, FIFO, RED (Random Early Detection, drops packets long before buffer full state), FRED (Flow Random Early Drop, drops based on flow state), DRR (Deficit Round Robin, weighted FQ) were performed on single congested links, multiple congested links, and coexistence of different adaptation schemes. The result shows that CSFQ achieves relatively fair bandwidth. It's far better than FIFO or RED and comparable to FRED. But FRED quires packet flow classifcation while CSFQ does not.

The last part of this article gives the reasons why fair allocations are important and introduces punishment for malicious end-notes that uses its own TCP stack to gain more priority of the network data flow.

The traditional approach to achieve fair allocations are very complicated to implement at high speeds among all routers, since each router has to analyse current flow and packet header to reach a decision. CSFQ could be more scalable when the number of routers increases.

Comments: It is understandable to utilize CSFQ in Tier-1 peering since it could simply the processing on the routers since they are obviously the "cores". But do we consider Tier-2 and Tier-3 ISPs to be edges or cores?

7. Analysis and Simulation of a Fair Queueing Algorithm

Ccongestion control can be divided in two aspects, 1) source varies the rate sending data, 2) gateway implements routing and queueing algorithms. This paper focuses on the latter.

Queueing algorithms can be evaluated in three quantities: bandwidth, promptness, and buffer space. The most common queueing algorithm used today is first-come-first-servced (FCFS). It simply discards any incoming packets when its buffer is full, and end-nodes could manipulate its implementations to take advantage of the network bandwidth. Furthermore, it lacks promptness for Telnet-like applications.

In order to achieve fairness throughout the network, Nagle proposed a fair queueing (FQ) algorithm that gateways maintain separate queues for each end-node. It lets data flows to take turns transferring packets (round-robin). But the main problem of FQ algorithm is that it implements fairness in the packet number level but doesn't take the packet length in to consideration. Thus, the authors incorporate a buffer allocation policy into the FQ algorithm.

Simulations of FCFS and FQ at the packet level were performed with different flow-control and queueing algorithms. Modified FQ rewards good-willed end-nodes and provides good bandwidth and promptness.

Comments: This paper sort of answers my question in mind when I read the two papers of last session, which factors in malicious end-nodes and smart queueing, instead of simply divides the bottleneck bandwidth into equal amounts for each thru-traffic connections.

6. Congestion Avoidance and Control

The Internet had the first congestion crash back in 1986 between Lawrence Berkeley National Laboratory and U.C. Berkeley. This paper pointed out that the causes is in the transport protocol implementations instead of the protocols themselves, and offered detailed solutions and rationales behind with simple codes to solve the problem.

The idea of conservation of packets was brought for a connection in equilibrium, in which a new packet isn't put into the network until an old one leaves. Therefore, for the packet conservation to fail, there are three possible ways and solutions:

1. Connection doesn't get to equilibrium: by transitive of equality, if the first packets are sent only in responsive to an ack, the sender's packet spacing time will match on the slowest link in the path, this is also called self clocking. A slow-start algorithm is implemented by sending one single packet to start with and adjust the window according to the time between two ack packets arrive.
2. Sender injects a new packet before an old one has existed: a good round-trip time estimator is the single most factor of any protocol implementation for a heavily loaded network. The authors developed a method to estimate variations and the resulting re-transimit timer derived from RFC793.
3. The equilibrium can't be reached because of resource limits along the path: if timers are in good shape, timeout indicates a lost packet and not a broken timer. Packet lost is more likely to result because network is congested and there's insufficient buffer along the path, so a congestion avoidance strategy should be adopted. Multiplicative decrease (cut window in half), addtive increase (increase cwnd) on each ack of new data, and sending min advertised windows cwnd are the three lines of code to avoid congestion.

While at the end nodes could control their own data flows, there should be some congestion detection on the gateway side to insure fair sharing of the network capacity before reaching its maximum capacity.

Comment: It is good to read a self-explanatory paper that gives you all the detailed explanations behind each steps, while still keeping the code simple. Cal Rocks! haha. Seriously though, it wasn't easy to identy the problems that caused network congestion, particularly from the protocol implementation perspective. And I really liked the figures which include packet size, timing and bandwidth, all in a 2D diagram.

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

This paper reviews the algorithms used in avoiding network congestions and offers several suggestions throughout the article.

As fiber optics and gigabit local area networks are getting more popular these days, the link speed could vary from several giga bits-per-second (bps) to 56K bps dial-ups. These various types of networks co-exist in the network, and there has to be some sort of flow/congestion control to achieve maximum possible speed while keeping collision / dropped packets to the minimum.

Traditionally, congestion control schemes kick in when congestion occurs near it's max possible throughput (cliff), but the response time which starts to increase significantly while throughput remains about the same (knee), occurs before cliff. In this paper, this knee-working-range is called congestion avoidance, as opposed to congestion control that keeps the network working before cliff.

Congestion avoidance utilizes the same increase/decrease algorithm that congestion control uses. There's a binary feedback signal that simply tells if the network transport is busy (1), or not busy (0) in the QoS header. The abstract model assumes that all users on the network receive this information and act on it accordingly.

User data flow demands can either flow to centralized decision-making managers or to decentralized locations, which is this research is based on. The successfulness of congestion avoidance is measured in four aspects,

• efficiency: the closer the total load to the knee, the more efficient
• fairness: maxmin fairness criterion, bottleneck sharing within the same group
• distributedness: awareness of the congestion on the user end
• convergence: time taken to reach a relatively stable state (knee)

Congestion avoidance is achieved through network monitoring and asking users to increase or decrease their load appropriately by a binary system. The decrease of data flow must be multiplicative from the experiment results, and additive increase with multiplicative decrease is the optimal policy.

Thoughts:

1. Instead of sending a binary bit about the congestion status of the network, would it be possible to have, say, a multi-bits status for the level of the congestion? e.g. 00 for extremely congested, every user stops sending new packets for a random amount of time, 01 for severely congested, 10 for mildly congested, and 11 for light-workload, please send packets faster? This way the user sides could decide if they need to slow down a little bit or a lot.
2. As we discussed in the first week, some applications require reliable data transmission, others more latency-critical. Maybe this extra magic bit(s) could include how fast/reliable it wants to be handled?

4. Understanding BGP Misconfigurations

This paper is a quatitative study of Border Gateway Protocol (BGP) misconfigurations by analyzing configuration errors over a 3 week period. The authors concluded that most errors, while 1 on every 25 incidents actually affects connectivity, could be prevented through better router design or protocol revision.

BGP is a policy based protocal in which autonomous systems (ASes) receive and send routing information to hosts and neighbors. They put the misconfiguration into two categories: origin misconfiguration, and export misconfiguration. An example of the former is a wrong prefix injection into global BGP tables; for the latter, the router exports a route that shouldn't go through.

The effects of the misconfiguration were discussed in three different aspects, including routing load, connectivity disruption, and policy violation. The new routes lasting less than a day are carefully considered as misconfiguration while using external vantange points and administrator email surveys to check if it actually caused the above three kinds of effects. Selection bias is addressed by the authors, and by comparing the results of the email surveys and vantage points, it is kept to a minimum in a safe way.

The physical links and relationships between ASes are usually commercial secrets, and Gao's algorithm was used to estimate the actual linkage, which is based on three rules: 1) all valid AS-path routing information goes downward (e.g. from provider to customer), 2) AS-path can have at most one peer-to-peer edge, 3) ASes with more neighbors are likely to be providers.

Results: A equivalent to 0.2-1.0% of the glocal BGP table size suffers from misconfiguration each day, which means up to 3 in 4 new route annoucements per day are misconfigs. While connectivity was surprising solid, affected in onlly 4% of the misconfiged announcements or 13% of the misconfig incidents, the extra loading in the routers takes up to 2% of the time, or more than 10% of the total update load. In an extreme case, it went higher than 60% of the update load with 15minutes averaging.

The paper investigates the causes of misconfiguration and classify the human errors into slips (errors in the excution of a correct plan, e.g. typoes) and mistakes (erros in the plan itself, e.g., logic bugs). In owing to the human operatior error rate affects the system, as seen in phone network, aircraft, and bank databases, the authors suggests that BGP router configuration is far from error-free because of the command-based editing and lack of high-level languages and checking. Protocol revisions/extensions were suggested, and active alerting wrong routing infomation was also proposed.

Afterthoughts:

1. This is a carefully examined paper with almost all stastistical and bias errors were carefully considered, which makes the the results very confincing that the BDP is far from perfection.
2. It's interesting to see that they conducted this experiment after Christmas during the New Year. There's no explanation of why they specifically chose this period depite their careful, scientific setting. Is it probable that there is less/more routing updates during this period?

3. Interdomain Internet Routing

This paper is about how routing information is exchanged between service providers such as Border Gateway Protocol (BGP) as well as failures and shortcomings of the routing system.

In a more realistic view of the Internet structure, Internet Service Providers (ISPs) can be put into three categories, Tier-3 (small, local), Tier-2 (large, region-wide), and Tier-1 (really huge, "default free," only 10 as of 2009). Routing infomation is exchanged between these autonomous systems (ASes) with each assigned a unique 16-bit number address through BGP, while within the ASes, Interior Gateway Protocols (IGPs) were used. The difference between BGP and IGP is that the former implement autonomous routing policies, whereas the latter are usually non-concerned with optimizing a path metric.

There are two kinds of Inter-AS relationships, "transit" and "peering". "Transit" is the customer-ISP data traffic, in which customer is usually charged for the serive. "Peering" is the ISP-ISP traffic, in which may not involve financial settlement if the traffic radio is not highly asymmetric (4:1).

Reasons for peering relationships: 1) Tier-1 peering acts as an alliance of a certain size Tier-1 providers. Peering between Tier-1 ISPs ensures that they have default-free routing information to all Internet nodes. 2) Tier-2 and Tier-3 ISPs usually have to pay their upper tiers for asymmetric traffic, but if they could settle a new link between themselves, while generating roughly symmetric data flow, to save money, and to increase end-to-end performance.

ISPs charger customers for transit links and import/export routing tables to make or save money by peering in order to make profit. Since routing traffic to customers always generate income, ISPs tend to put customer traffic on top priority (local preference) and try to avoid a distant peering that cost them.

BGP sessions can be divided into two types, eBGP (between ASes), and iBGP (within ASes). They use the same protocol for different purposes. Two important goals have to be met when disseminating the routes, namely, loop-free forwarding, and complete visibility.

The lack of origin authentications weakens the BGP by letting network administrators hijack the routes by mistake (the YouTube example) or for profit (the spam example). A solution called secure-BGP (s-BGP) is proposed, but not yet implemented for a variety of reasons.

Comment:

1. It is interesting to learn how the money actually flows for the Internet Service from customer to ISPs and upper-tier ISPs, since everything is inter-connected in some ways.
2. A bit of googling shows that s-BGP uses Public Key Infrastructure (PKI) to authenticate the routing updates. It should make sense that s-BGP would replace BGP a.s.ap., but in this paper it says one of the reasons it isn't deployed is because of existing routing table errors! :-O