CONTROLLI

CONTROLLI

1. CONGESTION CONTROL

   • way to manage packets in order to limit as much as we can them being stuck in a queue waiting their turn, in order to prevent packet loss if the congestion is too much (in non blocking network there's not this problem bcause we can always find disjoint paths)
     • General Approach: while True -> 1)measure congestion 2)adjust sending rate accordingly
       • either the sender, receiver or switch decide new sending rate, but always the sender adjusts it
     • for TCP
       • RED (Random Early Detection)
         • switch keeps track of avg length of the queue and keeps 2 threshold, if over the window drop every packet, if between, it drops a number of packet proportional to the level (we do that because waiting the queue to become full is bad, we have to react earlier)
       • ECN (Explicit Congestion Notification)
         • switch detects that pkts in a queue are over a certain threshold, so marks the pkt header ECN bit, the receiver sees it and tells in the ack to the sender so the sender halves sending rate
           • dropping pkt not that gud
           • always halving not that gud
           • what if we give more fine grained informations?
           • what if a switch cant modify header
       • DCTCP (Data Center TCP)
         • sender keeps moving avg of pkts marked with ECN and adjusts sending rate accordingly
     • for RDMA (for roce v1 and v2 cuz IB is lossless??)
       • PFC (Priority-based Flow Control)
         • (happens between switches) we got a bunch of queues in the switch and when one of those exceeds a threshold we send a pause frame, so I ask transmitter(another switch) to stop sending on that queue, when queue gets small enough I tell to restart (pause-stop mechanism between switches)
           • problems: queue can contain pkts from different applications (there can be more applications than queues), 1) so hard to determine threshold and 2)by stopping a queue we can penalize applications that are not contributing on the congestion (congestion speading. 3)Deadlock may happen (
             • deadlock
     • HPCC (High Precision Congestion Control)
       • instead of one bit in ECN field we use more to give more details, so every switch traversed adds his piece of infos (Telemetry: timestamp, queue length, transmitted bytes, and link bandwidth) that tell how congested were the queues traversed by the pkt, then the receiver acks the sender and the sender adjusts sendig rate accordingly (they have their own algorithm to decide it. There is some research on that and also reinforcement learning is being used to understand)
     • Delay as congestion signal
       • we measure RTT (Round Trip Time) of a pkt sent on the host. So we have a more outdated info with respect of ECN but measuring RTT is a more fine grained info

2. LOAD BALANCING

   • selecting path of a pkt in order to avoid congestion control
     • why not to have a global view of the net? it would mean have a global entity that receives infos from all th switches everytime and adjusts path accordingly, is not feasible. So each switch decides by itself based on a local view (that is an approximation, so rly hard to make it work properly)
       • In network Problem: U need advanced switches / Centralized problem: reactiveness.
   • Centralized
     • A global scheduler that continously checks on switches how long are their queues and tries to map that flow in a way. Its hard to react fast but there are some cases where worloads are predictable. Its good if network has big flows that last for minutes with steady traffic
     • Hedera
   • In Network
     • Congestion Oblivious (Chosing paths randomically)
       • ECMP (Equal Cost Multi Path)
         • Gets source and destination address and gives an hash in order to randomically select a path for the information flow.
           • Problemi: 1) given a random choice we are wasting half of the net potential on avg (61% bisection bandwith lost on a network with 27k server) 2) if a link dies, u will get notified later and so we wasted time bcasue it was a pre-selected path
       • Random Packet Spraying
         • Select a random path for each packet (instead of the entire messager)
           • Problemi: pkts may arrive out of order -> Issue with TCP (may trigger retransmission) but also with some RDMA protocols
     • Congestion Aware(keeping infos)
       • CONGA
         • CONGA: each switch has a table where they keep track of the congestion towards any other leaf switches across all different paths. Each flowlet is sent on the least congested path. Just flowlets can change path during the sending, so we know they arrive ordered and we dont risk retransmission. Hard to decide a working delta(if too small we switch too much and they arrive unordered, if too big we dont switch paths)
           • (Flowlets are goups of pkts of the same messages that differ from a certain time of transmission)
           • RDMA è + steady di TCP con flowlet
   • Host-Based (working on the host, cheap, dont need advanced switches)
     • Flow Bender
       • Similar to ECMP, uses ECN: switch must support ECMP, so it can compute the hash function and put a packet on a pth depending on such function. (hash gets source, dest address and a entropy setbyuser parameter). With ECN marks I know if a path is congested and can force hash to give another path changing entropy, getting a new path hopefully less congested
         • it works only if u have stable application with predictable patterns
   • we assumed all these approaches working on fat trees, so all nodes have the same distances, what about structures of different lengths?a layer of complexity is added, choose a longer but more empty path or a shorter but more congested one?
     • Issues with low-diameter networks (like Dragonfly)
       • In Network Compute: We have seen that some switches can modify fields in the header, there are also programmable switches based on Reconfigurable Match-Action Table
         • parser, sequence of match action units where u match fields and take some actions and so on, and eventually the packet goes out (so no loops, no conditional constructs...)
         • Use cases (Generally adding info to the headers help the quality of load balancing)
           • Map Reduce
             • Imagine having a big file and u want to count how many times a word occurs in that file, u give rows to different server and they compute the sum and then u sum up every result. What can we accelerate? --> swapping and reduction. Instead of computing everything on the host u do that on the switches. So a switch receives a info from 2 nodes and spit out the sum
               • So we choose mapper and reducer nodes: mapper forward the infos to the reducer. but we aggregate datas during the path, so the reducer will receive the full aggregated info. What if a switch becomes full? it just propagates its as it is and if the aggregation is incomplete when the information rechaes the reducer: it just finishes computing (cuz he has enough memory to do that)
                 • benefits: data volume reduced by 88%, time required to compute by 84%, n of packets reduced by 80%
           • Allreduce
             • so a centralized network not a good idea (bottleneck in receiving infos), so we can compute infos in the switch itself: so u send datas to the switch, it sums every vector and sends the result back. This works if every worker under the same switch, what if more switches?
               • we build a tree, each switch sums whatever it receives from the childs and forwards up, then data reaches the root and there is fully aggregated and then distributed below to the child
                 • Problems and solutions
                   • hard to realize cuz paths are static so u cant change in case of congestion, so with thounsands of nodes the probability of a link getting slower is high ----------------------------> just set a timer and if information is incomplete just send it, u will have an approximation
                   • floats dont work with association, so depending from the order of operations u can get different results. And an error like that propagates to the next computations. We could put temporary results in a buffer and at the end sum everything but we dont have that much memory so --------------------------------------> use fixed point numbers
                   • packet losses and switch failures --------> we need a resiliency protocol between switch and host and switch and switch. I could do a retransmission mechanism, I send a data to the switch and I expect a knock, if that doenst arrive after some time I transmit the same data again, but how can the switch determine if this is exactly the same data as before or its a new data to aggregate? Good solution, hard to implement and far from perfect

Imágenes y archivos del mapa