Networks MidKit

PART 1Introduction

0/6

جزء صغير. اللي بييجي منه: تعريفات، الفرق بين شوية حاجات، والـ layers. احفظ الجمل الإنجليزي زي ما هي، وتحت كل جملة سطر بالعربي يفهّمك معناها.

خريطة الجزء — العناوين وتابعة لإيه (دوس على أي عنوان يوديك له)

Part 1 كله (20 سلايد) + Part 2 لحد سلايد 32 ← Assignment 1

Definitionsslides 2–4

ASG1 P1a,b

Network: a collection of nodes connected by communication links.الشبكة = مجموعة أجهزة (nodes) متوصلة ببعض بلينكات.
Communication link: a medium through which data travels (coax, fiber optics, radio spectrum).اللينك = الوسط اللي الداتا بتعدي فيه: سلك نحاس، فايبر، أو موجات راديو.
Internet: a network of networks that interconnects billions of computing devices.الإنترنت = شبكات كتير متوصلة ببعض.
WWW: a distributed system that runs on top of the Internet.الويب مش هو الإنترنت؛ الويب برنامج شغال فوق الإنترنت.
Computing devices (= hosts / end systems): Traditional: computers, smartphones, tablets. Non-traditional: TVs, home security systems, home appliances, watches, cars.أي جهاز على الشبكة اسمه host أو end system: تقليدي (كمبيوتر، موبايل) أو غير تقليدي (تلفزيون، ساعة، عربية).
Distributed system: a collection of nodes that appears to users as a single system; users are unaware of the underlying structure.كذا جهاز بيشتغلوا مع بعض وإنت شايفهم كأنهم جهاز واحد ومش شايف التفاصيل.
Network: users have to specify the location of resources.في الشبكة العادية إنت اللي لازم تقول الحاجة موجودة على أنهي جهاز.
Relation: a distributed system is a software system built on top of a network.العلاقة بينهم: الـ distributed system برنامج مبني فوق الشبكة.

Network Classificationslides 5–9

ASG1 P1c,e

By transmission

Broadcast: a single channel shared by all nodes; data sent as packets; supports unicast, multicast, broadcast; the intended recipient(s) are encoded in the address field.قناة واحدة الكل بيسمعها. الباكت فيها عنوان بيقول هي لمين: لواحد (unicast)، لمجموعة (multicast)، أو للكل (broadcast).
Point-to-point: many connections between individual pairs of nodes; a packet may pass through intermediate nodes; there could be multiple routes.لينكات بين كل جهازين. الباكت ممكن تعدي على أجهزة في النص، وممكن يكون فيه أكتر من طريق.

Broadcast network slide — Slide 5 · Broadcast: سلك واحد للكل

Point-to-point network slide — Slide 6 · Point-to-point: لينكات بين كل اتنين

By switching

Circuit switching (e.g. landline phones): dedicated links established between the communicating nodes → idle periods waste resources → poor utilization.زي التليفون الأرضي: الخط محجوز ليك طول المكالمة، حتى لو ساكت ← الخط ضايع على الباقي ← استغلال وحش.
Packet switching: no dedicated links; data sent in small messages (packets); different nodes use the same links at the same time → efficient utilization.مفيش حجز: الداتا بتتقطع باكتس صغيرة والكل بيشارك نفس اللينكات ← استغلال كويس.

By scale

Network scale table — Slide 9 · PAN 1 m · LAN 10 m–1 km · MAN 10 km · WAN 100–1000 km · Internet 10,000 km

PAN (1 m) · LAN (room, building, campus) · MAN (city) · WAN (country, continent) · the Internet (planet).التصنيف بالحجم: حواليك (PAN)، مبنى أو جامعة (LAN)، مدينة (MAN)، دولة أو قارة (WAN)، الكوكب كله (الإنترنت).

Network Architecture (Layering) & Protocolsslides 10–12

ASG1 P2a,bMID 2026 P1a

Networks are organized as a stack of layers → reduces design complexity.الشبكة متقسمة طبقات فوق بعض؛ الفايدة إن التصميم يبقى أبسط (كل طبقة ليها شغلة محددة).
Each layer provides certain services to the layer above it.كل طبقة بتخدم الطبقة اللي فوقها.
Each adjacent pair of layers at the same node is connected by an interface.الطبقتين اللي فوق بعض في نفس الجهاز بيتكلموا من خلال interface.
Only corresponding layers at different nodes “communicate”, using protocols. Different layers at different nodes do NOT communicate.الطبقة في جهازك بتكلم نفس الطبقة في الجهاز التاني بس (مثلًا transport مع transport)، وده اسمه protocol.
Protocol: every activity on the Internet that involves two or more communicating nodes is governed by a protocol. A protocol defines the format and the order of messages exchanged, and the actions taken on the transmission and/or receipt of a message.الـ protocol = اتفاق بين الجهازين بيحدد 3 حاجات: شكل الرسالة، ترتيب الرسايل، والأكشن اللي يتعمل لما رسالة تتبعت أو توصل.

Layered architecture slide — Slide 11 · الخط الرأسي = interface (نفس الجهاز) · الخط المتقطع = protocol (نفس الطبقة في جهازين)

The 5 Internet Layersslides 13–18

ASG1 P2c

Layer	Packet name	What to write
Application	message	Supports network applications (HTTP → Web, SMTP → e-mail, FTP → file transfer); interfaces directly with application processes; an application-layer protocol is distributed over multiple end systems.طبقة البرامج: المتصفح (HTTP)، الإيميل (SMTP)، نقل الملفات (FTP). البرنامج عندك بيكلم البرنامج في الجهاز التاني.
Transport	segment	Accepts data from above and splits it into smaller units; controls link reliability (flow control, segmentation/de-segmentation, error control); determines type of service; isolates upper layers from hardware changes.بتاخد الرسالة وتقطعها حتت (segments)، وتتحكم في السرعة والأخطاء، وتخبي تفاصيل الهاردوير عن الطبقات اللي فوق.
Network	datagram	Routing and addressing; end-to-end (source → destination) packet delivery; quality of service and error control.العناوين (IP) واختيار الطريق (routing) من المصدر للوجهة.
Link	frame	Transfers data between nodes: buffer allocation, size of transmitted data, ensures correct reception; may detect and correct errors from the physical layer.نقل الداتا بين جهازين جنب بعض على لينك واحد، وتأكيد إنها وصلت صح.
Physical	bits	Transmits raw bits over a channel: voltage levels for bits, duration of each bit, network connector type and shape, connection initiation and disconnection.الكهربا والأسلاك: الفولت اللي يمثل 0 و1، مدة كل bit، شكل الفيشة، وبدء وقطع الاتصال.

Encapsulationslide 19

ASG1 P2d

At the source (down): message M → transport adds Ht (segment) → network adds Hn (datagram) → link adds Hl (frame) → physical sends bits.وإنت نازل كل طبقة بتحط header قدام الرسالة (زي ظرف جوه ظرف): Ht ثم Hn ثم Hl.
In between: a link-layer switch processes up to the link layer; a router processes up to the network layer.الـ switch بيفتح الظرف الأول بس (frame)، والـ router بيفتح ظرفين (لحد الـ IP).
At the destination (up): each layer removes its own header and passes the rest up until M reaches the application.في الجهاز التاني وإنت طالع كل طبقة بتشيل الـ header بتاعها وتدي الباقي للي فوقها.

الخلاصة — Part 1أهم نقط البارت في سطور؛ راجعها قبل ما تقفله

Definitions

Network = nodes + links · Internet = network of networks
WWW = distributed system on top of the Internet
Distributed system: looks like one system · Network: user specifies location

Classification

Broadcast: one shared channel + address field · Point-to-point: links between pairs
Circuit = dedicated → poor utilization · Packet = shared → efficient
PAN < LAN < MAN < WAN < Internet

Layers & protocols

Layering → reduces design complexity
Interface = adjacent layers, same node · Protocol = peer layers, different nodes
Protocol = format + order + actions
message → segment → datagram → frame → bits
Encapsulation: + Ht, + Hn, + Hl · switch opens up to Link · router up to Network

PART 2Data Link Layer

0/12

أكبر جزء في الميدترم. 4 مواضيع: إزاي نبعت frame (framing + errors)، إزاي كذا جهاز يشاركوا قناة واحدة (MAC)، Ethernet وWiFi، وأخيرًا hubs وswitches.

خريطة الجزء — العناوين وتابعة لإيه (دوس على أي عنوان يوديك له)

سلايد 1–32 ← Assignment 1 · سلايد 33–57 ← Assignment 2 · سلايد 58–96 ← Assignment 3

DLL Basics & Implementationslides 4–8

ASG1 P3a,b

A DLL protocol transmits frames over a single link. It defines: the format of frames; the actions taken when sending/receiving frames; the channel access protocol (rules for transmitting a frame onto the link).شغلة الـ link layer: تبعت frame على لينك واحد بس (بين جهازين جنب بعض). بتحدد شكل الـ frame، الأكشن عند الإرسال والاستقبال، وقواعد مين يستخدم اللينك إمتى.
Basic functions: error detection, frame retransmission, flow control.3 وظايف أساسية: اكتشاف الأخطاء، إعادة إرسال الـ frame، والتحكم في سرعة الإرسال.
Implemented on a chip called the network adapter = network interface controller (NIC); mostly in hardware.متنفذة في كارت الشبكة (NIC)، وأغلبها hardware مش software.
Sending side: controller takes the datagram stored in host memory by higher layers → encapsulates it in a frame → transmits it. Receiving side: receives the entire frame → extracts the datagram.في الإرسال الكارت بياخد الـ datagram من الميموري ويلفها في frame ويبعتها. في الاستقبال بيستقبل الـ frame كلها ويطلع منها الـ datagram.

Link layer implementation: host, CPU, memory, adapter — Slide 6 · الـ NIC فيه controller + physical transmission

Framing slide — Slide 8 · Header | Payload | Trailer

Framing & Frame Boundariesslides 8–11

ASG1 P4a

The DLL encapsulates network-layer packets into frames [Header | Payload | Trailer]; the physical layer sends a raw stream of bits.المشكلة: المستقبل بيستقبل bits ورا بعض، فمحتاج يعرف الـ frame بتبدأ منين وتخلص فين. دي الـ 3 طرق:
1) Character count: a header field = number of characters in the frame (includes itself). An error in the count → loss of synchronization.نحط في الأول رقم بيقول الـ frame طولها كام حرف (الرقم بيحسب نفسه). العيب: لو الرقم باظ، المستقبل يضيع ويقرا كل اللي بعده غلط.
2) Flag bytes with byte stuffing: each frame starts and ends with a FLAG byte; an ESC byte is inserted before every FLAG or ESC that appears inside the data.نحط byte مميز اسمه FLAG في الأول والآخر. لو نفس الـ FLAG (أو ESC) ظهر جوه الداتا بالصدفة، نحط قبله ESC عشان المستقبل يعرف إنه داتا مش نهاية.
3) Starting & ending flags with bit stuffing: flag = 01111110. After five consecutive 1s in the data, the sender stuffs a 0; the receiver deletes it. Data 01111110 is sent as 011111010.نفس الفكرة على مستوى الـ bits: الـ FLAG فيه ست 1 ورا بعض، فلو الداتا فيها خمس 1 ورا بعض نحشر 0 بعدهم عشان ماتبقاش ست. المستقبل يشيل الـ 0 ده.

Character count framing slide — Slide 9 · Character count: الغلط في العدّاد بيضيّع الـ sync

Byte stuffing slide — Slide 10 · Byte stuffing: ESC قبل أي FLAG أو ESC

Flow Control & Error Controlslides 12–16

ASG1 P3c,dMID 2025 P2b

Flow control is needed when nodes operate at different speeds and have limited buffering; prevents the sender from overwhelming the receiver.الراسل سريع والمستقبل بطيء وذاكرته صغيرة ← لازم حاجة تمنع الراسل إنه يغرّق المستقبل.
Feedback-based: the receiver sends back information giving the sender permission to send more data, or telling it how the receiver is doing.النوع الأول: المستقبل بيبعت للراسل "ابعت كمان" أو "استنى".
Rate-based: a built-in mechanism limits the sending rate, without feedback from the receiver.النوع التاني: الراسل عنده حد أقصى للسرعة من الأول، من غير ما المستقبل يرد عليه.
Error control: all frames delivered correctly and in order: sequence numbers; a timer per frame; positive ACK if correct; negative ACK if wrong → retransmit; timer expires → retransmit.عشان نضمن إن كل frame توصل صح وبالترتيب: نرقّم الـ frames، نشغّل timer لكل واحدة، المستقبل يرد ACK لو صح أو NACK لو غلط. لو NACK أو التايمر خلص ← نبعت تاني.
Errors come from signal attenuation and electromagnetic noise.الأخطاء سببها ضعف الإشارة مع المسافة والتشويش الكهرومغناطيسي.
Error detection: enough redundancy to know an error occurred → request retransmission → used on highly reliable channels (fiber).نضيف bits زيادة تكفي بس إننا نعرف إن فيه غلط ونطلب إعادة. مناسب للقنوات النضيفة زي الفايبر لأن الإعادة نادرة.
Error correction: enough redundancy to find the error locations and fix them → used on channels with many errors (wireless).نضيف bits أكتر تكفي إننا نعرف الغلط فين ونصلّحه بنفسنا. مناسب للـ wireless لأن الأخطاء كتير والإعادة هتبقى مكلفة.

Error detection and correction block diagram — Slide 17 · D + EDC → لينك فيه أخطاء → D' EDC' → OK؟

Parity · Checksum · CRC · Hammingslides 18–32

ASG1 P4b,P5ASG2 P1MID 2025 CRC

Parity

One bit added so the number of 1’s is even or odd.أبسط طريقة: bit واحدة زيادة تخلي عدد الـ 1 في الداتا زوجي (even) أو فردي (odd). لو العدد اتغير يبقى فيه غلط.
2D parity: bits in a matrix; a parity bit for each row and column. Detects and corrects one error (row + column locate it). Two errors are detected but not corrected.نرص الداتا صفوف وأعمدة ونحط parity لكل صف ولكل عمود. غلطة واحدة: الصف الغلط × العمود الغلط = مكانها بالظبط فنصلّحها. غلطتين: نعرف إن فيه غلط بس مش نعرف نصلّح.

Two dimensional parity correctable error — Slide 20 · غلطة واحدة: الصف × العمود بيحددوا مكانها

Checksum

d bits treated as k-bit integers and summed; the sum is the error-detection field. 101111110001 → 101 111 110 001 → 5+7+6+1 = 19. Receiver recomputes and compares.نقطّع الداتا حتت بطول k ونجمعهم كأرقام؛ المجموع هو الـ checksum. المستقبل يجمع تاني ويقارن.

CRC (polynomial code)

Bit string = polynomial with 0/1 coefficients; 110001 → x⁵+x⁴+x⁰. Arithmetic modulo 2: addition = subtraction = XOR, no carries.بنتعامل مع الـ bits كأنها معادلة (كل 1 = حد في المعادلة). الحساب mod 2 يعني الجمع والطرح = XOR من غير carry.
Sender & receiver agree on G(x); its high and low bits must be 1; the frame must be longer than G.الاتنين متفقين على رقم اسمه G (المقسوم عليه)، لازم يبدأ وينتهي بـ 1، والداتا أطول منه.
Algorithm: r = degree of G → append r zeros → divide by G (mod 2) → remainder (r bits) → append it = T(x).الخطوات: r = عدد bits الـ G ناقص 1 → ضيف r أصفار على الداتا → اقسم على G بالـ XOR → الباقي (r bits) حطه مكان الأصفار. ده اللي يتبعت.
Receiver divides T(x) by G(x): remainder ≠ 0 → error (T(x)+E(x) arrives; result is E(x)/G(x)).المستقبل يقسم اللي وصله على G: لو الباقي صفر يبقى سليم، لو مش صفر يبقى فيه غلط.

Modulo 2 arithmetic examples — Slide 23 · جمع وطرح mod 2 = XOR

CRC division example — Slide 27 · G = 1001, M = 101110 → T = 101110 011

Hamming codes

Codeword n = m data bits + r check bits.الكلمة اللي تتبعت = m bits داتا + r bits فحص.
Hamming distance = number of bit positions in which two codewords differ (XOR, count 1’s).المسافة بين كلمتين = عدد الـ bits المختلفة بينهم (اعمل XOR وعدّ الـ 1).
Detect d errors → distance d+1. Correct d errors → distance 2d+1. Single parity → distance 2.عشان تكتشف d غلطة محتاج مسافة d+1، وعشان تصلّح d غلطة محتاج 2d+1. الـ parity العادية مسافتها 2 (تكتشف غلطة واحدة بس).
Correcting single errors: each of the 2ᵐ messages needs n+1 patterns → (n+1)·2ᵐ ≤ 2ⁿ → (m + r + 1) ≤ 2ʳ.عشان تصلّح غلطة واحدة، كل رسالة محتاجة n+1 شكل محجوز ليها. ده بيطلع الشرط الشهير: m + r + 1 ≤ 2ʳ. جرّب r لحد ما يتحقق.

Multiple Access Protocols — overviewslides 34–36

MID 2025 P1a

MAPs coordinate the access of multiple nodes to a shared broadcast channel (shared wire e.g. Ethernet, shared wireless, satellite).لما كذا جهاز على قناة واحدة (سلك مشترك، واي فاي، قمر صناعي)، الـ MAP هو القواعد اللي بتنظم مين يتكلم إمتى.
Broadcast problem: two or more nodes transmit at the same time → frames collide → lost → bandwidth wasted.المشكلة: لو اتنين اتكلموا في نفس اللحظة تحصل collision، الـ frames تبوظ والوقت يضيع.
Three categories: Channel partitioning (TDM, FDM, CDMA) · Random access (slotted ALOHA, CSMA) · Taking-turns (polling, token passing).3 أنواع: تقسيم القناة (بالوقت، التردد، أو الكود)، عشوائي (اتكلم وشوف)، بالدور (مدير يسأل، أو token يلف).
Ideal MAP (rate R): one node → R; M nodes → R/M each; decentralized (no master that can fail); simple and inexpensive.الـ MAP المثالي: لو واحد بس بيتكلم ياخد السرعة كلها، لو M بيتكلموا كل واحد ياخد R/M، مفيش جهاز رئيسي ممكن يبوظ، وبسيط ورخيص.

Channel Partitioning: TDM · FDM · CDMAslides 37–45

ASG2 P2,P3MID 2026 P2

TDM (R bps, N nodes): time divided into time frames, each into N slots, one slot per node.تقسيم بالوقت: الوقت متقطع time frames، وكل time frame متقسم N slots، كل جهاز له slot ثابت بيبعت فيه بس.
Advantages: avoids collision; fairness (R/N each).المميزات: مفيش collisions، والكل بياخد نصيب متساوي R/N.
Disadvantages: a node is limited to R/N even when alone; must wait for its turn → poor utilization.العيوب: لو إنت لوحدك برضو مش هتاخد غير R/N، ولازم تستنى دورك حتى لو الباقي ساكتين ← القناة بتضيع.
FDM: divides the R bps channel into N frequencies of bandwidth R/N each. Same advantages/disadvantages.تقسيم بالتردد: بدل الوقت، نقسم القناة N قنوات صغيرة كل واحدة R/N. نفس المميزات والعيوب.
CDMA: a unique code per node; nodes transmit simultaneously over the whole bandwidth; the receiver uses the sender’s code to decode.تقسيم بالكود: كل جهاز له كود مختلف، والكل بيبعت مع بعض في نفس الوقت وعلى كل التردد. المستقبل بيستخدم كود الراسل عشان يطلّع كلامه من وسط الزحمة.
Codes are mutually orthogonal (sum of bitwise products = 0).شرط الأكواد: orthogonal، يعني لو ضربت أي كودين عنصر بعنصر وجمعت يطلع صفر. ده اللي بيخلي باقي الأجهزة تتلغي عند فك الكود.
Chipping rate ≫ data rate; one bit = M mini-slots (chips). Encode Z = d·c; decode d = (1/M) Σ Z·c.كل bit داتا بتتبعت كـ M حتة صغيرة (chips). الترميز: اضرب الـ bit في الكود. الفك: اضرب اللي وصل في الكود، اجمع، واقسم على M.

TDM slide — Slide 37 · TDM: slot لكل node في كل time frame

FDM slide — Slide 39 · FDM: تردد لكل node

CDMA orthogonal codes — Slide 41 · الأكواد orthogonal

CDMA sender and receiver — Slide 44 · ترميز وفك ترميز CDMA

CDMA two senders — Slide 45 · اتنين بيبعتوا في نفس الوقت والمستقبل بيفصل بالكود

Random Access: Slotted ALOHA · CSMAslides 46–53

ASG2 P4,P5MID 2025 P2a

Random access: a node transmits at the full rate; on collision each node retransmits after an independent random delay.الفكرة: اتكلم بالسرعة كلها على طول، ولو حصل collision كل واحد يستنى وقت عشوائي مختلف ويعيد.
Slotted ALOHA set-up: frames of L bits; slots of L/R s; nodes start only at slot beginnings; nodes synchronized; collisions detected before the slot ends.الافتراضات: كل الـ frames نفس الطول L، الوقت متقسم slots طول كل واحدة = وقت frame واحدة (L/R)، الكل ساعاتهم متظبطة وبيبدأوا في أول الـ slot بس.
Protocol: new frame → wait for the next slot → send the whole frame. No collision → done. Collision → retransmit in each following slot with probability p until success.عندك frame؟ استنى أول slot جاي وابعتها كلها. وصلت؟ خلاص. حصل collision؟ في كل slot جاي ارمي عملة: باحتمال p تعيد، وإلا تسكت، لحد ما تنجح.
Advantages: a single active node transmits continuously at full rate; decentralized — but needs slot synchronization.المميزات: لو واحد بس شغال ياخد السرعة كلها، ومفيش جهاز رئيسي. بس محتاج الكل يبقى متظبط على نفس الـ slots.
Disadvantages (many active nodes): slots with collisions (wasted) and empty slots (everyone refrained).العيوب لما الأجهزة تكتر: slots بتضيع في collisions، وslots تانية بتفضى لأن الكل قرر يسكت في نفس الوقت.
CSMA: carrier sensing (listen before transmitting; busy → wait a random time and sense again) + collision detection (listen while transmitting; another node transmitting → stop).مبدأين: (1) اسمع قبل ما تتكلم؛ لو حد بيتكلم استنى وقت عشوائي واسمع تاني. (2) اسمع وإنت بتتكلم؛ لو حد تاني بيتكلم اسكت فورًا.
Collisions still happen because of propagation delay. Advantage of CD: abort shortly after detecting a collision → not transmitting a useless damaged frame in its entirety.ليه بيحصل collision رغم إننا بنسمع؟ لأن الإشارة بتاخد وقت توصل: جهاز بعيد لسه ماسمعش إنك بدأت فيبدأ هو كمان. فايدة الـ CD: بتوقف بدري بدل ما تكمل frame بايظة لآخرها.

Slotted ALOHA example — Slide 50 · C = collision, E = empty, S = success

CSMA space time diagram — Slide 52 · D بيبدأ قبل ما إشارة B توصله ← collision

CSMA with collision detection — Slide 53 · مع CD الاتنين بيوقفوا بسرعة

Taking-Turns: Polling · Token Passingslides 54–57

ASG2 P4bMID 2026 P1b

Polling: a master node tells node 1 it may transmit up to a maximum number of frames, then node 2, … (detects the end by the lack of signal); cyclic.فيه جهاز رئيسي (master) بيقول لكل جهاز بالدور "ابعت لحد كذا frame". لما الإشارة تقف يعرف إنه خلص ويروح للي بعده، ويلف تاني.
+ eliminates collisions and empty slots → high efficiency.الميزة: مفيش collisions ومفيش slots فاضية ← كفاءة عالية.
− polling delay (one active node gets less than R); master fails → whole channel inoperative.العيوب: وقت ضايع في السؤال (حتى لو واحد بس شغال، الـ master بيسأل الباقي)، ولو الـ master وقع القناة كلها تقف.
Token passing: a small frame (token) passed in a fixed order 1→2→…→N→1; a node holds it only if it has frames (sends up to a max), otherwise forwards it immediately.frame صغيرة اسمها token بتلف على الأجهزة بترتيب ثابت. اللي معاه الـ token بس يبعت (لحد كذا frame) وبعدين يمرره؛ لو ماعندوش حاجة يمرره فورًا.
+ decentralized, high efficiency.الميزة: مفيش جهاز رئيسي، وكفاءة عالية.
− one node’s failure can crash the channel; a node that doesn’t release the token → recovery procedure needed.العيوب: لو جهاز واحد باظ القناة تقف، ولو جهاز نسي يمرر الـ token لازم إجراء استرجاع.

Switched LANs: MAC Addresses & ARPslides 58–66

ASG3 P1c,d,e · P5MID 2025 P3d

Switches operate at the link layer: switch frames, don’t recognize network-layer addresses, don’t use routing algorithms.الـ switch شغال في الـ link layer: بيوجّه frames بالـ MAC، مش بيفهم IP ومش بيعمل routing.
LAN (MAC) address = the adapter’s address: permanent, burned into ROM; 6 bytes = 48 bits → 2⁴⁸ addresses; hex; unique; IEEE allocates (2²⁴ at a time, first 24 bits fixed). Broadcast = FF-FF-FF-FF-FF-FF. A node discards frames not addressed to it.الـ MAC = عنوان كارت الشبكة نفسه: ثابت ومحروق في الكارت، 48 bit مكتوب hex، مفيش كارتين بنفس العنوان (IEEE بتوزعهم). عنوان كله 1 (FF-FF-...) معناه للكل. الجهاز بيرمي أي frame مش ليه.
ARP (RFC 826) translates IP → MAC. Each node has an ARP module with an ARP table: IP address, MAC address, TTL (entry deleted after ~20 minutes).ARP بيحوّل IP لـ MAC. كل جهاز عنده جدول فيه: IP، MAC، وTTL (الصف بيتمسح بعد حوالي 20 دقيقة).
Same LAN: entry exists → use it. Else: build an ARP packet (own IP + MAC, destination IP) → broadcast → only the matching node responds → update table.عايز تبعت لجهاز على نفس الـ LAN: لو الـ MAC في الجدول استخدمه. لو لأ، ابعت سؤال للكل (broadcast) "مين صاحب الـ IP ده؟"، صاحبه بس يرد بالـ MAC، وتسجله في الجدول.
Different LAN: the router has an IP, adapter, MAC and ARP module per interface. The sender uses the MAC of the router’s LAN-1 interface → router passes the frame to its network layer → routing table → output interface → LAN-2 interface builds a new frame with the destination’s MAC.الجهاز في LAN تانية: ابعت الـ frame بـ MAC الراوتر (interface اللي ناحيتك). الراوتر يطلّع الـ IP، يبص في جدوله يعرف يخرج من أنهي interface، ويعمل frame جديدة بـ MAC الجهاز في الناحية التانية.

Switched LAN topology — Slide 59 · شبكة switches

LAN addresses — Slide 60 · كل adapter له MAC

ARP table slide — Slide 63 · ARP table: IP, MAC, TTL

Sending a packet to a node off the LAN — Slide 65 · الراوتر بين LAN1 وLAN2، لكل interface MAC وIP

Ethernet IEEE 802.3slides 67–80

ASG3 P2MID 2025 P1bMID 2026 P1c

Topologies: bus, star. Media: coax, twisted pair, fiber. 10 Mbps – 40 Gbps.الإيثرنت ممكن يبقى سلك واحد الكل عليه (bus) أو كل جهاز متوصل بنقطة مركزية (star)، على coax أو twisted pair أو fiber.
Preamble (8 B): 7 bytes 10101010 → wake up receivers and synchronize clocks; last byte 10101011 → last two bits mark the start of data. Frame end = absence of current.أول 8 bytes في الـ frame: 7 منهم 10101010 عشان يصحّوا المستقبل ويظبطوا ساعته، والتامن بينتهي بـ 11 عشان يقول "الداتا هتبدأ". نهاية الـ frame = الكهربا وقفت.
Dest / Source (6 B each): MAC addresses. Type (2 B): which network-layer protocol gets the data. Data (46–1500 B): MTU 1500 → fragment; < 46 → stuff. CRC (4 B): computed over everything except the preamble.بعدين MAC المستقبل والراسل، وType بيقول الداتا دي لبروتوكول إيه (IP مثلًا)، والداتا بين 46 و1500 byte (أكبر من 1500 تتقطع، أقل من 46 تتحشى)، وفي الآخر CRC بيتحسب على كل حاجة ما عدا الـ preamble.
Service: connectionless (no connection) and unreliable (no ACK/NACK; bad CRC → discard; the application layer handles gaps).الإيثرنت مش بيعمل اتصال قبل الإرسال، ومش بيضمن الوصول: مفيش ACK، واللي CRC بتاعها غلط بيترمي، والبرنامج هو اللي يكتشف الناقص.
Baseband: digital signal sent directly. Manchester: 1 = high→low, 0 = low→high; a transition every bit → clock synchronization.Baseband يعني الإشارة الرقمية بتتبعت زي ما هي من غير تحويل تردد. Manchester: الـ 1 = نزول في نص الـ bit، الـ 0 = طلوع. كل bit فيها حركة فساعة المستقبل بتفضل متظبطة.
CSMA/CD: sense voltage; idle → send; busy → wait; collision → abort + 48-bit jam signal.الكارت بيحس بالفولت: فاضي يبعت، مشغول يستنى، ولو حصل collision يوقف ويبعت 48 bit تشويش (jam) عشان الكل يعرف.
Exponential backoff: after the n-th collision pick K from {0…2ᵐ−1}, m = min(n,10); wait K × 512 bit times.بعد كل collision بيستنى K × 512 bit، وK رقم عشوائي من مجموعة بتكبر مع كل collision (بعد الأولى من {0,1}، بعد التانية من {0..3}...). كده الانتظار بيتأقلم مع عدد الأجهزة.
Efficiency = 1 / (1 + 5·t_prop/t_trans).الكفاءة بتقل كل ما وقت الانتشار (t_prop) يكبر بالنسبة لوقت إرسال الـ frame (t_trans).

