Answer Key
6.829 Problem Set 1 with Solutions
-
University:
Massachusetts Institute of Technology -
Course:
6.829 | Computer Networks Academic year:
2020
-
Views:
27
Pages:
18
Author:
America Bradley
Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science
6.829 Fall 2002
Problem Set 1
September 10, 2002
This problem set has nine questions, each with several parts. Answer them as clearly and concisely as possible. You may discuss ideas with others in the class, but your solutions and presentation. must be your own. Do not look at anyone else's solutions or copy them from anywhere. Turn in your solutions in on Tuesday, September 24, 2002 in class,
1 Multiplexing
In this problem, we will compare statistical multiplexing to time-division multiplexing (TDM) to
understand the differences between packet switching and circuit switching.
In our statistical multiplexing scheme, packets of all sessions are merged into a single queue and transmitted on a first-come first-served (FCFS) basis. Our TDM scheme is the same as the one described during the first lecture (see the LI notes).
A switch is said to be work conserving if the only time it is idle is when there are no frames waiting for service.
1. Is our TDM scheme work conserving? What about our statistical multiplexing scheme?
Answer:
No, the TDM scheme is not work conserving. This is because TDM scheme schedules a slot for a session even if there is no data on that session (i.e. it wastes slots even though it could have scheduled transmission for some other session instead in that slot).
The statistical multiplexing scheme is work conserving. This is because it never wastes a slot as long as there is data for some session.
2. Let's study the impact of statistical multiplexing on quening delays. Suppose there are N concurrent sessions each with a Poisson traffic stream with rate A frames/second. Also suppose that frame lengths are exponentially distributed, such that the average rate at which frames are serviced at the switch is a frames per second (NA). What is the average delay seen by a frame in TDM and in statistical multiplexing? What is the physical interpretation of your result?
Answer: The average queuing delay for a FIFO queue with transmission rate Poisson with mean and arrival rate A is given by:
T See any book on queuing theory, or Bertsekas and Gallager, pg. 170.
Figure 1: Utilization of output link for Statistical Multiplexing (left) and TDM (right)
In case of statistical multiplexing, all the input streams are merged into one queue and served from there. Thus, the total input rate to this stream is NX. The service rate of this queue is 4. Hence, the average queuing delay per packet is given by:
T=NX
On the other hand, with the TDM scheme, the output stream is divided into N equal portions (time slots), one per input stream. Thus, each portion behaves like an M/M/1 (formal nota- tion for a queue with Poisson arrival and service processes) with arrival rate A and average service rate /N. Thus, the average delay per packet is:
= T N
Thus, you can see that the average delay in a TDM scheme is N times that in statistical multiplexing. This is because the TDM scheme is not work conserving.
3. Assume that all the sessions send frames at a simple constant bit rate and that there are A active sessions at a given point in time out of a possible N, sharing an output link. What is the utilization of the output link when the aggregate input rate for the A active sessions is u frames/second. Sketch this as a function of A for both statistical multiplexing and TDM.
Answer:
The plots are shown in Figure 1.
4. Explain why TDM has smaller variation in the delay of a frame through a switch, compared to statistical multiplexing. (This delay variation is sometimes called the jitter.)
Answer: TDM schedules each stream independently of other streams and assigus time slots for a stream at regular intervals. Hence, burstiness of data in one stream does not effect other stream. Thus, TDM has lower jitter than statistical multiplexing. This is the reason why
2
1. (a) 4.0.4.90. This IP address corresponds to a Genuity router that is participating in a BGP session with the Oregon router (as is clear from the routeviews home page). This means that the Oregon router has conducted a TCP session with the Genuity router (since BGP runs over TCP) over some physical port. The Oregon router, when it wants to send to the next hop IP address 4.0.4.90, simply sends out this same physical port. The information about which physical port to use is stored in the forwarding table (and was presumably populated when the router first came up or when the TCP connection with 4.0.4.90 was first initiated).
(b) Only 1, not including MIT (namely, it must traverse AS 1)
(c) No, it is not.
(d) Because MIT would rather send traffic cheaply over Internet2/Abilene, when it is allowed (which is when the traffic is between two educational institutions). MIT has a routing entry that directs traffic intended for U of Oregon (and other universities, presumably) to its Internet2 link. The traceroute likely does not match the AS path because the IP address-to-AS number resolution, in the traceroute, is accomplished via queries to a database that map IP addresses to the database owner's concept of AS. The AS numbers in the AS path are reported by the actual AS, and the database that maps IP addresses to ASes may no longer be aware of which ASes have which IP addresses (IP addresses can be resold). Moreover, there are cases in which the same logical AS uses different AS numbers. In this example, the queries to the database induced by the "A" option can only return one AS number, so it might be returning one different from what the AS reports as its own. In any case, note that the AS Path in the MIT table is logically the same as the one traceroute indicates the first hops are Harvard (10578 aka 1742), followed by Abilene/Internet2 links, followed by AS 4600, followed by two different AS mumbers that refer to slightly different pieces of the Oregon organization.
(e) The AS number for MIT appears to be 3
(f) 23
(g) The best route is the one with AS PATH 1 3. We cannot be totally sure why this route was selected as the best route. There are no LOCAL PREFs set for this route, by inspection. So BGP should select the route with smallest ASPATH length, but there are two such routes: (13) and (293 3). None of the other BGP attributes (e.g., ORIGIN, MED, BGP/IBGP, IGP path) appears to be relevant (since these two routes have the same state for each attribute or the attribute isn't relevant, as with MED, for comparing two routes that start at different ASes). One possibility is that the ROUTER ID criterion worked in (13)'s favor. Another is that, by inspection, (13) represents the path through the AS (1) with much more connectivity and reachability. The router may have an automated way of telling that the (13) route is more "credible", but we cannot be sure.
h) Aside from MIT's AS (3), all of the routes to MIT, except for (2933), have in common (
only AS 1. AS 1 is likely MIT's service provider.
(i) AS I corresponds to Genuity's IP network.
2. (a) (A (Ai & (1 (32m)))
(b) 192.0.32.0/20. This address corresponds to 16 class C networks (since class C networks are /24, and this is /20, representing a block of 16 class C addresses). The maximum number of routing table entries saved is 15 (16 networks minus 1 for the entry itself). We cannot infer the actual number of addresses that this CIDR address saves, just from the
11
Related Documents
- Lecture Note: Report Data
- Dynamic Programming, and How is it Used to Optimize Algorithmic
- Let’s Encrypt Now Being Abused By Malvertisers
- Processing of 2D RGB and Depth Data into 3D Space
- Introduction to Matlab Parallel Computing Tooblox Pt 3
- Traversing a Binary Tree: Depth & Breadth
- Introduction to LaTex
- Proof of the Master Theorem
- Introduction to Computer Science I Project 3
- A Brisk Introduction to LATEX
- COSC-311 Sample Midterm Questions 2
- COSC-311 Sample Midterm Questions 1
- Introduction to Computer Science I Project 3 Minesweeper
6.829 Problem Set 1 with Solutions
of 18
Recommended Documents
Report
Tell us what’s wrong with it:
Thanks, got it!
We will moderate it soon!
Free up your schedule!
Our EduBirdie Experts Are Here for You 24/7! Just fill out a form and let us know how we can assist you.
Take 5 seconds to unlock
Enter your email below and get instant access to your document