Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

University > Networks > Flashcards

Networks Flashcards

1
Q

Define Physical Layer

A

The physical part of a network (e.g. Cables, Radio Waves, etc.)
The path data takes is a channel (e.g. Frequency Range)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Define Link Layer

A

Responsible for sending frames (encapsulated packets) over one hop of the physical layer

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Link Layer: Frame Header & Trailer

A

Header: Source & Destination MAC Address
Trailer: Error Checking (e.g. Checksum). Uses Cyclic Redundancy Check (CRC) to identify corruption

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Link Layer: Flow Control

A

Regulation of data transmitted over a network to prevent congestion

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Link Layer: ARQ

A

Automatic Repeat Request. Re-transmits frames if Link Layer Acknowledgement (ACK) isn’t received before timeout

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Link Layer: Connection-oriented & Connectionless Communication

A

Connection-Oriented: Established dedicated connection e.g. TCP
Connectionless: Independently delivered frames e.g. UDP

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Link Layer: MAC Layer

A

Media Access Control sub-layer. Manages access to Physical Layer. CSMA/CD protocol ensures only one sender transmits at a time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Link Layer: LANs: ARP

A

Address Resolution Protocol. Determines MAC addresses using IPv4. Stores in ARP Cache (Vulnerable to Spoofing)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Network Layer: Define

A

Responsible for routing packets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Network Layer: MTU

A

Maximum Transmission Unit. Determines fragment size

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Network Layer: QoS Methods

A

Quality of Service Methods. Minimise loss of important data by giving critical data (voice, video, etc.) necessary bandwidth and low latency

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Network Layer: IPv4: Subnetting

A

Uses Subnet Masks to split on network into multiple sub-networks

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Network Layer: IPv4: NAT

A

Network Address Translation. Translates private IPv4 address to public IPv4 address.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Network Layer: IPv4: CGNAT

A

Carrier Grade NAT (CGNAT). One public IPv4, many ISP customers.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Network Layer: IPv6: Address Compression

A

Remove leadings 0s, compress longest consecutive 0s to ::

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Network Layer: IPv6: Link-local Address

A

For routing local network packets. fe80::/10

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Network Layer: IPv6: Path MTU Discovery

A

Determines MTU size on path to receiver, fragmentation occurs only once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Network Layer: IPv6: Deployment Issues

A

Time, Money, Hardware Support, Education

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Network Layer: ICMP

A

Internet Control Message Protocol. Adds a header to provide diagnostics before IP encapsulation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Network Layer: ICMPv6: NDP

A

Neighbour Discovery Protocol.

Neighbour Solicitation (NS) and Neighbour Advertisement (NA) messages to retrieve MAC addresses using IPv6 addresses

Router Advertisement (RA) and Router Solicitation (RS) to discover routers and config info (Network Prefix, Default Router Address, Address Allocation Type (SLAAC or DHCP))

Redirections inform hosts of better first-hop routers by updating routing tables.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Network Layer: ICMPv6: SLAAC

A

Allows hosts to configure their own IPv6 address without relying on a DHCPv6 server

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Network Layer: Routing Tables

A

Database of information about paths to destinations.
Gateway: Connection to another network (typically a router). ‘On-link’ means end point is on the same network
Interface: The point of connection
Metric: Priority, lower number is higher priority

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Network Layer: Traceroute

A

Determines route between two hosts by sending packets with increasing time-to-live (TTL) packets. ICMP time exceeded message sent
to sender when TTL is 0.
Latency not equal to RTT/2 as routes change quickly and routes are likely to be asymmetric

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Network Layer: Autonomous Systems (AS)

A

Interconnected networks managed by a single netwrok

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Network Layer: Multi-Homed AS

A

AS with multiple connections to other AS

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Network Layer: Transit AS

A

AS with no network of its own, just provides connections between AS

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Network Layer: Single-Homed/Stub AS

A

AS with one connection to another AS, typically a service provider

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Network Layer: AS: Interior Gateway Protocol

A

A routing protocol using within autonomous systems

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Network Layer: AS: Interior Gateway Protocol: Distance Vector Routing: RIP

A

Routers interact with only neighbour routers