Ethernet frame structure — Slide 69 · Preamble 8 · Dest 6 · Src 6 · Type 2 · Data 46–1500 · CRC 4

Manchester encoding — Slide 74 · Manchester

Ethernet efficiency — Slide 77 · exponential backoff + efficiency

10Base2 Ethernet — Slide 78 · 10Base2: bus, thin coax, 185 m / 30 nodes, 4 repeaters

10BaseT 100BaseT — Slide 79 · 10BaseT/100BaseT: star مع hub، 100 m

Technology	Topology	Speed	Coverage
10Base2	Bus, thin coax	10 Mbps	200 m nominal; 185 m, 30 nodes per segment; up to 4 repeaters → 925 m, 150 nodesسلك coax رفيع واحد الكل عليه بـ T connectors. كل segment 185 متر و30 جهاز، وممكن 4 repeaters يوصلوا 5 segments.
10BaseT / 100BaseT	Star (hub), twisted pair	10 / 100 Mbps	Max adapter–hub 100 m; hub disconnects jabbering adapters; 100BaseT uses 4B5Bكل جهاز متوصل بـ hub بسلك twisted pair لحد 100 متر. الـ hub بيعزل أي كارت بايظ بيتكلم على طول. 100BaseT بيستخدم ترميز 4B5B.
Gigabit 802.3z	Point-to-point or shared	1000 Mbps	Backward compatible; CSMA/CD on shared (distance restricted); full-duplex point-to-pointنفس شكل الـ frame ومتوافق مع القديم. لو مشترك يستخدم CSMA/CD بمسافات قصيرة، ولو point-to-point يبعت ويستقبل مع بعض (full-duplex).

Wireless LANs IEEE 802.11slides 81–88

ASG3 P3MID 2025 P1cMID 2026 P3a

802.11 defines the physical and MAC layers of wireless LANs. BSS = basic service set, AP = access point.802.11 هو معيار الواي فاي، بيحدد الطبقة الفيزيائية والـ MAC. الـ AP = الراوتر اللي بتتوصل بيه، والـ BSS = الـ AP مع الأجهزة اللي عليه.
Infrastructure network: hosts associated with a base station; address assignment and routing provided by the network. Ad hoc: stations group themselves, no central control.Infrastructure = فيه AP مركزي بيدي عناوين ويعمل routing. Ad hoc = الأجهزة بتتوصل ببعض مباشرة من غير AP.
MAC = CSMA/CA. Idle ≥ DIFS → may transmit. Receiver waits SIFS then sends an explicit ACK. Busy → backoff (random, doubled per collision).الواي فاي بيستخدم CSMA/CA (تجنب مش اكتشاف). تسمع القناة فاضية مدة DIFS تبعت. المستقبل يستنى مدة أقصر SIFS ويرد ACK. لو القناة مشغولة تستنى وقت عشوائي بيتضاعف مع كل collision.
SIFS < DIFS so ACK/CTS get priority over new transmissions.SIFS أقصر من DIFS عشان الرد (ACK أو CTS) يطلع قبل ما أي جهاز جديد يلحق يبدأ.
No collision detection: sending + receiving at once is costly, and collisions happen at the receiver: hidden terminal (A, C can’t hear each other → collide at B) and fading (too weak to hear each other, strong enough to interfere at B).ليه مفيش collision detection؟ لأن الجهاز اللاسلكي مش بيعرف يسمع وهو بيبعت، ولأن الـ collision بيحصل عند المستقبل مش عند الراسل: A وC مش سامعين بعض (حاجز أو بُعد) فيبعتوا مع بعض ويتخبطوا عند B.
Collision avoidance: duration field → NAV (defer time); RTS/CTS reserve the channel; CTS is heard by all stations near the receiver → solves hidden station & fading; collisions only involve the short RTS/CTS.الحل: الراسل يبعت RTS قصيرة، المستقبل يرد CTS، وكل اللي حوالين المستقبل يسمعوا الـ CTS ويسكتوا المدة المكتوبة فيها (NAV). لو حصل collision يبقى على الرسايل القصيرة بس مش على الداتا.

802.11 architecture — Slide 81 · BSS + AP

802.11 DIFS SIFS ACK — Slide 84 · DIFS → data → SIFS → ACK · NAV للباقي

Hidden terminal and fading — Slide 86 · hidden terminal & fading

RTS CTS — Slide 88 · RTS → CTS → DATA → ACK

Interconnection: Hubs · Switches · Bridgesslides 89–96

ASG3 P1a, P4ASG4 P1MID 2025 P3e

Hub: physical-layer device; repeats bits on all ports; all segments = one collision domain; extends max distance; can disconnect a malfunctioning hub.الـ hub جهاز غبي في الطبقة الفيزيائية: أي bit تدخله يكررها على كل البورتات. فكل اللي متوصل بيه بيبقى collision domain واحد. فايدته بس إنه يطوّل المسافة.
Hub limitations: same Ethernet technology everywhere; one collision domain → throughput of one segment; limits on nodes per domain, distance between hosts, number of tiers.عيوبه: الكل لازم نفس التكنولوجيا، والسرعة الكلية = سرعة segment واحد لأن الكل بيتزاحم، وفيه حدود لعدد الأجهزة والمسافة وعدد الطبقات.
Switch: layer-2; forwards and filters by destination MAC; each segment an isolated collision domain; connects different LAN technologies; no LAN size limit.الـ switch ذكي: بيبص على MAC الوجهة ويبعت على بورت واحد بس. كل بورت collision domain لوحده، ويعرف يوصل تكنولوجيات مختلفة، ومفيش حد لحجم الشبكة.
Switch table (Address | Interface | Time). Frame for A arrives on x, table says y: x = y → discard; x ≠ y → output buffer of y. Switches have no MAC address; run CSMA/CD when forwarding.جدول الـ switch: MAC ← بورت ← وقت. frame لـ A جت من بورت x والجدول بيقول A على بورت y: لو نفس البورت يرميها (A شافتها خلاص)، لو مختلف يبعتها على y. الـ switch نفسه ماعندوش MAC.
Self-learning: table initially empty; unknown destination → copies to all other interfaces; for every frame store source MAC, arrival interface, time.الجدول بيتعلم لوحده: يبدأ فاضي، وكل frame تيجي يسجل "MAC الراسل ده جه من البورت ده". لو الوجهة مش في الجدول يبعت على كل البورتات ما عدا اللي جت منه.
Spanning tree: redundant paths → frames cycle and multiply → switches run a spanning tree protocol → loop-free tree, some interfaces disabled.لو فيه أكتر من طريق بين الـ switches (عشان لو واحد باظ)، الـ frames ممكن تلف في loop وتتضاعف. الحل: الـ switches تتفق على شجرة من غير loops وتقفل البورتات الزيادة.
Full-duplex switch links: a host sends at full rate, never collides. Bridge = switch with few interfaces.الجهاز المتوصل بالـ switch مباشرة بيبعت ويستقبل مع بعض بالسرعة كلها ومفيش collisions. الـ bridge = switch صغير ببورتات قليلة.
Store-and-forward: whole frame stored first; max delay = L/R (R = inbound rate). Cut-through: start sending the front while the back arrives.نوعين switches: store-and-forward يستقبل الـ frame كلها الأول وبعدين يبعتها (أقصى تأخير = طول الـ frame ÷ سرعة اللينك الداخل). cut-through يبدأ يبعت أول الـ frame وآخرها لسه بيوصل.

Hubs multi tier — Slide 89 · hubs: collision domain واحد

Switch forwarding and filtering — Slide 92 · switch table

Spanning tree — Slide 94 · spanning tree

Switches full duplex — Slide 95 · switch high-performance, full-duplex

الخلاصة — Part 2أهم نقط البارت في سطور؛ راجعها قبل ما تقفله

2.1 DLL · framing · errors

DLL = frames over a single link · implemented in the NIC
Character count → count error = loss of sync
Byte stuffing: ESC before every FLAG / ESC in data
Bit stuffing: flag = 01111110 · stuff 0 after five 1s
Flow control: feedback-based / rate-based
Error control: seq#، timer، ACK/NACK
Detection → fiber · Correction → wireless
2D parity: corrects 1 error · detects 2
CRC: append r zeros → divide (XOR) → append remainder
Hamming: m + r + 1 ≤ 2ʳ · detect d+1 · correct 2d+1

2.2 Multiple access

Types: partitioning · random · taking turns
TDM / FDM: no collision + fair · limited to R/N even when alone
CDMA: codes orthogonal · Z = d·c · d = (1/M)ΣZ·c
Slotted ALOHA: slot = L/R · retransmit with prob. p · cons: collision + empty slots
CSMA: carrier sense + collision detection · collisions due to propagation delay
Polling: master · cons: polling delay, master fails
Token: decentralized · cons: node failure, lost token

2.3 Addresses

MAC = 48 bits, ROM, IEEE · broadcast FF-FF-FF-FF-FF-FF
ARP: IP → MAC · table = IP, MAC, TTL (20 min)
Not in table → broadcast ARP request → only the owner replies
Other LAN → send to the router’s MAC

2.4 Ethernet · WiFi · hubs/switches

Frame: 8 | 6 | 6 | 2 | 46–1500 | 4
Preamble = clock sync · not in the CRC
Service: connectionless + unreliable
Manchester: 1 ↓ · 0 ↑ → clock sync
Backoff: wait K × 512 bit times · K ∈ {0 … 2ᵐ−1} · m = min(n,10)
10Base2: bus, 185 m, 30 nodes, 4 repeaters · 10BaseT: star, hub, 100 m
802.11: CSMA/CA · SIFS < DIFS · hidden terminal + fading → RTS/CTS + NAV
Hub → one collision domain · Switch → one per port
Switch: self-learning · spanning tree vs loops · delay = L/R (inbound)

PART 3Network Layer

0/14

نصين: Data plane (الراوتر من جوه، IP، IPv6) وControl plane (إزاي نلاقي أحسن طريق: Dijkstra وDV، وبروتوكولات RIP/OSPF/BGP، وMulticast). المسألة الكبيرة في الميدترم بتيجي من الـ routing.

خريطة الجزء — العناوين وتابعة لإيه (دوس على أي عنوان يوديك له)

سلايد 1–40 ← Assignment 4 · سلايد 41–68 ← Assignment 5 · سلايد 69–94 ← Assignment 6 · سلايد 95–107 ← Assignment 7

Data Plane vs Control Planeslides 2–5

ASG4 P2

The network layer = data plane + control plane.طبقة الشبكة ليها جزئين: data plane (نقل الباكت) وcontrol plane (تحديد الطريق).
Data plane (router functions): how a datagram arriving on one of a router’s input links is forwarded to one of its output links.الـ data plane = شغل الراوتر الواحد: الباكت دخلت من بورت، تطلع من أنهي بورت؟
Control plane: how a datagram is routed among routers along an end-to-end path from source host to destination host.الـ control plane = على مستوى الشبكة كلها: الطريق من المصدر للوجهة بيمر على أنهي راوترات؟
Forwarding (switching) — data plane: the router-local action of transferring a packet from an input link interface to the appropriate output interface (a packet may also be blocked or duplicated).Forwarding = حركة محلية جوه الراوتر من الـ input للـ output المناسب (وممكن الراوتر يمنع باكت أو ينسخها على كذا لينك).
Routing — control plane: the network-wide process that determines the end-to-end paths.Routing = العملية اللي بتحسب الطرق على مستوى الشبكة كلها، وهي اللي بتملى جدول الـ forwarding.
Service model: guaranteed delivery; delivery with bounded delay; in-order delivery; guaranteed minimal bandwidth; security.الـ service model = الخدمات اللي الطبقة ممكن توعد بيها: الوصول مضمون، في وقت محدد، بالترتيب، بسرعة أدنى، وأمان. (الإنترنت الحقيقي مش بيضمن أي حاجة منهم.)

Forwarding table filled by routing algorithm — Slide 4 · الـ routing algorithm بيعمل الجدول، والجدول بيحدد الباكت تطلع من فين

Router Architecture & Input Portsslides 7–10

ASG4 P3a,c

Input ports: link termination, DLL functions, lookup and forwarding; control packets go to the routing processor. Switching fabric: connects inputs to outputs. Output ports: store and transmit. Routing processor: runs routing protocols, maintains routing tables, network management.الراوتر 4 حتت: input ports (بتستقبل وتبص في الجدول)، switching fabric (بتنقل من input لـ output)، output ports (بتخزن وتبعت)، routing processor (بيشغّل بروتوكولات الـ routing ويعمل الجداول).
Input port: line termination → data link processing → lookup, forwarding, queueing → fabric.الباكت في الـ input port: تدخل من اللينك ← تتفك من الـ frame ← يتبصلها في الجدول وتستنى في طابور ← تدخل الـ fabric.
A “shadow copy” of the routing table at each input port (updated by the routing processor) → decision made locally → decentralized switching avoids a forwarding bottleneck.كل input port معاه نسخة من الجدول عشان ياخد القرار لوحده بسرعة من غير ما يرجع للبروسيسور (اللي كان هيبقى عنق زجاجة).
Must run at line speed: a lookup takes less time than receiving a packet.لازم البحث في الجدول يخلص قبل ما الباكت اللي بعدها توصل، وإلا الطوابير تتراكم.
Routing table entries stored in a tree: each level = one bit of the destination address (0 → left, 1 → right) → lookup in N steps (N = address length).الجدول متخزن كشجرة: كل مستوى = bit من العنوان (0 شمال، 1 يمين). فالبحث عدد خطواته ثابت = طول العنوان (32)، وده سريع.

Router architecture — Slide 7 · input ports → fabric → output ports + routing processor

Router input ports — Slide 8 · input port processing

Routing table as binary tree — Slide 10 · الجدول شجرة: كل مستوى = bit

Switching Fabrics · Output Ports · Queuing · HOLslides 11–17

ASG4 P3b,d,e

Fabric	How	+ / −
Memory	Under direct CPU control; input port signals the processor by interrupt; packet copied into memory; processor finds the output and copies it to the output buffer.زي كمبيوتر عادي: الباكت تتنسخ في الميموري، البروسيسور يقرر، وينسخها للـ output.	+ simple. − every packet passes through the CPU (copied twice), one at a time.بسيط بس بطيء: كل باكت بتعدي على البروسيسور وبتتنسخ مرتين، وواحدة في المرة.
Bus	Input port sends the datagram to the output over a shared bus, no processor involvement.سلك مشترك جوه الراوتر، الـ input يبعت للـ output مباشرة من غير البروسيسور.	+ no routing processor. − one packet at a time; busy bus → queued at input; limited to bus speed.أسرع من الميموري، بس باكت واحدة في المرة على السلك، والسرعة الكلية = سرعة السلك.
Interconnection network (crossbar)	2N buses connect N inputs to N outputs; packet travels on the horizontal bus until the vertical bus of its output; free → transferred; busy → queued at input.شبكة أسلاك (N أفقي × N رأسي): الباكت تمشي أفقي لحد عمود الـ output بتاعها وتنزل فيه لو فاضي.	+ overcomes the single-bus limit; parallel transfers to different outputs. − more complex; same-output packets still queue.كذا باكت تتنقل مع بعض لو وجهاتهم مختلفة. أعقد، واللي رايحين لنفس الـ output لسه بيستنوا.

Output port: fabric → queuing / buffer management → data link processing → line termination. Fabric faster than the output link → queuing and buffer management needed.الـ output port: الباكت تيجي من الـ fabric ← تستنى في طابور ← تتلف في frame ← تطلع على اللينك. لو الـ fabric بيجيب باكتس أسرع ما اللينك بيبعت، لازم طابور وإدارة للذاكرة.
Queues grow → buffer exhausted → packet loss.لو الطابور كبر والذاكرة خلصت، الباكتس بتترمي.
n ports, Vᵢ = Vₒ, fabric Vₛ ≥ n·Vᵢ → no input queuing; output worst case: all n to the same output → n−1 queued → dropped when memory is full. Vₛ < n·Vᵢ → queuing at the input.لو الـ fabric سرعتها ≥ مجموع سرعات المداخل، مفيش طابور عند المداخل. بس لو n باكت جم مع بعض ورايحين لنفس الـ output، واحدة تطلع و n−1 يستنوا. ولو الـ fabric أبطأ، الطابور يبقى عند المداخل.
Packet scheduler: FCFS, or WFQ (weighted fair queuing — shares the link fairly among connections).مين يطلع من الطابور الأول؟ يا الأول فالأول (FCFS)، يا توزيع عادل بين الاتصالات (WFQ).
HOL blocking (crossbar + FCFS): packets at the front of two input queues want the same output → one waits; the packet behind it waits too even though its own output is free.HOL = باكت في أول طابور المدخل مستنية output مشغول، فاللي وراها واقفة معاها حتى لو الـ output بتاعها هي فاضي.

Switching via memory — Slide 11 · via memory

Switching via interconnection network — Slide 13 · crossbar

Router output ports — Slide 14 · output port

Head of line blocking — Slide 17 · HOL blocking

IP & the IPv4 Datagramslides 18–20, 27

ASG4 P5

The Internet network layer gives a connectionless datagram service: the sender encapsulates the segment in an IP datagram, writes the destination address, and drops it into the network.الـ IP من غير اتصال: الراسل يحط الـ segment جوه datagram، يكتب عليها العنوان، ويرميها في الشبكة.
Best effort: no guarantee of arrival time, order, or arrival at all.Best effort = "هحاول": مفيش ضمان توصل في وقت، ولا بالترتيب، ولا توصل أصلًا.
Two components: network protocol (addressing, datagram fields, how end systems and routers act on them) and path determination (route from origin to destination). The Internet’s network protocol = IP (IPv4, IPv6).جزئين: البروتوكول (العناوين وشكل الـ datagram) وتحديد الطريق. البروتوكول في الإنترنت هو IP بنسختيه 4 و6.
IPv4 header (typically 20 bytes): version, header length, type of service, packet length, identifier / flags / 13-bit fragmentation offset (fragmentation), TTL (decremented by 1 at every router), upper-layer protocol, header checksum, source IP, destination IP, options, data.الـ header عادة 20 byte. أهم حقوله: العنوانين، TTL (بينقص 1 في كل راوتر وبيترمي لما يوصل صفر)، وحقول الـ fragmentation (identifier, flags, offset)، وupper-layer protocol (TCP ولا UDP).

IP Addressing & Classesslides 21–30

ASG4 P4aMID 2025 P3a,b

A host has one IP address; a router has one per interface. 32 bits, dot-decimal (193.32.216.9).الجهاز له IP واحد، الراوتر له IP لكل interface. العنوان 32 bit مكتوب 4 أرقام بينهم نقط.
Two parts: network part + host part; all interfaces on LAN 1 are 223.1.1.xxx.العنوان جزئين: الأول بيحدد الشبكة، والآخر بيحدد الجهاز جوه الشبكة. كل أجهزة نفس الـ LAN بيبدأوا بنفس الجزء الأول.
Router-to-router links are networks too: 3 LANs + 3 router links = six networks.اللينك بين راوترين بيتحسب شبكة لوحده. فـ 3 LANs + 3 لينكات بين راوترات = 6 شبكات.
Classes: A 0 + 7-bit network, 24-bit host (2⁷ networks, 2²⁴ interfaces) · B 10, 16/16 (2¹⁴ networks) · C 110, 24/8 (2²¹ networks) · D 1110 multicast · E 11110 reserved.الـ classes بتحدد الجزء بتاع الشبكة طوله كام: A أول bit 0 وشبكة 8 bits (شبكات قليلة وكبيرة)، B أول 2 bits 10 وشبكة 16، C أول 3 bits 110 وشبكة 24 (شبكات كتير وصغيرة)، D للـ multicast. عدد الشبكات = 2 أس (bits الشبكة ناقص الثابتة).
Managed by ICANN; assigned by regional registries. Host part: manual configuration or DHCP.العناوين بتوزعها ICANN عن طريق هيئات إقليمية. جزء الجهاز يا الأدمن يكتبه يدوي يا سيرفر DHCP يديه تلقائي.
A → B (same LAN): extract the network part, routing table says 1 hop → same LAN → link layer delivers directly.A عايز يبعت لـ B: يطلّع جزء الشبكة من عنوان B، يبص في جدوله يلاقي 1 hop يعني على نفس الـ LAN، فيديها للـ link layer تبعتها مباشرة.
A → E (different LAN): table says 2 hops via router 223.1.1.4 → link layer sends to the router’s interface 1 → router’s table → interface 2 (1 hop) → link layer delivers to E.A عايز يبعت لـ E في LAN تانية: جدوله بيقول 2 hops عن طريق الراوتر، فيبعتها للراوتر. الراوتر يبص في جدوله يلاقي E على interface 2 ويبعتها من هناك.

IP addressing LANs — Slide 22 · network part + host part

Interconnected systems six networks — Slide 23 · 6 networks: 3 LANs + 3 لينكات بين الراوترات

IPv4 address classes — Slide 24 · classes A, B, C, D

Sending on the same LAN — Slide 28 · A → B على نفس الـ LAN (1 hop)

Sending to a different LAN — Slide 29 · A → E عن طريق الراوتر (2 hops)

“كام IP network في الـ topology؟” ← كل LAN (hosts + switch/hub) = network، وكل link بين راوترين = network. الـ switch والـ hub مابيقسموش network.

Fragmentation & Reassemblyslides 31–32

ASG4 P5

The DLL carries at most an MTU; links along a route may have different MTUs.كل لينك له حد أقصى لحجم الباكت اسمه MTU، واللينكات في الطريق ممكن يبقى لكل واحد MTU مختلف.
Datagram > MTU → the router’s network layer fragments it; only the destination reassembles.لو الـ datagram أكبر من MTU اللينك، الراوتر يقطعها حتت (fragments). اللي يجمعها تاني هو الجهاز الأخير بس، مش أي راوتر.
Sender stamps each datagram with an identification number; flag = 0 on the last fragment, 1 otherwise; offset = position of the fragment’s data.عشان الجهاز الأخير يعرف يجمع: كل الحتت ليها نفس رقم الـ identification، الـ offset بيقول الحتة دي مكانها فين في الأصل، والـ flag = 1 يعني "فيه حتت بعدي" وآخر حتة flag = 0.
Any fragment missing → the datagram is “lost” and not passed up.لو حتة واحدة ماوصلتش، الـ datagram كلها تعتبر ضايعة ومتتسلمش للـ transport.

Fragmentation example — Slide 32 · 4000 bytes, MTU 1500 → 1480 (off 0, flag 1) · 1480 (off 1480, flag 1) · 1020 (off 2960, flag 0)

IPv6 & the IPv4 → IPv6 Transitionslides 33–40

ASG4 P4b,c,d

IPv6: 128-bit addresses, 40-byte fixed header, flow labeling and priority. Header: Version · Traffic class · Flow label · Payload length · Next hdr · Hop limit · Source · Destination.IPv6 اتعمل عشان عناوين IPv4 خلصت: العنوان 128 bit، الـ header ثابت 40 byte، وفيه flow label وpriority لتمييز الباكتس.
Addresses assigned to interfaces, not nodes. Unicast (one interface) · Anycast (a set; delivered to one member, the nearest) · Multicast (a group; delivered to all). No broadcast.3 أنواع عناوين: unicast لـ interface واحد، anycast لمجموعة بس الباكت تروح لأقرب واحد فيهم، multicast لمجموعة والباكت تروح لكلهم. مفيش broadcast في IPv6.
Unicast format: 010 | registry ID | provider ID | subscriber ID | subnet ID | interface ID. Multicast format: 11111111 | FLGS | SCOP | GROUP ID.عنوان الـ unicast بيبدأ بـ 010 وبعدين الهيئة ← مزود الخدمة ← المشترك ← الشبكة الفرعية ← الـ interface. عنوان الـ multicast بيبدأ بـ 8 واحدات وبعدين flags وscope ورقم المجموعة.
Dual stack: IPv6 nodes also run IPv4; IPv4 with IPv4 nodes, IPv6 with IPv6 nodes. If either end is IPv4-only → IPv4 is used, and IPv6 fields (flow label) are lost.Dual stack = الراوتر بيفهم الاتنين. لما يقابل راوتر IPv4 بس، يحوّل الباكت لـ IPv4، والحقول اللي مش موجودة في IPv4 (زي flow label) بتضيع.
Tunneling: the IPv4 routers between two IPv6 routers form a tunnel; the IPv6 datagram is carried as the payload of an IPv4 datagram → nothing lost.Tunneling = نحط باكت الـ IPv6 كلها زي ما هي جوه باكت IPv4 وتعدي الراوترات القديمة في "نفق"، وفي الناحية التانية تتفك. مفيش حاجة بتضيع، وده الأحسن.

IPv6 unicast address format — Slide 35 · unicast format

IPv6 multicast address format — Slide 37 · multicast format

Dual stack — Slide 39 · dual stack: الـ flow label بيضيع

Tunneling — Slide 40 · tunneling: IPv6 جوه IPv4

Routing Basics & Hierarchical Routingslides 42–50

ASG5 P1a,b,cMID 2025 P1d

Optimality principle: if the best path P₀→Pₙ passes through Pᵢ, the sub-path P₀→Pᵢ is the best path to Pᵢ.لو أحسن طريق من A لـ Z بيعدي على M، يبقى الجزء من A لـ M هو كمان أحسن طريق من A لـ M.
Routing problem: find the path with the optimal cost; many variables contribute to a path cost (distance, delay, bandwidth, load, reliability, monetary cost, hop count).مشكلة الـ routing: نلاقي أرخص طريق. "التكلفة" ممكن تكون مسافة، تأخير، bandwidth، حمل، موثوقية، فلوس، أو عدد hops. (جه في ميدترم 2025: اذكر 3 متغيرات.)
Sink tree: the optimal routes from all sources to one destination form a tree rooted at the destination; routing algorithms aim to find the sink trees for all routers.لو جمعت أحسن طريق من كل الراوترات لراوتر واحد، بتطلع شجرة جذرها الراوتر ده. هدف أي routing algorithm إنه يلاقي الشجرة دي لكل راوتر.
Global (centralized): complete connectivity and cost info → link state. Decentralized: each node knows only its own links; iterative exchange with neighbors → distance vector.تصنيف 1: global = كل راوتر عارف الخريطة كلها (link state). decentralized = كل راوتر عارف لينكاته بس وبيتبادل معلومات مع جيرانه شوية بشوية (distance vector).
Static: routes change slowly, often by humans. Dynamic: change with load/topology; periodic or triggered; prone to routing loops and oscillation.تصنيف 2: static = الطرق بتتغير نادرًا وغالبًا بإيد الأدمن. dynamic = بتتغير لوحدها مع الحمل والتغييرات، بس معرضة لـ loops وتذبذب.
Hierarchical routing: routers grouped into autonomous systems (AS) for scale and administrative autonomy; intra-AS protocol inside; gateways route outside using an inter-AS protocol.الإنترنت كبير جدًا، فالراوترات متجمعة في مجموعات اسمها AS (كل شركة/مؤسسة). جوه الـ AS بروتوكول واحد (intra-AS)، والراوترات اللي على الحدود (gateways) بتكلم الـ ASs التانية ببروتوكول تاني (inter-AS).

Optimal path principle — Slide 42 · optimality principle

Routing problem graph — Slide 43 · routing problem

Hierarchical routing ASes — Slide 48 · intra-AS و inter-AS

Hierarchical routing example h1 to h2 — Slide 50 · h1 → h2: intra-AS → inter-AS → intra-AS

Link State & Dijkstraslides 51–58

ASG5 P2a,P3aMID 2025 P3cMID 2026 P3c

