#Computer Networks
Location: St. Leonard's Land Gym 4
Date/Time: Monday 29/04/2013, 09:30:00-11:30:00 (02:00:00)
?
KR5e = "Computer Networking: A Top-Down Approach" (5th edition)
- [KR5e]
Sections 1.1-3(The Internet as nuts-and-bolts services & What is a protocol?) - [KR5e]
Chapter 1(Computer Networks and The Internet) - [KR5e]
Section 2.1(Principles of Network Applications) - [KR5e]
Sections 2.1-4 and 2.7(Principles and Application Examples) - [KR5e]
Chapter 2(The Application Layer) - [KR5e]
Sections 3.1-2(Introduction to the Transport Layer / (De)Multiplexing) - [KR5e]
Sections 3.3-4(UDP and Principles of Reliable Data Transfer) - [KR5e]
Sections 3.5-8(TCP) - [KR5e]
Sections 4.1-4 - [KR5e]
Sections 4.5-6 - [KR5e]
Sections 5.1-6
- 1:
Intro & Overview - 2:
Layered Network Architecture - 3:
TCP/UDP - 4:
The Network Layer - 5:
Traffic Management - 6:
PANs - 7:
Intro to Wireless - 8:
Tutorial on Wireless - 9:
802.11 Wireless LANs - 10:
RFID - 11:
Cellular Networks
P lease (Physical Layer):
- Twisted Pair Copper-Wire/Coaxial Cabling/Fiber.
- Concerned with transporting indidual Bits within a Frame from one end of the 'physical'-link to the other.
L ynne, (data-Link Layer):
- Ethernet/WiFi/DOCSIS.
- Concerned with transporting Frames consiting of Packets between (host/router) Nodes.
- Links are the connections between Nodes.
N o (Network Layer):
- IP.
- Concerned with transporting Message Segment Datagrams to a given Address.
- The Internet, a network of networks, is structed as a series of connected Autonomous Systems.
- Routers pass datagrams from Source to Destination through a combination of intra-AS and inter-AS protocols.
- RIP (a decentralised distance vector protocol) and OSPF (a global link-state protocol) are used to populate router forwarding tables.
- Datagrams that exceed the maximum Frame size of the interface between routers may be Fragmented using offsets and Fragment flags in the datagram header.
T ouching (Transport Layer):
- TCP/UDP.
- Concerned with transporting Message Segments to a given Host and Port.
S exy (Service Layer): (Only present in the 7 Layer model) Delimiting/Synchronisation of data exchange.
P rofessional (Presentation Layer): '' '' Provides Encryption/Compression/Description of data.
A sians (Application Layer):
- Network Applications and their Protocols, (HTTP/SMTP/FTP).
- Concerned with sending Messages.
"The Stop-and-Wait protocol is an example of the Automatic Repeat-Request (ARQ) class of protocols for sending information between two connected devices. Derive a formula for the efficiency."
The protocol requires each datagram to be uploaded, propagated, processed and then the ACK to be uploaded, propagated and then processed before the next packet can be transfered.
Assuming constant RTT and processing times, the total time taken (T) is RTT + 2*Proc + (Ldg /R) + (Lack / R).
The effective transmission rate (Reff) is the total amount of information (not data) transmitted (datagram minus header) over the time taken: (Ldg - Lhead) / T. The transmission efficiency is therefore Reff / R.
"What is the impact on the transmission efficiency derived above for an error probability of Pf in transmitting a datagram?"
The probability of successs (Psuc) = (1 - Pf) and the expected number of transmissions (E) for a datagram to be successfully transferred is (1 / Psuc). Replace T with ET in the formula above.
"Describe the Go-back-N ARQ protocol where the transmitting process continues to send a number of frames specified by a window size without receiving an acknowlegement packet from the receiver. Illustrate the operation of the protocol with a diagram for the case of N = 4."
With Go-back-N, the sender is allowed to continue sending packets without ACK receipt, up to a maximum of N unconfirmed packets in limbo (given enough data provided by the upper layer). The sender records the lower-bound of the window, the oldest outstanding packet currently unACKed and the packets within the window currently sent (alongside their time of dispatch). The upper layer can continue to fill the window with packets to send (which are immediately dispatched given space) until the windows is full, at which point the tranmission halts.
When the receiver sends an ACK with sequence number M, it is assumed that all packets up to and including M have been received successfully and the lower bound of the window is slid forward to M+1 (allowing seq=M+1 and N-1 other packets to be sent).
A timer on the sender causes an interrupt if a threshold interval has passed since the transmission of the lower-bound packet, causing retransmission of ALL sent packets within the window.
"For the transmitting process above, derive the bound on the window size in terms of the number of bits available in the header for sequencing."
Given an N bit sequence header, the highest seq_id possible is 2^N -1. There are therefore 2^N possible ids (including 0) and the id should be incremented modulo 2^N. Since the wrap around may be ambiguous (is the next id expected the first 0 meaning no success or the next 0 meaning total success?) the window size Ws is limited to 2^N -1.
"Describe how the Selective-Repeat ARQ protocol improves on the Go-backN protocol. Illustrate the operation of the protcol with a diagram"
With Selective-Repeat, the receiving host has a buffer allowing receipt of packets out-of-order. Instead of retransmitting the entire sent portion of a transmission window when the lower-bound timer expires, each datagram has an associated timer. The above layer can proceed to send datagrams immeditately if there is space remaining at the window.
Each datagram is ACKed by the receiver and any datagrams outstanding are retransmitted when their timer exceeds the threshold duration. The protocol benefits from not having to retransmit ALL datagrams within the sliding window on the failure of the lowest, but the window still restricts the highest sequence packet to be at most N-1 above the lower-bound (since the destination host has to be able to buffer all datagrams in order for reassembly).
"In Selective-Repeat, derive the bounds on the window sizes in terms of the number of bits available in the header for sequencing."
Selective-Repeat uses two windows; a sending window Ws and a receiving window Wr (allowing the buffering of packets to be reassembled). As before, Ws maximum length is determined as the highest unambiguous number of IDs given M bits (2^M -1). However, the receiving window has the maximum size of however many datagrams the destination host can buffer. The receive window, Wr, is advertised by the destination host using the TCP protocol. In order to avoid transmitting more datagrams than the receiver can buffer, the sending window is therefore limited to the minimum of (Ws_max, Wr).
"What are the services provided by a Domain Name System (DNS)?"
DNS is a distributed database of human-readable Domain Name to IP Address mappings. It is also an application layer protocol for querying said database by end-systems.
In addition, DNS provides aliasing of domain names to canonical names and mailserver IP addresses and can be used as a load-balancer by selecting one of many server IPs to return when queried with a domain.
"Describe the hierarchical organisation of a typical Domain Name System."
The Domain Name System uses the lookup of DNS servers responsible for a series of progressively lowering scopes until the entity responsible for the resource's records can be found. An example is as follows: In order to lookup the IP address of a domain such as www.google.com the first port-of-call is a Root DNS server. The Root DNS server will return the hostname and IP address responsible for the records of the .com TLD. Next, the .com TLD is queried in order to find the hostname and IP address of the google.com nameserver. Finally, the google.com nameserver is queried for the IP address associated with www.google.com.
"Describe the format of the Resource Records."
A resource record is a 4-tuple of (Name, Value, Type, TTL). If the type is A: The name is the a hostname and the value is its IP address.
If the type is NS: The name is the domain and the value is the hostname of its authorative DNS server.
If the type is CNAME: The name is a hostname alias and the value is the canonical hostname associated.
If the type is MX: The name is a hostname alias and the value is the canonical name of a mailserver associated.
In all cases, the TTL is the length of time that the resource should be cached in a local DNS cache before being deleted and therefore required to be fetched again on next request to that hostname.
"A new company has registered the domain name newstart.com. What are the Resource Records that the registrar must insert in the com server?"
The person responsible for newstart.com must provided NS records for the primary and secondary authorative DNS servers, of the following style:
(newstart.com, dns1.newstart.com, NS, 30min) (newstart.com, dns2.newstart.com, NS, 30min)
They must also provide A records for the two DNS servers:
(dns1.newstart.com, 188.122.1.2, A, 30min) (dns2.newstart.com, 188.122.1.1, A, 30min)
"Explain the rationale behind the choice of CDMA as the channel access method in 3G cellular wireless networks. Outline two key practical challenges for effectively using CDMA in cellular networks."
By using Code-Division-Multiple-Access, multiple hosts are able to communicate over the wireless 3G channel without destructive interference causing the contents of their frames to be lost. This allows for greater capacity and allows periods with few users to exploit the greater per-user throughput available. CDMA also allows association with multiple basestations between handoffs due to the available access to all frequencies.
The two challenges for CDMA in 3G are synchronisation and the near-far problem.
It would be infeasible to have syncronised chipping codes across all connected devices so codes are need that are orthogonal across all time offsets.
The near-far problem is the issue that signal strength varies with distance from basestation and with a very strong signal present it may be impossible to cancel out its effects on a weaker signal's coded broadcast. The solution is to force the end-devices to alter their transmit power so that the received power levels are the same.
"Infrastructure mode communication in 802.11 wireless networks between an access point (AP) and its associated clients bears similarity with reader-tag communication in UHF (EPC Gen 2) RFID networks in the sense that both cases employ contention based random multiple access methods. Why are the actual multiple access protocols in the two cases so different? Explain, focusing on the key aspects of 802.11 MAC and EPC Gen 2 tag identification protocols."
802.11 communcation uses distributed Carrier-Sense-Multiple-Access with Collision Avoidance and Inter-Frame-Spaces received for certain frame types. In 802.11 CMSA, each host attempts to send if the medium is idle in certain IFS (received signal below threshold). Otherwise, random backoff between 0-CWmin. Counter only decrements during idle slots then attempted retransmission.
If no ACK, double backoff interval.
UHF RFID uses a master-slave approach to collision avoidance. The reader (master) gives a range of slots with a 'Query' message and each slave receives this message and picks a random slot. The master then sends a QRepeat message with a specified slot. Any slave that picked this slot then transmits a random 16 digit number, if its number is acked the slave can then send the entire identifier.
The two approaches are very different with a master-slave approach being taken over a distributed carrier-sense protocol due to the inability for RFID tags to receive eachother's messages.
"Suppose you are tasked with optimizing voice over IP (VoIP) performance over WiFi (802.11) for mobile smartphone users in an enterprise while being compliant to the 802.11 standard. What aspects/parameters of the protocol would you choose to optimize and why? Assume that you can update the 802.11 related software on access points as well as user devices."
The 802.11 standard allows higher-priority frames to be sent in earlier Inter-Frame Spacing gaps than low-priority frames in order to increase the likelyhood of successful transmission. The VoIP traffic can be also use a lower contention window than other traffic so that it is likely to be transmitted much sooner after a busy channel (When a random counter is selected from CWmin). The VoIP flow would have to be tagged as such by the upper layers so that the wireless interface can recognise its type and treat the traffic differently to other flows.
"In Stop-and-Wait ARQ why should the receiver always send an acknowledgement message each time it receives a frame with the wrong sequence number?"
Imagine the scenario where the source sends a datagram with seq_id 0 and it is successfully received by the destination host who replies with ACK 1 (the next seq_id expected). If this ACK is lost between endpoints, the sender will timeout and resend datagram 0. If the destination does not ACK 1 (once again, the next expected), the source will repeatedly timeout and this cycle will continue indefinitely. If the destination does ACK, this should (eventually) be received by the source and it can progres to sending the next datagram in the sequence.
"Using diagrams showing the exchange of messages between transmitter and receiver, explain how the Selective-Repeat protocol overcomes the problems: (i) a corrupted information frame, (ii) a corrupted ACK frame."
On receipt of a corrupted datagram the destination host has two choices. It can either do nothing or ACK the oldest sequence ID that it has not received yet. If nothing is done, the timer for the corrupted datagram on the sender-side will exprire triggering its retransmission. If the ACK is sent, the datagram referenced by will be immediately (re)transmitted by the sender. This datagram may or may-not be the corrupted datagram but the protocol will continue to function correctly anyway.
(Or this could be answered by the angle of corrupted datagrams being discarded and therefore either nothing is received or the next datagram in sequence is received: in which case the same happens.)
On receipt of a corrupted ACK, the sender just discards the ACK and continues allowing the timers to either expire or be cumulatively ACKed when a higher sequence number is ACKed (assuming that the destination is ACKing the earliest non-received).
"Consider an error-free communication network where frames are generated by Node A and sent to node C via Node B. The link betweem A and B is 4000 kilometer long and uses a sliding window protocol with window size 3, and the link transmission rate is 100kbps. Since there are no errors, goback-N performs exactly the same as Selective-Repeat in this situation. The distance between B and C is 1000 kilometer, and a simple Stop-and-Wait protocol is used. The propagation delay is 5 microsecond per kilometer for both lines. There are full-duplex lines between the nodes. All data frames are 1000 bits long with negligible header overhead. ACK frames are separate and have negligible length. Determine the minimum data rate required between nodes B and C so that the buffers in node B are not overrun"
The effective data rate (Reff) of Go-Back-N is the amount of data that it can send over the time that it can take to send it. The unit of data is know at 1000bits. The time taken to send it is 1000/R + RTT.
This gives the inequality (1000 / (1000/R + 0.000005*2000)) >= effective data rate of A->B.
With Selective-Repeat and a window size of 3, the window can be sent in T = (3*1000)/R and cumulatively ACKed in T + RTT where RTT = (0.000005 * 8000).
Work out the inequality....
"Describe the congestion control mechanism in TCP."
TCP uses and End-to-end congestion control mechanism.
A TCP connection starts with an initial congestion window of 1 (or 4 if you are Google). On successful ACK of a segment, the congestion window is doubled until a negative indicator or a predetermined threshold is reached. If the threshold is reached, the window continues to grow linearly. On three NACKs, the window is halved and the window grows linearly from then on. If a timeout occurs this signals significant congestion, the threshold is set to half Cwnd and the algorithm starts again with exponential growth from Cwind = 1.
"Given that a content distribution network (CDN) does not increase the capacity of network links (assuming the CDN uses existing links to distribute its content among CDN nodes), how does a CDN improve the performance seen by hosts? Give an example."
A CDN adds more end-systems presenting a resource to the Internet. This provides the advantage of being able to serve a higher number of requests than a smaller set of original servers. The CDN may have far more sophisticated load-balancing in order to scale more significantly. In addition the CDN may have greater geographic distribution than the original source, causing clients in areas further from source to have a lower latency due to CDN servers closer to them and therefore with a lower RTT.
"Explain the key features of the IEEE 802.11 Multiple Access Control(MAC) protocol and how it addresses the issues that arise for random access MAC protocols in wireless networks."
802.11 Uses Carrier-Sense Multiple-Access with Collision-Avoidance. It aims to reduce the number of frames lost due to multiple simultaneous transmissions destroying eachother due to interference.
A wireless interface wishing to transmit a frame listens for signal-activity. A low activity level suggests that the channel is free. If the channel is free, at a certain Inter-Frame-Spacing the frame is transmitted. Otherwise, the transmitter selects a random count between 0 and the CWmin. This counter is decremented on each free channel slot. Once the counter is at 0 the interface attempts a retrasmission. If the channel is busy again the backoff is doubled. Exponential backoff eases congestion of the medium caused by many devices trying to retransmit on the case of failed frames destroyed by interference.
"Describe the operational phases of the Open Shortest Path First (OSPF) protocol for building and maintaining routing tables in a packet switched IP network."
OSPF is a link-state protocol that uses flooding of link-state information and Djikstra's algorithm for finding the shortest-path tree to all subnets.
Phase 1: Hello protocol. Router periodically broacasts Hello. Routers respond to Hello with Hello containing IDs of every known neighbouring router.
Hello with own id in body shows that there is a working bidirectional link.
Phase 2: Routers pair and become adjacent, synchronising link-state database. Advertising changes to their database and requesting database from other.
Phase 3: Maintenance. Link-state requests to neighbour and link state updates again. Link State Advertisements are flooded to all but origin.
Link state advertisements are broadcast every 30 minutes if no change before.
"Explain how the use of hierarchy enhances the scalability of the routing in the OSPF protocol."
The hierarchy of IP Addresses encourage geographically similar end-systems to share most significant bits, as well as some of the shortest-path route. This simplifies the routing tables required in the network layer as routers can perform a longest-prefix match on subnets when updating or consulting the routing table.
For example, imagine a router has the subnet 118.0.0.0/8 shortest path being interface A and it recieves information for 118.101.1.0 If the new subnet shares the same interface for the shortest-path, no new information must be added to the routing table as the longest-match will be the same. If it requires a different interface, a more detailed entry will be added with a longer subnet mask (such as 118.101.0.0/16). The longest-match will now direct traffic to the correct interface.
With hierarchical OSPF routing, the full Autonomous System is split into smaller Areas. The smaller areas reduce the number of entries in the forwarding table and it is much easier to work out the optimum path for a smaller topology. All of the OSPF Areas are connected via their Area Border Routers as a 'Backbone' network which links outside the AS. The area border routers summarise their internet nets and advertise these paths within the backbone network.
"A home computer is connected to the Internet via one-way satellite broadband. The up-link is through a common 56K dial-up. Which of the following uses would be efficient and which ones not? Justify your answers. i. Listening to an Internet radio station. ii. Chatting (real-time messaging, not IP telephony). iii. Playing online, fast-action games. iv. Publishing the user’s high quality photos through a web server running at the local machine. v. Sending email. vi. Receiving email."
i. Would work well, latency is not too much of an issue for internet radio as it does not have to be real-time. The high download rate of the broadband would handle retrieving the large datagram packets over UDP fine.
ii. Chatting would work as the delay due to the satellite link would not be too much to disrupt the flow of a typed conversation. In addition, the amount of data contained within outgoing typed messages would not be enough to overwhelm the 56k up-link.
iii. This would not work well due to the high latency of the satellite link causing the game client to have a state that was significantly behind others. An application layer game server may reject high latency connections as they degrade the experience for others.
iv. This would not work well due to the 56k up-link having insufficient data-rate to serve requests for photo resources in any reasonable time.
v. Sending email would work
ETC
"Describe the (graceful) connection termination procedure of TCP."
To close a connection, the client sends a segment with the Fin flag set and waits for an ACK (retransmitting if lost as usual). The server then sends a segment with the Fin flag set. On receipt the client sends and ACK and enters a timed-wait phase. Further Fin segments (if the ACK was lost) reset the time and are ACKed otherwise the client releases all resources after the timed-wait expires.
Wireless Network forumulae
Shannon's Channel Capacity Theorem:
C = W * log2(1+SNR)
Frame error rate = 1 - prob bit success where prob bit success = (1-BER)^L
Throughput = bit rate * prob frame success