Problem set 3-solution.pptx

Networks top down approach

1. Computer Networks (CIE 447) Problem set 3 – Chapter 4 Dr. / Samy Soliman T. A. : Eng. Menna Mohamed : Eng. Nourhan Tarek Cie 447- Spring 2020

2. IPv4 addresses IPv4 address is the logical address of a network device, which is composed of a 32-bits address. It is written as 4 octets, that are separated by a dot. Ex.: 172.16.254.1 Each octet in the IPv4 address has a value range from 0 to 255 , where each octet is a 4-bit long. Cie 447- Spring 2020 2

3. The subnet Class A Class A addresses were originally designed for networks with a very large number of hosts. The default subnet mask is 255.0.0.0 or /8. Some of this class addresses are reserved or invalid to be assigned to hosts. 0.0.0.1 to 0.255.255.255 are invalid host addresses. 127.0.0.1 to 127.255.255.255 are invalid host addresses, However, they are used for testing the local computer 127.0.0.1 is used for testing the TCP/IP. Cie 447- Spring 2020 3

4. The subnet Classes B & C Class B Class B addresses were originally designed for medium-sized to large-sized networks. The default subnet mask is 255.255.0.0 or /16. The range of valid addresses are from 128.0.0.0 to 191.255.0.0 / 16. Class C Class C addresses were designed for small networks. The default subnet mask is 255.255.255.0 or /24. The range of valid addresses are from 192.0.0.0 to 123.255.255.0 / 24. Cie 447- Spring 2020 4

5. The subnet Classes D & E Class D Class D addresses are reserved for multicasting IP addresses. The addresses are not assigned to hosts, which means there is no default subnet mask. the range of valid addresses is from 224.0.0.0 to 239.255.255.255 Class E Class E addresses are experimental and reserved for future use. These addresses are not assigned to hosts and there is no default subnet mask. The valid range of addresses is from 240.0.0.0 to 255.255.255.255 Cie 447- Spring 2020 5

6. Classless Interdomain routing (CIDR) Cie 447- Spring 2020 6 Class Size of  network number  bit field Size of  rest  bit field Start address End address Default subnet mask CIDR notation Class A (unicast) 8 24 0.0.0.0 127.255.255.255 255.0.0.0 /8 Class B (unicast) 16 16 128.0.0.0 191.255.255.255 255.255.0.0 /16 Class C (unicast) 24 8 192.0.0.0 223.255.255.255 255.255.255.0 /24 Class D ( multicast ) not defined not defined 224.0.0.0 239.255.255.255 not defined not defined Class E (reserved) not defined not defined 240.0.0.0 255.255.255.255 not defined not defined

7. Classless Interdomain routing (CIDR) Classless Completely eliminates traditional concepts of Class A, B and C addresses. Network prefix based: Routers do not make any assumption on the basis of the three leading bits. They require an explicit network prefix to determine dividing point between network_id (prefix) and host_id . Cie 447- Spring 2020 7

8. Classless Interdomain routing (CIDR) Example: Subnet 1: 213.2.96.0 → 11010101.00000010.011000 00 .00000000 Subnet 2: 213.2.97.0 → 11010101.00000010.011000 01 .00000000 Subnet 3: 213.2.98.0 → 11010101.00000010.011000 10 .00000000 Subnet 4: 213.2.99.0 → 11010101.00000010.011000 11 .00000000 Supernet mask: 255.255.252.0 Supernet address: 213.2.96.0/22 → 11010101 . 00000010 . 011000 00 . 00000000 Cie 447- Spring 2020 8

9. Longest prefix match Matching the longest prefix of an IP destination address to the entries in a routing table, to determine the appropriate outgoing link. Subnet 1’s IP addresses are from 213.2.96.0 → 11010101.00000010.01100000.00 000000 to 213.2.96.23 → 11010101.00000010.01100000.00 110111 The longest prefix match that is used in the forwarding table of the router is: 11010101.00000010.01100000.00 Subnet 2’s IP addresses are from 213.2.97.0 → 11010101.00000010.01100001 .00000000 to 213.2.97.226 → 11010101.00000010.01100001. 11100010 The longest prefix match that is used in the forwarding table of the router is: 11010101.00000010.01100001 Cie 447- Spring 2020 9