Initially a node knows only its directly attached neighbors; each node broadcasts its link identities and costs to all routers → every node computes the same least-cost paths.في الأول كل راوتر عارف جيرانه بس. كل واحد يعلن لينكاته وتكلفتها لكل الراوترات، فالكل يبقى عنده نفس الخريطة ويحسب نفس الطرق.
Dijkstra: least-cost paths from one node to all others; after the k-th iteration, paths to k destinations are known.Dijkstra بيحسب أرخص طريق من راوتر واحد لكل الباقي، خطوة خطوة: بعد k خطوة بيبقى عارف أرخص طريق لـ k راوتر.
c(i,j) link cost (∞ if not neighbors); λ(v) current least cost; p(v) previous node; L(v) = (λ(v), p(v)); N = nodes whose path is definitively known.الرموز: c = تكلفة اللينك (∞ لو مش جيران)، λ(v) = أرخص تكلفة لـ v لحد دلوقتي، p(v) = النود اللي قبل v في الطريق، N = النودز اللي طريقها اتأكد.
Each iteration: take the node not in N with the least λ → add it to N → for its neighbors v not in N: λ(v) = min{λ(v), λ(w) + c(w,v)}. Ties → pick arbitrarily.كل خطوة: خد أرخص نود لسه مش في N، دخّلها N، وبص على جيرانها: لو الطريق من خلالها أرخص من اللي متسجل، حدّث التكلفة والـ p. لو اتنين بنفس التكلفة اختار أي واحد.
Complexity: n + (n−1) + … = n(n+1)/2 → O(n²).في أول خطوة بتدور في n نود، بعدين n−1، وهكذا. المجموع n(n+1)/2 يعني O(n²).
Oscillations when link cost = load (c(x,y) ≠ c(y,x)): routes flip every run. Fix: routers must not run the algorithm at the same time → randomize the period.لو تكلفة اللينك = الحمل عليه، الكل يهرب من اللينك المزحوم لنفس اللينك التاني فيزحم هو، ويرجعوا تاني... تذبذب. الحل: الراوترات ماتشغلش الخوارزمية في نفس اللحظة (وقت عشوائي بينهم).

Dijkstra initialization — Slide 53 · initialization: N = {A}

Dijkstra first iteration — Slide 54 · iteration 1: add D

Dijkstra second iteration — Slide 55 · iteration 2: B و E متعادلين، اختار E

Dijkstra result — Slide 56 · النتيجة النهائية

Oscillations with link state routing — Slide 58 · oscillations

نفس مثال السلايدز في شكل جدول الامتحان: صف لكل iteration، كل خانة (التكلفة، النود اللي قبلها)، الأخضر = اللي دخل N

Distance Vectorslides 59–68

ASG5 P2b,c P3b,c P4MID 2025 P2d

DV is distributed (each node computes from its neighbors’ info and sends results back), iterative (until no more exchange), asynchronous (no lock-step).DV موزّع (كل راوتر يحسب من كلام جيرانه ويرد عليهم)، متكرر (لحد ما مفيش جديد يتبعت)، وغير متزامن (مش لازم الكل يشتغل في نفس اللحظة).
Distance table at each node: rows = destinations, columns = directly attached neighbors.كل راوتر عنده جدول: صف لكل وجهة، وعمود لكل جار مباشر. الخانة = التكلفة للوجهة دي لو مشيت عن طريق الجار ده.
λᴱ(R,M) = c(E,M) + min_w{λᴹ(R,w)}: cost from E to R via neighbor M = link cost to M + M’s best cost to R.المعادلة: تكلفتي للوجهة R عن طريق جاري M = تكلفة اللينك ليه + أرخص تكلفة هو عارفها لـ R. وأصغر رقم في الصف هو الطريق اللي هختاره.
Link cost decrease: good news travels fast (converges in a couple of updates).لما لينك يرخص، الخبر الحلو بينتشر بسرعة: كام update والجداول تثبت.
Link cost increase: bad news travels slow — X–Y goes 4 → 60; Y routes to X via Z and Z via Y → routing loop; costs climb 2 per exchange → 44 iterations → count-to-infinity.لما لينك يغلى فجأة، Y يفتكر إن الطريق لـ X عن طريق Z أرخص (بمعلومة قديمة)، وZ أصلًا كان رايح عن طريق Y ← الاتنين بيرموا على بعض (loop) والأرقام تزيد 2 كل مرة لحد ما توصل للحقيقة بعد 44 مرة. دي مشكلة count-to-infinity.
Poisoned reverse: if Z routes through Y to reach X, Z tells Y its distance to X is ∞ → loop avoided. Does not detect loops of 3 or more nodes.الحل: لو Z بيروح لـ X عن طريق Y، يقول لـ Y "مسافتي لـ X = ∞" عشان Y مايفكرش يرجع عن طريقه. بيحل الـ loop بين اتنين بس، مش بين 3 أو أكتر.

DV distance table at E — Slide 60 · جدول E: صفوف = وجهة، أعمدة = عن طريق مين

DV initial tables X Y Z — Slide 63 · الجداول الأولية

DV after first exchange — Slide 64 · بعد أول تبادل

DV link cost decrease — Slide 66 · cost decrease: good news fast

DV link cost increase count to infinity — Slide 67 · cost increase: count-to-infinity

Poisoned reverse — Slide 68 · poisoned reverse

Internet Routing: RIP · OSPF · IGRP · BGPslides 69–82

ASG5 P1d,eASG6MID 2026 P1d, P3b

Intra-AS: RIP, OSPF, IGRP. Inter-AS: BGP. Different because of Policy (control transit traffic), Scale (inter-AS handles many networks), Performance (inter-AS is policy-oriented).جوه الـ AS: RIP أو OSPF أو IGRP. بين الـ ASs: BGP. ليه مختلفين؟ السياسة (مين يعدي من شبكتي)، الحجم (بين الـ ASs شبكات كتير جدًا)، والأداء (بين الـ ASs السياسة أهم من أحسن طريق).

RIP

Distance vector; metric = hop count; max 15; tables exchanged every 30 s via response messages (≤ 25 networks each); no news for 180 s → neighbor unreachable; request message asks for a cost.RIP = distance vector بيعد hops (كل لينك = 1 مهما كانت تكلفته)، أقصى 15 hop. كل راوتر يبعت جدوله لجيرانه كل 30 ثانية (رسالة response فيها لحد 25 شبكة). لو جار سكت 180 ثانية يعتبر مات. رسالة request تسأل جار عن تكلفة معينة.
RIP routing table also has a default interface (datagrams for unlisted networks) and a loopback interface (data returned back, for debugging).في جدول RIP فيه صف default (أي وجهة مش في الجدول تطلع منه) وloopback (بيرجع الداتا لنفس الجهاز، للتجربة).
Runs as the routed process over UDP (standard socket + transport protocol).RIP برنامج عادي اسمه routed شغال في طبقة التطبيق فوق UDP.

dest	next	hops
30	C	4
1	–	1
10	–	1

Advertisement from router A

dest	next	hops
1	A	2
20	B	2
30	A	5

Router D after update: 30 was via B (7) → via A (4+1 = 5)

OSPF

Link state; flooding + Dijkstra; each router has a complete map, runs Dijkstra with itself as root; admin sets costs; periodic info to all routers.OSPF = link state: كل راوتر عنده خريطة الـ AS كلها ويعمل Dijkstra وهو الجذر. التكاليف بيحددها الأدمن. كل راوتر يبعت معلوماته لكل الراوترات دوريًا.
Features: security (authentication), multiple same-cost paths, per-TOS metrics, unicast + multicast, hierarchy.مميزاته: الرسايل متوثقة (أمان)، يقدر يستخدم كذا طريق بنفس التكلفة، تكلفة مختلفة لكل نوع traffic، بيدعم unicast وmulticast، وبيتقسم مستويات.
OSPF areas: each area runs its own OSPF; details invisible outside; area border routers route outside; the backbone area connects areas.الـ AS الكبيرة بتتقسم areas، كل area بتعمل OSPF لوحدها وتفاصيلها مش ظاهرة بره. الـ backbone area بتوصل الـ areas ببعض، والـ area border routers على الحدود.
Router types: Internal · Area border · Backbone · Boundary (talks to other ASes).4 أنواع راوترات: internal (جوه area)، area border (بين area والـ backbone)، backbone (جوه الـ backbone بس)، boundary (بيكلم ASs تانية). جه في ميدترم 2026.

IGRP

Cisco; distance vector; metrics delay, bandwidth, reliability, load weighted by admin. vs RIP: reliable transport, updates only on change, diffusing update algorithm → loop-free quickly.IGRP بتاع Cisco: distance vector زي RIP بس بمقاييس أكتر (تأخير، bandwidth، موثوقية، حمل) بأوزان من الأدمن. الفرق عن RIP: بيبعت على بروتوكول موثوق، بيبعت بس لما حاجة تتغير، وعنده خوارزمية بتتجنب الـ loops بسرعة.

BGP

Path vector — propagates the sequence of ASes, not costs; route choice = policy.BGP مش بيبعت تكلفة، بيبعت الطريق نفسه (قايمة الـ ASs). واختيار الطريق قرار سياسة من الأدمن مش حسبة.
W receiving XABCY adds WXABCY unless W is in the path (loop), it has a better path, or policy forbids an AS.لما AS يستلم طريق من جاره، يضيف نفسه في أوله ويسجله، إلا لو: هو موجود في الطريق أصلًا (loop)، أو عنده طريق أحسن، أو سياسته بتمنع المرور من AS معين.
Messages: OPEN (establish contact, authenticate, timers) · UPDATE (advertise / withdraw a path) · KEEPALIVE (alive, nothing to send; ACKs OPEN) · NOTIFICATION (error, or closing).4 رسايل: OPEN (افتح جلسة وعرّف نفسك)، UPDATE (أعلن طريق أو اسحبه)، KEEPALIVE (أنا عايش، ورد على OPEN)، NOTIFICATION (فيه غلط أو هقفل الجلسة).

RIP advertisement example — Slide 71 · RIP: D بيحدّث جدوله من إعلان A

RIP routing table — Slide 72 · default + loopback

OSPF hierarchical routing — Slide 76 · OSPF areas + backbone

OSPF router types — Slide 77 · internal / area border / backbone / boundary

ICMP · Ping · Tracerouteslides 83–84

ASG6 P1e

ICMP: hosts, routers and gateways communicate network-layer information, mostly error reporting; carried as IP payload; has a type and a code; carries the first 8 bytes of the IP packet that caused it. 0/0 echo reply · 3/0 network unreachable · 3/1 host unreachable · 3/2 protocol unreachable.ICMP = رسايل أخطاء وتشخيص بين الأجهزة والراوترات، بتتبعت جوه باكت IP. كل رسالة ليها type وcode، وبتشيل أول 8 bytes من الباكت اللي سببت المشكلة.
Ping: send type 8 code 0 (echo request) → host answers type 0 code 0.Ping بيختبر إن الجهاز شغال: تبعت echo request (8/0) ويرد echo reply (0/0).
Traceroute: datagrams with TTL = 1, 2, 3… and a timer each; the n-th expires at the n-th router → router discards it and sends an ICMP warning → source learns the RTT (timer) and the router’s name and IP (ICMP).Traceroute بيكشف الطريق: يبعت باكت TTL = 1 فتموت عند أول راوتر ويرد ICMP، بعدين TTL = 2 تموت عند التاني... من التايمر يعرف الوقت ومن رسالة ICMP يعرف اسم وIP كل راوتر.

ICMP types and codes — Slide 83 · ICMP types/codes

Multicast & IGMPslides 85–94

ASG6 P4ASG7 P1b

Multicast: one sender → multiple receivers with a single transmit operation (live lecture streaming, software upgrade). Internet multicast is not connectionless: routers keep group state.Multicast = تبعت مرة واحدة وتوصل لمجموعة (بث محاضرة، توزيع تحديث). عكس IP العادي، الراوترات هنا لازم تحتفظ بمعلومات عن المجموعة.
Multicast via unicast: separate unicast connection per receiver (duplicated at the sender). Network multicast: one packet, replicated at routers → one copy per link; needs considerable network-layer support.طريقتين: (1) via unicast: الراسل يبعت نسخة لكل مستقبل لوحده (نسخ كتير على نفس اللينكات). (2) network multicast: نسخة واحدة، والراوتر ينسخها بس لما الطريق يتفرع، فكل لينك عليه نسخة واحدة. أوفر بس محتاج دعم من الشبكة.
Address indirection: one identifier (a class D address) for the group; a copy goes to all members of the multicast group; hosts keep their unicast IPs.المجموعة ليها عنوان واحد (class D). تبعت للعنوان ده فتوصل لكل الأعضاء. كل جهاز لسه عنده IP العادي بتاعه.
IGMP: between a host and its directly attached router; host tells the router it wants to join a group. Routers coordinate via multicast routing algorithms.IGMP شغال بين الجهاز والراوتر اللي متوصل بيه بس: الجهاز بيقول "عايز أشترك في المجموعة دي". التنسيق بين الراوترات بيعمله multicast routing (الموضوع الجاي).
Messages: Membership query – general · Membership query – specific (includes the group address) · Membership report (reply, or first join; heard by all hosts on the interface) · Leave group (optional).رسايل IGMP: الراوتر يسأل "مين مشترك في أي مجموعة؟" (general) أو "مين مشترك في المجموعة دي؟" (specific). الجهاز يرد membership report (أو يبعتها لوحده أول ما يشترك)، وممكن يبعت leave لما يسيب.
Feedback suppression: the router needs only one member per group; query carries a max response time; a host waits a random time 0…max; if it hears another report for the group it discards its own.الراوتر محتاج يعرف إن فيه عضو واحد على الأقل، مش كلهم. فكل جهاز يستنى وقت عشوائي قبل ما يرد، ولو سمع جهاز تاني رد عن نفس المجموعة يلغي رده. ده بيوفر رسايل.
IGMP format: type | max resp time | checksum | multicast group address, carried in IP.شكل الرسالة: النوع، أقصى وقت رد، checksum، وعنوان المجموعة. بتتبعت جوه IP.
Service model: any host can join; the sender doesn’t add/control receivers; no control over who sends; no coordination of addresses.أي جهاز يقدر يشترك من غير إذن الراسل، وأي حد يقدر يبعت للمجموعة (حتى لو مؤذي)، ومفيش تنسيق في العناوين فممكن مجموعتين ياخدوا نفس العنوان.

Multicast via unicast — Slide 86 · multicast via unicast

Network multicast — Slide 87 · network multicast: نسخة واحدة على كل لينك

Multicast addressing — Slide 89 · class D group address

IGMP protocol — Slide 90 · IGMP بين الجهاز والراوتر

IGMP message format — Slide 93 · IGMP format

Multicast Routingslides 95–107

ASG7MID 2025 P1e (RPF)MID 2026 P3d

Goal: a tree of links connecting all routers with group hosts (may include routers without group hosts).الهدف: شجرة لينكات توصل كل الراوترات اللي عندها أعضاء في المجموعة. ممكن الشجرة تعدي على راوترات ماعندهاش أعضاء.
Group-shared tree: one tree for all senders, links bi-directional. Source-based trees: one tree per sender.نوعين شجر: group-shared = شجرة واحدة الكل يبعت عليها (في الاتجاهين). source-based = شجرة مختلفة لكل راسل.
Steiner tree: minimum-cost tree (minimum sum of link costs) — NP-complete; approximations need all link info and re-run on cost changes.أحسن group-shared tree هي اللي مجموع لينكاتها أقل (Steiner tree)، بس حسابها صعب جدًا (NP-complete)، فبنستخدم تقريبات محتاجة معلومات عن كل اللينكات وتتعاد لما التكاليف تتغير.
Center-based: pick a center; routers send unicast join messages toward it; a join stops at the first router on the tree; its path becomes a branch.الطريقة العملية: نختار راوتر مركز. كل راوتر عايز يشترك يبعت join ناحية المركز بأقصر طريق unicast. الـ join توقف عند أول راوتر موجود في الشجرة، والطريق اللي مشيته يبقى فرع جديد.
Least unicast-cost tree (source-based): Dijkstra from the source; union of least-cost paths. Not the Steiner tree: it minimizes the cost from the source to each destination; Steiner minimizes the sum.للـ source-based: اعمل Dijkstra من الراسل، واتحاد أقصر الطرق = الشجرة. دي مش Steiner: دي بتقلل تكلفة الوصول لكل راوتر لوحده، Steiner بتقلل مجموع اللينكات.
RPF: a router forwards a packet on all other links only if it arrived on the link of its shortest path back to the source; otherwise discards. Routers forward even without group hosts → unwanted packets.RPF = قاعدة بسيطة: الراوتر يسأل "الباكت دي جت من اللينك اللي على أقصر طريقي للراسل؟" لو أيوه يبعتها على كل اللينكات التانية، لو لأ يرميها. العيب: راوترات ماعندهاش أعضاء بتستلم باكتس مالهاش لازمة.
Pruning: a router with no group hosts sends a prune upstream; a router that gets prunes from each downstream router prunes too. Rejoin: unprune or time-out.الحل: الراوتر اللي ماعندوش أعضاء يبعت prune ("ماتبعتليش") للراوتر اللي فوقه. لو راوتر كل اللي تحته بعتوا prune وهو كمان ماعندوش أعضاء، يبعت prune هو كمان. عشان يرجع يشترك يبعت unprune أو يستنى الـ prune ينتهي وقته.
Tunneling builds a virtual multicast network over mixed routers.معظم راوترات الإنترنت مش بتدعم multicast، فالراوترات اللي بتدعمه بتعمل "أنفاق" بينها فوق الشبكة العادية.
DVMRP: source-based, RPF + pruning + grafting. MOSPF: OSPF ASes, pre-pruned source trees. CBT: group-shared, one core. PIM: unicast-independent; dense & sparse modes. BGMP: inter-AS, group-shared; center may be in an AS without members = third-party dependency.البروتوكولات: DVMRP وMOSPF شجر source-based (الأول بـ RPF والتاني فوق OSPF)، CBT شجرة مشتركة بمركز واحد، PIM مش معتمد على بروتوكول unicast معين وله وضعين (dense لما الأعضاء كتير، sparse لما قليلين ومتفرقين)، BGMP بين الـ ASs بشجرة مشتركة وعيبه إن المركز ممكن يقع في AS ماعندهاش أعضاء (third-party dependency).

Multicast routing tree of links — Slide 95 · tree of links

Group shared tree — Slide 96 · group-shared tree

Source based trees — Slide 97 · source-based trees

Center based approach example — Slide 100 · center-based: E center

Least unicast cost tree — Slide 101 · least unicast-cost tree from A

Multicast tunneling — Slide 105 · tunneling

الخلاصة — Part 3أهم نقط البارت في سطور؛ راجعها قبل ما تقفله

Data plane · router

Forwarding = router-local · Routing = network-wide
Router: input ports · fabric · output ports · routing processor
Shadow copy at each input port · table stored as a binary tree
Fabrics: memory (slow, via CPU) · bus (one at a time) · crossbar (2N buses)
Queuing: output (same destination port) · input (Vs < n·Vi) · HOL

IP · IPv6

IP: connectionless, best effort · TTL −1 at every router
Classes: A 2⁷ · B 2¹⁴ · C 2²¹ · D multicast
Each LAN + each router–router link = one IP network
Fragmentation: routers split, only destination reassembles · same ID · offset · last flag = 0
IPv6: 128 bits, 40-byte header · unicast / anycast / multicast · no broadcast
Dual stack → flow label lost · Tunneling → IPv6 inside IPv4

Routing algorithms

Sink tree: best routes to one destination form a tree
Global = link state · decentralized = distance vector
Static vs dynamic · AS: intra-AS / inter-AS, gateways
Dijkstra: N، λ، p · O(n²) · oscillation → randomize
DV: λᴱ(R,M) = c(E,M) + min λᴹ(R,w)
Cost ↑ → count-to-infinity → fix: poisoned reverse (fails for loops of 3+)

Protocols · multicast

RIP: DV, hop count, max 15, every 30 s, dead after 180 s, over UDP
OSPF: LS + Dijkstra · security · areas · internal / area border / backbone / boundary
IGRP: several metrics · updates only on change · loop-free
BGP: path vector، policy · OPEN / UPDATE / KEEPALIVE / NOTIFICATION
ICMP: ping 8/0 → reply 0/0 · traceroute via increasing TTL
IGMP: query / report / leave · feedback suppression
Trees: Steiner (NP-complete) · center-based (join) · least unicast-cost · RPF + pruning
DVMRP، MOSPF = source · CBT = shared · PIM dense/sparse · BGMP third-party

ASSIGNMENT 1 · PARTS 1 & 2Intro, Framing & Error Detection

0/5

حاول تجاوب في دماغك (أو على ورقة) الأول، وبعدين افتح الإجابة. علّم على المسألة لما تبقى فاهمها.

Problem 1 — Part 1 theory

السؤال الأصلي

(a)What are the types of computing devices?

الإجابة

Traditional devices: computers, smartphones, tablets. Non-traditional devices: TVs, home security systems, home appliances, watches, cars. All of them are called hosts or end systems.يعني: أي جهاز على الشبكة اسمه host، سواء كمبيوتر وموبايل (تقليدي) أو تلفزيون وساعة وعربية (غير تقليدي).

(b)Difference between a distributed system and a network? How are they related?

الإجابة

Distributed system: a collection of nodes that appears to users as a single system; users are unaware of the underlying structure. Network: users have to specify the location of resources. Relation: a distributed system is a software system built on top of a network (e.g. the WWW runs on top of the Internet).يعني: الـ distributed system بيخبي التفاصيل عنك وشايفه جهاز واحد، الـ network لازم تقول الحاجة فين، والأول برنامج شغال فوق التاني.

(c)Describe transmission types in networks.

الإجابة

Broadcast: a single channel shared by all nodes; data sent as packets; supports unicast, multicast and broadcast; the intended recipient(s) are encoded in the address field. Point-to-point: many connections between individual pairs of nodes; a packet may go through intermediate nodes; there could be multiple routes.يعني: broadcast = قناة واحدة للكل والعنوان في الباكت. point-to-point = لينكات بين كل اتنين وممكن تعدي على أجهزة في النص.

(d)What is the purpose of protocols, and what are the general functions they perform? MID 2026

الإجابة

سؤال حفظ. الإجابة = الجملة اللي في Part 1: الـ protocol بيحدد format + order + actions. اكتب الكلمات التلاتة دول بالذات.

Purpose: every activity that involves two or more communicating nodes is governed by a protocol; protocols are how corresponding layers at different nodes communicate. Functions: a protocol defines the format and the order of messages exchanged between nodes, and the actions taken on the transmission and/or receipt of a message.يعني: الـ protocol هو الاتفاق اللي بيحكم أي تواصل، وبيحدد شكل الرسالة وترتيبها والأكشن عند الإرسال والاستقبال.

(e)Difference between circuit switching and packet switching?

الإجابة

Circuit switching (e.g. landline phones): dedicated links are established between the communicating nodes; idle periods waste resources → poor utilization. Packet switching: no dedicated links; data sent in small packets; different nodes use the same links at the same time → efficient utilization.يعني: circuit = خط محجوز حتى لو ساكت (ضياع). packet = الداتا حتت والكل بيشارك اللينكات (كفاءة).

Problem 2 — Layering

السؤال الأصلي

(a)Describe the layering architecture; what is its advantage?

الإجابة

Networks are organized as a stack of layers; each layer provides services to the layer above it; adjacent layers at the same node are connected by an interface; only corresponding layers at different nodes communicate, using protocols. Advantage: reduces design complexity.يعني: طبقات فوق بعض، كل طبقة بتخدم اللي فوقها، interface جوه الجهاز وprotocol بين الجهازين، والفايدة تبسيط التصميم.

(b)Relationship and communication between (i) layers at the same node, (ii) layers at two different nodes.

الإجابة

(i) Same node: each adjacent pair of layers is connected by an interface; the lower layer provides services to the upper layer. (ii) Different nodes: only corresponding (peer) layers communicate, using protocols; non-corresponding layers do not communicate.يعني: في نفس الجهاز الطبقتين بيتكلموا عبر interface، وبين جهازين نفس الطبقة بس بتتكلم عبر protocol.

(c)Main functions of the physical layer?

الإجابة

Transmits raw bits over a communication channel: voltage levels for bits, duration of each bit, network connector type and shape, connection initiation and disconnection.يعني: الطبقة الفيزيائية بتبعت الـ bits الخام: الفولت، مدة الـ bit، شكل الفيشة، وبدء وقطع الاتصال.

(d)Outline how encapsulation is done as data moves between layers at A and B.

الإجابة

ارسم الجهازين A و B وبينهم switch و router. في A اكتب M، وبعدين Ht M، وبعدين Hn Ht M، وبعدين Hl Hn Ht M. في B اعكس. وقول إن الـ switch بيفتح لحد Link والـ router لحد Network.

At A: application message M → transport adds header Ht (segment) → network adds Hn (datagram) → link adds Hl (frame) → physical sends the bits. Intermediate devices: a switch processes up to the link layer, a router up to the network layer. At B the reverse: each layer removes its header (Hl, Hn, Ht) and passes the rest up until M reaches the application. (Draw the encapsulation figure from Part 1.)

Problem 3 — Link layer

السؤال الأصلي

(a)Where is the link layer implemented?

الإجابة

On a chip called the network adapter, also known as the network interface controller (NIC). Much of the link-layer controller’s functionality is implemented in hardware.يعني: في كارت الشبكة (NIC)، وأغلبها hardware.

(b)Draw a block diagram of the network adapter, host components and protocol stack.

الإجابة

Draw the “Host” box: CPU and Memory on the motherboard bus; the network adapter (Controller + Physical transmission) hangs off the bus and connects to the link. Application/Transport/Network/Link run on the host CPU; Link/Physical are implemented in the adapter. Same figure as Part 2 → DLL basics.

يعني: ارسم الـ host (CPU + Memory على الـ bus) والكارت متوصل بالـ bus وفيه controller وphysical transmission.

(c)(i) Why is flow control needed? (ii) Two types.

الإجابة

(i) Communicating nodes may operate at different speeds and have limited buffering; flow control prevents the sender from overwhelming the receiver. (ii) Feedback-based: the receiver sends back information giving the sender permission to send more or telling it how it is doing. Rate-based: a built-in mechanism limits the sending rate without feedback from the receiver.يعني: عشان الراسل السريع مايغرّقش المستقبل البطيء. نوعين: المستقبل يبعت feedback، أو سرعة محدودة من الأول.

(d)Error detection vs error correction; when is each used?

الإجابة

Detection: enough redundancy to know an error occurred (not where) → the receiver requests retransmission; used on highly reliable channels such as fiber. Correction: enough redundancy to find the error locations and correct them; used on channels with many errors such as wireless links.يعني: detection = نعرف إن فيه غلط ونطلب إعادة (للفايبر النضيف). correction = نصلّح بنفسنا (للـ wireless اللي فيه أخطاء كتير).

Problem 4 — Framing & checksum

السؤال الأصلي

A = 01111101 · B = 11110011 · FLAG = 00111100 · ESC = 11111000 · Frame: [B ESC ESC FLAG A B FLAG]

(a-i)Character count

الإجابة

عدّ الحروف في الـ frame (7) وزوّد 1 للعدّاد نفسه = 8. حط الرقم في الأول.

[8] B ESC ESC FLAG A B FLAG

Added: one count character = 8 (7 characters + the count itself) → 00001000.

(a-ii)Flag bytes with byte stuffing

الإجابة

حط FLAG في الأول والآخر. امشي على الداتا: أي ESC أو FLAG جواها حط قبله ESC. علّم على اللي زودته.

FLAG B ESC ESC ESC ESC ESC FLAG A B ESC FLAG FLAG

Added: start/end FLAG, and one ESC before every ESC or FLAG inside the data.

(a-iii)Starting and ending flags with bit stuffing

الإجابة

حوّل كل حرف لـ bits وحطهم ورا بعض (من غير الـ FLAGs اللي في الأطراف). امشي من الشمال وعدّ الـ 1 المتتالية؛ أول ما يبقوا 5 حط 0 وصفّر العدّاد (أي 0 بيصفّر العدّاد). العدّ بيكمل من حرف للي بعده. في الآخر حط 01111110 في الأول والآخر.

char	bits	sent
B	11110011	11110011
ESC	11111000	111011000
ESC	11111000	111110000
FLAG	00111100	00111100
A	01111101	011111001
B	11110011	111100011
FLAG	00111100	00111100

01111110 11110011 111011000 111110000 00111100 011111001 111100011 00111100 01111110

ركز: الـ 1 اللي في آخر B بتتحسب مع أول ESC (11 + 111 = خمسة) فالـ 0 بيتحط بعد تالت bit في الـ ESC. ونفس الحكاية بين A و B.

(b)4-bit checksum of [11011001 11100101]

الإجابة

قطّع الـ bits كل 4 مع بعض، حوّل كل حتة لرقم، واجمع. اكتب الناتج بالعشري والـ binary.

1101 + 1001 + 1110 + 0101 = 13 + 9 + 14 + 5 = 41 = 101001

The receiver recomputes the sum over the received data and compares it with the checksum in the packet.

Problem 5 — 2D parity (odd)

السؤال الأصلي

Data: 11000011 11011001 · odd parity · 4×4

(a)Checksum field for 4×4 two-dimensional parity

الإجابة

رتّب الـ 16 bit في 4 صفوف × 4 أعمدة. لكل صف: parity bit يخلي عدد الـ 1 فردي (odd). نفس الحاجة لكل عمود. وخانة الركن parity لصف الـ parities.

