ƯƠ

NG 7

Ạ

CH Ể Ạ M NG CHUY N M CH GÓI (Packet Switching Network)

ả

 Gi ng viên: Tr nh Huy Hoàng ị     Email:hoangth@hcmup.edu.vn

ộ

N i dung

ụ

Ứ

ể

ạ

 ng d ng  Công ngh  chuy n m ch gói ệ  Tìm đ ngườ  X.25

2

CSE 501035 – Data Communication

ể

ạ

Chuy n m ch gói

ể

ượ

ế ế ể

ề

c thi

ạ t k  đ  truy n tho i

ạ ượ

 Chuy n m ch m ch đ ạ  Các tài nguyên đ

ộ ọ c dành riêng cho cu c g i

ờ ầ ế ế ố ữ ệ ả

 H u h t th i gian là k t n i d  li u r nh  T c đ  d  li u c  đ nh ố ộ ữ ệ ố ị  Thi ả

ạ

Ứ

(cid:0) ầ ể

ụ ứ

 Các  ng d ng d  li u ữ ệ ụ

 Public Data Network (PDN) / Value­added Network (VAN)  Private Packet­Switched Network

ố ộ ế ị ả t b  c  2 đ u ph i ch y cùng t c đ   ạ ệ  Công ngh  chuy n m ch gói  ng d ng

 Các  ng d ng ti ng nói ụ  Packetized Voice Network

3

CSE 501035 – Data Communication

ứ ế

ỏ

ỗ ỏ c chia thành m t chu i các gói nh

ạ c truy n theo gói nh ng là 1000 octet / gói ệ ớ ộ

ơ ượ ầ ữ ệ ủ ườ ề

ể Chuy n m ch gói – Nguyên lý  D  li u đ ữ ệ ượ ề  Thông th ườ  Các thông đi p l n h n đ  M i gói ch a m t ph n d  li u c a ng ứ

ộ i dùng và các thông tin đi u

ề

ỗ khi nể

 Ch a thông tin cho vi c tìm đ

 Thông tin đi u khi n ể ệ ư ạ

ượ

ậ

ệ

ể

ứ ườ

ỉ ị ng (đ a ch ) ế ờ c nh n, l u t m th i (đ m) và chuy n cho node k

 Các gói đ ti p ế  L u và chuy n (store and forward) ư

4

CSE 501035 – Data Communication

ể

Ư ể

ể

ạ

Chuy n m ch gói –  u đi m

ệ

ườ

ề

 Hi u qu  s  d ng đ

ả ử ụ ế ơ

ng truy n ể

ề

 Liên k t đ n node­node có th  dùng chung b i nhi u gói  Các gói đ ể ỗ ạ

ề ở ấ ể c x p hàng và truy n đi nhanh nh t có th

ụ ộ ớ ố ộ ủ

ượ

ạ

ế ầ ế ể

 Các gói đ

ằ ố ộ t đ  cân b ng t c đ ậ c ch p nh n ngay khi m ng đang b n

ậ  Vi c phát có th  ch m l ạ

ệ i

ộ ư

 Thông báo có th  có các đ   u tiên khác nhau

5

CSE 501035 – Data Communication

ượ ế  Chuy n đ i t c đ  d  li u ổ ố ộ ữ ệ  M i tr m k t n i v i node c c b  v i t c đ  c a nó ế ố ớ  Các node đ m d  li u n u c n thi ữ ệ ệ ấ ể ậ ể

ể

ạ

ỹ

ậ Chuy n m ch gói – K  thu t

ỏ

ề ạ

t vào m ng

 Tr m chia thông báo dài thành nhi u gói nh ạ  Các gói đ  Các gói đ

ượ ở ầ ượ c g i l n l ượ ử c x  lý theo 2 cách

 Datagram  Virtual circuit

6

CSE 501035 – Data Communication

ể

ạ

ỹ

ậ Chuy n m ch gói – K  thu t

 Datagram

ấ ứ ườ

ợ ng thích h p nào ứ ự ở  g i

ụ ủ

ệ

ấ ậ ự

 M i gói đ ộ ậ ượ ử ỗ c x  lý đ c l p  Các gói có th  đi theo b t c  đ ể  Các gói có th  đ n đích không theo th  t ể ế  Các gói có th  th t l c trên đ ườ ể ấ ạ ng đi  Nhi m v  c a bên nh n là s p x p l ế ạ ắ

i các gói m t tr t t

và

ụ

ậ ấ ạ khôi ph c các gói th t l c

7

CSE 501035 – Data Communication

ể

ạ

Chuy n m ch gói ­ Datagram

8

CSE 501035 – Data Communication

ể

ạ

Chuy n m ch gói ­ Datagram

9

CSE 501035 – Data Communication

ạ

ỹ

ậ ể Chuy n m ch gói – K  thu t  Virtual circuit ị ườ

 Đ ng đi đ nh s n đã đ

ượ ạ ướ ẵ ở c t o tr c khi g i các gói đi

 Các gói yêu c u cu c g i và ch p nh n cu c g i đ

ộ ọ ượ ộ ọ ấ ậ ể ạ ế c dùng đ  t o k t

ố ầ n i (handshake)

 M i gói ch a thông tin v  đ ứ

ề ườ ỗ ả ị ỉ ng đi “ o” thay vì thông tin đ a ch  đích

 Không c n quy t đ nh tìm đ

ế ị ầ ườ ng cho các gói

 Yêu c u xóa đ  h y k t n i  ể ủ ế ố

ầ

 Không ph i là m t đ

ộ ườ ả ng dành riêng

 M i đ VCI)

10

CSE 501035 – Data Communication