10. Problem 4 Consider the network below. a. Suppose that this network is a datagram network. Show the forwarding table in router A, such that all traffic destined to host H3 is forwarded through interface 3. Cie 447- Spring 2020 10

11. Problem 4 Consider the network below. a. Suppose that this network is a datagram network. Show the forwarding table in router A, such that all traffic destined to host H3 is forwarded through interface 3. Solution: Cie 447- Spring 2020 11 Destination address Interface link H3 3

12. Problem 4 Consider the network below. b. Suppose that this network is a datagram network. Can you write down a forwarding table in router A, such that all traffic from H1 destined to host H3 is forwarded through interface 3, while all traffic from H2 destined to host H3 is forwarded through interface 4? (Hint: this is a trick question.) Cie 447- Spring 2020 12

13. Problem 4 Consider the network below. b. Suppose that this network is a datagram network. Can you write down a forwarding table in router A, such that all traffic from H1 destined to host H3 is forwarded through interface 3, while all traffic from H2 destined to host H3 is forwarded through interface 4? (Hint: this is a trick question.) Solution: No, because the forwarding table is based on the destination address, not the source address Cie 447- Spring 2020 13 Destination address Interface link H3 3 H3 4

14. Problem 4 Consider the network below. c. Now suppose that this network is a virtual circuit network and that there is one ongoing call between H1 and H3, and another ongoing call between H2 and H3. Write down a forwarding table in router A, such that all traffic from H1 destined to host H3 is forwarded through interface 3, while all traffic from H2 destined to host H3 is forwarded through interface 4. Cie 447- Spring 2020 14

15. Problem 4 Consider the network below. c. Now suppose that this network is a virtual circuit network and that there is one ongoing call between H1 and H3, and another ongoing call between H2 and H3. Write down a forwarding table in router A, such that all traffic from H1 destined to host H3 is forwarded through interface 3, while all traffic from H2 destined to host H3 is forwarded through interface 4. Solution: the forwarding table at router A Cie 447- Spring 2020 15 11 12 13 14 22 21 23 24 Incoming interface Incoming VC Outgoing interface Outgoing VC 1 11 3 12 2 21 4 22

16. Problem 4 Consider the network below. d. Assuming the same scenario as (c), write down the forwarding tables in nodes B, C, and D. Cie 447- Spring 2020 16

17. 14 22 21 23 24 13 11 12 Problem 4 Consider the network below. d. Assuming the same scenario as (c), write down the forwarding tables in nodes B, C, and D. Solution: The forwarding table at router B: The forwarding table at router C: Cie 447- Spring 2020 17 Incoming interface Incoming VC Outgoing interface Outgoing VC 1 12 2 13 Incoming interface Incoming VC Outgoing interface Outgoing VC 1 22 2 23 The forwarding table at router D: Incoming interface Incoming VC Outgoing interface Outgoing VC 1 13 3 14 2 23 3 24

18. Problem 5(*) Consider a VC network with a 2-bit field for the VC number. Suppose that the network wants to set up a virtual circuit over four links: link A, link B, link C, and link D. Suppose that each of these links is currently carrying two other virtual circuits, and the VC numbers of these other VCs are as follows: Cie 447- Spring 2020 18 In answering the following questions, keep in mind that each of the existing VCs may only be traversing one of the four links. a. If each VC is required to use the same VC number on all links along its path, what VC number could be assigned to the new VC?

19. Problem 5(*) Consider a VC network with a 2-bit field for the VC number. Suppose that the network wants to set up a virtual circuit over four links: link A, link B, link C, and link D. Suppose that each of these links is currently carrying two other virtual circuits, and the VC numbers of these other VCs are as follows: Cie 447- Spring 2020 19 In answering the following questions, keep in mind that each of the existing VCs may only be traversing one of the four links. a. If each VC is required to use the same VC number on all links along its path, what VC number could be assigned to the new VC? Solution: A new VC can’t be established, as the VC number is 2 bits.  