1	1	0	0	1
0	0	1	1	1
1	1	0	1	0
1	0	0	1	1
0	1	0	0	0

Row parity = 1 1 0 1, column parity = 0 1 0 0, corner = 0. Each row/column (with its parity bit) has an odd number of 1’s.

(b)Example: 2D parity detects and corrects a single-bit error

الإجابة

اقلب bit واحدة. الصف بتاعها هيبقى غلط والعمود بتاعها هيبقى غلط ← تقاطعهم هو مكان الغلطة.

Flip the bit in row 2, column 3 (1 → 0). Row 2 now has an even number of 1’s (parity error) and column 3 too. Their intersection gives the exact location → flip it back = corrected.

(c)Counter-example: a double-bit error can’t always be corrected

الإجابة

اقلب اتنين في نفس الصف: الصف هيبان صح (اتنين غلط بيلغوا بعض) بس عمودين غلط. عارف الأعمدة مش عارف الصف ← مش هتعرف تصلّح.

Flip two bits in the same row, e.g. row 1 columns 1 and 2 (11 → 00). Row 1 parity still checks (two changes), but columns 1 and 2 fail. We know the columns but not the row → cannot correct. (Or two errors in different rows and columns: rows 1,3 and columns 1,2 fail → two possible pairs → ambiguous.)

(d)Example: some double-bit errors can be detected

الإجابة

In the example in (c), columns 1 and 2 show parity errors → the receiver knows the data is wrong (detected) and requests retransmission, even though it can’t correct it.

ASSIGNMENT 2 · PART 2CRC, Hamming & MAC Protocols

0/5

Problem 1 — CRC & Hamming

السؤال الأصلي

(a)G = 11001, frame = 1110011001. Remainder and transmitted data?

الإجابة

r = عدد bits الـ G − 1 = 4. ضيف 4 أصفار على الـ frame. اقسم قسمة طويلة بـ XOR (كل خطوة: لو أول bit = 1 اعمل XOR مع G، لو 0 اعمل XOR مع أصفار). آخر 4 bits = الباقي. الـ transmitted = الـ frame الأصلي + الباقي.

r = 4 → append 4 zeros: 1110011001 0000 ÷ 11001 (mod-2).

Remainder = 1000 · Transmitted = 1110011001 1000

(b)Hamming: limit on check bits r to correct one error for (i) 33 and (ii) 63 message bits.

الإجابة

المعادلة (m + r + 1) ≤ 2ʳ. جرّب r = 5، 6، 7 ... لحد ما تتحقق. اكتب المحاولة اللي فشلت واللي نجحت.

Each of the 2ᵐ legal messages needs n+1 bit patterns (itself + n one-bit errors): (n+1)·2ᵐ ≤ 2ⁿ → (m + r + 1) ≤ 2ʳ.

(i) m = 33: r = 5 → 39 ≤ 32 ✗ · r = 6 → 40 ≤ 64 ✓ → r = 6
(ii) m = 63: r = 6 → 70 ≤ 64 ✗ · r = 7 → 71 ≤ 128 ✓ → r = 7

Problem 2 — TDM · Slotted ALOHA · FDM · CDMA

MID 2026 P2 · MID 2021 P2

السؤال الأصلي

3 nodes share a channel. Node 1: 1 frame, node 2: 8 frames, node 3: 3 frames. Frame = 25 bits. R = 150 bit/s. → one frame takes 25/150 = 1/6 s.

(a)Slot size using (i) TDM with 1 s time frame, (ii) slotted ALOHA

الإجابة

احسب وقت الـ frame الواحدة = L / R. في TDM الـ slot = الـ time frame ÷ عدد الـ nodes. في slotted ALOHA الـ slot = وقت frame واحدة.

(i) TDM: the 1 s time frame is divided into N = 3 slots → slot = 1/3 s (= 50 bits = 2 frames per slot).

(ii) Slotted ALOHA: slot = time to transmit one frame = L/R = 25/150 = 1/6 s.

(b)How frames are transmitted with (i) TDM 1 s, (ii) FDM, (iii) schematic

الإجابة

TDM: اعرف الـ slot فيه كام frame (slot ÷ وقت الـ frame)، وارسم time frames ورا بعض وكل node بيبعت في slot بتاعه بس. FDM: السرعة ÷ عدد الـ nodes = سرعة كل واحد، والكل بيبعت مع بعض بس أبطأ.

(i) TDM: each time frame = [node1 | node2 | node3], 1/3 s each; in its slot a node sends up to 2 frames at the full 150 bps. Node 1 is done in the first slot; node 3 needs 2 time frames; node 2 needs 4 time frames. Empty slots are wasted.

TDM, 1 s time frame — each square = one 25-bit frame (1/6 s)

(ii) FDM: the channel is split into 3 frequency bands of 150/3 = 50 bps; every node transmits continuously on its own band; one frame takes 25/50 = 0.5 s.

FDM — three 50 bps channels in parallel

(c)Time for each node’s frames: (i) TDM 1 s, (ii) TDM 2 s, (iii) FDM, (iv) CDMA

الإجابة

TDM: عدد الـ time frames الكاملة × T + مكان الـ slot بتاعه في آخر time frame + عدد الـ frames في آخر slot × وقت الـ frame. FDM: عدد frames × (L ÷ (R/N)). CDMA: عدد frames × (L ÷ R) لأنه بياخد السرعة كلها.

	Node 1 (1 frame)	Node 2 (8 frames)	Node 3 (3 frames)
(i) TDM 1 s — slot 1/3 s, 2 frames/slot	1/6 s	3 + 1/3 + 2/6 = 3⅔ s	1 + 2/3 + 1/6 = 1⅚ s
(ii) TDM 2 s — slot 2/3 s, 4 frames/slot	1/6 s	2 + 2/3 + 4/6 = 3⅓ s	4/3 + 3/6 = 1⅚ s
(iii) FDM — 50 bps each	0.5 s	8 × 0.5 = 4 s	3 × 0.5 = 1.5 s
(iv) CDMA — whole bandwidth, simultaneously	25/150 = 1/6 s	200/150 = 4/3 s	75/150 = 1/2 s

طريقة الحل: اعرف الـ slot فيه كام frame، وبعدين شوف آخر frame للنود هيتبعت في أنهي time frame وفي أنهي slot. مثال node 2 في (i): 8 frames ÷ 2 لكل slot = 4 time frames، آخر slot ليها بيبدأ عند 3 + 1/3 ويخلص بعد 2/6 ← 3⅔ s.

★Mid 2026 version (Nov 2025): node 1 = 1, node 2 = 3, node 3 = 5 frames; 20 bits; 60 bit/s

الإجابة

نفس الخطوات بالظبط بالأرقام الجديدة: frame = 20/60 = 1/3 s.

One frame = 20/60 = 1/3 s. Slotted ALOHA slot = 1/3 s. TDM 1 s: slot 1/3 s = 1 frame. TDM 2 s: slot 2/3 s = 2 frames.

	Node 1	Node 2	Node 3
TDM 1 s	1/3 s	2 + 2/3 = 2⅔ s	4 + 1 = 5 s
TDM 2 s	1/3 s	2 + 2/3 + 1/3 = 3 s	4 + 4/3 + 1/3 = 5⅔ s
FDM (20 bps each)	1 s	3 s	5 s
CDMA (60 bps)	1/3 s	1 s	5/3 s

Problem 3 — CDMA

السؤال الأصلي

(a)Are [−1 −1 1 1 −1 −1 1 1] and [1 −1 1 1 −1 1 −1 1] mutually orthogonal?

الإجابة

اضرب كل عنصر في اللي قصاده واجمع. لو الناتج 0 يبقى orthogonal، غير كده لأ.

(−1)(1) + (−1)(−1) + (1)(1) + (1)(1) + (−1)(−1) + (−1)(1) + (1)(−1) + (1)(1)
= −1 + 1 + 1 + 1 + 1 − 1 − 1 + 1 = 2 ≠ 0

Not orthogonal: the sum of the bit-wise products must be 0.

(b)Codes c₁ = (1, 1, −1, −1), c₂ = (−1, 1, −1, 1); 4 chips; each data bit uses three code periods. Sender 1 sends (−1, −1), sender 2 sends (1, −1).

الإجابة

(i)(ii) لكل bit: اضرب قيمة الـ bit في الكود كله، وكرر 3 مرات. (iii) اجمع خرج الاتنين chip بـ chip = القناة. عشان تفك sender 2: اضرب القناة في كود 2، اجمع، واقسم على عدد الـ chips.

Check: c₁·c₂ = −1 + 1 + 1 − 1 = 0 ✓ orthogonal. Encode Z = d × code, repeated 3 times per bit (12 chips per bit).

(i)  Sender 1:  bit −1 → (−1,−1, 1, 1)×3     bit −1 → (−1,−1, 1, 1)×3
(ii) Sender 2:  bit  1 → (−1, 1,−1, 1)×3     bit −1 → ( 1,−1, 1,−1)×3
     Channel (sum): bit 1 → (−2, 0, 0, 2)×3   bit 2 → ( 0,−2, 2, 0)×3
(iii) Receiver for sender 2 (multiply by c₂ and add, divide by M = 12):
     bit 1: 3 × [(−2)(−1) + 0 + 0 + (2)(1)] / 12 = 3 × 4 / 12 = +1
     bit 2: 3 × [0 + (−2)(1) + (2)(−1) + 0] / 12 = 3 × (−4) / 12 = −1
     → sender 2 data = (1, −1) ✓   (same with c₁ gives (−1, −1))

لو الدكتورة قاصدة إن كل bit بياخد code واحد بس (4 chips)، نفس الخطوات من غير التكرار × 3 والقسمة على 4، والنتيجة واحدة.

Problem 4 — CSMA, polling, token, ALOHA

السؤال الأصلي

(a)Two principles of CSMA

الإجابة

سؤال حفظ: carrier sensing (اسمع قبل) + collision detection (اسمع أثناء).

Carrier sensing: a node listens to the channel before transmitting; if another frame is being transmitted it waits a random time and senses again; if idle it begins transmission. Collision detection: a node listens while transmitting; if it detects another node transmitting, it stops and uses some protocol to decide when to try again.يعني: اسمع قبل ما تبعت، واسمع وإنت بتبعت ولو حد تاني بيبعت اسكت.

(b)Advantages and disadvantages of (i) polling, (ii) token passing

الإجابة

سؤال حفظ من السلايدز 54–57: لكل واحد ميزة وعيبين.

(i) Polling — advantage: eliminates collisions and empty slots → much higher efficiency. Disadvantages: polling delay (if only one node is active it transmits at less than R because the master polls the inactive nodes in turn); if the master node fails the whole channel becomes inoperative. (ii) Token passing — advantages: decentralized, high efficiency. Disadvantages: failure of one node can crash the entire channel; if a node neglects to release the token a recovery procedure is needed.يعني: polling مفيش collisions بس فيه وقت ضايع في السؤال ولو الـ master وقع الكل يقف. token مفيش master وكفاءة عالية بس جهاز واحد بايظ أو token ضايع يوقف الكل.

(c)(i) Explain slotted ALOHA. (ii) Sketch its disadvantages with 4 nodes.

الإجابة

ارسم 4 صفوف (nodes) × slots. في slot 1 خلي الكل يبعت = C. بعدها بعض الـ slots فاضية (E) وبعضها فيها واحد بس (S). اكتب تحت كل slot C/E/S.

(i) Frames of L bits, slots of L/R s, nodes synchronized and start only at slot beginnings. A node with a new frame waits for the next slot and sends the whole frame. No collision → done. Collision (detected before the slot ends) → retransmit in each later slot with probability p until it succeeds.

(ii) C = collision (wasted), E = empty (everyone backed off), S = success

يعني: استنى أول slot وابعت الـ frame كلها، لو collision أعد في كل slot جاي باحتمال p. العيب: slots بتضيع في collisions وslots فاضية.

Problem 5 — CSMA space–time

السؤال الأصلي

4 nodes, frame = 50 bits, R = 300 bit/s → t_trans = 50/300 = 1/6 s ≈ 166.7 ms. Delays: 2↔3 = 200 ms, 2↔4 = 210 ms, 1↔3 = 210 ms → on the bus: 1 —10— 2 ——200—— 3 —10— 4. Node 2 → node 4 at 10, 410, 810 ms; node 3 → node 1 at 510 ms.

(a)How do nodes 2 and 3 use CSMA?

الإجابة

احسب وقت الـ frame (L/R). ارسم خط زمن لكل node. في كل لحظة إرسال اسأل: الإشارة اللي بتتبعت دلوقتي وصلت للـ node ده ولا لسه؟ (أضف propagation delay). لو لسه ماوصلتش هيشوف القناة فاضية ويبعت ← collision.

t = 10: node 2 senses idle → sends frame 1 (10 → 176.7 ms). It reaches node 3 at 210 and node 4 at 220–386.7 ms → delivered.
t = 410: node 2 senses idle (frame 1 has passed) → sends frame 2 (410 → 576.7). Its first bit reaches node 3 at 610, node 4 at 620.
t = 510: node 3 senses the channel; node 2’s signal hasn’t reached it yet (propagation delay) → it “thinks” the channel is idle → starts sending to node 1.
t = 610: node 3 detects node 2’s signal while transmitting → collision detected → aborts shortly after and backs off a random time.
Node 2 finished at 576.7, before node 3’s signal reaches it (710) → node 2 does not detect the collision. Node 3’s signal reaches node 4 from 520 until ≈ 620+, overlapping the start of frame 2 → frame 2 is damaged at node 4.
t = 810: node 2 senses; node 3’s aborted signal is passing node 2 (≈ 710–815) → busy → node 2 waits a random time and senses again, then sends frame 3 when idle. Node 3 retransmits after its random backoff when it senses the channel idle.

(b)Space vs time diagram

الإجابة

المحور الأفقي = مكان الـ nodes على السلك (بالمسافة/التأخير بينهم)، الرأسي = الزمن. كل إرسال = مستطيل مايل: بيبدأ عند الـ node وبيميل بالـ propagation delay، وعرضه = وقت الـ frame.

x = position on the bus (propagation delay), y = time (0.3 px per ms)

ASSIGNMENT 3 · PART 2Switches, Ethernet & 802.11

0/5

Problem 1 — Switches, LAN, MAC, ARP

السؤال الأصلي

(a)Describe the connection and operation of a switch.

الإجابة

A switch is a layer-2 device: hosts/LAN segments connect to its interfaces (often full-duplex links). It forwards and filters frames using the destination MAC address and its switch table: frame for A arrives on interface x, table says A is on y → x = y discard, x ≠ y put in the output buffer of y; unknown destination → copies to all other interfaces. The table is built automatically (source MAC, arrival interface, time). Each segment is a separate collision domain; it can connect different LAN technologies; it doesn’t recognize network-layer addresses or run routing algorithms; it uses store-and-forward or cut-through.يعني: الأجهزة متوصلة ببورتات الـ switch، وهو بيبص على MAC الوجهة في جدوله ويبعت على البورت الصح بس (أو على الكل لو مش عارف)، وبيتعلم الجدول لوحده.

(b)Difference between a LAN and a subnet?

الإجابة

A LAN is a link-layer concept: nodes connected by hubs/switches that reach each other using MAC addresses, without a router. A subnet is a network-layer concept: a set of interfaces sharing the same network part of the IP address (e.g. 223.1.1.xxx), reachable without passing through a router. A router separates subnets; one switched LAN normally forms one subnet.يعني: الـ LAN فكرة من الـ link layer (أجهزة بتوصل لبعض بالـ MAC من غير راوتر). الـ subnet فكرة من الـ network layer (أجهزة بنفس جزء الشبكة في الـ IP). الراوتر هو اللي بيفصل subnets.

(c)What is the LAN (MAC) address?

الإجابة

The data-link address of a network adapter: permanent, burned into the adapter’s ROM during manufacturing (physical / medium access control address); 6 bytes (48 bits) → 2⁴⁸ addresses, written in hex (e.g. 1A-23-F9-CD-06-9B); no two adapters have the same address; IEEE manages allocation. Broadcast = FF-FF-FF-FF-FF-FF.يعني: عنوان الكارت نفسه، 48 bit ثابت ومحروق فيه، فريد، وبتوزعه IEEE.

(d)Function of ARP?

الإجابة

ARP (RFC 826) translates between an IP address and a MAC address: the DLL receives a packet from the network layer with an IP destination and uses ARP to find the corresponding MAC address. If not in the table: build an ARP packet (own IP and MAC + destination IP), broadcast it, only the node with that IP responds, update the table.يعني: ARP بيحوّل IP لـ MAC: يبص في الجدول، لو مش موجود يسأل الكل بالـ broadcast وصاحب الـ IP يرد.

(e)What is the ARP table and its entries?

الإجابة

A table in each node’s ARP module that maps IP ↔ MAC addresses. Entries: IP address, MAC (LAN) address, and TTL (when the entry will be deleted; typically 20 minutes).يعني: جدول في كل جهاز فيه IP ← MAC ← TTL (وقت انتهاء الصف، حوالي 20 دقيقة).

Problem 2 — Ethernet

MID 2026 P1c

السؤال الأصلي

(a)Advantage of adding collision detection to CSMA?

الإجابة

Nodes abort their transmission a short time after detecting a collision → they don’t keep transmitting a useless, damaged frame in its entirety → better performance (less wasted channel time).يعني: بدل ما تكمل frame بايظة لآخرها، توقف أول ما تحس بالـ collision فتوفر وقت القناة.

(b)(i) Function of the 8-byte preamble? (ii) Is it included in the CRC? Why?

الإجابة

(i) First 7 bytes 10101010 wake up the receiving adapters and synchronize their clocks with the sender’s clock (drift in transmission rate); last byte 10101011 — its last two bits alert the receiver that data starts. (ii) No: the CRC is computed over all frame data except the preamble — the preamble only serves synchronization and is not part of the frame’s data (it may be partly lost while the receiver locks on).يعني: الـ preamble بيصحّي المستقبل ويظبط ساعته، وآخر bits فيه بتعلن بداية الداتا. مش داخل في الـ CRC لأنه للمزامنة بس مش داتا.

(c)Connect 122 nodes with 10Base2. How many repeaters and why?

الإجابة

كل segment في 10Base2 ياخد 30 node بالكتير. 122 ÷ 30 = 4.07 ← 5 segments ← عدد الـ repeaters = segments − 1 = 4.

10Base2 without a repeater: max 30 nodes per segment (185 m). ⌈122 / 30⌉ = 5 segments → 4 repeaters to join them. That is also the maximum allowed (4 repeaters → 925 m, 150 nodes ≥ 122).

(d)Describe the Ethernet service type.

الإجابة

Connectionless: no connection is established between sender and receiver. Unreliable: no positive or negative acknowledgment; the receiver discards a frame that fails the CRC check. Detecting gaps in the data depends on the application-layer protocol; if the sender retransmits, Ethernet doesn’t know it is retransmitted data.يعني: من غير اتصال ومن غير ضمان: مفيش ACK، اللي CRC بتاعها غلط بتترمي، والبرنامج هو اللي يكتشف الناقص.

(e)(i) Why Manchester encoding? (ii) Encode 10001010.

الإجابة

كل bit قسمها نصين: 1 = عالي ثم واطي، 0 = واطي ثم عالي. اربط الخط.

(i) Every bit contains a transition (1 = up→down, 0 = down→up) → used to synchronize the sender’s and receiver’s clocks.

يعني: كل bit فيها انتقال في النص (1 نزول، 0 طلوع) فساعة المستقبل بتفضل متظبطة مع الراسل.

Problem 3 — 802.11

MID 2025 P1c

السؤال الأصلي

(a)Infrastructure vs ad-hoc network?

الإجابة

Infrastructure: hosts are associated with a base station (AP); network services such as address assignment and routing are provided by the network. Ad hoc: 802.11 stations group themselves to form a network with no central control.يعني: infrastructure فيه AP مركزي بيدي عناوين ويعمل routing، ad hoc الأجهزة مع بعض من غير أي جهاز مركزي.

(b)How 802.11 reserves the channel; schematic of the steps.

الإجابة

ارسم 3 خطوط زمن (source, destination, others) واكتب: DIFS → RTS → SIFS → CTS → SIFS → DATA → SIFS → ACK، والباقي NAV.

Using short RTS/CTS control frames: after sensing the channel idle for DIFS the source sends RTS (with the duration); after SIFS the destination answers CTS, heard by all stations around it; they set their NAV and defer. After SIFS the source sends DATA; after SIFS the destination sends ACK.

Draw the RTS → CTS → DATA → ACK timeline from Part 2 → 802.11.

يعني: الراسل يبعت RTS، المستقبل يرد CTS (اللي حواليه يسمعوها ويسكتوا)، بعدين الداتا، بعدين ACK.

(c)When are DIFS and SIFS used? Which is shorter and why?

الإجابة

DIFS: a station may transmit (a new frame / RTS) only after sensing the channel idle for DIFS. SIFS: the gap a receiver waits before sending its ACK (or CTS, or DATA after CTS). SIFS is shorter so the response frames get priority: the receiver replies before any other station can see the channel idle for a full DIFS and start a new transmission that would collide with the ACK.يعني: DIFS = الوقت اللي تستنى القناة فاضية قبل ما تبدأ. SIFS = الوقت الأقصر قبل الرد (ACK/CTS). SIFS أقصر عشان الرد ياخد أولوية.

(d)Hidden station problem and how to avoid it?

الإجابة

A and C can’t hear each other (e.g. an obstacle between them) so both sense idle and transmit → their frames collide at B. Avoided with RTS/CTS: the CTS sent by the receiver is heard by all stations within its vicinity (including hidden ones), so they defer; a collision can only involve the short RTS/CTS frames.يعني: A وC مش سامعين بعض فبيبعتوا مع بعض ويتخبطوا عند B. الحل RTS/CTS: الـ CTS من B بتوصل للاتنين فيسكتوا.

(e)Cause of the fading problem?

الإجابة

Signal strength decreases with distance: the signals of A and C are too weak to be detected by each other, but they are strong enough to interfere at B, the receiver in the middle.يعني: الإشارة بتضعف مع المسافة، فـ A وC ضعاف عند بعض بس قويين كفاية إنهم يشوشوا على B.

Problem 4 — Hubs & switch types

السؤال الأصلي

(a)Limitations of hubs?

الإجابة

All segments must use the same Ethernet technology; the separate collision domains become one common collision domain → max aggregate throughput limited to that of one segment; each technology limits the max number of nodes per collision domain, the max distance between two hosts and the max number of tiers → limits total hosts and geographical reach.يعني: نفس التكنولوجيا للكل، collision domain واحد فالسرعة = segment واحد، وحدود للعدد والمسافة والطبقات.

(b)Types of switches and their strategy?

الإجابة

Store-and-forward: the whole frame is received and stored before transmission on the outbound link starts (max delay L/R). Cut-through: if the output buffer is empty before the entire frame arrives, the switch starts sending the front of the frame while the back is still arriving.يعني: store-and-forward يستقبل الـ frame كلها الأول، cut-through يبدأ يبعت أولها وآخرها لسه بيوصل.

(c)Max store-and-forward delay: L = 800 bytes, inbound 25×10⁵ bit/s, outbound 40×10⁵ bit/s?

الإجابة

Delay = L / R بتاع اللينك الداخل (inbound). حوّل bytes لـ bits (× 8). سرعة الخارج مش بتدخل.

L/R = (800 × 8) / (25 × 10⁵) = 6400 / 2,500,000 = 2.56 ms

R is the rate of the inbound link (the one the frame arrives on); the outbound rate is a distractor.

Problem 5 — Routers, switch, ARP

السؤال الأصلي

Each router has one adapter (MAC + IP) per interface. The switch has no MAC.

(a)Assign MAC addresses to the nodes and routers.

الإجابة

كل host كارت واحد = MAC واحد. كل router له interface في كل LAN = MAC لكل interface (الراوتر هنا له 2). الـ switch ماله MAC. اكتب أي عناوين hex فريدة.

Interface	MAC	IP (example)
A	1A-23-F9-CD-06-9B	111.111.111.1
B	5C-66-AB-90-75-B1	111.111.111.2
Router 1 – left (R1a)	E6-E9-00-17-BB-4B	111.111.111.3
Router 1 – right (R1b)	CC-49-DE-D0-AB-7D	222.222.222.1
C	49-BD-D2-C7-56-2A	222.222.222.2
D	88-B2-2F-54-1A-0F	222.222.222.3
Router 2 – left (R2a)	74-29-9C-E8-FF-55	222.222.222.4
Router 2 – right (R2b)	3A-11-6F-B0-C2-D8	133.133.133.1
E	9E-52-0D-41-7A-C3	133.133.133.2

Any unique 48-bit values are fine; the switch gets none.

(b)ARP table of D (D recently talked to all nodes).

الإجابة

الـ ARP table فيها بس الأجهزة اللي على نفس الـ LAN بتاعة D (اللي متوصلة بالـ switch): C، وinterface الراوتر 1، وinterface الراوتر 2. A وB وE مش على نفس الـ LAN فمش موجودين.

IP address	MAC address	TTL
222.222.222.1 (R1b)	CC-49-DE-D0-AB-7D	13:45:00
222.222.222.2 (C)	49-BD-D2-C7-56-2A	13:47:00
222.222.222.4 (R2a)	74-29-9C-E8-FF-55	13:50:00

D بيكلم A و B عن طريق R1b، وبيكلم E عن طريق R2a. عشان كده مفيش entries لـ A و B و E، لأنهم مش على نفس الـ subnet.

(c)Steps when A sends E a frame.

الإجابة

امشي خطوة خطوة: A ← (ARP لـ MAC الراوتر) ← Router 1 يعمل frame جديدة ← switch يبص في جدوله ← Router 2 يعمل frame جديدة ← E. في كل frame اكتب src MAC و dst MAC.

A’s network layer: E is on a different network → next hop = Router 1 (R1a). ARP gives R1a’s MAC (broadcast ARP request if not in the table).
A’s DLL sends a frame: src MAC A, dst MAC R1a (IP dst = E).
Router 1 passes it up to its network layer → routing table → out of R1b, next hop R2a; ARP for R2a’s MAC → new frame: src R1b, dst R2a.
The switch receives it on port 1, looks up R2a → port 2 → forwards (filters it from other ports).
Router 2 → network layer → routing table: E is on the network directly attached to R2b → ARP for E’s MAC → new frame: src R2b, dst E → E receives it.

(d)How is a switch table built?

الإجابة

Automatically (self-learning): initially empty; for each frame received the switch stores the frame’s source MAC, the interface it arrived on, and the current time; if a frame’s destination isn’t in the table it forwards copies to the output buffers of all other interfaces.يعني: بيتعلم لوحده: كل frame تيجي يسجل MAC الراسل والبورت والوقت، ولو الوجهة مش معروفة يبعت على كل البورتات.

(e)Switch table after communication between all nodes.

الإجابة

اللي هيظهر = الأجهزة اللي frames بتوصل للـ switch منها مباشرة (على نفس الـ LAN): C, D, وinterface كل راوتر. أي حاجة ورا راوتر مش هتظهر لأن الراوتر بيحط MAC بتاعه.

Address	Interface	Time
CC-49-DE-D0-AB-7D (R1b)	1	9:32
49-BD-D2-C7-56-2A (C)	1	9:33
88-B2-2F-54-1A-0F (D)	2	9:35
74-29-9C-E8-FF-55 (R2a)	2	9:36

A و B و E مش هيظهروا في الجدول أبدًا. أي frame جاية منهم بتعدي على الراوتر، والراوتر بيعمل frame جديدة بالـ MAC بتاعه هو.

ASSIGNMENT 4 · PARTS 2 & 3Collision Domains, Routers & IP

0/5

Problem 1 — Router G, switch n, hubs j, k, h

السؤال الأصلي

(a)How many collision domains? List them.

الإجابة

قاعدة: hubs مابتفصلش (كل اللي متوصل بـ hubs = domain واحد). كل port في switch أو router = domain لوحده. فعدّ: مجموعة الـ hubs مع بعض = 1، وكل جهاز متوصل مباشرة بالـ switch = 1.

3 collision domains. Hubs only repeat bits, so everything connected through hubs is one collision domain; each switch (and router) interface is a separate collision domain.

p, q, hub k, hub h, hub j, t, u, router G’s interface, and switch n’s port to h.
host r with its switch-n port.
host s with its switch-n port.

(b)If p uses 10BaseT, must q, r, s, t, u also use 10BaseT?

الإجابة

الـ hubs بتجبر الكل على نفس التكنولوجيا؛ الـ switch لأ. شوف كل host متوصل بإيه.

q, t, u: yes — they are connected to p through hubs, and all segments joined by hubs must use the same Ethernet technology. r, s: no — they are behind switch n, and a switch can interconnect different LAN technologies.

(c)(i) How is switch n’s table built? (ii) Write it.

الإجابة

(ii) كل MAC وراه رقم الـ port اللي الـ frame بتاعته بتدخل منه. كل الأجهزة اللي ورا الـ hubs (p, q, t, u, G) بتدخل من نفس الـ port.

