Computer Science notes ⇒ Networks and Distributed Systems

Protocol layers exist to reduce design complexity and improve portability and support for change. Networks are organised as series of layers or levels each built on the one below. The purpose of each layer is to offer services required by higher levels and to shield higher layers from the implementation details of lower layers.

Each layer has an associated protocol, which has two interfaces: a service interface - operations on this protocol, callable by the level above and a peer-to-peer interface, messages exchanged with the peer at the same level.

No data is directly transferred from layer n on one machine to layer n on another machine. Data and control pass from higher to lower layers, across the physical medium and then back up the network stack on the other machine.

As a message is passed down the stack, each layer adds a header (and possibly a tail such as a checksum, although this is most common at the bottom of the stack) and passes it to the next layer. As a message is received up the stack, the headers are removed and the message routed accordingly.

As you move down the stack, layers may have maximum packet sizes, so some layers may have to split up the packet and add a header on each packet before passing each individual packet to the lower layers.

Some protocol design issues include identification (multiple applications are generating many messages and each layer needs to be able to uniquely identify the sender and intended recipient of each message), data transfer alternatives (simplex, half and full duplex), EDC error control (error detection and correction - depends on environment e.g., SNR and application requirements), message order preservation and swamping of a slow receiver by a fast sender (babbling idiot problem, when a failed node swamps a databus with nonsense).

We can also consider two types of protocols, connection vs. connectionless. Connection orrientated services are where a connection is created and then messages are received in the order they are sent, a real world analogy is the POTS. Connectionless services are where data is sent independently. It is dispatched before the route is known and it may not arrive in the order sent, a real world analogy here is the postal system.

The ISO Open Systems Interconnections (OSI) reference model deals with connecting open networked systems. The key principes of the OSI are:

• layers are created when different levels of abstraction are needed
• the layer should perform a well defined function
• the layer function should be chosen with international standards in mind
• layer boundaries should be chosen to minimise information flow between layers
• the number of layers should be: large enough to prevent distinct functions being thrown together, but small enough to prevent the whole architecture being unweildy

Layer	Description	Examples
Application (APP)	Protocols that are designed to meet the communication requirements of specific applications, often defining the interface to a service.	HTTP, FTP, SMTP, CORBA IIOP
Presentation (SECURITY)	Protocols at this level transmit data in a network representation that is independent of the representations used in individual computers, which may differ.	SSL, CORBA Data Representation
Session (ERRORS)	At this level, reliability and adaptation are performed, such as detection of failures and automatic recovery.
Transport (TRANS)	This is the lowest level at which messages (rather than packets) are handled. Messages are addressed to communication ports attached to processes. Protocols in this layer be be connection-orrientated or connectionless.	TCP, UDP
Network (ROUTING)	Transfers data packets between computers in a specific network. In a WAN or an inter-network this involves generation of a route passing through routers. In a single LAN, no routing is required.	IP, ATM virtual circuits
Data link (DATA)	Responsible for transmission of packets between nodes that are directly connected by a physical link. In a WAN, transmission is between pairs of routers or between routers and hosts. In a LAN it is between a pair of hosts.	Ethernet MAC, ATM cell transfer, PPP
Physical (WIRES)	The circuits and hardware that drive a network. It transmits sequences of binary data by analogue signalling, using AM or FM of electrical signals (on cable circuits), light signals (on fibre optic circuits) or other EM signals (on radio or microwave circuits).	Ethernet based-band signalling, ISDN

Messages and headers combine to form packets - the bits that actually appear on the network.

The TCP/IP reference model originated from research in 1974 using the ARPANET (predecessor to the modern Internet). TCP/IP does not have session or presentation layers, which are only really needed in applications with specific requirements, and the data link and physical layers are combined to form one layer.

Protocols within the TCP/IP model include Telnet, FTP, SMTP and DNS at the application layers, TCP and UDP in the transport layer, IP in the network/Internet layer and ARPANET, SATNET, AX.25 and Ethernet in the physical/data-link layer.

Middleware alters the OSI model by replacing session and presentation layers with middleware protocols. In terms of the TCP/IP model, middleware protocols are placed between the application and transport layers. It is a good place to augment TCP/IP with dependability features, e.g., security and fault tolerance.

Middleware protocols abstract away from the difficulties of using raw UDP and TCP, and allow high-level IPC to occur. TCP is connection-based, so a connection needs to be established and closed down before messages can be sent. Messages are sent using the send and receive primitives, and can be used synchronously or asynchronously. Destinations of messages are specified as a tuple of IP address and port as dictated by TCP and UDP.

Sockets

Most client-server communication is synchronous (the client blocks until the server replies), and acknowledgements are redundant, however asynchronous communication allows clients to continue without waiting (e.g., when no reply is expected from the server, or the client accepts the reply when it arrives).

Typically, request-reply type communication is mapped to TCP, as UDP may get omissions, lost replies, duplicates, unordered messages, etc... Using UDP/TCP in this way means distribution is apparent to the application, but one of the goals of distributed systems is transparency. Middleware provides a transparent layer between the application and transport protocols.

Remote Procedure Calls

We have the issue where hosts involved in communication may have different architectures and therefore representing data differently, so data needs to be converted between the sender and receiver representations. This is accomplished by the presentation layer in the OSI model.

The process of encoding and decoding application data and messages is called marshalling and unmarshalling.

We only consider lower level representations (integer lengths and big-endian vs. little-endian, IEEE754 floats vs. non-standard ones, string encoding, arrays, structures, etc) and not the higher level representations (e.g., images, video, multimedia documents, etc) which is dealt with at the application level.

Negotiation is required to change base types into a common format (e.g., 32 bits for integers), structures and arrays must be packed for transport, and more complex types (such as pointers), must be linearised. The most common conversion strategies are to use a common/canonical intermediate form, or to use a receiver-makes-right system. Tagging data helps this, as a common interface is used across a range of implementations.

In order to implement failure recovery, the server generates a unique ID for each remote procedure, and all RPCs must include the appropriate ID. The ID can then be used to detect failed server processes (by the dispatcher on the server) using a variety of techniques, and on the restart of the server process, a new ID is created, and the call with the stale ID is aborted. In the case of client failure, the server must be able to "roll back" (or perhaps do nothing if the semantics require it) to a previous state.

Different types of failure semantics include: Maybe (Best Efforts) Call Semantics, where the request is sent only once, and it is unknown what happens if the request times out, and unreliable networks may duplicate requests, and the state of the server is not reliable. Another type is At-Least-Once Call Semantics, where the client retries up to n times, so if the call succeeds the procedure has been executed at least once, however depending on the failure modes, this could be more.

At-Most-Once call semantics guarantees that the remote procedure is executed no more than once, but may only be partially complete. Here, the server tracks request identifiers and discards duplicates. The server must buffer replies and retransmit until it is acknowledged by the client. Transactional call semantics guarantees the procedure is executed completely once or not at all (i.e., no partial completion). The server must offer atomic transactions for each RPC, to take it from one consistent state to another consistent state, otherwise other RPCs using the data may get an inconsistent state.

The basis of data communication is that of some variation of a physical property of the communication medium, e.g., voltage on coaxial cable, pulsing light down fibre optics or RF propagation through the atmosphere.

At the physical level, we deal with communications at a bit level, and this is probably the most difficult layer to deal with, as physical hardware sends or receives raw bit streams and bit streams tend not to be error free.

Encodings such as non return-to-zero (NRZ) are used as electrical failure is easier to detect and signal-to-noise ratio is improved; here, 0 is -5V and 1 is +5V. The Manchester encoding improves the SNR further as an alternating signal is used - a '1' is represented by a full cycle of the inverted signal from the master clock.

The introduction of fault tolerance at this layer makes transparency difficult - the session layer is supposed to be responsible for fault tolerance, but this can only really be done with a fault model (i.e., a knowledge of errors due to transmission at the physical layer).

A limit on the data rate is placed by the sampling frequency. The Nyquist Samping Theorem (developed by Harry Nyquist working at Bell Labs) states that in order to be "perfectly" represented by its samples, a signal must be sampled at a sampling rate (or frequency) equal to at least twice its frequency. Other factors that affect data rate include the SNR and attenuation.

