1. Question 1 - UCL



Department of Computer Science

University College London

Cover Sheet for Examination Paper to be sat in

May 2004

COMPC329-resit / COMPD015-resit

Communications and Networks

Time allowed 2.5 hours

Calculators are permitted

Answer THREE questions

Checked by First Examiner: Date:

Approved by External Examiner: Date:

COMPC329 / COMPD015 Communications and Networks

Answer THREE questions

Marks for each part of each question are indicated in square brackets

Calculators are permitted

|Formulae which may be useful in the exam |

| |

|Information Theory |

|Capacity C, bandwidth W, signal to noise ratio S/N, number of signal levels M. |

| |

|Signal to Noise Ratio in decibels = 10log10(S/N) |

| |

|Nyquist’s Theorem C = 2Wlog2M. Shannon's Theorem C = W log2(1+S/N) |

|Miscellaneous |

|[pic] |

1. Asynchronous Transfer Mode (ATM) is a virtual-circuit (VC) based technology in which data is transmitted in cells. Explain the terms cell and virtual-circuit. Explain how VCs are identified within an ATM network and the constraints that apply when identifiers are allocated. Outline some of the reasoning that has been advanced for the use of VCs in ATM. [13 marks]

Cell = a small (53-byte) fixed-size packet.

Virtual circuit = a path set up between two hosts through the switches of a packet network. All packets sent on the VC follow the same path.

VCs are identified by a series of numbers (VC identifiers) applied to each link traversed. A VCI must be unique within the scope of a link. Each packet carries a VCI in its header. Switches map VCIs appropriately before transmission on the next link.

In the ATM case VCIs have two components: The virtual path identifier (VPI) identifies (usually) a path between two hosts. VPIs must be unique within the scope of links. The virtual channel identifier (VCI) acts as a sub-multiplexor identifying a particular activity on the VPI. VCIs must be unique within the scope of a VPI. In this model switches process VPIs , hosts process VCIs.

Cells were chosen since a) small size reduces store and forward delay, b) fixed size makes for rapid processing.

Small size means cells cannot carry global addresses. This demands a VC architecture in which cells need only carry VCIs which can be small due to their limited scope.

a) Describe the Switched Virtual Circuit mode of the Classical IP over ATM (CIPA) mechanism for implementing IP over ATM. [5 marks]

There are three main problems to solve:

Encapsulation

ATM cells are generally too small to carry IP datagrams. The IP fragmentation mechanism would be inefficient. Therefore an ATM-specific framing mechanism (AAL5) is used to group cells into larger frames.

Address Resolution

An ATM ARP Server must be present at a well-known address. Typically hosts establish VCCs with the AAS and register their mappings at start-up. When an IP datagram is to be send to a host for which no mapping is cached, the AAS is consulted.

Connection management

Host to host VCCs are set up on demand. They may be discarded after an idle timeout.

i) Discuss the inefficiencies that may arise when two IP subnets are implemented on a single ATM network and outline a possible enhancement. [4 marks]

The classical IP architecture requires a) that the two subnets use different network prefixes and b) that inter-subnet traffic goes via a router.

This works but means that inter-subnet traffic traverses the ATM network twice even though a more efficient path is available.

One solution is to use the Next-Hop Resolution Protocol. This requires a Next Hop server in addition to the AAS. The NHS is informed of mappings on both subnets. Hosts consult the NHS as well as the AAS. If the NHS returns an address on the local ATM network then a diorect VCC is set up.

b) The diagram below shows two Ethernet LANs and an ATM network.

[pic]

Discuss some options for providing connectivity between hosts on these networks, indicating some of their strengths and weaknesses. [11 marks]

Some points that could be included … (obviously answers will vary. I am looking for evidence of understanding of the various ways of connecting things together)

A) IP

Make A and B routers and deploy three IP subnets on the three networks. Use CIP and ATM for example.

Advantages. Full IP connectivity between hosts on all networks. Simple, well understood. Routers may have useful firewall features

Disadvantages. Excludes non-IP traffic. Routers comparatively expensive.

(B) LAN

Use LANE on the ATM network, A and B are bridges.

Advantages. Supports IP and non-IP. Only need one IP subnet

Disadvantages. May make for a very large subnet. LANE complex, not especially efficient

B) A and B half bridges or routers joined by ATM VCC

Advantages. Very simple use of ATM network.

