CS 351: Design of Large Programs -------------------------------- Assignment # 3, Due Date 10/18/01 ---------------------------------- The goal of this assignment is to simulate a single switch and a network of switches. Preliminaries: -------------- An mXn switch is a device that has m input ports and n output ports. It receives packets on one or more inputs. Each packet bears a destination address from which is infered the output port it needs access to. We assume that a packet is destined to only one address rather than being multicast. The mapping of destination to output port is many-to-many in general. For example, a packet destined for node 3001 may have multiple paths to 3001 some of which could be through output port 2 and some through output port 5. Further, there could be a certain bias with respect to a given port -- perhaps a path through port 5 is shorter. For purposes of this assignment however, we assume that, given a destination, there is one and only one port that the packet can exit through to reach its final destination. Of course packets for different destinations may need to access the same output port -- thus the mapping is many-to-one. General mappings as in a router involve table look-up. However, the mapping here will be as simple as inspecting specific digits or bits of the destination address. We also assume that the bandwidth of each link, to and from a switch is the same. Finally, the length of a packet is fixed. Operation and Design of the Switch: ----------------------------------- ________________ ------->|0 0|->------ | | ------->|1 1|->------ | | ------->|2 2|->------ | | ------->|3 3|->------ |________________| We define cycle time as the minimum time interval between two consecutive packet arrivals at an input port. At the start of a cycle new packets will arrive at zero or more input ports. (This arrival probability is a measure of network load or traffic. A heavily loaded part of a network will see fresh packet arrivals at the start of a cycle on just about every input port.) The rest of the cycle is spent in determining which packet gets to go where. If two or more packets wish to use the same output port, one will be allowed to -- the others will either have to be discarded (dropped) or stored in the switch. This is illustrated below. ____________________ | | | | 1 | | ------->|0 0|->------ | | | | 1 | | ------->|1 1|->------ | | | | 0 | | ------->|2 2|->------ | | |____________________| Consider packets that arrive at each input port that intend to access output ports 1, 1 and 0 as shown. Only one packet can be sent out on a transmission line per cycle in this switch. So only one of the packets arriving on input ports 0 and 1 can be transmitted. Without any internal buffers, one of these packets will have to be discarded. If we allow the packet on port 0 to proceed, the packet on port 1 will have to be discarded. To prevent any input port from starving, we use round-robin scheduling i.e. we service requests in the order i, i+1, . . . m-1, 0, 1 . . . i-1. In the next cycle the order is i+1, i+2, . . . m-1, 0, 1 . . . i and so on. Scheduling Policy 1A: Simple Round Robin with no buffering. --------------------------------------------------------- Initialize i to 0 For each cycle For each input port j starting from port i, if a packet has arrived on j, examine the output port it needs access to, say k. if k has not yet been reserved in the current cycle, reserve k for this packet else discard this incoming packet. i = (i+1) % m. The cycle by cycle arrival of packets and their intended destinations is shown below on the left. The right table shows whether a packet has been discarded and, if not, the output port through which it exits using the above policy. Incoming Packet | Port of departure Cycle number |In Port 0 In Port 1 In Port 2| 0 1 2 ________________|_____________________________|__________________ 1 | 1 1 0 | 1 D 0 2 | 2 0 0 | 2 0 D 3 | 1 2 1 | D 2 1 4 | 0 1 2 | 0 1 2 5 | 0 0 1 | D 0 1 6 | 1 1 0 | 1 D 0 7 | 2 0 0 | 2 0 D 8 | 1 0 - | 1 0 - 9 | 2 1 2 | D 1 2 10 | 2 1 0 | 2 1 0 11 | 1 1 2 | D 1 2 12 | 0 2 1 | 0 2 1 13 | 1 - 0 | 1 - 0 14 | 0 0 1 | D 0 1 15 | 1 0 0 | 1 D 0 16 | 0 1 - | 0 1 - 17 | 1 1 1 | D 1 D Table 1: Cycle by cycle output of packets using RR scheduling (b=0) In lieu of discarding packets in the event of a conflict, it is possible (and even desirable) to store or buffer packets in the switch for later transmission. There are several possible ways of buffering -- input buffering, output buffering and shared buffers. For purposes of this assignment, we assume finite buffers at each input port. The input buffers are parameterized by b, the number of slots in a buffer (i.e. maximum number of packets at a time that can be buffered at a port.) Scheduling Policy 1B: Simple Round Robin with Input Buffering. ------------------------------------------------------------ Initialize i to 0 For each cycle For each input port j starting from port i, if the queue at input j is not empty, let p be the packet at the head of the queue. else if a packet has arrived at input j, let p be this packet. if p != NULL examine the output port it needs access to, say k. if k has not yet been reserved in the current cycle, reserve k for packet p if p is not new arrival and there is new arrival, add new arrival to queue else if there is a new arrival if the queue at j is not full add p to the queue else discard this incoming packet. i = (i+1) % m. The tables below show the state of the buffer and packet departures (if any), given packet arrivals during each cycle. Notation: What follows "b=" is the content of the buffer at that port, tail first. If the buffer holds nothing subsequent to possible transmission in the current cycle, a "-" will appear. The "t/d" represents transmitted or discarded. If a packet is transmitted from that input port, the destination port of that packet will follow the "t/d=". If the new arrival is dropped, a "d" will appear. Finally, if no packet is released from that input port + buffer, a "-" appears. As an example, consider the interpretation of the row corresponding to cycle 13 in Table 2. Packets destined for output ports 1 and 0 appear on input ports 0 and 2 respectively. No packet has arrived on input port 1. The "round robin pointer" happens to point to port 0 yet again, so we start by scanning port 0. The buffer at this port is occupied by a packet destined for output port 2. So we must let it proceed and the new arrival (destined for port 1) is now buffered. The transmission of a packet and state of the buffer at input port 0 is summarized by the notation "b=1 t/d=2". The corresponding entries for the other input ports can be similarly obtained. Packet Arrivals |Input Port # | State of Input Ports Cycle | 0 1 2 | 0 1 2 ______|_______________|_____________________________________________ 1 | 1 1 0 | b=- t/d=1 b=1 t/d=- b=- t/d=0 2 | 2 0 0 | b=- t/d=2 b=0 t/d=1 b=- t/d=0 3 | 1 2 1 | b=1 t/d=- b=2 t/d=0 b=- t/d=1 4 | 0 1 2 | b=0 t/d=1 b=1 t/d=2 b=2 t/d=- 5 | 0 0 1 | b=0 t/d=0 b=0 t/d=1 b=1 t/d=2 6 | 1 1 0 | b=1 t/d=0 b=0 t/d=d b=0 t/d=1 7 | 2 0 0 | b=2 t/d=1 b=0 t/d=0 b=0 t/d=d 8 | 1 0 - | b=1 t/d=2 b=0 t/d=0 b=0 t/d=- 9 | 2 1 2 | b=2 t/d=1 b=0 t/d=d b=2 t/d=0 10 | 2 1 0 | b=2 t/d=2 b=1 t/d=0 b=2 t/d=d 11 | 1 1 2 | b=2 t/d=d b=1 t/d=1 b=2 t/d=2 12 | 0 2 1 | b=2 t/d=d b=2 t/d=1 b=1 t/d=2 13 | 1 - 0 | b=1 t/d=2 b=2 t/d=- b=0 t/d=1 14 | 0 0 1 | b=0 t/d=1 b=0 t/d=2 b=1 t/d=0 15 | 1 0 0 | b=1 t/d=0 b=0 t/d=d b=0 t/d=1 16 | 0 1 - | b=0 t/d=1 b=1 t/d=0 b=0 t/d=- 17 | 1 1 1 | b=0 t/d=d b=1 t/d=1 b=1 t/d=0 Table 2: Cycle by cycle output of packets using RR scheduling (b=1, HOL) The table below performs the same exercise but now each buffer can accomodate two packets. Packet Arrivals |Input Port # | State of Input Ports Cycle | 0 1 2 | 0 1 2 ______|_______________|_____________________________________________ 1 | 1 1 0 | b=-,- t/d=1 b=-,1 t/d=- b=-,- t/d=0 2 | 2 0 0 | b=-,- t/d=2 b=-,0 t/d=1 b=-,- t/d=0 3 | 1 2 1 | b=-,1 t/d=- b=-,2 t/d=0 b=-,- t/d=1 4 | 0 1 2 | b=-,0 t/d=1 b=-,1 t/d=2 b=-,2 t/d=- 5 | 0 0 1 | b=-,0 t/d=0 b=-,0 t/d=1 b=-,1 t/d=2 6 | 1 1 0 | b=-,1 t/d=0 b=1,0 t/d=- b=-,0 t/d=1 7 | 2 0 0 | b=-,2 t/d=1 b=0,1 t/d=0 b=0,0 t/d=- 8 | 1 0 - | b=-,1 t/d=2 b=0,0 t/d=1 b=-,0 t/d=0 9 | 2 1 2 | b=-,2 t/d=1 b=0,0 t/d=d b=-,2 t/d=0 10 | 2 1 0 | b=-,2 t/d=2 b=1,0 t/d=0 b=0,2 t/d=- 11 | 1 1 2 | b=1,2 t/d=- b=1,1 t/d=0 b=2,0 t/d=2 12 | 0 2 1 | b=0,1 t/d=2 b=2,1 t/d=1 b=1,2 t/d=0 13 | 1 - 0 | b=1,0 t/d=1 b=2,1 t/d=- b=0,1 t/d=2 14 | 0 0 1 | b=0,1 t/d=0 b=0,2 t/d=1 b=0,1 t/d=d 15 | 1 0 0 | b=0,1 t/d=d b=0,0 t/d=2 b=0,0 t/d=1 16 | 0 1 - | b=0,0 t/d=1 b=1,0 t/d=0 b=0,0 t/d=- 17 | 1 1 1 | b=0,0 t/d=d b=1,1 t/d=0 b=0,0 t/d=d Table 3: Cycle by cycle output of packets using RR scheduling (b=2, HOL) Note that the scheduling policy under consideration is strictly FCFS and can be implemented by a FIFO structure such as a queue. Unfortunately, this can lead to HOL-blocking (Head of the line blocking.) Scheduling Policy 2: RR + b>0 + non-Head of the Line ---------------------------------------------------- If the packet at the head of the line cannot proceed because its output port has been allocated to a packet from another input port, the packet just behind it is inspected to see if its output port is free and, if so, it is allowed to proceed. In cycle 12, for example, (see Table 2), the packet buffered at input 0 is destined for port 2. This port has already been allocated to the packet from input port 2 (which in this cycle is given preference). However, the incoming packet at port 0 is destined for output 0 which has not yet been allocated. It is allowed access. This policy prevents the incoming packet at input 0 from being discarded. In general, this policy will result in a decreased probability of a dropped packet and an increase in switch throughput. Note that ONLY the packet behind the HOL packet may be considered for transmission and that too ONLY IF the HOL packet cannot proceed for the reason mentioned above. Scheduling Policy 3: RR with packet priorities and timestamps ------------------------------------------------------------- In this case it is assumed that each packet carries a timestamp and a priority (smaller the value of the timestamp, older the packet and priority=1 corresponds to highest priority, 2=next highest and 3 is least.) The scheduling policy is: Packets at the head of their queues (only HOL packets) are ordered based on their priorities. If two packets have the same (packet) priority, the older one is placed above the younger one. If two packets have the same (packet) priority and age, they will be placed in round robin order. This defines the order in which packets are assigned to output ports. As usual, if a packet is destined to an output port which has already been allocated, then it will not leave the switch. Example: Suppose the packets at the head of the lines at the input ports are Port 0: <3, 1, 375> Port 1: <2, 1, 285> Port 2: <3, 1, 375> Port 3: <0, 2, 312> Port 4: <3, 2, 350> Port 5: <3, 1, 425> Port 6: <2, 2, 358> The first element of the tuples above is the output port number, the second element is the packet priority and the third element is the timestamp. Let the round-robin pointer be pointing at port 3. There are 4 packets that wish to access output port 3. Of these, three - at inputs 5, 0 and 2 - are high priority packets (priority number 1). The packets at ports 0 and 2 are the oldest (lowest timestamp values.) Since 0 appears before 2 in round-robin order, this scheduler assigns the packet at port 0 to output port 3. PART 1 ------ The first part of this assignment involves the simulation of a single switch using the scheduling policies described above. The input file called "input" is organized as below. The first line (header) comprises six integers m n b sp #cycles #snapshots where m is the number of input ports, n is the number of output ports, b is the maximum number of slots per input buffer, sp is the scheduling policy, #cycles is the total number of cycles over which the simulation should be run and #snapshots is the number of points in time at which a snapshot of the switch must be captured and output. sp = 1 => use scheduling policy 1A (if b=0) or 1B (if b>0) sp = 2 => use scheduling policy 2 sp = 3 => use scheduling policy 3 with HOL service only. The #snapshots points in time at which the snapshots of the switch need to be output are specified next begining line 2 of the input file. Finally, the cycle-by-cycle specification of the packet arrivals appears. If sp = 1 or 2 (scheduling policies 1 or 2), then the packets arrivals per cycle is a sequence of m integers. These are packets arrivals on input ports 0, 1, . . . m-1. The ith integer is the output port the packet on the ith input port is destined to. If the ith integer is -1, then there is no arrival on input i during that cycle. If sp = 3 (scheduling policy 3), packet arrivals in a cycle are represented by sequences of 3-tuples. A 3-tuple represents a packet. The first element is the destination output port number, the second element is the packet priority and the third is its timestamp. Again, in this case a "-1" in the corresponding position indicates the absence of a packet arrival. Example: -------- This is related to Table 3. 3 3 2 1 17 3 8 12 17 1 1 0 2 0 0 1 2 1 0 1 2 0 0 1 1 1 0 2 0 0 1 0 - 2 1 2 2 1 0 1 1 2 0 2 1 1 - 0 0 0 1 1 0 0 0 1 - 1 1 1 Your program needs to output three snapshots of the switch - at the end of cycles 8, 12 and 17. Output of your program ---------------------- For the above input, the program output should be At end of Cycle 8: ------------------ Input Port 0: b = -,1 t/d = 2 Total # of packet arrivals = 8, Total # of packets dropped = 0 Input Port 1: b = 0,0 t/d = 1 Total # of packet arrivals = 8, Total # of packets dropped = 0 Input Port 2: b = -,0 t/d = 0 Total # of packet arrivals = 7, Total # of packets dropped = 0 At end of Cycle 12: ------------------- Input Port 0: b = 0,1 t/d = 2 Total # of packet arrivals = 12, Total # of packets dropped = 0 Input Port 1: b = 2,1 t/d = 1 Total # of packet arrivals = 12, Total # of packets dropped = 1 Input Port 2: b = 1,2 t/d = 0 Total # of packet arrivals = 11, Total # of packets dropped = 0 At end of cycle 17: ------------------- Input Port 0: b = 0,0 t/d = d Total # of packet arrivals = 17, Total # of packets dropped = 2 Input Port 1: b = 1,1 t/d = 0 Total # of packet arrivals = 16, Total # of packets dropped = 1 Input Port 2: b = 0,0 t/d = d Total # of packet arrivals = 15, Total # of packets dropped = 2 If scheduling policy 3 is used, then each packet in the output should be represented as a 3-tuple rather than a single integer as described earlier. ------------------------------ *** ---------------------------------- PART 2 Due Date 10/23/01 -------------------------- In Part 2, we combine multiple switches to form a multi-stage switching network. First, consider two stages of 2X2 switches. ________ ________ |_ | |_ | 0 o-->-|_| |-------|_| |->--o 0 |_ | |_ | 1 o-->-|_| |_ _|_| |->--o 1 |________| \ / |________| \ / X ________ / \ ________ |_ |_/ \_|_ | 2 o-->-|_| | |_| |->--o 2 |_ | |_ | 3 o-->-|_| |-------|_| |->--o 3 |________| |________| Stage 0 Stage 1 The operation of the network in a cycle begins with the schedulers in the rightmost stage (in this case stage 1) deciding which, if any, of the packets should leave through the external links. Then, transmission of packets cleared for departure commences. Simultaneously, each stage 1 scheduler informs the input links to its switch whether or not its buffers (i.e. the input buffers at stage 1) can accept a packet from the preceding stage. A buffer is unable to accept a packet from the preceding stage if it is full prior to scheduling and will remain so just after the current round of scheduling has been completed, i.e. if it is full and the scheduler has not cleared its HOL packet for departure. The links then inform the schedulers in the preceding stage (in this case stage 0) of the availability of space in the stage 1 buffers. This is the extra piece of information needed before the stage 0 schedulers can begin their task. (Note that this is not true for the rightmost stage schedulers since their switches are connected to external links which are able to sink a packet during each cycle.) After the scheduling in stage 0 switches is over, transmission of packets cleared for departure begins. This should be implemented in your program by stage 0 schedulers communicating 0 or 1 packets to their output links. The links, in turn, communicate the received packet to the stage 1 switches which accomodate them in their input buffers. Finally, the stage 0 switches read incoming packets from a file and host them in stage 0 buffers contingent on available space as discussed earlier. If no space is available in an input buffer, an incoming packet will have to be dropped. Note that packets are not permitted to be dropped at points other than the inputs to the leftmost stage of switches. For this part, your program should use the scheduler supporting Policy 1b that you implemented in Part 1. Each packet is represented by a pair (a,b) - the first element is a unique packet identifier and the second is the destination (the numbers on the extreme right of the figure i.e. 0 through 3.) As mentioned in class, routing in stage 0 is obtained by inspecting the MS bit of the destination (0=>up, 1=>down). Routing in stage 1 uses the LS bit of the destination address. Example: -------- Below we show the operation of the above network with b=1. SW 0 refers to the top switch, SW 1 to the bottom switch. Each switch has two input buffers top and bottom (connected respectively to input ports 0 and 1.) Assume that the state of the buffers at the start of cycle i is as shown below. Also, assume that the round robin pointer points to the upper buffer at cycle i. Shown below are the states of all buffers during the next five cycles. Departing packets during a cycle are shown with an asterisk as also incoming packets that enter the switching fabric. Cycle i Stage 0 Stage 1 ------- ------- SW 0, top buffer *(4, 00) (0, 01)* SW 0, bottom buffer *(5, 01) (1, 01) SW 1, top buffer *(6, 11) (2, 10)* SW 1, bottom buffer *(7, 11) (3, 10) Cycle i+1 Stage 0 Stage 1 ------- ------- SW 0, top buffer *(8, 01) (4, 00)* SW 0, bottom buffer (5, 01) (1, 01)* SW 1, top buffer (6, 11) - SW 1, bottom buffer (7, 11) (3, 10)* Cycle i+2 Stage 0 Stage 1 ------- ------- SW 0, top buffer (8, 01) (5, 01)* SW 0, bottom buffer *(9, 11) - SW 1, top buffer (6, 11) - SW 1, bottom buffer *(10, 00) (7, 11)* Cycle i+3 Stage 0 Stage 1 ------- ------- SW 0, top buffer *(11, 10) (8, 01)* SW 0, bottom buffer *(12, 01) (10, 00)* SW 1, top buffer *(13, 01) (9, 11) SW 1, bottom buffer *(14, 10) (6, 11)* Cycle i+4 Stage 0 Stage 1 ------- ------- SW 0, top buffer (11, 10) (12, 01)* SW 0, bottom buffer - (13, 01) SW 1, top buffer *(15, 00) (9, 11)* SW 1, bottom buffer - (14, 10)* Cycle i+5 Stage 0 Stage 1 ------- ------- SW 0, top buffer *(16, 11) - SW 0, bottom buffer *(17, 10) (13, 01)* SW 1, top buffer (15, 00) (11, 10)* SW 1, bottom buffer *(18, 10) - Input ----- The first line of the input file comprises the three integers n #cycles #snapshots Each of these have meanings identical to those in Part 1. The specification of a packet is a pair as in the example above. The first element is a unique identifying integer, the second is the destination as explained above. Output ------ For each cycle specified in the input file for which a snapshot of the network is required, your program should output the packets buffered in each input buffer as shown above. Also, indicate the number of packet arrivals at each input port and the number dropped, if any.