<b>An Example:</b>

Next: About this document Up: Probabilities and Random Previous: Expectations:

An Example:

Let's consider problem 3-20 of Tanenbaum. Because each node has many frames to send, at slot 0, they are doomed to collide. Assume a collision has occured in the first slot. Let be the number of collision rounds, including the successful round, required to have successful transmission. Clearly, is a discrete random variable. In order to obtain the mean value of , we need first to calculate the pmf of .

Clearly, by the definition of , is impossible:.

is when the second round succeeds after the first failed round. In the second round, each node choose one of two delay possibilities: {0,1}with probability , respectively. If both nodes choose to delay by 0 slot, with probiability , they will collide again, or if both nodes choose to delay by 1 slot, also with probiability , they will also collide. Therefore, the probability that the the second round fails is given by: . And the probability that the second round succeeds is the compliment of the above probability: . Therefore:

Since .

Similarly the probability that the third round succeed

For the third round, the random delay is one of 4 possibilities with equal probability. The probability of collision in any particular slot is given by: . Therefore the probability that the third round fails is given by: , and the probability that the third round succeeds is given by: .

Using similar arguments,

Let's continue a few more steps to see what rule we can come up with. For round four, the random delay is one of 8 possibilities with equal probability. The probability of collision in any particular slot is given by: . Therefore the probability that the third round fails is given by: , and the probability that the third round succeeds is given by: .

Using similar arguments,

You should be able to see the pattern now:

Unfortunately, no closed form expression exists for this summation.

35.468 Computer Communications Networks

Spring, 1994

Ji Zhang

Homework No. 1(Due Feb. 3)

Read Chapter 1 and 2. If you want to learn more about the most recent development in computer networking, you can also read some of the magazines and journals. The most appropriate ones are IEEE Spectrum Magazine, IEEE Network Magazine, IEEE Communications Magazine, IEEE Journals on Selected Area of Networks. On these publications, you will also see announcements of major network conferences, tradeshows, seminars, new products, new technology breakthroughs, etc.

From Chapter 2 problems:

Do problem 3;
Do problem 4;
Do problem 5;
Do problem 11;
Do problem 18;

35.468 Computer Communications Networks

Spring, 1994

Ji Zhang

Homework No. 2(Due Feb. 22, Tuesday )

The main focus of this chapter is the study of some of the most popular LAN protocols today. There are many books devoted specifically to the subject of LAN networking. If you want to dig deeper into the subject in performance analysis issues, you can read the book by Bertsekas and Gallagher. Many other practical books exist explaining the actual hardware and software implementations of various protocols.

I'll add some more problems to this homework. So please watch for the updates on this file. Some of the problems require some knowledge of probability. If you don't have any background, try to read some books on the subject. The book by Alberto Leon Garcia: Probability with Applications for Electrical Engineers, is a good one to read.

From Chapter 3 problems:

Do problem 3;
Do problem 4;
Do problem 5;
Do problem 9;
Do problem 13;
Do problem 16;
Do problem 19;
Do problem 20;
Do problem 23;
Do problem 26;
Do problem 29;

35.468 Computer Communications Networks

Spring, 1994

Ji Zhang

Homework No. 3(March 22, First class after the break )

IMPORTANT: The midterm exam will be given on March 24, Thursday, which is the SECOND class after the Spring break. It will be one and a half hours in class exam. The exam will be closed book, closed notes. It will cover all the topics covered in class, up to the end of Chapter 4 (topics not discussed in classes will not be on the exam).

From Chapter 4 problems:

For each of the following generator polynomials for CRC, , which corresponds to . and , which corresponds to , decompose it into two parts: , where is the primitive polynomial.
Do problem 1;
Do problem 2;
Do problem 6;
Do problem 7;
Do problem 9;
Do problem 10;
Do problem 14;
Do problem 19;
Do problem 21;

35.468 Computer Communications Networks

Spring, 1994

Ji Zhang

