Digital Communication
Aims
The aims of this course are to develop an understanding of communications networks from a wide perspective, within a framework of principles rather than technologies or architectures. Technologies and architectures will, however, be used as examples and motivation.
Lectures
· Scope. Two example systems: Ethernet and the telephone system: basic operation; common issues; differing constraints; differing approaches.
· Partitioning the problem. Abstraction, service versus implementation; layering as a restricted form of abstraction; motivation for layering; the channel as an abstraction; layered channels.
· Fundamental transmission. Emphasis on the service provided by physical channel; limitations: noise, attenuation. Channel capacity (bandwidth). Modulation techniques for digital systems.
· Coding. Coding as a general concept: modulation as a form of coding, A/D,D/A, error correcting and detecting codes, other forms of coding, relation to layering.
· Multiplexing. Basic definitions, FDM, synchronous and asynchronous TDM. Circuit switching, packet switching, ATM. Shared media networks with particular emphasis on media access control. Packet scheduling. Non orthogonal multiplexing. Multiplexing and channel characteristics.
· Switching and routing. Introduction from LAN perspective (repeaters, bridges, routers). Fundamental view of switching extended to telephone network, connectionless versus connection oriented.
· Protocols and state. Imperfect view of state at far end of channel. ARQ as an example of an error control protocol; sliding window ARQ as an example of a flow control protocol; flow control in general: X.25 as an example.
· Naming, addressing and routing. Service access points, binding. Hierarchical versus flat address spaces. Routing classifications and algorithms.
· The Internet. Internet architecture, context of development, addressing and routing, transmission control protocol (TCP), higher layer protocols, evolution.
· Standards. Role of standards, dynamics of standards process, standards bodies.
Objectives
At the end of the course students should
· be able to analyse a communication system by separating out the different functions provided by the network
· understand that there are fundamental limits to physical transmission systems
· understand the general principles behind multiplexing, addressing, routing and stateful protocols as well as specific examples of each
· understand what FEC is and how CRCs work
· be able to compare communications systems in how they solve similar problems
· have an informed view of the internal workings of the Internet
Recommended reading
* Peterson, L.L. & Davie, B.S. (2003). Computer networks: a systems approach. Morgan Kaufmann (3rd ed.).
Comer, D. & Stevens, D. (1995). Internetworking with TCP-IP, vol. 1 and 2. Prentice Hall (3rd ed.).
Schwartz, M. (1987). Telecommunication networks: protocols, modeling and analysis. Addison-Wesley.
| OSI Model | |||
| Data unit | Layer | Function | |
| Host layers |
Data | Application | Network process to application |
| Presentation | Data representation and encryption | ||
| Session | Interhost communication | ||
| Segments | Transport | End-to-end connections and reliability (TCP) | |
| Media layers |
Packets | Network | Path determination and logical addressing (IP) |
| Frames | Data link | Physical addressing (MAC & LLC) | |
| Bits | Physical | Media, signal and binary transmission | |
Noise may be systematic or random
Attenuation: Signal looses energy as it travels along a channel.
C=B log_2(1+ S/N)
· C= information capacity
· B= bandwidth
· S/N= signal to noise ratio
Modulation: Transform to apporiate signal for transmission medium.
This technique of letting each shift of a wave represent some bit value is phase shift keying. But the real key is to shift each wave relative to the wave that came before it.
Forward error correction (FEC) is a system of error control for data transmission, whereby the sender adds redundant data to its messages, which allows the receiver to detect and correct errors (within some bound) without the need to ask the sender for additional data. The advantage of forward error correction is that retransmission of data can often be avoided, at the cost of higher bandwidth requirements on average, and is therefore applied in situations where retransmissions are relatively costly or impossible.
A trivial example of FEC to send three times, use majority voting.
Block coding is another type of FEC. Typically, a block code takes a k-digit information word, and transforms this into an n-digit codeword. If the sent data, doesn't match a codeword-but is very near then it was probably that one. Decoding is the hard part.
A cyclic redundancy check (CRC) is a type of hash function, which is used to produce a small, fixed-size checksum of a larger block of data, such as a packet of network traffic or a computer file. The checksum is used to detect errors after transmission or storage. A CRC is computed and appended before transmission or storage, and verified afterwards by the recipient to confirm that no changes occurred in transit. CRCs are popular because they are simple to implement in binary hardware, are easy to analyse mathematically, and are particularly good at detecting common errors caused by noise in transmission channels.
Multiplexing
Coding distinguishes higher level channels apart, policy determines how the lower layer channel is shared out.
Frequency division multiplexing distinguishes by different frequencies, eg TV.
Time division multiplexing eg different programmes (higher layer) on a certain TV channel (lower layer).
Synchronous time division multiplexing is when the receiver gets data at certain periodic intervals, eg digital telephony gets 8bits of data every 125us. No data identification needed as it's identity is known by the time at which it is sent.
In Asynchronous time division multiplexing identification needs to be sent with packets, to distinguish different senders. Hopes that senders will want to send at different times, otherwise could have a long queue.
Ethernet uses random access in which senders try and send, then if a collision is detected whilst being sent, then sending is aborted and tried again later.
Token rings, and radio conversation ("over") use tokens: once the transmitter is finished they pass the token along.
Reservation systems reserve time in advance.
Slotted systems divide the bandwidth into fixed size slots marked either free or busy.
Packet switching
Two dimensional parity makes the numbers of 1's both horizontally and vertically even.
| 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
(The bottom left 0 applies to the row of parity bits, not the column).
Checksums simply provide the result of adding all sent data.
With CRC you work out what you need to add or subtract from the data (treated as a polynomial) to make it exactly divisible by a set number (in Ethernet CRC it is a certain 32bit number) and send that as well as the message.
http://en.wikipedia.org/wiki/Mathematics_of_CRCs
ARQ (Automatic Repeat Request)
If gets data and valid CRC, sends ACK
If gets incorrect CRC or data too long, send NACK
Stop-and-wait
Stop and wait is the simplest ARQ scheme. Send, if no ACK receieved within a certain time or a NACK then resend with a leading 0 (instead of 1) so receiver knows its getting a second copy- not the next frame. This is a slow method as it can't send any data whilst waiting for an ACK.
The sliding window algorithm
The sender sends up to fixed number of frames without waiting for an ACK.
The sender maintains three variables: SWS (send window size), LAR (latest acknowledgement received) and LFS (last frame sent) and maintains
LFS - LAR < SWS
The receiver maintains RWS (receive window size), LAF (largest acceptable frame) and LFR (last frame received) and maintains
LAF - LFR < RWS
Eg if the receiver receives 7 and 8 but not 6 (and LFR=5, RWS=4 so LAF=4+5=9) then it will wait until 6 is received to send ACK's.
Naming, Addressing and Routing
Eg;
Name: John Leslie
Address: FN15
Route: Up one floor, across the hall
Names identify things, addreses identify attatchment points, routes identify paths.
Service access points are the points of attatchment between an upper layer and lower layer entity- you can view addresses as denoting service access points.
Flat address spaces have no structure, eg Ethernet 48. They give few clues to routing protocols.
Class based addresses are normally one of three types (with 0,10 or 110 at the beginning) and the word is split into network and host bits.
ARP
If A knows B's IP address but needs to know B's Ethernet address in order to communicate-
A sends out, using Ethernet broadcast address and ARP request packet containing:
l Tag saying this is an ARP request
l Tag saying IP is the protocol
l A's IP and Ethernet Address
l B's IP address
If B receives this packet and recognises its IP address, it updates its tables about A and transmits to A vie A's Ethernet address:
l Tag saying this is an ARP reply
l Tag saying IP is the protocol
l B's IP and Ethernet Address
l A's IP and Ethernet Address
Routing
A network bridge connects multiple network segments at the data link layer (layer 2) of the OSI model. Bridges are similar to repeaters or network hubs, devices that connect network segments at the physical layer, however a bridge works by using bridging where traffic from one network is managed rather than simply rebroadcast to adjacent network segments. In Ethernet networks, the term "bridge" formally means a device that behaves according to the IEEE 802.1D standard - this is most often referred to as a network switch in marketing literature.
Since bridging takes place at the data link layer of the OSI model, a bridge processes the information from each frame of data it receives. In an Ethernet frame, this provides the MAC address of the frame's source and destination. Bridges use two methods to resolve the network segment that a MAC address belongs to.
A router acts as a junction between two or more networks to buffer and transfer data packets among them. A router is different from a switch and a hub: a router is working on layer 3 of OSI model, a switch on layer 2 and a hub on layer 1. This makes them work for different situations: a switch connects devices to form a Local area network (LAN) (which might, in turn, be connected to another network via a router).
One easy illustration for the different functions of routers and switches is to think of switches as neighborhood streets, and the router as the intersections with the street signs. Each house on the street has an address within a range on the block. In the same way, a switch connects various devices each with their own IP address(es) on a LAN. However, the switch knows nothing about IP addresses except its own management address. Routers connect networks together the way that on-ramps or major intersections connect streets to both highways and freeways, etc. The street signs at the intersection (routing table) show which way the packets need to flow.
In order to route packets, a router communicates with other routers using routing protocols and using this information creates and maintains a routing table. The routing table stores the best routes to certain network destinations, the "routing metrics" associated with those routes, and the path to the next hop router. See the routing article for a more detailed discussion of how this works.
Routing is most commonly associated with the Internet Protocol, although other less-popular routed protocols are in use.
Router means Connection between different networks... sample example: 192.168.0.1 to 10.0.0.1.
Forwarding: Taking a packet, looking at is destination address, consulting a table, and sending the packet in a direction determined by that table. Routing is the process by which routing tables are built.
The forwarding table contains the mapping from a network number to an outgoing interface and some MAC information, such as Ethernet address of the next hop.
The routing table, on the other hand, is the table that is built up by the routing algorithms as a precursor to building the forwarding table.
Can get the source to choose the route and embed it in the packet.
The internet
Internet Protocol (IP) service is the delivery of internet datagrams- a low level common service.
Eg; over Ethernet the frame data section contains the ip header and ip data.
The IP Address has two parts: network address and host address.
Datagram = connectionless
Virtual circuit = connection orientated
TCP
To establish a connection, TCP uses a three-way handshake. Before a client attempts to connect with a server, the server must first bind to a port to open it up for connections: this is called a passive open. Once the passive open is established, a client may initiate an active open. To establish a connection, the three-way (or 3-step) handshake occurs:
1. The active open is performed by sending a SYN to the server.
2. In response, the server replies with a SYN-ACK.
3. Finally the client sends an ACK (usually called SYN-ACK-ACK) back to the server.
At this point, both the client and server have received an acknowledgement of the connection.
Example:
1. The initiating host (client) sends a synchronization (SYN flag set) packet to initiate a connection. Any SYN packet holds a Sequence Number. The Sequence Number is a 32-bit field in TCP segment header. For example let the Sequence Number value for this session be x.
2. The other host receives the packet, records the Sequence Number of x from the client, and replies with an acknowledgment and synchronization (SYN-ACK). The Acknowledgment Number is a 32-bit field in TCP segment header. It contains the next sequence number that this host is expecting to receive (x + 1). The host also initiates a return session. This includes a TCP segment with its own initial Sequence Number value of y.
3. The initiating host responds with the next Sequence Number (x+1) and a simple Acknowledgment Number value of y + 1, which is the Sequence Number value of the other host + 1.
TCP is different to UDP in that it provides:
l Ordered data transfer
l Retransmission of lost packets
l Discarding duplicate packets
l Error-free data transfer
l Congestion control