ỗ ườ ả ượ ộ ố ng  o đ c gán m t mã s  riêng (Virtual Circuit Identifier –

ể

ạ

Chuy n m ch gói – Virtual Circuit

11

CSE 501035 – Data Communication

ể

ạ

Chuy n m ch gói – Virtual Circuit

12

CSE 501035 – Data Communication

ấ ự ầ ự

ể ỗ

ề

và đi u khi n l

i

Virtual Circuit vs. Datagram  Virtual circuit  M ng có th  cung c p s  tu n t ể ạ  Các gói đ ơ ượ c chuy n nhanh h n ườ ầ

ể ế ị

 Không c n các quy t đ nh tìm đ ộ

ấ ả

ẽ

ấ

ộ

ỏ

ế ố

 Đ  tin c y kém h n ơ ậ  Vi c m t m t node s  làm h ng t ệ

t c  các k t n i đi qua node đó

 Datagram

ạ

ế ậ

ế ố t l p k t n i

ng

 Không c n giai đo n thi ầ  T t h n n u s  gói nh ố ơ ế ố ỏ  Linh đ ng h n ơ ộ  Đ ng đi đ ượ ườ

ế ị ẽ ạ ầ c quy t đ nh sao cho tránh các ph n m ng đang ngh n

13

CSE 501035 – Data Communication

k tẹ

ướ

Kích th

c gói

14

CSE 501035 – Data Communication

Circuit vs. Packet Switching

 Hi u su t ấ ệ  tProp  tTrans  tNode

15

CSE 501035 – Data Communication

Circuit vs. Packet Switching

Circuit Switching

Datagram Packets

Virtual Circuit Packets

ườ

ề

ẫ

ườ

ề

ẫ

ườ

ề

ẫ

Đ ng truy n d n dành riêng

Đ ng truy n d n không dành riêng

Đ ng truy n d n không dành riêng

ữ ệ

ề

ữ ệ

ề

ữ ệ

ề

ụ D  li u truy n liên t c

D  li u truy n theo gói

D  li u truy n theo gói

ủ

ứ

ụ

ươ

ủ

ứ

ụ

ươ

ủ

ứ

ụ

ươ

Đ  nhanh cho  ng d ng t

ng tác

Đ  nhanh cho  ng d ng t

ng tác

Đ  nhanh cho  ng d ng t

ng tác

ượ ư

ữ

ể ượ ư

ữ

ượ ư

ữ

ế

Thông báo không đ

c l u tr

c l u tr  cho

c l u tr  cho đ n khi

ế

ế

Thông báo có th  đ ế đ n khi đ n phân phát

Thông báo đ đ n phân phát

ườ

ượ

ề

ẫ

ườ

ượ

ế ậ

ỗ

ượ

t l p

c thi

t l p cho m i

t l p cho toàn

ườ ộ

ế ậ c thi Đ ng truy n d n đ ổ ộ cho toàn b  quá trình trao đ i

Đ ng đi đ gói

ế ậ c thi Đ ng đi đ ổ b  quá trình trao đ i

ế ậ

ư

ễ

ễ

ế ậ

ề Tr  truy n các gói

ễ t l p, tr

ễ ờ

t l p, nh ng  ề

ễ

ề

Tr  do quá trình thi truy n các gói

Tr  do quá trình thi th i gian tr  trong quá trình truy n  không đáng kể

ệ

ế

ậ

ậ

ườ ở

ế

ể ượ ượ

Tín hi u b n n u bên nh n không  ẵ s n sàng

Ng i g i có th  đ ế n u các gói không đ

c thông báo  c phân phát

ườ ở ượ Ng i g i đ ượ gói không đ

c thông báo n u các  c phân phát

16

CSE 501035 – Data Communication

Circuit vs. Packet Switching (tt)

Circuit Switching

Datagram Packets

Virtual Circuit Packets

ả ẽ

ễ ủ

ờ

ả

ể

i s  khóa vi c thi

i s  tăng th i gian tr  c a

i có th  khóa vi c thi

ườ

ệ ễ ủ

ờ

ệ ế ậ t l p;  ề ng truy n đã

Quá t gói

ế Quá t t  ậ l p; tăng th i gian tr  c a gói

ượ

ả ẽ Quá t ễ không tr  khi đ ế ậ t l p c thi đ

ể

ơ ệ

ặ ượ

ạ

ỏ

ạ

ỏ

c

ể Node chuy n m ch nh

ể Node chuy n m ch nh

ề

ể

ở

ạ Chuy n m ch c  đi n ho c đ đi u khi n b i máy tính

ị

ạ

ệ

ạ

ể ẽ ị

ệ

ệ User ch u trách nhi m khi các  ị ấ ạ thông báo b  th t l c

ể ẽ ị M ng có th  s  ch u trách nhi m  cho các gói đ n lơ ẻ

M ng có th  s  ch u trách nhi m  ỗ cho chu i các gói

ể

ổ

ể

ả

ể

ả

ng không c n chuy n đ i

ổ ố ộ Chuy n đ i t c đ  và b ng mã

ổ ố ộ Chuy n đ i t c đ  và b ng mã

ả

ầ ườ Th ố ộ t c đ  và b ng mã

ố ị

ề

ẫ

ử ụ

ộ

ộ

Truy n d n băng thông c  đ nh

Linh đ ng s  d ng băng thông

ử ụ Linh đ ng s  d ng băng thông

ữ ệ

ữ ệ

ố

ỗ

ữ ệ

ố

ỗ

T n kém d  li u cho m i gói

T n kém d  li u cho m i gói

Không t n chi phí d  li u sau khi  thi

ố ế ậ t l p

17

CSE 501035 – Data Communication

ạ ộ

ể

ạ

ạ

ữ

Ho t đ ng bên ngoài – bên trong  Chuy n m ch gói ­ datagrams ho c virtual circuits ặ  Giao ti p gi a tr m và node m ng ạ

 K t n i (Connection oriented) ầ

ậ

ế ố ượ ộ ề ế ố ấ ượ c đánh d u thu c v  k t n i đó và đ ố c đánh s

ứ ự

ụ ạ ả

ạ ả ạ ộ

ế ế ố  Tr m yêu c u k t n i lu n lý (virtual circuit) ạ  T t c  các gói đ ấ ả  ứ ự th  t  M ng phân phát các gói theo th  t ạ  D ch v  m ch  o bên ngoài  ị  e.g. X.25  Khác so v i ho t đ ng m ch  o bên trong

ớ ế ố

ị

 Không k t n i (Connectionless)  Các gói đ ộ ậ ượ ử c x  lý đ c l p  D ch v  datagram bên ngoài ụ  Khác so v i ho t đ ng datagram bên trong

18

CSE 501035 – Data Communication

ạ ộ ớ

ổ ợ

ệ

T  h p các công ngh

Dòc h vuïbe ân ng oaøi Dòc h vuïbe ân ng oaøi

ÖÙng duïng ÖÙng duïng

V.C. V.C.

Datagram Datagram

V.C V.C

Not used Not used

IBM SNA IBM SNA TYMNET TYMNET

ườ

ạ

 External virtual circuit,  internal virtual circuit  Đ ng dành riêng thông qua m ng

Datagram Datagram

Dòc h Dòc h vuï vuï be ân be ân tro ng tro ng

ARPANET ARPANET (packet) (packet)

X.25 X.25 ARPANET ARPANET (packet, message) (packet, message)

 External virtual circuit, internal datagram ỗ

ử

ệ

ạ

ạ ả

ể

ườ

 M ng x  lý m i gói riêng bi t   Các gói khác nhau cho cùng m t m ch  o bên ngoài có th  đi các đ ộ

ng bên trong

khác nhau ư

ạ

ữ

ạ

ể ắ

ế ạ

ứ ự

 M ng l u tr  các gói t

i node đích đ  s p x p l

i th  t

 External datagram, internal datagram

ượ ố ử ộ

ở ả ạ

 Các gói đ

ộ ậ c đ i x  m t cách đ c l p b i c  m ng và user

ấ

ở ừ

ộ

ế ậ

ậ ư

ợ

 External datagram, internal virtual circuit  Ng ế ố ườ i dùng ngoài không th y các k t n i  Ng ườ i dùng ngoài g i t ng gói m t   M ng thi ế ố ạ t l p k t n i lu n lý  T i sao ph i t n chi phí nh ng không có l ả ố ạ

i gì ?

19

CSE 501035 – Data Communication

External Virtual Circuit and Datagram Operation

20

CSE 501035 – Data Communication

Internal Virtual Circuit and Datagram Operation

21

CSE 501035 – Data Communication

ngườ ề ứ ạ

ố ớ

ể

ạ

Tìm đ  V n đ  ph c t p, quy t đ nh đ i v i m ng chuy n  ấ ế ị ạ

m ch gói

 Các đ c tính yêu c u ầ

ặ  Chính xác  Đ n gi n ả ơ  M nh mạ ẽ  n đ nh Ổ ị  Công b ngằ  T i  uố ư  Hi u qu ả ệ ẩ

ả

ể ọ ườ

ể i thi u

 Tiêu chu n đo tính hi u qu ệ  Đ c dùng đ  ch n đ ượ ng  S  ch ng đ ố ườ ố ặ ng (hop) là t  Chi phí (cost) t ể ố i thi u

22

CSE 501035 – Data Communication

ườ

Chi phí các đ

ng đi

23

CSE 501035 – Data Communication

ế ố

ế ị

ậ

ườ

Y u t

ế  quy t đ nh chi n thu t tìm đ

ng

ặ

ờ ể ế ị

 N i quy t đ nh

 Th i đi m quy t đ nh  Trên c  s  m ch  o ho c gói ơ ở ạ ả ơ  Phân tán (Distributed) ệ ạ

ượ

ự

i các node

ồ

ở

 Đ c th c hi n t  T p trung (Centralized) ậ  T i ngu n g i (Source) ạ ồ

ế ị

ậ ậ ờ

ượ ự

 Ngu n thông tin m ng và th i đi m c p nh t thông tin ng thông th

ả ng (không ph i luôn luôn) đ

c d a trên các

ể ườ

thông tin v  m ng

ườ

 Tìm đ

ng phân tán (Distributed routing)

ử ụ

ậ ậ

ừ ừ

ườ

ề

ụ ộ ế ậ  các node k  c n  các node trên đ

 Node s  d ng các thông tin c c b  Có th  thu th p thông tin t  Có th  thu th p thông tin t

ng ti m năng

ậ

ườ

 Tìm đ

ừ ấ ả

ể ể ng t p trung (Central routing) ậ t c  các node  t

 C p nh t thông tin ậ

ị

ữ ạ

ượ ậ

i các node đ

ậ c c p nh t

ượ ư c l u tr  t ậ c c p nh t

ố ị ộ

ậ

ậ

 Thu th p thông tin t ậ  Xác đ nh khi nào các thông tin m ng đ  C  đ nh (Fixed) – không bao gi  Đ ng (Adaptive) – c p nh t th

ạ ờ ượ ậ  đ ườ ng xuyên

24

CSE 501035 – Data Communication

ạ  Quy t đ nh tìm đ ườ ế ị ề ạ

ế

ậ

ườ

Chi n thu t tìm đ

ng

ế

ậ

 Chi n thu t (Routing Strategies)

 Fixed routing  Flooding routing  Random routing  Adaptive routing

25

CSE 501035 – Data Communication

trình c  đ nh cho m i

ộ ộ ườ ố ị ồ ừ ế

Fixed Routing  M t l đ

ỗ  ngu n đ n đích ng đi t

ạ

tr

 T t c  các đ ấ ả ườ ng đi qua m ng  ượ ề ế ậ ừ ướ c  t l p t c thi đ u đã đ ế ậ ậ và không c p nh t theo các bi n  ổ ề đ i v  các đi u ki n t trong m ngạ

ệ ả ề i, …

 Đ ng đi đ ườ ả

ượ

ậ ố gi i thu t chi phí t ị c xác đ nh dùng  ể i thi u

ố ị

 Đ ng c  đ nh ít ra cho đ n khi  ổ ấ có s  thay đ i c u hình m ng

26

CSE 501035 – Data Communication

ườ ự ế ạ

Flooding Routing

ạ

ạ ớ ỗ ậ ượ ẽ ượ c s  đ

ề ề i m i node k  (láng gi ng)  ế ố ấ ả ề t c  các k t n i ngo i  c truy n trên t

ẽ ế

ủ

ộ ố ố

ấ

 Không c n thông tin m ng  ầ  Node g i các gói t ở  Các gói nh n đ ừ ế ố ế tr  k t n i đ n ẽ ẽ ượ c đánh s  duy nh t sao cho các copy trùng nhau s

 Cu i cùng s  có m t s  copy c a gói s  đ n đích  ố  M i gói đ ỗ ị ạ ỏ b  lo i b

ể

ạ

ớ

 Node có th  ghi nh  các gói đã đi qua, giúp cho m ng không quá

ả

ề

t

i nhi u

ể ứ ố ặ

ườ

ượ

 Có th  ch a s  ch ng đ

ng (hop) trong các gói, đ

ể c dùng đ

ớ ạ

ề

ế

gi

i h n hay k t thúc quá trình truy n

27

CSE 501035 – Data Communication

Flooding Routing

 Đ c đi m

ộ

ề

trình đ u

ể ặ  T t c  các l ấ ả ử ượ c th đ  Robust   Lãng phí băng thông  Ít nh t s  có m t gói đi  ộ ớ ố ặ  trình v i s  ch ng

ấ ẽ ộ theo l ít nh t ấ

ế ể ể ượ t c dùng đ  thi

ề ượ

 T t c  các node đ u đ

c

t

 Có th  đ ậ ườ l p đ ấ ả i ớ  Dùng đ  phân tán thông tin

ạ ả ng m ch  o

28

CSE 501035 – Data Communication

ể ườ (tìm đ ng)

Random Routing

ộ ườ

ề

ế

ể

ậ

 Node s  ch n m t đ ẽ ọ

ng liên k t ra đ  truy n đi các gói nh n

đ

ọ ự

ể

ặ

 Vi c ch n l a có th  là ng u nhiên ho c xoay vòng (round  ẫ

c ượ ệ robin)

ể ọ ườ

ự

ế

ệ

ấ

 Có th  ch n đ

ng liên k t ra d a trên vi c tính toán xác su t

(cid:0)

P i

(cid:0)

R i R

j

j

ầ

ạ

ượ

ả

ườ

ng không ph i là đ

ng có chi phí

 Không c n thông tin m ng  L  trình tìm đ c thông th ể

ặ ố ặ

ườ ỏ

ấ

ộ ố i thi u ho c s  ch ng nh  nh t

t

29

CSE 501035 – Data Communication

ạ

ạ

ở ầ ườ

ệ

ạ

ổ

Adaptive Routing  Đ c s  d ng b i h u h t các m ng chuy n m ch gói  ượ ử ụ ế  Quy t đ nh tìm đ ế ị

ể ề ng thay đ i khi các đi u ki n trên m ng thay

ề ạ

ộ ấ ượ

ữ

ạ

ng c a thông tin m ng và chi phí

ộ

ả ứ ậ

ế

ẫ

đ iổ  H ng (Failure)  Ngh n (Congestion) ẽ  C n bi ế ầ t các thông tin v  m ng   Quy t đ nh là m t hàm ph c t p ứ ạ ế ị  Tradeoff gi a ch t l ủ  Ph n  ng quá nhanh có kh  năng gây dao đ ng  ả  Quá ch m d n đ n không còn thích h p ợ

30

CSE 501035 – Data Communication

ỏ

Adaptive Routing

ệ

c c i thi n ẽ

ạ

 u đi m Ư ể  Hi u su t đ ệ ấ ượ ả  Tr  giúp đi u khi n ngh n m ng  ề ợ ể  Chi ti ế ế ờ t n u có th i gian  H  th ng ph c h p ứ ợ ệ ố  Có kh  năng không th c hi n các ích l ả

 Phân lo iạ

 D a trên các ngu n thông tin

ự ệ ợ ề ặ ế i v  m t lý thuy t

ụ ộ

ồ ự  C c b  (isolated)  Các node k  (distributed) ề  T t c  các node (centralized)

31

CSE 501035 – Data Communication

ấ ả

ự ậ ỗ ườ ủ ự

Isolated Adaptive Routing  M i node trong m ng t ậ ả ạ  c p nh t b ng tìm đ ọ ỏ ượ

ề ạ ổ ng c a mình d a vào các  c, không trao đ i thông tin routing

thông tin v  m ng mà node đó h c h i đ v i các node khác

ớ ở ợ

ể ộ ư

ấ ủ ữ ơ ườ ộ ợ ng đ ng, phù h p

ả ng pháp đ n gi n nh t c a tìm đ ạ ộ ướ ỏ c nh  và ho t đ ng

 G i các gói trên các liên k t ra có hàng đ i ng n nh t  ấ ắ ế  Có th  thêm các đ   u tiên (bias) cho các đích   M t trong nh ng ph ộ ươ ạ ớ v i các m ng có kích th ố ổ ươ ng đ i  n đ nh t

 Ít dùng (không dùng thông tin có s n)ẵ

32

CSE 501035 – Data Communication

ị

Adaptive Routing  Distributed Adaptive Routing

 Trong ph ạ

ươ ạ ộ ủ ề ệ

ạ ổ ậ c phân b  v  l

ạ ng pháp này, thông tin v  tình tr ng ho t đ ng hi n hành c a  ữ ạ c đ nh k  trao đ i, c p nh t gi a các node trong toàn m ng.  i các node trong m ng hay  ậ ườ ụ ệ ể ng đ  các node này c p

 Ph

ứ ủ ạ ng pháp này đáp  ng đ

 Centralized Adaptive Routing ươ

ậ ẽ ượ ị ỳ m ng s  đ ẽ ượ ố ề ạ Sau đó thông tin này s  đ ạ ộ ố m t s  node trong m ng làm nhi m v  tìm đ ậ ạ ả nh t l i b ng routing ươ ư ờ ồ ạ ượ ớ nh ng đ ng th i cũng làm tăng l u l ổ ạ ữ c v i nh ng thay đ i tr ng thái c a m ng,  ư ượ ng thông tin trong m ng

 Trong ph ạ

ạ ộ ủ ề ệ

ạ ậ

ỳ ẽ ượ ậ ủ ạ ạ ng pháp này, thông tin v  tình tr ng ho t đ ng hi n hành c a  ữ ổ ậ c đ nh k  trao đ i, c p nh t gi a các node trong toàn m ng.  ề ộ c t p trung v  m t máy ch  trong m ng làm

ệ

 Tuy đáp  ng đ

ẽ ượ ị m ng s  đ Sau đó thông tin này s  đ ụ nhi m v  routing ứ ượ ớ ổ ứ ư ạ ờ

ươ c v i nh ng thay đ i t c th i trong m ng nh ng  ạ ể ậ ng pháp này có nh ữ ượ c đi m là thông tin routing trong toàn m ng t p

ạ ộ ạ

33

CSE 501035 – Data Communication

ạ ộ ượ ph ẽ ề ộ trung v  m t máy nên khi máy này không ho t đ ng thì toàn m ng s   không ho t đ ng đ c

ườ

ậ i thu t tìm đ

ấ ắ ng ng n nh t

ả Gi  Bài toán

 Cho m ng các node đ

ượ ố ở ế ề ề ỗ c n i b i các liên k t 2 chi u, m i chi u có giá

ị ạ tr  chi phí riêng

 Chi phí c a đ

ủ ườ ữ ạ ổ ị ng đi gi a 2 node trong m ng là t ng các giá tr  chi phí

 Xác đ nh đ

ấ ắ ng ng n nh t ng đi ế

 Tiêu chu n đ ẩ ườ  S  ch ng đ ố ặ ườ  Giá tr  m i liên k t là 1 ị ỗ  Giá tr  liên k t ế ị  T  l ị ỉ ệ ế ố ộ  ngh ch t c đ  liên k t  T  l ế ậ ả ỉ ệ i trên liên k t  thu n t  T  h p các đ i l ạ ượ ổ ợ ng trên

ả

 Gi

ậ i thu t

 Forward­search (Dijkstra)  Backward­search (Bellman­Ford)

34

CSE 501035 – Data Communication

ủ c a các liên k t đi qua ắ ườ ữ ấ ấ ấ ị ế ng đi ng n nh t (chi phí th p nh t) gi a 2 node

ậ

ả

i thu t Dijkstra

Gi  Input

 Đ  th  G(V, E) trong đó V là t p đ nh, E là t p c nh có tr ng s  không  ỉ

ậ ạ ồ ị ậ ố ọ

âm

ồ

ỉ

 Đ nh ngu n S:  S

V

(cid:0)

 Output ườ

 Đ ng đi ng n nh t t

ấ ừ ỉ ế ấ ả ắ ạ ồ  đ nh ngu n S đ n t ỉ t c  các đ nh còn l i

 Ký hi uệ  Di : đ

ấ ừ ế ồ ệ ạ node ngu n S đ n node i t ạ ướ i b c ch y hi n

ườ ủ hành c a gi ậ ạ ủ ệ ả ậ i thu t

ạ ọ c ch y hi n hành c a gi ế  node i đ n node j

35

CSE 501035 – Data Communication

ắ ng đi ng n nh t t ậ ả i thu t  M: t p các đ nh đã xét t ạ ướ ỉ i b ố ừ ố  dij : tr ng s  trên c nh n i t ế dij = 0 n u i trùng j  ế dij = Eij n u i khác j

ở ộ

ậ ả Gi i thu t Dijkstra  Gi ậ ả i thu t  B c 1: kh i đ ng ướ  M = {S}  Di = dSI

ậ

ấ ậ ườ ắ ng đi ng n nh t i (cid:0)  V sao cho: DN = min {Di}  (cid:0)

(cid:0) V\M

 B c 2: c p nh t đ ướ ỉ ọ  Ch n đ nh N   M = M (cid:0)  {N}   Dj = min {Dj, DN + dNj  } (cid:0)

ướ

 B c 3: l p l

ặ ạ ướ i b

ế c 2 cho đ n khi M=V

ườ

ấ ừ

ế

ắ ng đi ng n nh t t

ồ  node ngu n S đ n

ẽ ả i s  là đ

ế  K t qu  D node i

36

CSE 501035 – Data Communication

j (cid:0) V\M

ả

ậ

ấ ừ

ườ

ế ấ ả

ạ

Gi  Tìm đ

i thu t Dijkstra ắ ng đi ng n nh t t

ồ  node ngu n 1 đ n t

t c  các node còn l

i

5

3

2

3

5

2

1

2

3

6

1

1

2

1

4

5

M

Node 2

Node 3

Node 4

Node 5

Node 6

(cid:0) (cid:0)

(cid:0)

Laàn  chaïy  1  2  3  4  5  6

1  1 , 4  1 , 4 , 2  1 , 4 , 2 , 5  1 , 4 , 2 , 5 , 3  1 , 4 , 2 , 5 , 3 ,6

D2  Path  2  1 – 2  2  1 – 2  2  1 – 2  2  1 – 2  2  1 – 2  2  1 – 2

D3  Path  5  1 – 3  4  1 – 4 – 3  4  1 – 4 – 3  3  1 – 4 – 5 – 3  3  1 – 4 – 5 – 3  3  1 – 4 – 5 – 3

D4  Path  1  1 – 4  1  1 – 4  1  1 – 4  1  1 – 4  1  1 – 4  1  1 – 4

D5  Path  ­­­  1 – 4 – 5  1 – 4 – 5  1 – 4 – 5  1 – 4 – 5  1 – 4 – 5

2  2  2  2  2

D6  Path  ­­­  ­­­  ­­­  1 – 4 – 5 – 6  1 – 4 – 5 – 6  1 – 4 – 5 – 6

4  4  4

37

CSE 501035 – Data Communication

(cid:0)

ả

ậ

Gi

i thu t Dijkstra

38

CSE 501035 – Data Communication

ậ

ả

i thu t Bellman ­ Ford

Gi  Input

ậ ạ ọ ỉ

 Đ  th  G(V, E) trong đó V là t p đ nh, E là t p c nh có tr ng s   ố ậ  Đ nh ngu n S:  S

 Output

(cid:0) ồ ị ỉ ồ V

(cid:0) không t n t

 Đ  th  có chu trình âm   Đ ng đi ng n nh t t

 Ký hi uệ

ồ ị ườ ắ ấ ừ ỉ i đ ế ấ ả ạ ồ ạ ườ ồ  đ nh ngu n S đ n t ấ ắ ng đi ng n nh t ỉ t c  các đ nh còn l i

 D(h)i : đ (link). ọ

ườ ấ ừ ế ồ ố ạ ắ ng đi ng n nh t t node ngu n S đ n node i có t i đa h đo n

ố ừ ạ ế  node i đ n node j

39

CSE 501035 – Data Communication

ố  dij: tr ng s  trên c nh n i t ế dij = 0 n u i trùng j  ế dij = Eij n u i khác j

ả

ậ

Gi  Gi

ấ ừ

ườ

ế

ố

ạ

V\{S}

i thu t Bellman – Ford ậ ả i thu t  B c 1: kh i đ ng ở ộ ướ  D(1)N = dSN, (cid:0) N (cid:0) ắ ng đi ng n nh t t (đ

S đ n N có t

i đa 1 đo n)

ậ ườ

ậ

 B c 2: c p nh t đ

ấ ắ ng đi ng n nh t j (cid:0)  V\{S}

ướ  D(h+1)N = min {D(h)j + djN}   (cid:0)

ướ

ế

ườ

ớ

 B c 3: l p l

ng đi m i

ặ ạ ướ i b ơ ượ

c 2 cho đ n khi không có đ ừ

ấ

ắ nào ng n h n đ

c tìm th y thì d ng

ả

ườ

ấ ừ

ồ

ắ ng đi ng n nh t t

node ngu n S

ẽ N s  là đ

ế  K t qu  D(h) ế đ n node N

40

CSE 501035 – Data Communication

ả

ậ

i thu t Bellman – Ford  ấ ừ

ườ

ế ấ ả

ạ

Gi  Tìm đ

ắ ng đi ng n nh t t

ồ  node ngu n 1 đ n t

t c  các node còn l

i

5

3

2

3

5

2

1

2

3

6

1

1

2

1

4

5

Node 5  D(h)5  Path

Node 6  D(h)6  Path

Laàn  Node 2  chaïy  D(h)2  Path  1–2  2  1–2  2  1–2  2  1–2  2

1  2  3  4

Node 3  D(h)3  Path  1–3  1–4–3  1–4–5–3  1–4–5–3

5  4  3  3

Node 4  D(h)4  Path  1–4  1–4  1–4  1–4

1  1  1  1

2  2  2

­­­  1–4–5  1–4–5  1–4–5

10  4  4

­­­  1–3–6  1–4–5–6  1–4–5–6

41

CSE 501035 – Data Communication

(cid:0) (cid:0)

ả

ậ

Gi

i thu t Bellman – Ford

42

CSE 501035 – Data Communication

ấ ừ

node 1

Bài t pậ  Tìm đ ườ  Theo gi  Theo gi

ắ ng ng n nh t t ậ ả i thu t Dijkstra ậ ả i thu t Bellman – Ford

4

1

2

3

3

1

6

2

1

2

5

3

4

3

4

3

1

5

7

43

CSE 501035 – Data Communication

ấ ừ

node 1

Bài t pậ  Tìm đ ườ  Theo gi  Theo gi

ắ ng ng n nh t t ậ ả i thu t Dijkstra ậ ả i thu t Bellman – Ford

1

1

E

A

B

1

1

5

1

G

C

3

1

F

D

2

1

4

1

1

H

K

J

44

CSE 501035 – Data Communication

Dijkstra vs. Bellman–Ford     Bellman­Ford ệ

ề

 Vi c tính toán cho node n ph i bi ế ủ ế t các thông tin v  chi phí liên k t c a  ừ  node s đ n các node k  c a node n các node k  và chi phí t ng c ng t

ả ộ

ề ầ ư ế ỗ ế ổ  M i node c n l u tr  t p các chi phí và các đ ườ ữ ậ ề ủ ươ ứ ng  ng đ n các ng đi t

 Có th  trao đ i thông tin v i các node k  tr c ti p ề ự ế  Có th  c p nh t thông tin v  chi phí và đ

ớ ề ổ ậ ự

 Dijkstra

node khác ể ể ậ ổ ớ ườ ề ề ng đi d a trên các thông tin  ế trao đ i v i các node k  và các thông tin v  chi phí liên k t

ầ ế ộ ạ

t chi phí liên k t c a t

 M i node c n bi ỗ  Ph i bi ế ả  Ph i trao đ i thông tin v i t ổ ả

45

CSE 501035 – Data Communication

t topology toàn b  m ng ế ủ ấ ả ớ ấ ả ạ ạ ế t c  các liên k t trong m ng t c  các node khác trong m ng

ủ

ử

ả ầ ừ

ậ i thu t  các node khác

ề

ệ

Đánh giá  Ph  thu c vào th i gian x  lý c a các gi ờ ộ ụ  Ph  thu c vào l ượ ộ ụ ng thông tin yêu c u t  Ph  thu c vào vi c hi n th c ự ệ ệ ộ ụ  Cùng h i t ả ướ ộ ụ ề ộ ờ i d i gi  v  m t l

i đi u ki n topology tĩnh và chi

phí không thay đ iổ ế

ả

ạ ể

ổ

ậ ẽ i thu t s  tính l

i đ  theo

 N u chi phí liên k t thay đ i, các gi

ư

ư

ạ

i thay

ượ

ế ng đi đ

 N u chi phí liên k t thay đ i theo l u thông, l u thông l ổ ọ c ch n

ế ổ ị ự k p s  thay đ i ế ườ ổ đ i theo đ  Ph n h i ồ ả  Có th  r i vào tr ng thái không  n đ nh ạ ể ơ

46

CSE 501035 – Data Communication

ổ ị

ngườ

ARPANET – Tìm đ  Th  h  đ u tiên ế ệ ầ

ễ ướ

ể

ệ

 1969  Distributed adaptive  Dùng th i gian tr   ờ

ẩ c tính làm tiêu chu n đ  đánh giá hi u

ườ

ả

ng Bellman­Ford  ờ

ậ i thu t tìm đ ổ

ễ ớ

qu  ả  Dùng gi  Các node trao đ i thông tin (các vector th i gian tr ) v i các

node k  ề

ậ

ườ

ng d a trên thông tin đ n

ề

ế ỉ

 C p nh t b ng tìm đ ự ậ ả  Không quan tâm đ n t c đ  đ

ng truy n, ch  quan tâm

chi u dài hàng đ i t

ế ố ộ ườ i các node

ợ ạ ợ

ủ

ờ

 Chi u dài hàng đ i không ph i là cách đo chính xác c a th i  ả

ề ề gian tr  ễ ứ

ẽ

ạ

ậ

ớ

 Đáp  ng ch m v i ngh n m ch

47

CSE 501035 – Data Communication

ARPANET – Tìm đ

ngườ

ế ệ ứ

 Th  h  th  2

ờ

ệ

ạ

ặ

ữ

ễ

ạ

ờ

 1979  Dùng th i gian tr  làm tiêu chu n đánh giá hi u qu   ả ẩ ễ  Th i gian tr  đ ự ế ễ ượ ờ c đo tr c ti p   Dùng gi ườ ậ ả ng Dijkstra i thu t tìm đ  Thích h p cho m ng có t ẹ ả ợ i trung bình ho c nh    Khi m ng t ươ ả ặ i n ng, có ít t ờ

ễ ặ

ượ

ng quan gi a th i gian tr  đo  ả c và th i gian tr  g p ph i

đ

ế ệ ứ

 Th  h  th  3

ế

ượ

ổ ượ c thay đ i  ố c đo trong 10 giây cu i  ả ướ

ị ệ ạ

ườ

ự

 1987  Vi c tính toán chi phí c a liên k t đã đ ủ ệ  Th i gian tr  trung bình đ ễ ờ  Bình th

ng hóa d a trên giá tr  hi n t

ế i và k t qu  tr

c đó

48

CSE 501035 – Data Communication

ạ

ệ

ế

ạ

ạ

ạ

ề ố M ng truy n s  luy n X.25  1976, CCITT  Giao ti p gi a máy ch  và  ủ ữ ể m ng chuy n m ch gói  công c ngộ ổ ế ể

 Ph  bi n trong các m ng  ạ ủ

ể chuy n m ch gói và chuy n  m ch gói c a m ng ISDN

ớ

ạ  Đ nh nghĩa 3 l p

ạ ị  V t lý  ậ  Liên k t ế  Gói

X.25 Interface

49

CSE 501035 – Data Communication

X.25 – 3 l pớ  V t lýậ

 Giao ti p gi a tr m và liên  ữ ế ế ớ k t v i node

ạ

ặ ả ớ ấ

 DTE: user equipment  DCE: node  Dùng đ c t ậ  l p v t lý X.21  Cung c p vi c truy n d  li u  ề ữ ệ ệ ế ậ tin c y thông qua liên k t v t  lý

ậ

 D  li u là chu i các frame

ỗ

 Link Access Protocol  Balanced (LAPB)

ứ

 T p con c a nghi th c  ủ

ậ HDLC

 Gói

ữ ệ  Liên k tế

 External virtual circuits  K t n i lu n lý (virtual  ậ ữ

ế ố

50

CSE 501035 – Data Communication

circuits) gi a các thuê bao

X.25 – Virtual Circuit

 D ch v  m ch  o ụ ạ ả

ộ

ỗ

c t o đ ng cho m i giao d ch

c gán tr

ầ

ị  Virtual Call (SVC – Switched Virtual Circuit)  Virtual circuit đ ị ượ ạ  Permanent virtual circuit  Virtual circuit đ  Không c n thi

ướ ố ị ượ c c  đ nh ế ố ế ậ t l p và xóa k t n i

 Fast Select call

ề

ỏ

 Dùng đ  truy n  ể ệ thông báo/l nh nh (<128 octet) trong quá  ế ậ trình thi

ế ố t l p/xóa k t n i

51

CSE 501035 – Data Communication

ạ

ị

X.25 – Đ nh d ng gói

52

CSE 501035 – Data Communication

ữ ệ

X.25 – Gói d  li u

 S  VC (12 bits) – 4 bit logical group number + 8 bit logical channel number.

ườ

ng 2 tr

ư ộ c xem nh  m t ữ

ị ạ ế ố

ượ ặ

ộ ặ

ị

ườ ể ỉ ạ ế ố ể

ộ ườ

ế

ậ

ậ

ố  Thông th ng này đ  Dùng đ  ch  th  lo i k t n i ho c kênh gi a các DTE  Các lo i k t n i khác nhau cho phép nhi u phiên giao d ch gi a cùng m t c p DTE ề  Có th  lên đ n 4095 kênh lu n lý trên cùng m t đ

ữ ế ng giao ti p v t lý

ượ ị

ườ

 Q bit (Qualifier bit) – không đ

c đ nh nghĩa trong chu n, th

ng phân bi ề

ứ ữ ệ

ẩ ứ

ệ t các gói  ể ch a d  li u (i.e. user information Q=0) và các gói ch a thông tin đi u khi n (Q=1)

ề

ị

ẽ ế ướ

ể

ạ

ộ

ớ ạ

ẽ ượ

 M bit (More bit) – ch  th  nhi u gói s  ti p theo ỉ  M ng chuy n gói công c ng có kích th

c gi

i h n cho các gói (thông báo s  đ

c

ề

ẽ

phân thành nhi u gói  Ngo i tr  gói cu i cùng, các gói s  có bit M đ ạ ừ ố ằ

ộ

ượ ậ c b t (M=1) ả ị

ầ ủ

ằ

ượ

 D bit – b ng 0 khi gói này là m t ph n c a gói b  phân m nh, b ng 1 khi gói đ

c tái

ượ

h pợ  Cũng đ

ụ ộ

c dùng đ  đi u khi n dòng ự ự

ể ề ể ể

ở

ể  Khi D=0, đi u khi n dòng đ ượ ề  Khi D=1, đi u khi n dòng đ ượ ề

ệ ụ ộ ữ c th c hi n c c b  (gi a DTE và c c b  DCE) ữ ệ c th c hi n gi a DTE và DTE

xa

ầ ự

ậ

 P(R) – ch  s  nh n tu n t ỉ ố  P(S) – ch  s  g i tu n t ầ ự ỉ ố ở

53

CSE 501035 – Data Communication

ề ế ố

 Gói thi

ế ậ ề ậ ẩ t l p k t n i, đi u khi n dòng, giám sát, xác nh n, chu n đoán,

ể X.25 – Gói đi u khi n  6 nhóm: thi ể ắ ng t quãng ế ố ế ậ t l p k t n i ạ ượ

ạ ả

ạ

 4 lo i: Call Request, Incoming Call, Call Accepted, và Call Connected  Đ c dùng trong giai đo n thi ế ậ

t l p m ch  o

 Gói đi u khi n dòng ề ạ ượ

ề ữ ệ

ứ

ề

ạ

 3 lo i: Receive Ready (RR), Receive Not Ready (RNR), và Reject (REJ)  Đ c dùng trong giai đo n truy n d  li u (các gói đ u ch a P(R))  Xem thêm HDLC

 Gói giám sát

ồ

 Bao g m: Restart Request/Indication, Clear Request/Indication, Reset

ượ

ể

ấ

ố

c dùng trong tình hu ng x u (host crash) đ  xóa VC do DTE

Request/Indication  Restart Request đ này đang giữ

ượ

ể

ượ

ể

ậ

ỉ c ch  ra trong VC number) ầ ự ề ở ỉ ố c dùng đ  reset ch  s  nh n/g i tu n t

ế ộ  v  0 trong ch  đ

 Clear Request dùng đ  xóa VC (đ  Reset Request đ ề ữ ệ truy n d  li u

54

CSE 501035 – Data Communication

ể

ề

ể

X.25 – Gói đi u khi n  Gói xác nh nậ

ể

ầ

ướ

 Dùng đ  xác nh n các yêu c u tr ậ

c đó (cho Restart, Clear,

Reset, và Interrupt)

 Gói chu n đoán

ạ

ụ

ẩ

 Do m ng t o ra cho m c đích chu n đoán l

ỗ i

ứ

 Đ c truy n trong quá trình truy n d  li u, và không ch a

ậ

ẩ ạ  Gói ng t quãng ắ ượ ỉ ố ở ủ

ầ ự ề

ể

ề ữ ệ ắ ề ề ớ

ắ

ố . Nghĩa là gói ng t quãng không là đ i  ượ c  ớ i DTE đích v i

c truy n t

ượ ữ ệ

ề ch  s  g i/nh n tu n t ể ượ t ng c a quá trình đi u khi n dòng (đi u khi n dòng đ ỏ b  qua và các gói ng t quãng đ ơ ộ ư đ   u tiên cao h n các gói d  li u)

55

CSE 501035 – Data Communication

ạ

ồ

X.25 ­ Multiplexing  DTE có th  t o 4095 m ch  ể ạ ờ ớ ả o đ ng th i v i các DTE  ộ ế ố khác trên m t k t n i DTC­ DCE

 Gói ch a s  m ch  o 12 bit  ứ ố ạ ả  Cách đánh s  m ch  o ố ạ ả

56

CSE 501035 – Data Communication

X.25 – Set và Reset

 Reset

ở ạ ạ i virtual circuit ố ầ ự ượ ặ ằ  đ

c đ t b ng 0 ị ấ

ả

ể

ạ ở

ệ

ẽ

 Kh i t o l  S  tu n t  Các gói đang quá c nh b  m t   Tùy vào các protocol c p cao đ  khôi ph c l ụ ạ ấ  Kích ho t b i vi c m t các gói, sai s  tu n t ố ầ ự ấ

ị ấ i các gói b  m t  ạ , ngh n m ch,

m t internal virtual circuit

ầ

ng đ

ng v i yêu c u xóa t ệ

ươ ấ ạ

ậ

ấ  Restart  T ấ ả ươ ớ t c  các virtual circuit  E.g. m t t m th i vi c truy c p m ng ạ ờ

57

CSE 501035 – Data Communication

ế ậ

X.25 – Th  t c thi  PSN (cid:0)  DTEa (cid:0)

ủ ụ  DCEa (cid:0)

ế ố t l p k t n i  DCEb (cid:0)

DTEb (DTEa mu n ố

ộ

ứ

ị

ế ố ớ k t n i v i DTEb)  DTEa nh n m t virtual circuit number (VCN) ậ  DTEa g i gói call­request cho DTEb (ch a VCN, đ a ch   ỉ ở ị

DTEa, đ a ch  DTEb)

ế

ạ

ỉ ườ

 DCEa tìm đ

ng đi băng qua m ng PSN cho gói này đ n

DCEb

ậ

ế

ở

 DCEb nh n m t VCN m i và g i gói incoming­call đ n

ộ ứ

ị

ồ

ớ ỉ ớ DTEb (gói ch a VCN m i và các thông tin đ a ch   ngu n/đích)

ế ố ằ

ở

ậ

 DTEb ch p nh n k t n i b ng cách g i gói call­accepted qua

ở

c gói call­accepted và g i gói call­connected

ớ

ấ ể ế DCEb đ  đ n DCEa  DCEa nh n đ ậ ượ i DTEa

t

ể ở

 Sau quá trình này, DTEa và DTEb có th  g i các gói d   ữ

ệ

ạ

li u qua l

i

58

CSE 501035 – Data Communication

ế ố i phóng k t n i

X.25 – Th  t c gi  DTEa (cid:0)

DCEb (cid:0)

DTEb (DTEa mu n ố

ớ

i DCEa

ớ

ớ

ả ủ ụ  PSN (cid:0)  DCEa (cid:0) ế ố ớ xóa k t n i v i DTEb)  DTEa g i gói clear­request t ở  DCEa g i gói clear­indication t ở  DTEb g i clear­indication t ở

i DTEb (thông qua DCEb) i DTEa (thông qua các DCEb và

DCEa)

59

CSE 501035 – Data Communication

Virtual Call

60

CSE 501035 – Data Communication

ả

X.25 – Phân m nh (segmentation)

ố

ế ố ớ

ư

 Xét tình hu ng các tr m A, B, C, D k t n i v i nhau A ­ B ­ C ­  ạ ượ ị c đ nh nghĩa nh  sau ướ ướ ướ

ộ

ố

ạ D. Các lo i gói đ  A – B: gói có kích th  B – C: gói có kích th  C – D: gói có kích th ở

ả ở

ế

ơ ữ

ả

ể ả

ề

ế

ậ

ả

ả

 Đ  gi

ộ t m t

 A mu n g i m t gói đ y đ  đ n D, nó ph i g i các gói 1500  ỏ bytes đ n B. B ph i phân nh  các gói này h n n a  (segmentation/fragmentation) ế ấ ả

ề

ợ gói phân m nh và tái h p nó đ  truy n cho D

 X.25 cho phép quá trình phân m nh thông qua các bit M và D.

ệ

ạ

ả

ậ

ợ

ậ ượ

ậ

ả

ợ

ỉ

i quy t v n đ  này, C ph i có kh  năng nh n bi ể ả ậ Các bit này cho phép các tr m nh n di n các gói phân m nh và  tái h p nó, và xác nh n nó (ack), nghĩa là không xác nh n các gói  ả phân m nh, ch  xác nh n khi các gói phân m nh đã đ c tái h p  ộ thành m t gói

61

CSE 501035 – Data Communication

c 1500 bytes c 1000 bytes c 1500 bytes ầ ủ ế

ể

ề

ể

ươ

X.25  Đi u khi n dòng và đi u khi n sai ề ng 5)

 HDLC (ch

ề

ớ

 Chu i các gói ỗ  Chu i đ y đ  các gói  ỗ ầ ủ  Cho phép kh i d  li u l n đ

ố ữ ệ ớ ượ ỏ ơ

ạ ẹ ủ

ố

th

c truy n qua m ng v i kích  ấ ướ c gói nh  h n mà không m t tính toàn v n c a kh i   2 lo i gói  ạ  Các gói A

 M bit 1, D bit 0  Chi u dài gói t ố

i đa

ề  Các gói B

 Ph n còn l ầ

ạ i ể

ượ

ở

 Các gói A (có th  là không có gói A nào) đ

c theo sau b i

gói B

62

CSE 501035 – Data Communication

ọ

Đ c thêm

 W. Stallings, Data and Computer Communications (6th

edition), Prentice Hall 2003, chapter 10

 X.25 info from ITU­T web site  Routing information from Comer

63

CSE 501035 – Data Communication