Homework No. 4, Due Thursday, April 21, 1994

ATM is based on statistical multiplexing. Each of the ATM links can take many virtual circuits(VC). VCI/VPI together can be used to identify a VC. What's the maximum number of VCs in any ATM link? This number is the size of entries in the VC lookup table for each port in the ATM switch.
In an ATM cell, VCI/VPI identifies the label for the channel being carried. Explain why there is no need to include source address in the ATM cell header.
An ATM switch contains 16 ports, each port has a data rate of 155Mbps.
1. Calculate how many ATM cells each switching port has to process in a second.
2. Calculate the size of the VCI/VPI lookup table for the entire switch;
3. Calculate the number of VCI/VPI table lookups per second for the entire switch;
4. If only VPI is used for the switching, what is the size of the VPI table for the entire switch?
  .
Suppose that in the CS (convergence sublayer) 8bytes of header and trailer are added to each CS PDU(protocol data unit, used to denote a frame of CS data), and the header and trailer added to each SAR PDU is another 4bytes, Suppose that each CS PDU (with head/trailer already included) is broken down to an average of SAR PDUs, which will be further encapsulated in ATM cells (another 5bytes header). Assume that the probability of ATM cell loss is given by , and the cell loss events are independent of each other. Lost ATM cells are not retransmitted. Assume that the CS PDU is considered lost (or unrecoverable) if one or more ATM cells are lost.
1. Find the amount of processing overhead, measured as the percentage of traffic that are headers and trailers. All headers and trailers in CS PDU, SAR PDU and ATM cells should be counted. Express the overhead in terms of and evaluate the value when .
  when
2. Find the probability that a CS PDU is lost . Hint: the number of lost cells is binomially distributed with parameter .
  where
3. If a CS PDU is lost, the entire CS PDU has to be retransmitted, and let be the number of transmissions for the successful delivery of a CS PDU. Clearly, is a random variable. Use to find the average value of : . Hint: this number is a geometrically distributed random variable expressed in terms of .
4. Find the overall overhead (in percentage) due to both the additions of headers/trailers and the retransmissions of errored CS PDUs. This overhead is expressed in terms of .
5. Find the value of , , which gives the maximum overall efficiency, and express it in terms of . Evaluate the value when and when . Hint: take the derivative with respect to and let the result be zero, then solve for from the equation.
Overall overhead(expressed in terms of ):

Take the derivative:

Simplify:
where ,

Solving for gives:

