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
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