Disadvantages. Excludes ATM hosts

[Total 33 marks]

2. A wireless channel is subject to a signal to noise ratio of –20dB. The channel is required to provide a capacity of 1 Mbps.

i) Show that the required capacity may be achieved provided the channel bandwidth is greater than about 70 MHz. [4 marks]

SNR = -20dB => S/N = 0.01

From Shannon, C = Blog2(1.01) = 0.0144B

For C = 106 we must have B = 106 / 0.0144 = 69.7 MHz (3.s.f)

ii) Outline briefly why a conventional modulation scheme such as Quadrature Amplitude Modulation (QAM) would not be effective on this channel. [4 marks]

16-QAM, for example would need to transmit at 106 / 16 = 62500 baud. Modulation would produce a signal of the order of 2(62500 = 0.125 MHz – a long way short of 70Mhz. In practice the noise would make the scheme impractical

iii) A possible transmission technique for this channel is Code Division Multiple Access (CDMA). A CDMA scheme uses the following chip sequences for stations A, B and C:

A 00111001

B 01001101

C 10011100

By reference to this scheme, explain how CDMA works and why it is effective on a noisy channel. [10 marks]

Operation is best understood if a zero chip is represented as –1.

The chip sequences are orthogonal – i.e. A.B = 0 for all pairs. Also, A.A = 1 for all codes.

To transmit a 1 bit, a station transmits its chip sequence. To transmit a 0 bit it transmits the complement.

A receiving station must compensate for differential power levels and lack of synchrony between stations. If this is done, the combined, received signal may be regarded as the sum of the transmissions. Thus, if A, B and C transmit 0, 1, 1 respectively the combined signal will be:

1 1 -1 -1 -1 1 1 –1

-1 1 -1 -1 1 1 -1 1

1 -1 -1 1 1 1 -1 –1

1 1 -3 -1 1 3 -1 -1

To extract the signal for (say) B we form the normalised scalar product with B’s code which gives (-A+B+C).B = -A.B + B.B + C.B = B.B = 1, i.e.:

-1 + 1 + 3 + 1 + 1 + 3 + 1 + -1 = 8 => 8/8 = 1

In practice the noise would mean that some chips would be received in error so that the result is not quite 1(0). However, most of the time sufficient will be received correctly so that we can correctly recover the bit.

Clearly this scheme is using 8 times the capacity, hence the bandwidth, of a conventional modulation scheme. By varying the chipping ratio we can spread the signal over an arbitrary bandwidth.

a) The sequence 1010 1110 0011 0111 1111 1001 0011 0011 1001 11 is a message followed by a Cyclic Redundancy Check (CRC) generated using the polynomial x5+x3+1. The left-most bit is transmitted first. Write down the message and the CRC. [N.B. the bits have been grouped in fours to aid reading – there is no other significance.]

[2 Marks]

message 1010 1110 0011 0111 1111 1001 0011 0011 1, CRC 00111

i) Show how the sequence in b) i) above would be encoded in the data link layer if the system used transparent bit-oriented framing (such as that used in HDLC for example). [3 marks]

The data link layer will perform bit stuffing and will delimit with flags and the resulting string will be:

0111 1110 1010 1110 0011 0111 1101 1100 1001 1001 1100 1110 1111 110

b) The diagram shows two network switches S1 and S2 on the path between hosts A and B. The diagram also shows the link capacities. The propagation time on each link is p sec.

[pic]

i) “S1 and S2 are store-and-forward packet switches”. Explain what this statement means and derive a formula for the delay when sending a packet of s bits from A to B. [Ignore all other possible sources of delay]. [4 marks]

Store-and-forward switches must receive the complete packet on the input link before they begin transmission on the output link.

Assume transmission starts at t = 0 sec

Last bit of packet leaves A at t = s/a sec

Last bit of packet arrives at S1 at t = p + s/a sec

Last bit of packet arrives at S2 at t = 2p + s/a + s/b sec

Last bit of packet arrives at B at t = 3p + s/a + s/b + s/c sec

ii) A single error occurs as a packet traverses the inter-switch link. The error is detected and recovered as a result of a timeout of T sec and successful retransmission. In one scheme, detection and recovery take place in the Data-link Layer; in another scheme, detection takes place at the destination host (B) and recovery is in the Transport Layer. Find, in each case, the effect this error has on the delay calculated in part c) i). Briefly discuss the strengths and weaknesses of the two recovery schemes. [6 marks]

