CS204 Fall 2013

1. We say that a packet switch (such as an Ethernet "switch" aka. layer-2 transparent bridge or an IP router) is non-blocking if its internal components can forward packets at "wire speed" between all ports simultaneously without dropping anything. For example, if the switch has N ports with a data rate of 100 Mbps, it must be capable of receiving packets at a combined rate of 100*N Mbps across all ports, and transmitting packets at a combined rate of 100*N Mbps across all ports, as long as the required output rate through every port is no more than 100 Mbps. In particular, such a switch must be capable of supporting any permutation, P, where all arrivals on port k exit through port P(k).
   
1. Suppose I give you several identical switches, each with the N ports running at the same data rate. Can you combine them to build a non-blocking network structure that connects more than N users?  Explain your answer.
2. Now let us relax the traffic-handling requirement in the following way. This time, let us assume that the destinations for packets arriving at each port is evenly distributed over the other ports. (Don't worry about random fluctuations -- just assume that a fraction 1/(N-1) of the packets from port i must exit through port j, for all j != i.) Also assume that N is "large enough" for us to ignore the fact that no packet exits through its entry port, so that half the traffic entering from any port exits through ports 1 through N/2, and half exits through ports N/2+1 through N. What is the maximum number of users that can be supported under this traffic model using two identical N-port switches? [HINT: Because of symmetry, assume that each switch uses M ports to create a multi-channel connection to the other switch and the remaining N-M ports to connect users.]
   
3. Repeat part (b) assuming you have three identical N-port switches.  Ignore the requirement that layer-2 bridged networks cannot have cycles, and consider both options where the three switches are directly connected to form a triangle, or switches 1 and 3 must communicate along a 2-hop path through switch 2. [HINT: Because of symmetry, assume each switch-switch connection uses M parallel channels, so in the second topology switch 2 has only N-2M ports available for connecting users.]
   
2. Many commercial Ethernet switches include one or more "uplink ports", whose data rate is exactly 10 times higher than a "normal" port, since Ethernet supports a variety of link speeds including 100 Mbps, 1 Gbps, 10 Gbps and 100 Gbps. Thus, for this question assume that: (i) all users are connected to "edge" switches (twenty 100 Mbps downlinks + two 1 Gbps uplinks), (ii) the uplinks from edge switches may be connected to "mid level" switches (twenty 1 Gbps downlinks + two 10 Gbps uplinks), and (iii) the uplinks from mid level switches may be connected to "core" switches (twenty 10 Gbps downlinks + two 100 Gbps uplinks). 
1. Suppose you have exactly two "core" switches and plenty of "edge" and "mid level" switches available. What is the largest (in terms of the number of connected users) non-blocking layer-2 bridged network you can construct below an interconnected pair of "core" switches?
2. Now suppose each "core" switch can function as an IP router (for traffic exchanged with other core switches, typically through its 100 Gbps uplinks) as well as a layer-2 transparent bridge (for traffic exchanged with its mid level switches through certain 10 Gbps downlinks). Briefly explain why this change allows us to construct a much larger network (in terms of number of connected users). The routed core should have very high capacity, but doesn't need to be fully non-blocking.
   
3. In addition to supporting high throughput and large numbers of connections, a large data center network must also be reliable, in the sense of continuing to operate despite the failures of a few links and/or switches.  Unfortunately, the "fat-tree" bridged network you created in problem 2(a) has zero redundancy, so that any single failure will disconnect the network. A naïve solution to this problem would be to duplicate the entire network, by installing a backup ("blue") switch next to each regular ("red") switch and then: (i) installing "red" and "blue" network cards in all users and connecting each to the same-colored "edge" switch; (ii) adding "blue" switch-switch links to connect all "blue" switches in the same pattern as the "red" network"; and (iii) adding "purple" switch-switch links to connect each "red" switch to the backup "blue" switch on the next level (both up and down) of the tree.
1. How must the total number of ports in each switch change to support the "purple" connections?
2. Suppose you run Spanning Tree on your "red"/"blue"/"purple" network. What fraction of the total number of links and  switches will be active, assuming one of the "red" core switches forms the root of the (active) tree?
3. Suppose you have been able to force the active tree to include all "red" and "blue" links, plus a single "purple" link between core nodes. What happens when a user tries to send a packet from its "red" network interface to its neighbor's "blue" network interface?
   
4. If we eliminate the tree topology restriction, we could make use of "backup" hardware all the time, to increase throughput and/or shorten path lengths in the network. However, doing so by moving from layer-2 bridging to IP routing has disadvantages related to management complexity and higher equipment cost. Thus both the IETP (via "TRILL") and IEEE 802 (via "Shortest Path Bridging") are developing separate standards for layer-2 switched networks that can support mesh-like topologies. Read at least two sources describing each proposal (including at least one standards document) and then summarize their main ideas in a couple of paragraphs (say 200-300 words).
   

What to turn in.