Only one of them is positive:
when , the value is 1348. When , the value is 13. This can be better seen in the following plot.
Using the program to do:
```
ping wiliki.eng.hawaii.edu
```
and
```
ping princeton.edu
```
observing the first 2000 responses (you type the command only once, but observe the first 2000 lines of output), and plot the histogram of the route trip delay (given by the field), with X-axis being the delay in intervals of and Y-axis being the number of responses that fall into that interval.
You can send the output into a file, say, ,
```
ping wiliki.eng.hawaii.edu > output &
```
and then extract the last column of by using the or programs, which are available on any UNIX system.
For example, you can do:
```
rm temp
awk '{print $7}' output >temp
cut -c6- temp >wiliki.graph
```
contains all the delays in raw numbers.
Because you are 'ing two different machines, two different histograms are generated. You should plot them on the same graph.
You can use any of the plotting packages, such as , , or (I'm only familiar with the first one, but any others are acceptable).
The results I got is given by Figure . The C codes I used to generate the histogram is given by the following:
```
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_PIN 100

main (int argc,char *argv[])

{ 
FILE *fin, *fout;
int c,i,hist[MAX_PIN];
char *s1, *s2;
for (i=0;i<MAX_PIN;i++) hist[i]=0;
if (argc<2) {printf("Arguments needed. Exit \n");exit(0);}
s1=argv[1];
s2=malloc(sizeof(argv[1]));
for (i=0;i<strlen(argv[1]);i++) 
{
*(s2+i)=*(argv[1]+i);
}
 
strcat(s1,".graph");
strcat(s1,"\0");
strcat(s2,".hist");
strcat(s2,"\0");

fin=fopen(s1, "r");
fout=fopen(s2, "w");
while (fscanf(fin, "%d", &c)!=EOF )
{
i=c/10;
hist[i]++;
}
for (i=0;i<MAX_PIN;i++)
{
printf("%d %d \n", i, hist[i]);
fprintf(fout,"%d %d \n", i*10, hist[i]);
}
fclose(fin);
fclose(fout);
}
```
From this graph, we can see that at least for this measurement, the round trip delay for is greater than that of , even though the actual distance comparison is the opposite. This shows again that distance may not be the best metric as the cost of routing, especially when time sensitive traffic is to be carried.
Note that sometimes the remote machines may be down, when that happens you will see no response on your screen, then the respond with a message saying that there is no response from the remote site after certain seconds. You should try to do it in another time.
Given the following diagram, find the shortest path from node to node using Dijkstra's shortest path algorithm. You should write down each iteration similar to the one on the note. Use the worksheet included here and draw more graphs if you don't have enough.

35.468 Computer Communications Networks

Spring, 1994

Ji Zhang

Homework No. 5, Due May 6, Friday, 2pm, 1994. Late submissions will absolutely not be accepted.

This is the last homework assignment. The final exam will be given on May 11, Wednesday, 9am-12pm, RI 203. You may bring with you to the exam: text book, computer classnotes, 2 crib sheets, but no other notes or homeworks are allowed.

We can not cover all the topics I had in mind at the beginning of the semester. For example, we did not address issues in very high speed network protocols (gigabit network), all optic networks. Some other topics that are closely associated with computer networking include: data syntax representation, data compression, data encryption and security. These belongs to the next upper three layers: session, presentation and application layers. They are usually closely associated with the specific operating systems and applications, and are not considered as part of the networking research. But recent rapid development in multimedia networking and commercial use of the Internet has made it very clear that these research issues are absolutely essential in the design of network based applications. Such examples include video and image compression algorithms, and data encryption, digital data signature and authentication, etc. Research and development in this area, in association with networking industry, has become the fastest growing sector of industry.

Let's show that the superposition of two independent Poisson processes, and , with rates and , respectively, gives another Poisson process. To see this, we want to prove for any , is still a Poisson process with rate . Because of the independence assumption, we can write
1. Use this result to show that is still Poisson distributed with rate .
  
  This shows that indeed, is still Poisson distributed. More is needed to prove that is actually a Poisson process, which we will not do here. Many of you used the expression of for Poisson distribution, which is due to a typo in my note, the correct expression should be: . But full credit will be given if the derivations are correct.
2. Write down the probability density function (pdf) for the interarrival times of ;
Follow up on our discussion in class on Little's theorem, let's consider a system described in Figure , where we have three independent general arrival processes, 1, 2 and 3, with arrival rate , and average system time within the system of for , respectively given by:
1. Find the average number of packets in the system .
  
  where , and
  Therefore,
2. Find the average system time for an average packet;
A packet arrives at a transmission line every seconds with the first packet arriving at time 0. All packets have equal length and requires seconds for transmission where . The processing and propagation delay per packet is seconds. The arrival rate here is .
1. Find the system time
2. Using Little's theorem to find the average number of packets in the system
Because packets arrive at a regular rate (equal interarrival times), there is no delay for queueing, so that time a packet spends in the system (including the propagation delay) is
According to Little's Theorem, we have
Consider the system which is the same as except that there can be no more than packets in the system and packets arriving when the system is full are lost. Use the balance equation technique derived for queues to show that the steady-state occupancy probabilities are given by:

Proof: this problem is proven very much like what I did in class, except that there are only finite number of balance equations:

Therefore,
Explain why lost TCP acknowledgements do not necessarily force retransmissions.
Because if the sequence number in the next acknowledgement is increased from the last acknowledgement seen, it's an indication that the segment with lost acknowledgement has been received anyway.

Rensselaer Polytechnic Institute
Electrical, Computer and Systems Engineering Department
35.468 Computer Communications Networks

Midterm Exam
(Closed book, closed notes, two page crib sheets allowed.)
(85 minutes, Good Luck!)
March 24, Thursday 1994

.0in NAME_______________________
.5in

1. (5 points) Suppose that a digital sequence 101000111111111111000 is to be enclosed in a data link layer frame for transmission. Using bit-oriented framing technique (using 01111110 to signal the start and end of a frame), write down the entire frame, including the start and end of frame bit patterns. You should enclose the inserted binary digits in .
2. (5 points) Repeat the above problem, but use character based framing. Assuming each character has 3bits and DLE=000, STX=ETX=111, write down the bit stream, including both start and end of frame bit patterns.
  Answer:
  a). (01111110)10100011111(0)11111(0)11000(01111110)
  b). (000111:DLE-STX)101000(000:add another DLE) 111111111111000(000:add another DLE)(000111:DLE-ETX)