In both cases the last bit of the packet arrives at B at t = T +3p+ s/a + s/b + s/c sec,. However, the timeout in the Data-Link case can be shorter since it depends on the RTT on a single link. This will be both shorter than the end-to-end RTT and will likely have lower variance.

The disadvantage of this is that it forces the application to accept error recovery and the consequential variable delay whether it wants it or not.

[Total 33 marks]

3. A web server runs on a computer with domain name haig.cs.ucl.ac.uk. A browser accesses a page with URL . Both the browser host, the web server host and the DNS host are connected to the same Ethernet LAN. Give an account of the steps that take place as the browser requests the page. [Assume no useful cached information is available at the start of the exchange. You do not need to account for every packet sent!]

[8 marks]

The browser software extracts the domain name from the URL and constructs a look-up request to send to the DNS server. The IP address of the DNS server must be known.

IP routing will determine that the packet can be sent direct. The IP address will need to be resolved using ARP. Assuming the look-up is successful, the browser now has the web server’s IP address. This is used to set up a TCP connection to the web server. If this is successful, the HTTP request for the page is sent over the TCP connection. (Again, ARP will be used to resolve the server’s IP address)

a) Explain what is meant by a user-level session.

[2 marks]

User-level session – an association between (typically) two applications. There is a synchronisation phase at the start, a message exchange phase, then a termination phase.

i) Explain one method whereby a user-level session spanning several HyperText Transfer Protocol (HTTP) requests may be implemented.

[3 marks]

For example, the cookie mechanism …

Cookie – a piece of named information understood at the server

Server might include Set-Cookie: SessionId="1234"; in an HTTP response. In this case the cookie identifies a session at the server. The client must include the cookie in all subsequent requests to the server. Typically the client stores the cookie on a local disc. Cookies generally have timeouts associated with them.

ii) How is the concept of a user-level session realised in the Internet File Transfer Protocol (FTP)? Outline the principle events that occur at the transport layer and above as a file is transferred from the server.

[4 marks]

Client establishes a control channel with the server. This is achieved by opening a TCP connection to the server and logging in. The user-level session is 1-1 with the transport connection.

Having established a session, client may request a file transfer via the control connection. The server validates the request and opens a new TCP connection back to the client which is used to transfer the file. Each file transfer requires the set-up of a new TCP connection. TCP guarantees the reliable delivery of the file.

b) Discuss the role played by cacheing and proxies in the world-wide web. What impact, if any, do proxies have on user-level session maintenance?

[9 marks]

Caches of frequently accessed pages speed up operation across slow sections of the Internet. They also help the network by minimising the amount of data transferred.

Not all data can sensibly be cached. There is no point cacheing dynamically generated content. Some files may be updated frequently and so should not be cached. A server may indicate in the HTTP header whether or not a page should be cached.

Most browsers keep a cache of pages on the local disc. The local cache will be searched before a request is made to the server. Sometimes the currency of the cached version is checked with the server.

Some sites deploy proxies which maintain site-wide caches. Browsers send requests initially to the proxy which returns the cached version if present. The strategy is effective where many users at a site access the same pages.

Cookies are an end-to-end mechanism. Proxies should not cache cookies nor should they reply to cookie requests on behalf of users.

c) Tag bytes in the ISO Basic Encoding Rules (BER) are constructed as follows:

|Bit |8 |7 |6 |5 |4 |3 |2 |1 |

| | | | |

Where:

Class: 00 = UNIVERSAL, 01 = APPLICATION

Type: 0 = Primitive, 1 = Constructed

Tag Value: 00010 = INTEGER

10000 = SEQUENCE

00100 = OCTET STRING

Given the following ASN.1 syntax definition:

IpAddress ::= [APPLICATION 0] IMPLICIT OCTET STRING (SIZE (4))

SocketAddress ::= SEQUENCE {

ipAddr IpAddress,

port INTEGER (0..65535)

}

Illustrate how an instance of SocketAddress would be encoded for transmission.

[7 marks]

There should be a correct interpretation of IMPLICIT and the INTEGER SIZE. Possible answer (in hex)

30 0A SEQUENCE

40 04 80 10 08 44 IMPLICIT IpAddress 128.16.8.68

02 02 12 34 INTEGER 0x1234