Other issues at the physical layer include latency (delay between sending and data becoming available at destination), message transmission time and throughput (the total volume of data across a network in any given time).

The data link layer builds the bit stream into frames of data.

The start and end of frames can be denoted by time gaps, however we then have the problem of missing bits - how do we signify the difference between the end of a frame and an error. We could denote a time gap with a certain sequence (e.g., CAN uses 6 consecutive equal bits), but this sequence could also indicate failure and "real" data has to be stuffed (insertion of an alternate bit pattern based on a pattern known to both sender and receiver that the receiver ignores) to prevent n equal bits being misconstrued as an error or time gap.

Other ways of implementing frames is by using a character count, start/end characters and this can be combined with parity checking or CRC checks.

Standards such as RS232 are point-to-point standards, which specify mechanical, electrical, functional and procedural interfaces. RS232 utilises a number of copper wires to connect two nodes, and what signals on these wires mean. Unidirectional hardware control lines are used to control flow.

On RS232, communications normally occur using either a 7 or 8 bit byte, followed by an optional parity bit or stop bit. Both ends have to be configured in the same manner for communication to occur, however. RS232 has no real real error control, so the data-link layer usually includes some kind of basic protocol.

For RS232, transfer of data from source to destination occurs by an unacknowledged connectionless service (the source sends independent data frames to the destination), an acknowledged connectionless service (the source sends independent data frames to the destination with acknowledgement returned) or an acknowledged connection-orrientated service (the source and destination establish connection and send numbered/sequential frames). The latter is more reliable than the former.

Other checks (such as sliding window protocols) can be used, but are normally implemented at higher levels of the network stack.

In addition to point-to-point networks, we can also consider broadcast networks, which share a single communication channel. Here, messages are broken into packets which are broadcast to all on that channel, and when a packet is received, a computer examines the data (which contains a destination address) and discards it if it is not relevant.

Multicasting is a special case of this, and can be implemented in point-to-point networks also. Multicasting is one-to-some (where some is a subset of all destinations), and this requires support in the network hardware.

However, in broadcast networks, we have the problem of deciding who uses the channel if there is competition for it. We use medium access control (MAC) to determine who goes next. There are two main philosophies in this, which is static allocation (typically time slots) and dynamic allocation, which can be either have a central abitration or decentralised allocation (a free-for-all).

One method of solving this problem is ALOHA, which is contention system. In ALOHA, users transmit when data becomes available, however collisions are inevitable, and the colliding frames are destroyed. A sender finds out if a frame is destroyed by also listening. A variation of ALOHA called slotted ALOHA imposes agreed timeslots (this requires global time, however - see later lectures), and you only send at the start of a timeslot.

ALOHA developed into carrier sense multiple access (CSMA), where a sender listens to a channel first and only transmits if it is silent. If a collision occurs, the station waits a random amount of time and then retries. There are two different varieties of CSMA, non-persistent CSMA, which senses transmission and sends if free, but waits for re-sensing if busy, and p-persistent CSMA which senses if the channel is silent, then transmits with probability (1 - p). If the channel is not free after waiting, it continually senses until it is free.

