Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 70 views

    Exercise Problems

    Uploaded by

    hari
    This document discusses convex sets and functions, utility maximization problems in communication networks, and statistical multiplexing and queueing. Specifically: 1) It asks which sets are convex and proves that the intersection of convex sets is convex. 2) It presents two utility maximization problems - one with three users and the other with n routes - and asks to write the optimization problems and determine the optimal rates. 3) It asks questions about bounding the overflow probability in a queue, computing the average waiting time in a Geo/Geo/2 queue, and analyzing the service and delays under GPS and WFQ scheduling for two flows of packets arriving at a shared link.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Exercise Problems

    Uploaded by

    hari
    70 views2 pages
    This document discusses convex sets and functions, utility maximization problems in communication networks, and statistical multiplexing and queueing. Specifically: 1) It asks which sets are convex and proves that the intersection of convex sets is convex. 2) It presents two utility maximization problems - one with three users and the other with n routes - and asks to write the optimization problems and determine the optimal rates. 3) It asks questions about bounding the overflow probability in a queue, computing the average waiting time in a Geo/Geo/2 queue, and analyzing the service and delays under GPS and WFQ scheduling for two flows of packets arriving at a shared link.

    Original Description:

    problems

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses convex sets and functions, utility maximization problems in communication networks, and statistical multiplexing and queueing. Specifically: 1) It asks which sets are convex and proves that the intersection of convex sets is convex. 2) It presents two utility maximization problems - one with three users and the other with n routes - and asks to write the optimization problems and determine the optimal rates. 3) It asks questions about bounding the overflow probability in a queue, computing the average waiting time in a Geo/Geo/2 queue, and analyzing the service and delays under GPS and WFQ scheduling for two flows of packets arriving at a shared link.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    70 views2 pages

    Exercise Problems

    Uploaded by

    hari
    This document discusses convex sets and functions, utility maximization problems in communication networks, and statistical multiplexing and queueing. Specifically: 1) It asks which sets are convex and proves that the intersection of convex sets is convex. 2) It presents two utility maximization problems - one with three users and the other with n routes - and asks to write the optimization problems and determine the optimal rates. 3) It asks questions about bounding the overflow probability in a queue, computing the average waiting time in a Geo/Geo/2 queue, and analyzing the service and delays under GPS and WFQ scheduling for two flows of packets arriving at a shared link.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    1

    INDIAN INSTITUTE OF TECHNOLOGY TIRUPATI


    EE5202 COMMUNICATION NETWORKS

    I. C ONVEX S ETS AND C ONVEX F UNCTIONS

    1) Which of the following sets are convex? (Hint: sketch the form of these sets in <2 )
    a) A slab, i.e., a set of the form {x ∈ <n : α ≤ aT x ≤ β}.

    b) A rectangle, i.e., a set of the form {x ∈ <n : αi ≤ xi ≤ βi , i = 1, · · · , n}. (A rectangle is


    sometimes called a hyper-rectangle when n > 2.)

    c) A wedge, i.e., {x ∈ <n : aT1 x ≤ b1 , aT2 x ≤ b2 }.

    d) The set of points closer to a given point than a given set, i.e.,
    {x : ||x − x0 ||2 ≤ ||x − y||2 for all y ∈ S}
    where S ⊆ <n .

    e) The set of points closer to one set than another, i.e.,


    {x : dist(x, S) ≤ dist(x, T )},
    where S, T ⊆ <n , and dist(x, S) = inf{||x − z||2 : z ∈ S}.

    2) Show that if S1 and S2 are convex sets in <n , then S = S1 ∩ S2 is convex.

    3) Let S1 and S2 be convex sets in <m+n . Define their partial sum as


    n o
    S = (x, y1 + y2 )|x ∈ <m , y1 , y2 ∈ <n , (x, y1 ) ∈ S1 , (x, y2 ) ∈ S2 .

    Show that S is convex.

    4) Determine whether the following functions are convex, concave or neither:


    a) f (x) = min{x, 5} over S = <
    b) f (x) = log(1 + x2 ) over S = <+
    c) f (x) = ex − 1 over S = <
    d) f (x1 , x2 ) = x1 x2 on <2++ .

    5) Suppose f : < → < is convex, show that for any a < b


    b−x x−a
    f (x) ≤ f (a) + f (b)
    b−a b−a
    for all x ∈ [a, b].

    please turn over ...


    2

    II. U TILITY M AXIMIZATION


    6) Consider the network shown in Fig. 1. Assume that the link capacities are CA = CB = 1. The
    utility functions are U0 (x0 ) = log(x0 ), U1 (x1 ) = log(1 + x1 ), and U2 (x2 ) = log(1 + x2 ).
    (a) Write the utility maximization problem and determine the optimal rates.
    (b) What is the price q2 charged to user-2?

    Fig. 1: Problem 2.

    7) Consider a network with n links and n routes as shown in Fig. 2. Each link is of unit capacity.
    Let x = (x1 , x2 , · · · , xn ) denote the vector of rates where xr (r = 1, 2, · · · , n) is the rate allocated
    on route r. Assume log utility functions for each route, i.e., Ur (xr ) = r log(xr ). Write the utility
    maximization problem and determine the optimal rates.

    1 2 3 𝑛
    𝑥& 𝑥' 𝑥(
    𝑥)
    Fig. 2: Problem 3.

    III. S TATISTICAL M ULTIPLEXING AND Q UEUEING


    8) Compute a bound on the overflow probability P(q(t) ≥ B) if the arrivals {ai (t)} are i.i.d Bernoulli(λ)
    random variables.

    9) Compute the average waiting time in a Geo/Geo/2 queueing system.

    10) Consider a link shared by two flows, A and B. For simplicity, assume that the system starts at time
    t = 0, and the transmission time of a packet of length S is S time units. Packets belonging to the
    flows arrive at the link as follows:
    • Flow A : packets of length 8 arrive at time slots 5, 25, 45, and 65
    • Flow B : packets of length 5 arrive at time slots 0, 10, 20, 30, 40, and 50.
    a) Assume the link is operated under GPS. For each packet sent on the outgoing link, write
    down the time when the packet starts to receive service and the delay between the arrival and
    departure.
    b) Assume the link is operated under GPS. Calculate the percentage of the link used by each
    flow up to and including time slot 59.
    c) Repeat above two questions assuming WFQ is used.

    You might also like