Homework 4 Problems From The Network and Link Layers

    1) (10 points) A certain router receives a datagram of size 7000 B (including the header). However, all of its output ports have an MTU (maximum transfer unit) of 1500 B, thus the original datagram should be fragmented into several smaller datagrams when forwarded. For each of the output fragments write the following fields of the IP header: length, ID, flag and offset! Assume 20 B for the IP header.



    2) (10 points) A certain autonomous system (AS) is assigned a subnet which to the outside world (Internet) is advertised as 24.23.5.0 /24. Each router has its number of hosts attached to it, which includes the router interface on that particular side of the subnet. As a network administrator, your job is to properly and efficiently do the subnetting inside this AS!
(Note: for subnets with 2 interfaces we suggest to also include the network and broadcast domain)
(Hint: start with the largest subnets first)


















Fig.1. An autonomous system (AS) with an assigned subnet of 24.23.5.0 /24.



    3) (10 points) Inside your AS you have the 6 subnets given bellow. Summarize them so when advertised to the outside world you’ll have as least entries (subnets) to advertise as possible. Of course, avoid over-summarization.

243.157.50.0 /22;  243.157.54.0 /22;  243.157.58.0 /22;  243.157.62.0 /22; 243.157.10.0 /22
243.157.42.0 /22
    4) (10 points) In Fig.2 you have the topology of a certain network. Construct the forwarding table for router u towards all the other routers using the Dijkstra’s algorithm. Show all of the steps!
















Fig.2. Topology of a certain network



    5) (15 points) In Fig.3 you have the topology of a certain network. Construct the forwarding table for all of the routers towards all the other routers in the network using the Bellman-Ford’s algorithm. You can assume that all the routers send their newly computed/changed distance vectors (DV’s) values to their neighbor at the same time, i.e. for t=0 all of them have only the DVs for their neighbors, at t=1 they do the first exchange of DVs, at t=2 they do the second exchange of DVs, etc. Show all of the steps until the algorithm converges for all of the routers (i.e. there are no more changes in DVs)!

(Note: if everything as done correctly, you shouldn’t have more to do more than 3 iterations (including the initialization) for any of the routers.)

(Hint: fill-up the all of the tables below corresponding to new DV values after an exchange with the neighbors. The initial tables for all of the routers are given.)












Fig.3. Topology of a certain network


Dx()
X
Y
Z


Dy()
X
Y
Z


Dz()
X
Y
Z



X
0
2
7


X
∞
∞
∞


X
∞
∞
∞

t=0

Y
∞
∞
∞


Y
2
0
1


Y
∞
∞
∞



Z
∞
∞
∞


Z
∞
∞
∞


Z
7
1
0



DV table of X


DV table of Y


DV table of Z



Dx()
X
Y
Z


Dy()
X
Y
Z


Dz()
X
Y
Z



X





X





X




t=1

Y





Y





Y






Z





Z





Z






DV table of X


DV table of Y


DV table of Z



Dx()
X
Y
Z


Dy()
X
Y
Z


Dz()
X
Y
Z



X





X





X




t=2

Y





Y





Y






Z





Z





Z






DV table of X


DV table of Y


DV table of Z


    6) (10 points) A sender has this data payload to send D=10011010. If both the sender and the receiver have agreed to use 1 + 3 as their generator (i.e. G=1001), then compute the CRC (Cyclic Redundancy Check) for D! Show all the details!


    7) (15 points)

    a) (5 points) A sender has this data payload to send D=01011010001011. It uses a 2D parity check with 5 rows and 4 columns and odd parity (i.e. in each row and column, including the parity bits, the number of 1s should be an odd number). Construct the message that will be send after 2D parity is added and show it in matrix form.

(Note: If the number of bits in the payload D is not enough to fill-up the matrix with 5 rows and 4 columns, at the end of D you can append the necessary number of zeros so as to fill-up the matrix)

    b) (10 points) In the table below you have the message that a certain sender which uses 2D even parity check for error detection and/or correction has sent. Are there any transmission errors? If so, where? If so, can you correct them? Why?


101101 0
001010 0
101100 1
001010 0
100101



    8) (15 points) A sender sends an n bit message through an unreliable channel which has a bit-error probability p. What is the probability of:
        a) (5 points) exactly one bit is flipped from the transmitted message
        b) (5 points) at least one bit is flipped from the transmitted message
        c) (5 points) exactly b bits are flipped from the transmitted message



    9) (25 points) Consider the figure below (Fig.4), which shows the arrival of 6 messages for transmission at different multiple access wireless nodes at times t = <0.8, 1.2, 2.9, 3.1, 4.3, 4.6> and each transmission requires exactly one-time unit.








Fig.4. Transmission times of different multiple access nodes sharing a transmission medium


a) (5 points) Aloha

a.1) Suppose all nodes are implementing the Aloha protocol. For each message, indicate the time at which each transmission begins. Separate each value with a comma and no spaces.

a.2) Which messages transmit successfully? Write your answer as a comma separated list with no spaces using the messages' numbers
b) (5 points) Slotted Aloha

b.1) Suppose all nodes are implementing the Slotted Aloha protocol. For each message, indicate the time at which each transmission begins. Separate each value with a comma and no spaces.

b.2) Which messages transmit successfully? Write your answer as a comma separated list with no spaces using the messages' numbers

c) (5 points) CSMA

c.1) Suppose all nodes are implementing Carrier Sense Multiple Access (CSMA), but without collision detection. Suppose that the time from when a message transmission begins until it is beginning to be received at other nodes is 0.4 time units. (Thus if a node begins transmitting a message at t=2.0 and transmits that message until t=3.0, then any node performing carrier sensing in the interval [2.4, 3.4] will sense the channel busy.) For each message, indicate the time at which each message transmission begins, or indicate that message transmission does not begin due to a channel that is sensed busy when that message arrives. Separate each value with a comma and no spaces, and if the channel is sensed busy, substitute it with 's'

c.2) Which messages transmitted successfully? Write your answer as a comma separated list with no spaces using the messages' numbers


d) (10 points) CSMA/CD

d.1) Suppose all nodes are implementing Carrier Sense Multiple Access (CSMA), with collision detection (CSMA/CD). Suppose that the time from when a message transmission begins until it is beginning to be received at other nodes is 0.4 time units, and assume that a node can stop transmission instantaneously when a message collision is detected. (Thus if a node begins transmitting a message at t=2.0 and transmits that message until t=3.0, then any node performing carrier sensing in the interval [2.4, 3.4] will sense the channel busy.) For each message, indicate the time at which each message transmission begins, or indicate that message transmission does not begin due to a channel that is sensed busy when that message arrives. Separate each value with a comma and no spaces, and if the channel is sensed busy, substitute it with 's

d.2) Which messages transmitted successfully? Write your answer as a comma separated list with no spaces using the messages' numbers

d.3) At what time did each message stop transmitting due to a collision. Write your answer as a comma separated list with no spaces using the messages' numbers in order, and if a message didn't stop, write 'x' for that message


Good luck!
CS408 Team (Artrim Kjamilji, Begüm Arslanhan)