Data Communication and Networking Dr –Ing Vo Que Son Email: sonvq@hcmut.edu.vn Telecomm Dept Faculty of EEE DCN HCMUT Content  Chapter 3: Data Link Layer Protocols  Flow Control  Error Control  Connection Management  Data link layer Protocols  Chapter 4: Communication Networks  Introduction to communication networks  802.x standard and TCP/IP Model  Ethernet, Token Pass, Token Ring  IP Addressing: Classfull and VLSM  Network devices  Switching and Routing  STP, VLAN Telecomm Dept Faculty of EEE DCN HCMUT Local Area Network  A local area network (LAN) is a computer network that interconnects computers in a limited area such as a home, school, computer laboratory, or office building using network media  Medium:  Coaxial cable  Twisted-pair line Telecomm Dept Faculty of EEE DCN HCMUT Wide Area Network  A wide area network (WAN) is a network that covers a broad area (i.e., any telecommunications network that links across metropolitan, regional, or national boundaries) using private or public network transports Telecomm Dept Faculty of EEE DCN HCMUT Physical Topology Bus Ring Star Telecomm Dept Faculty of EEE Extended Star Hierarchical Mesh DCN HCMUT Project 802  IEEE 802 refers to a family of IEEE standards dealing with local area networks and metropolitan area networks  The services and protocols specified in IEEE 802 map to the lower two layers (Data Link and Physical) of the seven-layer OSI networking reference model In fact, IEEE 802 splits the OSI Data Link Layer into two sub-layers named Logical Link Control (LLC) and Media Access Control (MAC), so that the layers can be listed like this: Data link layer • LLC Sublayer: • MAC Sublayer Physical layer Telecomm Dept Faculty of EEE DCN HCMUT Project 802  Modules in Project 802  LLC: based on HDLC protocol  Multiplexing protocols transmitted over the MAC layer (when transmitting) and decoding them (when receiving)  Providing node-to-node flow and error control  MAC: provides addressing and channel access control mechanisms that make it possible for several terminals or network nodes to communicate within a multiple access network that incorporates a shared medium Telecomm Dept Faculty of EEE DCN HCMUT LLC Frame formats LLC PDU: DSAP: Destination Service Access Point SSAP: Source Service Access Point Control field: HDLC format Telecomm Dept Faculty of EEE DCN HCMUT Ethernet  Topology: bus, star, ring  Media Access Control: Deterministic, Non-deterministic  Addressing: Every computer has a unique way of identifying itself : MAC address or physical address The physical address is located on the Network Interface Card (NIC) MAC addresses have no structure, and are considered flat address spaces MAC addresses are sometimes referred to as burned-in addresses (BIAs) because they are burned into read-only memory (ROM) and are copied into random-access memory (RAM) when the NIC initializes • 0000.0c12.3456 or 00-00-0c-12-34-56 • If MAC is all bits 1: broadcast address Telecomm Dept Faculty of EEE DCN HCMUT IEEE 802.3: frame format  Preamble: 10101010 (7 bytes)  The Start Frame field (10101011) tells other devices on the network that a frame is coming down the wire  The Address field stores the source and destination MAC addresses  Source address is unicast, Destination address can be unicast, multicast or broadcast  The Type/Length field is an optional field  Exact length of frame, or Layer protocol making the sending request, or Not used  The Data field is the actual information being sent by the upper layer protocols Therefore, it will be all upper layer data  CRC: bytes, error checking Telecomm Dept Faculty of EEE DCN HCMUT 10 Routing Each router needs running a routing protocol to update the its routing table Delay of packets Queuing delay Processing delay Propagation delay Telecomm Dept Faculty of EEE DCN HCMUT 61 Routing Protocols: Classification  Global or decentralized information?  Global: • all routers have complete topology, link cost info • “link state” algorithms  Decentralized: • router knows physically-connected neighbors, link costs to neighbors • iterative process of computation, exchange of info with neighbors • “distance vector” algorithms  Static or dynamic?  Static: • routes change slowly over time  Dynamic: • routes change more quickly • periodic update • in response to link cost changes Telecomm Dept Faculty of EEE DCN HCMUT 62 Routing Algorithms: Link State Dijkstra’s algorithm  net topology, link costs known to all nodes  accomplished via “link state broadcast”  all nodes have same info  computes least cost paths from one node (‘source”) to all other nodes  gives forwarding table for that node Notation:  c(x,y): link cost from node x to y; = ∞ if not direct neighbors  D(v): current value of cost of path from source to dest v  p(v): predecessor node along path from source to v  N': set of nodes whose least cost path definitively known  iterative: after k iterations, know least cost path to k dest.’s Telecomm Dept Faculty of EEE DCN HCMUT 63 Dijkstra’s algorithm: example Step N' u u,x u,x,y u,x,y,v u,x,y,v,w u,x,y,v,w,z D(v),p(v) D(w),p(w) 2,u 5,u 2,u 4,x 2,u 3,y 3,y D(x),p(x) 1,u D(y),p(y) ∞ 2,x D(z),p(z) ∞ ∞ 4,y 4,y 4,y u Telecomm Dept Faculty of EEE v x w z y DCN HCMUT 64 Dijkstra’s algorithm: example Resulting shortest-path tree from u: v w u z x y Resulting forwarding table in u: destination link v x (u,v) (u,x) y (u,x) w (u,x) z (u,x) Telecomm Dept Faculty of EEE DCN HCMUT 65 Dijkstra’s algorithm, discussion  Algorithm complexity: n nodes  each iteration: need to check all nodes, w, not in N  n(n+1)/2 comparisons: O(n2)  more efficient implementations possible: O(nlogn)  Do not work with negative link costs:  Oscillations possible: Dijkstra selects vertex immediately after But shortest path from to is 0-1-2-3  e.g., link cost = amount of carried traffic D A 0 C 1+e B e 2+e D e initially Telecomm Dept Faculty of EEE A 1+e C 0 B … recompute routing D A 0 C 2+e B 1+e … recompute 2+e D A 1+e C B e … recompute DCN HCMUT 66 Dijkstra’s algorithm: Example Given a network topology with the link cost of distance (km) Assuming v=2.108 m/s: Find the Shortest Path from node A to other nodes so that the end-to-end delay is smallest? If the packet processing time at each node is 1us, how can you modify the algorithm? Telecomm Dept Faculty of EEE DCN HCMUT 67 Distance Vector Algorithm Bellman-Ford Equation (dynamic programming) Define: dx(y) := cost of least-cost path from x to y Then dx(y) = {c(x,v) + dv(y) } where is taken over all neighbors v of x Telecomm Dept Faculty of EEE DCN HCMUT 68 Bellman-Ford example Clearly, dv(z) = 5, dx(z) = 3, dw(z) = u v x w z y B-F equation says: du(z) = { c(u,v) + dv(z), c(u,x) + dx(z), c(u,w) + dw(z) } = {2 + 5, + 3, + 3} = Node that achieves minimum is next hop in shortest path ➜ forwarding table Telecomm Dept Faculty of EEE DCN HCMUT 69 Distance Vector Algorithm Dx(y) = estimate of least cost from x to y Node x knows cost to each neighbor v: c(x,v) Node x maintains distance vector Dx = [Dx(y): y є N ] Node x also maintains its neighbors’ distance vectors For each neighbor v, x maintains Dv = [Dv(y): y є N ] Telecomm Dept Faculty of EEE DCN HCMUT 70 Distance Vector Algorithm Basic idea: From time-to-time, each node sends its own distance vector estimate to neighbors Asynchronous When a node x receives new DV estimate from neighbor, it updates its own DV using B-F equation: Dx(y) ← minv{c(x,v) + Dv(y)} for each node y ∊ N Under minor, natural conditions, the estimate Dx(y) converge to the actual least cost dx(y) Telecomm Dept Faculty of EEE DCN HCMUT 71 Distance Vector Algorithm Iterative, asynchronous: each local iteration caused by:  local link cost change  DV update message from neighbor Each node: wait for (change in local link cost or msg from neighbor) Distributed:  each node notifies neighbors only when its DV changes  neighbors then notify their neighbors if necessary Telecomm Dept Faculty of EEE recompute estimates if DV to any dest has changed, notify neighbors DCN HCMUT 72 Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = node x table from x y ∞∞ ∞ z ∞∞ ∞ node y table cost to x y z cost to x y z from cost to x y z x y z x ∞ ∞ ∞ y z ∞∞ ∞ node z table cost to x y z from from x x ∞∞ ∞ y ∞∞ ∞ z Telecomm Dept Faculty of EEE Network Layer y z time DCN HCMUT 73 x ∞∞ ∞ y ∞∞ ∞ z Telecomm Dept Faculty of EEE cost to x y z x y z x y z from cost to x y z cost to x y z cost to x y z x y z x y z from from from x ∞ ∞ ∞ y z ∞∞ ∞ node z table cost to x y z x y z x y z cost to x y z cost to x y z from from x y ∞∞ ∞ z ∞∞ ∞ node y table cost to x y z from cost to x y z from node x table from Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = x y z time DCN HCMUT 74 Distance Vector: link cost changes Link cost changes:  node detects local link cost change  updates routing info, recalculates distance vector  if DV changes, notify neighbors “good news travels fast” Telecomm Dept Faculty of EEE x y 50 z At time t0, y detects the link-cost change, updates its DV, and informs its neighbors At time t1, z receives the update from y and updates its table It computes a new least cost to x and sends its neighbors its DV At time t2, y receives z’s update and updates its distance table y’s least costs not change and hence y does not send any message to z DCN HCMUT 75