Computational Thinking II - Lecture Summary and Exam Information
3 views 0 purchase
Course
Computational Thinking II (IS553)
Institution
Universität Mannheim (UMA)
Book
From Computing to Computational Thinking
A comprehensive review of lecture content, exercise classes, and the exam Q&A. I got 1.3 in the FSS 2020 exam with this note and hope that you will find it helpful.
Computational Thinking II – FSS 2020
Ch1. The Internet
Ch2. The Internet protocol stack
Ch3. Web Servers
Ch4. HTML
Ch5. Apache and PHP
Ch6. Databases
Ch7. Databases and PHP
Ch8. Business Logic and JavaScript
Ch9. Security
Ch1. The Internet
Distance vector routing vs. link state routing:
Distance vector routing:
- Only know the distance to neighbors → rely on this info to know to which of your
neighbor you forward the message to
- Not have global knowledge → hard to adapt to death nodes in network
Link state routing:
- Have global knowledge → know every port + every intermediate node on that port →
much more computational resources are required. But better adapt to death nodes.
- You don’t determine the path that everybody has to stick to it → cannot tell your
neighbor which path your neighbor should fwd the message to. You compute the
global optimal path to choose the neighbor and expect them to do the same → the
neighbor again compute the global optimal path from its own location to compute the
globally optimal path → this is very computationally expensive & storage expensive
- Problem: It requires every router to have global knowledge → huge routing table →
not scalable
Hierarchical routing:
We have millions of nodes in network + hierarchical routing → group nodes into regions →
know how to reach a specific region → inside each region, a node is known and optimal
routing can be done there.
1. Distance Vector Routing:
- Each vector maintains a routing table (column=’destination_router’, ‘distance’, ‘outgoing_line’)
- Routers know distance to their direct neighbors (local knowledge)
- Routing table is updated regularly: routers send their tables to every neighbor.
- Each router updates its own routing table using the tables from its neighbors. → define the
fastest route.
➢ Properties:
o Adapts fast to new nodes in the network
o Adapts slowly to dead nodes in the network (the count-to-infinity problem)
1
, Computational Thinking II – FSS 2020
➢ The count-to-infinity problem: happens when routers do not have the global knowledge
about the network structure
A --------- B ---------C
• Here, at first, router C uses router B to connect A.
• When the link A-B breaks, B tries to connect to A via C (distance = 3), not knowing that
this route uses B itself.
• Then, C updates distance to A = 4
• B updates its distance to A = 5
• ………
• This process would lead to distance of infinity for both nodes.
2. Link state routing
Each router must:
• Discover its neighbors.
• Measure delay/cost to each of its neighbors.
• Construct a packet telling all it has learned.
• Send this packet to ALL OTHER routers. (in Distance Vector: only send neighbors)
• Compute the shortest path to every other router.
Each router gains global knowledge + must have a globally unique address.
Steps:
(1) Learning about neighbors
(2) Measure link cost (measure delay in ECHO message → take half of the link delay)
(3) Build link state packets (containing: router name, sequence number and age, delay of all
neighbors).
(4) Distribute the packets
➢ Characteristics: they are flooded; each router must keep track of the most recent
packets
➢ How to deal with duplicates and old packets?
- Only use packet with the highest sequence number from a router.
- Discard packets with lower sequence numbers.
➢ How to deal with false information and old packets?
- Discard if the packet is to old.
(5) Computing new routes
Problem: Memory and computationally expensive → not scalable.
Solution: Hierarchical routing
3. Hierarchical routing
When we have millions of nodes in network, hierarchical routing groups nodes into regions →
each router knows how to reach a specific region
Inside each region, a node is known and optimal routing can be done there.
2
, Computational Thinking II – FSS 2020
Idea brief:
• Group computers within each region and connect all regions.
• Routers in each region know everything about their regions.
• Every router knows one path to other regions.
Pros:
- Reduce network loads.
- Reduce size of the routing tables.
- Reduce computation load on routers
- ➔ increase scalability
Cons:
- No longer optimal (but save a lot of complexity).
3
, Computational Thinking II – FSS 2020
Ch2. The Internet protocol stack
Communication protocol = set of rules between entities that allows communication between
them.
Realizing protocol? ➔ Protocol Stack!
I. Protocol hierarchy
- Within each computer: n layers
- The lowest layers (L1) of 2 computers are connected by physical medium
Concepts:
➢ Layer interfaces between adjacent layers: defines the service that the lower layer offers to
the higher layer → physical communication.
➢ Same level protocols (e.g. L5 protocol): a set of protocols for communication between
same layer in 2 different computers → virtual communication.
More layers = more overhead information in each message.
➢ Protocol stack = group of protocols
➢ Protocols in a stack: determine the interconnectivity rules for a layered network model (e.g.
OSI or CTP/IP). To be a stack, the protocols must be interoperable (able to connect both
vertically between layers and horizontally between end-points in the network)
➢ Connect vertically: How lower layer server upper layer; and how upper layer can use its
lower layer.
1. Three general layers (not including Application Layer) in the Internet protocol stack:
(1) Network Access Layer: Finds the correct device to forward the message to and transmits the
message via a physical connection.
(2) Internet Layer: Finds the correct receiver in the global network (Internet) and forwards
message via (multiple) routers to this device.
(3) Transport Layer: Addresses the correct process via a port number on the receiving devices
(both UDP and TCP) to make sure that the message is received by the correct application.
TCP also ensures that the message is actually sent. UDP does not guarantee this.
Hence, the roles of the message headers for each layer:
(1) Ethernet header (Network Access Layer): Address host on local network.
(2) IP header (Internet Layer): Address host on global network.
(3) TCP header (Transport Layer): Address process on host.
2. Internet Protocol (IP)
a) IP provides:
- addressing of host
- unreliable packet-based communication between hosts
4
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller sonphan. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $10.33. You're not tied to anything after your purchase.
