Data Networks Lecture 1 Introduction Eytan Modiano Eytan Modiano Slide 16.263: Data Networks • Fundamental aspects of network Design and Analysis: – Architecture Layering Topology design – Protocols Pt.-to-Pt. Multiple access End-to-end – Algorithms Error recovery Routing Flow Control – Analysis tools Probabilistic modeling Queueing Theory Eytan Modiano Slide 2Course Information • Lecturer: Professor Eytan Modiano • Requirements & Grading – About one problem set per week (10% of grade) – Project (5% of grade) – Midterm exam (35 %) – Final Exam during finals week (50%) • Prerequisite Policy: 6.041, or an equivalent class in probability • Textbook: Bertsekas & Gallager, Data Networks (2nd Edition) Eytan Modiano Slide 3Tentative syllabus LEC # TOPICS 1 Introduction, OSI 7-layer architecture 2 Data Link Layers, Framing, error detection 3 Retransmission Algorithms 4 Retransmission Algorithms 5 Queueing Models - Introduction & Little's theorem 6 M/M/1, M/M/m, queues etc. 7 Networks of queues 8 M/G/1 queues, M/G/1 w/ vacations 9 M/G/1 queues and reservations, priority queues 10 Stability of queueing systems 11 M/G/1 queue occupancy distribution 12 Quiz Eytan Modiano Slide 4Tentative syllabus, continuedLEC # TOPICS 13 Multiple access & Aloha 14 Stabilized Aloha, Tree Algorithms 15 CSMA, CSMA/CD and Ethernet 16 High-speed LANs, Token rings, Satellite reservations 17 Introduction to switch architecture 18 High Speed Switch Scheduling 19 Broadcast routing & Spanning trees 20 Shortest path routing 21 Distributed routing algorithms, optimal routing 22 Flow Control - Window/Credit Schemes 23 Flow Control - Rate Based Schemes 24 Transport layer and TCP/IP 25 ATM Networks 26 Special topic: Optical Networks, Wireless networks Final Exam during final exam week. Date and time to be announced. Eytan Modiano Slide 5Network Applications • Resource sharing – Computing – Mainframe computer (old days) Today, computers cheaper than comm (except LANS) Printers, peripherals – Information DB access and updates E.g., Financial, Airline reservations, etc. • Services – Email, FTP, Telnet, Web access – Video conferencing – DB access – Client/server applications Eytan Modiano Slide 6Network coverage areas • Wide Area Networks (WANS) – Span large areas (countries, continents, world) – Use leased phone lines (expensive!) 1980’s: 10 Kbps, 2000’s: 2.5 Gbps User access rates: 56Kbps – 155 Mbps typical – Shared comm links: switches and routers E.g, IBM SNA, X.25 networks, Internet • Local Area Networks (LANS) – Span office or building – Single hop (shared channel) (cheap!) – User rates: 10 Mbps – 1 Gbps E.g., Ethernet, Token rings, Apple-talk • Metro Area networks (MANS) • Storage area networks Eytan Modiano Slide 7Network services • Synchronous – Session appears as a continuous stream of traffic (e.g, voice) – Usually requires fixed and limited delays • Asynchronous – Session appears as a sequence of messages – Typically bursty – E.g., Interactive sessions, file transfers, email • Connection oriented services – Long sustained session – Orderly and timely delivery of packets – E.g., Telnet, FTP • Connectionless services – One time transaction (e.g., email) • QoS Eytan Modiano Slide 8Switching Techniques • Circuit Switching – Dedicated resources • Packet Switching – Shared resources – Virtual Circuits – Datagrams Eytan Modiano Slide 9Circuit Switching • Each session is allocated a fixed fraction of the capacity on eachlink along its path – Dedicated resources – Fixed path – If capacity is used, calls are blocked E.g., telephone network • Advantages of circuit switching – Fixed delays – Guaranteed continuous delivery • Disadvantages – Circuits are not used when session is idle – Inefficient for bursty traffic – Circuit switching usually done using a fixed rate stream (e.g., 64Kbps) Difficult to support variable data rates Eytan Modiano Slide 10Problems with circuit switching • Many data sessions are low duty factor (bursty), (message transmission time)/(message interarrival time) << 1 Same as: (message arrival rate) * (message transmission time) << 1 • The rate allocated to the session must be large enough to meet thedelay requirement. This allocated capacity is idle when the sessionhas nothing to send • If communication is expensive, then circuit switching isuneconomic to meet the delay requirements of bursty traffic • Also, circuit switching requires a call set-up during whichresources are not utilized. If messages are much shorter than thecall set-up time then circuit switching is not economical (or evenpractical) – More of a problem in high-speed networks Eytan Modiano Slide 11Circuit Switching Example L = message lengths λ = arrival rate of messages R = channel rate in bits per second X = message transmission delay = L/R – R must be large enough to keep X small – Bursty traffic => λx << 1 => low utilization • Example – L = 1000 bytes (8000 bits) – λ = 1 message per second – X < 0.1 seconds (delay requirement) – => R > 8000/0.1 = 80,000 bps Utilization = 8000/80000 = 10% • With packet switching channel can be shared among manysessions to achieve higher utilization Eytan Modiano Slide 12Packet Switched Networks Packet Network PS PS PS PS PSPS PS Buffer Packet Switch Messages broken into Packets that are routed To their destination Eytan Modiano Slide 13Eytan ModianoSlide 14Packet Switching• Datagram packet switching– Route chosen on packet-by-packet basis– Different packets may follow different routes– Packets may arrive out of order at the destination– E.g., IP (The Internet Protocol)• Virtual Circuit packet switching– All packets associated with a session follow the same path– Route is chosen at start of session– Packets are labeled with a VC# designating the route– The VC number must be unique on a given link but can change fromlink to link Imagine having to set up connections between 1000 nodes in a mesh Unique VC numbers imply 1 Million VC numbers that must be represented and stored at each node– E.g., ATM (Asynchronous transfer mode)Eytan ModianoSlide 15Virtual Circuits Packet Switching• For datagrams, addressing information must uniquely distinguish each network node and session – Need unique source and