recitation network

computer systems › 6.033 system design

Paper:Ethernet

Ethernet: Distributed Packet Switching for Local Computer Networks

Background

  1. demands of computer-computer interconnection grow

  2. Reliability:

    packets are delivered only with high probability.

    • Fact: control is completely distributed among stations with packet transmissions coordinated through statistical arbitration.

Design choice

Problem 1: distribute control of the communications facility among the communicating computers

Choice

  1. Topology: an unrooted tree is better than a star network in distributed interconnections.

  2. Control

    Problem 2: collision: more than one packets are transmitted at the same time

    • Retransmission: controller would adjust the mean retransmission interval in proportion to the frequency of collisions.
    • equity: cooperation among the stations is required. This equality rule is maintained by low-level software in each station

  3. Addressing : packet(source, destination)

  4. Reliability : remove the responsibility for reliable communication from the packet transport mechanism

    从而把责任转移给应用层，更好地决定可靠性和恢复。

    • error-free communication(reliable delivery of any single packet) is hard. Instead, we choose to support reliable transport where it can get both economy of transmission and high reliability averaged over many packets

  5. packet transport mechanism

    Problem 3: reduce the probability and cost of losing a packet.

    Fact: a station connects to the Ether with a tap and transceiver.

    There are five mechanisms: (1) carrier detection, (2) interference detection, (3) packet error detection, (4) truncated packet filtering, and (5) collision consensus enforcement.

Alternatives of design choice

Implementation

performance measure

Acquisition probability, waiting time, efficiency

protocols

What does the term “layering” mean in the context of networking?

Why do we use a layered model?

How do you imagine that layered model is reflected in actual packets?

Paper: RON

Resilient overlay networks: an application-layer overlay on top of the existing internet routing substrate.

Problem 1: failure and latency

BGP 可扩展性同时造成的问题：端到端通信的容错性减少，导致网络延迟发生和延迟时间加长（几十分钟的程度）。这也让现有的网络非常脆弱，会由于各种问题而崩溃。

因为BGP出于可扩展性和政策执行的考虑，隐藏了许多拓扑细节，几乎没有关于交通状况的信息，并且在出现潜在问题时抑制路由更新以防止大规模振荡。

解决方法是在应用层上分布一层重叠的节点来完成连接。底层网络节点的变化不会扰动到上层，由此来解决可扩展性带来的问题。

General goal

  1. Main goal: enable a group of nodes to communicate in the face of problem1

    what RON can do:

    • 检测问题快：whether the underlying internet path is the best one
    • 交换交通信息
    • 限制RON path的大小以避免过度占用网络带宽，减少网络延迟

  2. integrate routing and path selection with distributed applications more tightly

    更针对性的建设网络通路

    • consult application-specific metrics in selecting paths
    • incorporate application-specific notions of what network conditions constitute a “fault.”

  3. provide a framework for the implementation of expressive routing policies, which govern the choice of paths in the network

Design goal

更准确的描述设计目标：

1 Fast failure detection and recovery

评估failure造成的影响。现有的BGP-4找到合适的线路通信经常会遇到failures。failure可以分为link failures和path failures。它们在应用中常表现为两种形式：outages or performance failures。outage对网络造成的影响能达到几个数量级（比如TCP degrades, average packet loss rate over a sustained period of several minutes）；而performance failures的影响则没有那么极端，仍在同等数量级下。

因此我们希望RON能够做到检测快和恢复快。

2 Tighter integration with applications

fact: Failures and faults are application-specific notions.

根据应用场景的不同而制定的标准（metrics）来选择合适的网络线路。理想的情况下，最合适的线路应该满足多种标准。

这里不同标准在实际应用之间的衡量（trade-offs）是设计考虑的重点。

3 expressive policy routing

RON’s powerful end-points allow fine-grained policy routing.

打个比方就就是地图精度更高了，路径规划也就越准确。

Design

1 Software architecture

  • RON client: forwarder, conduits

  • RON: router, membership manager

  • forwarding service:

    • IP paths
    • RON

  • forwarder: onduits access RON

    • send(pkt, dst, via_ron): forward a packet to a destination RON
    • recv(pkt, via_ron): callback function that is called when a packet arrives for the client program