However, we now have the problem of when is a collision detected. An improvement to CSMA can be made by aborting transmission as soon as a collision is detected (however, senders may not immediately hear the collision). The contention period here is normally quite small, as collisions can be detected in just a few microseconds. CSMA-CD also works better with large packets, as once connection is established, the throughput is greater (although this does have the disadvantage of reducing other packets' responsiveness).

Another way of solving the problem is to use collision avoidance, where it is agreed in advance when the sender has sole access to the network. Some ways of implementing this include:

• Time Division Multiplexing - have an agreed time slot for a message (this does have the requirement of global time, however)
• Frequency Division Multiplexing - frequency range of wireless communications split into bands, each user having exclusive access
• Wavelength Division Multiple Access - like FDM, but for fibre optics and at the visible area of the spectrum
• Spread Spectrum (frequency hopping) - this is used to prevent jamming, where the frequency changes according to a system only the sender and receiver know

Ethernet (IEEE802.3)

Controller Area Network

Broadcast and point-to-point networks are good for message passing as they are connectionless, but they are less good for streaming applications (e.g., transmission of video/sound data streams). Switched networks are better for connection orrientated requirements, as well as many WAN applications and streaming applications.

In switched networks, all computers are directly linked to the swich (i.e., computers are not linked directly to one another), and switching is used to transmit information between two nodes which do not share a direct link.

Packet switching is worked by placing computers at each switching node. Basic processing and storage is made available, and "store and forward" networks (where packets are forwarded from source to destination when a link to the destination becomes available) are now possible. A permanent connection is established between each node and the switch, and to send a packet from A to B, the switch determines when the packet is forwarded to B. Switches can also switch between different types of physical networks.

One way of implementing switch networks is using source routing, where each packet has enough info to enable any switch to decide how to get the packet to its destination - overheads are expensive as the full route must be known beforehand and must be embedded in the packet being sent.

Another method is virtual circuit switching. VC switching is similar to a phone call, where there is an explicit setup and tear-down stage, so all packets for that connection follow the same circuit. This is sometimes called a connection-orrientated model. Each packet contains a VCI (virtual circuit ID) which is then reassigned by each switch for the next VC switch based on a VCI table. Switches here are complicated, and timing guarantees are difficult. Only the connection request needs to contain the full destination address, and as the VCI tends to be smaller than the connection address, the per-packet overhead is small.

Due to the setup time, you generally have to wait a full round trip time (RTT) for connection setup before sending the first data packet, so this is inefficient for short or bursty packets. Additionally, if a switch or link in the connection fails, the connection is broken and a new one needs to be set up.

The connection set up does provide an opportunity to reserve resources, however (this is important if Quality of Service is a prime requirement for applications)

Another method is datagram switching. Here, there is no connection set up phase and each packet is forwarded independently, so the model is completely connectionless, and is analogous to the postal system. Each switch maintains a forwarding (routing) table which maps host to port, therefore a switch needs to know which port to send a packet on to reach its desired host.

In this model, there is no RTT delay waiting for the connection setup; a host can send data as soon as it is ready. However, the source host has no way of knowing if the network is capable of delivering such a packet, or if the destination host is even up or available. However, as packets are treated independently, it is possible to route around link and node failures. Every packet must contain the full address of the destination, so the overhead per packet is higher than for the connection-orrientated model.

Hubs act at a physical layer and are basically multi-port repeaters. They perform no routing (so are only useful in broadcast networks) and simply receive and send onwards. They can help reduce effects such as SNR, but can increase collisions. Hubs act at the physical layer and join network segments.

Bridges act at the data-link layer and connect two or more network segments or LANs (however, they must be of the same type). They have an accept-and-forward strategy, and perform a basic level of routing. They usually do not alter a packet header.

A key issue is that we must ensure that we forward a packet to the correct LAN. The simplest way to implement this is to use fixed routing - this is where a route is assigned for all source/destination pairs, so is only usable in small networks. The selected route is usually the one with the fewest hops, but problems can be encountered if the network changes or new machines are added.

Learning bridges work by having a routing table and entries in this are learnt from the source address, and is effective if we have a tree network topology. In learning bridges, we only forward if necessary, so unnecessary traffic is not created on segments or LANs. The algorithm for learning bridges is such that when a frame arrives on a port P at the bridge, it must have come from the direction of a sending LAN, so we examine this source address S. We then update the forwarding table to reflect that to send messages to destination S, we forward it to the LAN connected to port P. Each entry in the forwarding table is then timestamped to enable entries to be deleted after a fixed time - this enables the table to reflect changes in network topology (e.g., S could move from port 1 to port 2 and the bridge would learn this next time S sends a message).

In learning bridges however, we have the problem of network loops causing messages to arrive at a bridge from multiple directions, which causes the route table to oscillate. To solve this, we can use a simple result from graph theory: "for any connected graph, consisting of nodes and edges connecting pairs of nodes, there is a spanning tree of edges that maintains the connectivity of the graph but contains no closed loops".

To implement this, we have bridges running a distributed algorithm to find a spanning tree. An attempt is made to find the best tree (with respect to number of hops), and the topology is not know before running the algorithm. The algorithm is that each bridge has a unique ID, and each port on a bridge is assigned a cost (sometimes the same cost for each port, and is usually factors such as bitrate supported by a port). The bridge with the smallest ID is the tree root. The number of hops is initiallised to 0.

The bridges then need to find the root bridge, so all bridges circulate messages containing their ID and the number of hops. When a bridge receives one of these messages, if the ID is lower than its own message, or the ID is same but has a lower cost, it adds one on to the hop count and forwards the message on, stopping sending its own message, as it has identified another bridge that could be the root, or a faster route to the root, otherwise the message is discarded. Eventually, only messages from the root bridge will be circulating, and all other bridges should have backed off as their ID/cost is higher. Loops are therefore avoided, assuming that all identifiers are unique.

Each bridge will then determine its root port (i.e., port with least cost to root) and a dedicated bridge is chosen for each LAN. Where a LAN has more than one bridge, the bridge sends messages to other (external) bridges on the same segment (this is achieved by no bridge forwarding a message to another LAN), and the message contains the cost to root for each bridge. The bridge with the smallest cost to root is then chosen as the designated bridge (i.e., fastest route from bridge up the tree chosen).

This algorithm results in that one bridge on each LAN is selected as the designated bridge, each bridge forwards frames over each LAN for which it is the designated bridge. This is still a learning-style algorithm, but there are no loops.

Bridges do have the problem of not scaling, as the spanning tree algorithm does not scale, and having a single designated bridge can be a bottleneck. Additionally, it does not accomodate heterogeneity (bridges make use of frame headers, so they can only support networks with the same format for addresses). Additionally, different MTUs can cause problems.

We can think of switches as multiport bridges.

Switches solve the problem of static network topologies dictated by attempts to minimise wiring, so switched networks provide flexible architecture for networks. Switches allow packets to traverse point-to-point WANs from source to destination, and are fundamental for WANs.

Recently, switches have also become cost effective for LANs, as they allow the ability of a local LAN to have effective total connectivity between nodes, and provide fast communication and less contention. The advantages are that whilst wiring is still based on physical demands (i.e., computer is connected to the closest switch), LANs can be configured logically (usually in software).

LAN switches are strictly switching hubs, and switch between single LAN types. They are termed level 2 switches (from the OSI model), as the inspect packets at the frame level by looking for the MAC address. They can be implemented as store-and-forward switches, where the incoming frame is buffered briefly before being routed, which allows the number of switches to be less than the number of ports (although this has a performance hit), or cut-through switches, where an incoming frame is routed as soon as the MAC address is received (usually at the front of the frame, e.g., in Ethernet). This can lead to propogation of faulty frames, as the sending frame is forwarded before the CRC is checked.

Routers are capable of providing interconnects between different sorts of LANs and WANs.

ATM stands for asynchronous transfer mode and is a connection-oriented packet-switched network. It was developed by and for the telecoms industry and was originally designed for WAN, although it is now used in LAN settings. It is a IEC standard.

ATM requires the setting up of a virtual circuit before transmission can start, and connections are identified by a two-level hierarchy consiting of a VCI (virtual circuit identifier) giving the route across switches from source to destination and a virtual path identifier which identifies a set of inter-switch routes. A combination of VCI and VPI can be thought of as a virtual circuit in packet switched network terminology.

The ATM model is a three-level model consisting of an ATM Adaption Layer (AAL) which adapts information to be sent to the cell structure (i.e., creates packets or cells for, e.g., specially dealing with voice), an ATM layer which is responsible for multiplexing and switching packets (or cells) and a physical or adaptation layer which is responsible for adapting to the underlying transmission media.

Packets in ATM are called cells and are made up of a 5-byte header and a 48-byte fixed length payload.

• GFC - generic flow control
• VPI - virtual path identifier
• VCI - virtual circuit identifier
• Type - mangement, congestion control, AAL, etc (AAL 1 and 2 for applications that need a guaranteed data rate, 3 and 4 for packet data and 5 as an alternate packet data standard)
• CLP - cell loss priority (when network is overloaded, packets of a lower priority are lost first)
• HEC - header error check

Fixed length packets are easier to switch in hardware, and enables hardware switch parallelism as variable length packets inevitably require software to process them. When deciding what length to use, there is no optimal, as small packets have a high header-to-data overhead and large packets have an underutilisation problem. Small packets do improve latency (especially important for voice), e.g., if sound is recorded at 64 kbps and a cell was 1000 bytes long, you would need to wait 125 ms before a cell was full, which is too long for voice. ATM was a compromise of Europes desired 32 bytes and Americas desired 64 bytes.

With ATM there is a problem of congestion if the rate at which things are being put into the queue for the output ports is close to or greater than the maximum data rate of the output port. Recognising congestion can take time, so it is often better to try to prevent congestion rather than react to it. Ways of avoiding congestion include:

• Admission Control - this is used to decide whether or not a request for a new connection is allowed, and once this is set up all parties have some knowledge of likely data rates along the connection
• Rate Policing - this controls flow into a network across a channel to be regular, using a "leaky-bucket" algorithm (i.e., buffer packets and release at a regular rate). This transforms a bursty data arrival into a regular drip of packets into the network, speading the load. This is usually matched to an agreed data rate set up by admission control

However, if congestion still arises in physical networks, we can use the CLP byte to shed low priority traffic.

The ATM model does not easily map on to the OSI and TCP/IP models, as ATM has characteristics of end-to-end VCs, switching and routing, which occur at OSI levels 3 and 4, but the TCP/IP view is that ATM sits at levels 1 and 2, which enables them to place IP over it, however ATM does not have the characteristics of a single hop data-link layer, and it needs messages to be split and reformed which IP does not support.

We can try and represent how ATM fits into the OSI model below, however:

OSI Layer	ATM Layer	ATM Sublayer	Functionality
3/4	AAL	CS	Providing the standard interface (convergence) (TCP, UDP and IP would go between these layers)
		SAR	Segmentation and reassembly
2/3	ATM		Flow control Cell header generation/extraction Virtual circuit/path management Cell multiplexing/demultiplexing
2	Physical	TC	Cell rate decoupling Header checksum generation and verification Cell generation Packing/unpacking cells from the enclosing envelope Frame generation
1		PMD	Bit timing Physical network access

In classful routing, there are 5 classes of addresses, named A-E, however D addresses are reserved for multicast, which is rarely used on the modern Internet and class E addresses are reserved. A class can be identified by its leading value, and classes differ by how many bits the network number and host numbers use.

Class	Leading Value	Bit length of network number	Bit length of host number
A	0	7	24
B	10	14	16
C	110	21	8
D	1110	N/A	N/A
E	1111	N/A	N/A

Choices over which class an organisation is supplied are assigned based on how many hosts are anticipated to be used in the network, and within classes, ranges were assigned geographically (e.g., 144.x for the UK, etc).

The original intent of classful routing was to have the network part of an IP address would identify exactly one network. However, for every network under 255 hosts, a class C was needed, and for over 255 hosts, a class B. This can lead to a large wastage, a class C with 2 hosts is only 0.78% efficient, and a class B with 256 hosts is only 0.39% efficient. Additionally, there were still a lot of networks, and route propagation protocols do not scale well.

Subnets add another level to the address/routing hierarchy, as subnet masks are used to define a variable partition of the host part. The mask reveals the subnet number which is part of the IP address to be compared with the routing table entry, this is more flexible than classful address space, as it allows a greater break up of addresses and more efficiency.

Forwarding is selecting an output port based on the destination address and the routing table, and routing is the process by which the routing table is built.

The easiest way to represent a network for routing is as a weighted graph, and we then have the problem of finding the lowest cost path between two nodes. Factors to consider include static factors such as topology and dynamic issues such as load. A simple solution is to send the packet out on all interfaces except the one it came in on, this is guaranteed to reach the destination in the shortest time, but causes congestion, duplication, etc...

We can use metrics to measure network performance. The original ARPANET metric measured the number of packets queued on each link, and took neither latency nor bandwidth into consideration. A new ARPANET metric was developed to combat this, where each incoming packet is stamped with an arrival time (AT), and the departure time (DT) is recorded. When a link-level ACK arrives, the delay time is then computed as Delay = (DT - AT) + Transmit + Latency. If a timeout occurs, DT is reset to the time the packet was retransmitted, and the link cost is the average delay over some time period.

RIP (Routing Information Protocol) can be used to compute a distance vector. Each node contains a set of triples (Destination, Cost, NextHop), and exchanges updates with its directly connected neighbours, either periodically (typically in the order of several seconds) or whenever the table changes (called a triggered update). The updates are in a form of a list of pairs (Destination, Cost), and if a route appears to be better (i.e., have a smaller cost), the local table is updated with the new NextHop. Existing routes should be refreshed periodically, and delete if they time out.

When subnetting is used, the routing algorithm changes, however. The entries are now of the form (SubnetNumber, SubnetMask, Cost, NextHop). A binary AND is performed on the IP and the subnet mask, and then it is seen whether or not it matches the subnet number, and if it is, forwarded on to NextHop.

Problems can occur with loops and failures, however, where an out of date node publishes information about a link that goes down to NextHop, and the node decides it can reach the failed node through the out-of-date node, causing an infinite loop. To break these loops, we can do things such as set "infinity" to an arbitrary number, such as 16, or use a split horizon, where routes learnt from a neighbour are not sent back to that neighbour.

To solve the problem of extremely large routing tables, interdomain routing is used. Here, networks are parts of autonomous systems (AS), which correspond to an administrative domain. They are autonomous as what happens inside an AS doesn't affect the outside. Route propogation now uses a two-level hierarchy, with an interior gateway protocol to speak to other nodes inside the network, and an exterior gateway protocol (i.e., BGP is an Internet wide standard) to talk to neighbours (or peers) of the AS.

EGP (the exterior gateway protocol) was previously used on the Internet before being replaced by BGP (border gateway protocol). It is designed for a tree-structured Internet, and is concerned with reachability, not optimal routes. The protocol consists of messages for neighbour acquisition (one router requests that another be its peer, and peers then exchange reachability information), neighbour reachability (one router periodically tests if another if still reachable, by exchanging HELLO/ACK messages, and a k out of n rule is used) and routing updates (peers periodically exchange their distance-vector routing tables).

Constraints in routing are varied, and normally have to be programmed into routers manually.

BGP4 is the current version of the border gateway protocol used on the Internet. BGP4 has 4 AS types:

• stub AS - has a single connection to one other AS, and carries local traffic only
• multihomed AS - has connections to more than one AS but only carries local traffic; it does not allow transit between peers across its network
• transit AS - has connections to more than one AS, and carries both local and transit traffic

Each AS has one or more border routers, and one BGP speaker that advertises its local networks, other reachable networks (in the case of transit AS) and gives path information.

IPv6 features completely classless 128-bit addresses. The address contains host "subnet" details and a specific address. It works around the fragmentation problem by using a method called "end-to-end" fragmentation, where once sent, no further fragmentation can occur, as the minimum MTU on route is determined prior to the send (either by using path discovery, or default to a minimum MTU - 1280 bytes). It provides many services such as real-time (using priority field in the header), multicast and anycast (ensuring delivery to at least one set of nodes). Security can also occur at the IP layer via authentication and an encrypted payload.

The header is 40 bytes long, with extensions (fixed order, with a mostly fixed length). The type of extensions are indicated by a "next header" field, and contain information such as routing or fragmentation information.

Currently, IPv6 is implemented on top of the current IPv4 network using a method called tunneling. Tunneling is a transmission of packets through an alien network (in this case IPv4), but where both the sender and recipient speak a common protocol. The sender encapsulates an IPv6 packet within an IPv4 packet and sends it, however fragmentation may be necessary. It is effectively a software layer.

UDP, the user datagram protocol, is an unreliable and unordered protocol based on the datagram idea. It extends the unreliable host-to-host service to a process-to-process level, it consists of no flow control and has a simple header format, with an optional checksum.

Both UDP and IP provide a connectionless unreliable interface, and the only thing UDP offers IP is the idea of a port interface. However, UDP is service-oriented and removes the need for the sender to know much about the receiver/network topology, which hosts should not know for transparency reasons.

TCP, the Transmission Control Protocol, provide a connection-oriented transport. It is full-duplex and point-to-point and has flow control, to keep the sender from overrunning the receiver, and congestion control, to keep the sender from overrunning the network.

TCP uses the concept of a reliable byte-stream. Applications read and write bytes, but TCP sends and receives segments and the translation between the two is done using buffers. It has the same port concept idea as UDP and is similar in concept to ATM.

TCP needs to address end-to-end issues, as it can potentially connect many different hosts, so explicit connection establishment and termination is required. Additionally, it must deal with problems that can be introduced at the network layer, such as potentially different round trip times (RTT), so an adaptive timeout mechanism is needed; or long delays in the network, so we need to be able to handle the arrival of very old packets; or different capacity at the destination compared to the source or on the network, so we need to be able to deal with congestion and capacity issues.

Connections in TCP are established by a three way handshake. Initially, a server is listening for client connection requests (CR), then, when a client issues a CR, then the server checks if a server is listening on the selected port and sends an ACK if it is. The ACK indicates next data is expected, so the client acknowledges the connection and synchronises sequence numbers in the first data segment that is sent out.

The TCP model has a state diagram which indicates which particular state the communication is in at any one time. In addition to opening the connection, connections are ended by either end sending a segment with the FIN bit set in the header.

TCP considers flow control, which is important as both senders and receivers have a finite buffer space, and they process data at different rates. A sliding window protocol is used to provide flow control. Here, a time window of connections can be established and messages sent. It is possible to deal with out-of-order arrival of segments and to have multiple outstanding (un-ACKed) segments in the time window. The upper bound of un-ACKed segments sets the window size, and this limits the amount of buffer space required at the sender and receiver. Having a bigger window gives us more flexibility, but increases the risk of more failures remaining undetected.

Flow control is implemented on the sender to bound failure detection, i.e., where a message is not acknowledged sufficiently quick enough. A sequence number is assigned to each frame, and three state variables are maintained - SWS (send window size), which is the maximum number of unacknowledged frames the sender can transmit, LAR, the sequence number of the last acknowledgement received and LFS, the sequence number of the last frame sent. We must then maintain the invariant LFS - LAR ≤ SWS.

When an ACK arrives, we advance the LAR pointer, but we must retransmit the frame if an ACK is not received within a given time. As we need to buffer up to SWS frames, this means the transmission failure detection time is bounded.

To support out-of-order receives and reject out-of-date messages, the receiver must also implement flow control. Here, three state variables are maintained, the receive window size (RWS), the largest frame acceptable (LFA - basically, how many messages make up the largest allowed frame), and LFR, the last frame received, but not delivered. An invariant LFA - LFR ≤ RWS must be maintained.

When a frame with sequence number S arrives, if LFR < S ≤ LFA, then we accept, else if S ≤ LFR or S > LFA, we discard. Cumulative ACKs are sent, e.g., if we receive segments in the order 7, 8, 6, then we wait until 6 arrives before acknowledging 7 and 8. The LFA does define a limit, however, e.g., if 11 is received before any other packets, then it may be rejected. The buffer supports up to RFS frames.

Flow control allows us to deal with errors. e.g., if RWS = 1, then after an error, subsequent frames are discarded, so the sender must go back N frames and repeat them. N is decided mainly by network delay. If RWS > 1, then after an error, subsequent frames are buffered, and the sender selectively repeats the missed frame. This is a trade off between bandwidth required and the buffer space required, and typically, the larger the transmission delay and likely errors, the larger the buffer that is needed.

Sliding window and flow control is implemented in TCP using the Acknowledgement, SequenceNum, AdvertisedWindow and Flags fields. The AdvertisedWindow field in the header defines the window to be used for transmission.

ACK messages consist of the acknowledged sequence number in the Acknowledgement field, and in the same message, a new AdvertisedWindow can be sent. The AdvertisedWindow tells us how many more bytes can be sent than those already received/acknowledged.

A problem with TCP is that of a 32-bit sequence number, which is limited given current network speeds, and it is only a matter of seconds in gigabit networks until sequence numbers start to repeat. We need to ensure that the network is well utilised, which has implications on window size. A 16-bit AdvertisedWindow means we only have 64 kbytes before wraparound. To work round this, TCP has been given the option of a scaling factor to cope.

A final problem to consider in TCP is that of retransmission (from the sender) of unacknowledged segments after some timeout has expired. This requires a timer, but there is the problem of knowing which value to use. A fixed value needs knowledge of network behaviour and does not respond to changing network conditions - too small and the network is flooded with retransmission, and two large and the receiver will stall. Another method is using an adaptive timer, however it is still difficult to monitor RTT with cumulative acknowledgements, and network conditions may change faster than we can adapt.

Adaptive retransmission does still tend to be used, however. One method involves using a weighted average, where a SampleRTT is measured for each segment/ACK pair, and a weighted average (basically a balance between actual and expected RTT) is computed: EstRTT_{t + 1} = α × EstRTT_t + β × SampleRTT, where α + β = 1. Typically, 0.8 < α < 0.9 and 0.1 < β < 0.2. Timeout is then set based on this RTT, and is typically twice the value.

This weighted average gives quite a large timeout when the network is relatively stable, however. Another solution is the Jacobson/Karel algorithm, where the mean deviation of actual RTTs from the estimated RTTs is used.

Diff = SampleRTT - EstRTT
EstRTT = EstRTT + (δ × Diff)
Dev = Dev + δ (|Diff| - Dev)

Where δ is a factor between 0 and 1.

Variance is then considered when setting a timeout value: Timeout = μ × EstRTT + φ × Dev, where μ = 1 and φ = 4.

This algorithm is only as good as the granuality of the clock (500 ms on UNIX), and μ, φ and δ are used to control the speed of response and the ability to adapt.

The Karn/Partridge algorithm tells us not to sample the RTT when we retransmit, as the subsequent ACK may be from the original transmission, just late, so the timeout value becomes distorted. In this algorithm, the timeout is multiplied by a constant after each retransmission (often 2), which progressively gives the network longer to get a message through. When an ACK is received for a segment that has not been retransmitted, Jacobson's algorithm is used to set a timeout.

This bit is wrong, but is
what the lecture slides
say, so use it for the exam.

URLs (uniform resource locators) are direct links to host and IPs (e.g., pisa.cs.york.ac.uk) and can scale to a limitless set of web resources. It does have the problem of web dangling references, however - if a resource moves, the URL is invalid.

URNs (uniform resource names) solve the dangling link problem, as URNs persist, even if the resource moves. The resource owner registers it with a URN lookup service, which provides the current URL when asked - if a URL changes, the owner must inform the URN lookup service. URNs identify a namespace and a resource, e.g., urn:cs.york.ac.uk/RT2001-2 identifies the resource RT2001-2 in the namespace cs.york.ac.uk. URNs also identify a scheme, e.g., http, ftp, etc...

A name space is a collection of all valid names in a given context, e.g., for a file system, the context might be a directory and the valid names are strings that follow a certain pattern (e.g., printable characters no longer than 255 characters). A valid name does not necessarily map to an existing entity (e.g., a file with a given name may not necessarily exist in that directory).

Flat name spaces (i.e., where everything is in a single context) are usually finite, but hierarchial namespaces are possibly infinite by allowing recursive contexts.

Name resolution is an iterative process used to map names to primitive attributes, or to derive a name to be passed on to another name service (e.g., an aliased name may first be translated to another name, then to a reference for the actual resource). Aliases can lead to circularities, so it is often necessary to implement around cyclic lookups.

The name service for a large number of names should not be stored on a single computer, as this is a bottleneck as well as a single point of failure.

Partitioning of a name service requires a structure so that names can be resolved efficiently. This process of finding naming data within the split name service is called navigation. In iterative navigation, a client nameserver presents a name to NS1, which will resolve all or part of a name, and suggests that a further nameserver can help, if required.

To resolve a name in the DNS, e.g., milan.cs.york.ac.uk, we first contact the root nameservers which gives the address of the nameserver for .uk, which in turn gives us the address for the nameserver for .ac.uk, which gives us the main York nameserver for york.ac.uk, which we can ask for the cs.york.ac.uk nameserver, which will finally give us the address of milan.

This co-ordinated resolution can involve recursive or non-recursive navigation. This is the opposite to iterative navigation, which is client controlled, but this is server controlled. In non-recursive, the root nameserver does all of the lookups, whereas in a recursive setup, each server contacts the upstream servers and passes the results back.

The DNS name space is partitioned organisationally and geographically, e.g., milan.cs.york.ac.uk identifies the server milan in the Computer Science department of the University of York, which is an academic institution in the UK. Components are seperated by dots and it is case-insensitive.

DNS supports host name resolution (A records for IPv4 and AAAA records for IPv6), mail host locations (MX records), aliases (CNAME records), reverse lookups (IPs to hostnames with PTR records), etc, and typically uses the iterative lookup mechanism.

Most DNS servers use caching to increase performance, which helps in availability of name service data if a nameserver crashes. DNS records are accompanied by a TTL (time to live), which tells the cache how long to cache the record for before refreshing. We call responses from caches to be "non-authorative", as they may not be accurate and are out-of-date. An authorative server is the name server that actually manages the zone records for that domain name, and this server needs to intelligently manage the TTL to balance between load and accuracy.

DNS clients are called resolvers and are often implemented in the OS as a library function.

Software such as Jini provides facilities for service discovery, and are called lookup services. Lookup services allow servers to register the services they provide, and then clients query the lookup service for the required service. Infrastructure then provides an appropriate interface to a server via remote method invocation (RMI).

Lookup services should also be able to control the services that different users (e.g., visitors) can access.

In the above example, a client requires a lookup service in the finance group, so it sends out a broadcast, to which the lookup service for that group responds. The client then communicates with the lookup to request printing. As only one printing service is registered for the finance group, the address of it is given to the client for direct communication to the printing service.

Heterogeneity - Networks require standard communications protocols, hardware may vary (data types, e.g., length of an int may be implemented differently or big endian vs. little endian), OSs may provide varying implementations of network protocols and programming languages may not be implemented on some architectures (common languages e.g., Java and C tend to be used).

Openness - This determines whether or not the system can be extended or partially re-implemented. Open distributed systems enable new services (by adding new hardware and software) to be added for use by clients. Documentation of the interfaces is required for this. It is hard to design and support a system if you have little knowledge or control over how it is used or modified.

Security - Many services have high value to users. Often, secure data is passed across public networks. There is a need to ensure the concealment of the content of messages and that the identity of the client can be determined by the server (and vice versa). Common security problems include denial-of-service attacks and the security of mobile code.

Scalability - Requires that the system is still usable if many more computers/resources/services are added. Scalability requires the system to control the cost of physical resources, control performance loss, prevent software resources running out and to avoid performance bottlenecks.

Failure handling - Network partitions and computer systems fail producing incorrect, or no results. You need to detect, mask, tolerate and recover from failures. Requirements can include Mean Time Between Failures (MTBF), availability and amount of unscheduled maintenance.

Concurrency - Services and applications provide resources that are shared in distributed systems, hence shared resources can be accessed simultaneously. Operations must be synchronised to maintain data consistency.

Transparency - Concealment from the users and applications of seperation of componenets of a distributed system. We can consider different forms of transparency.

Transparency	Description
Access	Hide differences in data representation and how a resource is accessed (network transparency)
Location	Hide where a resource is located (network transparency)
Migration	Hide that a resource may move to another location (distribution transparency)
Relocation	Hide that a resource may be moved to another location whilst in use (distribution transparency)
Replication	Hide that a service may be replicated for fault tolerance and performance (distribution transparency)
Concurrency	Hide that a resource may be shared by several competitive users (distribution transparency)
Failure	Hide the failure and recovery of a resource (distribution transparency)
Persistence	Hide whether a software resource is in memory or on disk (distribution transparency)

Performing all file operations on a remote server increases network traffic and decreases performance because of network delays, so recently used data or directories is cached locally for repeated access. The size of a cache unit is normally the same as the block unit for transfers, and as larger block sizes means lower network overheads.

The cache location is either on the client or the server. If we cache on the client size, local disc tends to be non-volative and have a large size and main memory is faster, smaller but volatile, however they are both difficult to maintain consistency for writes whilst having a low network load. However, if we cache on the server side, in memory there is faster I/O, no consistency problems, more memory is typically available than in a client, but it is volatile and network load increases.

It is difficult to maintain file consistency when caching, and there are three cache flush policies, write through to server (information is written to the cache and server in parallel, which is reliable, but has poor write performance), delayed write (periodically, or when cached block is discarded by the cache replacement algorithm, multiple blocks are bulk written, but there is ambiguity for other file readers) and write on close (but there is a problem if files are open for a long term). The choice depends in importance of consistency and usage patterns.

The Sun NFS is the most famous implementation of a network file system and consists of a collection of protocols that provide clients with a model of a distributed file system and is based upon RPC. It provides one-copy semantics for consistency, where updates are written to the single copy and are available immediately, and is similar to a local file system, based on the concept of delegation. It does have to cope with network, server and client failures.

Access to the servers files is via the NFS server and the flat file server. The virtual file system helps map to actual UNIX file system. The NFS allows transparent access to the remote filesystem, where the server exports all or part of a filesystem, and the client mounts all or part of it into the clients filesystem.

Name resolution becomes iterative, which increases network traffic. In some ways, it would be better to have recursive name resolution, but this has a higher load on the server.

NFS implements server-side caching with read-ahead and write-behind caching in the main memory. Client-side caching works by each client having a memory cache containing data previously read from a file, and the server may delegate some rights to a client. This delegation may be recalled if another machine contacts the server to access the file. The server must keep track of which file it has delegated, and to whom.

Cache validation checks whether the client copy is still valid (e.g., whether or not the TTL has expired), or whether the server copy been updated. This is quicker than updating the file. Modification and validation timestamps are used, along with a freshness interval, which is set adaptively, depending on frequency of file updates. This could be 3-30 seconds for files, or 30-60 seconds for directories.

Synchronisation of files is difficult in distributed file systems if caching is used. To solve this, we have multiple options, such as propogating all changes to server immediately (which is inefficient), or using session semantics (changes to open files visible to the modifying process immediately, and only when the file is closed are changes made available to others. NFS adopts session semantics so consistency could be a problem. Concurrent access to files does remain a problem, and issues include preventing more than one simultaneously attempt to write to a file, so file locks can be used.

NFS was developed on SunRPC, which uses at-least-once semantics, so NFS implements a duplicate-request cache, so each RPC contains a unique identifier which is cached. If a call is still in progress when a duplicate request arrives, it is ignored, which gives a combination similar to at-most-once semantics. The difference is the acknowledgement the client has when the result has been received.

File locks can be used, which allow one writer and multiple concurrent readers. To lock a file, special lock commands can be used. However, we need to consider what happens if a client crashes whilst holding a lock, so the server issues a lease on each lock, and when it expires the lock is removed automatically by the server. A renew() command exists which requests that the lock is renewed. However, if the server crashes, the server will probably lose information on locks granted to files, but when it reboots, the server will enter a grace period where clients can reclaim locks previously granted. During the grace period, only claims for previous locks will be accepted - i.e., no new locks. The leasing approach does require the client and the server to have reasonably synchronised clocks.

Delegation also causes problems when a failure occurs and a cache isn't written back - full recovery is impossible, unless the cache is persistent. The NFS places responsibility on the client for providing file recovery (which is very difficult). If the server crashes, delegations are allowed to be reclaimed during the grace period. In general, mechanisms used for caching are highly dependent of the needs of the system and future characteristics.

We can compare the criteria for distributed file systems to Sun NFS:

• Access Transparency - The UNIX API provides the same interface as the VFS
• Location Transparency - NFS does not enforce a network-wide namespace. Therefore, different machines may mount different combinations of remote filesystems.
• Migration transparency - Not fully achieved in NFS as mount tables must change if file changes filesystem
• Scalability - Yes
• File Replication - Not supported
• Fault Tolerance - Similar to local files, but some differences due to distribution
• Consistency - One-copy semantics

IrDA is an infrared based standard started in 1993 based upon that used by TV remote controls. It is of limited range and of line of sight only.

The standard provides a data link layer, which is essentially a wireless serial link ranging in speed from 9600 bps to 4 Mbps. The key motivation behind IrDA was to "provide a low-cost, low-power, half-duplex, serial data interconnection standard that supports a walk-up, point-to-point user model that is adaptable to a wide range of applications and devices" - that is, it provides a convenient wireless point-to-point link. Many protocols are available to run on IrDA.

Bluetooth is meant to unite the worlds of computers and telecoms. It is based in the ISM 2.4 GHz RF band with ranges from 10-100 m. It defines its own protocol stack which doesn't map on to either the OSI nor TCP/IP model. It can cope with devices moving in and out of range by broadcasting periodic "I am here" messages to establish neighbours.

Non-standard protocols need to be used to access a LAN, and Bluetooth is often not standardised across multiple manufacturers, and problems can occur implementing it.

The wireless Ethernet standard is defined in IEEE 802.11a, b and g, with a and b being incompatible, but g is backwards compatible with b. In IEEE 802.11b, devices can communicate at up to 11 Mbps over distances of up to 150 m and can communicate both in an ad-hoc/peer-to-peer system directly with other devices or in a more structured way with an access point.

Wireless Ethernet differs from standard IEEE 802.3 Ethernet in the implemenation of MAC and the CSMA/CS mechanism. There are still equal opportunities for all to transmit, but the MAC controls use of the transmission channel, with both added security (WEP/WPA) and slot conditions. Additionally, a fairly consistent signal strength is required through the network to detect interference and collisions (i.e., another sender), and there are more failure conditions than in wired LANs.

Hidden stations are when a failure to detect that another station is transmitting occurs. Additional problems include fading as a signal may not be heard by all nodes in the network, but is by the base station. Additionally, collision masking is not effective in wireless, as multiple transmitters may produce garbled messages. As the frequency band used by wireless Ethernet is ISM, it is shared with devices such as Bluetooth and microwave ovens so interference can occur.

MAC is augmented by slot reservation. Before sending, the receiver agrees a transmission slot and when you are ready to transmit, you sense the medium, and if there is no signal, then the medium is either available, or there are out of range stations requesting a slot, or using previously reserved slots. To request a slot, the sender sends a request to send (RTS) packet with the duration, and the receiver acknowledges this with a clear to send (CTS) packet with the duration. All stations in the range of the sender and receiver therefore know about the slot, and the sender can send with a minimal risk of collision.

This gives us a mechanism called CSMA/CA (collision avoidance), but there are still problems with nodes moving.

Many devices connect at different locations so do not want a static IP address allocated. DHCP (Dynamic Host Configuration Protocol) enables a temporary IP address to be acquired, but there are still difficulties if you want to stay connected whilst moving between networks.

IP routing is based on subnets at fixed locations, however mobile IP is based on the idea of an allocation of an address in the "home" domain. When the hosts move, routing becomes more complex. A home agent (HA) in the home domain and a foreign agent (FA) in the current domain perform routing. The home domain currently routes for the sender and the foreign domain takes over hosting sender.

When a mobile host arrives at a new site, it informs the foreign agent and a temporary "care-of" address is allocated. The FA then contacts the HA of the host with the new "care-of" address. The sender communicates with the HA initially and then it is told the "care-of" address. "Care-of" addresses do timeout.

In the router of the HA, a mobility binding table is maintained on the home agent of the mobile node, and the mobile nodes home address is mapped to its current care-of address along with a lifetime. The FAs maintain a visitor list which maps the home address and HA address to the MAC address, along with the lifetime.

HAs then use IP tunneling and encapsulate all packets addressed to the mobile node and forward them to the FA. The FAs then decapsulate all packets addressed to them and forwards them to the correct node using the hardware lookup table. Mobile nodes can often perform FA functions if it receives an IP address (e.g., via DHCP). Bidirectional communications will require tunneling in each direction - this is analogous to IPv6 over IPv4 networks.

Mobile IP implements security using authentication. All parties can authenticate, but the bare minimum is that between the mobile node and the HA. Authentication uses MD5 (a 128-bit digest of the message) for added security. To protect against replay attacks, timestamps are mandatory, and sequence numbers must be unique. Unique random numbers are also generated in requests to join network that must be returned in the reply. The HA and FA do not need to share any security information.

Mobile IP has the problem of using suboptimal triangle routing, where if the mobile node is in the same sub-network as the node in which it is communicating, it could be very slow to route via the HA. It would be an improvement if packets can be directly routed. To do this, foreign agents let the corresponding node know the care-of address of the mobile node, and the corresponding node can create its own tunnel to the mobile node. This does require special software, however. The HA must initiate it with the corresponding node via a "binding update", and binding tables can become stale.

Other problems with mobile IP include redundancy problems (single HAs are fragile - so we have multiple), and frequent reports to the HA if the mobile node is moving, of which a possible solution is to cluster FAs. Security is also always a concern when data travels over untrusted networks.

IPv6 implements mobile IP in the standard, so FAs are not needed; whereas mobile IPv4 is a set of extensions that must be supported by all nodes to work. With mobile IPv6, mobile nodes can function in any location without the services of a special router as IPv6 uses stateless address auto-configuration, that is, DHCP. Home agents do still need to be told by the mobile node where it is. Additionally, with security, nodes are expected to employ strong authentication and encryption.

Originally, data and phone networks were seperate each having different requirements. As networks grew, a greater need to carry data over telecom networks developed and the issue was how to carry data over telecoms networks. Currently, data is the majority of telecom traffic, so new telecoms networks being installed are data networks, and the issue shifts to being how to carry voice over data networks - the solution being to encode voice as data.

VoIP has many issues to be considered, such as user location, setting up a connection and real-time and QoS (quality of service) issues. Provision of QoS is difficult, as it is difficult to map the users' view of quality into the network stack - arguably no layers implement QoS, although some may provide a higher quality service. QoS is difficult to achieve with a limited network capacity, and all parts of the network must cooperate to provide QoS.

An implementation of VoIP is SIP - session initiation protocol, which provides a general means of negotiating a connection. SIP URLs act as locators, and users register with a local server, which permeates outwards to location servers and proxy servers so that callers can be routed to the correct hosts. Proxies then communicate together and route data onwards; however they must keep an up-to-date cache of these locations to do this.

The actual transmission protocol used is RTP for the message data (i.e., the voice) which has some QoS. RTP is a transport layer running on top of UDP. RTP headers include timing information which allows applications to specify acceptable loss rates and react accordingly, e.g., change encoding rate to reduce traffic.

RTP does rely on a network that is capable of delivering packets on time, and to maintain timeliness, we degrade the quality delivered. Networks are generally poor at delivering packets on time, so prioritisation ("traffic shaping") and reservation of bandwidth are usual methods for dealing with the problem (e.g., ATM). Variability in communication times can be significant and hence cause problems.

Wikipedia article on
the MSF time signal

The key time source is universal co-ordinated time (UTC), which is based on atomic clocks, but leap seconds are inserted to keep in phase with astronomic time. Radio stations (MSF in the UK) broadcast UTC as an encoded time signal. Atmospheric disturbances mean that land-based UTC sources have an accuracy of ± 10 msec. GEOS (Geostationary Environment Operation Satellite) or GPS signals provide UTC to ± 0.5 msec. To support these type of services, radio or GPS receivers are required on the machine to receive the signals.

Synchronous systems have bounds known for the clock drift rate, maximum message transmission delay, and to execute each step of a process. In theory, the process sends a message at local time t, and the receiver gets the message at time t + T, where T is the time to send a message. The two clocks are now synchronised.

However, T is very difficult to know, but we can assume a maximum and a minimum. If we set the clock to t + min or t + max, then skew can be up to u, where u = (max - min). If we set the clock to t + (max-min)/2, then skew is up to u/2. The best skew is u(1 - 1/N), for synchronising N clocks.

In asynchronous systems, there is no max message delay, and round-trip times between pairs of processes is often short. Cristian's algorithm tells us to estimate message propogation time p = (T1 - T0)/2, so the clock gets sent to UTC + p. To increase the accuracy of this, we can measure T1 - T0 over a number of transactions, but discard any that are over a threshold as being subject to excessive delay, or take the minimum values as the most accurate.

Here, we have the problem of the time server being a single point of failure, and a bottleneck, and spurious time server values. It also makes the assumption that the server replies instantly, and tranmission in both directions takes the same time.

The Berkeley Algorithm was developed for Berkeley UNIX (now BSD). A co-ordinator is chosen as the master, and slaves are periodically polled to query clocks. The master than estimates local times with a compensation for propogation delay. An average time is now calculated, ignoring obviously invalid times. A message is then sent to each slave indicating clock adjustment. Here, synchronisation is feasible to within 20-25 msec for 15 computers with a drift rate of 2 × 10^-5 and a round trip delay of 10 msec.

Cristian's and the Berkeley algorithms were designed for use in LANs. Synchronisation across the Internet is more problematic. The Network Time Protocol (NTP) was created with the following design aims:

• To provide a service enabling clients across the Internet to be synchronised accurately to UTP
• Provide a reliable service that can survive lengthy losses of connectivity
• Enable clients to resynchronise sufficiently frequently to offset the drift rates found in most computers
• Provide protection against interference with the time service, whether malicious or accidental

NTP is implemented with multiple time servers across the Internet. Primary servers (stratum 1) are connected directly to UTC receivers, and secondary servers (stratum 2) synchronise with the primaries. Lower stratum servers synchronise with the higher strata, where each level is less accurate than the last.

NTP scales easily to large numbers of servers and clients, and can easily cope with failures of servers (if a primary UTC server fails, it becomes a secondary).

There are different types of synchronisation modes for NTP: multicast, where 1 or more servers periodically multicast to other servers on a high-speed LAN, this sets clocks assuming some small delay and isn't very accurate; procedure call mode is similar to Cristian's algorithm, where a client requests time from a few other servers, and this is used where there is no multicast, or higher accuracy is needed; and the symmetric protocol, which is used by master servers on LANs, and the layers closest to the primaries, which is very high accuracy and is based on pairwise synchronisation.

This can be characterised with Lamport's happens-before relation: a → b, where event a happens before event b. If a and b are from the same process, and a occurs before b, then a → b is true. If a is the event of a message send by one process and b is the event of the same message being received by another process, then a → b is also true.

Happens-before is a transitive relationship, and concurrent events have no relation (if a and b occur at the same time in process that do not exchange messages (even indirectly), then neither a → b nor b → a is true.

See OPS.

Like in independent systems, distributed systems also have to share resources, which are often encapsulated in critical sections. There are two essential requirements for mutual exclusion:

1. Safety - At most one process can be in a critical section at a time
2. Liveness - Requests to enter/exit the critical section will eventually succeed

The second requirement implies freedom from deadlock (discussed in OPS) and starvation (freedom from which requires fairness when selecting who should receive the critical section next amongst waiting processes).

One way of implementing this is using a central server which controls access to resources and grants permissions to enter and exit critical sections. This is a simple method, but has a single point of failure.

Another way is using a token ring to form a logical token ring amongst processes. A token is given to process 0, which then circulates. When a process has a token, it can enter a critical section, perform the requested operations and then exit the critical section then handing on the token. Problems can occur if the token is lost, though - there's no way to tell if it was lost, or if someone is using it.

Ricart and Agrawala use multicast to provide mutual exclusion - this requires total event ordering. This distributed algorithm is:

1. When a process wants to enter a critical section, it sends all the other processes a message containing the name of the critical section and the current time. It waits until an OK reply is received from all the other processes.
2. When a process receives a request message:
   1. If the receiver is not in the named critical section, and doesn't want to enter it - it sents back an OK
   2. If the receiver is in the named critical section, it does not reply, but queues the request
   3. If the receiver wants to enter the critical section (but is not actually in it yet), it compares the timestamp in the message with one it has sent to everyone, and the lowest timestamp wins. If the received timestamp is lower, we proceed as (a), otherwise we proceed as (b).
3. When a process exits a critical section, the process sends OK to all processes on its queue (and then deletes them from the queue)

Algorithm	Messages per entry/exit	Delay before entry (in message times)	Problems
Centralised	3	2	Coordinator crash
Distributed	2(n - 1)	2(n - 1)	Crash of any process
Token ring	1 to ∞	0 to n - 1	Lost token, process crash

Centralised algorithm is the most efficient, as the only messages required are to request, grant to enter and exit, and the delay between request and grant is short. In the distributed algorithm, messages required include many requests and grants per critical section access, and there is a long delay to enter a critical section. In a token ring implementation, messages are variable as a token can circulate without a critical section being entered, and the delay can be anything between 0 (the token has arrived as it is needed) and n - 1 (the token has just departed).

Some distributed algorithms require some process to act as a coordinator. The selection of a coordinator occurs via an election. The goal is that once an election has started, it concludes with all processes knowing the new coordinator.

An election can be called by any process, but a process can not call more than one election at a time. Many elections can occur concurrently, called by different processes, and election algorithms must be resilient to this.

In the ring algorithm, processes are arranged into a logical ring. When a process notices the coordinator is not functioning, an ELECTION message containing its process number is sent to the successor. If the successor is also down, it is sent to the next process. The message is then forwarded to all in the ring, each adding its own process number. The message then returns to the instigator (who sees that its own process number is in the message), which sends out a COORDINATOR message to all with the highest process number in it.

Another method the bully algorithm. When a process P notices coordinator is not responding, it initiates is an election by sending the ELECTION message to all processes with a higher numbers. If no-one responds, P wins an election and becomes the co-ordinator. If one of the higher processes respond, P's job is done and the higher process now holds an election. Eventually, all processes give up apart from one, which is the new coordinator. This process sends all others a COORDINATOR message to indicate its identity.

If transactions perform correctly by themselves, then if a series of transactions is performed serially, the combined effect will be okay. An interleaving of the operations of the transactions which also has the same effect is a serially equivalent interleaving. Serial equivalence prevents lost updates or inconsistent retrieval problems.

Serial interleaving prevents lost updates and inconsistent retrieval problems.

For two transactions to be serially equivalent, all pairs of conflicting operations of the two transactions must be executed in the same order at all of the objects they both access.

Operations of different transactions	Conflict?	Reason
read/read	No	Because the effect of a pair of read operations does not depend on the order in which they are executed
read/write	Yes	Because the effect of a read and a write operation depends on the order of their execution
write/write	Yes	Because the effect of a pair of write operations depends on the order of their execution

Servers must record effects of committed transactions, and record none of the effects of aborted transactions.

Problems occur if we don't do this, such as the dirty read problem, which arises if a transaction reads the uncommitted value of another transaction, which is then aborted. The premature write problem arises if a transaction reads a value written by another transaction which is then aborted, with the wrong value potential restored. To solve this, we require that all reads/writes take place after all previous transactions using the objects have been committed or aborted.

Transactions must be scheduled so that the effect on shared data is serially equivalent, but this doesn't necessarily prevent concurrency.

In exclusive locks (which is used when exclusive access is needed), the server attempts to lock any object about to be used by operations of a client transaction. If a client requires access to an object already locked, the transaction is suspended and the client waits until the object is unlocked. However, we must consider the problems of deadlock from OPS.

Two-phase locks can be used to ensure conflicting operations are executed in the same order. The transaction is not allowed to get more locks after it has released a lock. The first phase is to acquire locks, and the second phase is to release locks.

In strict two-phase locking, locks applied during a transaction is held until the transaction has committed or aborted. This solves the problem of dirty writes or premature writes.

A unique timestamp is assigned to each transaction when it starts. From this, we can get a total ordering of transaction starts, and requests from transactions can be ordered.

Transaction requests are checked immediately:

Rule	Tc	Ti
1	write	read	Tc must not write an object that has been read by any Ti, where Ti > Tc. This requires that Tc ≥ the maximum read timestamp of the object.
2	write	write	Tc must not write an object that has been written by any Ti where Ti > Tc. This requires that Tc > the write timestamp of the committed object.
3	read	write	Tc must not read an object that has been written by any Ti where Ti > Tc. This requires that Tc > the write timestamp of the committed object.

Each logical object is implemented by a collection of physical copies turned replicas. For the purpose of the model, we assume an asynchronous system, where the processes fail by crashing, and there are no network partitions.

We can break down a request into five phases:

• A request is made to the front end, which then issues the request directly to the replica manager
• Coordination - the replica managers coordinate to execute the request consistently (decisions need to be made about the relative ordering of requests).
• Execution - replica managers execute requests in such a way that it can be undone
• Agreement - replica managers reach a consensus on the effect of the request that will be committed, and an abort or commit is decided at this stage
• Response - the replica managers respond to the request, via the front end

Management of replicas require multicast communication (i.e., a message sent to just the replica managers, at the same time). Group membership services control multicast by managing the membership of a group (which can be dynamic by servers failing, new ones coming online and other ones going offline). The group membership service provides an interface for membership changes (create/destroy process groups, add/remove prcesses), implements a failure detector (monitors group members for crashes and may suspend potentially failing processes) and monitors reachability of members in the event of a communications crash. The service would also notify group members to membership changes and performs group address expansion.

An application running in a process group must be able to cope with changing membership. The group management service provides each process with a series of views of the membership. Each process in a group holds the same view, and a new view is delivered when a change in membership occurs (to ensure consistency, the group membership protocol holds new views in a queue until all members agree to delivery). New views are delivered at the same time to all processes, and view changes occur in the same order at each process, so processes should always act on the same view in order to maintain consistency. This method is called view delivery.

Another method called view synchronous group communication extends the group delivery to guarantee that a message multicast to members of a view reaches all non-faulty members of the group. This relies on the principles of agreement (all processes deliver the same set of messages in any given view), integrity (a process will deliver a message at most once) and validity (processes always deliver the messages that they send).

In the view-synchronous system, delivery of a new view draws a conceptual line, and every message delivered is either one side of the line or another. You can infer a set of messages delivered to other processes when a new view is delivered.

ISIS implements a synchronous view using TCP/IP, however the main problem is that of ensuring all messages delivered before the next group membership change occurs. A solution to this problem is that messages received by everyone in the group are stable, but when a view change needs to occur, all unstable messages are sent to all, followed by a flush message. When a process has received a flush from all others, a stable state is regained and it can continue.

Fault tolerance attempts to ensure that a correct service is provided, despite failures (so data and functionality is replicated at the replica managers).

The naïve approach is that if one replica is not responding, to try another. Correctness for replicated objects is achieved by linearisability, an interleaved sequence of operations meets the specification of a single correct copy of the object.

The order of operations in the interleaving is consistent with the real times which the operations were requested by the client. The idea is to ensure that replicas are the same as a virtual replica that receives operations in the correct order and doesn't crash. It requires synchronised clocks (which is not always possible). This only applies to operations however, not transaction. Concurrency control is still needed to achieve transaction consistency

One way of implementing fault tolerance is using a passive (primary backup) setup. A single primary replica manager and a number of secondary (backup) replica managers exist, and the frontends communicate with the primary replica manager only. Going back to the five phases of the system model:

• Request - made to the frontend which passes it with a unique identifier to the primary replica manager
• Coordination - FIFO used, in addition with identifier checks to make sure transactions aren't done twice
• Execution - the primary executes the request and stores the response
• Agreement - if the request is an update, the primary pushes the updated state to the backups (which acknowledge)
• Response - primary responds to the frontend which passes back to the client

This is an implementation of linearisability if the primary is correct. It requires a single backup to take over the primary role if the primary fails, and agreement on what operations have taken place at the replicas when the primary fails. View-synchronous communication can be used as the new view can be delivered without the primary, although ordering over the replica managers is required to decide who is to become the new primary. All surviving replicas have received the same operations also.

In active replication, the replica managers play equivalent roles and are organised as a group. Again, we can compare this to the five phases of the system model:

• Request - made to the frontends, including a unique identifier which is multicasted to all the replica managers
• Coordination - group communications system delivers the message to all replica managers in the same order
• Execution - each replica manager executes a request (identically)
• Agreement - is not needed
• Response - each replica manager sends a response to the frontend, which will collect a number of replies and check for consistency

This does not acheive linearisability (the total order in which replica managers process requests is different to the real-time order in which the clients made their requests). However, the weaker condition of sequential consistency is achieved. Replica managers process the same sequence of requests in the same order - happen-before ordering can be used. There is no total ordering over requests (as required by linearisability), just an ordering over requests coming from a specific client.