(i) Self-learning: initially empty; for each received frame store source MAC + arrival interface + time; unknown destination → forward copies to all other interfaces.

MAC address	Interface	Time
MAC(r)	1	9:30
MAC(s)	2	9:31
MAC(p)	3 (to hub h)	9:32
MAC(q)	3	9:33
MAC(t)	3	9:34
MAC(u)	3	9:35
MAC(G interface)	3	9:36

الـ hubs مالهمش MAC، فمش هيظهروا في الجدول.

Problem 2 — Planes & service model

السؤال الأصلي

(a)Main functions of (i) the data plane, (ii) the control plane

الإجابة

(i) Data plane (router functions): determine how a datagram arriving on one of a router’s input links is forwarded to one of its output links. (ii) Control plane: determine how a datagram is routed among routers along an end-to-end path from the source host to the destination host.يعني: data plane = الراوتر الواحد يقرر الباكت تطلع من فين. control plane = تحديد الطريق على مستوى الشبكة كلها.

(b)Switching (forwarding) vs routing

الإجابة

Forwarding (data plane): the router-local action of transferring a packet from an input link interface to the appropriate output link interface (it may also block or duplicate packets). Routing (control plane): the network-wide process that determines the end-to-end paths packets take from source to destination.يعني: forwarding حركة محلية جوه الراوتر، routing حسبة على مستوى الشبكة كلها بتملى جدول الـ forwarding.

(c)Characteristics of the network-layer service model

الإجابة

It defines the characteristics of end-to-end transport between end systems: guaranteed delivery; guaranteed delivery with bounded delay; in-order packet delivery; guaranteed minimal bandwidth; security (encryption/decryption). (The Internet’s IP gives best-effort service: none of these are guaranteed.)يعني: الخدمات اللي الطبقة ممكن تضمنها: الوصول، في وقت محدد، بالترتيب، بسرعة أدنى، وأمان. (الـ IP الحقيقي مش بيضمن أي حاجة.)

Problem 3 — Router internals

السؤال الأصلي

(a)Block diagram of the router architecture

الإجابة

Input ports → switching fabric → output ports, with the routing processor attached to the fabric (figure in Part 3 → Router Architecture). Input port: line termination → data link processing → lookup/forwarding/queueing. Output port: queuing/buffer management → data link processing → line termination.يعني: input ports ← switching fabric ← output ports، والـ routing processor متوصل بالـ fabric.

(b)Advantages and disadvantages of switching fabrics

الإجابة

Memory: simple, done under direct CPU control; but every packet is copied into and out of memory through the routing processor (interrupt) → slow, one packet at a time. Bus: no routing-processor intervention; but only one packet at a time on the shared bus, arriving datagrams queue at the input when busy, bandwidth limited to bus speed. Interconnection network (crossbar, 2N buses for N ports): overcomes the single-bus limit, packets to different outputs move in parallel; but more complex, and a packet waits at the input when its vertical bus is busy (HOL blocking).يعني: memory بسيطة بس بطيئة (البروسيسور بينسخ كل باكت). bus من غير بروسيسور بس باكت واحدة في المرة. crossbar كذا باكت مع بعض بس أعقد وفيه HOL.

(c)How are routing table entries stored; effect on processing time?

الإجابة

In a binary tree: each level corresponds to one bit of the destination address (0 → left subtree, 1 → right). A lookup takes N steps (N = address length) → fast and bounded, so lookup can finish in less time than receiving a packet → input processing at line speed. A shadow copy at each input port makes the decision local (no central bottleneck).يعني: شجرة كل مستوى فيها = bit من العنوان، فالبحث عدد خطواته ثابت وسريع، ونسخة من الجدول عند كل input port.

(d)How queues build up at input and output ports

الإجابة

Output: if the fabric delivers packets faster than the output link rate, e.g. with Vs ≥ nVi all n inputs send to the same output → n arrive, 1 leaves → n−1 queued (dropped when memory is full). Input: if the fabric is not fast enough (Vs < nVi), or with HOL blocking in a crossbar, packets wait at the input queues.يعني: عند الـ output لما كذا باكت يعوزوا نفس المخرج. عند الـ input لما الـ fabric أبطأ من مجموع المداخل أو بسبب HOL.

(e)HOL blocking and the scenario that causes it

الإجابة

Head-of-the-line blocking: a queued packet must wait for transfer through the fabric even though its output port is free, because it is blocked by another packet at the head of its line. Scenario: crossbar fabric with FCFS; the packets at the front of two input queues go to the same output → one waits, and the packet behind it (going to a free output) also waits.يعني: باكت في أول الطابور مستنية مخرج مشغول، فاللي وراها واقفة معاها رغم إن مخرجها فاضي. بيحصل في crossbar مع FCFS.

Problem 4 — IPv4 classes & IPv6

السؤال الأصلي

(a)Max number of networks per IPv4 class

الإجابة

عدد bits الشبكة − الـ bits الثابتة في الأول. A: 8 − 1 = 7. B: 16 − 2 = 14. C: 24 − 3 = 21. الناتج 2 أس الرقم.

A: 8-bit network, first bit fixed (0) → 2⁷ = 128
B: 16-bit network, first 2 bits fixed (10) → 2¹⁴ = 16,384
C: 24-bit network, first 3 bits fixed (110) → 2²¹ = 2,097,152
D: multicast — no networks

السلايد بتقول صراحة إن class A = 2⁷ لإن أول bit ثابت. نفس المنطق في B و C: اطرح الـ bits الثابتة.

(b)Address types in IPv6

الإجابة

Unicast: identifies a single interface. Anycast: identifies a set of interfaces; a packet is delivered to one member (the nearest). Multicast: identifies a group of interfaces; a packet is delivered to all of them. No broadcast addresses in IPv6.يعني: unicast لواحد، anycast لأقرب واحد من مجموعة، multicast للمجموعة كلها، ومفيش broadcast.

(c)Advantage of tunneling over dual stack (with example)

الإجابة

With dual stack, whenever a node on the path is IPv4-only, the datagram is converted to IPv4 and IPv6-only fields (e.g. the flow label) are lost, even if source and destination are both IPv6. With tunneling, the complete IPv6 datagram is encapsulated as the payload of an IPv4 datagram through the IPv4 part, so nothing is lost. Example: A, B (IPv6) – C, D (IPv4) – E, F (IPv6): dual stack → E receives IPv4 and sends F an IPv6 packet with “flow: ???”; tunnel B → E keeps flow X.يعني: في dual stack الحقول الزيادة (flow label) بتضيع لما نعدي على IPv4. في tunneling باكت الـ IPv6 بتتلف كلها جوه IPv4 فمفيش حاجة تضيع.

(d)A(6) – B(4) – C(6) – D(4) – E(4) – F(6) – G(6): A sends to G

الإجابة

امشي node node. Dual stack: أول ما تقابل IPv4 حوّل لـ IPv4 والحقول الزيادة تضيع. Tunneling: اللي قبل الـ IPv4 يلف الـ IPv6 جوه IPv4 واللي بعده يفكها.

(i) Dual stack: B is IPv4-only → A must send an IPv4 datagram (src A, dst G; flow label lost). C (dual stack) must use IPv4 again toward D, and D → E → F stay IPv4. F → G are both IPv6 → F rebuilds an IPv6 datagram (src A, dst G) but the original IPv6 fields are lost (flow: ???).

(ii) Tunneling: tunnel A → C through B: A puts the IPv6 datagram (src A, dst G, flow X) inside an IPv4 datagram (src A, dst C); C decapsulates. Tunnel C → F through D, E: IPv4 (src C, dst F) carrying the same IPv6 datagram; F decapsulates and sends native IPv6 to G. All IPv6 fields arrive intact.

Problem 5 — Fragmentation

السؤال الأصلي

Segment 2400 bytes from A to B. Links: A —MTU 800— Router —MTU 400— Router —MTU 200— B. IP header = 20 bytes (offsets in bytes, as in the slides).

(a)How many fragments reach B?

الإجابة

طبّق الـ MTU بالترتيب. في كل مرحلة: data في الحتة = MTU − 20. قسّم كل حتة من المرحلة اللي فاتت على الرقم ده (الباقي حتة صغيرة لوحدها). الحتت اللي أصغر من MTU بتعدي زي ما هي. عدّ في الآخر.

MTU 800 → 780 data each: 2400 = 780 + 780 + 780 + 60 → 4 fragments
MTU 400 → 380 data: each 780 → 380 + 380 + 20 (3); the 60 stays (1) → 3×3 + 1 = 10
MTU 200 → 180 data: each 380 → 180 + 180 + 20 (3); each 20 and the 60 stay (1)
Per 780 block: 3 + 3 + 1 = 7 → 3 × 7 + 1 = 22 fragments

(b)Fragments’ characteristics (ID, offset, flag)

الإجابة

نفس ID للكل. offset = بداية data الحتة بالنسبة للأصل (ممكن تكتبه بالـ bytes زي السلايدز، أو ÷ 8 زي الـ IP الحقيقي). flag = 1 لكل الحتت ما عدا اللي فيها آخر byte.

All fragments share the same identification number (e.g. 777). Flag = 1 for all except the very last fragment (offset 2340).

(c)How many times do fragmentation and reassembly occur, and where?

الإجابة

Fragmentation بتحصل في كل مكان الحتة أكبر من MTU اللينك الجاي (هنا 3 مرات). Reassembly مرة واحدة بس عند B.

Fragmentation: 3 times — at A’s network layer (MTU 800), at the first router (MTU 400) and at the second router (MTU 200). Reassembly: once, at the destination B (routers never reassemble).

ASSIGNMENT 5 · PART 3Dijkstra & Distance Vector

0/4

قاعدة الحل: الـ switch والـ hub مش routing nodes. بنجمع تكلفة اللينكات اللي حواليهم (مثلًا C–u–D = 1 + 1 = 2). والـ hosts مابتدخلش في الجداول.

Problem 1 — Theory

السؤال الأصلي

(a)Static vs dynamic routing algorithms

الإجابة

Static: routes change very slowly over time, often as a result of human intervention. Dynamic: routes change with changes in network traffic load or topology; can run periodically or in direct response to topology or link-cost changes; more susceptible to routing loops and route oscillation.يعني: static الطرق ثابتة تقريبًا وبتتغير بإيد الأدمن. dynamic بتتغير لوحدها مع الحمل والتغييرات بس معرضة لـ loops وتذبذب.

(b)Centralized vs decentralized routing algorithms

الإجابة

Centralized (global): complete information about connectivity and link costs across the entire network; the min-cost path is computed from this global state (link-state algorithms). Decentralized: no node has complete information; each node knows only the costs of the links attached to it; an iterative process of calculation and exchange of information between neighbors finds the min-cost path (distance vector).يعني: centralized كل راوتر عارف الخريطة كلها (link state). decentralized كل راوتر عارف جيرانه بس وبيتبادل معاهم (distance vector).

(c)What is the sink tree? How is it related to routing?

الإجابة

The set of optimal routes from all sources to a given destination forms a tree rooted at the destination. The goal of all routing algorithms is to find and use the sink trees for all routers.يعني: أحسن الطرق من كل الراوترات لراوتر واحد بتعمل شجرة جذرها الراوتر ده، والـ routing هدفه يلاقي الشجرة دي لكل راوتر.

(d)Types of routers in OSPF hierarchical routing MID 2026

الإجابة

Internal routers: in non-backbone areas, perform only intra-area routing. Area border routers: belong to both an area and the backbone. Backbone routers: perform routing within the backbone but are not area border routers. Boundary routers: exchange routing information with routers belonging to other autonomous systems.يعني: internal جوه area، area border بين area والـ backbone، backbone جوه الـ backbone بس، boundary بيكلم ASs تانية.

(e)RIP vs IGRP

الإجابة

Both are distance-vector intra-AS protocols. RIP: hop count metric (max 15), periodic advertisements every 30 s over UDP. IGRP (Cisco): several metrics (delay, bandwidth, reliability, load) weighted by the administrator; uses a reliable transport protocol; sends updates only when routing-table costs change; uses a distributed diffusing update algorithm to quickly compute loop-free routes.يعني: الاتنين distance vector، بس RIP بيعد hops وبيبعت كل 30 ثانية على UDP، وIGRP بمقاييس أكتر وبيبعت بس لما حاجة تتغير وبيتجنب الـ loops بسرعة.

Problem 2 — 6 routers A–F, host w

السؤال الأصلي

(a)(i) Dijkstra from E step by step. (ii) Routing tree.

الإجابة

جدول: عمود لكل node غير الـ source. الصف الأول: جيران E بتكلفتهم و(E)، الباقي ∞. كل صف: اختار أصغر تكلفة لسه مدخلتش N، ضيفها لـ N، وحدّث جيرانها لو (تكلفتها + اللينك) أصغر. الشجرة = من كل node للنود اللي بين القوسين.

Tree from E: E–C, C–A, A–D, D–B, D–F

(b-i)Initial distance table at D

الإجابة

صفوف = كل الوجهات، أعمدة = جيران D بس. في البداية الخانة (الوجهة = الجار) = تكلفة اللينك، وكل الباقي ∞.

في الأول D عارف بس تكلفة اللينكات بتاعته (القطر)، وكل حاجة تانية ∞.

(b-ii)Distance tables at D, E, F at steady state

الإجابة

الخانة (وجهة R، عن طريق M) = تكلفة اللينك D–M + أرخص طريق من M لـ R (من Dijkstra أو من شجرة M). الأخضر = أصغر رقم في الصف.

كل خانة = تكلفة اللينك للـ neighbor + أقل تكلفة عند الـ neighbor للـ destination. الأخضر هو الـ min (لو فيه تعادل، الاتنين أخضر).

(b-iii)Routing trees from (ii)

الإجابة

من جدول كل node: لكل وجهة خد العمود اللي فيه أصغر رقم = الجار اللي تمشي منه. ارسم اللينكات اللي اتستخدمت بس.

D: A(1), B(1), C via A(2), E via A(7), F(2)

E: everything via C

F: B(1), D(2), A via B or D (3) — tie

(c)D–E cost 8 → 80: problem routing to E from D and F?

الإجابة

اسأل: اللينك ده كان مستخدم في أي طريق لـ E؟ بص في عمود via E عند D و F. لو مش هو الأصغر في أي صف، التغيير مش هيأثر على أي route.

No problem. At steady state D reaches E via A (D–A–C–E = 7), not over the direct D–E link (8), and F reaches E via B or D (9) — also through A–C–E. The D–E link is not on any route to E, so the min in D’s row for E stays 7 via A; only the unused “via E” column changes (8 → 80). No count-to-infinity, no routing loop.يعني: اللينك D–E مش مستخدم أصلًا في أي طريق لـ E (الكل بيروح عن طريق A–C)، فلما يغلى مفيش حاجة بتتغير ومفيش loop.

Problem 3 — Two ASes X and Y

السؤال الأصلي

AS-X (C–D through switch u = 1 + 1 = 2; q is a host on B)

AS-Y (r is a host on M) · inter-AS link A–F = 5

(a)(i) Dijkstra from M in AS-Y. (ii) Routing tree.

الإجابة

نفس خطوات Dijkstra. AS-Y لوحدها (ماتدخلش A أو اللينك 5). اكتب ترتيب الإضافة: M, J, K, H, G, F.

Order added: M, J(2), K(3), H(7), G(9), F(10) · tree M–J, J–K, K–H, H–G, G–F

(b)DV in AS-X: (i) steady-state tables at all nodes. (ii) Routing tree.

الإجابة

AS-X فيها 4 راوترات بس. لينك C–D = 1 + 1 = 2 (الـ switch بيتجمع). الـ hosts مش في الجداول.

All least-cost routes use A–B, B–C, C–D (A–C = 7 and B–D = 8 are never used)

(c)B–C cost changes 3 → 50. (i) New tables at A and B after the first update. (ii) Count-to-infinity effect. (iii) Solution.

الإجابة

(i) B بيعيد الحساب بالأرقام اللي جيرانه بعتوهاله آخر مرة (قبل التغيير). A بيحسب من جدول B الجديد. (ii) دوّر على اتنين كل واحد رايح للوجهة عن طريق التاني = loop. (iii) poisoned reverse: اللي بيمشي من خلالك يقولك ∞.

(i) B detects the change and recomputes using the neighbors’ last advertised minimums (A: C=4, D=6 — both through B; C: A=4, D=2; D: A=6, C=2):

λᴮ	via A	via C	via D
A	1	54	14
C	5	50	10
D	7	52	8

λᴬ (after B’s update)	via B	via C
B	1	10
C	6	7
D	8	9

(ii) B now thinks it reaches C (and D) through A, while A reaches them through B → routing loop A ⇄ B. Each exchange raises the costs (B→C: 5 → 7 → 8, A→C: 6 → 7) and packets bounce between A and B until the costs pass the real alternatives (A’s direct link to C = 7, B via D = 10). Here it ends after a few updates (B→C = 8 via A, B→D = 8 direct) because A has its own link to C; with no alternative path it would count up to infinity.

(iii) Poisoned reverse: since A routes to C and D through B, A advertises to B that its distance to C and D is ∞. Then B never routes to C or D via A based on stale info: it first picks via D (10 and 8), and after A recomputes (A→C = 7 direct) B correctly uses A (8).

(d)(i) How a packet is routed from r to q. (ii) How many routing protocols are used?

الإجابة

3 مراحل: جوه Y (Dijkstra من M لـ F)، اللينك بين الـ ASs (F → A)، جوه X (DV من A لـ B). عدد البروتوكولات = 3.

(i) r → its router M. Inside AS-Y (link-state/Dijkstra): M → J → K → H → G → F (cost 10, from part a). F is the gateway: F → A over the inter-AS link (inter-AS protocol, e.g. BGP). Inside AS-X (distance vector): A → B (cost 1). B delivers to host q. Path: r → M → J → K → H → G → F → A → B → q. (ii) 3 protocols: the intra-AS link-state protocol in Y, the inter-AS protocol (BGP) between F and A, and the intra-AS distance-vector protocol in X.يعني: 3 مراحل ببروتوكول مختلف في كل واحدة: جوه Y بـ link state، بين الـ ASs بـ BGP، وجوه X بـ distance vector.

Problem 4 — Routers A, B, C, D, F; switches E, G

السؤال الأصلي

Switch E joins p, D (3), C (1) and switch G (8) → for routing D–C = 3 + 1 = 4. M, N, P, R are hosts and are not in the tables.

(i)All initial distance tables

الإجابة

لكل راوتر: صفوف الوجهات، أعمدة الجيران، تكلفة اللينك في خانة الجار و∞ في الباقي. D–C عن طريق switch E = 3 + 1 = 4. B–D مباشر = 6.

(ii)Tables at B and F after 1 update

الإجابة

بعد update واحد كل راوتر عرف الـ initial vector (أرخص أرقام) بتاع جيرانه بس: الخانة = اللينك + رقم الجار الأولي (اللينك المباشر أو ∞).

بعد أول update، كل نود عرفت الـ initial vector بتاع جيرانها بس. يعني B عرفت إن A بيوصل D بـ 3 (فـ via A = 2 + 3 = 5)، و F عرفت من C إن B = 2 و D = 4.

(iii)Steady-state table at B

الإجابة

نفس القاعدة بس بأرخص طريق حقيقي من كل جار (من Dijkstra).

B → D = 5 via A (via C = 6, direct = 6) · B → F = 11 via C.

ASSIGNMENT 6 · PART 3RIP, OSPF, BGP & IGMP

0/4

أهم فكرة هنا: RIP بيعد hops (كل لينك = 1 مهما كانت تكلفته)، وOSPF بيستخدم تكلفة اللينكات (Dijkstra). عشان كده الجدولين بيطلعوا مختلفين لنفس الشبكة.

Problem 1 — AS-X (RIP) & AS-Y (OSPF)

السؤال الأصلي

AS-X: hub n connects D, s, p · q on E · gateway A

AS-Y: G–m–F through switch m = 1 + 2 = 3 · r on K · inter-AS A–G = 4

(a)RIP in AS-X: (i) routing table at D (steady state), (ii) routing tree

الإجابة

RIP = hop count: كل لينك = 1 مهما كانت تكلفته. احسب أقل عدد hops من D لكل راوتر، واكتب next router. لو فيه تعادل اكتب الاتنين.

RIP tree at D (hop count): D–E–A, D–C–B (B could also go via E — tie, 2 hops)

الجدول ماشي بطريقة السلايدز وحلول الأسايمنتس: الراوتر نفسه = 1 hop، وكل لينك بيزوّد 1. يعني A = 3 لأن بينها وبين D لينكين.

(b)OSPF in AS-Y: (i) how F builds its table, (ii) routing tree

الإجابة

OSPF = link state بالتكاليف الحقيقية. G–F عن طريق switch m = 1 + 2 = 3. اعمل Dijkstra من F واكتب الجدول.

(i) Every router floods the identities and costs of its attached links to all routers in the AS → F builds a complete topological map of AS-Y → runs Dijkstra locally with itself as the root → the shortest-path tree gives the routing table (next hop + cost for each destination).

F–H (1), H–G (2, cheaper than G–m–F = 3), H–J (4), F–K (3)

(c)How a packet from host p is routed to host r

الإجابة

3 مراحل: جوه X بـ RIP (hops)، A → G (inter-AS)، جوه Y بـ OSPF (تكلفة). اكتب الطريق كله.

p sends the frame (dst MAC = D) through hub n to its router D.
Intra-AS in X (RIP, hop count): D → E → A (A is the gateway to AS-Y).
Inter-AS (BGP): A → G.
Intra-AS in Y (OSPF): G → H → F → K (cost 1 + 1 + 3 = 5; via switch m would be 6).
K delivers to host r on its directly attached network.

p → n → D → E → A → G → H → F → K → r

يعني: من p للراوتر D، جوه X بـ RIP (أقل hops) لحد الـ gateway A، بعدين لـ G ببروتوكول inter-AS، وجوه Y بـ OSPF (أقل تكلفة) لحد K، وK يسلّم لـ r.

(d)(i) How many interfaces does the packet travel over? (ii) How many routing tables are indexed?

الإجابة

كل راوتر في الطريق = 2 interfaces (دخول وخروج). + 1 للـ host المرسل + 1 للمستقبل. الـ hub ماعندوش interfaces بعناوين. عدد الجداول = عدد الراوترات في الطريق (ممكن تزوّد جدول الـ host).

(i) p (1) + each router in and out: D, E, A, G, H, F, K (7 × 2 = 14) + r (1) = 16 interfaces (the hub has no MAC/IP interface; the switch m is not on this path). (ii) 7 routing tables in the routers D, E, A, G, H, F, K (8 if you also count host p’s own table, which decides to send to D).

(e)How p gets the route to r with traceroute

الإجابة

p sends a series of datagrams to r: the first with TTL = 1, the second TTL = 2, etc., starting a timer for each. When the n-th datagram reaches the n-th router (D, E, A, G, H, F, K…), its TTL has just expired → the router discards it and sends an ICMP warning message to p. p gets the round-trip time from the timer and the router’s name and IP address from the ICMP message → the full route.يعني: p يبعت باكتس بـ TTL 1 و2 و3...، كل راوتر لما الـ TTL يخلص عنده يرد ICMP، فـ p يعرف كل راوتر في الطريق ووقته.

Problem 2 — RIP vs OSPF at G

السؤال الأصلي

(a)RIP: routing table at G (steady state)

الإجابة

عدّ لينكات بس (من غير تكلفة) وزوّد 1، والراوتر نفسه = 1. E و F لينك واحد ← 2، A و B لينكين ← 3 (A عن طريق E، B عن طريق F)، C و D تلات لينكات ← 4.

Hosts: x, y directly attached (1 hop in slide convention); n, m via E (behind A).

(b)OSPF: routing table at G

الإجابة

Dijkstra من G بالتكاليف. لاحظ G–F = 3 أرخص من G–E = 5، فحتى E نفسها أرخص عن طريق F (3 + 1 = 4).

With costs everything leaves G via F (G–F = 3 is cheaper than G–E = 5)

(c)x sends to n: (i) IP networks crossed, (ii) routing tables scanned — in each case

الإجابة

عدّ الشبكات = عدد اللينكات اللي الباكت عدّت عليها (host–router وrouter–router كل واحد شبكة). الجداول = عدد الراوترات (+1 لو حسبت الـ host).

	Path	IP networks	Routing tables
RIP	x → G → E → A → n	4 (x–G, G–E, E–A, A–n)	3 routers (G, E, A) — 4 with host x
OSPF	x → G → F → E → A → n	5 (x–G, G–F, F–E, E–A, A–n)	4 routers (G, F, E, A) — 5 with host x

Problem 3 — BGP

السؤال الأصلي

Router A receives the path B T W X Y N from B. When is it (i) added, (ii) not added?

الإجابة

3 شروط للإضافة (مش في الطريق، مفيش أحسن، الـ policy تسمح) وعكسهم 3 أسباب للرفض.

(i) A adds the new entry A B T W X Y N if: A does not already appear in the path (no loop), A has no preferable path to N, and A’s policy allows forwarding datagrams through every AS on the path (B, T, W, X, Y). (ii) It is not added if A is already in the path (loop), if A already has a preferable path to N, or if A has a policy decision not to forward datagrams through one of these ASes (e.g. T).يعني: A يضيف الطريق لو مش موجود فيه ومفيش أحسن منه والسياسة تسمح. ويرفضه لو هو فيه (loop) أو عنده أحسن أو السياسة بتمنع AS معين.

Problem 4 — Multicast theory

السؤال الأصلي

(a)IGMP message types

الإجابة

Membership query – general: sent by a router to all hosts on an attached interface to find the set of all groups joined. Membership query – specific: used by a router to check if a specific group has been joined on an interface (includes the group address). Membership report: sent by a host in response to a query or when an application first joins a group (received by all hosts on the interface). Leave group: optional; the router infers that no host is joined when no one answers a query with that group address.يعني: الراوتر يسأل عام (أنهي مجموعات؟) أو خاص (المجموعة دي؟)، الجهاز يرد report، وممكن يبعت leave.

(b)Feedback suppression — what and why?

الإجابة

A router only needs to know that at least one attached host belongs to a group. Each query carries a maximum response time; a host waits a random time between 0 and that maximum; if it hears another host’s report for the same group first, it discards its own pending report. Used as a performance optimization: avoids unnecessary membership reports.يعني: الراوتر محتاج رد واحد بس لكل مجموعة، فكل جهاز يستنى وقت عشوائي ولو سمع حد رد يلغي رده. بيوفر رسايل.

(c)Multicast via unicast vs network multicast

الإجابة

Via unicast: the sender opens a separate unicast transport connection to each receiver and duplicates the data at the sender → many copies on the same links. Network multicast: explicit support at the network layer; one packet is sent and replicated at routers only where it must go out on several links → a single copy per link (efficient), but needs considerable network-layer support.يعني: via unicast الراسل بيبعت نسخة لكل واحد (نسخ كتير). network multicast نسخة واحدة والراوتر ينسخها عند التفرع (نسخة واحدة على كل لينك).

(d)Address indirection

الإجابة

A single identifier (a class D multicast address) is used for the group of receivers; a copy of a datagram addressed to that identifier is delivered to all receivers associated with it (the multicast group). Each host keeps its own unicast address.يعني: المجموعة ليها عنوان واحد (class D)، تبعت ليه فتوصل لكل الأعضاء، وكل عضو لسه عنده IP بتاعه.

(e)Objective of group-shared and source-based trees

الإجابة

Group-shared: a single tree for all senders — find a tree that connects all routers with attached group hosts with minimal cost (minimum sum of link costs → Steiner tree problem). Source-based: an individual tree per sender — least-cost paths from the source to each destination (least unicast-cost tree, or RPF).يعني: group-shared شجرة واحدة للكل بأقل مجموع تكلفة. source-based شجرة لكل راسل بأقصر طريق من الراسل لكل واحد.

ASSIGNMENT 7 · PART 3Multicast Routing

0/4

التلات طرق في سطر: center-based = كل راوتر بيبعت join للـ center بالـ unicast route بتاعه، والـ join بيقف عند أول راوتر موجود في الـ tree. least unicast-cost = Dijkstra من الـ source. RPF = الراوتر بيقبل الباكت لو جات من ناحية الـ shortest path للـ source، وبعدين يبعتها على كل اللينكات التانية.

Problem 1 — Center-based tree & IGMP

MID 2026 P3d

السؤال الأصلي

(a)Group-shared center-based tree with D as the center

الإجابة

1) احسب أقصر طريق (unicast) من كل راوتر للـ center D. 2) كل راوتر يبعت join على طريقه ده. 3) الـ join يقف عند أول راوتر موجود في الشجرة. الفروع = الطرق اللي الـ joins مشيت فيها.

D is the center. Each router that wants to join sends a join message by unicast toward D; it stops at the first router already on the tree; the path becomes a branch.
Unicast routes to D (Dijkstra from D): A–D (2), C–D (2), B–C–D (5), E–A–D (9), F–B–C–D (9), G–F–B–C–D (12).
Joins: A → A–D grafted. C → C–D. B → reaches C (on tree) → B–C. E → reaches A → E–A. F → reaches B → F–B. G → reaches F → G–F.
Routers with group hosts: A (n, m) and G (x, y). If only they join: A–D, then G’s join travels G → F → B → C → D.