20. Problem 5(*) Consider a VC network with a 2-bit field for the VC number. Suppose that the network wants to set up a virtual circuit over four links: link A, link B, link C, and link D. Cie 447- Spring 2020 20 b. If each VC is permitted to have different VC numbers in the different links along its path (so that forwarding tables must perform VC number translation), how many different combinations of four VC numbers (one for each of the four links) could be used?

21. Problem 5(*) Consider a VC network with a 2-bit field for the VC number. Suppose that the network wants to set up a virtual circuit over four links: link A, link B, link C, and link D. Cie 447- Spring 2020 21 b. If each VC is permitted to have different VC numbers in the different links along its path (so that forwarding tables must perform VC number translation), how many different combinations of four VC numbers (one for each of the four links) could be used? Solution: The number of link = 4 and each link has 2 VC numbers The total combinations of the 4 VC links = = 16 combination (10, 00, 00, 10) or (00, 10, 00, 10)  

22. Problem 10 Consider a datagram network using 32-bit host addresses. Suppose a router has four links, numbered 0 through 3, and packets are to be forwarded to the link interfaces as follows: a. Provide a forwarding table that has five entries, uses longest prefix matching, and forwards packets to the correct link interfaces. Cie 447- Spring 2020 22 Destination Address Range Link Interface 11100000 00000000 00000000 00000000 Through 11100000 00111111 11111111 11111111 11100000 01000000 00000000 00000000 Through 11100000 01000000 11111111 11111111 1 11100000 01000001 00000000 00000000 Through 11100001 01111111 11111111 11111111 2 Otherwise 3

23. Problem 10 Consider a datagram network using 32-bit host addresses. Suppose a router has four links, numbered 0 through 3, and packets are to be forwarded to the link interfaces as follows: a. Provide a forwarding table that has five entries, uses longest prefix matching, and forwards packets to the correct link interfaces. Solution: Cie 447- Spring 2020 23 Destination Address Range Link Interface 11100000 00000000 00000000 00000000 Through 11100000 00111111 11111111 11111111 11100000 01000000 00000000 00000000 Through 11100000 01000000 11111111 11111111 1 11100000 01000001 00000000 00000000 Through 11100001 01111111 11111111 11111111 2 Otherwise 3 Entry no. Prefix match Link interface 1 11100000 00 2 11100000 01000000 1 3 1110000 2 4 11100001 1 3 5 Otherwise 3

24. Problem 10 Consider a datagram network using 32-bit host addresses. Suppose a router has four links, numbered 0 through 3, and packets are to be forwarded to the link interfaces as follows: b. Describe how your forwarding table determines the appropriate link interface for datagrams with destination addresses: 11001000 10010001 01010001 01010101 11100001 01000000 11000011 00111100 11100001 10000000 00010001 01110111 Cie 447- Spring 2020 24

25. Problem 10 Consider a datagram network using 32-bit host addresses. Suppose a router has four links, numbered 0 through 3, and packets are to be forwarded to the link interfaces as follows: b. Describe how your forwarding table determines the appropriate link interface for datagrams with destination addresses: Cie 447- Spring 2020 25 Entry no. Prefix match Link interface 1 11100000 00 2 11100000 01000000 1 3 1110000 2 4 11100001 1 3 5 Otherwise 3 Solution: 11001000 10010001 01010001 01010101 → it matches entry: otherwise, it will be forwarded to link 3 11100001 01000000 11000011 00111100 → it matches entry, it will be forwarded to link 2 11100001 10000000 00010001 01110111 → it matches entry, it will be forwarded to link 3  

26. Problem 11 Consider a datagram network using 8-bit host addresses. Suppose a router uses longest prefix matching and has the following forwarding table: For each of the four interfaces, give the associated range of destination host addresses and the number of addresses in the range. Cie 447- Spring 2020 26

