Sachverhalt: Sachverhalt: A. Dr. med. A._ (Kläger) war seit Mai 1996 als Oberarzt und seit 1997 als leitender Arzt bei der Klinik B._ AG (Beklagte) bzw. bei deren Rechtsvorgängerin tätig. Auf den 1. Januar 1998 stellte die Beklagte Dr. med. C._ als Chefarzt ein. In dieser Funktion war er der Vorgesetzte des Klägers, welcher jedoch seine Stellung als leitender Arzt beibehielt. Im August 1999 wurde die Ehefrau des Chefarztes von der Beklagten als Kardiologin angestellt. Am 4. September 2000 führten der Verwaltungsratspräsident und am 25. Oktober 2000 der Verwaltungsdirektor der Beklagten je eine Unterredung mit dem Kläger. Mit Schreiben vom 10. November 2000 kündigte die Beklagte das Arbeitsverhältnis mit dem Kläger auf den 31. Mai 2001. Als Begründung gab sie an, dass das Vertrauensverhältnis innerhalb der medizinischen Leitung bereits seit geraumer Zeit unüberwindlich zerrüttet sei, was eine weitere Zusammenarbeit verunmögliche. Am 14. Dezember 2000 liess der Kläger der Beklagten mitteilen, dass er die Kündigung als missbräuchlich erachte. In den Monaten Januar und Februar 2001 war der Kläger zeitweise ganz oder teilweise arbeitsunfähig. Auf den 5. Juni 2001 trat er eine neue Stelle an. Am 4. September 2000 führten der Verwaltungsratspräsident und am 25. Oktober 2000 der Verwaltungsdirektor der Beklagten je eine Unterredung mit dem Kläger. Mit Schreiben vom 10. November 2000 kündigte die Beklagte das Arbeitsverhältnis mit dem Kläger auf den 31. Mai 2001. Als Begründung gab sie an, dass das Vertrauensverhältnis innerhalb der medizinischen Leitung bereits seit geraumer Zeit unüberwindlich zerrüttet sei, was eine weitere Zusammenarbeit verunmögliche. Am 14. Dezember 2000 liess der Kläger der Beklagten mitteilen, dass er die Kündigung als missbräuchlich erachte. In den Monaten Januar und Februar 2001 war der Kläger zeitweise ganz oder teilweise arbeitsunfähig. Auf den 5. Juni 2001 trat er eine neue Stelle an. B. Mit Klage vom 26. Oktober 2001 verlangte der Kläger vor Kantonsgericht von Appenzell A.Rh. im Wesentlichen die Verpflichtung der Beklagten zur Zahlung von Fr. 150'000.-- nebst Zins. Die Klage wurde mit Urteil vom 1. Juli 2002 im Betrag von Fr. 18'613.05 netto nebst 5 % Zins seit 5. Juni 2001 gutgeheissen. Das Kantonsgericht hielt die Kündigung aufgrund der nachgewiesenen Tatumstände nicht für missbräuchlich. Es sprach dem Kläger jedoch für die Zeit vom 1. bis zum 4. Juni 2001 Lohn von Fr. 2'239.80 zu, für Hintergrunddienst Dezember 2000 - Mai 2001 Fr. 1'392.90 sowie als Abgeltung des Ferienanspruchs Fr. 14'980.35 für 23 Tage. Hinsichtlich der Entschädigung für nicht bezogene Ferien erwog das Kantonsgericht, der Kläger habe sich einen Drittel der nicht durch Krankheit dahingefallenen Freistellungszeit, mithin 1,75 Monate, auf sein Ferienguthaben von 60,52 Tagen anrechnen zu lassen. B. Mit Klage vom 26. Oktober 2001 verlangte der Kläger vor Kantonsgericht von Appenzell A.Rh. im Wesentlichen die Verpflichtung der Beklagten zur Zahlung von Fr. 150'000.-- nebst Zins. Die Klage wurde mit Urteil vom 1. Juli 2002 im Betrag von Fr. 18'613.05 netto nebst 5 % Zins seit 5. Juni 2001 gutgeheissen. Das Kantonsgericht hielt die Kündigung aufgrund der nachgewiesenen Tatumstände nicht für missbräuchlich. Es sprach dem Kläger jedoch für die Zeit vom 1. bis zum 4. Juni 2001 Lohn von Fr. 2'239.80 zu, für Hintergrunddienst Dezember 2000 - Mai 2001 Fr. 1'392.90 sowie als Abgeltung des Ferienanspruchs Fr. 14'980.35 für 23 Tage. Hinsichtlich der Entschädigung für nicht bezogene Ferien erwog das Kantonsgericht, der Kläger habe sich einen Drittel der nicht durch Krankheit dahingefallenen Freistellungszeit, mithin 1,75 Monate, auf sein Ferienguthaben von 60,52 Tagen anrechnen zu lassen. C. Beide Parteien appellierten gegen das Urteil vom 1. Juli 2002. Das Obergericht von Appenzell A.Rh. verpflichtete die Beklagte am 18. November 2003, dem Kläger den Betrag von Fr. 44'873.85 brutto nebst 5 % Zins seit 5. Juni 2001 (Lohn 1.-4. Juni 2001 und Ferienentschädigung) zu bezahlen. Im Mehrbetrag wies es die Klage ab. Darüber hinaus nahm das Obergericht davon Vormerk, dass die Beklagte die Klage im Umfang von Fr. 1'500.-- brutto nebst 5 % Zins seit 5. Juni 2001 (Entschädigung Hintergrunddienst) anerkannt hat. Wie das erstinstanzliche Gericht kam auch das Obergericht zum Ergebnis, dass die Kündigung nicht missbräuchlich sei. Hingegen schützte das Obergericht die Berufung des Klägers betreffend die Position Ferienentschädigung. Es hielt fest, die Beklagte habe mit der Freistellung unmissverständlich die Weisung an den Kläger verbunden, sich während der Freistellungsdauer der Arbeitnehmerin zur Verfügung zu halten. Diese Anordnung habe bis zum Ausscheiden des Klägers aus dem Arbeitsverhältnis mit der Beklagten bestanden. Dass sich der Kläger während der Freistellung mehrheitlich in Karlsruhe aufgehalten habe, sei auf die Kündigung der Wohnung des Klägers in der Klinik zurückzuführen. Der Arbeitnehmer sei nie aufgefordert worden, sich eine Unterkunft in der Nähe des Arbeitsortes zu suchen. Unter diesen Umständen stehe die Weisung der Arbeitgeberin an den Arbeitnehmer, sich zur Verfügung zu halten, dessen Pflicht zum Bezug von Ferientagen während der Freistellungsdauer entgegen. Die Beklagte habe dem Kläger daher das volle Guthaben von 60,52 Ferientagen, insgesamt Fr. 42'448.75 nebst Zins, zu vergüten. Auf Appellation der Beklagten bestätigte die Vorinstanz ferner das erstinstanzliche Urteil, soweit damit die Abgeltung des Lohnes für die Zeit vom 1.-4. Juni 2001 angeordnet worden war. C. Beide Parteien appellierten gegen das Urteil vom 1. Juli 2002. Das Obergericht von Appenzell A.Rh. verpflichtete die Beklagte am 18. November 2003, dem Kläger den Betrag von Fr. 44'873.85 brutto nebst 5 % Zins seit 5. Juni 2001 (Lohn 1.-4. Juni 2001 und Ferienentschädigung) zu bezahlen. Im Mehrbetrag wies es die Klage ab. Darüber hinaus nahm das Obergericht davon Vormerk, dass die Beklagte die Klage im Umfang von Fr. 1'500.-- brutto nebst 5 % Zins seit 5. Juni 2001 (Entschädigung Hintergrunddienst) anerkannt hat. Wie das erstinstanzliche Gericht kam auch das Obergericht zum Ergebnis, dass die Kündigung nicht missbräuchlich sei. Hingegen schützte das Obergericht die Berufung des Klägers betreffend die Position Ferienentschädigung. Es hielt fest, die Beklagte habe mit der Freistellung unmissverständlich die Weisung an den Kläger verbunden, sich während der Freistellungsdauer der Arbeitnehmerin zur Verfügung zu halten. Diese Anordnung habe bis zum Ausscheiden des Klägers aus dem Arbeitsverhältnis mit der Beklagten bestanden. Dass sich der Kläger während der Freistellung mehrheitlich in Karlsruhe aufgehalten habe, sei auf die Kündigung der Wohnung des Klägers in der Klinik zurückzuführen. Der Arbeitnehmer sei nie aufgefordert worden, sich eine Unterkunft in der Nähe des Arbeitsortes zu suchen. Unter diesen Umständen stehe die Weisung der Arbeitgeberin an den Arbeitnehmer, sich zur Verfügung zu halten, dessen Pflicht zum Bezug von Ferientagen während der Freistellungsdauer entgegen. Die Beklagte habe dem Kläger daher das volle Guthaben von 60,52 Ferientagen, insgesamt Fr. 42'448.75 nebst Zins, zu vergüten. Auf Appellation der Beklagten bestätigte die Vorinstanz ferner das erstinstanzliche Urteil, soweit damit die Abgeltung des Lohnes für die Zeit vom 1.-4. Juni 2001 angeordnet worden war. D. Der Kläger hat das Urteil des Obergerichts von Appenzell A.Rh. vom 18. November 2003 mit eidgenössischer Berufung beim Bundesgericht angefochten. Er beantragt, die Beklagte zu verpflichten, ihm Fr. 105'126.15 nebst 5 % Zins seit dem 5. Juni 2001 zu bezahlen. Die Beklagte schliesst auf Abweisung der Berufung, soweit darauf eingetreten werden könne, und sie erhebt Anschlussberufung mit dem Rechtsbegehren, die Forderung des Klägers von Fr. 42'448.75 (Ferienentschädigung) abzuweisen und diesem nur noch Fr. 2'425.10 zuzusprechen; eventuell die Streitsache zur Entscheidung in diesem Punkte an die Vorinstanz zurückzuweisen. Der Kläger stellt den Antrag, die Anschlussberufung abzuweisen. 