Routing Algorithm & IP Protocol

Routing Algorithm

 

최소 비용 경로 찾는 알고리즘

 

 

 

Graph: G = (N, E)

• N = Routers (Nodes)
• E = Links (Edges)

 

 

 

cost : 링크 상 물리적 거리

 

 

 

 

 

1.  Global 라우팅 알고리즘 : 네트워크 전체에 대한 토폴로지 & 모든 link cost 알고 있어야 함

• Dijkstra’s algorithm

 

Dijkstra’s algorithm

 

 

`u `에서 시작

단계	N'	D(v),p(v)	D(w),p(w)	D(x),p(x)	D(y),p(y)	D(z),p(z)
0 (init)	u	2, u	5, u	1, u	∞	∞
1	ux	2, u	4, x		2, x	∞
2	uxy	2, u	3, y			4, y
3	uxyv		3, y			4, y
4	uxyvw					4, y
5	uxyvwz

 

 

Dijkstra’s algorithm 결과

 

 

 

 

 

2. Distributed 라우팅 알고리즘 : 이웃 노드 & link cost 정보만 알고 있어도 됨

• Bellman-Ford algorithm :  이웃노드와 반복적인 거리 벡터 교환과 거리 벡터 재계산

 

Bellman-Ford algorithm

 

 

 

 

3. 정적(static) 라우팅 알고리즘 : 경로의 변경이 느림

 

 

4. 동적(dynamic)라우팅 알고리즘 : 경로 변경 빠름. Link cost 변화 주기적으로 경신

 

 

 

 

 

---

IP Packet format

 

 

• Header Length : 헤더 크기(4 byte)를 word 단위로 나타냄. 헤더의 최소 크기는 20 byte
• Type of Service (ToS) : 서비스 유형 및 라이터와 라우팅 알고리즘

 

ToS

• Priority (0~7) : 우선순위 낮음 (000), 우선순위 높음 (111)
• Low Delay (D) : 보통의 지연 경로 (0), 낮은 지연 경로 (1)
• High Throughput (T) : 보통의 전송률 경로 (0), 높은 전송률 경로 (1)
• High Reliability (R) : 보통의 신뢰성 경로 (0), 높은 신뢰성 경로 (1)

 

• Total Packet Length : IP 패킷 전체 크기 (byte 단위) 
• Time to Live (TTL) : 망 혼잡을 막기 위해 TTL에 거쳐가는 최대 라우터 수 설정(TTL = 0, IP 패킷 폐기 & 송신측에 ICMP 전달)
• Protocol : 전송 계층의 potocol ID
      ICMP : 1, IGMP : 6, TCP : 6, UDP : 17
• Header Checksum : IP 헤더의 오류 검출
• Options : Error reporting, debugging, routing redirection  용도
• Padding : 32 bit (4byte) 워드 단위가 될 수 있도록 padding 필드에 해당 크기 만큼 0으로 채움

 

 

 

 

 

패킷 분할 및 병합 : 전송 계층의 데이터가 너무 크면 여러 개의 패킷을 분할 전송

 

MTU(maximum transmission unit)

• 최대패킷전송단위
• LAN에서 크고 WAN에서 작다

 

• Identification : 같은 데이터에서 분할된 패킷(fragment)끼리 같은 값
• Flags
          DF (Don’t fragment) bit : 패킷 분할 막기 (DFbit=1)
          MF (More fragment) bit : 마지막 패킷 (MFbit=0), 나머지 패킷 (MFbit=1)
• Fragment Offset : 각 분할된 패킷이 원래 데이터에서 차지하는 위치 (8 byte의 배수)

 

 

 

 

 

 

 

 

 

---

IP address format

 

IPV4 (32bit)

 

 

 

 

• net id : 네트워크 주소 (변경 불가)
• host id : 네트워크 내 host 주소 (네트워크 관리자가 부여)

 

참고 : Class D - 멀티캐스트, Class E - 실험/장래대비

 

 

 

Class	Address Range
A	1.0.0.1 ~ 126.255.255.254
B	128.1.0.1 ~ 191.255.255.254
C	192.0.1.1 ~ 223.255.254.254
D	224.0.0.0 ~ 239.255.255.255
E	240.0.0.0 ~ 254.255.255.254

 

 

 

 

 

 

Subnet addressing

 

ex. Class B

 

 

 

 

 

Subnet mask : net id & subnet id를 host id와 구분

• net id와 subnet id 부분: 1
• host id 부분: 0