27. Problem 11 Consider a datagram network using 8-bit host addresses. Suppose a router uses longest prefix matching and has the following forwarding table: For each of the four interfaces, give the associated range of destination host addresses and the number of addresses in the range. Solution: Cie 447- Spring 2020 27 Destination Address Range Link Interface No. of addresses in a link 00000000 Through 00111111 01000000 Through 01011111 1 01100000 Through 01111111 2 10000000 Through 10111111 2 11000000 Through 11111111 3 Destination Address Range Link Interface No. of addresses in a link 00000000 Through 00111111 01000000 Through 01011111 1 01100000 Through 01111111 2 10000000 Through 10111111 2 11000000 Through 11111111 3

28. Problem 12(*) Consider a datagram network using 8-bit host addresses. Suppose a router uses longest prefix matching and has the following forwarding table: For each of the four interfaces, give the associated range of destination host addresses and the number of addresses in the range. Cie 447- Spring 2020 28

29. Problem 12(*) Consider a datagram network using 8-bit host addresses. Suppose a router uses longest prefix matching and has the following forwarding table: For each of the four interfaces, give the associated range of destination host addresses and the number of addresses in the range. Solution: Cie 447- Spring 2020 29 Destination Address Range Link Interface No. of addresses in a link 10000000 Through 11111111 10000000 Through 10111111 1 11100000 Through 11111111 2 32 00000000 Through 01111111 3 Destination Address Range Link Interface No. of addresses in a link 10000000 Through 11111111 10000000 Through 10111111 1 11100000 Through 11111111 2 00000000 Through 01111111 3

30. Problem 13 Consider a router that interconnects three subnets: Subnet 1, Subnet 2, and Subnet 3. Suppose all of the interfaces in each of these three subnets are required to have the prefix 223.1.17/24. Also suppose that Subnet 1 is required to support at least 60 interfaces, Subnet 2 is to support at least 90 interfaces, and Subnet 3 is to support at least 12 interfaces. Provide three network addresses (of the form a.b.c.d /x) that satisfy these constraints. Cie 447- Spring 2020 30

31. Problem 13 Consider a router that interconnects three subnets: Subnet 1, Subnet 2, and Subnet 3. Suppose all of the interfaces in each of these three subnets are required to have the prefix 223.1.17/24. Also suppose that Subnet 1 is required to support at least 60 interfaces, Subnet 2 is to support at least 90 interfaces, and Subnet 3 is to support at least 12 interfaces. Solution: The total no. of addresses = and by mapping the CIDR into binary address The IP address: 223.1.17.0 → network address, can’t be used as an interface and the IP address: 223.1.17.225 → broadcast address For subnet 1: it needs 60 interfaces +2 (network and broadcast) The subnet 1 address: 223.1.17.0/25 For subnet 2: it needs 90 interfaces +2 (network and broadcast) The subnet 2 address: 223.1.17.64/24 For subnet 3: it needs 12 interfaces +2 (network and broadcast) The subnet 3 address: 223.1.17.192/28   Cie 447- Spring 2020 31 223 1 17 x 11011111 00000001 00010001 xxxxxxxx

32. Problem 17 Consider the topology shown in Figure 4.17. Denote the three subnets with hosts (starting clockwise at 12:00) as Networks A, B, and C. Denote the subnets without hosts as Networks D, E, and F. a. Assign network addresses to each of these six subnets, with the following constraints: All addresses must be allocated from 214.97.254/23; Subnet A should have enough addresses to support 250 interfaces; Subnet B should have enough addresses to support 120 interfaces; Subnet C should have enough addresses to support 120 interfaces. subnets D, E and F should each be able to support two interfaces. Cie 447- Spring 2020 32

33. Problem 17 Consider the topology shown in Figure 4.17. Denote the three subnets with hosts (starting clockwise at 12:00) as Networks A, B, and C. Denote the subnets without hosts as Networks D, E, and F. a. Assign network addresses to each of these six subnets, with the following constraints: All addresses must be allocated from 214.97.254/23; The total no. of available addresses =   Cie 447- Spring 2020 33 214 97 254 x 11010110 01100001 1111111 xxxxxxxx

