Answers

1. For  assignment  3  you  need  to  implement  a  method  to  check the  number  of elements  of a  queue implemented with a LL. Write a pseudo­code for a method or function called Length() that can do that. Discuss aspects such as: return value, extra pointers or variables for better performance.

Answer:

The method Length() could rely on a counter being updated by Join() and Leave():

int Queue::Length() {

return counter;

}

Or, if you do not want to add the variable, we have to traverse the linked­list:

int Queue::Length() {

Node *temp=front;

int counter=0;

while(temp!=NULL){

temp=temp­>next;

counter++;

}

return counter;

}

Traversing long linked­lists have performance consequences, and having a counter updated by Leave( ) and Join( ) would be a better approach.

2. For assignment 3, use the following data to simulate the router, and to get the appropriate outputs for each queue:

## Router simulation

Ports 3

## each line represents the queue for a single input port

## each number represents the destination of the packet

## this router has N=3 ports

2 2 2 2 3 3

1 1 3 3 3 3

1 2 2 1 2 1

Answer:

There are 6 queues, 3 input queues and 3 output queues. Lets call them InpQ[i] and OutQ[i]. We also need an array to keep the maximum congestion size at any point.

We start by loading the input queues with the data (considering that the head of the queue is on the left, and the tail is on the right), and with empty output queues:

InpQ[0] = { 2 2 2 2 3 3 } InpQ[1] = { 1 1 3 3 3 3 } InpQ[2] = { 1 2 2 1 2 1 }

OutQ[0] = { }

OutQ[1] = { }

OutQ[2] = { }

Congestion_Size[0] = 0

Congestion_Size[1] = 0

Congestion_Size[2] = 0

The simulation starts by moving one packet at a time, and at

time = clock % (TIMEDELAY*number_of_ports) == 0,

with TIMEDELAY=3 and number_of_ports=3. Therefore queues can have one packet removed when t=9, t=18, t=27 etc...

Time t=4: port 2 transfers a packet 1 to port 1

InpQ[0] = { 2 2 3 3 }      OutQ[0] = { 1 1 1 }

InpQ[1] = { 3 3 3 3 }      OutQ[1] = { 2 2 }

InpQ[2] = { 2 2 1 2 1 }   OutQ[2] = { }

Time t=5: port 3 transfers a packet 2 to port 2

Time t=6: port 1 transfers a packet 2 to port 2

Time t=7: port 2 transfers a packet 3 to port 3

Time t=8: port 3 transfers a packet 2 to port 2

OutQ[0] = { 1 1 1 }      OutQ[1] = { 2 2 2 2 2 } OutQ[2] = { 3 }

Time t=9: port 1 transfers a packet 2 to port 2

OutQ[0] = { 1 1 1 }         OutQ[1] = { 2 2 2 2 2 2 } OutQ[2] = { 3 }

One packet leaves each queue, then we verify the sum

OutQ[0] = { 1 1 }         OutQ[1] = { 2 2 2 2 2 } OutQ[2] = { }

Congestion_Size[0] = 3

Congestion_Size[1] = 2

Congestion_Size[2] = 0

Congestion_Size[0] = 3

Congestion_Size[1] = 3

Congestion_Size[2] = 0

Congestion_Size[0] = 3

Congestion_Size[1] = 4

Congestion_Size[2] = 0

Congestion_Size[0] = 3

Congestion_Size[1] = 4

Congestion_Size[2] = 1

Congestion_Size[0] = 3

Congestion_Size[1] = 5

Congestion_Size[2] = 1

Congestion_Size[0] = 3

Congestion_Size[1] = 6

Congestion_Size[2] = 1

Congestion_Size[0] = 2

Congestion_Size[1] = 5

Congestion_Size[2] = 0

Therefore, the number of packets in the most congestion situation so far (with max_sum=9) is

queue 1: 3 pkts, in queue 2: 5 pkts, and in queue 3: 1 pkts.