전체 글 썸네일형 리스트형 Network Layer (2/4) : Data Plane Internet Protocol Datagram Format (IPv4 Datagram Format) - The Internet's network-layer packet is referred to as a datagram. - IPv4 datagrams have many key fields. - Time to live sets the max number remaining hops and is decremented at each router. - Upper layer has the upper layer protocol to deliver payload to. - 32 bit source IP address and 32 bit destination IP address is also stored. - Data.. 더보기 Network Layer (1/4) - Data Plane Goal : 1. Understand the principles behind network layer services - Network Layer Service Models - Forwarding vs Routing - How a router works - Generalized Forwarding 2. Instantiation, Implementation in the Internet Network Layer - The network layer provides host-to-host communication service. - There is a piece of the network layer in each and every host and router in the network. - The network.. 더보기 Greedy Greedy - Like DP or Divide&Conquer, Greedy is a programming paradigm rather than a specific algorithm. Minimum Spanning Tree - Let's assume we have a connected, undirected graph G=(V,E) with weight function w : E -> R. - The MST of the graph is a tree that connects all vertices with minimum weight. - An algorithm that finds the MST of a graph could be used when building Spanning Tree Protocol(ST.. 더보기 Dynamic Programming Dynamic Programming - Like Divide-and-Conquer, Dynamic Programming is a design technique of algorithms. Longest Common Subsequence(LCS) - LCS is a famous example of a problem that could be solved using DP. - Given two sequence x[1, ... , m] and y[1, ... , n], the goal is to find the longest subsequence common to both. - A naive approach is to check every subsequence of x to se if it is also a su.. 더보기 Order Statistics - In order to find the ith smallest of n elements, one naive approach is to sort the n elements using merge sort or heap sort and pick the ith element, which would take O(NlgN) time in the worst case. Randomized Divide-and-Conquer Algorithm - Instead we could use a randomized divide-and-conquer algorithm. - In this algorithm, we do not sort the sub arrays which are consisted of elements smaller .. 더보기 Trees Binary Search Tree - To build a BST with a given array input, the best time complexity would take O(NlogN) for N elements, and worst case would be O(N^2). - The worst case is when a the array is in ascending order or descending order. - This is because for each element, since the BST is skewed, it would take N comparisons to find the position for the corresponding element. - The expected time to.. 더보기 Transport Layer (3/3) Principles of Congestion Control - Packet Loss is typically resulted from the overflowing of router buffers as the network becomes congested. - To treat the cause of network congestion, mechanisms are needed to throttle senders in the face of network congestion. Scenario 1 - Let's assume that the router has an infinite amount of buffer space. - The left graph plots the per-connection throughput;.. 더보기 Transport Layer (2/3) Principles of Reliable Data Transfer - With a reliable channel, no transferred data bits are corrupted or lost, and all are delivered in the order in which they were sent. - It is the responsibility of a reliable data transfer protocol to implement this service abstraction. - For example, TCP is a reliable data transfer protocol that is implemented on top of an unreliable(IP) end-to-end network .. 더보기 이전 1 2 3 4 ··· 6 다음
