AIT

In distributed system one can satisfy at most 2/3 properties

1. Consistency means same data at any time

2. Availability means allows operations any time

3. Partition-tolerance means continuous work in spite of partitions

1. Randomly by system

2. Manually by administrator

Parallelize and process directly at location

Speedup of parallelizable portion p is S=1/((1-p) + p/n)

S is only upper bound due to overhead and workload imbalance

1. Maximize portion p

2. Balance workload

3. Minimize overhead

1. Independent requests // Rarely connections across requests

2. Little read-write (so-called producer-consumer) sharing

Goolge’s Query-Serving Architecture

1. Random distribution of data

2. Many redundant replicas used for load balance

1. Request to next Warehouse Scale Computer (WSC)

2. Load balancer redirects to cluster within WSC

3. Forward to Google Web Servers (GWS) handling request

4. Ask index server for relevant documents

5. Return relevant document list

6.1 Get indexed documents with IDs

6.2 Ad system and images

7.1 Order resulting documents

7.2 Decorate with sponsored links

1. Compute largely distributed data with simple computations

2. Tolerate faults

MapReduce (MR)

1. By Google for ~20EB/d

2. Two phases map and reduce

3. Automatic parallelization across large-scale clusters

4. Handle failures, efficient communication and performance

1. Web crawl // Outgoing links from HTML documents

2. Google Search

3. Google Earth

4. Google Maps

5. 10k MR programs at Google in 4 years

6. 100k MR jobs per day in 2008

1. Data are key-value (K,V) pairs

2. Input split means to split data for single map tasks

3. Map function for each split

4. Partitioner for a set of mapper

5. Reduce function for one out_key in a partition

6. Tasks

Data is shared among cluster but have single namespace

1. Input in_key and in_val

2. Output out_key and intermed_value

Sort out_key together for a reducer by sort

1. One key can have multiple appearances

2. Input out_key and list of intermed_value

3. Output out_value

1. In isolation

2. Limited communication for scalability and fault tolerance

3. Restart tasks in case of node failure

4. Run multiple task copies // Requires scheduling

5. One data chunk per map is common

1. Master Slave architecture

2. Slave Task Tracker (TT)

3. Master Job Tracker (JT)

4. TT pulls periodically with task request // heartbeat

5. JT assigns Map locally and Reduce anytime

6. JT re-assigns jobs if heartbeat stops

7. JT re-assings slow tasks (so-called stragglers) // Speculative execution

Fog computing

1. Computing on network edges with end-user clients

2. Good concept for IoT

3. Combination of cloud computing P2P and control plane

1. Software connected to hardware // Buggy software

2. Operating the network is more than half the total cost

3. Slow protocol standardization and long delays for new features

4. Evolution of becoming faster instead of better // Compared to other areas

1. Data plane (DP) (sending data) and 2. control plane (CP) (Where to send data)

1. Efficient routing // Distributed algorithms, adjusting weights, MPLS

2. Isolation // ACLs, VLANs, Firewalls

1. No modularity

2. (Too) many mechanisms without abstraction

3. Limited functionality

1. Forward

2. Filter

3. Buffer

4. Mark

5. Rate-limit

6. Measure

1. Forwarding state and 2. packet header

1. Track topology changes

2. Compute routes

3. Install forwarding rules

4. Generate forwarding states

1. CLI

2. SNMP

1. OSPF

2. ISIS

3. BGP

1. Abstractions for the network domain // Programming languages and OS

2. No additional functionality only better organization