4 and 5 o Show the operation of the forward search variant of Dijkstra\'s algori

Question

4 and 5

o Show the operation of the forward search variant of Dijkstra's algorithm for computing the least cost path from node F to all other nodes. o Show the distance table that would be computed by the Distance Vector algorithm in D. 4. (10 points) Eva Luator is in charge of assigning groups of addresses to organizations in Europe. Eva has only 10 groups of addresses left: two groups of a.b.c.d/22 addresses and eight groups of a.b.c.d/24 addresses. She receives requests from many different companies, each of which asking for a group of 512 addresses. In general, how many such requests will Eva be able to satisfy? Justify 5. (10 points) The HDLC protocol uses a flag 01111110 at the start and at the end of frames. In order to prevent data bits from being confused with flags, the sender stuffs a zero after every 5 consecutive ones in the data. Ned Works wants to change the protocol to stuff a zero only after a zero followed by 5 consecutive ones. Is this a good idea? Justify.

Explanation / Answer

4) 2 groups of a.b.c.d/22 addresses.

Here 22 bit is Networks id and the rest 10 bits are Host id.Now, we need groups of 512 addresses so, LSB 9 bits should be fixed as Host id part( as 29 = 512).Therefore, we are left with 10 - 9 = 1 bit in the Host id part for making subnets of 512 addresses. With 1 bit we can have 21 = 2 subnets of 512 addresses.

Therefore with 2 groups of a.b.c.d/22 addresses we can satisfy 2*2 = 4 requests.

8 groups of a.b.c.d/24 addresses:

In this Network id is of 24 bits and Host id is of 8 bits.

As we need groups of 512 addresses which is 29 so, 8 bits will not suffice.

Therefore we will merge two networks to make it a.b.c.d/23.Now, a.b.c.d/23 can suffice for 512 addresses as now the Host id part has 9 bits.

With 8 groups of a.b.c.d/24 addresses, we will have 4 groups of a.b.c.d/23 addresses and each one will satisfy one request.

Therefore total number of requests that can be satisfied by 8 groups of a.b.c.d/24 addresses = 4 requests.

Therefore total number of requests that can be satisfied = 4+4 = 8 requests.

5) Yes this is a good idea.This is because even if the data bits doesn't consist of the flag bits i.e 01111110, the HDLC protocol will unnecessarily stuff a 0 bit which is not the case with the new protocol.

For instance, if the data bits to be sent is 111111111111 then HDLC protocol will stuff bits after 5 consecutive 1's and send the message as 11111011111011.

Now in the new protocol as the data bits are not starting with a zero it will only send 111111111111.And this is more logical as the Flag bits itself start with a zero.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.