Telecommunication Networks - formulario ed esercizi

Message delivery time with CS connections

T = ^M/_R + B T_p + N t_c

Message delivery time with PS connections

T = ^N/_R + t_p + N t_c

Message delivery time with PS + pipeline

T = T_p + N t_c + (N-1) ^M/_K R + ^M/_R + K t_M/_R

Message delivery time with PS + pipe + bottleneck

T = T_p + N t_c + (N-1) ^M/_{K Rh} + K t_M/_R2

h = index of bottleneck link

Optimal K with bottleneck

K = ^N/_{∑ (1/h-ind a1)^NS/Rh}

Delay

R: delay

delay = RTT

delay end-to-end ⇒ H bits can be transmitted simultaneously

BDP

Bit rate R₀

Throughput S ⇒ S = R₀

Goodput S_g

Message delivery time with CS connections

T = ^M/_R + 3T_p + NT_c

Message delivery time with PS connections

T = ^N-M+H/_R + t_p + NT_c

Message delivery time with PS + pipeline

T = t_p + NT_c + (N-1)(^M/_R + ^H/_K)

Message delivery time with PS + pipe + bottleneck

T = t_p + NT_c + (N-1)(^H/_K) ¹/_min(1/λi) + ^KH/_Rn

n = index of bottleneck link

Optimal K with bottleneck

K = √^N/_∑h=n ( ^R_h/_H+λIh )

BDP

R: delay

Delay = RTT => PIPE CAPACITY

delay = end-to-end => H bits can be transmitted simultaneously

Bit rate R_o

Throughput S = > σ = o

S_g = S_out / IP_OUT = S_i OVERHEAD

S_OUT = IP_OUT

Poisson

P_X(n) = ^λn/_n! e^-λ

E(n) = λ

Geometric

P_X(n) = p(1-p)ⁿ

p = succ. probab.

Esponenziale

f_X(x) = μ e^-μx

E(x) = ¹/_μ

Problem 1

M = # bits of a message

K = # packs the message is divided into

H = # bits of header

N = # of links

T_e = elaboration time of each

R_k = bit rate of each

• Find the pipe capacity, assuming that the transmission of the ACK only takes the propagation/elaboration time
• Find the max throughput

Γ = T₁ + (K - 1) T_f

