Main Flashcards
How does a client-server model look?
What type of network is a network of scale: Vicinity?
(PAN) Personal Area Network
Connect devices over the range of a person:
Example of a Bluetooth PAN:
(The word Vicinity means: “the area near or surrounding a particular place”)
What type of network is a network of scale: Building?
(LAN) Local Area Network
Connect devices in a home or office building
Called enterprise network in a company
What type of network is a network of scale: City?
(MAN) Metropolitan Area Networks
Connect devices over a metropolitan area
Example of a MAN based on cable TV:
What type of network is a network of scale: Country?
(WAN) Wide Area Network
Three different kinds:
- Connect devices over a country
- Example of a WAN conneting three branch offices:
- An Internet Service Provider (ISP) network.
- Customers buy connectivity from the ISP to use it.
- A Virtual Private Network (VPN) is built from virtual links that run on top of the Internet.
What type of network is a network of scale: Planet?
The Internet (the network of all networks)
What are protocol layers?
Protocol layering is the main structuring method used to divide up network functionality.
- Each protocol instance talks virtually to its peer
- Each layer communicates only by using the one below
- Lower layer services are accessed by an interface
- At bottom, messages are carried by the medium (means: data are then sent over physical cables)
How does headers work with protocol layers?
Each lower layer adds its own header (with control information) to the message to transmit and removes it on recieve.
What is a Connection-Oriented service?
Must be set up for ongoing use (and torn down after use), e.g. a phone call
What is a Connectionless service?
Messages are handled separately, e.g. postal delivery
What are the different Reference Models?
- OSI reference model
- TCP/IP reference model
- Model used for this course
Name the layers of the OSI reference model
A principled, international standard, seven layer model to connect different systems
- Application
- Presentation
- Session
- Transport
- Network
- Data link
- Physical
Explain the TCP/IP reference model:
A four layer model; omits some OSI layers and uses the IP as the network layer.
Explain the reference model used in this course:
It is based on the TCP/IP model but we call out the physical layer and look beyond Internet protocols.
What is a distributed system?
Definition:
A distributed system is the one in which hardware and software components at networked computers communicate and coordinate their activity only by passing messages.
What are service layers?
It is a conceptual layer within a network service provider architecture.
What is Middleware?
It is computer software that provides services to software applications beyond those available from the operating system. It can be described as “software glue”.
Middleware makes it easier for software developers to perform communication and input/output, so they can focus on the specific purpose of their application.
- Masks heterogenity
- Provides a convenient programming model
- Objects / processes
- Communication primitives
- Synchronization
- Group and multicasting
- Naming and Localization services
- Event notification
What is an Asynchronous interaction model?
The most significant aspect of asynchronous communications is that data is not transmitted at regular intervals, thus making possible variable bit rate, and that the transmitter and receiver clock generators do not have to be exactly synchronized all the time.
- No known bounds for:
- The execution speed of a process
- Message delay on the network
- Clock drift
What is a (partly) Synchronous interaction model
- Known upper and lower bound for each process step
- Known upper bound for the time it takes for a message to be recieved
- Known upper bound for clock drift
What does Heterogeneity mean?
A heterogeneous network is a network connecting computers and other devices with different operating systems and/or protocols.
For example, local area networks (LANs) that connect Microsoft Windows and Linux based personal computers with Apple Macintosh computers are heterogeneous.
What are Timing failures?
- Class of Failure: Clock
- Affects: Processes
- Process’s local clock exceeds the bounds on its rate of drift from real time
- Class of Failure: Performance
- Affects: Processes
- Process exceeds the bounds on the interval between two steps
- Class of Failure: Performance
- Affects: Channel
- A message’s transmission takes longer than the stated bound
What is the MAC Sublayer?
- Responsible for deciding who sends next on a multi-access link
- An important part of the link layer, especially for LANs
Explain Static channel allocation
- You divide up the bandwidth using FTM, TDM, CDMA, etc.
- Like radio (different channels)
- Static allocation performs poorly for busy traffic
- Allocation to a user will also sometimes go unused
Explain dynamic allocation
Dynamic allocation gives the channel to a user when they need it. Potentially N times as efficient for N users.
Explain Pure ALOHA
- Users transmit frames when they have data to send
- If, while you are transmitting data, you receive any data from another station, there has been a message collision. All transmitting stations will need to try resending “later”.
- Collisions happen during what is called a “vulnerable period” that is twice the frame time
“Efficient and low-delay under low load”
Explain Slotted ALOHA
- Divide time into frame-size slots
- Transmission can only start at the beginning of a slot
- Twice as effective as pure ALOHA
- But we need a way to sync users to the beginning of the slot
Explain Carrier Sence, Multiple Access (CSMA)
Carrier Sence, Multiple Access improves ALOHA by sensing the channel to see if it is idle before transmitting.
- Users doesn’t send if they sense someone else
Variations on what to do if the channel is busy:
- 1-persistent(greedy)
- Send as soon as idle
- Nonpersistent
- Wait a random time then try again
- p-persistent
- Send with probability p when idle
“CSMA outperforms ALOHA, and being less persistent is better under high load.”
Explain Carrier Sence, Multiple Access Collision Detection (CSMA/CD)
CSMA/Collision Detection
It uses a carrier sensing scheme in which a transmitting data station detects other signals while transmitting a frame, and stops transmitting that frame, transmits a jam signal, and then waits for a random time interval before trying to resend the frame.
CSMA/CD is used to improve CSMA performance by terminating transmission as soon as a collision is detected, thus shortening the time required before a retry can be attempted.
Explain Collision-Free: Bitmap
- The basic bit-map protocol:
- Sender set a bit in contention slot if they have data
- Senders send in turn; everyone knows who has data
What is a Collision-Free protocol?
- Collision-free protocols avoid collisions entirely
- Senders must know when it is their turn to send
Explain Collision-Free - Token Ring
A token is sent round ring and defines the sending order
- Station with token may send a frame before passing
- Idea can be used without ring too, e.g., token bus
Explain Binary Countdown
Data is transmitted as binary. If several nodes on a network start transmitting simultaneously, all transmit their network ID as a binary number.
These numbers are compared starting with the first number in the sequence, representing the highest value in the byte.
All those containing a zero at this bit are knocked out, if there are still more than one node in contention, the next bit along is compared. Again, those with 1 stay in and those with 0 are out.
This process continues along the bits of the network ID until there is only one node left and that gets control of the media.
What are Limited-Contention Protocols?
Idea is to divide stations into groups within which only a very small number are likely to want to send
- Avoids wastage due to idle periods and collisions
Limited-Contention Protocol: Explain Adaptive Tree Walk
Initially all nodes are allowed to try to aquire the channel. If a node is able to aquire the channel, it sends its frame.
If collision then the nodes are divided into two equal groups and only one of these groups compete for slot 1.
If one of its members aquire the channel then the next slot is reserved for the other group.
On the other hand, if there is a collision again then that group is also subdivided and the same process is followed. This can be better understood if the nodes are thought of as being organised in a binary tree
- Depth first search under nodes with poll collisions
- Start search at lower levels if more than one station expected
What complications does Wireless have compared to Wired?
Wireless has complications compared to wired.
- Nodes may have different coverage regions
- Leads to hidden and exposed terminals
- Nodes can’t detect collisions, i.e., sense while sending
- Makes collisions expensive and to be avoided
What are Hidden terminals?
Hidden terminals are senders that cannot sense each other but nonetheless collide at intended receiver
- Want to prevent; loss of efficiency
- A and C are hidden terminals when sending to B
What are Exposed terminals?
Exposed terminals are senders who can sense each other but still transmit safely (to different receivers)
- Desirably concurrency; improves performance
- B -> A and C -> D are exposed terminals
Wireless LANs: What is Multiple Access with Collision Avoidance (MACA)?
- When a wireless network node wants to transmit, it sends a signal called Request-To-Send (RTS) with the length of the data frame to send.
- If the receiver allows the transmission, it replies the sender a signal called Clear-To-Send (CTS) with the length of the frame that is about to receive.
- Meanwhile, a node that hears RTS should remain silent to avoid conflict with CTS; a node that hears CTS should keep silent until the data transmission is complete.
Classic Ethernet: Explain the Physical Layer
One shared coaxial cable to which all hosts attached
- Up to 10 Mbps, with Manchester encoding
- Hosts ran the classic Ethernet protocol for access
Classic Ethernet: Explain MAC protocol
MAC protocol is 1-persistent CSMA/CD (earlier)
- Random delay (backoff) after collision is computed with BEB (Binary Exponential Backoff)
How is the Classic Ethernets performance?
- Efficient for large frames, even with many senders
- Degrades for small frames (and long LANs)
Explain Switched/Fast Ethernet
Fast Ethernet extended Ethernet from 10 to 100 Mbps
- Hubs wire all lines into a single CSMA/CD domain
- Switches isolate each port to a separate domain
- Much greater throughput for multiple ports
- No need for CSMA/CD with full-duplex lines
- Switches can be wired to computers, hubs and switches
- Hubs concentrate traffic from computers
What does Idempotent mean?
An idempotent operation can be repeated an arbitrary number of times and the result will be the same as if it had been done only once.
What does Non-Idempotent mean?
A Non-idempotent operation will have a different result depending on the amount of times the operation was done.
OSI-model: Explain the Physical layer
- Defines electrical and physical specifications of the data connection
- Defines transmission mode: Simplex, half duplex, full duplex
- Defines network topology: bus, mesh, ring, etc.
OSI-model: Explain the Data link layer
The data link layer provides node-to-node data transfer—a link between two directly connected nodes. It detects and possibly corrects errors that may occur in the physical layer.
It, among other things, defines the following protocols:
- Protocols for establish and terminate a connection between two physically connected devices.
- Protocol for flow control between the two physically connected devices.
It is divided into two sublayers:
- Media Access Control (MAC) layer - responsible for controlling how devices in a network gain access to medium and permission to transmit it.
- Logical Link Control (LLC) layer - responsible for identifying Network layer protocols and then encapsulating them and controls error checking and frame synchronization.
OSI-model: Explain the Network layer
- A key design issue is determining how packets are routed from source to destination.
- Handling congestion is also a responsibility of the network layer.
- The quality of service (delay, transit time, etc.) is also a network layer issue.
- It is up to the network layer to allow heterogeneous networks to be interconnected.
OSI-model: Explain the Transport layer
The basic function of the transport layer is to accept data from above it, split it up into smaller units if need be, pass these to the network layer, and ensure than the pieces all arrive correctly at the other end.
OSI-model: Explain the Session layer
The session layer allows users on different machines to establish sessions between them.
Sessions offer various services, including:
- Dialog Control (keeping track of whose turn it is to transmit)
- Token Management (preventing two parties from attempting the same critical operation simultaneously)
- Synchronization (checkpointing long transmissions to allow them to pick up from where they left off in the event of a crash and subsequent recovery)
OSI-model: Explain the Presentation layer
Unlike the lower layers, which are mostly concerned with moving bits around, the presentation layer is concerned with the syntax and semantics of the information transmitted.
In order to make it possible for computers with different internal data representations to communicate, the data structures to be exchanged can be defined in an abstract way, along with a standard encoding to be used ‘‘on the wire.’’
The presentation layer manages these abstract data structures and allows higher-level data structures (e.g., banking records) to be defined and exchanged.
OSI-model: Explain the Application layer
The application layer contains a variety of protocols that are commonly needed by users.
One widely used application protocol is HTTP (HyperText Transfer Protocol), which is the basis for the World Wide Web.
Other application protocols are used for file transfer, electronic mail, and network news.
What is Remote Procedure Call (RPC)?
Remote Procedure Call (RPC) is a protocol that one program can use to request a service from a program located in another computer in a network without having to understand network details. (A procedure call is also sometimes known as a function call or a subroutine call.)
- RPC uses the client/server model.
- The requesting program is a client and the service-providing program is the server.
- Like a regular or local procedure call, an RPC is a synchronous operation requiring the requesting program to be suspended until the results of the remote procedure are returned.
- However, the use of lightweight processes or threads that share the same address space allows multiple RPCs to be performed concurrently.
Explain Remote Method Invocation (RMI)?
RMI is the Java version of what is generally known as a remote procedure call (RPC), but with the ability to pass one or more objects along with the request.
What is Marshalling?
Marshalling is the process of taking a collection of data items and assembling them into a form suitable for transmission in a message.
What is Unmarshalling?
Unmarshalling is the process of disassembling data on arrival.
- Values are converted to an agreed external format before transmission, and converted to the local format on receipt.
- Values are transmitted in the sender’s format together with an indication of the format used.
- Translate at sender side, receiver side, or both!
What is Request-reply communication?
It is one of the basic methods computers use to communicate with each other, in which the first computer sends a request for some data and the second computer responds to the request.
What are the different Failure models?
- Fail-stop
- Process halts and remains halted. Other processes may detect this state.
- Crash
- Process halts and remains halted. Other processes may not be able to detect this state.
- Omission
- A message inserted in an outgoing message buffer never arrives at the other end’s incoming message buffer.
- Send-omission
- A process completes a send but the message is not put in its outgoing message buffer.
- Receive-omission
- A message is put in a process’s incoming message buffer, but that process does not receive it.
- Arbitrary (Byzantine)
- Process/channel exhibits arbitrary behaviour: it may send/transmit arbitrary messages at arbitrary times,
commit omissions; a process may stop or take an incorrect step.
- Process/channel exhibits arbitrary behaviour: it may send/transmit arbitrary messages at arbitrary times,
Request-reply protocols: How do they cope with lost requests and lost repliests?
- Lost Replies
- Client: Times out and retransmits request
- Server:
- If idempotent operation
- Re-execute
- If non-idempotent
- Use a history (buffer) of results and retransmit
- If idempotent operation
- Lost Requests
- Client: Times out and retransmits
Define the properties of Objects
- Interfaces and services
- Each object is an instance of a type that defines a set of methods (interface) that can be invoked to operate on the object.
- Separation of interfaces and implementation: independent (re-)implementation of C/S
- Invocation is syntactically and (semantically) independent of an object’s location or implementation.
- Defines “type”
- Encapsulated
- The only way to operate on an object is through its methods; the internal representation/implementation is hidden from view.
- State only accessible via message passing / RMI
- Already logically partitioned physical distribution
- Unit for persistence, caching, location, replication, and/or access control.
- Dynamically allocated/destroyed/binding
- Objects are created as needed and destroyed when no longer needed; not bound to specific program scope
- Client dynamically locates and binds to servers
- Uniquely referenced
- Each object is uniquely identified during its existence by reference that can be held/passed/stored/shared.
- For Distr sys: add mapping between id and (current) location
What is an Interface Definition Language (IDL)?
It is a specification language used to describe a software component’s application programming interface (API).
IDLs describe an interface in a language-independent way, enabling communication between software components that do not share one language.
For example, between those written in C++ and those written in Java.
What is a remote object?
A remote object is the object that contains the methods that can be invoked when using RMI.
What are Distributed Objects?
They create the illusion of a “method call” on a different machine.
Distributed Objects can be located on the server while being invoked by the client.
The marshalled invocation is passed accross the network to the server.
What is a Remote Object Reference?
Uniquely identifies an object system-wide in time and space.
Fx (first 4 blocks are 32 bits):
| Internet address | Port nr | Time | Object nr | Interface of remote obj |
Problem: What if objects migrate?
Add a service that maps object refs to current (last known) location.
What is a servant?
A servant is an instance of a class that provides the body of a remote object.
It is the servant that eventually handles the remote requests passed on by the corresponding skeleton.
Servants live within a server process. They are created when remote objects are instantiated and remain in use until they are no longer needed, finally being garbage collected or deleted.
Implementation of RMI: Garbage collection
Other computers have remote references to objects. Such objects cannot be garbage collected purely locally.
- Distributed Garbage Collection
- Reclaim object when no object/node in the system can reference the object
- Tolerating (transient failures) and concurrency (add/release references)
Implementation of RMI: Parameter Passing
Should parameters (IN and OUT / return) be transferred by value or reference? Normally, anything is by reference, except primitive or valueTypes
Call-By-Value: a copy created at receiver
- Potentially expensive marshalling and communication of large objects state+code
- Side-effects made by receiver are not visible to calee
System objects cannot be marshalled eg. open files, threads…)
Implementation of RMI: Exceptions
- Where are exceptions that are generated on the server side directed?
- 2 kinds:
- server side handling
- client side handling
- Which can take suitable recovery action?
- 2 kinds:
- What about new exception types introduced by the RMI subsystem?
- Remote object may be/become inaccessible
RIM: What are Stubs?
- A client stub is responsible for conversion (Marshalling) of parameters used in a function call and deconversion of results passed from the server after execution of the function.
- A server skeleton, the stub on server side, is responsible for deconversion of parameters passed by the client and conversion of the results after the execution of the function.
RMI: What are the security problems with Distributed Class Files?
- Dynamically loaded code from remote clients (perhaps programmed by other people) cannot / should not be trusted
- Anybody that knows the interface can access the remote object!
- Before a Java application is allowed to download code dynamically, a suitable security manager and security policy must be set.
- If no security manager is set, stubs and classes can only be loaded from the local CLASSPATH.
What is a stateless server?
Stateless means there is no record of previous interactions and each interaction request has to be handled based entirely on information that comes with it.
Semantics of File Sharing: Unix semantics
- Every operation on a file is instantly visible to all processes: a read operation returns the effect of the last write operation
- Can only be implemented for remote access models in which there is only a single copy of the file
Semantics of File Sharing: Session semantics
- No changes are visible to other processes until the file is closed.
- The effects of read and write operations are seen only to the client that has opened (a local copy) of the file.
- When the file is closed, only one client’s writes remain
Semantics of File Sharing: Immutable files
No updates are possible; simplifies sharing and replication
Semantics of File Sharing: Transaction semantics
- All changes occur atomically.
- The file system supports transactions on a single file
- Issue: how to allow concurrent access to a physically distributed file
File System Models: Remote Access Model vs Upload/Download Model
- Remote Access Model
- The client requests to access the remote file on the server.
- The file always stays on the server.
- Upload/Download Model
- File is deleted from the server and moved to the client
- The client accesses the file
- File is saved as a new file on the server
Explain Network File System (NFS)?
An implementation and a specification (RFC) of a software system for accessing remote files across LANs (or WANs)
- RPC/XDR based protocol
- Goals
- Access transparency
- Heterogeneous,
- OS Independent
Explain NFS
- Made by SUN in 1985
- Provides a set of RPCs (searching, read/write, ect.)
- Stateless
- Does not provide concurrency-control mechanism
Use separate lock-service. - Fault tolerance
- Operations are idempotent
- Server is stateless
Fault-Tolerance of NFS
- No RPC for open / close!
- File-handle supplied at each invocation
- Operations are Idempotent
- Repeated invocations leaves server in same state
- Server is State-less!
- Server crash: Client can continue unaffected when server recovers
- Client crash: No state to be remembered/ or leaned up at server
Explain Caching in NFS
Both (in main memory):
- Server-side caching:
- Read operations: easy.
- Write operations:
- Write-through, or
- Delayed-write: flush on commit operation (+file close)
- Client-side caching:
- Similarly caches read/write/getattr/lookup results
- Consistency problems when several clients holds copies of the same blocks
Client cache validation check in NFS
- Time-stamp based validation
- Client validation before use of cache contents
- TC is the time of the last validation of cached block
- Tm-server is the modification timestamp stored at server
- Tm-client is the modification timestamp stored at client
- T=current time
- t is the freshness interval
- TC is the time of the last validation of cached block
- Valid if: (T- TC < t) or (Tm-client = Tm-server)
- Tm-client obtained through getattr polling before cache entry is used
- t is 3-30s adaptive (compromise between consistency and efficiency (files/directories))
What is a Daemon?
A daemon is a computer program that runs as a background process, rather than being under the direct control of an interactive user.
- Systems often start daemons at boot time and serve the function of responding to network requests, hardware activity, or other programs by performing some task.
- Daemons can also configure hardware, run scheduled tasks, and perform a variety of other tasks.
Explain main pointers of The Andrew File System (AFS)
- A distributed computing environment
- Design objectives
- Highly scalable: targeted to span over 5000 workstations.
- Whole-file-serving:
- Entire contents of directories and files transfered from server to client.
- Whole-file-caching:
- When file transfered to client it will be stored on that client’s local disk
- Clients more independent of server than NFS
What happens when a user opens a file in the Andrew Files System (AFS)?
- A user process opens a shared file not in local cache.
- Client requests a copy of the file from server
- The copy is cached on the local file system.
- Read and write operations are performed on the local copy
- When the user process performs a close operation, and if the file has been modified, it is copied back to the server.
- The server installs the new version of the file, and updates the last modified timestamp for the file.
Why use The Andrew Files System (AFS)?
- For infrequently updated files, the cached copies remain valid for long periods (e.g. system binaries)
- Large caches are possible
What is a call-back promise?
A token representing a promise made by server that it will notify the client when the cached file is modified by other clients
- Stored in client disk-cache
- States: valid or cancelled
- Moves from valid to cancelled state when callback is received
- Client access to file with cancelled call-back promise => fetch fresh copy from server
- Client access to file with valid call-back promise => use local copy
Update Semantics of Unix, NFS and AFS
- Unix: one-copy semantics
- there is one copy of the file, and each write is destructive (i.e., “last write wins”)
- NFS: one-copy semantics, except:
- clients may have out-of-date cache entries for brief periods of time when files are shared, can lead to invalid writes at the server.
- AFS: session semantics
- if a callback message is lost, a client will continue working with an out-of-date copy for at most T minutes
- if two clients writes to the same file concurrently => last to close wins (Use locking if needed)
Failure Performance: NFS vs AFS
- When an NFS server fails, everything fails
- all accesses have apparent local semantics (except for “soft mounts”)
- when a server fails, it is as though the local disk has become unobtainable
- since authentication files are often stored on NFS servers, this brings down the entire system
- When an AFS server fails, life (partly) goes on
- all locally cached files remain available
- work is still possible, though there is a higher chance of conflict for shared files
Explain Microsoft Message Queueing (MSMQ)
MSMQ is essentially a messaging protocol that allows applications running on separate servers/processes to communicate in a failsafe manner.
A queue is a temporary storage location from which messages can be sent and received reliably, as and when conditions permit. This enables communication across networks and between computers, running Windows, which may not always be connected.
By contrast, sockets and other network protocols assume that direct connections always exist.
What is a socket?
- An interface between application and network
- The application creates a socket
- The socket type dictates the style of communication
- reliable vs. best effort
- connection-oriented vs. connectionless
- Once configured the application can
- pass data to the socket for network transmission
- receive data from the socket (transmitted through the network by some other host)
Name the different kinds of System Queues for messages
- Journal queues
- stores copies of messages sent to/through/from this machine
- read-only (can’t be directly sent to); much like database logs
- Dead-letter queues
- final resting place of undeliverable messages
- one each for transactional and non-transactional Q’s
- read-only (can only be read and deleted, not sent to)
- Connector queues
- used for store-and-forward messaging in route
Name the different Communication Modes in Distributed Systems (something-cast)
- Uni-cast
- Messages are sent from exactly one process to one process
- Broad-cast
- Messages are sent from exactly one process to all processes on the network.
- Multi-cast
- Messages are sent from exactly one process to several processes on the network (named group).
- Any-cast
- Message is sent to one (eg “best” or “nearest”) of a set of possible receivers
- Geo-cast:
- Message sent to geographically close neighbors
Explain the Unicast use
- With 4 receivers, the sender must replicate the stream 4 times.
- Consider good quality audio/video streams are about 1.5Mb/s (a T1)
- Each additional receiver requires another 1.5Mb/s of capacity on the sender network
- Multiple duplicate streams over expensive WAN links
Explain the Publish-Subscribe Model
It is a messaging pattern where senders of messages, called publishers, do not program the messages to be sent directly to specific receivers, called subscribers, but instead characterize published messages into classes without knowledge of which subscribers, if any, there may be.
Similarly, subscribers express interest in one or more classes and only receive messages that are of interest, without knowledge of which publishers, if any, there are.
Pub/sub is a sibling of the message queue paradigm, and is typically one part of a larger message-oriented middleware system.
Explain Distributed Shared Memory
Give processes the illusion that they are running on a shared memory machine, even though they run on different machines and that their memories are physically distributed
What is the Aim of Peer-to-Peer Systems?
- Sharing of data and resources at very large scale
- Privacy
- Anonymity
Peer-to-Peer: What is a super-node?
- A client with
- Sufficient Bandwidth
- High availability
- Public IP
What is Onion Routing?
Onion routing is a technique for anonymous communication over a computer network.
In an onion network, messages are encapsulated in layers of encryption, analogous to layers of an onion.
The encrypted data is transmitted through a series of network nodes called onion routers, each of which “peels” away a single layer, uncovering the data’s next destination.
When the final layer is decrypted, the message arrives at its destination.
The sender remains anonymous because each intermediary knows only the location of the immediately preceding and following nodes.
P2P: Unstructured vs Semi-structured vs Structured
- Unstructured
- Links in overlay created arbitrarily
- Semi-structured
- P2P system with super-peers
- Structured
- Logical topology on node and data ID’s (eg most DHT’s)
What is a Distributed Hash Table?
- A class of a decentralized distributed system
- provides lookup service similar to a hash table (maps object key to a live node)
- KVPs are stored in a DHT
- Responsibility for maintaining the mapping from keys to values is distributed among the nodes.
- This allows a DHT to scale to extremely large numbers of nodes and to handle continual node arrivals, departures, and failures.
What are the common issues with P2P?
- Organize, maintain overlay network
- routing
- node arrivals
- node failures
- Resource allocation/load balancing
- Efficient placement & localization
- Locality (network proximity)
What is a backoff slot?
A backoff slot is an amount of time that a station can wait after the channel goes idle before the station tries to transmit again.
Differently backoff slot times add quality of service
What is a bridge?
A bridge operates as a switched LAN (not a hub)
Computers, bridges and hubs connect to its ports.
Reference model used in this course: Name the devices that process the different layers
- Application layer = Application gateway
- Transport layer = Transport gateway
- Network layer = Router
- Data link layer = Bridge, switch
- Physical layer = Repeater, hub
What is a Virtual LAN
A virtual LAN (VLAN) is any broadcast domain that is partitioned and isolated in a computer network at the data link layer
Explain Store-and-Forward Packet Switching
Information is sent to an intermediate station where it is kept and sent at a later time to the final destination or to another intermediate station.
What is a datagram?
A datagram is a basic transfer unit associated with a packet-switched network. The delivery, arrival time, and order of arrival need not be guaranteed by the network.
Connectionless
What is a Virtual Circuit?
Tells the router where to send the packet.
What is routing?
- Routing is the process of discovering network paths
- Model the network as a graph of nodes and links
- Decide what to optimize (e.g., fairness vs efficiency)
- Update routes for changes in topology (e.g., failures)
What is Forwarding?
Forwarding is the sending of packets along a path
What is a sink tree?
The set of optimal routes from all nodes to a given destination, form a tree rooted at the destination. Such a tree is called a sink tree.
The tree only contains the optimal paths from all nodes to the destination
Explain The Optimality Principle
If node y is on the optimal path from node x to z, then the optimal path from y to z also falls along the same path
What is Flooding?
A simple method to send a packet to all network nodes
- Each node floods a new packet received on an incoming link by sending it out all of the other links
- Nodes need to keep track of flooded packets to stop the flood; even using a hop limit can blow up exponentially
Explain Distance Vector Routing
- A dynamic algorithm
- Each router maintains a table giving the best known distance to each destination and which link to use to get there.
- The tables are updated by exchanging info with neighbours.
- Eventually each router knows the best link to reach each destination.
What is the Count-to-Infinity Problem?
The core of the count-to-infinity problem is that if A tells B that it has a path somewhere, there is no way for B to know if the path has B as a part of it.
To see the problem clearly, imagine a subnet connected like A–B–C–D–E–F.
Suppose A goes offline. B notices that the route to A, which was distance 1, is down. The problem is, B also gets an update from C, and C is still not aware of the fact that A is down. So C tells B that A is only two jumps from C (C to B to A), which is false. Since B doesn’t know that the path from C to A is through itself (B), it updates its table with the new value “B to A = 2 + 1”. Later on, B forwards the update to C and due to the fact that A is reachable through B (From C point of view), C decides to update its table to “C to A = 3 + 1”. This slowly propagates through the network until it reaches infinity
Explain Link State Routing
- Replaced Distance Vector Routing.
- The complete topology of the network is distributed to every router.
- Then Dijkstra’s algorithm can be run at each router to find shortest path to each router.
Each router must do the following things to make Link State Routing work:
- Discover its neighbours and learn their network addresses
- Set the distance or cost metric to each of its neighbours.
- Constuct a packet telling all it has just learned.
- Send this packet to and receive packets from all other routers.
- Compute the shortest path to every other router.
Explain Hierarchial Routing
Routers are divided into regions. Each router knows all the details about how to route packets to destinations within its own region but knows nothing about the internal structure of other regions.
Hierarchical routing reduces the work of route computation but may result in slightly longer paths than flat routing
Explain Broadcast Routing
- Broadcast sends a packet to all nodes
- RPF (Reverse Path Forwarding): send broadcast received on the link to the source out all remaining links
- Alternatively, can build and use sink trees at all nodes
Explain Traffic-Aware Routing
Choose routes depending on traffic, not just topology
(Like when driving it is sometimes faster to take a longer road if there is traffic on the shorter road)
Explain Admission Control
Admission control allows a new traffic load only if the network has sufficient capacity, e.g., with virtual circuits
- Can combine with looking for an uncongested route
Explain Traffic Throttling
Congested routers signal hosts to slow down traffic
ECN (Explicit Congestion Notification) marks packets and receiver returns signal to sender
What is Load Shedding?
When the network discards packets that it cannot deliver.
Explain Tunneling
Think of a bank with a IPv6 network in Paris and a IPv6 network London that are connected via the IPv4 Internet.
To send an IP packet to London, the Paris office constructs the packet containing an IPv6 address, and sends it to the multiprotocol router that connects the Paris IPv6 network to the IPv4 Internet.
When this router gets the IPv6 packet, it encapsulates the packet with an IPv4 header addressed to the IPv4 side of the multiprotocol router that connects to the London IPv6 network.
When this wrapped packet arrives, the London router removes the original IPv6 packet and sends it onward to the destination host.
Explain Packet Fragmentation
Networks have different packet size limits for many reasons
Large packets sent with fragmentation & reassembly
What is Subnetting?
Subnetting splits up IP prefix to help with management
Looks like a single prefix outside the network
What is Aggregation?
Aggregation joins multiple IP prefixes into a single larger prefix to reduce routing table size
What does a Network Address Translation (NAT) box do?
It maps one external IP address to many internal IP addresses
- Uses TCP/UDP port to tell connections apart
- Violates layering; very common in homes, etc.
What are the control protocols that IP works with?
IP works with the help of several control protocols:
- ICMP is a companion to IP that returns error info
- Required, and used in many ways, e.g., for traceroute
- ARP finds Ethernet address of a local IP address
- Glue that is needed to send any IP packets
- Host queries an address and the owner replies
- DHCP assigns a local IP address to a host
- Gets host started by automatically configuring it
- Host sends request to server, which grants a lease
Interior Routing Protocol: What is Open Shortest Path First (OSPF)?
OSPF computes routes for a single network (e.g., ISP)
- Models network as a graph of weighted edges
- It divides one large network into areas connected to a backbone area
- It is link-state routing:
- Uses messages below to reliably flood topology
- Then runs Dijkstra to compute routes
What is an address space?
Address space is the amount of memory allocated for all possible addresses for a computational entity, such as a device, a file, a server, or a networked computer.
When is the Border Gateway Protocol (BGP) used?
Is used to do routing based on policies.
What are Berkley Sockets?
Berkeley sockets is an API for Internet sockets and Unix domain sockets, used for inter-process communication (IPC). It is commonly implemented as a library of linkable modules.
What are TSAPs?
TSAPs are ports for TCP/UDP
What is a Three-way handshake?
- Host1 sends a Connect Request
- Host2 sends an Acknowledgement
- Host1 sends data
How does a Connection Release work?
When the two hosts are done sending they want to release the connection.
- Host1 sends a Disconnect Request
- Host2 replies a Disconnect Request (that also serves as a sort of ACK)
- Host1 sends a ACK
What is Flow Control?
It is the process of managing the rate of data transmission between two nodes to prevent a fast sender from overwhelming a slow receiver.
What is Multiplexing?
Channels are often shared by multiple signals. After all, it is much more convenient to use a single wire to carry several signals than to install a wire for every signal. This kind of sharing is called multiplexing.
What is inverse multiplexing?
If a user needs more bandwidth or more reliability than one of the network paths can provide, a way out is to have a connection that distributes the traffic among multiple network paths on a round-robin basis.
This is called inverse multiplexing.
What is Goodput?
Goodput is the application level throughput, i.e. the number of useful information bits delivered by the network to a certain destination per unit of time. The amount of data considered excludes protocol overheadbits as well as retransmitted data packets. This is related to the amount of time from the first bit of the first packet sent (or delivered) until the last bit of the last packet is delivered
For example, if a file is transferred, the goodput that the user experiences corresponds to the file size in bits divided by the file transfer time. The goodput is always lower than the throughput
When would a sender need to slow down (the sending)
- Flow control
- when the receiver is not fast enough
- Congestion
- when the network is not fast enough
What is UDP?
UDP uses a simple connectionless transmission model with a minimum of protocol mechanism. It has no handshaking dialogues, and thus exposes the user’s program to any unreliability of the underlying network protocol. There is no guarantee of delivery, ordering, or duplicate protection.
What is a Checksum?
A checksum is a count of the number of bits in a transmission unit that is included with the unit so that the receiver can check to see whether the same number of bits arrived.
If the counts match, it’s assumed that the complete transmission was received.
Both TCP and UDP communication layers provide a checksum count and verification as one of their services.
What is Real-time Transport Protocol (RTP)
RTP (Real-time Transport Protocol) provides support for sending real-time media over UDP
- Often implemented as part of the application
RTP header contains fields to describe the type of media and synchronize it across multiple streams
- RTCP sister protocol helps with management tasks
Buffer at receiver is used to delay packets and absorb jitter so that streaming media is played out smoothly
High jitter, or more variation in delay, requires a larger playout buffer to avoid playout misses
- Propagation delay does not affect buffer size
What is TCP?
TCP provides reliable, ordered, and error-checked delivery of a stream of octets (unit of size 8 bits) between applications running on hosts communicating over an IP network.
What does the TCP header include?
It includes addressing (ports), sliding window (seq. / ack. number), flow
control (window), error control (checksum) and more.
How does TCP establish connections?
TCP sets up connections with the three-way handshake
Release is symmetric (Both the client and server can initiate the disconnect operation.)
TCP/IP: Application layer
Includes the protocols that provide user services.
- Protocols:
- HTTP
- FTP
- Etc.
TCP/IP: Transport layer
- Establishes data channels that applications use
- End-to-end message transfer independent of underlying network
- Error, Flow and Congestion Control
- Contains the protocols: TCP and UDP
TCP/IP: Internet layer
- Responsible for sending packets across multiple networks.
- Does host addressing and identification
- Does packet routing (sending datagrams from source to destination
- Contains the protocols: IP and ICMP
TCP/IP: Link layer
Contains communication methods for data that remain within a single network segment
What is one of the problems with sending a lot of small frames?
Each frame needs a header which takes up space, often better to send a larger frame with only one header instead.
Explain Delay Tolerant Networks (DNT)
Store messages inside the network until they can be delivered
- Messages called bundles are stored at DTN nodes while waiting for an intermittent link to become a contact
- Bundles might wait hours, not milliseconds in routers
- May be no working end-to-end path at any time
Explain Addresses, Ports and Sockets with a real world analogy
Like apartments and mailboxes
- You are the application
- Your apartment building address is the address
- Your mailbox is the port
- The post-office is the network
- The socket is the key that gives you access to the right mailbox (one difference: assume outgoing mail is placed by you in your mailbox)
Sockets: The bind function
Associates and (can exclusively) reserves a port for use by the socket
How does nodes keep track of time?
- Each node has its own private physical clock !
- Physical clocks are HW devices that count oscillations of a quartz.
- After a specified number of oscillations, the clock increments a register, thereby adding one clock-tick to a counter that represents the passing of time: Hi(t).
What is Clock Drift?
Two clocks count time at different rates.
What is Clock Skew?
The difference between the times on two clocks
Explain external clock synchronization
Synchronization of process’ clocks with an authorative external source.
Explain internal clock synchronization
Synchronization of process’ clocks with each other
Clocks: What are synchronization bounds?
The maximum amount of clock skew allowed between two clocks.
- Let K > 0 be the synchronization bound
- Let clock1 and clock2 be clocks at two processes
- If (clock1.time - clock2.time) < K
- Then clocks clock1, clock2 agree within the bound of K
Synchronous systems: When synchronizing with an external source, how does the client make sure that the time is correct?
(The server sends what time it is to the client)
Since the system is a synchronous system we know (by assumption):
- Known upper (max) and lower (min) bound for communication delay,
- Known maximum clock drift,
- Known maximum time taken for each computational step.
So we synchronize by:
- Time server sends its local time t to a client,
- Ideally, client sets clock to tserver +TtransferTime (Unknown!)
- The client sets its local clock to tserver + (max+min)/2.
- Skew is at most (max-min)/2
Explain Christians Algorithm
A server (or multiple) server have access to a UTC source, and clients can then request the time from this server.
Explain The Berkley Algorithm
A server gets the clock times from all clients, averages them, and then sends back the “new” time.
Main attributes of the Network Time Protocol
- Synchronization of clients relative to UTC on an internet-wide scale
- Reliable, even in the presence of extensive loss of connectivity
- Allow frequent synchronization (relative to clock drift)
- Tolerant against disturbance
Explain NTP Stratum
- Higher level servers never synchronize with servers at lower stratum
- Failures: nodes connected to multiple servers; degradation to higher level nodes
What are the different Network Time Protocol Modes?
- Multicast (for quick LANs, low accuracy)
- server periodically sends its actual time to its leaves in the LAN
- Procedure-call (medium accuracy)
- server responds to requests with its actual timestamp
- like Cristian’s algorithm
- Symmetric mode (high accuracy)
- used to synchronize between pairs of time servers (mostly at high stratums)
In all cases, the UDP is used
What is Leslie Lamport’s Happened Before Relation
- This ordering is based on two simple and intuitively obvious points:
- If two events occurred at the same process pi ( i = 1, 2, … ,N ), then they occurred in the order in which pi observes them – this is the order –>i that we defined above.
- Whenever a message is sent between processes, the event of sending the message occurred before the event of receiving the message.
- Lamport called the partial ordering obtained by generalizing these two relationships the happened-before relation. It is also sometimes known as the relation of causal ordering.
Total Order Lamport Timestamps
Vectore clocks
An extended version of Lamport’s mechanism, where each process keeps track of all other clocks receiving messages, by storing them in a vector, instead of just choosing the larger value.
What does Loose Coupling mean?
Loose coupling is an approach to interconnecting the components in a system or network so that those components depend on each other to the least extent practicable.
Coupling refers to the degree of direct knowledge that one element has of another.
What does interoperable mean?
It is a property of a system, which interface is completely understood, to work with other systems, present or future, without any restricted access or implementation.
Explain Service Oriented Architecture
Develop large scale applications from (distributed) collections of smaller loosely-coupled service providers
What is Uniform Resource Identifier (URI)?
- URI (Uniform Resource Identifier): a general ressource identifier, whose value may be either URL or URN
- URL: includes resource location information
- http://www.cdk4.net/person
- URN: (Uniform Resource Names): location independent, rely on lookup service to map them onto the URLs of resources
- urn:isbn:0-321-26354-5
XML tags
- XML: tags describe the logical structure of the data
- XML is extensible: users can define their own tags (HTML uses a fixed set of tags)
XML-Schema
- A schema defines the legal structure (grammar) of an XML document
- elements and attributes that can appear in a document,
- how the element are nested and the number of elements,
- whether an element is empty or can include text.
What is SOAP
SOAP is a messaging protocol that allows programs that run on different operating systems (Windows, Linux, etc.) to communicate using HTTP and XML.
SOAP Message Enveloping
How does SOAP use nodes?
Soap message may be destined to a set of intermediary nodes as well as an
ultimate receiver
•En/de-cryption, compression, load-balancing, access control, auditing, routing,
monitoring
How efficient is SOAP?
- SOAP requests may be 14 times longer than CORBA
- SOAP requests may take 882 times as long as CORBA
Explain Web Services Description Language (WSDL)
WSDL (pronounced “Whistle”)
- Interface Definition for Web services
- XML-based language describing:
- What functionality is provided?
- How should it be accessed?
- Where is the service located?
Explain REST
REST is an architectural style for the building of network-based systems
- Characteristics of REST
- “Everything” is resources identified through URIs
- Resources manipulated through representations
- Self-descriptive messages
- Hyperlinks define application state
- Interactions are stateless
- REST emphasizes the role of intermediaries:
- caches, proxies, gateways, etc.
What is a RESTful Web-service?
A web service implemented using HTTP and the principles of REST.
What is a cloud?
A cloud is a unified computing resource made up of several interconnected or virutalized computers.
Explain Platform as a Service (PaaS)
- Development platform (Abstract Infrastructure, OS, Middleware) to drive developer productivity.
- Provides the programmer with sets of software elements than can be combined in a scalable way to build large scale applications
- Hosting and management
- Examples
- Google App Engine: scalable environment for developing and hosting web-applications (managed object storage, messaging, authentication,…)
Explain Software as a Service (SaaS)
- (online) applications and software delivered as a service over the Internet
- No application software installed and run on the customer’s own computers.
- Simplified maintenance and support.
- Pay based on usage.
- API’s /SOA
- Examples:
- Google Docs, Gmail,
Cloud: Under/Over Provisioning of server capacity
- Over-provisioning is expensive
- Poor Ressource Utilization
- How to predict peak-demand?
- Under-provisioning leads to
- poor response time
- bad user experience / efficiency
- Sustained under provisioning ==> customers leave
- E.g. ”Friendster”
What is a Security Policy?
A network security policy, or NSP, is a generic document that outlines rules for computer network access, determines how policies are enforced and lays out some of the basic architecture of the company security/ network security environment.
What is a Security Mechanism?
- A security mechanism are used to enforce a security policy.
- Mechanisms can be nontechnical, such as requiring proof of identity before changing a password; in fact, policies often require some procedural mechanisms that technology cannot enforce
Explain the CIA Triad
- Confidentiality:
- Access must be restricted to those authorized to view the data in question
- Integrity:
- Maintaining the consistency, accuracy, and trustworthiness of data over its entire life cycle.
- Availability:
- Data is available.
- Providing adequate bandwidth
- Disaster recovery
- Data is available.
Name the security threats
- Eavesdropping
- Masquerading
- Message tampering
- Replaying
- Denial of service
What is a block cipher?
A block cipher is a method of encrypting text (to produce ciphertext) in which a cryptographic key and algorithm are applied to a block of data (for example, 64 contiguous bits) at once as a group rather than to one bit at a time.
Explain Cipher Block Chaining
In CBC mode, each block of plaintext is XORed(true if either but not both inputs are true) with the previous ciphertext block before being encrypted.
This way, each ciphertext block depends on all plaintext blocks processed up to that point. To make each message unique, an initialization vector must be used in the first block.
Security terms used in our project that we need at DSN exam
- Cryptography notation
- Signing / Certificate
- Encryption
Security: What is a Nonce?
A nonce, in information technology, is a number generated for a specific use, such as session authentication. In this context, “nonce” stands for “number used once” or “number once.”
Explain the Needham-Schroeder secret-key authentication protocol
- A requests S to supply a key for communication with B
- S returns a msg encrypted with A’s secret key, containing KAB and a ‘ticket’ encrypted with B’s secret key. The nonce NA demonstrates that the msg was sent in response to the preceeding one. A belives that S sent the msg because only S knows A’s secret key.
- A sends the ‘ticket’ to B
- B decrypts the ticket and uses the new key KAB to encrypt another nonce NB
- A demonstrates to B that she was the sender of the previous msg by returning an agreed transformation of NB.
What is Kerberos?
Designed for intranet authentication and encryption.
- Requires central server(s) holding user passwords (possibly in scrambled form).
- Ticket: Token issued to a client for presentation to a particular server.
- Authentication: A token constructed by a client and sent to a server to prove the identity of the user.
- Session key: A secret key randomly generated by Kerberos and issued to a client for use when communicating with a particular server.
Explain the Heartbleed bug
Security vulnerability in OPENSSL software that lets a hacker access the memory of data servers.
XKCD comic explanation used in lecture:
- A asks server to respond with the word “potato”, 6 letters long (and the server responds)
- A asks the server to respond with the word “hat” 500 letters long.
- The server then prints “hat” and the next 497 words in memory (containing passwords etc.)
Explain the Shellshock bug
Shellshock is a family of security bugs in the widely used Unix Bash shell.
Many Internet-facing services use Bash to process certain requests, allowing an attacker to cause vulnerable versions of Bash to execute arbitrary commands. This can allow an attacker to gain unauthorized access to a computer system.
Name the different scales of networks
- Vicinity = Personal Area Network
- Building = Local Area Network
- City = Metropolitan Area Network
- Country = Wide Area Network
- Planet = The Internet
What is ubiquitous computing?
Embedding computation into the environment and everyday objects would enable people to interact with information-processing devices more naturally and casually than they currently do, and in ways that suit whatever location or context they find themselves in.
What is big data
Large sets of data.
What is a packet-switched network?
Packet-switched describes the type of network in which relatively small units of data called packets are routed through a network based on the destination address contained within each packet
What is slow-start?
- The purpose of slow start is to avoid congestion.
- It works by sending one packet.
- When an ack msg is received it thinks “that went well lets turn it up a bit”.
- It then sends two packets.
- It keeps doubling this way until either it fails or the msg has been delivered.
- The reason to send multiple packets is to achieve higher transmission speed.
What is a routing table?
A routing table is a set of rules, often viewed in table format, that is used to determine where data packets traveling over an Internet Protocol (IP) network will be directed.
A basic routing table includes the following information:
- Destination: IP address of the packet’s final destination
- Next hop: The IP address to which the packet is forwarded
- Interface: The outgoing network interface the device should use when forwarding the packet to the next hop or final destination
- Metric: Assigns a cost to each available route so that the most cost-effective path can be chosen
- Routes
Explain the IPv6 header
IPv6 protocol header has much longer addresses (128 vs. 32 bits) and is simpler (by using extension headers)
It handles other functionality:
Extension header: Description
Hop-by-hop options: Additional information for the destination
Routing: Loose list of routers to visit
Fragmentation: Management of datagram fragments
Authentication: Verification of the sender’s identity
Encrypted security payload: Information about the encrypted contents
What is an internetwork?
Internetworking is the practice of connecting a computer network with other networks through the use of gateways that provide a common method of routing information packets between the networks.
The resulting system of interconnected networks is called an internetwork, or simply an internet.
What is the ICMP protocol?
It is used by network devices, like routers, to send error messages indicating, for example, that a requested service is not available or that a host or router could not be reached. ICMP can also be used to relay query messages
Found in the Internet layer of TCP/IP
What is a sequence number?
When frames may be transmitted multiple times there is a danger that the receiver will accept the same frame two or more times and pass it to the network layer more than once. To prevent this from happening, it is generally necessary to assign sequence numbers to outgoing frames, so that the receiver can distinguish retransmissions from originals.
What is a GUID?
A globally unique ID
Explain routing table for connectionless network
- For sending datagrams
- Each router has a table telling it which outgoing line to use for each possible destination router.
- This table can be updated as often as needed, due to jams, nodes broken down or other reasons.
Explain Routing Tables for Connection oriented networks
In a connection oriented network, each packet has a Virtual Circuit that tells the routers where to send the packet.
- Connection setup:
- A route is chosen and given to the VC
- VC is assigned a unique VC number
- The setup procedure uses the same kind of table as datagrams.
- Each router along the chosen path puts an entry in a table, linking the VC number to an outgoing line.
- Every further packet in this connection has the VC number in a header, which the routers then reads, to determine where to send the packet.
Sliding window
The purpose of Sliding window is to avoid congestion by making sure sender does not send more than the receiver can handle (throttling)
- Sender: This is how big of a window i need
- Receiver: This is how big of a window i have
- In each ack msg the receiver says: Remaining window space
RMI: What are server threads?
A thread on the server. Typically each remote invocation is run in its own separate thread.
RMI: Call Semantics (Maybe, At least once, At mose Once)
- Maybe:
- The client calls the remote method, and is happy if he receives a reply, otherwise he just carries on
- At lease once:
- The client calls the remote method until he receives a reply. The server keeps running the func while he receives the request.
- At most once:
- The client calls the remote method until he receives a reply. The server only calls the function once, and otherwise just returns a value from the history / buffer.
How are Distributed File Systems different from Centralized?
- No open or close operations
- The Read and Write commands have a parameter specifying a startup point
- Unix has a pointer specifying current position
- All funcs, except Create, are idempotent
NFS: What is a file handle?
An object consisting of the filesystem identifier, the i-node number of file and the i-node generation number.
- i-node number = file location in unix
- generation number needed because i-node number is reused after file is deleted
NFS: What is read-ahead?
Guessing which data you need next, and then reading them while the disk is idle anyway.
NFS: What is write through?
If you are writing critical data, you can request the server to write through the buffer, i.e. writing directly to the disk (also stored in the buffer), before you receive a reply.
NFS: Directory Service
Maps names of network resources to network addresses
NFS: Client Module
Emulates the conventional file system interface
Explain Pastry and the example of forwarding a msg
- Pastry is a routing overlay.
- All nodes and objects are assigned GUIDs.
- In a network with n nodes, the complexity is O(log n)
- Each node stores a leaf set
- Vector containing GUIDs and IPs of nodes with numerically closest GUIDs to either side of their own (above and below)
Example of forwarding a msg
- At each step the msg is closer to the destination
- Has to send msg to GUID 0302
- Finds the peer with longest common prefix (03**)
- Forward msg to him. He has to forward to longest common prefix
Pastry: Leaf set and its purpose
A vector containing the GUIDs and IP addresses of the nodes whose GUIDs are numerically closest on either side of its own.
Purpose:
- Used in Pastry’s routing algorithm to determine whether the receiver is one of the neighbors.
- If there is no match in the routing table
- send to the one of our neighbors that are numerically closest.
Pastry: What happens when a node goes offline and when a node joins?
- Msg is sent to dissapeared node
- Neighbor receives it and must pass it on whenever possible.
- Node joins
- It gets data from other nodes.
P2P: Overlay network
- A distributed algorithm that takes the responsibility for locating nodes and objects.
- Resources and Nodes are identified by GUID.
Explain public key signing
- A generates key pairs K.priv and K.pub
- A computes the digest of message M, H(M) using an agreed secure hash func H.
- A encrypts it using the private key K.priv to produce the signature S={H(M)}K.priv
- A sends the signed message [M]K = M,S to B
- B decrypts S using K.pub and computes the digest of M, H(M).
- If they match, the signature is valid.
Name the three threats to distributed systems
- Leakage
- Acquisition of information by unauthorized people
- Tampering
- Unauthorized alteration of information
- Vandalism
- Interference with the proper operation of a system
Classes of attacks
- Eavesdropping
- Obtaining copies of messages without authority
- Masquerading
- Sending or receiving messages using the identity of another principal without their authority
- Message tampering
- Intercepting messages and altering them before passing them on (MITM)
- Replaying
- Storing intercepted messages and sending them later
- Denial of service
- Flooding a channel or resource in order to deny access for other users
What is a HMAC?
- Construction for calculating a message authentication code (MAC) (short piece of information used to authenticate a message) involving a cryptographic hash function in combination with a secret cryptographic key.
- As with any MAC, it may be used to simultaneously verify both the data integrity and the authentication of a message.*
Explain the main pointers of Needham Schroeder (not the protocol itself)
- Based on an authentication server S that supplies secret keys to clients.
- S has a table of names and secret keys for each principal known to the system
- The secret key is used to authenticate client processes and to transmit messages securely between client processes and S.
- The protocol is based on the generation and transmission of tickets by S
- A ticket:
- Encrypted msg containing a secret key for use in communication between A and B.
- If the protocol is successfully completed, both A and B can be sure that any message encrypted in KAB that they receive comes from the other and any message they send encrypted with KAB can only by understood by the other or S.
Code: Socket.listen
Listen causes a connection-oriented Socket to listen for incoming connection attempts.
What is a Lamport clock?
- A simple software counter that is not related to any physical clock.
- Every process keeps a counter
- Each message is timestamped with the counters value, after it has been incremented.
- When sending messages to other machines in the system, this value is then piggybacked, and the host then takes the larger of the values (the piggybacked value and the host’s counter’s value), and sets the counter to this value, before proceeding.
What can be done with vector clocks that cannot be achieved with Lamport clocks?
With Lamport clocks, we know that if event e happened before event e’, then
L(e) < L(e`), but we have no way of going the other way.
- With vectors we can say that we know that:
- “this message happened before this message, and at that time we know that the counter in that process was at least this value”.
We may compare vector timestamps as follows:
V = V’ iff V[j] = V’[j] for j = 1,2,…,N
V ≤ V’ iff V[j] ≤ V’[j] for j = 1,2,…,N
V < V’ iff V ≤ V’ /\ V ≠ V’
What is bus topology?
A bus network is an arrangement in a local area network (LAN) in which each node(workstation or other device) is connected to a main cable or link called the bus.
What is Full-duplex?
Full-duplex data transmission means that data can be transmitted in both directions on a signal carrier at the same time.
For example, on a local area network with a technology that has full-duplex transmission, one workstation can be sending data on the line while another workstation is receiving data.
Full-duplex transmission necessarily implies a bidirectional line (one that can move data in both directions).
