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

2. The Design Philosophy of the DARPA Internet Protocols

• 1. This paper attempts to capture some of the early reasoning which shaped the Internet protocols developed by DARPA.
• datagram / connectionless service, no emphasis in the first paper
• 2. Fundamental Goal: top level goal for DARPA: multilexed ultilization of existing interconnected networks (ARPANET <-> ARPA packet radio network) (LAN not emerged)
• technique selected: packet switching, instead of circuit switching.
• Top level assumption: connected by Internet packet switches, also called gateways.
• 3. Second level goals: clearer definitions of "effective": (priority)
• 1) communication must continue despite loss of networks or gateways, (military)
  
• 2) support multiple services,
• 3) accommodate a variety of networks,
• 4) permit distributed management,
• 5) cost effective,
• 6) permit host attachment easily,
• 7) resources used must be accountable
• 4. Survivability in the face of failure: transport layer provides no facility to communicate to the client. sync never lost unless there was no physical path
• state info of the on-going conversatoin must be protected from loss. if lower layers lost this info, they won't be able to tell if data were lost.
• 5. Types of service: suould support a variety of types of service at the transport service level, distinguished by speed, latency, reliability, etc.
• traditional type of service is bi-directional reliable delivery of data, "virtual circuit" service. remote login or file transfer was the first service provided in Internet architecture, using TCP. (delay / throughput requirements)
• impossible to support all services into one protocol. e.g. 1) XNET (cross-Internet debugger) -- shouldn't be reliable, 2) live voice chat, smooths the delay, missing packet replaced by silence
• TCP provides reliable sequenced data streams; IP provides basic building block, the datagram (UDP: User Datagram Protocol)
• 6. Varieties of networks: long haul (ARPANET, X.25), short haul (Ethernet, ringnet), boradcast satellite nets (DARPA Altantic Satelite Network), packet radio networks, etc
  
• flexibility achieved by making a minimum set of assumptions about the functions the net will provide. packet or datagram.
• 7. Other goals: distributed management, gateways.
• Problems of Internet today: lack of sufficient tools for distributed management, esp routing.
• headers of Internet packets are long (40 bytes). e.g. remote login packets, only one byte of data with 40 bytes of header.
• problem of host-resident machanisms -- poor implementation may hurt the network and the host
• accountability: the Internet contains few tools for accounting for packet flows
• 8. Architecture and implementation: the architecture tried very hard not to limit the services the Internet could provide.
• 9. Datagrams: 1) eliminate the need for connection state, i.e. Internet can be reconstituted after a failure, 2) provides a basic building block
  
• 10. TCP: window management, port address structure. original ARPANET provided flow control both on bytes and packets. TCP - only bytes. reasons: 1) to permit the insertion of control info, 2) permit TCP packet to be broken up in to smaller packets if necessary, 3) permit a number of small packets to be gathered into one larger packet
• EOL / Push changes
• 11. Conclusion: datagram solves the most important goals, but not so well when addressing some goals durther down the priority list. there may be a better building block than the datagram for newer generations of architecture.

1.End-to-End Arguments in System Design

• end-to-end argument def: functions at low levels may be redundant when compared to the cost of providing them at that low level
• authors suggest moving functions upward in a layered system
• possible problems for end-to-end transmission: hardware faults, software mistakes in buffering and copying, processor or memory transient errors, packet drops or duplicates
• e.g. file transfer program: A->B, B calculates checksum of the original and sends it back to A
• communications level proposal of file transfer to achieve a reliable data transmissions: selective redundancy in packet checksums, sequence number checking, internal retry mechanisms
• authors suggest that the comm level proposals has "no effect on inevitability or correctness of the outcome", and that the file transfer program must supply the reliability guarantee itself
• e.g. app programmers know there's a packet checksum on the gateways so they didn't include any checksums in the program level. A bite pair interchange occurred in one gateway, which happens every million bytes. Files were corrupted and manual comparison has to be made.
• performance aspects: authors suggest that the lower levels need not provide prefect reliability since app level has to do it anyways, and that it's probably not important to strive for a negligible error rate at any point below the app level. If error-checksum related functions were performed in network comm level, 1) those apps that don't need them will pay for it, 2) low-level may not have enough info and cannot do the job efficiently
• **thoughts**: detect bit-error rate in the communications level and decides if there's any need for checksum?
• delivery guarantees: low level may be wasting its effort providing a function that the app level will implement anyways (ARPANET example: knowing for sure that the msg was delivered to the target isn't very important)
  
• secure transmission: 1) low level encryption/decryption must be trusted to manage the keys, 2) data will be in the clear and vulnerable, 3) authenticity must still be checked by the app. Encryption in low levels may be called for if necessary.
• **thoughts**: so why not call for the checksums in communications layer when it is needed? leave the decision to the application designer
• duplicate message suppression: app level duplicates look different to comm system, so it cannot suppress them
• guaranteeing FIFO message delivery: an independent mechanism at a higher level must control the ordering of actions
• transaction management: applying end-to-end argument to SWALLOW distributed data storage system. Low-level does not suppress duplicate messages since 1) object identifier and version info suffices to detect duplicates, 2) effect of a duplicate read request is only to generate a duplicate response, which is easily discarded. Thus, data comm protocol is significantly simplified.
• Identifying the ends: live voice chat, live video streams: mild packet loss is acceptible, low-level checksum isn't important; voicemail: short delays are ok, so low-level reliability measures is okay.
• **thoughts**: so why not call for the checksums in communications layer when it is needed? leave the decision to the application designer
• Conclusions from the authors: awareness of end-to-end argements can help program designers not to be tempted to write more functions than necessary. end-to-end argument will help to add substance about proper layering of communication protocols.