2 routing and path selection

  • Routing = building up the forwarding tables -> choose paths for packets

  • default metrics for selecting the path:

    latency; packet loss rate; throughput

    • RON clients: can override defaults
    • RON library: construct the table
    • Router: build up forwarding tables following the demands
  1. link-state dissemination
  • small size of RON allows fast propagation
  1. path evaluation and selection

  • path evaluation is composed of combination of two links into a path and formula used to evaluate it.

  • Outage detection: whether the connection is still working?

  • Throughput path selection: avoid paths of low throughput when alternatives are available instead of an optimal one

    为了避免performance failure，选择一条相对合适的路径而不是直接中断。

    Problem: how throughput-intensive applications handle traffic?

    Solution:TCP or TCP-like congestion control

  1. performance database

    Demand:RON needs to know performance info

    Consideration:

    1. Performance repository must be reliable and flexible
    2. Measurement data : noisy, and many clients would want to use the data

    we conclude that the system needs a flexible summarization mechanism.

    -> each RON node or local group of nodes uses a separate performance database to store samples.

3 policy routing

  1. Classification：查找信息
  2. routing table formation：计算最短路径

two policy mechanism :

  1. Exclusive cliques

    比如校园网

  2. general policies

    更灵活地制定规则

4 data forwarding

5 Bootstrap and membership management

conclusion

Paper: DCTCP

Applications in datacencer network are expected to have these requirements:

  1. low latency for short flows
  2. high burst tolerance
  3. high utilization for long flows

Paper: E2E argument 1981

The function in question can completely and correctly be implemented only with the knowledge and help of the application standing at the end points of the communication system. Therefore, providing that questioned function as a feature of the communication system itself is not possible. (Sometimes an incomplete version of the function provided by the communication system may be useful as a performance enhancement.)

what

E2E argument is a reasoning against low-level function implementation. It is applied in many contexts but this paper chose data communication networks to provide more concrete details about it. For designers, it’s a guideline that helps in application and protocol design analysis rather than a rule.

ex: reliable data transmission in file transfer - “the function in question”

The same example as in the book with extra details on the file transfer machanism which is to retry/commit after dectect checksum failures.

Conclusion:

The end-to-end check of the file transfer application must still be implemented no matter how reliable the communication system becomes.

  1. Apps that perform file transfer must supply a file-transfer-specific, end-to-end reliability guarantee.
  2. Reliable transport does not guarantee the reliablity of apps.

performance view

  1. The lower levels need not provide “perfect” reliability. The effort to provide reliability at the lower level may cost more than the effort and still guarantee nothing.
  2. Engineering tradeoff: The effort to supply reliablity measures on the data communication networks is a tradeoff of performance.
  3. Function placement at the lower level may not be efficient for two reasons:
    • Function at the low level affects many applications. Other applications may not need this function.
    • The low-level subsystem has less information that high levels.
  4. ex: where to put reliable technique? File transfer application or communication system.
    • More efficient in communication system. Adding the reliable checks on every application is redundant.

How: identifying the ends

one must use some care to identify the end points to which the argument should be applied.

example 1: network carrying some packet voice connections between two telephones

example 2: speech message system, user listens to the voice message stored in the file system

A srong E2E argument will ask in-order delivery to provide reliability. In example 1, if it needs to preserve a bit-perfect communication, enforcements on the delivery order (low-level reliability measures) causing delay are disruptive. It’s better to receive damaged data and add replacement measures as duplication, noise for better performance. However, some applications like real-time communication require the strong E2E argument.

In example 2, a storage system is at the receiving end of the voice communciation. Short delays are not disruptive. So designers can consider the low-level reliability measure like packet ordering for correctness and performance.

Some thinking

  1. My opinions of E2E argument?
  2. How might one use the end-to-end argument when designing a system?
  3. What role does trust play in the end-to-end argument?
  4. Packet acknowledgement is ignored in this paper but becomes an esstial part of reliable tranport. Though, the E2E argument still influenced the design of TCP as being a layer above IP (From recitation notice).