All routers joined

Only A and G joined

(b)Hosts n and m joined group 226.3.16.4; how does A use IGMP to find out?

الإجابة

4 خطوات: الراوتر يبعت membership query specific بعنوان المجموعة + max response time → كل host يستنى وقت عشوائي → أول واحد يبعت membership report → اللي يسمعه يسكت. ارسم محتوى الرسالتين.

A sends a membership query – specific on its interfaces, containing the group address and a maximum response time.
Each host in the group (n, m) starts a random timer between 0 and the max response time.
The first host whose timer expires (say n) sends a membership report for 226.3.16.4; it is received by A and by all hosts on that interface.
A host on the same interface that hears this report suppresses its own (feedback suppression). (n and m are drawn on separate links, so each interface may get one report — A only needs one per interface.)
A now knows the group has members and joins the multicast tree for it.

typequerymax resp. timee.g. 10checksum

group address 226.3.16.4

Membership query – specific (router A → hosts)

typereportmax resp.unusedchecksum

group address 226.3.16.4

Membership report (n → A)

Problem 2 — 10 routers, source K

السؤال الأصلي

(a)Least unicast-cost path multicast tree from K

الإجابة

Dijkstra من K. الشجرة = اتحاد أقصر الطرق لكل راوتر.

K–J, J–L, L–O, K–M, M–N, M–P, P–Q, P–T, T–R

(b)RPF with pruning, source K, group = K, M, O

الإجابة

ابدأ من شجرة Dijkstra. أي ورقة مش في المجموعة تبعت prune لفوق. الراوتر اللي كل اللي تحته بعتوا prune وهو مش في المجموعة يبعت prune هو كمان. الراوتر اللي في المجموعة بيوقف الـ prune.

RPF forwards along the shortest-path tree from (a); routers without group hosts still receive packets.
Leaves with no group members send prune upstream: N → M, Q → P, R → T.
T received prunes from all its downstream routers (R) and has no members → T → P prune. P now has prunes from Q and T → P → M prune.
M is a member → stops. O is a member → L and J keep forwarding toward it.

Pruned tree: K–M and K–J–L–O

(c)RIP: (i) routing table at K, (ii) routing tree

الإجابة

عدّ اللينكات من K من غير تكلفة وزوّد 1 (K نفسه = 1). لاحظ إن RIP ممكن يختار لينك غالي زي O–R (9) لأنه بيعد hops بس.

Hop-count tree (ties: N via L or M, Q via M or L) — note O–R (9) is used: RIP ignores cost

(d)Center K; using (c), how do “D” and R join? no node D in the figure → read it as P

الإجابة

كل راوتر يمشي بطريق الـ RIP (hops) ناحية K ويبعت join. الفرع = الطريق.

Each router sends a join toward the center K along its RIP (hop-count) route; the path becomes a branch. P → M → K (2 hops). R → O → L → K (3 hops).

Tree after P and R join: K–M–P and K–L–O–R

Problem 3 — AS-X and AS-Y

السؤال الأصلي

$Original question a7-3$

AS-X: A–e–D = 1+3 = 4, A–u–B = 2+1 = 3, D–u–B = 7+1 = 8

AS-Y (r on M)

(a)AS-X, center A: tree after C joins

الإجابة

احسب أقصر طريق من C لـ A بالتكاليف (الـ switches بتتجمع: A–u–B = 3). الـ join تمشي في الطريق ده.

C’s unicast route to A: C → B → (u) → A, cost 2 + 1 + 2 = 5 (the other way C → D → (e) → A costs 4 + 3 + 1 = 8). The join travels C → B → A → tree = A–u–B–C.

(b)Least unicast-cost tree from G

الإجابة

Dijkstra من G في AS-Y بس (11 راوتر، r host).

(c)RPF: how a packet from G is distributed

الإجابة

لكل راوتر حدد اللينك اللي على أقصر طريقه لـ G (من Dijkstra). الباكت اللي تيجي من اللينك ده يقبلها ويبعتها على كل اللينكات التانية؛ أي نسخة تانية يرميها. على كل لينك ارسم مربع + سهم لكل مرة باكت عدّت.

Solid green arrows = accepted (arrive on the router’s shortest path to G) · dashed red arrows = sent but discarded at the receiver

Every router forwards the packet it accepts on all its other links. On tree links the packet goes one way (parent → child). On non-tree links (G–H, H–K, M–K, N–P, P–V) both ends send a copy and both copies are discarded, because they don’t arrive on the receiver’s shortest path to G.

(d)Only G, H, V in the group; pruned topology

الإجابة

من شجرة RPF: الأوراق اللي مش في المجموعة (M, P, W) تبعت prune. امسح فروعهم. الراوترات اللي في طريق V (J, K, N, T) تفضل.

M (no group host) → prune to J. P → prune to T. W → prune to V. V is a member, so T, N, K, J keep forwarding toward it; F forwards to H.

Pruned: G–F–H and G–J–K–N–T–V

Problem 4 — Internet multicast protocols

السؤال الأصلي

(a)DVMRP, MOSPF, CBT — group-shared or source-based?

الإجابة

DVMRP: source-based (RPF, pruning, grafting). MOSPF: source-based (source-specific, pre-pruned shortest-path trees). CBT: group-shared (bi-directional tree with a single center/core).يعني: DVMRP وMOSPF شجرة لكل راسل، CBT شجرة مشتركة بمركز.

(b)Advantage of PIM’s two distribution scenarios

الإجابة

PIM is independent of the underlying unicast protocol and has dense mode and sparse mode, so it fits both situations efficiently: dense mode when many routers have group members (flood-and-prune, RPF source trees); sparse mode when members are few and widely scattered (routers join explicitly toward a center → no flooding of routers that don’t need the traffic).يعني: PIM بيختار الوضع المناسب: dense (غرّق وبعدين prune) لما الأعضاء كتير، sparse (اشترك ناحية المركز) لما الأعضاء قليلين ومتفرقين، فمفيش غرق لراوترات مش محتاجة.

(c)Third-party dependency in BGMP; its disadvantage

الإجابة

BGMP (inter-AS) uses a group-shared tree, and the tree’s center could be chosen in an AS that doesn’t contain any hosts of the group. This dependency would unfairly burden that AS and may unnecessarily subject the group to performance dependencies on ASes outside those participating in the group.يعني: مركز الشجرة ممكن يقع في AS ماعندهاش أعضاء، فتتحمل عبء مش بتاعها وأداء المجموعة يعتمد على AS بره.

(d)Why tunneling in Internet multicast?

الإجابة

Only a small fraction of Internet routers are multicast capable. If a router is multicast capable but its immediate neighbors are not, tunneling builds a virtual network of multicast-capable routers on top of a physical network that mixes unicast and multicast routers.يعني: راوترات قليلة بتدعم multicast، فبيعملوا أنفاق بينهم فوق الشبكة العادية عشان يبقوا شبكة multicast افتراضية.

MIDTERM · NOV 10, 2025 · TERM 2025/2026Mid 2026

0/3

أحدث امتحان وأهمهم. لاحظ إن معظمه متكرر من الأسايمنتس: P1(a) هو ASG1 P1(d)، وP2 هو ASG2 P2 بأرقام جديدة، وP3 بنفس أسلوب ASG6 وASG7. الحسابات كلها متراجعة بالكود.

Problem 1 — 5 points

السؤال الأصلي

(a)What is the purpose of protocols, and what are the general functions they perform? = ASG1 P1d

الإجابة

Purpose: every activity on the Internet that involves two or more communicating nodes is governed by a protocol. Protocols are how corresponding (peer) layers at different nodes communicate.

Functions: a protocol defines the format and the order of messages exchanged between two or more communicating nodes, as well as the actions taken on the transmission and/or receipt of a message.

يعني: أي تواصل بين جهازين محكوم بـ protocol، والـ protocol بيحدد 3 حاجات: شكل الرسالة، ترتيب الرسايل، والأكشن عند الإرسال والاستقبال.

(b)Describe the polling protocol.

الإجابة

A taking-turns protocol: one node is designated as the master.
The master sends a message to node 1, saying it can transmit up to some maximum number of frames. After node 1 transmits, the master tells node 2 it can transmit, and so on.
The master determines when a node has finished by observing the lack of a signal on the channel. The procedure continues in a cyclic manner.
Advantage: eliminates the collisions and empty slots of random access → much higher efficiency.
Drawbacks: polling delay (time needed to notify a node; if only one node is active it transmits at a rate less than R); if the master node fails, the entire channel becomes inoperative.

يعني: فيه master بيدي الإذن لكل جهاز بالدور يبعت لحد عدد معين من الـ frames، ولما الإشارة تقف يروح للي بعده. مفيش collisions، بس فيه وقت ضايع في السؤال، ولو الـ master وقع القناة كلها تقف.

(c)Describe the Ethernet service type. = ASG3 P2d

الإجابة

Connectionless: no connection is established between the sending and receiving adapters before sending a frame.
Unreliable: the receiving adapter does not send a positive or a negative acknowledgment. If a frame fails the CRC check, it is simply discarded.
The application-layer protocol (e.g. using TCP) is responsible for detecting gaps in the data; if the sender retransmits, Ethernet does not know whether the frame is new data or retransmitted data.

يعني: الإيثرنت مش بيعمل اتصال قبل ما يبعت، ومش بيرد بـ ACK أو NACK. الـ frame اللي الـ CRC بتاعها غلط بتترمي، والطبقات اللي فوق هي اللي تكتشف الناقص.

(d)Explain the types of routers used with the OSPF hierarchical routing. = ASG5 P1d · Mid 2021

الإجابة

Internal routers: in non-backbone areas; perform only intra-area routing.
Area border routers: belong to both an area and the backbone.
Backbone routers: perform routing within the backbone but are not area border routers.
Boundary routers: exchange routing information with routers belonging to other autonomous systems.

OSPF router types slide — Slide 77 · ارسم الشكل ده جنب الإجابة

يعني: internal جوه area، area border بين area والـ backbone، backbone جوه الـ backbone بس، boundary بيكلم ASs تانية.

Problem 2 — 7 points

same as ASG2 P2

السؤال الأصلي

3 nodes share a broadcast channel. Node 1 has 1 frame, node 2 has 3, node 3 has 5. Frame size = 20 bits. Rate R = 60 bit/s.

أول حاجة دايمًا: وقت الـ frame الواحدة = L / R = 20 / 60 = 1/3 s. كل الأسئلة بتتحل من الرقم ده.

(a)Explain how the size of a slot will be chosen using (i) TDM with 1 second time frame, (ii) Slotted Aloha.

الإجابة

TDM: الـ time frame بيتقسم على عدد الـ nodes. ALOHA: الـ slot = وقت frame واحدة.

(i) TDM: the 1 s time frame is divided into N = 3 slots → slot = 1/3 s, one slot per node. In one slot a node sends 60 × 1/3 = 20 bits = exactly 1 frame.

(ii) Slotted ALOHA: slot = time to transmit one frame = L/R = 20/60 = 1/3 s.

يعني: في الحالتين الـ slot طلع 1/3 ثانية، بس السبب مختلف: في TDM عشان قسمنا الثانية على 3 nodes، وفي ALOHA عشان ده وقت frame واحدة.

(b)Explain how the frames will be transmitted using (i) TDM with 1 s time frame, (ii) FDM, (iii) draw a schematic.

الإجابة

(i) TDM: every 1 s time frame = [node 1 | node 2 | node 3], 1/3 s each. Each node sends one frame per time frame at the full 60 bit/s. Node 1 finishes in the 1st time frame, node 2 in the 3rd, node 3 in the 5th. The slots of nodes that have nothing left stay empty (wasted).

TDM, 1 s time frame — each box = one 20-bit frame (1/3 s)

(ii) FDM: the channel is divided into 3 frequency bands of 60/3 = 20 bit/s each. All nodes transmit at the same time, each on its own band; one frame takes 20/20 = 1 s.

FDM — three 20 bit/s channels in parallel

يعني: TDM = كل واحد بياخد دوره في الوقت بالسرعة الكاملة. FDM = الكل بيبعت مع بعض طول الوقت بس كل واحد بسرعة أقل (تلت السرعة).

(c)How long will it take for the frames of each node to reach the destination using (i) TDM 1 s, (ii) TDM 2 s, (iii) FDM, (iv) CDMA?

الإجابة

اعرف الـ slot = T ÷ 3، وفيه كام frame (slot ÷ 1/3).
لكل node: احسب هتحتاج كام time frame. آخر frame بتتبعت في الـ time frame الأخير.
الوقت = (عدد الـ time frames الكاملة اللي قبلها × T) + بداية الـ slot بتاع الـ node + (عدد الـ frames في آخر slot × 1/3).
FDM: عدد الـ frames × (20 ÷ 20). CDMA: عدد الـ frames × (20 ÷ 60) لأنه بياخد السرعة كلها.

	Node 1 (1 frame)	Node 2 (3 frames)	Node 3 (5 frames)
(i) TDM 1 s · slot 1/3 s · 1 frame/slot	1/3 s	2 + 1/3 + 1/3 = 2⅔ s	4 + 2/3 + 1/3 = 5 s
(ii) TDM 2 s · slot 2/3 s · 2 frames/slot	1/3 s	2 + 2/3 + 1/3 = 3 s	4 + 4/3 + 1/3 = 5⅔ s
(iii) FDM · 20 bit/s each	1 × 1 = 1 s	3 × 1 = 3 s	5 × 1 = 5 s
(iv) CDMA · 60 bit/s each, simultaneously	20/60 = 1/3 s	60/60 = 1 s	100/60 = 5/3 s

مثال node 3 في (ii): الـ 5 frames محتاجين 3 time frames (2 ثم 2 ثم 1). آخر frame بتتبعت في الـ time frame التالت، بعد الـ slots بتوع node 1 و node 2:

4      (two full 2-s time frames)
+ 4/3  (slots of node 1 and node 2: 2 × 2/3)
+ 1/3  (one frame)
= 5 2/3 s

TDM, 2 s time frame — slot 2/3 s fits 2 frames

يعني: CDMA أسرع حاجة لأن كل node بياخد السرعة كلها في نفس الوقت. TDM بيضيع وقت في الـ slots الفاضية، وFDM كل واحد بطيء بس مش بيستنى.

Problem 3 — 8 points

السؤال الأصلي

7 routers (A–G), 2 switches (j, k), one wireless access point (x), 4 hosts (n, p, q, r).

Mid 2026 problem 3 topology — Exam figure (red lines drawn by a student) · F–k–G through switch k = 2 + 1 = 3

Router graph used in the solution (switch k merged into F–G = 3)

قبل أي حاجة: شيل الـ switches من الحسبة واجمع تكاليفها. F–k–G = 2 + 1 = 3. الـ hosts (n, p, q, r) والـ AP (x) مش بيدخلوا في جداول الـ routing.

(a)Does the data link layer of host n have to implement 802.11 technology to receive frames from host q? Explain.

الإجابة

فكّر: الـ link layer شغالة على لينك واحد بس. الـ frame بتتعمل من جديد عند كل راوتر.

No. The data link layer works over a single link only. Only q's link to the access point x uses 802.11. The frame from q ends at the router A interface: router A passes the datagram to its network layer and builds a new frame for the link A–n, using that link's technology (e.g. Ethernet). Host n only needs to implement the link-layer technology of its own link to A.

يعني: لأ. الـ 802.11 على اللينك بتاع q بس. الراوتر A بيفك الـ frame ويعمل frame جديدة بتكنولوجيا اللينك اللي بينه وبين n (Ethernet مثلًا)، فـ n مش محتاج يفهم 802.11.

(b)RIP is used. (i) Routing table at A at steady state. (ii) Routing tree.

الإجابة

RIP = hop count: عدّ اللينكات بين الراوترات من غير تكلفة، وزوّد 1 (A نفسه = 1). A ليه جار راوتر واحد بس (B)، فكل الطرق next router = B.

RIP tree at A: E via C (3 links) not via D (4 links); G via F

يعني: RIP بيختار أقل عدد لينكات. عشان كده E بيتوصل لها عن طريق C (A–B–C–E) مش عن طريق D، حتى لو التكلفة أعلى.

(c)(i) Dijkstra from A: order of nodes added and path costs. (ii) Routing tree.

الإجابة

الصف الأول = جيران A بس (B = 2). كل خطوة اختار أرخص نود لسه مادخلتش N وحدّث جيرانها. D و G بنفس التكلفة (6) — اختار أي واحد واكتب إنه tie.

Order: A, B(2), F(3), C(5), D(6), G(6), E(7) · tree A–B, B–F, B–C, C–D, D–E, F–G

يعني: بالتكلفة، E أرخص عن طريق D (2+3+1+1 = 7) مش عن طريق C مباشرة (2+3+3 = 8). ده الفرق بين OSPF/Dijkstra وRIP.

(d)Routers are multicast-capable. Explain the group-shared center-based algorithm with A as center; routers join in order F, G, C, D, E, B.

الإجابة

كل راوتر بيبعت join message بالـ unicast ناحية الـ center A على أقصر طريق بتاعه.
الـ join بتقف عند أول راوتر موجود في الشجرة (أو عند A).
الطريق اللي مشيته الـ join يتضاف كفرع. امشي بالترتيب المطلوب.

F joins: F’s unicast path to A is F → B → A. Neither B nor F is on the tree, so the join goes all the way to A → branch A–B–F is added.
G joins: path G → F → B → A. The join reaches F, which is already on the tree → branch F–G is grafted.
C joins: path C → B → A. B is on the tree → branch B–C.
D joins: path D → C → … C is on the tree → branch C–D.
E joins: least-cost path E → D → C → B → A (cost 7). D is on the tree → branch D–E.
B joins: B is already on the tree (it was added as an intermediate router when F joined) → nothing is added.

Final group-shared tree: A–B, B–F, F–G, B–C, C–D, D–E

لو اعتبرت إن الـ unicast routing هو RIP (من part b)، فرق واحد بس: E هتبعت الـ join على E → C (أقل hops)، فالفرع يبقى C–E بدل D–E. اكتب أنهي routing استخدمت.

يعني: الشجرة بتتبني فرع فرع: كل راوتر يمشي ناحية A لحد ما يخبط في الشجرة. B دخل الشجرة بدري لأنه في طريق F، فلما جه دوره ماحصلش حاجة.

MIDTERM · NOV 18, 2024 · TERM 2024/2025Mid 2025

0/3

امتحان السنة اللي فاتت. P1 وP2 نظري وحسابات صغيرة من الأسايمنتس، وP3 مسألة topology كاملة (IP، Dijkstra، ARP، spanning tree).

Problem 1 — 5 points

السؤال الأصلي

(a)Three categories of multiple access protocols, one example each.

الإجابة

Channel partitioning protocols — e.g. TDM (also FDM, CDMA).
Random access protocols — e.g. slotted ALOHA (also CSMA).
Taking-turns protocols — e.g. polling (also token passing).

يعني: تقسيم القناة (بالوقت/التردد/الكود)، عشوائي (ابعت ولو حصل collision أعد)، بالدور (master أو token).

(b)Topology, speed and coverage area of (i) 10Base2, (ii) 100BaseT.

الإجابة

	Topology	Speed	Coverage
10Base2	Bus (thin coaxial cable)	10 Mbps	≈ 200 m: max 185 m per segment, 30 nodes; up to 4 repeaters → 925 m, 150 nodes
100BaseT	Star (nodes connected to a hub, twisted pair)	100 Mbps	Max 100 m between an adapter and the hub

يعني: 10Base2 سلك coax واحد الكل عليه (bus) بسرعة 10 ولحد 185 متر للـ segment. 100BaseT كل جهاز بسلك twisted pair لـ hub (star) بسرعة 100 ولحد 100 متر.

(c)In IEEE 802.11, SIFS must be shorter than DIFS. Why?

الإجابة

A station starts a new transmission only after sensing the channel idle for DIFS, while the receiver of a correct frame waits only SIFS before sending its ACK (and SIFS is also used before CTS and DATA in RTS/CTS). Because SIFS < DIFS, the ACK/CTS is sent before any other station can see the channel idle for DIFS → response frames get priority and no other station interrupts the ongoing exchange.

يعني: الرد (ACK أو CTS) لازم يطلع قبل ما أي جهاز تاني يلحق يشوف القناة فاضية مدة DIFS ويبدأ يبعت. فـ SIFS أقصر عشان الرد ياخد أولوية.

(d)Variables that could affect a path cost (mention three).

الإجابة

Physical length/distance of the link · link speed / bandwidth · delay · traffic load (congestion) · reliability · monetary cost · hop count. (Any three.)

يعني: تكلفة اللينك ممكن تتحسب من المسافة، السرعة، التأخير، الزحمة، الموثوقية، الفلوس، أو عدد الـ hops. اكتب أي 3.

(e)(i) Why is pruning used in RPF? (ii) How does pruning work?

الإجابة

(i) With RPF, a router forwards the multicast packet on all its other links even if it has no attached hosts in the group → routers without members receive many unwanted packets. Pruning stops this.

(ii) A multicast router that receives multicast packets and has no attached hosts joined to the group sends a prune message to its upstream router. If a router receives prune messages from each of its downstream routers (and has no members itself), it forwards a prune upstream. A router must know which downstream routers depend on it. To rejoin: an unprune message, or pruned branches time out.

يعني: الراوتر اللي ماعندوش أعضاء يقول للي فوقه "ماتبعتليش" (prune). لو كل اللي تحت راوتر بعتوا prune وهو مالوش أعضاء، يبعت prune لفوق هو كمان.

Problem 2 — 6 points

السؤال الأصلي

(a)Advantages and disadvantages of slotted ALOHA.

الإجابة

Advantages: a single active node can continuously transmit at the full rate of the channel; highly decentralized (each node detects collisions and independently decides when to retransmit); simple.

Disadvantages: requires the slots to be synchronized in the nodes; with many active nodes, a fraction of slots have collisions (wasted) and another fraction are empty (all active nodes refrain because of the probabilistic policy) → low efficiency.

يعني: لو لوحدك تاخد السرعة كلها ومفيش master. بس محتاج الكل متزامن، ولما الأجهزة تكتر slots بتضيع في collisions وslots تفضى.

(b)A fiber channel and a wireless channel: suggest a strategy to deal with errors in each.

الإجابة

Fiber (highly reliable, few errors): error detection + retransmission — add only enough redundancy to detect an error (e.g. CRC) and request retransmission.

Wireless (error-prone): error correction — add enough redundancy (e.g. Hamming code) so the receiver can locate and correct errors itself, since retransmissions would be frequent and costly.

يعني: الفايبر أخطاؤه نادرة فكفاية نكتشف ونطلب إعادة. الـ wireless أخطاؤه كتير فالأحسن نصلّح عند المستقبل بدل ما نعيد كل شوية.

(c)CRC with G = 1011, data = 11101011. (i) Transmitted data (show work). (ii) How does the receiver check?

الإجابة

r = 4 − 1 = 3 ← ضيف 3 أصفار ← اقسم بالـ XOR ← آخر 3 bits = الباقي ← حطه مكان الأصفار.

(i) Remainder R = 101 → transmitted T = 11101011 101.

(ii) The receiver divides the received bits (11101011101) by G = 1011 using modulo-2 division. Remainder = 000 → no error detected; remainder ≠ 0 → error detected (frame discarded / retransmission requested).

يعني: المستقبل بيقسم كل اللي وصله على G. لو الباقي أصفار يبقى سليم، لو فيه 1 يبقى فيه غلط.

(d)What is the counting-to-infinity problem and how to overcome it?

الإجابة

In distance-vector routing, when a link cost increases (e.g. X–Y from 4 to 60), Y still believes Z can reach X cheaply (Z’s old cost went through Y). Y routes to X via Z while Z routes to X via Y → a routing loop. Each exchange raises the costs by a small amount, so many iterations are needed (44 in the slides’ example) before the correct route is found: “bad news travels slow”.

Solution — poisoned reverse: if Z routes through Y to get to X, Z advertises to Y that its distance to X is infinity, so Y will never route to X via Z. (It does not solve loops involving three or more nodes.)

Count to infinity slide — Slide 67 · link cost increase

يعني: لما لينك يغلى، راوترين يفتكروا إن الطريق عن طريق بعض، فيعملوا loop والأرقام تزيد ببطء. الحل: لو أنا رايح X عن طريقك أقولك إن مسافتي لـ X = ∞.

Problem 3 — 9 points

السؤال الأصلي

6 routers (A–F), 4 switches (g, h, j, k), 3 hosts (m, n, p).

Mid 2025 problem 3 topology — Exam figure · A–g–D through switch g = 7 + 5 = 12

Router graph (switches merged; h, j, m, n shown on B’s LAN)

(a)How many IP networks? List them.

الإجابة

قاعدة: كل LAN (أجهزة متوصلة بـ switches/hubs من غير راوتر) = network، وكل لينك بين راوترين = network، وكل host متوصل براوتر لوحده = network. الـ switch مش بيفصل networks.

10 IP networks:

A – p
A – g – D (switch g joins A and D)
A – B
B – C
C – D
C – E
D – E
D – F
E – F
B – h, k, j – m, n (one switched LAN)

يعني: 8 لينكات بين راوترات (منهم A–D عن طريق g) + network الـ host p + الـ LAN بتاع B اللي فيها m و n = 10.

(b)Assign IP addresses to this topology.

الإجابة

لكل network من (a) اختار network part مختلف (class C مثلًا)، وادي كل interface فيها رقم host مختلف. الراوتر بياخد IP لكل interface. الـ switches مالهاش IP.

#	Network	Interfaces
1	192.168.1.0	A 192.168.1.1 · p 192.168.1.2
2	192.168.2.0	A 192.168.2.1 · D 192.168.2.2
3	192.168.3.0	A 192.168.3.1 · B 192.168.3.2
4	192.168.4.0	B 192.168.4.1 · C 192.168.4.2
5	192.168.5.0	C 192.168.5.1 · D 192.168.5.2
6	192.168.6.0	C 192.168.6.1 · E 192.168.6.2
7	192.168.7.0	D 192.168.7.1 · E 192.168.7.2
8	192.168.8.0	D 192.168.8.1 · F 192.168.8.2
9	192.168.9.0	E 192.168.9.1 · F 192.168.9.2
10	192.168.10.0	B 192.168.10.1 · m 192.168.10.2 · n 192.168.10.3

يعني: كل network ليها أول 3 أرقام خاصين بيها، وكل جهاز أو interface جواها له الرقم الأخير. الراوتر D مثلًا عنده 4 IPs لأنه على 4 networks.

(c)(i) Dijkstra from A, step by step. (ii) Routing tree.

الإجابة

الصف الأول: B = 3، D = 12 (عن طريق switch g)، الباقي ∞. لاحظ إن D بتتحدث 3 مرات: 12 ← 10 (عن طريق C) ← 9 (عن طريق E) ← 8 (عن طريق F).

Order: A, B(3), C(5), E(6), F(7), D(8) · tree A–B, B–C, C–E, E–F, F–D

يعني: D أرخص لما نلف A–B–C–E–F–D (8) من اللينك المباشر عن طريق g (12) أو من C (10).

(d)All ARP tables are empty: how will the data link layer of host p send a frame to host m?

الإجابة

p و m في networks مختلفة ← p عمره ما هيعرف MAC بتاع m. هو محتاج MAC الراوتر A بس. كل hop بيعمل ARP على اللينك بتاعه.

p’s network layer sees that m is on a different network → next hop = router A (its interface on network 1). It passes the datagram (src IP p, dst IP m) to the DLL with A’s IP.
p’s ARP table is empty → p builds an ARP request (its IP and MAC + A’s IP) and broadcasts it (FF-FF-FF-FF-FF-FF). Only A recognizes its IP and replies with its MAC. p stores A’s IP/MAC/TTL.
p’s adapter sends the frame: src MAC = p, dst MAC = A (interface on network 1).
A passes the datagram to its network layer; the routing table gives next hop B (link A–B). A uses ARP on that link to get B’s MAC, then sends a new frame src MAC A → dst MAC B.
B: m is on its directly attached LAN → B broadcasts an ARP request on that LAN (the switches h, k, j flood it); m replies; B sends a new frame src MAC B → dst MAC m. Switch h forwards it to m (self-learning table).

يعني: p يسأل بالـ broadcast على MAC الراوتر A ويبعتله. A يعمل frame جديدة لـ B، وB يسأل على MAC m في الـ LAN بتاعته ويبعتله. كل frame عناوين الـ MAC فيها بتتغير، والـ IP ثابت.

(e)Is a spanning tree protocol needed? Explain.

الإجابة

دوّر على loop بين switches. لو فيه، الإجابة Yes.

Yes. Switches h, k and j form a loop (h–k, k–j, j–h). Frames (especially broadcasts like the ARP request in (d)) would cycle and multiply forever. The switches run the spanning tree protocol to agree on a loop-free tree and disable one interface, e.g. the link h–j, leaving h–k–j. (Switch g has no redundant path.)

