CSCI 356 / Fall 2024
Computer Networking
Update Nov 20, 3pm: The checksum calculation was clarified, below.
Note: We haven't yet covered in class all the topics that appear below, but we have covered some, and will cover others soon, and you can find material in the texbook on these topics as well.
The first exercises we won't cover for a while, so you'll have to invent your own strategy. Be creative!
Congratulations, you've been hired by VectorCorp, a bike courier startup company, working out of their station in the Mission Hill neighborhood. From the VectorCorp station, you can dispatch cyclists directly to a few destinations around the city using your own VectorCorp couriers. But your Mission Hill station is just one in a large coalition of bike courier companies, each operating out of a different neighborhood. You can make use of these partner companies to reach places that VectorCorp's local couriers can't reach directly. In fact, some of VectorCorp's cyclists from Mission Hill are pretty slow and the terrain varies, so depending on the destination, it might even be faster to hand off a package to a partner company in some other neighborhood, even if VectorCorp could have carried the package directly to the destination.
From their home base in Mission Hill, there are FIVE destinations VectorCorp can reach directly using their own couriers:
From Mission Hill to... Time, and Method
Dorchester 45 minutes, by direct local courier
Fenway 12 minutes, by direct local courier
Jamaica Plain 30 minutes, by direct local courier
Mission Hill 0 minutes, obviously, that's our station
Roxbury 15 minutes, by direct local courier
South End 35 minutes, by direct local courier
VectorCorp needs to create a delivery plan for their cyclists to deliver packages, but needs more info to build a more complete list of neighborhoods and estimates for how long it takes to reach each one. Sadly they aren't too tech savvy, and they rely entirely on looking at the public advertisements from their five neighboring stations.
(a) A flyer arrives from Roxbury carrying the following advertisment:
Daily Advertisement for Roxbury Delivery Station!
We [1] can get your package to... in just
Dorchester 10 minutes
Mission Hill 28 minutes
Jamaica Plain 32 minutes
South Boston 20 minutes
South End 15 minutes
Fenway 10 minutes
Back Bay 10 minutes
[1] The small print: deliveries to some destinations may rely on partner companies.
Use the above information to complete the delivery plan for your cyclists to use when packages are dropped off at your station, using the fastest possible route for each destination. Some destinations are already filled in for you. For Dorchester, for example, we could go direct in 45 minutes, but it's better to send packages to Roxbury (15 minutes away), then let Roxbury station deliver to Dorchester (somehow, perhaps direct, or perhaps through some other station, we don't really care how, but they say they can do it in 10 minutes), for a total time of 25 minutes.
From Mission Hill to... Time, and Method
Back Bay ______________________________
Dorchester 25 minutes, via Roxbury
Fenway 12 minutes, by direct local courier
Jamaica Plain ______________________________
Mission Hill 0 minutes, obviously, that's our station
Roxbury ______________________________
South Boston ______________________________
South End ______________________________
(b) The next day, a new flyer arrives, this time from Fenway:
Daily Advertisement for Fenway Delivery Station!
We [1] can get your package to... in just
Back Bay 10 minutes
South End 28 minutes
South Boston 20 minutes
Beacon Hill 32 minutes
Allston 32 minutes
Roxbury 15 minutes
[1] The small print: deliveries to some destinations may rely on partner companies.
Use this advertisement, combined with info from your previous delivery plan from the last question, to generate a new delivery plan for your Mission Hill cyclists. Include all known destinations.
From Mission Hill to... Time, and Method
Allston ______________________________
Back Bay ______________________________
_______________________ ______________________________
_______________________ ______________________________
_______________________ ______________________________
_______________________ ______________________________
_______________________ ______________________________
_______________________ ______________________________
_______________________ ______________________________
_______________________ ______________________________
Congratulations, you've been hired by StateLink, a new public transit startup company financed by your state's government. Your first assignment is to determine the least expensive way to get between certain popular destinations by public transit.
Sadly, with the state of public transit in your area, you don't have much to start with: no comprehensive map, and no multi-city route information. Instead, you have only information about direct city-to-city bus links. For example, there is a direct bus going between city A and city B (in either direction) for $9, and there is also a second direct bus link between A and D (either direction) for $10. This means you can get from D to B using the route D-A-B for a cost of $19. Of course, there might be a better option going through some other city, or going through multiple cities. Remember: StateLink is looking for the cheapest routes, not the most convenient ones.
Fare... Direct Bus Link Fare... Direct Bus Link
$ 9 A - B $ 21 E - I
$ 12 A - E $ 6 F - G
$ 10 A - D $ 15 F - I
$ 13 B - C $ 12 G - I
$ 2 B - E $ 14 G - L
$ 7 B - F $ 12 H - I
$ 19 C - G $ 11 I - K
$ 7 D - E $ 3 I - L
$ 3 D - H $ 8 J - K
$ 16 D - J $ 7 K - L
$ 11 E - F
For each of the following pairs, find the least expensive route between the two cities, and give both the total cost of the optimal route and the list of cities on the route. Your new boss isn't very tech savvy, so you'll have to work on paper and pencil and briefly explain your work or show your method, providing just enough detail to convince them your results are reasonble.
Hint: Draw a map? Or start from one city and work outward looking for direct routes, 2-link routes, 3-link routes, etc., keeping track as you work of the cheapest routes to various destinations so far. If looking for help online, there are many algorithms for "shortest path on a graph".
(a) Encode the first 4 or 5 letters of your login name in Manchester encoding. Draw your answer as a time-varying signal of high and low values. Try to be reasonably consistent about the duration of each value: a short line for a single low, twice as long for two lows in a row, etc. Your signal should be continuous, i.e. connected together so it can be drawn completely in one pass without lifting the pencil.
For example, I'm kwalsh. You can find ASCII tables online, but the ASCII letter 'k' in binary is 01101011. ASCII 'w' is 01110111. ASCII 'a' is 01100001, and so on. Thus kwalsh = 011010110111011101100001... Next I'd take each bit and do Manchester encoding: each 1 becomes "low-then-high" (i.e. low value for 1 unit of time, transition to high, then hold high for 1 unit of time), and each 0 becomes "high-then-low" (i.e. high value for 1 unit of time, transition to low, then hold low for 1 unit of time). When putting all the bits together, some pieces fit together naturally, for others you will need to add some extra transitions (shown as gray lines) to connect the individual pieces so the overall signal is continuous.
(b) When using Manchester encoding, it's possible to have two "high" signal values in a row (see above example). Is it possible to have three or more "high" signal values in a row? Give an example, or explain why not.
(c) If a signal is constructed from some combination of high values of duration 1 or 2 and some low values of length 1 or 2, is it guaranteed the signal is a valid Manchester encoding of some binary value? If not, give an example of a signal that is not valid and explain why it isn't valid. Otherwise, prove or informally explain why every signal constructed from such pieces must always be a valid encoding. Here, you should assume the signal duration is an even number (because odd-length signals are never valid Manchester encodings). Or if you'd prefer, just assume a low value of duration 1 is always added to the end of odd-length signals in order to strech it into an even-length signal.
(a) Decode the above manchester-encoded signal into an ascii (text) message. Show your work in some way. This signal doesn't use the full standard ethernet frame layout, but instead uses a abbreviated format consisting of only:
HINT: The message starts with "M" and is a person's name. It might not be a familiar name to you. Google it.
(b) Is this frame corrupt? Show your work to recalculate and verify whether the checksum is valid or not. Rephrased for clarity... In this frame, the sender has calculated the checksum as the 8-bit ones-complement sum of all payload bytes (with wraparound), complemented (flipped). The receiver can do an 8-bit ones-comoplement sum of ALL bytes, including the checksum, with wraparound, and should obtain an all-ones result (0xff) upon success. As with real Ethernet, the preamble and SOF are not normally included in checksum calculations, since they don't ever change and errors in them are easily detected even without a checksum.
Hint 0: If working on paper, you might want to split the wave in 2 or 3 pieces, and print each picture in hardcopy in landscape paper mode. Then write down the raw 0's and 1's beneath the waveform, then decode each pair into a bit.
Hint 1: Decode the manchester-encoded preamble to get a sense of the timing (i.e. length of each bit, and distinguishing which transitions are "between" bits versus those transitions that fall in the center of a bit and represent an encoded bit value). You know what the preamble is supposed to be, so you'll know if you have the right timing.
Hint 2: Once you get the premble, look for the SOF.
Hint 3: Next decode the payload. There are ascii tables online, as well as binary-to-hex tools if you have forgotten your hexadecimal!