Transcript Burke*s theorem and networks of queues

INTRODUCTION
Weiqiang Sun
About the course
• Lecturer: Weiqiang Sun (孙卫强)
• TA: Kai Kang(康凯)
• Requirements and grading:
– One problem set each week (20%)
– Class participation (15%)
– Final exam (65%)
• Textbook
– Bertsakas & Gallager, Data Networks, 2nd Edition
• Course website (lecture notes, problem set & solutions etc.)
– http://front.sjtu.edu.cn/datacomm/
Weiqiang Sun
2
Content coverage
• This course will cover fundamental aspects of data network analysis
and design
– Architecture
• Network layering
– Protocols
• Point-to-point
• End to end
• Multi-access
– Algorithms
• Error recovery
• Routing
• Flow control
– Analysis tools
• Queueing theory
• Probabilistic modeling
Weiqiang Sun
3
Course syllabus
#
TOPICS
1 Introduction to Data Networks
2 The data link layer: framing and error correction
3 The data link layer: ARQ protocols
4 The Little's Theorem
5 M/M/x Queue
6 Burke's Theorem and network of queues
7 M/G/1 queue
8 Reservation and priority queues
9 Aloha protocol
10 Local Area Networks: CSMA and CSMA/CD
11 Broadcasting routing and routing in data networks
12 Flow and Congestion Control
13 Higher Layer Protocols: TCP/IP and ATM
Weiqiang Sun
WEEK #
1
2
3
4
5
6
7
8
9
10
11
12
13
4
Guest lectures (tentative)
#
TOPICS
Guest speaker
Monique J. Morrow (Cisco
SP AP CTO)
Trends and challenges in
A-Qiang Shen, Assistant
2
China Mobile communications
Prof. of BUPT, China
Broadband Access in Shanghai
3
Chengbing Shen
Telecom
1 The future of data networks
Weiqiang Sun
Week #
TBD
TBD
TBD
5
The history of Internet
•
•
•
•
•
•
•
•
•
•
1946, first appearance in science fiction: A logic named Joe
1969, interconnection of two nodes, later became ARPANET
1974, TCP Protocol became an RFC and the first use of term “Internet”
1976, X.25 became a CCITT (later ITU-T) standard
1978, International packet switched service in US and Europe
1981, X.25 based network grew from Europe and US to Canada, HK
and Australia
1983, first TCP/IP base wide-area network started to operate, NSFNET
started construction in 1985
1989, commercial mail services were available on NSFNET
1991, WWW was publicized at CERN: European Organization for
Nuclear Research
1996, the use of internet had become commonplace
Weiqiang Sun
6
The history of Internet
•
•
•
•
•
•
•
•
•
•
1946, first appearance in science fiction: A logic named Joe
1969, interconnection of two nodes, later became ARPANET
1974, TCP Protocol became an RFC and the first use of term “Internet”
1976, X.25 became a CCITT (later ITU-T) standard
1978, International packet switched service in US and Europe
1981, X.25 based network grew from Europe and US to Canada, HK
and Australia
1983, first TCP/IP base wide-area network started to operate, NSFNET
started construction in 1985
1989, commercial mail services were available on NSFNET
1991, WWW was publicized at CERN: European Organization for
Nuclear Research
1996, the use of internet had become commonplace
Weiqiang Sun
7
Network applications
•
•
•
•
•
•
•
•
E-mail
The World Wide Web
Remote access
Collaboration
File sharing (FTP, BT etc)
Streaming (PPLive, IPTV etc)
Voice telephony (VoIP)
And much more….
Weiqiang Sun
8
Network coverage areas
• Wide Area Networks (WAN)
– Large footprint, usually country scale, or inter-country scale, 1000KM and more
– Use leased line/circuit switching
• Metro Area Networks (MAN)
– Medium footprint, in a city (metropolitan), 50-100KM
– Provides connectivity for LAN in a city
• Local Area Networks (LAN)
– Small span, in a building or office, ~100M
– Direct high speed connection
•
•
•
•
Home Area Networks (HAN)
Personal Area Networks (PAN)
Storage Area Networks (SAN)
…
Weiqiang Sun
9
Switching techniques
• Circuit switching
– Dedicated resources
– Low efficiency
– Higher Quality of Service
• Packet switching
–
–
–
–
Shared resources
Can be used to implement virtual circuits
High efficiency
Prone to congestion and packet loss
Weiqiang Sun
10
Network footprints and switching
techniques
• Wide Area Networks (WAN)
• Metro Area Networks (MAN)
• Local Area Networks (LAN)
• Home Area Networks (HAN)
Circuit switching
Packet switching
• Personal Area Networks (PAN)
• Storage Area Networks (SAN)
• …
Weiqiang Sun
11
The layered network model – OSI
reference model
Application
Application
Presentation
Presentation
Session
Session
Transport
Transport
Network
Network
Network
Network
Data Link
Control
DLC
DLC
DLC
DLC
Data Link
Control
Physical
Interface
PHY
PHY
PHY
PHY
Physical
Interface
Weiqiang Sun
12
The OSI reference model in the context of
broadband access – an example
Your PC
Your friend’s PC
Application
Application
Presentation
Presentation
Session
Session
Transport
W-less router
….
Transport
Network
Network
Network
Network
DSL Modem
Data Link
Control
DLC
DLC
Physical
Interface
PHY
PHY
Weiqiang Sun
DLC
PHY
PHY
DLC
DLC
Data Link
Control
PHY
PHY
Physical
Interface
13
The layered network model – OSI
reference model
Peer communications
Application
Presentation
Application
Presentation
Inter-layer
communications
Session
Session
Transport
Transport
Network
Network
Network
Network
Data Link
Control
DLC
DLC
DLC
DLC
Data Link
Control
Physical
Interface
PHY
PHY
PHY
PHY
Physical
Interface
Weiqiang Sun
14
The physical layer
• Responsible for transmission of bits over a link
– Wireline link, such as twisted pair, fiber optics, serial lines etc
– Wireless link, such as satellite link, free space optics, microwave etc
• Modulation and de-modulation (MODEM)
– Mapping the bits from high layer to signals and the reverse
• Modes of operation
– Synchronous, intermittent synchronous, and asynchronous
• Can incur transmission errors
– Noise, power loss etc
• Can induce transmission delay
– The speed of light (EM wave)
Weiqiang Sun
15
The data link control layer
• Responsible for error-free transmission of bits across a pointto-point link
– Realizes a reliable “virtual” link
– Re-transmit, or drop packet if some error occurs
• Framing, error detection and correction
• Sometimes in a shared media, is also responsible for
contention resolution/access control
– e.g. in a wireless radio network
– The MAC sublayer
Weiqiang Sun
16
The Network layer
• Routing and flow control in the network (network wide)
• One network layer process on each node
• Route the packets to the proper outgoing DLC, or to up layer
(at destination)
Network layer
DLC Layer
Link 1
Weiqiang Sun
DLC Layer
Link 1
A node
DLC Layer
Link 1
17
The transport layer
• Break messages into packets and reassemble
– Packet of size suitable for network layer
•
•
•
•
Multiplex sessions with same source/destination nodes
Re-sequence packets at destination
Recover from packet loss or failures
Provide end-to-end flow control
Weiqiang Sun
18
Other layers
• Presentation layer
– Provides character code conversion, data encryption, data
compression, etc.
• Session layer
– Obtains virtual end to end message service from transport layer
– Provides directory assistance, access rights, billing functions, etc.
• Standardization has not proceeded well here, since transport
to application are all in the operating system and don't really
need standard interfaces
Weiqiang Sun
19
The Internet model
FTP, HTTP, SMTP…
application
TCP/UDP protocol
transport
IP
protocol
IP
Data link and
lower layer
Ethernet
Ethernet
Weiqiang Sun
application
IP
protocol
IP
Ethernet
transport
Token
ring
IP
Data link and
lower layer
Token ring
20
Encapsulation
User data
“hi”
“hi”
TCP data
“hi”
application
transport
IP packet
“hi”
Ethernet Frame
“hi”
IP
Data link and
lower layer
Ethernet
Weiqiang Sun
21
The “Hi” example
Frame header / trailer
IP header
TCP header
Hi
Weiqiang Sun
22