يعني: أيوه، لأن h و k و j متوصلين في دايرة. الـ broadcast هيفضل يلف ويتضاعف، فلازم يقفلوا لينك واحد منهم (مثلًا h–j).

MIDTERM · NOV 20, 2023 · TERM 2023/2024Mid 2023

0/2

ده الامتحان الوحيد اللي معانا نموذج إجابة الدكتورة بتاعه (Mid 2023-solution.pdf). الإجابات اللي عليها علامة "✓ official" متطابقة معاه. مفيد جدًا عشان تعرف طريقة تصحيحها.

Problem 1 — 13 points

السؤال الأصلي

AS-X: 2 routers (A, B), 3 switches (r, s, u), 2 hubs (i, p), 4 hosts (c, d, e, f). AS-Y: 10 routers (Q, G, H, J, K, M, N, T, V, W).

(a)Is a spanning tree protocol needed in AS-X? If yes, draw the topology after applying it.

الإجابة

No ✓ official. The switches u, r and s are connected without any redundant path between them (u and s are even in different LANs, separated by router A), so there is no loop for frames to cycle in.

يعني: مفيش loop بين الـ switches، فمش محتاجين spanning tree. (الحل الرسمي قال No بالرغم من الخط اللي بين i و p في الرسمة.)

(b)Assign MAC addresses in AS-X.

الإجابة

MAC لكل adapter: الـ host له 1، والراوتر له 1 لكل interface. الـ switches والـ hubs مالهمش MAC.

10 MAC addresses ✓ official: 4 for router A (interfaces to u’s LAN, to e, to s’s LAN, and to Q in AS-Y), 2 for router B (to s’s LAN and to f), and 1 for each host c, d, e, f.

Interface	MAC
A1 (u LAN) · A2 (e) · A3 (s LAN) · A4 (to Q)	AA-AA-AA-AA-AA-11 … -14
B1 (s LAN) · B2 (f)	BB-BB-BB-BB-BB-11 , -12
c · d · e · f	CC-…-11 · DD-…-11 · EE-…-11 · FF-…-11

يعني: عدّ الـ adapters: A عنده 4 كروت، B عنده 2، وكل host كارت واحد = 10.

(c)ARP table of d (d recently communicated with all other nodes in AS-X).

الإجابة

الـ ARP table فيها بس الأجهزة اللي على نفس الـ LAN بتاعة d (الـ LAN بتاعة switch s). e و f ورا راوترات، فـ d بيوصلهم عن طريق MAC الراوتر. وIPs الراوترات لازم تكون من نفس الـ LAN.

Used for	IP	MAC	TTL
e (via router A)	223.128.150.1 (A3)	AA-AA-AA-AA-AA-13	13:05
f (via router B)	223.128.150.2 (B1)	BB-BB-BB-BB-BB-11	13:06
c	223.128.150.3	CC-CC-CC-CC-CC-11	13:07

✓ official: “For hosts e and f, must use the MAC address of the routers. IP addresses for routers A and B must belong to the same LAN.”

يعني: 3 صفوف بس: الراوتر A والراوتر B (بالـ interface اللي على LAN بتاعة d) وc. d ماعندوش MAC بتاع e أو f.

(d)Explain how a switch table is built.

الإجابة

Self-learning: the table is initially empty. For each frame received, the switch stores the frame’s source MAC address, the interface it arrived on, and the current time. If the destination is not in the table, the switch forwards copies to all other interfaces.

Using the table ✓ official: when a frame for c arrives on interface x, the switch looks up c’s interface y. If x = y, the frame comes from c’s own segment → no forwarding needed, discard. If x ≠ y, the frame is put in the output buffer that precedes interface y.

يعني: الجدول بيتعلم لوحده من الـ source بتاع كل frame. ولما frame تيجي، لو جت من نفس بورت الوجهة يرميها، غير كده يبعتها على بورت الوجهة.

(e)Switch table for s (recent communication between all nodes in AS-X).

الإجابة

مين بيدخل s مباشرة؟ الراوتر A (بورت 1)، c (بورت 2)، و d و الراوتر B (بورت 3). e و f ورا راوترات فمش هيظهروا.

Address	Interface	Time
AA-AA-AA-AA-AA-13 (A)	1	9:30
CC-CC-CC-CC-CC-11 (c)	2	9:31
DD-DD-DD-DD-DD-11 (d)	3	9:32
BB-BB-BB-BB-BB-11 (B)	3	9:33

✓ official: A → 1, c → 2, d → 3, B → 3 (−0.5 for each missing, nonexistent or wrong entry).

يعني: 4 صفوف بس. e و f عمرهم ما هيظهروا لأن الراوتر بيحط MAC بتاعه على الـ frame.

(f)RIP in AS-Y: (i) routing table at N (steady state), (ii) routing tree.

الإجابة

عدّ اللينكات من N من غير تكلفة وزوّد 1 (N نفسه = 1). جيران N: G، H، K، M.

✓ official tree: G, H, K, M direct · T via H · V, W via T · Q, J via K

يعني: RIP بيختار أقل لينكات: Q عن طريق K (لينكين) مع إن Q–J–K أرخص في التكلفة.

(g)Group-shared center-based tree with N as center: draw the tree after Q and W join.

الإجابة

الـ join بتمشي على طريق الـ unicast routing المستخدم (هنا RIP من part f) ناحية N.

Q joins: RIP path Q → K → N → branch Q–K–N. W joins: RIP path W → T → H → N → branch W–T–H–N.

✓ official: Q–K (6), K–N (4), W–T (3), T–H (3), H–N (3)

ملاحظة مهمة من نموذج الإجابة: الدكتورة مشّت الـ join على طريق RIP (Q–K–N) مش على أرخص طريق بالتكلفة (Q–J–K–N). يعني استخدم الـ routing اللي في السؤال.

يعني: كل راوتر يمشي ناحية المركز N بطريق RIP، والطريق ده يبقى فرع في الشجرة.

Problem 2 — 7 points

السؤال الأصلي

(a)(i) Explain CSMA/CD of Ethernet. (ii) Explain its exponential backoff.

الإجابة

(i) ✓ official Ethernet adapters sense the channel by measuring voltage levels. The adapter places a frame in its buffer. If the channel is idle (no signal energy) it starts transmitting; if busy it waits until it senses no signal energy (plus a few hundred microseconds). While transmitting, it monitors for signal energy from other adapters and aborts if detected, then sends a 48-bit jam signal so all other transmitting adapters detect the collision.

(ii) After the n-th collision in a row for a frame, the adapter picks K at random from {0, 1, 2, …, 2ᵐ − 1}, m = min(n, 10), and waits K × 512 bit times before retrying. The set grows exponentially with the number of collisions (until n = 10), so the wait adapts to the number of senders. Collisions from the past are not considered when sending a new frame.

يعني: اسمع، لو فاضي ابعت، لو حصل collision وقف وابعت jam. بعد كل collision استنى وقت عشوائي، والمدى بتاعه بيتضاعف مع كل collision.

(b)How could a queue build up at the input and output ports of a router?

الإجابة

✓ official n input/output ports with the same speed (Vi = Vo) and switching speed Vs ≥ n·Vi: output worst case — the packets arriving at each of the n inputs go to the same output port: n packets arrive, 1 leaves → n − 1 queued; if memory becomes full, packets are dropped. If Vs < n·Vi, queuing occurs at the input ports (also HOL blocking).

يعني: عند الـ output لما كله رايح لنفس المخرج. عند الـ input لما الـ fabric أبطأ من مجموع المداخل.

(c)CDMA: code length 4 chips, each data bit needs two data slots. Codes (−1, 1, 1, −1) and (1, −1, 1, −1). Both senders transmit (−1, −1, 1). (i) Sender 1 output, (ii) sender 2 output, (iii) receiver recovers sender 1.

الإجابة

"two data slots" = الكود بيتكرر مرتين لكل bit (8 chips).
خرج كل sender = الـ bit × الكود (×2).
القناة = مجموع الاتنين chip بـ chip.
الفك: اضرب في كود sender 1، اجمع، واقسم على 8.

(i)  Sender 1, code c1 = (−1, 1, 1, −1):
     bit −1 → ( 1,−1,−1, 1,  1,−1,−1, 1)
     bit −1 → ( 1,−1,−1, 1,  1,−1,−1, 1)
     bit  1 → (−1, 1, 1,−1, −1, 1, 1,−1)
(ii) Sender 2, code c2 = (1, −1, 1, −1):
     bit −1 → (−1, 1,−1, 1, −1, 1,−1, 1)
     bit −1 → (−1, 1,−1, 1, −1, 1,−1, 1)
     bit  1 → ( 1,−1, 1,−1,  1,−1, 1,−1)
(iii) Arriving at receiver (sum):
     bit 1: ( 0, 0,−2, 2,  0, 0,−2, 2)
     bit 2: ( 0, 0,−2, 2,  0, 0,−2, 2)
     bit 3: ( 0, 0, 2,−2,  0, 0, 2,−2)
     × c1 (repeated twice) and sum:
     bit 1: 0+0−2−2+0+0−2−2 = −8 → −8/8 = −1
     bit 2: −8 → −1
     bit 3: 0+0+2+2+0+0+2+2 = +8 → +1
     Sender 1 data = (−1, −1, 1) ✓

يعني: الضرب في كود sender 1 بيلغي sender 2 تمامًا (لأن الكودين orthogonal)، فبيرجعلك كلام sender 1 بس.

MIDTERM · NOV 21, 2022 · TERM 2022/2023Mid 2022

0/4

نفس AS-Y بتاعة Mid 2023 بس اسم Q هنا F. ومسألة الـ CRC نفسها اتكررت في Mid 2025.

Problem 1 — 5 points

السؤال الأصلي

(a)CRC with G = 1011, data = 11101011: (i) transmitted data, (ii) receiver check.

الإجابة

نفس مسألة Mid 2025 بالظبط: 3 أصفار، قسمة XOR، الباقي 101.

(i) T = 11101011 101. (ii) The receiver divides the received frame by G; remainder 000 → no error, otherwise an error is detected.

(b)(i) Minimum distance to correct 2 errors? (ii) How many errors can be detected with it? (iii) Hamming code for 24 message bits correcting a single error: minimum check bits?

الإجابة

Correct d errors ← distance 2d+1. Detect d errors ← distance d+1. Hamming: جرّب r في m + r + 1 ≤ 2ʳ.

(i) 2d + 1 = 2(2) + 1 = 5.

(ii) distance 5 = d + 1 → d = 4 errors can be detected.

(iii) m = 24: r = 4 → 29 ≤ 16 ✗ · r = 5 → 30 ≤ 32 ✓ → r = 5 check bits. Because each of the 2ᵐ legal messages needs n + 1 bit patterns (itself + n single-error patterns): (n + 1)·2ᵐ ≤ 2ⁿ → m + r + 1 ≤ 2ʳ.

يعني: عشان تصلّح غلطتين محتاج الكلمات تبعد عن بعض 5 bits، والمسافة دي بتكفي تكتشف 4 أخطاء. ولـ 24 bit داتا محتاج 5 bits فحص.

Problem 2 — 3 points

السؤال الأصلي

A = 01111110 · B = 01010101 · E = ESC = 00001111 · F = FLAG = 11110000 · frames [A, E, B, F] and [A, E, F]

(a)Character count.

الإجابة

5 A E B F | 4 A E F

يعني: الرقم = عدد الحروف + 1 (العدّاد نفسه).

(b)Flag bytes with byte stuffing.

الإجابة

FLAG A ESC ESC B ESC FLAG FLAG | FLAG A ESC ESC ESC FLAG FLAG

يعني: FLAG في الأول والآخر، وESC قبل أي E أو F جوه الداتا. الـ bold = اللي اتزود.

(c)Starting and ending flags with bit stuffing.

الإجابة

الـ flag هنا 01111110 (مش الحرف F). خد بالك إن الحرف A نفسه = 01111110 فلازم يتعمله stuffing. وعدّ الـ 1 المتتالية عبر الحروف (E بيخلص بـ 1111 و F بيبدأ بـ 1111).

Frame 1: 01111110 011111010 00001111 01010101 111100000 01111110

Frame 2: 01111110 011111010 00001111 101110000 01111110

يعني: في frame 1 الـ 1 اللي في آخر B + أول 4 bits في F = خمسة، فـ 0 بعد رابع bit في F. في frame 2 آخر 4 bits في E + أول bit في F = خمسة، فـ 0 بعد أول bit في F.

Problem 3 — 5 points

السؤال الأصلي

(a)Two principles of CSMA.

الإجابة

Carrier sensing: a node listens to the channel before transmitting; if a frame from another node is being transmitted, it waits a random amount of time and senses again; if idle, it transmits. Collision detection: a node listens while it is transmitting; if another node is transmitting, it stops and uses a protocol to decide when to retransmit.

يعني: اسمع قبل ما تبعت، واسمع وإنت بتبعت.

(b)(i) Min and max data size in Ethernet? (ii) How does Ethernet deal with smaller or larger data?

الإجابة

(i) Min 46 bytes, max 1500 bytes (MTU). (ii) Larger than 1500 → the host must fragment the datagram. Smaller than 46 → the data field is stuffed (padded) to 46 bytes; the receiving network layer uses the length field in the datagram header to remove the stuffing.

يعني: أكبر من 1500 تتقطع، أقل من 46 تتحشى لحد 46، والمستقبل يشيل الحشو بالـ length field.

(c)How can the hidden station problem be avoided?

الإجابة

Using RTS/CTS: the sender sends a short Request To Send; the receiver replies with Clear To Send, which is heard by all stations near the receiver, including the hidden ones; they set their NAV and defer for the duration. Collisions can only involve the short RTS/CTS frames, not the data.

يعني: الـ CTS اللي بيبعتها المستقبل بتوصل لكل اللي حواليه حتى المستخبيين عن الراسل، فيسكتوا.

Problem 4 — 9 points

السؤال الأصلي

AS-X: 2 routers (A, B), 4 switches (c, d, e, i), 5 hubs (p, q, r, s, u). AS-Y: 10 routers (F, G, H, J, K, M, N, T, V, W).

Mid 2022 AS-Y — AS-Y (F = Q of Mid 2023)

(a)How many LANs in AS-X? Names of the routers, switches and hubs in each.

الإجابة

الراوتر هو اللي بيفصل LANs. امشي من كل interface في A و B وشوف إيه اللي متوصل بيه من غير ما تعدي على راوتر.

3 LANs:

Switches e, i + hubs p, q + router A (interface 1).
Switch d + hub r + router A (interface 2) + router B (interface 1).
Switch c + hubs s, u + router A (interface 3) + router B (interface 2).

(A’s 4th interface is the inter-AS link to router F in AS-Y, not a LAN inside AS-X.)

يعني: الراوترات A و B بيقسموا AS-X لـ 3 LANs. كل switch وhub بيتبع الـ LAN اللي متوصل بيها.

(b)Can hubs s and u use a different technology? Explain.

الإجابة

Yes. s and u are each connected to switch c, not to each other through hubs. A switch isolates each segment as a separate collision domain and can interconnect different LAN technologies (e.g. s 10BaseT, u 100BaseT). Only nodes joined through hubs must use the same technology.

يعني: أيوه، لأن اللي بينهم switch مش hub، والـ switch بيعرف يوصل تكنولوجيات مختلفة.

(c)RIP: (i) routing table at F (steady state), (ii) routing tree.

الإجابة

جيران F: J و K بس. عدّ اللينكات وزوّد 1. أي حاجة تحت K أقرب عن طريق K.

RIP tree at F

(d)Center-based tree with F as center: (i) how G and M join, (ii) draw the tree.

الإجابة

زي Mid 2023: الـ join تمشي على طريق RIP ناحية F، وتقف عند أول راوتر في الشجرة.

(i) G sends a join message toward F along its RIP route G → N → K → F; none of these is on the tree yet → the whole path becomes a branch. Then M sends a join along M → K → F; K is already on the tree → only M–K is grafted.

Tree: F–K, K–N, N–G, K–M

يعني: G بيعمل الفرع الطويل لحد F، وM بيتوصل بأقرب راوتر في الشجرة (K).

MIDTERM · NOV 30, 2021 · TERM 2021/2022Mid 2021

0/3

أقدم امتحان. P2 هو ASG2 P2 بنفس الأرقام بالظبط، وP1(b) هو ASG2 P3(a).

Problem 1 — 4 points

السؤال الأصلي

(a)Difference between error detection and error correction; when should each be used?

الإجابة

Detection: include only enough redundancy to deduce that an error occurred (not where) and request a retransmission → used on highly reliable channels such as fiber. Correction: include enough redundancy for the receiver to determine the error locations and correct them → used on channels with many errors such as wireless links.

يعني: detection نعرف إن فيه غلط ونطلب إعادة (فايبر). correction نصلّح بنفسنا (wireless).

(b)Are [−1 −1 1 1 −1 −1 1 1] and [1 −1 1 1 −1 1 −1 1] mutually orthogonal? = ASG2 P3a

الإجابة

(−1)(1)+(−1)(−1)+(1)(1)+(1)(1)+(−1)(−1)+(−1)(1)+(1)(−1)+(1)(1) = −1+1+1+1+1−1−1+1 = 2 ≠ 0

Not orthogonal: the sum of the bit-wise products of the two codes must be 0.

(c)Types of routers used with OSPF hierarchical routing.

الإجابة

Internal routers (intra-area routing only, non-backbone areas) · Area border routers (belong to an area and the backbone) · Backbone routers (route within the backbone, not area border) · Boundary routers (exchange routing info with other ASes). — same as Mid 2026 P1(d).

Problem 2 — 8 points

identical to ASG2 P2

السؤال الأصلي

Node 1: 1 frame, node 2: 8, node 3: 3 · 25 bits · 150 bit/s → one frame = 1/6 s.

(a–c)Slot sizes, transmission, and times.

الإجابة

(a) TDM slot = 1/3 s (holds 2 frames) · slotted ALOHA slot = 1/6 s. (b) Schematics: see Assignment 2 · P2.

	Node 1	Node 2	Node 3
TDM 1 s	1/6 s	3⅔ s	1⅚ s
TDM 2 s	1/6 s	3⅓ s	1⅚ s
FDM (50 bit/s)	0.5 s	4 s	1.5 s
CDMA	1/6 s	4/3 s	1/2 s

يعني: نفس حل الأسايمنت 2 بالظبط، افتحه هناك للشرح خطوة خطوة والرسومات.

Problem 3 — 12 points

السؤال الأصلي

10 routers (J, K, L, M, N, O, P, Q, R, T).

Same graph redrawn

(a)(i) Shortest paths from R using the OSPF algorithm (show steps). (ii) Routing tree.

الإجابة

OSPF = Dijkstra بالتكاليف. جيران R: Q = 2، O = 8. فيه tie مرتين (M و O = 8، و K و N = 9)، وJ ممكن توصلها من K أو L بنفس التكلفة 11.

Tree: R–Q, Q–T, T–P, P–M, M–K, M–N, K–L, K–J (or L–J, tie), R–O

يعني: أغلب الشبكة أرخص لما نروح من تحت (R–Q–T–P–M) لأن اللينك R–O غالي (8). O بس اللي بنوصلها مباشرة.

(b)RIP: (i) routing table at R, (ii) routing tree.

الإجابة

عدّ اللينكات من غير تكلفة. هنا R–O بقى زيه زي أي لينك (1)، فحاجات كتير هتبقى عن طريق O.

One possible RIP tree (M is a tie: via Q–P or via O–N)

يعني: بالـ hops، R–O–L–J لينكات أقل من الطريق الطويل من تحت، فـ RIP بيختار O رغم إن تكلفته 8.

(c)RPF: explain how a packet originating at R moves step by step until it reaches all routers.

الإجابة

لكل راوتر حدد "اللينك اللي على أقصر طريقه لـ R" من شجرة part (a). الباكت اللي تيجي منه تتقبل وتتبعت على كل اللينكات التانية. أي نسخة تيجي من لينك تاني تترمي.

R sends the packet to Q and O.
Q (from R: on its shortest path) accepts → forwards to P and T. O (from R) accepts → forwards to L and N.
T (from Q) accepts → forwards to P. P discards the copy from Q (P’s shortest path to R is via T), accepts the copy from T → forwards to M and Q (Q discards it).
M (from P) accepts → forwards to K and N. N discards the copy from O, accepts the copy from M → forwards to L and O (both discard).
K (from M) accepts → forwards to J and L. L discards the copies from O and N, accepts the one from K → forwards to J, N, O (all discard). J accepts from K → forwards to L (discard).

Green = accepted (arrives on shortest path to R) · red dashed = discarded

يعني: كل راوتر بيقبل الباكت مرة واحدة بس (من ناحية أقصر طريق لـ R) ويوزعها على الباقي، وأي نسخة تانية بيرميها.

(d)Only R, M and L belong to the group; pruning is used: draw the pruned topology.

الإجابة

ابدأ من شجرة RPF. أي ورقة مش عضو تبعت prune لفوق، وكرر.

Leaves that are not members send prunes upstream: J → K, N → M, O → R. K still has member L below it, so K is not pruned. Pruned tree: R–Q–T–P–M–K–L.

Pruned: J, N, O removed

يعني: اللي ماعندوش أعضاء ومحدش تحته محتاج يتشال. L عضو، فالطريق لحد L لازم يفضل حتى لو فيه راوترات مش أعضاء (Q، T، P، K).

FINAL · DEC 28, 2025 · TERM 2025/2026 · MIDTERM-SCOPE QUESTIONS ONLYFinal 2026

0/3

أحدث فاينال. شيلت الأسئلة اللي من الـ transport layer (P2 c,d) لأنها مش في منهج الميد. الباقي كله من أول 3 بارتس وبنفس أسلوب الميد بالظبط.

Problem 1 — framing, CSMA, checksum, Hamming

السؤال الأصلي

(a)A → B through 1 switch, then 1 router, then another switch. Sketch the encapsulation from the application layer of A to the application layer of B.

الإجابة

ارسم A بالـ 5 طبقات، وبعده switch (Link + Physical)، وبعده router (Network + Link + Physical)، وبعده switch تاني، وفي الآخر B بالـ 5 طبقات. اكتب الـ headers عند كل طبقة.

   A (source)        switch 1        router          switch 2        B (dest)
 Application  M                                                     M  Application
 Transport  Ht|M                                                  Ht|M  Transport
 Network  Hn|Ht|M                 Hn|Ht|M                      Hn|Ht|M  Network
 Link  Hl|Hn|Ht|M   Hl|Hn|Ht|M    Hl|Hn|Ht|M    Hl|Hn|Ht|M   Hl|Hn|Ht|M  Link
 Physical  bits ──▶  bits ──▶     bits ──▶      bits ──▶      bits  Physical

A: M → +Ht (segment) → +Hn (datagram) → +Hl (frame) → bits.
Switches process up to the link layer only (read Hl, forward the same frame).
Router processes up to the network layer: removes Hl, reads Hn, then builds a new frame (new Hl) for the next link.
B: removes Hl, Hn, Ht in turn and delivers M to the application.

يعني: الـ switch بيفتح لحد الـ frame بس، والـ router بيفتح لحد الـ datagram ويعمل frame جديدة. الـ M والـ Ht والـ Hn بيوصلوا زي ما هم.

(b)CSMA, 4 nodes, frame 100 bits, R = 500 bit/s. Delays: 1–2 = 50 ms, 1–4 = 300 ms, 2–3 = 200 ms, 2–4 = 250 ms. Node 1 sends 2 frames to node 4 at t₁ = 20, t₂ = 450 ms. Node 3 sends 2 frames to node 2 at t₃ = 250, t₄ = 870 ms. A node aborts 100 ms after detecting a collision. (i) Space–time diagram, (ii) when does a node abort?

الإجابة

وقت الـ frame = 100 / 500 = 200 ms.
رتّب النودز على السلك من التأخيرات: 1 عند 0، 2 عند 50، 3 عند 250 (50+200)، 4 عند 300 (يتأكد: 1–4 = 300، 2–4 = 250).
لكل إرسال: النود بتسمع الأول. لو الإشارة لسه ماوصلتهاش تبعت. وصول الإشارة لأي نود = وقت البداية + التأخير بينهم.
لو وصلتها إشارة وهي بتبعت → collision → توقف بعد 100 ms.

t = 20: node 1 senses idle → sends frame 1 (20–220). It reaches node 2 at 70–270, node 3 at 270–470, node 4 at 320–520.
t = 250: node 3 senses the channel; node 1’s signal reaches node 3 only at 270 → node 3 thinks it is idle → starts its frame (to node 2).
t = 270: node 3 detects node 1’s signal → collision detected at node 3 → node 3 aborts at 370. Its partial frame (250–370) reaches node 4 at 300–420, node 2 at 450–570, node 1 at 500–620.
Node 4, 320–420: node 1’s frame 1 overlaps node 3’s signal → frame 1 is corrupted at node 4. Node 1 finished at 220, before node 3’s signal reached it (500), so node 1 does not detect this collision.
t = 450: node 1 senses idle (node 3’s signal arrives at 500) → sends frame 2 (450–).
t = 500: node 1 detects node 3’s signal → collision detected at node 1 → node 1 aborts at 600. Its partial frame (450–600) reaches node 2 at 500–650, node 3 at 700–850, node 4 at 750–900.
Node 2, 500–570: node 3’s and node 1’s partial frames overlap → collision at node 2.
t = 870: node 3 senses idle (node 1’s last signal left node 3 at 850) → sends its 2nd frame (870–1070). It reaches node 4 at 920–1120, node 2 at 1070–1270 (received correctly), node 1 at 1120–1320.
(ii) Aborts: node 3 at 370 ms (detected at 270) and node 1 at 600 ms (detected at 500). Both retransmit their aborted frames later after a random backoff.

x = position on the bus (node 1 at 0, 2 at 50, 3 at 250, 4 at 300 ms) · y = time · red bars = collisions at the receiver

يعني: نود 3 بدأت قبل ما إشارة نود 1 توصلها فحصل collision عندها ووقفت. فريم نود 1 الأول باظ عند نود 4 من غير ما نود 1 تعرف. نود 1 لما بعتت التانية جالها إشارة نود 3 فوقفت. آخر فريم من نود 3 عدّى سليم.

(c)Bytes [11000011 00011000 11110100]: checksum with (i) 2-bit and (ii) 3-bit checksumming.

الإجابة

قطّع الـ 24 bit حتت بطول k، حوّل كل حتة لرقم، واجمع، واكتب الناتج بالـ binary.

(i)  2-bit: 11 00 00 11 | 00 01 10 00 | 11 11 01 00
     = 3+0+0+3 + 0+1+2+0 + 3+3+1+0 = 16 = 10000
(ii) 3-bit: 110 000 110 001 100 011 110 100
     = 6+0+6+1+4+3+6+4 = 30 = 11110

يعني: نفس الداتا بتطلع checksum مختلف حسب طول الحتة. الـ 24 bit بيتقسموا على 2 ← 12 حتة، وعلى 3 ← 8 حتت.

(d)Hamming code: limit on the number of check bits r to correct one error in 56 message bits.

الإجابة

(m + r + 1) ≤ 2ʳ وجرّب r.

r = 5 → 56 + 5 + 1 = 62 ≤ 32 ✗ · r = 6 → 63 ≤ 64 ✓ → r = 6

Each of the 2ᵐ legal messages needs n + 1 bit patterns (the codeword + n one-bit errors): (n + 1)·2ᵐ ≤ 2ⁿ → m + r + 1 ≤ 2ʳ.

Problem 2 — router

(c), (d) transport — not in midterm

السؤال الأصلي

(a)Draw how the network address [1010 1100] will be stored in a router.

الإجابة

الجدول متخزن شجرة: كل مستوى = bit. 0 شمال، 1 يمين. امشي bit bit لحد آخر الـ 8.

Root → 1 (right) → 0 (left) → 1 → 0 → 1 → 1 → 0 → 0 · lookup in 8 steps

Routing table entries are stored in a binary tree: each level corresponds to one bit of the address (0 → left, 1 → right), so the lookup takes N steps (N = address length), fast enough for line speed.

(b)Types of switching fabrics with a sketch of each.

الإجابة

Memory: under direct CPU control; input port signals the routing processor by interrupt; the packet is copied into memory, the processor finds the output port and copies it to the output buffer.
Bus: input port sends the datagram directly to the output port over a shared bus without the processor; one packet at a time; busy bus → queued at input; bandwidth limited to bus speed.
Interconnection network (crossbar): 2N buses connect N inputs to N outputs; the packet travels on the horizontal bus until it meets the vertical bus of its output; free → transferred, busy → queued at input.

يعني: memory = البروسيسور بينسخ (بطيء)، bus = سلك مشترك واحدة في المرة، crossbar = شبكة أسلاك كذا باكت مع بعض.

Problem 3 — AS-X & AS-Y (45 points)

السؤال الأصلي

AS-X: 4 routers (A–D), 1 switch (e), 1 hub (u), 1 host (q). AS-Y: 11 routers (F, G, H, J, K, M, N, P, T, V, W), 1 host (r).

Final 2026 topology — Exam figure (pen marks by a student) · D–e–A = 2 + 1 = 3 · A–u–B = 3 + 1 = 4