T_f = Σ_k=1^N(T_p + T_e + ^H⁄_K)_Rk + (K - 1) ½ ^N_Rk½∑_k=1^Nmin {R_k, x∑k_{k - 1},N_k}∑min {R_N

T₁ = T_P - ^{K, H + M}⁄R^N→ RTT = 2 · T_p∑_k=1^N½→ C = RTT · min {Rn, _{^M⁄H + ½K}}

I'm sorry, the image you provided is blank, and there is no text to transcribe.

Token bucket dimensioning

1R2C

Given

L = fixed size of packets [byte]

R_L = regular packs arrival rate [_packets/^s]

λ = intensity of the Poisson process [_events/^s]

R_z = burst generation rate [_packets/^s]

D = duration of the burst event

r = [R_L: λ : (R_z - R_L) : D : λ ] L = [R_L + (R_z - R_L) : D : λ ] L [Average Token rate]

p = R_z : L [Peak rate]

b = (p - r) : D = Tok bucket size

β = [buffer size]

d_l = ^b/_{λp - r} [Maximum burst length]

t_z = ^{B + b}/_{λp - r} [Max burst period]

d_m = ^B/_r [Delay introduced by filter. Happens when λp >> burst duration]

I'm sorry, but it seems the image you provided is blank or does not contain visible text. Can you try uploading a different image or check if there's text present?

Describe the steps needed to send an email from host_X to host_Y

Internet mail

(Pass from router to another network)

• NIC realizes there’s a new device connected. PHY entities of H_X, L2 Switch negotiates the PHY layer parameters and sets up PHY layer setup.
• DHCP DISCOVERY message sent by HOST_X

Ethernet frame

DHCP DISCOVERY

PAYLOAD

Source MAC Address = Host_X MAC address

Destination = FF:FF:FF:FF:FF:FF

• Switch learns Host_X MAC
• DHCP server sends back a DHCP OFFER message

ETH-frame

SRC MAC = DHCP Server MAC

DST MAC = FF:FF:FF:FF:FF:FF

• Host_x sends DHCP REQUEST (in broadcast)
• DHCP server sends DHCP ACK (in broadcast)
• Host_x knows its own IP address = IP_x

Netmask (NM_x)

Default gateway IP address (IP_GW)

Local DNS IP address (IP_DNS)

• Mail client needs to resolve the mnemonic name of the outgoing mail server and its IP address.

IP_MAIL = ?

It sends a DNS QUERY Message to the DNS Server and now the packet can be sent.

IP_DNS cannot always be solved locally, so the query needs to go at least through IP layer.

ETH frame

IP dst: IP_DNS

IP src: IP_X

SRC MAC: MAC_X

DST: call ARP agent

UDP

SRC port: hⁿ

DEST port: nⁿ WELL KNOWN

The IP layer entity will call ARP agent to find the MAC Address associated to IP_DNS

ARP Agent broadcasts ARP REQUEST for IP_DNS

ARP Agent at the target host replies with a REPLY MESSAGE that is sent to the MAC Address: MAC_X and it carries MAC_DNS

The DNS server gets the query, checks the DNS table and retrieves the IP address associated to outgoing mail server name (e.g. mail.dei.unipd.it)

Sends back a DNS Reply message with IP_MAIL — it’s now a DNS REPLY

Mail client connection

Tries to contact the outgoing mail server by establishing a TCP connection.

It sends a TCP SYN segment to the IP_MAIL, port ₂₅ (Well known port number for _SMTP server).

TCP SYN

SRC Port = Ephemeral

Dst = 25

DST IP: IP_MAIL

SRC IP:

IP agent sees that IP_MAIL can be reached through indirect forwarding and asks ARP agent to find MAC address of IP_GW

Ethernet

TCP SYN

SRC MAC: MAC_X

DST MAC: MAC_GW

I'm sorry, I'm unable to provide the transcription as there is no visible text in the image. If you have another image or further information, feel free to share it!

Configure the network with the following services

Web page

Email

Internet cloud service

3 private sub-networks of >100 networks each, which should be able to freely communicate one another, access the web and mail server of the company and access the public internet only for HTTP services.

• What is the smallest block of public IP addresses that the company need to acquire?
• Which other devices are needed to configure the network?
• Draw schematically the connections among the network devices and assign IP addresses and network functionalities to all devices.
• Write the routing / NAT tables when needed.

LAN A: 192.168.1.0/24

LAN B: 192.168.2.0/25

LAN C: 192.168.3.0/25

DHCP: 192.168.1.253

We need public IP addresses for:

DNS, WEB, MAIL, R0.eth1 (NAT), R1.eth0

We need at least a block of size 8, e.g.:

1.255.255.249/29 WEB

1.255.255.250/29 MAIL

1.255.255.251/29 DNS

1.255.255.252/29 NAT1 R0.eth1

1.255.255.253/29 NAT1 R1.eth0

1.255.255.254/29 future

1.255.255.248/29 network

Routing tables

R1

dest. network: 1.255.255.248

net mask: 255.255.255.248

nexthop: *

interface: eth0

dest. network: 0.0.0.0

net mask: 0.0.0.0

nexthop: ?

interface: eth2

R2

dest network: 1.255.255.248

net mask: 255.255.255.248

nexthop: *

interface:

dest network:

net mask: see PDF

nexthop:

interface:

EX 1- 100 Mbps MAC (Layer)

tg = 0- R_b = 1 Mbit/s

tc = 1ms

LAN_a 30.20.2.0 /25

• Assign IP addresses and netmasks where needed in the network

H₁ IP_a 30.20.2.1 /25

longest mask guaranteeing 3 hosts is 255.255.255.248

H₂ IP₂ 30.90.9.2

R₁ eth0 IP₃ 30.20.2.3

R_a eth1 10.0.0.2 /30

Broadcast address: 30.20.2.7

R_b eth0 10.30.3.9 /29

Routing tables of R_a

Destination NET address

Netmask

Next hop

Interface

30.20.2.0

255.255.255.248

eth0

0.0.0.0

0.0.0.0

10.0.0.1

eth1

H₁ sets up a TCP connection with the server

MSS = 1250 bytes.

Find RTT.

H = H_IP + H_TCP = 20 + 20 = 40 bytes

RTT = [ ((H + MSS)/R₀/8 + τ₀)⋅3 + ((H + MSS)/R₂/8 + τ₂) ] _{Forwarding Time} + 3 H/R_0/8 + H/R_2/8 - τ₂ = _{ACKing time} = 30 ms

Find the pipe capacity

C = RTT ⋅ (lowest rate = R_L ) ⋅ 1/ ((MSS + H)⋅8) = 1,26 segments

Time to transfer K=10 segments from the server to the host

S = C/RTT [segments/s]

R/S = K/C ⋅RTT  _{if always valid if PIPE is always full, CWND > PIPE}

In this case the pipe capacity is very small and the congestion window accrues after the first RTT, if the buffer at R₀ is large enough the connection will always be used at full rate.

T = 3 ⋅ [ H/8/R₀ ⋅ 3 + H/8/R₂ + τ₂ ] + RTT + (K-1)⋅ (H + MSS)⋅8/R₁

If R > ] RTT ⋅ K/C = T ⋅ R/RTT + (K-1) ⋅ (H + MSS)⋅8/R_L