This would be transmitted as 30 0A 40 04 80 10 08 …

4. The diagram shows two hosts A and B communicating via a router R.

[pic]

A is transmitting data packets to B of length 200 bytes (including 40 byte headers). B is replying with acknowledgement packets of length 40 bytes. The time-sequence diagram below shows one exchange.

[Assume throughout part a) that no errors occur and that all parties may overlap transmissions and receptions. Note also that processing and propagation times are assumed to be negligible].

[pic]

i) Assuming that A transmits continuously (i.e. no flow control), describe the evolution of the system over the next few packets and calculate their round-trip times as observed by A.

A queue will build up at the router.

RTT for the first packet is 36 ms

Transmission of the second data packet on the A-B link will begin at 5ms

Transmission of the second data packet on the R-B link will begin at 30ms. Its ack will reach A 25 + 5 + 1 = 31 ms later, i.e. at t = 61 ms. Thus RTT is 61 –5 = 56ms

Clearly behaviour is governed by the data transmission time R-B (25 ms). Thus acks will reach A at 25 ms intervals.

Since packet transmissions at A begin at 5ms intervals, RTTs will increase by 20ms per packet – i.e. 36, 56, 76, 96 etc.

[6 marks]

ii) Assume now that A’s transmissions are constrained by an idle-RQ protocol. What effect does this have on the round-trip times? What effect does it have on the data throughput of the system? [4 marks]

RTTs are now constant since no queue builds at the router.

Throughput was constrained by capacity of R-B link that was continually busy. This implies 64 kbps or 64 * 160/200 = 51.2 Kbps of data

With stop and wait, one packet is transmitted every 36ms, so throughput is 160*8/36 = 35.5 Kbps

iii) Assume now that A’s transmissions are constrained by a continuous request protocol with window size w packets where w is big enough to allow continuous transmission on the R->B link. Assuming that protocol operation has reached a steady state, at what rate will acknowledgement packets arrive at A and what will be the state of A’s transmit window each time an acknowledgement packet arrives? [4 marks]

Continuous transmission on the R-B link implies one data packet arrives and one ack is generated each 25 ms. Therefore acks arrive at A at 25 ms intervals.

Clearly A can transmit data packets more frequently than this and will do so until its window runs out. Therefore, each ack changes the transmit window from 0 to 1 and allows the transmission of one data PDU.

a) Briefly describe the flow control mechanism used in the Internet Transmission Control Protocol (TCP). [5 marks]

Transmitter has a window measured in bytes.

Transmitter may have bytes outstanding up to the limit imposed by the window. When this limit is reached transmitter must pause.

Receiver sends acknowledgements which state which bytes have been received (acks are cumulative). Acks also include a new window size.

If receiver allocates a large enough window then transmitter never has to pause.

If receiver allocates a small (esp. zero) window, then transmitter will have to pause or halt.

Receiver may now send a larger window to allow transmit rate to increase.

i) A TCP transmitter is in slow-start, using a segment size of 1460 bytes and has just successfully sent 16 segments. It will now carry on transmitting. Assuming an RTT of 100ms and that its next windows worth of transmission are all successfully transmitted and acknowledged, evaluate the transmission rate in bits/second. [3 marks]

Next window will be 32 segments (slow start), which will be delivered in a single round-trip time, that is 32 ( 1460bytes ( 8bits/byte / 0.1s = 3 737 600 b/s ( 3.7Mb/s.

[Question 4 continued on next page]

[Question 4 continued]

b) Describe the operation of a token bucket scheme that may be used to shape traffic from a source. [5 marks]

A token bucket specification has two parameters; the token replenishment rate r, and the bucket size b. Logical tokens drip into the bucket at a constant rate r bytes/s. A packet of length s bytes logically consumes s bytes of tokens when it leaves. If there are not s bytes in the bucket, then the source is "not conforming" and transmissions must wait. If there is a break in packet generation then the bucket fills - but only until it contains b bytes of tokens.

i) Host A is transmitting data to host B across a link with a capacity of p bps. Host A must conform to a token bucket of size b bits and a replenishment rate r bps. Derive a formula for the maximum time at which A may transmit at the full link speed. [4 marks]

In the best case A has a full bucket of tokens.

Suppose the maximum burst time is t sec. In this time pt bits are transmitted and rt token bits arrive – so a total of b+rt token bits are consumed.

We must have pt ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download