34. Problem 17 a. Assign network addresses to each of these six subnets, with the following constraints: Subnet A should have enough addresses to support 250 interfaces; it needs 250 interfaces +2 (network and broadcast) Subnet B should have enough addresses to support 120 interfaces; it needs 120 interfaces +2 (network and broadcast) Subnet C should have enough addresses to support 120 interfaces. it needs 120 interfaces +2 (network and broadcast) subnets D, E and F should each be able to support two interfaces. Each needs 2 interfaces The total no. of the designed addresses = 516, which exceeds the available number of addresses Sol. : Deduct a number of addresses from one of the subnets → Subnet B   Cie 447- Spring 2020 34

35. Problem 17 a. Assign network addresses to each of these six subnets, with the following constraints: Subnet A should have enough addresses to support 250 interfaces; it needs 250 interfaces +2 (network and broadcast) The range of addresses are 214.97.255.00000000 → 214.97.255. 00000001 The range of addresses are 214.97.255.0 → 214.97.255.254 Subnet A’s network address: 214.97.255/24 Subnet B should have enough addresses to support 120 interfaces; it needs 120 interfaces +2 (network and broadcast) Only 120 addresses will be used. a set of IP addresses will be deducted. The range of addresses are 214.97.254.00000000 → 214.97.255. 01111111 The required no. of addresses to be deducted = 8 The deducted range of addresses: 214.97.254.00000000 → 214.97.254.00000111   Cie 447- Spring 2020 35 Subnet B’s network address : 214.97.254.0/25 - 214.97.254.0/29  

36. Problem 17 a. Assign network addresses to each of these six subnets, with the following constraints: Subnet C should have enough addresses to support 120 interfaces. it needs 120 interfaces +2 (network and broadcast) The range of addresses are 214.97.254.10000000 → 214.97.254. 11110111 The range of addresses are 214.97.254.128 → 214.97.254.247 Subnet C’s network address: 214.97.254.128/25 subnets D, E and F should each be able to support two interfaces. Subnet D has 2 addresses : 214.97.254.0/31 Subnet E has 2 addresses : 214.97.254.2/31 Subnet F has 4 addresses : 214.97.254.4/30   Cie 447- Spring 2020 36

37. Problem 17 Cie 447- Spring 2020 37

38. Problem 17 Consider the topology shown in Figure 4.17. Denote the three subnets with hosts (starting clockwise at 12:00) as Networks A, B, and C. Denote the subnets without hosts as Networks D, E, and F. b. Using your answer to part (a), provide the forwarding tables (using longest prefix matching) for each of the three routers. Router 1: Cie 447- Spring 2020 38 Longest prefix match Link interface 11010110 01100001 11111111 A 11010110 01100001 11111110 0000000 D 11010110 01100001 11111110 000001 F

39. Problem 17 Consider the topology shown in Figure 4.17. Denote the three subnets with hosts (starting clockwise at 12:00) as Networks A, B, and C. Denote the subnets without hosts as Networks D, E, and F. b. Using your answer to part (a), provide the forwarding tables (using longest prefix matching) for each of the three routers. Router 2: Cie 447- Spring 2020 39 Longest prefix match Link interface 11010110 01100001 11111110 1 C 11010110 01100001 11111110 0000001 E 11010110 01100001 11111110 000001 F

40. Problem 17 Consider the topology shown in Figure 4.17. Denote the three subnets with hosts (starting clockwise at 12:00) as Networks A, B, and C. Denote the subnets without hosts as Networks D, E, and F. b. Using your answer to part (a), provide the forwarding tables (using longest prefix matching) for each of the three routers. Router 3: Cie 447- Spring 2020 40 Longest prefix match Link interface 11010110 01100001 11111110 0 B 11010110 01100001 11111110 0000000 D 11010110 01100001 11111110 0000001 E

41. Homework Solve problems 14, 15 and 16. Due date : 5/4/2020 Cie 447- Spring 2020 41