AS-X routers (switch e and hub u merged)

AS-Y

(a)How many collision domains in AS-X? List them.

الإجابة

كل port في switch = domain لوحده. الـ hub مابيقسمش (كل اللي عليه domain واحد). كل لينك مباشر بين جهازين = domain.

7 collision domains (inside AS-X):

D – switch e (port 1)
switch e (port 2) – A
A – hub u – B (one domain through the hub)
D – B
D – C
C – B
C – q

(The inter-AS link A–F is one more collision domain if it is counted.)

يعني: الـ switch e قسم اللي حواليه لاتنين، والـ hub u خلّى A وB domain واحد، وكل لينك تاني domain لوحده.

(b)How many LANs in AS-X? List them.

الإجابة

هنا الراوتر بس هو اللي بيفصل. الـ switch والـ hub مابيقسموش LAN.

6 LANs:

D – e – A
A – u – B
D – B
D – C
C – B
C – q

(plus the external link A–F to AS-Y.)

يعني: الفرق عن (a): الـ switch e مابيقسمش LAN، فـ D–e–A LAN واحدة بس هي 2 collision domains.

(c)(i) How is the switch table of e built? (ii) Write it (recent communications between all nodes).

الإجابة

(i) Self-learning: initially empty; for each frame received, e stores the source MAC, the arrival interface and the time; unknown destination → forward on all other interfaces. Frame for X arrives on x, table says y: x = y → discard, x ≠ y → forward to y.

Address	Interface	Time
MAC(D, interface to e)	1	9:30
MAC(A, interface to e)	2	9:31

يعني: e عليه جهازين بس (D وA)، وأي frame من حد تاني بتوصله وعليها MAC الراوتر، فالجدول فيه صفين بس.

(d)Distance vector in AS-X: (i) initial tables at C, (ii) steady-state tables at C, (iii) routing tree.

الإجابة

جيران C: B (6) و D (3). اللينكات: A–D = 3 (عن طريق switch e)، A–B = 4 (عن طريق hub u)، D–B 2، D–C 3، C–B 6.

Tree at C: everything via D (A = 6, B = 5, D = 3)

يعني: حتى B أرخص عن طريق D (3 + 2 = 5) من اللينك المباشر (6).

(e)(i) Dijkstra from V in AS-Y: order and path costs. (ii) Routing tree.

الإجابة

Order: V, T(1), W(3), P(4), M(5), K(7), J(8), G(9), F(10), H(11), N(12)

يعني: الشبكة كلها بتطلع من V–T–P–M–K–J–G–F–H–N، كلها لينكات رخيصة (1 و2)، وW لوحدها مباشرة.

(f)Group-shared center-based tree with V as center: (i) how it is built when M, J, F join, (ii) draw it.

الإجابة

الـ join بتمشي على أقصر طريق (من part e) ناحية V وتقف عند أول راوتر في الشجرة.

M joins: path M → P → T → V; nothing on the tree yet → branch M–P–T–V.
J joins: path J → K → M …; M is on the tree → branch J–K–M.
F joins: path F → G → J …; J is on the tree → branch F–G–J.

V–T–P–M–K–J–G–F

(g)RPF with pruning, source V, only M and J in the group: (i) how pruning is applied, (ii) pruned tree.

الإجابة

ابدأ من شجرة Dijkstra (part e). الورقة اللي مش عضو تبعت prune لفوق، وكرر.

W has no group hosts and no downstream routers → prune to V.
N → prune to H; H now has prunes from all downstream routers → prune to F; F → prune to G; G → prune to J.
J is a member → stops. K, M, P, T stay (they lead to members).

Pruned tree: V–T–P–M–K–J

يعني: كل اللي بعد J (G، F، H، N) وW اتشالوا لأن مفيش تحتهم أعضاء.

FINAL · DEC 29, 2024 · TERM 2024/2025 · MIDTERM-SCOPE QUESTIONS ONLYFinal 2025

0/3

شيلت P1 (c, d, e) لأنهم transport وapplication. P2 هو نفس مسألة TDM/FDM/CDMA بـ 5 nodes.

Problem 1 — Hamming & IPv6 transition

السؤال الأصلي

(a)Hamming code correcting one error, m + r = 7: (i) maximum message bits and why? (ii) Example of a legal message and the bit patterns dedicated to it.

الإجابة

n = 7 ثابت. جرّب: m + r + 1 ≤ 2ʳ يعني 8 ≤ 2ʳ ← r ≥ 3 ← m ≤ 4.

(i) n = m + r = 7 and m + r + 1 ≤ 2ʳ → 8 ≤ 2ʳ → r ≥ 3 → m ≤ 4. With m = 5, r = 2: 8 ≤ 4 ✗.

(ii) Example: message 1011 → codeword 0110011 (Hamming(7,4): check bits at positions 1, 2, 4). The n + 1 = 8 patterns dedicated to it: the codeword itself + the 7 one-bit-error patterns:

0110011 · 1110011 · 0010011 · 0100011 · 0111011 · 0110111 · 0110001 · 0110010

يعني: لكل رسالة 8 أشكال محجوزين ليها (الشكل الصح + 7 أشكال فيهم غلطة واحدة)، و16 رسالة × 8 = 128 = 2⁷ بالظبط، فـ m = 4 هو الأقصى.

(b)(i) Methods for transitioning from IPv4 to IPv6, (ii) sketch an example of each.

الإجابة

Dual stack: IPv6 nodes also have a complete IPv4 implementation; they use IPv4 with IPv4 nodes and IPv6 with IPv6 nodes. If any node on the path is IPv4-only, IPv4 is used and IPv6 fields (flow label) are lost. Tunneling: the IPv4 routers between two IPv6 routers form a tunnel; the whole IPv6 datagram is carried as the payload of an IPv4 datagram (src B, dst E) → nothing lost.

Problem 2 — TDM · FDM · CDMA (5 nodes)

السؤال الأصلي

Node 1: 2 frames, node 2: 3, node 3: 1, nodes 4 & 5: none. 40 bits, R = 100 bit/s → one frame = 0.4 s.

(a–c)Slot sizes (TDM 2 s, slotted ALOHA), how frames are sent, and times in a table.

الإجابة

TDM: الـ 2 ثانية بتتقسم على 5 nodes (حتى اللي ماعندهمش حاجة، الـ slot بتاعهم بيضيع) ← slot = 0.4 s = frame واحدة. FDM: 100 ÷ 5 = 20 bit/s لكل node ← frame = 2 s.

(a) TDM slot = 2/5 = 0.4 s (1 frame). Slotted ALOHA slot = L/R = 0.4 s.

(b) TDM: each 2 s frame = [n1 | n2 | n3 | n4 | n5]; nodes 4, 5 slots always empty. FDM: 5 bands of 20 bit/s, nodes 1–3 transmit in parallel.

	Node 1	Node 2	Node 3	Nodes 4, 5
TDM 2 s	2 + 0.4 = 2.4 s	4 + 0.4 + 0.4 = 4.8 s	0.8 + 0.4 = 1.2 s	—
FDM (20 bit/s)	2 × 2 = 4 s	3 × 2 = 6 s	2 s	—
CDMA (100 bit/s)	0.8 s	1.2 s	0.4 s	—

يعني: هنا N = 5 مش 3، والـ slots بتوع node 4 و5 بتضيع في TDM وتردداتهم بتضيع في FDM. ده عيب الـ channel partitioning.

Problem 3 — AS-X & AS-Y

السؤال الأصلي

AS-X: routers A–D, switches e, i, hubs p, q, r, s, u. AS-Y: 9 routers (F, G, H, K, M, N, T, V, W), hosts a, b, d.

(a)ARP table for host d (d recently communicated with all other nodes in AS-Y).

الإجابة

d متوصل بالراوتر K بلينك لوحده. أي جهاز تاني (حتى a وb) في network تانية ← d بيبعتله عن طريق MAC الراوتر K.

IP	MAC	TTL
IP of K’s interface on d’s link (e.g. 200.10.3.1)	MAC of that K interface (e.g. 3C-4A-…-01)	13:45

Only one entry: d’s only neighbor on its LAN is router K; all other nodes are reached through K’s MAC address.

يعني: الـ ARP table فيها الأجهزة اللي على نفس الـ LAN بس، وd مالوش غير K.

(b)(i) Can hubs s and u use different Ethernet technologies? (ii) Can hubs p and q?

الإجابة

(i) No. s and u are both connected to hub r; hubs join them into one collision domain, and all segments connected by hubs must use the same Ethernet technology.

(ii) Yes. p and q are each connected to switch e; a switch isolates segments into separate collision domains and can interconnect different technologies.

يعني: اللي بينهم hub ← لازم نفس التكنولوجيا. اللي بينهم switch ← عادي يختلفوا.

(c)Distance vector in AS-X: (i) initial tables at A and C, (ii) steady table at A, (iii) routing tree.

الإجابة

الراوترات بس: A–B 4، A–C 7، B–C 2، B–D 5، C–D 2.

A–B (4), B–C (6), C–D (8)

(d)(i) Shortest paths from H with OSPF, order and costs. (ii) Tree.

الإجابة

Order: H, N(1), T(2), F(3), G(4), K(5), V(6), W(6), M(7)

(e)Center-based tree with H as center: (i) after K joins, (ii) after K and V join.

الإجابة

(i) K’s least-cost path to H is K → G → H (5) → tree H–G–K. (ii) V joins along V → T → H (6) → add T–V, H–T.

(i)

(ii)

(f)RPF with pruning, source H, group = H, M, V, F: (i) how pruning works, (ii) pruned tree.

الإجابة

On the shortest-path tree from H: K (no members) → prune to G; G then has prunes from all downstream routers and no members → prune to H. W → prune to T. T stays (V below it), N stays (M below it).

H–F, H–N–M, H–T–V

(g)Hosts b and d want to join a multicast group: (i) protocol? (ii) messages used.

الإجابة

(i) IGMP (between the hosts and their directly attached router K).

(ii) Each host sends a membership report to K when its application first joins (or in response to K’s membership query – general/specific, which carries a max response time; a host waits a random time and suppresses its report if it hears another one for the same group on its interface — b and d are on different interfaces of K, so each sends its own). Leave group is optional.

FINAL · DEC 31, 2023 · TERM 2023/2024 · MIDTERM-SCOPE QUESTIONS ONLYFinal 2024

0/2

شيلت Problem 2 كله (transport وapplication). الحلول متراجعة كمان مع حل طالب موجود في الفولدر (solution.pdf) واتطابقت.

Problem 1

السؤال الأصلي

(a)CRC, G = 11001, frame = 1001100111: remainder and transmitted data.

الإجابة

Remainder 0100 · T = 1001100111 0100

(b)Delay A–B = 1.6 ms; A has a frame at t₀ = 0.8 ms, B at t₁ = 2.3 ms. (i) How CSMA is used, (ii) space–time diagram.

الإجابة

0.8: A senses idle → starts transmitting. Its signal reaches B at 0.8 + 1.6 = 2.4 ms.
2.3: B senses the channel; A’s signal has not arrived yet → B thinks the channel is idle → starts transmitting.
2.4: A’s signal reaches B → B detects the collision and aborts shortly after.
3.9: B’s signal (started 2.3) reaches A → if A is still transmitting, A detects the collision and aborts.
Both wait a random backoff, sense the channel again, and retransmit when it is idle.

40 px per ms

يعني: B بدأ قبل ما إشارة A توصله بـ 0.1 ms، فحصل collision، وB اكتشفه الأول (2.4) وA بعده (3.9).

(c)(i) Why Manchester? (ii) Encode 10001110.

الإجابة

(i) Every bit has a transition (1 = high→low, 0 = low→high) → synchronizes the sender’s and receiver’s clocks.

(d)How a routing table entry 101011 is stored.

الإجابة

1 right · 0 left · 1 right · 0 left · 1 right · 1 right

(e)(i) Sketch IPv4 and IPv6 headers. (ii) Fields in both headers (mark ✓).

الإجابة

Exist in both ✓: Version, Source address, Destination address. Same role under a different name: type of service ↔ traffic class, packet length ↔ payload length, upper-layer protocol ↔ next header, time-to-live ↔ hop limit. Only in IPv4: header length, identifier/flags/offset (fragmentation), header checksum, options. Only in IPv6: flow label.

يعني: المشترك بالاسم 3 حقول بس (Version والعنوانين). فيه 4 حقول نفس الوظيفة باسم تاني.

Problem 3 — AS-X & AS-Y

السؤال الأصلي

$Original question f24-3$

Final 2024 topology — Exam figure · AS-X: routers A–D, switches e, i, hubs p, q, r, s, u

(a)How many LANs in AS-X? Draw an oval around each and number them.

الإجابة

6 LANs (+ 1 external link A–F):

Switches e, i + hubs p, q + router A’s interface.
Hubs r, s, u + router D’s interface.
A – D
D – B
B – C
C – A

يعني: كل حاجة متوصلة ببعض من غير راوتر = LAN. حل الطالب في الفولدر برضو 6 + 1 external.

(b)Can hubs s and u use different technologies?

الإجابة

No. s and u are connected through hub r → one collision domain → same Ethernet technology.

(c)(i) Dijkstra from V in AS-Y. (ii) Tree.

الإجابة

W is cheaper the long way (14) than directly (15)

(d)Center-based with V as center: (i) after W joins, (ii) after W and M join.

الإجابة

(i) W’s least-cost path to V is W → M → K → G → F → H → T → V (14) → the whole path becomes the branch. (ii) M is already on the tree → nothing is added.

(e)RPF with pruning, source V, group V, T, N: (i) pruning, (ii) pruned tree.

الإجابة

W → prune to M; M → K; K → G; G → F; F → H. H stays (N below it is a member).

V–T–H–N

(f)RIP: (i) routing table at V, (ii) tree.

الإجابة

يعني: نفس اللي في حل الطالب بالظبط. لاحظ W هنا مباشرة لأن RIP بيعد اللينكات بس.

FINAL · JAN 1, 2023 · TERM 2022/2023 · MIDTERM-SCOPE QUESTIONS ONLYFinal 2023

0/2

شيلت Problem 2 (transport وapplication). AS-Y هنا نفس شبكة Mid 2023 بس Q اسمها F، وAS-X نفس شبكة Final 2024.

Problem 1

السؤال الأصلي

(a)A → D through switch B and router C: block diagram of encapsulation.

الإجابة

A: M → Ht → Hn → Hl → bits. Switch B: up to the link layer. Router C: up to the network layer, then a new frame. D: removes Hl, Hn, Ht and delivers M. (Same figure as Final 2026 P1(a) without the second switch.)

(b)Network adapter relation to host components and protocol stack.

الإجابة

(c)Hamming single-error correction: (i) which of [101001], [101010], [100110] can be legal code words? (ii) 6-bit code: message bits and check bits?

الإجابة

عشان تصلّح غلطة واحدة لازم أي كودين legal يبعدوا عن بعض 3 على الأقل (2d+1). احسب المسافات بالـ XOR.

101001 ⊕ 101010 = 000011 → distance 2
101001 ⊕ 100110 = 001111 → distance 4
101010 ⊕ 100110 = 001100 → distance 2

(i) Correcting one error needs distance ≥ 2(1)+1 = 3. 101001 and 100110 (distance 4) can both be legal codewords; 101010 is at distance 2 from both, so it cannot be legal together with them.

(ii) n = 6: m + r + 1 ≤ 2ʳ → 7 ≤ 2ʳ → r = 3, m = 3 (r = 2: 7 ≤ 4 ✗).

(d)How 802.11 reserves the channel; schematic.

الإجابة

DIFS → RTS (with duration) → SIFS → CTS (heard by all stations near the receiver; they set NAV) → SIFS → DATA → SIFS → ACK.

(e)Types of switching fabrics with sketches.

الإجابة

Memory · Bus · Interconnection network (crossbar) — see Final 2026 P2(b).

(f)Fields of the IPv6 header.

الإجابة

Version · Traffic class (8-bit priority) · Flow label · Payload length (16-bit) · Next header · Hop limit · Source address (128) · Destination address (128) · Data.

Problem 3 — AS-X & AS-Y

السؤال الأصلي

Final 2023 topology — Exam figure (student marks) · F–J = 2 in print

(a)How many LANs in AS-X?

الإجابة

6 (+ external A–F) — same topology as Final 2024 P3(a): (1) e, i, p, q + A · (2) r, s, u + D · (3) A–D · (4) D–B · (5) B–C · (6) C–A.

(b)Is a spanning tree protocol needed in AS-X? If yes, draw the topology after it.

الإجابة

دوّر على دايرة على مستوى الـ link layer (switches/hubs).

Yes. Hubs q and p are connected to each other and each is also connected to switch e → loop e–q–p–e; broadcast frames would cycle. Switch e runs STP and blocks one of these ports (e.g. its port to p). Result: e–q, q–p, e–i, e–A (the link e–p is disabled).

يعني: q وp متوصلين ببعض ومتوصلين بـ e، فـ e لازم يقفل بورت واحد منهم.

(c)Can hubs s and u use different technologies?

الإجابة

No — connected through hub r (same collision domain).

(d)(i) Dijkstra from N. (ii) Tree.

الإجابة

Ties (H/K at 3, G/J/T at 6, F/W at 8) only change the order, not the tree

(e)Center-based with N as center: trees after (i) F, (ii) F and K, (iii) F, K, G join.

الإجابة

الـ join بتمشي على أقصر طريق (Dijkstra من part d).

(i) F → J → K → M → N (8) → branch F–J–K–M–N. (ii) K is already on the tree → no change. (iii) G → H → N (6) → add G–H–N.

(i) = (ii)

(iii)

لو اعتبرت الـ unicast routing هو RIP (part g) زي نموذج Mid 2023: F → K → N، وG → N مباشرة. اكتب أنهي routing استخدمت.

(f)RPF with pruning, source N, group K, G, T, W.

الإجابة

On the tree from N: F → prune to J; J → prune to K (K is a member, stops). V stays (W below it).

(g)RIP: routing table at N and tree.

الإجابة

Same as Mid 2023 P1(f) (F instead of Q).

FINAL · JAN 16, 2022 · TERM 2021/2022 · MIDTERM-SCOPE QUESTIONS ONLYFinal 2022

0/2

شيلت Problem 2 (transport وapplication). الشبكة نفس شبكة Mid 2022 (صورتها أوضح فحطيتها هنا). الحلول متطابقة مع حل الطالب اللي في الفولدر.

Problem 1

السؤال الأصلي

(a)CRC G = 1011, data 11101011.

الإجابة

Same as Mid 2025 P2(c): T = 11101011 101.

(b)CDMA, 4 chips, 3 slots per bit. Node 1 code (1, 1, −1, −1) sends (1, −1); node 2 code (1, −1, −1, 1) sends (−1, −1). Channel output and how node 3 recovers node 1’s data.

الإجابة

Node 1:  bit  1 → ( 1, 1,−1,−1)×3     bit −1 → (−1,−1, 1, 1)×3
Node 2:  bit −1 → (−1, 1, 1,−1)×3     bit −1 → (−1, 1, 1,−1)×3
Channel: bit 1 → ( 0, 2, 0,−2)×3      bit 2 → (−2, 0, 2, 0)×3
Node 3, × c1 and sum, ÷ 12:
  bit 1: 3 × (0 + 2 + 0 + 2) = 12 → 12/12 = +1
  bit 2: 3 × (−2 + 0 − 2 + 0) = −12 → −1
  Node 1 data = (1, −1) ✓

(c)Manchester for [1, −1, −1, 1, 1, −1, 1, −1].

الإجابة

−1 is a 0 bit → 1 0 0 1 1 0 1 0:

(d–g)802.11 collision avoidance · IPv4 header · router architecture · IPv6 unicast address format.

الإجابة

يعني: الأسئلة دي كلها "ارسم" — الرسمة اللي في السلايد هي الإجابة.

Problem 3 — AS-X & AS-Y

السؤال الأصلي

(a)How many LANs in AS-X; routers, bridges, hubs in each.

الإجابة

3 LANs — same as Mid 2022 P4(a): (1) bridges e, i + hubs p, q + A · (2) bridge d + hub r + A + B · (3) bridge c + hubs s, u + A + B.

(b)Is a spanning tree protocol needed? Draw the result.

الإجابة

Yes. Bridges e and i and hubs q, p form loops (q–e, q–i, i–e, i–p, p–e). STP keeps a loop-free tree, e.g. e–q, e–p, e–i (bridge i blocks its ports to q and p).

(c)Can hubs s and u use different technologies?

الإجابة

Yes — each is connected to bridge c, which isolates collision domains and can connect different technologies.

(d)Dijkstra from F and tree.

الإجابة

(e)Center-based with F as center: G and M join.

الإجابة

(Using the least-cost paths of part d.) G → H → N → M → K → J → F (14) → the whole path is the branch. M is already on the tree.

في Mid 2022 كان قبله سؤال RIP فاستخدمنا مسار RIP (G–N–K–F). هنا قبله Dijkstra، فاستخدمنا الأرخص.

(f)RPF with pruning, source F, group F, J, W.

الإجابة

Only G (leaf with no members) prunes to H. Everything else leads to J or W and stays.

(g)RIP at F.

الإجابة

FINAL · FEB 28, 2021 · TERM 2020/2021 · MIDTERM-SCOPE QUESTIONS ONLYFinal 2021

0/3

شيلت P1(a) (OSI مش في سلايدز المنهج ده)، وP2 كله، وP4(a) (virtual circuits). P1(e) هو ASG2 P5 بنفس الأرقام.

Problem 1

السؤال الأصلي

(b)CRC, G = 10011, frame 1110011001.

الإجابة

Remainder 0001 · T = 1110011001 0001

الإجابة

0101 0110 0011 0111 1001 0001 1100 1000
= 5 + 6 + 3 + 7 + 9 + 1 + 12 + 8 = 51 = 110011

(d)4 nodes, slotted ALOHA: sketch its disadvantages.

الإجابة

Same as ASG2 P4(c): slots with collisions (C) and empty slots (E).

(e)CSMA, 4 nodes, 50 bits, 300 bit/s …

الإجابة

Identical to ASG2 P5 — open it there for the full answer and diagram.

Problem 3 — AS-X & AS-Y

السؤال الأصلي

AS-X: routers A–D, bridges q, r, s, hubs e, i, p. AS-Y: 10 routers.

A–D = 3 through bridges (A–q–s–D = 1+1+1), cheaper than through hub p (2+2 = 4)

(a)Is STP needed in AS-X? Draw the result.

الإجابة

Yes. Bridges q, r, s form loops: q–s–r and the two paths q–e–r and q–i–r (through hubs e and i). Frames would cycle and multiply. After STP, e.g.: keep q–s and s–r; bridge r blocks its ports to e and i (hubs e and i stay attached to q only). Result: A–q, q–s, s–r, s–D, q–e, q–i.

يعني: بين q وr فيه 3 طرق (عن طريق s، وعن طريق e، وعن طريق i)، فلازم نقفل اتنين منهم.

(b)Bridge table of one bridge (q).

الإجابة

على الـ LAN دي مفيش hosts، الأجهزة الوحيدة اللي ليها MAC هي interface الراوتر A وinterface الراوتر D. الـ bridges والـ hubs مالهمش MAC.

Address	Interface	Time
MAC(A, interface on q’s LAN)	1 (to A)	10:01
MAC(D, interface on s)	4 (to s)	10:02

(c)ARP table at A.

الإجابة

A عنده interface في كل network: LAN الـ bridges، LAN الـ hub p، لينك A–B، ولينك A–F. الجدول فيه جيرانه على كل واحدة.

IP	MAC	TTL
D (interface on the bridge LAN)	MAC D1	20 min
D (interface on hub p)	MAC D2	20 min
B (link A–B)	MAC B1	20 min
F (link A–F, AS-Y)	MAC F1	20 min

C has no network in common with A → reached via D or B, never in A’s ARP table.

(d)Distance vector in AS-X: (i) initial table at A, (ii) steady table at A, (iii) tree.

الإجابة

افتراض واضح: A–D = 3 (عن طريق الـ bridges، أرخص من الـ hub p = 4)، A–B 6، D–B 2، D–C 5، B–C 2.

A–D (3), D–B (5), B–C (7)

(e)Dijkstra from W in AS-Y and tree.

الإجابة

(f)RPF with pruning, source W, group V, H, K.

الإجابة

F → prune to G; G → prune to H (H member, stops). M → prune to N. T → prune to V (V member).

W–J–H, W–J–K, W–N–V

Problem 4 (b, c)

السؤال الأصلي

(b)Sketch the different routers in OSPF hierarchical routing.

الإجابة

OSPF routers — Internal · area border · backbone · boundary

(c)Sketch the types of switching fabrics.

الإجابة

See Final 2026 P2(b).

MIND MAPParts 1–3 at a glance

الخريطة الكاملة للمادة اللي داخلة في الميدترم. كل عنوان تحته العناوين الفرعية، والأزرق بيوديك للشرح. ذاكر بيها عشان تعرف إنت فين وكل حاجة تابعة لإيه.

Study plan — ذاكر إيه وبعدين حل إيه

#	Slides to study	Topics	Then solve
1	Part 1: 1–20 Part 2: 1–32	Intro · DLL basics · framing · flow/error control · parity, checksum, CRC, Hamming	Assignment 1 (all)
2	Part 2: 33–57	MAC protocols: TDM, FDM, CDMA · slotted ALOHA, CSMA · polling, token	Assignment 2
3	Part 2: 58–96	MAC addresses, ARP · Ethernet · 802.11 · hubs, switches	Assignment 3
4	Part 3: 1–40	Data plane: forwarding vs routing · router architecture · IP addressing, fragmentation · IPv6	Assignment 4 (P1 is on Part 2 hubs/switches)
5	Part 3: 41–68	Routing basics · Dijkstra · distance vector	Assignment 5
6	Part 3: 69–94	RIP, OSPF, IGRP, BGP · ICMP · multicast & IGMP	Assignment 6
7	Part 3: 95–107	Multicast routing: Steiner, center-based, RPF, pruning, protocols	Assignment 7

بعد كل خطوة: ذاكر السلايدز بالشرح العربي، راجع الخلاصة في آخر البارت، وبعدين افتح الأسايمنت وحاول قبل ما تشوف الإجابة. لما تخلص الـ 7 خطوات، حل امتحانات الميدترم من القايمة الجانبية بالوقت (90 دقيقة) قبل ما تفتح الحل، وابدأ بـ Mid 2026.

PART 1Introduction

By transmission

By switching

By scale

الخلاصة — Part 1أهم نقط البارت في سطور؛ راجعها قبل ما تقفله

Definitions

Classification

Layers & protocols

PART 2Data Link Layer

Parity

Checksum

CRC (polynomial code)

Hamming codes

الخلاصة — Part 2أهم نقط البارت في سطور؛ راجعها قبل ما تقفله

2.1 DLL · framing · errors

2.2 Multiple access

2.3 Addresses

2.4 Ethernet · WiFi · hubs/switches

PART 3Network Layer

RIP

OSPF

IGRP

BGP

الخلاصة — Part 3أهم نقط البارت في سطور؛ راجعها قبل ما تقفله

Data plane · router

IP · IPv6

Routing algorithms

Protocols · multicast

ASSIGNMENT 1 · PARTS 1 & 2Intro, Framing & Error Detection

ASSIGNMENT 2 · PART 2CRC, Hamming & MAC Protocols

ASSIGNMENT 3 · PART 2Switches, Ethernet & 802.11

ASSIGNMENT 4 · PARTS 2 & 3Collision Domains, Routers & IP

ASSIGNMENT 5 · PART 3Dijkstra & Distance Vector

ASSIGNMENT 6 · PART 3RIP, OSPF, BGP & IGMP

ASSIGNMENT 7 · PART 3Multicast Routing

MIDTERM · NOV 10, 2025 · TERM 2025/2026Mid 2026

MIDTERM · NOV 18, 2024 · TERM 2024/2025Mid 2025

MIDTERM · NOV 20, 2023 · TERM 2023/2024Mid 2023

MIDTERM · NOV 21, 2022 · TERM 2022/2023Mid 2022

MIDTERM · NOV 30, 2021 · TERM 2021/2022Mid 2021

FINAL · DEC 28, 2025 · TERM 2025/2026 · MIDTERM-SCOPE QUESTIONS ONLYFinal 2026

FINAL · DEC 29, 2024 · TERM 2024/2025 · MIDTERM-SCOPE QUESTIONS ONLYFinal 2025

FINAL · DEC 31, 2023 · TERM 2023/2024 · MIDTERM-SCOPE QUESTIONS ONLYFinal 2024

FINAL · JAN 1, 2023 · TERM 2022/2023 · MIDTERM-SCOPE QUESTIONS ONLYFinal 2023

FINAL · JAN 16, 2022 · TERM 2021/2022 · MIDTERM-SCOPE QUESTIONS ONLYFinal 2022

FINAL · FEB 28, 2021 · TERM 2020/2021 · MIDTERM-SCOPE QUESTIONS ONLYFinal 2021

MIND MAPParts 1–3 at a glance

TOOLSPractice Solvers

QUIZFlashcards