RTT ⋅ R_L/R_L = 8 (MSS+H) ⋅ K

UDP packets

t=0. 2 packs UDP queued a R₄ with destination N₂. The server has 3 UDP packets to be sent to N₁ and 5 UDP packets to be sent to N₂. ∀ packs same size of L = 1024 byte of each of UDP packets sent by the server.

T_{1^st pack} = (H_s + L)⋅8/R₀ + 3⋅L_a + (H_s + L)⋅8/R₁

T_{2^nd pack} = [(H_s + L)⋅8/R₁ + (H_s + L)⋅8/R₀ + (H_s + L)⋅8/R₁ +2⋅L⋅C_a +2⋅(H_s + L)⋅8/R₀

T_B = (H_s + L)⋅8/R₄ + (H_s + L)⋅8/R₀ + (H_s + L)⋅8/R₁ ⋅ C_a + 2⋅(H_s + L)⋅8/R₀ =>= T₂ + (H_s + L)⋅8/R₂

In general T_n = T_n+1 + (H_s + L)⋅8/R₁

H_s = 20 => 28 byte

6 byte

UDP header

IP header

I'm sorry, but the image doesn't contain any visible text for transcription.

Packet loss probability and throughput

Pi = packet loss probability at PHY layer

Ri = Tx rate of i^th link

Ci = one way, prop. delay of i^th link

Find the end-to-end long-term average throughput when:

A) A sends UDP packs and there is no recovery mechanism

B) Each link implements layer 2) ARQ S&W recovery mechanism

C) A and B implement a end-to-end SR ARQ

D) Find the average delivery time of a packet for previous case.

Solution A

Let λ_i be the max flow that can be offered to the i^th link from the upstream link.

The average throughput across that link will be

μ_i = min(λ_i, Ri) (1 - Pi)

since the output can't exceed the input rate and the speed of the link. The packets crossing the i^th link are dropped with probability Pi.

The packets that survive will flow into the downstream link, so that we have

λ_i+1 = μ_i

The Throughput is

