transmit long (multiframe) files.After each frame is sent, they contend for the channel, using the binary exponential backoff algorithm. What is
theprobability that the contentionends on round k, and what is the mean number of rounds percontentionperiod?
答：把获得通道的尝试从1 开始编号。第i 次尝试分布在2 i-1 个时隙中。因此，i 次尝试碰撞的概率是2-(i-1)，开头k-1 次尝试失败，紧接着第k 次尝试成功的概率是：
Pk=（1-2^-（k-1））[2^-0*2*-1*······*2^-(k-2)]=（1-2^-（k-1））2^-(k-1)(k-2)/2所以每个竞争周期的平均竞争次数是Σkpk(k=1,2,3······∞)
8．An IP packet to be transmitted by Ethernet is 60 bytes long, including all itsheaders. If LLC is not in use, is padding needed in the Ethernet frame, and if so, how many bytes?
答：最小的以太帧是64bytes，包括了以太帧头部的二者地址、类型/长度域、校验和。因为头部域占用18 bytes 报文是60 bytes，总的帧长度是78 bytes, 已经超过了64-byte 的最小限制。因此，不需要填补。
1. Describe distance vector (DV) algorithm. Discuss the feature of the DV
routing algorithm.
Solution:
(1) The basic idea of DV algorithm
Each node x begins with Dx(y), an estimate of thecost of the least-cost path from itself to node y, for all nodes in N. Let Dx= [Dx(y): yin N] be node x’s distance vector, which is the vector of cost estimates from x to allother nodes, y, in N. With the DV algorithm, each node x maintains the followingrouting information: ? For each neighbor v, the cost c(x,v) from x to directly attached neighborv ? Node x’s distance vector, that is, Dx= [Dx(y): y in N], containing x’s estimate ofits cost to all destinations, y, in N
? The distance vectors of each of its neighbors, that is, Dv= [Dv(y): y in N] for eachneighbor v of x
In the distributed, asynchronous algorithm, from time to time, each node sendsa copy of its distance vector to each of its neighbors. When a node x receives anew distance vector from any of its neighbors v, it saves v’s distance vector, andthen uses the Bellman-Ford equation to update its own distance vector as follows:
Dx(y) _ minv{c(x,v) + Dv(y)} for each node y in N
If node x’s distance vector has changed as a result of this update step, node x willthen send its updated distance vector to each of its neighbors, which can in turnupdate their own distance vectors. Miraculously enough, as long as all the nodescontinue to exchange their distance vectors in an asynchronous fashion, each costestimate Dx(y) converges to dx(y), the actual cost of the least-cost path from node xto node y
(2) The feature of the DV routing algorithm
The distancevector(DV) algorithm is iterative, asynchronous, and distributed. It is distributedin that each node receives some information from one or more of its directlyattached neighbors, performs a calculation, and then distributes the results of itscalculation back to its neighbors.
It is iterative in that this process continueson until no more information is
exchanged between neighbors. (Interestingly, thealgorithm is also
self-terminating—there is no signal that the computation shouldstop; it just stops.) The algorithm is asynchronous in that it does not require all ofthe nodes to operate in lockstep with each other.
2. Consider a configuration in which packets are sent from computers on a LAN to systems on other networks. All of these packets must pass through a router that connects the LAN to a widearea network and hence to the outside world.
Let us look at the traffic from the LAN through the router. Packets arrive with a mean arrivalrate of 5 per second. The average packet length is 144 bytes, and it is assumed that packetlength is exponentially distributed. Line speed from the router to the wide-area network is9600 bps. The following questions are asked: (a) What is the utilization of the link of the router? (b) What is the mean residence time in the router?
(c) How many packets are in the router, including those waiting for transmission
and the one currently being transmitted (if any), on the average?
Solution:
(a) Mean arrival rate(throughput): X=5 packets/sec Average
service
time:
S=((144bytes/packet)*(8bits/byte))/9600bps=0.12sec/packet
Utilization(time the router is busy): U=X*S=(5 packets/sec)*(0.12 sec/packet)=0.6 (b) The mean residence time is T=S/(1-U)=(0.12 sec/packet)/(1-0.6)=0.3 sec/packet (c) Number of packets in the router is E[n]=U/(1-U)=1.5 packets
2. Consider the arrival traffic characterized by a token bucket with parameters ρ (average rate) = 1 Mbps, M (maximum output rate) = 2 Mbps, and C (token capacity) = 200Kb. What is the minimum rate r that needs to be allocated by a router in order to guarantee a delay no larger than 50ms?
Solution:
We build the equation according to the rule: the bits flowed in the router are equal to the bits
flowed out the router. Let S be burst length, the maximum accumulative amount of arrival traffic to the router is C+ρS=MS.We get S=C/(M-ρ). When the router deal the arrival traffic at the minimum rate r with a delay no larger than 50ms, let D=50ms and the equation is MS=r*(S+D). So,
r?MSS?D?MC/(M??)C/(M??)?0.05s?2Mbps*200Kb/(2Mbps?1Mbps)200Kb/(2Mbps?1Mbps)?0.05s?0.4Mb0.25s?1.6Mbps
3. Describe the border gateway protocol (BGP) and discuss how a packet would be transmitted among different autonomous system (AS). Solution:Border GatewayProtocol version 4 (BGP4)
We just learned how ISPs use RIP and OSPF to determine optimal paths for sourcedestinationpairs that are internal to the same AS. Let’s now examine how paths aredetermined for source-destination pairs that span multiple ASs. BGPprovides each AS a means to
1. Obtain subnet reachability information from neighboring ASs. 2. Propagate the reachability information to all routers internal to the AS.
3. Determine “good” routes to subnets based on the reachability information andon AS policy.
4. Suppose that frames are 1250 bytes long including 25 bytes of head. Also assume that ACK frame are 25 bytes long. Calculate the efficiency of stop-and-wait ARQ in a system that transmits at R=1Mbps and with reaction time of 1ms for channels with a bit error of 10-6, 10-5, 10-4. Solution:
From the above figure and condition, we know the total time to transmit 1 frame is t0=2(tprop+tproc)+tf+ta.Here, 2(tprop+tproc) is the reaction time of 1ms, tf is the time to transmit the fames nf=1250 bytes with the head nh=25 bytes and ta is the time to transmit the ACK frame na=25 bytes. And the useful size of the frame is (nf-nh). Moreover, the probability of transmitting a frame without errors is (1-Pe). So the transmission efficiency is as follows.