1. (5 points) A physical channel has a bandwidth of 2000, and a signal to noise ratio of , what is the maximum data rate, (in ), the channel can carry?
  Answers:
2. (5 points) Explain briefly the meaning of .
is the maximum rate at which channel can carry digital information with arbitrarily small error probability.
(5 points) Explain why is used as the basic rate for ISDN;
Answer: Because ISDN is based on TDM technology. TDM was developed to carry digital voice, which requires 8bit/sample at 8000 samples/second sampling. This gives 64 as the basic digital rate.
A large population of ALOHA users manages to generate 50 requests/sec, including both originals and retransmissions. Time is slotted in units of 40.
1. (5 points) What is the probability that the first attempts all result in collisions? ()
2. (5 points) What is the probability that the channel is idle?
Answer: , the probability that there are transmissions in the channel in any slot is given by Poisson random variable: .
This problem is vague in that we could assume that the attempts are by the same user, with no-activity slots in between each attempts. We could also assume that there are consecutive collision slots. Therefore, full credit is given if either of the above assumptions are used.
Under assumption 1, in each of the attempts that the tagged user tries, at least another user is also transmitting, with probability , therefore, the event that consecutive attempts fail has probability .
Under assumption 2, In any slot, the probability that the slot is idle is given by , and the probability that the slot has one active user is given by . Therefore, the probability of collision is the compliment of the above events: . consecutive such collisions has probability: .
Probability of idle channel is easy: .
(5 points) Describe the steps required to add a new node in a token bus network;
- When the ring is established, each station knows the physical addresses of its predecessor and successor. Therefore, no ambiguity exists over the order of token passing;
- Periodically, token holder issues the SOLICIT_SUCCESSOR{ownaddress, successor's address} message.
- If two or more new stations contend to be successor, contention algorithm similar to that of CSMA/CD is used to choose one successor (fortunately, this doesn't happen very often);
- Only one station may be added for each token rotation;
In an FDDI network, suppose the target token rotation time , and there are two nodes, node 1 and 2, on the network with , . Transmission rate is 100 and around-the-ring propagation delay is 20.
1. (5 points) Suppose that both nodes in the network are fully loaded with high priority data, what is the actual token rotation time ?
  40+50+20=110ms
2. (5 points) Suppose that both nodes in the network are fully loaded with low priority data but have no high priority data, what is the actual token rotation time ?
  100ms
3. (5 points) Suppose that both nodes in the network are fully loaded with high priority data, what is the efficiency ?
  90/110
4. (5 points) Suppose that both nodes in the network are fully loaded with low priority data and have no high priority data, what is the efficiency ?
  80/100
To solve these problems you DO NOT need to use the inequalities given on our class notes. (There are some confusions over the notations which I will fix later.) What you do need to know is how FDDI allocation bandwidth to high and low priority traffic and the roles of and in this process.
Answers: Basically, is the maximum amount of time node can transmit high priority traffic. includes delays to the next node. The aggregate round trip delay is 20.
Efficiency is given as the ratio of useful transmission over actual token rotation time.
Note that the actual token rotation time is not the same as the target token rotation time. Some of you used the target token rotation time to calculate the efficiency, which is incorrect.
1. Assume that low priority traffic is zero, then the actual token rotation time is 10 ahead of , i.e., . If we assume that the ring is also fully loaded with low priority traffic, then the 10 will be used up by low priority traffic. Therefore, the token rotation time will be 100.
2. In this situation, regardless whether the ring contains high priority traffic, the token rotation time will always be the full 100.
3. If there is no low priority data, we use 90 for the actual token rotation time, the efficiency is equal to: . Note here we subtract from the numerator since it's wasted due to propagation delays.
  Similarly, if we assume the ring is also fully loaded with low priority data, the efficiency is equal to: . Here because and do not bound the time for low priority traffic transmission, the full 100 target token rotation time is used.
4. When there is no high priority data, low priority data will take the entire capacity of the ring, excluding the propagation delays, therefore, the efficiency is equal to: .
To summerize: for FDDI, provides the upper bound for the high priority transmission, provides the target upper bound for the total amount of low priority transmissions.
Full credits were given if the problem is solved under any of the above assumptions.
(51 points, 3 points each) For each of the following statement, decide if it is TRUE or FALSE. If FALSE, you must briefly explain why it is FALSE.
1. CSMA/CD is more efficient than Token Bus when carrying time sensitive traffic under heavy load;
  False. At heavy load, the massive amount of collision and retransmission will crash the CSMA/CD protocol, making the efficiency close to zero. Token Bus will continue to have high efficiency since there is no collisions.
2. Token Ring network use shared transmission media (in contrast to point-to-point links);
  False. Token Ring uses point-to-point links. Token Bus and CSMA/CD use shared media.
3. The Tree-Walk Algorithm is used to resolve collisions in multiple access channels;
  True.
4. The Tree-Walk Algorithm is used to speed up the token rotation time in FDDI;
  False. Tree-Walk Alg. is for multiple access protocols, not token ring type protocols.
5. ALOHA networks can be made more efficient than Token Bus under heavy load if the propagation delay is zero;
  False. For the same reason for CSMA/CD networks.
6. ALOHA networks are in general more efficient than CSMA/CD networks;
  False. ALOHA does not have collision detection and carrier sensing, making it less efficient.
7. ALOHA networks are identical to CSMA (without CD) networks;
  False. ALOHA does not have carrier sensing, while CSMA does.
8. Under heavy load, TDM achieves close to 100%transmission efficiency;
  True. TDM is not a contention based protocol. Therefore, full utilization of the link is possible, as long as all slots are assigned. Of course when used to carry packet switched traffic, bandwidth has to be reassigned from packet to packet, making maintenance a very difficult task.
9. Under heavy load, Token Ring achieves close to 50%transmission efficiency; False. It's close to 100%because the overhead is token processing, which is independent of traffic load. Token processing usually takes much less time than the frame transmission.
10. Under heavy load, ALOHA achieves close to 100%transmission efficiency;
  False. For the same reason as that of . Another way to look at it is through the expression: as .
11. Under heavy load, ALOHA achieves close to 0%transmission efficiency;
  True. Because as .
12. Under heavy load, SLOTTED ALOHA achieves close to 18.2%transmission efficiency;
  False. Because as .
13. Under heavy load, SLOTTED ALOHA achieves close to 36%transmission efficiency;
  False. Because as .
14. Go-Back-N protocol is more efficient than Selective Repeat Protocol when the channel is very noisy;
  False. GBN will never be more efficient than SRP simply because it may retransmit frames that are correctly received, which will never occur in SRP. The reason for using GBN is its simplicity.
15. Data link layer may deliver frames out of order to the higher layers;
  False. The reason for using protocols like GBN, SRP or others is to ensure orderly delivery of frames.
16. A single parity check code can detect all odd number of bit errors;
  True.
17. A single parity check code can detect only single bit errors;
  False. See above statement.

RENSSELAER POLYTECHNIC INSTITUTE
Electrical, Computer and Systems Engineering Department
35.468 - Computer Communications Networks
Spring 1994
Final Exam
Thursday, May 11 (9am-12pm), 1994, RI 203 Ji Zhang
There are a total of 119 points on this exam. You have 3 hours to complete the exam. It is open book but closed notes, except that one crib sheet is allowed. Even though the test appear to be long, all problems require at most only some simple calculations. Good luck!

.0in NAME_______________________
.0in

.5in

For each statement in parts to , circle ONE AND ONLY ONE of the associated choices that best matches your understanding (you will get no credit if more than one choice are circled):

(5 points) Selective Repeat Protocols
1. can only be used over a half-duplex link;
2. requires a window size less than twice the buffer capacity;
3. requires a window size no less than twice the buffer capacity;
4. requires a window size less than half the buffer capacity;
5. requires a window size no less than half the buffer capacity;
6. requires no buffering;
7. may deliver packets out of order;
8. is less efficient than GO BACK N when they use the same window size;
(5 points) The token ring network
1. has the longest media access time when compared with ALOHA and Ethernet;
2. has more than one token in the network at any time;
3. has unbounded delay;
4. is more efficient than Ethernet under light load;
5. is less efficient than Ethernet under heavy load;
6. is more efficient than Ethernet under heavy load;
7. is a ring formed by logically assigning the order to pass tokens;
(5 points) Time Division Multiplexing
1. is only used in local area networks;
2. can not be used for statistical multiplexing;
3. is only used in full duplex transmissions;
4. is more suitable for bursty data traffic transmissions;
5. is more suitable for high speed transmissions than frequency division multiplexing;
6. is more suitable for digital transmissions than frequency division multiplexing;
7. requires the use of fixed packet size;
(5 points) In TCP protocol, the sliding window algorithm
1. uses selective repeat scheme with positive acknowledgement scheme;
2. uses Go-Back-N with negative acknowledgement scheme;
3. uses the service provided by upper layers;
4. sequentially numbers each IP datagram;
5. None of the above.
(5 points) If an IP datagram is discarded in a particular node because the time-to-live field reaches zero at that node, then an error message in the form of a datagram has to be sent back.
1. If the previous node is not the one that originated the datagram but only a forwarding node, this previous node will be the only one receiving this error message;
2. every node neighboring this node will receive the message;
3. The new copy of the original datagram will be retransmitted at the node where the old one is lost;
4. Every neighboring nodes have to retransmit a copy of the lost datagram;
5. None of the above.
(5 points) Dijkstra's algorithm
1. is used to find the shortest paths from all nodes to all other nodes;
2. is used as a lookup table for routing purposes;
3. is used to find the shortest paths from a single source node to all other destination nodes;
4. is used to find the shortest paths from all nodes to a single destination node;
5. is used to find the shortest of two known paths to a given destination;
6. both and above;
7. all of , and ;
8. None of the above;
(5 points) In sliding window protocol, when the link is very unreliable,
1. Go-Back-N protocol is more efficient than Selective Repeat protocol with the same buffer size;
2. Go-Back-N protocol is less efficient than Selective Repeat protocol with the same buffer size;
3. links with longer propagation delay are more efficient than links with shorter propagation delay;
4. links with longer propagation delay are less efficient than links with shorter propagation delay;
5. and .
6. and .
(5 points) TCP protocol
1. is a connection-less transport layer protocol;
2. is a connection-oriented transport layer protocol;
3. is a connection-less network layer protocol;
4. is a connection-oriented network layer protocol;
5. can not be used without the IP layer;
6. TCP segment usually encapsulates IP datagram;
7. performs routing functions;
8. TCP segment is usually encapsulated in IP datagram;
9. and ;
10. and ;
11. to .
12. None of the above;
(5 points) An ATM network is to be used to support an application, which is a TCP/IP based application. This means that application data will be broken down into TCP segments, which in turn will be changed into IP datagrams, which will be further broken down into smaller ATM cells upon entering the ATM network. The cells will be reassembled back into IP datagrams and then TCP segments upon departure from the ATM network, as shown in Figure , where user data appears in points and , TCP segments appear in points and , IP datagrams appear in points and .

Now suppose that an ATM cell is lost due to buffer overflow within the ATM network, which of the following layers is responsible to recover the lost ATM cell? Circle one answer only.
1. the ATM switch where the cell is lost;
2. ATM Adaptation (AAL) layer;
3. IP layer;
4. TCP layer;
5. Application layer;
6. All of the above;
(5 points) A noise free analog channel has a bandwidth of 2000Hz, find the maximum data rate, in bits/sec, the channel can carry digital information with arbitrarily small probability of error.
(5 points) Give arguments for and against using small ATM cell size;
1. FOR:
  Smaller packetization delay, good for real time traffic;
2. AGAINST:
  Large overhead, inefficient for large data file transfers.
(12 points) Continue with the question on ATM networks in Problem , as shown in Figure . You do not have to explain your answers. You must use YES or NO as your answers. Anything else will not be acceptable.
1. Do all the ATM cells generated from a single IP datagram have to follow the same routing path (between ) within the ATM network?
  YES
2. Do all the ATM cells generated from multiple IP datagrams that flow between two fixed IP addresses have to follow the same routing path (between ) within the ATM network?
  NO
3. Do all the ATM cells generated from a single TCP segment () have to follow the same routing path within the ATM network?
  NO
4. Do all the ATM cells generated from multiple TCP segments () have to follow the same routing path within the ATM network?
  NO
5. Do all the ATM cells generated from a single IP datagram have to be orderly delivered within the ATM network?
  YES
6. Do all the ATM cells generated from multiple IP datagrams that flow between two fixed IP addresses have to be orderly delivered within the ATM network?
  NO
(10 points) In a network that has a maximum packet size of 128bytes, a maximum packet lifetime of 30sec. An 8-bit packet sequence number is used for numbering the packets consecutively, what is the maximum data rate per connection (bits/sec)
Condition:
(12 points) In TCP/IP, IP datagrams may have to be fragmented due to internetworking constraints.
1. Now suppose one of the fragments is lost during transmission, which layer is responsible for recovering the lost information?
2. Do the smaller fragments have to have complete addressing information?
3. Which layer contains the so called three-way handshaking procedure?
4. What information is exchanged in the three-way handshaking procedure?
a). TCP b). Yes c). TCP d). ISN and port numbers.
(10 points) Consider an ATM switch with four ports, as described in Figure . the VCI/VPI table for the ATM switch is given below.

Suppose that the switch processes cells in the order of port , one cell at a time, write down the VCI/VPI labels at they appear at the output ports on Figure . Make sure the time relationships of the cells are correct.
(20 points) Consider the following queueing system which is formed by two M/M/1 queues in tandem, as described in Figure . That is, the customers departing from the first queue is fed into the second. A second arrival stream, independent of the departure process from queue 1 is fed into queue 2. Both arrival streams are Poisson processes with rate (customers/sec), the service rates for the two queues are (customers/sec).
1. Let be the average queue length, including the one in service if the queue is not empty, of queue 1, find
2. Assume that the departure process from queue 1 is still a Poisson process independent of the separate arrival to queue 2, find the queue length of queue 2 Again, this includes the customer in service if the queue is not empty.
3. What's the system time for queue 2: (The customers may be from queue 1 or from the separate arrival stream.)
4. Treat the system as a whole, find the overall average system time for an average customer joining the system

Next: About this document Up: Probabilities and Random Previous: Expectations:

zhangj@
Mon May 23 15:29:10 EDT 1994