S₁ = µ_k = (1 - P_e) · min (R_n, λⁿ){(1 - P_e) · min (R_k, (min (R_k-1, λ^n-1)) · (1 - P_e))

Recursively = min {n / n_L (1 - P_i) · R_j), k = 1, ..., n} [bit/s]

B)

Introducing layer-2 ARQ S&W, the different links always deliver the packets to the downstream link but with a random delay. From the upper layer, this is perceived as a variable bit rate. Denoting by L the MAC-layer packet size and assuming the MAC-Layer ACKs have negligible length, we can get the average packet transmission time over the i^th link as:

T_i = (L / R_i + 2L_i) · (1 / 1 - p_i) [s]

The throughput offered by the i^th link to the upper layer is then:

R̄_i = L / T_i

= L (1 - P_i) · R_i · L / L

= L / R_i + 2L_i · R_i · L / L

= R_i · (1 - P_i) · 1 / (1 + 2R_ir_i) / L [byte/s]

- Finally, the max end-to-end average throughput is

C1

When applying the end-to-end SR-ARQ the throughput is the same we obtain in case 1, when using no recovery mechanism.

Indeed the DLLs of the different links will be able to deliver packets to the destination with a max average rate of S_I [1 - p_I].

The SR-ARQ mechanism simply determines which packets have to be retransmitted over such a channel, without introducing any idle time or useless retransmission.

Therefore the overall throughput will still be equal to SI with the difference that, in this case, all packs generated by the application in A will be sooner or later delivered to B.

D1

The overall delay of a packet since the first time it is transmitted to the time it is successfully delivered to B (assuming ideal ACK and E2E setting), is given by:

RTT = ⁿ∑_i=1 τ_i + T_FWRD

T_FWRD = ⁿ∑_i=1 (τ_i + ¹/_Ri)

NOTE if also ACK packs can be dropped with equal probability as data packs then we would get

T_exe = ¹/_{∏ⁿi=1 (1-Pi)} (RTT + T_FWRD)

Token Bucket Filter

1) Consider a Token Bucket Filter used as traffic policer. Assume that each token is worth the transmission of one pack of L bits. Find the token bucket parameter that give an average i. rate R and a peak rate Rp. For a time T_burst:

Policer g_t = ^R/_L average token rate

b = (^R_p/_R - g_t) T_burst bucket size = (^{R_p - R}/_R) L T_burst

2) Assume that packets arrive to the TBF according to a Poisson process of rate \(\lambda = 0.1\); g_t: A new tok is generated every T_g seconds. Starting from time t=0 IF at time t₀ = T_g, the bucket is empty, what's the probability that the next packet is marked by the TBF as "excess"?

Solution

The time to get a new tok is T_g = ^L/_R; Since the pack arrival process is Poissonian, the inter-arrival times are i.i.d exponential random variables (of parameter \(\lambda \)) and hence are memoryless (which means that the time before the next arrival starting from t₀ = T_g is still exponentially distributed with param \(\lambda \) irrespective of the time elapsed since the previous arrival at time t₀. Therefore the next pack will be marked as "excess" if it arrives before a new fork is available, i.e. if τ < T_fix. The probability of this event is hence:

P_r [ τ < T_fix ] = 1 - e^-λT_fix

= 1 - e^{-0.2⋅9⋅1/₉₆}

= 1 - e^-0.1₂ ≈ 0.095

the same host are spaced apart by random time.

All packs of the same burst have the same destination that with probp = ₁/₂ is within the LAN while with 1 - p is in the outside ethernet.

Packs arrive to the LAN from the internet according to a Poisson process with λ = ? with uniform dest. to the LAN.

Find the average uplink and downlink traffic across links a, b and c.

Each host generates on average traffic

G_uplink = m . K . L / S [ ]

G_A = G_uplink

G_B = G_uplink (1 - p) + G . p

G_C = ₈/₇ G