Computer Network
정리가 잘 되지 않는다.
- Computer Network
- The OSI Model and the TCP/IP Protocol Suite
- Introduction to the Transport Layer
- Transmission Control Protocol(TCP)
- IPv4 Addresses
- Delivery and Forwarding of IP Packets
- Internet Protocol Version4(IPv4)
- Address Resolution Protocol(ARP)
- Internet Control Message Protocol Version 4(ICMPv4)
- Unicast Routing Protocols
- Continued…
The OSI Model and the TCP/IP Protocol Suite
Protocol Layers
Established in 1947, the International Standards Organization(ISO) is a multinational body dedicated to worldwide agreement on international standards. Almost three-fourths of countries in the world are represented in the ISO. An ISO standard that covers all aspects of network communications is the Open Systems Interconnection(OSI) model. It was first introduced in the late 1970s
- Physical
- To transmit bits over a medium; to provide mechanical and electrical specifications
- Data link
- To organize bits into frames; to provide hop-to-hop delivery
- Frame unit
- MAC 주소 확인 가능
- Network
- To move packets from source to destination; to provide internetworking
- Packet unit, Datagram unit
- Packet의 이동경로를 결정하는 계층
- IP
- Transport
- To provide reliable process-to-process message delivery and error recovery
- Error control, Flow control
- Segment unit
- TCP/UDP¡
Session
- To establish, manage, and terminate sessions
Presentation
- To translate, encrypt, and compress data
- JPEG, MPEG, SMB, etc.
- Application
- To allow access to network resource
- HTTP, FTP, DNS, SSH, etc.
TCP/IP Model
- Network Access Layer(네트워크 접속 계층)
- Data Link Layer + Physical Layer
- Internet Layer(인터넷 계층)
- IP(Internet Protocol)이라 함
- 경로설정, 패킷 스위칭
- Transport Layer(전송 계층)
- 신뢰도, 흐름제어, 에러제어를 위한 재전송 책임
- TCP/UDP
- Application Layer(응용 계층)
- 효율성 고려(응용+표현+세션 계층)
Today, TCP/IP model is more used than OSI 7 layers
Addressing
Four levels of addresses are used in an internet employing the TCP/IP protocols. Physical address, logical address, port address, and application specific address
Application-Specific Address - Application layer
Port Address - Transport layer
Logical Address - Network layer
Physical Address - Data link layer
Introduction to the Transport Layer
Transport-Layer Services
The transport layer is located between the network layer and the application layer. The transport layer is responsible for providing services to the application layer. It receives services from the network layer
- TCP
- TCP는 Flow Control(흐름제어)와 Congestion Control(혼잡제어) 두개의 제어 메커니즘을 이용하여 end-to-end 간의 신뢰성 있는 전송을 보장한다. 흐름 제어는 송신 측이 수신 측으로부터 Advertised window 크기를 받은 후 그것보다는 적게 보냄으로써 네트워크상의 흐름을 조절하는 방법이고, 혼잡 제어는 sender가 네트워크 상황을 보고 스스로 흐름을 조절하는 방법이다.
Transport-Layer Protocols
Flow Control
송신측과 수신측의 데이터 처리 속도 차이를 해결하기 위한 기법이다. 수신측이 송신측보다 속도가 빠른것은 아무 문제가 없다. 하지만 송신측이 수신측보다 속도가 빠르면 문제가 발생한다.
수신측에서 수신된 데이터를 처리해 상위 계층으로 서비스하는 속도보다 송신측에서 보내는 데이터의 속도가 더 빠르다면, 수신측에서는 제한된 저장용량을 초과하여 이후에 도착하는 데이터는 손실될 수 있다. 만약 데이터가 손실된다면 불필요하게 응답과 데이터의 재전송이 송신측과 수신측간에 빈번히 발생한다. 따라서 이러한 위험을 줄이기 위해 송신측의 데이터 전송량을 수신측의 window size에 따라 조절한다. 이러한 작업을 Flow Control이라 한다.
Host와 Host간의 데이터 처리를 효율적으로 하기 위한 기법
Flow Control 방법
- Stop-and-Wait
- Stop-and-Wait 방식은 송신측에서 수신측으로 데이터를 전송하고 제대로 수신했는지 확인 패킷을 기다렸다가, 확인이 되면 다음 데이터를 전송, 일정시간 동안 확인이 되지 않으면 error가 발생했다고 판단하여 재전송한다.
- Sliding Window
- TCP 슬라이딩 윈도우 기법은 수신측에서 설정한 윈도우 크기만큼 송신측에서 확인 응답 없이 세그먼트를 전송할 수 있게 하여 데이터 흐름을 동적으로 조절하는 제어 기법이다. 이처럼 슬라이딩 윈도우 기법을 통하여 송신 버퍼의 범위는 수신측의 여유 버퍼 공간을 반영하여 동적으로 바뀜으로써 흐름제어를 수행한다.
-
슬라이딩 윈도우는 일단 윈도우에 포함되는 모든 패킷을 전송하고, 그 패킷들의 전달이 확인되는대로 이 윈도우를 옆으로 옮김(sliding)으로써 그 다음 패킷들을 전송하는 방식이다.
-
또한 윈도우의 크기만큼은 수신쪽의 확인(응답)을 받지 않고도 보내는 것이 가능하므로 매번 전송한 패킷에 대해 확인을 받아야만 그 다음 패킷을 전송하는 방법(stop-and-wait)을 사용하는 것보다 훨씬 네트워크를 효율적으로 사용할 수 있다.
Congestion Control
혼잡제어는 송신측의 데이터 전달과 네트워크의 데이터 처리 속도 차이를 해결하기 위한 기법이다. 송신측의 데이터는 지역망이나 인터넷으로 연결된 대형 네트워크를 통해 전달된다. 하지만 이러한 네트워크 상의 라우터가 항상 한가로운 상황은 아니다. 만약, 라우터에 데이터가 몰릴 경우, 다시 말해 혼잡할 경우 라우터는 자신에게 온 데이터를 모두 처리할 수 없다. 그렇게되면 호스트들은 또다시 재전송을 하게 되고, 결국 더욱 더 혼잡만 가중시켜 오버플로우나 데이터 손실을 발생시킨다. 따라서, 이러한 네트워크의 혼잡을 피하기 위해 송신측에서 보내는 데이터의 전송속도를 강제로 줄이게 된다.
Host와 네트워크 상의 데이터처리를 효율적으로 하기 위한 기법
Go-Back-N
전송 효율을 높이기 위해서 송신자가 응답을 기다리는 동안 여러개의 프레임을 보내어 채널을 사용량을 높이는 기법이다
Selective-Repeat
Go-back-N 프로토콜은 수신자 쪽에서의 과정을 단순화한다. 오직 하나의 변수만 관리하며, 순서가 뒤바뀐 프렘들을 보관하는 버퍼가 없이 단순히 버려진다. 그러나 Go-Back-N 프로토콜은 혼잡한 채널에서는 매우 비효율적이다. 데이터 전송 시 손상될 경우 다수의 프레임을 재전송하게 되고, 이는 더욱 큰 혼잡을 발생하므로 속도가 저하된다. 이 때 N개의 프레임을 재전송하는 대신 손상된 프레임만 전송하는 방법이 Selective Repeat 프로토콜이다
Transmission Control Protocol(TCP)
TCP lies between the application layer and the network layer, and serves as the intermediary between the application programs and the network operations
Well-known Ports used by TCP
| Port | Protocol | Description |
|---|---|---|
| 7 | Echo | Echocs a received datagram back to the sender |
| 9 | Discard | Discards any datagram that is received |
| 11 | Users | Active users |
| 13 | Daytime | Returns the date and the time |
| 17 | Quote | Returns a quote of the day |
| 19 | Chargen | Returns a string of characters |
| 20 and 21 | FTP | File Transfer Protocol(Data and Control) |
| 23 | TELNET | Terminal Network |
| 25 | SMTP | Simple Mail Transfer Protocol |
| 53 | DNS | Domain Name Server |
| 67 | BOOTP | Bootstrap Protocol |
| 79 | Finger | Finger |
| 80 | HTTP | Hypertext Transfer Protocol |
TCP Connection
TCP is connection-oriented. It establishes a virtual path between the source and destination. All of the segments belonging to a message are then sent over this virtual path
TCP connection is virtual, not physical. TCP operates at a higher level. TCP uses the services of IP to deliver individual segments to the receiver, but it controls the connection itself. If a segment is lost or corrupted, it is retransmitted
Three-way handshake
Flow control
Flow control balances the rate a producer creates data with the rate a consumer can use the data.
Opening and Closing Windows
Silly Window Syndrome
데이터를 전송 시 목적지와 window 크기 등 정보를 전달하는 header 부분을 같이 보내게 되는데, 데이터가 header에 비해 너무 작아 전송 시 발생하는 관련된 것
송신측에서 발생하는 신드롬
- Nagle 알고리즘
송신측에서 데이터를 보낼 때 비효율이 발생하는 문제를 줄이기 위해, 처음보내는 데이터는 크기에 관계없이 전송하고 그에 대한 ACK를 받을때가지 데이터를 쌓아두는 방법. 꽉 차게 되면 ACK이 오기 전이라도 데이터를 보낸다.
수신측에서 발생하는 신드롬
Clark 해결법
ACK 전송 시 Buffer의 크기가 일정 이상으로 여우가 생길때까지 rwnd를 0으로 보낸다. 여유가 생기면 여유크기
로 rwnd를 보냄확인응답 지연
ACK 전송을 지연시켜 Window를 확보해나가고, 송신측에서는 데이터를 전송하지 않는다
SYN Flooding
TCP는 three-way handshake 방식으로 통신을 연결하는데, 이 방식의 취약점을 이용한 공격이 SYN Flooding 이다. server socket은 backlog에 연결 요청을 하는 client들을 대기시키는데, 악의적인 목적으로 다른 ip를 통해 접속하는 client들 같은 경우 서버가 SYN+ACK을 보내도 그 다음 응답을 받을 수 없게 된다. 그렇게 되면 server가 연결을 초기화 할 때까지 연결 요청 대기 큐에는 자리를 차지하고 있게되어 이러한 요청이 홍수처럼 많이 밀려들면 정작 필요한 client들이 server에 접속 할 수 없게되고, server가 마비된다.
Error Control
TCP is a reliable transport layer protocol. This means that an application program that delivers a stream of data to TCP relies on TCP to deliver the entire stream to the application program on the other end in order, without error, and without any part lost or duplicated.
Error control in TCP is achieved through the use of three tools, checksum, acknowledgment, and time-out
Chekcsum
데이터가 손상되었는지 확인하는 값Acknowledgment
- rule 1 : 응답과 데이터를 동시에 보내는 방식
- rule 2 : ACK를 받은 뒤 일정시간의 대기시간을 둔다. 대기시간 동안 전송할 데이터가 존재하는지 확인한다
- rule 3 : 데이터가 2번(ACK 2번) 들어오게 되면 무조건 ACK으로 답한다. 첫 ACK를 받은 뒤 rule 2 의 time 동안 또 다른 ACK이 들어오면 rule 2에 관계없이 ACK을 응답한다. 효율성을 위해
전송 중 데이터가 사라졌을 때 신뢰성을 확보하기 위해 사용되는 rule들 - rule 4 : client가 timer를 설정하여 2개의 데이터를 보냈을 때 첫번째 데이터가 손실된다면, server 측에서 잃어버린 데이터의 재전송을 요구하는 ACK를 전송한다
- rule 5 : rule 4 에서 재전송을 요구하는 ACK 보냈을 때 client의 timer가 바로 종료되는 것이 아닌 timer가 종료된 후 전송한다
- rule 6 : rule 2, 3 에 의해 데이터를 전송 할 때 데이터가 아닌 ACK가 손실 될 경우 데이터를 재전송하고, server 측에선 데이터를 받자마자 기다리지 않고 ACK을 전송한다
Congestion Control
Congestion control in TCP is based on both open loop and closed-loop mechanisms. TCP uses a congestion window and a congestion policy that avoid congestion and detect and alleviate congestion after it has occurred.
Slow Start
최초 cwnd 값을 1에서 부터 시작한다. 그리고 데이터를 전송하고 ACK을 받을때마다 exponential하게 증가하여 데이터 전송량을 미리 정해둔 임의의 threshold 값에 도달할때까지 증가하게 한다.
- 정상적으로 계속해서 데이터 전송이 이루어져 cwnd가 threshold와 같아지게 되면 Congestion Avoidance 방법으로 넘어간다
- 중간에 Packet Lost가 발생하여 3 duplicate ACKs가 발생하여 threshold를 마지막 전송시의 window의 절반으로 설정하고 그 크기를 cwnd로 하여 Congestion Avoidance 방법으로 넘어간다
- 데이터 전송이 제대로 이루어지지 않아 ACK을 받지 못하고, Time-Out이 발생하게되어 네트워크가 혼잡하다고 가정하고 threshold는 마지막 window의 절반으로, cwnd는 1MSS(Maximum Segment Size)로 설정한다
Congestion Avoidance
한번의 ACK을 받을때마다 cwnd 값을 1씩 증가시키는 방법이다.
- 정상적으로 모든 데이터 전송을 마치고 연결을 종료한다
- 중간에 Packet Lost가 발생하여 3 duplicate ACKs를 통해 네트워크 혼잡을 감지하고 threshold와 cwnd를 마지막 window의 절반으로 설정한다. 그 후 다시 Congestion Avoidance 방법으로 진행한다
- ACK를 받지 못하고 Time-Out 발생 시 네트워크가 혼잡하다고 판단하여, Threshold를 마지막 window의 절반으로 cwnd를 1로 설정하고 Slow Start 방법으로 되돌아간다다
Continued…
IPv4 Addresses
The identifier used in the IP layer of the TCP/IP protocol suite to identify each device connected to the Internet is called the Internet address or IP address. An IPv4 address is a 32-bit address that uniquely and universally defines the connection of a host or a router to the Internet; an IP address is the address of the interface.
Classful Addressing
IP addresses, when started a few decades ago, used the concept of classes. This architecture is called classful addressing. In the mid-1990s, a new architecture, called classeless addressing, was introduced that supersedes the original architecture.
The network address is the identifier of a network
Classless Addressing
Subnetting and supernetting in classful addressing did not really solve the address depletion problem. With the growth of the Internet, it was clear that a larger address space was needed as a long-term solution.
Although the long-range solution has already been devised and is called IPv6, a short-term solution was also devised to use the same address space but to change the distribution of addresses to provide a fair share to each organization.
The short-term solution still uses IPv4 addresses, but it is called classless addressing.
In classless addressing, the prefix defines the network and the suffix defines the host
Prefix length for classful addressing
| Class | Prefix length |
|---|---|
| A | /8 |
| B | /16 |
| C | /24 |
| D | /4 |
| E | /4 |
Special Addresses
In classful addressing some addresses were reserved for special purposes. The classless addressing scheme inherits some of these special addresses from classful addressing.
- 0.0.0.0
- 255.255.255.255
- 127.0.0.1
- etc.
NAT
The distribution of addresses through ISPs has created a new problem. If the business grows or the household needs a larger range, the ISP may not be able to grant the demand because the addresses before and after the range may have already been allocated to other networks.
In most situations, however, only a portion of computers in a small network need access to the Internet Simultaneously. A technology that can help in this cases is network address translation(NAT).
공유기와 같은 것들
- 192.168.0.0
- 172.16.0.0
- 10.0.0.1
- etc.
Delivery and Forwarding of IP Packets
Delivery
The network layer supervises the handling of the packets by the underlying physical networks. We defines this handling as the deliver of a packet. The delivery of a packet to its final destination is accomplished using two different methods of delivery; direct and indirect
Direct
Indirect
Forwarding
Forwarding means to place the packet in its route to its destination. Since the Internet today is made of a combination of links(networks), forwarding means to deliver the packet to the next hop(which can be the final destination or the intermediate connecting device).
Although the IP protocol was originally designed as connectionless protocol, today the tendency is to use IP as a connection-oriented protocol.
Internet Protocol Version4(IPv4)
The Internet Protocol(IP) is the transmission mechanism used by the TCP/IP protocols at the network layer
Datagrams
Packets in the network layer are called datagrams. A datagram is a variable-length packet consisting of two parts(header and data).
The header is 20 to 60 bytes in length and contains information essential to routing and delivery. It is customary in TCP/IP to show the header in 4-bytes sections.
![IP datagram]](http://i.imgur.com/s3YB4hP.png)
Protocols
| Value | Protocol | Value | Protocol |
|---|---|---|---|
| 1 | ICMP | 17 | UDP |
| 2 | IGMP | 89 | OSPF |
| 6 | TCP |
Fragmentation
A datagram can travel through different networks. Each router decapsulates the IP datagrams from the frame it receives, processes it, and then encapsulates it in another frame.
The format and size of the received frame depend on the protocol used by the physical network through which the frame has just traveled. The format and size of the sent frame depend on the protocol used by the physical network through which the frame is going to travel.
Checksum
The error detection method used by most TCP/IP protocols is called the checksum. The checksum protects against the corruption that may occur during the transmission of a packet.
The checksum is calculated at the sender and the value obtained is sent with the packet. The receiver repeats the same calculation on the whole packet including the checksum. If the result is satisfactory the packet is accepted. Otherwise, it is rejected
Checksum in IP covers only the header, not the data
Address Resolution Protocol(ARP)
Address Mapping
The deliver of a packet to a host or a router requires two levels of addressing(logical and physical). Address mapping need to be able to map a logical address to its corresponding physical address and vice versa. These can be done using either static and dynamic mapping
Anytime a host or a router has an IP datagram to send to another host or router, it has the logical(IP) address of the receiver. But IP datagram must be encapsulated in a frame to be able to pass through the physical network. This means that the sender needs the physical address of the receiver.
A mapping corresponds a logical address to a physical address. ARP accepts a logical address from the IP protocol, maps the address to the corresponding physical address and pass it to the data link layer
APR Packet
An ARP request is broadcast, an ARP reply is unicast
Internet Control Message Protocol Version 4(ICMPv4)
The IP protocol has no error reporting or error correcting mechanism.
Network layer
Messages
ICMP messages are divided into two broad categories(error reporting messages and query messages). The error reporting messages report problems that a router or a host(destination) may encounter when it processes an IP packet. The query messages, which occur in pairs, help a host or a network manager get specific information from a router or another host.
Also, hosts can discover and learn about routers on their network and routers can help a node redirect its messages.
ICMP always reports error messages to the original source
There is no flow-control or congestion control mechanism in the IP protocol
Unicast Routing Protocols
Distance Vector Routing
Bellman-Ford Algorithm
벨만-포드 알고리즘은 가중 유향 그래프에서 최단 경로 문제를 푸는 알고리즘이다. 이 때 간선의 가중치는 음수일 수 있다.
- 시작 정점
의 최단 거리만 0으로 설정하고, 나머지 정점이 갖는 값을 모두 무한대 값으로 초기화 모든 간선을 한번씩 살피면서 해당 간선으로 인해 앞에서 설정한 최단 거리가 더 짧아질 수 있는지 확인
- 처음은 에서 나갈 수 있는 모든 간선들을 확인하여 가장 적은 값으로 갈 수 있는 정점을 선택
- 이 후 한개의 간선에 대해서 확장되어지는 그 위치에서 또 나갈 수 있는 모든 간선에 대해 값을 계산
- 이를 반복
- 이 때 이미 정점이 다른 간선이 지나가면서 값이 설정되어 있을 경우 막 들어온 간선의 최종 값과 비교하여 작은 값을 저장
- 처음은
Dijkstra Algorithm
다익스트라 알고리즘은 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다.
다익스트라 알고리즘은 각각의 정점 
에 대해 
에서 까지의 최단 거리 
를 저장하면서 작동한다.
이고, 가 아닌 다른 모든 정점 에 대해서는 
로 놓아 다른 정점에 대해서는 아직 최단 경로가 모른다는 사실을 표시- 에서
까지의 최단 경로 
를 이미 알고 있고, 에서 까지 길이가 
인 변 
가 존재할 때, 에서 까지의 최단 경로는 까지의 최단 경로에 변 를 추가함으로써 얻을 수 있다. 이 경로의 비용은 
가 되며, 이 비용이 현재의 d[v] 값보다 낮으면 d[v]를 새로운 값으로 바꾼다.
Continued…
'Class' 카테고리의 다른 글
| [cs224n] Lecture 4 Word Window Classification and Neural Networks (0) | 2018.03.25 |
|---|---|
| [cs224n] Lecture 1 Natural Language Processing with Deep Learning (0) | 2018.03.10 |
| Algorithm 정리 (0) | 2015.05.08 |
| OS(Operating System) 정리 (2) | 2015.04.29 |
| Data Structure, 자료구조 정리 (0) | 2015.04.18 |