Routing Information Protocol (RIP). Has a router send its routing table periodically to connected routers.
Limitations:
- Slow Updates (30s periodically)
- Unacknowledged (uses UDP)
- Poor Quality Metric (Hop count doesn’t take into account physical medium speed)
- Maximum Hop Count (after 15 hops, the router is deemed unreachable
- Cracked Authentication Hash (MD5)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Network Layer: AS: Interior Gateway Protocol: Link-State Routing

A

Routers interact with all routers to establish complete network knowledge

Broadcast reaches all routers and assigns cost
Dijkstras algorithm populates routing table
Benefits:
- Fast Updates
- Known Topology
- Avoids loops

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Network Layer: AS: Exterior Gateway Protocol: BGP

A

Route between autonomous systems

Border Gateway Protocol: Considers relationships with other AS. Neighbours choose whether to route by you
Drawbacks:
- Trust Based
- Slow
- Flapping
- Limited routing table

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Transport Layer: Definition

A

Responsible for data transfer between applications

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Transport Layer: UDP

A

Connectionless, Unacknowledged

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Transport Layer: TCP

A

Connection-oriented, Acknowledged (Uses SYN, SYN-ACK, ACK to establish connection)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

Transport Layer: TCP: Congestion Control

A

Manages flow of data to avoid overload.

Congestion window is number of bytes that can be sent over a network. The ‘Slow Start’ algorithm gradually increases the window until timeout and then resets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

Transport Layer: TCP: Flow Control

A

e.g. Sliding Window Protocol
Uses buffers and messages to allow sender to send data when buffer has enough space

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

Application Layer: Definition

A

Responsible for providing services to applications and users

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

Application Layer: DHCP

A

Dynamic Host Configuration Protocol.
Assigns IP addresses to reduce IP conflicts and simplify network administration
Uses DISCOVER, OFFER, REQUEST, ACK to assign IP addresses

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

Application Layer: DHCP Helper

A

Forwards DISCOVER messages from subnets to DHCP servers. Stops needed a server per subnet which is inefficient

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

Application Layer: DHCPv6

A

Uses IPv6 and uses DHCP Unique Identifiers (DUIDs) instead of MAC Addresses.
Terminology Changes
- DISCOVER -> Solicit
- OFFER -> Advertise
- ACK -> Reply

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

Application Layer: Telnet

A

Remote access of CLI.
Unencrypted, replaced by SSH

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

Application Layer: SMTP

A

Simple Mail Transfer Protocol.
Sends email, no authentication, vulnerable to email spoofing (extensions resolve this)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

Application Layer: IMAP

A

Internet Message Access Protocol.
Used to manage and retrieve emails from a server. Uses TCP

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

Application Layer: HTTP

A

Client to Web Server.
GET
HEAD (Retrieve resource headers without retrieving all data)
POST (Process Data)
PUT (Modify or create data)
DELETE

1XX: Information
2XX: Success
3XX: Redirection
- 301: Moved Permanently
4XX: Client Error
- 403: Forbidden
- 404: Not Found
5XX: Server Error
- 500: Internal Error

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

Application Layer: HTTP/2

A

Adopted Multiplexing, one TCP connection, many requests

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

Application Layer: HTTP/3

A

Adopts Quick UDP Internet Connection (QUIC) protocol.
Built on UDP - adds reliability and encryption

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

Application Layer: RTSP

A

Real-time Streaming Protocol

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

Application Layer: SMB

A

Server Message Block.
Windows file-sharing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

Application Layer: NFS

A

Network File System.
Unix file sharing. used between servers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
50
Q

Application Layer: MQTT

A

Message Queuing Telemetry Transport
Communication between IoT devices. TCP or UDP
Pub/Sub Model with Hierarchical Topics
+ wildcard selects all at a level
# wildcard selects all after a specific level

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
51
Q

Application Layer: CoAP

A

Constrained Application Protocol
Communication between constrained devices (low power systems)
Uses small messages
UDP with retransmission and ACK
RESTful architecture like HTTP
Features
- Observation: Clients get updates on resource change
- Proxy Servers: Cache values
- Multicast Support
- Data Chunking
- Resource Discovery using CoRE

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
52
Q

Application Layer: DNS

A

Domain Name System
Converts URL to IP
Uses UDP
ICANN Delegates domain names
Target for cyber attacks
DNS Resolvers query root DNS server if it cannot find the URL

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q

Network Security: Firewalls

A

A barrier to malicious traffic between internal and external network

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
54
Q

Network Security: Stateless Firewalls

A

Examine packets against a set of rules in an attempt to identify malicious intent

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
55
Q

Network Security: Stateful Firewalls

A

Track connections to identify malicious pakcets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
56
Q

Network Security: Application-Layer Firewalls

A

Analyse packet contents to ensure the purpose is legitimate e.g. port 80 only receives HTTP

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
57
Q

Network Security: NID

A

Network Intrusion Detection.
Monitoring of network traffic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
58
Q

Network Security: NIDS

A

Network Intrusion Detection Systems (NIDS)
Use signature-based detection and anomaly detection to identify potential threats (and in some cases take action)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
59
Q

Network Security: NAC

A

Network Access Control (NAC)
Determines what devices are granted network access (e.g. use MAC Address filtering (poor choice)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
60
Q

Network Security: NAC: 802.1x

A

NAC Solution using Extensible Authentication Protocol (EAP) requiring login credentials to access a network

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
61
Q

Network Security: IPSec

A

Protocol and standards used by IP to provide authentication, integrity, confidentiality of IP packets. e.g. via encryption

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
62
Q

Network Security: VPN: Site-to-Site

A

Securely connects two netwroks

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
63
Q

Network Security: VPN: Remote-Access

A

Allows client to connect to a server and act resources as if they were physically there

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
64
Q

Network Security: WEP

A

Wired Equivalent Privacy.
Outdated, insecure protocol designed to provide confidentiality over wireless connections similar to that of wired networks

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
65
Q

Network Security: WPA

A

Wi-Fi protected access.
Upgrade to WEP
WPA Personal for small networks uses a constant Pre-shared key (PSK) that is vulnerable to dictionary attacks. Compromised devices are also an issue and there is no user-level authentication
WPA Enterprise for larger orgs, uses 802.1x

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
66
Q

Network Security: Key Reinstallation Attack (KRACK)

A

Vulnerability in WPA and WPA2 that allows an attacker to work out the key used for secure connections

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
67
Q

Network Security: WPS

A

Wifi Protected Setup
Makes it easier to connect to a WPA protected network using an easily trackable 8 digit pin or by pushing a physical button on the access point

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
68
Q

Network Security: DNS

A

Vulernable as not encyrpted.
Where you are going can be seen, not what you are doing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
69
Q

Network Security: DNS Amplification

A

DDoS Attack using a spoofed IP and a misconfigured DNS server that response to a large request. overloading the victim
Mitigate by ignoring large requests

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
70
Q

Network Security: DNS Man-in-the-Middle

A

DNS is vulnerable to man in the middle attacks

71
Q

Network Security: DNS Cache Poisoning

A

Causes DNS Resolver to return the wrong IP aaddress

72
Q

Network Security: DNS Hijacking

A

Hackers take over a DNS server

73
Q

Network Security: DNSSEC

A

DNS Security Extensions providing authentication and integrity allowing response to be verified.
Slow Deployment like IPv6

74
Q

Network Security: DDoS

A

Overwhlem a server’s bandwidth, CPU cucles, server state, etc.
Typically used as a distraction

75
Q

Network Security: DDoS: TCP SYN Flood

A

Send multiple TCP SYN packets causing the server to be left waiting

76
Q

Network Security: DDoS: LOIC

A

Low Orbit Ion Cannon. Voluntary botnet used to perform UDP/TCP attacks

77
Q

Network Security: DDoS: HOIC

A

High Orbit Ion Cannon. Uses HTTP flood attack (lots of POST requests)

78
Q

Network Security: DDoS: Slowloris

A

Opens mulitiple HTTP GET requests but never sends the final packet to complete the request header

79
Q

Network Security: DDoS: IPv6 RA Flood

A

Exploits NDP and sends lots of RA multicast to consume CPU resources

80
Q

Network Security: DDoS: Mitigation

A

Use Content Delivery Network (CDN) to distribute servers. Causes DDOS attacks to be spread across multiple servers

Also ensure systems are patched

81
Q

Distributed System: Definition

A

A system where data and computation is distributed over networked machines that communicate and coordinate their actions through messages

82
Q

Distributed System: Trends

A

Volume, Variety, Velocity

IOT devices producing lots of data sent to more powerful devices

83
Q

Distributed System: Trends: Edge Computing

A

Enables processing to occur closer to source of data, reducing latency and increasing efficiency

84
Q

Distributed System: Trends: Fog Computing

A

Addresses limitation of Edge Computing by adding an intermediate layer of resources between the edge and the cloud

85
Q

Distributed System: Challenges

A

Heterogeneity: Variety of hardware
Openness: capacity for a system to be extended
Scalability: Ability to remain effective with increase in demand
Failure Handling
Concurrency: Serialise resource access and limit throughput or allow concurrent access and maximise throughput

86
Q

Distributed System: Physical Models

A

Cover physical infrastructur and hardware

87
Q

Distributed System: Architectural Models

A

Describes components, relationships and interactions of a system.
Validated against performance, adaptability, security and availabilitu

88
Q

Distributed System: Architectural Models: Communicating Entities

A

Elements that communicate with each other. Two perspectives
- System-oriented perspective. Entities are processes, threads, and nodes. Not suitable for programming
- Problem-Object perspective. Entities are objects, components (objects that specify required dependencies) and web services

89
Q

Distributed System: Architectural Models: Communication Paradigms: IPC

A

Inter-process Communication. Message-passing primatives and socket programming

90
Q

Distributed System: Architectural Models: Communication Paradigms: Remote Invocation

A

Two-way exchange. e.g. Request reply protocols (e.g. HTTP)

91
Q

Distributed System: Architectural Models: Communication Paradigms: Remote Invocation: RPC

A

Remote Procedure Call.
Request remote function execution and receive a response.
No pass by reference

92
Q

Distributed System: Architectural Models: Communication Paradigms: Remote Invocation: RMI

A

Problem-oriented perspective, invoke methods of remote entities

93
Q

Distributed System: Architectural Models: Communication Paradigms: Indirect Communication

A

Sends don’t know who they’re sending to and do not need to exist at the same time .

E.g. Group Communication
Recipients join groups to receive messages
E.g. Pub/sub model, publishers send messages to topics and subscribers receive

94
Q

Distributed System: Architectural Models: Entity Roles & Responsibilities

A

Processes interact with each other to perform a function, in doing so they take on roles

Client-Server Model
Peer-to-Peer Model. Decentralisation increases scalability, distributed workload but increases complexity

95
Q

Distributed System: Architectural Models: Entity Placement

A

Refers to how to map entities (objects, processes, etc.) onto underlying physical infrastructure. It determines performance, reliability and security

Services mapped to servers.

96
Q

Distributed System: Architectural Patterns: Layering

A

Logical decomposition of the system into layers

97
Q

Distributed System: Architectural Patterns: Tiers

A

Organising Layers onto appropriate servers

98
Q

Distributed System: Architectural Patterns: One-Tier

A
  • Performance: No network communication overhead
  • Scalability: Replicating layers leads to overhead
  • Fault Tolerance: Server crash means service is unavailable
99
Q

Distributed System: Architectural Patterns: Two-Tier

A
  • Performance: Interaction between UI and AL are affected by network
  • Scalability: Limited by server’s resources but can be scaled
  • Fault Tolerance: Server crash means service is unavailable
100
Q

Distributed System: Architectural Patterns: Two-Tier with Server Replication

A
  • Performance: Interaction between UI and AL are affected by network
  • Scalability: Can add more servers
  • Fault Tolerance: Can tolerate N-1 server crashes
101
Q

Distributed System: Architectural Patterns: Three-Tier

A
  • Performance: Interactions between UI and AL or AL and DM (Data Management) are affected by network
  • Scalability: Can scale application logic and data management independently
  • Fault Tolerance: Finer grain fault tolerance
102
Q

Distributed System: Architectural Patterns: Object Replication

A
  • Performance: Overhead to keep data consistent
  • Scalability: Limited by the mechanism to preserve consistency (limited by server’s storage)
  • Fault Tolerance: Can tolerate N-1 crashes
103
Q

Distributed System: Architectural Patterns: Object Partitioning

A
  • Performance: No overhead for consistency. Overhead to find right partition
  • Scalability: Can partition over more servers but the request load for most frequently accessed data affects it
  • Fault Tolerance: Server crash means all data objects stored in that server are unavailable
104
Q

Distributed Systems: Fundamental Model

A

Fundamental models explicitly state assumptions about the system to capture properties including performance, reliability and security

105
Q

Distributed Systems: Fundamental Model: Interaction Model

A

Describes interactions in a system

106
Q

Distributed Systems: Fundamental Model: Interaction Model: Factors affecting communication

A

Latency (transmission time, network card delay, os delay)
Bandwidth
Jitter (variation in time to deliver a series of messages)

107
Q

Distributed Systems: Fundamental Model: Interaction Model: Synchronous Models

A

Has known lower and upper bounds for each step.
Messages received in bounded time
Clock drift rate is known

108
Q

Distributed Systems: Fundamental Model: Interaction Model: Asynchronous Models

A

Proccess execution time unknown
Message times not known
Clock drift rate unknown

109
Q

Distributed Systems: Fundamental Model: Interaction Model: Failure Model: Process Omission Failure

A

e.g. Crash
In Synchronous, detected with timeouts. Known as a fail-stop if can be detected with certainty
In Asynchronous, cannot be detected

110
Q

Distributed Systems: Fundamental Model: Interaction Model: Failure Model: Communication Omission Failure

A

e.g. Message Drop
Arbritrary Failure e.g. communication channel corrupts message, message delivered more than once
Timing failure (in synchronous, e.g. exceeds time allowance etc)

111
Q

Distributed Systems: Fundamental Model: Interaction Model: Failure Model: Handling Failures

A

Failure Masking: Hiding failure e.g. resend message, restart process
Failure Conversion: convert to acceptable failure. e.g. checksum: arbitrary corruption to handlable failure

112
Q

Distributed Systems: Fundamental Model: Interaction Model: Reliable Communication

A

Requires validity (messages eventually delivered)
Integrity (delivered msg same as sent)

Ensured through timeout-based retransmission.
Checksums. disregarding duplicate msgs

113
Q

Distributed Systems: Fundamental Model: Interaction Model: Security Model

A

Describe how security is achieved
Threats include, process threats, communication threats, dos
Prevented through encryption, authentication, secure channels

114
Q

Distributed Systems: Measuring Time

A

Measured using quartz clocks or atomic clocks

115
Q

Distributed Systems: Timing: Local Network Clock Synchronisation

A

Used to sync a machines clock with an accurate one

116
Q

Distributed Systems: Timing: Local Network Clock Synchronisation: Cristian’s Algorithm

A
  • Cristian’s Algorithm has the user request a server for a time. It then calculates it as Tserver + (T1 – T0)/2 where T1 is time response is received by client and T0 time when request is sent. Division by 2 is an approximation that the time delay between the client and server is symmetrical
117
Q

Distributed Systems: Timing: Local Network Clock Synchronisation: Berkeley Algorithm

A

assumes no clock server and a co-ordinator fetches the time of each node, it calculates the average time difference and broadcasts the new time. To improve the algorithm, ignore outliers, use a secondary-coordinator in case the primary goes down and instead, broadcast the time difference for each node (reducing impact of latency)

118
Q

Distributed Systems: Timing: Internet Network Clock Synchronisation: NTP

A
  • Network Time Protocol (NTP) uses a hierarchy of time servers (Stratum model)
  • Stratum level 0-15 indicates the device’s distance to the reference clock. stratum 0 is atomic clocks
  • Algorithm uses a UDP packet with 4 slots for 4 timestamps, client send, server receive, server send, client receive. Network delay calculated as delta = (T3 – T0) – (T2 – T1). Assume request and response delay are equal so time at server when client receives is T2 + delta/2. Clock skew is time different between client and server. Theta = T2 + delta/2 – T3
  • Estimating clock skew several times determines how the client should adjust their clock. <125ms: Slewing (slowly adjust). 125ms-1000s: stepping (reset clock). >1000s: manual reset
119
Q

Distributed Systems: Timing: Logical Clocks

A

Count the number of events
No relation to time

120
Q

Distributed Systems: Timing: Logical Clocks: Happens-before Relation

A

Event a happens before event b if
- they occur at the same node and a occurs before b
- OR event a sends a message and event b is the recipient of that message
- OR there exists an event c such that a-> c, c -> b

If Neither a -> b or b-> a then a || b (concurrent)

121
Q

Distributed Systems: Timing: Logical Clocks: Lamport Clock

A

Each node maintains a counter that increments on each local event

Sent messages include time t. Recipient uses largest of the received time and their time

FLAWED: If L(a) < L(b) where L(e) is the value of t at e, we cannot tell which happened before or whether they’re concurrent

122
Q

Distributed Systems: Timing: Logical Clocks: Vector Clocks

A

Each node tracks a vector of observed events
On Receiving a message, find the max of each vector value

  • Relational operators can be defined on the vector timestamps. Two vector timestamps are equal if all values are the same, one vector timestamp is less than another if all values are less than. Two vector timestamps are concurrent if neither one is less than the other
  • V(a) < V(b) iff a -> b
  • V(a) = V(b) iff a =b
  • V(a) || V(b) iff a | b
123
Q

Distributed Systems: Mutual Exclusion

A

Ensuring only one process accesses a critical section at any time

124
Q

Distributed Systems: Mutual Exclusion: Algorithm Requirements

A

No Deadlocks
No Starvation (indefinite waiting process)
Fairness (every site gets a chance to access the critical section)
Fault Tolerances (Failures are recognizable)

125
Q

Distributed Systems: Mutual Exclusion: Algorithm Properties

A

Safety: Mutual exclusion guaranteed and freedom from deadlock
Liveness: Every process eventually accesses the critical section
Fairness: Access is in a fair-order, first-come-first-serve
Performance: Measured in number of messages, client delay, synchronisation delay

126
Q

Distributed Systems: Mutual Exclusion: Token-based Algorithm: Centralised Algorithm

A

Server stores queue of requests to obtain token and grants token when process finishes with critical section.

Satisfies safety, liveness, and fairness
Performance: Single point of failure, risk of bottleneck. Server must be elected or known

127
Q

Distributed Systems: Mutual Exclusion: Token-based Algorithm: Ring Algorithm

A

Suitable for ring topologies
Token passed to neighbouring process

Satisfies safety, and liveness
Does not satisfy fairness. Ordering is based on ring order
Performance: Token circulation consumes bandwidth

128
Q

Distributed Systems: Mutual Exclusion: Token-based Algorithm: Raymond’s Tree Based ALgorithm

A

Nodes have one parent to which they send requests for the token to.
Each node maintains a FIFO queue

Satisfies Safety, Liveness (if not using a greedy strategy) and Fairness
Performance: O(log n)

129
Q

Distributed Systems: Mutual Exclusion: Non-token-based Algorithm: Ricart-Agrawala

A

Sites broadcast request to access critical section. Those not in request queue or critical section respond immediately, otherwise add to queue
When leaving critical section, respond to broadcast requests as way of letting the process know they can enter the critical section

Requests contain site ids and timestamp

Satisfies Safety Liveness and Fairness
Good Performance

130
Q

Distributed Systems: Mutual Exclusion: Quorum Based Algorithm: Maekawa’s Algorithm

A

Quorums are subsets of nodes that must agree on an operation.

Any two quorums must have a common site to ensure mutual exclusion

  • Processes request access and only gain access when all processes in the quorum reply. Processes don’t reply when they know another process is accessing the critical section.
  • Processes notify all other processes in the quorum when they have released the critical section

Satisfies safety
Does not satisfy liveness (easy to deadlock with two requests t the same time. Resolved by using happens-before ordering)
Does not satisfy fairness (Resolved with vector clocks)
PErformance better than ricart-agrawala if N>4

131
Q

Distributed Systems: Leader Elections: Definition & Advantages

A

Used to give one node special powers:
Systems are easier to manage and design
Can be more efficient than consensus
Can improve performance and costs
Easier to write software

132
Q

Distributed Systems: Leader Elections: Properties

A

Safety: One process becomes the leader and all other processes know this
Liveness: All processes participate and eventually are either elected or identify a leader
Performance: Minimise number of messages

133
Q

Distributed Systems: Leader Elections: Ring Leader Election

A
  • Each process has a unique identifier I(n) that acts as a priority. Higher value means more suitable for leader
  • Satisfies safety and liveness
134
Q

Distributed Systems: Leader Elections: Bully Election

A
  • A failed process is detected and an ‘Election’ message is sent to processes with a higher unique identifier to announce an election
  • Higher ID processes respond with ‘Answer’, then they send out ‘Election’ to processes with a higher Id than them. This repeats until a process gets no ‘Answer’s meaning they are the highest priority. They then send out coordinator messages
  • Satisfies liveness, can violate safety if a failed process leads to two coordinators
  • Performance is best case n-2 messages, worst case O(n^2) messages
  • Unreliable process failure detection can cause two coordinators.
  • Multiple elections are handled as highest id is still selected
135
Q

Distributed Systems: Multicast

A
  • Multicast is an asynchronous group communication protocol.
  • Multicast middleware sits between application and network. Data is send and received by middleware. Data is multicasted and delivered to and from application
136
Q

Distributed Systems: Multicast Models: Basic Multicast

A
  • Messages will be eventually be delivered to the group (closed or open (sender can be outside the group))
  • B-multicast(g, m) sends m to all processes p in m with send(p, m). Middleware receives with receive(m) and delivers to application with B-deliver(m)
  • Poor failure tolerance, if crash during multicast then not all will receive
137
Q

Distributed Systems: Multicast Models: Reliable Multicast

A
  • Improves basic multicast, guarantees integrity (delivers messages at most once), agreement (all or nothing delivery), validity (if multicast, a message will eventually be delivered)
  • When message received for first time, the node multicasts the message and then once that’s done delivers the message. So if the sender crashes then no multicast occurs or at least one other process receives the message and calls multicast.
  • O(N^2) messages. Inefficient
  • Gossip protocol stop forwarding to all in the group and selects only a few
138
Q

Distributed Systems: Multicast Models: FIFO Ordered Multicast

A
  • Built on reliable multicast and ensures two messages multicast from the same process maintain their delivery order
  • Uses buffer queue to store messages until guarantees are met
139
Q

Distributed Systems: Multicast Models: Causal Ordering Multicast

A
  • Built on FIFO Ordered Multicast and ensures that if a multicast happens-before another multicast then it will be delivered before the other
140
Q

Distributed Systems: Multicast Models: Total Ordered Multicast

A
  • Built on reliable multicast and ensures if a multicast happens before another multicast, then it must be delivered before the other for all processes
  • One process acts as a sequencer, responsible for ordering messages. Processes add messages to a buffer until the sequencer tells them to process it
  • Poor Fault Tolerance, if leader crashes no messages received
141
Q

Distributed Systems: Multicast Models: FIFO-Total ORdered Multicast

A
  • Combination of FIFO ordered multicast and total ordered multicast
  • Meets requirements for casual multicast
142
Q

Distributed Systems: Consensus

A
  • Used to achieve agreement on a single data value among distributed processes
143
Q

Distributed Systems: Consensus: Two Generals Problem

A
  • Two generals problem has no solutions, it focuses on the issue of network communication and that you can never guarantee reliable communication in a distributed systems
144
Q

Distributed Systems: Consensus: Byzantine Generals Problem

A
  • The byzantine generals problem focuses on node behaviour and says that you need 3f + 1 total generals to tolerate f malicious generals i.e. 1/3 may be malicious
145
Q

Distributed Systems: Consensus: Algorithm Requirements

A
  • Algorithms must satisfy:
    Termination (eventually every non faulty process sets its value)
    Agreement (All-non faulty processes decide on the same value
    Integrity (If majority propose a value, then non-faulty processes select that value)
146
Q

Distributed Systems: Consensus: Relation to Total Ordered Multicast

A
  • Without failures, total-order multicast can be used to solve consensus. All processes TO-multicast proposed values, sequencer multicast.
    An algorithm that solves consensus can also be used to implement TO-multicast without a leader (sequencer) – use successive rounds of consensus to decide on next message
147
Q

Distributed Systems: Consensus: Synchronous System Consensus

A
  • Timeouts to detect when a process has crashed
  • With F crashed processes, at least F + 2 processes are needed total to make a consensus (at least 2 processes needed to form a consensus)
  • Need F + 1 rounds as a failure during a round may mean some processes have not correctly received values. Another round is necessary to ensure any missing values are updated
  • Each process stores only the new values multicast to it each round before choosing a value in the final round
  • With F arbitrary failures, more than 3F processes are needed with F + 1 failures. AKA if more than a third of processes fail with arbitrary failures then you cannot reach a consensus (byzantine generals problem)
148
Q

Distributed Systems: Consensus: ASynchornous System Consensus

A
  • Cannot use timeouts to detect missing messages so cannot detect crash processes
  • Can only achieve consensus with a probability to a certain level
149
Q

Distributed Systems: Data Replication: Primary-Backup Replication

A
  • One server acts as a primary, the others act as a backup
  • Clients interact with the primary who executes and stores the response (if it hasn’t been done before), changes in data are replicated by the backups using ordered multicast (so all are synchronised), primary awaits ACKs
  • Can tolerate N-1 server failures. If backup fails, it is replaced and its state is collected from other backups (not the primary to avoid overload). If primary fails, a new primary is elected via leader election, new primary registers itself with name service so clients no who to consult. Clients resend requests after timeout
150
Q

Distributed Systems: Data Replication: CAP Theorem

A
  • CAP Theorem states it is impossible to achieve the following three properties at once, at most two can be obtained:
    Consistency (Replicas have the same state for data objects)
    Availability (All requests are served as long as at least one server is available)
    Partition Tolerance (Data stores continue to work even with a network partition)
  • Proved by contradiction, a network partition occurs and a client updates on server, another client reads from another server. Values are inconsistent
151
Q

Distributed Systems: Data Replication: CAP Theorem: AP Systems

A
  • Availability & Partition Tolerance ensured and Consistency is lost
  • Can ensure partial consistency on partially synchronous networks as messages will be eventually delivered. During synchronous periods the servers reconcile data, during asynchronous periods, read operations return inconsistent values
152
Q

Distributed Systems: Data Replication: CAP Theorem: CP Systems

A
  • Consistency & Partition Tolerance ensured and availability is lost. Refuse requests when a network partition occurs (may accept read requests)
  • Suitable when consistent data is essential
153
Q

Distributed Systems: Data Replication: CAP Theorem: CA Systems

A
  • Not really a distributed system as Partition Tolerance is not impossible on all distributed systems (even for those on a single site)
154
Q

Distributed Systems: Data Replication: Scalability

A
  • Scalability is the ability to adapt something to meet greater needs in the future
  • Scalability Parameters: External fluctuating values e.g. number of client, workload
  • Scalability Metrics: Measurements of system properties e.g. latency, throughput, availability
  • Scalability Criteria: Expected metrics, e.g. system available 99.99% of the time
  • Adding more servers only improves metrics to a certain point. Overhead of adding servers include downtime for reconfiguration (e.g. rebalancing) and increased messages for server communication. Bottlenecks as scale parameters increase for deciding on what server to use etc.
155
Q

Distributed Systems: Data Replication: Scalability: Primary-Backup Model Scalability

A
  • The primary-backup model has poor scalability, the primary server handles all requests and the backups have to send ACKs with every change. TO resolve, add more primary servers and partition the data, and make the primary only wait for the majority of ACKs, not all. The overhead of this is adding new servers means more time spent partitioning and migrating, also dependency on data objects increases the coordination required among primary servers. And not all backups may be synchronised with the primary, so needs to be taken into account when running leader election
156
Q

Distributed Systems: Consitency Models: Strong Consistency

A

Models use CP systems and requires a global ordering of updates that all replicas agree on

157
Q

Distributed Systems: Consitency Models: Weak COnsitency

A

Models use AP system and uses eventual consistency

158
Q

Distributed Systems: Consitency Models: Passive Replocation

A

The Primary-Backup MOdel

159
Q

Distributed Systems: Consistency Models: Active Replication

A

clients communicate with a group of replicas and updates are propagated amongst replicas using total-order multicast

160
Q

Distributed Systems: Consistency Models: Strict Consistency

A

where a write to any variable is immediately available to all other replicas. The DS acts as a single store, this is impossible as instantaneous message exchange isn’t possible

161
Q

Distributed Systems: Consistency Models: Linearizability

A

a weaker version of strict consistency stating that if one operation completes before another, then it precedes the other. Implemented with a perfectly synchronised clock and bounded message delays (synchronous system) with total order multicast

162
Q

Distributed Systems: Consistency Models: Sequential Consistency

A

weaker than linearizability that does not mention timing but states that if a write precedes another write then no process reading the variable will read the latter write before the former. Implemented by forcing replicas to return local copies and write operations trigger TO-multicast that awaits acknowledgements. No synchronised clocks needed

163
Q

Distributed Systems: Consistency Models: Causal Consitency

A

any writes with a causal relationship must be seen in the same order and the order of values returned by read operations must be consistent with the causal order. Implemented with Vector Timestamps and write operations are multicasted

164
Q

Distributed Systems: Consistency Models: Eventual Consitency.
How to resolve conflicts

A
  • Eventual Consistency states that after an unspecified amount of time following a write, if there are no more writes, then all replicas will be in the same state. No guarantee of how long it will take. Implemented by propagating changes in the background. Conflicts resolved with a consensus algorithm, a rollback, or delegation to the application. Allows for fast reads and writes even when network partition occurs, very weak notion of consistency and requires mechanism to deal with conflict
165
Q

Distributed Systems: Consistency Models: Strong Eventual Consistency

CRDT

A
  • Strong Eventual Consistency guarantees that any two replicas that have received the same set of updates in any order will be in the same state. Concurrent updates applied with Conflict-Free Replicated Data Types (CRDT)
  • Operation-based CRDT: On write, broadcast operation. On broadcast receive, apply operation. Used in collaborative editors e.g. Overleaf, Google Docs
  • State-based CRDT: On write, broadcast state. On broadcast receive, merge states. Used for grow-only counters
166
Q

Distributed Systems: Consistency Models: Quorum-based Protocol

A
  • Quorum-based Protocols, read quorum and write quorum, the two quorums intersect to ensure consistency. R + W > N. On a write, the write quorum replicates others in the background. On a read, replicas return stored value and vector timestamp so that more recently updated replicas have their values take precedence. If replicas fail, the quorum can read and write as long as the remaining vectors form a majority
167
Q

Distributed Systems: Remote Invocation

A
  • Remote Invocation utilises Request-Reply protocols. There are three styles
    Request (R) Protocol – No reply expected
    Request-Reply (RR) Protocol
    Request-Reply-Acknowledgement (RRA) Protocol
  • They are implemented with UDP to reduce overhead
  • Protocol can fail if there is a process crash, channel omission failure or messages out of order. To resolve, use timeouts and ids for messages to discard duplicates
168
Q

Distributed Systems: Remote Invocation: Remote Procedure Call (RPC)

A
  • Call a subroutine remotely as if it were local (Transparency)
  • There should be no syntax difference between local and remote
  • RPC is more vulnerable to failures
  • Latency is significantly larger
  • RPC cannot support call by reference
  • RPC Call Semantics is how the RPC system handles delivery, execution and responses:
  • Maybe: No fault tolerance. System can’t guarantee request will be executed
  • At-Least-Once: Request executed at least once and client receives a response
  • At-Most-Once: Requests executed at most once and duplicates are discarded
  • Local Procedure calls are Exactly-Once
    RPC Interfaces specify procedures offered by a server. They are described in an Interface Definition Language (IDL), enabling communication regardless of programming language
169
Q

Distributed Systems: Remote Invocation: Remote Method Invocation

A
  • OOP equivalent of RPC, call remote object methods as if local
  • Like RPC, uses interfaces, request-reply protocols and has transparency. Additionally allows objects to be used as parameters in method calls
  • Remote Object References identify remote objects and can be passed as arguments or returned as results
  • RMI can cause local invocations on the remote machines, instantiate new objects (new IDL must be created)
  • Clients using garbage collection use distributed garbage collection modules to ensure remote object’s lifecycles are handled properly. Uses reference counting, increment when a reference is created and sent to a different process. Decrement when reference count is no longer needed. If 0, garbage collector reclaims memory
  • Exceptions raised by RMI are exposed to the caller, they can be caused due to remote nature of the object, such as the remote process crashing or communication omission
170
Q

Distributed Systems: Peer-to-Peer

A
  • Client-Server architectures have bottlenecks of computational power, memory, disk space, network bandwidth. Upgrading infrastructure with more servers and bandwidth takes time and has high maintenance and management costs
  • Peer-to-Peer is an alternative with two types
  • Servers become peers, clients communicate with service provider consisting of peers
  • Both clients and servers become peers
     Peer spread over internet. Peers can leave or fail. Computational power and resources fluctuates. Poses challenges of
    How to distribute data and consumption
    How to access distributed data and computation
    How to cope with failures
    How to cope with high churn (rate at which nodes enter and leave the network)
171
Q

Distributed Systems: Peer-to-Peer: Napster

A
  • Napster uses a server to store locations of files. User requests file location, server responds with locations, user requests from peer, file is delivered, the user then updates the server to say it now has the file
  • Taught us that large-scale P2P systems are feasible although it was not a pure P2P system with a centralised server index. It was limited by server-based indexing with lots of requests and index updates. Ensuring consistency is simple as it was used for mp3 files which are never updated
172
Q

Distributed Systems: Peer-to-Peer: BitTorrent

A
  • Sharing a file to BitTorrent requires creating a torrent, this is done by using a .torrent file that references the file(s) they want to distribute.
  • A tracker keeps track of peers participating in a torrent. The URL to the tracker is stored on .torrent server where .torrent files are stored. The .torrent file directs the user to the tracker.
  • Peers are either Seeders or Leechers. A seeder has the entire file downloaded. A leecher is in the process of downloading a file. New peers contact the tracker who responds with a list of peers who they can connect to exchange data
  • The .torrent server also stores file name and size and chunk chesums (files are divided into chunks, the server stores checksums of these ensure integrity)
  • BitTorrent operates on peer cooperation principles, peers must be willing to upload chunks of a file they have download to other peers who are downloading.
  • Uses a tit-for-tat incentive mechanism
  • Peers that don’t upload enough are choked.
  • Choking/unchoking decisions is based on the upload rate of the peer.
  • New peers are penalised because they don’t have any chunks to upload. Optimistic unchoking unchokes a random peer every 30 seconds
  • Trackers and .torrent server are centralised
  • Evolved towards a Distributed Hash Table (DHT) based tracker-less schema to achieve full decentralisation. Uses a ring network.
173
Q

Distributed Systems: Distributed Transactions:

A
  • A transaction is a set of sequential operations guaranteed by a server to be atomic in the presence of multiple clients and server crashes. Operation is free from interference, either all steps of the transaction complete or none. Needs to tolerance crash failures or omission communication failures.
  • ACID Properties (Atomicity, Consistency, Isolation, Durability)
  • In the event of a server crash, a completed transaction must be durable. A new server to replace the old one can recover the server’s objects. Uncommitted transactions are aborted and recovery procedures restore objects to last committed values

University (9 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions